Damir D Dzhafarov

Jun Le Goh

Denis R Hirschfeldt

Ludovic Patey
email: ludovic.patey@computability.fr

Arno Pauly
email: a.m.pauly@swansea.ac.uk

Jun Le Goh

Ramsey's theorem and products in the Weihrauch degrees

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Reverse mathematics is a foundational area of logic devoted to calibrating the precise axioms needed to prove a given theorem of ordinary mathematics. For a standard reference, see Simpson [START_REF] Stephen | Subsystems of Second Order Arithmetic[END_REF]. A particularly fruitful line of research in this endeavor has been looking at theorems from combinatorics, particularly Ramsey's theorem and its many variants. See Hirschfeldt [START_REF] Denis | Slicing the Truth: On the Computable and Reverse Mathematics of Combinatorial Principles[END_REF] for an introduction to the area. One recent way of extending the scope of this analysis is to replace the traditional framework of reverse mathematics, which is provability in fragments of second-order arithmetic, by Weihrauch reducibility. The latter is a tool that has been widely deployed in computable analysis and complexity theory; see the recent survey article by Brattka, Gherardi, and Pauly [START_REF] Brattka | Weihrauch complexity in computable analysis[END_REF]. Recently it has gained prominence also in the study of computable combinatorics, and it is currently seeing a surge of activity; see, e.g., [1,[START_REF] Brattka | On the uniform computational content of Ramsey's theorem[END_REF][START_REF] François | On uniform relationships between combinatorial problems[END_REF][START_REF] Damir | Strong reductions between combinatorial principles[END_REF][START_REF] Damir | Ramsey's theorem for singletons and strong computable reducibility[END_REF][START_REF] Hirschfeldt | On notions of computability-theoretic reduction between Π 1 2 principles[END_REF][START_REF] Hirst | Using Ramsey's theorem once[END_REF][START_REF] Hirst | Reverse mathematics of matroids[END_REF][START_REF] Monin | Π 0 1 encodability and omniscient reductions[END_REF][START_REF] Nichols | Strong reductions between relatives of the stable Ramsey's theorem[END_REF][START_REF] Patey | Partial orders and immunity in reverse mathematics[END_REF][START_REF] Patey | The weakness of being cohesive, thin or free in reverse mathematics[END_REF]. See also Brattka [2] for an updated bibliography.

In this paper, we turn the lens of Weihrauch reducibility on various results concerning Ramsey's theorem and its products with other mathematical principles. We begin with some background on Weihrauch reducibility and Ramsey's theorem. Definition 1.1. A problem P is a partial multifunction from 2 ω to 2 ω , written P : ⊆ 2 ω ⇒ 2 ω . We call each X ∈ dom(P) an instance of P, or P-instance for short, and each Y ∈ P(X) a solution to X as an instance of P, or just a P-solution to X.

In general, a problem may be a partial multifunction between other kinds of represented spaces. We shall consider such problems in Section 4, and refer the reader to [4, Section 2] for definitions. Elsewhere in this paper, the above definition will Dzhafarov was supported by grant DMS-1400267 from the National Science Foundation of the United States and a Collaboration Grant for Mathematicians from the Simons Foundation. Goh was supported by NSF grant DMS-1161175. Hirschfeldt was supported by grant DMS-1101458 from the National Science Foundation of the United States and a Collaboration Grant for Mathematicians from the Simons Foundation. All authors thank the Leibniz-Zentrum für Informatik at Schloss Dagstuhl, where the initial work for this project was conducted.

be sufficient. (To be precise, we do work with represented spaces, since we code objects such as colorings of n-tuples of natural numbers as elements of Cantor space, but our codings are transparent enough that we can safely ignore this distinction, which we believe will improve clarity for most readers.)

We assume familiarity with standard computability-theoretic notation. For a partial function ψ, we write ψ(x) y to mean that ψ(x) is equal to y if defined.

A broad class of problems comes from reverse mathematics, where a typical object of study is a mathematical principle of the syntactic form

(∀X)[ϕ(X) → (∃Y )[θ(X, Y )]],
where ϕ and θ are arithmetical formulas of second-order arithmetic. Such a principle gives rise to the problem whose instances are the sets X such that ϕ(X) holds, and where the solutions to any such X are the Y such that θ(X, Y ) holds. In general, the formulas ϕ and θ above need not be unique for a given principle, but in practice, each principle one studies has a natural such pair of formulas associated to it. We adopt this terminology for specifying problems in this paper. Definition 1.2. Let P and Q be problems.

(1) Q is computably reducible to P, written Q c P, if every instance X of Q computes an instance X of P, such that for every solution Y to X, we have that X ⊕ Y computes a solution Y to X. (2) Q is strongly computably reducible to P, written Q sc P, if every instance X of Q computes an instance X of P, such that every solution Y to X computes a solution Y to X. (3) Q is Weihrauch reducible to P, written Q W P, if there exist Turing functionals Φ and Ψ such that for every instance X of Q, we have that Φ X is an instance of P, and for every solution Y to Φ X we have that Ψ X⊕ Y is a solution to X. (4) Q is strongly Weihrauch reducible to P, written Q sW P, if there exist Turing functionals Φ and Ψ such that for every instance X of Q, we have that Φ X is an instance of P, and for every solution Y to Φ X we have that Ψ Y is a solution to X.

We write P ≡ c Q if P c Q and Q c P, and similarly for the other reducibilities above. All of these reducibilities are transitive, so the resulting notions of equivalence are in fact equivalence relations, which yield degree structures in the usual way. Figure 1 summarizes the relationships that hold between these reducibilities. We refer the reader to Hirschfeldt and Jockusch [START_REF] Hirschfeldt | On notions of computability-theoretic reduction between Π 1 2 principles[END_REF]Section 4.1] for a more thorough discussion of these reducibilities, and for various generalizations of them with applications to reverse mathematics.

The following lists several important operations one can perform on problems.

Definition 1.3. Let P 0 and P 1 be problems.

(1) The (parallel) product of P 0 and P 1 , written P × Q, is the problem whose instances are pairs X 0 , X 1 with X i a P i -instance, and where the solutions to X 0 , X 1 are all pairs Y 0 , Y 1 with Y i a P i -solution to X i . (2) The coproduct of P 0 with P 1 , written P 0 P 1 , is the problem whose instances are all pairs i, X for i < 2 such that X is a P i -instance, and where the solutions to i, X are just the P i -solutions to X.

Definition 1.4. Let X be a subset of ω and k a positive number.

(

) [X] 2 = { x, y ∈ X × X : x < y}. (2) A k-coloring of pairs (frequently just coloring) is a function c : [ω] 2 → k. 1
We write c(x, y) instead of c( x, y ) for x, y ∈ [X] 2 . The coloring is stable if for every x there is an i < k such that c(x, y) = i for all sufficiently large y, in which case we write lim y c(x, y) = i.

(3) A set H ⊆ X is homogeneous for such a c if c [H] 2 is constant. A set Y ⊆ X is almost homogeneous for c if there is a finite set F such that Y -F is homogeneous for c. ( 4
) A set L ⊆ X is limit-homogeneous for c if there is an i < k such that c(x, y) = i for all x ∈ L and all sufficiently large y ∈ L, in which case we write lim y∈L c(x, y) = i. A set Y ⊆ X is almost limit-homogeneous for c if there is a finite set F such that Y -F is limit-homogeneous for c.

If i < k is the color witnessing that some set is homogeneous or limit-homogeneous then we say the set is homogeneous/limit-homogeneous with color i. Note that if c is stable and L is limit-homogeneous for c with color i then also lim y c(x, y) = i for all x ∈ L.

The following mathematical principles are well-known, and have been studied extensively in computability theory, reverse mathematics, and more recently, in the context of Weihrauch reducibility.

Ramsey's theorem for k-colorings of pairs (RT 2 k ). For every coloring c : [ω] 2 → k, there is an infinite homogeneous set for c. Stable Ramsey's theorem for k-colorings of pairs (SRT 2 k ). For every stable coloring c : [ω] 2 → k, there is an infinite homogeneous set for c.

∆ 0 2 k-partition subset principle (D 2 k ).
For every stable coloring c : [ω] 2 → k, there is an infinite limit-homogeneous set for c.

(So, for concreteness, the instances of RT 2 k are all colorings c : [ω] 2 → k, and the solutions to a given such c are its infinite homogeneous sets. Similarly for the other problems.) One additional principle that has been studied extensively alongside RT 2 2 and SRT 2 k is the following: Cohesive principle (COH). For every sequence c 0 , c 1 , . . . , where c i : ω → 2 for each i ∈ ω, there exists an infinite set X that is almost homogeneous for each c i .

It is an easy exercise to see that D 2 k is strongly Weihrauch equivalent to the problem asserting that for every ∆ 0 2 k-partition A 0 , . . . , A k-1 of ω, there exists an infinite subset X of some A i , and in the sequel, we will use whichever formulation is more convenient. It is obvious that D k . Note that if j < k then the version of each of the above principles for j-colorings is strongly Weihrauch reducible to the version for k-colorings. Patey [START_REF] Patey | The weakness of being cohesive, thin or free in reverse mathematics[END_REF] showed that the converse is false; in fact, if j < k, then even D 2 k c RT 2 j . Further relationships between SRT 2 2 , D 2 2 , and related principles under the various reductions from Definition 1.2 have been investigated by Nichols [START_REF] Nichols | Strong reductions between relatives of the stable Ramsey's theorem[END_REF]. Definition 1.5. For a problem P, let P fe be the problem whose instances are the same as those of P, but such that Y is a P fe -solution to X if there is a P-solution Z to X such that Y = * Z (i.e., such that Y and Z agree on a cofinite domain). Thus, for instance, (D 2 k ) fe asserts that every stable coloring c : [ω] 2 → k has an infinite almost limit-homogeneous set. For some well-behaved principles P, we can express P fe in terms of the implication operation introduced by Brattka and Pauly in [START_REF] Brattka | On the algebraic structure of Weihrauch degrees[END_REF]Section 3.3]. In lieu of a definition, we use the following property (see [START_REF] Brattka | On the algebraic structure of Weihrauch degrees[END_REF]Theorem 23]): for problems P and Q, we have

Q → P ≡ W inf W {R : P W Q R}.
We also recall the following choice principle (see [START_REF] Brattka | Weihrauch complexity in computable analysis[END_REF]Section 7]). Definition 1.6. C N is the problem whose instances are functions e : ω 2 → 2 such that • for all x, e(x, 0) = 0 and there is at most one s with e(x, s) = e(x, s + 1);

• there is at least one x with e(x, s) = 0 for all s.

A solution to such an e is any x ∈ ω such that e(x, s) = 0 for all s.

Thus the instances of C N are enumerations of sets with nonempty complements, and the solutions are the elements of these complements.

Proposition 1.7. Let P ∈ {RT 2 k , SRT 2 k }. Then P fe ≡ W C N → P. Proof. To show that P fe W C N → P, consider any R such that P W C N R. Let Φ and Ψ witness this reduction. We describe a uniform procedure for reducing P fe to R, which will prove what we want. Given a P-instance c, we use Φ to convert this to an instance X of R. Now from any R-solution Y to X, we can uniformly compute an instance Z of C N . More precisely, we obtain a uniformly Y -computable enumeration of a set Z such that Z = ∅. And given any C N -solution to Z, i.e., a point x ∈ Z, Ψ( c, x, Y ) must be a solution to P. Thus, to uniformly compute a P fe -solution H to c from a given R-solution Y to X, we proceed as follows. To determine H(n), we choose the least x not yet in our Y -computable enumeration of Z at stage n, and wait for x either to be enumerated, or for Ψ( c, x, Y ) to converge, in which case we let H(n) = Ψ( c, x, Y ). It is easy to see that H will be almost homogeneous for c.

In the other direction, by the characterization of the implication it suffices to show that P W C N P fe . Consider the following uniform procedure. Given an instance c : [ω] 2 → k of P, we regard it also as an instance of P fe . Now, given any P fe -solution Y to c, i.e., an infinite almost homogeneous set, define

Z = {x ∈ Y : (∃i < k)(∀y x)(∀z > y)[y, z ∈ Y → c(y, z) = i]}.
Note that Z agrees with Y on all but finitely many elements, and so is in particular nonempty. Moreover, Z is a Π 0,Y 1 subset of N, and hence can be passed as an instance to C N . Let x be any C N -solution to this instance. Then {y ∈ Y : y x} is a P-solution to c.

Ramsey's theorem for pairs

Our starting point is the following summary of known facts concerning relationships between RT 2 2 , SRT 2 2 , and COH under Weihrauch reducibility. Theorem 2.1.

(

) SRT 2 2 COH W RT 2 2 W SRT 2 2 COH; (2) SRT 2 2 COH W COH × SRT 2 2 W SRT 2 2 COH. Proof. That RT 2 2 W SRT 2 2 1
COH follows by the proof of Cholak, Jockusch, and Slaman [10, Theorem 12.5] that SRT 2 2 ∧ COH implies RT 2 2 in the formal system RCA 0 (see also [START_REF] François | On uniform relationships between combinatorial problems[END_REF]Section 5.2]). The remaining reductions are obvious from the definitions.

Our main motivation for this section is the following question, asked during the workshop "Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis", at the Leibniz-Zentrum für Informatik at Schloss Dagstuhl in September, 2015. Question 2.2 (Brattka, see [START_REF] Brattka | Measuring the complexity of computational content (Dagstuhl Seminar 15392)[END_REF]). What additional reductions hold between the problems in Theorem 2.1?

To answer the question, we begin by recalling some ancillary notions. Definition 2.3. Let c : [ω] 2 → k be a coloring, and let X be a set.

(1) The coloring c is unbalanced on X if for some i < k, every infinite homogeneous set for c contained in X has color i. If c is not unbalanced on X, it is balanced on X.

(2) The coloring c avoids the color i < k on X if c(x, y) = i for all x, y ∈ X.

If, in the definition above, X = ω, we shall say simply that c is unbalanced / balanced / avoids the color i, without further qualification.

The following lemma will allows us to prove our main result, from which we will derive a number of consequences, including an answer to Question 2.2.

Lemma 2.4. Let c : [ω] 2 → k be a computable coloring, A an infinite computable set, and C ⊆ 2 ω a nonempty Π 0 1 class of k-partitions of A. If, for every P 0 , . . . , P k-1 ∈ C, c is unbalanced on P j for every j < k, then c has a computable infinite homogeneous set.

Proof. Fix c and C, and suppose that c has no computable infinite homogeneous set. We construct a set G = {G i,j : i, j < k}, and exhibit a P 0 , . . . , P k-1 ∈ C, such that G i,j ⊆ P j for all i, j < k, and c avoids the color i on G i,j . We will furthermore satisfy the following requirement for each n ∈ ω and all α ∈ k k :

R n,α : (∃j < k)(∃x n)[x ∈ G α(j),j ].
The claim is that c is then balanced on some P j . For if not, define α ∈ k k by letting α(j) be the color i < k such that every infinite homogeneous set for c contained in P j has color i. Since G satisfies R n,α for all n, there must be a j < k such that G α(j),j is infinite. Let H be any infinite homogeneous set for c contained in G α(j),j . As c avoids the color α(j) on G α(j),j , it follows that H has some other color than α(j), which is a contradiction since G α(j),j ⊆ P j .

The construction of G is by a forcing notion whose conditions are tuples p = ({E i,j : i, j < k}, X, D),

such that for all i, j < k:

• E i,j is a finite subset of A;
• X is a computable infinite subset of A such that max E i,j < min X;

• for every x ∈ X, c avoids the color i on E i,j ∪ {x};

• D is a nonempty Π 0 1 subclass of C such that for every P 0 , . . .

, P k-1 ∈ D, E i,j ⊆ P j . A condition q = ({F i,j : i, j < k}, Y, E) extends p if Y ⊆ X, E ⊆ D, and E i,j ⊆ F i,j ⊆ E i,j ∪ X for all i, j < k.
Say a condition p as above satisfies R n,α if there are some j < k and some x n such that x ∈ E α(j),j . We claim that the set of conditions satisfying R n,α is dense. Fix p = ({E i,j : i, j < k}, X, D). First, suppose there are some Q 0 , . . . , Q k-1 ∈ D, some < k, and some x ∈ X ∩Q such that Y = {y ∈ X : c(x, y) = α( )} is infinite. Let q = ({F i,j : i, j < k}, Y, E), where F α( ), = E α( ), ∪ {x}, F i,j = F i,j for all i, j < k with i = α( ) or j = , and E = { P 0 , . . . , P k-1 ∈ D : x ∈ P }. Then q is an extension of p satisfying R n,α . So suppose now that there are no such Q, , and x. We derive a contradiction. The assumption implies that for every x ∈ X, lim y∈X c(x, y) exists, since given any Q 0 , . . . , Q k-1 ∈ D, we have that lim y∈X c(x, y) = α( ) for the unique with x ∈ Q . So the map g : X → k defined by g(x) = lim y∈X c(x, y) for all x ∈ X is computable from every member of D. By the cone-avoidance basis theorem (see, e.g., [START_REF] Damir | Ramsey's theorem and cone avoidance[END_REF]Theorem 2.1]), this implies that g is computable. But then c has a computable infinite homogeneous set, which we assumed it did not.

To complete the proof, let G = q 0 , q 1 , . . . be a sufficiently generic sequence on our forcing poset, where for each s, q s = ({E s i,j : i, j < k}, X s , D s ), and q s is extended by q s+1 . Define

G i,j = s∈ω E s i,j
for all i, j < k. Let P 0 , . . . , P k-1 be any element of s∈ω D s , which is an intersection of a nested sequence of Π 0 1 classes and hence is nonempty. Then G = {G i,j : i, j < k} and P 0 , . . . , P k-1 have the desired properties.

The following important problems arise frequently in the study of Weihrauch degrees.

Definition 2.5.

(1) LPO is the principle whose instances are all infinite binary sequences of the form 0 ω or 0 n 1 ω for some n ∈ ω, and the solutions are either the singleton {0} if the instance is 0 ω , or {1} if the instance is 0 n 1 ω for some n.

(2) NON is the principle whose instances are all sets, and the solutions to an instance X are all sets Y T X.

Viewed as a Π 1 2 principle, NON is thus equivalent over RCA 0 to the principle AST considered by Hirschfeldt, Shore, and Slaman [START_REF] Hirschfeldt | The atomic model theorem and type omitting[END_REF]Section 6]. (See specifically [START_REF] Hirschfeldt | The atomic model theorem and type omitting[END_REF]Theorem 6.3].) Theorem 2.6. LPO × NON W RT 2 2 . Proof. Assume otherwise, and fix functionals Φ and Ψ witnessing the reduction. We build an instance S of LPO such that the pair S, ∅ contradicts this assumption. We have that Φ S⊕∅ is a coloring [ω] 2 → 2, and for every infinite homogeneous set H for this coloring, Ψ S⊕∅⊕H = {b}, Y , where b is 0 or 1 depending on whether S = 0 ω or S = 0 n 1 ω for some n, and Y T ∅. (Thus, Ψ S⊕∅⊕H (0)↓ = 1 if and only if b = 0.) We show that the coloring Φ S⊕∅ necessarily has an infinite homogeneous set H satisfying one of the following properties:

(1) H is computable;

(2) Ψ S⊕∅⊕H (0) 1 and S = 0 ω ;

(3) Ψ S⊕∅⊕H (0)↓ = 0 and S = 0 n 1 ω for some n. In the first case, S ⊕ ∅ ⊕ H obviously cannot compute a solution to our NONinstance. And in the remaining cases, we have a contradiction to Ψ S⊕∅⊕H giving us a solution to our LPO-instance.

Let c be the coloring Φ 0 ω ⊕∅ : [ω] 2 → 2. Define C to be the Π 0 1 class consisting of all 2-partitions P 0 , P 1 of ω such that

(∀i < 2)(∀ finite F ⊆ P i )[(∀x, y ∈ F )[c(x, y) = i] → Ψ 0 ω ⊕∅⊕F (0) 1].
We consider two cases. First, suppose C is nonempty. By Lemma 2.4 with k = 2 and A = ω, if c is unbalanced on P 0 and P 1 for every P 0 , P 1 ∈ C, then c has a computable infinite homogeneous set. We can then take this to be H, set S = 0 ω , and satisfy Property (1) above. So assume not. Fix P 0 , P 1 ∈ C and i < 2 such that c is balanced on P i , so that in particular, P i is infinite. Let H ⊆ P i be any infinite homogeneous set for c with color i. If we then take S = 0 ω , it follows by the definition of C that Ψ S⊕∅⊕H (0) 1, so we satisfy Property (2).

So now, suppose C = ∅. By compactness, choose m so that for every partition P 0 , P 1 of ω, there are an i < 2 and a finite F ⊆ P i m such that c(x, y) = i for all x, y ∈ F and Ψ 0 ω ⊕∅⊕F (0)↓ = 0. Note that there are only finitely many such F across all possible partitions, so there is a global bound u on the uses of all these computations. Without loss of generality, u m. Choose n > u large enough so that Φ 0 n 1 ω ⊕∅ agrees with c = Φ 0 ω ⊕∅ below u. Let S = 0 n 1 ω , and let d = Φ S⊕∅ . By repeatedly taking subsets, we see that there is a computable infinite set Y > m such that for each x < m, lim y∈Y d(x, y) exists. For each i < 2, let Q i = {x < m : lim y∈Y d(x, y) = i}, so that for some partition P 0 , P 1 of ω, we have Q 0 = P 0 m and Q 1 = P 1 m. Choose i < 2 and F ⊆ Q i as above. If Y contains no infinite homogeneous set for d with color i, then Y contains a computable infinite homogeneous set with color 1 -i, and we satisfy Property (1) again. Otherwise, we can take an infinite homogeneous set H for d having F as an initial segment, and by construction, this set satisfies Ψ S⊕∅⊕H (0)↓ = 0 even though S = 0 ω . Thus, we satisfy Property (3).

Trivially, LPO W RT 1 2 , since every instance of LPO can be regarded as an instance of RT 1 2 , so we have the following. Corollary 2.7.

RT 1 2 × NON W RT 2 2 . Clearly RT 1 2 W SRT 2 2
, and there is a uniform construction of an X-computable instance of COH with no X-computable solution, so we also have the following. . We can improve on this reduction with the following strong counterpoint to Theorem 2.6, which shows that the theorem fails as soon as the number of colors is allowed to increase from two, even via a stable coloring. Proposition 2.10. LPO × NON W SRT 2 3 . Proof. Let S be an arbitrary instance of LPO, and let X be any set. Let c : [ω] 2 → 2 be the result of applying a standard uniform construction of an X-computable stable coloring c : [ω] 2 → 2 with no X-computable infinite homogeneous set (e.g., as in [START_REF] Jockusch | Ramsey's theorem and recursion theory[END_REF]Theorem 2

.1]). Define d : [ω] 2 → 3 by d(x, y) = c(x, y) if S(x) = S(y), 2 otherwise.
Clearly, d is uniformly computable from S ⊕ X. If S = 0 ω then d = c, while if S = 0 n 1 ω for some n then lim y d(x, y) = 2 for all x < n, and d(x, y) = c(x, y) for all x n. Hence, every infinite homogeneous set for d has color 0 or 1, and is also homogeneous for c. In particular, no infinite homogeneous set for d is Xcomputable. Moreover, we have that S = 0 n 1 ω if and only if (∃x min H)[S(x) = 1]. Hence, {b}, H , where b is 0 or 1 depending as S = 0 ω or S = 0 n 1 ω for some n, is a uniformly (S ⊕ X ⊕ H)-computable solution to the LPO × NON-instance S, X .

We do not know whether SRT 2 3 above can be replaced by D 2 3 . However, we have the following related result, which does work for D 2 3 . The proof uses a novel coding mechanism.

Theorem 2.11. For every k 1, (RT 1 k ) fe × NON W D 2 k+1 . Proof. Let c : ω → k be a coloring and X a set. We describe a uniform procedure to define an X-computable stable coloring d : [ω] 2 → k + 1 with no X-computable solution (i.e., no X-computable infinite limit-homogeneous set), and a uniform procedure for turning any such solution into an almost limit-homogeneous set for c. Fix a canonical (c ⊕ X)-computable enumeration of (c ⊕ X) , and let

s 0 < s 1 < • • • be a (c ⊕ X)
-computable sequence such that for all e, we have that (c ⊕ X) [s e ] and (c ⊕ X) agree on all x e. Using (c ⊕ X) , choose

x 0,0 < x 0,1 < x 1,0 < x 1,1 < x 2,0 < x 2,1 < • • •
with x e+1,0 -x e,1 s e for all e, and such that either Φ X e (x e,0 )↓ = Φ X e (x e,1 )↓ = 1, or Φ X e (x) 0 for all sufficiently large x. Now define a (c ⊕ X) -computable (k + 1)-partition P 0 ∪ • • • ∪ P k of ω as follows.

For each e, put x e,0 into P k , and put every other x into P c(x) . Thus, for all e, we have that x e,0 and x e,1 belong to different parts of the partition, so by construction, if Φ X e defines an infinite set, this set cannot be an infinite subset of any P i . We also have that if

z 0 < • • • < z n-1 ∈ P k then z e+1 -z e
s e for all e < n, so any infinite subset of P k computes (c ⊕ X) . We can regard P 0 ∪ • • • ∪ P k as a (c ⊕ X)computable stable coloring d. Clearly, d is defined uniformly from X and c, and no infinite limit-homogeneous set for d is X-computable.

Consider any D 2 k+1 -solution to d, i.e., any infinite set Z = {z 0 < z 1 < • • • } contained in one of P 0 , . . . , P k . We construct a set Y = {y 0 < y 1 < • • • } inductively by stages, defining y n at stage n. At any stage, we may choose to exit the construction, which simply means to let m be the maximum of all y n defined thus far, and let the rest of our set be {z n ∈ Z : z n > m}. At stage n = 0, let y 0 = 0, and declare no color i < k forbidden. If we have not exited the construction by stage n + 1, assume we have defined y n and there is at least one i < k that is still not forbidden. For the least such i, we compute a number e such that e ∈ (c ⊕ X) if and only if (∃y > y n )[c(y) = i], which we can do uniformly from y n , the color i, and an index for c as a (c ⊕ X)-computable coloring. If e ∈ (c ⊕ X) [z e+1 -z e ] then certainly e ∈ (c ⊕ X) , so we can find a y > y n with c(y) = i, and we let y n+1 be the least such y. If e / ∈ (c ⊕ X) [z e+1 -z e ], we declare i forbidden and restart the process with the next smallest non-forbidden color. In this case, we promise that if at any future stage we see a y > y n with c(y) = i, we exit the construction. Note that this can happen only if z e+1 -z e < s e . Note also that it must happen if all i < k become forbidden.

It is easy to see that Y is uniformly computable from c ⊕ X ⊕ Z. We claim that Y is almost limit-homogeneous for c. This is clear if we never exit the construction, because in that case there must be some least i that is never declared forbidden, and then c(y n ) = i for almost all n. If, on the other hand, we do exit the construction, then as noted above we must have z e+1 -z e < s e for some e, and hence Z cannot be a subset of P k . In this case, Z is therefore a subset of P i for some i < k, and by construction, if x ∈ P i for such an i then c(x) = i. As Y = * Z, it follows that Y is almost limit-homogeneous for c.

Stable Ramsey's theorem for pairs

As mentioned above, every instance of LPO can be regarded as an instance of RT 1 2 . The latter instance, however, is consequently unbalanced. It is interesting to ask whether this is the only possible reduction, or whether LPO can in fact be reduced to RT 1 2 via a balanced coloring. The following proposition shows that the answer is no. It also points to an additional point of disagreement in the uniform strengths of SRT 2 2 and D 2 2 , to complement the aforementioned result that

SRT 2 2 W D 2
k for all k. We first give a definition. Thus, if S = 0 ω then lim y c(x, y) = par(x) for all x, and if S = 0 n 1 ω for some n then lim y c(x, y) = 1 -par(x) for all x. In either case, for each i < 2, there are infinitely many x with lim y c(x, y) = i, so c is balanced. Now, every element in an infinite homogeneous set for c has the same parity. So if H is any such homogeneous set, and if x 0 and x 1 are its least two elements, then S = 0 ω if and only if c(x 0 , x 1 ) = par(x 0 ). Thus, we have the desired uniform reduction.

Definition 3.1. For P ∈ {RT 1 k , SRT 2 k , D 2 k },
For the negative reduction, assume towards a contradiction that

LPO W b-D 2 k via some Φ and Ψ. Then c = Φ 0 ω is a computable balanced stable coloring [ω] 2 → k. Define C to be the Π 0 1 class of all partitions P 0 , . . . , P k-1 of ω such that (∀i < k)(∀ finite F ⊆ P i )[Ψ 0 ω ⊕F (0) 1].
First, we claim that C = ∅. Otherwise, by compactness, there is an m such that for every partition P 0 , . . . , P k-1 of ω, there are an i < k and a finite F ⊆ P i m such that Ψ 0 ω ⊕F (0)↓ = 0. Let u m be a bound on the uses of all these computations, for all possible such F . Choose n > u large enough so that Φ 0 n 1 ω and c = Φ 0 ω agree below u. Let S = 0 n 1 ω and d = Φ S , which is another balanced stable coloring. For the partition P 0 , . . . , P k-1 of ω given by P i = {x : lim y d(x, y) = i}, fix i < k and F ⊆ P i m as above. As d is balanced, there is an infinite homogeneous set H for d with color i that has F as an initial segment. But then we have Ψ S⊕H (0)↓ = 1 even though S = 0 ω , a contradiction. So C = ∅. Choose any P 0 , . . . , P k-1 ∈ C. Since P 0 ∪ • • • ∪ P k-1 = ω, there is an i < k such that P i is infinite. Let L be any infinite limit-homogeneous set for c contained in P i . Then Ψ 0 ω ⊕L (0) 1, which contradicts the choice of Ψ.

Corollary 3.3. LPO W b-RT 1 k for all k. Proof. The usual proof that RT 1 k W D 2 k shows that b-RT 1 k W b-D 2 k .
One generalization of the notion of unbalanced coloring is the following, in which merely one of the possible colors of homogeneous set-rather than, all but one-is omitted.

Definition 3.4. Let c : [ω] 2 → k be a coloring and X a set. The coloring c is thin-unbalanced on X if for some i < k, there is no infinite homogeneous set for c contained in X with color i. The color i is called a witness of thin-unbalancing for c on X. If c is not thin-unbalanced on X, it is thin-balanced on X.

When X = ω, we shall simply say c is thin-unbalanced / thin-balanced. Note that if k = 2, then c is thin-unbalanced on a set if and only if it is unbalanced on that set in the sense of Definition 2.3, which in turn holds if and only if c avoids one of its two colors on that set. Definition 3.5. For P ∈ {SRT 2 k , D 2 k }, we define the following variations on P: • ∆ 0 2 -wtu-P is the problem whose instances are pairs c, where c is an instance of u-P and : ω → k is a function such that lim y (y) exists and is a witness of thin-unbalancing for c, and the solutions to such a pair are the P-solutions to c.

• wtu-P is the problem whose instances are pairs c, i where c is an instance of u-P and i is a witness of thin-unbalancing for c, and the solutions to such a pair are the P-solutions to c.

The above are arguably not natural problems from a combinatorial point of view, and we will not study them in their own right. Rather, our interest is in what these principles can reveal about SRT 2 k and D 2 k . As we will see, the above restrictions capture various elements of standard proofs of these principles. Proposition 3.6.

(

) For P ∈ {SRT 2 k , D 2 k }, we have LPO W wtu-P sW ∆ 0 2 -wtu-P sW u-P. (2) wtu-SRT 2 k × wtu-SRT 2 2 sW wtu-SRT 2 k and wtu-D 2 k × wtu-D 2 2 sW wtu-D 2 k . Proof. For part (1), it is enough to show that LPO W wtu-D 2 1
2 , the rest of the reductions being obvious. This is proved much like Proposition 2.10. Given an instance S of LPO, define c :

[ω] 2 → 2 by c(x, y) = 1 if S(x) = S(y), 0 otherwise.
If S = 0 ω then c(x, y) = 1 for all x < y, and if S = 0 n 1 ω then lim y c(x, y) = 1 for all x > n and lim y c(x, y) = 0 for all x n. Either way, c is an instance of wtu-D 2 2 with witness of thin-unbalancing 0. Now if L is any limit-homogeneous set for c then S = 0 ω if and only if there is an x min L such that S(x) = 1.

For part (2), we prove the result for SRT 2 k , the proof for D Notice that e is stable. We claim that e is thin-unbalanced as witnessed by i c . Indeed, if H were infinite and homogeneous for e with color i c then we could define

f : [H] 2 → 2 by f (x, y) = 0 if c(x, y) = i c , 1 otherwise.
Any infinite homogeneous set for f contained in H with color 0 would be homogeneous for c with color i c , and any infinite homogeneous set for f contained in H with color 1 would be homogeneous for d with color i d . Neither of these is possible by assumption, so the claim holds. Hence, e is an instance of wtu-SRT 2 k , and it is clear that any infinite homogeneous set for e is homogeneous for both c and d.

As we will see in Proposition 4.2, wtu-P ≡ W ∆ 0 2 -wtu-P for P ∈ {SRT 2 2 , D 2 2 }. Note that in part (1) above, the reduction from LPO to wtu-P cannot be improved from W to sW . Indeed, it follows from a result of Brattka and Rakotoniaina

Thus, if S = 0 ω then d = c, and if S = 0 n 1 ω for some n then c(x, y) = d(x, y) for all x n and lim y d(x, y) = lim y (y) = i for all x < n. Since c has no infinite limit-homogeneous set with color i, it follows that every infinite limit-homogeneous set L for d is also limit-homogeneous for c. Moreover, we have that S = 0 n 1 ω if and only if (∃x min L)[S(x) = 1]. Hence, {b}, L , where b is 0 or 1 depending on whether S = 0 ω or S = 0 n 1 ω for some n < L, is a uniformly S ⊕ L-computable solution to the LPO × ∆ 0 2 -wtu-D 2 k -instance S, c, . For the reverse direction, fix a problem P such that LPO × P W D 2 k , say via functionals Φ and Ψ. Fix an instance X of P. We describe a uniform procedure to define an X-computable thin-unbalanced stable coloring d : [ω] 2 → k with a witness given in a ∆ 0 2 way, and a uniform procedure for turning any infinite limithomogeneous set for d into a P-solution for X. To begin, let c = Φ 0 ω ⊕X , which is a stable coloring [ω] 2 → k by assumption. Define C to be the Π 0,X 1 class consisting of all partitions P 0 , . . . , P k-1 of ω such that

(∀i < k)(∀ finite F ⊆ P i )[Ψ 0 ω ⊕X⊕F (0) 1].
It must be that C = ∅. For suppose otherwise, and choose any P 0 , . . . , P k-1 ∈ C and an i < k such that P i is infinite. Let L ⊆ P i be an infinite limit-homogeneous set for c. Then by the definition of C, we have Ψ 0 ω ⊕X⊕L (0) 1, which is a contradiction because 0 ω , X is an instance of LPO × P, and we should thus have Ψ 0 ω ⊕X⊕L (0)↓ = 0. So C is empty, as claimed. By compactness, we can uniformly X-computably find an m such that for every partition P 0 , . . . , P k-1 of ω, there are an i < k and a finite F ⊆ P i m such that Ψ 0 ω ⊕X⊕F (0)↓ = 0. Let u m be a bound on the uses of all these computations, for all possible such F . Choose n > u large enough so that Φ 0 n 1 ω ⊕X and c = Φ 0 ω ⊕X agree below u. Let S = 0 n 1 ω , and let d = Φ S⊕X . Note that d is uniformly X-computable.

We claim that d is thin-unbalanced. To see this, let P 0 , . . . , P k-1 be the partition of ω given by P i = {x ∈ ω : lim y d(x, y) = i}. Let i < k and F ⊆ P i m be as above. If P i were infinite, then there would be an infinite limit-homogeneous set L for d having F as an initial segment, and by construction, this set would satisfy Ψ S⊕X⊕L (0)↓ = 0 even though S = 0 ω . Thus, P i is finite, so i is a witness to thin-unbalancing for d. Moreover, since i depends only on lim y d(x, y) for x < m, it follows that i can be approximated from d, and hence from X, in a uniform ∆ 0 2 way. So d is an instance of ∆ 0 2 -wtu-D 2 k . Now if L is any infinite limit-homogeneous set for d, we must have Ψ S⊕X⊕L = {1}, Y , where Y is a P-solution to X. Hence, there is a uniform way to convert X ⊕ L into a P-solution for X, as desired.

A succinct way to express the characterization given by the preceding theorem is that ∆ 0

2 -wtu-D 2 k = sup W {P : P × LPO W D 2 k }.
We can obtain several other results of this sort, the proofs of which are similar to the preceding theorem, and are left to the reader. Proposition 3.8. The following all exist and are all Weihrauch equivalent:

(1)

∆ 0 2 -wtu-D 2 k ; (2) sup W {P : P × LPO W D 2 k }; (3) sup W {P : P × LPO W ∆ 0 2 -wtu-D 2 k }; (4) sup W {P : P × ∆ 0 2 -wtu-D 2 k W ∆ 0 2 -wtu-D 2 k }; (5) sup W {P : P × ∆ 0 2 -wtu-D 2 k W D 2 k }.
We do not know a similar characterization for SRT 2 k , nor even an answer to the following question. (It is worth noting that the Weihrauch lattice is not complete. Indeed, by [START_REF] Higuchi | The degree structure of Weihrauch reducibility[END_REF]Proposition 3.15], it does not have any nontrivial infinite suprema.) Question 3.9. Does sup W {P : P × LPO W SRT 2 k } exist? As a partial step, we have the following: Proposition 3.10. Let P be a problem.

