Ideals and Quotients#

Ideals of orders are of two types. All ideals are fractional and inherit from type RngOrdFracIdl. Integral ideals can have (the sub–)type RngOrdIdl. Some functions only apply to integral ideals and only ideals with the integral type can be prime. An ideal with fractional type but trivial denominator can be converted to have the integral type and any integral ideal can be converted to fractional type. Ideals can be taken of orders over \({\mathbb{Z}}\) and orders defined over a maximal order. A few functions are not implemented for the latter. Where an element or elements are returned from a function the elements are usually in the field of fractions if the ideal has the fractional type and in the order if it has integral type. Fractional ideals over \({\mathbb{Q}}\) are of type RngIntFracIdl, while integral ideals in \({\mathbb{Z}}\) have the type RngInt.

Creation of Ideals in Orders#

The general ideal constructor can be used to create ideals in orders of algebraic fields, as described below. Since ideals in orders are allowed to be fractional ideals, algebraic field elements are allowed as generators. Ideals can also be created how they are written on paper: as an element multiplied by an order.

x * O: RngElt, RngOrd -> RngOrdFracIdl#
O * x: RngElt, RngOrd -> RngOrdFracIdl#: Create the ideal \(x*O\) for element \(x\) and order \(O\). If the ideal is integral it will be returned with the integral type.

F !! I: RngOrd, RngInt -> RngOrdFracIdl#
F !! I: FldOrd, RngOrdFracIdl -> RngOrdFracIdl#
F !! I: FldRat, RngOrdFracIdl -> RngIntFracIdl#
F !! I: FldRat, RngIntFracIdl -> RngIntFracIdl#
F !! I: FldOrd, RngIntFracIdl -> RngOrdFracIdl#
O !! I: RngOrd, RngOrdFracIdl -> RngOrdIdl#
O !! I: RngInt, RngInt -> RngInt#: Make the ideal \(I\) either fractional (first case where \(F\) is a field of fractions compatible with the order of \(I\)) or integral (second case where \(O\) is an order compatible with the order of \(I\)).

ideal< O | a₁, a₂, ... , aₘ >: RngOrd, RngElt, ..., RngElt -> RngOrdFracIdl#

ideal<O | x>: RngOrd, RngIntElt -> RngOrdIdl#

ideal<O | M, d>: RngOrd, AlgMatElt, RngIntElt -> RngOrdFracIdl#

ideal<O | M, d>: RngOrd, ModDed, RngIntElt -> RngOrdFracIdl#

ideal<O | M, I1, ..., In>: RngOrd, AlgMatElt, RngOrdFracIdl, ..., RngOrdFracIdl -> RngOrdFracIdl#

ideal<O | M, [I1, ..., In]>: RngOrd, AlgMatElt, [RngOrdFracIdl] -> RngOrdFracIdl#

Given an order \(O\), as well as anything that can be used to produce a sequence of elements of the field of fractions of \(O\) return the ideal generated by those elements. If the ideal is integral then it will be returned with the integral type.

A single integer may be given in which case the principal ideal it generates will be returned. A matrix or a module over an order (ModDed) (or a matrix and ideals which the module could be created from) can be supplied as the basis for the resulting ideal. An optional second argument is a denominator given as an integer, (except when ideals are given).

Example: Ideals (ex-dc3704)#

We give an example of the creation of an ideal generated by an element from an order.

> R<x> := PolynomialRing(Integers());
> f := x^4-420*x^2+40000;
> K<y> := NumberField(f);
> E := EquationOrder(K);
> O := MaximalOrder(K);
> elt := O ! (y^2/40+y/4);
> elt in E;
false
> I := ideal< O | elt >;
> I;
Principal Ideal of O
Generator:
    [0, 1, 1, 0]
> FieldOfFractions(O)!!I;
Principal Ideal of O
Generator:
    O.2 + O.3
> O!!$1 eq I;
true

Run in calculator

It is also possible to construct fractional ideals in \({\mathbb{Q}}\).

FractionalIdeal(x): FldRatElt -> RngIntFracIdl#
FractionalIdeal(x): RngIntElt -> RngIntFracIdl#
FractionalIdeal(x): [ FldRatElt ] -> RngIntFracIdl#
FractionalIdeal(x): [ RngIntElt ] -> RngIntFracIdl#: The fractional ideal generated by \(x\).

FractionalIdeal(I): RngInt -> RngIntFracIdl#: Make \(I\) into a fractional ideal.

Invariants#

Some information describing an ideal can be retrieved.

Order(I): RngOrdFracIdl -> RngOrd#
Order(I): RngIntFracIdl -> RngInt#: The order \(O\) which the ideal \(I\) is of.

Denominator(I): RngOrdFracIdl -> RngIntElt#
Denominator(I): RngIntFracIdl -> RngIntElt#: The denominator of the fractional ideal \(I\). This is the smallest positive integer \(d\) such that \(d I\) is an integral ideal.

PrimitiveElement(I): RngOrdIdl -> RngOrdElt#
PrimitiveElement(I): RngOrdFracIdl -> FldOrdElt#
UniformizingElement(P): RngOrdIdl -> RngOrdElt#
UniformizingElement(P): RngInt -> RngIntElt#: A primitive element of an ideal \(I\) is an element \(a\) which is in \(I\) but not in the square of \(I\). This function returns such an element \(a\). UniformizingElement returns the primitive element of a prime ideal.

Index(O, I): RngOrd, RngOrdIdl -> RngIntElt#: The index of the integral ideal \(I\), when viewed as a submodule of the order \(O\). This is the same as the cardinality of the finite quotient ring \(O/I\).

Norm(I): RngOrdIdl -> RngIntElt#
Norm(I): RngOrdFracIdl -> FldRatElt#
Norm(I): RngOrdFracIdl -> RngOrdFracIdl#
Norm(I): RngIntFracIdl -> RngIntElt#: The norm of the fractional ideal \(I\). This returns the index of the ideal if the ideal is integral, and is defined on fractional ideals by multiplicativity so that the norm of \(I^{-1}\) equals the reciprocal of the norm of \(I\).

MinimalInteger(I): RngOrdIdl -> RngElt#: Given an ideal \(I\) of an order in some number field, the function returns the least positive integer contained in the ideal.

Minimum(I): RngOrdFracIdl -> RngElt#
Min(I): RngOrdFracIdl -> RngElt#: Given an ideal \(I\), this function returns the least positive integer \(m\) if the ideal is integral or the least positive rational \(r\) if is fractional contained in \(I\).

AbsoluteNorm(I): RngOrdIdl -> RngIntElt#
AbsoluteNorm(I): RngOrdFracIdl -> FldRatElt#
NormAbs(I): RngOrdIdl -> RngIntElt#
NormAbs(I): RngOrdFracIdl -> FldRatElt#: The absolute norm of the fractional ideal \(I\). This returns the index of the ideal if the ideal is integral, and is defined on fractional ideals by multiplicativity so that the norm of \(I^{-1}\) equals the reciprocal of the norm of \(I\).

CoefficientHeight(I): RngOrdIdl -> RngIntElt#
CoefficientHeight(I): RngOrdFracIdl -> RngIntElt#: For an ideal \(I\) the coefficient height is defined to be the maximum integer occurring in the current representation of the ideal: If the ideal is given via two elements, this will be the maximal coefficient height of the generators, otherwise the maximal entry of the basis matrix.

CoefficientLength(I): RngOrdIdl -> RngIntElt#
CoefficientLength(I): RngOrdFracIdl -> RngIntElt#: For an ideal \(I\) the coefficient length is defined to be the size of the current representation: If the ideal is given via two elements, this will be the sum of the coefficient lengths of the generators, otherwise the sum of the entries of the basis matrix.

