# Ideals

(Integral) ideals in orders are always free $Z$-module of the same rank as the order, hence have a representation via a $Z$-basis. This can be made unique by normalising the corresponding matrix to be in reduced row echelon form (HNF).

For ideals in maximal orders $Z_K$, we also have a second presentation coming from the $Z_K$ module structure and the fact that $Z_K$ is a Dedekind ring: ideals can be generated by 2 elements, one of which can be any non-zero element in the ideal.

For efficiency, we will choose the 1st generator to be an integer.

Ideals here are of type AbsNumFieldOrderIdeal, which is, similar to the elements above, also indexed by the type of the field and their elements: AbsNumFieldOrderIdeal{AbsSimpleNumField,AbsSimpleNumFieldElem} for ideals in simple absolute fields.

Different to elements, the parentof an ideal is the set of all ideals in the ring, of type AbsNumFieldOrderIdealSet.

## Creation

idealMethod
ideal(O::AbsSimpleNumFieldOrder, a::ZZRingElem) -> AbsNumFieldOrderIdeal
ideal(O::AbsSimpleNumFieldOrder, a::Integer) -> AbsNumFieldOrderIdeal

Returns the ideal of $\mathcal O$ which is generated by $a$.

source
idealMethod
ideal(O::AbsSimpleNumFieldOrder, M::ZZMatrix; check::Bool = false, M_in_hnf::Bool = false) -> AbsNumFieldOrderIdeal

Creates the ideal of $\mathcal O$ with basis matrix $M$. If check is set, then it is checked whether $M$ defines an ideal (expensive). If M_in_hnf is set, then it is assumed that $M$ is already in lower left HNF.

source
idealMethod
ideal(O::AbsSimpleNumFieldOrder, x::AbsSimpleNumFieldOrderElem) -> AbsNumFieldOrderIdeal

Creates the principal ideal $(x)$ of $\mathcal O$.

source
idealMethod
ideal(O::AbsSimpleNumFieldOrder, x::ZZRingElem, y::AbsSimpleNumFieldOrderElem) -> AbsNumFieldOrderIdeal
ideal(O::AbsSimpleNumFieldOrder, x::Integer, y::AbsSimpleNumFieldOrderElem) -> AbsNumFieldOrderIdeal

Creates the ideal $(x, y)$ of $\mathcal O$.

source
idealMethod
ideal(O::AbsSimpleNumFieldOrder, x::ZZRingElem, y::AbsSimpleNumFieldOrderElem) -> AbsNumFieldOrderIdeal
ideal(O::AbsSimpleNumFieldOrder, x::Integer, y::AbsSimpleNumFieldOrderElem) -> AbsNumFieldOrderIdeal

Creates the ideal $(x, y)$ of $\mathcal O$.

source
idealMethod
ideal(O::AbsSimpleNumFieldOrder, a::ZZRingElem) -> AbsNumFieldOrderIdeal
ideal(O::AbsSimpleNumFieldOrder, a::Integer) -> AbsNumFieldOrderIdeal

Returns the ideal of $\mathcal O$ which is generated by $a$.

source
idealMethod
ideal(O::AbsSimpleNumFieldOrder, x::AbsSimpleNumFieldOrderElem) -> AbsNumFieldOrderIdeal

Creates the principal ideal $(x)$ of $\mathcal O$.

source
*Method
*(O::AbsSimpleNumFieldOrder, x::AbsSimpleNumFieldOrderElem) -> AbsNumFieldOrderIdeal
*(x::AbsNumFieldOrderElem, O::AbsNumFieldOrder) -> AbsNumFieldOrderIdeal

Returns the principal ideal $(x)$ of $\mathcal O$.

source
factorMethod
factor(A::AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}) -> Dict{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, Int}

Computes the prime ideal factorization $A$ as a dictionary, the keys being the prime ideal divisors: If lp = factor_dict(A), then keys(lp) are the prime ideal divisors of $A$ and lp[P] is the $P$-adic valuation of $A$ for all $P$ in keys(lp).

source
factorMethod
factor(I::AbsNumFieldOrderIdealSet{AbsSimpleNumField, AbsSimpleNumFieldElem}, a::AbsSimpleNumFieldElem) -> Dict{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, ZZRingElem}

Factors the principal ideal generated by $a$.

source
coprime_baseMethod
coprime_base(A::Vector{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}) -> Vector{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}
coprime_base(A::Vector{AbsSimpleNumFieldOrderElem}) -> Vector{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}

A coprime base for the (principal) ideals in $A$, i.e. the returned array generated multiplicatively the same ideals as the input and are pairwise coprime.

