Jump Over Left Menu
Destructive and Constructive Computing in Number Theory
N M Stephens
The electronic computer has an obvious part to play in the Theory of Numbers. It has a powerful memory and can do arithmetic more accurately and more quickly than a human being. Its disadvantage is, of course, that whereas mathematicians are concerned with theorems which relate to an infinite class of objects, the amount of computation done by a machine is finite. (I am ignoring the contribution of theorem proving on the computer which has not yet developed enough to be significant.)
For example, consider the following conjecture
Conjecture 1: For any odd distinct primes p and q,
(pq-1)/(p-1) never divides (qp-1)/(q-1).
This conjecture is important in the sense that its validity would have eased considerably the work of Feit and Thompson in their major paper on groups of odd order, . However it has not been proved; the difficulty is that, apart from elementary considerations, the Number Theorist has no machinery with which to tackle this kind of problem. Of course, the computer may be employed to test the conjecture for different values of p and q, but the conjecture is a statement about an infinite class of pairs of primes, and, as such, no (finite) amount of verification will add any weight to its validity. However, one single counter-example is sufficient to prove its falsehood.
Consequently, there is little virtue in using a computer on a known conjecture that is expected to be true. On the other hand, a conjecture based on little evidence and little reason is fair game. The following was formulated soon after conjecture 1.
Conjecture 2: For any odd distinct primes p and q,
A = (pq-1)/(p-l) and B = (qp-1)/(q-1) have no common factor.
Clearly, the validity of conjecture 2 implies the validity of conjecture 1. But, treating A and B as two very large random numbers and using rather loose probability type arguments, conjecture 1 has a very good chance of being true, whereas conjecture 2 has not. It is easy to prove that if r is a prime number and r divides both A and B then r = 2Î»pq + 1 for some integer Î». This result makes searching for a counter-example to conjecture 2 more efficient, though less thorough; instead of computing the actual values of A and B as large multilength numbers, they may be computed modulo r, where r is of the required form. In fact, it required very little time on ATLAS to produce the counter-example to conjecture 2 with p = 17, q = 3313 and r = 112643 = 2pq+1 (see ). Further computation revealed that r is the only prime dividing A and B, so this example leaves conjecture 1 unresolved.
There is a more constructive use of computers in Number Theory than searching for counter-examples. This can take the form, for example, of obtaining a large amount of numerical evidence on what appear to be two or more unrelated phenomena and seeking relationships. Such an investigation requires intuition and is often more rewarding because it deals with structure, and structure is the essence of mathematics. Having established a numerical relationship, it is then the job of the mathematician to prove it, or, if he is unable to do so and the result is significant, to formulate his results as properly tested conjectures. The last ten years have seen some important conjectures developed in the theory of elliptic curves. The impetus came from the work of Birch and Swinnerton-Dyer by just such intelligent computer investigation.
An elliptic curve (over the rationals) is an equation
y2 = x3 - Ax - B
where A and B are given integers and where rational solutions in x and y are sought. The set of all rational solutions forms an abelian group. This means that there is an operation called addition which constructs in terms of two given solutions a third solution, and that addition obeys the laws of normal addition in arithmetic. The easiest way to view this operation is the following. Let (x1, y1) and (x2, y2) be the two given solutions and consider them as points on a curve. The line joining them has the equation
y = mx + c
where m and c are two rational numbers. This line meets the curve at a point whose x co-ordinate is given by the solutions of
(mx + c)2 = x3 - Ax - B
This equation already has two solutions, namely x1 and x2; so it has a third x3 and
x1 + x2 + x3 = m2
Hence x3 is a rational number and so is y3 = mx3+c. Addition for the curve is given by
(x1, y1) "+" (x2, y2) = (x3, y3)
This method of constructing a third point is known as the tangent-chord method; the chord is, of course, replaced by the tangent if the two given points are the same. Every curve has one point, namely the point at infinity, O, which acts as the zero element with respect to addition. Given one point on the curve, P = (x1,y1), it is possible to construct the point P+P=2P, 2P+P=3P, and so on. Either P generates an infinite number of distinct points (P has infinite order) or, for some positive integer m, mP=O (P has order m). For example, for the curve
y3 = x3 + 9
if P = (0,3) then 2P = (0,-3), 3P = O, and P has order 3, whereas if P = (3,6), 2P = (-15/16,183/64), . . and it can be shown that P has infinite order.
There are two interesting theorems concerning the group of rational points of an elliptic curve. One is that the number of points of finite order is itself finite; denote this number by f. The second is that the points of infinite order may be generated (by the tangent-chord method) by a finite number of points; denote the smallest number of generators by g.
For any particular elliptic curve, there is an algorithm (i.e. a finite procedure) for determining the points of finite order. There is also a method for determining g and the g generators; since it involves a search for rational solutions on curves associated with the original elliptic curve, it cannot be called an algorithm. There is no guarantee that the method will always work, but in practice it is, in almost all cases, efficient. Birch and Swinnerton-Dyer, , showed how this method could be programmed for the computer, and produced some data on EDSAC. Their results, and all subsequent results, indicate that g = 0 or 1 usually, g = 2 or 3 sometimes, and g â‰¥ 4 rarely.
The conjectures of Birch and Swinnerton-Dyer relate the structure of the group of rational points of an elliptic curve to the behaviour of its zeta-function. The essential part of the latter is an L-series of the form
where s is a complex variable and the integer coefficients an can be readily computed. In its most recent form, see , the conjectures state:
where h is a non-zero measure of the size of the basic generators (h = 1, if g = 0) and S is a positive integer measuring how difficult it is to determine g. See  for explicit definitions of h and S.
The conjecture is very important. For example, an immediate consequence of its truth is that, for any particular elliptic curve, L(1) = 0 implies g â‰¥ 1. Thus it can be deduced that a curve has rational points without every finding them. Such a result appears to be very deep.
The computer has played a major role at many stages of the formulation of this conjecture, for it would have been impossible to reproduce manually the extensive tables of g, L(1), etc., on which the conjectures were based. It has also usefully verified many ramifications of the conjectures.
More recently, the computer has again played a constructive part in formulating a conjecture concerning elliptic curves, . Consider the family of elliptic curves
y2 = x3 - 1728m33 ...(2)
where m is a square-free integer, and either m > 0 and m â‰¡ 2 or 3 (modulo 4) or m < 0 and m â‰¡ 1 (modulo 4). From the functional equation of L(s), conjecture 3 predicts that g is odd for these values of m. Using the theory of modular functions and algebraic number theory, it may be shown that (2) has a solution (x,y) with x and y algebraic numbers. Thus x satisfies an equation of the form
c0xn + c1xn-1 + ... + cn-1x + cn = 0 ...(3)
where the coefficients c1 are rational numbers, and similarly y. By adding (x,y) to all its conjugates (the other roots of (3)), a point (x0,y0) is obtained which has rational co-ordinates. Is this then an algorithm for determining a rational solution of (2) of infinite order? Not quite, for it may turn out that (x0,y0) equals the point at infinity or the other point of finite order, namely (12,0). Clearly a case for investigation, numerical evidence obtained on ATLAS suggests
Conjecture 4: (x0,y0) is a point of infinite order if, and only if, g = 1.
In fact the numerical evidence suggests more than this and explicitly relates the point (x0,y0) to the value of the derivative of the corresponding L-series at s = 1. Perhaps this last relation will provide a clue as to the proof of conjecture 3. If so, then the computer has played a significant and constructive part in indicating to the mathematicians guidelines for the proof. It cannot be expected to do much more.
1. Feit, W., and Thompson, J. C. (1962). A solvability criterion for finite groups and some consequences, Proc. Nat. Acad. Sci. U.S.A., 48, 968-970.
2. Stephens, N. M. (1971). On the Feit-Thompson conjecture, Maths of Comp., 25, 625.
3. Birch, B. J., and Swinnerton-Dyer, H. P. F. (1963). Notes on elliptic curves I, J. reine angew. Math, 212, 7-25.
4. Swinnerton-Dyer, H. P. F. (1967). The conjectures of Birch and Swinnerton-Dyer, and of Tate, Proc. Conf Local Fields (Driebergen 1966), Berlin: Springer, 132-157.
5. Birch, B. J., and Stephens, N. M. (1971) unpublished.