Factored Elements
In many applications in number theory related to the multiplicative structure of number fields, interesting elements, e.g. units, are extremely large when written wrt. to a fxied basis for the field: for the fundamental unit in
Mathematically, one can think of factored elements to formally live in the ring
Since
In Hecke, this is caputured more generally by the type FacElem
, parametrized by the type of the elements in the base and the type of their parent.
Important special cases are
FacElem{ZZRingElem, ZZRing}
, factored integersFacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}
, factored algerbaic numbersFacElem{AbsNumFieldOrderIdeal, AbsNumFieldOrderIdealSet}
, factored ideals
It should be noted that an object of type `
Construction
In general one can define factored elements by giving 2 arrays, the base and the exponent, or a dictionary containing the pairs:
FacElem{B, S}
Type for factored elements, that is elements of the form prod a_i^k_i for elements a_i
of type B
in a ring of type S
.
FacElem{B}(R, base::Vector{B}, exp::Vector{ZZRingElem}) -> FacElem{B}
Returns the element
FacElem{B}(base::Vector{B}, exp::Vector{ZZRingElem}) -> FacElem{B}
Returns the element
FacElem{B}(R, d::Dict{B, ZZRingElem}) -> FacElem{B}
FacElem{B}(R, d::Dict{B, Integer}) -> FacElem{B}
Returns the element
FacElem{B}(d::Dict{B, ZZRingElem}) -> FacElem{B}
FacElem{B}(d::Dict{B, Integer}) -> FacElem{B}
Returns the element
ideal(O::AbsSimpleNumFieldOrder, a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField)
The factored fractional ideal
Conversion
The process of computing the value defined by a factored element is available as evaluate
. Depending on the types involved this can be very efficient.
evaluate{T}(x::FacElem{T}) -> T
Expands or evaluates the factored element, i.e. actually computes the value. Does "square-and-multiply" on the exponent vectors.
evaluate(x::FacElem{QQFieldElem}) -> QQFieldElem
evaluate(x::FacElem{ZZRingElem}) -> ZZRingElem
Expands or evaluates the factored element, i.e. actually computes the the element. Works by first obtaining a simplified version of the power product into coprime base elements.
evaluate{T}(x::FacElem{T}) -> T
Expands or evaluates the factored element, i.e. actually computes the value. Does "square-and-multiply" on the exponent vectors.
evaluate_naive{T}(x::FacElem{T}) -> T
Expands or evaluates the factored element, i.e. actually computes the value. Uses the obvious naive algorithm. Faster for input in finite rings.
Special functions
In the case where the parent of the base allows for efficient gcd computation, power products can be made unique:
simplify(x::FacElem{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, AbsNumFieldOrderIdealSet{AbsSimpleNumField, AbsSimpleNumFieldElem}}) -> FacElem
simplify(x::FacElem{AbsSimpleNumFieldOrderFractionalIdeal, AbsNumFieldOrderFractionalIdealSet{AbsSimpleNumField, AbsSimpleNumFieldElem}}) -> FacElem
Uses coprime_base
to obtain a simplified version of
simplify(x::FacElem{QQFieldElem}) -> FacElem{QQFieldElem}
simplify(x::FacElem{ZZRingElem}) -> FacElem{ZZRingElem}
Simplfies the factored element, i.e. arranges for the base to be coprime.
The simplified version can then be used further:
isone(x::FacElem{QQFieldElem}) -> Bool
isone(x::FacElem{ZZRingElem}) -> Bool
Tests if
factor_coprime(x::FacElem{ZZRingElem}) -> Fac{ZZRingElem}
Computed a partial factorisation of
factor_coprime(x::FacElem{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, AbsNumFieldOrderIdealSet{AbsSimpleNumField, AbsSimpleNumFieldElem}}) -> Dict{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, Int}
Computed a partial factorisation of
factor_coprime(Q::FacElem{AbsSimpleNumFieldOrderFractionalIdeal, AbsNumFieldOrderFractionalIdealSet{AbsSimpleNumField, AbsSimpleNumFieldElem}}) -> Dict{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, Int}
A coprime factorisation of
factor_coprime(I::AbsNumFieldOrderIdealSet{AbsSimpleNumField, AbsSimpleNumFieldElem}, a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}) -> Dict{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, ZZRingElem}
Factors the rincipal ideal generated by
factor(Q::FacElem{AbsSimpleNumFieldOrderFractionalIdeal, AbsNumFieldOrderFractionalIdealSet{AbsSimpleNumField, AbsSimpleNumFieldElem}}) -> Dict{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, Int}
The factorisation of
factor(I::AbsNumFieldOrderIdealSet{AbsSimpleNumField, AbsSimpleNumFieldElem}, a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}) -> Dict{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, ZZRingElem}
Factors the principal ideal generated by
For factorised algebraic numbers a unique simplification is not possible, however, this allows still do obtain partial results:
compact_presentation(a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}, n::Int = 2; decom, arb_prec = 100, short_prec = 1000) -> FacElem
Computes a presentation
valuation(a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}, P::AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}) -> ZZRingElem
The valuation of
valuation(A::FacElem{AbsSimpleNumFieldOrderFractionalIdeal, AbsNumFieldOrderFractionalIdealSet{AbsSimpleNumField, AbsSimpleNumFieldElem}}, p::AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem})
valuation(A::FacElem{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, AbsNumFieldOrderIdealSet{AbsSimpleNumField, AbsSimpleNumFieldElem}}, p::AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem})
The valuation of
evaluate_mod(a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}, B::AbsSimpleNumFieldOrderFractionalIdeal) -> AbsSimpleNumFieldElem
Evaluates
reduce_ideal(A::FacElem{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}) -> AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, FacElem{AbsSimpleNumFieldElem}
Computes
modular_proj(a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}, me::modular_env) -> Vector{fqPolyRepFieldElem}
Given an algebraic number
Positivity & Signs
Factored elements can be used instead of number field elements for the functions sign
, signs
, is_positive
, is_negative
and is_totally_positive
, see Positivity & Signs
Miscellaneous
maxabs_exp(a::FacElem)
Finds the largest exponent by absolute value in the factored element