Erdős problem #985 — wave 7z

Live-page check, literature check, and computation: 2026-07-28 (UTC).

Claim labels used throughout:

• [a] elementary-rigorous;
• [b] rigorous modulo the explicitly named published theorem;
• [c] plausible/structural-unverified;
• [d] computational-only.

0. Mandatory live-page gate

I fetched the rendered live page through the Bright Data browser route and followed its discussion and proof-claims links. I did not rely on the stale tracker YAML or on a search-engine snippet.

[d] Live state. The page is marked OPEN. It displays:

• 2 comments on this problem;
• 0 claimed proofs for this problem;
• Interested in collaborating: None;
• Currently working on this problem: None;
• Likes this problem: Dogmachine;
• This problem looks difficult: Dogmachine;
• no tractability or formalisation-worker marker.

The mandatory stop condition therefore did not fire.

The exact current statement, verbatim, is:

Is it true that, for every prime \(p\), there is a prime \(q<p\) which is a primitive root modulo \(p\)?

The page's complete mathematical remark is:

Artin conjectured that \(2\) is a primitive root for infinitely many primes \(p\), which Hooley \([Ho67b]\) proved assuming the Generalised Riemann Hypothesis. Heath-Brown \([He86b]\) proved that at least one of \(2\), \(3\), or \(5\) is a primitive root for infinitely many primes \(p\).

The page cites Erdős's source [Er65b], marks a Lean formalisation as present, and links OEIS sequences A002233, A219429, and A103309 as possible related sequences.

[d] Comments read in full.

1. Woett (2025-08-17) says that \(p>2\) is required and gives a random-set

heuristic based on \(\varphi(p-1)\) primitive-root residues and \(\pi(p)\) primes.

1. AronBhalla (2026-03-06) posts a GPT-5.4 literature lead: an almost-all

result attributed to Nongkynrih, a shifted-sieve/GRH result of Martin, and Oliveira e Silva's computation. The comment concludes that the full problem remains open. It is explicitly an unverified user comment.

Live sources: problem page, discussion thread, and proof-claims page.

1. The literal statement has a one-line counterexample

Proposition 1.1 [a]. The live statement exactly as written is false.

Proof. Take \(p=2\). There is no prime \(q<2\). This already falsifies the quantified statement, independently of what “primitive root modulo \(2\)” is taken to mean. \(\square\)

This is a boundary defect, not a resolution of the intended research question. [d] The first comment flags it, and the linked Lean formalisation adds the hypothesis \(p\ne2\). The rest of this report therefore studies the intended version:

I do not claim that (E985+) is settled.

2. Primary-source literature audit

Write \(G(p)\) for the least prime that is a primitive root modulo \(p\).

2.1 Original source and results actually listed on the page

[b] Erdős's original 1965 article asks the same question in the sentence beginning “As far as I know…”, at printed p. 233: P. Erdős, Some recent advances and current problems in number theory, author-archive PDF, scan p. 38.

[b] The two references listed on the live page exist with the stated bibliographic data:

• C. Hooley, On Artin's conjecture, J. Reine Angew. Math. 225 (1967),

209–220, DOI. Hooley proves Artin's fixed-base conjecture under the relevant GRH assumptions.

• D. R. Heath-Brown, Artin's conjecture for primitive roots, Quart. J.

Math. 37 (1986), 27–38, DOI. Its corollary gives the stated \(2,3,5\) alternative unconditionally.

Neither result is uniform in the modulus \(p\) in the way (E985+) requires: “one fixed base works for infinitely many \(p\)” does not imply “every \(p\) has some small prime base.”

2.2 The almost-all theorem: correction to the comment

Let \(N(H,p)\) count prime primitive roots \(q\le H\), and let \(\log_k\) denote the \(k\)-fold iterated logarithm.

[b] A. Nongkynrih, On prime primitive roots, Acta Arith. 72 (1995), 45–53, primary PDF, Theorem 1.2, proves for almost all primes \(p\)

when

with at most \(O(Y^\varepsilon)\) exceptional primes \(p\le Y\). This is

whose exponent is not fixed. Thus the comment's inference “take \(H=(\log p)^A\) for fixed large \(A\)” does not follow from Nongkynrih's theorem.

[b] The fixed-polylogarithmic almost-all result is instead Theorem 1 of G. Martin, The least prime primitive root and the shifted sieve, Acta Arith. 80 (1997), 277–288, primary PDF and arXiv:math/9807104. For \(\varepsilon\le20/21\), \(\eta>0\), and

all but \(O_{\varepsilon,\eta}(Y^\varepsilon)\) odd prime powers \(p^r\le Y\) satisfy

Since \(\omega(p-1)\ll\log p\), this is a fixed power of \(\log p\). Consequently (E985+) holds unconditionally for all primes outside a set whose counting function is \(O_\varepsilon(Y^\varepsilon)\), apart from a finite initial range. In particular it holds for a natural-density-one set of primes. This does not eliminate every exceptional prime.

2.3 Uniform and conditional results

