Monday, December 19, 2016

The very first Ramseyian Theorem

Many years ago I noticed that in several books on Ramsey Theory  mention that  Hilbert proved the first   Ramseyian theorem.  The theorem is the Hilbert Cube Lemma (HCL) which in modern language is:

DEFINITION: Let x, y1, y2,...,yn   be natural numbers. Then the n-cube on x, y1, y2, ..., yn is

{ x+ e1*y1 + ... + en*yn : e1,...,en \in {0,1} }

HCL: for all c there exists H=H(m,c) such that for all c-colorings of {1,...,H} there exists a monochromatic cube.

Here are some quotes about this theorem from texts on Ramsey Theory:

Graham-Rothchild-Spencer's book Ramsey Theory: In the middle of Szemeredi's proof of a cube lemma with double exp bounds on H (Hilbert's proof gives tower-type bounds) they write:

Historical Note: In 1892 D. Hilbert proved that, for any k\ge 1, if N (the naturals) is
finitely colored then there exists in one color infinitely many translates of a k-cube.

THATS IT! No mention of WHY Hilbert proved this. According to the index this is the only mention of Hilbert in the book.

From Landman and Robertson Ramsey Theory over the Integers:

The results that are generally accepted to be the earliest Ramsey-type theorems are due,
in chronological order, to Hilbert, Schur, and van der Warden.

Later in the exercises he asks the reader to prove HCL from VDW's theorem.

THATS IT! No mention of WHY Hilbert proved this According to the index this is the only
mention of Hilbert in the book.

Andrew Soifer's The Mathematical Coloring Book.  This is a very scholarly work about the history of coloring theorems. (For my review see here .) I expected to get MORE on why Hilbert did. Soifer  does devote two pages to Hilbert. But as for WHY Hilbert did it all he says is:

As far as we know today, the first Ramseyian-type results appeared in 1892 as a little noticed
assertion in [Hil]. Its author was the great David Hilbert. In this work Hilbert proved the theorem of our interest merely as a tool for his study of irreducibility of rational functions.

I wanted to know what Hilbert proved (this was easy- I looked up the Hilbert Irreducibility
theorem) and how he used his Cube Lemma to do it.  I assumed this would be known and out there
in English since the Hilbert Irreducibility Lemma is very important.

But NO- I found the original German Version but THATS IT.

Well, if you want something done, best to do it yourself. Except that I don't know German.


Here is a paper with Mark Villarino and Ken Regan, in English, that has the proof.
In some later post I'll describe how the paper came about.

For now I will state the Hilbert Irred Theorem, two-variable case:

If f(x,t) is in Z[x,t] and is irreducible then for infinitely many natural numbers t,  f(x,t) is irreducible.


  1. This fine Villarino/Gasarch/Regan preprint ("Hilbert's Proof of His Irreducibility Theorem", arXiv:1611.06303) builds largely upon the theorems and methods of Victor Puiseux. Computational Complexity readers can find much further information regarding Victor Puiseux' persona and works in Étienne Ghys' just-released notes A Singular Mathematical Promenade (AMS Open Math Notes, 2016).

    Beyond their intrinsic mathematical interest, Ghys' notes are notable too for their impeccable typographic quality and overall beauty of visual design … these notes make a wonderful holiday gift for the mathematicians in your life … especially if you don't mind that A Singular Mathematical Promenade is released under a Creative Commons License (and hence is entirely free-as-in-freedom, both economically and informatically).

    Gift-givers who prefer the physicality of paper can take inspiration from the works of the artist Caspar David Friedrich, whose paintings Ghys' notes features prominently, including in particular Friedrich's “Wanderer above the sea of fog” (p. ii) "Tree of crows" (p. 284), and "Man and woman contemplating the moon" (p. 286).

    The Wikipedia page "Humboldtian Science" — which features Friedrich's “Wanderer above the sea of fog" — then leads us to Andrea Wulf's just released biography The Invention of Nature: Alexander von Humboldt's New World (2016). Wulf's history-of-natural-science very beautifully complements (as it seems to me) Puiseux' beautiful mathematics and Friedrich's beautiful paintings. That is Wulf's (purchased) book, together with Ghys' (free-as-in-freedom) AMS Open Math Note, jointly make a wonderful gift.

    Can any practical benefits be associated to this rich banquet of mathematical beauty-and-truth? Yah, sure, you betcha! My own interest in the Puiseux-grounded mathematics that Ghys/Villarino/Gasarch/Regan discuss is associated to the still-mysterious role(s) of algebraic singularities in the tensor-network state-spaces that nowadays propagate throughout the global STEAM enterprise (see e.g. comments #84 and #88 in the recent Shtetl Optimized essay "My quantum computing cartoon with Zach Weinersmith"). Needless to say, it will be a long time before the Friedrich-style mathematical fog entirely lifts from this vast landscape of algebraic, geometric, informatic, combinatorical, computational, practical, and dynamical structures and capacities (both classical and quantum).

    We are all of us fortunate, in this holiday season, to be so diversely gifted with shared appreciations of beauty and truth; and we are fortunate too, to be blessed with plenty of Friedrich-style fog, that throughout decades to come will no doubt lift, to slowly unveil still more beauty and truth.

    Best wishes for a happy holiday season are hereby extended to all! :)

  2. Bill, thanks for the blog post and to you and your coauthors for the article. I've read through the article once and have a question based on the end of the article.

    At the end you have some comments about the context that Hilbert was working in. In addition to Hilbert's cube lemma and Ramsey's original paper (connected with math. logic) there was Schur's theorem on sum free sets. Do we know if Hilbert knew of Ramsey's work? Schur's? Did he see the connection?

    Bill, Lance, thanks for the work you've put into the CC weblog and may you and yours have happy holidays and new year!

    1. Hilbert's Cube lemma was in 1894
      Schur was BORN in 1891. Most 3 year olds know very little combinatorics.
      Ramsey was BORN in 1903.
      So surely when Hilbert proved his Cube Lemma he could not have know of the connections.

      But I think you mean later. But again, no. There is no evidence
      that Hilbert knew of Ramsey's work (was it that well known?)
      or of Schur's work.
      The connection to Ramsey's work would have been hard to
      figure out- in fact, while we all think of Ramsey's theroem
      and VDW's theorem and HCL as being parts of Ramsey Theory,
      Mathematically Ramsey's theorem and HCL do not share anything except the notion of `when you color big enough stuff there is a nice monochromatic substructure'

      Schur's theorem also- it would have been hard to see the

      BUT- VDW's theorem YES- VDW implies HCL. And VDW was alive
      at the right time. But I doubt Hilbert knew of it since VDW's
      theorem was not really out there until it was publicized by
      Khinchin in

      Three pearls of Number THeory
      which was published in 1952- and
      Hilbert died in 1943.

      Three pearls:

      All this bring us back to my motivation for the paper--- this theorem seemed to be in danger of being lost. Hilbert's lack of interest is part of that reason.

  3. I can mention that my initial role was helping Bill deal with that German. I translated the paper but without full command of terms whose literal translation becomes oxymoronic in current English math usage, such as "whole rational number." Then Bill and I couldn't get past one point in the proof of the Irreducibility Theorem until Mark both did a fresh translation and pushed through the obstacle.