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]}.
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. .
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 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: 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
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.
(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.
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 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.
(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.
(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.
Some Other Confirming Approaches
Constructive Inductive Proof of Directed Tree from its Graphical
Elements
(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).
My Collatz Home Page
Index to Terms Used