source

## Arithmetic

All the usual operations are supported:

• ==, +, *
• divexact, divides
• lcm, gcd
• in
intersectMethod
intersect(x::AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, y::AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}) -> AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}

Returns $x \cap y$.

source
colonMethod
colon(a::AbsNumFieldOrderIdeal, b::AbsNumFieldOrderIdeal) -> AbsSimpleNumFieldOrderFractionalIdeal

The ideal $(a:b) = \{x \in K | xb \subseteq a\} = \hom(b, a)$ where $K$ is the number field.

source
inMethod
in(x::NumFieldOrderElem, y::NumFieldOrderIdeal)
in(x::NumFieldElem, y::NumFieldOrderIdeal)
in(x::ZZRingElem, y::NumFieldOrderIdeal)

Returns whether $x$ is contained in $y$.

source
is_powerMethod
is_power(A::AbsNumFieldOrderIdeal, n::Int) -> Bool, AbsNumFieldOrderIdeal
is_power(A::AbsSimpleNumFieldOrderFractionalIdeal, n::Int) -> Bool, AbsSimpleNumFieldOrderFractionalIdeal

Computes, if possible, an ideal $B$ s.th. $B^n==A$ holds. In this case, true and $B$ are returned.

source
is_powerMethod
is_power(I::AbsNumFieldOrderIdeal) -> Int, AbsNumFieldOrderIdeal
is_power(a::AbsSimpleNumFieldOrderFractionalIdeal) -> Int, AbsSimpleNumFieldOrderFractionalIdeal

Writes $a = r^e$ with $e$ maximal. Note: $1 = 1^0$.

source
is_invertibleMethod
is_invertible(A::AbsNumFieldOrderIdeal) -> Bool, AbsSimpleNumFieldOrderFractionalIdeal

Returns true and an inverse of $A$ or false and an ideal $B$ such that $A*B \subsetneq order(A)$, if $A$ is not invertible.

source
isoneMethod
isone(A::AbsNumFieldOrderIdeal) -> Bool
is_unit(A::AbsNumFieldOrderIdeal) -> Bool

Tests if $A$ is the trivial ideal generated by $1$.

source

## Class Group

The group of invertable ideals in any order forms a group and the principal ideals a subgroup. The finite quotient is called class group for maximal orders and Picard group or ring class group in general.

class_groupMethod
class_group(O::AbsSimpleNumFieldOrder; bound = -1,
redo = false,
GRH = true)   -> FinGenAbGroup, Map

Returns a group $A$ and a map $f$ from $A$ to the set of ideals of $O$. The inverse of the map is the projection onto the group of ideals modulo the group of principal ideals.

By default, the correctness is guarenteed only assuming the Generalized Riemann Hypothesis (GRH).

Keyword arguments:

• redo: Trigger a recomputation, thus avoiding the cache.
• bound: When specified, this is used for the bound for the factor base.
• GRH: If false, the correctness of the result does not depend on GRH.
source
narrow_class_groupMethod
narrow_class_group(O::AbsSimpleNumFieldOrder) -> FinGenAbGroup, Map

Computes the narrow (or strict) class group of $O$, ie. the group of invertable ideals modulo principal ideals generated by elements that are positive at all real places.

source
picard_groupMethod
picard_group(O::AbsSimpleNumFieldOrder) -> FinGenAbGroup, MapClassGrp

Returns the Picard group of $O$ and a map from the group in the set of (invertible) ideals of $O$.

