The Distribution of 3x+1 Trees

David Applegate Jeffrey C. Lagarias

Abstract

Backwards iteration of the 3x + 1 function starting from a fixed integer a produces a tree of preimages of a. Let T_{k}(a) denote this tree grown to depth k, and let T_{k}^{∗}(a) denote the pruned tree resulting from the removal of all nodes n ≡ 0 mod 3. We previously computed the maximal and minimal number of leaves in T_{k}^{∗}(a) for all a ≢ 0 mod 3 and all k ≤ 30. Here we compare these data with predictions made using branching process models designed to imitate the growth of 3x + 1 trees, developed in an earlier paper by Lagarias and Weiss. We derive rigorous results for the branching process models. The range of variation exhibited by the 3x + 1 trees appears significantly narrower than that of the branching process models. We also study the variation in expected leaf-counts associated to the congruence class of a mod 3^{j}. This variation, when properly normalized, converges almost everywhere as j → ∞ to a limit function on the invertible 3-adic integers.