erdős #142

← #141 · #143 → (packet.json; erdosproblems.com)

Let $r_{k} (N)$ be the largest possible size of a subset of ${1, \dots, N}$ that does not contain any non-trivial $k$ -term arithmetic progression. Prove an asymptotic formula for $r_{k} (N)$ .

Worked, still open.

additive combinatorics · open · prize $10000 · formalized (Lean) · 0 attempts

machinery: additive-combinatorics,arithmetic-progressions,Behrend-construction,density-increment,Szemeredi-theorem,Fourier-analytic-bound

use this record

vela registry pull vfr_37aec80d874a0239

vela reproduce examples/erdos-problems

evidence

unverified AI candidates (2)

gpt-erdos · GPT-5.2 Pro + Deep Research · unverified

Fix an integer (k\ge 3). Write ([N]={1,2,\dots,N}). A *non‑trivial* $k$-term arithmetic progression in $[N]$ means [ a,\ a+d,\ a+2d,\ \dots,\ a+(k-1)d ] with (d\neq 0) [[nomath]](so here $d\ge 1$)[[/nomath]].

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_142 (k : ℕ) : (fun N => (r k N : ℝ)) =Θ[atTop] (answer(sorry) : ℕ → ℝ)

formal-conjectures/142.lean ↗

oeis

A003002 — Size of the largest subset of the numbers [1...n] which does not contain a 3-term arithmetic progression.0,1,2,2,3,4,4,4,4,5,5,6,6,7,8,8,8,8,8,8,9,9,9,9,10,10,11,11,11,11,12,12,13,13,13,13,14,14,14,14,15,16,16,16,16,16,16,16,A003003 — Size of the largest subset of the numbers [1...n] which doesn't contain a 4-term arithmetic progression.1,2,3,3,4,5,5,6,7,8,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,17,17,18,18,18,19,20,20,20,21,21,21,22,22,22,23,23,24 A003004 — Size of the largest subset of the numbers [1..n] which does not contain a 5-term arithmetic progression.1,2,3,4,4,5,6,7,8,8,9,10,11,12,12,13,14,15,16,16,16,16,16,17,18,18,19,20,21,21,22,22,23,24,24,25,26,27,28,28,29,30,31,32 A003005 — Size of the largest subset of the numbers [1..n] which doesn't contain a 6-term arithmetic progression.1,2,3,4,5,5,6,7,8,9,9,10,11,12,13,13,14,15,16,17,17,18,19,20,21,22,22,22,23,23,23,24,25,25,26,27,28,28,29,30,31,31,31,32

links

#3If

A \subseteq N

has

\sum_{n \in A} \frac{1}{n} = \infty

then must

A

contain arbitrarily long arithmetic progressions?A003002 #139Let

r_{k} (N)

be the size of the largest subset of

{1, \dots, N}

which does not contain a non-trivial

k

-term arithmetic progression. Prove that

r_{k} (N) = o (N)

.A003002 #140Let

r_{3} (N)

be the size of the largest subset of

{1, \dots, N}

which does not contain a non-trivial

3

-term arithmetic progression. Prove that

r_{3} (N) ≪ N / (lo g N)^{C}

for every

C > 0

.A003002 #201Let

G_{k} (N)

be such that any set of

N

integers contains a subset of size at least

G_{k} (N)

which does not contain a

k

-term arithmetic progression. Determine the size of

G_{k} (N)

. How does it relate to

R_{k} (N)

, the size of the largest subset of

{1, \dots, N}

without a

k

-term arithmetic progression? Is it true that

N \to \infty lim \frac{R _{3} ( N )}{G _{3} ( N )} = 1 ?

A003002

status