Ordinary two-point correlations of multiplicative functions

Proof. Under the law u(q)/(qS), primes in Q are independently included with probabilities 4/(p+4). Equation (2.2) and partial summation give

for large L. Markov’s inequality therefore excludes \log q>98L with probability at most 4/98, and excludes \omega(q)>100\log L with probability at most 4/100. Every remaining q, together with every d\in\mathcal D, satisfies \log(dq)\le100L by (2.3), and so lies in one of the intervals (2.5). Their probability exceeds 1/2. Summing the independent harmonic weights of d, whose total is V_*, proves the lower bound. Dropping both restrictions proves the upper bound.□

Proof. We use Braverman’s bounded-independence theorem [Bra10, Corollary 2]: for a fixed depth d_0, every t-wise uniform distribution on Boolean bits fools circuits of size m to error \varepsilon when t\ge(\log(m/\varepsilon))^{C(d_0)}, with a suitable constant depending only on the depth. Being t-wise uniform means that every set of at most t bits has exactly the uniform joint distribution. We first encode the residue tests by bits, then correct the small failure of exact independence in the integer average.

Under the integer-residue law, R_s denotes the residue of the uniformly chosen origin modulo s; under \mu it is the independent uniform coordinate. In both cases represent R_s by an integer in \{0,\ldots,s-1\}. Put B=\lceil L^{15}\rceil. Independently at each modulus s, adjoin a uniform random variable U_s\in[0,1), independent also of the origin, and take the first B binary digits of

Under \mu, all these bits are independent and unbiased. Decode R_s from its bits whenever their dyadic interval lies inside one interval [r/s,(r+1)/s); on ambiguous intervals make any fixed choice. Conditional on any value of R_s, the probability of a decoding error is at most 2s2^{-B}, since only the two boundary cells can cause an error. This bound holds under either origin law. Therefore the probability of any error is at most

for large L. Correct decoding of one coordinate makes all its translated equality tests correct simultaneously.

A decoded equality is a Boolean function of B bits. Its truth-table disjunctive normal form has at most 2^B conjunctions, each containing at most B literals. Substituting these forms into the original circuit gives depth at most 22 and size at most \exp(L^{17}) for large L.

Fix any set of at most t encoded bits. It involves at most t residue coordinates, whose moduli are pairwise coprime. Their product D satisfies D\le l e^{tL}. If N=|I|, each residue modulo D occurs either \lfloor N/D\rfloor or \lceil N/D\rceil times in I. Thus its distribution has total variation distance at most D/N from uniform. Here total variation is one half of the \ell^1 distance between probability masses. Adding independent jitters and projecting to the selected bits cannot increase this distance. Their marginal consequently differs from uniform by at most

for sufficiently large L. The only use of l is as one modulus coprime to the selected primes, so repeated prime factors in l cause no change.

There are at most n_{\mathrm{bit}}\le e^{2L} bits in all. Let f be the density of their integer-origin law relative to uniform measure on this finite Boolean cube. For a set S of bit indices, let \chi_S be the product of the signs (-1)^{x_i} over i\in S, and write \widehat f(S)=\E_{\mathrm{unif}}f\chi_S. By (3.3),

Set t=\lceil L^{C_1}\rceil. The total absolute value of these coefficients is bounded by

provided A>C_1+20 and L is large.

The estimate (3.4) allows a correction that preserves nonnegativity, even where f vanishes. This is a direct Fourier form of the almost-to-exact independence argument of Alon, Goldreich, and Mansour [AGM03, Theorem 2.1 and Section 3.1]. We give the calculation with the error budget needed here. Put a=e^{-L^{11}} and define

Since |H|\le q\le a, the function g is nonnegative. Its integral is one, and every nonconstant Fourier coefficient of order at most t vanishes. Fourier inversion on each marginal shows that the law with density g is exactly t-wise uniform. Moreover,

Choose the absolute constant C_1 large enough for Braverman’s theorem at depth 22, size e^{L^{17}}, and error e^{-L^{11}}. Then choose A>C_1+20. Applying Braverman’s theorem to g gives error at most a=e^{-L^{11}}. Under either the integer-residue or product-residue law, the original and encoded tests can disagree only on the decoding event. The total comparison error is therefore at most

for sufficiently large L. This proves (3.1). All choices are absolute; the threshold may depend on the fixed modulus l.□

Proof. Apply (3.1) term by term and sum |c_\alpha|e^{-L^{10}}. This argument preserves the signs of the coefficients until after taking each expectation.□

Proof. Expand by exact active sets of size at most m_Q, with scalar coefficient 5^{|Q_a|}. The total coefficient sum is \exp(O(L\log L)), so Remark 3.2 applies. The product-law expectation is at most \E w=S, by independence of the prime coordinates. Finally S\ge1. The bound is uniform in the offset, and summing it proves the last assertion.□

Proof. Put y=\exp(L^{0.99}). We need upper bounds for the number of integers in [D,2D) avoiding every prime at most y, and for the number of triples in [D,2D)^3 for which all four forms

avoid those primes. The last form is positive throughout this integer box. In the first case put m=1, and in the second put m=4. For each prime p, the proportion \nu_m(p) of residue vectors where at least one form vanishes satisfies

For the four forms, every pair of defining hyperplanes is independent over every prime field, including the field with two elements. Inclusion and exclusion of pairs proves (4.3). Moreover \nu_m(p)<1 for every p: the residue 1 in the first case and the vector (1,1,1) in the second avoid all the forms.

For completeness, a finite inclusion–exclusion argument suffices here. Let r_0=2\lceil500\log L\rceil and truncate inclusion–exclusion of the bad-prime events at this even order. This gives an upper bound for the proportion avoiding all the events. For any selected prime set of product r, the Chinese remainder theorem gives residue density \prod_{p\mid r}\nu_m(p). Its normalized count in the interval or box differs from this density by O(r/D) when r\le D. Indeed, each residue coordinate occurs D/r+O(1) times; summing the product of these counts over at most r or r^3 residue vectors proves the assertion. There are at most (r_0+1)(1+\pi(y))^{r_0} terms, each with r\le y^{r_0}. The total boundary error is therefore at most

which is smaller than every fixed negative power of L, by the lower bound on D.

In the independent residue model the difference between the even truncated sum and the full product is at most the next elementary symmetric sum. Partial summation of the prime number theorem and (4.3) give

Thus that difference is at most

The full product satisfies

the finitely many small primes contribute a positive constant, and the remaining factors follow by taking logarithms in (4.3). Together with (4.4), this proves the respective counts O(DL^{-0.99}) and O(D^3L^{-3.96}).

The first count bounds \sum_{z\in\mathcal Z}1/z and hence \|B\|_\infty. Orthogonality expresses the fourth moment as the sum of (z_1z_2z_3z_4)^{-1} over z_1+z_2=z_3+z_4 with all four variables in \mathcal Z. The factor h does not change this equality. Each triple determines z_4, and each weight is at most D^{-4}. The second count proves the fourth moment bound.□

Proof. For each integer 1\le v\le Y define

We first claim that, uniformly in \theta,

For integer D, every x\in(v,v+1) has precisely v+1,\ldots,v+D as the integers in [x,x+D]. Apply Theorem 4.3 with H=D and Z=\lfloor Y\rfloor+1, discarding the unused initial unit interval. The restriction to the residue class follows from

Its coefficients have total absolute value one. After the unimodular factor arising from n=v+m is removed, this applies the same theorem to the frequencies \theta+a/l. In particular, no assumption that b_0 is coprime to l is needed. The scale hypotheses imply 10\le D\le Z and

which proves (4.6).

Average the sum on the left of (4.5), before taking its absolute value, over translations by m=1,\ldots,D. Each translation changes at most 2m prefix terms for each z. By Lemma 4.2, the normalized endpoint error is at most

Let B be the polynomial in Lemma 4.2. Orthogonality now expresses the translated average as

Indeed, expanding the integral imposes a=m+hz. Since 1\le m\le D and D\le z<2D, this value of a lies in the full range used to define G_v.

On the set where |B|\le L^{-1.05}, Parseval and Cauchy–Schwarz give

Its contribution to (4.7) is therefore O_h(L^{-1.05}). The complementary set, denoted by \mathcal E, satisfies

On this set use \|B\|_\infty\ll L^{-0.99}, |G_v|\le(2h+1)D, and (4.6). Its contribution is at most

Finally D/Y\le\exp(2L-L^A/2) is negligible. This proves (4.5).□

Proof of Remark 4.1. The full-divisibility contribution is (2.7). For every other term in the expansion of (2.6), let I\subset\{1,\ldots,J\} be the nonempty set of prime supplies whose factors have been replaced by -1/p. Put

For fixed q,d',j, substitute n=qd'v and put Y=T_j/(qd'). After extracting the sign (-1)^{|I|} and the factor u(q)/(qd'), the remaining expression is

where z ranges over the products from the supplies indexed by I that also satisfy the bin condition. This substitution is valid in every residue class, since qd' is invertible modulo l.

The allowed z lie in an interval of logarithmic width \eta<\log2. Split them by residue modulo l and by the at most two dyadic intervals [D,2D) that meet this interval. In each resulting piece the residue bz\pmod l is constant. Unique prime factorization and the disjointness of the supplies show that each integer z occurs at most once. Since I is nonempty, all its prime factors are at least H_0=\exp(L^{0.995}), and

Furthermore, if the piece is nonempty, its bin condition implies Y>Xe^{-\eta}z, so \log Y\ge L^A/2 for large L. Lemma 4.4 therefore bounds (4.8) by O_{h,l}(L^{-21/20}).

For each fixed I and bin, the sum of the extraction weights is at most

where the last inequality uses V_i>1. There are O(L/\eta) bins and fewer than 2^J nonempty sets I. Hence the total contribution of the partial centering terms is

Together with the full divisibility term this proves (4.1).□

Proof. Conditionally on the primes of Q dividing n, choose q_1,q_2 independently with probabilities

Each available prime is selected with probability 4/5. Under the combined tilted law let Z=\log(q_1/q_2). A prime r contributes +\log r or -\log r with probability 4/[5(r+4)] each, and contributes zero otherwise. The contributions are independent, so its characteristic function, with angular frequency t, is

Every factor is nonnegative: even at r=2 it is at least 7/15. The inequality 1-x\le e^{-x} therefore gives

Replacing r+4 by r changes the exponent by O(1), uniformly in t. For |t|\le2, partial summation of the fixed-modulus prime number theorem in (2.2) gives

For completeness, in the partial summation the derivative of (1-\cos(t\log x))/(x\log x) is O(1/(x^2\log x)) uniformly for |t|\le2. Its product with the prime-number-theorem error is integrable on [2,\infty). Deleting the finitely many prime divisors of lh also costs O_{h,l}(1). To verify the second equality, set u=|t|y. The integral over u\le1 is bounded, and integration by parts bounds \int_1^U\cos u\,du/u uniformly in U\ge1. The lower endpoint |t|\log2 stays bounded. These observations also cover t=0. It follows that

Conditionally on n, the probability that both divisors lie in the jth bin is \rho_j(n,d)^2. Divisors in the same bin have |Z|\le\eta\le1. Consequently the left side of (4.10) is at most \Pbb^*(|Z|\le1). The function \kappa(x)=(\sin x/x)^2, with \kappa(0)=1, satisfies

Taking expectations, using (4.13), and integrating gives

The common translation \log d of the two padding logarithms disappeared from Z, which proves the asserted uniformity.□

Proof. We first bound the deletion costs in the auxiliary product model, after dropping the Liouville factors and the progression indicator, and replacing the absolute centered product by

At the end of the proof we transfer precisely these nonnegative costs to integer averages by Lemma 3.1. No assertion about untruncated integer moments of w is needed.

