Ulrich Kr

Friedrich Wagemann

A UNIVERSAL ENVELOPING ALGEBRA FOR COCOMMUTATIVE RACK BIALGEBRAS

We construct a bialgebra object in the category of linear maps LM from a cocommutative rack bialgebra. The construction does extend to some non-cocommutative rack bialgberas, as is illustrated by a concrete example. As a separate result, we show that the Loday complex with adjoint coefficients embeds into the rack bialgebra deformation complex for the rack bialgebra defined by a Leibniz algebra.

INTRODUCTION

A shelf is a set X with a composition (x, y) → x ✁ y which satisfies the self-distributivity relation (x ✁ y) ✁ z = (x ✁ z) ✁ (y ✁ z). More generally, this condition makes sense for coalgebras in braided monoidal categories, as was observed by Carter-Crans-Elhamdadi-Saito [START_REF] Carter | Cohomology of categorical selfdistributivity[END_REF] and further studied by Lebed [START_REF] Lebed | Homologies of algebraic structures via braidings and quantum shuffles[END_REF]. In the present article, we will focus on shelves in the category of vector spaces with the tensor flip as braiding: Definition 1. A linear shelf is a coassociative coalgebra (C, △) together with a morphism of coalgebras C ⊗ C → C, (x, y) → x ✁ y that satisfies [START_REF] Alexandre | Structure theory of rack bialgebras[END_REF] (x ✁ y) ✁ z = (x ✁ z (1) ) ✁ (y ✁ z (2) ) ∀x, y, z ∈ C.

A counital and coaugmented linear shelf (C, △, ✁, ǫ, 1) for which

x ✁ 1 = x, 1 ✁ x = ǫ(x)1, ǫ(x ✁ y) = ǫ(x)ǫ(y)

holds for all x, y ∈ C will be called a rack bialgebra.

Here and elsewhere, all vector spaces, coalgebras etc will be over a field k, and we use Sweedler's notation △(z) = z (1) ⊗ z (2) for coproducts.

If C is spanned by primitive elements (together with the coaugmentation), the definition of a rack bialgebra reduces to that of a Leibniz algebra [START_REF] Loday | The tensor category of linear maps and Leibniz algebras[END_REF]. Lie racks provide another natural source of examples with a rich structure theory and applications in the deformation quantisation of duals of Leibniz algebras, see [START_REF] Alexandre | Structure theory of rack bialgebras[END_REF], [START_REF] Alexandre | Algebraic deformation quantization of Leibniz algebras accepted in Communications in Algebra[END_REF].

An important step in the theory of Leibniz algebras was the definition of their universal enveloping algebras [START_REF] Loday | Universal enveloping algebras of Leibniz algebras and (co)homology[END_REF]. Here, we extend this construction to all cocommutative rack bialgebras. The result is a cocommutative bialgebra U(C) in the category of vector spaces, see Theorem 1 below.

One application of universal enveloping algebras is to express cohomology theories as derived functors. Our motivation for the present article was the article [START_REF] Carter | Cohomology of categorical selfdistributivity[END_REF]. Therein, the authors develop a deformation theory of linear shelves. To this end, they defined cohomology groups H n sh (C, C) for n ≤ 3. However, it remained an open question how to extend this to a fully fledged cohomology theory including an interpretation as derived functors in an abelian category. In [START_REF] Crans | On Homology of Associative Shelves[END_REF], this was further studied in the special case where ✁ is also associative.

The present article is meant as a first step towards a possible answer to this question. Our initial goal was to apply our results from [START_REF] Krähmer | Leibniz algebras and Yetter-Drinfel'd modules[END_REF]: therein, we constructed examples of rack bialgebras from Hopf algebras in Loday-Pirashvili's category of linear maps LM [START_REF] Loday | The tensor category of linear maps and Leibniz algebras[END_REF]. Therefore, Gerstenhaber-Schack cohomology [START_REF] Gerstenhaber | Schack Bialgebra cohomology, deformations, and quantum groups[END_REF] in the tensor category LM could be used to define H n sh (C, C) if all linear shelves arose in this way.

Let us describe the content of the present article section by section. Section 1 contains preliminaries on coalgebras and points out that counitisation does not provide an equivalence between linear shelves and rack bialgebras. Section 2 recalls from [START_REF] Krähmer | Leibniz algebras and Yetter-Drinfel'd modules[END_REF] the construction of rack bialgebras from Hopf algebras. Section 3 introduces the notion of a Yetter-Drinfel'd rack which guides the construction of U(C) in the main subsequent Section 4. Therein, we define U(C) and establish its universal property. We also reformulate these results in terms of a bialgebra object in LM and give some examples. The construction of U(C) does extend also to some non-cocommutative rack bialgebras. This is demonstrated with an explicit example in Section 5.

In Section 6, we describe this example as a deformation of a cocommutative rack bialgebra. Furthermore, the Loday complex with adjoint coefficients is embedded into the deformation complex of the rack bialgebra associated to a Leibniz algebra. The article concludes with an outlook and some open questions.

RACK BIALGEBRAS AND LINEAR SHELVES ARE NOT EQUIVALENT

One might expect that linear shelves and rack bialgebras are related by counitisation. We begin by pointing out that this is not the case, so when developing cohomology or deformation theories, one must be clear which of the two structures one is studying. The construction from [START_REF] Krähmer | Leibniz algebras and Yetter-Drinfel'd modules[END_REF] inevitably yields rack bialgebras, hence these are the objects we will focus on afterwards.

More precisely, recall that if a coalgebra has a counit

ǫ : C → k, ǫ(c (1) )c (2) = ǫ(c (2) )c (1) = c ∀c ∈ C,
and is in addition coaugmented, i.e. has a distinguished group-like element

1 ∈ C, △(1) = 1 ⊗ 1,
then the vector space Č := ker ǫ becomes a coalgebra with coproduct

△(c) := △(c) -1 ⊗ c -c ⊗ 1,
or, in Sweedler notation,

c ( 1) ⊗ c ( 2) = c (1) ⊗ c (2) -1 ⊗ c -c ⊗ 1.
Furthermore, the map c → (ǫ(c)1, c -ǫ(c)1) splits C canonically into a direct sum C = k1 ⊕ Č. This shows that C → Č is an equivalence between the category of counital and coaugmented coalgebras and the category of all coalgebras, with inverse C → Ĉ := k⊕C and △(x) = △(x)+1⊗x+x⊗1.

If C is a rack bialgebra, then ✁ does restrict to Č = ker ǫ, but it is in general not self-distributive with respect to △, so Č does not become a linear shelf in its own right. Conversely, if C is a linear shelf, then Ĉ is in general not a rack bialgebra with respect to △. In fact, we have: Proposition 1. The counitisation functor does not lift to an equivalence from the category of linear shelves to the category of rack bialgebras.

Proof. Consider linear shelves C with vanishing coproduct △ = 0. The category of these has a zero object, the shelf of vector space dimension dim k (C) = 0, and a unique simple object, the shelf of dimension dim k (C) = 1 with ✁ = 0. For all other objects C there is a morphism of shelves C → D with nonzero kernel and nonzero image D = 0. Indeed, the quotient vector space C/im ✁ is a linear shelf with respect to △ = ✁ = 0, and the canonical projection C → C/im ✁ is a morphism of linear shelves. Its kernel vanishes if and only if ✁ = 0, that is, if C is a direct sum of 1-dimensional shelves with trivial coproduct and shelf product. In this case, the canonical projection onto any quotient vector space D of dimension dim k (C) -1 has the desired properties. If instead ✁ = 0, then we can take the quotient C → D := C/im ✁ itself: for △ = 0, the selfdistributivity condition reads (x ✁ y) ✁ z = 0 for all x, y, z ∈ C; in particular, im ✁ ⊆ x∈C ker (-✁ x) = C, hence D = 0.

In contrast, the shelf condition on the counitisation Ĉ of a coalgebra C with vanishing coproduct says precisely that the subspace C ⊂ Ĉ is a Leibniz algebra. In particular, this means that among the rack bialgebras with this underlying coalgebra structure, we have the (counitisations of) all simple Lie algebras, and these do not admit any nontrivial proper quotients.

However, there are some subclasses of linear shelves which do admit counitisations that can be turned functorially into rack bialgebras. The most important one is obtained from linearised shelves spannned by group-like elements:

Example 1. Assume that (C, △, ✁) is a linear shelf with a vector space basis G consisting of group-like elements. Then {1, 1 + x | x ∈ G} is a vector space basis of the counitisation Ĉ. Now define a new rack product ◭ on Ĉ by

(1 + x) ◭ (1 + y) := 1 + (x ✁ y).
The self-distributivity for ◭ follows immediately from the selfdistributivity of ✁ and thus Ĉ becomes a rack bialgebra. △

FROM HOPF ALGEBRAS TO RACK BIALGEBRAS

Let (H, △ H , ǫ H , µ H , 1 H , S H ) be a Hopf algebra over k. Then ker ǫ H is a (right right) Yetter-Drinfel'd module with respect to the right adjoint action

h ✁ h ′ := S(h ′ (1) )hh ′ (2)
and the right coaction

h → h (0) ⊗ h (1) := h (1) ⊗ h (2) -1 ⊗ h.
If C ⊂ ker ǫ H is invariant under the adjoint action, then ✁ restricts to a product C ⊗C → C which satisfies (1). However, z (1) ⊗z (2) is the coproduct in H, and in general, this does not restrict to C. One situation where this approach leads to linear shelves is the following:

Proposition 2.
Let H be a cocommutative Hopf algebra and C ⊂ ker ǫ H be a Yetter-Drinfel'd submodule. Then Ĉ := k1 H ⊕ C is a rack bialgebra with respect to the adjoint action ✁ and the restriction of △ H to Ĉ.

