Optimized Quadratic Number Field Elements¶
This file defines a Cython class NumberFieldElement_quadratic
to speed up
computations in quadratic extensions of \(\QQ\).
AUTHORS:
- Robert Bradshaw (2007-09): Initial version
- David Harvey (2007-10): fix up a few bugs, polish around the edges
- David Loeffler (2009-05): add more documentation and tests
- Vincent Delecroix (2012-07): comparisons for quadratic number fields (trac ticket #13213), abs, floor and ceil functions (trac ticket #13256)
Todo
The _new()
method should be overridden in this class to copy the D
and standard_embedding
attributes
-
class
sage.rings.number_field.number_field_element_quadratic.
NumberFieldElement_quadratic
¶ Bases:
sage.rings.number_field.number_field_element.NumberFieldElement_absolute
A NumberFieldElement_quadratic object gives an efficient representation of an element of a quadratic extension of \(\QQ\).
Elements are represented internally as triples \((a, b, c)\) of integers, where \({\rm gcd}(a, b, c) = 1\) and \(c > 0\), representing the element \((a + b \sqrt{D}) / c\). Note that if the discriminant \(D\) is \(1 \bmod 4\), integral elements do not necessarily have \(c = 1\).
TESTS:
sage: from sage.rings.number_field.number_field_element_quadratic import NumberFieldElement_quadratic
We set up some fields:
sage: K.<a> = NumberField(x^2+23) sage: a.parts() (0, 1) sage: F.<b> = NumberField(x^2-x+7) sage: b.parts() (1/2, 3/2)
We construct elements of these fields in various ways - firstly, from polynomials:
sage: NumberFieldElement_quadratic(K, x-1) a - 1 sage: NumberFieldElement_quadratic(F, x-1) b - 1
From triples of Integers:
sage: NumberFieldElement_quadratic(K, (1,2,3)) 2/3*a + 1/3 sage: NumberFieldElement_quadratic(F, (1,2,3)) 4/9*b + 1/9 sage: NumberFieldElement_quadratic(F, (1,2,3)).parts() (1/3, 2/3)
From pairs of Rationals:
sage: NumberFieldElement_quadratic(K, (1/2,1/3)) 1/3*a + 1/2 sage: NumberFieldElement_quadratic(F, (1/2,1/3)) 2/9*b + 7/18 sage: NumberFieldElement_quadratic(F, (1/2,1/3)).parts() (1/2, 1/3)
Direct from Rationals:
sage: NumberFieldElement_quadratic(K, 2/3) 2/3 sage: NumberFieldElement_quadratic(F, 2/3) 2/3
This checks a bug when converting from lists:
sage: w = CyclotomicField(3)([1/2,1]) sage: w == w.__invert__().__invert__() True
-
ceil
()¶ Returns the ceil.
EXAMPLES:
sage: K.<sqrt7> = QuadraticField(7, name='sqrt7') sage: sqrt7.ceil() 3 sage: (-sqrt7).ceil() -2 sage: (1022/313*sqrt7 - 14/23).ceil() 9
TESTS:
sage: K2.<sqrt2> = QuadraticField(2) sage: K3.<sqrt3> = QuadraticField(3) sage: K5.<sqrt5> = QuadraticField(5) sage: for _ in range(100): ....: a = QQ.random_element(1000,20) ....: b = QQ.random_element(1000,20) ....: assert ceil(a+b*sqrt(2.)) == ceil(a+b*sqrt2) ....: assert ceil(a+b*sqrt(3.)) == ceil(a+b*sqrt3) ....: assert ceil(a+b*sqrt(5.)) == ceil(a+b*sqrt5) sage: K = QuadraticField(-2) sage: l = [K(52), K(-3), K(43/12), K(-43/12)] sage: [x.ceil() for x in l] [52, -3, 4, -3]
-
charpoly
(var='x')¶ The characteristic polynomial of this element over \(\QQ\).
EXAMPLES:
sage: K.<a> = NumberField(x^2-x+13) sage: a.charpoly() x^2 - x + 13 sage: b = 3-a/2 sage: f = b.charpoly(); f x^2 - 11/2*x + 43/4 sage: f(b) 0
-
continued_fraction
()¶ Return the (finite or ultimately periodic) continued fraction of
self
.EXAMPLES:
sage: K.<sqrt2> = QuadraticField(2) sage: cf = sqrt2.continued_fraction(); cf [1; (2)*] sage: cf.n() 1.41421356237310 sage: sqrt2.n() 1.41421356237309 sage: cf.value() sqrt2 sage: (sqrt2/3 + 1/4).continued_fraction() [0; 1, (2, 1, 1, 2, 3, 2, 1, 1, 2, 5, 1, 1, 14, 1, 1, 5)*]
-
continued_fraction_list
()¶ Return the preperiod and the period of the continued fraction expansion of
self
.EXAMPLES:
sage: K.<sqrt2> = QuadraticField(2) sage: sqrt2.continued_fraction_list() ((1,), (2,)) sage: (1/2+sqrt2/3).continued_fraction_list() ((0, 1, 33), (1, 32))
For rational entries a pair of tuples is also returned but the second one is empty:
sage: K(123/567).continued_fraction_list() ((0, 4, 1, 1, 1, 1, 3, 2), ())
-
denominator
()¶ Return the denominator of self. This is the LCM of the denominators of the coefficients of self, and thus it may well be \(> 1\) even when the element is an algebraic integer.
EXAMPLES:
sage: K.<a> = NumberField(x^2+x+41) sage: a.denominator() 1 sage: b = (2*a+1)/6 sage: b.denominator() 6 sage: K(1).denominator() 1 sage: K(1/2).denominator() 2 sage: K(0).denominator() 1 sage: K.<a> = NumberField(x^2 - 5) sage: b = (a + 1)/2 sage: b.denominator() 2 sage: b.is_integral() True
-
floor
()¶ Returns the floor of x.
EXAMPLES:
sage: K.<sqrt2> = QuadraticField(2,name='sqrt2') sage: sqrt2.floor() 1 sage: (-sqrt2).floor() -2 sage: (13/197 + 3702/123*sqrt2).floor() 42 sage: (13/197-3702/123*sqrt2).floor() -43
TESTS:
sage: K2.<sqrt2> = QuadraticField(2) sage: K3.<sqrt3> = QuadraticField(3) sage: K5.<sqrt5> = QuadraticField(5) sage: for _ in range(100): ....: a = QQ.random_element(1000,20) ....: b = QQ.random_element(1000,20) ....: assert floor(a+b*sqrt(2.)) == floor(a+b*sqrt2) ....: assert floor(a+b*sqrt(3.)) == floor(a+b*sqrt3) ....: assert floor(a+b*sqrt(5.)) == floor(a+b*sqrt5) sage: K = QuadraticField(-2) sage: l = [K(52), K(-3), K(43/12), K(-43/12)] sage: [x.floor() for x in l] [52, -3, 3, -4]
-
galois_conjugate
()¶ Return the image of this element under action of the nontrivial element of the Galois group of this field.
EXAMPLES:
sage: K.<a> = QuadraticField(23) sage: a.galois_conjugate() -a sage: K.<a> = NumberField(x^2 - 5*x + 1) sage: a.galois_conjugate() -a + 5 sage: b = 5*a + 1/3 sage: b.galois_conjugate() -5*a + 76/3 sage: b.norm() == b * b.galois_conjugate() True sage: b.trace() == b + b.galois_conjugate() True
-
imag
()¶ Returns the imaginary part of self.
EXAMPLES:
sage: K.<sqrt2> = QuadraticField(2) sage: sqrt2.imag() 0 sage: parent(sqrt2.imag()) Rational Field sage: K.<i> = QuadraticField(-1) sage: i.imag() 1 sage: parent(i.imag()) Rational Field sage: K.<a> = NumberField(x^2 + x + 1, embedding=CDF.0) sage: a.imag() 1/2*sqrt3 sage: a.real() -1/2 sage: SR(a) 1/2*I*sqrt(3) - 1/2 sage: bool(I*a.imag() + a.real() == a) True
TESTS:
sage: K.<a> = QuadraticField(-9, embedding=-CDF.0) sage: a.imag() -3 sage: parent(a.imag()) Rational Field
-
is_integer
()¶ Check whether this number field element is an integer.
EXAMPLES:
sage: K.<sqrt3> = QuadraticField(3) sage: sqrt3.is_integer() False sage: (sqrt3-1/2).is_integer() False sage: K(0).is_integer() True sage: K(-12).is_integer() True sage: K(1/3).is_integer() False
-
is_integral
()¶ Returns whether this element is an algebraic integer.
TESTS:
sage: K.<a> = QuadraticField(-1) sage: a.is_integral() True sage: K(1).is_integral() True sage: K(1/2).is_integral() False sage: K(a/2).is_integral() False sage: K((a+1)/2).is_integral() False sage: K(a/3).is_integral() False sage: K.<a> = QuadraticField(-3) sage: a.is_integral() True sage: K(1).is_integral() True sage: K(1/2).is_integral() False sage: K(a/2).is_integral() False sage: ((a+1)/2).is_integral() True
-
is_one
()¶ Check whether this number field element is \(1\).
EXAMPLES:
sage: K = QuadraticField(-2) sage: K(1).is_one() True sage: K(-1).is_one() False sage: K(2).is_one() False sage: K(0).is_one() False sage: K(1/2).is_one() False sage: K.gen().is_one() False
-
is_rational
()¶ Check whether this number field element is a rational number.
EXAMPLES:
sage: K.<sqrt3> = QuadraticField(3) sage: sqrt3.is_rational() False sage: (sqrt3-1/2).is_rational() False sage: K(0).is_rational() True sage: K(-12).is_rational() True sage: K(1/3).is_rational() True
-
minpoly
(var='x')¶ The minimal polynomial of this element over \(\QQ\).
INPUT:
var
– the minimal polynomial is defined over a polynomial ring in a variable with this name. If not specified this defaults tox
.
EXAMPLES:
sage: K.<a> = NumberField(x^2+13) sage: a.minpoly() x^2 + 13 sage: a.minpoly('T') T^2 + 13 sage: (a+1/2-a).minpoly() x - 1/2
-
norm
(K=None)¶ Return the norm of self. If the second argument is None, this is the norm down to \(\QQ\). Otherwise, return the norm down to K (which had better be either \(\QQ\) or this number field).
EXAMPLES:
sage: K.<a> = NumberField(x^2-x+3) sage: a.norm() 3 sage: a.matrix() [ 0 1] [-3 1] sage: K.<a> = NumberField(x^2+5) sage: (1+a).norm() 6
The norm is multiplicative:
sage: K.<a> = NumberField(x^2-3) sage: a.norm() -3 sage: K(3).norm() 9 sage: (3*a).norm() -27
We test that the optional argument is handled sensibly:
sage: (3*a).norm(QQ) -27 sage: (3*a).norm(K) 3*a sage: (3*a).norm(CyclotomicField(3)) Traceback (most recent call last): ... ValueError: no way to embed L into parent's base ring K
-
numerator
()¶ Return self*self.denominator().
EXAMPLES:
sage: K.<a> = NumberField(x^2+x+41) sage: b = (2*a+1)/6 sage: b.denominator() 6 sage: b.numerator() 2*a + 1
-
parts
()¶ This function returns a pair of rationals \(a\) and \(b\) such that self \(= a+b\sqrt{D}\).
This is much closer to the internal storage format of the elements than the polynomial representation coefficients (the output of
self.list()
), unless the generator with which this number field was constructed was equal to \(\sqrt{D}\). See the last example below.EXAMPLES:
sage: K.<a> = NumberField(x^2-13) sage: K.discriminant() 13 sage: a.parts() (0, 1) sage: (a/2-4).parts() (-4, 1/2) sage: K.<a> = NumberField(x^2-7) sage: K.discriminant() 28 sage: a.parts() (0, 1) sage: K.<a> = NumberField(x^2-x+7) sage: a.parts() (1/2, 3/2) sage: a._coefficients() [0, 1]
-
real
()¶ Returns the real part of self, which is either self (if self lives it a totally real field) or a rational number.
EXAMPLES:
sage: K.<sqrt2> = QuadraticField(2) sage: sqrt2.real() sqrt2 sage: K.<a> = QuadraticField(-3) sage: a.real() 0 sage: (a + 1/2).real() 1/2 sage: K.<a> = NumberField(x^2 + x + 1) sage: a.real() -1/2 sage: parent(a.real()) Rational Field sage: K.<i> = QuadraticField(-1) sage: i.real() 0
-
sign
()¶ Returns the sign of self (0 if zero, +1 if positive and -1 if negative).
EXAMPLES:
sage: K.<sqrt2> = QuadraticField(2, name='sqrt2') sage: K(0).sign() 0 sage: sqrt2.sign() 1 sage: (sqrt2+1).sign() 1 sage: (sqrt2-1).sign() 1 sage: (sqrt2-2).sign() -1 sage: (-sqrt2).sign() -1 sage: (-sqrt2+1).sign() -1 sage: (-sqrt2+2).sign() 1 sage: K.<a> = QuadraticField(2, embedding=-1.4142) sage: K(0).sign() 0 sage: a.sign() -1 sage: (a+1).sign() -1 sage: (a+2).sign() 1 sage: (a-1).sign() -1 sage: (-a).sign() 1 sage: (-a-1).sign() 1 sage: (-a-2).sign() -1 sage: K.<b> = NumberField(x^2 + 2*x + 7, 'b', embedding=CC(-1,-sqrt(6))) sage: b.sign() Traceback (most recent call last): ... ValueError: a complex number has no sign! sage: K(1).sign() 1 sage: K(0).sign() 0 sage: K(-2/3).sign() -1
-
trace
()¶ EXAMPLES:
sage: K.<a> = NumberField(x^2+x+41) sage: a.trace() -1 sage: a.matrix() [ 0 1] [-41 -1]
The trace is additive:
sage: K.<a> = NumberField(x^2+7) sage: (a+1).trace() 2 sage: K(3).trace() 6 sage: (a+4).trace() 8 sage: (a/3+1).trace() 2
-
-
class
sage.rings.number_field.number_field_element_quadratic.
OrderElement_quadratic
¶ Bases:
sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic
Element of an order in a quadratic field.
EXAMPLES:
sage: K.<a> = NumberField(x^2 + 1) sage: O2 = K.order(2*a) sage: w = O2.1; w 2*a sage: parent(w) Order in Number Field in a with defining polynomial x^2 + 1
-
charpoly
(var='x')¶ The characteristic polynomial of this element, which is over \(\ZZ\) because this element is an algebraic integer.
EXAMPLES:
sage: K.<a> = NumberField(x^2 - 5) sage: R = K.ring_of_integers() sage: b = R((5+a)/2) sage: f = b.charpoly('x'); f x^2 - 5*x + 5 sage: f.parent() Univariate Polynomial Ring in x over Integer Ring sage: f(b) 0
-
inverse_mod
(I)¶ Return an inverse of self modulo the given ideal.
INPUT:
I
- may be an ideal of self.parent(), or an element or list of elements of self.parent() generating a nonzero ideal. A ValueError is raised if I is non-integral or is zero. A ZeroDivisionError is raised if I + (x) != (1).
EXAMPLES:
sage: OE.<w> = EquationOrder(x^2 - x + 2) sage: w.inverse_mod(13) == 6*w - 6 True sage: w*(6*w - 6) - 1 -13 sage: w.inverse_mod(13).parent() == OE True sage: w.inverse_mod(2*OE) Traceback (most recent call last): ... ZeroDivisionError: w is not invertible modulo Fractional ideal (2)
-
minpoly
(var='x')¶ The minimal polynomial of this element over \(\ZZ\).
EXAMPLES:
sage: K.<a> = NumberField(x^2 + 163) sage: R = K.ring_of_integers() sage: f = R(a).minpoly('x'); f x^2 + 163 sage: f.parent() Univariate Polynomial Ring in x over Integer Ring sage: R(5).minpoly() x - 5
-
norm
()¶ The norm of an element of the ring of integers is an Integer.
EXAMPLES:
sage: K.<a> = NumberField(x^2 + 3) sage: O2 = K.order(2*a) sage: w = O2.gen(1); w 2*a sage: w.norm() 12 sage: parent(w.norm()) Integer Ring
-
trace
()¶ The trace of an element of the ring of integers is an Integer.
EXAMPLES:
sage: K.<a> = NumberField(x^2 - 5) sage: R = K.ring_of_integers() sage: b = R((1+a)/2) sage: b.trace() 1 sage: parent(b.trace()) Integer Ring
-
-
class
sage.rings.number_field.number_field_element_quadratic.
Q_to_quadratic_field_element
¶ Bases:
sage.categories.morphism.Morphism
Morphism that coerces from rationals to elements of a quadratic number field K.
-
class
sage.rings.number_field.number_field_element_quadratic.
Z_to_quadratic_field_element
¶ Bases:
sage.categories.morphism.Morphism
Morphism that coerces from integers to elements of a quadratic number field K.