In pure mathematics one can often prove that some object with certain properties exists; such a proof gives an existence theorem. To find this object in a specific case may be another matter. However, when one can in fact do so, the reader might reasonably suppose that it was computable. Unfortunately, this word has come to have a technical meaning, that it is theoretically possible to give an algorithm and a fixed integer N, such that after at most N steps one can find the object. Those who specialise in this sort of mathematics make in addition a subtle distinction between computable and effectively computable; roughly, possible by some algorithm. and possible by the algorithm under current consideration. But none of these words. existence, computable, nor even effectively computable, means that one can actually do it, in practice. here and now.
However the history of mathematics, and of number theory in particular, is studded with examples of general conjectures made after the examination of special cases actually calculated, and the generalization finally proved (it may be easier to prove a wood than to prove trees). A famous example is the law of quadratic reciprocity. If p and q are different odd primes, we write (p/q) = 1 if the equation x2 = p + qy is soluble in integers x and y, and write otherwise (p/q) = -1. Then the law is:
(p/q).(q/p) = 1 if either p or q is of the form 4m + 1,
(p/q).(q/p) = -1 if both p and q are of the form 4m + 3.
This was certainly known to Euler, but was first proved by Gauss (who gave 8 proofs in all), and has since become the most proved theorem in number theory, around 200 proofs being known. In this case, of course, Gauss could certainly have found the law for himself (and possibly did).
Another more recent (1917) example is Ramanujan's conjecture that if
then where is interpreted as zero if n/p is not an integer. Professor Mordell, who later proved this, tells me that he would probably not have come across it on purely theoretical grounds. As a final example we may cite the highly sophisticated conjectures of Birch and Swinnerton-Dyer on elliptic curves, for which an extensive and informed computer attack was needed; these still await proof.
The electronic computer has so vastly increased the possibilities of actual calculation that one often needs to express the fact (sometimes by no means trivial) that an object can now be calculated in practice; the phrase feasibly computable, suggested to me by John Leech, is here put forward. Feasible computability is a strictly practical concept, dependent on time and place, on the machine time required in relation to the importance of the work, and so forth. For this reason it is not susceptible to rigorous definition.
I give below an easy classical example which may help to crystallise these ideas. Before this, it should be stated that this article is solely concerned with computation as an empirical aid to discovery, and not with the further problems involved when electronically computed facts form an essential part of a final proof.
One of the most beautiful results of elementary number theory is this: given any two integers (positive or negative) a and b with no common divisor greater than unity, there exist integers x and y such that ax + by = 1 .
To prove this, consider for fixed a and b the (infinite) class C of all numbers (ax + by) as x and y take all integer values; let d = ax1 + by1 be the least positive member of C. If d= 1 we have proved our theorem. We suppose then that d > 1, and establish a contradiction. If d does not divide a, then a = qd + r, with 1 < r < d, so that:
r = a - qd = a - q(ax1 + by1) = (1 - qx1) a - (qy1) b
belongs to C, which is false since r < d. Hence d divides a. Similarly d divides b. But now d > 1 is a common divisor of a and b, contrary to hypothesis, and this contradiction proves the theorem. Note that this proof of existence gives no clue at all as to how one might actually find x and y with ax + by = 1.
Next, it is easy to prove that if x1, y1 is any solution, then the most general solution is
x = x1 + bt, y = y1 - at; t = 0, ± 1, ± 2, . . .
Hence there is some solution with 1 ≤ x ≤ b (and in fact only one), so that if we computability with N = min(a,b). Up to N = 102 by hand or 107 on Atlas, this may try all these b values of x we must come across a solution. This proves effective also be regarded as feasible (while Atlas could go further, this would not be justified in terms of machine time, in view of the algorithm below).
I show finally (without proof) the feasible method, by which Stephen Muir has found solutions when a and b are as large as 10100, using the multi-length routines of Lunnon. It is best explained by example, for which I choose a = 64 and b = 537; the numbers in brackets below are given to aid the explanation, and do not form part of the calculation.
2(5) 64(1) 537(2) 8(3)
1(9) 14(6) 25(4) 1(7)
1(13) 3(10) 11(8) 3(11)
1(14) 2(12) 2(15)
0(16)
We start with our a and b (a < b) in (1) and (2), and (3) and (4) are quotient and remainder for (2): (I). Next (5) and (6) are quotient and remainder for: (1): (4), (7) and (8) for (4): (6), (9) and (10) for (6): (8), (11) and (12) for (8): (10), (13) and (14) for (10): (12), and (15) and (16) for (12): (14). When the remainder is 0 we stop, and the last divisor (here (14) must be 1 if a and b have no common divisor.
2(5) 23(22) 193(23) 8(3)
1(9) 5(20) 9(21) 1(7)
1(13) 1(18) 4(19) 3(11)
0 1(17)
We now keep the numbers in the extreme columns except for the last one ((15)), remove the middle columns, and replace the penultimate division by 1 (17) divides (13) (in fact 1 here) (18) times with remainder O. In general (17) is always 1, and (18) equal to (13). Next (19) = (18). (11) + (17), (20) = (19). (9) + (18), (21) = (20). (7) + (19), (22) = (21). (5) + (20), (23) = (22). (3) + (21). The numbers 23 in (22) and 193 in (23) are more or less our solution; in fact 64.193-537.23 = 1.
This method takes more programming (about 40 Fortran statements) than the crude method above, but its time is of the order of log(min(a,b)) as opposed to min(a,b). As a proof of effective computability, the crude method exhibited is the right proof because it is the simplest, and it is permanently valid however large a and b are. But, and this is the crux of the matter, it is only feasible for fairly small a and b, while our final algorithm above is feasible for much larger values, and with present machines no method is feasible in general if a and b are as large as 1010100 .
Of course the mathematician will recognise that this example is slightly artificial, since the theory of the feasible method could be used as a proof of existence and effective computability as well. Effective computability clearly implies existence; in some cases feasible computability may not, for one may know a feasible method is right without having proved it!
The idea of feasible computability has always been of interest to some mathematicians. Gauss in his Disquisitiones Arithmeticae (now translated into English, which has regrettably replaced Latin as the lingua franca of international science) often illuminates his general theorems both by small examples and by feasible methods for large scale hand calculation. Nowadays a decision as to feasible computability involves the possible use of computers, and the mathematician who is not competent to assess what they might be able to do for him may be unable to make it. A distinguished number theorist recently told me that he would have tried to get some tables of interest to him computed, but had assumed that a subsidiary operation would be impossibly slow. I was able to assure him that I regularly performed this operation (by proxy) in 100 microseconds. So long as this kind of misapprehension exists, the Atlas Computer Laboratory and other computer centres have a clear evangelical role to play.
Having decided that a computation is feasible, we must decide whether or not to perform it. The temptation to compute needlessly is particularly strong when a new machine makes a computation feasible for the first time. Swinnerton-Dyer is severe (though in brackets):
(At the moment, most number theoretical calculations merely pile up lists of integers in the manner of a magpie; they are neither designed to produce valuable results nor capable of doing so.)
While people may travel long distances to watch men lift heavy weights above their heads, an international convention of bulldozer manufacturers in Mexico City would be strictly a trade event. As a definitive and rigorous tour de force we may admire Shanks and Wrench's calculation of the first 100000 decimal digits of π but be incurious about the 100,001st digit. They wrote in 1961: . . . say, in 5 to 7 years . . . a computation of π to 1000000D will not be difficult. The time has come, but nobody has done it; this does not invalidate their prophecy, but merely indicates that their own work has rendered such a computation pointless. I feel that 100000 is about right; anything significant about the digits of π must show up by then (which might not have been true of 10000). Of course this is a practical, and therefore subjective, judgment. But machine time is finite, and one has to make these judgments continually.
The reader cannot expect me to quote an example of someone else's work that I regard as futile, but I can admit the possession of 2 cwt. of computed tables, of which at least 2 stone I have not even thought worth examining.
We are only considering here the value of computation in mathematics; naturally work may have value as new computational technique which has none as mathematics, and one should only condemn more of the same by the same method on a bigger machine when no reasonable hope of further discovery exists. In every attempt to discover the infinite by inspecting the finite, we have to decide when to stop computing and start thinking; this is a decision where the computer cannot replace the mathematician.
Finally, the computer has given a new lease of life to those mathematicians whose interests lie in the direction of Hardy's quotation of Whitehead: the large generalization, limited by a happy particularity. Before the electronic computer, man's powers of calculation had been static for about 200 years, despite large individual variations. A new discovery in an old subject by heuristic methods was hard to come by; those who lived later had the advantage of more developed theory, but the disadvantage of not being there first. Now they can add every few years an order of magnitude in their numerical power. Each new generation of machines makes feasible a whole new range of computations; provided mathematicians pursue these rather than merely break old records for old sports, computation will have a significant part to play in the development of mathematics. If mathematicians with machines cannot prove all that they conjecture, then at least they will provide work for others, which may be the prime virtue of the 21st Century.