The additive indecomposability of the primes

=3

1 Introduction

Let \mathcal P denote the set of positive primes, and put \N_0=\{0,1,2,\ldots\}. For A,B\subseteq\N_0, write A+B=\{a+b:a\in A,\ b\in B\}. Two subsets of \N_0 are asymptotically equal if their symmetric difference is finite. Ostmann’s conjecture asserts that \mathcal P is asymptotically additively indecomposable: it is not asymptotically equal to A+B when both summands contain at least two elements. The conjecture goes back to his 1956 treatise [30, p. 13]; the eventual-equality formulation and its terminology are recorded explicitly in [11, Definition 1.1 and Conjecture 1.2]. It is also known as the inverse Goldbach problem.

Laffer and Mann showed that a hypothetical decomposition must have two infinite summands [25, Theorem 12]. We first give a short sieve proof of this reduction in Lemma 2.2, then state the two-infinite-set contradiction as Theorem 2.3. The rest of the paper proves that theorem.

The conclusion concerns both eventual coverage of the primes and eventual exclusion of composite sums. Neither requirement is replaced by a density condition. In particular, if |A|,|B|\ge2 and A+B contains every sufficiently large prime, then it contains infinitely many composite numbers.

Earlier work established increasingly strong restrictions on a hypothetical decomposition. Hornfeck’s work [21, 22] was followed by sieve arguments of Pomerance, Sárközy and Stewart [31], Hofmann and Wolke [20], and Elsholtz [9]. Write A(x)=|A\cap[0,x]| and similarly for B. Bounds such as A(x)B(x)\ll x are compatible with the coverage lower bound A(x)B(x)\gg x/\log x and therefore do not by themselves exclude a decomposition. Elsholtz combined the large and larger sieves to put both counting functions at the square-root scale, up to powers of \log x, and ruled out a decomposition into three nontrivial summands [8]. His later refinement [10, Theorem 1.9] gives the bounds reproduced in Lemma 2.4. Croot and Elsholtz also studied thin ternary sumsets contained in the primes, obtaining restrictions under a regularity hypothesis on representation multiplicities [3, Theorem 1]. Shao later proved a finite ternary obstruction: for some absolute c>0, three subsets of [1,N], each of size at least N^{1/3-c}, have a composite number in their sumset once N is sufficiently large [34, Theorem 1.3 of the preprint version]. In their positive-integer formulation, Elsholtz and Harper sharpened the binary counting bounds to

under a hypothetical eventual decomposition [11, Theorem 2.6].

Green and Harper developed inverse questions for the large sieve and proved that a suitable inverse-sieve conjecture would imply Ostmann’s conjecture [16, Conjecture 1.5 and Theorem 1.8]. Their conjecture proposes a quadratic description of sets near the square-root sieve bound. Under half-residue restrictions |C\bmod p|\le p/2+O(1) at every prime and |C|\gg\sqrt N for C\subseteq[1,N], Hanson proved additive correlation with the squares and a logarithmic-size intersection with a quadratic image [17, Theorem 1.2 and Corollary 1.3]. Croot, Mao and Yip subsequently proved inverse theorems for local restrictions to short arithmetic progressions, with extensions to unions of progressions and other additive structures [5]. More recently, Croot, Mao, Pohoata and Yip used a weighted entropy argument to derive a further necessary condition for a hypothetical decomposition of the primes into two sets of positive integers, each containing at least two elements [4, Theorem 1.10 and Corollary 1.11]. For some c>0 and every sufficiently large N, each summand then has at least \exp(c\sqrt{\log N}/(\log\log N)^{3/2}) elements in [1,N] lying in an integral quadratic image m\pm\Z^2; the product of the two intersection sizes is at least \exp(c\sqrt{\log N}/\log\log N). These quadratics may depend on N.

These large intersections with quadratic images fall short of the near-containment required by Green and Harper’s conditional route. Our proof uses the simultaneous residue restrictions and coverage of every sufficiently large prime to reach a contradiction without such a classification.