[b] J. Ha, On the least prime primitive root, J. Number Theory 133 (2013), 3645–3669, DOI, proves the uniform unconditional bound \(G(p)\ll p^{3.1}\) for prime moduli (and related moduli). Its exponent is larger than \(1\), so it does not imply \(G(p)<p\).

[b] Under GRH, Martin's Corollary 3.1 gives

An explicit later result is stronger: K. McGown, E. Treviño, and T. Trudgian, Resolving Grosswald's conjecture on GRH, arXiv:1508.05182, Theorem 1, proves

under GRH. Together with the finite check below, this proves (E985+) under GRH. It is not an unconditional solution.

2.4 Prior computation

[d] Tomás Oliveira e Silva's author page reports that all prime moduli through \(10^{14}\) were tested and double-checked, and gives preliminary data through \(10^{16}\). The live URL now returns 404, so I verified the author's archived page and its compressed result table:

• archived primary page;
• archived \(G(p)\) table.

The table has test and double-test interval \([3,10^{14}]\); its counts cover the odd prime moduli in that interval and its largest occurring least-prime-root value is \(617\). No counterexample was reported. This is finite computational evidence only. I did not claim to independently repeat a \(10^{14}\) computation on this VM.

The numerical paper A. Paszkiewicz and A. Schinzel, On the least prime primitive root modulo a prime, Math. Comp. 71 (2002), 1307–1321, DOI, also gives record tables and studies Bach's proposed order \((\log p)(\log\log p)^2\). Those data and heuristics are not uniform theorems.

2.5 Two advertised unconditional “solutions” do not survive a local audit

This subsection is included because a current literature search otherwise appears to turn up a solution.

[a] Logical gap in the 2015 claim. N. A. Carella, Least Prime Primitive Roots, International Journal of Mathematics and Computer Science 10 (2015), 185–194, paper PDF, claims

for every sufficiently large prime. Its proof defines, at \(s=2\),

Equations (27)–(32) obtain a relation of the form

under the assumption that no small prime primitive root exists, and then infer a contradiction merely because \(\kappa_2(p)>0\).

That inference is not uniform: the paper itself says that \(\kappa_2=\kappa_2(p)\) depends on \(p\), and supplies no lower bound such as

with a uniform \(C>0\). Pointwise positivity permits \(\kappa_2(p)\) to be smaller than the error. Indeed, controlling the first nonzero term of this series is essentially controlling \(G(p)\), so the missing lower bound contains the hard part. The displayed argument therefore does not establish its claimed uniform theorem.

[a] False inequality in the 2025 preprint. The newer preprint N. A. Carella, Small Prime Primitive Roots in Arithmetic Progressions, arXiv:2509.19309, claims the still stronger unconditional bound

In equation (8.10), used to prove the decisive error estimate, it bounds the absolute value of an incomplete exponential sum by the absolute value of the corresponding complete sum:

This inequality is false in general because the omitted terms can cancel the retained terms (the two-term example \(z_1=1,z_2=-1\) already reverses it). Hence the cited complete-sum estimate does not bound that incomplete sum, Lemma 8.3 is not proved, and the final main-term/error comparison does not follow. The preprint also defines its prime-counting weight using \(\Lambda(u)\ne0\), which includes prime powers, without completing the extra step needed to retain the asserted arithmetic progression after passing to the prime base.

I therefore do not treat either Carella claim as a named theorem modulo which this problem is solved. This is consistent with the authoritative live page's current OPEN and 0 claimed proofs state.

3. Two elementary uniform classes

3.1 Multiplicative-group order a power of two

Proposition 3.1 [a]. If \(p\) is an odd prime and \(p-1\) is a power of two, then a prime \(q<p\) is a primitive root modulo \(p\).

Proof. Let \(q\) be the least positive quadratic nonresidue modulo \(p\). It is prime: if \(q=ab\) with \(1<a,b<q\), multiplicativity of the Legendre symbol would make at least one of \(a,b\) a smaller nonresidue. In a cyclic group of order \(2^k\), a nonsquare is an odd power of a fixed generator and therefore has order \(2^k\). Thus this prime \(q<p\) is a primitive root. \(\square\)

For example, this covers \(p=3,5,17,257,65537\); the proposition is uniform and makes no claim that this list is complete.

3.2 Safe primes

[b] This elementary case is also recorded in V. P. Ramesh and M. Makeshwari, Least Primitive Root of any Safe Prime is Prime, Amer. Math. Monthly 129 (2022), p. 971, DOI.

Proposition 3.2 [a]. If \(p=2r+1\) with \(p,r\) prime, then a prime \(q<p\) is a primitive root modulo \(p\).

Proof. The case \(p=5\) is witnessed by \(q=2\). Now let \(p\ge7\). The group has order \(2r\), so a quadratic nonresidue has order either \(2\) or \(2r\). The unique element of order \(2\) is \(-1\).

