Problem 142 — Visual explainer (undergrad)
==========================================

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

Picture
-------
Number line picture of an arithmetic progression (equal spacing):

---o-----o-----o-----o-----o---
   a    a+d   a+2d  a+3d  a+4d

Conjecture / Task: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Context
-------
Area hint: additive combinatorics / additive number theory.

Benchmarks / known results (from comments)
----------------------------------------
- In Erd\H{o}s offered \$1000, but given that he elsewhere offered \$5000 just
  for (essentially) showing that $r_k(N)=o_k(N/\log N)$, that value seems odd.
- In he offers \$10000, stating it is 'probably enormously
  difficult'.<br><br>The best known upper bounds for $r_k(N)$ are due to
  Kelley and Meka for $k=3$, Green and Tao for $k=4$, and Leng, Sah, and
  Sawhney for $k\geq 5$.
- An asymptotic formula is still far out of reach, even for $k=3$.