Ideals

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 NfAbsOrdIdl, which is, similar to the elements above, also indexed by the type of the field and their elements: NfAbsOrdIdl{AnticNumberField,nf_elem} for ideals in simple absolute fields.

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

Creation

Hecke.ideal — Method.
ideal(O::NfOrd, a::fmpz) -> NfAbsOrdIdl
ideal(O::NfOrd, a::Integer) -> NfAbsOrdIdl

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

Hecke.ideal — Method.
ideal(O::NfOrd, x::fmpz_mat, check::Bool = false, x_in_hnf::Bool = false) -> NfAbsOrdIdl

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

Hecke.ideal — Method.
ideal(O::NfOrd, x::NfOrdElem) -> NfAbsOrdIdl

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

Hecke.ideal — Method.
ideal(O::NfOrd, x::fmpz, y::NfOrdElem) -> NfAbsOrdIdl
ideal(O::NfOrd, x::Integer, y::NfOrdElem) -> NfAbsOrdIdl

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

Hecke.ideal — Method.
ideal(O::NfOrd, I::NfAbsOrdIdl) -> NfOrdFracIdl

The fractional ideal of $O$ generated by a Z-basis of $I$.

Base.:* — Method.
*(O::NfOrd, x::NfOrdElem) -> NfAbsOrdIdl
*(x::NfOrdElem, O::NfOrd) -> NfAbsOrdIdl

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

Hecke.prime_decomposition — Method.
prime_decomposition(O::NfAbsOrd,
                    p::Integer,
                    degree_limit::Int = 0,
                    lower_limit::Int = 0) -> Array{Tuple{NfOrdIdl, Int}, 1}

Returns an array of tuples $(\mathfrak p_i,e_i)$ such that $p \mathcal O$ is the product of the $\mathfrak p_i^{e_i}$ and $\mathfrak p_i \neq \mathfrak p_j$ for $i \neq j$.

If degree_limit is a nonzero integer $k > 0$, then only those prime ideals $\mathfrak p$ with $\deg(\mathfrak p) \leq k$ will be returned. Similarly if \lower_limit is a nonzero integer $l > 0$, then only those prime ideals $\mathfrak p$ with $l \leq \deg(\mathfrak p)$ will be returned. Note that in this case it may happen that $p\mathcal O$ is not the product of the $\mathfrak p_i^{e_i}$.

Hecke.prime_decomposition — Method.
prime_decomposition(O::NfAbsOrd,
                    p::Integer,
                    degree_limit::Int = 0,
                    lower_limit::Int = 0) -> Array{Tuple{NfOrdIdl, Int}, 1}

Returns an array of tuples $(\mathfrak p_i,e_i)$ such that $p \mathcal O$ is the product of the $\mathfrak p_i^{e_i}$ and $\mathfrak p_i \neq \mathfrak p_j$ for $i \neq j$.

If degree_limit is a nonzero integer $k > 0$, then only those prime ideals $\mathfrak p$ with $\deg(\mathfrak p) \leq k$ will be returned. Similarly if \lower_limit is a nonzero integer $l > 0$, then only those prime ideals $\mathfrak p$ with $l \leq \deg(\mathfrak p)$ will be returned. Note that in this case it may happen that $p\mathcal O$ is not the product of the $\mathfrak p_i^{e_i}$.

Hecke.factor — Method.
factor(A::NfOrdIdl) -> Dict{NfOrdIdl, 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).

Hecke.factor — Method.

factor(a::nf_elem, I::NfOrdIdlSet) -> Dict{NfOrdIdl, fmpz}

Factors the principal ideal generated by $a$.

Arithmetic

Base.:== — Method.
==(x::NfAbsOrdIdl, y::NfAbsOrdIdl)

Returns whether $x$ and $y$ are equal.

Base.:+ — Method.
+(x::NfOrdIdl, y::NfOrdIdl)

Returns $x + y$.

Base.:* — Method.
*(x::NfOrdIdl, y::NfOrdIdl)

Returns $x \cdot y$.

AbstractAlgebra.Generic.divexact — Method.
divexact(A::NfOrdIdl, B::NfOrdIdl) -> NfOrdIdl

Returns $AB^{-1}$ assuming that $AB^{-1}$ is again an integral ideal.

AbstractAlgebra.Generic.divides — Method.
divides(A::NfOrdIdl, B::NfOrdIdl)

