GitHub

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 with respect to a fixed basis for the field: for the fundamental unit in $Q[\sqrt d]$ it is known that the coefficients with respect to 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 $\mathbb{Z}[K^*]$ the group ring of the non-zero field elements. Thus elements are of the form $\prod a_i^{e_i}$ where $a_i$ are elements in $K$, typically small and the $e_i\in \mathbb{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.

Presentations of elements of $K^*$ are 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 captured 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 integers
  • FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}, factored algebraic numbers
  • FacElem{AbsNumFieldOrderIdeal, AbsNumFieldOrderIdealSet}, factored ideals

It should be noted that an object of type FacElem{ZZRingElem, ZZRing} 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:

FacElem — Type
FacElem{B, S}

Type for factored elements, that is elements of the form prod ai^ki for elements a_i of type B in a ring of type S.

source
FacElem — Method
FacElem{B}(R, base::Vector{B}, exp::Vector{ZZRingElem}) -> FacElem{B}

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

source
FacElem{B}(base::Vector{B}, exp::Vector{ZZRingElem}) -> FacElem{B}

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

source
FacElem{B}(R, d::Dict{B, ZZRingElem}) -> FacElem{B}
FacElem{B}(R, d::Dict{B, Integer}) -> FacElem{B}

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

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

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

source
ideal — Method
 ideal(O::AbsSimpleNumFieldOrder, a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField)

The factored fractional ideal $a*O$.

source

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 — 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.

source
evaluate — Method
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.

source
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.

source
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.

source

Special functions

In the case where the parent of the base allows for efficient gcd computation, power products can be made unique:

simplify — Method
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 $x$, ie. in the simplified version all base ideals will be pariwise coprime but not necessarily prime!.

source
simplify — Method
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.

source

The simplified version can then be used further:

isone — Method
isone(x::FacElem{QQFieldElem}) -> Bool
isone(x::FacElem{ZZRingElem}) -> Bool

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

source
factor_coprime — Method
factor_coprime(x::FacElem{ZZRingElem}) -> Fac{ZZRingElem}

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

source
factor_coprime — Method
factor_coprime(x::FacElem{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, AbsNumFieldOrderIdealSet{AbsSimpleNumField, AbsSimpleNumFieldElem}}) -> Dict{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, Int}

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

source
factor_coprime — Method
factor_coprime(Q::FacElem{AbsSimpleNumFieldOrderFractionalIdeal, AbsNumFieldOrderFractionalIdealSet{AbsSimpleNumField, AbsSimpleNumFieldElem}}) -> Dict{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, 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.

source
factor_coprime — Method
factor_coprime(I::AbsNumFieldOrderIdealSet{AbsSimpleNumField, AbsSimpleNumFieldElem}, a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}) -> Dict{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, ZZRingElem}

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

source
factor — Method
 factor(Q::FacElem{AbsSimpleNumFieldOrderFractionalIdeal, AbsNumFieldOrderFractionalIdealSet{AbsSimpleNumField, AbsSimpleNumFieldElem}}) -> Dict{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, Int}

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

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

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

source

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

compact_presentation — Function
compact_presentation(a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}, 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_i$ 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}.

source
valuation — Method
valuation(a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}, P::AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}) -> ZZRingElem

The valuation of $a$ at $P$.

source
valuation — Method
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 $A$ at $P$.

source
evaluate_mod — Method
evaluate_mod(a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}, B::AbsSimpleNumFieldOrderFractionalIdeal) -> AbsSimpleNumFieldElem

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".

source
reduce_ideal — Method
reduce_ideal(A::FacElem{AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}}) -> AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}, FacElem{AbsSimpleNumFieldElem}

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

source
modular_proj — Method
modular_proj(a::FacElem{AbsSimpleNumFieldElem, AbsSimpleNumField}, me::modular_env) -> Vector{fqPolyRepFieldElem}

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.

source

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

max_exp — Method
max_exp(a::FacElem)

Finds the largest exponent in the factored element $a$.

source
min_exp — Method
min_exp(a::FacElem)

Finds the smallest exponent in the factored element $a$.

source
maxabs_exp — Method
maxabs_exp(a::FacElem)

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

source