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

2019/09/04 by Kwan, Matthew, Sauermann, Lisa
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1909.02089

Abstract

Consider a quadratic polynomial f(ξ₁,…,ξ_n) 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/√(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.

Related

• Resolution of the quadratic Littlewood--Offord problem
• Algebraic aspects of the polynomial Littlewood-Offord problem
• Anti-concentration for polynomials of independent random variables
• A continuous variant of the inverse Littlewood-Offord problem for quadratic forms
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices