Two New Extensions of the Hales-Jewett Theorem
Randall McCutcheon∗
Department of Mathematics
University of Maryland
College Park, MD 20742
randall@math.umd.edu
Submitted: June 30, 2000; Accepted: September 28, 2000
Abstract: We prove two extensions of the Hales-Jewett coloring theorem. The
first is a polynomial version of a finitary case of Furstenberg and Katznelson’s
multiparameter elaboration of a theorem, due to Carlson, about variable words.
The second is an “idempotent” version of a result of Carlson and Simpson.
MSC2000: Primary 05D10; Secondary 22A15.
For k, N ∈N,letWN
kdenote the set of length-Nwords on the alphabet {0,1,···,k−
1}.Avariable word over WN
kis a word w(x) of length Non the alphabet {0,1,···,k−
1,x}in which the letter xappears at least once. If w(x) is a variable word and
i∈{0,1,...,k−1},wedenotebyw(i) the word that is obtained by replacing each
occurrence of xin w(x)byani. The Hales-Jewett theorem states that for every
k, r ∈N, there exists N=N(k, r)∈Nsuch that for any partition WN
k=Sr
i=1 Ci,
there exist j,1≤j≤r, and a variable word w(x)overWN
ksuch that w(i):i∈
{0,1,...,k−1}⊂Cj.
1. Finitary extensions.
In [BL], V. Bergelson and A. Leibman provided a “polynomial” version of the Hales-
Jewett theorem. In order to formulate their result, we must develop some terminology.
Let l∈N.Aset-monomial (over Nl)inthevariableXis an expression m(X)=
S1×S2×···×Sl, where for each i,1≤i≤l,Siis either the symbol Xor a non-
empty singleton subset of N(these are called coordinate coefficients). The degree of
the monomial is the number of times the symbol Xappears in the list S1,···,S
l.
For example, taking l=3,m(X)={5}×X×Xis a set-monomial of degree 2,
while m(X)=X×{17}×{2}is a set-monomial of degree 1. A set-polynomial is an
expression of the form P(X)=m1(X)∪m2(X)∪ ···∪mk(X), where k∈Nand
m1(X),···,m
k(X) are set-monomials. The degree of a set-polynomial is the largest
degree of its set-monomial “summands”, and its constant term consists of the “sum” of
∗The author acknowledges support from the National Science Foundation via a
post doctoral fellowship administered by the University of Maryland.
the electronic journal of combinatorics
7
(2000),#R49 2
those mithat are constant, i.e. of degree zero. Finally, we say that two set polynomials
are disjoint if they share no set-monomial summands in common.
Let F(S) denote the family of non-empty finite subsets of a set S. Any non-
empty set polynomial p(A) determines a function from F(N)toF(Nl) in the obvious
way (interpreting the symbol ×as Cartesian product and the symbol ∪as union).
Notice that if P(X)andQ(X) are disjoint set-polynomials and B∈F(N) contains
no coordinate coefficients of either Por Qthen P(B)∩Q(B)=∅.
Here now is the Bergelson-Leibman coloring theorem.
Theorem 1.1. Let l∈Nand let Pbe a finite family of set-polynomials over Nl
whose constant terms are empty. Let I⊂Nbe any finite set and let r∈N.There
exists a finite set S⊂N,withS∩I=∅, such that if FSP∈P P(S)=Sr
i=1 Cithen
there exists i,1≤i≤r, some non-empty B⊂S,andsomeA⊂SP∈P P(S)with
A∩P(B)=∅for all P∈P and A∪P(B):P∈P
⊂Ci.
Although the “polynomial” nature of Theorem 1.1 is at once clear, it is not im-
mediately obvious that it includes the Hales-Jewett theorem as a special case, so we
shall give a different formulation, and derive it from Theorem 1.1.
Let k, N, d ∈N. WedenotebyMN
k(d) the set of all function φ:{1,2,...,N}d→
{0,1,...,k−1}.Whend= 2, one may identify this with the set of N×Nmatrices
with entries belonging to {0,1,...,k−1}, so in general we shall refer to the members
of MN
k(d) as matrices, even when d>2. A variable matrix over MN
k(d) is a function
ψ:{1,2,...,N}d→{0,1,...,k−1,x}for which xappears in the range. The support
of ψis the set ψ−1(x); that is, the set of locations in the matrix where the symbol x
appears. If ψis a variable matrix over MN
k(d), ψis said to be standard if its support
has the form Bdfor some B⊂{1,2,...,N}.
We shall also consider multi-variable matrices ψ:{1,2,...,N}d→{0,1,...,k−
1,x
1,x
2,...,x
t}. Inthiscasewerequirethatallthexiappear in the range, and we
call ψ−1(xi)theith support of ψ.Ifψis a t-variable matrix then ψgives rise, via
substitution, to a function w(x1,...,x
t):{0,...,k−1}→M
N
k(d), and we will often
refer to this induced winstead of to ψwhen dealing with variable matrices.
We require the following nonconventional notion of addition of matrices. We will
introduce this notion in the context of dimension 2, although the obvious analogs
are valid in arbitrary dimension. Let w=(wij )M
i,j=1 and y=(yij )M
i,j=1 be matri-
ces (variable or otherwise). If there exist disjoint sets Wand Y, whose union is
{1,...,M}2, such that wij =0for(i, j)∈Wand yij =0for(i, j)∈Y,thenwe
define w+y=(zij )M
i,j=1,wherezij =wij if (i, j)∈Yand zij =yij if (i, j)∈W.If
however there exists (i, j)∈{1,...,M}2such that wij 6=06=yij then the sum w+y
is undefined.
Theorem 1.2 The following are equivalent:
(a) Theorem 1.1.
(b) Let d∈Nand let Pi(X)t
i=1 be pairwise disjoint set-polynomials over Ndhaving
empty constant term and let Jbe any finite subset of Ncontaining all coordinate
the electronic journal of combinatorics
7
(2000),#R49 3
coefficients represented in the Pi’s. Let k, r ∈N. There exists N∈Nhaving the
property that if MN
k(d)=Sr
i=1 Cithen there exists a set B⊂{1,2,...,N}\J,a
variable matrix w(x1,...,x
t), and n,with1≤n≤r, such that
(i) The ith support of wiis Pi(B), 1 ≤i≤t,
(ii) {w(i1,...,i
t):ij∈{0,1,...,k−1},1≤j≤t}⊂Cn,and
(iii) wis 0 on Jd.
(c) Let k, r, d ∈N. There exists Nsuch that for every partition MN
k(d)=Sr
i=1 Ci
there is a standard variable matrix w(x)overMN
k(d) such that {w(i):i∈{0,1,...,k−
1}} lies in one cell Cj.
Proof. First we show (a) implies (b). Choose b∈Nwith 2b≥kand consider the set
P={
t
[
s=1 Es×Ps(X):Es⊂{1,...,b},1≤s≤t}.
Pis a finite family of set polynomials over Nd+1.LetI=J∪{1,...,b}and let
l=d+ 1. Now pick a finite subset S⊂Nas guaranteed by Theorem 1.1. Notice in
particular that S∩I=∅.PickN∈Nsuch that S∪I⊂{1,...,N}. Suppose that
MN
k(d)=Sr
i=1 Ci. Form a map π:F{1,...,b}×{1,...,N}d→M
N
k(d) as follows:
π(A)(a1,...,a
d)=minX
(j,a1,...,ad)∈A
2j−1,k−1.
Now put Di=π−1(Ci), 1 ≤i≤r.ThenFSP∈P P(S)⊂Sr
i=1 Diso there
exist B⊂Sand A⊂SP∈P P(S)withA∩P(B)=∅for all P∈P(in particular
A∩{1,...,b}×Pi(B)=∅,1≤i≤t) and such that for some z,1≤z≤r,
A∪
t
[
s=1 Es×Ps(B):Es⊂{1,...,b},1≤s≤t⊂Dz.
Define a variable matrix ψ=w(x1,...,x
t)overMN
k(d)by
1. ψ(a1,...,a
d)=xiif (a1,...,a
d)∈Pi(B), and
2. ψ(a1,...,a
d)=π(A)(a1,...,a
d) otherwise.
(Recall that the sets {Pi(B):1≤i≤t}are pairwise disjoint, owing to the fact that
the Pi’s are pairwise disjoint and Bcontains no coordinate coefficients of any Pi.)
The ith support of wis clearly Pi(B), 1 ≤i≤t.Nowforanyi1,...,i
t∈
{0,1,...,k−1}, we pick sets Es⊂{1,...b}such that Pn∈Es2n−1=is,1≤s≤t,
and note that
w(i1,...,i
t)=π(A)+
t
X
s=1
πEs×Ps(B)=πA∪
t
[
s=1 Es×Ps(B)∈Cz.
the electronic journal of combinatorics
7
(2000),#R49 4
Since J⊂I,S∩I=∅and A⊂SP∈P P(S), we have A∩{1,...,b}×Jd=∅,so
that wis zero on Jd.
This finishes the proof that (a) implies (b). Letting t= 1 and P1(X)=Xd,one
sees that (b) implies (c). Therefore all that remains is to show (c) implies (a).
Let {Q1,···,Q
t}be the family of all set-monomials that appear in any of the
set-polynomials of P, and write Qi(X)=S(i)
1×···×S(i)
d,whereeachS(i)
jis either a
singleton or the symbol X.Letk=2
tand put d=l.
Let Nbe as promised by (c) and choose y∈Nlarger than all coordinate coef-
ficients in question and larger than any member of I.SetS={y+1,...,y +N}.
Suppose now that FSP∈P P(S)=Sr
i=1 Ci.
Let Ybe the family of t-tuples of subsets of {1,...,N}d.WeidentifyYwith
MN
k(d)by
(A1,...,A
t)↔wif and only if w(i1,...,i
d)=
t
X
s=1
21As((i1,...,id)).
Our next task is to construct a map πsending Y(and thus, effectively, MN
k(d)) to
FSt
s=1 Qs(S)=FSP∈P P(S). First we define πfor t-tuples of sets, one of which
is a singleton and the rest of which are empty. Suppose then that iis fixed, Aj=∅
for i6=jand Ai={(a1,...,a
d)}. Recall that Qi(X)=S(i)
1×···S(i)
d,wheresome
of the S(i)
jare singletons and some are X.LetT={j:S(i)
j=X}. Suppose that
for all j∈{1,...,d}\T,aj=min
ai:i∈T. If this condition is not met, we
set π(A1,···,A
t)=∅. If the condition is met, put bj=S(i)
jif S(i)
jis a singleton
and bj=aj+yif S(i)
j=X,1≤j≤d, and set π(A1,...,A
t)={(b1,...,b
d)}.
We now extend πto the desired domain by requiring that π(A1∪B1,...,A
t∪Bt)=
π(A1,...,A
t)∪π(B1,...,B
t). (This extension is unique.)
We now confirm that πhas the following two properties. First, if C⊂{1,...,N},
then letting B=C+y={c+y:c∈C}, fixing iand putting Ai=Cdand
Aj=∅for all j6=i,π(A1,...,A
t)=Qi(B). Second, if Ai∩Bi=∅for all i,
π(A1,...,A
t)∩π(B1,...,B
t)=∅.
We now use the map πto draw back the partition. Namely, let Di=π−1(Ci),
1≤i≤r.ThenY=Sr
i=1 Di.ButYis identified with MN
k(d), so by (c) there exists
a standard variable matrix w(x)andsomez,1≤z≤r, such that W=w(i):i∈
{0,1,...,k−1}⊂Dz. (After the identification, of course.)
Let Cdbe the support of w(x). Let (A1,...,A
t)bethememberofYthat is
identified with w(0). Then Ai∩Cd=∅for 1 ≤i≤t,sothatπ(A1,...,A
t)∩
π(Cd,...,Cd)=∅.Moreover,inY,Wtakes the form
W=(A1,...,A
t)∪(F1,...,F
t): Fi∈{∅,Cd},1≤i≤t.
Let A=π(A1,...,A
t)and let B=C+y.LetP∈Pand choose a set E⊂{1,...,t}
such that P(X)=Si∈EQi(X). Next put Fj=Cdif j∈Eand Fj=∅otherwise.
Then (A1,...,A
t)∪(F1,...,F
t)∈W.Butπ(W)⊂Cz,soA∪Si∈EQi(Bd)∈Cz.
the electronic journal of combinatorics
7
(2000),#R49 5
Formulations (a) and (b) in Theorem 1.2 are more powerful, on the surface, than
formulation (c) and hence it is good to have them on hand for some applications, but
formulation (c) has aesthetic advantages. For one, when d= 1 it gives precisely the
Hales-Jewett theorem.
We now shift our focus slightly. Let Abe a finite field and let n∈N.ThenAnis
a vector space over A. A translate of a t-dimensional vector subspace of Anis called a
t-space. The following theorem was proved by Graham, Leeb and Rothschild ([GLR]).
Theorem 1.3 Let r, n, t ∈N. There exists N=N(r, n, t) such that for any r-coloring
of the n-spaces of ANthere exists a t-space Vsuch that the family of n-spaces contained
in Vis monochromatic.
We mention this result because it is so well known. It is not quite in keeping with
our theme, namely extensions of the Hales-Jewett theorem, but if we restrict attention
to a certain sub-class of n-spaces, the situation becomes much more “Hales-Jewett-
like”.
Recall that a variable word over Wkis a word on the alphabet {1,2,···,k,x}in
which the symbol xappears at least once. An n-variable word is a word on the alphabet
{1,···,k,x
1,···,x
n}in which all the xi’s occur and for which no occurrence of xi+1
precedes an occurrence of xi,1≤i≤n−1. If w(x1,···,x
n)isann-variable word over
WM
kthen the set {w(t1,t
2,···,t
n):1≤ti≤k, i =1,···,n}will be called the space
associated with w. (Notice now that if k=psfor some prime pand s∈Nand we
identify {0,1,...,k−1}with a field Ahaving pselements, choose a basis {v1,···,v
M}
for AMand identify the word w1w2···wMwith the vector PM
i=1 wivi, then the space
associated with an n-variable word is indeed an n-space in AN. However, not all
n-spaces can be obtained in this way.)
If wis a t-variable word and vis an n-variable word and the space associated
with vis contained in the space associated with w,vwill be called an n-subword of w.
Another way of seeing this is, if w(y1,···,y
t)isat-variable word then the n-variable
subwords of it (in the variables x1,···,x
n) are of the form w(z1,···,z
t), where z1···zt
is an n-variable word over Wk(t).
The following theorem is a finitary consequence of a generalization of T. Carlson’s
theorem ([C, Lemma 5.9]) due to H. Furstenberg and Y. Katznelson (see [FK, Theorem
3.1]). It extends the Hales-Jewett theorem in the following sense. If we call regular
words (that is, elements of WM
k) 0-variable words, then the Hales-Jewett theorem
corresponds to the case n=0,t= 1 of Theorem 1.4.
Theorem 1.4 Let k, r, n, t ∈Nbe given. There exists M=M(k, r, n, t) such that for
every r-cell partition of the n-variable words over WM
kthere exists a t-variable word
all of whose n-subwords lie in the same cell.
We seek now to give a polynomial analog of Theorem 1.4. To this end, let
k, N, d, n ∈Nand suppose we have non-empty sets Bi⊂{1,...,N},1≤i≤n,
