Although a great deal had been learned (October 2007) about the structure of the Collatz iteration, some features seemed to require additional work.
One such was my continued worry that some readers would not be satisfied that the congruence sets were completely utilized and distributed as required in the predecessor tree. Recall the dissection of the abstract tree in a top down manner, identifying but only partially filling, congruence sets along the way. No demonstration has been made that the congruence sets of the abstract tree are completely filled in the upward portion of the binary tree development process.
Another compelling notion is that, if the abstract tree were shown to contain completely filled congruence sets, it would follow that the inductive constructive proof of the Collatz conjecture might be founded on congruence sets rather than individual integers as at present.
One approach to a program to test the completeness of the congruence sets (congruence sets program) could do the downward development of the abstract tree in the familiar manner and keep a data set of the nodes visited to contain the density of the integers in congruence sets accumulating at every level of the traversal of a path in the tree. Whenever a leaf node is encountered in the traversal, the density of integers in the path above it need to be added to the accumulating density of every node in the path of the abstract tree above it back to the root. The hope was that the densities of the integers would accumulate to create a recognizable pattern of completely filled upper level congruence sets. In the end this hope was not fulfilled because certain difficulties were not overcome, but the experience gained and the data gathered at the individual left descent assembly level led to a satisfactory result (see below) using infinite summations of the densities of the integers in the congruence sets at successive powers-of-2 levels of the abstract tree.
Of course, the infinite size of the Collatz predecessor graph places serious limitations on the obtainable precision of the accumulated densities. One possible approach might have been to take snapshots of the results of the csetidea program at a series of modest depths which would result in improving precisions as a larger and larger fraction of supplementing densities were included, and then extrapolate the answers for each congruence set. One might expect to find convergence of the values for any particular congruence set to approach the value which would result from the fully precise run if only it were possible. This approach was not pursued because the desired result was obtained more directly, and the faulty counting of the integer densities on each left descent assembly was never completely corrected.
In spite of the difficulties, certain very interesting results were noted which lead the way to a more accurate conception of the structure of the congruence sets in the abstract prdecessor tree.
One issue which requires better understanding and careful watching is a power of 2. It has to do with the conversion of the d of c[d] to a density in the congruence set characterized by c[d]. Early on, I was using 2/d; now I think I should use 1/d, especially in progams which deal directly in congruence sets. Using all the integers (even and odd both), exactly one integer in d is in the congruence set characterized by c[d], so the density would be 1/d. In cases where only odd numbers are represented, there are only d/2 integers in each numeric interval d, only one of which is odd, so the density is 1 in d/2 or 2/d.
The recent troubles have been that the csetprog, in which d/2 was used as the density measure for c[d], consistently and (up until now) mysteriously over-estimated the density of integers within the congruence sets dependent from the header of any subtree of the Collatz prdecessor tree in spite of several efforts to eliminate some of the obvious causes deriving from replicative identification of subsets while tracing the "upward" paths. And in the approach which follows, how does one determine whether the predecessor graph is limited to odd numbers or is comprehensive of both odd and even integers?
The following segments of output lines from csetprog are the result of sorting them by columns 1, 2, 3, 5, and 6. (Those useless integer densities and density sums fields are dropped.) The three segments have power-of-two values of 0, 1, and 2. Note that in each case the congruence sets of the left descent assemblies headed by a particular branch of the predecessor tree produce d values in the "upward" direction whose cardinality goes 1, 2, 4, 8, ..., a pattern which goes on until the program limits stop the further production of output lines.
modified lda cdown ddown lda at leaf cup dup
e 5 8 e 5 8
e 5 8 es 5 24
In 'e' there e 5 8 eb 13 24
are no powers e 5 8 ebs 13 72
of 2 in its e 5 8 esb 29 72
d-value e 5 8 ebb 37 72
above the 2^3 of e 5 8 ess 53 72
the 8. e 5 8 ebss 13 216
e 5 8 esbb 29 216
e 5 8 ebbs 37 216
e 5 8 esss 53 216
e 5 8 esbs 101 216
e 5 8 ebbb 109 216
e 5 8 essb 125 216
e 5 8 ebsb 157 216
In 'es' there is es 3 16 es 3 16
a single "extra" es 3 16 esb 19 48
power of 2 in es 3 16 ess 35 48
16. es 3 16 esbb 19 144
es 3 16 esss 35 144
es 3 16 esbs 67 144
es 3 16 essb 83 144
es 3 16 esbss 67 432
es 3 16 essbb 83 432
es 3 16 esbbb 163 432
es 3 16 esssb 179 432
es 3 16 esbsb 211 432
es 3 16 esbbs 307 432
es 3 16 essss 323 432
es 3 16 essbs 371 432
In 'eb' there eb 17 32 eb 17 32
are two "extra" eb 17 32 ebs 17 96
powers of 2 in eb 17 32 ebb 49 96
32. eb 17 32 ebss 17 288
eb 17 32 ebbs 49 288
eb 17 32 ebbb 145 288
eb 17 32 ebsb 209 288
eb 17 32 ebssb 17 864
eb 17 32 ebbsb 49 864
eb 17 32 ebbbs 145 864
eb 17 32 ebsbs 209 864
eb 17 32 ebbss 337 864
eb 17 32 ebbbb 433 864
eb 17 32 ebsss 593 864
eb 17 32 ebsbb 785 864
The first column shows the header of the left descent assembly whose path is being traced, accompanied in the second and third columns by the left descent assemblies are given in column four with each one's c[d] values in columns five and six, so that the values ascribed to each parent of the traversal appear side-by-side with those of its dependent left descent assemblies on each output line. The ready availability of these c[d] values of columns five and six was the feature which unexpectedly provided the new view of the distribution of the congruence sets in the abstract binary prececessor tree.
Note that the three blocks presented above represent examples of no (extra -- only the 2^3 of the 5[8] congruence set) powers of 2 (in e and its fill-ins), one extra power of 2 (in es and its fill-ins), and two extra powers of two (in eb and its fill-ins).
There is an additional subtree consisting of ess and its fill-ins which also has two extra powers of 2 beyond those of 5[8] in its d value. Note that the d values throughout exactly agree with one another in eb and ess, while the c on the dependent left descent assembly elements differ throughout. These same relationships are observed in higher cases of powers of two, where there are largers numbers of subtrees sharing a given power of two.
ess 23 32 ess 23 32
ess 23 32 esss 23 96
ess 23 32 essb 55 96
ess 23 32 essbb 55 288
ess 23 32 esssb 119 288
ess 23 32 essss 215 288
ess 23 32 essbs 247 288
ess 23 32 essbbb 55 864
ess 23 32 esssss 215 864
ess 23 32 esssbb 407 864
ess 23 32 essssb 503 864
ess 23 32 essbsb 535 864
ess 23 32 essbbs 631 864
ess 23 32 esssbs 695 864
ess 23 32 essbss 823 864
The next step is to look at the accumulation of integer densities due to these systematic relationships. This reckoning does not depend upon the choice of a particular relatonship between integer density and the value of d. Instead the total number of conruence sets, c[d], is accumulated and a single integer is assigned every instance. By avoiding any specific density accumulation, the question of deciding between two density values is begged.
Both the number of dependent congruence sets with a given d value and the number of powers of two containing the common d value contribute to the determination of the density of the congruence set. When the d value is factored into its powers of 2 and 3, and combined with the power of 2 value for the cardinality of its appearance, the expressions in column 4 of the following table give the densities in column 5 of the dependent congruence sets at the successive levels i for i=0,1,2... . Column 6 then gives the sum over i=0..infinity of the densities across the value of i.
e 5 8 2^(i-3)/3^i 1/8,1/12,1/18,1/27,2/81... 3/8 es 3 16 2^(i-4)/3^i 1/16,1/24,1/36,1/54,1/81... 3/16 eb 7 32 2^(i-5)/3^i 1/32,1/48,1/72,1/108,... 3/32 ess 23 32 2^(i-5)/3^i . 3/32 ebs 3 16 2^(i-6)/3^i 1/64,1/96,1/144,1/216,... 3/64 esss 15 64 2^(i-6)/3^i . 3/64 esb 25 64 2^(i-6)/3^i . 3/64 ebb 65 128 2^(i-7)/3^i 1/128,1/192,1/288,1/432,... 3/128 ebss 7 128 2^(i-7)/3^i . 3/128 esbs 59 128 2^(i-7)/3^i . 3/128 essb 73 128 2^(i-7)/3^i . 3/128 essss 95 128 2^(i-7)/3^i . 3/128
Since the c values differ from one another for all the left descent assemblies which share a given d in the table (i.e. the same power-of-2), these families of subsets differ from one another and can be lumped together without introducing duplication in doing a summation in the vertical dimension of the table. Using j to represent the powers-of-2 in a row or a series of rows grouped by their common c/d values, the summation of 3/2^(j+3)j=0..infinity will give the total density of the integers in the entire predecessor tree of congruence sets, exclusive of the root 5[8]. That sum is 3/4. This is correct because the entire membership of 5[8] appears in the root of the tree, and that one congruence set's integer density is the missing 1/4.
To summarize, the program csetprog has produced quite a lot of new understanding about the Collatz predecessor tree. Perhaps foremost is the successful construction by the program of the predecessor tree viewed as consisting of congruence sets. Beyond the production of huge amounts of detailed information about the placement and organization of the fill-in integers in the higher portions of the tree by tracing the paths of left descent assemblies upwards, the program's output proved to contain systematic features from which it was shown using infinite summation in two dimensions that all the odd positive integers are included in the predecessor tree. Thus, the program is tantamount to proof by construction that the predecessor tree is infinite and contains all the odd positive integers. The program thus completes a proof of the Collatz conjecture.