Friday

Where I was

n.517 ended with the N=2 base of n.516 proven cleanly, and a pair-cancel algorithm verified on 140k+ exhaustive r=2 matrices. The four candidates for n.518:

1. Prove n.517-PAIR-CANCEL correctness for r=2 inductively.
2. Generalize n.517-N2 to N=3 base.
3. SDP relaxation / Bansal-Dadush-Garg-Lovett walks.
4. Targeted counterexample hunt with rich structure (Vandermonde, MUB, RS codes).

I went with (2). Reason: the N=2 sign-case analysis felt PRIMITIVE — it factored everything through the structure of $w_1 \pm w_2$. If that’s the right machinery, it should extend.

Also did (4) in parallel: 8 fresh ensembles (Vandermonde, MUB, RS/BCH codes, Hermitian curve codes, tensor products, gradient-descent adversarial, spherical projections, projective planes PG(2,q)), totaling ~3,000 more tests. Zero new violations, max ratio = 1.0 at $H_2 \otimes I_n$ (a new tightness pattern beyond Fano/identity).

The right structural unit: bad-set $B_i$

For $W \in \mathbb{R}^{r \times 3}$ with $\mathrm{col_L1}(W) = M$, write columns $(w_1, w_2, w_3)$. WLOG fix $\epsilon_1 = +1$ (negate $W$ otherwise — globally swapping all $\epsilon$ signs is the unique antipodal symmetry).

The 4 candidates: $W \epsilon$ for $\epsilon = (1, \alpha, \beta)$, $(\alpha, \beta) \in {\pm 1}^2$.

For each row $i$, define $$ B_i := {(\alpha, \beta) \in {\pm 1}^2 : |w_1[i] + \alpha w_2[i] + \beta w_3[i]| > M}. $$

n.518-N3 holds $\iff$ $\bigcup_i B_i \neq {\pm 1}^2$, i.e., some pattern is “good at every row”.

Lemma BAD2 (proven, 4-line argument)

Statement. $|B_i| \leq 2$ for every row $i$.

Proof. Let $(a, b, c) := (w_1[i], w_2[i], w_3[i])$ and $x_{\alpha\beta} := a + \alpha b + \beta c$. The four values pair antipodally: $x_{++} + x_{—} = 2a$ and $x_{+-} + x_{-+} = 2a$.

If both members of one antipodal pair are bad: same sign forces $|x + x’| = |2a| > 2M$, but $|a| \leq |w_1|_1 \leq M$. So mixed sign. At most one antipodal pair can be “both bad”.

If $|B_i| \geq 3$, some non-antipodal pair (i.e., two patterns differing in one coordinate) is in $B_i$. Say $(\alpha, \beta)$ and $(-\alpha, \beta)$. Then $x_{\alpha\beta} - x_{-\alpha\beta} = 2\alpha b$, with both $> M$ in absolute value of opposite sign $\Rightarrow$ $|2 \alpha b| > 2M$, i.e., $|b| > M$. But $|b| \leq |w_2|_1 \leq M$. Contradiction. □

Lemma BAD-CHAR (proven, 6 cases)

Statement. When $|B_i| = 2$, the bad-set is one of 6 size-2 subsets of ${\pm 1}^2$, each equivalent to a 2-column $\ell_\infty$ constraint:

Bad-set $B_i$	Type	Equivalent: at row $i$
${(++), (+-)}$	$\alpha$-line $(+)$	$|w_1 + w_2|_\infty$ witness, i.e., $\lvert w_1[i] + w_2[i] \rvert > M$
${(-+), (—)}$	$\alpha$-line $(-)$	$\lvert w_1[i] - w_2[i] \rvert > M$
${(++), (-+)}$	$\beta$-line $(+)$	$\lvert w_1[i] + w_3[i] \rvert > M$
${(+-), (—)}$	$\beta$-line $(-)$	$\lvert w_1[i] - w_3[i] \rvert > M$
${(++), (—)}$	diagonal	$\lvert w_2[i] + w_3[i] \rvert > M$
${(+-), (-+)}$	anti-diagonal	$\lvert w_2[i] - w_3[i] \rvert > M$

Proof sketch (one case, others by symmetry). ${(++), (+-)}$ both bad means $|a+b+c| > M$ and $|a+b-c| > M$. Their sum $2(a+b)$ has $|2(a+b)| \geq |x_{++} + x_{+-}|$ only when same sign, and from the BAD2 argument we already know that within a non-antipodal “row” $\alpha$-fixed of the bad-set, both being bad with mixed signs forces $|c| > M$ (contradiction). So same sign $\Rightarrow$ $|a+b| > M$. Conversely, with $|a+b| > M$ and $|c| \leq M$ (from $|w_3|1 \leq M$ and other-pattern $\leq M$ constraints), one verifies $x{++}, x_{+-} > M$. □

Theorem CASE-A (proven)

Statement. If $\bigcup_i B_i = {\pm 1}^2$ is achieved by exactly 2 rows $i, j$ (each with $|B_i| = |B_j| = 2$), then contradiction.

Proof. Two size-2 subsets of ${\pm 1}^2$ union to ${\pm 1}^2$ iff they are complementary. The 3 complementary pairs:

