New bounds on the strength of some restrictions of Hindman’s Theorem

Abstract

The relations between (restrictions of) Hindman’s Finite Sums Theorem and (variants of) Ramsey’s Theorem give rise to long-standing open problems in combinatorics, computability theory and proof theory. We present some results motivated by these open problems. In particular we investigate the restriction of the Finite Sums Theorem to sums of at most two elements, which is the subject of a long-standing open question by Hindman, Leader and Strauss. We show that this restriction has the same proof-theoretic and computability-theoretic lower bound that is known to hold for the full version of the Finite Sums Theorem. In terms of reverse mathematics it implies ${ACA}_{0}$ . Also, we show that Hindman’s Theorem restricted to sums of exactly n elements is equivalent to ${ACA}_{0}$ for each $n ⩾ 3$ , provided a certain sparsity condition is imposed on the solution set. The same results apply to bounded versions of the Finite Union Theorem, in which such a sparsity condition is already built-in. Further we show that the Finite Sums Theorem for sums of at most two elements is tightly connected to the Increasing Polarized Ramsey’s Theorem for pairs introduced by Dzhafarov and Hirst. The latter reduces to the former in the technical sense known as strong computable reducibility.

Keywords

Reverse mathematics Hindman’s Theorem Finite Unions Theorem

1. Introduction and motivation

The Finite Sums Theorem by Neil Hindman [20] says that whenever the positive integers are coloured in finitely many colours there exists an infinite set of positive integers such that all the finite non-empty sums of distinct numbers from the set have the same colour. We denote this theorem by $HT$ and use ${HT}_{k}$ to stand for its restriction to k-colourings. Writing $FS (X)$ for the set of non-empty finite sums of distinct elements of the set X, the conclusion of Hindman’s Theorem is that there exists an infinite $X \subseteq N$ (where N denotes the set of positive integers throughout the paper) such that $FS (X)$ is monochromatic.

There are some interesting long-standing open problems related to $HT$ at the crossroads of combinatorics, proof theory and computability theory. The following question was asked by Hindman, Leader and Strauss in [21], and has been open since.

Question 12. Is there a proof that whenever N is finitely coloured there is a sequence $x_{1}, x_{2}, \dots$ such that all $x_{i}$ and all $x_{i} + x_{j}$ ( $i \neq j$ ) have the same colour, that does not also prove the Finite Sums Theorem?

It is very natural to recast the above question in the context of reverse mathematics, which is a framework for rigorously comparing the relative strength of theorems from all areas of mathematics over a fixed base theory (see [22,31] for excellent introductions to the topic). Traditionally such a base theory is the formal axiomatic system

{RCA}_{0}

(

{RCA}_{0}

is an acronym for Recursive Comprehension Axiom) capturing the intuitive idea of computable mathematics. Denoting by

{HT}^{⩽ n}

the restriction of

HT

to (non-empty) sums of at most n distinct elements, and by

{HT}_{k}^{⩽ n}

the further restriction to k-colourings, a good formal rendering of Question 12 reads as follows: Is

{HT}^{⩽ 2}

enough to prove

HT

over

{RCA}_{0}

Pinning down the exact strength of Hindman’s Theorem is by itself one of the major open problems in reverse mathematics (see [26, Question 9]). The seminal results of Blass, Hirst and Simpson in the late 1980’s leave indeed a huge gap between the lower and upper bound. In terms of reverse mathematics these results place Hindman’s Theorem no lower than the system ${ACA}_{0}$ (Arithmetical Comprehension Axiom) and no higher than the much stronger system ${ACA}_{0}^{+}$ . The system ${ACA}_{0}$ is equivalent to asserting that the Turing Jump of any set exists, and the system ${ACA}_{0}^{+}$ extends ${ACA}_{0}$ by the axiom stating that the ω-th Turing jump is always defined. ${ACA}_{0}$ is known to be equivalent to ${RT}_{2}^{3}$ (Ramsey’s Theorem for 2-colorings of triples) by the seminal work of Jockusch and of Simpson ([31, Theorem III.7.6] or [22, Chapter 6]), so we have that $HT$ implies ${RT}_{2}^{3}$ over ${RCA}_{0}$ . On the other hand ${ACA}_{0}^{+}$ was only recently given a Ramsey-theoretic characterization in work of the first and fourth author, who showed [9] that the system ${ACA}_{0}^{+}$ is equivalent to a Ramsey-theoretic theorem due to Pudlák and Rödl [30] and Farmaki and Negrepontis [16], which we denote by ${RT}_{2}^{! ω}$ (see Definition 5.7). This theorem extends Ramsey’s Theorem to colourings of objects of variable dimension, in particular to so-called exactly large sets of positive integers, where a set is exactly large in case its cardinality is greater by one than its minimum element. The following inequalities summarize the situation with respect to implications over the base theory ${RCA}_{0}$ : $\begin{matrix} {RT}_{2}^{! ω} \to HT \to {RT}_{2}^{3}, \end{matrix}$ where at least one of the two implications does not reverse, because it is known that ${RT}_{2}^{3} ↛ {RT}_{2}^{! ω}$ (in fact, $\forall n \forall k {RT}_{k}^{n} ↛ {RT}_{2}^{! ω}$ ).

By a “solution to Hindman’s Theorem for a finite coloring c” we mean an infinite set $H \subseteq N$ such that all finite non-empty sums of distinct elements from H have the same c-color. In terms of computability theory, the Blass–Hirst–Simpson bounds on $HT$ can then be expressed as follows. On the one hand, there exists a computable coloring $c : N \to 2$ such that any solution to Hindman’s Theorem for the coloring c computes $\emptyset^{'}$ , the first Turing Jump of the computable sets. On the other hand, for every computable coloring $c : N \to 2$ there exists a solution computable from $\emptyset^{(ω + 1)}$ , the $(ω + 1)$ -th Turing Jump of the computable sets.

In [3] Blass advocated the study of restrictions of Hindman’s Theorem to sums of bounded length (i.e., number of terms), conjecturing that the strength of $HT$ grows with the length of the sums for which monochromaticity is required. Only recently Dzhafarov, Jockusch, Solomon and Westrick [12] proved that the restriction of $HT$ to sums of at most 3 terms from the solution set, ${HT}^{⩽ 3}$ , already implies ${ACA}_{0}$ , matching the only known lower bound for $HT$ (in particular, ${HT}_{3}^{⩽ 3}$ suffices).

One of our main results is that the same lower bound already holds for the restriction to sums of at most 2 elements, ${HT}^{⩽ 2}$ , i.e., the restriction of $HT$ considered in [21, Question 12]. This means that the known upper and lower bounds for $HT$ and ${HT}^{⩽ 2}$ are now the same, which might be read as indicating that the restriction of $HT$ to sums of at most two terms might be close in strength to the full theorem.

On the other hand, we prove that the same lower bound holds for a number of restricted forms of $HT$ for which a matching upper bound can also be proved. The first examples of principles with this property, at the level of ${ACA}_{0}$ , were found in [7] and therein called “weak yet strong” principles. We improve and expand on [7] by showing, for example, that Hindman’s Theorem for sums of exactly n elements is equivalent to ${ACA}_{0}$ , provided that $n ⩾ 3$ and a certain sparsity condition is imposed on the solution set. Such a condition, which we call, following [7], the apartness condition, is crucial yet was not given a name in earlier work [4,12,19]. In our setting it means that the sets of exponents in some fixed base of the elements of the homogeneous set do not intertwine. An analogous condition is built-in in the formulation of Hindman’s Theorem in terms of finite unions (the Finite Unions Theorem), and called the unmeshedness condition [3] or the block sequence condition [1]. We will observe that bounded versions of the Finite Unions Theorem are equivalent to bounded versions of the Finite Sums Theorem with the apartness condition.

Note that, in contrast to ${HT}_{k}^{⩽ n}$ , the exact versions of Hindman’s Theorem – which we denote by ${HT}_{k}^{= n}$ when we consider sums of exactly n distinct terms and k-colorings – are easily seen to follow from ${RT}_{k}^{n}$ : given a colouring $f : N \to k$ , let $c : {[N]}^{n} \to k$ be defined by setting $c (a_{1}, \dots, a_{n}) = f (a_{1} + \dots + a_{n})$ . A solution $H \subseteq N$ to ${RT}_{k}^{n}$ for the instance c (i.e., an infinite homogeneous set X) is a solution to ${HT}_{k}^{= n}$ for instance f; i.e. all sums of exactly n distinct terms from H have the same color. We will prove, for example, that ${RT}_{2}^{3}$ already follows from (and is actually equivalent to) ${HT}_{2}^{= 3}$ with the apartness condition imposed on the solution set.

The argument just given is an example of a particularly simple and natural combinatorial reduction of the principle ${HT}_{k}^{= n}$ to ${RT}_{k}^{n}$ : Starting from an instance f of ${HT}_{k}^{= n}$ we defined an instance c of ${RT}_{k}^{n}$ . From a solution X to c we recovered a solution $X^{'}$ to the original instance of ${HT}_{k}^{= n}$ (in that case $X^{'}$ equals X). Proofs of this kind are abundant in combinatorics. Furthermore observe that in the above example c is easily seen to be computable relative to f and similarly $X^{'}$ is computable relative to X (this is obvious since $X = X^{'}$ in the example at hand). Such a proof that ${RT}_{k}^{n}$ follows from ${HT}_{k}^{= n}$ is an instance of what is known in the literature as a strong computable reduction. This notion, first defined in [13], has quickly become central in the computable and reverse mathematics literature (see, e.g., [14] and references therein). We use the notation $Q ⩽_{sc} P$ to indicate that a Ramsey-type theorem $Q$ is reducible to another Ramsey-type theorem $P$ by a strong computable reduction. Not all proofs of an implication over ${RCA}_{0}$ have the form of a strong computable reduction. For example, it has been recently proved [28] that there is no strong computable reduction from ${RT}_{3}^{n}$ to ${RT}_{2}^{n}$ , despite the fact that a straightforward combinatorial argument exists and that the two theorems are equivalent over ${RCA}_{0}$ . In the present paper, however, we only deal with positive results. For instance, we prove that an interesting restriction of Ramsey’s Theorem for pairs (the Increasing Polarized Ramsey’s Theorem of Dzhafarov and Hirst’s [15], denoted ${IPT}_{2}^{2}$ ) is strongly computably reducible to ${HT}_{4}^{⩽ 2}$ (in fact to ${HT}_{2}^{= 2}$ with the apartness condition imposed on the solution set).

