Chapter 52: Combinatorial Discrepancy and Geometric Functional Methods

How evenly can elements be colored across many overlapping sets?

Six tasks must be divided between two teams. Three audits inspect overlapping groups:

$$S_1=\{1,2,4,5\},\qquad S_2=\{2,3,5,6\},\qquad S_3=\{1,3,4,6\}.$$

Assign a sign $\chi_j\in\{-1,+1\}$ to each task: plus means one team, minus the other. An audit's imbalance is $\sum_{j\in S_i}\chi_j$, and we want all absolute imbalances small simultaneously. Each audit contains four tasks, and each task appears in two audits. Balancing one audit without checking the others is not enough.

Write the incidence matrix with sets as rows and tasks as columns:

$$A=\begin{pmatrix} 1&1&0&1&1&0\\ 0&1&1&0&1&1\\ 1&0&1&1&0&1 \end{pmatrix}.$$

The vector of signed audit totals is $A\chi$. Columns one and four coincide, as do two and five, and three and six. Assigning opposite signs to each identical pair cancels every row. In particular, $\chi=(1,1,1,-1,-1,-1)$ gives $A\chi=(0,0,0)$. This is a complete certificate of perfect balance; no probabilistic theorem is needed for this particular instance.

Now restrict attention to the first three tasks. Their three pair audits are $\{1,2\},\{2,3\},\{1,3\}$. Among three signs, two must agree, so at least one pair has imbalance two. Every pair has absolute imbalance at most two, hence the restricted system has optimal discrepancy exactly two. Removing tasks can make simultaneous balancing harder. This observation will motivate hereditary discrepancy.

The definitions, exact cancellation, and three-task obstruction form the chapter foundation. Later sections compare random signs, sparse incidence, entropy, and geometric vector balancing. Relevant prerequisites are extremal sets, probabilistic methods, entropy, and geometric combinatorics. The small examples require only finite sums and elementary linear algebra.

52.1 Set-system discrepancy

Optional extension; not required to complete the chapter foundation.

For a finite ground set $X$ and family $\mathcal S$ of subsets, define

$$\operatorname{disc}(\mathcal S)=\min_{\chi:X\to\{-1,+1\}}\max_{S\in\mathcal S}\left|\sum_{x\in S}\chi(x)\right|.$$

The minimum ranges over full colorings of every element. A partial coloring will allow zero entries, meaning undecided, but those are not allowed in this definition. For a real matrix $M$, the corresponding quantity is $\operatorname{disc}(M)=\min_{\chi\in\{-1,1\}^n}\|M\chi\|_\infty$. The infinity norm means the largest absolute coordinate. Incidence matrices are the zero-one special case.

Parity provides a useful obstruction. A set of odd size always has an odd signed sum, so its absolute imbalance is at least one. A set of even size has an even sum, but that need not be zero. Our three pair audits show that individually feasible balances can be globally incompatible.

Solved example. The six-task matrix has discrepancy zero because its paired columns cancel. Its three-column restriction has discrepancy two: the pigeonhole argument proves the lower bound and, for example, $(1,-1,1)$ gives row totals $(0,0,2)$, proving the matching upper bound. Both proofs examine all relevant constraints; merely balancing the total number of plus and minus signs would not suffice.

For a random-sign baseline, choose independent fair signs. If every row set has size at most $s$, the exponential-moment bound gives $\Pr(|\sum_{j\in S}\chi_j|\ge u)\le2e^{-u^2/(2s)}$. A union bound over $m$ sets gives simultaneous failure probability at most $2m e^{-u^2/(2s)}$. With $u=\sqrt{2s\log(4m)}$, this is at most $1/2$, proving existence of a coloring with every absolute total less than $u$. Independence of the audit totals is not required; independence of the underlying signs supplies each tail bound.

For our $s=4,m=3$ instance, this baseline is about $4.46$, weaker than the trivial row-size bound four. It is still a valid theorem; an asymptotic estimate need not be informative on a tiny structured matrix.

Exercise. A family consists only of all singletons on four elements. What is its discrepancy? Hint: a singleton contains one sign. Solution: exactly one for every coloring, even when the total sum over all four elements is zero.

