Synopsis

This page dates from about 2005. Perhaps a more timely page would prove mode useful. The current approach makes no use of state transition diagrams.

The principle contribution of this work is to provide a new viewpoint for the Collatz 3n+1 problem.  This synopsis will hardly even introduce the subject,  but it will mention the highlights and suggest a way in which a proof of the conjecture might be teased out of this viewpoint.  Hopefully,  this will interest the reader to pursue a more careful reading of all these pages,  and serve to focus attention on the main line of the argument among what might otherwise appear to be (and sometimes are)  long and rambling excursions.

The nomenclature used here derives not from the predecessor tree,  rooted in 1,  in which every integer which is a predecessor in the Collatz sequence of a parental node appears in ascending order as its children,  but from its transform into a binary tree.  It emerges that the Collatz steps which involve but 1 or 2 divisions by 2 appear as "left descents" in the binary tree,  and the steps involving 3 or more divisions by 2 appear in right descents which are called "extensions" since all give the same Collatz successor.  Thus,  the binary predecessor tree for the Collatz trajectories contains sets of "left descents" and "extensions".  The latter consist of the odd integers congruent to 5 mod 8,  and the former of the odd integers congruent to 1,  3,  or 7 mod 8,  and extensions and left descents are therefore disjoint.  Extensions head every left descent and every node in the tree has an infinite set of extensions.  This dissection of the tree into its component parts, left descent assemblies (l.d.a.s) and extensions, is the basis for this work.

The binary predecessor tree may be collapsed into an abstract predecessor tree ,  a tree all of whose nodes are infinite sets of integers,  simply by gathering all the extensions into a set as the root.  Thus,  the root node,  (as well as all the other nodes)  of the abstract predecessor tree consists of an infinite set.  The l.d.a.s which come with the extensions will be the basis for elaboration of the whole abstract predecessor tree.  Its growth is followed in detail by determining which elements of a parental set will have children which involve a single division by 2 (called s(small)-steps),  which involve 2 divisions by 2 (called b(big)-steps),  and which are leaf nodes.  The growth continues indefinitely,  defining all possible combinations of b and s steps to form the left descents.  To reiterate,  the left descents are limited to steps invoking only 1 or 2 divisions by 2 in the Collatz trajectories,  can grow to arbitrary lengths,  produce only integers in {1,3,7} mod 8,  and exist with every possible combination of b and s steps for every length.

The node contents in the abstract predecessor tree are described using formulas d*n+c,  (i.e.  conguent to c mod d, also denoted at times as {c[d]})  where d and c are characteristic for the node contents and n is in {0..infinity}.  These formulas are derived by traversing in each left descent down to leaf nodes and up again to the parental extension.   These formulas represent mutually disjoint subsets.  Effectively this down-and-up process maps (projects?)  all the leaf set contents back through all intervening levels of the abstract tree into the root extensions,  assigning arithmetic progression formulas (d*n+c or {c[d]}) to every node in the path in the process.  The coefficients d are products of powers of 2 and 3,  c is odd,  and c<d. Any path from a leaf node to an extension in the abstract tree corresponds to an l.d.a. 

An arbitrary odd positive integer can be located in the abstract predecessor tree by a numerical algorithm which identifies its left descent,  its element within that left descent,  and which instantiation (value of n) of that left descent it is in. 

The big picture is that the arithmetic progressions are thus grouped together in sets (called left descent assemblies or l.d.a.s) consonant with the Collatz trajectories.  The algorithm which locates an integer in the abstract tree depends on simple arithmetic operations (and solution of a linear equation for n)  which are surely shared by all integers.  Any (every)  odd integer can be mapped in this way,  a fact which will lead to the claim that the Collatz graph (a tree) does reach all the odd integers.

The first instance in numeric order of the extension (header) of any given left descent can be regarded as a sieve  which marks all subsequent instances.  Proceeding iteratively,  every unmarked extension heads an additional left descent which sieves its infinite instances.  This description of the odd integers is somewhat similar to Eratosthenes' division of the integers into primes and composites.  It provides an alternative way to see that any integer may be found in the l.d.a. units which occur during the Collatz trajectories, and thus that the trajectories include every integer.

