Probability Seminar

Lisa SauermannStanford University
An algebraic inverse theorem for the quadratic Littlewood-Offord problem

Monday, October 28, 2019 - 4:00pm
Malott 406

Consider a quadratic polynomial f in n variables. Furthermore, consider independent Rademacher random variables xi_1,...,xi_n (this means that Pr(xi_i=1)=Pr(xi_i=-1)=1/2 for each i). How large can the concentration probabilities Pr(f(xi_1,...,xi_n)=x) on any single value x be? This is a variant of the classical Littlewood-Offord problem, which asks the same question for a linear polynomial f. As in the linear case, it is known that the point probabilities Pr(f(xi_1,...,xi_n)=x) can be as large as about 1/\sqrt{n}. However, for a generic polynomial f with, say, bounded integer coefficients, one would expect the maximum point probabilities to be roughly 1/n.

In this talk, we discuss an inverse theorem for this problem. More specifically, we show that if f has some point probability larger than n^{-1+o(1)}, then f must be close to a quadratic form of bounded rank. For the linear Littlewood-Offord problem there has been an intensive line of research on inverse theorems, with important applications to random matrix theory. Similarly, results on the quadratic Littlewood-Offord problem have had applications to the theory of random symmetric matrices.

Joint work with Matthew Kwan.