Reused writeup on Math-1006 (gpt pro 5.2)

Erdős Problem 971 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/971

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/971.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/971.tex.

Let $p(a,d)$ be the least prime congruent to $a\pmod{d}$. Does there exist a constant $c>0$ such that, for all large $d$,\[p(a,d) > (1+c)\phi(d)\log d\]for $\gg \phi(d)$ many values of $a$? Erdős [Er49c] could prove this is true for an infinite sequence of $d$. He also proved that, for any $\epsilon>0$,\[p(a,d)< \epsilon \phi(d)\log d\]for $\gg_\epsilon \phi(d)$ many values of $a$. References [Er49c] Erdős, P., On some applications of {B}run's method . Acta Univ. Szeged. Sect. Sci. Math. $1949$, 57--63.

1) FORMAL RESTATEMENT
For integers $d\ge 1$ and $a\in\mathbb{Z}$, define \[ p(a,d):=\min\{p\text{ prime}: p\equiv a\pmod d\}. \] Ambiguity. If $\gcd(a,d)>1$, there may be no prime congruent to $a\pmod d$ (e.g. $a\equiv 0\pmod d$ with $d>1$), or there may be a unique such prime dividing $d$. The natural convention in this question is to restrict to reduced residue classes $a\bmod d$ with $\gcd(a,d)=1$.

Using $\phi(d)$ for Euler's totient and taking $\log$ to be the natural logarithm, the question is:

Does there exist a constant $c>0$ such that for all sufficiently large $d$, the set \[ A_d(c):=\{a\in\{1,2,\dots,d\}: \gcd(a,d)=1\text{ and }p(a,d)>(1+c)\,\phi(d)\log d\} \] has cardinality $|A_d(c)|\ge c'\phi(d)$ for some absolute $c'>0$ independent of $d$?

2) QUICK LITERATURE/CONTEXT CHECK
The statement records two results of Erdős: (i) the displayed lower bound holds for an infinite sequence of moduli $d$; (ii) for any fixed $\varepsilon>0$ there are $\gg_\varepsilon \phi(d)$ classes with $p(a,d)<\varepsilon\phi(d)\log d$. I do not invoke any further external results.

3) ATTACK PLAN
Proof track: relate the distribution of $p(a,d)$ to how primes $\le X$ occupy reduced residue classes mod $d$; show that for $X\asymp \phi(d)\log d$ many classes remain empty up to $X$.

Disproof track: attempt to prove that for infinitely many $d$ almost every reduced residue class already contains a prime $\le (1+c)\phi(d)\log d$, contradicting the desired positive proportion of large least primes.

I only obtain unconditional counting lemmas and small numerical checks.

4) WORK
FAST REALITY CHECK (small moduli). For $d\le 100$, I computed $p(a,d)$ for all $a$ with $\gcd(a,d)=1$ and checked the proportion of classes satisfying $p(a,d)>(1+c)\phi(d)\log d$. For $c=0.1$, the average proportion over $2\le d\le 100$ was approximately $0.242$. Sample values: \[ \begin{array}{c|c|c|c} d & \phi(d) & (1+0.1)\phi(d)\log d & |A_d(0.1)|/\phi(d)\\\hline 30 & 8 & 29.93 & 1/8\\ 60 & 16 & 72.06 & 1/16\\ 90 & 24 & 118.79 & 3/24\\ 100 & 40 & 202.63 & 5/40 \end{array} \] This is only a sanity check at very small $d$.

Lemma 971.1 (injective counting bound). Fix $d\ge 1$ and $X\ge 2$. Let \[ B_d(X):=\{a\in\{1,2,\dots,d\}: \gcd(a,d)=1\text{ and } p(a,d)\le X\}. \] Then \[ |B_d(X)|\le \pi(X), \] where $\pi(X)$ is the number of primes $\le X$. Consequently, \[ |\{a\in\{1,\dots,d\}: \gcd(a,d)=1\text{ and }p(a,d)>X\}|\ge \phi(d)-\pi(X). \]

Proof. For each $a\in B_d(X)$, choose the prime $p(a,d)\le X$. If $a\ne a'$ are two reduced residue classes mod $d$, then $p(a,d)\equiv a\not\equiv a'\equiv p(a',d)\pmod d$, so $p(a,d)\ne p(a',d)$. Thus the map $a\mapsto p(a,d)$ from $B_d(X)$ to the set of primes $\le X$ is injective, giving $|B_d(X)|\le \pi(X)$. The second inequality follows because the reduced residue classes are exactly $\phi(d)$ in number. $\square$

Lemma 971.2 (distinct least primes across classes). For fixed $d\ge 2$, the values $\{p(a,d): 1\le a\le d,\ \gcd(a,d)=1\}$ are $\phi(d)$ distinct primes, none dividing $d$. In particular, \[ \max_{\gcd(a,d)=1} p(a,d)\ \ge\ p_{\phi(d)}, \] where $p_m$ denotes the $m$-th prime.

Proof. If $\gcd(a,d)=1$ then any prime $p\equiv a\pmod d$ cannot divide $d$ (otherwise $p\mid d$ would imply $a\equiv 0\pmod p$ and hence $\gcd(a,d)>1$). Thus $p(a,d)$ never divides $d$. If $a\ne a'$ are reduced residue classes, then any prime congruent to $a\pmod d$ is not congruent to $a'\pmod d$, so $p(a,d)\ne p(a',d)$. Therefore these least primes are $\phi(d)$ distinct primes. Ordering them increasingly gives a list of $\phi(d)$ distinct primes, hence the largest is at least the $\phi(d)$-th prime $p_{\phi(d)}$. $\square$

5) VERIFICATION
Lemma lem:971-injection only uses injectivity of the map $a\mapsto p(a,d)$ and does not require distribution results for primes. Lemma lem:971-distinct requires $d\ge 2$; for $d=1$ the definition degenerates.

The computation for $d\le 100$ was verified by checking that every reduced residue class found a least prime within the sieve limit (primes up to $5\times 10^5$ were used).

6) FINAL
UNRESOLVED

(i) Strongest proved partial result. For any modulus $d$ and threshold $X$, at most $\pi(X)$ reduced residue classes mod $d$ can have least prime $\le X$ (Lemma lem:971-injection). Also, the least primes across reduced classes are all distinct (Lemma lem:971-distinct).

(ii) First gap (crisp). Unconditionally show (or refute) that there exist constants $c,c'>0$ such that for all sufficiently large $d$, \[ |\{a\bmod d: \gcd(a,d)=1,\ p(a,d)>(1+c)\phi(d)\log d\}|\ge c'\phi(d). \]

(iii) Top 3 next moves.

• Combine Lemma lem:971-injection with quantitative upper bounds on $\pi(X)$ at $X\asymp \phi(d)\log d$ to force $\phi(d)-\pi(X)\gg \phi(d)$; this would require nontrivial prime-counting input.
• Try to transfer known "Maier matrix"/irregularity ideas to least primes in progressions, aiming to show many residue classes avoid primes up to $(1+c)\phi(d)\log d$.
• Extend computation to larger $d$ (e.g. up to several thousand) and test stability of the proportion for various $c$, to guess plausible constants.

(iv) Minimal counterexample structure. A counterexample to the conjectured statement for a given $c$ would be an infinite sequence of moduli $d$ for which almost every reduced residue class contains a prime $\le (1+c)\phi(d)\log d$. Such a modulus would have to exhibit unusually even early prime coverage across residue classes.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.