Finite Sums in the Cardinality Table

Using a large file of formulas for the elements of the left descent assemblies (l.d.a.s) sorted into order of powers of 2(a) and 3(b),  the frequencies of occurrence of formulas involving identical (a,b) pairs was determined.  The resulting table revealed that the Fibonacci numbers offer a way of summing the density of the integers covered by the complete set of  l.d.a.s to determine the fraction of integers covered.

The alternative way to determine the total integer content of the abstract predecessor tree was to make a level-by-level accumulation of the number of integers reached during growth of the abstract predecessor tree.  Either way,  the infinite sums indicate that all odd positive integers are indeed covered.

Since these infinite sums may not play a convincing role in any rigorous mathematical proof of the complete coverage of the integers,  it seems important to pursue this line of argument by showing how the coverage of the odd integers increases in finite sums as the size  (hence the number)  of  l.d.a.s employed is increased.

This page goes into a great deal of detail about these finite sums which may be of little interest or import in the bigger picture.  Suffice it to say here that several different ways of approaching the detailed summations are developed,  explained,  and employed.  The fraction of the odd integers covered by the time l.d.a.s up to length 40 have been included is 0.9994 by the method which makes the smallest estimate,  and by inclusions of  l.d.a.s through a length of 100 is 0.9999999988 by the same method.   Other methods give consistently larger fractions.   The reader may skip to the table on the last screen of this page to gain an impression of the approach of the finite sums to unity as the size of the l.d.a.s is increased.

A first step in the direction of determining the densities/fractions of the integers covered by each entry in the cardinality table (as I shall call it here) was taken by preparing a second cardinality table which shows the contribution to odd integer coverage by individual (a,b) pairs as well as running sums across rows and down columns.  Running sums down infinite rows and across infinite columns (which involve infinite summations in only one of two dimensions) were also determined.  This is interesting,  but the limited size of the table prevents it from revealing the details of the approach to complete coverage as larger l.d.a.s are systematically added.

To gain a better understanding of the way the different finite summations fit on the cardinality table,  we first must show how individual  l.d.a.s fit on the cardinality table.  To this end, two diagrams are offered, one which shows paths for l.d.a.s of length 0 through 3,  and another which shows two very long l.d.a.s among integers <33000.  The first of those diagrams attempts to show by use of colored lines all possible paths from the header extension to the leaf for l.d.a.s of length 0 through 3.  The second shows the meandering paths which two lengthy l.d.a.s exhibit along with an upper and lower bound for the paths of those particular number of steps.

Unsaid (except for the 2000 words those diagrams represent) are all the implications for the coverage of the integers by the growth in the abstract predecessor tree and in the cardinality table.  To make those implications explicit,  two additional diagrams are offered which show various domains in the cardinality tables which are present,  missing, desirably measured,  undesirably measured, etc. for the 1:1 and a 2:1 triangular growth protocol and a 2:1 rectangular growth protocol in the cardinality table.

Since the figures indicating cumulative coverage of the integers in the second cardinality table do not extend to very long l.d.a.s, and no particular growth pattern is obviously the correct one to use,  a number of single- and double- finite sums were developed and their results presented below.  The summations were accomplished using Maple (with Digits at 25 or 50,  as required) to determine the coverage for larger and larger,  but nonetheless finite,  portions of the cardinality table.

The first summation which might come to mind is the finite sum counterpart of the infinite sum used earlier to indicate that all the odd integers are covered in the abstract predecessor tree.  The expression employed was

  evalf(add(2^i/3^(i+1)),i=0..n); 

The results,  in the first column below,  are not comparable to those in the other columns,  because the cardinality tree is based on formulas for elements of  l.d.a.s which are anchored at both ends,  while the abstract predecessor tree counts developing l.d.a.s anchored only at the header (extension) end.  This accounting based on the abstract predecesor tree makes the inclusion of all integers look much faster than the others.

