A sieve for finitely many shifts

We use the classical additive large sieve in the following form. If complex coefficients \(c_n\) are supported on an interval of \(M\) consecutive integers and \(Q\ge1\), then \[ \sum_{q\le Q}\ \sum_{\substack{h\bmod q\\(h,q)=1}} \left|\sum_n c_n e_q(hn)\right|^2 \ll (M+Q^2)\sum_n|c_n|^2. \tag{1}\] Indeed, the reduced fractions with denominators at most \(Q\) are \(Q^{-2}\)-separated modulo one, so this is the separated-frequency inequality of Montgomery and Vaughan (Montgomery and Vaughan 1973, Theorem 1); see also Green and Harper (Green and Harper 2014, Proposition 3.1). The estimate applies to arbitrary complex coefficients. Restricting its outer sum to prime or squarefree moduli is permitted by nonnegativity.

The two-infinite-set theorem

It remains to prove the following technical theorem.

Together with Lemma 3, this proves Theorem 1: a counterexample to the latter would have both summands infinite and would therefore contradict Theorem 4.

For the remainder of the proof, suppose to the contrary that infinite sets \(A,B\subseteq\mathbb N_0\) satisfy this eventual equality. Fix a threshold \(N\) so that both of the following statements hold: \[ \mathcal P\cap(N,\infty)\subseteq A+B, \qquad (A+B)\cap(N,\infty)\subseteq\mathcal P. \tag{3}\] The first is prime coverage; the second excludes composite sums. Choose an integer \(N_*>|N|+10\) and put \(D=-B\). Constants in \(O(\cdot)\) and \(\ll\) may depend on these fixed data; additional dependencies will be indicated where the order of parameters matters.

Complementary residue supports

For every prime \(p\), the residue sets \[\{a\bmod p:a\in A,\ a>p+N_*\},\qquad \{d\bmod p:d\in D,\ -d>p+N_*\}\] are disjoint. Indeed, a common residue would make \(a-d\) a positive multiple of \(p\) larger than \(p\) and \(N\), although \(a-d\in A+B\) must be prime. Both sets are nonempty by infinitude. Choose a partition \(S_p,S_p^c\) of \(\mathbb F_p\) containing the respective sets, and write \(\sigma_p=|S_p|/p\). Thus \(0<\sigma_p<1\). Residues in neither tail support may be assigned to either part.

Sizes of the summands

The following bounds are due to Elsholtz (Elsholtz 2006, Theorem 1.9). We include the large-sieve and collision argument in the present nonnegative-integer convention.

Collision stability

The congruent-pair count underlying Gallagher’s larger sieve (Gallagher 1971) also measures how close a summand is to uniform on its residue support. This quantitative use of the larger sieve is central to Green and Harper’s inverse-sieve arguments (Green and Harper 2014, Equation (2.1) and Lemma 2.4). We need the following weighted form for the two complementary supports.

Write \(U_E\) for uniform probability on a finite nonempty set \(E\). If \(\mu\) is a probability measure on integers, write \(\mu_p\) for its projection modulo \(p\). The norms in the next statement are counting norms of probability mass functions.

One useful form of the lemma does not require pointwise bounded test functions. If \(f_p:\mathbb F_p\to\mathbb C\) has probability squared norm at most one, then \[ \left|\mathbb E_\mu f_p-\mathbb E_{S_p}f_p\right|^2 \le p\|\mu_p-U_{S_p}\|_2^2, \tag{8}\] by Cauchy–Schwarz. Thus these squared errors have total \(\log p/p\)-weighted sum \(O_b(\log\log X)\); the same holds on the other side. In particular this applies to tests bounded by one. By Lemma 5, uniform measures on \[A\cap[X^{9/10},X],\qquad D\cap[-X,-X^{9/10}]\] meet the hypotheses for a fixed \(b\): their sizes are \(\gg\sqrt X/(\log X)^3\), while the discarded initial pieces have size \(o(\sqrt X/(\log X)^3)\).

A budget for centered tensor coordinates

Throughout this section we reset the large parameters by \[\log X=\exp L,\qquad R=\sqrt X.\] Set \[A_0=A\cap(R+N_*,X],\qquad D_0=D\cap[-X,-R-N_*),\qquad m_A=|A_0|,\quad m_D=|D_0|.\] Both sets are nonempty for large \(L\), by (4). For every prime \(p\le R\), their reductions are supported on \(S_p\) and \(T_p:=S_p^c\), respectively. Write \(\kappa_p=|T_p|/|S_p|=(1-\sigma_p)/\sigma_p\).

Apply Lemma 6 at \(Y=X(\log X)^{40}\), using the uniform measures on its two full tails. By (4), their largest point masses are at most \((\log Y)^4/\sqrt Y\) for large \(Y\). The associated prime cutoff is \(\sqrt Y/(\log Y)^5>R\). Since \(\sigma_p^{-1}+(1-\sigma_p)^{-1}-4 =\kappa_p+\kappa_p^{-1}-2\), it follows that \[ \sum_{p\le R}(\kappa_p+\kappa_p^{-1}-2)\frac{\log p}{p}\ll L, \qquad \sum_{p\le R}\frac{|\log\kappa_p|}{p}\ll\sqrt L . \tag{61}\] For the second assertion, use \((\log t)^2\le t+t^{-1}-2\) for \(t>0\) and Cauchy–Schwarz: \[\sum_{p\le R}\frac{|\log\kappa_p|}{p} \le \left(\sum_{p\le R} \frac{(\log\kappa_p)^2\log p}{p}\right)^{1/2} \left(\sum_p\frac1{p\log p}\right)^{1/2}.\] The last prime sum converges.

Let \(\mathbf e_x\) be the standard point vector in \(\mathbb C^{\mathbb F_p}\). Let \(Q_{S_p}\) be the orthogonal projection onto \[\mathcal H_{S_p} =\left\{f\in\mathbb C^{\mathbb F_p}: \mathop{\mathrm{supp}}f\subseteq S_p,\ \sum_x f(x)=0\right\},\] and define \(Q_{T_p}\) and \(\mathcal H_{T_p}\) similarly. All these inner products use counting measure. For squarefree \(t\) whose prime factors are at most \(R\), put \[B_A(t)= \left\|\frac1{m_A}\sum_{a\in A_0} \bigotimes_{p\mid t}Q_{S_p}\mathbf e_{a\bmod p}\right\|^2, \qquad B_A(1)=1,\] and define \(B_D(t)\) with \(D_0,T_p\).

The precise energy identity we need is \[ \sum_{\substack{h\bmod q\\(h,q)=1}} \left|\frac1{m_A}\sum_{a\in A_0}e_q(ha)\right|^2 =\sum_{t\mid q}tB_A(t)\prod_{p\mid q/t}\kappa_p \qquad(q\le R,\ q\ {\rm squarefree}). \tag{62}\] Indeed, the Ramanujan kernel factors over the primes of \(q\). For \(x,y\in S_p\), \[\sum_{h\in\mathbb F_p^*}e_p(h(x-y)) =p\mathbf 1_{x=y}-1 =\kappa_p+ p\langle Q_{S_p}\mathbf e_x,Q_{S_p}\mathbf e_y\rangle .\] Expand the product of these identities and average over two independent uniform elements of \(A_0\). The term with centered factors at precisely the primes of \(t\) is the corresponding term on the right of (62). For \(D_0\), the same identity holds with \(\kappa_p^{-1}\). In particular all terms in both expansions are nonnegative.

Write \[\mathcal B_L=\{p:.05L\le\log\log p\le.9L\}.\] For each fixed \(C_*>0\), let \(\mathcal T_{C_*}\) be the set of products of at most \(C_*L\) distinct primes from \(\mathcal B_L\), including 1. We claim that \[ \sum_{t\in\mathcal T_{C_*}}B_A(t) \le \exp(o(L))\frac R{m_A}, \qquad \sum_{t\in\mathcal T_{C_*}}B_D(t) \le \exp(o(L))\frac R{m_D}. \tag{63}\] The error terms are uniform over \(t\) for each fixed \(C_*\). To prove this, note first that \[\log t\le C_*L\exp(.9L)=o(\log X).\] Consequently \(t<R\), and \(U=R/t=X^{1/2-o(1)}\), uniformly. Among the positive integers \(u\le U\), the proportion failing to be squarefree is at most \(\sum_p p^{-2}<1\). The proportion not coprime to \(t\) is at most \[\sum_{p\mid t}\frac1p \le C_*L\exp\bigl(-\exp(.05L)\bigr)=o(1).\] Also, by (61), \[\frac1{\lfloor U\rfloor}\sum_{u\le U} \sum_{p\mid u}|\log\kappa_p| \ll\sum_{p\le U}\frac{|\log\kappa_p|}{p} \ll\sqrt L .\] Markov’s inequality shows that only \(O(L^{-1/4})\) of these integers have the inner sum exceeding \(L^{3/4}\). Thus at least \(cU\) integers, for an absolute \(c>0\) and all sufficiently large \(L\), are squarefree, coprime to \(t\), and satisfy \[\prod_{p\mid u}\kappa_p\ge e^{-L^{3/4}}, \qquad \prod_{p\mid u}\kappa_p^{-1}\ge e^{-L^{3/4}}.\] The additive large sieve, applied to the probability measure on \(A_0\), bounds the sum of the left side of (62) over squarefree \(q\le R\) by \(CR^2/m_A\). Interchanging the nonnegative terms on the right, and retaining only \(t\in\mathcal T_{C_*}\), gives \[\frac{CR^2}{m_A} \ge \sum_{t\in\mathcal T_{C_*}}tB_A(t) \sum_{\substack{u\le R/t\\u\ {\rm squarefree}\\(u,t)=1}} \prod_{p\mid u}\kappa_p \ge cR e^{-L^{3/4}} \sum_{t\in\mathcal T_{C_*}}B_A(t).\] This proves the first assertion, and the reciprocal argument proves the second. Notice in particular the consequence of the \(t=1\) terms: \[ m_A,m_D\le R\exp(o(L)). \tag{64}\]

A contracting local kernel from a sparse transform

Fix a sufficiently small absolute \(\varepsilon_0>0\); all conditions on its size below are absolute. Choose \(0<\delta_0\le\varepsilon_0^2\). Suppose, for a sequence of arbitrarily large \(L\), that (60) fails. Let \[\mathcal S=\{p\in\mathcal B_L: 1/3\le\sigma_p\le2/3,\ \gamma_p<\delta_0\}, \qquad H=\sum_{p\in\mathcal S}\frac1p.\] Mertens’ theorem gives \(\sum_{p\in\mathcal B_L}1/p=.85L+o(1)\). Outside the balanced range, \(\kappa_p+\kappa_p^{-1}-2\ge1/2\), so (61) gives \[\sum_{\substack{p\in\mathcal B_L\\ \sigma_p\notin[1/3,2/3]}}\frac1p \ll L\exp(-.05L)=o(1).\] It follows that \(H\ge .70L-o(L)\). We shall use the weaker bound \[ H\ge .68L, \tag{65}\] which remains valid after deleting any one prime of \(\mathcal S\).

For \(p\in\mathcal S\) define \[E_p=\{v\in\mathbb F_p:|g_p(v)|>1\}.\] This set is symmetric, avoids zero, and satisfies \[ |E_p|\le\varepsilon_0p,\qquad \sum_{v\in E_p}|g_p(v)|^2\ge(1-\varepsilon_0^2)p. \tag{66}\] Indeed, \(|E_p|\le\sum_v|g_p(v)|<\delta_0p\); on its complement, \(|g_p(v)|^2\le|g_p(v)|\). Put \(t_0=.85\) and \[b_p(x)=\frac{t_0}{p}\sum_{h\in E_p}e_p(hx).\] These functions are real. Let \(\Pi_p\) be the orthogonal projection in \(\mathbb C^{\mathbb F_p}\) onto the additive Fourier modes in \(E_p\). The raw matrix with entries \(b_p(x-y)\) is \(t_0\Pi_p\). Furthermore, \[\Pi_p\mathbf1=0,\qquad \|\Pi_pF_p-F_p\|\le\varepsilon_0\sqrt p, \qquad \|\Pi_pF_p\|^2\ge(1-\varepsilon_0^2)p.\] The latter assertions follow by Parseval from (66).