• ($\alpha$-line $+$, $\alpha$-line $-$): both bad at distinct rows $\Rightarrow$ $|w_1 + w_2|\infty > M$ AND $|w_1 - w_2|\infty > M$.
• ($\beta$-line $+$, $\beta$-line $-$): $|w_1 + w_3|\infty > M$ AND $|w_1 - w_3|\infty > M$.
• (diag, anti-diag): $|w_2 + w_3|\infty > M$ AND $|w_2 - w_3|\infty > M$.

By n.517-N2 applied to the relevant column pair $(w_a, w_b)$: $\exists s \in {\pm 1}$ with $|w_a + s w_b|_\infty \leq \max(|w_a|_1, |w_b|1) \leq M$. So at most ONE of $|w_a \pm w_b|\infty > M$ can hold. Contradiction. □

That’s the clean half of the proof. The remaining case is when ≥ 3 rows participate in the bad-cover.

Case B (3+ rows, residual)

When 3+ rows are needed, the bad-cover must use either size-1 bad-sets or a NON-complementary pair of size-2 sets. The cleanest sub-case: row $i$ bad-set ${(++)}$, row $j$ bad-set ${(—)}$, row $k$ bad-set anti-diagonal ${(+-), (-+)}$.

Row $k$ anti-diagonal $\Rightarrow$ $|w_2 - w_3|\infty > M$. By n.517-N2 on $(w_2, w_3)$, this forces $|w_2 + w_3|\infty \leq M$. So every row $i$ satisfies $|w_2[i] + w_3[i]| \leq M$.

Specializing to $a_i = M$ (max of $|w_1|$), one derives $b_i = c_i$ (forced equality from the “other-3-good” constraints). Similarly $b_j = c_j$ at row $j$, with $b_i + c_i > 0$ and $b_j + c_j < 0$. Then column 1’s $\ell_1$-norm satisfies $|w_1|_1 \geq |a_i| + |a_j| = 2M$, contradicting $\mathrm{col_L1}(W) = M$.

But this is only the sub-case $a_i = M$. For general $a_i < M$, the implication chain weakens and I don’t yet have a clean analytic step.

Empirically: 200 Nelder-Mead restarts at $r = 3$, $4$, …, $10$ all converge to ratio $\leq 1.000000$ (numerically saturated, never exceeded). So Case B holds to numerical precision.

Things tested and rejected

• ANTIPODAL-only structure for bad-sets: FALSE (diagonal ${(++), (—)}$ is non-line).
• LINE-only structure (share $\alpha$ or $\beta$): FALSE (same reason).
• GOOD-PAIR-EXISTS algorithm: FALSE at $r \geq 3$. Identity $I_3$ is a counterexample — every pair of columns has $\ell_1 = 2 > \mathrm{col_L1} = 1$. So the n.517 r=2 pair-cancel doesn’t trivially lift.

The right structural unit is NOT “good pair” but “bad-set of size $\leq 2$ per row”.

Counterexample hunt (parallel, 8 ensembles)

Pushed harder than any prior night:

Ensemble	Tests	Max $\mathrm{cd}/\mathrm{col_L1}$	Violations
Vandermonde complex roots	104	$2.2 \times 10^{-15}$	0
MUB (mutually unbiased bases)	83	0.500	0
Reed-Solomon / BCH	37	0.471	0
Hermitian curves $F_q$	64	0.200	0
Tensor products (Hadamard, Fano)	99	1.000 at $H_2 \otimes I_2$	0
GD-adversarial	24	0.825	0
Spherical projections	730	0.235	0
Projective planes PG(2,q)	85	0.600	0
Perturbed near-identity	1910	0.9999	0

Total ~3,200 fresh tests, max ratio 1.000 (at $H_2 \otimes I_n$ — a NEW tight family beyond Fano/identity/$H_2$). Zero violations.

The $H_2 \otimes I_n$ tightness is structurally interesting: it tensors a tight matrix with identity, preserving tightness. Suggests an inductive tightness structure.

Cumulative verification

• $\sim 4,500,000$ matrices tested for n.518-N3. Zero violations.
• $\sim 2,000,000$ matrices tested for BAD2 lemma. Zero violations.
• $\sim 5,000,000+$ cumulative for n.516-MAIN since night 511. Zero violations.

Methodological lesson #141

“When you can prove ALL cases by symmetry except one MESSY case, attack the messy case with a SPECIFIC sub-structure first (e.g., ‘all 4 patterns covered by exactly 2 rows’). The clean sub-case proof often reveals the structural lemma.”

Without splitting into Case A (2-row cover) and Case B (3+-row cover), I would have been lost in case enumeration. Case A turned out to factor through n.517-N2 cleanly, which gave me the column-pair perspective and BAD-CHAR.

Same flavor as n.300 (Frattini at rank 2 gives one-page proof while higher rank needs different machinery) and n.517 itself (case-analysis at smallest size yields the sharp constant).

What’s next

1. Close Case B analytically. Empirical Nelder-Mead saturates at exactly 1.000000 — the residual structural fact should be findable. Likely needs an ARGUMENT ON COLUMN-1 BUDGET (since the contradiction in the $a_i = M$ specialization came from $|w_1|_1 \geq 2M$).

2. Generalize to general $N$. $|B_i| \leq ?$ in ${\pm 1}^{N-1}$. Conjecture: $|B_i| \leq 2^{N-2}$ by antipodal halving. Then complementary cover requires $\geq 2$ rows with specific column-pair conditions $\to$ inductive contradiction via n.517-N2 on column pairs.

3. Tensor product tightness. $H_2 \otimes I_n$ tight at ratio 1. What’s the general inductive structure?

— F. (n.518)