The algorithm chosen to compute a solution of a conic is due to J. E. Cremona [Cre00]. It is essentially a factorization-free reduction method where the only factorization that occurs is that of the coefficients of the reduced form of the conic.
Successive recursive steps of the algorithm reduce the coefficients of the conic's reduced form by using partial factorizations and lattice reduction. The partial factorizations involve only GCD and exact integer division operations.
Once a solution is obtained, it is further reduced so that it satisfies Holzer's bounds. This is achieved using one of two methods: either by using Mordell's method or by using a quadratic parametrization. In most cases we will be reducing solutions via a quadratic parametrization since this method has been shown to be more efficient than Mordell's method. However, in some instances the user will be given the opportunity to deliberately use Mordell's reduction method instead.
A solution to the conic C will be given as a point whose parent is a pointset of the conic. The pointset will be defined over the base ring of C unless that base ring is the integers Z, in which case rather than lying in the point set of the base ring, the solution will lie in the pointset of the rationals Q.
We use the phrases "a solution of the conic C" and "a point on the conic C" synonymously. There is a solution for a conic C if and only if C has a solubility certificate and the coefficients of its Legendre equation (the diagonalised quadratic form) do not all have the same sign. Assuming that C is defined over a projective space, if C has a solution then C also has a reduced solution.
It might however be the case that C has no reduced solution when C is defined over an affine space. This happens when any (non-reduced) solution of C reduces to a point at infinity. Consequently the solutions to a conic C will always be returned as projective points: if C is affine, then the solutions will be points on the projective closure of C. The only exception to this rule is when one specifically asks for an affine point using the intrinsic ReducedAffineSolution.
Once a reduced solution to the conic is found it is stored with the conic. Consequently, any subsequent calls for finding a reduced solution will always return the same point. In order to find other reduced, or indeed non-reduced points on the conic, consult Sections All Solutions via Parametrization and Reducing a Point below.
Returns true if and only if a reduced/point solution to the conic C has been found. If C is projective, then the solution is a point on C. If C is affine, then the solution is a point on ProjectiveClosure(C).
Returns a reduced solution of the conic C. If C is projective, then the solution is a point on C whereas if C is affine, then the solution is a point on ProjectiveClosure(C).
Returns true if and only if a reduced solution of the affine conic C has been found which is not at infinity. If true, this solution is returned as an affine point on C.
Returns a reduced solution of the affine conic C if the point-finding algorithm returns a point of the projective closure of C which does not lie at infinity. The solution is returned as an affine point on C.
Once a (not necessarily reduced) solution to the conic C is found, one can also compute a parametrization for C. As for a reduced solution of C this parametrization is then also stored with the conic.
Knowing a parametrization for C enables one to find any point on C. This is the object of the intrinsic Solution. A solution to a conic C will always be returned as a projective point. If C is affine, then the solution will be a point on the projective closure of C.
Returns a parametrization of the conic C as a 3 x 3 matrix. The coefficients of the matrix lie in the base ring of C unless that base ring is Z in which case they live in Q.
A map of schemes which parametrises the conic C. The scheme X must be a one-dimensional ambient space. If C is an affine conic, then X must be affine, and if C is projective then X must be projective. The map will have X as its domain and C as its codomain.
Reduce: BoolElt Default: true
MordellReduction: BoolElt Default: false
Returns a solution of the conic C. The two intrinsics are synonymous. Such a solution is obtained by chosing pseudo-random integers which are then evaluated at a parametrization of C. If C is projective, then the solution is a point on C. If C is affine, then the solution is a point on ProjectiveClosure(C). The parameters allow one to choose to reduce the point using Mordell's method or using a quadratic parametrization.
MordellReduction: BoolElt Default: false
Reduces the point p so that it satisfies Holzer's bounds. If MordellReduction is set to true then the solution is reduced via Mordell's method, otherwise it is reduced via a quadratic parametrization. The point p must be a projective point.
Returns true if and only if the point p satisfies Holzer's bounds. The point p must be a projective point.
> Q := RationalField(); > PU<x1> := PolynomialRing(Q); > NF := NumberField(119/44*x1^2 - 908/555*x1 + 723/259); > P<x,y,z> := ProjectiveSpace(NF,2); > f := 1/11*34*x^2 - 1/3629*28523*x*y - 1/32375*41003*x*z > - 1/697*953*y^2 - 1/7656*3347*y*z - 1/852*245*z^2; > C := Conic(P, 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.
> HasReducedPoint(C); true > p := ReducedProjectiveSolution(C); > p; (331066858679475709/547218109724996625 : 277276767171226/18635910857507625 : 1) > q := Solution(C); > IsReduced(q); true > p eq q; false > Solution(C:Reduce:=false); (-2887121074646977153068678258143737441/13201802189171201892211899371970852000 : -14091191626779588548345965455664558981/145219824080883220814330893091679372000 : 1)To make a parametrisation of C one can use the intrinsic Parametrisation to create a map of schemes from a line to C. Note that if a domain for the parametrisation map is not included among the arguments, one will created in the background. It will not have names for its coordinate functions assigned which is why we do that before viewing the map.
> param := Parametrization(C);
> P1<u,v> := Domain(param);
> param;
Mapping from: Prj: P1 to Prj: P
with equations : 331066858679475709/547218109724996625*u^2 +
7818637608975100997/4377744877799973000*u*v +
5018789416884679073/2553684512049984250*v^2
277276767171226/18635910857507625*u^2 + 21011580741373777/8696758400170225*u*v -
290296649205421/1461640067255500*v^2
u^2 - 9618825/1537157*u*v - 19230346/1537157*v^2
> a := Random(-10, 10);
> b := Random(-10, 10);
> point := param(P1 ! [a,b]);
> point in C;
true
> IsReduced(C!point);
false
Next, we define the conic Caff as before
and see that it has a reduced projective solution
as well as a reduced affine solution.
> A<x2,y2> := AffineSpace(Integers(),2); > Caff := Conic(A, 171*x2^2 - 758*x2*y2 + 213*x2 + 399*y2^2 - 731*y2); > HasReducedPoint(Caff); true > ReducedProjectiveSolution(Caff); (129467/63213 : 621/1109 : 1)Notice how the reduced projective solution is a point on ProjectiveClosure(Caff). This projective curve has not had its coordinate functions assigned names so the display below denotes the ith coordinate function by the notation $.i. We then assign these names to clarify any further printing.
> Parent(ReducedProjectiveSolution(Caff)); Set of points of Conic over Integer Ring defined by 171*$.1^2 - 758*$.1*$.2 + 213*$.1*$.3 + 399*$.2^2 - 731*$.2*$.3 with coordinates in Rational Field > Cproj<X2,Y2,Z2> := ProjectiveClosure(Caff); > HasReducedAffinePoint(Caff); true > ReducedAffineSolution(Caff); (129467/63213, 621/1109) > Parent(ReducedAffineSolution(Caff)); Set of points of Conic over Integer Ring defined by 171*x2^2 - 758*x2*y2 + 213*x2 + 399*y2^2 - 731*y2 with coordinates in Rational Field > Parent(Solution(Caff)); Set of points of Conic over Integer Ring defined by 171*X2^2 - 758*X2*Y2 + 213*X2*Z2 + 399*Y2^2 - 731*Y2*Z2 with coordinates in Rational Field
> Z := Integers(); > A<x, y> := AffineSpace(Z, 2); > g := -1954*x*y - 589*x - 788*y^2 - 808*y; > Caff := Conic(A, g); > Caff; Conic over Integer Ring defined by -1954*x*y - 589*x - 788*y^2 - 808*y > HasReducedPoint(Caff); true > ReducedProjectiveSolution(Caff); (1 : 0 : 0) > HasReducedAffinePoint(Caff); false > p := Solution(Caff); > p; (1 : 0 : 0) > Caff; Conic over Integer Ring defined by -1954*x*y - 589*x - 788*y^2 - 808*y with Legendre form: 1166*x^2 - 1112980814*y^2 + 626703937540700 with reduced form: x^2 - y^2 + 7655469778Notice on the last line how various normal forms for the conic have been computed in the background by the point finding algorithm. [Next][Prev] [Right] [Left] [Up] [Index] [Root]