The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi

2010/02/26 by Terence Tao, Van Vu, Tao, Terence +1
Mathematics · #11B30 #60G50 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics #math.CO #msc:11B30 #msc:60G50

paper · pdf · doi:10.48550/arxiv.1002.5028

8 pages, no figures. To appear, Combinatorica. This is the final version, incorporating the referee suggestions

openalex publication_date 2010/02/26 · arxiv created 2011/04/04 · arxiv updated 2011/04/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a new bound on the probability that the random sum ξ₁ v₁ +...+ ξ_n v_n belongs to a ball of fixed radius, where the ξ_i are iid Bernoulli random variables and the v_i are vectors in \R^d. As an application, we prove a conjecture of Frankl and Füredi (raised in 1988), which can be seen as the high dimensional version of the classical Littlewood-Offord-Erd\H os theorem.

Related

• The Littlewood-Offord Problem for Markov Chains
• Small ball probability, Inverse theorems, and applications
• Inverse Littlewood-Offord problems for Quasi-Norms
• A non-uniform Littlewood-Offord inequality
• A nonuniform Littlewood-Offord inequality for all norms