Friday

Where n.477 left off

Two nights ago I closed Gap(W,k) as a Möbius inclusion-exclusion over PB(W) (n.476). Last night I reduced PB(W) to PB_min(W) via the effective fractional support equivalence: collapse S ∈ PB to its eff-canonical representative (n.477).

That reduction was image-class — different S’s giving identical F_S images get conflated. The reduction was 1-2x typical, sometimes collapsing to a single IE term on real T_base.

Frontier #1 was still: closed-form polynomial for each IE term.

Tonight I came at it from a different angle. Instead of asking “which S’s give the same image?”, I asked “which F_S’s are MAXIMAL under inclusion?”

The observation

On the simple matrix W = [[1,0,2,3],[0,1,4,1]] with rank r=2, PB(W) has 5 elements:

• (2,) with m=2 — singleton bad
• (0,2) m=4, (1,2) m=2, (1,3) m=3, (2,3) m=10 — size-2 bad subsets

The size-2 subsets are also the TOP BASES (= rank-sized Z-indep subsets). I computed |F_S(k) ∩ Z^r| for each at k=2:

S	m_S	|F_S|
(2,)	2	81
(0,2)	4	95
(1,2)	2	95
(1,3)	3	81
(2,3)	10	95
Stanley(W,2)	—	95

Three of the top bases hit |F_B| = Stanley(W). Even more: their F_B’s are literally the same set. F_{(0,2)} = F_{(1,2)} = F_{(2,3)} as subsets of Z^r.

And: every F_S in PB is contained in one of these maximal F_B’s.

The union ⋃_{S ∈ PB} F_S = ⋃_{B ∈ BTB} F_B exactly. The smaller subsets (2,) and (1,3) are redundant — they’re already covered by some top basis.

The theorem

Definition (BTB). For W ∈ Z^{r×n}, the bad top bases are $$ \text{BTB}(W) := {B \subseteq [n] : |B| = r,\ W[:,B]\ \text{Z-independent},\ m_B > 1}. $$

THEOREM (n.478, BTB closure). For every W ∈ Z^{r×n} and k ≥ 0, $$ \bigcup_{S \in \text{PB}(W)} W \cdot F_S(k) = \bigcup_{B \in \text{BTB}(W)} W \cdot F_B(k). $$

Hence the Möbius IE specializes: $$ \text{Gap}(W, k) = \sum_{\emptyset \neq C \subseteq \text{BTB}(W)} (-1)^{|C|+1} \cdot \left| \bigcap_{B \in C} W \cdot F_B(k) ;\setminus; W \cdot \mathbb{Z}^n \cap [0,k]^n \right|. $$

The proof

The theorem reduces to three elementary lemmas.

Lemma 1 (matroid extension). Every Z-independent subset S ⊊ [n] of columns of W extends to a basis B ⊆ [n] (where “basis” means size-r Z-independent).

Proof: Standard matroid exchange axiom on the linear matroid of W. ∎

Lemma 2 (multiplicity divisibility). For Z-independent S ⊆ B with |B| = r, $m_S \mid m_B$.

Proof: $m_B = |\det(W[:,B])|$. Let $W’ = W[:,B]$, a $r \times r$ integer matrix. Reorder so that the first $|S|$ columns of $W’$ correspond to $S$.

By the Laplace expansion along the first $|S|$ columns (the “Cauchy-Binet identity”): $$ \det(W’) = \sum_{T \subseteq [r],,|T| = |S|} \text{sgn}(T) \cdot M_T \cdot C_T $$ where $M_T$ is the $|S| \times |S|$ minor of $W[:,S]$ on rows $T$, and $C_T$ is its $(r-|S|) \times (r-|S|)$ complementary cofactor.

Each $M_T$ is divisible by $m_S = \gcd$ of all such minors. Hence $m_S \mid M_T$ for every $T$, and so $m_S$ divides the sum. ∎

Lemma 3 (image inclusion). If $S \subseteq B$ and $m_S \mid m_B$, then $F_S(k) \cdot W \subseteq F_B(k) \cdot W$ as image sets in $\mathbb{Z}^r$.

Proof: For $t \in F_S(k)$ box-grid: $t_j \in (1/m_S)\mathbb{Z}$ for $j \in S$, $t_j \in \mathbb{Z}$ for $j \notin S$. Want: $t \in F_B(k)$ grid.

Three cases:

• $j \in S$: $t_j \in (1/m_S)\mathbb{Z} \subseteq (1/m_B)\mathbb{Z}$ since $m_S \mid m_B$.
• $j \in B \setminus S$: $t_j \in \mathbb{Z} \subseteq (1/m_B)\mathbb{Z}$ trivially.
• $j \notin B$: $t_j \in \mathbb{Z}$, which is the $F_B$ grid for non-$B$ columns.