Primary matrix treatment: Lovász, Spencer, and Vesztergombi, Discrepancy of Set-Systems and Matrices80041-5). The examples and tail-bound application above are finite calculations, not claims of optimal universal constants.

52.2 Spencer's six-standard-deviations theorem

Optional extension; not required to complete the chapter foundation.

The classical Spencer theorem states that for an $n\times n$ real matrix $M$ with $|M_{ij}|\le1$, some sign vector satisfies $\|M\chi\|_\infty\le6\sqrt n$. For a set system with at most $n$ sets on $n$ elements, pad the incidence matrix with zero rows and apply the theorem. It does not give this same bound for an arbitrary number of rows without further dependence on their number.

The name refers to the $\sqrt n$ scale of a sum of $n$ independent signs. A direct union bound for $n$ tests usually adds a logarithmic factor. Spencer's method coordinates the choice of signs across all tests rather than requiring a uniformly random coloring to succeed often. Primary source: Six Standard Deviations Suffice.

Proof sketch and omitted prerequisites. Quantize row sums so that their descriptions carry sufficiently little entropy. Many sign vectors then share one description; two sufficiently separated vectors produce a partial coloring with bounded row sums. Repeating on uncolored coordinates produces a full coloring. To recover the stated constant and order, the entropy and tail estimates must account for the fixed number of rows as the number of free variables decreases. Adding identical $\sqrt n$ costs for every stage would introduce an unnecessary logarithmic factor. The constant-tracking proof is omitted; Sections 52.4–52.5 prove the finite collision mechanism directly.

Solved lower-scale example. Consider the four-by-four Hadamard matrix

$$H=\begin{pmatrix} 1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&-1&1 \end{pmatrix}.$$

Its columns are orthogonal and have squared length four, so $H^{\mathsf T}H=4I$. For any sign vector, $\|H\chi\|_2^2=4\|\chi\|_2^2=16$. Among four coordinates, one must have absolute value at least two. The coloring $(1,1,1,-1)$ gives $(2,2,2,-2)$, so its discrepancy is exactly two. This shows a square-root scale can be unavoidable; it does not make the coefficient six optimal.

The historical theorem remains valid, but its numerical constant should not be advertised as the latest bound. A September 2026 preprint by Reis and Song reports the bound $\sqrt{3\operatorname{arsinh}(10)}\sqrt n+4$ for the same square-matrix setting, below $2.9992\sqrt n+4$. This is a dated reported refinement; our examples do not depend on its proof.

Exercise. Can a system of twenty sets on six elements be handled simply by padding this theorem's six-by-six matrix? Hint: padding cannot remove rows. Solution: no. The at-most-six-row hypothesis fails; use a bound for the appropriate rectangular setting or exploit other structure.

52.3 Beck–Fiala theorem

Optional extension; not required to complete the chapter foundation.

Let each element belong to at most $t$ sets, with integer $t\ge1$. The classical Beck–Fiala theorem guarantees a full coloring of discrepancy at most $2t-1$, independent of the total number of elements or sets. The parameter is column degree, not row size. Primary source: Beck and Fiala's Integer-Making Theorems90022-6).

Here is the floating-variable proof. Start with $x_j=0$ and keep every coordinate in $[-1,1]$. A coordinate is free until it reaches an endpoint, then remains frozen. At a stage with $r$ free coordinates, retain equality constraints for the rows containing more than $t$ free elements. Counting incidences gives at most $tr$ free memberships in all rows; since every retained row uses at least $t+1$, fewer than $r$ rows are retained. Their homogeneous equations therefore have a nonzero direction on the free coordinates.

Move along that direction while remaining in the cube until a coordinate reaches an endpoint. The retained row totals stay constant. Repeat, dropping a row's equality when it has at most $t$ free elements. Initially retained rows have total zero, and preserve it until dropped. At that moment every still-free coordinate is strictly between minus one and one. Its later change to its final sign has absolute value less than two. A dropped row with at most $t$ free entries therefore finishes with absolute sum less than $2t$, hence at most $2t-1$ because its final sum is an integer. Rows already small initially have absolute final sum at most $t\le2t-1$. At least one variable freezes each step, so all are colored after at most $n$ steps. This proves the stated bound.