Checks if B divides A

Base.lcm — Method.
intersect(x::NfOrdIdl, y::NfOrdIdl) -> NfOrdIdl
lcm(x::NfOrdIdl, y::NfOrdIdl) -> NfOrdIdl

Returns $x \cap y$.

Base.gcd — Method.

gcd(A::NfOrdIdl, B::NfOrdIdl) -> NfOrdIdl

The gcd or sum (A+B).

Base.gcd — Method.

gcd(A::NfOrdIdl, p::fmpz) -> NfOrdIdl

The gcd or sum (A+ pO).

Base.intersect — Method.
intersect(x::NfOrdIdl, y::NfOrdIdl) -> NfOrdIdl
lcm(x::NfOrdIdl, y::NfOrdIdl) -> NfOrdIdl

Returns $x \cap y$.

Hecke.colon — Method.
colon(a::NfAbsOrdIdl, b::NfAbsOrdIdl) -> NfOrdFracIdl

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

Base.in — Method.
in(x::NfOrdElem, y::NfAbsOrdIdl)
in(x::nf_elem, y::NfAbsOrdIdl)
in(x::fmpz, y::NfAbsOrdIdl)

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

Hecke.ispower — Method.
ispower(A::NfAbsOrdIdl, n::Int) -> Bool, NfAbsOrdIdl
ispower(A::NfOrdFracIdl, n::Int) -> Bool, NfOrdFracIdl

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

Hecke.ispower — Method.
ispower(I::NfAbsOrdIdl) -> Int, NfAbsOrdIdl
ispower(a::NfOrdFracIdl) -> Int, NfOrdFracIdl

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

Hecke.isinvertible — Method.
isinvertible(A::NfAbsOrdIdl) -> Bool, NfOrdFracIdl

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.

Base.isone — Method.
isone(A::NfAbsOrdIdl) -> Bool
isunit(A::NfAbsOrdIdl) -> Bool

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

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.

Hecke.class_group — Method.
class_group(O::NfOrd; bound = -1, method = 3, redo = false, large = 1000) -> GrpAbFinGen, 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. \texttt{redo} allows to trigger a re-computation, thus avoiding the cache. \texttt{bound}, when given, is the bound for the factor base.

Hecke.class_group — Method.
class_group(K::AnticNumberField) -> GrpAbFinGen, Map

Shortcut for {{{classgroup(maximalorder(K))}}}: returns the class group as an abelian group and a map from this group to the set of ideals of the maximal order.

Hecke.picard_group — Method.
  picard_group(O::NfOrd) -> GrpAbFinGen, MapClassGrp

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

Hecke.ring_class_group — Method.
ring_class_group(O::NfAbsOrd)

The ring class group (Picard group) of $O$. 


julia> k, a = wildanger_field(3, 13);

julia> zk = maximal_order(k);