The paper is organized as follows. In Section 2 we define the apartness condition and prove a simple lemma about it, and discuss the equivalence of the bounded versions of the Finite Unions Theorem with bounded versions of the Finite Sums Theorem with apartness. In Section 3 we prove ${ACA}_{0}$ lower bounds for restrictions of Hindman’s Theorem, including our main result that ${HT}^{⩽ 2}$ implies ${ACA}_{0}$ over ${RCA}_{0}$ . In Section 4 we deal with reductions between Hindman’s Theorem and the Increasing Polarized Ramsey’s Theorem. In Section 5 we present a number of other results that can be obtained by the arguments of the previous sections. In Section 6 we summarize our results and discuss some open problems.

2. Hindman’s Theorem, apartness, and finite unions

We define two natural types of restrictions of Hindman’s Theorem based on bounding the length of sums for which homogeneity is guaranteed. For $X \subseteq N$ and $n \in N$ we denote by ${FS}^{⩽ n} (X)$ the set of non-empty sums of at most n many distinct elements of X and by ${FS}^{= n} (X)$ the set of sums of exactly n many distinct elements of X.

Definition 2.1 (Hindman’s Theorem with bounded-length sums).

Fix $n, k ⩾ 1$ .

${HT}_{k}^{⩽ n}$ is the following principle: For every coloring $f : N \to k$ there exists an infinite set $H \subseteq N$ such that ${FS}^{⩽ n} (H)$ is monochromatic for f.

${HT}_{k}^{= n}$ is the following principle: For every coloring $f : N \to k$ there exists an infinite set $H \subseteq N$ such that ${FS}^{= n} (H)$ is monochromatic for f.

The principles ${HT}_{k}^{⩽ n}$ were discussed in [3] (albeit phrased in terms of finite unions instead of sums) and first studied from the perspective of Computable and Reverse Mathematics in [12], where the principles ${HT}_{k}^{= n}$ were also defined.

As indicated above, some of our results highlight the crucial role of a property of the solution set – the so-called apartness condition – that is central in Hindman’s original proof and in the proofs of the lower bounds in [4,7,12].

We use the following notation: Fix a base $t ⩾ 2$ . For $n \in N$ we denote by $λ_{t} (n)$ the least exponent of n written in base t, by $μ_{t} (n)$ the greatest exponent of n written in base t. We will drop the subscript when clear from context.

Definition 2.2 (Apartness Condition).

