Archive for the ‘Mathematics’ Category

2008 SIAM Annual Meeting

October 22, 2007

Lenore Cowen (a co-chair of the 2008 SIAM annual meeting) asked if I might write a post here to help publicize that conference, and I’m very happy to do so. The conference will be held in San Diego from July 7-11, and it looks like it will cover a wider spectrum of topics than is usual for SIAM, so you might consider attending even if it’s not on your normal conference circuit.

The themes for the 2008 meeting are computational science & engineering, data mining, dynamical systems, geosciences, imaging science, linear & multi-linear algebra, biological, social, and internet networks, and enabling complex simulations with scientific software. There is also a quite diverse list of invited speakers.

At SIAM’s annual meeting you are encouraged to propose and organize your own mini-symposium. There are also regular contributed talks and posters. Submission deadlines are January 14 for minisymposium proposals, and January 28 for abstracts for contributed and minisymposium speakers. See the conference web-site for more details.

Advertisements

Using Unambiguous Notation

October 19, 2007

I’ve mentioned their book the “Structure and Interpretation of Classical Mechanics” a couple times already; today I’d like to recommend that you read a wonderful short paper by Gerald Jay Sussman and Jack Wisdom, called “The Role of Programming in the Formulation of Ideas,” which helps explain why understanding physics and the other mathematical sciences can sometimes be so difficult. The basic point is that our notation is often an absolute mess, caused by the fact that we use equations like we use natural language, in a highly ambiguous way:

“It is necessary to present the science in the language of mathematics. Unfortunately, when we teach science we use the language of mathematics in the same way that we use our natural language. We depend upon a vast amount of shared knowledge and culture, and we only sketch an idea using mathematical idioms.”

The solution proposed is to develop notation that can be understood by computers, which do not tolerate ambiguity:

“One way to become aware of the precision required to unambiguously communicate a mathematical idea is to program it for a computer. Rather than using canned programs purely as an aid to visualization or numerical computation, we use computer programming in a functional style to encourage clear thinking. Programming forces one to be precise and formal, without being excessively rigorous. The computer does not tolerate vague descriptions or incomplete constructions. Thus the act of programming makes one keenly aware of one’s errors of reasoning or unsupported conclusions.”

Sussman and Wisdom then focus on one highly illuminating example, the Lagrange equations. These equations can be derived from the fundamental principle of least action. This principle tells you that if you have a classical system that begins in a configuration C1 at time t1 and arrives at a configuration C2 at time t2, the path it traces out between t1 and t2 will be the one that is consistent with the initial and final configurations and minimizes the integral over time of the Lagrangian for the system, where the Lagrangian is given by the kinetic energy minus the potential energy.

Physics textbooks tell us that if we apply the calculus of variations to the integral of the Lagrangian (called the “action”) we can derive that the true path satisfies the Lagrange equations, which are traditionally written as:

lagrange001.jpg

Here L is the Lagrangian, t is the time, annd qi are the coordinates of the system.

These equations (and many others like them) have confused and bewildered generations of physics students. What is the problem? Well, there are all sorts of fundamental problems in interpreting these equations, detailed in Sussman and Wisdom’s paper. As they point out, basic assumptions like whether a coordinate and its derivative are independent variables are not consistent within the same equation. And shouldn’t this equation refer to the path somewhere, since the Lagrange equations are only correct for the true path? I’ll let you read Sussman and Wisdom’s full laundry list of problems yourself. But let’s turn to the psychological effects of using such equations:

“Though such statements (and derivations that depend upon them) seem very strange to students, they are told that if they think about them harder they will understand. So the student must either come to the conclusion that he/she is dumb and just accepts it, or that the derivation is correct, with some appropriate internal rationalization. Students often learn to carry out these manipulations without really understanding what they are doing.”

Is this true? I believe it certainly is (my wife agrees: she gave up on mathematics, even though she always received excellent grades, because she never felt she truly understood). The students who learn to successfully rationalize such ambiguous equations, and forget about the equations that they can’t understand at all, are the ones who might go on to be successful physicists. Here’s an example, from the review of Sussman and Wisdom’s book by Piet Hut, a very well-regarded physicist who is now a professor at the Institute for Advanced Studies:

“… I went through the library in search of books on the variational principle in classical mechanics. I found several heavy tomes, borrowed them all, and started on the one that looked most attractive. Alas, it didn’t take long for me to realize that there was quite a bit of hand-waving involved. There was no clear definition of the procedure used for computing path integrals, let alone for the operations of differentiating them in various ways, by using partial derivatives and/or using an ordinary derivative along a particular path. And when and why the end points of the various paths had to be considered fixed or open to variation also was unclear, contributing to the overall confusion.

Working through the canned exercises was not very difficult, and from an instrumental point of view, my book was quite clear, as long as the reader would stick to simple examples. But the ambiguity of the presentation frustrated me, and I started scanning through other, even more detailed books. Alas, nowhere did I find the clarity that I desired, and after a few months I simply gave up. Like generations of students before me, I reluctantly accepted the dictum that ‘you should not try to understand quantum mechanics, since that will lead you astray for doing physics’, and going even further, I also gave up trying to really understand classical mechanics! Psychological defense mechanisms turned my bitter sense of disappointment into a dull sense of disenchantment.”

Sussman and Wisdom do show how the ambiguous conventional notation can be replaced with unambiguous notation that can even be used to program a computer. Because it’s new, it will feel alien at first; the Lagrange equations look like this:

functional002.jpg

It’s worth learning Sussman and Wisdom’s notation for the clarity it ultimately provides. It’s even more important to learn to always strive for clear understanding.

One final point: although mathematicians do often use notation that is superior to physicists’, they shouldn’t feel too smug; Sussman and Wisdom had similar things to say about differential geometry in this paper.

Princeton Companion to Mathematics

October 5, 2007

From Terence Tao’s excellent blog, I learned about the upcoming Princeton Companion to Mathematics (PCM), a roughly 1000-page survey of and introduction to mathematics at the undergraduate level. It looks like the PCM editors have lined up a distinguished cast of mathematicians to write comprehensible articles covering all of mathematics. The editor-in-chief is Timothy Gowers, who like Tao is a Fields Medalist, and who has very recently started his own blog.

Gowers gives instructions for finding a large sample of articles that will appear in the book, but they are not completely transparent, so follow these:

  1. Go here.
  2. Use Username “Guest” and Password “PCM”.
  3. Click on “Resources” in the sidebar.
  4. Click on “Sample articles” in the sidebar.

You’ll find many interesting and highly readable articles in .pdf format.

Consistent Quantum Theory

September 4, 2007

Quantum mechanics is a notoriously confusing and difficult subject, which is terribly unfortunate given its status as a fundamental theory of how the world works. When I was an undergraduate and graduate student of physics in the 1980’s, I was always unsatisfied with the way the subject was presented. We basically learned how to calculate solutions to certain problems, and there was an understanding that you were better off just avoiding the philosophical issues or the paradoxes surrounding the subject. After all, everybody knew that all the challenges raised by physicists as eminent as Einstein had ultimately been resolved experimentally in favor of the “Copenhagen interpretation.”

Still, there was a lot of weird stuff in the Copenhagen interpretation like the “collapse of the wave-function” caused by a measurement, or apparently non-local effects. What I wished existed was a clearly-defined and sensible set of “rules of the game” for using quantum mechanics. The need for such a set of rules has only increased with time with the advent of the field of quantum computing.

cover.gif

In his book, “Consistent Quantum Theory,” (the first 12 out of 27 chapters are available online) noted mathematical physicist Robert Griffiths provides the textbook I wished I had as a student. With contributions from Murray Gell-Mann, Roland Omnes, and James Hartle, Griffiths originated the “consistent history” approach to quantum mechanics which is explained in this book, .

The best summary of the approach can be obtained from the comparison Griffiths makes between quantum mechanics and the previous classical mechanics. Quantum mechanics differs from classical mechanics in the following ways:

1. Physical objects never posses a completely precise position or momentum.
2. The fundamental dynamical laws of physics are stochastic and not deterministic, so from the present state of the world one cannot infer a unique future (or past) course of events.
3. The principle of unicity does not hold: there is not a unique exhaustive description of a physical system or a physical process. Instead reality is such that it can be described in various alternative, incompatible ways, using descriptions which cannot be combined or compared.

It is the 3rd point which is the heart of the approach. In quantum mechanics, you are permitted to describe systems using one “consistent framework” or another, but you may not mix incompatible frameworks (basically frameworks using operators that don’t commute) together.

Griffiths uses toy models to illustrate the approach throughout the book, and provides resolutions for a large number of quantum paradoxes. He stresses that measurement plays no fundamental role in quantum mechanics, that wave function collapse is not a physical process, that quantum mechanics is a strictly local theory, and that reality exists independent of any observers. All of these points might seem philosphically natural and unremarkable, except for the fact that they contradict the standard Copenhagen interpretation.

This is a book that will take some commitment from the reader to understand, but it is the best explanation of quantum mechanics that I know of.

Duke and Pawn Endgames

September 3, 2007

Note: to understand this post, you don’t need to know anything about chess; I’ll explain everything necessary right here.

One of the best ways for a chess beginner to improve is to study king and pawn endgames, and one of the best ways to do that is to play a game with only kings and pawns. Just remove all the rest of the pieces, and have at it.

