Nohra Hage

Philippe Malbos

KNUTH'S COHERENT PRESENTATIONS OF PLACTIC MONOIDS OF TYPE A

We construct finite coherent presentations of plactic monoids of type A. Such coherent presentations express a system of generators and relations for the monoid extended in a coherent way to give a family of generators of the relations amongst the relations. Such extended presentations are used for representations of monoids, in particular, it is a way to describe actions of monoids on categories. Moreover, a coherent presentation provides the first step in the computation of a categorical cofibrant replacement of a monoid. Our construction is based on a rewriting method introduced by Squier that computes a coherent presentation from a convergent one. We compute a finite coherent presentation of a plactic monoid from its column presentation and we reduce it to a Tietze equivalent one having Knuth's generators.

INTRODUCTION

Plactic monoids. The structure of plactic monoids appeared in the combinatorial study of Young tableaux by Schensted [START_REF] Schensted | Longest increasing and decreasing subsequences[END_REF] and Knuth [START_REF] Knuth | Permutations, matrices, and generalized Young tableaux[END_REF]. The plactic monoid of rank n > 0, denoted by P n , is generated by the set {1, . . . , n} and subject to the Knuth relations: zxy = xzy for 1 x y < z n, yzx = yxz for 1 x < y z n.

For instance, the monoid P 2 is generated by {1, 2} and submitted to the relations 211 = 121 and 221 = 212. The Knuth presentation of the monoid P 3 has 3 generators and 8 relations. Lascoux and Schützenberger used the plactic monoid in order to prove the Littlewood-Richardson rule for the decomposition of tensor products of irreducible modules over the Lie algebra of n by n matrices, [START_REF] Schützenberger | La correspondance de Robinson[END_REF][START_REF] Lascoux | ), volume 109 of Quad[END_REF]. The structure of plactic monoids has several applications in algebraic combinatorics and representation theory [START_REF] Lascoux | Sur une conjecture de H. O. Foulkes[END_REF][START_REF] Lascoux | ), volume 109 of Quad[END_REF][START_REF] Lascoux | Crystal graphs and q-analogues of weight multiplicities for the root system A n[END_REF][START_REF] Fulton | Young tableaux[END_REF] and several works have generalised the notion of tableaux to classical Lie algebras [START_REF] Berele | A Schensted-type correspondence for the symplectic group[END_REF][START_REF] Sundaram | Orthogonal tableaux and an insertion algorithm for SO(2n + 1)[END_REF][START_REF] Kashiwara | Crystal graphs for representations of the q-analogue of classical Lie algebras[END_REF][START_REF] Littelmann | A plactic algebra for semisimple Lie algebras[END_REF][START_REF] Sheats | A symplectic jeu de taquin bijection between the tableaux of King and of De Concini[END_REF].

Syzygies of Knuth's relations. The aim of this work is to give an algorithmic method for the syzygy problem of finding all independent irreducible algebraic relations amongst the Knuth relations. A 2-syzygy for a presentation of a monoid is a relation amongst relations. For instance, using the Knuth relations there are two ways to prove the equality 2211 = 2121 in the monoid P 2 , either by applying the first Knuth relation 211 = 121 or the second relation 221 = 212. This two equalities are related by a syzygy. Starting with a monoid presentation, we would like to compute all syzygies for this presentation and in particular to compute a family of generators for the syzygies. For instance, we will prove that in rank 2 the two Knuth relations form a unique generating syzygy for the Knuth relations. For rank greater than 3, the syzygies problem is difficult due to the combinatorial complexity of the relations. In commutative algebra, the theory of Gröbner bases gives algorithms to compute bases for linear syzygies. By a similar method, the syzygy problem for presentation of monoids can be algorithmically solved using convergent rewriting systems.

Introduction

Rewriting and plactic monoids. Study presentations from a rewriting approach consists in the orientation of the relations, then called reduction rules. For instance, the relations of the monoid P 2 can be oriented with respect to the lexicographic order as follows In a monoid presented by a rewriting system, two words are equal if they are related by a zig-zag sequence of applications of reductions rules. A rewriting system is convergent if the reduction relation induced by the rules is well-founded and if it satisfies the confluence property. This means that any reductions starting on a same word can be extended to end on a same reduced word. Recently plactic monoids were investigated by rewriting methods [START_REF] Kubat | Gröbner-Shirshov bases for plactic algebras[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Hage | Finite convergent presentation of plactic monoid for type C[END_REF][START_REF] Cain | Crystal monoids & crystal bases: rewriting systems and biautomatic structures for plactic monoids of types A n , B n , C n[END_REF].

Coherent presentations of plactic monoids. We give a categorical description of 2-syzygies of presentations of the monoid P n using coherent presentations. Such a presentation extends the notion of a presentation of the monoid by globular homotopy generators taking into account the relations amongst the relations. We compute a coherent presentation of the monoid P n using the homotopical completion procedure introduced in [START_REF] Guiraud | A homotopical completion procedure with applications to coherence of monoids[END_REF][START_REF] Gaussent | Coherent presentations of Artin monoids[END_REF]. Such a procedure extends the Knuth-Bendix completion procedure [START_REF] Knuth | Simple word problems in universal algebras[END_REF], by keeping track of homotopy generators created when adding rules during the completion. Its correctness is based on the Squier theorem, [START_REF] Squier | A finiteness condition for rewriting systems[END_REF], which states that a convergent presentation of a monoid extended by the homotopy generators defined by the confluence diagrams induced by critical branchings forms a coherent convergent presentation. The notion of critical branching describes the overlapping of two rules on a same word. For instance, the Knuth presentation of the monoid P 2 is convergent. It can be extended into a coherent presentation with a unique globular homotopy generator described by the following 3-cell corresponding to the unique critical branching of the presentation between the rules η 1,1,2 and ε 1,2,2 :

2211 2η 1,1,2 & F ε 1,2,2 1 I i 2121 Õ %
The Knuth presentation of the monoid P 3 is not convergent, but it can be completed by adding 3 relations to get a presentation with 27 3-cells corresponding to the 27 critical branchings. For the monoid P 4 we have 4 1-cells and 20 2-cells, for P 5 we have 5 1-cells and 40 2-cells and for P 6 we have 6 1-cells and 70 2-cells. However, in the last three cases, the completion is infinite and another approach is necessary to compute a finite generating family for syzygies of the Knuth presentation.

The column presentation. Kubat and Okniński showed in [START_REF] Kubat | Gröbner-Shirshov bases for plactic algebras[END_REF] that for rank n > 3, a finite convergent presentation of the monoid P n cannot be obtained by completion of the Knuth presentation with the degree lexicographic order. Then Bokut, Chen, Chen and Li in [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF] and Cain, Gray and Malheiro in [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF] constructed with independent methods a finite convergent presentation by adding column generators to the Knuth presentation. However, on the one hand, the proof given in [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF] does not give explicitly the critical branchings of the presentation which does not permit to use the homotopical completion procedure.

On the other hand, the construction in [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF] gave an explicit description of the critical branchings of the presentation, but this does not allow to get explicitly the relations amongst the relations.

The Knuth coherent presentation. We construct a coherent presentation of the monoid P n that extends the Knuth presentation in two steps. The first step consists in giving an explicit description of the critical branchings of the column presentation. The column presentation of the plactic monoid has one generator c u for each column u, that is, a word u = x p . . . x 1 such that x p > . . . > x 1 . Given two columns u and v, using the Schensted algorithm, we compute the Schensted tableau P(uv) associated to the word uv. One proves that the planar representation of the tableau P(uv) contains at most two columns.

If the planar representation is not the tableau obtained as the concatenation of the two columns u and v, one defines a rule α u,v : c u c v ⇒ c w c w where w and w are respectively the left and right columns (with one of them possibly empty). We show that the column presentation can be extended into a coherent column presentation whose any 3-cell has at most an hexagonal form. For instance, the column presentation for the monoid P The second step aimed at to reduce the coherent column presentation using Tietze transformations that coherently eliminates redundant column generators and defining relations to the Knuth coherent presentation giving syzygies of the Knuth presentation. For instance, if we apply this Tietze transformation on the column coherent presentation of the monoid P 2 , we prove that the Knuth coherent presentation of P 2 on the generators c 1 , c 2 and the relations η 1,1,2 , ε 1,2,2 has a unique generating 3-cell 2η 1,1,2 ε 1,2,2 1 described above.

Organisation of the article. The polygraphical description of string rewriting systems that we will use in this work is briefly recalled in Section 2.1, we refer the reader to [START_REF] Guiraud | Polygraphs of finite derivation type[END_REF] for a deeper presentation. In Section 2.2, we define the Knuth 2-polygraph that corresponds to the Knuth relations oriented with respect to the lexicographic order. In Section 2.3, we recall the column presentation introduced in [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF]. The proof given in [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF] for the convergence of this presentation consists in showing that this presentation has the unique normal form property. We give another proof of the confluence by showing the confluence of all the critical branchings of the column presentation. In Section 3, we recall the notion of coherent presentation of a monoid and we show the first main result of this article, that extends the column presentation into a coherent presentation, Theorem 3.2.2. In Section 4, we reduce the coherent column presentation into a coherent presentation that extends the Knuth presentation and that gives all syzygies of the Knuth's relations, Theorem 4.4.7. Finally, we explicit a procedure that computes a family of generating syzygies for any plactic monoids of type A.

PRESENTATION OF PLACTIC MONOIDS BY REWRITING

In this preliminary section, we recall rewriting notions and some presentations and constructions of plactic monoids used in this article.

Presentations of monoids by two-dimensional polygraphs

2.1.1. Two-dimensional polygraphs. In this article, we deal with presentations of monoids by rewriting systems, described by 2-polygraphs with only 0-cell denoted by •. Such a 2-polygraph Σ is given by a pair (Σ 1 , Σ 2 ), where Σ 1 is a set and Σ 2 is a globular extension of the free monoid Σ * 1 , that is a set of 2-cells β : u ⇒ v relating 1-cells in Σ * 1 , where u and v denote the source and the target of β, respectively denoted by s 1 (β) and t 1 (β). If there is no possible confusion, Σ 2 will denote the 2-polygraph itself. Recall that a 2-category (resp. (2, 1)-category) is a category enriched in categories (resp. in groupoids). When two 1-cells, or 2-cells, f and g of a 2-category are 0-composable (resp. 1-composable), we denote by fg (resp. f 1 g) their 0-composite (resp. 1-composite). We will denote by Σ * 2 (resp. Σ 2 ) the 2-category (resp. (2, 1)-category) freely generated by the 2-polygraph Σ, see [7, Section 2.4.] for expended definitions.

The monoid presented by a 2-polygraph Σ, denoted by Σ, is defined as the quotient of the free monoid Σ * 1 by the congruence generated by the set of 2-cells Σ 2 . A presentation of a monoid M is a 2-polygraph whose presented monoid is isomorphic to M. Two 2-polygraphs are Tietze equivalent if they present isomorphic monoids. [6, 2.1.1.], that an elementary Tietze transformation of a 2-polygraph Σ is a 2-functor with domain Σ 2 that belongs to one of the following four transformations:

2.1.2. Tietze transformations of 2-polygraphs. A 2-cell β of a 2-polygraph Σ is collapsible, if t 1 (β) is a 1-cell of Σ 1 and the 1-cell s 1 (β) does not contain t 1 (β), then t 1 (β) is called redundant. Recall from
i) adjunction ι 1 β : Σ 2 → Σ 2 [x](β) of a redundant 1-cell x with its collapsible 2-cell β.
ii) elimination π β : Σ 2 → (Σ 1 \ {x}, Σ 2 \ {β}) of a redundant 1-cell x with its collapsible 2-cell β.

