Nearly minimal maxima and positive minima of Littlewood polynomials

Proof. Use the real-line Fourier transform \widehat g(\xi)=\int_{\R}g(x)\e(-\xi x)\,dx, and put x_0=u/(T\beta). Completing the square reduces the integral to

Insert the damping factor \exp(-\pi\rho y^2) with \rho>0, and use Fourier inversion on g(x_0+y). The resulting double integral is absolutely integrable. The inner Gaussian integral is

Here the square root is the branch analytic in the right half-plane and positive on the positive real axis. As \rho\downarrow0,

The modulus of the exponential multiplier is at most one, and |(\rho-iT\beta)^{-1/2}|\le(T|\beta|)^{-1/2}. Since \widehat g is Schwartz, dominated convergence applies on the Fourier side. On the original side it applies with dominating function |g(x_0+y)|. We obtain the exact identity

The difference of the last integral from g(x_0) has absolute value at most

This bound is independent of x_0, proving the required uniformity.□

Proof of Proposition 2.1. Fix \delta. The choices below are successive: once a parameter has been chosen, it stays fixed while later parameters vary.

A polynomial of almost unit mean square. Starting with p_0=0, introduce one new torus coordinate at each step and define

For |z|\le1, (1-z^2)/2=(1-|z|)(1+|z|)/2\le1-|z|. Thus |p_j|\le1 pointwise. Integrating first in y_j shows that p_j has mean zero. If M_j=\int_{\T^j}p_j^2, integration of the square in the new variable gives

Hence M_j\uparrow1: a limit below one would make the increments bounded below by a positive constant. Choose d\ge2 so that M_d\ge1-\delta.

Let \mathcal S\subset\Z^d be the Fourier support of p_d, consisting of the frequencies with nonzero coefficients, and put c_s=\widehat p_d(s). Every vector in \mathcal S has last nonzero coordinate equal to 1 or -1. Indeed, the old term in (5) keeps the previous frequencies with new coordinate zero, whereas every frequency in the new term has new coordinate 1 or -1. The two terms cannot cancel each other. There is no constant frequency because the mean is zero.

If two such vectors are parallel, comparing their last nonzero coordinates shows that they are equal or negatives. Let s_1,\ldots,s_D be those with positive last nonzero coordinate. They are pairwise nonparallel and \mathcal S=\{\pm s_1,\ldots,\pm s_D\}. There are at least two: the coefficient at the first coordinate vector in p_1 is nonzero, and the coefficient at the second coordinate vector in p_2 is (1-M_1)/4=7/32>0; both persist in later steps.

We have obtained the mean-square mass needed in (1). It remains to distribute its Fourier coefficients so that the total width and the coefficient-to-width ratios in (2) are both controlled.

Choosing the quadratic curvatures. Choose \gamma\in\R^d outside the finite union of hyperplanes s^\perp, s\in\mathcal S, and define \rho_s=|s\cdot\gamma|>0. We will choose vectors b_1,\ldots,b_D\in\R^d so that the products

are approximately a common multiple of |c_s|^2/\rho_s. Here is the reason for this target. At a large oscillation scale B, the construction below assigns about B^D\Delta_s Fourier positions to the original frequency s, with coefficient sizes bounded by about |c_s|/\sqrt{B^D\Delta_s}. Assigning each such position a width proportional to \rho_s/B^D makes the total width of this family proportional to \Delta_s\rho_s, and the resulting upper bound for the ratio of squared coefficient size to width proportional to |c_s|^2/(\Delta_s\rho_s). Thus choosing \Delta_s\rho_s approximately proportional to |c_s|^2 balances these upper bounds while making the total width track the Parseval mass \sum_s|c_s|^2. The estimates and the common proportionality factor are made precise below.

For each j, choose b_j^0\in s_j^\perp which is not orthogonal to any s_l with l\ne j. This is possible because each such orthogonality condition cuts out a proper subspace of s_j^\perp, and a finite union of proper subspaces cannot cover that space. Choose b_j^1 satisfying

and set b_j=b_j^0+\tau b_j^1 for a positive parameter \tau. Every denominator is nonzero by the choices just made. For s=s_j,

The same limit holds for -s_j. Fix a sufficiently small \tau>0 so that, simultaneously for all s\in\mathcal S,

In particular, every curvature \beta_{s,j}:=s\cdot b_j is nonzero. All these curvatures are fixed from now on; no lower bound uniform in \delta is needed.

Spreading the coefficients. Choose g\in C_c^\infty((-1/2,1/2)) with 0\le g\le1 and

For a large positive real parameter B, and z\in[-1/2,1/2]^D, define

The cutoff makes this function vanish near every boundary face in z, so it extends to a smooth real function on \T^{d+D}. Translation invariance in y gives

Fourier integration first in y shows that the only possible frequencies are (s,u) with s\in\mathcal S and u\in\Z^D, and

Lemma 2.2 and 0\le g\le1 imply

uniformly for every real w. The constants may depend on the already fixed curvatures and cutoff. Since there are only finitely many pairs (s,j), for all sufficiently large B we have

The stationary points for these integrals suggest keeping the boxes

Their cardinalities satisfy

for all sufficiently large B. Thus the product \Delta_s controls the number of retained frequencies as well as their coefficient bound.

A summable bound outside the boxes. We need uniform approximation after truncation, so the additive error in Lemma 2.2 cannot simply be summed over the whole lattice. Instead, outside the boxes the phase has no stationary point near the amplitude support.

Choose \alpha<1/2 with \operatorname{supp}g\subset[-\alpha,\alpha]. For a fixed \beta\ne0, if |w|>B|\beta|/2, then

with c_{\alpha,\beta}>0. Indeed, the middle expression is at least (1-2\alpha)|w|, while B<2|w|/|\beta|. Integrate by parts l times using

There are no boundary terms. Each term after these integrations contains a bounded derivative of g and a factor bounded by C_l B^h(B+|w|)^{-l-h} for some 0\le h\le l. Hence

For integer w the sum of this bound outside the one-dimensional box is O(B^{1-l}) when l>1. The full sum over integer w is O(B): inside there are O(B) terms, each at most \norm{g}_{L^1(\R)}, and the outside sum is bounded by (14).

The complement of \mathcal U_s is contained in the union of the D coordinate complements. Consequently

Fix an integer l>D. Summing over the finite set \mathcal S shows that the total discarded coefficient mass tends to zero. The Fourier series is absolutely convergent, so this mass also bounds the uniform truncation error.

Truncation and the final budgets. Fix one B large enough for (11), (12), and a truncation error at most \delta in (15). Define

The boxes satisfy \mathcal U_{-s}=\mathcal U_s=-\mathcal U_s. Since G is real, the retained coefficients have conjugate symmetry, and F is real. By (9) and the uniform error,

Set m=d+D and take the containing support

Its vectors are nonzero. If two are parallel, projection onto the first d coordinates forces the proportionality factor to be 1 or -1; the full vectors must then be equal or negatives. Thus one representative from each signed pair gives nonparallel vectors a_1,\ldots,a_r. Every box contains zero, so r\ge D\ge2. Some of the corresponding Fourier coefficients can vanish; the containing support and all estimates remain valid in that case.

Finally choose

For a=(s,u)\in\mathcal A,

Using (12) and (7), with both signs already included in \mathcal S, gives

The coefficient bound (11), divided by 1+\delta, also gives

These are all the assertions of the proposition.□

Proof of Lemma 3.1. We place small disjoint slots on a finite grid in a half-circle. Each slot has one of the types 1,\ldots,r and reserves both itself and its reflection. A compatible choice of one slot of every type will be an edge. We randomize the slots so that almost all vertices have the same degree, then use Theorem 3.2 to select many compatible choices without reusing a slot.

