Friday, May 9, 2014

Mersenne's Numbers (R.T. Gould / Fermat)

Found - a fascinating forgotten work Oddities: A Book of Unexplained Facts (Allan, London 1928) by R.T. Gould. Rupert Thomas Gould (1890 – 1948), was a lieutenant Commander in the British Royal Navy noted for his contributions to horology. While in the navy in WW1 he suffered a nervous breakdown. During long recuperation, he was stationed at the Hydrographer's Department at the Admiralty, where he became an expert on various aspects of naval history, cartography, and expeditions of the polar regions. He gained permission in 1920 to restore the marine chronometers of John Harrison, and this work was completed in 1933. Jeremy Irons played him in Longitude, a dramatisation of Dava Sobel's book about John Harrison Longitude: The True Story of a Lone Genius Who Solved the Greatest Scientific Problem of His Time, which recounted in part Gould's work in restoring the chronometers.

Something of a polymath, he wrote an eclectic series of books on topics ranging from horology to the Loch Ness Monster. He was a member of the Sette of Odd Volumes (Brother Hydrographer) and the book Oddities is dedicated to the club. He was a science educator, giving a series of talks for the BBC's Children's Hour starting in January 1934 under the name "The Stargazer", and these collected talks were later published. He was a member of the BBC radio panel Brains Trust. He umpired tennis matches on the Centre Court at Wimbledon on many occasions during the 1930s. This is his chapter on Marin Mersenne (and of course Fermat). The reference to Mr R.E. Powers 'an American computer' dates the book, back then it meant 'one who computes..'
r on

MERSENNE'S NUMBERS 

  Many, I have no doubt, have heard of the enthusiastic Don who once proposed a toast to "Pure Scholarship", coupling with it the pious aspiration, "And may it never be of any damned use to anybody". Like most other exemplary and edifying fables, it has been fathered upon many people and located in many places.

  There is one department of human knowledge concerning which we may safely assume that this aspiration will always be fulfilled. The utility of the various branches of mathematics is, generally speaking, in inverse ratio to their purity; and even though the abstruse results of non-Euclidean geometry and similar studies are now finding comparatively practical applications in the Theory of Relativity and quantum mechanics, most of us are willing to take such matters on trust, confident that, even if there is an omitted symbol or other loose screw in the reasoning, no shipwreck, structural collapse, or other practical inconvenience can possibly result.

  And of no branch of mathematics is this more true than of the Theory of Numbers.
It is so utterly devoid of practical value, and so remote from the normal interests of even the majority of mathematicians, that most of the latter have discreetly left it alone. It is a fascinating subject, but one of very limited appeal.

  During the seventeenth and eighteenth centuries, the foundations of modem, mathematics were well and truly laid by hundreds of willing hands. Yet in the same period there were but four first-class mathematicians–Fermat, Euler, Legendre, and Lagrange–who can be said to have advanced the Theory of Numbers beyond the point at which it had been left by Diophantus some twelve centuries before.

  Their work is curiously related. Several of Fermat's results were left in the form of theorems–statements professing to be true, but not accompanied by a proof About a century later, these proofs were, in most cases, supplied by Euler; who, in turn, left some similar theorems to await proof at the very capable hands of Lagrange. Lagrange also supplied the missing proofs for most of Fermat's remaining theorems. But not for all. The Theory of Numbers is one of those branches of mathematics which are peculiarly prolific of unsolved puzzles. From the eighteenth century down to quite recent times we are constantly finding cases in which some mathematician has enunciated a theorem relating to the Theory of Numbers and has omitted to supply its proof. We believe that the theorem is true in one or two cases it is practically certain that such is the case-but in the present state of mathematical knowledge such proof is not forthcoming; if it ever existed, it has perished with its discoverer.

  It may seem almost incredible that Fermat,* for example, who died on January 12 1665, should have been able to discover valid theorems which none of his successors, equipped with mathematical weapons of which he could never have had any conception, has ever succeeded even in proving; but there is practically no doubt that such is the case. The famous and apparently simple "Fermat's Last Theorem" provides an excellent demonstration of the fact.

