# Why is Mathematics Possible: Tim Gowers’s Take on the Matter

In a previous post I mentioned the question of why is mathematics possible. Among the interesting comments to the post, here is a comment by Tim Gowers:

“Maybe the following would be a way of rephrasing your question. We know that undecidability results don’t show that mathematics is impossible, since we are interested in a tiny fraction of mathematical statements, and in practice only in a tiny fraction of possible proofs (roughly speaking, the comprehensible ones). But why is it that these two classes match up so well? Why is it that nice mathematical statements so often have proofs that are of the kind that we are able to discover?

# Why is mathematics possible?

## Spectacular advances in number theory

Last weeks we heard about two spectacular results in number theory.  As announced in Nature, Yitang Zhang proved that there are infinitely many pairs of consecutive primes $(p_n, p_{n+1})$ which are at most 70 million apart! This is a sensational achievement. Pushing 70 million to 2 will settle the ancient conjecture on twin primes, but this is already an extremely amazing breakthrough.  An earlier breakthrough came in 2005 when Daniel Goldston, János Pintz, and Cem Yıldırım proved that the gaps between consecutive primes $p_{n+1}-p_n$ is infinitely often smaller than $\sqrt {\log p_n} \log \log ^2 p_n$.

Update: A description of Zhang’s work and a link to the paper can be found on Emmanuel Kowalski’s bloog Further update: A description of Zhang’s work and related questions and results can be found now in Terry Tao’s blog. Terry Tao also proposed a new polymath project aimed to reading Zhang’s paper and attempting to improve the bounds.

Harald Helfgott proved that every integer is the sum of three primes.  Here the story starts with Vinogradov who proved it for sufficiently large integers, but pushing down what “sufficiently large” is, and pushing up the computerized methods needed to take care of “small” integers required much work and ingenuity.

## Why is Mathematics possible?

The recent news, and a little exchange of views I had with Boaz Barak, bring us back to the question: “Why is mathematics possible?” This is an old question that David Kazhdan outlined in a lovely 1999 essay “Reflection on the development of mathematics in the twentieth century.” The point (from modern view) is this: We know that mathematical statements can, in general, be undecidable.  We also know that a proof for a short mathematical statement can be extremely long. And we also know that even if a mathematical statement admits a short proof, finding such a proof can be computationally intractable. Given all that, what are the reasons that mathematics is at all possible?

It is popular to associate “human creativity” with an answer. The problem with incorrect (or, at least, incomplete) answers is that they often represent missed opportunities for better answers. I think that for the question “why is mathematics possible” there are opportunities (even using computational complexity thinking) to offer better answers.

# Fundamental Examples

It is not unusual that a single example or a very few shape an entire mathematical discipline. Can you give examples for such examples?

I’d love to learn about further basic or central examples and I think such examples serve as good invitations to various areas.

I asked this question over mathoverflow and it yielded around 100 examples. They are not equally fundamental and they are not equally suitable to be regarded as “examples,” but overall it is a very good list.  If you see some important example missing please, please add it.  Here are the examples classified to areas. (Of course, sometimes, the same example may fit several areas.)

### Logic and foundations:

$\aleph_\omega$ (~1890),  Russell’s paradox (1901), Halting problem (1936), Goedel constructible universe L (1938), McKinsey formula in modal logic (~1941), 3SAT (*1970), The theory of Algebraically closed fields (ACF) (?),

### Physics:

Brachistochrone problem (1696), Ising model (1925), The harmonic oscillator (?), Dirac’s delta function (1927), Feynman path integral (1948),

# Rodica Simion: Immigrant Complex

Rodica Simion immigrated to the United States from Romania. She was a Professor of Mathematices at George Washington University untill her untimely death on January 7, 2000. Her poem  “Immigrant complex” appeared in : “Against Infinity”, An Anthology of Contemporary Mathematical Poetry, edited by Ernest Robson and Jet Wimp, 1979, p. 66. Published by Primary Press, Parker Ford, PA, and Jet Wimp, Drexel University.

I have a
complex
not simplicial (it is-in fact-
involved)
not a cell-complex
(my cells are
fine)
not a CW

complex
(I have no com-
plexion no weight
problems)

it is a
language
complex

my thinking is of
class C-one even
C-infinity

it does not matter:
my speech
approximates it by
linear functions
only
my talk (being merely
polygonal) wastes
my
C-n (n  > > 0)
mind
Continue reading →

# A Proof by Induction with a Difficulty

The time has come to prove that the number of edges in every finite tree is one less than the number of vertices (a tree is a connected graph with no cycle). The proof is by induction, but first you need a lemma.

