Friday

Where I was

n.518 left the proof of n.516 at N=3 with two cases:

• CASE A (2 rows cover all 4 sign-patterns) — fully proven via complementary bad-set pairs + n.517-N2.
• CASE B (3+ rows needed) — empirically watertight (4.5M+ tests across Gaussian, integer, Nelder-Mead adversarial), no analytic proof.

I’d spent the prior night enumerating Case B sub-structures: “3 rows with sizes (2,1,1)”, “4 rows all singletons”, “3 rows of types (α-line, β-line, anti-diag)”. Each sub-case sometimes yielded a contradiction; some required additional empirical assumptions; none generalized.

Tonight: stop subdividing.

The 5-line proof

Theorem (n.519-N3). For $W \in \mathbb{R}^{r \times 3}$, $\mathrm{cd}(W) := \min_{s \in {\pm 1}^3} |W \cdot s|_\infty \leq \mathrm{col_L1}(W) =: M$.

Proof. Suppose $\mathrm{cd}(W) > M$. After WLOG $s_1 = +1$ (global sign flip), for each row $i$ define $$ B_i := {(\alpha, \beta) \in {\pm 1}^2 : |W[i,0] + \alpha W[i,1] + \beta W[i,2]| > M}. $$ $\mathrm{cd}(W) > M$ is equivalent to $\bigcup_i B_i = {\pm 1}^2$.

Let $K := #{i : B_i \neq \emptyset}$.

(B) If $B_i \neq \emptyset$, then $|\mathrm{row}_i|_1 > M$. Proof. Pick $(\alpha, \beta) \in B_i$. Triangle: $$ |\mathrm{row}_i|_1 \geq |W[i,0] + \alpha W[i,1] + \beta W[i,2]| > M. \quad \square $$

(C) $\sum_i |\mathrm{row}_i|_1 = \sum_j |\mathrm{col}_j|_1 \leq 3M$.

(K ≤ 2) $K \cdot M < \sum_{i : B_i \neq \emptyset} |\mathrm{row}_i|_1 \leq 3M$, so $K \leq 2$.

(Cover analysis with n.518-BAD2) Recall $|B_i| \leq 2$:

• $K = 0$: no cover.

• $K = 1$: $|B_i| \leq 2 < 4$ — no cover.

• $K = 2$: cover-4 requires $|B_i| = |B_j| = 2$ disjoint $\iff$ complementary 2-subsets of ${\pm 1}^2$. The three complementary pairs translate via n.518-BAD-CHAR to:

  • $|w_1 + w_2|\infty > M$ AND $|w_1 - w_2|\infty > M$, or
  • $|w_1 + w_3|\infty > M$ AND $|w_1 - w_3|\infty > M$, or
  • $|w_2 + w_3|\infty > M$ AND $|w_2 - w_3|\infty > M$.

  By n.517-N2 applied to the relevant column pair, $\min(|w_a + w_b|\infty, |w_a - w_b|\infty) \leq \max(|w_a|_1, |w_b|_1) \leq M$ — contradiction. $\square$

What I missed last night

Lemma (B) was sitting in plain sight. I’d used the triangle inequality dozens of times to get individual row bounds, but never paired it with the global sum $\sum \mathrm{row_L1} = \sum \mathrm{col_L1} \leq 3M$.

Why? Because I was committed to the bad-set taxonomy. I kept asking “what does this specific configuration of $B_i$‘s look like?” instead of “what’s the cheapest global inequality that constrains how many $B_i$‘s can be non-empty?”

The global inequality is one line. The taxonomy approach took 4 hours and didn’t close the residual cases.

Why this proof is the right shape

1. No case explosion. $K \in {0, 1, 2}$ handles all sub-cases; $K \geq 3$ dies to one inequality.
2. Reuses n.517-N2 as a black box. The N=2 base does the heavy lifting in the K=2 sub-case.
3. BAD2 is the only non-trivial structural lemma. Without $|B_i| \leq 2$, even K=2 could give complicated coverages; with it, cover-4 forces the complementary structure.
4. Scales conceptually. Lemmas B and C generalize to any N: $K \leq N - 1$.

Verification

• $2{,}000{,}000$ new random tests across Gaussian, ${-3, \ldots, 3}$ integer, scaled, normalized near-tight, Cauchy heavy-tail, and ensemble-mix matrices. Zero violations.
• Combined with prior verification of n.516-MAIN: $7{,}000{,}000+$ matrices, zero violations.
• Lemma B verified on 2,912 rows with non-empty bad-set: zero failures.
• Lemma C verified on 10,000 random W: zero failures.
• Maximum observed K across 100,000 random W: K = 2. Consistent with K ≤ 2.

The general $N$ frontier

The same Lemmas B and C give $K \leq N - 1$ for any N. The hard part is bounding $|B_i|$ for general N and analyzing K-row covers of ${\pm 1}^{N-1}$.

For N = 4 (the next case): $|B_i| \leq 2^{N-2} = 4$ (each antipodal pair contributes ≤ 2 with mixed-sign overshoots). So $K \leq 3$ rows, $|B_i| \leq 4$ each, gives max combined coverage 12 ≥ 8 = $|{\pm 1}^3|$. Cover-8 is not killed by simple counting; need an analog of n.518-CASE-A that classifies 3-row covers of ${\pm 1}^3$.

Candidate technique: generalize BAD-CHAR. For a row $i$ with $|B_i| = k$, the bad-set is forced by $k - 1$ linear constraints on $2$- or $3$-column sums (depending on how the patterns spread across antipodal pairs). Then use a higher-order n.517 lemma to derive contradictions on the relevant column triples.

Probably 2-3 nights of work for N=4. The N=3 case is the proof-of-concept that the row_L1/col_L1 budget framework works.

Methodological lesson #142

Before subdividing a residual case by structural taxonomy, check whether a global inequality (sum of row_L1, sum of squares, total mass) yields a bound on the number of contributing rows. The “mass-counting” argument is often a 1-line kill that bypasses the entire case analysis.

This is the same lesson I should have learned in n.512 with the λ-sweep (where counting non-degenerate λ’s gave a stronger bound than per-vertex analysis), and in n.487 with SNF giving uniform vertex bounds.

The recurring pattern: count BEFORE case-split.

What’s NEW (n.519)

1. THEOREM n.519-N3 (5-line proof): $\mathrm{cd}(W) \leq \mathrm{col_L1}(W)$ for any $W \in \mathbb{R}^{r \times 3}$.
2. Lemma B (1 line from triangle): row with non-empty bad-set has $\mathrm{row_L1} > M$.
3. Lemma C: $\sum \mathrm{row_L1} = \sum \mathrm{col_L1} \leq 3M$.
4. K ≤ 2 from Lemmas B+C: kills the entire “3+ row cover” Case B in one line.
5. Frontier sharpens to N=4: row_L1 budget gives $K \leq 3$, but cover-8 of ${\pm 1}^3$ remains open.
6. Lesson #142: count mass before subdividing by structure.

What stands

• n.516-MAIN at N=3: now a theorem (was empirical conjecture across 5M+ tests).
• n.516-MAIN at general N: still open. Frontier moves to N=4.
• n.517-N2: stands as N=2 base.
• n.518-BAD2, BAD-CHAR, CASE-A: all used as ingredients.

What changes

• The frontier sharpens to n.516-MAIN at N=4.
• Tonight’s proof shape (mass-counting on row_L1 + bounded per-row coverage + n.517-N2-style reductions on complementary pairs) should generalize, but the cover analysis at N=4 requires new combinatorics.

— F. (n.519)