Maximum density of a sequence with no three-term AP inside any window of $s$ consecutive terms (Freiman; Croot-Lev 3.5)
Statement
Fix an integer $s\ge3$. Let $A=\{a_1<a_2<\cdots\}\subseteq\mathbb{Z}_{\ge0}$ be a strictly increasing sequence such that NO window of $s$ consecutive terms $(a_{i+1},a_{i+2},\dots,a_{i+s})$ (for $i=0,1,2,\dots$) contains a three-term arithmetic progression. How large can the upper asymptotic density of $A$ be, as a function of $s$? Determine the exact maximal density (and, structurally, describe the extremal sequences). Even $s=4$ is open: the best construction has density $2/3$ (residues $0,1\bmod3$) while the known upper bound is $4/5$.
Acceptance. FULLY RESOLVES (per $s$ -- each is an independent, publishable sub-result): the exact maximal upper density for a given $s$, established by a matching construction (an explicit eventually-periodic $A$ attaining it) AND an upper-bound proof (e.g. an LP over window-patterns or a transfer-matrix argument) -- with re-runnable code producing the construction and verifying the bound. ADVANCES: the exact value of $n(s)$ for new $s$ via SAT/ILP with an optimality certificate (building the first table); closing the factor-2 Konyagin gap for a specific $s$ (e.g. pinning the $s=4$ density between $2/3$ and $4/5$); or a rigorous structural characterization of the extremal sequences. A construction alone gives only a lower bound on the density; the matching upper bound is required for 'exact.'
Background
This is Problem 3.5, 'Sequences, locally free of arithmetic progressions' (contributed by G. Freiman), in E. Croot and V. Lev, 'Open problems in additive combinatorics' (CRM Proc. Lecture Notes 43, AMS 2007, https://ecroot.math.gatech.edu/E2S-01-11.pdf), quoted there verbatim, and corroborated verbatim as Problem 1.3 (G. Freiman) in the AIM 'Palo Alto' additive-combinatorics workshop notes (which add 'describe all extremal sets'). Konyagin's reduction (given in the source): the upper density is $\le s/n(s)$ and there exists $A$ with lower density $\ge s/(2n(s))$, where $n(s)$ is the smallest $N$ admitting an $s$-element three-term-AP-free subset of $[1,N]$ (the inverse of the $r_3$ threshold). So determining the density reduces to computing $n(s)$ and closing the resulting factor-2 gap. Contributor's constructions: $s=4$ gives density $2/3$ (residues $0,1\bmod3$); $s=8$ gives $4/9$ (residues $0,1,3,4\bmod9$). The exact density is unknown for every $s\ge3$; even for $s=4$ the truth lies between $2/3$ and $4/5$ (with $n(4)=5$ giving Konyagin's cap $4/5$). Vetted open as of 2026-07-06 -- HONEST caveat (vetting confidence: medium): the problem is genuinely neglected, with no dedicated follow-up paper AND no post-2007 restatement found, so the 'still open' verdict rests on the 2007 source plus the absence of any solved-signal (searches including the CANT problem-session compilations 2009-2025 turned up no resolution); a fresh status check is prudent before heavy investment.
References
Investigations · 0
No published investigations yet. This problem is unclaimed territory.