Finite residue fields

We can take the residue field of maximal ideals in the ring of integers of number fields. We can also take the residue field of irreducible polynomials over \(\GF{p}\).

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 7)
sage: P = K.ideal(29).factor()[0][0]
sage: k = K.residue_field(P); k
Residue field in abar of Fractional ideal (2*a^2 + 3*a - 10)
sage: k.order()
841

We reduce mod a prime for which the ring of integers is not monogenic (i.e., 2 is an essential discriminant divisor):

sage: # needs sage.rings.number_field
sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 8)
sage: F = K.factor(2); F
(Fractional ideal (-1/2*a^2 + 1/2*a - 1)) * (Fractional ideal (-a^2 + 2*a - 3))
* (Fractional ideal (3/2*a^2 - 5/2*a + 4))
sage: F[0][0].residue_field()
Residue field of Fractional ideal (-1/2*a^2 + 1/2*a - 1)
sage: F[1][0].residue_field()
Residue field of Fractional ideal (-a^2 + 2*a - 3)
sage: F[2][0].residue_field()
Residue field of Fractional ideal (3/2*a^2 - 5/2*a + 4)

We can also form residue fields from \(\ZZ\):

sage: ZZ.residue_field(17)
Residue field of Integers modulo 17

And for polynomial rings over finite fields:

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(5)[]
sage: I = R.ideal(t^2 + 2)
sage: k = ResidueField(I); k
Residue field in tbar of Principal ideal (t^2 + 2) of
 Univariate Polynomial Ring in t over Finite Field of size 5

AUTHORS:

• David Roe (2007-10-3): initial version

• William Stein (2007-12): bug fixes

• John Cremona (2008-9): extend reduction maps to the whole valuation ring add support for residue fields of ZZ

• David Roe (2009-12): added support for \(GF(p)(t)\) and moved to new coercion framework.

class sage.rings.finite_rings.residue_field.LiftingMap

Bases: Section

Lifting map from residue class field to number field.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 + 2)
sage: F = K.factor(5)[0][0].residue_field()
sage: F.degree()
2
sage: L = F.lift_map(); L
Lifting map:
  From: Residue field in abar of Fractional ideal (a^2 + 2*a - 1)
  To:   Maximal Order generated by a in Number Field in a with defining polynomial x^3 + 2
sage: L(F.0^2)
3*a + 1
sage: L(3*a + 1) == F.0^2
True

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(13)[]
sage: P = R.ideal(8*t^12 + 9*t^11 + 11*t^10 + 2*t^9 + 11*t^8
....:             + 3*t^7 + 12*t^6 + t^4 + 7*t^3 + 5*t^2 + 12*t + 1)
sage: k.<a> = P.residue_field()
sage: k.lift_map()
Lifting map:
  From: Residue field in a of Principal ideal (t^12 + 6*t^11 + 3*t^10
        + 10*t^9 + 3*t^8 + 2*t^7 + 8*t^6 + 5*t^4 + 9*t^3 + 12*t^2 + 8*t + 5) of
        Univariate Polynomial Ring in t over Finite Field of size 13
  To:   Univariate Polynomial Ring in t over Finite Field of size 13

class sage.rings.finite_rings.residue_field.ReductionMap

Bases: Map

A reduction map from a (subset) of a number field or function field to this residue class field.

It will be defined on those elements of the field with non-negative valuation at the specified prime.

EXAMPLES:

sage: # needs sage.rings.number_field sage.symbolic
sage: I = QQ[sqrt(17)].factor(5)[0][0]; I
Fractional ideal (5)
sage: k = I.residue_field(); k
Residue field in sqrt17bar of Fractional ideal (5)
sage: R = k.reduction_map(); R
Partially defined reduction map:
  From: Number Field in sqrt17 with defining polynomial x^2 - 17
        with sqrt17 = 4.123105625617660?
  To:   Residue field in sqrt17bar of Fractional ideal (5)

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(next_prime(2^20))[]; P = R.ideal(t^2 + t + 1)
sage: k = P.residue_field()
sage: k.reduction_map()
Partially defined reduction map:
  From: Fraction Field of
        Univariate Polynomial Ring in t over Finite Field of size 1048583
  To:   Residue field in tbar of Principal ideal (t^2 + t + 1) of
        Univariate Polynomial Ring in t over Finite Field of size 1048583