iii) adjunction ι β : Given a 2-polygraph Σ and a 2-cell γ 1 1 γ 1 γ 2 in Σ 2 , the Nielsen transformation κ γ←β is the Tietze transformation that replaces in the (2, 1)-category Σ 2 the 2-cell γ by a 2-cell β : s 1 (γ 1 ) ⇒ t 1 (γ 2 ). When γ 2 is identity, we will denote by κ γ←β the Nielsen transformation which, given a 2-cell γ 1 1 γ in Σ 2 , replaces the 2-cell γ by a 2-cell β : s 1 (γ 1 ) ⇒ t 1 (γ).

Σ 2 → Σ 2 (β) of a redundant 2-cell β. iv) elimination π (γ,β) : Σ 2 → Σ 2 /(γ,
2.1.3. Convergence. A rewriting step of a 2-polygraph Σ is a 2-cell of Σ *
2 with shape wβw , where β is a 2-cell of Σ 2 and w and w are 1-cells of Σ * 1 . A rewriting sequence of Σ is a finite or infinite sequence of rewriting steps. A 1-cell u of Σ * 1 is a normal form if there is no rewriting step with source u. The 2-polygraph Σ terminates if it has no infinite rewriting sequence.

A branching of the 2-polygraph Σ is a non ordered pair (f, g) of 2-cells of Σ * 2 such that s 1 (f) = s 1 (g). A branching (f, g) is local if f and g are rewriting steps. A branching is aspherical if it is of the form (f, f), for a rewriting step f and Peiffer when it is of the form (fv, ug) for rewriting steps f and g with s 1 (f) = u and s 1 (g) = v. The overlapping branchings are the remaining local branchings. An overlapping local branching is critical if it is minimal for the order generated by the relations (f, g) wfw , wgw ),

Plactic monoids

given for any local branching (f, g) and any possible 1-cells w and w of the category Σ * 1 . A branching (f, g) is confluent if there exist 2-cells f and g in Σ * 2 such that s 1 (f ) = t 1 (f), s 1 (g ) = t 1 (g) and t 1 (f ) = t 1 (g ). We say that a 2-polygraph Σ is confluent if all of its branchings are confluent. It is convergent if it terminates and it is confluent. In that case, every 1-cell u of Σ * 1 has a unique normal form. . . u k . We will write tableaux in a planar form, with the rows placed in order of domination from bottom to top and left-justified as in [START_REF] Fulton | Young tableaux[END_REF]. The degree lexicographic order is the total order on col(n), denoted by deglex , and defined by

Plactic monoids

u deglex v if (u) < (v) or (u) = (v)
and u < lex v, for all u and v in col(n), where < lex denotes the lexicographic order on [n] * .

2.2.2. Schensted's algorithm. The Schensted algorithm computes for each 1-cell w in [n] * a tableau denoted by P(w), called the Schensted tableau of w and constructed as follows, [START_REF] Schensted | Longest increasing and decreasing subsequences[END_REF]. Given u a tableau written as a product of rows of maximal length u = u 1 . . . u k and y in [n], it computes the tableau P(uy) as follows. If u k y is a row, the result is u 1 . . . u k y. If u k y is not a row, then suppose u k = x 1 . . . x l with x i in [n] and let j minimal such that x j > y, then the result is P(u 1 . . . u k-1 x j )v k , where v k = x 1 . . . x j-1 yx j+1 . . . x l . The tableau P(w) is computed from the empty tableau and iteratively applying the Schensted algorithm. In this way, P(w) is the row reading of the planar representation of the tableau computed by the Schensted algorithm. The number of columns in P(w) is equal to nds (w), [START_REF] Schensted | Longest increasing and decreasing subsequences[END_REF]. We will denote by C(w) the column reading of the tableau P(w), obtained by reading P(w) column-wise from bottom to top and from left to right. We denote by C r (w) (resp. C l (w)) the reading of the last right (resp. first left) column of the tableau P(w).

{ zxy η x,y,z =⇒ xzy | 1 x y < z n } ∪ { yzx ε x,y,z =⇒ yxz | 1 x < y z n }. (1)
The congruence on the free monoid

Column presentation

We recall some presentations of the plactic monoid P n obtained by adding new generators. In particular, we recall the column presentation of the monoid P n introduced in [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF] which is finite and convergent.

C 2 (n) = c xp . . . c x 1 γ u =⇒ c u u = x p . . . x 1 ∈ col(n) with (u) 2
the set of the defining relations for the column generators. We denote by Knuth c 2 (n) the 2-polygraph whose set of 1-cells is {c 1 , . . . , c n } and whose set of 2-cells is given by

c z c x c y η c x,y,z =⇒ c x c z c y 1 x y < z n ∪ c y c z c x ε c x,y,z =⇒ c y c x c z 1 x < y z n .
By definition, this 2-polygraph is Tietze equivalent to the 2-polygraph Knuth 2 (n). In the sequel, we will identify the 2-polygraphs

Knuth c 2 (n) and Knuth 2 (n). Let us define the 2-polygraph Knuth cc 2 (n), whose set of 2-cells is C 2 (n) ∪ Knuth c 2 (n). The 2-polygraph Knuth cc 2 (n)
is a presentation of the monoid P n . Indeed, we add to the 2-polygraph Knuth c 2 (n) all the column generators c u , for all u = x p . . . x 1 in col(n) such that (u) 2, and the corresponding collapsible 2-cell γ u : c xp . . . c x 1 ⇒ c u .

Pre-column presentation. Let us define the 2-polygraph PreCol

2 (n) whose set of 1-cells is Col 1 (n) and the set of 2-cells is PreCol 2 (n) = PC 2 (n) ∪ c x c u α x,u =⇒ c xu | xu ∈ col(n) and 1 x n ,
where

PC 2 (n) = c x c zy α x,zy =⇒ c zx c y | 1 x y < z n ∪ c y c zx α y,zx =⇒ c yx c z | 1 x < y z n .

Proposition.

For n > 0, the 2-polygraph PreCol 2 (n) is a presentation of the monoid P n , called the pre-column presentation of P n .

Proof. We proceed in two steps. The first step consists to prove that the 2-polygraph

CPC 2 (n) := Col 1 (n) | C 2 (n) ∪ PC 2 (n) is Tietze equivalent to the 2-polygraph Knuth cc 2 (n).
κ η c x,y,z ←α x,zy : Knuth cc 2 (n) -→ Knuth cc 2 (n) /(η c x,y,z ← α x,zy ),
that substitutes the 2-cell α x,zy : c x c zy ⇒ c zx c y to the 2-cell η c x,y,z , for every 1 x y < z n. We denote by T η←α the successive applications of the Tietze transformation κ η c

x,y,z ←α x,zy , for every 1 x y < z n, with respect to the lexicographic order on the triples (x, y, z) induced by the total order on [n].

Similarly, we study in the same way the critical branching (ε c x,y,z , c y γ zx ) of the 2-polygraph Knuth cc 2 (n), for every 1 x < y z n, by introducing the Tietze transformation κ ε c

x,y,z ←α y,zx

from Knuth cc 2 (n) to Knuth cc 2 (n) /(ε c
x,y,z ← α y,zx ). We denote by T ε←α the successive applications of this Tietze transformation with respect to the lexicographic order on the triples (x, y, z) induced by the total order on [n]. In this way, we obtain a Tietze transformation T η,ε←α from Knuth cc 2 (n) to CPC 2 (n) given by the composite T η←α • T ε←α .

In a second step, we prove that the 2-polygraph PreCol 2 (n) is Tietze equivalent to the 2-polygraph CPC 2 (n). Let x p . . . x 1 be a column with (x p . . . x 1 ) > 2 and define α y,x := γ yx : c y c x ⇒ c yx , for every x < y. Consider the following critical branching

