11
$\begingroup$

I know there is a nice way of getting the continued fraction expansion of quadratic irrationals mainly because they recur after a point, and if they recur after a point they are quadratic irrationals. When constructing the expansion you can multiply by conjugates (kind of), e.g.

$\sqrt 3 =1+\sqrt 3 -1 = 1+\frac {1}{\frac {\sqrt 3 +1}{2}} $

Where you use $(\sqrt 3 - 1)(\sqrt 3 +1)=2$.

Are there identities that would help with the construction for $ \sqrt[3]{2} $?

One I thought was useful in the first step to get [1; 3,...] was

$ (\sqrt[3]{2}-1)( \sqrt[3]{4} + \sqrt[3]{2}+1 )=1$,

So you get:

$ \sqrt[3]{2}=1+( \sqrt[3]{2}-1 )=1+\frac {1}{ \sqrt[3]{4} + \sqrt[3]{2}+1 }= 1+\frac {1}{3+ (\sqrt[3]{4} + \sqrt[3]{2}-2)} $

Thanks for the help.

$\endgroup$
4
  • 3
    $\begingroup$ As far as I am aware very little is known about the continued fraction of any algebraic number with degree greater than $2$. However your computations can be simplified by working with polynomials, starting with the fact that $\root3\of2$ is a root of $x^3-2$. I have an exposition using this very example here starting at page 80. $\endgroup$
    – David
    May 3, 2014 at 13:21
  • $\begingroup$ @David Yeh, that was mentioned in our number theory class. Thanks for the link to the ps. It's really helpful (+1). Its pretty much an answer, that polynomial method and the identity that comes after it, for the more complicated way. Thanks for the post. $\endgroup$
    – snulty
    May 3, 2014 at 17:43
  • $\begingroup$ There are rules to derive CF for higher roots. For more info look at this Wikipedia page: en.wikipedia.org/wiki/Generalized_continued_fraction $\endgroup$ Sep 9, 2017 at 3:34
  • $\begingroup$ Not only the $3^{rd}$ but $n^{th}$ degree is actually explained in the Continued Fractions of Algebraic Numbers paper by Enrice Bombieri and Alfred J. var der Poorten paper at page 152. $\endgroup$
    – Redu
    Apr 2 at 18:58

2 Answers 2

6
$\begingroup$

Starting from the column vector $(1,0,0,-2)$, consider the following steps:

Step a) Repeat multiplication by the matrix $A$ $$A=\begin{bmatrix} 1&0&0&0\\ 3&1&0&0\\ 3&2&1&0\\ 1&1&1&1 \end{bmatrix}$$ while the coefficients of the resulting vector have different signs.

Step b) Reverse the coefficients of the vector, or equivalently multiply by $$B=\begin{bmatrix} 0&0&0&1\\ 0&0&1&0\\ 0&1&0&0\\ 1&0&0&0 \end{bmatrix}$$

Then the number of times you multiply by $A$ in step a gives the partial quotients of continued fraction of $\sqrt[3]{2}$.


For, starting from $(1,0,0,-2)$, successive multiplication by $A$ gives: \begin{align} (1,0,0,-2) &\xrightarrow A\color{red}{(1,3,3,-1)}\\ &\xrightarrow A(1,6,12,6) \end{align} hence in step a we multiply by $A$ one time only, because $(1,6,12,6)$ have positive coefficients only, hence the first partial quotient is $1$: $$\sqrt[3]{2}=1+\cdots$$

Apply step b to $(1,3,3,-1)$ we get $(-1,3,3,1)$. Then applying step a to $(-1,3,3,1)$, successive multiplication by $A$ gives: \begin{align} (-1,3,3,1) &\xrightarrow A(-1,0,6,6)\\ &\xrightarrow A(-1,-3,3,11)\\ &\xrightarrow A\color{red}{(-1,-6,-6,10)}\\ &\xrightarrow A(-1,-9,-21,-3)\\ \end{align} hence the second partial quotient is $3$: $$\sqrt[3]{2}=1+\frac 1{3+}\cdots$$ and so on...


This algorithm holds for every algebraic number of third degree which is the only positive root of it minimal polynomial. For higher degree the matrix $A$ is enlarged as in the Tartaglia-Pascal triangle; for example for fourth degree: $$A=\begin{bmatrix} 1&0&0&0&0\\ 4&1&0&0&0\\ 6&3&1&0&0\\ 4&3&2&1&0\\ 1&1&1&1&1 \end{bmatrix}$$


