An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs

Abstract

Consider a quadratic polynomial $f\left({\xi }_1,\dots ,{\xi }_n\right)$ of independent Bernoulli random variables. What can be said about the concentration of $f$ on any single value? This generalises the classical Littlewood--Offord problem, which asks the same question for linear polynomials. As in the linear case, it is known that the point probabilities of $f$ can be as large as about $1/\sqrt{n}$, but still poorly understood is the "inverse" question of characterising the algebraic and arithmetic features $f$ must have if it has point probabilities comparable to this bound. In this paper we prove some results of an algebraic flavour, showing that if $f$ has point probabilities much larger than $1/n$ then it must be close to a quadratic form with low rank. We also give an application to Ramsey graphs, asymptotically answering a question of Kwan, Sudakov and Tran.

References in corpus (4)

• Combinatorial anti-concentration inequalities, with applications
• A Completion of the Proof of the Edge-statistics Conjecture
• The edge-statistics conjecture for $\ell \ll k^{6/5}$
• A Local Limit Theorem for Cliques in G(n,p)

Cited by in corpus (1)

• Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture