Donatien Gaparayi

A Nourou Issa

A Twisted Generalization of Lie-Yamaguti Algebras

Keywords: Mathematics Subject Classification: 17A30, 17D99 Lie-Yamaguti algebra (i.e. generalized Lie triple system, Lie triple algebra), Malcev algebra, Hom-Lie algebra, Hom-Lie triple system, Hom-Nambu algebra, Hom-Akivis algebra

A twisted generalization of Lie-Yamaguti algebras, called Hom-Lie-Yamaguti algebras, is defined. Hom-Lie-Yamaguti algebras generalize multiplicative Hom-Lie triple systems (and subsequently ternary multiplicative Hom-Nambu algebras) and Hom-Lie algebras in the same way as Lie-Yamaguti algebras generalize Lie triple systems and Lie algebras. It is shown that the category of (multiplicative) Hom-Lie-Yamaguti algebras is closed under twisting by self-morphisms. Constructions of Hom-Lie-Yamaguti algebras from ordinary Lie-Yamaguti algebras and Malcev algebras are given. Using the well-known classification of real two-dimensional Lie-Yamaguti algebras, examples of real two-dimensional Hom-Lie-Yamaguti algebras are given.

Introduction

Using the Bianchi identities, K. Nomizu [START_REF] Nomizu | Invariant affine connections on homogeneous spaces[END_REF] characterized, by some identities involving the torsion and the curvature, reductive homogeneous spaces with some canonical connection. K. Yamaguti [START_REF] Yamaguti | On the Lie triple system and its generalization[END_REF] gave an algebraic interpretation of these identities by considering the torsion and curvature tensors of Nomizu's canonical connection as a bilinear and a trilinear algebraic operations satisfying some axioms, and thus defined what he called a "general Lie triple system". M. Kikkawa [START_REF] Kikkawa | Geometry of homogeneous Lie loops[END_REF] used the term "Lie triple algebra" for such an algebraic object. More recently, M.K. Kinyon and A. Weinstein [START_REF] Kinyon | Leibniz algebras, Courant algebroids and multiplications on reductive homogeneous spaces[END_REF] introduced the term "Lie-Yamaguti algebra" for this object.

A Lie-Yamaguti algebra (V, * , {,,}) is a vector space V together with a binary operation * : V ×V → V and a ternary operation {,,} : V ×V ×V → V such that (LY1) x * y = -y * x, (LY2) {x, y, z} = -{y, x, z}, (LY3) (x,y,z) [(x * y) * z + {x, y, z}]=0, (LY4) (x,y,z) {x * y, z, u} =0, (LY5) {x, y, u * v} = {x, y, u} * v + u * {x, y, v}, (LY6) {x, y, {u, v, w}} = {{x, y, u},v,w} + {u, {x, y, v},w} +{u, v, {x, y, w}}, for all u, v, w, x, y, z in V and (x,y,z) denotes the sum over cyclic permutation of x, y, z.

In [START_REF] Benito | Irreducible Lie-Yamaguti algebras[END_REF] the notation "LY-algebra" is used for "Lie-Yamaguti algebra". So, likewise, below we will write "Hom-LY algebra" for "Hom-Lie-Yamaguti algebra".

Observe that if x * y = 0, for all x, y in V , then (V, * , {,,}) reduces to a Lie triple system (V, {,,}) as defined in [START_REF] Yamaguti | On algebras of totally geodesic spaces (Lie triple systems)[END_REF]. From the other hand, if {x, yz, } =0 for all x, y, z in V , then (V, * , {,,}) is a Lie algebra (V, * ). Originally, N. Jacobson [START_REF] Jacobson | Lie and Jordan triple systems[END_REF] defined a Lie triple system as a submodule of an associative algebra that is closed under the iterated commutator bracket.

In this paper we consider a Hom-type generalization of LY algebras that we call Hom-LY algebras. Roughly, a Hom-type generalization of a given type of algebras is defined by twisting the defining identities of that type of algebras by a self-map in such a way that, when the twisting map is the identity map, one recovers the original type of algebras. The systematic study of Hom-algebras was initiated by A. Makhlouf and S.D. Silvestrov [START_REF] Makhlouf | Hom-algebras structures[END_REF], while D. Yau [START_REF] Yau | Hom-algebras and homology[END_REF] gave a general construction method of Hom-type algebras starting from usual algebras and a twisting self-map. For information on various types of Hom-algebras, one may refer to [START_REF] Atagema | Generalization of n-ary Nambu algebras and beyond[END_REF], [START_REF] Issa | Hom-Akivis algebras[END_REF], [START_REF] Makhlouf | Hom-alternative algebras and Hom-Jordan algebras[END_REF]- [START_REF] Makhlouf | Hom-algebras structures[END_REF], [START_REF] Yau | Enveloping algebra of Hom-Lie algebras[END_REF]- [START_REF] Yau | On n-ary Hom-Nambu and Hom-Nambu-Lie algebras[END_REF].

A Hom-type generalization of n-ary Lie algebras, n-ary Nambu algebras and n-ary Nambu-Lie algebras (i.e. Filippov n-ary algebras) called n-ary Hom-Lie algebras, n-ary Hom-Nambu algebras and n-ary Hom-Nambu-Lie algebras respectively, is considered in [START_REF] Atagema | Generalization of n-ary Nambu algebras and beyond[END_REF]. Such a generalization is extended to the one of Hom-Lie triple systems and Hom-Jordan triple systems in [START_REF] Yau | On n-ary Hom-Nambu and Hom-Nambu-Lie algebras[END_REF]. We point out that the class of (multiplicative) Hom-LY algebras encompasses the ones of multiplicative ternary Hom-Nambu algebras, multiplicative Hom-Lie triple systems (hence Jordan and Lie triple systems), Hom-Lie algebras (hence Lie algebras) and LY algebras.

The rest of the paper is organized as follows. In section 2 some basic facts on Hom-algebras and n-ary Hom-algebras are recalled. The emphasis point here is that the definition of a Hom-triple system (Definition 2.3) is more restrictive than the D. Yau's in [START_REF] Yau | On n-ary Hom-Nambu and Hom-Nambu-Lie algebras[END_REF]. However, with this vision of a Hom-triple system, we point out that any non-Hom-associative algebra (i.e. nonassociative Hom-algebra or Hom-nonassociative algebra) has a natural structure of (multiplicative) Hom-triple system (this is the Hom-counterpart of a similar well-known result connecting nonassociative algebras and triple systems). Then we give the definition of a Hom-LY algebra and make some observations on its relationships with some types of ternary Hom-algebras and with LY algebras. In section 3 we show that the category of Hom-LY algebras is closed under twisting by self-morphisms (Theorem 3.1). Subsequently, we show a way to construct Hom-LY algebras from LY algebras (or Malcev algebras) by twisting along self-morphisms (Corollary 3.2 and Corollary 3.3); this is an extension to binary-ternary algebras of a result due to D. Yau ([23], Theorem 2.3. Such an extension is first mentioned in [START_REF] Issa | Hom-Akivis algebras[END_REF], Corollary 4.5). In section 4 examples of real two-dimensional Hom-LY algebras are constructed, relaying on the classification of (real) two-dimensional LY algebras [START_REF] Issa | Classifying two-dimensional hyporeductive triple algebras, Intern[END_REF], [START_REF] Yamaguti | On cohomology groups of general Lie triple systems[END_REF].

