OctoInformBeta

Real ultraflat Littlewood polynomials and unbounded binary merit factors

A Littlewood polynomial of length NN is a polynomial P(z)=∑k=0N−1εkzkP(z)=\sum_{k=0}^{N-1}\varepsilon_kz^k whose coefficients εk\varepsilon_k all lie in {−1,1}\{-1,1\}. Its maximum modulus is ∥P∥∞=max⁡|z|=1|P(z)|\|P\|_\infty=\max_{|z|=1}|P(z)|. Let mNm_N be the least value of ∥P∥∞/N\|P\|_\infty/\sqrt N over the Littlewood polynomials PP of length NN. Parseval’s identity gives mN≥1m_N\ge1 for every NN. The real-sign analogue of a question of Erdős asks whether there is an absolute constant c>0c>0 with mN≥1+cm_N\ge1+c for all large NN.

Erdős’s original question allows complex coefficients of modulus one. With such coefficients, Littlewood built polynomials from quadratic phases near the scale N\sqrt N. A sequence of polynomials PNP_N, of length NN and with coefficients of modulus one, is ultraflat when |PN(z)|/N|P_N(z)|/\sqrt N tends to 11 uniformly on |z|=1|z|=1. Kahane constructed ultraflat polynomials. They answer the original question in the negative. Bombieri and Bourgain gave quantitative constructions of ultraflat polynomials. For real signs, the polynomials found by Shapiro and independently by Rudin are Littlewood polynomials. Their maximum modulus is O(N)O(\sqrt N). When NN is a power of two, their maximum modulus is at most 2N\sqrt{2N}. Balister proved that, at every length NN, the polynomial formed by the first NN coefficients of a longer polynomial of Shapiro and Rudin has maximum modulus at most 6N−2−1\sqrt{6N-2}-1. Balister, Bollobás, Morris, Sahasrabudhe and Tiba constructed Littlewood polynomials whose modulus lies between two fixed positive multiples of N\sqrt N on the whole unit circle. Erdélyi proved that every Littlewood polynomial PP of length NN has ∥P∥∞2≥N+(N−1)1/3/38\|P\|_\infty^2\ge N+(N-1)^{1/3}/38. Georgiev, Gómez-Serrano, Tao and Wagner searched numerically for the real-sign minimum at degrees up to 100100.

The main theorem of the preprint, Theorem 1.1, is that mNm_N tends to 11 as NN tends to infinity through all integers. The real-sign analogue of Erdős’s question therefore has a negative answer. The merit factor of a word a=(a0,…,aN−1)a=(a_0,\dots,a_{N-1}) in {−1,1}N\{-1,1\}^N is N2/(2∑u=1N−1Cu2)N^2/\bigl(2\sum_{u=1}^{N-1}C_u^2\bigr), where Cu=∑k=0N−1−uakak+uC_u=\sum_{k=0}^{N-1-u}a_ka_{k+u}. Turyn’s conjecture asserts that the merit factor is bounded by an absolute constant. From Theorem 1.1 the preprint also derives that the largest merit factor of a word in {−1,1}N\{-1,1\}^N tends to infinity, disproving Turyn’s conjecture, a consequence the Lean library does not contain.

The Lean library Littlewood proves Theorem 1.1 in an equivalent form: for every η>0\eta>0 there is N0≥1N_0\ge1 such that for every N≥N0N\ge N_0 some Littlewood polynomial PP of length NN has |P(z)|≤(1+η)N|P(z)|\le(1+\eta)\sqrt N at every zz with |z|=1|z|=1. The Lean library also proves Corollary 7.1, flatness for every finite exponent: there are Littlewood polynomials PNP_N, one of each length NN and each of least maximum modulus among those of its length, with ∫01||PN(e2πit)|/N−1|pdt→0\int_0^1\bigl|\,|P_N(e^{2\pi it})|/\sqrt N-1\bigr|^p\,dt\to0 for every real p>0p>0. The results on these pages are the Lean library’s, each stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every result of the Lean library. The Lean library is therefore the reference, and where the preprint states a result differently, that result’s page gives the Lean library’s statement with the preprint’s beside it. The preprint is a guide only: it gives the results their order and their names. The preprint quotes two combinatorial theorems, which the Lean library does not assume. An rr-uniform hypergraph is δ\delta-nearly regular with small codegrees when, for some D>0D>0, each of its vertices lies in between (1−δ)D(1-\delta)D and (1+δ)D(1+\delta)D edges and each two of its vertices lie together in at most δD\delta D edges. Pippenger and Spencer proved that for every γ>0\gamma>0, when δ\delta is small enough in terms of rr and γ\gamma, the edges of such a hypergraph split into at most (1+γ)D(1+\gamma)D matchings. In place of this edge-coloring theorem, the Lean library proves, as Theorem 3.2, a matching theorem in the form of Alon and Yuster: for every γ>0\gamma>0 and every K0≥0K_0\ge0, such a hypergraph on nn vertices, in which each two vertices lie together in at most some CC edges with nC≤K0DnC\le K_0D, has a matching that covers all but at most γn\gamma n of its vertices, once δ\delta is small enough and DD and nn are large enough in terms of rr, K0K_0 and γ\gamma. In place of the partial-coloring theorem of Lovett and Meka, the Lean library proves an entropy partial-coloring lemma of its own.

The Lean library: Littlewood

Littlewood is a Lean library: 19 items, in seven groups. Each has a page written by OctoInform, listed below.

§1. Introduction 2 items
  1. Littlewood polynomials and the normalized minimum maximum Littlewood polynomials built from real coefficient vectors and signings.
  2. Theorem 1.1 Real Littlewood polynomials with maximum modulus close to N\sqrt{N}.
§2. Reduction to approximation and rounding 4 items
  1. The phase e(x) and the relaxed sum Q_X Real polynomials on the unit circle are sums of phases.
  2. Proposition 2.1 Almost-sign coefficient vectors with small maximum modulus.
  3. Lemma 2.2 Rounding to signs with error controlled by the defect mass.
  4. Proof of Theorem 1.1 Rounding a real coefficient vector to a Littlewood polynomial.
§3. Packing signed intervals 3 items
  1. Closed circle intervals Closed intervals of the circle and signed points.
  2. Lemma 3.1 Nonparallel integer frequencies admit disjoint signed arcs.
  3. Theorem 3.2 Almost perfect matchings in nearly regular hypergraphs with small codegrees.
§4. Spreading Fourier coefficients 4 items
  1. Proposition 4.1 An auxiliary frequency packet exists for each small parameter.
  2. The binary recursion Functions on tori bounded by one, with spread Fourier coefficients.
  3. Curvatures, spreading and truncation Tuning curvature products and bounding quadratically spread Fourier coefficients.
  4. Lemma 4.2 Uniform stationary phase for quadratic oscillatory integrals.
§5. Sampling the auxiliary polynomial 2 items
  1. Lemma 5.1 A uniform stationary phase expansion of smoothed quadratic sums.
  2. Blocks, the uniform maximum and the mean square Sampling a torus polynomial in blocks controls maximum and energy.
§6. Rounding with a small defect mass 2 items
  1. Lemma 6.1 Column signings with small row sums for bounded matrices.
  2. Dyadic rounding and the passage to the circle Rounding a vector of small mass to zeros and ones.
§7. Flatness for every finite exponent 2 items
  1. The flatness model Real signings and their Littlewood polynomials.
  2. Corollary 7.1 There are Littlewood polynomials flat for every finite exponent.

No item matches.