(

) If P W ∆ 0 2 -wtu-SRT 2 k then LPO × P W SRT 2 k . (2) If LPO × P W SRT 2 1
k then P is Weihrauch reducible to the problem whose instances are pairs c, where c is an instance of SRT 2 k and : ω → k is a function such that lim y (y) exists and is a witness to thin-unbalancing for c on some set that is low relative to c, and the solutions to such a pair are the SRT 2 k -solutions to c. Proof. Part (1) is proved just like the forward direction of Theorem 3.7. For part (2), we proceed as in the proof of the reverse direction of Theorem 3.7, only the Π 0,X 1 class C now consists of all partitions P 0 , . . . , P k-1 of ω such that

(∀i < k)(∀ finite F ⊆ P i )[(∀x, y ∈ F )[c(x, y) = i] → Ψ 0 ω ⊕X⊕F (0) 0].
We can assume that c ≡ T X, because we can replace it by the coloring c obtained by letting c (n, n + 1) = X(n) and c (x, y) = c(x, y) for all other pairs. An infinite solution to c can be uniformly transformed into one to c by thinning. Now, if C = ∅, let n be as in the corresponding case in the proof of Theorem 3.7. For each i < k, let P i = {x : lim y Φ 0 n 1 ω ⊕X (x, y) = i}. Then for some i < k, there exists a finite F ⊆ P i such that F is homogeneous for Φ 0 n 1 ω ⊕X with color i and Ψ 0 n 1 ω ⊕X⊕F (0)↓ = 1. Moreover, this F and i can be approximated in a ∆ 0,X 2 way (i.e., ∆ 0 2 relative to the instance 0 n 1 ω , X ). Now if Φ 0 n 1 ω ⊕X had any infinite homogeneous set with color i, then c would have such a set extending F , which would produce the same contradiction as in Theorem Thus, it must be that Φ 0 n 1 ω ⊕X has no homogeneous set with color i, so in particular, it is thin-unbalanced (on the low set ω).

If, on the other hand, C = ∅, then let P 0 , . . . , P k-1 be the canonical lowover-X element of it (given by the proof of the low basis theorem). Clearly, we can approximate in a ∆ 0,X 2 way (in fact, in a Π 0,X 1 way), the least i such that P i is infinite. Then c = Φ 0 ω ⊕X must be thin-unbalanced on P i with witness i. Otherwise, we could take a homogeneous set H for c with color i contained in P i and have, by the definition of C, that Ψ 0 ω ⊕X⊕H (0) 1, which is a contradiction because 0 ω , X is an instance of LPO × P, and we should thus have Ψ 0 ω ⊕X⊕H (0)↓ = 0. Remark 3.11. With a view to some of the recent work on the algebraic structure of the Weihrauch degrees ( [START_REF] Brattka | On the algebraic structure of Weihrauch degrees[END_REF][START_REF] Damir | Joins in the strong Weihrauch degrees[END_REF]), Theorem 3.7 suggests a natural parallel quotient operator on problems, given by P/Q = sup W {R : R × Q W P}. We have no reason to think this operator is total, but studying the kinds of problems for which it is defined ought to be interesting in its own right.

The cofinite-to-infinite principle

In this section, we briefly depart from studying products, to investigate wtu-D 2 2 (in the guise of a Weihrauch-equivalent principle introduced below) in the context of other weak Weihrauch degrees. Some of our terminology will be specific to the Weihrauch literature, and we refer the reader to [START_REF] Brattka | Weihrauch complexity in computable analysis[END_REF] for any definitions we omit.

We begin by introducing the following "cofinite set to infinite set" principle. (Thus, informally, CFI ∆ 0 2 is the problem of finding an infinite subset of a cofinite set given by a ∆ 0 2 approximation.) The connection to the previous section is provided by the following result.

Proposition 4.2. CFI ∆ 0 2 ≡ W wtu-D 2 2 ≡ W ∆ 0 2 -wtu-D 2 2 . Proof. It is clear that CFI ∆ 0 2 W wtu-D 2 2 W ∆ 0 2 -wtu-D 2 2 .
In the other direction, suppose we are given an instance c, of ∆ 0

2 -wtu-D 2 2 . Define d : [ω] 2 → 2 by d(x, y) = 1 if c(x, y) = 1 -(y), 0 otherwise.
Now for all x, we have that lim y c(x, y) = 1 -lim y (y) if and only if lim y d(x, y) = 1. In particular, since lim y c(x, y) = 1 -lim y (y) for almost all x, we have lim y d(x, y) = 1 for almost all x. Clearly, every limit-homogeneous set for d is also limit-homogeneous for c.

Notice that a similar proof shows that wtu-SRT 2 2 ≡ W ∆ 0 2 -wtu-SRT 2 2 . We now compare CFI ∆ 0 2 with the choice principle C N defined in Section 1.

Proposition 4.3. CFI ∆ 0 2 C N ≡ W CFI ∆ 0 2 . Proof. First we show that CFI ∆ 0 2 C N W CFI ∆ 0 2 × C N .
Note that C N is computable with finitely many mindchanges, while solutions to instances of CFI ∆ 0 2 are invariant under finitely many mindchanges. Thus, we can compute directly the impact C N has the CFI ∆ 0 2 , and do not need to use them sequentially. Then we argue that CFI ∆ 0 2 × C N W CFI ∆ 0 2 . We identify an instance e of C N with the complement of the set enumerated by e, and an instance c of CFI ∆ 0 2 with the corresponding ∆ 0,c 2 set. As shown in [28, Lemma 2.3], we may assume without loss of generality that the instances of C N are of the form {n | n > k} for some k ∈ ω. Given instances of C N and of CFI ∆ 0 2 , we can compute the intersection of these instances, and think of it as an instance of CFI ∆ 0 2 . Any infinite subset of this intersection is a solution to the original CFI ∆ 0 2 instance, and any element a solution to the C N instance.

We can think of the instances of CFI ∆ 0 2 as being functions p : ω → ω such that |{i ∈ ω : p(i) = n + 1}| < ∞ for all n, and such that |{i ∈ ω : p(i) = n + 1}| is even for cofinitely many n. Then, a solution is any infinite set Y such that if n ∈ Y then |{i ∈ ω : p(i) = n + 1}| is even. It is easy to see that this formulation is Weihrauch equivalent to the one given in Definition 4.1. However, we shall find this version more convenient for our results below.

Given p ∈ ω ω as above, let ψ(p) = {n : |{i ∈ ω : p(i) = n + 1}| is even}. For each p ∈ ω <ω ∪ ω ω , let [p] = {n : ∃i p(i) = n + 1}. For σ ∈ ω <ω , let σ be the length-lexicographically least extension of σ such that|{i ∈ ω :

σ(i) = n + 1}| is even for all n ∈ [σ]. Definition 4.4. For σ ∈ ω <ω , let CFI σ ∆ 0 2 denote the restriction of CFI ∆ 0 2 to instances σp such that [σ] ∩ [p] = ∅. Proposition 4.5. For every σ ∈ ω <ω , we have CFI σ ∆ 0 2 ≡ W CFI ∆ 0 2 . Proof. Let h : ω → {x ∈ ω : x > max[σ]} be a computable bijection. Let h : ω ω → ω ω be defined pointwise via h(p)(n) = h(p(n)). Then CFI ∆ 0 2 (p) = h -1 • CFI σ ∆ 0 2 ( σh(p)).
We can now prove that CFI ∆ 0 2 has properties very similar to being a total fractal (see Brattka, Gherardi, and Pauly [4, Section 4]; see also Theorem 7.15 in that paper). In the context of Weihrauch degrees, a fractal may be thought of as a problem that retains its full power on arbitrarily small (clopen) restrictions of its domain. Proof. Let Φ map instances of CFI ∆ 0 2 to instances of C N . If there is no string σ ∈ ω <ω such that Φ σ (0)↓ = 0, then 0 is always a valid answer to the C N -instances used in the reduction, and the C N -call is useless. So suppose otherwise, and let σ 0 be such a string.

Assume now that we have defined σ 0 , . . . , σ k-1 ∈ ω <ω , and choose the least n / ∈ i<k [σ i ]. Suppose there is no string σ with n ∈ [σ] and [σ] ∩ [σ i ] = ∅ for all i < k, and such that Φ σ0... σ k-1 σ (k)↓ = 0. Then choose any σ with n ∈ [σ] and

[σ] ∩ [σ i ] = ∅ for all i < k. Now CFI σ0•••σ k-1 σ ∆ 0 2
W P because we can replace the output of C N by k. By Proposition 4.5, this fact implies the claim. So suppose otherwise, and let σ k be a string with the desired properties.

If this procedure never stops, then we construct some p = σ 0 σ 1 σ 2 . . .. By induction, all the [σ i ] are mutually disjoint, and every n ∈ ω appears some even number of times in some [σ i ], so certainly p is an instance of CFI ∆ 0 2 . However, by construction we also find that Φ p = ∅ is not an instance of C N , which is a contradiction. This proposition allows us to deduce a number of non-reduction facts about CFI ∆ 0 2 , which point to its strength. We begin with the following. Neumann and Pauly [START_REF] Neumann | A topological view on algebraic computation models[END_REF] introduced the sorting principle, Sort, whose instances are all elements of 2 ω , such that the instance p ∈ 2 ω has the unique solution 0 n 1 ω if p contains exactly n many 0's, and 0 ω if p contains infinitely many 0's. We refer to [4, Definition 1.2] for the definitions of the k-fold product and the star operation, * . Suppose there is a τ such that Φ τ outputs at least n many 0's for each input to Sort and Ψ outputs some l ∈ N on input τ, 0 n , . . . , 0 n . Then there is some p such that l / ∈ ψ(τ p), which is a contradiction. Thus for each p, there is some d k such that the dth input to Sort given by Φ p has finitely many 0's. The set of pairs d, n such that the dth input has some 0 in a position greater than n is c.e. in p, so from p we can obtain an instance of C N whose solutions are pairs d, n such that the dth input has no 0's at positions greater than n. It follows that

