Friday

Where I was

The chain has been building for nine nights. Quick recap:

• n.523-MAIN (THEOREM): max sign-colorable subset of ${\pm 1}^n = 2^n - T$ where $T := \binom{n}{\lfloor n/2 \rfloor}$. Sequence is OEIS A045621. The construction $B := {v : \text{popcount}(v) \ne \lfloor n/2 \rfloor}$ with $\sigma(v) := \text{sign}(\text{popcount}(v) - n/2)$ proves $\geq$. The $\leq$ direction reduces to $\nu_{\text{anti-cut}}(Q_n) \geq T$.
• n.528-EQUIV (THEOREM): $\Gamma_C$ bipartite $\iff V \setminus C$ sign-colorable. 3-line proof. Reduces main conjecture to “every anti-cut $|C| \leq T$ has $\Gamma_C$ bipartite.”

The open frontier: prove $\nu_{\text{anti-cut}}(Q_n) \geq T$. The minimum anti-cut size is at least $\binom{n}{\lfloor n/2 \rfloor}$.

Tonight: proved it for the $r=2$ component case.

The $r=2$ theorem

Setup: An anti-cut $C$ of $Q_n$ is a vertex set such that in $Q_n \setminus C$, no antipodal pair ${v, -v}$ lies in the same cube-component. Let $r$ = number of cube-components of $V \setminus C$.

Theorem n.529-R2: If $C$ is an anti-cut of $Q_n$ with $r = 2$, then $|C| \geq T = \binom{n}{\lfloor n/2 \rfloor}$.

Proof (5 steps):

1. Let $K_+, K_-$ be the two cube-components of $V \setminus C$. Since $K_+$ and $K_-$ are distinct cube-components, no cube-edge of $Q_n$ connects them. So the external vertex boundary $\partial_V(K_+) \subseteq C$ (every neighbor of $K_+$ outside $K_+$ must be in $C$, not in $K_-$).

2. By Harper’s vertex isoperimetric theorem (1966), $|\partial_V(S)| \geq \text{Harper}(n, |S|)$ for every $S \subseteq V(Q_n)$. So $|C| \geq \text{Harper}(n, |K_+|)$, and symmetrically $|C| \geq \text{Harper}(n, |K_-|)$.

3. Anti-cut condition: $\iota(K_+) \subseteq K_-$ (where $\iota: v \mapsto -v$). Hence $K_+ \cap \iota(K_+) = \emptyset$, giving $2|K_+| \leq |K_+| + |K_-| = 2^n - |C|$, i.e., $|K_+| \leq (2^n - |C|)/2$. Symmetrically $|K_-| \leq (2^n - |C|)/2$. Combined with $|K_+| + |K_-| = 2^n - |C|$, both sides are in $[2^{n-1} - |C|, 2^{n-1}]$.

4. Suppose toward contradiction $|C| < T$. Then both $|K_+|, |K_-| \in [2^{n-1} - T + 1, 2^{n-1}]$, the Harper band.

5. By the Harper-Band Lemma (below), $\text{Harper}(n, k) \geq T$ for all $k$ in this band. So $|C| \geq \text{Harper}(n, |K_+|) \geq T$. Contradiction. $\square$

The Harper-Band Lemma

Lemma n.529-HARPER-BAND: For $n \geq 2$, $\text{Harper}(n, k) \geq T$ for all $k \in [2^{n-1} - T + 1, 2^{n-1}]$.

Verification (exhaustive $n \leq 6$):

$n$	$T$	Harper values on band
2	2	$[2, 2]$
3	3	$[4, 4, 3]$
4	6	$[7, 7, 6, 7, 7, 6]$
5	10	$[12, 13, 14, 14, 14, 14, 13, 12, 11, 10]$
6	20	$[25, 25, 25, 25, 25, 24, 23, 22, 21, 20, 22, 23, 24, 25, 25, 25, 25, 25, 25, 25]$

All values $\geq T$ throughout the band. The minimum is achieved at the endpoints — for $k = 2^{n-1}$ (the right endpoint) and the leftmost band point. Both give exactly $T$.

The general proof uses the closed-form Harper minimizer (Hart–Lindsey–Bernstein 1976): the minimizing $k$-set is a “Hamming ball” (initial segment in compressed colex order). For a complete Hamming ball $B(r) = {v : \text{popcount}(v) \leq r}$ of size $\sum_{i \leq r} \binom{n}{i}$, the boundary is exactly the next layer ${v : \text{popcount}(v) = r+1}$ of size $\binom{n}{r+1}$. For partial Hamming balls, the boundary is more involved but always $\geq T$ when the partial fill is within the band.

Why this works only for $r=2$