section()

Computes a section of the map, namely a map that lifts elements of the residue field to elements of the field.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^5 - 5*x + 2)
sage: P = K.ideal(47).factor()[0][0]
sage: k = K.residue_field(P)
sage: f = k.convert_map_from(K)
sage: s = f.section(); s
Lifting map:
  From: Residue field in abar of
        Fractional ideal (-14*a^4 + 24*a^3 + 26*a^2 - 58*a + 15)
  To:   Number Field in a with defining polynomial x^5 - 5*x + 2
sage: s(k.gen())
a
sage: L.<b> = NumberField(x^5 + 17*x + 1)
sage: P = L.factor(53)[0][0]
sage: l = L.residue_field(P)
sage: g = l.convert_map_from(L)
sage: s = g.section(); s
Lifting map:
  From: Residue field in bbar of Fractional ideal (53, b^2 + 23*b + 8)
  To:   Number Field in b with defining polynomial x^5 + 17*x + 1
sage: s(l.gen()).parent()
Number Field in b with defining polynomial x^5 + 17*x + 1

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(2)[]; h = t^5 + t^2 + 1
sage: k.<a> = R.residue_field(h)
sage: K = R.fraction_field()
sage: f = k.convert_map_from(K)
sage: f.section()                                                           # needs sage.libs.ntl
Lifting map:
  From: Residue field in a of Principal ideal (t^5 + t^2 + 1) of
        Univariate Polynomial Ring in t over Finite Field of size 2 (using GF2X)
  To:   Fraction Field of
        Univariate Polynomial Ring in t over Finite Field of size 2 (using GF2X)

class sage.rings.finite_rings.residue_field.ResidueFieldFactory

Bases: UniqueFactory

A factory that returns the residue class field of a prime ideal \(p\) of the ring of integers of a number field, or of a polynomial ring over a finite field.

INPUT:

• p – a prime ideal of an order in a number field.

• names – the variable name for the finite field created. Defaults to the name of the number field variable but with bar placed after it.

• check – whether or not to check if \(p\) is prime.

OUTPUT:

The residue field at the prime \(p\).

EXAMPLES:

sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 7)                                              # needs sage.rings.number_field
sage: P = K.ideal(29).factor()[0][0]                                            # needs sage.rings.number_field
sage: ResidueField(P)                                                           # needs sage.rings.number_field
Residue field in abar of Fractional ideal (2*a^2 + 3*a - 10)

The result is cached:

sage: ResidueField(P) is ResidueField(P)                                        # needs sage.rings.number_field
True
sage: k = K.residue_field(P); k                                                 # needs sage.rings.number_field
Residue field in abar of Fractional ideal (2*a^2 + 3*a - 10)
sage: k.order()                                                                 # needs sage.rings.number_field
841

It also works for polynomial rings:

sage: R.<t> = GF(31)[]
sage: P = R.ideal(t^5 + 2*t + 11)
sage: ResidueField(P)                                                           # needs sage.rings.finite_rings
Residue field in tbar of Principal ideal (t^5 + 2*t + 11) of
 Univariate Polynomial Ring in t over Finite Field of size 31

sage: ResidueField(P) is ResidueField(P)                                        # needs sage.rings.finite_rings
True
sage: k = ResidueField(P); k.order()                                            # needs sage.rings.finite_rings
28629151

An example where the generator of the number field doesn’t generate the residue class field:

sage: # needs sage.rings.number_field
sage: K.<a> = NumberField(x^3 - 875)
sage: P = K.ideal(5).factor()[0][0]; k = K.residue_field(P); k
Residue field in abar of Fractional ideal (5, 1/25*a^2 - 2/5*a - 1)
sage: k.polynomial()
abar^2 + 3*abar + 4
sage: k.0^3 - 875
2

An example where the residue class field is large but of degree 1:

sage: # needs sage.rings.number_field
sage: K.<a> = NumberField(x^3 - 875)
sage: P = K.ideal(2007).factor()[2][0]; k = K.residue_field(P); k
Residue field of Fractional ideal (223, 1/5*a + 11)
sage: k(a)
168
sage: k(a)^3 - 875
0