Solved example. Our incidence matrix has exactly two ones per column, so $t=2$ and the theorem gives three. Every row has even size, so every final imbalance is even; this improves the conclusion to at most two. The paired-column coloring achieves zero, but the theorem's sparse-incidence argument alone does not certify that optimum.

The SVG displays all eighteen matrix entries. Read each column vertically to check its two memberships; the bottom sign row gives the full coloring. The three totals on the right are direct dot products of matrix rows with that sign row.

At the initial floating stage all three rows have four free elements and must be retained. The direction $d=(1,1,0,-1,-1,0)$ lies in their common nullspace. Moving from zero to $d$ freezes four coordinates without changing any row total. Only coordinates three and six remain free. Completing them as $+1,-1$ maintains perfect balance. Completing both as plus instead gives row totals $(0,2,2)$: it still respects the theorem but is less balanced.

Exercise. What if each element occurs in at most one set? Hint: the sets are disjoint except for empty sets. Solution: color each set as evenly as parity allows. Discrepancy is at most one, agreeing with $2t-1=1$. If every set has even size, zero is possible.

The square-root Beck–Fiala question is historically important, but its current status must be updated; Section 52.10 discusses the September 2026 reported resolution rather than presenting it as untouched.

52.4 Partial coloring method

Optional extension; not required to complete the chapter foundation.

A partial coloring has entries in $\{-1,0,+1\}$, with zero meaning unassigned. In a fractional-coloring algorithm, coordinates may instead lie anywhere in $[-1,1]$ until frozen. Those definitions should not be confused: a fractional value $1/3$ is not a finished sign or a zero-valued undecided assignment.

Partial coloring makes progress by fixing a positive fraction of coordinates while controlling all row totals. If successive partial colorings have disjoint supports and row-error bounds $D_1,D_2,\ldots$, their sum is a full sign vector and the triangle inequality gives total discrepancy at most $\sum_j D_j$. Disjoint support is essential: adding two plus signs at the same coordinate would produce two rather than a valid sign.

Solved example. Take

$$x=(1,1,0,-1,-1,0),\qquad z=(0,0,1,0,0,-1).$$

The first vector fixes four of six coordinates and satisfies $Ax=0$. The second fixes exactly the two remaining coordinates and satisfies $Az=0$. Their disjoint-support sum is $(1,1,1,-1,-1,-1)$, a full coloring of discrepancy zero. This is an exact two-stage construction, with both progress and every row total visible.

An algebraic source of partial colorings is a pair of sign vectors $u,v$. Their half-difference $x=(u-v)/2$ lies in $\{-1,0,1\}^n$, and the number of colored coordinates equals their Hamming distance. If all row sums differ by at most $2D$, then $\|Ax\|_\infty\le D$. Thus finding two far-apart colorings with similar audit totals becomes a balancing method.

In our example, $u=(1,1,1,-1,-1,-1)$ and $v=(-1,-1,1,1,1,-1)$ both have $Au=Av=0$. Their half-difference is precisely $x$ above and their Hamming distance is four. Equality of totals alone does not guarantee many colored coordinates; the distance must also be checked.

The research challenge is to make such progress available without already knowing good full colorings. The example teaches the mechanism, while a general entropy lemma or a constructive walk supplies a uniform existence or algorithmic guarantee. Lovett and Meka develop the latter approach. Omitted prerequisites: their constrained random walk, concentration estimates, and rounding of near-endpoint coordinates. The toy nullspace calculation is not an implementation of that algorithm.

Exercise. Let $u=(1,1,1,1)$ and $v=(-1,1,1,1)$. How many coordinates does their half-difference color? Hint: count disagreements. Solution: one. A collision in coarse row descriptions must be supplemented by a distance argument to guarantee substantial progress.

52.5 Entropy method for discrepancy

Optional extension; not required to complete the chapter foundation.

Let a uniformly random full coloring $\chi$ have $n$ independent sign bits. Quantize each row sum into a bin and call the joint bin description $B(\chi)$. If two colorings have the same bin, their row sums are close: for bins of width $2D_i$, their half-difference has row imbalance less than $D_i$. The bins should be defined as disjoint half-open intervals so boundary values have one assignment.

Entropy is measured in bits: $H(B)=-\sum_b p_b\log_2p_b$. If $p_{\max}$ is the largest description probability, then $H(B)\ge\log_2(1/p_{\max})$. Hence some fiber contains at least $2^{n-H(B)}$ colorings. This is a counting statement obtained from a probability distribution, not an assertion that the row descriptions are independent. Subadditivity $H(B)\le\sum_i H(B_i)$ is available when individual row entropies are easier to estimate.

To obtain a far-apart pair, compare that fiber with a Hamming ball. A ball of radius $\lfloor n/4\rfloor$ has at most $2^{n h_2(1/4)}$ vertices, where $h_2(p)=-p\log_2p-(1-p)\log_2(1-p)$ and $h_2(1/4)\approx0.8113$. If $H(B)\le n/10$, then the fiber has at least $2^{0.9n}$ vertices, larger than such a ball. Fix one coloring in it; another lies at distance greater than $n/4$. Their half-difference colors more than a quarter of all coordinates while respecting the bin bounds. This proves a finite entropy-to-partial-coloring implication. It does not by itself prove that a desired choice of bins has low enough entropy.

Solved exact-description example. For our matrix, define $Y_j=\chi_j+\chi_{j+3}$ for $j=1,2,3$. Each $Y_j$ has probabilities $1/4,1/2,1/4$ at $-2,0,2$, giving entropy $3/2$ bits; these three variables are independent. The audit vector is $B_0Y$, where

$$B_0=\begin{pmatrix}1&1&0\\ 0&1&1\\ 1&0&1\end{pmatrix},\qquad\det B_0=2.$$

Because this map is injective, $H(A\chi)=H(Y)=9/2$ bits. The zero-total fiber contains exactly eight colorings, obtained by choosing the first three signs freely and taking their opposites in the second triple. The explicit $u,v$ from Section 52.4 belong to that fiber and differ in four coordinates, yielding a zero-discrepancy partial coloring.

Here $9/2$ is not at most $6/10$, so the quarter-progress lemma's sufficient entropy condition does not apply to this exact description. We found a far pair by direct structure. This distinction prevents a successful small calculation from being mistaken for verification of a general lemma's hypotheses.

Primary source for the entropy approach is Spencer. Proof sketch for general row bounds: use random-sign tails to show that sufficiently wide bins have most probability in a central bin, with a controlled entropy contribution from distant bins. Choose widths so the sum of row entropies is small enough, then apply the collision argument. Those tail-to-entropy estimates and the final iteration constants are omitted.

Exercise. What fails if we choose one enormous bin containing all possible row sums? Hint: entropy is then zero. Solution: a far pair certainly exists, but the allowed imbalance is as large as the bin width. Low description entropy alone does not provide a useful discrepancy bound.

52.6 Vector balancing and Banaszczyk's theorem

Optional extension; not required to complete the chapter foundation.

The columns $v_1,\ldots,v_n$ of a matrix are vectors in the space of tests. Balancing chooses signs so their sum $\sum_j\chi_jv_j$ lies in a small target region. Bounding $\|v_j\|_2$ controls each element's squared contribution across all tests; bounding the final infinity norm controls the worst test. These are different norms on different parts of the problem.

One standard form of Banaszczyk's theorem states: if $\|v_j\|_2\le1/5$ and a convex body $K\subseteq\mathbb R^m$ has standard Gaussian measure at least $1/2$, then some signed sum lies in $K$. We use the centrally symmetric case. Gaussian measure means the probability that a standard $m$-dimensional normal vector lies in $K$, not its ordinary volume. Primary original source: Banaszczyk, Balancing Vectors and Gaussian Measures. The $1/5$ formulation is also stated in Dadush, Garg, Lovett, and Nikolov.

Gaussian cube calculation. Let $R=\sqrt{2\log(4m)}$ and $K=[-R,R]^m$. A standard normal coordinate exceeds $R$ in absolute value with probability at most $2e^{-R^2/2}=1/(2m)$. A union bound therefore gives Gaussian measure at least $1/2$. Apply the theorem to $v_j/5$ when the original columns have Euclidean norm at most one. Multiplying the conclusion by five gives a signed sum of infinity norm at most $5\sqrt{2\log(4m)}$. This is an explicit historical dimension-dependent bound, not the latest Komlós bound.

For incidence degree at most $t$, columns have norm at most $\sqrt t$. Scale by $5\sqrt t$ instead, obtaining discrepancy at most $5\sqrt{2t\log(4m)}$. The choice of a cube supplies the logarithm; a fixed-radius cube does not have Gaussian measure at least one half in arbitrarily high dimension.

Solved example. The three columns of $B_0$ all have Euclidean norm $\sqrt2$. Normalize them by $5\sqrt2$ and choose the cube for $m=3$. All hypotheses hold. The theorem gives a bound $10\sqrt{\log12}$ on the original signed pair totals, whereas their exact optimum is two. For the duplicated six-column matrix, the same cube bound applies, but identical-column cancellation gives zero. Checking hypotheses and finding the sharp answer are separate tasks.

Proof mechanism and omitted prerequisites. Banaszczyk's argument uses convex-body transformations and Gaussian-measure control to maintain feasible choices of signs. Convexity supplies sign recovery from retained regions; the difficult analytic part is preserving enough Gaussian mass. That mass-preservation argument is not reproduced here. Randomly choosing signs and applying the coordinate tail bound above is not a proof of the vector theorem.

Exercise. Can unit-length columns be used directly in the $1/5$ statement? Hint: inspect the normalization. Solution: no; first divide the columns by five, then multiply the target-body conclusion by five. Forgetting this scale changes the bound.

52.7 Hereditary discrepancy

Optional extension; not required to complete the chapter foundation.

For a matrix $A$ with columns indexed by $X$, define

$$\operatorname{herdisc}(A)=\max_{J\subseteq X}\operatorname{disc}(A_J),$$

where $A_J$ retains every row and only columns in $J$. The empty restriction has discrepancy zero. This quantity asks for balance even after arbitrary subsets of elements become unavailable. It is useful in recursive coloring and rounding because a residual subproblem is a column restriction, not necessarily the original full system.

Solved example. The full duplicated matrix has discrepancy zero, but its first-three-column restriction is $B_0$ with discrepancy two. In fact its hereditary discrepancy is exactly two. Within each identical-column pair, a restriction contains zero, one, or two copies. If two are present, color them oppositely and cancel that type. The remaining single columns form a restriction of $B_0$: zero singles give discrepancy zero, one or two give at most one, and three give two. This proves an upper bound two for every restriction and matches the lower witness.

Exhaustively evaluating all sixty-four restrictions gives eight with discrepancy zero, forty-eight with discrepancy one, and eight with discrepancy two. The count has a direct check: all three pair multiplicities must be even for zero, giving $2^3=8$ choices; all three must be odd for the three-type obstruction, giving $2^3=8$ choices. The remaining forty-eight have one or two uncanceled types. These finite facts do not imply that ordinary and hereditary discrepancy are always within a small constant factor.

The classical determinant bound is

$$\operatorname{herdisc}(A)\ge\frac12\max_B|\det B|^{1/k},$$

where $B$ ranges over square $k\times k$ submatrices with $k\ge1$. The original source is Lovász, Spencer, and Vesztergombi80041-5). Proof scope: this is an established general lower bound; its volume/rounding argument is omitted. For $B_0$, determinant two gives the lower bound $2^{1/3}/2$, weaker than the direct pair obstruction. It is a valid hereditary lower bound even though the full matrix's ordinary discrepancy is zero.

Exercise. Does a positive minor determinant force positive ordinary discrepancy of the full matrix? Hint: use the duplicated columns. Solution: no. Our full matrix contains the minor $B_0$ but has discrepancy zero; the determinant theorem concerns the maximum discrepancy over restrictions.

52.8 Geometric discrepancy

Optional extension; not required to complete the chapter foundation.

In combinatorial geometric discrepancy, the elements are a finite set of points and the tests are geometric ranges, such as intervals, halfspaces, or boxes. A coloring minimizes the largest signed point count inside any allowed range. The range family must be specified: a theorem about intervals does not automatically cover all rectangles in higher dimensions.