RamificationIndex(I, p): RngOrdIdl, RngIntElt -> RngIntElt#
RamificationDegree(I, p): RngOrdIdl, RngIntElt -> RngIntElt#: For a prime ideal \(I\) of an order \(O\) such that \(p \in I\) returns the maximal exponent \(e\) such that \(I^e\) divides the principal ideal \(pO\). If \(p\) is not given it is taken to be the minimal integer of \(I\).

RamificationDegree(I): RngOrdIdl -> RngIntElt#
RamificationIndex(I): RngOrdIdl -> RngIntElt#: Computes the relative ramification index of the prime ideal \(I\) over the coefficient ring. To be more precise: Let \(I\) be a prime ideal of some order \(O\) with coefficient ring \(o\). Then \(I \cap o\) is an prime ideal \(p\) in \(o\). The ramification index \(e = e(I|p)\) is the maximal exponent \(e\) such that \(I^e\) divides \(pO\).

AbsoluteRamificationDegree(I): RngOrdIdl -> RngIntElt#
AbsoluteRamificationIndex(I): RndOrdIdl -> RngIntElt#: Return the ramification index of the prime ideal \(I\) as an extension of the prime integer which is its minimum.

ResidueClassField(O, I): RngOrd, RngOrdIdl -> FldFin, Map#
ResidueClassField(I): RngOrdIdl -> FldFin, Map#: If \(I\) is a prime ideal of \(O\), this function returns the finite field \(F\) isomorphic to \(O/I\) and the map \(O\rightarrow F\).

Degree(I): RngOrdIdl -> RngIntElt#
InertiaDegree(I): RngOrdIdl -> RngIntElt#: Given a prime ideal \(I\) this function returns the relative degree \(f\) of the residue class field of the ideal \(I\). To be more precise: Let \(I\) be a prime ideal in some order \(O\) with coefficient ring \(o\). Then \(p := o \cap I\) is a prime ideal in \(o\) and the residue class field \(O/I\) is a finite extension of degree \(f=f(I|p)\) of the residue class field \(o/p\).

AbsoluteInertiaDegree(I): RngOrdIdl -> RngIntElt#
AbsoluteInertiaIndex(I): RngOrdIdl -> RngIntElt#: Return the inertia index of the prime ideal \(I\) as an extension of the prime integer which is its minimum.

Valuation(I, p): RngOrdFracIdl, RngOrdIdl -> RngIntElt#
Valuation(I, p): RngIntFracIdl, RngInt -> RngIntElt#: Given an ideal \(I\) and a prime ideal \(p\) in an order \(O\), returns the valuation \(v_p(I)\) of \(I\) at \(p\), that is, the number of factors \(p\) in the prime ideal decomposition of \(I\). Note that, since the ideal \(I\) is allowed to be a fractional ideal, the returned value may be a negative integer. If \(p\) has been constructed using the Montes algorithm then this valuation computation will also use the Montes algorithm [Stainsby, 2018].

Content(I): RngOrdFracIdl -> RngIntElt#: The content of the ideal \(I\), i.e. the maximal ideal of the base ring dividing \(I\).

Example: Ideal Invar (ex-f01e3a)#

The retrieval of some properties of an ideal is illustrated.

> R<x> := PolynomialRing(Integers());
> M := MaximalOrder(x^5 + 4*x^4 - x^3 + 7*x^2 - 1);
> R<x> := PolynomialRing(M);
> O := MaximalOrder(x^3 - 2);
> M;
Maximal Equation Order with defining polynomial x^5 + 4*x^4 - x^3 + 7*x^2 - 1
over Z
> O;
Maximal Order of Equation Order with defining polynomial x^3 - [2, 0, 0, 0, 0]
over M
> I := 19/43*M.4*O.3*O;
> I;
Fractional Principal Ideal of O
Generator:
    19/43*M.4*O.3
> Order(I);
Maximal Order of Equation Order with defining polynomial x^3 - [2, 0, 0, 0, 0]
over M
> Norm(Norm(I));
15545474078591793458176/3177070365797955661914307
> FactorizationOfQuotient($1);
[ <2, 10>, <19, 15>, <43, -15> ]
> Norm(Norm(O.3));
1024
> Norm(M.4);
1
> Denominator(I);
43
> Denominator(O.3);
1
> PrimitiveElement(I);
19/43*M.4*O.3
> Minimum(I);
19/43
> [ Norm(Norm(tuple[1])) : tuple in Factorization(I) ];
[ 2, 4, 4, 43, 43, 43, 6859, 3418801, 3418801, 3418801, 2213314919066161 ]

Run in calculator

Basis Representation#

The basis of an ideal can be computed as well as related matrices.

Basis(I): RngOrdIdl -> [RngOrdElt]#
Basis(I): RngOrdFracIdl -> [FldOrdElt]#
Basis(I): RngIntFracIdl -> [FldRatElt]#
Basis(I, R): RngOrdFracIdl, Rng -> [RngElt]#: Given an ideal \(I\) of an order \(O\) of the algebraic field \(F\), this function returns a basis for \(I\) as a sequence of elements of \(F\) (if fractional), \(O\) (if integral) or the ring \(R\) if given.

BasisMatrix(I): RngOrdFracIdl -> MtrxSpcElt#: Returns the basis matrix for the ideal \(I\) of the order \(O\). The basis matrix consists of the elements of a basis for the ideal written as rows of rational coefficients with respect to the basis of \(O\). The entries of the matrix are elements of \({\mathbb{Z}}\) for an integral ideal of an order over \({\mathbb{Z}}\) only or the field of fractions of the coefficient ring of \(O\).

TransformationMatrix(I): RngOrdFracIdl -> MtrxSpcElt, RngIntElt#: Returns the transformation matrix for the ideal \(I\) of the order \(O\), as well as a denominator. The transformation matrix consists of the elements of a basis for the ideal written as rows of coefficients with respect to the basis of the order \(O\). The entries of the matrix are elements of \({\mathbb{Z}}\) for an integral ideal of an order over \({\mathbb{Z}}\) or the field of fractions of the coefficient ring of \(O\).

CoefficientIdeals(I): RngOrdFracIdl -> [RngOrdFracIdl]#: The coefficient ideals of the ideal \(I\) in a relative extension. These are the ideals \(\{A_i\}\) of the coefficient ring of the order of \(I\) such that for every element \(e \in I\), \(e = \sum_i a_i*b_i\) where \(\{b_i\}\) is the basis returned for \(I\) and each \(a_i \in A_i\).

Example: Ideal Basis (ex-49f139)#

Continuing from the last example, the use of the basis functions for ideals is shown.

> Basis(I);
[
    19/43*M.4*O.3,
    19/86*M.4*O.1,
    19/43*M.4*O.2
]
> Basis(I, NumberField(O));
[
    19/86*$.1^3*$.1^2,
    19/86*$.1^3,
    19/86*$.1^3*$.1
]
> BasisMatrix(I);
[0 0 19/43*M.4]
[19/86*M.4 0 0]
[0 19/43*M.4 0]
> TransformationMatrix(I);
[M.1 0 0]
[0 M.1 0]
[0 0 M.1]
1

Run in calculator

For relative extensions, a different method is available:

Module(I): RngOrdFracIdl -> ModDed, Map#: For an ideal \(I\) in some relative extension, return a Dedekind module over the coefficient ring with the “same” basis.

Two–Element Presentations#

All ideals of maximal orders can be generated by one or two elements of the field of fractions of the order they are an ideal of.

Generators(I): RngOrdIdl -> [ RngOrdElt ]#
Generators(I): RngOrdFracIdl -> [ FldOrdElt ]#
Generators(I): RngIntFracIdl -> [ FldRatElt ]#: Given a (fractional) ideal \(I\) of \(O\), return a sequence containing two elements that generate \(I\) as an ideal. The elements will be in the order iff the ideal is integral, otherwise they will come from the field of fractions of \(O\).