All vector spaces and algebras throughout are considered over a ground field K of characteristic 0.

Ternary Hom-algebras. Definitions

We recall some basic facts about Hom-algebras, including ternary Hom-Nambu algebras. We note that the definition of a Hom-triple system given here (see Definition 2.3) is slightly more restrictive than the one given by D. Yau [START_REF] Yau | On n-ary Hom-Nambu and Hom-Nambu-Lie algebras[END_REF].

Then we give the definition of the main object of this paper (see Definition 2.6) and show its relationships with known structures such as ternary Hom-Nambu algebras, Hom-Lie triple systems, Hom-Lie algebras or Lie-Yamaguti algebras.

For definitions of n-ary Hom-algebras (n-ary Hom-Nambu and Hom-Nambu-Lie algebras, n-ary Hom-Lie algebras, etc.) we refer to [START_REF] Atagema | Generalization of n-ary Nambu algebras and beyond[END_REF], [START_REF] Yau | On n-ary Hom-Nambu and Hom-Nambu-Lie algebras[END_REF]. For information on origins of Nambu algebras, one may refer to [START_REF] Nambu | Generalized Hamiltonian dynamics[END_REF], [START_REF] Takhtajan | On foundation of the generalized Nambu mechanics[END_REF]. Here, for our purpose, we restrict our concern to ternary Hom-algebras. In fact, as we shall see below, a Hom-Lie-Yamaguti algebra is some multiplicative ternary Hom-Nambu algebra with an additional binary anticommutative operation satisfying some compatibility conditions.

Definition 2.1. ([25]). A ternary Hom-algebra (V, [,,],α =( α 1 ,α 2 )) consists of a K-module V , a trilinear map [,,]:V × V × V → V , and linear maps α i : V → V , i =1 , 2, called the twisting maps. The al- gebra (V, [,,],α =( α 1 ,α 2 )) is said multiplicative if α 1 = α 2 := α and α([x, y, z]) = [α(x),α(y),α(z)] for all x, y, z ∈ V .
For convenience, we assume throughout this paper that all Hom-algebras are multiplicative.

Definition 2.2. ([1]

). A (multiplicative) ternary Hom-Nambu algebra is a (multiplicative) ternary Hom-algebra (V, [,,],α) satisfying

[α(x),α(y), [u, v, w]] = [[x, y, u],α(v),α(w)] + [α(u), [x, y, v],α(w)] +[α(u),α(v), [x, y, w]], (2.1)
for all u, v, w, x, y ∈ V .

The condition (2.1) is called the ternary Hom-Nambu identity. In general, the ternary Hom-Nambu identity reads:

[α 1 (x),α 2 (y), [u, v, w]] = [[x, y, u],α 1 (v),α 2 (w)] + [α 1 (u), [x, y, v],α 2 (w)] +[α 1 (u),α 2 (v), [x, y, w]],
for all u, v, w, x, y ∈ V , where α 1 and α 2 are linear self-maps of V .

Definition 2.3. A (multiplicative) Hom-triple system is a (multiplicative) ternary Hom-algebra

(V, [,,],α) such that (i) [u, v, w]=-[v, u, w], (ii) (u,v,w) [u, v, w]=0, for all u, v, w ∈ V .
Remark. A more general definition of a Hom-triple system is given by D. Yau [START_REF] Yau | On n-ary Hom-Nambu and Hom-Nambu-Lie algebras[END_REF] without the requirements (i), (ii) as in Definition 2.3 above. Our definition here is motivated by the concern of giving a Hom-type analogue of the relationships between nonassociative algebras and triple systems (see Remark below after Proposition 2.4).

A Hom-algebra in which the Hom-associativity is not assumed is called a nonassociative Hom-algebra [START_REF] Makhlouf | Paradigm of nonassociative Hom-algebras and Homsuperalgebras[END_REF] or a Hom-nonassociative algebra [START_REF] Yau | Enveloping algebra of Hom-Lie algebras[END_REF] (the expression of "non-Hom-associative" Hom-algebra is used in [START_REF] Issa | Hom-Akivis algebras[END_REF] for that type of Hom-algebras). With the notion of a Hom-triple system as above, we have the following Proposition 2.4. Any non-Hom-associative Hom-algebra is a Hom-triple system.

Proof. Let (A, •,α) be a non-Hom-associative algebra. Then (A, [, ],as(,,),α) is a Hom-Akivis algebra with respect to [x, y]:=x • yy • x (commutator) and as(x, y, z):=xy • α(z)α(x) • yz (Hom-associator), i.e. the Hom-Akivis identity (x,y,z) [[x, y],α(z)] = (x,y,z) as(x, y, z) -(x,y,z) as(y, x, z) holds for all x, y, z in A ( [START_REF] Issa | Hom-Akivis algebras[END_REF]). Now define [x, y, z]:=[[x, y],α(z)]as(x, y, z)+as(y, x, z) for all x, y, z in A. Then [x, y, z]=-[y, x, z] and the Hom-Akivis identity implies that (x,y,z) [x, y, z] = 0. Thus (A, [,,],α) is a Hom-triple system.

Remark. For α = Id (the identity map), we recover the triple system with ternary operation [[x,y],y,z)+(y,x,z) that is associated to each nonassociative algebra, since any nonassociative algebra has a natural Akivis algebra structure with respect to the commutator and associator operations [x, y] and (x, y, z), for all x, y, z (see, e.g., remarks and references in [START_REF] Issa | Hom-Akivis algebras[END_REF]).

Definition 2.5. ([25]

). A Hom-Lie triple system is a Hom-triple system (V, [,,],α) satisfying the ternary Hom-Nambu identity (2.1).

When α = Id, a Hom-Lie triple system reduces to a Lie triple system.

We now give the definition of the basic object of this paper. Definition 2.6. A Hom-Lie-Yamaguti algebra (Hom-LY algebra for short) is a quadruple (L, * , {,,},α) in which L is a K-vector space, " * "a binary operation and "{,,}" a ternary operation on L, and α : L → L a linear map such that (HLY1) α(x * y)=α(x) * α(y), (HLY2) α({x, y, z})={α(x),α(y),α(z)}, (HLY3) x * y = -y * x, (HLY4) {x, y, z} = -{y, x, z}, (HLY5) (x,y,z) [(x * y) * α(z)+{x, y, z}]=0, (HLY6) (x,y,z) {x * y, α(z),α(u)} =0, (HLY7) {α(x),α(y),u * v} = {x, y, u} * α 2 (v)+α 2 (u) * {x, y, v}, (HLY8) {α 2 (x),α 2 (y), {u, v, w}} = {{x, y, u},α 2 (v),α 2 (w)} +{α 2 (u), {x, y, v},α 2 (w)} +{α 2 (u),α 2 (v), {x, y, w}}, for all u, v, w, x, y, z in L.

