Desert Island Theorems

Suppose you were cast away on a desert island. You’re only allowed to take a maximum of eight known theorems with you, along with rudimentary results such as ZFC axioms together with ‘boring stuff’ such as mathematical induction over the naturals, commutativity of real multiplication and the least upper-bound property of \mathbb{R}. Everything else you have to prove yourself.

So, which eight theorems would you take with you on a desert island? It would be a waste of time to take the Baire category theorem, for instance; despite being extremely useful, it’s pretty trivial to prove. The same applies to the Dirichlet pigeonhole principle. On the other end of the spectrum, whilst Fermat’s Last Theorem is very difficult to prove, the end result is not nearly as useful as the machinery developed by Andrew Wiles in the course of solving this problem.

At the end of the post, there’s a ‘comments’ section for you to mention which theorems you would choose if marooned on a desert island. Here are my choices:

8. Density Hales-Jewett theorem

The ordinary Hales-Jewett theorem is quite straightforward to prove, using plenty of induction and the Dirichlet pigeonhole principle. On the other hand, the density analogue (c.f. Szemeredi’s theorem) is much deeper, requiring the entire Polymath project to establish a purely combinatorial proof (the original proof involved ergodic theory).

I’m not sure whether I’ve ever required the full force of Density Hales-Jewett, but Szemeredi’s theorem and ordinary Hales-Jewett have proved invaluable to me.

7. The abc theorem

Disclaimer: I don’t think that a second person is capable of understanding Mochizuki theory*, so this might still be classed as a conjecture until someone can peer-review the paper.

* Formerly known as inter-universal Teichmüller theory, although Doron Zeilberger makes a good argument that it should be renamed.

The abc conjecture is concerned with triples of coprime naturals, a < b < c, such that a + b = c. It states that the radical d (larger squarefree divisor) of abc cannot be much smaller than c. Specifically, for any ε > 0, we can only find finitely many examples where d < c^{1 - \epsilon}. This asserts that Beal’s conjecture holds in all but a finite number of cases, as does Fermat’s last theorem.

6. Max-flow min-cut theorem

I would have ranked this higher, except for the fact that it has a short elementary proof. The statement of the theorem is about networks, which are directed (multi-)graphs where each edge has a maximum capacity. A flow in a network is an assignment of nonnegative real values to each of the edges, such that they do not exceed the capacity, and that Kirchoff’s current law is obeyed at all vertices (with the exception of the source and sink vertices). The statement of the theorem is that the maximum flow attainable is equal to the minimum capacity of a cut (partitioning of the graph into two sets of vertices, so as to separate the source from the sink).

It can be used to prove Menger’s theorem in graph theory, Hall’s marriage theorem, Dilworth’s theorem on partially-ordered sets, and the Erdős-Szekeres theorem (although this also follows from Dilworth’s easier twin, Mirsky’s theorem).

5. Borsuk-Ulam theorem

This is informally stated as ‘two antipodal points on the Earth’s surface have the same temperature and pressure’. More generally, if we have a continuous function f from the n-sphere to \mathbb{R}^n, then we can find antipodal points x and y such that f(x) = f(y).

A corollary is the Brouwer fixed-point theorem, and all that that implies.

4. Gödel’s completeness theorem

This is one of the most beautiful and powerful theorems in mathematical logic. If a statement in first-order logic is consistent (i.e. we cannot prove a contradiction), then this asserts that there exists a finite or countable model. Consequently, we establish logical compactness: a set of first-order sentences has a model if and only if every finite subset has a model.

With the compactness theorem, the problem of computing the chromatic number of the plane is reduced to the more tractable problem of determining the maximum chromatic number of any finite unit-distance graph.

3. Every set can be well-ordered

This is equivalent to the axiom of choice, but much friendlier than the boring statement of AC involving a choice function. The main advantage is that it endows one with the power of transfinite induction over arbitrary sets, which is one of my favourite tools for proving theorems:

  • Constructing an infinite game where neither player has a winning strategy;
  • 2-colouring the plane such that there is no continuous monochromatic path;
  • Proving that the direct product of two infinite sets has cardinality equal to the larger of the two sets (by Cantor normal form);
  • Establishing Zorn’s lemma to show that any vector space has a basis…

2. Classification of finite simple groups

This is an impossible endeavour for a single individual to attempt, with the current proof being a 5000-page behemoth comprising many different papers. The Classification obviously reduces deep results such as the Feit-Thompson theorem (that there are no finite simple groups with odd composite order) and Burnside’s p^a q^b theorem to easy corollaries. (Of course, these theorems were almost certainly used in establishing the Classification, so this would be logically circular.)

It’s also a very beautiful theorem, with a vast wealth of exciting groups such as PSL(2,7), exceptional Lie groups over finite fields, and the Monster group. The Classification was also involved in proving theorems in areas outside group theory, such as establishing which graphs are 4- and 5-ultrahomogeneous.

1. Bezout’s theorem

