Clément Alleaume
email: clement.alleaume@univ-st-etienne.fr

REWRITING IN HIGHER DIMENSIONAL LINEAR CATEGORIES AND APPLICATION TO THE AFFINE ORIENTED BRAUER CATEGORY

In this paper, we introduce a rewriting theory of linear monoidal categories. Those categories are a particular case of what we will define as linear (n, p)-categories. We will also define linear (n, p)-polygraphs, a linear adapation of n-polygraphs, to present linear (n -1, p)-categories. We focus then on linear (3, 2)-polygraphs to give presentations of linear monoidal categories. We finally give an application of this theory in linear (3, 2)-polygraphs to prove a basis theorem on the category AOB with a new method using a rewriting property defined by van Ostroom: decreasingness.

LINEAR (n, p)-CATEGORIES

This section and section 3 will recall the basic notions of n-category and n-polygraphs. The rewriting techniques used in this paper will be presented in the last two sections.

INTRODUCTION

Affine walled Brauer algebras were introduced by Rui and Su [START_REF] Rui | Affine walled brauer algebras[END_REF] in the study of super Schur-Weyl duality. A result of [START_REF] Rui | Affine walled brauer algebras[END_REF] is the Schur-Weyl duality between general Lie superalgebras and affine walled Brauer algebras. A linear monoidal category, the affine oriented Brauer category AOB was introduced in [START_REF] Brundan | A basis theorem for the affine oriented Brauer category and its cyclotomic quotients[END_REF] to encode each walled Brauer algebra as one of its morphism spaces. This category is used to prove basis theorems for the affine walled Brauer algebras given in [START_REF] Rui | Affine walled brauer algebras[END_REF], which gives an explicit basis for each affine walled Brauer algebra. The proof of this theorem uses an intermediate result on cyclotomic quotients of AOB. For each of those quotients, a basis is given. With these multiple bases, each morphism space of AOB is given a generating family which is proved to be linearly independent.

Our aim is to give a constructive proof of the mentioned basis result. For this, we study AOB in this article by rewriting methods. Rewriting is a model of computation presenting relations between expressions as oriented computation steps. There are multiple examples of rewriting systems. An abstract rewriting system [START_REF] Huet | Confluent reductions: abstract properties and applications to term rewriting systems[END_REF] is the data of a set S and a relation → on S called the rewrite relation. A rewriting sequence from a to b is a finite sequence (u 0 , u 1 , • • • u n-1 , u n ) of elements of S such that:

a = u 0 , b = u n ,
and for any 0 k < n, we have u k → u k+1 . A word rewriting system is the data of an alphabet A and a relation ⇒ on the free monoid A * over A. We say that there is a rewriting step from a word u to a word v if there are words a, b, u ′ and v ′ such that:

u = au ′ b, v = av ′ b, u ′ ⇒ v ′ .
A higher dimensional generalization of such rewriting systems has been introduced by Burroni [Bur93] under the name of polygraph. An (n+1)-polygraph is a rewriting system on the n-cells of an n-category.

To study AOB from a rewriting point of view, we will need to introduce the rewriting systems presenting monoidal linear categories. The objects giving such rewriting systems will be called linear (n, p)-polygraphs which are linear adaptations of n-polygraphs. Linear monoidal categories are a special case of what we will call linear (n, p)-categories. In this language, linear monoidal categories are linear (2, 2)-categories with only one 0-cell. They are presented by linear (3, 2)-polygraphs. Once those objects are defined, we will introduce the rewriting theory of linear (3, 2)-polygraphs. Once we have this theory, we will use it to construct bases for the morphism spaces of AOB.

Rewriting can offer constructive proofs by giving presentations of objects with certain properties. For example, two properties studied in rewriting systems are termination and confluence. A rewriting system is terminating if it has no infinite rewriting sequence, in which case all computations end. A rewriting system is confluent if any pair of rewriting sequences with the same source can be completed into a pair of rewriting sequences with the same target, in which case all computations lead to the same result. A rewriting system is said to be convergent if it is terminating and confluent.In the case of word rewriting, the property of convergence, the conjunction of termination and confluence, gives a way to decide the word problem, that is, deciding if two words in A * are equal in the quotient of A * by the relation ⇒.

What we will do in the case of AOB is giving a confluent presentation AOB of this linear (2, 2)category with some others properties. Those properties will prove the bases given in [START_REF] Brundan | A basis theorem for the affine oriented Brauer category and its cyclotomic quotients[END_REF] are indeed bases. The linear (3, 2)-polygraph AOB will not be terminating, which will prevent us to prove AOB is confluent by the use of Newman's lemma, a criterion needing termination to prove confluence from a weaker property called local confluence [START_REF] Huet | Confluent reductions: abstract properties and applications to term rewriting systems[END_REF]. To prove AOB is confluent, we will use a more general property called decreasingness introduced in [vO94]. We will prove AOB is decreasing and use the theorem from [vO94] stating decreasingness implies confluence.

In the first section, we recall first the notions of higher dimensional category theory. Then, we define linear (n, p)-categories, which will be our higher dimensional categories with linear structure. After defining them, we recall in the second section the categorical construction of the category of npolygraphs given in [START_REF] Métayer | Cofibrant objects among higher-dimensional categories[END_REF]. We define next the categorical construction of the category of linear (n, p)polygraphs. We give their main rewriting properties, such than 4.2.15 in the case (n, p) = (3, 2) in which AOB falls.

In the third section we will study the decreasingness property defined in the case of abstract rewriting systems by van Ostroom [vO94]. Then, in the last section, we recall from [START_REF] Brundan | A basis theorem for the affine oriented Brauer category and its cyclotomic quotients[END_REF] the definition of the linear (2, 2)-category AOB. This will lead us to give two linear (3, 2)-polygraphs presenting AOB. Those linear (3, 2)-polygraphs will be called AOB and AOB. The first one is a translation of the definition of AOB.

The main result of this article, Theorem 5.2.9 states AOB is confluent. It will be proved with the properties of confluence of critical branchings and decreasingness. This theorem gives us the main result of [START_REF] Brundan | A basis theorem for the affine oriented Brauer category and its cyclotomic quotients[END_REF] as an entirely constructive consequence given as corollary 5.2.10.

Preliminaries

We fix n an integer. We denote by Set the category of sets.

2.1.1. Definition. An n-graph in a category C is a diagram in C: G 0 s 0 t 0 G 1 s 1 t 1 • • • s n-2 t n-2 G n-1 s n-1 t n-1 G n such that for any 1 k n -1, we have s k-1 • s k = s k-1 • t k and t k-1 • s k = t k-1 • t k .
Those relations are called the globular relations. We just call an n-graph in Set an n-graph.

The elements of G k are called k-cells. The maps s k and t k are respectively called k-source and ktarget maps. For any l-cell u of G with l > k + 1, we respectively denote by s k (u) and t k (u) the k-cells

(s k • • • • • s l-1 )(u) and (t k • • • • • t l-1 )(u). A morphism of n-graphs F from G to G ′ is a collection (F k : G k → G ′ k
) of maps such that, for every 0 < k n, the following diagrams commute:

G k-1 s k-1 G k F k-1 F k G ′ k-1 s ′ k-1 G ′ k G k-1 t k-1 G k F k-1 F k G ′ k-1 t ′ k-1 G ′ k
We call Grph n the category of n-graphs.

In particular, Grph 0 is the category Set and Grph 1 is the category of directed graphs. We can define n-categories by enrichment. A 0-category is a set. For n 1, an n-category is a 1category enriched in (n-1)-categories. We denote by Cat n the category of n-categories and n-functors. This category has a terminal object I n with only one k-cell for 0 k n.

In an n-category, for any 0 k < n, we denote the k-composition by ⋆ k . For all 0 i < j n -1 the following equality, called exchange relation, holds:

(u ⋆ i v) ⋆ j (u ′ ⋆ i v ′ ) = (u ⋆ j u ′ ) ⋆ i (v ⋆ j v ′ ). (1)
By forgetting its units and compositions, an n-category is in particular an n-graph. We now denote by U n the forgetful functor from Cat n to Grph n .

Linear (n, p)-categories

In this section, we fix n an integer. We will define linear (n, p)-categories by induction on p n. We will denote by Vect the category of vector spaces over a fixed field.

2.2.1.

Definition. An internal n-category in Vect is the data of:

an n-graph in Vect:

V 0 s 0 t 0 V 1 s 1 t 1 • • • s n-2 t n-2 V n-1 s n-1 t n-1 V n -for each 0 k < l n, a linear unit map v → 1 v from V k to V k+1 .

Linearity of the unit maps

gives us the following relation:

1 λu+µv = λ1 u + µ1 v (2)
for any scalars λ and µ and any k-cells u and v such that p k < n,

-for each 0 k < l n, a linear composition map ⋆ k from V l × V k V l to V k .
Linearity of the unit maps gives us the following properties:

(f + g) ⋆ k (f ′ + g ′ ) = f ⋆ k f ′ + g ⋆ k g ′ , (3)
λf ⋆ k λf ′ = λ(f ⋆ k f ′ ). (4)
for any scalar λ and any pairs (f, f ′ ) and (g, g ′ ) of k-composable l-cells such that p k < l n verifying the axioms of n-categories.

Internal n-categories in Vect are also called (n + 1)-vector spaces [START_REF] Baez | Higher-dimensional algebra. VI. Lie 2-algebras[END_REF], see also [START_REF] Khudaverdyan | Higher categorified algebras versus bounded homotopy algebras[END_REF].

Definition.

A linear (n, 0)-category is an internal n-category in Vect. Let us assume linear (n, p)categories are defined for p 0. A linear (n + 1, p + 1)-category is the data of a set C 0 and:

- such that:

-⋆ a,c,d • (⋆ a,b,c × id C(c,d) ) = ⋆ a,b,d • (id C(a,b) × ⋆ b,c,d ), -⋆ a,a,b • (i a × id C(a,b) ) • is l = id C(a,b) = ⋆ a,b,b • (id C(a,b) × i q )
• is r where is l and is r respectively denote the canonic isomorphisms from C(a, b) to