CFI ∆ 0 2 W Sort k-1 C N . By Proposition 4.6, this in turn implies CFI ∆ 0 2 W Sort k-1 , contradicting the minimality of k.
In the next proposition, K N denotes the choice problem for compact subsets of N (see [START_REF] Brattka | Weihrauch complexity in computable analysis[END_REF]). We refer the reader to [4, Section 6] for the definition of the jump operator, , on Weihrauch degrees. Definitions of the countable coproduct and the problems C {0,...,n} used in the proof below can also be found in that paper, in Sections 4 and 7, respectively.

Proposition 4.8. CFI ∆ 0 2 W C N but CFI ∆ 0 2 W K N .
Proof. For the reduction, fix some enumeration (σ i ) i∈ω of ω <ω . Given some input d to CFI ∆ 0 2 we define a sequence (e n ) n∈ω with e n : ω 2 → 2 by e n (x, s) = 0 iff for all y < n we have that d(y, s) = 0 iff y occurs in σ x . The sequence (e n ) n∈ω converges to some e : ω 2 → 2 with the property that e(x, s) = 0 for all s ∈ ω precisely when σ x lists exactly those k with lim y d(k, y) = 0. Clearly, from such a finite tuple we can compute an infinite subset of its complement.

For the non-reduction, note that

K N W n∈ω C {0,...,n} C N , so if CFI ∆ 0 2 W
K N , then by Proposition 4.6, we have CFI ∆ 0 2 W n∈ω C {0,...,n} . As CFI ∆ 0 2 is a fractal (as discussed above), then there is some k ∈ ω with CFI ∆ 0 2 W C {0,...,k} . But this is impossible for reasons of cardinality.

The connected choice problem of the next theorem was introduced by Brattka, Le Roux, Miller, and Pauly [START_REF] Brattka | Connected choice and the Brouwer Fixed Point Theorem[END_REF]. The instances of CC 1 are nonempty closed subintervals of the real unit interval (see [START_REF] Brattka | Connected choice and the Brouwer Fixed Point Theorem[END_REF] for details on how the elements of the collection A([0, 1]) of such subintervals are represented), and the solutions to any such instance are the points inside it. Theorem 4.9.

CC 1 W CFI ∆ 0 2 . Proof. Assume that CC 1 W CFI ∆ 0
2 via Φ and Ψ. Let p 0 ∈ ω ω be a name for [0, 1] ∈ A([0, 1]). There have to be some finite set B 0 ⊂ ω and a prefix σ 0 of p 0 such that upon reading σ 0 and B 0 , the functional Ψ outputs a 2 -2 -approximation of some x 0 ∈ [0, 1]. We can find some τ 0 p 1 such that σ 0 τ 0 p 1 is a name for some interval I 1 with |I 1 | 2 -2 and such that for any q extending σ 0 τ 0 and representing some A ∈ A([0, 1]), we have that A ∩ B(x 0 , 2 -2 ) = ∅ (where B(x 0 , 2 -2 ) is the ball of radius 2 -2 around x 0 ). It follows that for any q extending σ 0 τ 0 , the set ψ(Φ q ) must not contain B 0 , for if it did, we could start the enumeration with B 0 , and thus trick Ψ into outputting a 2 -2 -approximation of x 0 , which cannot be correct.

In the next step, Ψ has to output some 2 -4 -approximation of some x 1 upon reading some prefix σ 0 τ 0 σ 1 of σ 0 τ 0 p 1 and a finite set B 1 with max B 1 > min B 0 . We pick τ 1 to exclude B(x 1 , 2 -4 ) from the solution set, and thus conclude that for any q extending σ 0 τ 0 σ 1 τ 1 , the set ψ(Φ q ) must not contain B 1 (nor B 0 ).

By iterating the procedure, we obtain some input σ 0 τ 0 σ 1 τ 1 σ 2 τ 2 • • • ∈ ω ω , which is in the domain of CC 1 (as this has a total domain if represented in a suitable way), but such that ψ(Φ σ0τ0σ1τ1σ2τ2••• ) excludes countably many disjoint finite sets

B 0 , B 1 , . . .. Hence, ψ(Φ σ0τ0σ1τ1σ2τ2••• ) / ∈ dom(CFI ∆ 0 2
), and we have derived a contradiction.

Brattka, Hölzl, and Kuyper [5, Proposition 16] showed that CC 1 W Sort, so it follows that Sort W CFI ∆ 0

2 . An alternate proof of this fact can be given by using the following technical notion, where lim is the problem where an instance is a convergent sequence of elements of N N , and the unique solution to this problem is the limit of this sequence. Definition 4.10. Suppose G : ⊆ X ⇒ Z is a partial multifunction of represented spaces. Then G is low for functions if, for every f : Y → ω ω that satisfies f W lim G, we have f W lim.

(∀x ∈ X)(∃k 0 ∈ ω)(∀k k 0 )[{n : n k} ∈ G(x)].
Then G is low for functions.

Proof. Let f : Y → ω ω be such that f W lim G. Without loss of generality, we may assume that X, Y ⊆ ω ω . As lim is transparent (see Brattka, Gherardi, and Marcone [3, Fact 5.5]), we can obtain f (x) = lim i→∞ Ψ i (x, G(Φ(x))) for some functionals Φ and Ψ i . Let ω k = {n ∈ ω : n k} ∈ O(ω). Now for any x ∈ X, we have that Ψ k (x, ω k ) is defined and is an element of Ψ k (x, G(Φ(x))) for almost all k. As f is a function, in lim i→∞ Ψ i (x, G(Φ(x))) it does not matter whether we choose from G(Φ(x)) once for the entire expression, or separately for each i. Thus, we can compute f (x) as lim k→∞ Ψ k (x, ω k ). (While finitely many of these values may be undefined, this problem can be resolved with a standard argument.) Lemma 4.12. Let G be low for functions, and f : X → ω ω with f W G. Then lim f W lim.

Proof. As f is a function, so is lim f . Moreover, f W G implies lim f W lim G, so lim f W lim. Corollary 4.13. Sort W CFI ∆ 0 2 . Proof. By Proposition 4.11, CFI ∆ 0 2 is low for functions. As Sort is a function, Lemma 4.12 shows that if we had Sort W CFI ∆ 0 2 we would also have lim Sort W lim. However, it is not difficult to check that LPO W LPO Sort W lim Sort, but LPO W lim. To see that this non-reduction holds, first note that there is a uniformly computable sequence S 0 , S 1 , . . . of instances of LPO such that for each e, the eth Turing functional Φ e is total if and only if S e = 0 ω . Thus, for each e, to determine whether S e has solution 0 is Π 0 2 -hard. On the other hand, every computable lim-instance has a uniformly ∆ 0 2 solution.

Note that while the proof above shows that lim Sort W lim, it was shown by Neumann and Pauly [24, Corollary 32] that lim lim Sort W lim lim.

Ramsey's theorem for singletons

In this section, we investigate Ramsey's theorem for singletons and different numbers of colors, and how these problems behave under Weihrauch reducibility with respect to products. A motivating toy example is the fact that RT We show below that the right-hand side is optimal. Our results extend a number of similar investigations, including by Dorais, Dzhafarov, Hirst, Mileti, and Shafer [START_REF] François | On uniform relationships between combinatorial problems[END_REF], Hirschfeldt and Jockusch [START_REF] Hirschfeldt | On notions of computability-theoretic reduction between Π 1 2 principles[END_REF], and Patey [START_REF] Patey | The weakness of being cohesive, thin or free in reverse mathematics[END_REF].

In the sequel, we will regard RT 1 k as the problem whose instances are colorings c : ω → k and whose solutions are colors that appear infinitely often in c. Note that this formulation of RT 1 k is Weihrauch equivalent to the more usual one given in Definition 1.4, so we will not distinguish these versions when discussing Weihrauch reducibility. In the context of strong Weihrauch reducibility, we will refer to the new version as rt 1 k . Given this formulation, the backward functionals of our strong Weihrauch reductions will have single numbers or tuples of numbers as oracles, and hence can be regarded as partial functions. For such a functional Ψ, we write Ψ(n) instead of Ψ n .

We begin with the following lemma:

Lemma 5.1. Suppose that P W Q and these problems satisfy the following properties:

• P has finite tolerance, i.e., there is some Θ such that if C 0 and C 1 are P-instances, C 0 (x) = C 1 (x) for all x above some m, and S 0 is a P-solution to C 0 , then Θ S0⊕m is a P-solution to C 1 ; • any finite modification of a P-instance is still a P-instance;

• solutions to all instances of P and Q lie in some fixed finite set.

Then P sW Q.

Proof. Fix functionals Φ and Ψ witnessing that P W Q. Since solutions to all instances of P lie in some fixed finite set, we may assume that for each P-instance C and each s that is a Q-solution to Φ C , we have that Ψ C⊕s outputs a number that codes a P-solution to C. Fix a functional Θ witnessing that P has finite tolerance. Fix a finite solution set S for Q. We define functionals that witness that P sW Q.