The grid and the random slots. Choose positive numbers \alpha_i>2w_i with \sum_i\alpha_i=1. Approximating large multiples of the \alpha_i by positive odd integers gives fixed odd integers L_i such that, with L=\sum_i L_i,

On a grid with spacing 1/q, a type-i slot will have length L_i/q. We seek a matching of size H\sim q/(2L), so that (16) makes the desired width w_i/H strictly smaller than the slot length.

Let b be the rank over \mathbb Q of the matrix with rows a_i. Then b\ge2. For all sufficiently large primes q, this matrix has rank b over \mathbb F_q, and every pair of its rows has rank two. To see this, exclude the prime divisors of one nonzero b-by-b minor and one nonzero two-by-two minor for each pair of rows. In the rest of the proof q tends to infinity through these primes. All implied constants may depend on the fixed forms and the fixed integers L_i.

Put n=(q-1)/2, R=\lfloor\sqrt q\rfloor, and U_q=\{1,\ldots,n\}. For s\in\mathbb F_q, write |s|_q for the absolute value of its representative in [-n,n]. We call |s|_q its folded site. Partition U_q into consecutive chunks of R sites, with a possibly shorter final chunk; their number is K=\lceil n/R\rceil.

Partition the integers periodically into consecutive slots, each period consisting of one type-i slot of L_i sites for each i=1,\ldots,r, in that order. In each chunk independently, translate this pattern by a uniform residue modulo L and retain only the slots contained entirely in the chunk. A retained slot is a vertex of its type. Its middle site c is an integer because L_i is odd. Independently give each retained slot the oriented center c or -c in \mathbb F_q, with equal probabilities. The orientation specifies which signed center will enter the linear equations; geometrically both signs will be used.

A chunk of u sites has u/L+O(1) retained slots of each type, uniformly in the shift. Thus every realization has

vertices of each type. Call a site interior if its distance from both ends of its chunk is at least L. Let C_j(s) indicate that s is the oriented center of a type-j vertex; in particular C_j(0)=0. If |s|_q is interior, exactly one shift modulo L puts a type-j middle site there, and the required orientation has probability 1/2. Consequently

whenever |s|_q is interior. Center events in different chunks are independent.

Compatibility, degrees, and codegrees. Declare a set of one vertex of each type, with oriented centers s_1,\ldots,s_r, to be an edge when

has a solution y\in\mathbb F_q^m. Each compatible tuple is included only once. Since the evaluation map has rank b, every edge has exactly q^{m-b} generating vectors y.

For s\ne0, define

The affine fiber in this sum has q^{m-1} elements. If the vertex (i,s) is present, division by the multiplicity q^{m-b} gives its degree:

Fixing two centers of different types leaves q^{m-2} possible generating vectors, by pairwise rank two. Their codegree is therefore at most

Vertices of the same type have codegree zero.

We will show that almost all present vertices have degree close to D_q=p^{r-1}q^{b-1}. Joint independence of all the forms is unavailable. Instead, most vectors in a fixed fiber put the other evaluations in different chunks, where the slot choices are independent. The same observation for two fiber vectors will control the variance.

Conditional first and second moments. All relations in this paragraph are over \mathbb F_q. For a fixed type i, exclude the nonzero centers s for which there are indices j<l, both different from i, and a relation

Call this set E_i. For either signed combination of a fixed pair, there is at most one such c; if the combination is a multiple of a_i, the multiple cannot be zero by pairwise nonparallelism. Since multiplication by c\ne0 is a bijection,

Fix s\ne0 outside E_i, and let Q_s be the chunk containing |s|_q. Sample y uniformly from a_i\cdot y=s, independently of the random slots. For each j\ne i, pairwise rank two makes a_j\cdot y uniform on \mathbb F_q. There are at most 2LK noninterior positive sites, including those in a short final chunk. Thus a specified evaluation is zero, folds to a noninterior site, or folds into Q_s with probability at most

