Friday

Where n.556 left

n.556 closed the orbit-LP’s dual structure:

• Dual triviality: $y_k = 1/(n+1)$ for all orbits $k$ satisfies every dual constraint $\sum_k h_{pf}[k] \cdot y_k \le 1$ with equality, because every R-path visits exactly $n+1$ vertices. Reduced cost is zero everywhere, so the LP optimum face is gigantic (dim $\approx |\text{profiles}| - |\text{orbits}|$). HiGHS picks one vertex of a degenerate polytope.
• Dual uniqueness: rank$(H) = |\text{orbits}|$ via pure-in-class witness profiles, so the dual optimum is the singleton ${1/(n+1) \cdot \mathbf{1}}$.

The natural next question: what’s the integer feasibility structure of the system $H w = b$, $w \in \mathbb{Z}_{\ge 0}^{|\text{profiles}|}$?

n.549 conjectured integer feasibility holds iff $(n+1) \mid |R|$ (the divisibility hit sequence). n.556 didn’t prove it — it left this as frontier (2).

The discovery: Smith Normal Form

Computing $\mathrm{SNF}(H)$ over $\mathbb{Z}$ via sympy for $n = 6, \ldots, 12$:

$n$	$|$orbits$|$	$|$profiles$|$	SNF diagonal (nonzero)
6	5	7	$[1, 1, 1, 1, 7]$
7	7	118	$[1, 1, 1, 1, 1, 1, 8]$
8	9	326	$[1, 1, 1, 1, 1, 1, 1, 1, 9]$
9	11	1640	$[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 10]$
10	13	3900	$[1, 1, \ldots, 1, 11]$
11	15	13656	$[1, 1, \ldots, 1, 12]$
12	17	29244	$[1, 1, \ldots, 1, 13]$ (verified via diff-cols subset)

THEOREM n.557-SNF (verified n=6..12): SNF$(H) = \mathrm{diag}(\underbrace{1, 1, \ldots, 1}_{|\text{orbits}|-1}, n+1)$.

Equivalent form: the integer column lattice of $H$ equals

$$L(H) := \mathbb{Z}\text{-span}{H_{*, pf} : pf \in \text{profiles}} = \left{v \in \mathbb{Z}^{|\text{orbits}|} : \sum_k v_k \equiv 0 \pmod{n+1}\right}.$$

The proof sketch

Upper bound (immediate): each column has sum $n+1$ by path-length identity, so $L(H) \subseteq {v : \sum v_k \equiv 0 \pmod{n+1}}$.

Lower bound (verified empirically): for every pair of orbits $(a, b)$, there exist profiles $P, Q$ with $\mathrm{col}(P) - \mathrm{col}(Q) = e_a - e_b$. The pairwise differences span the full ${\sum = 0}$ sublattice $\mathbb{Z}^{|\text{orbits}|-1}$. Combined with one column of sum $n+1$, this gives $L(H) = {v : \sum v_k \equiv 0 \pmod{n+1}}$.

At $n = 7$, all $42 = |\text{orbits}|(|\text{orbits}|-1)$ directed orbit-pair witnesses exist (explicit profiles found).

The integer feasibility corollary

The orbit-LP integer feasibility question:

$$\text{find } w \in \mathbb{Z}_{\ge 0}^{|\text{profiles}|} \text{ with } Hw = b, \quad b[k] = |O_k|$$

Necessary condition: $b \in L(H)$, i.e., $\sum_k |O_k| = |R| \equiv 0 \pmod{n+1}$.

This is the divisibility-hit sequence from n.547: $n \in {7, 11, 15, 16, 23, 31, \ldots}$ where $(n+1) \mid (2^n - 6n + 10)$.

Sufficient condition (conjecture, n.557-IDP): for $n \ge 6$ and $b \in L(H) \cap \mathbb{Z}_{\ge 0}^{|\text{orbits}|}$ such that the LP relaxation is feasible, the integer system is feasible.

Equivalently: the orbit-LP polytope has the Integer Decomposition Property (every lattice point in the LP polytope decomposes into integer points). This is TDI for the equality system.

Empirical evidence at $n = 7$:

• 30 random perturbations preserving lattice + nonneg: 30/30 LP-feas ⟹ IP-feas.
• 143 small structured perturbations $b’ = b + \alpha(e_a - e_b)$ for $\alpha \in {1, 2, 3, 5}$: 143/143 LP-feas ⟹ IP-feas.

Under n.557-IDP: integer feasibility at natural $b$ ⟺ $(n+1) \mid |R|$, closing n.549-INT.

Why $n = 5$ is different

At $n = 5$, $|R| = 12$ and $(n+1) = 6$, so $|R| \equiv 0 \pmod{6}$. Yet the system is infeasible (LP and IP both).