Proof. As C is a (right) subcomodule, we have

h (0) ⊗ h (1) ∈ C ⊗ H. But h (0) ⊗ h (1) = h (1) ⊗ h (2) -1 ⊗ h, thus we conclude that h (1) ⊗ h (2) = h (0) ⊗ h (1) + 1 ⊗ h ∈ C ⊗ H. But by cocommutativity, this implies that h (1) ⊗ h (2) = h (2) ⊗ h (1) ∈ H ⊗ C. In conclusion, h (1) ⊗ h (2) ∈ C ⊗ H ∩ H ⊗ C = C ⊗ C, i.e. C is stable under the coproduct of H.
The adjoint action is a morphism of coalgebras thanks to cocommutativity:

(a ✁ b) (1) ⊗ (a ✁ b) (2) = (S(b (1) )ab (2) ) (1) ⊗ (S(b (1) )ab (2) ) (2) = (S(b (1) )) (1) a (1) (b (2) ) (1) ⊗ (S(b (1) )) (2) a (2) (b (2) ) (2) = S(b (3) )a (1) b (2) ⊗ S(b (1) )a (2) b (4) = S(b (1) )a (1) b (2) ⊗ S(b (3) )a (2) b (4) = (a (1) ✁ b (1) )) ⊗ (a (2) ✁ b (2) ),
where we have used cocommutativity in the last step.

As mentioned before, the self-distributivity is the only property which works independently of the cocommutativity of C. Indeed, on the one hand, we have:

(a ✁ b) ✁ c = S(c (1) )S(b (1) )ab (2) c (2)
And on the other hand, we have:

(a ✁ c (1) ) ✁ (b ✁ c (2) ) = S(S(c (3) ) (1) b (1) (c (4) ) (1) )(S(c (1) )ac (2) )(S(c (3) ) (2) b (2) (c (4) ) (2) ) = S(S(c (4) )b (1) c (5) )(S(c (1) )ac (2) )(S(c (3) )b (2) c (6) ) = S(c (5) )S(b (1) )S 2 (c (4) )S(c (1) )ac (2) S(c (3) )b (2) c (6) = S(c (3) )S(b (1) )S(c (2) )S(c (1) )ab (2) c (4) = S(c (1) )S(b (1) )ab (2) c (2)
Example 2. If X is a shelf in the category of sets [START_REF] Fenn | Rourke Racks and links in codimension 2[END_REF], then as discussed in Example 1, the counitisation C = kX of its linearisation becomes a rack bialgebra in which all x ∈ X are group-like. Observe that this construction differs slightly from the construction in [START_REF] Carter | Cohomology of categorical selfdistributivity[END_REF], Section 3.1. △ Example 3. Given a (right) Leibniz algebra h, the k-vector space C := k⊕h becomes a rack bialgebra by extending the bracket [x, y] =: x ✁ y to a shelf product on all of k ⊕ h. More precisely, we endow first of all C with a coproduct requiring that all elements of h are primitive, △(1) = 1 ⊗ 1, ǫ(x) = 0 for all x ∈ h and ǫ(1) = 1. Then put for all x, y ∈ h x✁y = [x, y],

1 ✁ x = ǫ(x)1 and x ✁ 1 = x. This gives a rack bialgebra. △

YETTER-DRINFEL'D RACKS

The question arises which rack bialgebras arise as in Proposition 2. Just as the cocommutativity of H was therein a sufficient, but not a necessary assumption, the construction of a bialgebra that we carry out now can also be applied to certain noncocommutative rack bialgebras. Hence we consider the following general setting adapted from [9, Proposition 5.5]:

Definition 2. Let H be a bialgebra. A Yetter-Drinfel'd rack over H is a rack bialgebra C together with a right H-module structure • : C ⊗ H → C rendering C an H-module coalgebra, and a morphism q : C → H of counital coaugmented coalgebras such that (2) a ✁ b = a • q(b)
and ( 3)

h (1) q(a • h (2) ) = q(a)h
hold for all h ∈ H and a, b ∈ C.

In the cocommutative setting, we have, as the name suggests:

Proposition 3. Let H be a cocommutative bialgebra and C be a Yetter-Drinfel'd rack. Then C becomes a Yetter-Drinfel'd module with respect to the coaction

C → C ⊗ H, x → x (0) ⊗ x (1) := (x (1) -ǫ(x (1) )) ⊗ q(x (2) ) + ǫ(x) ⊗ 1.
Proof. The above formula defines a right coaction, as it is constructed using the coproduct, the counit and the morphism of coalgebras q.

Let us check the Yetter-Drinfel'd property. The two sides in the YDproperty have three terms. Let us reason term by term. For the first term, we have for x ∈ C and h ∈ H

(x • h (2) ) (1) ⊗ h (1) q(x • h (2) ) (2) = = x (1) • h (2) ⊗ h (1) q(x (2) • h (3) ) = = x (1) • h (1) ⊗ q(x (2) )h (2) ,
where we were able to apply the above Condition (3) in the last step only thanks to cocommutativity.

For the second term, we have thanks to Condition (3) and 1 • a = ǫ(a)1. The third term is simply

ǫ(x • h (2) )1 ⊗ h (1) = ǫ(x)1 • h (1) ⊗ h (2) ,
which is simply true again by 1 • a = ǫ(a)1.

Remark 1. Note that for elements h = q(c) in the image of q, the Hmodule coalgebra property

(x • h) (1) ⊗ (x • h) (2) = x (1) • h (1) ⊗ x (2) • h (2)
is satisfied automatically by the fact that ✁ is a morphism of coalgebras.

Hence the H-module coalgebra condition in Definition 2 can be omitted if H is generated as an algebra by im q. △ If H is a Hopf algebra (admits an antipode), then ker ǫ is a Yetter-Drinfel'd module with respect to the right adjoint action, and (3) and the coalgebra morphism condition on q are equivalent to q| C : C → ker ǫ being a morphism of Yetter-Drinfel'd modules.

THE UNIVERSAL ENVELOPING ALGEBRA U(C)

Given any rack bialgebra C, let T = k ⊕ Č ⊕ Č⊗2 ⊕ . . . denote the tensor algebra of Č = ker ǫ and i : C → T be the canonical inclusion, which is the identity on Č and maps the distinguished group-like 1 ∈ C to the scalar 1 ∈ k = Č⊗0 . As we will also consider the tensor product T ⊗ T , we denote the product in T by . rather than ⊗. By the universal property of T , the linear map

Č → T ⊗ T, x → i(x (1) ) ⊗ i(x (2) )
extends uniquely to an algebra map △ T : T → T ⊗ T . The coassociativity of the coproduct in C implies that of △ T . That is, T becomes a bialgebra and i yields an embedding of counital coaugmented coalgebras C → T . Using once more the universal property of T , the rack product

✁ : Č → End(C), x → (y → y ✁ x)
extends to an algebra homomorphism T → End(C), so C becomes a right T -module coalgebra such that x ✁ y = x • i(y). However, i does not turn C into a Yetter-Drinfel'd rack over H = T , as the commutativity relation ( 3) is not satisfied in general. Hence we add the relations manually: Definition 3. For any rack bialgebra C we denote by U(C) the symmetric algebra of C with respect to the vector space braiding

τ : C ⊗ C → C ⊗ C, x ⊗ y → y (1) ⊗ x ✁ y (2) ,
that is, U(C) := T /J where T = T ( Č) and

J := i(y (1) ).i(x ✁ y (2) )) -i(x).i(y) | x, y ∈ C .
We call U(C) the universal enveloping algebra of C and denote the canonical map C → U(C) by q.

A key observation is that in case C is cocommutative, the coproduct △ T descends to U(C):

Lemma 1. The ideal J is also a coideal in case C is cocommutative.

Proof. As △ T is an algebra map, it is sufficient to prove that the coproduct of a generating element of J belongs to T ⊗ J + J ⊗ T .

△ T (i(y (1) ).i(x ✁ y (2) ) -i(x).i(y)) = i(y (1) ).i(x ✁ y (3) ) (1) ⊗ i(y (2) ).i(x ✁ y (3) ) (2) -i(x (1) ).i(y (1) ) ⊗ i(x (2) ).i(y (2) ) = i(y (1) ).i(x (1) ✁ y (3) ) ⊗ i(y (2) ).i(x (2) ✁ y (4) ) -i(x (1) ).i(y (1) ) ⊗ i(x (2) ).i(y (2) )
By cocommutativity, this is an element of T ⊗ J + J ⊗ T :

i(y (1) ).i(x (1) ✁ y (3) ) ⊗ i(y (2) ).i(x (2) ✁ y (4) ) -i(x (1) ).i(y (1) ) ⊗ i(x (2) ).i(y (2) ) = i(y (3) ).i(x (1) ✁ y (4) ) ⊗ i(y (1) ).i(x (2) ✁ y (2) ) -i(x (1) ).i(y (1) ) ⊗ i(x (2) ).i(y (2) ) = i(y (3) ).i(x (1) ✁ y (4) ) -i(x (1) ).i(y (3) ) ⊗ i(y (1) ).i(x (2) ✁ y (2) )+ + i(x (1) ).i(y (3) ) ⊗ i(y (1) ).i(x (2) ✁ y (2) ) -i(x (1) ).i(y (1) ) ⊗ i(x (2) ).i(y (2) ) = i(y (3) ).i(x (1) ✁ y (4) ) -i(x (1) ).i(y (3) ) ⊗ i(y (1) ).i(x (2) ✁ y (2) )+ + i(x (1) ).i(y (1) ) ⊗ i(y (2) ).i(x (2) ✁ y (3) ) -i(x (2) ).i(y (2) ) ∈ J ⊗ T + T ⊗ J.
Note that the action of T on C passes to an action of U(C) on C, thanks to the self-distributivity of ✁: Lemma 2. For all x, y, z ∈ C, we have:

(x • i(y)) • i(z) = (x • i(z (1) )) • i(y ✁ z (2) )
Proof. We have

(x • i(z (1) )) • i(y ✁ z (2) ) = (x ✁ z (1) ) ✁ (y ✁ z (2) ) = (x ✁ y) ✁ z = (x • i(y)) • i(z).
We thus arrive at the following theorem, which realises Č as in [9, Proposition 5.5] as a braided Leibniz algebra: Theorem 1. The universal enveloping algebra U(C) of a cocommutative rack bialgebra is canonically a bialgebra, and C becomes canonically a U(C)-Yetter-Drinfel'd rack. If furthermore q H : C → H is any Yetter-Drinfel'd rack structure on C, then there exists a unique morphism of bialgebras u : U(C) → H such that u • q = q H and hence

(4) x • U (C) s = x • H u(s)
holds for all x ∈ C, s ∈ U(C).

Proof. The U(C)-Yetter-Drinfel'd rack structure of C has been established already. By the universal property of the tensor algebra, there exists a unique algebra homomorphism T ( Č) → H such that

c 1 . • • • .c l → q H (c 1 ) • • • q H (c l ).
This is a morphism of coalgebras on the level of generators, and thus, by multiplicativity, a morphism of coalgebras, i.e. a morphism of bialgebras.

As C is a Yetter-Drinfel'd rack over H, we have

q H (x)q H (y) = q H (y (1) )q H (x ✁ y (2) ), x, y ∈ Č.
Hence the bialgebra map induces a bialgebra morphism

u : U(C) → H.
The equality u • q = q H is true by construction.

Corollary 1. If C is a cocommutative rack bialgebra and U(C) is a Hopf algebra, then C arises as in Proposition 2.

Proof. Indeed, just take H = T ⋊ U(C) -taking the semidirect product is necessary when q : C → U(C) is not injective as in Example 5 below.

We now construct a bialgebra object in Loday-Pirashvili's category LM out of the Yetter-Drinfel'd rack C. Recall that LM is the monoidal category of linear maps between vector spaces with the so-called infinitesimal tensor product as monoidal product, see [START_REF] Loday | The tensor category of linear maps and Leibniz algebras[END_REF] for details. As explained in [START_REF] Krähmer | Leibniz algebras and Yetter-Drinfel'd modules[END_REF], a bialgebra object in LM consists of a bialgebra H, an H-tetramodule M and an H-bilinear coderivation f : M → H. As is well-known [8, Section 13.1.3], any Yetter-Drinfel'd module V over a bialgebra H gives rise to a tetramodule whose underlying vector space is H ⊗ V . Its actions and coactions are given by

g(h ⊗ v)g ′ := ghg ′ (1) ⊗ v • g ′ (2) , (h ⊗ v) (-1) ⊗ (h ⊗ v) (0) ⊗ (h ⊗ v) (1) = h (1) ⊗ (h (2) ⊗ v (0) ) ⊗ h (3) v (1) . Now we have: Theorem 2. If C is a cocommutative rack bialgebra, then U(C) ⊗ Č → U(C), x ⊗ y → x.q(y)
is canonically a bialgebra object in Loday-Pirashvili's category of linear maps LM. Example 4. Note that the bialgebra U(C) is not a Hopf algebra in general, i.e. does not necessarily have an antipode. For example, for C = k • 1 ⊕ k • g with △ C (g) = g ⊗ g and g ✁ g = g, we obtain for U(C) a polynomial algebra in one group-like generator which does not have an antipode. This rack bialgebra C is the counitisation of the linearisation of the conjugation rack of the trivial group. In general, if C = kX for a rack X as in Example 2, then the group algebra of the associated group of the rack X (see [START_REF] Fenn | Rourke Racks and links in codimension 2[END_REF] for definitions) is obtained by localisation of U(C) at all group-likes. For the rack bialgebra C with group-like basis 1, g and g ✁ g = 1, U(C) is the bialgebra with one group-like generator g satisfying g 2 = g, so U(C) ∼ = k ⊕ k as algebra. If U(C) does admit an antipode, then at least over an algebraically closed field of characteristic 0 it is as a Hopf algebra isomorphic to a semidirect product of a group algebra and a universal enveloping algebra of a Lie algebra (see e.g. [START_REF] Cartier | A Primer on Hopf Algebras[END_REF]Theorem 3.8.2]). Note further that there is an omission in [START_REF] Krähmer | Leibniz algebras and Yetter-Drinfel'd modules[END_REF]Lemma 4.8] as the last statement only makes sense when H is a Hopf algebra. △ Example 5. If C = k • 1 ⊕ h is the rack bialgebra associated to a Leibniz algebra h as in Example 3, then U(C) is the universal enveloping algebra of the Lie algebra h Lie associated to h, that is, the quotient by the Leibniz ideal generated by all squares [x, x]. Indeed, the generators of the ideal J are in this case of the form [x, y] + y.x -x.y, and J contains in particular all squares [x, x]. The bialgebra object in LM obtained in Theorem 2 is the universal enveloping algebra of the Lie algebra object (h, h Lie ) as in [START_REF] Loday | The tensor category of linear maps and Leibniz algebras[END_REF]Definition 4.3]. Thus Theorem 2 extends the construction of the universal enveloping algebra of a Leibniz algebra. △ Example 6. Let g be a Lie algebra, H = U(g) be its universal enveloping algebra, and C ⊂ H be the image of k ⊕ g ⊕ g ⊗ g, that is, the degree 2 part in the PBW filtration. This is a rack bialgebra following the construction in Proposition 2 (starting with Č ⊂ ker ǫ H ). The symmetric algebra U(C) is not H, but U(g ⊕ S 2 g), where S 2 g are the symmetric 2-tensors over g, viewed as abelian Lie algebra, and the direct sum is a direct sum of Lie algebras. The kernel of u : U(C) → H is the ideal generated by S 2 g. △ Remark 2. Before we continue, let us point out that U(C) differs from the Nichols algebra associated to the braided vector space ( Č, τ ). The latter can also be defined as a quotient algebra of T , but with homogeneous relations in degrees that can be of arbitrary degree, cf. [START_REF] Vendramin | Nichols algebras[END_REF] for a pedagogical introduction and original references. In contrast, the generators of J are in general inhomogeneous involving terms of degree two and one. They are homogeneous if and only if ✁ vanishes. In this case τ is the tensor flip and U(C) is the classical symmetric algebra of the vector space Č. This is the only case in which U(C) agrees with the Nichols algebra. △

A NON-COCOMMUTATIVE EXAMPLE

Up to now, all examples of rack bialgebras were cocommutative, and this was an essential assumption in our results. Also in our main reference [START_REF] Carter | Cohomology of categorical selfdistributivity[END_REF], all examples were cocommutative (note that the examples in Lemma 3.8 and Lemma 3.9 therein are isomorphic to each other). In this section, we present a non-cocommutative example of a rack bialgebra that nevertheless admits the structure of a Yetter-Drinfel'd rack and can be constructed from a bialgebra object in LM. Proposition 4. Let C = Vect(1, x, y, z, t) be the coalgebra in which t, y, z are primitives and △(x) = 1 ⊗ x + x ⊗ 1 + y ⊗ z. Then C carries a unique rack bialgebra structure in which -✁ x, -✁ t : C → C are zero and

x ✁ z = t, x ✁ y = t, z ✁ z = 0, z ✁ y = 0, y ✁ z = 0, y ✁ y = 0, t ✁ z = 0, t ✁ y = 0. Proof. The self-distributivity (a ✁ b) ✁ c = (a ✁ c (1) ) ✁ (b ✁ c (2) )
is clear if one of the three elements is 1. Otherwise, it follows from the fact that (a✁b)✁c = 0 for a, b, c ∈ Č, as then both sides of the equation vanish. Now let us check that

(a ✁ b) (1) ⊗ (a ✁ b) (2) = (a (1) ✁ b (1) ) ⊗ (a (2) ✁ b (2) ).
For b = 1, both sides are equal. For primitive b, the equation reads:

(a ✁ b) (1) ⊗ (a ✁ b) (2) = (a (1) ✁ b) ⊗ a (2) + a (1) ⊗ (a (2) ✁ b).
For b = t, both sides are clearly zero. For b = y or b = z, the only nontrivial case is a = x. We have for a = x and b = y for the LHS:

(x ✁ y) (1) ⊗ (x ✁ y) (2) = t (1) ⊗ t (2) = 1 ⊗ t + t ⊗ 1.
We have for a = x and b = y for the RHS:

(x (1) ✁ y) ⊗ x (2) + x (1) ⊗ (x (2) ✁ y) = (1 ✁ y) ⊗ x + (x ✁ y) ⊗ 1 + 1 ⊗ (x ✁ y) + x ⊗ (1 ✁ y) + (y ✁ y) ⊗ z + y ⊗ (z ✁ y) = t ⊗ 1 + 1 ⊗ t.
The case a = x and b = z is similar. The last case is the case b = x. The equation reads then:

0 = a (1) ⊗ (a (2) ✁ x) + (a (1) ✁ x) ⊗ a (2) + (a (1) ✁ y) ⊗ (a (2) ✁ z).
The first two terms (and the LHS) are zero, because -✁ x is zero. Concerning the third term, the only case where it is non-zero is when a (1) ⊗ a (2) contains a non-zero component proportional to x ⊗ x. However, there is no a with this property in C.

Since C is not cocommutative, Theorem 1 can not be applied to construct a canonical Yetter-Drinfel'd rack structure. However, C is a Yetter-Drinfel'd rack over the coordinate ring of the upper triangular unipotent group in GL(3): Proposition 5. Let H be the Hopf algebra whose underlying algebra is the polynomial ring k[X, Y, Z] with the coproduct

