Open-access mathematical research insights
About Contact
Home / Erdos Problems / Problem #817

Problem #817: Let $k\geq 3$ and define $g_k(n)$ to be the minimal $N$...

Let $k\geq 3$ and define $g_k(n)$ to be the minimal $N$ such that $\{1,\ldots,N\}$ contains some $A$ of size $\lvert A\rvert=n$ such that\[\langle...

Problem Statement

Let $k\geq 3$ and define $g_k(n)$ to be the minimal $N$ such that $\{1,\ldots,N\}$ contains some $A$ of size $\lvert A\rvert=n$ such that\[\langle A\rangle = \left\{\sum_{a\in A}\epsilon_aa: \epsilon_a\in \{0,1\}\right\}\]contains no non-trivial $k$-term arithmetic progression. Estimate $g_k(n)$. In particular, is it true that\[g_3(n) \gg 3^n?\]
Categories: Additive Combinatorics

Progress

A problem of Erdős and Sárközy who proved\[g_3(n) \gg \frac{3^n}{n^{O(1)}}.\]

Source: erdosproblems.com/817 | Last verified: January 16, 2026

Stay Updated

Get weekly digests of new research insights delivered to your inbox.