I n × C(a, b) and to C(a, b) × I n .
2.2.3. Remark. In particular, a linear (n, p)-category is an n-category.

A morphism of linear (n, p)-categories from C to C ′ is an n-functor:

C 0 s 0 t 0 C 1 s 1 t 1 • • • s n-2 t n-2 C n-1 s n-1 t n-1 C n F 0 F 1 F n-1 F n C ′ 0 s ′ 0 t ′ 0 C ′ 1 s ′ 1 t ′ 1 • • • s ′ n-2 t ′ n-2 C ′ n-1 s ′ n-1 t ′ n-1 C ′ n
such that for any p k n, the map F k is linear. We denote by LinCat n,p the category of linear (n, p)categories. We denote by U n,p the forgetful functor from LinCat n,p to Grph n .

Example.

A linear (1, 1)-category is just a linear category or a category enriched in vector spaces as introduced by Mitchell [START_REF] Mitchell | Rings with several objects[END_REF].

2.2.5. Remark. Let C be a linear (n, p)-category with 0 p < n. The underlying (n -1)-category to C is a linear (n -1, p)-category. Indeed, there is an internal (n + p -1)-graph in the category of vector spaces given by:

C p s p t p C p+1 s p+1 t p+1 • • • s n-3 t n-3 C n-2 s n-2 t n-2 C n-1
which can be completed into an (n -1)-category:

C 0 s 0 t 0 C 1 s 1 t 1 • • • s p-2 t p-2 C p-1 s p-1 t p-1 C p s p t p C p+1 s p+1 t p+1 • • • s n-3 t n-3 C n-2 s n-2 t n-2 C n-1
The source maps, target maps and composition maps of this (n -1)-category meet all the requirements of a linear (n -1, p)-category.

POLYGRAPHS

n-Polygraphs

The notion of polygraph was introduced by Burroni [START_REF] Burroni | Higher-dimensional word problems with applications to equational logic[END_REF]. It was introduced independently by Street under the name of computad [START_REF] Street | The algebra of oriented simplexes[END_REF] as system of generators and relations for higher dimensional categories. Let us recall the constructions of the categories of n-categories with a globular extension and npolygraphs from [START_REF] Métayer | Cofibrant objects among higher-dimensional categories[END_REF].

3.1.1. Definition. The category Cat + n of n-categories with a globular extension is defined by the following pullback diagram:

Cat + n Grph n+1 Grph n Cat n Grph n U n U G n
where U G n is the functor from Grph n+1 to Grph n associating to each (n + 1)-graph its underlying ngraph by eliminating the (n + 1)-cells.

In a diagrammatic way, a globular extension of an n-category C is the data of a set Γ and of two maps s n and t n from Γ to C n forming an (n + 1)-graph:

C 0 s 0 t 0 C 1 s 1 t 1 • • • s n-2 t n-2 C n-1 s n-1 t n-1 C n s n t n Γ
A morphism of n-categories with globular extension from (C, Γ ) to (C ′ , Γ ′ ) is the data of an n-functor F from C to C ′ and a map ϕ from Γ to Γ ′ such that (F, ϕ) makes a morphism of (n + 1)-graphs.

3.1.2. Definition. Let (C, Γ ) be an n-category with globular extension. The free (n + 1)-category over (C, Γ ) is the (n + 1)-category which underlying n-category is C and which (n + 1)-cells are the compositions of elements of Γ and elements of the form 1 u where u is in C n . The free functor from Cat + n to Grph n+1 is denoted by F W n+1 .

3.1.3. Definition. Pol 0 is the category of sets and the functor F 0 from Pol 0 to Cat 0 is the identity functor. Let us assume the category Pol n of n-polygraphs and the functor F n from Pol n to Cat n are defined. The category Pol n+1 is defined by the following pullback diagram:

Pol n+1 Grph n+1 Grph n Pol n Cat n U n F n U G n U P n U GP n+1
We denote by F P n+1 the unique functor making the following diagram commutative:

Pol n+1 Pol n F n F P n+1 Cat + n Grph n+1 Grph n Cat n Grph n U n U G n U P n U GP n+1
The functor F n+1 is defined as the following composite:

Pol n+1 Cat + n Cat n+1 F P n+1 F W n+1
A 0-polygraph is a set. The free 0-category over a 0-polygraph is the 0-polygraph itself. Given an n-polygraph Σ, we denote by Σ * the free n-category over Σ. Let us assume n-polygraphs and free n-categories over n-polygraphs are defined. An (n + 1)-polygraph is the data of an npolygraph Σ:

Σ 0 Σ * 0 s 0 t 0 Σ 1 Σ * 1 s 1 t 1 • • • • • • s n-2 t n-2 Σ n-1 Σ * n-1 s n-1 t n-1 Σ n
and a globular extension Σ n+1 of the free n-category over Σ:

Σ 0 Σ * 0 s 0 t 0 Σ 1 Σ * 1 s 1 t 1 • • • • • • s n-2 t n-2 Σ n-1 Σ * n-1 s n-1 t n-1 Σ n Σ * n Σ n+1 s n t n
The elements of Σ k are called k-cells.

Linear (n, p)-polygraphs

In this section, we introduce linear (n, p)-polygraphs.

Definition. The category LinCat +

n,p of linear (n, p)-categories with a globular extension is defined by the following pullback diagram:

LinCat + n,p Grph n+1 Grph n LinCat n,p Grph n U n,p U G n 3.2.2. Definition.
The free linear (0, 0)-category Σ ℓ over the 0-polygraph Σ is the vector space spanned by Σ. For n > 0, the free linear (n, n)-category over the n-polygraph Σ is the linear (n, n)-category Σ ℓ such that Σ ℓ k = Σ * k for 0 k < n and Σ ℓ n (u, v) is the vector space spanned by Σ * (u, v) for each (n -1)-cells u and v.

3.2.3. Definition. LinPol n,n is the category of n-polygraphs and the functor F n,n from LinPol n,n to LinCat n,n is the free functor from LinPol n,n to LinCat n,n . Let us assume the category LinPol n,p of linear (n, p)-polygraphs and the functor F n,p from LinPol n,p to LinCat n,p are defined. The category LinPol n+1,p is defined by the following pullback diagram:

LinPol n+1,p Grph n+1 Grph n LinPol n,p LinCat n,p U n,p F n,p U G n U P n,p U GP n+1,p
We denote by F P n+1,p the unique functor making the following diagram commutative:

LinCat + n,p Grph n+1 Grph n LinCat n,p Grph n U n,p U G n LinPol n+1,p LinPol n,p F P n+1,p F n,p U P n,p U GP n+1,p
The functor F n+1,p is defined as the following composite:

LinPol n+1,p LinCat + n,p LinCat n+1,p F P n+1,p F W n+1,p 3.2.4. Definition. Let 0 p n.
The free linear (n + 1, p)-category over a linear (n, p)-category with globular extension (C, Γ ) is the linear (n + 1, p)-category having C as an underlying linear (n, p)category and which (n + 1)-cells are defined this way:

we construct the set A 1 of all (n + 1)-cells of the form

1 u 1 ⋆ n • • • ⋆ 0 α ⋆ 0 • • • ⋆ n 1 u 2n where each u k is in C n and α is in Γ ,
we define the set of all formal n-compositions of elements of A 1 quotiented by the exchange relations (1) to obtain a set A 2 ,

if p = 0, the (n + 1)-cells of the free linear (n + 1, p)-category are the linear combinations of elements of A 2 quotiented by Relations (2), (3) and (4). if p > 0, the (n + 1)-cells of the free linear (n + 1, p)-category are the linear combinations of (p -1)-composable elements of A 2 quotiented by Relations (2), (3) and (4).

A linear (n, n)-polygraph is an n-polygraph. Given an n-polygraph Σ, we denote by Σ * the free ncategory over Σ. Let us assume linear (n, p)-polygraphs are defined. a linear (n + 1, p)-polygraph is the data of a linear (n, p)-polygraph Σ:

Σ 0 Σ * 0 s 0 t 0 Σ 1 Σ * 1 s 1 t 1 • • • • • • s n-2 t n-2 Σ n-1 Σ ℓ n-1 s n-1 t n-1 Σ n
and a globular extension Σ n+1 of the free (n, p)-category Σ ℓ over Σ:

Σ 0 Σ * 0 s 0 t 0 Σ 1 Σ * 1 s 1 t 1 • • • • • • s n-2 t n-2 Σ n-1 Σ ℓ n-1 s n-1 t n-1 Σ n Σ ℓ n Σ n+1 s n t n

LINEAR REWRITING

Higher dimensional monomials

We will consider n > 0 for this section.

In 2-categories, 2-cells can be represented as planar diagrams with an upper boundary and a lower boundary. The upper boundary will correspond to the 1-source of the 2-cell and the lower boundary will correspond to its 1-target. A generating 2-cell with 1-source a and 1-target b will be pictured as follows: ... ...

... α 0 = 1 a , ... ... α k + 1 = ... α ... ... α k (5)
In linear (2, 2)-categories, linear combinations of such diagrams will be used to represent 2-cells. Such a representation will be used later.

Example.

Let C be a linear (2, 2)-category with only one 0-cell, one 1-cell x from and α a 2-cell from x to xx. By representing 1 x this way: we can represent α by: Then, the following diagrams:

, + respectively correspond to α ⋆ 0 α and α ⋆ 1 (1 x ⋆ 0 α) + α ⋆ 1 (α ⋆ 0 1 x ).
4.1.2. Definition. Let Σ be a linear (n, n -1)-polygraph. A monomial of Σ is a (n -1)-cell of the free (n -1)-category Σ * (n-1) . We say Σ is left-monomial if all elements of Σ n have monomial source.

4.1.3. Remark. Let Σ be a linear (n, n -1)-polygraph. Any n-cell of Σ ℓ has a unique decomposition as a linear combination of monomials.

4.1.4. Definition. Let Σ be an n-polygraph. A monomial order on Σ is a well-founded order ≺ on Σ * n such that:

for any 0 k < n and any n-cells a, b, u and v, we have a

⋆ k u ⋆ k b ≺ a ⋆ k v ⋆ k b if u ≺ v whenever this makes sense, -≺ is strict on Σ * n (a, b)
for each (n -1)-cells a and b.

An n-polygraph does not always have a monomial order.

Example. Let Σ be a 2-polygraph with only one 0-cell, one 1-cell and two 2-cells represented by:

, If there is a monomial order ≺ on Σ, we have one of the following inequalities:

≺ or ≺
Let us assume the first inequality is true, the other case being symmetric. Then, we have:

≺ = ≺
which contradicts the existence of a monomial order Σ * 2 .

Rewriting in linear (2, 2)-categories

We recall that a linear (2, 2)-category is a category enriched in linear categories. We will explicit the rewriting systems arising from linear (3, 2)-polygraphs. A similar theory exists in the case of npolygraphs [START_REF] Guiraud | Higher-dimensional categories with finite derivation type[END_REF]. The rewriting theory of linear (2, 2)-categories we will present is a linear adaptation of the case of 2-categories.

Let Σ be a linear (3, 2)-polygraph. The congruence generated by Σ is the equivalence relation ≡ on Σ ℓ 2 such that u ≡ v if there is a 3-cell α in Σ ℓ such that s 2 (α) = u and t 2 (α) = v. Note that in a linear (3, 2)-category, all 3-cells are invertible. if α is a 3-cell from a 2-cell u to a 2-cell v, the 3cell 1 v +1 u -α has 2-source v and 2-target u. Let Σ be a linear (3, 2)-polygraph. A linear (2, 2)-category is presented by Σ if it is isomorphic to the quotient of Σ ℓ 2 by the congruence generated by Σ. We introduce next the notions of rewriting step of a left-monomial linear (3, 2)-polygraph to define branchings, termination and conflence in this context. We will fix Σ a left-monomial linear (3, 2)polygraph for the remainder of this section.

Definition.

A rewriting step of Σ is a 3-cell of Σ ℓ of the form:

λm 1 ⋆ 1 (m 2 ⋆ 0 s 2 (α) ⋆ 0 m 3 ) ⋆ 1 m 4 + u ⇛ λm 1 ⋆ 1 (m 2 ⋆ 0 s 2 (α) ⋆ 0 m 3 ) ⋆ 1 m 4 + u λ s 2 (α) • • • • • • m 3 • • • • • • m 2 • • • • • • m 1 • • • m 4 • • • + u ⇛ λ t 2 (α) • • • • • • m 3 • • • • • • m 2 • • • • • • m 1 • • • m 4 • • • + u
where α is in Σ 3 , the m i are monomials, λ is a nonzero scalar and u is a 2-cell such that the monomial λm 2 ⋆ 1 (m 1 αm 4 )⋆ 1 m 3 does not appear in the monomial decomposition of u. A rewriting sequence of Σ is a finite or infinite sequence:

u 0 ⇛ • • • ⇛ u n ⇛ • • • of rewriting steps of Σ.
For any 2-cells u and v, we say u rewrites into v if there is a non-degenerate rewriting sequence from u to v. A 2-cell is a normal form if it can not be rewritten. We say Σ is normalizing if each 2-cell rewrites into a normal form or is a normal form.

A branching of Σ is a pair of rewriting sequences of Σ with the same 2-source: , if for all v such that u rewrites into v, the property P(v) is true, P(u) is true. Then, P(u) is true for any u ∈ Σ ℓ 2 . Proof. Let us assume P(u 0 ) is false for some u 0 ∈ Σ ℓ 2 . So, there exists u 1 ∈ Σ ℓ 2 such that u 0 rewrites into u 1 and P(u 1 ) is false. This gives us an infinite rewriting sequence:

u 0 • • • ⇛ u n ⇛ • • • • • • ⇛ u ′ n ⇛ • • • A local branching of Σ is a
u 0 ⇛ • • • ⇛ u n ⇛ • • •
where P(u n ) is false for each n ∈ N. The existence of this rewriting sequence contradicts the termination hypothesis. Noetherian induction principle is thus proved.

Termination of a rewriting system implies equivalence between confluence and local confluence [START_REF] Newman | On theories with a combinatorial definition of "equivalence[END_REF]. This result is called Newman's lemma. We have the same result in the case of linear (3, 2)polygraphs.

4.2.3. Lemma. Let Σ be a terminating left-monomial linear (3, 2)-polygraph. Then Σ is confluent if and only if Σ if locally confluent.

Proof. Confluence implies local confluence. We have to prove the converse implication, assuming Σ is terminating. Let us assume Σ is locally confluent and let u be in Σ ℓ 2 . if u is a normal form, all branchings with source u are confluent because there is no branching with source u. if u is not a normal form, and if for any v such that u rewrites into v all branchings with source v are confluent, any non-trivial branching (α, β) is confluent by the following confluence diagram:

u v α 0 t 2 (α) w β 0 t 2 (β) u ′ v ′ û
where α 0 and β 0 are respectively the first rewriting step of α and β.

This proof for linear (3, 2)-polygraphs by Noetherian induction works like in the case of abstract rewriting systems [START_REF] Huet | Confluent reductions: abstract properties and applications to term rewriting systems[END_REF].

4.2.4. Definition. An aspherical branching of Σ is a branching made up of two identical rewriting steps. A Peiffer branching is a branching of the form:

t 2 (α) ⋆ 1 s 2 (β) + h ⇚ s 2 (α) ⋆ 1 s 2 (β) + h ⇛ s 2 (α) ⋆ 1 t 2 (β) + h
where α and β are rewriting steps of Σ with monomial source. Note that all branchings of the form:

t 2 (α) ⋆ 1 s 2 (β) + h ⇚ s 2 (α) ⋆ 0 s 2 (β) + h ⇛ s 2 (α) ⋆ 1 t 2 (β) + h
are also Peiffer branchings beacause of the relation:

s 2 (α) ⋆ 0 s 2 (β) = (s 2 (α) ⋆ 0 1 s 1 (β) ) ⋆ 1 (1 s 1 (α) ⋆ 0 s 2 (β))
An additive branching is a branching of the form:

t 2 (α) + s 2 (β) ⇚ s 2 (α) + s 2 (β) ⇛ s 2 (α) + t 2 (β)
where α and β are rewriting steps of Σ. An overlapping branching is a branching that is not aspherical, Peiffer or additive. 4.2.5. Notation. Let us partition Σ 3 in multiple families and assume an overlapping branching (α, β) of Σ is confluent. If α is in the family i and β is in the family j, we denote:

u ⇛ i j v
where u is the source of (α, β) and v is a 2-cell attained after completion of (α, β).

4.2.6. Definition. Let ⊑ be the order on the monomials of Σ such that we have f ⊑ g if we have g = m 1 ⋆ 1 (m 2 ⋆ 0 f ⋆ 0 m 3 ) ⋆ 1 m 4 for some monomials m i . A critical branching is an overlapping branching with monomial source such that its source is minimal for ⊑.

4.2.7. Definition. A 3-cell of Σ ℓ is elementary if it is of the form λm 1 ⋆ 1 (m 2 ⋆ 0 α ⋆ 0 m 3 ) ⋆ 1 m 4 + u
where α is in Σ 3 , the m i are monomials, λ is a nonzero scalar, and u is a 2-cell.

Example.

Let A and B be two monomials of Σ ℓ such that there is a rewriting step from A to B.

Then, there is a 3-cell of Σ ℓ from 2A to A + B which is not a rewriting step. But this 3-cell is elementary.

4.2.9. Lemma. Let α be an elementary 3-cell. Then, there exists two rewriting sequences β and γ of length at most 1 such that α = β ⋆ 2 γ -1 .

Proof. Let us write α = α ′ + g where α ′ is a rewriting step from a 2-cell u to a 2-cell f and g is a 2-cell.

Let us write g = λu+h where f does not appear in the monomial decomposition of h. Then, (λ+1)u+h rewrites into (λ + 1)f + h either by an identity or a rewriting step and u + g rewrites into (λ + 1)u + h either by an identity or a rewriting step.

4.2.10. Definition. Let Σ be a left-monomial linear (3, 2)-polygraph. The rewrite order of Σ is the relation

′ Σ on Σ ℓ 2 defined by v ′ Σ u if u rewrites into v or u = v.
The canonical rewrite order of Σ is the minimal binary relation Σ such that:

-if v ′ Σ u, then v Σ u, -if v Σ u, v ′
Σ u ′ , and u and u ′ do not have any common monomial in their decomposition,

then v + v ′ Σ u + u ′ .
The strict canonical rewrite order of Σ is the strict order ≺ Σ defined for any 2-cells u and v by v ≺ Σ u if we have v Σ u but not u Σ v. The semistrict rewrite order of Σ is the binary relation

≺ ′ Σ on Σ ℓ 2 defined by v ≺ ′ Σ u if u rewrites into v.
4.2.11. Remark. if Σ is terminating, those relations are order relations and ≺ Σ is well-founded. In general, only ≺ Σ is an order.

4.2.12. Lemma. Let f be a 2-cell of a left-monomial linear (3, 2)-polygraph Σ. Let us assume that all critical branchings of Σ are confluent and Σ is locally confluent at every 2-cell g such that g ≺ Σ f. Then, Σ is locally confluent at f. Proof. A local branching with source f is either an aspherical branching, an overlapping branching, an additive branching or a Peiffer branching. Aspherical branchings are always confluent. Let (α, β) be an additive branching with source f. Let us write f = s 2 (α ′ ) + s 2 (β ′ ) where α ′ is the rewriting step αs 2 (β) and β ′ is the rewriting step βs 2 (α). If we do not have f

≺ Σ t 2 (α ′ ) + t 2 (β ′ ), we have either t 2 (α ′ ) + s 2 (β ′ ) ′ Σ s 2 (α ′ ) + t 2 (β ′ ) or s 2 (α ′ ) + t 2 (β ′ ) ′ Σ t 2 (α ′ ) + s 2 (β ′
), and (α, β) is confluent. Else, we have the following confluence diagram:

f α β t 2 (α ′ ) + s 2 (β ′ ) s 2 (α ′ ) + t 2 (β ′ ) t 2 (α ′ ) + t 2 (β ′ ) f ′ f ′′ f a b
Here, the dotted 3-cells are elementary, the 3-cells a and b are rewriting sequences, and the other 3-cells are rewriting steps or identities, whose existence are guaranteed by Lemma 4.2.9.

Assume there is a Peiffer branching with source f. Let us write f = u ⋆ 1 v + h where u and v are respectively monomial sources of rewriting steps α and β. If we do not have f

≺ Σ t 2 (α) ⋆ 1 t 2 (β) + h, we have either u ⋆ 1 β + h ′ Σ t 2 (α) ⋆ 1 v + h or t 2 (α) ⋆ 1 v + h ′ Σ u ⋆ 1 β + h,
and the Peiffer branching is confluent. Else, we have the following confluence diagram:

f α ⋆ 1 v + h u ⋆ 1 β + h t 2 (α) ⋆ 1 v + h u ⋆ 1 t 2 (β) + h t 2 (α) ⋆ 1 t 2 (β) + h f ′ f ′′ f a b
Assume there is an overlapping branching with source f. Let us write f = λm 1 (m 2 ⋆ 1 u ⋆ 1 m 3 )m 4 + h where the m i are monomials, u is the source of a critical branching and λ is a nonzero scalar. The overlapping branching can be written (α+h, β+h) where (α, β) is confluent by hypothesis to a common target g. if t 2 (α) = t 2 (β) or if we do not have f ≺ Σ g + h, we have either t 2 (α) + h ′ Σ t 2 (β) + h or t 2 (β)+h ′ Σ t 2 (α)+h, and the overlapping branching is confluent. Else, because ≺ Σ is well-founded, there is a monomial m of t 2 (α)t 2 (β) such that:

m can be rewritten into a linear combination of the others monomials of t 2 (α)t 2 (β), m only appears in t 2 (α) or t 2 (β).

This makes the branching (α + h, β + h) confluent and concludes the last case of local branching. 4.2.13. Theorem. Let Σ be a left-monomial linear (3, 2)-polygraph such that ≺ Σ is well-founded. Then, Σ is locally confluent if and only if its critical branchings are confluent.

Proof. if Σ is locally confluent, then its critical branchings are confluent. Conversely, let us assume that all critical branchings of Σ are confluent. Induction on ≺ Σ can be used to prove that Σ is confluent. Indeed, Σ is locally confluent at every minimal 2-cell for ≺ Σ and lemma 4.2.12 concludes the proof. 4.2.14. Lemma. Let Σ be a confluent left-monomial linear (3, 2)-polygraph. Let C be the linear (2, 2)category presented by Σ. Then, for any 1-cells u and v of C with same 0-source and 0-target, the linear map τ from Σ ℓ 2 (u, v) to C(u, v) sending each 2-cell to its congruence class has for kernel the subspace of Σ ℓ 2 (u, v) made of all 2-cells having 0 as a normal form.

Proof. Σ being left-monomial, 0 is a normal form. If a 2-cell rewrites into 0, it is congruent to 0.

Converesly, let us assume a non-zero 2-cell f is in Ker(τ). Confluence of Σ makes f rewrite into 0. This concludes the proof.

4.2.15. Proposition. Let Σ be a confluent and normalizing left-monomial linear (3, 2)-polygraph. Let C be the linear (2, 2)-category presented by Σ. Then, for any 1-cells u and v of C with same 0-source and 0-target, the set of monomials of Σ in normal form with 1-source u and 1-target v gives a basis of C(u, v).

Proof. Let us fix two 1-cells u and v of C with same 0-source and 0-target. Every 2-cell of Σ ℓ with 1-source u and 1-target v has a normal form because Σ is terminating. Each normal form is a linear combination of monomials in normal form because Σ is left-monomial. So, the family of monomials in normal form is generating. The family of monomials in normal forms is free because Σ is confluent, which allows us to use lemma 4.2.14. This concludes the proof.

Confluence by decreasingness

We fix in this section Σ a left-monomial linear (3, 2)-polygraph.

4.3.1. Definition. Let R be the set of all rewriting steps of Σ. We say Σ is decreasing if there is a wellfounded order ≺ on a partition P of R such that, for every I and J in P, every local branching (i, j) with i ∈ I and j ∈ J can be completed into a confluence diagram

j i a I b J c a J b I c ′ such that:
a I is a rewriting sequence such that for each rewriting step k in a I , there exists K in P such that k ∈ K and K ≺ I.

a J is a rewriting sequence such that for each rewriting step k in a J , there exists K in P such that k ∈ K and K ≺ J.

b I is either an identity or an element of I.

b J is either an identity or an element of J.

c and c ′ are rewriting sequences such that for each rewriting step k in c or c ′ , there exists K in P such that k ∈ K and K ≺ I or K ≺ J. The following result is proved in [vO94] in the case of abstract rewriting systems. The proof can be adapted to the case of linear (3, 2)-polygraphs.

4.3.3. Theorem. Let Σ be a left-monomial libear (3, 2)-polygraph. if Σ is decreasing, then Σ is conflu- ent.
Proof. Let us assume Σ is decreasing for a partition P of the set of its rewriting steps and an order ≺ on P. We introduce the following map | • • • | from the free monoid P * over P to N P :

if ε is the empty word of P * , for every K in P, we have |ε|(K) = 0, for every I in P and every K in P, we have |I|(I) = 1 and |I|(K) = 0 if I = K, for every I in P and every word σ of P * , we have |Iσ| = |I| + |σ (I) | where σ (I) denotes the word σ without the letters J such that J ≺ I.

We remark that for every words σ 1 and σ 2 of P * , we have:

|σ 1 σ 2 | = |σ 1 | + |σ 2 | (σ 1 ) ,
where: We now define a strict order ≺ ′ on N P . For any M and N in N P , we define M ≺ ′ N if there exist X, Y and Z in N P such that:

|σ 2 | (σ 1 ) (K) = 0 if there exists I in P such that K ≺ I and |σ 1 |(I) = 0 |σ 2 |(K) otherwise Then, we extend | • • • | to the set of finite rewriting sequences of Σ by defining |r 1 • • • r n | = |K 1 • • • K n | for every rewriting sequence u 0 ⇛ r 1 • • • ⇛ r n u n such that
-M = Z + X, -N = Z + Y, -Y is not zero,
for every I in P such that M(I) = 0, there exists J in P such that N(J) = 0 and I ≺ J.

The order ≺ ′ is well-founded because ≺ is. We call ′ the symmetric closure of ≺ ′ .

To prove that Σ is confluent, it is sufficient to prove that every branching (α, β) made of finite rewriting sequences can be completed into a confluence diagram (α

⋆ 2 τ, β ⋆ 2 σ) β α τ σ such that: |α ⋆ 2 τ| ′ |(α, β)|, ( 6
)
|β ⋆ 2 σ| ′ |(α, β)|. ( 7
)
We will prove this fact by induction on |(α, β)|. This is trivial when |(α, β)| is minimal because this is the case of a trivial branching made of two identities.

Let us now assume that for each branching (α ′ , β ′ ) made of finite rewriting sequences such that 6) and (7). For every diagram of the following form:

|(α ′ , β ′ )| ≺ ′ |(α, β)|, we can complete (α ′ , β ′ ) into a confluence diagram verifying (
δ 0 γ 1 δ 1 τ γ 2 such that |γ 1 ⋆ 2 δ 1 | ′ |(δ 0 , γ 1 )|, we have |(δ 1 , γ 2 )| ≺ ′ |(δ 0 , γ 1 ⋆ 2 γ 2 )| if γ 1 is not an identity. Indeed: |(δ 1 , γ 2 )| ≺ ′ |γ 1 | + |(δ 1 , γ 2 )| (γ 1 ) = |γ 1 ⋆ 2 δ 1 | + |γ 2 | (γ 1 ) ′ |(δ 0 , γ 1 )| + |γ 2 | (γ 1 ) = |(δ 0 , γ 1 ⋆ 2 γ 2 )|.
Let us also remark that for every diagram of the form:

δ 0 γ 1 δ 1 τ 1 γ 2 δ 2 τ 2
such that:

-|δ 0 ⋆ 2 τ 1 | ′ |(δ 0 , γ 1 )| and |γ 1 ⋆ 2 δ 1 | ′ |(δ 0 , γ 1 )|, -|δ 1 ⋆ 2 τ 2 | ′ |(δ 1 , γ 2 )| and |γ 2 ⋆ 2 δ 2 | ′ |(δ 1 , γ 2 )| We have the pasting property |δ 0 ⋆ 2 τ 1 ⋆ 2 τ 2 | ′ |(δ 0 , γ 1 ⋆ 2 γ 2 )| and |γ 1 ⋆ 2 γ 2 ⋆ 2 δ 2 | ′ |(δ 0 , γ 1 ⋆ 2 γ 2 )|. Indeed: |δ 0 ⋆ 2 τ 1 ⋆ 2 τ 2 | = |δ 0 ⋆ 2 τ 1 | + |τ 2 | (δ 0 ⋆ 2 τ 1 ) ′ |(δ 0 , γ 1 )| + |τ 2 | (δ 0 ⋆ 2 τ 1 )(γ 1 ) ′ |(δ 0 , γ 1 ⋆ 2 γ 2 )|, |γ 1 ⋆ 2 γ 2 ⋆ 2 δ 2 | = |γ 1 ⋆ 2 γ 2 | + |δ 2 | (γ 1 )(γ 2 ) ′ |γ 1 ⋆ 2 γ 2 | + |δ 2 | (γ 2 ) ′ |(δ 0 , γ 1 ⋆ 2 γ 2 )|.
To prove (α, β) is confluent when α and β have nonzero length, we consider α 0 the first step of α and β 0 the first step of β. We have then the following confluence diagram:

IH1 α 0 t 2 (α) β 0 t 2 (β) D IH2
Where D verifies ( 6) and ( 7) by decreasingness of Σ, the diagram IH1 exists because of the induction hypothesis and verifies ( 6) and ( 7) by the pasting property. Finally, the induction hypothesis allows us to construct IH2. The pasting property proves all the diagram verifies (6) and ( 7). This proves in particular by well-founded induction Σ is confluent.

Example.

The linear (3, 2)-polygraph Σ ex from 4.3.2 is decreasing and is therefore confluent. Because every 2-cell rewrites into a semi-normal form and the semi-normal form of a 2-cell is unique, we easily conclude Σ ex is indeed confluent.

THE AFFINE ORIENTED BRAUER CATEGORY

Dotted oriented Brauer diagrams with bubbles

After recalling the definition of the affine oriented Brauer category AOB from [START_REF] Brundan | A basis theorem for the affine oriented Brauer category and its cyclotomic quotients[END_REF], we will present it by a linear (3, 2)-polygraph.

Dotted oriented Brauer diagrams with bubbles. A dotted oriented Brauer diagram with bubbles is a planar diagram such that:

edges are oriented, edges are either bubbles or have a boundary as source and target, each edge is decorated with an arbitrary number of dots not allowed to pass through the crossings.

5.1.2. Equivalence of dotted oriented Brauer diagrams with bubbles. Two dotted oriented Brauer diagrams are equivalent if one can be transformed into the other with isotopies and Reidemeister moves. A description of those moves can be found in [START_REF] Turaev | Quantum Invariants of Knots and 3-Manifolds[END_REF]. An isotopy can move a dot along an edge but cannot make a dot go through a crossing. A dotted oriented Brauer diagram is normally ordered if:

all bubbles are clockwise, all bubbles are in the leftmost side region, all dots are either on a bubble or a segment pointing toward a boundary. Dotted oriented Brauer diagrams with bubbles will be described as 2-cells of a 2-category with vertical and horizontal concatenation respectively standing as 1-composition and 0-composition. 5.1.4. Definition. The affine oriented Brauer category AOB is the linear (2, 2)-category with one 0cell, two generating 1-cells and with 2-cells from a to b given by linear combinations of dotted oriented Brauer diagrams with bubbles with source a and target b subject to the following relations:

invariance by equivalence given in 5.1.2, -= + 5.1.5. An equational presentation of AOB. There is a presentation by generators and relations of the linear (2, 2)-category AOB given in [START_REF] Brundan | A basis theorem for the affine oriented Brauer category and its cyclotomic quotients[END_REF]. The category AOB is the linear (2, 2)-category with only one 0-cell, two generating 1-cells ∧ and ∨ and five generating 2-cells

1 c ⇒ ∧∨, ∨∧ d ⇒ 1, ∧∧ s ⇒ ∧∧, ∧∨ t ⇒ ∨∧, ∧ x ⇒ ∧
respectively represented by: , , , , subject to the following relations:

= = = = = + = =
From this equational presentation of the linear (2, 2)-category AOB, we deduce a linear (3, 2)polygraph presenting AOB. -AOB 1 = {∧, ∨},

-AOB 2 = , , , , ,
-AOB 3 is made of the following 3-cells:

⇛ ⇛ ⇛ ⇛ ⇛ + ⇛ ⇛
This linear (3, 2)-polygraph presents the linear (2, 2)-category AOB. This presentation is not confluent. For example, the following critical branching is not confluent:

⇚ ⇛ +
We will give a confluent presentation of the linear (2, 2)-category AOB in Theorem 5.2.9.

A confluent presentation of AOB

We will give a linear (3, 2)-polygraph AOB presenting the linear (2, 2)-category AOB, with more 2-cells than the linear (3, 2)-polygraph AOB. We will prove that AOB is confluent. The presence of redundant 2cells can be seen as an addition of redundant generators to give more relations and make our presentation confluent.

5.2.1. The linear (3, 2)-polygraph AOB. The linear (3, 2)-polygraph is defined by:

-AOB has the same 0-cells and 1-cells than the linear (3, 2)-polygraph AOB,

-AOB 2 = AOB 2 ∪ , , , , ,
-AOB 3 is made of the following four families of 3-cells:

Isotopy 3-cells i 0 1 ⇛ i 0 2 ⇛ i 0 3 ⇛ i 0 4 ⇛ i 1 1 ⇛ i 1 2 ⇛ i 1 3 ⇛ i 1 4 ⇛ Reidemeister 3-cells r 0 1 ⇛ r 0 2 ⇛ r 0 3 ⇛ r 0 4 ⇛ r 1 1 ⇛ r 1 2 ⇛ r 1 3 ⇛ r 1 4 ⇛ r 1 5 ⇛ r 1 6 ⇛ r 1 7 ⇛ r 1 8 ⇛ r 2 1 ⇛ r 2 2 ⇛ r 2 3 ⇛ r 2 4 ⇛ r 2 5 ⇛ r 2 6 ⇛ r 2 7 ⇛ r 2 8 ⇛ r 3 1 ⇛ r 3 2 ⇛ r 3 3 ⇛ r 3 4 ⇛ r 3 5 ⇛ r 3 6 ⇛ r 3 7 ⇛ r 3 8 ⇛ r 4 1 ⇛ r 4 2 ⇛ r 4 3 ⇛ r 4 4 ⇛ r 5 1 ⇛ r 5 2 ⇛ Ordering 3-cells o 0 1 ⇛ + o 0 2 ⇛ - o 0 3 ⇛ - o 0 4 ⇛ + o 0 5 ⇛ - o 0 6 ⇛ + o 0 7 ⇛ + o 0 8 ⇛ - o 1 0 ⇛ o 1 1 ⇛ - 2 o 1 2 ⇛ 2 -2 + • • • Sliding 3-cells s 0 0 ⇛ s 0 1 ⇛ + 2 s 0 2 ⇛ 2 + 2 + • • • s 1 0 ⇛ s 1 1 ⇛ - 2 s 1 2 ⇛ 2 -2 - • • • 5.2.2. Remark.
The last three families of 3-cells correspond to infinite families of relations which can be calculated by induction. Those relations are noted as in Convention (5). The first induction formula is given in [START_REF] Brundan | A basis theorem for the affine oriented Brauer category and its cyclotomic quotients[END_REF]. If we denote the counterclockwise bubble with n dots n as u n,0 and by expressing the clockwise bubbles with m dots m as u 0,m , we have for any n and m of N:

u n+1,m = u n,m+1 -u n,0 ⋆ 1 u 0,m .
Which can be used to rewrite u n,0 as a linear combination of the family (u j 0,i ) 0 i n,j∈N . The others induction forumulas are:

v n+1,m = v n,m+1 + w n+m + n-1 k=0 w m+n-k ⋆ 1 v k,0 , v ′ n+1,m = v ′ n,m+1 + w ′ n+m - n-1 k=0 v ′ 0,k ⋆ 1 w ′ m+n-k
where v n,0 , v 0,m , v ′ n,0 and v ′ 0,m respectively denote:

n , m , n , m
and where w n and w ′ n respectively denote:

n , n

Let us now expand on the first chapter of [START_REF] Turaev | Quantum Invariants of Knots and 3-Manifolds[END_REF]. This chapter defines first ribbon categories as braided monoidal categories with duals and twist. The twist is a natural transformation θ from the identity functor to itself satisfying:

θ V⊗W = b W,V • (θ V ⊗ θ W ) • b V,W
for each objects V and W, where b denotes the braiding. A ribbon category satisfies the axiom θ * = θ.

An example of ribbon category is the category of ribbon tangles on a set S of colors. This strict monoidal category RIB S is defined by: the objects of RIB S are the words of the free monoid on S × {∨, ∧}, the morphisms of RIB S from a word u to a word v are the oriented tangles of colored ribbons such that the word u is on the upper boundary and the word v is on the lower boundary, two isotopic tangles are equal.

In this category, each object is its own dual. The twist corresponds to transversally twisting a ribbon by 360 degrees. Turaev then gives a presentation by generators and relations of RIB S . The generators are the cups, caps, crossings and twistings of each ribbon colors and directions. The relations are invariance by multiple moves Turaev describes as elementary isotopies and Reidemeister moves.

From the presentation of RIB S by generators and relations, we can present the category RIB of ribbon tangles with only one color by generators and relations. RIB being a monoidal category, we can describe it as a 2-category with only one 0-cell. The linearization of RIB is thus a linear (2, 2)-category with the same 0-cell and 1-cells than RIB. We will call RIB K this linear (2, 2)-category, where K is our fixed field. Let OB be the subcategory of AOB defined by:

-OB 0 = AOB 0 and OB 1 = AOB 1 , -OB 2 is made of the oriented Brauer diagrams with bubbles (without dots)

The linear 2-functor from RIB K to OB sending each ribbon to a string with the same direction is full as noted in [START_REF] Brundan | A basis theorem for the affine oriented Brauer category and its cyclotomic quotients[END_REF]. We derive from this fact a description of elementary isotopies and Reidemeister moves first described in [START_REF] Turaev | Quantum Invariants of Knots and 3-Manifolds[END_REF] for the linear (2, 2)-category AOB 5.2.3. Proposition. The linear (3, 2)-polygraph AOB is a presentation of the linear (2, 2)-category AOB.

Proof. All 3-cells of AOB correspond to a relation verified in the linear (2, 2)-category AOB by Definition 5.1.4. Moreover, the set of 3-cells of type i 0 , r 0 , r 1 , r 2 , r 4 , and r 5 contains all elementary isotopies and Reidemeister moves given in [START_REF] Turaev | Quantum Invariants of Knots and 3-Manifolds[END_REF] (Chapter 1, Section 4), and thus generates the equivalence of dotted oriented Brauer diagram with bubbles. As a consequence, the 3-cells of AOB are sufficient to find any relation verified in AOB.

Then, we define some particular 2-cells of AOB ℓ 2 . 5.2.4. Definition. We call a monomial of AOB quasi-reduced if the only 3-cells we can apply to it are of the form:

i ⇛ i -1 ⇛ ⇛ + 2 ⇛ 2 + 2 + • • • ⇛ ⇛ - 2 ⇛ 2 + 2 + • • • ⇛ ⇛ - 2 ⇛ 2 + 2 + • • • ⇛ ⇛ + 2 ⇛ 2 + 2 + • • •
all critical branchings involving i 1 k for some 1 k 4 and a Reidemeister 3-cell, all critical branchings involving two Reidemeister 3-cells.

Indeed, the above 3-cells correspond to the relations verified by the category OB defined in [START_REF] Brundan | A basis theorem for the affine oriented Brauer category and its cyclotomic quotients[END_REF].

Those relations do not depend on the up or down directions. Those relations are also invariant by axial symmetry. Those facts allow us to withdraw multiple critical pairs from our enumeration. In the same way, any critical branchings involving two isotopy 3-cells can be studied up to axial symmetry.

The interactions between an ordering 3-cell and a Reidemester 3-cell are not invariant by symmetry. But, when a critical branching involving an ordering 3-cell and a Reidemeister 3-cell r k l is confluent, all critical branchings involving an ordering 3-cell and a 3-cell of the form r k * are confluent. This fact allows us to treat multiple cases of critical branching simultaneously.

We now verify each critical branching is confluent. For each critical branching we are treating, we will use notation 4.2.5. Thus, we will give the source of each critical branching and a target attained once a confluence diagram is given for this critical pair.

The sliding 3-cells can be seen as making a bubble going through an identity and creating some additive residues. For each n of N, the only bubbles created by the 3-cells s 0 n and s 1 n have less than n dots. Thus, treating the confluence of the critical branchings involving no sliding relation other than s 0 0 and s 1 0 shows by induction on n all critical branchings involving sliding relations are confluent. This deals with the totality of the critical branchings.

τ = τ = τ = τ = 1 τ = τ = τ = τ = 3 τ = τ = 0
Then, we give the following algorithm taking a monomial m as an entry:

-While m can be rewritten into a 2-cell m ′ such that τ(m ′ ) < τ(m) do:

assign m to m ′ -While m can be rewritten into a 2-cell m ′ without applying a 3-cell of the form:

i j ⇛ i -1 j + 1 i j ⇛ i -1 j + 1 ⇛ ⇛ + 2 ⇛ 2 + 2 + • • • ⇛ ⇛ - 2 ⇛ 2 + 2 + • • • ⇛ ⇛ - 2 ⇛ 2 + 2 + • • • ⇛ ⇛ + 2 ⇛ 2 + 2 + • • • do:
assign m to m ′ This algorithm terminates because Σ is terminating without the sliding 3-cells and the isotopy 3-cells that do not decrease the weight. This results in rewriting any 2-cell into a linear combination of normally ordered Brauer diagrams. For each equivalence class of dotted oriented Brauer diagram with bubbles, exactly one representative of this class can appear in a 2-cell attained by the given algorithm because there is no isotopy or Reidemeister 3-cell to apply anymore. Those are the quasi-reduced monomials.

5.2.8. Lemma. The linear (3, 2)-polygraph AOB is decreasing.

Proof. We define the set P = {P n |n ∈ N} where for each rewriting step α of AOB and each n in N, we have α ∈ P n if and only if the rewriting sequence of minimal length from t 2 (α) to a quasi-reduced 2-cell is of length n. Because of the fact that every 2-cell can be rewritten into a quasi-reduced one 5.2.6, P is a partition of the set of rewriting steps of AOB. We give on this partition the order ≺ such that P n ≺ P m if and only if n < m. This well-founded order respects all the properties of 4.3.1 for the critical branchings of AOB. The decreasingness critical branchings is explicited in the appendix. Then, the order ≺ meets the properties of 4.3.1, ending the proof by 4.3.3.

5.2.9. Theorem. The linear (3, 2)-polygraph AOB is a confluent presentation of AOB.

Proof. The linear (3, 2)-polygraph AOB is locally confluent by lemma 5.2.5. Lemma 5. Proof. We need to give a confluent left-monomial linear (3, 2)-polygraph presenting the linear (2, 2)category AOB such that:

-There is a bijection between the 2-cells of the free linear (2, 2)-category and dotted oriented Brauer diagrams with bubbles.

-A normally ordered dotted oriented Brauer diagram does not rewrite into a linear combination of non-equivalent others.

-Each 2-cell that is not in normal form rewrites into a linear combination of normally ordered dotted oriented Brauer diagrams.

The linear (3, 2)-polygraph AOB from 5.2.9 verifies those properties. To prove that a normally ordered Brauer diagram does not rewrite into a linear combination of non-equivalent others, it is sufficient to show that a quasi-reduced 2-cell does not rewrite into another quasi-reduced 2-cell. The only way to rewrite a quasi-reduced monomial is to apply sliding 3-cells or isototpy relations that do not decrease the weight. So, the only way to rewrite a quasi-reduced monomial into a linear combination of others is to use rewriting paths of the forms:

⇛ ⇛ ⇛ ⇛ • • • ⇛ ⇛ ⇛ + ⇛ • • • ⇛ ⇛ ⇛ - ⇛ • • • ⇛ ⇛ ⇛ - ⇛ • • • ⇛ ⇛ ⇛ + ⇛ • • •
Then, a quasi-reduced 2-cell does not rewrite into a linear combination of others.

⇚ 0 ⇛ 0 ⇚ 0 ⇛ 2 ⇛ 1 ⇛ 0 ⇚ 0 ⇚ 1 ⇚ 2 ⇛ 0 ⇚ 0 ⇚ 1 ⇚ 2 ⇛ 0 ⇛ 3 ⇛ 2 + ⇛ 1 + ⇛ 0 + ⇛ 2 ⇛ 1 + ⇛ 0 + ⇚ 0 ⇛ 2 ⇛ 1 ⇛ 0 ⇚ 0 ⇛ 1 ⇛ 0 ⇚ 0 ⇛ 1 ⇛ 0 ⇚ 0 ⇚ 1 + ⇚ 2 ⇛ 0 ⇚ 0 ⇚ 1 ⇚ 2 ⇛ 2 ⇛ 1 ⇛ 0 ⇚ 0 ⇚ 1 ⇚ 2 ⇛ 2 ⇛ 1 ⇛ 0 ⇚ 0 ⇚ 1 ⇚ 2 ⇚ 3 ⇛ 2 ⇛ 1 ⇛ 0 ⇚ 0 ⇚ 1 ⇚ 2 ⇛ 1 ⇛ 0 ⇛ 3 + ⇛ 2 + + ⇛ 1 + + ⇛ 0 + + ⇛ 3 ⇛ 2 + ⇛ 1 + + ⇛ 0 + + ⇚ 0 ⇚ 1 ⇚ 2 ⇛ 2 ⇛ 1 ⇛ 0 ⇚ 0 ⇚ 1 ⇚ 2 ⇛ 2 ⇛ 1 ⇛ 0 ⇚ 0 ⇚ 1 ⇛ 1 ⇛ 0 ⇚ 0 ⇚ 1 ⇚ 2 ⇚ 3 ⇛ 0 ⇚ 0 ⇚ 1 ⇛ 2 ⇛ 1 ⇛ 0 ⇚ 0 ⇚ 1 ⇛ 1 ⇛ 0 ⇚ 0 ⇚ 1 ⇚ 2 ⇛ 0 + ⇚ 0 + ⇚ 1 ⇛ 1 ⇛ 0 + ⇚ 0 ⇚ 1 ⇚ 2 ⇛ 2 ⇛ 1 ⇛ 0 ⇚ 0 ⇚ 1 ⇚ 2 ⇛ 2 ⇛ 1 ⇛ 0 ⇚ 0 ⇚ 1 ⇛ 1 ⇛ 0 ⇛ 1 ⇛ 0 ⇛ 5 + ⇛ 4 + ⇛ 3 - + ⇛ 2 - + ⇛ 1 ⇛ 0 ⇚ 0 ⇚ 1 ⇚ 2 ⇛ 2 ⇛ 1 ⇛ 0 ⇚ 0 ⇚ 1 + ⇚ 2 ⇛ 1 ⇛ 0 ⇚ 0 ⇚ 1 ⇚ 2 ⇛ 0 ⇚ 0 ⇚ 1 + ⇚ 2 + ⇚ 3 + ⇚ 4 ⇛ 0 ⇚ 0 ⇚ 1 ⇚ 2 ⇛ 0 ⇚ 0 + ⇚ 1 ⇛ 1 - ⇛ 0 ⇚ 0 ⇛ 2 ⇛ 1 ⇛ 0 ⇚ 0 ⇚ 1 ⇛ 1 ⇛ 0

  for each a and b in C 0 , a linear (n, p)-category C(a, b), for each a in C 0 , an identity morphism i a from the terminal n-category I n to C(a, a), for each a, b and c in C 0 , a bilinear composition morphism ⋆ a,b,c from C(a, b)×C(b, c) to C(a, c).

β

  composition α ⋆ 0 β will be represented by horizontal concatenation .composition α ⋆ 1 β will be represented by vertical concatenation .If a 2-cell α verifies s 1 (α) = t 1 (α) = a, we use for any k ∈ N the following notations:

  for each 1 i n we have r i ∈ K i . We extend finally | • • • | to the set of branchings of Σ made of finite rewriting sequences by defining |(α, β)| = |α| + |β| for every finite rewriting sequences α and β.

  5.1.3. Example. Here is an example of dotted oriented Brauer diagram: This diagram is not normally ordered. The following one is normally ordered: Those diagrams are not equivalent.

  5.1.6. The linear (3, 2)-polygraph AOB. Let us define the linear (3, 2)-polygraph AOB. It is the (3, 2)polygraph with only one 0-cell and:

5. 2

 2 .6. Lemma. Each 2-cell of the linear (2, 2)-polygraph AOB ℓ 2 can be rewritten into a quasi-reduced 2-cell. Before proving this claim, we introduce the notion of weight function on a linear (2, 2)-category. 5.2.7. Definition. Let C be a linear (2, 2)-category. A weight function on C is a function τ from C 2 to N such that: for each 0-composable monomials a and b we have τ(a ⋆ 0 b) = τ(a) + τ(b), for each 1-composable monomials a and b we have τ(a ⋆ 1 b) = τ(a) + τ(b), for each 2-cell x, we have τ(x) = max{τ(a)|a appears in the monomial decomposition of x}. Proof. To prove that each 2-cell of AOB ℓ 2 rewrites into a normally dotted oriented Brauer diagram, we give first a weight function τ on AOB ℓ 2 defined by:

  2.8 allows us to use 4.3.3 and conclude the proof. This theorem implies the following result from [BCNR14]: 5.2.10. Corollary. Let a and b be two 1-cells of the linear (2, 2)-category AOB. Then, the vector space AOB 2 (a, b) has basis given by equivalence classes of normally ordered dotted oriented Brauer diagrams with bubbles with source a and target b.

  if all its branchings of source u are confluent. A linear (3, 2)-polygraph is confluent if all its branchings are confluent. A linear (3, 2)-polygraph is locally confluent at a 2-cell u ∈ Σ ℓ 2 if all its local branchings of source u are confluent. A linear (3, 2)-polygraph is locally confluent if all its local branchings are confluent. The linear (3, 2)-polygraph Σ is terminating if it has no infinite rewriting sequence. The linear (3, 2)-polygraph Σ is convergent if it is terminating and confluent. 4.2.2. Proposition (Noetherian induction principle). Let Σ be a terminating left-monomial linear (3, 2)polygraph. Let P be a property on the 2-cells of Σ ℓ such that for any u ∈ Σ ℓ 2

	α	u ′
	u	v
	β	u ′′
	into a branching made of rewriting sequences with the same 2-target. A linear (3, 2)-polygraph is conflu-
	ent at a 2-cell u ∈ Σ ℓ 2

pair of rewriting steps of Σ with the same 2-source.

A branching (α, β) is confluent if it can be completed

  We give a partition {P n |n ∈ N} of the set of rewriting steps of Σ ex such that, for any rewriting step α, we have α ∈ P n if the shortest rewriting sequence from t

	4.3.2. Example. Let Σ ex be the linear (3, 2)-polygraph with only one 0-cell, one 1-cell a, two 2-cells
	represented by:
		,
	and the following 3-cell:
		⇛
	A 2-cell is said in semi-normal form if it cannot be rewritten by using a rewriting step of one of the
	following forms:
	⇛	,	⇛

2 (α) to a semi-normal form is of length n. This is a partition of the set of rewriting steps of Σ ex because every 2-cell rewrites into a semi-normal form. We define on {P n |n ∈ N} the order ≺ by P n ≺ P m if n < m. With this well-ordered partition given, Σ ex is decreasing. This translates the fact any 2-cell has a unique semi-normal form.

ACKNOWLEDGMENTS

The author would like to thank Labex Milyon (ANR-10-LABX-0070). This work has been supported by the project Cathre, ANR-13BS02-0005-02.

We call a 2-cell of AOB ℓ 2 quasi-reduced if all monomials in its monomial decomposition are quasireduced. 5.2.5. Lemma. The linear (3, 2)-polygraph AOB is locally confluent.

Proof. We will prove all critical branchings of AOB are confluent, which will give local confluence of AOB by 4.2.13 because its strict canonical rewrite order is well-founded.

We enumerate first the sources of the critical branchings which do not involve dotted bubbles, starting with the overlapping of the isotopy 3-cells and continuing in the order in which the relations are given. The first given 3-cell of AOB is i 0 1 . We search for all the cells having a source overlapping with the source of i 1 0 . Those 3-cells are i 0 3 , i 1 2 , r 2 1 and a family of sliding 3-cells given in the end denoted by s * . We continue our enumeration by searching for all the overlaps of the source of i 0 2 and so on. The final enumeration is:

3 ), (i 0 2 , i 0 4 ), (i 0 2 , i 1 3 ), (i 0 2 , r 2 2 ), (i 0 2 , r 2 4 ), (i 0 3 , i 1 4 ), (i 0 3 , r 2 5 ), (i 0 3 , r 2 7 ), (i 0 4 , i 1 1 ), (i 0 4 , r 2 6 ), (i 0 4 , r 2 8 ), (i 1 1 , r 2 2 ), (i 1 1 , r 2 4 ), (i 1 3 , r 2 6 ), (i 1 3 , r 2 8 ), (r 0 1 , r 0 1 ), (r 0 1 , r 1 1 ), (r 0 1 , r 1 2 ), (r 0 1 , r 1 4 ), (r 0 1 , r 2 1 ), (r 0 1 , r 3 1 ), (r 0 2 , r 0 2 ), (r 0 2 , r 1 2 ), (r 0 2 , r 1 4 ), (r 0 2 , r 1 8 ), (r 0 2 , r 2 2 ), (r 0 2 , r 2 7 ), (r 0 2 , r 3 3 ), (r 0 2 , r 3 6 ), (r 0 2 , r 4 2 ), (r 0 2 , r 4 3 ), (r 0 2 , o 0 6 ), (r 0 2 , o 0 7 ), (r 0 3 , r 0 3 ), (r 0 3 , r 1 3 ), (r 0 3 , r 1 6 ), (r 0 3 , r 1 7 ), (r 0 3 , r 2 3 ), (r 0 3 , r 2 6 ), (r 0 3 , r 3 2 ), (r 0 3 , r 3 7 ), (r 0 3 , r 4 1 ), (r 0 3 , r 4 4 ), (r 0 3 , o 0 5 ), (r 0 3 , o 0 8 ), (r 0 4 , r 0 4 ), (r 0 4 , r 1 5 ), (r 0 4 , r 1 6 ), (r 0 4 , r 1 7 ), (r 0 4 , r 2 4 ), (r 0 4 , r 2 5 ), (r 0 4 , r 3 4 ), (r 0 4 , r 3 5 ), (r 0 4 , o 0 4 ), (r 0 4 , o 0 7 ), (r

2 ), (r 1 4 , o 0 1 ), (r 1 4 , o 0 2 ), (r 1 4 , o 0 6 ), (r 1 4 , o 0 8 ), (r 1 5 , r 1 5 ), (r 1 5 , o 0 3 ), (r 1 5 , o 0 4 ), (r 1 6 , r 1 7 ), (r 1 6 , r 2 3 ), (r 1 6 , r 2 5 ), (r 1 6 , r 3 5 ), (r 1 6 , r 4 1 ), (r 1 6 , o 0 5 ), (r 1 6 , o 0 7 ), (r 1 7 , r 2 4 ), (r 1 7 , r 2 6 ), (r 1 7 , r 3 4 ), (r 1 7 , r 4 4 ), (r 1 7 , o 0 4 ), (r 1 7 , o 0 5 ), (r 1 7 , o 0 6 ), (r 1 8 , r 1 8 ), (r 1 8 , r 3 3 ), (r 1 8 , r 3 6 ), (r 1 8 , r 4 2 ), (r 1 8 , r 4 3 ), (r 1 8 , o 0 3 ), (r 1 8 , o 0 5 ), (r 1 8 , o 0 8 ), (r 2 1 , r 2 8 ), (r 2 1 , r 3 7 ), (r 2 1 , r 3 8 ), (r 2 1 , r 5 1 ), (r 2 1 , o 0 1 ), (r 2 1 , o 0 2 ), (r 2 2 , r 3 4 ), (r 2 2 , r 3 8 ), (r 2 2 , r 4 3 ), (r 2 2 , o 0 5 ), (r 2 3 , r 3 1 ), (r 2 3 , r 3 6 ), (r 2 3 , r 4 4 ), (r 2 3 , o 0 6 ), (r 2 4 , r 2 5 ), (r 2 4 , r 3 3 ), (r 2 4 , r 3 5 ), (r 2 4 , r 5 2 ), (r 2 4 , o 0 4 ), (r 2 5 , r 3 4 ), (r 2 5 , r 3 6 ), (r 2 5 , r 5 2 ), (r 2 5 , o 0 3 ), (r 2 5 , o 0 4 ), (r 2 6 , r 3 8 ), (r 2 6 , r 4 1 ), (r 2 6 , o 0 7 ), (r 2 7 , r 3 3 ), (r 2 7 , r 3 5 ), (r 2 7 , r 4 2 ), (r 2 7 , o 0 6 ), (r 2 7 , o 0 8 ), (r 2 8 , r 3 2 ), (r 2 8 , r 5 1 ), (r 2 8 , o 0 2 ), (r 3 1 , r 3 8 ), (r 3 1 , o 0 1 ), (r 3 1 , o 0 2 ), (r 3 2 , r 4 4 ), (r 3 2 , o 0 5 ), (r 3 2 , o 0 6 ), (r 3 3 , r 4 3 ), (r 3 3 , o 0 3 ), (r 3 3 , o 0 5 ), (r 3 4 , r 3 5 ), (r 3 4 , o 0 5 ), (r 3 4 , o 0 7 ), (r 3 5 , o 0 3 ), (r 3 5 , o 0 4 ), (r 3 6 , r 4 2 ), (r 3 6 , r 4 2 ), (r 3 6 , o 0 7 ), (r 3 6 , o 0 8 ), (r 3 7 , r 4 1 ), (r 3 7 , o 0 1 ), (r 3 7 , o 0 7 ), (r 3 8 , o 0 5 ), (r 3 8 , o 0 7 ), (r 4 1 , r 4 4 ), (r 4 1 , o 0 6 ), (r 4 2 , r 4 3 ), (r 4 2 , o 0 5 ), (r 4 3 , o 0 8 ), (r 4 4 , o 0 7 ), (r 5 1 , o 0 1 ), (r 5 2 , o 0 3 ), (i 0 1 , s * ), (i 0 2 , s * ), (i 0 3 , s * ), (i 0 4 , s * ), (r 0 1 , s * ), (r 0 2 , s * ), (r 0 3 , s * ), (r 0 4 , s * ), (r 1 1 , s * ), (r 1 2 , s * ), (r 1 3 , s * ), (r 1 4 , s * ), (r 1 5 , s * ), (r 1 6 , s * ), (r 1 7 , s * ), (r 1 8 , s * ), (r 2 1 , s * ), (r 2 2 , s * ), (r 2 3 , s * ), (r 2 4 , s * ), (r 2 5 , s * ), (r 2 6 , s * ), (r 2 7 , s * ), (r 2 8 , s * ), (r 3 1 , s * ), (r 3 2 , s * ), (r 3 3 , s * ), (r 3 4 , s * ), (r 3 5 , s * ), (r 3 6 , s * ), (r 3 7 , s * ), (r 3 8 , s * ), (r 4 1 , s * ), (r 4 2 , s * ), (r 4 3 , s * ), (r 4 4 , s * ), (r 5 1 , s * ), (r 5 2 , s * ), (o 1 * , s * ), (s * , s * ). By doing this, we remark we can eliminate multiple critical branchings, similar to others. First, we can ignore the directions of the up and down for each of the following interactions: all critical branchings involving i 1 k and i 1 l for some 1 k 4 and 1 l 4,

APPENDIX

In this appendix, we give all confluence diagrams for the critical branchings of AOB verifying the axioms of decreasingness. For each n in N, with respect to the partition defined in the proof of lemma 5.2.8, we index the rewriting steps of P n by n.


Frank Vega
email: vega.frank@gmail.com

A Simple Proof of P versus NP

Keywords: P, NP, coNP, maximum, succinct

P versus NP is one of the most important and unsolved problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? Another major complexity class is coNP. Whether NP is equal to coNP is another fundamental question that it is as important as it is unresolved. We shall show there is a problem in coNP that is not in P. Since P = NP implies P = coNP, then we prove that P is not equal to NP.

Introduction

P versus NP is a major unsolved problem in computer science. This problem was introduced in 1971 by Stephen Cook [START_REF] Cook | The complexity of theorem-proving procedures[END_REF]. It is considered by many to be the most important open problem in the field [START_REF] Fortnow | The Status of the P versus NP Problem[END_REF]. It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US$1,000,000 prize for the first correct solution [START_REF] Fortnow | The Status of the P versus NP Problem[END_REF].

In 1936, Turing developed his theoretical computational model [START_REF] Turing | On Computable Numbers, with an Application to the Entscheidungsproblem[END_REF]. The deterministic and nondeterministic Turing machine have become in some of the most important definitions related to this theoretical model for computation. A deterministic Turing machine has only one next action for each step defined in its program or transition function [START_REF] Papadimitriou | Computational complexity[END_REF]. A nondeterministic Turing machine could contain more than one action defined for each step of its program, where this one is no longer a function, but a relation [START_REF] Papadimitriou | Computational complexity[END_REF].