Two residues folding into the same chunk have either a sum or a difference with folded absolute value at most R. On the fiber a_i\cdot y=s, each of (a_j+a_l)\cdot y and (a_j-a_l)\cdot y is either uniform on \mathbb F_q or constant. The latter case occurs precisely when its linear form is a multiple c a_i, and its value is then cs. Our exclusion of E_i prevents that constant from having folded absolute value at most R. The uniform case has probability at most (2R+1)/q. A union bound therefore shows that the r-1 evaluations fold into distinct interior chunks, all different from Q_s, except on an O(q^{-1/2}) fraction of the fiber.

For the second moment take independent uniform vectors y,y' in the same fiber. The preceding argument controls collisions within each copy. Across copies, a_j\cdot y and a_l\cdot y' are independent uniform residues whenever j,l\ne i, including j=l. Their sum and difference are uniform, so the same bound controls each cross-copy collision. For u=1 or u=2 independent fiber samples, the fraction for which the combined list fails to occupy distinct interior chunks outside Q_s is at most

Let V_{i,s} be the event that the vertex (i,s) is present, and condition on this event whenever it has positive probability. It depends only on the random choices in Q_s. For every fiber tuple outside the exceptional fraction in (24), the required center events occur in distinct other chunks. Conditional on V_{i,s} they remain independent, each with probability p. The exceptional fraction depends only on the fiber vectors, and its contribution to an expectation is between zero and that fraction. Averaging over one and two fiber vectors therefore gives

Here the expectations are over the slots and their orientations; the square in the second line expands as the average over the independent pair y,y'. The bounds are uniform in s\notin E_i. No interior condition on |s|_q is needed, since the entire chunk Q_s was avoided.

Deletion and a large matching. Set \varepsilon_q=q^{-1/8}. The two moment estimates imply

By Chebyshev’s inequality and (19), a present vertex with s\notin E_i has degree outside [(1-\varepsilon_q)D_q,(1+\varepsilon_q)D_q] with conditional probability O(q^{-1/4}). Summing over the at most r(q-1) candidate centers, the expected number of these vertices is O(q^{3/4}). The vertices with centers in the sets E_i number O(q^{1/2}) in every realization. Markov’s inequality thus gives a realization with at most q^{7/8} vertices in these two classes, for sufficiently large q.

Delete all these vertices and their incident edges. A surviving vertex loses at most the sum of its codegrees with deleted vertices, which by (20) is at most

Every remaining degree is consequently (1+O(q^{-1/8}))D_q, and the maximum codegree is still at most q^{b-2}=o(D_q). Moreover, (17) shows that each type retains (1+o(1))q/(2L) vertices. The matching consequence of Theorem 3.2 gives a matching of size at least (1-o(1))q/(2L). A matching uses one vertex of each type per edge, so its size is also at most (1+o(1))q/(2L). We have obtained

From slots to closed intervals. For each matching edge choose a generating vector y_h\in\mathbb F_q^m, and set \theta_h=y_h/q\pmod{\Z^m} using integer representatives of its coordinates. Then a_i\cdot\theta_h is the corresponding oriented center divided by q, modulo one.

A slot with sites t,\ldots,t+L_i-1 determines the real interval

of length L_i/q and centered at its middle site divided by q. All positive slot intervals lie in [1/(2q),1/2] and have disjoint interiors. Their reflections modulo one lie in [1/2,1-1/(2q)] and also have disjoint interiors. The whole family therefore has disjoint interiors, although adjacent intervals may share endpoints, including at 1/2.

By (16) and (27), for all sufficiently large q,

Each desired closed interval is thus contained strictly inside its slot interval or its reflection. The two signs use this same pair regardless of the chosen orientation. The matching never reuses a slot, so all 2rH closed intervals are pairwise disjoint.□

Proof. For \beta\in J and \ell\in\Z, define

Poisson summation, applied to a smooth compactly supported function, gives

The factor N from the change of scale combines with the original N^{-1/2} to give \sqrt N.

Choose a fixed integer Q so large that, for |\ell|>Q,

