Greedy pointwise-extension argument exploiting shared interior points of APs

Statement

Let $A=\{a_0<a_1<\cdots<a_k\}$ be a finite set of nonnegative integers containing no 3-term arithmetic progression (a 3-free set, equivalently a Salem–Spencer set). The greedy extension (or Stanley sequence) generated by $A$ is the infinite sequence $S(A)=(a_n)_{n\ge0}$ defined recursively: having fixed $a_0<\cdots<a_n$, let $$ a_{n+1} \;=\; \text{the smallest integer } >a_n \text{ such that } \{a_0,\ldots,a_n,a_{n+1}\}\text{ is still 3-free.} $$ (Odlyzko–Stanley 1978, unpublished Bell Labs memorandum, per Moy–Rolnick arXiv:1502.06013 Def. 1.1 and Rolnick arXiv:1408.1940 §1 — both fetched and read directly.)

The key mechanism — "interior point" language. Say an integer $x$ is covered by a set $S$ if there exist $s,t\in S$ with $s<t$ and $2t-s=x$; equivalently $s,t,x$ form a 3-term AP $s,t,x$ with $t$ as the shared interior (middle) point (Rolnick arXiv:1408.1940 §2, "we say an integer $x$ is covered by a set $S$ of integers if there exist $s,t\in S$ such that $s<t$ and $2t-s=x$"). Two sets $S,T$ jointly cover $x$ if $\exists s\in S,\,t\in T$ with $s<t$, $2t-s=x$ — i.e. the AP's shared interior point $t$ is drawn from a *different* already-built block than its outer point $s$. The Stanley sequence $S(A)$ is then *exactly* the unique increasing sequence extending $A$ such that every integer $x$ beyond $A$'s range lies in $S(A)$ iff it is not covered by $S(A)$ — the greedy rule is nothing but "extend by exactly the integers that no existing pair's shared interior point forces you to skip."

The reusable structural engine is the Cover-shift Lemma (Rolnick arXiv:1408.1940, Lemma 2.1, proved trivially but load-bearing throughout): if $x$ is jointly covered by $S$ and $T$, and $n_1\le n_2$ are integers, then $x+(2n_2-n_1)$ is jointly covered by $S+n_1$ and $T+n_2$. This says the "interior-point-covering" relation is *equivariant under independent translations of the two participating blocks* — which is exactly what licenses recursively translating and re-gluing whole blocks of the greedy sequence (doubling/tripling them, in the AP-free case) while keeping global 3-freeness automatic.

Facts

