Proof. Put \(y_0=u/(T\beta)\) and complete the square. Fourier inversion reduces the bracket in (1) to the exact expression \[\int_\mathbb R\widehat g(\xi)\mathrm e(\xi y_0) \mathrm e\bigl(-\xi^2/(2T\beta)\bigr)\,d\xi.\] 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 \(\mathrm e(\mathop{\mathrm{sgn}}(\beta)/8)/\sqrt{T|\beta|}\). Finally, replacing \(\mathrm e(-\xi^2/(2T\beta))\) by \(1\) costs at most \[\frac{\pi}{T|\beta|}\int_\mathbb R\xi^2|\widehat g(\xi)|\,d\xi,\] independently of \(y_0\). ◻

Proof. Write \(d=\mathop{\mathrm{sgn}}(\phi'')\). If \(t_x\in I\), the change of variable \[y=(t-t_x) \left(\frac{2d[\phi(t)-\phi(t_x)-\phi'(t_x)(t-t_x)]} {(t-t_x)^2}\right)^{1/2}\] 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 \(\mathop{\mathrm{supp}}f\) is separated from the endpoints of \(I\). At \(y=0\) their value is \(f(t_x)/\sqrt{|\phi''(t_x)|}\). Lemma 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'(\mathop{\mathrm{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 \(\mathrm 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 \(\mathrm 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 (OpenAI 2026b, 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 \[A_{2\ell,j}=\Re\bigl(d_j\mathrm e(jt_\ell)\bigr),\qquad A_{2\ell+1,j}=\Im\bigl(d_j\mathrm e(jt_\ell)\bigr).\] 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 \(\lVert A(p^{(J)}-p)\rVert_\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 4 to the columns indexed by \(S_h\). Reverse all its signs if necessary so that their sum is nonpositive, and put \[p_j^{(h-1)}= \begin{cases} p_j^{(h)}+2^{-h}\xi_j,&j\in S_h,\\ p_j^{(h)},&j\notin S_h. \end{cases}\] 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 \[s_h\le\min(n,2^h\mu),\qquad \lVert A(p^{(h-1)}-p^{(h)})\rVert_\infty \le C2^{-h}\sqrt{s_h\log(80n/s_h)}.\] The last inequality is used only at nonempty stages. Monotonicity of \(s\log(80n/s)\) on \((0,n]\) gives \[s_h\log(80n/s_h)\le2^h\mu\log(80n/\mu).\] 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\), \[ \lVert A(p'-p)\rVert_\infty \le1+C\sqrt{\mu\log(80n/\mu)}. \tag{5}\]

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(\mathrm e(t_\ell))\) are each bounded by twice the left side of (5). 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 \[|Q(z)|\le S\max(1,|z|^{n-1}),\qquad \max_{|z|\le1+1/n}|Q(z)|\le\exp(1)S.\] Cauchy’s estimate in disks of radius \(1/n\) centered on the unit circle therefore gives \[\left|\frac{d}{dt}Q(\mathrm e(t))\right|\le2\pi\exp(1)nS.\] Every point of \(\mathbb T\) is within \(1/(40n)\) of the grid. Hence \(S\le\max_\ell|Q(\mathrm e(t_\ell))|+(\pi\exp(1)/20)S\). Since \(\pi\exp(1)/20<1\), this proves (4). 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 \[I_\beta(u)=\int_{-1/2}^{1/2}g(y)\mathrm e(T\beta y^2/2-uy)\,dy \qquad(u\in\mathbb Z).\] Lemma 1 and \(L_\beta/(T|\beta|)\to1\) give, uniformly in \(u\), \[ \sqrt{L_\beta}|I_\beta(u)|\le1+q \tag{8}\] for all sufficiently large \(T\). The coefficients outside the stated interval have a small sum of absolute values. Indeed, \(\mathop{\mathrm{supp}}g\) is separated from both endpoints, so on a neighborhood of this support, \[|T\beta y-u|\ge c_{g,\beta}(T+|u|) \quad\text{if }|u|>T|\beta|/2.\] 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 \[ \sum_{|u|>\lfloor T|\beta|/2\rfloor}|I_\beta(u)|=O_{g,\beta}(T^{-1}). \tag{9}\]

For the retained indices define \(Z_u=\sqrt{L_\beta}I_\beta(u)/(1+q)\). By (8), \(|Z_u|\le1\). Parseval’s identity and (9) show that, for large \(T\), \[\frac1{L_\beta}\sum_u|Z_u|^2\ge\frac{1-2q}{(1+q)^2}.\] Since \(1-|Z_u|\le1-|Z_u|^2\), the defect \(\mu=\frac12\sum_u(1-|Z_u|)\) satisfies \[\frac{\mu}{L_\beta}\le\frac{4q+q^2}{2(1+q)^2}\le2q<1/2.\] Apply Lemma 5 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\mathrm e(uy)\) satisfies \[\lVert f_\beta-\frac 1{1+q}\sum_u I_\beta(u)\mathrm e(u\,\cdot)\rVert_\infty \le C\left(L_\beta^{-1/2}+\sqrt{q\log(80/q)}\right).\] 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 (9), 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 6. 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 \[p_j(y_1,\ldots,y_j) =p_{j-1}(y_1,\ldots,y_{j-1}) +\tfrac12(1-p_{j-1}(y_1,\ldots,y_{j-1})^2)\cos(2\pi y_j).\] 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 \[M_j-M_{j-1}=\tfrac18\int(1-p_{j-1}^2)^2 \ge\tfrac18(1-M_{j-1})^2.\] 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 \[p_d(y)=\sum_{s\in\mathcal S}b_s\mathrm e(s\cdot y), \qquad b_s\ne0.\] 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\mathbb 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\mathbb 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\mathbb R^d\) such that \[s_j\cdot W_j^1 =\frac{|b_{s_j}|^2} {\rho_{s_j}\prod_{\ell\ne j}|s_j\cdot W_\ell^0|}.\] Set \(W_j=W_j^0+\tau W_j^1\). As \(\tau\downarrow0\), \[\frac1\tau\prod_{j=1}^D|s\cdot W_j| \longrightarrow\frac{|b_s|^2}{\rho_s} \qquad(s\in\mathcal S).\] 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}|\), \[ (1-\delta)\frac{\tau|b_s|^2}{\rho_s} \le\Delta_s\le (1+\delta)\frac{\tau|b_s|^2}{\rho_s} \qquad(s\in\mathcal S). \tag{10}\]

All these data are now fixed. Apply Lemma 7 to the finite list of nonzero \(\beta_{s,j}\), choosing \(\alpha>0\) small enough that \[ \left(\sum_{s\in\mathcal S}|b_s|\right) D\alpha(1+\alpha)^{D-1}\le\delta. \tag{11}\] With the resulting common cutoff \(g\) and sufficiently large \(T\), define \[F(y,z)=\sum_{s\in\mathcal S}b_s\mathrm e(s\cdot y) \prod_{j=1}^D f_{\beta_{s,j}}(z_j), \qquad (y,z)\in\mathbb T^d\times\mathbb T^D.\] 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 \[\left(\prod_{j=1}^Dg(z_j)\right) p_d\left(y+\frac T2\sum_{j=1}^D W_jz_j^2\right),\] 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 (11). Therefore \(\lVert F\rVert_\infty\le1+\delta\).

Over each old frequency \(s\), the Fourier support of \(F\) is the full box \[a=(s,u_1,\ldots,u_D),\qquad |u_j|\le\lfloor T|\beta_{s,j}|/2\rfloor.\] 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 \[ (1-\delta)T^D\Delta_s\le n_s\le(1+\delta)T^D\Delta_s \qquad(s\in\mathcal S), \tag{12}\] 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 \[v=\left(\frac{\gamma}{\tau T^D(1+\delta)^3},0\right)\in\mathbb R^{d+D}.\] For every frequency \(a\) over \(s\), its weight is \(w_a=\rho_s/(\tau T^D(1+\delta)^3)>0\). Combining (10) and (12) gives \[\begin{align*} \frac{(1-\delta)^2}{(1+\delta)^3}|b_s|^2 &\le\sum_{a\text{ over }s}w_a\le\frac{|b_s|^2}{1+\delta}, \tag{13}\\ 1+\delta&\le\frac{|c_a|^2}{w_a} \le\frac{(1+\delta)^3}{(1-\delta)^2}. \tag{14}\end{align*}\] 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 (14) 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 (6). 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 8. Fix \(\delta\) and choose the data of Proposition 6. Thus \[F(y)=\sum_{a\in\mathcal A}c_a\mathrm e(a\cdot y),\qquad \lambda_a=a\cdot v,\qquad w_a=|\lambda_a|,\] where \(F\) is real, \(\mathcal A=-\mathcal A\), and \[ \|F\|_\infty\le1+\delta,\qquad 1-C\delta\le\sum_{a\in\mathcal A}w_a<1,\qquad 1\le m_a:=\frac{|c_a|}{\sqrt{w_a}}\le1+C\delta\le2. \tag{18}\] 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.