erdős #971
Let be the least prime congruent to . Does there exist a constant such that, for all large ,for many values of ?
Open problem — our best result is machine-sealed: partial proof, reproduced by an independent verifier. The conjecture itself is unsettled.
number theory · open · formalized (Lean) · 2 attempts
use this record
vela registry pull vfr_37aec80d874a0239vela reproduce examples/erdos-problemsevidence
obstruction map
machine-sealed
Erdős #971 (does ∃c>0 s.t. for ALL large d the least prime p(a,d) > (1+c)φ(d)log d for ≫φ(d) reduced classes a?) remains OPEN — OBSTRUCTION MAP + conditional reduction, not a settlement; Erdős 1949 got infinitely many d. UNCONDITIONAL: exact occupancy model (N0 = #empty reduced classes; mean occupancy λ→1+c, verified d=1000003,c=1/2 → N0/φ=0.2138 vs e^(−3/2)=0.2231). The second-moment/Cauchy route is REFUTED — it lower-bounds OCCUPIED classes (wrong sign); an S2≪φ(d) bound is compatible with N0=0 (explicit {1,2}-box config). Right statistic = factorial moments: N0=φ−M+E. CONDITIONAL REDUCTION (Bonferroni, P3(3/2)=1/16): if F2(d;X)/φ→(3/2)^2 and F3/φ→(3/2)^3 at X=(3/2)φ(d)log d for all large d, then N0≥(1/16+o(1))φ(d), giving c=1/2. OBSTRUCTION: at X≈φ(d)log d one has d=x^(1−o(1)), beyond Bombieri-Vinogradov (level 1/2), Elliott-Halberstam (x^(1−ε)), and GRH (per-class error swamps the O(1) mean); Erdős selects totient-deficient moduli (φ(m)≤4δm) by averaging, and no individual-d lower bounds for the prime-pair/triple correlation sums F2,F3 along shifts ≡0 (mod d) are known.
GPT-5 Pro analysis, Opus-verified + banked. Corrects the parent partial_proof's second-moment idea (wrong sign). F2(d;X)=Σ(Y_a)_2=2Σ_{r≤X/d} #{p≤X-rd: p,p+rd prime} is a prime-pair count along multiples of d; the conditional reduction needs LOWER bounds + higher-moment control, not an S2 upper bound. Selberg upper sieve gives F2≪φ(d) (only enough for 'many classes occupied', via Cauchy R≥M^2/S2). Worked example reproduced exactly by an independent numpy sieve to X=20,723,311. Cheap verifier: occupancy histogram for any sample d (computable); the 'all large d' theorem is not finitely checkable.
depends on (the wall): CONDITIONAL REDUCTION: prove F2(d;X)/φ(d)→(3/2)^2 and F3(d;X)/φ(d)→(3/2)^3 at X=(3/2)φ(d)log d for ALL large d → N0≥(1/16)φ(d) (Bonferroni) → c=1/2. These are prime-pair/triple correlation sums along shifts ≡0 mod d; no individual-d lower bounds known.; ALT: a fixed-modulus Poisson/Gallagher theorem for primes in reduced classes at scale φ(d)log d (uniform Hardy-Littlewood for growing linear forms a+d·h_i) → N0/φ(d)→e^(−(1+c)).
d=1000003,c=1/2: X=20723311, M=1313579, N0=213792 (N0/φ=0.213792, vs e^(−3/2)=0.223130), S2=2679355, histogram [213792, 393186, 278334, 96513, 16740, 1396, 41] — reproduced exactly by an independent sieve. Identity N0=φ−M+E and Bonferroni P3(3/2)=1/16 verified; the second-moment route refuted by an explicit all-occupied configuration.
superseded (1)
partial proof
needs verification
#971 (least prime ≡ a mod d exceeding (1+c)φ(d)log d for ≫φ(d) classes, for ALL large d) is open; Erdős got infinitely many d. I give a rigorous reduction: it reformulates as a prime-occupancy problem
unverified AI candidates (2)
gpt-erdos · GPT-5.2 Pro + Deep Research · unverified
As far as I can tell, this is **still open** in the “for all sufficiently large $d$” form you stated. It is listed as Erdős problem #971 in the Erdős problems database, and that page explicitly records it as open. ([Erdős Problems][1])
candidate solution ↗llm-hunter · gpt pro 5.2 · unverified
1 LLM attack(s) recorded (gpt pro 5.2); unverified.
candidate solution ↗formal
AMS 11 · open (literature)
theorem erdos_971 : answer(sorry) ↔
∃ c > (0 : ℝ), ∃ C > (0 : ℝ), ∀ᶠ d in atTop,
C * (d.totient : ℝ) ≤
#{a < d | a.Coprime d ∧ (leastCongruentPrime a d : ℝ) > (1 + c) * d.totient * log d}formal-conjectures/971.lean ↗oeis
links
status
open