Another huge advance in the last century was the definition of a complexity class. A language over an alphabet is any set of strings made up of symbols from that alphabet [START_REF] Cormen | Introduction to Algorithms[END_REF]. A complexity class is a set of problems, which are represented as a language, grouped by measures such as the running time, memory, etc [START_REF] Cormen | Introduction to Algorithms[END_REF].

In computational complexity theory, the class P contains those languages that can be decided in polynomial-time by a deterministic Turing machine [START_REF] Goldreich | Np-Completeness[END_REF]. The class NP consists in those languages that can be decided in polynomial-time by a nondeterministic Turing machine [START_REF] Goldreich | Np-Completeness[END_REF].

The biggest open question in theoretical computer science concerns the relationship between these two classes:

Is P equal to NP?

In a 2002 poll of 100 researchers, 61 believed the answer to be no, 9 believed the answer is yes, and 22 were unsure; 8 believed the question may be independent of the currently accepted axioms and so impossible to prove or disprove [START_REF] Gasarch | The P=?NP poll[END_REF].

If NP is the class of problems that have succinct certificates, then the complexity class coNP contains those problems that have succinct disqualifications [START_REF] Papadimitriou | Computational complexity[END_REF]. That is, a "no" instance of a problem in coNP possesses a short proof of its being a "no" instance [START_REF] Papadimitriou | Computational complexity[END_REF]. We discuss one problem that is not in P. At the same time, we show this language is also in coNP. But, we already know if P = NP, then P = NP = coNP [START_REF] Papadimitriou | Computational complexity[END_REF]. In conclusion, we demonstrate the existence of a coNP language that is not in P, and therefore, P NP [START_REF] Papadimitriou | Computational complexity[END_REF].

