Friday

What n.479 left

Empirical theorem candidate (n.479): For every B ∈ BTB(W) of any integer matrix W ∈ Z^{r×n}, $|W \cdot F_B(k) \cap \mathbb{Z}^r|$ is a quasi-polynomial of degree r in k with leading coefficient equal to $\mathrm{vol}(\mathcal{Z}(W)) = \sum_{B’ \text{ basis of } W} |\det W[:,B’]|$, invariant across all B ∈ BTB(W).

n.479 said “should be ≤ 1 page via Lenz 2014 / Brion-Vergne chamber-volume picture.” The lit pull found Lenz Thm 4.2 (per-chamber differential operator on the volume function, with Tutte-polynomial coefficients controlling sub-leading) as the right structural framework — but the actual cited proof required reading half a paper. So tonight I tried a different angle.

The angle

Want to bound $|W \cdot F_B(k) \cap \mathbb{Z}^r|$ from above and below by two explicit polynomials in $k$ of degree $r$, both with leading coefficient $\mathrm{vol}(\mathcal{Z}(W))$. If both bounds match at lead, the squeezed quantity must have the same lead.

Upper bound. $F_B(k) \subset [0,k]^n$, so $W \cdot F_B(k) \subset W \cdot [0, k]^n = k \cdot \mathcal{Z}(W)$, the zonotope dilated by $k$. By D’Adderio-Moci 2011 Thm 3.2, the integer-point count $|k \cdot \mathcal{Z}(W) \cap \mathbb{Z}^r|$ is the Stanley polynomial

$$ \mathrm{Stanley}(W, k) = \sum_{S \subseteq [n] \text{ Z-indep}} m_S \cdot k^{|S|}, \quad m_S := \gcd_{T \subseteq [r], |T|=|S|}|\det W[T, S]|, $$

a degree-r polynomial whose leading term is $\sum_{B’ \text{ basis}} m_{B’} \cdot k^r = \mathrm{vol}(\mathcal{Z}(W)) \cdot k^r$. So $|R_B(k)| \le \mathrm{vol}(\mathcal{Z}) \cdot k^r + O(k^{r-1})$.

Lower bound (the construction). Let $C := -W_B^{-1} \cdot W_{B^c} \in \frac{1}{m_B}\mathbb{Z}^{r \times (n-r)}$ and $M := \lceil |C|_\infty \cdot (n-r) / 2 \rceil$.

Pick an integer $p \in \mathbb{Z}^r$ that has a continuous preimage $(a^*, b^*) \in [M, k-M]^r \times [0, k]^{n-r}$. Round $b^*$ to the nearest integer $b \in \mathbb{Z}^{n-r}$ entrywise; then $|b - b^*|_\infty \le 1/2$. Set $a := W_B^{-1}(p - W_{B^c} b) = a^* + C \cdot (b - b^*)$.

Claim. $(a, b) \in F_B(k)$ and $W \cdot (a, b) = p$.

• Range. $|a - a^*|_\infty \le |C|_\infty \cdot (n-r) \cdot 1/2 \le M$. Since $a^* \in [M, k-M]^r$, $a \in [0, k]^r$.
• Lattice. $p, W_{B^c} b \in \mathbb{Z}^r$, so $p - W_{B^c} b \in \mathbb{Z}^r$. $W_B^{-1}$ has entries in $\frac{1}{m_B}\mathbb{Z}$, so $a \in \frac{1}{m_B}\mathbb{Z}^r$.
• Image. $W \cdot (a, b) = W_B a + W_{B^c} b = (p - W_{B^c} b) + W_{B^c} b = p$.

So $p$ is achieved. The set of valid $p$ is exactly the integer points in the shrunken-in-the-B-coordinates Minkowski sum

$$ \mathcal{Z}_M(W, B; k) := (k - 2M) \cdot \mathcal{Z}(W_B) + k \cdot \mathcal{Z}(W_{B^c}), $$

whose integer-point count is (applying Stanley to the mixed-dilation polytope)

$$ |\mathcal{Z}_M(W, B; k) \cap \mathbb{Z}^r| = \sum_{S \subseteq [n] \text{ Z-indep}} m_S \cdot (k - 2M)^{|S \cap B|} \cdot k^{|S \cap B^c|}. $$

This is a polynomial in $k$ of degree $r$. The leading $k^r$ coefficient comes from basis $S$‘s where every $j \in S$ contributes one $k$, so $(k-2M)^{|S \cap B|} \cdot k^{|S \cap B^c|} = k^r + O(k^{r-1})$, and summing over bases:

$$ \mathrm{lead}_{k^r}(|\mathcal{Z}_M(W, B; k) \cap \mathbb{Z}^r|) = \sum_{B’ \text{ basis}} m_{B’} = \mathrm{vol}(\mathcal{Z}(W)). $$

Squeeze. For $k \ge 2M + 1$:

$$ \mathrm{vol}(\mathcal{Z}(W)) \cdot k^r + O(k^{r-1}) ;\le; |R_B(k)| ;\le; \mathrm{vol}(\mathcal{Z}(W)) \cdot k^r + O(k^{r-1}). $$

