Ï C Lo

Foissy

Xiao-Song Peng
email: pengxiaosong3@163.com

TYPED ANGULARLY DECORATED PLANAR ROOTED TREES AND GENERALIZED ROTA-BAXTER ALGEBRAS

Keywords: Mathematics Subject Classification. 17B38, 05C05, 16S10, 08B20 Generalized Rota-Baxter algebra, diassociative semigroups, planar rooted trees

We introduce a generalization of parametrized Rota-Baxter algebras, named Ω-Rota-Baxter algebra, which includes family and matching Rota-Baxter algebras. We study the structure needed on the set Ω of parameters in order to obtain that free Ω-Rota-Baxter algebras are described in terms of typed and angularly decorated planar rooted trees: we obtain the notion of λ-extended diassociative semigroup, which includes sets (for matching Rota-Baxter algebras) and semigroups (for family Rota-Baxter algebras), and many other examples. We also describe free commutative Ω-Rota-Baxter algebras generated by a commutative algebra A in terms of typed words.

1. Introduction 2. Ω-Rota-Baxter algebras 2.1. Definitions 2.2. Ω-Rota-Baxter algebras on typed angularly decorated planar rooted trees 2.3. Commutative Ω-Rota-Baxter algebras on typed words 3. More results on λ-ETS and ETS 3.1. Description in terms of linear and bilinear maps 3.2. A description of all λ-ETS of cardinality two 3.3. A description of all ETS of cardinality two References where λ is a scalar called the weight of the Rota-Baxter operator P. Firstly introduced by Baxter [START_REF] Baxter | An analytic problem whose solution follows from a simple algebraic identity[END_REF] in a context of probability theory and popularized by Rota [8,9,10], they now appear in numerous fields of mathematics and physics, see for example [3] for examples and more details.

The first appearance of family Rota-Baxter algebras seems to be in [2], in the context of Renormalization in Quantum Field Theories. This terminology, due to Li Guo [START_REF] Guo | Operated semigroups, Motzkin paths and rooted trees[END_REF] refers to an associative algebra A with a family of linear endomorphims P α : A -→ A indexed by the elements of a semigroup (Ω, * ), such that for any a, b ∈ A, for any α, β ∈ Ω, This notion of matching Rota-Baxter algebra is introduced in [11]. This time, the Rota-Baxter operators are indexed by the elements of a set Ω with no structure, and the weights are given by a family of scalars (λ α ) α∈Ω . For any a, b ∈ A, for any α, β ∈ Ω, P α (a)P β (b) = P β (P α (a)b) + P α (aP β (b)) + λ β P α (ab).

These notions have been extended to other types of algebras (Lie, pre-Lie, dendriform. . .), see for example [11,12,[START_REF] Zhang | Free Rota-Baxter family algebras and (tri)dendriform family algebras[END_REF][START_REF] Zhang | Free (tri)dendriform family algebras[END_REF].

Our aim here is a generalization of both family and matching Rota-Baxter algebras, in the spirit of what is made in [5] for dendriform algebras. We here consider that the set of parameters Ω is given five operations ←, →, , and •, and a family of scalars λ = (λ α,β ) α,β∈Ω . An Ω-Rota-Baxter algebra of weight λ is an associative algebra A with a family of linear endomorphisms indexed by Ω such that for any a, b ∈ A, for any α, β ∈ Ω, P α (a)P β (b) = P α→β (P α β (a)b) + P α←β (aP α β (b)) + λ α,β P α•β (ab).

Taking

α → β = α ← β = α • β = α * β, α β = α, α β = β,
and λ α,β being constant, we recover in this way family Rota-Baxter algebras. Taking

α → β = β, α ← β = α, α • β = α, α β = α, α β = β,
and λ α,β depending only on β, w recover matching Rota-Baxter algebras.

For any set Ω with five operations and any family of scalars λ, we define an operad and a category of Ω-Rota-Baxter algebras (Definition 2.8). This is far too general, and we impose the extra constraint that the combinatorics of Rota-Baxter algebras is somehow preserved. To be more precise, as free Rota-Baxter algebras are based on planar rooted trees [START_REF] Zhang | Free (tri)dendriform family algebras[END_REF], we impose that free Ω-Rota-Baxter algebras own a description in terms of angularly decorated (by the set of generators) and typed (by Ω) planar rooted trees, that is to say in terms of planar rooted trees with angles decorated by the generators and internal edges decorated by elements of Ω, with an inductive description of the associative product and the Rota-Baxter operators being given by the grafting on a new root, the created internal edge begin of the required type. We show in Theorem 2.14 that this imposes strong constraints on Ω: we obtain that this combinatorial description holds if, and only if Ω is a λ-ETS, as defined in Definition 2.3. In particular, (Ω, ←, →) has to be a diassocative semigroup: for any α, β, γ ∈ Ω,

(α ← β) ← γ = α ← (β ← γ) = α ← (β → γ), (α → β) ← γ = α → (β ← γ), (α → β) → γ = (α ← β) → γ = α → (β → γ).
This notion firstly appeared in Loday's work [START_REF] Loday | Dialgebras, Dialgebras and related operads[END_REF] under the name of (associative) dimonoid; the free dimonoid is also constructed in Loday's article. Moreover, (Ω, ←, →, , ) is an extended semigroup (see Definition 2.2 below), a notion used in [5] In the case of weight 0, we obtain the generalization of the result [3] establishing that any Rota-Baxter of weight 0 is a dendriform algebra, see Proposition 2.11. Moreover, generalizing the construction of free commutative Rota-Baxter algebras, we obtain that free commutative Ω-Rota-Baxter algebras can be described in terms of Ω-typed words (Proposition 2.18 and Theorem 2.20). This paper is organised as follows. The first section introduces the definitions of EDS, λ-ETS, ETS and of Ω-Rota-Baxter algebras. The main result on free Rota-Baxter algebras and λ-ETS is then proved (Theorem 2.14), with a description of free Ω-Rota-Baxter algebras in terms of trees. The last subsection deals with commutative Ω-Rota-Baxter algebras and their description in terms of typed words (Theorem 2.20). The second section gives more examples of λ-ETS and ETS, and in particular a classification of these objects of cardinality 2.

Notation. Throughout this paper, k is a unitary commutative ring which will be the base ring of all modules, algebras, as well as linear maps.

2. Ω-Rota-Baxter algebras 2.1. Definitions. We first recall the definition of diassociative semigroups and extended diassociative semigroups of [5], where these objects were used for parametrized versions of dendriform algebras.

Definition 2.1. [5, 7] A diassociative semigroup is a family (Ω, ←, →), where Ω is a set and ←, →:

Ω × Ω → Ω are maps such that (α ← β) ← γ = α ← (β ← γ) = α ← (β → γ), (α → β) ← γ = α → (β ← γ), (α → β) → γ = (α ← β) → γ = α → (β → γ), for all α, β, γ ∈ Ω.
Definition 2.2. [5, Definition 2] An extended diassociative semigroup (abbr. EDS) is a family (Ω, ←, →, , ), where Ω is a set and ←, →, , :

Ω × Ω → Ω such that (Ω, ←, →) is a diassociative semigroup and α (β ← γ) = α β, (1) (α → β) γ = β γ, (2) (α β) ← ((α ← β) γ) = α (β ← γ), (3)
(α β) ((α ← β) γ) = β γ, (4) (α β) → ((α ← β) γ) = α (β → γ), (5) (α β) ((α ← β) γ) = β γ, (6) (α (β → γ)) ← (β γ) = (α ← β) γ, (7) (α (β → γ)) (β γ) = α β, (8) (α (β → γ)) → (β γ) = (α → β) γ, (9) (α (β → γ)) (β γ) = α β, (10)
for all α, β, γ ∈ Ω.

We shall use here the notion of λ-extended triassociative semigroup, where a family of scalars plays the role of weights.

Definition 2.3. An λ-extended triasssociative semigroup (abbr. λ-ETS) is a family (Ω, ←, → , , , •, * , λ), where (Ω, ←, →, , ) is an EDS and λ = (λ α,β ) α,β∈Ω is a family of elements in k indexed by Ω 2 such that

λ α→β,γ = λ β,γ (11) λ α β,(α←β) γ = λ β,γ (12) λ α←β,γ = λ α,β→γ (13) λ α (β→γ),β γ = λ α,β (14) λ α,β = λ α,β←γ (15) λ α,β λ α•β,γ = λ β,γ λ α,β•γ (16)
and, for all α, β, γ ∈ Ω:

(a) If λ α→β,γ = λ β,γ 0, then

α β = α (β • γ), (17) (α → β) • γ = α → (β • γ). (18) (b) If λ α β,(α←β) γ = λ β,γ 0, then (α β) • ((α ← β) γ) = α (β • γ), (19) (α ← β) ← γ = α ← (β • γ). (20) (c) If λ α (β→γ),β γ = λ α,β 0, then α → (β → γ) = (α • β) → γ, (21) (α (β → γ)) • (β γ) = (α • β) γ. ( 22
) (d) If λ α←β,γ = λ α,β→γ 0, then (α ← β) • γ = α • (β → γ), (23) α β = β γ. ( 24
) (e) If λ α,β = λ α,β←γ 0, then (α • β) γ = β γ, (25) (α • β) ← γ = α • (β ← γ). (26) (f) If λ α,β λ α•β,γ = λ β,γ λ α,β•γ 0, then (α • β) • γ = α • (β • γ). (27) Example 2.4.
(a) Let (Ω, ←, →, , ) be an EDS. If we put λ α,β = 0 for any α, β ∈ Ω, then for any product •, (Ω, ←, →, , ,

•, λ) is a λ-ETS. (b) If for any α, β ∈ Ω, α ← β = β → α = β α = α β = α, then (Ω, ←, →, , , •, λ) is a λ-ETS if,
and only if, the following map defines an associative product:

ψ • : kΩ ⊗ kΩ -→ kΩ α ⊗ β -→ λ α,β α • β. Indeed, for any α, β, γ ∈ Ω, ψ • • (ψ • ⊗ id)(α ⊗ β ⊗ γ) = λ α,β λ α•β,γ (α • β) • γ, ψ • • (id ⊗ ψ • )(α ⊗ β ⊗ γ) = λ β,γ λ α,β•γ α • (β • γ),
which gives the missing condition (27). (c) Let (Ω, ) be a semigroup and λ ∈ k. We put, for any α, β ∈ Ω:

α ← β = α β, α β = β, α → β = α β, α β = α, λ α,β = λ, α • β = α β.
Then (Ω, ←, →, , , •, λ) is a λ-ETS. (d) Let (Ω, ) be an abelian group and let λ ∈ k. For any α, β ∈ Ω, we put:

α ← β = α, α → β, β, α β = α β -1 , α β = α -1 β, λ α,β = λ, α • β = α.
Then (Ω, ←, →, , , •, λ) is a λ-ETS. (e) Let Ω = (Ω, ←, →, , , •, λ) be a λ-ETS. For any α, β ∈ Ω, we put

α ← op β = β → α, α op α = β α, α → op β = β ← α, α op α = β α, α • op β = β • α, λ op α,β = λ β,α . Then (Ω, ← op , → op , op , op , • op , λ op
) is also a λ-ETS, called the opposite of Ω and denoted by Ω op . We shall say that Ω is commutative if it is equal to its opposite. Definition 2.5. A extended triasssociative semigroup (abbr. ETS) is a family (Ω, ←, →, , , •, * ), where (Ω, ←, →, , ) is an EDS and

(α → β) * γ = β * γ, (28) α β = α (β • γ), (17) (α → β) • γ = α → (β • γ), (18) (α β) * ((α ← β) γ) = β * γ, ( 29
) (α β) • ((α ← β) γ) = α (β • γ), ( 19
) (α ← β) ← γ = α ← (β • γ), (20) (α (β → γ)) * (β γ) = α * β, (30) α → (β → γ) = (α • β) → γ, (21) (α (β → γ)) • (β γ) = (α • β) γ, ( 22
) (α ← β) * γ = α * (β → γ), (31) (α ← β) • γ = α • (β → γ), (23) α β = β γ, (24) α * β = α * (β ← γ), (32) (α • β) γ = β γ, (25) (α • β) ← γ = α • (β ← γ), (26) α * β = α * (β • γ), (33) (α • β) * γ = β * γ, (34) (α • β) • γ = α • (β • γ). ( 27
)
Example 2.6.

(a) Let (Ω, * , •) be a set with two products such that for any α, β, γ ∈ Ω:

α * β = α * (β • γ), (35) (α • β) * γ = β * γ, (36) (α • β) • γ = α • (β • γ). (37)
We put, for any α, β ∈ Ω:

α ← β = α, α β = β, α → β = α, α β = β.
Then (Ω, ←, →, , , •, * ) is an ETS. (b) Let (Ω, ←, →, , , •, * ) be an ETS. For any α, β ∈ Ω, we put

α ← op β = β → α, α op α = β α, α → op β = β ← α, α op α = β α, α * op β = β * α, α • op β = β • α.
Then (Ω, ← op , → op , op , op , * op , • op ) is also an ETS, called the opposite of Ω. We shall say that Ω is commutative if it is equal to its opposite.

Actually, each ETS induces a λ-ETS, as the following result indicates:

Proposition 2.7. Let (Ω, ←, →, , , •, * ) be an ETS and let (µ α ) α∈Ω be a family of scalars. For any α, β ∈ Ω, we put:

λ α,β = µ α * β .
Then (Ω, ←, →, , , •, λ) is a λ-ETS.

Proof. Conditions (a)-(f) of Definition 2.3 are obviously satisfied by (17)-( 27). ( 11) is (28), ( 12) is ( 29), ( 13) is (31), ( 14) is (30), ( 15) is (32), and (16) comes from (33) and (34).

We now propose the concept of Ω-Rota-Baxter algebras as follows:

Definition 2.8. Let Ω be a set with five products ←, →, , , • and λ = (λ α,β ) α,β∈Ω be a family of elements in k indexed by Ω 2 . An Ω-Rota-Baxter algebra of weight λ is a family (A, (P ω ) ω∈Ω ) where A is an associative algebra and P ω : A ⊗ A → A is a linear map for each ω ∈ Ω, such that Taking all elements of λ equal to 0, we get the concept of Ω-Rota-Baxter algebras of weight 0:

Definition 2.9. Let Ω be a set with four products ←, →, , . An Ω-Rota-Baxter algebra of weight 0 is a family (A, (P ω ) ω∈Ω ) where A is an associative algebra and P ω : A ⊗ A → A is a linear map for each ω ∈ Ω, such that Example 2.10. (a) If (Ω, ) is a semigroup, we recover the definition of Rota-Baxter family algebras [START_REF] Guo | Operated semigroups, Motzkin paths and rooted trees[END_REF][START_REF] Zhang | Free Rota-Baxter family algebras and (tri)dendriform family algebras[END_REF] by defining

α ← β = α → β = α • β = α β, α β = α, α β = β,
and requiring all elements of λ to be equal. Note that this is the λ-ETS of Example 2.4 (c). (b) For a set Ω, define Proof. For a, b, c ∈ A and α, β ∈ Ω,

α → β = α β = β, α β = α ← β = α • β = α,
(a ≺ α b) ≺ β c = aP α (b) P β (c) = a P α (b)P β (c) = a P α→β (P α β (b)c) + P α←β (bP α β (c)) = aP α→β (P α β (b)c) + aP α←β (bP α β (c)) = a ≺ α→β (b α β c) + a ≺ α←β (b ≺ α β c), a α (b ≺ β c) = P α (a) bP β (c) = P α (a)b P β (c) = (a α b) ≺ β c, a α (b β c) = P α (a) P β (b)c = P α (a)P β (b) c = P α→β (P α β (a)b) + P α←β (aP α β (b)) c = P α→β (P α β (a)b)c + P α←β (aP α β (b)c = (a α β b) α→β c + (a ≺ α β b) α←β c.
2.2. Ω-Rota-Baxter algebras on typed angularly decorated planar rooted trees. First, let us recall some notations on planar rooted trees (see [START_REF] Zhang | Free (tri)dendriform family algebras[END_REF] for more details). For a planar rooted tree T , we shall consider the root and the leaves of T as edges rather than vertices. Denote by IE(T ) the set of internal edges of T , i.e. edges which are neither leaves nor the root and denote by V(T ) the set of vertices of T . For each vertex v yields a (possibly empty) set of angles A(v), an angle being a pair (e, e ) of adjacent incoming edges for v. Let A(T ) = v∈V(T )

A(v) be the set of angles of T . Then:

Definition 2.12. [14, Definition 2.2] Let X and Ω be two sets. An X-angularly decorated Ωtyped (abbr. typed angularly decorated) planar rooted tree is a triple T = (T, dec, type), where T is a planar rooted tree, dec : A(T ) → X and type : IE(T ) → Ω are maps.

For n 0, let T n (X, Ω) denote the set of X-angularly decorated Ω-typed planar rooted trees with n+1 leaves and at least one internal vertex such that internal edges are decorated by elements of Ω. We put

T(X, Ω) := n 0 T n (X, Ω) and kT(X, Ω) := n 0 kT n (X, Ω).
For example,

T 0 (X, Ω) =          , α , α β , . . . α, β, • • • ∈ Ω          , T 1 (X, Ω) =            x , x α , x β α , x γ α β , x γ α β , x β α , . . . x ∈ X, α, β, γ, • • • ∈ Ω            , T 2 (X, Ω) =          x y γ β α , y x α , y x β α , x y α , x y α , x y β α , . . . x, y ∈ X, α, β, γ, • • • ∈ Ω          ,
Graphically, an element T ∈ T(X, Ω) is of the form:

T = T 1 T 2 T n T n+1 x 1 • • • x n α 1 α n+1 α 2 α n , with n 0, where x 1 , • • • , x n ∈ X, α i ∈ Ω if T i | and otherwise α i does not exist for 1 i n + 1.
For each ω ∈ Ω, there is a grafting operator B + ω : kT(X, Ω) → kT(X, Ω) which add a new root to a tree and an new internal edge typed by ω between the new root and the root of the tree.

For example,

B + ω α = α ω , B + ω x α = x α ω .
The depth dep(T ) of a rooted tree T is the maximal length of linear chains from the root to the leaves of the tree. For example,

dep = dep x = 1 and dep ω = dep x y α = 2.
We also consider the trivial tree | and put by convention dep(|) := 0. For each typed angularly decorated planar rooted tree T , define the number of branches of T to be bra(T )

= 0 if T = |.
Otherwise, dep(T ) 1 and T is of the form

T = T 1 T 2 T n T n+1 x 1 • • • x n α 1 α n+1 α 2 α n with n 0,
where T j ∈ T(X, Ω) {|}, j = 1, . . . , n + 1. We define bra(T ) := n + 1. For example, bra = 1, bra

y x α = 2
and bra

x y α = 3.
Let X be a set, (Ω, ←, →, , , •) be a set with five products, and λ = (λ α,β ) (α,β)∈Ω 2 be a family of elements in k indexed by Ω 2 . By analogy with the construction of free Rota-Baxter algebras, we define a product on kT(X, Ω) as follows. For T, T ∈ T(X, Ω), we define T T by induction on dep(T ) + dep(T ) 2. For the initial step dep(T ) + dep(T ) = 2, we have dep(T ) = dep(T ) = 1 and T, T are of the form

T = x 1 • • • x m and T = y 1 • • • y n , with m, n 0. Define (38) T T := x 1 • • • x m y 1 • • • y n := x 1 • • • x m y 1 • • • y n .
For the induction step dep(T ) + dep(T ) 3, the trees T and T are of the form

T = T 1 T 2 T m T m+1 x 1 • • • x m α 1 α m+1 α 2 α m and T = T 1 T 2 T n T n+1 y 1 • • • y n β 1 β n+1 β 2 β n with some T i | or some T j |.
There are four cases to consider. Case 1:

T m+1 = | = T 1 . Define (39) T T := T 1 T 2 T m x 1 • • • x m α 1 α 2 α m T 2 T n T n+1 y 1 • • • y n β n+1 β 2 β n := T 1 T 2 T m T 2 T n T n+1 x 1 • • • x m y 1 • • • y n α 1 β n+1 α 2 α m β 2 β n . Case 2: T m+1 | = T 1 . Define (40) T T := T 1 T 2 T m T m+1 x 1 • • • x m α 1 α m+1 α 2 α m T 2 T n T n+1 y 1 • • • y n β n+1 β 2 β n := T 1 T 2 T m T m+1 T 2 T n T n+1 x 1 • • • x m y 1 • • • y n α 1 β n+1 α 2 α m β 2 β n α m+1
.

Case 3:

T m+1 = | T 1 . Define (41) T T := T 1 T 2 T m x 1 • • • x m α 1 α 2 α m T 1 T 2 T n T n+1 y 1 • • • y n β 1 β n+1 β 2 β n := T 1 T 2 T m T 1 T 2 T n T n+1 x 1 • • • x m y 1 • • • y n α 1 β n+1 α 2 α m β 2 β n β 1 . Case 4: T m+1 | T 1 . Define T T := T 1 T 2 T m T m+1 x 1 • • • x m α 1 α m+1 α 2 α m T 1 T 2 T n T n+1 y 1 • • • y n β 1 β n+1 β 2 β n := T 1 T 2 T m x 1 • • • x m α 1 α 2 α m B + α m+1 (T m+1 ) B + β 1 (T 1 ) T 2 T n T n+1 y 1 • • • y n β n+1 β 2 β n := T 1 T 2 T m x 1 • • • x m α 1 α 2 α m B + α m+1 →β 1 B + α m+1 β 1 (T m+1 ) T 1 + B + α m+1 ←β 1 T m+1 B + α m+1 β 1 (T 1 ) (42) + λ α m+1 ,β 1 B + α m+1 •β 1 T m+1 T 1 T 2 T n T n+1 y 1 • • • y n β n+1 β 2 β n .
Here the first is defined by Case 3, the second, third and fourth are defined by induction and the last is defined by Case 2. This inductively define the multiplication on T(X, Ω). We then extend by linearity to kT(X, Ω). We then have the following result:

Lemma 2.13. Let (Ω, ←, →, , , •, λ) be a λ-ETS. Then (kT(X, Ω), ) is an associative algebra with identity .

Proof. By the construction of , kT(X, Ω) is closed under and is the identity of . Now we show the associativity of , i.e.

(T 1 T 2 ) T 3 = T 1 (T 2 T 3 ), (43) for all T 1 , T 2 , T 3 ∈ T(X, Ω) We prove Eq. ( 43) by induction on the sum of depths p := dep(T 1 ) + dep(T 2 ) + dep(T 3 ). If p = 3, then dep(T 1 ) = dep(T 2 ) = dep(T 3 ) = 1 and T 1 , T 2 , T 3 are of the form

T 1 = x 1 • • • x l , T 2 = y 1 • • • y m , and
T 3 = z 1 • • • z n
with l, m, n 0.

Then (T 1 T 2 ) T 3 = T 1 (T 2 T 3 ) by a direct calculation. For the induction step p 4, we use induction on the sum of branches q := bra(T 1 ) + bra(T 2 ) + bra(T 3 ). If q = 3 and one of T 1 , T 2 , T 3 has depth 1, then this tree must be of the form and the associativity of follows directly. Assume

T 1 = B + α (T 1 ), T 2 = B + β (T 2 ), T 3 = B + γ (T 3 ) for some α, β, γ ∈ Ω and T 1 , T 2 , T 3 ∈ T(X, Ω), then (T 1 T 2 ) T 3 = B + α (T 1 ) B + β (T 2 ) B + γ (T 3 ) = B + α→β (B + α β (T 1 ) T 2 ) B + γ (T 3 ) + B + α←β (T 1 B + α β (T 2 )) B + γ (T 3 ) + λ α,β B + α•β (T 1 T 2 ) B + γ (T 3 ) = B + (α→β)→γ B + (α→β) γ (B + α β (T 1 ) T 2 ) T 3 + B + (α→β)←γ (B + α β (T 1 ) T 2 ) B + (α→β) γ (T 3 ) + λ α→β,γ B + (α→β)•γ (B + α β (T 1 ) T 2 ) T 3 + B + (α←β)→γ B + (α←β) γ (T 1 B + α β (T 2 )) T 3 + B + (α←β)←γ (T 1 B + α β (T 2 )) B + (α←β) γ (T 3 ) + λ α←β,γ B + (α←β)•γ (T 1 B + α β (T 2 )) T 3 + λ α,β B + (α•β)→γ B + (α•β) γ (T 1 T 2 ) T 3 + λ α,β B + (α•β)←γ (T 1 T 2 ) B + (α•β) γ (T 3 ) + λ α,β λ α•β,γ B + (α•β)•γ (T 1 T 2 ) T 3 = B + (α→β)→γ B + (α→β) γ (B + α β (T 1 ) T 2 ) T 3 + B + (α→β)←γ (B + α β (T 1 ) T 2 ) B + (α→β) γ (T 3 ) + λ α→β,γ B + (α→β)•γ (B + α β (T 1 ) T 2 ) T 3 + B + (α←β)→γ B + (α←β) γ (T 1 B + α β (T 2 )) T 3 + B + (α←β)←γ T 1 (B + α β (T 2 ) B + (α←β) γ (T 3 )) + λ α←β,γ B + (α←β)•γ (T 1 B + α β (T 2 )) T 3 + λ α,β B + (α•β)→γ B + (α•β) γ (T 1 T 2 ) T 3 + λ α,β B + (α•β)←γ (T 1 T 2 ) B + (α•β) γ (T 3 ) + λ α,β λ α•β,γ B + (α•β)•γ (T 1 T 2 ) T 3 (by the induction hypothesis) = B + (α→β)→γ B + (α→β) γ (B + α γ (T 1 ) T 2 ) T 3 + B + (α→β)←γ (B + α β (T 1 ) T 2 ) B + (α→β) γ (T 3 ) + λ α→β,γ B + (α→β)•γ (B + α β (T 1 ) T 2 ) T 3 + B + (α←β)→γ B + (α←β) γ (T 1 B + α β (T 2 )) T 3 + B + (α←β)←γ T 1 B + (α β)→((α←β) γ) (B + (α β) ((α←β) γ) (T 2 ) T 3 ) + B + (α←β)←γ (T 1 B + (α β)←((α←β) γ) (T 2 B + (α β) ((α←β) γ) (T 3 ))) + λ α β,(α←β) γ B + (α←β)←γ T 1 B + (α β)•((α←β) γ) (T 2 T 3 ) + λ α←β,γ B + (α←β)•γ (T 1 B + α β (T 2 )) T 3 + λ α,β B + (α•β)→γ B + (α•β) γ (T 1 T 2 ) T 3 + λ α,β B + (α•β)←γ (T 1 T 2 ) B + (α•β) γ (T 3 ) + λ α,β λ α•β,γ B + (α•β)•γ (T 1 T 2 ) T 3 , and
T 1 (T 2 T 3 ) = B + α (T 1 ) B + β (T 2 ) B + γ (T 3 ) = B + α (T 1 ) B + β→γ (B + β γ (T 2 ) T 3 ) + B + α (T 1 ) B + β←γ (T 2 B + β γ (T 3 )) + λ β,γ B + α (T 1 ) B + β•γ (T 2 T 3 ) = B + α→(β→γ) B + α (β→γ) (T 1 ) (B + β γ (T 2 ) T 3 ) + B + α←(β→γ) T 1 B + α (β→γ) (B + β γ (T 2 ) T 3 ) + λ α,β→γ B + α•(β→γ) T 1 (B + β γ (T 2 ) T 3 ) + B + α→(β←γ) B + α (β←γ) (T 1 ) (T 2 B + β γ (T 3 )) + B + α←(β←γ) T 1 B + α (β←γ) (T 2 B + β γ (T 3 )) + λ α,β←γ B + α•(β←γ) T 1 (T 2 B + β γ (T 3 )) + λ β,γ B + α→(β•γ) B + α (β•γ) (T 1 ) (T 2 T 3 ) + λ β,γ B + α←(β•γ) T 1 B + α←(β•γ) (T 2 T 3 ) + λ β,γ λ α,β•γ B + α•(β•γ) T 1 (T 2 T 3 ) = B + α→(β→γ) (B + α (β→γ) (T 1 ) B + β γ (T 2 )) T 3 + B + α←(β→γ) T 1 B + α (β→γ) (B + β γ (T 2 ) T 3 ) + λ α,β→γ B + α•(β→γ) T 1 (B + β γ (T 2 ) T 3 ) + B + α→(β←γ) B + α (β←γ) (T 1 ) (T 2 B + β γ (T 3 )) + B + α←(β←γ) T 1 B + α (β←γ) (T 2 B + β γ (T 3 )) + λ α,β←γ B + α•(β←γ) T 1 (T 2 B + β γ (T 3 )) + λ β,γ B + α→(β•γ) B + α (β•γ) (T 1 ) (T 2 T 3 ) + λ β,γ B + α←(β•γ) T 1 B + α←(β•γ) (T 2 T 3 ) + λ β,γ λ α,β•γ B + α•(β•γ) T 1 (T 2 T 3 ) (by the induction hypothesis) = B + α→(β→γ) B + (α (β→γ))→(β γ) (B + (α (β→γ)) (β γ) (T 1 ) T 2 ) T 3 + B + α→(β→γ) B + α (β→γ)←(β γ) (T 1 B + (α (β→γ) (β γ)) (T 2 )) T 3 + λ α (β→γ),β γ B + α→(β→γ) (B + (α (β→γ))•(β γ) (T 1 T 2 ) T 3 ) + B + α←(β→γ) T 1 B + α (β→γ) (B + β γ (T 2 ) T 3 ) + λ α,β→γ B + α•(β→γ) T 1 (B + β γ (T 2 ) T 3 ) + B + α→(β←γ) B + α (β←γ) (T 1 ) (T 2 B + β γ (T 3 )) + B + α←(β←γ) T 1 B + α (β←γ) (T 2 B + β γ (T 3 )) + λ α,β←γ B + α•(β←γ) T 1 (T 2 B + β γ (T 3 )) + λ β,γ B + α→(β•γ) B + α (β•γ) (T 1 ) (T 2 T 3 ) + λ β,γ B + α←(β•γ) T 1 B + α←(β•γ) (T 2 T 3 ) + λ β,γ λ α,β•γ B + α•(β•γ) T 1 (T 2 T 3 )
. By the induction hypothesis and (Ω, ←, →, , , •, λ) being a λ-ETS, we get

(T 1 T 2 ) T 3 = T 1 (T 2 T 3 ).
If q > 3, then at least one of T 1 , T 2 , T 3 have branches greater than or equal to 2. If bra(T 1 ) 2, then there exist T 1 , T 1 of the form

T 1 = T 1 T 2 T m x 1 • • • x m α 1 α 2 α m and T 1 = T 1 T 2 T n T n+1 y 1 • • • y n β n+1 β 2 β n such that T 1 = T 1 T 1 . Hence (T 1 T 2 ) T 3 = ((T 1 T 1 ) T 2 ) T 3 = (T 1 (T 1 T 2 )) T 3
(by the induction hypothesis) = T 1 ((T 1 T 2 ) T 3 ) (by the form of T 1 and the definition of ) = T 1 (T 1 (T 2 T 3 ))

(by the induction hypothesis)

= T 1 T 1 (T 2 T 3 )
(by the form of T 1 and the definition of ) = T 1 (T 2 T 3 ).

If bra(T 2 ) 2 or bra(T 3 ) 2, the associativity can be proved similarly.

Let i : X → kT(X, Ω), x → x be the natural inclusion. Then Theorem 2.14. Let Ω be a set with five products ←, →, , , • and λ a family of elements in k indexed by Ω 2 . Then the following conditions are equivalent:

(a) (kT(X, Ω), , (B + ω ) ω∈Ω ) together with the map i is the free Ω-Rota-Baxter algebra generated by X.

(b) (kT(X, Ω), , (B + ω ) ω∈Ω ) is an Ω-Rota-Baxter algebra. (c) (Ω, ←, →, , , •, λ) is a λ-ETS.
B + α ( x ) B + β ( y ) B + γ ( z ) = B + α→β (B + α β ( x ) y ) B + γ ( z ) + B + α←β ( x B + α β ( y )) B + γ ( z ) + λ α,β B + α•β ( x y ) B + γ ( z ) = B + (α→β)→γ B + (α→β) γ (B + α β ( x ) y ) z + B + (α→β)←γ (B + α β ( x ) y ) B + (α→β) γ ( z ) + λ α→β,γ B + (α→β)•γ (B + α β ( x ) y ) z + B + (α←β)→γ B + (α←β) γ ( x B + α β ( y )) z + B + (α←β)←γ ( x B + α β ( y )) B + (α←β) γ ( z ) + λ α←β,γ B + (α←β)•γ ( x B + α β ( y )) z + λ α,β B + (α•β)→γ B + (α•β) γ ( x y ) z + λ α,β B + (α•β)←γ ( x y ) B + (α•β) γ ( z ) + λ α,β λ α•β,γ B + (α•β)•γ ( x y ) z = B + (α→β)→γ B + (α→β) γ (B + α γ ( x ) y ) z + B + (α→β)←γ (B + α β ( x ) y ) B + (α→β) γ ( z ) + λ α→β,γ B + (α→β)•γ (B + α β ( x ) y ) z + B + (α←β)→γ B + (α←β) γ ( x B + α β ( y )) z + B + (α←β)←γ x B + (α β)→((α←β) γ) (B + (α β) ((α←β) γ) ( y ) z ) + B + (α←β)←γ ( x B + (α β)←((α←β) γ) ( y B + (α β) ((α←β) γ) ( z ))) + λ α β,(α←β) γ B + (α←β)←γ x B + (α β)•((α←β) γ) ( y z ) + λ α←β,γ B + (α←β)•γ ( x B + α β ( y )) z + λ α,β B + (α•β)→γ B + (α•β) γ ( x y ) z + λ α,β B + (α•β)←γ ( x y ) B + (α•β) γ ( z ) + λ α,β λ α•β,γ B + (α•β)•γ ( x y ) z = • (α → β) γ α β (α → β) → γ z y x + • α β (α → β) γ (α → β) ← γ y z x + λ α→β,γ (α → β) • γ α β y z x • + • (α ← β) γ α β (α ← β) → γ z x y + • (α β) → ((α ← β) γ) (α β) ((α ← β) γ) (α ← β) ← γ x z y + • (α β) ← ((α ← β) γ) (α β) ((α ← β) γ) (α ← β) ← γ x y z + λ α β,(α←β) γ • y z (α β) • ((α ← β) γ) (α ← β) ← γ x + λ α←β,γ x z y • α β (α ← β) • γ + λ α,β • z x y (α • β) γ (α • β) → γ + λ α,β • x y z (α • β) γ (α • β) ← γ + λ α,β λ α•β,γ z y x • (α • β) • γ , and
B + α ( x ) B + β ( y ) B + γ ( z ) = B + α ( x ) B + β→γ (B + β γ ( y ) z ) + B + α ( x ) B + β←γ ( y B + β γ ( z )) + λ β,γ B + α ( x ) B + β•γ ( y z ) = B + α→(β→γ) B + α (β→γ) ( x ) (B + β γ ( y ) z ) + B + α←(β→γ) x B + α (β→γ) (B + β γ ( y ) z ) + λ α,β→γ B + α•(β→γ) x (B + β γ ( y ) z ) + B + α→(β←γ) B + α (β←γ) ( x ) ( y B + β γ ( z )) + B + α←(β←γ) x B + α (β←γ) ( y B + β γ ( z )) + λ α,β←γ B + α•(β←γ) x ( y B + β γ ( z )) + λ β,γ B + α→(β•γ) B + α (β•γ) ( x ) ( y z ) + λ β,γ B + α←(β•γ) x B + α←(β•γ) ( y z ) + λ β,γ λ α,β•γ B + α•(β•γ) x ( y z ) = B + α→(β→γ) B + (α (β→γ))→(β γ) (B + (α (β→γ)) (β γ) ( x ) y ) z + B + α→(β→γ) B + α (β→γ)←(β γ) ( x B + (α (β→γ) (β γ)) ( y )) z + λ α (β→γ),β γ B + α→(β→γ) (B + (α (β→γ))•(β γ) ( x y ) z ) + B + α←(β→γ) x B + α (β→γ) (B + β γ ( y ) z ) + λ α,β→γ B + α•(β→γ) x (B + β γ ( y ) z ) + B + α→(β←γ) B + α (β←γ) ( x ) ( y B + β γ ( z )) + B + α←(β←γ) x B + α (β←γ) ( y B + β γ ( z )) + λ α,β←γ B + α•(β←γ) x ( y B + β γ ( z )) + λ β,γ B + α→(β•γ) B + α (β•γ) ( x ) ( y z ) + λ β,γ B + α←(β•γ) x B + α←(β•γ) ( y z ) + λ β,γ λ α,β•γ B + α•(β•γ) x ( y z ) = • (α (β → γ)) → (β γ) (α (β → γ)) (β γ) α → (β → γ) z y x + • (α (β → γ)) ← (β γ) (α (β → γ)) (β γ) α → (β → γ) z x y + λ α (β→γ),β γ • z x y (α (β → γ)) • (β γ) α → (β → γ) + • α (β → γ) β γ α ← (β → γ) x z y + λ α,β→γ x z y • β γ α • (β → γ) + • α (β ← γ) β γ α → (β ← γ) y z x + • α (β ← γ) β γ α ← (β ← γ) x y z + λ α,β←γ • x y z β γ α • (β ← γ) + λ β,γ α → (β • γ) α (β • γ) y z x • + λ β,γ • y z α (β • γ) α ← (β • γ) x + λ β,γ λ α,β•γ z y x • α • (β • γ) .
By Lemma 2.13 and identifying the types of the planar rooted trees, we get that (Ω, ←, →, , , •, λ) is a λ-ETS.

(c) =⇒ (a) By Lemma 2.13 and the definition of , (kT(X, Ω), , (B + ω ) ω∈Ω ) is an Ω-Rota-Baxter algebra. Now we show the freeness of kT(X, Ω).

Let (R, •, (P ω ) ω∈Ω ) be an Ω-Rota-Baxter algebra of weight λ Ω and f : X → R a set map. We extend f to an Ω-Rota-Baxter algebra morphism f : kT(X,

Ω) → R such that f • i = f .
For T ∈ T(X, Ω), we define f (T ) by induction on dep(T ). If dep(T ) = 1, then T is of the form

T = x 1 • • • x m . Define f (T ) := f (x 1 ) • f (x 2 ) • • • f (x m ).
For the induction step of dep(T ) 2, we define f (T ) by induction on the branches of T . If bra(T ) = 1, then T is of the form

T = T 1 T 2 T m T m+1 x 1 • • • x m α 1 α m+1 α 2 α m • ω . Define f (T ) := P ω P α 1 f (T 1 ) • f (x 1 ) • P α 2 f (T 2 ) • • • P α m f (T m ) • f (x m ) • P α f (T m+1 ) .
If bra(T ) > 1, then T is of the form

T = T 1 T 2 T m T m+1 x 1 • • • x m α 1 α m+1 α 2 α m . Define f (T ) := P α 1 f (T 1 ) • f (x 1 ) • P α 2 f (T 2 ) • • • P α m f (T m ) • f (x m ) • P α f (T m+1 ) .
By construction of f , f • i = f and P ω f = f B + ω for all ω ∈ Ω. Next we show that f is an algebra homomorphism, i.e.

f (T T ) = f (T ) • f (T ) for all T, T ∈ T(X, Ω). (44)
We prove Eq. ( 44) by induction on dep(T ) + dep(T ). If dep(T ) + dep(T ) = 2, then dep(T ) = dep(T ) = 1 and

T = x 1 • • • x m and T = y 1 • • • y n , with m, n 0,
and

f (T T ) = f (x 1 ) • • • f (x m ) • f (y 1 ) • • • f (y n ) = ( f (x 1 ) • • • f (x m )) • ( f (y 1 ) • • • f (y n )) = f (T ) f (T ).
For the induction step of dep(T ) + dep(T ) 3. If T T belongs to the first three cases, then f (T T ) = f (T ) • f (T ) by the definition of and the construction of f . So we only need to consider the fourth case. Then

f (T T ) = f T 1 T 2 T m x 1 • • • x m α 1 α 2 α m B + α m+1 →β 1 B + α m+1 β 1 (T m+1 ) T 1 + B + α m+1 ←β 1 T m+1 B + α m+1 β 1 (T 1 ) + λ α m+1 ,β 1 B + α m+1 •β 1 T m+1 T 1 T 2 T n T n+1 y 1 • • • y n β n+1 β 2 β n = P α 1 ( f (T 1 )) • f (x 1 ) • P α 2 ( f (T 2 )) • • • P α m ( f (T m )) • f (x m ) • f B + α m+1 →β 1 B + α m+1 β 1 (T m+1 ) T 1 + B + α m+1 ←β 1 T m+1 B + α m+1 β 1 (T 1 ) + λ α m+1 ,β 1 B + α m+1 •β 1 T m+1 T 1 • f (y 1 ) • P β 2 ( f (T 2 )) • • • P β n+1 ( f (T n+1 )) = P α 1 ( f (T 1 )) • f (x 1 ) • P α 2 ( f (T 2 )) • • • P α m ( f (T m )) • f (x m ) • P α m+1 ( f (T m+1 )) • P β 1 ( f (T 1 )) • f (y 1 ) • P β 2 ( f (T 2 )) • • • P β n+1 ( f (T n+1 )) = f (T ) f (T ).
Moreover, by the construction of f , it is the unique way to extend f as an Ω-Rota-Baxter algebra morphism. Hence (kT(X, Ω), , (B + ω ) ω∈Ω ) together with the map i is the free Ω-Rota-Baxter algebra generated by X.

Remark 2.15.

(a) In Definition 2.8, Ω is required to be a set with five products ←, →, , , • and λ is required to be a family of elements in k indexed by Ω 2 . This defines a category of Ω-Rota-Baxter algebras for any such Ω. Generally, free Ω-Rota-Baxter algebras are not based on Ω-angularly decorated planar trees. However, by Theorem 2.14, the condition of a free Ω-Rota-Baxter algebra based on the combinatorics of Ω-angularly decorated planar trees, similar to the one of (classical) Rota-Baxter algebras, is equivalent to (Ω, ←, → , , , •, λ) being a λ-ETS.

(b) As a particular case, we recover the description of free family Rota-Baxter algebras of [START_REF] Zhang | Free (tri)dendriform family algebras[END_REF]. An alternative description of free Rota-Baxter algebras (with rooted forests) is done in [START_REF] Ebrahimi | Free Rota-Baxter algebras and rooted trees[END_REF].

Taking all elements in λ to be 0, we get the following result:

Corollary 2.16. Let Ω be a set with four products ←, →, , . Then the following conditions are equivalent: (a) (kT(X, Ω), , (B + ω ) ω∈Ω ) together with the map i is the free Ω-Rota-Baxter algebra of weight 0 generated by X. (b) (kT(X, Ω), , (B + ω ) ω∈Ω ) is an Ω-Rota-Baxter algebra of weight 0. (c) (Ω, ←, →, , ) is an EDS.

2.3.

Commutative Ω-Rota-Baxter algebras on typed words. Let Ω be a set and V a vector space. Recall from [5] that the space of Ω-typed words in V is

Sh + Ω (V) = n 1 (kΩ) ⊗(n-1) ⊗ V ⊗n .
For the ease of statement, we redefine the space of Ω-typed words in V as

Sh + Ω (V) = n 0 V ⊗ (kΩ) ⊗ • • • ⊗ (kΩ) ⊗ V (n + 1)'s V and n's (kΩ)
and write each pure

tensor v = v 0 ⊗ ω 1 ⊗ • • • ⊗ ω n ⊗ v n ∈ Ω under the form v = v 0 ⊗ ω 1 v 1 ⊗ ω 2 • • • ⊗ ω n v n ,
where n 0,

ω 1 , • • • , ω n ∈ Ω and v 0 , • • • , v n ∈ V with the convention v = v 0 if n = 0. We call v
an Ω-typed word in V and define its length (v) := n + 1.

Let A be an algebra with identity 1 A , (Ω, ←, →, , , •) be a set with five products and λ = (λ α,β ) (α,β)∈Ω 2 be a family of elements in k indexed by Ω 2 . For any pure tensors a = a (45)

0 ⊗ α 1 a , b = b 0 ⊗ β 1 b ∈ Sh + Ω (A)
a b :=                    a 0 b 0 , if m = n = 0, a 0 b 0 ⊗ α 1 a , if m > 0, n = 0, a 0 b 0 ⊗ β 1 b , if m = 0, n > 0, a 0 b 0 ⊗ α 1 →β 1 (1 A ⊗ α 1 β 1 a ) b + a 0 b 0 ⊗ α←β 1 a (1 A ⊗ α 1 β 1 b ) +λ α 1 ,β 1 a 0 b 0 ⊗ α 1 •β 1 (a b ), if m > 0, n > 0.
Extending bilinearly, we construct a product on Sh + Ω (A). Lemma 2.17. Let A be an algebra with identity 1 A , Ω a set with five products ←, →, , , • and λ a family of elements in k indexed by

Ω 2 . If (Ω, ←, →, , , •, λ) is a λ-ESD, then (Sh + Ω (A),
) is an associative algebra with identity 1 A .

Proof. By Eq. (45), Sh + Ω (A) is closed under and 1 A is the identity of .

a = a 0 ⊗ α 1 a , b = b 0 ⊗ β 1 b , c = c 0 ⊗ γ 1 c . Then (a b) c = (a 0 b 0 )c 0 ⊗ (α 1 →β 1 )→γ 1 (1 A ⊗ (α 1 →β 1 ) γ 1 ((1 A ⊗ α 1 ⊗ β 1 a ) b )) c + (a 0 b 0 )c 0 ⊗ (α 1 →β 1 )←γ 1 ((1 A ⊗ α 1 β 1 a ) b ) (1 A ⊗ (α 1 →β 1 ) γ 1 c ) + λ (α 1 →β 1 ),γ 1 (a 0 b 0 )c 0 ⊗ (α 1 →β 1 )•γ 1 ((1 A ⊗ α 1 β 1 a ) b ) c + (a 0 b 0 )c 0 ⊗ (α 1 ←β 1 )→γ 1 (1 A ⊗ (α 1 ←β 1 ) γ 1 (a (1 A ⊗ α 1 β 1 b ))) c + (a 0 b 0 )c 0 ⊗ (α 1 ←β 1 )←γ 1 a (1 A ⊗ (α 1 β 1 )→((α 1 ←β 1 ) γ 1 ) ((1 A ⊗ (α 1 β 1 ) ((α 1 ←β 1 ) γ 1 ) b ) c )) + (a 0 b 0 )c 0 ⊗ (α 1 ←β 1 )←γ 1 a (1 A ⊗ (α 1 β 1 )←((α 1 ←β 1 ) γ 1 ) (b (1 A ⊗ (α 1 β 1 ) ((α 1 ←β 1 ) γ 1 ) c ))) + λ (α 1 β 1 ),((α 1 ←β 1 ) γ 1 ) (a 0 b 0 )c 0 ⊗ (α 1 ←β 1 )←γ 1 a (1 A ⊗ (α 1 β 1 )•((α 1 ←β 1 ) γ 1 ) (b c )) + λ (α 1 ←β 1 ),γ 1 (a 0 b 0 )c 0 ⊗ (α 1 ←β 1 )•γ 1 (a (1 A ⊗ α 1 β 1 b )) c + λ α 1 ,β 1 (a 0 b 0 )c 0 ⊗ (α 1 •β 1 )→γ 1 (1 A ⊗ (α 1 •β 1 ) γ 1 (a b )) c + λ α 1 ,β 1 (a 0 b 0 )c 0 ⊗ (α 1 •β 1 )←γ 1 (a b ) (1 A ⊗ (α 1 •β 1 ) γ 1 c ) + λ α 1 ,β 1 λ (α 1 •β 1 ),γ 1 (a 0 b 0 )c 0 ⊗ (α 1 •β 1 )•γ 1 (a b ) c and a (b c) = a 0 (b 0 c 0 ) ⊗ α 1 →(β 1 →γ 1 ) (1 A ⊗ (α 1 (β 1 →γ 1 ))→(β 1 γ 1 ) ((1 A ⊗ (α 1 (β 1 →γ 1 )) (β 1 γ 1 ) a ) b )) c + a 0 (b 0 c 0 ) ⊗ α 1 →(β 1 →γ 1 ) (1 A ⊗ (α 1 (β 1 →γ 1 ))←(β 1 γ 1 ) (a (1 A ⊗ (α 1 (β 1 →γ 1 )) (β 1 γ 1 ) b ))) c + λ (α 1 (β 1 →γ 1 )),(β 1 γ 1 ) a 0 (b 0 c 0 ) ⊗ α 1 →(β 1 →γ 1 ) (1 A ⊗ (α 1 (β 1 →γ 1 ))•(β 1 γ 1 ) (a b )) c + a 0 (b 0 c 0 ) ⊗ α 1 ←(β 1 →γ 1 ) a (1 A ⊗ α 1 (β 1 →γ 1 ) ((1 A ⊗ β 1 γ 1 b ) c )) + λ α 1 ,(β 1 →γ 1 ) a 0 (b 0 c 0 ) ⊗ α 1 •(β 1 →γ 1 ) a ((1 A ⊗ β 1 γ 1 b ) c ) + a 0 (b 0 c 0 ) ⊗ α 1 →(β 1 ←γ 1 ) (1 A ⊗ α 1 (β 1 ←γ 1 ) a ) (b (1 A ⊗ β 1 γ 1 c )) + a 0 (b 0 c 0 ) ⊗ α 1 ←(β 1 ←γ 1 ) a (1 A ⊗ α 1 (β 1 ←γ 1 ) (b (1 A ⊗ β 1 γ 1 c ))) + λ α 1 ,(β 1 ←γ 1 ) a 0 (b 0 c 0 ) ⊗ α 1 •(β 1 ←γ 1 ) a (b (1 A ⊗ β 1 γ 1 c )) + λ β 1 ,γ 1 a 0 (b 0 c 0 ) ⊗ α 1 →(β 1 •γ 1 ) (1 A ⊗ α 1 (β 1 •γ 1 ) a ) (b c ) + λ β 1 ,γ 1 a 0 (b 0 c 0 ) ⊗ α 1 ←(β 1 •γ 1 ) a (1 A ⊗ α 1 (β 1 •γ 1 ) (b c )) + λ β 1 ,γ 1 λ α 1 ,(β 1 •γ 1 ) a 0 (b 0 c 0 ) ⊗ α 1 •(β 1 •γ 1 ) a (b c ) .
By induction hypothesis and (Ω, ←, →, , , •, λ) being a λ-ETS, (a b) c = a (b c). Hence (Sh + Ω (A), ) is an associative algebra with identity 1 A .

For each ω ∈ Ω, define a linear map P ω : Sh + Ω (A) → Sh + Ω (A), a → 1 A ⊗ ω a. If further A is a commutative algebra and (Ω, ←, →, , , •, λ) is a commutative λ-ETS, we get the following result:

Proposition 2.18. If A is a commutative algebra with identity 1 A and (Ω, ←, →, , , •, λ) is a commutative λ-ETS, then (Sh + Ω (A), , (P ω ) ω∈Ω ) is the free commutative Ω-Rota-Baxter algebra generated by A.

Proof. For a, b ∈ Sh + Ω (A) and α, β ∈ Ω, Suppose Eq. (47) holds for (a) + (b) < p, where p 2 is a fixed integer. We consider the case of (a) + (b) = p + 1. If one of (a), (b) is equal to 1, then Eq. (47) holds directly. We assume that a = a

P α (a) P β (b) = (1 A ⊗ α a) (1 A ⊗ β b) = 1 A ⊗ α→β (1 ⊗ α β a) b + 1 ⊗ α←β a (1 A ⊗ α β b) + λ α,β 1 A ⊗ α•
0 ⊗ α 1 a , b = b 0 ⊗ β 1 b , then a b = (a 0 ⊗ α 1 a ) (b 0 ⊗ β 1 b ) = a 0 b 0 ⊗ α 1 →β 1 (1 A ⊗ α 1 β 1 a ) b + a 0 b 0 ⊗ α 1 ←β 1 a (1 A ⊗ α 1 β 1 b ) + λ α 1 ,β 1 a 0 b 0 ⊗ α 1 •β 1 (a b ) = b 0 a 0 ⊗ α 1 →β 1 (1 A ⊗ α 1 β 1 a ) b + b 0 a 0 ⊗ α 1 ←β 1 a (1 A ⊗ α 1 β 1 b ) + λ α 1 ,β 1 b 0 a 0 ⊗ α 1 •β 1 (a b ) (by A being a commutative algebra) = b 0 a 0 ⊗ α 1 →β 1 b (1 A ⊗ α 1 β 1 a ) + b 0 a 0 ⊗ α 1 ←β 1 (1 A ⊗ α 1 β 1 b ) a + λ α 1 ,β 1 b 0 a 0 ⊗ α 1 •β 1 (b a ) (by the induction hypothesis) = b 0 a 0 ⊗ β 1 ←α 1 b (1 A ⊗ β 1 α 1 a ) + b 0 a 0 ⊗ β 1 →α 1 (1 A ⊗ β 1 α 1 b ) a + λ β 1 ,α 1 b 0 a 0 ⊗ β 1 •α 1 (b a ) (by Ω being commutative) = (b 0 ⊗ β 1 b ) (a 0 ⊗ α 1 a ) = b ⊗ a.
Hence (Sh + Ω (A), ) is a commutative algebra.

Let (R, •, (P ω ) ω∈Ω ) be a commutative Ω-Rota-Baxter algebra and f : A → R a commutative algebra homomorphism. We extend f to an Ω-Rota-Baxter algebra morphism f : Sh + Ω (A) → R as follows: for a ∈ Sh + Ω (A), we define f (a) by induction on (a). If (a) = 1, then define f (a) = f (a). Suppose f (a) has been defined for all a with (a) p, where p 1 is a fixed integer. Consider the case of (a) = p + 1. We suppose that a = a 0 ⊗ α 1 a , and we then put:

f (a) := f (a 0 ) • P α 1 ( f (a )).
We can get that it is the unique way to extend f as an Ω-Rota-Baxter algebra morphism. Hence (Sh + Ω (A), ) is the free commutative Ω-Rota-Baxter algebra generated by A.

Let us assume that A is unitary. We denote its unit by 1 A . For each ω ∈ Ω, define a linear map

P ω : Sh Ω (A) → Sh Ω (A), a → 1 A ⊗ ω a.
Proposition 2.19. If A is a unitary commutative algebra and (Ω, ←, →, , , •, λ) is a commutative λ-ETS, then (Sh Ω (A), , (P ω ) ω∈Ω ) is a commutative Ω-Rota-Baxter algebra.

Proof. For a, b ∈ Sh Ω (A) and α, β ∈ Ω,

P α (a) P β (b) = (1 A ⊗ α a) (1 A ⊗ β b) = 1 A ⊗ α→β (1 A ⊗ α β a) b + 1 A ⊗ α←β a (1 A ⊗ α β b) + λ α,β 1 A ⊗ α•
= a 0 ⊗ α 1 a , b = b 0 ⊗ β 1 b , then a b = (a 0 ⊗ α 1 a ) (b 0 ⊗ β 1 b ) = a 0 b 0 ⊗ α 1 →β 1 (1 A ⊗ α 1 β 1 a ) b + a 0 b 0 ⊗ α 1 ←β 1 a (1 A ⊗ α 1 β 1 b ) + λ α 1 ,β 1 a 0 b 0 ⊗ α 1 •β 1 (a b ) = b 0 a 0 ⊗ α 1 →β 1 (1 A ⊗ α 1 β 1 a ) b + b 0 a 0 ⊗ α 1 ←β 1 a (1 A ⊗ α 1 β 1 b ) + λ α 1 ,β 1 b 0 a 0 ⊗ α 1 •β 1 (a b ) (by A being a commutative algebra) = b 0 a 0 ⊗ α 1 →β 1 b (1 A ⊗ α 1 β 1 a ) + b 0 a 0 ⊗ α 1 ←β 1 (1 A ⊗ α 1 β 1 b ) a + λ α 1 ,β 1 b 0 a 0 ⊗ α 1 •β 1 (b a ) (by the induction hypothesis) = b 0 a 0 ⊗ β 1 ←α 1 b (1 A ⊗ β 1 α 1 a ) + b 0 a 0 ⊗ β 1 →α 1 (1 A ⊗ β 1 α 1 b ) a + λ β 1 ,α 1 b 0 a 0 ⊗ β 1 •α 1 (b a ) (by Ω being commutative) = (b 0 ⊗ β 1 b ) (a 0 ⊗ α 1 a ) = b ⊗ a.
Hence (Sh Ω (A), ) is a commutative algebra.

Let A be a commutative algebra. We put uA = k ⊕ A and give it a product defined by

(λ + a)(µ + b) = λµ + (λb + µa + ab).
Then uA is a commutative unitary algebra and its unit 1 A is the unit 1 of k. Theorem 2.20. We put

Sh Ω (A) = A ⊕ n 2 uA ⊗ (kΩ) ⊗ • • • ⊗ (kΩ) ⊗ uA n's V and (n -1)'s (kΩ)
.

Then Sh Ω (A) is the free commutative Ω-Rota-Baxter algebra generated by the algebra A.

Proof. Let (R, •, (P ω ) ω∈Ω ) be a commutative Ω-Rota-Baxter algebra and f : A → R a (nonunitary) algebra homomorphism. We extend f , first from uA to R as a unitary algebra morphism by sending 1 uA to 1 R , then as an Ω-Rota-Baxter algebra morphism f : Sh Ω (A) → R as follows: for a ∈ Sh Ω (A), we define f (a) by induction on (a). If (a) = 1, then define f (a) = f (a). Suppose f (a) has been defined for all a with (a) p, where p 1 is a fixed integer. Consider the case of (a) = p + 1. Suppose a = a 0 ⊗ α 1 a , then define

f (a) := f (a 0 ) • P α 1 ( f (a )).
For any a ∈ Sh Ω (A) and for any α ∈ Ω:

f • P α (a) = f (1 A ⊗ α a) = 1 B • P α ( f (a)) = P α • f (a).
Let us prove that this is an algebra morphism. Let a, b ∈ Sh Ω (A), let us prove that f (a

b) = f (a) f (b) by induction on n = (a) + (b). If (a) = (b) = 1, then f (a b) = f (a 0 b 0 ) = f (a 0 b 0 ) = f (a 0 ) • f (b 0 ) = f (a) • f (b). If (a) = 1 and (b) > 1, then f (a b) = f (a 0 b 0 ⊗ α 1 a ) = f (a 0 b 0 ) • P α 1 • f (a ) = f (a 0 ) • f (b 0 ) • P α 1 • f (a ) = f (a) • f (b). This is similar if (a) > 1 and (b) = 1. If (a) > 1 and (b) > 1, then f (a b) = f ( a 0 b 0 ⊗ α 1 →β 1 ((1 ⊗ α 1 β 1 a ) b )) + f (a 0 b 0 ⊗ α←β 1 (a (1 ⊗ α 1 β 1 b ))) + f (λ α 1 ,β 1 a 0 b 0 ⊗ α 1 •β 1 (a b )) = f ( a 0 b 0 ) • P α 1 →β 1 • f ((1 ⊗ α 1 β 1 a ) b ) + f (a 0 b 0 ) • P α←β 1 • f (a (1 ⊗ α 1 β 1 b ))) + λ α 1 ,β 1 f (a 0 b 0 ) • P α 1 •β 1 • f (a b ) = f (a 0 ) • f (b 0 ) • f (P α 1 →β 1 (P α 1 β 1 (a ) b )) + f (a 0 ) • f (b 0 ) • f (P α←β 1 (a P α 1 β 1 (b ))) + λ α 1 ,β 1 f (a 0 ) • f (b 0 ) • f (P α 1 •β 1 (a b )) = f (a 0 ) • f (b 0 ) • f (P α 1 (a )P β 1 (b )) = f (a 0 ) • f (b 0 ) • f (P α 1 (a )) • f (P β 1 (b )) (by the induction hypothesis) = f (a 0 ) • f (b 0 ) • P α 1 • f (a ) • P β 1 • f (b ) = f (a 0 ) • P α 1 • f (a ) • f (b 0 ) • P β 1 • f (b ) (as B is commutative) = f (a) • f (b).
We get that it is the unique way to extend f as an Ω-Rota-Baxter algebra morphism. Hence Sh Ω (A) is the free commutative Ω-Rota-Baxter algebra generated by A.

3. More results on λ-ETS and ETS 3.1. Description in terms of linear and bilinear maps. As in Lemma 5 of [5], we obtain:

Lemma 3.1. Let (Ω, ←, →, , , •) be a set with five operations and λ = (λ α,β ) α,β∈Ω be a family of elements in k indexed by Ω 2 . We denote by kΩ the vector space generated by Ω. We put:

ϕ ← : kΩ ⊗2 -→ kΩ ⊗2 α ⊗ β -→ α ← β ⊗ α β, ϕ → : kΩ ⊗2 -→ kΩ ⊗2 α ⊗ β -→ α → β ⊗ α β, ψ • : kΩ ⊗2 -→ kΩ α ⊗ β -→ λ α,β α • β.

3.2.

A description of all λ-ETS of cardinality two. The following table gives all λ-ETS. We slightly generalize our definition, by accepting more general maps ϕ • : kΩ ⊗2 -→ kΩ. The underlying set is {a, b} and all the products are given by a 2 × 2 table. Here, λ, µ are elements of the base field k. The commutative λ-ETS are the ones of type A and H, C 1 (λ), C 3 (λ), C 5 (λ), F 1 (λ, µ), F 1 (λ, µ) and F 4 (λ). The opposite of B 1 (λ), B 1 (λ), B 2 (λ) and B 2 (λ) are respectively D 1 (λ), D 1 (λ), D 2 (λ) and D 2 (λ). The opposite of C 2 is C 4 . The opposite of E 1 (λ), E 2 and E 3 (λ) are respectively G 1 (λ), G 2 and G 3 (λ). The opposite of F 1 (λ) is F 1 (λ). The λ-ETS F 2 and F 5 are not commutative but are isomorphic to their opposite in a non trivial way. Finally, if * is an associative product, the opposite of F 3 ( * ) is F 3 ( * op ).

3.3.

A description of all ETS of cardinality two. The following table gives all the ETS of cardinality 2.

  algebra is an associative algebra A with a linear endomorphism P : A -→ A, such that for any a, b ∈ A, P(a)P(b) = P(aP(b)) + P(P(a)b) + λP(ab),

P

  α (a)P β (b) = P α * β (P α (a)b + aP β (b) + λab).

  for parametrization of dendriform algebras. Particular examples of λ-ETS attached to a set give matching Rota-Baxter algebras (see Example 2.4-(b), with ψ • (α ⊗ β) = λα) and particular examples of λ-ETS attached to a semigroup gives family Rota-Baxter algebras (see Example 2.4-(c)).

P

  α (a)P β (b) = P α→β (P α β (a)b) + P α←β (aP α β (b)) + λ α,β P α•β (ab), for all a, b ∈ A and α, β ∈ Ω. If, further, A is commutative, then (A, (P ω ) ω∈Ω ) is a commutative Ω-Rota-Baxter algebra.

P

  α (a)P β (b) = P α→β (P α β (a)b) + P α←β (aP α β (b)), for all a, b ∈ A and α, β ∈ Ω.

  and λ α,β = λ α , for a family (λ α ) α∈Ω of elements of k. Then we get the concept of matching Rota-Baxter algebra [12], up to the change of the product of A into its opposite. As we know, Rota-Baxter algebras of weight 0 induce dendriform algebras [3]. Similarly, we can show that each Ω-Rota-Baxter algebra of weight 0 has a structure of an Ω-dendriform algebra [5, definition 11]: Proposition 2.11. Let Ω be a set with four products ←, →, , and (A, (P ω ) ω∈Ω ) an Ω-Rota-Baxter algebra of weight 0. Then (A, (≺ ω ) ω∈Ω , ( ω ) ω∈Ω ) is an Ω-dendriform algebra, where a ≺ ω b := aP ω (b), a ω b := P ω (a)b, for all a, b ∈ A and ω ∈ Ω.

  Proof. (a) =⇒ (b) It is obvious. (b) =⇒ (c) For α, β, γ ∈ Ω and x , y , z ∈ T(X, Ω), we have

  with (a) = m and (b) = n, define a b inductively as follows:

  For pure tensors a, b, c ∈ Sh + Ω (A), we prove (a b) c = a (b c) (46) by induction on (a) + (b) + (c). If (a) + (b) + (c) = 3, then (a) = (b) = (c) = 1 and a = a 0 , b = b 0 , c = c 0 . Hence (a b) c = a 0 b 0 c 0 = a (b c). Suppose Eq. (46) holds for (a) + (b) + (c) p, where p 3 is a fixed integer. Consider the case of (a) + (b) + (c) = p + 1. If one of (a), (b), (c) is equal to 1, then Eq. (46) holds by direct calculation. Hence we assume (a) > 1, (b) > 1, (c) > 1 and

  β (a b) = P α→β (P α β (a) b) + P α←β (a P α β (b)) + λ α,β P α•β (a b), hence Sh Ω (A) is an Ω-Rota-Baxter algebra. Next we show a b = b a (47) by induction on (a) + (b). If (a) + (b) = 2, then (a) = (b) = 1 and a b = a 0 b 0 = a 0 b 0 = b 0 a 0 = b 0 a 0 = b a.

  β (a b) = P α→β (P α β (a) b) + P α←β (a P α β (b)) + λ α,β P α•β (a b), hence Sh Ω (A) is an Ω-Rota-Baxter algebra. Next we show a b = b a (48) by induction on (a) + (b). If (a) + (b) = 2, then (a) = (b) = 1 and a b = a 0 b 0 = a 0 b 0 = b 0 a 0 = b 0 a 0 = b a. Suppose Eq. (48) holds for (a) + (b) < p, where p 2 is a fixed integer. We consider the case of (a) + (b) = p + 1. If one of (a), (b) is equal to 1, then Eq. (48) holds directly. So assume a

  µ)a (λ + µ)a (λ + µ)a λa + µb A 1 (λ, µ) µ)a (λ + µ)a (λ + µ)a λa + µb A 2 (λ, µ) µ)a (λ + µ)a (λ + µ)a λa + µb , (λ + µ)a (λ + µ)b (λ + µ)b λa + µb , F 1 (λ, µ), F 1 (λ, µ)