Results

Definition 2.1. Given a set S of n (distinct) positive integers and an integer x, MAXIMUM is the problem of deciding whether x is the maximum number in S .

How many comparisons are necessary to determine when some integer is the maximum in a set of n elements? We can easily obtain a upper bound of n comparisons: examine each element of the set in turn and keep track of the largest element seen so far, and finally, compare the final result with x [START_REF] Cormen | Introduction to Algorithms[END_REF]. Is this the best we can do? Yes, since we can obtain a lower bound of n -1 comparisons for the problem of determining the maximum in a set of integers [START_REF] Cormen | Introduction to Algorithms[END_REF]. And one final comparison for the verification of whether this maximum is equal to x. Hence, n comparisons are necessary to determine whether an element x is the maximum in S . This naive algorithm for MAXIMUM is optimal with respect to the number of comparisons performed [START_REF] Cormen | Introduction to Algorithms[END_REF].

On the other hand, a Boolean circuit may be viewed as the computation on the binary input sequence proceeds by a sequence of Boolean operations (called gates) from the set {∧, ∨, ¬} (logical AND, OR and NEGATION) to compute the output(s). While an algorithm can handle inputs of any length, a circuit can only handle one input length (the number of input gates it has). The efficiency of a circuit is measured by its size. Definition 2.2. A succinct representation of a set of (distinct) b-bits positive integers is a Boolean circuit C with b input gates [START_REF] Papadimitriou | Computational complexity[END_REF]. The set represented by C, denoted S C , is defined as follows: Every possible integer of S C should be between 0 and 2 b -1. And j is an element of S C if and only if C accepts the binary representations of the b-bits integer j as input. The problem SUCCINCT MAXIMUM is now this: Given the succinct representation C of a set S C and a b-bits integer x, where C is a Boolean circuit with b input gates, is x the maximum in S C ? Let's state our principal Theorem. Theorem 2.3. SUCCINCT MAXIMUM P.

Proof. As we mentioned before, we should need n comparisons to know whether x is the maximum in a set of n (distinct) positive integers when the set S is arbitrary. And this number of comparisons will be optimal [START_REF] Cormen | Introduction to Algorithms[END_REF]. This would mean we cannot always accept every instance This previous language is very similar to SUCCINCT MAXIMUM, but the set S C might not contain the b-bits integer x. QUESTION: Is there some element y of S C such that x < y?

Every "yes" instance C; x of coSUPREME could be verified in polynomial-time with a given certificate. Indeed, we can prove in polynomial-time whether x is an integer of a bit-length equal to b, where b is the number of input gates in C. Moreover, given a b-bits integer y, we can check whether C accepts the binary representation of y (which means that y is an element of S C ) and x < y in polynomial-time, since the comparison of two b-bits integers can be done in polynomial-time and the efficiency of the acceptance of y by C only depends in the size of the circuit. Since the bit-length of the certificate y is more short than the size of C; x , then the language coSUPREME will be in NP. Consequently, SUPREME would be in coNP.

We say that a language L 1 is polynomial-time reducible to a language L 2 if there exists a polynomial-time computable function f : {0, 1} * → {0, 1} * such that for all x ∈ {0, 1} * ,

x ∈ L 1 if and only if f (x) ∈ L 2 .
Theorem 2.7. SUCCINCT MAXIMUM ∈ coNP.

Proof. Given an instance C; x of SUCCINCT MAXIMUM and over the assumption that x is in S C , we can state that C; x would belong to SUCCINCT MAXIMUM if and only if C; x is in SUPREME. In addition, we could decide whether x is in S C in polynomial-time just verifying whether C accepts the binary representation of x, because the efficiency of the acceptance of x by C will only depend in the size of the circuit. Hence, it will exist an identity polynomial-time reduction from SUCCINCT MAXIMUM to SUPREME, such that this will first check whether x is in S C . We say that a complexity class G is closed under reductions if, whenever L 1 is reducible to L 2 and L 2 ∈ G, then also L 1 ∈ G [START_REF] Papadimitriou | Computational complexity[END_REF]. Since coNP is closed under reductions, then we obtain that SUCCINCT MAXIMUM is in coNP [START_REF] Papadimitriou | Computational complexity[END_REF]. Theorem 2.8. P NP.

Proof. The existence of a problem in coNP and not in P is sufficient to show that P NP, because if P would be equal to NP, then P = coNP [START_REF] Papadimitriou | Computational complexity[END_REF].

Conclusions

This proof explains why after decades of studying the NP problems no one has been able to find a polynomial-time algorithm for any of more than 300 important known NP-complete problems [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness, 1st Edition[END_REF]. Indeed, it shows in a formal way that many currently mathematically problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems.

  C; x of SUCCINCT MAXIMUM in polynomial-time, because we must use at least n = |S C | comparisons for infinite amount of cases, where |S C | is the cardinality of S C . However, n could be exponentially more large than the size of C; x . Now, let's define a new problem. Definition 2.4. Problem SUPREME: INSTANCE: The succinct representation C of a set S C and a b-bits integer x, where C is a Boolean circuit with b input gates.QUESTION: Does every element y of S C comply with x ≥ y?

Lemma 2 . 5 .Definition 2 . 6 .

 2526 SUPREME ∈ coNP. Proof. Let's state the complement language of SUPREME. Problem coSUPREME: INSTANCE: The instances of SUPREME.

Although this demonstration removes the practical computational benefits of a proof that P = NP, it would represent a very significant advance in computational complexity theory and provide guidance for future research. In addition, it proves that could be safe most of the existing cryptosystems such as the public-key cryptography. On the other hand, we will not be able to find a formal proof for every theorem which has a proof of a reasonable length by a feasible algorithm.