Wednesday, November 28, 2007

Why Mathematics?

Terry Tao points to a beautiful article written by Michael Harris for the Princeton Companion to Mathematics, titled Why Mathematics, You Might Ask.

The titular question is the point of departure for a fascinating discussion on the foundations of mathematics, on the philosophy of mathematics, on post-modernism, on the "anthropology" approach to social science studies of mathematics, and on what mathematicians think they are doing, and why.

In general, I find articles on philosophical issues in mathematics to be more readable and enlightening when written by mathematicians. Perhaps it's just that they lack the sophistication of the working philosopher, a sophistication which I mistake for unreadability. But I also find that mathematicians tend to bring up issues that matter more to me.

For example, the metaphysical discussions on the "reality" of mathematical objects and the "truth" of theorems are all well and good, but the really interesting questions seem to be different ones.

The formalist view of mathematics, for example, according to which mathematics is the derivation of theorems from axioms via formal proofs, or as Hilbert apparently put it, "a game played according to certain simple rules with meaningless marks on paper," does not begin to capture what mathematics, just as "writing one sentence after another" does not capture what poetry is. (The analogy is due to Giancarlo Rota.) Indeed one of the main fallacies that follow by taking the extreme formalist position as anything more than a self-deprecating joke is to consider mathematical work as tautological. That is, to see a mathematical theorem as implicit in the axioms and so its proof as not a discovery. (Some of the comments in this thread relate to this point.) Plus, the view does not account for the difference between "recreational" mathematics and "real" mathematics, a difference that I don't find it easy to explain in a few words, probably because I don't have a coherent view of what mathematics really is.

It's not quite related, but I am reminded of a conversation I had a long time ago with Professor X about faculty candidate Y.

[Not an actual transcript, but close enough]

X: so what do you think of theory candidate Y?
Me: he is not a theory candidate.
X: but his results have no conceivable application.
Me: there is more to doing theory than proving useless theorems.
X: that's interesting! Tell me more


I enjoyed Harris's suggestion that "ideas" are the basic units of mathematical work, and his semi-serious discussion of whether ideas "exist" and on their importance.

There are indeed a number of philosophical questions about mathematics that I think are extremely interesting and do not seem to figure prominently in the social studies of mathematics.

For example, and totally randomly:


  1. When are two proofs essentially the same, and when are they genuinely different?
  2. What makes a problem interesting? What is the role of connections in this determination?
  3. What makes a theorem deep?
  4. What does it mean when mathematicians say that a certain proof explains something, or when they say that it does not?

Tuesday, November 27, 2007

Terminology

Different communities have different traditions for terminology. Mathematicians appropriate common words, like ring, field, scheme, ideal,... and the modern usage of the term bears no connection with the everyday meaning of the word. Physicists have a lot of fun with their sparticles and their strangeness and charm and so on. Theoretical computer scientists, like the military, and NASA, prefer acronyms.

We have some isolated examples of felicitous naming. Expander, for example, is great: it sounds right and it is suggestive of the technical meaning. Extractor is my favorite, combining a suggestion of the meaning with a vaguely threatening sound. I think it's too bad that seedless extractor has come to pass, because it evokes some kind of device to get grape juice. (I was on the losing side that supported deterministic extractor.)

Unfortunate namings are of course more common. Not only is the complexity class PP embarrassing to pronounce, but its name, derived from Probabilistic Polynomial time, is a poor description of it. By analogy with #P and $\oplus$P, it should be called MajP.

I heard the story of a famous (and famously argumentative) computer scientist complaining to one of the authors of the PCP theorem about the term PCP, which stands for Probabilistically Checkable Proof. "I too can define a probabilistic checker for SAT certificates," he supposedly said, "with probability half check the certificate, with probability half accept without looking at it." The point being that the terminology emphasizes a shortcoming of the construction (the probabilistic verification) instead of the revolutionary feature (the constant query complexity). Personally, I would prefer Locally Testable Proof.

Of course we will never change the name of PP or PCP, and the seedless extractors are here to stay, but there is one terminology change for which I'd like to start a campaign.

Naor and Naor constructed in 1990 a pseudorandom generator whose output is secure against linear tests. They called such a generator $\epsilon$-biased if the distinguishing probability of every linear test is at most $\epsilon$. Such generators have proved to be extremely useful in a variety of applications, most recently in the Bogdanov-Viola construction of pseudorandom generators again degree-2 polynomials.

Shall we start calling such generators $\epsilon$-unbiased? Seeing as it is the near lack of bias, rather than its presence, which is the defining feature of such generators?

(I know the reason for the Naor-Naor terminology: zero-bias generator makes perfect sense, while zero-unbiased makes no sense. But how about the fact that it is technically correct to say that the uniform distribution is $\frac {1}{10}$-biased?)

[Update: earlier posts on the same topic here and here]