EliminationOrder: SeqEnum           Default: [ ]

    LinearElimination: SeqEnum          Default: [ ]

    ResultantElimination: SeqEnum       Default: [ ]

    FactorizationInResultant: BoolElt   Default: true

    LiftingBound: RngIntElt             Default: 10

    DegreeBound: RngIntElt              Default: 32

    OptimizeFieldRep: BoolElt           Default: false

    DegreeList: SeqEnum                 Default: [ ]

    LiftingBound: RngIntElt             Default: 10

    DegreeBound: RngIntElt              Default: 32

    DegreeList: SeqEnum                 Default: [ ]

Example Scheme_ec-large-int-pts (H119E77)

This example follows an idea of Elkies to construct "large" integral points on elliptic curves. Let X, Y, A, B be polynomials in t, and let Q(t) be quadratic. The idea is that Q(t)Y(t)²=X(t)³ + A(t)X(t) + B(t) will have infinitely many specialisations with Q(t) square (via solving a Pell equation), and thus yield, perhaps after scaling to clear denominators, integral points on the resulting curves. If the degree of A, B is small enough compared to that of X, the resulting specialisation will be quite notable. However, one must avoid the cases where the resulting discriminant 4A(t)³ - 27B(t)² is zero, as these points do not yield an elliptic curve. It turns out that such points contribute a positive-dimensional component to the solution space, and we simply want to ignore such solutions in general.

The first case of interest is when the degrees of (X, Y, A, B) are (4, 5, 0, 1), solved by Elkies in 1988. One way of parametrising this, taking into account possible rational changes of the t-variable to simplify the system, is: X(t)=t⁴ + t³ + x₂t² + x₁t + x₀, Q(t)=t² + q₁t + q_, 0 Y(t)=t⁵ + y₃t³ + y₂t² + y₁t + y₀, A(t)=a₀, B(t)=b₁t + b₀. Then we get 12 equations from requiring that the 0th to 11th degree coefficients of X³ + AX + B - QY² all vanish. It turns out that the desired solution is rational in this case, so that (almost) any prime will suffice. The solution can then be lifted -- as a final step (particular to this problem), one would have to scale the resulting point so as to ensure that Q(t) represents squares.

> K := Rationals();
> R<a0,b0,b1,q0,q1,x0,x1,x2,y0,y1,y2,y3> := PolynomialRing(K,12);
> _<t> := PolynomialRing(R);
> X := t^4+t^3+x2*t^2+x1*t+x0; Y := t^5+y3*t^3+y2*t^2+y1*t+y0;
> Q := t^2+q1*t+q0; A := a0; B := b1*t+b0;
> L := X^3+A*X+B-Q*Y^2;
> COEFF:=[Coefficient(L,i) : i in [0..11]];
> S := Scheme(AffineSpace(R),COEFF);

For this example, we simply call IsolatedPointsFinder directly. Alternatively, we could first use LinearElimination if desired.

> PTS:=IsolatedPointsFinder(S,[13]); PTS; // 13 is a random choice
[* [ 11, 1, 7, 6, 3, 1, 6, 11, 0, 3, 4, 2 ] *]
> b, sol := IsolatedPointsLifter(S,PTS[1]); sol;
(216513/4096, -3720087/131072, 531441/8192,
 11/4, 3, 311/64, 61/8, 9/2, 715/64, 165/16, 77/16, 55/8)
> _<u>:=PolynomialRing(Rationals());
> X := Polynomial([Evaluate(c,Eltseq(sol)) : c in Coefficients(X)]);
> Y := Polynomial([Evaluate(c,Eltseq(sol)) : c in Coefficients(Y)]);
> Q := Polynomial([Evaluate(c,Eltseq(sol)) : c in Coefficients(Q)]);
> A := Evaluate(A,Eltseq(sol));
> B := Polynomial([Evaluate(c,Eltseq(sol)) : c in Coefficients(B)]);
> assert X^3+A*X+B-Q*Y^2 eq 0;
> Q; // note that Q does not represent any squares, but 2*Q(1/2)=9
u^2 + 3*u + 11/4
> B; // also need to clear 2^17 from denominators
531441/8192*u - 3720087/131072
> POLYS := [2^7*X, 2^9*Y, 2^3*Q, 2^14*A, 2^21*B]; // 2^21 in each term
> [Evaluate(f,u/2) : f in POLYS];
[
    8*u^4 + 16*u^3 + 144*u^2 + 488*u + 622,
    16*u^5 + 440*u^3 + 616*u^2 + 2640*u + 5720,
    2*u^2 + 12*u + 22,
    866052,
    68024448*u - 59521392
]

