Regenerated from the community database (Apache-2.0), dated, and linked back to it
from every problem. erdosproblems.com no longer shows statuses (Bloom's reasons); this is the database's record, not our verdict.
908 of 1221 statements are formalized in Lean (Formal Conjectures) · 107 carry an Erdős prize · 3 are independent of ZFC and 9 more can't be proved, or can't be disproved, from ZFC alone · “open” counts the computable and Lean-checked ones too.
Find problems
tag “arithmetic progressions” · 29 problems✕ clear
OPENPRIZE $5,000CLOSEDnumber theory · additive combinatorics · arithmetic progressions
If \(A \subset \mathbb{N}\) has \(\sum_{n \in A}\frac 1 n = \infty\), then must \(A\) contain arbitrarily long arithmetic progressions? Yes. This was proved by an internal OpenAI model in September 2026 [OAI26]; see the linked Lean proof.
**Erdős Problem 139**: Let \(r_k(N)\) be the size of the largest subset of \({1,...,N}\) which does not contain a non-trivial \(k\)-term arithmetic progression. Prove that \(r_k(N) = o(N)\).
Prove an asymptotic formula for \(r_k(N)\), the largest possible size of a subset of \(\{1, \dots, N\}\) that does not contain any non-trivial \(k\)-term arithmetic progression. That is, find \(f_k\) with \(r_k(N) / f_k(N) \to 1\) as…
On [Mathoverflow](https://mathoverflow.net/a/410815) user [leechlattice](https://mathoverflow.net/users/125498/leechlattice) shows that \(h(n) \ll n^{\frac 2 3}\).
Let \(A=\{a_1,a_2,\ldots\}\subset \mathbb{R}^d\) be an infinite sequence such that \(a_{i+1}-a_i\) is a positive unit vector (i.e. is of the form \((0,0,\ldots,1,0,\ldots,0)\)). For which \(d\) must \(A\) contain a three-term arithmetic…
Let \(k\geq 3\). Must any ordering of \(\mathbb{R}\) contain a monotone \(k\)-term arithmetic progression, that is, some \(x_1 <\cdots < x_k\) which forms an increasing or decreasing \(k\)-term arithmetic progression? The answer is no,…
What is the largest \(k\) such that in any permutation of \(\mathbb{Z}\) there must exist a monotone \(k\)-term arithmetic progression \(x_1 < \cdots < x_k\)? Here a permutation of \(\mathbb{Z}\) is a one-sided arrangement…
Must every permutation of \(\mathbb{N}\) contain a monotone 4-term arithmetic progression? Here a monotone \(k\)-term arithmetic progression in a permutation \(f\) is a set of indices \(i_1 < \cdots < i_k\) such that…
Let \(V\) be a vector space over the rationals and let \(k\) be a fixed positive integer. Then there is a set \(X_k \subseteq V\) such that \(X_k\) meets every infinite arithmetic progression in \(V\) but \(X_k\) intersects every…
If \(A\subset \mathbb{R}\) does not contain a 3-term arithmetic progression then must \(\mathbb{R}\backslash A\) contain an infinite arithmetic progression? Baumgartner [Ba75] answered this in the negative.
Are there arbitrarily long arithmetic progressions of primes? Solution: yes. Ref: Green, Ben and Tao, Terence, _The primes contain arbitrarily long arithmetic progressions_
Let \(N\geq 1\). What is the largest \(t\) such that there are \(A_1,\ldots,A_t\subseteq \{1,\ldots,N\}\) with \(A_i\cap A_j\) a non-empty arithmetic progression for all \(i\neq j\)?
PROVED LEANnumber theory · additive combinatorics · ramsey theory · arithmetic progressions
If ℕ is \(2\)-coloured then there must exist a monochromatic three-term arithmetic progression \(x,x+d,x+2d\) such that \(d>x\). This was first proved by Brown and Landman [BrLa99], who in fact show that this is always possible with…
Let \(\delta_k\) be such that in any \(2\)-colouring of \(\{1,\ldots,n\}\) there exist at least \((\delta_k+o(1))n^2\) many monochromatic \(k\)-term arithmetic progressions. Give reasonable bounds (or even an asymptotic formula) for…
SOLVEDnumber theory · primes · additive combinatorics · arithmetic progressions
Let \(k\geq 3\). Is it true that, in any finite colouring of the integers, there are monochromatic arithmetic progressions of primes of length \(k\)? It follows from the theorem of Green and Tao [GrTa08] (that any set of primes with…
Source: teorth/erdosproblems (its own interactive table), Apache-2.0, pulled 2026-10-21. A status here is what that database records, not an independent verification by us, except where a problem page says so.