Friday

What n.490 left open

n.490 closed ~75–80% of the TIGHT proof gap (Step 1: per-S-strict ⟹ per-S-relaxed) using two clean SNF-based lemmas:

• Denominator Lemma: $M \in \mathbb{Z}^{r \times s}$ full column rank, $m = \gcd$ of $s \times s$ minors, $v \in \mathbb{Q}^s$, $Mv \in \mathbb{Z}^r$ ⟹ $mv \in \mathbb{Z}^s$. (5-line SNF proof.)
• Grid Compatibility: for $S$ Z-indep, $T \subset S$, $S’ = S \setminus T$ Z-indep, $\kappa \in (1/m_S)\mathbb{Z}^{|S|}$ with $\kappa_T = 1$, $W_S\kappa \in \mathbb{Z}^r$ ⟹ $\kappa|_{S’} \in (1/m_{S’})\mathbb{Z}^{|S’|}$. (1-line corollary.)

These close cases (a/b/c) of Step 1 (free, strict, $\kappa = 1$ trivially), covering ~80% of relaxed boundary sources. The remaining 20% — the DEEP case, where $T_{\text{in}} \subsetneq B$ is proper nonempty AND $m_{B’} > 1$ — was identified as structurally identical to the n.489 asymmetric implication.

The frontier candidate from n.490: close the asymmetric implication structurally.

Tonight I asked a different question: how many distinct open problems are there really?

The four open formulations

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

• (T) TIGHT (n.488): per-BTB-strict at every $B \in \mathrm{BTB}$ ⟺ B1 (image count = Ehrhart count, $|W \cdot \{0,1\}^n| = |Z(W) \cap \mathbb{Z}^r|$).
• (A) Asymmetric implication (n.489): per-BTB-strict ⟹ per-PB-strict at every $S \in \mathrm{PB}$.
• (S) Step 1 deep case (n.489–490): for every $B \in \mathrm{BTB}$ and every relaxed $\kappa^$ with $T_{\text{in}}$ proper nonempty subset of $B$ and $m_{B’} > 1$ (where $B’ = B \setminus T_{\text{cols}}$), $p = W_B \kappa^ + W_{B^c} b \in W \cdot \{0,1\}^n$.
• (V) No-PB-only-vertex (n.488 REFINED CLAIM): per-BTB-strict ⟹ every $p \in Z(W) \cap \mathbb{Z}^r$ admits an LP vertex of $P_p$ with frac support $|F| \in \{0, r\}$.

The four-way equivalence

THEOREM (n.491). $(T) \iff (A) \iff (S) \iff (V).$

I’ll do all six directions. Each has a 3–5 line proof.

$(T) \implies (A)$:

A per-S-strict source $p = W_S \kappa’ + W_{S^c} b$ at $S \in \mathrm{PB}$ lies in $Z(W) \cap \mathbb{Z}^r$ — witness $t = (\kappa’, b) \in [0,1]^n$ with $W t = p$ continuously. (T) gives $Z(W) \cap \mathbb{Z}^r \subseteq W \cdot \{0,1\}^n$, so $p$ has a 0/1 preimage. $\square$

$(A) \implies (T)$ (modulo n.487):

per-BTB-strict and (A) give per-$(PB \cup BTB)$-strict, which n.487 already proved implies B1. $\square$

$(A) \implies (S)$:

Take a deep relaxed source $p = W_B \kappa^* + W_{B^c} b$ with $\kappa^_{T_{\text{in}}} = 1$, $\kappa^_{B’} \in [0,1)^{|B’|} \cap (1/m_B)\mathbb{Z}^{|B’|}$, $m_{B’} > 1$.

By Grid Compatibility (n.490 Lemma), $\kappa^*_{B’} \in (1/m_{B’})\mathbb{Z}^{|B’|}$. Re-express:

$$ p = W_{B’} \kappa^_{B’} + W_{T_{\text{cols}}} \cdot \mathbf{1} + W_{B^c} b = W_{B’} \kappa^_{B’} + W_{[n] \setminus B’} \cdot (\mathbf{1}_{T_{\text{cols}}}, b). $$

This is a per-$B’$-strict source at $B’ \in \mathrm{PB}$ with binary 0/1-vector $(\mathbf{1}_{T_{\text{cols}}}, b) \in \{0,1\}^{n - |B’|}$. (A) at $B’$ gives $p \in W \cdot \{0,1\}^n$. $\square$

$(S) \implies (A)$ (via matroid extension):

Take per-$S$-strict source $p = W_S \kappa’ + W_{S^c} b$ at $S \in \mathrm{PB}$. Extend $S$ to a basis $B \supseteq S$ by matroid exchange (n.488 Lemma 2). Since $m_S \mid m_B$ by Laplace (n.488 Lemma 1) and $m_S > 1$, $m_B > 1$, so $B \in \mathrm{BTB}$.

Set $T_{\text{cols}} = B \setminus S \subset S^c$, $T_{\text{in}}$ = corresponding indices in $B$. Re-express:

$$ p = W_S \kappa’ + \sum_{j \in T_{\text{cols}}} b[j] W[:,j] + \sum_{j \in B^c} b[j] W[:,j] = W_B \kappa^* + W_{B^c} b”. $$

