The reverse mathematics of Hindman’s Theorem for sums of exactly two elements

Abstract

Hindman’s Theorem (HT) states that for every coloring of $\mathbb{N}$ with finitely many colors, there is an infinite set $\mathit{H}\subseteq \mathbb{N}$ such that all nonempty sums of distinct elements of H have the same color. The investigation of restricted versions of HT from the computability-theoretic and reverse-mathematical perspectives has been a productive line of research recently. In particular, ${\mathrm{HT}}_{\mathit{k}}^{⩽\mathit{n}}$ is the restriction of HT to sums of at most n many elements, with at most k colors allowed, and ${\mathrm{HT}}_{\mathit{k}}^{=\mathit{n}}$ is the restriction of HT to sums of exactly n many elements and k colors. Even ${\mathrm{HT}}_2^{⩽2}$ appears to be a strong principle, and may even imply HT itself over RCA₀. In contrast, ${\mathrm{HT}}_2^{=2}$ is known to be strictly weaker than HT over RCA₀, since ${\mathrm{HT}}_2^{=2}$ follows immediately from Ramsey’s Theorem for 2-colorings of pairs. In fact, it was open for several years whether ${\mathrm{HT}}_2^{=2}$ is computably true.

We show that ${\mathrm{HT}}_2^{=2}$ and similar results with addition replaced by subtraction and other operations are not provable in RCA₀, or even WKL₀. In fact, we show that there is a computable instance of ${\mathrm{HT}}_2^{=2}$ such that all solutions can compute a function that is diagonally noncomputable relative to ${\varnothing }^{\prime }$ . It follows that there is a computable instance of ${\mathrm{HT}}_2^{=2}$ with no ${\mathrm{\Sigma }}_2^0$ solution, which is the best possible result with respect to the arithmetical hierarchy. Furthermore, a careful analysis of the proof of the result above about solutions DNC relative to ${\varnothing }^{\prime }$ shows that ${\mathrm{HT}}_2^{=2}$ implies ${\mathrm{RRT}}_2^2$ , the Rainbow Ramsey Theorem for colorings of pairs for which there are most two pairs with each color, over RCA₀. The most interesting aspect of our construction of computable colorings as above is the use of an effective version of the Lovász Local Lemma due to Rumyantsev and Shen.