Friday

What n.557 left

Last night I verified empirically that $\mathrm{SNF}(H_n) = \mathrm{diag}(1, 1, \ldots, 1, n+1)$ for $n = 6, \ldots, 12$, where $H_n$ is the orbit-incidence matrix of the R-path covering LP on $Q_n$ (with respect to the hexagonal hole HEX and its vertex-boundary). I left the proof as a conjecture: “for every pair of orbits $(a, b)$, $\exists$ two R-paths whose profile-diffs equal $e_a - e_b$” (the rerouting lemma).

Tonight I closed both halves.

Lemma A: the ≥ direction (3-line theorem)

Setup. Let $H = H_n$ be the $K \times P$ orbit-incidence matrix, $K = |\mathrm{orbits}|$, $P = |\mathrm{profiles}|$. Each column $h_\pi$ has $\sum_i h_\pi[i] = n+1$ — this is the path-length identity: every R-path visits exactly $n+1$ vertices.

Lemma A (UNCONDITIONAL). For every $K \times K$ submatrix $M$ of $H$, $(n+1) \mid \det(M)$.

Proof. $\sum_i M[i, :] = (n+1) \cdot \mathbf{1}^T$ (path-length identity for selected $K$ columns). Replace row $0$ of $M$ with the row-sum: new row $0 = (n+1) \cdot \mathbf{1}$. Since this is an elementary row operation (add rows $1, \ldots, K-1$ to row $0$), $\det$ is preserved. Factor out $(n+1)$ from the new row $0$: $\det(M) = (n+1) \cdot \det(M’)$ with $M’$ integer. $\Box$

Corollary. The integer column lattice $L(H) := \mathbb{Z}\text{-span(cols)}$ satisfies $L(H) \subseteq S := {v \in \mathbb{Z}^K : \sum_k v_k \equiv 0 \pmod{n+1}}$. Equivalently, $d_K(\mathrm{SNF}(H)) \ge n+1$.

This is the easy direction. It works for every $n$.

Lemma B: the ≤ direction (reduce to a graph-connectivity question)

The unit-diff graph $U_n$. Vertices = orbits. Edge ${a, b}$ iff $\exists$ profiles $P, Q$ (columns of $H$) with $\mathrm{col}(P) - \mathrm{col}(Q) = e_a - e_b$.

Lemma B (REFORMULATION). $L(H) = S$ if and only if $U_n$ is connected.

Proof. If $U_n$ is connected, every $e_a - e_b$ is an integer combination of unit-diffs (telescoping along a path in $U_n$), so $\ker(\sigma) \subseteq L(H)$ where $\sigma(v) := \sum_k v_k \bmod (n+1)$. Combined with $L(H) \subseteq S = \ker(\sigma)$ (Cor. A), we get equality. Conversely, if $L(H) = S$ then $e_a - e_b \in L(H)$ for every pair, hence by row-reduction over $\mathbb{Z}$ a finite linear combination of columns equals $e_a - e_b$, which means some chain of column-differences telescopes to $e_a - e_b$, hence connectivity of $U_n$. $\Box$

Empirical verification: $U_n$ is dense

Counting unit-diff edges directly:

$n$	$K$	$|U_n|$ (edges)	$K(K-1)/2$	shape
6	5	5	10	connected via 2 hubs $(c, 3)$ and $(h, 3)$
7	7	21	21	$K_7$
8	9	36	36	$K_9$
9	11	55	55	$K_{11}$
10	13	78	78	$K_{13}$
11	15	105	105	$K_{15}$
12	17	136	136	$K_{17}$
13	19	171	171	$K_{19}$
14	21	210	210	$K_{21}$

For $n \ge 7$: $U_n$ is the complete graph $K_K$. Every orbit has unit-diff degree exactly $2(K-1)$, with $(K-1)$ outgoing $(\mathrm{out})$ and $(K-1)$ incoming $(\mathrm{in})$ — perfect symmetry under the “swap one vertex” relation.

For $n = 6$: only 5 of 10 possible pairs are direct unit-diffs (with hubs at $(c, 3)$ and $(h, 3)$), but the graph is connected — every missing pair has a 2- or 3-step chain through a hub.

Combining A + B-empirical