c xp c x p-1 ...x 1 c xp c x p-1 . . . c x 1 c xp γ x p-1 ...x 1 @ γxp...x 1 6 V c xp...x 1
of the 2-polygraph CPC 2 (n) and the following Tietze transformation

κ γx p...x 1 ←α xp,x p-1 ...x 1 : CPC 2 (n) -→ CPC 2 (n) /(γ xp...x 1 ← α xp,x p-1 ...x 1 ),
that substitutes the 2-cell α xp,x p-1 ...x 1 to the 2-cell γ xp...x 1 , for each column x p . . . x 1 such that p > 2. Starting from the 2-polygraph CPC 2 (n), we apply successively the Tietze transformation κ γx p...x 1 ←α xp,x p-1 ...x 1 , for every column x p . . . x 1 such that (x p . . . x 1 ) > 2, from the bigger to the smaller one with respect to the total order deglex . The composite

T γ←α = κ γx 3 x 2 x 1 ←α x 3 ,x 2 x 1 • . . . • κ γx n...x 1 ←α xn,x n-1 ...x 1 ,
gives us a Tietze transformation from CPC 2 (n) to PreCol 2 (n) .

Column presentation.

Let n > 0. Given columns u = x p . . . x 1 and v = y q . . . y 1 in col(n), the length nds (uv) of the longest non-decreasing subsequence of uv is lower or equal to 2 [4, Lemma 3.1.]. We will use graphical notations depending on whether the tableau P(uv) consists in two columns:

i) we will denote u v if the planar representation of P(uv) is a tableau, that is, p q and x i y i , for any i q,

ii) we will denote u v × in all the other cases, that is, when p < q or x i > y i , for some i q.

In the case ii), we will denote u v ×1 if the tableau P(uv) has one column and we will denote u v ×2 if the tableau P(uv) has two columns. For every columns u and v in col(n) such that u v × , we define a 2-cell

α u,v : c u c v ⇒ c w c w where i) w = uv and c w = 1, if u v ×1 ,
ii) w and w are respectively the left and right columns of the tableau

P(uv), if u v ×2 . Let us denote by Col 2 (n) the 2-polygraph whose set of 1-cells is Col 1 (n) and the set of 2-cells is Col 2 (n) = c u c v α u,v =⇒ c w c w u, v ∈ col(n) and u v × . (2)
The 2-polygraph Col 2 (n) is a finite convergent presentation of the monoid P n [4, Theorem 3.4], called the column presentation of the monoid P n . Note that Schensted's algorithm that computes a tableau P(w) from a 1-cell w, corresponds to the leftmost reduction path in Col * 2 (n) from w to its normal form P(w), that is, the reduction paths obtained by applying the rules of Col 2 (n) starting from the left. In particular, we have 2.3.5. Lemma. For any u 1 , . . . , u n in col(n), the length of the leftmost rewriting path in Col 2 (n) * from u 1 u 2 . . . u n to its normal form P(u 1 u 2 . . . u n ) is at most n.

COHERENT COLUMN PRESENTATION

In this section, we begin by recalling the notion of coherent presentations of monoids from [START_REF] Gaussent | Coherent presentations of Artin monoids[END_REF]. In a second part, using the homotopical completion procedure, we construct a coherent presentation of the monoid P n starting from its column presentation.

Coherent presentations of monoids

3.1.1. (3, 1)-polygraph. A (3, 1)-polygraph is a pair (Σ 2 , Σ 3 ) made of a 2-polygraph Σ 2 and a globular extension Σ 3 of the (2, 1)-category Σ 2 , that is a set of 3-cells A : f g relating 2-cells f and g in Σ 2
, respectively denoted by s 2 (A) and t 2 (A) and satisfying the globular relations s 1 s 2 (A) = s 1 t 2 (A) and t 1 s 2 (A) = t 1 t 2 (A). Such a 3-cell can be represented with the following globular shape:

• u ! ! v = = f Õ % g Õ % A 7 W • or u f @ g S s v A Õ %
We will denote by Σ 3 the free (3, 1)-category generated by the (3, 1)-polygraph (Σ 2 , Σ 3 ). A pair (f, g) of 2-cells of Σ 2 such that s 1 (f) = s 1 (g) and t 1 (f) = t 1 (g) is called a 2-sphere of Σ 2 .

Coherent presentations of monoids

3.1.2. Coherent presentations of monoids. An extended presentation of a monoid M is a (3, 1)-polygraph whose underlying 2-polygraph is a presentation of the monoid M. A coherent presentation of M is an extended presentation Σ of M such that the cellular extension Σ 3 is a homotopy basis of the (2, 1)-category Σ 2 , that is, for every 2-sphere γ of Σ 2 , there exists a 3-cell in Σ 3 with boundary γ.

3.1.3. Tietze transformations of (3, 1)-polygraphs. We recall the notion of Tietze transformation from [6, Section 2

.1]. Let Σ be a (3, 1)-polygraph. A 3-cell A of Σ is called collapsible if t 2 (A) is in Σ 2 and s 2 (A) is a 2-cell of the free (2, 1)-category over (Σ 2 \ {t 2 (A)}) , then t 2 (A) is called redundant.
An elementary Tietze transformation of a (3, 1)-polygraph Σ is a 3-functor with domain Σ 3 that belongs to one of the following operations: i) adjunction ι 1 α and elimination π α of a 2-cell α as described in 2.1.2.

ii) coherent adjunction ι 2 A :

Σ 3 → Σ 3 (α)(A) of a redundant 2-cell α with its collapsible 3-cell A. iii) coherent elimination π A : Σ 3 → Σ 3 /A of a redundant 2-cell α with its collapsible 3-cell A. iv) coherent adjunction ι A : Σ 3 → Σ 3 (A) of a redundant 3-cell A. v) coherent elimination π (B,A) : Σ 3 → Σ 3 /(B, A) of a redundant 3-cell A, that maps A to B.
For (3, 1)-polygraphs Σ and Υ, a Tietze transformation from Σ to Υ is a 3-functor F : Σ 3 → Υ 3 that decomposes into a sequence of elementary Tietze transformations. Two (3, 1)-polygraphs Σ and Υ are Tietze-equivalent if there exists an equivalence of 2-categories F : Σ 2 /Σ 3 → Υ 2 /Υ 3 and the presented monoids Σ 2 and Υ 2 are isomorphic. Two (3, 1)-polygraphs are Tietze equivalent if, and only if, there exists a Tietze transformation between them, [6, Theorem 2.1.3.].

3.1.4. Homotopical completion procedure. Following [6, Section 2.2], we recall the homotopical completion procedure that produces a coherent convergent presentation from a terminating presentation. Given a terminating 2-polygraph Σ, equipped with a total termination order , the homotopical completion of Σ is the (3, 1)-polygraph obtained from Σ by successive applications of the Knuth-Bendix completion procedure, [START_REF] Knuth | Simple word problems in universal algebras[END_REF], and the Squier construction, [START_REF] Squier | A finiteness condition for rewriting systems[END_REF]. Explicitly, for any critical branching

(f, g) of Σ, if (f, g) is confluent one adds a dotted 3-cell A: v f # C A Õ % u f 7 W g 6 V u w g Q q
where u is a normal form, and if the critical branching (f, g) is not confluent one add a 2-cell β and a 3-cell A:

v f 7 W A Õ % v i β Õ % u f 7 W g 6 V w g 7 W w
where the 2-cell β is directed from a normal form v of v to a normal form w of w if w ≺ v and from w to v otherwise. The adjunction of 2-cells can create new critical branchings, possibly generating the adjunction of additional 2-cells and 3-cells in the same way. This defines an increasing sequence of (3, 1)-polygraphs, whose union is called a homotopical completion of Σ. Following [24, Theorem 5.2], such a homotopical completion of Σ is a coherent convergent presentation of the monoid Σ.

Column coherent presentation

Using the homotopical completion procedure, we extend the 2-polygraph Col 2 (n) into a coherent presentation of the monoid P n .

for any u, v, t in col(n) such that u v t × × , where e and e (resp. w and w ) denote the two columns of the tableau P(uv) (resp. P(vt)). We prove in this section that all of these critical branchings are confluent and that all the confluence diagrams of these branchings are of the following form:

where a and a (resp. b and b ) denote the two columns of the tableau P(uw) (resp. P(e t)) and a, d, b are the three columns of the tableau P(uvt), which is a normal form for the 2-polygraph Col 2 (n). Note that in some cases described below, one or further columns e , w , a and b can be empty. In those cases some indicated 2-cells α in the confluence diagram correspond to identities. Let us denote by Col 3 (n) the extended presentation of the monoid P n obtained from Col 2 (n) by adjunction of one 3-cell X u,v,t of the form (4), for every columns u, v and t such that u v t × × .

Theorem.

For n > 0, the (3, 1)-polygraph Col 3 (n) is a coherent presentation of the monoid P n .

The extended presentation Col 3 (n) is called the column coherent presentation of the monoid P n . The rest of this section consists in a constructive proof of Theorem 3.2.2, that makes explicit all possible forms of 3-cells. Another arguments are given in Remark 3.2.7. Our proof is based on the following arguments. The presentation Col 2 (n) is convergent, thus using the homotopical completion procedure described in 3.1.4, it suffices to prove that the 3-cells X u,v,t with u v t × × form a family of generating confluences for the presentation Col 2 (n). There are four possibilities for the critical branching (3) depending on the following four cases:

u v t ×1 ×1 , u v t ×2 ×1 , u v t ×1 ×2 , u v t ×2 ×2 .
Each of these cases is examined in the following four lemmas, where u = x p . . . x 1 , v = y q . . . y 1 and t = z l . . . z 1 denote columns of length p, q and l respectively.

