\documentclass[11pt]{amsart} \usepackage[letterpaper,margin=1in]{geometry} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage{amsmath,amssymb} \usepackage{xurl} \usepackage[hidelinks]{hyperref} \setlength{\emergencystretch}{2em} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \numberwithin{equation}{section} \newcommand{\N}{\mathbb N_0} \newcommand{\Z}{\mathbb Z} \newcommand{\bit}{\operatorname{bit}} \newcommand{\supp}{\operatorname{supp}} \newcommand{\cat}{\mathbin{\Vert}} \title[Erd\H{o}s 196: avoiding four-term progressions]{Erd\H{o}s 196: A permutation of the natural numbers with no monotone four-term arithmetic progression} \author{Jensen Kohlmeyer} \email{jenwin@purdue.edu} \author{Liam Kruer} \email{kruerl@purdue.edu} \date{September 9, 2026} \subjclass[2020]{Primary 11B25; Secondary 05A05, 68V20} \keywords{Erd\H{o}s problem 196, infinite permutations, arithmetic progressions, binary orders, finite extension, Lean formalization} \begin{document} \begin{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\H{o}s problem 196. The construction extends finite prefixes while preserving two conditions: every ordered three-term progression with a nonnegative fourth term has that term already placed before its third, and the requirements imposed by unfinished progressions agree at each binary residue node. To extend a prefix, we order a new finite block by an adapted binary order and impose saturation only at nodes where the old prefix branches. Finiteness follows from the weight \(w(n)=2^{\rho(n)}n\), where \(\rho\) is a finite binary residue rank. The extension preserves both conditions and can include any prescribed finite set. Iteration therefore gives a bijection of order type \(\omega\) on all the natural numbers. The finite extension theorem, the resulting bijection, and the exact negative answer are formalized in Lean 4. \end{abstract} \maketitle \section{Introduction} Write \(\N=\{0,1,2,\ldots\}\). A permutation of \(\N\) means a bijection \(p:\N\to\N\), viewed as the sequence \(p(0),p(1),\ldots\). A monotone four-term arithmetic progression in this sequence consists of indices \(i exact hf (h.mp True.intro f) \end{verbatim} The source type is \(\texttt{True}\leftrightarrow\forall f:\mathbb N\simeq\mathbb N,\ \texttt{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 \begin{verbatim} propext, Classical.choice, Quot.sound \end{verbatim} 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 \nolinkurl{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. \section*{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. \begin{thebibliography}{5} \bibitem{ABJ} H. Ardal, T. Brown, and V. Jungi\'c, \emph{Chaotic orderings of the rationals and reals}, Amer. Math. Monthly 118 (2011), no. 10, 921--925. \href{https://doi.org/10.4169/amer.math.monthly.118.10.921}{doi:10.4169/amer.math.monthly.118.10.921}. \bibitem{website} Conjectures.io, \emph{Erd\H{o}s problem 196}, \url{https://conjectures.io/problems/erdos196-erdos-196}. Accessed September 9, 2026. \bibitem{DEGS} J. A. Davis, R. C. Entringer, R. L. Graham, and G. J. Simmons, \emph{On permutations containing no long arithmetic progressions}, Acta Arith. 34 (1977), no. 1, 81--90. \href{https://doi.org/10.4064/aa-34-1-81-90}{doi:10.4064/aa-34-1-81-90}. \bibitem{Geneson} J. Geneson, \emph{Density bounds for permutations avoiding monotone arithmetic progressions}, preprint, arXiv:2608.12604v1 (2026). \url{https://arxiv.org/abs/2608.12604v1}. \bibitem{FC} Google DeepMind, \emph{Formal Conjectures}, file \nolinkurl{FormalConjectures/ErdosProblems/196.lean}, revision \nolinkurl{8432eac998110a563e03df65a28c117e97c8c142}. \url{https://github.com/google-deepmind/formal-conjectures}. \end{thebibliography} \end{document}