source
julia> k, a = wildanger_field(3, 13);julia> zk = maximal_order(k);julia> c, mc = class_group(zk)(Z/9, ClassGroup map of
Set of ideals of Maximal order of Number field of degree 3 over QQ
with basis AbsSimpleNumFieldElem[1, _$, 1//2*_$^2 + 1//2])julia> lp = prime_ideals_up_to(zk, 20);julia> [ mc \ I for I = lp]10-element Vector{FinGenAbGroupElem}:
[7]
[1]
[1]
[8]
[3]
[5]
[4]
[7]
[0]
[5]julia> mc(c[1])<2, 1//2*_$^2 + 2*_$ + 1//2>
Norm: 2
Minimum: 2
two normal wrt: 2julia> order(c[1])9julia> mc(c[1])^Int(order(c[1]))<32, 10991426517025591//2*_$^2 - 5454445711922803*_$ + 11899932301596121//2>
Norm: 512
Minimum: 32
two normal wrt: 2julia> mc \ ansAbelian group element [0]

The class group, or more precisely the information used to compute it also allows for principal ideal testing and related tasks. In general, due to the size of the objects, the fac_elem versions are more efficient.

is_principalMethod
is_principal(A::AbsSimpleNumFieldOrderIdeal) -> Bool
is_principal(A::AbsSimpleNumFieldOrderFractionalIdeal) -> Bool

Tests if $A$ is principal.

source
is_principal_with_dataMethod
is_principal_with_data(A::AbsSimpleNumFieldOrderIdeal) -> Bool, AbsSimpleNumFieldOrderElem
is_principal_with_data(A::AbsSimpleNumFieldOrderFractionalIdeal) -> Bool, AbsSimpleNumFieldElem

Tests if $A$ is principal and returns $(\mathtt{true}, \alpha)$ if $A = \langle \alpha\rangle$ or $(\mathtt{false}, 1)$ otherwise.

source
is_principal_fac_elemMethod
is_principal_fac_elem(A::AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}) -> Bool, FacElem{AbsSimpleNumFieldElem, number_field}

Tests if $A$ is principal and returns $(\mathtt{true}, \alpha)$ if $A = \langle \alpha\rangle$ or $(\mathtt{false}, 1)$ otherwise. The generator will be in factored form.

source
power_classMethod
power_class(A::AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, e::ZZRingElem) -> AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}

Computes a (small) ideal in the same class as $A^e$.

source
power_product_classMethod
power_product_class(A::Vector{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}, e::Vector{ZZRingElem}) -> AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}

Computes a (small) ideal in the same class as $\prod A_i^{e_i}$.

source
power_reduceMethod
power_reduce(A::AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, e::ZZRingElem) -> AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, FacElem{AbsSimpleNumFieldElem}

Computes $B$ and $\alpha$ in factored form, such that $\alpha B = A^e$ $B$ has small norm.

source
class_group_ideal_relationMethod
class_group_ideal_relation(I::AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, c::ClassGrpCtx) -> AbsSimpleNumFieldElem, SRow{ZZRingElem}

Finds a number field element $\alpha$ such that $\alpha I$ factors over the factor base in $c$.

source
factor_base_bound_grhMethod
factor_base_bound_grh(O::AbsSimpleNumFieldOrder) -> Int

Returns an integer $B$, such that under GRH the ideal class group of $\mathcal O$ is generated by the prime ideals of norm bounded by $B$.

source
factor_base_bound_bachMethod
factor_base_bound_bach(O::AbsSimpleNumFieldOrder) -> Int

Use the theorem of Bach to find $B$ such that under GRH the ideal class group of $\mathcal O$ is generated by the prime ideals of norm bounded by $B$.

source
prime_ideals_up_toFunction
prime_ideals_up_to(O::AbsSimpleNumFieldOrder,
B::Int;
degree_limit::Int = 0, index_divisors::Bool = true) -> Vector{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}

Computes the prime ideals $\mathcal O$ with norm up to $B$.

If degree_limit is a nonzero integer $k$, then prime ideals $\mathfrak p$ with $\deg(\mathfrak p) > k$ will be discarded. If 'index_divisors' is set to false, only primes not dividing the index of the order will be computed.

source
prime_ideals_up_to(O::AbsSimpleNumFieldOrder,
B::Int;
complete::Bool = false,
degree_limit::Int = 0,
F::Function,
bad::ZZRingElem)

Computes the prime ideals $\mathcal O$ with norm up to $B$.

If degree_limit is a nonzero integer $k$, then prime ideals $\mathfrak p$ with $\deg(\mathfrak p) > k$ will be discarded.

The function $F$ must be a function on prime numbers not dividing bad such that $F(p) = \deg(\mathfrak p)$ for all prime ideals $\mathfrak p$ lying above $p$.

source
julia> I = mc(c[1])<2, 1//2*_$^2 + 2*_$ + 1//2>
Norm: 2
Minimum: 2
two normal wrt: 2julia> is_principal(I)falsejulia> I = I^Int(order(c[1]))<32, 10991426517025591//2*_$^2 - 5454445711922803*_$ + 11899932301596121//2>
Norm: 512
Minimum: 32
two normal wrt: 2julia> is_principal(I)truejulia> is_principal_fac_elem(I)(true, 5^5*(_$^2 + _$ + 2)^-5*(_$+ 5)^5*(_$^2 + 1)^5*3^-5*1^-1*(_$- 3)^-1*(_$ + 1)^-5)

The computation of $S$-units is also tied to the class group:

torsion_unitsMethod
torsion_units(O::AbsSimpleNumFieldOrder) -> Vector{AbsSimpleNumFieldOrderElem}

