A polynomial of almost unit mean square.

Starting with \(p_0=0\), introduce one new torus coordinate at each step and define \[ p_j(y_1,\ldots,y_j) =p_{j-1}(y_1,\ldots,y_{j-1}) +\frac{1-p_{j-1}(y_1,\ldots,y_{j-1})^2}{2}\cos(2\pi y_j). \tag{5}\] 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_{\mathbb T^j}p_j^2\), integration of the square in the new variable gives \[ M_j=M_{j-1}+\frac18\int_{\mathbb T^{j-1}}(1-p_{j-1}^2)^2 \ge M_{j-1}+\frac18(1-M_{j-1})^2. \tag{6}\] 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\mathbb 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\mathbb 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\mathbb R^d\) so that the products \[\Delta_s=\prod_{j=1}^D|s\cdot b_j|\] 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 \[s_j\cdot b_j^1 =\frac{|c_{s_j}|^2} {\rho_{s_j}\prod_{l\ne j}|s_j\cdot b_l^0|}>0,\] 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\), \[\frac{\Delta_{s_j}}\tau =(s_j\cdot b_j^1) \prod_{l\ne j}|s_j\cdot b_l^0+\tau s_j\cdot b_l^1| \longrightarrow\frac{|c_{s_j}|^2}{\rho_{s_j}} \qquad(\tau\downarrow0).\] The same limit holds for \(-s_j\). Fix a sufficiently small \(\tau>0\) so that, simultaneously for all \(s\in\mathcal S\), \[ (1-\delta)\frac{\tau|c_s|^2}{\rho_s} \le\Delta_s\le (1+\delta)\frac{\tau|c_s|^2}{\rho_s}. \tag{7}\] 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 \[\left(\int_{\mathbb R}g(x)^2\,dx\right)^D\ge1-\delta.\] For a large positive real parameter \(B\), and \(z\in[-1/2,1/2]^D\), define \[ G(y,z)=\left(\prod_{j=1}^Dg(z_j)\right) p_d\left(y+\frac B2\sum_{j=1}^Db_jz_j^2\right), \qquad y\in\mathbb T^d. \tag{8}\] The cutoff makes this function vanish near every boundary face in \(z\), so it extends to a smooth real function on \(\mathbb T^{d+D}\). Translation invariance in \(y\) gives \[ \left\lVert G\right\rVert_\infty\le1, \qquad \left\lVert G\right\rVert_2^2=M_d\left(\int g^2\right)^D\ge(1-\delta)^2. \tag{9}\]

Fourier integration first in \(y\) shows that the only possible frequencies are \((s,u)\) with \(s\in\mathcal S\) and \(u\in\mathbb Z^D\), and \[ \widehat G(s,u)=c_s\prod_{j=1}^DI_{s,j}(u_j), \qquad I_{s,j}(w)=\int_{\mathbb R}g(x)\mathrm e(B\beta_{s,j}x^2/2-wx)\,dx. \tag{10}\] Lemma 3 and \(0\le g\le1\) imply \[|I_{s,j}(w)|\le \frac{1+O(B^{-1})}{\sqrt{B|\beta_{s,j}|}}\] 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 \[ |\widehat G(s,u)|\le (1+\delta)\frac{|c_s|}{\sqrt{B^D\Delta_s}} \qquad(s\in\mathcal S,\ u\in\mathbb Z^D). \tag{11}\]