Either endpoint. For a fixed numerical pair (d,q), translation by hqd preserves the auxiliary product law. Moreover divisibility by q and by each prime of d is unchanged by this translation. Thus an upper-endpoint failure has the same bound as a lower-endpoint failure. This argument does not assert that the full weight w is constant across an edge. It suffices to analyze one endpoint and multiply the resulting bound by 2.

The two padding cuts. The P coordinates are independent of the Q coordinates and \E a_d^+=2^J/d. Enlarge the eligible padding divisors to all divisors in their respective bins. The total costs of the first two cuts, at one endpoint and summed over bins, are at most

Indeed the sum of padding weights in a bin is w(n)\rho_j(n,d), and \sum_j\rho_j\le1. Under the tilted law the mean of \omega_Q is at most 4\log L for large L. Independence and exponential Markov therefore give

Also x\1_{x>K/L}\le(L/K)x^2 for x\ge0. Applying Lemma 4.5 bounds the second term in braces by O_{h,l}(K^{-1}). Since \sum_d1/d=V_*, this gives the first two terms of (4.17).

The P-degree cut. For fixed d, tilt the P coordinates by a_d^+ divided by its mean 2^J/d. Primes outside d retain their independent Bernoulli laws, whereas the selected J primes contribute at most J to the count. As \sum_{p\in P}1/p=\sum_iV_i\le2WJ, exponential Markov gives

The padding coordinates remain independent. Summing their weights u(q)/q over all eligible pairs and bins is at most S for each d. Thus this deletion costs at most 2^JSV_*e^{-2WJ} per endpoint.

The rare sites. For one bin, the entire absolute row weight is bounded by

To see this, sum all padding divisors for each d, and then sum each prime slot separately. Independence gives

Here C,C' are absolute: the first product is polynomial in L by partial summation, and J\log(18W^2)\le\delta\log L\,\log(18W^2)/(6W) is bounded by an absolute multiple of \log L for W\ge10. Cauchy–Schwarz and (4.14) therefore bound a single-bin rare-site cost by

There are O(L/\eta) bins, and SV_*\ge1. Their total contribution is at most \exp(-L^{0.9}) for sufficiently large L.

Transfer to integer averages. We now justify applying Lemma 3.1 to the preceding costs. This also ensures that no independence claim is being made for arbitrary integer functions. Use a union bound for the two endpoints, and for the following four failures at either endpoint:

This is the same deletion event, with the padding-mass failure tested only after the low-Q cut passes. In the product model its cost is bounded by the estimates already proved, since dropping the extra low-Q condition can only increase a nonnegative cost.

Fix a numerical j,d,q and expand a_d^+ as a sum of divisibility indicators. There are 2^J terms, with coefficients at most 1. The factor \1_{q\mid n} is a conjunction of its prime divisibilities. Each degree failure is an OR over subsets of primes of the required cardinality, testing that all their residues vanish. Since there are at most e^L available primes, the low-Q degree test has size \exp(O(L\log L)). The P threshold has the same bound, using 6WJ\le\delta\log L.

For the padding-mass failure with low Q degree, list all possible exact sets of at most 400\log L primes of Q dividing the site. For each set, a conjunction asserts both the indicated presences and all other absences. On that state, both w and \rho_j are fixed numbers; retain the state precisely when \rho_j>K/L. There are \exp(O(L\log L)) such states, each specified by at most e^L tests. The remaining event \mathcal B_j has the circuit representation assumed in the statement. Intersecting any of these events with the indicated prime divisibilities has depth at most 10 and size at most \exp(L^4) for large L. Translation to an upper endpoint changes only the tested residues, not these bounds.

Finally, the numerical pairs satisfy dq\le\exp(100L+\eta). The disjoint prime supports of d and q determine both from their product, so there are \exp(O(L)) eligible pairs in all bins. Also u(q)\le4^{100\log L}, and the expansion of a_d^+ has total coefficient mass at most 2^J. The total absolute coefficients in all these comparisons are therefore at most \exp(O(L^4)); even the looser bound permits all listed state expansions. The averaging interval has length \lfloor T_j\rfloor\ge\exp(\tfrac12L^A). Lemma 3.1 makes the aggregate comparison error at most \exp(-L^9). Replacing the integer-length normalization by T_j costs at most T_j^{-1}\exp(O(L^4)), which is smaller still. Together with the product estimates, these errors prove (4.17).□

Proof. There are O(R\log L) slots, since each tuple has J=O(\log L) factors and every eligible padding has at most 100\log L factors. A partition of N slots has at most N^N descriptions. Signs, factor counts and all recorded indices therefore cost \exp(O(R\log^2L)). Each numerical class has reciprocal mass O(\log L), by the prime harmonic bounds, and Lu(q_i)\le L^{1+100\log4}. This proves the first assertion. Dropping bin or numerical distinctness restrictions enlarges these positive sums. If distinct abstract classes are assigned the same numerical prime in such an enlargement, they retain their separate reciprocal factors.

For the second assertion the coefficient is invertible modulo p, so z lies in one residue class. Enlarge from primes to integers and compare the reciprocal sum along that progression with its integral:

Fix the nonselected variables and sum the selected ones in reverse order. Every remaining earlier relation is independent of the variable currently being summed. Its own coefficient test is retained; if this test fails, the admissible inner sum is zero. The displayed bound is uniform in the remaining variables, and backward induction proves multiplication of the savings. After these sums, the other prime variables are bounded by the first assertion.□

Proof. We may count all forward prohibited positive words, without requiring minimality. For a fixed numerical word, positivity either gives inconsistent residue conditions or fixes one residue at each distinct prime in its steps. Its probability is accordingly zero or the product of their reciprocals.

At the last transition choose a column whose prime changes. Its last prime z occurs nowhere earlier, by the interval condition. In (5.1), the contribution involving z is exactly the last step. Thus its coefficient is \varepsilon_m hq_m d_m/z. The controlling prime p is absent from d_m, from h and from every padding, so this coefficient is a unit modulo p. It is independent of z. Fixing the equality pattern, padding and other tuple values, Remark 5.2 supplies one saving (1+L)/H_0. The remaining count, summed over 3\le m\le s, is at most

This proves the probability bound.

Each eligible numerical pair satisfies dq\le\exp(100L+1). The disjoint prime supports recover d and q uniquely from their product. Thus the number of numerical words of length at most s is \exp(O(sL)). Preselect those satisfying the numerical prohibition and minimality conditions. Positivity of one such word is a conjunction of O(s\log L) residue equalities, one per prime occurrence. Taking their disjunction gives the stated depth and size bounds. Translation merely shifts the same residue coordinates. This verifies all the hypotheses on the deleted events in Remark 4.6.□

Proof. For a uniform residue Z modulo p, a fixed residue a, and any function F of that coordinate,

Apply this identity successively to the independent singleton coordinates. At a nonsingleton, incompatible lit tests give zero; otherwise they force one residue and supply 1/p, while every unlit choice supplies the scalar -1/p. These operations produce exactly the factor b_{\mathcal L} and the mixed difference, up to the signs of the unlit scalars. The factor R is unchanged in every operation. Taking the absolute value after these integrations proves the bound. The final assertion follows because G takes values in \{0,1\}.□

Proof. If a nonsingleton has a lit occurrence, each of its unlit occurrences supplies an extra reciprocal beyond its basic 1/p. If all its m\ge2 occurrences are unlit, it supplies p^{-m} and hence at least m/2 extra reciprocal powers beyond the basic one. Thus at least U/2 extra powers remain, all at primes at least H_0. The total is at most

□

Proof. Let E(c,y) denote the divisibility event in the statement, and let y' be an independent copy of y, independent also of c. Cauchy–Schwarz, applied to the conditional probability with c fixed, gives

The two copies have the same controlling primes c_i, so subtraction removes the entire vector f(c).

