Skip to content

Erdős Problem #196

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: 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

Does every permutation of the positive integers contain a monotone four-term arithmetic progression? This is a subsequence \(a_i,a_j,a_k,a_l\) whose indices satisfy \(i<j<k<l\) and whose values form an arithmetic progression in either direction, with nonzero common difference.

Erdős and Graham asked whether the answer was yes. To refute this, one must construct one permutation of all positive integers containing no such four-term subsequence. A long finite prefix avoiding progressions is not enough.

A small example

In the finite list \(3,1,2,4\), the set of numbers \(1,2,3,4\) is an arithmetic progression, but it appears in the order \(3,1,2,4\), so it is not monotone. A candidate infinite construction must prevent this for all possible four-term progressions, including negative common differences and progressions whose indices are far apart.

For a finite prefix of an injective sequence, enumerate all index quadruples \(i<j<k<l\) and reject if \(a_i+a_k=2a_j\) and \(a_j+a_l=2a_k\) with the entries distinct. The two equalities encode a four-term progression without floating-point arithmetic.

What is known

DISPROVED in September 2026. Boon Suan Ho, A 4AP-free permutation of the positive integers, submitted 11 September 2026, constructs a permutation with no monotone four-term arithmetic progression. The author's Lean 4 formalization and executable Python implementation explicitly verify the existence theorem and the permutation's bijectivity.

An independent later construction and Lean formalization appeared on 14 September 2026, and its publication note recognizes Ho's priority. Conjectures.io separately reports a verified counterexample for the equivalent nonnegative-integer formulation, but its Lean verification and review are external, not GCL protected admission.

The maintained Erdős #196 page and pinned August 2025 task classify the question OPEN because they have not incorporated this September 2026 development. This is a dated status drift, not permission to rewrite the protected source lock. The original 1977 Davis–Entringer–Graham–Simmons results proved three-term necessity but only avoided five-term progressions.

GCL's current state

Original issue: #1465. Record PINNED OPEN / PRIMARY 2026 DISPROVED. The public preprint, formal source and its authorship were inspected, but the GCL toolchain has not independently kernel-checked the exact pinned theorem. Do not claim a new GCL solution or transfer the positive-integer disproof to #195 on all integers.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded task runs Ho's named Python implementation on its first 256 outputs, verifies distinctness and the forbidden-quadruple predicate, then matches its recursion against the fixed Lean commit and checks the exact nonnegative versus positive-integer shift. Acceptance: no repeated values or monotone four-term progression in the fixture, successful exact Lean build with an axiom audit, and a statement-level comparison to the historical conjecture. Stop without treating finite tests as a proof.

Sources and claim boundaries

No independent Lean certification, priority claim or protected editorial admission is made.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1465 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • Formal-statement coverage: A provider statement was included in the pinned 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