Hindman theorem

Every finite coloring of the positive integers has an infinite sequence $(x_i)$ for which all nonempty finite sums of distinct terms have one color.

Extend a finite coloring of the positive integers to a point $x$ 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 $y$ proximal to $x$. Put $q=y(0)$. If all sums in $\{0\}\cup \mathrm{FS}(a_1,\dots ,a_r)$, the augmented finite-sums set, have color $q$ in $y$, their coordinate constraints define a cylinder set containing $y$. The joint return lemma for a proximal minimal pair chooses a new positive term so that all new sums have color $q$ in both $x$ and $y$. 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.

Choose an idempotent ultrafilter on the natural numbers $\mathcal{U}$ and a color class $A\in \mathcal{U}$. The setalso belongs to $\mathcal{U}$, and $A^{\ast }-x\in \mathcal{U}$ for every $x\in A^{\ast }$. Recursively choosing each new term from the finitely many required translates of $A^{\ast }$ puts every nonempty finite sum in $A$.

For a sequence $(x_i)$, its finite-sums set is

Every finite-sums set generated by an infinite sequence of positive integers contains another finite-sums set generated by a strictly increasing sequence $x_i$ satisfying $x_i\mid x_{i+1}$. Consequently the divisibility requirement can be added to the conclusion of Hindman theorem.

Choose each $x_i$ as a sum over a finite block of indices of the original sequence, with these index blocks disjoint and successive. Given $x_i=m$, take two fresh groups of $m$ terms. In either group the $m+1$ partial sums, including $0$, give two equal congruence classes modulo $m$ by the pigeonhole principle. Their difference is a nonempty consecutive sum divisible by $m$, and hence at least $m$. Add the two such sums to obtain $x_{i+1}\ge 2m$ divisible by $m$. Its index block is the union of the two selected subblocks. Discard the rest of these groups and continue after them. Because the blocks are disjoint, every finite sum of the $x_i$ is a finite sum of distinct original terms. This proves both the finite-sums set containment and the strictly increasing divisibility chain.

A subset $A$ of the positive integers is an IP set if it contains a finite-sums set generated by an infinite sequence of positive integers. Sums use distinct indices, although the generators themselves need not be distinct. An IP set is necessarily infinite, because its successive partial sums are unbounded. The partition regularity of IP sets is the relative form of the Hindman theorem needed when applying that theorem inside an already specified IP set.

Let $E$ be the union of integer intervals $[2^{2j},2^{2j+1})$ for $j\ge 0$. Every nonempty sum of distinct $4^j$ has largest summand $4^J$ and lies in $[4^J,2\cdot 4^J)$, since the sum of all smaller summands is $(4^J-1)/3$. Thus $\mathrm{FS}(4^j)\subseteq E$. Doubling gives $\mathrm{FS}(2\cdot 4^j)\subseteq E^c$. Both sides are IP sets. Each can be adjoined to the IP-star filter while preserving the finite intersection property, yielding two distinct IP ultrafilters.

An IP-star set meets every IP set. Equivalently, its complement is not an IP set: a disjoint IP set is precisely an IP subset of the complement. This is a condition on all infinite finite-sums sets, not merely on a single generating sequence.

The IP-star sets form a proper filter on a set over the positive integers. Indeed, sets that are not IP sets are closed under taking subsets. They are also closed under finite unions, because the partition regularity of IP sets would otherwise put an IP set in one of the union's constituent sets. Taking complements gives upward closure and closure under finite intersections for the IP-star sets. The full set belongs to this filter and the empty set does not.

Every finite coloring of an IP set has a color class that is an IP set. Here is a reduction to the ordinary Hindman theorem. Given $\mathrm{FS}(x_i)$ in the original set, color an integer $n>0$ by the color of ${\sum }_{i\in {\mathrm{supp}}_2(n)}{x}_i$, where the support consists of positions of its nonzero digits in the binary expansion. The Hindman theorem produces $w_i>0$ with monochromatic $\mathrm{FS}(w_i)$. Replace the $w_i$ by consecutive, disjoint finite block sums $v_j$ with separated binary supports: after a block has been chosen, take $K$ above all previously used positions; two of $2^K+1$ partial sums of a fresh tail agree modulo $2^K$, so their positive difference supplies the next block sum divisible by $2^K$. Now binary addition of distinct $v_j$ has no carries. Therefore $y_j={\sum }_{i\in {\mathrm{supp}}_2(v_j)}{x}_i$ generates a monochromatic finite-sums set in the original IP set.

The Milliken–Taylor theorem gives monochromatic systems of separated block sums with a fixed compressed coefficient vector, such as $(1,2,3)$. Systems associated with two nonproportional compressed coefficient vectors need not have the same color: in particular, there is a finite coloring for which a finite-sums set and the $(1,2,3)$ Milliken–Taylor system cannot be monochromatic together.