Algebraic aspects of the polynomial Littlewood-Offord problem
Preprint
Abstract
Consider a degree-$d$ polynomial $f(ξ_1,\dots,ξ_n)$ of independent Rademacher random variables $ξ_1,\dots,ξ_n$. To what extent can $f(ξ_1,\dots,ξ_n)$ concentrate on a single point? This is the so-called polynomial Littlewood-Offord problem. A nearly optimal bound was proved by Meka, Nguyen and Vu: the point probabilities are always at most about $1/\sqrt n$, unless $f$ is "close to the zero polynomial" (having only $o(n^d)$ nonzero coefficients). In this paper we prove several results supporting the general philosophy that the Meka-Nguyen-Vu bound can be significantly improved unless $f$ is "close to a polynomial with special algebraic structure", drawing some comparisons to phenomena in analytic number theory. In particular, one of our results is a corrected version of a conjecture of Costello on multilinear forms (in an appendix with Ashwin Sah and Mehtaab Sawhney, we disprove Costello's original conjecture).
Keywords
All Related Versions
This publication has 32 references indexed in Scilit:
- Polynomial bound for partition rank in terms of analytic rankGeometric and Functional Analysis, 2019
- The correct exponent for the Gotsman–Linial Conjecturecomputational complexity, 2014
- Bilinear and quadratic variants on the Littlewood-Offord problemIsrael Journal of Mathematics, 2012
- Optimal inverse Littlewood–Offord theoremsAdvances in Mathematics, 2011
- A sharp inverse Littlewood-Offord theoremRandom Structures & Algorithms, 2010
- On a Lemma of Littlewood and Offord on the Distributions of Linear Combinations of Vectors*2009
- The Littlewood–Offord problem and invertibility of random matricesAdvances in Mathematics, 2008
- The rank of random graphsRandom Structures & Algorithms, 2008
- The density of integer points on homogeneous varietiesActa Mathematica, 1985
- Estimates for the concentration function of combinatorial number theory and probabilityPeriodica Mathematica Hungarica, 1977