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 msuch 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 .
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 . 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 .