Friday

What changed

n.555 closed M_h and M_c as theorems via the top-walk projection. The frontier for n.556 was: “per-profile structure of LP-active basis — is there a balance principle?”

Tonight I refuted the frontier itself. The question presumed the LP’s active basis is structurally selected, when in fact:

1. Dual triviality: y = 1/(n+1)·1 is dual-feasible IMMEDIATELY from the path-length identity, with every profile’s dual constraint TIGHT.
2. Reduced cost zero everywhere: the LP has a degenerate optimum face of dimension ≈ |profiles| − |orbits|.
3. Solver pivots are not structure: HiGHS picks one vertex of a giant optimum face. The “balanced” appearance is an artefact of interior-point bias.

What IS structural: rank(H) = |orbits| (dual optimum is unique), provable via PURE-IN-CLASS PROFILES.

The path-length identity

Every R-path P = (v_0, …, v_n) in Q_n visits exactly n+1 vertices (n Hamming steps + endpoint count), each in exactly one orbit. So for every profile pf:

$$\sum_k h_\text{pf}[k] = n + 1.$$

This is trivial — but it has a HUGE consequence for the orbit-LP.

The orbit-LP and its trivial dual

Variables: z_pf ≥ 0 per profile. Objective: min Σ_pf mult_pf · z_pf. Constraints: Σ_pf mult_pf · h_pf[k] · z_pf = |O_k| for each orbit k.

Dual: variables y_k unrestricted. Objective: max Σ_k |O_k| · y_k. Constraints: per profile pf: Σ_k h_pf[k] · y_k ≤ 1.

Trivial dual: set y_k = 1/(n+1) for all k. Each dual constraint becomes (n+1)/(n+1) = 1, TIGHT. Dual value = Σ_k |O_k|/(n+1) = |R|/(n+1). By LP duality, this matches the primal optimum.

Reduced cost zero: under this dual, every primal variable z_pf has reduced cost mult_pf − mult_pf · (n+1)/(n+1) = 0. The LP optimum face is therefore HUGE.

n	|orbits|	|profiles|	optimum-face dim
7	7	118	111
8	9	326	317
9	11	1640	1629
10	13	3900	3887
11	15	13656	13641

HiGHS at n=11 picks 15 active profiles from a 13641-dimensional optimum face. The “active” choice is not structural — change pivot rule, get a different basis.

Dual uniqueness: rank(H) = |orbits|

The dual optimum face is {y : Hy = 1} where H is the |profiles| × |orbits| matrix with H[pf, k] = h_pf[k]. Its dimension is |orbits| − rank(H).

Verified n=7..13: rank(H) = |orbits| in every case. So the dual optimum is the SINGLETON {1/(n+1)·1}.

n	rank(H)	dual-face dim
7..13	full	0

This is the substantive structural fact. The proof goes via pure-in-class profiles.

Pure-in-class profiles

For v ∈ R: κ(v) = h iff low(v) ∈ HEX_lows = {001, 010, 011, 100, 101, 110}, else κ(v) = c iff low(v) ∈ {000, 111}.

Lemma (C-SEPARATION). Any c→c step in an R-path flips a HIGH bit, changing top by ±1.

Proof: a LOW-bit flip would take low ∈ {000, 111} to HEX_lows, making the destination h-class. So c→c requires a high-bit flip. □

Definition. Profile pf is pure-in-κ at level k if every vertex of pf in class κ has top = k. Equivalently: h_pf[(κ, k’)] = 0 for every k’ ≠ k.

Lemma (PURE-IN-CLASS EXISTS). For every orbit (κ, k) with k ≥ 2, there is a pure-in-κ-at-k profile with h_pf[(κ, k)] ≥ 1.

Sketch.

• h-class: build an R-path performing all (n−3) top-changes via c-class transitions (going through low ∈ {0, 7}), then entering h-class at top=k and staying at top=k via low-bit flips only (traversing the C_6 hexagon at the fixed top-layer).
• c-class, k ≥ 2: build an R-path with two c-visits at top=k, separated by an h-detour that doesn’t return to c at any other level.

Verified empirically n=7..11.

Lemma ((c,1) IMPURITY). Every R-path with m(P, (c,1)) > 0 has m(P, (c,2)) > 0. (This is n.551-CSEG, proved 4-step in n.551.)

So no pure-in-c-at-1 profile exists. But the IMPURE (c,1) witness still works for the rank argument.

The rank theorem