TwoElement(I): RngOrdFracIdl -> FldOrdElt, FldOrdElt#: Given a (fractional) ideal \(I\) of \(O\), return two elements of (the field of fractions of) \(O\) that generate \(I\) as an ideal.

TwoElementNormal(I): RngOrdIdl -> RngOrdElt, RngOrdElt, RngIntElt#: Given an integral ideal \(I\) of \(O\) (a maximal order over \({\mathbb{Z}}\)), return two elements of \(O\) that form a two-element normal presentation for \(I\), as well as an integer \(g\) such that \(I\) is \(g\)-normal.

Example: Ideal Two (ex-4c86cb)#

The generators and two element presentation of \(I\) are compared.

> Generators(I);
[
    19/43*M.4*O.3
]
> TwoElement(I);
19/43*M.4*O.3
19/43*M.4*O.3

Run in calculator

Standard Names#

These utility functions implement a standard naming convention, which is used in the LMFDB (\(L\)-function database) and elsewhere. Important: the label of an ideal depends on the defining polynomial of the field (but not on any other choices).

LMFDBLabel(I): RngOrdIdl -> MonStgElg#: The name of the ideal \(I\) of a maximal order. This is a well-defined function of the ideal and the defining polynomial of the number field (which must be a simple extension of \({\mathbb{Q}}\)).

LMFDBIdeal(K, s): FldNum, MonStgElt -> RngOrdIdl#: The ideal of \({\mathbb{Z}}_K\) that has the name \(s\).

Predicates on Ideals#

Ideals may be tested for various properties and whether given elements lie in the ideal.

I eq J: RngOrdFracIdl, RngOrdFracIdl -> BoolElt#
I ne J: RngOrdFracIdl, RngOrdFracIdl -> BoolElt#
x in I: FldOrdElt, RngOrdFracIdl -> BoolElt#
x in I: RngOrdElt, RngOrdFracIdl -> BoolElt#
x notin I: FldOrdElt, RngOrdFracIdl -> BoolElt#
x notin I: RngOrdElt, RngOrdFracIdl -> BoolElt#
I subset J: RngOrdIdl, RngOrdIdl -> BoolElt#
IsIntegral(I): RngOrdFracIdl -> BoolElt#
IsIntegral(I): RngIntFracIdl -> BoolElt#: Returns true if and only if the fractional ideal \(I\) is integral.

IsZero(I): RngOrdFracIdl -> BoolElt#: Returns true if the ideal \(I\) is the zero ideal, false otherwise.

IsOne(I): RngOrdIdl -> BoolElt#
IsOne(I): RngOrdFracIdl -> BoolElt#
IsOne(I): RngIntFracIdl -> BoolElt#: Returns true if the ideal \(I\) is the ideal generated by \(1\), false otherwise.

IsPrime(I): RngOrdIdl -> BoolElt, RngOrdIdl#
IsPrime(I): RngOrdFracIdl -> BoolElt#: Returns true if and only if the ideal \(I\) is a prime ideal of Order(I). If Order(I) is maximal and \(I\) is a proper ideal of type RngOrdIdl, then in the case \(I\) is not prime, the function also returns a proper divisor.

IsPrincipal(I): RngOrdFracIdl -> BoolElt, FldOrdElt#

verbose: ClassGroup                    Default: Verbose : 5

Returns true if the fractional ideal \(I\) of the order \(O\) is a principal ideal, otherwise false. If \(I\) is principal, a generator (as an element of the field of fractions of \(O\)) is also returned. If it is known or easy to decide whether \(I\) is principal the function will return quickly. If it is necessary to compute the class group of \(O\) the function will be slower. If the generator is required this may cause the function to take longer as well. If \(I\) is an ideal of a non-maximal order the Unit group may be required also. Class group and unit group computations will be carried out to the most rigorous proof level, if this level of proof is not required then the UnitGroup should be precomputed and ClassGroup bounds set before calling IsPrincipal.

IsRamified(P): RngOrdIdl -> BoolElt#: Returns true iff the ramification index of the prime ideal \(P\) is greater than \(1\).

IsRamified(P, O): RngOrdIdl, RngOrd -> BoolElt#
IsRamified(P, O): RngIntElt, RngOrd -> BoolElt#
IsRamified(P, O): RngInt, RngOrd -> BoolElt#: Returns true iff for any prime ideal \(Q\) lying above \(P\) in the order \(O\), the ramification index of \(Q\) is greater than \(1\). \(P\) must be a prime ideal of the base ring of \(O\) or a prime number (if \(O\) is an absolute order).

IsSquarefree(I): RngOrdIdl -> BoolElt#
IsSquarefree(I): RngInt -> BoolElt#: Returns true iff the ideal \(I\) has no repeated factors.

IsTotallyRamified(P): RngOrdIdl -> BoolElt#: Returns true iff the ramification index of the prime ideal \(P\) equals the degree of its order over the base field.

IsTotallyRamified(P, O): RngOrdIdl, RngOrd -> BoolElt#
IsTotallyRamified(P, O): RngIntElt, RngOrd -> BoolElt#: Returns true iff for any prime ideal \(Q\) lying above \(P\) in the order \(O\), the ramification index of \(Q\) equals the field degree. \(P\) must be a prime ideal of the base ring of \(O\) or a prime number (if \(O\) is an absolute order).

IsTotallyRamified(K): FldAlg -> BoolElt#: Returns true if all primes dividing the discriminant the maximal order of the algebraic field \(K\) are totally ramified over the coefficient field of \(K\).

IsTotallyRamified(O): RngOrd -> BoolElt#: Returns true if all primes dividing the discriminant of the maximal order \(O\) are totally ramified over the coefficient ring of \(O\).

IsWildlyRamified(P): RngOrdIdl -> BoolElt#: Returns true iff the ramification index of the prime ideal \(P\) is a multiple of the characteristic of the residue class field of \(P\).

IsWildlyRamified(P, O): RngOrdIdl, RngOrd -> BoolElt#
IsWildlyRamified(P, O): RngIntElt, RngOrd -> BoolElt#: Returns true iff for any prime ideal \(Q\) of the order \(O\) lying above \(P\), the ramification index \(e(Q|P)\) is a multiple of the characteristic of the residue class field of \(Q\). \(P\) must be a prime ideal of the base ring of \(O\) or a prime number (if \(O\) is an absolute order).

IsTamelyRamified(P): RngOrdIdl -> BoolElt#: Returns true iff the prime ideal \(P\) is not wildly ramified.

IsTamelyRamified(P, O): RngOrdIdl, RngOrd -> BoolElt#
IsTamelyRamified(P, O): RngIntElt, RngOrd -> BoolElt#: Returns true iff the prime ideal or integer \(P\) is not wildly ramified in the order \(O\).

IsUnramified(P): RngOrdIdl -> BoolElt#: Returns true iff the ramification index of the prime ideal \(P\) is \(1\).

IsUnramified(P, O): RngOrdIdl, RngOrd -> BoolElt#
IsUnramified(P, O): RngIntElt, RngOrd -> BoolElt#: Returns true iff for all prime ideals \(Q\) lying above \(P\) in the order \(O\), the ramification index of \(Q\) is \(1\). \(P\) must be a prime ideal of the base ring of \(O\) or a prime number (if \(O\) is an absolute order).

IsInert(P): RngOrdIdl -> BoolElt#: Returns true iff the inertia degree of the prime ideal \(P\) is the field degree.

IsInert(P, O): RngOrdIdl, RngOrd -> BoolElt#
IsInert(P, O): RngIntElt, RngOrd -> BoolElt#
IsInert(P, O): RngInt, RngOrd -> BoolElt#: Returns true iff the prime integer or ideal \(P\) in the base ring of the order \(O\) is inert, i.e. \(PO\) is an unramified prime ideal of \(O\).

IsSplit(P): RngOrdIdl -> BoolElt#: Returns true iff the prime ideal \(P\) is not the only prime ideal which lies above its intersection with the base ring of its order.

