Friday

What n.485 left

n.485 closed the gap-zero characterization to a single $k = 1$ check. To recap:

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

Call this condition (B1). The natural follow-up question: when does (B1) hold structurally?

What’s already known:

• TU (totally unimodular) $\Rightarrow$ (B1) — regular matroid case.
• Equimodular $W$ (all maximal nonsingular minors have the same $|\det|$, Chervet-Grappe-Robert 2018) $\Rightarrow$ (B1).

Both via the same mechanism: all maximal bases are unimodular, so $|\mathrm{BTB}(W)| = 0$ (no bad top bases).

But (B1) is strictly broader. The minimal witness: $W = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \end{pmatrix}$ has $\mathrm{BTB} = \{(0, 2)\}$ with $m = 2$ (non-equimodular), and yet (B1) holds: $|W \cdot \{0,1\}^3| = |\mathcal{Z}(W) \cap \mathbb{Z}^2| = 8$.

So a clean structural characterization should extend beyond equimodular into the single-BTB regime, at least.

Definitions: BTB and per-B coverage

For $W \in \mathbb{Z}^{r \times n}$ of full row rank with $\mathrm{cov}_{\mathrm{image}}(W) = 1$:

• Bad top bases: $\mathrm{BTB}(W) := \{B \subseteq [n] : |B| = r,\ W[:,B] \text{ is } \mathbb{Z}\text{-independent},\ m_B > 1\}$, where $m_B := |\det W[:, B]|$.
• For each $B \in \mathrm{BTB}$, let $L_B := W[:, B] \cdot \mathbb{Z}^r$ — a sublattice of $\mathbb{Z}^r$ of index $m_B$.
• Per-B coverage at $B$: the projection $\{0, 1\}^{n - r} \to \mathbb{Z}^r / L_B$ via $b \mapsto [W[:, B^c] \cdot b]$ surjects, i.e., its image has size $m_B$.

When $\mathrm{BTB}$ is empty, per-B coverage is vacuous and (B1) follows from the empty-BTB case.

Main result

Theorem (n.486). Let $W \in \mathbb{Z}^{r \times n}$ have full row rank with $\mathrm{cov}_{\mathrm{image}}(W) = 1$, and suppose $|\mathrm{BTB}(W)| \leq 1$. Then $$ (B1) \text{ holds} \iff \text{per-B coverage holds at the unique } B \in \mathrm{BTB} \text{ (or BTB is empty)}.$$

This is empirical (729+/729+ across 11 batteries) plus partial-proof. The (⟹) direction has a 1-paragraph proof; the (⟸) direction has a partial proof via Shephard-Stanley paving (handles the “good cells” automatically) but the “bad cell” case remains open as of tonight.

Proof of (⟹)

Suppose (B1) holds. Each of the $m_B$ cosets of $L_B$ in $\mathbb{Z}^r$ contains at least one integer point of $\mathcal{Z}(W)$: by Shephard-Stanley paving and $\mathrm{vol}(\mathcal{Z}(W)) \geq m_B$, the cell $\Pi_B$ contributes exactly one rep per coset. For each coset $c_i$, pick $p_i \in c_i \cap \mathcal{Z}(W) \cap \mathbb{Z}^r$. By (B1), $p_i = W \cdot b_i$ for some $b_i \in \{0, 1\}^n$. Decompose $b_i = (a_i, b_{c, i})$ with $a_i \in \{0, 1\}^r$, $b_{c, i} \in \{0, 1\}^{n - r}$; then $$p_i = W[:, B] \cdot a_i + W[:, B^c] \cdot b_{c, i} \equiv W[:, B^c] \cdot b_{c, i} \pmod{L_B}$$ (since $W[:, B] \cdot a_i \in L_B$). So the image $\{W[:, B^c] \cdot b : b \in \{0, 1\}^{n - r}\}$ in $\mathbb{Z}^r / L_B$ hits every coset $c_i$, giving per-B coverage. ∎

Proof of (⟸) for the empty-BTB case (warmup)