And for polynomial rings:

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(next_prime(2^18))[]
sage: P = R.ideal(t - 5)
sage: k = ResidueField(P); k
Residue field of Principal ideal (t + 262142) of
 Univariate Polynomial Ring in t over Finite Field of size 262147
sage: k(t)
5

In this example, 2 is an inessential discriminant divisor, so divides the index of ZZ[a] in the maximal order for all a:

sage: # needs sage.rings.number_field
sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 8)
sage: P = K.ideal(2).factor()[0][0]; P
Fractional ideal (-1/2*a^2 + 1/2*a - 1)
sage: F = K.residue_field(P); F
Residue field of Fractional ideal (-1/2*a^2 + 1/2*a - 1)
sage: F(a)
0
sage: B = K.maximal_order().basis(); B
[1, 1/2*a^2 + 1/2*a, a^2]
sage: F(B[1])
1
sage: F(B[2])
0
sage: F
Residue field of Fractional ideal (-1/2*a^2 + 1/2*a - 1)
sage: F.degree()
1

create_key_and_extra_args(p, names=None, check=True, impl=None, **kwds)

Return a tuple containing the key (uniquely defining data) and any extra arguments.

EXAMPLES:

sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 7)                                          # needs sage.rings.number_field
sage: ResidueField(K.ideal(29).factor()[0][0])  # indirect doctest          # needs sage.rings.number_field
Residue field in abar of Fractional ideal (2*a^2 + 3*a - 10)

create_object(version, key, **kwds)

Create the object from the key and extra arguments. This is only called if the object was not found in the cache.

EXAMPLES:

sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 7)                                          # needs sage.rings.number_field
sage: P = K.ideal(29).factor()[0][0]                                        # needs sage.rings.number_field
sage: ResidueField(P) is ResidueField(P)  # indirect doctest                # needs sage.rings.number_field
True

class sage.rings.finite_rings.residue_field.ResidueFieldHomomorphism_global

Bases: RingHomomorphism

The class representing a homomorphism from the order of a number field or function field to the residue field at a given prime.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 7)
sage: P  = K.ideal(29).factor()[0][0]
sage: k  = K.residue_field(P)
sage: OK = K.maximal_order()
sage: abar = k(OK.1); abar
abar
sage: (1+abar)^179
24*abar + 12

sage: # needs sage.rings.number_field
sage: phi = k.coerce_map_from(OK); phi
Ring morphism:
  From: Maximal Order generated by a in Number Field in a with defining polynomial x^3 - 7
  To:   Residue field in abar of Fractional ideal (2*a^2 + 3*a - 10)
sage: phi in Hom(OK,k)
True
sage: phi(OK.1)
abar

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(19)[]; P = R.ideal(t^2 + 5)
sage: k.<a> = R.residue_field(P)
sage: f = k.coerce_map_from(R); f
Ring morphism:
  From: Univariate Polynomial Ring in t over Finite Field of size 19
  To:   Residue field in a of Principal ideal (t^2 + 5) of
        Univariate Polynomial Ring in t over Finite Field of size 19

lift(x)

Returns a lift of x to the Order, returning a “polynomial” in the generator with coefficients between 0 and \(p-1\).

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 7)
sage: P = K.ideal(29).factor()[0][0]
sage: k = K.residue_field(P)
sage: OK = K.maximal_order()
sage: f = k.coerce_map_from(OK)
sage: c = OK(a)
sage: b = k(a)
sage: f.lift(13*b + 5)
13*a + 5
sage: f.lift(12821*b + 918)
3*a + 19

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(17)[]; P = R.ideal(t^3 + t^2 + 7)
sage: k.<a> = P.residue_field(); f = k.coerce_map_from(R)
sage: f.lift(a^2 + 5*a + 1)
t^2 + 5*t + 1
sage: f(f.lift(a^2 + 5*a + 1)) == a^2 + 5*a + 1                             # needs sage.modules
True

section()

