Argument via Construction of a Binary Tree

Let's do a little exercise.  Let's build a graph out of its component units.  The units we have are the nodes of a directed labelled graph and its attached edges.  In the case of leaf nodes there are two attached edges and in the case of internal nodes three .  The nodes are each labelled by an odd positive integer value. 

Let's reiterate the convention used for the orientation of the precdessor tree and the other spatial relationships.  We regard the various guises of the predecessor tree as if the deeper generations are derived from their Collatz successors.  When we created the state transition diagrams to characterize the available steps which can occur in the Collatz predecessor tree,  we continued that convention, which would have the edges point generally downward in the predecessor graph.  But when following paths in the direction of the trajectories,  we employ edges which are directed downwards in the predecessor tree in the upward direction.  There is no trouble about this;  though it may seem strange and confusing.  The convention is arbitrary, so it is helpful to be aware of it at all times.

The more generally employed Collatz tree has the edges directly oppositely to those of the predecessor tree . There are two or three edges from a node representing any odd intgeger in this view.  One edge is directed upward toward the successor;  the other one or two (depending on whether or not the node is a leaf node) are directed into the node from below.  One single node,  the root node,  is unique in that one of the edges points back to itself,  i.e.  that edge both originates and terminates in that one node.  Otherwise the incoming edges arise from nodes different from one another and from itself.

Two illustrations have been prepared to help the reader accustom himself to this orientation and inspect the properties of each node and its edges just described.  The first presents isolated nodes without putting a context around them,  and the second shows them in the context of a somewhat abstract binary predecessor tree.  These pictures do a better job of characterizing the situation than I seem able to produce verbally.

There must be a theorem here,  which might go something as follows.  Rather than complicate the wording,  I'll write this as if a leaf node has an incoming edge from a null left child.  This lets us speak of the nodes as having a uniform degree of 3.

Proposed Th.: Given a collection of labelled nodes of degree 3 with directed edges and
(1) one unique node whose outgoing edge loops back to itself*,  and
(2) one outgoing edge and two incoming edges for every node,  and
(3) every node is uniquely labelled with an odd positive integer,  and
(4a) every non-null left child is labelled with its parent's predecessor in an l.d.a., and
(4b) every right child is labelled with its parent's extension,and
(5) no restrictions arise to limit the growth of the graph,
then the only graph which can be formed is a directed binary tree.

An anonymous correspondent has provided an example of a graph which satisfies all these criteria except 4a and 4b, yet is not a binary tree. Criteria 4a and 4b are clearly required to ground this graph construction exercise firmly in the context of the Collatz conjecture.

*(We consider that the root node has its sole subtree as its right child.  The subtree is,  after all,  headed by 5,  the first extension from 1.  The two pictures referenced just above show it this way.  Alternatively,  one could put 1 in a node as the left subtree of the root  (and omit the looping edge)  because the predecessor of 1 is 1 via a b-step.)

How are these conditions satisfied in the Collatz (3n+1)/2^i predecessor graph?  And where were those conditions demonstrated?

(1) Briefly,  a state transition diagram,  in which the states of the diagram are the values of the odd integers modulo 8 reflects all possible successors of the odd integers in 1[8],  3[8],  5[8]  and 7[8] was prepared.  This very basic view establishes the nature and number of the edges available to every node for construction of the predecessor graph.

(2) A detailed examination of the values which may arise through successive steps of calculation of predecessors indicates that every step merely subdivides the set of integers represented by its parent.  Thus every label must be unique,  and there can be neither cycles nor alternative paths to any given integer.

(3) The solution of the equation which relates a predecessor to its successor has a unique solution when the successor is the predecessor (see details) .  This ensures that there is only a single anomalous node to serve as the root of the binary tree.

(4) The unlimited opportunity for growth emerges during the construction process, below.

If the above theorem were proven,  we would know that the predecessor graph for the Collatz trajectories is a tree and,  from Lagarias' review article, in one specific section,,  since a tree is a weakly connected graph,  that would complete the proof of the Collatz 3n+1 conjecture.