IsSplit(P, O): RngOrdIdl, RngOrd -> BoolElt#
IsSplit(P, O): RngIntElt, RngOrd -> BoolElt#
IsSplit(P, O): RngInt, RngOrd -> BoolElt#: Returns true iff at least two prime ideals in the order \(O\) lie above the prime integer or ideal \(P\) of the base ring of \(O\).

IsTotallySplit(P): RngOrdIdl -> BoolElt#: Returns true iff there are as many prime ideals lying above the intersection of the prime ideal \(P\) with the base ring of its order as the degree of the order of \(P\).

IsTotallySplit(P, O): RngOrdIdl, RngOrd -> BoolElt#
IsTotallySplit(P, O): RngIntElt, RngOrd -> BoolElt#
IsTotallySplit(P, O): RngInt, RngOrd -> BoolElt#: Returns true iff as many prime ideals in the order \(O\) lying above the prime integer or ideal \(P\) of the base ring of \(O\) as the degree of \(O\).

Ideal Arithmetic#

Ideals can be multiplied in several ways, divided and added. Powers of ideals, the least common multiple and the intersection of two ideals can also be calculated.

I * J: RngOrdFracIdl, RngOrdFracIdl -> RngOrdFracIdl#
I * J: RngIntFracIdl, RngOrdFracIdl -> RngOrdFracIdl#
I * J: RngIntFracIdl, RngIntFracIdl -> RngIntFracIdl#: The product \(IJ\) of the (fractional) ideals \(I\) and \(J\), generated by the products of elements in \(I\) and elements in \(J\).

x * I: RngElt, RngOrdFracIdl -> RngOrdFracIdl#
x * I: FldRatElt, RngIntFracIdl -> RngIntFracIdl#
x * I: RngIntElt, RngIntFracIdl -> RngIntFracIdl#
I * x: RngOrdFracIdl, RngElt -> RngOrdFracIdl#: Given an element \(x\) of (or coercible into) a field of fractions \(F\), and a (fractional) ideal \(I\) in the order of \(F\), return the product of the ideal and the principal ideal generated by \(x\).

&* L: [RngOrdFracIdl] -> RngOrdFracIdl#
&* L: { RngOrdFracIdl } -> RngOrdFracIdl#: The product of all ideals in the sequence or set \(L\).

I div J: RngOrdIdl, RngOrdIdl -> RngOrdIdl#
I div J: RngOrdFracIdl, RngOrdFracIdl -> RngOrdIdl#
I div J: RngInt, RngInt -> RngInt#: For ideals \(I\) and \(J\) of some maximal order such that \(J\) divides \(I\) (or equivalently that \(J\) is contained in \(I\)), return the integral ideal \(K\) such that \(JK=I\).

I / J: RngOrdFracIdl, RngOrdFracIdl -> RngOrdFracIdl#

The quotient of the (fractional) ideals \(I\) and \(J\) of a maximal order \(O\). This is the fractional ideal \(K\) of \(O\) with the property that \(JK=I\).

There are some considerations to be made here. Firstly, the “\(I/J\)” notation is interpreted as above, and not (say) as an ideal of the quotient \(O/J\) (see also the example with \({\bf Z}\) as a number field order in Section Ideals of \({\mathbb{Z}}\) and \({\mathbb{Z}}\) as a Number Field Order). Secondly, since \(I/J\) is only defined (in Magma) for maximal orders, this is the same (in Magma) as the ColonIdeal (or IdealQuotient) as noted below. Thirdly, \(I/J\) and I div J are not synonyms, as \(I/J\) will work even when \(J\) does not divide \(I\), while I div J will give an error in that case.

I / x: RngOrdFracIdl, RngElt -> RngOrdFracIdl#: Given an ideal \(I\) and an element \(x\) construct the fractional ideal \(I / x\).

I + J: RngOrdFracIdl, RngOrdFracIdl -> RngOrdFracIdl#
I + J: RngIntFracIdl, RngIntFracIdl -> RngIntFracIdl#
I + J: RngIntFracIdl, RngInt -> RngIntFracIdl#: The sum of the (fractional) ideals \(I\) and \(J\), generated by the sums of elements in \(I\) and elements in \(J\).

I ^ k: RngOrdFracIdl, RngIntElt -> RngOrdFracIdl#
I ^ k: RngIntFracIdl, RngIntElt -> RngIntFracIdl#: The \(k\)-th power of the (fractional) ideal \(I\) (for an integer \(k\)). If \(I\) has integral type and \(k\) is negative the result will have fractional type.

I eq J: RngOrdFracIdl, RngOrdFracIdl -> BoolElt#
I eq J: RngIntFracIdl, RngIntFracIdl -> BoolElt#
I eq J: RngIntFracIdl, RngInt -> BoolElt#: Tests if the ideals \(I\) and \(J\) are equal.

I subset J: RngOrdIdl, RngOrdIdl -> BoolElt#: Tests if the two ideals \(I\) and \(J\) of the same order are contained in each other. For invertible ideals this is equivalent to checking if \(J\) divides \(I\),

E in I: RngOrdElt, RngOrdIdl -> BoolElt#
E in I: RngOrdElt, RngOrdFracIdl -> BoolElt#
E in I: FldAlgElt, RngOrdFracIdl -> BoolElt#: Tests if the element \(E\) is actually in the ideal \(I\). The element and the ideal have to be compatible, i.e., live in the same number field.

LCM(I, J): RngOrdFracIdl, RngOrdFracIdl -> RngOrdFracIdl#
Lcm(I, J): RngOrdFracIdl, RngOrdFracIdl -> RngOrdFracIdl#
LeastCommonMultiple(I, J): RngOrdFracIdl, RngOrdFracIdl -> RngOrdFracIdl#: Return the least common multiple of ideals \(I\) and \(J\). They must both be of the same maximal order.

GCD(I, J): RngOrdFracIdl, RngOrdFracIdl -> RngOrdFracIdl#
Gcd(I, J): RngOrdFracIdl, RngOrdFracIdl -> RngOrdFracIdl#
GreatestCommonDivisor(I, J): RngOrdFracIdl, RngOrdFracIdl -> RngOrdFracIdl#: The greatest common divisor of the ideals \(I\) and \(J\) of some maximal order of an algebraic number field.

Content(M): Mtrx -> RngOrdFracIdl#: For a matrix \(M\) with entries in some number field \(k\), compute the gcd of all elements as principal ideals in the maximal order of \(k\).

I meet J: RngOrdFracIdl, RngOrdFracIdl -> RngOrdFracIdl#: The intersection of the (fractional) ideals \(I\) and \(J\). For ideal in the maximal order this is the same as the \({\operatorname{lcm}}\).

&meet S: [RngOrdFracIdl] -> RngOrdFracIdl#
&meet S: { RngOrdFracIdl } -> RngOrdFracIdl#: The intersection of all ideals \(I\) of the sequence or set \(S\). For ideals in some maximal order this is the same as the \({\operatorname{lcm}}\).

I meet R: RngOrdFracIdl, Rng -> Any#
R meet I: Rng, RngOrdFracIdl -> Any#: The intersection of the ideal \(I\) with the compatible ring \(R\). If \(R = {\mathbb{Q}}\) an error will occur since ideals of \({\mathbb{Q}}\) cannot be created. If such information is required use Minimum instead. An ideal of \(R\) is returned.

a mod I: RngOrdElt, RngOrdIdl -> RngOrdElt#: A representative of the element \(a\) of an order \(O\) in the quotient \(O/I\).

InverseMod(E, M): RngOrdElt, RngIntElt -> RngOrdElt#
InverseMod(E, M): RngOrdElt, RngOrdIdl -> RngOrdElt#
Modinv(E, M): RngOrdElt, RngOrdIdl -> RngOrdElt#
Modinv(E, M): RngOrdElt, RngIntElt -> RngOrdElt#: An element \(y\) such that \(y*E = 1\) mod \(M\) where \(M\) is an integral ideal or an integer and \(E\) is an element of an order.

