PaperlayerView exact revision on arXiv

Source-linked AI summary

Three Standard Deviations Suffice While One Does Not

Victor Reis, Zhao Song

arXiv:2609.34471v1math.COcs.DM

TL;DR

The paper studies matrix discrepancy, with particular interest in the square case. It uses a potential function and a modified Hadamard matrix to prove an upper bound and Bandeira’s conjecture.

  • Problem

    The paper studies discrepancy for matrices, with the square case singled out as particularly interesting.

    Source: §1 · p. 1

  • Method

    The paper minimizes a potential function for its upper-bound result and proves Bandeira’s conjecture by replacing a 2^-22 fraction of Hadamard-matrix columns with independent random signs.

    Source: §1 · p. 2, §1.1 · p. 3, §3.4 · p. 8

  • Results

    Theorem 1.2 gives a discrepancy bound of sqrt(3arsinh(10))sqrt(n)+4, and the paper also proves Bandeira’s conjecture.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The upper-bound result applies to every matrix in any dimension and for any number of vectors.

    Source: §1 · p. 2

    The result is existential rather than polynomial-time because the authors do not provide an algorithm to minimize the potential.

    Source: §3 · p. 6

Abstract

from arXiv · show

Spencer's 1985 ``six standard deviations suffice'' theorem shows that every $A \in [-1,1]^{n \times n}$ has a sign vector $x \in \{-1,1\}^n$ with $\|Ax\|_\infty \le 6\sqrt{n}$. We show the upper bound $\sqrt{3\operatorname{arsinh}(10)}\sqrt{n}+4 < 2.9992 \sqrt{n} + 4$ by directly rounding the minimizer of a potential function to a vertex of the cube. We also show that, for every power of two $n \ge 2^{50}$, there exists a matrix $A \in \{-1,1\}^{n \times n}$ such that $\|Ax\|_\infty >1.0000002\sqrt{n}$ for every choice of signs $x \in \{-1,1\}^n$. The construction simply replaces a $2^{-22}$ fraction of the columns of a Hadamard matrix with independent random sign vectors. This is the first improvement over the $\sqrt{n}$ lower bound of Olson and Spencer (1978), which uses a Hadamard matrix.

1 Introduction

The introduction presents a random-column replacement of a Hadamard matrix as a lower-bound construction and a potential-based rounding argument for an upper bound. Its proof overview explains how the two approaches establish their respective bounds.

1 Introduction

  • For powers of two n ≥ 250, Theorem 1.1 considers replacing any fixed set of δn columns of an n×n Hadamard matrix with independent random signs.The proof overview concludes that, with high probability, no sign vector achieves small discrepancy.Source: §1 · p. 2, §1.1 · p. 3

1.1 Proof overview

  • For the lower-bound proof, orthogonality fixes ||Hu||₂², while concentration and a compensation bound make small discrepancy unlikely.The argument separates signings by whether ||Hu||₁ exceeds 0.99n^(3/2), then combines the two cases.Source: §1.1 · pp. 2–3
  • Rounding z to its nearest sign vector changes Az by at most R(z), so the proof seeks R(z) = 4 before rounding.The potential is defined using s(z) = R(z) − 4 and row-gap penalties.Source: §1.1 · p. 3
  • The upper-bound proof minimizes a potential on a compact set, using a barrier that diverges at row thresholds and decays for distant rows.A minimizer with R(z) > 4 would yield a direction along which the potential has negative second derivative.Source: §1.1 · p. 3

2 Proof of the lower bound

The proof combines concentration and random-sign tail bounds with a split of the matrix into unchanged Hadamard columns and independent random-sign columns. It bounds the bad-event probability by treating most sign vectors separately from an exceptional set.

2.1 Preliminaries

  • Talagrand’s concentration inequality is used to control the tail of the ℓ1 norm ∥Hε∥1.The proof applies the inequality to a closed convex set defined by a bound on ∥Hu∥1, together with Markov’s inequality.Source: §2.1 · p. 3, §2.2 · p. 4
  • Tail bounds for sums of independent random signs and for binomial noise S_δn are established for later use.The cited text notes that the estimates for random-sign sums are proved in Appendix A, while the binomial-noise bounds follow from Lemma 2.2(d).Source: §2.1 · pp. 3–4
  • For ∥z∥1 ≤ 0.99n^3/2, the upper bound improves to 2^-3n.This is the stronger bound used when ∥Hu∥1 ≤ 0.99n^3/2.Source: §2.1 · p. 4, §2.2 · p. 4

