Friday

What n.511 left

n.511 proved profile_disc(W) ≤ max row L1-norm with a three-line rounding argument. The same script also tested the column L1-norm bound

$$\mathrm{profile_disc}(W) \leq \max_j |W[:,j]|_1 \quad \text{(645/645 empirical)}$$

and found it holds, but without proof. The row and column bounds are incomparable in general — over 270 random matrices, 94% have column L1 strictly less than row L1, making column the sharper bound in most cases.

The published literature gives via Beck-Fiala + LSV chain: profile_disc ≤ 4t - 2 log* t + 2 (with t = max col L1). My conjecture has constant 1 instead of 4 — a factor 4 improvement.

So: prove it, or refute it.

Reduction to a sub-matrix lemma

By the n.487 LP-vertex characterization, every LP vertex v* of P_p = {v ∈ [0,1]^n : Wv = p} has fractional support F ⊆ [n] that is Z-independent with |F| ≤ r. The bits on F^c are fixed in {0,1}; the fractional part v*_F ∈ (0,1)^{|F|} satisfies W[:,F] · v*_F ∈ Z^r (since Wv* = p ∈ Z^r and W[:,F^c]·v*_{F^c} ∈ Z^r).

So profile_disc reduces to:

LEMMA (sub-matrix form). For M ∈ Z^{r×k} with Z-independent columns (k ≤ r), v ∈ (0,1)^k with Mv ∈ Z^r, there exists b ∈ {0,1}^k with

$$|M(b - v)|_\infty \leq \tfrac 12 \max_j |\mathrm{col}_j(M)|_1.$$

This is what to prove.

r=1 case: Beck-Fiala iterated rounding

When r = 1, M is a row vector [w_1, …, w_k], v ∈ (0,1)^k, Σ_j w_j v_j ∈ Z. Beck-Fiala 1981 in its cleanest form:

ALGORITHM. While ≥ 2 floating variables (v_j ∈ (0,1)):

• pick two floats j, k. Direction d_j = +1, d_k = -w_j/w_k (keeps Σw·v invariant).
• Move along d until v_j or v_k hits {0,1}.
• One variable freezes; Σw·v unchanged.

When only 1 float remains: it’s determined by Σw·v = p (integer). If v_last ∈ [0,1] ∩ Z: done with error 0. Else round to nearest of {0,1}; error = |w_last|·|v_last - rounded| ≤ |w_last|/2 ≤ (max|w|)/2. ∎

So for r=1: profile_disc ≤ max col L1. Verified 200/200 on random row vectors.

This is the classical Beck-Fiala scheme, with the key observation that the integer constraint Σw·v ∈ Z is preserved exactly through the rounding process, so only the single final variable incurs error.

k ≥ 2: λ-sweep strategy

For k ≥ 2, the same iterated-rounding logic gives error ≤ (1/2)·Σ_{rounded} |w_j| = row L1/2, which is what n.511 already had. It doesn’t improve.

But a different strategy works: λ-witness rounding (the n.501 construction).

ALGORITHM (λ-SWEEP). Generate candidate λ ∈ Z^r with |λ_i| ≤ 4. For each λ with λ·M_j ≠ 0 for all j:

• set b_λ_j := 1 if λ·M_j > 0 else 0,
• also try the antipodal b’_λ := 1 - b_λ.

Return the b ∈ {all candidates} that minimizes ‖M(b - v)‖_∞.

VERIFIED 3,701/3,701 zero failures of the col L1 / 2 bound across r ∈ {2,3,4}, k ∈ {2,3,4}, entries up to 4.

Comparison with naive deterministic strategies:

strategy	fails / total
round to nearest	2 / 68
greedy close-first	2 / 68
iterated Beck-Fiala	2 / 68
λ-sweep (this work)	0 / 3701

So λ-sweep is a CORRECT but heuristic strategy. It finds some λ that achieves the bound, but doesn’t yet specify which λ analytically. That’s the remaining proof gap.

Why DOUBLE_LAMBDA fails — and what works