ColonIdeal(I, J): RngOrdFracIdl, RngOrdFracIdl -> RngOrdFracIdl#

IdealQuotient(I, J): RngOrdFracIdl, RngOrdFracIdl -> RngOrdFracIdl#

In Magma, the colon ideal (or ideal quotient) \([I:J]\) for two fractional ideals \(I,J\) is defined as the fractional ideal \((I:J)=\{ x\in {\rm Frac}(O) : x J \subseteq I\}\), where \(O\) is the order to which \(I\) and \(J\) belong. In this definition we have \(x\in {\rm Frac}(O)\) rather than \(x\in O\), and so this differs from ColonIdeal for other structures, where the result would be an ideal rather than a fractional ideal.

For ideals of a maximal order (or in general for invertible ideals) the ColonIdeal is equivalent to \(I/J\) (see above), otherwise only \(J(I:J)\subset I\) holds. Below is an example of the latter.

Currently ColonIdeal and IdealQuotient do not exist for RngInt types, so there is a slight incompatibility for Z as a number field order (see §\({\mathbb{Z}}\) as a Number Field Order).

Example: colon (ex-9af5d2)#

> O := EquationOrder(Polynomial([4,0,1]));
> z := O.2; // z^2 = -4
> I := ideal<O|1>; // O as an ideal
> J := ideal<O|[2,z]>; // noninvertible ideal
> ColonIdeal(I,J)*J eq I;
false

Run in calculator

IntegralSplit(I): RngOrdFracIdl -> RngOrdIdl, RngElt#: Given an ideal \(I\), return an integral ideal \(J\) and a minimal positive integer \(d\) such that \(I = J/d\).

Different(I): RngOrdFracIdl -> RngOrdFracIdl#: The different of the (possibly fractional) ideal \(I\) of an order of an algebraic number field.

Codifferent(I): RngOrdFracIdl -> RngOrdFracIdl#: The codifferent of the ideal \(I\). This will be the inverse of the different of \(I\) if I is an ideal of a maximal order.

Roots of Ideals#

It is possible to ask for the \(k\)-th root of an ideal where \(k\) is a positive integer.

Root(I, k): RngOrdFracIdl, RngIntElt -> RngOrdFracIdl#: Find the \(k\)th root of the ideal \(I\) if it exists.

IsPower(I, k): RngOrdFracIdl, RngIntElt -> BoolElt, RngOrdFracIdl#: Return true if the ideal \(I\) is a \(k\)th power of an ideal and the ideal it is a power of otherwise false.

SquareRoot(I): RngOrdFracIdl -> RngOrdFracIdl#
Sqrt(I): RngOrdFracIdl -> RngOrdFracIdl#: Return the square root of the ideal \(I\) if \(I\) is square.

IsSquare(I): RngOrdFracIdl -> BoolElt, RngOrdFracIdl#: Return true if the ideal \(I\) is the square of an ideal and the ideal it is a square of otherwise false.

Factorization and Primes#

The factorization of an ideal into prime ideals and the divisors of an ideal can be determined.

Decomposition(O, p): RngOrd, RngIntElt -> [<RngOrdIdl, RngIntElt>]#

Decomposition(O, p): RngOrd, RngOrdIdl -> [ <RngOrdIdl, RngIntElt> ]#

Al: MonStgElt                    Default: 

verbose: IdealDecompose                    Default: Verbose : 5

Given an order \(O\) and a rational prime number \(p\) or a prime ideal \(p\) of the coefficient ring of \(O\), return a sequence of tuples consisting of prime ideals and exponents, according to the decomposition of \(p\) in \(O\). The parameter Al can be set to "Montes" when \(O\) is an extension of \({\mathbb{Z}}\) by a single monic integral polynomial and \(p\) is an integer, in which case the Montes algorithm [Stainsby, 2018] will be used to compute the decomposition.

DecompositionType(O, p): RngOrd, RngIntElt -> [<RngIntElt, RngIntElt>]#

DecompositionType(O, p): FldAlg, RngIntElt -> [<RngIntElt, RngIntElt>]#

DecompositionType(O, p): FldAlg, RngOrdIdl -> [<RngIntElt, RngIntElt>]#

DecompositionType(O, p): RngOrd, RngOrdIdl -> [ <RngIntElt, RngIntElt> ]#

verbose: IdealDecompose                    Default: Verbose : 5

Given an order \(O\) and a rational prime number \(p\) or a prime ideal \(p\) of the coefficient ring of \(O\), return the decomposition type, ie. a sequence of tuples consisting of the degree of the prime ideals and their ramification index, according to the decomposition of \(p\) in \(O\).

Factorization(I): RngOrdFracIdl -> [<RngOrdIdl, RngIntElt>]#

Factorisation(I): RngOrdFracIdl -> [<RngOrdIdl, RngIntElt>]#

Factorization(I): RngIntFracIdl -> [<RngInt, RngIntElt>]#

Factorisation(I): RngIntFracIdl -> [<RngInt, RngIntElt>]#

verbose: IdealDecompose                    Default: Verbose : 5

Returns the prime ideal factorization of an ideal \(I\) in a maximal order \(O\), as a sequence of 2-tuples (prime ideal and integer exponent).

Example: Non Maximal Fact (ex-4f7652)#

We provide an example of Factorization. An ideal in an order which is not maximal can only be decomposed into primary ideals. We illustrate how to compute some prime “factors” of an ideal of an order which is not maximal.

> R<x>:=PolynomialRing(Integers());
> f:=x^3+4*x+15;
> K<y>:=NumberField(f);
> E:=EquationOrder(K);
> O:=MaximalOrder(K);
> c:=4*y^2+6*y+4;
> I:=c*O;
> Factorisation(I);
[
    <Prime Ideal of E
    Two element generators:
        [2, 0, 0]
        [1, 1, 0], 1>,
    <Prime Ideal of E
    Two element generators:
        [2, 0, 0]
        [3, 1, 1], 1>,
    <Prime Ideal of E
    Two element generators:
        [3, 0, 0]
        [1, 0, 1], 1>,
    <Prime Ideal of E
    Two element generators:
        [151, 0, 0]
        [262, 1, 0], 1>
]
> J := c*E;
> Factorisation(J);
>>     Factorisation(J);
                    ^
Runtime error in 'Factorisation': Order associated with ideal argument 1 is not
known to be maximal
> E2 := Decomposition(E, 2);
> E2;
[
    <Prime Ideal of E
    Two element generators:
        [2, 0, 0]
        [1, 1, 0], 1>,
    <Prime Ideal of E
    Two element generators:
        [2, 0, 0]
        [3, 1, 1], 1>
]
> Valuation(J, E2[1][1]);
1
> Valuation(J, E2[2][1]);
1
> J := ColonIdeal(J, E2[1][1]); J;
Ideal of E
Basis:
[  1   3 403]
[  0   6 702]
[  0   0 906]
> J := ColonIdeal(E!!J, E2[2][1]); J;
Ideal of E
Basis:
[  1   0  52]
[  0   3 351]
[  0   0 453]
> E3 := Decomposition(E, 3);
> E3;
[
    <Prime Ideal of E
    Two element generators:
        [3, 0, 0]
        [0, 1, 0], 1>,
    <Prime Ideal of E
    Two element generators:
        [3, 0, 0]
        [1, 0, 1], 1>
]
> Valuation(J, E3[1][1]);
0
> Valuation(J, E3[2][1]);
1
> J := ColonIdeal(E!!J, E3[2][1]); J;
Ideal of E
Basis:
[  1   0  52]
[  0   1 117]
[  0   0 151]
> E151 := Decomposition(E, 151);
> E151;
[
    <Prime Ideal of E
    Two element generators:
        [151, 0, 0]
        [18, 1, 0], 1>,
    <Prime Ideal of E
    Two element generators:
        [151, 0, 0]
        [22, 1, 0], 1>,
    <Prime Ideal of E
    Two element generators:
        [151, 0, 0]
        [262, 1, 0], 1>
]
> Valuation(J, E151[1][1]);
0
> Valuation(J, E151[2][1]);
0
> Valuation(J, E151[3][1]);
1
> J := ColonIdeal(E!!J, E151[3][1]); J;
Ideal of E
Basis:
[1 0 0]
[0 1 0]
[0 0 1]

