The decryption is given by the formula
Applied to ae, it gives us back the original number a. But only those who know d can do this.
The reason why this is a good encryption scheme is that in order to find d, which enables one to reconstruct the numbers being encoded, we must know the value of (p −1)(q − 1). But for this we need to know what p and q are, which are the two prime divisors of n. Those are kept secret. For n sufficiently large, using known methods of prime factorization, it may take many months, even on a network of powerful computers, to find p and q. For example, in 2009 a group of researchers using hundreds of parallel computers were able to factor into primes a 232-digit number; it took two years (see http://eprint.iacr.org/2010/006.pdf). But if one could come up with a more efficient way to “factor” natural numbers into primes (for example, by using a quantum computer), then one would have a tool for breaking this encryption scheme. That’s why a lot of research is directed toward factoring numbers into primes.
8. In the case of the rational numbers, we saw that the equations of the form x2 = 2 may not have solutions among rational numbers, and in that case we could create a new numerical system by adding these solutions, such as and . Then we saw that flipping and was a symmetry of this new numerical system.
Likewise, we can consider polynomial equations in the variable x, such as x2 = 2 or x3− x = 1, as equations in the finite field {0,1,2,..., p−1}. We may then ask whether this equation can be solved for x inside this finite field. If it does not have a solution, then we can adjoin the solutions to the finite field, in the same way in which we adjoined and to the rational numbers. This way we create new finite fields.
For instance, if p = 7, the equation x2 = 2 has two solutions, 3 and 4, because
Note that 4 is −3 with respect to the arithmetic modulo 7 because 3 + 4 = 0 modulo 7. So these two solutions of the equation x2 = 2 are the negatives of each other, just like and are the negatives of each other. This is not surprising: the two solutions of the equation x2 = 2 will always be the negatives of each other because if a2 = 2, then (−a)2 = (−1)2a2 = 2 as well. This means that if p ≠ 2, there will always be two elements of the finite field that square to the same number, and they will be the negatives of each other (if p ≠ 2, then p is necessarily odd, and then −a cannot be equal to a, for otherwise p would be equal to 2a). Therefore, only half of the non-zero elements of the finite field {1,2,..., p − 1} are squares.
(The celebrated Gauss reciprocity law describes which numbers n are squares in the arithmetic modulo p and which are not. This is beyond the scope of this book, but let’s just say that the answer only depends on the value of p modulo 4n. So, for example, we already know that n = 2 is a square modulo p = 7. In this case 4n = 8. Hence, it will also be a square modulo any prime p which is equal to 7 modulo 8, no matter how large. This is a stunning result!)
If p = 5, then 12 = 1, 22 = 4, 32 = 4, and 42 = 1 modulo 5. So 1 and 5 are squares modulo 5, but 2 and 4 are not. In particular, we see that there are no solutions to the equation x2 = 2 in the finite field {0,1,2,3,4}, just as it was in the case of rational numbers. Hence, we can create a new numerical system extending the finite field {0,1,2,3,4} by adjoining the solutions of x2 = 2. Let us denote them again by and (but we have to remember that these are not the same numbers that we adjoined to the rational numbers before).
We obtain a new finite field which consists of numbers of the form
where a and b are in {0,1,2,3,4}. Because we have two parameters a and b taking values 0, 1, 2, 3, or 4, we find that this new numerical system has 5 · 5 = 25 elements. More generally, any finite extension of the field {0,1,..., p−1} has pm elements for some natural number m.
Now suppose that we adjoin all solutions of all polynomial equations in one variable to the finite field {0, 1, 2,..., p−1}. Then we obtain a new numerical system called the algebraic closure of the finite field. The original finite field has p elements. It turns out that its algebraic closure has infinitely many elements. Our next question is what is the Galois group of this algebraic closure. These are the symmetries of this algebraic closure, which preserve the operations of addition and multiplication and send the elements of the original field of p elements to themselves.
If we start with the field of rational numbers and take its algebraic closure, then the corresponding Galois group is very complicated. In fact, the Langlands Program was created in part to describe this Galois group and its representations in terms of harmonic analysis.
In contrast, the Galois group of the algebraic closure of the finite field {0, 1, 2,..., p −1} turns out to be quite simple. Namely, we already know one of these symmetries: the Frobenius, which is the operation of raising to the pth power: a → ap. According to Fermat’s little theorem, the Frobenius preserves all elements of the original finite field of p elements. It also preserves addition and multiplication in the algebraic closure:
Hence, the Frobenius belongs to the Galois group of the algebraic closure of the finite field.
Let us denote the Frobenius by F. Clearly, any integer power Fn of the Frobenius is also an element of the Galois group. For example, F2 is the operation of raising to the p2th power, a → ap2 = (ap)p. The symmetries Fn, where n runs over all integers, form a subgroup of the Galois group which is called the Weil group, in honor of André Weil. The Galois group itself is what’s called a completion of the Weil group; in addition to the integer powers of F, it also has as elements certain limits of Fn as n goes to ∞. But in the appropriate sense, the Frobenius generates the Galois group.
Here is an example of how the Frobenius acts on elements of the algebraic closure of a finite field. Consider the case p = 5 and the elements of the algebraic closure of the above form
where a and b are 0,1,2,3, or 4. This numerical system has a symmetry exchanging and :
in parallel with what happens when we adjoin to the rational numbers. What is surprising (and what has no analogue in the case of rational numbers) is that this flip symmetry is in fact equal to the Frobenius. Indeed, applying the Frobenius to means raising it to the 5th power, and we find that
because 4 = −1 modulo 5. It follows that for p = 5 the Frobenius sends . The same is true for any prime p such that the equation x2 = 2 has no solutions in the finite field {0,1,2,..., p−1}.
9. A symmetry of an n-dimensional vector space, more properly called linear transformation (see endnote 2), may be represented by a matrix, that is a square array of numbers aij, where i and j run from 1 to n, where n is the dimension of the vector space. Then the trace is the sum of the diagonal elements of this matrix, that is, of all aii with i running from 1 to n.
10. In the present context, going back would mean finding, for a given function f, a sheaf such that for each point s in our manifold, the trace of the Frobenius on the fiber at s is equal to value of f at s. Any given number can be realized as the trace of a symmetry of a vector space. What is difficult is to combine these vector spaces into a coherent collection satisfying the properties of a sheaf.
Chapter 15. A Delicate Dance
1. A representation of the Galois group in a group H is a rule that assigns to each element of the Galois group an element of H. It should satisfy the condition that if a, b are two elements of the Galois group and f (a), f (b) are the elements of H assigned to them, then to the product ab in the Galois group should be assigned the product f(a)f(b) in H. A more proper name for this is a homomorphism from the Galois group to H.
2. To make this more precise, recall the notion of an n-dimensional vector space from endnote 17 to Chapter 10. As we discussed in Chapter 2, an n-dimensional representation of a given group is a rule that assigns a symmetry Sg of an n-dimensional vector space to each element g of this group. This rule must satisfy the following property: for any two elements of the group, g and h, and their product gh in the group, the symmetry Sgh is equal to the composition of Sg and Sh. It is also required that for each element g, we have and for any vectors , and a number k. (Such
symmetries are called linear transformations; see endnote 2 to Chapter 14.)
The group of all invertible linear transformations of an n-dimensional vector space is called the general linear group. It is denoted by GL(n). Thus, according to the definition in the previous paragraph, an n-dimensional representation of a given group Г is the same as a representation of Г in GL(n) (or, a homomorphism from Г to GL(n), see endnote 1).
For example, in Chapter 10 we talked about a three-dimensional representation of the group SO(3). Each element of the group SO(3) is a rotation of a sphere, to which we assign the corresponding rotation of the three-dimensional vector space containing the sphere (it turns out to be a linear transformation). This gives us a representation of SO(3) in GL(3) (or equivalently, a homomorphism from SO(3) to GL(3)). Intuitively, we can think about a rotation as “acting” on the three-dimensional vector space, rotating each vector in this space to another vector.
On one side of the Langlands relation (also known as the Langlands correspondence), we consider n-dimensional representations of the Galois group. On the other side, we have automorphic functions that can be used to build the so-called automorphic representations of another group GL(n) of symmetries of the n-dimensional vector space, though not over the real numbers but over the so-called adèles. I will not attempt to explain what these are, but the following diagram shows schematically what the Langlands relation should look like:
For example, two-dimensional representations of the Galois group are related to the automorphic representations of the group GL(2), which can be constructed from the modular forms discussed in Chapter 9.
A generalization of this relation is obtained by replacing the group GL(n) by a more general Lie group. Then, on the right-hand side of the relation we have automorphic representations of G, rather than GL(n). On the left-hand side, we have representations of the Galois group in the Langlands dual group LG, instead of GL(n) (or equivalently, homomorphisms from the Galois group to LG). For more details, see, for example, my survey article: Edward Frenkel, Lectures on the Langlands Program and conformal field theory, in Frontiers in Number Theory, Physics and Geometry II, eds. P. Cartier, e.a., pp. 387–536, Springer-Verlag, 2007, available online at http://arxiv.org/pdf/hep-th/0512172.pdf
3. See the video at http://www.youtube.com/watch?v=CYBqIRM8GiY
4. This dance is called Binasuan. See, for example, this video: http://www.youtube.com/watch?v=N2TOOz_eaTY
5. For the construction of this path and the explanation why if we traverse this path twice, we obtain a trivial path, see, for example, Louis H. Kaufmann, Knots and Physics, Third Edition, pp. 419–420, World Scientific, 2001.
6. In other words, the fundamental group of SO(3) consists of two elements: one is the identity and the other is this path, whose square is the identity.
7. The mathematical name for this group is SU(2). It consists of the “special unitary” transformations of the two-dimensional complex vector space. This group is a cousin of the group SU(3), discussed in Chapter 2 in connection with quarks, which consists of special unitary transformations of the three-dimensional complex vector space.
8. More precisely, the lifting of the closed path we have constructed (corresponding to the first full turn of the cup) from the group SO(3) to its double cover, the group SU(2), will be a path that starts and ends at different points of SU(2) (both of which project onto the same point in SO(3)), so it’s not a closed path in SU(2).
9. In general, this relationship is more subtle, but to simplify matters, in this book we will assume that the dual of the dual group is the group itself.
10. A principal G-bundle (or, G-bundle) on a Riemann surface is a fibration over the Riemann surface such that all fibers are copies of the “complexification” of the group G (it is defined by replacing, in the definition of the group, real numbers by complex numbers). The points of the moduli space (more properly called stack) of G-bundles on X are equivalence classes of G-bundles on X.
In order to simplify the exposition, in this book we do not make a distinction between a Lie group and its complexification.
11. In the fundamental group, we identify any two closed paths that could be deformed into one another. Since any closed path on the plane that does not go around the removed point can be contracted to a point, the non-trivial elements of the fundamental group are those closed paths that go around this point (those cannot be contracted – the point we have removed from the plane is an obstacle to doing this).
It is easy to see that any two closed paths with the same winding number can be deformed into one another. So the fundamental group of the plane without one point is nothing but the group of integers. Note that this discussion is reminiscent of our discussion in Chapter 5 of the braid group with two threads, which we also found to be the same as the group of integers. This is not a coincidence because the space of pairs of distinct points on the plane is topologically equivalent to the plane with a point removed.
12. The reason that the monodromy takes values in the circle group is due to the famous Euler’s formula
In other words, the complex number is represented by the point on the unit circle corresponding to the angle θ, as measured in radians. Recall that 2π radians is the same as 360 degrees (this corresponds to the full rotation of the circle). Therefore, the angle θ measured in radians is the angle 360 · θ/2π degrees.
A special case of this formula, for θ = π, is
which Richard Feynman called “one of the most remarkable, almost astounding, formulas in all of mathematics.” It played a prominent role in the Yoko Ogawa’s novel The Housekeeper and the Professor, Picador, 2009. Another special case, no less important, is .
This means that the unit circle in the complex plane with the coordinate t, on which the solution of our differential equation is defined, consists of all points of the form , where θ is between 0 and 2π. As we move along the unit circle counterclockwise, we are evaluating our solution x(t) = tn at these points , letting the angle θ increase from 0 to 2π (in radians). Making full circle means setting θ equal 2π. Therefore, to obtain the corresponding value of our solution, we need to substitute into tn. The result is . But the original value of the solution is obtained by substituting t = 1 into tn, which is 1. Thus, we find that when we traverse the closed path going counterclockwise along the unit circle, our solution gets multiplied by . And that’s the monodromy along this path.
This monodromy is a complex number that can be represented by a point on the unit circle on another complex plane. That point corresponds to the angle 2πn radians, or 360n degrees, which is what we wanted to show. In fact, multiplying any complex number z by amounts, geometrically, to rotating the point on the plane corresponding to z by 360n degrees. If n is an integer, then , so no monodromy occurs, but if n is not an integer, we get a non-trivial monodromy.
To avoid confusion, I want to stress that we have two different complex planes here: one is the complex plane on which our solution is defined – the “t-plane.” The other is the plane on which we represent the monodromy. It has nothing to do with the t-plane.
To recap, we have interpreted the monodromy of the solution along a closed path with the winding number +1 on the t-plane as a point of another unit circle. Similarly, if the winding number of the path is w, then the monodromy along this path is , which amounts to the rotation by 2πnw radians, or 360wn degrees. Thus, the monodromy gives rise to a representation of the fundamental group in the circle group. Under this representation, the path on the t-plane without a point, whose winding number is w, goes to the rotation by 360wn degrees.
13. Note that it is important that we have removed one point, the origin, from the plane. Otherwise, any path on the plane could be collapsed, and the fundamental group would be trivial. Hence no monodromy would be possible. We are forced to remove this point because our solution, tn, is not defined at the origin if n is not a natural number or 0 (in that case there is no monodromy).
14. More precisely, no
t all representations of the fundamental group in LG can be obtained from opers, and in this diagram we restrict ourselves to those that can. For other representations, the question is still open.
15. Edward Frenkel, Langlands Correspondence for Loop Groups, Cambridge University Press, 2007. Online version is available at http://math.berkeley.edu/~frenkel
Chapter 16. Quantum Duality
1. You may be wondering what happened between 1991 and 2003. Well, in this book my main goal is to tell you about the aspects of the Langlands Program that I find most interesting and how the discoveries in this area were made, in which I was fortunate to participate. I am not trying to recount the complete story of my life to date. But, if you are curious, during those years I brought my family from Russia to the U.S., moved out West to Berkeley, California, fell in and out of love, got married and divorced, brought up several Ph.D. students, traveled and lectured around the world, published a book and dozens of research papers. I kept trying to uncover the mysteries of the Langlands Program in different domains: from geometry to integrable systems, from quantum groups to physics. I’ll save the details of this part of my journey for another book.
2. See http://www.darpa.mil/Our_Work
3. G.H. Hardy, A Mathematician’s Apology, Cambridge University Press, 2009, p. 135.
4. R.R. Wilson’s Congressional Testimony, April 17, 1969, quoted from http://history.fnal.gov/testimony.html
5. Maxwell’s equations in vacuum have the form
where denotes the electric field and denotes the magnetic field (to simplify the formulas, we are choosing a system of units in which the speed of light is equal to 1). It is clear that if we send
the equations of the left-hand side will become the equations on the right-hand side, and vice versa. Thus, each individual equation changes, but the system of equations does not.
Love and Math Page 32
