HOW MANY NUMBERS ARE TOTIENTS?
A complete and elementary walk through the theorem
V(x) ~ (x/log x) * G_m * A(1; theta)
------------------------------------------------------------------------------
ABSTRACT
------------------------------------------------------------------------------
Let phi(n) be Euler's totient function: phi(n) counts the positive integers
<= n that share no prime factor with n. For example phi(1) = 1,
phi(10) = 4, phi(12) = 4. The set of totient values up to x is
V(x) = #{ v : v = phi(n) for some n, and v <= x }.
Every prime p contributes the totient p - 1, so by the prime number theorem
V(x) is at least about x / log x. But V(x) is much larger than that trivial
lower bound, and figuring out exactly how much larger has been an open
question for nearly a century.
The classical result (Ford 1998) says
V(x) = (x/log x) * K(x),
where K(x) is a positive quantity of order exp(c (logloglog x)^2) for a
specific constant c. Ford proved that K(x)/Ford_scale(x) stays bounded
between two positive constants, but he did not pin down its limit.
This document proves the following sharpened theorem.
THEOREM 1. Define explicit numbers rho, lambda, m, theta, G_m and a
limit A(1;*) as below. Then, as x -> infinity,
V(x) ~ (x / log x) * G_m * A(1; theta);
and, for every fixed real c > 0,
V(c x) / V(x) -> c.
Here "A ~ B" means A / B -> 1. The constants G_m and A(1; theta) are
bounded above and below by positive constants that do not depend on x.
The proof is long. It uses Ford's theorems about the typical shape of a
totient preimage, a sieve estimate for pairs of shifted primes, a collision
bound that assures us different "candidate preimages" really give different
values, and a finite inclusion-exclusion over arithmetic "tail witnesses".
Every step is spelled out below. A reader with college calculus and
comfort with asymptotic notation (O, o, ~) should be able to follow it.
------------------------------------------------------------------------------
HOW TO READ THIS DOCUMENT
------------------------------------------------------------------------------
The proof has three conceptual jobs. Keep them in mind:
(A) EXTRACTION. Almost every totient v <= x has a "basic witness": a
factorization v = phi(p_0 p_1 ... p_L a) in which p_0,...,p_L are
primes that sit in predetermined ranges, p_0 is large, and the last
factor a is tiny. This is Ford's structural theorem, given below.
(B) UNIQUENESS. Almost every such v has at most ONE decomposition of
that form, after grouping together the small tail. Without this
step, "count preimages" would not equal "count values". This is
where the deep shifted-prime collision bound lives.
(C) COUNTING. Once (A) and (B) hold, count the candidate preimages by
the prime number theorem, replace the huge list of primes by a
volume in a simplex, and identify the leftover finite-tail
arbitrariness with an inclusion-exclusion formula. That formula
is our A.
The companion theorem about "least preimage intervals" is a weighted
version of the same machinery: instead of the constant weight 1, use a
sawtooth weight f_k that selects the appropriate smallest preimage.
------------------------------------------------------------------------------
NUMERICAL NOTATION
------------------------------------------------------------------------------
x, y, z positive real numbers (never 0 or negative)
x -> oo x tends to +infinity
log x natural log (base e)
loglog(x) log(log(x))
logloglog(x) log(log(log(x)))
A ~ B A/B -> 1
A << B |A| <= C B for some constant C (Vinogradov)
A =~ B A << B and B << A
A = O(B) |A| <= C B for some constant C
A = o(B) A/B -> 0
phi(n) Euler's totient: #{1 <= k <= n : gcd(k,n) = 1}
V set of ALL totient values {phi(n) : n >= 1}
V(x) #{v in V : v <= x}
ell(v) smallest n with phi(n) = v, when v is in V
p, q, r primes
d, n, v positive integers; "d in V" means d is a totient
------------------------------------------------------------------------------
1. EULER'S TOTIENT AND THE COUNTING PROBLEM
------------------------------------------------------------------------------
1.1 What phi does
For n >= 1, phi(n) counts how many integers 1, 2, ..., n are coprime to n.
Basic facts we use throughout:
(1) phi(1) = 1; phi(p) = p - 1 for every prime p.
(2) phi is multiplicative: if gcd(m,n) = 1 then phi(mn) = phi(m) phi(n).
(3) phi(p^k) = p^{k-1} (p - 1) for any prime p and any k >= 1.
(4) If n = p_1^{e_1} ... p_r^{e_r}, then
phi(n) = n * (1 - 1/p_1) * ... * (1 - 1/p_r).
Convention throughout: "preimage of v" means an integer n with phi(n) = v.
If v has several preimages, that is a fact we have to live with.
1.2 A table
n: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
phi: 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8
Distinct values among phi(1),...,phi(20):
1, 2, 4, 6, 8, 10, 12, 16, 18; count = 9. So V(20) = 9.
Notice: 14 is missing. In fact 14 is never a totient. Reason: phi(n) = 14
forces phi(n) to be divisible by 7. By (3)-(4), 7 | phi(n) requires either
7^2 | n (but phi(49) = 42 > 14) or some prime q | n with q = 1 mod 7; the
smallest such q is 29 and phi(29) = 28 > 14 already. Hence no n has
phi(n) = 14, so 14 is not a totient.
The image V is therefore not all of {1, 2, 3, ...}. It is also not
"almost all" numbers:
Pillai (1929). V(x)/x -> 0. Almost no positive integer is a totient.
Erdos (1935). For every eps > 0, V(x) << x / (log x)^{1-eps}.
The trivial lower bound is V(x) >= pi(x + 1) ~ x / log x, since every prime p
contributes p - 1 = phi(p). So V(x) is sandwiched:
x / log x << V(x) << x / (log x)^{1-eps} (any eps > 0).
Everything interesting is the factor between x/log x and x/(log x)^{1-eps}.
------------------------------------------------------------------------------
2. THE SHAPE OF THE MAIN THEOREM
------------------------------------------------------------------------------
2.1 Classical calibration
The leading asymptotic is best written as
V(x) ~ (x / log x) * K(x),
where K(x) is bounded away from zero and grows (very slowly in x, but fast
enough that K(x) -> infinity with x).
Successive sharpenings of K(x):
Maier-Pomerance (1988):
K(x) = exp( (C_0 + o(1)) * (logloglog x)^2 ), C_0 = 0.8178146...
Ford (1998):
K(x) = exp( C_0 (log_3 x - log_4 x)^2 + D_0 log_3 x
- (D_0 + 1/2 - 2 C_0) log_4 x + O(1) ),
where D_0 = 2.1769687... and log_j denotes j-fold iterated log.
Ford's formula fixes K(x) to within a bounded multiplicative factor.
Specifically:
Ford's order estimate. There are absolute constants c_-, c_+ > 0 such
that
c_- <= (V(x) log x) / (x G_m) <= c_+
for every large x, where G_m is the explicit scale constructed in 2.2.
The gap c_+/c_- is what the present theorem closes.
2.2 The scale G_m
Fix once and for all the number rho in (0, 1) defined by
a_j = (j+1) log(j+1) - j log(j) - 1, j = 1, 2, 3, ...
sum_{j>=1} a_j rho^j = 1.
The a_j are positive (since log is convex), the sum
sum_{j>=1} a_j z^j is strictly increasing from 0 to +infinity as z goes
from 0 to 1, so rho is the unique root. Numerically 0.54 < rho < 0.545.
Let
lambda = log(1/rho) (so 0.60 < lambda < 0.62)
g_0 = 1
g_j = sum_{d=1}^{j} a_d g_{j-d} j >= 1
gamma = ( sum_{j>=1} j a_j rho^j )^{-1}
so that g_j ~ gamma rho^{-j} as j -> infinity (a straightforward recurrence
fact; Ford proves this in his Lemma 3.7, crediting Lau).
For an argument x >= 3, define
B(x) = loglog(x)
m(x) = floor( ( log B(x) - loglog(B(x)) ) / lambda )
theta(x) = ( log B(x) - loglog(B(x)) ) / lambda - m(x) in [0, 1)
and
G_j(x) = B(x)^j / ( j! * g_1 * g_2 * ... * g_j ), j = 0, 1, ..., m(x).
Facts (verified directly from the definitions and Stirling):
m(x) ~ logloglog(x) / lambda -> +infinity
G_m ~ exp( c (logloglog x)^2 )
c = lambda/2 - ... , in any case c > 0 and the exponent is exactly the
classical C_0 exponent (with corrections matching Ford's expansion).
The point of G_m is: the honest asymptotic scale is not x/log x, it is
x G_m / log x. The concrete numbers B, m, theta, G_m depend continuously
on x, except that m jumps by 1 when the phase theta passes 0.
2.3 The coefficient A
The main theorem introduces a specific numerical coefficient A(1; theta)
depending on the phase theta in [0, 1), built from a finite arithmetic
construction:
-- choose a large cutoff H (an integer tending to infinity later);
-- write P = floor(loglog H);
-- a "tail" is a list of primes Q_P, Q_{P+1}, ..., Q_{H-1} whose sizes
follow a specific pattern in double logarithms, plus a small smooth
integer a;
-- the resulting tail totient d = phi( a Q_P ... Q_{H-1} ) is finite
because H is finite;
-- form A_H(1; theta) by an explicit finite inclusion-exclusion over
all tails giving each d;
-- let A(1; theta) = lim_{H -> oo} A_H(1; theta).
A_H(1; s) as a function of s is explicitly written in section 7.4. The
key properties proved below:
-- 0 < A(1; s) < oo for every s, uniformly in s;
-- A(1; s) depends on s continuously enough that everything we need
works; in particular, uniform convergence holds.
2.4 The main theorem (restated with all definitions)
THEOREM 1. Define rho, lambda, m(x), theta(x), G_m(x), and A as in
sections 2.2 and 2.3. Then
V(x) ~ (x / log x) * G_m(x) * A(1; theta(x)) (x -> oo).
Moreover, for every fixed real c > 0,
V(c x) / V(x) -> c (x -> oo).
The equality V(cx)/V(x) -> c was asked by Erdos and Hall in the final line
of their 1976 paper (and repeated by Erdos in 1979). Ford had established
V(cx) - V(x) =~_c V(x). The theorem gives the exact ratio.
2.5 The companion theorem (least preimage intervals)
For v in V, let ell(v) be the smallest integer n with phi(n) = v. For
a fixed positive integer k, we want to count
N_k(x) = #{ v in V : v <= x and k x < ell(v) <= (k+1) x }.
Define the weight
f_k(r) = min{1, (k+1)/r} - min{1, k/r}, r >= 1.
Then f_k(r) > 0 exactly when r > k, f_k(r) <= 1/(k+1), and f_k is
nonnegative on [1, oo).
THEOREM 2. For each fixed k >= 1, the functions A_H(f_k; s) converge
uniformly for 0 <= s < 1, and
N_k(x) = (x / log x) * G_m * ( A(f_k; theta) + o(1) ).
There are exactly two possibilities:
(i) some totient d has ell(d) > k d, in which case
A(f_k; s) is bounded away from 0 uniformly in s, and
N_k(x) ~ (x/log x) G_m A(f_k; theta) =~_k V(x).
(ii) every totient d has ell(d) <= k d, in which case
N_k(x) = 0 for every x, and A(f_k; s) = 0 for every s.
The positive alternative (i) holds for k = 1 and k = 2.
This does NOT settle which k > 2 give (i). The two alternatives are
mutually exclusive and exhaustive; the theorem proves that much in full
generality. Whether (i) holds for every k >= 1 is equivalent to the
open question of whether ell(d)/d is unbounded over totients d.
------------------------------------------------------------------------------
3. THE PROOF STRATEGY
------------------------------------------------------------------------------
3.1 A typical preimage looks like a falling stack of primes
The modern proof is driven by one structural fact, due to Ford. Order the
prime factors of a preimage n with multiplicity as
p_0 >= p_1 >= p_2 >= ... >= p_L >= ...
Then for a "typical" totient v <= x = e^{e^B}, the primes p_i are extremely
regular in double-logarithmic scale:
loglog(p_i) is about b_i = alpha * h_i * rho^{-h_i} (*)
where h_i = m - i and alpha = B rho^m / m is a slowly varying constant
depending only on the phase theta(x). Because rho < 1, h_i decreases as i
grows, so rho^{-h_i} SHRINKS as i grows. That is: the primes fall off at a
super-exponential rate. p_0 is basically x; p_1 is roughly exp(exp(0.6 B));
by the time i = m - P, loglog(p_i) is only polynomial in P.
Almost every totient is of this shape. Ford's Theorems 10 and 16 quantify
how few values escape it: the "escape" set has size << V(x) e^{-cP}.
3.2 Two cuts
Fix a large integer H and let P = floor(loglog H). Two integer cutoffs
play distinct roles:
R = m - H -- "prefix / tail boundary". Primes p_0..p_R are
"heavy": their double logs are huge and follow a
simplex. The remaining primes p_{R+1}..p_L, plus
a small smooth factor a, form a bounded-size "tail".
L = m - P -- "end of the prime factors we track". Beyond index L
the prime factorization continues, but as even
smaller primes packed into a smooth factor; we lump
them into a.
Every totient has a witness
v = phi( p_0 p_1 ... p_L a )
where p_0..p_L are distinct primes in prescribed ranges, P^+(a) <= p_L, and
a is smooth and bounded once H is fixed.
3.3 The three jobs, now precise
(A) EXTRACTION.
Show that "almost every" totient v <= x has such a basic witness for
EVERY preimage of v. "Almost every" means: exception set of size
(epsilon_H + o_{x;H}(1)) * V(x), with epsilon_H -> 0 as H -> oo.
This is Proposition 4.1 below.
(B) UNIQUENESS.
Group the possible witnesses into "tuples" tau = (p_0,...,p_R, d)
where d = phi(tail) is the totient of the whole bounded tail. Two
tuples with the same value map
F(p_0,...,p_R,d) = d * prod_{i=0}^R (p_i - 1)
represent the same totient v. Show: the number of ordered PAIRS of
distinct good tuples with the same value F is negligible compared to
the total count. That is Proposition 6.1 (Prefix collisions).
Combined with an elementary finite-map lemma this yields: almost
every totient has at most one good tuple, and hence, for its value v,
ell(v) = p_0 p_1 ... p_R ell(d),
where ell(d) is the smallest preimage of the tail totient d.
(C) COUNTING.
Now that tuples map bijectively to values (off a negligible set),
count distinct tuples. Because the tuple's dependence on p_0 is
just "how many primes lie in an interval of length x/D", the prime
number theorem applies cleanly:
#{ p_0 : tuple valid } = ( x / (D log x) ) (1 + o(1)),
where D = d * prod_{i=1}^R (p_i - 1) is the data of the tuple minus
p_0. Summing over the remaining tuple data produces
V(x) ~ (x / log x) * M_1(x; H) + (tiny error),
where
M_1(x; H) = sum over distinct tail tuples (d, p_1, ..., p_R)
of 1 / ( d * prod_{i=1}^R (p_i - 1) ).
This already gives fixed scaling V(cx)/V(x) -> c, immediately,
because both V(x) and V(cx) use the same M_1 up to negligible error.
(D) VOLUME-TO-COEFFICIENT.
Now observe that M_1(x; H) is a Riemann-type sum over primes
p_1,...,p_R satisfying the simplex constraints. Replace reciprocal
prime sums by volumes via Mertens' theorem. The R remaining
coordinates become a simplex of dimension R. The bounded tails
(d and the primes p_{R+1}..p_L, and the smooth a) stay discrete and
produce a finite arithmetic sum. Extract coefficient A_H(1; theta)
so that
M_1(x; H) = G_m * A_H(1; theta) + (error of size O(epsilon_H)).
Let H -> oo and conclude that A = lim A_H exists, is bounded above
and below by constants, and that
V(x) ~ (x / log x) * G_m * A(1; theta).
3.4 Why the deep collision bound is really deep
Job (B) is the hard part. The collision statement we need is:
Given two different tuples tau, sigma with F(tau) = F(sigma) = v,
the number of such ordered pairs is at most (epsilon_H + o(1)) V(x).
The challenge is that the equality F(tau) = F(sigma) is a nontrivial
multiplicative constraint in the shifted primes p_i - 1 and q_j - 1. It
looks like an "abc-style" guess, but the structure of the typical tuple
pins things down enough to give a genuine estimate.
The idea (Ford's, refined here):
-- Cancel the common prefix of primes. Let i be the FIRST index where p_i
and q_i differ.
-- The residual identity groups the primes from index i onward:
prod_{j=i}^{L} (p_j - 1) D_i
= prod_{j=i}^{L} (q_j - 1) D_i'
for certain "smooth residuals" D_i and D_i'.
-- Align the largest prime factors LARGEST FIRST. Because the bands are
laid out on geometrically shrinking scales in double logarithms, the
"top largest prime" on each side (P^+(p_i-1) vs P^+(q_i-1)) must be
very close. Working down through all indices, you pin down a grid of
"which interval each p_j, q_j lives in" at resolution delta ~ b_i^{-1/3}.
-- Layered sieve: after aligning intervals, expose the small prime factors
in layers (Y_b < Y_{b-1} < ... < Y_0 = y). At each layer, equality
pins two "near-prime" conditions: A*Q + 1 and A'*Q + 1 for specially
chosen large primes Q, Q'. A two-or-three-form sieve (Ford's uniform
upper sieve) bounds the count.
-- The simplex slack (each good tuple has strict inequality with slack
h_i^{-4}) gives the factor of size exp(-kappa * B_y / h^4) that the
sieves need in order to converge. Without the slack, the layered
sieve bound would exactly match the trivial count and not suffice.
The result is a bound of the shape
#{ ordered suffix tuple pairs with y/2 < v_i <= y }
<< (y / log y) * exp( -kappa B_y / h^4 )
which, summed over dyadic scales y and over indices i, is
o(x G_m / log x). Hence almost every worthwhile totient has exactly one
tuple representing it, with no pair of distinct tuples colliding.
3.5 Order of the rest of the document
Section 4: Extraction -- Proposition 4.1.
Section 5: The comparison proposition for shifted primes (Prop 5.6).
Section 6: Prefix collisions (Prop 6.1) and uniqueness (Prop 6.7).
Section 7: Counting, fixed scaling, and the coefficient A.
Section 8: Least preimage intervals (Theorems 2 and Corollary 8.8).
------------------------------------------------------------------------------
4. EXTRACTION: FINDING A LONG PRIME PREFIX
------------------------------------------------------------------------------
Throughout sections 4-8, we fix a large integer H and set
P = floor( loglog H ), R = m - H, L = m - P.
We first let x -> oo with H fixed; then let H -> oo at the very end.
"o(1)" in what follows will mean some quantity going to 0 as x -> oo, and
"o_H(1)" will mean a quantity whose bound depends on H but tends to 0 as
x -> oo. Every "epsilon_H" is a positive number depending only on H that
tends to 0 as H -> oo. Every "o_{x;H}(1)" is a quantity bounded by
epsilon_H times x G_m / log x.
Define, for 0 <= i <= m,
h_i = m - i
alpha = B rho^m / m
b_i = alpha * h_i * rho^{-h_i}
xi_i = 1 + 10^{-4} exp( -h_i / 40 )
Notice b_0 = B (because h_0 = m and alpha * m * rho^{-m} = B rho^m * rho^{-m}
= B). This is the "double-log scale" of the i-th prime.
Two coarser bands we also use later:
0.9 b_i <= loglog(p_i) <= 1.1 b_i (coarse bands)
(u_1,...,u_L) lies in the simplex S_L(xi) defined in 4.2 below.
Both are consequences of Ford's Theorem 10 (see below).
4.1 Ford's structural theorems
Two results of Ford's 1998 paper (Theorem 10 and Theorem 16 of the revised
2013 arXiv version) drive extraction. We state them in the form we need.
FORD THEOREM 10 (bands). For each 0 < eta <= 1/8,
#{ v <= x : v in V, some preimage has
|loglog(p_i) / b_i - 1| > eta for some i <= m - P }
<<_eta V(x) * exp( -c_eta P ).
Remark. The double-log bands are "tight everywhere". If v has any
preimage that escapes even one band, v is in a set of size << V(x)
exp(-c P). Since P = floor(loglog H) -> oo as H -> oo, the escaping
set is eventually negligible relative to V(x).
FORD THEOREM 16 (simplex + cofactor). All but O(V(x) e^{-P^2/4})
values v <= x have every preimage n satisfying, writing
u_0 = B and u_i = loglog(p_i) for i >= 1,
loglog(p_L) > 2, (4.1a)
sum_{r=i+1}^{L} a_{r-i} u_r <= xi_i u_i 0 <= i < L. (4.1b)
(Here "a_j" is the sequence from section 2.2, and xi_i = 1 + 10^-4
exp(-h_i/40).)
Remark. (4.1b) is a "simplex constraint": the u_i live in a
P-dimensional polytope of shape prescribed by the a_j. This is what
makes counting by volume possible.
In the original literature Theorem 16 also has a "final adjacent
inequality" with coefficient 1 rather than a_1 < 1; we have weakened
it and still get a false-statement-equivalent inequality, which is
what (4.1b) is.
Combining Theorem 10 (with eta = 0.04) with (4.1a)-(4.1b) gives the
"basic witness" structure:
DEFINITION 4.1. A basic witness for a pair (v, x) is a factorization
v = phi( p_0 p_1 ... p_L a )
where p_0, p_1, ..., p_L are primes, a is a positive integer, and:
p_0 >= x^{0.9}, (4.2a)
0.9 b_i <= loglog(p_i) <= 1.1 b_i for 1 <= i <= L, (4.2b)
(u_1,...,u_L) lies in the simplex S_L(xi), (4.2c)
P^+(a) <= p_L, (4.2d)
log a <= exp( 2 b_L ). (4.2e)
Here u_i = loglog(p_i) for i >= 1 and u_0 = B; P^+(a) is the largest
prime factor of a (with P^+(1) = 1). The primes p_0,...,p_L are
distinct and strictly decreasing.
Because the bands b_i fall off super-exponentially (b_{i+1}/b_i < 0.62
for i near the boundary), the primes are automatically distinct and
decreasing once (4.2a)-(4.2b) hold. This is checked in the source.
PROPOSITION 4.1 (Coverage). There is a subset E_x of V intersect [1, x]
with
|E_x| <= ( epsilon_H + o(1) ) V(x)
and with the property that EVERY preimage of EVERY v outside E_x is
p_0 p_1 ... p_L a for a basic witness. One may take
epsilon_H << exp(-c P) + K_H * exp( -exp( c P rho^{-P} ) ),
where K_H = exp( C P rho^{-P} ) = H^{o(1)}.
Moreover, for every basic witness, putting w = p_{R+1} ... p_L a,
p_1 ... p_L a <= exp( (log x)^{0.8} ), (4.3a)
log w <= H exp( 0.62 b_R ) + exp( 2 b_L ), (4.3b)
w < p_R. (4.3c)
In particular, w is bounded in terms of H alone, uniformly in x and in
the phase theta(x).
The point of Proposition 4.1 is: for almost every v <= x, ALL preimages
are basic. Not just "some preimage". This is essential for the
uniqueness statement later: we can't have a stray preimage outside the
prefix form ruining the least-preimage formula.
4.2 The simplex S_L
For 1 <= j <= m, define the simplex S_j(beta) inside R^j by
S_j(beta) = { (u_1,...,u_j) : beta_i u_i - sum_{r=i+1}^{j} a_{r-i} u_r >= 0
for all 0 <= i <= j }
where beta_0 = B is a fixed constant, beta_i >= 1 for 1 <= i < j, and
beta_j = 1. For j = 0, S_0 is a single point with volume G_0 = 1.
LEMMA 4.2 (Simplex volume). For 1 <= j <= m,
(a) Volume of S_j(1) is G_j.
(b) Under uniform volume measure on S_j(1), the variables
W_i = g_i s_i / B, i = 0, 1, ..., j,
where s_i = u_i - sum_{r=i+1}^{j} a_{r-i} u_r (the slack),
are uniformly distributed on the standard simplex
{ W_i >= 0, sum_{i=0}^{j} W_i = 1 }.
(c) Volume of S_j(beta) is at most G_j prod_{r= 0, sum g_t s_t = B }.
Under the scaling s_i -> W_i = g_i s_i / B the region becomes the
standard simplex { W_i >= 0, sum_{i=0}^{j} W_i = 1 }. Substituting
s_i = B W_i / g_i for i=1,...,j with s_0 = B W_0, the Jacobian from
(W_1,...,W_j) to (s_1,...,s_j) is prod_{i=1}^{j} (B / g_i), and the
standard simplex in (W_1,...,W_j) coordinates has volume 1/j!, so
Vol(S_j(1)) = B^j / (j! prod_{i=1}^j g_i) = G_j. This is (a)-(b).
(c)-(e) follow by rescaling coordinates and bounding the Jacobian. []
We will also use a concentration inequality: the u_i concentrate near b_i.
LEMMA 4.3 (Concentration). Fix eta > 0. There are constants C_eta,
c_eta > 0 such that, if Q is an integer with 0 <= Q < m, j = m - Q,
1 <= i <= j, and h_i >= C_eta (Q+1), then under uniform volume measure
on S_j(1):
Prob( |u_i / b_i - 1| > eta ) <= C_eta exp( -c_eta h_i ).
Also for T >= 0:
Prob( u_j >= T ) = ( 1 - g_j T / B )_+^{j} <= exp(-j g_j T / B).
PROOF. By g_j ~ gamma rho^{-j} and Lemma 4.2(b),
u_i / (B rho^i) = sum_{t=i}^{j} (1 + O(rho^{t-i})) W_t,
i.e. a weighted average of W_t with exponentially decreasing weights.
Write W_t = E_t / sum_{r=0}^{j} E_r with E_t i.i.d. exponential. The
main term has j - i + 1 = h_i - Q + 1 terms; the error term has bounded
exponential moment since prod_{r>=0} (1 - z rho^r)^{-1} < infinity.
Exponential moment bounds on the weighted sums give the first
assertion. The second is the exact marginal tail of W_j. []
4.3 Prime boxes and smooth cofactors
The replacement of sums over primes by volumes uses unit boxes in the
coordinates loglog p and Mertens' theorem.
LEMMA 4.4 (Mertens in unit boxes). Uniformly for b >= 2:
sum_{b <= loglog p < b+1} 1 / (p - 1) = 1 + O( exp(-b) ).
PROOF. Mertens' theorem gives the sum of 1/p over such an interval.
The replacement of 1/p by 1/(p-1) changes each summand by
O(1/(p(p-1))) which is negligible in the interval where p is
astronomically large. []
We use the following estimate for the whole simplex. It is essentially
Ford's Lemma 3.1 in his notation.
LEMMA 4.5 (Total projected mass). For 0 <= j <= L,
sum_{p_1,...,p_j} prod_{i=1}^{j} 1/(p_i - 1) << G_m,
where the sum runs over primes satisfying
0.9 b_i <= loglog(p_i) <= 1.1 b_i,
(u_1,...,u_j) in S_j(xi).
PROOF. Every unit box meeting the allowed region lies in S_j(beta)
where beta_t = 1 + C ( e^{-h_t/40} + h_t^2 rho^{h_t} ). The volume of
S_j(beta) is at most G_j times a bounded factor: Lemma 4.2(c) and the
observation that sum_{t < j} (j - t) * (small) < infinity give
prod_{r= P} h e^{-h/40}) << 1.
Multiplying the unit-box Mertens sums across all coordinates costs
at most a constant factor (the lower endpoints grow geometrically
backward, so errors shrink geometrically). Finally G_j / G_m << 1
by equation (4.5) below. This gives the stated bound. []
We also need a "shell" estimate for boundary losses: if the simplex
constraint is nearly tight, the volume is small.
LEMMA 4.6 (Shell mass). Fix A > 0. Among unit boxes meeting the
allowed region, retain those with a point satisfying, for some i <= R,
at least one of:
(i) i >= 1 and u_i is within A of a coarse band endpoint;
(ii) | xi_i u_i - sum_{r=i+1}^{L} a_{r-i} u_r | <= A h_i^2;
(iii) sum_{r=i+1}^{L} a_{r-i} u_r >= (1 - h_i^{-4}) u_i.
The total volume of these boxes and their total reciprocal-prime
weight is
O_A( H^{-2} G_m ).
Moreover if we only need (i)-(ii), or the region lost by replacing
xi_i with 1, the stronger bound holds:
O_A( G_m sum_{h >= H} ( h e^{-h/40} + h^3 rho^h ) ) = o_H(1) G_m.
PROOF. A tube of width O(h_i^2) around boundary (ii) has slack
s_i <= b_i ( e^{-h/40} + h^{-4} + h^3/b_i ). By Lemma 4.2(d), the
volume fraction is <= const * h_i * g_i / B * b_i * (...) << h_i^{-3}
+ h_i e^{-h_i/40} + h_i^3 rho^{h_i}. Summing over i >= H gives the
first part. Boundary (i) is a tube of width O(1) around a band
endpoint: volume fraction <= const * rho^{h_i}, summable. Boundary
(iii) is the largest boundary cost: dropping h_i^{-4} from the slack
interval gives a factor of h_i^{-3} which sums to H^{-2}. []
We will also need a smooth-number tail estimate to handle the factor a.
LEMMA 4.7 (Smooth-number tail). Uniformly for Y >= exp(exp(2)),
Z >= 0:
sum_{P^+(a) <= Y} a^{1/log Y} / phi(a) << log Y,
sum_{P^+(a) <= Y, log a > Z} 1 / phi(a) << (log Y) e^{-Z/log Y}.
In particular, taking Y = exp(exp(1.1 b_L)) and using b_L ~ P rho^{-P}:
sum_{P^+(a) <= Y} 1 / phi(a) <= K_H,
sum_{log a > exp(2 b_L)} 1 / phi(a) <= K_H exp( -exp(c P rho^{-P}) ).
Here K_H = exp(C P rho^{-P}) = H^{o(1)}.
PROOF. Put sigma = 1/log Y. The Euler factor for a is
1 + p^sigma / ( (p-1) (1 - p^{sigma-1}) ),
whose log is p^{sigma-1} + O(p^{-2+2sigma}). Partial summation gives
sum_{p <= Y} (p^{sigma-1} - p^{-1}) = O(1), so the product over p <= Y
is O(log Y). The tail bound follows from Rankin's inequality (i.e.
weighting each a by a^{sigma}). The exponent 1.1 b_L - exp(0.9 b_L)
is exponentially negative by b_L ~ P rho^{-P}. []
LEMMA 4.8 (G_j uniform bound). For 0 <= j <= m,
G_j / G_m = prod_{i=j+1}^{m} ( i g_i / B )
<= C^{m-j} rho^{(m-j)(m-j-1)/2} << 1.
PROOF. By the recurrence estimate in section 2.2 (Ford's Lemma 3.7),
g_i = gamma rho^{-i} + O(1). Then i g_i / B ~ gamma i rho^{-i} / B.
Since B ~ alpha m rho^{-m}, i g_i / B ~ (gamma/alpha) (i/m) rho^{m - i}.
For i = j+1,...,m the accumulated product telescopes into the stated
bound. []
4.4 Proof of the coverage proposition 4.1
Fix eta = 0.04 in Ford's Theorem 10. Using the trivial comparison
alpha / alpha_theta = 1 + O(log m / m) (immediate from B = alpha m rho^{-m}
and alpha_theta = lambda * exp(lambda theta)), the strict bands
0.96 b_i <= loglog p_i <= 1.04 b_i (Ford's hypothesis rescaled) imply
the coarse bands 0.9 b_i <= loglog p_i <= 1.1 b_i.
Apply Theorem 16 as well. Both conclusions (bands and simplex) hold for
all preimages of a v outside an exceptional set E_1 with
|E_1| <= V(x) [ O_m(e^{-m/13}) + O(e^{-P^2/4}) ] << V(x) e^{-cP}.
Next remove v <= x^{0.95} and Omega(v) > 5 B; each contributes o(V(x)).
For the second:
#{v <= x : Omega(v) > 5 B} <= z^{-5B} x sum_{r <= x} z^{Omega(r)}/r
by Markov with z = 1.9 < 2. The Euler product gives the sum
<< (log x)^{1.9}, so the whole thing is << x (log x)^{1.9} exp(-5 B log z)
= x exp( -B (5 log z - 1.9) + o(B) ) = o(x / log x), since 5 log z - 1.9
> 1.
Then p_1 <= exp((log x)^{0.61}) from the upper band (loglog p_1 <= 1.1 b_1
~ 1.1 alpha (m-1) rho^{-(m-1)} = (1 + o(1)) * (lambda/m)* B << B * loglog B
<< (log x)^{0.61} for large H). Combined with Omega(n) <= 5 B + 1,
log p_0 = log v - sum_{i=1}^{L} log p_i - log a - log(other factors)
>= 0.95 log x - 6 B * (log x)^{0.61} > 0.9 log x.
That gives p_0 >= x^{0.9}.
The only remaining constraint is (4.2e), log a <= exp(2 b_L). Fix
p_1,...,p_L, a and count p_0: supermultiplicativity of phi gives
phi(p_0...p_L a) >= (p_0 - 1) phi(a) prod_{i=1}^{L} (p_i-1),
so phi(...) = v forces p_0 - 1 <= x / (phi(a) prod (p_i-1)). The prime
number theorem gives at most
C x / log x * 1/(phi(a) prod (p_i-1))
choices of p_0, provided the upper endpoint >= x^{0.9}; if not the count
is zero. Sum the prefix by Lemma 4.5 and the cofactor a by Lemma 4.7.
This bounds values v that fail (4.2e) by
O( x / log x * K_H * exp(-exp(c P rho^{-P})) ),
which is o(V(x)) when combined with the Ford order estimate V(x) =~
x G_m / log x. Every remaining exception thus lives in E_x with the
stated bound. []
Finally (4.3a): p_1 ... p_L a <= exp( (log x)^{0.8} ) follows from the
p_1 band and L <= m - P. The next (4.3b):
b_{i+1} = alpha (h_i - 1) rho^{-h_i+1} = alpha h_i rho^{-h_i} rho / (1 - 1/h_i)
= b_i rho / (1 - 1/h_i) < 0.62 b_i / (1 - 1/h_i).
Iterating, the tail primes after p_R have loglog <= 0.62 b_R * H. So
sum_{i=R+1}^{L} loglog(p_i) <= H * 0.62 b_R. Similarly loglog(a) <=
2 b_L. Adding exponentials: log w <= H exp(0.62 b_R) + exp(2 b_L).
This is < p_R for large H and x. (4.3c). []
4.5 The set T(t): distinct tuples
Let t = x or t = x/c for a fixed c > 1. All parameters (B, m, theta,
alpha, h_i, b_i) are formed from x, not t.
DEFINITION 4.9 (Tuples). A tuple at level t is a list
tau = (p_0, p_1, ..., p_R, d)
where p_0,...,p_R are distinct primes, d is a positive integer, and
some basic witness exists with w = p_{R+1} ... p_L a satisfying
phi(w) = d, and d * prod_{i=0}^{R} (p_i - 1) <= t.
T(t) = set of distinct tuples with that property.
Each tuple represents a totient
F(tau) = d * prod_{i=0}^{R} (p_i - 1).
Because w < p_R (Proposition 4.1), the tail w and the prefix pads
p_0..p_R are coprime, so phi(p_0..p_R w) = F(tau) indeed. Several
witnesses may give the SAME tuple; T(t) counts each tuple once.
DEFINITION 4.10 (Good and bad tuples). Fix 0 <= i <= R. Set
h = h_i,
J_i = ceil(30 log h),
S_i = exp( exp( b_i^{1/3} ) ),
z_i = exp( exp( 0.7 b_{i+J_i} ) ).
For a basic witness as in Definition 4.1, write
D_i = phi( p_{i+J_i+1} p_{i+J_i+2} ... p_L a ) (empty product:
D_i = phi(a)).
For large H these indices exist: J_i < h_i/2 and i + J_i < L.
A tuple tau is GOOD if EVERY basic witness giving tau satisfies,
for every 0 <= i <= R:
sum_{r=i+1}^{L} a_{r-i} u_r <= (1 - h_i^{-4}) u_i (4.4a)
p_i, p_{i+1}, ..., p_{i+J_i} are S_i-normal (Def 4.11 below), (4.4b)
prod_{j=i}^{i+J_i} (p_j - 1) is squarefree on primes > z_i, (4.4c)
Omega( D_i ) <= b_i / h_i^{8}. (4.4d)
Denote G(t) = set of good tuples, D(t) = T(t) \ G(t).
We need "S-normal":
DEFINITION 4.11 (S-normal prime). For S >= e^e, a prime p is
S-normal if
Omega(p - 1, 1, S) <= 2 loglog(S) (i.e. 2 * log_2 S) and,
for every S <= U < T <= p - 1,
| Omega(p - 1, U, T) - (log_2 T - log_2 U) | <
sqrt( log_2 S * log_2 T ).
Here Omega(n, U, T) is the number of prime factors of n in (U, T],
counted with multiplicity, and Omega(n) = Omega(n, 1, n) with Omega(1)
= 0.
Ford's Lemma 2.6 (in his 2013 revision) gives: uniformly for z >= 3,
#{ p <= z : p is NOT S-normal } << (z / log z) (loglog z)^5 / (log S)^{1/6}.
This inequality is used in the discard proposition 4.12.
PROPOSITION 4.12 (Discard). For t = x and t = x/c, with the same
x-dependent parameters:
|D(t)| <= ( epsilon_H + o(1) ) * x G_m / log x.
One may take epsilon_H << K_H H^{-2}. Also, for any good tuple,
P^+(D_i) < z_i, S_i < z_i, c h_i^{-20} <= b_{i+J_i}/b_i <=
C h_i^{-18}. (4.5)
PROOF. The last comparison:
b_{i+J}/b_i = (1 - J/h) rho^{J}
with J = ceil(30 log h) and 18 < 30 log(1/rho) < 20; replacing the
ceiling changes only constants, so (4.5) follows. From (4.5),
S_i < z_i (since b_{i+J} < 0.7 b_i). The prime bands give
loglog of every remaining prime (including p_{i+J+1}, ..., p_L, and
the factors of a) less than 0.7 b_{i+J}; taking a totient cannot
introduce a prime factor above this bound, so P^+(D_i) < z_i.
For |D(t)|: a bad tuple has at least one failing witness. Bound the
count of these failing witnesses; this upper-bounds the number of
bad tuples regardless of witness multiplicity. The prime number
theorem for p_0 contributes C x / log x, with the product of
reciprocal factors for the other variables. The smooth-a sum
contributes K_H by Lemma 4.7.
(i) Failure of (4.4a): Lemma 4.6 condition (iii) with
A = 1 (after adjusting the simplex): contribution is
O( K_H H^{-2} x G_m / log x ). This is the dominant error.
(ii) Failure of (4.4b): For each i, at most H indices. Partial
summation of the normal-prime bound gives
sum_{p <= exp(exp(1.2 b)) non-normal} 1/(p - 1) <<
(1+b)^6 exp(-b^{1/3}/6).
Total relative to x G_m/log x:
K_H sum_{h >= H} exp(C h^2 - c b(h)^{1/3}) = exp(-c' H^{1-o(1)}).
(iii) Failure of (4.4c): A square q^2 | (p-1) for q > z_i. For each
prime q, sum_{p : q^2 | p-1} 1/p << 1/q^2. Summing over
q > z_i gives sum_{q > z_i} 1/q^2 << 1/z_i, exponentially
small. Multiplied by 2^{Omega(D_i)} possibilities, still small.
This gives the bound (4.4c).
(iv) Failure of (4.4d): Omega(D_i) > b_i/h_i^8. Since Omega(a) <<
log a <= exp(2 b_L) = H^{o(1)}, and b_i/h_i^8 is exponentially
large for h_i >= H, failure requires some i+J < j <= L with
Omega(p_j - 1) > b_i/(2 h^9). The Euler product bound
sum_{n <= Z} (3/2)^{Omega(n)} / n << (log Z)^{3/2}
gives the exceptional reciprocal sum <=
exp(C b_{i+J} - c b_i/h^9) <= exp(-c'b_i/h^9), exponentially
small. This contributes K_H sum e^{-c b_i/h^9} << H^{-2}.
Each error in (i)-(iv) is bounded by (epsilon_H + o(1)) with
epsilon_H << K_H H^{-2}, and the (i) term is the largest. For t=x/c,
the witness set only decreases, so the same bound holds. []
A consequence of Proposition 4.12 we use later: the good tuples'
"tail-D values" are tightly controlled: within any good tuple,
log_2 z_i << b_i h_i^{-18}, and log_2 S_i = b_i^{1/3}.
4.6 From tuples to values
LEMMA 4.13 (Finite-map). Let T, W be finite sets, F : T -> W. Write
T = G disjoint-union D. Suppose every w in W \ E has a preimage in T for some
E subset-of W. For w in W put r_w = |G intersect F^{-1}(w)|, K = sum_w r_w (r_w-1).
Then
-|E| <= |T| - |W| <= |D| + K/2.
Moreover, with E* = E union F(D) union {w : r_w >= 2},
|E*| <= |E| + |D| + K/2,
|F^{-1}(E*)| <= |E| + 2|D| + K.
The restriction F |_{T \ F^{-1}(E*)} is a bijection onto W \ E*.
PROOF. Coverage gives the lower bound. Since r - 1 <= r(r-1)/2 for
r >= 0, |G| - |F(G)| <= K/2, and adding the <= |D| remaining elements
of T gives the upper bound. # of fibers with r_w >= 2 is <= K/2
(since each such fiber contributes r_w(r_w-1) >= 2). For
sum_{w in E*} r_w: r <= 1 + r(r-1)/2 gives sum_{w in E*} r_w <=
|E*| + K/2. Add the |D| elements of D. Outside E*, coverage, absence
of discarded elements, and |F^{-1}(w) intersect G| <= 1 give exactly one
preimage under F. []
PROPOSITION 4.14 (Common prefix). For t = x or t = x/c:
| |T(t)| - V(t) | <= ( epsilon_H + o(1) ) x G_m / log x. (4.6)
There is a set E*(t) subset-of V intersect [1, t] with both
|E*(t)| <= (epsilon_H + o(1)) x G_m / log x
and (after enlarging epsilon_H)
# of tuples in T(t) with values in E*(t) <= same.
For every v in (V intersect [1, t]) \ E*(t): there is a unique tuple
(p_0, ..., p_R, d) in T(t) with F(tuple) = v, every preimage of v has
that prefix and a remaining factor of totient d, and
ell(v) = p_0 p_1 ... p_R * ell(d). (4.7)
PROOF. Apply Lemma 4.13 to T = T(t), G = G(t), D = D(t),
W = V intersect [1, t], F(tau) = d * prod (p_i - 1). Let E be the exceptional
values in Proposition 4.1, restricted to [1, t]. Every preimage of
every v outside E is basic, so it induces an element of T.
|E| = (epsilon_H + o(1)) x G_m / log x by Ford's order estimate.
|D| is bounded by the same by Proposition 4.12. The prefix collision
K = sum_w r_w (r_w - 1) is bounded by Proposition 6.1 (proof in
section 6) with the same bound. The counting conclusions of
Lemma 4.13 follow.
Now fix v not in E*(t). Every preimage is basic, so gives a tuple in
T(t). It cannot give a tuple in D(t) because v is not in F(D(t)).
Remaining: unique tuple in G(t) with value v. Write Q = p_0...p_R.
Every preimage is Q z for some z with phi(z) = d; so every preimage is
>= Q * ell(d).
For the reverse inequality: choose one basic witness with tail w.
By (4.3c), w < p_R, so ell(d) <= w < p_R. The prefix primes are
distinct so gcd(Q, ell(d)) = 1. Multiplicativity gives
phi(Q ell(d)) = phi(Q) phi(ell(d)) = v.
Therefore ell(v) <= Q ell(d). This proves (4.7). []
The universal quantifier "every preimage" in Proposition 4.1 is what
gives the reverse inequality ell(v) <= Q ell(d): if only one preimage
were basic, we would only know ell(v) <= Q ell(d) for that particular
representation, not for every representation. The "no stray preimage"
property is key.
------------------------------------------------------------------------------
5. COMPARING PRODUCTS OF SHIFTED PRIMES
------------------------------------------------------------------------------
We now prove the "collision" bound that underpins uniqueness. Section 5
establishes the deep estimate on products of shifted primes. Section 6
then plugs it in to bound K = sum_w r_w (r_w - 1) directly.
The comparison machinery is the deepest part of the proof. It is taken
from Ford's paper (Lemma 5.1 and the surrounding analysis), refined here
to accommodate the two-cut structure and the specific slack parameters
we've chosen.
5.1 The uniform sieve lemma
The engine is a sieve bound with two or three linear forms.
LEMMA 5.1 (Uniform sieve). There are absolute constants C and y_0
with the following property. Let y >= y_0, B_y = loglog y. Let
1 <= A, A' <= y be integers. Consider either the TWO forms
n, A n + 1
or the THREE forms
n, A n + 1, A' n + 1 with A != A'.
Write k = 2 or 3 (respectively). Let P subset-of Z_{>= 1} be the set of n
at which all indicated forms are prime. Then, uniformly for X >= 3:
#(P intersect [1, X]) <= C X (B_y)^k / (log X)^k. (5.1)
Moreover, uniformly for 3 <= U <= Y,
sum_{n in P, U <= n <= Y} 1/n <= C (B_y)^k / (log U)^{k-1}. (5.2)
The coefficients A, A' need NOT be bounded in terms of X or U -- only
in terms of y. (So the bound is uniform in A, A', but not in y.)
PROOF. Apply Ford's uniform upper sieve (his Theorem 2.5, published
in his 2023 lecture notes): for primitive, distinct, admissible
integral linear forms a_j n + b_j with positive leading coefficients
and nonzero determinant Delta = |prod a_j prod_{j= y_0 and
b in [1, B_y]. Choose cutoffs
Y_0 = y, S >= e^e, Y_{j+1} < U_j < Y_j for 0 <= j < b.
Set
nu_j = loglog(Y_j) / B_y (0 <= j <= b),
mu_j = loglog(U_j) / B_y (0 <= j < b),
delta = sqrt( loglog(S) / B_y ).
Fix a positive integer D with P^+(D) <= Y_b and a real r >= 1.
Let N count ordered tuples (p_0,...,p_{b-1}, q_0,...,q_{b-1}, D')
with p_j, q_j primes, D' positive integer, satisfying:
(i) p_j, q_j are S-normal primes, and p_j != q_j;
U_j <= P^+(p_j - 1), P^+(q_j - 1) <= Y_j for 0 <= j < b.
(ii) P^+(D') <= Y_b and
D * prod_{j=0}^{b-1} (p_j - 1)
= D' * prod_{j=0}^{b-1} (q_j - 1) <= y/r.
(iii) The common product in (ii) is squarefree on primes > Y_b.
(iv) The part of p_0 - 1 supported above Y_1 exceeds sqrt(y).
PROPOSITION 5.6 (Comparison). There are absolute constants C and
y_0 such that, with the notation of Definition 5.2,
N <= (y / (r D)) * (C B_y^6)^b * (b+1)^{Omega(D)}
* (log Y_b)^{ 1 + 3b log(b(b+1)) }
* (log y)^{ -2 + sum_{j=1}^{b-1} a_j nu_j + E_b }, (5.6)
where
E_b = 2 sum_{j=1}^{b-1} (nu_j - mu_j)
+ delta * sum_{i=2}^{b} ( i log i + i ). (5.7)
Empty sums are zero when b = 1, in which case Y_1 = Y_b.
PROOF. Deferred to section 5.3. []
Remark. The KEY term is the exponent of log y:
-2 + sum_{j=1}^{b-1} a_j nu_j + E_b.
If the weighted sum of the a_j nu_j were 1 (the simplex equality),
the exponent would be -1 + E_b, and the overall bound would be
comparable to y/(log y) * everything. Precisely because the good
tuples have strict simplex slack h_i^{-4}, we have
sum_{j=1}^{b-1} a_j nu_j <= 1 - h^{-4} + o(1),
and hence the exponent is -1 - (a bit), giving a genuine SAVING over
the trivial count. That saving absorbs the K_H-tail cost (recovering
tuple data inside the smooth remainder) in section 6.
5.3 Proof of the comparison proposition 5.6
We follow Ford's layered structure. The two innovations relative to his
version are: the constants must be uniform in the number of layers b
(which grows like B_y = loglog y), and the strict simplex slack h^{-4}
in the good tuple conditions must show up explicitly in the final
exponent of log y.
5.3.1 Layer configurations
For 0 <= i <= b and 0 <= j < b, define
s_{i,j} = prod over primes p <= Y_i with p^a || (p_j - 1),
of p^a,
s'_{i,j} = the same with q_j - 1 in place of p_j - 1.
Restricting the equality in (ii) of Definition 5.2 to primes <= Y_i
gives the common product
s_i# = D * prod_{j=0}^{b-1} s_{i,j} = D' * prod_{j=0}^{b-1} s'_{i,j}.
(We use "s_i#" as shorthand for the original "s_i^\#".) For 1 <= i <= b,
put
t_{i,j} = s_{i-1,j} / s_{i,j},
t'_{i,j} = s'_{i-1,j} / s'_{i,j},
t_i# = s_{i-1}# / s_i#.
Each t_i# is squarefree (by condition (iii) of Definition 5.2) and has
all prime factors in the interval (Y_i, Y_{i-1}]. For j >= i, the
individual factors t_{i,j} = t'_{i,j} = 1 because the shifts p_j - 1,
q_j - 1 have no prime factor above Y_j, and by the cutoff ordering
Y_j <= Y_i. So each layer i consists of TWO allocations of the same
squarefree integer t_i# among i labeled slots:
t_i# = prod_{j=0}^{i-1} t_{i,j} = prod_{j=0}^{i-1} t'_{i,j}. (5.8)
Now define the configuration space. For 0 <= i <= b,
sigma_i = (D', s_{i,0}, ..., s_{i,b-1}, s'_{i,0}, ..., s'_{i,b-1}),
C_i = set of such sigma_i arising from tuples counted by N.
Restriction of prime factors maps C_{i-1} into C_i; each extension is
uniquely determined by the two allocations in (5.8). Reconstructing a
tuple from the small prime factors runs from C_b back to C_0; the
weighted summation we are about to perform goes the OPPOSITE way, from
C_0 up. The original tuples are in bijection with C_0 because
p_j = s_{0,j} + 1 and q_j = s'_{0,j} + 1.
For i >= 2 we bound, uniformly in sigma_i, the "extension weight":
W_i(sigma_i) := sum over sigma_{i-1} in C_{i-1} restricting to
sigma_i, of 1 / t_i#.
This is the right weight to sum because
1 / s_{i-1}# = 1 / (s_i# * t_i#).
Exactly the same remark appears in Ford's argument.
5.3.2 Top layer (i = 1)
Only the shift p_0 - 1 (or q_0 - 1) can contribute a prime factor above
Y_1: for j >= 1 the shift p_j - 1 has P^+ <= Y_j <= Y_1 by condition
(i). So t_1# is the (Y_1, y]-part of p_0 - 1 and also of q_0 - 1.
Condition (iv) says |(p_0 - 1)_{> Y_1}| > sqrt(y). Combined with
normality of p_0 (condition (i)):
Omega(p_0 - 1) <= B_y + loglog S + sqrt(B_y loglog S) <= 3 B_y.
(Here we use S = S in Definition 5.2, so loglog S <= B_y.) Write
t_1# = t' * Q, t' = (t_1# / Q), Q = P^+(t_1#).
The bound Omega(t_1#) <= 4 B_y comes for free and gives
Q >= y^{1/(8 B_y)}.
After fixing sigma_1 and t', the two completed primes have the form
p_0 = A Q + 1, q_0 = A' Q + 1, A != A'
(their difference forces A != A', which is exactly the nonzero determinant
condition for the k = 3 sieve). With
X = y / (r * s_1# * t')
we have X >= Q >= y^{1/(8 B_y)} when the extension is nonempty, so
Lemma 5.1 with k = 3 (three forms n, A n + 1, A' n + 1 applied at n = Q)
gives
# { Q : A Q + 1 and A' Q + 1 both prime }
<< (X / Q) * B_y^6 / (log X)^3
<< (X / Q) * B_y^6 / (log y)^3.
The factor 1/Q from summing over Q is estimated by
sum_{t' : t' is squarefree, supported on (Y_1, y]} 1/t'
<= prod_{Y_1 < p <= y} (1 + 1/p)
<= (log y) / (log Y_1) = (log y) / (nu_1 B_y).
Combining, for each sigma_1:
#{sigma_0 : restricting to sigma_1}
<= C B_y^6 * (y/(r s_1#)) * (log y)^{-2 - nu_1}. (5.10)
(The bounded powers of B_y from the Mertens logarithm and from the sieve
absorb into the constant; the exact power of B_y is a fixed polynomial,
which is all we need.)
5.3.3 Intermediate layers (2 <= i <= b)
Fix 2 <= i <= b and a configuration sigma_i. The i-1-th slot is
"completed" after this layer: the primes p_{i-1}, q_{i-1} become fully
determined. Let
Q_1 = P^+ of the shift p_{i-1} - 1 restricted to (Y_i, Y_{i-1}],
Q_2 = P^+ of the shift q_{i-1} - 1 restricted to (Y_i, Y_{i-1}].
Both lie in [U_{i-1}, Y_{i-1}] by condition (i).
Case A: Q_1 = Q_2 = Q (shared prime).
Remove the single occurrence of Q from t_i# and call the result t.
Then the two remaining completed-prime conditions become
A Q + 1 prime, A' Q + 1 prime, A != A'.
By Lemma 5.1 with k = 3 applied to the two-form structure on n = Q
(with A, A' the products of the other already-determined shifts), we get
sum_Q 1/Q <= sum_{n in [U_{i-1}, Y_{i-1}] with A n + 1 and A' n + 1 prime} 1/n
<< B_y^3 / (log U_{i-1})^2. (5.11)
Case B: Q_1 != Q_2 (two distinct primes).
Remove both Q_1 and Q_2 from t_i#, obtaining t.
Case B1: Q_1 and Q_2 lie in DIFFERENT slots of the layer. Then the two
remaining conditions are
A Q_1 + 1 and A' Q_2 + 1
both prime, applied at n = Q_1 and n = Q_2 respectively. These are
independent k = 2 sieves, each with parameter range [U_{i-1}, Y_{i-1}].
Applying (5.2) twice:
sum_{Q_1, Q_2} 1/(Q_1 Q_2) << B_y^4 / (log U_{i-1})^2. (5.12)
Case B2: Q_2 lies in the LAST SLOT on the first side (i.e., q_{i-1} = Q_2
contributes a prime to p_{i-1}'s slot too). Then Q_2 < Q_1 (because
P^+(p_{i-1} - 1) = Q_1 > Q_2 by definition of Q_2 being in a lower slot).
Symmetrically Q_1 cannot lie in the last slot on the second side (whose
largest prime is Q_2 < Q_1). So the two conditions are
A Q_2 Q_1 + 1 prime, and A' Q_2 + 1 prime.
First sum over Q_1 conditional on Q_2. The forms are n and A Q_2 n + 1,
with leading coefficient A Q_2 <= y (by the size bound on A), so the
k = 2 sieve gives
sum_{Q_1 : A Q_2 Q_1 + 1 prime} 1/Q_1 << B_y^2 / (log U_{i-1}).
Then sum over Q_2:
sum_{Q_2 : A' Q_2 + 1 prime} 1/Q_2 << B_y^2 / (log U_{i-1}).
Combined:
sum_{Q_1, Q_2} 1/(Q_1 Q_2) << B_y^4 / (log U_{i-1})^2. (5.13)
The incidence B2 is handled by reversing the two sides; both B2
orientations cannot hold simultaneously (they would force
Q_1 < Q_2 < Q_1).
5.3.4 Allocation counting
The integer t (after removing Q_1, Q_2) is squarefree, supported on
(Y_i, Y_{i-1}]. Each shift p_j - 1 for j <= i-1 contributes at most
some number of such prime factors by normality: in the interval
(Y_i, Y_{i-1}], normality bounds Omega(p_j - 1, Y_i, Y_{i-1}) by
(Delta_i + delta) * B_y
where Delta_i = nu_{i-1} - nu_i and delta = sqrt(loglog S / B_y) (the
second term is the normality slack). Only i shifts contribute to
this layer; removing Q_1, Q_2 only decreases the count. So
Omega(t) <= I_i := i (Delta_i + delta) B_y.
Since t is squarefree, each prime factor of t chooses one of i slots
on each side, giving at most i^{2 Omega(t)} allocations. The
reciprocal-prime contribution is at most
M_i = sum_{Y_i < p <= Y_{i-1}} 1/p <= Delta_i B_y + O(1).
(We do not need the O(1) because delta B_y >= sqrt(B_y) dominates it.)
Multiplying:
sum_t i^{2 Omega(t)} / t
<= sum_{n <= I_i} (i^2 M_i)^n / n!
<= i^{I_i} * exp(i M_i)
<= exp( (i log i + i)(Delta_i + delta) B_y ). (5.14)
The middle inequality writes i^{2n} = i^n * i^n, bounds i^n <= i^{I_i},
and extends the remaining exponential series. It is valid without any
lower bound on Delta_i / delta.
Combining (5.11), (5.12), (5.13), and (5.14), and using i <= b <= B_y
to absorb the i^2 position choices:
W_i(sigma_i) <= C B_y^6
* (log y)^{-2 mu_{i-1} + c_i (nu_{i-1} - nu_i + delta)} (5.15)
where c_i = i log i + i. The exponent of log y here is
-2 mu_{i-1} + c_i * (nu_{i-1} - nu_i) + c_i * delta.
5.3.5 Multiplying the layer estimates
Starting from (5.10) (= top layer for sigma_1), sum over C_1. Then,
for each i = 2, ..., b, use the exact multiplicative identity
sum_{sigma_{i-1} in C_{i-1}} 1/s_{i-1}#
= sum_{sigma_i in C_i} 1/s_i#
* sum_{sigma_{i-1} restricting} 1/t_i#.
This is where the weights W_i(sigma_i) enter. All bounds (5.15) are
UNIFORM in the coarser configuration sigma_i (that is the "uniformly
in sigma_i" property established above). Their constants C, B_y^6
multiply to give (C B_y^6)^{b-1} for the b-1 intermediate layers.
The accumulated log-power exponent is
-2 - nu_1 + sum_{i=2}^{b} [-2 mu_{i-1} + c_i (nu_{i-1} - nu_i + delta)]
= -2 - nu_1 + sum_{i=2}^{b} c_i nu_{i-1} - sum_{i=2}^{b} c_i nu_i
- 2 sum_{i=2}^{b} mu_{i-1} + delta sum_{i=2}^{b} c_i.
Reindex the first sum with j = i - 1:
-2 - nu_1 + sum_{j=1}^{b-1} c_{j+1} nu_j - sum_{i=2}^{b} c_i nu_i
- 2 sum_{j=1}^{b-1} mu_j + delta * sum_{i=2}^{b} c_i.
Now compute the coefficient of nu_j for each j = 1, ..., b-1.
For j = 1: the top-layer term contributes -nu_1, and the first
reindexed sum contributes c_2 nu_1. The second sum (over i = 2..b)
starts at i = 2, so it does NOT contribute at j = 1. Coefficient:
c_2 - 1 = (2 log 2 + 2) - 1 = 2 log 2 + 1 = a_1 + 2.
For j = 2, ..., b-1: the first reindexed sum contributes c_{j+1} nu_j,
and the second sum (with i = j) contributes -c_j nu_j. Coefficient:
c_{j+1} - c_j = a_j + 2. (Check: c_{j+1} - c_j
= (j+1) log(j+1) + (j+1) - j log j - j
= (j+1) log(j+1) - j log j + 1
= a_j + 2, using a_j = (j+1) log(j+1) - j log j - 1.)
For j = b: the second sum has a term -c_b at index i = b. Coefficient:
-c_b <= 0.
Therefore the total log-power exponent from all layered contributions is
-2 + sum_{j=1}^{b-1} (a_j + 2) nu_j
- 2 sum_{j=1}^{b-1} mu_j
+ delta sum_{i=2}^{b} c_i
- c_b nu_b. (5.15b)
Regroup: sum_{j=1}^{b-1} (a_j + 2) nu_j - 2 sum_{j=1}^{b-1} mu_j
= sum_{j=1}^{b-1} a_j nu_j + 2 sum_{j=1}^{b-1} (nu_j - mu_j).
Discard -c_b nu_b (nonpositive; dropping it can only enlarge the bound).
Result:
accumulated log-exponent
= -2 + sum_{j=1}^{b-1} a_j nu_j
+ 2 sum_{j=1}^{b-1} (nu_j - mu_j)
+ delta sum_{i=2}^{b} c_i.
Identify E_b := 2 sum_{j=1}^{b-1}(nu_j - mu_j) + delta sum_{i=2}^{b} c_i,
which is exactly (5.7). This gives the log-y factor
(log y)^{-2 + sum_{j=1}^{b-1} a_j nu_j + E_b}, (5.16)
matching the exponent in (5.6).
5.3.6 Smooth parts below Y_b
The remaining step is to bound the innermost sum
sum_{sigma_b in C_b} 1/s_b#.
Write s = s_b# / D and L_b = loglog(Y_b). The integer s has all prime
factors <= Y_b. For a fixed s, its allocation among the b left slots
has at most b^{Omega(s)} possibilities (each prime occurrence chooses a
slot), and the allocation of sD among the b right slots and the extra
slot D' has at most (b+1)^{Omega(sD)} possibilities.
Every left shift has largest prime factor > Y_b (by condition (i)), so
normality on each shift gives
Omega(p_j - 1, 1, Y_b) <= 3 L_b.
Summing over j in the layer-free bottom (i.e. all b shifts), we get
Omega(s) <= 3 b L_b.
An Euler product gives
sum_{P^+(s) <= Y_b} 1/s = prod_{p <= Y_b} (1 - 1/p)^{-1}
~ exp(gamma_log) log Y_b
<< log Y_b.
Combining:
sum_{sigma_b} 1/s_b#
<= (b+1)^{Omega(D)} / D * [b(b+1)]^{3b L_b} * log Y_b
= (b+1)^{Omega(D)} / D * (log Y_b)^{1 + 3b log(b(b+1))}.
This, applied to the (5.16) expression and multiplied by the top-layer
factor y/(r D) and the intermediate-layer constants, gives exactly (5.6).
5.3.7 Wrap-up
Multiplying (5.10), (5.15) multiple times, and the smooth-part bound,
with all constants collected:
N <= (C B_y^6)^b * y / (r D) * (b+1)^{Omega(D)}
* (log Y_b)^{1 + 3b log(b(b+1))}
* (log y)^{-2 + sum_{j=1}^{b-1} a_j nu_j + E_b}.
This is (5.6), completing the proof of Proposition 5.6. []
Remark (why the exponent of log y really saves).
In our application (Section 6), the cutoffs Y_j and U_j are chosen
from good tuples. For a good tuple with strict slack h^{-4}, we have
sum_{j=1}^{b-1} a_j nu_j <= 1 - h^{-4} + O(J^2 log(2J) delta). So
-2 + sum a_j nu_j + E_b <= -1 - h^{-4} + (small corrections),
where "small" means the E_b perturbation 2 sum(nu_j - mu_j) +
delta sum c_i <= c J^2 log(b) * delta = O(h^{-4/3}) when
J = ceil(30 log h) and delta ~ b_i^{-1/3} << h^{-1/2}. Hence the
total is <= -1 - c h^{-4} for a positive constant c. Comparing to
the trivial bound y / log y (a gain of one log-power), this saves a
factor of (log y)^{-c h^{-4}}, which is precisely what is needed to
absorb the recovery-of-tuple-data cost in Section 6.
------------------------------------------------------------------------------
6. PREFIX COLLISIONS AND UNIQUENESS
------------------------------------------------------------------------------
The comparison tool (Prop 5.6) applies to a single pair of shifted-prime
lists with the same product. In this section we apply it to bound the
total number of colliding PAIRS of good tuples, which lets us conclude
that almost every value in V has exactly one good tuple.
6.1 The statement
DEFINITION 6.1 (Prefix collisions). Fix c > 1. For t = x and
t = x/c, with all parameters (B, m, theta, h_i, b_i, R, L) formed
from x (not from t), define
K(t) = # of ordered pairs (tau, sigma) in G(t) x G(t) such that
tau != sigma and F(tau) = F(sigma).
Here each tau = (p_0, ..., p_R, d) is a good tuple in G(t) (Definition
4.10), and the value map is
F(p_0, ..., p_R, d) = d * prod_{i=0}^{R} (p_i - 1).
PROPOSITION 6.2 (Prefix collisions). There is a quantity epsilon_H
-> 0, independent of the phase theta(x), such that for t = x and
t = x/c (both with the same x-dependent parameters):
K(t) <= (epsilon_H + o(1)) * x G_m / log x. (6.1)
The pairs counted are ordered pairs of DISTINCT tuples.
PROOF. Deferred to subsections 6.2-6.8. []
The bound (6.1) says: ordered pairs of distinct colliding good tuples are
essentially negligible on the scale x G_m / log x. Combined with the
finite-map Lemma 4.13, this will show that almost every value has at most
one good tuple.
6.2 Setup: choosing witnesses
Fix two distinct good tuples tau, sigma in G(t) with F(tau) = F(sigma).
Choose one basic witness for each (Definition 4.1):
tau from v = phi(p_0 p_1 ... p_R w), w = p_{R+1} ... p_L a,
d = phi(w),
sigma from v = phi(q_0 q_1 ... q_R w'), w' = q_{R+1} ... q_L a',
d' = phi(w').
Because both are good, both witnesses satisfy (4.4a)-(4.4d). The value
F(tau) = d * prod_{i=0}^{R}(p_i - 1) equals F(sigma) = d' * prod (q_i - 1).
If p_i = q_i for every i, then d = d' follows, and tau = sigma. So some
displayed prime differs. Let
i = min{ j : p_j != q_j },
h = h_i = m - i >= H,
J = J_i = ceil(30 log h),
S = S_i = exp(exp(b_i^{1/3})),
z = z_i = exp(exp(0.7 b_{i+J})).
For j < i, p_j = q_j (the two witnesses share a common coprime prefix).
Canceling this common prefix from v and from prod_{j= H, and b_i = alpha h rho^{-h}, so log b_i = O(h).
(b) Proposition 4.12 gives c h^{-20} <= b_{i+J} / b_i <= C h^{-18},
using 18 < 30 log(1/rho) < 20 (Ford's Lemma 3.7).
(c) Proposition 4.12 also gives S < z.
(d) With delta := sqrt(loglog S / B_y) ~ b_i^{-1/3}, we have
J delta = O(h^{-20}) (from (b) and J = ceil(30 log h)).
Also J < h/2 and i+J < L for large H (from Proposition 4.12).
Now bound the residual-log size. The portion of v^(i) coming from
residual primes above index i+J has logarithm bounded by
h * exp(0.62 b_i) + exp(2 b_L) = o(exp(0.88 b_i))
(using b_{i+1} < 0.62 b_i / (1 - 1/h_i) from between (4.2b) and (4.3b),
and h * exp(0.62 b_i) << exp(0.88 b_i) for large b_i). Since
log p_i >= x^{0} * exp(0.88 b_i) (from (4.2b)), the ratio
v^(i) / (log p_i * ...) satisfies:
p_i, q_i >= y^{0.9}, (6.3a)
0.88 b_i <= B_y <= 1.12 b_i, where B_y = log_2 v^(i), (6.3b)
u_i <= B_y + O(1), where u_i = log_2 p_i. (6.3c)
For i = 0, set y = x; the inequalities are part of the basic-witness
conditions, with u_0 = B.
6.4 Alignment of the largest prime factors
For 0 <= j <= J, write
A_j = P^+(p_{i+j} - 1), A_j' = P^+(q_{i+j} - 1).
LEMMA 6.3 (Alignment). For every 0 <= j <= J:
| log_2 A_j - log_2 A_j' | <= (2j + 1) delta B_y, (6.4)
where delta = sqrt(loglog S / B_y) ~ b_i^{-1/3}.
PROOF. Suppose A_j > A_j'. Put e = (log_2 A_j - log_2 A_j') / B_y.
Consider the interval (A_j', A_j] of "middle" primes.
On the LEFT side of (6.2): each shift p_{i+t} - 1 for t = 0, ..., j
contributes primes to (A_j', A_j], because P^+(p_{i+t} - 1) = A_t is
(roughly) in the band of size exp(b_{i+t}), and b_{i+t} decreases
with t. The alignment we are about to prove inductively implies
A_t > A_t'; in particular, A_t >= A_j >= (upper end of interval).
Each such shift contributes at least (e - delta) B_y prime factors to
the interval (after normality, condition (4.4b) on p_{i+t}).
On the RIGHT side: only the first j shifts can contribute to
(A_j', A_j] (p_{i+j} - 1 has P^+ at most A_j', and it is smaller
for larger shifts). Each such shift contributes at most
(e + delta) B_y prime factors to the interval.
All other prime factors on both sides are <= A_j' in absolute size.
The residuals D_i, D_i' are supported below z < A_0', because the
largest prime factor of D_i is at most max(p_{i+J+1}, factors of a)
<< exp(0.7 b_{i+J}) = z (by Proposition 4.12). Similarly for D_i'.
Equality of the two sides of (6.2), restricted to primes in
(A_j', A_j], therefore forces:
(j+1)(e - delta) <= j(e + delta). (6.5)
This gives e <= (2j + 1) delta. Interchanging sides handles A_j < A_j'. []
Remark. The band hypothesis (4.4b) is used to assure each p_{i+t}
is S-normal, so the "count prime factors in an interval" operation
is controlled by log_2 length / B_y up to delta error.
6.5 Preparing the comparison
Cancel any equal primes among the two lists in (6.2). The disjoint prime
bands (each p_{i+j} - 1 has P^+ near exp(b_{i+j}), and b shrinks with j)
show that equality is only possible at the same index. The index i
survives because p_i != q_i.
Let b' <= J + 1 be the number of remaining primes on each side. Their
paired shifts are primitive (p'_j - 1 and q'_j - 1) on opposite sides,
and the surviving primes are pairwise distinct.
Choose the cutoffs for Proposition 5.6:
y = value of v^(i) in its dyadic window,
Y_b' = z (smallest cutoff; note S < z by (c) above),
Y_0 = y,
log_2 U_0 = 0.8 B_y.
For each remaining index j = 1, ..., b'-1, choose a delta-grid interval
[U_j, Y_j] in normalized double-logarithmic units that contains both
log_2 P^+(p'_j - 1) and log_2 P^+(q'_j - 1). Lemma 6.3 shows that these
logarithms are within (2j+1) delta B_y of each other; so the intervals
have width O(J delta) and remain strictly separated by >= J delta (since
J delta = o(h^{-20}) is much smaller than the band gaps O(b_i h^{-20})).
Each remaining interval lies below height 0.8 by (6.3b) and
u_{i+1} <= 0.62 b_i. At index 0, the bands give factors above height 0.9
(combination of (6.3a) and (6.4)).
All ordered-cutoff hypotheses of Proposition 5.6 hold. Applying it to
(6.2) with D = D_i and D' = D_i', after cancelling the common prefix
product r >= 1:
# of ordered pairs (tau, sigma) with first-unequal-index = i and
v^(i) in the dyadic window [y/2, y]:
<= (y / (r D_i)) * (C B_y^6)^{b'} * (b'+1)^{Omega(D_i)}
* (log Y_b')^{1 + 3b' log(b'(b'+1))}
* (log y)^{-2 + sum_{j=1}^{b'-1} a_j nu_j + E_b}. (6.6)
Here nu_j, mu_j, E_b refer to the cutoffs Y_j, U_j chosen above.
6.6 The slack exponent
The exponent of log y in (6.6) is
-2 + sum_{j=1}^{b'-1} a_j nu_j + E_b.
The perturbation E_b satisfies (by Definition 5.7 and the cutoffs above):
|E_b| <= 2 sum_{j=1}^{b'-1} (nu_j - mu_j) + delta sum_{i=2}^{b'} c_i
<= (J^2 log J) * delta = O(h^2 log h * b_i^{-1/3})
= O(h^{-4}),
where we used b_i ~ h rho^{-h} >> h^{4/3} for large h, so
h^2 log h * b_i^{-1/3} << h^{-4} * (positive power).
Now use the STRICT SLACK of good tuples (condition (4.4a) of Definition
4.10 with i as above):
sum_{r=i+1}^{L} a_{r-i} u_r <= (1 - h^{-4}) u_i.
Each remaining index j = j_k (where 1 <= j_1 < j_2 < ... < j_{b'-1} <= J
are the surviving positive indices) contributes a_j in the simplex sum
above with index k in the reindexed (nu-grid) setting. Since j_k >= k
and a_k <= a_{j_k}, and since the grid widths add O(J delta):
sum_{k=1}^{b'-1} a_k nu_k
<= (1/B_y) sum_{j=1}^{J} a_j u_{i+j} + O(J^2 log J delta)
<= (1 - h^{-4}) u_i / B_y + O(B_y^{-1} + J^2 log J delta).
(6.7)
Using u_i / B_y = 1 + O(b_i^{-1/2}) (since u_i = b_i (1 + O(b_i^{-1/3}))
and B_y = b_i (1 + O(b_i^{-1/3}))):
sum_{k=1}^{b'-1} a_k nu_k <= 1 - h^{-4} + o(h^{-4}). (6.8)
Combined with (6.6) and |E_b| = O(h^{-4}), the log-y exponent becomes
-2 + sum_{k} a_k nu_k + E_b
<= -1 - h^{-4} + o(h^{-4}) <= -1 - (1/2) h^{-4}. (6.9)
Therefore the log-y power in (6.6) satisfies
(log y)^{-2 + sum a_j nu_j + E_b} <= (log y)^{-1 - (1/2) h^{-4}}. (6.10)
6.7 Costs of recovery and summation
Bound the extraneous factors in (6.6):
(a) Recovery of residual D_i (or D_i') as an ordered factorization:
at most (h+1)^{Omega(D_i)} possibilities. By the good-tuple
condition (4.4d), Omega(D_i) <= b_i / h^8. So the cost is at most
exp( 2 b_i log(h+1) / h^8 ). (6.11)
(b) The factor (log Y_b')^{1 + 3 b' log(b'(b'+1))} = exp(O(h log h
* loglog h)) because log_2 Y_b' = log_2 z = O(b_i h^{-18}).
(c) The factor (C B_y^6)^{b'} <= exp(O(h log h)).
(d) Summing 1/D_i over z-smooth D_i (from the finite Euler product):
sum_{P^+(D) <= z} 1/D << log z = O(b_i h^{-18}). (6.12)
(e) Restoring the common prefix p_0 ... p_{i-1}: sum 1/(p_j - 1) times
the prime number theorem factor for p_0 contributes
O(x G_m / log x) to each suffix pair count, by Lemma 4.5
(projected simplex mass).
Now multiply the extraneous factors:
extra := (a)*(b)*(c)*(d) = exp( O(h log h) ) * exp( 2b_i log h / h^8 )
* (b_i h^{-18}).
The log of "extra" is O(h log h) + 2 b_i log h / h^8 + O(log b_i).
Compare with the exponent (6.10): (log y)^{(1/2) h^{-4}} gives an
exponential saving in B_y ~ b_i. And
b_i / h^4 = alpha h^{-3} rho^{-h},
which grows exponentially in h, whereas
extra's exponent = O(h log h + b_i log h / h^8)
grows at most polynomially in b_i (i.e. much slower than b_i / h^4).
Specifically, since 1/h^4 >> log h / h^8, the negative term
(1/2) b_i / h^4 dominates.
Thus there is an absolute constant kappa > 0 such that for each dyadic
window and each index i:
# of suffix tuple pairs (with first unequal index i) with value
v^(i) in [y/2, y]
<= (y / log y) * exp( -kappa B_y / h^4 ). (6.13)
6.8 Summing suffixes and restoring the prefix
For a given suffix-pair count (6.13), the contribution to K(t) weighted
by 1/v^(i) is:
sum over dyadic windows [y/2, y] of (1/y) * (y/log y exp(-kappa B_y/h^4))
<= sum_{n : log(n log 2) >= 0.88 b_i} exp(-kappa log(n log 2) / (h^4 log 2)) / (n log 2)
<= int_{0.88 b_i}^{oo} exp(-kappa u / h^4) du
<< h^4 exp( -kappa b_i / h^4 ). (6.14)
(In this change of variable u = log (n log 2); the factor 1/log y exactly
compensates the density of dyadic endpoints. No factor of order exp(b_i)
is lost.)
For i = 0: the same expression (6.13) directly bounds pairs with first
unequal index zero and y = x, giving at most
(x/log x) exp(-kappa B/m^4) = o(x G_m/log x) after restoring the factor
x G_m / log x and using B / m^4 = O(1) with m^4 >> B.
Summing (6.14) over i = 0, ..., R. Since b_i = alpha h_i rho^{-h_i},
the sum is dominated by small h (i.e. i near R), with each successive
term a factor exp(-c' rho^{-1} h) << 1 smaller. So:
sum_{i=0}^{R} h^4 exp( -kappa b_i / h^4 ) <= C H^4 exp( -kappa' rho^{-H} ).
Define epsilon_H := C H^4 exp( -kappa' rho^{-H} ) -> 0 as H -> oo.
Then the total contribution to K(t) from all suffix pairs at all indices
is at most:
x G_m / log x * epsilon_H * (1 + o(1)). (6.15)
The multiplicative factor x G_m / log x is restored by the "count p_0 by
the prime number theorem" step in each suffix pair (see the discussion at
the start of 6.7(e)). The suffix-pair count (6.14) is a weighted count,
so summing over all p_0 choices multiplies by at most (x/log x) / D_prefix.
Now, cancelling the extra_prefix sum: sum_{prefix} 1/(prod_0^{i-1}(p_j-1))
<< G_m by Lemma 4.5 (projected simplex mass). So the total bound (6.15)
holds.
This proves (6.1) for t = x. For t = x/c, the same argument holds
because the witness set only DECREASES and the parameter choices
(B, m, theta, h_i, b_i, R, L) are all formed from x, not t (as
Definition 6.1 requires). []
6.9 Consequences: uniqueness
Apply Lemma 4.13 with T = T(t), G = G(t), D = D(t), W = V intersect [1, t].
The bounding quantities are:
- |E| <= (epsilon_H + o(1)) x G_m / log x (Ford's order estimate for
the coverage exception set).
- |D(t)| <= (epsilon_H + o(1)) x G_m / log x (Proposition 4.12).
- K = K(t) <= (epsilon_H + o(1)) x G_m / log x (Proposition 6.2 just proved).
Therefore (from Lemma 4.13):
| |T(t)| - V(t) | <= (epsilon_H + o(1)) x G_m / log x, (6.16)
and there is a set E*(t) with |E*(t)| <= (epsilon_H + o(1)) x G_m / log x
such that F restricts to a bijection T(t) \ F^{-1}(E*(t)) -> V(t) \ E*(t).
Restated as Proposition 4.14 (with (4.7)):
For every v in V(t) outside a set E*(t) with |E*(t)| <=
(epsilon_H + o(1)) x G_m / log x, there is a UNIQUE good tuple
(p_0, ..., p_R, d) in G(t) with F = v, and
ell(v) = p_0 p_1 ... p_R * ell(d). (6.17)
This is the key input for Section 7 below.
------------------------------------------------------------------------------
7. THE LIMITING FORMULA AND THE ARITHMETIC COEFFICIENT
------------------------------------------------------------------------------
We fix H, fix t = x or t = x/c (with all parameters formed from x), and
compute V(t). The infrastructure developed in sections 4-6 gives us:
-- Proposition 4.14: tuples in T(t) map to values in V(t) with a bijection
off a meager exceptional set, and (4.7): ell(v) = p_0 ... p_R * ell(d);
-- Proposition 4.12: bad tuples are meager;
-- Proposition 6.2: collisions are meager.
What remains is bookkeeping: sum over tuples using the prime number theorem
for the largest prime p_0, and then identify the resulting mass with an
explicit arithmetic coefficient via a volume calculation.
7.1 The tuple-reciprocal mass M_1
DEFINITION 7.1 (Tail data). Let D_H(x) be the set of DISTINCT data
(d, p_1, ..., p_R) (d, p_j positive integers, p_j primes) that arise
from some basic witness of some tuple in T(x), with p_0 omitted.
Each element of D_H(x) thus satisfies the basic-witness conditions
(4.2b)-(4.2e) on the primes p_1, ..., p_R and integer a with
phi(tail) = d.
DEFINITION 7.2 (Reciprocal mass). For any f : [1, oo) -> [0, 1],
define
M_f(x; H) = sum over (d, p_1, ..., p_R) in D_H(x) of
f(ell(d)/d) / ( d * prod_{i=1}^R (p_i - 1) ). (7.1)
For f = 1 this is the simpler M_1(x; H).
LEMMA 7.3 (Mass bound). Uniformly in x, H, and f:
0 <= M_f(x; H) <= M_1(x; H) <= C K_H G_m. (7.2)
where K_H = exp(C P rho^{-P}) = H^{o(1)}.
PROOF. Since 0 <= f <= 1, M_f <= M_1. For M_1:
sum over (d, p_1, ..., p_R) 1 / (d prod (p_i - 1))
<= sum over p_1, ..., p_R satisfying (4.2b), (4.2c), (4.3a)
of [1/prod(p_i - 1)] * sum over d compatible of 1/d.
The p_1, ..., p_R sum is at most G_m by Lemma 4.5 (projected simplex
mass, after removing the p_0 coordinate). The d sum is at most K_H by
summing 1/phi(a) over the smooth tail a (Lemma 4.7). Combining gives
(7.2). []
7.2 Counting the largest prime
PROPOSITION 7.4 (Number of values via prime sum). For each fixed c > 1,
both t = x and t = x/c satisfy:
V(t) = (t / log x) ( M_1(x; H) + E_H(t; x) G_m ), (7.3)
where
lim_{H -> oo} limsup_{x -> oo} max_{t in {x, x/c}} |E_H(t; x)| = 0.
(Both formulas use the SAME parameters B, m, theta, etc., formed from x.)
PROOF. Fix (d, p_1, ..., p_R) in D_H(x) and write
D = d * prod_{i=1}^R (p_i - 1).
By (4.3a), 1 <= D <= exp((log x)^{0.8}).
We count how many primes p_0 can accompany this tail data. A valid
p_0 must satisfy (4.2a) p_0 >= x^{0.9} and (4.2b) for p_0 = p_0, plus
satisfy the value bound d * prod_{i=0}^{R} (p_i - 1) <= t, i.e.
(p_0 - 1) * D <= t,
p_0 <= 1 + t/D.
The remaining prime factors p_{R+1}, ..., p_L and a are absorbed into
the tail totient d, and the prefix primes p_1, ..., p_R are already
bounded below x^{0.9}, so they don't repeat p_0.
Interval for p_0: [ x^{0.9}, 1 + t/D ].
Both endpoints are x^{1-o(1)} uniformly: the lower endpoint x^{0.9} is
a fixed power; the upper endpoint is t/D, where D <= x^{0.8+o(1)}, so
upper >= x^{0.2 - o(1)}. Actually we need upper >= lower for the
interval nonempty. This forces D <= t / x^{0.9} <= x^{1.1}. Which is
implies D <= x^{o(1)}, so in fact D is quite small when the tuple exists.
Anyway, prime number theorem: number of primes in [x^{0.9}, 1+t/D] is
pi(1 + t/D) - pi(x^{0.9})
= (t / (D log(1 + t/D))) (1 + o(1))
= (t / (D log x)) (1 + o(1)), (7.4)
since log(1+t/D) = log x + o(log x) uniformly.
Here the lower bound x^{0.9} costs a relative error x^{-0.1+o(1)} < 1/2.
Summing (7.4) over (d, p_1, ..., p_R) in D_H(x):
# of valid tuples (p_0, ..., p_R, d) with value <= t
= (t / log x) M_1(x; H) (1 + o(1)) + small.
The small error is from: (a) relative error x^{-0.1+o(1)}, absorbed
into o(1); (b) the discrepancy between counting "tuples with value <= t"
and counting "primes p_0 in the interval". All absorbed.
Now use Proposition 4.14 to convert "# of tuples with value <= t"
into "V(t)". The adjustment is |E*(t)| <= (epsilon_H + o(1)) x G_m/log x,
absorbed into the E_H G_m error in (7.3). And (4.3a) ensures that the
tuple's value bound d prod(p_i - 1) * (p_0 - 1) <= t is exactly
phi(p_0 ... p_R w) <= t for a basic witness (combining with phi(w) = d).
So V(t) = (t/log x) M_1(x; H) + (E_H(t;x) G_m), with E_H(t;x) -> 0
uniformly in t as H -> oo then x -> oo. []
7.3 Fixed dilation
We are now ready to prove the fixed dilation corollary.
COROLLARY 7.5. For every fixed real c > 0,
V(cx) / V(x) -> c as x -> oo. (7.5)
PROOF. Let c > 1. Apply Proposition 7.4 at t = x and t = x/c, with
the SAME parameters formed from x. We get:
V(x) = (x/log x) ( M_1(x; H) + E_x G_m ),
V(x/c) = (x/(c log x)) ( M_1(x; H) + E_{x/c} G_m ),
where E_x = E_H(x; x), E_{x/c} = E_H(x/c; x).
Then
c V(x/c) = (x/log x) ( M_1(x; H) + E_{x/c} G_m ),
V(x) - c V(x/c) = (x G_m/log x)(E_x - E_{x/c}).
By Ford's order estimate (Prop 4.1, or the analogous statement in the
introduction), there is a positive constant c_- with
V(x) log x / (x G_m) >= c_-
for every large x. Also V(x) log x / (x G_m) <= c_+.
Hence
| 1 - c V(x/c)/V(x) | = | V(x) - c V(x/c) | / V(x)
<= (E_x - E_{x/c}) / c_- -> 0 (7.6)
as x -> oo, then H -> oo. Then replace x by cx: for every fixed
c > 1 and same argument, V(cx)/V(x) -> c.
The case c = 1 is trivial. For 0 < c < 1, apply the result already
proved to 1/c > 1 and argument y = cx:
V(y)/V(y/c) -> 1/c, i.e. V(cx)/V(x) -> c. (7.7)
[]
Remark. Corollary 7.5 has NOT used the specific form of A. It only
used Proposition 7.4 (the mass M_1 with M_1(x;H) independent of t).
This is why fixed dilation holds even in the presence of the complicated
phase theta(x): the M_1 mass is phase-dependent, but it's the SAME
phase-dependent mass for x and cx.
7.4 Volume of the tail witness union
We now identify M_1(x; H) with an explicit arithmetic coefficient via
a volume calculation.
DEFINITION 7.6 (Tail witnesses for a fixed totient d at phase s).
For 0 <= s < 1, let alpha_s = lambda * exp(lambda s). A tail witness
is a tuple
eta = ( (Q_h)_{P <= h < H}, a ),
where Q_h are primes, a is a positive integer, and the following hold,
writing v_h = log_2 Q_h:
0.9 alpha_s h rho^{-h} <= v_h <= 1.1 alpha_s h rho^{-h}
for P <= h < H, (7.8a)
sum_{l=P}^{h-1} a_{h-l} v_l <= (1 + 10^{-4} exp(-h/40)) v_h
for P <= h < H, (7.8b)
P^+(a) <= Q_P, (7.8c)
log a <= exp( 2 alpha_s P rho^{-P} ). (7.8d)
The associated integer is w(eta) = a * prod_{h=P}^{H-1} Q_h, and its
totient is d(eta) = phi(w(eta)).
W_{H,s}(d) = { eta : d(eta) = d }, for d in V.
D(h, eta) = sum_{l=P}^{H-1} a_{h-l} v_l for h >= H. (7.8e)
These witnesses eta live inside the "tail" of the basic witness. The
constraint (7.8b) is the "tail consistency" from the simplex conditions.
Now fix theta(x); the witness set is W_{H, theta(x)}(d).
DEFINITION 7.7 (Prefix regions). For each eta in W_{H, theta(x)}(d),
define the region K_eta in R^R by u_0 = B and
u_i - sum_{r=i+1}^{R} a_{r-i} u_r >= D(m - i, eta),
for 0 <= i <= R. (7.9)
These are "shifted simplexes": each is S_R intersect a shifted simplex.
LEMMA 7.8 (Volume of the tail witness union). There are numbers
delta_H -> 0 such that, uniformly for f : [1, oo) -> [0, 1],
limsup_{x -> oo} | M_f(x; H) / G_m
- (1/G_m) sum over d with W_{H, theta}(d) nonempty
of f(ell(d)/d) / d
* Vol_R( union_{eta in W_{H,theta}(d)} K_eta ) |
<= delta_H. (7.10)
Moreover, for every nonempty finite subset T of W_{H, theta}(d),
Vol_R( intersection_{eta in T} K_eta )
= G_R * ( 1 - (1/B) sum_{h=H}^{m} g_{m-h} max_{eta in T} D(h, eta) )_+^R
(7.11)
where z_+ = max(z, 0).
PROOF SKETCH. (Intersection volume). The intersection constraint
is u_i - sum_{r>i} a_{r-i} u_r >= C_i := max_eta D(m-i, eta). In the
simplex variables s_i := u_i - sum_{r>i} a_{r-i} u_r, the constraint is
s_i >= C_i for every 0 <= i <= R, and Lemma 4.2 gives
sum_{i=0}^R g_i s_i = B. Translating s_i -> s_i + C_i leaves the
available slack B - sum g_i C_i. The remaining simplex has volume
G_R * (1 - sum g_i C_i / B)_+^R.
(Union ~ prime mass). Identify Q_h = p_{m-h} for P <= h < H. For
fixed eta, the prime-conditions in (4.2b)-(4.2c) for the prefix
p_1, ..., p_R (mapped to u_1, ..., u_R = log_2 p_1, ..., log_2 p_R)
place u inside eta's "perturbed simplex": bands 0.9 <= u_i/b_i <= 1.1
and (7.9) with the xi-perturbation.
Take the union over eta in W(d). This is essential: a prefix that
is compatible with several eta should be counted only once.
Replace prime sums by volumes (Lemma 4.4 + 4.5): a small error
O(K_H * sum_{h>=H} (h e^{-h/40} + h^3 rho^h)) G_m = o_H(1) G_m.
The xi -> 1 perturbation also costs o_H(1) G_m. Removing the coarse
bands via concentration (Lemma 4.3) costs o_H(1) G_m as well.
After all replacement errors, the sum of 1/(prod(p_i-1)) * [d-compatible]
over (d, p_1, ..., p_R) converges to the volume formula in (7.10).
All constants are uniform in theta(x) by (7.8a) with
lambda <= alpha_s <= lambda/rho. []
LEMMA 7.9 (Uniformly finite tail data). Fix H. The union over
0 <= s < 1 and all d of W_{H,s}(d) is a FINITE set. Its prime and
integer coordinates, and their totient values, are bounded by constants
depending only on H. Uniformly:
0 <= D(h, eta) <= C_H log(h+1) for h >= H. (7.12)
PROOF. With a_* = lambda/rho, alpha_s <= a_*. Every Q_h >= e^{e} and
<= exp exp(1.1 a_* H rho^{-H}), so finitely many possibilities per
coordinate. Similarly log a <= exp(2 a_* P rho^{-P}), so finitely many
a. Bounds: d <= w <= a * prod_{h=P}^{H-1} Q_h <= finite function of H.
For (7.12): a_j = int_j^{j+1} log t dt <= log(j+1). Then
D(h, eta) = sum_{l=P}^{H-1} a_{h-l} v_l
<= sum_{l} log(h-l+1) * 1.1 a_* l rho^{-l}
<= 1.1 a_* H rho^{-H} * sum_l log(h-l+1)
<<_H log(h+1). (7.13)
[]
7.5 The explicit arithmetic coefficient A_H
Now we assemble (7.10) into the explicit definition of A_H(f; s).
DEFINITION 7.10 (Arithmetic coefficient A_H(f; s)). For a bounded
function f : [1, oo) -> [0, 1], define A_H(f; s) by
A_H(f; s) := rho^{H(H-1)/2} (gamma / alpha_s)^H
* sum over d in V with W_{H,s}(d) nonempty
of f(ell(d)/d) / d
* sum over nonempty T subset of W_{H,s}(d)
of (-1)^{|T|-1}
* exp( -(gamma/alpha_s)
* sum_{h=H}^{oo} rho^h
max_{eta in T} D(h, eta) ). (7.14)
This is the explicit finite sum (up to absolutely convergent series
in the exponent) whose limit A(f; s) we will define below.
The prefactor rho^{H(H-1)/2} (gamma/alpha_s)^H comes from the limiting
ratio
G_{m-H} / G_m = prod_{l=0}^{H-1} ( (m-l) g_{m-l} / B )
-> (gamma/alpha_theta)^H * rho^{H(H-1)/2}, (7.15)
which captures the difference between "prefix has R = m - H coordinates"
and "prefix has m coordinates".
PROPOSITION 7.11 (Approximation). There are numbers epsilon_H -> 0
such that, for every bounded f : [1, oo) -> [0, 1],
limsup_{x -> oo} | M_f(x; H) / G_m - A_H(f; theta(x)) |
<= epsilon_H. (7.16)
The bound is independent of f and of phase.
PROOF. Apply finite inclusion-exclusion to the union in (7.10), and
then use (7.11).
For a nonempty finite subset T of witnesses, write
C_T(h) = max_{eta in T} D(h, eta),
S_T = sum_{h=H}^{oo} rho^h C_T(h),
q_{m,T} = (1/B) sum_{h=H}^{m} g_{m-h} C_T(h).
The series for S_T converges absolutely by (7.12) (D(h, eta)
= O_H(log(h+1)) while rho^h decays geometrically).
Using B = alpha m rho^{-m} and g_j = gamma rho^{-j} + O(1):
q_{m,T} = (gamma / (alpha m)) sum_{h=H}^{m} rho^h C_T(h)
+ O_H( m log(2m) / B )
= (gamma / (alpha m)) S_T + o_{x;H}(m^{-1}). (7.17)
The omitted geometric tail is O_H(rho^m log(2m)). In particular
q_{m,T} = O_H(1/m).
Hence
( 1 - q_{m,T} )_+^{m - H}
= exp( -(gamma/alpha_theta) S_T ) + o_{x;H}(1), (7.18)
using (alpha/alpha_theta) = 1 + O(log m / m) and
(m-H) q_{m,T}^2 = O_H(1/m).
The prefactor of the simplex intersection volume from Lemma 7.8:
G_{m-H} / G_m = prod_{l=0}^{H-1} ( (m-l) g_{m-l} / B )
= (gamma/alpha_theta)^H rho^{H(H-1)/2} + o(1). (7.19)
There are only boundedly many terms for fixed H. So the
inclusion-exclusion expression differs from A_H(f; theta(x))
in (7.14) by o(1) uniformly in phase.
Nonnegativity: A_H(f; s) >= 0 comes from the finite-union probability
interpretation (f >= 0, and the union probability is nonnegative). []
7.6 From A_H to A, and the main theorem
DEFINITION 7.12 (Limit coefficient). When the limit exists, put
A(f; s) := lim_{H -> oo} A_H(f; s), 0 <= s < 1. (7.20)
The main theorem asserts the existence for f = 1; the companion
theorem (Section 8) for f = f_k.
LEMMA 7.13 (Uniform convergence from a common comparison). Fix
f : [1, oo) -> [0, 1]. Suppose a real function C_f(x), independent
of H, and numbers eta_H -> 0 satisfy
limsup_{x -> oo} | C_f(x) - M_f(x; H) / G_m | <= eta_H. (7.21)
Then A_H(f; s) converges uniformly for 0 <= s < 1 to A(f; s), and
C_f(x) = A(f; theta(x)) + o(1). (7.22)
If additionally c_- <= C_f(x) <= c_+ for all large x, then
c_- <= A(f; s) <= c_+ for every s in [0, 1).
PROOF. By Proposition 7.11:
limsup_{x -> oo} | C_f(x) - A_H(f; theta(x)) | <= zeta_H
:= eta_H + epsilon_H -> 0.
Every phase s in [0, 1) occurs at arbitrarily large real x. To see
this, put psi(B) = (log B - loglog B) / lambda, continuous and strictly
increasing for B > e, tending to infinity. For any s solve
psi(B_n) = n + s, put x_n = exp(exp B_n). Then m(x_n) = n and
theta(x_n) = s exactly.
Comparing A_H and A_K at the SAME phase s along this sequence:
| A_H(f; s) - A_K(f; s) | <= zeta_H + zeta_K -> 0.
This bound is independent of s, so A_H(f; s) is uniformly Cauchy in
(H, s). In particular
sup_{0 <= s < 1} | A_H(f; s) - A(f; s) | <= zeta_H. (7.23)
Combining with the preceding limsup bound and sending H -> oo gives
(7.22). The bound clause follows by applying those bounds on the
exact-phase sequences and letting H -> oo. []
PROOF of Theorem 1 (main). Set
C_1(x) := V(x) log x / (x G_m).
Proposition 7.4 with t = x gives
limsup_{x -> oo} | C_1(x) - M_1(x; H) / G_m | <= E_H(x; x).
So (7.21) holds with eta_H = sup_x |E_H(x; x)|, which -> 0 as H -> oo
by (7.3).
Lemma 7.13 therefore gives:
- the uniform existence of A(1; s) = lim A_H(1; s),
- C_1(x) = A(1; theta(x)) + o(1).
Ford's order estimate gives c_- <= C_1(x) <= c_+; the same lemma gives
c_- <= A(1; s) <= c_+ for every s. Therefore
V(x) = (x/log x) G_m C_1(x)
= (x/log x) G_m (A(1; theta(x)) + o(1))
~ (x/log x) G_m A(1; theta(x)).
This is the first assertion of Theorem 1.
Corollary 7.5 supplies the second assertion V(cx)/V(x) -> c, in full
generality. []
Remark (independence of A from V). The definition (7.14) of A_H(f;s)
uses only:
-- d in V (a set membership, not a count);
-- ell(d), i.e. the smallest preimage of d;
-- tail witnesses eta, i.e. finite data depending only on H and s;
-- absolutely convergent series in exponents.
So A(1; s) is defined WITHOUT using V(x) in its definition. V(x)
appears only when we PROVE that C_1(x) = A(1; theta(x)) + o(1).
------------------------------------------------------------------------------
8. LEAST PREIMAGE INTERVALS: THE COMPANION THEOREM
------------------------------------------------------------------------------
For v in V, let ell(v) be the smallest integer n with phi(n) = v. For a
fixed positive integer k, we count how often ell(v) is in (kx, (k+1)x].
8.1 The weight f_k and the statement
Recall the count and the weight:
N_k(x) = #{ v in V : v <= x, kx < ell(v) <= (k+1) x }, (8.1)
f_k(r) = min{1, (k+1)/r} - min{1, k/r}, r >= 1. (8.2)
Facts about f_k: 0 <= f_k <= 1/(k+1); f_k(r) > 0 iff r > k.
Why this weight: fix v in V and put t = v/x in (0, 1] and r = ell(v)/v.
The condition
kx < ell(v) <= (k+1)x
is equivalent to
kx/v < r <= (k+1)x/v iff k < r t <= k+1 (after multiplying by t=v/x),
so v is counted iff t lies in {s in (0,1] : k < r s <= k+1}, of length
exactly f_k(r). So the weight f_k(r) exactly "sees" whether x * (uniform
test t) lands in the right band.
THEOREM 8.1 (Companion). Fix k >= 1. Then:
(a) The functions A_H(f_k; s) converge uniformly for 0 <= s < 1 to a
limit A(f_k; s).
(b) N_k(x) = (x/log x) G_m ( A(f_k; theta(x)) + o(1) ).
(c) There are exactly two possibilities:
(i) Some totient d satisfies ell(d) > k d. Then
inf_{0<=s<1} A(f_k; s) > 0, and
N_k(x) ~ (x/log x) G_m A(f_k; theta) =~_k V(x).
(ii) Every totient d satisfies ell(d) <= k d. Then
N_k(x) = 0 for every x, and A(f_k; s) = 0 identically.
(d) The positive alternative (i) holds at least for k = 1 and k = 2.
The proof splits into Lemma 8.2 (weighted prime count), the uniform
convergence step, and Lemmas 8.3, 8.4 (used in (c)).
8.2 Weighted prime count
LEMMA 8.2 (Weighted count). For each fixed k >= 1, there is an
epsilon_{H,k} -> 0 (as H -> oo) such that:
| N_k(x) - (x/log x) M_{f_k}(x; H) |
<= (epsilon_{H,k} + o(1)) x G_m / log x. (8.3)
PROOF. Fix (d, p_1, ..., p_R) in D_H(x). Put
D = d * prod_{i=1}^R (p_i - 1),
A = ell(d) * prod_{i=1}^R p_i,
r = ell(d) / d >= 1, (since ell(d) >= d)
q = prod_{i=1}^R (1 - 1/p_i) in (0, 1),
T = x / D,
U = x / A = T q / r.
The admissible primes p_0 must satisfy
p_0 >= x^{0.9}, (8.4a)
kx < p_0 * A <= (k+1)x, (8.4b)
(p_0 - 1) * D <= x, i.e. p_0 <= 1 + T. (8.4c)
(8.4b) says p_0 in (kU, (k+1)U]; (8.4c) pushes the upper bound down to
min((k+1)U, T+1). So the interval for p_0 is
p_0 in ( max(kU, x^{0.9}), min((k+1)U, T+1) ]. (8.5)
First, the "extra" lower cutoff x^{0.9}: replacing max(kU, x^{0.9}) by
kU costs a relative error x^{-0.1+o(1)} in the count of primes, which
we absorb into o(1).
Second, replacing the upper +1 by just T: replacing min((k+1)U, T+1)
by min((k+1)U, T) loses at most one candidate prime. This is
absorbed into o(1).
After both replacements, the length of the interval is
min(T, (k+1)U) - min(T, kU) = T f_k(r/q), (8.6)
using U = T q / r and the definition of f_k.
The prime number theorem applies uniformly, both endpoints being
x^{1-o(1)}: hence
#{p_0 in (8.5)}
= (T / log x) ( f_k(r/q) + o(1) ) + O(1) (the +1). (8.7)
Now perturb f_k under r -> r/q.
The map z -> f_k(1/z) is (k+1)-Lipschitz on (0, 1], with value zero at
z = 0 (check at r = k, k+1). In the variable r we get:
|f_k(r/q) - f_k(r)| <= ((k+1)/r) * (1 - q) <= (k+1) sum_{i=1}^R 1/p_i.
(8.8)
Now sum (8.7) over (d, p_1, ..., p_R) in D_H(x). The main term gives
(x/log x) * sum 1/(D) * f_k(r) = (x/log x) M_{f_k}(x; H). (8.9)
The error from (8.8) sums to:
(x/log x) sum over data of (k+1) * (sum_{i=1}^R 1/p_i) / D. (8.10)
Bound the interior factor. The band structure gives b_{i-1}/b_i >=
rho^{-1} - o(1), and p_i >= exp(exp(c b_i)). So prod_{i=1}^R 1/p_i
as a geometric series bounded by its smallest term:
sup_{(d,p_1,...,p_R)} sum_{i=1}^R 1/p_i
<= sum_{h_i >= H} exp(-exp(c b_i)) << exp(-exp(c' b_H)) = exp(-c'' rho^{-H}).
Combined with M_1 <= K_H G_m (Lemma 7.3), the contribution from (8.10)
is at most
(x/log x) * (k+1) * exp(-c'' rho^{-H}) * M_1
<= (x G_m / log x) * (k+1) * K_H * exp(-c'' rho^{-H}).
Define epsilon_{H,k} := (k+1) * K_H * exp(-c'' rho^{-H}). Since
K_H = H^{o(1)} and rho^{-H} grows super-polynomially in H, this tends
to 0 as H -> oo.
Finally, the o(1) error from the PNT, from the +1, and from the
x^{0.9} lower cutoff -- absorbed.
Rounding: N_k(x) counts VALUES v <= x satisfying kx < ell(v) <= (k+1)x.
The weighted count we just computed counts TUPLES satisfying the same
(by (4.7): for each value v outside E*(t), ell(v) = p_0 ... p_R * ell(d)).
Proposition 4.14 bounds the exceptional set E*(t) by (epsilon_H + o(1))
x G_m / log x, absorbed. []
8.3 Uniform convergence for k >= 1
Apply Lemma 7.13 with
C_{f_k}(x) = N_k(x) * log x / (x G_m).
The comparison condition (7.21) holds with eta_H = epsilon_{H,k} by (8.3).
Therefore A_H(f_k; s) converges uniformly on [0, 1) to A(f_k; s), and
C_{f_k}(x) = A(f_k; theta(x)) + o(1), (8.11)
i.e.
N_k(x) = (x G_m / log x) ( A(f_k; theta(x)) + o(1) ). (8.12)
This gives Theorem 8.1 (a) and (b).
8.4 Seed propagation and bounded ratios
LEMMA 8.3 (Ford's fiber propagation). Fix a totient d, and write
phi^{-1}(d) = {d_1, d_2, ..., d_kappa} (all preimages of d). Then
there are constants eta_d > 0 and x_d such that, for every x >= x_d,
at least eta_d V(x) distinct totients v <= x have the form
v = d phi(b), phi^{-1}(v) = { b d_1, b d_2, ..., b d_kappa }
for some positive integer b. In particular such v satisfy
ell(v)/v >= ell(d)/d.
PROOF. This is essentially Ford's Theorem 2 construction, Section 5
pp. 24-26 of his paper (equations (5.10)-(5.19)). For a fixed d, he
constructs a set B of integers such that:
-- For every to b in B, every preimage of d phi(b) is one of the
products b d_i, i = 1, ..., kappa.
-- The values d phi(b) for b in B are DISTINCT totients (paragraph
following (5.18) of Ford).
-- Excluding at most half the members of B (those that violate a
Selberg sieve condition), the survivors still number
|B|/2 >>_d V(x)
for sufficiently large x.
The full-fiber conclusion is also recorded explicitly in Ford's
Section 7.3, p. 39.
Finally, for v in the good set:
ell(v)/v = b/phi(b) * ell(d)/d >= ell(d)/d,
since b/phi(b) >= 1 for every b >= 1. []
LEMMA 8.4 (Bounded ratios). For every epsilon > 0, there are C < oo
and x_0 such that
#{ v in V : v <= x, ell(v)/v > C } <= epsilon V(x) (8.13)
for every x >= x_0.
PROOF. Choose H_0 large in Proposition 4.1 (with H = H_0), so its
exceptional set E_x has size at most (epsilon/2) V(x).
Every remaining v has a basic witness n = p_0 ... p_{R_0} w with
R_0 = m - H_0, and w < p_{R_0} by (4.3c), and w bounded in terms of H_0
only (by (4.3b)).
The prefix primes p_0, ..., p_{R_0} are distinct, and their bands give
a uniform bound
prod_{i=0}^{R_0} p_i / (p_i - 1) <= C(H_0)
(each factor p_i/(p_i-1) = 1 + 1/(p_i-1) <= 1 + 1/exp(exp(...)), and
the whole product converges to a bounded constant).
Then
ell(v)/v <= n / phi(n) = w / phi(w) * prod_{i=0}^{R_0} p_i/(p_i-1)
<= C'(H_0)
with C'(H_0) independent of x. Set C = C'(H_0). []
8.5 The dichotomy and the positive cases k = 1, 2
Case (i). Suppose some totient d_* has ell(d_*)/d_* > k. Choose
delta > 0 (depending only on d_* and k) with
ell(d_*)/d_* > k + 2 delta. (8.14)
Apply Lemma 8.3 to d_*: there is a fixed eta > 0 such that, for all
large x, at least eta V(x) values v <= x satisfy
ell(v)/v > k + 2 delta. (8.15)
Apply Lemma 8.4 with epsilon = eta/4: there is a fixed C such that at
most (eta/4) V(x) values satisfy ell(v)/v > C. Therefore at least
(3/4) eta V(x) values have
k + 2 delta < ell(v)/v <= C. (8.16)
Fix these delta, eta, C before H is allowed to grow.
For sufficiently large H, and then for sufficiently large x, Proposition
4.14 removes at most (eta/4) V(x) of these (the exceptional set E*(t)
restricted to [1, x]). So at least (eta/2) V(x) of these values are
"good" (unique tuple, all preimages basic).
For each such good v with unique tuple, ell(v)/v = (ell(d)/d) * R where
R = prod_{i=0}^R p_i/(p_i-1). Since each p_i is astronomically large
(prod_i p_i/(p_i-1) = 1 + O(1/p_0) = 1 + O(x^{-0.9})), we have
R = 1 + O(epsilon_H) + o(1), uniform in the tuple.
Increasing H and then x, we may arrange R <= (k + 2 delta)/(k + delta).
Thus at least (eta/2) V(x) values have good ratio ell(d)/d in
[k + delta, C].
Let I = [k + delta, C] and M_{1_I} be the mass with weight 1_I
(indicator of I). The analogous counting bound to (8.3), with 1_I in
place of f_k, gives
M_{1_I}(x; H) >= (1/2) eta * V(x) / ((x/log x) (1+o(1)))
>= c_1 * G_m (8.17)
for some c_1 > 0 (using V(x) >= c_- x G_m/log x).
Since inf_{r in I} f_k(r) >= min{delta/(k+delta), 1/C} > 0, we
conclude that
M_{f_k}(x; H) >= c_2 * G_m (8.18)
for some c_2 > 0 independent of H.
Now apply (8.3) with this lower bound:
N_k(x) >= (x/log x) (c_2 G_m - (epsilon_{H,k} + o(1)) G_m). (8.19)
So for large H and then large x:
C_{f_k}(x) = N_k(x) * log x / (x G_m) >= c_2/2. (8.20)
Apply Lemma 7.13 (with c_- = c_2/2) to the bounds clause:
inf_{0 <= s < 1} A(f_k; s) >= c_2/2 > 0. (8.21)
Also N_k(x) <= V(x), and the same argument gives an upper bound:
N_k(x) <= (x/log x) M_{f_k}(x; H) + o(x G_m / log x)
<= c_3 * x G_m / log x.
Combined with V(x) = (x/log x) G_m (A(1; theta) + o(1)) and A(1; s)
bounded below (Theorem 1), this gives
N_k(x) =~_k V(x). (8.22)
This proves the positive alternative.
Case (ii). Suppose ell(d) <= k d for every totient d. Then for every
v <= x:
ell(v) <= k v <= k x,
so N_k(x) = 0 for every x.
Also, in the definition (7.14) of A_H(f_k; s), each weight f_k(ell(d)/d)
is zero (since ell(d)/d <= k implies f_k = 0). So A_H(f_k; s) = 0 for
all H, s, and A(f_k; s) = 0.
This completes the dichotomy.
Positive cases k = 1, 2. We show the positive alternative holds.
For k = 1: take d_* = 2, a totient (2 = phi(3) = phi(4) = phi(6)). The
smallest preimage is ell(2) = 3. So ell(d_*)/d_* = 3/2 > 1 = k. Lemma
8.3 with d_* = 2 and k = 1 gives the positive alternative.
For k = 2: Ford's Section 7.3, p. 39, gives d_* = 2^{18} * 257 as a
totient all of whose preimages are divisible by 8. Let n be any such
preimage. Then n is even (in fact 8 | n) and has an odd prime factor
otherwise n would be a power of 2, giving phi(n) = phi(2^a) = 2^{a-1}
which is a power of 2, not d_* (which is divisible by 257). So
n has some odd prime p | n with p != 2, and
n / phi(n) = prod_{p | n} p/(p-1) >= 2 * p/(p-1) >= 2 * 3/2 = 3
(using p >= 3). Hence ell(d_*) >= min{n : phi(n) = d_*} >= 3 d_* > 2 d_*.
Actually 2 * p/(p-1) for p >= 3 is at most 2 * 3/2 = 3, but only equal
when p = 3. For p = 5, 2 * 5/4 = 2.5. For p >= 3 the bound 2 * 3/2 = 3
is an upper bound on... no wait, p/(p-1) <= 3/2 for p >= 3 (equality at
p = 3), so 2 * p/(p-1) <= 3. Yes: for p >= 3, p/(p-1) <= 3/2, so
n/phi(n) >= 2 * (bounded below by 2 since n even, plus p^{something}).
Hmm, let me redo. n is divisible by 8 (so has factor 2^3), and has an
odd prime factor p. Then
n/phi(n) = prod_{q|n} q/(q-1) >= (2/1)^3 * p/(p-1) / 2^2
That's wrong since we're multiplying factors 2/(2-1) once per distinct
prime. Let me be careful.
If n has prime factorization n = 2^a * p^b * (other), where a >= 3 (since
8 | n) and p is an odd prime, then
n/phi(n) = (2/(2-1)) * (p/(p-1)) * (other factors) -- prod over DISTINCT primes.
So n/phi(n) >= 2 * p/(p-1) whenever p >= 3, which is
= 2 * (something). If p = 3, ratio = 3. If p = 5, ratio = 2.5.
For any odd p, ratio >= 2 * (3/2)... no, >= 2 * p/(p-1) where
p/(p-1) <= 1.5 for p >= 3 (equality at p=3, and p/(p-1) approaches
1 as p grows).
So n/phi(n) >= 2 * 1 = 2 for any odd p... hmm that gives only 2, not >2.
We need strictly >2. So if n has an odd prime factor p, and 2 | n:
n/phi(n) = 2 * p/(p-1) * (other factors) ... but only "other factors"
contributes positive contributions (each factor >= 1 with strict >1 for
odd primes).
Wait no. Actually, if n has an odd prime factor p > 2, then p/(p-1) > 1
strictly. And 2/(2-1) = 2. And other factors > 1 strictly for other
odd primes.
So n/phi(n) >= 2 * p/(p-1) >= 2 * (1 + 1/(p-1)) > 2. Strictly greater
than 2. Good.
So ell(d_*) / d_* > 2 = k. Lemma 8.3 gives the positive alternative
for k = 2. []
This completes Theorem 8.1.
8.6 What is NOT proved
The question of whether (i) holds for every k >= 1 is equivalent to
whether the quantity sup_{d in V} ell(d)/d is unbounded. That is an open
problem. The companion theorem does not resolve it.
------------------------------------------------------------------------------
9. WHAT IS NOT PROVED, WHAT IS OPEN, AND REFERENCES
------------------------------------------------------------------------------
9.1 Concepts the theorem uses but does not construct
This document proves an explicit asymptotic formula for V(x). Some
questions remain.
(a) The value of A(1; s) at any particular s. We prove existence and
boundedness, but we do not numerically evaluate A(1; s) at any specific
s. A numerical evaluation at s = 0 or s = 1/2 would require computing
sums over the (typically very many) tail witnesses for each fixed H,
and then letting H grow. We have given a formula (7.14) but no
computational method.
(b) Whether A(1; s) is continuous in s. The main theorem establishes
uniform convergence in s of A_H(1; s), hence that A(1; s) exists for
each s; but the limit does not automatically inherit any regularity.
Whether A(1; *) is continuous is not addressed.
(c) Whether A(1; s) is ever equal to A(1; s') for s != s'. If it were
constant in s, the fixed-scaling corollary V(cx)/V(x) -> c would
still hold, but the interpretation would be simplified.
9.2 Principal open problems
The following problems from the original Erdos-Hall-Erdos-Maier-Pomerance
tradition are NOT resolved here:
(a) Unboundedness of ell(d)/d over totients d. This is equivalent to
the positive alternative in Theorem 8.1 holding for every k >= 1.
It is an open problem in the study of iterated totient properties.
(b) Precise value of A(1; theta(x)) as a phase function. Even the
behavior of A(1; s) near s = 0 and s = 1 (the "phase boundaries"
where m jumps by 1) is not determined.
(c) Sharper error terms in V(x) = (x/log x) G_m A(1; theta) + error.
The current proof gives error o(x G_m / log x) without an explicit
rate (beyond "the error goes to 0 as x -> oo").
(d) Analogous questions for iterated preimages: elld(n) (d-fold iterated
ell) and their extremal behavior.
9.3 References
The following numbered references are cited in the text:
[Erdos1945] P. Erdos, Some remarks on Euler's phi function and some
related problems, Bull. Amer. Math. Soc. 51 (1945), 540-544.
[Erdos1958] P. Erdos, Some remarks on Euler's phi function,
Acta Arith. 4 (1958), 10-19.
[Erdos1935] P. Erdos, On the normal number of prime factors of p-1
and some related problems concerning Euler's phi-function,
Quart. J. Math. 6 (1935), 205-213.
[Erdos1979] P. Erdos, Some unconventional problems in number theory,
Asterisque 61 (1979), 73-82.
[Erdos1995] P. Erdos, Some of my favourite problems in number theory,
combinatorics, and geometry, Resenhas 2 (1995), 165-186.
[ErdosHall1976] P. Erdos, R. R. Hall, Distinct values of Euler's
phi-function, Mathematika 23 (1976), 1-3.
[FordTotients2013] K. Ford, The distribution of totients, Ramanujan J.
2 (1998), 67-151; revised arXiv version arXiv:1104.3264v2 (14 July
2013) is the version cited.
[FordSieve2023] K. Ford, Sieve methods lecture notes, UIUC, Spring 2023
https://ford126.web.illinois.edu/sieve2023.pdf.
[FordLau2000] K. Ford, K.-W. Lau, Asymptotics of a recurrent sequence:
10682, Amer. Math. Monthly 107 (2000), 374-375.
[MaierPomerance1988] H. Maier, C. Pomerance, On the number of distinct
values of Euler's phi-function, Acta Arith. 49 (1988), 263-275.
[Pillai1929] S. S. Pillai, On some functions connected with phi(n),
Bull. Amer. Math. Soc. 35 (1929), 832-836.
[Pomerance1986] C. Pomerance, On the distribution of the values of
Euler's function, Acta Arith. 47 (1986), 63-70.
[PPT2013] P. Pollack, C. Pomerance, E. Trevino, Sets of monotonicity
for Euler's totient function, Ramanujan J. 30 (2013), 379-398.
[OpenAITotientFibers2026] OpenAI, Weighted dilation graphs, smooth
shifted primes and totient fibers, OpenAI Math Release preprint,
September 24 2026.
------------------------------------------------------------------------------
10. A CRIB SHEET, FOR THE IMPATIENT READER
------------------------------------------------------------------------------
If you only want to remember the ESSENCE:
(1) The number of totients up to x is (x/log x) G_m A(1; theta), where
G_m is an explicit scale (defined from rho and g_j) that grows like
exp(c (logloglog x)^2), and A is a specific arithmetic limit that
captures the exact constant.
(2) The proof breaks into:
-- Ford's theorem: a typical totient is p_0...p_L a with p_i in
prescribed double-log bands and a smooth bounded tail a;
-- A deep comparison: two such representations almost never give
the same totient;
-- A finite arithmetic limit: sum the resulting tuple mass by
Riemann-primes and take a limit as H grows.
(3) Once A is identified, the ratio V(cx)/V(x) -> c follows immediately:
V(x) and V(cx) share the same M_1 with the same phase parameters at
the base x, so their ratio tends to c.
(4) The companion theorem weights the count by the "least preimage
interval" condition. It gives two alternatives (positive or zero)
depending on whether some totient supports a seed ratio > k. The
positive alternative holds for k = 1, 2 and is open for larger k.
If you want to remember the FORMULAS:
rho unique root of sum_{j>=1} a_j rho^j = 1 (0.54..0.545)
a_j (j+1) log(j+1) - j log(j) - 1
lambda log(1/rho) (0.60..0.62)
g_0 = 1, g_j = sum_{d=1}^j a_d g_{j-d}, j >= 1
gamma (sum_{j>=1} j a_j rho^j)^{-1}
B(x) loglog(x)
m(x) floor( (log B - loglog B) / lambda )
theta(x) (log B - loglog B) / lambda - m(x)
G_j(x) B(x)^j / ( j! prod_{i=1}^j g_i ), j = 0..m
A(f; s) lim_{H -> oo} A_H(f; s), defined in (7.14)
V(x) ~ (x/log x) G_m(x) A(1; theta(x)).
------------------------------------------------------------------------------
11. END
------------------------------------------------------------------------------
The theorem V(x) ~ (x/log x) G_m A(1; theta), together with the fixed
dilation result V(cx)/V(x) -> c, is now proven in full. The companion
weighted formula for N_k(x) is proven as well.
What is new here, compared to Ford's paper, is:
- the identification of the bounded K(x) in (x/log x) K(x) with an
explicit limit A(1; theta);
- the proof of the fixed-scale limit V(cx)/V(x) -> c;
- the weighted formula for N_k(x).
What is not resolved:
- the specific numerical value of A(1; s) at any given s;
- the continuity of s -> A(1; s);
- the openness of ell(d)/d (unboundedness), which would settle the
companion theorem for every k.
END OF DOCUMENT.