Almost all orbits of the Collatz map attain almost bounded values

Terence Tao

Forum of Mathematics, Pi, Tome 10 (2022)

Résumé

Define the Collatz map ${\operatorname {Col}} \colon \mathbb {N}+1 \to \mathbb {N}+1$ on the positive integers $\mathbb {N}+1 = \{1,2,3,\dots \}$ by setting ${\operatorname {Col}}(N)$ equal to $3N+1$ when N is odd and $N/2$ when N is even, and let ${\operatorname {Col}}_{\min }(N) := \inf _{n \in \mathbb {N}} {\operatorname {Col}}^n(N)$ denote the minimal element of the Collatz orbit $N, {\operatorname {Col}}(N), {\operatorname {Col}}^2(N), \dots $. The infamous Collatz conjecture asserts that ${\operatorname {Col}}_{\min }(N)=1$ for all $N \in \mathbb {N}+1$. Previously, it was shown by Korec that for any $\theta> \frac {\log 3}{\log 4} \approx 0.7924$, one has ${\operatorname {Col}}_{\min }(N) \leq N^\theta $ for almost all $N \in \mathbb {N}+1$ (in the sense of natural density). In this paper, we show that for any function $f \colon \mathbb {N}+1 \to \mathbb {R}$ with $\lim _{N \to \infty } f(N)=+\infty $, one has ${\operatorname {Col}}_{\min }(N) \leq f(N)$ for almost all $N \in \mathbb {N}+1$ (in the sense of logarithmic density). Our proof proceeds by establishing a stabilisation property for a certain first passage random variable associated with the Collatz iteration (or more precisely, the closely related Syracuse iteration), which in turn follows from estimation of the characteristic function of a certain skew random walk on a $3$-adic cyclic group $\mathbb {Z}/3^n\mathbb {Z}$ at high frequencies. This estimation is achieved by studying how a certain two-dimensional renewal process interacts with a union of triangles associated to a given frequency.

Détail

DOI : 10.1017/fmp.2022.8

Bibliographie

[1] Allouche, J.-P., Sur la conjecture de “Syracuse-Kakutani-Collatz”, Séminaire de Théorie des Nombres, 1978–1979, Exp. No. 9, 15 pp., CNRS, Talence, 1979.Google Scholar

[2] Baker, A., Linear forms in the logarithms of algebraic numbers. I , Mathematika. A Journal of Pure and Applied Mathematics, 13 (1966), 204–216.Google Scholar

[3] Barina, D., Convergence verification of the Collatz problem , The Journal of Supercomputing, 2020.Google Scholar

[4] Bourgain, J., Periodic nonlinear Schrödinger equation and invariant measures , Comm. Math. Phys. 166 (1994), 1–26.Google Scholar | DOI

[5] Carletti, T., Fanelli, D., Quantifying the degree of average contraction of Collatz orbits , Boll. Unione Mat. Ital. 11 (2018), 445–468.Google Scholar | DOI

[6] Chamberland, M., A survey: number theory and dynamical systems, The ultimate challenge: the problem, 57–78, Amer. Math. Soc., Providence, RI, 2010.Google Scholar

[7] Crandall, R. E., On the ‘’ problem , Math. Comp. 32 (1978), 1281–1292.Google Scholar

[8] Everett, C. J., Iteration of the number-theoretic function , , Adv. Math. 25 (1977), no. 1, 42–45.Google Scholar | DOI

[9] Korec, I., A density estimate for the problem , Math. Slovaca 44 (1994), no. 1, 85–89.Google Scholar

[10] Kontorovich, A., Lagarias, J., Stochastic models for the and problems and related problems, The ultimate challenge: the problem, 131–188, Amer. Math. Soc., Providence, RI, 2010.Google Scholar

[11] Kontorovich, A., Miller, S. J., Benford’s law, values of -functions and the problem , Acta Arith. 120 (2005), no. 3, 269–297.Google Scholar | DOI

[12] Kontorovich, A. V., Sinai, Ya. G., Structure theorem for -maps , Bull. Braz. Math. Soc. (N.S.) 33 (2002), no. 2, 213–224.Google Scholar | DOI

[13] Krasikov, I., Lagarias, J., Bounds for the problem using difference inequalities , Acta Arith. 109 (2003), 237–258.Google Scholar | DOI

[14] Lagarias, J., The 3x+1 problem and its generalizations , Amer. Math. Monthly 92 (1985), no. 1, 3–23.Google Scholar | DOI

[15] Lagarias, J., Soundararajan, K., Benford’s law for the function , J. London Math. Soc. (2) 74 (2006), no. 2, 289–303.Google Scholar | DOI

[16] Lagarias, J., Weiss, A., The problem: two stochastic models , Ann. Appl. Probab. 2 (1992), no. 1, 229–261.Google Scholar | DOI

[17] Oliveira E Silva, T., Empirical verification of the 3x+1 and related conjectures , The ultimate challenge: the problem, 189–207, Amer. Math. Soc., Providence, RI, 2010.Google Scholar

[18] Roosendaal, E., www.ericr.nl/wondrous.Google Scholar

[19] Sinai, Ya. G., Statistical problem , Dedicated to the memory of Jürgen K. Moser. Comm. Pure Appl. Math. 56 (2003), no. 7, 1016–1028.Google Scholar | DOI

[20] Tao, T., The logarithmically averaged Chowla and Elliott conjectures for two-point correlations , Forum Math. Pi 4 (2016), e8, 36 pp.Google Scholar | DOI

[21] Terras, R., A stopping time problem on the positive integers , Acta Arith. 30 (1976), 241–252.Google Scholar | DOI

[22] Terras, R., On the existence of a density , Acta Arith. 35 (1979), 101–102.Google Scholar | DOI

[23] Thomas, A., A non-uniform distribution property of most orbits, in case the conjecture is true , Acta Arith. 178 (2017), no. 2, 125–134.Google Scholar | DOI

[24] Wirsching, G., The Dynamical System Generated by the Function, Lecture Notes in Math. No. 1681, Springer-Verlag: Berlin 1998.Google Scholar