Problem 817

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?

Source: erdosproblems.com/817

Additive combinatorics

Wiki page

Status

Open

No claim settles this problem.

Open. The site's label was OPEN on 2026-09-18, 2026-10-06 and 2026-10-07. Source-supported bounds: for $k=3$ ,

\Bigl(\frac{\sqrt3}{2\sqrt\pi}+o(1)\Bigr)\frac{3^n}{\sqrt n}\ \le\ g_3(n)\ \le\ 3^{n-1},

the lower bound Theorem 1.1 (Korsky 2026) of Korsky [Ko26] (arXiv:2606.24139v1, June 2026, a preprint), recorded as the claimed partial claim Korsky's bounds, sharpening Erdős and Sárközy's $g_3(n)\gg3^n/n^{O(1)}$ (the site's wording; the paper's Theorem 4, p. 251, on $K(N)$ , whose p. 261 argument gives $g_3(n)\gg3^n/n$ ), recorded as the accepted partial claim Erdős and Sárközy's lower bound on the refereed paper; for fixed $k\ge4$ , $\liminf g_k(n)^{1/n}\ge(k-1)/(k-2)$ and $\limsup g_k(n)^{1/n}\le\min_pp^{2/(\min\{p,k\}-1)}$ (Theorems 1.2 and 1.3 of [Ko26], on Korsky's claim page). The displayed question $g_3(n)\gg3^n$ has a claimed negative answer: a four-page preprint of September 2026 [Co26] (Zenodo, 5 September 2026; arXiv:2609.06303v1, 5 September 2026) proves, if correct, $\liminf_{n\to\infty}g_3(n)/3^n=0$ , from Korsky's Corollary 4.2 and a consequence of the construction, credited by the site to GPT-6 Astra run by Epoch AI, that disproved Problem 1; its acknowledgments declare the use of ChatGPT (OpenAI, GPT-5.6 Sol) in finding, checking and revising the argument. The claim is on the site's proof-claim tab (submitted 2026-09-05 01:48:23, labeled full on 2026-09-05 and partial from 2026-09-06, when the site's moderator relabeled it and called its scope debatable); the site's label was OPEN on 2026-10-07 and its commentary does not adopt the claim; no refereed version, independent review or citing paper beyond the thread was found. The claim has its own page, Costa's negative answer, a partial claim with status claimed: if correct it settles the displayed question and leaves the estimate open. For the estimate, this is a bounded negative finding, not a certificate of openness.

Er91: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397--406. Not held; the site's key.
ErSa92: Erdős, P. and Sárközy, A., Arithmetic progressions in subset sums. Discrete Math. 102 (1992), no. 3, 249--264, DOI 10.1016/0012-365x(92)90119-z; the publisher's open-archive scan is the edition cited, by printed page. Definitions, p. 249 and p. 251; Theorem 4, p. 251; the remark on the $\log\log N$ gap, p. 252; the proof of Theorem 4, pp. 258--261, with the interval argument on p. 261. The paper [Ko26] (its [10]) and [Co26] (its [5]) cite it for the bound $g_3(n)\gg3^n/n^{O(1)}$ . Library home: Erdős and Sárközy 1992.
Ko26: Korsky, S., Arithmetic progression-free subset-sum sets. arXiv:2606.24139v1 (23 June 2026), 15 pp. Theorems 1.1--1.2, p. 2; Theorem 1.3 and Corollary 1.4, p. 3; Proposition 4.1 and Corollary 4.2, p. 6; Remark 4.6, p. 8. Library home: Korsky 2026.
Co26: Costa, S., A negative answer to the Erdős--Sárkőzy question. Preprint, Zenodo record 22313501, DOI 10.5281/zenodo.22313501 (publication date 2026-09-05; 4 pp.; the record's single PDF, not filed in the library), also arXiv:2609.06303v1 (5 September 2026). Theorem 1.1 and Corollary 1.2, p. 2; Propositions 2.1--2.2, p. 2; the proof, p. 3; the acknowledgments declaring AI assistance, p. 4. The record's second version (DOI 10.5281/zenodo.22638810, published 2026-09-07) adds a Lean archive beside the PDF; the corpus holds no copy of the archive.
Du26: Dutta, S., The greedy algorithm for dissociated sets. arXiv:2601.07068 (2026); [Co26]'s [4], giving a weaker $3^n/\sqrt n$ bound with constant $\sqrt3/(4\sqrt\pi)$ per [Co26], p. 1. Not held.
Ba02: Bae, J., On generalized subset-sum-distinct sequences. Int. J. Pure Appl. Math. 1 (2002), 335--343; [Co26]'s [1], the term "2-fold subset-sum-distinct". Not held.

Problem 817

Status

Proof claims

Discussion