Run in calculator

It will not always be the case that an ideal of a non maximal order will be able to be factorized into powers of prime ideals, although in this example it is the case.

Divisors(I): RngOrdIdl -> [<RngOrdIdl, RngIntElt>]#: Return the ideals which divide the ideal \(I\) which must be of a maximal order.

Support(I): RngOrdFracIdl -> {RngOrdIdl}#
Support(I): RngIntFracIdl -> {RngInt}#: For a non-zero ideal \(I\) of some maximal order, return the set of prime ideals \(p\) dividing \(I\).

Support(L): [RngOrdFracIdl] -> {RngOrdIdl}#

Support(L): [FldAlgElt] -> {RngOrdIdl}#

GaloisStable: BoolElt                    Default: false
CoprimeOnly : BoolElt                    Default: false
UseBernstein: BoolElt                    Default: false

For a sequence \(L\) of ideals in some maximal order (or of number field elements representing principal ideals), return the set of prime ideals dividing at least one of the ideals. If CoprimeOnly is given, the set returned will not in general be containing prime ideals, but will satisfy the following:

Every ideal in \(L\) can be uniquely decomposed into a power product of ideals in the set returned
The set is minimal and closed under gcd, ie. for two elements in the set, their gcd will be one.

If the number field is normal and if GaloisStable is given, then the set returned will be closed under the action of the galois group. Depending on the (unknown) factorisation pattern of the ideals, taking the Galois action into account will in general refine the coprime factorisation.

In general, this function will first construct a coprime basis, and the factorise the result of this step.