Under a hypothetical decomposition, put D=-B. For each prime p, deleting finite initial segments from A and B leaves disjoint images of A and D in \F_p. Completing these subsets to a partition gives a residue set S_p and its complement. The collision estimate in Section 2 shows, on suitable prime averages, that the two parts have approximately equal size and that the summands are approximately uniform on their respective parts.

The next stage rules out persistent correlations with translated multiplicative characters. Section 3 treats quadratic characters with independently chosen translating centers at every prime. A moment argument and Poisson summation force a common rational center. The quadratic large sieve then confines positive fractions of long tails of the summands to a small family of quadratic kernels, leading to a collision contradiction. Section 4 treats all higher character orders by repeated Cauchy–Schwarz transfers. Its anchor variables distinguish the copied terms and supply the character cancellation needed to control the diagonals. Together these arguments give the mixed-character decorrelation in Corollary 4.2.

Prime coverage enters separately in Section 5. A tensor estimate shows that the normalized additive transforms of the residue indicators cannot have small L^1 norm on too much harmonic prime mass. The proof compares a nonnegative sumset statistic with its average over the primes. This comparison retains the coverage information beyond the preliminary lower bounds for the summands.

The remaining residue indicators need not have a prescribed algebraic form. Section 6 proves a finite-field comparison for the binary trees produced by the transfers, using the mixed-character decorrelation. Its hypotheses involve only a probability L^2 bound and mixed-character correlations; they permit highly nonuniform pointwise values. This feature is needed for the exact Fourier transforms of the residue indicators. Sections 7 and 8 construct a positive statistic and establish its comparison estimates. The arithmetic separation includes repeated internal prime labels, coprimality conditions, and the possible exceptional real character in prime progression estimates. Finally, Section 9 averages over permutations of the bulk variables. Most pairs of arrangements have few overlap components and hence small correlation. Their total contribution and the remaining diagonal terms contradict the lower bound inherited from the positive statistic. The transfer depth is chosen sufficiently large and fixed before the large scale tends to infinity.

This proves asymptotic indecomposability directly from the simultaneous residue restrictions and prime coverage. The argument does not require the general inverse-sieve conjecture of [16], and no such general classification theorem is asserted here.

2 Finite summands and residue supports

For C\subseteq\N_0, put C(Y)=|C\cap[0,Y]|. All logarithms are natural.

We use e(x)=\exp(2\pi i x) and e_m(x)=e(x/m). An expectation over a finite set means its uniform probability average unless another probability law is specified. Multiplicative characters, including the principal character, are extended by zero at zero. For functions on \F_p our Fourier convention is

Norms of functions on a finite field use probability measure. A mass function \mu of a probability measure instead uses the counting norm \|\mu\|_2^2=\sum_x|\mu(x)|^2 when explicitly so stated below. This distinction is useful in the collision estimate.

2.1 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

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 [27, Theorem 1]; see also Green and Harper [16, Proposition 3.1]. The estimate applies to arbitrary complex coefficients. Restricting its outer sum to prime or squarefree moduli is permitted by nonnegativity.

2.2 The two-infinite-set theorem

It remains to prove the following technical theorem.

Together with Lemma 2.2, this proves Theorem 1.1: a counterexample to the latter would have both summands infinite and would therefore contradict Theorem 2.3.

For the remainder of the proof, suppose to the contrary that infinite sets A,B\subseteq\N_0 satisfy this eventual equality. Fix a threshold N so that both of the following statements hold:

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.

2.3 Complementary residue supports

For every prime p, the residue sets

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 \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.

2.4 Sizes of the summands

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

2.5 Collision stability

The congruent-pair count underlying Gallagher’s larger sieve [13] 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 [16, 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:\F_p\to\C has probability squared norm at most one, then

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 2.4, uniform measures on

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).

3 Quadratic characters with arbitrary translating centres