Let \(B_p^{(2)}\) denote the raw matrix with entries \(b_p(x-y)^2\). Its additive Fourier eigenvalue at \(s\) is \[\frac{t_0^2}{p}\#\{(h,h')\in E_p^2:h+h'=s\}.\] Consequently \[ \|B_p^{(2)}\|\le t_0^2\varepsilon_0,\qquad |b_p(x)|\le t_0\varepsilon_0. \tag{67}\] For later use, if \(e_p^*=|E_p|/p\), direct orthogonality gives \[\begin{align*} \frac1{p-1}\sum_{x\ne0}b_p(x) &=-\frac{t_0e_p^*}{p-1},\\ \frac1{p-1}\sum_{x\ne0}b_p(x)^2 &=\frac{t_0^2(e_p^*-(e_p^*)^2)}{p-1}. \tag{68}\end{align*}\] In particular both unit means are \(O(\varepsilon_0/p)\).

For a kernel \(h(x-y)\), let \(h\) also denote its raw matrix, and set \[u_S=|S_p|^{-1}\mathbf1_{S_p},\qquad u_T=|T_p|^{-1}\mathbf1_{T_p}.\] The map from \(\mathbb C\oplus\mathcal H_{T_p}\) to \(\mathbb C\oplus\mathcal H_{S_p}\) defined by \[L_p[h]= \begin{pmatrix} u_S^*hu_T&u_S^*hQ_{T_p}\\ Q_{S_p}hu_T&Q_{S_p}hQ_{T_p} \end{pmatrix}\] represents the kernel on the coordinates \((1,Q_{S_p}\mathbf e_x)\), \((1,Q_{T_p}\mathbf e_y)\). Indeed \(u_S+Q_{S_p}\mathbf e_x=\mathbf e_x\) for \(x\in S_p\), and likewise on \(T_p\). Define \[L_p(u,v)=L_p[(1+ub_p)(1+vb_p)],\qquad U_p(u,v)=\frac1{p-1}\sum_{x\ne0}(1+ub_p(x))(1+vb_p(x)).\]

Tensoring and truncating the kernel

Choose a sufficiently large fixed \(C_K>0\), as specified below, and put \(K=\lceil C_KL\rceil\). Define the nonnegative function \[ W(n)= \left(\sum_{\substack{I\subseteq\mathcal S\\|I|\le K}} \prod_{p\in I}b_p(n)\right)^2. \tag{70}\] For a polynomial \(P(u,v)\), scalar- or operator-valued, let \(\mathcal R_K P\) be the sum of its Taylor coefficients with degree at most \(K\) in each variable, evaluated at \((1,1)\). Set \[\mathcal L(u,v)=\bigotimes_{p\in\mathcal S}L_p(u,v),\qquad \mathcal U(u,v)=\prod_{p\in\mathcal S}U_p(u,v),\qquad U=\mathcal U(1,1).\] The matrix \(\mathcal R_K\mathcal L\) represents \(W(a-d)\) between the full tensor coordinates. Similarly, \(\mathcal R_K\mathcal U\) is the mean of \(W\) on independent uniform unit residues.

Let \(r_0=1.03\). Lemma 12 and \(H\le .85L+o(L)\) bound the norms of both polynomials on \(|u|,|v|\le r_0\) by \(\exp(C_0L)\) with an absolute \(C_0\). Cauchy’s coefficient formula applies to the finite-dimensional operator spaces as well as to scalars: if \(P_{ij}\) is the coefficient of \(u^iv^j\), then \(\|P_{ij}\|\le\exp(C_0L)r_0^{-i-j}\). Summing the geometric series over \(i>K\) or \(j>K\), we obtain \[ \|\mathcal R_K\mathcal L-\mathcal L(1,1)\| +|\mathcal R_K\mathcal U-U| \ll \exp(C_0L)r_0^{-K}. \tag{71}\] We also have \(U=\exp(O(\varepsilon_0L))>0\), and \[\|\mathcal L(1,1)\| \le U\prod_{p\in\mathcal S}(1-1.6/p) \le Ue^{-1.6H}.\] Choose the fixed \(C_K\) so large that the right side of (71) is \(o(Ue^{-1.6H})\). For example, after bounding all the displayed absolute constants, one can ensure an error at most \(e^{-5L}\).

There is no loss from the dimension of these tensor spaces. To see explicitly which coordinates are used, write \[V_A=\frac1{m_A}\sum_{a\in A_0} \bigotimes_{p\in\mathcal S}(1,Q_{S_p}\mathbf e_{a\bmod p}), \qquad V_D=\frac1{m_D}\sum_{d\in D_0} \bigotimes_{p\in\mathcal S}(1,Q_{T_p}\mathbf e_{d\bmod p}).\] The tensor space is the orthogonal direct sum of its centered subset modes. The squared norm of the mode indexed by the primes of \(t\) is \(B_A(t)\), respectively \(B_D(t)\). Each monomial retained in \(\mathcal R_K\mathcal L\) involves at most \(2K\) primes. At every other prime the local constant kernel has only a scalar block. Consequently \(\mathcal R_K\mathcal L=P_A(\mathcal R_K\mathcal L)P_D\), where \(P_A,P_D\) retain only subset modes with at most \(2K\) centered factors. Equation (63), with any fixed \(C_*>2C_K\), gives \[\|P_AV_A\|^2\le e^{o(L)}R/m_A,\qquad \|P_DV_D\|^2\le e^{o(L)}R/m_D.\] The kernel identity, the operator norm bound, and Cauchy–Schwarz now give \[ \frac1{m_Am_D}\sum_{a\in A_0}\sum_{d\in D_0}W(a-d) \le U\exp(-1.6H+o(L)) \left(\frac{R^2}{m_Am_D}\right)^{1/2}. \tag{72}\] Every assertion of this subsection is uniform under the deletion of one prime from \(\mathcal S\). We may therefore make such a deletion, and redefine the polynomials and \(W\) accordingly, when addressing an exceptional character below.

The prime mean of the weight

Set \[ \log Q_b=2K\exp(.9L). \tag{73}\] Products of at most \(2K\) primes from \(\mathcal S\) are at most \(Q_b\). We first record explicitly the analytic estimate used to average our weight.

We now perform the possible deletion promised after (72), using the one-prime removal of an exceptional conductor as in (Ford et al. 2018, sec. 7, following Lemma 7.1). If the exceptional primitive character of conductor at most \(Q_b\) has conductor equal to a product of primes in \(\mathcal S\), delete one of those primes from \(\mathcal S\). Otherwise make no deletion. Keep \(K,Q_b\) fixed and redefine \(W,\mathcal L,\mathcal U,U,H\) using the resulting set. Equations (65) and (72) continue to hold. Every primitive character induced by a monomial of \(W\) has squarefree conductor formed from primes of \(\mathcal S\); hence none of those induced characters is the exceptional one.

Fix from now on a nonzero nonnegative smooth \(\phi\) compactly supported in \((1/2,1)\). For \(j=1,2\) and a multiplicative character \(\lambda\bmod p\), write \[c_{p,j}(\lambda) =\frac1{p-1}\sum_{x\ne0}b_p(x)^j\overline{\lambda(x)}.\] Multiplicative Fourier inversion expresses \(b_p(x)^j\) as \(\sum_\lambda c_{p,j}(\lambda)\lambda(x)\) on \(\mathbb F_p^*\). Equations (67) and (68), followed by Cauchy–Schwarz, give \[ |c_{p,j}(\lambda)|\ll p^{-1/2}\quad(\lambda\ne1,\ j=1,2), \qquad |c_{p,j}(1)|\ll p^{-1}\quad(j=1,2). \tag{77}\] For example the mean of \(b_p^2\) on units is \(O(1/p)\), and the mean of \(b_p^4\) is at most \(\|b_p\|_\infty^2\) times that mean, also \(O(1/p)\). All constants here are absolute.

Expand (70) by its two subsets \(I,J\), and expand each participating local factor multiplicatively. For an integer coprime to every prime of \(\mathcal S\), group the resulting terms by the primitive character they induce. This gives \[ W(n)=\sum_{\substack{\chi\ {\rm primitive}\\ \operatorname{cond}(\chi)\le Q_b}} C(\chi)\chi(n) \qquad \left((n,\prod_{p\in\mathcal S}p)=1\right). \tag{78}\] Only squarefree conductors supported on \(\mathcal S\) occur. The conductor bound follows because \(|I\cup J|\le2K\).

For a fixed primitive character \(\chi\) of conductor \(d\), its local nonprincipal character is prescribed at every \(p\mid d\). There are three possible statuses for such a prime: membership in \(I\) alone, in \(J\) alone, or in both. The sum of the absolute coefficient costs at that prime is at most \(C/\sqrt p\) by (77). For \(p\nmid d\), the absent status contributes 1 and the other three statuses use principal coefficients, with total cost at most \(1+C/p\). Discarding the degree restrictions only enlarges this nonnegative majorant. Therefore even the sum of the absolute values of all terms grouped into \(C(\chi)\) is bounded by \[ \prod_{p\mid d}\frac C{\sqrt p} \prod_{\substack{p\in\mathcal S\\p\nmid d}}(1+C/p) \le e^{C'L}. \tag{79}\] In the last inequality all conductor-prime factors are at most 1 for sufficiently large \(L\), and \(\sum_{p\in\mathcal S}1/p=O(L)\). This is a uniform bound for each grouped coefficient; we will multiply it by the total error in (74). The principal coefficient retains its signs and satisfies exactly \[C(1)=\mathcal R_K\mathcal U =U+o(Ue^{-1.6H})=(1+o(1))U.\]

Every prime in the support of \(\phi(p/X)\) is larger than every prime in \(\mathcal S\), because \(\exp(\exp(.9L))=X^{o(1)}\). Thus (78) holds on all desired prime inputs. Apply (74) to the grouped sum, taking its fixed \(D_1\) larger than the absolute constants in (79) and in \(U=\exp(O(\varepsilon_0L))\). No exceptional character occurs, by our deletion. The resulting error is \(o(UX)\).

To pass from von Mangoldt sums to primes, it is harmless that the grouped identity was only asserted on units. Indeed the number of primitive characters of conductor at most \(Q_b\) is at most \(Q_b^2\), and \[\sum_{\substack{n\le X\\n\ {\rm a\ prime\ power}\\ n\ {\rm not\ prime}}}\Lambda(n) \ll X^{1/2}(\log X)^2.\] The absolute contribution of all these terms to the grouped character sum is at most \[e^{C'L}Q_b^2 X^{1/2}(\log X)^2 =X^{1/2+o(1)}=o(UX).\] This bound also covers prime powers whose prime base lies in \(\mathcal S\), for which extension from unit classes can change the value of the grouped expansion. We have proved \[ \sum_{p\ {\rm prime}}(\log p)\phi(p/X)W(p) =(1+o(1))UX\int_0^\infty\phi(t)\,dt. \tag{80}\]

Using coverage of every sufficiently large prime

The elementary bound \(|b_p(n)|\le1\) gives, with \(M_{\mathcal S}=|\mathcal S|\), \[W(n)\le (K+1)^2(1+M_{\mathcal S})^{2K} \le\exp\bigl(O(K\exp(.9L))\bigr)=X^{o(1)}\] uniformly in \(n\). By eventual prime coverage, every prime counted in (80), for sufficiently large \(L\), has at least one representation \(p=a-d\) with \(a\in A\), \(d\in D\). Since \(a,-d\ge0\) and \(p<X\), every such representation has \(a,-d\le X\).

Remove all primes possessing a representation with \(a\le R+N_*\) or \(-d\le R+N_*\). The number of removed primes is at most \[A(R+N_*)B(X)+A(X)B(R+N_*)=X^{3/4+o(1)}\] by (4). Their contribution to the left side of (80) is still \(X^{3/4+o(1)}\), by the uniform bound on \(W\), boundedness of \(\phi\), and \(\log p\le\log X\). This is \(o(UX)\). Every remaining prime has a representation by a pair in \(A_0\times D_0\). Choose one such pair for each prime. Different primes give different pairs, and the other pairs have nonnegative weight. Consequently, for a fixed \(c_\phi>0\), \[ \frac1{m_Am_D}\sum_{a\in A_0,d\in D_0}W(a-d) \ge c_\phi U\frac{X}{m_Am_D\log X}. \tag{81}\] Here we used \((\log p)\phi(p/X)\le\|\phi\|_\infty\log X\) to remove the prime weight from the surviving lower bound in (80). This step uses coverage of the full prime set.

Put \(z=X/(m_Am_D)=R^2/(m_Am_D)\). Equation (64) gives \(z\ge e^{-o(L)}\). Comparing (81) with (72), and canceling the positive \(U\), gives \[c_\phi z e^{-L} \le e^{-1.6H+o(L)}\sqrt z.\] Since \(H\ge .68L\), this implies \[\sqrt z\le\exp\bigl(-.088L+o(L)\bigr),\] contradicting \(z\ge e^{-o(L)}\). Thus (60) cannot fail along an unbounded sequence, and Proposition 11 follows.

The diagrams and their elementary density bound

A diagram of depth \(l\) uses a full ordered binary tree with \(r=2^l\) leaves. Its leaf variables \(M_i\) take values in \(U\). For a node \(n\), write \(M_n\) for the product of the variables at its descendant leaves. Choose frequencies \(s_n\in U\) at every node, a constant \(D'\in U\), and unit constants \(C_{n,+},C_{n,-},u_n\) at the internal nodes. There are also two current entries \(X_{n,+},X_{n,-}\): these are fixed units at the root and are propagated down the tree as follows. At an internal node, set \[ \begin{split} H_{n,\pm}&=X_{n,\pm}C_{n,\pm}M_{n,\pm},\\ p_n&=\frac{s_{n,+}H_{n,-}-s_{n,-}H_{n,+}}{s_nu_n},\\ y_n&=\frac{s_n}{D'H_{n,+}H_{n,-}},\\ y_{n,\pm}&=\frac{s_{n,\pm}}{D'p_nu_nH_{n,\pm}}. \end{split} \tag{83}\] The new ordered pair of current entries in child \(n,\pm\), when that child is internal, is \((p_n,X_{n,\pm})\). The fixed constants are required to be consistent in the sense that \[H_{n,\pm,+}H_{n,\pm,-}=p_nu_nH_{n,\pm}.\] Equivalently, this is the condition \(C_{n,\pm,+}C_{n,\pm,-}=u_nC_{n,\pm}\) on the fixed constants. It ensures that the formula for a child’s argument in its parent’s display agrees with its own formula for \(y_n\).

All these operations take place in \(\mathbb F_q\). If a reconstructed \(p_n\) is zero, the entire diagram value is defined to be zero, and no division by that value is performed. Otherwise define \(W\) to be the product of \(g(y_i)\) or \(\overline{g(y_i)}\) over the leaves, choosing opposite conjugations on the two leaves of every bottom sibling pair. The choices on different pairs may be arbitrary. For depth zero set \(y_1=c/M_1\), with a fixed \(c\in U\), and take either \(g(y_1)\) or its conjugate.

We first prove the density estimate behind (84). Directly from (83), on valid points, \[ y_n=y_{n,+}-y_{n,-},\qquad \frac{y_{n,+}}{y_{n,-}} =\frac{s_{n,+}}{s_{n,-}}\frac{H_{n,-}}{H_{n,+}}. \tag{86}\] Expose first the product of all leaf variables. It is uniform on \(U\), so the root argument is uniform on \(U\). At each successive split, conditionally on the exposed parent product and all ancestor splits, \(M_{n,+}\) is uniform on \(U\) and \(M_{n,-}\) is determined by their product. This follows either by counting the fibers of the product map or by induction on the two disjoint sets of descendant leaves. The current entries are already known at this point. Consequently the ratio on the right of (86) is a fixed unit times \(M_{n,+}^{-2}\). A prescribed valid ordered pair of child arguments therefore has conditional probability at most \(2/(q-1)\).

A specified vector of leaf arguments determines all its intermediate arguments by taking the indicated differences. Its probability on the valid part of the sample space is at most \(2^{r-1}(q-1)^{-r}\). Thus the joint leaf-argument measure, with invalid points assigned mass zero, is dominated by \(2^{r-1}\) times independent uniform unit measure. It follows that \[\mathbb E|W|^2 \leq 2^{r-1}\left(\frac q{q-1}\right)^r \bigl(\mathbb E_{x\in\mathbb F_q}|g(x)|^2\bigr)^r \leq3^r.\] Stopping the same exposure at any horizontal level gives the analogous domination for the arguments at that level. In particular, the arguments at the roots of the bottom quartets have joint density bounded by a constant depending only on \(l\) relative to independent uniform unit arguments. These are bounds for nonnegative integrals; they place no pointwise boundedness assumption on \(g\).

The cycle reduction and the quartet estimates

We turn to the paired estimate (85). The subgroup distribution in the statement has the following equivalent description. First choose independent uniform component totals. In each diagram, independently given those totals, choose its leaf variables uniformly subject to the specified product in each component. Every product fiber has the same cardinality, so this is indeed uniform on the subgroup. Each diagram separately has independent uniform leaf variables.

In the first diagram make a bipartite multigraph whose vertices are its \(b\) component sets and its \(r/4\) bottom quartets, with one edge for each leaf. It has \(r\) edges and at most \(r\) vertices, and no isolated vertices. A forest on nonempty vertex sets has fewer edges than vertices, so the graph contains a cycle, possibly two parallel edges. Choose a simple such cycle. On its leaf variables multiply alternately by \(z\) and \(z^{-1}\), with \(z\in U\). This preserves every component product and every quartet product. Let \(\mathcal P\) denote averaging over this action, an orthogonal projection in \(L^2(U^r)\).

Let \(\mathcal T\) be the collection of component totals. The action preserves their fibers and their uniform measures, so \(\mathbb E(W_1\mid\mathcal T)=\mathbb E(\mathcal PW_1\mid\mathcal T)\). Conditional independence of the diagrams, conditional Cauchy–Schwarz, and (84) imply \[ |\mathbb EW_1\overline{W_2}| \leq \|\mathbb E(W_1\mid\mathcal T)\|_2\, \|\mathbb E(W_2\mid\mathcal T)\|_2 \leq3^{r/2}\|\mathcal PW_1\|_2. \tag{87}\] The last norm uses the first diagram’s marginal law of independent uniform unit leaves; it is not conditioned on the component totals.

Under this law, condition on the products in all bottom quartets. Ancestor data and ancestor validity are determined by these products. If an ancestor is invalid the contribution vanishes. Otherwise quartet interiors are independent uniform product fibers. Each cycle quartet contains two moving leaves. Fix its two held leaves and use one moving leaf as a coordinate on \(U\); the quartet product determines the other. Take the Mellin expansion in this coordinate with coefficients \(a_{j,\rho}\). The action scales the coordinate by \(z\) or \(z^{-1}\), so projection retains precisely the tuples of indices with \[ \prod_{j=1}^t\rho_j^{\delta_j}=1, \qquad \delta_j\in\{1,-1\}, \tag{88}\] where \(t\) is the number of quartets on the cycle.

The needed local estimates concern any bottom quartet with its product and all ancestor data fixed. On valid ancestor data its current entries and parent argument \(y\) are fixed units. Choose two distinct leaves to move by reciprocal multiplication, preserving their product, and hold the other two leaves fixed. Use one moving leaf as a coordinate on \(U\); the other is then determined. Write \(a_\rho\) for the Mellin coefficient of the quartet value in this coordinate.

We shall construct nonnegative functions \(B_\rho(y)\), depending on \(g\) and \(q\) but not on the ancestor data or unit parameters, such that \[\mathbb E_{\mathrm{held}}|a_\rho|^2\leq B_\rho(y),\] and \[ \sup_\rho\mathbb E_{y\in U}B_\rho(y) \ll\varepsilon_q^2+q^{-1/2}=o(1),\qquad \sum_\rho\mathbb E_{y\in U}B_\rho(y)\ll1. \tag{89}\] The held average here is the independent uniform average of the two held leaf variables, conditional on the quartet product. We shall also construct a nonnegative \(B_0(y)\) of bounded mean that dominates the full conditional second moment of an untouched quartet. Finitely many orientations and conjugation choices are possible; adding their majorants makes all these assertions uniform without affecting their bounds.

One character in (88) is determined by the others. We will use the small supremum in (89) for that index, the bounded sum for the remaining indices, and \(B_0\) for quartets off the cycle. The following local calculations establish these estimates; we then complete the projected norm bound.

Bottom-pair autocorrelations

We next establish the local estimates used in each quartet. Fix \(\sigma\in\{1,-1\}\) and \(g_*\in\{g,\overline g\}\). For \(d\in U\) and \(t\in U\setminus\{1\}\), let \[x=\frac{\sigma dt}{t-1},\qquad z=\frac{\sigma d}{t-1},\qquad h(d,t)=g_*(x)\overline{g_*(z)}.\] Extend \(h\) by zero whenever \(d=0\) or \(t\in\{0,1\}\). Thus on valid arguments \(x-z=\sigma d\) and \(t=x/z\). Write \[R_*(d)=\mathbb E_{t\in U}|h(d,t)|^2\qquad(d\in U).\] The map \((d,t)\mapsto(x,z)\) is a bijection between the valid pairs and ordered distinct unit pairs, so \[ \mathbb E_{d\in U}R_*(d) =\frac1{(q-1)^2}\sum_{\substack{x,z\in U\\x\ne z}} |g_*(x)|^2|g_*(z)|^2 \leq\left(\frac q{q-1}\right)^2. \tag{90}\] For nonzero \(d\), the Mellin coefficient of \(h(d,\cdot)\) is \[ P_\chi(d)=\frac q{q-1}\mathbb E_{x\in\mathbb F_q} (g_*\overline\chi)(x) \overline{(g_*\overline\chi)(x-\sigma d)}. \tag{91}\] Indeed, \(t=x/(x-\sigma d)\) gives precisely this coefficient. Use the autocorrelation formula (91) also to define \(P_\chi(0)\); this value is not the Mellin coefficient of the zero-extended \(h(0,\cdot)\).

Let \(w_\chi(a)=\widehat P_\chi(a)\) and \(r_\chi=\sum_a w_\chi(a)^2\). Autocorrelation and additive Fourier inversion give \[w_\chi(a)=\frac q{q-1} |\widehat{g_*\overline\chi}(\sigma a)|^2\geq0, \qquad P_\chi(0)=\sum_a w_\chi(a) =\frac q{q-1}\|g\|_2^2.\] In particular, \[ \begin{gathered} \sum_a w_\chi(a)\ll1,\qquad \max_{\chi,a}w_\chi(a)\ll\varepsilon_q^2=o(1),\\ \max_\chi r_\chi\ll\varepsilon_q^2=o(1),\qquad \sum_\chi r_\chi\ll1. \end{gathered} \tag{92}\] For the last assertion, Mellin Parseval at \(d\ne0\) gives \(\sum_\chi|P_\chi(d)|^2=R_*(d)\). At \(d=0\), each of the \(q-1\) characters has the same value \(q\|g\|_2^2/(q-1)\). Additive Parseval and (90) therefore give the explicit bound \[ \sum_\chi r_\chi =\frac1q\sum_{d\in\mathbb F_q}\sum_\chi|P_\chi(d)|^2 \leq\frac{2q}{q-1}\leq3. \tag{93}\]

We shall repeatedly use the following elementary consequence of Mellin expansion. If \(f(t)=\sum_\chi c_\chi\chi(t)\) on \(U\), \(K\in U\), and \(\rho\in\widehat U\), then \[ \left|\mathbb E_{z\in U}f(Kz^{\pm2})\overline{\rho(z)}\right|^2 \leq2\sum_{\chi^{\pm2}=\rho}|c_\chi|^2. \tag{94}\] To see this, orthogonality makes the coefficient on the left equal to \(\sum_{\chi^{\pm2}=\rho}c_\chi\chi(K)\). The squaring map on \(\widehat U\) has kernel of size two, so there are at most two terms, and Cauchy–Schwarz proves the inequality. Similarly, uniform measure on any square coset in \(U\) is dominated by twice uniform measure on \(U\) for nonnegative integrands.

A uniform Mellin estimate

The following estimate will be applied to the quartet terms in the next subsection. For every \(\eta\in\widehat U\) and \(a\in\mathbb F_q\), \[ \sum_{\chi\in\widehat U} |\widehat{P_\chi\chi\eta}(a)|^2 \leq\frac q{q-1} \left(\varepsilon_q^4+\sqrt3\,q^{-1/2}\right)=o(1). \tag{95}\] Here the multiplicative twist sets the value at zero to zero, even if \(\chi\eta\) is principal.

For a proof, expand \(h(d,\lambda d)\) in Mellin characters and apply Parseval in \(\lambda\in U\). The left side of (95) equals \[\mathbb E_{\lambda\in U} \left|\mathbb E_{d\in\mathbb F_q}h(d,\lambda d)\eta(d)e_q(-ad)\right|^2,\] where an argument with \(d=0\) or \(\lambda d=1\) contributes zero. In the parametrization \(x-z=\sigma d\), \(x/z=\lambda d\), solve for \(x\) and \(d\) in terms of \(z\): \[x=\frac{z^2}{z-\sigma/\lambda},\qquad d=\frac{z}{\lambda z-\sigma}.\] This is a bijective parametrization of the valid values: \(z\in U\setminus\{\sigma/\lambda\}\) corresponds precisely to \(d\in U\setminus\{1/\lambda\}\). Setting \(t=\sigma/\lambda\) and \(r'=1/z\) gives \(1/x=r'-tr'^2\). Define \[G(h)=(g_*\eta)(1/h)e_q(-a\sigma/h)\quad(h\in U),\qquad G(0)=0.\] The identities \(\eta(d)=\overline{\eta(\lambda)}\eta(x/z)\) and \(e_q(-ad)=e_q(-a\sigma x)e_q(a\sigma z)\) show that the inner coefficient is \[ \overline{\eta(\lambda)}\,TG(t),\qquad TF(t)=\frac1q\sum_{r'\in U}\overline{G(r')} F(r'-r'^2t). \tag{96}\] The zero definition of \(G\) encodes exactly the excluded values in this formula. Inversion permutes \(U\), so \(\|G\|_2\leq1\) and \(|\mathbb EG|\leq\varepsilon_q\) by (82).

Here is a direct operator bound for (96). The affine-action estimate is a concrete counterpart of the convolution bounds developed by Gowers (Gowers 2008), Babai, Nikolov and Pyber (Babai et al. 2008), and Gill (Gill 2016, Theorem 2 and Proposition 1.7). We give the weighted calculation directly in the additive Fourier basis. Let \(U_rF(t)=F(r-r^2t)\), a unitary operator on the probability-normalized \(L^2(\mathbb F_q)\). The map underlying \(U_r^*U_s\) is \[t\longmapsto(s/r)^2t+s-s^2/r.\] For a prescribed slope, \(z=s/r\) has at most two possibilities. Unless \(z=1\), the translation \(r(z-z^2)\) determines \(r\) uniquely; \(z=1\) gives the identity and forces \(r=s\). Hence every nonidentity affine map has at most two ordered representations as \(U_r^*U_s\). Write the coefficient array of \(T^*T\) on affine maps as \(c(a,b)\), with \(a\in U\), \(b\in\mathbb F_q\), and action \(F(t)\mapsto F(at+b)\). Its identity coefficient is at most \(1/q\). Cauchy–Schwarz on each fiber of at most two nonidentity representations gives \[ \sum_{a,b}|c(a,b)|^2 \leq\frac1{q^2} +\frac2{q^4}\left(\sum_{r\in U}|G(r)|^2\right)^2 \leq\frac3{q^2}. \tag{97}\]

For completeness, the required affine-action estimate follows from ordinary additive Parseval. The functions \(e_q(\xi t)\), \(\xi\in U\), form an orthonormal basis of the mean-zero subspace, and \(F(t)\mapsto F(at+b)\) sends the mode \(\xi\) to the mode \(a\xi\) with factor \(e_q(\xi b)\). Thus the squared Hilbert–Schmidt norm on this subspace is \[\sum_{a\in U}\sum_{\xi\in U} \left|\sum_b c(a,b)e_q(\xi b)\right|^2 \leq q\sum_{a,b}|c(a,b)|^2.\] Combining with (97) bounds the operator norm of \(T^*T\) there by \(\sqrt3q^{-1/2}\). Affine actions preserve the mean-zero subspace and the constants. If \(m_G=\mathbb EG\), then \(T1=\overline{m_G}\), so the constant part of \(TG\) has squared norm \(|m_G|^4\). Therefore \[\mathbb E_{t\in\mathbb F_q}|TG(t)|^2 \leq\varepsilon_q^4+\sqrt3q^{-1/2}.\] Changing the average to \(t\in U\), and using that \(\lambda\mapsto\sigma/\lambda\) permutes \(U\), proves (95).

Quartet coefficient majorants

We now construct the majorants in (89). Fix a bottom quartet with its product and ancestor data as in the cycle reduction. Let \(d,e\) be its two bottom-pair arguments, so \(d-e=y\). In either pair, orient a leaf as free and the other as held. Its product test is \(h(d,t)\) defined above, with \(\sigma\) recording the orientation and \(g_*\) recording the conjugation on the free leaf.

First suppose both moving leaves are in the left pair. At fixed pair product, its ratio is a fixed unit times the inverse square of the moving coordinate. Equation (94) bounds the squared coefficient by \[2\sum_{\chi^2=\rho^{-1}}|P_\chi(d)|^2 \times|\text{right-pair value}|^2.\] Interchanging the coordinate convention only inverts \(\rho\). Average the two held variables by exposing first their product and then their split. The first exposure makes \(d/e\) uniform on a square coset, and the second makes the right-pair ratio uniform on a square coset. Dominate each by twice full unit measure. Thus a majorant is a fixed constant times \[ \frac1{q-1}\sum_{\substack{d,e\in U\\d-e=y}} \left(\sum_{\chi^2=\rho^{\pm1}}|P_\chi(d)|^2\right)R_*(e), \tag{98}\] where summing both signs is allowed. Its mean over \(y\) is bounded by a constant times the product of the means of the two nonnegative factors: remove the restriction \(d\ne e\) to obtain this bound. Equations (92) and (90) give the two assertions of (89). An untouched quartet has the analogous majorant with \(R_L(d)R_R(e)\) in place of the displayed product, and hence has bounded mean.

It remains to treat one moving leaf in each bottom pair. The following diagram records the ordered current entries; the leaf labels underneath give the corresponding factors \(H\) before each bottom reconstruction. It will explain exactly which held leaves lead to the two formulas below.

Orient the moving leaf as free in each pair. Division of the formulas in (83) gives \[ \frac{t_L}{d}=\text{a fixed unit}\times H_{\mathrm{held},L}^2, \qquad \frac{t_R}{e}=\text{a fixed unit}\times H_{\mathrm{held},R}^2. \tag{99}\] For example, if the free leaf is the first child of the left pair, the constant in the first identity is \(D's_{\mathrm{free}}/(s_{\mathrm{held}}s_{\mathrm{pair}})\); the opposite orientation gives the same form with the two bottom frequencies interchanged. At the quartet root, another direct consequence of (83) is \[ p_*^2=\frac{s_+s_-}{s_nD'u_n^2}\frac{y}{de}. \tag{100}\] If the held entry in Figure 1 is the residual \(A\) or \(B\), (99) therefore has the first of the following forms; if it is \(p_*\), use (100) to obtain the second: \[ t_L=\lambda_Ld\ \text{or}\ \lambda_L/e, \qquad t_R=\lambda_Re\ \text{or}\ \lambda_R/d. \tag{101}\] Call the first choice on either side friendly and the second bad. The parameters \(\lambda_L,\lambda_R\) are fixed unit multiples of the squares of the two held leaf variables. The multiples may depend on the fixed parent data and on \(y\), but not on the held variables. Since those variables are independent uniform units, the two parameters are independent uniform square-coset variables.

For fixed held variables the parent ratio \(d/e\) is a fixed unit times the inverse square of the moving coordinate. The local value depends on this ratio, rather than on its square-root choice. Indeed changing the moving coordinate to its negative changes \(p_*\) to its negative, while (101) only used its square; the arguments within either pair are determined by their ratio and their difference. Apply (94), and then dominate the two square-coset laws of the held parameters by full independent unit laws. The latter domination is applied to a nonnegative squared coefficient and costs at most four. On changing from \(d/e\) to \(d-e=y\), the normalization changes by the bounded factor \(q/(q-1)\). We obtain a constant times \[ \sum_{\nu^2=\rho^{\pm1}} \mathbb E_{\lambda_L,\lambda_R\in U} \left|\frac1q\sum_{\substack{d,e\in U\\d-e=y}} h_L(d,t_L)h_R(e,t_R)\nu(d/e)\right|^2. \tag{102}\] The sign allows either Mellin convention. All invalid ratios are encoded by the zero definitions of the functions \(h\); in particular, the parent ratio \(1\) has no valid \((d,e)\) with \(d-e=y\ne0\).

To check the sum over \(\rho\) in (89), it suffices to sum over all \(\nu\). For \(y\ne0\), the map \(t=d/e\) is a bijection from \(U\setminus\{1\}\) to the unit solutions of \(d-e=y\), with \(d=yt/(t-1)\) and \(e=y/(t-1)\). Mellin Parseval, followed by the independent \(\lambda_L,\lambda_R\) averages, bounds this sum by a constant times \[\frac1{q-1}\sum_{\substack{d,e\in U\\d-e=y}}R_L(d)R_R(e).\] Its mean over \(y\in U\) is bounded by (90).

For the small bound at a fixed \(\nu\), extend the nonnegative \(y\) average to all of \(\mathbb F_q\), paying at most \(q/(q-1)\). Expand both \(h\) factors in Mellin characters \(\chi,\psi\). Orthogonality in the independent parameters separates their squared coefficients. Additive convolution Parseval then reduces the bound to \[ \sum_{a,\chi,\psi} |\widehat{P_\chi\alpha}(a)|^2 |\widehat{P_\psi\beta}(-a)|^2. \tag{103}\] Each pair uses its own choice of \(\sigma,g_*\) in its \(P\). The twists are listed explicitly below; all are zero at zero: \[\begin{array}{c|cc} \text{choices}&\alpha&\beta\\ \hline \text{friendly, friendly}&\nu\chi&\overline\nu\psi\\ \text{friendly, bad}&\nu\chi\overline\psi&\overline\nu\\ \text{bad, friendly}&\nu&\overline\nu\psi\overline\chi\\ \text{bad, bad}&\nu\overline\psi&\overline\nu\overline\chi \end{array}\] For example, the left friendly term contributes \(\chi(d)\) and the left bad term contributes \(\overline\chi(e)\), which explains all four rows. If the left choice is friendly, the second twist is independent of \(\chi\). Apply (95) to the sum over \(\chi\), uniformly in the remaining index and \(a\). The remaining sum is bounded since additive Parseval gives \[\sum_{\psi,a}|\widehat{P_\psi\beta}(a)|^2 \leq\sum_\psi\mathbb E_{d\in\mathbb F_q}|P_\psi(d)|^2\ll1;\] here \(\beta\) may depend on \(\psi\). This bounds (103) by \(O(\varepsilon_q^4+q^{-1/2})\). The right friendly case is symmetric.

The case of two bad choices

It remains to bound (103) when \(\alpha=\nu\overline\psi\) and \(\beta=\overline\nu\overline\chi\). For a nonprincipal character \(\alpha\), the additive Fourier transform of \(\alpha\) has constant modulus \(q^{-1/2}\) on nonzero frequencies, and equals zero at zero. For clarity, the needed Gauss identity follows by substituting \(x\mapsto x/t\) in \(\sum_x\alpha(x)e_q(tx)\) for \(t\ne0\); its modulus is \(\sqrt q\), because \[\left|\sum_x\alpha(x)e_q(x)\right|^2 =\sum_{u\in U}\alpha(u)\sum_{z\in U}e_q((u-1)z) =(q-1)-\sum_{u\ne1}\alpha(u)=q.\] Consequently, with harmless unit factors and a possible reflection of the frequency, \[ |\widehat{P_\chi\alpha}(a)| =q^{-1/2}\left|\sum_b w_\chi(b)\overline\alpha(a-b)\right|. \tag{104}\]

Let \(w\geq0\) be any weights of mass \(J\) and let \(r_w=\sum_b w(b)^2\). Multiplicative orthogonality yields \[ \frac1{q-1}\sum_{\alpha\in\widehat U}\sum_a \left|\sum_b w(b)\alpha(a-b)\right|^4 \leq 2q r_w^2+J^4. \tag{105}\] Indeed, after expansion, a nonzero term requires \[(a-b_1)(a-b_2)=(a-b_3)(a-b_4)\ne0.\] When the two unordered pairs of \(b\)’s agree, their total weight is at most \(2r_w^2\) and there are at most \(q\) values of \(a\). Otherwise, subtracting the two monic quadratics gives a nonzero polynomial of degree at most one, so there is at most one value of \(a\). The total weight of all these latter quadruples is at most \(J^4\).

The principal character alone contributes \[\frac1{q-1}\sum_a(J-w(a))^4 \geq\frac{qJ^4-4J^3\sum_aw(a)}{q-1} =J^4-\frac{3J^4}{q-1}.\] Subtract this contribution in (105) before applying (104). Since the masses \(J\) of our \(w_\chi\) are uniformly bounded, for each \(\chi\) this gives \[\sum_{\alpha\ne1,a}|\widehat{P_\chi\alpha}(a)|^4 \leq2r_\chi^2+O(q^{-2}).\] Summing over \(\chi\) and using (92), we obtain \[ \sum_{\chi,\alpha\ne1,a}|\widehat{P_\chi\alpha}(a)|^4 \ll\varepsilon_q^2+q^{-1}. \tag{106}\] When both twists in (103) are nonprincipal, Cauchy–Schwarz bounds it by the geometric mean of two sums of this form. This is legitimate because at fixed \(\nu\) the map \((\chi,\psi)\mapsto(\chi,\nu\overline\psi)\) is bijective, and the corresponding assertion holds for the other factor.

We also record the principal cases explicitly. Because the principal character is zero at zero, its additive transform is \[ \widehat{P_\chi\mathbf 1_U}(a)=w_\chi(a)-\frac{P_\chi(0)}q. \tag{107}\] Thus its Fourier maximum is \(O(\varepsilon_q^2+q^{-1})\), and its squared Fourier norm is no greater than \(r_\chi\) by Parseval on the original functions. If \(\alpha\) is principal, then \(\psi=\nu\) is fixed. When \(\beta\) is nonprincipal, (104) and the bounded mass of \(w_\psi\) bound the other Fourier factor by \(O(q^{-1/2})\) uniformly. Summing the first squared factor over \(\chi,a\) costs \(O(1)\) by (93); this part is \(O(q^{-1})\). The case with the two roles exchanged is identical. If both twists are principal, both indices are fixed. Apply the small Fourier maximum in (107) to one factor and the bounded squared norm to the other. This contributes \(O(\varepsilon_q^4+q^{-2})\).

The two-bad case of (103) is therefore \(O(\varepsilon_q^2+q^{-1})\). Together with the friendly estimates this proves the first assertion of (89) for (102). Adding the finitely many orientation choices and the same-pair majorants completes the construction of \(B_\rho\) and \(B_0\).

Completion of the cycle estimate

Return to the projection in (87), conditioning again on the products in all bottom quartets. Orthogonality in the independent moving coordinates gives a sum of products of \(|a_{j,\rho_j}|^2\), with squared untouched-quartet values as the other factors. Average the held variables. The bounds already proved dominate this expression by \[\sum_{\prod_j\rho_j^{\delta_j}=1} \prod_{j=1}^t B_{\rho_j}(y_j) \prod_{j\notin\mathrm{cycle}}B_0(y_j).\] The actual joint distribution of quartet arguments on valid ancestor points is dominated by a constant depending only on \(l\) times independent uniform unit measure, by the horizontal-level density bound proved above. Since this last display is nonnegative, we may use that domination without any pointwise control of \(g\).

Put \(b_\rho=\mathbb E_{y\in U}B_\rho(y)\) and \(b_0=\mathbb E_{y\in U}B_0(y)\). One character in (88) is determined uniquely by the others. Consequently \[\|\mathcal PW_1\|_2^2 \leq C_l\bigl(\sup_\rho b_\rho\bigr) \left(\sum_\rho b_\rho\right)^{t-1} b_0^{r/4-t} \ll_l\varepsilon_q^2+q^{-1/2}.\] If the cycle consists of two parallel edges, \(t=1\) and its sole character is principal; the same inequality simply uses \(b_1\leq\sup_\rho b_\rho\). Thus this degenerate cycle requires no separate structural assumption. Equation (87) proves the quantitative statement of Lemma 15, and hence (85).

For the later application, the exact transforms \(g_p\) in (59) satisfy \(g_p(0)=0\) and \(\mathbb E|g_p|^2=1\) by centering and additive Parseval. On the chosen spectator subset their mixed correlation parameters tend to zero uniformly. Once independent unit bulk residues have been obtained in Section 8, Lemma 15 may therefore be applied separately at every spectator prime. The zero convention in the diagram retains the requirement that every reconstructed entry be a unit at that prime.

Scales and prime priors

Let \(L\to\infty\). The transfer depth \(k\) will be a sufficiently large fixed positive integer, chosen before \(L\) tends to infinity. Put \[h=e^{.01L},\qquad z=k^4,\qquad m=2\lfloor zL/2\rfloor,\qquad r_j=2^{j-1}\quad(1\le j\le k).\] The notation \(o_k(m)\) and \(O_k(1)\) permits dependence on all parameters that are fixed before \(L\). In bounds of the form \(Cm\) or \(C2^lm\), however, \(C\) will be independent of \(k\) and of the large gap constants introduced below, once \(k\) and then \(L\) are sufficiently large. The threshold on \(L\) may depend on these fixed choices.

Choose fixed positive constants \(B_s,B_D,B_z\), with their order of choice specified in Section 9, and define \[\begin{align*} \Delta_0&=(B_s+8\log z)m,\\ \Delta_j&=r_j(B_D+B_z\log z+.4\log r_j)m \qquad(1\le j\le k),\\ E_l&=\Delta_0+\sum_{j=1}^l\Delta_j+2^l\sqrt m,\\ V_l&=e^{E_l}\qquad(0\le l\le k). \tag{108}\end{align*}\] Thus \(\log V_l=O_k(m)\). In particular, all frequencies used below are smaller than every sampled prime, since even the smallest prime range has lower endpoint \(\exp(\exp(.0005L))\).

Fix a nonnegative smooth function \(\varphi\) supported on \([-1,1]\) such that \[\sum_{n\in\mathbb Z}\varphi(t-n)=1\qquad(t\in\mathbb R).\] Then \(0\le\varphi\le1\) and \(\int_{\mathbb R}\varphi(t)\,dt=1\). For a center \(c\), the log-cell prior is the probability measure on primes proportional to \[\frac{\varphi(\log p-c)}p.\] Except for the giant-prime prior defined shortly, all prime priors will omit a set \(\mathcal E_L\) of at most two prime values. This set is fixed for each \(L\); Section 8 specifies its choice from the two possible Page exceptional conductors. Every abundance assertion in this section holds uniformly after any such deletion. A nongiant cell is therefore normalized by \[Z_c=\sum_{\substack{p\ \text{prime}\\p\notin\mathcal E_L}} \frac{\varphi(\log p-c)}p.\] For all the cell centers used here, the prime number theorem and partial summation give \(Z_c\sim c^{-1}\). The same statement holds without the deletion. They also give \[\sum_p\frac{\log p}{p}\varphi(\log p-c)=1+o(1).\] The errors are uniform as the centers in our specified ranges tend to infinity. Deleting two prime values does not change these asymptotics.

By (60), there is a block \([G_0,G_0+h]\) in log-prime coordinates, contained in the range of that estimate, such that the primes satisfying its two conditions have total \((\log p)/p\) weight at least \(c_0h\), for a fixed \(c_0>0\). Here and below a prime satisfying those conditions is called favorable. To see the block assertion, partition \([e^{.05L},e^{.9L}]\) into intervals of length \(h\), apart from the two end pieces. On each full block the log coordinate varies by a relative \(o(1)\), uniformly in the block. If every block had favorable \((\log p)/p\) weight at most \(ch\), summing these bounds after division by the left log coordinate would give favorable harmonic weight at most \((.85c+o(1))L\). A sufficiently small fixed \(c\) contradicts (60). Mertens’ estimates make the two end pieces negligible in this calculation.

Set \[\log X=2G_0+2^{k+1}h, \qquad A'=A\cap[X^{9/10},X].\] The whole chosen block lies below the prime cutoff in (7) for the uniform measure on \(A'\). Indeed, \(\log\sqrt X=G_0+2^kh\), whereas the block ends at \(G_0+h\), and the loss from the logarithmic denominator in that cutoff is only \(O(\log\log X)=O(L)\).

Use the transforms \(F_p,g_p\) from (59), with the normalization \[g_p(b)=\sqrt p\,\mathbb E_{x\bmod p}F_p(x)e_p(-bx),\qquad F_p(x)=p^{-1/2}\sum_{b\bmod p}g_p(b)e_p(bx).\] For a favorable prime put \[\widetilde g_p(b)= \begin{cases} g_p(b)/|g_p(b)|,&g_p(b)\ne0,\\ 0,&g_p(b)=0, \end{cases}\] and put \(\widetilde g_p=0\) at every other prime. Let \(\widetilde F_p\) be its inverse transform with the same normalization. Conjugate symmetry of \(g_p\) implies that \(\widetilde F_p\) is real. Also \[\mathbb E_x\widetilde F_p(x)=0, \qquad \mathbb E_x|\widetilde F_p(x)|^2 =\mathbb E_b|\widetilde g_p(b)|^2\le1.\] For a favorable prime, Parseval and the definition of \(F_p\) give \[\mathbb E_{x\in S_p}\widetilde F_p(x) =\sqrt{\frac{1-\sigma_p}{\sigma_p}}\, \mathbb E_b|g_p(b)|\ge\frac{\delta_0}{\sqrt2}.\]

There is an integer center \(G\), whose log-cell support is contained in \([G_0,G_0+h]\), for which \[ \mathbb E_{\substack{p\ \text{in the cell at}\ G\\a\in A'}} \widetilde F_p(a)\ge c_1>0. \tag{109}\] The giant prior in this display includes all primes in its cell. Here is why the collision estimate applies to these possibly unbounded inverse transforms. If \(\mu_p\) is the projection of the uniform probability on \(A'\), then Cauchy–Schwarz gives \[\left|\sum_{x\bmod p} (\mu_p(x)-U_{S_p}(x))\widetilde F_p(x)\right|^2 \le p\,\|\mu_p-U_{S_p}\|_2^2.\] Consequently (7) bounds the sum of these squared errors with weight \((\log p)/p\) by \(O(L)\). The total such weight on the block is \(O(h)\), so its weighted sum of absolute errors is \(O(\sqrt{Lh})=o(h)\). The favorable uniform means, on the other hand, have a positive sum of order \(h\). Partitioning by the integer translates of \(\varphi\), and deleting the bounded-width end strips, therefore supplies a cell with a positive average empirical mean. Replacing \((\log p)/p\) by \(1/p\) in this cell does not change this conclusion: the log coordinate has relative variation \(o(1)\), and the same error bound applies. This proves (109).

Fix this \(G\). Write \[ Z_G=\sum_{p\ \text{prime}}\frac{\varphi(\log p-G)}p, \qquad \mu_G(p)=\frac{\varphi(\log p-G)}{pZ_G}, \qquad c_g=\log Z_G^{-1}. \tag{110}\] We have \(Z_G\sim G^{-1}\), and hence \(c_g=\log G+O(1)\le .91L\) for sufficiently large \(L\). The coefficient in this last bound is independent of the gap constants and of \(k\).

The initial lists and positive statistic

A half-list consists of the following independent positions:

1. one giant with prior \(\mu_G\), using the test \(\widetilde F_p\);

2. \(m/2\) bulk positions, with their common prior proportional to \(1/p\) on \(.004L\le\log\log p\le .006L\), omitting \(\mathcal E_L\);

3. \(m/2\) spectator positions, with their common prior proportional to \(1/p\) on a subset of \(.0005L\le\log\log p\le .001L\) of harmonic mass \(\gg L\), omitting \(\mathcal E_L\), on which (59) holds uniformly with a bound tending to zero;

4. three top positions and two compensation positions of each type \(j=1,\ldots,k\), with cell priors chosen below.

Every nongiant position uses the exact test \(F_p\). The spectator subset exists by Corollary 10; its exceptional threshold can be chosen slowly enough that all the stated conclusions hold uniformly on the retained subset. The bulk and spectator harmonic normalizing masses are both between fixed positive multiples of \(L\).

Let \(S_b,S_d\) be the sums of the log primes at the bulk and spectator positions of one half-list. Include in its weight the two factors \[\varphi(S_b-t_b)\varphi(S_d-t_d).\] These are weights, not conditioning of any prior. Choose integer centers \(t_b,t_d\) so that, for each of the two groups, the expectation of its cutoff together with the restriction \(1/3\le\sigma_p\le2/3\) at all its positions is at least \(e^{-Cm}\). Such choices follow directly from the partition of unity. Almost all the probability of a single position is balanced, by (59) or (7); for sufficiently large \(L\) the probability that all positions in that group are balanced is at least \(2^{-m/2}\). Each possible log sum lies in an interval admitting at most \(\exp(O(L)+O(\log m))\) relevant integer centers. At least one center thus has the required weighted mass. In particular, \[t_b,t_d=o_k(h).\]

Call the bulk and top positions protected. For the full list of two half-lists, define the target log sum \(J\) for the protected positions and the target log sum \(w_j\) for compensation type \(j\) by \[ J=\frac{\log X-2G-2t_d+\Delta_0+\sum_{j=1}^k\Delta_j}{2^k}, \qquad w_j=J+\sum_{i>j}w_i-\frac{\Delta_j}{r_j}. \tag{111}\] The second definition is made successively for \(j=k,k-1,\ldots,1\). It gives \[J\asymp h,\qquad w_j=(2^{k-j}+o_k(1))J, \qquad J+\sum_{j=1}^kw_j=2^kJ-\sum_{j=1}^k\Delta_j.\] Choose the three top cell centers in a fixed small relative neighborhood of \((J-2t_b)/6\), with their sum equal to \((J-2t_b)/2+O(1)\). For the two positions of type \(j\), choose centers in a corresponding neighborhood of \(w_j/4\), with sum \(w_j/2+O(1)\). Neighborhoods of relative radius \(.03\) suffice to keep different compensation types, top positions, bulk positions, spectator positions, and giants in pairwise disjoint prime ranges.

All these top and compensation centers can be chosen so that the balanced primes have a fixed positive fraction of the cell prior. Indeed, these primes also lie below the cutoff in (7). A cell in which a fixed positive fraction is unbalanced contributes a fixed positive amount to the nonnegative imbalance term in that estimate. Since the translates of \(\varphi\) sum to one, only \(O(L)\) integer centers can fail the desired balanced-fraction condition. Each neighborhood available here has length comparable to \(h\), which is much larger than \(L\). For a prescribed rounded pair sum, exclude a bad center and its reflection about that sum; this excludes only \(O(L)\) choices. For a triple, choose the first two centers in slightly smaller neighborhoods. Among the resulting pairs only an \(O(L/h)\) fraction have a bad third center determined by the rounded sum. This gives the required centers while respecting all ranges. On the bulk cutoff, the protected log sum of each half-list is now \(J/2+O(1)\).

Let \(T(n)\) be the expectation over one half-list of the product of all its tests at \(n\), multiplied by the two log-sum cutoffs. For \(a\in A'\), every exact local test is \[F_p(a)=\sqrt{\frac{1-\sigma_p}{\sigma_p}}>0.\] This value is independent of the choice of \(a\in A'\): all these primes are sufficiently small for the defining residue restriction on \(A\) to apply. The expectation of the product of exact tests and the cutoffs is therefore a positive scalar \(c_L\), independent of \(a\), with \(c_L\ge e^{-Cm}\). This lower bound follows by restricting every nongiant position to balanced primes; each local value is at least \(2^{-1/2}\), and the preceding bin and cell choices give the required mass. Thus \[T(a)=c_L\mathbb E_{p\sim\mu_G}\widetilde F_p(a).\] Take the nonnegative Schwartz function \(\psi\) used in the quadratic argument, with compactly supported smooth Fourier transform and a positive lower bound on \([0,1]\). The tests are real, so \(T(n)^2\) is nonnegative. Equation (109), Jensen’s inequality on \(A'\), and the lower bound in (4) give \[ I:=\sum_{n\in\mathbb Z}\psi(n/X)T(n)^2 \ge \sqrt X\,e^{-Cm}. \tag{112}\] The logarithmic loss in \(|A'|\) is absorbed here because \(\log\log X=O(L)\) and \(m\asymp k^4L\). Notice that this argument uses the mean of the giant test and its square; it does not require the giant test to be pointwise nonnegative.

Removing repeated primes and applying Poisson summation

Expand \(T(n)^2\) using two independent half-lists. Let \(M\) be the product of all positions, counted with multiplicity. On the cutoff support, \[\log M=2G+2t_d+J+\sum_{j=1}^kw_j+O_k(1) =\log X+\Delta_0+O_k(1).\] We may discard the tuples with repeated prime values, with a negligible error relative to (112). We give the estimate because no cancellation estimate for repeated local factors is being assumed.

For a tuple containing a repetition, the product of its distinct primes, denoted \(Q\), satisfies \[Q\ll_k X e^{\Delta_0}/\exp(\exp(.0005L))=o(X).\] The product of the local tests is periodic modulo \(Q\). Compact Fourier support of \(\widehat\psi\) implies that its smoothed sum is exactly \(X\widehat\psi(0)\) times its residue mean, for sufficiently large \(L\). If any prime occurs once, that residue mean is zero by the mean-zero property of its test and CRT. If a prime occurs with multiplicity \(e\ge2\), its contribution to the absolute residue mean is at most \(p^{e/2-1}\). Indeed every local test has probability \(L^2\) norm at most one, hence supremum at most \(\sqrt p\); apply Cauchy–Schwarz to two factors and use the supremum bound for the others. This argument also covers factors assigned different roles at the same prime.

The probability of any prescribed ordered tuple is at most \[M^{-1}L^{-2m}\exp(Cm+O_k(1)).\] There are \(2m\) broad-band positions. Each contributes a normalization of size at most \(C/L\). The remaining \(4k+8\) cell positions have combined normalization at most \(\exp(O(kL)+O_k(1))\), which is \(\exp(Cm+O_k(1))\) with \(C\) independent of large \(k\) because \(m\asymp k^4L\). Since \(\prod_{p\mid Q}p^{e_p/2-1}=M^{1/2}/Q\), the absolute contribution of tuples in which every prime occurs at least twice is at most \[\sqrt X\exp(-\Delta_0/2+Cm+O_k(1))L^{-2m} \sum_{\rm tuples}\frac1{\prod_{p\ \text{distinct}}p}.\] Put \(b=2m+4k+8\). The harmonic mass of the union of all prime ranges is \(O(L)\). Assigning the \(b\) labeled positions to \(i\) distinct values, and then dropping restrictions for an upper bound, gives \[\sum_{\rm tuples}\frac1{\prod_{p\ \text{distinct}}p} \le \sum_{i=1}^{b}\frac{i^b(CL)^i}{i!} \le b^b e^{CL}.\] Thus the repeated-prime contribution is bounded by \[\sqrt X\exp\left(-\frac{\Delta_0}{2} +(2\log z+C)m+o_k(m)\right).\] Choosing \(B_s\) sufficiently large makes this negligible in (112). The constant required here is independent of the later gap constants and of sufficiently large \(k\).

Retain only tuples with all positions distinct, and let \(\eta_0\) be their Poisson expression divided by \(\sqrt X\). We have shown that \[ |\eta_0|\ge e^{-B_*m} \tag{113}\] for a fixed \(B_*\) independent of \(B_D,B_z\) and \(k\). The same \(B_*\) may be used for all sufficiently large admissible \(B_s\).

Templates, coefficients, and support conventions

Keep the \(m\) spectator positions of the two half-lists, with their original half-list roles, as one outside list \(\mathbf d\), and write \(d\) for their product. This list will never be duplicated. All other positions form the ordered regular template \(\mathcal I_0\); its two giants are labeled \(+\) and \(-\) in a fixed order.

At step \(j\), split \(\mathcal I_{j-1}\) into the pivot positions and the remaining template \(H\). The pivot product is \(P=pu\), where \(p\) is the \(+\) giant and \(\mathbf u\) is the ordered list of all current compensation positions of type \(j\), with product \(u\). Unlike the whole-pivot extension in Section 4, here only the giant \(p\) will be extended to positive integers. The entries of \(\mathbf u\) retain their actual-prime priors. Thus \(H\) contains the other giant, all protected positions, and all positions of types \(i>j\). Form \(\mathcal I_j=(H_+,H_-)\) from two copies of \(H\), labeling their giants \(+\) and \(-\), respectively. Whenever a template or a part of one is sampled, its positions have independent copies of their specified priors.

Before step \(j\), there are \(r_j\) copies of the full protected list of two half-lists, and \(r_j\) copies of each compensation type not yet removed. In particular \(\mathbf u\) has \(4r_j\) positions. On the inherited protected bins, \[\begin{align*} \log u&=r_jw_j+O_k(1),\\ \log H&=T_H+O_k(1),\qquad T_H=G+r_j\left(J+\sum_{i>j}w_i\right) =G+r_jw_j+\Delta_j. \tag{114}\end{align*}\] Here a template and its product are denoted by the same letter only when no confusion can result.

If \(R\) is the product of distinct actual regular prime values, put \[G_R(b)=\prod_{\ell\mid R} g_\ell^{\rm reg}\bigl(b/(R/\ell)\bmod\ell\bigr),\] where \(g_\ell^{\rm reg}=\widetilde g_\ell\) on a giant position and \(g_\ell^{\rm reg}=g_\ell\) on every small regular position. Field fractions always have unit denominators. This expression is used only on the pairwise coprime support, and is extended by zero when that support fails. The amplitudes will have the form \[ \eta_l=\mathbb E_{\mathbf d,\mathcal I_l} \sum_{0<|s|\le V_l}G_R(s/d)A_l(s), \qquad R=\prod\mathcal I_l. \tag{115}\] The factor \(G_R(s/d)\) depends on the actual regular prime values and their product, so it is unchanged when the bulk values are reassigned among their positions. The coefficient \(A_l\) will contain the spectator factors and all arrangement-dependent history weights and support conditions. This separates the common factor from the coefficient to be averaged over arrangements. The outer positions in this expectation are actual primes. The coefficient \(A_l\), unlike \(G_R\), will also be defined when its two giant entries are positive integers.

We specify all its support conventions. A history is a full binary tree of depth \(l\), with leaves at level zero. Each node at level \(i\) has a nonzero signed integer frequency of magnitude at most \(V_i\). At every state in a history require pairwise coprimality of all its current slots and the outside list \(\mathbf d\). Its two current giant values must also be units against every frequency at that node or below it. These last restrictions may always be added at an actual top, without changing an expression: actual giant primes exceed every frequency in any of the finitely many possible history levels. Once added, they are kept when a giant is extended to an integer. These requirements are imposed termwise on complete histories; they include cross-branch frequency tests for either current giant. A newly inserted pivot is a current giant in its child states, so it is subject to their subtree tests. Failed support conditions give zero.

At level zero set \[ \begin{split} A_0(s)={}&\left(\frac{X}{dR}\right)^{1/2} \widehat\psi\left(-\frac{sX}{dR}\right)\, \prod_{\rm halves}\varphi(S_b-t_b)\varphi(S_d-t_d)\\ &\hspace{13mm}\cdot \prod_{q\mid d} g_q\bigl(s/((d/q)R)\bmod q\bigr), \end{split} \tag{116}\] on this support, and zero otherwise. The half-list spectator weights use the original outside roles of \(\mathbf d\). Formula (115) with \(l=0\) is the distinct-tuple Poisson formula. Indeed the local inverse expansions contribute \((dR)^{-1/2}\), and Poisson summation followed by division by \(\sqrt X\) gives the factor \(\sqrt{X/(dR)}\) in (116). The zero frequency vanishes since the local transforms vanish at zero. On the cutoffs, \(dR/X=\exp(\Delta_0+O_k(1))\); the additional \(\sqrt m\) in \(E_0\) therefore accommodates the fixed compact support of \(\widehat\psi\).

For the recursive definition of \(A_j\), a current state is \(\mathcal I_j=(H_+,H_-)\) with root frequency \(s\). Sum over \(v,w\) with \(0<|v|,|w|\le V_{j-1}\), and independently sample the type-\(j\) vector \(\mathbf u\) by its priors. Restore the pivot by \[ p=\frac{vH_- - wH_+}{su}. \tag{117}\] Retain it only if it is a positive integer. The two child states are copies of \(\mathcal I_{j-1}\) with entries \((p,\mathbf u,H_+)\) and \((p,\mathbf u,H_-)\) in their prescribed roles. Their giant pairs, in order, are the inserted \(p\) and the giant of \(H_+\) or \(H_-\), respectively. Keep the same outside list \(\mathbf d\). Multiply the two child coefficients, conjugating the right one, by \[ u\varphi(\log p-G). \tag{118}\] Sum and average these terms, imposing all the history restrictions above. In a formula, with state arguments displayed only here, \[\begin{align*} A_j(s;\mathbf d,H_+,H_-) =\sum_{\substack{0<|v|\le V_{j-1}\\0<|w|\le V_{j-1}}} \mathbb E_{\mathbf u}\bigl[{} &u\varphi(\log p-G) A_{j-1}(v;\mathbf d,p,\mathbf u,H_+)\\ &\cdot\overline{A_{j-1}(w;\mathbf d,p,\mathbf u,H_-)} \bigr]. \end{align*}\] The bracket is interpreted termwise after expanding the two child histories, and is zero unless (117) and all their support conditions hold. Internal samples in the two children are independent; only \(\mathbf u\) at the present node is shared. This defines \(A_l\) for actual or integer giant entries, and includes no transform attached to an integer giant.

Figure 2 records the dependencies in this recursion.

The exact transfer and its diagonal

We verify the relation between the successive expressions (115). Fix \(\mathbf d,p,\mathbf u\) at step \(j\), put \(P=pu\), and group old terms according to \(t=v/H\pmod P\). On the original prime support, \[G_{PH}(v/d)=G_P(t/d)G_H(v/(Pd)).\] Let \[B_t=\mathbb E_H \sum_{\substack{0<|v|\le V_{j-1}\\v/H\equiv t\ ({\rm mod}\ P)}} G_H(v/(Pd))A_{j-1}(v),\] with all inherited support conditions; invalid terms are zero. The extracted row has counting squared norm at most \(P\): \[\sum_{t\bmod P}|G_P(t/d)|^2\le P.\] This is CRT and the exact probability squared norm one at each compensation prime, together with squared norm at most one at the giant. Cauchy–Schwarz in this row, followed by Jensen over the outer probability measures, yields \[|\eta_{j-1}|^2 \le\mathbb E_{\mathbf d,p,\mathbf u} P\sum_{t\bmod P}|B_t|^2.\] Crucially, \(B_t\) contains no prime-specific transform of the pivot giant \(p\). It is defined for a positive integer \(p\) by exactly the same formulas, with the same coprimality and frequency filters. Equation (110) gives \(p\mu_G(p)=e^{c_g}\varphi(\log p-G)\) at primes. Extending the nonnegative sum to all positive integers gives \[ |\eta_{j-1}|^2 \le e^{c_g}\mathbb E_{\mathbf d,\mathbf u} \sum_{p\in\mathbb N}u\varphi(\log p-G) \sum_{t\bmod pu}|B_t|^2. \tag{119}\] Here the sum over \(p\in\mathbb N\) means positive integers.

Expand the square using independent \(H_+,H_-\) and child frequencies \(v,w\). Separate the terms \(vH_-=wH_+\) as the diagonal. For every other term, the congruence of the two group indices defines the nonzero signed integer \(s=(vH_--wH_+)/(pu)\), so the substitution is exactly (117). It is one-to-one, with \(p\) still any positive integer in its cell. Equations (108) and (114) show \[\log|s|\le E_{j-1}+\Delta_j+O_k(1)<E_j.\] The margin is \(2^{j-1}\sqrt m\), which tends to infinity. All protected bins used in this size estimate are present in each nonzero child history.

The actual lists \(H_+,H_-\) cannot share a prime on such a term. If \(\ell\) divided both products, it would divide \(s\), since it is coprime to \(pu\); but \(\ell>|s|\). At a prime of \(H_+\) and a prime of \(H_-\), respectively, (117) gives \[v/P=s/H_-,\qquad -w/P=s/H_+.\] The inverse tests are real, so \(g_\ell^{\rm reg}(-b)=\overline{g_\ell^{\rm reg}(b)}\). The two regular transforms therefore combine exactly into \(G_{H_+H_-}(s/d)\). The remaining weights, histories, and inserted pivot are precisely the recursive definition of \(A_j\). Additional giant-frequency tests at the new top are free because its two giants are actual primes. Consequently the off-diagonal part of the extended expression in (119), before \(e^{c_g}\), is exactly \(\eta_j\).

Write \(\mathcal D_j\) for its exact diagonal. It is nonnegative, as we now verify, and we have \[ e^{-c_g}|\eta_{j-1}|^2 \le\mathcal D_j+\eta_j. \tag{120}\] In particular the off-diagonal expression \(\eta_j\) is real: the extended square and its diagonal are real.

On the diagonal, all prime factors of \(H_+\) and \(H_-\) exceed the frequencies, so \(vH_-=wH_+\) forces \(H_+=H_-\) as products and \(v=w\). Grouping by this common product and frequency before expanding the square gives a common factor \(|G_H(v/(pud))|^2\) times the squared absolute value of the prior-weighted sum of coefficients over its ordered arrangements. This proves nonnegativity. The common factor is independent of the ordering: each prime uses the same local transform in every arrangement, and the single giant in \(H\) is fixed by its disjoint range. We may therefore drop its bounded giant factor in this nonnegative expression. The remaining multiplier is \[ \mathcal G=\prod_{\ell\mid H_{\rm sm}} \left|g_\ell\bigl(v/(pud(H/\ell))\bmod\ell\bigr)\right|^2, \tag{121}\] where \(H_{\rm sm}\) consists of the small slots of \(H\).

Now expand by bijections matching the slots in the two \(H\) lists. This counts every ordered counterpart once, since the prime values within a valid \(H\) are distinct. Only matches within the same prime band can occur. In particular the giant matches itself and bulk positions match bulk positions.

Fix a first ordered \(H\). For any prescribed counterpart ordering, its point probability is \(C_H/H\) times its smooth cell factors and its role-membership indicators. The normalizing constants satisfy \[ C_H\le L^{-r_jm}\exp(Cr_jm+O_k(1)). \tag{122}\] Indeed there are \(r_jm\) bulk positions, and \(O(kr_j)\) cell positions. The latter normalizations cost \(\exp(O(kr_jL)+O_k(1))\), absorbed uniformly by \(\exp(Cr_jm)\) because \(m\asymp k^4L\). On simultaneous coefficient support, (114) allows us to extract \(C_He^{-T_H}\), leaving \(e^{T_H}/H=O_k(1)\). Normalize the external integer measure as \[ \int f(p)\,d\mu_{\mathrm{ext}}(p) :=e^{-G}\sum_{p\ge1}\varphi(\log p-G)f(p). \tag{123}\] It has bounded total mass. Extracting \(e^G\) from its definition and \(e^{r_jw_j}\) from \(u\) leaves the net scalar \(C_He^{-\Delta_j}\). The remaining Archimedean factor is \[K_{\rm ar} =\frac{e^{T_H}}H\frac{u}{e^{r_jw_j}} \prod_{\text{counterpart cell positions}} \varphi(\log p_i-c_i).\] This factor is \(O_k(1)\) on simultaneous coefficient support. Counterpart role-membership indicators are retained as zero conventions in addition to these displayed smooth factors.

The two comparison estimates

We state precisely the comparison estimates needed for the diagonal and the final symmetrization. Their proof occupies Section 8. At level \(l\), put \(r=2^l\). Each coefficient \(A_l\) has \(r\) bottom leaves, each carrying the \(m\) bulk positions of the initial full list. Its \(m\) outside spectator positions are shared by all leaves.

There are two outer environments, always using the priors, integer extension, coefficients, and support conventions just defined.

1. In the final environment, \(l=k\), the current list is \(\mathcal I_k\) with its actual prime priors. Set \(\mathcal G=1\). A pair of assignments may permute all \(rm\) bulk values among their labeled positions; the nonbulk positions and the outside spectator list are common. Set \(K_{\rm ar}=1\).

2. In the diagonal environment for step \(j\), \(l=j-1\). The current \(+\) giant \(p\) has the external measure (123). All other current slots, including the type-\(j\) vector \(\mathbf u\), have their original actual prime priors. Set \(\mathcal G\) equal to (121) with \(v=s\), with the zero convention on invalid top support. In a pair of assignments the first uses the ordered \(H\) and the second uses a prescribed same-band matching of its slots, with \(p,\mathbf u, \mathbf d\) unchanged. Use the factor \(K_{\rm ar}\) above, including the counterpart role indicators. For the norm of a single assignment this factor is omitted.

The expectation in the second environment includes the bounded-mass integer measure; it need not be a probability measure. All root-frequency sums below are over \(0<|s|\le V_l\).

For a pair of assignments, form the bipartite multigraph whose two vertex sets are their respective \(r\) bottom leaves. Each actual bulk variable is an edge joining the leaf that contains it in the first assignment to the leaf that contains it in the second. Every vertex has degree \(m\). The graph and its number of connected components depend only on the slot assignments, not on the sampled prime values or on internal histories.

The assumptions about all current-state coprimalities and all giant-frequency unit tests are part of this proposition. They are used in its arithmetic reduction, not additional conclusions of the estimate. The outside spectator list is not resampled within either coefficient or between a paired comparison. In contrast, the two coefficients have independent internal prime samples; within each coefficient, a sample at one node is shared by its two children as specified in (118). The assigned actual top values have the stated coupling between the coefficients. Coincidences among independently sampled internal prime values are allowed when the support permits them, and their equality patterns will be summed explicitly in the proof.

Histories, supports, and real-variable weights

Expand the two amplitudes in a comparison into their frequency histories. For the norm estimate (124), use the same assignment in the two histories. At level \(t\geq1\) there are \(2^{l-t}\) nodes in a history, and its sampled compensation vector has \(4\cdot2^{t-1}\) entries. Thus the total number of internal prime samples in the two histories is \(O(kr)\). This counts each sample when it is made, rather than each subsequent occurrence of that sample in a descendant list.

Partition these samples according to their equality pattern. There are \(O_k(1)\) patterns. Entries in a single compensation vector must be distinct, and the disjoint size ranges imply that equality is possible only between samples of the same compensation type. For each distinct internal sampled prime \(b\), let \(n_b\) be its multiplicity in the pattern. The product of the weights in (118) is then \[\prod_b b^{n_b}.\] We retain all the other support restrictions for the moment.

Write \(x_+,x_-\) for the top giant entries. The negative giant \(x_-\) is an actual prime in both environments; \(x_+\) is a prime in the final environment and an external positive integer in the diagonal environment. Let \(d\) be the product of the \(m\) distinct spectator primes, and let \(c_{\rm sm}\) be the product of the distinct actual regular small primes at the top. The internal samples are disjoint from these primes by their types. Define \[ R_f=\prod_{\nu}|\nu|,\qquad Q_f=R_f^{k+2}, \qquad \log Q_f=O_k(m), \tag{126}\] where the product includes every frequency in the two histories. Repetitions in this product are allowed. A modulus equal to one has its usual trivial interpretation. Every small prime in the construction is larger than every frequency and hence is coprime to \(Q_f\).

At a reversing node write the two current giant entries as \(X_+,X_-\) and factor its child products as \[ H_+=X_+C_+M_+,\qquad H_-=X_-C_-M_-. \tag{127}\] Here \(M_\pm\) are the products of the bulk slots in the respective child subtrees, and \(C_\pm\) contain their other regular small factors. The latter may include compensation samples from preceding reversals on the path. Both current giants are rational linear functions of \(x_+,x_-\), by (117).

We first justify an exhaustive residue description of the support. Assume temporarily that the top giants are coprime and that both are units modulo \(c_{\rm sm}d\). Suppose that a current state is pairwise coprime. At its reversal the numerator is \[ N=vH_--wH_+,\qquad p=\frac{N}{su}. \tag{128}\] Every prime divisor of \(H_+\) is coprime to \(H_-\) and to \(v\): for an actual small prime this follows by size, and for a giant factor it is one of the giant–frequency unit conditions. Hence \(N\) is a unit at every prime factor of \(H_+\). The same argument, interchanging the two sides, applies to \(H_-\). If \(p\) is integral, it follows from \(N=sup\) that both \(p\) and \(u\) are automatically coprime to every inherited slot in \(H_+H_-\). In particular, a new compensation sample cannot divide an inherited giant. To obtain a pairwise-coprime child state, it remains only to require that \(p\) be a unit against its own \(u\) and against \(d\).

The following tests therefore describe all the remaining arithmetic support:

1. Modulo frequency factors, impose \(s\mid N\) at every node and impose all giant–frequency unit conditions. These tests are determined by the top and small coordinates modulo \(Q_f\). Division by a node frequency loses at most one factor \(R_f\) of precision; the \(u\)’s are units modulo \(Q_f\). At most \(k\) successive divisions occur, so (126) leaves enough precision for every subsequent test.

2. For each \(b\mid u\) at a node, require \[ N\equiv0\pmod b, \qquad N\not\equiv0\pmod{b^2}. \tag{129}\] The entries of the current \(u\) are distinct and are coprime to \(s\), so these are exactly its remaining integrality and own-\(u\) unit requirements. Ancestor denominators involve other compensation types and frequencies; they are units even modulo \(b^2\). Thus the tests can also be computed directly from the rational expressions in the top giants.

3. Require the top giant units modulo \(c_{\rm sm}d\). At each spectator \(q\mid d\), use the zero convention in (83) whenever an inserted giant vanishes modulo \(q\).

These tests, together with positivity and the real cutoffs, agree with ordinary recursive evaluation over the integers. Indeed, assuming the ancestors have already been evaluated integrally, the first two tests give divisibility by the relatively prime factors \(s\) and \(u\). The preceding coprimality argument then passes the required support to the children. This proves the assertion by induction down the tree.

At a spectator \(q\), put \(D'=d/q\). Formula (127), the order of the child giants, and (117) identify the spectator factors from a history with the tree value in (83). In particular, if the bulk product at leaf \(i\) is \(M_i\), the constants at a child have the product consistency required in that formula. Denote the two tree values by \(W_{1,q},W_{2,q}\). Their combined spectator factor is \[ \prod_{q\mid d}W_{1,q}\overline{W_{2,q}}. \tag{130}\] The zero convention incorporates precisely the inserted-giant unit tests at \(q\).

Let \(\Xi\) denote the product of all smooth real factors in the two histories, including \(K_{\rm ar}\) when it is present, but excluding \(\prod_b b^{n_b}\). Define it for real positive top and small variables by using (117) over \(\mathbb R\). Set the contribution to zero if an inserted \(p\) is nonpositive. This is a smooth extension: the factor \(\varphi(\log p-G)\) already vanishes for \(p<e^{G-1}\). Counterpart role indicators involving nonbulk slots are retained as restrictions on those variables; all bulk priors and their role ranges are identical, so no such indicator cuts a bulk log coordinate.

There are \(r\) leaf factors in each history. On their common support, the modulus in each instance of (116) has logarithm \(\log X+\Delta_0+O_k(1)\). This follows from the giant cutoffs, all the specified small-prime ranges, and both sum bins at that leaf. Consequently \[ |\Xi|\leq e^{-r\Delta_0+O_k(1)}. \tag{131}\] Its first derivatives in the log coordinates of the top giants and bulk slots are bounded by \(\exp(O_k(m))\). To check the possible cancellation in (128), use (114) at each subtree. Each of \(|vH_-|\) and \(|wH_+|\), divided by \(|s|up\), is at most \[\exp(\Delta_j+E_{j-1}+O_k(1))\] at a node of level \(j\). The depth is bounded by \(k\), so repeated logarithmic differentiation along a path costs \(\exp(O_k(m))\). The remaining cutoffs, the bounded Fourier arguments in the leaf factors, and \(K_{\rm ar}\) satisfy the same bound. The bounds extend over support boundaries: any problematic nonpositive inserted value lies outside the giant cutoff, where the smooth extension is zero. We use the actual prior ranges as integration domains, so no extra discontinuous real indicator is needed.

A progression estimate retaining the exceptional term

We record the precise approximation needed for the two successive idealizations. In the following table, either row may be used: \[ \begin{array}{c|rrrrrr} &a_0&a_1&\mu&\delta&\delta'&\theta\\ \hline \mathrm{giant}&.049&.95&.012&.015&.018&.022\\ \mathrm{bulk}&.0039&.007&.0012&.0014&.0016&.0018 \end{array} \tag{132}\]

For each row, choose the possible exceptional character in Lemma 17 before fixing the nongiant priors. If its conductor has a prime factor at least \[ T_*=\exp(e^{.0004L}), \tag{138}\] delete one such prime value from every nongiant prior. This prescribes at most two deletions, as allowed in the construction. Every prime factor of the moduli below outside \(Q_f\) exceeds \(T_*\), whereas every prime factor of \(Q_f\) is smaller than \(T_*\) by (126). Hence if an exceptional conductor still divides one of these moduli, its full conductor divides \(Q_f\). Indeed, a selected large prime factor has been excluded, and otherwise all conductor prime factors must lie in the \(Q_f\) part; coprimality with the other parts also accounts for their exponents. Thus every surviving Page correction depends only on the real coordinate and the \(Q_f\) residue. It does not couple any of the other CRT coordinates.

Idealization of the top giants

Condition on all actual small primes, including the internal samples in both histories. At fixed frequencies, the logarithm of the product of their large weights and all pointwise transform bounds is at most \(e^{.012L}\) for large \(L\). More explicitly, the regular and internal small-prime products have logarithms \[ O_k(e^{.01L})+O_k(m e^{.006L}), \tag{139}\] and the spectator products have still smaller logarithms. Use \(|g_\ell|\leq\sqrt\ell\) and \(|\widetilde g_\ell|\leq1\) for their local pointwise bounds. All the factors \(\prod b^{n_b}\) are included in this estimate.

We may now remove the temporary assumption that the two top giants are coprime, using the residue description just obtained as the extension. In the prime environment the discrepancy is equality of the two primes; its probability is at most \(e^{-G+O(L)}\). In the external-integer environment, a fixed prime \(x_-\) has only \(O(1)\) positive multiples in the log cell for \(x_+\), and their normalized total mass is \(O(e^{-G})\). Multiplying by the preceding pointwise bound is harmless, because \(G\geq e^{.049L}\).

Use the modulus \[ M_*=c_{\rm sm}dQ_f\prod_b b^2. \tag{140}\] Its factors are pairwise coprime, and (139) gives \(\log M_*\leq e^{.012L}\). The giant log cells lie in \([e^{.049L},e^{.95L}]\), by their selection from (60). Lemma 17, with the original cell cutoff and normalization, replaces each top prime by a real log coordinate and a Haar-unit residue modulo \(M_*\). Its density is the principal harmonic density times the correction in (133). For an external integer the analogous replacement uses \[ e^{t-G}\varphi(t-G)\,dt \tag{141}\] and uniform residues on all classes modulo \(M_*\). Elementary counting of integers in a progression gives this replacement with error \(e^{-G+O(L)}\) per interval and residue. The total ideal measure of each coordinate is bounded. A prime cell’s normalizing reciprocal costs only \(\exp(O(L))\).

We give a joint error estimate so that no conditional equidistribution is implicit. Partition both log cells using mesh \(\eta_g=\exp(-e^{.015L})\) and freeze the smooth factor \(\Xi\) in each box. All other tests at fixed small variables and frequencies are residue tests. The variation error, including the pointwise costs above, is bounded by \[\exp\bigl(-e^{.015L}+O(e^{.012L})+O_k(m)\bigr).\] The logarithm of the total number of boxes and pairs of residue classes is \(O(e^{.015L}+e^{.012L})\). Thus the absolute interval errors from the giant row of (133), even summed over all these boxes and classes and multiplied by the pointwise bound, contribute at most \[\exp\bigl(-c e^{.018L}+O(e^{.015L})+O(e^{.012L})+O_k(m)\bigr).\] The integer-coordinate errors have the still stronger negative term \(-G\). It follows that the whole giant replacement has uniform error \[ O\bigl(\exp(-e^{.013L})\bigr). \tag{142}\] The Page factors are part of the measures in this argument; they need not be frozen or differentiated.

Integration of the actual and internal small-prime coordinates

In the ideal giant distribution, CRT separates its coordinates, and a surviving Page factor uses only \(Q_f\). First integrate the giant coordinates modulo \(c_{\rm sm}\). In the diagonal environment, \(x_-\) is already a unit there, and \(x_+\) must be restricted from all classes to units. At \(\ell\mid H_{\rm sm}\) the argument of \(g_\ell\) in (121) is a fixed unit divided by \(x_+x_-\). It is therefore uniform on the unit group once both giants are units. Since \(g_\ell(0)=0\) and \(\mathbb E_{a\bmod\ell}|g_\ell(a)|^2=1\), the average of its squared modulus on units is \(\ell/(\ell-1)\). Independence over \(\ell\) gives \[ \frac{\phi(c_{\rm sm})}{c_{\rm sm}} \prod_{\ell\mid H_{\rm sm}}\frac{\ell}{\ell-1} =\prod_{\ell\mid u_{\rm out}}\left(1-\frac1\ell\right), \tag{143}\] where \(u_{\rm out}\) is the actual outer compensation product of type \(j\) in the diagonal environment. This factor is bounded by one and is independent of the bulk values. In the final environment the analogous integral equals one. The support descent proved above shows that no remaining test uses these giant coordinates modulo the actual regular small primes.

Fix now a distinct internal sampled prime \(b\). Each of its occurrences requires a numerator in (128) to vanish modulo \(b\). This numerator is a nonzero linear form in \((x_+,x_-)\) modulo \(b\). To see nonvanishing, along its ancestor path each substitution retains one giant entry and replaces the other by a linear combination with two unit coefficients. Its matrix is invertible modulo \(b\), and the current numerator is itself a nonzero row applied to this pair. All coefficients are rational expressions in other small regular or internal primes and in the fixed frequencies. No variable of the same compensation type as \(b\) is needed: that type has not yet appeared at any ancestor, and the current numerator does not contain the current \(u\). This also holds across the two histories, and the ancestor transformations are invertible modulo \(b^2\).

If the forms for all occurrences of \(b\) have rank two, they have no solution under the sampled giant residues, because \(x_-\) is a unit. In rank one, their common line has probability \[ \begin{cases} (b-1)^{-1},&\text{both giants prime and both line coefficients nonzero},\\ b^{-1},&\text{$x_+$ external and its coefficient nonzero},\\ 0,&\text{otherwise}. \end{cases} \tag{144}\] For example, in the second case each of the \(b-1\) unit choices of \(x_-\) determines one of the \(b\) choices of \(x_+\). These probabilities multiply over distinct \(b\) by CRT.

Conditional on a rank-one solution modulo \(b\), a forbidden zero modulo \(b^2\) from (129) removes at most \(1/b\) of the uniform lifts: at least one coefficient of the form is a unit. A union bound over its occurrences gives a relative loss \(O_k(1/b)\). To justify dropping these exclusions in the weighted expression, we first bound those weights. For a prime in a compensation log cell, every occurrence prior \(\mu_i\) satisfies \(b\mu_i(b)\leq e^{CL}\), with \(C\) independent of \(k\) once \(L\) is sufficiently large. Thus, selecting any occurrence as representative, \[\left(\prod_{i=1}^{n_b}\mu_i(b)\right) \frac{b^{n_b}}{b-1} \leq 2\mu_1(b)e^{C(n_b-1)L}.\] Summing over the \(O(kr)\) occurrences shows that the joint measure after integrating these line conditions is dominated by independent representative priors times \[ \exp(CkrL). \tag{145}\] Restrictions that representatives be distinct can be discarded for this upper bound. The same domination holds in the external-integer case since \(1/b\leq1/(b-1)\).

After (143), the remaining large pointwise factor is the spectator product. Since there are \(2r\) leaf transforms at each spectator, its logarithm is at most \[ O_k(m e^{.001L}). \tag{146}\] Every internal \(b\) satisfies \(\log b\asymp_k e^{.01L}\). The relative \(O_k(1/b)\) losses, multiplied by (145), (146), and all \(\exp(O_k(m))\) costs, are therefore negligible. We drop all the nonvanishing-modulo-\(b^2\) exclusions henceforth.

Removing arithmetic coincidences in the line conditions

For the signed comparison (125) we need to remove dependence of the line probabilities on accidental bulk congruences. Fix the equality pattern among internal samples. Regard the remaining small-prime representatives and actual small primes as independent formal variables. For each \(b\), clear the denominators in the coefficient-zero and two-by-two minor-zero tests for its forms. Those denominators are units modulo \(b\). We obtain integer polynomials in the fixed frequencies and the formal variables, with no spectator variable and no variable of \(b\)’s compensation type.

The degree is \(O_k(m)\). This follows inductively because each coefficient in a reversal is a product of a subtree’s small slots times a frequency, and there are only \(k\) substitutions on any path. Clearing the products of ancestor denominators and forming a two-by-two minor preserves this bound. The same induction gives, whenever an evaluation is nonzero, \[ \log|P|\leq e^{.012L} \tag{147}\] for large \(L\): the total degrees are \(O_k(m)\), all small-prime logarithms are \(O_k(e^{.01L})\), and the logarithms of the frequency coefficients are \(O_k(m)\).

Replace each test by the question whether its polynomial is identically zero over \(\mathbb Q\). We quantify the error in this replacement under (145). If a polynomial of total degree \(D\) in independent variables is not identically zero and each variable has maximal atom at most \(\alpha\), then \[ \mathbb P(P=0)\leq D\alpha. \tag{148}\] This is a maximal-atom variant of the Schwartz–Zippel argument. Schwartz (Schwartz 1980, Lemma 1, p. 702) gives the sharp total-degree estimate for uniform finite sets; Zippel (Zippel 1979, sec. 3.1, Theorem 1) gives related coordinate-degree zero estimates in sparse interpolation. Earlier random-evaluation identity testing appears in DeMillo and Lipton (DeMillo and Lipton 1978). The proof below extends the uniform-finite-set argument to independent nonuniform laws; that extension is supplied here, not imported from these references. Indeed, write it as a polynomial of degree \(d\) in its last variable, with nonzero leading coefficient of degree at most \(D-d\). Induction bounds the probability that this coefficient vanishes by \((D-d)\alpha\); otherwise there are at most \(d\) roots in the last variable. This proves (148).

All variables occurring here are at least bulk size. Their maximal atoms are at most \(\exp(-c e^{.004L})\), so an accidental exact zero has probability at most \(O_k(m)\exp(-c e^{.004L})\). If the evaluation is nonzero, (147) implies that it has at most \(e^{O(L)}\) distinct prime divisors. The representative \(b\) is independent of this evaluation, because its whole compensation type is absent from the polynomial. Its maximal atom is at most \(\exp(-c_k e^{.01L}+O(L))\), so the probability that it divides this nonzero evaluation is again negligible. A polynomial which is an identity vanishes modulo \(b\) identically, because the cleared denominators are units.

The error bounds remain valid with the other support restrictions: for this purpose discard those restrictions and use the representative-prior domination. Both the original and the replaced line factors are bounded by \(1/(b-1)\), so the same domination applies to their difference. There are only \(O_k(1)\) tests, and multiplying by the spectator bound (146) and all \(\exp(O_k(m))\) factors still gives an error \[ O\bigl(\exp(-e^{.002L})\bigr). \tag{149}\]

We now integrate out the giant coordinates modulo each internal \(b\). For (125) their contribution is its symbolic rank and feasibility flag times the appropriate scalar in (144). The flags depend on the formal pattern and frequencies, not on the sampled bulk values. The line itself leaves no further condition, since no other factor uses the giant coordinates at \(b\) after its \(b^2\) exclusions have been removed. Thus replacing the flags and integrating the line conditions removes all dependence on bulk residues modulo internal primes.

For (124) there is a simpler nonnegative upper bound. Take absolute values in the two-history expansion and replace every line probability by its upper bound \(1/(b-1)\) before using (145). In this estimate rank and feasibility flags are discarded; they do not remain as restrictions on the bulk variables. The symbolic replacement is needed for the signed comparison, but not for this upper bound.

We may also remove distinctness among the actual bulk samples in the simplified expressions. There are \(rm=O_k(m)\) such samples, and their collision probability under independent priors is at most their number of pairs times their maximal point mass. Equations (145) and (146) show that the resulting error is bounded by (149). This step extends the already simplified formula; it does not attempt to use (143) with a nonsquarefree \(c_{\rm sm}\). Keep spectator distinctness and any restrictions involving only nonbulk variables.

Joint idealization of the bulk variables

The remaining dependence on actual bulk values is smooth in their log coordinates or occurs modulo \(dQ_f\). No condition involving their residues at internal sampled primes or at actual regular small primes remains. Furthermore \[ \log(dQ_f)=O_k(m e^{.001L})<e^{.0012L}. \tag{150}\] Use the bulk row of Lemma 17 to replace the \(rm\) bulk priors by their real harmonic densities and Haar-unit residues modulo \(dQ_f\), retaining the possible Page corrections. The actual range \(e^{.004L}\leq\log p\leq e^{.006L}\) is strictly inside the row’s permitted range. Its harmonic normalization is of order \(L\). If a deleted prime lies in the bulk range, removing its single atom has negligible cost by the same maximal-atom estimate just used. Thus the approximation may use the all-prime formula, while keeping the given normalization constants.

Here too the approximation is joint. Let \(N_b=rm\) and partition every bulk log range using mesh \(\eta_b=\exp(-e^{.0014L})\). The logarithm of the number of joint boxes and joint residue classes is at most \[ O_k\bigl(m(e^{.0014L}+L+\log(dQ_f))\bigr). \tag{151}\] Freeze the smooth weight in each box. Equations (145) and (146) bound its remaining total or pointwise cost by \(\exp(O_k(m e^{.001L}))\). The derivative bound gives variation error at most \[\exp\bigl(-e^{.0014L}+O_k(m e^{.001L})+O_k(m)\bigr).\] For the interval errors, even summing over all the boxes and residues in (151) gives the upper bound \[\exp\bigl(-c e^{.0016L} +O_k(m(e^{.0014L}+L+e^{.0012L})) +O_k(m e^{.001L})\bigr).\] Both are \[ O\bigl(\exp(-e^{.00125L})\bigr). \tag{152}\] The bounded masses of the other coordinates add only \(\exp(O_k(m))\). In the main term their real distributions are integrated as measures; the box count is charged only to the approximation errors. There is therefore no box-count factor multiplying a main term.

For fixed \(k\) the number of frequency histories is \(\exp(O_k(m))\), because each frequency has bound \(\exp(O_k(m))\) and there are \(O_k(1)\) nodes. The number of equality patterns is \(O_k(1)\). Thus (142), (149), and (152) remain negligible after the frequency and pattern sums. These errors are uniform for each comparison of assignments. All surviving Page multipliers are functions only of the real and \(Q_f\) coordinates and are bounded by two per sampled prime.

The signed comparison

We prove (125). Condition in the resulting main expression on the real coordinates, the \(Q_f\) coordinates, the nonbulk prime values, and the top-giant residues. The bulk residues on \(d\) are then independent Haar units. The only remaining factor using them is (130). In particular the support descent, (143), and the integrated symbolic line factors have left no additional bulk condition at the other small primes.

At a fixed \(q\mid d\), each bulk slot is an independent Haar unit. In either diagram its leaf products are marginally independent Haar units, because the leaves use disjoint nonempty sets of slots. Jointly, their law is exactly uniform on the subgroup specified by equality of the products in corresponding overlap components. To verify this, regard each bulk slot as an edge of the bipartite overlap multigraph. Its value contributes to the product at both endpoints. In each connected component the product of the left vertex products must equal the product of the right vertex products. Conversely, prescribe vertex products satisfying this relation, set the non-tree edges to one, and choose a spanning tree. Successively eliminate a terminal vertex by assigning its incident tree edge the value needed for that vertex. The last vertex is satisfied by the product relation. This proves surjectivity onto exactly the asserted subgroup. A homomorphism of finite groups sends the uniform distribution to the uniform distribution on its image, proving the claimed joint law.

All frequencies and nonbulk constants needed for Lemma 15 are units at \(q\), and the ancestor and child relations are those of (83). The selected spectator primes satisfy (82) uniformly, with a bound tending to zero; their sizes tend to infinity uniformly as well. Therefore (85) provides a bound \(\epsilon_k(L)\), where \(\epsilon_k(L)\to0\), for the absolute correlation at every spectator, uniformly in the conditioned data. By CRT the bulk coordinates at distinct spectators are independent, so their combined bound is \(\epsilon_k(L)^m\).

The remaining total costs, including the representative domination, bounded masses, and all frequency sums, are \(\exp(O_k(m))\). Consequently \[\left|\mathbb E\sum_s\mathcal G K_{\rm ar} A_l^{(1)}(s)\overline{A_l^{(2)}(s)}\right| \leq \epsilon_k(L)^m\exp(O_k(m)) +O\bigl(\exp(-e^{.00125L})\bigr) =\exp(-\omega_k(m)),\] as required in (125).

The norm comparison and the frequency sums

We finally prove (124). Use the nonnegative upper bound described above. At the \(d\) coordinates, (84) and Cauchy–Schwarz bound the expectation of the absolute product of two tree values by \(3^r\) for each spectator, hence by \(3^{rm}\) in total. Retain the frequency divisibility conditions, and discard the Page multipliers at cost \(2^{rm+O(1)}\). The bulk coordinates modulo \(Q_f\) are now independent Haar units for the upper bound.

Because the assignments agree, the bulk slots split into exactly the same subtrees in the two histories. Fix the other necessary residues. Expose the product of all bulk slots and then expose the products on successive subtree splits, proceeding from the root downwards. Conditional on a parent product, the product \(M_+\) in one child is uniform on the unit group modulo \(Q_f\), and \(M_-\) is determined by \(M_+M_-\). This follows directly from the product map on two disjoint collections of independent Haar units. Ancestor pivots in both histories depend only on previously exposed splits and are known with the precision supplied by (126).

We evaluate support indicators under this original Haar measure, without first conditioning on the validity of the complete histories. All frequencies are fixed at the outset. A current giant’s unit tests against descendant frequencies therefore depend only on already exposed data. Tests on a newly created pivot are evaluated after the split that creates it; tests on later pivots are deferred to their own splits, or discarded for this nonnegative upper bound. Thus the retained earlier tests do not select an unexposed split.

At a node, the support requires \(X_\pm C_\pm\) to be units modulo its frequency. If that unit test fails we stop that branch, whose contribution is zero. Otherwise the condition \[ vX_-C_-M_-\equiv wX_+C_+M_+\pmod{|s|} \tag{153}\] requires \((v,s)=(w,s)\), since all the other factors are units. Put \(g=(v,w,s)\). In a soluble case, division by \(g\) makes both frequency coefficients units modulo \[ a=\frac{|s|}{(v,w,s)}. \tag{154}\] Substituting the fixed parent product \(M_+M_-\) into (153) then fixes \(M_+^2\) to a specified unit modulo \(a\). The other history at the same node fixes a square modulo \(a'=|s'|/(v',w',s')\).

For each odd prime power, a unit has at most two square roots, and for a power of two it has at most four. Thus the simultaneous square equations have at most \(2^{\omega([a,a'])+1}\) solutions modulo \([a,a']\), where brackets denote the least common multiple. If they are inconsistent, their probability is zero. The ordinary divisor bound and \(n/\phi(n)\leq\tau(n)\) give, uniformly for the moduli at hand, \[2^{\omega(n)+1}\frac{n}{\phi(n)}=\exp(o_k(m)), \qquad n\leq\exp(O_k(m)).\] It follows that the conditional probability at this split is at most \[ \frac{\exp(o_k(m))}{[a,a']}. \tag{155}\] Reduction of Haar units modulo \(Q_f\) to this modulus is uniform. All earlier tests are measurable with respect to the earlier exposed products, so these conditional upper bounds multiply along the tree. Failed tests contribute zero and do not alter the upper bound.

It remains to sum (155) over internal frequencies. The requisite numerical estimate is \[ \sum_{a,a'\leq V}\frac1{[a,a']} \ll(1+\log V)^3. \tag{156}\] Indeed, write \(a=du\), \(a'=dv\) with \((u,v)=1\), and then discard the coprimality condition. The left side is at most \[\sum_{d\leq V}\frac1d \left(\sum_{u\leq V/d}\frac1u\right)^2,\] which proves (156). With child frequencies \(v,w\) fixed, every \(s\) giving a specified \(a=|s|/(v,w,s)\) is of the form \(s=\pm ad\) with \(d\mid(v,w)\). Its multiplicity is therefore at most \(2\tau((v,w))\). The analogous bound holds in the other history. Since these gcds and all the frequency bounds are at most \(\exp(O_k(m))\), (156) shows that each pair of internal frequencies sums to \(\exp(o_k(m))\), uniformly in the fixed child frequencies.

Drop the equality of the two root frequencies if necessary for this nonnegative numerical bound. Sum the root pair first while holding the children fixed, then proceed down the tree. Only the \(2r\) leaf frequencies remain, giving at most \((2V_0)^{2r}\) choices. Combining this with (131) and \(E_0=\Delta_0+\sqrt m\) yields \[ (2V_0)^{2r}e^{-r\Delta_0+O_k(1)} =\exp(r\Delta_0+o_k(m)). \tag{157}\] All the other losses fit \(Crm+o_k(m)\) in the exponent. These are the \(3^{rm}\) spectator bound, bounded per-coordinate masses and Page factors, the domination (145), and \(O_k(1)\) equality patterns. The constant can be absolute: the internal-sample count is \(O(kr)\), and \(kL/m\asymp k^{-3}\); fixed-\(k\) constants not proportional to \(m\) are absorbed by \(o_k(m)\). Inserting the negligible approximation errors gives \[\mathbb E\sum_s\mathcal G|A_l(s)|^2 \leq\exp\bigl(r(\Delta_0+Cm)+o_k(m)\bigr).\] This is (124), and completes the proof of Proposition 16.

Counting bad arrangements

At level \(l\) put \(r=2^l\). Call a pair of arrangements of the \(rm\) bulk variables bad if it is not covered by (125). Thus every pair is called bad when \(l=0,1\); when \(l\ge2\), a bad pair has more than \(3r/4\) connected components in its bipartite overlap graph. For each fixed first arrangement, the number of bad second arrangements satisfies \[ N_{\mathrm{bad}}(r,m) \le (m!)^r \exp\bigl((\tfrac14\log r+C)rm+O_k(1)\bigr). \tag{158}\] Here arrangements distinguish all bulk positions and all sampled bulk variables, so they are indexed by permutations even before any distinctness restrictions are imposed.

To prove (158) for \(l\ge2\), write \(a_i\) for the number of leaves on either side of the \(i\)th connected component. The numbers on the two sides agree: every vertex has degree \(m\), and counting the component’s edges on either side gives the equality. If there are \(t\) components, then \[\sum_{i=1}^t a_i=r, \qquad \sum_{i=1}^t(a_i-1)=r-t<\frac r4.\] There are only \(\exp(O_k(1))\) ways to choose and pair the two partitions of the leaf sets into these components. Once they are chosen, the variables incident to a component can be assigned to its second set of slots in at most \((a_i m)!\) ways. For \(1\le a\le r\), \[a\log a =(a-1)\log a+\log a \le(a-1)(\log r+1), \qquad (am)!\le(m!)^a a^{am}.\] The factorial inequality follows by bounding one multinomial coefficient by the sum of all multinomial coefficients with \(a\) parts. Consequently \[\prod_i(a_i m)! \le(m!)^r\exp\left(m\sum_i a_i\log a_i\right) \le(m!)^r\exp\left(\frac14(\log r+1)rm\right),\] which proves the claim. For \(r=1,2\), the upper bound \((rm)!\le(m!)^r r^{rm}\) proves the same assertion after enlarging the absolute constant \(C\). Nonbulk matchings in a diagonal have only \(\exp(O_k(1))\) possibilities, since their number of slots is fixed once \(k\) is fixed.

We shall also use the corresponding bound for the fraction of bad arrangements. Since \(m!\le m^m\) and \((rm)!\ge(rm/e)^{rm}\), \[ \frac{N_{\mathrm{bad}}(r,m)}{(rm)!} \le\exp\bigl((-\tfrac34\log r+C)rm+O_k(1)\bigr). \tag{159}\]

Diagonal bounds and the order of parameter choices

Let \(\mathcal D_j\) be the nonnegative diagonal contribution in the extended square at step \(j\), before the factor \(e^{c_g}\) in (119). At this step the two compared amplitudes have level \(j-1\) and \(r_j=2^{j-1}\) leaves. We first estimate the bad matchings.

For each such matching, apply \(|A^{(1)}\overline{A^{(2)}}|\le (|A^{(1)}|^2+|A^{(2)}|^2)/2\) on their simultaneous support, after the nonnegative-square reduction that gives (121). For either retained square, extract the point probability of the other ordered tuple. On this support it is at most \[C_H\exp(-T_H+O_k(1)), \qquad C_H\le L^{-r_jm}\exp(Cr_jm+O_k(1)).\] The retained tuple is then summed with its own priors. This order of extraction is valid for both squares, including when a matching exchanges positions with different log-cell priors. The external integer measure and the \(u\) weight contribute \(\exp(G+r_jw_j)\); by (114), their combination with \(\exp(-T_H)\) is \(\exp(-\Delta_j)\). All remaining Archimedean factors are bounded by \(\exp(O_k(1))\) on the simultaneous support. Thus the one-assignment estimate (124), followed by (158), bounds the bad part by \[\exp(-\Delta_j) L^{-r_jm}(m!)^{r_j} \exp\bigl(r_j\Delta_0+ (\tfrac14\log r_j+C)r_jm+o_k(m)\bigr).\] Since \(m/L\le z\), we have \(L^{-r_jm}(m!)^{r_j}\le\exp(r_jm\log z)\). We obtain \[ \mathcal D_{j,\mathrm{bad}} \le \exp\left( -\Delta_j+r_j\bigl\{\Delta_0+ (\log z+\tfrac14\log r_j+C)m\bigr\}+o_k(m) \right). \tag{160}\] For every other matching, (125) applies with its stated Archimedean multiplier. After the probability extraction, the number and size of these terms cost at most \(\exp(O_k(m))\): in particular, \[(r_jm)!L^{-r_jm} \le\exp\bigl(r_jm\log(r_jm/L)\bigr) =\exp(O_k(m)).\] Their total is therefore \(\exp(-\omega_k(m))\). In this notation, \(\omega_k(m)/m\to\infty\) at every fixed \(k\). Combining the two parts, \[ \mathcal D_j\le \exp\left( -\Delta_j+r_j\bigl\{\Delta_0+ (\log z+\tfrac14\log r_j+C)m\bigr\}+o_k(m) \right)+\exp(-\omega_k(m)). \tag{161}\]

We specify the parameter order and the reserve in the iteration. The constant \(B_s\) has already been chosen sufficiently large for (113), whose constant \(B_*\) is independent of the later gaps and of \(k\). Write \[Z_G=\sum_{p\ \mathrm{prime}} \frac{\varphi(\log p-G)}p, \qquad c_g=\log Z_G^{-1}.\] The giant range and the prime-cell normalization give \(Z_G\sim G^{-1}\) and \(c_g\le .91L\) for all sufficiently large \(L\), with the coefficient \(.91\) independent of all the gap choices and \(k\). Fix, now, \[ B=B_*+3. \tag{162}\] Choose \(B_z\ge9\) and then choose \(B_D\) so large that \[ B_D\ge B_s+2B+C+6, \tag{163}\] where \(C\) dominates the uniform constant in (161). These are fixed constants, chosen before \(k\).

Indeed, substitution from (108) shows that the exponent of the first term in (161), divided by \(r_jm\), is \[ B_s-B_D+(9-B_z)\log z -\frac3{20}\log r_j+C+o_k(1). \tag{164}\] Hence, for every sufficiently large fixed \(k\) and then sufficiently large \(L\), uniformly for \(1\le j\le k\), \[ \mathcal D_j\le\exp\bigl(-(2B+3)r_jm\bigr). \tag{165}\] The precise choice of \(k\) will be made below. We require already that it be large enough that, using \(m=k^4L+O(1)\), \[ \frac{c_g+\log2}{m}\le\frac2{k^4}<1 \tag{166}\] for all sufficiently large \(L\).

The transfer identity underlying (119) gives \[e^{-c_g}|\eta_{j-1}|^2 \le\mathcal D_j+\eta_j \le\mathcal D_j+|\eta_j|.\] If \(|\eta_{j-1}|\ge\exp(-Br_jm)\), then (165) and (166) imply \(\mathcal D_j\le\tfrac12 e^{-c_g}|\eta_{j-1}|^2\). Therefore \[ |\eta_j|\ge\frac12e^{-c_g}|\eta_{j-1}|^2. \tag{167}\] Starting with (113), induction proves simultaneously this estimate and the sharper bound \[ -\log|\eta_j| \le 2^jB_*m+(2^j-1)(c_g+\log2) <B2^jm, \qquad 0\le j\le k. \tag{168}\] For the induction, the sharper bound at \(j-1\) supplies the coarse hypothesis needed for (167); that inequality then gives the displayed sharper bound at \(j\). Its final inequality follows from (162) and (166). In particular the reserve is inherited from the initial estimate rather than spent afresh at each step.

The transfers have now retained an exponential lower bound for \(|\eta_k|\). We will obtain the opposite bound by averaging \(A_k\) over the bulk arrangements. Since \(G_R(s/d)\) depends only on their prime values, not their positions, it is common to these arrangements. The Cauchy–Schwarz step therefore also requires a norm estimate for this regular-transform factor.

The norm of the common regular transform

At the final level put \(r=2^k\). The sum over \(s\) in this subsection is over the nonzero signed integers with \(|s|\le V_k\). We claim \[ \mathbb E_{\mathbf d,\mathcal I_k} \sum_{0<|s|\le V_k}|G_R(s/d)|^2\ll V_k, \tag{169}\] with an absolute implied constant for sufficiently large \(L\) at the fixed parameters. Only the pairwise-distinctness and coprimality zero conventions of \(G_R\) are needed here; bins and all history restrictions belong to the amplitudes.

Fix \(s\), the spectator list \(\mathbf d\), the actual regular small primes, and one of the two giant primes, denoted by \(q\). Configurations with a repeated regular small prime or with a regular small prime dividing \(d\) already give zero and can be discarded. Let \(C\) be the squarefree product of the remaining regular small primes, and call the other giant \(p\). Both giant transforms have absolute value at most one. After dropping their squared absolute values, the remaining factor is \[ F(p\bmod C),\qquad F(a)=\prod_{\ell\mid C} \left|g_\ell(a_\ell a^{-1}\bmod\ell)\right|^2, \qquad a_\ell=\frac{s}{dq(C/\ell)}\pmod\ell . \tag{170}\] All \(a_\ell\) are units: the retained primes are distinct and coprime to \(d\), and \(0<|s|\le V_k\) is smaller than every actual slot prime. The restriction \(p\ne q\) may now be dropped, since the remaining nonnegative expression is still defined when \(p=q\). The giant range is disjoint from all the small-prime ranges, so every prime \(p\) in its cell is a unit modulo \(C\).

Write \(U_C=(\mathbb Z/C\mathbb Z)^\times\). By the Chinese remainder theorem, as \(a\) varies uniformly over \(U_C\), the arguments \(a_\ell a^{-1}\pmod\ell\) are independent uniform nonzero residues. The exact local normalizations \(g_\ell(0)=0\) and \(\ell^{-1}\sum_x|g_\ell(x)|^2=1\) therefore give the identities \[ \sum_{a\in U_C}F(a)=C, \qquad \frac1{\phi(C)}\sum_{a\in U_C}F(a) =\frac C{\phi(C)} =\prod_{\ell\mid C}\frac\ell{\ell-1}. \tag{171}\] Here \(\phi\) is Euler’s totient. There are \(O_k(m)\) factors, and every such prime is at least \(\exp(\exp(.004L))\). Consequently \(C/\phi(C)=1+o_k(1)\) uniformly in the fixed lists. This calculation uses no uniform pointwise bound on the small-prime transforms.

We next justify the averaging over the actual prime \(p\), including the possible exceptional term. The size bounds for the final list give \[\log C=O_k(h+m\exp(.006L))\le\exp(.012L)\] for sufficiently large \(L\), so the giant row of (133) applies with modulus \(C\). With the positive constant \(c\) from that estimate, put \[\varepsilon_L=\exp(-c\exp(.018L)).\] Splitting the support of \(\varphi(t-G)\) into intervals of length at most one and applying partial summation gives, uniformly for \(a\in U_C\), \[\begin{align*} \sum_{\substack{p\ \mathrm{prime}\\p\equiv a\pmod C}} \frac{\varphi(\log p-G)}p &=\frac1{\phi(C)}\int \frac{\varphi(t-G)}t \bigl(1-\chi_*(a)e^{(\beta_*-1)t}\bigr)\,dt +O(\varepsilon_L). \tag{172}\end{align*}\] As in (133), the exceptional term is omitted if it is absent or its conductor does not divide \(C\). When it is present, \[0\le1-\chi_*(a)e^{(\beta_*-1)t}\le2.\] This pointwise inequality suffices even if the exceptional character correlates with \(F\).

Multiply (172) by \(F(a)\), sum over \(a\in U_C\), and divide by \(Z_G\). Since \(F\ge0\), the exact sum in (171) both bounds the main term and sums the absolute progression errors. It follows that \[ \mathbb E_p F(p\bmod C) \le 2\frac C{\phi(C)} \frac{\displaystyle\int\varphi(t-G)\,dt/t}{Z_G} +O(Z_G^{-1}C\varepsilon_L) =2+o_k(1). \tag{173}\] Indeed the integral divided by \(Z_G\) is \(1+o(1)\) by ordinary prime-cell normalization. Moreover \(Z_G^{-1}=\exp(O(L))\) and \(\log C\le\exp(.012L)\), whereas \(\varepsilon_L=\exp(-c\exp(.018L))\), so the summed error is \(o(1)\). All estimates are uniform in \(s\), \(\mathbf d\), \(q\), and the retained small-prime list. Averaging those variables and summing over the at most \(2V_k\) frequencies proves (169).

Symmetrization and contradiction

Let \(\mathfrak S_{rm}\) permute the values in all \(rm\) bulk positions, keeping every other position fixed. The bulk priors are identical, including their allowed prime deletions, so their joint law is invariant under this action. Also \(G_R(s/d)\) is unchanged: the product \(R\), the set of its prime factors, the exact transform attached to each bulk prime value, and every argument \(s/(d(R/\ell))\) are unchanged. Its distinctness and coprimality zero conventions are invariant as well. Define \[ A_{\mathrm{sym}}(s) =\frac1{(rm)!}\sum_{\pi\in\mathfrak S_{rm}}A_k^\pi(s), \tag{174}\] where \(A_k^\pi\) has its bulk values placed according to \(\pi\). Changing variables separately for each permutation in (115) yields \[\eta_k=\mathbb E\sum_{0<|s|\le V_k}G_R(s/d)A_{\mathrm{sym}}(s).\] In this operation all bins and history-dependent support conditions remain inside their respective \(A_k^\pi\); they need not be invariant. Cauchy–Schwarz and (169) give \[ |\eta_k|^2 \le\left(\mathbb E\sum_s|G_R(s/d)|^2\right) \left(\mathbb E\sum_s|A_{\mathrm{sym}}(s)|^2\right) \ll V_k\mathbb E\sum_s|A_{\mathrm{sym}}(s)|^2. \tag{175}\]

Expand the second factor into ordered pairs of permutations. Each bad pair is at most \(\exp(r(\Delta_0+Cm)+o_k(m))\) in absolute value by Cauchy–Schwarz and the two one-assignment bounds (124). Its fraction among all pairs is bounded by (159). Each remaining pair satisfies (125); that estimate is uniform, so averaging these pairs preserves its bound. Consequently \[ |\eta_k|^2\ll e^{E_k} \left[ \exp\bigl(r\{\Delta_0+(-\tfrac34\log r+C)m\}+o_k(m)\bigr) +\exp(-\omega_k(m)) \right]. \tag{176}\]

For completeness, the sums in (108) satisfy \[\sum_{j=1}^k r_j=r-1, \qquad \sum_{j=1}^k r_j\log r_j =r\log r-2r\log2+2\log2.\] They give, in particular, the convenient upper bound \[ \frac{E_k}{rm} \le\frac25\log r+B_D+B_s+(B_z+8)\log z+o_k(1). \tag{177}\] Since \(\Delta_0/m=B_s+8\log z\), the logarithm of the first term on the right of (176), divided by \(rm\), is at most \[ -\frac7{20}\log r+B_D+2B_s+(B_z+16)\log z+C+o_k(1). \tag{178}\] All constants here have already been fixed. Now choose \(k\) sufficiently large, retaining (166), that the expression in (178) without its \(o_k(1)\) term is less than \(-2B-4\). This is possible because \(\log r=k\log2\) while \(\log z=4\log k\). Finally take \(L\) sufficiently large. The first term of (176) is then at most \(\exp(-(2B+3)rm)\), after absorbing its absolute implied constant. The second term remains \(\exp(-\omega_k(m))\), since \(E_k=O_k(m)\). Thus, for sufficiently large \(L\), \[|\eta_k|^2\le\exp(-(2B+1)rm).\] This contradicts (168), which gives \(|\eta_k|^2\ge\exp(-2Brm)\). The assumed decomposition is therefore impossible: no two infinite subsets of \(\mathbb N_0\) have a sumset whose symmetric difference with the positive primes is finite. This proves Theorem 4.