If UseBernstein is given, then Dan Berstein’s asymptoically fast algorithm ([Bernstein, 2005], which runs in time essentially linear in \(\#L\)) is used.

CoprimeBasis(L): [RngOrdFracIdl] -> RngOrdIdl#

GaloisStable: BoolElt                    Default: false
UseBernstein: BoolElt                    Default: false

Given a sequence \(L\) of ideals in some maximal order, a coprime basis \(C\) for \(L\) is constructed. That means

- every element in \(L\) has a unique representation as a power product with elements in \(C\)

- \(C\) is closed under gcd, the ideals in \(C\) are pairwise coprime.

If the field is normal and if GaloisStable is given, the input sequence is supplemented by the action of the automorphism group, thus potentially refining the coprime basis.

If UseBernstein is given then instead of the naive algorithm with quadratic complexity in \(\#L\), an asymptotically fast, almost linear algorithm by Dan Berstein is used, [Bernstein, 2005].

CoprimeBasisInsert(~L, I): [RngOrdIdl], RngOrdFracIdl#

GaloisStable: BoolElt                    Default: false
UseBernstein: BoolElt                    Default: false

Given a coprime basis in the sequence \(L\), enlarge it by the ideal \(I\), ie. enlarge \(L\) in such a way that \(L\) stays a coprime basis but allows the decomposition of \(I\) as well. If the ideals are in a normal field and if GaloisStable is given, then in addition of \(I\) all its Galois conjugates are inserted as well. Furthermore, a fractional ideal is always decomposed into the numerator and denominator ideal, ach of which is inserted independently.

If UseBernstein is given then instead of the naive algorithm with quadratic complexity in \(\#L\), an asymptotically fast, almost linear algorithm by Dan Berstein is used, [Bernstein, 2005].

PowerProduct(B, E): [RngOrdFracIdl], [RngIntElt] -> RngOrdFracIdl#: Given sequences \(B\) of ideals of some maximal order and \(E\) of integers, compute the ideal \(\prod B[i]^{E[i]}\).

Other Ideal Operations#

Various other functions can be applied to ideals. In addition to those listed, the completion of an order at a prime ideal can also be taken (see Completion and Chapter \(p\)-Adic Rings and Their Extensions).

ChineseRemainderTheorem(I1, I2, e1, e2): RngOrdIdl, RngOrdIdl, RngOrdElt, RngOrdElt -> RngOrdElt#
ChineseRemainderTheorem(X, M): SeqEnum[RngOrdElt], SeqEnum[RngOrdIdl] -> RngOrdElt#
CRT(I1, I2, e1, e2): RngOrdIdl, RngOrdIdl, RngOrdElt, RngOrdElt -> RngOrdElt#
CRT(X, M): SeqEnum[RngOrdElt], SeqEnum[RngOrdIdl] -> RngOrdElt#: Returns an element \(e\) of the order \(O\) such that \((e_1 - e)\) is in the ideal \(I_1\) of \(O\) and \((e_2 - e)\) is in the ideal \(I_2\). If a sequence of elements \(X\) and a sequence of ideals \(M\) is given then the element \(e\) will be such that \((X[i] - e)\) is in \(M[i]\) for all \(i\).

CRT(I1, L1, e1, L2): RngOrdIdl, [RngIntElt], RngOrdElt, [RngIntElt] -> RngOrdElt#

ChineseRemainderTheorem(I1, L1, e1, L2): RngOrdIdl, [RngIntElt], RngOrdElt, [RngIntElt] -> RngOrdElt#

Returns an element \(e\) of the order \(O\) such that \((e_1 - e)\) is in the ideal \(I_1\) of \(O\) and the signs of the conjugates listed in \(L1\) are the same as in \(L2\).

\(L1\), a sorted sequence of integers \(0<l_i<= r1\), is meant to be formal product of infinite places. The signs of the \(l_i\)’th conjugate of \(e\) will be the same as the sign of \(L2[i]\).

WeakApproximation(I, V): [RngOrdIdl], [RngIntElt] -> FldOrdElt#
WeakApproximation(I, V): [RngInt], [RngIntElt] -> FldRatElt#: Compute an element in the field of fractions of the order of the ideals in \(I\) which has valuation \(V[i]\) at the prime ideal \(I[i]\).

Idempotents(I, J): RngOrdIdl, RngOrdIdl -> BoolElt, RngOrdElt, RngOrdElt#: For coprime integral ideals \(I\) and \(J\) return true and elements \(i\in I\) and \(j\in J\) such that \(i+j=1\).

CoprimeRepresentative(I, J): RngOrdIdl, RngOrdIdl -> FldOrdElt#
MakeCoprime(I, J): RngOrdIdl, RngOrdIdl -> FldOrdElt#: Given two integral ideals \(I\) and \(J\) in the same maximal order, find an element \(q\) in the field of fractions of this order such that \(qI\) is coprime to \(J\).

IdealsUpTo(B, O): RngIntElt, RngOrd -> [RngOrdIdl]#

IdealsUpTo(B, K): RngIntElt, FldNum -> [RngOrdIdl]#

CoprimeTo: RngOrdIdl                    Default: 

Given a number field \(K\) or a maximal order \(O\), returns a sequence containing the ideals of \(O\) or the maximal order of \(K\) with norm at most \(B\) which are coprime to any ideals given in CoprimeTo.

ClassRepresentative(I): RngOrdFracIdl -> RngOrdFracIdl#: Let \(I\) be an ideal in the absolute maximal order \(O\) of the number field \(K\). Further, assume that the class group of \(O\) has been computed. The class group calculation will have chosen a set of ideal class representatives. This function returns the representative ideal for the ideal class to which \(I\) belongs.

SUnitGroup(I): RngOrdFracIdl -> GrpAb, Map#

SUnitGroup(S): [ RngOrdIdl ] -> GrpAb, Map#

Raw    : BoolElt                       Default: false
verbose: ClassGroup                    Default: Verbose : 5

This function computes the group of \(S\)-units for the set \(S\) of prime ideals, where \(S\) may be input as a sequence or as an ideal (in which case \(S\) is the set of primes appearing in its factorization). An element \(mu\) is an \(S\)-unit iff \(v_p(mu) = 0\) for all primes \(p\) not in \(S\).

The function returns (by default) an abstract abelian group \(A\), and a map from \(A\) to the field.

When Raw is true, the \(S\)-units are represented as power-products rather than as ordinary elements. A fixed sequence \(L\) of field elements is given, and each unit is specified as a vector of integers \(e\) (of the same length as \(L\)) such that the unit equals \(\prod L_i^{e_i}\). Three values are returned in the Raw case: an abstract abelian group \(A\), a map from \(A\) to exponent vectors, and the sequence \(L\).

Example: S Units (ex-062dcc)#

First we compute the \(3\)-units of \({\mathbb{Q}}(\sqrt 10)\).

> K := QuadraticField(10);
> M := MaximalOrder(K);
> U, mU := SUnitGroup(3*M);
> U;
Abelian Group isomorphic to Z/2 + Z + Z + Z
Defined on 4 generators
Relations:
    2*U.1 = 0
> mU;
Mapping from: GrpAb: U to Field of Fractions of M
> u := mU(U.3); u;
7/1*M.1 - 2/1*M.2
> Decomposition(u);
[
  <Prime Ideal of M
    Two element generators:
      3
      $.2 + 1, 2>
]

Run in calculator

So \(u\) is indeed a \(3\) unit, as the factorization contains only prime ideals over \(3\). Next we do the same computation but using the Raw option:

> U, mU, base := SUnitGroup(3*M:Raw);
> mU;
Mapping from: GrpAb: U to Full RSpace of degree 14 over Integer Ring
> mU(U.3);
( 0  2  1  0  0  0  0  0  0  0 -2)
> PowerProduct(base, $1);
7/1*M.1 - 2/1*M.2
> base[2]^2 * base[3]^1 * base[11]^-2;
7/1*M.1 - 2/1*M.2

Run in calculator

This representation is of particular importance for large degree fields or fields with large units. To illustrate this, consider the following field from the pari-mailing list:

> K := NumberField(Polynomial([ 13824, -3894, -1723, 5, 1291, 1 ]));
> L := LLL(MaximalOrder(K));
> C, mC := ClassGroup(L : Proof:="GRH");
> U, mU, base := SUnitGroup(1*L:Raw);
> logs := Matrix([Logs(x) : x in Eltseq(base)]);
> mU(U.3)*logs;
(2815256.998090806477937318458440358713392011019115562
    -636746.05251910981832558348350489744160309616673457
    -770882.44652629342064307574571528191509290934280166)

Run in calculator

As the logarithm of the absolute value of the real embeddings is of the order \(10^6\), we expect that a basis representation will have coefficients requiring roughly \(10^6\) digits. While it is feasible to compute them (using PowerProduct), this will take a long time.

SUnitAction(SU, Act, S): Map, Map, SeqEnum[RngOrdIdl] -> Map#

Base: SeqEnum[RngOrdElt]                    Default: []

Given a description of the \(S\)-unit group as computed by SUnitGroup and a (multiplicative) map of the underlying number field, this function computes the induced map on the abstract abelian group.

The argument \(S\) should be a sequence of ideals as in SUnitGroup. The argument \(SU\) should either be the map returned by SUnitGroup(S) as second return value - in which case Base is trivial (and not specified) or the second return value of SUnitGroup(S:Raw) in which case Base should equal the third computed value.

The argument \(Act\) must be any (multiplicative) function of the underlying number field or any order, that acts on the \(S\)-unit group.

On return, a endomorphism of the domain of \(SU\) is obtained.

SUnitAction(SU, Act, S): Map, SeqEnum[Map], SeqEnum[RngOrdIdl] -> [Map]#

Base: SeqEnum[RngOrdElt]                    Default: []

Given a description of the \(S\)-unit group as computed by SUnitGroup and a sequence of (multiplicative) maps of the underlying number field, this function computes the induced maps on the abstract abelian group.

The argument \(S\) should be a sequence of ideals as in SUnitGroup. The argument \(SU\) should either be the map returned by SUnitGroup(S) as second return value - in which case Base is trivial (and not specified) or the second return value of SUnitGroup(S:Raw) in which case Base should equal the third computed value.

The argument \(Act\) must be a sequence of (multiplicative) functions of the underlying number field or any order, that acts on the \(S\)-unit group.

On return, a sequence of endomorphisms of the domain of \(SU\) is obtained.

SUnitDiscLog(SU, x, S): Map, FldAlgElt, SeqEnum[RngOrdIdl] -> GrpAbElt#

SUnitDiscLog(SU, L, S): Map, SeqEnum[FldAlgElt], SeqEnum[RngOrdIdl] -> GrpAbElt#

Base: SeqEnum[RngOrdElt]                    Default: []

Given a description of the \(S\)-unit group as computed by SUnitGroup and a (multiplicative) map of the underlying number field, this function computes the induced map on the abstract abelian group.

The argument \(S\) should be a sequence of ideals as in SUnitGroup. The argument \(SU\) should either be the map returned by SUnitGroup(S) as second return value - in which case Base is trivial (and not specified) or the second return value of SUnitGroup(S:Raw) in which case Base should equal the third computed value.

This function solves the discrete logarithm problem for the \(S\)-unit group and the algebraic number \(x\). That is, an element in the abstract abelian group representing the \(S\)-unit group is computed which corresponds to \(x\). If a list of algebraic numbers \(L\) is passed into this function, the discrete logarithm is computed for each of them.

Example: S-Units, advanced (ex-95d956)#

> M := MaximalOrder(Polynomial([ 25, 0, -30, 0, 1 ]));
> S := [ x[1] : x in Factorisation(30*M)];
> U, mU := SUnitGroup(S);
> L := Automorphisms(NumberField(M));
> s2 := SUnitAction(mU, L[2], S);
> s2;
Mapping from: GrpAb: U to GrpAb: U
> L[2](mU(U.2)) eq mU(s2(U.2));

Run in calculator

Now the same in Raw representation:

> R, mR, Base := SUnitGroup(S:Raw);
> S2 := SUnitAction(mR, L[2], S:Base := Base);
> [S2(R.i) : i in [1..Ngens(R)]];
[
    R.1,
    R.1 - R.2,
    R.3,
    R.1 + R.3 - R.4,
    R.1 + R.5,
    R.1 + R.3 + R.7,
    R.1 - R.3 + R.6,
    R.8
]

Run in calculator

If we combine SUnitAction with SUnitDiscLog we can solve norm equations:

> N := map<FieldOfFractions(M) -> M | x:-> L[1](x) * L[2](x)>;
> NR := SUnitAction(mR, N, S:Base := Base);

Run in calculator

Now NR is the norm function with respect to the field fixed by L[2].

> SUnitDiscLog(mR, FieldOfFractions(M)!5, S:Base := Base);
2*R.5
> $1 in Image(NR);
true
> $2 @@ NR;
R.2 + R.5
> PowerProduct(Base, mR($1));
-3/1*M.1 - 2/1*M.2 + M.4
> N($1);
[5, 0, 0, 0]

Run in calculator

Quotient Rings#

Quotients of orders defined over maximal orders and their integral ideals can be formed resulting in an object with type RngOrdRes. Elements of such orders can be created and elementary arithmetic and predicates may be applied to them.

Operations on Quotient Rings#

The creation of quotient rings and the functions which may be applied to them are described.

quo< O | I >: RngOrd, RngOrdIdl -> RngOrdRes#
quo< O | M >: RngOrd, ModDed -> RngOrdRes#
quo< O | M >: RngOrd, AlgMatElt -> RngOrdRes#
quo< O | S >: RngOrd, RngElt, ..., RngElt -> RngOrdRes#: Creates the quotient ring \(Q=O/I\) of the order \(O\). The right hand side of the constructor may contain an ideal or anything that the ideal constructor can create an ideal from.

quo< O | m >: RngOrd, RngIntElt -> RngOrdRes#: Construct the quotient ring \(Q=O/m\) where \(m\) is a prime power.

UnitGroup(OQ): RngOrdRes -> GrpAb, Map#
MultiplicativeGroup(OQ): RngOrdRes -> GrpAb, Map#: Returns an abelian group and the map from the group into \(OQ\), a quotient of an absolute maximal order.

Modulus(OQ): RngOrdRes -> RngOrdIdl#: Return the denominator of the quotient ring \(OQ\), i.e. \(I\) where \(OQ = O/I\).

Example: quotient (ex-d59aa1)#

Creation of quotient rings is shown. The orders are the same as for the ideal examples, however an integral ideal is now required.

> I := Denominator(I)*I;
> I;
Principal Ideal of O
Generator:
    38/1*M.4*O.3
> Basis(I);
[
    38/1*M.4*O.3,
    19/1*M.4*O.1,
    38/1*M.4*O.2
]
> Q := quo<Order(I) | I>;
> Q;
Quotient Ring of Principal Ideal of O
Generator:
    [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 38, 0]]
> Modulus(Q);
Principal Ideal of O
Generator:
    [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 38, 0]]

Run in calculator

Elements of Quotients#

Functions for elements of the quotient rings are predominantly arithmetic. Elements of quotient rings can be looped through using for x in OQ do ... end for.

OQ ! a: RngOrdRes, Elt -> RngOrdResElt#: Coerce the element \(a\) into the quotient \(OQ\) where \(a\) is anything that can be coerced into the order \(OQ\) is a quotient of.

Random(OQ): RngOrdRes -> RngOrdResElt#: A random element of the quotient ring \(OQ\).

a mod I: RngOrdElt, RngOrdIdl -> RngOrdElt#: A canonical representative of the element \(a\) (belonging to an order \(O\)) in the quotient ring \(O/I\).

a * b: RngOrdResElt, RngOrdResElt -> RngOrdResElt#
a + b: RngOrdResElt, RngOrdResElt -> RngOrdResElt#
a - b: RngOrdResElt, RngOrdResElt -> RngOrdResElt#
a / b: RngOrdResElt, RngOrdResElt -> RngOrdResElt#
- a: RngOrdResElt -> RngOrdResElt#
a ^ n: RngOrdResElt, RngIntElt -> RngOrdResElt#
a eq b: RngOrdResElt, RngOrdResElt -> BoolElt#
a ne b: RngOrdResElt, RngOrdResElt -> BoolElt#
a div b: RngOrdResElt, RngOrdResElt -> RngOrdResElt#
a mod b: RngOrdResElt, RngOrdResElt -> RngOrdResElt#
Quotrem(a, b): RngOrdResElt, RngOrdResElt -> RngOrdResElt, RngOrdResElt#
Lcm(a, b): RngOrdResElt, RngOrdResElt -> RngOrdResElt#
Gcd(a, b): RngOrdResElt, RngOrdResElt -> RngOrdResElt#
XGcd(a, b): RngOrdResElt, RngOrdResElt -> RngOrdResElt, RngOrdResElt, RngOrdResElt#
IsZero(a): RngOrdResElt -> BoolElt#: Returns true if and only if the quotient ring element \(a\) is the zero element of the quotient ring \(OQ\).

IsOne(a): RngOrdResElt -> BoolElt#: Returns true if and only if the quotient ring element \(a\) is the one element of the quotient ring \(OQ\).

IsMinusOne(a): RngOrdResElt -> BoolElt#: Returns true if and only if the quotient ring element \(a\) is the minus one element of the quotient ring \(OQ\).

IsUnit(a): RngOrdResElt -> BoolElt#: Returns true if and only if the quotient ring element \(a\) has an inverse in the quotient ring \(OQ\).

Eltseq(a): RngOrdResElt -> []#
ElementToSequence(a): RngOrdResElt -> []#: The coefficients of the quotient ring element \(a\) in the field of fractions of the coefficient ring of the order of the quotient ring containing \(a\).

EuclideanNorm(a): RngOrdResElt -> RngIntElt#: Return the Euclidean norm of the element \(a\) of a quotient ring \(OQ\), where the Euclidean norm is the function that makes \(OQ\) into a Euclidean ring.

Annihilator(a): RngOrdResElt -> RngOrdResElt#: The annihilator of the element \(a\) in the quotient ring \(OQ\).

Reconstruction#

Given an element \(e\) in some order \(O\), known modulo some ideal \(I\), a common problem in several algorithms is to recover \(e\), ie. a unique minimal element \(f\in O\) such that \(e-f\in I\) and \(f\) is as “small” as possible. An equally common variation would be to ask for some field element \(f/d\) with \(d\) an integer, such that \(f-de \in I\) and \(f\) as well as \(d\) are small.

In the case of \(O\) being the ring of integers and \(I\) a power of a prime (ideal), this is usually done by moving to the symmetric residue system in the first case and by rational reconstruction in the second. Here, we use techniques based on the LLL algorithm as described in [Fieker and Friedrichs, n.d.].

Since the method is more complicated than in the case of the integer ring, one first has to create a “reconstruction environment” of type RngOrdRecoEnv, which is subsequently used to reconstruct any number of elements.

ReconstructionEnvironment(p, k): RngOrdIdl, RngIntElt -> RngOrdRecoEnv#
ReconstructionEnvironment(p, k): RngIntElt, RngIntElt -> RngOrdRecoEnv#: Given a (prime) ideal \(p\) and an exponent \(k\), initialize the reconstruction process for the ideal \(I=p^k\), that is, the object returned can be used to reconstruct elements from “approximations” modulo \(p^k\).

Reconstruct(x, R): RngOrdElt, RngOrdRecoEnv -> RngOrdElt#

Reconstruct(x, R): RngIntElt, RngOrdRecoEnv -> RngIntElt#

UseDenominator: BoolElt                    Default: false

Given an order element \(e\), thought to be an approximation modulo \(p^k\) where \(p\) and \(k\) are stored in the reconstruction environment \(R\), return the unique minimal \(f\) in the same order such that \(e-g\in p^k\). Is UseDenominator is true, then a field element is computed, otherwise a ring element will be found.

ChangePrecision(~R, k): RngOrdRecoEnv, RngIntElt#: Change the ideal \(I=p^l\) stored in \(R\) to \(p^k\).

Example: Order Reco (ex-c0c980)#

We illustrate the use of the reconstruction environment to find roots of some polynomial over a number field. We will first compute the roots over some completion, up to some precision, then “list” the elements back from the completion into the starting order and finally use reconstruction to get the roots.

> f := Polynomial([1,1,1,1,1]);
> M := MaximalOrder(f);
> P := Decomposition(M, 11)[1][1]; P;
Prime Ideal of M
Two element generators:
    [11, 0, 0, 0]
    [2, 1, 0, 0]
> C, mC := Completion(M, P:Precision :=  10);
> fC := Polynomial([c@ mC : c in Eltseq(f)]);
> rt := Roots(fC); rt;
> R := ReconstructionEnvironment(P, 10);
> [Reconstruct((x[1]) @@ mC, R) : x in rt];
[
    M.4,
    M.3,
    -M.1 - M.2 - M.3 - M.4,
    M.2
]
> [ Evaluate(f, x) : x in $1];
[
    0,
    0,
    0,
    0
 ]

Run in calculator