Optimal inverse Littlewood-Offord theorems

DOI10.1016/j.aim.2011.01.005zbMath1268.11020arXiv1004.3967OpenAlexW2001765932MaRDI QIDQ633617

Van H. Vu, Hoi H. Nguyen

Publication date: 29 March 2011

Published in: Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

concentration probabilitygeneralized arithmetic progressioninverse Littlewood-Offord problem

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Combinatorial probability (60C05) Arithmetic progressions (11B25) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Arithmetic combinatorics; higher degree uniformity (11B30)

Related Items

Random walks with different directions ⋮ On the Littlewood-Offord problem ⋮ Near invariance of the hypercube ⋮ Arak's inequalities for concentration functions and the Littlewood-Offord problem ⋮ Non-abelian Littlewood-Offord inequalities ⋮ Real roots of random polynomials: expectation and repulsion ⋮ Singularity of random symmetric matrices revisited ⋮ Random matrices have simple spectrum ⋮ A non-uniform Littlewood-Offord inequality ⋮ Monochromatic Hilbert cubes and arithmetic progressions ⋮ 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 ⋮ A new approach to an old problem of Erdős and Moser ⋮ Multiplicative structures and random walks in o-minimal groups ⋮ Multivariate estimates for the concentration functions of weighted sums of independent, identically distributed random variables ⋮ Random doubly stochastic matrices: the circular law ⋮ A necessary and sufficient condition for convergence of the zeros of random polynomials ⋮ A bound for the maximal probability in the Littlewood-Offord problem ⋮ Inverse Littlewood-Offord problems for quasi-norms ⋮ Anticoncentration versus the Number of Subset Sums ⋮ Random matrices: tail bounds for gaps between eigenvalues ⋮ Short Proofs of Some Extremal Results ⋮ A nonuniform Littlewood-Offord inequality for all norms ⋮ Resilience for the Littlewood-Offord problem ⋮ New applications of Arak's inequalities to the Littlewood-Offord problem ⋮ Sparse random matrices have simple spectrum ⋮ Asymptotic zero distribution of random orthogonal polynomials ⋮ SINGULARITY OF RANDOM SYMMETRIC MATRICES—A COMBINATORIAL APPROACH TO IMPROVED BOUNDS ⋮ 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 ⋮ On the singularity of random symmetric matrices ⋮ Convergence and asymptotic approximations to universal distributions in probability ⋮ Arak Inequalities for Concentration Functions and the Littlewood--Offord Problem ⋮ Entropy Inequalities for Sums in Prime Cyclic Groups ⋮ Some new results in random matrices over finite fields ⋮ On the counting problem in inverse Littlewood–Offord theory ⋮ Geometric and o-minimal Littlewood-Offord problems ⋮ The strong circular law: A combinatorial view ⋮ On the concentration of random multilinear forms and the universality of random block matrices ⋮ Roots of random functions: A framework for local universality ⋮ Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors ⋮ Random symmetric matrices: rank distribution and irreducibility of the characteristic polynomial ⋮ Random integral matrices: universality of surjectivity and the cokernel

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• John-type theorems for generalized arithmetic progressions and iterated sumsets
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• The Littlewood-Offord problem and invertibility of random matrices
• A sharp inverse Littlewood-Offord theorem
• Smooth analysis of the condition number and the least singular value
• On the singularity probability of random Bernoulli matrices
• RANDOM MATRICES: THE CIRCULAR LAW
• Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property
• Estimates for the concentration function of combinatorial number theory and probability
• Solution of Two Difficult Combinatorial Problems with Linear Algebra
• Freiman's theorem for solvable groups
• From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices
• Über ein Problem von Erdös und Moser
• Long arithmetic progressions in sumsets: Thresholds and bounds
• On a lemma of Littlewood and Offord