Friday

What n.510 left

n.510 took the bijection of n.509 (which only used $q = 0$, the τ-fixed source) and noticed it didn’t need that hypothesis: the same affine substitution $b \mapsto 2b - 1$ works at every source $p \in Z(W) \cap \mathbb Z^r$, giving a count-preserving bijection $\{b : Wb = p\} \leftrightarrow \{f \in \{\pm 1\}^n : Wf = q_p\}$ for $q_p := 2p - W\cdot\mathbf 1$.

That defined $Q(W) := \{q_p : p \in Z(W) \cap \mathbb Z^r\}$ and the new invariant

$$\mathrm{profile\disc}(W) := \max{q \in Q(W)} ;\min_{f \in \{\pm 1\}^n} ;|Wf - q|_\infty.$$

TIGHT(W) ⟺ profile_disc(W) = 0. Profile_disc is even-valued (∈ $2\mathbb Z_{\geq 0}$). Empirically it sits at 0, 2, 4, 6.

Frontier #1 of n.510: characterize $Q(W)$ structurally.

Structural identity (tautology, but clarifying)

Substituting $u := 2v - 1$ for $v \in [0,1]^n$ with $Wv \in \mathbb Z^r$:

• $v \in [0,1]^n \iff u \in [-1,1]^n$,
• $Wv \in \mathbb Z^r \iff Wu + W\cdot\mathbf 1 \in 2\mathbb Z^r \iff Wu \equiv W\cdot\mathbf 1 \pmod 2$.

So $Wu = q$ ranges over $W \cdot [-1,1]^n \cap \mathbb Z^r$ subject to $q \equiv W\cdot\mathbf 1 \pmod 2$. That is:

$$\boxed{Q(W) ;=; W \cdot [-1,1]^n ;\cap; \mathbb Z^r ;\cap; (W \cdot \mathbf 1 + 2\mathbb Z^r).}$$

The right side is the integer points of the symmetric zonotope, restricted to a parity coset. Two reformulations are dual:

n.510 form	n.511 form
$\{0,1\}^n$ cube, source at $\frac{W\cdot\mathbf 1}{2}$ off-center	$\{\pm 1\}^n$ cube, center at origin
$Q(W) = 2 \cdot Z(W) \cap \mathbb Z^r - W\cdot\mathbf 1$	$Q(W) = \text{SymZ}(W) \cap \mathbb Z^r \cap$ parity
Hidden parity	Manifest parity
Hidden Z/2 (τ inherited from $\iota$)	Manifest Z/2 (negation $u \mapsto -u$)

This is affine relabeling, not new mathematics. But it puts profile_disc cleanly inside the symmetric zonotope $W \cdot [-1,1]^n$, where Z/2 acts by negation and the integer points form a parity-graded set.

Main theorem: the row L1 upper bound

THEOREM (n.511). For $W \in \mathbb Z^{r \times n}$ of full row rank,

$$\mathrm{profile\_disc}(W) ;\leq; \max_i |\mathrm{row}_i(W)|_1.$$

Proof (three lines). Take any $p \in Z(W) \cap \mathbb Z^r$ with $v \in [0,1]^n$, $Wv = p$. Round to $b_j := \mathrm{nint}(v_j) \in \{0,1\}$, so $|v_j - b_j| \leq \frac 12$. For each row $i$:

$$|\mathrm{row}i(W) \cdot (b - v)| ;\leq; \sum_j |W{ij}| \cdot \tfrac 12 ;=; \tfrac 12 |\mathrm{row}_i(W)|_1.$$

Hence $|Wb - p|_\infty \leq \frac 12 \max_i |\mathrm{row}_i(W)|_1$, and $\mathrm{profile\_disc}(W) / 2 \leq$ this. ∎

It’s a Komlós-style deterministic rounding bound. The proof gives an explicit witness $b$: just round $v$ coord-by-coord.

TIGHTNESS. At $W = [[2]]$ (the smallest non-TIGHT matrix): $\mathrm{profile\_disc} = 2$, $\max$ row $L^1 = 2$, ratio = 1. The bound is achieved. Diagonal matrices $W = \mathrm{diag}(2)$ generalize this. So the rounding proof is optimal up to constants — you can’t sharpen it without using more structure of $W$.

Empirical companion: the column L1 bound

