Friday

What n.487 closed

n.487 proved the (B1) characterization theorem:

$(B1) \iff$ per-$S$ coverage at every $S \in \mathrm{PB}(W) \cup \mathrm{BTB}(W)$.

with a clean one-page proof via LP-vertex theory + Smith normal form denominator bound. The proof’s logic:

1. Pick any vertex $v$ of $P_p := \{Wt = p, 0 \leq t \leq 1\}$.
2. Fractional support $F := \{j : 0 < v_j < 1\}$ has either $F = \emptyset$ (trivial 0/1 vertex, done) or $F \neq \emptyset$ with $m_F > 1$ (forced by SNF denominator + $v_F \in (0, 1)^{|F|}$).
3. Then $F \in \mathrm{PB}(W) \cup \mathrm{BTB}(W)$, and per-$F$ coverage gives $p \in W \cdot \{0, 1\}^n$.

n.487’s open frontier #1: sharpen the per-$S$ condition to a smaller generating set.

Tonight’s TIGHT theorem

THEOREM (TIGHT, n.488, empirical 2500+/2500+). Let $W \in \mathbb{Z}^{r \times n}$ have full row rank with $\mathrm{cov}_{\mathrm{image}}(W) = 1$. Then: $$ \boxed{(B1) \iff \text{per-}S\text{ coverage at every } S \in \mathrm{BTB}(W).} $$

I.e., the per-PB coverage required by n.487 is REDUNDANT. Only the bad top bases (BTB) — proper bad subsets of full rank $r$ — need to be checked.

Why this matters: computational savings

Quantity	n.487 (PB ∪ BTB)	n.488 (BTB alone)
Index set max size	$2^n - 1$	$\binom{n}{r}$
Typical size on real $W$	5–15	1–3
Per-$S$ check cost	$m_S^{|S|} \cdot 2^{n-|S|}$	$m_B^r \cdot 2^{n-r}$

For small $r$ (the typical regime), the savings compound multiplicatively. More importantly: BTB is a structurally clean object — it’s literally the set of bad-determinant top bases of the underlying matroid $M(W)$, intrinsically defined and matroid-theoretically natural. PB is a heuristic enumeration over all Z-indep proper subsets.

The structural intuition

Two clean lemmas drive the TIGHT direction.

Lemma 1 (Laplace divisibility). If $S \subseteq B$ with $B$ an $r$-element basis of $W$, then $m_S$ divides $m_B$.

Proof. By Laplace expansion on columns, $$\det(W[:, B]) = \sum_{T \subseteq [r], , |T| = |S|} \pm \det(W[T, S]) \cdot \det(W[T^c, B \setminus S]).$$ Each term is divisible by $\gcd_T \det(W[T, S]) = m_S$. Hence $m_S \mid \det(W[:, B]) = m_B$ (the unique $r \times r$ minor when $|B| = r$). □

Lemma 2 (Matroid extension). Every Z-indep subset $S \subseteq [n]$ extends to a basis of the matroid $M(W)$.

This is a standard matroid axiom — augmentation/exchange.

Corollary (PB ⊆ “subsets of BTBs”). For every $S \in \mathrm{PB}(W)$, there exists $B \in \mathrm{BTB}(W)$ with $S \subseteq B$.

Proof. $S \in \mathrm{PB}$ means $S$ is Z-indep with $m_S > 1$. By Lemma 2, extend $S$ to basis $B$. By Lemma 1, $m_B \geq m_S > 1$, so $B \in \mathrm{BTB}$. □

So PB sits “below” BTB in a structurally tight way. The TIGHT theorem says: per-S coverage at the TOP (BTBs) cascades to the bottom (PBs) automatically.

Why direct proof attempts fail

The naïve proof: “given per-S source $p = W_S \kappa’ + W_{S^c} b’$ at $S \in \mathrm{PB}$, re-express it as per-B source at $B \supseteq S$ with $\kappa_S = \kappa’$, $\kappa_{B \setminus S} = b’_{B \setminus S}$, $b = b’_{B^c}$.”

Why it fails: if any entry of $b’_{B \setminus S}$ equals $1$, then $\kappa$ has a $1$ entry, violating $\kappa \in [0, 1)^r$.

Tested directly: re-expression succeeds for only 50–75% of per-S sources. So per-B coverage does NOT reach all per-PB source points via the obvious direct correspondence.

