State Transition Diagram Problem

Mensanator's discovery that the shape of the state transition diagram for the Collatz trajectories is identical for the positive and the negative domains led to his argument that the state transition diagram cannot be trusted to indicate that Collatz trajectories are loop free (excepting the trivial loop 4-2-1) since the negative domain does exhibit non-trivial loops.

This is truly astounding because the Collatz trajectories in the negative domain has loops and in the positive  (presumably)  none other than the trivial one.  The negative state transitions show no sign of congruence sets  (see below),  while the positive transitions produce nothing else.  The positive transition diagram has no edge which requires more than 2 divisions by 2,  while the negative one has cetain nodes every one of whose effluent edges requires 3 or more divisions by 2.  From the identical shape he argues that one cannot conclude from the shape of the state transition diagram that it excludes a non-trivial cycle in the positive domain.  Yet the behaviors of the Collatz trajectories is profoundly different in the two domains.  We'll have to look elsewhere for the determining feature.

First look at a comparison of the state transitions for the negative and positive domains starting from an arbitrary congruence set. The sign of 1 in the exression (3n+1)/2^i is the same as the sign of 3n in the positive domain while it is opposite in the negative domain.  To illustrate the effect of this, consider the Collatz successors of the series of instances the succesive integers in the congruence set,  -3[24].  In the negative domain, the result exhibits a prolific variety of product states.  (The state names are assigned according to their congruences modulo -24.)

  -3    (-3*3+1)/2*i   =  -8/2^3  =  -1  A   -1
 -27   (-27*3+1)/2*i   = -80/2^4  =  -5  C   -5
 -51   (-51*3+1)/2*i   =-152/2^3  = -19  J  -19
 -75   (-75*3+1)/2*i   =-224/2^5  =  -7  D   -7
 -99   (-99*3+1)/2*i   =-296/2^3  = -37  G  -11
-121  (-123*3+1)/2*i   =-368/2^4  = -23  L  -23
-147  (-147*3+1)/2*i   =-440/2^3  = -55  D   -7
-171  (-171*3+1)/2*i   =-512/2^9  =  -1  A   -1
-195  (-195*3+1)/2*i   =-584/2^3  = -73  A   -1
-219  (-219*3+1)/2*i   =-656/2^4  = -41  D   -7
-243  (-243*3+1)/2*i   =-728/2^3  = -91  G  -11
-267  (-267*3+1)/2*i   =-800/2^5  = -25  A   -1
-291  (-291*3+1)/2*i   =-872/2^3  =-109  G  -11
-315  (-315*3+1)/2*i   =-944/2^4  = -59  F   -9

Using the predecessor formula in the positive domain and operating on elements of 5[8],  we notably get elements of only three congruence sets, a leaf set, 0[3],  and two non-leaf sets, 19[24],  and 11[24].  These results repeat infinitely.  Using any other c[d] congruence set will yield a similar result  (perhaps cyclically permuted in the sets of 3 predecessors).  Note that the same result is obtained if successors of 3[16] are employed,  a simple result of the reversability of the edges in the state transition diagram among the positive integers.

   5     (2*5-1)/3     =  3    leaf in 0{[3]} 1st instance
  29    (2*29-1)/3     = 19    in 19{[24]}    1st instance
  53    (2*53-1)/3     = 35    in 11{[24]}    2nd instance
  77    (2*77-1)/3     = 51    leaf in 0{[3]} 17th instance
 101   (2*101-1)/3     = 67    in 19{[24]}    2nd instance
 125   (2*125-1)/3     = 83    in 11{[24]}    3rd instance
 149   (2*149-1)/3     = 99    leaf in 0{[3]} 33rd instance
 173   (2*173-1)/3     =115    in 19{[24]}    3rd instance
 197   (2*197-1)/3     =131    in 11{[24]}    4th instance

Additionally, supposing that a non-trivial loop might appear among large positive integers requires that some such numbers fail to obey the rules of the simple arithmetic operations, multiplying, adding , and dividing   While very large numbers are wondrous in many ways , it cannot be expected that any behave in such a basically capricious way.

The question is now moot in any case.  The program rsetprog develops the congruence sets constituting the Collatz predecessor graph de novo from the congruence set 5[8].  The de novo development avoids the use of assumptions about the state transition diagram and the comprehensivess of the abstract predecessor tree,  but instead develops the whole schema in which those features may be discerned.  Examination of the membership of the congruence sets at the successive powers-of-2 levels allows calculations  (two dimensional infinite summations)  which indicate that all the odd positive integers would be produced in an infinite program run of rsetprog.  Detailed examination of the tree of congruence sets reveals the left descent assemblies and confirms the validity of the abstract predecessor tree construction.  Unlike many computer programs which don't prove anything,  rsetprog effectively constitutes the desired inductive constructive proof of the Collatz conjecture.

My Collatz Home Page        Index to Terms Used