The distribution of \(3x+1\) trees. (English) Zbl 0868.11012

Applegate, David; Lagarias, Jeffrey C.

Exp. Math. 4, No. 3, 193-209 (1995).

The \(3x+1\) function is defined by \(T(n)=n/2\) for \(n\) even, \(T(n)=(3n+1)/2\) for \(n\) odd. Starting from a positive integer \(a\), backward iteration of \(T\) produces a tree of preimages. It is convenient to “prune” this tree by removing the nodes \(n\equiv 0\bmod 3\); denote by \({\mathcal T}^*_k(a)\) the pruned tree extended up to depth \(k\). On the other hand, a sequence \({\mathcal B}[3^j]\) of branched processes designed to model backward iteration of \(T\) had been studied previously [J.-C. Lagarias and A. Weiss, Ann. Appl. Probab. 2, 229-261 (1992; Zbl 0742.60027)].
Here empirical data concerning the minimal and the maximal numbers of leaves of depth \(k\) of \({\mathcal T}^*_k(a)\) are compared to predictions produced by the branched process \({\mathcal B}[9]\). The result is: The range of the leaf counts observed empirically using the trees \({\mathcal T}^*_k(a)\) is significantly narrower than that “predicted” by the stochastic model.
In the final section, fluctuations of the leaf counts of such trees caused by the branching pattern at the base of the tree are studied. Appropriately normalized, the leading terms of these fluctuations are martingale with respect to the \(\sigma\)-fields \(\{{\mathcal F}_j: j\geq 1\}\), with \({\mathcal F}_j=\{\text{residue classes mod }3^j\}\). Then the Martingale Convergence Theorem is applied to show that the normalized variations of leaf counts lead to a function \(W_\infty\) that is defined almost everywhere on the group \(\mathbb{Z}^\times_3\) of invertible 3-adic numbers. It is conjectured that \(W_\infty\) is a continuous function on \(\mathbb{Z}^\times_3\), and it is shown that this is connected to a conjecture called \(C^\#\) concerning the asymptotic behaviour of the extreme leaf counts.

Reviewer: G.Wirsching (Eichstätt)

MSC:

11B83	Special sequences and polynomials
11B37	Recurrences
60G46	Martingales and classical analysis

Keywords:

\(3n+1\)-problem; Collatz problem; backward iteration; numbers of leaves of depth \(k\); fluctuations of the leaf counts

Citations:

Zbl 0742.60027

References:

[1]	Applegate D., Math. Comp. 64 pp 411– (1995)
[2]	Applegate D., Math. Comp. 64 pp 427– (1995)
[3]	Athreiya K. B., Branching Processes (1972)
[4]	Billingsley P., Probability and Measure (1979)
[5]	Borovkov K., ”Estimates for the Syracuse problem via a probabilistic model” (1993) · Zbl 0984.60050
[6]	Crandall R. E., Math. Comp. 32 pp 1281– (1978)
[7]	Harris T. E., The Theory of Branching Processes (1963) · Zbl 0117.13002
[8]	DOI: 10.1214/aoms/1177699266 · Zbl 0203.17401
[9]	DOI: 10.2307/2322189 · Zbl 0566.10007
[10]	Lagarias J. C., Ann. Applied Prob. 2 pp 229– (1992) · Zbl 0742.60027
[11]	Leavens G., Computers and Mathematics, with Applications 24 (11) pp 79– (1992)
[12]	Müller H., Mitteilungen Math. Ges. Hamburg 12 pp 231– (1991)
[13]	Rawsthorne D. W., Math. Mag. 58 pp 172– (1985) · Zbl 0587.10030
[14]	Wagon S., Math. Intelligencer 7 pp 72– (1985) · Zbl 0566.10008
[15]	Wirsching G. J., Rev. Roum. Math. Pure Appl. 39 pp 915– (1994)
[16]	Wirsching G. J., Habilitationsschrift (1995)