First, we construct a finite initial segment τ of a P-instance C that decides (in the sense of Cohen 1-genericity) for each s ∈ S whether Ψ C⊕s converges. Since S is finite, such τ exists.

We define Φ by Φ C = Φ C , where C is obtained from C by replacing its initial segment of length |τ | by τ itself. By our assumption on P, this C is still a Pinstance.

We define Ψ by Ψ(s) = Θ Ψ τ ⊕s ⊕|τ | . We show that Φ and Ψ witness that P sW Q. Take any P-instance C. Since C is a P-instance, Φ C = Φ C is a Q-instance. Let s be any Q-solution to Φ C . Then Ψ C ⊕s is a P-solution to C . In particular, Ψ C ⊕s converges. Since C extends τ , by our construction of τ , we have that Ψ τ ⊕s ↓ = Ψ C ⊕s ↓. Hence Ψ τ ⊕s is a P-solution to C . We conclude that Ψ(s) = Θ Ψ τ ⊕s ⊕|τ | is a P-solution to C.

It is easy to see that rt 1 k (and finite parallel products of rt 1 k ) satisfy the properties of P and Q in Lemma 5.1. Therefore we have the following. Proof. Fix Φ and Ψ witnessing that n m=0 rt 1 km sW rt 1 N . We show that for each (a 0 , . . . , a n ) ∈ n m=0 k m , there is some i < N such that Ψ(i) = (a 0 , . . . , a n ). Consider the tuple of constant colorings (a ω 0 , . . . , a ω n ). This is a n m=0 rt 1 kminstance, so Φ (a ω 0 ,...,a ω n ) is an rt 1 N -instance with some solution i. Then Ψ(i) must be a solution to (a ω 0 , . . . , a ω n ), so Ψ(i) = (a 0 , . . . , a n ).

Corollary 5.4.

If n m=0 RT 1 kn W RT 1 N , then N n m=0 k m .
Therefore the right-hand side of n m=0 rt 1 km sW rt 1 n m=0 km is optimal, with regards to both W and sW . However, we will see that RT for all n 1 and k 0 , . . . , k n 2 (Proposition 5.13). In the rest of this section, we attempt to find the smallest N such that

RT 1 N W n m=0 RT 1 km .
We start by giving a lower bound for N .

Proposition 5.5. For all n 1 and k 0 , . . . , k n 2,

rt 1 1+ n m=0 (km-1) sW n m=0 rt 1 km .
Proof. Suppose we are given an instance c of rt 1

1+ n m=0 (km-1) . For 0 m n, we define colorings

d m : ω → m-1 i=0 (k i -1), . . . , m i=0 (k i -1)
as follows. Note that for each m, d m will be a k m -coloring.

For each m and x, we define d m (x) as follows. First check which color among 0, . . . , m i=0 (k i -1) appears most often among c(0), . . . , c(x). (Resolve ties by picking the smallest color.) If this color is among 0, . . . ,

m-1 i=0 (k i -1), let d m (x) = m-1 i=0 (k i -1)
. Otherwise, let d m (x) be this color. Now, given (a 0 , . . . , a n ) that, for each m, the color a m appears infinitely often in d m , we want to compute a color that appears infinitely often in c. Start by considering a n . If a n = n-1 i=0 (k i -1), then for infinitely many x, the color a n appears most often among c(0), . . . , c(x). In particular, a n appears infinitely often in c.

On the other hand, if a n = n-1 i=0 (k i -1), then for infinitely many x, some color among 0, . . . , n-1 i=0 (k i -1) appears most often among c(0), . . . , c(x). By the pigeonhole principle, some color among 0, . . . , n-1 i=0 (k i -1) appears infinitely often in c. We then proceed to consider a n-1 and repeat the above case division. Eventually we either reach some a m that is not equal to m-1 i=0 (k i -1), in which case a m appears infinitely often in c, or we reach a 0 = 0, in which case 0 appears infinitely often in c.

In order to obtain upper bounds for N , we begin by restricting the reductions that we need to diagonalize against. Firstly, by Lemma 5.1, we need only handle strong Weihrauch reductions: km -instance, and a backward functional Ψ. Then for any i < N , there exists (a 0 , . . . , a n ) where each a m < k m and Ψ(a 0 , . . . , a n ) = i.

Proof. Given i < N , consider the coloring c that is constantly i. Then the tuple (Φ c 0 , . . . , Φ c n ) is a n m=0 rt 1 km -instance. Hence it has some solution (a 0 , . . . , a n ). The only solution to c is i, so Ψ(a 0 , . . . , a n ) must be i. Henceforth, we will always assume that our reductions of rt 1 N to n m=0 rt 1 km have the above special form. In order to diagonalize against such reductions, it will be convenient to have the following notion of covering a tuple of colors using a set of tuples of colors. Definition 5.9. If X ⊆ n m=0 k m and (i 0 , . . . , i n ) ∈ n m=0 k m , we say that X covers (i 0 , . . . , i n ) if for each 0 m n, there is an (a 0 , . . . , a n ) ∈ X such that a m = i m .

Observe that if c is a n m=0 rt 1 km -instance whose solution set contains X, and X covers (i 0 , . . . , i n ), then (i 0 , . . . , i n ) is also a solution to c.

The following terminology will also be useful.

Definition 5.10. For a surjective partial function Ψ : n m=0 k m → N , we refer to each Ψ -1 (i) as a group. We call a group of size one a singleton.

We now work towards an upper bound (≈ km

2 ) for N . Suppose we want to show that RT 1 km such that Ψ is a surjective partial function from n m=0 k m to N . We aim to construct c : ω → N and some (a 0 , . . . , a n ) such that (a 0 , . . . , a n ) is a solution to Φ c 0 , . . . , Φ c n , yet Ψ(a 0 , . . . , a n ) is not a solution to c.

Our basic strategy is to choose N large enough so that the following combinatorial property holds for all surjective partial functions Ψ : n m=0 k m → N : There is some nonempty S N such that for any set of (a 0 , . . . , a n )'s whose image under Ψ is exactly S, the (a 0 , . . . , a n )'s cover some (b 0 , . . . , b n ) that maps outside S under Ψ.

( * ) Assuming ( * ), we may construct c by repeatedly looping through colors in S: for each i ∈ S, extend constantly by i until there is some (a 0 , . . . , a n ) that maps to i under Ψ, such that for all 0 m n, we have that Φ c m has some new element of color a m . (This must happen eventually: if c is the rt 1 N -instance produced by extending the current finite coloring by i forever, then Φ c 0 , . . . , Φ c n is a n m=0 rt 1 kminstance with some solution (a 0 , . . . , a n ). Then Ψ(a 0 , . . . , a n ) = i, and for each 0 m n, some new element of color a m must appear at some finite stage of Φ c m .) Then for each i ∈ S, there is some (a 0 , . . . , a n ) such that Ψ(a 0 , . . . , a n ) = i and (a 0 , . . . , a n ) is a solution to Φ c 0 , . . . , Φ c n . But then the (a 0 , . . . , a n )'s cover some (b 0 , . . 2 , by a counting argument, Ψ must have at least one singleton (a 0 , a 1 ). Note that there are 1 + (k 0 -1) + (k 1 -1) = k 0 + k 1 -1 many pairs in k 0 × k 1 that share some color with (a 0 , a 1 ). But N > k 0 + k 1 -1, so there is some group G such that none of its pairs share any colors with (a 0 , a 1 ). In other words, for every pair in G, the set containing it and (a 0 , a 1 ) covers a pair outside G. Let S be the image of (a 0 , a 1 ) and G under Ψ. Then S witnesses that ( * ) holds.

Corollary 5.12. We have that RT Note that Proposition 5.5 implies that RT 1 k0+k1-1

W RT 1 k0 × RT 1 k1
. Hence all of the non-reductions in Corollary 5.12 are sharp. We will address the missing case of RT 1 8 and RT 1 4 × RT 1 4 in Proposition 5.16. We can derive more results using variations of the argument in Proposition 5.11. Proof. As before, we show that ( * ) holds. By a counting argument, Ψ must have at least 1 + max k m many (a 0 , . . . , a n ) that are singletons. Among these singletons, there must be two of them that differ in at least two entries, i.e., the set consisting of these two singletons covers a new tuple of colors. We can then take S to be the image of two such singletons under Ψ.

We can improve on this bound asymptotically, but even then this result seems to be far from optimal. Proof. As before, we show that ( * ) holds. Since N >

2+ n m=0 km 2

, the reduction Ψ must have at least three singletons.

Case 1. If there are two singletons that differ in at least two entries, then we may take S to be the image of two such singletons under Ψ, as in Proposition 5.13.

Case 2. Otherwise, all of the singletons share exactly one common entry. So there are some 0 m n and 3 l k m such that there are exactly l many singletons and all of them are of the form (a 0 , . . . , a m-1 , b, a m+1 , . . . , a n ), where b < k m . Case 1. The rectangle contains at least one of those k groups. There are at most (4 -1)k = 3k many such rectangles.

a 0 0 • a 1 1 • • • b 0 a 0 0 2 a 1 1 • • b 0 b 2 a 0 0 a 1 1 2 b 0 b 2 0 1 0 2 0 1 1 2 0 1 2 2
Case 2. The rectangle contains at least one group in diagonal position. There are at most 8 -k many such rectangles.

Therefore, there are at most 3k + (8 -k) = 2k + 8 many rectangles that intersect at most three groups. So there are at most 2k + 8 many collections that satisfy (2).

Next, we give an upper bound for the number of collections that satisfy (1) in Lemma 5.15.

Case 1. If a row/column contains two groups (and hence nothing else), then said row/column does not contribute to our upper bound. Let l be the number of such rows and columns. Note that 2l k.

