|
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
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 the matrix to a unimodular integral diagonal matrix, which is equivalent
to the conic x2 + y2 - z2 = 0, and then the Pythagorean parametrisation
of this can be pulled back to the original conic.
The existence of a point on a conic C/Q is determined entirely
by local solubility conditions, which are encapsulated in a solubility
certificate.
The algorithm of Simon works prime-by-prime, determining local solubility
as it goes through 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 that
one can factor the coefficients (assuming that 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
each of 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
arising 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, when it is not too large
the class group of the base field may be used 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 [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.
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 such 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 parametrisation of C, then by point reduction
if the parameter Reduce is set to true.
(See Section Point Reduction
for more information about point reduction.)
RationalPoints(C : parameters) : CrvCon -> SetIndx
Bound: RngIntElt Default:
Given a conic over the rationals or a finite field, returns an
indexed set of the rational points of the conic. If the
curve is defined 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 that 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, an alternative approach
which is guaranteed to find points on the third curve would be to
construct a rational parametrisation.
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.
There exist constructive algorithms to find a Holzer-reduced point
from a given one;
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 after passing to
this model.
Returns a Holzer-reduced point derived from p.
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)
> IsReduced(p);
true
> q := Random(C : Reduce := true);
> q;
(-221060094911776/6522127367379 : -49731359955013/6522127367379 : 1)
> IsReduced(q);
true
> q := Random(C : Bound := 10^5);
> q;
(4457174194952129/84200926607090 : -1038901067062816/42100463303545 : 1)
> IsReduced(q);
false
> Reduction(q);
(-221060094911776/6522127367379 : -49731359955013/6522127367379 : 1)
> IsReduced($1);
true
To make a parametrisation of C one can use the intrinsic
Parametrization to create a map of schemes from a line to C.
> 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]
|