Bilinear and Quadratic variants on the Littlewood-Offord Lemma

Combinatorics Seminar
Friday, August 29, 2008 - 15:00
1 hour (actually 50 minutes)
Skiles 255
School of Mathematics, Georgia Tech
Let f be a polynomial or multilinear form in a large number of variables. A basic question we can ask about f is how dispersed it becomes as the number of variables increases. To be more concrete: If we randomly (and independently) set each entry to be either 1 or -1, what is the largest concentration of the output of f on any single value, assuming all (or most) of the coefficients of f are nonzero? Can we somehow describe the structure of those forms which are close to having maximal concentration? If f is a linear polynomial, this is a question originally examined by Littlewood and Offord and answered by Erdos: The maximal concentration occurs when all the nonzero coefficients of f are equal. Here we will consider the case where f is a bilinear or quadratic form.