This is a result in geometry, which says that if a degree-m and degree-n algebraic curve intersect in finitely many points, then they do so in at most mn points. Moreover, equality holds when the curves are on the complex projective plane, and we count intersections with the appropriate multiplicity.

An immediate corollary of this is the fundamental theorem of calculus, by taking one of the curves to be the line y = 0 and the other to be y = f(x) (where terms have been multiplied by appropriate powers of z to homogeneise them, and f is an arbitrary polynomial).

Also, it can be used to establish the Cayley-Bacharach theorem of cubic curves, which itself can prove the associativity of the elliptic curve group operation, Pascal’s theorem, Pappus’ theorem, and thus Desargues’ theorem.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

16 Responses to Desert Island Theorems

  1. Johnicholas says:

    Is it reasonable to divide mathematics into “frontier-work”, classifying as-yet-unknown propositions into true and false, and “internal-work”, deciding which parts of the known world of mathematics ought to be broad highways and which ought to be narrow dirt roads?

    The goal of internal work is presumably to minimize the computational effort in getting from anywhere to anywhere else inside the known world, which is to say, to index and compress the known world.

    There has been a lot of progress in text compression, certainly measured and made visible by, (and probably stimulated by) benchmarks like the Calgary Corpus or the Hutter Prize. Do you think a similar benchmark for compressing the known results of mathematics would be valuable? It might consist of a formal language of propositions and a set of example propositions in the language (or more likely, a portfolio of example-generator programs).

    • apgoucher says:

      I think that distinction is an appropriate one. For example, the first proof of the Classification of Finite Simple Groups was really long, and there’s now an effort to clean it up somewhat. I believe that they’ve succeeded in reducing its length from about 10000 to 5000 pages.

      Proof-verifying software such as Coq is particularly satisfying, since it’s less likely to enable an error to slip through than a human-readable proof (the only vulnerability would be if the software contains a bug or its axioms are arithmetically unsound). I’m not sure what portion of mathematics has been Coq-ified, although it includes the Four Colour Theorem.

  2. I haven’t come up with all eight yet, but I would definitely bring the Uniformization Theorem, which states that any simply connected surface with negative Euler characteristic can be given a metric with constant curvature -1. (It actually does more: Any simply connected Riemann surface is conformally equivalent to the sphere, the complex plane, or the hyperbolic plane. But I only use the theorem to get hyperbolic metrics on genus g surfaces where g>1, so I don’t usually think about the rest of it.) I might also bring the ham and cheese sandwich theorem because I’d probably be pretty hungry. (I know, that was terrible.)

    The fundamental theorem of calculus would be nice too. (Or when you bring a theorem, do you get every theorem that is used to prove it for free? Because there’s a lot of stuff that implicitly uses the fundamental theorem of calculus.)

    I study Teichmüller theory, and I couldn’t really tell how much of Zeilberger’s opinion #88 was satirical. I do wish we would stop naming increasingly unrelated things after him, and in my opinion, whatever inter-universal Teichmüller theory is, it’s very unlike anything Teichmüller actually did. Periodically researchers in my area of math talk about how we should rename stuff after less repugnant people who also contributed more to the way we understand the theory now, but it never quite catches on. I do think it’s good that we talk about the issue and make young people in the field (like myself) aware of a little bit of the history.

    • apgoucher says:

      Yes, the Uniformisation Theorem is very elegant, and quite unexpected. For instance, you get conformal embeddings of Hurwitz surfaces in three-dimensional space (e.g. the Klein quartic surface, which admits that beautiful tiling with PGL(2,7) symmetry).

      If you take a theorem, you get the immediate corollaries for free. I don’t think that you automatically get the substance of the proof, which is why it’s better to take the Tanayama-Shimura theorem than Fermat’s Last Theorem.

      Considering its publication date (April 1st), to which Zeilberger explicitly draws attention, it wouldn’t surprise me if the majority of the opinion was intended to be satirical. Nevertheless, he does have a very good point, and since we already name mathematical theorems after completely unrelated people (c.f. Pell equations) it would not ruin mathematical tradition to boycott Teichmüller.

  3. wojowu says:

    I don’t know any particularily useful theorems (I like simple to formulate but harder to prove facts, like Dirichlet’s theorem), but 4. header should say compactness, not completeness, I think.

  4. Anonymous says:

    If you’re going to take a false theorem, you ought at least to choose the nice sort of false theorem that implies all the other theorems (and their negations).

    • apgoucher says:

      Any false theorem, when coupled with its counter-example, would enable you to derive ‘false’ and therefore all statements by the Principle of Explosion. Which of those eight theorems are you contesting? (The abc conjecture is the only one where the proof is still going through the stages of peer-reviewing; all of the others are established.)

  5. notatab says:

    Classification of complex semi-simple lie algebras by Dynkin diagrams. There’s a story (which may be apocryphal but was told to me by a fairly eminent man) that they were considered for inclusion on the Pioneer disc as proof of intelligent life on Earth.

  6. Pingback: Brouwer’s fixed-point theorem | Complex Projective 4-Space

  7. Pingback: An enormous theorem: the classification of finite simple groups | Computers & Science

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s