Collatz-Intro - The primitive loop
|
Workshop |
|
|
Unfortunately the critical property of the modular-table cannot be proven by itself, but is dependent 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 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 primitve 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) 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.2Level 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 = powerceils(3^N) 1 2^N 2^N
1 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 |