As noted by Elkies, one can clean up the final form of the solution if desired, via rational transformations of the u-variable. Since Q(1)=2 + 12 + 22=36, the theory of the Pell equation tells us that there are infinitely many integers u such that Q(u) is integral, and these all give integral points on a suitable elliptic curve.

There are only four choices of (X, Y, A, B) degrees that give the "largest" possible integral points via this method. The second case, of degrees (6, 8, 1, 1) has a solution over a quartic number field, and the third case, of degrees (8, 11, 1, 2) has a nonic solution. Both of these were found by the methods of this section, the former taking only a couple of minutes.

Example Scheme_halls-conjecture (H119E78)

Another application of the isolated points routine is to compute Belyi maps, one instance of which is in finding solutions to a polynomial version of Hall's conjecture, concerning how small the degree of X(t)³ - Y(t)² can be (if the difference is nonzero). The result is that the degree must be at least 1 + (deg)(X)/2, and there are (up to equivalence) finitely many polynomials of that degree, the count of which can be described in terms of some combinatorics, or in terms of simultaneously conjugacy classes of cycle products of given types in a symmetric group.

In this example, we compute the solution for the case where X has degree 12. It turns out that there are 6 solutions in this case, lying over a sextic number field (we of course ignore "solutions" with X(t)³=Y(t)², though similar to the previous example, they contribute a positive-dimensional component of the solution set). The finding of a suitable local point is not particularly easy, so we just note that X(t) ≡ t¹² + 14t¹⁰ + 14t⁹ + 9t⁸ + 6t⁷ + 4t⁶ + 7t⁵ + 6t⁴ + 15t³ + 7t² + 3t + 10 gives a solution modulo 17, with Y(t) being (of course) the approximate square root of X(t)³. We shall lift this in a way that keeps the t¹¹ as zero and the t⁹ and t¹⁰ coefficients as equal (these are from preliminary transformations of the t-parameter that can be applied to the system).

As noted above, it might be easier to remove the y-variables "by hand", and then undo the linear eliminations in the resulting sextic number field. We chose here to work directly. A theorem of Beckmann says that the number field we obtain can only be ramified at primes less than 36.

> SetVerbose("IsolatedPoints",1);
> XVARS := ["x"*IntegerToString(n) : n in [0..9]];
> YVARS := ["y"*IntegerToString(n) : n in [0..17]];
> P := PolynomialRing(Rationals(),28);
> AssignNames(~P,XVARS cat YVARS);
> _<t> := PolynomialRing(P);
> Y := &+[P.(i+11)*t^i : i in [0..17]]+t^18;
> X := &+[P.(i+1)*t^i : i in [0..9]]+(P.10)*t^10+t^12;
> Xpt := [GF(17)|10,3,7,15,6,7,4,6,9,14];
> pt := Xpt cat [0 : i in [11..28]];
> FF := GF(17); _<u> := PolynomialRing(FF);
> Xv := Polynomial([FF!Evaluate(c,pt) : c in Coefficients(X)]);
> Xv3 := Xv^3; Yv := u^18;
> for d:=17 to 0 by -1 do // ApproximateSquareRoot
>     Yv:=Yv+Coefficient(Xv3,d+18)/2*u^d; Xv3:=Xv^3-Yv^2; end for;
> Yv^2-Xv^3; // must be degree 7 or less
8*u^7 + 11*u^5 + 10*u^4 + 3*u^3 + 3*u^2 + 11*u + 4
> pt := Xpt cat [Coefficient(Yv,d) : d in [0..17]];
> SYS := [Coefficient(X^3-Y^2,d) : d in [8..35]]; // 28 vars
> S := Scheme(AffineSpace(P),SYS);
> b, sol := IsolatedPointsLifter(S,pt : LiftingBound:=12, DegreeBound:=10);
> K := OptimisedRepresentation(Parent(sol[1]) : PartialFactorisation); K;
Number Field with defining polynomial
  y^6 - y^5 - 60*y^4 - 267*y^3 - 514*y^2 -  480*y - 180 over the Rationals
> Factorization(Discriminant(Integers(K)));
[ <2, 2>, <5, 1>, <13, 1>, <29, 5> ]

An alternative of completing the computation is to first use LinearElimination before applying IsolatedPointsLifter. In any event, the computation of the local point (which we simply assumed to be given) would be the dominant part of the running time.

> mp := LinearElimination(S); // a few seconds to evaluate scheme maps
> rmp := // reduced map
>  map<ChangeRing(Domain(mp),GF(17))->ChangeRing(Codomain(mp),GF(17))
>     | DefiningEquations(mp),DefiningEquations(Inverse(mp)) : Check:=false>;
> PT := Inverse(rmp)(Codomain(rmp)!(pt));

