✦ 5 frontiers

read-only vieweressays

erdős #140

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

Let $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$ .

Worked, still open.

additive combinatorics · solved · prize $500 · 0 attempts

use this record

vela registry pull vfr_37aec80d874a0239

vela reproduce examples/erdos-problems

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,

links

Create a formalisation here · link

A \subseteq N

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

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 #142Let

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)

.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}

k

-term arithmetic progression? Is it true that

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

status

solved

finding.noted · reviewer:will-blair · 1 day

renders the record as of vev_d199cb2e · 1,338 events · hub