Unfortunately, while Chess with just kings and pawns is not trivial, as you improve you will eventually outgrow it, because between two good chess players, the game is very likely to end in a draw.

As I mentioned in an earlier post, my son Adam likes to design games, and he designed this very clever variant of the King and Pawn endgame that eliminates the possibility of a draw.

duke001.jpg

Rules:

Set up the pieces as above, with four pawns plus a King for both White and Black.

The players alternate moves, starting with White.

The pawns move as in chess: one square forward, or optionally two squares forward if they haven’t moved yet, and they capture a piece one square ahead of them diagonally.

Pawns may still capture en passant as in Chess, which means the following. If an enemy pawn moves two squares forward, and one of your pawns could have captured it if it had only moved one square forward, you may capture that pawn as if it had only moved one square forward, but only if you do so with your pawn on the turn immediately after the enemy pawn moves.

The Kings can only move one square up or down, or left or right; they cannot move diagonally. (Such limited versions of Kings are sometimes called “Dukes;” hence the title of this post.)

You win the game immediately if you capture the opponent’s King, or if one of your pawns reaches the other side of the board.

You must always move; if you cannot make a legal move, you lose the game. (This is different from Chess, where stalemate is a draw.)

You may not make a move which recreates a position that has previously occurred during the game. (This is also different from Chess, but such a rule exists in Shogi, the Japanese version of Chess.)

That’s all the rules. In this game, draws are impossible, even if only two Kings remain on the board. For example, imagine that the White King is on a1, and the Black King is on b2. If White is to move, he loses, because he must move to a2 or b1, when Black can capture his King. But if Black is to move, he must retreat to the north-east, when White will follow him, until Black eventually reaches h8 and has no more retreat.

So arranging that your opponent is to move if the two Kings are placed on squares of the same color (if there are no pawn moves) is the key to victory. This concept, known as the “opposition,” is also very important in ordinary Chess King and pawn endgames, which is why skill at chess will translate into skill in this variant, and why improving your play at this variant will improve your Chess. Of course, the pawns are there, and they complicate things enormously!

Naturally, one can consider other starting positions, with different numbers of pawns.

This game can be analyzed using the methods of Combinatorial Game Theory (CGT). Noam Elkies, the Harvard mathematician, has written a superb article on the application of CGT to ordinary chess endgames, but it required great cleverness for him to find positions for which CGT could be applied; with this variant, the application of CGT should be much easier.

Combinatorial Game Theory

August 29, 2007

Combinatorial Game Theory (CGT) is a mathematical discipline that studies two-player, zero-sum games, where the players play sequentially, and there is perfect information and no chance. The aim of CGT is to build mathematical theories that will help players win such games! In practice, the ideas from CGT are of minimal help to the serious player in more complicated games like Chess or Go, but the theories are extremely helpful for simpler but still non-trivial games like Dots-and-Boxes.

9781568811307.jpg

The CGT bible is Winning Ways for Your Mathematical Plays, a four-volume set of books (for the 2nd edition from the early 2000’s; the first edition from 1982 was in two volumes), by the eminent mathematicians Elwyn Berlekamp, John Horton Conway, and Richard Guy.

The basic idea of CGT is to develop a calculus, which lets you assign a value to a position in the game. One normally considers games with the condition that a player who cannot move loses. If both players are without a move in a position (whoever moves loses), the position is assigned a value of 0. If the player on the right can make one move that transforms the position to one of value 0, and the player on the left cannot move at all, the position is assigned a value of 1 (if the roles are reversed, the position has value -1).

Now what happens if the player on the left has a move to a position of value 0, and the player on the right has a move to a position of value 1? What is the value of that position? It turns out to be worth 1/2, as can be seen by considering the position obtained by adding such two such positions together with a position of value -1, when one gets back to a position of value 0 where whoever moves loses (I’ll let you work out the details).

There are more different kinds of values than just fractions. Berlekamp, Conway, and Guy consider a multitude of different interesting games, which give rise to ever deeper mathematics, and game positions with strange values along with complex rules for combining those values.

The writing is informal, with constant punning, but the mathematics is serious. Still, one charm of the field is that there is no pre-requisite mathematical material needed to understand these books–bright high school students can launch right in.

After finishing “Winning Ways,” the ambitious student can move on to the two volumes “Games of No Chance” and “More Games of No Chance” (note that nearly all the papers in these books are available online), and then move onto the rest of the papers collected at David Eppstein‘s CGT page.

Also, take a look at Aaron Siegel‘s Combinatorial Game Suite software to help you do CGT computations.

There’s still much more to say, but I’ll leave that for other posts.