Erdős Problem #200

Erdős Problem #200: longest arithmetic progression of primes up to $N$ (ROUND 2)

1) ROUND-2 OBJECTIVE

I again pursue path (C). This is Erdős Problem #200 [Bloom200]. Round 1 proved the standard upper bound \[ L(N)\le (1+o(1))\log N, \] but did not isolate where that argument fundamentally stops. In this round I sharpen the modular argument into an exact dichotomy for the first term of a prime progression, prove a stronger upper bound in the generic case, and then give an explicit family of pseudoprogressions showing that the primorial/congruence strategy cannot by itself prove $L(N)=o(\log N)$.

2) Round-1 FOUNDATION USED

From Round 1 I use the already-proved fact that if \[ a,a+d,\dots,a+(k-1)d \] is a $k$-term arithmetic progression of primes, then every prime $q\le k/2$ divides $d$. Equivalently, \[ P(k/2):=\prod_{q\le k/2} q \mid d. \] I also use the Round-1 bound $k\le (1+o(1))\log N$.

3) NEW INSIGHT / TOOL (ROUND 2)

The new tool is a precise divisibility dichotomy.

Key new dichotomy. For all sufficiently large $k$, either

• the first prime $a$ satisfies $a>k$, in which case every prime $q\le k$ divides $d$; or
• the first prime $a$ itself is the only possible exception, and then necessarily \[ a\in (k/2,k]\cap \mathbf P \] and \[ P(k)/a\mid d. \]

So the only obstruction to improving the Round-1 logarithmic upper bound by the primorial method is the exceptional regime where the first term itself is a prime in $(k/2,k]$.

4) ATTACK PLAN (ROUND 2)

The exact Round-1 gap was that the modular argument only yielded $d\gg e^{(1+o(1))k}$, which still allows $k\asymp \log N$.

I now proceed in two steps.

1. Strengthen the divisibility statement from primes $\le k/2$ to primes $\le k$, up to one forced exceptional prime.
2. Show that if the exception does not occur (that is, if $a>k$), then the extra factor of $k$ in $(k-1)P(k)$ gives the stronger upper bound \[ k\le \log N-\log\log N+o(\log\log N). \] Then I explicitly construct pseudoprogressions at scale $e^{(1+o(1))k}$ that satisfy all local congruence conditions up to $k$, proving that those local conditions alone can never yield $o(\log N)$.

5) WORK (ROUND 2)

Let \[ p_j=a+jd\qquad (0\le j\le k-1) \] be a $k$-term arithmetic progression of primes, with $p_{k-1}\le N$. Write \[ P(x):=\prod_{q\le x} q, \qquad \vartheta(x):=\sum_{q\le x}\log q, \] where in both places $q$ runs over primes.

Proposition 5.1. If $a\le k$, then in fact $a\in (k/2,k]$.

Proof. The first term $a$ is prime. If $a\le k/2$, then by the Round-1 divisibility lemma the prime $a$ divides $d$. Hence \[ a+d \] is divisible by $a$ and is strictly larger than $a$, so it is composite. This contradicts the primality of the second term. Therefore $a>k/2$. $\square$

Theorem 5.2 (exact divisibility dichotomy). For all sufficiently large $k$ (equivalently, whenever $P(k/2)>k$), exactly one of the following two alternatives holds:

1. $a>k$ and $P(k)\mid d$;
2. $a\in (k/2,k]$ is prime and $P(k)/a\mid d$.

Proof. By the Round-1 lemma, \[ P(k/2)\mid d. \] For sufficiently large $k$ this implies $d\ge P(k/2)>k$.

Now let $q$ be any prime with $k/2<q\le k$. Suppose $q\nmid d$. Since $d$ is invertible modulo $q$, the congruence \[ a+jd\equiv 0\pmod q \] has exactly one residue class of solutions modulo $q$, so among the $k$ indices $0,1,\dots,k-1$ there is at least one $j$ with $a+jd\equiv 0\pmod q$. Because every term of the progression is prime, that term must equal $q$.

But if $j\ge 1$, then \[ a+jd\ge a+d>d>k\ge q, \] so $a+jd$ cannot equal $q$. Therefore the only possible divisible term is the first one $j=0$, and hence $q=a$.

Thus every prime $q\le k$ divides $d$, except possibly the single prime $q=a$. If $a>k$, there is no exception at all, so $P(k)\mid d$. If $a\le k$, then Proposition 5.1 shows that $a\in (k/2,k]$, and the only possible missing factor is exactly $a$, so $P(k)/a\mid d$. This proves the dichotomy. $\square$