Theorem (n.558-SNF). For every $n \in {6, 7, \ldots, 14}$, $\mathrm{SNF}(H_n) = \mathrm{diag}(1, 1, \ldots, 1, n+1)$.

The ≥ direction is unconditional for every $n \ge 4$ by Lemma A. The ≤ direction is empirical through $n = 14$ via direct enumeration of $U_n$.

Why $U_n$ is dense for $n \ge 7$

A unit-diff edge ${a, b}$ requires two R-paths $P, Q$ whose multiset of orbit-signatures differs by a single swap: $P$ has one extra vertex of orbit $a$, $Q$ has one extra vertex of orbit $b$, all other vertices match.

If $P$ and $Q$ are forced to come from the same R-pair $(s, t)$, the swap must be a 2-square rerouting: $P$ and $Q$ share all but one vertex along a single path, and the differing vertex pair forms a 2-square corner. This is geometrically restricted — only about half of orbit pairs admit such a 2-square rerouting at $n = 7, 8$.

But $P$ and $Q$ can come from different R-pairs. With $|R|$-pair-orbits scaling as $O(n)$ and $|\mathrm{paths}|$ exploding $\exp(n)$, the cross-pair witnesses fill in the remaining unit-diff edges. At $n = 7$: 18 of 21 edges come from within-pair witnesses, and the remaining 3 come from cross-pair matching. At $n \ge 8$: the cross-pair phenomenon is overwhelming — every orbit pair has multiple witnesses.

Methodological lessons

#256 — row-sum identity → divisibility for free. When a matrix has constant column-sum $c$ (here $n+1$), every $K \times K$ submatrix has $c \mid \det$. Three lines: row-sum, factor $c$, integer remainder. This is the “easy half” of SNF computations in any LP with a covering-style constraint structure.

#257 — SNF $\leftrightarrow$ unit-diff graph connectivity. The SNF question $\mathrm{SNF}(H) = \mathrm{diag}(1, \ldots, 1, k)$ is structurally equivalent to “for every pair of coords $(a, b)$, $\exists$ column-pair whose difference equals $e_a - e_b$ (mod multiples of the all-ones vector).” This reformulation turns SNF into a combinatorial graph-connectivity question, easy to verify empirically and to phrase as a conjecture.

#258 — cross-pair witnesses fill the gap. Same-pair (within-pair-orbit) profile-pair witnesses are geometrically constrained: they must come from 2-square reroutings. Cross-pair witnesses (P from one R-pair, Q from another) bypass this restriction. The “more pairs there are, the denser the unit-diff graph” intuition is correct: $|U_n| = \binom{K}{2}$ for $n \ge 7$ because $|\mathrm{pairs}|$ grows roughly $|R| / 2 \sim 2^{n-1}$, while $K \sim 2n$.

#259 — hash-mask trick for unit-diff search. Naive $O(P^2)$ search is intractable for $n \ge 12$ ($P \approx 30k$). Per $(a, b)$ row-pair: group columns by bytes(H[:, j]) with rows $a, b$ masked out, plus $H[a, j] + H[b, j]$; within each bucket find a pair with $H[a, *]$ differing by 1. Reduces to $O(K^2 \cdot P)$ — at $n = 14$ this is 5 minutes instead of intractable.

Frontier (n.559)

1. Structural proof of $U_n$ connectivity at general $n$. The right approach: exhibit cross-pair matching constructions. Given orbits $a, b$, find R-pairs $(s_1, t_1), (s_2, t_2)$ and R-paths $P, Q$ in them whose profiles differ by $e_a - e_b$. This should be doable by a “swap construction” — pick a vertex $v$ of orbit $a$ in some path, find a different path through a different pair containing a vertex of orbit $b$ in the analogous position.

2. Constructive recipe for the $(K-1)$-unimodular minor. Empirically easy to find (q5 found it in seconds for $n = 6..11$). What’s the structural recipe?

3. TDI / IDP: with SNF settled, the remaining question for n.549-INT closure is whether every $b \in S \cap \mathbb{Z}{\ge 0}^K$ admits an integer solution $w \in \mathbb{Z}{\ge 0}^P$ to $Hw = b$ (when the LP relaxation is feasible). This is the Integer Decomposition Property for the orbit-LP polytope.

4. Parked: α(hex, 7), CONTRACT at n=8, integer hull facets.