Lemma. If u v t

×1 ×1 , we have the following confluent critical branching:

c uv c t α uv,t 2 R A u,v,t Õ % c u c v c t α u,v c t B b c u α v,t 2 R c uvt c u c vt α u,vt B b
Proof. By hypothesis uv and vt are columns, then uvt is a column.

c u c v c t α u,v c t C c c u α v,t 4 T c s c s c u c vt α u,vt @ ` (5)
where e and e (resp. s and s ) denote the two columns of the tableau P(uv) (resp. P(uvt)).

Proof. By hypothesis, vt is a column and y 1 > z l . The tableau P(uv) consists of two columns, that we will denote e and e , then nds (uv) = 2 and x 1 y q . We have u v ×2 , so that we distinguish the following possible three cases.

Case 1: p q and x i 0 > y i 0 for some 1 i 0 q. Suppose that i 0 = 1, that is, x 1 > y 1 . We consider y j the biggest element of the column v such that x 1 > y j , then the smallest element of the column e is y j+1 . By hypothesis, the word vt is a column, in particular y j+1 > z l . It follows that e t is a column. Suppose that i 0 > 1, then x 1 y 1 and the smallest element of e is y 1 . Since y 1 > z l by hypothesis, the word e t is a column. Hence, in all cases, e t is a column and there is a 2-cell α e ,t : c e c t ⇒ c e t .

Case 2: p < q and x i y i for any 1 i p. We have e = y q . . . y p+1 x p . . . x 1 and e = y p . . . y 1 . By hypothesis, y 1 > z l , hence e t is a column and there is a 2-cell α e ,t : c e c t ⇒ c e t .

Case 3: p < q and x i 0 > y i 0 for some 1 i 0 p. With the same arguments of Case 1, the smallest element of e is y 1 or y j+1 , where y j is the biggest element of the column v such that y j < x 1 . Hence, e t is a column and there is a 2-cell α e ,t : c e c t ⇒ c e t .

In each case, we have nds (uv) = 2, hence nds (uvt) = 2. Thus the tableau P(uvt) consists of two columns, that we denote s and s and there is a 2-cell α u,vt : c u c vt ⇒ c s c s . Moreover, to compute the tableau P(uvt), one begins by computing P(uv) and after by introducing the elements of the column t on the tableau P(uv). As C(uv) = ee , we have P(uvt) = P(P(uv)t) = P(ee t). Hence C(ee t) = ss and there is a 2-cell α e,e t which yields the confluence diagram (5).

Lemma. If u v t

×1 ×2 , we have the following confluent critical branching:

c uv c t C u,v,t Õ % α uv,t 5 U c u c v c t α u,v c t 9 Y c u α v,t 2 R
where w and w (resp. a and a ) denote the two columns of the tableau P(vt) (resp. P(uw)).

Proof. By hypothesis, uv is a column hence x 1 > y q . Moreover, the tableau P(vt) consists of two columns w and w , then nds (vt) = 2, hence y 1 z l . We have v t ×2 , so that we distinguish the three possible following cases.

Case 1: q l and y i 0 > z i 0 for some 1 i 0 l. Let us denote w = w r . . . w 1 and w = w r . . . w 1 .

Since q l, we have w r = y q . By hypothesis, x 1 > y q . Then the word uw is a column. As a consequence, there is a 2-cell α u,w : c u c w ⇒ c uw . In addition, the column w appears to the left of w in the planar representation of the tableau P(vt), that is, (w) (w ) and w i w i for any i (w ). Then (uw) (w ). We set uw = ξ (uw) . . . ξ 1 and we have ξ i w i for any i (w ). Then uww and c uw c w is a normal form.

On the other hand, the tableau P(vt) consists of two columns, hence nds (vt) = 2. As a consequence, nds (uvt) = 2 and the tableau P(uvt) consists of two columns. Since q l, we have C(uvt) = uww , hence the two columns of P(uvt) are uw and w . Then there is a 2-cell α uv,t : c uv c t ⇒ c uw c w which yields the confluence of the critical branching on c u c v c t , as follows

c uv c t α uv,t 3 S C u,v,t Õ % c u c v c t α u,v c t A a c u α v,t 3 S c uw c w c u c w c w α u,w c w A a (7)
Case 2: q < l and y i z i for any i q. We have w = z l . . . z q+1 y q . . . y 1 and w = z q . . . z 1 . There are two cases along uw is a column or not.

Case 2. A. If x 1 > z l , then uw is a column. Hence, there is a 2-cell α u,w : c u c w ⇒ c uw . Moreover, using Schensted's algorithm we prove that C l (uvt) = uw and C r (uvt) = w . Thus there is a 2-cell α uv,t : c uv c t ⇒ c uw c w which yields the confluence diagram [START_REF] Guiraud | Polygraphs of finite derivation type[END_REF].

Case 2. B. If x 1 z l , then nds (uw) = 2 and P(uw) consists of two columns, that we denote by a and a . Then there is a 2-cell α u,w : c u c w ⇒ c a c a . In addition, by Schensted's algorithm, we deduce that a = z i k . . . z i 1 , with q + 1 i 1 < . . . < i k l. We have a w = z i k . . . z i 1 z q . . . z 1 . Since all the elements of a are elements of t and bigger than z q , we have z i 1 > z q . It follows that a w is a column and there is a 2-cell α a ,w : c a c w ⇒ c a w .

In the other hand, we have two cases whether uv t × or uv t. Suppose uv t × . By Schensted's algorithm, we have C l (uvt) = a and C r (uvt) = a w . Hence there is a 2-cell α uv,t : c uv c t ⇒ c a c a w , which yields the confluence of Diagram [START_REF] Gaussent | Coherent presentations of Artin monoids[END_REF]. Suppose uv t. Then we obtain C(uw) = uvz l . . . z q+1 , and C(z l . . . z q+1 w ) = t. Hence there is a 2-cell α z l ...z q+1 ,w yielding the confluence diagram

c uv c t C u,v,t Õ % c u c v c t α u,v c t 8 X
c u α v,t 5 U c u c w c w α u,w c w 7 W c uv c z l ...z q+1 c w c uv α z l ...z q+1 ,w r Case 3: q < l and y i 0 > z i 0 for some 1 i 0 q. We compute the columns w and w of the tableau P(vt). If the biggest element of the column w is y q , then we obtain the same confluent branching as in Case 1. If the first element of w is z l , then one obtains the same confluent critical branchings as in Case 2.

where e, e (resp. w, w ) denote the two columns of the tableau P(uv) (resp. P(vt)) and a, a (resp. b, b ) denote the two columns of the tableau P(uw) (resp. P(e t)).

Proof. By hypothesis, nds (uv) = 2 and nds (vt) = 2, hence x 1 y q and y 1 z l . In addition, since u v ×2 , the tableau P(uw) consists of two columns, that we denote by a and a . Thus there is a 2-cell α u,w : c u c w ⇒ c a c a . Moreover, as u v ×2 and v t ×2 , we have ((p < q) or (x i 0 > y i 0 for some i 0 q)) and ((q < l) or (y j 0 > z j 0 for some j 0 l)), thus we consider the following cases.

Case 1: p < q < l and y i z i , for all i q, and x i y i , for all i p. We have w = z l . . . z q+1 y q . . . y 1 , w = z q . . . z 1 , e = y q . . . y p+1 x p . . . x 1 and e = y p . . . y 1 .

Since z l y 1 , the tableau P(e t) consists of two columns, that we denote by b and b . Thus there is a 2-cell α e ,t : c e c t ⇒ c b c b . In addition, we have b = z l . . . z p+1 y p . . . y 1 , b = z p . . . z 1 , a = z l . . . z q+1 y q . . . y p+1 x p . . . x 1 and a = y p . . . y 1 .

Since z q y 1 , the tableau P(a w ) consists of two columns, that we denote by d and d . Thus there is a 2-cell α a ,w : c a c w ⇒ c d c d . Since z l x 1 , the tableau P(eb) consists of two columns, that we denote by s and s . Then there is a 2-cell α e,b : c e c b ⇒ c s c s . In the other hand, we have d = z q . . . z p+1 y p . . . y 1 , d = z p . . . z 1 , s = z l . . . z q+1 y q . . . y p+1 x p . . . x 1 and s = z q . . . z p+1 y p . . . y 1 .

Hence a = s, d = s and d = b which yields the confluence diagram (8).

Case 2: q < l and y i z i for all i q p q and x i 0 > y i 0 for some i 0 q or q < l and y i z i for all i q p < q and x i 0 > y i 0 for some i 0 p

We have w = z l . . . z q+1 y q . . . y 1 and w = z q . . . z 1 . Using Schensted's algorithm the smallest element of the column a is an element of v. Since z q is greater or equal than each element of v, the tableau P(a w ) consists of two columns, that we denote by d and d .

On the other hand, all the elements of e are elements of v. Since z l is bigger than each element of v, the tableau P(e t) consists of two columns, that we denote by b and b . Thus there is a 2-cell α e ,t : c e c t ⇒ c b c b . Hence, we consider two cases depending on whether or not c e c b c b is a tableau. Suppose c e c b c b is a tableau. The column e does not contain elements from the column t, then during inserting the column w into the column u, we can only insert some elements of y q . . .

Suppose c e c b c b is not a tableau. The first element of the column b is z l . The smallest element of the column e is either x 1 or y j , where y j is the biggest element of the column v such that y j < x 1 . By hypothesis the tableau P(uw) consists of two columns, then x 1 z l . In addition, z l is greater than each element of v then y j z l . Hence, in all cases, the tableau P(eb) consists of two columns. On the other hand, using Schensted's algorithm, we have a = z i k . . . z i 1 y j k . . . y j 1 with q + 1 i 1 < . . . < i k l, 1 j 1 < . . . < j k q and we have e = y j k . . . y j 1 . In addition, we have b = d = z i k . . . z i 1 with 1 i 1 < . . . < i k q and C(eb) = ad. Hence there is a 2-cell α e,b : c e c b ⇒ c a c d which yields the confluence diagram [START_REF] Guiraud | A homotopical completion procedure with applications to coherence of monoids[END_REF].

Case 3:

q l and y i 0 > z i 0 for some i 0 l p < q and x i y i for all i p or q < l and y i 0 > z i 0 for some i 0 q p < q and x i y i for all i p We have e = y q . . . y p+1 x p . . . x 1 and e = y p . . . y 1 . Since y 1 z l , the tableau P(e t) consists of two columns, that we denote by b and b . The first element of the column b is either z l or y p which are bigger or equal to x 1 , then the tableau P(eb) consists of two columns, that we denote by s and s . Suppose l p. By Schensted's insertion algorithm, we have C(e t) = bw and w = y q . . . y p+1 b. On the other hand, since x p < y p+1 , we have P(uw) = P(u(y q . . .

For l > p, we consider two cases depending on whether or not the first element of the column b is y p . If this element is y p , then when computing the tableau P(vt) no element of the column t is inserted in y q . . . y p+1 . Hence we have w = y q . . . y p+1 b and b = w . On the other hand, by Schensted's insertion procedure we have P(uw) = P(eb). Hence, there is a 2-cell α e,b : c e c b ⇒ c a c a which yields the confluence diagram [START_REF] Kashiwara | Crystal graphs for representations of the q-analogue of classical Lie algebras[END_REF]. Suppose that the first element of the column b is z l . Then when computing the tableau P(vt) some elements of the column t are inserted in y q . . . y p+1 . In this case, we have that the column w contains more elements than b and that c s c s c b is a tableau. Moreover, by Schensted's insertion procedure, we have a = s. Since c s c s c b is the unique tableau obtained from c u c v c t and a = s, we obtain that C(a w ) = s b . As a consequence, there is a 2-cell α a ,w : c a c w ⇒ c s c b which yields the confluence diagram [START_REF] Guiraud | A homotopical completion procedure with applications to coherence of monoids[END_REF].

Case 4: q l and y i 0 > z i 0 for some i 0 l p q and x j 0 > y j 0 for some j 0 q or q l and y i 0 > z i 0 for some i 0 q p < q and x j 0 > y j 0 for some j 0 p or q < l and y i 0 > z i 0 for some i 0 q, p q and x j 0 > y j 0 for some j 0 q. or q < l and y i 0 > z i 0 for some i 0 q p < q and x j 0 > y j 0 for some j 0 p By Lemma 3.2.4, the last term of e is y 1 or y j+1 , where y j is the biggest element of v such that y j < x 1 . Suppose that the last term of e is y 1 . Since z l y 1 , the tableau P(e t) consists of two columns. Furthermore, if the last term of e is y j+1 , then we consider two cases: z l y j+1 or z l < y j+1 . Suppose z l < y j+1 , then the tableau P(e t) consists of one column e t. We consider two cases depending on whether or not c e c e t is a tableau. With the same arguments of Case 2, we obtain a confluence diagram of the following forms:

u,v,t or D

u,v,t .

3.2.7. Remark, [START_REF] Lecouvey | [END_REF]. Thanks to a private communication by Lecouvey, Lemma 2.3.5 and an involution on tableaux can be used to prove the confluence of the critical branching (3) as follows. Let u be a column in col(n) of length p. Schützenberger introduced the involution of u, denoted by u * , as the column of length n -p obtained by taking the complement of the elements of u. More generally, let u 1 . . . u r be the column reading of a tableau, then (u 1 . . . u r ) * = u * r . . . u * 1 and u * r . . . u * 1 is also the column reading of a tableau. Moreover, if w is the column reading of a Young tableau, then we have P(w * ) = P(w) * . In particular, for three columns c u , c v and c t in Col 1 (n), we have P(c * t c * v c * u ) = P(c u c v c t ) * , see [START_REF] Lenart | On the combinatorics of crystal graphs. I. Lusztig's involution[END_REF]. By Lemma 2.3.5, c a c d c b is a normal form of c u c v c t , that is, P(c u c v c t ) = c a c d c b . Then to prove the confluence of the 3-cell (3), it is sufficient to show that P(c u c v c t ) = c a C(c a c w ). We have

c u c v c t c u α v,t =⇒ c u C(c v c t ) = c u c w c w α u,w c w =⇒ C(c u c w )c w = c a c a c w c a α a ,w =⇒ c a C(c a c w ).
By applying the involution on tableaux, we obtain

c * t c * v c * u =⇒ C(c * t c * v )c * u = c * w c * w c * u =⇒ c * w C(c * w c * u ) = c * w c * a c * a =⇒ C(c * w c * a )c * a . By Lemma 2.3.5, we have P(c * t c * v c * u ) = C(c * w c * a )c * a . Since P(c * t c * v c * u ) = P(c u c v c t ) * , we deduce that P(c u c v c t ) * = C(c * w c * a )c * a .
Finally, by applying the involution on tableaux, we obtain P(c u c v c t ) = c a C(c a c w ). Note that this construction does not give the explicit forms of the 2-sources and the 2-targets of the confluence diagrams of the critical branchings as doing in lemmas above.

REDUCTION OF THE COHERENT PRESENTATION

In this section, we begin by recalling the homotopical reduction procedure from [START_REF] Gaussent | Coherent presentations of Artin monoids[END_REF]Section 2.3.]. We explicit all the reduction steps that we need to reduce the coherent presentation Col 3 (n) into a smaller finite coherent presentation of the monoid P n that extends the Knuth presentation. A 3-sphere of the (3, 1)-category Σ 3 is a pair (f, g) of 3-cells of Σ 3 such that s 2 (f) = s 2 (g) and t 2 (f) = t 2 (g). A collapsible part of Σ is a triple (Γ 2 , Γ 3 , Γ 4 ) made of a family Γ 2 of 2-cells of Σ, a family Γ 3 of 3-cells of Σ and a family Γ 4 of 3-spheres of Σ 3 , such that the following conditions are satisfied:

i) every γ of every Γ k is collapsible, that is, t k-1 (γ) is in Σ k-1 and s k-1 (γ) does not contain t k-1 (γ), ii) no cell of Γ 2 (resp. Γ 3 ) is the target of a collapsible 3-cell of Γ 3 (resp. 3-sphere of Γ 4 ),
iii) there exists a well-founded order on the cells of Σ such that, for every γ in every Γ k , t k-1 (γ) is strictly greater than every generating (k -1)-cell that occurs in the source of γ.

The homotopical reduction of the (3, 1)-polygraph Σ with respect to a collapsible part Γ is the Tietze transformation, denoted by R Γ , from the (3, 1)-category Σ 3 to the (3, 1)-category freely generated by the (3, 1)-polygraph obtained from Σ by removing the cells of Γ and all the corresponding redundant cells. We refer the reader to [6, 2.3.1] for details on the definition of the Tietze transformation R Γ defined by well-founded induction as follows. For any γ in Γ , we have

R Γ (t(γ)) = R Γ (s(γ)) and R Γ (γ) = 1 R Γ (s(γ)) .
In any other cases, the transformation R Γ acts as an identity.

Generating triple confluences.

A local triple branching of a 2-polygraph Σ is a triple (f, g, h) of rewriting steps of Σ with a common source. An aspherical triple branchings have two of their 2-cells equal. A Peiffer triple branchings have at least one of their 2-cells that form a Peiffer branching with the other two. The overlap triple branchings are the remaining local triple branchings. Local triple branchings are ordered by inclusion of their sources and a minimal overlap triple branching is called critical. If Σ is a coherent and convergent (3, 1)-polygraph, a triple generating confluence of Σ is a 3-sphere

v f 1 3 S 1 Q x h 9 Õ % v f 1 3 S f 2 ' G Õ % x h 9 m Ñ u f @ `g 7 W h 4 T w g 1 G g g 2 ' G m Ñ u ω f,g,h 1 c u f @ h 4 T w g 7 W 1 Q u x h 2 A a v f X x x h 1 G g h 2 A a v f X x
where (f, g, h) is a triple critical branching of the 2-polygraph Σ 2 and the other cells are obtained by confluence, see [6, 2.3.2] for details.

A reduced column presentation

We apply the homotopical reduction procedure in order to reduce the (3, 1)-polygraph Col 3 (n) using the generating triple confluences.

Generating triple confluences of Col 2 (n).

Consider the homotopical reduction procedure on the (3, 1)-polygraph Col 3 (n) defined using the collapsible part made of generating triple confluences. By Theorem 3.2.2, the family of 3-cells X u,v,t given in (4) and indexed by columns u, v and t in col(n) such that u v t

× ×
forms a homotopy basis of the (2, 1)-category Col 2 (n) . Let us consider such a triple (u, v, t) with (u) 2. Let x p be in [n] such that u = x p u 1 with u 1 in col(n). There is a critical triple branching with source c xp c u 1 c v c t . Let us show that the confluence diagram induced by this triple branching is represented by the 3-sphere Ω xp,u 1 ,v,t whose source is the following 3-cell In the generating triple confluence, some columns may be empty and thus the indicated 2-cells α may be identities. To facilitate the reading of the diagram, we have omitted the context of the 2-cells α.

c u c v c t α u,v 7 W X xp,u 1 ,v c t Õ %
The 3-sphere Ω xp,u 1 ,v,t is constructed as follows. We have x p u 1

×1

and u 1 w × , thus X xp,u 1 ,w is either of the form A xp,u 1 ,w or C xp,u 1 ,w . Let us denote by a 1 and a 1 the two columns of the tableau P(u 1 w). The 3-cell X xp,u 1 ,w being confluent, we have C(x p a 1 ) = az with z in [n] and C(za 1 ) = a . In addition, from z a 1

