Several Arguments Towards a Proof

At this time I believe that the best argument in support of the Collatz conjecture is the one based on simple graph theory.

This page just lists a number of ways which,  starting from the structure developed here to describe the Collatz itineraries,  it seems to me might potentially support a rigorous proof of the Collatz conjecture.  I'll try to title them to characterize the different approaches and set them off from one another.

"Counting" Approaches,  Down to the Finest Detail

Of course,  we don't really count the integers in any of these sets. The sets are all infinite!  Really we use the densities of the sets of integers among the infinite set of odd integers.  These densities are known precisely  (2/d from the dn+c formulas for each set)  and the infinite summations employed are not threatened by the peculiar properties of sums of infinite sets.

All nodes in the abstract tree are sets of odd integers.  The root of the tree is the {8n+5} subset of all integers.  The integers in this set are equally distributed among {0,  1,  2} mod 3. All the integers congruent to 0 mod 3 are discarded as leaf nodes.  The remaining integers are separated into those congruent to 1 mod 3 and those congruent to 2 mod 3. When the former are treated with the b process and the latter with the s process,  each produces a smaller set of integers also equally distributed among {0,  1,  2} mod 3. Again,  those congruent to 0 mod 3 are discarded and the others separated into those congruent to 1 mod 2 which will get the b treatment and those congruent to 2 mod 3 which will get the s treatment.  Continuing this indefinitely will result in less and less dense (but still infinite)  subsets of the integers which have been created by every possible combination of b and s processes.  This repetitive process permits totaling the density of the integers included in the abstract tree.

Summing the densities of the nodes in the abstract predecessor tree in various ways leads to the conclusion that it contains the right number of odd integers to contain all the odd positive integers.  At the grossest level,  this is of little use.  But the exact same infinite sums which applied to the tree at the grossest level also apply to its refinements,  clear down through the table of cardinalities which incorporated the Fibonacci series and the restatement of the contents of the completely subsetted abstract predecessor tree as a list of left descent assemblies (l.d.a.s) which must,  therefore,  cover all the odd integers as well.  At so detailed a level,  accounting for the odd integers must be useful in a proof.

For those suspicious of the value of infinite summations,  a series of finite summations were calculated using various approaches to approximating the coverage of the integers by increasingly larger l.d.a.s.  In every case it appears that complete coverage of the integers is approached rapidly as the size of the l.d.a.s is increased,  thus providing an "engineering proof" that the set of finite l.d.a.s is sufficient to cover all the integers.

Elimination of Cycles and Disjoint Graphs

Historically,  a concern has been that there might be cycles or disjoint graphs in the graph representing the Collatz 3n+1 trajectories.  If we have the right number of integers in the predecessor trees,  the only way there could be a disjoint graph would be if we had double counted some elements in our counts which accounted for all the integers.  So it would be worthwhile to look at the elements which build the graph (i.e. tree)  to see if these possibilities can be eliminated.

To show that there can have been no double-counting we need only note that all the nodes in the abstract tree are disjoint.  Thus there cannot be two paths to any odd integer, and there can be no double-counting of a subtree under any integer.

That there cannot be two paths to any integer is more directly shown by a Alexandre Buisse's proof that any integer has a unique parent in the Collatz predecessor tree.

The abstract predecessor tree is clealy a directed graph.  The predecessor direction is downward in the tree,  and the Collatz trajectory runs upward in the tree.  The left descents which are defined in the abstract tree inherit this property;  the l.d.a.s in the binary predecessor tree are therefore directed graphs also.  Since any given integer appears in exactly one place in the predecessor trees and can only make the defined parental,  l.d.a.,  and extension connections,  no cycle can be formed simply because the nodes' edge-forming capabilities are exhausted by these three edges.

Progress Toward 1 is Inevitable

This is really only a crude form of the argument by directed graphs,  see next section,  second paragraph,  below.

The edges in the predecessor tree are of two kinds,  those connecting the elements of an l.d.a.  and those connecting extensions.  We know that these are disjoint -- the former involve 1 or 2 divisions by 2 in the Collatz trajectory,  and the latter 3 or more divisions by 2 in the Collatz trajectory.  We have a state transition diagram which visibly illustrates this point.

The effect on the magnitude of the numbers by a Collatz trajectory step differs in these two kinds of edges.   Within an l.d.a. the magnitude may increase or decrease in the l.d.a.,  but within a set of extensions the numbers inevitably decrease in magnitude in reaching the common parent.  This separation of the roles of the two kinds of steps (edges) reduces the confusion caused by the fact that numbers rise and fall apparently capriciously during the trajectory and allows one to say that the progress toward 1 is inexorable.  Within an l.d.a. the trajectory goes up to its extension header,  and in the extension the trajectory step goes to a smaller number.  Thus progress in the binary tree is always upward  (in an l.d.a.)  and leftward  (from any extension)  in the binary predecessor tree quite independently of capricious variations in the magnitude of the numbers involved in an l.d.a. 