△(X) = 1 ⊗ X + X ⊗ 1 + Y ⊗ Z, △(Y ) = 1 ⊗ Y + Y ⊗ 1, △(Z) = 1 ⊗ Z + Z ⊗ 1.
Then the rack bialgebra C from Proposition 4 becomes a Yetter-Drinfel'd rack over H with q(x) = X, q(y) = Y, q(z) = Z, q(t) = 0.

Proof. The map q is evidently a morphism of coalgebras as k • t is a coideal. As the linear maps -✁ x, -✁ y, -✁ z : C → C commute with each other, there is a well-defined right H-module structure on C such that a ✁ b = a • q(b). The H-module coalgebra condition

(c • h) (1) ⊗ (c • h) (2) = (c (1) • h (1) ) ⊗ (c (2) • h (2)
) and ( 3) is verified by direct computation when h is one of the generators X, Y, Z and hence holds for all h ∈ H.

Thus C can be constructed as in Corollary 1 inside the Hopf algebra T ( Č) ⋊ H despite the fact that it is non-cocommutative, and as well from the corresponding Hopf algebra object in LM.

DEFORMATION COHOMOLOGY

In [START_REF] Carter | Cohomology of categorical selfdistributivity[END_REF], the authors define cohomology groups controlling the deformation theory of linear shelves. The method is to define the operations (i.e. the coproduct and the shelf product) on C[[t]] instead of C, for a formal parameter t, and then to impose self-distributivity and the coalgebra morphism condition on ✁ as well as the coassociativity of △. These requirements up to t n+1 then give cocycle identities up to t n+2 . They are realised in a bicomplex whose differentials are given explicitly up to degree 3, see Section 6 in [START_REF] Carter | Cohomology of categorical selfdistributivity[END_REF] for details.

On the other hand, in [START_REF] Alexandre | Algebraic deformation quantization of Leibniz algebras accepted in Communications in Algebra[END_REF] a deformation complex for cocommutative rack bialgebras C is defined. Therein, the deformations involve only the shelf product, and not the underlying coalgebra. Cochains are defined to be coderivations with respect to iterates of the shelf product. In [START_REF] Alexandre | Structure theory of rack bialgebras[END_REF], [START_REF] Alexandre | Algebraic deformation quantization of Leibniz algebras accepted in Communications in Algebra[END_REF], left shelves and Leibniz algebras are considered, so we transpose the definitions here to right shelves and Leibniz algebras.

Let C be a rack bialgebra with a cocommutative underlying coalgebra. Then the rack product µ(x, y) := x ✁ y can be iterated to

µ n (x 1 , . . . , x n ) := (. . . (x 1 ✁ x 2 ) ✁ . . .) ✁ x n ,
with the convention that µ 1 = id and µ 2 = µ.

Note that in the following definition we moved the Sweedler notation to the top to avoid confusion with the other indices. Definition 4. Let C be a rack bialgebra with a cocommutative underlying coalgebra. The deformation complex of C is the graded vector space C * (C; C) defined in degree n by

C n (C; C) := Coder(C ⊗n , C, µ n )
denoting the space of coderivations along µ n , i.e. of linear maps ω :

C ⊗n → C such that △ C • ω = (ω ⊗ µ n + µ n ⊗ ω) • △ C ⊗n , endowed with the differential d C : C * (C; C) → C * +1 (C; C) defined in degree n by d n C := n i=1 (-1) i+1 (d n i,1 -d n i,0 ) + (-1) n+1 d n n+1
where the maps d n i,1 and d n i,0 are defined respectively by

d n i,1 ω(r 1 , . . . , r n+1 ) := ω(r 1 , . . . , r i-1 , r (1)
i+1 , . . . , r

n+1 ) ✁ µ n-i+2 (r i , r (1)
i+1 , . . . , r

3 . . . , r

n+1 ) ✁ ω(r 2 , r (1)
3 , . . . , r

n+1 ) for all ω in C n (C; C) and r 1 , . . . , r n+1 in C.

It is shown in

[2] that d n C • d n-1 C
= 0 and that d n C sends coderivations to coderivations.

Remark 3. Cochains in the cohomology in Section 6 of [START_REF] Carter | Cohomology of categorical selfdistributivity[END_REF] are maps C ⊗i → C ⊗j , like in the Gerstenhaber-Schack cohomology of associative bialgebras. Defining special cochains as (η 1 , 0, . . . , 0) where η 1 : C ⊗n → C, one obtains that cocycles in C * (C, C) as above give rise to special cocycles. Indeed, while the first cocycle identity in [START_REF] Carter | Cohomology of categorical selfdistributivity[END_REF] is just the cocycle identity with respect to the above coboundary operator d n C , the second cocycle identity is the coderivation property and all other identities are trivial. △ Example 7. The rack bialgebra C = Vect(1, x, y, z, t) defined in Section 5 is a first order deformation in the sense of the cohomology defined in [START_REF] Carter | Cohomology of categorical selfdistributivity[END_REF] of the cocommutative shelf in coalgebras C 0 = Vect(1, x, y, z, t) where x, y, z, t are primitives and 1 is group-like. The cocycle associated to the deformation is ω : C → C ⊗2 given by ω(x) = y ⊗ z and is trivial on the other basis elements. Clearly, C is not a deformation in the sense of the cohomology defined in [START_REF] Alexandre | Algebraic deformation quantization of Leibniz algebras accepted in Communications in Algebra[END_REF] as in this complex, the coproduct is not deformed. △

We come to the main theorem of this section: ) defined above (by [START_REF] Alexandre | Algebraic deformation quantization of Leibniz algebras accepted in Communications in Algebra[END_REF]). Proof. We extend Leibniz cochains f : h ⊗n → h to cochains in the complex C * (C, C) with C = k • 1 ⊕ h by setting them zero on all components in k • 1 ⊂ C. More precisely ω((λ 1 , x 1 ), . . . , (λ n , x n )) := pr h (f (x 1 , . . . , x n )), for (λ i , x i ) ∈ k • 1 ⊕ h for all i = 1, . . . , n and with pr h : k • 1 ⊕ h → h the natural projection.

(iii) The braided Leibniz complex [START_REF] Lebed | Homologies of algebraic structures via braidings and quantum shuffles[END_REF]. Our previous article [START_REF] Krähmer | Leibniz algebras and Yetter-Drinfel'd modules[END_REF] showed how objects in the setting (ii) can be expressed as objects in the setting (iii). The present article provides the link from (i) to (ii) and from (i) to (iii) in the cocommutative case. A deformation theory for cocommutative rack bialgebras alone should however rather be built on the dual version of André-Quillen cohomology (the cohomology theory that controls deformations of commutative algebras) than the Cartier cohomology that underlies Gerstenhaber-Schack cohomology.

In general, Gerstenhaber-Schack cohomology of a bialgebra f : M → H in LM captures more information than the cohomology from [START_REF] Carter | Cohomology of categorical selfdistributivity[END_REF], as one can deform H, M and f . On the other hand, braided Leibniz cohomology seems to capture less information than [START_REF] Carter | Cohomology of categorical selfdistributivity[END_REF], because it only indirectly reflects deformations of the coproduct. A full investigation of the relation between the three settings seems a fruitful future research direction.

Two rather concrete questions that arises from this article are:

Question 1. Is there a (necessarily non-cocommutative) rack bialgebra that can not be expressed as a Yetter-Drinfel'd rack over any bialgebra?

Question 2. For which rack bialgebras is U(C) a Hopf algebra?

This matters in the passage from (ii) to (i) as the antipode is in general necessary to turn the coinvariants in a Hopf tetramodule into a right module. One expects that U is then part of an adjoint pair of functors between such Hopf racks and Hopf algebras, at least in the cocommutative setting.

