Ask Your Question
4

Continued fraction expansion of quadratic irrationals

asked 2011-05-15 19:49:17 -0500

Menny gravatar image

updated 2011-05-16 02:44:26 -0500

Let me emphasize that I am very new to sage and to computing in general, but I did research as much as I could before asking this question.

It is well know that that quadratic irrationals has eventuallyperiodic continued fraction expansion. I really tried to find a function that gives me the period of a given quadratic irrational. The best I could find was in this forum: http://www.mail-archive.com/sage-supp...

It explains that you can get using GAP the PrePeriod+Period. It has two disadvantages: the first, you can't get the pure period, i.e., without the preperiod, and the second is that it is the input is not the number itself but the polynomial it solve. If this polynomial has many positive roots it is a problem...

I tried to look also in PARI and didn't find anything. I did see that it is written that sage itself does not have this function.

Let me also remark that such algorithm exist. My question: Is there a way (via packages that are contained in sage) to find the period of a given quadratic irrational?

Thanks a lot! Menny

edit retag flag offensive close merge delete

Comments

It seems that you are correct that this is not the case - yet. In fact, see http://groups.google.com/group/sage-support/tree/browse_frm/month/2008-05?_done=%2Fgroup%2Fsage-support%2Fbrowse_frm%2Fmonth%2F2008-05%3F& for something related. Can you point us to some of the algorithms? Also, the current expansion is in pure Python, so rather slow.

kcrisman gravatar imagekcrisman ( 2011-05-16 05:27:01 -0500 )edit

I didn't find the algorithm yet, but you can see that it is implemented in maple: http://www.maplesoft.com/support/help/Maple/view.aspx?path=numtheory/cfrac I'll go hunting for the algorithms.

Menny gravatar imageMenny ( 2011-05-16 08:48:22 -0500 )edit

It's also implemented (for some quadratic irrationals) in Mathematica / Wolfram|Alpha. See: http://www.wolframalpha.com/input/?i=continued+fraction+sqrt%2817%29%2F12 (period is 6) and http://www.wolframalpha.com/input/?i=continued+fraction+sqrt%28100027%29%2F12 (period is large, you'd have to count it yourself I guess after clicking "more terms" a bunch of times).

benjaminfjones gravatar imagebenjaminfjones ( 2011-05-16 13:16:07 -0500 )edit

I think what @Menny wanted was something that gives the period without having to count and click more terms :)

kcrisman gravatar imagekcrisman ( 2011-05-17 02:57:18 -0500 )edit

I mainly want to be able to work with it through sage and manipulate the results I'm getting. I can seems to find the algorithms.... I looked in Cohen books, and asked for the help of google and didn't find anything yet. Is there a generic references of Number theory algorithms?

Menny gravatar imageMenny ( 2011-05-17 04:02:18 -0500 )edit

4 answers

Sort by » oldest newest most voted
3

answered 2011-05-17 06:59:23 -0500

benjaminfjones gravatar image

As far as I can tell, there aren't any packages available in Sage beyond the GAP package you mention above. There is a relatively simple algorithm for finding the period and I think it would be worth implementing this in the continued fractions module in Sage.

I created a trac ticket for this enhancement: Trac #11345

A colleague of mine who works on diophantine approximation communicated an algorithm to me which I'll paraphrase below. The algorithm takes a specific quadratic irrational and would determine the pre-period (if desired), the periodic sequence, and the length of the period. The algorithm makes use of the following classical results (which I don't have specific references for yet).

Theorem(Galois): Let $\zeta\in\mathbb{Q}(\sqrt{D})$ be a positive quadratic irrational. Then $\zeta$ has a purely periodic continued fraction iff $\zeta > 1$ and the conjugate of $\zeta$ under the map $\sqrt{D}\mapsto -\sqrt{D}$ is between -1 and 0.

Theorem(Lagrange?): The period of a purely periodic quadratic irrational $\zeta$ as above has length at most $2D$ (and this upper bound is sharp?). I'll need to find a reference for that.

Algorithm: (to determine the period of a quadratic irrational number)

INPUT: $\zeta$, a positive quadratic irrational in the form $\zeta = q + r\sqrt{D}$ for rational numbers $q, r$.

  1. Check if $\zeta$ is purely periodic (using the theorem above).
  2. If so, we know that the period has length at most $2D$. We then determine the period by listing enough terms in the continued fraction approximation.
  3. If $\zeta$ isn’t purely periodic, replace $\zeta$ with $\frac{1}{\zeta}-\text{floor}(\frac{1}{\zeta})$ and go to step 1.

