Skip to content

Erdős Problem #271

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: additive combinatorics, arithmetic progressions.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

Fix an integer \(n\ge 1\). Start with \(a_0=0\) and \(a_1=n\). Having chosen \(a_0<a_1<\cdots<a_k\), choose \(a_{k+1}\) to be the least integer strictly larger than \(a_k\) for which the enlarged set contains no three-term arithmetic progression. Thus the normalized sequence is

\[ a_{k+1}=\min\{m\in\mathbb Z:m>a_k,\ \{a_0,\ldots,a_k,m\}\text{ contains no }x<y<z\text{ with }x+z=2y\}. \]

The question asks for an explicit description of \(a_k\) and for its growth as \(k\) tends to infinity. The quantifiers matter: the construction is a separate sequence for each fixed initial value \(n\), and the choice at every stage is the least admissible integer after the current maximum. It is not a choice from all positive integers, and it is not a question about merely finding some infinite progression-free set.

There is a material normalization exception. The maintained Erdős Problems entry for 271 says “least positive integer” but omits \(m>a_k\). Literally using that wording after \(0,4\) would choose \(1\), because the set containing \(0\), \(1\), and \(4\) has no three-term progression; that contradicts the required ordering. The original printed statement and Odlyzko–Stanley’s formulation both include the increasing condition, so this article uses the increasing version and preserves the live-page conflict rather than silently repairing it.

A small example

For \(n=4\), the beginning is

\[ A(4)=[0,4,5,7,11,12,16,23,26,31,33,37,38,44,49,56]. \]

The finite rule is easy to check exactly. Once \(m\) is larger than every selected term, adding \(m\) creates a progression precisely when two earlier terms \(x<y\) satisfy \(x+m=2y\). After \(0,4,5,7\) have been selected, \(8\) is rejected because \(0+8=2\cdot4\), \(9\) is rejected because \(5+9=2\cdot7\), and \(10\) is rejected in two ways, including \(4+10=2\cdot7\). Hence \(11\) is the next term.

The following integer-only calculation independently reproduces the displayed prefix; Python’s integers perform the equalities without rounding or probabilistic tests.

from itertools import combinations

def greedy(n, count):
    A = [0, n]
    while len(A) < count:
        m = A[-1] + 1
        while any(x + m == 2*y for x, y in combinations(A, 2)):
            m += 1
        A.append(m)
    return A

expected = [0, 4, 5, 7, 11, 12, 16, 23,
            26, 31, 33, 37, 38, 44, 49, 56]
assert greedy(4, 16) == expected
print(greedy(4, 16))

This is a finite verification of the recurrence, not evidence for a proposed asymptotic law. The same prefix appears in the inspected Odlyzko–Stanley paper, p. 1, and in the original Erdős–Graham discussion.

What is known

Erdős and Graham’s 1980 source places the problem on printed p. 22 and records the increasing greedy construction, including the special behavior for \(n=1\) and the difficulty of the \(n=4\) case. Odlyzko and Stanley, pp. 1–2, give exact ternary membership descriptions for \(n=3^r\) and \(n=2\cdot3^r\). For \(n=3^r\), their Theorem 1 characterizes membership by restrictions on ternary digits; Theorem 2 gives the analogous characterization for \(2\cdot3^r\). Their regular-case calculation yields the exponent \(\log 3/\log 2\) in the corresponding growth comparison.

For other initial values, Odlyzko–Stanley describe the behavior as irregular and use a probabilistic heuristic. On p. 3 they motivate a scale of the form \(a_k\) comparable to \(k^2/\log k\) for irregular cases. That is an empirical model, not a theorem. The maintained entry reports a related dichotomy and reports data for \(A(4)\), but the entry’s comments are not a substitute for a primary proof; the source audit specifically records the Lindhurst thesis as unavailable for direct inspection.

A proved general bound comes from Richard A. Moy, “On the Growth of the Counting Function of Stanley Sequences.” If \(A\) is any finite 3-free subset of the nonnegative integers and \(S(A,x)\) counts its greedy Stanley sequence up to \(x\), Theorem 1.1, p. 1, states that for every \(\varepsilon>0\),

\[ S(A,x)\ge (\sqrt{2}-\varepsilon)\sqrt{x} \]

for all sufficiently large \(x\). Applying this to \(\{0,n\}\) gives a quadratic-order upper bound on the inverse sequence: since \(a_k\le x\) exactly when \(S(A,x)\ge k+1\), one obtains \(a_k=O_n(k^2)\). This does not prove the explicit bound displayed on the maintained page, and it does not select between the regular and irregular asymptotic pictures.