Nevertheless, let's make an inductive proof by construction.  Start with a two-node binary tree consisting of the root and its first extension  It is a tree, subsuming whatever problems are associated with the unique root.  This tree has 2 unsatisfied edges.  We'll take this two-node tree as the basis for induction.

Now there are two cases.  Either an  l.d.a.  element can be added as a left child or an extension element can be added as a right child.  If an  l.d.a. element is added,  a tree will result and the resulting tree will either have the same number of unsatisfied edges (if the l.d.a. element is a leaf node),  or an addition of one unsatisfied edge (if the l.d.a.  element is an internal one).  If an extension element is added as a right child, a tree is again obtained,  with no increased number of unsatisifed edges (if the extension heads a null l.d.a.),  or the addition of one unsatisfied edge (if the extension is not a leaf).  In either case a tree results,  and the resulting tree will contain at least as many unsatisfied edges as the starting one,  but more likely one or two more.  The number of unsatisfied edges monotonically increases as additional nodes are added.

That completes the induction.  We conclude that the Collatz predecessor graph can only be an infinite binary tree.   That the tree is binary is a stronger result than we need.  Any sort of tree is weakly connected,  and would suffice to prove the Collatz conjecture.

That seems far too easy.  The reader will start wondering if it is based on an inadequate model of the Collatz process.  So,  we turn now to a somewhat more detailed explication of the ideas which provided the basis for the assumptions for the inductive proof.

State transition diagrams serve as the basis for construction of the predecessor graphs.  The predecessor graphs can only contain the units permitted by the state transition diagrams.  For the Collatz 3n+1  (and other Collatz-like)  iteration(s),  as the following argument indicates,  the state transition diagram clearly shows that no cycles can arise in the predecessor graphs built out of nodes and edges permitted by this state transition diagram.  (To avoid assuming the predecessor graph is a tree  (thus merely creating a cyclic argument),  we need only to think of a spanning tree in whatever graph the predecessor graph might be to reach the same conclusion -- that there can be no closure of edges in the graph to complete a cycle and hence there is no cycle in the predecessor graph.)

When there are no possible cycles revealed by the state transition diagram, every step downward in the abstract  (spanning?)  tree generates a subset of integers disjoint to its parents.  Formulas represent the permitted values of the nodes modulus some product of powers of 2 and 3.  At every level of development of the (spanning?) graph,  the subsets existing among the parents are divided into disjoint subsets.   When these subsets are projected back to their parental nodes,  the whole heirarchy of parental nodes are subdivided into subsets which are disjoint to one another.  Since cycles necessarily imply reaching a node with some given value in more than one way,  and it is impossible that a given value can be a member of two disjoint subsets, it is shown that no cycles can exist in the  (spanning)  predecessor graph.  The systematic subsetting appears not only within the l.d.a.s of the (3n+1)/2^i system  (e.g. the descent to 27)  but also within predecessor trees for which no l.d.a.s can be defined e.g.  the (3n+9)/2 system.

(3) We may solve the equations in which some node is attached to itself,  i.e.  the condiion which leads to the terminating infinite loop characteristic of the Collatz-like iterations.  These solutions  (always 3*k)  are unique to each case in the family of  (3*n+3*k)/2^i Collatz-like iterations.  This shows that there is only one integer unique to each case in which the Collatz sequence can terminate.   This indicates that there is only a single root to the Collatz predecessor tree,  eliminating the possibility that there is a family of disjoint trees which constitutes the Collatz prdecessor graph.  (For the cases in which the state transition diagrams are permissive of a cycle,  e.g. (5n+1)/2^i,  the cycles seem to be quickly discovered by tracing through the paths from the first few odd integers.)

In summary, the start from the unique  (root)  node provides a first level subsetting of all the integers.  The subsetting occurs recursively and infinitely  (there being no alterntive),  eventually to include all the odd positive integers.  We have the nodes restricted to having degree 3, with directed edges, one input edge (from the Collatz successor)  and two output edges  (to the eldest and second eldest predecessors if regarded as a general tree,  or to the next l.d.a. element and the extension when the graph is represented as a binary tree).  Since the values of the nodes are unique  (in the abstract tree they are unique residue subsets),  the only kind of graph which can be constructed is a tree. 

My Collatz Home Page        Index to Terms Used