On a lemma of Littlewood and Offord

By P. Erdös. 1945

Remark. Choose Xi = l, n even. Then the interval ( — 1, + 1 ) contains Cn,m s u m s ^ i e ^ , which shows that our theorem is best possible. We clearly can assume that all the Xi are not less than 1. To every sum ]Qfc=ifcfc w e associate a subset of the integers from 1 to n as follows: k belongs to the subset if and only if e&= + 1 . If two sums 2^J»i€^jb and ]Cfc=i*& #& are both in 7, neither of the corresponding subsets can contain the other, for otherwise their difference would clearly be not less than 2. Now a theorem of Sperner states that in any collection of subsets of n elements such that of every pair of subsets neither contains the other, the number of sets is not greater than Cn,m, and this completes the proof. An analogous theorem probably holds if the Xi are complex numbers, or perhaps even vectors in Hubert space (possibly even in a Banach space). Thus we can formulate the following conjecture.

Subfields: Pure Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Pure Mathematics

Citations in the corpus

Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, positive): “small ball probability theorem, or anti-concentration for sum of Bernoulli variables, see [30]), we know Pr |∑ j∈Λ w j · zj − r| ≤ t ∣∣ E  ≤ O(√kt+ 1 √ |Λ′| ) = O( √ kt+ 1 √ |Λ|k/d )”
Anti-concentration for Polynomials of Independent Random Variables (2015, methodology): “Consider the Erdős-Rényi random graph G(N, p).”
Random matrices: tail bounds for gaps between eigenvalues (2015, unknown): “2 [10,17,25,31] Let ε > 0 be fixed, let δ > 0, and let v ∈ Rm be a unit vector with ρδ(v) ≥ m− 1 2+ε.”
Hardness of Learning Halfspaces with Noise (2006, background): “The following Lemma is well-known in probability as the ‘Littlewood-Offord Problem’[14] (see Theorem 11.”
Optimal Inverse Littlewood-Offord theorems (2010, background): “The first such result was discovered by Erdős and Moser [2], who showed that if vi are distinct, then ρ(V ) = O(n −3/2 log n).”
On the singularity probability of random Bernoulli matrices (2005, background): “But by Erdös’s Littlewood-Offord inequality (see [5]) this forces at most n/2 (say) of the coefficients a1, .”
RANDOM MATRICES: THE CIRCULAR LAW (2007, background): “A classical theorem of Littlewood and Offord [17] (see also [6]) shows that if x is Bernoulli, and all |vi| ≥ 1, then p1,x(v) = O(n−1/2).”
Non-asymptotic theory of random matrices: extreme singular values (2010, methodology): “For example, if all |ai| ≥ 1 then L(S, 1) ≤ Cn−1/2 [52, 21], which agrees with (4.”
The Elliptic Law (2012, background): “A classical result of Erdős [10] and Littlewood-Offord [28] in the 1940s asserts that if ai are complex numbers of magnitude |ai| ≥ 1, then the probability that the linear form ∑n i=1 aixi concentrates on a disk of radius one is of order O(n−1/2), where xi are i.”
Adjacency matrices of random digraphs: singularity and anti-concentration (2015, methodology): “In its classical form, established by Erdős [13], the Littlewood-Offord inequality states that for every fixed z ∈ R, a fixed vector a = (a1, a2, . . . , an) ∈ Rn with non-zero coordinates, and for independent random signs rk, k ≤ n, the probability P { ∑n k=1 rkak = z} is bounded from above by n−1”
On the singularity of adjacency matrices for random regular digraphs (2014, unknown): “1 (Anti-concentration for random walks [16]).”
Small Ball Probability, Inverse Theorems, and Applications (2012, background): “(of Theorem 1.2) Erdős’ proof made an ingenious use of Sperner’s lemma, which asserts that if F is an anti-chain on a set of n elements, then F has at most ( n bn/2c ) elements (an anti-chain is a family of subsets none of which contains the other).”
Inverse Littlewood-Offord problems and The Singularity of Random Symmetric Matrices (2011, background): “One direction of research was to generalize Erdős’ result to other groups.”
The Littlewood-Offord problem and invertibility of random matrices (2007, background): “The classical result of Littlewood and Offord strengthened by Erdös [7] states that if all |ak| ! 1 then for the random sign-sums one has p1(a) # n−1/2.”