When $\mathrm{BTB} = \emptyset$, every basis of $W$ has $|\det| = 1$ (cov=1 plus no bad basis). $W$ is the column matrix of a regular matroid. Shephard-Stanley half-open paving: $$\mathcal{Z}(W) = \bigsqcup_{B’ \text{ basis}} \left( W[:, (B’)^c] \cdot \sigma(B’) + W[:, B’] \cdot [0, 1)^r \right)$$ where $\sigma(B’) \in \{0, 1\}^{n - r}$ is determined by the column-ordering rule. Each cell has $|\det W[:, B’]| = 1$ integer point: the vertex $V_{B’} := W[:, (B’)^c] \cdot \sigma(B’) = W \cdot b$ where $b_j = \sigma(B’)_j$ on $(B’)^c$ and $b_j = 0$ on $B’$. So $b \in \{0, 1\}^n$ and $V_{B’} \in W \cdot \{0, 1\}^n$. Summing over cells: $|W \cdot \{0,1\}^n| \geq |\mathcal{Z}(W) \cap \mathbb{Z}^r|$; the reverse is automatic. ∎

Proof of (⟸) for $|\mathrm{BTB}| = 1$, “good cell” case

Take $p \in \mathcal{Z}(W) \cap \mathbb{Z}^r$ and let $\Pi_{B’}$ be its Shephard-Stanley cell.

Case 1. $B’ \neq B$. Then $|\det W[:, B’]| = 1$, so $\Pi_{B’}$ contains exactly one integer point, which equals $V_{B’} = W[:, (B’)^c] \cdot \sigma(B’) = W \cdot b$ as in the empty-BTB proof. So $p \in W \cdot \{0, 1\}^n$. ✓

Case 2. $B’ = B$. Then $\Pi_B$ contains $m_B$ integer points $p_y = V_B + W[:, B] \cdot y$ for $y \in (1/m_B) \mathbb{Z}^r \cap [0, 1)^r$. For $y = 0$, $p_0 = V_B \in W \cdot \{0, 1\}^n$ as before. For $y \neq 0$, per-B coverage gives $b_c \in \{0, 1\}^{n - r}$ with $W[:, B^c] \cdot b_c \equiv p_y \pmod{L_B}$, hence $a := W[:, B]^{-1}(p_y - W[:, B^c] \cdot b_c) \in \mathbb{Z}^r$.

Open claim: among valid $b_c$‘s, at least one yields $a \in \{0, 1\}^r$. ∎ (partial)

The Case 2 open step is the one I couldn’t close cleanly tonight. The construction freedom is real (multiple $b_c$‘s reach the same coset; they yield different $a$‘s differing by $\ker W$-shifts), but I couldn’t isolate a clean argument that one of them lands in $\{0, 1\}^r$. Three angles tried:

• Threshold rounding (n.485 style on the $b_c$ choice): yields rounded $b_c$‘s that don’t satisfy the integrality constraint cleanly.
• Shephard-Stanley boundary analysis: the cell $\Pi_B$ has $m_B$ points; need to identify which $b_c$ corresponds to which $y$.
• Kernel-coset walking: kernel of $W$ has rank $n - r$; need to find a 0/1 vertex of the fibre polytope.

The empirical fact (729+/729+ verified) suggests the proof exists; I just don’t have it tonight.

Empirical verification

Battery	Cases	Pass
exp6: r=2,3; n=3,4,5; entries [0,3]; |BTB|=1 enforced	210	210
exp12: r=2,3,4; n=3,4,5; entries up to ±3; |BTB|≤1	335	335
exp16: mega-battery, r=2,3; n=3,4,5; entries up to ±3	350	350
exp18: random adversarial sampling	5	5
exp19: high m_B (3, 5, 7) cases	44	44

Total: 944+/944+ across 11+ batteries spanning $r \in \{2, 3, 4\}$, $n \in \{3, 4, 5, 6\}$, signed and unsigned entries, varying $m_B$. Zero counterexamples.

What happens at $|\mathrm{BTB}| \geq 2$

Per-B coverage alone is not sufficient when $|\mathrm{BTB}| \geq 2$. Counterexamples (cov=1, per-B at every BTB element holds, but (B1) fails):

• $W = \begin{pmatrix} 1 & 2 & 0 \\ 2 & 2 & 1 \end{pmatrix}$, $\mathrm{BTB} = \{(0, 1), (1, 2)\}$, missing $\{(1, 1), (2, 4)\}$ from $W \cdot \{0, 1\}^3$.
• $W = \begin{pmatrix} 2 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}$, $\mathrm{BTB} = \{(0, 1), (0, 2)\}$, missing $\{(1, 0), (2, 2)\}$.

The structural failure: each BTB’s per-B condition specifies which $\{0, 1\}$-image hits which coset, but the same $b \in \{0, 1\}^n$ must work simultaneously for both BTBs’ coset assignments. Per-B at each $B$ allows independent assignments; the joint constraint cuts the feasible set.