Proof.

  In light of Proposition 3 and Theorem 1, any cocommutative rack bialgebra C becomes a Yetter-Drinfel'd module over H = U(C). Furthermore, the decomposition C = k • 1 ⊕ Č is a direct sum of Yetter-Drinfel'd modules. Thus M := U(C) ⊗ Č is a Hopf tetramodule. That the linear map given by s ⊗ c → sq(c) is a coderivation and a bimodule map is straightforwardly verified.

  ω(r 1 , . . . , r n+1 ) := ω(r 1 ✁ r (1) j , . . . , r j-1 ✁ r (j-1) j , r j+1 , . . . , r n+1 ) and d n n+1 by d n n+1 ω(r 1 , . . . , r n+1 ) := µ n (r 1 , r

Theorem 3 .

 3 Consider the rack bialgebra C = k ⊕ h associated to a (right) Leibniz algebra h, see Example 3. The Leibniz cohomology complex with values in the adjoint representation embeds into the deformation complex (C * (C; C), d * C

Acknowledgements. We thank Alissa Crans for interesting discussions that motivated us to work on the topic of this paper.

With this definition, it follows that these cochains are coderivations along µ n , i.e.

△ C • ω = (ω ⊗ µ n + µ n ⊗ ω) • △ C ⊗n . Indeed, when computing the iterated coproduct △ C ⊗n (r 1 , . . . , r n ), the elements r i ∈ h are distributed among the two factors in C ⊗n ⊗ C ⊗n and all other components are filled with units. On the LHS, ω(r 1 , . . . , r n ) is primitive by construction, thus we get the two terms ω(r 1 , . . . , r n ) ⊗ 1 + 1 ⊗ ω(r 1 , . . . , r n ). On the RHS, the only terms which do not vanish are those with all r i as arguments in ω. This shows the equality. Now we specify the different parts of the coboundary operator.

i+1 , . . . , r

i+1 , . . . , r

because the only contributing term is the one where all r j are arguments of ω, i.e. all the units are in µ n-i+2 .

j , . . . , r j-1 ✁ r (j-1) j

, r j+1 , . . . , r n+1 )

= ω([r 1 , r j ], . . . , r j-1 , r j+1 , . . . , r n+1 ) + . . . . . . + ω(r 1 , . . . , [r j-1 , r j ], r j+1 , . . . , r n+1 ), because only one of the r (k) j is equal to r j and all others are equal to 1.

3 . . . , r

because this is the only term where one does not insert 1 into ω. Remark 4. A similar statement is true for the rack bialgebra C associated to a (set-theoretical) shelf, cf Example 2. In fact, the deformation complex in [START_REF] Alexandre | Algebraic deformation quantization of Leibniz algebras accepted in Communications in Algebra[END_REF] has been constructed as a linearization of the cohomology complex of a shelf. △

OUTLOOK AND FURTHER QUESTIONS

One natural direction of further research is to link the three different approaches to deformation theories of rack bialgebras:

(i) The bicomplex of Carter-Crans-Elhamdadi-Saito [START_REF] Carter | Cohomology of categorical selfdistributivity[END_REF].

(ii) The Gerstenhaber-Schack bicomplex in LM [START_REF] Gerstenhaber | Schack Bialgebra cohomology, deformations, and quantum groups[END_REF].


Lu U Liu

Benoit Monin
email: benoit.monin@computability.fr

Ludovic Patey
email: ludovic.patey@computability.fr

Lacl

A COMPUTABLE ANALYSIS OF VARIABLE WORDS THEOREMS

published or not. The documents may come

Introduction

Let (N) k and (N) ∞ denote the set of partitions of N into exactly k and infinitely many non-empty pieces, respectively. For X ∈ (N) ∞ , (X) k is the set of all Y ∈ (N) k which are coarser than X.

Statement 1.1 (Dual Ramsey theorem). DRT k is the statement "If (N) k is colored with finitely many Borel colors, then there is some X ∈ (N) ∞ such that (X) k is monochromatic".

The Dual Ramsey theorem was proven by Carlson and Simpson [START_REF] Carlson | A dual form of Ramsey's theorem[END_REF], and studied from a reverse mathematical viewpoint by Slaman [START_REF] Slaman | A note on dual ramsey theorem[END_REF], Miller and Solomon [START_REF] Miller | Effectiveness for infinite variable words and the dual Ramsey theorem[END_REF] and Dzhafarov et al. [START_REF] Solomon | Effectiveness for the dual ramsey theorem[END_REF]. In this paper, we shall focus on a combinatorial lemma used by Carlson and Simpson to prove the Dual Ramsey theorem. This lemma can be formulated in terms of variable words. Definition 1.2 (Variable word). An infinite variable word on a finite alphabet A is an ω-sequence W of elements of A ∪ {x i : i ∈ N} in which all variables occur at least once, and finitely often. Moreover, the first occurrence of x i comes before the first occurrence of x i+1 . A finite variable word is an initial segment of an infinite variable word. A finite or infinite variable word is ordered if moreover all occurences of x i come before any occurrence of x i+1 . Given ā = a 0 a 1 . . . a k-1 ∈ A <ω , we let W (ā) denote the finite A-string obtained by replacing x i with a i in W and then truncating the result just before the first occcurence of x k .

Statement 1.3 (Variable word theorem). VW(n, r) is the statement "If A <ω is colored with r colors for some alphabet A of cardinality n, there exists an infinite variable word W such that {W (ā) : ā ∈ A <ω } is monochromatic. OVW(n, r) is the same statement as VW(n, r) but for ordered variable words.

In this paper, we study the computability-theoretic properties of the variable word theorems using the framework of reverse mathematics. 11.1. Reverse mathematics. Reverse mathematics is a vast foundational program aiming to determine the optimal axioms to prove ordinary theorems. It uses the framework of second-order arithmetic, with a base theory RCA 0 consisting of the axioms of Robinson arithmetic, the Σ 0 1 induction scheme and the ∆ 0 1 comprehension scheme. The system RCA 0 arguably captures computable mathematics. Starting from a proof-theoretic perspective, modern reverse mathematics tends to be seen as a framework to analyse the computability-theoretic features of theorems. Among the distinguished statements, let us mention weak König's lemma (WKL), asserting that every infinite binary tree has an infinite path, the arithmetic comprehension axiom (ACA), and the Π 1 1 comprehension axiom (Π 1 1 CA), consisting of the comprehension scheme restricted to arithmetic and Π 1 1 formulas, respectively. See Simpson [START_REF] Stephen | Subsystems of Second Order Arithmetic[END_REF] for reference book on classical reverse mathematics.

The statements studied within this framework are mainly of the form (∀X)[Φ(X) → (∃Y )Ψ(X, Y )], where Φ and Ψ are arithmetic formulas with set parameters, and can be considered as problems. Given a statement P of this form, a set X such that Φ(X) holds is an instance of P, and a set Y such that Ψ(X, Y ) holds is a solution to the P-instance X. In this paper, we shall consider exclusively statements of this kind.

Friedman and Simpson [START_REF] Friedman | Issues and problems in reverse mathematics[END_REF], and later Montalban [START_REF] Montalbán | Open questions in reverse mathematics[END_REF], asked about the reverse mathematical strength of the ordered variable word. The statement OVW(k, ) is known to be provable in RCA 0 + Π 1 1 CA. Our main result is a direct combinatorial proof of OVW(2, ) in RCA 0 + ACA. Theorem 1.4. For every ≥ 2, RCA 0 + ACA OVW(2, ).

On the lower bound hand, Miller and Solomon [START_REF] Miller | Effectiveness for infinite variable words and the dual Ramsey theorem[END_REF] constructed a computable instance c of OVW(2, 2) with no ∆ 0 2 solution, and deduced that RCA 0 + WKL does not prove VW(2, 2). Indeed, seeing the instance c of OVW(2, 2) as an instance of VW(2, 2), and noticing that the jump of a solution to VW(2, 2) gives a solution to OVW(2, 2), one can deduce that c has no low VW(2, 2)-solution. In this paper, we improve their lower bound by constructing a computable instance of OVW(2, 2) whose solutions are of DNC degree relative to ∅ .

1.2. Organization of the paper. In section 2, we shall give a simple proof of the ordered variable word for binary strings (OVW(2, )) using the finite union theorem. Then, in section 3, we provide a direct combinatorial proof of the same statement over RCA 0 + ACA. Finally, in section 4, we give a new lower bound on the strength of OVW(2, ) using a computable version of Lovasz Local Lemma. 1.3. Notation. Given two sets A and B, we write A < B for the formula (∀x ∈ A)(∀y ∈ B)x < y. Given a set A, we write A <ω for the set of finite A-valued strings. In particular, 2 <ω is the set of binary strings. We denote by P f in (N) the collection of finite non-empty subsets of N. Given two strings σ, τ ∈ A <ω , σ * τ denotes their concatenation. We may also write στ when there is no ambiguity. Given a string or a sequence X and some n ∈ ω, we write X n for the initial segment of X of length n. In particular, X 0 is the empty string, written ε.

A simple proof of the Ordered Variable Word theorem from the Finite Union Theorem

Simpson first noted a relation between Hindman's theorem and the Carlson-Simpson lemma [START_REF] Carlson | A dual form of Ramsey's theorem[END_REF]. In this section, we give a formal counterpart to his observation by giving a simple proof of OVW(2, ) using the Finite Union Theorem, a statement known to be equivalent to Hindman's theorem. A variation of the proof below was used by Dzhafarov et al. [START_REF] Solomon | Effectiveness for the dual ramsey theorem[END_REF] to give an upper bound to the Open Dual Ramsey's theorem. A direct combinatorial proof of OVW(2, ) in RCA 0 + ACA will be given in the next section. Definition 2.1. An IP collection is an infinite collection of finite sets I ⊆ P f in (N) which is closed under non-empty finite unions and contains an infinite subcollection of pairwise disjoint sets.

Note that any IP collection I necessarily contains an infinite I-computable sequence S 0 < S 1 < . . . . Statement 2.2 (Finite union theorem). For every ∈ N, FUT is the statement "For every coloring c : P f in (N) → , there is a monochromatic IP collection". wFUT 2 is the statement "For every coloring c : P f in (N) × N → , there is an IP collection I and a color i < such that c(S, min T ) = i for every S < T ∈ I."

Theorem 2.3. RCA 0 ∀ (FUT → wFUT 2 ).
Proof. Assume ≥ 2, the other cases being trivial. Let f : P f in (N) × N → be an instance of wFUT 2 . Note that over RCA 0 , FUT → ACA and ACA → COH. Let R be a sequence of set defined for every S ∈ P f in (N) and i < by R S,i = {n ∈ N : f (S, n) = i}. Apply COH to R to obtain an infinite R-cohesive set C. In particular, for every S ∈ P f in (N), lim n∈C f (S, n) exists.

Let h : ω → C be a computable bijection. Let f :

P f in (N) → be defined by f (S) = lim n∈C f (h[S], n). f is a ∆ 0,f ⊕C 2
instance of FUT , so by the finite union theorem, there is an IP collection I ⊆ P f in (N). and a color i < such that for every S ∈ I, f (S) = lim n∈C f (h[S], n) = i. Note that for every S ∈ I, min h[S] ∈ C. Therefore, by f -computably thinning-out the set I, we obtain an IP collection J ⊆ I such that for every

S < T ∈ J , f (h[S], min h[T ]) = i. The set {h[S] : S ∈ J } is a solution to f . Theorem 2.4. RCA 0 ∀ (wFUT 2 → OVW(2, )).
Proof. Let f : 2 <ω → be an instance of OVW(2, ). Define an instance g : P f in (N) × N → of wFUT 2 as follows: Given some S ∈ P f in (N) and n ∈ N, if max S < n, then set g(S, n) = f (σ), where σ is the binary string of length n defined by σ(i) = 1 iff i ∈ S. If n ≤ max S, set g(S, n) = 0. By wFUT 2 , there is an IP collection I and a color i < such that g(S, min T ) = i for every S < T ∈ I. Compute from I an infinite increasing sequence of pairwise disjoint finite sets F 0 < F 1 < . . . Let W be the infinite variable word defined by

W (n) =    1 if n ∈ F 0 x i if n ∈ F i for some i ≥ 1 0
otherwise The variable word W and the sequence of the F 's is a solution to the instance f of OVW(2, ).

Corollary 2.5. RCA 0 ACA + → ∀ OVW(2, ). Proof. Immediate since ACA + → ∀ FUT → ∀ wFUT 2 → ∀ OVW(2, ) over RCA 0 .

A proof of the Ordered Variable Word theorem in ACA

The proof of the previous section gave a very coarse computability-theoretic upper bound of the Ordered Variable Word theorem in terms of ω-jumps. In this section, we give a direct combinatorial proof of OVW(2, ) in RCA 0 + ACA. Actually, every PA degree relative to ∅ is sufficient to compute a solution of a computable instance of OVW (2, ). We thereby answer a question of Miller and Solomon [START_REF] Miller | Effectiveness for infinite variable words and the dual Ramsey theorem[END_REF].

Theorem 3.1. For every ∈ ω, every computable instance c of OVW(2, ), every PA degree over ∅ computes a solution to c.

A formalization of Theorem 3.1 yields a proof of Theorem 1.4.

Proof of Theorem 1.4. The proof of Theorem 3.1 can be formalized within RCA 0 + ACA. Indeed, the arguments require only arithmetical induction to be carried out, and every model of RCA 0 + ACA is a model of the statement "For every set X, there is a set of PA degree over the jump of X."

Let us first introduce some notation. For a finite set F and a string σ ∈ 2 <ω let σ F be the binary string of length |σ| defined by σ F (i) = σ(i) if i ∈ F , and σ F (i) = 1 -σ(i) otherwise. Let ≤ lex denote the shortlex order on ω <ω , that is, the order with the shortest length first, and with the strings of same length sorted lexicographically.

In what follows, fix a coloring c : 2 <ω → , and a string ρ ∈ 2 <ω . The main combinatorial lemma we use is Lemma 3.4. As a warm up, we first prove the following lemma 3.2, which is a consequence of Lemma 3.4 and the proof is somehow similar but much simpler. In the following lemma, one may think of ρ P as a finite variable word, where the positions at P are replaced by a same variable kind.

Lemma 3.2. For any

P ⊆ {0, • • • , |ρ| -1} with (∀n ∈ P )[ρ(n) = 0] ∧ |P | ≥ , there exist two subsets P < P of P with P = ∅ such that c(α) = c(α P ) where α = ρ P . Proof. Suppose P = {p 0 < • • • < p m-1 }. Let 0 , .
. . , m be defined by i = c(ρ {p0,...,pi-1} ). In particular,

0 = c(ρ). Since |P | = m ≥ , so among 0 , • • • , m , there must exists i < j such that i = j . Let P = {p 0 , • • • , p i-1 } (if i = 0 then P = ∅), and P = {p i , • • • , p j-1
}, let α = ρ P . Clearly P < P and P = ∅.

It is also easy to see that c(α) = i = j = c(α P ).

We now prove a technical lemma used in the proof of our main combinatorial lemma (Lemma 3.4). The sequence in the following lemma is obtained by a simple greedy algorithm, with finitely many resets.

Lemma 3.3. There exists a nonempty set of colors

L ⊆ {0, 1, • • • , -1}, |L| + 1 many sets of binary strings Γ 0 = {τ η } η∈L , Γ 1 = {τ η } η∈L 2 , • • • , Γ |L| = {τ η } η∈L |L|+1 , such that, letting η = max L * max L * • • • * max L |L|+1 many
and letting ρ = τ η * 0, the following holds:

(1) ρ ≺ Γ 0 and τ η ≺ τ β ⇔ η < lex β; (2) ρ(|τ |) = 0 for all τ ∈ Γ i , i ≤ |L|; (3) for all i ≤ |L|, η ∈ L i+1 , let η 0 ≺ η 1 ≺ • • • ≺ η i-1 denote all nonempty predecessors of η, let Q = |τ η0 |, |τ η1 |, • • • , |τ ηi-1 | (if i = 0 then Q = ∅), then c(τ η Q ) = η(i); (4) let P = {|τ η |} η∈L ≤|L|+1 , for all subset Q of P , all τ ρ, c τ Q ∈ L. Moreover, Γ i , i ≤ |L| is computable in the jump of c, uniformly in ρ.
Proof. We firstly show how to find Γ 0 . Start with L = {0, 1, • • • , -1}. At step 1, try to find a string τ ∈ 2 <ω such that c(ρτ ) = 0 and let τ 0 = ρτ . Then try to find a τ such that c(τ 0 0τ ) = 1 and let τ 1 = τ 0 0τ . Generally, after τ j is found, try to find τ such that c(τ j 0τ ) = j + 1 and let τ j+1 = τ j 0τ if τ is found. If during the above process, after τ j-1 is defined ( τ -1 = ρ ), there is no τ such that c(τ j-1 0τ ) = j, then we start all over again with ρ replaced by ρ 1 = τ j 0 and with L replaced by L {j}.

Generally, given a set of colors L and after τ β is found, let η be the immediate successor (with respect to ≤ lex order restricted to L-strings) of β, let

η 0 ≺ η 1 ≺ • • • ≺ η i-1 denote all nonempty predecessors of η, let Q = |τ η0 |, |τ η1 |, • • • , |τ ηi-1 | (if i = 0 then Q = ∅), we try to find τ such that c((τ β 0τ ) Q ) = η(|η| -1).
If such a string τ does not exists then we start all over again with ρ replaced by τ β 0 Q and L replaced by L {η(|η| -1)}. If such τ exists then let τ η = τ β 0τ .

Note that we have to start over for at most -1 times before we ultimately succeed since there are colors in total. It is plain to check all the four items. Also note that the sequence Γ 0 , • • • , Γ |L| is c -computable since we only need to use the jump of c to know whether the next τ η can be found. We say that (ρ, P ) is c-valid if P and ρ satisfy Lemma 3.4. We say that (P , P ) witnesses c-validity of (ρ, P ) for σ ρ if P < P ⊆ P , and letting α = σ P , c(α) = c(α P ) = c(α min P ). Before proving Theorem 3.1, we start with the following simpler version. Theorem 3.5. For every ∈ ω, every computable instance c : 2 <ω → of OVW(2, ), every P A degree over ∅ computes a solution to c.

p i = |τ 0••• i | (where τ 0 ••• i ∈ Γ i ). Since 0 , • • • , |L| ∈ L (by item 4 of Lemma 3.3), there is some i < j ≤ |L| such that i = j . Let P = {p 0 , • • • , p i-1 } (if i = 0 then P = ∅), P = {p i , • • • , p j-
P i ⊆ |ρ i |, • • • , |ρ i+1 | -1 be such that (ρ i+1 , P i )- is c i -valid,
and let c i+1 be the coloring of [ρ i+1 ] which on σ ρi+1 associates P , P , j such that (P , P ) witnesses c i -validity of (ρ i+1 , P i ) for σ, and c i (σ P ) = j. If there are multiple such tuples, take the least one, in some arbitrary order. Note that the range of c i is some finite set L i .

We now analyze for σ ρi what c i (σ) = P , P , j means. Note that elements of L i , i ∈ ω admit a natural partial order ¡ as follows: for P 0 , P0 , j 0 ∈ L i , P 1 , P1 , j 1 ∈ L i+1 , P 1 , P1 , j 1 is an immediate successor of P 0 , P0 , j 0 if and only if j 1 = P 0 , P0 , j 0 . Clearly every j ∈ L i admit a unique immediate predecessor. Claim 3.6. Fix some n ≥ 1, and let ˜ ¡ P 0 , P0 , j 0 ¡ • • • ¡ P n-1 , Pn-1 , j n-1 = c n (σ), Let P = i≤n-1 P i and α = σ P . Then for any subset

J of {0, • • • , n -1}, (∀p ∈ min Pj : 1 ≤ j ≤ n -1 ∪ {|α|}) c(α PJ p) = ˜ .
Proof. First we prove the claim for n = 1. By definition of c 1 (σ) = P 0 , P0 , j 0 , letting β = σ P 0 , c 0 (β) = c 0 (β P0 ) = j 0 = ˜ . In other words, for any subset J ⊆ {0},

(∀p ∈ min{ Pj : 1 ≤ j ≤ 0} ∪ {|β|}) c(β PJ p) = ˜ .
So the claim holds for n = 1. Suppose now the claim holds for n -1.

Suppose

c n (σ) = P n-1 , Pn-1 , j n-1 . Let β = σ P n-1 . We have c n-1 (β) = c n-1 (β Pn-1 ) = c n-1 (β min Pn-1 ) = j n-1 = P n-2 , Pn-2 , j n-2 . As c n-1 (β) = P n-2
, Pn-2 , j n-2 and as ˜ ¡ P n-2 , Pn-2 , j n-2 , by induction hypothesis, for any subset J of {0, • • • , n -2} we have:

c(β (∪ i≤n-2 P i )∪ PJ ) = ˜ . (3.1)
Let β = β Pn-1 . As c n-1 (β ) = P n-2 , Pn-2 , j n-2 and as ˜ ¡ P n-2 , Pn-2 , j n-2 , by induction hypothesis, for any subset J of {0, • • • , n -2} we have:

c(β (∪ i≤n-2 P i )∪ PJ ) = ˜ . (3.2)
As c n-1 (β min Pn-1 ) = P n-2 , Pn-2 , j n-2 and as ˜ ¡ P n-2 , Pn-2 , j n-2 , by induction hypothesis, for any subset J of {0, • • • , n -2} we have:

(∀p ∈ min Pj : 1 ≤ j ≤ n -2 ∪ |β min Pn-1 | ) c(β (∪ i≤n-2 P i )∪ PJ p) = ˜ . (3.
(∀p ∈ min Pj : 1 ≤ j ≤ n -1 ∪ {|β|}) c(β (∪ i≤n-2 P i )∪ PJ p) = ˜ which completes the proof of the claim since β ∪ i≤n-2 P i = α. Let T 0 be the ∅ -computable set of all γ such that (∀i ≤ |γ|)[γ(i) ∈ L i ], γ(i) ¡ γ(i + 1) and γ(|γ| -1) = c |γ|-1 (ρ |γ| ).
Then, let T be the downward closure of the set T 0 by the prefix relation. The tree T is infinite by construction of the strings ρi , the colors c i and the sets P i : a witness for the c i -validity of (ρ i+1 , P i+1 ) for ρ i+1 yields a node of T 0 of length i + 2. The tree T is also ∅ -computably bounded, and ∅ -computable. Let j 0 * P 0 , P0 , j 0 * P 1 , P1 , j 1 * • • • be an infinite path through T computed by any PA degree over ∅ . By construction, P i , Pi , j i ¡ P i+1 , Pi+1 , j i+1 . Let X = i∈ω ρi , P = i∈ω P i and let Y = X P . Clearly (∀i∀n ∈ Pi )[Y (n) = 0] and Y is computable in the given PA degree relative to ∅ . Therefore, letting P osition = min Pi : i ≥ 1 , it suffices to show that for all subsets J of ω,

(∀p ∈ P osition) c(Y PJ p) = j 0 ].
Without loss of generality, suppose p = min Pn and J ⊆ {0, • • • , n-1}. Since j 0 * P 0 , P0 , j 0 * P 1 , P1 , j 1 * • • • P n , Pn , j n is an initial segment of some element in T 0 , there must exist some N > n such that c N (ρ

N +1 ) = P N -1 , PN-1 , j N -1 . Let σ = ρN+1 , α = σ P . Clearly α ≺ Y ∧ |α| > p. Moreover, by Claim 3.6, c(α PJ p) = j 0 . Thus c(Y PJ p) = j 0 .
Finally, we slightly modify the proof of Theorem 3.5 to derive Theorem 3.1.

Proof of Theorem 3.1. The main point is to make the tree T ∅ -computable. To ensure this, after we obtain ρi , c i , we do not directly go to ρi+1 . Instead, we ∅ -compute ρ0

i ≺ ρ1 i ≺ • • • ≺ ρri i such that ρ0 i ρi and c i {τ : τ ρri i } ⊆ c i ρ0 i , • • • , ρri i .
Then we ∅ -compute ρi+1 ρri i as in the proof of Theorem 3.5. Note that this indeed can be achieved using ∅ since c i is computable. Define T to be the set of all γ such that (∀i ≤ |γ|)[γ(i) ∈ L i ], γ(i) ¡ γ(i + 1), and either |γ| = 1 ∧ γ ∈ L 0 or there exists ρu |γ|-1 with c |γ|-1 (ρ u |γ|-1 ) = γ(|γ| -1). It is easy to see that T is ∅ -computable since c i is computable for all i and the sequences c i : i ∈ ω and ρv i : i ∈ ω, v ≤ r i are ∅ -computable. Now we show that T is a tree. Suppose γ ∈ T , |γ| = n+1 with n ≥ 1, and c n (ρ u n ) = γ(n) = P , P , j ∈ L n . We claim that γ n ∈ T . If n = 1, then γ 1 ∈ L 0 ⊆ T . Otherwise, let Q , Q, k ∈ L n-1 be the predecessor of P , P , j . We need to show that there exists ρv

n-1 such that c n-1 (ρ v n-1 ) = Q , Q, k . c n (σ) = P , P , j implies that, letting α = σ P , c n-1 (α) = c n-1 (α min P ) = j = Q , Q, k . Note that α ρrn-1 n-1 since P > |ρ rn-1 n-1 |. But c n-1 {τ : τ ρrn-1 n-1 } ⊆ c n-1 {ρ 0 n-1 , • • • , ρrn-1 n-1 } . Therefore there exists ρu n-1 such that c n-1 (ρ u n-1 ) = Q , Q, k .
It follows that γ n ∈ T and that T is a tree. Any PA degree relative to ∅ computes an infinite path through T . The rest of the proof goes exactly the same as Theorem 3.5.

We now give an alternative proof of Theorem 3.1 based on the definitional complexity of the solutions of c.

Second proof of Theorem 3.1. Let P 0 , P 1 , . . . be the ∅ -computable sequence defined in the proof of Theorem 3.5. We have seen that there exists an infinite ordered variable word such that the nth variable kind appears before the position max P n . Let T be the tree of all finite ordered variable words which are finite solutions to c and such that the nth variable appears before the position max P n . By the previous observation, the tree is infinite, ∅ -computable, and ∅ -computably bounded. Any PA degree relative to ∅ computes an infinite variable word which, by construction of T , is a solution to c. This completes the proof of Theorem 3.1.

Note that the above proof can be slightly modified to obtain a proof of a sequential version of the ordered variable word. Statement 3.7. SeqOVW(n, ) is the statement "If c 0 , c 1 , . . . is a sequence of -colorings of a fixed alphabet A of cardinality n, there exists a variable word W such that for every i ∈ ω and every b ∈ A i , {W ( bā) : ā ∈ A <∞ } is monochromatic for c i ." Theorem 3.8. For every computable instance c 0 , c 1 , . . . of SeqOVW(2, ), every PA degree relative to ∅ computes a solution to c.

Proof. The proof is similar to Theorem 3.1. Using Lemma 3.4, we first construct a ∅ -computable sequence of strings ρ0 ≺ ρ1 ≺ • • • , a sequence of finite sets

P i ⊆ |ρ i-1 |, • • • , |ρ i | -1 and a sequence of colorings d i : [ρ i ] → L i inductively as follows. ρ0 = ε and d 0 = c 0 . Given ρi and d i : [ρ i ] → L i , let ρi+1
ρi and

P i ⊆ |ρ i |, • • • , |ρ i+1 | -1 be such that (ρ i+1 , P i )-is d i -valid,
and let d i+1 be the coloring of [ρ i+1 ] which on σ ρi+1 associates P , P , j, k such that (P , P ) witnesses d i -validity of (ρ i+1 , P i ) for σ, d i (σ P ) = j and c i+1 (σ P ) = k. Note that the main difference with the previous construction is that we handle more and more colorings among c 0 , c 1 , . . . at each level. The remainder of the proof is the same as in Theorem 3.1.

The theorem above is optimal, in that we can obtain the following reversal. Theorem 3.9. There is a computable instance c 0 , c 1 , . . . of SeqOVW(2, 2), such that every solution is of PA degree relative to ∅ .

Proof. Let R 0 , R 1 , . . . be a uniformly computable sequence of sets such that for every e, if Φ ∅ e (e) ↓= 0 then R e is finite, and if Φ ∅ e (e) ↓= 1 then R e is cofinite. In particular, any function f : ω → 2 such that f (e) gives a side of R e which is infinite, is DNC 2 relative to ∅ , hence of PA degree relative to ∅ . Let c i : 2 <∞ → 2 be defined by c i (σ) = 1 iff |σ| ∈ R i , and let W be a solution to c, that is, a variable word W such that for every i ∈ ω and every b ∈ A i , {W ( bā) : ā ∈ A <∞ } is monochromatic for c i . We claim that W computes such a function f . Given e, let f (e) = c e (W ( b)), where b ∈ 2 e is arbitrary (this is well-defined, since c e ( b) depends only on the length of b). By definition of W , {W ( bā) : ā ∈ A <∞ } is monochromatic for c e , the color of c e (W ( b)) appears infinitely often in R e . Therefore, W is of PA degree relative to ∅ . This completes the proof.

A difficult instance of the Ordered Variable Word theorem

Miller and Solomon [START_REF] Miller | Effectiveness for infinite variable words and the dual Ramsey theorem[END_REF] constructed a computable instance of OVW(2, 2) with no ∆ 0 2 solution. In this section, we strengthen their proof by constructing a computable instance of OVW(2, 2) such that every solution is of DNC degree relative to ∅ , using a significantly simpler argument.

The proof makes an essential use of a computable version of Lovasz Local Lemma proven by Rumyantsev and Shen [START_REF] Rumyantsev | Probabilistic constructions of computable objects and a computable version of lovász local lemma[END_REF]. The idea of using Lovasz Local Lemma to analyse the computability-theoretic strength of problems in reverse mathematics comes from Csima and Dzhafarov, Hirschfeldt, Jockusch, Solomon and Westrick [START_REF] Barbara F Csima | The reverse mathematics of hindman's theorem for sums of exactly two elements[END_REF], who proved that a version of Hindman's theorem for subtractions is not computably true. Definition 4.1. Fix a countable set of variables x 0 , x 1 , . . . A (disjunctive) clause C is a tuple of the form

(x n1 = i 1 ∨ • • • ∨ x n k = i k ), with i 1 , . . . , i k < 2.
The length of C is the integer k. An infinite CNF formula is an infinite conjunction of disjunctive clauses. An infinite CNF formula n C n is computable if the function which given n outputs a code for C n is computable, and the set of n such that C n contains the variable x j is uniformly computable in j. Theorem 4.2 (Rumyantsev and Shen [START_REF] Rumyantsev | Probabilistic constructions of computable objects and a computable version of lovász local lemma[END_REF]). For every α ∈ (0, 1), there exists some N ∈ ω such that every computable infinite CNF where each variable appears in at most 2 αn clauses of size n (for every n) and all clauses have size at least N , has a computable satisfying assignment.

Theorem 4.3.

There is a computable instance c of OVW(2, 2) and a computable function h : ω → ω such that if Φ ∅ e outputs a finite variable word in which the first h(e) variable kinds occur, then Φ ∅ e is not extendible into an infinite solution to c.

Proof. Fix α = 0.5, and let N be the threshold of Theorem 4.2. For every index e and stage s, we interpret Φ ∅ e [s] as a finite variable word W e,s with exactly N + e variable kinds, and where a new variable occurs right after W e,s . Such a variable word induces a binary tree T e,s with 2 N +e leaves. Let L e,s be the set of leaves of T e,s , that is, the set of all instantiations of the variable word W e,s . Moreover, all the leaves of T e,s have the same length n e,s .

The idea is the following: since the variable word is ordered and a new variable kind occurs right after W e,s , no variable among the first N + e variables can occur after W e,s . If W is a solution to c with initial segment W e = lim s W e,s for some color i, then W must be homogeneous for c for every instance of the variables, so in particular when setting all the variables after the N + e first ones to 0. Hence, there must be infinitely many strings τ such that for every σ ∈ lim s L e,s , c(στ ) = i. By ensuring that for cofinitely many τ , there is some σ ∈ L e,|τ | such that c(στ ) = i, we force W e not to be a solution to c for color i.

Fix a countable collection of variables (x ρ : ρ ∈ 2 <ω ). Each variable x ρ corresponds to the color of the string ρ. Given some s ∈ ω, τ ∈ 2 <ω and some i < 2, if n e,s + |τ | = s, then let C e,s,τ,i be the disjunctive e is not extendible into an infinite solution to c. Definition 4.4. A function f : ω → ω is diagonally non-computable relative to X (or X-dnc) if for every e, f (e) = Φ X e (e). Corollary 4.5. There is a computable instance c of OVW(2, 2) such that every solution is of ∅ -dnc degree.

Proof. Let c and h be as in Theorem 4.3. For every e, let α e be a computable bijection from the finite variable words in which the first h(e) variable kinds occur, to the set of the integers. By Kleene's fixpoint theorem, there is a computable function g : ω → ω such that for every e, Φ ∅ g(e) = α -1 g(e) (Φ ∅ e (e)). Let W be a solution to c, that is, an infinite variable word. Let f be the W -computable function defined by f (e) = α g(e) (w e ), where w e is the first initial segment of W in which the first h(g(e)) variable kinds occur. We claim that f is ∅ -dnc. Indeed, given e ∈ ω, w e = Φ ∅ g(e) , so f (e) = α g(e) (w e ) = α g(e) (Φ ∅ g(e) ) = Φ ∅ e (e) This completes our proof.

We conclude this section with a small computational observation about VW(2, 2) based on the syntactical form of the statement. Definition 4.6. A function g : ω → ω dominates f : ω → ω if (∀x)f (x) < g(x). A function f : ω → ω is hyperimmune if it is not dominated by any computable function. A Turing degree is hyperimmune-free if it does not contain any hyperimmune function.

Lemma 4.7 (Folklore). Let P be a statement of the form (∀X)[Φ(X) → (∃Y )Ψ(X, Y )] where Φ is an arbitrary predicate, and Ψ is a Π 0 2 predicate. For every computable instance I of P, if I has a solution of hyperimmune-free degree, then every PA degree computes a solution to I.

Proof. Say Ψ(X, Y ) ≡ (∀x)(∃y)Θ(X y, Y y, x, y), where Θ is a decidable predicate. Let I be a computable P-instance with a solution S of hyperimmune-free degree. Let h : ω → ω be the S-computable function such that for every x, Θ(I, S, x, h(x)) holds. In particular, there is a computable function g : ω → ω such that (∀x) max(h(x), S(x)) < g(x). Let T ⊆ ω <ω be the computably bounded tree defined by T = σ ∈ ω <ω :

(∀x < |σ|)σ(x) < g(x))∧ (∀x < |σ|)[g(x) < |σ| → (∃y < |σ|)Θ(I y, σ y, x, y)]

In particular, S ∈ [T ], so the tree is infinite. Moreover, any R ∈ [T ] is a solution to I, and any PA degree computes a member of [T ]. This completes the proof.

Corollary 4.8. There is a computable instance of VW(2, 2) such that every solution is of hyperimmune degree.

Proof. First, note that the statement VW(2, 2) is of the form of Lemma 4.7. Let c : 2 <ω → 2 be the computable instance of VW(2, 2) with no low solution constructed by Miller and Solomon [START_REF] Miller | Effectiveness for infinite variable words and the dual Ramsey theorem[END_REF] or by Theorem 4.3.

Letting d be a low PA degree, d computes no solution to c, hence by Lemma 4.7, every solution to c is of hyperimmune degree.

It is still unknown whether there is a computable instance of OVW(2, 2) such that every solution is PA over ∅ , or even just computes ∅ . In particular the following questions remain open: Question 4.9. Does VW(2, 2) or OVW(2, 2) imply ACA over RCA 0 ? Question 4.10. Is there a computable instance of VW(2, 2) or OVW(2, 2) such that the measure of oracles computing a solution to it is null?

Lemma 3 . 4 .

 34 There exists a string ρ ρ and a finite setP ⊆ |ρ|, • • • , |ρ| -1 with (∀i ∈ P )[ρ(i) = 0]such that for all σ ρ there exists two subsets P < P of P with P = ∅ such that, letting α = σ P , c(α) = c(α P ) = c(α min P ). Moreover, |P | < +2 , and ρ, P , are computable in the jump of c, uniformly in ρ.Proof. Let L and ρ satisfy Lemma 3.3. We claim that ρ and P = {|τ η |} η∈L ≤|L|+1 satisfy the current lemma. It is clear by item 1 of Lemma 3.3 that ρ ρ and by item 2 of Lemma 3.3 that (∀i ∈ P )[ρ(i) = 0].Fix an arbitrary σ ρ. We now describe how to construct P and P . Define 0 , . . . , |L| and p 0 , . . . , p |L| inductively by 0 = c(σ), i+1 = c(σ {p0,p1,••• ,pi} ), and

  1 }, and let α = σ P . We claim that c(α) = c(α P ) = c(α min P ). Note that min P =p i = |τ 0••• i |. Therefore α min P = τ 0••• i P . By item 3 of Lemma 3.3, we have c(τ 0••• i P ) = i .Meanwhile, by definition of i , c(σ P ) = c(α) = i . By definition of j , c(σ P ∪ P ) = c(α P ) = j . Thus, c(α) = c(α P ) = c(α min P ).

