Set-polynomials and polynomial extension of the Hales-Jewett theorem

V. Bergelson and A. Leibman

Review from Zentralblatt MATH:

In this paper a generalization of the polynomial Hales-Jewett (PHJ) type extension of the polynomial van der Waerden theorem is proved. Its simplest variant says: If $r,d,q\in{\bbfN}$, then there exits $N(r,d,q)\in{\bbfN}$ such that, for any $r$-coloring of the set of subsets of $V=\{1,\dots,N\}^d\times \{1,\dots,q\}$, there exist a set $a\subset V$, and a non-empty set $\gamma\subseteq \{1,\dots,N\}$, such that $a\cap(\gamma^d\times \{1,\dots,q\})=\emptyset$, and the sets $a$, $a\cup(\gamma^d\times \{1\})$, $a\cup(\gamma^d\times \{2\})$, \dots, $a\cup(\gamma^d\times \{q\})$ are all of the same color.

The paper is divided into 9 main sections. The introduction (labeled as Section 0) is devoted to a discussion of the connections of the proved generalization of the previous related results and prepares the sole for developing the used set-polynomial machinery and the methods of topological dynamics. Here the set-polynomials are defined via the operations of union (i.e. addition) and Cartesian multiplication of finite sets. Thus set-polynomials are polynomials like expressions having finite sets as coefficients, e.g. as monomials $\gamma^d\times \{\ell\}$ of degree $d$. The dynamics is brought into play through an action $\cal{F}(W)$, where $W$ is a given set, on a topological set $X$ which is a mapping $T$ from $\cal{F}(W)$ into the set of continuous self-mappings of $X$, $a\to T^a$, satisfying that for any $a,b\in\cal{F}(W)$ with $a\cap b=\emptyset$ one has $T^{a\cup b}=T^aT^b$. PHJ can now be stated thus: Given $r,d,q\in{\bbfN}$, there exits $N(r,d,q)\in{\bbfN}$ such that, for $V=\{1,\dots,N\}^d\times \{1,\dots,q\}$ and for any $r$-coloring of $\cal{F}(V)$, there exist $a\subset V$ and a non-empty set $\gamma\subseteq \{1,\dots,N\}$ such that $a\cap(\gamma^d\times \{1,\dots,q\})=\emptyset$, and the sets $a$, $a\cup(\gamma^d\times \{1\})$, $a\cup(\gamma^d\times \{2\})$, \dots, $a\cup(\gamma^d\times \{q\})$ are all of the same color.

Section 1 demonstrates the method of proof of PHJ on the background of two special cases, the `linear' (i.e. $d=1$) variant of the Hales-Jewett theorem and the simplest non-trivial non-linear case of a topological variant of PHJ. In Section 2 basics of set-polynomials and their formalism are developed. In Section 3 the formalism of the previous section is further developed and used to reformulate the main result in the set-polynomial language: If $A$ is a system consisting of set-polynomials with empty constant term, then $A$ is a system of (chromatic) recurrence. This result is then proved in Section 6, while Sections 4 and 5 contain some necessary technical supporting results. Section 7 is devoted to some combinatorial results derived from PHJ, and corollaries pertaining to topological recurrence. The last section is devoted to the abstract polynomiality and brings some group-theoretical corollaries of PHJ.

Reviewed by Stefan Porubský

Keywords: van der Waerden theorem; geometric Ramsey theorem; set-polynomials; topological dynamics

Classification (MSC2000): 05D10 05E99 11B25 37B05 54H20

Full text of the article:

• PDF file (323 kilobytes)