- Canonical example (the "digit trick"). $S(\{0\})=S(0)=0,1,3,4,9,10,12,13,27,\ldots$ — exactly the nonnegative integers with no digit $2$ in base 3 (Wikipedia "Stanley sequence"; Moy–Rolnick arXiv:1502.06013 §1). This is the lexicographically-first infinite 3-free sequence and directly witnesses the Erdős–Turán 1936 lower-bound exponent $n^{\log_3 2}$ for $r_3(n)$. - Type 1 / Type 2 growth dichotomy (Odlyzko–Stanley 1978 conjecture). Every Stanley sequence $(a_n)$ is conjectured to satisfy *either* $a_n=\Theta(n^{\log_2 3})$ (highly structured, "Type 1"/regular) *or* $a_n=\Theta(n^2/\log n)$ (chaotic, "Type 2"/irregular) — no intermediate growth rate is believed possible (arXiv:1502.06013 Conjecture 1.2, generalizing Rolnick's arXiv:1408.1940 Conjecture 1.1). This is erdos/271 in the Erdős–Graham problem list [ErGr80, p.22] (erdosproblems.com/271, fetched directly, confirmed status OPEN): "Can the $a_k$ be explicitly determined? How fast do they grow?" No sequence has ever been proved to have Type 2 growth, though $S(0,4)$ (OEIS A005487) is strongly conjectured to (Lindhurst 1990 senior thesis, numerically). A 2025 preprint (arXiv:2512.11983, "Irregular Stanley sequences plausibly do not have growth $\Theta(n^2/\log n)$") reports numerical evidence complicating even the *form* of the Type-2 conjecture. - Moy's upper bound. Every Stanley sequence satisfies $a_k\le(\tfrac12+\epsilon)k^2$ for all sufficiently large $k$, later made fully explicit as $a_k\le\frac{(k-1)(k+2)}{2}+n$ by van Doorn–Sothanaphan (Moy, *Discrete Math.* 311 (2011) 560–562; cited on erdosproblems.com/271, fetched directly). This solves "Problem 1" of Erdős–Lev–Rauzy–Sándor–Sárközy, *Discrete Math.* 200 (1999) 119–135 (the paper that coined "Stanley sequence" and generalized the $|A|=2$ case). - Independent / regular / modular / pseudomodular / basic hierarchy (Rolnick arXiv:1408.1940; Moy–Rolnick arXiv:1502.06013, both read in full). $S(A)$ is independent with character $\lambda$ if, for all large $k$ and $0\le i<2^k$: $a_{2^k+i}=a_{2^k}+a_i$ and $a_{2^k}=2a_{2^k-1}-\lambda+1$ — i.e. each successive *block* $\Gamma_k=\{a_i:2^k\le i<2^{k+1}\}$ is a literal translate of the previous prefix, glued on by "doubling and subtracting $\lambda-1$." Regular sequences generalize this by allowing the translated prefix to be some other independent sequence's terms (the *core*), with a *shift index* $\sigma$. Modular sequences (Moy–Rolnick, arXiv:1502.06013 Def. 2.2) further relax "block length a power of 2" to "block length a multiple $m$"; a set $A\subset\{0,\ldots,N-1\}$ is a modular set mod $N$ if it is 3-free mod $N$ and every non-member of $\{0,\ldots,N-1\}$ is covered by $A$ modulo $N$ (interior-point covering taken cyclically) — then $S(A)=A+N\cdot S(0)$ (Theorem 2.4). Basic sequences (§4) generalize $S(0)$'s base-3 digit trick to sums of subsets of an arbitrary basis $(b_k)$ with $b_k\to\alpha\cdot3^k$. - All independent/regular/modular/pseudomodular sequences provably have Type 1 growth $a_{2^k}=\alpha\cdot3^k$ (Rolnick, Prop. 2.4; Moy–Rolnick, Cor. 2.6) — this is the *positive* direction of Conjecture 1.2/erdos/271, fully proved for this entire well-structured family; only the converse ("irregular $\Rightarrow$ Type 2") and the classification of *all* Type-1 sequences as (pseudo)modular remain open (Moy–Rolnick Conjecture 3.4). - $\otimes_k$-product: given independent $S(A)$ and regular $S(B)$, with $A^*=\{a_0,\ldots,a_{2^k-1}\}$, the set $A\otimes_k B=\{a_{2^k}b+a : a\in A^*, b\in B\}$ yields a new regular $S(A\otimes_k B)=\{a_{2^k}b+a: a\in A^*, b\in S(B)\}$ with character $\lambda(A\otimes_kB)=a_{2^k}\lambda(B)+\lambda(A)$ (Rolnick, Theorem 1.3). This operation is associative and is the main engine for manufacturing new well-structured sequences from old ones (e.g. it shows infinitely many characters $\lambda\ge0$, $\lambda\notin\{1,3,5,9,11,15\}$, are achievable — Rolnick Conjecture 2.15 / Corollary 4.5). - Deletability / non-maximality (2014 surprise). Contrary to the tacit assumption in the founding papers (Erdős et al. 1999; Moy 2011) that Stanley sequences are *maximal* 3-free sets, Rolnick showed certain elements of dependent (regular, non-independent) sequences can be deleted while the remaining set is still a valid Stanley sequence — e.g. removing $11$ from $S(0,1,4)=0,1,4,5,11,12,14,15,31,\ldots$ yields another valid, dependent Stanley sequence with shift index $\sigma=1$ (arXiv:1408.1940, Example 4.6, Conjecture 4.7). - Generalization to $p$-term APs. For any odd prime $p$, the same recursion with "3-free" replaced by "$p$-free" (no $p$-term AP) defines $p$-Stanley sequences $S_p(A)$; $S_p(0)$ consists exactly of integers with no digit $p-1$ in base $p$ (Moy–Rolnick arXiv:1502.06013, Definition 6.1, Lemma 6.4 — this is the object motivating Szekeres's original 1936 conjecture on $r_p(n)$).

Technique

WHY it works (the mechanism). The greedy rule "add the next number iff no existing pair's *interior point* forces it to be skipped" converts the *global*, seemingly unbounded search for a 3-free (or $p$-free) sequence into a *local, deterministic, one-step-at-a-time* decision: at each step, exactly one set of "forbidden next values" (the covered integers) is computable from the current finite prefix, and the next allowed value is simply the smallest integer past the frontier not in that forbidden set. Because "interior point" is a symmetric relation on pairs already placed, tracking which integers are covered reduces to tracking two numbers per pair $(s,t)$ — this is why the whole apparatus (covered/jointly-covered sets, the omitted set $O(A)$, its max $\omega(A)$) stays *finite and computable* at every step, even though the sequence itself is infinite.

The Cover-shift Lemma is the reason this local rule produces *global, self-similar structure* for well-chosen seeds $A$: because covering is equivariant under independently translating the two participating blocks ($x$ jointly covered by $S,T$ $\Rightarrow$ $x+(2n_2-n_1)$ jointly covered by $S+n_1,T+n_2$), one can *predict*, without re-running the greedy search, exactly which integers the next translated copy of a block will cover — turning an a priori sequential greedy process into a *closed-form recursive doubling/tripling* ($a_{2^{k+1}}\approx 3a_{2^k}$ for independent sequences). This is precisely why $S(0)$ has the clean "digits $0,1$ in base 3" description: successive blocks are literal, predictable translates, each one landing in the gap the previous block's interior-point-covering left free.

HOW it is used to prove things (recombination steps)

1. Seed a 3-free (or $p$-free) set $A$ and run the recursive greedy rule (Definition 1.1) to get $S(A)$; this alone already proves *existence* of an infinite 3-free extension of any finite 3-free set — the technique's most basic payoff, underlying every explicit lower-bound construction for $r_3(n)$/$r_p(n)$ built this way (Szekeres's original motivating heuristic, Erdős–Turán 1936). 2. Compute the covered/omitted sets explicitly for small seeds ($O(A)$, its bound $\omega(A)$) to certify short-range structure, then look for periodicity or self-similarity (independence: $a_{2^k+i}=a_{2^k}+a_i$) — this is the step that upgrades "we have *a* sequence" to "we have a *closed form*," and is checked via Proposition 2.3 in arXiv:1408.1940: independence at *one* sufficiently large $k$ (with an explicit inequality $a_{2^k-1}\ge\lambda+\omega$) propagates to *all* larger $k$ by the Cover-shift Lemma — turning an infinite verification into a finite one. 3. Combine known well-structured sequences via $\otimes_k$ (Theorem 1.3) or via the basis/digit generalization (§4 of arXiv:1502.06013) to manufacture *new* explicit, closed-form 3-free sequences with prescribed properties — e.g. arbitrarily large characters (Corollary 4.5), arbitrarily large gaps between consecutive terms $\liminf(a_{n+1}-a_n)=\infty$ (arXiv:1502.06013, Corollary 5.2, via the modular set $A_m$ built by induction with base $29$), or sequences answering specific structural questions of Erdős et al. [ErLeRaSaSa99]. 4. Translate a block and recompute (the "shifted Stanley sequence" $S_k(c,A)$): pick a regular $S(A)$, translate one block by a constant $c$ in the valid range $\lambda\le c\le a_{2^k-2\ell}-\lambda$ (Theorem 1.5), and recompute — this produces new *dependent* sequences with the original as their *core*, again licensed entirely by the Cover-shift Lemma tracking how the interior-point-covering set moves under the translation. 5. When it applies vs. doesn't: the technique applies whenever a problem reduces to *"greedily/maximally extend a progression-avoiding (or similarly pairwise-constrained) set of integers, one element at a time, by a locally-checkable rule keyed to arithmetic-mean/interior-point relations."* It is the right tool for constructive lower bounds on progression-free set sizes and for producing explicit self-similar/periodic examples with prescribed asymptotic behavior. It is *not* by itself a tool for proving upper bounds (Roth/Behrend-type density bounds come from Fourier-analytic or polynomial methods — see Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt), Entropy-inequality method (Katz–Tardos): Shannon-entropy linear programming for the sums-and-entries / distinct-distances problem) nor for resolving the still-open Type 1/Type 2 dichotomy itself (erdos/271): the greedy machinery proves *sufficient* conditions for Type 1 growth (independence/regularity/modularity) but gives no way yet to certify that a *given* irregular-looking sequence (e.g. $S(0,4)$) truly has Type 2 growth — that direction remains conjectural even after 45+ years.

Related

- erdos/271 — the Odlyzko–Stanley/Erdős–Graham growth-rate problem for Stanley sequences [ErGr80, p.22]: OPEN. The greedy pointwise-extension argument is the *definition* of the object this problem asks about, and everything in "Facts" above (Moy's upper bound, the independent/regular/modular hierarchy, all proven Type-1 results) is partial progress toward it. - The alteration (deletion) method — probabilistic existence proofs that build an almost-good random structure, then delete its blemishes; canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs and other probabilistic-construction concepts — a contrasting family of techniques for building progression-free (or similarly constrained) sets *non-constructively*, via random deletion/alteration, rather than by a deterministic greedy interior-point rule; useful to compare when a problem could go either route. - Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt), Entropy-inequality method (Katz–Tardos): Shannon-entropy linear programming for the sums-and-entries / distinct-distances problem — the *upper-bound* toolkit for $r_3(n)$/$r_k(n)$ (Roth, Bloom–Sisask, Kelley–Meka, Croot–Lev–Pach/polynomial method), structurally unrelated to the greedy construction but answering the complementary question about the same objects. - Finite-field / projective-plane constructions for extremal additive sets — another explicit-construction family (algebraic rather than greedy/digit-based); contrast with the base-3/base-$p$ digit description of $S(0)$ and $S_p(0)$ here, which is combinatorial/arithmetic rather than algebraic. - Cover-shift Lemma (Rolnick, arXiv:1408.1940, Lemma 2.1) — the specific reusable equivariance lemma that makes "shared interior points of APs" a *transportable* structural fact under translation, and is the technical core enabling every closed-form/self-similarity result in this family (independent, regular, modular, pseudomodular, basic sequences; the $\otimes_k$-product; the shifted-sequence construction).