|
There is now experimental code to try to find isolated points of
schemes in (A)(Q)n that are defined by n or more equations.
There is no restriction that the scheme itself must be of dimension 0,
and in many applications, there is an uninteresting (or degenerate)
variety of positive dimension, with the isolated points being the ones
of interest.
The first technique to do this is to find points locally modulo
some prime, at which the Jacobian matrix is of maximal rank.
A separate procedure then lifts such points via a Newton method,
and tries to identify them (via LLL) in a number field.
If the degree is known (or suspected), this information can be
passed to the lifting function, and otherwise it will try a generic
method that applies LLL for degrees 3.2n and 4.2n
as n increases, expecting to catch other solutions via a factorization
into a smaller field (for instance, a degree 6 solution will show up in
degree 8 as the expected minimal polynomial multiplied by a more-or-less
random quadratic one).
The running time of such a process is often dominating by the
searching for local points, and so various methods can be used
to pre-condition the system. Firstly, variables which appear
as a linear monomial in one of the equations can be (iteratively)
eliminated. Already it is not clear what the best order is, so the
user can specify it. In given examples, it is not untypical for later
steps to take 10 times as long due to a different choice of eliminations,
so some experimenting with this parameter can be useful.
Secondly, resultants can be used to try to eliminate
more variables, perhaps concentrating on those which appear to a small
degree in the equations. By default, if a variable appears to degree 2
or less in all the equations, a resultant step will be applied. The
resulting equations can be quite complicated (taking many megabytes to
represent them), but it is still often faster to loop over pV - 1
possible local points compared to pV. The resultants can introduce
extraneous solutions, which are checked when undoing the modifications
to the system of equations.
An error can occur if the variable elimination reduces the number of
equations below the dimension.
Another concern for running time is in the order of the above operations.
For instance, computing the resultants can be time-consuming in some examples,
and perhaps doing so modulo p for the primes of interest might be a superior
method in some cases. A second example is that recognising points over
the number fields in question might be faster with a reduced system and
then undoing the resultants and linear eliminations in the number field,
though the lifting might be slower in that case. The algorithm as implemented
tries to handle the general case well.
Note that the scheme given to the IsolatedPoints routines might also
have components of positive dimension, but the techniques here will
only work to find the points that do not lie on them.
EliminationOrder: SeqEnum Default: [ ]
Given a scheme, iteratively eliminate variables that appear strictly
linearly (that is, as a monomial times a constant) in some equation.
The EliminationOrder vararg allows an ordering to be specified.
The results can vary drastically when the order is changed.
The returned value is a map from the resulting scheme to the input scheme,
with an inverse.
LinearElimination: SeqEnum Default: [ ]
ResultantElimination: SeqEnum Default: [ ]
FactorizationInResultant: BoolElt Default: true
Given a affine n-dimensional scheme defined over the rationals
by at least n equations, and a sequence of primes, try to find
liftable points of the scheme modulo the primes.
The variables given in the LinearElimination vararg will
be eliminated in that order. If this is non-empty, an automatic procedure
will be applied. Similarly with ResultantElimination.
Finally, by default, computed resultants have SquarefreeFactorization
applied to them (and repeated factors removed), and this can be turned off.
LiftingBound: RngIntElt Default: 10
DegreeBound: RngIntElt Default: 32
OptimizeFieldRep: BoolElt Default: false
DegreeList: SeqEnum Default: [ ]
Given a affine n-dimensional scheme defined over the rationals
by at least n equations,
and a sequence of finite field elements giving a point (on the scheme) whose
Jacobian matrix is of maximal rank,
attempt to lift the point via a Newton method and
recognise it over a number field. The function returns false if a point
was not found, and else returns both true and the point that was found.
The LiftingBound vararg determines how many lifting steps to use,
with the default being 10, so that approximately precision p^(210)
is obtained. The DegreeBound is a limit on how high of a degree of
field extension to check for solutions. The method used only checks
for some of the degrees via LLL, as usually smaller degrees will show
up in factors. The DegreeList vararg can also be used for this,
perhaps when the degree of the solution in question is known.
The practical limit is likely around 50 in the degree.
Finally, there is the OptimizeFieldRep boolean vararg, which
determines whether the number field obtained will have its
optimised representation computed.
LiftingBound: RngIntElt Default: 10
DegreeBound: RngIntElt Default: 32
DegreeList: SeqEnum Default: [ ]
This works as with IsolatedPointsLifter, but instead of trying to
find a common field containing all the coordinates, simply returns a minimal
polynomial for each one.
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) 2=X(t) 3 + 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) 3 - 27B(t) 2 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)=t4 + t3 + x2t2 + x1t + x0, Q(t)=t2 + q1t + q_, 0
Y(t)=t5 + y3t3 + y2t2 + y1t + y0, A(t)=a0, B(t)=b1t + b0.
Then we get 12 equations from requiring that the 0th to 11th
degree coefficients of X3 + AX + B - QY2 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.
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) 3 - Y(t) 2
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)3=Y(t)2,
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) ≡ t12 + 14t10 + 14t9 + 9t8 + 6t7 + 4t6 + 7t5 + 6t4 + 15t3 + 7t2 + 3t + 10
gives a solution modulo 17, with Y(t) being (of course) the approximate
square root of X(t)3.
We shall lift this in a way that keeps the t11 as zero and the t9
and t10 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.
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) 3 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^(214) 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.
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 23 over K(t)
(this is sometimes called the monodromy group of f).
This involves trying to find f=P 3P 22P 44=P 7P 82 - 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^(211), 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 M23.
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 M23.
> 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 ]
]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|