Struggling for a Proof

Proof Introduction and Notations

The Collatz conjecture has attracted hundreds of interested workers during the seventy years since its proposal but is still without a generally accepted proof.  The conjecture involves a recursive iteration on the positive integers and proposes that the trajectory of these iterations is such that convergence to 1 will result from any starting value.

It appears the conjecture could be easily proven if one could just develop a structure which accommodates the peculiar behavior of its trajectories.   This work develops and then proceeds from just such a structure.

Following common practice,  we use T to denote any element in a Collatz trajectory and/or in the infinite predecessor graph which represents their totality.  The Collatz successor, Ts,  of any odd n in Z+ can be found from
      Ts(n)=(3n+1)/2i,  where i is that integer which results in an odd successor, Ts                (eqn 1)

Clearly,  the smallest Collatz predecessor,  Tp of any odd n can be found from
      Tp(n)=(-1+n*2i)/3,  where i is the least integer giving an odd integer predecessor,  Tp        (eqn 2)

When n is in {0[3]},  no predecessor exists, so we have a leaf node.  When n is in {1[3]},  i is 2, or,  more generally,  in {0[2]},  and when n is in {2[3]},  i is 1 or,  more generally, in {1[2]}.

As these formulas reflect,  we have chosen to focus on the odd positive integers, since the even integers are readily added as powers-of-two multiples of the odd integers (i.e. n*2k, for all odd n and k in Z+).  Obviously, the even integers can't contribute to idiosyncratic trajectories.

The structure we will come to is an infinite directed predecessor tree.  This is one particular tree,  completely defined by the collection of all possible Collatz trajectories.  This tree must be investigated from several viewpoints to appreciate its instructive features.  As an informal introduction to them,  we offer necessarily very sketchy pictures of it from each of the useful viewpoints,  which we have come to call the general tree,  the binary tree,  and the abstract tree.

Since we regard the predecessor tree as recursively defined,  we dispense with subscripts denoting the distance of an element into the trajectory from its starting point in favor of subscripts and superscripts indicating local relationships within these three critical viewpoints. Three aspects are critical:  the viewpoint of the tree in use to represent trajectories,  the positional relationships among near neighbors in the predecessor tree,  and the direction of travel in the tree. 

To indicate the direction of relationship,  we use,  as above,  subscripts p or s, denoting predecessor or successor, respectively.  Thus,  in the trajectory 7-11-17-13-5-1,

      Tp(11)=7;        Ts(13)=5

Since we follow the practice of placing the root of a tree at the top of its picture,  predecessors appear below their successors,  and Collatz trajectories appear  (at least to the degree accommodated by the viewpoint)  as paths from origins deep in the predecessor tree upwards to the root.  Only the general tree accurately maps the odd numbers observed in a numeric calculation of a Collatz trajectory as a path from deep in the tree to the root.

The standard transformation of the general tree into the corresponding binary tree results in modest alterations in the apparent trajectory as reflected by upwards paths in the tree.  In these instances a superscript is used to specify the tree used for the representation,  with g for the general tree,  b for the binary tree,  and a for the abstract tree.

Since the path 213-53-13-3-5-1 in the binary tree appears as 213-5-1 in the general tree,

      Tbp(5)=3.       but     Tgp(5)=213,

These "phantom"  Tbs   in the binary tree (53 and 13,  in this instance)  (so-called because they appear in the binary tree path,  but not in the numerically calculated trajectory)  arise from the shuffling of  links during the tree transformation.  These "phantoms" in the binary tree are required to properly place those elided elements (like 53 and 13) in the binary tree representation,  whenever a predecessor (like 213) occurs where the i of eqn 2 is replaced by any i+2k, with k in Z+.

As is customary in binary trees,  we distinguish the left predecessor (Tblp) from the right predecessor (Tbrp).  Further, we group a series of Tblps with their header element making a left descent assembly   (l.d.a.).  Tbrps are called extensions because they extend the individual Tbrp to give a set sharing one Tgs (successor in the general tree).  L.d.a. headers appear in {5[8]} and their leaf elements in {0[3]}.

Abstract Tree; Its Derivation from a State Transition Diagram

The abstract tree is a tree whose nodes are infinite sets of odd integers {c[d],  i.e. congruent to c modulo d}.  We often refer to these sets using formulas {dn+c, n in Z+ and d in {2a*3b}}, reflecting the means of their derivation  (below).

At first purely from observation,  but later supported in detail,  the root of  the abstract tree is assigned as {5[8]}.  One sees in the general tree that second and subsequent children  (they become the extensions in the binary tree)  all fall into this residue class.  The effect is to collect the headers of the l.d.a.s into the root node of the abstract tree so that it can be used to discover several essential properties  of  l.d.a.s.