Fix $t ⩾ 2$ . We say that a set $X \subseteq N$ satisfies the t-apartness condition (or is t-apart) if for all $x, x^{'} \in X$ , if $x < x^{'}$ then $μ_{t} (x) < λ_{t} (x^{'})$ .

Note that t-apartness is inherited by subsets.

For a Hindman-type principle $P$ , let “ $P$ with t-apartness” denote the corresponding version in which the solution set is required to satisfy the t-apartness condition. As will be observed below, it is significantly easier to prove lower bounds on $P$ with t-apartness than on $P$ in all the cases we consider. In Hindman’s original paper it is shown [20, Lemma 2.2] how 2-apartness can be ensured by a simple counting argument (proved in [19, Lemma 2.2]) under the assumption that we have a solution to the Finite Sums Theorem, i.e., an infinite H such that $FS (H)$ is monochromatic. In our terminology, we have that, for each $k \in N$ , ${HT}_{k}$ is equivalent to ${HT}_{k}$ with 2-apartness. Note that the counting argument used by Hindman [19, Lemma 2.2] requires very elementary arithmetic assumptions, and that the set satisfying t-apartness is obtained from a general solution to $HT$ by an algorithmic thinning out procedure (as observed already in [4]). In other words, $HT$ and $HT$ with t-apartness are equivalent over ${RCA}_{0}$ .

Proposition 2.3 (Implicit in [19]).

For each positive integers t and k, ${HT}_{k}$ and ${HT}_{k}$ with t-apartness are equivalent over ${RCA}_{0}$ . The equivalence is witnessed by strong computable reductions.

Note that, to show the implication from ${HT}_{k}$ to ${HT}_{k}$ with t-apartness it is crucial that we start with a homogeneous set H such that all finite sums of distinct elements from H have the same colour. Putting a bound on the length of the sums would disrupt the argument. Thus, for bounded versions of $HT$ , the situation might be different. However, in typical situations, the choice of t in t-apartness does not matter. We prove below that ${HT}_{k}^{⩽ n}$ with t-apartness and ${HT}_{k}^{= n}$ with t-apartness are robust concepts and that it is sufficient to consider the case of $t = 2$ . To show this in detail we make a detour through another popular formulation of Hindman’s Theorem in terms of colorings of finite subsets of the natural numbers (see, e.g., [2]). This version is called the Finite Union Theorem. Let $P_{fin} (X)$ denote the set of finite subsets of X. If ${(X_{i})}_{i \in N}$ is a sequence of finite subsets of N, we denote by $FU ({(X_{i})}_{i \in N})$ the set of all finite unions of elements of ${(X_{i})}_{i \in N}$ , i.e., $FU ({(X_{i})}_{i \in N}) = {⋃_{t \in F} X_{t} : F a non-empty finite subset of N}$ .

Definition 2.4 (Finite Unions Theorem).

${FUT}_{k}$ : For every $f : P_{fin} (N) \to k$ there exists an infinite sequence ${(X_{i})}_{i \in N}$ of finite subsets of N such that if $i < j$ then $max (X_{i}) < min (X_{j})$ and such that $FU ({(X_{i})}_{i \in N})$ is monochromatic. $FUT$ denotes $\forall k {FUT}_{k}$ .

A sequence ${(X_{i})}_{i \in N}$ of finite subsets of N is called unmeshed or a block sequence if it satisfies the condition that for each $i < j$ then $max (X_{i}) < min (X_{j})$ . This condition is obviously akin to apartness and is part of the very statement of the Finite Unions Theorem. If this requirement is dropped, then the theorem becomes equivalent to the Infinite Pigeonhole Principle $\forall k {RT}_{k}^{1}$ as proved by Hirst in [23].

The equivalence of $HT$ with $FUT$ is well-known (see, e.g., [2]) and an inspection of the proof shows that it is witnessed by strong computable reductions. Below we verify that the equivalence still holds between ${FUT}_{k}^{⩽ n}$ (resp. ${FUT}_{k}^{= n}$ ) and ${HT}_{k}^{⩽ n}$ with t-apartness (resp. ${HT}_{k}^{= n}$ with t-apartness), for any t, where ${FUT}_{k}^{⩽ n}$ and ${FUT}_{k}^{= n}$ have the obvious meanings.

This shows that the principles ${HT}_{k}^{⩽ n}$ with 2-apartness can be considered as fully natural bounded restrictions of $HT$ . Thus, we will only need to consider 2-apartness in what follows, despite our use of 3-apartness in Lemma 2.7.

Proposition 2.5.
For each $n, k, t ⩾ 2$ , ${HT}_{k}^{⩽ n}$ with t-apartness is equivalent to ${FUT}_{k}^{⩽ n}$ over ${RCA}_{0}$ . Moreover, these principles are mutually strongly computably reducible. The same equivalences hold for ${HT}_{k}^{= n}$ with t-apartness and ${FUT}_{k}^{= n}$ .
Proof.
We give the proof for ${FUT}_{k}^{⩽ n}$ and ${HT}_{k}^{⩽ n}$ with t-apartness. For ${FUT}_{k}^{= n}$ and ${HT}_{k}^{= n}$ with t-apartness the argument is exactly analogous.

Let $c : P_{fin} (N) \to k$ . Define $d : N \to k$ as follows: let $m \in N$ . If $λ_{t} (m) = 0$ then d colors m arbitrarily. Otherwise, d colors m as c colors the set of its base t exponents. By ${HT}_{k}^{⩽ n}$ with t-apartness let $H = {h_{1}, h_{2}, \dots}$ (in increasing order) be a t-apart infinite set of positive integers such that ${FS}^{⩽ n} (H)$ is monochromatic for d. Since H is t-apart we can assume without loss of generality that for no $h \in H$ we have $λ_{t} (h) = 0$ . For each $i \in N$ let $S_{i} \subseteq N$ be the set of base t exponents of $h_{i}$ . Then ${(S_{i})}_{i \in N}$ is a block sequence in $P_{fin} (N)$ such that c is constant on ${FU}^{⩽ n} ({(S_{i})}_{i \in N})$ .

Let $d : N \to k$ . Define $c : P_{fin} (N) \to k$ as follows: c colors $S \in P_{fin} (N)$ as d colors $t^{s_{1}} + \dots + t^{s_{p}}$ where $S = {s_{1} < \dots < s_{p}}$ . The values of d on other elements of N are irrelevant. Let ${(S_{i})}_{i \in N}$ be a block sequence such that ${FU}^{⩽ n} ({(S_{i})}_{i \in N})$ is monochromatic for c. Let $S_{i} = {s_{i, 1} < \dots < s_{i, p_{i}}}$ . Then ${x_{i} : x_{i} = t^{s_{i, 1}} + \dots + t^{s_{i, p_{i}}}, i \in N}$ is a t-apart solution to ${HT}_{k}^{⩽ n}$ for d. □
Corollary 2.6.
Over ${RCA}_{0}$ , ${HT}_{k}^{⩽ n}$ with t-apartness (resp. ${HT}_{k}^{= n}$ with t-apartness) is equivalent to ${HT}_{k}^{⩽ n}$ with s-apartness (resp. ${HT}_{k}^{= n}$ with s-apartness), for any $t, s ⩾ 2$ .

Henceforth we will use just apartness for 2-apartness. Note that, in what follows, all the results for ${HT}_{k}^{⩽ n}$ with apartness (resp. ${HT}_{k}^{= n}$ with apartness) also hold in the case of ${FUT}_{k}^{⩽ n}$ (resp., for ${FUT}_{k}^{= n}$ ).

In some cases it is easy to show that the apartness condition can be enforced at no cost. For example the proof of ${HT}_{k}^{= n}$ from ${RT}_{k}^{n}$ sketched above yields t-apartness for any $t > 1$ simply by applying Ramsey’s Theorem relative to an infinite t-apart set. In some other cases the apartness condition can be ensured at the cost of increasing the number of colours. This is the case of ${HT}_{k}^{⩽ n}$ , as illustrated by the next lemma. The idea of the proof is from the first part of the proof of [12, Theorem 3.1], with some needed adjustments. Lemma 2.7 ( ${RCA}_{0}$ ).

For all $n ⩾ 2$ , for all $k ⩾ 1$ , ${HT}_{2 k}^{⩽ n}$ implies ${HT}_{k}^{⩽ n}$ with apartness. Furthermore, the implication is established by a strong computable reduction.

Proof.
We work in base 3 (this is without loss of generality by Corollary 2.6). Let $f : N \to k$ be given. For $m > 0$ let $i (m)$ denote the coefficient of the least term of m written in base 3. Define $g : N \to 2 k$ as follows: $\begin{matrix} g (m) : = \{\begin{matrix} f (m) & if i (m) = 1, \\ k + f (m) & if i (m) = 2 . \end{matrix} \end{matrix}$ Let H be an infinite set of positive integers such that ${FS}^{⩽ n} (H)$ is monochromatic for g of colour ℓ. For $h, h^{'} \in {FS}^{⩽ n} (H)$ we have $i (h) = i (h^{'})$ .

We claim that for each $j ⩾ 0$ there is at most one $h \in H$ such that $λ_{3} (h) = j$ . By way of contradiction suppose otherwise, as witnessed by $h, h^{'} \in H$ . Then $i (h) = i (h^{'})$ and $λ_{3} (h) = λ_{3} (h^{'})$ . Therefore $i (h + h^{'}) = 3 - i (h) \neq i (h)$ , but $h + h^{'} \in {FS}^{⩽ n} (H)$ . Contradiction.

Using the claim, we can computably obtain a 3-apart infinite subset $H^{'}$ of H. □

3. Bounded Hindman vs. arithmetical comprehension

In this section we first show that ${HT}^{⩽ 2}$ implies ${ACA}_{0}$ (hence ${RT}_{2}^{3}$ ) over ${RCA}_{0}$ . This improves on the main result of [12] that ${HT}^{⩽ 3}$ implies ${ACA}_{0}$ . In particular we show that ${HT}_{4}^{⩽ 2}$ implies ${ACA}_{0}$ . In terms of finite unions our proof shows that ${FUT}_{2}^{⩽ 2}$ implies ${ACA}_{0}$ . This should also be compared with Corollary 2.3 and Corollary 3.4 in [12] which show that ${HT}_{2}^{⩽ 2}$ implies the Stable Ramsey’s Theorem ${SRT}_{2}^{2}$ over the slightly stronger base theory ${RCA}_{0} + B Σ_{2}^{0}$ or, equivalently, ${RCA}_{0} + \forall k {RT}_{k}^{1}$ . Then we go on to prove that ${HT}_{2}^{= 3}$ with apartness is equivalent to ${ACA}_{0}$ . In terms of finite unions this shows that ${FUT}_{2}^{= 3}$ is equivalent to ${ACA}_{0}$ . Note that while ${HT}_{2}^{= 3}$ with apartness is easily reducible to ${RT}_{2}^{3}$ , it is unknown whether ${ACA}_{0}$ (and thus ${RT}_{2}^{3}$ ) implies ${HT}_{2}^{⩽ 2}$ over ${RCA}_{0}$ .

The lower bound proofs below are based on a significant simplification of the original argument of Blass, Hirst and Simpson [4]. Towards the end of [3] Blass states without giving details that inspection of the proof of the lower bound for $HT$ in [4] shows that this bound also holds for the restriction of the Finite Unions Theorem to unions of at most two sets. While our Proposition 3.1 confirms this conclusion, we would like to stress that from an inspection of the proof in [4] one can glean that sums of 3 elements are sufficient, as later proved in [12]. Indeed, while apparently only sums of 2 terms are used, in one crucial step one of the summands is itself a sum of length 2.

3.1. Sums of at most two terms

Let us recall that in ${RCA}_{0}$ we have that for every n there exists some ℓ such that for each $x < n$ , $x \in rg (f)$ if and only if $x \in rg (f ↾ ℓ)$ . This is a special case of a general principle known as strong $Σ_{1}^{0}$ -collection (or strong $Σ_{1}^{0}$ -bounding, see [31, Exercise II.3.14], [18, Thm I.2.23 and Definition I.2.20]). This simple fact will be used in our lower bound arguments below.

Proposition 3.1.
${HT}_{2}^{⩽ 2}$ with apartness (eq. ${FUT}_{2}^{⩽ 2}$ ) implies ${ACA}_{0}$ over ${RCA}_{0}$ .
Proof.
Assume ${HT}_{2}^{⩽ 2}$ with apartness and consider an injective function $f : N \to N$ . We have to prove that the range of f exists (this is well-known to be equivalent to proving ${ACA}_{0}$ , see [31, Lemma III.1.3 and Theorem III.7.6]).

For a positive integer n, written as $2^{n_{0}} + \dots + 2^{n_{r}}$ in base 2 notation, we call $j \in {0, \dots, r}$ important in n if some value of $f ↾ [n_{j - 1}, n_{j})$ is below $n_{0}$ . Here $n_{- 1} : = 0$ . The colouring $g : N \to 2$ is defined as follows: $\begin{matrix} g (n) : = card {j : j is important in n} mod 2 . \end{matrix}$ Note that g is computable relative to f. By ${HT}_{2}^{⩽ 2}$ with apartness, there exists an infinite set $H \subseteq N$ such that H is apart and ${FS}^{⩽ 2} (H)$ is monochromatic w.r.t. g. We claim that for each $n \in H$ and each $x < λ (n)$ , $x \in rg (f)$ if and only if $x \in rg (f ↾ μ (n))$ . This will give us an algorithm for deciding whether any given x is in the range of f: find the smallest $n \in H$ such that $x < λ (n)$ and check whether x is in $rg (f ↾ μ (n))$ .

It remains to prove the claim. In order to do this, consider $n \in H$ and assume that there is some element below $n_{0} = λ (n)$ in $rg (f) ∖ rg (f ↾ μ (n))$ .

Let ℓ be such that for each $x < λ (n)$ , $x \in rg (f)$ if and only if $x \in rg (f ↾ ℓ)$ . By apartness, and the fact that H is infinite, there is $m \in H$ with $λ (m) ⩾ ℓ > μ (n)$ . Write $n + m$ in base 2 notation, $\begin{matrix} n + m = 2^{n_{0}} + \dots + 2^{n_{r}} + 2^{n_{r + 1}} + \dots + 2^{n_{s}}, \end{matrix}$ where $n_{0} = λ (n) = λ (n + m)$ , $n_{r} = μ (n)$ , and $n_{r + 1} = λ (m)$ . Clearly, $j ⩽ s$ is important in $n + m$ if and only if either (i) $j ⩽ r$ and j is important in n or (ii) $j = r + 1$ ; hence, $g (n) \neq g (n + m)$ . This contradicts the assumption that ${FS}^{⩽ 2} (H)$ is monochromatic, thus proving the claim. □
Theorem 3.2.
${HT}_{4}^{⩽ 2}$ implies ${ACA}_{0}$ over ${RCA}_{0}$ .
Proof.
By Proposition 3.1, Lemma 2.7 and Corollary 2.6. □

3.2. Sums of exactly three terms, with apartness

We next extend the argument in Proposition 3.1 to show that ${HT}_{2}^{= 3}$ with apartness implies ${ACA}_{0}$ (hence ${RT}_{2}^{3}$ ) over ${RCA}_{0}$ . Since ${HT}_{2}^{= 3}$ with apartness is also easily deducible from ${RT}_{2}^{3}$ , we obtain an equivalence.

Theorem 3.3.
${HT}_{2}^{= 3}$ with apartness (eq., ${FUT}_{2}^{= 3}$ ) is equivalent to ${ACA}_{0}$ over ${RCA}_{0}$ .
Proof.
The upper bound, that is the implication from ${RT}_{2}^{3}$ to ${HT}_{2}^{= 3}$ with apartness, follows by applying the argument proving ${HT}_{k}^{= n}$ from ${RT}_{k}^{n}$ sketched in Section 1. Thus, it remains to prove the lower bound.

We argue in the base theory ${RCA}_{0}$ assuming ${HT}_{2}^{= 3}$ with apartness. Consider an injective function $f : N \to N$ . We have to prove that the range of f exists. The relation j is important in n and the colouring $g : N \to 2$ are defined as in the proof of Proposition 3.1.

By ${HT}_{2}^{= 3}$ with apartness, there exists an infinite set H such that H is apart and ${FS}^{= 3} (H)$ is monochromatic w.r.t. g. Let $r < 2$ be the colour of ${FS}^{= 3} (H)$ under g. We describe a method for algorithmically deciding membership in the range of f relative to the set H. Claim 1.
For each $n, k \in H$ , if $n < k$ and $g (n + k) = r$ then for each $x < λ (n)$ , $\begin{matrix} x \in rg (f) ⟺ x \in rg (f ↾ μ (k)) . \end{matrix}$

To prove Claim 1, let $n, k \in H$ be such that $n < k$ and $g (n + k) = r$ . As in the proof of Proposition 3.1, let ℓ be such that for all $x < λ (n)$ , $\begin{matrix} x \in rg (f) ⟺ x \in rg (f ↾ ℓ) . \end{matrix}$ Then, take $m \in H$ such that $λ (m) > ℓ$ . Now, if $x \in rg (f) ∖ rg (f ↾ μ (k))$ for some $x < λ (n)$ , then the number of important digits in $n + k + m$ is greater by one than the number of important digits in $n + k$ . Then, $g (n + k + m) = 1 - g (n + k) = 1 - r$ which contradicts the fact that r is the colour of ${FS}^{= 3} (H)$ . Thus, Claim 1 is proved. Claim 2.
For each $n \in H$ there exists $k \in H$ such that $n < k$ and $g (n + k) = r$ .

To prove Claim 2, fix n and, again, let ℓ be such that for all $x < λ (n)$ , $\begin{matrix} x \in rg (f) ⟺ x \in rg (f ↾ ℓ) . \end{matrix}$ Take any $k \in H$ such that $λ (k) > ℓ$ . For any $m \in H$ , if $k < m$ , then $g (n + k) = g (n + k + m) = r$ . This proves Claim 2.

We now describe an algorithm for deciding membership in $rg (f)$ given access to H. For an input x, find $n \in H$ such that $x < λ (n)$ . Then, find $k \in H$ such that $n < k$ and $g (n + k) = r$ . By Claim 2 this part of computation ends successfully. Finally, check whether $x \in rg (f ↾ μ (k))$ . By Claim 1 this is equivalent to $x \in rg (f)$ . □

Let us conclude this section with some remarks on the relations between the principles ${HT}_{k}^{= n}$ with apartness and ${HT}_{p}^{= ℓ}$ with apartness for arbitrary $n, ℓ ⩾ 3$ and $k, p ⩾ 2$ . Prima facie it is not obvious that, say, ${HT}_{2}^{= 3}$ with apartness implies ${HT}_{8}^{= 2}$ with apartness. Yet the proofs of our results above allow us to show that some of these principles are equivalent over ${RCA}_{0}$ .
Proposition 3.4.
For each $n ⩾ 3$ and $k ⩾ 2$ , ${HT}_{2}^{= 3}$ with apartness is equivalent to ${HT}_{k}^{= n}$ with apartness and to ${ACA}_{0}$ over ${RCA}_{0}$ .
Proof.
The proof of Theorem 3.3 obviously shows that, for $n ⩾ 3$ , ${HT}_{2}^{= n}$ with apartness implies ${ACA}_{0}$ over ${RCA}_{0}$ . On the other hand, for each $n ⩾ 1$ , ${RT}_{k}^{n}$ implies ${HT}_{k}^{= n}$ with apartness. Finally, it is known that for each $n ⩾ 3$ and $k ⩾ 2$ , the principle ${RT}_{k}^{n}$ is equivalent to ${ACA}_{0}$ over ${RCA}_{0}$ . Thus, ${ACA}_{0}$ implies ${HT}_{k}^{= n}$ with apartness. This concludes the proof. □

We finally observe that, in some cases an implication from ${HT}_{k}^{= m}$ to ${HT}_{k}^{= n}$ (with $m > n$ ) can be witnessed by a strong computable reduction. Proposition 3.5.
For any $n, m ⩾ 2$ and $k ⩾ 2$ , if n divides m then ${HT}_{k}^{= n}$ is strongly computably reducible to ${HT}_{k}^{= m}$ .
Proof.
Let $f : N \to k$ . Let $m = n d$ . Let $H = {h_{1}, h_{2}, \dots} \subseteq N$ with $h_{1} < h_{2} < \dots$ be a solution for the instance f of ${HT}_{k}^{= m}$ . Let $H^{+}$ consist of the sums of d many consecutive terms of H, i.e., $H^{+} = {h_{1} + \dots + h_{d}, h_{d + 1} + \dots + h_{2 d + 1}, \dots}$ . Then ${FS}^{= n} (H^{+})$ is monochromatic. □

4. Bounded Hindman and Polarized Ramsey

We here consider the principle ${HT}^{⩽ 2}$ from Question 12 of [21] from the point of view of strong computable reductions. Before our Theorem 3.2 the only known lower bounds on ${HT}_{k}^{⩽ 2}$ principles were those of Dzhafarov et al. [12] showing that ${HT}_{2}^{⩽ 2}$ is not provable in the base theory ${RCA}_{0}$ and that the Stable Ramsey’s Theorem for pairs ${SRT}_{2}^{2}$ follows from ${HT}_{2}^{⩽ 2} + B Σ_{2}^{0}$ . ${SRT}_{2}^{2}$ is just Ramsey’s Theorem for 2-colourings of ${[N]}^{2}$ restricted to colourings – called stable colourings – that eventually stabilize with respect to the second coordinate. After our conference paper [8] appeared, Csima et al. published new lower bounds on ${HT}_{2}^{= 2}$ ([10], see Remark 1 below for a discussion of these results).

In this section we uncover a tight connection between ${HT}^{⩽ 2}$ and the Increasing Polarized Ramsey’s Theorem for pairs ${IPT}_{2}^{2}$ introduced by Dzhafarov and Hirst in [15], which is known to be strictly stronger than ${SRT}_{2}^{2}$ (Corollary 4.12 of [29]). We show that ${IPT}_{2}^{2}$ is strongly computably reducible to ${HT}_{4}^{⩽ 2}$ . As a reverse mathematical implication, this is weaker than the one from ${HT}_{4}^{⩽ 2}$ to ${RT}_{2}^{3}$ in our Theorem 3.2. However we do not know whether the latter can be witnessed by a strong computable reduction.

We start by recalling the definition of the Increasing Polarized Ramsey’s Theorem.

Definition 4.1 (Increasing Polarized Ramsey’s Theorem).

For a pair of positive integers n and k, ${IPT}_{k}^{n}$ is the following principle.

Whenever ${[N]}^{n}$ is k-coloured then there exists a sequence $(H_{1}, \dots, H_{n})$ of infinite subsets of N such that all edges of the form ${x_{1}, \dots, x_{n}}$ with $x_{1} < \dots < x_{n}$ , $x_{i} \in H_{i}$ have the same colour.

A sequence of sets $H_{1}, \dots, H_{n}$ satisfying the above homogeneity property is referred to as an increasing p-homogeneous sequence. ${IPT}_{2}^{2}$ can be read as the following restriction of ${RT}_{2}^{2}$ : given a 2-colouring of the complete graph on N, we look for an infinite bipartite graph whose forward edges all have the same colour (such a graph is sometimes called a skew bipartite graph). It is not known whether ${IPT}_{2}^{2}$ is strictly weaker than ${RT}_{2}^{2}$ .

We first show that ${IPT}_{2}^{2}$ reduces in the sense of $⩽_{sc}$ to ${HT}_{2}^{= 2}$ with apartness. When this result appeared (Theorem 3 in [8]), no lower bounds on ${HT}_{2}^{= 2}$ without apartness were known (see Remark 1 below for further details).

Theorem 4.2.
${IPT}_{2}^{2}$ is strongly computably reducible to ${HT}_{2}^{= 2}$ with apartness.
Proof.
Let $c : {[N]}^{2} \to 2$ be given. Define $f : N \to 2$ as follows: $\begin{matrix} f (n) : = \{\begin{matrix} 0 & if n = 2^{m} for some m or λ (n) = 0, \\ c (λ (n), μ (n)) & otherwise. \end{matrix} \end{matrix}$ Note that f is well-defined since $λ (n) < μ (n)$ if n is not of the form $2^{m}$ . The other condition in the first case of the definition of f ( $λ (n) = 0$ ) is to avoid applying c on pairs with 0 as the first coordinate.

Let $H = {h_{1} < h_{2} < \dots} \subseteq N$ witness ${HT}_{2}^{= 2}$ with apartness for f. Note that (by the apartness condition) we can assume without loss of generality that $0 < λ (h_{1})$ and thus $0 < λ (h_{i})$ for all $i \in N$ . Let $\begin{matrix} H_{1} : = {λ (h_{2 i - 1}) : i \in N}, H_{2} : = {μ (h_{2 i}) : i \in N} . \end{matrix}$ We claim that $(H_{1}, H_{2})$ is a solution to ${IPT}_{2}^{2}$ for c.

First observe that we have $\begin{matrix} H_{1} = {λ (h_{1}), λ (h_{3}), λ (h_{5}), \dots}, H_{2} = {μ (h_{2}), μ (h_{4}), μ (h_{6}), \dots}, \end{matrix}$ with $λ (h_{1}) < λ (h_{3}) < λ (h_{5}) < \dots$ and $μ (h_{2}) < μ (h_{4}) < μ (h_{6}) < \dots$ . This is so because $λ (h_{1}) ⩽ μ (h_{1}) < λ (h_{2}) ⩽ μ (h_{2}) < \dots$ by the apartness condition. Let the colour of ${FS}^{= 2} (H)$ under f be $k < 2$ . We claim that $c (x_{1}, x_{2}) = k$ for every increasing pair $(x_{1}, x_{2}) \in H_{1} \times H_{2}$ . Note that $(x_{1}, x_{2}) = (λ (h_{i}), μ (h_{j}))$ for some $i < j$ (the case $i = j$ is impossible by construction of $H_{1}$ and $H_{2}$ ). We have $\begin{matrix} c (x_{1}, x_{2}) = c (λ (h_{i}), μ (h_{j})) = c (λ (h_{i} + h_{j}), μ (h_{i} + h_{j})) = f (h_{i} + h_{j}) = k, \end{matrix}$ since ${FS}^{= 2} (H)$ is monochromatic for f with colour k. This shows that $(H_{1}, H_{2})$ is an increasing p-homogeneous sequence for c. □
Corollary 4.3.
${IPT}_{2}^{2}$ is strongly computably reducible to ${FUT}_{2}^{⩽ 2}$ and to ${HT}_{4}^{⩽ 2}$ .
Proof.
Note that the relation $⩽_{sc}$ is transitive. That ${IPT}_{2}^{2} ⩽_{sc} {FUT}_{2}^{⩽ 2}$ follows from Theorem 4.2 and Proposition 2.5. The fact that ${IPT}_{2}^{2} ⩽_{sc} {HT}_{4}^{⩽ 2}$ follows from Theorem 4.2 and Lemma 2.7. □

5. Other restrictions of Hindman’s Theorem

In this section we present results on some restrictions of Hindman’s Theorem of a different flavour. These restrictions are not obtained by merely bounding the number of terms of the sums for which monochromaticity is guaranteed. Instead, it is required that all sums whose length belongs to some structured set of integers have the same colour. Nevertheless, some bounds on their strength can be obtained by adapting the previous arguments.

5.1. Weak yet strong principles

The first author investigated in [7] a family of restrictions of $HT$ that admit proofs from Ramsey’s Theorem yet realize the Blass–Hirst–Simpson lower bound, i.e., they are equivalent to ${ACA}_{0}$ . Our results from the previous sections (Theorem 3.3 and Proposition 3.4) show that the principles ${HT}_{k}^{= n}$ with apartness are a “weak yet strong” family in this sense. One might read this “weak yet strong” phenomenon as a warning not to over-interpret the lower bounds for ${HT}^{⩽ 2}$ obtained in the previous sections. For $X, A \subseteq N$ we denote by ${FS}^{A} (X)$ the set of all numbers that are non-empty sums of a-many distinct elements from X, for some $a \in A$ (e.g., in this notation, $FS (X)$ is ${FS}^{N} (X)$ and ${FS}^{{⩽ n}} (X)$ is ${FS}^{{1, 2, \dots, n}} (X)$ ). The simplest instance of the “weak yet strong” phenomenon treated in [7] is the following Hindman–Brauer Theorem (with 2-apartness):

Whenever N is 2-coloured there is an infinite and 2-apart set $H \subseteq N$ and there exist positive integers $a, b$ such that ${FS}^{{a, b, a + b, a + 2 b}} (H)$ is monochromatic.

We complement the results from [7] by showing that some prima facie weaker restrictions of Hindman’s Theorem share the same properties of the Hindman–Brauer Theorem.

Definition 5.1.
${HT}_{2}^{\exists {a < b}}$ is the following principle: Whenever N is 2-coloured there exists an infinite set $H \subseteq N$ and positive integers $a < b$ such that ${FS}^{{a, b}} (H)$ is monochromatic.
Theorem 5.2.
${HT}_{2}^{\exists {a < b}}$ with apartness is equivalent to ${ACA}_{0}$ over ${RCA}_{0}$ .
Proof.
We first prove the upper bound. Given $f : N \to 2$ let $c : {[N]}^{3} \to 8$ be defined as follows: $\begin{matrix} c (x_{1}, x_{2}, x_{3}) : = ⟨ f (x_{1}), f (x_{1} + x_{2}), f (x_{1} + x_{2} + x_{3}) ⟩ . \end{matrix}$ Fix an infinite and apart set $H_{0} \subseteq N$ . By ${RT}_{8}^{3}$ applied to colourings of triples from $H_{0}$ we get an infinite (and 2-apart) set $H \subseteq H_{0}$ monochromatic for c. Let the colour of ${[H]}^{3}$ be $(c_{1}, c_{2}, c_{3})$ , a binary sequence of length 3. Then, for each $i \in {1, 2, 3}$ , f restricted to ${FS}^{= i} (H)$ is a constant function with value $c_{i}$ . Obviously for some $3 ⩾ b > a > 0$ it must be that $c_{a} = c_{b}$ . Then ${FS}^{{a, b}} (H)$ is monochromatic under f.

The lower bound is proved by a minor adaptation of the proof of Proposition 3.1. As the n in that proof take an a-term sum. Then take a $(b - a)$ -term sum as the m. □

Note that the upper bound part of the previous theorem establishes that ${HT}_{2}^{\exists {a < b}}$ with apartness is strongly computably reducible to ${RT}_{8}^{3}$ . The same lower bound proof yields that the following Hindman–Schur Theorem with apartness from [7] implies ${RT}_{2}^{3}$ :
Whenever N is 2-coloured there is an infinite and apart set $H \subseteq N$ and there exist positive integers $a, b$ such that ${FS}^{{a, b, a + b}} (H)$ is monochromatic.
Indeed, the latter principle implies ${HT}^{\exists {a < b}}$ with apartness. Provability from ${RT}_{2}^{3}$ is shown in [7] by an argument similar to the upper bound part of Theorem 5.2. The proof shows indeed that the Hindman–Schur Theorem with apartness is strongly computably reducible to ${RT}_{2^{6}}^{6}$ . The number 6 comes from the Ramsey number for ensuring a monochromatic triangle and from the standard proof of Schur’s Theorem from the finite Ramsey Theorem (see, e.g., [17]).

Let us observe that the proof of Theorem 3.3 works in the case of ${HT}_{2}^{= a}$ with apartness, for any fixed $a ⩾ 3$ by taking a sum of $a - 2$ elements in place of n. This leads us to the following definition and corollary.
Definition 5.3.
Let ${HT}_{2}^{\exists {a ⩾ 3}}$ be the following principle: For every colouring $f : N \to 2$ there exists an infinite set $H \subseteq N$ and there exists a number $a ⩾ 3$ such that ${FS}^{{a}} (H)$ is monochromatic for f.
Theorem 5.4.
${HT}_{2}^{\exists {a ⩾ 3}}$ with apartness is equivalent to ${ACA}_{0}$ , over ${RCA}_{0}$ .

Note that the latter result, coupled with the results of the previous section, shows that the principles ${HT}_{k}^{= n}$ with apartness form a weak yet strong family in the sense of [7].
5.2. Increasing polarized Hindman’s Theorem

We define an (increasing) polarized version of Hindman’s Theorem. We prove that the case of pairs and 2 colours with an appropriately defined notion of apartness is equivalent to ${IPT}_{2}^{2}$ . Indeed the two principles are strongly computably inter-reducible.

Definition 5.5 ((Increasing) Polarized Hindman’s Theorem).

Fix $n ⩾ 1$ . ${PHT}_{2}^{n}$ (resp. ${IPHT}_{2}^{n}$ ) is the following principle: For every 2-colouring f of N there exists a sequence $(H_{1}, \dots, H_{n})$ of infinite sets such that for some colour $k < 2$ , for all (resp. increasing) $(x_{1}, \dots, x_{n}) \in H_{1} \times \dots \times H_{n}$ , $f (x_{1} + \dots + x_{n}) = k$ .

We impose an apartness condition on a solution $(H_{1}, \dots, H_{n})$ of ${IPHT}_{2}^{n}$ by requiring that the union $H_{1} \cup \dots \cup H_{n}$ is apart. We denote by “ ${IPHT}_{2}^{n}$ with apartness” the principle ${IPHT}_{2}^{n}$ with this apartness condition on the solution set.

Theorem 5.6.
${IPT}_{2}^{2}$ and ${IPHT}_{2}^{2}$ with apartness are equivalent over ${RCA}_{0}$ . Furthermore, the two principles are mutually strongly computably reducible.
Proof.
We first prove that ${IPHT}_{2}^{2} with apartness ⩽_{sc} {IPT}_{2}^{2}$ . Given $f : N \to 2$ define $c : {[N]}^{2} \to 2$ by setting $c (x, y) : = f (2^{x} + 2^{y})$ . Let $(H_{1}, H_{2})$ be a solution of ${IPT}_{2}^{2}$ for c. Let the colour under c of all increasing pairs in $H_{1} \times H_{2}$ be $k < 2$ . Let $H_{i}^{+} = {2^{x} : x \in H_{i}}$ , for $i \in {1, 2}$ . The set $H_{1}^{+} \cup H_{2}^{+}$ is apart by construction. Obviously we have that for any increasing pair $(2^{x_{1}}, 2^{x_{2}}) \in H_{1}^{+} \times H_{2}^{+}$ , $f (2^{x_{1}} + 2^{x_{2}}) = c (x_{1}, x_{2}) = k$ . Therefore $(H_{1}^{+}, H_{2}^{+})$ is a solution to ${IPHT}_{2}^{2}$ with apartness for f.

Next we prove that ${IPT}_{2}^{2} ⩽_{sc} {IPHT}_{2}^{2}$ with apartness. Let $c : {[N]}^{2} \to 2$ be given. Define $f : N \to 2$ by setting $f (n) : = c (λ (n), μ (n))$ if n is neither a power of 2 nor such that $λ (n) = 0$ , and $f (n) = 0$ otherwise. Let $(H_{1}, H_{2})$ be an apart solution to ${IPHT}_{2}^{2}$ for f, of colour $k < 2$ . By apartness we can assume without loss of generality that $0 < λ (h_{i})$ for all $i \in N$ . Let $H = {h_{1} < h_{2} < h_{3} < \dots}$ be such that $h_{2 i - 1} \in H_{1}$ and $h_{2 i} \in H_{2}$ for each $i \in N$ . Then set $H_{1}^{+} : = {λ (h_{2 i - 1}) : i \in N}$ and $H_{2}^{+} : = {μ (h_{2 i}) : i \in N}$ . We claim that $(H_{1}^{+}, H_{2}^{+})$ is an increasing p-homogeneous pair for c. Let $(x_{1}, x_{2}) \in H_{1}^{+} \times H_{2}^{+}$ be an increasing pair. Then for some $h \in H_{1}$ and $h^{'} \in H_{2}$ such that $h < h^{'}$ we have $λ (h) = x_{1}$ and $μ (h^{'}) = x_{2}$ . Therefore $\begin{matrix} c (x_{1}, x_{2}) = c (λ (h), μ (h^{'})) = c (λ (h + h^{'}), μ (h + h^{'})) = f (h + h^{'}) = k, \end{matrix}$ regardless of the choice of $(x_{1}, x_{2})$ . □

5.3. Exactly large sums, with apartness

By analogy with the Pudlák-Rödl [30] theorem ${RT}_{2}^{! ω}$ on colourings of exactly large sets we consider a restriction of Hindman’s Theorem to exactly large sums, i.e., sums whose set of terms is an exactly large set. As noted earlier, the Pudlák-Rödl theorem is known to imply $HT$ over ${RCA}_{0}$ (yet no combinatorial proof is known).

Let us introduce some terminology and notation and state the Pudlák-Rödl theorem. A finite set $S \subseteq N$ is exactly large, or $! ω$ -large, if $| S | = min (S) + 1$ . Exactly large sets are strictly related to Schreier sets in Banach Space Theory (see [16]), while their supersets – called relatively large sets – play a prominent role in the study of unprovability results for first-order theories of arithmetic (see [24,27]).

Definition 5.7 (Ramsey’s Theorem for exactly large sets).

${RT}_{2}^{! ω}$ is the following principle:

Whenever the exactly large subsets of an infinite set $X \subseteq N$ are coloured in 2 colours, there exists an infinite set $H \subseteq X$ such that all exactly large subsets of H have the same colour.

The strength of ${RT}_{2}^{! ω}$ was studied by the first and fourth author in [9] and proved there to be much beyond the strength of Ramsey’s Theorem.

We now formulate our analogue for Hindman’s Theorem. Given a set X of natural numbers, the sums of integers whose underlying set of terms is an exactly large set in X are called exactly large sums (from X). We denote by ${FS}^{! ω} (X)$ the set of numbers that can be expressed as sums of an exactly large subset of X.

Definition 5.8 (Hindman’s Theorem for Exactly Large Sums).

${HT}_{2}^{! ω}$ denotes the following principle: For every colouring $f : N \to 2$ there exists an infinite set $H \subseteq N$ such that ${FS}^{! ω} (H)$ is monochromatic under f.

Besides being a restriction of $HT$ , ${HT}_{2}^{! ω}$ (with t-apartness, for any $t > 1$ ) has an easy direct proof from ${RT}_{2}^{! ω}$ . Given $f : N \to 2$ just set $c (S) : = f (\sum_{s \in S} s)$ , for S an exactly large set (to get t-apartness, restrict c to an infinite t-apart set). Consistently with the previous conventions, we use ${HT}_{2}^{! ω}$ with 2-apartness to denote the principle obtained from ${HT}_{2}^{! ω}$ by imposing that the solution is a 2-apart set. We note, however, that for the principle ${HT}_{2}^{! ω}$ the choice of t in the t-apartness conditon might matter.

The argument of Theorem 3.3 can be easily adapted to show that ${HT}_{2}^{! ω}$ with 2-apartness implies ${ACA}_{0}$ . In the proof of Theorem 3.3 take, instead of n, an almost exactly large sum $n_{0} + n_{1} + \dots + n_{n_{0} - 2}$ of elements of H. The argument then proceeds unchanged.

Proposition 5.9.
${HT}_{2}^{! ω}$ with apartness implies ${ACA}_{0}$ over ${RCA}_{0}$ .

Furthermore, a number of strong computable reductions can be established for Hindman’s Theorem for exactly large sums. For example, we have the following result.
Proposition 5.10.
${IPHT}_{2}^{2}$ with apartness is strongly computably reducible to ${HT}_{2}^{! ω}$ with apartness.
Proof.
Let $f : N \to 2$ be given, and let $H = {h_{1}, h_{2}, h_{3}, \dots}$ with $h_{1} < h_{2} < h_{3} < \dots$ be an infinite 2-apart set such that ${FS}^{! ω} (H)$ is monochromatic for f of colour $k < 2$ . Let $S_{1}, S_{2}, S_{3}, \dots$ be such that each $S_{i}$ is an exactly large subset of H, $⋃_{i \in N} S_{i} = H$ , and $max S_{i} < min S_{i + 1}$ , for each $i \in N$ . Let $s_{i} = \sum_{s \in S_{i}} s$ . Let $H_{s} : = {s_{1}, s_{2}, \dots}$ . $H_{s}$ is 2-apart and consists of the sums of consecutive disjoint exactly large subsets of H. Let $H_{t} = {t_{1}, t_{2}, \dots}$ (in increasing order) be the set consisting of the elements from $H_{s}$ minus their largest term (when written as $! ω$ -sums). Note that distinct elements of $H_{s}$ share no term, because $H_{s}$ is 2-apart. Let $H_{1} : = H_{t}$ and $H_{2} : = {s_{i} - t_{i} : i \in N}$ . Then $(H_{1}, H_{2})$ is a 2-apart solution for ${IPHT}_{2}^{2}$ . Note that both $H_{1}$ and $H_{2}$ are computable relative to H. □
Proposition 5.11.
${HT}_{k}^{! ω}$ implies ${HT}_{k}^{= 2}$ over ${RCA}_{0}$ , for each $k \in N$ .
Proof.
Let c be a k-coloring of N and let X be a solution to ${HT}_{k}^{! ω}$ for c. We reason by cases.

Case 1. X contains infinitely many odd elements. Let $d_{1} < d_{2} < d_{3} < \dots$ be the odd elements in X and assume, without loss of generality, that $d_{1} > 1$ . Consider the exactly large set $D = {d_{1}, d_{2}, \dots, d_{d_{1} + 1}}$ and let $\begin{matrix} X_{o} = {x \in X : x > d_{d_{1} - 1}} . \end{matrix}$ Let $\begin{matrix} s = d_{1} + d_{2} + \dots + d_{d_{1} - 1} . \end{matrix}$ Observe that s is even. Let $\begin{matrix} x_{1}^{'} < x_{2}^{'} < x_{3}^{'} < \dots \end{matrix}$ be an increasing enumeration of $X_{o}$ . Consider the set $H = {h_{1}, h_{2}, h_{3}, \dots}$ where $\begin{matrix} h_{i} = \frac{s}{2} + x_{i}^{'} . \end{matrix}$ We have that, for all $i < j$ : $\begin{matrix} h_{i} + h_{j} = s + x_{i}^{'} + x_{j}^{'} = d_{1} + d_{2} + \dots + d_{d_{1} - 1} + x_{i}^{'} + x_{j}^{'} . \end{matrix}$ Therefore H is an infinite solution to ${HT}_{k}^{= 2}$ for c.

Case 2 can be treated analogously. The details are left to the reader. □

Other results on ${HT}_{2}^{! ω}$ were proved by the third author in his BSc. Thesis [25]. We believe that the study of the strength of ${HT}_{2}^{! ω}$ is of interest. Remark 1.
Most of our results in this paper deal with restrictions of the Finite Sums Theorem with the apartness condition or, equivalently (in view of Proposition 2.5), on restrictions of the Finite Unions Theorem. As implied by Lemma 2.7 and witnessed by Theorem 3.2, some corollaries on restrictions of the Finite Sums Theorem ${HT}_{k}^{⩽ n}$ without the apartness condition can also be obtained from bounds on restrictions with apartness. To obtain lower bounds for the restrictions ${HT}_{k}^{= n}$ without apartness seems instead to require different methods. Only very recently, after the conference version [8] appeared and a draft of the present paper was circulated, a lower bound on ${HT}_{2}^{= 2}$ without the apartness condition was obtained by Csima et alii [10]. The proof features a very interesting technique derived from probabilistic arguments in combinatorics and gives as a corollary that ${HT}_{2}^{= 2}$ implies, over ${RCA}_{0}$ , the Rainbow Ramsey Theorem for pairs ${RRT}_{2}^{2}$ . Note that ${RRT}_{2}^{2}$ is strictly weaker than ${IPT}_{2}^{2}$ (for example the latter implies $SADS$ while the former doesn’t, see [11,15]) which we showed is a lower bound to ${HT}_{2}^{= 2}$ with apartness.

Combining the main results of [10] with some of our results presented above some corollaries on restrictions of the Finite Sums Theorem without apartness can be easily obtained. An inspection of the proofs in [10] shows that in general they apply if the homogeneity condition with respect to a coloring c of N in 2 colors is weakened to the following: for all $x < y < z$ we have $c (x + z) = c (y + z)$ . Moreover, the computability-theoretic and proof-theoretic lower bounds for ${HT}_{2}^{= 2}$ proved in [10] can be proved for the following principles studied above:
${IPHT}_{2}^{2}$ : The main arguments in [10] apply almost unchanged to this principle.

${HT}_{2}^{! ω}$ : By Proposition 5.11 this principle implies ${HT}_{2}^{= 2}$ .

${HT}^{\exists {a < b}}$ and ${HT}^{\exists {a ⩾ 3}}$ : both of these are easily seen to imply ${IPHT}_{2}^{2}$ . So by the first item they imply ${RRT}_{2}^{2}$ .

6. Conclusion and open questions

Our results are summarized in Table 1, along with previously known results. In the table we use Ramsey-theoretic statements instead of equivalent theories (thus ${RT}_{2}^{3}$ for ${ACA}_{0}$ and $\forall k {RT}_{k}^{1}$ instead of $B Σ_{2}^{0}$ ).

Table 1

Implications over ${RCA}_{0}$ ( $⩾, ⩽$ ) and strong combinatorial reductions ( $⩾_{sc}$ , $⩽_{sc}$ ). We abbreviate “with apartness” by “w. ap”

Principle:	Lower Bound	Upper Bound
$HT \equiv FUT$	$⩾ {RT}_{2}^{3}$ [4]	$⩽ {RT}_{2}^{! ω}$ [4,9]
${HT}_{2}^{⩽ 2}$	$⩾ {RRT}_{2}^{2}$ [10]	$⩽ {RT}_{2}^{! ω}$ [4,9]
${HT}_{2}^{⩽ 2} + \forall k {RT}_{k}^{1}$	$⩾ {SRT}_{2}^{2}$ [12]	$⩽ {RT}_{2}^{! ω}$ [4,9]
${FUT}_{2}^{⩽ 2} \equiv {HT}_{2}^{⩽ 2}$ w. ap.	$⩾ {RT}_{2}^{3}$ (Prop. 3.1)	$⩽ {RT}_{2}^{! ω}$ [4,9]
${HT}_{4}^{⩽ 2}$	$⩾ {RT}_{2}^{3}$ (Th. 3.2), $⩾_{sc} {IPT}_{2}^{2}$ (Cor. 4.3)	$⩽ {RT}_{2}^{! ω}$ [4,9]
${HT}_{2}^{\exists {a < b}}$	$⩾ {RRT}_{2}^{2}$ (Remark 1)	$⩽ {RT}_{2}^{3}$ , $⩽_{sc} {RT}_{8}^{3}$ (Th. 5.2)
${HT}_{2}^{\exists {a < b}}$ w. ap.	$⩾ {RT}_{2}^{3}$ (Th. 5.2)	$⩽ {RT}_{2}^{3}$ , $⩽_{sc} {RT}_{8}^{3}$ (Th. 5.2)
${HT}_{2}^{\exists {a ⩾ 3}}$	$⩾ {RRT}_{2}^{2}$ (Remark 1)	$⩽ {RT}_{2}^{3}$ [7]
${HT}_{2}^{\exists {a ⩾ 3}}$ w. ap.	$⩾ {RT}_{2}^{3}$ (Th. 5.4)	$⩽ {RT}_{2}^{3}$ , $⩽_{sc} {RT}_{2^{6}}^{6}$ [7]
${HT}_{2}^{= 2}$	$⩾ {RRT}_{2}^{2}$ [10]	$⩽_{sc} {RT}_{2}^{2}$ (obvious)
${HT}_{2}^{= 3}$	$⩾ {RRT}_{2}^{2}$ [10]	$⩽_{sc} {RT}_{2}^{3}$ (obvious)
${FUT}_{2}^{= 2} \equiv {HT}_{2}^{= 2}$ w. ap.	$⩾_{sc} {IPT}_{2}^{2}$ (Th. 4.2)	$⩽_{sc} {RT}_{2}^{2}$ (obvious)
${FUT}_{2}^{= 3} \equiv {HT}_{2}^{= 3}$ w. ap.	$⩾ {RT}_{2}^{3}$ (Th. 3.3)	$⩽_{sc} {RT}_{2}^{3}$ (obvious)
${IPHT}_{2}^{2}$	$⩾ {RRT}_{2}^{2}$ (Remark 1)	$⩽ {IPT}_{2}^{2}$ (Th. 5.6)
${IPHT}_{2}^{2}$ w. ap.	$⩾_{sc} {IPT}_{2}^{2}$ (Th. 5.6)	$⩽_{sc} {IPT}_{2}^{2}$ (Th. 5.6)
${HT}_{2}^{! ω}$	$⩾ {RRT}_{2}^{2}$ (Remark 1)	$⩽_{sc} {RT}_{2}^{! ω}$ (obvious)
${HT}_{2}^{! ω}$ w. ap.	$⩾ {RT}_{2}^{3}$ (Prop. 5.9)	$⩽_{sc} {RT}_{2}^{! ω}$ (obvious)

Theorem 3.2, showing that the ${RT}_{2}^{3}$ lower bound known for $HT$ already holds for ${HT}^{⩽ 2}$ , might be read as indicating that the latter restriction is as strong as the full theorem, thus pointing to a negative answer to Question 12 of [21]. On the other hand, many of our additional results confirm the “weak yet strong” phenomenon uncovered in [7]: the known lower bounds on Hindman’s Theorem hold for restricted versions for which – contrary to the ${HT}^{⩽ n}$ restrictions studied in [12] – a matching ${RT}_{2}^{3}$ upper bound is known. Analogously, the ${IPT}_{2}^{2}$ lower bound for ${HT}^{⩽ 2}$ already holds for the principle ${HT}_{2}^{= 2}$ with apartness, which is provable from ${RT}_{2}^{2}$ (for another example at this level, see [6]). Our results also highlight the role of the apartness condition on the solution set. They also apply to bounded versions of the Finite Unions formulation of Hindman’s Theorem, in which an analogous condition is already built-in.

Many natural questions remain, besides the main open problems on $HT$ and ${HT}^{⩽ 2}$ (Question 9 of [26] and Question 12 of [21]). The question of whether some of the known implications between Ramsey-type theorems and Hindman-type theorems can be witnessed by strong computable reductions is of interest. We expect that many separations are within reach of currently available methods. Some separations can be gleaned from our results and known results from the literature. For example, ${RT}_{8}^{4}, {RT}_{9}^{3} ≰_{sc} {HT}_{2}^{\exists {a, b}}$ with apartness, and ${RT}_{2}^{4}, {RT}_{4}^{3} ≰_{sc} {HT}_{2}^{= 3}$ with apartness. To see this, note that on the one hand we have ${HT}^{\exists {a, b}}$ with 2-apartness $⩽_{sc} {RT}_{8}^{3}$ by the upper bound proof in [7], and ${HT}_{2}^{= 3}$ with 2-apartness $⩽_{sc} {RT}_{2}^{3}$ by the trivial proof. On the other hand, ${RT}_{k}^{4} ≰_{sc} {RT}_{k}^{3}$ , ${RT}_{9}^{3} ≰_{sc} {RT}_{8}^{3}$ and ${RT}_{4}^{3} ≰_{sc} {RT}_{2}^{3}$ (see, e.g., [28]). Note that the separations can strengthened to computable reducibility.

We would like to single out the following two questions which seem to be of some general combinatorial interest.

Question 1.

Is there a strong computable reduction of ${IPT}_{k}^{3}$ to ${HT}_{ℓ}^{⩽ n}$ , for some $n, k, ℓ ⩾ 2$ ?

On the one hand we know that the implication from ${HT}_{4}^{⩽ 2}$ to ${IPT}_{2}^{3}$ holds over ${RCA}_{0}$ . This follows from Theorem 3.2 and the equivalence of ${IPT}_{2}^{3}$ with ${RT}_{2}^{3}$ (see [15]). On the other hand, we do not know how to lift the combinatorial reduction ${IPT}_{2}^{2} ⩽_{sc} {HT}_{4}^{⩽ 2}$ of Corollary 4.3 to higher exponents.

Question 2.

Is there a strong computable reduction of $HT$ to ${RT}_{2}^{! ω}$ ?

Combining the results of [4] and [9] we know that the implication from ${RT}_{2}^{! ω}$ to $HT$ holds over ${RCA}_{0}$ . Can this be witnessed by a strong computable reduction? Is there a combinatorial proof of Hindman’s Theorem from the Pudlák-Rödl Theorem?

Footnotes

Acknowledgements

Part of this work was done while the first author was visiting the Institute for Mathematical Sciences, National University of Singapore in 2016. The visit was supported by the Institute. The second author was partially supported by Polish National Science Centre grant no. 2013/09/B/ST1/04390. The fourth author was partially supported by University Cardinal Stefan Wyszyński in Warsaw grant UmoPBM-26/16. Some of the results have been presented at the conference Computability in Europe 2017 and appeared in [8]. We thank the referees for helpful suggestions for improving the paper. In particular, one of the referees suggested how to obtain a strong computable reduction for the forward implication of Theorem .

References

Argyros and

Todorčević, Ramsey Methods in Analysis, Advanced Courses in Mathematics CRM Barcelona, Birkhäuser, Basel-Boston-Berlin, 2005.

Bergelson, Ultrafilters, IP sets, dynamics, and combinatorial number theory, Contemporary Mathematics 530 (2010), 23–47. doi:10.1090/conm/530/10439.

Blass, Some questions arising from Hindman’s Theorem, Scientiae Mathematicae Japonicae 62 (2005), 331–334.

A.R.

Blass,

J.L.

Hirst and

S.G.

Simpson, Logical analysis of some theorems of combinatorics and topological dynamics, in: Logic and combinatorics (Arcata, Calif., 1985), Contemp. Math., Vol. 65, Amer. Math. Soc., Providence, RI, 1987, pp. 125–156. doi:10.1090/conm/065/891245.

Carlucci, Bounded Hindman’s Theorem and increasing polarized Ramsey’s theorem, In: Logic Blog, A. Nies, ed., Part 4, Section 9, 2016, available at: https://arxiv.org/abs/1703.01573.

Carlucci, A weak variant of Hindman’s Theorem stronger than Hilbert’s Theorem, Archive for Mathematical Logic 57(3–4) (2018), 381–389. doi:10.1007/s00153-017-0576-1.

Carlucci, “Weak yet strong” restrictions of Hindman’s finite sums theorem, Proceedings of the American Mathematical Society 146 (2019), 819–829. doi:10.1090/proc/13856.

Carlucci,

L.A.

Kołodziejczyk,

Lepore and

Zdanowski, New bounds on the strength of some restrictions of Hindman’s Theorem, in: Unveiling Dynamics and Complexity – 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12–16, 2017,

Kari,

Manea and

Petre, eds, Proceedings, Lecture Notes in Computer Science, Vol. 10307, Springer, 2017, pp. 210–220.

Carlucci and

Zdanowski, The strength of Ramsey’s theorem for colouring relatively large sets, Journal of Symbolic Logic 79(1) (2014), 89–102. doi:10.1017/jsl.2013.27.

10.

B.F.

Csima,

J.R.

Dzhafarov,

D.R.

Hirschfeldt,

Jockusch,

Solomon and

L.B.

Westrick, The reverse mathematics of Hindman’s Theorem for sums of exactly two elements, Computability 8(3–4) (2019), 253–263. doi:10.3233/COM-180094.

11.

B.F.

Csima and

J.R.

Mileti, The strength of the rainbow Ramsey theorem, Journal of Symbolic Logic 74(4) (2009), 1310–1324. doi:10.2178/jsl/1254748693.

12.

Dzhafarov,

Jockusch,

Solomon and

L.B.

Westrick, Effectiveness of Hindman’s Theorem for bounded sums, in: Proceedings of the International Symposium on Computability and Complexity,

Day,

Fellows,

Greenberg,

Khoussainov and

Melnikov, eds, Lecture Notes in Computer Science, Vol. 10010, Springer, 2016, pp. 134–142, (in honour of Rod Downey’s 60th birthday). doi:10.1007/978-3-319-50062-1_11.

13.

D.D.

Dzhafarov, Cohesive avoidance and strong reductions, Proceedings of the American Mathematical Society 143 (2015), 869–876. doi:10.1090/S0002-9939-2014-12261-1.

14.

D.D.

Dzhafarov, Strong reductions between combinatorial principles, Journal of Symbolic Logic 81(4) (2016), 1405–1431. doi:10.1017/jsl.2016.1.

15.

D.D.

Dzhafarov and

J.L.

Hirst, The polarized Ramsey’s theorem, Archive for Mathematical Logic 48(2) (2011), 141–157. doi:10.1007/s00153-008-0108-0.

16.

Farmaki and

Negrepontis, Schreier sets in Ramsey theory, Transactions of the American Mathematical Society 360(2) (2008), 849–880. doi:10.1090/S0002-9947-07-04323-1.

17.

R.L.

Graham and

B.L.

Rothschild Ramsey Theory, Wiley, New York, 1990.

18.

Hájek and

Pudlák, Metamathematics of First-Order Arithmetic, Springer Verlag, 1993.

19.

Hindman, The existence of certain ultrafilters on N and a conjecture of Graham and Rothschild, Proceedings of the American Mathematical Society 36(2) (1972), 341–346.

20.

Hindman, Finite sums from sequences within cells of a partition of N, Journal of Combinatorial Theory Series A 17 (1974), 1–11. doi:10.1016/0097-3165(74)90023-5.

21.

Hindman,

Leader and

Strauss, Open problems in partition regularity, Combinatorics Probability and Computing 12 (2003), 571–583. doi:10.1017/S0963548303005716.

22.

D.R.

Hirschfeldt, Slicing the truth (on the computable and reverse mathematics of combinatorial principles), Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, Vol. 28.

23.

Hirst, Hilbert vs Hindman, Archive for Mathematical Logic 51(1–2) (2012), 123–125. doi:10.1007/s00153-011-0257-4.

24.

Ketonen and

Solovay, Rapidly growing Ramsey functions, Annals of Mathematics, (ser. 2) 113 (1981), 267–314. doi:10.2307/2006985.

25.

F.C.

Lepore, The effective content and logical strength of Hindman’s finite sums theorem, BSc. Thesis, Computer Science Department, University of Rome I, 2016.

26.

Montalbán, Open questions in reverse mathematics, Bulletin of Symbolic Logic 17(3) (2011), 431–454. doi:10.2178/bsl/1309952320.

27.

Paris and

Harrington, A mathematical incompleteness in Peano arithmetic, in: Handbook of Mathematical Logic,

Barwise, ed., North-Holland, 1977, pp. 1133–1142. doi:10.1016/S0049-237X(08)71130-3.

28.

Patey, The weakness of being cohesive, thin or free in reverse mathematics, Israel Journal of Mathematics 216(2) (2016), 905–955. doi:10.1007/s11856-016-1433-3.

29.

Patey, Somewhere over the rainbow Ramsey theorem for pairs, Preprint, arXiv:1501.07424.

30.

Pudlák and

Rödl, Partition theorems for systems of finite subsets of integers, Discrete Mathematics 39(1) (1982), 67–73. doi:10.1016/0012-365X(82)90041-3.

31.

Simpson, Subsystems of Second Order Arithmetic, 2nd edn, Cambridge University Press, New York, NY, 2009, Association for Symbolic Logic.