// Determine rational n-cycles under z |--> z^2 + c
// ================================================
//
// I.e., pairs of rational numbers (z,c) such that
// with z_0 = z, z_{m+1} = z_m^2 + c,
// we have z_0, z_1, ..., z_{n-1} distinct and z_n = z_0.
//
// For example, (0, 0) gives a rational 1-cycle,
// (0, -1) gives a rational 2-cycle 0 |-> -1 |-> 0, ...
//
// See Flynn, Poonen and Schaefer: Cycles of quadratic polynomials ...
// Duke Math. J. 90 (1997)
// and references given there.
//
// Michael Stoll, Goettingen, July 2006
//
// NOTE: The code below works with version 2.13-1
//
//======================================================================
//
// Set up polynomial ring in two variables z,c
P2zc := PolynomialRing(Rationals(), 2);
//
// Find the first few iterates of f : z |--> z^2 + c
iterates := [i eq 0 select z else Self(i)^2 + c : i in [0..6]];
iterates[1];
iterates[2];
iterates[3]; // and so on.
//
// The condition that z_n = z_0 = z means iterates[n+1] - z = 0.
// So for 1-cycles, we get the relation between z and c given by
g1 := iterates[2] - z; g1;
//
// This obviously describes a conic in the affine (z,c)-plane,
// which we can parametrize by z |--> (z, z-z^2)
//
// For 2-cycles, we have iterates[3] = z, but this is also satisfied
// for 1-cycles, so we have to divide by g1.
g2 := ExactQuotient(iterates[3] - z, g1); g2;
//
// This is again a conic, which is trivially parametrized by
// z |--> (z, -z^2-z-1).
//
// For 3-cycles, we get in the same way
g3 := ExactQuotient(iterates[4] - z, g1); g3;
//
// This is not so easily recognized,
// so we use Magma's plane curves machinery.
// We first have to set up the ambient space, here it is an affine plane.
Aff2 := AffineSpace(P2zc);
//
// Then we turn our equation into an affine curve.
C3 := Curve(Aff2, g3); C3;
//
// Now we can ask Magma for its genus.
Genus(C3);
//
// So despite its complex appearance, it is a genus 0 curve.
// If it has a rational point, then we can again parametrize all the
// rational points.
//
// For this, we need one (nonsingular) rational point on C3.
// We can use the new PointSearch function for finding one,
// but first we have to turn our affine curve into a projective one.
C3p := ProjectiveClosure(C3);
Pr2 := Ambient(C3p); // to set the names of the coordinates
PointSearch(C3p, 100 : OnlyOne);
pt := $1[1];
Pr1__ := ProjectiveSpace(Rationals(), 1);
L := Curve(Pr1);
Parametrization(C3p, Place(pt), L); // should really work without "Place"
//
// Another possibility is to first transform the curve into a conic.
Co3, phi1 := Conic(C3p);
// Check if the conic has a rational point:
HasPoint(Co3);
// Parametrize it:
phi2 := Parametrization(Co3, L);
// Compose maps to get parametrization of C3:
time phi3 := Expand(phi2*phi1^-1);
phi3 : Minimal;
def := DefiningPolynomials(phi3);
// Make them a bit nicer:
def := [ExactQuotient(f, g) : f in def] where g := GCD(def);
def;
// the following shows that this parametrization is rather nice
[Factorization(pol) : pol in def];
// use this to define the parametrization
par := map C3p | def>;
// Note that the fact that Magma accepts this input shows that the
// polynomials in def really define a parametrization of C3p!
//
// Now we can generate examples...
{par(L![a,b]) : a, b in [-2..2] | GCD(a,b) eq 1};
{C3!pt : pt in $1 | pt[3] ne 0};
//
// =====================================================================
//
// Let us move on to n=4. Here, we have to remove 1-cycles and 2-cycles
// from the equation.
g4 := ExactQuotient(iterates[5] - z, g1*g2); g4;
//
// What is its genus?
C4 := Curve(Aff2, g4);
time Genus(C4);
//
// So this is a genus 2 curve and therefore must have a model of the form
// y^2 = F(x) with F of degree 5 or 6.
// In particular, it is a hyperelliptic curve.
// Magma has a built-in command that converts a curve into a
// hyperelliptic model.
time flag, H4, mC4H4 := IsHyperelliptic(C4 : Eqn); // Eqn: compute model
flag; // just to be sure...
H4;
// (This happens to be X_1(16)...)
//
// To answer the original question, we need to find the set of rational
// points on H4.
//
// We can first do a simple search for points.
ptsH4 := Points(H4 : Bound := 1000); ptsH4;
//
// What are the corresponding points on C4?
[ pt @@ mC4H4 : pt in ptsH4 ]; // ==> error message related to weighted P^2
// So we have to do this in a more pedestrian way, by solving algebraic
// equations.
def := DefiningPolynomials(mC4H4); def;
// note that def[3] = 1
[Variety(ideal)
: pt in ptsH4 | pt[3] ne 0];
//
// so there are no _affine_ points on C4 that map to the points we found
// on H4.
//
// It remains to prove that the list of points on H4 is already complete.
//
// To do this, we will use information on the Mordell-Weil group of
// the Jacobian of H4. So we first construct the Jacobian.
J4 := Jacobian(H4);
//
// Next, we have to find the rank of the MW group.
// A bound for the rank is obtained through 2-descent.
time RankBound(J4);
// The value is zero; this proves that the MW rank is zero.
// (In general, this gives an upper bound on the rank.)
//
// So J4(Q) is just the torsion subgroup. Let us determine what it is.
TorsionSubgroup(J4);
//
// Now, using a suitable map of H4 into J4, we can easily find the set
// of rational points on H4. It is still simpler to use a function
// provided for that purpose.
Chabauty0(J4);
$1 eq ptsH4;
//
// So we have indeed found all points and proved the following.
// THEOREM. There are no rational 4-cycles under z |--> z^2 + c.
//
//======================================================================
//
// What about n = 5?
//
g5 := ExactQuotient(iterates[6] - z, g1); g5;
C5 := Curve(Aff2, g5);
// time Genus(C5); // takes a while, so we don't do it here
// result is 14
//
// This genus is too large to allow direct computations with C5.
//
// So what can we do?
//
// Note that we have an action of the cyclic group Z/5Z on C5, given by
// the map we iterate: (z, c) |--> (z^2+c, c).
// We can hope to get a curve we can more easily deal with by dividing
// by this action.
// We find the quotient by setting up a suitable map and asking for its
// image.
mC5D5 := map Aff2 | [&+[iterates[i] : i in [1..5]], c]>;
D5 := Image(mC5D5); D5;
Genus(D5);
// So we are back in business!
//
time flag, H5, mD5H5 := IsHyperelliptic(D5 : Eqn);
H5;
//
// Now the model H5 is not particularly nice,
// so let us find a better one.
M5, mH5M5 := ReducedMinimalWeierstrassModel(H5); M5;
//
// For further compuations, it is better to remove the y terms.
S5, mM5S5 := SimplifiedModel(M5); S5;
//
// Now we can again look for points.
ptsS5 := Points(S5 : Bound := 1000); ptsS5;
//
// Let us try to move them back to D5.
ptsM5 := {@ pt @@ mM5S5 : pt in ptsS5 @}; ptsM5;
ptsH5 := {@ pt @@ mH5M5 : pt in ptsM5 @}; ptsH5;
//
// Now we would run into the same bug as before, so use the work-around:
fx,fy,fz := Explode(DefiningPolynomials(mD5H5)); fx;fy;fz;
h5 := DefiningPolynomial(D5);
// be careful to use the grading (1,3,1) of the ambient P^2 of H4!
[Variety(ideal)
: pt in ptsH5];
ptsD5 := &join[{@ D5![pt[1],pt[2]] : pt in a @} : a in $1]; ptsD5;
// (-1,-4/3) is a singularity; the map is not defined there:
Points(BaseScheme(mD5H5));
Points(SingularSubscheme(D5));
//
// Check if one of these points lifts to C5.
// Note that pt @@ mC5 here will return a scheme, so we have to ask
// for its points.
[Points(pt @@ mC5D5) : pt in ptsD5];
// So, no point lifts.
//
// It remains to show that we really have found all points on S5 (say).
//
// So we again find the Mordell-Weil group.
J5 := Jacobian(S5);
time RankBound(J5);
//
// The rank bound is 1, and by standard conjectures (which imply that
// the difference between the bound and the actual rank is even), the
// rank has to be 1.
// We can find a point of infinite order to prove this:
ptJ := J5![ptsS5[1], ptsS5[2]]; ptJ;
Order(ptJ);
//
// We need the full group J5(Q). First check the torsion.
TorsionSubgroup(J5);
// ==> no torsion.
//
// So J5(Q) is isomorphic to Z, and we need to find a generator.
// Let us look for some small points on J5.
ptsJ5 := Points(J5 : Bound := 10); ptsJ5;
//
// The following finds a basis of the group they generate.
time ReducedBasis(ptsJ5);
a,b := $1;
gen := a[1]; ht := b[1,1]; // b is a matrix!
//
// So most likely, this point generates the MW group.
// Let us prove this!
// If gen is not a generator, then it is a multiple of the generator,
// whose canonical height therefore is at most ht/4.
// Now we can get a bound on the difference between naive and canonical
// height, as follows.
bd := HeightConstant(J5 : Effort := 2); bd;
//
// This is logarithmic, so the bound for the search is
sbd := Floor(Exp(ht/4 + bd)); sbd;
//
// We need to find all points up to that naive height on J5 and check
// that they all are multiples of gen.
ptsJ5 := Points(J5 : Bound := sbd);
ptsJ5 diff {@ n*gen : n in [-10..10] @};
// OK. We have shown that J5(Q) = .
//
// Since J5(Q) is infinite, we cannot use the simple trick that worked
// for n=4.
// However, since the rank (1) is less than the genus (2), we can use
// Chabauty's method.
BadPrimes(S5);
S5F3 := ChangeRing(S5, GF(3));
Points(S5F3);
// We have to show that the first two points lift to one rational point
// each and that the other two points lift to two rational points each.
//
// There is a regular differential omega on the curve over Q_3
// whose image on the Jacobian kills the Mordell-Weil group.
// (I.e., the integral of omega from 0 to P vanishes for any P in J5(Q).)
// We can find it mod 3 by looking at the image on the Kummer Surface
// of a multiple of the generator that is in the kernel of reduction.
J5F3 := Jacobian(S5F3);
Order(J5F3!gen);
KummerSurface(J5)!($1*gen);
// The first three coordinates, when divided by 3^2 and reduced mod 3,
// are the coefficients a,b,c of a quadratic polynomial a x^2 - b x + c,
// which is a square.
Factorization(PolynomialRing(GF(3))![(-1)^(i-1)*$1[i]/g : i in [1..3]]
where g := GCD([Integers()|$1[1],$1[2],$1[3]]));
// Here, it is (x-1)^2 mod 3.
// The differential mod 3 is then omega = (x-1) dx/y.
// Since omega does not vanish at the first two points (at infinity),
// they can lift to at most one rational point each.
// At the other two points, omega vanishes to first order.
// When the residue characteristic is 5 or more, this implies that each
// of them can lift to at most two rational points.
// Since here p = 3, we have to look more carefully.
// Let t = x-1 be a uniformizer at the point (1,1) (over Q_3).
P := PolynomialRing(Rationals());
f5 := P!HyperellipticPolynomials(S5);
Evaluate(f5, t+1);
// So y^2 = 1 + 6 t + O(t^2), hence y = 1 + 3 t + O(t^2), and
// omega = (t + O(t^3)) dt mod 3.
// The integral on this residue class (with t = 3 T) is then
// c + 3^2 a_0 T + 3^2 T^2 + 3^3 a_2 T^3 + ... ;
// this can have at most two roots in Z_3.
//
// So we have now proved that our list of points on S5, and hence on D5,
// is complete.
//
// Therefore, we have proved another result.
// THEOREM. There are no rational 5-cycles under z |--> z^2 + c.
//
//======================================================================
//
// What about n = 6?
//
// We have to remove cycles of lengths 1, 2, and 3:
g6 := ExactQuotient(iterates[7] - z, g1*g2*g3); g6;
C6 := Curve(Aff2, g6);
// Again, we use the action of Z/6Z to map to a "smaller" curve.
mC6D6 := map Aff2 | [&+[iterates[i] : i in [1..6]], c]>;
D6 := Image(mC6D6); D6;
Genus(D6);
time IsHyperelliptic(D6);
// With current technology, this is beyond what we can do...
// We can look for points on D6, however:
D6p := ProjectiveClosure(D6);
PointSearch(D6p, 1000);
// The last point is interesting:
Evaluate(g6, [t, -71/48]);
Factorization($1);
// The three quadratic factors all define the same number field:
$1[1..3];
[Discriminant(f[1]) : f in $1];
// We get a 6-cycle defined over Q(sqrt(33)).
K := NumberField(t^2 - 33);
Roots(Evaluate(g6, [t, -71/48]), K);
z0 := $1[1,1];
z0^2 - 71/48;
$1^2 - 71/48;
$1^2 - 71/48;
$1^2 - 71/48;
$1^2 - 71/48;
$1^2 - 71/48;
$1 eq z0;
// For all the other points, we get cycles defined over (cyclic)
// sextic number fields.
__