by Wells, David
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
The sequence starts with 1 which has no factors apart from 1, but we don't actually count 1 as a prime, basically because a lot of theorems and formulae are simpler to express if you leave 1 from the list. (The Greeks thought that 1 was special, because it was the unity from which all the other counting numbers were generated so it is historically quite appropriate to make this exception.)
We take the first number after 1 which is 2, and cross through all the subsequent even numbers. The first number remaining is 3, so we cross out all multiples of 3, except for 3. The next number remaining is 5, so we deleted all multiples of 5, except 5, and so on.
This seems a simple process but actually it's complicated. Let's see why. In the sequence of squares, 1
2
3
4
5
6
7
8
9
10
…
1
4
9
16
25
36
49
64
81
100
…
each square is calculated from the counting number above. It could be calculated from the previous square (you could calculate 36 from 25) but it's not quite so simple and it's not necessary. The situation with the primes is quite different. As we operate Erastosthenes’ sieve, we only know what the next sieving number will be at the last moment, at the end of the previous sieving step.
There seems to be no simple way to calculate the nth prime from the number n, or from the (n −1)th prime, and indeed no such usable formula has ever been found. This is a hint that the behaviour of the primes is very irregular and that it will pose serious – but deeply fascinating! – problems. It does not mean that we can prove nothing about them, though the proofs of all but the simplest theorems are extremely difficult.
It is an obvious speculation that they go on for ever, that however far we go, we can always ‘another one’. But how might this be proved? One of Euclid's great achievements, whether or not it was his own, was to record a simple proof that they do go ‘to infinity’. He argued that if the primes were only finite in number, for example if p were the largest: 2
3
5
7
11
13
17
…
…
p
then we could calculate the product and add 1:
to get a number which is not divisible by any of the primes from 2 up to p and therefore must either be prime itself or have a novel prime factor. Either way, our assumption that 2 to p is the set of all the primes is false.
Prime pairs
Jot down the first few prime numbers, and it is impossible not to notice that some of them come in pairs:
An instant conjecture – the twin prime conjecture – is that just as there are an infinite number of primes, there is an infinite sequence of prime pairs. They may become rarer as they get larger – we would expect that too – but there will always be another one. This is believed but has not been proved.
Following the twin prime conjecture, it is natural to notice runs of primes such as 5–7–11 or 11–13–17 or 17–19–23, where the differences are always 2 then 4, and to conjecture that they also go on for ever. Easy to conjecture but difficult to prove! However, progress has been made. Many years ago, in 1923, G. H. Hardy and his long-time collaborator J. E. Littlewood published a paper containing a series of more than a dozen bold conjectures: bold, but based on their extraordinarily deep understanding of prime number theory and their own original methods. These included a formula for the expected number of twin primes; a conjecture that all prime patterns such as 5–7–11 and 5–7–11–13 and even 5–7–11–13–17 (with differences always 2, 4, 2, 4) are also infinite in number; and a formula for the number of primes of the form n2 + 1 [Hardy & Littlewood 1923: 1–170].
How do you conjecture a complicated formula? As we said, Hardy and Littlewood had a profound understanding based on many years of research and many brilliant insights: on that kind of foundation, you can take a risk and be bold and specific. It is a mark of their profundity that not one of their conjectures has been disproved though neither have they been proved.
The limits of conjecture
The history of prime numbers is indeed a history of experiment and conjecture as Hardy said but it doesn't follow that it could stay that way for ever. The harder the questions asked, the less reliable direct experience became. The early prime number theory of Fermat and his successors turned into, during the nineteenth century, analytic number theory, which exploited the calculus and complex variables to prove very profound theorems indeed. So G. H. Hardy, a master of the theory, issued a warning:
Some branches of mathematics have the pleasant characteristic that what seems plausible at first sight is generally true. In [analytic prime number] theory anyone can make plausible conjectures, and they are almost always false.
[Hardy 1915: 18]
Elsewhere, Hardy pointed out that,
It is comparatively easy to make clever guesses; indeed, there are theorems, like ‘Goldbach's Theorem’, which have never been proved and which any fool could have guessed.
[Hardy 1940: 19]
Goldbach (1690–1764) had conjectured in 1742 that every even number greater than 2 is the sum of two primes. The first few cases are easy to check:
and so on. We might guess, with as little effort as Goldbach, that almost all even numbers are the sum of two primes in more than one way. Yet it is still a conjecture today, although usually referred to as Goldbach's theorem. What we do know is that every sufficiently large odd number is the sum of three primes, and that almost all even numbers are the sum of two.
A Polya conjecture and refutation
Could Goldbach's theorem be false? History does offer some warnings. In 1919 George Polya compared the positive integers less than or equal to N with an odd number of factors and those with an even number of factors, and noticed that the former are apparently never less numerous than the latter.
Calling the number of positive integers less than or equal to N with an odd number of factors, ON, and those with an even number of factors, EN, then:
Experimental calculation showed that this conjecture was certainly true for many small numbers and it was rather assumed to be true for all numbers. Then, in 1958, it was proved that it is not always true: there are an infinite number of exceptions. Four years later, R. S. Lehman found the first counter-example to Polya's conjecture and in 1980, M. Tanaka found the smallest counter-example, 906150257 [Haimo 1995].
With the arrival of high-powered computers in recent years modern experimental mathematics has taken off, and it is even clearer that the mathematicians motto ought to be ‘caveat computat’, as the Borwein brothers put it in presenting seven misleading equations which look as if they might be true but are in fact approximations correct to at least 30 digits and in one case to 18000 d
igits and in another to more than 1 billion digits [Borwein & Borwein 1992: 622].
The limitations of experiment
Experiment is vital to mathematics, but it has its limitations. Suppose that Cardan and later mathematicians had been content to find the roots of polynomials by experiment. They could have found approximations to the solutions relatively easily – and we can do so almost instantly using modern computers – but if they had been content with so feeble an approach they would have missed the profound and profoundly creative ideas of complex numbers and group theory. On the other hand, if you could input the coefficients of a set of cubics into a computer program together with the solutions for each as calculated approximately, and the output was a formula linking the two sets of data then although you would initially have no idea why that formula worked, you would have some excellent clues to the deeper answer. All mathematicians are detectives and experiment can be a brilliant means of collecting clues.
Experiment has another side: possible failure. Not all experimental results are quite what they seem. Just as an apparently logically watertight proof can contain a hidden flaw, a pattern spotted in experimental data may look convincing yet actually be on further investigation, a chimaera. Here are two examples, one from number theory and the other from geometry. The first could be spotted by a bright school pupil, the second actually was.
The figure below is Pascal's triangle, also known as the binomial triangle because it appears in the coefficients of (1 + x)n. 1
1
1
1
2
1
1
3
3
1
1
4
6
4
1
1
5
10
10
5
1
1
6
15
20
15
6
1
and so on…
Each number is the sum of the two numbers above it, left and right. The next figure is a variant, called the trinomial triangle because its terms appear when you expand (1 + x + x2)n. 1
1
1
1
1
2
3
2
1
1
3
6
7
6
3
1
1
4
10
16
19
16
10
4
1
1
5
15
30
45
51
45
30
15
5
1
and so on…Each number is the sum of the three numbers immediately above it and to the left and right.
The central column, 1, 1, 3, 7, 19, 51,…is the central trinomial sequence t(n) which appears in many combinatorial problems. For example, t(n)/3n is the probability that in a three-candidate race with n voters, two specified candidates will get the same number of votes.
How could we predict the terms of this sequence without constructing the whole triangle?
Any school pupil with experience of trying to answer puzzles about continuing sequences will think of comparing successive terms to see how rapidly they are increasing. In this case, each term is a bit less than 3 times the previous term so we calculate 3t(n) − t(n + 1) and see what the differences look like:
Bingo! If we ignore for the time being the annoying first two terms, then the sequence 2, 6, 12, 30, 72…is made up of simple ‘round’ numbers which can be factorised as in the next row as products of pairs of consecutive integers. What's more, the first numbers in each pair of factors make the sequence of Fibonacci numbers, F(n) in which each number is the sum of the previous two:
This pattern looks very convincing, going on for seven terms, but just to check it we calculate a bit farther:
And now we see that the pattern fails because 21·22 = 462 and not 464. Similarly, 1206 is a miss: 34·35 = 1190, rather than 1206.
The great Euler, who was a genius at spotting patterns of all kinds, spotted this one and its failure, and write a short paper on it, Exemplum memorabile inducionis fallacis, or A Memorable Example of Fallacious Induction [Andrews 1990] [Villegas 2007: 121 and 92–112] [Euler 1760b].
Now for a misleading geometrical figure. Daniel Schultz was 12 years old when he decided to explore a typical triangle with the quarter points marked on the sides. Joining the quarter points makes two triangles which overlap to make a hexagon (Figures 12.1, 12.2).
Figure 12.1 Schultz basic figure
Figure 12.2 Schultz figure with ‘parallel’ lines
It looks very much here as if the lines JH and KG are parallel, and when Daniel repeated his experiment by drawing several differently shaped triangles, these lines did always seem to be parallel – but appearance is no proof.
By using weighted averages, which Daniel was taught especially so that he could use them for this problem, he could calculate the locations of every point in Figure 12.3 in terms of the vertices, as J has been calculated in the figure. In particular, he was able to treat JH and KG as vectors and check if they really are parallel.
Figure 12.3 Schultz figure showing weighted averages
It turns out JH and KG are not parallel, but that 4JH/5 − KG = AB/20. Since JH, KG and AB all ‘point in much the same direction’ we can see why JH and KG seem to the naked eye to be genuinely parallel, though they are typically a fraction of a degree apart. Only as the triangle becomes more and more obtuse does it become obvious that they are not parallel [Wells & Schultz 2008].
This negative conclusion can be easily checked with any dynamic geometry program, but that raises a further question: if Daniel had started by using a computer, he might have spotted the apparent parallelism, paused, wondered for a moment, moved one of the vertices to check his suspicion, realised that the appearance was false and moved on, all in a few seconds. Would he have thus gained or lost? I think he would have lost. The appearance is very surprising and deserves to be investigated further, by calculation, because only exact calculation – which amounts to a proof – will reveal what is actually going on ‘behind the appearance’.
Proof versus intuition
Logic merely sanctions the conquests of intuition.
[Jacques Hadamard]
Hadamard (1865–1963) was a truly great mathematician but not all mathematicians would agree with his judgement. Gauss published six proofs of his quadratic reciprocity theorem during his lifetime and a seventh was found in his papers. Yet he was no doubt convinced it was true by experiment, and his first proofs were not erroneous, so why the multiplication?
Proofs do far more than logically certify that what you suspect, or conjecture, is actually the case. Proofs need ideas, ideas depend on imagination and imagination needs intuition, so proofs beyond the trivial and routine force you to explore the mathematical world more deeply – and it is what you discover on your exploration that gives the proof a far greater value than merely confirming a ‘fact’.
Of course, the proof must be solid. William Thurston is a brilliant geometer with a wonderful intuition and imagination. Here he is on what he means by a good proof:
I’d like to spell out more what I mean when I say that I proved this theorem. It meant that I had a clear and complete flow of ideas, including details, that withstood a great deal of scrutiny by myself and by others. Mathematicians have many different styles of thought. My style is not one of making broad sweeping but careless generalities, which are merely hints of inspiration: I make clear mental models, and I think things through…My proofs have turned out to be quite reliable. I have not had trouble backing up claims or producing details for things I have proven. I am good at detecting
flaws in my own reasoning as well as in the reasoning of others.
[Thurston 1994]
Not all mathematicians have been as rigorous as Thurston. Saunders MacLane reported that in Italy during the years 1880–1920 a number of results in algebraic geometry were published without careful proving. The situation became so bad that it was jokingly said that a triumph for an Italian algebraic geometer consisted in proving a new theorem and simultaneously proposing a counter-example to the theorem. As a result Italian results in algebraic geometry were discredited until several mathematicians, including Emmy Noether whom we met earlier, cleared up the disputed points by applying much more rigorous standards of proof [Hanna 1996: 2].
A too-scientific approach to mathematics also has its risks. Induction can refer both to a sound mathematical method of proof, and to the use of scientific induction within mathematics. As we have seen, induction within mathematics is common enough and rightly so but if you don't prove what you've induced, you could be in trouble. Ramanujan, genius though he was, occasionally fell into this trap, and was criticised by Hardy who believed that nothing but absolute rigour would suffice in number theory, if mistakes were to be avoided. Littlewood wrote of Ramanujan:
His intuition worked in analogies…and…by empirical induction from particular numerical cases…The clear-cut idea of what is meant by a proof…he perhaps did not possess at all. If a significant piece of reasoning occurred somewhere, and the total mixture of evidence and intuition gave him certainty, he looked no further.