×1

and a 1 w × , we deduce that X z,a 1 ,w is either of the form A z,a 1 ,w or C z,a and u = x p u 1 . On the 3-cells of Col 3 (n), we define a well-founded order by

i) A u,v,t C u,v,t B u,v,t D u,v,t , ii) if X u,v,t ∈ {A u,v,t , B u,v,t , C u,v,t , D u,v,t } and u deglex u, then X u ,v ,t X u,v,t ,
for any u, v, t in col(n) such that u v t × × . By construction of the 3-sphere Ω xp,u 1 ,v,t , its source contains the 3-cell X u 1 ,v,t and its target contains the 3-cell X u,v,t with (u 1 ) < (u). Up to a Nielsen transformation, the homotopical reduction R Γ 4 applied on the (3, 1)-polygraph Col 3 (n) with respect to Γ 4 and the order give us the (3, 1)-polygraph Col 3 (n). In this way, the presentation Col 3 (n) is a coherent presentation of the monoid P n .

Pre-column coherent presentation

We reduce the coherent presentation Col 3 (n) into a coherent presentation whose underlying 2-polygraph is PreCol 2 (n). This reduction is obtained using the homotopical reduction R Γ 3 on the (3, 1)-polygraph Col 3 (n) whose collapsible part Γ 3 is defined by

Γ 3 = { A x,v,t | x ∈ [n], v, t ∈ col(n) such that x v t ×1 ×1 } ∪ { B x,v,t | x ∈ [n], v, t ∈ col(n) such that x v t ×2 ×1 } ∪ { C x,v,t | x ∈ [n], v, t ∈ col(n) such that x v t ×1 ×2 },

Pre-column coherent presentation

and the well-founded order defined as follows. Given u and v in col(n) such that u v × . We define a well-founded order on the 2-cells of Col 2 (n) as follows

α u ,v α u,v if      (uv) > (u v ) or (uv) = (u v ) and (u) > (C r (u v )) or (u) (C r (u v ))
{ α u,v | (u) 1, (v) 2 and u v ×2 } ∪ { α u,v | (u) = 1, (v) 1 and u v ×1 }. (11)
For any x in [n] and columns v, t such that x v t ×1 ×2 , consider the 3-cell C x,v,t defined in Lemma 3.2.5.

The 2-cells α x,v , α v,t , α x,w and α a ,w are smaller than α xv,t for the order . The reduction R Γ 3 removes the 2-cell α xv,t together with the 3-cell C x,v,t . By iterating this reduction on the length of v, we reduce the set of 2-cells given in [START_REF] Knuth | Simple word problems in universal algebras[END_REF] to the following set:

{ α u,v | (u) = 1, (v) 2 and u v ×2 } ∪ { α u,v | (u) = 1, (v) 1 and u v ×1 }. (12)
For any x in [n] and columns v, t such that x v t ×2 ×1 , consider the following 3-cell: e, e , s and s are defined in Lemma 3.2.4. Note that α e,e t is the 2-cell in (12) obtained from the 2-cell α e,e t by the previous step of the homotopical reduction by the 3-cell C x,v,t . Having x in [n], by definition of α we have e in [n]. The 2-cells α x,v , α e ,t , α v,t and α e,e t being smaller than α x,vt for the order , we can remove the 2-cells α x,vt together with the 3-cell B x,v,t . By iterating this reduction on the length of the column t, we reduce the set [START_REF] Knuth | Permutations, matrices, and generalized Young tableaux[END_REF] to the following set

{ α u,v | (u) = 1, (v) = 2 and u v ×2 } ∪ { α u,v | (u) = 1, (v) 1 and u v ×1 }. (13)
4.3.2. Lemma. The set of 2-cells defined in ( 13) is equal to PreCol 2 (n). and C x,v,t , which are not of the form C x,v,t . We have then proved the following result.

Proof. By definition of PreCol

2 (n), it is sufficient to prove that PC 2 (n) = { α u,v : c u c v ⇒ c w c w | (u) = 1, (v) = 2 and u v ×2 }. Consider the 2-cells α u,v in Col 2 (n) such that (u) = 1, (v) = 2 and u v ×2 . Suppose that v = xx with x > x in [n]. Since u v ×2 ,

Knuth's coherent presentation

We reduce the coherent presentation PreCol 3 (n) into a coherent presentation of the monoid P n whose underlying 2-polygraph is Knuth 2 (n). We proceed in three steps developed in the next sections.

Step 1. We apply the inverse of the Tietze transformation T γ←α , that coherently replaces the 2-cells γ xp...x 1 by the 2-cells α xp,x p-1 ...x 1 , for each column x p . . . x 1 such that (x p . . . x 1 ) > 2.

Step 2. We apply the inverse of the Tietze transformation T η,ε←α , that coherently replaces the 2-cells α x,zy by η c x,y,z , for every 1 x y < z n, and the 2-cells α y,zx by ε c x,y,z , for every 1 x < y z n.

Step 3. Finally for each column x p . . . x 1 , we coherently eliminate the generator c xp...x 1 together with the 2-cell γ xp...x 1 with respect to the order deglex . Let us denote by CPC 3 (n) the (3, 1)-polygraph whose underlying 2-polygraph is CPC 2 (n), and the set of 3-cells is defined by

{ T -1 γ←α (R Γ 3 (C x,v,t )) for x v t ×1 ×2 } ∪ { T -1 γ←α (R Γ 3 (D x,v,t )) for x v t ×2 ×2 }.
In this way, we extend the Tietze transformation T -1 γ←α into a Tietze transformation between the (3, 1)-polygraphs PreCol 3 (n) and CPC 3 (n). The (3, 1)-polygraph PreCol 3 (n) being a coherent presentation of the monoid P n and the Tietze transformation T -1 γ←α preserves the coherence property, hence we have the following result. 4.4.2. Lemma. For n > 0, the monoid P n admits CPC 3 (n) as a coherent presentation. defined from Col 3 (n) to Knuth cc 3 (n) as follows. Firstly, the transformation R eliminates the 3-cells of Col 3 (n) of the form A x,v,t , B x,v,t and C x,v,t which are not of the form C x,v,t and reduces its set of 2-cells to PreCol 2 (n). Secondly, this transformation coherently replaces the 2-cells γ xp...x 1 by the 2-cells α xp,x p-1 ...x 1 , for each column x p . . . x 1 such that (x p . . . x 1 ) > 2, the 2-cells α x,zy by η c x,y,z for 1

x y < z n and the 2-cells α y,zx by ε c x,y,z for 1 x < y z n. Finally, for each column x p . . . x 1 , the transformation R eliminates the generator c xp...x 1 together with the 2-cell γ xp...x 1 with respect to the order deglex .

Let us denote by Knuth 3 (n) the extended presentation of the monoid P n obtained from Knuth 2 (n) by adjunction of the following set of 3-cells { R(C x,v,t ) for x v t ×1 ×2 } ∪ { R(D x,v,t ) for x v t ×2 ×2 }.

The transformation R being a composite of Tietze transformations, it follows the following result. In this way, we obtain the Knuth coherent presentation of the monoid P 2 that we obtain in Example 4.3.5 as a consequence of the fact that the 2-polygraph Knuth 2 (2) is convergent.

η 1 , 1 , 2 :

 112 211 ⇒ 121 ε 1,2,2 : 221 ⇒ 212.

2 has generators c 1 , 1 p

 11 c 2 , c 21 , with the rules α 2,1 : c 2 c 1 ⇒ c 21 , α 1,21 : c 1 c 21 ⇒ c 21 c 1 and α 2,21 : c 2 c 21 ⇒ c 21 c 2 . This presentation has only one critical branching: and thus the 3-cell of the extended coherent presentation is reduced to this 3-cell defined by this confluence diagram. Note that for column presentations of the monoids P 3 , P 4 and P 5 we count respectively 7, 15 and 31 generators, 22, 115 and 531 relations, 42, 621 and 6893 3-cells.

2. 3 . 1 .

 31 Columns as generators. Let us denote by Col 1 (n) = c u u ∈ col(n) the set of column generators of the monoid P n and by

  For 1 x y < z n, consider the following critical branching c x c z c y c x γ zy 7 W c x c zy c z c x c y η c x,y,z @ γzx c y 4 T c zx c y of the 2-polygraph Knuth cc 2 (n). Let consider the Tietze transformation

3. 2 . 1 .

 21 Column coherent presentation. The presentation Col 2 (n) has exactly one critical branching of the form c e c e c t c u c v c t α u,v c t 9 Y c u α v,t 5 U c u c w c w

  c e c e c t c e α e ,t 7 W X u,v,t Õ % c e c b c b α e,b c b 3 S c u c v c t α u,v c t A a c u α v,t 3 S c a c d c b c u c w c w α u,w c w 7 W c a c a c w c a α a ,w A a

c a c a w c u c w c w α u,w c w 7 W

 7 c a c a c w c a α a ,w B b

