##
The Reverse Mathematics of Hindman's Theorem for Sums of
Exactly Two Elements

Status: published in *Computability* 8
(2019) 253 - 263

Availability: journal
version and preprint

**Abstract.** Hindman's Theorem (HT) states that for every coloring
of
ℕ
with finitely many colors, there is an infinite set *H* ⊆
ℕ 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,
HT^{≤n}_{k} is the restriction of HT to
sums of at most *n*
many elements, with at most *k* colors allowed, and HT^{=n}_{k} is the
restriction of HT to sums of *exactly* *n* many elements and *k*
colors. Even HT^{=2}_{2} appears to be a strong principle,
and may even imply HT itself over RCA_{0}. In
contrast, HT^{=2}_{2} is known to be strictly weaker than HT over
RCA_{0}, since HT^{=2}_{2} follows immediately from Ramsey's Theorem
for 2-colorings of pairs. In fact, it was open for several years
whether HT^{=2}_{2} is computably true.

We show that HT^{=2}_{2} and similar results with addition replaced by
subtraction and other operations are not provable in RCA_{0}, or even
WKL_{0}. In fact, we show that there is a computable instance of
HT^{=2}_{2} such that all solutions can compute a function that is
diagonally noncomputable relative to ∅'. It follows that
there is a computable instance of HT^{=2}_{2} with no Σ^{0}_{2}
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 ∅' shows
that HT^{=2}_{2} implies RRT^{2}_{2},
the Rainbow Ramsey Theorem for colorings of pairs for which there are are
most two pairs with each
color, over RCA_{0}. 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.

drh@math.uchicago.edu