Write v=B(y-y'). For a subset Z\subseteq\{1,\ldots,r\} of size a, the rows of B indexed by Z have rank a. Choose an invertible a-column minor in those rows. Conditional on y' and on the coordinates of y outside that minor, the equations v_i=0 for i\in Z determine at most one vector of values for its a remaining coordinates. Independence and the atom bound imply

This includes a=0, with the empty condition having probability one.

Now fix y,y'. A nonzero integer of absolute value at most M has at most d_M distinct prime divisors. Each nonzero coordinate v_i therefore satisfies c_i\mid v_i with conditional probability at most d_M\alpha. The controls are independent of each other and of v. If the exact zero set of v is Z, their joint conditional probability is thus at most (d_M\alpha)^{r-|Z|}. Using (6.2) and summing over the possible exact zero sets gives

Taking the square root proves (6.1).□

Proof. Use the positive reciprocal majorant and enumeration of Remark 5.2. Thus we may discard the denominators and cutoffs, retain one reciprocal for every distinct prime label, and include the factors Lu(q_a) and 2^{S_1} in the crude count. We retain the lit-consistency conditions. The total unrestricted count, including external dimension factors, is \exp(O(L\log^2L)).

Fix a column, its equality pattern, and the other-column and padding data. Choose r jointly independent pairs, and denote their controlling labels by z_1,\ldots,z_r and their difference vectors by w_1,\ldots,w_r. The controlling labels are distinct. Modulo C=\operatorname{span}(e_{z_1},\ldots,e_{z_r}), the images of the w_i remain independent: a dependence would express a nontrivial linear combination of the w_i as a combination of the e_{z_i}, contrary to joint independence. Therefore the row matrix of the w_i, after deleting all controlling columns, has rank r. Choose an invertible r-column minor B_0 of that matrix.

The entries of the entire row matrix, and hence the choice of a minor by any fixed deterministic rule, are independent of all the numerical primes in column \nu. Fix the prime variables in that column outside the controlling coordinates and the minor. Write c_i=p_{z_i} for the controls and y for the vector of primes in the minor. The selected lit-consistency conditions become

with fixed integer matrices B_0,A_0 and a fixed integer vector d_0. No invertibility assertion modulo c_i is being made.

Enlarge the positive sum by dropping numerical distinctness among abstract labels, as well as bin and closure restrictions. Continue to attach one factor 1/p to each abstract label: if two coordinates now take the same prime, their product weight is 1/p^2. The enlarged reciprocal sum is consequently a product sum. Its normalized coordinates have independent law

This independence allows numerical coincidences. In particular, after subtraction in Remark 6.1, the controls remain independent of B_0(y-y'), even on a sample space that permits such coincidences.

We check the size hypothesis after these enlargements. The fixed padding values came from eligible steps, so q_a\le e^{100L+1}. The product of the primes in the other columns is at most e^{2L} by the geometric spacing of their bands. Hence

Each row of the difference matrix has sum of absolute coefficients at most 2kh e^{102L+1}. Since every prime in the resampled column is at most e^L, we obtain

For fixed h and sufficiently large L, the constant in this last exponent is absolute. In Remark 6.1 we may therefore take d_M=O(L), \alpha=(V_\nu H_0)^{-1}, and f(c)=A_0c+d_0. The probability of (6.5) is at most

Multiplying by the unrestricted harmonic masses restores the unnormalized reciprocal sum with this same relative saving. The estimate is uniform in every fixed outside variable, so these variables may now be summed.

The column, selected pairs and selected minor have at most J(2k)^{O(r)} descriptions. Their cost is absorbed in \exp(O(r\log L)). Together with the crude enumeration, the total is bounded by

Since \log H_0=L^{199/200} and r=L^{1/50}+O(1), its negative term is (\tfrac12+o(1))L^{203/200} and dominates both positive terms. This proves the lemma.□

Proof. For the fixed numerical word, let \mathscr W be the finite set of all possible witness tests at its departure sites. Write I_w for the indicator that the preselected numerical word w is positive at its assigned departure. Then

A repeated test in this product is harmless because its factors take values in \{0,1\}. Expand this finite product algebraically and apply the mixed difference in \mathcal U. If the union of the prime supports of a subfamily \mathscr A\subseteq\mathscr W omits a prime p\in\mathcal U, then \prod_{w\in\mathscr A}I_w is independent of the p coordinate. Its full mixed difference is therefore zero. Consequently \Delta G\ne0 implies that some subfamily whose supports cover \mathcal U has a nonzero mixed difference. Its intersection indicator is then one in at least one hybrid. All witnesses in that subfamily are positive in this single configuration.

Choose an inclusion-minimal subfamily covering \mathcal U there. Each member contains a prime of \mathcal U occurring in no other member, since otherwise that member could be removed. A witness has at most sJ distinct P labels, so this subfamily has at least S_1/(sJ) members. For sufficiently large L,

Keep any T members and one private prime in each. Their private primes remain private in the selected subfamily. Finally,

The algebraic expansion above has been used only to deduce existence. No bound is obtained by summing the absolute values of its terms, and no enumeration of all its subfamilies is charged.□

Proof. Consecutive tuples differ, and each label occupies an interval of step indices. Thus some label z enters for the first time on the last step. Let c be the first-step label controlling the prohibited suffix of the word. Since c is absent from the last tuple and divides neither h nor a padding factor, c\nmid E_m. The contribution of z to the prohibited suffix is exactly E_m, so z is active. The same argument shows that every label used only on the last step is active.

Now suppose that y occurs before the last step. Restricting attention to steps 1,\ldots,m-1, its occurrences form a nonempty interval [a,b], where b<m; y may also occur on step m. If E_a+\cdots+E_b is nonzero modulo z, then (6.7) holds at i=m. Otherwise

Every step before the last is nonzero modulo z, so b>a. Reverse the contiguous subword E_a,\ldots,E_m, negating all its steps. Its first step contains z, its last does not, and its suffix consisting of the reversed steps E_b,\ldots,E_a has sum divisible by z. This suffix starts strictly after the first step because b<m, and strictly before the last step because b>a. The interval appearances and unequal consecutive tuples persist under reversal. The reversed subword is therefore forward prohibited. Minimality forces a=1.

Choose a label z' newly entering on step 2, which is possible because the first two tuples differ. Let b' be the smaller of b and the last index carrying z'. Its contribution to (6.8) is E_2+\cdots+E_{b'}. If that contribution were zero modulo z, then b'>2, since z\nmid E_2. The reversed subword E_m,\ldots,E_2 would then be forward prohibited, with controlling prime z and suffix E_{b'},\ldots,E_2. It is shorter than the original word, contradicting minimality. Hence z' is active through (6.8). Since y occurs on step 1 and z' does not, its contribution before step 2 is E_1\not\equiv0\pmod{z'}. This proves (6.7) with i=2 and z' in place of z.□

Proof. Whenever the integrand is nonzero, Lemma 6.3 supplies T witnesses positive in one common hybrid, with marked private singletons. Order them as w_1,\ldots,w_T by their attachment indices a_1\le\cdots\le a_T on the main word; order ties arbitrarily. Write t(y) for the unique main step carrying a main singleton y. Thus the main position of y has been passed at attachment a exactly when t(y)<a. We will select at least \lfloor T/8\rfloor prime variables and order their relations so that each relation is independent of all later selected variables. In the first two cases we select active labels, which need not be the marked singletons. In the remaining case we select the private marked singletons themselves.

Internal relations. Suppose at least T/8 witnesses have an active label absent from every earlier witness. Choose one such label from each of these witnesses, and record an internal relation establishing its activity. The chosen labels are distinct. Each earlier relation involves only labels in its own witness, so it is independent of every later chosen label, including as a controlling modulus. Sum the chosen prime values in reverse witness order. When one is summed, all earlier relations are independent of that variable, while its own relation has an invertible coefficient. This gives at least \lfloor T/8\rfloor successive reciprocal-prime savings. If instead at least T/8 witnesses have an active label absent from every later witness, apply the same argument with the order reversed.

Comparison relations. Assume neither alternative holds. Apart from fewer than T/4 witnesses, every active label occurs in both an earlier and a later witness. In each remaining witness w_j, its private marked singleton y_j is not active. By Lemma 6.4, choose an active label z_j and a departure within w_j whose prefix has nonzero y_j-contribution modulo z_j.

First consider those j for which t(y_j)\ge a_j. Choose an earlier witness w_h, h<j, containing z_j, and a departure there using z_j. Let \beta_j and \beta_h be the offsets of these selected departures from the respective starts of w_j and w_h. Positivity in the common hybrid gives

The main segment omits y_j because t(y_j)\ge a_j, and w_h omits it by privacy. Its only contribution is therefore through \beta_j, where it has the nonzero prefix contribution given by Lemma 6.4.

For two selected witnesses w_j,w_i with j<i, the private label y_i occurs in neither witness prefix in (6.9). It is also absent from its main segment, since

Thus the comparison belonging to w_j is independent of every later selected variable y_i. This includes its controlling prime: z_j occurs in both w_j and w_h, whereas each selected y_i is private. Eliminating the selected labels in decreasing attachment order is therefore valid. Equal attachment indices cause no difficulty, as the main segment still ends strictly before that index.

For the witnesses with t(y_j)<a_j, choose instead a later witness containing z_j. The comparison uses the main segment starting at a_j and ending just before that later attachment, so it omits y_j. Order this group by decreasing attachment index. A selected label from a smaller attachment has its unique main position still smaller than that attachment, and hence lies before the start of every earlier comparison segment in this order. Privacy removes it from the two witness prefixes as well. The same reverse-elimination argument applies. One of these two groups has at least T/8 witnesses for sufficiently large T: there are more than 3T/4 candidates before dividing them according to whether their main position has passed.

Summing the relations. In all cases, record the chosen relations, their order, their controlling labels, and the nonvanishing coefficient tests. Fix the equality pattern, the numerical padding factors, and all nonselected numerical labels. Every selected congruence is linear in its selected prime x; its coefficient is a unit modulo its controlling prime p. The latter is unselected or belongs to an earlier relation in the chosen order. The reciprocal sum is bounded by

where enlarging from primes to integers only increases the sum. Retain the nonvanishing coefficient condition during each elimination; if it fails for the remaining fixed data, that inner sum is zero. After summing a selected variable, drop its already used relation. The explicit dependencies above ensure that all still retained relations are independent of the variable just eliminated.

It remains to justify the residue cost and the number of records. Bound |\Delta G| by 2^{S_1}, drop denominators and cutoffs from R, and retain its padding divisibilities. The factor b_{\mathcal L} already supplies one reciprocal for every main P label. Each new witness P label and each distinct main or witness Q label has a positivity test in its original residue coordinate, which no hybrid changes. Their joint average supplies one reciprocal per distinct such label. Constraints on overwritten main coordinates may be dropped. In particular no choice of hybrid needs to be counted: these retained residue tests are unchanged throughout the hybrids, and the recorded numerical relations are necessary consequences of positivity in the common one.

The total recorded length is at most 4L. Lemma 5.2 therefore bounds the equality patterns, numerical reciprocal sums before the selected savings, signs, and weights by \exp(O(L\log^2L)). Attachments, marked labels, internal interval endpoints, partner-witness indices, and elimination orders have only polynomially many options per recorded slot, so their inclusion preserves this bound. The factors 2^{S_1} and |\mathcal D|^2M=\exp(O(L)) do so as well. We have proved the bound

Finally, T\log H_0\asymp L^{1/12+199/200}=L^{647/600}. This dominates both L\log^2L and L^{21/20}, proving the assertion.□

Proof. If the interval assertion fails, choose across all columns two consecutive occurrence groups having the shortest gap. Let i be the last position in the first group and i' the first in the next, and let p be their common prime. The prime p is absent from i+1,\ldots,i'-1. Every label in the substring i,\ldots,i'-1 has interval-shaped uses, since otherwise it would give a shorter gap. Positivity at the departures of steps i and i' gives

The length i'-i cannot be two: the latter sum would be one displacement whose tuple and padding both omit p, while p\nmid h. The substring therefore has length at least three. It is a forward prohibited word, with its suffix starting at its second step. Pass to a minimal prohibited contiguous subword, allowing reversal. Positivity survives these operations, and its starting vertex is one of the main vertices. This contradicts \sigma_j=1 there.

For the second assertion a single displacement is nonzero. In any subinterval of length at least two, the first and last tuples differ. Indeed, if they agreed in every column, the interval assertion would make every tuple in that subinterval equal, contrary to the nonbacktracking condition. Choose a first-step prime p absent from the last tuple. If the total displacement were zero, deleting the first step would leave a suffix sum divisible by p. In a two-step subinterval this is impossible, because p does not divide the last displacement. In length at least three it makes the subinterval forward prohibited. Minimal descent gives the same contradiction. A reversed subword may begin at the end of the block; this endpoint is also a main vertex. At the end of the closed word it is its initial vertex, so the survival condition still applies.□

Proof. Fix one realization and one column. Let \mathcal Z be its set of distinct labels and let \mathcal V be the real vector space with basis (e_z)_{z\in\mathcal Z}. If the label at position a is z_a, define its formal departure offsets by

The coefficients t_a do not use the prime values in this column. Choose an inclusion-maximal collection of pairs (e_z,v(i)-v(i')), where i,i' are lit occurrences of z, whose combined vectors are independent. If there are m pairs, their span D_0 has dimension 2m<2r.

Choose a basis of \mathcal V/D_0 from the images of the coordinate vectors. Call the corresponding labels regular and the other labels omitted. There are exactly 2m<2r omitted labels. Write \bar v and \bar e_z for images in the quotient. For a regular label z, all lit starts lie on one affine line parallel to \bar e_z. Otherwise some difference v(i)-v(i') would be outside D_0+\mathbb R e_z; since e_z\notin D_0, adjoining that pair would contradict maximality. The regular directions are nonzero and jointly independent. For each regular label z with a lit occurrence, let

The preceding argument makes this line independent of the choice of i. The lines so defined are distinct, since their directions are independent.

Compress each constant run in each perfect block to one run-entry. By Remark 7.1, a given label occurs in at most one run per block. A regular run of label z has quotient increment

The inequality uses the nonzero-subinterval assertion of Remark 7.1. Cut the runs at omitted entries and at block boundaries. This leaves at most (2r+1)B nonempty regular segments and at most 2rB omitted run-entries. The parameter bounds and (7.2) give

Each regular run of label z starts and ends on \ell_z, and (7.3) says that its endpoints are distinct. A transition from a z-run to a z'-run is therefore a common point of \ell_z and \ell_{z'}. We encode these incidences by a simple bipartite graph: one vertex represents each line used by the regular segments, and one vertex represents each distinct projected transition point. Join a transition point to the two lines of its transition, identifying vertices whenever the same line or point recurs. Include an isolated line vertex if it occurs only in one-run segments. There are at most 2k line vertices and at most 2k point vertices.

This graph is a forest. A simple cycle would pass through distinct line vertices, and thus through distinct independent directions. On each of its lines the two adjacent point vertices are distinct. The displacements around the cycle would consequently give a linear relation among the regular directions with every coefficient nonzero, a contradiction.

A regular segment gives a walk in this forest. It has no immediate reversal: a walk line–point–same line would repeat an adjacent run label, and a walk point–line–same point would contradict (7.3). A walk without immediate reversal in a forest is the unique simple path between its endpoints. Therefore the ordered pair of line endpoints recovers all run labels of the segment. Equal endpoints encode a one-run segment.

Figure 1 illustrates this decoding. The graph records only incidences; the numerical positions of the points will not enter the code.

We describe explicitly a code for the whole column pattern.

1. 1.

   Record imperfect positions, block boundaries, run boundaries, and the omitted or regular status of each run. These are binary data on O(k) positions and have \exp(O(k)) possibilities.

2. 2.

   Record the equality partition among the omitted run-entries. Its cost is at most (2k)^{O(rB)}.

3. 3.

   Give the abstract forest, rooted and ordered in any manner, with its line or point vertex types. The parenthesis traversal of a rooted ordered forest with at most 4k vertices, together with the type bits, has \exp(O(k)) possibilities. The traversal numbers its vertices.

4. 4.

   Give the ordered pair of line-vertex numbers for every regular segment. By the unique-path property this recovers its run sequence. The cost is at most (4k)^{O((2r+1)B)}.

5. 5.

   At every imperfect position, give a representative occurrence of its label. A label already represented in a perfect position points to such a position; otherwise use its first imperfect occurrence. This costs at most (2k)^I.

These data determine a unique equality partition. Omitted labels cannot equal regular labels. Their recorded partition determines all omitted equalities, while the forest vertices determine all regular equalities. The last step supplies every remaining equality. Neither coordinates of transition points nor numerical coefficients are needed in this decoding.

All constants in these code counts are absolute. Their logarithms sum to at most

for an absolute C and sufficiently large absolute L. Here k=\lfloor L\rfloor and both exponents 0.92 and 1/4 are strictly less than one.

The code universe just described depends only on the length and the displayed numerical bounds. Every realizable pattern, whatever the coefficients, has a code in that same universe. For example, choose the first valid code in a fixed ordering; the decoder shows that two different patterns cannot receive the same code. Thus the bound counts the union over all coefficients, not just the patterns at one fixed coefficient choice. Applying this universal bound in each of the J columns proves the last assertion.□

Proof. Let c_i(n,q) denote the ith factor in the product. The definition of \rho_j allows all squarefree padding products in the bin; the extra bound on \omega(q) in \mathcal S_j only reduces their sum. Consequently, at every site n,

Set F_{m+1}(n)=1 and recursively define

Backward induction, using a bound uniform in the starting site at each stage, gives F_i(n)\le K^{m-i+1}. In particular F_1(n_1)\le K^m. The shifts caused by earlier padding choices therefore introduce no additional factor.□

Proof of Remark 5.4. First work in the product residue law. The contributions with U>L^{1/50}, with a high-rank column, or with S_1>L^{1/4} are o(1) in total by Remarks 5.6, 6.2 and 6.5, including the external dimension factors of the trace expansion. We sum the remaining contributions using Remark 5.5.

By Remark 7.2, the combined column patterns lie in a single family of at most \exp(CJk) possibilities, independently of all padding choices. Fix one such pattern, its numerical column labels, the signs, and the lit or unlit designations. Replace |\Delta G| by 2^{S_1} and retain just one reciprocal per distinct column prime in b_{\mathcal L}. Every nonsingleton provides at least one such reciprocal: either it has a lit occurrence, or all of its at least two occurrences are unlit. Dropping the other reciprocals and lit consistency enlarges the nonnegative majorant.

In R, drop closure, progression and block restrictions, arrival cuts, and the low-Q cuts. Retain the padding divisibilities, bin conditions, departure weights, and departure \rho_j cuts. The closed-word identity for its denominators was established before this enlargement. Conditional on the non-P environment, Remark 7.3 with m=2k bounds the full padding sum by K^{2k}. All its factors are unchanged by the P-coordinate overwrites, and the bound is uniform in the environment. Taking its expectation preserves that bound.

Let m_i be the number of distinct labels in column i, and put m_P=\sum_i m_i. Among the 2kJ column occurrences, exactly S_1 belong to singleton labels and every other label occurs at least twice. Hence

After the uniform padding bound, the numerical label sum is at most

Here dropping distinctness among prime classes is simply an enlargement of a positive reciprocal sum. The classes are already identified by their first occurrences, so no further permutation factor is introduced.

There are at most 2^{2k} sign choices and 2^{2kJ} lit or unlit designations. The mixed difference contributes 2^{S_1}. The external indices cost at most |\mathcal D|^2M\le\exp(108L) for large L, since |\mathcal D|\le e^{2L} and M=\lceil e^{103L}\rceil. Combining these bounds with the forest count and (7.6) gives

where C_4 is absolute. The factor \exp(108L) is absorbed here using J\ge1 and k\ge L/2.

For every fixed W, once L is sufficiently large, (2W)^{L^{1/4}/2}\le e^k. This changes the required lower threshold on L, but not the absolute constant in the exponential. An absolute choice of C_2 therefore bounds the right-hand side of (7.7) by

Finally, the finite-law comparison for the trace expansion changes the expectation by at most \exp(-L^9). Increasing the same absolute constant C_2 absorbs this error as well and proves the integer-interval assertion of Remark 5.4. In particular, C_2 is fixed before W is selected; dependence on the fixed parameters is confined to how large X must be.□

Proof. Put m=\max\{a,b,\rho(\mathscr B)\}. If m=0, all B_i vanish. Otherwise set t=(2m)^{-1}. For real |u|\le t, the operators I-u\mathscr B and I+uB_i are invertible. Define

Each summand is self-adjoint, since B_i commutes with its own resolvent. If F(u)v=0, set z_i=(I+uB_i)^{-1}v. Then

A nonzero v would give a nonzero z, contradicting the invertibility of I-u\mathscr B. Hence F(u) is invertible throughout [-t,t]. It is positive definite there by continuity, because F(0)=I.

The resolvent identity gives

Since |u|\|B_i\|\le1/2, the inverses in the last expression are positive and bounded above by 2I. For v=Pv,

Positivity of F(t) and F(-t) therefore yields

Taking the supremum over unit vectors in the range of P proves (8.1). No step commutes two distinct B_i.□

Proof. For each of the two edge orientations, the weighted absolute row sum at n is at most

Indeed the sum without the last indicator is at most L\rho_j(n,d). For an incoming edge, q divides one endpoint if and only if it divides the other. All the other edge restrictions can be discarded in this nonnegative bound. Consequently

The weighted Schur inequality for a real symmetric matrix B follows by applying

to its quadratic form. Apply it to A_d on each level set of a_d; these level sets are invariant under A_d. The resulting bound is

In particular, a_d(n)\le1 proves (8.2).

At a site retained by E, the total P-degree is at most 6WJ. Since V_i\le2W, the arithmetic-geometric mean inequality gives

Sum (8.5) over d. This proves (8.3) without requiring E to commute with A_d.□

Proof. For every finite matrix, \rho(H)^{2k}\le\|H^k\|_{\mathrm{HS}}^2. Thus Remark 5.4 and Markov’s inequality show that

except on a fraction at most e^{-2k} of the origins. On each remaining block apply Remark 8.1 with

For J\ge1 and W\ge10, the choice

gives (8.6). In particular, C_3 is independent of W,h,l.□

Proof. Write T=T_j and N=\lfloor T\rfloor, and average over blocks I_t=\{t+1,\ldots,t+M\}, 0\le t<N. For large X, N\ge\exp(L^A/2), so the interval of origins is admissible in Remarks 3.1 and 5.4. On each block put

We first check the averaged norm needed for testing:

For each of the M block positions, Remark 3.3 applied to the corresponding translated interval of N origins bounds the average truncated weight by 2S. Summing proves (8.9). This uses the truncated comparison already established, without an untruncated integer moment of w.

On blocks satisfying (8.6), the averaged absolute quadratic form is at most 2MSK(C_3\sqrt W)^J. On every block, including exceptional ones, (8.4) gives the deterministic bound

Here we bound the form by its entrywise absolute value, use |g_t(n)|\le\sqrt{w(n)}, and then sum the weighted row bounds at sites satisfying both degree cutoffs. The right side divided by M is a fixed power of L for fixed W. Multiplication by the exceptional fraction e^{-2k} makes its contribution, after division by 2LM, at most e^{-L} for large L. Therefore

It remains to compare this form with the original prefix sum. Denote by c_j(n;d,q) the signed summand belonging to (d,q) in T C_j^\circ, including all its endpoint cutoffs. Use the same formula to define it for every positive n, and put r=hqd. These cutoffs are predicates of the ambient sites, independent of the choice of block; restricting to a block only removes edges leaving it. Testing an increasing matrix entry cancels its two square-root weights and gives L c_j(n;d,q); symmetry gives the same term in the opposite orientation. Thus the form on the left of (8.11), before taking absolute values, is exactly

where [x]_+=\max(x,0). This is the number of blocks containing both endpoints. All contributing n are positive.

Let

Every displacement is at most R_L, and the one-orientation row bound proves \sum_{d,q}|c_j(n;d,q)|\le D_L for every n. For large L we have N\gg M>R_L. If M\le n\le N, then m_N(n,r)=M-r. The lower boundary and the extra sites N<n<N+M contain at most 2M sites, and always 0\le m_N(n,r)\le M. Consequently the difference between (8.12) and C_j^\circ=T^{-1}\sum_{n\le N,d,q}c_j(n;d,q) is at most

The last term accounts for replacing N^{-1} by T^{-1}. Since M=\lceil e^{103L}\rceil, T\ge X=e^{L^A} and D_L is polynomial in L, (8.13) is O(e^{-L}) for sufficiently large L. This also bounds edges whose terminal endpoint exceeds T and the floor errors. Combining with (8.11) proves (8.8).□

Proof of Remark 2.1. There are O(L/\eta) bins. Sum (8.8), use S_0\ge SV_*/2 and V_*\ge W^J, and then apply the centering and deletion estimates of Remarks 4.1 and 4.6. We obtain

The deletion error in Remark 4.6 is already summed over the bins. The new error O((L/\eta)e^{-L}) from Remark 8.4 is absorbed by e^{-L^{0.9}}, because L/\eta is polynomial in L and SV_*\ge1.

Choose the absolute constants in the following order. First fix A as required by Remark 3.1; in particular A\ge1000 and A>C_1+20, where C_1 is the absolute exponent in that comparison. The trace proof gives an absolute C_2, and (8.7) then gives an absolute C_3. Now choose W\ge10 so large that

Only after fixing these constants do we increase the threshold for X, allowing it to depend on h,l,W.

Recall \eta=e^{-J}, K=e^{4J} and J\le\delta\log L/(6W) with \delta=1/200. The spectral term in (8.14) is at most e^{-J} by (8.15). The other terms satisfy

For the last line, it is enough to note that

Also e^{-L^{0.9}}+X^{-1}\ll e^{-J} for large X. Hence |F(X)|\ll_{h,l}e^{-J}. Finally,

All three constants A,W,c are absolute. The argument applies to every sufficiently large real X, with no excluded scales. On the remaining bounded range 3\le X\le X_0(h,l), the estimate follows from |F(X)|\le1 after enlarging the implied constant. This proves Remark 2.1.□

Proof of Remark 1.1. Fix a_1,a_2\ge1 and b_1,b_2\ge0 with nonzero determinant, and put

Multiplying the two affine arguments by a_2 and a_1, respectively, and using complete multiplicativity gives

Here \lambda(l)^2=1. For real Y\ge0 set

The sum is empty for Y<1. Let c>0 be the absolute exponent in Remark 2.1. That estimate applies to the residue c_0 without any coprimality restriction and gives

For every real X\ge3, the integers in the class c_0\pmod l with c_0<m\le lX+c_0 are precisely m=ln+c_0 with 1\le n\le X. Consequently (9.1) gives the exact endpoint identity

This identity includes both determinant signs and noninteger cutoffs. Since lX+c_0\ge X\ge3 and lX+c_0\le(l+c_0/3)X, the first term satisfies

Also |P(c_0)|\le c_0, which is absorbed into the same bound: the function (\log X)^c/X is bounded on [3,\infty). The exponent has not changed and is independent of the affine coefficients; only the implied constant depends on them. This proves Remark 1.1 for all real X\ge3.□

Proof. Write v_p(n) for the exponent of p in n. For a finite set \mathcal P of primes, multiplicativity gives

The majorant is periodic modulo \prod_{p\in\mathcal P}p^2. Its ordinary mean is

These products tend to zero as \mathcal P increases through the primes: the sum of the subtracted quantities diverges, whereas \sum_p p^{-2}<\infty. First take the long average with \mathcal P fixed, and then increase \mathcal P.□

Proof. Normalize the summands of (11.4) to a probability law on divisors, and denote its expectation and probability by \E_{\mathrm{div}} and \Pbb_{\mathrm{div}}. Each prime p in band a is included independently with probability A_a/(p+A_a). Prime harmonic estimates give

Choose C_0 large enough that the probabilities of \omega(d)>\lceil C_0\log B\rceil and \log d>C_0B are each at most 1/8, by Markov’s inequality.

For r_p=|f_1(p)f_2(p)|, the inequality 1-\prod_j r_j\le\sum_j(1-r_j), valid when 0\le r_j\le1, gives

Here squarefreeness permits the use of multiplicativity. Another application of Markov’s inequality shows that the probability of |f_1(d)f_2(d)|<1/2 tends to zero. Also \Pbb_{\mathrm{div}}(d=1)=L_0^{-1}\to0. Thus the remaining divisors carry at least L_0/2 of the unnormalized mass for large B.

There are at most 1+C_0B/\log\tau intervals (\tau^r,\tau^{r+1}], r\ge0, meeting (1,e^{C_0B}]. One of them carries at least cL_0/B of that mass, for a fixed c>0. Take its lower endpoint as H and retain the divisors already satisfying the preceding conditions.□

Proof. Put

For a fixed d, write x=dm. Unless \gcd(d,m)>1 or \gcd(d,m+h)>1, ordinary multiplicativity gives

The exceptional set has ordinary density at most 2\sum_{p\mid d}p^{-1}\le2J/P_0. At fixed B there are only finitely many d, so all associated residue-counting errors vanish as j\to\infty.

For p\in\mathcal C not dividing d, divisibility of dm by p is equivalent to divisibility of m. Hence the mean and variance of k_d(dm) under uniform residues are

The same formulas hold with m+h in place of m. For large B, |\mu_d-v_C|\le J/P_0\le(T/4)\sqrt{v_C}. Chebyshev’s inequality and a union bound show that the proportion on which either cutoff is not 1 is at most 32/T^2. Independence of the two endpoints is not needed.

The length X_j/d lies between N_j/\tau and N_j. Comparing each shorter sum with the sum up to N_j therefore gives

The factor 4J/P_0 allows a difference of size at most 2 on each coprimality failure. The endpoint rounding errors are included in o(1).

Choose \tau-1\le\gamma/64 and 32/T^2\le\gamma/64, and then take B and j large enough for the other two errors to be at most \gamma/64 each. The reverse triangle inequality, valid for the complex number S(N_j), yields

Finally, V_{\mathcal D}\ge H\sum_{d\in\mathcal D}A^{\omega_C(d)}/d \ge cHL_0/B. This proves the result with c_\gamma=\gamma c/8.□

Reduction of Remark 1.2. We deduce Remark 1.2 from Remarks 10.1 and 11.4. The zero-function and divergent-defect cases were settled above. Otherwise suppose (11.2) holds. Choose \tau,T,\phi,C_0 and, for each sufficiently large fixed B, the divisor family of Remark 11.2. Combining Remark 11.3 with the two propositions gives

After dividing by L_0/B, this reads

which is impossible for sufficiently large B.

In this comparison the functions, shift, and bias \gamma are fixed first; then \tau,T,\phi,C_0 are fixed. For each fixed B the limit is taken along the original sequence N_j, with X_j=HN_j. Only after these inequalities hold does B increase. Thus the contradiction excludes every alleged biased sequence.□

Proof. Outside \mathcal P the summands in the squared distances coincide. At a prime in \mathcal P their difference has absolute value at most |b(p)-f(p)|/p\le2/p. Sum this bound, and then take the infimum over |t|\le X and the minimum over the finite character family.□

Proof. We give the sieve bounds including their counting errors. Put

For every prime p<z_0, forbid \nu_p residue classes, where 0\le\nu_p\le2. If r(n) is the number of these prime conditions satisfied by n, even inclusion-exclusion gives

Indeed, for r>0 the sum on the right is \binom{r-1}s\ge0, and for r=0 it is 1. Write E_j((a_p))=\sum_{|\mathcal I|=j}\prod_{p\in\mathcal I}a_p for the elementary symmetric sum over subsets of the primes p<z_0. The Chinese remainder theorem, applied on any interval I of real length V, now yields

The residue-counting error is independent of the position of I. It is at most

for large B.

Let \Lambda_0=\sum_{p<z_0}\nu_p/p. Mertens’ estimate gives \Lambda_0\le2\log\log z_0+O(1)\le3\log B for large B. Since E_j((\nu_p/p))\le\Lambda_0^j/j!, the difference between the truncated density in (12.11) and its full Euler product has absolute value at most

Consequently the count in (12.11) is at most

For one rough integer, take \nu_p=1. The product is O(1/\log z_0)=O(B^{-1+\eps}\log B). Thus the number R of P_0-rough integers in (M,\tau M] satisfies

Both error terms in (12.12) are absorbed, since M\ge P_0/\tau.

The one-point bound proves (12.9), because w>M. To estimate the fourth moment, extend a_w=c_w/w by zero outside its support. Fourier orthogonality gives

There is no factor depending on h: multiplication by the nonzero integer h preserves Haar measure on \T. Let R_k count pairs w,w+k\in(M,\tau M] that are both P_0-rough. Each inner absolute value is at most R_k/M^2. We next bound R_k for k\ne0; only |k|\le2M can contribute. The permitted interval for w is an intersection of two intervals of length less than M. Sieve out the residues 0,-k modulo p<z_0. If k is odd there are no pairs for large B, because both rough integers must be odd. If k is even, the density product is

Here (1-2/p)/(1-1/p)^2=1-1/(p-1)^2\le1 and \log((1-1/p)/(1-2/p))=1/p+O(p^{-2}) for p\ge3. The singular factor is uniformly O_{C_0}(\log B): indeed

since \log|k|\le C_0B+\log2. Applying (12.12) proves

There are O(M) nonzero differences, so their total contribution is O(M^{-1}B^{-4+4\eps}(\log B)^6) by (12.14). The term k=0 is at most (R/M^2)^2\ll M^{-2}, which is smaller than the same bound because M\ge P_0/\tau. This proves (12.10).□

Completion of Remark 11.4. Apply (12.4) with c_w=c_w^{(u)} to each fixed u in the expansion at the start of this section. Dividing its contribution by X contributes the factor A^{\omega_C(u)}/u; the extracted factors f_1(u)f_2(u) have modulus at most 1. The two Fourier inversions cost at most \|\widehat\phi\|_1^2. At fixed B all sums over u,w are finite, and the uniform estimate therefore gives, by (12.2), a total limsup O(L_0B^{-1-\eps}). Adding the earlier coprimality error O(L_0J/P_0) proves (11.11).□

Proof. Full edge divisibility survives reversal: e\mid x and x'=x\pm he imply e\mid x'. For a candidate subpath all residue tests are constant on the original cylinder, since they involve only its fixed prime coordinates. If the current specification is not primitive, take a shorter qualifying contiguous subpath in an allowed orientation. Its support is contained in the preceding support. The positive length strictly decreases, so the procedure terminates.□

Proof. It suffices to count all qualifying specifications. For fixed edge labels, signs, and suffix, its displacement D=z_m-z_{i_0-1} is nonzero because the path vertices are distinct, and |D|\le Lh\tau H. Sum the extra prime first, keeping these numerical edge labels fixed. Since p>P_0,

The support weight for the remaining distinct edge primes is the product of their reciprocals. There are at most LJ edge-prime slots. Choosing the length, signs, suffix, factor counts, and a partition of these slots into equality classes costs \exp(O(LJ\log B)). Indeed a partition of at most LJ slots has at most (LJ)^{LJ} descriptions. Summing each remaining class over its prime values costs at most v_C+v_Z, or 1+v_C+v_Z as a uniform upper bound. At this point we may drop all bin and distinctness restrictions in those positive sums. The resulting bound is

Since LJ\log B=O(B^{1-\rho}\log^2B)=o(\log P_0), this proves the assertion.□

Proof. Suppose successive occurrence blocks of q are separated by edges not containing q. The intervening path begins and ends at active vertices for q, since adjacent qualifying q-edges have divisible endpoints. It is a shorter simple q-free path with nonzero total displacement divisible by q. With extra prime q and its whole path as suffix, it contradicts primitivity. This proves the first part.

Within a constant-label block, an adjacent change of sign would repeat a vertex, so all signs agree. If b=1, the prescribed suffix displacement is \pm khe_m for some 1\le k\le L. The prime p divides neither e_m nor h, and p>L, so this is impossible. Thus b>1. The unequal squarefree labels e_b,e_{b-1} lie in one bin of ratio less than 2. If every prime of e_b divided e_{b-1}, their quotient would be an integer at least 2, a contradiction. Choose r\mid e_b absent from e_{b-1}. By the first part it is absent from the entire prefix. Its coefficient in the suffix is

This is nonzero modulo p, because p>h,L and p divides none of the edge labels. The same reasoning applies to every prime confined to the tail.

Finally, intersect the occurrence interval of q with the prefix 1,\ldots,b-1. The resulting nonempty interval is i,\ldots,j; in particular, j=b-1 if q also occurs in the tail. The sum of these prefix terms is S=z_j-z_{i-1}\ne0. If r\mid S, reverse the path from z_{b-1} to z_{i-1}. Its edges avoid r, it starts at a vertex active for r, and its suffix from z_j to z_{i-1} has displacement divisible by r. Full divisibility survives reversal. This shorter qualifying specification contradicts primitivity. Since q\ne r and S is q times the asserted coefficient, that coefficient is invertible modulo r.□

Proof. The number of slots is at most

since 4\eps<\rho. A partition of R slots has at most R^R descriptions. All further indices have polynomially many choices in B per slot or per recorded vertex, giving the stated entropy. Recording the destination of each step among at most \ell+1 vertices includes possible vertex identifications and any chosen tree of recorded steps within the same bound.

Drop the cutoffs and W^{-1}, which lie in [0,1]. The powers of A from core occurrences are at most A^{\ell J}. A lit occurrence of p, or qualification of any attached specification using p, fixes its residue and supplies at most 1/p. In the absence of either, p appears only on unlit line occurrences. An unlit core occurrence vanishes; each unlit center occurrence supplies \theta/p, so at least one factor 1/p is still available. The remaining conditions may be discarded after taking these positive primewise bounds. Independence of the prime residue coordinates proves (13.5).

If a repeated center prime has a lit occurrence, every unlit occurrence supplies an additional reciprocal beyond the residue probability. If all its m\ge2 line occurrences are unlit, they supply p^{-m}, saving at least p^{-(m-1)} beyond the displayed majorant; here m-1\ge m/2. Additional qualification conditions can only improve the estimate. At least t_0 repeated-unlit occurrences therefore save P_0^{-t_0/2}.

For each unrestricted prime variable its reciprocal sum is at most 1+v_C+v_Z=O(1+\log B). Thus the total before the extra saving is \exp(O(B\log^2B)), including A^{\ell J}. The saving has logarithm at most -\frac12 B^{1+3\eps}, which proves the last assertion for sufficiently large B.□

Proof. Fix the nonselected variables. For the first type of test,

For the second type, invertibility leaves one residue class modulo r_j. Comparison with the integral of 1/x along that progression gives, even when the sum is enlarged from primes to integers,

The bound includes the zero residue class.

Sum the selected variables in the order q_k,q_{k-1},\ldots,q_1. When summing q_j, every remaining earlier test is independent of it, and its own test has one of the preceding uniform bounds. The conditions D_j\ne0 and a_j\not\equiv0\pmod{r_j} are retained through this elimination. If either fails for fixed earlier data, the admissible inner sum is zero. Numerical distinctness may also be retained; dropping it is unnecessary for the progression bound. Backward induction therefore gives a factor

The other prime sums and all descriptions cost \exp(O(B\log^2B)). Since k\log P_0\ge B^{1+\eps}, their product satisfies (13.6).

We verify the final description convention. There are O(B\log B) slots and polynomially many recorded positions or vertices. A bounded number of paths per test is specified by its endpoints and type, together with a choice of prime variables and order; choosing at most the number of slots many tests costs \exp(O(B\log^2B)). The common integer offset has O(\ell H+1)=\exp(O(B)) possible values. After fixing it we may drop the equation that originally identifies it with a difference of tree offsets, since we are taking an upper bound. Each edge product under arbitrary slot assignments is at most e^{BJ}. Hence every indicated bounded sum of path displacements still has logarithmic size O(B\log B), even after the original divisor-bin restrictions have been relaxed. Nonzero and invertibility tests are never relaxed.□

Proof. Root each component. The top of a path is its vertex nearest that root. Choose a path whose top has maximum depth, and mark its one or two edges incident with the top. Every path sharing an edge with the chosen path must contain a marked edge. Indeed, a path sharing an edge below a mark and avoiding that mark remains wholly in the component below it; its top would be strictly deeper. Remove the paths hit by the marks and repeat. The paths chosen at successive stages are pairwise edge-disjoint. There are fewer than t stages, so fewer than 2t marked edges suffice.□

Proof. An unlit core occurrence makes K_{\boldsymbol d}=0. A primitive specification supported on \mathcal F and qualifying at a trace vertex makes the corresponding Y factor zero for every remaining coordinate assignment. Discard these configurations. By Remark 13.6, those with at least t_0 unlit repeated center occurrences have the asserted negligible total. Each of these decisions uses only the line and n_{\mathcal F}.

Cut every tree edge having an unlit fixed occurrence. There are fewer than t_0 such edges. In the remaining forest a gap for p is a path of length at most L with active endpoints and at least one interior vertex, all interior vertices being inactive, for a fixed tree prime p. Such a gap has no p-edge: an active endpoint of a p-edge forces its other endpoint to be active, while a p-edge with inactive endpoints was cut.

Every gap contains a nonfixed prime label. Otherwise all its edge labels are fixed and lit, so the path is fully divisible. Its nonzero total displacement is divisible by p, and its edges avoid p. Taking extra prime p and the whole path as suffix gives a qualifying specification. By Remark 13.2, a primitive one with fixed support qualifies at a vertex of that tree path. Every tree vertex is a trace vertex, contrary to the preceding exclusion.

If there are t_0 edge-disjoint gaps, choose a nonfixed prime q on each. Each chosen prime occurs once on the full line, hence nowhere on the other selected gaps. The displacement of its gap is linear in q modulo the corresponding fixed prime p, with coefficient \pm h times the other prime factors of that edge. This coefficient is invertible modulo p, since the gap is p-free and p\nmid h. The selected constraints do not involve one another’s variables. Their paths and variables have the description cost of Remark 13.7, which discards this class. The inequality t_0\ge B^{2\eps} holds for large B.

Otherwise Remark 14.2 supplies fewer than 2t_0 further cuts meeting every gap. For each remaining piece traverse every edge twice and split that traversal into segments of at most L steps. The edges and vertices in a segment form a connected subtree of diameter at most L; include a singleton block for a piece with no edges. There are

blocks. They may overlap. Any two active vertices in a block have their joining path inside that block. An inactive portion on it would give a surviving short gap, impossible after the cuts. Thus activity is connected or empty on each block. Each block meets at most one whole-tree active component, and every such component has a vertex in a block. This proves the component bound.□

Proof. Start with arbitrary roots. A connected vertex set in a tree contains the entire path between any two of its vertices. It therefore has a unique nearest vertex to a chosen root. The root-to-x_p^j path avoids p-edges. If a retained label q occurs on this path, both ends of its edge lie in A_q^j; the nearest vertex x_q^j is then a strict ancestor of x_p^j. Thus dependencies are contained in the two strict ancestor orders. Indices with equal nearest points are incomparable.

Every finite partially ordered set with u elements has a chain or an antichain of size at least \sqrt u: partition its elements by the length of a longest chain ending there. Apply this to the first ancestor order. If an antichain is obtained, there are no dependencies from block 1 among its indices, so depth order in block 2 suffices. Otherwise apply the same argument in block 2 on the selected chain. An antichain there similarly suffices. In the remaining case we have chains in both blocks with at least m^{1/4} indices. The Erdős–Szekeres monotone-subsequence theorem [ES35, p. 467] shows that two total orders have a common agreeing or reversed subsequence of size at least the square root of their length. To recall the elementary argument, assign to each position the lengths of the longest increasing and decreasing subsequences ending there. Two positions have different pairs, so if both lengths are less than \sqrt u there cannot be u positions. We thus retain at least a constant times m^{1/8} indices. Agreeing orders already give the conclusion.

Suppose the orders are reversed. In block 2 take the segment from its root to the farthest selected x_p^2. The intersection of each A_p^2 with that segment is a closed vertex interval beginning at x_p^2; these left endpoints are distinct. At a vertex of the segment, each positive-length interval containing it contains an incident segment edge. Each of the at most two such edges has at most J prime factors. At most one interval can consist of that vertex alone. Hence at most 2J+1 intervals overlap at a vertex. Greedily coloring closed intervals in order of their left endpoints uses at most 2J+1 colors: an existing color is available only if its preceding right endpoint is strictly earlier than the new left endpoint. One color retains at least a 1/(2J+1) fraction of pairwise vertex-disjoint intervals.

Reroot block 2 at the far end of the segment. The nearest point of A_p^2 is now the right endpoint of its interval. Indeed, for any vertex of A_p^2 off the segment, its projection onto the segment lies in that interval, because the path from x_p^2 to the vertex lies in A_p^2. The path from the new root first reaches A_p^2 at the right endpoint. This also proves that off-segment branches cannot change the nearest point.

The right endpoints of vertex-disjoint intervals have the same order as their left endpoints along the original segment. Seen from its other end, that order reverses. The two block orders therefore agree after rerooting. The first paragraph applies to the new root as well and proves the dependency assertion. Each representative stayed in the same whole-tree component for its prime, so the two representatives for that prime are still distinct.□

Proof. For every such prime choose two blocks meeting distinct whole-tree active components. There are O(B^{2\rho}) ordered block pairs, so one pair serves m\gg B^{1-4\rho} primes. Inside each block, the active set is nonempty and connected. Every edge carrying a fixed prime has active endpoints after the earlier cuts, and the converse follows from p\nmid h. Apply Remark 14.4 and then specify the common integer

Each retained prime gives the test (14.3). The expression is independent of p, since both local paths avoid it. It involves only earlier retained variables by the lemma. Its nonvanishing follows from distinctness of the two representatives and the distinct integer offsets of tree vertices. The number of tests is

for large B.

Roots, endpoints, and prime choices can be recorded with the entropy allowed in Remark 13.7. Choose K only after the rerooting; its O(\ell H+1) possibilities cost \exp(O(B)). Although its original value depends on the labels, fixing it and dropping that defining equation enlarges a positive sum. The local path expressions then have the required triangular dependence. Retain their nonzero tests under this enlargement and apply Remark 13.7.□

Proof. For every corrupted prime choose a witnessing vertex outside its edge endpoints, and put D=\lfloor B^{1-3\rho}\rfloor. Distance from a vertex to an edge means its minimum tree distance to the two endpoints. Suppose first that at least half the selected witnesses have distance at most D from their prime edge. Use the path from the nearer edge endpoint to its witness. This path avoids the prime’s sole edge, so its nonzero displacement is independent of that prime and is divisible by it. The expression contains at most JD other prime labels.

On the selected primes draw a directed dependency edge p\to q if the test for p contains q. Its outdegree is at most JD. Every induced subgraph of the underlying undirected graph has average degree at most 2JD. Successively choose a vertex of degree at most 2JD and delete its neighbors. The resulting independent set has size at least a constant times

Its tests have no selected-variable dependencies. They are covered by Remark 13.7.

Otherwise at least half the witnesses have distance greater than D. Cover the full tree by O(\ell/D+1)=O(B^{3\rho}) connected traversal blocks of diameter at most D, as in the earlier construction. Assign each prime edge to a block containing that edge and its witness to a block containing that vertex. One ordered pair serves \gg B^{1-8\rho} primes. No selected prime edge has an endpoint in the second block: its corresponding witness lies there, so that would put it at distance at most D. Consequently paths inside the second block contain no selected prime label.

Root the two blocks at c_1,c_2. In block 1 let x_p^1 be the nearer endpoint of the prime edge; in block 2 let x_p^2 be its witness. The first local path avoids p. If it contains a selected prime q, the nearer endpoint of the q-edge is a strict ancestor of x_p^1. Thus the tests (14.3), after specifying the common root offset, are triangular in the depths of the first-block endpoints. The second local paths introduce no selected variables. Each tested displacement is nonzero because its witness differs from the chosen edge endpoint. Since 1-8\rho=3/5>2\eps, there are more than enough tests for Remark 13.7. All choices of witnesses, blocks, roots, and paths fit its description bound.□

Proof of Remark 14.1. Define R_{\boldsymbol d} by retaining the conditions obtained in Remarks 14.3, 14.5 and 14.6. Every activity and occurrence status of a fixed label is determined by n_{\mathcal F}; fixed forbidden qualifications use only those coordinates; corruption uses only numerical offsets. Covers and witnesses can be chosen by fixed finite ordering whenever they exist. Thus R_{\boldsymbol d} depends on no free center residue.

The zero exclusions vanish with K_{\boldsymbol d}\prod_j\1_Y. The other excluded classes have the stated absolute contribution by the three lemmas, yielding (14.2). Their proofs used precisely the majorants of Remarks 13.6 and 13.7, which allow up to 2t_0 attached specifications. Their retained tests depend only on the numerical line and fixed residues, and are unchanged when qualification indicators are added. This proves the additional assertion as well.□

Proof. If I\le J, every event containing I also contains J. Thus every family admitted for the maximum defining \operatorname{rk}(I) is admitted for \operatorname{rk}(J), proving monotonicity. Choose an inclusion-minimal family generating I. Each member must have a private coordinate: otherwise all its prescribed values already follow from the other members, since the prescriptions are compatible, and it can be removed. Its size is therefore at most \operatorname{rk}(I), proving (15.2) as well.

Fix J\in\mathscr P and let m=|\operatorname{supp}(J)|. An element of the interval [\widehat0,J] is determined by its support: its values must be the corresponding restrictions of those prescribed by J. Consequently this interval has at most 2^m elements. Along a strict chain from \widehat0 to J, supports grow strictly, so there are at most m steps. A chain of k steps is specified by recording, for each coordinate of \operatorname{supp}(J), the step at which it enters. There are at most k^m such chains. Expanding the inverse of the poset’s upper triangular incidence matrix, or applying the Möbius recursion repeatedly, gives the alternating sum over these chains. Thus, for m\ge1,

the coefficient at \widehat0 is 1. This proves the asserted coefficient bound for intersections of rank below t.

For x\in\Omega, let J_x be the intersection of all events satisfied at x, with J_x=\widehat0 if none are satisfied. An intersection I\in\mathscr P contains x if and only if I\le J_x. Indeed any family generating I then consists of events satisfied at x. It follows that

Since no forbidden event is the whole space, the last expression is precisely the avoidance indicator in (15.3).

If \operatorname{rk}(J_x)<t, monotonicity shows that the truncated sum contains the entire interval [\widehat0,J_x], so it is exact. Suppose instead that \operatorname{rk}(J_x)\ge t. Given any I\le J_x of rank below t, successively intersect it with events satisfied at x until reaching J_x. Let K be the first intersection whose rank is at least t, and let K^- be its immediate predecessor. Replace the generating family for K^- by an inclusion-minimal one. It has at most t-1 members. Adjoining the event that produces K shows that K is generated by at most t events. Thus

This argument allows the rank to jump by more than one. The re-minimization of the predecessor, rather than the length of the successive list, bounds the number of generators.

Every satisfied low-rank I is therefore below a satisfied member of \mathscr H_t. For any one such member there are at most 2^M possible predecessors I, by the interval bound already proved. The exact avoidance indicator is zero in the present case. Bounding each retained coefficient by (15.4) now gives (15.3).□

Proof. Order the witnesses by nondecreasing attachment indices k_1,\ldots,k_{t_0}; break ties arbitrarily. For witness j, choose a private prime q_j\notin\mathcal F, write p_j for its extra prime, and choose a tail prime r_j as in Remark 13.5. Thus r_j occurs only in its final constant block. That lemma supplies two coefficient facts:

1. (i)

   the intrinsic suffix displacement divisible by p_j is linear in a tail-only prime, with coefficient nonzero modulo p_j;

2. (ii)

   if a prime occurs before the constant tail, its coefficient in the prefix displacement immediately preceding that tail is nonzero modulo r_j.

All private primes q_j are distinct. Each occurs at most once as a label on the original line, because it is outside \mathcal F. We divide into three cases to control every dependence on another selected variable.

Private primes in intrinsic suffix constraints. Suppose at least t_0/10 witnesses have q_j=p_j or have q_j occurring only in the constant tail. In the first situation q_j divides the intrinsic suffix displacement, which is nonzero by simplicity and does not involve q_j. In the second situation use that suffix constraint as a linear congruence in q_j modulo p_j; its coefficient is nonzero by (i). The private-prime property excludes every other selected q from the witness, including from its modulus. These constraints have no dependencies on the other selected variables and hence form a triangular system.

Tail primes first or last appearing among the witnesses. Suppose at least t_0/10 witnesses have r_j absent from every earlier witness. Select these tail primes in increasing witness order. They are distinct: equality between two would make the latter prime occur in an earlier witness. Use the intrinsic suffix congruence for each selected r_j. No later selected tail prime occurs in this witness, by its defining absence property. This also excludes later selected variables from the modulus p_j. Thus each constraint uses only its own variable, earlier selected variables, and nonselected variables, and its coefficient is nonzero modulo p_j by (i). If instead at least t_0/10 witnesses have r_j absent from every later witness, the same argument in decreasing witness order applies.

Comparing two activities of a shared tail prime. If none of these cases applies, fewer than 3t_0/10 witnesses have been excluded by their three respective conditions. Retain at least t_0/2 witnesses for which q_j occurs before the tail and r_j appears in both an earlier and a later witness. Since q_j occurs at most once on the original line, it is absent either from all steps 1,\ldots,k_j or from all steps k_j+1,\ldots,\ell. At least t_0/4 of the retained witnesses satisfy the same one of these two absence conditions.

First consider the family absent from steps 1,\ldots,k_j, ordered increasingly by attachment index. For its witness j, choose an earlier witness i=i(j) using r_j. In witness i, choose a vertex at which r_j is active: its starting vertex if r_j is its extra prime, or the origin of an edge carrying r_j otherwise. Let T_i be this vertex’s offset relative to that witness’s start. Let P_j be the prefix displacement of witness j immediately preceding its constant tail. Joint qualification implies

The coefficient of q_j in this congruence is exactly its coefficient in P_j: privateness excludes it from witness i, and the selected absence condition excludes it from the line segment between k_i and k_j. This coefficient is nonzero modulo r_j by (ii).

Now take a later selected private variable q_s. It occurs in neither witness i nor witness j, by privateness. Moreover k_s\ge k_j, and its own absence condition excludes it from every line step through k_s, hence from the segment in (15.7). Thus no later selected variable occurs in that congruence. The modulus r_j is not any selected private prime: it differs from q_j because q_j occurs before the tail, and it differs from all other q_s by privateness. This proves triangularity in increasing order. Equal attachment indices merely make the corresponding line segment empty.

For the family absent from steps after k_j, order the witnesses decreasingly and compare witness j to a later witness containing r_j. Equation (15.7) has the same form, now with its line segment after k_j. A later selected variable in this decreasing order has attachment k_s\le k_j and is absent from all steps after k_s, so it is absent from that segment. Privateness excludes it from the two witness prefixes. Fact (ii) again supplies the nonzero coefficient. This gives a triangular system in decreasing order. The attained comparison displacement may equal zero; that causes no difficulty, since we use an invertible linear congruence, not a divisibility constraint with the selected prime as modulus.

Every case provides at least t_0/20 selected variables for sufficiently large B, allowing for integer parts. This is greater than B^{2\eps}. Each label is a squarefree product of at most J primes at most e^B, so its logarithm is at most BJ=O(B\log B) even without the divisor-bin restrictions. A suffix or a comparison above uses O(\ell+L) such terms. Every nonzero expression consequently has logarithmic size O(B\log B). The constraint choices are specified by witness and line positions and prime slots, within the enumeration allowed in Remark 13.7. All its hypotheses are now verified.□

Proof. At fixed \boldsymbol d,n_{\mathcal F} with R_{\boldsymbol d}=1, apply Remark 15.1 to the residual cylinders with t=t_0 and w=LJ+1. Multiply the identity with its pointwise error bound by K_{\boldsymbol d} and integrate the residual coordinates. For the low-rank sum, take the absolute value after each such integral and use the generating lists already constructed. The coefficient bound gives the main term on the right of (15.8).

For the error, take the absolute value of K_{\boldsymbol d} inside the integral and use the generating and witnessing lists described above. After integrating the fixed coordinates, their indicators require joint qualification of at most 2t_0 specifications, including the t_0 witnesses with private primes outside \mathcal F. We may drop the retained-data restriction in this positive bound. Remark 15.2 supplies at least B^{2\eps} triangular constraints for each nonzero contribution.

Refine the error count by the lit or unlit status of every line occurrence. Joint qualification fixes one residue for each distinct prime used by the specifications, or is inconsistent and contributes zero. For each refinement, Remark 13.6 gives A^{\ell J}\prod_p p^{-1}, with the product over distinct prime labels, rather than charging a shared residue repeatedly. The line and lists have at most

prime slots. Their equality patterns, occurrence statuses and all choices of witness constraints have cost \exp(O(B\log^2 B)). These are exactly the positive majorant and description budget required by Remark 13.7. Its reverse elimination applies to the system just supplied by Remark 15.2 and gives O(e^{-B^{1+\eps/2}}). The additional factor \mathfrak C_B is absorbed by the same estimate, since (15.6) gives \log \mathfrak C_B=o(B) whereas the saving before this final simplification is \exp(-\Omega(B^{1+\eps})). This proves the proposition.□

Proof. At each step record whether its destination is new and record its sign. At each return record one of at most \ell+1 previously visited vertices. These data give the stated bound. A tree-edge label and its sign specify the difference of its endpoint offsets; all offsets are consequently determined, and a return label must be the absolute endpoint difference divided by h. We retain only assignments for which the abstract vertices have distinct offsets and all these return labels belong to \mathcal D. There is no independent choice of a return label.

Let q be the number of leaves and b the number of vertices with at least two children. The adding steps occur in at most r_*+1 runs, each a downward path, so q\le r_*+1. Also b\le q-1 and

The number of edges incident with a leaf or such a branch vertex is therefore at most 4q. There are at most 2r_* endpoints of return steps. An endpoint that has not already been counted is unary and is incident with at most two tree edges, giving at most 4r_* further edges. The root adds at most one edge unless it was already counted as a branch vertex. These bounds imply (16.1).□

Proof. Start at a prescribed vertex v. At every reached vertex include each child edge independently with probability A_a\beta_a and exclude it with probability \beta_a. The resulting connected subtree has top v. A particular outcome Q has probability

The outcome with no edges has probability \beta_a^{s(v)}. Sum the other probabilities, then sum over the possible tops v.□

Proof. If adjacent vertices are active for p, their difference \pm hd is divisible by p. Since p\nmid h, the intervening label contains p. Conversely, a lit occurrence has both endpoints active. Thus the nontrivial active components record exactly the lit tree occurrences. Ghosts record the other occurrences; isolated active vertices create no label. Multiplying the distinct prime values of the tokens covering an edge recovers its label, proving (i).

By Remark 14.1, the fixed primes with several active components contribute O(B^{1-2\rho}B^\rho)=O(B^{1-\rho}) subtree tokens. Unlit fixed occurrences contribute O(t_0) ghosts and at most that many newly tagged connected labels. Corrupted nonfixed primes contribute O(B^{1-2\rho}) ghosts. Lists contribute O(M_0) slots and at most one new token per newly tagged connected tree prime: disconnected primes and primes with unlit occurrences have already been counted. Since

the sum of these bounds is at most N_{\mathrm{exc}} eventually.

For (iii), such a prime is repeated on the line and all its occurrences are lit. If its tree token consists of a single edge, its connected active set contains only the two endpoints of that edge. A further occurrence cannot be another tree edge, and hence must be a return touching these endpoints. This contradicts goodness. An active return endpoint elsewhere would give another active component and would have tagged the prime.□

Proof. Order of integration. The set \mathcal F does not contain every core prime. Put \mathcal C'=\mathcal C\setminus\mathcal F and \mathcal Z'=\mathcal Z\setminus\mathcal F. At fixed n_{\mathcal F} use exactly the inequality

In the inner average hold all core coordinates as parameters. The cutoffs can depend on the background core coordinates in \mathcal C', but never on \mathcal Z'. Apart from these cutoffs, the kernel and each compatible list cylinder separate by prime. The inner center-prime averages therefore factor, with their signs intact. We will subsequently use positive majorants in the other coordinates. No enlargement of the fixed set in the cylinder construction is involved.

Charging the cutoffs. Use the origin cutoff at each return step. For each u\in\mathcal U, use the endpoint cutoff at u of its incoming tree edge, which exists because a good origin is not the root. These are distinct cutoff occurrences: vertices of \mathcal U touch no return, and an incoming tree edge has a unique child. A charged cutoff with label d is at most

This inequality holds also off its support. The other cutoff factors are at most one. The constant parts give the first negative term in the exponent of (16.5).

For a return, allocate the normalization at its origin to that return. For a core prime its multiplier is A\beta_C when the prime is in the label and lit, zero when it is in the label and unlit, and at most \max(1,\beta_Ce^\kappa)=1 otherwise. Both A\beta_C<1 and \beta_Ce^\kappa<1 follow from A=e^{2\kappa}. Center-prime return multipliers also have absolute value at most one. These bounds will be used except when integrating a good singleton, where we retain the return factors until its signed average has been taken.

Fixed tree primes. After removing the bounded return factors, the core tree factors for an active component Q containing an edge are

At a charged vertex u\in\mathcal U, activity in such a component either continues through the incoming label, in which case that prime is excluded from this charge, or begins a subtree token at u, which is excluded by the definition of \mathcal U. Thus an additional e^\kappa can occur only at an isolated active vertex there. Its normalization is \beta_C^{s(u)}e^\kappa=\beta_Ce^\kappa\le1. Other isolated activities also contribute at most one. The remaining bound is the product of the core subtree weights.

A core tree prime has a lit occurrence. Choose one deterministically from its tokens and retain its activity indicator. This is one specified residue modulo p and supplies the factor 1/p upon integration. For a fixed center tree prime, the same argument gives the product of its active-subtree weights; lit factors 1-\theta/p are at most one, and ghost occurrences are bounded absolutely. If there is a lit tree occurrence, retain one such residue indicator. If there is none, at least one unlit tree occurrence supplies \theta/p\le1/p directly, without a residue restriction. Ghost weight 2 bounds all the remaining ghost factors. These constructions are positive primewise majorants on the assigned group.

Nonfixed tree primes. A tagged nonfixed tree prime has one occurrence. Its absolute integral is at most 2/p: the lit residue contributes at most 1/p and the other residues at most \theta/p. If the list fixes its residue, the bound only improves. An untagged nonfixed prime on a nongood edge Q contributes at most

Indeed its lit residue includes the normalizations of both endpoints, and any additional activities can only reduce their product.

Now let p be an untagged nonfixed prime on a good edge Q=(u,v). It occurs nowhere else on the line and in no list. On its lit residue, noncorruption says that no other tree vertex is active. Each endpoint has exactly one tree departure and no return incidence. Its entire prime multiplier, including return factors, is therefore exactly

Let a_0 be its lit residue, and for a\in\Z/p\Z define

This counts departures with multiplicity, including return departures. We have \nu_p(a_0)=2. On every other residue the entire prime multiplier is exactly -\theta\beta_Z^{\nu_p(a)}/p. Consequently its signed average is exactly

There are at most r_p-1 terms in the last sum, where r_p\le\ell+1 is the number of residue classes represented by tree vertices. The displayed quantity is nonnegative and at most

for sufficiently large B. Thus \theta=\beta_Z^2 cancels the terms of order 1/p before any absolute value is taken. Removing return factors by an absolute estimate before taking this average would not justify the calculation on the no-activity residues; here they have been retained throughout.

List primes and background primes. For a list prime absent from the tree, qualification supplies one specified residue. All other factors, including charged factors, are bounded by one: any activity in the tree is isolated, and at a vertex of \mathcal U its factor is again \beta_Ce^\kappa\le1. This yields 1/p for that prime.

For any remaining prime, discard return factors by the absolute bounds already proved. The positive tree multiplier is

If the tree offsets are pairwise distinct modulo p, its integral is exactly

For offset collisions we use the bound one. A prime occurring only on a return divides the nonzero difference between that return’s two distinct vertices, so is automatically one of these collision primes. It entails no independently chosen prime slot.

The omitted background primes are tree or list primes, or divide one of the O(\ell^2) nonzero differences of size O(\ell H). There are O(B\log B) tree and list slots. Since every prime is at least P_0 and \log(\ell H+2)=O(B+\log B), their reciprocal mass, multiplied by \ell+1, is o(1), uniformly in the valid assignment. For example each nonzero difference has at most \log(O(\ell H)+2)/\log P_0 prime divisors from \mathcal S. Using 1-x\le e^{-x} in (16.7) and restoring the omitted harmonic masses gives the remaining exponent in (16.5), with an o(1) error. The numerator in (16.7) is nonnegative, since at every charged vertex \beta_C e^\kappa\le1.

Finally, the grouping does not assert independence of conditioned coordinates. After (16.6) and the signed free-center integrations, use the positive majorants above on the group. Whenever a used-prime probability 1/p is claimed, its chosen activity or list residue indicator is retained. Drop all other group restrictions and integrate the resulting product over the remaining coordinates. This is an enlargement of a nonnegative integral and hence is valid despite any dependencies within the original group. It yields one bound per assigned record, not one bound for each individual fixed-coordinate configuration. Combining the primewise bounds proves the lemma.□

Proof. Choose one eligible type at each origin using any fixed order, and then choose its first named slot. Distinct origins choose different slots. Because s(u)=1, a nontrivial subtree with top u contains the edge leaving u.

Fix all other prime values and order the selected slots ancestor-first by their tops. If the token of a selected slot occurs on the edge leaving u, its top is u or an ancestor of u. Thus that edge’s product contains its selected prime and only earlier selected primes. The bin requirement has the form

where D_i is positive and all its other factors have been fixed. The harmonic sum of a core prime in such an interval is O(B^{-1+\eta}), uniformly in its position. To see this, write the interval as (x,\tau x]. If it meets the core band, then x\ge \exp(B^{1-\eta})/\tau, and the prime-counting upper bound gives

Eliminate the selected variables in reverse ancestor order. Each bound is uniform in the remaining earlier values, so induction gives one such factor per selected slot. Since v_C\ge1 for large B, each bound is also O(B^{-1+\eta})v_C. All unselected variables keep their unrestricted harmonic sums. This choice of named pivots requires no enumeration of possible pivots, and the bin condition holds for every slot permutation counted in (16.9).

The charge contribution is

Both bracketed coefficients exceed 100\log B for large B: v_C=(\eta+o(1))\log B, \kappa\eta=400, and \beta_C(e^\kappa-1)<1. Every non-skipped good edge therefore pays either its pivot saving or the stronger factor B^{-100} from its origin in \mathcal U. At most N_{\mathrm{exc}} good edges were skipped. Absorbing the constants for at most \ell pivots gives (16.10).□

Proof. First apply Remarks 16.4 and 16.5 to valid assigned records. The pivot bound is uniform in the detailed record and may be factored out for each topology.

For the tagged/list groups, unrestricted prime sums cost at most (1+v_C+v_Z)^{O(N_{\mathrm{exc}})}. A tagged subtree shape can be summed with its weight using (16.3), at a cost at most \ell+1; a ghost has at most \ell possible edges and weight 2. Ignoring compatibility between token shapes increases these positive sums. Thus all these shape costs are (O(\ell+1))^{O(N_{\mathrm{exc}})}. Together with (16.8), the lost skipped-edge savings and the cylinder prefactor, their logarithm is

For the untagged tokens, retain (16.9) and sum over unrestricted multiplicities. Their total is at most

These are finite products of positive convergent series. They cancel the unmodified background terms -v_CS_C(\mathscr T)-v_ZS_Z(\mathscr T) in (16.5). By (16.4), the remaining exponential is

for large B, since (\theta/2)(\eps-\eta)>\eps/10 and \theta(\eps-\eta)<\eps.

It remains to check the numerical margin including the topology count. Write g=|\mathcal G|, b=|E(\mathscr T)\setminus\mathcal G| and r=r_*. Then \ell=g+b+r and b\le10(r+1). Set \delta=\eps/10-\eta=9\eta. Combining the preceding bounds, (16.10) and the count in Remark 16.1, the negative base-B exponent is at least

Here 4^\ell and the fixed constants per pivot contribute O(\ell/\log B)=o(\ell), and (\ell+1)^r=B^{(1+o(1))r}. Substitution of g=\ell-b-r and b\le10(r+1) gives the lower bound

The coefficient of r is positive, and \delta-2c_*=7\eta>0. The slack absorbs the fixed last term, the displayed o(\ell) terms, and the sum over at most \ell+1 possible values of r. This proves the claimed bound.□

Completion of the proof of Remark 13.3. The density assertion is Remark 13.4. Apply Remark 14.1 to split the trace sum into retained and discarded configurations. For the retained part, the triangle inequality bounds the absolute full expectation by \E_{\mathcal F}R_{\boldsymbol d} |\E_{\mathcal S\setminus\mathcal F} K_{\boldsymbol d}\prod_j\1_Y(n+b_j)|. Now apply Remark 15.3. Their discarded contributions are O(\exp(-B^{1+\eps/2})). The retained conditional main term is bounded by Remark 16.6. Since \ell=2\lfloor B\rfloor,

for sufficiently large B. This proves the trace assertion and completes the theorem.□

Proof. The product \chi\overline\psi is a Dirichlet character modulo the least common multiple of the two moduli. At every prime outside S,

This identity holds also at primes where a character vanishes. Each prime in S contributes at most 2/p to the difference of squared distances, proving (18.1). Take the infimum over exactly |t|\le X on both sides of the resulting lower bound. For each fixed \chi, the character \chi\overline\psi is fixed, and the bounded error cannot prevent divergence to infinity. For conjugation the exact identity is

The interval |t|\le X is unchanged by t\mapsto-t.□

Proof. Let P(a) be the set of prime divisors of a. For p\in P(a) set \alpha_p=v_p(a) and define

Factorization into pairwise coprime prime powers gives the exact identity

No identity between f(p^k) and f(p)^k is used.

The obstruction to multiplicativity in this product is that A_p(0)=0. Resolve it by setting

Then A_p=B_p-C_p at every nonnegative exponent. For E\subseteq P(a) put

All local factors have modulus at most one and value one at exponent zero. If u and v are coprime, at most one of v_p(u),v_p(v) is positive at each prime; hence f_{a,E}(uv)=f_{a,E}(u)f_{a,E}(v). Expanding the finite product in (18.4) yields

Each summand agrees with f at prime powers outside P(a), so Remark 12.1 proves the last assertion.□

Proof. If d\nmid m, both sides vanish. If d\mid m, the congruence on the left is equivalent to m/d\equiv c\pmod q. When q>1, the residue c is a unit modulo q, so character orthogonality on (\Z/q\Z)^\times gives

For a nonunit m/d every character on the right vanishes. The case q=1 is the trivial identity with the stated convention. The finite expansion now follows from Remark 18.2.□

Proof. We may assume both functions are nonzero. Choose j\in\{1,2\} for which f_j is uniformly nonpretentious. Since

Remark 18.3, using the least nonnegative representative of b+h_j modulo l, expands the indicator as a function of m=n+h_j into finitely many bounded multiplicative functions, each agreeing with a fixed Dirichlet character outside a fixed finite prime set. Their products with f_j are uniformly nonpretentious by Remark 18.1. Apply Remark 1.2 to each product at shift h_j and the unchanged other factor at its distinct shift, and sum the finitely many conclusions. This proves (18.8) at integer X. For real X, replacing the normalization X by \lfloor X\rfloor changes the average by at most 1/X, proving the assertion.□

Proof of Remark 1.3. Zero factors again give an immediate conclusion. Otherwise set

For \Delta>0 put U=F_{a_2,f_1} and V=F_{a_1,f_2}; for \Delta<0 put U=F_{a_1,f_2} and V=F_{a_2,f_1}. In either case,

Indeed, when \Delta>0 the two arguments on the left are a_2(a_1n+b_1) and a_1(a_2n+b_2); when \Delta<0 their order is reversed.

Expand U and V by Remark 18.2. Each pair of multiplicative components has a uniformly nonpretentious factor, inherited from the corresponding original function. Applying Remark 18.4 termwise with shifts 0,h gives

Put T(m)=U(m)V(m+h)\1_{m\equiv c_0\pmod l} and X=lN+c_0. The integers in this class satisfying c_0<m\le X are precisely ln+c_0, 1\le n\le N. Therefore

The first term tends to zero because X/N\to l and (18.11) holds. The second has modulus at most c_0/N and is empty when c_0=0. This proves the corollary, including zero intercepts and coefficients with common factors.□

Proof. For a real 1-bounded multiplicative function f, [MRT15, Lemma C.1] gives

When \chi^2 is nonprincipal the same bound holds throughout |t|\le X. Thus taking f=\lambda proves the assertion for nonreal \chi and handles 1\le|t|\le X for all \chi. For real \chi, the other part of the cited lemma gives

It remains to estimate the distance at t=0 for these real characters.

If \chi is nonprincipal, the prime number theorem in arithmetic progressions for its fixed modulus yields, for some c_\chi>0,

Partial summation gives

since the integral converges absolutely as X\to\infty. As \lambda(p)=-1, Mertens’ estimate now gives

If instead \chi is principal modulo q, then

In both cases (18.15) is at least \frac13\sqrt{\log\log X}-O_\chi(1). Combining this with (18.14) proves (18.13) on the entire interval |t|\le X.□