Collatz-Intro - The primitive loop

Workshop
Recreational
Mathematics

Gottfried Helms Univ. Kassel

mailto: helms at uni-kassel

www: math-homepage

 

 

PL: A modular view

 (depending on a empirically checked assumption)

 

3) a modular view

 

It is very natural, to approach the critical diophantine equation with modular arguments. If this equation cannot be satisfied in integers, no primitive loop of any length is possible.

Unfortunately relies the modular approach in the current depth on an assumption, which is not yet proven, and is equivalent to a critical inequality steming from the waring-problem, which is very likely true, but which truth could not yet been proven explicitely.

 

But for the very unlikely case, that a counter-example exists, another condition must be satisfied - and this is one on the value of A in relation to N.

 

Since I was not experienced in approximation-theory, but as well, as I was not aware, that a first breakthrough was already made in disproving that type of loop in 1978 by Ray Steiner diproving the 1-cycle, 2000 by John Simons disproving the 2-cycle and 2003 de Weger/Simons disproving all m-cycles up to m=68 with such means, I approached that problem from the modular view.

 

I came pretty far and found a table which beautifully exhibits the impossibility of the primitive loop on the basis of being no integer solutions in that table. However, *that* in that table were no integers was depending on an assumption, which in turn I could *not*prove. It came out to be the same condition, which is known in the waring-problem, and again seems to deserve approximation-theory to be proven. But about that theme read the next chpater about approximation-arguments.

 

 

 

3.1) the modulus-table

Starting point is the divisibility table with the residue classes modulo powers of 2.

 

I'm presenting arguments, why the "primitive loop" cannot exist for modular reasons, in short: because

 

[Eq 1]:

 

       i*3^N - 1
2^A = -----------
       i*2^N - 1

 

cannot hold for any N,i > 1 , since the rhs is never an integer , and even less a power of 2.

 

The arguments that I'm presenting here look really good and suggestive. But I have to mention, that they rely on one basic assumption, which was *not* proven by this arguments, but seemingly needs external backing from other resources. This is the following assumption, which uses the expression of 3^N/2^N as an irregular fraction:

 

let 

     3^N         p
     --- = M  + ---    where M,p,q are positive integers, and q = 2^N
     2^N         q

    

 

then

     M + p < q 

 

 

That means - in other words - the remarkable fact, that the two digits in a base-2^N-representation not only never sum up to 2^N-1, but also that their sum is always smaller - an empirical observation, which I find very astonishing. I'm currently trying to relate this property to that condition, which is mentioned in the Log3/Log2-observations-section.

 

So the generalization of the observed facts in the modular two-way-table, (which strongly suggest, that this assumption is true) gives an argument, that there is no primitive loop at all on modular reqirements.

 

Another reason, why this approach may be interesting is, that it allows to be extended even to conacatenated PT-M-loops, or m-cycles schematically while the approximation-approach does not suffice for M>68, means the 68-fold-combination of 1-cycles to one m-cycle, according to results of J. Simons and B.de Weger. Since modular restrictions do not depend on the relative size of numbers it could be, that this way the general m-cycle-problem can be solved.

In short, the extensions follows the idea:

·         an 1-cycle is impossible, if no entry in that table is integer (more precisiely: a power of 2)

·         an m-cycle is impossible, if no product of m entries of this table can result in an integer (again more precisely in a power of 2)

(note that the exponents of the powers-of-2 have the known further restrictions to match about 0.59*N)

 

I'm currently investigating the conditions of such products.

Because of the possible value of that table, it is presented here in some detail.

 

 

 

The first observation is, that the nominator of [eq 1], for an i=1 follows a remarkable simple structure (which in fact can be derived from the binomial expansion of (2+1)^N) :

 

If we write down

 

 3^N-1  = 2^A * u,

where A is chosen to make u an odd ("u"neven) number, then the following table occurs for different A and N:

 

A  N

1  1,3,5,7,9,11,... = 2^0 + k*2^1

2  -- doesn't exist --

3  2,6,10,14,18,... = 2^1 + k*2^2

4  4,12,20,28,...   = 2^2 + k*2^3

5  8,24,40,...      = 2^3 + k*2^4

6  16,48,80,...     = 2^4 + k*2^5

 ...

 

then,  in connection with that condition from the introduction into the loop-problem,  that for a primitive loop A must be about 0.59*N, and so since

         i*3^N - 1

  2^A = ------------  when i is set to i=1

         i*2^N - 1

 

all cases which disagree with this condition, can be excluded for the assumption, that i=1. Only enumerable, and fortunately *very few* entries remain to be checked for an eventual loop: so all odd N>3, all N of the form N=4k+2 where N>6, all N of the form N=8k+4 where N>12 , all N>=24 and all N>=16 from the appropriate rows can be excluded for a primitive loop, assumed, that i=1.

 

That is a radical reduction of possible lengthes, leaving only a handful of choices, based on a modular view of the things.

In a first glance it may be stated, that if i increases, then the minimal member of the loop a increases by multiples of 2^N, and from the discussion of the general loop we know, that such a growth radically sharpens the critical  inequality against being greater than the lower-bound, given by the powerceil2(3^N) value.

But here we want to study primarily the modular conditions, and an increasing of i can always enable some terms to have an higher power of 2 as a factor than the factor 2^A, which is denoted as factor of 3^N-1.

A two-way-table including the changes of i seems somehow instructive, but is not evaluated finally.

 

 

An updated approach to display things seems the following table, where the lhs-fraction of Eq 1 is displayed in the number-system of 2^N as an irregular fraction.

