|
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
This section contains functions for deciding solubility, and
finding points on conics over the following base fields: the
rationals, finite fields, number fields and rational function fields in
odd characteristic.
A point on a conic C is given as a point in the pointset C(K) where
K is the base ring of the conic, unless that base ring is the integers Z,
in which case the returned point belongs to the pointset C(Q).
Over the rationals (or integers), the algorithm used to find rational points
is due to D. Simon[Sim05].
Simon's algorithm works with the symmetric matrix of the defining polynomial
of the conic. It computes transformations reducing the determinant of the
matrix by each of the primes which divide the discriminant of the conic,
until it has absolute value 1. After this it does an indefinite LLL which
reduces it to a unimodular integral diagonal matrix, which is equivalent
to the conic x2 + y2 - z2 = 0, and then the Pythagorean parametrization
of this can be pulled back to the original conic.
The existence of a point on conic C/Q is determined entirely
by local solubility conditions, which are encapsulated in a solubility
certificate.
The algorithm of Simon determines local solubility as it works
prime-by-prime, in its calculation of square roots modulo primes.
In theory the existence of a point can be determined using Legendre
symbols instead of computing these square roots. This is not
implemented because the running time is dominated by the time
needed to factorise the discriminant.
Over number fields, the algorithm for finding points is as follows.
One first reduces to diagonal form, which is done with care to ensure
one can factor the coefficients (assuming one can factor the discriminant
of the original conic). The algorithm for diagonal conics is a variant
of Lagrange's method (which was once the standard method for solving
diagonal conics over Q). It involves a series of reduction steps,
in which the conic is replaced by a simpler conic. Reduction is achieved
by finding a short vector in a suitable lattice sitting inside two copies
of the base field. (This lattice is defined by congruence conditions
coming from local solutions of the conic.) After several reduction steps,
one is often able to find a solution via an easy search. In other
cases, one is unable to reduce further and must call NormEquation
to solve the reduced conic. (This is still vastly superior to calling
NormEquation on the original conic.) The basic reduction loop
is enhanced with several tricks; in particular the class group of the
base field may be used, when it is not too large, to reduce much
further than would otherwise be feasible.
Over rational function fields, the algorithm for solving conics is due to
Cremona and van Hoeij (see [CR06]). The implementation
was contributed by John Cremona and David Roberts.
Over finite fields, the algorithm used for finding a point (x : y : 1)
on a conic is to solve for y at random values of x.
Subsections
The main function is HasRationalPoint, which also returns a point
when one exists. This (and also RationalPoint) works over various
kinds of fields; the other functions work only over the rationals (or integers)
and finite fields.
When a point is found, it is also cached for later use.
The conic C should be defined over the integers, rationals, a finite field,
a number field, or a rational function field over a finite field of odd characteristic.
The function returns true if and only if there exists a point on the conic C,
and if so, also returns one such point.
The conic C should be defined over the integers, rationals, a finite field,
a number field, or a rational function field over a finite field of odd characteristic.
If there exists a rational point on C over its base ring, then a
representative point is returned, otherwise an error results.
Bound: RngIntElt Default: 10^9
Reduce: BoolElt Default: false
Returns a randomly selected rational point of the conic C.
Such a solution is obtained by choosing random integers up to
the bound specified by the parameter Bound, followed by
evaluation at a parametrization of C, then by point reduction,
if so specified by Reduce.
RationalPoints(C) : CrvCon -> SetIndx
Bound: RngIntElt Default: 0
Given a conic over the rationals or a finite field, an indexed
set of the rational points of the conic is returned. If the
curve is over the rationals, then a positive value for the parameter
Bound must be given; this function then returns those points
whose integral coordinates, on the reduced Legendre model,
are bounded by the value of Bound.
We define three conics in Legendre form, having the same prime divisors
in their discriminants, which differ only by a sign change (twisting by
Sqrt( - 1)) of one of the coefficients.
> P2<x,y,z> := ProjectiveSpace(Rationals(),2);
> C1 := Conic(P2,23*x^2+19*y^2-71*z^2);
> RationalPoints(C1 : Bound := 32);
{@ @}
> C2 := Conic(P2,23*x^2-19*y^2+71*z^2);
> RationalPoints(C2 : Bound := 32);
{@ @}
> C3 := Conic(P2,23*x^2-17*y^2-71*z^2);
> RationalPoints(C3 : Bound := 32);
{@ (-31 : 36 : 1), (-31 : -36 : 1), (31 : 36 : 1), (31 : -36 : 1),
(-8/3 : 7/3 : 1), (-8/3 : -7/3 : 1), (8/3 : 7/3 : 1), (8/3 : -7/3 : 1),
(-28/15 : 11/15 : 1), (-28/15 : -11/15 : 1), (28/15 : 11/15 : 1),
(28/15 : -11/15 : 1) @}
This naive search yields no points on the first two curves and
numerous points on the third one. A guess that there are no
points on either of the first two curves is proved by a call
to BadPrimes, which finds that 19 and 23 are ramified
primes for the first curve, and 23 and 71 are ramified
primes for the second.
> BadPrimes(C1);
[ 19, 23 ]
> BadPrimes(C2);
[ 23, 71 ]
> BadPrimes(C3);
[]
The fact there are no ramified primes for the third curve is equivalent
to a true return value from the function HasRationalPoint.
As we will see in Section Isomorphisms, and alternative way,
which is guaranteed to find points on the third curve, would be to
construct a rational parametrization.
If a conic C/Q, in Legendre form ax2 + by2 + cz2=0, has a point,
then Holzer's Theorem tells us that there exists a point (x:y:z)
satisfying
|x| ≤Sqrt(|bc|),
|y| ≤Sqrt(|ac|),
|z| ≤Sqrt(|ab|),
with x, y, and z in Z, or equivalently max(|ax2|, |by2|, |cz2|)
≤|abc|. Such a point is said to be Holzer reduced.
The current Magma implementation uses a variant of Mordell's
reduction due to Cremona [CR03].
Returns true if and only if the projective point p on a conic
in reduced Legendre form satisfies Holzer's bounds. If the curve is
not a reduced Legendre model, then the test is done by passing to this
model for the test.
Reduces the point p so that it satisfies Holzer's bounds.
We provide a tiny example to illustrate reduction and reduction
testing on conics.
> P2<x,y,z> := ProjectiveSpace(Rationals(),2);
> C1 := Conic(P2,x^2 + 3*x*y + 2*y^2 - 2*z^2);
> p := C1![0,1,1];
> IsReduced(p);
false
The fact that this point is not reduced is due to the size of the
coefficients on the reduced Legendre model.
> C0, m := ReducedLegendreModel(C1);
> C0;
Conic over Rational Field defined by
X^2 - Y^2 - 2*Z^2
> m(p);
(3/2 : 1/2 : 1)
> IsReduced(m(p));
false
> Reduction(m(p));
(-1 : 1 : 0)
> Reduction(m(p))@@m;
(-2 : 1 : 0)
> IsReduced($1);
true
In this example we illustrate the intrinsics which apply to finding points
on conics.
> P2<x,y,z> := ProjectiveSpace(RationalField(),2);
> f := 9220*x^2 + 97821*x*y + 498122*y^2 + 8007887*y*z - 3773857*z^2;
> C := Conic(P2, f);
We will now see that C has a reduced solution; indeed, we find two
different reduced solutions. For comparison we also find a non-reduced
solution.
> HasRationalPoint(C);
true (157010/741 : -19213/741 : 1)
> p := RationalPoint(C);
> p;
(157010/741 : -19213/741 : 1)
> q := Random(C : Reduce := true);
> q;
(-221060094911776/6522127367379 : -49731359955013/6522127367379 : 1)
> q := Random(C : Bound := 10^5);
> q;
(4457174194952129/84200926607090 : -1038901067062816/42100463303545 : 1)
> Reduction($1);
(-221060094911776/6522127367379 : -49731359955013/6522127367379 : 1)
To make a parametrization of C one can use the intrinsic
Parametrization to create a map of schemes from a line to C.
Note that if a domain for the parametrization map is not included
among the arguments, one will be created in the background.
It will not have names for its coordinate functions assigned which
is why we do that before viewing the map.
> phi := Parametrization(C);
> P1<u,v> := Domain(phi);
> q0 := P1![0,1]; q1 := P1![1,1]; q2 := P1![1,0];
> phi(q0);
(7946776/559407 : -21332771/1118814 : 1)
> phi(q1);
(26443817/1154900 : -5909829/288725 : 1)
> phi(q2);
(157010/741 : -19213/741 : 1)
> C1, psi := ReducedLegendreModel(C);
> psi(phi(q0));
(-1793715893111/4475256 : -22556441171843029/4475256 : 1)
> p0 := Reduction($1);
> p0;
(1015829527/2964 : -59688728328467/2964 : 1)
> IsReduced(p0);
true
> p0@@psi;
(157010/741 : -19213/741 : 1)
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|
