Infinite Sums over the Abstract Predecessor Tree and the Table of Cardinalities

The predecessor trees must contain all the integers if the Collatz conjecture is true.  There turn out to be a large number of different ways to determine the total content of the abstract predecessor tree.  Some are so generic as to be of little more than passing interest.  These are given first.  Eventually we capitalize on various threads of information gleaned along the way to make much more satisfying "counts".

The prose here often repeats in good measure the arguments already given elsewhere.  Perhaps this may be excused as an attempt to reach readers who are not quick to grasp and piece together the various elements of argument here.

A word of explanation may be helpful.  Everything we are "counting" here is infinite.  We don't really count to infinity.  Instead we use more indirect approaches.  In the first portion of the following,  we count paths as they are formed in the abstract predecessor tree.  Subsequently,  we take advantage of the complete subsetting of the nodes of the abstract predecessor tree and the formulas which characterize each subset (anchored at both top and bottom so that they are unique)  to calculate the densities of the integers contributed by each and show that the densities of the subsets add correctly to account for all the odd integers >=3. When we add up the contributions by the members of various sets among the odd integers in order to show that the contributions sum to all the odd integers,  we base the summations on different starting sets so the sums may be 1/2 or 1 or 2 or 3 or 4,  as appropriate in each case.  Each summation could easily be rescaled,  but it would introduce an unnecessary awkwardness in the introduction of each instance.

The Maple V Computer Algebra System was used extensively in this work.  Results lifted from Maple V sessions are included below (and elsewhere in these pages)  with a Maple command prefixed by a greater than sign (">")  and the Maple response centered immediately below.

First we will consider the paths developed from the elements of the extensions set.  There should be a termination for every path even though the paths may be arbitrarily long.

The abstract predecessor tree starts with an infinite set of extensions whose values modulo 3 are in {0,  1,  2}.  One-third of these (those congruent to 0)  bear no left descents (hence are called leaf nodes)  and may be immediately regarded as finished paths.  The other two-thirds fall into two equal-sized disjoint sets whose members are congruent to 1 or 2 modulo 3.  Their elements are all the parents of children,  hence continued paths.  These children are equally {0,  1,  2} modulo 3 and will be subdivided for further development of the paths of the predecessor tree identically.  Thus,  one-third of each of the two branches (i.e.  2/9 in all at this level)  are barren (leaf nodes) ,  and represent newly terminated paths.  This process continues iteratively.  In the next stage there are 4 disjoint subsets in which 1/3 are leaf nodes,  totaling 4/27 of paths terminated at this level.  Thus,  the terminated paths accumulate as 1/3 + 2/9 + 4/27 + ...  as the predecessor tree is constructed level by level.  Inductively,  we expect an infinite descent with terminated paths accumulating as the sum of 2**i/3**(i+1).

Assertion: this formulation applies whether we are considering the infinite set of elements in the extension set of any integer or the totality of the elements of all the extension sets in the predecessor tree.  The validity of this shift of viewpoint may be questionable.  We will argue later that it is justified.

> sum(2**i/3**(i+1),  i=0 ..  infinity);

                                  1

There are as many paths to leaf nodes as there are extensions.  Considered in the small,  this says the elements at any stage in the predecessor tree will eventually reach a leaf node to terminate its path.  Considered as a totality,  this encompasses all the leaf nodes in the predecessor tree including the barren elements in the extension sets.  All left descents terminate.  We started by assuming that only extensions head left descents,  and now we see that every left descent terminates at length.  Could it be that all those left descents actually contain all the odd integers?

So let's turn to the total number of integers in the predecessor tree,  by summing the elements which accrue in the paths whether they are leaf nodes or internal nodes in the predecessor trees.  The first generation in the left descents,  immediately below the extensions,  has 2/3 of the original number of paths/extensions because of the loss of 1/3 to leaf nodes.  The left descent nodes produced from it are equally {0,1,2} modulo 3,  and thus divide again into leaf nodes,  b parents and s parents.  The second generation has 2/3 the number of paths of the first generation or 4/9 the number of paths of the original set of extensions.  Thus,  the expression for the total number of nodes in the left descents goes as 2/3 + 4/9 + 8/27 + ...  ,  i.e.  as the sum of 2**i/3**i,  based on the number of extensions.