The paths from extension to leaf node in the abstract tree are left descent assemblies,  composed of a header extension and zero to many left descent elements.  Any given element of an l.d.a.  has a constant density across all integer magnitudes; the "thinning" required among large integers is achieved through larger and larger values of d and c among long,  less frequent left descent assemblies. The densities of the integers in the nodes add to 1,  indicating that enough room is there to contain all the odd integers.  The nodes in the abstract predecessor tree are all disjoint,  and the integers within any given node are just an arithmetic series.  If one dared apply the pigeon-hole principle to an infinite set of disjoint odd integers,  all odd positive integers must be present in the abstract predecessor tree. 

There is an interesting anomaly here.  The idea that one in four of the odd integers is an extension while one in three of them are leaf nodes would seem to indicate that the average l.d.a. would have their leaf node 4/3 greater than their header.  Yet from the formulas the average ratio works out to 1.  This seems to be an example of the kind of paradox frequently enountered while reasoning about infinite sets.

If one had full faith in the infinite summations of densities which indicate that all positive odd integers appear in the abstract predecessor tree and in the applicability of the pigeon hole principle in such a bizarre case,  one would say that this proved the Collatz conjecture.  A better argument is needed and we now turn to arguments about the directed graph which is the binary predecessor tree.

The edges in the state transition diagram and the abstract predecessor tree are directed;  the Collatz trajectory direction is opposite to the predecessor direction.  Because l.d.a.s from the abstract tree map piecewise into the binary tree, the edges in left descent assembly are directed as well.  The full utilization of the degree of each node in forming the edges during the construction of the precdecessor trees disallows any cycle superimposed on the tree structure.  The unique placement of every integer in the trees prevents any integer from being a successor element in one place in the tree and a predecessor element in another,  thus precluding the existence of cycles from that source.  More basically,  no cycles can appear in any capacity in the predecessor graph because any imagined cycle must follow the Collatz trajectory consistently in one direction or the other (predecessor direction or successor direction,  it doesn't matter to the argument) and any such path will contain one or more edges contrary in direction to the directed edges of the state diagram and the derived abstract and detailed predecessor trees.   (A contribution has appeared in which information gained from (an+b)/2i examples which do contain cycles is applied to show that there are no non-trivial cycles in the Collatz (3n+1)/2i iteration.)

We are not able to map any given l.d.a.  instance into its precise position in the binary predecessor tree,  but we do know that every instance of an l.d.a.  from the abstract tree maps as a unit somehwere into the binary predecessor tree.  The extensions which head all l.d.a.s join their parental l.d.a.s in the binary predecessor tree at some element,  even possibly the leaf element,  of an l.d.a.  to its left.  Thus,  while we do not know the location of any l.d.a.  instance in the binary predecessor tree,  we do know its behavior wherever it may be located.  The Collatz trajectory from any of its elements will move up and rightward in its left descent to its header extension and then up and leftward to the integer parental to the extension set which contains this original l.d.a.  That integer is again in an l.d.a.,  located within the binary predecessor tree,  and will behave in the same way when run through its Collatz trajectory,  with the identification of another integer in another l.d.a. parental to its header extension.  Continuing iterations must eventually reach the root.

This argument depends on two key points.  (1) Any integer can be located within the abstract predecessor tree by a process of simple arithmetic manipulation to which all integers are susceptible.  This excludes the existence of a graph separate from the binary predecessor tree in the Collatz graph.  (2) The argument that all l.d.a.s behave as described assumes that there is no infinite (divergent) l.d.a.  (The l.d.a.s may be indefinitely long,  but any given l.d.a.  has a precise,  though possibly large,  length and longer and longer l.d.a.s appear with smaller and smaller frequency.)  If these arguments are supportable it would seem that the proof outlined will be successful.

It appears that there is an infinity of Collatz-like iterations on the integers each of which converges to a single integer, namely
      (3*n+3j)/2i

where i is the largest integer power of 2 which results in an integer and j runs from 0 to infinity. These each converge to 3j. The details of the predecessor tree for each j vary remarkably in such a way that it appears unlikely that this family of examples will shed light on the original j=0 case. The predecessor trees do not lend themselves to an assessment of the density of the integers contained therein, so the only indication that the predecessor graphs are indeed trees is a graphical one.


My Collatz Home Page        Index to Terms Used