By regarding the Collatz iteration as a finite state machine, a directed graph called a state transition diagram is readily constructed.  It shows the result of each Collatz transition as an edge from each {Ta} to its predecessors.  The {Ta} values are characterized in terms of their residue set mod 3 and mod 8.  Values in {1[3]} produce predecessors bigger than themselves,  and values in {2[3]} produce predecessors smaller than themselves,  whence we have formed the habit of calling transitions from the former b-steps and from the latter s-steps.

Each set {Ta} is composed of a subset of leaves ({0[3]}), and two subsets  ({1[3]} and {2[3]})  which lead via b- and s-steps to the two predecessor sets,   as controlled by the value of floor(mod(Ta,72)/24).   However,  only the latter two are included in the diagram because the leaf nodes have no predecessors ({Talp})and therefore cannot contribute to elaboration of an l.d.a.

Strikingly,  the nodes in {5[8]} have no incoming edges. All the other nodes are interconnected and can chain together to form a possibly lengthy l.d.a.  It is this separation of capabilities which justifies the selection of {5[8]} as the root of the abstract predecessor tree,  and the complementary sets {{1[8]}, {3[8]}, {7[8]}} as the contents of  l.d.a.s.

Where,  then, do the {5[8]} Ta values come from?   They are the values in the extensions, the Tbrp which come from eqn 2 with i>2 and always fall in {5[8]},  i.e.,  those Ta={Tgpderived from eqn 2 with i>2)}.

A rearranged state transition diagram showing the linkage between several  l.d.a.s is offered.  The principal addition there is that leaf nodes are collected and explicitly indicated as providing entries into deeper l.d.a.s.

To summarize,  the predecessor tree is composed of  l.d.a.s linked together by extensions which serve as headers for another generation of  l.d.a.s.   Every odd number has an extension,  but only those extensions in {1[3]} or {2[3]} appear as headers of additional l.d.a.s.  The extensions in {0[3]} are both leaves and l.d.a. headers.  In other words,  these are null l.d.a.s with no internal nodes. .

Accounting the Coverage of the Abstract Predecessor Tree

Any set other than a leaf node set can give rise to a predecessor set by either an s- or a b- step.  This immediately produces the abstract tree.  Any path from root to a terminating leaf set in the abstract tree represents an l.d.a.  L.d.a.s can be denoted by a string "e(s|b)kt", where the e represents the extension header,  the parenthesized expression indicates 0 or more selections of s- or b-steps,  and the t represents termination due to having reached a leaf set.

This expression denoting the detailed structure of an l.d.a. is in predecessor order.    Read left to right,  and you follow the growth of the predecessor tree.  Read right to left,  and you follow a path segment in the direction of the Collatz trajectory.  We will most often use the predecessor direction for l.d.a.s and other path segments.

A different picture of the abstract tree is useful to illustrate the coverage of the integers achieved by the developing tree.  Because one-third of the integers included in each {T} in the abstract tree represent leaf nodes,  only two-thirds carry on to their two predecessor sets.

For a more detailed description of the contents of abstract tree nodes,  the residue sets,  {c[d]},  represented by each node in the abstract,  tree must be developed.  Keep the same diagram in mind.  A rendering of the abstract tree with sets identified with {c[d]} labels cannot be  imagined at this stage,  because each node is in reality the union of untold numbers of sets yet to be dissected out as the tree is exhaustively developed.

The calculation of the numeric values is a three stage process,  involving a downward- ,  and an upward-,  process to get at  c,  followed by a determination of the d  value, composed as it is of 2a*3b,  by inspection of each entire l.d.a.  In a downwards process, subsets are dissected away from parental sets using eqn 2,  while keeping track of the c value of the yet incompletely differentiated subset.  In the upwards process,  the c value of the leaf set which terminates any particular l.d.a.  is propagated upwards using eqn 1 to determine the c values of every differentiated subset involved in that particular l.d.a.

In the downward process we repeatedly subdivide the sets determined for the parents in the developing abstract tree.  To determine the c value of subsets developed from a parental set,  c[d],  on the way down in the abstract tree, take 3 sets,  {c[3d]},  {(c+d)[3d]},  and  {(2c+d)[3d]}.  Together these represent the entire contents of  {c[d]}.  Of these three sets,  one will be entirely in {0[3]},  another in  {1[3]},  and the third in  {2[3]}.  That one in  {0[3]}  is a leaf set,  and does not develop further.  The two predecessor c values come from the current c by the b-step  (i=2) or the s-step  (i=1) by use of eqn 2.  An illustration of this downward process uses the dn+c formulation.

For every leaf set dissected and having a c value associated with it, one determines the c values for the specific subsets of the successor nodes on the way up in the predecessor tree by use of eqn 1.  An illustration of this process using the dn+c formulation appears.

