Skip to content

Erdős Problem #194

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (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

An ordering of the real numbers is an arbitrary linear order \(\prec\) on \(\mathbb R\), not necessarily the usual numerical order. A monotone three-term arithmetic progression is a triple of distinct reals \(a,a+d,a+2d\), with nonzero real \(d\), that appears in the same or reverse order under \(\prec\) as it does numerically.

Erdős and Graham asked whether every linear ordering of \(\mathbb R\) must contain such a progression of some length \(k\ge3\). A single linear order avoiding all monotone three-term progressions would refute every longer forced-length assertion.

A small example

The usual order of the reals has progressions everywhere. In contrast, for the three numbers \(1,2,3\), an order placing \(2\) first and then \(1,3\) prevents those particular points from appearing monotonically. Reordering just one triple does not solve the whole problem: the ordering must cover uncountably many reals and block every arithmetic triple.

A sequence or permutation of \(\mathbb Z\) is not the same object as a linear order on \(\mathbb R\). Extensions from rational to real orders require explicit construction rather than assuming countable and uncountable cases coincide.

What is known

DISPROVED. Hayri Ardal, Tom Brown and Veselin Jungić, Chaotic Orderings of the Rationals and Reals, American Mathematical Monthly 118 (2011), 921–925, construct a linear ordering of all real numbers containing no monotone three-term arithmetic progression. Their primary published abstract explicitly identifies the Erdős–Graham conjecture and its negative answer.

The argument builds on orderings of the rationals and their extension to \(\mathbb R\); it is not simply a permutation of a finite interval. If there is no monotone three-term progression, then there can be no monotone progression of any longer length, since consecutive three members of a longer progression form a forbidden triple.

GCL's current state

Pinned and maintained Erdős #194 classify the assertion DISPROVED. Original issue: #1463. The 2011 journal abstract and bibliographic details were verified. The full transfinite ordering construction was not independently reconstructed and no protected Lean certification is claimed.

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 enumerates all orderings of \(\{1,\ldots,8\}\), checks exact nonzero-difference arithmetic triples, and finds orderings avoiding monotone triples. Acceptance: the checker treats increasing and decreasing numerical progressions symmetrically, and distinguishes the constructed total order from the usual order. Separately formalize the extension mechanism in the published paper with its choice assumptions; stop before presenting finite avoidance as a proof for \(\mathbb R\).

Sources and claim boundaries

No new ordering construction, independent full proof verification or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1463 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • 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