2.2 Proof of Theorem 1.1

  • The matrix uses H for the unchanged Hadamard columns and R for δn independent random-sign columns.For x = (u,v), Ax = Hu + Rv, and ∥Hu∥2^2 = (1−δ)n^2.Source: §2.2 · p. 4
  • For each sign vector x, the proof bounds the probability of the bad event ∥Ax∥∞ ≤ (1+δ)pn using the binomial-noise estimates.When ∥Hu∥1 ≤ 0.99n^3/2, it uses the stronger probability bound 2^-3n; the proof also bounds the exceptional set of u and sums over the resulting cases.Source: §2.2 · p. 4

3 Proof of the upper bound

The proof establishes an upper bound by minimizing a potential over a constrained subset of the cube, then rounding a minimizer to a sign vector. Scalar estimates, a capped trace bound, and a second-derivative argument establish the needed minimizer properties.

3 Proof of the upper bound

  • For n ≥ 108, Theorem 3.1’s upper bound is less than 3√n.The theorem applies to every A ∈ [−1,1]^(d×n).Source: §3 · p. 5
  • The minimization result is existential rather than polynomial-time: the paper gives conceptual pseudocode but no algorithm to minimize Φ.The authors believe an efficient implementation is possible.Source: §3 · p. 6

3.1 Scalar inequalities

  • The scalar estimates establish that φ is positive, decreasing, and convex, diverges at zero, and has φ(c) = 1/2; ψ is positive.The proof also uses the stated monotonicity property of a scalar function in part (d).Source: §3.1 · pp. 6–7

3.2 Capped trace bound

  • The capped trace lemma converts a lower bound on a weighted quadratic form into an upper bound on the dimension of a subspace.Capped weights permit applying the scalar inequality in Lemma 3.3(c).Source: §3.2 · p. 7

3.3 Second derivative formula

  • At a minimizer, nonnegative second derivatives along directions orthogonal to z yield the quadratic inequality needed for the capped trace lemma.The second-derivative formula is for directions in the stated open set U.Source: §3.3 · pp. 7–8

3.4 Proof of Theorem 1.2

  • The potential attains a finite minimum on K, and every minimizer satisfies ||Az||∞ ≤ ∆ and R(z) = 4.The proof rules out R(z) > 4 by contradiction using a direction with an incompatible second derivative.Source: §3.4 · pp. 8–9
  • The proof rounds a point with R(z) = 4 to its nearest sign vector, with rounding changing Az by at most R(z) in ℓ∞.Here R(z) := n − ||z||₂²; the potential minimization produces a point with ||Az||∞ ≤ ∆ and R(z) = 4.Source: §3 · p. 5, §3.4 · pp. 8–9

A Proof of Lemma 2.2

The appendix proves Lemma 2.2 using binomial probabilities and scalar comparisons. Its steps establish probability estimates for sums of independent signs.

A Proof of Lemma 2.2

  • The proof derives integral identities by recurrence and uses that I_k decreases to obtain the stated estimate in Eq. (16).The recurrence is I_r = (r − 1)I_(r−2)/r for r ≥ 2.Source: A Proof of Lemma 2.2 · p. 11
  • A sum of k independent signs equals 2r − k when exactly r signs are positive, giving the corresponding binomial probability.The proof uses the central probability β_k in its subsequent estimates.Source: A Proof of Lemma 2.2 · pp. 11–12
  • For the binomial tail estimates, the proof compares successive partial sums using monotonicity and bounds their ratios with Eq. (17).The ratio argument covers j < k/2; for k = 2, the range is empty and Eq. (19) suffices.Source: A Proof of Lemma 2.2 · pp. 12–13
  • The proof treats three ranges of u and combines the intermediate-range estimates to establish part (d).The intermediate case combines Eqs. (25) and (26).Source: A Proof of Lemma 2.2 · p. 13

B Proof of Lemma 2.3

The proof handles two cases for the vector z, applying Lemma 2.2(d) to independent symmetric signs. The second case adds a bound on ||z||₁ and separates coordinates exceeding √n.

B Proof of Lemma 2.3

  • For each coordinate, the proof assumes ||z + Y||∞ ≤ (1 + δ)√n and applies Lemma 2.2(d) with u = |z_i|/√n.The sign-adjusted variables s_iY_i are independent copies of Y_1.Source: B Proof of Lemma 2.3 · pp. 13–14
  • In the proof of (b), the additional condition is ∥z∥1 ≤ 0.99n3/2, and I is defined as the set of indices i satisfying |zi| > pn.Source: B Proof of Lemma 2.3 · p. 14
  • For indices in I, the proof again applies Lemma 2.2(d), using independence and symmetry as in the first case.The resulting estimate uses the split at |z_i| = √n.Source: B Proof of Lemma 2.3 · p. 14

C Scalar calculations for the upper bound

The appendix verifies the scalar properties used in the upper-bound proof. It establishes positivity and convexity properties directly and reduces a capped inequality to a scalar comparison.

C Scalar calculations for the upper bound

Loading 2609.34471v1…