Factored Elements

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 $Q[\sqrt d]$ it is known that the coefficients wrt. the canonical basis $1, \sqrt d$ can have $O(\exp \sqrt d)$ many digits. All currently known, fast methods construct those elements as power products of smaller elements, allowing the computer to handle them.

Mathematically, one can think of factored elements to formally live in the ring $Z[K]$ the group ring of the non-zero field elements. Thus elements are of the form $ \prod ai^{ei}$ where $a_i$ are elements in $K$, typically small and the $e_i\in Z$ are frequently large exponents. We refer to the $a_i$ as the base and the $e_i$ as the exponents of the factored element.

Since $K$ is, in general, no PID, this presentation is non-unique, elements in this form can easily be multiplied, raised to large powers, but in general not compared and not added.

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

It should be noted that an object of type `$FacElem{fmpz, FlintIntegerRing}$ will, in general, not represent an integer as the exponents can be negative.

Construction

In general one can define factored elements by giving 2 arrays, the base and the exponent, or a dictionary containing the pairs:

Hecke.FacElem — Type.
FacElem{B}(base::Array{B, 1}, exp::Array{fmpz, 1}) -> FacElem{B}

Returns the element $\prod b_i^{e_i}$, un-expanded.

FacElem{B}(d::Dict{B, fmpz}) -> FacElem{B}
FacElem{B}(d::Dict{B, Integer}) -> FacElem{B}

Returns the element $\prod b^{d[p]}$, un-expanded.

Hecke.FacElem — Method.
FacElem{B}(base::Array{B, 1}, exp::Array{fmpz, 1}) -> FacElem{B}

Returns the element $\prod b_i^{e_i}$, un-expanded.

FacElem{B}(d::Dict{B, fmpz}) -> FacElem{B}
FacElem{B}(d::Dict{B, Integer}) -> FacElem{B}

Returns the element $\prod b^{d[p]}$, un-expanded.

Hecke.ideal — Method.
 ideal(O::NfOrd, a::FacElem{nf_elem, AnticNumberField)

The factored fractional ideal $a*O$.

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.

AbstractAlgebra.Generic.evaluate — Method.

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.

AbstractAlgebra.Generic.evaluate — Method.
evaluate(x::FacElem{fmpq}) -> fmpq
evaluate(x::FacElem{fmpz}) -> fmpz

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.

AbstractAlgebra.Generic.evaluate — Method.

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.

Hecke.evaluate_naive — Method.

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:

Hecke.simplify — Method.
simplify(x::FacElem{NfOrdIdl, NfOrdIdlSet}) -> FacElem
simplify(x::FacElem{NfOrdFracIdl, NfOrdFracIdlSet}) -> FacElem

Uses coprime_base to obtain a simplified version of $x$, ie. in the simplified version all base ideals will be pariwise coprime but not neccessarily prime!.

Hecke.simplify — Method.
simplify(x::FacElem{fmpq}) -> FacElem{fmpq}
simplify(x::FacElem{fmpz}) -> FacElem{fmpz}

Simplfies the factored element, i.e. arranges for the base to be coprime.

The simplified version can then be used further:

Base.isone — Method.
isone(x::FacElem{fmpq}) -> Bool
isone(x::FacElem{fmpz}) -> Bool

Tests if $x$ represents $1$ without an evaluation.

Hecke.factor_coprime — Method.
factor_coprime(x::FacElem{fmpz}) -> Fac{fmpz}

Computed a partial factorisation of $x$, ie. writes $x$ as a product of pariwise coprime integers.

Hecke.factor_coprime — Method.
factor_coprime(x::FacElem{NfOrdIdl, NfOrdIdlSet}) -> Dict{NfOrdIdl, Int}

Computed a partial factorisation of $x$, ie. writes $x$ as a product of pariwise coprime integral ideals.

Hecke.factor_coprime — Method.
 factor_coprime(Q::FacElem{NfOrdFracIdl, NfOrdFracIdlSet}) -> Dict{NfOrdIdl, Int}

A coprime factorisation of $Q$: each ideal in $Q$ is split using \code{integral_split} and then a coprime basis is computed. This does {\bf not} use any factorisation.

Hecke.factor_coprime — Method.

factorcoprime(a::FacElem{nfelem, AnticNumberField}, I::NfOrdIdlSet) -> Dict{NfOrdIdl, fmpz}

Factors the rincipal ideal generated by $a$ into coprimes by computing a coprime basis from the principal ideals in the factorisation of $a$.

Hecke.factor — Method.
 factor(Q::FacElem{NfOrdFracIdl, NfOrdFracIdlSet}) -> Dict{NfOrdIdl, Int}

The factorisation of $Q$, by refining a coprime factorisation.

Hecke.factor — Method.

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

Factors the principal ideal generated by $a$ by refinind a coprime factorisation.

For factorised algebraic numbers a unique simplification is not possible, however, this allows still do obtain partial results:

Hecke.compact_presentation — Function.
compact_presentation(a::FacElem{nf_elem, AnticNumberField}, n::Int = 2; decom, arb_prec = 100, short_prec = 1000) -> FacElem

Computes a presentation $a = \prod a_i^{n_i}$ where all the exponents $n_i$ are powers of $n$ and, the elements $a$ are "small", generically, they have a norm bounded by $d^{n/2}$ where $d$ is the discriminant of the maximal order. As the algorithm needs the factorisation of the principal ideal generated by $a$, it can be passed in in \code{decom}.

Hecke.signs — Method.
signs(a::nf_elem)          -> Dict{InfPlc, Int}
signs(a::FacElem{nf_elem}) -> Dict{InfPlc, Int}

This function returns a dictionary of the signs of $a$ at all infinite places of the ambient number field. The keys are infinite places of the ambient number field. The value is $1$ if the sign is positive and $-1$ if the sign is negative.

Hecke.signs — Method.
signs(a::nf_elem, l::Vector{InfPlc})          -> Dict{InfPlc, Int}
signs(a::FacElem{nf_elem}, l::Vector{InfPlc}) -> Dict{InfPlc, Int}

This function returns a dictionary of the signs of $a$ at places in $l$. The keys are the elements of $l$. The value is $1$ if the sign is positive and $-1$ if the sign is negative. The result will contain as many signs as there are real places contained in $l$.

Base.sign — Method.
sign(a::nf_elem, P::InfPlc)          -> Int
sign(a::FacElem{nf_elem}, P::InfPlc) -> Int

This function returns the sign of $a$ at the place $P$. The value is $1$ if the sign is positive and $-1$ if the sign is negative.

Nemo.ispositive — Method.
ispositive(a::nf_elem, P::InfPlc)          -> Bool
ispositive(a::FacElem{nf_elem}, P::InfPlc) -> Bool

Returns whether the element $a$ is positive at the embedding corresponding to $P$. The place $P$ must be real.

Nemo.ispositive — Method.
ispositive(a::nf_elem, l::Vector{InfPlc})          -> Bool
ispositive(a::FacElem{nf_elem}, l::Vector{InfPlc}) -> Bool

Returns whether the element $a$ is positive at the embeddings corresponding to the real places of $l$.

Hecke.istotally_positive — Method.
istotally_positive(a::nf_elem)          -> Bool
istotally_positive(a::FacElem{nf_elem}) -> Bool

Returns whether the element $a$ is totally positive, that is, whether it is positive at all places of the ambient number field.

AbstractAlgebra.Generic.valuation — Method.
valuation(a::FacElem{nf_elem, AnticNumberField}, P::NfOrdIdl) -> fmpz

The valuation of $a$ at $P$.

AbstractAlgebra.Generic.valuation — Method.
valuation(A::FacElem{NfOrdFracIdl, NfOrdFracIdlSet}, p::NfOrdIdl)
valuation(A::FacElem{NfOrdIdl, NfOrdIdlSet}, p::NfOrdIdl)

The valuation of $A$ at $P$.

Hecke.evaluate_mod — Method.
evaluate_mod(a::FacElem{nf_elem, AnticNumberField}, B::NfOrdFracIdl) -> nf_elem

Evaluates $a$ using CRT and small primes. Assumes that the ideal generated by $a$ is in fact $B$. Useful in cases where $a$ has huge exponents, but the evaluated element is actually "small".

Hecke.pure_extension — Method.
pure_extension(n::Int, gen::FacElem{nf_elem, AnticNumberField}) -> NfRel{nf_elem}, NfRelElem
pure_extension(n::Int, gen::nf_elem) -> NfRel{nf_elem}, NfRelElem

Create the field extension with the defining polynomial $x^n-gen$.

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

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

Hecke.modular_proj — Method.

modularproj(a::FacElem{nfelem, AnticNumberField}, me::modularenv) -> Array{fqnmod, 1}

Given an algebraic number $a$ in factored form and data \code{me} as computed by \code{modular_init}, project $a$ onto the residue class fields.

Miscellaneous

Hecke.max_exp — Method.
max_exp(a::FacElem)

Finds the largest exponent in the factored element $a$

Hecke.min_exp — Method.
min_exp(a::FacElem)

Finds the smallest exponent in the factored element $a$

Hecke.maxabs_exp — Method.
maxabs_exp(a::FacElem)

Finds the largest exponent by absolute value the factored element $a$