Acknowledgments: the authors acknowledge support from the grant ANR-20-CE40-0007 Combinatoire Algébrique, Résurgence, Probabilités Libres et Opérades. The second author is also supported by China Scholarship Council to visit ULCO and he thanks Prof. Dominique Manchon for valuable suggestions.

Data avalaibility: this article has no associated data.

Then (Ω, ←, →, , , •, λ) is a λ-ETS if, and only if:

In particular, ψ • is an associative product.

Proof. By Lemma 5 in [5], Eqs. ( 49)-( 53) are equivalent to (Ω, ←, →, , ) being an EDS. Moreover, direct computations prove that Eq. ( 54) is equivalent to Eq. ( 11) and condition (a); Eq. ( 55) is equivalent to Eq. ( 12) and condition (b); Eq. ( 56) is equivalent to Eq. ( 13) and condition (c); Eq. ( 57) is equivalent to Eq. ( 14) and condition (d); Eq. ( 58) is equivalent to Eq. ( 15) and condition (e); Eq. ( 59) is equivalent to Eq. ( 16) and condition (f) in Definition 2.3.

Similarly, we obtain for ETS: Lemma 3.2. Let (Ω, ←, →, , , * , •) be a set with six operations. We put:

Then (Ω, ←, →, , , * , •) is an ETS if, and only if, (34)-( 38) of [5] are satisfied and:

Proof. By Lemma 5 in [5], Eqs. (34)- [START_REF] Rota | Baxter algebras and combinatorial identities. I[END_REF] are equivalent to (Ω, ←, →, , ) being an EDS. Moreover, direct computations prove that Eq. ( 60) is equivalent to Eqs. (17),( 18) and (28); Eq. ( 61) is equivalent to Eqs. ( 19), (20) and (29); Eq. ( 62) is equivalent to Eqs. (21), ( 22) and (30); Eq. ( 63) is equivalent to Eqs. ( 23), ( 24) and (31); Eq. ( 64) is equivalent to Eqs. (25), ( 26) and (32); Eq. ( 65) is equivalent to Eqs. ( 27), (33) and (34).


Marko V Jankovic

A Disproof of Weak Goldbach's Conjecture

In this paper it is going to be proved that weak Goldbach's conjecture can not hold. The proof is based on fundamental theorem of arithmetic. This paper presents the idea that is simple modification (extension) of the idea used to prove that strong Goldbach's conjecture cannot hold.

Introduction

In elementary mathematics, a number line is a picture of the graduated straight line that serves as an abstraction to real numbers. Idea of number line was first introduced by John Napier [START_REF] Napier | A description of the admirable table of logarithms[END_REF], and later, John Wallis [START_REF] Wallis | Treatise of Algebra[END_REF] used this graphical representation to explain operations of addition and subtraction in terms of moving backward and forward under the metaphor of a person walking. However, that type of graphical interpretation is not particularly suitable in other contexts of interest. In order to obtain another useful representation of natural numbers, a multiplication tensor or M N -tensor has been recently introduced [START_REF] Jankovic | Multiplication Tensor and Number of Rational Numbers[END_REF]. Idea came from the fundamental theorem of arithmetic [START_REF] Hardy | An Introduction to the Theory of Numbers[END_REF]. In [START_REF] Jankovic | Addition Tensor and Goldbach's Conjecture[END_REF] an addition tensor has been introduced and that representation is used to show that strong Goldbach's conjecture [START_REF] Guy | Unsolved Problems in Number Theory[END_REF] cannot hold. In [START_REF] Jankovic | Addition Tensor and Goldbach's Conjecture[END_REF][START_REF] Jankovic | A Disproof of Strong Goldbach's Conjecture[END_REF] an elementary disproof of the strong Goldbach's conjecture has been presented, too. Multiplication and addition are introduced as new ways of presentation of numbers that should simplify reasoning in some contexts.

In this paper, we are going to present a simple extension (modification) of the idea in [START_REF] Jankovic | Addition Tensor and Goldbach's Conjecture[END_REF] in order to show that weak Goldbach's conjecture [START_REF] Guy | Unsolved Problems in Number Theory[END_REF] can not hold, too.

Remark:

In the text that follows, it is important to notice that there is no context in which it is correct to state that number of natural numbers is equal to the number of odd or even numbers (or that number of natural numbers is equal to the number of numbers divisible by 3, or 5, and so on)or in general, it is not considered possible that a set can have the same number of elements as the proper subset of that set (even in the case when a set contains infinite number of elements).

One way to understand the problem, for instance, is that it is possible to generate the same number of unique labels for odd or even numbers using the same number of unique labels for natural numbers. However, if we want to produce all those even and all those odd labels at the same time, obviously, it is necessary to have two sets of labels with natural numbers at the same time (it is necessary to clone the set of labels with natural numbers), which means that the number of labels with natural numbers on them, in that moment, is two times bigger than the number of labels with even or odd numbers on them. (In Cantor's set theory increase of the number of the elements of the set by cloning is ignored. In that theory, counting takes care only about unique elements of the setit creates a completely different reality with all known unusual phenomena that look completely counter intuitive, if you are not all the time aware of the fact that cloning does not change the number of elements of infinite set. However, if we assume that Cantor is right (or that his theory belongs to classical and not alternative mathematics) we will have to accept that fundamental theorem of arithmetic can not hold, and that creates a paradox, since it is proved that fundamental theorem of arithmetic holds. That consequence can be expected having in mind fact that if you change a way of counting the numbers, you will quite probably have to change a way how you add the numbers -then you will have to change how you multiply numbers, and that quite predictably can lead toward problems with fundamental theorem of arithmetic. This problem will be addressed in separate paper, but the problem can easily be identified at the end of this paper.)

The analysis of the problem can also be made in quantum probabilistic context, but it is beyond the scope of this paper. What can be immediately understood is that quantum probabilistic approach will offer a different angle from which problem can be analyzed, since in that context cloning is not allowed.

Multiplication tensor

The fundamental theorem of arithmetic states that every integer greater than 1 can be uniquely represented by a product of powers of prime numbers, up to the order of the factors [START_REF] Hardy | An Introduction to the Theory of Numbers[END_REF]. Having that in mind, an infinite dimensional tensor M N that contains all natural numbers only once, is going to be constructed [START_REF] Jankovic | Multiplication Tensor and Number of Rational Numbers[END_REF]. In order to do that we are going to mark vector that contains all prime numbers with p.

So, p(1) = 2, p(2) = 3, p(3) = 5, and so on. Tensor M N with elements m i1 i2 i3 ... is defined by the following equation (i 1 , i 2 , i 3 , … are natural numbers):

m i 1 i 2 i 3 ... = p(1) i 1 -1 p (2) i 2 -1 p(3) i 3 -1 ... .
The alternative definition is also possible. Now, the following notation is going to be assumed for some infinite size vectors

2 = [2 0 2 1 2 2 2 3 …], 3 = [3 0 3 1 3 2 3 3 …], 5 = [5 0 5 1 5 2 5 3 …] …
It is simple to be seen that every vector is marked by bold number that is equal to some prime number and that components of the vector are defined as powers of that prime number, including power zero (it can be seen that every vector represents infinite cyclic semi group defined by a primitive that is one of the prime numbers). Now, the M N -tensor can be defined as

M N = 2 ○ 3 ○ 5 ○ 7 ○...,
where ○ stands for outer product.

The tensor M N is of infinite dimension (equal to number of prime numbers) and size, and contains all natural numbers exactly ones. It is easy to understand why it is so, having in mind the fundamental theorem of arithmetic. This type of infinite tensor is called a half infinite tensor [START_REF] Jankovic | Multiplication Tensor and Number of Rational Numbers[END_REF].

The tensor that represents all odd numbers, M NO , contains elements defined as

m i 1 i 2 ... = p( 2) i 1 -1 p(3) i 2 -1 ... ,
or

M NO = 3 ○ 5 ○ 7 ○...,
where ○ stands for outer product.

Addition tensor

Now, recently introduced [START_REF] Jankovic | Addition Tensor and Goldbach's Conjecture[END_REF] addition tensor, or A N -tensor, is going to be presented. The tensor A N with elements a i1 i2 i3 ... is defined by the following equation (i 1 , i 2 , i 3 , … are natural numbers):

a i 1 i 2 i 3 ... =(i 1 -1) p(1)+(i 2 -1) p (2)+(i 3 -1) p(3)+... .
The edges of that tensor will contain the following vectors

2a = [0 2 4 6 …], 3a = [0 3 6 9 …], 5a = [0 5 10 15 …] …
It is simple to be seen that every vector is defined by some prime number and that components of the vector represent all non-negative integer multiples of that prime number. Now, the A N -tensor can be defined as

A N = 2a ○ + 3a ○ + 5a ○ + 7a ○ + ...,
where ○ + stands for outer sum, which is analogous to outer product where operation of interest is addition..

It is interesting to notice that the tensor M N does not contain number 0 that is neutral element for addition, while, on the other hand, the tensor A N does not contain number 1 that is neutral number for multiplication.

Here we will present an additional addition tensor A NO that is created by odd prime numbers, where elements of that tensor are defined as

a i 1 i 2 i 3 ... =(i 1 -1) p( 2)+(i 2 -1) p(3)+(i 3 -1) p(4)+... . or A NO = 3a ○ + 5a ○ + 7a ○ + ...,
where ○ + stands for outer sum.

A proof that weak Goldbach's conjecture cannot hold

Goldbach's conjecture, weak version, states that every odd integer bigger than 7 can be expressed as the sum of three odd prime numbers [START_REF] Guy | Unsolved Problems in Number Theory[END_REF]. From introduction of addition tensor it is trivial to understand that sub-tensor whose single prime factor has exponents bigger than 3, and we know that must be infinite number of such numbers (since there are infinitely many odd primes whose factorization contains at least one prime factor with exponent bigger than 3) -if it is not the case then fundamental theorem of arithmetic cannot hold. Now, it can easily be understood that the number of sums created by three odd prime numbers is smaller than the number of odd numbers, which means that weak Goldbach's conjecture can not hold. That completes the proof.

  :4, 1:4, …) have the same number of elements. Also, it is simple to understand that sub-tensor M NO (1:4, 1:4, 1:4, …) does not contain all odd numbers -it does not contain a single odd number

