Mathematics, rightly viewed, possesses not only truth, but supreme beauty - a beauty cold and austere, like that of sculpture.
-- Bertrand Russell (1872 - 1970)
Proof is the idol before whom the pure mathematician tortures himself.
-- Sir Arthur Eddington (1882 - 1944), The Nature of the Physical World
Validity is the first test of proof. That is, a proof should be correct.
We shall define a great proof as a proof distinguished by beauty, surprise, and economy of a significant mathematical statement.
We shall define a significant mathematical statement as one that has wide applicability in the branch of mathematics in which the statement is made.
What is beauty in proof?
Since a quest for the answer would make us wander, we shall use the following as the definition of beauty in proof. A beautiful proof is one that evokes an aesthetical experience - consider all words in this sentence as undefined terms so that the discussion will rest!
Surprise in proof is like a trip where what you are seeking suddenly stands there. It is like going in a bus to see the Leaning Tower of Pisa; suddenly it comes in to view. Surprise in mathematics proof is the appearance of a result in an unexpected way from the addition of that last statement in the proof. It evokes a feeling of magic. But the greatest surprise is when a proof shows the relevance of one branch of mathematics to another. Examples are the uses of complex analysis for proofs in number theory or combinatorics.
Some times even physics gets in! An example [1] is the use of Kirchoff's Laws from electricity and 3-connected planar graphs with n+1 edges to determine the perfect rectangles containing n squares. Of'course mathematics goes in surprising ways into physics. An example is the use of polynomial invariants of knots in quantum field theory.
We shall define economy in proof not only by the number of statements in the proof but also by how primitive the statements used are. Thus a proof using only beginning principles and definitions will be considered to possess economy as compared with a proof of the same result but achieved through using a result whose proof itself was longer.
Thus the following will not be accorded the status of a "short" proof:
The n-th root of 2 is irrational for every integer n >1.
Proof: The square root of 2 is irrational by a proof of Euclid. Now, let n > 2.
If 21/n is rational, say p/q, then 2 = pn/qn so that pn = qn + qn, which is impossible as conjectured by Pierre Fermat and proved by Andrew Wiles. Therefore, 21/n is not rational for every integer n >1.
Wiles' proof is not short. So the above proof using his proof does not possess economy.
Mathematicians refer to a beautiful proof possessing surprise and economy, an elegant proof. But beauty is the first test of elegance.
I have heard the great 20th century mathematician, Paul Erdös (pronounced "airdish" in Hungarian), say many a time that the greatest proofs must be contained in a book in the possession of God. After Erdös, mathematicians have come to call such a proof the "Book Proof." There is a book that is devoted to a sampling of such proofs.
(NOTE TO MATHEMATICIANS:
This essay being directed mainly to middle school and high school students who love math considers great proofs of a few significant statements that are easily grasped by this audience.)
By general consent the oldest Book Proof is attributed to Euclid; it appears as Proposition 20 in Book IX of the Elements. It is also referred to as Euclid's Second Theorem [2], the First Theorem being this: If a prime divides ab, then it divides either a or b.
A number p is said to be prime if (i) p >1 and (ii) p has no positive integer divisors except 1 and p.
Primes are important mainly because of the Fundamental Theorem of Arithmetic which states that every number can be UNIQUELY expressed as a product of primes in the sense that 24 = 2.2.2.3 and in any other expression of 24 as a product of primes there will be three 2's, one 3, and no other primes. (The Fundamental Theorem of Arithmetic is a corollary of Euclid's First Theorem.)
1. The number of primes is not finite
(English translation of Euclid's statement: Prime numbers are more than any assigned multitude of prime numbers.)
EUCLID'S PROOF.
For any finite set {p1,p2,...,pn} of primes, consider m = p1p2...pn+1. If m is prime it is not in the set since m > pi for all i. If m is not prime it has a prime divisor p. If p is one of the pi then p is a divisor of p1p2...pn and hence is a divisor of (m - p1p2...pn ) = 1, which is impossible; so p is not in the set. Hence a finite set {p1,p2,...,pn} cannot be the collection of all primes.
Remarks on the proof:
a) Euclid's proof contains this statement: If m is not prime it has a prime divisor p. The proof is as follows - see Theorem 1 in [2]. Either m is prime, in which case there is nothing to prove, or it has divisors between 1 and m. If q is the smallest of these divisors, q is prime; for if q is not prime, there exists r, 1<r<q and r divides q so that r then divides m, which contradicts the definition of q.
b) Euclid's proof contains this statement: If m is not prime it has a prime divisor p. If p is one of the pi then p is a divisor of p1p2...pn and hence is a divisor of (m - p1p2...pn ).
To justify this, we need the distributive law:
a(b+c) = ab+ac.
With -c in place of c, a(b+(-c))=ab+a(-c) = ab-ac.
But b+(-c) = b-c. So a(b-c) = ab-ac.
Now, since p is a divisor of m and of p1p2...pn, m= pb for some b, and p1p2...pn = pc for some c. IS THIS CLEAR ABOUT THE b AND THE c?
Then m - p1p2...pn = pb-pc = p(b-c), by the distributive law.
But m - p1p2...pn = 1 (see proof). So 1 = p(b-c), where p is an integer bigger than 1 and b-c is a non-zero integer (why?).
So 1 is a product of non-zero integers of which at least one integer is bigger than 1, which is impossible, as we said in the proof.
c) Proof by contradiction
Euclid's proof is given assuming that the
collection of all primes is finite and then deducing the absurd result that
there is a prime not in the finite collection.
The Latin phrase "reductio ad absurdum" means "reduction to the absurd."
It is one of the methods of proof. In English, it is called Proof by Contradiction," which is one type of "indirect
proof." The principle used is that Truth does not imply Falsity and
therefore that if an assumption leads to falsity it is not Truth. So, even the tool most often used in proof is based on a principle. Discussion
of this principle would take us into the philosophy of Logic of which
Aristotle is considered to have given the first interpretations.
G. H. Hardy [3] commented thus:
"The proof is by reductio ad absurdum, and reductio ad
absurdum, which Euclid loved so much, is one of a mathematician's finest
weapons. It is a far finer gambit than any chess gambit: a chess player may
offer the sacrifice of a pawn or even a piece, but a mathematician offers the
game"
d) An "existence" proof
Euclid's proof is perhaps the earliest example of an existence proof, which in this case is a non-existence proof. That is, the proof only establishes that there cannot be finitely many primes. The proof does not exhibit the infinite set of the primes.
e) The occurrence of primes
Although Euclid's proof does not exhibit the infinite set of primes, it can be modified to present an infinite sequence of primes:
One argument:
Let x1 = 2, x2 = 3, and xk+1 = x1x2...xk +1, for each k>1. Then if qk is a prime dividing xk then qk divides xr-1 for r>k (why?) and hence qk cannot divide xr (why?). So no prime dividing xk divides xk+1. But since xk+1 >1, there is a prime dividing it, which is a prime not among the divisors of x1,x2,...,xk.
Another argument ( See Section 2.2 in [2]):
Let 2,3,5,...,p be the set of primes up to p and let m = (2.3.5...p)+1. Then m is either prime, or divisible by a prime between p and m. This means if p is the nth prime pn then pn+1 does not exceed m. That is, pn+1 ≤ p1p2...pn+1, where p1 = 2, p2 = 3, etc. Then pn+1 ≤ pnn +1.
We can do better (see [2]): It is easily shown by applying the Principle of Mathematical Induction that
pn < 2a, where a = 2n. This means pn < pn+1 < pn2. (Why?)
Joseph Bertrand postulated that in fact if n > 2, there is at least one prime p such that n < p < 2n-2. A proof that the postulate is true and hence is a theorem was accomplished by others. An easier to remember version of Bertrand's postulate is that there is always a prime strictly between n and 2n, for n>2, but the actual postulate is the inequality in the preceeding sentence.
( Euclid's result says that there is an infinite number of primes among the natural numbers. It turns out that certain sequences contained in the natural numbers, while they omit an infinite number of natural numbers, still contain an infinite number of primes.
The most celebrated result on this matter was first conjectured by Euler and proved in 1837 A.D. by Dirichlet, a student of Gauss - yes! Carl Friedrich Gauss, referred to also as the prince among mathematicians.
Dirichlet's Theorem
If a is positive and a and b have no common divisor except 1, then there are infinitely many primes of the form an+b.
Thus, there are infinitely many primes of the form 4n+1, and similarly for
4n+3, 6n+1, and so on.
Clearly, not every integer of the form an+b, with a and b as above, is a prime (can you see it?). If they were, the proof of Dirichlet's Theorem would be immediate. Dirichlet is also famous for a method of proof called the Dirichlet Principle or, more popularly, the Pigeon Hole Principle.
While the proof of Dirichlet's Theorem is too difficult for inclusion here, there are simple proofs of its special cases.
We will present the case a = 4, b = 3.
Divided by 4, an integer can have only one of four remainders:0, 1, 2, 3. So an integer will have
one of the following forms: 4m, 4m+1, 4m+2, 4m+3. Numbers of the form 4m and 4m+2 are divisible by 2, and hence can not be prime (except for 2).
Now, numbers 4m+1 have the property that the product of any two of them is again
a number of the same form:
(4m+1)(4k+1) = 4(k+m+4km)+1.
Also,numbers of the form 4m+3 may be written as 4m+3 = 4(m+1)-1 = 4k-1.
Theorem
There are infinitely many primes of the form 4m+3.
PROOF.
As in Euclid's proof, assume there
is only a finite number p1,p2,...,pn of primes of the form 4m-1.
Consider N = 4p1p2...pn - 1. Since N itself
is of the form 4m-1, all of its prime factors can't be in the form 4m+1 (Why? Because if all prime factors are of the from 4m+1
then their product is of the form 4m+1, but N is of the form 4m-1 which is of the form 4k+3.) Therefore, there
must be at least one prime factor p of the form 4m-1. p must be different (Why? Because each of the pi's on dividing N gives a remainder of -1, whereas, p being a factor of N, leaves zero remainder on dividing N) from any of p1,p2,...,pn.
Contradiction.)
f) A quality of a great proof
Unlike proofs introduced in courts of justice, the function of a mathematical proof is not to convince you that the statement is true, rather it is to show you why it is true. But a great proof also points to other directions - as a great theorem has many corollaries. Illustrative of this aspect is a famous proof by Leonard Euler of Euclid's result. Euler's proof remains one of the most influential proofs ever and reminds this writer of this quote of Christopher Marlowe: Was this the face that launched a thousand ships, and burnt the topless towers of Ileum?
REFERENCES
[1] The dissection of rectangles into squares , Brooks, R.L., Smith, C.A.B., Stone, A.H. and Tutte, W.T. (1940)
[2] An Introduction to the Theory of Numbers, G.H. Hardy and E.M. Wright, Oxford University Press, 1979
[3] A Mathematician's Apology, G. H. Hardy, Cambridge University Press, 1993
(G.R.T)
Ü BACK
