Ultraflat real Littlewood polynomials

Proof. Put y_0=u/(T\beta) and complete the square. Fourier inversion reduces the bracket in (2.1) to the exact expression

For completeness, this identity follows by inserting \exp(-\pi r(y-y_0)^2), r>0, before applying Fourier inversion. The inner Gaussian integral has factor (r-iT\beta)^{-1/2}\exp(-\pi\xi^2/(r-iT\beta)); its modulus is at most (T|\beta|)^{-1/2}. Dominated convergence against |\widehat g(\xi)| justifies r\downarrow0 and yields the factor \e(\sgn(\beta)/8)/\sqrt{T|\beta|}. Finally, replacing \e(-\xi^2/(2T\beta)) by 1 costs at most

independently of y_0.□

Proof. Write d=\sgn(\phi''). If t_x\in I, the change of variable

extends smoothly across t=t_x and changes the phase to \phi(t_x)-xt_x+dy^2/2. Taylor’s integral formula and the lower bound on |\phi''| show that this is a smooth increasing coordinate with derivative bounded above and below, uniformly for t_x\in I. All its required derivatives and those of its inverse are uniformly bounded. The transformed amplitudes, extended by zero, have support in a fixed compact set and uniformly bounded smooth norms, because \supp f is separated from the endpoints of I. At y=0 their value is f(t_x)/\sqrt{|\phi''(t_x)|}. Lemma 2.1, whose error is controlled by a fixed finite collection of smooth norms, proves the assertion uniformly in this case. If x\notin\phi'(I), the distance between x and \phi'(\supp f) is bounded below uniformly; integration by parts then gives an O(N^{-1}) integral. These two cases include the endpoints of \phi'(I).□