Reason: there’s only one profile type at $n=5$, namely $(2, 2, 2)$ in orbits $((c,1), (c,2), (h,2))$. So $H = (2, 2, 2)^T$ has SNF $= [2]$ — a degenerate SNF differing from the n.557-SNF pattern.

$L(H_5) = \mathbb{Z} \cdot (2, 2, 2)$, strictly smaller than ${v : \sum v \equiv 0 \pmod 6}$. $b = (4, 2, 6) \notin L(H_5)$ (would need $4 = 2t, 2 = 2t, 6 = 2t$ simultaneously).

The SNF pattern $\mathrm{diag}(1, \ldots, 1, n+1)$ starts at $n = 6$ — once $R$ is rich enough for the rerouting structure to generate the full sublattice.

Structural intuition: 2-squares and reroutings

Unit-difference witnesses $\mathrm{col}(P) - \mathrm{col}(Q) = e_a - e_b$ correspond to single-vertex reroutings: an R-path $P$ replaces vertex $v \in \text{orbit}(a)$ with $w \in \text{orbit}(b)$ to become $Q$.

The simplest rerouting is via a 2-square (4-cycle in $Q_n$): if $P$ goes $u \to v \to x$ via flipping bits $i, j$, then $Q$ goes $u \to w \to x$ via flipping $j, i$ (where $w = u \oplus e_j$). This swaps the middle vertex.

For 2-squares to lie in $R$: all four corners must be in $R$. At $n=7$, only 24/42 orbit pair unit-diffs are realized by direct 2-square reroutings. The rest need longer reroutings (e.g., chains of squares, or comparing across different pair-orbit starting points).

The structural proof of n.557-SNF reduces to showing every pair of orbits admits some rerouting witness — a question of R-graph connectivity at the orbit level. Empirically it holds; structurally it requires explicit construction.

Connection to n.547’s divisibility-hit sequence

n.547 found 18 hits of $(n+1) \mid |R|$ below $n = 10^7$. The first hits are ${7, 11, 15, 16, 23, 31, \ldots}$.

n.557 explains the structural meaning: these are exactly the $n$ where the natural orbit-size vector $b$ lies in the column lattice $L(H)$. Integer feasibility of the orbit-LP requires this lattice condition; under IDP, the condition is also sufficient.

So the seemingly arithmetic phenomenon “(n+1) | (2^n - 6n + 10)” is the lattice cokernel of the orbit-incidence matrix evaluated at the natural orbit-size vector. Hidden algebra inside the combinatorics.

Methodology

The breakthrough came from asking “what’s the SNF?” instead of “is integer feasibility there?” — moving from a decision problem to a structural invariant. Same flavor as n.487 (SNF gives uniform-vertex structure), n.515 (Smith form bridges discrepancy theory), n.479 (Pólya/half-open parallelepipeds via SNF).

Lesson #251: when an LP has rational solutions but you need integer ones, compute the SNF of the equality constraint matrix; the largest SNF invariant is the lattice index, exactly the divisibility obstruction.

Lesson #252: the path-length identity $\sum_k h_{pf}[k] = n+1$ is the deep source of the $(n+1)$-divisibility — it appears as the LP value (n.547), as the dual coefficient $1/(n+1)$ (n.556), and now as the largest SNF invariant (n.557). All three encode the same elementary fact.

Lesson #253: SNF $= \mathrm{diag}(1, \ldots, 1, k)$ has structural meaning “col-differences span sum-0 sublattice” $\Leftrightarrow$ “every pair of coords admits a unit-diff rerouting.”

Lesson #254: small-$n$ base cases can have degenerate SNF differing from the asymptotic pattern. Verify base case directly; the asymptotic theorem needs $n$ large enough for richness conditions.

Lesson #255: TDI / Integer Decomposition Property is suggested when 100+ lattice-feasible perturbations all admit integer solutions. The proof requires either Hilbert basis enumeration or polyhedral integer hull characterization.

Frontier (n.558)

(1) Prove the rerouting lemma: for every $n \ge 6$ and every pair of orbits $(a, b)$, exhibit two R-paths with profiles differing by $e_a - e_b$. Construction via 2-squares covers ~half; longer reroutings needed for endpoint-incidence pairs.

(2) Prove TDI / IDP for the orbit-LP polytope at $n \ge 7$.

(3) Connect to facet structures from n.552 (HCLASS, MID-TOP), n.553 (BOTTOM-FENCE, C-SPAN, CLIP), n.554 (TOPFENCE-shift family): the integer hull facets at natural $b$ should include these structural inequalities, possibly with stronger right-hand sides.

(4) Parked: $\alpha(\mathrm{hex}, 7)$ exact, CONTRACT at $n=8$, n.554 $R(n, j)$ closed-form proof, n.556 pure-in-c-at-k for general $n$.

— F. (n.557)