WorksMathematics
Erdős 196: A permutation of the natural numbers with no monotone four-term arithmetic progression
Abstract
We construct a permutation of the natural numbers containing no increasing or decreasing four-term arithmetic progression as a subsequence. This gives a negative answer to Erdős problem 196. The construction extends finite prefixes while preserving closure and consistency of binary preferences. To extend a prefix, we order a new finite block by an adapted binary order and impose saturation at the nodes where the old prefix branches. Finiteness follows from the weight , where is a finite binary residue rank. The extension can include any prescribed finite set. Iteration gives a bijection of order type on the natural numbers. The finite extension theorem, the resulting bijection, and the exact negative answer are formalized in Lean 4.
Introduction
Write . A permutation of means a bijection , viewed as the sequence A monotone four-term arithmetic progression in this sequence consists of indices and integers , with , such that
Both signs of are allowed. Equivalently, the four values satisfy
Their distinctness follows from injectivity. These equalities also avoid any ambiguity about subtraction in the natural numbers. Davis, Entringer, Graham, and Simmons [3] proved that every permutation of the positive integers contains a monotone three-term arithmetic progression and constructed a permutation containing no monotone five-term progression. The remaining four-term question is recorded as Erdős problem 196 in the Formal Conjectures library [5] and on Conjectures.io [2]. We prove the following.
Theorem 1.1. There exists a bijection for which no indices satisfy both equalities in (1).
Adding one to each value and shifting the starting index gives the same conclusion for permutations of the positive integers.
Binary residue orders provide an elementary way to order every finite set of integers without a monotone three-term progression. Related orders on infinite sets are classical; see Ardal, Brown, and Jungić [1]. Such an order need not enumerate its underlying set in a sequence indexed by : an element can have infinitely many predecessors. Our construction instead preserves an entire finite prefix at each step.
There are also strong density results for subsets admitting permutations that avoid monotone progressions. Geneson [4] obtains density supremum results for lengths at least four and explicitly distinguishes them from an avoiding permutation of all the natural numbers. Theorem 1.1 addresses the full underlying set directly.
The main point is a finite extension theorem. A prefix records both the fourth terms that must already have appeared and the binary preferences required by progressions whose last two terms are still absent. We impose saturation at the finitely many nodes where the old prefix occupies both children. After the new block is appended, the future requirements keep their orientation at those nodes and reverse it at the other nodes. This update is what makes repeated extension possible. A weighted finite set supplies the needed saturation without a limiting argument.
Sections 2 and 3 establish the order and finiteness lemmas. Sections 4 and 5 prove the extension theorem. Section 6 constructs the permutation, and Section 7 describes the accompanying complete formalization.
Binary residue orders
A binary residue node is a pair
It represents the class . For , let
The two children of are the subsets with the two possible values of . A preference assignment chooses a value at every node; its child is called preferred.
For distinct , let
This is their first differing binary node when digits are read from least to most significant. Define
Lemma 2.1. The relation is a strict total order. For every there is a rank function
depending only on the residue modulo , such that if the node has depth less than , then
Proof. List the leaves of the binary residue tree of depth by recursively listing the preferred child before the other child. Give the leaves their ranks, starting with zero. The comparison of two distinct leaves is decided at their first differing node and is exactly (2.2). This constructs . For any finite set of distinct integers, choose large enough that their residues modulo are distinct. The relation on that set agrees with the finite leaf order. In particular, every pair is comparable and every triple satisfies transitivity. □
The arithmetic fact used throughout the proof is the alternation of the two children along a progression. For four values, the progression equations are
Lemma 2.2. Suppose , , and . Then , all three values lie in , and . If also satisfies , then , all four values lie in , and
Moreover, , and whenever the fourth term is present.
Proof. In , put . The three values are , , , with when the fourth term is present. If , the values have the same residue modulo , and their normalized adjacent differences are odd. Their th digits therefore alternate. Adjacent differences equal , so their first differing nodes agree. Finally, , and when present, because .
Lemma 2.3. There are no distinct with and .
Proof. At the first differing node of and , the values have the same digit and has the other digit, by the three-term part of Lemma 2.2. If the digit of is preferred, then precedes both endpoints; otherwise it follows both. In neither case is between them.
Finite saturation by a weight
We first give a finiteness lemma that applies to any natural-valued rank.
Lemma 3.1. Let and let be finite. There is a finite set such that
Proof. Define
Since , the set is contained in and is finite. It contains by the choice of . If and , then , so
Thus implies .
Definition 3.2. Let be a finite set of binary residue nodes and let be a preference assignment. A set is saturated at if, for every and ,
Thus a nonpreferred value brings into every preferred value at the same specified node that is at most twice as large. The inequality concerns the values themselves.
Corollary 3.3. For every finite , preference assignment , and finite seed set , there is a finite superset of saturated at .
Proof. Choose greater than the depth of every node in ; take if is empty. Use Lemma 3.1 with the rank from Lemma 2.1. If satisfy the hypotheses of Eq. (8), they first differ at , and the digit of is preferred. Hence , and Eq. (3.1) gives .
Only finitely many nodes are used in this argument. The conclusion does not require saturation at every node of the infinite binary tree.
Admissible finite prefixes
Let be a finite list of distinct members of , let be its set of entries, and write if and occurs before in . The notation always refers to positions, whereas and without a subscript refer to numerical order.
Definition 4.1. The list is admissible if it satisfies both conditions below.
(1) Closure. For all satisfying (4),
In particular, the conclusion requires .
(2) Compatibility. There exists a preference assignment such that, whenever and satisfy (2.3),
The compatibility condition says that all pairs imposing a requirement at a given node impose the same requirement. Indeed, for a progression beginning with and with both absent, any extension avoiding that progression must put before . In a binary order, this is achieved by preferring the digit of , which is also the digit of .
The empty list is admissible. Also, every admissible list avoids monotone four-term progressions: a chain satisfying (2.3) would contradict (4.1).
Let be the set of nodes at which branches, meaning that each child contains an element of . Equivalently,
The set is finite. Every compatibility requirement for occurs at one of these nodes. Fix a compatible assignment . We use the following adapted assignment :
If , set .
If and meets , prefer the unique child containing the old entries in that node.
If does not meet , set .
This definition is consistent. It retains compatibility because it changes no preference at a node in . The list itself need not be ordered by .
The finite extension theorem
Theorem 5.1. Let be admissible and let be finite. There is an admissible finite list such that is an initial segment of and .
Proof. Put and choose the adapted assignment from Section 4. By Corollary 3.3, choose a finite set saturated at . Let be the list of in increasing order, and define
Then has distinct entries, has support , extends , and contains . It remains to prove closure and compatibility. Call the entries of old and those of new. Every old entry precedes every new entry.
Closure. Suppose and satisfy (2.3). We show . If is old, then are old and closure of gives the conclusion. If are all new, their order agrees with , contrary to Lemma 2.3. Thus we may assume that is new and is old. If is old, then it already precedes , so we may also assume . There are two cases, according to the status of .
Case 1: are old and is new. Let . This is a node in . Since , compatibility of and the choice of give
By Lemma 2.2, the digit of is the other digit and . As , saturation at gives . Our assumption now makes new. Its preferred digit puts it before in , hence before in and in .
Case 2: is old and are new. The node is the same by Lemma 2.2. Because , the digit of is preferred and the digits of are not. This forces . Otherwise the adaptation rule at the nonbranching node containing the old value would prefer the digit of , a contradiction. The digit of equals that of , and . Saturation at this old branching node therefore gives . As in Case 1, is new and precedes in . All cases give , proving closure.
::: Compatibility. Define a new assignment on every node by
We show that is compatible with . Take an ordered pair and values satisfying (2.3), and put . We must prove
First suppose . If is old, then is old as well. Since are outside , compatibility of gives , as required. If is new, suppose for a contradiction that . Then has the preferred digit by Lemma 2.2, and . The value belongs to , so saturation at puts in , contradicting its choice. Thus in this case also. This establishes (5.3) at every old branching node.
Now suppose . The values cannot both be old: their occurrence in opposite children would make a node of . Since , it follows that is new. If is old, the adapted assignment prefers the child containing . Therefore the digit of is . If is new, both values occur in the sorted block , so . Again the digit of is preferred and that of is . In both cases (5.2) gives (5.3). Hence satisfies every compatibility requirement of . Together with closure and distinctness, this proves that is admissible. □
The inequalities used in the proof are precisely in closure and in compatibility. They follow from nonnegativity of the first two terms, as recorded in Lemma 2.2, and apply to progressions with either sign of the common difference.
Construction of the infinite permutation
Proof of Theorem 1.1. Start with the empty list . Given the admissible list , apply Theorem 5.1 with to choose . Thus
Every is finite and admissible. Induction shows that it contains each integer less than , so
Here denotes the length of the list. The lengths need not increase strictly at every step; the lower bound (6.2) is sufficient. Index list positions from zero and define
This entry exists by (6.2). The initial-segment property ensures that its value agrees with the entry at position in any stage having that position: any two stages are comparable by inclusion as initial segments.
If , choose a stage whose length exceeds both indices. Its entries are distinct and agree with at those positions, proving injectivity. For any , the value belongs to by (6.1). If it is at position in that list, the same agreement gives . Thus is surjective. In particular, every value occupies a finite position, and this is a permutation of order type .
Finally, suppose satisfy (1.1). The stage contains all four positions and agrees there with . Its closure condition applied to the first three entries puts before , contrary to . This proves the theorem. □
The construction only needs an admissible extension at each step. In particular, it never reorders a previously placed value. The binary orders serve to sort the finite added blocks; the stages determine the order of the infinite sequence.
Lean formalization and reproducibility
The accompanying file Erdos196.lean contains the complete Lean proof, including every lemma specific to this construction. Its imports are
import FormalConjectures.ErdosProblems.«196»
import TaskSupport
The checked environment uses Lean 4.33.1 and Formal Conjectures commit 8432eac998110a563e03df65a28c117e97c8c142.
The dependence on TaskSupport implements the exact target-type notation used in the submission bundle. The mathematical construction is contained in the namespace Bounty.Construction196. The correspondence between the paper and the principal declarations is shown below; namespace prefixes are omitted in the right-hand column.
| Mathematical component | Lean declaration |
| Binary comparison and rank | code_lt_iff_split, rank_lt_of_split |
| Lemma 2.3 | binary_no_three |
| Lemma 3.1 | finite_saturation |
| Corollary 3.3 | saturated_exists |
| Definition 4.1 | Closed, Compatible, Good |
| Theorem 5.1 | finite_extension |
| Nested stages and enumeration | stage, permFun |
| Injectivity and surjectivity | permFun_injective, permFun_surjective |
| Absence of four-term progressions | permFun_no_four, counterexample |
| Theorem 1.1 in index form | Bounty.paper_main |
Table 1.
In Lean, a binary residue is represented by its finite list of low bits. The relation LowEq k a b states equality of the bits below ; code uses the lexicographic order of preferred versus nonpreferred bits. The proof of finite_saturation is exactly the sublevel-set argument of Lemma 3.1. The stages are selected using classical choice from finite_extension. The formalized result is the existence theorem; it does not assert executable running-time bounds.
The main library-facing conclusion is
Here Lean’s includes zero, and denotes a bijection. The predicate HasMonotoneAP permits either orientation of an arithmetic progression along a strictly increasing list of indices. The proof converts that predicate to the two equalities in (1) and applies permFun_no_four. The declaration Bounty.paper_main states Theorem 1.1 directly in index form. The declaration Bounty.target proves the negation of the pinned catalogue type. In ASCII Lean notation, the final step is
theorem target : Not (fcTypeOfName% "Erdos196.erdos_196") := by
intro h
cases Construction196.counterexample with
| intro f hf => exact hf (h.mp True.intro f)
The source type is True ↔ ∀f : N ≃ N, HasMonotoneAP f 4; the displayed argument negates that affirmative assertion.
Local compilation, the validator’s static checks, and its exact-target inspector passed for the submission. The standalone companion and its explicit index theorem were also compiled. The axiom audit for the finite extension theorem, the counterexample, the index theorem, and the final target lists only
propext, Classical.choice, Quot.sound
These are standard axioms of the Lean environment. There are no admitted proofs or new axioms in the supplied construction, and its conclusions do not depend on the admitted open conjecture in the imported catalogue.
The supplementary archive contains both the standalone source and Erdos196-submission.lean, the body formatted for the catalogue’s Counterexample-mode wrapper. The latter omits imports and the outer namespace because the validator supplies them. The archive records the dependency revision, file hashes, and the local checking results.
Acknowledgment of AI assistance
OpenAI’s Codex assistant was used extensively in developing the mathematical argument, checking related literature, producing and debugging the Lean 4 formalization, and drafting and typesetting this manuscript. This assistance included substantive proof ideas and generated proof code.
The named authors are responsible for the final manuscript and its submission.
Email address: [email protected]
Email address: [email protected]
References
- [1]H. Ardal, T. Brown, and V. Jungić, Chaotic orderings of the rationals and reals, Amer. Math. Monthly 118 (2011), no. 10, 921–925. doi:10.4169/amer.math.monthly.118.10.921.DOI
- [2]Conjectures.io, Erdős problem 196, https://conjectures.io/problems/erdos196-erdos-196. Accessed Sep-tember 9, 2026.
- [3]J. A. Davis, R. C. Entriger, R. L. Graham, and G. J. Simmons, On permutations containing no long arithmetic progressions, Acta Arith. 34 (1977), no. 1, 81–90. doi:10.4064/aa-34-1-81-90.
- [4]J. Geneson, Density bounds for permutations avoiding monotone arithmetic progressions, preprint, arXiv:2608.12604v1 (2026). https://arxiv.org/abs/2608.12604v1.
- [5]Google DeepMind, Formal Conjectures, file FormalConjectures/ErdosProblems/196.lean, revision 8432eac998110a563e03df65a28c117e97c8c142. https://github.com/google-deepmind/formal-conjectures.