Computes a section of the map, namely a map that lifts elements of the residue field to elements of the ring of integers.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^5 - 5*x + 2)
sage: P = K.ideal(47).factor()[0][0]
sage: k = K.residue_field(P)
sage: f = k.coerce_map_from(K.ring_of_integers())
sage: s = f.section(); s
Lifting map:
  From: Residue field in abar of
        Fractional ideal (-14*a^4 + 24*a^3 + 26*a^2 - 58*a + 15)
  To:   Maximal Order generated by a in Number Field in a with defining polynomial x^5 - 5*x + 2
sage: s(k.gen())
a
sage: L.<b> = NumberField(x^5 + 17*x + 1)
sage: P = L.factor(53)[0][0]
sage: l = L.residue_field(P)
sage: g = l.coerce_map_from(L.ring_of_integers())
sage: s = g.section(); s
Lifting map:
  From: Residue field in bbar of Fractional ideal (53, b^2 + 23*b + 8)
  To:   Maximal Order generated by b in Number Field in b
        with defining polynomial x^5 + 17*x + 1
sage: s(l.gen()).parent()
Maximal Order generated by b in Number Field in b with defining polynomial x^5 + 17*x + 1

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(17)[]; P = R.ideal(t^3 + t^2 + 7)
sage: k.<a> = P.residue_field()
sage: f = k.coerce_map_from(R)
sage: f.section()
(map internal to coercion system -- copy before use)
Lifting map:
  From: Residue field in a of Principal ideal (t^3 + t^2 + 7) of
        Univariate Polynomial Ring in t over Finite Field of size 17
  To:   Univariate Polynomial Ring in t over Finite Field of size 17

class sage.rings.finite_rings.residue_field.ResidueField_generic(p)

Bases: Field

The class representing a generic residue field.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: I = QQ[i].factor(2)[0][0]; I
Fractional ideal (I + 1)
sage: k = I.residue_field(); k
Residue field of Fractional ideal (I + 1)
sage: type(k)
<class 'sage.rings.finite_rings.residue_field.ResidueFiniteField_prime_modn_with_category'>

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(29)[]; P = R.ideal(t^2 + 2); k.<a> = ResidueField(P); k
Residue field in a of Principal ideal (t^2 + 2) of
 Univariate Polynomial Ring in t over Finite Field of size 29
sage: type(k)                                                                   # needs sage.libs.linbox
<class 'sage.rings.finite_rings.residue_field_givaro.ResidueFiniteField_givaro_with_category'>

construction()

Construction of this residue field.

OUTPUT:

An AlgebraicExtensionFunctor and the number field that this residue field has been obtained from.

The residue field is determined by a prime (fractional) ideal in a number field. If this ideal can be coerced into a different number field, then the construction functor applied to this number field will return the corresponding residue field. See github issue #15223.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: K.<z> = CyclotomicField(7)
sage: P = K.factor(17)[0][0]
sage: k = K.residue_field(P); k
Residue field in zbar of Fractional ideal (17)
sage: F, R = k.construction()
sage: F
AlgebraicExtensionFunctor
sage: R
Cyclotomic Field of order 7 and degree 6
sage: F(R) is k
True
sage: F(ZZ)
Residue field of Integers modulo 17
sage: F(CyclotomicField(49))
Residue field in zbar of Fractional ideal (17)

ideal()

Return the maximal ideal that this residue field is the quotient by.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 + x + 1)
sage: P = K.ideal(29).factor()[0][0]
sage: k = K.residue_field(P)  # indirect doctest
sage: k.ideal() is P
True
sage: p = next_prime(2^40); p
1099511627791
sage: k = K.residue_field(K.prime_above(p))
sage: k.ideal().norm() == p
True

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(17)[]; P = R.ideal(t^3 + t^2 + 7)
sage: k.<a> = R.residue_field(P)
sage: k.ideal()
Principal ideal (t^3 + t^2 + 7) of
 Univariate Polynomial Ring in t over Finite Field of size 17

lift(x)

Returns a lift of x to the Order, returning a “polynomial” in the generator with coefficients between 0 and \(p-1\).

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 7)
sage: P = K.ideal(29).factor()[0][0]
sage: k = K.residue_field(P)
sage: OK = K.maximal_order()
sage: c = OK(a)
sage: b = k(a)
sage: k.lift(13*b + 5)
13*a + 5
sage: k.lift(12821*b + 918)
3*a + 19

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(17)[]; P = R.ideal(t^3 + t^2 + 7)
sage: k.<a> = P.residue_field()
sage: k.lift(a^2 + 5)
t^2 + 5

