The \(3x+1\) problem: a lower bound hypothesis. (English) Zbl 1415.11026
Summary: Much work has been done attempting to understand the dynamic behaviour of the so-called “\(3x+1\)” function. It is known that finite sequences of iterations with a given length and a given number of odd terms have some combinatorial properties modulo powers of two. In this paper, we formulate a new hypothesis asserting that the first terms of those sequences have a lower bound which depends on the binary entropy of the “ones-ratio”. It is in agreement with all computations so far. Furthermore it implies accurate upper bounds for the total stopping time and the maximum excursion of an integer. Theses results are consistent with two previous stochastic models of the \(3x+1\) problem.
MSC:
| 11B37 | Recurrences |
| 11B75 | Other combinatorial number theory |
| 60G50 | Sums of independent random variables; random walks |
| 94A17 | Measures of information, entropy |
Keywords:
\(3x+1\) problem; Collatz conjecture; parity vector; ones-ratio; binary entropy function; maximum excursionReferences:
| [1] | K.A. Borovkov, D. Pfeifer, Estimates for the Syracuse problem via a probabilistic model, Theory Probab. Appl. 45 (2001), 300-310. · Zbl 0984.60050 · doi:10.4213/tvp472 |
| [2] | T.M. Cover, J.A. Thomas, Elements of Information Theory, John Wiley, New York, 1991. · Zbl 0762.94001 |
| [3] | R.E. Crandall, On the \(3x+1\) problem, Math. Comp. 32 (1978), 1281-1292. · Zbl 0395.10013 |
| [4] | S. Eliahou, The \(3x + 1\) problem: new lower bounds on nontrivial cycle lengths, Discrete Math. 118 (1993), 45-56. · Zbl 0786.11012 · doi:10.1016/0012-365X(93)90052-U |
| [5] | C.J. Everett, Iteration of the number theoretic function \(f(2n)=n, f(2n+1)=3n+2\), Adv. Math. 25 (1977), 42-45. · Zbl 0352.10001 · doi:10.1016/0001-8708(77)90087-1 |
| [6] | D.J. Gibson, Discrete logarithms and their equidistribution, Unif. Distrib. Theory 7 (2012), 147-154. · Zbl 1313.11005 |
| [7] | A.V. Kontorovich, J.C. Lagarias, Stochastic models for the \(3x+ 1\) and \(5x+ 1\) problems and related problems, published in [1583:Lag10?], 131-188. · Zbl 1253.11035 |
| [8] | J.C. Lagarias, The \(3x+1\) problem and its generalizations, Amer. Math. Monthly 92 (1985), 3-23. · Zbl 0566.10007 · doi:10.2307/2322189 |
| [9] | J.C. Lagarias, A. Weiss, The \(3x + 1\) problem: two stochastic models, Ann. Appl. Probab. 2 (1992), 229-261. · Zbl 0742.60027 · doi:10.1214/aoap/1177005779 |
| [10] | J.C. Lagarias, editor, The ultimate challenge: The 3x+ 1 problem, Amer. Math. Soc., 2010. · Zbl 1253.11003 · doi:10.1090/mbk/078 |
| [11] | T. Oliveira e Silva, Empirical verification of the \(3x + 1\) and related conjectures, published in [1583:Lag10?], 189-207. · Zbl 1253.11038 |
| [12] | Y.G. Sinai, Statistical \((3x+1)\) problem, Commun. Pure Appl. Math. 56 (2003), 1016-1028. · Zbl 1044.11006 · doi:10.1002/cpa.10084 |
| [13] | T. Tao, The Collatz conjecture, Littlewood-Offord theory, and powers of 2 and 3, blog post published August 25, 2011 at http://terrytao.wordpress.com/2011/08/25. |
| [14] | R. Terras, A stopping time problem on the positive integers, Acta Arith. 30 (1976), 241-252. · Zbl 0348.10037 |
| [15] | G.J. Wirsching, The Dynamical System Generated by the \(3n + 1\) Function, Lecture Notes in Math. 1681, Springer, 1998. · Zbl 0892.11002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
