Erdős 196: A permutation of the natural numbers with no monotone four-term arithmetic progression
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 , 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.
Provenance statement
References
- 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
- Conjectures.io, Erdős problem 196 , https://conjectures.io/problems/erdos196-erdos-196. Accessed September 9, 2026.link
- 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
- J. Geneson, Density bounds for permutations avoiding monotone arithmetic progressions , preprint, arXiv:2608.12604v1 (2026). https://arxiv.org/abs/2608.12604v1.arXiv
- Google DeepMind, Formal Conjectures , file FormalConjectures/ErdosProblems/196.lean , revision 8432eac998110a563e03df65a28c117e97c8c142 . https://github.com/google-deepmind/formal-conjectures.link
Version history
- 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