Also available at http://math.ucr.edu/home/baez/week188.html October 11, 2002 This Week's Finds in Mathematical Physics (Week 188) John Baez I've been talking about q-mathematics, and last week the story reached a kind of climax when I combined the themes of q-deformation, categorification, and Dynkin diagrams. These are three of my favorite things, but I can't expect everyone to enjoy them as much as I do, so now I'll back down and talk about something simpler - but related. Let's see what happens when you put Pascal's triangle in a magnetic field! You've probably seen Pascal's triangle. It has a 1 on top, and each other number in the triangle is gotten by adding the number or numbers above it: 1 / \ 1 1 / \ / \ 1 2 1 / \ / \ / \ 1 3 3 1 / \ / \ / \ / \ 1 4 6 4 1 and so on. The number at each place tells you how many paths there are zig-zagging down from the top of the triangle to that place - since each number is the sum of the numbers above it. Let's think about one of these paths. To get to the kth place in the nth row of the triangle, the path must go to the right a total of k times and to the left a total of (n-k) times. Here I'm counting the rows starting from zero. For example, the "6" in Pascal's triangle is at the 2nd place in the 4th row, so any path down to the "6" must go left twice and right twice: 1 / 1 1 \ 1 2 1 / 1 3 3 1 \ 1 4 6 4 1 Now, the number of ways to choose k things out of n is the binomial coefficient (n choose k) = n! / k! (n-k)! so this is the number at the kth place of the nth row. And since each number in the triangle is the sum of those above it, we get (n choose k) = (n-1 choose k) + (n-1 choose k-1) To illustrate how these things work, you can actually build a machine where you drop a little ball into the top of a triangle, designed so that the ball has a 50% chance of zigging to the left or zagging to the right at each step of its fall. By the time it gets to the nth row, the chance of its being in the kth place will be proportional to (n choose k). If you drop a bunch of balls in the top and catch them as they fall out the bottom, you'll get an approximately Gaussian distribution of balls, like this: 1 / \ 1 1 / \ / \ 1 2 1 / \ / \ / \ 1 3 3 1 / \ / \ / \ / \ 1 4 6 4 1 o o o o o o o o o o o o o o o o This illustrates how the famous "bell curve" shows up whenever you add a big bunch of independent random numbers - as made precise by the "central limit theorem". This stuff is old - very old. In fact, Pascal's triangle had already been around for centuries before he wrote his book about it in 1654. I think we need a more up-to-date version of Pascal's triangle for the 21st century. So: let's suppose the little ball we drop into the machine is an ELECTRON, and let's turn on a MAGNETIC FIELD! In quantum mechanics, if you have a charged particle in a static magnetic field, its wavefunction gets multiplied by a phase when you move it around a loop. This phase is just q = exp(iF) where F is the flux of the magnetic field though any surface bounded by the loop. Here I'm working in units where Planck's constant and the particle's charge both equal 1. Suppose our particle is confined to a plane, and there's a constant magnetic field perpendicular to this plane. If we tile this plane with squares, moving the particle counterclockwise around any one of these squares multiplies its wavefunction by the same phase q: ---<--- | | v ^ | | --->--- Here's another way to think about it. Let U be the operation of moving our particle one unit across to the right, and let V be the operation of moving it one unit upwards. Then the operation of moving it around the above square is U V U^{-1} V^{-1} and we've just seen this equals q - that is, it acts to multiply the particle's wavefunction by q. So: U V U^{-1} V^{-1} = q This means that the operations U and V don't commute: instead, they "q-mute": UV = qVU Now suppose we have a grid of squares and our particle takes any path from the lower left corner to the upper right corner: --------------- | | | | | ^ | | | |----------->---| | | | | ^ | | | | --->----------- The phase it acquires by the end of its journey depends on the path it takes. Since UV = qVU, its phase gets an extra factor of q each time it goes first right and then up, as compared to going up and then right. So compared to the path that goes all the way up and then across, the *relative* phase of the particle at the end of its journey will be q^n, where n is the number of squares above and to the left of its path: --------------- | | | | 2 | 3 ^ | | | |----------->---| | | | | 1 ^ | | | | --->----------- In this example our particle gets a relative phase of q^3. Now let's rotate our grid of squares so it look like diamonds arranged in Pascal's triangle, with the lower right corner of our grid becoming the top of the triangle. And suppose we drop in a charged particle at the top! Then the particle can take lots of paths from the top to any given spot, but it will get a different phase depending on which path it takes. The rules of quantum mechanics say we have to add up these phases to get the amplitude for the particle to wind up at that spot. This sum over paths is a simple version of what physicists call a "path integral". For example, in this new picture the above path looks like: o / o x \ x o x / x o x x \ x x o x x and we can tell it gets a phase of q^3, because this shape is made of 3 diamonds: o / \ o 1 x \ / \ x o 2 x / \ / x o 3 x x \ / x x o x x If for each spot we sum these phases over all paths that reach that spot, we get the "q-deformed Pascal's triangle": 1 / \ / \ / \ / \ / \ 1 1 / \ / \ / \ / \ / \ / \ / \ / \ 1 1+q 1 / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \/ \/ \ 1 1+q+q^2 1+q+q^2 1 / \ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ 1 1+q+q^2+q^3 1+q+2q^2+q^3+q^4 1+q+q^2+q^3 1 Let's call the entry in the kth place of the nth row [n choose k] The square brackets tell us that these are "q-binomial coefficients" instead of the ordinary ones. Using the fact that every path to reach a spot must have come from the left or the right, you can show that [n choose k] = [n-1 choose k] + q^{n-k} [n-1 choose k-1] It helps to draw some pictures to see where that factor of q^{n-k} is coming from... but I'll leave that as a fun little exercise for you! And starting with this recursion relation, it's easy to check inductively that: [n]! [n choose k] = ----------- [k]! [n-k]! where [n]! is the q-factorial [n]! = [1] [2] ... [n] and [n] is the q-integer [n] = 1 + q + ... + q^{n-1} So the quantum Pascal's triangle is a lot like the ordinary one. In particular, the formula [n]! [n choose k] = ----------- [k]! [n-k]! makes it obvious that this triangle is symmetric around its axis, just like the ordinary one, even though I defined it in way that obscured this fact a bit. This symmetry gives us the mirror-image recursion relation: [n choose k] = q^k [n-1 choose k] + [n-1 choose k-1] But now let's see if you've really been paying attention. Do you really understand these q-binomial coefficients? If so, you should instantly know what the coefficient of any power of q in [n choose k] signifies. Say, the coefficient of q^i. Think about it. Right! It's the number of paths to the kth place of the nth row of Pascal's triangle that create a shape like this with i diamonds: o / \ o x \ / \ n = 4 x o x k = 2 / \ / i = 3 x o x x \ / x x o x x But these shapes are famous! They're usually drawn like this: --------------- | | | | | | | | | |--------------- | | | | | | ------- and they're called "Young diagrams" - or, with more historical accuracy, "Ferrers diagrams". So, the coefficient of q^i in [n choose k] is also the number of Young diagrams with i boxes, k columns and n-k rows. Now, Young diagrams show up all over the place in mathematics. I described a few of their most fundamental applications in "week157". One thing I *didn't* go into is their relation to Grassmannians. But we're pretty well-positioned to do that now, so let's give it a shot. The Grassmannian Gr(n,k) is the set of all k-dimensional subspaces of an n-dimensional vector space. This makes sense over any field. However, it's particularly fun to work over the field with q elements, where q is any prime power - because then our Grassmannian has [n choose k] elements! In fact, we already saw this in "week184". But now I want to give a proof that uses Young diagrams. This will forge yet another link between the two flavors of q-mathematics: the sort where q is a unit complex number, and the sort where q is a prime power. So far this week we've been doing quantum mechanics and thinking of q as a unit complex number. Now we'll turn into algebraists, take what've done, and apply it when q is a power of a prime number! In "week184" I showed that we can read off a lot of information about the Grassmannian Gr(n,k) from the q-binomial coefficient [n choose k]. For example, [4 choose 2] = 1 + q + 2q^2 + q^3 + q^4 and if we define our Grassmannian over the field F, we have Gr(4,2) = 1 + F + 2F^2 + F^3 + F^4 meaning that Gr(4,2) is a disjoint union of a point, a copy of the field F, 2 copies of F^2, a copy of F^3, and a copy of F^4. Each copy of F^i is called an "i-cell" - or in this context a "Schubert cell of dimension i", because there may be many ways to decompose a space into cells, but there's a particularly nice one for Grassmannians. If F is the real or complex numbers, the cells F^i are actually open balls, and we can use this to study the topology of the Grassmannian. But if F is the field with q elements, we can use the cell decomposition to work out the *cardinality* of the Grassmannian. For example, the number of points in Gr(4,2) is |Gr(4,2)| = |1 + F + 2F^2 + F^3 + F^4| = |1| + |F| + 2|F|^2 + |F|^3 + |F|^4 = 1 + q + 2q^2 + q^3 + q^4 = [4 choose 2] I already said all this in "week184". But now, I want to use Young diagrams to get ahold of these cell decompositions. The answer should be staring us in the face. We know that the coefficient of any power of q in a q-binomial coefficient is the number of Young diagrams of a certain sort. And we also know it's the number of Schubert cells of a certain sort. There should be some way to see this directly. To do this, we just have to find a way to decompose the Grassmannian Gr(n,k) into cells, where each i-cell corresponds to a Young diagram with i boxes, k rows and n-k columns. The idea is simple. A point in Gr(n,k) is a k-dimensional subspace of the vector space F^n. We can describe such a thing by writing a list of row vectors that form a basis for this subspace. This gives a matrix. Of course, the same subspace can have lots of different bases. But we can always find a nice "standard" basis where our matrix is in "row echelon form". This is one of those things you're supposed to learn in linear algebra... but if you forget how it goes, don't worry. The idea is just to take a matrix and keep subtracting multiples of any row from the rows below it, and stuff like that, until your matrix looks something like this: 1 0 X 0 X X X 0 X X n = 10 (10 columns) 0 1 X 0 X X X 0 X X k = 4 (4 rows) 0 0 0 1 X X X 0 X X i = 19 (19 X's) 0 0 0 0 0 0 0 1 X X Here the X's are arbitrary numbers. The set of matrices of a given shape like this is isomorphic to F^i, where i is the number of X's. So, each shape gives us an i-cell in our Grassmannian! To finish the job, we just need to think of each "shape" as being a Young diagram with i boxes, k rows and n-k columns. And that's easy: we just remove the 0's and 1's from the above picture and make a Young diagram out of the X's: X X X X X X k = 4 (4 rows) X X X X X X n-k = 6 (6 columns) X X X X X i = 19 (19 boxes) X X Voila! Just for the heck of it, I'll work out the Schubert cell decomposition of Gr(4,2) by this technique. I'll write out the various shapes of row echelon form for matrices with 4 columns and 2 rows, and next to them the corresponding Young diagrams and the kind of i-cells we get: 0 0 1 0 0-cell 0 0 0 1 0 1 X 0 X 1-cell 0 0 0 1 1 X X 0 X X 2-cell 0 0 0 1 0 1 0 X X 2-cell 0 0 1 X X 1 X 0 X X X 3-cell 0 0 1 X X 1 0 X X X X 4-cell 0 1 X X X X This is nicely consistent with what we already know: [4 choose 2] = 1 + q + 2q^2 + q^3 + q^4 Okay, enough of this... now for some references. I've already given lots of Young diagram references in "week157", and lots of references on q-binomial coeffients and the like in "week183" - "week185". So, I'll just give some references to Pascal's triangle and this "UV = qVU" business. Here's the best place to learn the history of Pascal's triangle: 1) A. W. F. Edwards, Pascal's Arithmetical Triangle, Charles Griffin and Co., London, 1987. You'll see that the basic idea of Pascal's triangle goes back to Mersenne in 1636, and Tartaglia in 1556, and the Hindu mathematician Bhaskara in 1150, and the Jain mathematician Mahavira in 850... and so on into the mists of time. You'll also see that around 1655, Wallis came up with his wonderful formula: 2 4 4 6 6 8 8 pi/4 = - - - - - - - ... 3 3 5 5 7 7 9 by relating Pascal's triangle to the integral for the area of a quarter-circle! His method was ingenious and daring: it consisted of taking an integral formula for binomial coefficients, extrapolating it to guess that 4/pi = (1 choose 1/2) and then using properties of Pascal's triangle to express the right-hand side as an infinite product! One reason I like this is that I want to categorify the number pi. Let me explain.... Jim Dolan and I have a way to assign non-integral cardinalities to groupoids (see "week147"). The cardinality of the groupoid of finite sets is e, and this actually explains lots of things about e once you understand it. So, I'm always on the lookout for a really nice groupoid whose cardinality is related to pi. It's easy to find groupoids that do the job; the hard part is finding one that does so in an enlightening way. Of course pi is a subtler number than e, so this may be hard. The philosopher David Corfield has gotten interested in this challenge. Recently he took a crack at it by looking for a structure type whose generating function was 1 1.3 1.3.5 arcsin x = x + --- x^3 + ----- x^5 + ------- x^7 + ... 2.3 2.4.5 2.4.6.7 and evaluating this at the 1-element set to get a groupoid whose cardinality is pi/4. (If this is utterly mystifying, see "week185" and the references there.) I've discussed this with him, and I've also talked about it with my friend the combinatorist Bill Schmitt, and we made a little progress, but not enough. So, right now I like the idea of going back to Wallis' original formula for pi, and seeing how it relates to Pascal's triangle, and seeing if I can get anywhere with that! Embarrassingly, I don't know how the formula for arcsin(1) is related to Wallis' formula, even though they look sort of similar. Next: If you like the "UV = qVU" idea, you need to study the "noncommutative torus". This is a name for the C*-algebra generated by two unitaries U and V satisfying UV = qVU. The quantum Pascal triangle is built right in, because (U + V)^n = sum_k [n choose k] U^k V^{n-k} As we've seen, the noncommutative torus shows up naturally when we have a charged particle on the plane in a magnetic field. Jean Belissard has used this to relate the fractional quantum Hall effect to the K-theory of the noncommutative torus: 2) Jean Bellisard, K-theory of C*-algebras in solid state physics, in Lecture Notes in Physics vol. 237, Springer, Berlin, 1986, pp. 99-156. Connes has also studied these matters: 3) Alain Connes, Noncommutative Geometry, Academic Press, New York, 1994. More recently, string theorists have done a bunch of physics on the noncommutative torus! The reason is that string theory includes a 2-form field "B" which is similar in some ways to the magnetic field. For an overview of this with lots of references try: 4) Richard Szabo, Quantum field theory on noncommutative spaces, available as hep-th/0109162. On the other hand, if you're more of a pure mathematician you might like this: 5) Marc Rieffel, Noncommutative tori: a case study of noncommutative differential manifolds, in Geometric and topological invariants of elliptic operators Contemp. Math. 105, American Mathematical Society, 1990, pp. 191-211. By the way, the concept of "noncommutative manifold" has not so far received a precise definition, but someone told me Connes is working on such a definition and is all excited about it. That sounds promising! Whatever the definition, the noncommutative torus must be an example. ----------------------------------------------------------------------- This Table has truly exceptional and admirable properties; for besides concealing within itself the mysteries of Combinations, as we have seen, it is known by those expert in the higher parts of Mathematics also to hold the foremost secrets of the whole of the rest of the subject. - James Bernoulli, 1713. ----------------------------------------------------------------------- Previous issues of "This Week's Finds" and other expository articles on mathematics and physics, as well as some of my research papers, can be obtained at http://math.ucr.edu/home/baez/ For a table of contents of all the issues of This Week's Finds, try http://math.ucr.edu/home/baez/twf.html A simple jumping-off point to the old issues is available at http://math.ucr.edu/home/baez/twfshort.html If you just want the latest issue, go to http://math.ucr.edu/home/baez/this.week.html