For the intuition behind this algorithm. Then vector $(1,0,0,-2)$ corresponds to the polynomial $p(x)=x^3-2$. Multyplication by $A$ corresponds to $p(x)\mapsto p(x+1)$, while revesing in step b corresponds to $p(x)\mapsto x^3p(1/x)$. Finally Descartes's signs rule provide the stopping criterion in step a.

$\endgroup$
5
  • $\begingroup$ So just to see if I understand a bit why this works. $(1,0,0,-2)$ is representing $1x^3+0x^2+0x-2$. Then $A$ and $B$ are some kind of linear maps on this polynomial ring/vector space. $A$ looks like $p\mapsto p+p’+p’’/2!+p’’’/3!$, which is a kind of Taylor expansion, while B I suppose can be seen like the map $p(x)->x^3*p(1/x)$. I have no idea why this works though. Is there some intuition for it? It seems really cool. $\endgroup$
    – snulty
    Oct 26, 2019 at 10:37
  • $\begingroup$ @snulty: I added explanation in answer, thank'you $\endgroup$ Oct 26, 2019 at 11:09
  • $\begingroup$ @FabioLucchini Can this method be used to bound the continued fraction coefficients of $\sqrt[3]{2}$? $\endgroup$ Nov 10, 2019 at 18:49
  • $\begingroup$ @franklin I am not sure the ciefficients are bounded in the first place. $\endgroup$ Nov 10, 2019 at 21:57
  • $\begingroup$ @OscarLanzi No, they’re probably not bounded, but I meant bounding them using something like big-O notation (showing that they have sub-quadratic growth, or sub cubic growth, or sub-exponential growth, or something like that). $\endgroup$ Nov 10, 2019 at 22:28
1
$\begingroup$

The accepted answer looks like based on Vincent's continued fractions method (1836). Downside is it's inefficiency. Say, the root is at $0.000001$ so $a_0=0$. In order to calculate the next term $a_1$ you have to invert the polynomial and the root of the inverted polynomial appears at $1000000$. This means at the next stage you have to perform $p(x)↦p(x+1)$ translation 1000000 times.

Instead one should find the lowest bound $b_0$ of the positive roots and perform a $p_0(x)↦p_0(x+b_0+1) = p_1(x)$ translation. We should also know that the lowest bound is just a bound and most probably doesn't yield an exact figure that pinpoints the smallest positive root. This means, we may have to perform subsequent lowest bound attempts on the translated polynomials up until there is no sign change remains in the coefficients of the last obtained polynomial, a.k.a. $var(p_n(x)) = 0$ which means there is no positive root according to Descartes Rule of Sign Change. Then the $i^{th}$continued fraction coefficient $a_i$ would be the sum of all horizontal translation amounts less $1$ such as $a_i = b_{0,i}+b_{1,i}+...+b_{n,i}+n$. Obviously if the subsequent translations yield a no sign change at the polynomial coefficients and at the same time $p(0) = 0$ case occurs then the continued fraction ends here. If not then we need to perform $p(\frac{1}{x-1})$ translation (one step to the right and invert) which is two translations one after the other like $p(x-1)$ and $p(\frac{1}{x})$. Keep in mind that inverting a polynomial like $p(\frac{1}{x})$ is as simple as reversing the coefficients of the polynomial. Such as if $p(x) = x^4+7x^2+2x-5$ then $p(\frac{1}{x}) = -5x^4+2x^3+7x+1$ but we are only interested in the roots and should make the initial coefficient 1. Accordingly dividing all coefficients by $-5$ we can safely say that the $p(\frac{1}{x})$ of our interest would actually be $p(\frac{1}{x}) = x^4-\frac{2}{5}x^3-\frac{7}{5}x-\frac{1}{5}$.

Now there are two crucial parts to this problem.

  1. Efficiently and most precisely finding the lowest bound.
  2. Translating the polynomial by an arbitrary amount ($b_{lower}+1$) in it's extended form.

1. Lowest Positive Bound

There are several linear and quadratic algorithms to find the lower positive bound. Linear ones resolve faster but yielding a coarse lower bound while quadratic ones yield much finer bounds. Keep in mind that a sharper lower positive bound would minimize the translation count dramatically. According to my calculations on overall performance, I prefer a quadratic one. If you need to know more about them please drop a comment and i will extend the answer.

2. Translation of a Polynomial by an Arbitrary Amount

This is as simple as performing subsequent synthetic divisions, the degree of the polynomial many times. It's known as the Ruffini-Horner Method. A description of how it works can be found in one of my SO answers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.