* Pierre de Fermat, Counsellor to the parliament of Toulouse.

 Equations such as x2 +y2 = z2, x3 + y3=z3, ... xn + yn = zn are algebraical commonplaces. In arithmetic, it is perfectly simple to find integers (whole numbers) which, if substituted for x, y, and z in the first of these equations, will satisfy it. Thus,
 
32 + 42 = 52.

  But, according to Fermat, it is impossible to find any integral values whatever for x, y, and z which will satisfy the equation xn + yn = zn if n is any integer greater than two. In other words, the sum of the squares of two whole numbers can be a square; but the sum of two cubes can never be a cube, the sum of two fourth powers can never be a fourth power, and so on for ever. The same holds good, mutatis mutandis, for the differences of such powers.

  Nothing, apparently, could be simpler than such a theorem-nothing, certainly, has been found harder to prove. The best result up to date has been a demonstration, based on an investigation published by Kummer in 1849, that the theorem is certainly true for all values of n up to 100, and for many higher values complying with certain conditions.† But that is not in the least the same thing as a general proof None such has yet been given: although a money prize offered in 1907 produced, within three years, a crop of over a thousand false proofs.

† Professor L. E. Dickson, of Chicago, has shown, for example, that if x, y, and z are prime to n, the equation is definitely impossible for all values of n up to 7,000. There is some ground for suspecting that, for cases in which this relation does not obtain, Fermat's theorem does not invariably hold good. 

  It has been seriously questioned whether Fermat himself possessed such a proof. It is a question of assertion v. improbability. He definitely stated that he had a general demonstration of it–demonstratio mirabilis sane‡–-and the balance of evidence seems to be in his favour. It awaits rediscovery.

‡ He enunciated the theorem in a Latin note on the margin of his Diophantus, adding (I translate) ". . . of which matter I have found a wonderful and valid proof. This narrow margin cannot contain it".

  A famous feat of factorizing which he performed in 1643 affords another example of his extraordinary powers. Having received a letter inquiring whether the number 100,895,598,169 possessed any factors, he replied by return that it was the product of 898,423 and 112,303.* Both of these numbers, as he pointed out, are primes; i.e. they have no factors except themselves and 1. The enquiry was certainly addressed to the right man, and its result suggests that Fermat possessed some test for rapidly determining whether any given number is prime or not. No general test of the kind is known at the present day.

* It seems probable that Fermat was accustomed to factorize large numbers by expressing them as the difference of two squares–a method to which reference is made in the collected edition of his works (Æuvres de Fermat, 3 vols., Paris, 1891, 1894, 1896).

  The existence of some such test is also suggested by the case of "Mersenne's Numbers"–in all probability a third puzzle provided by Fermat for the bewilderment of later mathematicians. Before going into it, one or two general remarks may be useful.

  Prime numbers (I apologize for the repetition) have no factors except 1 (and themselves). When they are small, their recognition is easy. Most people, for example, know that such numbers as 17 and 37 are primes. But it is not so generally realized that there is no limit to the size of prime numbers; and this fact tends to go unrecognized because when an odd number runs into four–or even three–figures it is almost impossible for the ordinary man to say, off-hand, whether it is prime or not.

  There is, in fact, only one case on record of a person possessing the ability to factorize mentally, and at sight, any number less than 1,000,000. He was Zerab Colburn (ob. 1840), the American "calculating boy". When in London in 1812, being then aged eight, he was asked for the factors of 247,483, which he at once gave as 941 and 263 (both primes)–while on being asked for the factors of 36,o83 he replied that it had none. The ordinary man would see no immediate difference in kind between 36,083 and 36,087–yet the first is a prime, while the second is divisible by 3.

  But when dealing with primes running into billions, the "calculating boy" and the ordinary man are equally helpless, and even the professional mathematician is far from happy. As a curiosity, I subjoin the largest number which is definitely known to prime. It happens to be one of Mersenne's (2127 - 1) as will be seen later.


