Skip to content

Erdős Problem #197

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

Can the positive integers be partitioned into two disjoint subsets \(A\) and \(B\) so that each subset admits an enumeration avoiding all monotone three-term arithmetic progressions? Each enumeration may have its own order. A monotone triple means three numbers \(a,a+d,a+2d\) with \(d\ne0\) that appear in increasing or decreasing numerical order within the chosen enumeration.

This is a simultaneous partition-and-ordering problem. It is not asking for one permutation of the whole of \(\mathbb N\), which is known to force a monotone triple.

A small example

The ordering \(2,1,3\) of the set \(\{1,2,3\}\) avoids a monotone three-term progression, even though the set contains \(1,2,3\) as an arithmetic progression. In a partition problem, a simple way to avoid false conclusions is first to specify the two disjoint sets and then list the independent orders of the elements in each part.

Finite experiments are easy to satisfy and can be misleading. For every finite interval there are permutations avoiding monotone three-term progressions, but they need not form compatible initial segments of infinite permutations.

What is known

The two-set partition conjecture remains OPEN. The original Erdős–Graham formulation and maintained #197 state that three subsets suffice. Hence the issue is the exact number of parts: whether three can be improved to two. Davis, Entringer, Graham and Simmons (1977) showed that the whole positive integers cannot be permuted to avoid monotone three-term arithmetic progressions.

Sarosh Adenwalla's Avoiding monotone arithmetic progressions in permutations of integers, published in Discrete Mathematics (2024), studies related permutation and density restrictions, and explicitly identifies this partition question as unresolved. His constructions for avoiding four- or five-term progressions do not resolve the two-part avoidance of three-term progressions.

A permutation of \(\mathbb Z\) or the rationals need not restrict to a partition of \(\mathbb N\) with the exact two-set condition. No full construction or obstruction for two sets is established by the sources inspected.

GCL's current state

The pinned and maintained Erdős #197 label it OPEN. Original issue: #1466. The protected source lock lacks a matched formal statement, and the three-part positive example is source-attributed rather than independently proven here.

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 uses constraint programming to partition \(\{1,\ldots,N\}\) into two parts and find an ordering of each avoiding monotone three-term progressions. Acceptance: a certificate includes the partition, two exact permutations and an exhaustive triple test; every element appears exactly once. Compare with a three-part fixture. Stop at finite \(N\); even success for large finite instances does not certify an infinite partition.

Sources and claim boundaries

No infinite two-part partition, new impossibility theorem or editorial admission is claimed.

Catalogue and evidence provenance

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