EMIS/ELibM Electronic Journals

Outdated Archival Version

These pages are not updated anymore. For the current production of this journal, please refer to http://www.jstor.org/journals/0003486x.html.

Annals of Mathematics, II. Series, Vol. 150, No. 1, pp. 33-75, 1999
EMIS ELibM Electronic Journals Annals of Mathematics, II. Series
Vol. 150, No. 1, pp. 33-75 (1999)

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home



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:

Electronic fulltext finalized on: 19 Aug 2001. This page was last modified: 21 Jan 2002.

© 2001 Johns Hopkins University Press
© 2001--2002 ELibM for the EMIS Electronic Edition
Metadata extracted from Zentralblatt MATH with kind permission