Love and Math
Page 10
I wrote in the Preface that one of the principal functions of mathematics is the ordering of information, or, as Langlands himself put it, “creating order from seeming chaos.”1 Langlands’ idea is so powerful precisely because it helps organize seemingly chaotic data from number theory into regular patterns full of symmetry and harmony.
If we think of different fields of mathematics as continents, then number theory would be like North America and harmonic analysis like Europe. Over the years, it’s been taking us less and less time to travel from one continent to the other. It used to take days by boat, and now only hours by plane. But imagine that a new technology was invented that would allow you to be instantly transported from anywhere in North America to someplace in Europe. That would be an equivalent of the connections discovered by Langlands.
I will now describe one of these breathtaking connections, which is closely related to Fermat’s Last Theorem that we talked about in Chapter 6.
Fermat’s Last Theorem is deceptively simple to state. It says that there are no natural numbers x, y, and z solving the equation
if n is greater than 3.
As I wrote, this result was guessed by the French mathematician Pierre Fermat more than 350 years ago, in 1637. He wrote about it on the margin of an old book he was reading, saying that he had found a “truly marvelous” proof of this statement, but “the margin is too small to contain it.” Call it a seventeenth-century Twitter-style proof: “I have found a marvelous proof of this theorem, but unfortunately I can’t write it here because it’s longer than one hundred and forty chara” – sorry, ran out of space.
There is little doubt that Fermat was mistaken. It took more than 350 years to find the real proof, and it is incredibly complicated. There are two main steps: first, in 1986, Ken Ribet showed that Fermat’s Last Theorem follows from the so-called Shimura–Taniyama–Weil conjecture.
(Perhaps, I should note that a mathematical conjecture is a statement that one expects to be true, but for which one does not yet know a proof. Once the proof is found, the conjecture becomes a theorem.2)
What Ken Ribet showed was that if there exist natural numbers x, y, z solving Fermat’s equation, then, using these numbers, one can construct a certain cubic equation, which has a property precluded by the Shimura–Taniyama–Weil conjecture (I will explain below what this equation and this property are). If we know that the Shimura–Taniyama–Weil conjecture is true, then this equation cannot exist. But then the numbers x, y, z solving Fermat’s equation cannot exist either.3
Let’s pause for a minute and go over the logic of this argument one more time. In order to prove Fermat’s Last Theorem, we assume that it is false; that is, we suppose that there exist natural numbers x, y, z such that Fermat’s equation is satisfied. Then we associate to these numbers a cubic equation, which turns out to have a certain undesirable property. The Shimura–Taniyama–Weil conjecture tells us that such an equation cannot exist. But then these numbers x, y, z cannot exist either. Hence there can be no solutions to Fermat’s equation. Therefore Fermat’s Last Theorem is true! Schematically, the flow chart of this argument looks as follows (we abbreviate “Fermat’s Last Theorem” as FLT and “Shimura–Taniyama–Weil conjecture” as STWC):
This kind of argument is called proof by contradiction. We start with the statement that is opposite to what we are trying to prove (in our case, it is the statement that there exist natural numbers x, y, z solving Fermat’s equation, which is opposite to what we want to prove). If, through a chain of implications, we then arrive at a statement that is demonstrably false (in our case, the existence of a cubic equation that is prohibited by the Shimura–Taniyama–Weil conjecture), then we conclude that the statement we started with is false. Hence the statement we wanted to prove (Fermat’s Last Theorem) is true.
What remains then to establish Fermat’s Last Theorem is to prove that the Shimura–Taniyama–Weil conjecture is true. Once this was understood (in 1986, after Ribet’s work), the search was on for a proof of the Shimura–Taniyama–Weil conjecture.
Several proofs had been announced over the years, but subsequent analysis showed that these proofs contained mistakes or gaps. In 1993, Andrew Wiles claimed that he had proved the conjecture, but a few months later it was found that there was a gap in his proof. For a while, it looked like his proof would be remembered alongside many other famous “non-proofs,” in which gaps were found, but never closed.
Luckily, Wiles was able to close the gap within a year, with the help of another mathematician, Richard Taylor. Together, they completed the proof.4 In a wonderful documentary film about Fermat’s Last Theorem, Wiles gets emotional when he recounts this moment, and one can only imagine what a gut-wrenching experience it must have been for him.
Thus, the Shimura–Taniyama–Weil conjecture is a key result in proving Fermat’s Last Theorem. It may also be viewed as a special case of the Langlands Program, and hence it provides an excellent illustration of the unexpected connections predicted by the Langlands Program.
The Shimura–Taniyama–Weil conjecture is a statement about certain equations. A large part of mathematics is in fact about solving equations. We want to know whether a given equation has a solution in a given domain; if so, can we find one? If there are several solutions, then how many? Why do some equations have solutions and some don’t?
In the previous chapter we talked about polynomial equations on one variable, such as x2 = 2. Fermat’s Last Theorem is about an equation on three variables: xn + yn = zn. And the Shimura–Taniyama–Weil conjecture is about a class of algebraic equations on two variables, such as this one:
A solution of this equation is a pair of numbers x, y such that the left-hand side is equal to the right-hand side.
But what kind of numbers do we want x and y to be? There are several choices: one possibility is to say that x and y are natural numbers or integers. Another possibility is to say rational numbers. We can also look for solutions x, y that are real numbers, or even complex numbers – we will discuss this option in more detail in the next chapter.
It turns out that there is one more choice, which is less obvious but equally important: to consider solutions x, y “modulo N,” for some fixed natural number N. This means that we look for integers x and y such that the left-hand side is equal to the right-hand side up to a number that is divisible by N.
For example, let’s look for solutions modulo N = 5. There is one obvious solution x = 0, y = 0. And there are three other, slightly less obvious, solutions: x = 0, y = 4 is a solution modulo 5 because the left-hand side is then 20 and the right-hand side is 0. The difference between the left- and right-hand sides is 20, which is divisible by 5. So this is indeed a solution of the equation modulo 5. By a similar argument, x = 1, y = 0 and x = 1, y = 4 are also solutions modulo 5.
We have already discussed this kind of arithmetic in Chapter 2 when we talked about the group of rotations of a round table. We saw then that the addition of angles was done “modulo 360.” That is to say, if the result of addition of two angles is greater than 360 degrees, we subtract from it 360 to bring it into the range from 0 to 360. For example, rotation by 450 degrees is the same as rotation by 90 degrees, because 450−360 = 90.
We also encounter this arithmetic when we use the clock. If we start working at 10 o’clock in the morning and work for 8 hours, when do we finish? Well, 10 + 8 = 18, so a natural thing to say would be: “We finish at 18 o’clock.” This would be perfectly fine to say in France where they record hours as numbers from 0 to 24 (actually, not so fine, because a working day in France is usually limited to seven hours). But in the U.S. we say: “We finish at 6 pm.” How do we get 6 out of 18? We subtract 12 from it: 18−12 = 6.
So we use the same idea with hours as we do with angles. In the first case, we do addition “modulo 360.” In the second case, we do addition “modulo 12.”
Likewise, we can do addition modulo any natural number N. Consider the set of all consecutive whole numbers bet
ween 0 and N − 1,
If N = 12, this is the set of possible hours. In general, the role of 12 is played by number N, so that it’s not 12 that takes us back to 0, but N.
We define addition on the set of these numbers in the same way as for the hours. Given any two numbers from this set, we add them up, and if the result is greater than N, we subtract N from it to get a number from the same set. This operation makes this set into a group. The identity element is the number 0: adding it to any other number does not change it. Indeed, we have n + 0 = n. And for any number n from our set, its “additive inverse” is N − n, because n + (N − n) = N, which is the same as 0 according to our rules.
For example, let’s take N = 3. Then we have the set {0, 1, 2} and addition modulo 3. For example, we have
in this system, because 2 + 2 = 4, but since 4 = 3 + 1, the number 4 is equal to 1 modulo 3.
So if someone says to you: “2 plus 2 equals 4” to indicate a well-established fact, you can now say (with a condescending smile if you like): “Well, actually, that’s not always true.” And if they ask you to explain what you mean, you can tell them, “If you do addition modulo 3, then 2 plus 2 is equal to 1.”
Given any two numbers from the above set, we can also multiply them. The result may not be between 0 and N − 1, but there will be a unique number in this range that will differ from the result of multiplication by something divisible by N. However, in general, the set {1, 2,..., N − 1} is not a group with respect to multiplication. We do have the identity element: number 1. But not every element has the multiplicative inverse modulo N. This happens if and only if N is a prime number, that is, a number that is not divisible by any other natural number other than 1 and itself.5
The first few primes are 2, 3, 5, 7, 11, 13,... (It is customary to exclude 1 from this list.) Even natural numbers, except for 2, are not prime, because they are visible by 2, and 9 isn’t prime, because it is divisible by 3. There are in fact infinitely many primes – no matter how large a prime number is, there is another prime number that is even larger.6 Primes, because they are indivisible, are the elementary particles of the world of natural numbers; every other natural number, in fact, can be written, in a unique way, as the product of prime numbers. For example, 60 = 2 · 2 · 3 · 5.
Let us fix a prime number. As is customary, we will denote it by p. Then we consider the set of all consecutive whole numbers between 0 to p − 1; that is,
And we consider two operations on them: addition and multiplication modulo p.
As have seen above, this set is a group with respect to addition modulo p. What is even more remarkable is that if we remove number 0 and consider the set of consecutive whole numbers between 1 and p − 1, that is {1,2,...,p−1}, we obtain a group with respect to multiplication modulo p. The element 1 is the multiplicative identity (this is clear), and I claim that any natural number between 1 and p − 1 has a multiplicative inverse.7
For example, if p = 5, we find that
and
so that the multiplicative inverse of 2 modulo 5 is 3, and 4 is its own inverse modulo 5. It turns out that this is true in general.8
In our everyday life, we are used to numbers that are integers or fractions. Sometimes, we use numbers like . But we have now discovered a numerical system of an entirely different nature: the finite set of numbers {0,1,2,..., p−1}, where p is a prime, on which we have the operations of addition and multiplication modulo p. It is called the finite field with p elements. These finite fields form an important archipelago in the world of numbers – one that, unfortunately, most of us are never told exists.
Even though these numerical systems look very different from the numerical systems we are used to, such as rational numbers, they have the same salient properties: they are closed under the operations of addition, subtraction, multiplication, and division.9 Therefore, everything we can do with the rational numbers may also be done with these, more esoteric looking, finite fields.
Actually, they are not so esoteric any more, having found important applications – most notably, in cryptography. When we make a purchase online and enter our credit card number, this number gets encrypted using the arithmetic modulo primes, which is dictated by the equations very much like the ones we have looked at above (see the description of the RSA encryption algorithm in endnote 7 to Chapter 14).
Let’s go back to the cubic equation
that we considered above. Let us look for solutions of this equation modulo p, for various primes p. For example, we have seen above that there are 4 solutions modulo 5. But note that the solutions modulo p = 5 are not necessarily solutions modulo other primes (say, p = 7 or p = 11). So these solutions do depend on the prime p modulo which we do the arithmetic.
The question we are going to ask now is the following: how does the number of solutions of this equation, taken modulo p, depend on p? For small p, we can count them explicitly (perhaps, with the aid of a computer), so we can actually compile a small table.
Mathematicians have known for some time that the number of solutions of an equation of this type modulo p is roughly equal to p. Let’s denote the “deficit,” the number by which the actual number of solutions differs from the expected number of solutions (namely, p), by ap. This means that the number of solutions of the above equation modulo p is equal to p − ap. The numbers ap could be positive or negative for a given p. For example, we found above that for p = 5 there are 4 solutions. Since 4 = 5−1, we obtain that a5 = 1.
We can find the numbers ap for small primes on a computer. They seem to be random. There does not appear to be any natural formula or rule that would enable us to compute them. What’s worse, the computation very quickly becomes immensely complicated.
But what if I told you that there was in fact a simple rule that generated the numbers ap all at once?
In case you are wondering what exactly I mean here by a “rule” generating these numbers, let’s consider a more familiar sequence, the so-called Fibonacci numbers:
Named after an Italian mathematician who introduced them in his book published in 1202 (in the context of a problem of mating rabbits, no less), Fibonacci numbers are ubiquitous in nature: from petal arrangements in flowers to the patterns on the surface of a pineapple. They also have many applications, such as the “Fibonacci retracement” in the technical analysis of stock trading.
The Fibonacci numbers are defined as follows: the first two of them are equal to 1. Each number after that is equal to the sum of the preceding two Fibonacci numbers. For example, 2 = 1 + 1,3 = 2 + 1,5 = 3 + 2, and so on. If we denote the nth Fibonacci number by Fn, then we have F1 = 1, F2 = 1 and
In principle, this rule enables us to find the nth Fibonacci number for any n. But in order to do this, we have to first find all Fibonacci numbers Fi for i between 1 and n − 1.
However, it turns out that these numbers could also be generated in the following way. Consider the series
In words, we multiply an auxiliary variable q by the sum of all powers of the expression (q + q2). If we open the brackets, we obtain an infinite series, whose first terms are
For example, let’s compute the term with q3. It can only occur in q, q(q + q2), and q(q + q2)2. (Indeed, all other expressions that appear in the defining sum, such as q(q + q2)3, will only contain powers of q greater than 3.) The first of these does not contain q3, and each of the other two contains q3 once. Their sum yields 2q3. We obtain in a similar way other terms of the series.
Analyzing the first terms of this series, we find that for n between 1 and 7, the coefficient in front of qn is the nth Fibonacci number Fn. For example, we have the term 13q7 and F7 = 13. It turns out that this is true for all n. For this reason, mathematicians call this infinite series the generating function of the Fibonacci numbers.
This remarkable function can be used to give an effective formula for calculating the nth Fibonacci number without any reference to the preceding Fibonacci numbers.10 But even putting the computational aspects aside, we can appreciate
the value added by this generating function: instead of giving a self-referential recursive procedure, the generating function beholds all Fibonacci numbers at once.
Let’s go back to the numbers ap counting the solutions of the cubic equation modulo primes. Think of these numbers as analogues of the Fibonacci numbers (let’s ignore the fact that the numbers ap are labeled by the prime numbers p, whereas the Fibonacci numbers Fn are labeled by all natural numbers n).
It seems nearly unbelievable that there would be a rule generating these numbers. And yet, German mathematician Martin Eichler discovered one in 1954.11 Namely, consider the following generating function:
In words, this is q times the product of factors of the form (1−qa)2, with a going over the list of numbers of the form n and 11n, where n = 1,2,3,.... Let’s open the brackets, using the standard rules:
and then multiply all the factors. Collecting the terms, we obtain an infinite sum, which begins like this:
and the ellipses stand for the terms with the powers of q greater than 13. Though this series is infinite, each coefficient is well-defined because it is determined by finitely many factors in the above product. Let us denote the coefficient in front of qm by bm. So we have b1 = 1, b2 = −2, b3 = −1, b4 = 2, b5 = 1, etc. It is easy to compute them by hand or on a computer.