lift_map()

Returns the standard map from this residue field up to the ring of integers lifting the canonical projection.

EXAMPLES:

sage: # needs sage.rings.number_field sage.symbolic
sage: I = QQ[3^(1/3)].factor(5)[1][0]; I
Fractional ideal (a - 2)
sage: k = I.residue_field(); k
Residue field of Fractional ideal (a - 2)
sage: f = k.lift_map(); f
Lifting map:
  From: Residue field of Fractional ideal (a - 2)
  To:   Maximal Order generated by a in Number Field in a
        with defining polynomial x^3 - 3 with a = 1.442249570307409?
sage: f.domain()
Residue field of Fractional ideal (a - 2)
sage: f.codomain()
Maximal Order generated by a in Number Field in a
 with defining polynomial x^3 - 3 with a = 1.442249570307409?
sage: f(k.0)
1

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(17)[]; P = R.ideal(t^3 + t^2 + 7)
sage: k.<a> = P.residue_field()
sage: f = k.lift_map(); f
(map internal to coercion system -- copy before use)
Lifting map:
  From: Residue field in a of Principal ideal (t^3 + t^2 + 7) of
        Univariate Polynomial Ring in t over Finite Field of size 17
  To:   Univariate Polynomial Ring in t over Finite Field of size 17
sage: f(a^2 + 5)
t^2 + 5

reduction_map()

Return the partially defined reduction map from the number field to this residue class field.

EXAMPLES:

sage: # needs sage.rings.number_field sage.symbolic
sage: I = QQ[2^(1/3)].factor(2)[0][0]; I
Fractional ideal (a)
sage: k = I.residue_field(); k
Residue field of Fractional ideal (a)
sage: pi = k.reduction_map(); pi
Partially defined reduction map:
  From: Number Field in a with defining polynomial x^3 - 2
        with a = 1.259921049894873?
  To:   Residue field of Fractional ideal (a)
sage: pi.domain()
Number Field in a with defining polynomial x^3 - 2 with a = 1.259921049894873?
sage: pi.codomain()
Residue field of Fractional ideal (a)

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 32)
sage: F = K.factor(2)[0][0].residue_field()
sage: F.reduction_map().domain()
Number Field in a with defining polynomial x^3 + x^2 - 2*x + 32
sage: K.<a> = NumberField(x^3 + 128)
sage: F = K.factor(2)[0][0].residue_field()
sage: F.reduction_map().codomain()
Residue field of Fractional ideal (1/4*a)

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(17)[]; P = R.ideal(t^3 + t^2 + 7)
sage: k.<a> = P.residue_field(); f = k.reduction_map(); f
Partially defined reduction map:
  From: Fraction Field of Univariate Polynomial Ring in t
        over Finite Field of size 17
  To:   Residue field in a of Principal ideal (t^3 + t^2 + 7) of
        Univariate Polynomial Ring in t over Finite Field of size 17
sage: f(1/t)
12*a^2 + 12*a

class sage.rings.finite_rings.residue_field.ResidueFiniteField_prime_modn(p, name, intp, to_vs, to_order, PB)

Bases: ResidueField_generic, FiniteField_prime_modn

The class representing residue fields of number fields that have prime order.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: R.<x> = QQ[]
sage: K.<a> = NumberField(x^3 - 7)
sage: P = K.ideal(29).factor()[1][0]
sage: k = ResidueField(P); k
Residue field of Fractional ideal (-a^2 - 2*a - 2)
sage: k.order()
29
sage: OK = K.maximal_order()
sage: c = OK(a)
sage: b = k(a)
sage: k.coerce_map_from(OK)(c)
16
sage: k(4)
4
sage: k(c + 5)
21
sage: b + c
3

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(7)[]; P = R.ideal(2*t + 3)
sage: k = P.residue_field(); k
Residue field of Principal ideal (t + 5) of
 Univariate Polynomial Ring in t over Finite Field of size 7
sage: k(t^2)
4
sage: k.order()
7