Partition $\mathbb{N}$ into two sets, each permutable to avoid monotone 3-term APs (Erdős #197)
Statement
Can $\mathbb{N}$ be partitioned into two sets, each of which can be permuted to avoid monotone 3-term arithmetic progressions? Here a set $A\subseteq\mathbb{N}$ 'can be permuted to avoid monotone 3-term APs' means: the elements of $A$ can be arranged in a sequence $a_1,a_2,a_3,\ldots$ (each element appearing exactly once) such that there are no indices $i<j<k$ or $i>j>k$ with $a_i,a_j,a_k$ an arithmetic progression in that order.
Acceptance. FULLY RESOLVES: either (a) an explicit partition $\mathbb{N}=A\sqcup B$ together with explicit orderings of $A$ and of $B$ (finitely described: formulas or recursions) and a proof that neither ordering contains a monotone 3-term arithmetic progression — machine-checkable (Lean/Coq) preferred, and the formal-conjectures Lean statement can host it; or (b) a proof that no such partition exists, which may be a finite computational refutation: an explicit $n$ plus an exhaustive, reproducible certificate that every 2-coloring of $\{1,\ldots,n\}$ has a color class admitting no monotone-3-AP-free ordering (code + exhaustiveness certificate), together with the restriction argument. ADVANCES: a verified computational study establishing, for a record range of $n$, that 2-colorings of $\{1,\ldots,n\}$ with both classes orderable do exist (with witness colorings and orderings, code, and certificates), mapping how constrained the survivors are; a proof for a restricted class of partitions (e.g. both parts unions of intervals, or defined by digit conditions) in either direction; or new structural criteria for which infinite sets can be permuted to avoid monotone 3-term APs. Deliver the partition + orderings + proof, or the refutation certificate + code, or the finite-range study with witnesses.
Background
A problem of Erdős and Graham [ErGr79] [ErGr80]; listed as open on erdosproblems.com/197 (fetched 2026-07-13, status 'open', tagged 'arithmetic progressions'). The motivating obstruction: $\mathbb{N}$ itself cannot be so permuted — Davis, Entringer, Graham, and Simmons [DEGS77] proved every permutation of $\mathbb{N}$ contains a monotone 3-term AP (see Erdős #196, erdosproblems.com/196; closely related to the venue problem on monotone 4-term APs in permutations of $\mathbb{N}$). The site records that a partition into THREE sets, each permutable to avoid monotone 3-term APs, is possible; the two-set case is what remains. A useful structural observation: if a two-set partition exists, then for every $n$ the induced 2-coloring of $\{1,\ldots,n\}$ has each color class orderable without monotone 3-term APs (restrict the infinite orderings); so exhibiting some $n$ for which EVERY 2-coloring of $\{1,\ldots,n\}$ has a class that cannot be so ordered would refute the partition's existence by a finite, checkable computation — though a positive answer cannot be certified finitely. The statement has been formalized in Lean in the google-deepmind/formal-conjectures repository. The attacker's tools: explicit digit- or interval-based partitions with recursively defined orderings and an avoidance proof for the positive direction; SAT/exhaustive search over 2-colorings of $\{1,\ldots,n\}$ and orderability tests for the finite refutation route.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #197 (T. F. Bloom) | website |
| REF-02 | Lean formalization of Erdős #197 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.