Proof. The primitive of \e(\pm y^2/2) has bounded differences on arbitrary real intervals: inside [-1,1] this is immediate, and on either remaining half-line integration by parts gives a uniform bound. Completing the square and rescaling therefore bounds every subinterval integral of \e(N\phi-kt) by C/\sqrt{N|\Lambda|} in the quadratic case. In the monotone case, one integration by parts bounds every such integral by C/(N\rho); monotonicity bounds the total variation of (N\phi'-k)^{-1} by 2/(N\rho). Integration against the amplitude f, using either primitive, gives the stated estimates.□

Proof. This is [13, Lemma 6.2], whose statement applies to arbitrary real matrices in the displayed rectangular range.□

Proof. If \mu=0, take \eta_j=Z_j. Suppose \mu>0, and set p_j=(1-|Z_j|)/2. Then 0\le p_j\le1/2 and \sum_jp_j=\mu. On the grid t_\ell=\ell/(20n), 0\le\ell<20n, form the real matrix with R=40n rows

Every entry belongs to [-1,1]. We round p to a vector in \{0,1\}^n, preserving an upper bound on its total mass.

Choose an integer J\ge1 with n2^{-J}\le1, and first set p_j^{(J)}=2^{-J}\lfloor2^Jp_j\rfloor. This costs at most 1 in \norm{A(p^{(J)}-p)}_\infty and does not increase the mass. At stage h=J,\ldots,1, let S_h contain those coordinates for which 2^hp_j^{(h)} is odd, and let s_h=|S_h|. If s_h=0, leave the vector unchanged. Otherwise apply Lemma 3.1 to the columns indexed by S_h. Reverse all its signs if necessary so that their sum is nonpositive, and put

An odd multiple of 2^{-h} in [0,1] lies between 2^{-h} and 1-2^{-h}. Either change therefore stays in [0,1] and lies on the next coarser grid. The total mass remains at most \mu, while the simultaneous sign reversal leaves the absolute discrepancy unchanged. In particular, each active coordinate has mass at least 2^{-h}, so

The last inequality is used only at nonempty stages. Monotonicity of s\log(80n/s) on (0,n] gives

For 2^h\mu>n, use the bound n\log80 on the left and \mu\le n/2 on the right. Summing the geometric series of step errors yields, with p'=p^{(0)}\in\{0,1\}^n,

Set \eta_j=d_j(1-2p'_j) and Q(z)=\sum_{j=0}^{n-1}(\eta_j-Z_j)z^j. The real and imaginary parts of Q(\e(t_\ell)) are each bounded by twice the left side of (3.2). Thus the claimed error bound holds on the grid. To pass to the circle, let S=\max_{|z|=1}|Q(z)|. The maximum principle, applied also to the reversed polynomial, gives

Cauchy’s estimate in disks of radius 1/n centered on the unit circle therefore gives

Every point of \T is within 1/(40n) of the grid. Hence S\le\max_\ell|Q(\e(t_\ell))|+(\pi\exp(1)/20)S. Since \pi\exp(1)/20<1, this proves (3.1). Multiplication by a unimodular monomial handles shifted consecutive frequencies. If the inputs are real, all d_j are signs and hence so are the outputs.□

Proof. Choose 0<q<1/4, to be fixed in terms of \alpha, and then choose such a g with \int g^2\ge1-q. For a fixed \beta\in\mathcal B, write

Lemma 2.1 and L_\beta/(T|\beta|)\to1 give, uniformly in u,

for all sufficiently large T. The coefficients outside the stated interval have a small sum of absolute values. Indeed, \supp g is separated from both endpoints, so on a neighborhood of this support,

Twice integrating by parts, with no boundary terms, gives |I_\beta(u)|\le C_{g,\beta}(T+|u|)^{-2} there. The derivative of T\beta y-u is T\beta, so all terms from these integrations have this bound. Consequently

For the retained indices define Z_u=\sqrt{L_\beta}I_\beta(u)/(1+q). By (4.3), |Z_u|\le1. Parseval’s identity and (4.4) show that, for large T,

Since 1-|Z_u|\le1-|Z_u|^2, the defect \mu=\frac12\sum_u(1-|Z_u|) satisfies

Apply Lemma 3.2 on this consecutive interval of frequencies, and divide its conclusion by \sqrt{L_\beta}. It gives unit complex numbers \eta_u. Their polynomial f_\beta(y)=\sum_u L_\beta^{-1/2}\eta_u\e(uy) satisfies

Indeed, for x=\mu/L_\beta>0, monotonicity gives x\log(80/x)\le2q\log(40/q)\le2q\log(80/q); the zero-defect case follows directly from the rounding lemma. By (4.4), the polynomial before rounding differs from the target by at most q+o(1) in supremum norm. First choose q small enough, then fix g, and finally take T large. The resulting error is at most \alpha. All estimates hold simultaneously for the finite set \mathcal B. Construct the polynomials for positive \beta and set f_{-\beta}=\overline{f_\beta}: the targets are conjugates and the frequency intervals are symmetric, so all conclusions are preserved.□

Proof of Proposition 4.1. We first construct a real polynomial with norm at most one and squared L^2 norm close to one. Starting with p_0=0, define successively

These polynomials have mean zero and satisfy |p_j|\le1, because (1-r^2)/2\le1-|r| for |r|\le1. Writing M_j=\int p_j^2, integration in the new coordinate gives

Thus M_j\uparrow1: a limit smaller than one would force increments bounded away from zero. Fix d\ge2 with M_d\ge1-\delta, and write

Zero is not in \mathcal S, since p_d has mean zero. At each step, old frequencies acquire a zero final coordinate and persist, while new frequencies have final coordinate 1 or -1. Hence every s\in\mathcal S has last nonzero coordinate 1 or -1. Parallel members of \mathcal S are therefore equal up to sign. The first-coordinate pair persists, and the second step introduces another pair, since \int(1-p_1^2)>0. Choose representatives s_1,\ldots,s_D of these sign pairs.

We next choose the sizes of the frequency boxes. Choose \gamma\in\R^d outside the finitely many hyperplanes s^\perp, and put \rho_s=|s\cdot\gamma|>0. The box over s should contain a number of frequencies approximately proportional to |b_s|^2/\rho_s: equal spreading then makes each squared coefficient approximately proportional to \rho_s, matching the weight supplied by a vector v proportional to (\gamma,0). We will choose vectors W_1,\ldots,W_D\in\R^d with nonzero projections s\cdot W_j and use these projections as spreading parameters. The box over s will then have size asymptotic to T^D\prod_j|s\cdot W_j|. We therefore require these products to be approximately \tau|b_s|^2/\rho_s, using one small positive parameter \tau for all s.

For each j, choose W_j^0\in s_j^\perp not orthogonal to any other representative. This is possible because d\ge2 and the representatives are pairwise nonparallel, so only finitely many proper subspaces of s_j^\perp are excluded. Choose W_j^1\in\R^d such that

Set W_j=W_j^0+\tau W_j^1. As \tau\downarrow0,

Indeed, exactly the factor belonging to the representative of \{s,-s\} vanishes at \tau=0, and its first-order coefficient was just prescribed. Fix \tau>0 small enough that all factors are nonzero and, with \beta_{s,j}=s\cdot W_j and \Delta_s=\prod_j|\beta_{s,j}|,

All these data are now fixed. Apply Lemma 4.2 to the finite list of nonzero \beta_{s,j}, choosing \alpha>0 small enough that

With the resulting common cutoff g and sufficiently large T, define

The conjugation condition on the factors and b_{-s}=\overline{b_s} show that F is real. If each factor is replaced by its target, the resulting function is

where z_j is represented in [-1/2,1/2]. The cutoffs vanish near the endpoints, so this expression is well defined on the torus and has norm at most one. A telescoping product estimate bounds its distance from F by the left side of (4.6). Therefore \norm F_\infty\le1+\delta.

Over each old frequency s, the Fourier support of F is the full box

This box has n_s=\prod_jL_{\beta_{s,j}} members, each with coefficient magnitude |b_s|/\sqrt{n_s}. Distinct old frequencies give disjoint boxes, so every indicated coefficient is nonzero. If two resulting frequencies are parallel, their s coordinates force the proportionality factor to be 1 or -1; thus they are equal or opposite. There remain at least two sign pairs, and no zero frequency.

Since L_\beta/(T|\beta|)\to1, increase T so that

and choose the approximants at this value of T. This is permitted because the spreading lemma holds for every sufficiently large T. Fix T, put m=d+D, and take

For every frequency a over s, its weight is w_a=\rho_s/(\tau T^D(1+\delta)^3)>0. Combining (4.5) and (4.7) gives

Finally, 1-\delta\le\sum_s|b_s|^2=M_d\le1, so the total weight lies between (1-\delta)^3/(1+\delta)^3 and 1/(1+\delta). The ratio bounds in (4.9) imply 1\le|c_a|/\sqrt{w_a}\le1+C\delta, and the upper bound is less than 2 for 0<\delta<1/100. These are all the assertions of (4.1). The choices were made in the order \delta, p_d, \gamma, (W_j^0,W_j^1), \tau, \alpha, g, T; in particular the entire auxiliary construction is fixed before the polynomial length is chosen.□

Proof of Proposition 5.1. Fix \delta and choose the data of Proposition 4.1. Thus

where F is real, \mathcal A=-\mathcal A, and

There are at least two sign-pairs in \mathcal A, and representatives of these pairs are nonparallel. All choices below, apart from bounded phase adjustments used to join endpoint values, will be fixed before N tends to infinity. Constants depending on these choices are allowed in errors that vanish with N; the constants multiplying \delta and \sqrt\delta in the final bounds will be absolute. We first obtain a bound 1+O(\delta) for the scaled Fourier contribution of the main intervals, then fill their small complement at cost O(\sqrt\delta). A separate integration-by-parts argument will control the sum of the exterior coefficients.

Packed intervals and inverse curvature

Apply Lemma 5.2 to one representative from each sign-pair, using w_{-a}=w_a. It gives disjoint closed arcs centered at -a\cdot\theta_h, of length w_a/H, for all a\in\mathcal A and 1\le h\le H. Each arc is disjoint from its reflection and consequently avoids the two fixed points 0 and 1/2 of reflection on \T. We may therefore regard the arcs as intervals in (-1/2,1/2), with center representatives t^*_{a,h} satisfying

The variable x will denote the normalized Fourier index k/N. For each h, choose a closed interval

symmetric about x_h^*=(h-1/2)/H. On J_h choose a smooth function \chi_h, symmetric about x_h^*, such that

Here \sigma\in(0,1) can be arbitrarily small. Indeed, first choose |J_h|>(1-\delta/2)/H, and then take \chi_h=1 except on endpoint neighborhoods of total length less than \delta/(2H), with smooth transitions to \sigma.

We will specify the point t at which a wave’s phase derivative equals x. Requiring |dt/dx|=w_a\chi_h(x)^2 makes the stationary-phase factor equal to \sqrt{w_a}\chi_h(x), so a wave of modulus m_a has leading scaled coefficient magnitude |c_a|\chi_h(x). Thus \chi_h can suppress endpoint Fourier contributions without decreasing the wave modulus.

Choose smooth real Q_h with

and with a smooth extension to a neighborhood of J_h. Define

This is a diffeomorphism, possibly reversing orientation, onto a closed interval I_{a,h}. Symmetry and \chi_h\le1 give |Q_h'|\le |J_h|/2<1/(2H), so I_{a,h} lies strictly inside its assigned packed arc. Write X_{a,h}:I_{a,h}\to J_h for the inverse map and set

The derivative identities follow by differentiating (5.8) and using (5.7). On each I_{a,h} define

The modulus is the constant m_a. Moreover, T_{-a,h}(x)=-T_{a,h}(x) and \psi_{-a,h}(-t)=-\psi_{a,h}(t); together with c_{-a}=\overline{c_a} these give conjugate symmetry on the main intervals. Their total length is

Coherent stationary contributions

The phase choice will make the leading stationary contributions sum to a scalar multiple of a single value of F. We first isolate them with a cutoff and estimate the remaining endpoint pieces using their large curvature.

Choose G_h\in C_c^\infty(\operatorname{int}J_h) with 0\le G_h\le1, such that, on J_h, 1-G_h is supported in the two endpoint intervals where \chi_h=\sigma, and is monotone on each such interval. Split each integral over I_{a,h} using the cutoff G_h(X_{a,h}(t)). On either endpoint part the phase has constant second derivative of modulus 1/(w_a\sigma^2). The cutoff has bounded total variation. Lemma 2.3 therefore bounds this part, after multiplication by \sqrt N, by

Choose \sigma so small, before fixing the functions in (5.6), that the sum of these bounds over all endpoints is at most \delta.

For the part with cutoff, apply Lemma 2.2 with x=k/N. After multiplication by \sqrt N, the leading term is zero if x\notin J_h; if x\in J_h, its stationary point is t=T_{a,h}(x) and its value is

Indeed,

and the phase correction \sgn(\psi_{a,h}'')/8 cancels the constant \sgn(\lambda_a)/8 in (5.10). The error is o(1) uniformly for 0\le k<N.

At most one J_h contains x. For that h, summing (5.12) over a gives

Here (5.5) may be used inside the exponential because k is an integer. Since 0\le G_h\chi_h\le1, the norm bound for F and the endpoint estimates imply

All errors are uniform in these integer indices. The finite number of intervals is fixed, so summing their stationary-phase errors preserves o(1).

Joining the waves through the gaps

It remains to define B_N on a set of length O(\delta) without losing its lower modulus bound. We will join the waves continuously and also match the derivatives of their leading phases. The first condition preserves the desired function; together, the two conditions will cancel the boundary terms in the exterior Fourier estimate.

Work first on [0,1/2]. Let [u_j,v_j] be the closures of the gaps between its main intervals, including the gaps adjacent to 0 and 1/2. Put l_j=v_j-u_j and L=\sum_jl_j. Strict containment in the packed arcs and (5.11) give

and each l_j is positive. At an endpoint z adjoining a main interval, prescribe the derivative x_z=\psi_{a,h}'(z)\in(0,1); at the remaining endpoints prescribe x_0=x_{1/2}=1/8.

For each gap choose a closed interval [P_j,R_j]\subset(1/4,3/4), of length l_j/(4L), such that these intervals are pairwise disjoint and none of their endpoints equals any prescribed x_z. To see that these choices are possible, note that their total length is 1/4. They can therefore be arranged with positive spaces between them inside an interval of length less than 1/2; a sufficiently small common translation then avoids the finitely many forbidden endpoint values. We call [P_j,R_j] the derivative interval assigned to gap j.

Divide gap j into three pieces. On these pieces take \phi_j' to be linear, successively interpolating

Thus \phi_j is continuously differentiable and piecewise quadratic; its additive constant is immaterial. Make both outer pieces shorter than l_j/4. Their nonzero slopes \Lambda=\phi_j'' can be made arbitrarily large in absolute value because P_j\ne x_{u_j} and R_j\ne x_{v_j}. Choose their lengths so that

The middle piece has length at most l_j, so its positive slope satisfies

Every value of every leading phase derivative lies in a fixed compact subset of (0,1).

Figure 1 illustrates the two distinct uses of these pieces: large outer slopes suppress the cost of joining the prescribed endpoint derivatives, while separated middle derivative intervals ensure that only one middle pair can contribute substantially at a given normalized Fourier index.

Let m_j interpolate linearly between the endpoint moduli m_a, with modulus 1 prescribed at 0 and 1/2. Define on gap j

where \gamma_{j,N} is affine. Choose its two endpoint values in [0,1) to give the exact phase factors required by the adjoining main waves, and phase factor 1 at 0 and 1/2. There is no constraint on these choices: each endpoint requires just one congruence modulo 1. In particular,

The second bound depends on the fixed gap but is independent of N. Extend to the negative half-circle by B_N(-t)=\overline{B_N(t)}. Because B_N(0)=B_N(1/2)=1, this gives a continuous function on \T satisfying (5.1). On reflected gaps use the leading phase -\phi_j(-t). Its derivative is \phi_j'(-t), so the leading phase derivatives match across every join, including 0 and the identified endpoints \pm1/2. Matching the full derivatives of B_N is unnecessary.

Fourier cost of the gaps

We now bound the Fourier contributions of the gaps. In (5.17) regard f_N=m_j\e(\gamma_{j,N}) as the amplitude. On each piece,

with an absolute constant, since m_j is monotone between values in [1,2] and the total variation of \gamma_{j,N} is at most 1. Lemma 2.3 and (5.15) show that all outer pieces and their reflections contribute at most C\sqrt\delta to the scaled Fourier coefficient \sqrt N\,\widehat B_N(k).

Choose a fixed \rho>0 so that the closed \rho-neighborhoods of the finitely many derivative intervals [P_j,R_j] are pairwise disjoint. At most one of these intervals is within \rho of x=k/N. If such an interval exists, the quadratic estimate and (5.16) bound the total contribution of its middle piece and its reflection by C\sqrt L. Every other middle piece has monotone \phi_j'-x of modulus at least \rho. The first-derivative estimate in Lemma 2.3, together with (5.18), bounds its scaled contribution by C/(\rho\sqrt N). The same bound holds for its reflection. Their number and \rho are fixed, so the sum of these terms is o(1), uniformly in k. Combining these bounds with (5.13) proves

Increasing N_0(\delta) absorbs the last error into \sqrt\delta and proves (5.2). In particular, neither the number of gaps nor their separation contributes to the surviving constant.

Cancellation at the joins and the exterior tail

For projection to the allowed frequencies, an estimate on individual exterior coefficients is insufficient; we need their sum to tend to zero. This is where matching the leading phase derivatives is used. Partition [-1/2,1/2] into all main intervals and the three pieces of each gap and reflected gap. On each piece write

The functions f_N,f_N',f_N'' are bounded independently of N on each piece. The phase \phi is fixed, its first three derivatives are bounded, and all values of \phi' lie in a fixed compact subinterval of (0,1). These bounds may depend on all the fixed construction data. For k<0 or k\ge N, put D=N+|k| and V=N\phi'-k. Then

on every piece, for fixed c>0 and C_*<\infty.

The first integration by parts gives boundary terms

They cancel at every internal join, because B_N is continuous and the leading phase derivatives agree. They also cancel at -1/2 and 1/2: there B_N=1, \phi'=1/8, and \e(-k/2)=\e(k/2) for integer k. After this cancellation, a second integration by parts involves

and its derivative

Since N\le D, (5.19) implies |A|+|A'|\le C_{\mathrm{data}}D^{-2}. Both the second boundary terms and the remaining integrals therefore have this bound on each piece. There are only finitely many pieces, whence

Summing over these integers proves (5.3), since \sum_{k\in\Z}(N+|k|)^{-2}=O(N^{-1}). The finitely many interior coefficients and this summable exterior bound show that the full Fourier series converges absolutely. Its sum equals B_N by continuity and uniqueness of Fourier coefficients. Finally, conjugate symmetry gives \widehat B_N(k)\in\R for every integer k.□