Note that the conditions (HLY1) and (HLY2) mean the multiplicativity of (L, * , {,,},α). (2) If x * y =0 , for all x, y ∈ L, then (L, * , {,,},α) becomes a Hom-Lie triple system (L, {,,},α 2 ) and, subsequently, a ternary Hom-Nambu algebra (since, by Definition 2.5, any Hom-Lie triple system is automatically a ternary Hom-Nambu algebra).

(3) If {x, y, z} =0for all x, y, z ∈ L, then the Hom-LY algebra (L, * , {,,},α) becomes a Hom-Lie algebra (L, * ,α).

Constructions of Hom-Lie-Yamaguti algebras

In this section we consider construction methods for Hom-LY algebras. These methods allow to find examples of Hom-LY algebras starting from ordinary LY algebras or even from Malcev algebras.

First, as the main tool, we show that the category of (multiplicative) Hom-LY algebras is closed under self-morphisms. Theorem 3.1. Let A α := (A, * , {,,},α) be a Hom-LY algebra and let β be an endomorphism of the algebra (A, * , {,,}) such that βα = αβ.L e tβ 0 = id and, for any n ≥ 1, β n := β • β n-1 . Define on A the operations x * β y := β n (x * y), {x, y, z} β := β 2n ({x, y, z}) for all x, y, z in A. Then A β n := (A, * β , {,,} β ,β n α) is a Hom-LY algebra, with n ≥ 1.

Proof. First, we observe that the condition βα = αβ implies

β n α = αβ n , n ≥ 1. Next we have (β n α)(x * β y)=(β n α)(β n (x) * β n (y)) = β n ((αβ n )(x) * (αβ n )(y)) =(αβ n )(x) * β (αβ n )(y)=(β n α)(x) * β (β n α)(y)
and we get (HLY1) for A β n . Likewise, the condition βα = αβ implies (HLY2). The identities (HLY3) and (HLY4) for A β n follow from the skew-symmetry of " * " and "{,,}" respectively.

Consider now (x,y,z) ((x * β y) * β (β n α)(z)) + (x,y,z) {x, y, z} β . Then

