|
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 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 Q are of type RngIntFracIdl, while
integral ideals in Z have the type RngInt.
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.
It is also possible to construct fractional ideals in Q.
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 : 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 | 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).
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, 0, 1, 0]
> FieldOfFractions(O)!!I;
Principal Ideal of O
Generator:
O.3
> O!!$1 eq I;
true
FractionalIdeal(x): RngIntElt -> RngIntFracIdl
FractionalIdeal(x): [ FldRatElt ] -> RngIntFracIdl
FractionalIdeal(x): [ RngIntElt ] -> RngIntFracIdl
The fractional ideal generated by x.
Make I into a fractional ideal.
Some information describing an ideal can be retrieved.
Order(I) : RngIntFracIdl -> RngInt
The order O which the ideal I is of.
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) : RngOrdFracIdl -> FldOrdElt
UniformizingElement(P) : RngOrdIdl -> RngOrdElt
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.
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) : 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.
Given an ideal I of an order in some number field,
the function returns the least positive integer
contained in the ideal.
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) : 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) : 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) : 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.
RamificationDegree(I, p) : RngOrdIdl, RngIntElt -> RngIntElt
For a prime ideal I of an order O such that p ∈I
returns the maximal exponent e such that Ie divides the principal
ideal pO. If p is not given it is taken to be the minimal integer
of I.
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 ∩o is an
prime ideal p in o.
The ramification index e = e(I|p)
is the maximal exponent e such that Ie divides pO.
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(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 -> F.
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 ∩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.
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) : RngIntFracIdl, RngInt -> RngIntElt
Given an ideal I and a prime ideal p in an order O, returns
the valuation vp(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 [Sta18].
The content of the ideal I, i.e. the maximal ideal of the base ring dividing I.
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 ]
The basis of an ideal can be computed as well as related matrices.
For relative extensions, a different method is available:
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.
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 Z for an
integral ideal
of an order over Z only or the
field of fractions of the coefficient ring of O.
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
Z for an integral ideal of an order over Z or the
field of fractions of the coefficient ring of O.
The coefficient ideals of the ideal I in a relative extension. These are
the ideals {Ai} of the coefficient ring of the order of I such that for every element
e ∈I, e = ∑i ai * bi where {bi}
is the basis returned for I and each ai ∈Ai.
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
For an ideal I in some relative extension, return a Dedekind module
over the coefficient ring with the "same" basis.
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) : 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.
Given a (fractional) ideal I of O, return two elements of (the
field of fractions of) O that generate I as an ideal.
Given an integral ideal I of O (a maximal order over 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.
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
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).
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 Q).
The ideal of ZK that has the name s.
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) : RngIntFracIdl -> BoolElt
Returns true if and only if the fractional ideal I is integral.
Returns true if the ideal I is the zero ideal, false otherwise.
IsOne(I) : RngOrdFracIdl -> BoolElt
IsOne(I) : RngIntFracIdl -> BoolElt
Returns true if the ideal I is the ideal generated by 1, false otherwise.
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.
SetVerbose("ClassGroup", n): Maximum: 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.
Returns true iff the ramification index of the prime ideal
P is greater than 1.
IsRamified(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 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) : RngInt -> BoolElt
Returns true iff the ideal I has no repeated factors.
Returns true iff the ramification index of the prime ideal P equals
the degree of its order over the base field.
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).
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.
Returns true if all primes dividing the discriminant of the maximal order
O are totally ramified over the coefficient ring of O.
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) : 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).
Returns true iff the prime ideal P is not wildly ramified.
IsTamelyRamified(P, O) : RngIntElt, RngOrd -> BoolElt
Returns true iff the prime ideal or integer P is not wildly ramified in
the order O.
Returns true iff the ramification index of the prime ideal P is 1.
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).
Returns true iff the inertia degree of the prime ideal
P is the field degree.
IsInert(P, O) : RngIntElt, 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.
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) : RngIntElt, 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.
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) : RngIntElt, 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.
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 : 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 : 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
The product of all ideals in the sequence or set L.
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.
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 (Z) as a number field order in
Section Ideals of Z and 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.
Given an ideal I and an element x construct the fractional ideal I / x.
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 : 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 : RngIntFracIdl, RngIntFracIdl -> BoolElt
I eq J : RngIntFracIdl, RngInt -> BoolElt
Tests if the ideals I and J are equal.
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, 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
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
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.
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.
The intersection of the (fractional) ideals I and J. For ideal in
the maximal order this is the same as the lcm.
&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 lcm.
R meet I : Rng, RngOrdFracIdl -> Any
The intersection of the ideal I with the compatible ring R. If R = Q an
error will occur since ideals of Q cannot be created. If such information
is required use Minimum instead. An ideal of R is returned.
A representative of the element a of an order O in the quotient O/I.
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.
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∈(Frac)(O) : x J ⊆I},
where O is the order to which I and J belong.
In this definition we have x∈(Frac)(O) rather than x∈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)⊂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 ParaZ as a Number Field Order).
> 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
Given an ideal I, return an integral ideal J and a minimal positive integer d
such that I = J/d.
The different of the (possibly fractional) ideal I of an order of
an algebraic number field.
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.
It is possible to ask for the k-th root of an ideal where k is
a positive integer.
Find the kth root of the ideal I if it exists.
Return true if the ideal I is a kth power of an ideal and the ideal it
is a power of otherwise false.
Sqrt(I) : RngOrdFracIdl -> RngOrdFracIdl
Return the square root of the ideal I if I is square.
Return true if the ideal I is the square of an ideal and the ideal it is a square
of otherwise false.
The factorization of an ideal into prime ideals and the divisors
of an ideal can be determined.
Al: MonStgElt Default:
Decomposition(O, p) : RngOrd, RngOrdIdl -> [ <RngOrdIdl, RngIntElt> ]
SetVerbose("IdealDecompose", n): Maximum: 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 Z by a single monic integral polynomial
and p is an integer, in which case the Montes algorithm [Sta18] will be used to compute the decomposition.
DecompositionType(O, p) : FldAlg, RngIntElt -> [<RngIntElt, RngIntElt>]
DecompositionType(O, p) : FldAlg, RngOrdIdl -> [<RngIntElt, RngIntElt>]
DecompositionType(O, p) : RngOrd, RngOrdIdl -> [ <RngIntElt, RngIntElt> ]
SetVerbose("IdealDecompose", n): Maximum: 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.
Factorisation(I) : RngOrdFracIdl -> [<RngOrdIdl, RngIntElt>]
Factorization(I) : RngIntFracIdl -> [<RngInt, RngIntElt>]
Factorisation(I) : RngIntFracIdl -> [<RngInt, RngIntElt>]
SetVerbose("IdealDecompose", n): Maximum: 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).
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]
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.
Return the ideals which divide the ideal I which must be of a maximal order.
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) : [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 ([Ber05],
which runs in time essentially linear in #L) is used.
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, [Ber05].
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, [Ber05].
Given sequences B of ideals of some maximal order and E of integers,
compute the ideal ∏B[i]E[i].
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(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 (e1 - e) is in the ideal
I1 of O and
(e2 - e) is in the ideal I2.
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 (e1 - e) is in the ideal
I1 of O and
the signs of the conjugates listed in L1 are the same as in L2.
L1, a sorted sequence of integers 0<li<= r1, is meant to be formal
product of infinite places. The signs of the li'th conjugate
of e will be the same as the sign of L2[i].
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].
For coprime integral ideals I and J return true and elements
i∈I and j∈J such that i + j=1.
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, 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.
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(S) : [ RngOrdIdl ] -> GrpAb, Map
Raw: BoolElt Default: false
SetVerbose("ClassGroup", n): Maximum: 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 vp(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 ∏Liei.
Three values are returned in the Raw case: an abstract abelian group A,
a map from A to exponent vectors, and the sequence L.
First we compute the 3-units of Q(√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>
]
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
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)
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.
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.
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, 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.
> 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));
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
]
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);
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]
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.
The creation of quotient rings and the functions which may be applied to them
are described.
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.
Construct the quotient ring Q=O/m where m is a prime power.
MultiplicativeGroup(OQ) : RngOrdRes -> GrpAb, Map
Returns an abelian group and the map from the group into OQ,
a quotient of an absolute maximal order.
Return the denominator of the quotient ring OQ, i.e. I where OQ = O/I.
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]]
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.
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
Coerce the element a into the quotient OQ where a is anything
that can be coerced into the order OQ is a quotient of.
A random element of the quotient ring OQ.
A canonical representative of the element
a (belonging to an order O) in the quotient ring
O/I.
Returns true if and only if the quotient ring element
a is the zero element of the quotient ring OQ.
Returns true if and only if the quotient ring element
a is the one element of the quotient ring OQ.
Returns true if and only if the quotient ring element
a is the minus one element of the quotient ring OQ.
Returns true if and only if the quotient ring element
a has an inverse in the quotient ring OQ.
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.
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.
The annihilator of the element a in the quotient ring OQ.
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∈O such that
e - f∈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 ∈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 [FF00].
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) : RngIntElt, RngIntElt -> RngOrdRecoEnv
Given a (prime) ideal p and an exponent k, initialize the
reconstruction process for the ideal I=pk, that is, the
object returned can be used to reconstruct elements from
"approximations" modulo pk.
Reconstruct(x, R) : RngIntElt, RngOrdRecoEnv -> RngIntElt
UseDenominator: BoolElt Default: false
Given an order element e, thought to be an approximation modulo
pk where p and k are stored in the reconstruction environment R,
return the unique minimal f in the same order such that e - g∈pk.
Is UseDenominator is true, then a field element is computed, otherwise
a ring element will be found.
Change the ideal I=pl stored in R to pk.
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
]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|