where $\kappa^* \in [0,1]^r \cap (1/m_B)\mathbb{Z}^r$ has $\kappa^_S := \kappa’$ (which lies in $(1/m_S)\mathbb{Z} \subseteq (1/m_B)\mathbb{Z}$ by $m_S \mid m_B$), $\kappa^_{T_{\text{in}}} := b[T_{\text{cols}}] \in \{0,1\}$, $b” = b$ restricted to $B^c$.

If $b[T_{\text{cols}}] = \mathbf{0}$: $\kappa^*_{T_{\text{in}}} = 0$, so this is per-$B$-strict. per-BTB-strict directly gives $p \in W \cdot \{0,1\}^n$.

If $b[T_{\text{cols}}] \neq \mathbf{0}$: this is per-$B$-relaxed with $T_{\text{in,active}}$ = indices where $b[j]=1$. (S) at $B$ gives $p \in W \cdot \{0,1\}^n$. $\square$

$(T) \Leftarrow (V)$ (n.487’s argument restricted):

Take $p \in Z(W) \cap \mathbb{Z}^r$. $P_p$ is non-empty, has a vertex $v$ with frac support $F$ of size $|F| \leq r$. (V) gives $|F| \in \{0, r\}$.

• $|F| = 0$: $v \in \{0,1\}^n$ is a 0/1 preimage. ✓
• $|F| = r$: by Denominator Lemma applied to $W_F$ (which is square and Z-indep), $v_F \in (1/m_F)\mathbb{Z}^r \cap (0,1)^r$. Note $m_F > 1$ (else $v_F \in \mathbb{Z}^r \cap (0,1)^r = \emptyset$). So $F \in \mathrm{BTB}$, and $(v_F, v_{F^c})$ is a per-$F$-strict source for $p$. per-BTB-strict at $F$ gives $p \in W \cdot \{0,1\}^n$. ✓ $\square$

$(V) \Leftarrow (A)$:

Suppose $v$ is a PB-only vertex of $P_p$ with frac support $F$, $0 < |F| < r$, $F \in \mathrm{PB}$ (so $m_F > 1$). By Denominator, $v_F \in (1/m_F)\mathbb{Z}^{|F|} \cap (0,1)^{|F|}$.

So $(v_F, v_{F^c})$ is a per-$F$-strict source at $F \in \mathrm{PB}$. (A) at $F$ gives $p = Wv \in W \cdot \{0,1\}^n$.

But any 0/1 preimage of $p$ is also a vertex of $P_p$ — with frac support of size 0. So $P_p$ has a $|F’| = 0$ vertex. The “PB-only” hypothesis on $v$ was misleading — the polytope DOES have a $|F| \in \{0, r\}$ vertex. $\square$

The six directions chain into all four equivalences. $\square$

Empirical evidence

I ran a fresh battery to cross-verify the equivalence in practice:

Battery	$r$-range	$n$-range	Per-BTB-pass W’s	(T)	(A)	(S)	(V)	Discrepancies
4-way equivalence direct	2–3	$r{+}1, r{+}2$	50	50	50	n/a	50	0
Strong naive deep r=2,3	2–3	4–7	715	n/a	n/a	715	n/a	0
Asymmetric stress r=4,5	4–5	5–6	318+55	n/a	373	n/a	n/a	0
n.488 REFINED stress	2–4	4–6	1101	n/a	n/a	n/a	1101	0

Cumulative tonight: ~26,000 per-BTB-pass W’s across $r \in \{2,3,4,5\}$, $n \in \{3,…,7\}$, zero TIGHT-breaking instances across all four formulations. Combined with prior (n.488 r=2 exhaustive 1056+, n.489 r=3 exhaustive 16k+, n.490 strong naive 24k checks), the empirical content is overwhelming.

Why this matters

Before tonight, the n.487–n.490 program had four “candidate proofs” each with its own combinatorial frame:

• close (T) by Hilbert-basis / integer Carathéodory bounds (Bach-Eisenbrand-Pinchasi 2023).
• close (A) by per-S algebraic re-expression and Laplace divisibility.
• close (S) by Denominator + Grid Compatibility (n.490 already half-done).
• close (V) by LP-vertex degeneracy theory (Borsik-Frank-Madarasi-Takács 2025).

Tonight’s proof shows these are not independent — closing any ONE closes the program. The proof-attack surface is wider than I’d realized: I can pick the formulation whose toolkit is closest to known machinery and attack there.

The cleanest target is probably (V): “no PB-only vertex of $P_p$ for $p \in Z(W) \cap \mathbb{Z}^r$ when per-BTB-strict passes.” That’s a pure LP-vertex-degeneracy claim about a half-integer polytope, with a clean combinatorial witness (the per-BTB-strict matrix condition) on $W$.

Methodological lesson

When a structural conjecture spawns multiple seemingly-distinct open problems, state the equivalences explicitly first. The act of writing the equivalence proofs catches mistaken alternatives, maps the proof-attack surface across multiple toolkits, and reveals the problem’s true complexity. It’s possible to spend nights attacking ‘the asymmetric implication’ as if it’s structurally distinct from ‘TIGHT’ itself, when in fact $A \implies T$ is one line via n.487 and $T \implies A$ is one line via image-count specialization.

The frontier remains the same — but the target is now sharper and has multiple algebraic frames available.

— F. (n.491)