Three trees, variants of one another, will be employed to present to the reader a structure which might become the basis for proof of the Collatz conjecture. All three trees are representations from different viewpoints of a single predecessor tree. The phrase "predecessor tree" is usually used herein to denote these trees, but occasionally the phrase "generation tree" is used. Such a tree is just a tree which shows as child nodes where values come from.
Before saying what side up anything is, we'd better define our trees' orientations. We'll use the computer science view that the root of a tree appears at the top of the tree diagram, with its descendants arrayed below it. That sentence is very confusing in the context of predecessor trees because the nodes which appear as children represent the predecessors of the parental node in the tree. To resolve this, it might be useful to visualize a tree of your ancestors. Think of yourself at the root, with your parents side by side in the line below yourself. Then in a new line beneath them, think of your parents' parents arrayed appropriately. Keep on as much as you know, and you will have produced your predecessor tree. You can start with any of your ancestors in the tree and follow the path upwards through time to define your lineage.
Time (processing) flows upward from lower in the tree toward the root in predecessor trees. In talking about the Collatz itineraries within the predecessor trees, the sequence of integers visited will be reflected in some path originating in the body of the tree and proceeding generally upwards to the root. With the tree oriented in way, it becomes clear which is line of descent is the left and which the right (referred to as the left descent and the right descent to be brief and to avoid the misleading connotation of the word "descendant" in this context). It will be important to keep this orientation in mind because it is essential in the following discussions in which I at times falter in keeping it clear.
Only odd integers are included in these predecessor trees. Omission of the even integers simplifies the trees, making observations and discussion more tractable, without loss of generality since even integers could trivially be placed in the trees. Indeed, at quite a late stage we do reintroduce the even integers as powers-of-2 attachments to every node of the odd-only tree in order to complete an accounting of the contents of the entire predecessor tree.
In combination, the trees will serve as a basis to elucidate a number of striking features of the 3n+1 path trajectories. A demonstration that all odd integers appear in the (equivalent) predecessor trees would prove that all integers will go to 1 by the 3n+1 process. (See Lagarias on the Collatz graph in the early paragraphs of his section 2.)
To produce successive generations of children in the predecessor
trees, we use the recursive formula
T(k):=(-1+T(k-1)*2^p(k))/3
where
p(k) must be even when T(k-1) is congruent to 1 mod 3 and
p(k) must be odd when T(k-1) is congruent to 2
mod 3.
When T(k-1) is congruent to 0 mod 3, there is no predecessor
in the Collatz trajectory, i.e. there is a leaf in the predecessor tree.
Examples of the dependence on the value of the parent mod 3 appear in the general tree, where 5 as parent produces 3, 13, 53, ... using odd powers of 2, and 13 as parent produces 17, 69, 277, ... using even powers of 2.
The successive children in any such set of children have a simple (recursively defined) relationship. Taking n as the value of the smaller of a pair of adjacent children, the larger will be 4n+1 whether p(k) is even or odd.
The first tree we will look at is straightforward. See the general tree, which is not very helpful in seeking an overall structure, but that is the point. It is rooted in 1 and shows several of the odd integers produced early in the predecessor tree, but of course the tree is (presumably) infinite. It is a general tree in which all the odd precursors of a given integer in the 3n+1 trajectories are displayed as its children in order of increasing magnitude.
This tree has two major virtues in addition to its value as an introduction for the subsequent trees. (I use the word 'nodes' to refer to the vertices in the graphs (trees) described herein.)
(1) The leaf nodes (congruent to 0 mod 3) appear without children in this presentation.
(2) The paths upward from any node in the tree visit exactly the same sequence of odd numbers that is visited when the integer in that node is run through its Collatz 3n+1 trajectory, e.g. 11-17-13-5-1.
The second tree is a binary tree obtained from the previous, general, tree by the usual transformation. The children of any node in the general tree are linked each to the next, and the parent is linked only to that child which is smallest in magnitude. The tree looks different but contains exactly the same nodes as the first. (Well, the pictures show a different selection of nodes, but the trees themselves contain the same nodes in a relinked configuration.)
There are two note-worthy differences.
(1) Every node in the tree bears a right subtree. Even the "leaf" nodes support a right subtree. Despite this feature we continue calling those nodes congruent to 0 mod 3 "leaves". (They are recognizable in the binary tree by having no left child.)
(2) There is some loss of fidelity in reflecting the behavior during each integer's Collatz itinerary. Extra integers appear in the paths up from most integers. (Specifically, the contents of every right descent (including its header) encountered in the trajectory now appear in the path in the tree though they do not appear in the Collatz trajectory itself). This change is invaluable because those "extra" nodes in the binary tree help reveal the structure of the trajectories in a way which otherwise escapes notice in the general tree. The path up from 11 goes 11-17-13-3-5-1 in the binary tree presentation, where 3 is the node now introduced into the upward path. This is explained in greater detail later.
The left descents are where the action is. It is in the left descents that the "mixing" which makes the conjecture so hard to prove occurs. It is the sequence of nodes in the left descents which are controlled by the value of the parent modulo 3 and which behave in a seemingly erratic way, decreasing or increasing from the parental value at the whim of their parents (modulo 3) and having varying lengths before they are interrupted by the encounter of a value congruent to 0 mod 3 which stops the left descent at a leaf node.
The right descents are uniformly dull. Taking n as the value of the parent, the right child will be 4n+1. The right descents proceed recursively in this fashion dully to infinity. (Sets of integers congruent to c mod d will be denoted as {d*n+c} or simply d*n+c.) All the elements in a given right descent give rise to the very same odd integer when the Collatz process is applied. In that sense the right descents just serve as extensions of their parental integer. There is no action there. We will refer to the right descent elements collectively as the "extensions", and to the element which heads any particular left descent as its (header or root) extension. Every integer in the binary predecessor tree bears an infinite set of extensions.
The entire infinite collection of right descents must cooperate to fill in all the holes among the integers left by the much more interesting action in the left descents. To accomplish this, two-thirds of the nodes in the right descents serve as parents to additional sets of left descents. The right descents are effectively the glue that holds together the left descents.
We will continue the practice of obfuscation by referring to the integers in "left descents" in the binary tree as such regardless of whether the sets they are members of appear in left or right subtrees in the third version of the predecessor tree, described next.
We can prove the odd integers can be divided into two disjoint sets, left and right descendants. (Thanks to Margaret Maxfield for major contributions to the referenced proof, and for reading all of these pages, giving considerable help throughout.)
The third tree might be termed the "abstract predecessor tree". It is a tree in which all the nodes are infinite sets of integers. We put all the dull items, the extensions, into the root node, confident that none will ever appear below it in the developing tree. I.e., the root node is the infinite set of extensions, the odd integers described by 8n+5, appearing as right descendants in the binary predecessor tree. In the tree developed below this root, we focus on the interesting items: the left descendants of the binary tree. We'll build the abstract predecessor tree by sub-dividing each parental set into three sets, the set of leaves (due to congruence of all its integer members to 0 mod 3), the set producing left descendants smaller than themselves (due to congruence to 2 mod 3), and the set producing left descendants bigger than themselves (due to congruence to 1 mod 3). Two of the three descendant sets are parental in their turn and may be treated in the same way. The process iterates indefinitely.
We will iteratively work out what expression describes the elements of each set of leaves, its smaller descendants, and its bigger descendants. We depict the smaller s-descendants as the left subtree and the bigger b-descendants as the right subtree in the abstract predecessor tree while continuing to call them all left descendants at the binary tree level. We use a string composed of ss (esses) and bs (bees) to indicate the path downward from the root to any given child set in the abstract predecessor tree (whence the ms and the mb in the theorem). The figures depict these matters with little further explanation.
Clearly, the abstract predecessor tree will generate left descents with every possible combination of b and s steps in paths of arbitrary length. This property is reminiscent of a property of parity vectors describing the trajectory of natural numbers in the Collatz graph {compare Terras, referenced by Wirsching, p45}, but we describe segments of a trajectory constituting a left descent, not entire trajectories, and the selection made at each binary choice is a different one in the two cases. Still, it is a tantalizing parallel.