Lemma: Every tree with at least two vertices has a leaf.

A leaf is a vertex with exactly one neighbor.

Well, you start from a vertex and move to a neighbor, and unless the neighbor is a leaf you can move from there to a different neighbor and go on. Since there are no cycles and the tree is finite you must reach a leaf. Of course you describe the argument in greater detail and it seems that everybody is happy.

Good.

Theorem: A tree $T$  with $n$ vertices has $n-1$ edges.

After checking the basis for the induction we argue as follows: By the lemma $T$ has a leaf $v$ and once we delete $v$  and the edge containing it we are left with a graph $T'$ on $n-1$ vertices. Now, $T'$ has no cycles since $T$ did not have any. It takes some effort to show that $T'$ is connected. You describe it very carefully. Once this is done you know that $T'$ is a tree as well and you can apply the induction hypothesis.

Student: Now what about the case where $v$ is not a leaf? Continue reading

# Ulam and The Future of Mathematics

Ulam was scheduled to give a talk at the University of Chicago titled “The future of mathematics.” Stanislaw Ulam was a rather famous mathematician and a major player in building the H-bomb, so a large audience gathered.

# Polymath1: Success!

polymath” based on internet image search

And here is a link to the current draft of the paper.

Update:  March 26, the name of the post originally entitled “Polymath1: Probable Success!” was now updated to “Polymath1: Success!” It is now becoming clear that there are  three (perhaps four) new emerging proofs of DHJ. (April 2: See this post by Terry Tao. As this update was also based on briefly talking with Terry,  Terry’s new post gives a better description on the state of affairs and relations between the different proofs.)

The proof directly emerged from the project indeed looks conceptually different and simpler than all other proofs, and may indeed lead to the simplest known proof for Szemeredi’s theorem. (But for this we will have to wait for the details.) In addition, there is a new Ergodic proof by Tim Austin, which was partially inspired by and which used (among several other ingredients developed by Austin) some ideas and  results discovered in the polymath project. Both the original  ergodic proof and Austin’s proof were (at least roughly) “combinatorialized”.

In what sense was it a massive open collaboration? It is true that in the crucial phases of polymath, the phases where two concrete strategies for proofs were considered, the number of pivotal participants was not large. But there was an initial phase were probably more than a hundred mathematicians took part as observers and as commentators. The comments in this early phase played some role in the later developments but what is more important is that this stage have led to the (emerging) selection of the team that developed the proof. Among the hundreds, those who felt they have ideas that can be crucial, or methods that could be helpful, and were smart or lucky to be correct,  and had the persistence to follow these ideas and how these ideas can be combined with other ideas, became the pivotal players. The team that played the game was not so large, but the main massive ingredient of the project which accounts for its accessive mathematical power was in the “draft”. The team emerged from a massive number of participants. (So if you believe there were 10 pivotal players out of a hundred, think about the emergence of the team among ${{100} \choose {10}}$  possible (but, of course, not equally plausible) teams, as a point were  polymath had extra power.)

Two related posts: Tim Gowers raised inthis post  interesting questions regarding the possibility of projects were the actual number of provers will be massive. Here on my blog we have a post  with an “open discussion”  on what are the correct bounds for Roth type problems.  The emphasis is on “small-talk discussion” and not on actual “hard-nose researching”.

We took the opportunity to spend three days of “Purim” visiting northern Israel. Coming back I saw two new posts on Tim Gowers’s blog entitled “Problem solved probably” and “polymath1 and open collaborative mathematics.” It appears that “polymath1” has led to a new proof for the density version of Hales-Jewett’s theorem for k=3 which was the original central goal! Also it looks like the open collaboration mode (while not being a massive collaboration) was indeed useful.

Perhaps the most important thing is to make sure that a complete proof for the k=3 case is indeed in place (as these famous problems sometimes “fight back,” as Erdos used to say).  The outline is described here. If everything is OK as Tim and other participants expect, there are already some discussions or even plans about an extension to the general k case. This seems to be the next major step in the project.  There are also other fruits from the various threads of the polymath1 project. Overall, this looks very exciting! The mathematical result is a first-rate achievement, and the mode of cooperation is novel, interesting and appears genuinely useful.

Let me quote what Tim writes about it: “Better still, it looks very much as though the argument here will generalize straightforwardly to give the full density Hales-Jewett theorem. We are actively working on this and I expect it to be done within a week or so. (Work in progress can be found on the polymath1 wiki.) Better even than that, it seems that the resulting proof will be the simplest known proof of Szemerédi’s theorem.” sababa!