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

Abstract

Hindman’s Theorem (HT) states that for every coloring of $N$ with finitely many colors, there is an infinite set $H \subseteq 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, ${HT}_{k}^{⩽ n}$ is the restriction of HT to sums of at most n many elements, with at most k colors allowed, and ${HT}_{k}^{= n}$ 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₀. In contrast, ${HT}_{2}^{= 2}$ is known to be strictly weaker than HT over RCA₀, 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₀, or even WKL₀. 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 $\emptyset^{'}$ . It follows that there is a computable instance of ${HT}_{2}^{= 2}$ with no $Σ_{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 $\emptyset^{'}$ shows that ${HT}_{2}^{= 2}$ implies ${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.

Keywords

Reverse mathematics Hindman’s Theorem Lovász Local Lemma

1. Introduction

This paper is concerned with the computability-theoretic and reverse-mathematical analysis of combinatorial principles, in particular that of versions of Hindman’s Theorem, a line of research that began with the work of Blass, Hirst, and Simpson [1] and has more recently seen substantial further development. Our main contribution is to bring to the area the use of probabilistic methods, in particular the Lovász Local Lemma, in an effective version due to Rumyantsev and Shen [16,17].

We assume familiarity with the basic concepts of computability theory and reverse mathematics. For a principle P of second-order arithmetic of the form $\forall X$ $[Θ (X) \to \exists Y Ψ (X, Y)]$ , an instance of P is an X such that $Θ (X)$ holds, and a solution to this instance is a Y such that $Ψ (X, Y)$ holds.

Hindman’s Theorem (HT) [7] states that for every coloring c of $N$ with finitely many colors, there is an infinite set $H \subseteq N$ such that all nonempty sums of distinct elements of H have the same color. Blass, Hirst, and Simpson [1] showed that such an H can always be computed in the $(ω + 1)$ st jump of c, and that there is a computable instance of HT such that every solution computes $\emptyset^{'}$ . By analyzing these proofs they showed that HT is provable in ${ACA}_{0}^{+}$ (the system consisting of RCA₀ together with the statement that ωth jumps exist) and implies ACA₀ over RCA₀. The exact reverse-mathematical strength of HT remains open, however.

Recently, there has been interest in investigating restricted versions of Hindman’s Theorem. For instance, ${HT}^{⩽ n}$ is HT restricted to sums of at most n many elements, and ${HT}^{= n}$ is HT restricted to sums of exactly n many elements. We can also consider ${HT}_{k}^{⩽ n}$ and ${HT}_{k}^{= n}$ , the corresponding restrictions to k-colorings. (Notice that ${HT}_{k + 1}^{⩽ n}$ clearly implies ${HT}_{k}^{⩽ n}$ , and similarly for ${HT}^{= n}$ .) An interesting phenomenon is that quite weak versions of HT are still rather difficult to prove. Indeed, there is no known way to prove even ${HT}^{⩽ 2}$ other than to give a proof of the full HT, which has led Hindman, Leader, and Strauss [8] to ask whether every proof of ${HT}^{⩽ 2}$ is also a proof of HT.

Dzhafarov, Jockusch, Solomon, and Westrick [4] showed that ${HT}_{3}^{⩽ 3}$ implies ACA₀ over RCA₀ and that ${HT}_{2}^{⩽ 2}$ is not provable in RCA₀. Carlucci, Kołodzieczyk, Lepore, and Zdanowski [2] investigated versions of Hindman’s Theorem for sums of bounded length in which the solutions are required to meet a certain natural sparseness condition known as apartness, and in particular showed that ${HT}_{2}^{⩽ 2}$ with apartness implies ACA₀ over RCA₀. (They also have results for ${HT}_{k}^{= n}$ with apartness.) They then deduced that ${HT}_{4}^{⩽ 2}$ (with no extra conditions) implies ACA₀ over RCA₀. It remains open whether either of ${HT}_{2}^{⩽ 2}$ and ACA₀ implies the other over RCA₀.

The principle ${HT}^{= 2}$ is quite different, as it follows immediately from Ramsey’s Theorem for pairs. For a set S, let ${[S]}^{n}$ be the set of n-element subsets of S. Recall that ${RT}_{k}^{n}$ is the statement that every k-coloring of ${[N]}^{n}$ has an infinite homogeneous set, that is, an infinite set H such that all elements of ${[H]}^{n}$ have the same color. Then ${HT}_{k}^{= n}$ follows at once from ${RT}_{k}^{n}$ , as ${HT}_{k}^{= n}$ is essentially the restriction of ${RT}_{k}^{= n}$ to colorings of ${[N]}^{n}$ where the color of a set depends only on the sum of its elements. For $n ⩾ 3$ (and $k ⩾ 2$ ), ${RT}_{k}^{n}$ is equivalent to ACA₀ over RCA₀, but ${RT}_{k}^{2}$ is a weaker principle, incomparable with WKL₀ (see e.g. Hirschfeldt [9] for further details).

The possibility was left open in late drafts of [4] that ${HT}_{2}^{= 2}$ is so weak as to be computably true, although a brief note at the end of the published version mentions the solution of this problem and more in the current paper. We will show that ${HT}_{2}^{= 2}$ is not computably true, and indeed, there is a computable instance of ${HT}_{2}^{= 2}$ such that the degree of any solution is DNC relative to $\emptyset^{'}$ (see Section 3 for a definition). It follows that this instance does not have any computable or even $Σ_{2}^{0}$ solutions. Thus ${HT}_{2}^{= 2}$ is not provable in RCA₀, or even in WKL₀. (That ${HT}_{2}^{= 2}$ does not imply WKL₀ follows from the analogous fact for ${RT}_{2}^{2}$ , proved by Liu [12].) Our method will also apply to a wider class of principles generalizing ${HT}_{2}^{= 2}$ , including one studied by Murakami, Yamazaki, and Yokoyama [15].

The basic idea for showing that ${HT}_{2}^{= 2}$ is not computably true is straightforward. We build a computable instance $c : N \to 2$ of ${HT}_{2}^{= 2}$ with no computable solution. Let $W_{0}, W_{1}, \dots$ be an effective listing of the c.e. sets. For $S \subseteq N$ and $s \in N$ , let $S + s = {k + s : k \in S}$ . For each i we choose an appropriately large number $k_{i}$ , wait until at least $k_{i}$ many numbers enter $W_{i}$ , and let $E_{i}$ consist of the first $k_{i}$ many numbers to enter $W_{i}$ , if $| W_{i} | ⩾ k_{i}$ . We would then like to ensure, for all sufficiently large s, that $E_{i} + s$ is not homogeneous for c, meaning that there are $x, y \in E_{i} + s$ such that $c (x) \neq c (y)$ . Then $E_{i}$ cannot be contained in a solution to c, hence in particular $W_{i}$ cannot be such a solution.

If we consider only a single fixed i, it is easy to define (uniformly in i) a computable coloring $c_{i}$ that satisfies the above, i.e., such that for all sufficiently large s, we have that $E_{i} + s$ is not homogeneous for $c_{i}$ . To do so, let $k_{i} = 2$ , and let $d = b - a$ , where $E_{i} = {a, b}$ and $a < b$ . Then define $c_{i}$ recursively as follows. If $E_{i}$ has not been defined by stage s or $s < d$ , let $c (s) = 0$ . Otherwise (so d is known at stage s), let $c (s) = 1 - c (s - d)$ . Then for all sufficiently large s, we have that $c (b + s) \neq c (b + s - d) = c (a + s)$ , so $E_{i} + s$ is not homogeneous for c because it contains $b + s$ and $a + s$ .

However, the simple method above can break down even for two values of i, say $i_{0}$ and $i_{1}$ , at least if we take $k_{i} = 2$ for $i = i_{0}, i_{1}$ . In such a case, it could happen that $E_{i_{0}} = {0, 1}$ and $E_{i_{1}} = {0, 2}$ . Then for every 2-coloring c of $N$ and every sufficiently large s, at least one of the three sets $E_{i_{0}} + s$ , $E_{i_{1}} + s$ , and $E_{i_{0}} + (s + 1)$ is homogeneous for c, since otherwise the colors $c (s), c (s + 1)$ , and $c (s + 2)$ are pairwise distinct, contradicting the assumption that c is a 2-coloring. Hence, for some $j ⩽ 1$ , there are infinitely many s such that $E_{i_{j}} + s$ is homogeneous. Even if we increase the $k_{i}$ ’s, overlaps between sets $E_{i} + s$ for different values of i and s can cause problems in defining c. The only way we know to deal with more than one value of i is to use some version of the Lovász Local Lemma as described below.

To implement this idea, we think of the bits $c (k)$ as mutually independent random variables with the values 0 and 1 each having probability $\frac{1}{2}$ . If $E_{i}$ is large, then the event that $E_{i} + s$ is homogeneous for c has low probability, namely $2^{- | E_{i} | + 1}$ . Furthermore, the events that $E_{i} + s$ is homogeneous and that $E_{j} + t$ is homogeneous are independent whenever s and t are far apart enough that $E_{i} + s$ and $E_{j} + t$ are disjoint. So what we need is a theorem saying that when we have events with sufficiently small probability that are somehow sufficiently independent, then it is possible to avoid all of them at once. That is exactly what the Lovász Local Lemma does.

However, this is not enough, because we need c to be computable. Thus we need an effective version of the Lovász Local Lemma. Fortunately, such a result has been obtained by Rumyantsev and Shen [16,17], as we describe in the next section. As we will see in Section 3, this result allows us to show easily that our desired computable c exists. Indeed, by computably approximating finite subsets $E_{i}$ of $Σ_{2}^{0}$ sets, we will be able not only to avoid computable solutions to c, but also to ensure that all solutions to c have DNC degree relative to $\emptyset^{'}$ .

Murakami, Yamazaki, and Yokoyama [15] defined a class of principles that includes the principles ${HT}_{k}^{= n}$ as special cases. For a function $f : {[N]}^{n} \to N$ , let ${RT}_{k}^{f}$ be the following statement: For any $c : N \to k$ , there is an infinite set $H \subseteq N$ such that if $s, t \in {[H]}^{n}$ then $c (f (s)) = c (f (t))$ . Let ${RT}^{f}$ be the principle $\forall k {RT}_{k}^{f}$ . Notice that if $f ({x_{0}, \dots, x_{n - 1}}) = x_{0} + \dots + x_{n - 1}$ then ${RT}_{k}^{f}$ is just ${HT}_{k}^{= n}$ . As shown in [15], if $f : {[N]}^{n} \to N$ is a bijection then ${RT}_{k}^{f}$ is equivalent over RCA₀ to ${RT}_{k}^{n}$ , and ${RT}_{k}^{n}$ is also equivalent to the statement that ${RT}_{k}^{f}$ holds for all $f : {[N]}^{n} \to N$ (and hence implies ${RT}_{k}^{f}$ for any particular such f).

The reason this definition appears in [15] is that the authors were considering versions of a principle known as the Ramseyan Factorization Theorem, and they showed that one of these versions is equivalent to ${RT}^{Subt}$ for the function $Subt ({x_{0}, x_{1}}) = | x_{0} - x_{1} |$ . They proved that ${RT}^{Subt}$ implies $B Σ_{2}^{0}$ over RCA₀, with a proof that also applies to ${HT}^{= 2}$ , and indeed to any ${HT}^{f}$ such that the image of an infinite set under f remains infinite. They left open whether ${RT}_{k}^{Subt}$ is provable in RCA₀, implies ${RT}_{k}^{2}$ , or is somewhere in between these extremes.

As we will see, our results hold for ${RT}_{2}^{Subt}$ as well, and indeed for ${RT}_{2}^{f}$ for any function satisfying the following definition.

Definition 1.1.
A function $f : {[N]}^{2} \to N$ is addition-like if
f is computable,

there is a computable function g such that if $y > g (x, n)$ then $f ({x, y}) > n$ , and

there is a b such that for all $x \neq y$ , there are at most b many z’s for which $f ({x, z}) = f ({x, y})$ .

We will finish the paper with some open questions, but would like to highlight the following open-ended one here.
Question 1.2.
What further uses do the Lovász Local Lemma and other probabilistic results have in the reverse-mathematical and computability-theoretic analysis of combinatorial principles?

One example has already been given by Liu, Monin, and Patey [13]. Another appears in Cholak, Dzhafarov, Hirschfeldt, and Patey [3].
2. The Lovász Local Lemma and its computable version

The Lovász Local Lemma was introduced in Erdős and Lovász [5]. It is a major tool in obtaining lower bounds for finite Ramsey numbers. See [6, Section 4.2] for a proof and some applications of the Lovász Local Lemma. The version that we need, known as the Asymmetric Lovász Local Lemma, first appeared in Spencer [18]. It is usually stated in a finite version, but the infinite version below follows easily from the finite one by a compactness argument, as pointed out in Proposition 3 of [17].

Let $x_{0}, x_{1}, \dots$ be a sequence of mutually independent random variables, such that each $x_{j}$ has a finite range, say ${0, \dots, f (j)}$ . Let $A_{0}, A_{1}, \dots$ be events such that each $A_{j}$ depends only on the variables $x_{n}$ for n in some finite set $vbl (A_{j})$ . Thus each event $A_{j}$ is a Boolean combination of statements of the form $x_{n} = k$ for $n \in vbl (A_{j})$ and $k ⩽ f (n)$ . We can think of $A_{j}$ as a finite set $S_{j}$ of functions with domain $vbl (A_{j})$ such that if $g \in S_{j}$ then $g (n) ⩽ f (n)$ for all $n \in vbl (A_{j})$ . An assignment of the $x_{n}$ is just a function $h : N \to N$ such that $h (n) ⩽ f (n)$ for all n. This assignment avoids $A_{j}$ if the restriction of h to $vbl (A_{j})$ is not in $S_{j}$ . Let $N (A_{j}) = {A_{t} : vbl (A_{t}) \cap vbl (A_{j}) \neq \emptyset}$ , and assume that each $N (A_{j})$ is finite. Then we have the following.

Asymmetric Lovász Local Lemma, Infinite Version.
Suppose the above hypotheses hold and there exist $r_{0}, r_{1}, \dots \in (0, 1)$ such that $\begin{matrix} Pr [A_{j}] ⩽ r_{j} \cdot \prod_{\begin{array}{c} A_{t} \in N (A_{j}) \\ t \neq j \end{array}} (1 - r_{t}) \end{matrix}$ for all j. Then there is an assignment of $x_{0}, x_{1}, \dots$ that avoids every $A_{j}$ .

Moser and Tardos [14] gave an efficient algorithm for finding such an assignment for $x_{0}, x_{1}, \dots, x_{n - 1}$ in the finite version of this theorem. As noted in [17], Fortnow then conjectured that an effective version of the theorem should also hold. This conjecture was confirmed as follows.

Let $x_{0}, x_{1}, \dots$ and $A_{0}, A_{1}, \dots$ be as above. Assume that the function f bounding the ranges of the $x_{n}$ is computable, and that the $x_{n}$ have uniformly computable rational-valued probability distributions. Assume also that the $A_{j}$ are uniformly computable (i.e., that there is a computable procedure that, given j, returns $vbl (A_{j})$ and the set $S_{j}$ as above). The assumption that each $N (A_{j})$ is finite means that each n is in $vbl (A_{j})$ for only finitely many j. Assume that we have a procedure for computing a canonical index of this finite set given j. The following result is the effective version of the Lovász Local Lemma, whose proof first appeared in Rumyantsev [16] and was subsequently published in Rumyantsev and Shen [17]. Note that the hypothesis of the effective version is a bit stronger than that of the original version, as the upper bound on $Pr [A_{j}]$ in the original version is multiplied by the factor $q < 1$ to obtain the upper bound in the effective version.
Theorem 2.1 (Rumyantsev and Shen [16,17]).

Suppose the above hypotheses hold and there are $q \in Q \cap (0, 1)$ and a computable sequence $r_{0}, r_{1}, \dots \in Q \cap (0, 1)$ such that $\begin{matrix} Pr [A_{j}] ⩽ q r_{j} \cdot \prod_{\begin{array}{c} A_{t} \in N (A_{j}) \\ t \neq j \end{array}} (1 - r_{t}) \end{matrix}$ for all j. Then there is a computable assignment of $x_{0}, x_{1}, \dots$ that avoids every $A_{j}$ .

The following consequence of this result is a slightly restated version of one given in [17, Corollary 7.2]. For a finite partial function σ, the size of σ is $| dom (σ) |$ . When we say that a sequence $σ_{0}, σ_{1}, \dots$ of finite partial functions is computable, we mean that there is a computable procedure that, given i, returns $dom (σ_{i})$ and the values of $σ_{i}$ on this domain.

Corollary 2.2 (Rumyantsev and Shen [17]).

For each $q \in (0, 1)$ there is an M such that the following holds. Let $σ_{0}, σ_{1}, \dots$ be a computable sequence of finite partial functions $N \to 2$ , each of size at least M. Suppose that for each $m ⩾ M$ and n, there are at most $2^{q m}$ many j such that $σ_{j}$ has size m and $n \in dom (σ_{j})$ , and that we can computably determine the set of all such j given m and n. Then there is a computable $c : N \to 2$ such that for each j there is an $n \in dom (σ_{j})$ with $c (n) = σ_{j} (n)$ .

From this result it is easy to conclude the following fact, which is the one we will use in the next section. To obtain it, apply Corollary 2.2 to the sequence $σ_{0}, σ_{1}, \dots$ , where $σ_{2 j}$ and $σ_{2 j + 1}$ each have domain $F_{j}$ , and $σ_{2 j} (x) = 0$ and $σ_{2 j + 1} (x) = 1$ for all $x \in F_{j}$ , choosing q in Corollary 2.2 to be greater than the given q for Corollary 2.3 below.

Corollary 2.3.
For each $q \in (0, 1)$ there is an M such that the following holds. Let $F_{0}, F_{1}, \dots$ be a computable sequence of finite sets, each of size at least M. Suppose that for each $m ⩾ M$ and n, there are at most $2^{q m}$ many j such that $| F_{j} | = m$ and $n \in F_{j}$ , and that we can computably determine a canonical index for the set of all such j given m and n. Then there is a computable $c : N \to 2$ such that for each j the set $F_{j}$ is not homogeneous for c.

3. The effective content of ${HT}_{2}^{= 2}$ and some generalizations

The next result will be considerably generalized in Theorem 3.3. Nonetheless, we include it here to illustrate an application of Corollary 2.3 in a simple context. The proof of Theorem 3.3 will have the same basic idea but will also involve computable approximations to $Σ_{2}^{0}$ sets and addition-like functions replacing addition.

Theorem 3.1.
The principle ${HT}_{2}^{= 2}$ is not computably true. That is, it has a computable instance with no computable solution.
Proof.
We follow the outline of the proof given in the introduction. Let M be as in Corollary 2.3 for $q = \frac{1}{2}$ , where we assume without loss of generality that $m ⩽ 2^{\frac{m}{2}}$ for all $m ⩾ M$ . For each i, let $k_{i} = M + i$ . For each i with $| W_{i} | ⩾ k_{i}$ , let $E_{i}$ consist of the first $k_{i}$ many elements enumerated into $W_{i}$ , and let $E_{i}$ be undefined if $| W_{i} | < k_{i}$ . Let $F_{0}, F_{1}, \dots$ be a computable enumeration without repetitions of all finite sets of the form $E_{i} + s$ (over all $i, s \in N$ ) such that $W_{i}$ contains at least $k_{i}$ many elements by stage s (so that $E_{i}$ is known by stage s). Clearly, if $E_{i}$ is defined, then for all sufficiently large s the set $E_{i} + s$ occurs in the sequence $F_{0}, F_{1}, \dots$ , and conversely, every set in the sequence $F_{0}, F_{1}, \dots$ of cardinality $k_{i}$ has the form $E_{i} + s$ for some s.

As explained in the introduction, it suffices to show that Corollary 2.3 applies to the sequence $F_{0}, F_{1}, \dots$ , since this corollary then gives the existence of a computable coloring $c : N \to 2$ such that no $F_{j}$ is homogeneous for c. It follows that for all i with $E_{i}$ defined, if s is sufficiently large then $E_{i} + s$ is not homogeneous for c, so no solution to c can contain $E_{i}$ , and in particular $W_{i}$ is not a solution to c.

We now verify that the hypotheses of Corollary 2.3 are satisfied. Let $m ⩾ M$ and n be given. We claim that there are at most m many values of j such that $| F_{j} | = m$ and $n \in F_{j}$ . Let $i = m - M$ , so that $| E_{i} | = k_{i} = m$ . The claim asserts that there are most m many values of s such that $E_{i} + s$ occurs in the sequence $F_{0}, F_{1}, \dots$ and $n \in E_{i} + s$ . If $n \in E_{i} + s$ , then $n = x + s$ for some $x \in E_{i}$ . There are m many choices for x and for each x there is a unique s with $n = x + s$ , so the claim is proved. Since $m ⩽ 2^{\frac{m}{2}}$ by the choice of M, there are at most $2^{\frac{m}{2}}$ many values of j such that $| F_{j} | = m$ and $n \in F_{j}$ . It remains to check that the set of such j can be effectively computed from m and n. Again, let $i = m - M$ . We must effectively compute the canonical index of the set S of s such that $W_{i}$ contains at least m many elements by stage s and $n \in E_{i} + s$ . If $n \in E_{i} + s$ , then $s ⩽ n$ . So for each $s ⩽ n$ we can check effectively whether $W_{i}$ contains at least m many elements by the end of stage s. If not, $s \notin S$ . If so, we can effectively compute $E_{i}$ and then effectively determine whether $n \in E_{i} + s$ , and hence whether $s \in S$ . Hence, we can apply Corollary 2.3 as described in the previous paragraph. □

A function f is diagonally noncomputable (DNC) relative to an oracle X if $f (e) \neq Φ_{e}^{X} (e)$ for all e such that $Φ_{e}^{X} (e)$ is defined, where $Φ_{e}$ is the eth Turing functional. A degree is DNC relative to X if it computes a function that is DNC relative to X. An infinite set A is effectively immune relative to X if there is an X-computable function f such that if $W_{e}^{X} \subseteq A$ then $| W_{e}^{X} | < f (e)$ , where $W_{e}$ is the eth enumeration operator.
Theorem 3.2 (Jockusch [11]).

A degree is DNC relative to X if and only if it computes a set that is effectively immune relative to X.

Let $W_{0}^{\emptyset^{'}}, W_{1}^{\emptyset^{'}}, \dots$ be an effective list of the $Σ_{2}^{0}$ sets, with corresponding computable approximations $W_{i}^{\emptyset^{'}} [s]$ (chosen so that $x \in W_{i}^{\emptyset^{'}}$ iff for all sufficiently large s, we have $x \in W_{i}^{\emptyset^{'}} [s]$ ). We adopt the standard convention that if $x \in W_{i}^{\emptyset^{'}} [s]$ then $x < s$ . For a function $f : {[N]}^{2} \to N$ and $x \neq y$ , we write $f (x, y)$ for $f ({x, y})$ . For a set $S ∌ y$ , we write $f (S, y)$ for ${f (x, y) : x \in S}$ .

It follows from the proof of Theorem 3.1 that there is a computable instance of ${HT}_{2}^{= 2}$ such that all solutions are effectively immune relative to ∅, and hence have degrees that are DNC relative to ∅. In the following theorem, which is our main result, we replace ∅ by $\emptyset^{'}$ as an oracle and simultaneously replace addition by an arbitrary addition-like operation as defined in Definition 1.1.

Theorem 3.3.
Let f be addition-like. There is a computable instance of ${RT}_{2}^{f}$ such that the degree of any solution is DNC relative to $\emptyset^{'}$ .
Proof.
Let b be a constant witnessing that f is addition-like, as in part (3) of Definition 1.1. Note that the fact that f is addition-like implies that if F is a finite set and $x \notin F$ , then for all but finitely many y, we have $min f (F, y) > max f (F, x)$ . Let M be as in Corollary 2.3 for $q = \frac{1}{2}$ . We may assume that $M > 0$ and M is sufficiently large so that $b m^{2} ⩽ 2^{\frac{m}{2}}$ for all $m ⩾ M$ .

Given i and s, for each $x \in W_{i}^{\emptyset^{'}} [s]$ , let $t_{x}$ be the least t such that $x \in W_{i}^{\emptyset^{'}} [u]$ for all $u \in [t, s]$ . (I.e., $t_{x}$ measures how long x has been in $W_{i}^{\emptyset^{'}}$ .) Order the elements of $W_{i}^{\emptyset^{'}} [s]$ by letting $x ≺ y$ if either $t_{x} < t_{y}$ or both $t_{x} = t_{y}$ and $x < y$ . Let $E_{i} [s]$ be the set consisting of the least $b (M + i)$ many elements of $W_{i}^{\emptyset^{'}} [s]$ under this ordering, or $E_{i} [s] = \emptyset$ if $W_{i}^{\emptyset^{'}} [s]$ has fewer than $b (M + i)$ many elements.1
¹
This definition could be simplified by noting that there is a partial $\emptyset^{'}$ -computable function ψ such that if $| W_{i}^{\emptyset^{'}} | ⩾ b (M + i)$ then $ψ (i)$ is the canonical index of a set $E_{i} \subseteq W_{i}^{\emptyset^{'}}$ such that $| E_{i} | = b (M + i)$ . The limit lemma then gives us a computable binary function g such that $ψ (i) = {lim}_{s} g (i, s)$ for all i such that $ψ (i)$ is defined, and we can define $E_{i} [s]$ to be the set with canonical index $g (i, s)$ if this set has size $b (M + i)$ , and $E_{i} [s] = \emptyset$ otherwise. However, the current definition will make it easier to describe the adaptation of this proof to one over RCA₀ in the next section.

The following properties of this definition are the ones that matter to us:
The function taking i and s to $E_{i} [s]$ is computable.

Every element of $E_{i} [s]$ is less than s, so $f (E_{i} [s], s)$ is defined.

If $E_{i} [s] \neq \emptyset$ then $| f (E_{i} [s], s) | ⩾ M + i$ .

If $| W_{i}^{\emptyset^{'}} | ⩾ b (M + i)$ then there is a t such that $E_{i} [t] \neq \emptyset$ and $E_{i} [s] = E_{i} [t] \subseteq W_{i}^{\emptyset^{'}}$ for all $s ⩾ t$ .

We build a computable sequence of finite sets $F_{0}, F_{1}, \dots$ as follows. Order the pairs $i, s$ via a standard pairing function, and go through each such pair in order. If $E_{i} [s] = \emptyset$ then proceed to the next pair. Otherwise, let $s_{0}$ be least such that $E_{i} [t] = E_{i} [s]$ for all $t \in [s_{0}, s]$ . Suppose that the following hold.
$min f (E_{i} [s], s) > s_{0}$ .

If $u < s_{0}$ and $E_{i} [u] \neq \emptyset$ then $min f (E_{i} [s], s) > max f (E_{i} [u], u)$ .
Then add $f (E_{i} [s], s)$ to our sequence. We say that $f (E_{i} [s], s)$ was enumerated into our sequence by i. Otherwise do nothing. In any case, proceed to the next pair.

Notice that if there is an $s_{0}$ such that $E_{i} [s] = E_{i} [s_{0}] \neq \emptyset$ for all $s ⩾ s_{0}$ , then we add $f (E_{i} [s], s)$ to our sequence for all sufficiently large s, because for each $u < s_{0}$ and $n ⩽ max f (E_{i} [u], u)$ , there are only finitely many s such that $n \in f (E_{i} [s_{0}], s)$ , and similarly for each $n ⩽ s_{0}$ .

Now $F_{0}, F_{1}, \dots$ is a computable sequence of finite sets, each of size at least M. Suppose that $n \in F_{j}$ and $| F_{j} | = m$ . Then $F_{j}$ was enumerated by some $i < m$ . (Actually $i ⩽ m - M$ .) If n is also in $F_{l}$ and $F_{l}$ was also enumerated by i, then we must have $F_{j} = f (E_{i} [s], s)$ and $F_{l} = f (E_{i} [t], t)$ for some s and t such that $E_{i} [t] = E_{i} [s]$ . For each $x \in E_{i} [s]$ , there are at most b many t such that $f (x, t) = n$ , so there are at most $b m$ many such l. Thus the total number of elements of size m in our sequence that contain n is at most $b m^{2} ⩽ 2^{\frac{m}{2}}$ .

By part (2) of Definition 1.1, given n and m, we can computably determine a stage $s ⩾ n$ such that for each $i < m$ and $t ⩾ s$ , we have $min f (E_{i} [n], t) > n$ . It follows from the definition of our sequence that if F is enumerated into it a stage at which we are working with a pair $i, t$ with $i < m$ and $t ⩾ s$ , then $min F > n$ . So we can compute the set of all j such that $| F_{j} | = m$ and $n \in F_{j}$ .

Thus the hypotheses of Corollary 2.3 are satisfied, and hence there is a computable c as in that corollary. Suppose that $| W_{i}^{\emptyset^{'}} | ⩾ b (M + i)$ . Then there is an $F \subseteq W_{i}^{\emptyset^{'}}$ such that $f (F, s)$ is in our sequence for all sufficiently large s. For each such s, there are $x, y \in F$ such that $c (f (x, s)) \neq c (f (y, s))$ , so F cannot be contained in a solution to c as an instance of ${RT}_{2}^{f}$ . Thus, if H is a solution to c and $W_{i}^{\emptyset^{'}} \subseteq H$ , then $| W_{i}^{\emptyset^{'}} | < b (M + i)$ , which means that H is effectively immune relative to $\emptyset^{'}$ , and so has DNC degree relative to $\emptyset^{'}$ . □

The computable instance c constructed above cannot have any $Σ_{2}^{0}$ solutions, since no $Σ_{2}^{0}$ set is effectively immune relative to $\emptyset^{'}$ . Thus we have the following fact, whose analogs for ${RT}_{2}^{2}$ and HT were proved by Jockusch [10] and Blass, Hirst, and Simpson [1], respectively.
Corollary 3.4.
Let f be addition-like. There is a computable instance of ${RT}_{2}^{f}$ with no $Σ_{2}^{0}$ solution.

In particular, both ${HT}_{2}^{= 2}$ and ${RT}_{2}^{Subt}$ have computable instances with no $Σ_{2}^{0}$ solutions. On the other hand, every computable instance of ${HT}_{2}^{= 2}$ does have a $Π_{2}^{0}$ solution since the corresponding result holds for ${RT}_{2}^{2}$ by [10].

Every principle ${RT}_{2}^{f}$ has the form $\forall X [Θ (X) \to \exists Y (Y is infinite and Ψ (X, Y))]$ where Ψ is $Π_{1}^{0}$ . Thus we can obtain a further result from the following general fact. Lemma 3.5.
Let P be a principle of the form $\begin{matrix} \forall X [Θ (X) \to \exists Y (Y is infinite and Ψ (X, Y))] \end{matrix}$ where Ψ is $Π_{1}^{0}$ . Suppose that P has a computable instance X with no low solution. Then every solution to X is hyperimmune.
Proof.
Assume for a contradiction that X has a solution Y that is not hyperimmune. Let $F_{0}, F_{1}, \dots$ be a computable sequence of pairwise disjoint finite sets such that $Y \cap F_{i} \neq \emptyset$ for all i. Let $C$ be the collection of all Z such that $Ψ (X, Z)$ holds and $Z \cap F_{i} \neq \emptyset$ for all i. Then $C$ is a $Π_{1}^{0}$ class, and is nonempty as it contains Y. By the Low Basis Theorem, $C$ has a low element. This element is a solution to X, contradicting the choice of X. □
Corollary 3.6.
Let f be addition-like. There is a computable instance of ${RT}_{2}^{f}$ such that all solutions are hyperimmune.

4. The logical strength of ${HT}_{2}^{= 2}$ and generalizations

As mentioned above, ${RT}_{k}^{2}$ implies ${RT}_{k}^{f}$ for every $f : {[N]}^{2} \to k$ , but does not imply WKL₀. Since WKL₀ has an ω-model consisting entirely of $Δ_{2}^{0}$ sets, we have the following.

Corollary 4.1.
Let f be addition-like. Then ${RT}_{k}^{f}$ is incomparable with ${WKL}_{0}$ over ${RCA}_{0}$ .

In particular, both ${HT}_{k}^{= 2}$ and ${RT}_{k}^{Subt}$ are incomparable with ${WKL}_{0}$ over ${RCA}_{0}$ .

Theorem 3.3 also has a reverse-mathematical version. For the purposes of reverse mathematics, we should alter the definition of addition-like function to remove the computability requirements. In other words, $f : {[N]}^{2} \to N$ is addition-like in the sense of reverse mathematics if there is a function g such that if $y > g (x, n)$ then $f (x, y) > n$ , and there is a b such that for all $x \neq y$ , there are at most b many z’s for which $f (x, z) = f (x, y)$ .

We also need to be careful in defining the reverse-mathematical analog of the notion of being DNC over the jump, since the existence of the jump cannot be proved in RCA₀. Given a set X, we can of course approximate $X^{'}$ , so we can define $Φ_{e}^{X^{'}} (x) [s]$ as usual. We adopt the convention that if $Φ_{e}^{X^{'}} (x) [s] ↓$ with use u and $X^{'} [s + 1] ↾ u \neq X^{'} [s] ↾ u$ , then $Φ_{e}^{X^{'}} (x) [s + 1] ↑$ . We now define $Φ_{e}^{X^{'}} (x) = y$ to mean that $\exists t \forall s ⩾ t [Φ_{e}^{X^{'}} (x) [s] = y]$ . We write $Φ_{e}^{X^{'}} (x) \neq y$ to mean that either $Φ_{e}^{X^{'}} (x) ↑$ or $Φ_{e}^{X^{'}} (x) = z$ for $z \neq y$ . We write $n \in W_{e}^{X^{'}}$ to mean that $\exists t \forall s ⩾ t [n \in W_{e}^{X^{'}} [s]]$ , where $W_{i}^{X^{'}} [s] = {n < s : Φ_{e}^{X^{'}} (n) [s] ↓}$ .

Now 2-DNC is the statement that for every X, there is a function h such that $h (e) \neq Φ_{e}^{X^{'}} (e)$ for all e.

Inspecting the proofs of Theorem 2.1 and Corollary 2.2 in [17], we see that they can be carried out in RCA₀. Thus we can obtain the following analog of Corollary 2.3.
Corollary 4.2.
The following is provable in ${RCA}_{0}$ : For each $q \in (0, 1)$ there is an M such that the following holds. Let $F_{0}, F_{1}, \dots$ be a sequence of finite sets, each of size at least M. Suppose that for each $m ⩾ M$ and n, there are at most $2^{q m}$ many i such that $| F_{i} | = m$ and $n \in F_{i}$ , and that there is a function taking m and n to the set of all such i. Then there is a $c : N \to 2$ such that for each i the set $F_{i}$ is not homogeneous for c.

The proof of Theorem 3.3, relativized to a given oracle X, can now be carried out in RCA₀, except for one issue: In the absence of $Σ_{2}^{0}$ -bounding, it is possible to have $b (M + i)$ many n such that $n \in W_{i}^{X^{'}}$ without having a single s such that $| W_{i}^{X^{'}} [s] | ⩾ b (M + i)$ . In this case, we would have $E_{i} [s] = \emptyset$ for all s.

To get around this issue, we do not attempt to establish effective immunity relative to $X^{'}$ , but work instead with a modified notion. Write $‖ W_{e}^{X^{'}} ‖ ⩾ m$ to mean that there are a finite set F with $| F | ⩾ m$ and a t such that $n \in W_{e}^{X^{'}} [s]$ for all $n \in F$ and $s ⩾ t$ . Now 2-EI is the statement that for each X, there are an infinite set A and a function f such that if $‖ W_{e}^{X^{'}} ‖ ⩾ f (e)$ , then there is an $n \in W_{e}^{X^{'}}$ with $n \notin A$ .

The proof of Theorem 3.3, relativized to an arbitrary X, shows that if f is addition-like then ${RT}_{2}^{f}$ implies 2-EI over RCA₀. The main point to notice in that proof is the following: Suppose that $‖ W_{i}^{X^{'}} ‖ ⩾ b (M + i)$ . By definition, there are F and t such that $| F | ⩾ b (M + i)$ and $n \in W_{i}^{X^{'}} [s]$ for all $n \in F$ and $s ⩾ t$ . By bounded $Π_{1}^{0}$ -comprehension, which holds in RCA₀, we can form the set $\hat{F}$ of all $n ⩽ max F$ such that $n \in W_{i}^{X^{'}} [s]$ for all $s ⩾ t$ , and then let G be the set consisting of the $b (M + i)$ many least elements of $\hat{F}$ in the ≺-ordering defined at stage t. If $k \in W_{i}^{X^{'}} [t] ∖ G$ then there is an $s_{k} > t$ such that $k \notin W_{i}^{X^{'}} [s_{k}]$ . By $Σ_{1}^{0}$ -bounding, which holds in RCA₀, there is a u such that we can take $s_{k} ⩽ u$ for all such k. If $s ⩾ u$ , then for any $k \in W_{i}^{X^{'}} [s] ∖ G$ and any $n \in G$ , we have that $n ≺ k$ for the ordering ≺ defined at stage s. It follows that $E_{i} [s] = G$ for $s ⩾ u$ .

To obtain 2-DNC, we use the following proposition, whose proof is based on that of Theorem 3.2 given in [11]. (We need only one direction of the proposition, but the equivalence it establishes is of independent interest.)
Proposition 4.3.
$2 -EI$ is equivalent to $2 -DNC$ over ${RCA}_{0}$ .
Proof.
We argue in RCA₀. First suppose that 2-EI holds. Given X, let A and f be as in the statement of 2-EI. Write $W_{e}^{X^{'}} \approx W_{i}^{X^{'}}$ if $W_{e}^{X^{'}} [s] = W_{i}^{X^{'}} [s]$ for all sufficiently large s. Notice that in this case, for each n we have $n \in W_{e}^{X^{'}}$ iff $n \in W_{i}^{X^{'}}$ , and $‖ W_{e}^{X^{'}} ‖ ⩾ m$ iff $‖ W_{i}^{X^{'}} ‖ ⩾ m$ .

Let $n_{0} < n_{1} < \dots$ be the elements of A in order. There is a function g such that $W_{g (e)}^{X^{'}} [s] = {n_{i} < s : i < f (e)}$ for all s. Then $W_{g (e)}^{X^{'}} ≉ W_{e}^{X^{'}}$ for all e, as otherwise we would have $‖ W_{e}^{X^{'}} ‖ ⩾ f (e)$ but $n \in A$ for all $n \in W_{e}^{X^{'}}$ .

There is a function p such that $W_{p (e)}^{X^{'}} [s] = W_{y}^{X^{'}} [s]$ if $Φ_{e}^{X^{'}} (e) [s] = y$ , and $W_{p (e)}^{X^{'}} [s] = \emptyset$ if $Φ_{e}^{X^{'}} (e) [s] ↑$ . Let $h = g \circ p$ . If $Φ_{e}^{X^{'}} (e) = y$ then $W_{p (e)}^{X^{'}} \approx W_{y}^{X^{'}}$ . But $W_{h (e)}^{X^{'}} ≉ W_{p (e)}^{X^{'}}$ , since $h (e) = g (p (e))$ , so $W_{h (e)}^{X^{'}} ≉ W_{y}^{X^{'}}$ , and hence $h (e) \neq y$ . Thus h is as in the definition of 2-DNC.

Now suppose that 2-DNC holds. Given X, let h be as in the statement of 2-DNC. We first define a function g such that for each e, we have $g (e) \neq Φ_{i}^{X^{'}} (i)$ for all $i ⩽ e$ . Let $τ_{0}, τ_{1}, \dots$ list the elements of $ω^{< ω}$ . Let ${(τ)}_{i}$ be the ith element of τ if $| τ | > i$ , and let ${(τ)}_{i} = 0$ otherwise. There is a function r such that $Φ_{r (i)}^{X^{'}} (r (i)) = {(τ_{k})}_{i}$ if $Φ_{i}^{X^{'}} (i) = k$ and $Φ_{r (i)}^{X^{'}} (r (i)) ↑$ if $Φ_{i}^{X^{'}} (i) ↑$ . Let $g (e)$ be such that $| τ_{g (e)} | = e + 1$ and ${(τ_{g (e)})}_{i} = h (r (i))$ for all $i ⩽ e$ . If $i ⩽ e$ and $Φ_{i}^{X^{'}} (i) = k$ then ${(τ_{g (e)})}_{i} \neq {(τ_{k})}_{i}$ , so $g (e) \neq k$ .

Let $D_{0}, D_{1}, \dots$ list the finite sets. Order the elements of $W_{e}^{X^{'}} [s]$ as in the proof of Theorem 3.3. That is, for $x \in W_{e}^{X^{'}} [s]$ , let $t_{x}$ be the least t such that $x \in W_{e}^{X^{'}} [u]$ for all $u \in [t, s]$ , then let $x ≺ y$ if either $t_{x} < t_{y}$ or both $t_{x} = t_{y}$ and $x < y$ . There is a function q such that if $W_{e}^{X^{'}} [s] ⊈ D_{i}$ , then $Φ_{q (e, i)}^{X^{'}} (q (e, i)) [s] = n$ for the ≺-least $n \in W_{e}^{X^{'}} [s] ∖ D_{i}$ .

We now define sequences $a_{0} < a_{1} < \dots$ and $k_{0}, k_{1}, \dots$ as follows. Suppose that we have defined $a_{j}$ and $k_{j}$ for all $j < e$ . Let $i_{e}$ be such that $D_{i_{e}} = {a_{0}, \dots, a_{e - 1}}$ . Let $k_{e} = q (e, i_{e})$ . For $j ⩽ a_{e - 1}$ , let $m_{j}$ be such that $Φ_{m_{j}}^{X^{'}} (m_{j}) = j$ . Let $m = max {k_{0}, \dots, k_{e}, m_{0}, \dots, m_{a_{e - 1}}}$ and let $a_{e} = g (m)$ . Notice that $a_{e} > a_{e - 1}$ .

Let $A = {a_{0}, a_{1}, \dots}$ . This set exists because the $a_{e}$ are defined in order. Now suppose that $‖ W_{e}^{X^{'}} ‖ ⩾ e + 1$ . Then there are a finite set F with $| F | = e + 1$ and a t such that for all $s ⩾ t$ , every element of F is in $W_{e}^{X^{'}} [s]$ . Let $\begin{matrix} S = {n ⩽ max F : \exists s ⩾ t [n \notin W_{e}^{X^{'}} [s]]} . \end{matrix}$ By $Σ_{1}^{0}$ -bounding, there is a $u ⩾ t$ such that $\exists s \in [t, u] [n \notin W_{e}^{X^{'}} [s]]$ for all $n \in S$ . Let G consist of the $e + 1$ least elements of $W_{e}^{X^{'}} [u]$ under the ≺-ordering. If $s ⩾ u$ then the elements of G are also the least $e + 1$ many elements of $W_{e}^{X^{'}} [s]$ under the ≺-ordering. Since $| D_{i_{e}} | = e$ , there is an $n \in G$ such that $Φ_{q (e, i_{e})}^{X^{'}} (q (e, i_{e})) [s] = n$ for all $s ⩾ u$ , and hence $Φ_{q (e, i_{e})}^{X^{'}} (q (e, i_{e})) = n$ . By the definition of q, we have that $n \neq a_{j}$ for $j < e$ , and by construction, $n \neq a_{j}$ for $j ⩾ e$ . Thus $n \in W_{e}^{X^{'}}$ but $n \notin A$ . So A and the function $e \mapsto e + 1$ are as required by 2-EI. □

We thus have the following result.
Theorem 4.4.
${RCA}_{0}$ proves that if f is addition-like then ${RT}_{2}^{f}$ implies $2 -DNC$ .

This theorem can be understood as an implication between Ramsey-theoretic principles, because Miller [unpublished] has shown that 2-DNC is equivalent over RCA₀ to ${RRT}_{2}^{2}$ , a version of the Rainbow Ramsey Theorem that states that if $c : {[N]}^{2} \to N$ is such that $| c^{- 1} (i) | ⩽ 2$ for all i, then there is an infinite set R such that c is injective on ${[R]}^{2}$ .
Corollary 4.5.
${RCA}_{0}$ proves that if f is addition-like then ${RT}_{2}^{f}$ implies ${RRT}_{2}^{2}$ .

For those familiar with Weihrauch reducibility, we will also say that the proofs in [17] are uniform, so the c in Corollary 2.3 can be obtained uniformly from the sequence $F_{0}, F_{1}, \dots$ (for a fixed q). The proof of Theorem 3.3 is also uniform, as is the proof that computing an effectively immune set implies computing a DNC function. Thus if f is addition-like (in the original sense of Definition 1.1), then $2 -DNC ⩽_{W} {RT}_{2}^{f}$ . Miller’s aforementioned argument shows that ${RRT}_{2}^{2} ⩽_{W} 2 -DNC$ , so we also have that ${RRT}_{2}^{2} ⩽_{W} {RT}_{2}^{f}$ .
5. Open questions

We finish with some open questions. Implications here could be over RCA₀ or in the sense of notions of computability-theoretic reduction such as Weihrauch reducibility.

Question 5.1.

Does ${HT}_{2}^{= 2}$ imply ${RT}_{2}^{2}$ ?

Question 5.2.

Does ${RRT}_{2}^{2}$ imply ${HT}_{2}^{= 2}$ ?

Question 5.3.

What is the exact relationship between ${HT}_{j}^{= 2}$ and ${HT}_{k}^{= 2}$ for $j \neq k$ ?

Question 5.4.

Does either of ${HT}_{2}^{= 2}$ and ${RT}_{2}^{Subt}$ imply the other?

Jockusch [10] showed that for each $n ⩾ 2$ , there is a computable instance of ${RT}_{2}^{n}$ with no $Σ_{n}^{0}$ solution.

Question 5.5.

For $n ⩾ 3$ , is there a computable instance of ${HT}_{2}^{= n}$ with no $Σ_{n}^{0}$ solution?

A positive answer to this question would imply that HT is not provable in ACA₀, for the same reason that Jockusch’s aforementioned result implies that $RT$ (the principle $\forall n \forall k {RT}_{k}^{n}$ ) is not provable in ACA₀ (see e.g. Section 6.3 of [9]). The question is also open for ${HT}_{2}^{⩽ n}$ , and even for full HT.

Question 5.6.

Is it true that for every degree a that is DNC relative to $\emptyset^{'}$ and every computable instance c of ${HT}_{2}^{= 2}$ , there is an a-computable solution to c?

A positive answer to the above question would show that Theorem 3.3 is best possible in a strong sense.

Question 5.7.

What is the first-order strength of ${HT}_{2}^{= 2}$ ? What about ${HT}^{= 2}$ ?

Of course, analogs of the above questions can also be asked for ${RT}_{2}^{Subt}$ or ${RT}_{2}^{f}$ for other addition-like (but not bijective) functions f.

Footnotes

Acknowledgements

Csima was partially supported by Canadian NSERC Discovery Grant 312501. Dzhafarov was partially supported by grant DMS-1400267 from the National Science Foundation of the United States and a Collaboration Grant for Mathematicians from the Simons Foundation. Hirschfeldt was partially supported by grant DMS-1101458 from the National Science Foundation of the United States and a Collaboration Grant for Mathematicians from the Simons Foundation. We thank Jason Bell and Jeff Shallit for very helpful suggestions that led us to the idea of using the Lovász Local Lemma. We also thank Ludovic Patey for information on ${RRT}_{2}^{2}$ .

References

A.R.

Blass,

J.L.

Hirst and

S.G.

Simpson, Logical analysis of some theorems of combinatorics and topological dynamics, in: Logic and Combinatorics,

S.G.

Simpson, ed., Contemporary Mathematics, Vol. 65, American Mathematical Society, Providence, RI, 1987, pp. 125–156. doi:10.1090/conm/065/891245.

Carlucci,

L.A.

Kołodzieczyk,

Lepore and

Zdanowski, New bounds on the strength of some restrictions of Hindman’s Theorem, in: Unveiling Dynamics and Complexity (CiE 2017),

Kari,

Manea and

Petre, eds, Lecture Notes in Computer Science, Vol. 10307, Springer, Cham, 2017, pp. 210–220. doi:10.1007/978-3-319-58741-7_21.

P.A.

Cholak,

D.D.

Dzhafarov,

D.R.

Hirschfeldt and

Patey, Some results on the COH vs.

{SRT}_{2}^{2}

problem, To appear.

D.D.

Dzhafarov,

C.G.

JockuschJr.,

Solomon and

L.B.

Westrick, Effectiveness of Hindman’s Theorem for bounded sums, in: Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday,

Day,

Fellows,

Greenberg,

Khoussainov,

Melnikov and

Rosamond, eds, Lecture Notes in Computer Science, Vol. 10010, Springer, Cham, 2017, pp. 134–142. doi:10.1007/978-3-319-50062-1_11.

Erdős and

Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in: Infinite and Finite Sets, Vol. II,

Hajnal,

Rado and

V.T.

Sós, eds, Colloquia Mathematica Societatis János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 609–627.

R.L.

Graham,

B.L.

Rothschild and

J.H.

Spencer, Ramsey Theory, 2nd edn, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1990.

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

Hindman,

Leader and

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

D.R.

Hirschfeldt, Slicing the Truth, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, Vol. 28, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015.

10.

C.G.

JockuschJr., Ramsey’s theorem and recursion theory, The Journal of Symbolic Logic37(2) (1972), 268–280. doi:10.2307/2272972.

11.

C.G.

JockuschJr., Degrees of functions with no fixed points, in: Logic, Methodology, and Philosophy of Science VIII, Moscow, 1987,

J.E.

Fenstad,

I.T.

Frolov and

Hilpinen, eds, Studies in Logic and the Foundations of Mathematics, Vol. 126, North-Holland, Amsterdam, 1989, pp. 191–201.

12.

Liu,

{RT}_{2}^{2}

does not imply WKL₀, The Journal of Symbolic Logic77(2) (2012), 609–620. doi:10.2178/jsl/1333566640.

13.

Liu,

Monin and

Patey, A computable analysis of variable words theorems, to appear in the Proceedings of the AMS. doi:10.1090/proc/14269.

14.

R.A.

Moser and

Tardos, A constructive proof of the general Lovász Local Lemma, Journal of the ACM57(2) (2010), 11. doi:10.1145/1667053.1667060.

15.

Murakami,

Yamazaki and

Yokoyama, On the Ramseyan factorization theorem, in: Language, Life, Limits: CiE 2014,

Beckmann,

Csuhaj-Varjú and

Meer, eds, Springer, Cham, Germany, 2014, pp. 324–332.

16.

Rumyantsev, Infinite computable version of Lovász Local Lemma, arXiv:1012.0557.

17.

Rumyantsev and

Shen, Probabilistic constructions of computable objects and a computable version of Lovász Local Lemma, Fundamenta Informaticae132(1) (2014), 1–14.

18.

Spencer, Asymptotic lower bounds for Ramsey functions, Discrete Mathematics20(1) (1977/1978), 69–76. doi:10.1016/0012-365X(77)90044-9.