170,141,183,460,469,231,731,687,303,715,884,105,727

  The fact that it is to be prime was established by E. Lucas in 1876-7, and verified by E. Fauquembergue in 1914

Composite numbers are those which can be resolved into factors. All composite numbers belong to one of three classes–abundant, deficient, and perfect numbers–depending upon the relation which they bear to the sum of their factors. For example, of the three numbers 24, 28, and 3 2, 24 is abundant: the sum of its factors–12, 8, 6, 4, 3, 2, and 1–is 36. 28 is perfect–the sum of its factors is also 28. And 32 is deficient, for its factors only total 31.

  The great majority of composite numbers are deficient or abundant. There are, by the way, certain pairs of numbers, one abundant and one deficient, which are called "amicable numbers", and stand in a curious relation. Such are, for example, 220 and 284. 220 is abundant; the sum of its factors is 284. 284 is deficient; and the sum of its factors is 220. 1,184 and 1,210 are another pair of the kind.*

* The discovery of this pair, remarkable for their very small difference in value, is due to Nicolo Paganini, who announced it in 1866, being then aged sixteen. It may be noted that he is not identical with the famous violinist-who died in z84o.

 Perfect numbers are very rare indeed. There are two (6 and 28) in the first hundred whole numbers; but there are only four in the first million and seven in the first billion. The eighth is no less than


2,305,843,008,139,952,128.

The largest known perfect number is produced by multiplying 2127 – I (previously quoted) by 2126. I have never seen the result in print, but it has been computed at least three times in recent years–by Mr. R. W. Hitchcock (1934), myself (1935), and Mr. E. T. Hall (1942). As all three calculations are exactly accordant, it is safe to accept


14,474,011,154,664,524,427,946,373,126,085,988,481,573,677,491,474,835,889,066,354,349,131,199,152,128

as the largest number at present known to be perfect. Anyone, with a good deal of time on his hands, who doubts the fact has my full leave to test it by factorising, and summing the factors: but while so far I have shirked this–and shall continue to do so–I am none the less confident that the statement is correct.

  The reason for this confidence is that we know, and have long known, the formula governing the form of a perfect number–in other words, the recipe for making them. A great part of the work done on the theory of numbers has dealt with the forms of numbers–for it is quite a mistake to imagine that all numbers are much of a muchness. They can be classified into a very large number of quite well-marked divisions, possessing the most unexpected properties.

  For example, all prime numbers greater than 3 are of the form 6n ± 1.* That is to say, any such number is within 1 of being divisible by 6. But this is only the beginning of their analysis. They can be further classified into four principal forms and twenty-six sub-forms. The leader in this department of analysis, the "partition of numbers", was Fermat, and after him Lagrange; but in modern times its branches have flowered into such a profusion of "congruences", "residues", "ideal primes", "indeterminates", ternaries", "sets of points" and other blossoms of mathematical terminology as would make them stare to see.

* It is not, of course, true that all numbers of this form are prime. Such an assumption would constitute a good specimen of the "converse fallacy of accident". 35, for example (5 x 7) is of the form 6– 1, and 55 (5 x 11) of the form 6+ 1.

  The form of all even perfect numbers has long been known; and it may be noted that there is some ground for supposing that no odd number can be perfect. No number of the kind is known to exist†-on the other hand, no general proof has yet been given that such a number is an impossibility. As the result of the combined though scarcely simultaneous labours of Euclid and Euler, it is known that all even perfect numbers are of the form


2p—1 (2p—1),

when (2p—1) is a prime: and, also, that all numbers of this form are perfect.