Two integrations by parts have no boundary terms and give

Each integral is O(N^{-2}|\ell|^{-2}). The entire tail in (33) is therefore O(N^{-3/2}), uniformly in \beta. This summable bound is needed before adding the stationary-phase errors.

For each of the finitely many indices |\ell|\le Q, expand

Apply Lemma 2.2 with T=N, curvature \lambda, and u=N(\ell-\beta+\lambda x_*). Its stationary point is x_{\beta,\ell}, and \phi_{\beta,\ell}(x_{\beta,\ell})=\omega_{\beta,\ell}. After multiplication by \sqrt N, the error is O(N^{-1}) uniformly in \beta. Increase Q if necessary so that \chi(x_{\beta,\ell})=0 whenever |\ell|>Q and \beta\in J. Adding the finite set of leading terms and errors proves the formula.□

Proof of Proposition 4.1. Fix \delta, and take F, \mathcal A=\{\pm a_i:1\le i\le r\}, and v from Proposition 2.1. Write

The widths w_i=|\lambda_{a_i}| satisfy 2\sum_iw_i<1. Lemma 3.1, with all centers negated, supplies H\ge1 and \theta_1,\ldots,\theta_H\in\T^m such that the closed arcs

are pairwise disjoint. They have length less than one and avoid 0 and 1/2: an arc containing either point would meet its distinct reflected arc I_{-a,h} there.

Put x_h^*=(h-1/2)/H. Choose

We require each \chi_h to be positive on a single interval; on that interval it strictly increases to a plateau at height one and strictly decreases after the plateau. The plateau has positive length. Such cutoffs exist with arbitrarily short boundary layers in each block, giving the last inequality in (35). Choose real lifts of the \theta_h, and set

At most one cutoff is nonzero for each k. Since F is real and \norm F_\infty\le1, these are real numbers in [-1,1].

For a\in\mathcal A, 1\le h\le H, and \ell\in\Z, define, for t\in\R,

Define the leading waves by

The sum is locally finite; shifting t by an integer merely reindexes \ell. It defines a smooth function on \T.

Expand F in (36) and apply Lemma 4.2 with \beta=t+a\cdot\theta_h, \lambda=\lambda_a, x_*=x_h^*, and \chi=\chi_h. The sum over k extends to \Z because the cutoffs are supported strictly inside (0,1). As t ranges over a fundamental interval, all linear frequencies \beta lie in a fixed compact interval. There are only finitely many pairs (a,h), so

For a term of (38) to be nonzero, x_{a,h,\ell}(t) must lie in the hth block. Thus

so t\pmod1 lies in I_{a,h}. Pairwise disjointness allows at most one pair (a,h), and its arc length is less than one, so at most one integer \ell contributes. Consequently |B_N(t)| does not depend on N. It equals the smooth nonnegative function

It vanishes near 0 and 1/2 because all its supporting arcs avoid those points. As F is real, c_{-a}=\overline{c_a} and \lambda_{-a}=-\lambda_a. In (38), replacing (t,a,\ell) with (-t,-a,-\ell) changes u to -u, keeps x unchanged, and changes \psi and \operatorname{sgn}\lambda_a to their negatives. Hence B_N(-t)=\overline{B_N(t)}, and B is even.

The disjointness also makes the mass calculation exact. On the arc indexed by (a,h), the change of variables from x to t has absolute Jacobian |\lambda_a|. Therefore

If E_N=\norm{U_{Y_N}-B_N}_\infty, then

Parseval now gives the second inequality in (29) for all sufficiently large N. This calculation covers repeated values of \lambda_a, since separation occurs in the angle variable.

The gaps and their endpoint phases. It remains to locate the small values of the fixed function B. Each arc supports one bump of height |c_a|/\sqrt{|\lambda_a|}. If this height is at least b, the set where that bump is at least b is a closed interval of positive length. The positive-length plateau ensures this even when the height equals b. A lower bump, including one with c_a=0, contributes no such interval. The supporting arcs are disjoint and avoid 0,1/2, so the claimed description of the superlevel set follows. It is nonempty because (41) gives \int B^2>b^2, and evenness places a nonempty part in each half-circle. The closures of the complementary intervals are thus precisely the gaps J_j in the statement, and every gap has positive length.

