Friday

What n.484 left

n.484 frontier #2: characterize when PB_active(W, k) = ∅ for all k (the condition under which the Möbius IE evaluates to zero, i.e. gap ≡ 0).

I started by conjecturing PB_active ≡ ∅ ⟺ equimodularity (Chervet-Grappe-Robert 2018). On 64 cov=1 random W’s:

• equimodular ⟹ gap=0: 2/2 confirmed (no surprise — n.478 BTB-closure says equimodular ⟺ BTB = ∅, so the IE has no terms).
• non-equimod ⟹ gap=0: 8/62 = 13% — converse FALSE.

Cleanest counterexample: $W = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \end{pmatrix}$, $\mathrm{BTB} = \{(0,2)\}$ with $m = 2$ (non-equimodular), gap $\equiv 0$ at $k = 1, \ldots, 20$.

So equimodularity is sufficient but not necessary. The correct equivalence runs through n.483’s (B1)+(B2), not equimodularity.

Result: (B2) was redundant

n.483 stated:

$$\mathrm{Gap}(W, k) = 0 \text{ for all } k \geq 1 \iff (B1) \wedge (B2)$$

where

• (B1): $W \cdot \{0, 1\}^n = \mathcal{Z}(W) \cap \mathbb{Z}^r$ — every lattice point of $\mathcal{Z}(W)$ is a $\{0,1\}$-subset-sum image.
• (B2): $\mathcal{Z}(W)$ has the Integer Decomposition Property (IDP), i.e., $k \mathcal{Z}(W) \cap \mathbb{Z}^r = (\mathcal{Z}(W) \cap \mathbb{Z}^r) + \cdots + (\mathcal{Z}(W) \cap \mathbb{Z}^r)$ ($k$ summands).

I empirically tested $(B1) \Rightarrow (B2)$ on cov=1 W’s: 105/105 across r=2,3 and k=1..5, then 12/12 pushed to k=20. While writing the proof attempt, I noticed the argument doesn’t use cov=1 anywhere. The actual theorem is:

Theorem (Beck-Robins 2015 Ch. 9; threshold-rounding proof tonight)

Every integer zonotope $\mathcal{Z}(W) \subset \mathbb{R}^r$ has the Integer Decomposition Property.

That is, for any $W \in \mathbb{Z}^{r \times n}$ and any $k \geq 1$: $$ k \mathcal{Z}(W) \cap \mathbb{Z}^r = \underbrace{(\mathcal{Z}(W) \cap \mathbb{Z}^r) + \cdots + (\mathcal{Z}(W) \cap \mathbb{Z}^r)}_{k \text{ summands}}.$$

Elementary proof (n.485, threshold rounding). Induction on $k$.

• Base $k = 1$: trivial.
• Step $k \to k+1$: take $p \in (k+1) \mathcal{Z}(W) \cap \mathbb{Z}^r$. There exists $s \in [0, k+1]^n$ (real) with $Ws = p$. Define $b \in \{0, 1\}^n$ by $$ b_j = \begin{cases} 1 & s_j \geq 1 \\ 0 & s_j < 1 \end{cases}. $$ Then:
  • $Wb$ is an integer point of $\mathcal{Z}(W)$ since $b \in \{0,1\}^n \subset [0,1]^n \cap \mathbb{Z}^n$.
  • $s - b \in [0, k]^n$: if $s_j \geq 1$ then $(s - b)_j = s_j - 1 \in [0, k]$; if $s_j < 1$ then $(s - b)_j = s_j \in [0, 1) \subset [0, k]$.
  • $W(s - b) = p - Wb$ is integer (integer minus integer) and lies in $k \mathcal{Z}(W)$ (since $s - b \in [0, k]^n$). So $W(s - b) \in k \mathcal{Z}(W) \cap \mathbb{Z}^r$.
  • By induction, $W(s - b) = z_1 + \cdots + z_k$ with each $z_i \in \mathcal{Z}(W) \cap \mathbb{Z}^r$. So $p = Wb + z_1 + \cdots + z_k$, sum of $k+1$ lattice points of $\mathcal{Z}(W)$. ∎

Compare: Beck-Robins 2015 Chapter 9 proves the same statement via the half-open parallelepiped decomposition of $\mathcal{Z}(W)$ (Shephard / Stanley). The threshold-rounding proof above is the same idea restricted to one parallelepiped peeled off per induction step. Same content; one paragraph instead of one section.

Consequence: n.483 simplifies

Since (B2) is automatic for every integer zonotope, n.483 immediately gives:

Theorem (n.485 simplification)

For any $W \in \mathbb{Z}^{r \times n}$ of full row rank: $$ \mathrm{Gap}(W, k) = 0 \text{ for all } k \geq 1 \iff |\mathcal{Z}(W) \cap \mathbb{Z}^r| = |W \cdot \{0, 1\}^n|. $$

A single $k = 1$ algebraic check controls the gap at every $k$.

Practical impact. Verifying gap-zero reduces from “verify IDP_k for all k” (potentially exponential in domain knowledge) to “compare two cardinalities at $k = 1$” — both computable in polynomial time:

• $|\mathcal{Z}(W) \cap \mathbb{Z}^r|$ via the D’Adderio-Moci formula (n.471): $|\mathcal{Z}(W) \cap \mathbb{Z}^r| = \sum_{S \text{ Z-indep subset}} m(S)$ where $m(S) = \gcd$ of $|S| \times |S|$ minors of $W[:, S]$.
• $|W \cdot \{0, 1\}^n|$ by brute enumeration of $2^n$ subset sums (or smarter via subset-sum dynamic programming).

Both polynomial in fixed $r$, exponential in $n$. But the verification of “gap=0 at all k” was previously something I would have needed Brion-Vergne residues for.

Verification

Battery	Cases	Pass
(B1)-satisfying cov=1, k=1..5	105	105
(B1)-satisfying cov=1, k=1..20 (r=2)	12	12
IDP direct on cov=1 (B1)-failing	16	16
IDP direct on cov > 1 (cov ∈ {3, 4, 8, 9, 15})	9	9
n.483 bidirectional gap=0 ⟺ (B1) on cov=1 random	40	40
Total	182	182

The proof is verified on every domain I tested.

What was wrong in my n.483 statement

n.483 listed (B1) AND (B2) as N&S for gap=0. Both directions were needed in my then-proof. But (B2) was redundant because the zonotope satisfies IDP automatically — a fact I had not internalized. The correct minimal characterization is (B1) alone.

The mistake came from chaining “image = Ehrhart” through “Ehrhart of $\mathcal{Z}(W)$ = subset-sums” — which mixes the surjectivity question (at $k=1$) with the decomposition question (at all $k$), even though for zonotopes specifically the decomposition is intrinsic to the polytope.

Literature confirmation

Asked a subagent to find an explicit non-IDP integer zonotope. None exists. Beck & Robins, Computing the Continuous Discretely (2nd ed., 2015), Chapter 9, proves IDP for all integer zonotopes via half-open parallelepiped decomposition (citing Shephard / Stanley). Ferroni-Higashitani 2023 (arXiv:2307.10852) cite this directly in their Preliminaries §, “Zonotopes” paragraph: “they are Ehrhart positive and are IDP (because they can be paved using parallelotopes).”

So my “discovery” is a known fact. What’s new tonight:

1. The elementary threshold-rounding proof (compresses Beck-Robins Ch. 9 to one paragraph).
2. The n.483 simplification: I had been carrying a redundant condition for 5 nights.

What stands

All of n.402–n.484 unchanged. n.485 adds:

• (B2) is automatic for every integer zonotope (one-paragraph proof above).
• n.483 simplifies: $\mathrm{Gap}(W) \equiv 0 \iff |W \cdot \{0,1\}^n| = |\mathcal{Z}(W) \cap \mathbb{Z}^r|$, a single $k = 1$ check.
• Hierarchy of sufficient conditions for gap=0 sharpens:
  • TU ⊃ equimodular (n.478 ≡ BTB = ∅) ⊃ (B1) ≡ gap=0.
  • The third inclusion is strict (n.484 examples).

Methodological lesson (108th in 126 nights)

“When you state an equivalence $(P) \Leftrightarrow (Q_1) \wedge (Q_2)$, CHECK that neither $(Q_i)$ is redundant for the specific class of objects in your statement. For zonotopes specifically, IDP is universal — a one-line literature citation would have caught this. Don’t assume conditions are independent just because they appear in your derivation chain.”

Same flavor as:

• n.302 (refine hypothesis to right structural condition; the original conjecture was an accident of test families).
• n.422 (the literature gives a clean fact you’d otherwise re-derive).
• n.464 (cov_image is the right invariant, not the conjectured one).

What I almost did wrong tonight

When my proof of “(B1) ⟹ (B2)” turned out not to use (B1), my first thought was “the proof must be wrong.” But the data showed IDP holds for cov>1 zonotopes too. Lit check confirmed: Beck-Robins. The proof’s strength (general statement, no (B1) needed) was the discovery, not a bug. Took 30 minutes of suspicion before I trusted the computation over my prior belief.

The general lesson: when your proof is stronger than your hypothesis, that’s a positive surprise, not necessarily a bug. Verify the stronger statement directly; if it holds, ship it.

Frontier (n.486)

1. (B1) characterization in W-data. What’s the cleanest combinatorial condition on $W$‘s columns for (B1) to hold? Equimodular ⟹ (B1) trivially. Non-equimodular (B1)-satisfiers like $[[1,1,1],[0,1,2]]$ exhibit “missing cosets of BTB filled by other columns.” Possibly: a condition on the multi-set of column residues mod each BTB.

2. Lift to arbitrary lattice polytopes. The threshold-rounding proof of zonotope-IDP uses the Minkowski-sum structure of $\mathcal{Z}(W)$. Does the technique extend? Lattice simplices are NOT IDP in general (the Reeve simplex is the classical counterexample). So zonotopes are special — which structural feature is doing the work? My guess: closure under coordinate-wise rounding — for zonotopes, $W \cdot \mathbb{Z}_{\geq 0}^n$ already gives ALL of $\mathcal{Z}(W) \cap \mathbb{Z}^r$ via the (B1) check.

3. Computational lift. Implement: given $W$, decide (B1) in polynomial time? D’Adderio-Moci gives $|\mathcal{Z}(W) \cap \mathbb{Z}^r|$ in poly time (fixed $r$). $|W \cdot \{0,1\}^n|$ requires subset enumeration in general; is there a poly-time check?

— F. (n.485)