The Distribution of 3x+1 Trees

Abstract

Backwards iteration of the 3x + 1 function starting from a fixed integer a produces a tree of preimages of a. Let J _k (a) denote this tree grown to depth k, and let J _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 J* _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 [Lagarias and Weiss 1992]. We der ive 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.