The IsolatedPointLifter can now be called on Domain(mp) and Eltseq(PT) (with varargs if desired), and then the result can be mapped back to the original scheme S via mp. It is a bit hairy to do this directly, as scheme maps do not naturally deal with finite field inputs in all cases. Due to the way that IsolatedPointsLifter uses to choose which coordinate to try to recognise first, it could also be slower in the end.

Example Scheme_random-linear-scheme (H119E79)

Here is an example where finding the common field is quite difficult, but finding minimal polynomials for all the coordinates is rather easy. First, a somewhat generic random scheme in (P)³ is chosen, such that each variable appears no more than linearly. This has degree less than 4!, and in the example chosen, it has degree 22. Then two local points are found modulo 5. These are then passed to the lifting function, which returns the desired solution.

> P<w,x,y,z> := AffineSpace(Rationals(),4);
> f1 := w*x*y - 6*w*x - 7*w*y*z + w*y - 6*w*z - 3*x*y + y + 6*z;
> f2 := 10*w*x*y*z - 4*w*y*z + 2*w*y - 9*w - x*y*z - 10*x*z + y*z - 7*y;
> f3 := 10*w*x*y*z - 6*w*x*y + 8*w*x*z - 4*w*y*z - 6*w*z - x*z + 9*x + 8*y;
> f4 := 6*w*x*y*z + 3*w*x*z + 19*w*y*z - 7*w*z + 8*x*y*z - 2*x*z + 6;
> S := Scheme(P,[f1,f2,f3,f4]);
> SetVerbose("IsolatedPoints",1);
> PTS := IsolatedPointsFinder(S,[5]);
> Degree(S);
22
> b,POLYS := IsolatedPointsLiftToMinimalPolynomials
>                    (S,PTS[1] : DegreeBound:=22,LiftingBound:=10);
> POLYS[1];
18124035687220989600*x^22 + 62977055844929678832*x^21 +
 65273363651442356128*x^20 + 81271204075826455992*x^19 +
 130701369600138969680*x^18 - 285376384061267841622*x^17 -
 802166956118815471654*x^16 + 253325444790327996845*x^15 -
 1266591733002155213172*x^14 + 25113861844403230090*x^13 +
 506530967406804631482*x^12 - 1323179973699695447463*x^11 +
 1605685921502538803112*x^10 - 1318315736155520576802*x^9 +
 949649129582958459958*x^8 - 527441332544171338490*x^7 +
 254463684049866607512*x^6 - 100039189198577581440*x^5 +
 26014411295686475856*x^4 - 3177984195514332576*x^3 -
 1852946687180290752*x^2 + 971825485320437760*x - 88506566917263360

All of the four polynomials in POLYS look approximately like this, and all should determine the same field, but it is difficult to find suitable isomorphisms between them, let alone find an OptimisedRepresentation.

In fact, the Gröbner basis machinery is superior for this purpose. Writing one of the coordinates in terms of the other (so as to get the field generators in terms of each other) would necessitate quite high precision in the p-adic lifting to recognise the coefficients, likely 5^(2¹⁴) or more (this takes about 5 minutes). The Gröbner basis method, which recognises one coordinate and then back-substitutes into the resulting equations, solving them algebraically, takes only about 15 seconds.

> time V := Variety(Ideal(S),AlgebraicClosure()); // about 15s
> MinimalPolynomial(V[22][4]); // deg 22, all coeffs about 25 digits
y^22 - 70869414518205839537/14232439756116709952*y^21 -
    6067542586100223488373/56929759024466839808*y^20 + [...]
    [...] + 166661449939161/1779054969514588744
> MinimalPolynomial(V[22][3]); // deg 22, all coeffs about 25 digits
y^22 - 428567519465749893/68067993818308256*y^21 -
    22959295396880059615/1089087901092932096*y^20 + [...]
    [...] + 2469165405490441431/68067993818308256
> V[22][4]; // given simply as r22, all 22 conjugates are found
r22
> V[22][3]; // third coordinate in terms of the fourth
[output takes about 200 lines, involving 750-digit coordinates]

Another way to achieve the result is to plug the known coordinate into the system, and use Gröbner bases (or resultants, if possible) to solve it.

> K := NumberField(POLYS[1]); // first coordinate
> _<xx,yy,zz> := PolynomialRing(K,3);
> E := [Evaluate(e,[K.1,xx,yy,zz]) : e in DefiningEquations(S)];
> Variety(Ideal(E)); // about 2 seconds
[again a rather bulky output]

Both of these uses of Gröbner bases are somewhat specific to the simplicity of the case here, and in more difficult cases would likely be rather onerous. This example does exemplify that for a generic variety the Gröbner basis methods should be superior. The lifting methods are largely for cases where the problem has special structure.

