Asymptotic Enumeration of Arithmetic-Progression-Free Sets

Definitions and mathematical statement

For integers $n\geq 1$, let $[n]=\{1,\ldots,n\}$. For an integer $k\geq 3$, a nontrivial $k$-term arithmetic progression in $[n]$ is a set \[ \{a,a+d,\ldots,a+(k-1)d\}, \qquad a,d\in{\mathbb{Z}},\quad a\geq1,\quad d\geq1,\quad a+(k-1)d\leq n. \] Here the conventional interpretation of arithmetic progressions with distinct terms is used; the supplied statement does not explicitly specify nontriviality. A subset of $[n]$ is $k$-term-AP-free if it contains no such progression. Define \[ \mathcal F_k(n)=\{A\subseteq[n]:A\text{ is }k\text{-term-AP-free}\}, \qquad r_k(n)=\max_{A\in\mathcal F_k(n)}|A|. \] The enumeration includes every such subset, including the empty set.

The question is whether, for every fixed integer $k\geq3$, \[ |\mathcal F_k(n)|=2^{(1+o(1))r_k(n)} \qquad\text{as }n\to\infty \] holds along positive integers $n$. Equivalently, is \[ \lim_{n\to\infty}\frac{\log_2|\mathcal F_k(n)|}{r_k(n)}=1 \qquad\text{for every fixed integer }k\geq3? \] The error term may depend on $k$; no uniformity for growing $k$ is requested.

The supplied record labels this question open and its statement corrected_verified; these are supplied curation labels, not independent verification. Its literature assessment concerns bounds for $r_3(n)$, rather than directly establishing the status of this enumeration question. The report-year discrepancy described in the Sources also remains unresolved.

Short English statement

For each fixed integer $k\geq3$, count all subsets of $\{1,\ldots,n\}$ containing no nontrivial $k$-term arithmetic progression. Is the base-two logarithm of this count asymptotic to the largest possible size $r_k(n)$ of such a subset? The supplied open status requires independent review.

Sources

• Local UnsolvedMath registry, supplied record with permanent ID $30003137$, source problem code catalogue entry, title Asymptotic Enumeration of Arithmetic-Progression-Free Sets, in the Oberwolfach Reports Open Problems collection. The record gives proposed year 2016 and names no individual proposer.
• Supplied report citation: Combinatorics and Probability (2017), Oberwolfach Reports, DOI 10.4171/owr/2016/22, pp. 1189--1257. https://doi.org/10.4171/owr/2016/22. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. The citation's 2017 label differs from the 2016 proposed year and the year embedded in the DOI; this discrepancy has not been resolved.
• Supplied statement-verification note: the statement was checked against the official Oberwolfach report and preserves its hypotheses, notation, and open mathematical target. This is a claim in the supplied record; no independent source consultation is asserted here.
• Kelley and Meka, Strong Bounds for 3-Progressions. https://arxiv.org/abs/2302.05537.
• Bloom and Sisask, Improvement to the Kelley--Meka Bounds. https://arxiv.org/abs/2309.02353.
• Literature assessment dated exactly 2026-08-21: supplied dated curation, not independently verified. It labels the status open and states that the exact growth of $r_3(n)$ remains unknown despite major improvements, with Kelley--Meka and Bloom--Sisask upper bounds still not matching Behrend-type lower bounds. The background explicitly describes this as dated literature triage derived from the supplied OWR curation and requests independent verification of time-sensitive status and cited claims. This assessment addresses the extremal function and does not itself verify the status of the enumeration question.