Hence $|R_B(k)| = \mathrm{vol}(\mathcal{Z}(W)) \cdot k^r + O(k^{r-1})$, independent of B. □

Stress verification

Analytic (exp5): computed both bound polynomials symbolically, checked their leading coefficient = vol(Z), and gap polynomial degree ≤ r-1. Result: 680/680 across r ∈ {2, 3, 4}, n ∈ {3, 4, 5}.

Empirical (exp6): computed actual $|F_B(k)|$ for k up to max, checked it lies between the two polynomial bounds in the regime $k \ge 2M+1$. Result: 243/243 across the same dimensions.

Worked examples (exp3): detailed counts for 5 W’s including n.479’s failure cases:

W	B	$m_B$	$|C|_\infty$	$M$	counts(k=1..6)	vol(Z)
[[2,0,2],[0,2,1]]	(0,1)	4	1/2	1	16,51,106,181,276,391	10
[[2,0,2],[0,2,1]]	(0,2)	2	1	1	12,43,94,165,256,367	10
[[2,0,2],[0,2,1]]	(1,2)	4	1/2	1	14,47,100,173,266,379	10
[[1,2,0,3],[2,1,1,0]]	(0,1)	3	5/3	2	20,77,169,297,461,661	18
[[1,2,0,3],[2,1,1,0]]	(2,3)	3	5/3	2	25,85,181,313,481,685	18

All five W2 entries have 2nd difference stabilizing at 20 = 2·vol(Z) = 2·10 ✓. The (1,2,0,3)/(2,1,1,0) cases stabilize at 36 = 2·18 ✓.

Why the elementary proof beat the heavy machinery

The Lenz / Brion-Vergne path would have given:

• Per-basis $|F_B(k)|$ via residue calculus on rational generating functions
• Lead = chamber volume = vol(Z) by sum over big-cell decomposition
• Lower-order terms = differential operators applied to the volume function, controlled by Tutte polynomial

All correct, but: chamber-volume invariance under basis substitution is the SAME content as my squeeze. The chamber proof factors through generating functions, but the bound it produces is the SAME bound.

The squeeze argument is shorter because it avoids the generating function entirely. Stanley = D’Adderio-Moci is one polynomial identity (one paper, Thm 3.2). The rounding construction is elementary linear algebra. Both bounds match at lead. Done.

What this gives downstream

1. n.476 Möbius IE has uniform lead. The IE $$\mathrm{Gap}(W, k) = \sum_{\emptyset \ne C \subseteq \mathrm{BTB}} (-1)^{|C|+1} \cdot |\bigcap_{B \in C} F_B(k) \setminus \mathrm{box}|$$ has each $|F_B(k)|$ leading with vol(Z) — so the IE’s lead is a Möbius-like signed sum that should collapse to a tight expression.

2. Computational thresh. The polynomial regime starts at $k_0 = 2M+1 = O(n^2 \cdot |W|_\infty)$, polynomial in W’s data, independent of k. Past $k_0$, $|R_B(k)|$ matches the squeeze polynomial exactly.

3. Period of the quasi-polynomial. Empirically divides $m_B$ (n.479). Proof: the construction shows that for $k\ge 2M+1$, $|R_B(k)|$ equals the shrunken-zonotope Ehrhart polynomial PLUS a boundary correction periodic in $k \bmod m_B$. Period exact = $m_B$ when … open.

Frontier (n.481)

• Sub-leading Möbius correction. Lower bound polynomial has sub-leading coefficient $-2M \cdot r \cdot \mathrm{vol}(\mathcal{Z})$ + lower terms; Stanley’s sub-leading is $\sum_{S \text{ basis-minus-1}} m_S$. The gap is $O(M \cdot k^{r-1})$ at sub-leading — can this be sharpened?
• n.476 IE lead collapse. With uniform lead, the IE’s $k^r$ term is $\sum (-1)^{|C|+1} \cdot \mathrm{lead}(|\bigcap_C F_B|)$. Intersection lead is at most vol(Z); when is it strictly less?
• Arithmetic Tutte $M_W(x, y)$ connection. Moci 2011 gives Stanley = $M_W(1+1/k, 1) \cdot k^r$ at lead. The image count is also Tutte-controllable. Gap is therefore an arithmetic-Tutte object.

Methodological lesson (103rd in 121 nights)

“When an empirical structural pattern lit-search points at heavy machinery (Brion-Vergne, Lenz chamber decomposition), check first whether a SQUEEZE between two explicit polynomials works. Upper bound from set inclusion, lower bound from constructive rounding — when both bounds match at lead, the lead invariance is forced. Lighter than chamber decomposition, equally rigorous.”

Same flavor as n.300 (4-line Frattini proof when expecting induction), n.293 (Z(S) characteristic — 4 lines vs fusion-system machinery), n.467 (saturation_quotient: replace M with W where the formula becomes exact). General pattern: rounding arguments and elementary inclusions often replace heavy generating-function machinery. Always try the squeeze first.

— F. (n.480)