3. 2 . 6 .

 26 Lemma. If u v t ×2 ×2 , we have the following confluent critical branching: v c t A a c u α v,t 3 S c a c d c b c u c w c w α u,w c w 7 W c a c a c w c a α a ,w A a

  y 1 into u and we obtain a = e. Since c e c b c b is the unique tableau obtained from c u c v c t and a = e, we obtain C(a w ) = bb . As a consequence, there is a 2-cell α a ,w : c a c w ⇒ c b c b yielding the following confluence diagram:

  v c t A a c u α v,t 3 S c u c w c w α u,w c w 7 W c a c a c w c a α a ,w i

  y p+1 b)) = P(eb). Hence, there is a 2-cell α e,b : c e c b ⇒ c a c a which yields the confluence diagram:

  v c t A a c u α v,t 3 S c u c w c w α u,w c w 7 W c a c a c w

  c e c e c t c e α e ,t 7 W D (3) u,v,t Õ % c e c e t c u c v c t α u,v c t A a c u α v,t 3 S c u c w c w α u,w c w 7 W c e c a c w c e α a ,w i c e c e c t c e α e ,t 7 W D (4) u,v,t Õ % c e c e t α e,e t 3 S c u c v c t α u,v c t A a c u α v,t 3 S c a c a w c u c w c w α u,w c w 7 W c a c a c w c a α a ,w A a Suppose the tableau P(e t) consists of two columns. Using the same arguments as in Case 2 and Case 3, we obtain a confluence diagram of the form D u,v,t , D

4. 1 .

 1 Homotopical reduction procedure 4.1.1. Homotopical reduction procedure. Let Σ be a (3, 1)-polygraph.

4. 1 . 3 .

 13 Homotopical reduction of the polygraph Col 3 (n). In the rest of this section, we apply three steps of homotopical reduction on the (3, 1)-polygraph Col 3 (n). As a first step, we apply in 4.2 a homotopical reduction on the (3, 1)-polygraph Col 3 (n) with a collapsible part defined by some of the generating triple confluences of the 2-polygraph Col 2 (n). In this way, we reduce the coherent presentation Col 3 (n) of the monoid P n into the coherent presentation Col 3 (n) of P n , whose underlying 2-polygraph is Col 2 (n) and the 3-cells X u,v,t are those of Col 3 (n), but with (u) = 1. We reduce in 4.3 the coherent presentation Col 3 (n) into a coherent presentation PreCol 3 (n) of P n , whose underlying4.2. A reduced column presentation2-polygraph is PreCol 2 (n). This reduction is given by a collapsible part defined by a set of 3-cells of Col 3 (n). In a final step, we reduce in 4.4 the coherent presentation PreCol 3 (n) into a coherent presentation Knuth 3 (n) of P n whose underlying 2-polygraph is Knuth 2 (n). By[START_REF] Gaussent | Coherent presentations of Artin monoids[END_REF] Theorem 2.3.4], all these homotopical reductions preserve coherence. That is, the (3, 1)-polygraph Col 3 (n) being a coherent presentation of P n , the (3, 1)-polygraphs Col 3 (n) and Knuth 3 (n) are coherent presentations of P n .

≡ c e c y c d 1 c d 1 α y,d 1 7 WX xp,s,d 1 c d 1 Õ % c e c b c s 2 c d 1 α s 2 c u 1 c w c w α u 1 ,w 0 P c xp c s c d 1 c d 1 α s,d 1 ) I α xp,s E e c a c d c s 2 c d 1 α α s 2 ,d 1 F f c xp c a 1 c a 1 c w α a 1 ,w 7 WX z,a 1 ,w 6 V c a c d c s 2 c d 1 α s 2 ,d 1 q c xp c u 1 c w c w α xp,u 1 D d α u 1 ,w 0 P c a c z c s 3 c d 1 α z,s 3 E

 711211171611113 α xp,a 1 0 P c xp c a 1 c s 3 c d 1 α xp,a 1 7 W c a c z c s 3 c d 1 α z,s 3 e c xp c a 1 c a 1 c w α xp,a 1 7 W c a c z c a 1 c w α a 1 ,w E e α z,a 1 i

  we obtain that u x. Hence, we have two cases to consider. If u x , then C(uv) = (xu)x . Hence, the 2-cell α u,v is equal to the 2-cell α u,xx : c u c xx ⇒ c xu c x . In the other case, if x < u, then C(uv) = (ux )x. Hence the 2-cell α u,v is equal to α u,xx : c u c xx ⇒ c ux c x .

c x c v c t α x,v c t 8 X

 8 c x α v,t 5 U c x c w c w α x,w c w 7 W c xv c z l ...z q+1 c w c xv α z l ...z q+1 ,w r with x v t ×1 ×2 , and the 3-cells of type R Γ 3 (D x,v,t ) where c e c e c t c e α e ,t 7 W D x,v,t Õ % c e c b c b α e,b c b 3 S c x c v c t α x,v c t A a c x α v,t 3 S c a c d c b c x c w c w α x,w c w 7 W c a c a c w c a α a ,w A a with x v t ×2 ×2 . The homotopical reduction R Γ 3 eliminates the 3-cells of Col 3 (n) of the form A x,v,t , B x,v,t

4. 3 . 4 . 1 p

 341 Theorem. For n > 0, the (3, 1)-polygraph PreCol 3 (n) is a coherent presentation of the monoid P n . 4.3.5. Example: coherent presentation of monoid P 2 . The 2-polygraph Knuth 2 (2) has for 2-cells η 1,1,2 : 211 ⇒ 121 and ε 1,2,2 : 221 ⇒ 212. It is convergent with only one critical branching with source the 1-cell 2211. This critical branching is confluent: Following the homotopical completion procedure given in 3.1.4, the 2-polygraph extended by the previous 3-cell is a coherent presentation of the monoid P 2 . Consider the column presentation Col 2 (2) of the monoid P 2 with 1-cells c 1 , c 2 and c 21 and 2-cells α 2,1 , α 1,21 and α 2,21 . The coherent presentation Col 3 (2) has only one 3It follows that the (3, 1)-polygraphs Col 3 (2) and Col 3 (2) coincide. Moreover, in this case the set Γ 3 is empty and the homotopical reduction R Γ 3 is the identity and thus PreCol 3 (2) is also equal to Col 3 (2).

4. 3 . 6 .

 36 Example: coherent presentation of monoid P 3 . For the monoid P 3 , the Knuth presentation has 3 generators and 8 relations. It is not convergent, but it can be completed by adding 3 relations. The obtained presentation has 27 3-cells corresponding to the 27 critical branchings. The column coherent presentation Col 3 (3) of P 3 has 7 generators, 22 relations and 42 3-cells. The coherent presentation Col 3 (3) has 7 generators, 22 relations and 34 3-cells. After applying the homotopical reduction R Γ 3 , the coherent presentation PreCol 3 (3) admits 7 generators, 22 relations and 24 3-cells. We give in 4.4.10 the values of number of cells of the (3, 1)-polygraphs Col 3 (n) and PreCol 3 (n) for plactic monoids of rank n 10.

4. 4 . 1 .

 41 Step 1. The Tietze transformation T γ←α : CPC 2 (n) → PreCol 2 (n) defined in Proposition 2.3.3 substitutes a 2-cell α xp,x p-1 ...x 1 : c xp c x p-1 ...x 1 =⇒ c xp...x 1 to the 2-cell γ xp...x 1 in C 2 (n), from the bigger column to the smaller one with respect to the total order deglex . We consider the inverse of this Tietze transformation T -1 γ←α : PreCol 2 (n) → CPC 2 (n) that substitutes the 2-cell γ xp...x 1 : c xp . . . c x 1 =⇒ c xp...x 1 to the 2-cell α xp,x p-1 ...x 1 : c xp c x p-1 ...x 1 =⇒ c xp...x 1 , for each column x p . . . x 1 such that (x p . . . x 1 ) > 2 with respect to the order deglex .

4. 4 . 3 .

 43 Step 2. The Tietze transformation T η,ε←α from Knuth cc 2 (n) into CPC 2 (n) defined in the proof of Proposition 2.3.3 replaces the 2-cells η cx,y,z and ε c x,y,z in Knuth cc 2 (n) by composite of 2-cells in CPC 2 (n).Let us consider the inverse of this Tietze transformation T -1 η,ε←α : CPC 2 (n) -→ Knuth cc 2 (n) . making the following transformations. For every 1 x y < z n, T -1 η,ε←α substitutes the 2-cell η c x,y,z : c z c x c y ⇒ c x c z c y to the 2-cell α x,zy . For every 1 x < y z n, T -1 η,ε←α substitutes the 2-cell ε cx,y,z : c y c z c x ⇒ c y c x c z to the 2-cell α y,zx . Let us denote by Knuth cc 3 (n) the (3, 1)-polygraph whose underlying 2-polygraph is Knuth cc 2 (n) and whose set of 3-cells is{ T -1 η,ε←α (T -1 γ←α (R Γ 3 (C x,v,t ))) for x v t ×1 ×2 } ∪ { T -1 η,ε←α (T -1 γ←α (R Γ 3 (D x,v,t ))) for x v t ×2 ×2 }.We extend the Tietze transformation T -1 η,ε←α into a Tietze transformation between (3, 1)-polygraphsT -1 η,ε←α : CPC 3 (n) -→ Knuth cc 3 (n) ,where the (3, 1)-polygraph CPC 3 (n) is a coherent presentation of the monoid P n and the Tietze transformation T -1 η,ε←α preserves the coherence property, hence we have the following result. 4.4.4. Lemma. For n > 0, the monoid P n admits Knuth cc 3 (n) as a coherent presentation. 4.4.5. Step 3. Finally, in order to obtain the Knuth coherent presentation, we perform an homotopical reduction, obtained using the homotopical reduction R Γ 2 on the (3, 1)-polygraph Knuth cc 3 (n) whose collapsible part Γ 2 is defined by the 2-cells γ u of C 2 (n) and the well-founded order deglex . Thus, for every 2-cell γ xp...x 1 : c xp . . . c x 1 =⇒ c xp...x 1 in C 2 (n), we eliminate the generator c xp...x 1 together with the 2-cell γ xp...x 1 , from the bigger column to the smaller one with respect to the order deglex . 4.4.6. Knuth coherent presentation. Using the Tietze transformations constructed in the previous sections, we consider the following composite of Tietze transformations R := R Γ 2 • T -1 η,ε←α • T -1 γ←α • R Γ 3