The stationary points for these integrals suggest keeping the boxes \[\mathcal U_s= \left\{u\in\mathbb Z^D: |u_j|\le\frac{B|\beta_{s,j}|}{2} \text{ for every }j\right\}.\] Their cardinalities satisfy \[\begin{align*} |\mathcal U_s| &=\prod_{j=1}^D\left(2\left\lfloor \frac{B|\beta_{s,j}|}{2}\right\rfloor+1\right) \\ &\le B^D\Delta_s\prod_{j=1}^D \left(1+\frac1{B|\beta_{s,j}|}\right) \le(1+\delta)B^D\Delta_s \tag{12}\end{align*}\] 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 3 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 \[ |B\beta x-w|\ge |w|-B|\beta|\alpha \ge c_{\alpha,\beta}(B+|w|) \qquad(x\in\operatorname{supp}g), \tag{13}\] 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 \[\frac{1}{2\pi i(B\beta x-w)}\frac{d}{dx} \mathrm e(B\beta x^2/2-wx)=\mathrm e(B\beta x^2/2-wx).\] 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 \[ \left|\int_{\mathbb R}g(x)\mathrm e(B\beta x^2/2-wx)\,dx\right| \le C_l(B+|w|)^{-l} \qquad\left(|w|>\frac{B|\beta|}{2}\right). \tag{14}\] 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 \(\left\lVert g\right\rVert_{L^1(\mathbb 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 \[\begin{align*} \sum_{u\notin\mathcal U_s}|\widehat G(s,u)| &\le |c_s|\sum_{j=1}^D \left(\sum_{|u_j|>B|\beta_{s,j}|/2}|I_{s,j}(u_j)|\right) \prod_{h\ne j}\left(\sum_{u_h\in\mathbb Z}|I_{s,h}(u_h)|\right) \\ &=O(B^{D-l}). \tag{15}\end{align*}\] 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 \[T_B(y,z)=\sum_{s\in\mathcal S}\sum_{u\in\mathcal U_s} \widehat G(s,u)\mathrm e(s\cdot y+u\cdot z), \qquad F=\frac{T_B}{1+\delta}.\] 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, \[\left\lVert F\right\rVert_\infty\le1, \qquad \left\lVert F\right\rVert_2\ge\frac{1-2\delta}{1+\delta}\ge1-3\delta.\]

Set \(m=d+D\) and take the containing support \[\mathcal A=\{(s,u):s\in\mathcal S,\ u\in\mathcal U_s\}.\] 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 \[v=\left(\frac{\gamma}{\tau B^D(1+\delta)^3},0\right)\in\mathbb R^{d+D}.\] For \(a=(s,u)\in\mathcal A\), \[|\lambda_a|=|a\cdot v| =\frac{\rho_s}{\tau B^D(1+\delta)^3}>0.\] Using (12) and (7), with both signs already included in \(\mathcal S\), gives \[\begin{align*} \sum_{a\in\mathcal A}|\lambda_a| &=\sum_{s\in\mathcal S}|\mathcal U_s| \frac{\rho_s}{\tau B^D(1+\delta)^3}\\ &\le\frac1{\tau(1+\delta)^2}\sum_{s\in\mathcal S}\Delta_s\rho_s \le\frac1{1+\delta}\sum_{s\in\mathcal S}|c_s|^2 =\frac{M_d}{1+\delta}<1. \end{align*}\] The coefficient bound (11), divided by \(1+\delta\), also gives \[\frac{|\widehat F(a)|^2}{|\lambda_a|} \le\frac{|c_s|^2\tau(1+\delta)^3}{\Delta_s\rho_s} \le\frac{(1+\delta)^3}{1-\delta}=K_\delta^2.\] These are all the assertions of the proposition. ◻

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\), \[ w_i<\frac{L_i}{2L}\qquad(1\le i\le r). \tag{16}\] 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 \[ \frac{q}{2L}+O(q/R+1) \tag{17}\] 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 \[ \mathbb E C_j(s)=p,\qquad p=\frac1{2L}, \tag{18}\] 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 \[a_i\cdot y=s_i\qquad(1\le i\le r)\] 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 \[Z_{i,s}=\frac1{q^{m-1}} \sum_{\substack{y\in\mathbb F_q^m\\a_i\cdot y=s}} \prod_{j\ne i}C_j(a_j\cdot y).\] 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: \[ d(i,s)=q^{b-1}Z_{i,s}. \tag{19}\] Fixing two centers of different types leaves \(q^{m-2}\) possible generating vectors, by pairwise rank two. Their codegree is therefore at most \[ q^{b-2}. \tag{20}\] 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 \[ a_j+a_l=c a_i\quad\text{or}\quad a_j-a_l=c a_i, \qquad c\in\mathbb F_q^{\times},\qquad |cs|_q\le R. \tag{21}\] 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, \[ |E_i|\le 2\binom{r-1}{2}(2R+1)=O(R). \tag{22}\]

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 \[ \tau_q=\frac{1+4LK+2R}{q}=O(q^{-1/2}). \tag{23}\]

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 \[ u(r-1)\tau_q+ 2\binom{u(r-1)}2\frac{2R+1}{q}=O(q^{-1/2}). \tag{24}\]

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 \[\begin{align*} \mathbb E[Z_{i,s}\mid V_{i,s}]&=p^{r-1}+O(q^{-1/2}), \tag{25}\\ \mathbb E[Z_{i,s}^2\mid V_{i,s}]&=p^{2(r-1)}+O(q^{-1/2}). \tag{26}\end{align*}\] 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 \[\mathbb E\bigl[(Z_{i,s}-p^{r-1})^2\mid V_{i,s}\bigr] =O(q^{-1/2}).\] 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 \[q^{7/8}q^{b-2}=O(q^{-1/8}D_q).\] 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 5 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 \[ H=(1+o(1))\frac q{2L}. \tag{27}\]

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{\mathbb 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 \[J=\left[\frac{t-1/2}{q},\frac{t+L_i-1/2}{q}\right],\] 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\), \[\frac{w_i}{H}<\frac{L_i}{q}\qquad(1\le i\le r).\] 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. ◻