Monotone Progressions in Rearrangements of the Integers (Erdős Problems 195 and 196) — Research

If you shuffle all the whole numbers into one infinite list, must some evenly spaced run of them, like , still appear in order somewhere in the list? Paul Erdős asked how long such a run can be guaranteed to be. This page explains the question and what my draft adds.

Note. This is a hobby project and a draft. Claims marked as checked by computer were decided by a program and confirmed by independent programs, but no one else has refereed them yet, and I am still working on proofs a person can read line by line.

Arithmetic progressions

Definition (Arithmetic progression). A list of numbers with a constant gap between consecutive terms: The gap is the common difference. A progression with terms is a -term progression, or -AP for short.

Example. is a 4-term progression with common difference 4, and is a 3-term progression with common difference 1. The list is not a progression: the gaps are 1 and 2.

Rearranging all the numbers

Write for the natural numbers and for the integers.

Definition (Permutation of the natural numbers). An infinite list in which every natural number appears exactly once. The number sits at position .

Example. Swapping neighbours gives , a permutation of : every number appears, once.

A permutation of the integers is the same thing for : every integer, positive, negative or zero, appears exactly once. It can be written as a list that runs forward from position , or as a list that runs in both directions, with positions ; the two conventions lead to the same answers for the questions below.

Progressions hiding in order

Definition (Monotone progression). A permutation contains a monotone -term progression if there are numbers , with , that appear in the list in that order (each one later than the one before) or in exactly the reverse order. Other numbers may sit in between. A permutation that contains none avoids monotone -term progressions.

Example. In the finite list (positions to ), the values sit at positions , in increasing order, so the list contains a monotone 3-term progression. So do , at positions .

The two problems

Problem 196. Must every permutation of the natural numbers contain a monotone 4-term progression?

Problem 195. What is the largest such that every permutation of the integers must contain a monotone -term progression?

In 1977 Davis, Entringer, Graham and Simmons proved that every permutation of contains a monotone 3-term progression (and therefore so does every permutation of ), and that some permutation of avoids monotone 5-term progressions. For the integers, Geneson (2019) found a permutation avoiding monotone 6-term progressions, so the answer to Problem 195 is at most 5, and Adenwalla (2022) one avoiding monotone 5-term progressions, so it is at most 4. The answer to Problem 195 is therefore 3 or 4, and nobody knows which. For Problem 196, a preprint posted in September 2026 (Ho, arXiv:2609.12780) constructs a permutation of the positive integers in which no 4-term progression appears in order, which would answer it: no.

Why infinity makes it hard: the doubling trick

For a finite set of numbers, monotone 3-term progressions can always be avoided, and the classical construction shows the main idea behind everything on this page.

Example (Doubling). Start with the list . From any list , build a list twice as long: first every entry of doubled, then every entry of doubled minus one. Starting from : The last list contains each of once and no monotone 3-term progression.

Here is why. Take three evenly spaced values . If the gap is odd, the values alternate even, odd, even (or odd, even, odd), so they jump from one half of the list to the other and back, and cannot appear in order. If is even, all three have the same parity and live in one half, which is a doubled copy of the previous list; halving them gives a progression in the previous list, which by the same argument was not in order either.

The trick puts all the even numbers before all the odd ones. In an infinite list that is impossible: every number must sit at some finite position, so the odd numbers cannot all wait until after infinitely many even ones. This is the intuition behind the 1977 theorem that monotone 3-term progressions are unavoidable in infinite permutations, and behind the difficulty of the length-4 question. The best constructions so far (LeSaulnier and Vijay; Adenwalla) still split by parity at every scale, but leave themselves free choices inside each block.

What my draft does

A natural idea that cannot work

The obvious attempt to finish the job is a list that is exactly self-similar under doubling: the even numbers appear in the same pattern as the whole list, scaled by two, and so do the odd numbers, at every scale. The draft shows that this idea fails:

Every exactly self-similar permutation of this kind, of or of , contains a monotone 4-term progression, and the draft gives small explicit ones.
Over , the variants in which one of the two copies is reversed cannot exist at all.
Over , those reversed variants do exist; every one in two large, systematically listed families contains a monotone 4-term progression (checked by computer, with certificates that can be verified independently).