> sum(2**i/3**i,  i=0 ..  infinity);

                                 3

This expresses the total content of the predecessor tree dependent from the parental extension nodes in terms of the content of the parental set.  There are three times as many left descent elements as there are extension elements.  Since 1/4 of the odd integers are congruent to 5 mod 8,  this establishes that there is the correct density of left descent elements.

Let's complete the balance sheet by accounting for the internal left descent elements,  those which are parental to another left descent element.  The difference between the entirety of each level (2^i/3^i)  and the leaf nodes in it (2^i/3^(i+1))  will give the internal nodes in it.  This expression simplifies as follows to a ratio of powers of 2 and 3.

> 2**i/3**i - 2**i/3**(i+1);

                                   i        i
                                 2        2
                                ---- - --------
                                   i     (i + 1)
                                 3     3

> simplify(");

                               (i + 1)  (-i - 1)
                              2        3

 

And that expression,  2**(i+1)/3**(i+1),  may be summed to discover the total number of internal nodes in the Collatz predecessor tree as a multiple of the number of elements in the extensions.

> sum(2**(i+1)/3**(i+1),  i=0..infinity);

                                 2

This just reinforces (what we already knew) that the 1/3 of all non-extension nodes which are congruent to 0 mod 3 are leaf nodes and the other 2/3,  those congruent to 1 or 2 mod 3,  are child-bearing and therefore internal to the tree.

The summations show that the left descents account for three times as many odd integers as the {8n+5} extensions.  The extensions account for one-quarter of the odd integers.  In the left descents,  2 times as many nodes are internal as are leaves.  Together the leaves and internal nodes in the predecessor tree constitute the 3/4 of the odd integers not accounted by the extensions.  Thus,  the entire set of odd integers is accounted for.  Not only have we been able to characterize the extensions and the left descents in terms of the subset of integers which constitute them,  we have also accounted for their proportions in a consistent way.

In support for the just preceding and the following paragraphs,  we must point out that the densities being added in every case are constant across the orders of magnitudes.  Thus,  the density of integers congruent to 5 mod 8 (aka 'in {8n+5}')  among the odd integers is 1/4.  The only precaution we need take is to sample exactly 4 or a multiple of 4 consecutive odd integers.  We will find that 1/4 of the sample is always congruent to 5 mod 8 and the other 3/4 is not.  This will be true whether we look at small numbers or immense numbers,  and whether our first sampled odd integer is congruent to 1,  3,  5,  or 7 mod 8 because the residues cycle through their values in a fixed order.  Every formula of the form d*n+c will have a density of representatives equal to 1/(d/2)  or 2/d,  provided only that d/2 consecutive odd integers are inspected and independent of the phase of the sampling.  Since we want to sample the integers fairly,  we will always start at 3.

Of course,  when we add the densities,  we must assure ourselves that the sets which are used in establishing them do not overlap,  else there would be an overcount made.

We turn now to the figures which represent the complete down and up-again development of the formulas representing the contents of all the subsets in the predecessor tree when separated into the subsets contained in the various completed left descents.  We wish to capitalize on the 1:1 mapping of leaf nodes back up the paths to their origins in the extensions to show that the extensions and the leaf nodes are 1:1.  If that can be shown,  then the utility of the set of all extensions as the root node in the abstract predecessor tree is supported.  Unfortunately there is still no assurance that some of the extensions included in the root node are not actually ones in the tree of counter examples. It turns out that this viewpoint gives the same result as summing all the leaf nodes in the tree,  but this time we are can see more clearly that the contribution of subsets to every parental node all the way up to the extensions behaves just as we observed for the entire tree earlier.

The rightmost filled column in each row of the up-again process represents the subsets of the 8n+5 set whose destiny has been worked out down to a depth of three or four.  The density of "et" leaf set is exactly that 1/3 of the 8n+5 set which is congruent to 0 mod 3.  Each of the entries in the second column,  the "ebt" and "est" sets,  second and third rows,  represent densities of exactly 1/9 of the original 8n+5 set but there are two of them.  Each of the entries in the third column,  rows three through six,  represent exactly 1/27 of the density of the original 8n+5 set but there are four of them.  Of the eight sets each accounting for 1/81 of the original 8n+5 set only three are shown,  but there are eight of them.  Clearly this relationship will continue indefinitely and we may sum the fractions of the odd integers which will be covered in all.

> sum(2^i/3^(i+1), i=0..infinity);

                                  1

Thus,  the sets constituting the abstract predecessor tree are completely subsetted and accounted for by projecting subsets identified from leaf nodes back into them.  That is not a different summation,  but it arises from a different viewpoint from that which first resulted from a count of the number of leaf nodes descendent from the extensions.  Perhaps this could be regarded as an indication that the paths from extension to leaf node do not branch; there is an undeviating path from extension node to leaf node for each path.

All the above summations use the paths in the predecessor tree level-by-level to account for the integers identified in various ways.  However,  the predecessor tree is lop-sided since,  in any given generation,  the integers reached in the left side where s steps predominate are smaller than those reached in the right side of the tree where b steps predominate.  In other words,  the density of integers reached by equally long paths with predominately s steps is greater than those reached by paths with predominately b steps.  This suggests that a more satisfying accounting might result if the summation were done using a view of the tree which was more balanced in terms of the magnitude of numbers reached.

Fortunately,  the distribution of cardinalities of formulas bearing successive values of a for a given value of b in the coefficients,  2^a*3^b,  over a very large set of such formulas (where the Fibonacci series makes an appearance)  provides exactly such a basis.  The reason the Fibonacci numbers appear is evident upon inspection of the selection of sets of binomial coefficients which apply to any given power of 2 depth.  This relationship is fully explored elsewhere on the web.

Furthermore,  the various fractions of the Fibonacci series which appear for a given value of b in that table of cardinalities have closed sums because the sum(F(i)/2^(i+1),i=1..infinity)  is 1,  where F(i)  are the Fibonacci numbers.  I.e.  the sum of 1/4 + 1/8 + 2/16 + 3/32 + 5/64 + 8/128 + 13/256 + ...  is 1. A related infinite sum substituting 10 for 2 in the denominator has been fully explored . Substituting 2 for 10 in the derivation gives 1/(4-2-1) or 1/1 in the penultimate step, thus proving the above relationship.

The contribution of the density of the integers in each cell in the relevant table to the total number of integers is its entry (its frequency of occurrence)  divided by 2^a*3^b  (its density among the integers).  Each row will make a smaller contribution than that of the Fibonacci series sum in the inverse ratio to that of its divisor to 4,  the first denominator in the Fibonacci sum,  above.  For the first row (b=1),  the first divisor is 24,  or six times the first denominator in the Fibonacci summation,  so the first row (whose cardinality starts at 1)  contributes 1/6 of the density of the integers.  For the second row (b=2),  the first divisor is 72,  or 18 times the first Fibonacci denominator,  but the weight is 2  (since the cardinality starts at 2),  so 2/18 or 1/9 is contributed to the density of the integers.  For the third row (b=3),  the first divisor is 216,  54 times the first Fibonacci denominator,  and the weight is 4,  so 4/54 or 2/27 is contributed to the density of the integers.  For the fourth row (b=4),  the first divisor is 648,  162 times the first Fibonacci denominator,  the weight is 8,  so 8/162 or 4/81 is contributed to the density of the integers.  Continuing on,  it becomes evident that the second and subsequent rows are contributing 2^i/3^(i+2)  each.  Even the initial row fits this at i=0, so the total density will be the sum(2^i/3^(i+2),i=0..infinity)  or 1/2,  or just enough to cover all the odd integers.

There is no possibility that even integers confuse accounting since the whole genesis of the table is concerned with odd integers only. 

This summation adds no new information to that obtained above -- it continues to say that all the odd integers are reached.  Since it was obtained from a much more detailed analysis and a deeper level of insight it should be regarded as a stronger result.  Also it is pleasing to be looking at a more nearly "balanced" tree in terms of the magnitude of numbers reached at any given depth.

These ideas will receive a still more thorough discussion in a later section devoted to examining various finite sums of the contents of the abstract tree and of the cardinality table.


My Collatz Home Page         Index to Terms Used