A density version of the Hales-Jewett theorem

The theorem of van der Waerden on arithmetic progressions states that for given natural numbers \(r,k\) there is a constant \(K(r,k)\) so that for any partition of an arithmetic progression of length \(K\geq K(r,k)\) to \(r\) subsets, one of these contains an arithmetic progression of length \(k\). This result is the prototype of a Ramsey theorem whereby a certain kind of structure is reproduced in small scale when a large scale model is partitioned arbitrarily to a fixed number of subsets. Van der Waerden's theorem is a special case of a general combinatorial theorem proved by Hales and Jewett. To formulate their result we make some definitions. Let \(A\) denote a finite set \(\{a_ 1,a_ 2,\dots,a_ k\}\), and let \(W_ N(A)\) denote the words of length \(N\) with letters in \(A\), \(W_ N(A)=A^ N\). We think of the points of \(W_ N(A)\) as vectors in a ``combinatorial \(N\)-dimensional space. If \(A\) is a finite field, then \(W_ N(A)\) is indeed a vector space over \(A\). This example motivates the following definition of a ``line in \(W_ N(A)\): if \(k=\#(A)\) then \(k\) points \(\{w^ 1,w^ 2,\dots,w^ k\}\) in \(W_ N(A)\) constitute a combinatorial line if there is a partition \(\{1,2,\dots,N\}=I\cup J\), \(I\cap J=\varnothing\), \(J\neq\varnothing\) and writing \(w^ h=(w^ h_ 1,w^ h_ 2,\dots,w^ h_ N)\) we have \(w^ 1_ n=w^ 2_ n=\cdots=w^ k_ n\) for \(n\in I\), and \(w^ h_ n=a_ h\) for \(n\in J\). We can also describe \(\{w^ 1,w^ 2,\dots,w^ k\}\) as follows. Let \(x\) denote a variable and form words with the alphabet \(A\cup x\). Suppose \(w(x)\) is such a word in which the letter \(x\) occurs. Then \(w(1)\), \(w(2),\dots,w(k)\) form a combinatorial line. Note that if \(A\) is a finite field then a combinatorial line is a line in the geometric sense in the vector space \(A^ N\). Moreover if \(A=\{0,1,\dots,k-1\}\) and we interpret \(W_ N(A)\) as integers \(<k^ N\), then a combinatorial line forms an arithmetic progression. The Hales-Jewett theorem can now be formulated as follows: Theorem A. There is a function \(M(r,k)\) defined for \(r,k\in\mathbb{N}\), so that for \(\#(A)=k\) and \(N\geq M(r,k)\), if \(W_ N(A)=C_ 1\cup C_ 2\cup\cdots\cup C_ r\) is any partition of \(W_ N(A)\) into \(r\) subsets, one of these subsets contains a combinatorial line. Van der Waerden's theorem follows from Theorem A by setting \(K(r,k)=k^{M(r,k)}\). We take \(\{0,1,\dots,K-1\}\) as the typical arithmetic progression of length \(K\). Expressing numbers to the base \(k\) we can identify \(\{0,1,\dots,K(r,k)-1\}\) with \(W_{M(r,k)}(\{0,1,\dots,k-1\})\). Interpreting \(A\) as a finite field we also get the following theorem: Theorem B. There is a function \(N(r,q)\) defined for \(r\in\mathbb{N}\) and \(q\) a prime power, so that if \(F\) is a field with \(q\) elements and \(V\) is a vector space over \(F\) of dimension \(\geq N(r,q)\) and if \(V=C_ 1\cup C_ 2\cup\cdots C_ r\) is any partition of \(V\) into \(r\) sets, then one of these sets contains an affine line. Theorems A and B have multidimensional analogues. Theorem A also gives at once the multidimensional analogue of van der Waerden's theorem (proved by Grünbaum). Now both van der Waerden's theorem and Theorem B have density versions which are considerably more powerful theorems. In view of this it is natural to ask whether the ``master coloring theorem, Theorem A, has a density theoretic analogue. The purpose of this paper is to answer this affirmatively with the following result: Theorem E. There is a function \(R(\varepsilon,k)\) defined for \(\varepsilon>0\) and \(k\in\mathbb{N}\), so that if \(A\) is a set with \(k\) elements, \(W_ N(A)\) consists of words in \(A\) of length \(N\), and if \(N\geq R(\varepsilon,k)\), then any subset \(S\subset W_ N(A)\) with \(\#(S)\geq\varepsilon k^ N\) contains a combinatorial line. Theorem E implies Theorem A by setting \(M(r,k)=R\left({1\over r+1},k\right)\).

Recommendations

Cites work

Cited in

(only showing first 100 items - show all)

This page was built for publication: A density version of the Hales-Jewett theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1803633)