Case 2. If a row/column contains one group, as well as two other vertices from two different groups, then said row/column contributes one collection to our upper bound. There are k -2l many such rows/columns. Case 3. Finally, the remaining 8 + l -k many rows or columns contribute 4 3 = 4 collections each.

  let b-P be the restriction of P to balanced colorings (on ω), and u-P the restriction to unbalanced colorings. Proposition 3.2. LPO W b-SRT 2 2 , but LPO W b-D 2 k for all k. Proof. For the positive reduction, let S be any instance of LPO. Let par(x) be 0 or 1 depending on whether x is even or odd, and define c : [ω] 2 → 2 by c(x, y) = par(x) if (∀z < y)[S(z) = 0], 1 -par(x) otherwise.

2 k

 2 being similar. Let c : [ω] 2 → k and d : [ω] 2 → 2 be instances of wtu-SRT 2 k and wtu-SRT 2 2 , respectively. Say the witnesses of thin-unbalancing for c and d are i c < k and i d < 2, respectively. Define e : [ω] 2 → k by e(x, y) = i c if c(x, y) = i c or d(x, y) = i d , c(x, y) otherwise.

[ 9 , 2 k W D 2 k

 922 Corollary 3.15] that LPO sW RT n k for all n, k 1. Theorem 3.7. Let P be a problem. Then P W ∆ 0 2 -wtu-D 2 k if and only if LPO × P W D 2 k . Proof. For the forward direction, we prove that LPO × ∆ 0 2 -wtu-D . Again, we emulate the proof of Proposition 2.10. Let S ∈ 2 ω be an instance of LPO. Let c, be an instance of ∆ 0 2 -wtu-D 2 k , so that c is a stable coloring [ω] 2 → k, and : ω → ω is a function with lim y (y) = i < k a witness of thin-unbalancing for c. Define d : [ω] 2 → k by d(x, y) = c(x, y) if S(x) = S(y),

Definition 4 . 1 .

 41 CFI ∆ 0 2 is the restriction of D 2 2 to colorings c : [ω] 2 → 2 such that lim y c(x, y) = 1 for almost all x.

Proposition 4 . 6 . 2 W

 462 Let P be any problem. If CFI ∆ 0 P C N , then CFI ∆ 0 2 W P.

Theorem 4 . 7 . 2 W 2 W 2 W 2 W

 472222 CFI ∆ 0 Sort * .Proof. Assume that CFI ∆ 0 Sort * . Then there is a Turing functional mapping instances of CFI ∆ 0 2 to instances of Sort * , and hence there are a σ and a k such that CFI σ ∆ 0 Sort k . Choose k minimal for which there is such a σ. By Proposition 4.5 we also have CFI ∆ 0 Sort k . Let Φ and Ψ witness the reduction.

Proposition 4 . 11 .

 411 Let G : X ⇒ O(ω) (where O(ω) consists of the subsets of ω represented by enumerations of their elements) be such that

1

 1

Proposition 5 . 6 . 1

 561 If RT 1 km via some forward functionals Φ m , 0 m n, where Φ m computes the m th coloring in the n m=0 rt 1

  Combining the previous two propositions, we obtain: Corollary 5.8. Suppose RT 1 witnessed by some Φ m , 0 m n, and Ψ where Ψ :n m=0 k m → N is a surjective partial function.

1

 1 km for some N . Towards a contradiction, we may (by Corollary 5.8) fix Φ m , 0 m n, and Ψ witnessing that rt 1 N sW m rt 1

  . , b n ) that maps outside S under Ψ. It follows that (b 0 , . . . , b n ) is also a solution to Φ c 0 , . . . , Φ c n . But Ψ(b 0 , . . . , b n ) / ∈ S and is hence not a solution to c, which is a contradiction. Thus rt 1 above strategy may be applied as follows:Proposition 5.11. If N > max{ k0•k1 2 , k 0 + k 1 -1}, then RT 1 N W RT 1 k0 × RT1 k1 . Proof. By the previous discussion, it suffices to show that ( * ) holds. Since N > k0•k1

Figure 2 .

 2 Figure 2. Case 2 in Lemma 5.15, assuming that b 0 = b 1 . In the array on the top level, 0 lies in position (a 0 , b 0 ) and 1 lies in position (a 1 , b 0 ), meaning that Ψ(a 0 , b 0 ) = 0 and Ψ(a 1 , b 0 ) = 1. We have yet to label position (a 2 , b 2 ). The middle level represents cases depending on whether a 2 equals some a i , or not. If a star lies in position (a, b), then (a, b) is known (by badness) to lie in the union of the bad collection of three groups. Sets of pairs that satisfy (1) or (2) are underlined. The bottom level represents cases depending on which of the three groups contains (a 2 , b 0 ). For example, in the array on the bottom right, 2 lies in positions (a 2 , b 0 ) and (a 2 , b 2 ), meaning that Ψ(a 2 , b 0 ) = Ψ(a 2 , b 2 ) = 2 and hence (a 2 , b 0 ) and (a 2 , b 2 ) lie in the same group. Then (a 0 , b 0 ), (a 1 , b 0 ), and (a 2 , b 0 ) lie in a column, satisfying (1).

  Corollary 2.8. SRT 2 2 × COH W RT 2 2 . Corollary 2.9. No additional relations hold between the problems in Theorem 2.1. SRT 2 2 . The remaining non-reductions follow from this fact and Corollary 2.8 by transitivity. Note that Theorem 2.6 cannot be improved to show that LPO × NON W RT 2 k for arbitrary k 2. Indeed, each of LPO and NON is Weihrauch reducible to RT 2 2 , and so LPO × NON W RT 2 2 × RT 2 2

Proof. Since every computable instance of each of COH and SRT 2 2 admits a ∆ 0 2 solution, so does every instance of COH × SRT 2 2 . By contrast, it is known that RT 2 2 has a computable instance with no ∆ 0 2 solution. Thus, RT 2 2 W COH × W RT 2 4

  , and in fact, it is easy to see that for all n 1 and k 0 , . . . , k n 2,

	RT 1 4 n		1 2 × RT 1 2	W
	RT 1 km	sW RT 1	n m=0 km .
	m=0

We claim that there are at least k m + 1 many groups of size < l. If not, by a counting argument, there are at least

many tuples, which is a contradiction. By the claim, there is a group U of size < l that does not contain any tuple of the form (a 0 , . . . , a m-1 , b, a m+1 , . . . , a n ). Since |U | < l, there is a singleton (a 0 , . . . , a m-1 , b, a m+1 , . . . , a n ) such that b does not appear in any tuple in U . Then for any tuple in U , the set containing it and (a 0 , . . . , a m-1 , b, a m+1 , . . . , a n ) covers some tuple outside U , so we can take S to be the image of U and said singleton.

The lower bound in Proposition 5.5 is, in general, much smaller than the upper bounds in Propositions 5.11, 5.13, and 5.14. Observe that in all of our proofs, the sets S consist of two elements, at least one of which is the image of a singleton under Ψ. However, Ψ may not have any singletons, for example in a hypothetical reduction witnessing that RT 1 8 W RT 1 4 × RT 1 4 . Also, there may not be any S that has exactly two elements and satisfies ( * ), e.g., consider Ψ : 4×4 → 8 as represented in the grid below. Here Ψ maps (i, j) ∈ 4 × 4 to the number in the (i, j) th position. 0 3 2 6 0 4 5 7 1 2 3 7 1 4 5 6

One can check that for any c, d < 8, there is a point labeled c that shares a row or column with a point labeled d. That means that S = {c, d} fails to satisfy ( * ).

Therefore, new techniques will be required to close the gap between our lower and upper bounds. We conclude this section by giving an ad hoc proof that RT 1 8 W RT 1 4 × RT 1 4 , which is the smallest case not resolved by Corollary 5.12. In order to do so, we will show that there exists some S that satisfies ( * ) and has exactly three elements.

Before specializing to the case of RT 1 8

, we consider a more general context: let k 0 , k 1 2 and fix a surjective partial function Ψ : k 0 × k 1 → N (i.e., a potential backward reduction for rt 1

). We say that a collection of three groups is bad if its image under Ψ does not satisfy ( * ). We can characterize the bad collections of three groups: Lemma 5.15. Let k 0 , k 1 2 and let Ψ : k 0 × k 1 → N be a surjective partial function. A collection of three groups is bad if and only if their union contains either:

(1) three pairs in a row/column (e.g., (a, b 0 ), (a, b 1 ), (a, b 2 )), with one pair from each of the three groups; . If Ψ has any singletons, we can derive a contradiction using the proof of Proposition 5.11. Hence we assume that Ψ has no singletons. There are sixteen pairs in 4 × 4, so Ψ must be total, and all of the eight groups in Ψ must contain exactly two pairs each.

As discussed previously, we derive a contradiction by producing a set S that satisfies ( * ) and consists of three elements. In other words, we show that there is a collection of three groups that is not bad. To that end, we give an upper bound for the number of bad collections of three groups. Since each group contains exactly two pairs, it is either contained in a row or column, or lies in diagonal position. Let k be the number of groups that are contained in some row or column.

First, we give an upper bound for the number of collections that satisfy (2) in Lemma 5.15. It suffices to give an upper bound for the number of rectangles that intersect at most three groups. Such rectangles have two possible forms, and we count those cases separately. We conclude that there are at most (2k + 8) + (32 -2k) = 40 bad collections of three groups. There are 8 3 = 56 > 40 collections of three groups in total, so we can define S to be the image under Ψ of any collection that is not bad. Then S satisfies ( * ), which is a contradiction.