State Transition Diagram for Steps Within One Left Descent Assembly (L.D.A.)

I'm using here the French notation in which a[b] denotes congruence to a mod b.

I define l.d.a.s as those paths in the binary Collatz predecessor tree headed by an extension {5[8]},  and including any/all left descent elements until terminated by a leaf node {0[3]}.  The header extension and the leaf node are both included in the l.d.a.  This structural feature has proven itself for dissecting the Collatz predecessor tree to develop an oversight useful in analyzing the Collatz trajectories.  For this purpose,  it is necessary that extensions do not arise as internal nodes in any l.d.a.  Extensions are extended only to form infinitely many extensions,  some of which head new l.d.a.s and others which are leaf nodes themselves.

To examine this,  I've produced a state transition diagram which compactly represents the allowed transitions within l.d.a.s.  [Finding a good reference to state diagrams on the internet isn't easy, but try the cola machine (on page 4). Do you see the error there? ] The nodes of a state diagram indicate the various states an odd positive integer can exist in,  and the edges indicate which transitions may occur among them under the Collatz predecessor transformation rules.  The states are characterized by their values mod 3 and mod 8.  In the diagram,  the nodes are color coded to indicate their values mod 8 and the edges colored to indicate their path types,  'b' or 's',  as determined by their initial node's values mod 3.

We are concerned with the odd positive integers with respect to their congruences mod 3 and mod 8.  The value mod 3 determines whether an odd integer is a leaf node in the Collatz predecessor tree or is the parent of an 's' or a 'b' step.  For a 'b' step (from any 1[3]), the Collatz predecessor is calculated using (4*n-1)/3 and for an 's' step (from any 2[3]),  the Collatz predecessor is calculated using (2*n-1)/3.  Since we consider only the odd integers,  there are just four values mod 8 to look at:  1[8],  3[8],  5[8],  and 7[8]).  We are not concerned with leaf nodes (i.e. all 0[3]) because leaf nodes do not head l.d.a.s and always terminate l.d.a.s.  A leaf node is the only element which can terminate an l.d.a.  Thus only eight states need be shown,  two (1[3] and 2[3]) mod 3,  in combination with the above four mod 8.

The state transition diagram doesn't show the transition from the penultimate element of an l.d.a. to the leaf node;  including that transition would just involve adding an arrow from each node in the diagram pointing to a collective leaf node.  The l.d.a.s which consist of a single header/leaf,  e.g.  21[24] also are not depicted.  In principle,  an l.d.a.  can continue indefinitely,  but as the length of an l.d.a.  increases its density of occurence rapidly decreases so lengthy l.d.a.s are relatively rare.

The odd integers 5[8] which start (head) l.d.a.s are shown as the red nodes A and B in the state diagram.  Working through all possible transitions from each possible state allows construction of the complete transition diagram.  The following table provides the basis for the edges in the state transition diagram.

            from        step                results
        A  1[3]  5[8]     b  -->  C  1[3]  1[8] and D  2[3]  1[8]
        B  2[3]  5[8]     s  -->  E  1[3]  3[8] and F  2[3]  3[8]
        C  1[3]  1[8]     b  -->  C  1[3]  1[8] and D  2[3]  1[8]
        D  2[3]  1[8]     s  -->  E  1[3]  3[8] and F  2[3]  3[8]
        E  1[3]  3[8]     b  -->  C  1[3]  1[8] and D  2[3]  1[8]
        F  2[3]  3[8]     s  -->  G  1[3]  7[8] and H  2[3]  7[8]
        F  2[3]  1[8]     s  -->  G  1[3]  7[8] and H  2[3]  7[8]
        G  1[3]  7[8]     b  -->  C  1[3]  1[8] and D  2[3]  1[8]
        H  2[3]  7[8]     s  -->  G  1[3]  7[8] and H  2[3]  7[8]

Note that all the other possible states are reached from one or the other of the header states, but nodes A and B are never reached from within an l.d.a.  (This point is already known -- see Margaret Maxfield's proof among these web pages.)  The fact that there are no edges reaching an extension/header from within the diagram supports my claim that l.d.a.s are a useful unit in dissecting the Collatz predecessor graph for further analysis.  This is a key fact.

As an example, we might take the l.d.a.  from 445 to 27,  which runs 445,  593,  263,  175,  233,  155,  103,  137,  91,  121,  161,  107,  71,  47,  31,  41,  27.  This l.d.a.,  which appears among low integers,  starts the Collatz trajectory from 27 which is often cited to show the caprice of the Collatz sequence.  This l.d.a. proceeds through

   A(445),  b->D(593),  s->F(395),  s->H(263),  s->G(175),  b->D(233),
s->F(155),  s->G(103),  b->D(137),  s->E(91),   b->C(121),  b->D(161),
s->F(107),  s->H(71),   s->H(47),   s->G(31),   b->D(41),   s->leaf(27),
where the last step is not on the diagram because it goes to the terminating leaf node.  Naturally,  since it is started via A->D, the alternative starting edges A-->C,  B-->E,  and B-->F cannot appear in this trajectory,  but of the other edges all except C-->C,  E-->D,  and G-->C are traversed in this l.d.a.  A more detailed exhibition of this same l.d.a. which includes the set contents at each stage is available.

A second picture of this state transition diagram has been prepared. While the above was arranged to appear planar (with no crossed edges), the second is presented more compactly and contains crossed edges. The identity of the nodes which give rise to each node are identified in the captions below the diagram, but it takes some work to understand the notation.

The first green line shows the first 2 non-leaf integers which exist in each state. Apply the appropriate predecessor formula to each of these in turn. 13 from A produces 17 which is in D, so put 17 and A in the second and third green rows under D. 37 from A produces 49 which is in C, so put 49 and A under C in the second and third green rows. 29 fom B gives 19 so put 19 and B under E. Continue. When finished the green rows show the sources which result in each state in the diagram. All the green result values under a given node are congruent mod 24. The individual edges may be confirmed in this way, and the fact that no edges lead to A and B is made quite evident.

The idea that l.d.a.s are a useful unit for dissection of the Collatz predecessor graph,  supported by this state diagram,  allows the development of the abstract predecessor tree,  in which the nodes are sets of odd integers,  the edges represent 's' or 'b' transitions,  and l.d.a.s are developed from systematic combination of the 's' and 'b' steps as the abstract tree is elaborated.  The umber and black edges in the state transition diagram collectively map into the 's' and 'b' edges,  respectively,  in the development of the abstract predecessor tree.

The arguments developed from the abstract predecessor tree speak to the unique occurence of every odd positive integer in the abstract tree,  to the directed graph nature of the abstract -- hence the detailed -- predecessor tree,  and to the summation of the densities of the integers in each set of the abstract tree which indicates that every odd integer is in it,  hence also in the Collatz graph.  These arguments thus are built indirectly on the state transition diagram.

The abstract predecessor tree is directed because it comes from the state diagram which is directed,  and the edges of the detailed predecessor tree must be directed identically because the two map piecewise into one another.  The state diagram supports the dissection of the detailed predecessor tree into l.d.a.s which is the basis for the assertion that the two trees can be mapped piecewise into one another.  All this seems to me to secure the notion that there is at least an underlying tree in the Collatz graph.

There are various arguments which exclude the appearance of a cycle among these trees.  If the Collatz graph is a simple tree,  un-encumbered by any cycles,  then the Collatz conjecture is proven.

My Collatz Home Page         Index to Terms Used