Menny's profile - activity

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

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
-0.267949192431123
sage: RR(sqrt(3)).frac()
0.732050807568877

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]

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?

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

I guess this is a very simple question:

What changes do I need to make in order to make

sage: sqrt(2) %1

work?

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

Thanks a lot, Menny

This method also gives the trace :)

@parzan - you're the man!

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

Given a quadratic field, say,

K.<a>=QuadraticField(2)

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

(For number-theoretic background: http://en.wikipedia.org/wiki/Splittin... ) I tried to look it up but didn't find anything.

Thanks a lot!!! Menny

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

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

sage: var('x')
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)

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

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

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

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!

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?

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.