3n+1 Predecessor Tree,  Three Views

At the most basic level, we wish to employ a graph to represent the trajectory which integers must take under the Collatz iteration in its progress to 1. Only a little experimentation or exposure to the literature leads to the conclusion that the Collatz graph must be a tree though, strictly speaking, one might insist that this be proven. We will employ the terminology of tree structures because it clearly applies, justified or not, to this work.

Three variant views will be employed to present the structure which serves as the basis for a proof of the Collatz conjecture.  These three views are representations of the predecessor tree from different viewpoints.  The phrase "predecessor tree" denotes this tree regardless of the particular viewpoint in current use.  Such a tree is just a tree which shows as children those nodes from which the values of any node come.

We'll use the computer science view that the root of a tree appears at the top of the tree diagram,  with its children arrayed below it.  To avoid potential confusion, 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,  place your grandparents 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.  The confusing point about predecessor trees is that the nodes which appear as children (in the tree) represent the predecessors (in real life) of the parental node (in the tree).  And the time order of creation of the tree is reversed from that of real time.

Following the Collatz itinerary starting from any integer goes upward from somewhere deep 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 this way,  we use "left descent" and "right descent" to be brief and to lessen the misleading connotation of the word "descendant" in this context.  It will be important to keep this orientation in mind; it is essential in all the ensuing discussion.

Only odd integers are included in the predecessor tree.  Omission of the even integers simplifies the trees,  making observations and discussion more tractable,  without loss of generality with regard to the essentials of Collatz trajectories . For acounting purposes.  we can think of the even integers as powers-of-2 attachments to every node of the odd-only tree to assess the entire contents of the predecessor tree.

In combination,  the representations of the tree will serve as a basis to elucidate a number of striking features of the 3n+1 trajectories.  A demonstration that an infinite predecessor tree that includes all the odd positive integers can be recursively constructed 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.  These are marked with a null symbol in the generat tree below.

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. This bifurcation  (ignoring leaf nodes)  of the possible predecessors at every level of the graph eliminates the need for use of a general tree in most of this work.

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.

Predecessor Tree as a General Tree

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.

Predecessor Tree as a Binary Tree

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 contains exactly the same nodes in a relinked configuration as the first except here the pictures show a slightly different selection of nodes.

(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) The leaf nodes are omitted in these next two depictions of the tree.  There is little loss of information about the tree structure because the leaves' lack of child nodes means there can be no elaboration below them in the tree.   Because of the leaf node omissions, extra integers appear in tracing the paths up from most integers.  (Specifically,  the contents of every right descent element   (including its header)  encountered in the trajectory now appear in the path in tracing the tree though they do not appear in the Collatz trajectory itself or in tracing a path in the general tree).  This feature provides an invaluable detail which otherwise might escape notice because those "extra" nodes in the binary tree trace reveal that three or more divisons by 2 occurred in tracing the trajectories.  The path up from 11 goes 11-17-13-3-5-1 in the binary tree trace,  where 3 is the node now introduced into the upward path.  This is explained in greater detail later.

Two observations can be made.

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 predecessor 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 {c[d]}, with or without the '{}' signs.)  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 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 early versions of these pages,  giving considerable help throughout.)

Predecessor Tree Abstracted into Sets as its Nodes

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 (in {0[3]}),  the set producing left descendants smaller than themselves (in {2[3]}),  and the set producing left descendants bigger than themselves (in {1[3]}). ).  Two of the three descendant sets are parental in their turn and may be treated in the same way.  The process iterates indefinitely.   Since the leaf node set no further propagates, it is elided from the abstract predecessor tree, leaving the tree to appear as a binary tree.

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.

My Collatz Home Page        Index to Terms Used