Subset sums with no $k$-term arithmetic progression: is $g_3(n)\gg 3^n$? (Erdős #817)
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 the set of subset sums $$\langle A\rangle = \left\{\sum_{a\in A}\epsilon_a a: \epsilon_a\in \{0,1\}\right\}$$ contains no non-trivial $k$-term arithmetic progression (non-trivial meaning the common difference is nonzero, i.e. the $k$ terms are distinct). Estimate $g_k(n)$. In particular, is it true that $$g_3(n) \gg 3^n?$$
Acceptance. FULLY RESOLVES: a complete proof that $g_3(n) \gg 3^n$ (no polynomial losses), or a disproof — a construction of $n$-element sets $A\subseteq\{1,\ldots,N\}$ with 3-AP-free subset-sum sets and $N=o(3^n)$ (equivalently $g_3(n)=o(3^n)$), with proof. Machine-checkable (Lean/Coq) proof preferred; otherwise a complete written proof with all steps. ADVANCES: (a) an improved lower bound on $g_3(n)$ reducing the polynomial loss stated in the background (e.g. $3^n/n^{o(1)}$ or an explicit small power), with full proof; (b) nontrivial upper or lower bounds on $g_k(n)$ for some $k>3$ beyond what the background states, with proof; (c) exact values of $g_3(n)$ for small $n$ via reproducible exhaustive search with an exhaustiveness certificate, plus the extremal witness sets $A$; (d) a Lean formalization of the Erdős–Sárközy lower bound compatible with the existing formalized statement. Deliver the proof file, or the construction + verification, or the search code + table of exact values and witnesses.
Background
A problem of Erdős and Sárközy, appearing in [Er91]; listed as open on erdosproblems.com/817 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics'). Erdős and Sárközy proved the lower bound $$g_3(n) \gg \frac{3^n}{n^{O(1)}},$$ so the question is whether the polynomial losses can be removed. A June 2026 preprint of Korsky sharpens the lower bound to $$g_3(n) \geq \left(\tfrac{\sqrt{3}}{2\sqrt{\pi}}+o(1)\right)\frac{3^n}{\sqrt{n}},$$ cutting the loss to a single factor $n^{1/2}$ but still short of the conjectured $\gg 3^n$. For orientation on the other side, the classical powers-of-3 construction gives a matching-order upper bound: with $A=\{1,3,9,\ldots,3^{n-1}\}$ the subset sums are exactly the integers whose ternary digits are all $0$ or $1$, and a carry-free digit argument shows this set has no non-trivial 3-term arithmetic progression, whence $g_3(n)\leq 3^{n-1}$. Thus $g_3(n)$ is pinned between $3^n/n^{O(1)}$ and $3^{n-1}$, and the conjecture asserts the exponential rate is exactly $3^n$ up to constants. For $k>3$ the estimation of $g_k(n)$ is wide open. The statement has been formalized in Lean in the google-deepmind/formal-conjectures repository. The attacker's tools: exact computation of $g_3(n)$ (and $g_k(n)$) for small $n$ by exhaustive or SAT-driven search over $A\subseteq\{1,\ldots,N\}$ with AP-freeness checking of the $2^n$ subset sums, to test sharpness of the constants; and tightening the Erdős–Sárközy argument to remove the polynomial factor.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #817 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of the statement (google-deepmind/formal-conjectures) | website |
| REF-03 | S. Korsky, Arithmetic Progression-Free Subset-Sum Sets (2026) — sharpens the $g_3(n)$ lower bound to $\gg 3^n/\sqrt{n}$ | paper |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.