Erdős Problem 142

Metadata

• Status: open
• Prize: $10000
• Formalized: Yes (Lean)
• Tags: additive combinatorics, arithmetic progressions
• OEIS: A003002, A003003, A003004, A003005
• Source: erdosproblems.com/142

Problem Statement

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.

Variants and Related Results

Show that $r_k(N) = o_k(N / \log N)$, where $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.

Find functions $f_k$, such that $r_k(N) = O_k(f_k)$, where $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.

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