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.