Erdős 196: A permutation of the natural numbers with no monotone four-term arithmetic progression

Primarily AI-generated textHuman understanding: no partsmath.NT — Number Theory

Contributed by Jensen Kohlmeyer, Liam Kruer ↗

Version 1 / Nov 21, 2026 / CC BY 4.0

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 w(n)=2ρ(n)nw(n)=2^{\rho(n)}n, where ρ\rho is a finite binary residue rank. The extension can include any prescribed finite set. Iteration gives a bijection of order type ω\omega on the natural numbers. The finite extension theorem, the resulting bijection, and the exact negative answer are formalized in Lean 4.

Author comments: TeX edition of the manuscript accompanying Justin Sun Prize submission JSP-000185. Pinned source and Lean verification materials: https://github.com/lkruer/conjectures/tree/bf058b903350eb8f873a22ab4a54b2e0faa9727d/problems/erdos-196

Provenance statement

OpenAI Codex assisted with the proof, literature checks, formalization and exposition. This is a TeX transcription of the pinned seven-page manuscript with a local clarification of the normalized adjacent differences.

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 (https://doi.org/10.4169/amer.math.monthly.118.10.921).DOI
  2. Conjectures.io, Erdős problem 196 , https://conjectures.io/problems/erdos196-erdos-196. Accessed September 9, 2026.link
  3. J. A. Davis, R. C. Entringer, 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 (https://doi.org/10.4064/aa-34-1-81-90).DOI
  4. J. Geneson, Density bounds for permutations avoiding monotone arithmetic progressions , preprint, arXiv:2608.12604v1 (2026). https://arxiv.org/abs/2608.12604v1.arXiv
  5. Google DeepMind, Formal Conjectures , file FormalConjectures/ErdosProblems/196.lean , revision 8432eac998110a563e03df65a28c117e97c8c142 . https://github.com/google-deepmind/formal-conjectures.link

Version history

  1. v1 · 7 pagesSubmitted by Liam KruerTeX edition of the manuscript accompanying Justin Sun Prize submission JSP-000185. Pinned source and Lean verification materials: https://github.com/lkruer/conjectures/tree/bf058b903350eb8f873a22ab4a54b2e0faa9727d/problems/erdos-196CurrentNov 21, 2026