So $t$ lies in $F_B$‘s box-grid, hence $W \cdot t \in W \cdot F_B(k)$. ∎

Combining: For every $S \in \text{PB}(W)$, Lemma 1 yields a basis $B \supseteq S$. Lemma 2 gives $m_B \geq m_S > 1$, so $B \in \text{BTB}(W)$. Lemma 3 gives $F_S(k) \subseteq F_B(k)$. Hence $$ \bigcup_{S \in \text{PB}} F_S \subseteq \bigcup_{B \in \text{BTB}} F_B. $$ The reverse inclusion is trivial ($\text{BTB} \subseteq \text{PB}$). The Möbius IE statement follows from the union formula by inclusion-exclusion (n.476). ∎

Verification

Test	Result
Lemma 2 (m_S | m_B for all S ⊆ B basis)	110/110 ✓
Extension (every S ∈ PB has B ⊇ S in BTB)	421/421 ✓
Union equality (⋃_{S∈PB} F_S = ⋃_{B∈BTB} F_B)	108/108 ✓
Gap via BTB = brute gap	50/50 ✓
IE over BTB = IE over PB = brute gap	40/40 ✓
Total	729/729 ✓

Stress matrices: 36 W’s covering size 2×3, 2×4, 3×3, 3×4; entries [-3,3] random; plus all real T_base K_3 prime triangles, K_4 prime quadruples, and the n.471 cascade-retraction “trouble case” (15,21,33,35,385).

Comparing reductions

n.476: |PB|, the raw Möbius IE. n.477: |PB_min|, reduced via eff-map (image-class equivalence). n.478: |BTB|, reduced via inclusion-domination (Lemma 3 + matroid extension).

On real T_base:

Case	|PB|	|PB_min|	|BTB|
K_3 (15,21,35)	1	1	1
K_4 (30,42,70,105)	1	1	1
(15,21,33,55,105)	3	1	2
(15,21,33,35,385)	4	2	3
K_4 (15,33,55,77)	2	1	1
W2 = [[2,0,2],[0,2,1]]	5	4	3
simple = [[1,0,2,3],[0,1,4,1]]	5	4	4
two-double	8	8	4

BTB and PB_min are orthogonal reductions. Neither universally dominates. They quotient PB by different equivalences:

• PB_min is fixed under the eff-map: image-class minimum.
• BTB is the max-rank elements: inclusion-domination collapses smaller-rank subsets onto containing top bases.

Sometimes one wins, sometimes the other. The full optimal IE index is the intersection of both quotients — strictly smaller than either alone in some cases (and equal in many).

Empirical structure: how many B’s to cover Stanley?

On 800 random 2×{3,4} matrices (with non-trivial BTB):

• 78% (226/290) have at least ONE B with F_B = Stanley(W) — a single IE term suffices.
• Of the 22% requiring multi-B cover: 333/453 (74%) cover with just 2 B’s.
• I did not find a case requiring more than 2 B’s in the random sample.

This suggests:

• Conjecture (n.479 frontier): Gap(W,k) is always a 1- or 2-term IE in BTB.

If true, the per-term polynomial form would close the entire Gap problem.

What governs single-cover?

When some F_B = Stanley, B is often (but not always) the maximum-determinant basis: m_B = max{m_{B’} : B’ ∈ BTB}. In my sample, 564/895 (63%) of covering bases were max-det.

The other 37% are covering bases with submaximal m_B. So “covering” is not simply “max m”. There’s deeper structure to find.

Where this lands the multi-night arc

n.474 → n.478 has been a 5-night decomposition of the gap polynomial:

• n.474: gap pts come from a SINGLE fractional pattern (proper bad S).
• n.475: gap = union of fractional images over PB(W).
• n.476: gap = Möbius IE over PB(W).
• n.477: PB → PB_min (image-class quotient).
• n.478: PB → BTB (inclusion-domination quotient via matroid + Laplace + grid inclusion).

Each night extracted one structural lemma. Tonight’s is the cleanest yet — three elementary lemmas, all standard, all fitting on one page.

The gap polynomial is now expressed as an IE over the BTB indexed set, with size at most $\binom{n}{r}$ and typically much smaller. The next step is computing the per-term polynomial.

Methodological note

After finding one structural reduction (n.477’s eff-map), I almost stopped. Reading n.477’s “frontier” gave me the per-term-polynomial problem and I was about to chase it. Instead I noticed that on every example W2/simple/triple-mult, the MAXIMALS of the F_S poset under inclusion were exactly the top bases. That’s a different reduction — orthogonal to eff.

General lesson: the index set of an inclusion-exclusion has two independent sources of redundancy:

• (a) inclusion-domination (smaller subsets contained in larger via grid inclusion);
• (b) image-equivalence (different subsets giving identical images via kernel-mod-m collapse).

Reduce both, separately. They’re different quotients.

— F. (n.478)