We retain the sets A,D=-B, the partitions S_p,S_p^c, and the densities \sigma_p=|S_p|/p from Section 2. For an odd prime p, let \chi_p be the quadratic character of \F_p, extended by zero at zero. The translating residues in the following proposition need not arise from a common integer or rational number.

The main difficulty is that the translating residues are initially unrelated. An amplified moment and Poisson summation, with estimates uniform over a polynomial-sized family of coefficient arrays, first produce a common rational centre for many primes. The quadratic large sieve then confines positive fractions of the two endpoint tails to a few quadratic kernels, whose populations contradict the collision estimate.

4 Translated characters of higher order

In this section the harmonic mass of a set of primes \mathcal P is \sum_{p\in\mathcal P}p^{-1}. All multiplicative characters are extended by zero at zero. The parameters introduced in this section are local to its proof.

We now prove translated decorrelation for every character of order greater than two. Repeated Cauchy–Schwarz steps create copies of the prime variables, and pairs of smaller and larger anchor primes distinguish their positions. Changing a position then exposes a one-sided interaction involving the square of a selected character. That square is nonprincipal because the character has order greater than two. The final corollary combines this argument with the quadratic conclusion of Section 3.

5 A supply of nonsparse additive transforms

We retain the sets S_p, their densities \sigma_p, and the normalized functions F_p,g_p defined in Corollary 4.2. The normalizations give

The conclusion below is a separate consequence of the sieve estimates and prime coverage. It does not require the decorrelation assertion in (4.16). Write

for the probability L^1 norm of the normalized additive transform.

Suppose, to the contrary, that primes with small \gamma_p have large harmonic mass. We shall construct a nonnegative weight from their sparse Fourier spectra. A tensor estimate bounds its sum over pairs of summand elements, while a prime-distribution estimate evaluates its sum over large primes. Prime coverage forces a lower bound for the former sum, and the contraction furnished by the sparse spectra will make the bounds incompatible.

5.1 A budget for centered tensor coordinates

Throughout this section we reset the large parameters by

Set