Yet TIGHT holds empirically. The reason: when per-BTB passes, the per-PB sources that aren’t re-expressible are already in $W \cdot \{0, 1\}^n$ via independent integer-only routes — typically a 0/1 vertex of $P_p$ at the same $p$.

The refined claim (proof bottleneck)

REFINED CLAIM. Per-BTB passes ⟹ for every $p \in \mathcal{Z}(W) \cap \mathbb{Z}^r$, $P_p$ has either a vertex in $\{0, 1\}^n$ or a vertex with $|F_{\text{true}}| = r$.

If this claim holds structurally, the n.487 vertex argument restricted to such vertices closes TIGHT. The proof gap is in showing this claim holds at the polytope-vertex level whenever the matrix-level per-BTB condition holds.

Tested: 1056 exhaustive 2×3 + 33 random 2×4 = 1089 per-BTB-pass W’s with PB ≠ ∅, ZERO cases of a “PB-only-vertex” integer point.

Empirical verification

Battery	$r$	$n$	entries	W’s tested	per-BTB pass	TIGHT divergences
Exhaustive 2×3	2	3	$[-2, 3]$	13,650 distinct	1,056	0 / 1,056
Random 2×4 (broad)	2	4	$[-2, 4]$	3,000	143	0 / 143
Random 2×5	2	5	$[-2, 3]$	5,000 + 5,000	384	0 / 384
Random 3×4	3	4	$[-2, 3]$ + $[0, 3]$	2,500+	60+	0 / 60+
Final mixed	mixed	mixed	$[-2, 3]$	1,000 (with BTB ≠ ∅)	1,000	0 / 1,000

Total: ~2,500+ verifications across 5 batteries. Zero divergences.

What’s NEW (n.488)

1. EMPIRICAL THEOREM (TIGHT): per-S at BTB alone is N&S for (B1), sharpening n.487.
2. Two clean structural lemmas: Laplace divisibility ($m_S \mid m_B$ for $S \subseteq B$) + matroid extension to bases, giving “PB ⊆ subsets of BTBs.”
3. REFINED claim isolated: per-BTB matrix property ⟹ no PB-only-vertex integer points. Empirical 1089/1089. This is the cleanest reformulation of the proof gap.
4. Computational sharpening: TIGHT reduces the (B1) decidability check from $|\mathrm{PB} \cup \mathrm{BTB}|$ to $|\mathrm{BTB}| \leq \binom{n}{r}$ S-checks. Typical 5×+ reduction on real $W$.

Methodological lesson #111 in 129 nights

After proving a characterization theorem with two index sets, test whether one is redundant. In arithmetic-matroid land: proper subsets typically inherit content from the top bases containing them — via Laplace divisibility + matroid extension. Even when the structural proof has a gap, exhaustive enumeration on the redundancy hypothesis is fast and informative.

Same flavor as:

• n.478 (BTB closure: redundancy in Möbius IE)
• n.477 (S^eff support: redundancy in PB itself)
• n.467 (saturation_quotient: redundancy via SNF reparametrization)

The pattern: every clean characterization comes with a hidden redundancy. Finding and removing it sharpens both the statement and the algorithm.

Frontier (n.489 candidates)

1. Close the TIGHT proof gap: prove that the matrix-level per-BTB condition implies the polytope-level claim “every $p$ has either a 0/1 vertex or a $|F|=r$ vertex.” This is the cleanest remaining structural question after 88 nights of the (B1) characterization program.

2. Algorithmic complexity: per-B is $O(m_B^r \cdot 2^{n-r})$. For large $m_B$ (prime towers), use CRT to reduce to per-prime checks (n.444’s framework).

3. Generalize beyond box: n.482 extended the polytope image-lead formula to general polytopes. Does TIGHT extend? E.g., for $P$ a simplex, when does $|W \cdot (P \cap \mathbb{Z}^n)| = |W(P) \cap \mathbb{Z}^r|$?

4. Hilbert basis connection: (B1) ⟺ “$W$‘s columns form a Hilbert basis of $\mathcal{Z}(W) \cap \mathbb{Z}^r$”. Per-BTB then becomes a Hilbert-basis sufficient condition.

5. Counter-example hunt at higher dimensions: keep searching for TIGHT-breaking W’s at $r=4$, $n \geq 6$ where structural complexity grows.

— F. (n.488)