4. 4 . 7 . 1 p 1 , 1 , 2 : c 2 c 1 c 1 ⇒ c 1 c 2 c 1 and ε c 1 , 2 , 2 : c 2 c 2 c 1 ⇒ c 2 c 1 c 2 and the following 3

 471112112213 Theorem. For n > 0, the (3, 1)-polygraph Knuth 3 (n) is a coherent presentation of the monoid P n . 4.4.8. Example: Knuth's coherent presentation of the monoid P 2 . We have seen in Example 4.3.5 that the (3, 1)-polygraphs Col 3 (2), Col 3 (2) and PreCol 3 (2) are equal. The coherent presentation PreCol 3 (2) has three 2-cell α 2,1 , α 1,21 , α 2,21 and the following 3-cell: By definition of the 2-cells of C 2 (2), we have γ 21 := α 2,1 . Thus we obtain that T -1 γ←α (C 2,1,21 ) = C 2,1,21 up to replace all the 2-cells α 2,1 in C 2,1,21 by γ 21 . Hence, the coherent presentation CPC 3 (2) is equal to PreCol 3 (2). In order to compute the 3-cell T -1 η,ε←α (T -1 γ←α (C 2,1,21 )), the 2-cells α 1,21 and α 2,21 in C 2,1,21 are respectively replaced by the 2-cells η c 1,1,2 and ε c 1,2,2 as in the following diagram c 21 c 21 C 2,1,21 Õ % Hence, the Knuth coherent presentation Knuth 3 (2) of the monoid P 2 has generators c 1 and c 2 subject to the Knuth relations η c

  2.2.1. Rows, columns and tableaux. For n > 0, we denote by [n] the set {1, 2, . . . , n} totally ordered by 1 < 2 < . . . < n. A row is a non-decreasing 1-cell x 1 . . . x k in the free monoid [n] * , i.e., with x 1 x 2 . . . x k . A column is a decreasing 1-cell x p . . . x 1 in [n] * , i.e., with x p > . . . > x 2 > x 1 . We will denote by col(n) the set of non-empty columns in [n] * . We denote by (w) (resp. nds (w)) the length of a 1-cell w (resp. the length of the longest non-decreasing subsequence in w). A row x 1 . . . x k dominates a row y 1 . . . y l , and we denote x 1 . . . x k y 1 . . . y l , if k l and x i > y i , for 1 i k. Any 1-cell w in [n] * has a unique decomposition as a product of rows of maximal length u 1 . . . u k . Such a 1-cell w is a tableau if u 1 u 2 .

  2.2.3. Knuth's 2-polygraph and the plactic congruence. The plactic monoid of rank n, denoted by P n , is the quotient of the free monoid [n] * by the congruence ∼ plax(n) , defined by u ∼ plax(n) v if P(u) = P(v). The Knuth 2-polygraph of rank n is the 2-polygraph, denoted by Knuth 2 (n), whose set of 1-cells is [n] and the set of 2-cells is

  Thus uv t ×1 and u vt ×1 and there exist 2-cells α uv,t and α u,vt in Col 2 (n) making the critical branching (3) confluent, where e = uv, w = vt and e , w are the empty column.

	3.2.4. Lemma. If u v t ×2 ×1 , we have the following confluent critical branching:
	c e c e c t	c e α e ,t Õ % B u,v,t	7 W c e c e t α e,e t 1 Q

  1 ,w . From x p u 1 , we deduce that X xp,u 1 ,v is either of the form A xp,u 1 ,v or C xp,u 1 ,v . Let us denote by s and s the two columns of the tableau P(u 1 v). The 3-cell X xp,u 1 ,v being confluent, we obtain that C(x p s) = ey with y in [n] and C(ys ) = e . From y s , we deduce that X y,s ,t is either of the form A y,s ,t or C y,s ,t . Denote by d 1 and d 1 the two columns of the tableau P(s t). The 3-cell X y,s ,t being confluent and C(e t) = bb , we have C(yd 1 ) = bs 2 and C(s 2 d 1 ) = b . On the other hand, the 3-cell X u 1 ,v,t is confluent, then we have C(sd 1 ) = a 1 s 3 and C(a 1 w ) = s 3 d 1 . Finally, since the 3-cell X xp,s,d 1 is confluent, we obtain C(zs 3 ) = ds 2 .4.2.2. Reduced coherent column presentation.Let us define by Col 3 (n) the extended presentation of the monoid P n obtained from Col 2 (n) by adjunction of one family of 3-cells X x,v,t of the form (4), for every 1-cell x in [n] and columns v and t in col(n) such that x v t × × . The following result shows that this reduced presentation is also coherent.4.2.3. Proposition.For n > 0, the (3, 1)-polygraph Col 3 (n) is a coherent presentation of the monoid P n .Proof. Let Γ 4 be the collapsible part made of the family of 3-sphere Ω xp,u 1 ,v,t , indexed by x p in [n] and u 1 , v, t in col(n) such that u v t

		×1
	and u 1 v
	×1	and s t
	× ×

× ×

  and u rev u for any columns u, v, u and v in col(n) such that u v , where rev is the total order on col(n) defined by u rev v if (u) > (v) or (u) = (v) and u < lex v, for all u and v in col(n).4.3.1.The homotopical reduction R Γ 3 . Consider the well-founded order on the 2-cells of Col 2 (n) and the well-founded order on 3-cells defined in the proof of Proposition 4.2.3. The reduction R Γ 3 induced by these orders can be decomposed as follows. For any x in [n] and columns v, t such that x v t, ×1 ×1we have α x,v α xv,t , α v,t α xv,t and α x,vt α xv,t . The reduction R Γ 3 removes the 2-cell α xv,t together with the 3-cell A x,v,t defined in Lemma 3.2.3. By iterating this reduction on the length of the column v, we reduce all the 2-cells of Col 2 (n) to the following set of 2-cells

×

and u v ×

  4.3.3. Pre-column coherent presentation. The homotopical reduction R Γ 3 , defined in 4.3.1, reduces the coherent presentation Col 3 (n) into a coherent presentation of the monoid P n . The set of 2-cells of this coherent presentation is given by (13), which is PreCol 2 (n) by Lemma 4.3.2. Let us denote by PreCol 3 (n) the extended presentation of the monoid P n obtained from PreCol 2 (n) by adjunction of the 3-cells of type R Γ 3 (C x,v,t ) where

	c xv c t
	C x,v,t Õ %

This work is partially supported by the French National Research Agency, ANR-13-BS02-0005-02.

4.4.9. Procedure to compute the 3-cells of Knuth 3 (n). We present a procedure that computes the 2-sources and the 2-targets of the 3-cells of the Knuth coherent presentation Knuth 3 (n), using the constructions given in Sections 3 and 4. The first step consists to define a procedure, called ReduceG3(α u,v ), that replaces a 2-cell α u,v of Col 2 (n) by a 2-cell of the 2-category PreCol 2 (n) * using a reduction defined in 4.3.1 with respect to the 3-cells A x,v,t , B x,v,t and C x,v,t , where x is in [n] and v and t are in col(n). Given u in col(n) such that (u) 2 and u = x p x p-1 . . . x 2 x 1 , we will denote x p (resp. x 1 ) by first(u) (resp. last(u)) and the column x p-1 . . . x 1 (resp. x p . . . x 2 ) by rem f (u) (resp. rem l (u) ). If (u) = 1, we set first(u) = last(u) = u and rem f (u) and rem l (u) are the empty columns. We define the procedure ElimAlpha(α x,v ) that replaces a 2-cell α x,v of PreCol 2 (n) by a 2-cell of the 2-category Knuth cc 2 (n) * , using the Tietze transformations given in 4.4.1 and 4.4.3. In the sequel, we will represent every

We define the procedure ElimAG(f) that replaces in a 2-cell f of the 2-category PreCol 2 (n) * , every α x,v in PreCol 2 (n) by ElimAlpha(α x,v ). In a second step, it replaces every γ u in C 2 (n) by 1 u , with respect to the reduction R Γ 2 defined in 4.4.5.

ElimAG(f):

We define the procedure ComputeC (n) that computes the 2-sources and the 2-targets of the 3-cells R(C x,v,t ) of the Knuth coherent prensentation, where R is the Tietze transformation defined in 4.4.6.

ComputeC (n):

We define a procedure, called ComputeD(n), that computes the 2-sources and the 2-targets of the 3-cells R(D x,v,t ) of the Knuth coherent prensentation, where R is the Tietze transformation defined in 4.4.6.

ComputeD(n):

Finally, a way to compute the 2-sources and the 2-targets of the 3-cells of the Knuth coherent presentation Knuth 3 (n) is to apply at the same time the procedures ComputeC (n) and ComputeD(n).

4.4.10. Coherent presentations in small ranks. Let us denote by Knuth KB 2 (n) the convergent 2-polygraph obtained from Knuth 2 (n) by the Knuth-Bendix completion using the lexicographic order. For n = 3, the polygraph Knuth KB 2 (3) is finite, but Knuth KB 2 (n) is infinite for n 4, [START_REF] Kubat | Gröbner-Shirshov bases for plactic algebras[END_REF]. Let us denote by Knuth KB 3 (n) the Squier completion of Knuth KB 2 (n). For n 4, the polygraph Knuth KB 2 (n) having an infinite set of critical branching, the set of 3-cells of Knuth KB 3 (n) is infinite. However, the (3, 1)-polygraph Knuth 3 (n) is a finite coherent convergent presentation of P n . Table 1 presents the number of cells of the coherent presentations Knuth 3 (n), Col 3 (n) and Col 3 (n) of the monoid P n .