Dynamical proof of Hindman's theorem 2026-10-05
Extend a finite coloring of the positive integers to a point of a two-sided full shift. A minimal subsystem of its forward orbit closure, together with the proximal-minimal existence theorem, supplies a minimal point proximal to . Put . If all sums in , the augmented finite-sums set, have color in , their coordinate constraints define a cylinder set containing . The joint return lemma for a proximal minimal pair chooses a new positive term so that all new sums have color in both and . Mathematical induction gives an infinite monochromatic finite-sums set. The new term can exceed the sum of all previous terms, giving unique representations. The proximal-minimal existence theorem is a substantive input to this proof.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 130 4 ii Solution Created 2026-10-03 Updated 2026-10-05
The dynamical proof of Hindman's theorem gives the following result. The Hindman theorem asserts that every finite coloring of the positive integers admits an infinite strictly increasing sequence for which all nonempty finite sums of distinct terms have one color. We will in fact arrange , so all these sums also have unique representations.
Extend the given coloring arbitrarily to a point , retaining the prescribed colors at every positive coordinate. Let be its forward orbit closure under the left shift. The product topology makes a compact metric space, and the left shift is a continuous map. There is a nonempty minimal subsystem : order the nonempty closed forward-invariant subsets by reverse inclusion, use compactness and the finite intersection property to intersect any chain, and apply the Zorn lemma. Minimality also implies . The result permitted in the question now supplies a minimal point proximal to .
We need the joint return lemma for a proximal minimal pair, which we prove here. It suffices to consider an open neighborhood of in . Choose an open neighborhood of with . Every forward orbit in meets , and a finite subcover of on supplies a bound on the needed return index. For a compatible metric , choose smaller than the distance from to when the latter is nonempty. By uniform continuity of the finitely many maps , , some ensuresProximality supplies arbitrarily large with . To see that the times can be large under the definition using an infimum over , either , in which case this is automatic, or injectivity of the left shift makes every finite collection of distances strictly positive, so a sufficiently smaller proximal distance occurs beyond that collection. Some has . Then also. Hence arbitrarily large positive satisfyThis uses the minimal point property for bounded returns and proximality for closeness; closeness alone would not guarantee a return near .
Put . Inductively, let , where denotes the finite-sums set, and maintainThe initial condition at is just ; no condition on is required. The cylinder set is a neighborhood of . Use the proved joint return lemma to choose with both and in . All new sums belong to , and the old sums remain in , so both inductive conditions persist. Every nonzero sum is positive, where agrees with the original coloring. ThereforeThis proves the Hindman theorem using only the permitted proximal-minimal existence result and the compactness and return arguments supplied above.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 130 4 i Solution Created 2026-10-03 Updated 2026-10-05
Use the product topology on , with discrete, and the left shift . A basic cylinder set specifies finitely many coordinates. This is a compact metric space, and is a homeomorphism. Write for the forward orbit closure. A minimal point means that is a minimal dynamical system, equivalently that every point of has a dense forward orbit in ; it need not be a fixed point.
There is a convention needed in the source: the bounded-gaps property concerns every finite integer interval , hence every finite word over an alphabet. Literally allowing would make the displayed condition impossible for finite , although a constant coloring is a minimal point. Under the standard finite-word interpretation, the property is precisely uniform recurrence.
Suppose first that is a minimal dynamical system. Its nonempty compact forward-invariant subset must equal . As the ambient left shift is invertible, all integer translates of belong to . Let have length , and let . This is a nonempty clopen set. Each forward orbit in meets , so covers . By compactness, finitely many suffice; let be the largest index in this finite cover. For any integer , the point lies in , so some satisfies . The prescribed word therefore occurs at positions , entirely inside . Taking proves the bounded-gaps property for every interval of length at least .
Conversely suppose is uniformly recurrent. Every finite word from any integer translate of occurs arbitrarily far to the right, so every such translate belongs to . Moreover, the property that every length- block contains a specified word of passes to every : a finite block of is a limit of blocks of forward translates of , and the finite discrete alphabet forces eventual exact agreement on that block. Given , look for its word inside . An occurrence starts at for some , so agrees with on . Taking for arbitrarily large proves that belongs to the forward orbit closure of every . That closure is a closed forward-invariant subset of , so it also contains every forward translate of and hence all of . Every forward orbit is therefore dense in , provingThe same conclusion holds if orbit closure is defined using all integer iterates: the bounded-gaps condition makes the forward and two-sided closures equal.
Uniform recurrence 2026-10-05
A two-sided sequence over a finite alphabet is uniformly recurrent if every finite word over an alphabet occurring in it occurs with bounded gaps. More precisely, for each such word some ensures that every length- interval contains a complete occurrence. This is equivalent to being a minimal point of the full shift: a finite cover of the orbit closure by preimages of a word's cylinder set bounds its return gaps; conversely, bounded gaps pass to all points of the orbit closure and make every forward orbit dense there. The property concerns finite words, not infinite integer intervals.