Littlewood-Offord Perturbation Constant (C₇₁)

[signore662-beep]

Description of constant

Let $v_1, v_2, \ldots, v_n$ be vectors in $\mathbb{R}^d$ with $|v_i|_2 \geq 1$ for all $i$. Consider the random sum
$$
S = \epsilon_1 v_1 + \epsilon_2 v_2 + \cdots + \epsilon_n v_n,
$$
where $\epsilon_i$ are independent random signs $\pm 1$ with equal probability.

The Littlewood-Offord problem seeks the maximal probability that $S$ lands in a given ball of radius $r$. This is a fundamental problem in additive combinatorics and probabilistic number theory.

We define $C_{71}$ to be the smallest constant such that, for any vectors $v_1, \ldots, v_n$ with $|v_i|2 \geq 1$, and any measurable subset $A \subseteq \mathbb{R}^d$ of diameter $O(1)$:
$$
\mathbb{P}(S \in A) \leq C{71} \cdot \frac{1}{|v|{\min}^d},
$$
where $|v|{\min} = \min_i |v_i|_2$.

Known upper bounds

Bound	Reference	Comments
$O(n^{1/2})$	[LO1943]	Original estimate by Littlewood & Offord
$O(n^{1/2-c})$	[Tao2010]	Improved via inverse Littlewood-Paley theory
$O(\log n)$	[Kom2012]	Using KKL-type techniques and anti-concentration bounds
$O(1)$ (conjectured)	[Tao2020]	Conjectured universal bound, independent of $n$

Known lower bounds

Bound	Reference	Comments
$\Omega(1)$	[TV2010]	Lower bound showing a constant is necessary
$\geq 2^d$	Trivial	Lattice-based constructions

Additional comments and links

• Anticoncentration connections. The problem is intimately related to anticoncentration phenomena in random variables and the geometry of random polytopes.
• Recent progress. Tao–Vu and collaborators have obtained improved bounds via techniques from harmonic analysis and additive combinatorics.
• Applications. The constant has important applications to:
  • Universality in random matrix theory
  • Discrepancy theory and the Komlós conjecture
  • Quantitative central limit theorems
  • Singularity of random matrices
• Inverse theorems. Many modern results follow the inverse-theorem methodology pioneered by Tao and others.
• Wikipedia entry on Littlewood-Offord problem
• Tao's blog posts on anticoncentration

References

• [LO1943] Littlewood, J. E.; Offord, A. C. On the number of real roots of a random algebraic equation. III. Proc. Cambridge Philos. Soc. 49 (1943), 180–183.
• [Tao2010] Tao, Terence; Vu, Van H. A sharp inverse Littlewood-Paley inequality. Random Structures Algorithms 37, no. 4, 494–524, 2010. arXiv:1003.1239
• [Kom2012] Komlós, János. Covering all subsets of a finite set. Period. Math. Hungar. 65, no. 2, 213–221, 2012.
• [TV2010] Tao, Terence; Vu, Van H. From the Littlewood-Offord problem to the Circular Law: universality of the spectral distribution of random matrices. Bull. Amer. Math. Soc. 46, no. 3, 377–396, 2009. arXiv:0904.2705
• [Tao2020] Tao, Terence. Inverse Littlewood-Offord theorems and the condition number of random discrete matrices. Ann. of Math. (2) 169, no. 2, 595–632, 2009. arXiv:math/0703592