Diophantus Of Alexandria, The Proof Of “Undecidability”, Right Triangles And A Million Dollars
“Die Mathematik ist die Königin der Wissenschaften und die Zahlentheorie is die Königin der Mathematik.” ( Mathematics is the queen of the sciences and number theory is the queen of mathematics.) The quote is from German mathematician Carl Friedrich Gauss, considered to be the greatest mathematician since antiquity.
Do you happen to know that a mathematical problem, in fact a problem on right triangles is worth a million dollars? “Wait a minute” you might say, “Don’t we actually know everything about right triangles since the ancient Greeks?” “Did not Euclid, the superstar of high school geometry, manage to answer every single question concerning right triangles?”
Allow me to respond to this and many other questions in the same vein that us, the mathematicians, constantly encounter, with an anecdote from my military service. I did my short-term military service in Burdur, a tiny Anatolian city that gets a rare press mention, if any, only thanks to the garrison it is home to. I was surrounded by a crowd with all sorts of backgrounds, from all over the world… One day at a break I came across a bunch that lived and worked in Paris. At the time I was a member of IHES, a world-famous Mathematics Institute in Paris, in order to learn some mathematics from the Euclids of our time. They asked me what I did for a living and I told them that I was a mathematician; even though I knew full well that this would not put an end to the interrogation. “So, you are a teacher?” probed one. Well, that is correct: “Teaching math” is what we also do on top of our research routine, but it so happened that, I was off the teacher roster that particular year. What’s worse for the occasion, I was in the mood for being extra precise, a malady that often afflicts the mathematicians.
– As a matter of fact, I am not really teaching this year.
– What are you doing then, if not teaching?
– I do research. On right triangles, believe that or not…
After a short silence, turning to the rest of the group “Do you see what our taxes are wasted on?” said the one who seemed to be the chief of that little Parisian gang, thus ending our conversation.
Let’s get back to right triangles: Here lies the answer to the question about what a mathematician does. Being a mathematician is just by looking at a right triangle, posing a question that challenges the intellect of mankind who successfully had reached the Moon and managed to split the atom and untiringly chase the answer for centuries. A mathematician is someone for whom the real joy is not solving millennia-old problems and arriving at knowledge with depths requiring hundreds of years of efforts despite misleadingly trivial appearance (aren’t we just talking about a right triangle here after all!), but discovering totally new worlds in the process.
Fine, we should perhaps let mathematics itself tell us what is it that the mathematicians want to do, and why mathematics – as Gauss has put it – is “the queen of sciences”?
Counting and Measuring: Cheops-Thales-Pythagoras-Plato
Ancient Egyptians realized that they should record the flooding regime of the Nile so that they could deal with the disasters they bring along and use them to their advantage. They calculated that the year is but a cycle made up of a certain number of days and split the cycle into three seasons (“akhet”, the flood season; “peret”, the growth season for the crops; “schemu”, the season of harvest) and adjusted their lives accordingly. To be able to predict the floods of the Nile, they systematically recorded the water-level and to that end, they developed suitable methods of calculation. Believe it or not, it is these mathematical systems (developed initially to protect themselves against the nature) that made the majestic Egypt so superior to other civilizations.
Our relationship with numbers began with a story along these lines: that is, by counting – be it days or other quantities! The set {1, 2, 3, …} is therefore called the set of natural numbers. After its qualified victory in the battle for survival thanks to the agricultural revolution, mankind turned its face to eternity. They set out to build colossal monuments that would last forever to be their traces on the face of Earth. As this required far more intricate calculations, they went a step further than merely counting people and took an interest in geometry. Although initially mathematics was merely a tool to provide answers to basic daily needs, mankind realized that it could put its intellectual world in order and even achieve aesthetic satisfaction with mathematical structures. Would you agree that the ratio of the Cheops’ pyramid’s base to its height strays from 2π, the key mathematical constant of the formula for the circumference of a circle by just two in one thousand (which is a mind-boggling proximity considering that this gigantic structure was built 5000 years ago) could be the result of such aspirations? With his oft-quoted words
“Why are numbers beautiful? It's like asking why Beethoven's Ninth Symphony is beautiful. If you don't see why, no one can tell you. I know numbers are beautiful. If they aren't, then nothing is.”
The late Paul Erdös, a renowned Hungarian mathematician of the last century, had articulated these feelings.
Oh yes, we were talking about right triangles before this chatterbox of a mathematician took over and started drooling on the beauty of mathematics! Yes, geometry, the subject of the engraving on the door to Plato’s Academy: “Let no one ignorant of geometry enter!” In Greece of Antiquity long before days of Plato and under the guidance of Thales and Pythagoras, prominent figures in the hall of fame of the land on which we now live, mathematics had already started its evolution from an area where only trial-and-error methods were available, to an area governed by axiomatic reasoning. As for Plato, I think it would be fair to say that it was him who rescued geometry from the superficiality of engineering and placed it on its abstract foundations. For Plato those who descend to use rulers and protractors were only fit to be porters, whereas a true scholar should never need anything more than a compass and a straightedge (a tool bearing no measurement marks as opposed to a ruler, and used only to draw straight lines) in seeking answers to problems. This line of thought led the mathematicians to the problem of identifying geometric figures which can be drawn solely by using a straightedge and a compass, and from thereon to what came to be known as the three impossibilities of antiquity which could be solved only in the 19th century with subtle methods based on the mankind’s 2200-year-long efforts and experience: namely, to the impossibility of trisecting some angles, or constructing a cube that has twice the volume of a given cube, or drawing a square of equal area with a circle using just a compass and a straightedge. Yes, we can now prove that neither you, nor your grandchildren will be capable of these. Don’t bother trying. Unfortunately it is not possible to explain the reasons in a couple of pages for the laymen, since to be able to comprehend, one has to have a formal university education in maths.
Just because the mathematicians have dug so deep down, we will not give up here, of course. At the very least, getting acquainted with that one-million-dollar problem about right triangles is worth swimming heads that might be caused some rather technical stuff. Hold tight then: We are now starting off the slightly more serious part of this article!
Congruent Number Problem
The problem I am about to present is not two millennia old as the three impossibilities of antiquity, but barely (!) a single millennium old – and has still not accumulated dust. It was the Arabs who first posed this question, at the peak of their civilization in the 1Oth century. In 13rd century Friedrich II, the Emperor of the Holy Roman Empire, summoned Italian mathematician Fibonacci and asked him to solve the following question:
Which positive integers n may be the area of a right triangle with rational sides?
When it is possible to find such a right triangle, we will call the integer n a congruent number. Algebraically, we can express this question as follows:
When it is possible to find rational numbers a, b, c such that
(*) a2+b2=c2 and = n
the integer n is called a congruent number
Pierre de Fermat, who was a lawyer by profession, proved that n=1 is not a congruent number, so that there is no right triangle with rational sides and whose area is 1. Fermat’s proof is quite elegant and comprehensible even to a high school student with a minimal interest in mathematics. The most important step in his proof is the so-called infinite descent method. Fermat shows that if there is a right triangle whose area is 1 where its hypotenuse, let’s denote it by c=m/n, is a rational number (here m and n are two positive integers), then it is possible to find a right triangle with rational sides, whose hypotenuse has a strictly smaller numerator than m. But, this is absurd since it implicitly says that we can find a smaller positive integer than any positive integer! This contradiction shows that our first assumption that there is a right triangle with area 1 must be wrong.
But then, how do we proceed in the general case?
Right Triangles and Diophantine Equations
We begin with a simple observation about congruent numbers. Although at first look, it might look like a step taken in vain , you will soon see how far the mathematicians managed to take this tiny step!
Observation 1: There is a one-to-one correspondence between the following two sets:
In other words, for a positive integer n to be a congruent number, it is necessary and sufficient that the Diophantine equation En: y2=x3-n2x has a solution other than (0,0), (0,n) and (0,-n).
What might be a Diophantine equation now? These are the type of equations that Diophantus of Alexandria worked on ages ago and therefore they were named after him as Diophantine Equations. Roughly speaking, Diophantus wanted to decide whether or not the equation F(x1,…, xn)=0 (where F(x1,…, xn) is a polynomial in n variables) has a solution as x1,…, xn take rational values; and if there is, whether it is possible to describe the solution set. This innocent-looking (or not?) problem hides a monster lying behind it. Well, let’s get to work to reveal him!
Example 1: The equation y2-(x3-n2x)=0 that we have seen just above is an example of a Diophantine equation for each choice of an integer n.
Example 2: It should not be too difficult to discover a solution of the equation x3+y3+z3=29 in the set of integers: (3,1,1). Staring at it long enough, one can see that the triple (4,-3,-2) is a solution as well.
Example 3: Let us now consider the similar-looking equation x3+y3+z3=30. The smallest solution to this equation in the set of integers is given by the triple (2220422932, -2218888517, -283059965). This solution could only be discovered in 1970’s with the aid of first calculators! The monster starts to bare its teeth, wouldn’t you think?
Example 4: So long as we have gone through the last two examples above, let us also consider the equations
x3+y3+z3=31
and
x3+y3+z3=32
These equations have no solution in integers and high school-level knowledge of mathematics is sufficient to prove this fact. Here is the way to go: Cube of an integer gives remainder 0,1 or 8 upon division by 9. This fact and a basic talent in arithmetic is good enough to handle this problem. Wait, what happened to the monster?
Example 5: All right, as one final example, let us now have a look at the equation
x3+y3+z3=33
Hold tight: No one knows whether or not this equation has a solution in the set of integers!
Yes, no one can prove that this equation cannot have a solution, or put forth a single solution (again, in the set of integers). How embarrassing indeed for the mankind who has conquered the Moon! This deadlock drags us to the following question: As we have computers that can compute far better and faster than us the humans, why don’t we simply write and run an algorithm to check whether the equation above could have a solution or not?
This problem is known as Hilbert’s tenth problem. It is one of the 23 problems that were presented by David Hilbert, one of the leading mathematicians of 20th century, during the International Congress of Mathematicians in 1900. He had labeled those 23 problems as those that need to be tackled with high priority in the new century. Hilbert’s 10th Problem: Is there an algorithm that takes a Diophantine Equation with rational coefficient as an input and gives the answer that either
THERE IS a rational solution of this equation
or
THERE IS NO rational solution of this equation
as an output.
Hilbert must have guessed a positive answer to this question, as he had said “In der Mathematik giebt es Ignorabimus” (In Mathematics, there cannot be such thing as we cannot know!).
Yet, Hilbert was proved to be wrong in 1970:
Matiyasevich: “The solvability of Diophantine equations is undecidable. In other words, there CANNOT BE FOUND an algorithm which could decide whether a randomly chosen Diophantine equation has rational solutions or not.”
Yes, Matiyasevich proves that we can never and ever decide! Perhaps you would now accept that we are facing a monster. It is really time to flee and get back to the realm of right triangles!
Right Triangles and Elliptic Curves
Let me recall where we had left the congruent number problem: There is a one-to-one correspondence between
1- right triangles with rational sides and an area a positive integer n and
2- points with rational coordinates that lie on the curve determined by the equation En: y2=x3-n2x, other than the points (0,0), (0,n) and (0,-n).
Let me recall where we had left the congruent number problem:
There is a one-to-one correspondence between
1- right triangles with rational sides and an area a positive integer n and
2- points with rational coordinates that lie on the curve determined by the equation En: y2=x3-n2x, other than the points (0,0), (0,n) and (0,-n).
The curves which are the solution set of an equation of the form En are called elliptic curves. Although it might look like that we are dealing with a very special type of equations, don’t say “who cares” and do not yet underestimate them! The One-Million-Dollar-worth Birch and Swinnerton-Dyer conjecture, one of the millennium problems of Clay Mathematics Institute and one of the most important problems in the world of mathematics, concerns the arithmetic properties of these objects. We will soon get back to this point. Beyond that, I should also indicate here that understanding the intricate structures related to elliptic curves form the heart of the proof of Fermat’s Last Theorem by Sir Andrew Wiles, a problem that remained open for 350 years. For those who are still dubious about their importance: Elliptic curves are used in the design of public-key cryptosystems. Every single digital bank account is essentially guarded by these innocent looking mathematical objects!
Mathematicians will not confine themselves to securing our bank accounts, of course. If we want to solve the congruent number problem, what we need is to describe the solution set En.
Problem: Describe the set
En(Q)={(x,y) ∈QxQ: y2=x3-n2 x}
of rational points on the curve En.
Let us once more remember the subset {(0,0), (0,n), (0,-n)} of En(Q), and call it the set of obvious elements of En(Q).
We have arrived at the point where we shall pass beyond the high school and in fact also the undergraduate level mathematics! Do not be discouraged though, a high school student can easily understand the statement of the theorem I am about to present; yet its proof requires a very serious amount of mathematical tools:
Theorem (Mordell, 1922): If the set En(Q) has a single element other than the obvious elements, then the set En(Q) has in fact infinitely many elements.
The crucial ingredient for the proof is mathematical alchemy. There is no such nonsense of course, but the main idea that goes into the verification of this theorem makes you feel that there is: The basic idea (due to Henri Poincare) is to play around with the set of points of an elliptic curve, and turn it into a mathematical object on which we can perform addition and subtraction. Roughly speaking, a set that comes equipped with an addition (and subtraction) operation is called a group. For example, the set of integers together with the usual addition gives us a group. Or, the set of nonzero rational numbers together with multiplication operation gives another one. In the figures below, we describe explicitly the “addition” operation given on the set of points on an elliptic curve.
Mordell’s main theorem asserts that, under this very special addition operation, the group En(Q) structurally resembles the group of integers. For readers who have attended an undergraduate level algebra class, I restate this assertion in a more mathematical language:
The group En(Q) is a finitely generated abelian group under the operation described in diagram above. The torsion subgroup of En(Q) consists exactly of its obvious elements.
It looks as though we took a giant step thanks to Mordell’s theorem: For an integer n to be a congruent number, it is necessary and sufficient that En(Q) has infinitely many elements. Therefore the congruent number problem takes the following form:
For which positive integers n, the elliptic curve En: y2=x3-n2x carries infinitely many rational points?
At this very point the Birch and Swinnerton-Dyer conjecture comes into the picture, one of the remaining six Clay Millennium problems whose resolution will be awarded by a million dollars! This conjecture leads us to a computable solution of the congruent number problem.
Birch and Swinnerton-Dyer Conjecture (1964)
For each prime number p, let us denote by Np the number of the solutions of the equation y2=x3-n2x mod p. For the set En(Q) to have an infinitely many elements, it is necessary and sufficient that p:prime p/Np converges to 0.
Frankly, the total wages of mathematicians actively working on this problem already far exceeds a million dollars; and this is the case despite the fact that mathematicians are relatively cheap workers. The point I am trying to make is that the award on this problem is far from reflecting its true value: It does not seem possible to obtain a full resolution of this problem for barely a million dollars!
This is the moment where we hit the last strike to the congruent number problem waiting for a proof for a whole millennium.
Theorem (Tunnell, 1982): Let us define
We assume the truth of the Birch and Swinnerton-Dyer conjecture. Then,
(a) If n is an odd integer, then for n to be a congruent number, the necessary and sufficient condition is that 2An=Bn.
(b) If n is an even integer, then for n to be a congruent number, the
necessary and sufficient condition is that 2Cn=Dn.
Does this look complicated? In truth it is not: Let me illustrate the strength of Tunnell’s theorem with an example. We keep assuming the validity of the Birch and Swinnerton-Dyer conjecture.
Example: Let’s verify by hand that if an integer n gives the remainder 7 when divided by 8, then it is a congruent number. For example, this assertion says that there has to be a right triangle with rational sides whose area is 81726749401007; although it doesn’t pin down a single right triangle.
Here is how we check this, relying on Tunnell’s result alluded to above. Any above-average high school student can easily check that if the integer n gives the remainder 7 when divided by 8, then both quantities An and Bn in Tunnell’s theorem are 0. Thus, in this specific case, we really have
0=2An = Bn =0
so by Tunnell’s theorem, n has to be a congruent number.
The rest of this story keeps being told in the PhD programs in the Math Departments of select universities. We, however, have to put an end to our story here. If you have the desire to be informed about the rest, for example, on Kazuyo Kato’s proof that half of the assertion in Birch and Swinnerton-Dyer conjecture holds unconditionally true (without the aid of a million dollars or anything) – a fact that I was forced to hide so far: you very well know where to find us, and in fact the story I so much love to relate starts at this point!
The following quote attributed to Bertrand Russell, the famed 20th century English philosopher and a mathematician, seems like a perfect way of to end this article, rather than appealing to the author’s poor understanding of the world of Mathematics.
“Mathematics, rightly viewed, possesses not only truth, but supreme beauty – a beauty cold and austere, like that of sculpture, without appeal to any part of our weaker nature, without the gorgeous trappings of painting or music, yet sublimely pure, and capable of a stern perfection such as only the greatest art can show. The true spirit of delight, the exaltation, the sense of being more than Man, which is the touchstone of highest excellence, is to be found in mathematics as surely as in poetry.”