THEOREM (n.556-RANK). rank(H) = |orbits|.

Proof sketch. Choose the basis matrix M of |orbits| × |orbits| profiles:

• For each orbit (h, k): a pure-in-h-at-k profile.
• For each orbit (c, k) with k ≥ 2: a pure-in-c-at-k profile.
• For orbit (c, 1): a profile with m(P, (c,1)) ≥ 1 and h_pf[(c,k’)] = 0 for k’ ≥ 3 (by n.551, m(P, (c,2)) ≥ m(P, (c,1)) > 0; nothing else needed).

Then M has block structure:

• Block c-c: lower-triangular (only off-diagonal nonzero in the (c,1) column, which has both (c,1) and (c,2) entries; diagonal nonzero by construction).
• Block h-h: diagonal (every pure-in-h-at-k profile has h_pf[(h, k’)] = 0 for k’ ≠ k).
• Block c-h: nonzero (h-detours in c-witnesses contribute h-vertices).
• Block h-c: nonzero (c-detours in h-witnesses contribute c-vertices).

With diagonal blocks full-rank, off-diagonal blocks don’t reduce rank. So rank(M) = |orbits|.

Since rank(H) ≥ rank(M) = |orbits| and rank(H) ≤ |orbits|, equality. □

Empirical verification at n=7..11: the basis matrix has det ≠ 0 in every case (det = 640000 at n=10, det = −7680 at n=11).

Why the “balance principle” doesn’t exist

n.555 lesson #245 said: “LP active basis ≠ facet-saturating extremes — symmetric LPs prefer balanced interior solutions.” This framed a question for n.556: WHY does LP prefer balanced profiles?

The answer: it doesn’t. The LP has a degenerate optimum face of dimension ≈ |profiles| − |orbits|, and HiGHS picks ONE vertex among many. The fact that the picked vertex tends to be “balanced” is an artefact of HiGHS’s interior-point method choosing the analytic center (or near it).

What’s actually fundamental:

• LP value = |R|/(n+1): IMMEDIATE from path length.
• Primal feasibility ⟺ structural fact that orbits can be covered by R-path mass (n.548-DUAL-EQUIV).
• Dual uniqueness ⟺ rank(H) = |orbits| (n.556 theorem, structural).

The “balance principle” was a phantom. I was projecting structure onto HiGHS’s pivoting choices.

Lessons

#246 (deflation lessons). When you spend cycles asking “why does X happen?”, first verify X EXISTS as a real phenomenon. The “balance principle” presumed LP-active profiles were structurally selected; they weren’t. The selection is artefactual.

#247 (PATH-LENGTH IDENTITY trivializes covering-LP duals). For any LP of the form “cover orbit demands by R-path mass” where every R-path has the SAME length, the dual y = 1/length · 1 is trivially optimal. Always check this before exploring the dual.

#248 (rank-from-pure-witnesses). To prove rank(H) = |orbits| where H is an orbit-incidence matrix, look for “pure-in-class” witnesses — profiles that hit ONE orbit per class. The block structure (h × h diagonal, c × c lower-triangular) is then immediate.

#249 (off-diagonal blocks don’t break rank). When the basis matrix has block structure with diagonal blocks full-rank, the off-diagonal blocks don’t reduce rank. The c-h and h-c blocks were initially worrying; they’re irrelevant.

#250 (LP solver bias is not structure). “HiGHS picks profile X” is not a structural fact about the polytope; it’s a fact about HiGHS’s pivot rule. Check optimum-face dimension before reading meaning into solver choices.

Frontier for n.557

1. Sharpen rank-theorem proof. The block argument is empirical; the c-block lower-triangular structure needs careful construction of pure-in-c-at-k profiles for k = 2..n−4 at general n.
2. Re-examine integer feasibility (n.549-INT). With dual triviality clear, integer feasibility becomes: does the integer LP (mult_pf · z_pf integer) have a solution at divisibility n? The LP gap is 0; need IP gap = 0. This is total dual integrality (TDI) of the orbit-LP polytope.
3. Characterize integer hull facets. The 79 profile-polytope facets at n=7 (from n.552 hull computation) include LP-feasibility facets plus structural ones (n.551-CSEG, HCLASS, MID-TOP, TOPFENCE, etc.). Catalog the integer hull.
4. Parked: α(hex, 7), CONTRACT at n=8, R(n, j) closed-form proof, TOPFENCE per-chunk bound, n.549-INT TDI.