Let E=\{t\in\T:B(t)<b\}. The endpoints of the finitely many intervals have measure zero, and evenness gives |E|=2L. Using B\le K_\delta and (41),

Thus

For the last inequality, K_\delta^2-1\le5\delta when \delta<1/100 and K_\delta^2-b^2\ge1-1/64. Also L>0, since B vanishes on neighborhoods of 0 and 1/2.

Finally, at a transition endpoint z, continuity gives B(z)=b>0. There is a neighborhood of z on which exactly one term of (38) is nonzero. For its fixed indices (a,h,\ell) choose \alpha_z\in\R with

This yields (31). Differentiating (37) gives

because the cutoff is positive there. All data have been fixed before N varies, and every positive integer N was permitted in the construction. This completes the proof.□

Proof. We use the following existential consequence of the Lovett–Meka theorem [8, Theorem 4 of arXiv:1203.5747v2]. Given vectors v_1,\ldots,v_R\in\R^u, a starting point x_0\in[-1,1]^u, and nonnegative numbers c_1,\ldots,c_R such that

there exists, for every sufficiently small \eta>0, a point x\in[-1,1]^u with

The cited theorem finds such a point with positive probability; we use only its existence assertion. Letting \eta tend to zero and taking a convergent subsequence in the compact cube gives a point with at least \lceil u/2\rceil coordinates equal to signs and the same discrepancy bounds. Indeed, there are only finitely many choices of these coordinates, and all the displayed inequalities are closed under limits.

Start at zero in [-1,1]^s. At a stage with u coordinates not yet equal to signs, restrict the rows of B to those coordinates, take their current values as x_0, and choose

The threshold sum is exactly u/16, and every restricted row has Euclidean norm at most \sqrt u. Thus this step changes each row sum by at most 4\sqrt{u\log(16R/u)} and fixes at least half the remaining coordinates. Leave the fixed coordinates unchanged and repeat. Zero rows impose no restriction. The process terminates with a sign vector.

If u_h is the number of remaining coordinates before step h, starting with h=0, then u_h\le2^{-h}s. The function u\log(16R/u) is increasing for 0<u\le R. With L=\log(16R/s)\ge\log16, the sum of the row errors is therefore at most

The last series converges, and \log(16R/s)\le4\log(2R/s) for s\le R. This proves the lemma with an absolute constant, including when s=R.□

Proof of Lemma 6.1. Let X=(X_0,\ldots,X_{N-1})\in[-1,1]^N and \mu=\frac12\sum_k(1-|X_k|). If \mu=0, every X_k is already a sign, and we take \varepsilon_k=X_k. Suppose henceforth that 0<\mu\le N/2. Set

Then X_k=\sigma_k(1-2p_k), 0\le p_k\le1/2, and \sum_kp_k=\mu. In particular, this definition includes X_k=0.

Put M=20N and R=2M=40N. For the grid points t_\ell=\ell/M, 0\le\ell<M, define the real R\times N matrix A by

Its entries belong to [-1,1], and every selection of its columns has at most N\le R columns.

Choose an integer J\ge1 with N2^{-J}\le1, and first round down:

This does not increase the mass, and

We next construct p^{(j-1)} from p^{(j)}, for j=J,J-1,\ldots,1. Intermediate entries may exceed 1/2, but it is enough to keep them in [0,1], whose endpoints encode the two choices of final sign. We preserve the two properties

Let S_j be the set of coordinates for which 2^jp^{(j)}_k is odd, and let s_j=|S_j|. If s_j=0, no change is needed. Otherwise apply Lemma 6.2 to the columns indexed by S_j, obtaining signs \xi_k. Replace all these signs by their negatives if necessary so that \sum_{k\in S_j}\xi_k\le0, and define