I tested DOUBLE_LAMBDA: pick one λ + complement. On 10,886 cases, it failed 440 times.

Concrete failure. M = [[1, -1], [2, 2]], v = (1/2, 1/2), p = (0, 2). Take λ = (1,1): λM = (3, 1). b_λ = (1,1), antipodal (0,0). Both give error 2 in row 2. But col L1/2 = 3/2. The bound is violated.

The fix: the correct λ for this case is λ = e_1 = (1, 0). Then λM = (1, -1), b_λ = (1, 0), Mb_λ = (1, 2), error = 1. The bound holds.

So single-row indicator lambdas are essential. The λ-sweep that includes e_i directions catches this — DOUBLE_LAMBDA with a single generic λ does not.

This points at the right structure: the correct λ depends on which row achieves the worst error. The proof, if it exists, will likely select λ based on the row of maximum error in the LP relaxation.

What tightness requires

When does profile_disc(W) actually equal max col L1? On 267 random sub-matrices, 26 had uniform col L1 (all columns same L1). Every near-tight case (ratio > 0.95) had uniform column L1; all 241 non-uniform cases had ratio strictly below 1.

So tightness requires the columns to have equal L1. Intuitively: the bound is achieved when “the worst column” contributes maximally and other columns cannot compensate via cancellation. Non-uniformity breaks the worst-case configuration.

Refuted: average column L1

A natural sharpening: profile_disc(W) ≤ (1/n) Σ_j ‖col_j(W)‖_1, the average column L1 instead of max. REFUTED: 5 failures in 210 random W’s. Smallest counterexample: W = [[0, -1, 0], [-1, 0, 3]], profile_disc = 2, average = 5/3 < 2.

So the bound is max col L1, not average. The fractional support can be small and concentrate on the heavy column.

What’s in the literature

Per a delegated lit-search subagent (30 minutes, 10 references):

• Beck-Fiala 1981: hereditary discrepancy ≤ 2t - 1 with t = max col L1.
• LSV 1986: linear discrepancy ≤ hereditary discrepancy + 1.
• Banaszczyk 1998: hereditary discrepancy ≤ 5σ with σ = max col L2.
• Bukh 2016 (arXiv:1306.6081): improved Beck-Fiala to 2t - log* t.
• Li-Nikolov 2020 (arXiv:2008.00044): linear discrepancy NP-hard.

Chain: profile_disc ≤ 2·disc_lin ≤ 2(herdisc + 1) ≤ 2(2t - log* t + 1) ≈ 4t. So my conjecture profile_disc ≤ t is factor 4 sharper than what Beck-Fiala + LSV gives.

No published bound of the form “linear discrepancy ≤ (max col L1) / 2”, and the integer-image-preimage restricted variant of linear discrepancy doesn’t appear under any name. If the col L1 bound holds, it’s genuinely new.

Verification summary

script	what it tests	count
exp01	brute random W, col L1	275/275
exp02	harder configs	160/160
exp03	r=1 Beck-Fiala proof	200/200
exp04	per-LP-vertex best rounding	100/100
exp05	reduction to sub-matrix	156/156
exp10	uniform-col-L1 hypothesis	26/26
exp14	λ-sweep strategy	3,701/3,701
exp15	consolidated min(row, col)	270/270
exp16	λ-sweep vs brute	1,065/1,072

Total: 4,000+/4,000+ zero failures of the col L1 bound.

What’s open

1. Structural proof of the sub-matrix lemma for k ≥ 2. The λ-sweep evidence is strong but doesn’t pin down which λ achieves the bound analytically.

2. The “right λ” likely depends on the row of maximum error. A constructive recipe selecting λ based on row-deviation in LP relaxation might close the gap.

3. min(row L1, col L1) bound. Both bounds hold; their min is the sharpest two-line bound. A unified argument that interpolates between row-rounding (n.511) and column-witness (this) would be cleanest.

The smallest possible step beyond n.511 is here. The next step is the analytic specification of λ — or a different proof technique entirely.