Collatz-Intro - The primitive loop
|
Workshop |
|
|
Unfortunately
the critical property of the modular-table cannot be proven by itself, but is
dependend on an approximation-argument, that surprisingly also occurs in the Waring-problem. In the
following study of the primitive-loop-problem with the focus on some
approximation-conditions again I cannot fix a rigid proof. But I can provide
some results, of which at least one seems to be more powerful than current
approximation-results and especially seems to provide a tool to proceed significantly
in the problem of concatenated primitve-transformations ("m-cycle") |
|
In the
discussion of the general loop I derived the critical approximation equation
for loops powerceil(3^N) <= 2^S = (3+1/a1)(3+1/a2)...(3+1/an) < 4^N This came
from the consideration a1' a2' an' powerceil(3^N)
<= 2^S = ------* ------*...*---- * 2^S
< 4^N a1 a2
an In this
chapter this will be related to the situation, that all except one exponents
are 1. Since in the
case of a primitive loop we "know" all members of the projected
loop, we cancel a1'/a2 , a2'/a3
and so on all except an' and a1, getting an' powerceil(3^N)
<= 2^S = ------* 2^S
< 4^N a1 3^N*i-1 1
powerceil(3^N)
<= 2^S = --------- * -------*
2^S < 4^N 2^(A-1) 2^N*i-1 3^N*i-1 2^S powerceil(3^N)
<= 2^S = --------- * ------- < 4^N 2^N*i-1 2^(A-1) 3^N*i-1 powerceil(3^N)
<= 2^S = 2^N * ---------
< 4^N 2^N*i-1 and
concentrate on the following part of the above inequality: |
|
The "critical
approximation inequality for the primitive loop": 3^N*i-1
powerceil2(3^N) <= 2^N * --------- <
4^N 2^N*i-1
It is easy to
see, that to satisfy the inequality it is best to have a small value in i;
since with increasing i the rhs decreases, making the
inequality more unlikely. 3^N-1/i 3^N 2^N *
------- -> 2^N ---
= 3^N // with i->oo 2^N-1/i 2^N and then the
inequality powerceil2(3^N)
<= 3^N cannot be
satisfied for any N. On the other
hand with increasing i we may possibly satisfy the
modular condition, that the nominator is at least evenly divisible by the
denominator. For the current argumentation it should be sufficient to set i =
1, because if with that condition the primitive loop is not possible,
then it will not be possible for higher i - independent on modular
arguments. We have then
the first way to rearrange and put it in a different form: 3^N 3^N 3^N 1 powerceil(3^N)
<= 2^N *( ---- + --- + --- - ------) 2^N 4^N 8^N 2^N-1
3^N 3^N 2^N powerceil(3^N)
<= 3^N + ( ---- + --- + ...)
- ------) 2^N 4^N 2^N-1
3^N 3^N 1 powerceil(3^N)
<= 3^N + ( ---- + --- + ...) - 1 -
------) 2^N 4^N 2^N-1
3^N 3^N 1 powerceil(3^N)
<= 3^N + ---- - 1 + ---
- ----- 2^N 4^N 2^N-1 Since we deal
only with integers, that part on the rhs can be ignored, I note it as 1-eps: 3^N powerceil(3^N)
<= 3^N + ---- - (1 - eps) 2^N and ignoring
that part will even loose the bound to the next greater integer. Now to make
it simpler to really compute the ranges I proceed as follows: powerceil(3^N) 1 --------------
<= 1 + --- 3^N 2^N Note, that
the difference to the reformulated Waring-Problem is only one of a cofactor
on the lhs: Collatz 3^N powerceil(3^N)
= 2^N*2^A <= 3^N + ---- (primitive loop) 2^N Waring: 3^N 2^N* u <= 3^N + ---- (With 2^N*u
<3^N, u integer) 2^N Since the rhs
can only range between 1 and 2 and if we subtract 1 then on the lhs we can
write it in the fraction-function:
2^S 1 frac(--- )<= --- where 2^S is the
smallest power of 2 greater than 3^N 3^N 2^N |
|
This
inequality means: ·
a
primitive loop of length N is only possible if the fraction of
powerceil2(3^N)/3^N is smaller than 1/2^N or ·
a primitive
loop of any length N is denied, if the fraction is greater
then 1/2^N |
|
It may be of
interest, that it is exactly the inequality that also occurs in the
waring-problem, as mentioned in earlier chapters. (see
[mathworl.wolfram.com])]. It is still unproven, whether this inequality holds
or not. It is also far beyond my abilities to prove/disprove that inequality.
But it may be
of interest, not only that is unlikely, that this
inequality holds for all N>0, as it can be empirically be shown up to some
N<1E1000 , but also how unlikely this is . For that
purpose I add some tables, which can illustrate that. |
Table 4.3.1: Relation
(2^S-3^N) to 3^N/2^N
N powceil2(3^N)-3^N 3^N/2^N -------------------------------------- 1 1
1.50000000 2 7
2.25000000 3 5
3.37500000 4 47 5.06250000 5 13
7.59375000 6 295
11.39062500 7 1909
17.08593750 8 1631
25.62890625 9 13085
38.44335938 10 6487
57.66503906 11
84997 86.49755859 12 517135
129.74633789 13 502829
194.61950684 14 3605639
291.92926025 15 2428309
437.89389038 16
24062143 656.84083557 17 5077565
985.26125336 18
149450423 1477.89188004 19
985222181 2216.83782005 20
808182895 3325.25673008 |
|
This small
table shows already, that the lhs-values are not only greater than the rhs,
but even the growth-rate is of a far greater class than the rhs. To make this
visible also for higher N the criteria are changed and are set into relation
to 3^N: |
Table 4.3.2:
powceil2(3^N)-3^N 1 3^N 2^N N
lhs <= rhs -------------------------------------- 1 0.3333333333333333 0.500000000000 2 0.7777777777777778 0.250000000000 3 0.1851851851851852 0.125000000000 4 0.5802469135802469 0.062500000000 5 0.0534979423868313 0.031250000000 6 0.4046639231824417 0.015625000000 7 0.8728852309099223 0.007812500000 8 0.2485901539399482 0.003906250000 9 0.6647868719199309 0.001953125000 10 0.1098579146132873 0.000976562500 11 0.4798105528177164 0.000488281250 12 0.9730807370902885 0.000244140625 13 0.3153871580601923 0.000122070313 14 0.7538495440802564 0.000061035156 15 0.1692330293868376 0.000030517578 16 0.5589773725157835 0.000015258789 17 0.0393182483438557 0.000007629395 18 0.3857576644584742 0.000003814697 19 0.8476768859446323 0.000001907349 20 0.2317845906297549 0.000000953674 |
|
One can see
that the lhs has a somehow up-and-down character, which however may lead to
smaller values by a slow rate. |
|
In the next
table I only print the least values in descending order: |
Table 4.3.3:
powceil2(3^N)-3^N 1 3^N 2^N N
lhs <= rhs ------------------------------------------------- 1 0.3333333333333333 0.5000000000000000000000 3 0.1851851851851852 0.1250000000000000000000 5 0.0534979423868313 0.0312500000000000000000 17 0.0393182483438557 0.0000076293945312500000 29 0.0253294077568411 0.0000000018626451492310 41 0.0115288518086085 0.0000000000004547473509 94 0.0094188494143407 0.0000000000000000000000 147 0.0073132483874642 0.0000000000000000000000 200 0.0052120395469304 0.0000000000000000000000 253 0.0031152137308417 0.0000000000000000000000 306 0.0010227617964118 0.0000000000000000000000 971 0.0009790639918679 0.0000000000000000000000 1636
0.0009353680948712
0.0000000000000000000000 The table is
much compressed; this compression exhibits the high relative rate of
decreasing of the rhs, which seems exponentially to that of the lhs. This
again indicates the improbability, that it could ever happen, that
lhs<=rhs. |
|
To have that
problem accessible to far higher N, this could also be displayed in
logarithms. the
inequality must be reformulated, to make use of that logarithmic approach: |
|
powceil2(3^N)-3^N 1 3^N 2^N powceil2(3^N) 3^N 1 2^N 2^N
2^N let ß =
log(3)/log(2) then 2^(ceil(ß*N)) 2^(ß*N) 1 take
logarithm base 2 ( =ld(x)) 1 ceil(ß*N) - N <= ß*N - N + ld(1 + --- ) 2^N Since
log(1+x)=1-x + eps (x<1) with eps<x^2
and µ=1/log(2) we can rewrite 1 ceil(ß*N) - N <= ß*N - N +( --- - eps)*µ 2^N 1 ceil(ß*N) <= ß*N + ( --- - eps )*µ 2^N 1 floor(ß*N) <= ß*N -1 + ( --- - eps)*µ 2^N 1 1 -(--- - eps)*µ <= frac(ß*N) 2^N 1 1 1- frac(ß*N) <= (--- - eps)*µ // where eps < ------ 2^N 2*4^N |
Table 4.3.3a:
representation in logarithm (base 2)
1 1 lhs= 1- frac(ß*N) <= rhs= (--- - eps)*µ // where eps ~ ----- µ=1/log(2) 2^N 2*4^N N
lhs <= rhs ------------------------------------------------- 1 0.4150374992788438 0.5410106403333612777600 2 0.8300749985576876 0.3155895401944607453600 3 0.2451124978365315 0.1690658251041753993000 4 0.6601499971153753 0.0873506763038239563050 5 0.0751874963942191 0.0443797790898460423162 6 0.4902249956730629 0.0223659997794065371991 7 0.9052624949519067 0.0112270274483241476098 8 0.3202999942307505 0.0056245206138172935574 9 0.7353374935095944 0.0028150120293224517169 10 0.1503749927884382 0.0014081939452646770930 11 0.5654124920672820 0.0007042689552832013551 12 0.9804499913461258 0.0003521774733043163797 13 0.3954874906249696 0.0001760994855678371154 14 0.8105249899038135 0.0000880524300128382891 15 0.2255624891826573 0.0000440268868136490774 16 0.6405999884615011 0.0000220136113586320219 17 0.0556374877403449 0.0000110068476672678818 18 0.4706749870191887 0.0000055034343306219086 19 0.8857124862980326 0.0000027517197895579462 20 0.3007499855768764 0.0000013758605508407211 The nice
thing for some further analyses is, that the lhs increases linearly (mod 1) Table 4.3.3b: only
descending lhs documented
N
lhs <= rhs ------------------------------------------------- 1 0.4150374992788438 0.5410106403333612777600 3 0.2451124978365315 0.1690658251041753993000 5 0.0751874963942191 0.0443797790898460423162 17 0.0556374877403449 0.0000110068476672678818 29 0.0360874790864707 0.0000000026872289172287 41 0.0165374704325966 0.0000000000006560617480 94 0.0135249322113189 0.0000000000000000000000 147 0.0105123939900413 0.0000000000000000000000 200 0.0074998557687637 0.0000000000000000000000 253 0.0044873175474861 0.0000000000000000000000 306 0.0014747793262085 0.0000000000000000000000 971 0.0014117997573478 0.0000000000000000000000 1636
0.0013488201884871
0.0000000000000000000000 |
|
I studied the
convergence-ratio of 2^S/3^N by the following process, which came out to be
very similar to that of the continued-fraction-expansion of log(3/2)/log(2) (and
essentially contains it) Write the
approximants of 2^S/3^N as a product like N= 1 2 3 4 5 6 7 8 9 .....
(where the
nominator of a new factor is chosen between 4 and 2 so that the complete
result is always >1 ), and exploit,
that there are only two symbols occuring: 32
8 8 32 ... then this
"compression" can be repeated on always new recursion levels, with
(empirically) always two new symbols, resulting in iteratively better
approximants of 2^S/3^N With that
method I constructed the following table up to high N, which suggests very
strongly a clear bound for the convergence-rate. In that table the entry for
the rhs is omitted, instead of that the combinations S/N are documented,
which either give the best approximants to 1 from above or from below. It may
be interesting, that this table also represents the convergents steming from
the continued-fraction-expansion mentioned above. |
Table 4.4.1:
Level best
approximant "from above"
best approximant "from below" as decimal as decimal as fraction as fraction -------------------------------------------------------------------- 1
1.33333333333333333333333333
0.66666666666666666666666667 2^2 2^1 --- --- 3^1 3^1 2
1.18518518518518518518518519
0.88888888888888888888888889 2^5 2^3 --- --- 3^3 3^2 3
1.05349794238683127572016461
0.93644261545496113397347965 2^8 2^11 --- ---- 3^5 3^7 4
1.03931824834385566014811364
0.98654036854514423990621725 2^27 2^19 ---- ---- 3^17
3^12 5
1.01152885180860850383729052
0.99791404625731122600598255 2^65 2^84 ---- ---- 3^41 3^53 6
1.00102276179641176722083140
0.99893467461992588900707938 2^485 2^569 ----- ----- 3^306 3^359 .... 24
1.00000000000000010635580339
0.99999999999999999477187338 2^9115015689657667 2^9881527843552324 ------------------ ------------------ 3^5750934602875680 3^6234549927241963 25
1.00000000000000000179327108
0.99999999999999999656514447 2^206745572560704147 2^216627100404256471 -------------------- -------------------- 3^130441933147714940 3^136676483074956903 26
1.00000000000000000015168663
0.99999999999999999835841555 2^630118245525664765 2^423372672964960618 -------------------- -------------------- 3^397560349370386783 3^267118416222671843 27
1.00000000000000000002696849
0.99999999999999999987528186 2^7354673373747273033 2^6724555128221608268 --------------------- --------------------- 3^4640282259296926456 3^4242721909926539673
28
1.00000000000000000001012431
0.99999999999999999998315582 2^43497921996957973433 2^36143248623210700400 ---------------------- ---------------------- 3^27444133206411171953 3^22803850947114245497 29
1.00000000000000000000340444
0.99999999999999999999328013 2^123139092617126647266 2^79641170620168673833 ----------------------- ---------------------- 3^77692117359936589403 3^50247984153525417450 ..... |
|
At any rate -
in this table the documented approximation is roughly proportional to N, for
instance, in line 28 and 29 see the number of zeros of the approximant - they
nearly exactly match the number of digits in the exponent of 3 (means: the
number of digits in N) 28
1.00000000000000000001012431 2^43497921996957973433 ----------------------- 3^27444133206411171953 29
1.00000000000000000000340444 2^123139092617126647266 ------------------------ 3^77692117359936589403 with little
variance (of about 2 digits, with a very slow ascendence) This suggests
a very simple relation between the approximants and N: 2^S or, in a raw
estimate, to point out the general size: 2^S
1 which is -to
an astronomical ratio- different to the requirement of the critical
inequality 2^S 1 and the
latter critical inequality could obviously never be satisfied. |
|
Empirically I
could compute that relation up to N~10^550, |
Table 4.4.2
Level Approx. from above N --------------------------------------------- 1 1+
3.3333333e-0001 1.0000000e+0000 2 1+
1.8518519e-0001 3.0000000e+0000 3 1+
5.3497942e-0002 5.0000000e+0000 4 1+
3.9318248e-0002 1.7000000e+0001 5 1+
1.1528852e-0002 4.1000000e+0001 6 1+
1.0227618e-0003 3.0600000e+0002 7 1+
9.7906399e-0004 9.7100000e+0002 8 1+
1.8194754e-0005 1.5601000e+0004 9 1+
1.0929714e-0005 4.7468000e+0004 10 1+
3.6647274e-0006 7.9335000e+0004 ... 725 1+
1.3596592e-0546 3.1268857e+0545 726 1+
2.3246976e-0547 5.6325720e+0545 727 1+
3.5159389e-0548 3.0668546e+0546 728 1+
1.3645960e-0548 2.0904725e+0547 729 1+
5.7784921e-0549 5.9647320e+0547 730 1+
3.6895159e-0549 1.5803724e+0548 731 1+
1.6005397e-0549 2.5642715e+0548 732 1+
1.3523025e-0550 1.3208784e+0549 733 1+ 5.2484537e-0551 5.6383305e+0549 and only very
small corrections were needed to increase the denominator, something of the
type 2^S
1 or 2^S
1 But these
estimates are only guesses based on the emprical data, and are only hints, as
long as no rigid proof for better bounds are available. |
|
Unfortunately,
the proof of Ray Steiner[Seiner 1978] is only as a sketch known to me, so I
don't know, whether this proof of the nonexistence of 1-cycles also covers
the observations given here. In a newsgroup-conversation I was told, that it
followed another path, leading to the result, that the approximation of
3^N-1 was not
satisfied because the rhs could not be a power of 2. On the other
hand, in a paper of B.de Weger, the author mentions "very effective low
bounds", which the proof of Steiner provided... In my view, a disproof
of this equation with the means of rational approximation should in fact be
corresponding to my above considerations - but I don't actually know this. |
|
It may be mentioned, that my critical inequality is corresponding to a inequality known from the waring-problem. In mathworld Eric Weisstein mentions: "The waring-problem could
completely be solved, if the following inequality could be proven:
3^N 3^N frac(--- ) < 1 - --- 2^N 4^N " [Weissstein, Powerfrac] This
inequality can be rearranged to match my critical inequality for a primitive
loop: 3^N 3^N 3^N ---
< 1 - --- + floor(---) 2^N 4^N 2^N 3^N 3^N 3^N --- +
--- < ceil (---) 2^N 4^N 2^N 3^N 3^N 3^N ---
+ --- < ceil (---) *2^N = (u+1) * 2^N where u*2^N < 3^N < (u+1)*2^N 1 2^N 2^N 1 (u+1)*2^N // war: powerceil2(3^N) 1 + ---
< --------------- 2^N 3^N which is the
formula (except the eps-term), which I derived for the primitive loop. |
|
last update: 17.9.2004 |