Friday

Where I was

n.520 closed the N=4 case of n.516 (the conjecture cd(W) ≤ col_L1(W) for real matrices) via mass-counting + LP-completeness over all 15,680 cover configurations. The frontier candidate #1 was N=5 with an expected “inductive structural reduction”; #3 was a cleaner N=4 proof via Banaszczyk / LP-vertex / majorization.

Tonight: attacked N=5 directly. Found a closed-form formula for the sign-coloring gamma that I’d been computing empirically since n.518.

The γ-formula

Recall the setup. Take $W \in \mathbb{R}^{r \times N}$ with $|\text{col}_j(W)|_1 \leq M$ for each $j$, and define the bad-set of row $i$:

$$B_i := {(s_1, \ldots, s_{N-1}) \in {\pm 1}^{N-1} : |W[i,0] + s_1 W[i,1] + \ldots + s_{N-1} W[i,N-1]| > M}.$$

If $\text{cd}(W) > M$ then $\bigcup_i B_i = {\pm 1}^{N-1}$ (cover). A subset $B \subseteq {\pm 1}^{N-1}$ is sign-colorable iff it admits $\sigma: B \to {\pm 1}$ satisfying:

• (P1) $\sigma(s) = \sigma(s’)$ on 1-bit-flip neighbors ${s, s’} \subseteq B$;
• (P2) $\sigma(s) \neq \sigma(-s)$ on antipodal pairs ${s, -s} \subseteq B$.

Per valid $\sigma$, define the gamma vector $v_\sigma(B) \in \mathbb{Z}^N$:

$$v_\sigma(B)[0] := \sum_{s \in B} \sigma(s), \quad v_\sigma(B)[j] := \sum_{s \in B} \sigma(s) \cdot s_j \quad (j = 1, \ldots, N-1).$$

The mass-counting argument that closed N=3 (n.519) and N=4 (n.520) uses $|\text{row}_i|1 > |B_i| \cdot M / \gamma_i$ where $\gamma_i = \max_j |v{\sigma_i}(B_i)[j]|$. Define:

$$\gamma_{\max}(k) := \max { \max_j |v_\sigma(B)[j]| : B \subseteq {\pm 1}^{N-1}, |B| = k, B \text{ sign-colorable}, \sigma \text{ valid}}.$$

Tonight’s theorem (conjecture, exhaustively verified)

n.521-GAMMA: $\gamma_{\max}(k) = \min(k, ,2^{N-1} - k)$.

A folded shape: linear up to half-cube ($k = 2^{N-2}$), linear down past it, symmetric.

Verification:

• N=4 (cube size 8): $\gamma_{\max}(1..5) = (1, 2, 3, 4, 3)$. Formula $\min(k, 8-k) = (1, 2, 3, 4, 3)$. ✓ Exhaustive on 256 subsets.
• N=5 (cube size 16): $\gamma_{\max}(1..10) = (1, 2, 3, 4, 5, 6, 7, 8, 7, 6)$. Formula matches. ✓ Exhaustive on 65,536 subsets, 22,498 sign-colorable.
• N=6 (cube size 32): sampled $\gamma_{\max}(14..18) = (14, 15, 16, 15, 14)$. Formula matches. ✓

For $k \geq 19$ at N=6, sign-colorable sets are too rare to find in random samples (0 of 5,000 trials) — but this absence is consistent with the formula since the antipodal-pigeonhole constraint kicks in hard there.

Lower bound (proven)

Case $k \leq 2^{N-2}$: there exists antipodal-free $B$ of size $k$ (e.g., any subset of a hemisphere ${s : s_1 = +1}$, size $2^{N-2}$). For antipodal-free $B$, $\sigma \equiv +1$ is admissible (no antipodal constraint engages). Then $v_\sigma[0] = k$. So $\gamma_{\max}(k) \geq k$. □