Given an order $O$, compute the torsion units of $O$.

source
torsion_unit_groupMethod
torsion_unit_group(O::AbsSimpleNumFieldOrder) -> GrpAb, Map

Given an order $\mathcal O$, returns the torsion units as an abelian group $G$ together with a map $G \to \mathcal O^\times$.

source
torsion_units_generatorMethod
torsion_units_generator(O::AbsSimpleNumFieldOrder) -> AbsSimpleNumFieldOrderElem

Given an order $O$, compute a generator of the torsion units of $O$.

source
torsion_units_gen_orderMethod
torsion_units_gen_order(O::AbsSimpleNumFieldOrder) -> AbsSimpleNumFieldOrderElem

Given an order $O$, compute a generator of the torsion units of $O$ as well as its order.

source
unit_groupMethod
unit_group(O::AbsSimpleNumFieldOrder) -> FinGenAbGroup, Map

Returns a group $U$ and an isomorphism map $f \colon U \to \mathcal O^\times$. A set of fundamental units of $\mathcal O$ can be obtained via [ f(U[1+i]) for i in 1:unit_group_rank(O) ]. f(U[1]) will give a generator for the torsion subgroup.

source
unit_group_fac_elemMethod
unit_group_fac_elem(O::AbsSimpleNumFieldOrder) -> FinGenAbGroup, Map

Returns a group $U$ and an isomorphism map $f \colon U \to \mathcal O^\times$. A set of fundamental units of $\mathcal O$ can be obtained via [ f(U[1+i]) for i in 1:unit_group_rank(O) ]. f(U[1]) will give a generator for the torsion subgroup. All elements will be returned in factored form.

source
sunit_groupMethod
sunit_group(I::Vector{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}) -> GrpAb, Map

For an array $I$ of (coprime prime) ideals, find the $S$-unit group defined by $I$, ie. the group of non-zero field elements which are only divisible by ideals in $I$.

source
sunit_group_fac_elemMethod
sunit_group_fac_elem(I::Vector{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}) -> GrpAb, Map

For an array $I$ of (coprime prime) ideals, find the $S$-unit group defined by $I$, ie. the group of non-zero field elements which are only divisible by ideals in $I$. The map will return elements in factored form.

source
sunit_mod_units_group_fac_elemMethod
sunit_mod_units_group_fac_elem(I::Vector{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}) -> GrpAb, Map

For an array $I$ of (coprime prime) ideals, find the $S$-unit group defined by $I$, ie. the group of non-zero field elements which are only divisible by ideals in $I$ modulo the units of the field. The map will return elements in factored form.

source
julia> u, mu = unit_group(zk)(Z/2 x Z, UnitGroup map of Maximal order of Number field of degree 3 over QQ
with basis AbsSimpleNumFieldElem[1, _$, 1//2*_$^2 + 1//2]
)julia> mu(u[2])_$^2 - _$ + 1julia> u, mu = unit_group_fac_elem(zk)(Z/2 x Z, UnitGroup map of Factored elements over Number field of degree 3 over QQ
)julia> mu(u[2])(19*_$^2 - 318*_$ + 338)^1*(-27*_$^2 + 317*_$ - 429)^1*(_$^2 + 1)^1*(_$ + 5)^1*(-22*_$^2 + 251*_$ - 39)^-1*3^-1*(_$+ 17)^-1*(111//2*_$^2 - 723*_$+ 533//2)^-1julia> evaluate(ans)_$^2 - _$+ 1julia> lp = factor(6*zk)Dict{AbsSimpleNumFieldOrderIdeal, Int64} with 4 entries: <3, _$ + 5>                  => 1
<3, _$^2 + 1> => 1 <2, 1//2*_$^2 + 2*_$+ 1//2> => 2 <2, 5//2*_$^2 + 7//2>        => 1julia> s, ms = Hecke.sunit_group(collect(keys(lp)))(Z/2 x Z^(5), SUnits  map of Number field of degree 3 over QQ for AbsSimpleNumFieldOrderIdeal[<3, _$+ 5> Norm: 3 Minimum: 3 basis_matrix [3 0 0; 2 1 0; 2 0 1] two normal wrt: 3, <3, _$^2 + 1>
Norm: 9
Minimum: 3
basis_matrix
[3 0 0; 0 3 0; 0 0 1]
two normal wrt: 3, <2, 1//2*_$^2 + 2*_$ + 1//2>
Norm: 2
Minimum: 2
basis_matrix
[2 0 0; 1 1 0; 0 0 1]

source