Corollary 5.3 (generic-case strengthening). Assume $a>k$. Then \[ k\le \log N-\log\log N+o(\log\log N). \]

Proof. In the case $a>k$, Theorem 5.2 gives $P(k)\mid d$, so $d\ge P(k)$. Therefore \[ N\ge a+(k-1)d>(k-1)P(k). \] Taking logarithms, \[ \log N\ge \log(k-1)+\vartheta(k). \] By the classical de la Vallée Poussin form of the prime number theorem, \[ \vartheta(k)=k+O\left(k e^{-c\sqrt{\log k}}\right) \] for some absolute $c>0$. The error term is $o(\log k)$, so \[ \log N\ge k+\log k+o(\log k). \] Round 1 already gave $k\le (1+o(1))\log N$, hence \[ \log k=\log\log N+O(1). \] Substituting this into the previous display gives \[ k\le \log N-\log\log N+o(\log\log N), \] as claimed. $\square$

Proposition 5.4 (explicit pseudoprogressions). For every integer $k\ge 2$ there exists a length-$k$ arithmetic progression \[ x_j=p+jP(k)\qquad (0\le j\le k-1) \] with the following properties:

1. $p$ is prime and $k<p\le 2k$;
2. no term $x_j$ is divisible by any prime $q\le k$;
3. the last term satisfies \[ x_{k-1}\le 2k+(k-1)P(k), \] so in particular \[ \log x_{k-1}=k+O(\log k). \]

Proof. By Bertrand's postulate there exists a prime $p$ with $k<p\le 2k$. Set \[ d:=P(k). \] For any prime $q\le k$, we have $q\mid d$, hence \[ x_j=p+j d\equiv p\not\equiv 0\pmod q, \] because $p>k\ge q$. Thus no $x_j$ has a prime divisor at most $k$. The bound on $x_{k-1}$ is immediate from the definition, and \[ \log P(k)=\vartheta(k)=k+o(k) \] by the prime number theorem, which implies \[ \log x_{k-1}=k+O(\log k). \] $\square$

Consequence for proof strategies. Proposition 5.4 shows that local congruence information modulo primes $q\le k$ allows length-$k$ arithmetic progressions all the way up to scale $e^{(1+o(1))k}$. Therefore:

Any argument based only on congruence obstructions modulo primes up to $k$ cannot prove $L(N)=o(\log N)$.

Such an argument can force at most the scale $k\ll \log N$, and Round 1 already reaches that barrier.

6) ADVERSARIAL VERIFICATION

I now test the new work for hidden weaknesses.

• Is the exceptional case real, or just an artefact of the proof? It is real. The prime progression \[ 5,11,17,23,29 \] has $k=5$, first term $a=5\in (k/2,k]$, and common difference $d=6$, which is not divisible by $5$.
• Did Proposition 5.4 accidentally prove something about prime progressions? No. It proves only the existence of arithmetic progressions avoiding small prime divisors. That is exactly the intended barrier: local congruence conditions do not distinguish these pseudoprogressions from genuinely prime progressions.
• Does Theorem 5.2 require large $k$? Yes, because I used $P(k/2)>k$ to deduce $d>k$. This is harmless for an asymptotic problem; finitely many small values can be absorbed into constants.
• Did Corollary 5.3 use more than was proved? No. It uses only $N>(k-1)P(k)$ and the standard error term for $\vartheta(k)$.
• Does the round really sharpen Round 1? Yes. It isolates the only local exceptional regime, proves a stronger upper bound when that regime is absent, and rigorously explains why the old primorial method stops where it stops.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 proves two genuinely new things beyond Round 1.

1. For long prime progressions, the only possible failure of full divisibility $P(k)\mid d$ is that the first term itself is a prime in $(k/2,k]$.
2. Outside that exceptional case one has the stronger bound \[ k\le \log N-\log\log N+o(\log\log N). \] Moreover, explicit pseudoprogressions show that the purely local congruence/primorial strategy cannot by itself do better than the Round-1 logarithmic bound.

So the remaining difficulty has been sharply localized: any proof of $L(N)=o(\log N)$ must either exploit information beyond local congruence obstructions, or else must somehow rule out the exceptional regime $a\in (k/2,k]$ for genuinely long prime progressions.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 57%

References

References