(x,y,z) ((x * β y) * β (β n α)(z)) + (x,y,z) {x, y, z} β = (x,y,z) [β n (β n (x * y) * β n (α(z)))] + (x,y,z) [β 2n ({x, y, z})] = (x,y,z) [β 2n ((x * y) * α(z))] + (x,
A β n . Next, {x * β y, (β n α)(z), (β n α)(u)} β = {β 3n (x * y),β 3n (α(z)),β 3n (α(u))} = β 3n ({x * y, α(z),α(u)}). Therefore (x,y,z) {x * β y, (β n α)(z), (β n α)(u)} β = (x,y,z) [β 3n ({x * y, α(z),α(u)}) = β 3n ( (x,y,z) {x * y, α(z),α(u)} = β 3n (0) (by (HLY6) for A α )
=0 so that we get (HLY6) for A β n . Further, using (HLY7) for A α and condition αβ = βα, we compute

{(β n α)(x), (β n α)(y),u * β v} β = β 3n ({α(x),α(y),u * v}) = β 3n ({x, y, u} * α 2 (v)+α 2 (u) * {x, y, v})=β n (β 2n ({x, y, u}) * (β 2n α 2 )(v)) +β n ((β 2n α 2 )(u) * β 2n ({x, y, v})) = {x, y, u} β * β (β 2n α 2 )(v) +(β 2n α 2 )(u) * β {x, y, v} β = {x, y, u} β * β (β n α) 2 (v)+(β n α) 2 (u) * β {x, y, v} β .
Thus (HLY7) holds for A β n . Using repeatedly the condition αβ = βα and the identity (HLY8) for A α , the verification of (HLY8) for A β n is as follows.

{(β n α) 2 (x), (β n α) 2 (y), {u, v, w} β } β = {(β 2n α 2 )(x), (β 2n α 2 )(y), {u, v, w} β } β = β 2n ({(β 2n α 2 )(x), (β 2n α 2 )(y),β 2n ({u, v, w})}) = β 4n ({α 2 (x),α 2 (y), {u, v, w}}) = β 4n ({α 2 (u)),α 2 (v)), {x, y, w}}) + β 4n ({{x, y, u},α 2 (v),α 2 (w)}) + β 4n ({α 2 (u), {x, y, v},α 2 (w)} = β 2n ({(β 2n α 2 )(u), (β 2n α 2 )(v),β 2n ({x, y, w})}) + β 2n ({β 2n ({x, y, u}), (β 2n α 2 )(v), (β 2n α 2 )(w)}) + β 2n ({(β 2n α 2 )(u),β 2n ({x, y, v}), (β 2n α 2 )(w)}) = {(β n α) 2 (u), (β n α) 2 (v), {x, y, w} β } β + {{x, y, u} β , (β n α) 2 (v), (β n α) 2 (w)} β + {(β n α) 2 (u), {x, y, v} β , (β n α) 2 (w)} β .
Thus (HLY8) holds for A β n . Therefore, we get that A β n is a Hom-LY algebra. This finishes the proof.

From Theorem 3.1 we have the following construction method of Hom-LY algebras from LY algebras (this yields examples of Hom-LY algebras). This method is an extension to binary-ternary algebras of a result due to D. Yau ([23], Theorem 2.3), giving a general construction method of Hom-algebras from their corresponding untwisted algebras. Such an extension to binaryternary algebras is first mentioned in [START_REF] Issa | Hom-Akivis algebras[END_REF], Corollary 4.5. (A,* ,[,,]) be a LY algebra and β an endomorphism of (A, * , [,,]). If define on A a binary operation " * " and a ternary operation "{,,}"b y

Corollary 3.2. Let

x * y := β(x * y), {x, y, z} := β 2 ([x, y, z]), then (A, * , {,,},β) is a Hom-LY algebra.

with a =0,b =0,e =0,f =0,k = 0, and afbe =0=bk + ae. Also recall that a classification of complex 2-dimensional LY algebras is given in [START_REF] Yamaguti | On cohomology groups of general Lie triple systems[END_REF].

The algebras of type (T1) are either the zero algebra or nonzero Lie triple systems (a classification of real 2-dimensional Lie triple systems is given in [START_REF] Kuz'min | Solvable and semisimple Bol algebras[END_REF]; see also [START_REF] Burdujan | The classification of real two-dimensional Lie triple systems[END_REF], a classification of complex 2-dimensional Lie triple systems is found in [START_REF] Yamaguti | On the Lie triple system and its generalization[END_REF]). According to Corollary 3.6 in [START_REF] Yau | On n-ary Hom-Nambu and Hom-Nambu-Lie algebras[END_REF], each of these Lie triple systems with a given endomorphism gives rise to a (real 2-dimensional) Hom-Lie triple system (i.e. a Hom-LY algebra with zero binary operation).

The algebras of type (T3) are real nonzero 2-dimensional Lie algebras (in fact (T3) is the only one, up to isomorphism, real nonzero 2-dimensional Lie algebra). Given any endomorphism of (T3) we get, by Theorem 3.3 of [START_REF] Yau | Hom-algebras and homology[END_REF], its corresponding (real 2-dimensional) Hom-Lie algebra (i.e. a Hom-LY algebra with zero ternary operation).

Since Hom-Lie algebras as well as Hom-Lie triple systems are particular instances of Hom-LY algebras, we shall focus on algebras of types (T2) and (T4) in order to get nontrivial applications of Corollary 3.2.

In the LY algebra of type (T4), consider the basis change ũ = au + bv, ṽ = v. Then some few transformations and the use of conditions a = 0, and afbe =0=bk + ae imply that (T4) is isomorphic to (T4') ũ * ṽ = aũ,[ũ, ṽ, ũ]=0,[ũ, ṽ, ṽ]=kũ.

One observes that the algebra (T4') is isomorphic to the algebra (T2) by an isomorphism θ given by θ(u)=αũ + βṽ, θ(v)=γ ũ + δṽ if and only if a = ±1 and α = 0. Then the isomorphisms are θ(u)=αũ, θ(v)=γ ũ + v (when a =1) and θ(u)=αũ, θ(v)=γ ũv (when a = -1), where α = 0 and γ are real numbers.

Therefore, for a nontrivial application of Corollary 3.2, we shall consider algebras of type (T2) and type (T4') when a = ±1.

In general, if (A, * , [,,]) is a LY algebra, then a linear self-map

φ of A is an endomorphism of (A, * , [,,]) if φ(x * y)=φ(x) * φ(y) φ([x, y, z]) = [φ(x),φ(y),φ(z)], (4.1)
for all x, y, z ∈ A. In order to determine φ, it suffices to apply the conditions (4.1) to the basis elements of A. Using elementary algebra, we are led to solve the resulting n simultaneous equations with respect to the coefficients expressing φ in the given basis (the number n depends on the dimension of A). These equations are not difficult to solve when dimA = 2. Suppose now that dimA = 2 and let {u, v} be a basis of A. Then a linear self-map φ of A is given by a 2 × 2-matrix with respect to {u, v}. Set φ(u)=ǫu + βv, φ(v)=γu + δv.

⋆ Case of type (T2): Then (4.1) induces the following simultaneous equations:

β =0 ǫ(1 -δ)=0, β =0 ǫ(1 -δ 2 )=0.
Resolving these simultaneous equations, we are led to the following endomorphisms φ of (T2):

I. φ(u)=0 φ(v)=γu + δv, II. φ(u)=ǫu φ(v)=γu + v,
where γ, δ, and ǫ = 0 are any real numbers.

For each endomorphism I. and II. above, we apply Corollary 3.2 to find the corresponding Hom-LY algebra.

-For an endomorphism of type I., Corollary 3.2 implies that the LY algebra (T2) is twisted into the zero Hom-LY algebra by such an endomorphism.

-For an endomorphism of type II., Corollary 3.2 induces from (T2) the following Hom-LY algebras:

u * v = ǫu, {u, v, u} =0,{u, v, v} = kǫ 2 u, (4.2)
where ǫ = 0 and k = 0 are real numbers.

Remark: A LY algebra of type (T2) admits a nonzero twisting (i.e. the associated Hom-LY algebra is nonzero) if and only if ǫ =0, in which case the twisting maps are algebra automorphisms (including the identity map) of (T2).

⋆ Case of type (T4') (i.e. (T4)): In this case, (4.1) leads to the same types I. and II. of endomorphisms as above. Therefore: -for an endomorphism of type I., we get the zero Hom-LY algebra from (T4') by Corollary 3.2; -for an endomorphism of type II., the application of Corollary 3.2 to (T4') gives the following Hom-LY algebras: ũ * ṽ = aǫũ, {ũ, ṽ, ũ} =0,{ũ, ṽ, ṽ} = kǫ 2 ũ, (

where ǫ =0,a =0, ±1 and k = 0 are real numbers.

Remark: One observes that a Hom-LY algebra of type (4.2) is isomorphic to the one of type (4.3) by an isomorphism θ(u)=αũ + βṽ, θ(v)=γ ũ + δṽ if and only if a = ±1 and α =0. Then the isomorphisms are θ(u)=αũ, θ(v)=γ ũ +ṽ (when a =1) and θ(u)=αũ, θ(v)=γ ũ -ṽ (when a = -1). Therefore the Hom-LY algebras (4.2) and (4.3) are isomorphic if and only if the LY algebras (T2) and (T4') are isomorphic.

Remark. ( 1 )

 1 If α = Id, then the Hom-LY algebra (L, * , {,,},α) reduces to a LY algebra (L, * , {,,}) (see (LY1)-(LY6)).

  y,z) [β 2n ({x, y, z})] = β 2n ( (x,y,z) [(x * y) * α(z)+{x, y, z}]) = β(0) (by (HLY5) for A α ) =0 and thus we get (HLY5) for

Proof. The proof follows if observe that Corollary 3.2 is Theorem 3.1 when α = Id and n =1.

A Malcev algebra [START_REF] Sagle | Malcev algebras[END_REF] is an anticommutative algebra (A, * ) such that the Malcev identity J(x, y, x * z)=J(x, y, z) * x holds for all x, y, z in A, where J(u, v, w):= (u,v,w) (u * v) * w in (A, * ).

Corollary 3.3. Let (A, * ) be a Malcev algebra and β any endomorphism of (A, * ). Define on A the operations x * y := β(x * y), {x, y, z}

) is a LY algebra [START_REF] Yamaguti | Note on Malcev algebras[END_REF]. Moreover, since β is an endomorphism of (A, * ), we have

] so that β is also an endomorphism of (A, * , [,,]). Then Corollary 3.2 implies that (A, * , {,,},β) is a Hom-LY algebra.

Examples of 2-dimensional Hom-Lie-Yamaguti algebras

In this section, algebras are considered over the ground field of real numbers.

Using the classification of real 2-dimensional LY algebras ([5], Corollary 2.7), we classify all the algebra morphisms of each of the proper (i.e. nontrivial) 2dimensional LY algebras and then we obtain their corresponding 2-dimensional Hom-LY algebras (hence we give some application of Corollary 3.2).

For completeness, we recall that any 2-dimensional real LY algebra is isomorphic to one of the algebras (with basis {u, v}) of the following types:


Michael Albert
email: michael.albert@cs.otago.ac.nz

Mireille Bousquet-Mélou
email: mireille.bousquet@labri.frsubm

Permutations sortable by two stacks in parallel and quarter plane walks

Keywords: permutations, stacks, quarter plane walks, generating functions

At the end of the 1960s, Knuth characterized in terms of forbidden patterns the permutations that can be sorted using a stack. He also showed that they are in bijection with Dyck paths and thus counted by the Catalan numbers. A few years later, Pratt and Tarjan asked about permutations that can be sorted using two stacks in parallel. This question is significantly harder. In particular, a sortable permutation can now be sorted by several distinct sequences of stack operations. Moreover, Pratt proved that in order to be sortable, a permutation must avoid infinitely many patterns. The associated counting question has remained open for 40 years. We solve it by giving a pair of equations that characterizes the generating function of permutations that can be sorted with two parallel stacks.

The first component of this system describes the generating function Q(a, u) of square lattice loops confined to the positive quadrant, counted by the length and the number of North-West and East-South factors. Our analysis of the asymptotic number of sortable permutations relies at the moment on two intriguing conjectures dealing with the series Q(a, u). We prove that these conjectures hold for closed walks confined to the upper half-plane, or not confined at all. They remain open for quarter plane walks. Given the recent activity on walks confined to cones, we believe them to be attractive per se.

Introduction

If we have a device whose only ability is to rearrange certain sequences of objects, it is very natural to ask "What rearrangements can my device produce?" When the device is an abstract one that can operate on sequences of any size, this becomes a combinatorial question. Such questions were apparently first considered by Knuth who dealt with the case where the device was a stack, i.e. a storage mechanism operating in a last in, first out manner (Figure 1).

Using a stack it is clear that the input sequence abc cannot be transformed into the output sequence cab as, in order for c to be the first element output, both a and b must be in the stack together but then they will Fig. 1: Four steps in the sequence of operations that outputs 2341 from 1234 using a single stack. Each arrow shows an operation that is about to be performed. be output as ba and not as ab. For a single stack this is the only restriction. In modern language, if the input is taken to be 12 • • • n, then the achievable permutations are those that avoid the pattern 312. Moreover, as the stack operations that will produce an output sequence from a given input sequence are easily seen to be uniquely determined, it is also routine to count such permutations, which turn out to be enumerated by the Catalan numbers. This is described in Section 2.2.1 of The Art of Computer Programming [START_REF] Knuth | The art of computer programming[END_REF]. Knuth also establishes there similar results for input-restricted deques (double-ended queues).

Knuth's investigations, nicely described in terms of "railway yard switching networks", were extended by Even & Itai [START_REF] Even | Queues, stacks, and graphs[END_REF], Pratt [START_REF] Pratt | Computing permutations with double-ended queues, parallel stacks and parallel queues[END_REF] and Tarjan [START_REF] Tarjan | Sorting using networks of queues and stacks[END_REF] who considered more general networks of stacks and queues, including a small network consisting of two stacks in parallel (Figure 2). This work was foundational for the study of permutation classes which can loosely be described as those collections of permutations that are closed by taking sub-permutations, and normalizing them. In our case, we observe indeed that any sub-permutation of a permutation that can be produced using two parallel stacks can itself be produced by this device. The study of permutation classes has been an active and growing field, often concentrating on enumeration, but also dealing with structural properties of these classes. For some general discussions and background see the books [START_REF] Bóna | Combinatorics of Permutations[END_REF][START_REF] Kitaev | Patterns in Permutations and Words[END_REF][START_REF] Linton | Permutation patterns[END_REF], and [START_REF] Bóna | A survey of stack-sorting disciplines[END_REF] for a survey on stack-sorting. The permutation 312 cannot be produced with a single stack, but can be produced with two parallel stacks as shown here. Note that several distinct sequences of operations produce it.

Despite this activity, most problems related to the rearranging power of Knuth's railway's switching networks have turned out to be very hard. For networks consisting of two stacks, the case of parallel stacks seems a bit more manageable than that of two stacks in series. For instance, the list of minimal permutations that cannot be achieved by two parallel stacks has been known since 1973 [START_REF] Pratt | Computing permutations with double-ended queues, parallel stacks and parallel queues[END_REF], but for two stacks in series it is only known to be infinite [START_REF] Murphy | Restricted permutations, antichains, atomic classes and stack sorting[END_REF]. Similarly, it has just been proved this year that one can decide in polynomial time if a permutation can be sorted by two stacks in series [START_REF] Pierrot | 2-Stack sorting is polynomial[END_REF], while the corre-sponding result was proved in 1992 for two parallel stacks [START_REF] Even | Queues, stacks, and graphs[END_REF][START_REF] Unger | The complexity of colouring circle graphs (extended abstract)[END_REF]. However, the natural questions "How many permutations of length n can be generated by two stacks in series, or by two stacks in parallel?" have remained equally open for forty years.

We answer the latter question in this paper, by giving a system of two functional equations that defines the generating function n s n t n , where s n is the number of permutations of length n that can be produced with two parallel stacks. We also determine the exponential growth of the numbers s n , modulo some conjectures that deal with square lattice walks confined to the quarter plane. These walks naturally encode the admissible sequences of stack operations, in the same way as Dyck paths do in the case of a single stack. Our conjectures deal with the enumeration of quarter plane walks counted by the length and by the number of corners of certain types. Walks confined to a quadrant have attracted a lot of attention in the past decade (see e.g. [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF][START_REF] Bostan | Non-D-finite excursions in the quarter plane[END_REF][START_REF] Bousquet-Mélou | Walks in the quarter plane: Kreweras' algebraic model[END_REF][START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF][START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF][START_REF] Kauers | Proof of Ira Gessel's lattice path conjecture[END_REF]), and we believe that our conjectures are of interest quite independently of the original stack sorting question.

Finally we remark that in this metaphor of "devices rearranging input" there are two common viewpoints. As described above, Knuth and Pratt tended to view the input as arriving in fixed order 12 • • • n and then the question is "How many permutations can be generated?". Tarjan on the other hand tended to think of the objective being to sort the input permutation, so the enumerative question becomes "How many permutations can be sorted?". Of course, passing to inverses, the two viewpoints are equivalent to one another. We will be adopting the first one.

The outline of this extended abstract is as follows. In Section 2, we describe a set of canonical operation sequences such that each permutation that can be produced using two parallel stacks is obtained by exactly one canonical operation sequence. In Section 3, we establish a system of functional equations that characterizes the generating function of canonical sequences, and thus, of permutations that can be produced by two parallel stacks. The first equation in this system defines the generating function of quarter plane walks, weighted by their length and the number of North-West and East-South factors (also called corners). In Section 4, we state two conjectures about this generating function, and provide evidence for them by demonstrating that they hold if we only impose on walks a half-plane restriction, or no restriction at all. In Section 5 we derive from our system of equations the exponential growth of the number of permutations of length n produced by two parallel stacks, assuming the conjectures of Section 4. Proofs and more detailed discussions of a number of issues are omitted, but will be included in the full version of this paper, which should soon be available on the arXiv.

Canonical operation sequences

Throughout this paper we consider the action of two stacks in parallel, and attempt to count permutations of length n that such a machine can generate. The primary issue in this question, as opposed to the case of a single stack considered by Knuth [START_REF] Knuth | The art of computer programming[END_REF], is that there is no one-to-one correspondence between sequences of operations of the machine, and the permutations they produce. That is, several sequences of operations may produce the same permutation: we then say that they are equivalent. The most obvious case is that of the identity permutation of length n: there are at least 2 n ways to produce it using two stacks (alternate input and output operations, allowing the freedom of choice as to which stack to use).

In this section we define a family of operation sequences, called canonical, such that each operation sequence is equivalent to exactly one canonical sequence. Canonical sequences are thus in one-to-one correspondence with permutations that can be produced with two parallel stacks.

In order to proceed further, we present three equivalent descriptions of what an operation sequence is.

Recall what the basic scenario is: input items numbered consecutively from 1 through n are processed by two stacks, each of which is capable of containing an arbitrarily large amount of data, but whose operations are limited to input (I) and output (O); an output operation produces the most recently entered item (i.e. items are processed in a last-in first-out fashion). Items are output as a sequence, and after all the input has been processed and the stacks emptied, the result is a permutation of the original input. Operation sequences are encoded as words over the alphabet {I 1 , I 2 , O 1 , O 2 }, the subscripts determining which stack is referred to. Note that one cannot output from an empty stack, and that both stacks must be empty at the end. This means that a word over {I 1 , I 2 , O 1 , O 2 } is an operation sequence if and only if it contains the same number of I i as O i letters for i = 1, 2, and, in each prefix, the number of I i letters is at least as great as the number of O i letters for i = 1, 2.

Let us call quarter plane walk a square lattice walk which begins at (0, 0), uses steps E = (1, 0), N = (1, 0), W = (-1, 0) and S = (0, -1) and remains in the quadrant {(x, y) : x ≥ 0, y ≥ 0}. This walk is a loop if it ends at (0, 0). There is an obvious one-to-one correspondence between operation sequences and quarter plane loops (replace I 1 by E, I 2 by N , O 1 by W and O 2 by S). Under this correspondence, the (x, y) coordinate reached after processing a prefix of an operation sequence simply records the number of items in each stack at that point. The number of quarter plane loops consisting of 2n steps is well known to be C n C n+1 , where A third perspective on these objects arises from considering them as bi-coloured arch systems (Figure 3). This is the two-dimensional counterpart of the standard bijection between Dyck paths and (onecoloured) arch systems [START_REF] Stanley | Enumerative combinatorics[END_REF]Exercise 6.19o]. For an operation sequence of length 2n, take 2n points arranged along a line, labelled from 1 to 2n. These points represented time, that is, the 2n steps of the operation sequence. For each item k in {1, . . . , n}, build an arch joining i to j where i (resp. j) is the time at which k is put in (resp. out of) a stack. If k is processed by the first stack, the arch will be above the line (and will be thought of as red), and otherwise below the line (and thought of as blue). Observe that the set of arches above the line may not contain any crossings, nor can the one below the line -but there are no further restrictions on such systems. The operation sequence is easily recovered by scanning from left to right the 2n points of the arch system, writing I (resp. O) if an arch opens (resp. closes) at this point, and 1 (resp. 2) if this arch is above (resp. below) the line. Upon closing the supporting line into a cycle, an arch system can also be seen as a rooted planar cubic map with a distinguished Hamiltonian cycle. In this disguise, they were already considered by Tutte [START_REF] Tutte | A census of Hamiltonian polygons[END_REF].

C n = 2n n /(n + 1)
Let us observe that two sequences obtained from one another by commuting pairs of adjacent letters I 1 O 2 or I 2 O 1 are equivalent. An operation sequence outputs eagerly if it contains neither I 1 O 2 nor I 2 O 1 as a factor. In other words, if the next item of the permutation which it is producing is already present in one of the two stacks (necessarily at the top of the stack), then it is output immediately, before any other input (necessarily to the other stack) is carried out. Such sequences correspond to walks in the plane containing no ES or N W factor and to arch systems in which the left endpoint of an arch of one colour is never followed immediately by the right endpoint of an arch of the opposite colour -a configuration that we call a left-right pair (see Figure 3).

Lemma 1 (Pratt [18]) If a permutation can be produced by some operation sequence, then it can be produced by one that outputs eagerly.

A second source of ambiguity in operation sequences is the possibility of reflecting one or several (well chosen) arches in the horizontal line. We say that two arches of different colours cross if they cross once the one below the line is reflected. We sometimes consider the arches as vertices of a graph, two arches being adjacent if they cross (Figure 3, bottom). This graph is then bipartite. We refer to its connected components as the (connected) components of the arch system, and call a non-empty arch system connected if its corresponding graph is. In terms of operation sequences, or equivalently quarter plane loops, this means that no proper factor is an operation sequence.

Definition 2 An arch system is standard if the first arch of each component is red (that is, above the line).

It is canonical if, in addition, it outputs eagerly. Fig. 4: The canonical arch system that is equivalent to the arch system of Figure 3. Note that the left-right pair created by edges 2 and 5 in Figure 3 has disappeared (in fact, these edges do not cross any more). Also, the colours of the two rightmost components (edges 6, 7, 8) have been changed. The output permutation is still 43125867.

The following lemma is illustrated by Figure 4.

Lemma 3 If a permutation can be produced by some operation sequence, then it can be produced by a canonical one.

A detailed but routine analysis yields:

Proposition 4 Every achievable permutation is produced by a unique canonical operation sequence.

Note that the concatenation of two canonical arch systems is a canonical arch system. We say that a non-empty canonical arch system is primitive if it cannot be written as a non-trivial concatenation. The corresponding permutations are also called primitive.

Exact enumeration

In this section, we establish a system of functional equations that characterizes the length generating function S(t) of permutations that can be produced (or sorted) by two stacks in parallel:

S(t) = 1 + t + 2t 2 + 6t 3 + 23t 4 + 103t 5 + 513t 6 + 2760t 7 + 15741t 8 + O(t 9 ).
The first equation in this system characterizes the generating function Q(a, u; x, y) of quarter plane walks, counted by the length (variable u), the number of NW or ES corners (variable a), and the coordinates of their endpoint (variables x and y). By setting x = y = 0, and replacing u by √ u, one obtains the generating function Q(a, u) of quarter plane loops counted by half-length (u) and NW or ES corners (a):

Q(a, u) = 1 + 2u + (8 + 2a)u 2 + (44 + 24a + 2a 2 )u 3 + O(u 4 ).
Equivalently, Q(a, u) counts arch systems by the number of arches (u) and the number of left-right pairs (a). The last series involved in our system of equations is the generating function of connected standard arch systems, counted by the number of arches (v) and the number of left-right pairs (b):

C(b, v) = v + bv 2 + b(b + 2)v 3 + O(v 4 ).
We find it convenient to use three different length variables (t, u and v) and two different corner variables (a and b) when we perform substitutions in our generating functions.

Theorem 5

The generating function Q(a, u; x, y) ≡ Q(x, y) of quarter plane walks is characterized by:

1 -u(x + x + y + ȳ) -u 2 (a -1)(xȳ + y x) Q(x, y) = 1 -uȳ(1 + ux(a -1))Q(x, 0) -ux(1 + uy(a -1))Q(0, y), (1)
where x = 1/x and ȳ = 1/y. The generating function for quarter plane loops is thus

Q(a, u) = Q(a, √ u; 0, 0).
The generating function C(b, v) for connected standard arch systems is characterized by

Q(a, u) = 1 + 2C 1 - 1 -a Q , uQ 2 , ( 2
)
where Q stands for Q(a, u). Finally, the generating function S(t) ≡ S of permutations that can be produced by two stacks operating in parallel is characterized by

S(t) = 1 + C 1 - 1 S , tS 2 .
The equation defining Q(x, y) translates a simple recursive description of quarter plane walks, constructed by adding one or two steps at a time (see [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF] for such arguments in the case of unweighted walks). The argument required to prove the other two results uses the structural decomposition of arch systems suggested by Figure 5.

By relating the functional equation ( 2) to a compositional inversion of bivariate series, we can eliminate the series C(b, v) from the system of Theorem 5, and thus obtain an equation defining S(t) in terms of Q(a, u). This relation looks nicer when we introduce the generating function S • (t) that counts primitive canonical operation sequences, defined at the end of Section 2.

Fig. 5:

The structure of an arch system: a connected system c with n arches (here, n = 3), in which 2n arbitrary arch systems are inserted. Here, c has two left-right pairs. The arch systems that are inserted there (shown in white) destroy these left-right pairs, unless they are empty.

Corollary 6

The series Q(a, u), S(t) ≡ S and S • (t) ≡ S • that count quarter plane loops, sortable permutations and primitive sortable permutations respectively, are related by

S = 1 1 -S • and Q -S • , t (1 + S • ) 2 = 1 + S • 1 -S • .

Corners in square lattice walks

Our analysis of the asymptotic behaviour of the number of sortable permutations of length n, performed in the next section, relies on three conjectures, which have their own combinatorial interest.

Conjecture 7

The series Q(a, u) is (a + 1)-positive: i.e. there exists polynomials

P n (b) ∈ N[b] such that Q(a, u) = n≥0 u n P n (a + 1).
Of course, Q(a, u) is a power series in u with coefficients in N[a], and hence in Z[a + 1]. What is not clear is why the coefficient of (a + 1) k should be non-negative. This has been checked on a computer up to half-length n = 100, using the functional equation [START_REF] Bernardi | Bijective counting of tree-rooted maps and shuffles of parenthesis systems[END_REF]. We conjecture this holds as well if we include a variable s counting East steps.

Conjecture 8 For

a ≥ -1, the radius of convergence of Q(a, •) is ρ Q (a) =          1 (2 + √ 2 + 2a) 2 if a ≥ -1/2, - a 2(1 -a) 2 if a ∈ [-1, -1/2]. (3)
We shall only use the above conjecture for a ≥ -1/2.

Conjecture 9

The series

Q ′ 2 (a, u) := ∂Q ∂u (a, u) is convergent at u = ρ Q (a) for a ≥ -1.
In the following subsections, we gather some evidence for these conjectures. In particular, we prove Conjectures 7 and 8 for general loops and for loops confined to the upper half-plane. (Conjecture 9 does not hold for these more general loops.) The fact that Conjecture 8 holds for general loops and half-plane loops is reminiscent of a recent result according to which the growth constant of (unweighted) loops confined to a wedge is independent of this wedge [8, Sec. 1.5].

Some results on quarter plane loops

Proposition 10 The series Q(a, s, u) counting quarter plane loops by the half-length (u), the number of East steps (s), and the number of NW and ES factors (a) satisfies

Q(1, s, u) = i,j≥0 2i + 2j 2i C i C j s i u i+j ,
where

C i = 2i i /(i + 1
) is the ith Catalan number. The value at a = -1 is just as remarkable:

Q(-1, s, u) = i,j≥0 i + j i C i C j s i u i+j .
The results dealing with Q(1, s, t) are well-known and easy to prove [START_REF] Guy | Lattice paths, reflections, & dimensionchanging bijections[END_REF]. For the case a = -1, we work from the functional equation ( 1), refined with a variable s. The proof is inspired by recent progress on quarter plane walks with general steps [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF]. It still lacks a combinatorial explanation. Let us now discuss the radius of convergence of Q(a, •).

Proposition 11 For a fixed, let ρ Q (a) be the radius of convergence of Q(a, •). Then

ρ Q (-1) = 1 8 , ρ Q (1) = 1 16 ,
and ρ is non-increasing function on [0, +∞), continuous on (0, +∞). Moreover, for a ≥ 0,

ρ Q (a) ≥ 1 (2 + √ 2 + 2a) 2 .
The series Q ′ 2 (a, ρ Q (a)) converges for a = -1 and a = 1. If Q(a, u) is (a + 1)-positive, then ρ Q is non-increasing on [-1, +∞) and continuous on (-1, +∞).

The values at a = 1 and a = -1 follow from Proposition 10. The lower bound is obtained by counting all walks by length and corners. The continuity result is standard for series with coefficients in N[a] and affine degree.

Unconfined loops

We now consider unconfined loops. Their generating function can be obtained by two successive coefficient extractions in the rational generating function that counts all walks and keeps track of their final position. This allows us to prove that Conjectures 7 ((a + 1)-positivity) and 8 (radius of convergence) hold for these loops.

Proposition 12

The generating function W(a, s, t; x, y) counting square lattice walks by the number of horizontal steps (s), the number of vertical steps (t), the number of ES and NW corners (a) and the coordinates of the endpoint (x, y) is rational, and given by

W(a, s, t; x, y) = 1 1 -s (x + x) -t(y + ȳ) -st (a -1) (xȳ + xy) . ( 4
)
The generating function that only counts loops is D-finite, and given by W 0,0 (a, s, t) := [x 0 y 0 ]W(a, s, t; x, y) = j≥0 2j j t 2j W j (a, s)

where

W j (a, s) = [x 0 ] (1 -sx(1 -a)) j (1 -sx(1 -a)) j (1 -s(x + x)) 2j+1 . ( 6
)
The generating function A(a, s, t) := j≥0 t 2j W j (a, s) is biquadratic, and can be written as

A(a, s, t) = 1 + t 2 (1 -a 2 )T (1 -t 2 (a 2 -1)T ) 2 -t 2 (1 + 2(a + 1)T ) 2 1 + 4T -t 2 (a -1) 2 T 1 -t 2 (a -1) 2 T , ( 7
)
where T ≡ T (a, s, t) is the unique series in Q[a][[s, t]] that satisfies T (a, 0, t) = 0 and

T = s 2 1 + 4T -(a -1) 2 t 2 T 1 -t 2 -t 2 (a + 1) 2 T . ( 8
)
The expression of W(a, s, t; x, y) follows from the same recursive construction of walks as the functional equation ( 1) for quarter plane walks. Extracting the coefficient of x 0 y 0 gives ( 5). If we drop the coefficient 2j j , this becomes the constant term (in x) of a rational series, and thus an algebraic series A(a, s, t). We perform the constant term extraction using a partial fraction expansion in x, as described for instance in [START_REF] Stanley | Enumerative combinatorics[END_REF]Thm. 6.3.3]. This gives a biquadratic equation for A, which we parametrize using [START_REF] Denis Denisov | Random walks in cones[END_REF].

Proposition 13

The series W 0,0 (a, s, t) that counts unconfined loops is (a + 1)-positive. Moreover,

W 0,0 (1, s, t) = i,j≥0 s 2i t 2j 2i + 2j 2i 2i i 2j j , while W 0,0 (-1, s, t) = i,j≥0 s 2i t 2j i + j i 2i i 2j j .
We first establish (a + 1)-positivity for T using (8), then for A using [START_REF] Bousquet-Mélou | Walks with small steps in the quarter plane[END_REF]. This is equivalent to saying that W 0,0 (a, s, t) is (a + 1)-positive. The expression of W 0,0 (1, s, t) is combinatorially clear, while the expression of W(-1, s, t) follows by specializing Proposition 12 to a = -1.

Proposition 14 Let a ≥ -1. The series W 0,0 (a, √ u, √ u) that counts unconfined loops walks by halflength and corners has radius of convergence given by (3).

We first compute a differential equation, of order 2, satisfied by this D-finite series. The radius is found among the roots of the coefficient of the second derivative. We select the correct root, depending on the value of a, by combining (a + 1)-positivity, a continuity argument, and the known values 1/16 and 1/8 at a = 1 and a = -1, respectively.

Half-plane walks

We obtain similar results for loops confined to the upper half-plane {(x, y) : y ≥ 0}.

Proposition 15

The generating function of half-plane loops, counted by horizontal steps (s), vertical steps (t), and NW and ES factors (a), is

H 0,0 (a, s, t) = j≥0 1 j + 1 2j j t 2j W j (a, s),
where W j (a, s) is given by [START_REF] Bousquet-Mélou | Walks in the quarter plane: Kreweras' algebraic model[END_REF]. It is (a + 1)-positive. Moreover,

H 0,0 (1, s, t) = i,j≥0 s 2i t 2j 1 j + 1 2i + 2j 2i 2i i 2j j , while H 0,0 (-1, s, t) = i,j≥0 s 2i t 2j 1 j + 1 i + j i 2i i 2j j .
For a ≥ -1, the series H 0,0 (a, √ u, √ u) that counts half-space loops by half-length and corners has radius of convergence given by (3).

These results follow from those obtained for unconfined walks, using the following proposition. The proof is simple, once one realizes that the number of NW and ES corners is distributed as the number of WN and SE corners, as stated in the following result (discovered independently by Olivier Bernardi and Julien Courtiel; personal communications).

Lemma 17

There exists an involution on square lattice paths that exchanges the number of NW and WN factors, fixes the number of ES or SE factors, and leaves the horizontal and vertical projections unchanged.

Consequently, for any pair of walks v ∈ {N, S} and w ∈ {E, W }, the following bi-statistics of corners are equidistributed in the set of walks that project vertically on v and horizontally on w: (NW,ES), (WN,ES), (WN,SE) and (NW,SE).

Asymptotic Analysis

Recall the relationship between the series Q(a, u) and S ≡ S(t) established in Corollary 6:

Q -S • , t (1 + S • ) 2 = 1 + S • 1 -S •
with S = 1/(1 -S • ). Our main theorem tells us that S(t) becomes singular when the pair (-S • , t(1 + S • ) -2 ) reaches the critical curve of Q, namely {(a, ρ Q (a)), -1 ≤ a} where ρ Q (a) is the radius of the series Q(a, •). However, this theorem relies on the conjectures studied in the previous section.

Theorem [START_REF] Pratt | Computing permutations with double-ended queues, parallel stacks and parallel queues[END_REF] Assume that the series Q(a, u) is (a + 1)-positive, and that Q ′ 2 (a, ρ Q (a)) < ∞ for -1/2 ≤ a ≤ 0. Let t c be the radius of convergence of S = 1/(1 -S • ). Then t/(1 + S • (t)) 2 increases on the interval [0, t c ], and on this interval,

t (1 + S • (t)) 2 ≤ ρ Q (-S • (t)),
with equality if and only if t = t c . Moreover, S • (t c ) ≤ 1/3.

We can make the value of t c more explicit thanks to the conjectured expression of ρ Q (a) (Conjecture 8).

Corollary 19

Assume that the assumptions of the above theorem hold, as well as (the first part of) Conjecture 8. Then the radius of convergence of S is

t c = 1 - √ 2 + 2a 2 2 ,
where a = -S • (t c ) satisfies

Q a, 1 (2 + √ 2 + 2a) 2 = 1 -a 1 + a .
Numerically, a ≃ -0.1477 and 1/t c = lim sup s 1/n n ≃ 8.29.

The proof of these results is rather delicate, first because we have to deal with bivariate series, and then because -S • is negative. The latter difficulty is partially alleviated by the (conjectured) (a + 1)-positivity of Q. The main ingredients of the proof are the implicit function theorem, Pringsheim's theorem, and the open mapping theorem in two variables.

  Fig. 2:The permutation 312 cannot be produced with a single stack, but can be produced with two parallel stacks as shown here. Note that several distinct sequences of operations produce it.

Fig. 3 :

 3 Fig. 3:The arch system associated with the operation sequence I1I2I1I1O1O1O1I1O2O1I2I1I2O2O2O1, and the associated graph. The arches are labelled using the left-to-right order of their left endpoint. This arch system has five connected components, and one left-right pair (between arches 2 and 5). The output permutation is 43125867.

Proposition 16

 16 Let v be a word on {N, S}. The generating function of walks whose vertical projection is v, counted by the number of horizontal steps (s), the abscissa of the endpoint (x) and the number of NW and SE factors (a), only depends on |v| N and |v| S .

Acknowledgements. We are indebted to Olivier Bernardi, Julien Courtiel, Kilian Raschel, Alin Bostan, Cyril Banderier, Pierre Lairez for helpful and interesting discussions and thank LaBRI for its hospitality to the first author in visits in 2008 and 2012.