Comparison of Binary Tree Features with the Graph-Forming Capabilities in the Predecessor Graph for the (3n+1)/2i Iteration

The following table allows the reader to compare  (on the one hand)  the node- and edge-wise description of a binary tree with  (on the other hand)  the features of elements of the predecessor graph for the classic Collatz iteration.   The left column of the table represents the typical recursive definition of a binary tree and the right column indicates the observed features of the Collatz graph.  The thrust of the argument will be that only a binary tree can be constructed from the nodes of the Collatz graph,  and since a binary tree is a weakly connected graph,  and since a weakly connected graph represents the Collatz itineraries,  the Collatz conjecture must be provable using this approach.

Properties of the binary tree data structure Collatz predecessor graph property fulfilling the binary tree structure
A unique (i.e. distinguished) node represents the root. 1 serves as the root because of the trivial loop 1-->1.
Every node's left and right children serve as roots of subtrees. *******
                   successor
                  / \
       predecessor   extension
           / \          / \                     
The left child is the Collatz predecessor,  calculated as
p=(4*s)-1)/3 when s mod 3 = 1 and
p=(2*s)-1)/3 when s mod 3 = 2.
The right subtree is the extension,  calculated as
e=4s+1.
The left child may be null (making s be called,  loosely,  a leaf node). A leaf node occurs when s mod 3 = 0.
*******An infinite binary tree will result from recursive application of the step above bearing asterisks. Every node in the Collatz graph bears an extension (right child),  so an infinite binary tree does result in spite of the frequent null left subtrees.

This table applies to unlabelled nodes.  To make a binary tree applicable to the Collatz conjecture,  we must label the nodes with the integer values that they contain.   The binary tree data structure can, of course,  contain many nodes bearing identical labels,  and one can deliberately  "explode"  recursive processes which do cover the same ground again and again into large binary trees containing many replicated labels.  To reach a proof of the Collatz conjecture based on the above table,  we must not only conclude that the binary tree is the only structure which can represent the pathways of the Collatz itineraries,  but we must also be satisfied that no nodes with identical labels ever appear, else there would be an effective loop in the Collatz itinerary.  It is therefore very important that we have shown that the abstract binary tree structure which describes a subdivision of the odd positive integers into its component l.d.a.s does so while always creating unique subsets.  Whence two nodes containing the same integer label cannot occur in multiple places within the Collatz predecessor binary tree.

Although we have gone to great length using infinite summations to show that the density of the odd positive integers represented in the binary tree is exactly that required to be inclusive of all the odd positive integers,  that point is moot here.   (This is fortunate, since the two dimensional infinite summation over infinite sets of infinite sets seems to raise doubts among mathematicians.)   Here we wish only to argue that no graph other than a binary tree can represent the Collatz predecessor graph and that the non-occurrence of replicate labels precludes any cycles,  thus completing the proof of the conjecture.

It is interesting that in the case of (3n+3^j)/2^i predecessor graphs this same argument seems to apply.  There does not seem to be any nifty way to break the predecessor graphs up into l.d.a.s.  Nevertheless,  when the graph as a whole is considered,  the same systematic production of disjoint subsets is observed,  again arguing that there can be no repetition in the labels on the nodes and again indicating that these binary trees represent the infinite predecessor graphs for this whole family of analogs,  thus providing the same line of argument to prove the whole family represent examples of convergence from all positive integers to a common integer,  3^j.



My Collatz Home Page        Index to Terms Used