Both sets are nonempty for large L, by (2.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 2.5 at Y=X(\log X)^{40}, using the uniform measures on its two full tails. By (2.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

For the second assertion, use (\log t)^2\le t+t^{-1}-2 for t>0 and Cauchy–Schwarz:

The last prime sum converges.

Let \mathbf e_x be the standard point vector in \C^{\F_p}. Let Q_{S_p} be the orthogonal projection onto

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

and define B_D(t) with D_0,T_p.

The precise energy identity we need is

Indeed, the Ramanujan kernel factors over the primes of q. For x,y\in S_p,

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 (5.3). For D_0, the same identity holds with \kappa_p^{-1}. In particular all terms in both expansions are nonnegative.

Write

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

The error terms are uniform over t for each fixed C_*. To prove this, note first that

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

Also, by (5.2),

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

The additive large sieve, applied to the probability measure on A_0, bounds the sum of the left side of (5.3) 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

This proves the first assertion, and the reciprocal argument proves the second. Notice in particular the consequence of the t=1 terms:

5.2 A contracting local kernel from a sparse transform

Fix a sufficiently small absolute \eps_0>0; all conditions on its size below are absolute. Choose 0<\delta_0\le\eps_0^2. Suppose, for a sequence of arbitrarily large L, that (5.1) fails. Let

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 (5.2) gives

It follows that H\ge .70L-o(L). We shall use the weaker bound

which remains valid after deleting any one prime of \mathcal S.

For p\in\mathcal S define

This set is symmetric, avoids zero, and satisfies

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

These functions are real. Let \Pi_p be the orthogonal projection in \C^{\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,

The latter assertions follow by Parseval from (5.7).

Let B_p^{(2)} denote the raw matrix with entries b_p(x-y)^2. Its additive Fourier eigenvalue at s is

Consequently

For later use, if e_p^*=|E_p|/p, direct orthogonality gives

In particular both unit means are O(\eps_0/p).

For a kernel h(x-y), let h also denote its raw matrix, and set

The map from \C\oplus\mathcal H_{T_p} to \C\oplus\mathcal H_{S_p} defined by

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

5.3 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

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

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 5.2 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

We also have U=\exp(O(\eps_0L))>0, and

Choose the fixed C_K so large that the right side of (5.12) 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

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 (5.4), with any fixed C_*>2C_K, gives

The kernel identity, the operator norm bound, and Cauchy–Schwarz now give

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.

5.4 The prime mean of the weight

Set

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 (5.13), using the one-prime removal of an exceptional conductor as in [12, Section 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 (5.6) and (5.13) 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

Multiplicative Fourier inversion expresses b_p(x)^j as \sum_\lambda c_{p,j}(\lambda)\lambda(x) on \F_p^*. Equations (5.8) and (5.9), followed by Cauchy–Schwarz, give

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 (5.11) 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

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 (5.18). 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

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 (5.15). The principal coefficient retains its signs and satisfies exactly

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 (5.19) holds on all desired prime inputs. Apply (5.15) to the grouped sum, taking its fixed D_1 larger than the absolute constants in (5.20) and in U=\exp(O(\eps_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

The absolute contribution of all these terms to the grouped character sum is at most

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

5.5 Using coverage of every sufficiently large prime

The elementary bound |b_p(n)|\le1 gives, with M_{\mathcal S}=|\mathcal S|,

uniformly in n. By eventual prime coverage, every prime counted in (5.21), 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

by (2.4). Their contribution to the left side of (5.21) 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,

Here we used (\log p)\phi(p/X)\le\|\phi\|_\infty\log X to remove the prime weight from the surviving lower bound in (5.21). This step uses coverage of the full prime set.

Put z=X/(m_Am_D)=R^2/(m_Am_D). Equation (5.5) gives z\ge e^{-o(L)}. Comparing (5.22) with (5.13), and canceling the positive U, gives

Since H\ge .68L, this implies

contradicting z\ge e^{-o(L)}. Thus (5.1) cannot fail along an unbounded sequence, and Proposition 5.1 follows.

6 A finite-field tree comparison

This section isolates the finite-field estimate needed for the auxiliary primes that will be shared by all leaves in Section 7. The field size tends to infinity while the tree depth remains fixed. In particular, every constant allowed to depend on the depth is independent of the field, the frequencies, and the other unit parameters in the tree.

Let q be an odd prime, let U=\F_q^\times, and write e_q(x)=\exp(2\pi i x/q). For a function on \F_q, use the Fourier normalization

For a function on U, its Mellin coefficients are (q-1)^{-1}\sum_{t\in U}f(t)\overline{\chi(t)}, where \chi\in\widehat U. Every multiplicative character, including the principal character, is extended by zero at zero. All L^2 norms in this section use probability measure unless a counting sum is written explicitly. Suppose throughout that g(0)=0 and \E_{x\in\F_q}|g(x)|^2\leq1, and put

The correlation parameter for \overline g is the same, since conjugation replaces (\chi,a) by (\overline\chi,-a). Also \eps_q\leq1 by Cauchy–Schwarz.

6.1 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

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

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 \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 (6.3). Directly from (6.2), on valid points,

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 (6.5) 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

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.

6.2 The cycle reduction and the quartet estimates

We turn to the paired estimate (6.4). 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 \E(W_1\mid\mathcal T)=\E(\mathcal PW_1\mid\mathcal T). Conditional independence of the diagrams, conditional Cauchy–Schwarz, and (6.3) imply

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

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

and

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 (6.7) is determined by the others. We will use the small supremum in (6.8) 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.

6.3 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

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

The map (d,t)\mapsto(x,z) is a bijection between the valid pairs and ordered distinct unit pairs, so

For nonzero d, the Mellin coefficient of h(d,\cdot) is

Indeed, t=x/(x-\sigma d) gives precisely this coefficient. Use the autocorrelation formula (6.10) 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

In particular,

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 (6.9) therefore give the explicit bound

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

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.

6.4 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\F_q,

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 (6.14) equals

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:

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

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

The zero definition of G encodes exactly the excluded values in this formula. Inversion permutes U, so \|G\|_2\leq1 and |\E G|\leq\eps_q by (6.1).

Here is a direct operator bound for (6.15). The affine-action estimate is a concrete counterpart of the convolution bounds developed by Gowers [15], Babai, Nikolov and Pyber [1], and Gill [14, 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(\F_q). The map underlying U_r^*U_s is

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\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

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

Combining with (6.16) 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=\E G, then T1=\overline{m_G}, so the constant part of TG has squared norm |m_G|^4. Therefore

Changing the average to t\in U, and using that \lambda\mapsto\sigma/\lambda permutes U, proves (6.14).

6.5 Quartet coefficient majorants

We now construct the majorants in (6.8). 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 (6.13) bounds the squared coefficient by

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

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 (6.11) and (6.9) give the two assertions of (6.8). 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 (6.2) gives

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 (6.2) is

If the held entry in Figure 1 is the residual A or B, (6.18) therefore has the first of the following forms; if it is p_*, use (6.19) to obtain the second:

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 (6.20) only used its square; the arguments within either pair are determined by their ratio and their difference. Apply (6.13), 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

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 (6.8), 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

Its mean over y\in U is bounded by (6.9).

For the small bound at a fixed \nu, extend the nonnegative y average to all of \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

Each pair uses its own choice of \sigma,g_* in its P. The twists are listed explicitly below; all are zero at zero:

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 (6.14) to the sum over \chi, uniformly in the remaining index and a. The remaining sum is bounded since additive Parseval gives

here \beta may depend on \psi. This bounds (6.22) by O(\eps_q^4+q^{-1/2}). The right friendly case is symmetric.

6.6 The case of two bad choices

It remains to bound (6.22) 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

Consequently, with harmless unit factors and a possible reflection of the frequency,

Let w\geq0 be any weights of mass J and let r_w=\sum_b w(b)^2. Multiplicative orthogonality yields

Indeed, after expansion, a nonzero term requires

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

Subtract this contribution in (6.24) before applying (6.23). Since the masses J of our w_\chi are uniformly bounded, for each \chi this gives

Summing over \chi and using (6.11), we obtain

When both twists in (6.22) 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

Thus its Fourier maximum is O(\eps_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, (6.23) 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 (6.12); 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 (6.26) to one factor and the bounded squared norm to the other. This contributes O(\eps_q^4+q^{-2}).

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

6.7 Completion of the cycle estimate

Return to the projection in (6.6), 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

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=\E_{y\in U}B_\rho(y) and b_0=\E_{y\in U}B_0(y). One character in (6.7) is determined uniquely by the others. Consequently

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 (6.6) proves the quantitative statement of Lemma 6.1, and hence (6.4).

For the later application, the exact transforms g_p in (4.16) satisfy g_p(0)=0 and \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 6.1 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.

7 A positive statistic and its binary-tree transfers

We combine the size and collision estimates with the Fourier supply of Proposition 5.1 to construct a nonnegative statistic. Poisson summation will turn it into an amplitude. The transfers propagate a quantitative lower bound once their diagonals are controlled; Section 9 will bound the same amplitude from above by averaging over arrangements of its prime variables.

The pivot extraction, extension to positive integers, and doubling of the remaining template follow the architecture of Section 4. The exact residue-mask transforms carry no prescribed multiplicative-character phase, so the anchor cancellation is replaced by a common outside list of spectator primes, where Lemma 6.1 compares the paired histories.

All parameters introduced in this section are new; in particular, the letters L,k,m no longer denote parameters from the preceding character arguments.

7.1 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

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

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

Then 0\le\varphi\le1 and \int_{\R}\varphi(t)\,dt=1. For a center c, the log-cell prior is the probability measure on primes proportional to

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

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

The errors are uniform as the centers in our specified ranges tend to infinity. Deleting two prime values does not change these asymptotics.

By (5.1), 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 (5.1). Mertens’ estimates make the two end pieces negligible in this calculation.

Set

The whole chosen block lies below the prime cutoff in (2.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 (4.16), with the normalization

For a favorable prime put

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

For a favorable prime, Parseval and the definition of F_p give

There is an integer center G, whose log-cell support is contained in [G_0,G_0+h], for which

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

Consequently (2.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 (7.2).

Fix this G. Write

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.

7.2 The initial lists and positive statistic

A half-list consists of the following independent positions:

1. (i)

   one giant with prior \mu_G, using the test \widetilde F_p;

2. (ii)

   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. (iii)

   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 (4.16) holds uniformly with a bound tending to zero;

4. (iv)

   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 4.2; 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

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 (4.16) or (2.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,

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

The second definition is made successively for j=k,k-1,\ldots,1. It gives

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 (2.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

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

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 (7.2), Jensen’s inequality on A', and the lower bound in (2.4) give

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.

7.3 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,

We may discard the tuples with repeated prime values, with a negligible error relative to (7.5). 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

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

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

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

Thus the repeated-prime contribution is bounded by

Choosing B_s sufficiently large makes this negligible in (7.5). 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

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.

7.4 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,

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

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

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

on this support, and zero otherwise. The half-list spectator weights use the original outside roles of \mathbf d. Formula (7.8) 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 (7.9). 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

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

Sum and average these terms, imposing all the history restrictions above. In a formula, with state arguments displayed only here,

The bracket is interpreted termwise after expanding the two child histories, and is zero unless (7.10) 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.

7.5 The exact transfer and its diagonal

We verify the relation between the successive expressions (7.8). 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,

Let

with all inherited support conditions; invalid terms are zero. The extracted row has counting squared norm at most 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

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 (7.3) gives p\mu_G(p)=e^{c_g}\varphi(\log p-G) at primes. Extending the nonnegative sum to all positive integers gives

Here the sum over p\in\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 (7.10). It is one-to-one, with p still any positive integer in its cell. Equations (7.1) and (7.7) show

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, (7.10) gives

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 (7.12), 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

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

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

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, (7.7) allows us to extract C_He^{-T_H}, leaving e^{T_H}/H=O_k(1). Normalize the external integer measure as

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

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.

7.6 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. (a)

   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. (b)

   In the diagonal environment for step j, l=j-1. The current + giant p has the external measure (7.16). All other current slots, including the type-j vector \mathbf u, have their original actual prime priors. Set \mathcal G equal to (7.14) 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 (7.11). 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.

8 Arithmetic comparison of the histories

We prove Proposition 7.1. Throughout this section all the constants in the construction and the depth k are fixed, and then L tends to infinity. The notation, priors, templates, and support conventions are those of Section 7. At comparison level l put r=2^l. We treat both the final environment and the diagonal environment of Proposition 7.1; in the latter the positive giant is the external integer variable. All estimates below are uniform in the assignments being compared and in the permitted frequency histories.

The arithmetic reduction first integrates the top giants at the regular and internal small primes. After resolving the resulting internal-prime conditions, we replace the bulk primes by real log coordinates and independent unit residues, keeping the real weights and frequency tests. The paired estimate (7.18) then uses signed spectator correlations. For the norm estimate (7.17), we may take absolute values termwise, but must retain frequency divisibility to control the sum over histories.

8.1 Histories, supports, and real-variable weights

Expand the two amplitudes in a comparison into their frequency histories. For the norm estimate (7.17), 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 (7.11) is then

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

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

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 (7.10).

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

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. 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 (8.1) leaves enough precision for every subsequent test.

2. 2.

   For each b\mid u at a node, require

   N\equiv0\pmod b, \qquad N\not\equiv0\pmod{b^2}. \tag{8.4}

   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. 3.

   Require the top giant units modulo c_{\rm sm}d. At each spectator q\mid d, use the zero convention in (6.2) 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 (8.2), the order of the child giants, and (7.10) identify the spectator factors from a history with the tree value in (6.2). 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

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 (7.10) over \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 (7.9) 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

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 (8.3), use (7.7) at each subtree. Each of |vH_-| and |wH_+|, divided by |s|up, is at most

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.

8.2 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:

For each row, choose the possible exceptional character in Lemma 8.1 before fixing the nongiant priors. If its conductor has a prime factor at least

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 (8.1). 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.

8.3 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

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

Its factors are pairwise coprime, and (8.14) gives \log M_*\leq e^{.012L}. The giant log cells lie in [e^{.049L},e^{.95L}], by their selection from (5.1). Lemma 8.1, 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 (8.8). For an external integer the analogous replacement uses

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

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 (8.8), even summed over all these boxes and classes and multiplied by the pointwise bound, contribute at most

The integer-coordinate errors have the still stronger negative term -G. It follows that the whole giant replacement has uniform error

The Page factors are part of the measures in this argument; they need not be frozen or differentiated.

8.4 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 (7.14) 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 \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

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 (8.3) 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

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 (8.4) 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,

Summing over the O(kr) occurrences shows that the joint measure after integrating these line conditions is dominated by independent representative priors times

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 (8.18), the remaining large pointwise factor is the spectator product. Since there are 2r leaf transforms at each spectator, its logarithm is at most

Every internal b satisfies \log b\asymp_k e^{.01L}. The relative O_k(1/b) losses, multiplied by (8.20), (8.21), and all \exp(O_k(m)) costs, are therefore negligible. We drop all the nonvanishing-modulo-b^2 exclusions henceforth.

8.5 Removing arithmetic coincidences in the line conditions

For the signed comparison (7.18) 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,

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 \Q. We quantify the error in this replacement under (8.20). If a polynomial of total degree D in independent variables is not identically zero and each variable has maximal atom at most \alpha, then

This is a maximal-atom variant of the Schwartz–Zippel argument. Schwartz [33, Lemma 1, p. 702] gives the sharp total-degree estimate for uniform finite sets; Zippel [35, §3.1, Theorem 1] gives related coordinate-degree zero estimates in sparse interpolation. Earlier random-evaluation identity testing appears in DeMillo and Lipton [6]. 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 (8.23).

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, (8.22) 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 (8.21) and all \exp(O_k(m)) factors still gives an error

We now integrate out the giant coordinates modulo each internal b. For (7.18) their contribution is its symbolic rank and feasibility flag times the appropriate scalar in (8.19). 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 (7.17) 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 (8.20). 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 (8.20) and (8.21) show that the resulting error is bounded by (8.24). This step extends the already simplified formula; it does not attempt to use (8.18) with a nonsquarefree c_{\rm sm}. Keep spectator distinctness and any restrictions involving only nonbulk variables.

8.6 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

Use the bulk row of Lemma 8.1 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

Freeze the smooth weight in each box. Equations (8.20) and (8.21) bound its remaining total or pointwise cost by \exp(O_k(m e^{.001L})). The derivative bound gives variation error at most

For the interval errors, even summing over all the boxes and residues in (8.26) gives the upper bound

Both are

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 (8.17), (8.24), and (8.27) 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.

8.7 The signed comparison

We prove (7.18). 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 (8.5). In particular the support descent, (8.18), 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 6.1 are units at q, and the ancestor and child relations are those of (6.2). The selected spectator primes satisfy (6.1) uniformly, with a bound tending to zero; their sizes tend to infinity uniformly as well. Therefore (6.4) 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

as required in (7.18).

8.8 The norm comparison and the frequency sums

We finally prove (7.17). Use the nonnegative upper bound described above. At the d coordinates, (6.3) 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 (8.1).

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

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

Substituting the fixed parent product M_+M_- into (8.28) 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,

It follows that the conditional probability at this split is at most

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 (8.30) over internal frequencies. The requisite numerical estimate is

Indeed, write a=du, a'=dv with (u,v)=1, and then discard the coprimality condition. The left side is at most

which proves (8.31). 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)), (8.31) 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 (8.6) and E_0=\Delta_0+\sqrt m yields

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 (8.20), 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

This is (7.17), and completes the proof of Proposition 7.1.

9 Completion of the proof

We now use Proposition 7.1 to control the diagonals in the transfers and then symmetrize the final amplitude. All parameters, priors, and zero conventions are those of Section 7. In particular, the constants denoted by C in costs Crm are independent of the depth k and of the large gap constants. The limits are taken with all these constants and k fixed, and then L\to\infty.

9.1 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 (7.18). 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

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 (9.1) for l\ge2, write a_i for the number of leaves on either side of the ith 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

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,

The factorial inequality follows by bounding one multinomial coefficient by the sum of all multinomial coefficients with a parts. Consequently

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},

9.2 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 (7.12). 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 (7.14). For either retained square, extract the point probability of the other ordered tuple. On this support it is at most

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 (7.7), 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 (7.17), followed by (9.1), bounds the bad part by

Since m/L\le z, we have L^{-r_jm}(m!)^{r_j}\le\exp(r_jm\log z). We obtain

For every other matching, (7.18) 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,

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,

We specify the parameter order and the reserve in the iteration. The constant B_s has already been chosen sufficiently large for (7.6), whose constant B_* is independent of the later gaps and of k. Write

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,

Choose B_z\ge9 and then choose B_D so large that

where C dominates the uniform constant in (9.4). These are fixed constants, chosen before k.

Indeed, substitution from (7.1) shows that the exponent of the first term in (9.4), divided by r_jm, is

Hence, for every sufficiently large fixed k and then sufficiently large L, uniformly for 1\le j\le k,

The precise choice of k will be made below. We require already that it be large enough that, using m=k^4L+O(1),

for all sufficiently large L.

The transfer identity underlying (7.12) gives

If |\eta_{j-1}|\ge\exp(-Br_jm), then (9.8) and (9.9) imply \mathcal D_j\le\tfrac12 e^{-c_g}|\eta_{j-1}|^2. Therefore

Starting with (7.6), induction proves simultaneously this estimate and the sharper bound

For the induction, the sharper bound at j-1 supplies the coarse hypothesis needed for (9.10); that inequality then gives the displayed sharper bound at j. Its final inequality follows from (9.5) and (9.9). 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.

9.3 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

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

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=(\Z/C\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

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

for sufficiently large L, so the giant row of (8.8) applies with modulus C. With the positive constant c from that estimate, put

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,

As in (8.8), the exceptional term is omitted if it is absent or its conductor does not divide C. When it is present,

This pointwise inequality suffices even if the exceptional character correlates with F.

Multiply (9.15) by F(a), sum over a\in U_C, and divide by Z_G. Since F\ge0, the exact sum in (9.14) both bounds the main term and sums the absolute progression errors. It follows that

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 (9.12).

9.4 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

where A_k^\pi has its bulk values placed according to \pi. Changing variables separately for each permutation in (7.8) yields

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 (9.12) give

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 (7.17). Its fraction among all pairs is bounded by (9.2). Each remaining pair satisfies (7.18); that estimate is uniform, so averaging these pairs preserves its bound. Consequently

For completeness, the sums in (7.1) satisfy

They give, in particular, the convenient upper bound

Since \Delta_0/m=B_s+8\log z, the logarithm of the first term on the right of (9.19), divided by rm, is at most

All constants here have already been fixed. Now choose k sufficiently large, retaining (9.9), that the expression in (9.21) 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 (9.19) 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,

This contradicts (9.11), which gives |\eta_k|^2\ge\exp(-2Brm). The assumed decomposition is therefore impossible: no two infinite subsets of \N_0 have a sumset whose symmetric difference with the positive primes is finite. This proves Theorem 2.3.