===============================================================================
SIMULTANEOUS PRIMITIVE ROOTS: A CONDITIONAL LOWER BOUND FOR PRIME BASES
===============================================================================
Version 2. Rewritten to be read in order, without any prior exposure to
algebraic number theory. Everything is in plain text with integers and
explicit constants.
Standard of completeness: every step is either proved here, or is one of
four clearly labelled inputs quoted in Part 3. There are no unstated
lemmas, no "it is easy to see", and no appeals to the companion paper
except for those four inputs.
CONTENTS
Part 0 How to read this note
Part 1 Orders, primitive roots, and the one trick
Part 2 The theorem
Part 3 The four inputs
Part 4 The proof in one page
Part 5 The reservoir: which primes we hunt
Part 6 A non-square base has odd index
Part 7 The large prime factor Q cannot divide the index
Part 8 The Kummer field, and the death of the small factors
Part 9 Sieving the reservoir
Part 10 Choosing the constants, and the end of the proof
Part 11 Checks on a computer
Part 12 Glossary and index of notation
Notation used from here on, once and for all:
p, q, ell, Q, j primes (lowercase q for the bases we prescribe)
M, r, d, m, n positive integers
x a large real number; the primes we want lie in (x,2x)
L log x (natural log throughout)
log natural logarithm
"a = b (mod c)" c divides a-b
"d | n" d divides n
"n <= X << Y" n is at most an absolute constant times Y
"n = O(Y)" same thing
"n ~ Y" n/Y tends to 1
"n = o(Y)" n/Y tends to 0
F_p the integers mod p; F_p^* = {1,2,...,p-1} under
multiplication mod p
#S the number of elements of the finite set S
phi(M) Euler's totient: the number of units mod M
===============================================================================
PART 0. HOW TO READ THIS NOTE
===============================================================================
The question is short. Fix a prime q, for concreteness q = 2. For which
primes p do the powers of 2 run through *every* nonzero residue mod p?
p powers of 2 mod p (until 1) order index
3 2, 1 2 1
5 2, 4, 3, 1 4 1
7 2, 4, 1 3 2
11 2, 4, 8, 5, 10, 9, 7, 6, 3, 1 10 1
13 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1 12 1
The primes that pass -- 3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, ... --
are the subject of Artin's primitive root conjecture (1927): they should
have density about 0.3739... among all primes. Nobody can prove even that
this set is infinite. What we prove here is a weaker statement with a
hypothesis: a positive proportion of x/(log x)^2 primes below x have a
whole prescribed finite set of primes as simultaneous primitive roots.
Read in this order:
Parts 1-2 set up the question and state the theorem. About 10 minutes.
Part 3 the four inputs. Skim on first read; each has a two-line
plain-English gloss that carries the meaning.
Part 4 the skeleton of the proof in one page. This is the map.
Parts 5-10 the proof itself, in the same order as Part 4.
Part 11 computer checks: each example in this note can be verified
with a five-line program.
Part 12 glossary, and a table of where each symbol is defined.
The two audiences this is written for: a high-school reader who knows
what "mod p" means and wants to see real mathematics end to end; and a
reader who wants to check the argument without wading through the
LaTeX original. Nobody needs to know what an L-function is beyond the
one paragraph definition in Part 3.
Two habits that make the rest easy.
(i) Always think in terms of *index*, not order. The index of q mod p is
(p-1)/ord_p(q), an integer dividing p-1. The index is 1 exactly when
q is a primitive root, and every failure has a prime divisor.
(ii) Always think in terms of *constructions of p*. We do not study a
random prime and ask about its order; we build p out of pieces
(Part 5) so that every possible way q could fail is visibly rare.
===============================================================================
PART 1. ORDERS, PRIMITIVE ROOTS, AND THE ONE TRICK
===============================================================================
1.1 The stage. Fix a prime p. The set F_p^* = {1,2,...,p-1} is a group
under multiplication mod p, with p-1 elements. Two standard facts, used
constantly:
(G1) F_p^* is cyclic: there is a g with
F_p^* = {1, g, g^2, ..., g^{p-1}}.
(G2) Lagrange: the number of elements of a subgroup divides the number
of elements of the group. Consequence: if a^d = 1 (mod p) for some
d >= 1, then ord_p(a) divides d.
1.2 Order and index. For a prime q not divisible by p,
ord_p(q) = the least d >= 1 with q^d = 1 (mod p).
By (G2) and Fermat's little theorem q^{p-1} = 1, the order divides p-1.
Its complement
iota_p(q) = (p-1) / ord_p(q)
is called the index of q mod p. Then q is a primitive root mod p if and
only if ord_p(q) = p-1, if and only if iota_p(q) = 1. The index is the
measure of failure: it is an integer, it divides p-1, and every index
greater than 1 has a prime divisor. The entire proof consists of making
each possible prime divisor of the index impossible or rare.
1.3 A table for p = 13, listing powers until they return to 1.
q powers ord iota
2 2 4 8 3 6 12 11 9 5 10 7 1 12 1
6 6 10 8 9 2 12 7 3 5 4 11 1 12 1
3 3 9 1 3 4
4 4 3 12 9 10 1 6 2
5 5 12 8 1 4 3
1 1 1 12
Check a couple by hand. 2^6 = 64 = 52 + 12 = 12 = -1 (mod 13), so 2 is
not a square mod 13; yet 2 is a primitive root. 3^3 = 27 = 1 (mod 13), so
ord_13(3) = 3 and 3 fails badly. And 6 = 2*3 is a primitive root while
3 is not: nothing here is multiplicative, because a generator times a
non-generator can be a generator.
1.4 Squares, non-squares, Euler's criterion. For p odd and p not dividing
q, exactly half of F_p^* is a square. Euler's criterion:
q^{(p-1)/2} = +1 (mod p) if q is a square mod p,
q^{(p-1)/2} = -1 (mod p) if q is not a square mod p.
(Reason: the squares form a subgroup of index 2, so q^{(p-1)/2} = 1
exactly when q lies in it.) Write (q|p) for the Legendre symbol: +1 for a
square, -1 for a non-square, 0 when p | q. It is multiplicative in q:
(q_1 q_2|p) = (q_1|p)(q_2|p).
1.5 THE TRICK. If q is a non-square mod p, then iota_p(q) is ODD.
Proof. Let d = ord_p(q) and suppose iota = (p-1)/d is even. Then d
divides (p-1)/2, so q^{(p-1)/2} = 1 (mod p), contradicting Euler's
criterion, which says the value is -1. QED
Two lines, and it is the hinge of the whole paper. Read it twice: it
turns a condition we can create with congruences on p (q is a non-square)
into a condition strong enough to enumerate (the index is odd, so it is
a product of odd primes only, and it divides p-1, whose factorization we
will know exactly).
Plan it suggests, and the plan we follow:
(a) build p so that q is a non-square mod p;
(b) build p so that p-1 has very few odd prime factors (Part 5), and
kill each of them one at a time (Parts 7 and 8).
1.6 Quadratic reciprocity, and the supplement for 2. For distinct odd
primes p and q,
(q|p)(p|q) = (-1)^{((p-1)/2)((q-1)/2)},
and
(2|p) = +1 if p = 1 or 7 (mod 8), -1 if p = 3 or 5 (mod 8).
So if p = 1 (mod 4) the exponent ((p-1)/2)((q-1)/2) is even, the sign is
+1, and (q|p) = (p|q): for such p the symbol depends only on p mod q.
Consequently, if p = a (mod q) with a a non-square mod q, then q is a
non-square mod p. One congruence on p handles one base; the Chinese
remainder theorem handles all of them at once. This is exactly how
Part 6 will arrange condition (a) for a whole finite set of bases.
===============================================================================
PART 2. THE THEOREM, AND THE TWO INGREDIENTS IT NEEDS
===============================================================================
Fix a finite set of distinct prime bases q_1, ..., q_k once and for all.
Everything below depends on them only through finitely many constants.
THEOREM 1. Assume Inputs A, B, C, D (Part 3). There are constants
c = c(q_1,...,q_k) > 0 and x_0 = x_0(q_1,...,q_k) such that for every real
x >= x_0, at least
c x / (log x)^2
primes p with x < p < 2x satisfy
p does not divide q_1 q_2 ... q_k, and
ord_p(q_i) = p-1 for every i = 1, ..., k.
In words: a prescribed finite set of primes is simultaneously a set of
primitive roots for at least a fixed multiple of x/(log x)^2 primes below
x, forever.
How large is that? The number of primes in (x,2x) is about x/(2 log x),
so the theorem delivers a fraction E of them with E about x/L^2 divided by
x/L, that is E of order 1/log x. The claim says nothing about which
proportion asymptotically; it says the count never drops below a fixed
multiple of x/(log x)^2. Two powers of the logarithm are lost, one to the
sieve (Part 9) and one to the marking device (Part 5).
The two ingredients are the following propositions. Their proofs are
Parts 5-9; here we only state them and note what they say in words.
PROPOSITION 2 (a reservoir of primes in a fixed progression). Assume
Inputs B, C, D. Let M >= 1 be odd and squarefree, and let a be a residue
class mod M with gcd(a(a-1), M) = 1. Then there are constants
c_{M,a} > 0 and x_{M,a} > 1 such that for every real x >= x_{M,a}, at
least c_{M,a} x / L^2 primes p satisfy
x < p < 2x, p = a (mod M), p = 4 r Q + 1,
where r is a positive integer, Q > x^{0.9} is prime, and every prime
divisor ell of r satisfies
exp(L^{0.1}) < ell < exp(L^{0.3}).
The case M = 1 is allowed and means the trivial progression.
In words: we can manufacture primes that are 1 more than four times a
number with exactly one enormous prime factor Q, all remaining prime
factors r sitting in a narrow window far from both 1 and Q, and with p
landing in any prescribed residue class that avoids 0 and 1. The window
is what makes Parts 7 and 8 work: the factors of r are large enough that
the analytic estimate of Part 8 applies to them, and small enough that
there are not many of them.
PROPOSITION 3 (a uniform bound for order obstructions). Assume Input A.
Fix a positive prime q. Then for all sufficiently large real x, uniformly
over primes ell with exp(L^{0.1}) < ell < exp(L^{0.3}), the number of
primes p with
x < p < 2x, p does not divide q ell, p = 1 (mod ell),
q^{(p-1)/ell} = 1 (mod p)
is at most
C_q ( x / (ell (ell-1) L) + x^{1-eta} ), eta = 10^{-6}.
The constant C_q depends only on q; the threshold in x depends on q but
not on ell.
In words: for a fixed base q, the primes where ell divides the index of q
are genuinely rare -- density about 1/ell^2 instead of 1/ell. If ell
divides iota_p(q) then q^{(p-1)/ell} = 1, so Proposition 3 counts exactly
the primes we must exclude. The condition p = 1 (mod ell) has density
1/ell, and the extra condition cuts it down by another factor 1/ell; that
saving is what makes the sum over all admissible ell converge (Part 6).
Three remarks on Theorem 1, to place it.
(i) One base is already hard. Take k = 1 and q_1 = 2. Then Theorem 1 says
that, conditionally on Inputs A-D, the primes for which 2 is a
primitive root number at least c x/L^2 up to x. Unconditionally, the
infinitude of that set is still unknown. What is known unconditionally
is only collective: Gupta and Murty (1984) and Heath-Brown (1986)
proved that for certain small sets of bases at least one member works
for infinitely many p.
(ii) The conditional history. Hooley (1967) proved the full Artin
asymptotic for one base under the generalized Riemann hypothesis;
Matthews (1976) treated simultaneous sets the same way; Anwar and
Pappalardi (2017) obtained an infinitude criterion from Schinzel's
Hypothesis H. Theorem 1 is of this family: strong hypothesis, strong
conclusion, no effective constants.
(iii) Input A is a consequence of the generalized Riemann hypothesis,
which forbids zeros with real part above 1/2 for all these
L-functions; Input A only forbids zeros with real part above
1 - 10^{-6}. Inputs C and D are combinatorial sieve facts. Input B is
a bilinear (Type II) estimate of Bombieri-Vinogradov flavour. Where
the four come from is the business of the companion paper; here they
are hypotheses, quoted verbatim in Part 3.
===============================================================================
PART 3. THE FOUR INPUTS
===============================================================================
Three of the four inputs are stated in terms of one fixed package of data,
used again in Parts 5 and 9. Nothing in this section is proved; it is the
bookkeeping that later parts refer to.
3.0 The marked data. Throughout, x is real and tends to infinity, L = log x,
and
W = exp(L^{0.24}), V(y) = prod_{p <= y} (1 - 1/p),
the product over primes p. So V(y) ~ e^{-gamma_E}/log y by Mertens'
theorem, where gamma_E = 0.577... is Euler's constant.
Fix an integer K >= 1 and fixed exponents
0.1 < a_1 < a_2 < ... < a_K < 0.2.
The i-th group of primes and its mass are
P_i = {p prime : exp(L^{a_i}) <= p <= exp(2 L^{a_i})},
V_i = sum_{p in P_i} 1/p = log 2 + o(1).
The last equality is Mertens' theorem again, since the interval
[L^{a_i}, 2L^{a_i}] in the exponent has logarithmic length log 2. For
large x the groups are disjoint (they live at different heights), and
every group prime lies in the window
exp(L^{0.1}) < p < exp(L^{0.3}).
Write G for the set of positive integers all of whose prime factors are
group primes; call these the group integers; 1 is included. For a
positive integer h put
h_P = prod_{p in P_1 u ... u P_K} p^{v_p(h)},
omega_i(h) = #{p in P_i : p | h},
where v_p(h) is the exponent of p in h. So h_P collects the full powers
of the group primes inside h, and h/h_P removes them completely -- all
exponents, not just the first power.
The mark of h, with mark parameter 1/2, is
W(h) = 2^{K - sum_i omega_i(h)} * prod_{i=1}^K omega_i(h)/V_i,
h >= 1,
with the convention that it is zero as soon as some omega_i(h) = 0. Two
facts about marks, used repeatedly.
(M1) 0 <= W(h) <= B_K = (2/log 2)^K for all h.
Proof: the bound j 2^{1-j} <= 1 for integers j >= 1 gives
W(h) = prod_i (2^{1-omega_i} omega_i / V_i) <= prod_i 1/V_i, and
V_i = log 2 + o(1), so prod_i 1/V_i <= B_K for large x. QED
(M2) A function F on the positive integers satisfies
F(p h) = F(h) for every group prime p and every h >= 1 if and only
if F(h) depends only on h/h_P.
Proof: multiplying by p changes nothing exactly when p is in a
group; and (M2) says F may not see the group part at all, including
how many times each group prime occurs. QED
Marks are a weighting device: they let us count integers that pick up at
least one prime from every group, with weights that are bounded (M1) and
multiplicative-ish. The reason for wanting one prime from each of K
disjoint groups will appear in Part 9 -- it is a way of making a
bilinear (Type II) estimate apply to a sieve problem.
Finally, for w > gamma > 0, define the rough-number density
D_gamma(w) = 1/w
+ sum_{j >= 2} (1/j!) * INT_{t_i >= gamma, sum t_i <= w - gamma}
( 1/(w - sum_{i<j} t_i) ) * prod_{i=1}^{j-1} dt_i/t_i,
the integral over j-1 variables t_1,...,t_{j-1}. The term with index j
requires w >= j gamma, so the sum is finite for fixed w. D_gamma is what
one gets by writing down the measure of integers whose least prime factor
is prescribed, in the standard Buchstab decomposition; its two properties
we need are recorded as Input D and used in Part 9. It is nonnegative and
jointly continuous on the region w > gamma > 0, which we check now because
Part 9 needs it.
Lemma 3.1. D_gamma(w) is nonnegative and continuous on w > gamma > 0.
Proof. Nonnegativity is clear. For continuity fix a compact set inside
w > gamma > 0 and a j >= 2. Put s = w - j gamma and substitute
t_i = gamma + s y_i for i = 1,...,j-1. When s >= 0 the j-th summand
becomes
s^{j-1}/j! * INT_{y_i >= 0, sum y_i <= 1}
prod dy_i / ( prod_{i<j} (gamma + s y_i) * (gamma + s(1 - sum y_i)) )
and we declare it zero when s < 0. On the compact set the denominators
stay bounded away from zero (all factors are at least gamma times
something), so the expression is continuous in s, hence in w, including at
s = 0 where it tends to zero. Each summand is continuous and only finitely
many are nonzero on a bounded w-set, so the sum is continuous. QED
Now the four inputs. Each is quoted in the exact form used, followed by a
plain-English gloss. Inputs A and B are analytic (L-functions and
bilinear sums); Inputs C and D are combinatorial sieve facts.
INPUT A (uniform Hecke zero-free assertion).
Let F be a cyclotomic number field containing all 12-th roots of unity.
Let chi be a finite-order Hecke character of F. Then the meromorphic
continuation of the L-function L_F(s, chi) has no zero with
Re s > 1 - 10^{-6}. The pole at s = 1 is permitted when chi is principal.
Gloss. A number field is a finite extension of the rationals; F = Q(mu_m)
is the field generated by the m-th roots of unity. Its ring of integers
has prime ideals P, each with a norm N(P), and an L-function is a product
L_F(s, chi) = prod_P (1 - chi(P) N(P)^{-s})^{-1},
convergent for Re s > 1, with a meromorphic continuation. A finite-order
Hecke character is the number-field analogue of a Dirichlet character; it
is a well-defined multiplicative function on the prime ideals, of finite
order. You only need one thing from this input: a fixed-width zero-free
strip, with a width that does not depend on F or on chi.
Why the uniformity is the content. For a single F, classical theory gives
a zero-free region of the shape Re s > 1 - c/log(disc F), whose width
shrinks as the discriminant grows. Input A insists on the same width
10^{-6} for all such F at once, including the fields Q(mu_{12 ell}) used
in Part 8, where ell runs up to exp(L^{0.3}) and the discriminants are
astronomical. The generalized Riemann hypothesis (zeros only at
Re s = 1/2) implies Input A immediately; the converse is false.
INPUT B (marked Type II estimate). Fix the marked data of 3.0. The input
has two parts.
(i) Coefficient criterion. Fix delta, C, D_* > 0. Let H_m, H_n be real
with H_m, H_n >= x^delta, and put X = H_m H_n, assumed to be of size x:
the ratio X/x lies between two fixed positive constants. Let F be a
function on the positive integers with |F(h)| <= 1 for all h and
F(p h) = F(h) for every group prime p and every h >= 1. Let (alpha_m),
(beta_n) be complex sequences supported on W-rough integers in
[H_m, 2H_m] and [H_n, 2H_n] respectively, where alpha_m may be nonzero
only for m in an arbitrary interval I inside [H_m, 2H_m], and with
|alpha_m|, |beta_n| <= L^C. Assume that for every fixed A_0, B, A > 0,
every Dirichlet character chi modulo k with k <= L^{A_0}, and every real
|t| <= 2 X L^B,
| (1/H_m) sum_m alpha_m chi(m) m^{it} | <<_A L^{-A},
uniformly in the interval I, in the character chi, and in the frequency t.
(The implied constant and the threshold in this estimate may depend on
A_0, B, A, on the marked data, and on all further fixed parameters that
enter the definition of the coefficients.) Then
| sum_{m,n} alpha_m beta_n F(m n - 1) W(m n - 1) | << X L^{-D_*}
provided K is large enough in terms of the fixed data, and independently of
the particular exponents a_i. The implied constant and the threshold in
this last inequality may depend on all fixed data, including the common
constants and thresholds in the estimate just displayed and the a_i. With
those data fixed, the bound is uniform over the permitted F, dyadic
intervals, intervals I, and coefficients.
(ii) Rough coefficient cancellation. Keep the marked data and the
hypotheses on F, beta, H_m, H_n, but do not assume any alpha has been
chosen. Fix 0 < gamma < w_- < w_+ < 1 and assume
[ log H_m / L, log(2 H_m)/L ] is contained in [w_-, w_+].
Then for every interval I inside [H_m, 2H_m] and every real |v| <= L^C, the
coefficient
alpha_m^(0) = m^{iv} * ( 1{P^-(m) > x^gamma}
- (D_gamma(log m / L) / (L V(W))) * 1{P^-(m) > W} ),
m in I,
extended by zero outside I, satisfies the displayed estimate of (i) with
alpha^(0) in place of alpha, for every fixed A_0, B, A > 0. The assertion
is uniform in the permitted dyadic intervals, intervals I, characters,
frequencies t, and real v. Its constant and threshold may depend on the
fixed parameters, including gamma, w_-, w_+; in particular gamma and
w_- - gamma are fixed before x grows.
Gloss, part (i). This is a "Type II" (bilinear) estimate: a statement that
a double sum over m and n, weighted by a factor F(mn-1) that sees only the
non-group part of mn-1, is small. The hypothesis is purely about
cancellation of the single sequence alpha_m against Dirichlet characters
twisted by m^{it}: alpha_m is orthogonal to every character and every
frequency in a wide range. That is the kind of input that
Bombieri-Vinogradov-type theorems supply for the difference between a
prime count in a progression and its main term.
Gloss, part (ii). The two indicators in alpha^(0) are "m has no prime
factor below x^gamma" and "m has no prime factor below W". Their
difference is a Buchstab-type comparison: the first is the exact test we
want, the second is its expected density times a smoother test at the
smaller threshold W, and Input B(ii) says the difference has square-root
cancellation against characters. This is what lets Part 9 replace an
awkward exact indicator by a tractable one, at the cost of one factor 1/L
(the density factor 1/(L V(W)) has size about L^{0.24}/L).
Note what is NOT assumed: nothing about F beyond boundedness and group
invariance (M2); nothing about beta beyond support and size. That
flexibility is why the estimate survives being multiplied by a Dirichlet
character in Part 9 (Lemma 9.2) and why it applies in as many as O(L)
dyadic boxes at once.
INPUT C (block sieve). Let z > 1. Let A be a finite set with nonnegative
weights lambda_nu for nu in A, and let D be a set of designated primes, all
at most z. For each p in D let A_p be the subset of A on which the bad
condition at p holds. For a squarefree product ell of primes in D put
A_ell = the intersection of the sets A_p over primes p dividing ell, and
A_1 = A. Suppose that, for ell = 1 as well,
sum_{nu in A_ell} lambda_nu = Y g(ell) + R(ell), Y >= 0,
where g is multiplicative on these squarefree products with g(1) = 1, and
g(p) is extended by zero at primes outside D. Suppose that for fixed
constants eta_0 > 0 and C_0 < infinity,
0 <= g(p) <= 1 - eta_0, sum_{u < p <= u^2} g(p) <= C_0 (u > 1),
sums over primes p in D. Let
S = sum of lambda_nu over nu in A but in no A_p
be the weight that avoids every bad condition. Then for every sufficiently
large even integer H,
S = Y prod_{p <= z} (1 - g(p)) * (1 + O(e^{-H}))
+ O( sum_{ell <= z^{4H+2}, ell squarefree,
p | ell => p in D} |R(ell)| ),
where both remainder sums run over squarefree products of designated
primes, ell = 1 included, and the thresholds and implied constants depend
only on eta_0 and C_0. In particular the constants are uniform when H
grows, the main term factorizes over primes, and the remainder has no
extra coefficient or multiplicity factor. For H = 2 the same method gives
the upper bound
S << Y prod_{p <= z} (1 - g(p))
+ sum_{ell <= z^{10}, ell squarefree, p | ell => p in D} |R(ell)|.
Gloss. A sieve is a machine for counting what survives when you forbid
divisibility by small primes. You feed it the sizes of the sets A_ell of
survivors against all products ell of forbidden primes; the machine
returns the count S. The main term is always the product of the local
densities 1 - g(p) over the forbidden primes, because divisibility by
distinct small primes behaves as if independent. The input has exactly
two hypotheses: a uniform gap 0 <= g(p) <= 1 - eta_0 (so no prime is
forbidden almost completely, which would make the product worthless), and
a bounded total mass C_0 on dyadic ranges of primes (so the product cannot
be destroyed by a burst of density somewhere). The word "block" refers to
the shape of the remainder: the sum of |R(ell)| is over ell up to a fixed
power of z, with no multiplicity factor. That shape is what makes Part 9's
remainder bookkeeping a clean comparison with Lemma 9.3.
INPUT D (rough-number density). For the density D_gamma(w) of 3.0 there
are absolute constants b_d, c_d, C_d > 0 such that, for every fixed
0 < b < min(b_d, 1/2),
INT_b^{1/2} D_t(1 - t) dt/t = D_b(1) - 1,
D_b(1) <= (e^{-gamma_E}/b) * (1 + C_d e^{-c_d/b}).
The value of the integrand at t = 1/2 is immaterial.
Gloss. The first line is a bookkeeping identity from the Buchstab
decomposition: it says that the density at parameter b equals 1 (the
contribution of prime inputs) plus the accumulated contribution of
composites, integrated over the bins for their least prime factor. The
factor dt/t is exactly the measure of "the least prime factor lies in the
exponent bin [t, t+dt]". The second line says the density is not much
larger than e^{-gamma_E}/b, the sieve-dimension-1 prediction, with a
relative error that is exponentially small in 1/b. That exponential
smallness is what Part 10 spends to make the final constant positive.
Where each input is used:
Input A Proposition 3 only (the Kummer field count, Part 8)
Input B Proposition 2, via Lemmas 9.2 and 9.4 (Part 9)
Input C Proposition 2, via the two sieves of Part 9
Input D Proposition 2, in the least-prime-factor removal of
Part 9 and in the constant selection of Part 10
Theorem 1 uses Input A through Proposition 3 and Inputs B, C, D through
Proposition 2; nothing else is assumed anywhere.
===============================================================================
PART 4. THE PROOF IN ONE PAGE
===============================================================================
This part proves Theorem 1 from Propositions 2 and 3, nothing else. If you
read only one part of this note, read this one: it is the whole idea, and
the remaining parts are the two ingredients' proofs.
The shape of the argument. To prove ord_p(q_i) = p-1 for every i, it is
enough, by Lemma 1.5, to produce p such that
(a) every q_i is a non-square mod p (this makes the index odd), and
(b) no prime divides the index of any q_i.
Step (a) is one congruence on p. Step (b) needs to know the prime
factorization of p-1: if p - 1 = 4 r Q with Q a huge prime and all prime
factors of r in a narrow window, then the odd primes dividing p-1 are the
factors of r together with Q, and there are few of them. That is exactly
the shape Proposition 2 delivers. So:
Proposition 2 gives lots of p of shape 4 r Q + 1 in a chosen
progression; Step (a) is then automatic; Step (b) splits into two
cases, Q or a factor of r, and each is rare by a different
argument (Q: elementary, Part 7; factors of r: Proposition 3).
Now the details.
Proof of Theorem 1. Let q_1, ..., q_k be the distinct prime bases.
1. The progression. Let M be the product of the odd members of
{q_1, ..., q_k}, with M = 1 if all of them are 2. For each odd q_i choose
a nonzero quadratic nonresidue c_i mod q_i; this is possible because
exactly half of the nonzero residues are nonresidues. By the Chinese
remainder theorem there is a residue class a mod M with a = c_i (mod q_i)
for every odd q_i; if M = 1 take the unique class. Since 1 is a square,
a is not 1 mod any q_i, and a is not 0 mod any q_i, so
gcd(a (a-1), M) = 1.
This is precisely the admissibility condition of Proposition 2, so that
proposition applies with this M and this a.
Note what step 1 buys. Reducing mod q_i is the same as asking for p = a
(mod q_i), and a is a non-square mod q_i. Later, in step 4, quadratic
reciprocity turns this into "q_i is a non-square mod p".
2. Apply Proposition 2. Get a set R(x) of primes with
x < p < 2x, p = a (mod M), p = 4 r Q + 1,
Q > x^{0.9} prime, every prime ell | r has exp(L^{0.1}) < ell < exp(L^{0.3}),
and with #R(x) >= c_{M,a} x / L^2. For x large every p in R(x) exceeds
every q_i, so p does not divide q_1...q_k.
Since r and Q are odd (Q > x^{0.9} > 2, and all prime factors of r are
odd), the product r Q is odd, hence
p = 4 r Q + 1 = 5 (mod 8), and in particular p = 1 (mod 4).
The congruence 5 mod 8 is not an accident: it is exactly the case in which
2 is a non-square (see 1.6), so the base 2 is handled at the same time as
the odd bases. That is why the shape contains the factor 4 rather than 2.
3. Every base is a non-square mod p. Fix p in R(x) and one base q = q_i.
If q is odd then q = q_i for some i, and q divides M, so
(q|p) = (p|q) by reciprocity, because p = 1 (mod 4) kills the sign,
= (a|q) because p = a (mod M) and q | M,
= -1 by the choice of a in step 1.
If q = 2, the supplementary law for 2 and p = 5 (mod 8) give (2|p) = -1.
Either way, q is a non-square mod p.
4. Hence the index is odd. By Lemma 1.5, iota_p(q) is odd. Since
iota_p(q) divides p - 1 = 4 r Q and is odd, it divides r Q. So either
iota_p(q) = 1, or iota_p(q) has an odd prime divisor lambda with
lambda | r Q, that is lambda = Q or lambda | r.
For such lambda, the definition of the order gives
q^{(p-1)/lambda} = 1 (mod p), (4.1)
because order divides (p-1)/lambda. So the primes p we must throw away are
exactly the p for which one of finitely many conditions of the form (4.1)
holds. Two cases.
5. Case A: lambda = Q. Then Q | iota_p(q), so the integer
j = (p-1)/Q = 4 r
satisfies 1 <= j < 2 x^{0.1}, because p < 2x and Q > x^{0.9}. Also
q^j = 1 (mod p) by (4.1), so p divides q^j - 1. Count such p by counting
prime divisors of a product. Every p in (x,2x) dividing the integer
P = prod_{1 <= j < 2x^{0.1}} (q^j - 1)
contributes at least log p > L to log P, so the number of them is at most
(log P)/L. And
log P <= sum_{j < 2x^{0.1}} log(q^j) = log q * sum_j j
<<_q (x^{0.1})^2 = x^{0.2}.
Hence
#{p in (x,2x) : Q | iota_p(q)} = O_q( x^{0.2} / L ) = o( x / L^2 ),
since x^{0.2} L < x^0.5 L < x for large x. Case A is negligible.
6. Case B: lambda | r. Here lambda is a prime in the window
exp(L^{0.1}) < lambda < exp(L^{0.3}). For each such lambda, the primes p
we are counting satisfy, by (4.1) and by lambda | p-1,
p = 1 (mod lambda), q^{(p-1)/lambda} = 1 (mod p),
and lie in (x,2x); they also satisfy p > q and p > lambda, so p does not
divide q lambda. Those are exactly the hypotheses of Proposition 3, which
bounds their number by
C_q ( x / (lambda (lambda-1) L) + x^{1-eta} ).
Sum over the primes lambda in the window. For the first term, the sum of
1/(lambda(lambda-1)) over primes lambda at least exp(L^{0.1}) is at most
the same sum over all integers in that range, which telescopes:
sum_{lambda > exp(L^{0.1})} 1/(lambda(lambda-1))
<= sum_{n > exp(L^{0.1})} 1/(n(n-1))
= 1 / exp(L^{0.1}),
using 1/(n(n-1)) = 1/(n-1) - 1/n. For the second term, there are at most
exp(L^{0.3}) primes in the window (crudely: at most exp(L^{0.3}) integers).
Hence
#{p in (x,2x) : some lambda | r divides iota_p(q)}
<= C_q ( x / L * exp(-L^{0.1}) + exp(L^{0.3}) x^{1-eta} )
= o( x / L^2 ).
Indeed, multiplying the first term by L^2/x gives L exp(-L^{0.1}), and
multiplying the second by L^2/x gives L^2 exp(L^{0.3} - eta L); the second
exponent tends to minus infinity, since eta = 10^{-6} beats L^{0.3}, and
the first clearly tends to 0.
7. Assemble. We have shown, for one fixed base q:
#{p in R(x) : iota_p(q) > 1} = o( x / L^2 ).
The bases are finitely many, k of them, and the sum of k quantities that
are each o(x/L^2) is still o(x/L^2). Therefore, for all large x,
# {p in R(x) : iota_p(q_i) = 1 for every i}
>= #R(x) - k * o(x/L^2)
>= ( c_{M,a} - o(1) ) x / L^2
>= ( c_{M,a}/2 ) x / L^2.
Every such p satisfies x < p < 2x and ord_p(q_i) = p - 1 for all i, which
is Theorem 1 with c = c_{M,a}/2. QED
Three things to notice about this proof, because they are the reason the
later parts are long and this part is short.
(i) The counting in Case A uses nothing but the size of q^j - 1; there is
no analytic input. It works because Q was forced to be enormous (bigger
than x^{0.9}), which forces j = (p-1)/Q to be small (below 2x^{0.1}).
That single number 0.9 is where the strength of Proposition 2 matters.
(ii) The counting in Case B is the only place where a real theorem about
L-functions enters, and it enters in the pleasant direction: an upper
bound of size x/(lambda^2 L) for a set of primes of natural size x/(lambda L).
(iii) Case B needs the window exp(L^{0.1}) < lambda < exp(L^{0.3}) for two
different reasons: lambda > exp(L^{0.1}) makes the telescoping sum small,
and lambda < exp(L^{0.3}) keeps the number of terms small enough that the
error term x^{1-eta} does not accumulate. Both constraints are exactly
what Proposition 2 hands over.
It remains to prove the two propositions. Proposition 3 is Part 8; it is
the shortest complete proof in the note if you accept Input A. Proposition
2 is Parts 5 and 9, and it is where all the sieve machinery lives.