julia> c, mc = class_group(zk)
(GrpAb: Z/9, ClassGroup map of Set of ideals of Maximal order of Number field over Rational Field with defining polynomial x^3-13*x^2+13*x-13
with basis nf_elem[1, _$, 1//2*_$^2 + 1//2]

)

julia> lp = prime_ideals_up_to(zk, 20);

julia> [ mc \ I for I = lp]
10-element Array{GrpAbFinGenElem,1}:
 [4]
 [1]
 [4]
 [5]
 [3]
 [2]
 [7]
 [1]
 [0]
 [2]

julia> mc(c[1])
<2, 3//2*_$^2 + 1*_$ + 3//2>
Norm: 2
Minimum: 2
basis_mat
[2 0 0]
[1 1 0]
[1 0 1]
two normal wrt: 2

julia> order(c[1])
9

julia> mc(c[1])^Int(order(c[1]))
<512, 26780950338796882953//2*_$^2 - 13289925516978788669*_$ + 28994552755335316893//2>
Norm: 512
two normal wrt: 256

julia> mc \ ans
[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 objetcs, the fac_elem versions are more effcient.

Hecke.isprincipal — Method.
isprincipal(A::NfOrdIdl) -> Bool, NfOrdElem
isprincipal(A::NfOrdFracIdl) -> Bool, NfOrdElem

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

Hecke.isprincipal_fac_elem — Method.
isprincipal_fac_elem(A::NfOrdIdl) -> Bool, FacElem{nf_elem, NumberField}

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

Hecke.power_class — Method.
power_class(A::NfOrdIdl, e::fmpz) -> NfOrdIdl

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

Hecke.power_product_class — Method.
power_product_class(A::Array{NfOrdIdl, 1}, e::Array{fmpz, 1}) -> NfOrdIdl

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

Hecke.power_reduce2 — Method.
power_reduce2(A::NfOrdIdl, e::fmpz) -> NfOrdIdl, FacElem{nf_elem}

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

Hecke.class_group_ideal_relation — Method.
class_group_ideal_relation(I::NfOrdIdl, c::ClassGrpCtx) -> nf_elem, SRow{fmpz}

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

julia> I = mc(c[1])
<2, 3//2*_$^2 + 1*_$ + 3//2>
Norm: 2
Minimum: 2
basis_mat
[2 0 0]
[1 1 0]
[1 0 1]
two normal wrt: 2

julia> Hecke.isprincipal(I)
(false, 1)

julia> I = I^Int(order(c[1]))
<512, 26780950338796882953//2*_$^2 - 13289925516978788669*_$ + 28994552755335316893//2>
Norm: 512
two normal wrt: 256

julia> Hecke.isprincipal(I)
(true, 1//2*_$^2 - 3*_$ + 9//2)

julia> Hecke.isprincipal_fac_elem(I)
(true, Factored element with data
Dict(_$+38=>-25,_$+1=>-35,5=>37,1//2*_$^2 - 1*_$ + 1//2=>40,_$^2 - 2*_$ - 2=>-27,7=>27,_$+2=>16,_$-4=>-2,11=>-8,-17//648*_$^2 + 35//108*_$ - 47//648=>20,-1=>-20,_$^2 + 1*_$ + 2=>-37,_$+5=>97,107=>25,_$-16=>-25,_$-35=>-25,1=>221))

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

Hecke.unit_group — Method.
unit_group(O::NfOrd) -> GrpAbFinGen, 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_rank(O) ]. f(U[1]) will give a generator for the torsion subgroup.

Hecke.unit_group_fac_elem — Method.
unit_group_fac_elem(O::NfOrd) -> GrpAbFinGen, 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_rank(O) ]. f(U[1]) will give a generator for the torsion subgroup. All elements will be returned in factored form.

Hecke.sunit_group — Method.
sunit_group(I::Array{NfOrdIdl, 1}) -> 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$.

Hecke.sunit_group_fac_elem — Method.
sunit_group_fac_elem(I::Array{NfOrdIdl, 1}) -> 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.

Hecke.sunit_mod_units_group_fac_elem — Method.
sunit_mod_units_group_fac_elem(I::Array{NfOrdIdl, 1}) -> 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.

julia> u, mu = unit_group(zk)
(GrpAb: Z/2 x Z, UnitGroup map of Maximal order of Number field over Rational Field with defining polynomial x^3-13*x^2+13*x-13
with basis nf_elem[1, _$, 1//2*_$^2 + 1//2]
)

julia> mu(u[2])
-_$+12

julia> u, mu = unit_group_fac_elem(zk)
(GrpAb: Z/2 x Z, Unit group map of Factored elements over Number field over Rational Field with defining polynomial x^3-13*x^2+13*x-13 in factored presentation
)

julia> mu(u[2])
Factored element with data
Dict(1//2*_$^2 - 1*_$ + 1//2=>-2,-17//648*_$^2 + 35//108*_$ - 47//648=>-1,1=>-11,-1=>1)

julia> evaluate(ans)
-_$+12

julia> lp = factor(6*zk)
Dict{NfAbsOrdIdl{AnticNumberField,nf_elem},Int64} with 4 entries:
  <3, _$^2 + 1>                => 1
  <2, 3//2*_$^2 + 1*_$ + 3//2> => 1
  <2, 1//2*_$^2 + 1//2>        => 2
  <3, _$-1>                    => 1

julia> s, ms = Hecke.sunit_group(collect(keys(lp)))
(GrpAb: Z/2 x Z^5, SUnits  map of Number field over Rational Field with defining polynomial x^3-13*x^2+13*x-13 for NfAbsOrdIdl{AnticNumberField,nf_elem}[<3, _$^2 + 1>, <2, 3//2*_$^2 + 1*_$ + 3//2>, <2, 1//2*_$^2 + 1//2>, <3, _$-1>]
)

julia> ms(s[4])
1//2*_$^2 - 6*_$ - 1//2

julia> norm(ans)
-18

julia> factor(numerator(ans))
-1 * 2 * 3^2

Miscaellenous

AbstractAlgebra.Generic.order — Method.
order(I::NfAbsOrdIdl) -> NfOrd

Returns the order of $I$.

Hecke.nf — Method.
nf(x::NfAbsOrdIdl) -> AnticNumberField

Returns the number field, of which $x$ is an integral ideal.

Hecke.basis — Method.
basis(O::NfOrd) -> Array{NfOrdElem, 1}

Returns the $\mathbf Z$-basis of $\mathcal O$.

basis(A::NfAbsOrdIdl) -> Array{NfOrdElem, 1}

Returns the basis of A.

Hecke.basis_mat — Method.
basis_mat(O::NfOrd) -> FakeFmpqMat

Returns the basis matrix of $\mathcal O$ with respect to the power basis of the ambient number field.

basis_mat(A::NfAbsOrdIdl) -> fmpz_mat

Returns the basis matrix of $A$.

  basis_mat(O::NfRelOrd{T, S}) -> Generic.Mat{T}

Returns the basis matrix of $\mathcal O$ with respect to the power basis of the ambient number field.

  basis_mat(a::NfRelOrdIdl{T, S}) -> Generic.Mat{T}
  basis_mat(a::NfRelOrdFracIdl{T, S}) -> Generic.Mat{T}

Returns the basis matrix of $a$.

Hecke.basis_mat_inv — Method.
basis_mat_inv(O::NfOrd) -> FakeFmpqMat

Returns the inverse of the basis matrix of $\mathcal O$.

basis_mat_inv(A::NfAbsOrdIdl) -> fmpz_mat

Returns the inverse basis matrix of $A$.

  basis_mat_inv(O::NfRelOrd{T, S}) -> Generic.Mat{T}

Returns the inverse of the basis matrix of $\mathcal O$.

  basis_mat_inv(a::NfRelOrdIdl{T, S}) -> Generic.Mat{T}
  basis_mat_inv(a::NfRelOrdFracIdl{T, S}) -> Generic.Mat{T}

Returns the inverse of the basis matrix of $a$.

Hecke.assure_has_basis_mat_inv — Method.
basis_mat_inv(A::NfAbsOrdIdl) -> FakeFmpqMat

Returns the inverse of the basis matrix of $A$.

Hecke.has_basis — Method.
has_basis(A::NfAbsOrdIdl) -> Bool

Returns whether A has a basis already computed.

Hecke.has_basis_mat — Method.
has_basis_mat(A::NfAbsOrdIdl) -> Bool

Returns whether $A$ knows its basis matrix.

Hecke.has_2_elem — Method.
has_2_elem(A::NfAbsOrdIdl) -> Bool

Returns whether $A$ is generated by two elements.

Hecke.has_2_elem_normal — Method.
has_2_elem_normal(A::NfAbsOrdIdl) -> Bool

Returns whether $A$ has normal two element generators.

Hecke.has_weakly_normal — Method.
has_weakly_normal(A::NfAbsOrdIdl) -> Bool

Returns whether $A$ has weakly normal two element generators.

Hecke.has_princ_gen_special — Method.
has_basis_princ_gen_special(A::NfAbsOrdIdl) -> Bool

Returns whether $A$ knows if it is generated by a rational integer.

Hecke.principal_gen — Method.
principal_gen(A::NfOrdIdl) -> NfOrdElem

For a principal ideal $A$, find a generator.

Hecke.principal_gen_fac_elem — Method.
principal_gen_fac_elem(A::NfOrdIdl) -> FacElem{nf_elem, NumberField}

For a principal ideal $A$, find a generator in factored form.

Base.minimum — Method.
minimum(A::NfAbsOrdIdl) -> fmpz

Returns the smallest nonnegative element in $A \cap \mathbf Z$.

  minimum(A::NfRelOrdIdl) -> NfOrdIdl
  minimum(A::NfRelOrdIdl) -> NfRelOrdIdl

Returns the ideal $A \cap O$ where $O$ is the maximal order of the coefficient ideals of $A$.

Hecke.has_minimum — Method.
has_minimum(A::NfAbsOrdIdl) -> Bool

Returns whether $A$ knows its mininum.

LinearAlgebra.norm — Method.
norm(A::NfAbsOrdIdl) -> fmpz

Returns the norm of $A$, that is, the cardinality of $\mathcal O/A$, where $\mathcal O$ is the order of $A$.

norm(a::NfRelOrdIdl) -> NfOrdIdl

Returns the norm of $a$.

norm(a::NfRelOrdFracIdl{T, S}) -> S

Returns the norm of $a$

Hecke.has_norm — Method.
has_norm(A::NfAbsOrdIdl) -> Bool

Returns whether $A$ knows its norm.

Hecke.idempotents — Method.
idempotents(x::NfOrdIdl, y::NfOrdIdl) -> NfOrdElem, NfOrdElem

Returns a tuple (e, f) consisting of elements e in x, f in y such that 1 = e + f.

If the ideals are not coprime, an error is raised.

Nemo.isprime — Method.
isprime(A::NfOrdIdl) -> Bool

Returns whether $A$ is a prime ideal.

Hecke.isprime_known — Method.
isprime_known(A::NfOrdIdl) -> Bool

Returns whether $A$ knows if it is prime.

Hecke.splitting_type — Method.
splitting_type(P::NfOrdIdl) -> Int, Int

The ramification index and inertia degree of the prime ideal $P$. First value is the ramificatio index, the second the degree of $P$.

Hecke.isramified — Method.
isramified(O::NfOrd, p::Int) -> Bool

Returns whether the integer $p$ is ramified in $\mathcal O$. It is assumed that $p$ is prime.

Hecke.ramification_index — Method.
ramification_index(P::NfOrdIdl) -> Int

The ramification index of the prime-ideal $P$.

AbstractAlgebra.Generic.degree — Method.
degree(P::NfOrdIdl) -> Int

The inertia degree of the prime-ideal $P$.

AbstractAlgebra.Generic.valuation — Method.
valuation(a::nf_elem, p::NfOrdIdl) -> fmpz
valuation(a::NfOrdElem, p::NfOrdIdl) -> fmpz
valuation(a::fmpz, p::NfOrdIdl) -> fmpz

Computes the $\mathfrak p$-adic valuation of $a$, that is, the largest $i$ such that $a$ is contained in $\mathfrak p^i$.

AbstractAlgebra.Generic.valuation — Method.
valuation(a::nf_elem, p::NfOrdIdl) -> fmpz
valuation(a::NfOrdElem, p::NfOrdIdl) -> fmpz
valuation(a::fmpz, p::NfOrdIdl) -> fmpz

Computes the $\mathfrak p$-adic valuation of $a$, that is, the largest $i$ such that $a$ is contained in $\mathfrak p^i$.

AbstractAlgebra.Generic.valuation — Method.
valuation(A::NfOrdIdl, p::NfOrdIdl) -> fmpz

Computes the $\mathfrak p$-adic valuation of $A$, that is, the largest $i$ such that $A$ is contained in $\mathfrak p^i$.

AbstractAlgebra.Generic.valuation — Method.
valuation(a::Integer, p::NfOrdIdl) -> fmpz

Computes the $\mathfrak p$-adic valuation of $a$, that is, the largest $i$ such that $a$ is contained in $\mathfrak p^i$.

AbstractAlgebra.Generic.valuation — Method.
valuation(a::nf_elem, p::NfOrdIdl) -> fmpz
valuation(a::NfOrdElem, p::NfOrdIdl) -> fmpz
valuation(a::fmpz, p::NfOrdIdl) -> fmpz

Computes the $\mathfrak p$-adic valuation of $a$, that is, the largest $i$ such that $a$ is contained in $\mathfrak p^i$.

AbstractAlgebra.Generic.valuation — Method.
valuation(A::NfOrdFracIdl, p::NfOrdIdl)

The valuation of $A$ at $p$.

Quotient Rings

quo(::NfOrd, ::NfOrdIdl)
ResidueRing(::NfOrd, ::NfOrdIdl)
ResidueField(::NfOrd, ::NfOrdIdl, ::Bool)
mod(::NfOrdElem, ::NfAbsOrdIdl)
crt(::NfOrdElem, ::NfOrdIdl, ::NfOrdElem, ::NfOrdIdl)