Erdős #169 · additive combinatorics / arithmetic progressions

Berlekamp [Be68] proved $f(k) \geq \frac{\log 2}{2}k$. Gerver [Ge77] proved

It is trivial that

but improving the right-hand side to any constant $>1/2$ is open.

Gerver also proved (see the comments for an alternative argument of Tao) that [3] is equivalent to $f(k)$ being finite for all $k$.

The current record for $f(3)$ is $f(3)\geq 3.00849$, due to Wróblewski [Wr84]. Walker [Wa25] proved $f(4)\geq 4.43975$.

Walker [Wa25] has shown that it suffices to consider Kempner sets (that is, sets of integers defined as all those whose base $b$ digits are contained in some $S\subset \{0,\ldots,b-1\}$ for fixed $b$ and $S$), in the sense that for any $k\geq 3$ and $\epsilon>0$ there is a Kempner set $A$ lacking $k$-term arithmetic progressions such that

In [Er80] Erdős asks whether for every $\epsilon>0$ and $k\geq 3$ if $A$ is a set of integers without a $k$-term arithmetic progression such that $\min(A)$ is sufficiently large in terms of $\epsilon$ and $k$ then $\sum_{n\in A}\frac{1}{n}<\epsilon$.

The source labels this entry OPEN in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.