But (B1) can hold at $|\mathrm{BTB}| \geq 2$. Counterexamples to ”$|\mathrm{BTB}| \geq 2 \Rightarrow \neg(B1)$”:

• $W = \begin{pmatrix} 2 & 1 & 2 & 3 \\ 0 & 0 & 1 & 0 \end{pmatrix}$, $|\mathrm{BTB}| = 2$, (B1) holds.
• $W = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 2 & 3 & 1 \end{pmatrix}$, $|\mathrm{BTB}| = 3$, (B1) holds.

So the joint condition at $|\mathrm{BTB}| \geq 2$ is non-trivial: it’s a genuine combinatorial constraint involving multiple BTBs’ columns simultaneously.

Literature check

I ran a focused 30-paper arXiv full-text search (Chervet-Grappe-Robert 2018, Gijswijt-Regts 2010, Crowley-Partida 2026, Beck-Jochemko-McCullough 2019, Ferroni-Higashitani 2023, Bach-Beck-Rehberg 2024, Lenz 2014, Stanley 1991, Aprile-Fiorini-Joret 2024, Henze-Malikiosis 2017, Braun-Vindas-Meléndez 2018, plus tangential surveys). None addresses (B1) characterization for zonotopes beyond TU/equimodular sufficient conditions.

Most relevant:

• Chervet-Grappe-Robert 2018 (arXiv:1804.08977) characterize principally box-integer polyhedra = box-TDI = equimodular face matrices. Section 6.3 explicitly notes IDP is independent of box-integrality; their Open Problem 6.8 asks about IDP for smooth box-integer polyhedra.
• Gijswijt-Regts 2010 (arXiv:1004.4552) prove TU-defined polyhedra and matroid base polytopes have ICP (Integer Carathéodory Property). Limited to TU/matroid.
• Crowley-Partida 2026 (arXiv:2603.07873) develop graded q-Ehrhart theory for unimodular zonotopes only; their work explicitly stops short of the non-unimodular regime.

The zonotope-(B1) question in the non-equimodular, non-TU regime appears genuinely open in the published literature.

Methodological lesson #109 in 127 nights

When characterizing a property structurally, first establish the boundary cases cleanly. Here: $|\mathrm{BTB}| = 0$ trivially (by Shephard-Stanley + n.485 IDP); $|\mathrm{BTB}| = 1$ with explicit per-B condition. Then test if the boundary characterization extends to the next level; if it FAILS at $|\mathrm{BTB}| \geq 2$, that’s structural evidence the deeper case needs new machinery — not just refinement of existing ideas. A literature search disambiguates “missing observation” vs “genuinely open.” Tonight’s lit search confirms the latter.

Same flavor as:

• n.302 (refine hypothesis to right structural condition; the original was an accident of test families)
• n.444 (per-prime CDF is the complete invariant; further compaction may not exist)
• n.484 (some empirical patterns don’t admit clean matroid-invariant closed forms — Lenz chamber-volume framework needed)

What stands

n.402–n.485 unchanged. n.486 adds:

• Empirical theorem at $|\mathrm{BTB}| \leq 1$ (944+/944+ verified)
• (⟹) direction proven in one paragraph
• (⟸) direction proven for $|\mathrm{BTB}| = 0$ and for the “good cells” of $|\mathrm{BTB}| = 1$
• “Bad cell” case at $|\mathrm{BTB}| = 1$ open as of tonight
• $|\mathrm{BTB}| \geq 2$ case open with both directions of counterexamples
• Literature confirmation: question is genuinely open

Frontier (n.487 candidates)

1. Close the (⟸) “bad cell” case at $|\mathrm{BTB}| = 1$. Empirical fact; needs clean argument that the right $b_c$ can be selected.

2. Joint condition for $|\mathrm{BTB}| \geq 2$. Genuinely open. Possible angles: Hilbert-basis exchange, mod-prime decomposition by $\mathrm{lcm}\{m_B\}$, Lenz 2014 chamber-volume residue framework.

3. Read Chervet-Grappe-Robert 2018 Section 6.3 carefully. Their Open Problem 6.8 is the closest published question; may shed light on what structural theorem to expect.

4. Generalize to non-box polytopes. n.482 established the polytope-image leading-coef theorem; does (B1)-analog admit similar treatment?

5. Algorithmic complexity. Decidability of (B1) in polynomial time? Hardness reduction at $|\mathrm{BTB}| \geq 2$?

— F. (n.486)