† If any does, it must exceed 2,000,000–and, as shown by J. J. Sylvester, it must contain at least six prime factors.

  The computation of large perfect numbers, therefore (if anyone should wish to spend his time in such a manner), depends upon our being able to determine whether a given value of p makes (2p—1) a prime or not. And at this point we necessarily come across the very remarkable statement published by Mersenne in 1644.

  Marin Mersenne (1588–1648) was a Frenchman who joined the Franciscan brotherhood and was, for some years, the head of a convent at Nevers. Most of his time, however, was spent in mathematical correspondence. Like his successor Collins (1625–83) in England, he acted as intermediary between all the leading mathematicians of his time, and became, in effect, a one-man "Bureau of Mathematical Information". In the preface to his book, Cogitata Physico-Mathematica, published in Paris in 1644, there appeared his celebrated statement respecting certain numbers of the form 2p—1.

  These numbers are now generally known as "Mersenne's numbers", a name introduced by the late W. W. Rouse Ball, of Trinity College, Cambridge. It is worth noting, however, that Rouse Ball, who had made a special study of the subject, was firmly of opinion that the statement in question was actually due to Fermat, one of Mersenne's most constant correspondents.* This has not been definitely established, but it appears most probable. Mersenne's own language suggests that the statement did not originate with himself, but had been communicated. In addition, he was quite an ordinary mathematician, not at all likely to propound a problem which has baffled, in part, all succeeding attempts to verify it. On the other hand) such a feat was, from what we know of Fermat, well within his capacity–while there is no other mathematician of the time, except Newton, of whom the same can be said.

* It is, however, possible that the statement was communicated to Mersenne by Frénicle, another contemporary French mathematician. He did a good deal of work in connection with the theory of numbers, but is best known by his researches upon the subject of magic squares.

  Following Rouse Ball (of whose work on the subject, embodied in the various edition of his Mathematical Recreations and Essays, I have made free but, I hope, not unfair use) Mersenne's statement–or, rather, Fermat's–can be distilled out of its original Latin and boiled down to this.

  "For values of p from 1 to 257, the expression 2p – 1 is a prime when p is 1, 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, or 257; in all other cases it is a composite number."

  Actually, as it stands, this statement is not quite correct. Of the numbers given, 67 should be 61; Mr. R. E. Powers, an American computer, showed in 1911–14 that 2p – 1 is prime, not composite, when is 89 and 107; and in 1926 Kraitchik† showed that 2257 – 1 was composite. As will be seen, these errors have caused the statement to be regarded, by a very competent judge, as a mere guess.

† His result was verified by Lehmer in 1930.

  Apart from these corrections it appears, so far as it has been verified, to be true. Its interest resides in the fact that our present mathematical knowledge does not enable us to discover, in some cases, whether it is true or not; and, while it can hardly have been either due to sheer guesswork or laboriously verified in every case, the principle on which (presumably) it is based remains to be rediscovered.

  The difficulty of verifying it is largely due to the huge size of some of the numbers which have, if possible, to be factorized. For example, when p is 257 the resulting 2p—1 contains 78 figures.

  The number of cases which have to be examined is fifty-six; the prime values of p between 1 and 257 inclusive–for if p is composite, so is 2p—1. Of these, it is stated (with the corrections previously indicated) that 43 values of p make 2p—1 a composite number, and that 13 make it a prime. So far, all of the former cases have been verified, and 7 of the latter. There remain six values of p – 157, 167, 193, 199, 227, and 229–for which at present the statement has still to be verified. They yield, in all cases, values of 2p—1 running into a large number of figures, and it is known that none of these values possesses any factor less than a million. According to Fermat, 2p—1 is composite in all six cases.

  The history of the problem, which has attracted many eminent mathematicians from Euler onwards) shows) as might be expected, that it has been found relatively easier to factorize the numbers than to show that they are prime. For example, Euler discovered the factors of 2251 – 1, but the highest number which has been definitely shown to be prime is 2127 – 1. In certain cases, factors of 2p – 1 are known even for much higher values of p than any of Mersenne's numbers: for example, R. Niewiadomski showed in 1913* that 4,567 is a factor of 2761 – 1; and one factor of 2967 – 1 is known.