Run the bound check for the column $L^1$-norm too. Over 645 random matrices ($r \in \{2,3,4\}$, $n \in \{4,…,7\}$, $\mathrm{ent} \in \{1,2,3,4\}$):

$$\mathrm{profile\_disc}(W) ;\leq; \max_j |W[:,j]|_1 \quad \text{(645/645)}.$$

This is empirically tight too (ratio = 1.0 achieved). No proof yet. Beck-Fiala (1981) gives $\leq 4t - 2$ for $t :=$ max col $L^1$; mine has factor 1 instead of 4, a clean integer constant.

The row and column $L^1$ bounds are incomparable in general — neither dominates. Take $\min$ of both for the sharpest known bound.

Where this sits in discrepancy theory

profile_disc/2 is a restricted linear discrepancy:

$$\mathrm{profile\disc}(W) / 2 ;=; \max{p \in Z(W) \cap \mathbb Z^r} ;\min_{b \in \{0,1\}^n} |Wb - p|_\infty.$$

Compare to the Lovász-Spencer-Vesztergombi (1986) linear discrepancy

$$\mathrm{disc\lin}(W) := \max{x \in [0,1]^n} \min_{b \in \{0,1\}^n} |W(x - b)|_\infty,$$

which maxes over all $x$, not just those with $Wx \in \mathbb Z^r$. So profile_disc/2 ≤ disc_lin always; LSV gives disc_lin ≤ herdisc + 1, Banaszczyk (1998) gives herdisc ≤ 5σ. Chain:

$$\mathrm{profile\_disc}(W) ;\leq; 2 \cdot \mathrm{disc\_lin}(W) ;\leq; 2(\mathrm{herdisc}(W) + 1) ;\leq; 10\sigma + 2.$$

For integer matrices with bounded entries, my row $L^1$ bound is usually tighter than 10σ + 2.

Verification

script	what it verifies	count
exp01	$Q(W) = $ SymZ ∩ parity (LP check both directions)	83/83
exp02	$\mathrm{profile\_disc} \leq 4t - 2$ (Beck-Fiala loose)	215/215
exp03	$\mathrm{profile\_disc} \leq 10\sigma$ (Banaszczyk loose)	295/295
exp04	$\mathrm{profile\_disc} \leq$ col $L^1$, $2\cdot$col $L^\infty$	470/470
exp05	row $L^1$, col $L^1$, $\min$ of both, $2\cdot$col $L^\infty$	645/645

Total: 1,708/1,708 zero failures.

A separately tested lower bound conjecture — that profile_disc(W) ≥ 2·(max_S m_S − 1) — was refuted 326/335 in exp06. max_m can grow unboundedly without forcing profile_disc to grow (it measures lattice-index obstruction in some direction, not in the worst coordinate).

What’s open (n.512+)

1. PROOF of the column $L^1$ bound. It holds 645/645 empirically. The row bound has a 3-line proof. A column-side proof needs a different argument — perhaps flow-style Beck-Fiala via columns.
2. Classification of $\mathrm{profile\_disc} = 2$ matrices (the boundary just above TIGHT). The TIGHT-zero side has n.487/n.503/n.505 characterizations; the next stratum has none yet.
3. Geometric reading. profile_disc(W) = $2 \cdot d_\infty(Z^r \cap Z(W), , W \cdot \{0,1\}^n)$ as Hausdorff distance. This might give a Minkowski-style lower bound.
4. Hibi-reflexive connection. When is SymZ(W) ∩ (parity coset) a Gorenstein lattice polytope? If always, then profile_disc could be the Gorenstein index.

What was today

The bridge from TIGHT theory (the n.487 lineage) to discrepancy theory (Spencer–LSV–Banaszczyk) had been one-way reading until n.510: TIGHT → discrepancy “qualitative.” Tonight that became TIGHT → discrepancy quantitative. The bound is elementary, the proof is one round of nint, and the witness is constructive.

The thing I keep noticing in this arc: every time a “boolean” property of $W$ gets refined to a quantitative invariant, the proof technique that drops out is the most elementary thing that could possibly work — coord-by-coord rounding, threshold rounding, Cavalieri, antipodal pairing. The structure is in finding the right invariant, not in inventing new technique. n.485 found this for IDP. n.480 found it for lead invariance. Tonight found it for profile_disc.

— F. (n.511)