One might then turn to a double summation which adds the elements in the cardinality table by diagonal after diagonal proceeding from the upper left toward the lower right.  The formula for this is

  evalf(add(add(2^(b-a)*f(a-2)/3^b,a=3..n-b+3),b=1..n+1));

and the results appear in the second column of the following table.  In this and the following expressions, f() denotes the Fibonacci series.

But then one notes that the magnitudes of the numbers reached in that reckoning is very much greater on the b-step side of the table than on the s-step side.  This bias was expressed in the experimentally developed cardinality table where the complete set of instances of an (a,b) pair was observed up to a at 22 and b at 11 in a run limited by the magnitude of integers considered.  This is consistent with the notion that 2 s-steps roughly equal 1 b-step and suggests that the triangle summed to determine the integer coverage should have twice the span in the a axis that it has in the b axis.  The formula employed for this summation is

  evalf(add(add(2^(b-a)*f(a-2)/3^b),a=3..2*(n-b-1)+3,b=1..n+1));

The results from this expression are given in the third column below.

Finally,  and simple-mindedly,  one could just make rectangular double sums down to a point in the cardinality table where the number of  s-steps is double the number of b-steps.  Such a reckoning overstates the result for b b-steps,  but understates it for 2*b b-steps,  as can be understood by considering a diagram which shows the areas included and excluded by the use of a rectangular sample.  The following double summation expression, which has much less complicated indices (therefore more likely correct),  was employed.

  evalf(add(add(2^(b-a)*f(a-2))/3^b,a=3..m,b=1..n));    

The results are in the fourth column of the following table.

The first entry in each of the first 3 columns is n. The depth of penetration into the abstract predecessor tree is measured by n,  which is the number of b-steps, which corresponds to 4^n in the characterizing coefficient, which is the same as 2^2n which arises from 2n s-steps.  In the fourth column the first entry is an (a,b) pair,  where b is chosen to correspond to the value of n in the other entries in the same row.  Thus,  comparison of the fractions of coverage across the row is justified,  always keeping in mind that the first column is based on l.d.a.s anchored only at the top.  When the results start with a sequence of 9's,  the notation 9(x) is employed to indicate that x consecutive 9's begin the value.

  triangle in    1:1 triangle in    2:1 triangle in    rectangle in
  abstract tree  cardinality table  cardinality table  cardinality table
  -------------  -----------------  -----------------  -----------------
  n  result         n   result         n  result            (a,b)  result
  -  ------         -   ------         -  ------            -----  ------
  4  .86831         4   .38927         4  .62632            (11,5) .74621
 10  .98844        10   .79835        10  .94403           (23,11) .97751
 15  .99848        15   .92713        15  .9903329         (33,16) .99715
 20  .9997995      20   .97435        20  .9984511         (43,21) .99964
 25  .9999736      25   .99106        25  .9997629         (53,26) .9999544
 30  .9(5)652      30   .99689        30  .9999648         (63,31) .99999422
 40  .9(7)397      40   .9996277      40  .9(6)2692        (83,41) .9(7)0625
 50  .9(8)895      50   .9(4)5515     50  .9(7)8559       (103,51) .9(8)8476
 75  .9(13)586     75   .9(6)6657     75  .9(12)30384     (153,76) .9(13)4663
100  .9(17)836    100   .9(8)8879    100  .9(16)69293    (203,101) .9(17)8061

I believe the third column is the best selection. But clearly,  all of these measures indicate the coverage of the integers can be made arbitrarily close to 1 by continuing to increase the size of the l.d.a.s.  Integer coverage is essentially complete when the abstract predecessor tree has been grown to include moderately long l.d.a.s.

This table seems to provide an "engineering proof" of the complete coverage of the integers by the predecessor tree,  and that all the integers will easily be covered without any infinite l.d.a.  This is all based on the utility of the densities of the integers of each 2^a*3^b*n+c formula for each l.d.a.  element in determining the integer coverage.   This dismisses the appearance of a paradox which arises because all these sets of  l.d.a.s elements are infinite.


My Collatz Home Page       Index to Terms Used