Ask Your Question

Menny's profile - activity

2016-11-06 08:58:08 -0500 received badge  Famous Question (source)
2015-11-02 09:26:36 -0500 received badge  Famous Question (source)
2014-06-28 20:14:52 -0500 marked best answer Continued fraction expansion of quadratic irrationals

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:

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

2014-05-06 17:15:49 -0500 received badge  Notable Question (source)
2013-12-21 05:49:57 -0500 received badge  Popular Question (source)
2013-09-17 14:46:00 -0500 received badge  Notable Question (source)
2013-09-14 23:07:31 -0500 received badge  Famous Question (source)
2012-12-25 08:14:36 -0500 received badge  Taxonomist
2012-11-06 01:06:29 -0500 received badge  Popular Question (source)
2012-03-19 02:37:46 -0500 received badge  Notable Question (source)
2011-12-21 16:42:43 -0500 marked best answer sqaure root type

In general if x % 1 fails (for x which is real) you can try RR(x) % 1 or RR(x).frac().

Note also that %1 and .frac() are different:

sage: RR(sqrt(3)) % 1
sage: RR(sqrt(3)).frac()

I guess you want the latter. Actually %1 is a bit weird:

sage: [RR((2*k+1)/2)%1 for k in range(10)]
[0.500000000000000, -0.500000000000000, 0.500000000000000, -0.500000000000000, 0.500000000000000, -0.500000000000000, 0.500000000000000, -0.500000000000000, 0.500000000000000, -0.500000000000000]
2011-12-21 01:13:06 -0500 commented answer sqaure root type

It works. But I'm having similar problems when I, for example, take x to be some complex number, and y=x.real_part. Then, y%1 return a type error... where do I found how to deal with these errors?

2011-12-21 01:07:05 -0500 commented question sqaure root type

Yes. when you write the code above you get an error regarding the type of the objects.

2011-12-20 09:04:47 -0500 asked a question sqaure root type

I guess this is a very simple question:

What changes do I need to make in order to make

sage: sqrt(2) %1


Also, what chapter in the manual I need to read in order not to ask such basic questions again??

Thanks a lot, Menny

2011-11-12 02:42:42 -0500 received badge  Popular Question (source)
2011-10-11 00:14:05 -0500 commented answer Number Fields and the Norm

This method also gives the trace :)

2011-10-02 01:14:15 -0500 commented answer splitting of primes

@parzan - you're the man!

2011-10-02 01:12:53 -0500 marked best answer splitting of primes

Are the ramified primes the ones which divide the field discriminant? If this is so you can get them by

sage: K.<y> = NumberField(x^4 - x^2 + 1)
sage: [x[0] for x in list(K.discriminant().factor())]
[2, 3]

If splitting means that the prime factors then you can check this like this:

sage: is_split = lambda F,x:sum([t[1] for t in list(F.factor(x))])>1

for example:

sage: K.<y> = NumberField(x^2 + 1)
sage: for x in range(30):
    if is_prime(x):
        print x%4,is_split(K,x)
2 True
3 False
1 True
3 False
3 False
1 True
1 True
3 False
3 False
1 True
2011-09-27 09:17:08 -0500 asked a question splitting of primes

Given a quadratic field, say,


Is there a method to know if a given prime splits/ stay inert/ ramify in K?

(For number-theoretic background: ) I tried to look it up but didn't find anything.

Thanks a lot!!! Menny

2011-08-31 04:24:49 -0500 commented answer extracting the coefficients of a linear combination

thanks a lot! this is an act of pure giving... Menny

2011-08-31 04:23:28 -0500 marked best answer extracting the coefficients of a linear combination

I take it you understand how to get the coefficients in the standard basis, e.g.:

sage: var('x')
sage: K.<a> = NumberField(x^2+1)
sage: 3+5*a+a^2                 
5*a + 2
sage: (3+5*a+a^2).vector()
(2, 5)

Then going to your preferred basis is just a linear algebra problem. For example, if your preferred QQ-basis is (1,1) and (2,0) then you could do:

sage: Q2 = (QQ^2).span_of_basis([(1,1), (2,0)]);  Q2
Vector space of degree 2 and dimension 2 over Rational Field
User basis matrix:
[1 1]
[2 0]
sage: Q2.coordinates([2,5])                         
[5, -3/2]

Check that this is correct:

sage: 5*vector([1,1]) + (-3/2)*vector([2,0])        
(2, 5)
2011-08-28 03:23:10 -0500 asked a question extracting the coefficients of a linear combination

Let me just say that I'm quite new to sage (although I'm making a progress!)

I wish to input a number field (in my case real quadratic field), a basis $w_1,w_2$ over $ \mathbb Q$ and an element $v$ of this number field and get the coefficient of $v$ as a linear combination of $w_1$ and $w_2$. I.e., if $v=aw_1+bw_2$ I wish to get (a,b).

I tried doing this with just solving equations in matrices but I didn't find a way to make it solve the equations over the base field $ \mathbb Q$.

Thanks a lot for helping! Menny

2011-07-12 17:05:38 -0500 answered a question Continued fraction expansion of quadratic irrationals

Via the reference within this page:

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...

2011-05-17 13:27:31 -0500 received badge  Good Question (source)
2011-05-17 11:32:22 -0500 received badge  Scholar (source)
2011-05-17 11:32:22 -0500 marked best answer Continued fraction expansion of quadratic irrationals

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$.

2011-05-17 11:28:34 -0500 answered a question Continued fraction expansion of quadratic irrationals

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!

2011-05-17 10:31:29 -0500 received badge  Supporter (source)
2011-05-17 04:02:18 -0500 commented question Continued fraction expansion of quadratic irrationals

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?

2011-05-16 08:48:22 -0500 commented question Continued fraction expansion of quadratic irrationals

I didn't find the algorithm yet, but you can see that it is implemented in maple: I'll go hunting for the algorithms.

2011-05-16 05:27:09 -0500 received badge  Nice Question (source)