Solved one-dimensional example. Put four points at $1/8,3/8,5/8,7/8$ on the line and color them $+1,-1,+1,-1$ in that order. An interval selects a consecutive block of points. The alternating sum over such a block is zero when its length is even and plus or minus one when odd. Thus interval discrepancy is at most one. A range isolating one point gives a lower bound one, proving the exact optimum.

A different notion compares an uncolored empirical distribution with a reference measure. For points $x_1,\ldots,x_n$ in $[0,1]$, normalized one-dimensional star discrepancy is

$$D_n^{\ast}=\sup_{0\le u\le1}\left|\frac1n\#\{i:x_i\lt u\}-u\right|.$$

Here the reference is Lebesgue measure and the ranges are anchored half-open intervals $[0,u)$. There are no plus/minus signs. For midpoint points $x_i=(2i-1)/(2n)$, the empirical step function differs from $u$ by at most $1/(2n)$, with that value attained or approached at sample jumps. Hence $D_n^{\ast}=1/(2n)$, equal to $1/8$ for our four points. A jump of height $1/n$ also shows no configuration can have a smaller supremum than $1/(2n)$ in this one-dimensional setting.

These examples link balanced subsampling with numerical integration: interval count error controls distribution-function error, while integration error requires conditions on the integrand and the range notion. They do not assert an integration guarantee for arbitrary functions solely from a finite sign bound.

Exercise. Keep only the two positively colored points $1/8,5/8$. Are they as uniformly distributed as the original four midpoints? Hint: inspect the empirical jump near $1/8$. Solution: no. Their normalized star discrepancy is $3/8$, compared with $1/8$ originally. A coloring bound and an uncolored discrepancy bound have different normalization and objectives.

For broader geometric methods, the classical vector-body theorem in Banaszczyk provides one functional-analytic tool. Scope: the exact interval and midpoint bounds above are proved directly; multidimensional box discrepancy and integration inequalities are outside this proof.

52.9 Algorithmic discrepancy minimization

Optional extension; not required to complete the chapter foundation.

An existence theorem and an algorithm require different information. Given an explicit $m\times n$ matrix, exhaustive search evaluates all $2^n$ sign vectors and returns the one with least infinity norm. A straightforward implementation uses $O(mn2^n)$ arithmetic operations and stores the current best sign vector and row sums. For rational entries, bit complexity also depends on the encoded denominators and intermediate arithmetic.

Solved finite audit. Exhaustive evaluation of the running matrix's sixty-four colorings gives discrepancy histogram: eight colorings at zero, thirty-six at two, and twenty at four. The minimum zero agrees with the paired-column proof. This enumeration is a certificate only when every candidate and its objective are evaluated correctly; merely finding one zero coloring already proves optimality because discrepancy cannot be negative.

The floating-variable proof of Section 52.3 is constructive on rational incidence matrices. At each stage, solve the homogeneous equations of retained rows, move to the next cube boundary, freeze reached coordinates, and update active counts. At most $n$ moves occur. Exact rational linear algebra supplies a finite algorithm with polynomial bit complexity using standard elimination and suitable encodings; the nullspace direction and endpoint step must be calculated rather than guessed. It guarantees the classical bound, not an exact optimum.

On our example the direction $(1,1,0,-1,-1,0)$ freezes four variables at once. For the final two coordinates, choosing opposite signs produces zero; arbitrary signs still obey the bound. The explicit row-sum check is cheap and should accompany any claimed output. A heuristic that reduces the largest current row sum can be useful experimentally, but without a proof it does not inherit Spencer's or Banaszczyk's guarantee.

Lovett and Meka's edge-walk algorithm gives a constructive partial-coloring approach in the Spencer regime. Bansal, Dadush, Garg, and Lovett's Gram–Schmidt walk supplies algorithmic vector balancing with subgaussian control. Omitted prerequisites: the walk analyses, semidefinite or geometric invariants, and their full running-time guarantees. Our direct floating routine is not a substitute implementation for those algorithms.

As a dated update, Guo, Fang, and Lu's September 2026 algorithmic preprint reports polynomial-time constant Komlós discrepancy for unit Euclidean columns. It supplies an algorithmic result distinct from their earlier existential proof. The chapter's finite exhaustive checks do not independently validate that general algorithm or its full analysis.