• [Bloom152] T. F. Bloom, Erdős Problem #152, https://www.erdosproblems.com/152, accessed 2026-03-07.
• [Bloom200] T. F. Bloom, Erdős Problem #200, https://www.erdosproblems.com/200, accessed 2026-03-07.
• [Bloom201] T. F. Bloom, Erdős Problem #201, https://www.erdosproblems.com/201, accessed 2026-03-07.
• [ESS94] P. Erdős, A. Sárközy, and T. Sós, On sum sets of Sidon sets. I, Journal of Number Theory 47 $1994$, 329--347.
• [GT08] B. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, Annals of Mathematics 167 $2008$, 481--547.
• [KSS75] J. Komlós, M. Sulyok, and E. Szemerédi, Linear problems in combinatorial number theory, Acta Mathematica Academiae Scientiarum Hungaricae 26 $1975$, 113--121.
• [MV07] H. Montgomery and R. Vaughan, Multiplicative Number Theory I. Classical Theory, Cambridge Studies in Advanced Mathematics 97, Cambridge University Press, 2007.
• [OBryant04] K. O'Bryant, A complete annotated bibliography of work related to Sidon sequences, Electronic Journal of Combinatorics 11 $2004$, Dynamic Survey 11.
• [OBryant10] K. O'Bryant, Thick subsets that do not contain arithmetic progressions, arXiv:0912.1494.
• [Semchankau20] A. Semchankau, Maximal subsets free of arithmetic progressions in arbitrary sets, arXiv:2010.04490.

OBJECTIVE AND SOURCE REVIEW

Erdős #200; independent attempt, 2026-09-23. Does the maximum length $L(N)$ of a nonconstant prime arithmetic progression in $[1,N]$ satisfy $o(\log N)$? I read the complete supplied 200.tex. Its claimed second-order logarithmic improvement uses an invalid comparison of error terms. There is, however, a sharper elementary description of the exceptional first term.

WORK: CORRECTED EXACT DICHOTOMY

Suppose $a,a+d,\ldots,a+(k-1)d$ are prime, with $d>0$, $k\ge2$. Then \[ k\le a. \] Indeed, if $a\mid d$, the second term is composite. Otherwise, if $k>a$, the term at index $a$ equals $a(1+d)$ and is composite. Consequently the supplied exceptional interval $k/2<a\le k$ reduces to $a=k$, necessarily prime. If $a>k$, every prime $q\le k$ divides $d$: otherwise one of the first $q$ indices gives a term divisible by $q$, and that term exceeds $q$. If $a=k$, the same argument works for $q<k$, while $k\nmid d$ is required by the second term. Hence, without any large-$k$ qualification, \[ \begin{cases} P(k)\mid d,&a>k,\\ P(k)/k\mid d,\quad k\nmid d,&a=k\text{ prime}, \end{cases} \qquad P(k)=\prod_{q\le k}q. \] In particular, for composite $k$ only the first alternative exists. The example $5,11,17,23,29$ verifies the second alternative is possible.

CORRECTION OF THE ASYMPTOTIC CLAIM

The valid generic-case inequality is \[ \log N>\vartheta(k)+\log(k-1). \] The supplied bound $\vartheta(k)=k+O(ke^{-c\sqrt{\log k}})$ does not make the error $o(\log k)$: the ratio of that error allowance to $\log k$ tends to infinity. Nor does $\vartheta(k)=k+o(k)$ imply the supplied pseudoprogression estimate $\log x_{k-1}=k+O(\log k)$; it implies only $k+o(k)$. Thus the asserted $-\log\log N+o(\log\log N)$ improvement is not proved by that argument.

ADVERSARIAL VERIFICATION AND REMAINING GAP

The term of index $a$ exists exactly when $k>a$, so the boundary $k=a$ is retained correctly. The divisibility proof uses positivity of $d$ and primality of every term. The stronger exact dichotomy still gives only logarithmic scale. Pseudoprogressions with step $P(k)$ continue to evade every prime at most $k$, so this correction does not supply the global primality information needed for $o(\log N)$.

SOURCES CHECKED

Complete local source: gpt_pro_5.4/200.tex. Official statement and baseline checked at the indexed primary page https://www.erdosproblems.com/history/200, 2026-09-23. The exact divisibility argument is self-contained.

FINAL

UNRESOLVED. The exception is narrowed to $a=k$ prime; the unjustified second-order estimate is withdrawn.

COMPLETION ESTIMATE

Conservative subjective progress toward the little-oh target. COMPLETION: 12%

Erdős Problem #200: Longest arithmetic progression of primes up to $N$

1) Formal restatement (quantifiers, definitions, edge cases)