There is a quadratic nonresidue \(a\in\{2,\ldots,p-2\}\), since there are \((p-1)/2\ge3\) nonresidues and only one is \(-1\). Factor \(a\) over the integers. By multiplicativity of the Legendre symbol, at least one prime factor \(q\mid a\) is a nonresidue. It satisfies \(q\le a<p-1\), so it is not \(-1\); its order is therefore \(2r=p-1\). \(\square\)

Thus any counterexample to (E985+) must be neither a safe prime nor a prime with \(p-1\) a power of two. These propositions are genuine uniform subclasses but do not control general factorizations of \(p-1\).

4. Exact reduction to prime character sums

Set \(n=p-1\) and \(\theta(n)=\varphi(n)/n\). The standard character identity is

Proposition 4.1 [a]. If \(N(p)\) is the number of prime primitive roots below \(p\), then exactly

where

Proof. Sum the indicator over primes \(q<p\). The \(d=1\) character is principal and contributes \(\pi(p-1)\); the remaining terms are exactly \(E_p\). \(\square\)

In particular, (E985+) is exactly the uniform assertion

For a concrete sufficient target, put

There are \(\varphi(d)\) characters of exact order \(d\), while the coefficient is \(1/\varphi(d)\). The squarefree divisors selected by \(\mu(d)\) number \(2^{\omega(n)}\). Hence

Corollary 4.2 [a]. The uniform estimate

for every odd prime \(p\) would prove (E985+).

[c] Wall diagnosis. Known zero-free-region and shifted-sieve methods give enough cancellation for all but a very thin exceptional set; GRH removes that exceptional set. Unconditionally, the exact missing input is a uniform lower bound for the prime-primitive-root count—or an aggregate character/sieve estimate strong enough to show \(E_p>-\pi(p-1)\)—for the moduli whose relevant Dirichlet \(L\)-functions may have zeros very near \(1\). A bound for the least integer primitive root does not supply this prime-support estimate. This is the precise uniformity step absent from both a finite search and the invalid \(\kappa_2(p)>0\) argument above.

5. Independent exact computation through \(10^7\)

The standalone standard-library verifier is erdos985_wave7z_reverify.py.

Run from the repository root:

python runs/erdos985_wave7z_reverify.py

For every odd prime \(p\le10^7\), it:

1. builds an odd-only smallest-prime-factor sieve from scratch;
2. factors \(p-1\);
3. tests primes \(q<p\) in increasing order using the exact criterion

\[ \operatorname{ord}_p(q)=p-1 \iff q^{(p-1)/r}\not\equiv1\pmod p \quad\text{for every prime }r\mid p-1; \]

1. independently reruns the complete prefix \(p\le5000\) with a different

bytearray prime sieve and repeated multiplication to compute orders, using no factorisation criterion;

1. checks the two elementary subclasses in Section 3 directly;
2. checks the character indicator and its \(2^{\omega(n)}\) coefficient

count exactly, with rational arithmetic, for every cyclic order \(n\le200\).

[d] Exact result. All \(664578\) odd prime moduli \(p\le10^7\) have \(G(p)<p\). In fact the sharp finite bound is

and equality occurs uniquely at \(p=4022911\).

The strict record setters are:

[d] Reproducibility checks.

• The independent brute-order prefix contains 668 odd prime moduli.
• The exact character-indicator cross-check covers 20100 pairs \((n,k)\).
• The script checks 30657 safe-prime moduli and all five

power-of-two-order moduli in the range.

• The SHA-256 digest of every line p:G(p)\n, in increasing \(p\), is

  693c6e7aba56e460490682af3b3626e8f65d2d4bd335c281ef99d955284fb6cd
  

• The full run took 12.8 seconds of one CPU and about 183 MB RSS on this VM.
• The record list independently reproduces the archived Oliveira e Silva

first-occurrence table over their overlapping range.

The script contains assertions for the modulus count, record table, maximum, subclass counts, and digest. Altering or truncating the census causes the default run to fail.

[d] Cost of a much larger independent rerun. Linear extrapolation from the measured Python run to \(10^{14}\) is about 35600 core-hours, before segmentation overhead (roughly USD 1400 at USD 0.04/core-hour). An optimized compiled segmented program would be much faster, as Oliveira e Silva's historical distributed computation demonstrates. No finite extension, however large, closes (E985+) without a theorem that bounds all remaining moduli.

6. Verified outcome

• [a] The authoritative statement is literally falsified by \(p=2\).
• [a] The corrected odd-prime problem holds uniformly for safe primes

and for primes with \(p-1\) a power of two.

• [b] Martin proves it for all but \(O_\varepsilon(Y^\varepsilon)\)

primes up to \(Y\), and GRH proves it for every odd prime.

• [d] A from-scratch census proves the sharp bound \(G(p)\le211\) for

every odd prime \(p\le10^7\).

• [c] The intended unconditional all-\(p\) statement remains open after

this audit; the missing step is uniform prime-support cancellation for the exceptional moduli, not more finite computation.

FOUND: The live statement is literally false at \(p=2\); for the intended \(p>2\) version, \(G(p)\le211<p\) is independently certified for every prime \(p\le10^7\), two uniform subclasses are proved, and the exact unresolved uniform character-sum step is isolated.