Proof.

  It suffices to compute, given a PA degree relative to ∅ , an infinite binary sequence Y ∈ 2 ω together with a sequence of finite sets P0 < P1 < • • • with (∀i ∈ ω)(∀n ∈ Pi )[Y (n) = 0] such that the following holds: Let P osition = min Pi : i ≥ 1 . There is some ˜ < such that for all subset J of ω, letting PJ = i∈J Pi , then we have, (∀p ∈ P osition) c(Y PJ p) = ˜ ]. Using Lemma 3.4, we first construct a ∅ -computable sequence of strings ρ0 ≺ ρ1 ≺ • • • , a sequence of finite sets P i ⊆ |ρ i-1 |, • • • , |ρ i | -1 and a sequence of colorings c i : [ρ i ] → L i inductively as follows. ρ0 = ε and c 0 = c. Given ρi and c i : [ρ i ] → L i , let ρi+1 ρi and

3 )

 3 But |β min Pn-1 | = min Pn-1 . So (3.3) means for any subset J of {0, • • • , n -2} we have:(∀p ∈ min Pj : 1 ≤ j ≤ n -1 ) c(β (∪ i≤n-2 P i )∪ PJ p) = ˜ .Or equivalently, for any subset J of {0, • • • , n -1} we have:(∀p ∈ min Pj : 1 ≤ j ≤ n -1 ) c(β (∪ i≤n-2 P i )∪ PJ p) = ˜ . (3.4)Now from 3.1, 3.2 and 3.4 we deduce that for any subset J of {0, • • • , n -1} we have:

  2 N +e -clause {x στ = i : σ ∈ L e,s }.This infinite CNF formula is clearly computable. Clearly C e,s,τ,i has length 2 N +e . Note that for every ρ, e, there exists at most one τ such that (∃σ ∈ L e,|ρ| )[στ = ρ]. Therefore, each variable x ρ appears in at most 2 clauses of length 2 N +e , namely, C e,|ρ|,τ,0 and C e,|ρ|,τ,1 , where τ is such that (∃σ ∈ L e,|ρ| )[στ = ρ]. Therefore, this formula satisfies the conditions of Theorem 4.2, and has a computable assignment c : 2 <ω → 2. By construction, letting h(e) = N + e + 1, the formula ensures that if Φ ∅ e outputs a finite variable word in which the first h(e) variables kinds occur, then Φ ∅

	And let C be the conjunction

ne,s+|τ |=s {C e,s,τ,i : e ∈ ω, τ ∈ 2 <ω , i < 2}.

The authors thank Damir Dzhafarov, Stephen Flood, Reed Solomon and Linda Brown Westrick for bringing the attention of the authors to the Carlson-Simpson lemma, and for numerous discussions. The authors are also thankful to Denis Hirschfeldt and Barbara Csima for showing them how to use Lovasz Local Lemma to prove lower bounds to combinatorial theorems.1