For $N\ge 2$, let $L(N)$ be the maximum integer $k$ such that there exist integers $a\ge 2$ and $d\ge 1$ with \[ a,\, a+d,\, a+2d,\,\dots,\, a+(k-1)d \ \text{all prime and}\ a+(k-1)d\le N. \] (Equivalently, $L(N)$ is the length of the longest arithmetic progression contained in the set of primes $\le N$.)

Problem statement.

Is it true that \[ L(N)=o(\log N)\qquad (N\to\infty)? \]

Edge cases.

$L(N)$ is nondecreasing in $N$ and $L(N)\ge 1$ always. For $k\ge 3$, any $k$-term progression of odd primes has even common difference $d$.

2) Quick literature/context check

• The primes contain arbitrarily long arithmetic progressions (Green--Tao theorem) [GreenTao08], so $L(N)\to\infty$, but existing proofs give no usable quantitative growth rate for $L(N)$.
• A standard application of the prime number theorem (via the Chebyshev function $\vartheta(x)=\sum_{p\le x}\log p\sim x$) yields the upper bound \[ L(N)\le (1+o(1))\log N. \] A complete proof is included below.
• Heuristics based on treating primes as a random set of density $\approx 1/\log N$ (and refined Hardy--Littlewood type constants) predict that the expected number of $k$-term prime progressions up to $N$ is about \[ \asymp \frac{N^2}{(k-1)(\log N)^k}, \] suggesting that the maximal $k$ satisfies $k\approx 2\log N/\log\log N$ (hence $o(\log N)$). A statement of this heuristic count appears, for instance, in The Prime Pages discussion of prime arithmetic progressions [PrimePagesAP].

3) Attack plan

1. Prove the known PNT-based upper bound $L(N)\le (1+o(1))\log N$ carefully, since it is explicitly mentioned in the prompt.
2. For the main open question $L(N)=o(\log N)$, outline why "current technology" (sieve bounds, distribution in residue classes, Green--Tao transference) does not presently deliver such a sharpening.
3. Provide a quick computational sanity check for moderate $N$.

4) Work

Theorem 4.1 (PNT upper bound).

Let $p_0, p_1,\dots,p_{k-1}$ be a $k$-term arithmetic progression of primes with $p_{k-1}\le N$. Then \[ k\le (1+o(1))\log N\qquad (N\to\infty). \]

Computational check (moderate $N$).

A brute-force search over all prime pairs $(p,q)$ with $p<q\le N$ (testing the progression with step $d=q-p$) gives: \[ L(10^3)=7,\quad L(5\cdot 10^3)=10,\quad L(10^4)=10,\quad L(2\cdot 10^5)=10, \] with a longest example for these ranges being \[ 199,\\ 409,\\ 619,\dots,\\ 2089\qquad (\text{length }10,\\ d=210). \] This is only a sanity check; it is not evidence for asymptotic behaviour.

5) Verification / consistency checks

• The key modular argument is checked in two regimes: $q\le k/2$ forces $\ge2$ multiples, hence $q\mid d$; $q\in(k/2,k]$ gives at most one multiple, forcing a near-total divisibility of $d$ when $d>k$.
• The only analytic input is $\vartheta(x)\sim x$, a standard equivalent form of the prime number theorem.

6) Final

UNRESOLVED.

1. Strongest proved partial result included here. Theorem 4.1 proves the known upper bound $L(N)\le (1+o(1))\log N$ from the prime number theorem. Also $L(N)\to\infty$ by Green--Tao [GreenTao08].
2. First precise obstacle. To improve the bound to $o(\log N)$ one would need a quantitative upper bound excluding $k$-term prime progressions for $k$ as large as $c\log N$, uniformly in the common difference. Current sieve/analytic tools (and the transference methods in Green--Tao) do not supply such a uniform "union bound" at this scale.
3. Most plausible next lemma. A plausible route would be a sharp upper bound for the number of $k$-term prime progressions up to $N$ of the form \[ \#\\{(a,d):\\ a,a+d,\dots,a+(k-1)d\le N\text{ all prime}\\}\\ \le\\ N^2\exp(-c k\log\log N) \] for $k$ up to (say) $\varepsilon\log N$, which would imply (by the first moment method) that $L(N)=o(\log N)$. Proving such bounds seems to require substantially stronger uniformity estimates for primes in progressions than are currently available.

7) Completion estimate

\[ \textbf{Completion: }40\%. \] (We can prove the standard PNT upper bound cleanly and explain the heuristic, but the main asymptotic sharpening remains open.)