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 3*n*+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)/2^{i} examples which
**do** contain cycles
is applied to show that there are no non-trivial cycles in the Collatz
(3n+1)/2^{i} 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*+3^{j})/2^{i}

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
3^{j}. 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