The entries are always of the form

 

 M + pi/qi            where qi is the appropriate term of i*2^N-1

and

 M + p /q            in the term for the limit i->oo

 

Especially interesting was the form for i=0, which always come out to be 1 since

 

  (i*3^N - 1)/ (i*2^N-1) = -1/-1 = 1           for i=0

 

 

That entry could be regularly added by the trick to write it as an irregular fraction as

 

              N - 1
  1  =   N  + -----
               -1

 

which is true for all N.

 

Here follows the table:

 

 For instance some rows for N>=2 , i=0..oo give

 

                    i=0       i=1        i=2                                    i->oo

                    M0  p0 q0   M1 p1 q1    M2 p2 q2                                M  p q

-------------------!---------!---------!---------!-----------!----------------!-------

   f(N=2,i=0..oo):   2  1/-1   2  2/3     2  3/7     2  4/11     2   5/15  .. -> 2  1/4

   f(N=3,i=0..oo):   3  2/-1   3  5/7     3  8/15    3 11/23     3  14/31  .. -> 3  3/8

   f(N=4,i=0..oo):   5  4/-1   5  5/15    5  6/31    5  7/47     5   8/63  .. -> 5  1/16

   f(N=5,i=0..oo):   7  6/-1   7 25/31    7 44/63    7 63/95     7  82/127  ..-> 7 19/32

   f(N=6,i=0..oo):  11 10/-1  11 35/63   11 60/127  11 85/191   11 110/255  . ->11 25/64

   f(N=7,i=0..oo):  17 16/-1  17 27/127  17 38/255  17 49/383   17  60/511   -->17 11/128

 ...

 

 

On a first glance we see some very useful properties:

 

  a) The integer-part M does never change by changings of i

  b) the nominators p1,p2,p3,... grow in positive arithmetic progression

  c) the progression p2-p1 of the nominator is smaller than that of the denominator q2-q1

 

  d) the second nominator  (p1 at i=1) is always equal or greater than the integral part M

  e) the progressions are

             p2-p1 = p =  (p1-M) + 1

             q2-q1 = q

      (which follows easily from the difference-equation f(N,i+1)-f(N,i))

 

  f) the first nominator p1 is always smaller than q1-1 for (N>2) or (N=2 and i>1).

 

 These observations, if they can be generalized, have remarkable consequences:

 

Any changing of i does not affect the integral part of the fraction in [Eq 1],

 

          which is a very useful property in analyzing formulae derived from [eq 1]

   and

         Since the progression of the nominator is always positive, but smaller than that

          of the denominator (which is obvious from the fact, that p/q is the remainder),

 

Nominator and denominator can never have a Null or an integral ratio,

 iff the second nominator p1 is already smaller than q1.

 

 

The consequence is, that we cannot find an integer in the whole two-way table, which covers all possible combinations of results for [eq 1], which in turn disproves the primitive loop, since that would mean, that either pi=0 or pi=qi to have a result for rhs in [eq1], which is at least integer (it even must be a power of 2, but that need not be discussed, if the result is no integer at all)

 

 

Now the prerequisite for that effect is, that

 

required, but not proven:

 

 p0 + p < q0 + q 

 M-1 + p < -1 + q

 

      p + M  < q   

 

or ,required (but not proven)

[Cond 1]

      p      < q - M

 

 

I checked empirical evidence for that up to N~ 15000 and had no counterexample.

I didn't find an elementary proof for that, but after some re-arranging of formulas it seems, that this condition is nothing else than the critical inequality in disguise. I'll have to verify this precisely.

 

So we have,

 - given [cond 1] holds, then -

 since each combination of i and N in equation [eq 1]

 

[Eq 1]:

 

       i*3^N - 1
2^A = -----------
       i*2^N - 1

 

results in a non-integer value, the equation [eq 1] describing a condition for a primitive loop cannot be satisfied.

Thus a primitive loop of any length cannot exist - given [cond 1] holds for all N.

 

 

 

 

[added 20.8.04]

The condition [Cond 1] is equivalent to the critical inequality for primitive loops, so it is proven with the Steiner-approximation-proof of nonexistence of 1-cycles. So it *is* indeed proven, but not by elementary means.

It is possible then to proceed with that table even if the elementary proof needs awaiting...

 

Given:

 

 s = M*q + p    so M = floor(s/q) and M+1 = ceil(s/q)

 

cond1:

 

 p < q - M

 

Then :

 

 M*q + p < M*q - M + q

 

     s   < (M+1)*q - M

 

     s   < M(q-1) + q

 

  s - q  < M(q-1)

 

 

  s - q

  -----  < M

  q - 1

 

      s - q

  1 + -----  < M +1 = ceil(s/q)

      q - 1

 

  s - 1      

  -----      < ceil(s/q)

  q - 1     

 

 q   s - 1                q

 - * -----  < ceil(s/q)* ---

 s   q - 1                s

 

Now with s = 3^N, q = 2^N , rhs = powerceil2(3^N)/3^N   this exactly the critical inequality for the primitive loop with i=1:

 

 2^N   3^N - 1     powerceil2(3^N)

 -   * -------  <  ----------------

 3^N   2^N - 1        3^N

 

 

This formula is proven via the proof done by Steiner, so cond1 is proven,

 

* so the p-values for the column i->oo holds,

* so the column for i=1 hold,

* and so all columns hold.

 

Since all columns and rows hold,

 

* there is no integer in this table,

 

and the table can be used in further considerations.

 

 

 

 

                                                                                                                          last update: 20. Aug. 2004