[math-fun] Nonquadratic surds with periodic continued fractions?
Jeffrey Shallit's 1979 undergrad thesis https://cs.uwaterloo.ca/~shallit/Papers/thesispt1.pdf, https://cs.uwaterloo.ca/~shallit/Papers/thesispt2.pdf claims that "the" correct decomposition of the complex plane into unit-area regions is tilted √2 by 1/√2 dominoes including their two left edges, excluding their top- and bottommost points, placed with the midpoint of the lower left side on the representative lattice point. It may not be obvious, but periodic continued fractions with Gaussian integer terms can represent algebraic numbers beyond quadratic. Shallit's thesis claims that the correct complex floor function is complexfloor[z_] := Floor@z + Which[#1 + #2 < 1, 0, #2 > #1, I, True, 1] & @@ReIm@FractionalPart@z which he then uses to define complex continued fractions. Here is a "resumable" version, cCF[srd_, max_: 33] := NestWhileList[FullSimplify[1/(# - complexfloor@#)] &, srd, UnsameQ@## &, All, max] which lists the successive states of the computation, whose complexfloors are the actual terms. Moreover, leaving the last computed term unfloored, when interpreted as a finite CF, recovers the original "fractionand". E.g., for 2 i^⅓, In[220]:= cCF[2 Power[I, 1/3]] Out[220]= {2 (-1)^(1/6), 1/2 (1 + Sqrt[3]), 1 + Sqrt[3], 1/2 (1 + Sqrt[3])} cCF terminated: The 4th state equals the 2nd. Taking the floors, In[221]:= complexfloor /@ % Out[221]= {1 + I, 1, 2, 1} Mathematica denotes periodicity with extra braces: In[222]:= Append[Drop[%, -2], Take[%, -2]] Out[222]= {1 + I, 1, {2, 1}} In[223]:= FromContinuedFraction@% Out[223]= Root[16 - 4 #1^2 + #1^4 &, 4, 0] A quartic. In[224]:= ToRadicals@% Out[224]= Sqrt[2 (1 + I Sqrt[3])] In[225]:= FullSimplify@% Out[225]= 2 (-1)^(1/6) as hoped. For fancier algebraics, we would expect periodicity to fail. E.g., for the real root of Brillhart's famous x^3=8x+10, cCF emulates the usual Euclid process: In[126]:= Solve[x^3 == 8 x + 10] Out[126]= {{x -> Root[-10 - 8 #1 + #1^3 &, 1, 0]}, {x -> Root[-10 - 8 #1 + #1^3 &, 2, 0]}, {x -> Root[-10 - 8 #1 + #1^3 &, 3, 0]}} #1 is the real root: cCF[x /. %126[[1]]] //InputForm {Root[-10 - 8 #1 + #1^3 &, 1, 0], 1/(-3 + Root[-10 - 8 #1 + #1^3 &, 1, 0]), Root[-7 - 44 #1 - 66 #1^2 + 10 #1^3 &, 1, 0], Root[-10 - 144 #1 - 502 #1^2 + 119 #1^3 &, 1, 0], Root[-119 - 926 #1 - 1552 #1^2 + 1002 #1^3 &, 1, 0], . . .} In[246]:= complexfloor /@ % Out[246]= {3, 3, 7, 4, 2, 30, 1, 8, 3, 1, 1, 1, 9, 2, 2, 1, 3, 22986, 2, 1, 32, 8, 2, 1, 8, 55, 1, 5, 2, 28, 1, 5, 1, 1501790} But the other two roots are complex. In[212]:= cCF[x /. %126[[2]]] Out[212]= {Root[-10 - 8*#1 + #1^3 & , 2, 0], 1/((2 + I) + Root[-10 - 8*#1 + #1^3 & , 2, 0]), 1/(2*I + 1/((2 + I) + Root[-10 - 8*#1 + #1^3 & , 2, 0])), -2*I + 1/(2 + Root[-10 - 8*#1 + #1^3 & , 2, 0]), I + 1/((2 + I) + Root[-10 - 8*#1 + #1^3 & , 2, 0]), 1/(2*I + 1/((2 + I) + Root[-10 - 8*#1 + #1^3 & , 2, 0]))} It repeated! What is the CF? In[213]:= complexfloor /@ % Out[213]= {-2 - I, -2 I, -I, -I, -I, -I} Here is where Murphy steps in. There is no information in the triplet i,i,i ! In[247]:= MatrixPower[{{-I, 1}, {1, 0}}, 3] Out[247]= {{-I, 0}, {0, -I}} Shallit's CF algorithm, as I carelessy read it, usually doesn't converge! Most times, it eventually falls into a period 3 loop with hairier terms than Out[212] above, but their complexfloors are all -i! Can some hay be made from this looping? —rwg
On Tue, May 14, 2019 at 5:44 PM Bill Gosper <billgosper@gmail.com> wrote:
It may not be obvious, but periodic continued fractions with Gaussian integer terms can represent algebraic numbers beyond quadratic.
Wow! It certainly wasn't obvious to me! Your example was a constructible quartic. Are all periodic Gaussian cf's constructible? What about with Eisenstein integers? -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
Brad Klee to the rescue. Mathematica's FractionalPart is *not* x - Floor@x ! I *think* Clear@complexfloor; complexfloor[z_] := (# + (Which[#1 + #2 < 1, 0, #2 > #1, I, True, 1] & @@ ReIm[z - #])) &@Floor@z is actually Shallit's function. This fixes the bogus periodicities, which were actually stalled convergence. Caveat: I'm still seeing some anomalies. —rwg On Tue, May 14, 2019 at 4:43 PM Bill Gosper <billgosper@gmail.com> wrote:
Jeffrey Shallit's 1979 undergrad thesis https://cs.uwaterloo.ca/~shallit/Papers/thesispt1.pdf, https://cs.uwaterloo.ca/~shallit/Papers/thesispt2.pdf claims that "the" correct decomposition of the complex plane into unit-area regions is tilted √2 by 1/√2 dominoes including their two left edges, excluding their top- and bottommost points, placed with the midpoint of the lower left side on the representative lattice point.
It may not be obvious, but periodic continued fractions with Gaussian integer terms can represent algebraic numbers beyond quadratic. Shallit's thesis claims that the correct complex floor function is complexfloor[z_] := Floor@z + Which[#1 + #2 < 1, 0, #2 > #1, I, True, 1] & @@ReIm@FractionalPart@z which he then uses to define complex continued fractions. Here is a "resumable" version,
cCF[srd_, max_: 33] := NestWhileList[FullSimplify[1/(# - complexfloor@#)] &, srd, UnsameQ@## &, All, max]
which lists the successive states of the computation, whose complexfloors are the actual terms. Moreover, leaving the last computed term unfloored, when interpreted as a finite CF, recovers the original "fractionand".
E.g., for 2 i^⅓, In[220]:= cCF[2 Power[I, 1/3]]
Out[220]= {2 (-1)^(1/6), 1/2 (1 + Sqrt[3]), 1 + Sqrt[3], 1/2 (1 + Sqrt[3])}
cCF terminated: The 4th state equals the 2nd. Taking the floors,
In[221]:= complexfloor /@ %
Out[221]= {1 + I, 1, 2, 1}
Mathematica denotes periodicity with extra braces:
In[222]:= Append[Drop[%, -2], Take[%, -2]]
Out[222]= {1 + I, 1, {2, 1}}
In[223]:= FromContinuedFraction@%
Out[223]= Root[16 - 4 #1^2 + #1^4 &, 4, 0]
A quartic.
In[224]:= ToRadicals@%
Out[224]= Sqrt[2 (1 + I Sqrt[3])]
In[225]:= FullSimplify@%
Out[225]= 2 (-1)^(1/6)
as hoped.
For fancier algebraics, we would expect periodicity to fail. E.g., for the real root of Brillhart's famous x^3=8x+10, cCF emulates the usual Euclid process:
In[126]:= Solve[x^3 == 8 x + 10]
Out[126]= {{x -> Root[-10 - 8 #1 + #1^3 &, 1, 0]}, {x -> Root[-10 - 8 #1 + #1^3 &, 2, 0]}, {x -> Root[-10 - 8 #1 + #1^3 &, 3, 0]}}
#1 is the real root: cCF[x /. %126[[1]]] //InputForm {Root[-10 - 8 #1 + #1^3 &, 1, 0], 1/(-3 + Root[-10 - 8 #1 + #1^3 &, 1, 0]), Root[-7 - 44 #1 - 66 #1^2 + 10 #1^3 &, 1, 0], Root[-10 - 144 #1 - 502 #1^2 + 119 #1^3 &, 1, 0], Root[-119 - 926 #1 - 1552 #1^2 + 1002 #1^3 &, 1, 0], . . .}
In[246]:= complexfloor /@ %
Out[246]= {3, 3, 7, 4, 2, 30, 1, 8, 3, 1, 1, 1, 9, 2, 2, 1, 3, 22986, 2, 1, 32, 8, 2, 1, 8, 55, 1, 5, 2, 28, 1, 5, 1, 1501790}
But the other two roots are complex. In[212]:= cCF[x /. %126[[2]]]
Out[212]= {Root[-10 - 8*#1 + #1^3 & , 2, 0], 1/((2 + I) + Root[-10 - 8*#1 + #1^3 & , 2, 0]), 1/(2*I + 1/((2 + I) + Root[-10 - 8*#1 + #1^3 & , 2, 0])), -2*I + 1/(2 + Root[-10 - 8*#1 + #1^3 & , 2, 0]), I + 1/((2 + I) + Root[-10 - 8*#1 + #1^3 & , 2, 0]), 1/(2*I + 1/((2 + I) + Root[-10 - 8*#1 + #1^3 & , 2, 0]))}
It repeated! What is the CF? In[213]:= complexfloor /@ %
Out[213]= {-2 - I, -2 I, -I, -I, -I, -I}
Here is where Murphy steps in. There is no information in the triplet i,i,i !
In[247]:= MatrixPower[{{-I, 1}, {1, 0}}, 3]
Out[247]= {{-I, 0}, {0, -I}}
Shallit's CF algorithm, as I carelessy read it, usually doesn't converge! Most times, it eventually falls into a period 3 loop with hairier terms than Out[212] above, but their complexfloors are all -i! Can some hay be made from this looping? —rwg
participants (2)
-
Bill Gosper -
Mike Stay