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:
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]).
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.
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.
- - 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.
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.
> 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.
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.
> 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]).
> 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.
> 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