Quasi-random multilinear polynomials

DOI10.1007/S11856-018-1821-YzbMATH Open1454.26018arXiv1804.04828OpenAlexW2963514742WikidataQ105965884 ScholiaQ105965884MaRDI QIDQ2631886FDOQ2631886

Authors: Gil Kalai, Leonard J. Schulman 

Publication date: 16 May 2019

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

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.

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

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

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)

Cites Work

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

Cited In (5)

• 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
• Constants of the Kahane-Salem-Zygmund inequality asymptotically bounded by 1

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)