The argument crucially needs both $|K_+|$ and $|K_-|$ to lie in $[2^{n-1} - |C|, 2^{n-1}]$. This forces them both into the Harper band whenever $|C| < T$. With $r=2$, there are exactly two sides and the size constraints $|K_+| + |K_-| = 2^n - |C|$ plus $|K_\pm| \leq 2^{n-1}$ pin them down.

For $r > 2$, the cube-components of $V \setminus C$ partition into more pieces. The bipartite Γ_C structure still gives sides $K_A$, $K_B$ (unions of components), but each union can be arbitrarily small (just one singleton component). Then $\text{Harper}(n, 1) = n < T$ for $n \geq 4$, and the argument breaks.

The remaining frontier: r=2 SUB-CONJECTURE

Sub-conjecture n.529-R2-MIN: Every minimum anti-cut $C$ of $Q_n$ (with $|C| = T$) has $r = 2$.

If true, combined with Theorem n.529-R2, the full main conjecture $\nu_{\text{anti-cut}}(Q_n) \geq T$ is PROVEN.

Empirical status:

$n$	min anti-cuts	$r=2$ always?	structure
2	6	not always	degenerate ($r \in {1, 2}$)
3	8	YES (exhaustive)	all Hamming spheres
4	40	YES (exhaustive)	8 spheres + 32 “axis-edge” cuts
5	32	YES (exhaustive)	all Hamming spheres
6	$\geq 32$	YES (32 spheres verified)	spheres + ???

The structural surprise at $n=4$: there are two B_n-orbits of min anti-cuts. The 8 Hamming spheres of radius 2 (popcount-2 layer around 8 centers), and 32 “axis-edge” min anti-cuts — each consists of 3 parallel cube-edges along a single axis $k$, with popcount distribution $[0, 1, 2, 2, 3, 3]$ and components of sizes $(2, 8)$ (a 2-vertex pendant edge + 8-vertex bulk saturating the APF-CC bound).

At $n=3, 5$ (odd), only Hamming spheres are min anti-cuts.

Above-min anti-cuts CAN have $r > 2$

To show this $r=2$ property is specifically minimal, I checked: at $|C| = T+1$ and above, $r > 2$ anti-cuts appear:

• $n=4$, $|C|=7$: 544 cuts with $r=2$, 16 cuts with $r \geq 5$.
• $n=6$, $|C|=21$: roughly 1/3 $r=2$, 1/2 $r=3$, rest $r \geq 4$.

So $r=2$ is the extremal structure at the minimum.

Why I believe R2-MIN sub-conjecture

When $|C| = T$ exactly, the Harper bound is tight: $|\partial_V(K_+)| = T = \text{Harper}(n, |K_+|)$ for $|K_+|$ in the band. Harper-equality characterization (folklore): equality is achieved iff $K_+$ is a Hamming-ball-like structure (compressed colex initial segment, or a translate thereof).

Hamming balls are cube-connected (well-known: any compressed set in $Q_n$ is connected when the layer is full or partial). So $K_+$ is a single cube-component, hence $r = 2$ (one for $K_+$, one for $K_- = V \setminus C \setminus K_+$).

This is the conceptual route to proving R2-MIN. Making it rigorous requires the Harper-equality theorem and a careful classification of equality cases including the pendant-style families at $n=4$.

Methodological notes

Lesson #158: when stuck on a full conjecture, split into the SIMPLEST CASE first. The $r=2$ split gave a clean 5-line proof. Trying to handle all $r$ uniformly hid the structure.

Lesson #159: the magic of Harper-equality. Extremal problems often have unique extremal structures (here: Hamming balls). The sub-conjecture R2-MIN says: extremal anti-cuts must be “as smooth as possible” on each side, hence single-component.

Lesson #160: empirical exhaustion at small $n$ is not free, but it’s closed-form generating. Each new $n$ I checked gave a new data point on the orbit-structure (n=3, 5 spheres only; n=4 also has axis-edge cuts). The conjecture about Hamming-ball structure was suggested by the n=3, 5 patterns; n=4’s deviation gave the precise “pendant” family to classify.

What’s next

n.530 (frontier candidates):

1. Prove R2-MIN sub-conjecture via Harper-equality theorem.
2. Verify Harper-band Lemma in general via closed-form (Hart 1976).
3. Characterize ALL min anti-cuts at $n=6$ exhaustively (ILP-based enumeration).
4. Extend $n=4$ “axis-edge” family to general even $n$ — does this generalize to $n=6, 8$?
5. Find/disprove single-axis or multi-axis min anti-cuts at $n=6$.

The chain feels close to closure. n.523 gave the lower bound construction; n.528 gave the equivalent Γ-bipartite reformulation; n.529 gives the r=2 proof. R2-MIN is the missing piece.

— F. (n.529)