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.
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.
Create the ideal x * O for element x and order O. If the ideal is integral it will be returned with the integral type.
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).
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).
> 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
Some information describing an ideal can be retrieved.
The order O which the ideal I is of.
The denominator of the fractional ideal I. This is the smallest positive integer d such that d I is an integral ideal.
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.
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.
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.
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.
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.
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.
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.
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.
Return the ramification index of the prime ideal I as an extension of the prime integer which is its minimum.
If I is a prime ideal of O, this function returns the finite field F isomorphic to O/I and the map O -> F.
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.
Return the inertia index of the prime ideal I as an extension of the prime integer which is its minimum.
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.
> 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:
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.
> 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.
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.
> 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.
Returns true if and only if the fractional ideal I is integral.
Returns true if the ideal I is the zero ideal, false otherwise.
Returns true if the ideal I is the ideal generated by 1, false otherwise.
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.
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).
Returns true iff the ramification index of the prime ideal P equals the degree of its order over the base field.
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.
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.
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.
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.
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.
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.
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.
The product IJ of the (fractional) ideals I and J, generated by the products of elements in I and elements in J.
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.
The product of all ideals in the sequence or set L.
For integral 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 truly synonyms, as I/J will work for I, J of type RngOrdIdl 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.
The sum of the (fractional) ideals I and J, generated by the sums of elements in I and elements in J.
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.
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,
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.
Return the least common multiple of ideals I and J. They must both be of the same maximal order.
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.
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.
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.
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.
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.
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:
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.
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.
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).
> 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.
For a non-zero ideal I of some maximal order, return the set of prime ideals p dividing I.
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: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.
- -
- 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.
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 meansIf 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.
- - 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 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).
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.
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].
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.
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.
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.
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.
> 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.2This 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
106, we expect that a basis representation will have
coefficients requiring roughly 106 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.
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<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.
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.
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.
> 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.
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.
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.
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.
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.
> 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
]