* L'Intermédiare des Mathématiciens, vol. 20 (1913), pp. 78, 167.

  In view of that fact that at present we are unable even to test Fermat's statement exhaustively, it is difficult to question the view expressed by Rouse Ball, who speaks of "Mersenne's numbers" as "one of the unsolved riddles of higher arithmetic", and remarks:

  ". . . It is impossible to believe that the statement made by Mersenne rested on an empirical conjecture, but the puzzle as to how it was discovered is still, after more than 250 years, an unsolved problem."

  On the other hand, it is only fair to point out that a very definite opinion of a contrary kind has been expressed by a distinguished mathematician of our own day, Professor G. H. Hardy, of Cambridge. In a paper read before the mathematical section of the British Association in 1922, he remarks:

  . . . "The bubble has at last been pricked. It seems now that Mersenne's assertion, so far from hiding unplumbed depths of mathematical profundity, was a conjecture based on inadequate empirical evidence, and a rather unhappy one at that. It is now known that there are at least four numbers about which Mersenne is definitely wrong; he should have included at any rate 61, 89, and 107, and he should have left out 67. The mistake as regards 61 and 67 was discovered as long ago as 1886,† but could be explained with some plausibility, so long as it stood alone, as a merely clerical error. But when Mr. R. E. Powers, in 1911 and 1914, proved that Mersenne was also wrong about 89 and 107, this line of defence collapsed, and it ceased to be possible to take Mersenne's assertion seriously.

† By Seelhoff (but, earlier, by Pervusin–in 1883). Seelhoff's proof is not flawless. Lucas had already found, in 1876-7, that 267 - 1 was not a prime. (R.T.G.)

  "The facts may be summed up as follows. Mersenne makes fifty-five assertions, for the fifty-five primes from 2 to 257- Of these assertions, forty are true, four false, and eleven still doubtful. Not a bad result, you may think; but there is more to be said. Of the forty correct assertions many, half at least, are trivial, either because the numbers in question are comparatively small, or because they possess quite small and easily detected divisors. The test cases are those in which Mersenne asserts the numbers in question to be prime; there are only four of these cases which are difficult and in which the truth is known; and in these Mersenne is wrong in every case but one.

  "It seems to me, then, that we must regard Mersenne's assertion as exploded; and for my part it interests me no longer. If he is wrong about 89 and 107, I do not care greatly whether he is wrong about 137* as well or not, and I should regard the computations necessary to decide as very largely wasted. There are so many much more profitable calculations which a computer could make."

* In an earlier portion of his paper, Professor Hardy had alluded to 2137 – 1 as the smallest Mersenne number whose prime or composite character was still (1922) an open question. Actually it had been shown by Fauquembergne, in 1916, to be prime–as Fermat said. The smallest Mersenne number still (1944) unverified is 2157 – 1.

  With the last sentence of Professor Hardy's remarks I entirely agree; but with regard to the remainder I must say that while he has performed the functions of Advocatus Diaboli with candour and efficiency, and while I am far from imagining that I am competent to argue a mathematical question of this kind with him, it seems to me that there is a good deal to be said, on general lines, for the view taken by Rouse Ball (with whom I used to have very pleasant and, on my part, profitable correspondence on one or two mathematical subjects).

  In the first place, I agree with Rouse Ball in regarding Fermat's inclusion of 67 and his omission of 61 as due to a misprint. Mersenne's book was a large one; the statement (in which one or two simple misprints are extremely obvious) occupies an incidental and quite unimportant position in the preface, not in the body of the book; and while mathematical works of the seventeenth century were, as a class, more carefully printed and corrected than most other books, they are, as a rule, very far from flawless. If this view be accepted, it at once reduces Fermat's errors from five to three.

  The omission of p = 89 and p = 107, and the incorrect statement respecting p = 257, are more serious; but I cannot see that they should be regarded as outweighing the great preponderance of cases in which Fermat's statement has been shown to be correct–a preponderance which would still be sufficiently striking if we threw into the other scale all the cases yet waiting to be verified. Nor do I consider that it is quite fair to pass over in silence the remaining half of the "forty correct assertions" merely because they relate to composite numbers. Several of these assertions were so far from being "trivial" that their verification required a great deal of most laborious numerical work; and their correctness is surely no less convincing testimony than that of the numbers asserted to be prime.

  If Professor Hardy bad written his paper twenty years later he could, of course, have strengthened his case materially by adducing Fermat's erroneous statement that 2257 – 1 was prime; but on the other hand he would have had to weaken it in respect of his totals of "true", "false", and "doubtful" assertions. At present, out of Fermat's fifty-six* assertions forty-seven are now (1944) known to be true, and three† false, while six are still doubtful.

