Optimal Inverse Littlewood-Offord theorems
Optimal Inverse Littlewood-Offord theorems
复制标题
最优逆 Littlewood-Offord 定理
DOI：
10.1016/j.aim.2011.01.005
复制
发表时间：
2010
影响因子：
1.7
通讯作者：
V. Vu
中科院分区：
文献类型：
--
作者：
H. Nguyen;V. Vu
设ηi，i= 1，.，n为iid Bernoulli随机变量，取值为±1，概率为12。给定一个n个整数v1，...，vn的多重集V，我们定义集中概率为：Littlewood-Offord和Erdens在20世纪40年代的一个经典结果断言，如果v不为零，那么ρ（V）是O（n−1/2）。从那时起，许多研究人员已经得到了改进的界限，假设各种额外的限制V。大约5年前，动机的问题，有关随机矩阵，陶和武介绍了逆Littlewood-Offord问题。在逆问题中，我们希望刻画集合V，假设ρ（V）相对较大。在本文中，我们介绍了一种新的方法来攻击反问题。作为一个应用，我们加强了以前的结果陶和Vu，获得V的最佳特征。这立即意味着几个经典定理，如Sárközy和Szemerédi和Halász。该方法也适用于连续设置，并导致一个简单的证明，β-网定理的陶和Vu，这在他们最近的研究中发挥了关键作用的随机矩阵。当V是无挠交换群的子集，η i是满足某些弱条件的独立变量时，所有结果都推广到了一般情况.
Let ηi, i=1,…,n, be iid Bernoulli random variables, taking values ±1 with probability 12. Given a multiset V of n integers v1,…,vn, we define the concentration probability as A classical result of Littlewood–Offord and Erdős from the 1940s asserts that, if the viare non-zero, then ρ(V) is O(n−1/2). Since then, many researchers have obtained improved bounds by assuming various extra restrictions on V. About 5 years ago, motivated by problems concerning random matrices, Tao and Vu introduced the inverse Littlewood–Offord problem. In the inverse problem, one would like to characterize the set V, given that ρ(V) is relatively large. In this paper, we introduce a new method to attack the inverse problem. As an application, we strengthen the previous result of Tao and Vu, obtaining an optimal characterization for V. This immediately implies several classical theorems, such as those of Sárközy and Szemerédi and Halász. The method also applies to the continuous setting and leads to a simple proof for the β-net theorem of Tao and Vu, which plays a key role in their recent studies of random matrices. All results extend to the general case when V is a subset of an abelian torsion-free group, and ηiare independent variables satisfying some weak conditions.