Quasi-random multilinear polynomials

DOI10.1007/S11856-018-1821-YMaRDI QIDQ2631886zbMATH OpenOpenAlexWikidataFDO

Authors Gil Kalai, Leonard J. Schulman

Publication date 16 May 2019

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.04828

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Polynomials and rational functions of one complex variable (30C10) Inequalities for trigonometric functions and polynomials (26D05) Combinatorial games (91A46)

Abstract: We consider multilinear Littlewood polynomials, polynomials in $n$ variables in which a specified set of monomials $U$ have $pm1$ coefficients, and all other coefficients are $0$. We provide upper and lower bounds (which are close for $U$ of degree below $logn$) on the minimum, over polynomials $h$ consistent with $U$, of the maximum of $|h|$ over $pm1$ assignments to the variables. (This is a variant of a question posed by Erd"os 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.

Recommendations

• Bilinear and quadratic variants on the Littlewood-Offord problem
• Concentration of multivariate polynomials and its applications
• On the concentration of multivariate polynomials with small expectation
• Quasi-random hypergraphs
• Random multilinear maps and the Erdős box problem

Cites work

• scientific article; zbMATH DE number 6679846 (Why is no real title available?)
• scientific article; zbMATH DE number 6508183 (Why is no real title available?)
• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• scientific article; zbMATH DE number 3781125 (Why is no real title available?)
• scientific article; zbMATH DE number 3539225 (Why is no real title available?)
• scientific article; zbMATH DE number 729736 (Why is no real title available?)
• scientific article; zbMATH DE number 2065328 (Why is no real title available?)
• scientific article; zbMATH DE number 3207686 (Why is no real title available?)
• scientific article; zbMATH DE number 3216393 (Why is no real title available?)
• scientific article; zbMATH DE number 3294856 (Why is no real title available?)
• An extremal problem for polynomials
• An inequality for the maximum of trigonometric polynomials
• Analysis of Boolean Functions
• Anti-concentration for polynomials of independent random variables
• Characteristic vectors of bordered matrices with infinite dimensions
• Computational excursions in analysis and number theory
• Distributional and \(L^q\) norm inequalities for polynomials over convex bodies in \(\mathbb{R}^n\)
• Explicit, almost optimal, epsilon-balanced codes
• Four decades of research on bent functions
• Hypergraphs, quasi-randomness, and conditions for regularity
• Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces
• Large networks and graph limits
• Majorizing measures: The generic chaining
• Martingales and stochastic integrals. I
• Minimization of ±1 matrices under line shifts
• On Bernstein's inequality and Kahane's ultraflat polynomials
• On ``bent functions
• On extensions of the Gale-Berlekamp switching problem and constants of \(\ell_p\)-spaces
• On the Fourier tails of bounded functions over the discrete cube
• On universality of graphs with uniformly distributed edges
• Pseudo-random graphs
• Pseudo-random hypergraphs
• Quasi-random graphs
• Quasi-random hypergraphs
• Quasi‐random classes of hypergraphs
• Some Theorems on Fourier Coefficients
• Some unsolved problems
• Statistical mechanics.
• Sur Les Polynomes a Coefficients Unimodulaires
• Szemerédi's partition and quasirandomness
• The Fourth Moment Method
• The number of submatrices of a given type in a Hadamard matrix and related results
• The solution to Berlekamp's switching game
• Weak quasi-randomness for uniform hypergraphs
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)

Cited in

(5)

• Constants of the Kahane-Salem-Zygmund inequality asymptotically bounded by 1
• On pseudorandom numbers from multivariate polynomial systems
• An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
• Vector-valued Kahane-Salem-Zygmund inequalities with asymptotically bounded constants
• Random multilinear maps and the Erdős box problem

This page was built for publication: Quasi-random multilinear polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2631886)