Quasi-random multilinear polynomials
- Creators
-
Kalai, Gil
-
Schulman, Leonard J.
Abstract
We consider multilinear Littlewood polynomials, polynomials in n variables in which a specified set of monomials U have ±1 coefficients, and all other coefficients are 0. We provide upper and lower bounds (which are close for U of degree below log n) on the minimum, over polynomials h consistent with U, of the maximum of |h| over ±1 assignments to the variables. (This is a variant of a question posed by Erdős regarding the maximum on the unit disk of univariate polynomials of given degree with unit coefficients.) We outline connections to the theory of quasi-random graphs and hypergraphs, and to statistical mechanics models. Our methods rely on the analysis of the Gale–Berlekamp game; on the constructive side of the generic chaining method; on a Khintchine-type inequality for polynomials of degree greater than 1; and on Bernstein's approximation theory inequality.
Additional Information
© 2018 Hebrew University of Jerusalem. Received January 9, 2018 and in revised form April 19, 2018. Part of this work was done while the authors were in residence at the Simons Institute for Theory of Computing, and part while the second author was in residence at the Israel Institute for Advanced Studies, supported by a EURIAS Senior Fellowship co-funded by the Marie Skłodowska-Curie Actions under the 7th Framework Programme. Work of the second author was also supported by United States NSF grant 1618795. Thanks to an anonymous referee for insightful comments which helped tighten our bounds.Additional details
- Eprint ID
- 92041
- Resolver ID
- CaltechAUTHORS:20190103-132542769
- European Institutes for Advanced Study (EURIAS)
- Marie Curie Fellowship
- CCF-1618795
- NSF
- Created
-
2019-01-03Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field