** Next:** Szemerédi's Theorem
** Up:** Ramsey Theory
** Previous:** Ramsey Theory

###

Hindman's Theorem

A famous and important Ramsey-type result is *Hindman's theorem*:

For any coloring of
with finitely many colors, there exists an
infinite set
such that all sums of finite subsets of
*H* have the same color.

Hindman's theorem is well known to be closely related to the
*Auslander/Ellis theorem* in topological dynamics:
For every state *x* in a compact dynamical system, there exists a
state *y* which is proximal to *x* and uniformly recurrent.

(A *compact dynamical system* consists of a compact metric space
*X* and a continuous function .
A state
is said to
be *uniformly recurrent* if for all
there exists *m*such that for all *n* there exists *k*<*m* such that
.
Two states
are said to be
*proximal* if for all
there exist infinitely many
*n* such that
.)
There has been a great deal of interest in the constructive or
effective aspect of Hindman's theorem and the Auslander/Ellis theorem.
Some of the known proofs are highly set-theoretical and cannot even be
formalized in second-order arithmetic. For an extensive discussion,
including several proofs of Hindman's theorem, see [12].

I conjecture that Hindman's theorem and the Auslander/Ellis theorem
are equivalent to
over
.
The known partial results in
this direction are in Blass/Hirst/Simpson [3]. There we showed
that Hindman's theorem and the Auslander/Ellis theorem are provable in
,
which consists of
plus ``for all
,
the th Turing jump
of *A* exists''. The proof
of Hindman's theorem in
involves a delicate effectivization
of Hindman's original proof. We also obtained a reversal by showing
that Hindman's theorem implies
over
.
The problem here
is to close the gap between
and
.

** Next:** Szemerédi's Theorem
** Up:** Ramsey Theory
** Previous:** Ramsey Theory
*Stephen G Simpson*

*1999-12-15*