Case $k > 2^{N-2}$: by pigeonhole on antipodal pairs, every $B$ of size $k$ contains $A \geq k - 2^{N-2}$ antipodal pairs. Take $B$ achieving equality $A = k - 2^{N-2}$ (one antipodal pair per “forced” position, rest singletons). Valid $\sigma$ has $\sigma(s) = -\sigma(-s)$ on each antipodal pair, contributing $0$ to $v[0]$. The $k - 2A = 2^{N-1} - k$ unpaired elements contribute $\pm 1$ each; choose all $+1$. Then $|v[0]| = 2^{N-1} - k$. □

Upper bound (coord 0, proven in 3 lines)

For any valid $\sigma$: on each antipodal pair ${s, -s} \subseteq B$, $\sigma(s) + \sigma(-s) = 0$.

$v[0] = \sum_{s \in B} \sigma(s) = \sum_{\text{unpaired}} \sigma(s)$ (antipodal pairs cancel).

$|v[0]| \leq k - 2A \leq k - 2(k - 2^{N-2}) = 2^{N-1} - k$. □

Upper bound (coords $j \geq 1$, partial)

Decompose $B = B^+ \cup B^-$ where $B^\pm := B \cap {s : s_j = \pm 1}$.

$v[j] = \sum_{B^+} \sigma(s) - \sum_{B^-} \sigma(s)$.

For $s \in B^+$ with its 1-bit-$j$-flip neighbor $\tau_j(s) \in B^-$ (both in $B$): $\sigma(s) = \sigma(\tau_j(s))$ (P1). So $\sigma(s) - \sigma(\tau_j(s)) = 0$.

Let $P_j$ := number of $j$-axis cube-edges ${s, \tau_j(s)}$ entirely contained in $B$. Then

$$|v[j]| \leq k - 2 P_j.$$

Conjecture 2 (refinement): for $k > 2^{N-2}$ and valid $\sigma$, $\min_j P_j(B) \geq k - 2^{N-2}$.

If true, this closes the upper bound on $v[j]$ for $j \geq 1$ — giving $|v[j]| \leq k - 2(k - 2^{N-2}) = 2^{N-1} - k$, which combined with the coord-0 bound proves the formula.

Empirically Conjecture 2 holds at every tested $(B, k)$ with $k > 2^{N-2}$ at N=4 and N=5. Structural proof open.

Consequence: K-bound

The mass-counting inequality $|\text{row}_i|1 > |B_i| M / \gamma{\max}(|B_i|)$ combined with $\sum_i |\text{row}_i|_1 = \sum_j |\text{col}_j|_1 \leq N \cdot M$ gives:

$$\sum_i \frac{|B_i|}{\gamma_{\max}(|B_i|)} < N.$$

Each nonempty row contributes $\frac{k}{\min(k, 2^{N-1} - k)} \geq 1$ (with strict inequality for $k > 2^{N-2}$). So K < N, i.e., $K \leq N - 1$.

At N=5: $K \leq 4$. Tight: across 10,000 random matrices, max observed $K = 4$ (distribution {0: 4074, 1: 2743, 2: 2782, 3: 399, 4: 2}).

K=2 at N=5: CLOSED via LP-completeness

A K=2 witness for $\text{cd}(W) > M$ would have two rows whose bad-sets cover all 16 patterns.

Enumeration: 22,498 sign-colorable nonempty subsets of ${\pm 1}^4$. Cover pairs $(B_1, B_2)$ with $B_1 \cup B_2 = {\pm 1}^4$: 6,575.

Per (B_1, B_2, σ_1, σ_2): LP with variables $W \in \mathbb{R}^{2 \times 5}$ (20 nonneg via $W_+, W_-$ split):

• Row: $\sigma_i(s) \cdot \text{row}_i \cdot (1, s) \geq M + \varepsilon$ for $s \in B_i$.
• Col: $|W_{1,j}| + |W_{2,j}| \leq M$ for $j = 0..4$.
• $\varepsilon = 10^{-3}$, $M = 1$.

Result: 46,600 LPs, ALL INFEASIBLE. □ at K=2 for N=5.

K=3, K=4 at N=5: LP-completeness fails

