Magma can solve norm, Thue, index form and unit equations.
Elements alpha of an order or algebraic field with norm equal to a given element can be calculated.
All: BoolElt Default: true
Solutions: RngIntElt Default: All
Exact: BoolElt Default: false
Ineq: BoolElt Default: false
Integral: BoolElt Default: true
Primes: eseq of prime ideals Default: []
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 function returns a boolean indicating whether an element alpha in O exists such that N_(F/L)(alpha), the norm of alpha 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 alpha. If an algebraic field F is given rather than the order O, solutions in the order with the same basis of F are found.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. In order to solve with Exact := true, 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.
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 field or 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]).
If Integral is set to false, we try to find a fractional solution instead of integral ones. Currently, this can only used for relative norm equations and to search for one solution. If no Primes are specified, generators for the class group of the larger field are used. If the field is normal over its coefficient field then this choice allows us to find a fractional solution if there is one. However, if the field is not relative normal, then one needs to consider ideals generating parts of the class group of the normal closure. In this case, the list of admissible prime divisors of the denominator must be given by the user.
To solve a norm equation N(x) = m for x in O, m in Z with All := true, the maximal order M of O is computed first. Next, all integral ideals A subject to N(A) = |m| are enumerated by finding all prime ideals with norm dividing m and then combining appropriately. The ideals generated in this way are tested for being principal and if they are a generator is computed. Now we have a complete list L of non--associate solutions to |N(x)| = |m| where x in M. We proceed to compute a transversal T of U_O in U_M (the unit group U_O of O is of finite index in U_M). The complete list of solutions to |N(x)| = |m| with x in O is determined as { t * l | t in T, l in L, t * l in O}.
To solve norm equations in relative extensions a different approach based on S-units is used. For details see [Fie97], [Coh00].
> x := PolynomialRing(Integers()).1;
> O := MaximalOrder(NumberField([x^2-229, x^2-2]));
> NormEquation(O, CoefficientRing(O)!3:Integral := false, \
> Exact := true, Solutions := 1);
true [
5/1*$.1*O.1 + 2/3*$.1*O.2
]
> NormEquation(O, CoefficientRing(O)!3:Integral := true, Exact := true);
false
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 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 ]
SetVerbose("UnitEq", n): Maximum: 5
Return the sequence of 1 x 2 matrices (e1, e2) such that a * e1 + b * e2 = 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 a absolute number field K with some order O, index form equations are equations of the form (O:Z[alpha]) = 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 alpha and beta are equivalent iff alpha = +- beta + r for some integer r.
If the field degree is larger than 4, the field must be normal.
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 alpha in OP to (O:Z[alpha])=k.
> 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 - 28*x^3 + 56*x^2 + 3962*x - 28014,
x^4 - 2044*x^3 + 6608*x^2 - 7126*x + 2562,
x^4 - 14*x^3 + 14*x^2 - 14*x + 14
]
> [ Discriminant(x) : x in $1 ] ;
[ -80240048, -80240048, -80240048 ]
> Discriminant(O);
-80240048