For which values of n is a/b + b/c + c/a = n solvable?
dave rusin@math.niu.edu
originally released 2003/07/22; last modified 2003/08/01
latest version: http://www.math.niu.edu/~rusin/research-math/abcn/
The Diophantine equation of the title has recently been brought to my
attention. For fixed values of n, this equation leads to an elliptic
curve which can be analyzed quickly if n is small (up to about 200, say).
Such an analysis has already been done, by Bremer and Guy (Proc. Edinburgh
Math. Soc. (2) 40 (1997), no. 1, 1--17) so the main value of this
article will be to use the present context as a means to introduce the
reader informally to some heavy-duty mathematics. This is done in the
first two sections of this article; in the last section, the lists of
numbers themselves appear, to answer the title question. The three sections
are:
I. "Some generalities on Diophantine problems" -- explains why one should
feel confident about solving an equation "like" this one. Also
provides background information about Elliptic Curves in particular.
II. "This particular equation" -- explains how the general theory of
Elliptic Curves plays out in this case. In particular, I provide
a detailed listing of the values of n for which the computations
required various types of tricks and assumptions. This includes
providing flags of which results are technically provisional.
It also should enable someone else to duplicate my computations
more rapidly, which could be useful since I sometimes make mis-steaks.
III. "The Lists" -- The values of n, together with a few sets of
solutions that demonstrate the title equation is solvable in each case.
This section can be readily understood with very little familiarity
of the previous sections, if all you want is numbers.
Included here are indications of just what computations
are needed to continue the list past n=200.
In the hope of aiding navigation I have divided this file into (sub)^n-headings
Just to show that all the verbiage that follows is indeed good for
something, let me note that the techniques herein show that the equation
a/b + b/c + c/a = 112
can be solved with explicit integers a,b,c; what appears to be the
simplest solution requires (90+)-digit numbers:
a = 44488222032517984080347242004206223609176772084
4845203037340381653808676781078204185344064777425
b = 180001063934056147663194703762128694791524068
4971323481294582383858472523311320365128373281158
c = -1331809157685411330016283859165784168699351
9959959149070559988026538909081959649861205201860
I am indebted to Allan MacLeod who cracked one of the more challenging
values of n and sent me the results on August 1 2003: When n=142,
an apparently-minimal solution to the title equation -- which happens to
use positive integers only! -- uses these (120+)-digit numbers:
a = 23381593234936372123623332652594607232679953206675800829
14801368818500874833339590707685028055162560266769298444575042876
b = 6472270006492812673719886357710878031344481152384871782008
59980415730790019463760618736457807240738779916233265738309991525
c = 3273877691398828904605661792745624282538951164849869225778
17123390124690992174499099412180521982402624674563255418744783750
Further, I got help from Tom Womack on the case n=177. Using some rather
more sophisticated descent and search tools, that one has been solved too.
A solution, which appears to be minimal(!) has (positive!) (a,b,c) =
445188681860061326821129950666859609205690550347150520111194630556966
436821631047458921363439516505891378648322116770968163708164
401573025159148773984893799821901869771134413368989401077170
2886480926826095375123436035133467353891453356440835740358388069273
117406748241229198230595283470644303272529734480463790129297
393707889262867159886114570461314560454492187347197854308700
126781403816382294735175160947259925023500288103896118531524943372
845798336255598830049585497128339056967473477664040582804720
897007784402845395115328240333301067358938774092489803085043
With all n<=200 now resolved, we have begun turning our CPU power to
a larger range to see what new behaviours await us.
I. Some generalities on Diophantine problems
The material in this section is well known to students of number theory
but may be new to readers whose only reaction to the title
equation would be to try small values of a, b, and c!
IA. The role of dimension
Let's take a broad view of Diophantine problems, to see why the equation
in the title would be considered "easy" by the cognoscenti.
Suppose you are given k equations in m unknowns. Moving the left-
and right-sides together, you can write the solution set V of the
equations as F^{-1} (0) where F : R^m --> R^k is the function
whose components are the expressions which you want to set equal to zero.
If those component functions are differentiable, then under a fairly
mild hypothesis ("full rank", which asserts that the k equations are
"independent"), the Implicit Function Theorem assures us that near almost
every point of V, the solution set looks like (m-k)-dimensional space,
that is, it's a manifold of this dimension. For example, the Pythagorean
equation
x^2 + y^2 - z^2 = 0
has a solution set which is simply a cone through the origin in R^3;
that cone is a (2-dimensional) surface, and 2 equals 3 - 1 (the number of
variables minus the number of equations). There is a bad point at the
origin (a "singularity") where the IFT cannot be applied. Typically there
are few singularities.
The Pythagorean example illustrates a common situation: when the
component functions of F are _homogeneous_, the solution set consists
of entire lines through the origin. Keeping that in mind, it is
sufficient, in such cases, to pay attention to only one point on each
line as a sort of placeholder. For example, every line in R^3 meets
the plane x = 1 at exactly one point, except for the lines in the
y,z plane (where x = 0). So in our Pythagorean example, we can
set x=1 to get the equation 1 + y^2 - z^2 = 0 which, by the
previous paragraph, describes a (1-dimensional) curve; it's the curve we
get by intersecting the cone with the plane x=1, and we can recover the
whole cone by taking the entire line passing through each point of
this curve. (We have to remember to add in the points with x=0, which
obviously add just two more lines, the lines {x=0,y=z} and {x=0,y=-z}.)
It's traditional in this homogeneous setting to think of the whole
cone as consisting as this collection of lines: one for each point on
the hyperbola, plus two more. If all you want to draw is the hyperbola,
that's fine; just remember that each _point_ on the hyperbola corresponds
to a _line_ in the cone; those two extra lines in the cone are thought
of as two additional points on the hyperbola, always called "the points
at infinity".
So this is the perspective from which one can look at a set of equations:
the solution set is (mostly) a manifold of dimension (m-k), and when
the equations are homogeneous we have an extra trick of viewing it as
a manifold of one lower dimension, (m-k-1).
Now, if you want to find _integer_ or _rational_ solutions to the
original equations, you just want points in V whose solutions are
all integers (or rationals). We call them "integer points" (or "rational
points"). In the homogenous case, there's really no difference: every
line through the origin containing a rational point also contains an
integer point.
Here is why the dimension arguments are crucial:
0. When V has dimension 0, we can find all the real points on V
and simply decide whether they are integer/rational or not.
Assuming the equations are _polynomial_ equations, this
process can be made quite algorithmic, and there is no
ambiguity at all in finding all solutions. (It's even _practical_,
as long as you have, say, no more than a half-dozen equations of
very low degree).
1. When V has dimension 1, the solution set is a curve. This is a
very well-studied case. I'll outline the subcases below, but
suffice it to say that there exist procedures which will
very often be able to tell whether there are infinitely many
solutions or only a finite number (including zero) of solutions;
that statement remains true whether you mean _rational_ solutions
or _integral_ solutions. So when you see that a Diophantine
problem leads to a _curve_, take heart!
2. When V has dimension 2, it is sometimes easy to find rational or
even integral solutions, by simply applying the ideas in the
previous paragraph to various curves embedded inside V. For
example, you could look to see whether there are solutions
with two variables equal to each other; that corresponds to
looking for solutions in the curves obtained by intersecting the
surface V with a hyperplane like x = y. Going in the other
direction, though, it is very difficult to prove that no rational
points exist on a surface. Many classic problems in number
theory come down to showing that a certain surface has no rational
points, but we don't have the tools to do that yet! (Examples
include the "rational box" problem, the problem "x^5+y^5=z^5+w^5",
etc.) So when you see that a Diophantine problem leads to a
_surface_, be very nervous!
3. When V has dimension 3 or more, it's usually pretty easy to
find rational solutions. That's not a theorem, but it's my
experience. The extra dimensions usually give a lot of "wiggle room"
and so one can find rational points without too much delay. Usually.
The equation of the title is one equation in three unknowns (if we treat n
as fixed), so it leads to a surface; but like the cone, this surface is
homogeneous, so we essentially have a curve. Right away we know to be
optimistic!
IB. Curves (dimension 1): the role of genus
When confronted with a _curve_ to analyze, we find there are several
subcases of interest. As it turns out, these can be distinguished
geometrically too. Instead of looking at all the _real_ solutions to
the initial equations, look at the set S of all _complex_ solutions.
It turns out the IFT applies in this case to ensure that S is (mostly)
a 1-dimensional _complex_ manifold, but one complex dimension can be
represented as two real dimensions, so we are describing a _real surface_.
It happens also to be an orientable surface (when F is analytic) and
a compact surface (in a suitable sense) and so the topologists tell us
that S must be one of a few different shapes (up to homeomorphism):
a sphere, a torus, a 2-holed torus, a 3-holed torus, etc. We write g
(the "genus") for the number of holes, and these are the cases
g=0, 1, 2, 3, ... Fascinatingly, when you want to find integer or
rational points on a curve defined by polynomials, the genus has a very
significant influence. There are really just three cases (and I'll
title them with "1"s just to remind the reader that we're talking here
only about subcases of the dimension-1 case itemized above):
1a. When the curve has genus zero, then we can not only find all
the rational points, but we can parameterize them with rational
functions. The Pythagorean case happens to have genus zero.
The rational points on the curve 1 + y^2 = z^2 can be
parameterized as (y,z) = (2t/(1-t^2), (1+t^2)/(1-t^2)) where
t ranges over the rational numbers. In particular, of course,
there are infinitely many such rational points. There can be
infinitely many integer points, too, and Pell's equation more
or less captures the whole story here. (For example, the
equation x^2 - 2 y^2 = 1 describes a genus-zero curve and
has infinitely many integer solutions.) Genus-zero curves
are "easy".
1b. When the curve has genus one, the curve is called an "elliptic
curve". (It's NOT an ellipse.) An example is y^2 = x^3-x; it's
an "egg" shape together with an unbounded cup shape. These can
have only a finite number of integer points. (Unfortunately,
there is no known algorithm which limits the size, or even the
number, of the integer points for every elliptic curve.) They
can have infinitely many rational points, and indeed more can
be said: the rational points can be given the structure of a
finitely-generated abelian group, and we can say a lot about,
and with, that group structure. More on this below.
1c. When the curve has genus greater than 1, the curve can only
have a finite number of rational points (and hence only a
finite number of integer points). As in the previous paragraph,
this finiteness statement is not effective, sadly. But it's
a great and very deep result (Faltings, circa 1985) and it
guarantees that, for example, there are only finitely many
rational solutions to x^5 + y^5 = 1. (We know for other
reasons that there are NO solutions to this one except with xy=0.)
As a rule of thumb, one quadratic in two variables gives a curve of
genus zero; one cubic in two variables, or two quadratics in three
variables, gives a curve of genus one; everything else gives higher
genus. This is an imprecise statement but a good starting point.
To add to this information about curves in general, let me say that
the genus is _effectively computable_. I use a package called CASA
which runs under Maple. There are other classical algorithms and
many have been embedded into lots of software, so that you can often
avoid doing any work when looking for rational or integer points on
curves, particularly when the genus is 0 or 1.
To subtract from this information I have to note that there can be
singularities which mess things up (including the very definition of
what "genus" is supposed to be.) For example, the cubic curve y^2 = x^3
isn't an elliptic curve at all, because of the singularity at (0,0).
(It's of genus zero and I can parameterize it's rational points as
claimed in 1a: (x,y) = (t^3, t^2). Duh.)
IC. Elliptic Curves (genus 1): the role of rank and other things
Now let me go into even more detail about subcase 1b. By using some
invertible changes of variables, these can always be put into a
2-variably cubic form of a very special type ("Weierstrass Normal Form"):
y^2 = x^3 + a x^2 + b x + c. (You can even assume a = 0 by using
a linear change of variables.) Since this equation is a cubic, it is
a simple bit of algebra to prove that
every straight line meeting the curve twice
meets it in precisely one more point.
This is very important: it gives a way to combine two points to make
a third point (the "chord and tangent process"). Iterating this, we
see that once we have two points, we are likely to have infinitely
many points. In fact, you can even combine a point with itself, using
a tangent line or a limiting argument.
More importantly, this "2 points in, one point out" idea allows us to
define a binary operation on the set of rational points which turns
out to satisfy all the axioms for an abelian group! (One has to
select a point to be the identity element, first.) A deep theorem of
Mordell (1920s?) shows the group is finitely generated, so it's a
product of cyclic groups. Another deep theorem of Mazur (1978) asserts
that there are very few possibilities for the torsion subgroup
(Z/n, n<11 or n=12; or (Z/2)*(Z/2n) for n=1,2,3,4). So finding all
the rational points on an elliptic curve can be broken into several
steps:
1b-i : find all the torsion points. (There's a quick algorithm.)
1b-ii : find a lower bound on the free rank. (Usually you just
hunt around and find some rational points. There are
algorithms to prove that they are independent, i.e. not
in the subgroup generated by other known points.)
1b-iii: find an upper bound on the free rank r (there are some
algorithms which work sometimes). With luck, this
agrees with your lower bound, so you know the true rank.
1b-iv : show that the points found generate the whole group and
not a subgroup of finite index.
Once you've got your generators, you can start creating all the points
you want using the group law. I want to stress that this really just means
drawing lines in the plane and finding the third point of intersection, as
in an earlier paragraph; it's not deep magic. And the process of combining
points tends to proceed very regularly: the number of digits needed to
write down "P + Q" is approximately the sum of the numbers of digits
needed to write down P and Q separately, so we tend to get the
"small" points first, then the "large" points.
Observe that we have now characterized the elliptic curves for which
there are infinitely many rational points: they're the ones whose
(free) rank is positive.
On the plus side, much of this has been made algorithmic over the years.
(I even played a small role in developing sone of those algorithms.)
In practice I just fire up Maple and load the package APECS which
incorporates all the algorithms I know about, and more. For the more limited
task of simply computing rank, there is another program, Cremona's MWRANK,
which is faster. Cremona also has a very efficient program RATPOINT
to carry out the necessary task of exhaustively computing all rational
solutions, of a bounded height, to an equation of the form
a m^4 + n m^3 n + c m^2 n^2 + d m n^3 + e n^4 = k^2
(These are called "homogeneous spaces"; more below.)
On the minus side, there are some things we can't always do or do well
with elliptic curves. We have to watch for these in the computer output.
Here are some problems with the four steps above:
1b-ii: there isn't a good way to establish a lower bound on the rank,
other than explicitly finding enough points. There are is a conjectural
result, using L-series (see next paragraph) which can give a lower
bound on the rank if you are willing to believe that these infinite
series sum to zero, when all you really have is that a certain finite
partial sum is very small! There is also a well-established parity
conjecture which can conditionally prove the rank to be one more than
the number of points you have already found. In practice, when one
of these conditional lower bounds of rank is larger than the number of
known independent points, it makes sense simply to look a little harder
for some points. In THIS document, we were almost always successful.
That is, for the curves AT HAND, the lower bound on the rank is precisely
the number of displayed independent points. (The exceptions are shown
in section III, and merely represent some additional searching we
need to do.) The reader should be thankful that our system administrator
permitted me to run MWRANK and RATPOINT on multiple machines to provide
these explicit lower bounds on the rank...
There are techniques used by the pros to find impressive-looking
points on a curve (and so to verify a lower bound on the rank),
including descent in algebraic number fields and Heegner-point
calculations. I have not used those techniques in this project
(mostly because I don't understand them well!)
1b-iii: Efficiently finding a close upper bound on the rank of an elliptic
curve is just plain hard. We have many tools but all have drawbacks,
and in particular some only give "conditional" upper bounds on the rank:
* There is a process called "descent" which is very useful at finding
upper bounds on the rank, often quite close to the true rank. (Though
it is know that the upper bound will definitely be too high some times.)
Unfortunately, descent only works easily when the curve has torsion of
order 2, which none of our curves does.
* When possible, APECS will compute an unconditional upper bound due
to Mazur. I don't really know how that works. When it is given, it is
usually pretty close to the true rank. APECS is a little stupid about
one thing: when two elliptic curves are isogenous (see section IIA),
they have the same rank. However, the Mazur upper bound computations
may differ. So it is to our advantage to compute the Mazur upper bounds
on the ranks for the set of (what turns out to be) three isogenous
companions, and take the minimum of those three upper bounds.
* MWRANK uses an enumeration of homogeneous spaces. I believe this
computation is also unconditional. However, it (1) requires an exhaustive
search of a particular range of parameters, usually large. This means
the task can take very long -- multiple CPU-days for the larger values
of n under consideration here; (2) if we want to show that the upper
bound actually equals the rank, we must search for points on the
homogeneous spaces mentioned below. But there is NO a priori bound on
how deep that search needs to be; and in fact no guarantee that a point
will EVER be found on there spaces. Indeed (3) it will definitely produce
an upper bound which is too large if a certain invariant "Sha" of the
elliptic curve is nonzero, which definitely happens; for example, it
seems to be true that Sha is nonzero for our curve when n=37.
* There is an algorithm due to Mestre which computes an upper bound
whose validity rests on the Birch and Swinnerton-Dyer conjecture.
This is in APECS actually a real-valued function of one parameter;
when I have used it, I have recorded a value of that parameter which
makes the bound close to its useful minimum.
* There is a "parity conjecture", which computes a sign (+1/-1) from
some numerical data about the elliptic curve; conjecturally, this
sign is always equal to (-1)^rank . When an upper bound is known
from some other technique, this conjecture can possibly lower the
upper bound by 1.
* If all else fails, one can rely on another conjecture to compute the
rank as the number of vanishing derivatives of the curve's L-function
at 1. That is, in order to show the rank is k or less, it is
sufficient to show that L^(k) (1) is nonzero. Unfortunately, L is
defined as an infinite series, so there is some guesswork involved in
determining that a partial sum is sufficiently close to the infinite
sum, and there are questions of roundoff error, etc.
So each of these techniques has some limitations. It is technically
correct to refer to some of these as "conditional" upper bounds on
the rank, since their correctness depends on some unproven conjectures.
However, these conjectures have tremendous amounts of theoretical and
numerical support; it is hardly worth fantasizing that one of our
curves will demontrate a failure of any of these conjectures, let alone
the failure of more than one at once. We will dutifully flag the use
of the conjectures in our rank computations, but there can be little
doubt of the true ranks.
It is, by the way, an open question whether or not there are
elliptic curves of arbitrarily high ranks. We've got examples with
ranks in the low 20s; that's it so far.
1b-iv: Even if we really do know the exact rank r of our abelian group,
AND have r independent elements, we can't yet be sure we are
generating ALL the elements of the group when we start adding together
multiples of the generators. To see what I mean, consider the group
Z^2 of rank 2, and consider the elements a = (1, 1) and b = (1,-1)
inside it. They are independent. But all sums of multiples of these
have the property that the sum of their two coordinates will be
an even number; you will never, for example, get (1,0) in this way.
In fact a and b generate a subgroup of Z^2 of index 2.
Well, in the elliptic curve setting, once we have the right number of
independent points, we can put an upper bound on the size of the
search space to look for more points; if none are found in that
seach space, then our independent points are really generators.
(APECS can do all this for us.) But sometimes that search space is
prohibitively large.
Because of all these problems, we sometimes have to throw in the towel
and say, "Look, I have analyzed the elliptic curve and I'm really
pretty sure these are all its elements; but I concede I have used
conjectures X,Y,and Z to draw that conclusion, so there is an outside
chance I am wrong." It is because of this that I must flag some of
the entries in the list below as being conjectural. Realistically I
haven't the slightest doubt that the results are right -- I certainly
wouldn't waste machine cycles trying to find counterexamples -- but
I do confess the results are not proven in an airtight way.
In fact, APECS accepts these conjecture-based ranks as true during its
computations. It tells you which conjectures it's using, if any,
but doesn't hesitate to accept them!
OK, that's enough babble! Let's move on to the equation at hand.
II. This particular equation
The paper by Bremner and Guy contains many of these same observations,
and the cited literature there suggests that these remarks have been
made independently by Schoof and others. So since there is precedent
for re-discovering and presenting these ideas anew, we proceed...
IIA. Descent to an isogenous curve
We treat n as a fixed integer constant.
Suppose we had integers a,b,c with a/b + b/c + c/a = n . By
homogeneity, we'd be able to find such a triple with gcd(a,b,c)=1. Clearing
denominators, we see we have a solution to a^2c + b^2a + c^2b = n abc .
This is (for fixed n) a single homogeneous polynomial of degree 3,
and so, following section I, we discover describes a curve, which
happens to be of genus 1.
As I will explain in a moment, it will be useful to study the curve
defined by the related equation
(*) d^3 + e^3 + f^3 = n d e f
(for the same value of n). These two curves are naturally related to
each other in the sense that points on each lead to points on the other.
If (d,e,f) is a point on (*), then (a,b,c)=(e^2f, f^2d, d^2e) is
easily checked to be a solution to our original equation. Reciprocally
(but certainly less obviously!) if (a,b,c) solves our original equation,
then we may construct a point on (*):
d = a*b*c*(a+b+c)*(a^2+b^2+c^2-a*c-b*c-a*b),
e = (a*c+b*c+a*b)*(a^2*b^2+c^2*a^2+b^2*c^2-b^2*c*a-b*c*a^2-c^2*b*a),
f = (a^2*b^4+b^2*c^4+c^2*a^4) - a*b*c*(a^2*b+b^2*c+c^2*a),
These operations are NOT inverses of each other but they are very useful
and just a little deep.
Indeed, our original abc-equation and the new def-equation (*) both
describe elliptic curves E1 and E2 which, in the previous section,
we noted carry the structure of abelian groups. The formulas just given
describe functions phi : E2 --> E1 and psi : E1 --> E2 which turn
out to be _homomorphisms of groups_ (assuming we use (0,0,1) as the
identity element of E2 .) The composites phi o psi and
psi o phi are not the identity maps but they happen to be the
multiplication-by-three ("tripling") maps E1 --> E1 and E2 --> E2
respectively. (We will give a formula for the tripling map on E2 below,
and the reader can check that it agrees with psi o phi.)
After this piece of information it should not be too surprising
to hear that phi and psi are nearly isomorphisms: the kernel
and kernel must be finite products of (Z/3Z)'s.
Such maps are called _isogenies_ between the elliptic curves (we say
the curves are _isogenous_) and they are very useful for discovering
things about the arithmetic structure of these groups. They're also
handy for finding points on the curves, since in general if phi is
an isogeny, then phi(x) has greater height (i.e., takes more digits
to write down) than x itself; that means, if you're lucky, that you
can find "big" points on E1 simply by finding "smaller" points
on E2, and applying phi. (This process is called "descent", since
it's what lay behind Fermat's method of "infinite descent" centuries ago!)
That's exactly what happens in our case: phi must be a surjection,
and therefore all solutions (a,b,c) to the original equation arise
from (simpler) solutions (d,e,f) to the new equation. This is easy to
see in an elementary way: if (a,b,c) is a primitive integer solution to
a^2c + b^2a + c^2b = n abc
then b divides a^2c. Thus, the primes dividing b are split into two
disjoint subsets: those also dividing a and those also dividing c.
If p is in the first subset, and if p^x, p^y, p^z are the greatest
powers of p dividing a, b, and c, then z=0 and y <= 2x. (Using
exactly the same argument with the variables rotated around, we find
as well that x <= y.) Now, if y is positive but less than 2x, then
the greatest power of p dividing the left side would be p^y exactly,
while the right side is divisible by p^(x+y). This contradiction shows
y must equal 2x : all primes in the set dividing both a and b
have exactly twice as high an exponent in b as they have in a.
So if f = gcd(a,b), then b = f^2 b' and a = f a' where a' and b'
are coprime to f (and to each other). Arguing similarly about
e= gcd(a,c) and d = gcd(b,c), we find a=e^2f, b=f^2d, c=d^2e.
(The signs of d,e,f should be chosen to match those of b,c,a respectively.)
That is, we have shown that the map phi is onto! (It's also one-to-one.
By contrast, psi has a kernel consisting of the three torsion points
of E1, and only maps onto the multiples of 3 in E2.)
So we see that it is to our advantage to look for solutions to (*)
rather than for solutions to our original equation. This will give
all solutions to the original equation, but using smaller numbers.
(For example, the example for n=112 in the introduction is phi(d,e,f)
where d,e,f are
403909122691328588518061393542,
-81634675793306734523552997069865,
66756829882613387041310733449793
respectively. Still large but smaller than before! Similarly, the
enormous point found by Womack for n=177 corresponds to (d,e,f)=
11586299300246645065650175011667633294528995894742493608006903
499128047096078689216614212030144552460525030444760940918765730
944421945175253160922633489847006529687358187395396664036033027
which use "only" 63-digit numbers.)
So from here forward we will be working with the isogenous curve (*)
rather than our original equation.
Incidentally, there is for each n a third elliptic curve isogenous
to these, and for some (not all) values of n the corresponding
isogeny to E2 may be a surjection on the rational points, meaning
that there are "smaller" -- and thus easier-to-find -- solutions on
this new curve which in turn give us the more impressive points on (*).
This is the technique which allowed MacLeod to find his solution for
n=142. (This third curve has no rational 3-torsion and so does not have a
symmetric 3-variable presentation, but may be cast into normal form as
v^2 = u^3 - 27*( (m+1)*u - 4*m^3)^2
where for brevity I have set m = (n-3)/9, which is not necessarily integral.
The isogeny in one direction may be given as
u = 1/(27*(X-4*n-12)^2) * (3*X+4*n^2)*( X^2 + 4*(n+3)*X + 16*(n^2-3*n+9) )
v = Y/(27*(X-4*n-12)^3) *
(X^3 - 12*(n+3)*X^2 - 16*(n^3+6*n^2+9*n+27)*X - 64*(n^4+n^3+9*n^2+27))
where (X,Y) is a point on the curve (***) below, and in the other direction as
X = ( u^3 - 12*(3*m^2+3*m+1)*u^2 + 432*m^3*(m+1)*u - 1728*m^6 )/u^2
Y = v*( u^3 - 432*m^3*(m+1)*u + 3456*m^6 )/u^3
So if a point is found on one curve, we easily obtain a point on the other
as well.)
IIB. Formulary, and reductions to standard form
Now, as in section I, we note that equation (*) describes a surface,
but it's homogeneous so we can scale every point to one with f = 1 say
(except those which have f = 0, namely the points (d,e,f) = (t, -t, 0).)
So our attempt to solve (*) in integers is really equivalent to solving
(**) x^3 + y^3 + 1 = n x y
in rational numbers. From here out, that's exactly what we will do.
(We'll also look specially for _positive_ rational pairs (x,y), which
give all the _positive_ integer solutions (d,e,f).) For symmetry's sake
we will sometimes write the point (x,y,z) but there is never
harm in taking z=1 (or scaling back to z=1).
Right away we see that n=3 is a special case: the equation (**) factors as
(x+y+1)(x+wy+w^2)(x+w^2y+w) = 0 where w is a cube root of unity. That
means all the complex solutions lie on three lines, two of which have no
real points at all except x=y=1. So the complete rational solution set is
(x,y) = (1,1) or (-1/2 + t, -1/2 - t) with t rational.
So when n=3, we have (a curve of genus zero and so) infinitely many
rational points. Of course with x+y=-1 it's hard to have both x and y
positive! So if that's your goal, the only rational solution when
n=3 is the point (1,1).
'Nuff said; from here out we assume n isn't 3.
Since (**) is a cubic, we suspect we have an elliptic curve, and so
we try to get it into Weierstrass Normal Form. We use the following
substitutions:
x = -1/2*(n*X+36-Y)/(3*X+4*n^2),
y = -1/2*(n*X+36+Y)/(3*X+4*n^2)
which are invertible (i.e., we aren't losing any points or introducing
spurious solutions); the inverse transformations are
X = -4*(n^2*(x+y)+9)/(3*(x+y)+n),
Y = 4*(n^3-27)*(x-y)/(3*(x+y)+n)
(OK, I lied; these transformations fail to be defined, or to be
one-to-one and onto, near some combinations of (x,y) or (X,Y);
but none of these bad points have rational coordinates for positive integers
n unless n=3.)
The result of applying these transformations is that we are left looking
for rational points on the curve
(***) Y^2 = X^3 + n^2*X^2 - 72*n*X - 16*(4*n^3+27)
which is recognizable as being in WNF. Such an equation really does describe
an elliptic curve as long as the discriminant of the cubic is nonzero.
Well, that discriminant is 256*( (n^3-27) )^3 , so we're safe.
That is, for all n other than 3, (**) describes a (non-singular)
elliptic curve.
The curves (***) with n=1 and n=2 turn out to be fairly "old" curves:
people make lists of elliptic curves which are "small" by some measure,
and these two curves are on those lists. These list-makers have proven
that these particular curves have rank 0, meaning they consist only of
torsion points, and that the only torsion points are those corresponding
to (x,y)= (0,-1) or (-1,0). So from here on, we will assume n > 3 .
(We could consider negative integers n as well; for small n these
are also well-known curves.)
We complete our formulary by translating the standard expressions
for the group operations back to the original xyz coordinates. Here
we have removed additional factors wherever appropriate, viewing
(kx, ky, kz) as equivalent to (x,y,z) when k is not identically zero.
Moreover, the formulas for each component are only unique up to
the addition of a multiple of x^3+y^3+z^3-nxyz , which is assumed to
vanish. We have selected what we consider particularly brief representatives
of these equivalence classes of polynomial. We also note that the
representatives chosen do not refer to the variable n !
0. The identity element is (x,y,z) = (1,-1,0) ( =(-1,1,0) ).
1. The negative of a point (x,y,z) is (y,x,z).
2. To add a point (x,y,z) to itself gives the point
( y*(z^3-x^3), x*(y^3-z^3), z*(x^3-y^3) )
(unless (x,y,z)=(1,1,1) -- which is only on the curve when n=3).
3. The "sum" of the distinct points (x0,y0,z0) and (x1,y1,z1) is
[(-y0*z1+z0*y1+x0*y1-x1*y0)*(y0^2*z1^2-z1*x1*y0^2-2*y0*y1*z0*z1+x0*y1*z1*y0
+y0^2*x1^2-2*x1*x0*y0*y1+x1*y0*y1*z0+y1^2*z0^2+y1^2*x0^2-z0*x0*y1^2)/y0/y1,
(-x0*z1-x0*y1+z0*x1+x1*y0)*(x0^2*z1^2-z1*x0^2*y1-2*x0*x1*z0*z1+x1*y0*x0*z1
+y1^2*x0^2+x0*x1*y1*z0-2*x1*x0*y0*y1+x1^2*z0^2+y0^2*x1^2-z0*x1^2*y0)/x0/x1,
-(-y0*z1-x0*z1+z0*y1+z0*x1)*(y0^2*z1^2-2*y0*y1*z0*z1-y0*x0*z1^2+x1*y0*z0*z1
+y1^2*z0^2+x0*y1*z0*z1-x1*y1*z0^2+x0^2*z1^2-2*x0*x1*z0*z1+x1^2*z0^2)/z0/z1 ]:
Note that this formula assumes all coordinates are nonzero. If, say, x0=0,
then the original equation x0^3 + y0^3 + z0^3 = n x0 y0 z0 forces y0 = -z0,
so one of the summands is (x0,y0,z0) = (0, -1, 1) (=(0,1,-1)), which is
one of our points of order 3. The sum of this point and (x1,y1,z1)
is (z1,x1,y1), and likewise the sum of (-1,0,1) and (x1,y1,z1) is
(y1,z1,x1).) Of course the sum of (1,-1,0) -- our identity element -- and
(x1,y1,z1) is exactly (x1,y1,z1) !
4. We can combine these formulas to get the triple of any point (x,y,z): it's
[(z^2*x+z*y^2+x^2*y)*(z^4*x^2-y^2*z^3*x-z^2*y*x^3+z^2*y^4-z*y^3*x^2+y^2*x^4),
(z^2*y+z*x^2+x*y^2)*(z^4*y^2-z^3*y*x^2-y^3*z^2*x+x^4*z^2-z*y^2*x^3+y^4*x^2),
y*x*z*(x^6-x^3*z^3-x^3*y^3+z^6+y^6-y^3*z^3)]:
We have already referred to this formula in our discussion of isogenies.
We will also use this formula for comments about positivity, in the next
section, and later for our discussion of torsion, and then finally in the
presentation of the final tables. (We can also use it to check for the
primitivity of numerical solutions: (a,b,1) is a triple iff this cubic
has a root which is a perfect cube (in which case y = Y^(1/3) and z=1 are
two of the coordinates of a solution having triple equal to (a,b,1) ):
(b^2*a^2)*Y^3 - b*(b^6+2*a^3+1+2*b^3+a^6-3*a*b^2-3*b^5*a+6*b^4*a^2
-7*b^3*a^3+6*b^2*a^4-3*a^5*b)*Y^2 + a*(2*a^3+a^6+6*b^4*a^2-3*b^5*a
+2*b^3-3*b*a^2+6*b^2*a^4-7*b^3*a^3-3*a^5*b+b^6+1)*Y - (b^2*a^2)
Before leaving this section, we note that in the equation (***), one
may treat n as a variable as well, so that (***) describes a _surface_.
In this document we are only interested in the slices of that surface
corresponding to a fixed integer value of n, but the surface has
other interesting features. For example, we note that the equation (***)
remains invariant under the involution (n,X,Y) -> (-X/4,-4n,Y) ---
an interesting observations which we can check in some numerical examples
below but which we cannot seem to use in any effective way!
IIC. Interpreting the positivity requirement
Our main goal is to find all the rational points on (***); they correspond
to all the rational points on (**). But what about the positivity condition?
We originally (assumed n is positive -- we will keep this assumption in this
section -- and) wanted positive a,b,c solving the title equation; positivity
occurs iff d,e,f are positive, and that happens iff x,y > 0 in (**).
Since the change-of-variable functions above describe continuous mappings
on the plane, it is clear that these substitutions must match up the points
on the bounded components of the curve (**) and the transformed curve (***).
A glance at the graph shows that the bounded component of (**) is precisely
the part of that curve lying in the first quadrant -- that is, it's the
part containing the points (x,y) of interest to us. Therefore, we will
be interested in finding rational points on the curve (***) which lie on
its bounded component. That component is easy to find: on the right side
of (***) we have a cubic with three real roots (if n>3) since the cubic is
positive at X = -n^2 and then negative at X = 0. So the curve (***)
consists only of points with X-coordinates between two negative real
roots (the bounded component) and points with X-coordinates larger than
the positive root (the unbounded component). So to keep the
positivity requirement of the original problem, we look for:
rational points on (***) with X < 0 ( assuming n>3 )
A straight line can't cross a closed curve just once; as a consequence, if
two points lie on the unbounded component of the curve, their sum does too.
This shows that the (real) points on the elliptic curve having X > 0 form a
subgroup of index 2. The rational points there then also form a subgroup
of index 2 unless all generators lie in that component of the curve.
Now, when we find independent points on the curve, it is not necessarily
true that they are generators of the whole group, but they are close enough
that we can find out whether there exist generators in the other component.
Here's how:
Suppose for example the curve has rank 1, i.e. it's generated by a single
element g of infinite order, and the torsion subgroup T (which, as
we will see below, lies in the unbounded component except when n=5).
If there is any element of the group in the bounded component, then g
itself must be such an element, and all the elements in the unbounded
component are those of the form 2k g + t for some integer k and some
torsion element t. So if we have an element h of infinite order which
is in the unbounded component, it is of this form, and thus h - t is
the double of another group element, k g. (Actually, except when n=5,
all torsion elements are themselves doubles.) Therefore, if our one
element of infinite order is not a double, then there are NO elements
of the elliptic curve in the bounded component.
In a similar way we can show that if the curve has rank 2 and two
independent elements h1 h2 are known, both lying in the unbounded
component, then we need only test to see whether h1, h2, or h1+h2
is a double; if not, then the rational points of the curve all lie
in the unbounded component.
So it is a completely effective process to determine whether the curve
has rational points in the bounded component, as soon as enough
independent points are known. (APECS has a command "Half" which can
determine whether a point is a double.) If we discovered that one of
our known points were the double of another point, we would replace
the former with the latter in our list of generators of the subgroup
of known points. Thus, if in the lists of section III none of the
known points lies in the bounded components, then there simply are
no points in the bounded component at all (assuming we have provided
as many independent points as the true rank of the curve.)
Note that if a point on the curve lies outside the unbounded-component
subgroup, then so does its triple. So our tripling formula above instantly
produces more positive solutions from a single starting positive solution.
This shows in a very constructive way that the set of positive solutions
will be infinite if nonempty (except for torsion elements, which we
take up next!)
Summary: ( _positive_ solutions a,b,c )
<--> ( _positive_ solutions x,y,z )
<--> ( _negative_ X-coordinates )
<--> ( _odd_ sums of "positive" generators )
IID. The Torsion subgroup
Let's begin our analysis of the arithmetic structure of this elliptic curve
by thinking about torsion. I claim the curve has a torsion
subgroup of order 3. I sort of know this from the get-go because of
the obvious 3-fold symmetry in our original problem. But we can
actually check that the points (x,y)=(0,-1) and (-1,0), which become
the points (X,Y)=( 4*n + 12, +- 4*(n^2+3*n+9) ) in (***),
really have order three. So that's part of the torsion. By Mazur's
theorem, the torsion subgroup then has to be one of
Z/3, Z/6, Z/9, Z/12, or Z/2 x Z/6.
We will show that for all integers n (not equal to 3), the torsion subgroup
is always just Z/3, except when n=5 or n=-1, for which the group is Z/6.
In order to do this, we must show that there is no element of order 9,
i.e., that the points {x,y,z}={0,1,-1} of order 3 are not themselves
the triples of any other points, and that there is no element of order 2.
Each of these problems amounts to finding Diophantine solutions to a
two-variable polynomial equation, so it will give us an opportunity to
use the skills discussed in section I !
The latter case is easier so we begin there. It is known that
an element of order 2 on the curve (***) would be a point (r,0) where
r is a rational root of the cubic. This would require r to be
integral, so we shall show that
r^3 + n^2*r^2 - 72*n*r - 16*(4*n^3+27) = 0
has no solution in integers (r,n) unless n=5 or n=-1 or n=3.
Well, that single equation in two variables describes a curve in the plane,
and since the polynomial is of degree 4, we expect it to have low genus.
In fact, the genus turns out to be zero, because this curve can be
parameterized --- we are after all talking about the triples (x,y,n)
for which n = (x^3+y^3+1)/(xy) and for which 0 = Y
= 4*(n^3-27)*(x-y)/(3*(x+y)+n); so a parameterization uses y = x and
n = (2x^3+1)/x^2, to discover that r = -4(x^3+2)/x. So we know we are
looking for integer points on a curve of genus zero, and these problems
can be resolved (e.g. Pell's equation).
But this particular polynomial can be analyzed quite explicitly.
If (r,n) is an integer solution, let u = 4*n-r+12, v = 4*n+r; these are
also integers, but they satisfy a different equation now, namely
(u-4)*(u-36)^3 + (-2*u^2+864-144*u)*v^2 + v^4 = 0
(as can be seen by solving for n and r in terms of u and v and
then substituting into the last polynomial equation). Since this
equation involves only w=v^2, not v itself, then u and the integer w
satisfy a relation
(u-4)*(u-36)^3 + (-2*u^2+864-144*u)*w + w^2 = 0
which is _quadratic_ in w. In particular, this means the discriminant
of this polynomial (with respect to w) must be a square. That
discriminant works out to be 1024 u^3 so we see that u itself
must be a square, say u = z^2. Replacing u by z^2 in the polynomial
linking u and v we now get a polynomial which _factors_, namely it's
( v^2 - (z-2)*(z+6)^3 )*( v^2 - (z+2)*(z-6)^3 ) = 0
so that v^2 is either f(z) or f(-z) where f(t) = (t-2)(t+6)^3.
(Since all we know about z is that its square is u, we may suppose z
is chosen so that v^2 = f(z). ) Now, a product of integers of the form
(z-2)*(z+6)^3 is a perfect square iff (z-2)(z+6) = (z+2)^2 - 16 is a
square, so we need to consider solutions in integers to an equation of the
form y^2 = x^2 - 16, which obviously requires (x-y)(x+y)=16, i.e., x-y and
x+y are two integers (of the same parity) whose product is 16. The only
choices are {2,8}, {4,4}, and their negatives. Thus the only possible
values of y are 5, -5, 4, or -4. One of these is our z+2, so we must
have z = 3, -7, 2, or -6; these imply respectively that v^2=f(z) is
27^2, 3^2, 0, or 0 (again), and that u = z^2 is respectively
9, 49, 4, or 36. Taking account of the two possible square roots in two
cases, we can then find all possible pairs (n,r) from the definitions
{u = 4*n-r+12, v = 4*n+r} : discarding the non-integral ones we find
the choices to be (n,r)=(-1,4), (3,-12), (3,15), and (5,-17). We already
know that when n=3, (***) does not describe an elliptic curve.
When n=-1 and n=5, we do indeed get elliptic curves with torsion
of order 6 (and rank zero), (although of course in this article we primarily
consider positive values of n).
So there is no 2-torsion in any of our curves except when n=-1 or n=5.
(We could certainly consider other _rational_ values for n, in which
case there would frequently be 2-torsion!)
Incidentally, we noted earlier that the cubic polynomial in (***) always has
three _real_ roots when n > 3, two negative and one positive.
The left-most root is between -n^2-1 and -n^2 if n>5,
and so is not an integer; but the other two roots are approximately
+- 8*n^(1/2) and so they cannot be so easily bracketed.
The only other torsion subgroup thus permitted by Mazur's theorem is Z/9,
which requires the elements of order 3 to be triples of other points.
Indeed, there would be a point (x,y,z) whose triple is the point (0,-1,1).
Now, we have an explicit formula for the triple of a point in these
original coordinates. The first coordinate of the triple is the product of
two factors
z^2*x+z*y^2+x^2*y and z^4*x^2-y^2*z^3*x-z^2*y*x^3+z^2*y^4-z*y^3*x^2+y^2*x^4
so we look for combinations of coordinates which allow one of these
factors to vanish. As usual we may take z = 1.
The first factor is a quadratic in x; for this to vanish for some rational
y, the discriminant with respect to x must be a square. That discriminant
is 1 - 4 y^3, so we are looking for a rational solution to
u^2 = 1 - 4 y^3. This equation describes a curve, and it happens to be
of genus 1, so we can study this with our tools for elliptic curves. As it
happens, this curve has rank zero, and its only rational points -- torsion
points of order 3 -- have y = 0. But if y = 0 and our quadratic
vanishes, then x = 0 too, and we have the point (x,y,z) = (0,0,1),
which does not lie on the curve x^3+y^3+z^3 = n x y z for any n !
The second factor vanishes at the origin (which we have just noted does
not correspond to a point on any of our curves) but never vanishes
at any other point on the axes, so we may freely divide by x
and y. In particular, m = x/y is a rational number and we may replace
x by ym in this polynomial to get a condition which we may write
symmetrically in m and y: (m+y)^2/(m*y)^2 -3/(m*y) -(m+y) +(m*y)^2 = 0.
Then the (rational!) sum s and product p of m and y satisfy a
condition which we may write as ( 2s-p )^2 = -3( p^4 - p).
Now, the equation Y^2=-3*(X^4-4*X) again happens to describe an elliptic
curve with only 2 rational points (having X=1), so we must have p=1 and
s = -1 or 2. Then m and y are the roots of one of the equations
X^2 + X + 1 = 0 or X^2 - 2 X + 1 = 0, and since m and y are real,
this can only mean each equals 1, so that x=1 as well. So the only
rational point where the second factor can vanish is at (1,1,1), and
that only lies on our original curve when n = 3 -- in which case,
as we know, the the curve is not an elliptic curve at all. So for
all rational values of n, there is no torsion element of order 9
on our elliptic curves.
So there are no torsion points, beyond the two we know of, on any of
the elliptic curves except when n=-1 or n=5. In particular, for all
n > 5, when the curve has any rational points besides those with xy=0,
then it must have non-torsion points, i.e. positive rank, meaning there
will be infinitely many points.
IIE. Computations of ranks
Now let's start computing ranks of the elliptic curves in our set.
We have no universal statements to make beyond what was given in
section I; rather, we will investigate each integer value
n=1, 2, ..., 200 separately.
A single command will get APECS to compute the rank of each of these
curves; it deliberates for a minute or two and produces an answer.
But one is obligated to read the fine print of the answer, for reasons
discussed in section I.
As it turns out, all the curves we are interested in, through n=200,
have rank 0, 1, or 2. Probably it is true that for larger n, almost half
will have rank 0 and almost half will have rank 1; curves of increasingly
large rank probably exist but are rare enough that an "average" rank
exists and is a little larger than 1/2.
APECS will be compute a lower bound on the rank, usually by finding
enough independent points. Sometimes it needs to be prodded to look
a little deeper in the search space; we can avoid that in the future
by simply informing it of points we have already found. Left to its
own devices, it will sometimes raise this lower bound by 1 in accordance
with a parity conjecture; we will prevent that in the discussion of
this list by making SURE we actually find enough independent elements.
Read again about case 1b-ii to understand this.
APECS will compute several upper bounds, in general. There is sometimes
a low provable upper bound on the rank. We can report that and, if it's
low enough, use it to determine the rank exactly. There is the Mestre
bound, which is actually a function of a parameter we can choose; when
it is helpful we report the best Mestre bound noticed (together with
the value of the parameter). As appropriate, we use the parity conjecture
to reduce the upper bound by 1. Again we observe that some of these upper
bounds are conjectural, so we record them as such.
Listed after n itself are the following data (as appropriate):
First, the Mazur (unconditional) upper bound on rank (where "-1" means none
is given by APECS); the flag "I" means the bound is taken from one of
the isogenous curves, invariably the first isogeny discussed in section IIA.
When the rank is positive, we give lists of independent points, first
in APECS native format (APECS performs an initial change of variables
to "Laska minimal form") and then showing our [X,Y] coordinates. (The
corresponding (x,y,z) coordinates are in section III.) Also shown,
when used, is the Mestre parameter used. There is a notation when
L-series computations were used to confirm a rank, and a notation when
MWRANK was used to confirm a rank. Also, when the rank is positive, it
is appropriate to ask for generators for the full group (rather than
for a subgroup of finite index); APECS can search for these, but the
time needed grows rapidly with n , so we have done this only for a few
small n (marked BAS, after the APECS routine used).
Values of n > 200 have only been tested sporadically (up to n=1000).
IIE0. Curves of rank 0 (no nontrivial solutions to title equation)
Case0a: Proven upper bound = 0: That means, unambiguously, that the
only rational points are the torsion points discussed above --
five when n=5, two points otherwise. (Note that in some cases, as
indicated, the proven upper bound on the rank is the Mazur bound on
an isogenous curve.) In many of these cases the conclusion that rank
is 0 is also supported by the use of the conditional methods discussed
elsewhere in this document.
1, proven rank = 0
2, 0
4, 0
5, 0
7,0I MW
8,0I MW
23, 2 MW
25, 2 MW
28,0I MW
32,0I MW
37, 2 mwrank cannot confirm rank=1 because Sha[2]=4
49,0I MW
50,0I mwrank cannot confirm rank=1 because Sha[2]=4
56,0I mwrank cannot confirm rank=1 because Sha[2]=4
58,0I (APECS can also "prove" this by showing an L-series nonzero...)
85,0I
88,0I (also L-series)
95,0I (also L-series)
121,0I
134,0I
140,0I
163,0I
169,0I
176,0I
179,0I
182,0I
200,0I
In the remaining cases, no rational points were found but APECS gives
no proof that rank = 0. To the limits of our patience, we have
confirmed that their ranks are 0 using MWRANK. We also use techniques
which, conditional upon famous conjectures, prove the rank to be
zero. (We can try to use one or more, possibly in tandem). Note that
in the remote chance that the conjecture(s) used should fail, this
will mean that there really are solutions to our original Diophantine
problem, while we are asserting here that none exist!
Case0b: In one case the proven upper bound on the rank is 1, and the
Mestre upper bound ( =Mest(200) ) is less than 1, giving two independent,
but both conditional, proofs that the rank is really 0: either an appeal
to the parity conjecture, or an appeal to the B-SD conjecture to justify
Mestre's bound, will suffice.
11, 1, 200 MW
Case0c: In other cases, we cannot use the parity conjecture (either
because no proven upper bound was given, or because that bound was 2)
but we can still prove the rank to be zero with Mestre's procedure
(the Mestre parameter is shown after the proven rank):
12,-1, 30 MW
22, 2, 200 MW
24,-1, 1000 MW
27,-1, 80 MW
33,-1, 1000 MW
34, 2, 2500 MW
39,-1, 400 MW
46, 2, 4000 MW
48,-1, 1500 MW
52, 2, 300 MW
55,2I, 600 MW
65,2I, 5000 MW
75,-1, 3600 MW
78,-1, 3000 MW (took a couple of hours!)
79,2I, 4000
111,-1, 300
118,2I 1000 (also L-series)
131,2I, 4000
138,-1, 5000
157,2I, 4000
165,-1, 4000
Case0d: In some cases, the proven upper bound on the rank is 1, but no
choice of the Mestre parameter was found to be sufficient to show the
rank is zero. In these cases, the parity conjecture can still show the rank
to be zero. (Note that in both the cases listed here the proven upper
bound is the Mazur bound on an isogenous curve.)
43,1I MW (took hours...)
91,1I (also L-series)
Case0e: There are some cases in which we must use BOTH conjectures:
there is no proven upper bound of 1 (or less), but Mestre's bound
shows the rank to be less than 2, and the parity conjecture rules out
rank 1. Thus the rank is 0.
42,-1, 150 MW
45,-1, 150
59, 3, 125
60,-1, 475
61,2I, 475
68,2I, 500
80,2I, 1000 (also L-series)
81,-1, 1500 (also L-series)
82, 2, 350 (also L-series)
89,2I, 375
90,-1, 200
93,-1, 1500 (also L-series)
97,2I, 500
100, 2, 150
104,2I, 800
114,-1, 4000 (also L-series)
115,2I, 150
125,2I, 850
135,-1, 1200 (also L-series)
137,2I, 850
139,3I, 150
141,-1, 4000 (also L-series)
144,-1, 1200
146,2I, 4000
150,-1, 700
152,2I, 500
153,-1, 700
180,-1, 500
183,-1, 700 (also L-series)
188,2I, 575
198,-1, 2500 (also L-series)
199,2I, 200
Case0f: In the most extreme cases even the use of Mazur's or Mestre's bound
seems not to permit us to conclude the rank is less than 2, and so even with
the parity conjecture we cannot show the rank is zero. However, we can
compute the L-series value L(1) and see that it is apparently nonzero
to conclude the rank of the curve is zero. (Value of L(1) is shown along
with the number of terms summed to get there.)
168,-1, .5488 2498
170,2I, .5437 2518
171,-1, .5411 1422
173,2I, .5358 2569
184, 2, .5100 2930
193,2I, .4913 2940
194,2I, .4890 3084
IIE1. Curves of rank 1
Recall that we are now listing a point found on the curve, in two
formats: the first can be used to tell APECS about the point
(the "Append" command); the second shows its (X,Y) coordinates.
Armed with these data, APECS knows that these curves have rank at least 1.
There are then several cases, parallel to the rank-0 cases in IIE0.
Case1a: Proven upper bound = 1 and point found:
As soon as we find one point, it is certain that the rank is 1,
and thus there are infinitely many rational points.
(Note that in many cases the proven upper bound is not the Mazur rank
of our curve but of a 3-isogenous curve.)
10, 1 [-9, 45] [-68, 364] Bas
13,1I [-12, 107] [-104, 812] MW Bas
14,1I [7, 32] [-36, 260] Bas
16, 1 [70, 513] [196, 4108] Bas
17,1I [14, 38] [-40, 364] Bas
19,1I [-53, 250] [-332, 1792] Bas
20,1I [42, 3] [36, 28] Bas
26,1I [43, 101] [-52, 812] Bas
29,1I [-24, 1019] [-376, 8060] Bas
31,1I [105, 311] [100, 2912] Bas
35,1I [114, -90] [48, -260] Bas
38,1I [-9, 1956] [-516, 15652] Bas
44,1I [12670, 1425860] [50036, 11406884] Bas
47,1I [304, 2938] [480, 24724]
53,1I [56, 4034] [-712, 32500]
62,1I [282485/841, 1519591/24389] [53460/841, 12254284/24389]
64, 1 [260920/729, 3444497/19683] [49324/729, 27634708/19683]
70, 1 [330085/729, 29121256/19683] [130612/729, 233048780/19683]
71,1I [437, -295] [68, -608]
73,1I [47735888578/158030041, 9357179103582972/1986595645411] [-89717798504/158030041, 77265730632501572/1986595645411]
74,1I [-793, 13682] [-4996, 109460]
83,1I [555, -502] [-76, -1792]
86,1I [511, -4317] [-420, -34532]
92,1I [8355372734/9579025, 235350241954548/29647082375] [6408640436/9579025, 1882920523965884/29647082375]
98,1I [1986709/2401, 110093894/117649] [263636/2401, 881221748/117649]
101,1I [-1260, 44901] [-8440, 354172]
103,1I [906, -16] [88, 3500]
109,1I [3999962194/3352561, 66193965153228/6138539191] [2723707216/3352561, 558871998491444/6138539191]
110,1I [-349, 55415] [-5428, 443324]
112, 1 [40291010574182510673125/130021324431751204, 8087337035895796623393558560583165/46883700003783029505476392] [40155138290151330664945/32505331107937801, 8087337059337646625285073313321361/5860462500472878688184549]
113,1I [634306/625, 30852379/15625] [-122776/625, 310312132/15625]
116,1I [1316, 11561] [780, 92492]
119,1I [1501, 19149] [1284, 159200]
122,1I [5662813820985655/5099778876361, 88135207127499343485090/11516672543340879109] [-2643647942807940/5099778876361, 705127723710168111397156/11516672543340879109]
124,1I [336129928/212521, 1890876921126/97972181] [255562108/212521, 15127407257732/97972181]
127,1I [2209, 59407] [3460, 484096]
130, 1 [-1428415201284331/555516808900, 25824873907708698020453/414043343177437000] [-2210582868215531/138879202225, 25825080929380286738953/51755417897179625]
133,1I [-177598381666583044/105974403705769, -121659399417402721404647785/1090941523841420218603] [-1335218610915546200/105974403705769, -980583897458924448846603980/1090941523841420218603]
143,1I [94810569/25, 922940050743/125] [379071876/25, 7385416617824/125]
142, 1 [61568710986227467806771993775/54727454720812833584888041, 15035770843224404601630250672289262022696064/404862801081772719402232087203316428661] [-121493651778952370463359660420/54727454720812833584888041, 120287786196999563903919614306662909447283156/404862801081772719402232087203316428661]
145,1I [-569393782850/806162449, -2968184179162750445/22889370414457] [-7927161573992/806162449, -23810049066526185932/22889370414457]
148,1I [174507816854/30591961, 63488181566247496/169204136291] [474709952116/30591961, 507906129346525132/169204136291]
158,1I [2786158821/4990756, 1165378563631629/11149348904] [-7594613659/1247689, 1165384138306081/1393668613]
164,1I [429460139617007378/188224982079121, 6696516546453420961637156/2582354712109303429831] [30591819110788868/188224982079121, 53582461790475804906816572/2582354712109303429831]
167,1I [222310534154/93876721, 1645499499080992/909571549769] [16564138200/93876721, 21783501340519436/909571549769]
172, 1 [5549264505504/2044396225, 2004333302224564642/92437375313375] [2039311243516/2044396225, 16035036167297770636/92437375313375]
175,1I [335662905/22801, 5874127939389/3442951] [1109899012/22801, 47195777681536/3442951]
181,1I [-16292694500/211208089, 632278184147251077/3069487157437] [-2371563109880/211208089, 5057290624209964364/3069487157437]
190,1I [358745206052548275702341545/22564302942549058507089, 6468297394252856504716447967984124935116/3389478494326077097438129088948313] [1163487131205442830852071332/22564302942549058507089, 51746392711936829342039973496389355274180/3389478494326077097438129088948313]
191,1I [15129, 1752999] [48356, 14084512]
197,1I [-5596, 263582] [-35320, 2086276]
In the remaining cases, one point has been found but APECS gives no proof
that rank <= 1. Since there is a nontorsion point, it is certain
that the rank is at least 1, and thus there are infinitely many
rational points. The only real question is whether there can be many
more beyond the ones we know about.
Case1b: If the proven upper bound on the rank is 2, and the Mestre upper
bound is less than 2, we have two independent, but both conditional, proofs
that the rank is at most 1, since either an appeal to the parity conjecture,
or an appeal to the B-SD conjecture to justify Mestre's bound, will suffice.
This can be done in many cases; here are the parameters supplied to the
APECS routine "Mest" which show the ranks to be less than 2.
67, 2, 100 [-54501/121, 19233618/1331] [-399020/121, 151476224/1331]
107, 2, 300 [1280420754/1311025, 9043901352/1501123625] [118811616/1311025, 5942682758636/1501123625]
128, 2, 1000 [792066/49, 697789254/343] [2900724/49, 5582315404/343]
187, 2I, 500 [207793548520135240010992346/42088384723360325817769, 1790974260446480835058152063696820535029/8634623149897546519454398931640853] [340591981745053002312053920/42088384723360325817769, 14498347780378019947728495917378963933252/8634623149897546519454398931640853]
Case1c: In other cases, we cannot use the parity conjecture (either
because no proven upper bound was given, or because that bound was 3
or more) but we can still prove the rank to be 1 with Mestre's procedure:
(The Mestre parameter is shown after the proven rank).
6, -1, 30 [-2, 3] [-20, 28] MW Bas
9, -1, 40 [1, 4] [-24, 36] MW Bas
15, -1, 50 [28, -50] [36, -288] MW Bas
18, -1, 80 [-42, 238] [-276, 1908] MW Bas
21, -1, 50 [1, 9] [-120, 2052] MW Bas
30, -1, 30 [6, 9] [-84, 2052] Bas
36, -1,3200 [129, 319] [84, 2556] Bas
40, 3, 100 [722, 18518] [2356, 148148]
51, -1, 300 [-26, 4909] [-972, 39168]
54, -1, 50 [174, -1733] [-276, -13860]
57, -1, 50 [-33, 345] [-2280, 70956]
63, -1, 400 [1972,83218] [6564, 673632] Bas
66, -1, 50 [-30, 500] [-2532, 108108]
72, -1, 600 [1103489553/1247689, 26345376393970/1393668613] [2257951620/1247689, 210768585826212/1393668613]
84, -1, 70 [83, 256] [636, 55404]
87, -1, 150 [656, -1056] [100, -5824]
96, -1,1200 [2377, 100641] [6436, 805132]
99, -1, 200 [19375201/7921, 72481839890/704969] [51614976/7921, 586752290676/704969]
102, -1, 150 [9845207257422/106215372649, 1661026035408709519/34616333453917643] [-13927451079540/106215372649, 362520187661304361548/34616333453917643] MW
108, -1,2500 [997, 752] [100, 6020]
117, -1, 200 [491, 33960] [-2600, 273644]
120, -1,1500 [2107/9, 60859/27] [3628, 486980]
123, -1, 400 [28165640687185/67551961, 149360820789868821284/555209567459] [112321830657456/67551961, 1195812539922182464332/555209567459]
132, -1, 900 [21397, 3109179] [79780, 24873436]
147, -1, 100 [-3272/9, 96716/27] [-20300, 734464]
156, -1, 800 [223256874357/77810041, 104559706176520310/686362371661] [7406052424260/77810041, 22584970661264526348/686362371661] MW
159, -1,1600 [2143, -3119] [144, -16380]
166, 3,2000 [-40325/9, 1940257/27] [-243956/9, 15522164/27]
177, 3, 250 [10609121884059612527193393358509363598672069/4216489864294939248323713357587084541129, 1849488829143872551255102601192353318044971238528720005154447353/273795679730722189468772898207282169644797335073220630314117] [-1600532606457895400719288872602056552863000/4216489864294939248323713357587084541129, 17551502920649953589434705332665169089975857243800664103187317772/273795679730722189468772898207282169644797335073220630314117]
178, 3I, 800 [2587, 4062] [-212, 32500]
185, 3I,1200 [2940, 6310] [352, 62244]
189, -1,1200 [6045781/121, 14755906409/1331] [22742256/121, 118313265636/1331]
192, -1, 100 [393, 1691] [1860, 365364]
(Note: for n=63 I believe an older version of APECS asserts the Mazur bound
is 1; we have not used that information here. I don't know why there is
a discrepancy but will double-check my notes.)
Case1d: In some cases, the proven upper bound on the rank is 2, but no
choice of the Mestre parameter was found to be sufficient to show the
rank is 1. In these cases, the parity conjecture still shows the rank
to be 1. (Note: I don't claim to have searched for the optimal choice
of the Mestre parameter; possibly Mestre's algorithm can resolve the
rank in some of these cases too.)
155, 2 [35507691/4, 211548880855/8] [35499683, 211584388550]
Case1e: There are some cases in which we must use BOTH conjectures:
there is no proven upper bound of 2 (or less), but Mestre's bound
shows the rank to be less than 3, and the parity conjecture rules out
rank 2 and we have a point so the rank is positive. Thus the rank is 1.
162,-1,3500 [2082, 8185] [-420, 65484] (Apecs also succeeds with L-series)
Case1f: There can also be occasions when both the parity conjecture and
the Mestre bound taken together do not lower the upper bound sufficiently
to know the rank with certainty. In that case we can still check for
the vanishing of L-series to determine the most likely rank.
No such rank-1 cases arose with n<200 (nor did any rank-2 cases require
a similar treatment).
Case1g: Sometimes the use of the parity conjecture can increase the
LOWER bound on the rank beyond what we can testify to with found
points. We assume the points exist and that we simply haven't searched
far enough into the search space. When this document was first prepared,
there were quite a few values of n listed here but, with continued
searching, we have now eliminated all of these under n=200.
For reference, a value of n recently removed from Case1g was n=187;
MWRANK had indicated that it was sufficient to find a point on one of
a set of dozens of homogeneous spaces, including
1793u^4 - 1950u^3v - 17915u^2v^2 + 13648uv^3 + 38208v^4 = w^2
which (finally!) was found to have a solution with u=-28001, v=38164,
giving the point (of height 58.97) shown in the tables, but only after
searching up through height 11.
IIE2. Curves of rank 2
Case2a: Proven upper bound = 2 and two independent points found:
As above, this means the rank is certainly 2, and of course there are
infinitely many rational points. (In some of the cases, as noted here, the
proven bound is the Mazur bound of an isogenous curve, although the Mestre
procedure or parity conjecture can also indicate the rank to be less than 3.)
41,2I, [[-110, 3313], [156,-278]] [-1000, 26068], [64, 1596] Bas
76, 2, [[770, 12008], [1652, 59874]] [1156, 96068], [4684, 478996]
77,2I, [[-656,21288], [1211/4, 53531/8]] [-4600,167684], [-765,54746]
94, 2, [[707, 1007], [2477/4, 42129/8]] [-116, 8060], [-467, 42133]
106, 2, [[-1745, 30333], [73297/64, 5857287/512]] [-10724, 242668], [13393/16, 5857543/64]
136, 2, [[6285/4, 10503/8], [1902, 25434]] [121, 10507], [1444, 203476]
149,2I, [[-2168, 158362], [1676, -13471]] [-16072,1258228], [-696,-101060]
151,2I, [[1925, -1307], [2156, 18587]] [100, -2752], [1024, 157324]
154, 2, [[-5547/4, 1362771/8], [1563, 30618]] [-13451,1362775], [-1652,244948]
160, 2, [[29218/9, 2605166/27], [2212,-6024]] [40084/9, 20841436/27],[316, -48188]
161,2I, [[4599/4, 592953/8], [-3610, 155578]] [-4041,597556], [-23080,1230188]
196, 2, [[6286, 347496], [1321030/9, 1517277077/27]] [12340, 2779972], [5168884/9, 12138216724/27]
Case 2b: In the other cases, two independent points have been found, but APECS
did not prove that the rank is at most 2. The independent points make
it certain that the rank is at least 2, and thus there are infinitely
many rational points. The only real question is whether there can be many
more beyond the ones we know about. In these cases, we can prove the rank
to be 2 with Mestre's procedure (with parameter shown). (It turns out that
in no case can we use the parity conjecture because no proven upper bound
was given at all.)
69, 175 [[311, -2960], [379, 49]] [-72,1908], [-344, -22436]
105, 300 [[793, -6773], [757, 7807]] [-504, -51012], [-648, 65484]
126, 500 [[1174, -9105], [-690, 89023]] [-596, -72836], [-8052, 712188]
129, 175 [[-245, 3290], [1351/9, -3983/27]] [-14376, 684180], [-152, -15652]
174, 200 [[90, 4854], [258, 633]] [-6852,1048572], [-804,136836]
186, 1500 [[3612, 70546], [-1842, 295978]] [2916,564372], [-18900,2367828]
195, 175 [[-98, 258097], [-3682, 354865]] [-13068, 2064384], [-27404,2824192]
As is the case in sections IIE0 and IIE1, there is the potential for
many combinations of uses of conditional tests to determine the rank to be
exactly 2, but in our range (n=1 through 200) we were fortunate not to
encounter any of these.
III. The Lists
The following is the complete set of the 111 values of n under 200 for
which the equation x^3+y^3+z^3=nxyz can be solved in nonzero integers:
3, 5, 6, 9, 10, 13, 14, 15, 16, 17, 18, 19, 20, 21, 26, 29, 30, 31,
35, 36, 38, 40, 41, 44, 47, 51, 53, 54, 57, 62, 63, 64, 66, 67, 69,
70, 71, 72, 73, 74, 76, 77, 83, 84, 86, 87, 92, 94, 96, 98, 99, 101,
102, 103, 105, 106, 107, 108, 109, 110, 112, 113, 116, 117, 119, 120,
122, 123, 124, 126, 127, 128, 129, 130, 132, 133, 136, 142, 143, 145,
147, 148, 149, 151, 154, 155, 156, 158, 159, 160, 161, 162, 164, 166,
167, 172, 174, 175, 177, 178, 181, 185, 186, 187, 189, 190, 191, 192,
195, 196, 197
Except for the case n=5, there are infinitely many solutions for each n.
The following is the complete list of the 57 values of n under 200 for
which the equation x^3+y^3+z^3=nxyz can be solved in positive integers:
3, 5, 6, 9, 10, 13, 14, 17, 18, 19, 21, 26, 29, 30, 38, 41, 51, 53, 54,
57, 66, 67, 69, 73, 74, 77, 83, 86, 94, 101, 102, 105, 106, 110, 113, 117,
122, 126, 129, 130, 133, 142, 145, 147, 149, 154, 158, 161, 162, 166, 174,
177, 178, 181, 186, 195, 197
Except for the cases n=3 and n=5, if there are any positive solutions at all
for a given n, then there are infinitely many positive solutions for that n.
The entries 73, 102, 113, 122, 130, 133, 142, 145, 158, 177, 181, and 186 of
the second list appear to be not previously known to some participants in the
Seq-Fan mailing list.
(For honesty's sake we mention again that unless we choose to take the
time to confirm the ranks using MWRANK (or otherwise), the exclusion of
other integers from these lists may be contingent upon the truth of
one or more of a set of standard conjectures in number theory. It is
my opinion that it would be a complete waste of CPU cycles to attempt
to find solutions for any of these other values of n in the hopes of
disproving these conjectures.)
IIIA. Relationship between generators and lists
Finally we give below lists of the "first" few primitive integer solutions
for each value of n in the first list; obviously the reader can pick out
the all-positive solutions from among them. Here we have the word "first"
in quotes because of three problems.
#1, the process of generating these solutions TENDS to increase the
(naive) height of the solutions, and that is asymptotically, but not
monotonically, true: "simpler" solutions can conceivably be further
down the line.
#2, the process assumes we have found the "simplest" (least MW-height)
elements, which are generators for the whole group (rather than a
subgroup of finite index). This has been checked for the smallest
values of n, but to do so for larger n requires an exhaustive search
("Bas" command) of the space of candidate points and grows quickly with n.
#3, for the few values of n in the last list, we have not even found a
generator (proven minimal or not); its mere existence is simply predicted
by the general theory and trusted conjectures.
In practice, problems #1 and #2 are unlikely to mean that we have
missed some simple solutions, but these events do occur from time to time.
For those who HAVE read the entire document up to here, we need only
remark that the first list of III consists of (1) the one curve of
genus 0 (n=3), (2) the one curve with "extra" torsion (n=5), and
(3) the curves of rank 1 or 2. The second list is the subset of
those for which the subgroup of points in the unbounded component is
a proper subgroup (of index 2) and requires only a check of the
X-coordinates of the generators (after having checked them for "doubles").
We have had to segregate out the third list since without explicit points
on the curves we cannot attempt to halve them! Finally the list below
consists simply of the positive multiples of the generator (in the rank-1
cases) or (in the rank-2 cases) the sums a g1 + b g2 of multiples of
the generators, with a > 0 or a=0 and b>0. (In this list, it is
unnecessary to add negatives of elements nor the three torsion elements,
because those operations give automorphisms of order 2 and 3 of the
elliptic curve which turn out to correspond to permutations of orders
2 or 3 of the three variables {x,y,z} in the equation x^3+y^3+z^3=n xyz.)
For those who HAVE NOT read the entire document up to here, and
because these additional elements can be obtained so systematically, we
have given above the formulas necessary to construct directly the additional
solutions for a given n, in the xyz coordinate system. When there is
only one generator, we obtain successive entries by "adding" the
generator to itself. When there are two generators g1 and g2, we
construct a g1 + b g2 (a and b integers, with a > 0 or else
a=0 and b>0) successively by adding either g1 or g2 or -g2 to
each prior element in the list. We have given explicit formulas in
section IIB which the reader may use without a detailed understanding.
These show how to compute "-P" when P is a triple (x,y,z), and
how to compute "P+Q" where P and Q are two such triples. (There
are special cases when P = Q or when P or Q have a coordinate equal
to zero.) In particular, we have given an explicit form for "3P" when
P = (x,y,z); if all coordinates of P are positive, so are those
for 3P.
For example, when n=6 and P=(x,y,z) is (1,2,3), the addition formula gives
Q = "2P" = (52, -19, -21), another solution of x^3+y^3+z^3=6xyz. Then
"3P" can be computed as "P+Q", either by using our general addition
formula or the special tripling formula; either way we get
(1817, 5275, 3258), another solution to x^3+y^3+z^3=6xyz, and an
all-positive solution at that! In this way we can construct lots of
all-positive solutions.
Remark: the addition formulas don't refer to the variable n ; but
do not attempt to "add" points on different curves using this formula --
you will create points that don't necessarily lie on _any_ curve with
an integral value of n !
IIIB. Presentation of the tables.
We show our points in the table below in the form {x,y,z}, which
stands for an equivalence class of primitive solutions (under all six
permutations and two choices of overall signs).
Warning: the order of the components does not matter in the
_presentation_ of the solutions, but does matter in their _construction_:
(1,2,3) and (2,3,1) are different points on the curve. (In our
inhomogeneous version, they correspond respectively to the points
(1/3, 2/3) and (2,3).)
We have printed for each n as many solutions as we could fit into
about 80 characters, always showing at least one (which is hard to do
especially for cases like n=187, where the generator alone takes about 120
characters to print!) In the 19 cases for which the curve has rank 2
(marked with a '*'), we have put a pair of generators first.
Of course it is possible to be more systematic but we have not taken
the effort to do so as we see little point in the construction of these
tables, once their contents are understood.
Using the formulas in IIB and the generating solutions in the table below,
the reader is invited to create as many solutions as he or she wishes
to some of the equations x^3+y^3+z^3=6xyz -- no understanding of
elliptic curves or Diophantine equations is needed at all!
I have already carried this out for the values of n shown, computing
the first ten multiples of each point, and retaining those for which
x,y,z have no more than 20 digits. Those are kept in a separate file
at the same web site.
n, {x,y,z}
-- ------
3 {1,1,1}
5 {1,1,2}
6 {1,2,3} {19,21,-52} {1817,3258,5275} {124904,2847511,-3096807}
9 {2,3,7} {133,632,-1005} {970703,2982043,4461282}
10 {5,7,18} {3924,27445,-39949} {4192875343,11021882957,19765145610}
13 {9,13,38} {55784,474075,-703859} {2197345737653,6384056084353,12689495542854}
14 {2,7,13} {3708,4355,-15323} {279025573,759054842,1638591583}
15 {1,3,-7} {91,185,-516} {26147,671769,-801173}
16 {9,31,-70} {2034340,3355119,-10655599}
17 {5,18,37} {211159,224105,-909504} {1932849997397,7649960172210,14857581287413}
18 {13,42,95} {6829645,10182731,-35917476}
19 {1,5,9} {151,279,-910} {728051,1279935,4135819}
20 {13,14,-61} {33367,2986425,-3208492}
21 {2,13,21} {14128,45969,-120289} {38304582498,44899033717,187979061005}
26 {9,38,91} {4927013,6288291,-28607996}
29 {27,43,182} {10887968,160624647,-258382055}
30 {2,21,31} {41060,286843,-625443} {907576024698,2555537666039,8213238158509}
31 {1,27,-37} {35168,364117,-683829}
35 {14,19,-97} {399155,12873448,-17392923}
36 {7,78,-151} {27422521,71605559,-268576932}
38 {70,151,629} {1949869179,17179066660,-37525793539}
40 {1,2,-9} {63,737,-1460} {502289,4268359,-9685062}
41*{1,2,9} {1,4,-13} {1,5,14} {2,31,43} {9,103,-208} {61,1133,1314}
44 {19,554,-819} {13668309737,139250151495,-304345505372}
47 {38,367,-845} {24805715544,41722712395,-221450000899}
51 {9,13,77} {28259,1022256,-1481363}
53 {2,7,27} {1809,7736,-27545} {210121627,5309015927,5755076082}
54 {2,43,57} {30196,647349,-1137565} {370030298454,3412808117911,7948993687541}
57 {19,91,310} {25720080,61301239,-301150759}
62 {1513300,1950953,-13559153}
63 {247,903,-3775} {1361350133800,6734754327197,-24295747136997}
64 {119479,232736,-1338039}
66 {1,3,14} {28,209,-633} {55075,1201649,1852326}
67 {1133,7525,23517} {1248321775926537,1781635744669913,-12232457245758050}
69*{2,57,73} {42,95,523} {676,939,-6631} {10564,39899,-171639}
70 {27083,896668,-1478979}
71 {7,9,-67} {12931,1055222,-1354977}
72 {404512675962,1012930784383,-5450170263655}
73 {89200900157319,1391526622949983,2848691279889518}
74 {133,2502,4607} {10921761369155,72146437148197,-244642267132812}
76*{2,13,-45} {1327,2196,-14911} {266,1989,-6437} {98505,186644,-1184729}
77*{67,630,1763} {133,1382,3665} {5,7,-52} {617984852,286888709233,-302735049565}
83 {5,9,61} {9211,282815,-510426} {406164641531,2343744686659,8805786469335}
84 {1,31,-56} {22823,185360,-604903} {264046351688,641207037467,-3781070788603}
86 {2,73,91} {729108,35399819,-55010099}
87 {1,5,-21} {1302,4693,-23155} {13866001,2282398335,-2681061091}
92 {548624531286,20446843218005,-35661385544981}
94*{27,182,673} {19,746,945} {2569,11111,-52056} {182836,2101059,-6133771}
96 {3,5,-38} {3724,164991,-274495} {80993577493,376883047187,-1720995246990}
98 {2559169,14154192,-59978401}
99 {1150522313,1832602198,-14466072543}
101 {79,1271,3078} {2141532398239,6318310548816,-37063297379023}
102 {459338480695732254,3816006884967068935,13212742329826830581}
103 {4,9,-61} {1159,26024,-58383} {2619142867,30685083497,-92681703468}
105*{2,91,111} {35,1171,1854} {97,3171,-6124} {38037,4367911,-5669524}
106*{1,35,54} {5697,195944,-372209} {1342,15929,46683} {114589,2315196,-5511205}
107 {83341950251,197624310994,-1329876450605}
108 {2,7,-39} {13065,119324,-415289} {21659465017,1207414568807,-1932665115654}
109 {99054267227,4035385003297,-7254524660292}
110 {1147,2745,18578} {356226463814956,7330896793887269,-17596934037664605}
112 {403909122691328588518061393542,66756829882613387041310733449793,-81634675793306734523552997069865}
113 {345842,6313383,15170275}
116 {13,739,-1204} {27935974079,485911791288,-1289806157279}
117 {545,1677,10318} {46992269360344,596093532925955,-1841855805999339}
119 {1,19,-49} {62254,168021,-1117675}
120 {496,1317,-8869} {19177421644913,347156560777312,-918936911786865}
122 {407249928739620845890,23848086141138276680923,25590382918388481967217}
123 {45191178833837,8723981310176706,-10554611259665663}
124 {75992904,1882858151,-4389003335}
126*{2,111,133} {1093,4199,23982} {245,1371,-6536} {1970012,181893859,-261141819}
127 {45,151,-931} {1560275003,18233942445,-60931944008}
128 {23611,422318,-1158179}
129*{31,774,1679} {70,629,2361} {39,76,-619} {126682669,6763090191,-11702817844}
130 {1046599292363750394389, 639905104499493910311, 16177096946436536530}
132 {39,905,-2234} {463732094631,1655747655604,-10090214441815}
133 {691440137111968428652609,8149000233894575265542178,27006382877335430051053793}
136*{45,203,-1118} {126,2797,-7141} {10791,350329,-755668}
142 {6587432496387235561093636933115859813174,53881756527432415186060525094013536917351,222932371699623861287567763383948430761525}
143 {2435,1520593,-1636453}
145 {44634584148027469,157591646586434781,1007950541819512850}
147 {21,925,1529} {14611305261,302529417014,-826614601475}
148 {71841303293459,188778746384314,-1418519131294563}
149*{1,14,45} {2,133,157} {7,148,-403} {2623,27652,-104923}
151*{9,13,-133} {9,637,-1054} {351,1393,-8611} {81385,154539,-1379209}
154*{2,13,63} {62,1183,3285} {936,58289,-101729} {11259,13244,-151619}
155 {458,442729,-466371}
156 {2433329851945933,57378032205801587,-151742066509610694}
158 {5642215349875,7336556299898,80828288788977}
159 {1,6,-31} {6665,30007,-178752} {483120431,166286747034,-191720116529}
160*{182,711,-4559} {43,1764,-3691} {8325,146963,-450338}
161*{11,38,259} {109,3933,7826} {7,8,-95} {146,6517,11349}
162 {35,1854,2881} {613899299195,18359866789309,-44334184670964}
164 {273965892543545308964986,2187625242203395484208435,-9967112990856026231233891}
166 {9,611,790} {2384458821,180197737580,-301246383581}
167 {90197542563908,868179733296745,-3641058343253213}
172 {127237919517328,16590668075015195,-23593229783585883}
174*{5,7,78} {2,157,183} {323,333,-4328} {2217,4223,-40388}
175 {1343816497,12984427575,-55614086497}
177 {11586299300246645065650175011667633294528995894742493608006903, 499128047096078689216614212030144552460525030444760940918765730, 944421945175253160922633489847006529687358187395396664036033027}
178 {2,27,97} {357196,381695,-4928391}
181 {10672860536839861,21088064331923949,201705586625136962}
185 {4,175,-379} {239197256,2031178869,-9527000525}
186*{5,67,-252} {2269,15938,81711} {11403,22774,219641}
187 {25564297137318411424451907466482829394,50621375726791887196233101919521352691,-492233837876182300994422946725623025365}
189 {209,7891,-18396} {1403810784530363,9038814254534232,-49125036148841315}
190 {297115335963207388794859858793856411,2716813894306138435285959241731689173,-12449186314350611078793751630598133592}
191 {1399,11655,-56059}
192 {38,1417,-3345} {1530353758844,9516939248145,-53034545735249}
195*{7,15,143} {39,703,2279} {948,4663,-29419} {2017,47331,-139204}
196*{18,19,-259} {4221,378995,-632186} {5785911,17022184,-139070743}
197 {127,6278,11655} {169642439406721,2883849663571695,-9939340825013776}
finis !