A NO (1:4, 1:4, 1:4, …) contains all possible sums of three prime numbers (plus many other sums). It is trivial to understand that sub-tensor A NO (1:4, 1:4, 1:4, …) and sub-tensor M NO (1:4,

1


Marko V Jankovic

Schnirelmann's Theorem Paradox

Introduction

In elementary mathematics, a number line is a picture of the graduated straight line that serves as an abstraction to real numbers. Idea of number line was first introduced by John Napier [START_REF] Napier | A description of the admirable table of logarithms[END_REF], and later, John Wallis [START_REF] Wallis | Treatise of Algebra[END_REF] used this graphical representation to explain operations of addition and subtraction in terms of moving backward and forward under the metaphor of a person walking. However, that type of graphical interpretation is not particularly suitable in other contexts of interest. In order to obtain another useful representation of natural numbers, a multiplication tensor or M N -tensor has been recently introduced [START_REF] Jankovic | Multiplication Tensor and Number of Rational Numbers[END_REF]. Idea came from the fundamental theorem of arithmetic [START_REF] Hardy | An Introduction to the Theory of Numbers[END_REF]. In [START_REF] Jankovic | Addition Tensor and Goldbach's Conjecture[END_REF] an addition tensor has been introduced. Multiplication and addition tensors are introduced as new ways of presentation of numbers that should simplify reasoning in some contexts.

In this paper, we are going to present a disproof of the Schnilermann's theorem [START_REF] Schnilermann | On the additive properties of numbers[END_REF] that uses the presentation of numbers introduced in [START_REF] Hardy | An Introduction to the Theory of Numbers[END_REF] and [START_REF] Jankovic | Addition Tensor and Goldbach's Conjecture[END_REF].

Remark:

In the text that follows, it is important to notice that there is no context in which it is correct to state that number of natural numbers is equal to the number of odd or even numbers (or that number of natural numbers is equal to the number of numbers divisible by 3, or 5, and so on)or in general, it is not considered possible that a set can have the same number of elements as the proper subset of that set (even in the case when a set contains infinite number of elements).

One way to understand the problem, for instance, is that it is possible to generate the same number of unique labels for odd or even numbers using the same number of unique labels for natural numbers. However, if we want to produce all those even and all those odd labels at the same time, obviously, it is necessary to have two sets of labels with natural numbers at the same time (it is necessary to clone the set of labels with natural numbers), which means that the number of labels with natural numbers on them, in that moment, is two times bigger than the number of labels with even or odd numbers on them. (In Cantor's set theory increase of the number of the elements of the set by cloning is ignored. In that theory, counting takes care only about unique elements of the setit creates a completely different reality with all known unusual phenomena that look completely counter intuitive, if you are not all the time aware of the fact that cloning does not change the number of elements of infinite set. However, if we assume that Cantor is right (or that his theory belongs to classical and not alternative mathematics) we will have to accept that fundamental theorem of arithmetic can not hold, and that creates a paradox, since it is proved that fundamental theorem of arithmetic holds. That consequence can be expected having in mind fact that if you change a way of counting the numbers, you will quite probably have to change a way how you add the numbers -then you will have to change how you multiply numbers, and that quite predictably can lead toward problems with fundamental theorem of arithmetic. This problem will be addressed in separate paper, but the problem can easily be identified at the end of this paper.)

The analysis of the problem can also be made in quantum probabilistic context, but it is beyond the scope of this paper. What can be immediately understood is that quantum probabilistic approach will offer a different angle from which problem can be analyzed, since in that context cloning is not allowed.

Multiplication tensor

The fundamental theorem of arithmetic states that every integer greater than 1 can be uniquely represented by a product of powers of prime numbers, up to the order of the factors [START_REF] Hardy | An Introduction to the Theory of Numbers[END_REF]. Having that in mind, an infinite dimensional tensor M N that contains all natural numbers only once, is going to be constructed [START_REF] Jankovic | Multiplication Tensor and Number of Rational Numbers[END_REF]. In order to do that we are going to mark vector that contains all prime numbers with p.

So, p(1) = 2, p(2) = 3, p(3) = 5, and so on. Tensor M N with elements m i1 i2 i3 ... is defined by the following equation (i 1 , i 2 , i 3 , … are natural numbers):

m i 1 i 2 i 3 ... = p(1) i 1 -1 p (2) i 2 -1 p(3) i 3 -1 ... .
The alternative definition is also possible. Now, the following notation is going to be assumed for some infinite size vectors

2 = [2 0 2 1 2 2 2 3 …], 3 = [3 0 3 1 3 2 3 3 …], 5 = [5 0 5 1 5 2 5 3 …] …
It is simple to be seen that every vector is marked by bold number that is equal to some prime number and that components of the vector are defined as powers of that prime number, including power zero (it can be seen that every vector represents infinite cyclic semi group defined by a primitive that is one of the prime numbers). Now, the M N -tensor can be defined as

M N = 2 ○ 3 ○ 5 ○ 7 ○...,
where ○ stands for outer product.

The tensor M N is of infinite dimension (equal to number of prime numbers) and size, and contains all natural numbers exactly ones. It is easy to understand why it is so, having in mind the fundamental theorem of arithmetic. This type of infinite tensor is called a half infinite tensor [START_REF] Jankovic | Multiplication Tensor and Number of Rational Numbers[END_REF].

Addition tensor

Now, recently introduced [START_REF] Jankovic | Addition Tensor and Goldbach's Conjecture[END_REF] addition tensor, or A N -tensor, is going to be presented. The tensor A N with elements a i1 i2 i3 ... is defined by the following equation (i 1 , i 2 , i 3 , … are natural numbers):

a i 1 i 2 i 3 ... =(i 1 -1) p(1)+(i 2 -1) p (2)+(i 3 -1) p(3)+... .
The edges of that tensor will contain the following vectors

2a = [0 2 4 6 …], 3a = [0 3 6 9 …], 5a = [0 5 10 15 …] …
It is simple to be seen that every vector is defined by some prime number and that components of the vector represent all non-negative integer multiples of that prime number. Now, the A N -tensor can be defined as

A N = 2a ○ + 3a ○ + 5a ○ + 7a ○ + ...,
where ○ + stands for outer sum, which is analogous to outer product where operation of interest is addition..

It is interesting to notice that the tensor M N does not contain number 0 that is neutral element for addition, while, on the other hand, the tensor A N does not contain number 1 that is neutral number for multiplication.

A disproof of Schnirelmann's theorem

Schnirelmann theorem [START_REF] Schnilermann | On the additive properties of numbers[END_REF] states that any natural number bigger than 1 can be written as the sum of not numbers and we can conclude that exists infinitely many natural numbers that are not contained in subtensor M N (1:C+1, 1:C+1, 1:C+1, …) -it is not difficult to be seen, that if it is not the case then fundamental theorem of arithmetic cannot hold. Now, it is not difficult to be understood that Schnirelmann's theorem cannot hold, since there will be infinitely many natural numbers that are not contained in sub-tensor A N (1:C+1, 1:C+1, 1:C+1, …) and cannot be represented as the sum of at most C prime numbers.

This completes this paper and creates a paradox that theorem can be proved and disproved at the same time.


Tom Davot

Sébastien Destercke

David Savourey

K-partitioning with imprecise probabilistic edges

K-partitioning with imprecise probabilistic edges

Tom Davot, Sébastien Destercke, David

Introduction

Partitioning a set of elements into heterogeneous groups such that elements within each group are as homogeneous as possible is a common task. It is at the very core of unsupervised learning and clustering problems, as well as when one considers networks of different kinds (e.g., social, voting, . . . ).

A natural way to encode the relations existing between elements is through graphs, where the presence of an edge indicates that elements should be grouped together. However, the existence of such a link may be subject to various uncertainties. For instance, if one thinks of grouping persons (e.g., in parliament) voting in the same way, it may be that we rarely observe two persons voting at the same time, or that two persons do not always have the same behaviour (sometimes voting in the same way, sometimes not). Imprecise probabilities offer a rich and natural model to describe this uncertainty.

However, once one has modelled link uncertainty by imprecise probabilities, it remains to infer what are the more likely clusters. In this paper, we study the problem of extracting possibly optimal clusters from imprecise Université de Technologie de Compiègne, CNRS, Heudiasyc (Heuristics and Diagnosis of Complex Systems), CS 60319 -60203 Compiègne Cedex, e-mail: surname.name@hds.utc.fr probabilistic graphs. We show that solving this problem exactly is NP-hard, and propose some heuristics. While there are existing approaches trying to extract partial clusters from imprecise probabilistic knowledge [START_REF] Denoeux | Evidential clustering: a review[END_REF][START_REF] Masson | Cautious relational clustering: A thresholding approach[END_REF], to our knowledge this is the first paper to view the problem as a robust decision-making one.

Notations and problem definition

Let be a simple loopless graph. We denote ( ) and ( ) the set of vertices and edges of , respectively (or simply or if no ambiguity occurs). The complement graph of , denoted ¯ is the graph defined by ( ¯ ) = ( ) and

( ¯ ) = { | ∉ ( )}.
A cluster graph is a disjoint union of complete graphs1 , called cliques. A -cluster graph is a cluster graph that contains non-empty connected components. Let be a complete graph, a -partition of is a -cluster subgraph of such that ( ) = ( ). In this paper, an imprecise probability is an interval [ , ] ⊆ [0, 1] of probabilities, and is called precise if = . An imprecise probabilistic graph ( , P) is a graph with a function P that associates to each edge in the graph an imprecise probability. If is an edge, we denote and the lower and upper bounds of P ( ), respectively. The probability bounds of an absence of an edge can be deduced by duality (i.e. [1 -, 1 -]). being the marginal probability is an edge (and 1-that it is not), we only assume

[ , ] ⊆ [0, 1]. A probability realisation : ( ) ↦ → [0, 1] of P is a function that asso- ciates to each edge a probability within [ , ]
. We denote R P the set of probability realisations of P. Let be a subgraph of and ∈ R P be a probability realisation. The probability of under , denoted ( ) corresponds to

( ) = ∈ ( ) ( ) ∉ ( ) 1 -( ).
Let 1 and 2 be two vertices -partitions of . We say that 1 is certainly more probable than 2 , denoted by 1 2 , if

∀ ∈ R P , ( 1 ) -( 2 ) > 0.
Let 1/ 2 denote the following value

1/ 2 = ∈ ( 1 )\ ( 2 ) 1 - ∈ ( 2 )\ ( 1 )
1 -.

Notice that if an edge belongs (resp. does not belong) to both 1 and 2 , then the factor ( ) (resp. 1 -( )) is present on both sides of the substraction. Thus, to verify if 1 is certainly more probable than 2 , we only need to consider edges in ( ) \ ( ( 1) ∩ ( 2)). Moreover, by duality

( 1 ) -( 2) is minimum if for every edge ∈ ( 1 ) \ ( 2 ) (resp. ∈ ( 2 ) \ ( 1)), we have ( ) = (resp. ( ) = ). Hence, we have the following property.

Property 1 Given two -partitions 1 and 2 of the imprecise probabilistic graph ( , F ), we have

1 2 ⇔ 1/ 2 > 1.
Notice that the order given by is partial since we may have 1 2 and 2 1 . Given a constant , we are then interested in finding the most probable -partitions of . Let ( ( )) be the set of -partitions of . We define M , = { ∈ ( ( )) | ∈ ( ( )), } the set of non-dominated -partitions under . In the following, we are interested in enumerating every partition of M , . Hence, we define the following problem.

Most probable -partitions ( -MPP) Input

A complete graph and an integer .

Output Enumeration of M , .

Analysis

Computational Complexity

We first show that finding one element of M , is NP-hard, even if = 2 and R P has one element. To do so, we construct in the following way a reduction from the Max Cut [START_REF] Karp | Reducibility among combinatorial problems[END_REF] problem (that aims at finding a spanning bipartite subgraph with a maximum number of edges in a graph ).

Construction 1 Given an instance of Max Cut, we construct an imprecise probabilistic graph ( , P) such that:

• ( ) = ( ),
• for each pair of vertices and , = = 0.1 ( red edges) if ∈ ( ) and, = = 0.5 ( blue edges), otherwise.

The proof idea is that a 2-partition is non-dominated if and only if it contains a minimum number of red edges, and thus its complement graph is a bipartite graph with a maximum number of edges. Hence, we can show the following.

Theorem 1 Let ( , P) be an imprecise probabilitstic graph. Computing any element of M , is NP-hard, even if = 2 and P is a singleton.

Proof Let be an instance of Max Cut and let the graph resulting from Construction 1. First, let be a two 2-partition of M ,2 . Let = | ( ) ∩ ( )| be the number of red edges in . The probability of , under any realisation, is equal to

( ) = 0.5 | ( ¯ ) | • 0.1 • 0.9 | ( ) |-.
Thus, a 2-partition belongs to M ,2 if and only if it contains a minimum number of red edges. Later, we now show that contains a 2-partition with red edges if and only if there is a bipartite subgraph of with | ( )|edges.

• Let be a 2-partition of containing red edges. Notice that ¯ is a bipartite graph and that by duality its contains a | ( )|red edges. Hence, since the red edges correspond to the edges of , the graph defined by ( ) = ( ) and ( )

= ( ¯ ) ∩ ( ) contains | ( ) -| edges.
• Let be a bipartite subgraph of containing | ( )|edges. Let and be the bipartition of . Let be the 2-partition of such that

= [ ] ∪ [ ].
The number of red edges in is equal to .

Hence, computing a non-dominated 2-partition of is equivalent to compute an optimal solution for Max Cut.

Easy cases

In this section we present three easy cases in which some element of -MPP can be polynomially computed in the size of graph. These easy cases appear when one value appears in every probabilistic interval of P. The first case is when 0.5 is contained in every probabilistic interval which implies that any -partition is non-dominated.

Theorem 2 Let ( , P) be an imprecise probabilistic graph such that ∀ ∈ ( ), 0.5 ∈ P ( ). We have M , = ( ).

Proof Let be the probability realisation of P such that ( ) = 0.5 for any edge . Notice that for any -partition we have ( ) = 0.5 | ( ) | . Hence, there is a probabilistic realisation for which all -partitions have the same probability and therefore, any -partition is non-dominated.

The second case is when a value inferior to 0.5 is contained in every probabilistic interval. In that case, every -partition that contains a minimum number of edges (i.e., is balanced) is non-dominated.

Theorem 3 Let < 0.5 and ( , P) be an imprecise probabilistic graph such that ∀ ∈ ( ), ∈ P ( ). Let be a -partition of with connected components { 1 , . . . , } of respective orders 1 , . . . , . If we have

∀ , , | -| ≤ 1 then, ∈ M , .
Proof Let be the probability realisation of P such that ( ) = for any edge . First, note that for any -partition of we have

( ) = | ( ) | • (1 -) ( )-| ( ) | . Hence, since < 0.5, is more probable under if | ( )| is minimum. Toward a contradiction,
| ( )| -| ( )| = | ( )| -| ( \ { })| + | ( )| -| ( ∪ { })| | ( )| -| ( )| = | | -1 -| | | ( )| -| ( )| > 1.
Thus, is not a -partition with a minimum number of edges. Further, let be a -partition of with connected components { 1 , . . . , } of respective orders 1 , . . . , and such that ∀ , , | -| ≤ 1. Since has a minimum number of edges, is non-dominated under and thus, it belongs M , .

Finally, the last case is when a value greater to 0.5 is contained in every probabilistic interval. In that case, every -partition that contains a maximum number of edges (i.e., is unbalanced) is non-dominated. Proof Let be the probability realisation of P such that ( ) = for any edge . First, note that for any -partition of we have

( ) = | ( ) | • (1 -) ( )-| ( ) | . Hence, since < 0.5, is more probable under if | ( )| is maximum. A -partition

Heuristic

In this section, we describe some heuristic method used to approach M , or to improve the computation time. This method relies on the use of a pattern and some associated reductions rules.

Pattern and Reduction Rules

Let ( , F ) be an imprecise probabilistic graph. A pattern of is a subset of edges. We say that a -partition respects a pattern if contains every edge of (i.e. ⊂ ( )). We denote ( ( ), ) the set of -partitions that respects . Let M , ( ) = { ∈ ( ( ), ) | ∈ ( ( ), ), } the set of non-dominated -partitions respecting . We give some reduction rules that reduce the size of without altering the computation of M , ( ).

Let be an edge of and be any vertex. Note that for any -partition ∈ ( ( ), ), and are contained in the same clique and contains either both and or none of them. Hence, and are acting like a single vertex and thus, we can contract into a single vertex and merge and together. Formally, the contraction of , denoted , is the application which given any graph , constructs the graph where:

• ( ) = ( ( ) \ { }) ∪ { }, • ( ) = ( ( ) \ { | ∀ ∈ ( ), ∩ ≠ ∅}) ∪ { | ∀ ∈ ( ) \ { }}.
The contraction rule uses and adapts the imprecise probability set and the pattern so that the sets of non-dominated -partitions respecting the pattern are equivalent in the original graph and the newly created graph.

Rule 1 (Contraction rule)

Let ( , F ) be an imprecise probabilistic graph and let = ( , ) be a pattern. Let be an edge of . We reduce to the following imprecise probabilistic graph ( , G).

• = ( ),
• for any edge of ( ) such that ∩ = ∅, we set G( ) = F ( ), and • for any vertex ∉ of ( ), we set

G( ) = [ • • + (1 - ) • (1 - ) , ¯ • ¯ ¯ • ¯ + (1 -¯ ) • (1 -¯ ) ].
This corresponds to compute bounds over the conditional probability ( ∧ |( ∧ ) ∨ (¬ ∧ ¬ )). We construct a new pattern for as follows.

• Let = { | ∈ , ∩ ≠ ∅} and = { | ∃ ∈ , ∈ }. We set = ( \ ) ∪ .
An example of the application of Rule 1 is depicted in Figure 1. The two next properties show that Rule 1 is safe, that is, the computation of M , ( ) is equivalent to the computation of M , ( ).

Property 2 is a bijection from ( ( ), ) to ( ( ), ).

Proof First, we show that for any ∈ ( ( ), ), we have ( ) ∈ ( ( ), ). Let = ( ). Let be the clique containing (which exists since ∈ ). Since contracting an edge in a clique leads to another Further, we show that is surjective. Let be any -partition of ( ( ), ). Let be the clique containing . Since splitting a vertex in two in a clique leads to another clique, then -1 ( ) is also a clique. Moreover, since any other connected component remains unchanged by -1 , then = -1 ( ) is a -partition of ( , F ) that contains . For any vertex ∈ and for any edge , in \ { } (resp.

), since ∈ (resp. ∈ ) then the vertex belongs (resp. does not belong) to -1 ( ) and thus ∈ ( ) (resp. ∉ ( )). Moreover, since \ ⊆ (resp. \ ⊆ ), any edge ∈ \ (resp. ∈ \ ) belongs to (resp. does not belong to) ( ) and since is not altered by -1 , we have ∈ ( ) (resp.

∉ ( )). Hence, ⊆ ( ) and ∩ ( ) = ∅, that is, is a -partition that respects .

Finally, we show that is injective. Let 1 and 2 be two -partitions of ( ( ), ). Let be an edge such that ∈ ( 1 ) and ∉ ( 2 ). If ∩ = ∅, then is not altered by and thus, ∈ ( ( 1 )) and ∉ (

( 2 )). Otherwise, without loss of generality, suppose that ∉ . Since ∈ , , and belong to the same clique in 1 and there is a clique in ( 1 ) that contains and . Moreover, , are not in the same clique as in 2 , and thus, is not in the same clique as in ( 2 ). Hence, we have

( 1 ) ≠ ( 2 ).
Property 3 Given two -partitions 1 and 2 in ( ( ), ) we have

1 2 ⇔ ( 1 ) ( 2 ).
Proof Let = ( , ) be a pattern of ( , F ) and let 1 and 2 be two kpartitions in ( ( ), ). Let 1 and 2 be the cliques containing in 1

Numerical Experiments

In the following, we provide some tests for the special case where = 2.

Dataset

For our tests, we use two types of dataset, one using some real data and one using some generated instances.

Real dataset: we use the dataset used by [START_REF] Arinik | Signed graph analysis for the interpretation of voting behavior[END_REF] that contains vote information for French and Italian members of the european parlement. Each member is represented by a vertex in the graph. To generate the imprecise probability sets, we use the following formula. Let and be two members. Let be the number of sessions in which both and participated and let be the number of sessions in which and voted the same. We set P ( )

= [ + , + + ]
where is a parameter settling the speed at which the intervals converge to a precise value. In the following, we set = 5. Since the generated graph contains 870 vertices, it is not possible to compute exactly the set of non-dominated 2-partitions, we create twenty subinstances by randomly drawing 15 vertices of the original graph.

Randomly Generated Instances: we proceed as follows. First, we define groups of vertices with a given size and an application : {1, . . . , } 2 ↦ → [0, 1] 4 which associate to each pair of integers { , } a tuple { , , ¯ , , ℓ , , l , }. Then for each pair of vertices and such that belongs to the group and belongs to the group ( can be equal to ), we draw two real numbers ∈ [ , , ¯ , ] and ℓ ∈ [ℓ , , l , ]. Finally, we introduce the edge with the imprecise probabilistic interval F ( ) = [ (0,ℓ),

(1, + ℓ)]. We test two differents groups configurations.

• Configuration A. The graph contains two groups of 7 vertices, and we set

(1, 1) = (2, 2) = {0.9, 0.95, 0, 0.3} and (1, 2) = {0.1, 0.2, 0, 0.3}. • Configuration B. The graph contains three groups of 6 vertices, and we set

(1, 1) = (2, 2) = (3, 3) = {0.9, 0.95, 0, 0.1} and (1, 2) = {0.1, 0.2, 0, 0.1}. For the values of (1, 3) and (2, 3), we test three differents variations.

-B1: (1, 3) = (2, 3) = {0.45, 0.55, 0, 0.1}, -B2: (1, 3) = (2, 3) = {0.45, 0.55, 0.2, 0.0.35}, -B3: (1, 3) = (2, 3) = {0.45, 0.55, 0.3, 0.7}.

For each configuration and each variation, we generate twenty instances.

Results

The tests were run on a personal laptop with 16Go of RAM and with an Intel Core 7 processor 2.5GHz. Results are displayed in Table 1. In our tests, we compare two exacts algorithms with our heuristic with two different values of . The "brute" version enumerate every 2-partitions to construct the solution set . For each enumerated 2-partition , if is not dominated by another 2-partition of , then is added to and every 2-partition of that is dominated by is removed from . The "init" version does the same thing but is initialized by a set of 2-partitions. To initialize , we take the value returned by Algorithm 1 with = 1. The idea behind the "init" version is that initializing with a set of possibly non-dominated solutions can reduce computational time (similar ideas can be found in [START_REF] Nakharutai | Improving and benchmarking of algorithms for decision making with lower previsions[END_REF]).For every configuration, the results correspond to the average of the twenty instances.

Table 1 Results on real and generated data for the 2-MPP problem. The columns "Brute" and "Init" correspond to exact algorithms. The columns "t=1" and "t=2" correspond to Algorihm 1 with two different values of . "Sol" is the size of the enumerated 2-partitions, " " is the size of the graph after the application of the reduction rules. "ER1" is the percentage of enumerated 2-partitions that do not belong to M , . "ER2" is the percentage of 2-partitions that belong to M , and that are not enumerated. We can see for the generated instances every 2-partition enumerated by the heuristic belongs to the exact solution. However, the number of 2-partitions returned by the heuristic can be relatively small compared to the size of M , . For example, for the B3 configuration, 97% of M , is not enumerated by the heuristic. Nevertheless, the results of 1 help to drastically reduce the computation time of the exact algorithm. For instances from real data, the results are more mixed: almost all of M , is not enumerated by the heuristic and at least 30% of the 2-partitions returned by the heuristic does not belong to M , . Moreover, since the results of the heuristic are not good enough, the computation time is not significantly reduced for the "init" version. We can explain this bad performance by the fact that drawing randomly 15 vertices in a real instance can lead to a subinstance that is not really representative since the 15 vertices can belong to the same group.

Conclusion

In this paper, we adressed the problem of the most probable -partition with imprecise probabilistic edges. After some theoritical results, we developed a heuristic to tackle this problem. We show that this heuristic can have good results in practice but becomes less performant if the probability intervals are to large. A natural perspective of our work can be to find another way to compute some -partitions to make the initialisation for the exact version, since we show that it can significantly reduce the computation time. It can be interesting to find another method since our heuristic can not perform well for some instances.

Theorem 4

 4 Let > 0.5 and ( , P) be an imprecise probabilistic graph such that ∀ ∈ ( ), ∈ P ( ). Let be a -partition of with connected components { 1 , . . . , } such that ∀ < , | | ≤ | |. If we have 1. | | = 1, ∀ < , and 2. | | = | ( )| -+ 1. then, ∈ M , .

Fig. 1

 1 Fig.1Example of an application of Rule 1 on the edge in an imprecise probabilistic graph with a motif (blue edges).

  has a maximum number of edges if and only if every clique but one is constitued of one vertex, that is, if it respects ( ) and ( ). Let be such -partition. Since is non-dominated under , it belongs to M , .

  Time is given in seconds.

	Config	Brute	Init	t=1			t=2
		Time Sol Time Time n Sol ER1 ER2 Time n Sol ER1 ER2
	A	15.5	1	0.36 10 -3 9.55 1 0%	0%	10 -5 4.3 2	0%	0%
	B1	1.8	2	3	10 -3 6.25 2 0%	0%	10 -5 3.05 2	0%	0%
	B2	296	2.7	3.05 10 -3 6.4 2 0% 17.2% 10 -5 3	2	0% 17.2%
	B3	5017 71.35 34.9 10 -4 6.55 2.7 0% 97%	10 -5 3	2	0% 97%
	Real	29 827.35 28.5 10 -3 6.9 9.15 30% 99.25% 10 -5 3.7 2.15 37.5% 99.5%

A complete graph is a simple graph where every pair of vertices is connected.

Acknowledgements This work was funded in the framework of the Labex MS2T. It was supported by the French Government, through the program "Investments for the future" managed by the ANR (Reference ANR-11-IDEX-0004-02).

and 2 , respectively (which exist since ∈ ). If 1 = 2 then, 1 / 2 = 1. Since any edge that does not belong to 1 or 2 are not altered by , we have 1/ 2 = ( 1 ) / ( 2 ). Thus, 1 2 ⇔ ( 1 ) ( 2 ). Now, suppose that 1 ≠ 2 . For any edge such that ∈ ( 1 ) and ∉

( 2 ), we have { , } ⊆ ( 1 ) and { , } ∩ ( 2 ) = ∅. We have

Samewise, for any edge such that ∉ ( 1 ) and

Hence, since any other edge in 1 or 2 is not altered by , we have

Algorithm Description

Our method to approach M , is described by Algorithm 1. The basic idea is to reduce the size of the graph by computing a pattern and applying the reduction rules described above. Once the size of the reduced graph is small enough, it seems possible to enumerate every -partitions and thus compute M , ( ) in a relatively small amount of time. The difficulty of this method is to find a pattern such that |M , ( )ΔM , | is minimum. In the next section, we take the pattern = { | ≥ 0.9}.

Algorithm 1: Heuristic method

Data: An imprecise probabilistic graph ( , F) and two integers and .

Result: A set of -partitions for .