Bilinear and quadratic variants on the Littlewood-Offord problem

被引:18
作者
Costello, Kevin P. [1 ]
机构
[1] Univ Calif Riverside, Dept Math, Riverside, CA 92521 USA
基金
美国国家科学基金会;
关键词
RANDOM SYMMETRIC-MATRICES; PROBABILITY; SINGULARITY; SUMS;
D O I
10.1007/s11856-012-0082-4
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
If f(x (1), aEuro broken vertical bar, x (n) ) is a polynomial dependent on a large number of independent Bernoulli random variables, what can be said about the maximum concentration of f on any single value? For linear polynomials, this reduces to one version of the classical Littlewood-Offord problem: Given nonzero constants a (1), aEuro broken vertical bar,a (n) , what is the maximum number of sums of the form +/- a (1) +/- a (2) +/- aEuro broken vertical bar +/- a (n) which take on any single value? Here we consider the case where f is either a bilinear form or a quadratic form. For the bilinear case, we show that the only forms having concentration significantly larger than n (-1) are those which are in a certain sense very close to being degenerate. For the quadratic case, we show that no form having many nonzero coefficients has concentration significantly larger than n (-1/2). In both cases the results are nearly tight.
引用
收藏
页码:359 / 394
页数:36
相关论文
共 20 条
[1]   On the singularity probability of discrete random matrices [J].
Bourgain, Jean ;
Vu, Van H. ;
Wood, Philip Matchett .
JOURNAL OF FUNCTIONAL ANALYSIS, 2010, 258 (02) :559-603
[2]   The rank of random graphs [J].
Costello, Kevin P. ;
Vu, Van H. .
RANDOM STRUCTURES & ALGORITHMS, 2008, 33 (03) :269-285
[3]   Random symmetric matrices are almost surely nonsingular [J].
Costello, Kevin P. ;
Tao, Terence ;
Vu, Van .
DUKE MATHEMATICAL JOURNAL, 2006, 135 (02) :395-413
[4]   (1,-1)-MATRICES WITH NEAR-EXTREMAL PROPERTIES [J].
de Launey, Warwick ;
Levin, David A. .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (03) :1422-1440
[5]  
Erdos P., 1945, AM MATH SOC B, V51, P898
[6]  
Halasz G., 1977, Period. Math. Hungar., V8, P197, DOI 10.1007/BF02018403
[8]   Combinatorial complexity of convex sequences [J].
Iosevich, A ;
Konyagin, S ;
Rudnev, M ;
Ten, V .
DISCRETE & COMPUTATIONAL GEOMETRY, 2006, 35 (01) :143-158
[9]   ON THE PROBABILITY THAT A RANDOM +/-1-MATRIX IS SINGULAR [J].
KAHN, J ;
KOMLOS, J ;
SZEMEREDI, E .
JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 1995, 8 (01) :223-240
[10]   ON A LEMMA OF LITTLEWOOD AND OFFORD ON DISTRIBUTION OF CERTAIN SUMS [J].
KLEITMAN, DJ .
MATHEMATISCHE ZEITSCHRIFT, 1965, 90 (04) :251-&