|
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
Magma can solve norm, Thue, index form and unit equations.
In this section, we will only dicuss norm equations, other types
of Diophantine equations are discussed in Solving 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.
NormEquation(F, m) : FldNum, RngIntElt -> BoolElt, [ FldNumElt ]
NormEquation(F, m) : FldNum, FldNumElt -> BoolElt, [ FldNumElt ]
NormEquation(F, m) : FldNum, FldNumElt -> BoolElt, [ FldNumElt ]
Primes: eseq of prime ideals Default: []
Nice: BoolElt Default: true
Given a number 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 the element 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.
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;
> K := NumberField([x^2-229, x^2-2]);
> NormEquation(K, 3);
true [
1/3*K.1 - 16/3
]
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 fixed field.
> F := AbsoluteField(K);
> t := F!K.2;
> t^2;
2
> A, _, mA := AutomorphismGroup(F);
> S := sub<A | [ x : x in A | mA(x)(t) eq t]>;
> N := map<F -> F | x:-> &* [ mA(y)(x) : y in S]>;
> NormEquation(3, N);
true [
-5/1*$.1 + 2/3*$.3
]
Finally, to show the effect of Raw:
> f, s, base := NormEquation(3, N:Raw);
> s;
[
( 0 1 -1 1 -1 0 2 -1 -1 -1 -1 2 0 0)
]
> z := PowerProduct(base, s[1]);
> z;
-5/1*$.1 + 2/3*$.3
> N(z);
3
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|