The d value for any subset in the abstract tree is easily determined,  once its l.d.a. is known,  from the values of a and b of 2a*3b.  The a value and the b value of the header node are respectively 3 and the number of stages included in the l.d.a.  The a value increases by i and the b value decreases by 1 at each step in the downward path.  These changes are the result of the activities of eqn 2 which devour a power of  3 and supply i powers of  2 at each stage of the trajectory. Thus at the leaf node a is 3 plus the total number of  2's employed and the b value has gone to 1. 

A simple algebraic formula applies to rows  (and a similar one to columns)  of the cardinality table which is easily computed out to very large numbers.  The asymptotic values of the cumulative row  (or column)  thus obtained are simple fractions whose sums are 1,  thus proving that all the odd positive integers appear in the abstract tree.  That the row sums and the column sums approach asymptotic values is confirmed by a MapleV4 demonstration that,  in the limit,  the density of the sets among higher and higher numeric ***needs reference*** values approach zero for both the columns and the rows.

Note that the process employed as described in the last several paragraphs to dissection of the sets in the abstract tree into their components subsets can equally well be applied  (with minor modifications)  to an individual arbitrary number to discover the location of that number in the abstract predecessor tree.  This will be used in another argument below.

Each element of an  l.d.a. occurs repeatedly at intervals designated by its d value.  Thus,  each dn+c formula is applied  (or instantiated,  to use a term from object-oriented programming)  infinitely for all n in Z.  Whence the predecessor tree is infinite for three distinct reasons: 
(a) the abstract tree and its contained  l.d.a.s can grow without limit, 
(b) all the elements of all the l.d.a.s are infinitely instantiated,   and
(c) all the odd integers in the predecessor tree bear an infinite set of powers-of-two multiples.

This iterative subdivision of the sets into disjoint subsets and the subsequently mapping back into unique subsets of all the parental nodes clear through {5[8]} insures that l.d.a.s are composed of unique subsets disjoint from those of every other l.d.a. We have proofs of this point from Margaret Maxfield and Alexandre Buisse as well as a picture which makes the point graphically.

The sets become rapidly sparser as we descend in the abstract tree.  Infinite sets cannot be measured by cardinality,  which is an extensive measure.  But they may be measured by density,  an intensive measure.  The use of density, which is just a ratio of elements in a set defined over some defined range to the range's maximum possible contents, is reminiscent of the principle of Cavalieri which is said to be "quite rigorous".

We use the d of the c[d] or the dn+c descriptor of our sets of odd integers to evaluate each one's density as 2/d.   For example,  the density of the odd integers in 5[8] is 1/4 of all the odd integers.  When this set is subdivided the descendants are 1/3 as dense as the parent after one stage, then 1/9, then 1/27, ..., as successive generations are produced.

There is the question of whether the densities assigned to each element of the l.d.a.s accurately reflect the densities out at very high numeric values.   There is a page which discusses the point in some detail.  Suffice it to say here that we consider that every interval represented by the d value of the c[d] descriptor of the l.d.a. element starts at 3,  that every d value is a product of powers of 2  and 3,  and that successive d values across each row of the cardinality table is 2 times (and in the columns 3 times) that of the previous one.   Thus,  the intervals terminate at the same points, at 3 + the d value of the largest subset yet included in either rows or columns.   This combination of circumstances means that the densities observed and accumulated during the reckoning for smaller values of a (in rows) or b (in columns) will add accurately into the precise density applicable to each newly considered set at larger numbers.  Continuing on,  the densities can be added through sets of increasing,  but always finite, size.   It's finite sets with increasingly large numbers but decreasing densities all the way to infinity.

The various infinite summations suggested by the nested sets diagram indicate that
(a) the tree contains all the odd positive integers, 
(b) there are 3 times as many integers in the rest of the tree as there are in the root node, 
(c) there are as many leaf nodes  (l.d.a.  terminations)  in the abstract tree as there are l.d.a. header nodes. 

These are all relationships which clearly must hold if the infinite predecessor tree is to represent the totality of the Collatz trajectories.  This result might be regarded as based on too gross an accounting to be convincing,  so we turn to a much finer description of the contents of the predecessor tree.

Once l.d.a.s are completely mapped out,  giving dn+c formulas for every element of every l.d.a.,  we can use those d values to determine the density contribution of every set represented in the abstract tree.  But,  all the paths which lead to a given d value arrive by different routes which contain the same numbers of s- and b- steps, e(sxby)t,  in different orders.  We can take a new view of the abstract tree, in which each node represents all the instances of occurrence of each particular (x,y) combination.  Suddenly in this new view,  we are concerned with the number of ways any particular d value can arise to get at its contribution to the density of all the integers that node represents.

