A sharp inverse Littlewood-Offord theorem

DOI10.1002/rsa.20327zbMath1205.60091arXiv0902.2357OpenAlexW3083309575MaRDI QIDQ3061186

Van H. Vu, Terence C. Tao

Publication date: 14 December 2010

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0902.2357

zbMATH Keywords

random walksinverse theoremsadditive combinatoricsconcentration probabilityLittlewood-Offord problem

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Arithmetic combinatorics; higher degree uniformity (11B30)

Related Items

Near invariance of the hypercube, Non-abelian Littlewood-Offord inequalities, Anticoncentration and the Exact Gap-Hamming Problem, Random matrices have simple spectrum, A non-uniform Littlewood-Offord inequality, Quantitative invertibility of random matrices: a combinatorial perspective, Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture, Inverse Littlewood-Offord problems and the singularity of random symmetric matrices, Complex random matrices have no real eigenvalues, Optimal inverse Littlewood-Offord theorems, Bilinear and quadratic variants on the Littlewood-Offord problem, Inverse Littlewood-Offord problems for quasi-norms, Random matrices: tail bounds for gaps between eigenvalues, Short Proofs of Some Extremal Results, Resilience for the Littlewood-Offord problem, New applications of Arak's inequalities to the Littlewood-Offord problem, Resilience for the Littlewood-Offord problem, Toward the history of the Saint St. Petersburg school of probability and statistics. I: Limit theorems for sums of independent random variables, An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs, Arak Inequalities for Concentration Functions and the Littlewood--Offord Problem, On the counting problem in inverse Littlewood–Offord theory, Geometric and o-minimal Littlewood-Offord problems, Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors

Cites Work

• Unnamed Item
• On the tightest packing of sums of vectors
• Optimal representations by sumsets and subset sums
• John-type theorems for generalized arithmetic progressions and iterated sumsets
• Solution of the Littlewood-Offord problem in high dimensions
• Finite addition theorems. I
• The Littlewood-Offord problem and invertibility of random matrices
• On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors
• On random ±1 matrices: Singularity and determinant
• On the singularity probability of random Bernoulli matrices
• RANDOM MATRICES: THE CIRCULAR LAW
• Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property
• On the Probability That a Random ± 1-Matrix Is Singular
• Long arithmetic progressions in sumsets: Thresholds and bounds