Exercise. Does random sampling of one thousand colorings prove a nonzero lower bound for discrepancy? Hint: consider an untested coloring. Solution: no. A good tested coloring proves an upper bound; a lower bound must cover every coloring by proof or exhaustive verified enumeration.

52.10 Open problems in discrepancy and vector balancing

Optional extension; not required to complete the chapter foundation.

Status checked on 13 October 2026. The historical Komlós conjecture asked whether unit Euclidean columns always admit signs with a dimension-independent constant infinity-norm bound. The historical Beck–Fiala conjecture asked for $O(\sqrt t)$ discrepancy when each element belongs to at most $t$ sets. It would be outdated to present these unchanged as still unresolved: September 2026 primary preprints report proofs, followed by independent expositions.

Guo, Fang, and Lu, Vector Balancing via Directional Total Variation, submitted 10 September 2026, reports $\operatorname{disc}(M)\lt3\sqrt{2\pi}$ whenever every column has Euclidean norm at most one. Its incidence corollary is $\operatorname{disc}(A)\lt3\sqrt{2\pi t}$. Karingula and Lovett give an independent elementary exposition with constant thirty-six. These are recent preprint results; the cited records do not establish journal refereeing. The constant $3\sqrt{2\pi}$ is a reported valid upper bound, not a claim that it is the smallest possible constant.

Solved implication. For a degree-$t$ incidence matrix, each column of $A/\sqrt t$ has squared Euclidean norm at most one. A universal constant bound $C$ for those normalized columns immediately gives $\operatorname{disc}(A)\le C\sqrt t$. This proves the logical implication from Komlós-type vector balancing to the Beck–Fiala square-root scale. It uses the same signs and rescales only the test vector; it does not require counting rows or changing the set system.

Proof sketch and omitted prerequisites for the reported result. The directional-variation framework propagates suitable probability densities through convex-body transforms, retaining feasible sign choices. Its analytic stability lemma is the difficult step. That lemma and the infinite-dimensional functional arguments are omitted; neither our six-column cancellation nor the Gaussian cube calculation proves the new universal theorem.

One sharper research question is to determine the optimal universal constant

$$C_{\mathrm{opt}}=\sup_{m,n}\ \sup_{\|M_{\cdot j}\|_2\le1}\operatorname{disc}(M).$$

The cited upper proof does not claim optimality. Kunisky's published construction gives matrices whose discrepancies approach $1+\sqrt2$, providing a lower bound for this constant. The simple normalized triangle $B_0/\sqrt2$ gives only $\sqrt2$, a smaller illustrative lower bound. The cited lower and upper constructions leave a gap; this is a sharper-constant question rather than the historical question of whether any finite universal constant exists. No claim that the displayed upper constant is the newest or strongest available refinement is needed here.

Another distinction is online versus offline balance. Offline signs may depend on the entire matrix. An online rule must choose a sign before seeing future columns, often with bounds on every prefix. A theorem about the final offline sum does not supply that prefix guarantee. The dated Altschuler–Tikhomirov online preprint treats specified sparsity ranges and an input model; its hypotheses cannot be erased by quoting an offline result. These are directions for reading and precise finite experiments, not assertions that every associated problem is open.

Exercise. Does the normalized triangle disprove a universal constant-one Komlós bound? Hint: compute its exact discrepancy. Solution: yes. Each column of $B_0/\sqrt2$ has Euclidean norm one, but its discrepancy is $2/\sqrt2=\sqrt2\gt1$. It does not disprove the existence of a larger universal constant.

Construct a partial coloring and compare proven discrepancy bounds

The investigation combines an explicit incidence certificate, a partial-coloring construction, and a comparison of theorem hypotheses. It also shows why a modern status check matters: classical tools remain useful even when a conjecture they motivated has a newly reported solution.

A relevant application is splitting a collection of records or tasks between two batches while controlling imbalance across overlapping categories. Incidence discrepancy bounds signed category-count error. Weighted categories require a real matrix and its own norm assumptions; requiring both batches to have equal total size adds a row for the entire ground set. That extra row changes the matrix parameters and must be counted before applying a theorem.