Skip to content

Erdős Problem #195

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

A permutation of \(\mathbb Z\) is a sequence listing every integer exactly once. It may be indexed one-sidedly by the positive integers; the ordering of the listed values, not their ordinary numerical order, determines whether a progression is monotone.

A monotone \(k\) term arithmetic progression is a subsequence appearing from left to right whose values form either an increasing or decreasing arithmetic progression of nonzero common difference. Erdős and Graham asked for the largest \(k\) for which every such permutation must contain a monotone \(k\) term progression.

A small example

The list \(3,1,2,4\) contains the numerical arithmetic progression \(1,2,3\) as a set, but those values occur in the list in the order \(3,1,2\), which is not monotone. Counting a progression without checking the relative positions of its values would give false positives.

For a finite permutation, test each set of \(k\) distinct values in arithmetic progression and check whether its positions are strictly increasing or strictly decreasing as the values run in numerical order. Larger monotone progressions automatically contain shorter ones.

What is known

The exact largest forced \(k\) remains OPEN, with the current bound \(3\le k\le4\). Davis, Entringer, Graham and Simmons (1977) proved that no permutation of the positive integers can avoid monotone three-term progressions. This also forces a three-term progression in a permutation of all integers: restricting its order to the positive entries gives a positive-integer permutation.

Geneson (2019) constructed a permutation of \(\mathbb Z\) avoiding six-term monotone progressions, showing the largest forced length is at most five. Sarosh Adenwalla, Avoiding monotone arithmetic progressions in permutations of integers, Discrete Mathematics 347 (2024), 114183, constructed a permutation avoiding five-term progressions. Thus the upper bound is now four.

The existence of a one-sided permutation of all integers avoiding four-term progressions remains a separate question from #196 about positive integers. Ho's September 2026 solution to #196 constructs a permutation only of positive integers and does not automatically supply a permutation of all integers.

GCL's current state

The pinned and maintained #195 classify the exact threshold OPEN. Original task: #1464. The 2024 published construction and its distinction between ambient integer sets were checked; its complete proof was not reproduced.

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 successor constructs and independently validates finite permutations of signed intervals avoiding monotone three- and four-term progressions. Acceptance: check both orientations in the position order, reject repeated elements, and show that a positive-integer permutation witness cannot be silently extended to all integers. Stop at finite semantics; the remaining infinite-four-term question is not settled by enumeration.

Sources and claim boundaries

No new four-term theorem or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1464 — 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