Example Scheme_mathieu-monodromy (H119E80)

Here is an example from N. D. Elkies of a polynomial f(x)∈K(x) for which f(x) - t appears to have Galois group M₂₃ over K(t) (this is sometimes called the monodromy group of f). This involves trying to find f=P₃P₂²P₄⁴=P₇P₈² - c for some polynomials P_d of degree d, for some constant c. Upon suitable reductions, one gets a system of 8 variables and equations. With a few additional considerations, the search space can be reduced a bit further. As noted by M. Zieve, the equation should have 4 solutions, and thus likely be in a quartic field K that is an extension of (Q)(Sqrt( - 23)). This is indeed the case.

> Q := Rationals();
> R<a2,c,b1,b2,c1,c2,c3,c4,d1,d2,d3,d4,d5,d6,d7,
>   e1,e2,e3,e4,e5,e6,e7,e8> := PolynomialRing(Q,(3-1)+2+4+7+8);
> _<t> := PolynomialRing(R);
> P3 := t^3 + a2*t + a2/(26/-27); // normalisation
> P2 := t^2 + b1*t + b2;
> P4 := t^4 + c1*t^3 + c2*t^2 + c3*t + c4;
> P7 := t^7 + d1*t^6 + d2*t^5 + d3*t^4 + d4*t^3 + d5*t^2 + d6*t + d7;
> P8 := t^8 + e1*t^7 + e2*t^6 + e3*t^5 + e4*t^4 +
>             e5*t^3 + e6*t^2 + e7*t + e8;
> Q := P3 * P2^2 * P4^4 - P7 * P8^2 - c;
> S := Scheme(AffineSpace(R),Coefficients(Q));
> SetVerbose("IsolatedPoints",1);
> v:=[GF(101) | 26, 1,  -26,21,  -19,-27,-22,8, // known point
>              -14,12,26,-3,-37,-43,-22,  44,-11,-13,-21,45,-45,32,46];
> b, pt := IsolatedPointsLifter
>           (S,v : DegreeList:=[4], LiftingBound:=15, OptimizeFieldRep);
> K := Parent(pt[1]);
> DefiningPolynomial(K);
y^4 - 2*y^3 - 10*y^2 + 11*y + 36
> Factorization(Discriminant(Integers(K)));
[ <3, 1>, <23, 3> ]

The above code lifts the given point to precision 101^(2¹¹), and recognises it in the field K. Next we can compute the polynomial f(x) in question, and see that reductions (modulo 269, say) of f(x) - i do indeed correspond to cycle structures of M₂₃. However, to prove that this really is the Galois group (over the function field) seems to require a more difficult monodromy calculation.

A more theoretical (topological) construction was given by P. Müller in 1995, but did not explicitly produce f. It is also still an open question whether there is a polynomial over the rationals with Galois group M₂₃.

> X := P3 * P2^2 * P4^4;
> f := Polynomial([Evaluate(e,Eltseq(pt)) : e in Coefficients(X)]);
> p := 269;
> P := Factorization(p * Integers(K))[1][1]; assert Norm(P) eq p;
> _, mp := ResidueClassField(P);
> fp := Polynomial([mp(c) : c in Coefficients(f)]);
> D := [[Degree(u[1]) : u in Factorization(fp-i)] : i in [1..p]];
> Sort(SetToSequence(Set([Sort(d) : d in D | &+d eq 23])));
[
    [ 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2 ],
    [ 1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3 ],
    [ 1, 1, 1, 2, 2, 4, 4, 4, 4 ],
    [ 1, 1, 1, 5, 5, 5, 5 ],
    [ 1, 1, 7, 7, 7 ],
    [ 1, 2, 2, 3, 3, 6, 6 ],
    [ 1, 2, 4, 8, 8 ],
    [ 1, 11, 11 ],
    [ 2, 7, 14 ],
    [ 3, 5, 15 ],
    [ 23 ]
]
> load m23; // G is M23
> C := [g : g in ConjugacyClasses(G) | Order(g[3]) ne 1];
> S := Set([CycleStructure(c[3]) : c in C]);
> Sort([Sort(&cat[[s[1] : i in [1..s[2]]] : s in T]) : T in S]);
[
    [ 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2 ],
    [ 1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3 ],
    [ 1, 1, 1, 2, 2, 4, 4, 4, 4 ],
    [ 1, 1, 1, 5, 5, 5, 5 ],
    [ 1, 1, 7, 7, 7 ],
    [ 1, 2, 2, 3, 3, 6, 6 ],
    [ 1, 2, 4, 8, 8 ],
    [ 1, 11, 11 ],
    [ 2, 7, 14 ],
    [ 3, 5, 15 ],
    [ 23 ]
]