OPEN
This is open, and cannot be resolved with a finite computation.
Let $k\geq 3$ and $f(k)$ be the supremum of $\sum_{n\in A}\frac{1}{n}$ as $A$ ranges over all sets of positive integers which do not contain a $k$-term arithmetic progression. Estimate $f(k)$.
Is\[\lim_{k\to \infty}\frac{f(k)}{\log W(k)}=\infty\]where $W(k)$ is the van der Waerden number?
Berlekamp
[Be68] proved $f(k) \geq \frac{\log 2}{2}k$. Gerver
[Ge77] proved\[f(k) \geq (1-o(1))k\log k.\]It is trivial that\[\frac{f(k)}{\log W(k)}\geq \frac{1}{2},\]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\[\sum_{n\in A}\frac{1}{n}\geq f(k)-\epsilon.\]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$.
View the LaTeX source
This page was last edited 04 April 2026. View history
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #169, https://www.erdosproblems.com/169, accessed 2026-04-11