An odd integer in [0,2^j] lies between 1 and 2^j-1; adding either sign therefore gives an even integer still in [0,2^j]. Thus the new vector belongs to ([0,1]\cap2^{-(j-1)}\Z)^N. Its mass does not increase, and the simultaneous sign reversal has left the discrepancy unchanged. The step error is consequently at most

Every coordinate in S_j is at least 2^{-j}, so the mass bound gives

This is where the total defect enters the estimate. Put U_j=2^j\mu and L_\mu=\log(80N/\mu). The function f(s)=s\log(80N/s) is increasing on (0,N]. If U_j\le N, then

If U_j>N, then, using \mu\le N/2,

These estimates apply at every nonempty stage. Summing (68) and (67) therefore gives, for p'=p^{(0)}\in\{0,1\}^N,

Empty stages contribute zero, without invoking the discrepancy bound with no columns.

Now set \varepsilon_k=\sigma_k(1-2p'_k)\in\{-1,1\} and define the error polynomial

By the definition of A, the real and imaginary parts of Q(\e(t_\ell)) each have absolute value at most 2\norm{A(p'-p)}_\infty. Hence

It remains to pass from this grid bound to the whole circle. We apply this step only to Q, the rounding error.

Write S=\max_{|z|=1}|Q(z)|. If Q=0, there is nothing to prove. Otherwise let d\le N-1 be its degree. Applying the maximum principle to Q on the unit disk and to the reversed polynomial z^dQ(1/z) gives

Cauchy’s estimate on the disk of radius 1/N centered at a point of the unit circle yields |Q'(z)|\le\exp(1)NS there. Consequently

Every point of \T has circular distance at most 1/(2M) from the grid. Integrating this derivative along the shorter arc gives

The denominator is positive. Combining this inequality with (70) and (69) proves Lemma 6.1, with an absolute constant. The same argument covers N=1, when the error polynomial is constant.□

Proof of Theorem 1.1. Let b=1/8 and let D>0 be the absolute constant in Proposition 5.1. For a fixed sufficiently small \delta>0, take the real coefficients Y_{N,k} and the functions B_N from Proposition 4.1, and the correction R_N from Proposition 5.1. All estimates below hold for every sufficiently large integer N. Put

Conjugate symmetry of R_N makes \widehat R_N(k) real. Since |Y_{N,k}|\le1 and \sqrt N|\widehat R_N(k)|\le s_\delta, the vector X_N belongs to [-1,1]^N. The uniform approximation in Proposition 4.1 and the exterior Fourier-tail estimate in Proposition 5.1 give

Consequently,

In the second inequality we used S_\delta\ge1.

The same coefficient bound controls the cost of rounding. Directly,

Both coefficients lie in [-1,1], so |X_{N,k}^2-Y_{N,k}^2|\le4s_\delta. Using the mean-square estimate from Proposition 4.1 and 1-|x|\le1-x^2 for |x|\le1, we obtain

Choose \delta small enough that q_\delta<1/2. The function q\mapsto q\log(80/q) is increasing on (0,1/2]. Lemma 6.1 therefore supplies signs \varepsilon_0,\ldots,\varepsilon_{N-1} with

If \mu(X_N)=0, we instead take \varepsilon_k=X_{N,k}, so this bound also covers that case.

Fix c=1/16 once and for all. As \delta\downarrow0,

For any prescribed \eta>0, first choose \delta so small that the first expression is strictly larger than c and the second is strictly smaller than 1+\eta. Fix every construction datum associated with this \delta. We may then choose N_0 so that for every N\ge N_0 all preceding estimates hold and the errors in (72) and (74) are smaller than these strict margins. It follows that

Multiplication by \sqrt N gives the asserted polynomial. Rounding assigns a real sign to each of the consecutive indices 0,\ldots,N-1; all estimates include t=0 and t=1/2 and hold through every sufficiently large integer length.□