GCL's current state

The authenticated GitHub identity used for the source audit is fyremael. The original MATH-PROGRAMME issue #1541 is the issue bound to ERDOS-CATALOGUE-0271-S01; its exact authenticated RESULT/1 source-audit comment has disposition STATUS_CONFLICT. That disposition is documentary evidence about source and status reconciliation, not a proof result.

The protected catalogue registry records issue 1541 with issue-body SHA-256 0ffdb3a24ca87307d359d253787f4a40c434101af084214ebf638b5578893d11, catalogue status open, triage class STATEMENT_CAPTURE_REQUIRED, and no protected Formal Conjectures statement. The pinned catalogue packet is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89; its 271 entry has Git blob 4e60263a80af6207aca494d2e1388e44fa372889 and packet SHA-256 be65b0db56fe13becec3178f2937685ee7e6a2f5df9325712474722c279c4182. It says open, unformalized, and formalized: no.

The exact fixed status is therefore: open, with a source-normalization conflict. It is not responsibly classifiable here as proved or disproved. At Formal Conjectures commit 85f863718beeec7b58a3a1926ee92e3472bc2020, no FormalConjectures/ErdosProblems/271.lean exists, so there is no problem-file hash, theorem, or replay to report. The inspected external MATHFORGE snapshot is commit ec80b855c988e8dc7ddff40cb892b67263d5c86e, with provider-manifest blob 5e74d0ceec81d313e9c858ec5bd4014fa543314f, composition blob bc0a92eeefc69e92a2e08c99f903b93f966257d8, and formal-shard blobs bde080f555ac1c07a6047fbab0137cd48d3a5cc3 and 49c3fc04c06cff45698dfd66b995020891aa3e4e; neither shard contains Problem 271.

What remains

The first unresolved obligation is semantic, not computational: the source packet must continue to distinguish the increasing recurrence from the live page’s incomplete wording. Any future proof or counterexample must state its indexing convention, its initial set, and the exact meaning of “least.” A result for a non-increasing greedy rule would not settle this problem.

The second obligation is mathematical. The explicit quadratic bound reported by the maintained entry and by unreviewed comments is

\[ a_k\le \frac{(k-1)(k+2)}{2}+n\qquad(k\ge 0). \]

It needs a primary proof with the zero-based conversion checked line by line. Moy’s Theorem 1.1 supplies the asymptotic counting lower bound, but the source audit correctly treats this stronger explicit formula as a proposed target rather than an accepted theorem. Lindhurst’s numerical evidence also remains unavailable for direct verification.

The third obligation is status review. The exact Formal Conjectures absence means there is no protected theorem statement to replay. A later Lean file, external proof repository, or self-reporting CI result would still require inspection of its hypotheses, definitions, dependencies, and kernel evidence. In particular, pinned Lean code containing sorry, an external proof repository, or a self-reported CI success cannot by itself certify the mathematics. The bounded next task is consequently to prove the explicit bound, find an exact counterexample, or isolate the first missing lemma; finite prefixes alone cannot decide the asymptotic question.

Sources and claim boundaries

  • P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, printed p. 22, inspected scan, retrieved PDF SHA-256 0cbf0c32f0ab1e1c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3.
  • A. M. Odlyzko and R. P. Stanley, “Some Curious Sequences Constructed with the Greedy Algorithm,” pp. 1–3, inspected paper, retrieved PDF SHA-256 3fcea97e6413eb1367ab091966fcf21e9df71aaa7b3b322407f4db773b210d5f.
  • Richard A. Moy, “On the Growth of the Counting Function of Stanley Sequences,” Theorem 1.1 p. 1 and Lemmas 2.1–2.4 pp. 2–3, arXiv source and paper, DOI 10.1016/j.disc.2010.12.019, retrieved PDF SHA-256 8e51b6bf14c361221ad13b5f4066b37990332579c659ace6bf334e5b770ac0df.
  • Pinned catalogue entry, maintained live entry, and the exact authenticated issue audit.

These sources support the normalized statement, the finite example, Moy’s counting theorem, and the carefully qualified historical claims above. They do not certify a complete solution of Problem 271. Editorial acceptance of this manuscript, if later considered, is determined by the protected V2 ledger; that documentary control is separate from mathematical certification.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1541 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction