mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, the Hales–Jewett theorem is a fundamental

combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...

result of

Ramsey theory Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of the mathematical field of combinatorics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in R ...

named after

Alfred W. Hales Alfred Washington Hales (born November 30, 1938) is an American mathematician, a professor emeritus of mathematics at the University of California, Los Angeles, and one of the namesakes of the Hales–Jewett theorem. He was born in Pasadena, Cali ...

and Robert I. Jewett, concerning the degree to which high-dimensional objects must necessarily exhibit some combinatorial structure. An informal geometric statement of the theorem is that for any positive integers ''n'' and ''c'' there is a number ''H'' such that if the cells of a ''H''-dimensional ''n''×''n''×''n''×...×''n'' cube are colored with ''c'' colors, there must be one row, column, or certain diagonal (more details below) of length ''n'' all of whose cells are the same color. In other words, assuming ''n'' and ''c'' are fixed, the higher-dimensional, multi-player, ''n''-in-a-row generalization of a game of

tic-tac-toe Tic-tac-toe (American English), noughts and crosses (English in the Commonwealth of Nations, Commonwealth English), or Xs and Os (Canadian English, Canadian or Hiberno-English, Irish English) is a paper-and-pencil game for two players who ta ...

with ''c'' players cannot end in a draw, no matter how large ''n'' is, no matter how many people ''c'' are playing, and no matter which player plays each turn, provided only that it is played on a board of sufficiently high dimension ''H''. By a standard

strategy-stealing argument In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many two-player games, that the second player cannot have a guaranteed winning strategy. The strategy-stealing argument applies to any symmetric game ...

, one can thus conclude that if two players alternate, then the first player has a winning strategy when ''H'' is sufficiently large, though no practical algorithm for obtaining this strategy is known.

Formal statement

Let ''W'' be the set of words of length ''H'' over an alphabet with ''n'' letters; that is, the set of sequences of of length ''H''. This set forms the hypercube that is the subject of the theorem. A ''variable word'' ''w''(''x'') over ''W'' still has length ''H'' but includes the special element ''x'' in place of at least one of the letters. The words ''w''(1), ''w''(2), ..., ''w''(''n'') obtained by replacing all instances of the special element ''x'' with 1, 2, ..., ''n'', form a combinatorial line in the space ''W''; combinatorial lines correspond to rows, columns, and (some of the) diagonals of the

hypercube In geometry, a hypercube is an ''n''-dimensional analogue of a square ( ) and a cube ( ); the special case for is known as a ''tesseract''. It is a closed, compact, convex figure whose 1- skeleton consists of groups of opposite parallel l ...

. The Hales–Jewett theorem then states that for given positive integers ''n'' and ''c'', there exists a positive integer ''H'', depending on ''n'' and ''c'', such that for any partition of ''W'' into ''c'' parts, there is at least one part that contains an entire combinatorial line. For example, take ''n'' = 3, ''H'' = 2, and ''c'' = 2. The hypercube ''W'' in this case is just the standard

board, with nine positions: A typical combinatorial line would be the word 2x, which corresponds to the line 21, 22, 23; another combinatorial line is xx, which is the line 11, 22, 33. (Note that the line 13, 22, 31, while a valid line for the game

, is not considered a combinatorial line.) In this particular case, the Hales–Jewett theorem does not apply; it is possible to divide the

board into two sets, e.g. and , neither of which contain a combinatorial line (and would correspond to a draw in the game of

). On the other hand, if we increase ''H'' to, say, 8 (so that the board is now eight-dimensional, with 3⁸ = 6561 positions), and partition this board into two sets (the "noughts" and "crosses"), then one of the two sets must contain a combinatorial line (i.e. no draw is possible in this variant of

). For a proof, see below.

Proof of Hales–Jewett theorem (in a special case)

We now prove the Hales–Jewett theorem in the special case ''n'' = 3, ''c'' = 2, ''H'' = 8 discussed above. The idea is to reduce this task to that of proving simpler versions of the Hales–Jewett theorem (in this particular case, to the cases ''n'' = 2, ''c'' = 2, ''H'' = 2 and ''n'' = 2, ''c'' = 6, ''H'' = 6). One can prove the general case of the Hales–Jewett theorem by similar methods, using

mathematical induction Mathematical induction is a method for mathematical proof, proving that a statement P(n) is true for every natural number n, that is, that the infinitely many cases P(0), P(1), P(2), P(3), \dots all hold. This is done by first proving a ...

. Each element of the

''W'' is a string of eight numbers from 1 to 3, e.g. 13211321 is an element of the hypercube. We are assuming that this hypercube is completely filled with "noughts" and "crosses". We shall use a

proof by contradiction In logic, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition by showing that assuming the proposition to be false leads to a contradiction. Although it is quite freely used in mathematical pr ...

and assume that neither the set of noughts nor the set of crosses contains a combinatorial line. If we fix the first six elements of such a string and let the last two vary, we obtain an ordinary

board, for instance "132113??" gives such a board. For each such board "abcdef??", we consider the positions "abcdef11", "abcdef12", "abcdef22". Each of these must be filled with either a nought or a cross, so by the

pigeonhole principle In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, of three gloves, at least two must be right-handed or at least two must be l ...

two of them must be filled with the same symbol. Since any two of these positions are part of a combinatorial line, the third element of that line must be occupied by the opposite symbol (since we are assuming that no combinatorial line has all three elements filled with the same symbol). In other words, for each choice of "abcdef" (which can be thought of as an element of the six-dimensional hypercube ''W''), there are six (overlapping) possibilities: # abcdef11 and abcdef12 are noughts; abcdef13 is a cross. # abcdef11 and abcdef22 are noughts; abcdef33 is a cross. # abcdef12 and abcdef22 are noughts; abcdef32 is a cross. # abcdef11 and abcdef12 are crosses; abcdef13 is a nought. # abcdef11 and abcdef22 are crosses; abcdef33 is a nought. # abcdef12 and abcdef22 are crosses; abcdef32 is a nought. Thus we can partition the six-dimensional

''W'' into six classes, corresponding to each of the above six possibilities. (If an element abcdef obeys multiple possibilities, we can choose one arbitrarily, e.g. by choosing the highest one on the above list). Now consider the seven elements 111111, 111112, 111122, 111222, 112222, 122222, 222222 in ''W''. By the

, two of these elements must fall into the same class. Suppose for instance 111112 and 112222 fall into class (5), thus 11111211, 11111222, 11222211, 11222222 are crosses and 11111233, 11222233 are noughts. But now consider the position 11333233, which must be filled with either a cross or a nought. If it is filled with a cross, then the combinatorial line 11xxx2xx is filled entirely with crosses, contradicting our hypothesis. If instead it is filled with a nought, then the combinatorial line 11xxx233 is filled entirely with noughts, again contradicting our hypothesis. Similarly if any other two of the above seven elements of ''W'' fall into the same class. Since we have a contradiction in all cases, the original hypothesis must be false; thus there must exist at least one combinatorial line consisting entirely of noughts or entirely of crosses. The above

argument An argument is a series of sentences, statements, or propositions some of which are called premises and one is the conclusion. The purpose of an argument is to give reasons for one's conclusion via justification, explanation, and/or persu ...

was somewhat wasteful; in fact the same theorem holds for ''H'' = 4. If one extends the above argument to general values of ''n'' and ''c'', then ''H'' will grow very fast; even when ''c'' = 2 (which corresponds to two-player

) the ''H'' given by the above argument grows as fast as the

Ackermann function In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total function, total computable function that is not Primitive recursive function, primitive recursive. ...

. The first

primitive recursive In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop is fixed befor ...

bound is due to

Saharon Shelah Saharon Shelah (; , ; born July 3, 1945) is an Israeli mathematician. He is a professor of mathematics at the Hebrew University of Jerusalem and Rutgers University in New Jersey. Biography Shelah was born in Jerusalem on July 3, 1945. He is th ...

, and is still the best known bound in general for the ''Hales–Jewett number'' ''H'' = ''H''(''n'', ''c'').

Connections with other theorems

Observe that the above argument also gives the following corollary: if we let ''A'' be the set of all eight-digit numbers whose digits are all either 1, 2, 3 (thus ''A'' contains numbers such as 11333233), and we color ''A'' with two colors, then ''A'' contains at least one

arithmetic progression An arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference from any succeeding term to its preceding term remains constant throughout the sequence. The constant difference is called common difference of that ...

of length three, all of whose elements are the same color. This is simply because all of the combinatorial lines appearing in the above proof of the Hales–Jewett theorem, also form arithmetic progressions in

decimal notation The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers (''decimal fractions'') of the ...

. A more general formulation of this argument can be used to show that the Hales–Jewett theorem generalizes

van der Waerden's theorem Van der Waerden's theorem is a theorem in the branch of mathematics called Ramsey theory. Van der Waerden's theorem states that for any given positive integers ''r'' and ''k'', there is some number ''N'' such that if the integers are colored, eac ...

. Indeed the Hales–Jewett theorem is substantially a stronger theorem. Just as

has a stronger ''density version'' in

Szemerédi's theorem In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers ''A'' with positive natural density contains a ''k''- ...

, the Hales–Jewett theorem also has a density version. In this strengthened version of the Hales–Jewett theorem, instead of coloring the entire

''W'' into ''c'' colors, one is given an arbitrary subset ''A'' of the hypercube ''W'' with some given density 0 < δ < 1. The theorem states that if ''H'' is sufficiently large depending on ''n'' and δ, then the set ''A'' must necessarily contain an entire combinatorial line. The density Hales–Jewett theorem was originally proved by Furstenberg and Katznelson using

ergodic theory Ergodic theory is a branch of mathematics that studies statistical properties of deterministic dynamical systems; it is the study of ergodicity. In this context, "statistical properties" refers to properties which are expressed through the behav ...

. In 2009, the

Polymath Project The Polymath Project is a collaboration among mathematicians to solve important and difficult mathematical problems by coordinating many mathematicians to communicate with each other on finding the best route to the solution. The project began in J ...

developed a new proof of the density Hales–Jewett theorem based on ideas from the proof of the

corners theorem In arithmetic combinatorics, the corners theorem states that for every \varepsilon>0, for large enough N, any set of at least \varepsilon N^2 points in the N\times N grid \^2 contains a corner, i.e., a triple of points of the form \ with h\ne 0. I ...

. Dodos, Kanellopoulos, and Tyros gave a simplified version of the Polymath proof. The Hales–Jewett is generalized by the

Graham–Rothschild theorem In mathematics, the Graham–Rothschild theorem is a theorem that applies Ramsey theory to combinatorics on words and combinatorial cubes. It is named after Ronald Graham and Bruce Lee Rothschild, who published its proof in 1971. Through the work ...

, on higher-dimensional combinatorial cubes.

References

External links

Full proof of HJT
- begins on slide 57
Science News article on the collaborative proof of the density Hales-Jewett theoremA blog post by Steven Landsburg discussing how the proof of this theorem was improved collaboratively on a blogHigher-Dimensional Tic-Tac-Toe
, Infinite Series by

PBS The Public Broadcasting Service (PBS) is an American public broadcaster and non-commercial, free-to-air television network based in Arlington, Virginia. PBS is a publicly funded nonprofit organization and the most prominent provider of educat ...

{{DEFAULTSORT:Hales-Jewett theorem Ramsey theory Theorems in discrete mathematics Articles containing proofs Positional games