This combinatorial situation immediately recalls the Pascal triangle since it is exactly like the abstract tree in its shape,  and the values from the Pascal triangle give directly the multiplicity of appearance of the sets which share a d value.  If one draws "isobars" on the Pascal triangle at increasing powers of  2 in the d value, the total multiplicity at successive isobars turns out to be the successive Fibonacci numbers.  Computer runs developing the formulas for large numbers of  l.d.a. element sets followed by collection of those sets sharing the value d show that the cardinalities of these aggregates go as powers of  2 multiples of the Fibonacci numbers.  The double infinite summation over the rows and columns gives the result that the total density of the integers represented is exactly that required to account for the odd positive integers.  The summation at this much more detailed level again supports the notion that the predecessor tree contains all the odd integers and confirms the Collatz conjecture.

Some Other Confirming Approaches

(A)Still other observations may lend credence to the notion that the abstract tree contains all the odd positive integers.  One is the idea that l.d.a.s constitute a sieve which identifies all the odd positive integers.  This is not really different from the above summations,  but the notion of a sieve suggests a reach to infinity,  so it seems worth mentioning.  A program was written to check the creation of all the odd integers from the list of {c[d]} sets for l.d.a.s whose headers range up to 100,061.  Almost all the integers up to two million were discovered, and the very few which were not proved to be members of  l.d.a.s whose headers are >100,061.   Time and space will always prevent an exhaustive test of the notion that all odd positive integers will be reached by sieving using the complete set of  l.d.a.s.

(B)The fact that the predecessor tree is a directed graph,  with edges in the binary tree always pointing downward toward each integers predecessor,  immediately implies that all paths in the tree  (viewed with the edges reversed to point upwards to successors)  must reach the root at 1.

(C)Another approach to a proof  is the existence of an algorithm locating any arbitrary odd integer in the abstract tree.  Since the algorithm uses only the basic arithmetic operations which are clearly applicable to every magnitude of integers,  the algorithm must apply to all positive integers,  regardless of size.  If any odd integer can be located in the tree,  then the tree clearly contains every odd integer,  which would complete the proof of the Collatz conjecture.

(D)Since that algorithm places every integer uniquely in the predecessor tree, and we have already shown that every integer has its unique location in the tree, and that every tree node has its unique path to the root we conclude the following. There is a 1:1:1 mapping of (a) the unique odd integers into (b) unique positions in the predecessor tree, each with (c) unique paths to the root. Such a mapping avoids all the questions about accounting for the infinities involved.

Constructive Inductive Proof of Directed Tree from its Graphical Elements

The most direct and graphically self-evident proof arises from a stepwise construction of the binary predecessor tree from its constituent graphical fragments.  We start with the trivial tree which represents 1 looping to itself and having an outgoing edge to its extension.  We have an infinite collection of nodes to be placed in the growing tree, each with its odd integer label and with a set of directed edges appropriate to the value it bears, in accord with the following table.
(a) All nodes have a single incoming edge.
(b) If a node bears a value in {5[8]}, it will have an incoming edge from the upper left, otherwise from the upper right.
(c) All nodes have an outgoing edge to the lower right. 
(d) If a node has a value in {0[3]}, its only outgoing edge will be to the lower right. 
(e) If a node bears a value in {1[3]} or {2[3]} it will bear two outgoing edges, one to the lower left (to accommodate the next  l.d.a. element) and the other to the lower right (to accommodate the extension).

A few features of this deterministic tree growth may be mentioned. We start with the seed tree containing the two nodes representing the loop at 1, and a stockpile containing nodes prelabeled with the odd integers, each of the appropriate kind according to its value. The numeric labels are controlling as the tree grows.  Each newly attaching element is selected deterministically by calculating the needed value and selecting it from the value-labeled nodes in the stockpile.  The fact that there are no duplicated values in the tree means that every node will eventually be selected, and every integer will simply wait to be positioned.

Null extension headers and leaf nodes maintain the unsatisfied edge count preceding their insertion, but the other node types increase the unsatisfied edge count.  I.e, the number of unsatisfied edges of the tree grows monotonically,  since it starts at 1 and every added node either maintains the number of unsatisfied edges or increases it by 1.  Therefore it is impossible that the tree will "neck down":  it will always maintain the capability of further growth and must not only grow without restraint, but also with an increasing capacity for still further growth.

Certainly the only kind of graph that can result is an infinite binary tree.  We need not worry about the triple sources of infinity or their enumeration and identification in detail,  though that offered much diversion,  because the mere identification of the Collatz predecessor graph as a tree suffices to prove the conjecture.

My Collatz Home Page       Index to Terms Used