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.)
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.
> 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.
> 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); falseThe 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
> 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); trueTo 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)