|
Magma has routines for solving norm equations, Thue equations,
index form equations and unit equations.
Norm equations in the context of number fields occur in many applications.
While Magma contains efficient algorithms to solve norm equations
it is important to understand the difference between the various types of
norm equations that occur. Given some element θ in
a number field k together with a finite extension K/k, there are two
different types of norm equations attached to this data:
- - Diophantine norm equations, that is norm equations where a solution
x∈K is restricted to a particular order (or any additive subgroup), and
- - field theoretic norm equations where any element in x∈K with
N(x) = θ is a solution.
While in the first case the number of different (up to equivalence)
solutions is finite, no such restriction holds in the field case.
On the other hand, the field case often allows to prove the existence
or non-existence of solutions quickly, while no efficient tests exist
for the Diophantine case. So it is not surprising that different
methods are applied for the different cases. We will discuss the differences
with the individual intrinsics.
NormEquation(O, m) : RngOrd, RngOrdElt -> BoolElt, [ RngOrdElt ]
All: BoolElt Default: true
Solutions: RngIntElt Default: All
Exact: BoolElt Default: false
Ineq: BoolElt Default: false
Given an order O and an element m of the ground ring of O which can be
a positive integer or an element of a suborder, this intrinsic solves
a Diophantine norm equation.
This function returns a
boolean indicating whether an element α∈O exists such that
NF/L(α), the norm of α with respect to the subfield L
of F (the field of fractions of O),
equals m, and if so, a sequence of length at most Solutions
of solutions α.
The parameter Exact may be used to indicate whether
an exact solution is required (with Exact := true) or
whether a solution up to a torsion unit suffices.
The maximal number of required solutions can be indicated with
the Solutions parameter, but setting All := true
will override this and the search will find all solutions.
If the order is absolute, then the parameter Ineq may be
set to true. If so, all solutions x with |N(x)| <= m will be found
using a variation of Fincke's ellipsoid method ([Fin84], [PZ89]).
Depending on whether the order is absolute maximal, absolute or (simple)
relative, different algorithms are used.
If the order is an absolute maximal order, Magma will, in a first step,
enumerate all integral ideals having the required norm (up to sign).
Next, all the ideals are tested for principality using the
class group based method. If Exact := true, then a third step is added:
we try to find a unit in O
of norm -1. This unit is used to sign adjust the solution(s).
If there is no such unit, we drop all solutions of the wrong sign.
If the order is absolute, but not maximal, the norm equation is first solved
in the maximal order using the above outlined method. In a second step,
a complete set of representatives for the unit group of the maximal order
modulo the units of O is computed and Magma attempts to combine solutions
in the maximal order with those representatives to get solutions in O.
If Solutions is set, the search stops after the required number of
solutions is found.
In case the order is of type RngOrd and in some imaginary quadratic
field, the norm function is a positive definite quadratic form, thus
algorithms based on that property are used.
In case the right hand side m equals ∓ 1, lattice based methods are
applied.
If Ineq is true, which is only supported for absolute fields,
lattice enumeration techniques ([Fin84], [PZ89]) based
on Fincke's ellipsoid method are used.
If the order is (simply) relative different algorithms are implemented,
depending on the number of solutions sought. However, common to all of them
is that they (partially) work in the AbsoluteOrder of O.
If O is a relative maximal order and if we only want to find 1 solution
(or to prove that there is none), Magma first looks for (integral) solutions
in the field using an S-unit based approach as outlined in
NormEquation. This step gives an affine subspace
of the S-unit group that contains all integral solutions of our equation.
In a second step, a simplex based technique is used to find totally
positive elements in the subspace.
In All is given or Solutions is >1, then
lattice based methods are used ([Fie97], [Jur93], [FJP97]).
NormEquation(F, m) : FldAlg, RngIntElt -> BoolElt, [ FldAlgElt ]
NormEquation(F, m) : FldAlg, FldAlgElt -> BoolElt, [ FldAlgElt ]
NormEquation(F, m) : FldAlg, FldRatElt -> BoolElt, [ FldAlgElt ]
Primes: eseq of prime ideals Default: []
Nice: BoolElt Default: true
Given a field F and an element m of the base field of F,
this function returns a
boolean indicating whether an element α∈F exists such that
NF/L(α), the norm of α with respect to the base field L
of F
equals m, and if so, a sequence of length 1
of solutions α.
The field theoretic norm equations are all solved using S-units. Before
discussing some details, we outline the method.
- - Determine a set S of prime ideals. We try to obtain a solution
as a S-unit for this set S.
- - Compute a basis for the S-units
- - Compute the action of the norm-map
- - Obtain a solution as a preimage.
In general, no effective method is known for the first step. If the
field is relative normal however, it is known that is S generates the
class group of F and if m is a S-unit, then S is large
enough (suitable in ([Coh00, 7.5]) [Fie97], [Sim02], [Gar80].
Thus to find S we have to compute the class group of F. If a (conditional)
class group is already known, it is used, otherwise an unconditional
class group is computed. The initial set S consists of all
prime ideals occurring in the decomposition of mZF. Note that
this step includes the factorisation of m and thus can take a long
time is m is large.
Next, we determine a basis for the S-unit group and the action of the norm
on it. This give the norm map as a map on the S-unit group as an
abstract abelian group.
Finally, the right hand side m is represented as an element of the S-unit
group and a solution is then obtained as a preimage under the norm map.
If Nice is true, then Magma attempts to find a smaller solution
by applying a LLL reduction to the original solution.
If Primes is give it must contain a list of prime ideals of L.
Together with the primes dividing m it is used to form the set S bypassing
the computation of an unconditional class group in this step.
If L is not normal this can be used
to guarantee that S is large enough. Note that the class group
computation is still performed when the S-units are computed. Since the
correctness of the S-unit group (we need only p-maximality for all primes
dividing the (relative) degree of L) can be verified independently of the
correctness of the class group, this can be used to derive provable
results in cases where the class group cannot be computed unconditionally.
By default, the MaximalOrder(L) is used to compute the class group.
If the attribute NeqOrder is set on L it must contain a
maximal order of L. If present, this order will be used for all the
subsequent computations.
Raw: BoolElt Default: false
Primes: eseq of prime ideals Default: []
Let N be a map on the multiplicative group of some number field. Formally
N may also be defined on the maximal order of the field. This intrinsic
tries to find a pre-image for m under N.
This function works by realising N as a endomorphism of S-units
for a suitable set S.
If N is a relative norm and if L is (absolutely) normal then
the set S as computed for the field theoretic norm equation is
guaranteed to be large enough to find a solution if it exists.
Note: this condition is not checked.
If Primes is given it will be supplemented by the primes
dividing m and then used as the set S.
If Raw is given, the solution is returned as an unevaluated
power product. See the example for details.
The main use of this function is for Galois theoretical constructions
where the subfields are defined as fields fixed by certain automorphisms.
In this situation the norm function can be realised as the product over
the fixed group. It is therefore not necessary to compute a (very messy)
relative representation of the field.
Nice: BoolElt Default: true
For a an integer or a unit in some number field, N being a multiplicative
function on some number field k which is the field of fractions of the
order O, try to find a unit in O that is the preimage of a under N.
In particular, N restricted to O must be an endomorphism of O.
If Nice is true, the solution will be size-reduced. In particular
when the conductor of O in the maximal order of k is large, and therefore
the unit index (Zk) * : O * is large as well, this function is much more
efficient than the lattice based approach above.
S: [RngOrdIdl] Default: false
HasSolution: BoolElt Default: false
For a number field K and subfield elements e∈k1 and f∈k2,
try to find a solution to the simultaneous norm equations
NK/k1(x) = e and NK/k2(x) = f.
The algorithm proceeds by first guessing a likely set S of prime ideals
that will support a solution - it is exists. Initially S will contain
all ramified primes in K, the support of e and f and enough primes
to generate the class group of K. In case K is normal over Q
this set is large enough to support a solution if there is a solution at all.
For arbitrary fields that is most likely not the case.
However, if S is passed in as a parameter then the set used internally
will contain at least this set.
If HasSolution is true, Magma will add primes to S until a
solution has been found. This is useful in situations where for some theoretical
reason it is known that there has to be a solution.
We try to solve N(x) = 3 in some relative extension:
(Note that since the larger field is a quadratic extension, the
second call tells us that there is no integral element with norm 3)
> x := PolynomialRing(Integers()).1;
> O := MaximalOrder(NumberField([x^2-229, x^2-2]));
> NormEquation(O, 3);
false
> NormEquation(FieldOfFractions(O), 3);
true [
5/1*$.1*O.1 + 2/3*$.1*O.2
]
Next we solve the same equation but come from a different angle,
we will define the norm map as an element of the group ring and, instead
of explicitly computing a relative extension, work instead with the
implicit fix-field.
> K := AbsoluteField(FieldOfFractions(O));
> t := K!NumberField(O).2;
> t^2;
2/1*K.1
> A, _, mA := AutomorphismGroup(K);
> F := sub<A | [ x : x in A | mA(x)(t) eq t]>;
> N := map<K -> K | x:-> &* [ mA(y)(x) : y in F]>;
> NormEquation(3, N);
true [
5/1*K.1 + 2/3*K.3
]
Finally, to show the effect of Raw:
> f, s, base := NormEquation(3, N:Raw);
> s;
[
(0 -1 0 -2 0 1 0 0 0 -1 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0)
]
> z := PowerProduct(base, s[1]);
> z;
5/1*K.1 + 2/3*K.3
> N(z);
3/1*K.1;
Thue equations are Diophantine equations of the form f(x, y) = k, where k
is some integer constant and f is a homogeneous polynomial in two variables.
Methods for computing all solutions to such equations are known, although the
search space may be larger than is practical.
To work with such equations in Magma a Thue object (category Thue)
must be created to store information related to the computations.
To solve Thue equations the reduction of Bilu and Hanrot ([BH96])
is used.
Given a polynomial f of degree at least 2 over the integers, this function
returns the `Thue object' corresponding to f; such objects are used by the
functions for solving Thue equations. They are printed as the homogeneous
version of f.
Given an order O with Z as its coefficient ring, this function
returns the Thue object corresponding to the defining polynomial of O.
Evaluate(t, S) : Thue, [ RngIntElt ] -> RngIntElt
Given a Thue object t and integers a, b, this function returns
the evaluation of
the homogeneous polynomial f involved in t at (a, b), that is
f(a, b). The second form takes as argument the sequence [a, b] instead.
This can be convenient if checking the results from an inexact solution.
Exact: BoolElt Default: true
SetVerbose("ThueEq", n): Maximum: 5
Given a Thue object t and an integer a, this function returns a sequence
consisting of all sequences of two integers [x, y] which solve the
equation f(x, y) = a, where f is the (homogeneous form of) the Thue
equation associated with t. If the optional parameter Exact is
set to false then solutions to f(x, y) = - a will also be found.
A use of thue equations is shown.
> R<x> := PolynomialRing(Integers());
> f := x^3 + x + 1;
> T := Thue(f);
> T;
Thue object with form: X^3 + X Y^2 + Y^3
> Evaluate(T, 3, 2);
47
> Solutions(T, 4);
[]
> Solutions(T, 7);
[]
> Solutions(T, 47);
[
[ -1, 4 ],
[ 3, 2 ]
]
> S := Solutions(T, -47 : Exact := false);
> S;
[
[ -3, -2 ],
[ -1, 4 ],
[ 1, -4 ],
[ 3, 2 ]
]
> [Evaluate(T, s) : s in S];
[ -47, 47, -47, 47 ]
Unit equations are equations of the form
aε + bη = c
where a, b and c are some algebraic numbers and ε and η
are unknown units in the same field.
SetVerbose("UnitEq", n): Maximum: 5
Return the sequence of 1 x 2 matrices (e1, e2)
such that ae1 + be2 = c for number field elements a, b and c,
where e1 and e2 are units in the maximal order.
The algorithm uses Wildanger's method ([Wil97], [Wil00]).
Usage of UnitEquation is shown.
> R<x> := PolynomialRing(Integers());
> K<a> := NumberField(x^7 - x^6 + 8*x^5 + 2);
> UnitEquation(a^7, 4*a^2 + a^80, a^7 + a^80 + 4*a^2);
[
[[1, 0, 0, 0, 0, 0, 0] [1, 0, 0, 0, 0, 0, 0]]
]
Given an absolute number field K with some order O, index form
equations are equations of the form (O:Z[α]) = k where k is some
positive integer.
In particular, if k=1 this function will find "all" integral power bases.
In this context "all" means up to equivalence, where two solutions
α and β are equivalent iff α = ∓ β + r for
some integer r.
If the field degree is larger than 4, the field must be normal and
an integral power basis must already be known.
The implementation follows [Wil97], [Wil00] for large degree equations,
[GPP93], [GPP96] for quartics and [GS89] for cubic fields.
SetVerbose("IndexFormEquation", n): Maximum: 5
Given an absolute order O, this function will find "all"
(up to equivalence) solutions α∈O to (O:Z[α])=k.
In the current implementation, the unit rank must be no more than 10.
We try to compute all integral power bases of the field defined by
a zero of x 4 - 14x 3 + 14x 2 - 14x + 14:
> x := PolynomialRing(Integers()).1;
> O := MaximalOrder(x^4-14*x^3+14*x^2-14*x+14);
> IndexFormEquation(O, 1);
[
[0, 1, 0, 0]
[0, 1, -13, 1],
[0, 1, -1, 1],
]
> [ MinimalPolynomial(x) :x in $1 ];
[
x^4 - 14*x^3 + 14*x^2 - 14*x + 14,
x^4 - 28*x^3 + 56*x^2 + 3962*x - 28014,
x^4 - 2044*x^3 + 6608*x^2 - 7126*x + 2562
]
> [ Discriminant(x) : x in $1 ] ;
[ -80240048, -80240048, -80240048 ]
> Discriminant(O);
-80240048
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|