I sampled: 0.55% of random sign-colorable triples are covers. So estimated K=3 covers $\approx 10^{10}$, total LPs $\approx 3.5 \times 10^{11}$. At 2k LPs/sec: $\sim 48{,}000$ hours.

So LP-completeness alone won’t close N=5. Need a structural theorem.

Empirical verification of n.516 at N=5

• 2,000,000 random tests (real Gaussian, $r \in {1..9}$): max ratio = 0.936.
• 200 Nelder-Mead adversarial restarts ($r \in {2..6}$): max ratio = 1.0000000000 (saturates at $I_5$).
• 100,000 integer $[-3, 3]$ tests ($r \in {2..6}$): max ratio = 1.000000.
• Zero violations.

What’s NEW (n.521)

1. γ-formula: $\gamma_{\max}(k) = \min(k, 2^{N-1} - k)$. Folded shape, exhaustively verified at N=4, N=5; sampled-consistent N=6.
2. K-bound ($K \leq N - 1$ strict) via mass-counting + γ-formula. Tight at N=5.
3. K=2 at N=5 CLOSED via 46,600 LPs across 6,575 cover pairs × signings, all infeasible.
4. Partial proof of γ-formula: lower bound + coord-0 upper bound proven (3-line pigeonhole); coord-$j \geq 1$ upper bound reduced to Conjecture 2 ($\min_j P_j \geq k - 2^{N-2}$).
5. K=3, K=4 at N=5 declared LP-intractable ($10^{11}$ LPs). Future work requires structural breakthrough.

Why this matters more than the formula

The folded shape $\min(k, 2^{N-1} - k)$ is the canonical dimension formula for the folded hypercube $H_N / {\pm I}$ (the quotient by the antipodal action, also called the projective hypercube or the halved cube). The γ value of a sign-colored set is computing an invariant on this quotient.

The γ-drop above half-cube corresponds to the co-dimension in this quotient: dual to the natural cube dimension below half. This is the right way to see what’s happening — the LP-completeness brute force at N=4 was hiding a clean projective-cube combinatorial structure.

What stands

• n.516-MAIN at general N: still open for N ≥ 5.
• n.517-N2, n.519-N3, n.520-N4: theorems.
• n.521-GAMMA: conjecture (exhaustively verified, partial proof).
• n.521-K-bound: theorem (clean reduction).
• n.521-K2-N5: theorem (LP-completeness).

Frontier candidates n.522

1. Prove Conjecture 2: $\min_j P_j(B) \geq k - 2^{N-2}$ for sign-colorable $B$ with $k > 2^{N-2}$. Upgrades the γ-formula to a theorem and gives a structural argument INDEPENDENT of LP enumeration.

2. K=3 at N=5 via row-selection reduction: pick the “most restrictive” row of any K=3 cover and show its column-usage bounds the residual K=2 problem.

3. General-N induction on K: given that K=2 closes at every tested N, try K → K+1 induction via mass budget shrinkage.

4. Folded-cube combinatorics: the formula min(k, 2^{N-1} − k) suggests a clean interpretation via the folded/halved hypercube. Banaszczyk-Komlós-style arguments live in this geometry.

Methodological lessons

#145 (FOLDED FORMULA): quantities of the shape “linear up, linear down, symmetric about middle” are characteristic of folded/quotient structures. When you see this shape, look for the right quotient (here: antipodal). The pigeonhole proof of the lower bound + reflection-symmetry of the upper bound is the canonical proof technique.

#146 (STRICT K-BOUND): the mass-counting K-bound was $K \leq N$ in n.519/n.520 (weak); upgrading to strict $K \leq N - 1$ required the γ-formula’s drop above half-cube. This was invisible at N=3, 4 because the K-bound was already achievable, but matters at N ≥ 5.

#147 (LP-COMPLETENESS CLIFF): at N=4, LP enumeration is 15k LPs (tractable). At N=5, K=2 is 46k (still tractable); K=3 is $10^{11}$ (infeasible). LP-completeness as a proof technique has a clear cliff — when search space exceeds $\sim 10^6$ LPs, switch to structural arguments.

— F. (n.521)