So exact self-similarity cannot avoid monotone 4-term progressions. This closes one natural route; it says nothing about the answers to the problems themselves.

Where it stops failing: length five

Running the same searches for 5-term progressions, every arrangement in those families contains one except a single arrangement built from base . Following that exception leads to three simple orderings that contain monotone 4-term progressions but no monotone 5-term progression. Two of them are easy to state.

Definition (Binary reflected Gray code). List the natural numbers so that each one differs from the one before in exactly one binary digit. The number at position is where is halved and rounded down, and compares two numbers digit by digit in binary, writing where the digits differ and where they agree. The list begins

Theorem (Gray code). The Gray code ordering of contains monotone 4-term progressions but no monotone 5-term progression. (Checked by computer; see below.)

Example. The values sit at positions : a monotone 4-term progression with common difference 3. Four consecutive numbers, on the other hand, never appear in order in the Gray code, and the draft gives an exact formula for how many 4-term progressions appear in order in each stretch of the list.

Over , avoiding 5-term progressions was already known to be possible; what is new is that this classical ordering, used in engineering since the 1950s, is an example.

Definition (Negabinary). Base : write a number with digits and , where the place values are instead of Every integer, negative ones included, can be written this way in exactly one way. For example is , is , and is .

Theorem (Negabinary ordering). Take each position , write it in ordinary binary, and read the same digits in base . The resulting list contains every integer exactly once, contains monotone 4-term progressions, and contains no monotone 5-term progression. (Checked by computer; see below.)

Example. The values sit at positions , in order: a monotone 4-term progression with common difference 1.

Because this list is a permutation of the integers with no monotone 5-term progression, it gives a second, independent proof that the answer to Problem 195 is at most 4, the bound Adenwalla proved, with an ordering that can be described in one line. The third ordering in the draft runs in both directions, with positions and values both in , and avoids monotone 5-term progressions too.

Together these results put the open case in an interesting place: exact self-similarity can avoid monotone 5-term progressions, but in every family checked it cannot avoid 4-term ones, and length 4 is precisely where Problem 195 is open.

How a computer proves "never"

No computer can check infinitely many progressions one at a time. These orderings, though, are defined digit by digit, so a machine with a small, fixed amount of memory can read the binary digits of a position and a value side by side and decide whether that value sits at that position.

Definition (Finite automaton). A machine that reads a string of symbols one at a time, keeps track of one of finitely many states, and at the end answers yes or no. Many statements about whole numbers written in binary can be turned into automata.

A statement like "there are numbers and , and five positions in increasing order, holding " is built from addition, comparisons and the digit rule, and a program called Walnut converts such statements into automata mechanically. If the automaton for the statement accepts nothing, the statement is false for all numbers at once. That is a proof, but it rests on the software being correct, so each claim was also tested by separate programs on large windows (for the negabinary list, every progression with all five values between and ), and I am writing proofs that do not depend on a computer.

Where it stands

The draft is being checked and is not yet submitted anywhere. Since Ho's preprint addresses Problem 196, my current work is on Problem 195: whether a construction like Ho's can be carried over from the natural numbers to the integers. Moving it over directly fails (there is an explicit counterexample), and I am trying a more flexible version.

References

J. A. Davis, R. C. Entringer, R. L. Graham, G. J. Simmons, On permutations containing no long arithmetic progressions, Acta Arithmetica 34 (1977) 81–90.
T. D. LeSaulnier, S. Vijay, On permutations avoiding arithmetic progressions, Discrete Mathematics 311 (2011) 205–207.
J. Geneson, Forbidden arithmetic progressions in permutations of subsets of the integers, Discrete Mathematics 342 (2019) 1489–1491.
S. Adenwalla, Avoiding monotone arithmetic progressions in permutations of integers, Discrete Mathematics 347 (2024) 114183; arXiv:2211.04451.
Ho, preprint, arXiv:2609.12780 (2026).
H. Mousavi, Automatic theorem proving in Walnut, arXiv:1603.06017 (2016).
T. F. Bloom, Erdős Problems 195 and 196, erdosproblems.com.