We get the length of the pre-period by counting the number of iterations above and we have an immediate upper bound on how much farther we have to search for the length of the period $2D$.

edit flag offensive delete link more

Comments

I've already said this on the Trac ticket, but it might be worth seeing if there is any code from GAP we could use, at least as pseudo-code. Also, how would we check for this being a quadratic surd? Sometimes very complicated things (think Cardano's formula-type stuff) end up being surds upon clever manipulation.

kcrisman gravatar imagekcrisman ( 2011-05-17 10:06:47 -0500 )edit

Just as a note, http://trac.sagemath.org/ticket/14567 seems to be almost ready...

kcrisman gravatar imagekcrisman ( 2014-02-08 15:10:08 -0500 )edit
2

answered 2014-02-07 23:40:06 -0500

updated 2014-02-19 19:50:05 -0500

The issue (among other things) is addressed in Sage by ticket 14567, after implementation of which you will be able to say:

sage: K.<sqrt11> = QuadraticField(11)
sage: cf = CFF(sqrt11); cf
[3; (3, 6)*]
sage: len(cf.period())
2

For literature, see also the OEIS database entry:

http://oeis.org/A003285

edit flag offensive delete link more
0

answered 2011-07-12 17:05:38 -0500

Menny gravatar image

Via the reference within this page: http://www.numbertheory.org/php/surd....

I found a more elegant algorithm than the one sketched above:

Algorithm for finding the period of a quadratic irrational

  1. Input: $(a,b,c)\in Z \times N\times Z$ and $b$ not a perfect square. This triple represents $\frac{a+\sqrt{b}}{c}$.

  2. If $c$ does not divide $b-a^{2}$ then multiply everything by $\frac{|c|}{|c|}$ , and get new triple that we call $(a',b',c')$

  3. Set $P_{0}=a'$ , $Q_{0}= c'$, $d=c'$.

  4. For $k\geq0$ set

(a) $\alpha_{k}=\frac{P_{k}+\sqrt{d}}{Q_{k}}$

(b) $a_{k}=\lfloor\alpha_{k}\rfloor$

(c) $P_{k+1}=a_{k}Q_{k}-P_{k}$

(d) $Q_{k+1}=\frac{d-P_{k+1}^{2}}{Q_{k}}$

  1. Then $\alpha_{0}=\frac{a+\sqrt{b}}{c}=[a_{0},a_{1},a_{2},...]$

  2. Let $k< l$ be the first pair of integers which satisfy that $$(P_{k},Q_{k})=(P_{l},Q_{l})$$ then the period of $\alpha_{0}$ is $(a_{k},\dots,a_{l-1})$ .

Hopefully this will help implementing it...

edit flag offensive delete link more

Comments

That's very helpful. Thanks for the reference. I had already implemented a first draft of the algorithm I described above, but I think what you've described here is going to be much faster. If you want to look at what I've got so far, email me.

benjaminfjones gravatar imagebenjaminfjones ( 2011-07-13 07:40:13 -0500 )edit
0

answered 2011-05-17 11:28:34 -0500

Menny gravatar image

As a continuation of the reply by Benjamin, Let me give some references and give more information.

Both Theorems appear in the book "Continued Fractions" By Andrew Mansfield Rockett and Peter Szüsz. The first is Theorem 3 on page 45, and the second is a remark before Theorem 1 on page 50. The second is not stated correctly (there should not be any coeffiecient before the square root):

Theorem(Lagrange Estimate): Let $t= \frac{P_0+\sqrt{D}}{Q_0}$ with $D$ not a perfect square and $P_0,Q_0$ are integers. Then the length of the period of $t$ is at most $2D$.

A better asymptotics is given by the following (which is Theorem 1 of page 50):

Theorem: Let $t$ be as above with the addtional assumption that $Q_0$ divide $D-P_0^2$. Then if $L(t)$ denoted the length of the period of $t$ then $$L(t)=O(\sqrt{D}log(D))$$

I'm not sure what the constant is (it is related to the divisor function)... I didn't read the proof yet!

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2011-05-15 19:49:17 -0500

Seen: 1,204 times

Last updated: Feb 19 '14