We would like to have mapped the individual l.d.a.s in the abstract predecessor tree back into the binary predecessor tree.   Had this been possible,  the complete coverage of the integers indicated  (by the summation of integer densities)  in the abstract tree would have immediately implied complete coverage in the binary tree,  and hence completed a proof  (to that extent).  However,  as explained in the above paragraph, the mapping as to location is not necessary,  since the behavior of an l.d.a.  regardless of its position in the binary tree is entirely predictable.  The progress from any starting integer is upward in its l.d.a.  and then leftward to its header's successor.  That new integer will behave the same way,  and the new integer in turn will do the same.  Eventually the root of the binary tree must be reached,  completing the proof in that fashion.  By transferring the property of directionality into the binary tree,  we avoid the question of location within the binary tree but still see that the behavior must lead to the root.

Graph Theoretic Approaches to Prove Only A Tree Possible

As noted above, a node in the binary predecessor tree can only make the parental,  l.d.a.,  and extension connections,  defined for it.  The nodes' edge-forming capabilities are exhausted by these three edges.  Thus,  the properties of the nodes which make the predecessor tree,  combined with the uniqueness of every node value,  imply that they are capable only of constructing a tree.  If a graph theoretic approach could prove this,  it would,  in combination with the count of the number of nodes in the predecessor trees,  or with the greediness of the abstract predecessor tree,  prove the conjecture.  Indeed,  as Lagarias has pointed out (in First Form),  merely showing that the predecessor graph is a weakly connected graph suffices to prove the Collatz conjecture.

At a lower level,  the directed nature of the edges in the predecessor trees sharpens the arguments of the previous section.  It is the fact that the edges are all directed upwards in the l.d.a.s and leftward in the extensions which ensures that all paths in the binary predecessor tree lead eventually to the root.  The exclusion of cycles and of multiple occurences of any integers in the graph support the assertion that the graph is indeed a tree.

Getting to Infinity

It is worthwhile pointing out that getting to infinity is accomplished in two different ways which are expressed in this conceptual structure. 

First,  every extension set,  and therefore,  since all l.d.a.s are headed by extensions,  every l.d.a.,  occurs in an infinite number of instances.  Their positions may be calculated for each element of every left descent assembly from its own individual formula's successive values of n,  as was done for a few examples.

Second,  the abstract predecessor tree can be grown to an indefinite depth to produce more and more,  longer and longer,  rarer and rarer,  left descents.  There is always some tiny sliver of the total set of extensions whose descriptive formulas are not yet unassigned no matter to what depth the development of the abstract predecessor tree has been pushed.  These unassigned segments are represented in grey in the graphical presentation.  Each time the abstract predecessor tree is extended to an additional depth,  those portions of the nodes at every level in each path up from the leaf node sets at the new level  (which could not previously be assigned a formula)  can now be given a specific descriptive formula.  This new subdivision applies upwards throughout the subsets within the path to the root of the abstract tree,  resulting in a reduction of the density of the integers to which no specific formula has yet been applied to 2/3 of its previous value.

The Generation Trees are Greedy

We would like to be able to say that the predecessor trees are greedy,  i.e. that there is no way an odd integer can escape inclusion.  This would serve to prove the conjecture.

We have been able to show that any integer can be placed in the abstract predecessor tree right down to the instantiation,  element and identity of the containing left descent assembly.  This placement depends only on being able to perform simple arithmetic processes on the integers to discover the left descent identity and the element within it which contains the integer being probed,  and solving a simple linear equation to determine the instantiation.  Any integer will support these processes though they may be onerous with very large ones.

We have shown that the recursive elaboration of the abstract predecessor tree produces every possible combination of s and b paths in every level in its growth and that its growth can continue through an indefinite number of levels,  leaving ever smaller fractions of the integers to be identified in yet-undone generations.  Clearly,  this elaboration can be done without limit to accommodate,  eventually,  every possible left descent,  even very large ones.

We have indicated how left descent assemblies map into subsets of the nodes in the abstract predecessor tree.  Since we can identify any (every)  integer in a left descent assembly,  and we can place any (every)  left descent assembly in the abstract predecessor tree,  and we can grow the abstract predecessor tree to an arbitrary depth to accommodate arbitrary left descents,  and all the predecessor trees map into one another at least piecewise,  then it must follow that the predecessor trees are greedy,  i.e. that they contain all the positive odd integers.

Some Kind of Divide and Conquer Inductive Proof of Inclusion of All Integers

The best argument that there is no graph of any kind disjoint to the predecessor tree is that the predecessor tree greedily consumes all the odd integers.  The down-the-tree-and-back-up-again process showed how an iterative approach divides and redivides the contents of sets in the tree,  more and more finely describing the set contents as the tree is explored in depth.  To whatever extreme depth the process is pushed,  accounting precisely for all but an infinitesimally small residual fraction of integers,  the process can be applied to still more generations,  each reducing the residual fraction to 2/3 of its previous size and completing the description of the 1/3 which reached a value congruent to 0 mod 3. It is an inexorable process,  leading at length to all the odd integers,  and leaving no integers behind to constitute a disjoint graph of any kind.  That sounds like a very good basis for a formal proof.

A Hopeful Summary

The conclusions reached from consideration of the abstract predecessor tree argue that all odd integers are reached.  The mappings among the trees and the integers and the list of left descent assemblies have been detailed.  Arguments about the limited capability of the edges involved in the Collatz predecessor graph construction suggest that nothing except a tree can be constructed from them.  Since we have a tree big enough to contain all the odd integers,  and greedy enough to reach them,  and the edges and nodes constituting the graph can't make anything but a tree,  it would seem secure that the Collatz conjecture is correct. 


My Collatz Home Page        Index to Terms Used