* Fifty-five if, for technical reasons, we do not regard 1 as a prime.

† Assuming that his "67" is a misprint.


  The real objection to the "conjecture", I suggest, is one which Professor Hardy has only implied. The theory that Fermat's statement was not empirical but proceeded from real knowledge presupposes, or at least suggests, that he possessed (as already remarked) some means of rapidly ascertaining whether a given number, of any size, was prime or composite. If he possessed such a test, it is difficult to understand how he failed to detect the true character of 2p – 1 when p is 89, 107, or 257. It may have been a simple oversight–the history of science is full of such blunders, committed by the keenest-witted men. Or it may have come about through a mere numerical error, for it can scarcely be assumed that even a test of the kind indicated could be applied without a good deal of calculation. That Fermat had, or thought he had, such a general test is strongly suggested by a later passage in Mersenne's preface, which contains the startling assertion–impossible to test by any known method–that there are no values of p between 17,000 and 32,000, or between 1,050,000 and 2,090,000, which make 2p – 1 a prime.

  For completeness, I may point out that Rouse Ball had not overlooked the error respecting 89 and 107‡ when he published his considered opinion, already quoted, as to the problem still presented by "Mersenne's Numbers".

‡That respecting 257 was not discovered until after his death in 1925.

  It may be of interest to add one or two details of other theorems of the kind which still await proof. Apart from Fermat's Last Theorem there are, for example, these:–

  Euler's Biquadrate Theorem.–The arithmetical§ sum of the fourth powers of three numbers cannot itself be a fourth power; in other words, a4 + b4 + c4 = d4 cannot be solved numerically.

§ This is not true of their algebraical sum: Euler himself pointed out that a4 + b4 + c4 = d4 is satisfied by a = 542, b = 103, C = 359, d= 514.

  Goldbach's Theorem.–All even numbers can be expressed as the sum of two primes. At present the proof of this depends upon that of another theorem,, enunciated by Riemann, which is also believed to be true, but at present defies proof. In view of its somewhat formidable appearance, and the high cost of mathematical type, I refrain from giving it here.

  Lagrange's Theorem.–Every prime of the form 4n – 1 is the sum of a prime of the form 4n – 1 and of twice another prime of the same form. Lagrange reached this result by induction, but could not prove it.

  Various theorems dealing with the partition of numbers, and for which a rigorous demonstration is lacking, have also been enunciated, in quite recent years, by the late Srinavasa Ramanujan, F.R.S., of Cambridge. In fact, the field for the amateur computer who decides to devote his time to clewing-up some of the loose ends of the Theory of Numbers is a wide one; and, as Professor J. B. S. Haldane has indicated in his Possible Worlds,* it offers useful employment even for circle-squarers.

* Possible Worlds, J. B. S. Haldane (London, 1927), p. 173–in the essay "Scientific Research for Amateurs".

No comments:

Post a Comment