WEIGHTED DILATION GRAPHS, SMOOTH SHIFTED PRIMES, AND TOTIENT FIBERS
version 2, September 2026.
a rewrite of weighted_dilation_totient_fibers_original.txt ("v1" below).
same mathematics, same order of proof, no LaTeX. every theorem is stated
in full; easy steps are proved completely; hard steps are reduced to a
list of precise claims that are then proved one by one.
0. HOW TO READ THIS FILE
What you need already.
- primes, unique factorization, gcd, congruence modulo m.
- logarithms, exponents, the phrase "for all sufficiently large x".
- Euler's phi(n), the number of a in [1,n] coprime to n. It satisfies
phi(p^a) = p^(a-1)(p-1) and phi(mn) = phi(m)phi(n) when (m,n) = 1.
- the O(.) and o(.) notation.
- basic probability: expectation, independence, "pick uniformly".
- nothing about Dirichlet characters. They appear twice, as bookkeeping
for residues modulo a small number; each time the use is spelled out.
What x^(1-o(1)) means. A count is x^(1-o(1)) if for every fixed eps > 0
it is at least x^(1-eps) once x is large. It has the full first power of
x, but it is not a positive proportion of x, and it is much weaker than
x/log x. Theorem B below is exactly this.
Convention on constants. Every constant is fixed before x tends to
infinity. L^O(1) means some fixed power of L = log x. An "arbitrarily
small negative power of L" means: for every fixed A > 0 we can make the
quantity at most L^(-A), at the cost of choosing an earlier parameter (a
mesh size, a number of integrations by parts, a sieve block count) large.
Whenever a parameter is chosen we say what had to be fixed before it.
Circular choices are the usual way this kind of argument dies.
Three scales recur.
L = log x, T = log L, W = exp(sqrt L).
So L is huge, T is tiny compared with L but still tends to infinity, and
W sits between every fixed power of L and every positive power of x:
W = x^o(1). T is also the number of size bands, because the primes
between exp(L^a) and exp(L^b) for fixed 0 < a < b < 1/2 can be cut into
about T geometrically spaced bands.
Vocabulary.
y-smooth: every prime factor is at most y.
y-rough: every prime factor is larger than y.
P^+(m): the largest prime factor of m.
P^-(m): the smallest prime factor of m.
N_u: the integer 2u+1.
So P^+(p-1) <= x^delta says p-1 is x^delta-smooth, and P^-(m) > W says m
is W-rough.
Fixed parameters used throughout. A prime set P is split into "small
groups" of primes in [exp(L^a), exp(L^b)] and "big groups" that are whole
intervals of primes in [exp(L^c), exp(L^d)], with 0 < a < b < c < d <
0.47. Also q in (0,1), ell a positive integer, and V_g the reciprocal
prime mass of group g, kept within fixed positive bounds [v_-, v_+]. The
number of groups of each kind is between fixed positive multiples of T.
These objects are introduced properly in section 5; until then they are
not needed.
The plan of the file.
1. the two theorems
2. the easy half: Theorem B implies Theorem A
3. the hard half: what is left, and the shape of the argument
4. toolkit: the elementary lemmas, proved
5. the weighted dilation graph, and two operator theorems
6. transference: physical graph to independent labels
7. small ideal kernels at every frequency
8. shifted correlations
9. the Type II estimate
10. the prime extraction, and the two sieve regimes
11. Theorem B from the sieves
12. Theorem A
13. where each hypothesis is used
Sections 5 to 9 are one continuous estimate. A reader who wants the
skeleton can read 1 to 3, then 10 to 12, and treat 5 to 9 as a black box
stated in Theorem 8.1.
1. THE TWO THEOREMS
Define
g(n) = #{ m >= 1 : phi(m) = n },
the number of preimages of n under phi, that is the size of the fiber of
phi above n.
THEOREM A (Erdos's conjecture on the largest totient fibers).
For every real eps > 0 there are infinitely many positive integers n with
g(n) > n^(1-eps).
LEMMA 1.1 (the exponent 1 cannot be improved). For every eta > 0,
g(n) <<_eta n^(1+eta). Proof in section 2.
So a fiber can be as large as the value it sits over, up to n^eta, and no
larger. Theorem A says the exponent tends to 1.
THEOREM B (smooth predecessors of primes).
For every fixed 0 < delta < 1/4, as x tends to infinity,
#{ p prime : 2x < p <= 5x, P^+(p-1) <= x^delta } >= x^(1-o(1)),
where the o(1) may depend on delta.
Theorem B for one delta implies it for every larger fixed delta: run it
with any delta' <= min(delta,1/4), since x^(delta') <= x^(delta). So the
theorem holds for every fixed delta > 0.
Theorem B is much stronger than the classical statement "for every eps >
0 there are infinitely many primes p with P^+(p-1) <= p^eps". It says
that in the single short interval (2x,5x] the smooth predecessors are as
numerous as x^(1-o(1)), for every fixed smoothness exponent.
WHY THE TWO THEOREMS ARE ONE PROBLEM. Section 2 derives Theorem A from
Theorem B in about forty lines, using only unique factorization and a
pigeonhole. Sections 3 to 11 prove Theorem B.
WHAT WAS KNOWN, WITH THE EXACT NUMBERS.
Erdos (1935, 1956) raised both questions. Pomerance (1980) states the
totient conjecture as C = 1, where C is the supremum of the c with
g(n) > n^c infinitely often, attributes it to Erdos, and records the
transfer from smooth shifted primes reproduced in section 2.
Baker and Harman (1998) obtained P^+(p-1) <= x^(0.2961) for x < p <= 2x,
with totient multiplicity exponent 0.7039. This improved Friedlander's
1/(2 sqrt e) + eps = 0.30326..., and their introduction surveys earlier
work of Pomerance, Balog, and Fouvry-Grupp.
Lichtman (2022) obtained at least x/(log x)^C primes p in (x,2x] with
P^+(p-1) <= x^beta for every beta > 15/(32 sqrt e) = 0.284311..., with
multiplicity exponent 0.7156.
The Dickman function predicts a positive proportion of primes, not just
x^(1-o(1)), for every fixed beta > 0 (Granville 2008, section 5.3).
Bharadwaj and Rodgers (2026) prove a full Poisson-Dirichlet law for
sequences with their regularity and congruence-uniformity conditions
plus level-one distribution; for shifted primes that gives the
prediction under Elliott-Halberstam, and their Proposition 2 verifies
level one half unconditionally.
Alford, Granville and Pomerance (1994) use smooth shifted primes to
build Carmichael numbers, which is one reason the question is not only
about phi.
Theorem B is unconditional, holds for every fixed delta, and gets the full
power of x. It is still weaker than a positive proportion.
2. THE EASY HALF: SMOOTH PRIMES GIVE LARGE TOTIENT FIBERS
This section proves Theorem A from Theorem B. Nothing here is hard and
nothing is approximate: every step is an identity or an exact count.
LEMMA 2.1 (fibers are finite, and not much larger than their value).
(i) For each n the set { m : phi(m) = n } is finite.
(ii) For every eta > 0, g(n) <<_eta n^(1+eta).
PROOF. Write p^a || m to mean p^a divides m but p^(a+1) does not. If
m = p^a m' with (p,m') = 1 then phi(m) = p^(a-1)(p-1) phi(m'). So if
phi(m) = n, then p-1 divides n, which leaves only finitely many possible
primes p, and then p^(a-1) divides n, which bounds the exponent a of each
of them. This is (i).
For (ii) fix 0 < theta < 1. Every sufficiently large prime p satisfies
1 - 1/p >= p^(-theta); only finitely many primes fail this, and the
finitely many integers built from them are absorbed into the constant.
For general m = prod p^a,
phi(m) = m prod_{p | m} (1 - 1/p) >= m prod_{p|m} p^(-theta)
= m (prod_{p|m} p)^(-theta) >= m^(1-theta),
because prod_{p|m} p <= m. Hence every m with phi(m) = n satisfies
m <= n^(1/(1-theta)), and there are at most that many such m. Take
theta = eta/(1+eta). [End]
So g(n) <= n^(1+eta) always, and Theorem A asks for the exponent 1 from
below. Now the transfer.
PROOF THAT THEOREM B IMPLIES THEOREM A. Only 0 < eps < 1 needs proof; a
smaller eps always suffices. Choose 0 < delta with 4 delta < eps, for
instance delta = eps/8.
Apply Theorem B with x = X/5, where X is large. Since 2(X/5) = 2X/5 and
5(X/5) = X, and (X/5)^delta <= X^delta, we get a set Pp of primes with
X/3 < p <= X, p-1 is X^delta-smooth, |Pp| >= X^(1-delta), (2.1)
for all large X: the count X^(1-o(1)) with o(1) < delta beats X^(1-delta),
and asking for p in (X/3,X] is a subinterval of (2X/5,X].
Let M = |Pp| and k = floor(X^(2 delta)). Since 3 delta < 1 we have
k <= M for large X. Put
binom(M,k) = prod_{j=0}^{k-1} (M-j)/(k-j) >= (M/k)^k, (2.2)
since every factor (M-j)/(k-j) is at least M/k. Different k-element
subsets Q of Pp have different products m_Q by unique factorization, so
they give at least (M/k)^k > X^((1-3 delta) k) distinct integers m_Q, and
each satisfies
X/3 < m_Q <= X^k. (2.3)
Step 2: the totients are few and small. By multiplicativity of phi on
squarefree m_Q,
phi(m_Q) = prod_{p in Q} (p-1). (2.4)
Each factor is at most X and is X^delta-smooth, so phi(m_Q) is
X^delta-smooth and at most X^k.
Step 3: count possible values. An X^delta-smooth integer that is at most
X^k is prod p^(a_p) over the at most X^delta primes p <= X^delta, subject
to sum_p a_p log p <= k log X; in particular each a_p is at most
k log X / log 2. So the number of possible values is at most
(1 + k log X / log 2)^(X^delta). (2.5)
The logarithm of (2.5) is at most X^delta log(2 k log X) =
O_delta(X^delta log X), while k log X is about X^(2 delta) log X. Hence
(2.5) is X^(o(k)): for every fixed eps > 0 and all large X it is at most
X^(eps k).
Step 4: pigeonhole. Divide (2.2) by (2.5). Some n is the totient of at
least
X^((1-3 delta) k) / X^(o(k)) = X^((1-3 delta-o(1)) k) (2.6)
of the products, each of which is a preimage of n. That is the claim.
The bookkeeping: |Pp| >= X^(1-delta) gives M >= X^(1-delta), so
k = floor(X^(2 delta)) <= M exactly when 3 delta < 1, which the choice of
delta ensures.
Step 5: infinitely many. By (2.3), n <= X^k, so n^(1-eps) <=
X^(k(1-eps)). Since 3 delta + o(1) < eps by 4 delta < eps, the bound
(2.6) exceeds n^(1-eps) for all large X. As X tends to infinity the
exponent in (2.6) tends to infinity, so the values g(n) obtained are
unbounded. By Lemma 2.1(i) no finite set of n can supply infinitely many
of these products, so the n are unbounded, which is the assertion for
infinitely many n. For eps >= 1 use any smaller positive eps. [End]
WHY SMOOTHNESS IS THE WHOLE STORY. Look at (2.4): the totient of a
squarefree product forgets the primes and remembers only the multiset of
their predecessors. If those predecessors could have large prime
factors, the multiset could be almost anything and the pigeonhole would
give nothing. Because they are X^delta-smooth, the multiset lives in a
set of only X^delta primes with a size budget of k log X, that is a set of
values of size X^(o(k)). The two requirements pull against each other:
we want many primes with smooth predecessors, and we want them in an
interval short enough that the smoothness exponent is measured against x
rather than against p itself. Theorem B supplies both at once. That is
why the remaining eight sections are about primes with smooth
predecessors.
3. THE HARD HALF: THE SHAPE OF THE PROOF OF THEOREM B
By section 2 the whole problem is Theorem B. Fix delta in (0,1/4) and
let x tend to infinity. We count primes p = 2u+1 with 2x < p <= 5x and
u essentially in [x,2x], such that u has a prescribed factorization.
THE FIRST MOVE: CONSTRUCT A THICK SET OF SMOOTH u. Instead of trying to
recognise smooth integers, prescribe them. Choose many disjoint sets of
primes, each set of primes of comparable size, spread over many
logarithmic scales from exp(L^a) up to exp(L^d) with d < 0.47. A
"candidate" u is a product of one prime from each set, times some
auxiliary factors. Every such u is then exp(L^d)-smooth by construction,
and exp(L^d) < x^delta once x is large, since d < 0.47 < 1. This is
sections 10.1 and 11.1.
Each candidate set contributes of order x/L integers, which is far more
than the x^(1-o(1)) we need. So we can afford to throw away all but a
vanishing proportion.
THE SECOND MOVE: SIEVE OUT COMPOSITE 2u+1. The question "is 2u+1 prime"
is attacked by a sieve on the small prime divisors of 2u+1. Removing all
u for which 2u+1 has an odd prime divisor at most z leaves mass
sum_u A(u) prod_{3 <= p <= z} (1 - 1_{p | 2u+1}), (3.1)
and the classical sieve evaluation gives this mass as (main term) times
prod_{3<=p<=z}(1 - 1/(p-1)) plus an error, which is the same as a
constant times 1/log z. The factor 1/L is exactly what the candidate set
can afford; it is why the estimates of section 10 must save logarithms
and not just be bounded.
A sieve by itself proves nothing: the main term of the linear sieve is
only an UPPER bound for the number of primes, and being off by a constant
matters. There are three separate obstructions, and the paper handles
each with a different tool.
OBSTRUCTION 1: the sieve error must be controlled for every residue
pattern, i.e. we need the number of u with 2u+1 in a given residue class
mod d to be the expected one, for all d up to the sieve level. This is
TYPE I, Proposition 10.2, and it is classical: characters, the large
sieve, and Siegel-Walfitz.
OBSTRUCTION 2: after the small primes are removed, the survivors with
2u+1 composite must be removed too. The products that remain have at
most two large prime factors, and the unbalanced ones (one factor at most
x^(1/2-kappa), the other close to x) are exactly what a bilinear (TYPE II)
estimate kills. That is section 9. The estimate says
sum_{mn = 2u+1, m in U, n in V} A(u) alpha_m beta_n << x L^(-D) (3.2)
with m an arbitrary W-rough sequence and n arbitrary, provided alpha
satisfies an equidistribution (discrepancy) condition. Everything is
needed: A(u) has many prime factors, so the coefficient of m is far from
a nice function.
OBSTRUCTION 3: the balanced products, with both prime factors near
x^(1/2), are invisible to Type II, whose ranges exclude that window. They
are removed by a separate two-variable sieve (section 10.4). Its main
term has a constant that must not depend on the small parameter kappa of
the unbalanced range, which is why it is a separate argument.
WHERE THE WEIGHTED DILATION GRAPH COMES FROM. To prove (3.2), Cauchy-
Schwarz in (e,n) (section 9.4) turns it into a sum over pairs of
factorizations with the same n, and subtracting the two equations forces
m' - m = 2 e k, h' - h = k n, z = m' h, z + k = m h' (3.3)
for a small nonzero integer k (section 9.5). So the Type II sum becomes a
CORRELATION of two endpoint sequences at a small shift k.
Now the difficulty is visible. A correlation like
sum_z Psi(z/Z)/z * conj(F_0(z)) * G_0(z+k) * W(z) * W(z+k) (3.4)
would be easy if the weight W carried no information about prime
divisors. But W(z) counts the marked prime divisors of z, and W(z+k)
counts those of z+k. A prime dividing both z and z+k divides k, so the
two ends are correlated through the divisors of k, and Cauchy-Schwarz
cannot see this. The graph formalism models exactly this: a VERTEX is a
pair (integer, ordered list of marked prime divisors), an EDGE moves by
kD where D is the product of the labels shared by its two ends, and the
labels are required to DIVIDE the integers at their vertices.
The rest is a comparison. In an IDEALIZED graph the labels do not have
to divide anything, so the two ends are independent and the operator norm
is a small power of L (section 7). Transference (section 6) shows that
the physical graph and the ideal graph have asymptotically the same
moments, at the price of enlarging the gap between consecutive vertices
into a memory. Averaging a divisibility requirement over the vertex
supplies the factor 1/p that is the ideal label law, and the memory makes
each prime pay that factor only once, no matter how many visits use it.
THE ORDER OF THE REST.
section 4: the elementary lemmas (PNT, Mertens, Siegel-Walfitz, large
sieve, divisor moments, mean squares, van der Corput,
Fourier separation, the block sieve).
section 5: the graph, the physical and ideal operators, and the two
theorems that connect them.
section 6: transference, Theorem 5.2.
section 7: the ideal norm bound, Theorem 7.1.
section 8: the shift cancellation, Theorem 8.1.
section 9: Type II, Theorem 9.1.
section 10: the weight, Type I, the presieve, proxies, the two sieve
regimes.
section 11: Theorem B.
section 12: Theorem A.
section 13: a table of where each hypothesis is used.
The dependencies are one-way: theorem numbers increase along the chain
the result is used in. The only apparent exception is that the geometric
data of section 5 must be fixed before the estimates of sections 6 to 9,
and it is.
4. TOOLKIT
Everything in this section is classical. Each item is stated in the exact
form used later, because the form matters: several of them are applied on
very short intervals, or to integers rather than to primes.
Notation for this section. p is always a prime. e(t) = exp(2 pi i t).
mu is the Moebius function: 0 if a prime square divides n, and (-1)^r if
n is a product of r distinct primes. tau is the divisor function. Sums
and products indexed by p run over primes. gamma_E is Euler's constant.
4.1 PRIMES.
(a) PRIME NUMBER THEOREM with a good error:
pi(y) = Li(y) + O(y (log y)^(-A)) for every fixed A > 0,
Li(y) = (y/log y)(1 + O(1/log y)). (4.1)
The constant is ineffective; only existence of a bound is used.
Two consequences used without comment, both immediate from (4.1) by
splitting into prime powers and summing by parts.
- The number of primes in [Y, e^h Y] equals (e^h - 1) Y/log Y times
(1 + o(1)), uniformly for h >= 1/log Y and Y large.
- The reciprocal-prime mass of an interval of logarithmic length h at
height Y equals h(1 + o(1)), again uniformly.
(b) MERTENS' ESTIMATES:
sum_{p <= y} 1/p = log log y + O(1),
prod_{p <= y} (1 - 1/p) ~ exp(-gamma_E)/log y. (4.2)
(c) SIEGEL-WALFITZ. For fixed A, C > 0, uniformly for (a,r) = 1 and
1 <= r <= (log y)^C,
#{ p <= y : p = a mod r } = Li(y)/phi(r) + O_{A,C}(y (log y)^(-A)). (4.3)
The constants are ineffective.
(d) HARMONIC CHARACTER ESTIMATES. We need absolute character cancellation
on very short intervals, and this is what (4.3) supplies.
COROLLARY. Fix c, C, B, A > 0. Let chi be a nonprincipal character
modulo r <= L^B. Then, uniformly for real |t| <= L^B and for intervals
I contained in [exp(L^c), x^C],
sum_{p in I} chi(p) p^(it)/p <<_{c,C,B,A} L^(-A). (4.4)
PROOF. Let A_chi(y) = sum_{p <= y} chi(p). Summing (4.3) against chi
over reduced residue classes, the main terms cancel, and the number of
classes costs at most L^B. Since log y >= L^c, the admissible moduli
r <= L^B are at most a fixed power of log y. Hence A_chi(y) <<_K
L^B y (log y)^(-K) for every fixed K. Partial summation on I = (a,b]
against y^(-1+it) gives boundary terms of size O_K(L^B (log a)^(-K)) and
an integral bounded by
C_K L^B (1 + |t|) int_a^b dy/(y (log y)^K) <<_K L^(2B) (log a)^(1-K). (4.5)
Take K large. The argument is uniform in both endpoints, covers an empty
interval, and covers a nonprincipal character induced from a smaller
modulus, which is itself nonprincipal on the modulus on which it is used.
[End]
What this does and does not give. It gives absolute cancellation, for a
single nonprincipal twist, uniformly on arbitrarily short subintervals of
[exp(L^c), x^C]. It does NOT give a relative asymptotic on every short
interval. That is exactly what is needed when one label of a marked list
varies and the others are frozen.
(e) MULTIPLICATIVE LARGE SIEVE. Let I be a real interval of length H, let
a_n be complex numbers supported on I intersect Z, and let R >= 1. Then
sum_{r <= R} (r/phi(r)) sum_{chi mod r}^* | sum_{n in I} a_n chi(n) |^2
<< (H + 1 + R^2) sum_n |a_n|^2, (4.6)
the star restricting to primitive characters.
4.2 DIVISOR MOMENTS.
LEMMA 4.1. For each fixed nonnegative integer k there is C_k with
sum_{n <= Y} tau(n)^k / n <<_k (log(2Y))^(C_k),
sum_{n <= Y} tau(n)^k <<_k Y (log(2Y))^(C_k). (4.7)
Consequently a convolution of a fixed number b of sequences, each bounded
by a fixed power of L, has coefficient-square sum U L^O(1) on a dyad of
size U <= x^O(1); and if the coefficients include the reciprocal of the
product index, the bound is L^O(1)/U instead.
PROOF. Positivity and unique factorization bound the harmonic sum by
prod_{p <= Y} sum_{a>=0} (a+1)^k p^(-a)
= prod_{p <= Y} (1 + 2^k/p + O_k(p^(-2))) <<_k (log(2Y))^(C_k), (4.8)
using Mertens. The counting bound is the harmonic one times Y. For the
convolution: the coefficient at n is at most a fixed log power times the
number of ordered b-factorizations of n, and the last factor is determined
by the first b-1, so that number is at most tau(n)^(b-1). Apply the
counting bound with k = 2(b-1). On a dyad the reciprocal index is
comparable to 1/U. [End]
4.3 TWO POLYNOMIAL ESTIMATES.
LEMMA 4.2 (mean squares). Let P(t) = sum_{n <= Y} c_n n^(it), and let I
be an interval of length H. Then
int_I |P(t)|^2 dt << (H + Y log(2Y)) sum_n |c_n|^2. (4.9)
For a set T of real points at mutual distance at least one, inside an
interval of length H,
sum_{t in T} |P(t)|^2 << (H + 1 + Y log(2Y)) (log(2Y))^2 sum_n |c_n|^2. (4.10)
The constants are absolute: no factorization of the coefficients enters.
PROOF. Integration gives the diagonal H sum_n |c_n|^2. For n != m the
exponential integral is at most 2/|log(n/m)| << Y/|n-m|. Use
2|c_n c_m| <= |c_n|^2 + |c_m|^2 and sum 1/|n-m|. For the discrete form
use the one-dimensional Sobolev inequality on unit intervals: |P(t)|^2 is
bounded by a constant times the integral of |P|^2 + |P'|^2 over that unit
interval, and unit intervals overlap boundedly. The derivative has
coefficients i (log n) c_n, so apply the first bound twice. [End]
LEMMA 4.3 (derivative tests; van der Corput). Let f be real-valued on an
interval of H consecutive integers.
(a) If f' is monotone and stays in [j + lam, j + 1 - lam] for an integer
j and 0 < lam <= 1/2, then |sum_n e(f(n))| << 1/lam.
(b) If f is twice differentiable with lam <= |f''| <= C lam on the whole
interval, then |sum_n e(f(n))| <<_C H lam^(1/2) + lam^(-1/2). (4.11)
Both hold on every subinterval where the hypotheses hold.
We also use the differencing form of (b). If the k-th derivative of f has
constant sign and magnitude comparable to lam_k on an interval of length
N, then differencing k-2 times, with positive integer shifts at most H_0,
gives a normalized bound of the shape
B^2 << H_0^(-1) + B_(k+1), (4.12)
where B_(k+1) controls the differenced sum, and the differenced phase has
second derivative of size lam_k H_0^(k-2) on an interval which is again an
interval. (The inequality follows by averaging H_0 translates and
applying Cauchy-Schwarz; its zero-shift term is precisely the displayed
H_0^(-1).)
4.4 SEPARATING VARIABLES.
LEMMA 4.4 (Fourier separation). Let F be smooth with support in a fixed
bounded box in R^b, b fixed, and suppose every derivative of order j is
bounded by C_j L^(C(j+1)). Then Fourier inversion writes F as a
superposition of products of one-variable phases with integrated absolute
coefficient mass L^O(1). There is a fixed C', depending only on b and C,
such that restricting every frequency to |xi| <= L^(C') loses at most
O_A(L^(-A)) for every fixed A, and C' may be fixed before A.
PROOF. Repeated integration by parts bounds the Fourier transform by a
derivative norm times an arbitrary fixed negative power of 1+|xi|. Taking
more than b derivatives first makes the bound integrable with a fixed power
of L. For the tail, take j > b derivatives and integrate outside
|xi| >= L^(C'): the bound is a constant times L^(C(j+1) - C'(j-b)). Fix
C' > C large enough, then increase j to get any prescribed negative power
of L. [End]
This lemma turns a smooth cutoff in a product of variables into a sum of
monomials in those variables, at a cost of a fixed log power. Applied in
logarithmic coordinates on a short dyad it becomes a Mellin separation.
4.5 THE BLOCK SIEVE.
This is the one elementary sieve used everywhere: it replaces a rough
indicator by a polynomial with small coefficients and controlled level.
The framework. There are OBJECTS, each carrying a weight. Each object
may satisfy or fail a BAD CONDITION, and the bad conditions are indexed
by primes p <= z. Write
X = total weight of all objects,
S = total weight of the objects that fail no bad condition,
r(d) = (total weight of objects failing, for every p | d, the bad
condition at p) - X prod_{p | d} g(p), (4.13)
for odd squarefree d supported on the primes p <= z. The numbers g(p) in
[0,1] are the "densities" of the bad conditions.
HYPOTHESES. There are fixed eta_0 > 0 and C with
0 <= g(p) <= 1 - eta_0, sum_{w < p <= w^2} g(p) <= C (w > 1). (4.14)
LEMMA 4.5 (block sieve). For every sufficiently large even integer h the
weight of the objects that fail no bad condition satisfies
S = X prod_{p <= z} (1 - g(p)) (1 + O(e^(-h)))
+ O( sum_{d <= z^(4h+2)} |r(d)| ). (4.15)
The implied constants depend on eta_0 and C, uniformly also when h grows.
Only the indicated primes and their squarefree products are used.
More precisely, the proof produces polynomials U, V in the indicators of
the bad conditions with
V <= indicator{no bad condition} <= U, U >= 0, (4.16)
both having coefficients of absolute value at most one and both supported
on squarefree d <= z^(4h+2). The nonnegative overcount
U - indicator{no bad condition} is dominated pointwise by U - V, whose
absolute coefficients are also at most one and which obeys the same level
bound. For the fixed even choice h = 2 there is an upper bound by a
constant times X prod_{p<=z}(1 - g(p)) plus the same remainder sum.
PROOF.
Step 1: blocks. Partition the indicated primes by size:
B_j = { p : z^(2^(-j-1)) < p <= z^(2^(-j)) }, j >= 0. (4.17)
Only finitely many blocks are nonempty. The point of the partition is
that block j contains at most z^(2^(-j)) primes, so a polynomial of degree
h_j in block j costs only z^(h_j 2^(-j)) of level. Set h_j = (j+1)h,
which is even.
Step 2: local polynomials. Let I_j be the indicator of "fails no bad
condition of block j". Let U_j be the inclusion-exclusion polynomial
through degree h_j,
U_j = sum_{a=0}^{h_j} (-1)^a sum over a-subsets T of the block of
the product of the indicators in T,
and let E_j be the sum of ALL monomials of degree exactly h_j+1 in the
indicators of block j. If exactly t bad conditions hold in the block,
then the binomial theorem gives
U_j = sum_{a=0}^{h_j} (-1)^a binom(t,a)
= 1 if t = 0,
= binom(t-1, h_j) if t >= 1, (4.18)
where a binomial coefficient is zero when its lower index exceeds its
nonnegative upper index. Therefore
U_j >= I_j >= 0, U_j - I_j <= E_j. (4.19)
Step 3: telescoping. For nonnegative factors,
0 <= prod_j U_j - prod_j I_j
<= sum_j E_j prod_{k != j} U_k, (4.20)
because prod U_j - prod I_j = sum_j (U_j - I_j) prod_{k<j} I_k prod_{k>j}
U_k, and each term is bounded using (4.19) together with I_k <= U_k. Take
U = prod_j U_j, V = U - sum_j E_j prod_{k != j} U_k. (4.21)
Step 4: coefficients and level. In U, block j contributes degree at most
h_j. A correction term with index j has degree exactly h_j+1 in block j
and at most h_k in block k != j. These supports are disjoint across j and
disjoint from the support of U. Hence every coefficient of U, of V, and
of U - V is an integer of absolute value at most one: the sign is a
product of signs and no monomial occurs twice.
For the level: the logarithm, divided by log z, of a product of monomials
in U is at most
sum_{j>=0} h(j+1) 2^(-j) = 4h. (4.22)
A correction adds at most one more unit, i.e. one extra factor of at most
z. So every monomial in use divides a squarefree d <= z^(4h+2).
Step 5: evaluate the polynomials probabilistically. Give the bad
conditions independent probabilities g(p) and let E denote expectation.
For a block put
a_j = E I_j = prod_{p in B_j} (1 - g(p)),
e_j = E E_j <= ( sum_{p in B_j} g(p) )^(h_j+1) / (h_j+1)!
<= C^(h_j+1) / (h_j+1)!, (4.23)
using positivity of the monomial coefficients for the first inequality,
and (4.14) for the second: a block is contained in (w, w^2] for w equal to
its left endpoint, so the sum of g over the block is at most C. Also
a_j >= exp(-C/eta_0) =: a_* > 0, (4.24)
because -log(1-u) <= u/eta_0 for 0 <= u <= 1 - eta_0 and the block has at
most C total density.
The block avoidance probability and the correction mass are therefore
a_j = prod(1 - g(p)) over the block, e_j <= C^(h_j+1)/(h_j+1)!. (4.25)
Now E U = prod_j a_j and E(negative part of E_j) >= -e_j, so the total
mass of the corrections is at most
sum_j e_j prod_{k != j} a_k
<= ( prod_j a_j ) sum_j C^(h_j+1) / ((h_j+1)! a_*), (4.26)
and the sum is at most e^(-h) for h large, uniformly in the number of
blocks, because h_j = (j+1)h makes each factorial huge compared with the
corresponding power of C. This is the displayed O(e^(-h)).
Finally, the contribution of a monomial with support d, evaluated on the
objects, differs from its expected value by definition by r(d), and the
sum of the absolute values over all monomials is bounded by (4.15). [End]
COROLLARY 4.6 (rough polynomial). Let z >= 2 and let h be a sufficiently
large even integer. Put D = z^(4h+2). There is a polynomial
U(n) = sum_{d | n} lambda_d, |lambda_d| <= 1, (4.27)
supported on squarefree d <= D whose prime factors are at most z, such
that
U(n) >= indicator{ P^-(n) > z } for every n, U(n) >= 0, (4.28)
and for every Y,
sum_{n <= Y} ( U(n) - indicator{ P^-(n) > z } )
<< Y e^(-h) prod_{p <= z} (1 - 1/p) + D. (4.29)
The summand in (4.29) is nonnegative, so restricting to any subset of
[1,Y] preserves the bound. Moreover
sum_d |lambda_d| / d <= prod_{p <= z} (1 + 1/p) << log(2z). (4.30)
PROOF. Apply (4.16) to the framework in which the objects are the
integers n <= Y with weight 1, and the bad condition at p is p | n. Then
g(p) = 1/p and (4.14) holds with eta_0 = 1/2 and C = 1, since the sum of
1/p over (w,w^2] is log log(w^2)/log log w = 1 + o(1) <= 1 for large w,
and it is bounded by an absolute constant for all w > 1. The polynomial U
of (4.16) is nonnegative with absolute coefficients at most one and has
support on squarefree d <= z^(4h+2); it majorizes the indicator pointwise.
Its independent expectation was bounded in the proof of Lemma 4.5 by
O(e^(-h)) prod_{p<=z}(1 - 1/p), and the sum of absolute remainders is
O(D). Dropping the avoidance product proves (4.29). Finally
prod_{p<=z}(1 + 1/p) <= prod_{p<=z}(1 - 1/p)^(-1) << log(2z) by Mertens.
[End]
This corollary is why the rest of the file may speak of "the rough
polynomial" as though it were the rough indicator: it agrees with the
indicator on average, it is nonnegative, its coefficient l1 norm is only
log(2z), and its level D is x^o(1) when z = exp(O(sqrt L log L)), which is
exactly the range used for the long rough factor of section 8.3.
5. THE WEIGHTED DILATION GRAPH
Sections 5 to 9 prove one estimate, the shift cancellation of Theorem 8.1,
which is the analytic input to Type II in section 9, which drives the
sieve in section 10. Everything here serves that estimate.
Why a graph. In a correlation such as (3.4), a prime may divide both z
and z+k, hence must divide k, so the two ends are not independent and
Cauchy-Schwarz cannot see the dependence. Modelling marked prime
divisors as LABELS CARRIED BY VERTICES makes the dependence explicit: an
edge moves from n to n+kD, where D is the product of the labels shared by
its two ends, and labels must divide the integers at their vertices. The
graph is combinatorial; analysis enters when its moments are compared
with those of an idealised graph whose labels divide nothing.
5.1 FIXED DATA.
Fix constants
0 < a < b < c < d < 0.47, c_0, C_0, v_-, v_+ > 0,
0 < q < 1, ell a positive integer. (5.1)
For each sufficiently large x let P_g be pairwise disjoint finite sets of
primes, indexed by the disjoint union of a set S (small) and a set B
(big), such that
c_0 T <= |S|, |B| <= C_0 T, (5.2)
and, uniformly, each P_g is the set of primes of an interval with
exp(L^a) <= p <= exp(L^b) for p in P_g, g in S,
exp(L^c) <= p <= exp(L^d) for p in P_g, g in B, (5.3)
v_- <= V_g := sum_{p in P_g} 1/p <= v_+, mu_g(p) := 1/(V_g p).
Write s = |S| + |B|, P = union of all P_g, and
omega_g(n) = #{ p in P_g : p | n }, omega(n) = sum_g omega_g(n).
So omega_g counts distinct prime divisors from one group, without
multiplicity, and omega counts them over all groups. Divisibility at
n = 0 has its usual meaning. Write n_* for the part of n supported
outside P.
Each mu_g is a probability measure on P_g, since the masses 1/(V_g p) sum
to V_g/V_g = 1. It is the law of a uniformly random prime divisor of a
random integer, because a prime p divides a random integer with
probability 1/p. This measure is the heart of the idealisation.
The reason for two sizes of groups is in section 6.5: the small groups
supply many independent chances to "omit a label", and the big groups
supply intervals long enough for character sums.
5.2 MARKED LISTS, PATTERNS, AND THE EDGE PRODUCT D.
Let J be a large fixed integer and put M = J + ell. An ORDERED LABEL
LIST has M slots in each group. A PATTERN nu assigns to each big group a
set C_g of at most m slots inside {1,...,J}, and C_g = empty for small g.
Here m is a fixed constant, chosen in section 7.6; J is chosen last, in
section 6.6. Put
c_g = |C_g|, t_g = ell + c_g, s_(R,g) = J - c_g, (5.4)
so c_g + s_(R,g) = J and s_(R,g) + t_g = M; the t_g slots of a pattern are
UNSHARED and the s_(R,g) slots are SHARED.
The edge product D is formed as follows: take the shared labels and, in
the C_g slots, independent labels with law mu_g. Then D has exactly J
prime factors from each group, hence Js factors in total. Because the
groups are disjoint and each c_g <= m, J and C_0 bound the size,
D <= exp( J sum_g (log of largest prime in P_g) ) = exp(O_J(T L^d)),
D >= exp( J s L^c / 2 ), (5.5)
and hence D = x^o(1) but D exceeds every fixed power of L: the facts used
in sections 7 to 9.
For each pattern there is a complex coefficient K_nu, depending only on
the ordered BIG-group source labels, the ordered big-group target labels,
and the auxiliary free labels used in D. The finite pattern family may
depend on x and on J, but
sum_nu sup |K_nu| <= L^(C_1), (5.6)
where m and C_1 are fixed independently of J. In every operator below,
"symmetrisation" means averaging all M! slot permutations independently in
each relevant group; this is an orthogonal projection because the measures
are invariant under those permutations. A row operator integrates a
function at the target and returns a function at the source.
5.3 THE PHYSICAL OPERATOR.
A PHYSICAL STATE is a pair (n, (p_(g,i))) in which n is an integer and
(p_(g,i)), 1 <= i <= M, are labels such that within each group the labels
are DISTINCT and DIVIDE n. Give every state at n the mass
prod_g V_g^(-M), (5.7)
use counting measure in n, and call the resulting Hilbert space H_ph.
Fix an integer k with 0 < |k| <= L^(C_2). For a pattern nu, sample the
auxiliary labels forming D as above and move from n to n' = n + kD. Then
sum over physical target states at n' whose shared slots carry the
prescribed shared labels, with coefficient prod_g V_g^(-t_g) per target.
Forbid every auxiliary free label of D from both endpoint lists;
auxiliary free labels may equal one another. Multiply the row action by
K_nu * D^(i zeta) * q^((omega(n) - Ms)/2) * q^((omega(n') - Ms)/2). (5.8)
Summing over patterns and symmetrising in all groups on both sides gives
an operator A on H_ph. The factors q^((omega - Ms)/2) are DAMPING: they
punish endpoints carrying more group-prime divisors than the M slots
actually need, which is what makes the absolute bounds of 5.5 uniform in
the number of slots.
The ADJOINT of A moves by -kD, interchanges source and target labels
inside the coefficient, and conjugates the multiplier. This is exact:
after both lists and the auxiliary labels are fixed the shared product,
hence D, is unchanged on reversal, and the joint measure of the two lists
in group g is
V_g^(-M-t_g) (5.9)
in either direction. The auxiliary-label probability is also unchanged.
So the reversal identity holds before symmetrisation, and
symmetrisations are self-adjoint.
5.4 THE IDEAL OPERATOR.
An IDEAL STATE is a pair (position, ordered label lists) with NO
divisibility requirement; the labels in group g are drawn independently
with law mu_g, so the measure of a list is prod_g V_g^(-M) prod_i
mu_g(p_(g,i)) times permutations, i.e. the symmetrised product measure.
Call the resulting Hilbert space H_id.
The ideal row action for a pattern nu is: retain the shared labels,
sample every unshared target label independently with law mu_g, sample the
auxiliary labels of D_B (the free part of D) independently with the same
law, and multiply by
K_nu * D_B^(i zeta) * e( Theta D_B ), (5.10)
where zeta is a real Mellin exponent, bounded by a fixed power of L
(section 8.3), and Theta is a real frequency. The shared product D_S is
common to both endpoints, so it is absorbed into the translation from n to
n'; only the free product D_B carries the twist. Summing over patterns,
composed on both sides with big-group symmetrisation, gives T(Theta),
acting on H_id.
5.5 THE ABSOLUTE BOUND.
LEMMA 5.1 (absolute physical bounds). Replace the coefficients of every
row transition of A by their absolute values before adding patterns or
averaging permutations. The resulting operator and its adjoint have row
sums at most L^(C_abs), where C_abs may depend on m, C_1 and the fixed data
of 5.1, but NOT on J. The same holds if the position is replaced by
independent uniform residues at all group primes.
PROOF. Suppose the target has y >= M divisors from group g. After the
s_(R,g) distinct shared labels are fixed, there are (y - t_g)_(t_g)
possible ordered unshared target lists, where (z)_j = z(z-1)...(z-j+1).
Their total, with endpoint damping, is at most
sup_{z >= 0} V_g^(-t_g) (z + t_g)_(t_g) q^(z/2) <= C, (5.11)
a constant, because t_g <= ell + m and the supremum is attained at
z = O(t_g/(1-q)): the falling factorial grows like z^(t_g) while the
damping decays geometrically. The source damping is at most one,
free-label probabilities have total mass one, and imposing restrictions
can only decrease an absolute sum. Take the product over the s = O(T)
groups and use (5.6) for the pattern mass. The reversed normalisation
(5.9) gives the identical argument for columns, and neither argument used
anything about integer positions beyond divisibility and translation.
[End]
So all these operators are bounded on their stated spaces, including the
physical space with unrestricted integer position. This is the only place
where the damping q enters quantitatively.
5.6 THE TWO THEOREMS CONNECTING THE GRAPHS.
THEOREM 5.2 (local transference). For every fixed E > 0 there is E_id > 0,
depending only on E and the fixed data of 5.1, with the following property.
Assume
sup_{Theta in R} || T(Theta) || <= L^(-E_id). (5.12)
Then, for every sufficiently large fixed J (how large may also depend on m
and C_1), put
R = ceil(L^(0.52)), N = 2R. (5.13)
For every fixed gamma > 0 and every I = [X,2X) with
x^gamma <= X <= x^(1/gamma),
(1/|I cap Z|) sum_{n in I cap Z} < u_n, (A A*)^R u_n > <= L^(-E N), (5.14)
where u_n is the vector equal to one on every physical state at position n
and zero elsewhere. The bound is uniform in I.
The exponent E_id depends on E but not on J or on the probe count m of
section 7; that is what makes the order of choices in section 8.10
non-circular. The proof occupies section 6.
COROLLARY 5.3 (endpoint pairing). Under the same hypotheses, let f in
H_ph be supported on positions I = [X,2X) and independent of the chosen
marks, with value f_n at position n. Suppose
sup_{n in I} |f_n| <= exp(O(sqrt L)), ||f||, ||g|| <= X^(1/2) L^(C_3). (5.15)
Then
| < f, A g > | << X L^(-E + 2 C_3). (5.16)
Only the FIRST endpoint has to be independent of its mark list.
PROOF. Let H >= 1 bound every displacement |kD|. Since D has Js
factors, each at most exp(L^d),
log H = O_J(T L^d). (5.17)
Partition I into consecutive intervals I_j of length ceil(H), except
possibly the last. Put f_j = 1_(I_j) f and let g_j be g restricted to the
H-neighbourhood of I_j. Those neighbourhoods have bounded overlap, so
< f, A g > = sum_j < f_j, A g_j >, sum_j ||g_j||^2 << ||g||^2. (5.18)
Let B_0 = A A* >= 0. Interpolation between the second and the 2R-th power
gives, for the exponent R of the theorem,
| < f_j, A g_j > | <= ||g_j|| ||f_j||^(1 - 1/R)
< f_j, B_0^R f_j >^(1/(2R)). (5.19)
The finite matrix ( < u_n, B_0^R u_m > )_(n,m in I_j cap Z) is positive
semidefinite, so its largest eigenvalue is at most its trace; since f is
mark independent,
< f_j, B_0^R f_j > <= ( sum_{n in I_j cap Z} |f_n|^2 ) d_j,
d_j := sum_{n in I_j cap Z} < u_n, B_0^R u_n >. (5.20)
There is no assertion here that the u_n have equal norm, nor that ordered
lists return to their starting values. By (5.17),
( O(H) sup |f_n|^2 )^(1/(2R))
= exp( O_J( (T L^d + sqrt L)/L^(0.52) ) ) = O(1), (5.21)
because T L^d is a fixed power of log L while L^(0.52) is a power of L.
Sum the block bounds by Holder with the three exponents 2, 2R/(R-1) and
2R, applied to ||g_j||, ||f_j||^(1-1/R) and d_j^(1/(2R)). This gives
| < f, A g > | << ||g|| ||f||^(1 - 1/R) ( sum_j d_j )^(1/(2R)), (5.22)
and the theorem bounds the last sum by |I cap Z| L^(-2RE) << X L^(-2RE).
Substituting (5.15) proves (5.16), since ||f||^(1-1/R) X^(1/(2R)) <=
X^(1/2) L^(C_3) for fixed C_3. [End]
What (5.16) costs and does not cost. Holder alone would give
| < f, A g > | <= (sup |f|) ||g|| times the norm of A, which is at best a
polylogarithm; against X^(1/2) L^(C_3) that is no saving in a power of X.
Bound (5.16) instead saves a full X^(1/2) L^(-E + C_3). That power of X is
what the correlation sum of section 8 needs, and it is available for every
fixed E, which is why E is left free here and only E_id is chosen.
6. TRANSFERENCE: FROM THE PHYSICAL GRAPH TO INDEPENDENT LABELS
This section proves Theorem 5.2. The hypothesis is the ideal norm bound
(5.12); the conclusion is the physical moment bound (5.14). The two
graphs differ in exactly one respect: in the physical graph a label must
DIVIDE the integer at its vertex, in the ideal graph it must not.
Averaging a required divisibility condition p | n over n supplies a factor
1/p, which is precisely the ideal law mu_g. The difficulty is that a prime
used at several visits must pay that factor only once, not once per visit.
6.1 THE PLAN, IN ORDER, AND WHY IN THAT ORDER.
Step 1 (6.2). Replace the integer root n by independent uniform
residues modulo every group prime. Legal because the modulus of all the
congruences together is small compared with the length of the interval.
Step 2 (6.3). For each big prime, expand its contribution exactly into
LIFESPANS: maximal runs of visits on which the prime is required to be
congruent to a fixed residue, with a single charge 1/(p b_p) at birth.
This is the step that makes a prime pay only once.
Step 3 (6.3). Build a Hilbert space with a MEMORY per big group, whose
coordinates record, for each prime currently out of use, the residue it
must hit when it was last used. A prime divides the integer at a visit
exactly when the memory entry translates to zero.
Step 4 (6.4). Prove absolute bounds: row and column sums of every
operation are at most a fixed power of L, independent of J. Then the
memory may be truncated at size L^2 with negligible loss.
Step 5 (6.5). Split each edge into CLEAN terms (no memory used) and
DIRTY terms (a store or a promotion). Dirty terms are killed by
averaging the omitted labels of the SMALL groups: the gain is a factor
exp(-(c_0/2) log binom(J+ell,ell)), which can be made arbitrarily large
by taking J large, and J is chosen last.
Step 6 (6.6). For clean terms, Fourier transform the residue
coordinates. Translation becomes a scalar and what remains is the ideal
operator T(Theta). Two small changes appear, the measure mu_g becoming
mu~_g and the free/active collision ban having to be removed, and both
are negligible in operator norm.
Step 7 (6.7). Restore the rule "distinct prime values at different
births", which steps 1 to 6 dropped. This is done by expanding the rule
into equality conditions between births, ordered by RANK. Large rank
costs many point masses exp(-L^c) each; small rank affects only o(N)
edges, which leaves the per-edge contraction intact.
6.2 REPLACING THE ROOT BY INDEPENDENT RESIDUES.
Expand the left side of (5.14) into paths with N alternating forward and
backward edges. Fix the patterns, all endpoint permutations, the
auxiliary labels, and the active lists at the visits 0,1,...,N. These
choices fix offsets
h_0 = 0, h_1, ..., h_N, h_(i+1) - h_i = sigma_i k D_i,
sigma_i in {+1,-1}, h_N = 0. (6.1)
Only the return of the POSITION is imposed; the final ordered list need
not equal the first one. Let Lambda_i be the set of active labels at visit
i; these are the labels that must divide the integer at that visit. Put
q_0 = q_N = sqrt(q), q_i = q for 0 < i < N. (6.2)
Then the entire dependence on the initial integer n is the nonnegative
factor
F(n) = prod_{i=0}^{N} ( prod_{p in Lambda_i} 1_{ n + h_i = 0 mod p } )
prod_{i=0}^{N} q_i^( # { p in P : p not in Lambda_i,
n + h_i = 0 mod p } ). (6.3)
All other factors in the path are independent of n.
LEMMA 6.1 (uniform residue replacement). For each compatible fixed path
and every fixed A > 0, the average of (6.3) over I cap Z equals its
expectation under INDEPENDENT UNIFORM RESIDUES at all group primes,
multiplied by 1 + O(exp(-A N T)). Incompatible active congruences give
zero in both models.
PROOF. Let Q_act be the product of the distinct primes occurring in the
active lists. There are at most (N+1) M s of them, so
log Q_act <= O_J( N T L^d ) = L^(0.52 + d + o(1)) = o(L), (6.4)
using d < 0.47 and N = O(L^(0.52)).
If two active congruences for the same prime are incompatible, both sides
vanish. Otherwise the active conditions fix one residue class modulo
Q_act, and |I cap Z| / Q_act counts the integers of that class in I up to
an error of at most one, so an error of relative size O(Q_act/|I|) <=
exp(-gamma L + o(L)).
For the remaining primes the factor (6.3) is a product of local factors.
For a prime p not in Q_act, let T_p be the set of visits i with p not in
Lambda_i and, at those visits only, put
X_p(n) = sum_{i in T_p} (1 - q_i) 1_{ n = -h_i mod p }, (6.5)
a sum over the visits in T_p of the indicators of the events
n = -h_i mod p; note 0 <= X_p <= N+1. The local factor is the product
prod_{i in T_p} (1 - (1-q_i) 1_{n = -h_i mod p}), to be expanded by
inclusion-exclusion. The
number of visits in T_p is at most N+1, so the number of distinct residue
classes involved is at most N+1, and
lambda := sum_p E X_p <= (N+1) sum_{p in P} 1/p <= (N+1) s v_+
= O_J(N T). (6.6)
Truncating the product at order h = floor(2 lambda): the product of the
local expectations is prod_p (1 - E X_p) >= exp(-lambda) >= exp(-O(NT)),
and the discarded tail has mass at most exp(-h) <= exp(-NT).
Each retained term of the truncation specifies one residue class at at
most h primes, hence a modulus
<= Q_act * prod of h primes <= exp( o(L) + h O(L^d) ), (6.7)
which is exp(o(L)), and the number of retained terms is at most the number
of subsets, exp(O(h (log s + L^d + log N))) = exp(o(L)). By the Chinese
remainder theorem and (6.4), the average over I of each retained term
agrees with its independent expectation up to O(exp(o(L))/|I|) <=
exp(-gamma L/2 + o(L)), which is negligible against exp(-NT).
Summing over paths with absolute coefficients: the initial factorial mass
is at most one, and the absolute mass of all length-N paths is L^(O(N)) by
Lemma 5.1. So the accumulated error is smaller than L^(-A'N) for every
fixed A', which after relabelling is the assertion. The return condition
h_N = 0 is imposed by the factor int_0^1 e(theta h_N) d theta, which is
harmless throughout. [End]
Consequently, uniformly in theta, we may replace the physical root by
independent residues modulo every group prime. The SMALL-group residues
stay genuine Haar coordinates throughout; only the big primes receive the
memory treatment of the next subsection.
6.3 THE EXACT EXPANSION FOR ONE BIG PRIME, AND THE MEMORY.
Put eta_i = 1 - q_i, P_* = exp(L^c) (the smallest big prime, up to
X^o(1)), and for each big prime
b_p = 1 - (1/p) sum_{i=0}^{N} eta_i > 0,
mu~_g(p) = 1/(V_g p b_p). (6.8)
The ratio mu~_g(p)/mu_g(p) is 1 + O(N/P_*), uniformly in the big groups,
because p >= P_*. Extract the common baseline prod_{p big} b_p <= 1 from
every path sum; what remains is a sum in which each big prime pays its full
reciprocal-prime factor exactly once.
CASE 1: p is active at some visits. Incompatible active offsets give
zero. Otherwise let their common residue be c_p, let a_p and z_p be the
first and last active visits, and put H_i = 1_{ h_i = c_p mod p }. The
residue expectation of the prime's factor from (6.3) is
(1/p) prod_{i : p not in Lambda_i} (1 - eta_i H_i). (6.9)
Two exact telescoping identities, obtained by subtracting consecutive
partial products, hold:
prod_{i < a_p} (1 - eta_i H_i)
= 1 - sum_{j < a_p} eta_j H_j prod_{j < i < a_p} (1 - eta_i H_i),
prod_{i > z_p} (1 - eta_i H_i)
= 1 - sum_{j > z_p} eta_j H_j prod_{z_p < i < j} (1 - eta_i H_i). (6.10)
Read together: the factor (6.9) equals (1/p) times a sum of terms indexed
by a BIRTH VISIT j <= a_p and a TERMINATION VISIT j' >= z_p. The term with
j = a_p and j' = z_p is "the prime was born at the start of its active run
and died at the end"; the other terms charge a factor -eta_j H_j at an
earlier birth and -eta_(j') H_(j') at a later termination, and are damped
by bounded factors.
CASE 2: p is active at no visit. Then (6.9) reads (1/p) prod_i
(1 - eta_i H_i), and the same telescoping identities apply with a_p and
z_p replaced by the first and last visit at which the prime is wanted. So
the prime is either never used, contributing probability 1 - O(N/p), or it
is born at an unmarked hit (factor -eta_j H_j) and dies at another
(-eta_(j') H_(j')).
Either way each big prime contributes exactly one charge 1/(p b_p), and
after dividing by V_g b_p that charge is the law mu~_g. The remaining
factors all have the shape prod (-eta_i/rho) and prod (q_i/rho^2) for a
constant rho chosen below. This is what "lifespan" means: a birth, a run
of visits on which the prime must be congruent to its birth residue, and a
termination.
THE MEMORY SPACE. To record the constraint that a prime out of use must
still hit its residue later, give each big group a memory space
F_g = { (phi, z) : phi : N -> P_g an injection with finite support }/,
(6.11)
that is, unordered finite lists of prime labels, each carrying the integer
RESIDUE it must hit. The space L^2(F_g) is taken with the measure
d lambda_g, which in memory coordinates ((p_h, r_h))_(h=1..j) is the
factorial (unordered) measure
d lambda_g = (1/j!) prod_{h=1}^{j} mu~_g(p_h) dr_h, (6.12)
with dr the counting measure on residues mod p_h. Counting measure is the
point: a required residue costs nothing.
The full space is
H = H_S tensor L^2( prod_{g in B} P_g^M , tensor_{g in B}
mu~_g^(tensor M) ) tensor tensor_{g in B} F_g. (6.13)
The boundary vector 1_empty is one when every memory is empty and zero
otherwise, and is independent of all other coordinates.
The factorial measure (6.12) is used for INNER PRODUCTS AND ADJOINTS, not
inserted anew in every row transition. All operations are first understood
on finite memory truncations; the absolute bounds of 6.4 justify the
unrestricted sums.
TWO KINDS OF OPERATION. Separate the path into an operation G_i AT each
visit 0 <= i <= N and an operation E_i ACROSS the following edge, for
i < N. G_i handles ghost endpoints and unmarked hits. E_i moves residues
and transfers particles between active lists and memory: a STORE keeps a
departing active label pending, a PROMOTION returns a pending particle to
an active slot. The operation G_i acts after arrival and promotion at
visit i and before storage and departure.
Choose rho in (0,1) with rho^2 > sqrt(q). At a strictly internal unmarked
hit, split the damping as
q_i = rho * (q_i/rho^2) * rho. (6.14)
The two adjacent edges supply the two factors rho, and the visit operation
supplies the middle factor q_i/rho^2 < 1, which damps the visit operation.
A ghost endpoint factor is split as -eta_i = (-eta_i/rho) * rho. These
local factorisations are what make BOTH operations bounded, including the
adjoint: without them the promotion count would be unbounded.
GHOST OPERATION. For a group memory z = ((p_h, r_h))_(h=1..j) write
Z(z) = { h : r_h = 0 }. At visit i the ghost operation G_i is, in each
big group, the product of the following row action, every other coordinate
being fixed:
(G_(i,g) F)(z) = sum_{A subset Z(z)} (-eta_i/rho)^(|A|)
(q_i/rho^2)^(|Z(z)| - |A|) sum_{b>=0} (1/b!)
(-eta_i V_g/rho)^b int F( z minus A, (p'_1,0),...,(p'_b,0) )
prod_{h=1}^{b} d mu~_g(p'_h). (6.15)
So selected old zeros terminate, continuing zeros are damped, and a new
unordered batch is born at zero. Termination precedes birth: an orphan
cannot be born and terminate at the same visit.
THE EXACT MEMORY IDENTITY. Let D_birth be the rule that all prime values
assigned at DIFFERENT births are distinct. Births are initial active
slots, fresh active target slots, and ghost births. This is a global rule
even if two births occur far apart. Apart from it, put no distinctness
restriction on big active lists or on memories.
LEMMA 6.2 (exact memory identity). Under the rule D_birth, the
independent-residue path expression with the phase coming from (6.3)
equals
( prod_{p big} b_p ) * < 1_empty, G_0 E_0 G_1 ... E_(N-1) G_N 1_empty >,
(6.16)
the inner product being taken in H with the indicator of D_birth inserted
in the expanded path integral.
PROOF. A particle born active begins with a required hit at that visit.
When it leaves an active run, storing it at zero and then translating
records its displacement from that hit; promotion checks displacement
zero; a later store resets the anchor at a congruent offset and therefore
changes no congruence requirement. A ghost birth sets the anchor at an
unmarked hit and a ghost termination checks zero. Shared continuations
automatically respect the congruence.
The rho factors cancel locally: at an internal visit a continuing pending
zero pays rho (q_i/rho^2) rho = q_i, a ghost birth pays (-eta_i/rho) rho =
-eta_i, and a ghost termination pays rho (-eta_i/rho) = -eta_i. An active
particle pays none of these, since promotion occurs before output damping
and storage after input damping. At visit 0 the memory starts empty and
at visit N it ends empty, so no term is lost at the boundary. The
converse construction, from a path in the memory space back to a set of
residue constraints, is the same list of rules read backwards, and it is
injective up to the factorial orders already divided out in (6.12). [End]
6.4 ABSOLUTE BOUNDS.
Everything here is an application of one principle, the weighted Schur
test, so the memory may be handled with row and column sums rather than
with spectral theory.
LEMMA 6.3 (weighted Schur test, constant weights). Let K be a linear map
with nonnegative kernel K(x,y) with respect to counting measure on a
discrete space, and let w > 0 be a weight. If
(Kw)(x) <= R w(x) for all x, (K*w)(y) <= C w(y) for all y,
(6.17)
then ||K|| <= sqrt(RC) for the L^2 norms with the counting measures.
PROOF. Pointwise,
|Kf(x)| <= sum_y K(x,y)|f(y)|
= sum_y (K(x,y)/w(y)) (w(y)|f(y)|)
<= (Kw)(x)^(1/2) ( K(|f|^2/w)(x) )^(1/2), (6.18)
by Cauchy-Schwarz on the sum with the two factors (K(x,y)/w(y))^(1/2) and
K(x,y)^(1/2) w(y)^(1/2). Sum over x, use (6.17), and sum over y. [End]
In the memory space the natural weight is a power of v: for a state with
memory total size j_tot = sum_g j_g, put
w(state) = v^(j_tot), v > 1 fixed. (6.19)
A ghost birth adds one pending particle and costs v, a promotion removes
one and gains 1/v. This exactly compensates the magnitude of the birth
and termination coefficients, which is why a single v handles both
directions.
6.4.1 THE GHOST ADJOINT. In one group abbreviate
A_i = q_i/rho^2, D_i = -eta_i/rho, C_i = V_g D_i, nu = mu~_g, (6.20)
and let z(u) count zero residues in a memory list. For test functions f,
h the joint integral defining (6.15) is
< f, G_(i,g) h > = sum_{k,t,b >= 0} (1/(k! t! b!))
int A_i^(z(u)) D_i^t C_i^b overline{f(u, alpha^0)} h(u, beta^0)
d lambda_g^(tensor k)(u) d nu^(tensor t)(alpha)
d nu^(tensor b)(beta), (6.21)
where alpha^0 means that all its residues are zero. The identity follows
by choosing t old zero indices out of a list of size k+t:
binom(k+t,t) / (k+t)! = 1/(k! t!). (6.22)
Swapping (t, alpha) with (b, beta) and conjugating shows that the adjoint
has the SAME row formula with the birth coefficient D_i and the
termination coefficient C_i. In particular reversal moves the factor V_g
from births to terminations; it never creates a factor p or 1/p. This is
the whole point of using counting measure in the residues: a required
residue costs nothing.
For the absolute ghost kernel the weighted row ratio is exactly
exp( |C_i| v nu(P_g) ) * ( A_i + |D_i|/v )^(z), (6.23)
and the column ratio has C_i and D_i interchanged. Choose v large enough
that, for both possible values of q_i,
q_i/rho^2 + 2 max(1, v_+) eta_i / (rho v) < 1. (6.24)
This is possible because q_i <= sqrt(q) < rho^2. Then both ratios are at
most L^(C_v) with C_v depending on the fixed data, ell and m but not on J.
Consequently
|G_i| w <= L^(C_v) w, so ||G_i|| <= L^(C_v). (6.25)
6.4.2 THE EDGE ADJOINT AND ITS FACTORIAL BOOKKEEPING. A clean edge
translates every memory residue by the step and refreshes unshared active
labels; a dirty edge also stores and promotes. Fix one big group, a
pattern, endpoint permutations, free labels, and the chosen transfer
subsets. Suppose a target slots are promotions and b source slots are
stores, so a, b <= t_g. Let the source memory have size j and write u for
its j-a surviving particles. Let p_1,...,p_a be the promoted labels and
s_1,...,s_b the stored labels. For step Delta the endpoint memories are
X = u joined with ((p_h, -Delta mod p_h))_(h<=a),
Y = T_Delta u joined with ((s_h, Delta mod s_h))_(h<=b), (6.26)
where T_Delta translates every residue. The joint measure on these
variables is
d lambda_g^(tensor (j-a))(u)/(j-a)!
prod_{h<=a} d nu(p_h) prod_{h<=b} d nu(s_h), (6.27)
along with one nu integration for every shared active label, dropped
source label, and fresh target label. The transfer coefficient is
V_g^(-a) and the damping is rho^(z(X)+z(Y)). The factorial accounting is
(j)_a / j! = 1/(j-a)! = (j-a+b)_b / (j-a+b)!. (6.28)
The first equality selects old memory indices into the a specified ordered
target slots. The second selects b indices of the output memory into the
original source slots on reversal. Each required residue in (6.26) is
counting measure, so it contributes no factor.
LEMMA 6.4 (absolute memory bounds). There is C_a, depending on m, C_1 and
the fixed data of 5.1 but NOT on J, such that every absolute edge has
weighted row and column bounds at most L^(C_a). The same holds after
multiplying any operation by a scalar of modulus at most one and after
applying the memory projections.
PROOF. Row direction. Fix a pattern, the free labels, the permutations
and the transfer subsets, and take absolute values of everything. If Z'
old pending particles have zero translated residue, the sum over the
ordered promotions together with the damping of the remaining zeros costs
at most (Z')_a rho^(Z'-a) <= sup_(z>=0) (z)_a rho^(z-a) < infinity; so
the number of promotions per group is controlled by a constant depending
only on rho and t_g <= ell + m. Damping of the stored particles can be
discarded for an upper bound. The Schur weight contributes v^(b-a),
promotions contribute V_g^(-a), and fresh integrations have mass
nu(P_g)^(t_g-a) <= 2^(t_g) for large x. There are at most 4^(t_g) choices
of the transfer subsets. Each of these costs is bounded by a constant per
group, INDEPENDENT OF J, because t_g <= ell + m. Small-group transitions
obey (5.11). Multiply over the groups, average the permutations and the
free labels, and sum (5.6).
Column direction. Use (6.28) and read the adjoint backwards: original
stores become ordered retrievals, whose count is controlled by the
original input rho factors exactly as in the row argument, and the leftover
factor V_g^(b-a) is bounded per group. Restrictions and multipliers of
modulus at most one are dominated by these absolute kernels. [End]
6.4.3 TRUNCATION. Restrict the total memory size to
B = ceil(L^2) (6.29)
before and after every operation, the projections being implicit. At most
(ell + m) s N particles can be supplied by stores, so a path violating the
restriction has at least B - O((ell + m) s N) ghost births. Each ghost
birth has mass at most |D_i| v nu(P_g) <= 2/P_*, since nu(p) <= 2/(V_g p)
and p >= P_*. Multiply every ghost birth by two in the absolute path sum
and use (6.25) and Lemma 6.4. The total omitted mass, even with the
distinct-birth indicator, is at most
2^(-B + O((ell+m) s N)) L^(O(N)) = exp(-Omega(L^2)) = o(L^(-A N)) (6.30)
for every fixed A, because B is of order L^2 while the path length N is of
order L^(0.52).
The boundary vector has bounded norm: its small-group part has mass at
most one by (5.11), and its big-group part has mass
prod_{g in B} nu(P_g)^M = 1 + O_J( s N/P_* ) = 1 + o(1), (6.31)
uniformly in the truncation. The same estimates prove absolute
summability before truncation, for instance by restricting all batch sizes
first and using monotone convergence on absolute kernels.
6.5 RARE TRANSFERS: WHY THE SMALL GROUPS EXIST.
It remains to obtain a small SIGNED edge norm, and then to restore the
distinctness rule that was dropped. Decompose each edge as
E_i = E_(i,clean) + E_(i,dirty), (6.32)
a term being DIRTY if it has at least one store or at least one promotion,
and CLEAN otherwise. Dirty terms are exactly the ones that connect the
memory to the active lists. They are suppressed by averaging the labels
that the source symmetrisation OMITS from the small groups, and this is the
only reason the small groups exist.
Define the omission number
D = binom(M, ell)^(|S|). (6.33)
LEMMA 6.5 (rare transfer). With the memory truncation (6.29), the
aggregate of all dirty terms of any edge has norm at most
2 L^(C_a) ( B/D )^(1/2), (6.34)
after enlarging C_a independently of J if necessary.
PROOF. Fix a big-group source label and a partition of the transfer data
between the two endpoints; these choices are outside the argument. In each
small group the source symmetrisation omits an independent uniformly chosen
ell-subset of its M distinct labels. Let F be the product of ALL small
source labels and let U be the product of the omitted labels. Then the
small-group part of the edge product is
D_S = F/U. (6.35)
By unique factorization and disjointness of the groups, the D possible
choices of U give DISTINCT positive integers. Moreover
U <= exp( ell |S| L^b ) < exp(L^c) <= p (6.36)
for every big p and all large x, because b < c. So the D choices of U are
distinct modulo p. Also F, k and D_B are invertible modulo every p
eligible in (6.36). Hence each pending particle admits AT MOST ONE choice
of U for which its residue is zero, and at most B of the D equally likely
choices allow any promotion at all.
Conditional on every omission choice, the remaining weighted row costs are
uniformly bounded by Lemma 6.4, since the big labels have been fixed. So
the promotion part improves its ROW bound from L^(C_a) to L^(C_a) B/D,
while its column bound stays L^(C_a). The weighted Schur test therefore
gives one half of (6.34). Terms with stores and no promotion have the same
improvement in their COLUMN bound by reversing the edge: a stored particle
becomes a retrieval from the output memory. The exclusion "p does not
divide D" survives reversal. Add the two bounds. [End]
Conditioning on all big labels does not bias the small omission choices,
which is why the argument is applied with the big labels frozen. Now
2 L^(C_a) (B/D)^(1/2)
<< L^( C_a + 1 - (c_0/2) log binom(J + ell, ell) ), (6.37)
because |S| >= c_0 T and B <= L^3. The right side can be made an
arbitrarily strong fixed saving by increasing J, WITHOUT changing the ideal
norm target E_id. This is the only place where J is used, and it is why J
is chosen last.
6.6 CLEAN EDGES AND THE FOURIER REDUCTION.
LEMMA 6.6 (clean norm). There is C_s, depending only on the fixed data of
5.1, such that under the ideal hypothesis (5.12) the clean part of every
edge satisfies
|| E_(i,clean) || <= 2 L^(-E_id + C_s) (6.38)
for all sufficiently large x. In particular C_s is independent of m, C_1
and J.
PROOF.
Step 1: what a clean edge does. A clean edge leaves all memory prime lists
and sizes unchanged, translates their residues, drops every unshared big
source slot, and fills every unshared big target slot freshly. Its input
and output rho factors and its memory projections are contractions and
commute with active-list symmetrisations. Absorb these factors and the
symmetrisations into the two test vectors w_1, w_2, which then remain
symmetric in the big active lists.
Step 2: conditioning on the shared small labels. Fix an ordered tuple d of
J shared labels in each small group and let d' be their product. Define a
map to unrestricted small residue functions by
(P_d w)(y) = ( prod_{g in S} V_g^(-J/2 - ell) )
q^( (1/2) sum_{g in S} (omega_g(y) - M) )
sum over (d, R) a small state at y of w( y, (d, R) ). (6.39)
All other coordinates are untouched. The map is zero where the displayed
list is not a small state, so the damping is used only where
omega_g(y) >= M. The two endpoint factors in (6.39) give
V_g^(-J-2 ell) = V_g^(-M-ell), (6.40)
exactly the physical joint normalisation. Averaging the source omission
and Cauchy-Schwarz over the omitted small labels gives the transfer bound
sum_d || P_d w ||^2 <= L^(C_s) || w ||^2, (6.41)
and the conditioned clean form of the edge pairing is
< w_1, E_(i,clean) w_2 > = sum_d < P_d w_1, T_d P_d w_2 > + error, (6.42)
where the error is O(L^(-A))||w_1||||w_2|| for every fixed A jointly in d
and where T_d is the between-map described in steps 3 and 4.
Step 3: Fourier transform in the big residues. In each big group the
active-list coordinates and the memory residues carry finite tori, and the
usual unitary finite Fourier transform diagonalises translations. One may
first use ordered memory representatives; restricting to symmetric
functions preserves the bound, and big active-list symmetry is unaffected.
At any fixed Fourier frequency, translation and the closure factor
contribute
e( sigma_i Theta D_B ) (6.43)
for a real Theta depending on d, on the memory prime list, on the frequency
and on theta, but INDEPENDENT of the variable big active labels. The
scalar (d')^(sigma_i i zeta) has modulus one. Hence the remaining
operator, on symmetric big active tests, is T(Theta) or its adjoint, with
two changes only: the measures of active labels and of fresh target
integrations are nu = mu~_g instead of mu_g, and the free/active collision
ban is still in force.
Step 4: both changes are negligible in operator norm. Across the M|B|
active coordinates the product density changes by 1 + O_J(sN/P_*), and the
corresponding square-root density identification is unitary between the two
L^2 spaces and commutes with symmetrisation. Fresh integration densities
obey the same bound. The ideal absolute row and column sums are at most
L^(C_1) before these changes, because all its unrestricted fresh laws are
probabilities. Schur's test therefore bounds the density perturbation by
O_J( L^(C_1) s N / P_* ). (6.44)
For the ban, condition on the fixed active state in either row direction.
Each free auxiliary draw has maximal atom O(1/P_*), so its chance to match a
fixed active label is bounded by that quantity; a match to a fresh opposite
unshared label has the same bound by independence. There are O_(J,m)(s)
possible comparisons, and reversal has the same estimate. Hence removing
the banned transitions costs
O_(J,m)( L^(C_1) s / P_* ) (6.45)
in operator norm, which is o(L^(-A)) for every fixed A. Pending labels do
not enter: they are fixed in the Fourier decomposition and are already
accounted for by translation.
Both changes are therefore negligible, uniformly in d, and the between-map
norm is at most 2 L^(-E_id) for large x. Apply Cauchy-Schwarz to (6.42) and
then (6.41). [End]
CHOOSING THE PARAMETERS. The three exponents are fixed in this order:
G > E + C_v + 3, (target signed edge saving)
E_id > G + C_s + 2, (ideal target, from (6.38))
J such that (dirty saving, from (6.37))
(c_0/2) log binom(J + ell, ell) > C_a + G + 3. (6.46)
Then both parts of the truncated edge are bounded and
|| E_i || <= L^(-G) (6.47)
for every edge, uniformly in the position. Only the last choice depends on
m and C_1, which is the quantifier order Theorem 5.2 promises.
One further argument is still needed: distinct births must be restored
WITHOUT losing the signed contraction on every edge. That is section 6.7.
6.7 RESTORING DISTINCT BIRTHS BY EQUALITY RANK.
A single absolute collision estimate cannot finish the job: one
reciprocal-prime saving P_*^(-1) = exp(-L^c) does not absorb a length-N
absolute path cost L^(O(N)). Instead expand the global distinctness
condition into equalities between BIRTH VALUES. Many independent
equalities give many point-mass savings; a small number of them can be
imposed by phases at their birth operations, which leaves the signed
contraction intact on all the other edges.
6.7.1 ADDRESSES. In the truncated evolution allocate potential birth
addresses as follows.
- initial big slots;
- every possible big target slot at every edge, in its canonical order
before the final symmetrisation;
- indices 1,...,B in each group's ordered ghost batch at each visit.
A target slot is PERFORMED as an address precisely when it is a fresh
birth rather than shared or promoted. A ghost address is performed
precisely when its batch is at least that large. These are conditions on
the individual local choices of a path, so the indicator is well defined
for every path in the expanded integral. Let A_* be the number of
addresses; A_* <= O_(J,m)(s N + s B).
6.7.2 THE EXPANSION. Sum over collections pi of pairwise disjoint blocks
of addresses, each block having size at least two. Let C_pi be the
condition that every address in those blocks is performed and that the
prime values within each block are EQUAL. Put
mu(pi) = prod_{B' in pi} (-1)^(|B'|-1) (|B'|-1)!,
r(pi) = sum_{B' in pi} (|B'|-1). (6.48)
For a fixed realised path,
indicator{distinct performed birth values} = sum_pi mu(pi) 1_(C_pi). (6.49)
Indeed, interpret a block of size h as a CYCLE on its h addresses: there
are (h-1)! such cycles, each of sign (-1)^(h-1). The right side is the sum
of signs of permutations of the performed addresses which preserve their
numerical prime values, and it factors over equal-value classes; the sign
sum is one for a singleton class and zero for any class of size at least
two, by pairing permutations with their product by a fixed transposition.
A rank-r collection involves at most 2r addresses, and its total absolute
coefficient, summed over collections of rank r, obeys
sum_(r(pi)=r) |mu(pi)| <= A_*^(2r) <= L^(C' r). (6.50)
For instance the unsigned cycle generating polynomial on A_* addresses is
prod_(j=0)^(A_*-1) (1 + j t), where the power of t is the sum of the cycle
lengths minus the number of cycles, so its coefficient of t^r is at most
(A_*^2)^r / r! <= A_*^(2r).
6.7.3 LARGE RANK: CHRONOLOGICAL FRESH INTEGRATIONS. Fix pi. Order the
birth addresses chronologically, using canonical slot order inside an edge
or a batch, and call the first address of each block its PIVOT. Every other
address is a DEPENDENT birth. When a dependent address is performed, its
fresh prime integration is constrained to the already determined pivot
value. Since
sup_{g in B, p in P_g} nu(p) << P_*^(-1), (6.51)
this improves the weighted absolute row bound by O(P_*^(-1)) for each
dependent birth.
Here the chronological assertion uses genuinely fresh integrations. At an
edge, choose stores, promotions and the step first, and then fill fresh
target slots in canonical order: the step, the promotion count and the
memory weight do not depend on the new prime values, the coefficient is
bounded by its supremum, and exclusions may be discarded. In the proof of
Lemma 6.4 replace the total fresh mass in each constrained slot by its
single-point bound; for a ghost operation keep its ordered batch integral
and factorial divisor, constraining indicated fresh coordinates replaces
their mass factors by the same single-point bound, and the birth
coefficient V_g together with the memory weight contributes only fixed
constants per constrained coordinate. Initial active slots obey the same
product estimate. Pivots and dependents within one operation are handled
in their prescribed integration order.
For completeness, these conditional row bounds iterate although a pivot may
have died before its dependent birth: retain all pivot values in the
conditioning, bound the remaining terminal sum by backward induction using
the uniform weighted row bounds for every possible conditioning, beginning
with 1_empty <= w, and note that whenever a dependent birth is reached the
preceding point-mass improvement is uniform in its retained pivot value. At
the initial boundary w = 1 and the remaining integrated boundary mass is
bounded. Thus the total absolute contribution for a fixed collection is at
most
L^(C_h (N+1)) (C/P_*)^(r(pi)) (6.52)
for fixed C_h and C, both of which may depend on m and C_1.
Choose a sufficiently large fixed C'' after these constants and after C',
and set
r_0 = ceil( C'' N T / log P_* ) = ceil( C'' N T / L^c ). (6.53)
By (6.50) and (6.52), the sum over r >= r_0 is bounded by
L^(C_h (N+1)) sum_(r >= r_0) ( C L^(C') / P_* )^r = o(L^(-E N)), (6.54)
because log P_* = L^c is enormous compared with T, so r_0 is a vanishing
proportion of N; increasing C'' beats the fixed exponent C_h + E.
6.7.4 SMALL RANK: PHASES ONLY AT THE AFFECTED BIRTHS. For a block with
pivot beta_0 and other addresses beta_1,...,beta_(h-1), equality of the
integer prime values has the EXACT representation
1_( p_(beta_j) = p_(beta_0) for 1 <= j < h )
= int_( [0,1]^(h-1) ) e( sum_(j=1)^(h-1) tau_j
( p_(beta_j) - p_(beta_0) ) ) d tau. (6.55)
For fixed Fourier parameters, collect the factors BY THEIR BIRTH OPERATION.
Each affected operation is multiplied, on its individual local choices, by
1_(designated local births are performed)
* e( sum_(beta local) c_beta p_beta ), (6.56)
of modulus at most one. Initial-slot factors merely modify the initial
boundary vector by such a multiplier. An affected EDGE can lose its signed
norm saving, but Lemma 6.4 bounds its new norm by L^(C_a). Unaffected edges
retain their complete signed pattern sum and both symmetrisations, so the
per-edge contraction (6.47) still applies.
There are at most 2r_0 affected edges, and C_a + G is fixed, so the total
contribution of all collections of rank at most r_0 is at most
L^( 2 r_0 (C_a + G) ) L^(-G N) = o(L^(-E N)), (6.57)
because 2 r_0 (C_a+G) = O(N T L^(-c)) vanishes against G N, using G > E.
Thus the high-rank terms are controlled by their fresh-label costs, and the
low-rank terms retain signed contraction on N - o(N) edges. Together they
bound the expansion with distinct births, which is the expression required
by Lemma 6.2.
6.8 COMPLETION OF THEOREM 5.2.
Apply (6.49) in the truncated memory identity of Lemma 6.2. The
large-rank bound (6.54) and the small-rank bound (6.57) together give
o(L^(-E N)), uniformly in theta. Restore the memory tail by (6.30), which
is o(L^(-E N)); multiply by the baseline prod_(p big) b_p, which is at most
one; integrate the return Fourier factor int_0^1 e(theta h_N) d theta; and
finally restore the uniform residue-replacement error of Lemma 6.1, whose
precision is chosen after the absolute path bound. The result is
o(L^(-E N)), that is (5.14) for all sufficiently large x.
The choice of E_id in (6.46) depends only on E, C_v and C_s, and the
dependence of those constants was stated: C_v depends on the fixed data, ell
and m; C_s on the fixed data alone; C_a on the fixed data, m and C_1. Only
J is chosen after E_id. This completes the proof of Theorem 5.2 with the
asserted quantifiers.
7. SMALL IDEAL KERNELS AT EVERY FREQUENCY
This section proves the ideal norm bound (5.12) that section 6 consumed.
It is the only place where the arithmetic of the big groups is used: each
big group is an INTERVAL of primes, so a single label may be varied while
the others are frozen, and Siegel-Walfitz becomes available.
7.1 THE THEOREM, AND WHY IT IS NOT TRIVIAL.
The operator T(Theta) of section 5.4 sends a test function on ordered label
tuples to another one, multiplying by K_nu D_B^(i zeta) e(Theta D_B). The
SHARED labels make the input and the output tuple depend on each other. If
K_nu were the constant one, T(Theta) would be a perfectly correlated "copy
everything" operator of norm one, and no power of L would be gained. We
must add signed comparison patterns whose combined effect is small, so the
raw coupling must be CANCELLED, not merely bounded.
The idea. Split the big groups into two blocks. Designate m probe slots
in each big group. A comparison pattern FREES some nonempty set A of probes
in the first block and some nonempty set B in the second block: the labels
in those slots are drawn independently at target and source instead of
being shared. Then decompose the two tests orthogonally along the probes
(the Efron-Stein decomposition). Freeing A kills every component of the
input test that genuinely depends on a probe of A, and symmetrically for B.
Alternating over all nonempty A and B therefore cancels every pair of
components except those for which the input is independent of at least one
first-block probe, or the target is independent of at least one second-block
probe. Those surviving components are small, because a symmetric function
that is independent of one coordinate of a large block must have small norm
after averaging the last ell coordinates.
Three analytic ingredients enter. (i) A bilinear estimate for phases
e(alpha n t) with n, t restricted to short integer intervals (7.2). (ii)
Character sums on a matched logarithmic cell, which need the interval
structure of the big groups (7.3). (iii) A Gram-matrix bound saying that
the character frame on a cell has norm at most two, because distinct
characters are nearly orthogonal (7.3).
THEOREM 7.1 (ideal kernels). For every fixed E_id > 0 there are a fixed
integer m = m(E_id), a fixed exponent C_1 = C_1(E_id), and a finite family of
patterns satisfying (5.6) with that C_1, such that
sup_(Theta in R) || T(Theta) || <= L^(-E_id) (7.1)
for all sufficiently large x. The data of section 5.1, and the requirement
J >= J_0 for a fixed J_0 depending on m and C_1, are the only other inputs.
So the exponent C_1 of the pattern mass is allowed to depend on E_id, and m
also, but neither depends on J or on the position. This is the quantifier
order that (5.12) and section 6.8 need.
7.2 TWO ELEMENTARY BOUNDS.
Throughout, Lambda is a nonempty set of slots using k_g <= m slots from
group g, P_Lambda is the product of its labels, and rho_Lambda is the
distribution of that product under the product of the laws mu_g, with
repetitions allowed.
LEMMA 7.2 (label product atoms). On the support of P_Lambda,
rho_Lambda(n) = Prob(P_Lambda = n)
= (1/n) prod_g ( k_g! / ( V_g^(k_g) prod_(p in P_g) a_p! ) )
<= L^kappa / n, (7.2)
where a_p is the multiplicity of p in n and
kappa = C_0 ( log(m!) + m log max(1, v_-^(-1)) ). (7.3)
The probability is zero unless the prescribed group multiplicities hold.
In particular the exponent does not depend on J.
PROOF. The displayed formula is the product over groups of the probability
that an unordered k_g-tuple drawn with law mu_g has a given multiset of
values. Each factor apart from 1/n is at most m! max(1, v_-^(-1))^m, and
there are at most 2 C_0 T groups. [End]
LEMMA 7.3 (ideal collapse). Let f be an L^2 test on the whole ordered
label tuple, supported where c_1 U <= P_Lambda <= c_2 U for fixed positive
c_1, c_2. Put a_n = E[ f 1_(P_Lambda = n) ]. Then
sum_n |a_n|^2 <= sum_n rho_Lambda(n) E[ |f|^2 1_(P_Lambda = n) ]
<= (L^kappa / (c_1 U)) || f ||^2. (7.4)
No assumption that f is a function of the product has been made.
PROOF. Cauchy-Schwarz on each fiber of the map that sends a label tuple to
its product, followed by (7.2). [End]
LEMMA 7.4 (integer bilinear estimate). Let U, V >= 1. Suppose a_n, b_t
are supported in integer intervals of lengths at most CU and CV, with C
fixed. If
alpha = u/r + beta, (u,r) = 1, r >= 1, |beta| <= r^(-2), (7.5)
then
| sum_(n,t) a_n b_t e(alpha n t) |
<<_C ||a||_(l2) ||b||_(l2)
[ U + (1 + V/r) ( U + r log(2r) ) ]^(1/2). (7.6)
The containing intervals need not begin at 1, and the coefficients may
vanish on arbitrary subsets of them.
PROOF. Extend the coefficients by zero to their containing intervals.
Cauchy-Schwarz in n, followed by expansion of the square and the
geometric-sum bound on the full interval of n, gives
| sum_(n,t) a_n b_t e(alpha n t) |^2
<<_C ||a||^2 ( U sum_t |b_t|^2
+ sum_(1 <= |h| <= CV) min(U, ||alpha h||_(R/Z)^(-1))
sum_t |b_t b_(t+h)| )
<<_C ||a||^2 ||b||^2 ( U + sum_(1 <= h <= CV)
min(U, ||alpha h||_(R/Z)^(-1)) ). (7.7)
At a zero denominator the minimum is read as U. For r >= 2 split the
h-range into O_C(1 + V/r) consecutive blocks, each of diameter at most r/2.
If h != h' lie in the same block, their difference is nonzero and less than
r in size, so
||alpha (h-h')||_(R/Z) >= ||u(h-h')/r||_(R/Z) - |h-h'|/r^2
>= 1/(2r). (7.8)
Thus the phases in a block are 1/(2r)-separated on the circle, and ordering
them by distance from zero bounds the contribution of a block by
O_C( U + sum_(1 <= j <= 2r) r/j ) = O_C( U + r log(2r) ). (7.9)
For r = 1 the trivial bound O_C(UV) for the whole sum gives (7.6). [End]
7.3 COMPARISON ON A MATCHED LOGARITHMIC CELL.
The operator T(Theta) multiplies by e(Theta D_B), which is a rapidly varying
function of the free product D_B. Two different free products must be
matched to the same logarithmic cell before the phase can be treated as a
constant; on a cell, characters handle the residue pattern, and the Gram
bound below says the character frame is almost orthogonal.
For a fixed nonempty slot set Lambda using at most m slots per group, let D
and X be independent products of label tuples of that type (one at the
target, one at the source). Given Q >= 1, 0 < h <= 1 and 0 < xi <= 1, put
I_j = [jh, (j+1)h), nu_(Lambda j) = Prob( log D in I_j ),
C_Q = { chi : chi primitive, conductor of chi <= Q }, (7.10)
the conductor-one character being included. Define the CELL KERNEL
K_Lambda(D, X) = sum_(j : nu_(Lambda j) >= xi)
( 1_(log D in I_j) 1_(log X in I_j) / nu_(Lambda j) )
sum_(chi in C_Q) conj(chi(D)) chi(X). (7.11)
Use K_A and K_B for the two slot sets. All powers of L chosen below are
fixed before J.
There are at most Q^2 characters in C_Q. The number N_Lambda of cells of
positive mass satisfies
N_Lambda <<_m 1 + T L^d / h,
sup |K_Lambda| <= Q^2/xi,
sup_X E_D |K_Lambda(D,X)| <= Q^2. (7.12)
The last inequality holds because, for fixed retained X, the mass nu_(Lambda
j) of its cell cancels the denominator; the kernel vanishes for discarded X
and is supported only where |log D - log X| < h.
LEMMA 7.5 (cell Gram bound). Let Q be a fixed power of L and let chi, chi'
be distinct members of C_Q. Then for every fixed D_* > 0,
| E[ 1_(log D in I_j) conj(chi(D)) chi'(D) ] | <<_(D_*) L^(-D_*), (7.13)
uniformly in j and in the nonempty slot set with at most m slots per group.
Consequently, for retained X,
E_D | K_Lambda(D, X) |^2 <= 2 Q^2 / nu_(cell)(X), (7.14)
where nu_(cell)(X) is the mass of the retained cell containing X, and the
kernel defines a bounded operator on L^2 with norm at most 2 Q.
PROOF. The first estimate: on a cell the ratio D/X lies within a factor
e^h = 1 + O(L^(-h_*)), so it suffices to sum conj(chi chi')(n) over integers
in a dyadic interval, and chi chi' is a nonprincipal character of conductor
at most Q^2 <= L^(2 q_*), for which the Polya-Vinogradov bound gives the
claim. The second estimate: the diagonal term of the character sum is the
single term chi = chi', giving 1/(nu_(cell)); every off-diagonal term is
small by the first estimate, and there are at most Q^2 of them. The
operator norm then follows from Schur with the two bounds
E_D|K(D,X)| <= Q^2 and E_X|K(D,X)| <= Q^2. [End]
LEMMA 7.6 (comparison). Fix the endpoint bounds and a fixed A_0 > 0.
There are fixed exponents q_*, s_*, h_*, x_*, and a fixed B_0, all depending
only on A_0 and the fixed data, such that on a pair of dyads with
U, V >= exp(L^a) and with products confined to [U/2,4U] and [V/2,4V], the
raw pairing R(F, H) of the two tests satisfies
| R(F, H) - R_(comp)(F, H) | <= L^(-A_0) ||F|| ||H||, (7.15)
where R_(comp) is the pairing in which each free product D_A or D_B has been
replaced by its matched cell representative and the character sums have been
inserted, times the comparison sign.
PROOF.
Discarded cells. Put
E = { X_A or X_B lies in a discarded cell }. (7.16)
The comparison term vanishes on E. The raw term there is at most
Prob(E)^(1/2) ||f|| ||g||, by Cauchy-Schwarz and independence of the two
tuple spaces, and
Prob(E) <= (N_A + N_B) xi. (7.17)
This argument also covers tests concentrated in a discarded cell; it does
not assert that restriction to a small event is small as an operator.
Matched cells. On retained cells write the remaining scalar multiplier in
the log variable as M(v) = exp(i zeta v) e(beta e^v). On the enlarged
product range its derivative has magnitude O(L^(C_4) + S). Since the two
matched log products differ by less than h, M(log(D_A D_B)) may be replaced
by M(log(X_A X_B)) leaving the rational phase unchanged. For each fixed
retained pair (X_A, X_B), (7.12) bounds the error after integration in
D_A, D_B by
O( Q^4 h (S + L^(C_4)) ). (7.18)
This error is pointwise, so pairing it with the tests costs at most the same
bound times ||f|| ||g||, the two spaces being independent.
Character reproduction. For a character psi meeting the condition below,
the Gram computation gives the pointwise reproduction formula, valid for
retained X:
E_D K_Lambda(D, X) psi(D) = psi(X) + O_(D_*)( Q^2 xi^(-1) L^(-D_*) ). (7.19)
The summand corresponding to the inducing primitive character is exactly
psi(X), because the diagonal conditional expectation is 1; every other
summand is bounded by (7.13) divided by the retained cell mass, and there
are at most Q^2 of them. Choose D_* so that the displayed error is at most
one. Applying (7.19) on both sides and then (7.13) reproduces
e(u X_A X_B / r) with pointwise error
O_(D_*)( Q^(5/2) xi^(-1) L^(-D_*) ). (7.20)
Multiplication by the fixed scalar M(log(X_A X_B)), of modulus one, does not
change this.
Together, (7.17), (7.18) and (7.20) give (7.15) for a suitable choice of the
exponents, which is made in section 7.5. [End]
7.4 SYMMETRIC PROBES AND EXACT CANCELLATION.
Now the cancellation. Fix two disjoint blocks of big groups, I_1 for the
input and I_2 for the target. Designate m probe slots in each big group of
each block. For a test vector F on the input and H on the target, and for
free sets A subset of the first-block probes and B subset of the second-block
probes, let R_(A,B)(F,H) denote the pairing in which the probes in A are
drawn independently at the source and those in B independently at the
target. The raw term is R_(empty,empty).
THE COMPARISON FAMILY. Include, with coefficient
(-1)^(|A| + |B|) 1_(A nonempty) 1_(B nonempty), (7.21)
the pattern obtained from the raw one by freeing A and B, with the same
coefficient data and the kernel replacement of Lemma 7.6. This is a finite
family whose size is at most 2^(m s_1) 2^(m s_2), and its total coefficient
mass is at most 2^P, where P = sum over the probes.
Step 1: the Efron-Stein decomposition. For a single group with m probes,
use the standard decomposition onto subsets: F = sum over S subset of the
probes of F_S, where F_S has mean zero in every probe not in S and is
independent of every probe in S. Then ||F||^2 = sum_S ||F_S||^2, and the
decomposition is orthogonal.
Step 2: freeing kills components. A comparison term with free set A
vanishes unless A is disjoint from the support set S of the input component,
since integrating an unshared label against the coordinate free of the
multiplier annihilates a mean-zero component. The same holds for B and the
target. Hence the A-sum over nonempty A disjoint from S equals
sum_(nonempty A subset U) (-1)^(|A|) = -1_(U nonempty), (7.22)
where U is the complement of S inside the probes.
Step 3: the exceptional components are small. A component pair survives
only if the input is independent of some first-block probe or the target of
some second-block probe. Let
theta_m = 2 (m/(m+ell))^m (ell/(m+ell))^ell <= 2 ell^ell m^(-ell), (7.23)
the middle expression being the maximum of t^m (1-t)^ell over t in [0,1],
attained at t = m/(m+ell); the Hoeffding fraction gives the bound
||F_full|| <= theta_m^(1/2) ||F||, ||H_full|| <= theta_m^(1/2) ||H||,
(7.24)
for the parts whose probe support misses at least one probe, after averaging
the last ell coordinates. This bound tensorises even when the vectors are
not products across groups: resolve the decomposition by component
cardinalities, use within-group permutation symmetry to see that all tuples
of subsets with fixed cardinalities have equal squared norms, and multiply
(7.23) over the groups of the block. Averaging the last ell coordinates in
the other groups is a further contraction.
Step 4: exact cancellation. With U, V the missing probe sets of a component
pair, the sum over nonempty A subset U and nonempty B subset V of
(-1)^(|A|+|B|) equals (-1)(-1) = 1, so the comparison sign (7.21) cancels the
raw pairing exactly, up to the errors of Lemma 7.6. Summing the exceptional
raw pairs before taking absolute values gives at most
2 theta_m^(1/2) ||F|| ||H||. (7.25)
Step 5: counting the errors. There are at most 3^P admissible triples
(component pair, free subsets): each probe is either indicated, missing but
not freed, or freed. So the accumulated error is at most
3^P L^(-A_0) ||F|| ||H||, and choosing
A_0 > E_id + P log 3 + 10 (7.26)
makes it L^(-E_id-10) ||F|| ||H||. With (7.25) and the choice of m in
section 7.6 this proves (7.1).
Step 6: the coefficient cost. The number of comparisons is at most 2^P <=
exp(m C_0 T log 2), and (7.12) bounds each coefficient by Q^4 xi^(-2). After
the choices of section 7.5, any fixed
C_1 > m C_0 log 2 + 4 q_* + 2 x_* + 1 (7.27)
bounds the total coefficient cost, including the raw pattern. Expanding the
two cell sums and the two character sums also contributes only a fixed power
of L terms. Both free products contain a big prime, so
D_A, D_B >= exp(L^c). The coefficient uses only the four products specified
by the cell kernel, and all assertions about labels and separation follow
from (7.11).
7.5 A NON-CIRCULAR CHOICE OF PARAMETERS.
Write Q = L^(q_*), S = L^(s_*), h = L^(-h_*), xi = L^(-x_*). After m, A_0
and C_4 have been fixed, choose successively
B_0 > A_0 + 2(d+1) + 10,
q_*, s_* > 2(B_0 + kappa + 10) + d + 1,
h_* > 4 q_* + max(s_*, C_4) + B_0 + 10,
x_* > 2 B_0 + d + 1 + h_* + 10,
D_* > B_0 + x_* + (5/2) q_* + 10. (7.28)
These lines control, in order: the dyadic summation in (7.15); the estimate
(7.17) for discarded cells; the multiplier error (7.18); the square root of
(7.17); and both (7.13) and (7.20). Fixed implied constants are absorbed by
the margins. Finally apply Siegel-Walfitz at the precision needed for this
D_*. None of these choices involves J. The exponent C_1 is then fixed by
(7.27), and it depends on m only through the term m C_0 log 2.
7.6 CHOOSING THE PROBE COUNT m.
Two conditions are needed. First, the Hoeffding fraction must be less than
one. With M = J + ell and (m + ell) <= M/2 the fraction is at most
(m/(m+ell))^m (ell/(m+ell))^ell <= ell^ell m^(-ell) < 1 (7.29)
for m > ell. Second, the surviving components must be small enough to be
absorbed: the exceptional pairs contribute at most theta_m^(s_i/2) for
s_i >= c_0 T/3 probe blocks, and the error terms contribute 3^P L^(-A_0)
with P <= m C_0 T. So it suffices that
theta_m := 2 ell^ell m^(-ell) and -(c_0/6) log theta_m > E_id + 3.
(7.30)
Since ell >= 1 is fixed, increasing m makes theta_m as small as desired, and
(7.30) is a condition on m alone. Choose m accordingly; then the number of
probes P and the error count in (7.26) are fixed, and A_0 is chosen from
(7.26). Finally require
J >= m and J + ell >= (m + ell)(m + ell - 1) =: J_0, (7.31)
which is the hypothesis used in (7.29) and in the theorem's quantifiers. A
still larger fixed J may be chosen later to meet Theorem 5.2 without
changing any kernel parameter, any A_0, or the exponent C_1.
This completes the proof of Theorem 7.1: the ideal norm bound (7.1) holds
with the constants chosen in (7.26), (7.27), (7.28) and (7.30), and with m
and C_1 depending only on E_id and on the fixed data of section 5.1.
8. LIFTED SHIFTED CORRELATIONS
We keep the prime groups P_g and their notation from sections 5-7. So the
small groups sit in [exp(L^a), exp(L^b)], the big groups are intervals of
primes in [exp(L^c), exp(L^d)], with 0 < a < b < c < d < 0.47. All groups
are disjoint, their harmonic masses V_g lie in [v_-, v_+], and each kind
has between c_0 T and C_0 T groups. The parameters q in (0,1) and ell >= 1
are fixed. Write P = union_g P_g and let n_* be the P-free part of n.
8.1 THE MARKED WEIGHTS AND ENDPOINTS.
For a vector t = (t_g)_g of nonnegative integers, define the marked weight
W_t(n) = q^(omega(n) - sum_g t_g) prod_g ((omega_g(n))_t_g / V_g^(t_g)),
(8.1)
where (y)_t = y(y-1)...(y-t+1). The falling factorial counts ordered lists
of distinct group primes dividing n. For a function b on these lists,
W_t^b(n) = q^(omega(n) - sum_g t_g) prod_g V_g^(-t_g) (8.2)
sum over ((p_(g,1),...,p_(g,t_g)) : distinct in each group,
p_(g,j) in P_g, p_(g,j) | n) of b((p_(g,j))).
An empty admissible-list set gives value zero. Write W_ell when all
t_g = ell. For every fixed t_max,
sup_(max t_g <= t_max) |W_t^b(n)| <= ||b||_infty L^(C(t_max)) (8.3)
because q^(y-t) (y)_t / V_g^t has a bounded sup over integers y >= t,
uniformly for t <= t_max, and there are O(T) groups.
An ENDPOINT is a function invariant under multiplication by P-integers,
of the form
F_0(n) = sum_(mpr = n_*) alpha_m chi_0(m) m^(i sigma_0) (8.4)
1_(p in I_p, P^-(p) > W) p^(i sigma_1) c_r.
Here |alpha_m|, |c_r| <= L^C, alpha_m = 0 unless P^-(m) > W, I_p is an
interval in [x^tau, x^eta] with fixed 0 < tau < eta < 1/4, chi_0 is a
Dirichlet character of modulus at most L^C, and |sigma_0|, |sigma_1| <=
L^C. The variable p is an integer, not asserted prime. The sequences may
depend on x, and all parameters may differ at the two endpoints. Since
W = exp(sqrt L) exceeds every group prime, m and p are P-free for large x.
We impose the DISCREPANCY CONDITION on the alpha sequence of at least the
first endpoint:
| sum over m in I of alpha_m chi(m) m^(iu) / m | <= L^(-B) (8.5)
for every interval I in [1, x^2], every Dirichlet character of modulus at
most L^B, and every real u with |u| <= L^B. Principal and imprimitive
characters are included. An existing interval restriction on alpha is
part of the sequence.
THEOREM 8.1 (lifted shift cancellation). Fix all the group and endpoint
bounds above, fix D_0 and C > 0, and a fixed compact interval
[c_Psi, C_Psi] in (0, infinity). Suppose 0 < |k| <= L^C is an integer,
x L^(-C) <= Z <= x L^C, |a_1|, |a_2| <= L^C, and Psi is supported in the
stated interval with ||Psi^(j)||_infty <<_j L^(C(j+1)) for every j >= 0.
There is a fixed B, depending only on these data and on D_0, such that
(8.5) implies
sum over z > 0, z + k > 0 of
(Psi(z/Z)/z) z^(ia_1) (z+k)^(ia_2)
conj(F_0(z)) G_0(z+k) W_ell(z) W_ell(z+k) (8.6)
<< L^(-D_0).
The bound is uniform over the indicated sequences, intervals, characters,
frequencies, and cutoffs. It also holds when the discrepancy-bearing
endpoint or its coefficients have been conjugated.
Conjugating on the right is harmless: conjugate (8.5) and replace chi by
conj(chi), u by -u. Products with extra characters and bounded power
twists are covered by increasing B. We prove (8.6) in the next seven
subsections.
8.2 THE PHYSICAL LIFT AND REMOVAL OF SHARED LABELS.
Take the raw pattern and the signed comparison patterns of Theorem 7.1.
Write m_probe for the fixed probe bound of that theorem; the letter m in
(8.4) denotes an integer factor, not a probe count. As in the physical
construction, M = J + ell, the edge product is D, and the positions are
n and n' = n + k D. Insert into the physical pairing the root weight
Psi(n/(ZD))/n, the edge phase D^(-i(a_1+a_2)), and the mark-independent
vectors
f(n, p) = n^(-ia_1) F_0(n) q^((omega(n) - Ms)/2), (8.7)
g(n', p') = (n')^(ia_2) G_0(n') q^((omega(n') - Ms)/2).
Our pairing is conjugate-linear in its first entry, so the integrand
contains n^(ia_1) conj(F_0(n)) at the source and (n')^(ia_2) G_0(n') at
the target. Every factor involving D is inside the slot symmetrisations.
On the support, n = ZD times x^o(1) and n'/n = 1 + O(L^C/Z). A partition
into at most O(L) dyads n = X plus restriction of the other endpoint to
an interval of length O(X) therefore suffices.
Step 1: the endpoint norm bound. On a physical state omega(n) >= Ms, so
the damping in (8.7) is at most one. There are at most tau(n_*)^2 ordered
factorizations in (8.4), so |F_0(n)| <= L^(2C) tau(n_*)^2. Fix an
ordered physical list S' of M distinct labels per group, with product
P(S'). For P(S') | n, one has n_* | n/P(S'), hence
sum over n = X, P(S') | n of tau(n_*)^4 (8.8)
<= sum over v = X/P(S') of tau(v)^4
<< (X/P(S')) L^(C_5).
Here P(S') <= exp(O_J(T L^d)) = x^o(1), so the v-interval still has
positive power length. Moreover
sum over S' of (1/P(S')) prod_g V_g^(-M)
<= prod_g (sum_(p in P_g) 1/(p V_g))^M = 1. (8.9)
So both endpoint vectors have norm at most X^(1/2) L^(C_6) in the
physical state measure, with C_6 independent of J and of the probe count.
Also |F_0(n)| <= exp(O(sqrt L)): an integer of size x^O(1) has O(sqrt L)
prime factors above W, with multiplicity, hence at most 2^(O(sqrt L))
choices of the rough divisors m, p. The vectors are independent of the
selected marks.
Step 2: logarithmic Fourier inversion. Let Phi(u) = Psi(e^u). Then
Psi(n/(ZD)) = (1/(2 pi)) int_R hat_Phi(v) (n/Z)^(iv) D^(-iv) dv. (8.10)
The derivative hypotheses give an L^O(1) integral norm, and, for any
fixed large C_7, the tails |v| > L^(C_7) have arbitrarily large negative
log powers. The cutoff exponent C_7 may be fixed from the derivative
bounds: more integrations by parts increases the saving without
increasing C_7.
On the dyad, multiply the first vector by X/n and by (n/Z)^(-iv) and
divide the pairing by X. The conjugation in the pairing supplies
(n/Z)^(iv). The required ideal frequency is zeta = -a_1 - a_2 - v. By
Corollary 5.3 and Theorem 7.1 the entire residual pairing is bounded by
L^(-D_1) for any prescribed D_1, after choosing the transfer target
first, then the ideal family, then J. The norm exponent just proved
makes this ordering possible. The discarded Fourier tails obey the same
conclusion by Lemma 5.1; their accuracy may be chosen after the absolute
comparison costs are known. All these apply to the sum of patterns,
with their signs.
Step 3: per pattern, after the lift. In group g write c_g for its
free-slot count and s_(R,g) = J - c_g for its shared-slot count; so
t_g = ell + c_g. Let D_R, D_C be the products of the shared and free
labels, so D = D_R D_C. This partition is by ROLE, not by size; the
earlier D = D_S D_B partition is by size. Set n = D_R w, n' = D_R w',
so w' = w + k D_C. The physical state and target-list normalizations
in group g are
V_g^(-M-t_g) = V_g^(-s_(R,g) - 2 t_g), M + t_g = s_(R,g) + 2 t_g. (8.11)
The factor 1/D_R from 1/n changes each shared-label sum into a draw of
mass 1/(p V_g) and leaves V_g^(-t_g) at each endpoint for its unshared
lists. Away from shared overlaps,
omega_g(D_R w) - M = omega_g(w) - t_g. (8.12)
The graph damping and that in (8.7) supply the full power of q at each
endpoint. Invariance of F_0 gives F_0(D_R w) = F_0(w); and the phases
become
(D_R w)^(ia_1) (D_R w')^(ia_2) (D_R D_C)^(-i(a_1+a_2))
= (w/D_C)^(ia_1) (w'/D_C)^(ia_2). (8.13)
The coefficient K_nu of a comparison uses the free labels and the
designated unshared big labels, and uses no shared labels. Its
dependence therefore survives the shared-harmonic summation.
Step 4: error bounds from the exclusions. For fixed w, w', D_C and any
earlier shared draws, only O_J(L) values are forbidden to a new shared
draw (endpoint prime divisors, free labels, previous shared labels).
Each atom has mass at most v_-^(-1) exp(-L^a). The O_J(T) draws have
excluded total probability L^(O_J(1)) exp(-L^a).
For distinct shared values the exact identity is
omega(D_R w) - Ms = omega(w) - sum_g t_g - #{p : p | D_R, p | w}. (8.14)
Bounding actual overlap terms by the unrestricted marked sum costs at
most q^(-2Ms) = L^(O_J(1)) in damping. Unshared divisors still divide
w, w', and their count cannot increase. By (8.3), endpoint
Cauchy-Schwarz, and divisor moments, their remaining absolute harmonic
average is L^O(1). So shared exclusions cost L^(O_J(1)) exp(-L^a).
Step 5: the free-label ban. Once shared overlaps are excluded, the
remaining ban excludes free labels from the unshared endpoint mark
lists. Every excluded configuration thus has a free prime p' dividing
an endpoint. Since p' | D_C, both p' | w and p' | w'; so it suffices to
bound all such multiples. On w = Y_0 = Z D_C, put w = p' v and
w' = p' (v + k D_C/p'). Invariance and Cauchy-Schwarz give
sum over w = Y_0, p' | w of |F_0(w) G_0(w + k D_C)| / w
<< L^O(1) / Y_0 (8.15)
( sum over v = Y_0/p' of tau(v)^4 )^(1/2)
( sum over v = Y_0/p' of tau(v + k D_C/p')^4 )^(1/2)
<< L^O(1) / p'.
Both shifted ranges lie in positive intervals of length O(Y_0/p'), and
Y_0/p' = x^(1+o(1)). The mark weights, coefficients, and total pattern
costs are fixed log powers, so summing over the free slots makes this
error negligible too. This is an AVERAGED bound over multiples of p',
not a restriction on the arbitrary coefficients.
Step 6: the stripped form per pattern. Up to errors smaller than every
fixed negative log power, each pattern contributes
E_free sum over w > 0, w' = w + k D_C > 0 of (8.16)
(Psi(w/(Z D_C))/w) (w/D_C)^(ia_1) (w'/D_C)^(ia_2)
conj(F_0(w)) G_0(w') W_t(w) W_t(w') E_marks(K_nu).
The outer expectation uses independent free-label laws mu_g. Conditional
on these labels and the positions, the inner expectation uses
independent uniform ordered unshared lists at each endpoint; its term is
zero if either list set is empty. The raw pattern has D_C = 1 and
t_g = ell, so it is exactly the sum in (8.6). What remains is to bound
every comparison term.
8.3 COMPARISON SHIFTS AND THEIR MAJOR ARCS.
Expand a comparison coefficient from Lemma 7.6 by its two logarithmic
cells and its two characters. Its factors on the free products D_A, D_B
separate, and the remaining factors are bounded weights on big unshared
marks at the two endpoints. Cell normalizations, the number of terms,
and the integral costs are fixed log powers, independent of J. Let H'
be the product of the lower size endpoints of the two cells; then
D_A D_B = H' up to e^h, and
H' >= exp(L^c), H' <= exp(O(m_probe T L^d)), Y = Z H' = x^(1+o(1)). (8.17)
Insert smooth size cutoffs at w, w' = Y, separate Psi(w/(Z D_A D_B))
logarithmically, and include Y/w in the first cutoff. Up to a factor of
1/Y and fixed log-power costs, every resulting term has the form
E_(D_A, D_B) b_1(D_A) b_2(D_B)
sum over w of conj(U(w)) V(w + k D_A D_B), (8.18)
with |b_1|, |b_2| <= 1, each supported on its cell. Each endpoint
sequence is its invariant endpoint times a smooth cutoff at Y, a power
w^(iv) with |v| <= L^O(1), and a weight W_t^b(w). The extra mark
function uses only big labels. In particular
sum over w of |U(w)|^2 + |V(w)|^2 << Y L^(C_8). (8.19)
All the frequency and cutoff bounds here are fixed before B.
The endpoint sequences are now independent of the free products. Fourier
inversion isolates the weighted shift average as a multiplier; bilinear
cancellation handles it away from small rational frequencies; endpoint
Fourier energy handles the rest. Put hat_F(theta) = sum over w of
F(w) e(theta w) on R/Z. The multiplier in (8.18) is
M(theta) = E b_1(D_A) b_2(D_B) e(-k theta D_A D_B). (8.20)
Claim: for every fixed desired saving D_2, M is O(L^(-D_2)) outside the
MAJOR ARCS
Mset = union_(1 <= r <= L^(C_arc)) union_(u mod r) (8.21)
{ theta : dist_R/Z(theta, u/r) <= L^(C_arc)/H' },
if C_arc is large enough. To verify the coefficient hypothesis of Lemma
7.4, collapse a free product of size U_0 to integer weights rho(n).
Each group contributes at most m_probe slots. Unique factorization
bounds the multiplicity at n by prod_g(m_probe!), and the V_g
normalizations cost another fixed constant per slot. So rho(n) <=
L^O(1)/n and sum_n rho(n) = 1; for bounded tests,
sum over n = U_0 of |b(n) rho(n)|^2 << L^O(1)/U_0. (8.22)
Both free products are nonempty and each contains a big prime, so both
sizes exceed every fixed power of L.
Put Q_D = floor(H'/L^(C')). Dirichlet approximation to k theta gives a
reduced u'/r' with r' <= Q_D and |k theta - u'/r'| <= 1/(r' Q_D) <=
(r')^(-2), where 1/(r' Q_D) << L^(C')/(r' H'). If r' <= L^(C'),
division by k places theta on one of the arcs of (8.21) after increasing
C_arc; reduction can only decrease the denominator. Otherwise
L^(C') < r' << H'/L^(C'). The integer bilinear estimate of Lemma 7.4
then saves any prescribed log power by increasing C'. Parseval and
(8.19) handle the complementary contribution, including its 1/Y.
Put H = H'/L^(C_arc). On each arc it suffices to prove, for every fixed
A > 0,
int over |beta| <= 1/H of |hat_U(u/r + beta)|^2 d beta <<_A Y L^(-A).
(8.23)
Indeed |M| <= 1, and Cauchy-Schwarz with (8.19) gives L^(-A/2 + C_8/2)
per arc after division by Y. There are at most L^(2 C_arc + O(1)) arcs.
We establish (8.23) with A chosen after all these costs. Its proof uses
three features of the first endpoint: one small prime can be extracted
from its ordered marks, every factorization contains the long
rough-integer factor in (8.4), and the alpha coefficients satisfy (8.5).
8.4 ONE SMALL MARK AND THE RATIONAL CHARACTER EXPANSION.
Choose any small group g_s and a designated slot among its t_(g_s) =
ell >= 1 ordered marks. The endpoint mark weight is independent of the
small labels. Whenever no prime of P_(g_s) has its square dividing w,
removal of the prime in this slot gives the exact identity
W_t^b(w) = sum over p_s in P_(g_s), p_s | w of
(1/V_(g_s)) W_(t - e_(g_s))^b(w/p_s). (8.24)
Removing the designated slot is a bijection of the ordered lists; both
omega_(g_s) and t_(g_s) decrease by one. There is therefore no extra
factorial or damping factor. Both sides, even on the exceptional
integers, are L^O(1) by (8.3) and omega_(g_s)(w) = O(L). Since
w_* | w/p_s^2 on a square multiple, the squared norm of the error after
multiplication by F_0 is at most
L^O(1) sum over p_s in P_(g_s) of sum over w = Y, p_s^2 | w of
tau(w_*)^4
<< Y L^O(1) sum over p_s in P_(g_s) of p_s^(-2)
<< Y L^O(1) e^(-L^a). (8.25)
Every Y/p_s^2 = x^(1+o(1)). Parseval makes this error negligible in
(8.23).
After (8.24), combine the remaining P-part with the residual factor of
(8.4). The full integer factorization is w = m p_s p r, with residual
coefficient c_(r_*) W_(t - e_(g_s))^b(r). This identity uses that m and
p have no group factors. The residual coefficient is a function of r
alone, bounded by L^O(1).
All of m, p_s, p are units modulo the arc denominator r_0 <= L^(C_arc).
Separate residual factors by d_0 = gcd(r, r_0), put q_0 = r_0/d_0. On
units modulo q_0 the exact finite character expansion is
e(uv/q_0) = sum over chi mod q_0 of c_(u,q_0)(chi) chi(v), (8.26)
c_(u,q_0)(chi) = (1/phi(q_0))
sum over v mod q_0, gcd(v,q_0)=1 of
e(uv/q_0) conj(chi(v)).
Each coefficient has modulus at most one. Use this with
v = m p_s p (r/d_0); the condition gcd(r, r_0) = d_0 guarantees that v is
a unit modulo q_0. The factors chi(r/d_0) and the gcd restriction are
absorbed into the residual coefficient. Every character modulo the
actual quotient is included, so principal and imprimitive components
survive. The number of divisors and characters is a fixed log power,
and products with chi_0 have polylogarithmic modulus.
It now suffices to prove the local energy bound at zero for sequences
a_w = Psi_1(w/Y) w^(iv_1)
sum over mp_s p r = w of alpha_m chi_m(m) m^(i sigma_0) (8.27)
b_s(p_s) 1_(p in I_p, P^-(p) > W) chi_p(p) p^(i sigma_1) d_r,
with p_s in P_(g_s), |b_s| << 1, |d_r| <= L^O(1), all characters and
frequencies bounded by fixed log powers, and Psi_1 of the same smooth
size support as above. Fixed-order divisor moments give sum_w |a_w|^2
<< Y L^O(1).
8.5 FROM LOCAL FOURIER ENERGY TO A MELLIN INTEGRAL.
We record the scale conversion explicitly. Choose a smooth nonnegative K
of integral one, supported in a fixed neighborhood of zero small enough
that |hat_K(xi)| >= 1/2 for |xi| <= 1, using the Fourier convention with
e(-xi u). Plancherel on R gives
int over |beta| <= 1/H of |hat_a(beta)|^2 d beta (8.28)
<< H^(-2) int over R of |sum over w of a_w K((w-v)/H)|^2 dv.
Only v = Y contributes. Keep the integral on this range when replacing
K by K(v log(w/v)/H); no estimate near v = 0 is used. On the union of
the two kernels' supports within this range,
|w - v| << H, and their arguments differ by O(H/Y).
So, by Cauchy-Schwarz over O(H) integers and then integrating the centers
allowed for each w, the squared norm of the error in (8.28) is at most
<< (H/Y)^2 sum over w of |a_w|^2, (8.29)
which is smaller than Y L^(-A) for every fixed A, since H = x^o(1) and
Y = x^(1+o(1)).
Set h = H/Y and P(t) = sum over w of a_w w^(it). With v = Ye^u,
logarithmic Fourier inversion gives
sum over w of a_w K(v log(w/v)/H) = (h/(2 pi)) (8.30)
int over R of e^(-u) hat_K(h e^(-u) t/(2 pi)) v^(-it) P(t) dt.
Insert a smooth compactly supported rho(u) equal to one on the required
range. The Fourier transform in u of rho(u) e^(-u)
hat_K(h e^(-u) t/(2 pi)), denoted A(s, t), satisfies, for every fixed j,
|A(s, t)| <<_j (1+|s|)^(-2) (1+|ht|)^(-j). (8.31)
Two integrations by parts in u prove this, since hat_K is Schwartz and u
stays in a fixed compact interval. Fourier-expand in u, apply Minkowski
in s, and Plancherel in u for each s. As dv << Y du, the normalization
is H^(-2) Y h^2 = Y^(-1). Replacing j by a larger integer gives
int over |beta| <= 1/H of |hat_a(beta)|^2 d beta (8.32)
<<_j Y^(-1) int over R of (1+|ht|)^(-j) |P(t)|^2 dt
+ (H/Y)^2 sum over w of |a_w|^2.
By Lemma 4.2 (mean squares), for every dyadic time scale T' >= 1,
Y^(-2) int over T' <= |t| <= 2T' of |P(t)|^2 dt
<< (1 + T'/Y) L^(C_9). (8.33)
So the portion |t| > L/h in (8.32) is O(Y L^(-A)) after choosing j large
enough. For the remaining portion split the four factor variables in
(8.27) into dyads. There are O(L^4) boxes, and only those whose joint
size is comparable to Y contribute. Write
P(t)/Y = sum over w of (1/w) ((w/Y) Psi_1(w/Y)) w^(i(t+v_1)) (8.34)
sum over mp_s p r = w of (the four coefficients).
Fourier-separate the parenthesized cutoff in log coordinates: its
integral cost is a fixed log power, and truncating at a fixed log-power
frequency loses an arbitrary saving. The tails are bounded by the
preceding mean values. The frequency shifts enlarge |t| <= L/h to
|t| <= 2L/h, because 1/h exceeds every fixed log power. We have reduced
to
int over |t| <= 2L/h of |P_s(t) P_l(t) R(t)|^2 dt << L^(-A'), (8.35)
for every prescribed fixed A', on each retained box, where
P_s(t) = sum over p_s = P of b_s(p_s) p_s^(-1 + it), (8.36)
P_l(t) = sum over p = P', p in I_p, P^-(p) > W of
chi_p(p) p^(-1 + i sigma_1 + it),
R(t) = ( sum over m = M_0 of alpha_m chi_m(m)
m^(-1 + i sigma_0 + it) )
( sum over r = R_0 of d_r r^(-1 + it) ).
Here and below dyads may be intersected with their existing support. We
have
e^(L^a)/2 <= P <= e^(L^b), x^tau/2 <= P' <= x^eta,
P M_0 P' R_0 = Y. (8.37)
For any subproduct of these four polynomials, collapse its coefficients
to sum over n = U of c_n n^(it). Fixed-order divisor moments give
sum over n of |c_n|^2 << L^(C_10)/U. (8.38)
The marked-group coefficient count was already absorbed by (8.3), not by
a growing divisor order. Individually all these polynomials are also
L^O(1) in absolute value by their harmonic sums.
The remaining integral has three regimes. Most times are controlled by
the small-prime polynomial P_s: where |P_s(t)| is a small negative power
of L, the ordinary mean square of P_l R, of joint size Y/P, suffices.
The exceptional times occupy only Y^o(1) unit intervals. On these, at
large times, P_l is small by oscillation over its long rough-integer
range; a sparse mean square for R makes that saving sufficient. For |t|
bounded by a fixed power of L, the m factor in R is small by the
original discrepancy hypothesis (8.5).
8.6 EXCEPTIONAL TIMES AND A SPARSE MEAN SQUARE.
The split into ordinary and exceptional times, followed by high
prime-polynomial moments and a sparse mean-square estimate, follows the
method of Matomaki and Radziwill; compare Section 2.1 and Section 4,
Lemmas 8-9 of Matomaki-Radziwill 2016. The specific estimates needed
here are proved below; no short-interval theorem is invoked.
Fix a large constant A_s and let E = {t : |t| <= 2L/h, |P_s(t)| >
L^(-A_s)}. Outside E, the indicated gain and the mean square of P_l R,
of joint size Y/P, give closure. That mean square's length exceeds the
time range, since
(Y/P) / (2L/h) = H/(2 L P) -> infinity, (8.39)
by b < c and (8.17). So this part of (8.35) is O(L^(-2A_s + C_11)).
The next two lemmas use the standard prime-polynomial moment arguments;
compare Soundararajan 2009, Lemma 3 and its proof. The dependence on
the growing power is explicit.
LEMMA 8.5 (number of exceptional unit intervals). The set E meets at
most
exp(O(L^b + L^(1-a) log L)) = Y^o(1) (8.40)
intervals [j, j+1], uniformly in the bounded coefficients b_s.
PROOF. Choose a point of E in each occupied interval; split the interval
indices into three residue classes to obtain separated points. Put j_0 =
floor(log Y / log(2P)). The polynomial P_s(t)^(j_0) has indices at most
Y and coefficient-square sum at most
j_0! (sum over p_s = P of |b_s(p_s)|^2 p_s^(-2))^(j_0)
<= j_0! (C/P)^(j_0). (8.41)
Indeed an integer has at most j_0! ordered representations as a product
of j_0 primes; Cauchy-Schwarz on each fiber proves this even with
repeated primes.
For a polynomial Q(t) = sum over n <= Y of c_n n^(it) and unit-separated
points in [-O(Y), O(Y)], the unit-interval Sobolev inequality and
bounded overlap give
sum over j of |Q(t_j)|^2 (8.42)
<< int over -O(Y) to O(Y) of (|Q(t)|^2 + |Q'(t)|^2) dt
<< Y (log(2Y))^O(1) sum over n of |c_n|^2.
The last step uses Lemma 4.2. Differentiation multiplies a coefficient
by i log n, so the constants are independent of j_0. The range 2L/h is
o(Y). If N_E is the number of occupied intervals,
N_E << Y L^O(1) j_0! (C L^(2A_s)/P)^(j_0). (8.43)
Now j_0 = O(L^(1-a)) and log Y - j_0 log P = O(L^b + j_0) by the
definition with 2P. Taking logarithms and using log(j_0!) <=
j_0 log j_0 proves (8.40). [End]
LEMMA 8.6 (sparse residual mean square). For the occupied unit intervals
I_j of Lemma 8.5,
sum over j of sup_(t in I_j) |R(t)|^2 << L^(C_12). (8.44)
PROOF. The collapsed residual size is U = Y/(P P') >= Y^(1-eta-o(1)) >
Y^0.6 for large x, and its coefficient-square sum is L^O(1)/U by (8.38).
On a containing integer interval n = U the Gram kernel satisfies,
uniformly for |z| << Y,
|sum over n = U of n^(iz)| << U/(1+|z|) + Y^(1/2). (8.45)
For |z| < 1 this is trivial. For 1 <= |z| <= cU with small fixed c,
the phase z log n/(2 pi) has monotone first derivative of magnitude
comparable to |z|/U and less than 1/2; Lemma 4.3 gives O(U/|z|). For
cU < |z| << Y the second-derivative test gives O(|z|^(1/2) +
U |z|^(-1/2)) = O(Y^(1/2)).
Choose a maximum point of |R| in each closed I_j and again split the
indices into three residue classes; in each class the points are at
least unit separated. For R = Y^o(1) such points, the absolute row sums
of their Gram matrix are at most
C (U log(2Y) + R Y^(1/2)) << U log(2Y). (8.46)
The first term follows by grouping distances into unit intervals; the
second is absorbed by U > Y^0.6. Schur's bound on this Gram matrix,
applied to the map (c_n) -> (sum_n c_n n^(it_j))_j, gives
sum over j of |R(t_j)|^2 << U log(2Y) sum over n of |c_n|^2
<< L^O(1). (8.47)
Summing the three classes proves (8.44), including the suprema. [End]
8.7 CANCELLATION OF THE LONG ROUGH-INTEGER FACTOR.
The following estimate explains why every endpoint must carry a
rough-integer factor of positive power length.
LEMMA 8.7 (long rough-integer polynomial). Fix tau > 0, eta < 1/4,
C > 0, A > 0. Let x^tau/2 <= P' <= x^eta, J' an interval in [P', 2P'],
and chi a character of modulus at most L^C. If |sigma| <= L^C, then for
a sufficiently large fixed B_0, uniformly when L^(B_0) <= |t| and
|t + sigma| <= x^2,
| sum over n in J', P^-(n) > W of chi(n) n^(-1 + i(t+sigma)) |
<< L^(-A). (8.48)
The constant B_0 may depend on C, A, tau, eta.
PROOF. Set h_s = 2 ceil(T^2) and
D = W^(4 h_s + 2) = exp(O(sqrt L T^2)) = x^o(1). By Corollary 4.6 there
is a polynomial U(n) = sum_(d | n) lambda_d >= 1_(P^-(n) > W), with
coefficients |lambda_d| <= 1, supported on squarefree d <= D with primes
at most W, satisfying
sum over n in [P', 2P'] of (U(n) - 1_(P^-(n) > W)) (8.49)
<< P' e^(-h_s) + D.
The summand is nonnegative, so restriction to any J' preserves the
bound. Replacing roughness by U in the normalized sum costs
O(e^(-h_s) + D/P'), smaller than every fixed negative power of L. Also
sum over d of |lambda_d|/d <= prod_(p <= W) (1 + 1/p)
<< log W = sqrt L. (8.50)
Write q' for the character modulus. Terms with gcd(d, q') > 1 vanish.
For the rest, split n = dv with v = q' y + a mod q'; the character is
constant on a class. The y-variable ranges over an interval of size
N = P'/(dq') >= x^(tau/2) for large x. Put u = t + sigma. Taking
B_0 > C + 1 ensures |u| >= L^(B_0)/2. Claim: on every subinterval of
the allowed y-range,
| sum over y of exp(iu log(q'y+a)) | << N (|u|^(-1) + N^(-delta)), (8.51)
for a fixed delta > 0 depending only on tau.
If |u| <= cN, the monotone first-derivative test gives O(N/|u|): the
derivative of u log(q'y+a)/(2 pi) stays away from nonzero integers.
Otherwise put eps_0 = 1/10. The overlapping ranges
N^(k-2+eps_0) <= |u| <= N^(k-eps_0), k >= 2, (8.52)
cover cN < |u| <= x^2 using 2 <= k <= K = ceil(4/tau) + 3. The k-th
derivative of the phase has constant sign and magnitude comparable to
|u| N^(-k). For k = 2 the second-derivative test directly saves a
positive power. For k > 2 the van der Corput differencing inequality
is applied k-2 times with positive integer shifts at most
H_0 = floor(N^(eps_0/(2k))). After shifts h_1,...,h_(k-2), the second
derivative is an iterated integral of the k-th derivative, hence of
constant sign and magnitude comparable to
|u| N^(-k) h_1 ... h_(k-2),
between c_k N^(-2+eps_0) and C_k N^(-eps_0/2). (8.53)
On an interval of length m <= CN the second-derivative bound gives
O(m lambda^(1/2) + lambda^(-1/2)) << N^(1 - eps_0/4). (8.54)
To justify the estimate uniformly for short subintervals, extend each
sequence by zero in a containing interval of length O(N). The
differencing inequality for its normalized sum has the form
B_j^2 << H_0^(-1) + B_(j+1), where B_(j+1) bounds the average of the
absolute normalized correlations. Their supports are intersections of
translates of the original interval, hence again intervals. All shifts
are o(N), preserving the derivative bounds. Iterating from the final
exponent eps_0/4 proves a bound O(N^(-delta_k)) for the original
normalized sum, with delta_k = eps_0/(k 2^(k-1)). Taking
delta = eps_0/(K 2^(K-1)) proves (8.51) in every case. The differencing
inequality itself follows by averaging H_0 translates and applying
Cauchy-Schwarz; its zero-shift term is the stated O(H_0^(-1)).
Partial summation of 1/[d(q'y+a)] costs O(1/P') times the uniform
unweighted bound; summing the at most q' classes gives
| sum over n in J', d | n of chi(n) n^(-1+iu) |
<< d^(-1) ( |u|^(-1) + x^(-tau delta/2) ). (8.55)
Finally (8.50) bounds the total by
O(e^(-h_s) + D/P') + O(sqrt L ( L^(-B_0) + x^(-tau delta/2) )).
(8.56)
Choosing B_0 > A + 2 in addition to its previous constraint proves
(8.48). [End]
8.8 COMPLETION AND ORDER OF PARAMETERS.
We finish (8.35). Outside E it is O(L^(-2A_s + C_11)); choose A_s
sufficiently large. On the exceptional intervals with |t| >= L^(B_0),
Lemma 8.7 gives an arbitrarily strong uniform bound for P_l. Its range
condition holds since 2L/h = o(Y) = x^(1+o(1)) < x^2/2, and the fixed
frequency shift does not change this. The polynomial P_s is bounded,
and Lemma 8.6 gives
int over E cap {|t| >= L^(B_0)} of |P_s(t) P_l(t) R(t)|^2 dt
<< ( sup over |t| >= L^(B_0) of |P_l(t)|^2 ) L^O(1). (8.57)
Here the sup is over the actual time range, and each occupied interval
has length one. Choose the saving in Lemma 8.7 after the exponent in
Lemma 8.6.
For the remaining |t| <= L^(B_0) use (8.5) on the m polynomial in R.
The retained dyads satisfy P M_0 P' R_0 = Y, so m << Y = x^(1+o(1)) <
x^2 for large x, also after smooth-cuttoff separation. Its character
modulus is a fixed log power, and its frequency is t + sigma_0. A
single sufficiently large B therefore bounds this polynomial by L^(-B)
throughout the range. Every other factor has absolute value L^O(1), and
the length of this time interval is 2 L^(B_0). The resulting integral is
L^(-2B + B_0 + O(1)), giving the required accuracy. This proves (8.35),
then the local energy bound (8.23) via (8.32), and hence every comparison
bound. The residual pairing and the raw identity in (8.16) prove (8.6).
For completeness, the choices occur in this order. First fix the
endpoint bounds, group geometry, cutoff derivative bounds, and desired
saving D_0. The uniform endpoint norm bound fixes the physical transfer
target and its required ideal target; the fixed Mellin cutoff fixes the
ideal frequency range. Next choose the probe count and comparison
parameters of Theorem 7.1, then the fixed J required by transference.
All pattern, cell, and absolute norm costs are now determined. Choose
the separation accuracies, arc exponent, local energy target, and Mellin
tail precision. Next choose A_s, the accuracy of the long rough
polynomial and its B_0. Finally choose one B in (8.5) exceeding all the
modulus, frequency, and low-time saving requirements, and let x tend to
infinity. The residual L^2 bounds used before the choice of J depend
only on the endpoint coefficient bounds and a fixed divisor moment.
Increasing later Fourier tail accuracies uses more integrations by
parts, with no enlargement of the already fixed ideal frequency range.
None of these choices is circular.
This completes the proof of Theorem 8.1.
9. A TYPE II ESTIMATE
We apply the shifted-correlation estimate to factorizations mn = 2u+1,
where u carries a weight supported on many geometric prime bands. The
coefficient of m will satisfy the discrepancy hypothesis (8.5); the
coefficient of n may be arbitrary within its stated bound. The task is
to retain the discrepancy while converting multiplicative factorizations
into additive correlations.
We split u = eh, with e slightly smaller than the scale of m, using a
smooth allocation of the band primes. Cauchy's inequality in (e, n)
then has a small enough outside factor to control its diagonal. Off the
diagonal the two factorizations give cross-products whose difference is
a small nonzero integer. These are the shifted endpoints. All group
factors and the compulsory rough integer are assigned to h, so both
endpoints retain the form (8.4).
9.1 THE WEIGHT AND THE UNIFORM STATEMENT.
Use the prime groups and the marked weight W_ell of section 8. In
particular, disjoint groups, masses in [v_-, v_+], both kinds of groups
with counts between c_0 T and C_0 T. For fixed 0 < a < b < c < d <
0.47, the small primes lie in [exp(L^a), exp(L^b)], the big in
[exp(L^c), exp(L^d)], with the interval structure required there. The
damping q in (0,1) and the integer ell >= 1 are fixed. Write u_* for
the factor of u supported outside all groups and u_P = u/u_*; then
W_ell(u) = prod_g q^(omega_g(u) - ell) (9.1)
((omega_g(u))_ell / V_g^ell).
Fix 0 < c_1 < c_2, s' > 0, lambda > 1, with c_2 s' < 1/4. For
0 <= j <= j_x put
s_j = s' L lambda^(-j),
Q_j = { p prime : c_1 s_j <= log p <= c_2 s_j }. (9.2)
Assume these intervals are pairwise disjoint and disjoint from the prime
groups, and c_- T <= s_(j_x) <= c_+ T for fixed 0 < c_- <= c_+. Choose
a fixed integer r_0 such that
(r_0 - 1) c_1 / lambda >= c_2 + 1. (9.3)
There are r_0 labelled slots in every band, each normally taking a prime
in Q_j with repetitions allowed. In one specified slot of a fixed band
j_** replace the prime by an integer in
I_** = [x^(tau_*), x^(eta_*)], P^-(p) > W, (9.4)
tau_* = c_1 s' lambda^(-j_**), eta_* = c_2 s' lambda^(-j_**).
The notation p for this slot never asserts primality. For large x this
slot is free of group primes, since exp(L^d) < W.
Define
a_Q(v) = (prod_(j=0)^(j_x) 1/r_0!) (9.5)
#{admissible labelled slot lists with product v},
A(u) = a_Q(u_*) W_ell(u).
The exceptional integer can be fixed as a divisor of v. Thereafter the
prime multiplicities in each disjoint band determine the list up to at
most r_0! permutations. Consequently
0 <= a_Q(v) <= tau(v), 0 <= A(u) <= L^(C_A') tau(u_*), (9.6)
sum over v of a_Q(v)/v <= L^(C_A'),
for a fixed exponent C_A'. The bound for W_ell follows by maximizing
q^(t-ell) (t)_ell / V_g^ell in each group. For the last bound, factor
the harmonic sum slot by slot: every prime slot has bounded harmonic
mass, the exceptional slot has mass O(L), and there are O(T) slots. The
exponent depends only on the fixed data.
THEOREM 9.1 (Type II). Fix D_* > 0, b_* > 0, C > 0, and require
eta_* < b_*/4 in (9.4). Let U, V be dyadic scales with
UV = x, x^(b_*) <= U, V <= x^(1 - b_*). (9.7)
Let Psi be a fixed smooth function with compact support in a fixed
compact subinterval of (0, infinity). Suppose |alpha_m|, |beta_n| <=
L^C and alpha_m = 0 unless P^-(m) > W. There is a fixed exponent B,
depending only on these data and the fixed group and band constants,
such that the discrepancy hypothesis (8.5) on alpha implies
sum over m = U, n = V, u >= 1, mn = 2u+1 of (9.8)
A(u) Psi(u/x) alpha_m beta_n << x L^(-D_*).
The sequence to which (8.5) is applied includes the actual restriction
m = U and any additional interval restriction on m; explicitly, for
that restricted sequence,
| sum over m in I of alpha_m chi(m) m^(it) / m | <= L^(-B) (9.9)
for I in [1, x^2], chi of modulus at most L^B, and |t| <= L^B. There
is no discrepancy hypothesis on beta. The constants are uniform over
the sequences, scales, and interval restrictions.
9.2 REMOVING A LARGE GROUP-PRIME FACTOR.
PROOF OF THEOREM 9.1. First discard u_P > x^(b_*/4), with an error
smaller than every fixed negative power of L times x. Set theta =
L^(-d). For one group write a_p = (p^(1-theta) - 1)^(-1). Since
p^theta <= e and the group primes tend to infinity, a_p <= 2 e/p. The
tilted marked harmonic sum is
sum over v whose prime factors are all in P_g of (9.10)
q^(omega_g(v) - ell) (omega_g(v))_ell / (V_g^ell v^(1 - theta))
= V_g^(-ell) prod_(p in P_g) (1 + q a_p)
sum over p_1,...,p_ell in P_g, distinct ordered of
prod_(i=1)^ell a_(p_i) / (1 + q a_(p_i))
<= C_0.
The last constant is fixed because v_- <= V_g <= v_+. Taking the
product over O(T) groups gives
sum over v > x^(b_*/4), v_* = 1 of W_ell(v)/v
<= exp( -(1/4) b_* L^(1-d) ) L^(C_1). (9.11)
On the support of (9.8), u = x. The number of divisors m of 2u+1 all of
whose prime factors exceed W is at most 2^(log(2u+1)/log W) =
exp(O(sqrt L)). Using (9.6) and (9.11), multiplying the harmonic mass
by O(x), and using 1 - d > 1/2, the total discarded contribution is at
most
x L^(C_2) exp( -(1/4) b_* L^(1-d) + O(sqrt L) ). (9.12)
Call the remaining slot tuples good. This estimate is independent of
the splitting precision introduced next.
9.3 A SMOOTH PARTITION INTO TWO FACTORS.
Put E = U L^(-K_0), where the fixed integer K_0 is chosen after the
splitting costs have been bounded. Our target is a weighted partition
into factorizations u = eh with
E L^(-C_s) <= e <= E, (9.13)
where C_s depends only on the band constants. The reason for placing e
below U is that Cauchy's inequality will contribute an outside factor
EV = x L^(-K_0). We will use this logarithmic saving to control the
diagonal, so the splitting costs must be independent of K_0.
Allocate all of u_P and the exceptional integer slot to h; this
preserves the group weight and the long rough factor at every shifted
endpoint. Process the remaining prime slots in increasing band index,
and in a fixed order within each band. Write v_i = log p_i and let
s_(j(i)) be the scale of slot i. If delta_i in {0,1} records whether
slot i is allocated to e, put
R_i = log E - sum_(t<i) delta_t v_t. (9.14)
Fix gamma in C^infty(R) with 0 <= gamma <= 1, gamma(t) = 0 for t <= 0,
gamma(t) = 1 for t >= 1. At slot i take it into e with probability
gamma((R_i - v_i)/s_(j(i))); otherwise into h.
Verify (9.13) by tracking the unfilled logarithmic size. At every stage
the induction target is
0 <= R_i <= sum_(t >= i) v_t + (c_2 + 1) s_(j_x). (9.15)
The terminal allowance accounts for a skip in the final band. On a good
tuple the factors assigned to h before the procedure starts have product
at most x^(b_*/2). The sum of the available prime logarithms is
therefore at least (1 - b_*/2) L + O(1), whereas 0 < log E <=
(1 - b_*) L - K_0 T for large x. This proves the initial bound even
without the terminal allowance. Taking a slot of positive probability
requires R_i > v_i and subtracts v_i from both the residual and the
available logarithm, so it preserves the bound and nonnegativity.
Skipping a slot of positive probability requires
R_i < v_i + s_(j(i)) <= (c_2 + 1) s_(j(i)). (9.16)
If a later band exists, its unprocessed prime slots have total logarithm
at least (r_0 - 1) c_1 s_(j(i)+1) >= (c_2 + 1) s_(j(i)) by (9.3). The
subtraction of one slot covers the possible exceptional integer in that
later band. So after such a skip the residual fits inside the remaining
available logarithm. In the final band a skip leaves at most
(c_2 + 1) s_(j_x), and subsequent operations cannot increase this
residual. This proves (9.15). After processing the last slot it gives
0 <= log E - log e <= (c_2 + 1) s_(j_x). (9.17)
Since s_(j_x) <= c_+ T, this proves (9.13) with C_s = (c_2 + 1) c_+.
The geometric series for the remaining band scales bounds
R_i/s_(j(i)) by a fixed constant; both bounds are independent of K_0.
Choose a fixed smooth compactly supported rho with values in [0,1],
equal to one throughout the possible range of (R_i - v_i)/s_(j(i)).
Replace the two transition functions by f_1 = rho gamma and
f_0 = rho (1 - gamma). This changes no branch on a good tuple. For an
arbitrary tuple the sum is rho <= 1, so its total branch mass is at most
one. Insert the resulting partition into (9.5), keeping every original
factorial normalization. Branches sum to one on good tuples, and
extending back to all tuples costs at most the error in (9.11). Every
resulting h contains the exceptional rough integer.
Quantitative detail of the smooth separation, independent of K_0. Let
N = O(T) be the number of processed slots, and use the Fourier
convention f(t) = (1/(2 pi)) int hat_f(xi) e^(i xi t) d xi. Choose a
fixed C_F >= 1 bounding the Fourier L^1 norms of both f_0, f_1, with
the normalization (1/(2 pi)) included. Summing the Fourier total
variations over the 2^N patterns gives at most (2 C_F)^N = L^O(1). For
the truncation: capping each |xi_i| at L has total error, for every
fixed M, at most
2^N N C_M C_F^(N-1) L^(-M). (9.18)
Thus any prescribed power saving is available. In a fixed pattern the
product of Fourier exponentials is a scalar of modulus one times
prod_t p_t^(i sigma_t), where
sigma_t = -xi_t / s_(j(t)) - delta_t sum_(i>t) xi_i / s_(j(i)). (9.19)
Indeed the scalar is exp(i log E sum_i xi_i / s_(j(i))). Since
sum_i 1/s_(j(i)) << 1/T, all frequencies in (9.19) are O(L/T).
Everything in this paragraph is independent of K_0.
Separate Psi(eh/x) by Fourier inversion in log(eh/x) as well. Its
Fourier L^1 norm is fixed, and the tail outside frequency L has
arbitrary power saving; its two factors are powers of e and h. All
these errors can be summed before Cauchy's inequality. Indeed, the
absolute sum over the original factorizations is bounded by
L^O(1) sum over u = x of tau(u) tau(2u+1) << x L^O(1) (9.20)
by Cauchy-Schwarz and divisor moments. The same estimate applies to
each uniform transition or cutoff error, using the total Fourier
variations of the other factors. So the original sum is, up to
O(x L^(-D_* - 1)), an integral and a sum of total variation at most
L^(C_f) of expressions
B_0 = sum over E L^(-C_s) <= e <= E, n = V of (9.21)
a_e(e) beta_n sum over m = U, h >= 1, mn = 2eh+1 of alpha_m a_h(h).
The exponent C_f and every coefficient exponent below are independent of
K_0:
|a_e(e)| <= L^(C_a), (9.22)
a_h(h) = h^(i varrho) W_ell(h) H(h_*),
H(t) = sum over pr = t of 1_(p in I_**, P^-(p) > W) p^(i sigma) c_r,
|c_r| <= L^(C_a).
In particular |a_h(h)| <= L^O(1) tau(h_*). Only group-free prime slots
go into e, so (eh)_* = e h_* and W_ell(eh) = W_ell(h). For a fixed
pattern, the number of ordered pure-prime lists at a fixed product is at
most (r_0!)^(j_x + 1) = L^O(1). This proves both the a_e bound and the
bound for the residual coefficient c_r. Fixing the exceptional integer
as a divisor gives the bound for a_h. Individual slot twists have
modulus one; the common power of h from the cutoff is h^(i varrho). The
frequencies varrho, sigma have fixed power bounds in L.
9.4 CAUCHY'S INEQUALITY AND THE DIAGONAL.
By Cauchy-Schwarz in (e, n), (9.21) satisfies
|B_0|^2 <= EV L^(C_3) Nn, (9.23)
Nn = sum over e, n of eta_e(e/E) eta_n(n/V)
|sum over m = U, h, mn = 2eh+1 of alpha_m a_h(h)|^2.
Here eta_e, eta_n are nonnegative smooth majorants, bounded by a fixed
constant, equal to one on the original ranges. They vanish unless
(1/2) E L^(-C_s) <= e <= 2E and n = V. Their derivatives of order j in
their displayed arguments are O_j(L^(C_4(j+1))), with C_3, C_4
independent of K_0. For example, the lower edge of eta_e is obtained by
rescaling a fixed smooth cutoff by L^(C_s).
On the diagonal m = m' the two equations force h = h'. For fixed m, n
the allowable e divide (mn - 1)/2, and
sum over e | (mn - 1)/2 of tau( (mn - 1)/(2e) )^2
<= tau(mn - 1)^3. (9.24)
Collecting by v = mn and using divisor moments gives
Nn_diag << L^O(1) sum over v = x of tau(v) tau(v - 1)^3
<< x L^(C_5). (9.25)
The exponents C_3, C_5 are independent of K_0. Since EV =
x L^(-K_0), its contribution to |B_0|^2 is O(x^2 L^(-K_0 + C_3 + C_5)).
We can therefore fix K_0 large enough that its square root, even
multiplied by L^(C_f), is O(x L^(-D_* - 1)). All subsequent precisions
may depend on this fixed K_0.
9.5 THE EXACT DETERMINANT PARAMETRIZATION.
Consider an off-diagonal term of (9.23), with
mn = 2eh + 1, m'n = 2eh' + 1, m != m'. (9.26)
The shared variables e, n force the two m values to be congruent modulo
2e: the first equation makes n a unit modulo 2e, and subtracting the
equations gives 2e | m' - m. Write m' - m = 2ek, with k != 0. The
resulting identities are
m' - m = 2ek, h' - h = kn, z = m'h, z + k = mh'. (9.27)
The last follows from mh' - m'h = k(mn - 2eh) = k. The enlarged e-range
gives
0 < |k| << L^(K_0 + C_s). (9.28)
Conversely, fix such a k, positive integers m, m', h, h' with
P^-(m), P^-(m') > W, and representations m'h = z, mh' = z+k. Suppose
m' = m mod 2|k| and e = (m' - m)/(2k) > 0. Then e is an integer and
m(h' - h) = k(2eh + 1). (9.29)
Every prime factor of m exceeds W, whereas |k| is bounded by a fixed
power of L, so gcd(m, k) = 1 for large x. Equation (9.29) implies
m | 2eh + 1. Set n = (2eh + 1)/m, a positive integer. The same
identity gives h' - h = kn, and substituting m' = m + 2ek recovers the
second equation of (9.26). This proves a bijection, with all variables
recovered by the displayed formulas. In particular, no additional
divisibility condition is being dropped. The coprimality gcd(m, k) = 1
is necessary to this converse.
Both m and m' are units modulo q_k = 2|k|, so the congruence is imposed
exactly by
1_(m' = m mod q_k) = (1/phi(q_k)) sum over chi mod q_k of (9.30)
chi(m) conj(chi(m')).
Thus Nn_off is a sum over k, z and these characters of terms having
coefficient
alpha_m conj(alpha_(m')) chi(m) conj(chi_(m')) (9.31)
a_h(h) conj(a_h(h')),
with m'h = z, mh' = z+k, and with the enlarged smooth (e, n) cutoffs.
The arguments are now the exact functions
e = (m' - m)/(2k), n = (m' - m) z / (k m m') + 1/m. (9.32)
The cutoffs are extended smoothly by zero to nonpositive arguments, so
they impose the positivity and size conditions as well.
9.6 SMOOTH SEPARATION AND THE SHIFTED ENDPOINTS.
On the resulting support, m, m' = U, n = V, and h = x/e. So z = m'h
lies in [x L^(-C_6), x L^(C_6)] with a fixed C_6 now allowed to depend
on K_0. Insert a smooth dyadic partition in z with O(T) terms,
denoting one scale by Z = x L^O(1); keep its smooth cutoff psi_Z(z/Z)
outside the Fourier expansion.
Regularity of the pulled-back cutoffs. Put t_1 = log(m/U),
t_2 = log(m'/U), t_3 = log(z/Z). Multiply by fixed smooth localizations
in these three variables equal to one on the ranges in use. From
(9.32) every derivative of e/E in these variables is O_j(U/(|k| E)),
and every derivative of n/V is O_j(Z/(|k| U V) + (U V)^(-1)). Both are
bounded by fixed powers of L; moreover the normalized derivatives of
eta_e, eta_n have the bounds already given. Repeated use of the chain
rule therefore bounds derivatives of the localized product cutoff by
O_j(L^(C_7(j+1))). Its support in (t_1, t_2, t_3) is a fixed compact
box. Fourier inversion, as in Lemma 4.4, represents it with total
variation L^O(1) as a superposition of
m^(i xi_1) (m')^(i xi_2) z^(i xi_3). (9.33)
Explicit tail estimate. Enlarge a fixed exponent C_8 so that, with
P = L^(C_8), the localized cutoff F satisfies
||partial^alpha F||_infty <<_alpha P^(|alpha|); its zeroth derivative
is bounded independently of L. Integration by parts gives
|hat_F(xi)| <<_j (1 + |xi|/P)^(-j), (9.34)
int over R^3 of |hat_F(xi)| d xi << P^3,
int over |xi| > PL of |hat_F(xi)| d xi <<_j P^3 L^(3-j).
So truncation at PL has uniform error O(L^(-A)) for every fixed A, by
choosing j > A + 3 C_8 + 3. These later exponents may depend on K_0.
There is sufficient absolute control to sum these errors. If the
coefficients in (9.22) and the two m sequences are replaced by their
absolute values, each resulting endpoint convolution is at most
L^O(1) tau(z_*)^2. Its product with W_ell(z) has squared sum
O(Z L^O(1)) on z = Z. Cauchy-Schwarz, also at z+k, therefore bounds
the absolute correlation by Z L^O(1). This uses only divisor moments.
It remains true after dropping the congruence; hence it controls the
errors just described, after summing the polynomial number of k values,
dyads, and character terms.
Identify the endpoints so as to track exactly which sequence satisfies
discrepancy. Use the notation of (9.22) and fix a character chi and
frequencies in (9.33). Since m, m' are free of group primes,
z_* = m' h_*, (z+k)_* = m h'_*, (9.35)
W_ell(z) = W_ell(h), W_ell(z+k) = W_ell(h').
Define the invariant endpoint functions
F_0(v) = sum over mpr = v_* of (9.36)
alpha_m chi(m) m^(i(varrho - xi_2))
1_(p in I_**, P^-(p) > W) p^(-i sigma) conj(c_r),
G_0(v) = sum over mpr = v_* of
alpha_m chi(m) m^(i(xi_1 + varrho))
1_(p in I_**, P^-(p) > W) p^(-i sigma) conj(c_r).
Direct substitution shows the separated summand is
psi_Z(z/Z) z^(i(varrho + xi_3)) (z+k)^(-i varrho) (9.37)
conj(F_0(z)) G_0(z+k) W_ell(z) W_ell(z+k),
up to scalar phases of modulus one and the Fourier coefficient. For
example, at z = m'h the factor h^(i varrho) becomes
z^(i varrho) (m')^(-i varrho), which explains the first endpoint's
power and the conjugation of c_r. In particular, the sequence inside
F_0 is the original alpha, with its actual interval restriction.
Both functions in (9.36) have the form (8.4). The character modulus
2|k|, all power frequencies, and the coefficient bounds are fixed
powers of L. The interval I_** lies in [x^tau, x^eta] for fixed
0 < tau < eta < 1/4, by (9.4) and the hypothesis eta_* < b_*/4. The
residual c_r has a fixed power bound, and no roughness condition on r is
needed. The original alpha is supported on W-rough integers and
satisfies (8.5); the explicit character and power factors are precisely
those permitted in (8.4). Thus the discrepancy hypothesis has not been
silently transferred to a new coefficient sequence.
Finally set tilde_psi_Z(t) = t psi_Z(t). The last unweighted
correlation equals Z times
sum over z > 0, z + k > 0 of (tilde_psi_Z(z/Z)/z) (9.38)
z^(i(varrho + xi_3)) (z+k)^(-i varrho)
conj(F_0(z)) G_0(z+k) W_ell(z) W_ell(z+k).
This is (8.6), including its harmonic normalization. Given any fixed
D_0, Theorem 8.1 bounds it by L^(-D_0) once the discrepancy exponent B
is sufficiently large. Consequently every separated unweighted
correlation is O(Z L^(-D_0)). Choose D_0 after K_0, the k-range, all
separation costs, and the desired saving in (9.23). The total
off-diagonal contribution is then O(x L^(-A)) for any prescribed fixed
A. Choose B after this application of Theorem 8.1. Together with
(9.25), this gives |B_0| << x L^(-D_* - C_f - 1). Summing its
pre-Cauchy expansion and the previously estimated tails proves (9.8).
[End]
REMARK 9.2 (order of precisions). The band constants, j_**, b_*, the
coefficient bound C, and the target D_* are fixed first. The transition
functions, their total variation, and the coefficient and diagonal
exponents are independent of K_0; only then is K_0 chosen. The smooth
separation after Cauchy's inequality and the accuracy required from
Theorem 8.1 are fixed next, and the required discrepancy exponent B is
fixed last. Accordingly, when alpha is the difference between a test
and its rough-integer proxy, the precision of the cells defining that
proxy may be chosen after B, provided the proxy's coefficient bound is
already uniform in that cell precision. This is the order used in
section 10.
10. PRIME EXTRACTION I: CANDIDATES, TYPE I, PROXIES, AND TWO SIEVES
Section 8 produced the shift correlation of Theorem 8.1, and section 9 used
it to prove the Type II estimate of Theorem 9.1. This section and section
11 use those inputs, together with Type I and the elementary sieve, to
count W-rough predecessors of primes and then prove Theorem B. The pass
from "rough predecessor" to "prime" has four separate pieces:
10.1-10.3: the candidate set, its mass, and the marked Euler factor.
10.4: Type I: equidistribution of 2u+1 in residue classes mod r for
all moduli r up to the sieve level.
10.5: the density of ordinary x^(b_1)-rough integers in (x,2x], by the
one-prime contribution and the block sieve upper bound.
10.6: the proxy that Type II compares against, and its discrepancy.
10.7: the balanced composite contribution, whose two large prime
factors are both near x^(1/2) and are invisible to Type II.
Section 11: assembling the sieve, Type I, Type II, and the balanced
bound into Theorem B. Section 12: Theorem A from Theorem B.
10.1 GEOMETRIC SETUP.
Fix c_1 = 1, c_2 = 6/5, c_3 = 3/2, c_4 = 9/5, and r_0 a positive integer
so large that, with s' = 1/(r_0 (c_1 + c_2)),
c_2 s' < delta, (r_0 - 1) c_1 / 2 >= c_2 + 1. (10.1)
For example r_0 = 6 always works when 0 < delta < 1/11. Put
s_j = s' 2^(-j) L, Q_j = { p : c_1 s_j <= log p <= c_2 s_j }, (10.2)
for 0 <= j <= j_x, where j_x is the largest integer for which
c_1 s_{j_x} >= 20 T.
Disjointness. Since c_2 = 6/5 < 2 c_1 = 2, Q_j and Q_(j-1) are
disjoint and separated. Since c_3 = 3/2 > c_2 = 6/5, Q_j and P_g for
any g at the same scale are disjoint. Consecutive scales are doubled;
c_3, c_4 < 2 c_3 mean that the P-groups at scale j and scale j-1 are
also disjoint, and c_3 > c_4/2 means that Q_j and P_(j-1) are disjoint.
So all bands and groups are pairwise disjoint. The number of bands with
either small or big primes is between c_0 T and C_0 T for fixed c_0, C_0,
because the j-range has length (1/10) log_2 L + O(1) = c_1' T + O(1).
The prime groups of both kinds. For each fixed scale j such that the
log-interval [c_3 s_j, c_4 s_j] lies wholly inside either [L^(1/10),
L^(1/5)] or [L^(3/10), L^(2/5)], let P_g be the set of primes whose log
lies in that interval: small in the first case, big in the second. Their
harmonic masses obey
V_g = sum over p in P_g of 1/p
= (c_4 - c_3) s_j (1 + o(1)) = (3/10) s_j (1 + o(1)), (10.3)
so v_- <= V_g <= v_+ for fixed v_-, v_+ > 0.
The candidate integers. There are r_0 ordered prime slots per Q-band.
One designated slot, in a fixed band j_** chosen once and for all with
j_** >= j_0, is the rough-integer slot: instead of a prime in Q_(j_**)
it takes an arbitrary integer v in [x^(tau_*), x^(eta_*)] with
P^-(v) > W, where lambda = 2, tau_* = c_1 s' lambda^(-j_**) and
eta_* = c_2 s' lambda^(-j_**). Note W = exp(sqrt L) > exp(L^(2/5)) >
exp(c_4 s_0)>= exp(c_4 s_j), so the rough slot is disjoint from every
group and from every Q-band. A candidate has form
u = v · (product of Q-primes, r_0 per band) ·
(product of P-primes, at most one per group),
u_* = v · (product of Q-primes). (10.4)
10.2 THE CANDIDATE MASS.
Let a_Q, A be as in (9.5), (9.3). Put ell = 1 in (9.1) so W_1 is the
damping associated with the marked P-divisors, and set
X_A = sum over u of A(u) Psi(u/x), (10.5)
H_Q = sum over v of a_Q(v) / v,
H_P = sum over r: r_* = 1 of W_1(r) / r.
Recall from (9.6) that 0 <= A(u) <= L^(C_A') tau(u_*) pointwise.
PROPOSITION 10.1 (candidate mass). There are constants C, C_A
depending only on the early candidate choices such that, for sufficiently
large x after fixing j_**,
0 <= A(u) <= L^C tau(u_*), A(u) <= exp(C sqrt L) (u = x), (10.6)
H_P = exp( q sum_g V_g + o(1) ), (10.7)
X_A = (x/L) H_Q H_P (1 + o(1)) >> x L^(-C_A). (10.8)
On the support of A(u) Psi(u/x) every prime divisor of u lies in
[L^20, x^delta].
PROOF. The first line of (10.6) is the bound (9.6). The second: for
v = x, any possible rough-slot divisor divides the part of v supported
on primes > W, which has at most O(L/log W) = O(sqrt L) prime factors
counted with multiplicity, hence at most exp(O(sqrt L)) divisors. This
is A(u) <= L^(O(1)) exp(O(sqrt L)) for the pointwise factor W_1 <= L^C
and the tau factor.
(10.7). For one group, the marked Euler factor is
F_g(q) = prod over p in P_g of (1 + q/(p-1)). (10.9)
Summing the geometric series over the powers of the p in P_g shows that
the factor of g in H_P is
(1/V_g) sum over p in P_g of 1/(p - 1 + q) · F_g(q). (10.10)
Each prime factor contributes exp(q/(p-1) + O(p^(-2))). Since V_g is
bounded above and below, and since sum over all p in any group of
1/p^2 <= T exp(-2 L^(1/10)) = o(1), we have
F_g(q) = exp( q V_g + o(1/T) ). (10.11)
...
...
10.3 THE MARKED EULER FACTOR AND THE USEFUL INEQUALITY.
Two consequences are worth isolating.
The lower comparison. From (10.10) and p - 1 + q <= p,
H_P >= prod over p in any P-group (1 + q/(p-1)). (10.15)
The mask comparison. Suppose an integer u has an ordered list of
distinct P-prime divisors p_(g,1) in each group g, at most one in each
group. Then the damping factor q^(omega_P(u) - s_P) that W_1 assigns to
u is exactly the probability that an independent Bernoulli(q) random
subset of the usable P-groups is a sub-list of the given one. This
identification is used in section 10.9 when we form the mask majorant of
A(u); it is the reason the damping is exactly q^(omega_g - 1) per group
and not some other function.
10.4 CONGRUENCE DISTRIBUTION AND TYPE I.
For odd squarefree d define the remainder
r(d) = sum_{d | N_u} A(u) Psi(u/x) - X_A / phi(d), (10.16)
where N_u = 2u + 1. The main term X_A/phi(d) is the natural harmonic
density in each reduced class.
PROPOSITION 10.2 (Type I distribution). For every fixed
0 < theta < 1/2 and every D > 0,
sum over 1 <= d <= x^theta, d odd and squarefree of |r(d)|
<< x L^(-D) + X_A L^(-18). (10.17)
PROOF. The congruence 2u+1 = 0 mod d specifies a unit class for u,
since d is odd. Use character orthogonality on that class. Replacing
the principal coprime mass by X_A has total cost at most X_A L^(-18),
because for each supported u
sum over d <= x^theta, (d,u) > 1 of mu^2(d)/phi(d) (10.18)
<= ( sum over p | u of 1/(p-1) )
( sum over d' <= x of mu^2(d')/phi(d') ) << L^(-18).
Here every p | u is at least L^20 by (10.6), there are at most
O(L/log L) such primes, and the last sum is O(L) by its Euler product
and Mertens. So the main terms combine to X_A/phi(d) on the coprime
class.
Extract one fixed Q_0 slot, as in the proof of Proposition 10.1, to
write
A(u) = sum over pr = u, p in Q_0 of b(r), 0 <= b(r) <= L^O(1)
tau(r). (10.19)
Split p, r into dyads of sizes P, U with P U = x. There is a fixed
a > 0 such that x^a << P, U << x^(1-a) in every contributing dyad.
Character decomposition. A nonprincipal character modulo squarefree d
is induced by a primitive nonprincipal character modulo f > 1, where
d = h f and (h, f) = 1; it acts as that primitive character together
with the restrictions (p, h) = (r, h) = 1, and phi(d) = phi(h) phi(f).
Large conductors. Fix h. On conductors f = R > L^(C'), separate
Psi(pr/x) by Mellin inversion, which has bounded integrated absolute
cost. For each twist, the large sieve, Cauchy-Schwarz, and divisor
moments give
sum over f = R of (1/phi(f)) sum over chi mod f, primitive of (10.20)
|sum over p = P of a_p chi(p)| |sum over r = U of b_r chi(r)|
<< L^O(1)/R · sqrt( (P + R^2)(U + R^2) P U )
<< x L^O(1) ( R^(-1) + P^(-1/2) + U^(-1/2) + R/sqrt(x) ).
The coefficients include coprimality to h and unit-modulus Mellin
twists, so their squared sums are O(P) and U L^O(1). Discarding
(h, f) = 1 and squarefreeness only enlarges the positive bound.
Summing dyads and 1/phi(h) costs a fixed power of L. Since
R <= x^theta, a sufficiently large C' gives any prescribed
logarithmic saving.
Small conductors. For 1 < f <= 2 L^(C'), fix r and apply
Siegel-Walfitz to the p-sum with the original smooth cutoff
Psi(pr/x), using partial summation. The nonprincipal character sum
is O_A(P L^(-A)) for arbitrary fixed A. Omitting primes dividing h
costs only O(1) terms, since such primes in the range have log at
least x^a and h <= x^theta. Their total cost after summing r,
moduli, and dyads is x^(1-a) L^O(1). The remaining costs are fixed
powers of L, absorbed by choosing A large.
Summing all the contributions proves (10.17). [End]
10.5 THE PRESIEVE AND ITS MAIN TERM.
Define the standard sieve products
V(y) = prod over p <= y of (1 - 1/p),
V_1(y) = prod over 3 <= p <= y of (1 - 1/(p-1)),
Sel = 2 prod over p >= 3 of (1 - 1/(p-1)^2) > 0. (10.21)
Mertens gives V(y) ~ e^(-gamma_E)/log y and V_1(y) ~ Sel V(y).
Choose a fixed small 0 < kappa < 1/50, then a sufficiently small
fixed b_1 > 0, and set b_* = b_1/3.
Preliminary sieve step. Apply the block sieve (Lemma 4.5) to the odd
prime divisors of N_u up to x^(b_1), with density g(p) = 1/(p-1) and
the remainders r(d) from (10.16)-(10.17). Take
h = 2 floor(1/(40 b_1)), theta = 1/2 - kappa/2. (10.22)
For sufficiently small b_1, h is large enough for Lemma 4.5, and
b_1(4h+2) < theta. Choose D > C_A + 10 in (10.17). Then, summing the
remainders with the Type I bound,
sum over P^-(N_u) > x^(b_1) of A(u) Psi(u/x) (10.23)
>= (Sel X_A/L) { (e^(-gamma_E)/b_1) (1 - O(e^(-c/b_1))) + o(1) }.
The constants in the exponential error are uniform in small b_1 and in
0 < kappa < 1/50.
10.6 PROXIES WITH CHARACTER AND MELLIN DISCREPANCY.
At fixed b_1, kappa, partition (b_1, 1/2 - kappa] into finitely many
exponent bins (gamma, gamma']. Their mesh is chosen later. On the
factor ranges below consider the tests
I_gamma(m) = 1_{P^-(m) > x^gamma}, I_pr(m) = 1_{m prime}. (10.24)
Every such range lies between two fixed positive powers of x; throughout
this subsection the ambient interval is [x^(b_1/4), x^(1 - b_1/4)].
Put Delta_L = L^(-S), with S a fixed precision to be chosen last.
Partition the logarithmic axis into intervals of width Delta_L. For
a full cell C_Y = (Y, e^(Delta_L) Y] meeting the ambient interval set
c_I(C_Y) = (sum over m in C_Y of I(m)) / (10.25)
#{ m in C_Y : P^-(m) > W },
B_I(m) = c_I(C_Y) 1_{P^-(m) > W} (m in C_Y).
The counts defining c_I are full-cell counts even when the factor range
cuts a cell; range restrictions are imposed afterwards.
LEMMA 10.1 (proxy discrepancy). The denominators in (10.25) are
positive for large x, and 0 <= B_I <= 1. Given any fixed discrepancy
exponent B, taking S > 2 B + 3 makes
alpha_m = (I(m) - B_I(m)) 1_{m in K} (10.26)
satisfy the discrepancy condition (8.5), uniformly for every interval K
inside a dyad in the stated factor ranges, for each of the finitely
many tests above. Thus the coefficient bound in Theorem 9.1 is
independent of S.
PROOF. Use the block sieve (Lemma 4.5) on ordinary integers in a cell
with z = W, g(p) = 1/p, and h_s = 2 ceil(T^2). Each divisibility
remainder is O(1), and the sieve level is
D_W = W^(4 h_s + 2) = exp(O(sqrt L T^2)) = x^o(1). (10.27)
Since Y >> x^(b_1/4), uniformly for these cells,
#{ m in C_Y : P^-(m) > W } ~ Delta_L Y V(W) (1 + O(e^(-T^2))). (10.28)
Both actual tests select subsets of these rough integers for large x:
for the prime test all integers in the cell exceed W, and for the other
tests x^gamma > W. So 0 <= c_I <= 1 exactly.
Principal case. Every prime divisor of a modulus r <= L^B is below W,
so a principal character is identically one throughout the support of
alpha. On a full cell the unweighted sum of I - B_I is zero. For
f(t) = t^(iv-1) with |v| <= L^B, its variation on that cell is at most
O((1+|v|) Delta_L / Y). The absolute harmonic mass on a dyad is O(1)
(even O(L^(1/2)) would suffice). So the full cells contribute
O(L^(B-S)); intersecting the test interval in (8.5) with K leaves at
most two partial cells, whose combined harmonic mass is
O(L^(-S) + x^(-b_1/4)). These bounds give the principal case with room
to spare when S > 2 B + 3.
Nonprincipal case for the actual roughness test. Each admitted integer
has a unique nondecreasing list of at most O(1/b_1) prime factors. Fix
the first l-1 factors and sum over the last prime. Its order
restriction, its lower bound x^gamma, and the interval restriction on
the full product intersect in one prime interval whose endpoints lie
between x^gamma and x^2. By Siegel-Walfitz and partial summation, the
harmonic sum of this prime against a nonprincipal character and the
twist p^(iv) has arbitrarily strong logarithmic saving, uniformly for a
prescribed logarithmic bound on modulus and frequency. The reciprocal
masses of the remaining factors are bounded in terms of b_1, because
sum over x^gamma < p <= x^2 of 1/p = O_{b_1}(1). Summing the bounded
number of list lengths preserves the saving. Repeated primes are
included by the nondecreasing enumeration. Imprimitive nonprincipal
characters give the same estimate via their nonprincipal primitive
characters; primes dividing the modulus are too small to occur. For
I_pr this is the same argument with one prime.
Nonprincipal case for the proxy. For every subinterval J' of a cell and
every unit class a mod r, apply the block sieve to that class, omitting
primes dividing r from the sieve. The CRT gives an O(1) remainder at
each squarefree sieve product. Since all prime divisors of r are below
W, the main term is
|J'|/r · prod over p <= W, p ∤ r of (1 - 1/p) = |J'| V(W)/phi(r). (10.29)
Thus
#{ m in J' : m = a mod r, P^-(m) > W } (10.30)
= |J'| V(W)/phi(r) (1 + O(e^(-T^2))) + O(D_W).
Summing against a nonprincipal character cancels the common main term,
and bounds the remaining sum by O(|J'| V(W) e^(-T^2) + phi(r) D_W).
Multiply by c_I <= 1 and use partial summation against m^(iv-1). The
number of cells is at most O(L^(S+1)); the moduli and twists cost fixed
powers of L. The first error remains smaller than every fixed negative
power of L, and the second is x^(-b_1/4 + o(1)) times a fixed power of
L. So the proxy has the discrepancy required. [End]
Prescribe the saving in Theorem 9.1 large enough that its errors, after
all dyadic decompositions, are o(X_A/L). Its coefficient exponent is
fixed before S by Lemma 10.1; obtain the required discrepancy exponent
in (8.5) and then choose S. There are only finitely many test types, so
the same S works for all.
10.7 LOCAL DENSITIES AND THE INTEGRAL IDENTITY.
For w > gamma > 0 define the Buchstab rough-number density
D_gamma(w) = 1/w + sum over l >= 2 of (1/l!) (10.31)
int over t_i >= gamma, sum_{i<l} t_i <= w - gamma of
(1/(w - sum_{i<l} t_i)) prod_{i<l} dt_i / t_i.
Only finitely many terms are nonzero. On compact subsets of w > gamma >
0 the functions are jointly continuous, including at thresholds
w = l gamma: the integrands have bounded denominators and the moving
boundaries have measure zero. This D_gamma is the Buchstab density in
logarithmic coordinates; the minimum-coordinate decomposition below is
the Buchstab identity.
LEMMA 10.2 (proxy density bounds). For the prime proxy on
x^(1/2 - 2 kappa) <= m <= x^(1/2 + 2 kappa),
c_pr(m) <= C/(L V(W)), (10.32)
with C absolute for 0 < kappa < 1/50. If mn = N_u on the support of
Psi(u/x) and log n / L in (gamma, gamma'], then
c_gamma(m) <= ( sup over gamma <= a <= gamma' of D_gamma(1-a) + o(1) )
/ (L V(W)). (10.33)
At fixed b_1 one also has the two identities
int over b_1 <= alpha <= 1/2 of D_alpha(1-alpha) d alpha / alpha (10.34)
= D_{b_1}(1) - 1,
D_{b_1}(1) <= (e^(-gamma_E)/b_1) (1 + O(e^(-c/b_1))). (10.35)
At alpha = 1/2 the integrand is understood by its left limit.
PROOF. For (10.32): the prime number theorem with arbitrarily large
logarithmic error at both endpoints of a cell gives
#{ p in (Y, e^(Delta_L) Y] } = (1+o(1)) Delta_L Y / log Y. (10.36)
For w = log Y / L in [0.46+o(1), 0.54+o(1)], divide by (10.28) to get
(10.32) with an absolute eventual constant.
For (10.33): uniformly on compact sets with gamma >= b_1, w - gamma
bounded below and w bounded above, the number of integers rough above
x^gamma in a cell is at most
(D_gamma(w) + o(1)) Delta_L Y / L. (10.37)
Indeed repeated prime factors contribute at most
sum over p > x^gamma of floor(2Y/p^2) << Y x^(-b_1)
= o(Delta_L Y / L). (10.38)
Count the squarefree remaining integers by ordered lists of l primes
with weight 1/l!, where l is bounded in terms of b_1. Fix the first l-1
primes, write Q = prod_{i<l} p_i and t_i = log p_i / L. A last prime
can occur only when sum_{i<l} t_i <= w - gamma + O(Delta_L/L). Its
count is at most
(1+o(1)) Delta_L Y / (L Q (w - sum_{i<l} t_i)). (10.39)
The prime number theorem is uniform here because Y/Q >= x^gamma/2.
The reciprocal-prime measures converge to dt_i / t_i. A finite-grid
approximation gives uniform convergence of the resulting integrals:
denominators stay bounded away from zero, while strips around the
moving hyperplane boundary have uniformly vanishing volume. This
proves (10.37). In our application w = 1 - log n / L + o(1) and
w - gamma >= 2 kappa + o(1). Continuity, followed by division by
(10.28), gives (10.33).
For (10.34): write the l-th term (l >= 2) of D_(b_1)(1) on the simplex
t_1 + ... + t_l = 1, t_i >= b_1, measure dt_1 ... dt_{l-1} /
(l! t_1 ... t_l). (10.40)
This measure is invariant under permutations of the l coordinates:
exchanging a dependent and an independent coordinate has absolute
Jacobian one. Except on a null set exactly one coordinate is the
minimum, say alpha. Selecting that coordinate in l ways, its measure
is d alpha / alpha, and the remaining coordinates (sum 1 - alpha, lower
bound alpha) give the (l-1)-term of D_alpha(1-alpha). The coefficient
l/l! is 1/(l-1)!. Summing proves (10.34); the one-prime term of
D_(b_1)(1) equals one.
For (10.35): order prime lists with weight 1/l! kill strictly less than
one mass per integer, so
liminf over x of (L/x) #{ x < m <= 2x : P^-(m) > x^(b_1) }
>= D_(b_1)(1). (10.41)
On the other hand Lemma 4.5 with g(p) = 1/p, O(1) remainders, and
h = 2 floor(1/(40 b_1)), bounds this count by
x V(x^(b_1)) (1 + O(e^(-c/b_1))) + O(x^(b_1(4h+2)/...)). (10.42)
Its remainder is o(x/L) for small b_1, and the Mertens asymptotics in
(10.21) prove (10.35). [End]
10.8 SUBTRACTING COMPOSITES AWAY FROM BALANCE.
Consider a composite N_u counted in (10.23) with least prime factor at
most x^(1/2-kappa). This p lies in one bin (x^gamma, x^(gamma')], and
m = N_u/p satisfies P^-(m) > x^gamma. Its total contribution is
bounded by
sum over mp = N_u, x^gamma < p <= x^(gamma') of A(u) Psi(u/x)
I_gamma(m). (10.43)
All contributing dyads of m and p lie between x^(b_*) and x^(1-b_*)
for large x, with b_* = b_1/3: constants in N_u = x are absorbed by the
strict exponent slack. Apply Theorem 9.1 with alpha = I_gamma - B_gamma
restricted to each actual cofactor range, and beta the prime indicator
restricted to its bin and dyad. Lemma 10.1 supplies its discrepancy
hypothesis. Replacing I_gamma by B_gamma costs o(X_A/L) in total.
For a prime p > W the condition that m = N_u/p be rough above W is
equivalent to P^-(N_u) > W. By (10.33) the resulting upper bound
reduces to a constant over L V(W), times
sum over x^gamma < p <= x^(gamma') of (10.44)
sum over p | N_u, P^-(N_u) > W of A(u) Psi(u/x).
For each such p sieve the odd primes up to W with base mass X_A/(p-1),
density 1/(p-1), and remainders r(pd). Take h_s = 2 ceil(T^2) in
Lemma 4.5. All products pd are at most x^(1/2-kappa+o(1)), which is
below the Type I level x^(1/2 - kappa/2). Moreover different pairs
(p, d) give different products: p > W is their unique prime factor
above W. So the Type I bound (10.17) applies without any divisor
multiplicity loss, giving
sum over x^gamma < p <= x^(gamma') of p | N_u, P^-(N_u) > W (10.45)
of A(u) Psi(u/x)
= X_A V_1(W) sum over x^gamma < p <= x^(gamma') of 1/(p-1)
+ o(X_A V(W)).
The reciprocal sum tends to log(gamma'/gamma). So the composite
contribution of the bin is at most
(Sel X_A / L) { sup over gamma <= a <= gamma' of
D_gamma(1-a) · log(gamma'/gamma) + o(1) }. (10.46)
At fixed b_1, kappa, joint continuity in Lemma 10.2 permits a
sufficiently fine fixed mesh such that the sum of these constants is
at most
int over b_1 <= alpha <= 1/2 - kappa of D_alpha(1-alpha) (10.47)
· d alpha / alpha + 1/10.
Subtracting (10.46) from (10.23) and using (10.34)-(10.35) leaves at
least
(Sel X_A / L) { 1 - 1/10 - O(b_1^{-1} e^(-c/b_1)) + o(1) }
>= Sel X_A / (2 L) (10.48)
on primes and composites with least prime factor exceeding
x^(1/2-kappa), provided b_1 is sufficiently small.
10.9 A UNIFORM UPPER BOUND FOR BALANCED COMPOSITES.
If a composite N_u = x has least prime factor above x^(1/2-kappa), it
has exactly two prime factors counted with multiplicity, because
3(1/2 - kappa) > 1. Both factors belong, for large x, to
B_kappa = [x^(1/2 - 2 kappa), x^(1/2 + 2 kappa)]. (10.65)
We may overcount them by ordered pairs (m, n) of primes in that range
with mn = N_u. Replace the first prime indicator by its proxy using
Theorem 9.1, then replace the second using the same theorem with the
factor roles exchanged. The remaining coefficient in the second
application is a proxy bounded by one. All required discrepancy and
range hypotheses follow from Lemma 10.1, as before. By (10.32) the
resulting upper bound is o(X_A/L) plus
(C/(L^2 V(W)^2)) sum over m, n in B_kappa, mn = 2u+1, (10.66)
P^-(m) > W, P^-(n) > W of A(u) Psi(u/x).
We bound this positive sum with a constant independent of kappa, b_1,
j_**, and S. More precisely, each dyadic pair with mn = x contributes
O(X_A V(W)^2). There are only O(kappa L + 1) such pairs in the
indicated range, so the prefactor in (10.66) gives an
O((kappa + L^(-1)) X_A/L) bound.
Micro bands. Choose a fixed large index j' and then theta in the gap
c_2 s' 2^(-j') < theta < c_1 s' 2^(-j'+1), 10 theta <= 1/20, (10.67)
sum over j >= j' of r_0 c_2 s' 2^(-j) <= 1/25.
The gap exists because c_2 < 2 c_1. These choices depend only on the
candidate geometry. Increase the early lower bound j_0 to ensure
j_0 >= j', so the rough slot is in a band j >= j'. Call these the
micro bands. Write H_Q^mic for the Q harmonic mass of just these bands.
Omitting the finitely many fixed bands j < j' gives
H_Q^mic << H_Q, (10.68)
with a constant independent of j_**.
An assignment consists of the complete ordered Q-lists in the micro
bands, including the rough slot, and one marked prime from every
P-group. Give it weight
lambda_assgn = prod_{j=j'}^{j_x} (1/r_0!) prod over P-groups g of (10.69)
(1/V_g),
and let D_1 be the product of all its entries, with multiplicity. The
micro Q contribution has size at most x^(1/25) by (10.67); the P marks
have product exp(O(T L^(2/5))) = x^o(1). So
D_1 <= x^(1/20), sum over assignments of lambda_assgn / D_1
= H_Q^mic, (10.70)
sum over assignments of lambda_assgn <= x^(1/20) H_Q^mic.
In the middle identity the harmonic sum of the normalized P-mark in
each group is exactly V_g^(-1) sum over p in P_g of 1/p = 1.
Damping. Once one P prime per group is marked in D_1, every additional
distinct P-prime divisor of u contributes a factor q. We represent
these factors by independent random permissions for those primes;
averaging the permissions recovers exactly the damping.
For each assignment, ban every odd non-P prime l <= x^theta not
dividing D_1. For each P prime not dividing D_1, independently allow
it with probability q and otherwise ban it. Primes dividing D_1 are
never banned. All P primes are below x^theta and indeed below W.
Then we have the pointwise majorant
A(u) <= sum over assignments of lambda_assgn (10.71)
1_{D_1 | u} E_mask 1_{l does not divide u for every
banned l}.
To verify it, expand A(u) into Q-lists and one P mark per group. For
every genuine list the divisibility D_1 | u holds, and every non-P
prime divisor of u below x^theta occurs in D_1: omitted Q-bands
contain only pure primes above x^theta. The micro Q product has no P
factors, so D_1 contains exactly one distinct P prime per group. For
such a genuine list the mask expectation is q^(omega(u)-s), which is
the damping in W_1(u). Once the micro entries are fixed, the
normalized number of omitted pure-prime lists with any fixed residual
product is at most one: a band with prime multiplicities a_p
contributes prod 1/a_p! <= 1, and disjointness prevents alternative
band assignments. Dropping these residual restrictions proves (10.71).
Dyadic estimate. Fix a pair of dyads m = M_1, n = M_2 meeting the
product support mn = x, an assignment, and a mask. Since D_1 is odd,
D_1 | u and mn = 2u+1 imply mn = 1 mod D_1. Use this congruence to
bound the number of pairs in the full dyadic box. For an odd prime
l <= z' := x^theta with l ∤ D_1, the bad events are
mn = 0 mod l (l <= W), mn = 1 mod l (l banned). (10.72)
The two residue sets are disjoint and contain respectively 2l-1 and
l-1 pairs. Put
nu(l) = (2l-1) 1_{l <= W} + (l-1) 1_{l banned}, g(l) = nu(l)/l^2. (10.73)
These densities satisfy the hypotheses of the block sieve uniformly in
assignment and mask: g(l) <= 3/l, and for l >= 3 they are bounded away
from one. The base mass is the product of the two real side lengths
times phi(D_1)/D_1^2.
Lattice error. For a squarefree product d of the sieve primes the CRT
gives exactly phi(D_1) nu(d) residue pairs modulo D_1 d, including when
D_1 has prime-power factors. Each pair of residue classes has lattice
count equal to its area term with error
O( 1 + (M_1 + M_2)/(D_1 d) ). (10.74)
Since nu(d) <= d 3^(omega(d)) and phi(D_1) <= D_1, the sum of absolute
remainders up to D = (z')^(10) = x^(10 theta) is
<< L^O(1) ((M_1 + M_2) D + D_1 D^2)
<= L^O(1) ((M_1 + M_2) x^(1/20) + D_1 x^(1/10)). (10.75)
Here omega(d) occurs only in this elementary divisor bound; its sums
follow for instance from 3^(omega(d)) <= tau_3(d). Apply the upper-
bound version of the block sieve with h = 2.
Euler product. A banned prime below W has factor 1 - 3/l + 2/l^2, and
a banned prime above W has factor 1 - 1/l + 1/l^2. Each is at most
(1 - 1/l)^(1 + 2·1_{l<=W}) (1 + O(l^(-2))). (10.76)
An allowed P prime has factor (1 - 1/l)^2, so it requires one
compensating factor (1 - 1/l)^(-1). Omitting the prime 2 changes only
an absolute constant, as does the convergent product of the
1 + O(l^(-2)) factors. Removed primes dividing D_1 require at most
three compensating factors. So
prod over 3 <= l <= z', l ∤ D_1 of (1 - g(l)) (10.77)
<= C V(W)^2 V(z') prod over l | D_1 of (1 - 1/l)^(-3)
prod over P primes p ∤ D_1 of (1 - 1/p)^(-1).
Every prime dividing D_1 is at least L^20, so D_1 <= x^(1/20) makes
its compensating product uniformly bounded. The expectation of the
last product is
prod over P primes p ∤ D_1 of (1 - q + q/(1 - 1/p))
= prod over P primes p ∤ D_1 of (1 + q/(p-1)) <= H_P (10.78)
by (10.15).
Summing main terms. Since phi(D_1)/D_1^2 <= 1/D_1, sum the main sieve
terms over assignments using (10.70), and bound Psi by its fixed
supremum. Their contribution on the dyadic pair is
<< x V(W)^2 V(x^theta) H_Q^mic H_P << X_A V(W)^2, (10.79)
by (10.8), (10.68), and V(x^theta) << 1/L. To sum the error (10.75)
use M_i << x^(0.54) and (10.70); the result is
<< x^(0.64) L^O(1) H_Q^mic = o(X_A V(W)^2). (10.80)
The comparison is uniform in the later parameters: use
H_Q^mic << H_Q, H_P >= 1, and X_A V(W)^2 = x H_Q H_P / L^2.
So the dyadic estimate holds:
sum over m = M_1, n = M_2, mn = 2u+1, P^-(m) > W, P^-(n) > W (10.81)
of A(u) Psi(u/x) << X_A V(W)^2.
There are O(kappa L + 1) possible dyads for m in B_kappa, and for each
only O(1) possible dyads for n because mn = x. Combining (10.66) and
(10.81) bounds the entire balanced composite contribution by
C_bal (kappa + L^(-1)) X_A/L + o(X_A/L). (10.82)
The constant C_bal depends only on delta, r_0, Psi, j', theta, and the
fixed P-group geometry. It does not depend on kappa, b_1, j_**, the
later analytic parameters, or S. Indeed the candidate comparison is
uniform in j_**; the omitted macro bands are fixed before the gap; the
prime proxy bound is uniform on [0.46, 0.54]; and the sieve-density and
lattice constants just used are absolute.
11. CLOSING THE PARAMETER CHOICES AND PROVING THEOREM B.
The choices above can be made in the following order.
11.1 THE ORDER.
(1) Fix delta, Psi, r_0, and the Q/P geometry. Choose the finite prefix
for the candidate lower bound in the proof of Proposition 10.1, then
j' and theta in (10.67), and enlarge j_0 to cover both requirements.
All these are early choices, depending only on fixed parameters.
(2) Fix kappa in (0, 1/50) so small that C_bal kappa < Sel/4. This is
possible because the constant C_bal in (10.82) is independent of the
gap.
(3) Choose b_1 > 0 sufficiently small for (10.23), (10.35), and (10.48).
Set b_* = b_1/3. Choose j_** to meet (10.1) and c_2 s' 2^(-j_**) <
b_*/4. Then choose the finite exponent mesh for (10.46).
(4) Prescribe the saving in Theorem 9.1 large enough that every
replacement error, including dyadic sums, is o(X_A/L). The
coefficient exponents are already bounded independently of S. The
proof of that theorem fixes its Cauchy splitting precision, its
shift-saving target, its graph and analytic parameters, and finally
a required discrepancy exponent B in (8.5).
(5) Choose S sufficiently large in Lemma 10.1 for that B. Fix any
prime-number-theorem accuracies needed for this S, then let x tend
to infinity.
In particular, the precision of the proxy cells causes no feedback into
the Type II coefficient bound. All constants that appear in the
balanced-composite bound (10.82) are fixed before step (2).
11.2 COUNTING PRIMES AND PROVING THEOREM B.
Subtract (10.82) from (10.48). For all sufficiently large x there
remains a positive constant multiple of X_A/L on prime values of N_u:
sum over 2u+1 prime of A(u) Psi(u/x) >> X_A/L. (11.1)
By Proposition 10.1 each summand is at most exp(O(sqrt L)), and X_A >>
x L^(-C_A). The map u -> 2u+1 is injective, so the number of distinct
primes is at least
x L^(-C_A-1) exp(-O(sqrt L)) = x^(1-o(1)). (11.2)
Their range is 2x < p <= 4x + 1 <= 5x. Moreover, P^+(p-1) = P^+(2u) =
max(2, P^+(u)) <= x^delta for large x. The strict inequality c_2 s' <
delta in (10.1) leaves room for every subpower P-prime, and the factor 2
is eventually below x^delta. This proves Theorem B.
11.3 REMARK ON THE PROOF SKELETON.
The pieces of the proof combine as follows. Section 4 supplied the
elementary lemmas; sections 5, 6, 7 proved that the physical dilation
graph has the same moments as its idealised counterpart; section 8
extracted a cancellation at any prescribed shift, which section 9
converted into the Type II bilinear estimate. Sections 10.1-10.9 then
threaded the sieve: Type I to control the congruence distribution, the
block sieve to establish the presieve mass, proxies to turn roughness
tests into ordinary-density tests, Type II to remove unbalanced
composites, and a two-variable sieve to control the balanced window.
Section 11.1 fixed the parameters, and section 11.2 converted the
surviving prime mass into a count. Nothing in this chain depends on
Siegel-Walfitz for the ideal norm or the shift cancellation; the only
ineffective input is the usual one inside Type I and the prime number
theorem in the block sieve, and both are absolute.
12. THEOREM A FROM THEOREM B.
The derivation is complete in section 2. This section records the
exact constants, so that the reader who jumps to the end can check
that the proof really finishes Theorem A.
Setting. Suppose eps is a fixed real with 0 < eps < 1. Choose a
fixed 0 < delta < 1/4 with 4 delta < eps, for example delta = eps/8.
The prime set. Apply Theorem B with x = X/5 for large X. Since
2(X/5) = 2X/5 and 5(X/5) = X, and (X/5)^delta < X^delta, Theorem B
yields a set Pp of primes with
X/3 < p <= X, p-1 is X^delta-smooth, |Pp| >= X^(1-delta). (12.1)
The last inequality uses X^(1-o(1)) >= X^(1-delta) for large X.
Many distinct products. Put M = |Pp| and k = floor(X^(2 delta)).
For large X, k <= M because 3 delta < 1. The elementary bound
binom(M,k) = prod_{j=0}^{k-1} (M-j)/(k-j) >= (M/k)^k, and every factor
(M-j)/(k-j) is at least M/k, gives
number of k-element subsets Q of Pp >= (M/k)^k
>= X^((1-3 delta) k). (12.2)
Different subsets have different products m_Q by unique
factorization, and every such m_Q satisfies X/3 < m_Q <= X^k.
Their totients are few. By multiplicativity of phi on squarefree
m_Q,
phi(m_Q) = prod_{p in Q} (p-1). (12.3)
Each factor is at most X and is X^delta-smooth, so phi(m_Q) is
X^delta-smooth and at most X^k. An X^delta-smooth integer at most
X^k has form prod p^(a_p) over primes p <= X^delta, subject to
sum_p a_p log p <= k log X; in particular each a_p is at most
k log X/log 2. So the number of possible phi-values is at most
(1 + k log X / log 2)^(X^delta) = X^(o(k)). (12.4)
The exponent claim: the logarithm of the left side, divided by
k log X, is O_delta(X^delta log X / (k log X)) = O_delta(X^(-delta)),
which tends to zero because k = X^(2 delta).
Pigeonhole. By (12.2) and (12.4), some totient value n <= X^k has
g(n) >= X^((1-3 delta - o(1)) k) > n^(1 - eps) (12.5)
for large X, since 3 delta + o(1) < eps and 1 - eps > 0.
Infinitely many n. The lower bound (12.5) tends to infinity with
X, so the values n achieving it cannot belong to a fixed finite set.
They are unbounded, giving infinitely many n with g(n) > n^(1 - eps).
This proves Theorem A. For eps >= 1 the statement is subsumed by any
smaller positive eps. The elementary upper bound n^(1+eta) from
Lemma 2.1 shows the exponent 1 in Theorem A is the largest possible.
13. WHERE EACH HYPOTHESIS IS USED.
Every result of the paper is stated with the parameters on which it
depends, and the following table records where each external
hypothesis is introduced and where it is discharged. All constants
are fixed before x tends to infinity, except where a parameter
depends on x, which is stated.
Hypothesis | Introduced | Used / discharged in
-------------------------------+----------------+--------------------------------
Prime number theorem with | sec 4.1 | 4.2, 8.5, 10.7 (proxy
logarithmic error | | densities), 11.2
Mertens asymptotics | sec 4.1 | 4.2, 4.5 (block sieve),
| | 10.5 (Sel, V(W))
Siegel-Walfitz (Thm 4.x) | sec 4.1 | 4.4 (harmonic character
| | estimates), Lemma 10.1
| | (proxy discrepancy), and
| | the small-conductor case
| | of Type I (Prop 10.2)
Multiplicative large sieve | sec 4.1 | 7.3 (character frame),
| | 10.4 (Type I, large f)
Block sieve (Lemma 4.5) | sec 4.5 | Cor 4.6 (rough
| | polynomial), Lemma 10.1
| | (proxy discrepancy),
| | Lemma 10.2 (rough
| | densities), 10.5 (pre-
| | sieve), 10.8 (second
| | sieve for unbalanced
| | composites), 10.9
| | (two-variable sieve for
| | balanced composites)
Ideal-norm hypothesis (5.12) | sec 5.2 | required by Thm 5.2
| | (transference); proved
| | by Thm 7.1
Distinctness of birth values | sec 6.7 | restored in 6.7 by the
| | rank expansion
Discrepancy condition (8.5) | sec 8.1 | required by Thm 9.1
| | (Type II); supplied by
| | Lemma 10.1
Geometric data (5.1) | sec 5.1 | fixed before 6-9;
| | used by 10.1 and 10.9
Candidate geometry (10.1) | sec 10.1 | fixed at the start of
| | single-prime-extraction
| | step
Band gaps (9.1) | sec 9.1 | fixed before Type II,
| | controlled by j_0 in
| | (10.1)
The quantifier order. Throughout, the choices are made in the order:
delta, Psi, r_0, Q/P geometry
-> finite prefix for the candidate lower bound, then j' and theta
-> kappa (with C_bal kappa < Sel/4)
-> b_1 (with b_1(4h+2) < theta in (10.22)) and b_* = b_1/3
-> j_** (with c_2 s' 2^(-j_**) < b_*/4)
-> finite exponent mesh for (10.46)
-> Type II saving target and the constants it needs (J, E_id,
A_0, C_1, m, B)
-> S in Lemma 10.1 (with S > 2B+3)
-> prime-number-theorem accuracies for this S
-> x -> infinity.
The only apparent feedback is the requirement c_2 s' < delta for the
final smooth-image growth in (11.2), and that inequality is
discharged by fixing r_0 sufficiently large. Everything else is
fixed in one direction.
Dependence on J. The pattern length J is chosen last among the
graph analytic parameters: after the ideal norm target E_id and the
comparison kernels. Its only appearance outside the graph
construction is in the small-group gain in (6.37) and the small-group
mask of (10.9); both are invisible once J is fixed.
Dependence on the discrepancy exponent B. B is chosen last in the
Type II chain: after J and the Mellin cutoffs, and before S. Its
only role is to state the discrepancy hypothesis (8.5), so it is
also the only constraint on the cell precision in (10.25).
13.1 A ONE-PARAGRAPH SKELETON.
A reader who wants only the shape of the proof can hold the following
in mind. The candidate set supplies about x/L integers u whose prime
factors all lie below x^delta. The presieve removes u with a small
odd prime dividing 2u+1, leaving x/L mass. Type I ensures that
2u+1 is equidistributed among residue classes up to the sieve level.
Type II replaces roughness of each factor of 2u+1 by a local density,
which the two-variable sieve and the Buchstab identity then subtract
from the presieve mass. The remainder is positive on prime values,
and the count of distinct primes follows by dividing the surviving
mass by the largest summand. Everything else is bookkeeping to make
these five steps uniform in the parameters and correct at every
scale.
14. REFERENCES AND PROOF-DEPENDENCY MAP.
14.1 SHORT REFERENCE LIST.
The mathematics is all self-contained (every scalar is a named finite
product or sum), but a few external results are worth citing for
orientation:
Erdos, P. On the normal number of prime factors of p-1 and some
related problems concerning Euler's phi-function. Quart. J. Math.
6 (1935), 205-213.
Erdos, P. On pseudoprimes and Carmichael numbers. Publ. Math.
Debrecen 4 (1956), 201-206.
Pomerance, C. Popular values of Euler's function. Mathematika 27
(1980), 84-89.
Baker, R. C. and Harman, G. Shifted primes without large prime
factors. Acta Arith. 83 (1998), 331-361.
Montgomery, H. L. and Vaughan, R. C. Hilbert's inequality. J.
London Math. Soc. (2) 8 (1974), 73-82.
Ford, K. and Halberstam, H. The Brun-Hooley sieve. J. Number
Theory 81 (2000), 335-350.
Soundararajan, K. Moments of the Riemann zeta function. Ann. of
Math. (2) 170 (2009), 981-993.
Buchstab, A. Asymptotische Abschaetzung einer allgemeinen
zahlentheoretischen Funktion. Rec. Math. [Mat. Sbornik] N.S. 2
(44) (1937), 1239-1246.
Matomaki, K. and Radziwill, M. Multiplicative functions in short
intervals. Ann. of Math. (2) 183 (2016), 1015-1056.
Alford, W. R., Granville, A., and Pomerance, C. There are
infinitely many Carmichael numbers. Ann. of Math. (2) 139 (1994),
703-722.
Pilatte, C. Improved bounds for the two-point logarithmic Chowla
conjecture. arXiv:2310.19357, v3 (2026).
The role each of these plays: Erdos (1935), Erdos (1956), and
Pomerance (1980) were the origin of Theorem A and the smoothness
expectation in Theorem B. Baker-Harman (1998) were the strongest
earlier shifted-prime bounds and highlight why a fixed exponent
delta with x^{1-o(1)} count is a change of kind. Montgomery-Vaughan
(1974) is the source of the Dirichlet-polynomial mean-value lemma
in 4.3. Ford-Halberstam (2000) is the source of the block sieve
inequality in 4.5. Soundararajan (2009) is the source of the
prime-polynomial moment argument in 8.6. Buchstab (1937) is the
source of the rough-integer density in 10.7. Matomaki-Radziwill
(2016) is the modern model for Type II estimates of this kind.
Alford-Granville-Pomerance and Pilatte are included as context for
the totient-fiber problem; neither is used in the proof.
14.2 PROOF-DEPENDENCY MAP.
The following list is the plain-text version of the paper's diagram
of dependencies. A result may use anything to its left.
Theorem 5.2 (local transference)
depends on Section 6 (rare transfers, clean edges) and
Section 7 (ideal kernels).
Theorem 7.1 (ideal norm bound)
depends on Sections 7.3 (character frame) and 7.4 (symmetric
probes).
Theorem 8.1 (shift cancellation)
depends on Theorem 5.2 and its pairing corollary, and on the
Mellin and local-energy input of Section 8.5.
Theorem 9.1 (Type II)
depends on Theorem 8.1.
Proposition 10.1 (candidate mass)
depends on Section 4 only (prime number theorem).
Proposition 10.2 (Type I)
depends on Section 4.1 (Siegel-Walfitz and large sieve).
Lemma 10.1 (proxy discrepancy)
depends on Lemma 4.5 (block sieve) and Theorem 4.4 (Siegel-
Walfitz).
Lemma 10.2 (rough densities)
depends on Lemma 4.5 and the prime number theorem.
Sections 10.8 and 10.9 (removing unbalanced and balanced
composites)
depend on Theorem 9.1 and Lemma 10.1.
Theorem B
depends on Propositions 10.1-10.2, Lemmas 10.1-10.2, and
Sections 10.8-10.9.
Theorem A
depends on Theorem B and Lemma 2.1.
Section 3 (the shape of the proof) reads these in order. Section 13.1
compresses the same chain into a single paragraph.
14.3 A NOTE ON THE STYLE OF THIS FILE.
Because the file is meant to be read without LaTeX, several conventions
differ from a conventional paper.
- "e(t) = exp(2 pi i t)"; "L = log x"; "T = log L".
- "z << w" means |z| <= C w for an absolute C, occasionally for a
constant depending on fixed parameters; those parameters are
stated.
- "for large x" means "for all x >= x_0(<fixed parameters>)".
- "x^(1-o(1))" is defined in the header.
- A display's equation number, e.g. (10.23), is meant to be cited
only from later in this file. Section 13 has the index of
where each hypothesis is actually consumed.