Séminaire Lotharingien de Combinatoire 54 (2006), Article B54k

TRANSITIVE HALL SETS

GÉRARD DUCHAMP, MARIANNE FLOURET AND JEAN-GABRIEL LUQUE

Dedicated to Xavier Viennot

Abstract. We give the definition of Lazard and Hall sets in the context of transitive factorizations of free monoids. The equivalence of the two properties is proved. This allows to build new effective bases of free partially commutative Lie algebras. The commutation graphs for which such sets exist are completely characterized and we explicit, in this context, the classical PBW rewriting process.

1. Introduction

Since the pioneering works of Schützenberger [27, 28] and Viennot [30] it has been believed (and hoped) that the correct dictionary between (discrete) monoids and (discrete) Lie algebras could be obtained through the correspondence between multiplicative factorizations of monoids and additive factorizations of Lie algebras.

On the other hand, one observes that elimination processes in discrete Lie algebras give free factors as for the Knizhnik-Zamolodchikov Lie algebra (see [1] eq. 4.9 and [15]) and partially commutative Lie algebras through a scheme (LA = Lie Algebra)

LA_{1} in the class C=Free LA ⊕ LA_{2} in the class C

with increasing degree indices so that the process could be applied to obtain bases (and, indeed in the case of Free Lie algebras, all homogeneous ones, including Hall). This observation has led to believe that the free factors could be the right way to generalize Hall processes.

One must mention here that the contribution of Viennot himself to the subject is twofold. First to the factorizations of monoids, the subject of Viennot’s “Thèse d’État” [29]. In this impressive memoir, Viennot proposes a classification of the factorizations of the free monoid and constructs a very interesting category, the bascules (a reconstrution of the effect of the factorization “from outside”), endowed with two functors L and K⟨?⟩, respectively toward the category of K-Lie algebras and to the category of K-associative algebras with unit. The

2 GÉRARD DUCHAMP, MARIANNE FLOURET AND JEAN-GABRIEL LUQUE

second, and not least, contribution is the model of heaps [31] which provides a geometric insight for the partially commutative monoid [2]. This model allows also to introduce a thickness parameter for the pieces [14, 21].

In this paper, we want to show that the framework of factorization with free factors can be broaden, following the track of the “transitive factorizations”. We show that the category of partially commutative structures [8, 9, 11] can be used for getting a correct generalization of Hall rewriting techniques as they appear in the works of Reutenauer and Mélançon [26, 22, 23, 24]. Our construction here, although it works for a wider category of algebras is valid for only some types of graphs.

The insight of heaps, by means of the “pyramids” which are the exact counterpart of the elements of the Lazard code obtained by eliminating some variables (letters of the alphabet) has been worked out by Lalonde and Krob. They can be found in [19, 17, 18].

The structure of the paper is the following. In section (2), we give a partially commutative version of Schützenberger ’s factorization theorem. We introduce in Section (3) the notions of transitive Lazard and transitive Hall sets in the free algebras of trees. Transitive Lazard sets are defined by means of iterations of transitive bisections [11]. Transitive Hall sets classically use a description of the total order of the factorization which, here, must be compatible with the commutations. We prove that the two notions coincide and allow the construction of bases of the free partially commutative Lie algebra L(A, θ) as well as a natural Poincaré-Birkhoff-Witt rewriting process (PBW).

2. Factorizations of a trace monoid

Let A be an alphabet and θ ∈ A×A−{(a, a)|a ∈ A} be a symmetric relation. We will denote by 𝕄(A, θ) a trace monoid (or a free partially commutative monoid) over the alphabet A and whose commutations are defined by ab = ba when (a, b) ∈ θ. The only way to get the equality

(1)  \underline{𝕄(A, θ)} = \underline{a^{∗}}.\underline{𝕄(X, θ_{X})}

where X is a subset of 𝕄(A, θ), a^{∗} is the free monoid of the alphabet \{a\} and \underline{E} = ∑_{e∈E} e, is to impose for each pair of letters (z_{1}, z_{2}) ∈ θ ∩ (A − a)^{2} the commutation (z_{1}, a) ∈ θ or (z_{2}, a) ∈ θ. It is a direct consequence of the transitive factorization theorem (see Section (3.3) [11]).

More generally, an ordered family (M_{i})_{i∈I} of submonoids of M is said to be a factorization if the product mapping ∐_{i∈I} M_{i} → M is one to one. For |I| = 2, one gets the notion of a bisection related to the flip-flop^{1} Lie-algebra by Viennot [30]. At the other end, when all the M_{i} have a single generator, one obtains a complete factorization whose generating series is equal to the Hilbert series of the Free Lie algebra. It has been shown in [8] that this property stills holds in the case of partial commutations and the link between the Lyndon basis and Lazard elimination in this context has been elucidated [16]. In this paper, we use this property to define transitive Lazard sets for a family of trace monoids. Let us first show some properties about conjugacy.

2.1. Roots of conjugacy classes. Let m ∈ 𝕄(A, θ). It is shown in [10] (see also [7]) that the equation u = t^{p} (p ≥ 1) has at most one solution. When it exists, this solution will be denoted by ^{p}\sqrt{u}. In the same paper [10], it is shown that if g, r, and t are three traces such that g = r^{q} = t^{p} with q, p ∈ ℕ then there exists a trace g′ and m ∈ lcm(p, q)ℕ such that g = g^{′m}. Hence, one defines the root \sqrt{g} of a trace g as the smallest trace g′ satisfying g = g^{′m} (the integer m will be called the exponent of g, we denote m = ex(g)).

Example 2.1. Let us consider the commutation graph

(A, θ) = a − c − b

we have \sqrt{babcac} = bac and ex(babcac) = 2

We recall here the definition of conjugacy due to Duboc and Choffrut [4]. Two traces t and t′ are said conjugate if there exists a trace u such that tu = ut′. Conjugacy is an equivalence relation which, in turn, is no more that the restriction to 𝕄(A, θ) of the conjugacy relation for the group 𝔽(A, θ). Exponent and root are invariant under conjugacy in the following sense.

Proposition 2.2. Let C be a conjugacy class, f ∈ C, g ∈ 𝕄(A, θ) and p ∈ ℕ be such that f = g^{p}. For each f′ ∈ C, there exists g′ ∈ 𝕄(A, θ) such that f′ = g^{′p}. Furthermore g and g′ are conjugate.

As a consequence of Proposition (2.2) the root \sqrt{C} of a conjugacy class C is uniquely defined as the set \sqrt{C} = \{\sqrt{g}\}_{g∈C}.

2.2. Schützenberger’s factorization theorem for traces. It is classical that a submonoid 𝕄 of 𝕄(A, θ) has a unique minimal generating set. Hence, a factorization will be characterized by the family of the generating sets of its components and will be denoted by 𝔽 = (Y_{i})_{i∈I} instead of 𝔽 = (𝕄_{i})_{i∈I} if Y_{i} = 𝕄_{i} − 𝕄_{i}^{2}.

1In french ”bascule”.

The existence of the root of conjugacy classes allows us to extend Schützenberger’s factorization theorem [27] to trace monoids.

Theorem 2.3. Let 𝔽 = (Y_{i})_{i∈J} be an ordered family of noncommutative subsets (i.e., for each i and each pair (x, y) ∈ Y_{i}^{2}, x ≠ y implies xy ≠ yx) of 𝕄(A, θ) and ⟨Y_{i}⟩ the submonoid generated by Y_{i}. We consider the following assertions:

(1) The mapping prod is into.

(2) The mapping prod is onto.

(3) Each monoid ⟨Y_{i}⟩ is free. For each conjugacy class C in 𝕄(A, θ), if C is connected (i.e., if the restriction of the noncommutation graph to the alphabet Alph(C) = {a ∈ A|uav ∈ C with u, v ∈ 𝕄(A, θ)} is a connected graph) then there exists a unique i ∈ J such that C ∩ ⟨Y_{i}⟩ ≠ ∅ and in this case C ∩ ⟨Y_{i}⟩ is a conjugacy class of ⟨Y_{i}⟩. If C is not connected, for each i ∈ J, C ∩⟨Y_{i}⟩ = ∅.

Two of the previous assertions imply the third.

Proof. The structure of the proof is, in the broad outline, the same as in [27]. Nevertheless, due to the specificity of the partially commutative context, numerous technical arguments are more sophisticated.

Without restriction, one supposes that each Y_{i} is a minimal generating set of ⟨Y_{i}⟩.

We prove 1) and 2) imply 3) by examining the series

(2)  log \underline{𝕄(A, θ)} − ∑ log \underline{⟨Y_{i}⟩}.

Observing that 1) and 2) force the set 𝔽 to be a factorization, it is easy to show that (2) is a Lie series whose valuation is strictly greater than 1. Hence, if C is a conjugacy class of 𝕄(A, θ), one has

(3)  (\underline{C}, ∑ log \underline{⟨Y_{i}⟩}) = (\underline{C}, ∑_{l∈Ly(A,θ)} log \frac{1}{1 − l})

where Ly(A, θ) denotes the set of Lyndon traces (which is a complete factorization of 𝕄(A, θ) for the standard order [17, 18, 19]) and ( , ) is the scalar product for which the monomials are orthonormal. Lalonde has proved [17] that Ly(A, θ) is a representative set of the strongly connected conjugacy classes.

If C is not connected (3) implies

(\underline{C}, ∑_{i} ∑_{m} \frac{1}{m}\underline{Y_{i}^{m}}) = (\underline{C}, ∑_{l} ∑_{m} \frac{1}{m}l^{m}) = 0

and, the series ∑_{i} ∑_{m} \frac{1}{m} \underline{Y_{i}^{m}} being positive, one gets ⟨Y_{i}⟩ ∩ C = ∅.

If C is strongly primitive (i.e., C is connected and \sqrt{C} = C), equality (3) implies

(\underline{C}, ∑_{i} ∑_{m} \frac{1}{m}\underline{Y_{i}^{m}}) = 1.

Let i and m be such that C ∩ Y_{i}^{m} ≠ ∅. The strong primitivity of \underline{C} implies

(\underline{C}, ∑_{i} ∑_{m} \frac{1}{m}\underline{Y_{i}^{m}}) ≥ 1

and the uniqueness of Y_{i} follows. Furthermore, by Card C ∩ Y_{i}^{m} = m, we show that C ∩ Y_{i}^{m} is a conjugacy class in ⟨Y_{i}⟩.

Now, suppose that C is connected but not primitive and let p > 1 such that C = \{g^{p}/g ∈ \sqrt{C}\}. Let Y_{i} such that \sqrt{C} ∩ ⟨Y_{i}⟩ ≠ ∅ is a conjugacy class in ⟨Y_{i}⟩ (from the previous case, Y_{i} exists and is unique). One has C ∩ ⟨Y_{i}⟩ = C_{j} where each C_{j} is a conjugacy class in ⟨Y_{i}⟩. But for each j,

(\underline{C_{j}}, ∑_{m} \frac{1}{m}\underline{Y_{i}}^{m}) = \frac{1}{p}

and from (3) one has

(\underline{C}, ∑_{m} \frac{1}{m}\underline{Y_{i}}^{m}) = \frac{1}{p}.

The uniqueness of Y_{i} and C_{j} follows.

In order to prove that 1) (resp. 2)) and 3) imply 2) (resp. 1)), one considers a conjugacy class C of 𝕄(A, θ). We need to examine two cases. If C is connected, assertion 3) implies that there exists a unique i and a unique conjugacy class C_{i} of the monoid ⟨Y_{i}⟩ verifying C_{i} = C ∩ ⟨Y_{i}⟩. Let p be the exponent of C and p_{i} the exponent of C_{i} in ⟨Y_{i}⟩. The monoid ⟨Y_{i}⟩ being a submonoid of 𝕄(A, θ), one has immediately p ≥ p_{i}. On the other hand, let j such that \sqrt{C} ∩ ⟨Y_{j}⟩ = C_{j} ≠ 0 where C_{j} is a conjugacy class of the monoid ⟨Y_{j}⟩. Hence, for each w ∈ C_{j}, w^{p} ∈ C. This implies C ∩ ⟨Y_{j}⟩ ≠ 0 and, by assertion 3), i = j. It follows p ≤ p_{i} and then p = p_{i}.

Now, each ⟨Y_{j}⟩ being free with generator Y_{j}, assertion 3) gives

(\underline{C}, ∑_{j∈J} ∑_{m≥1} \frac{1}{m}\underline{Y_{j}^{m}}) = (\underline{C_{i}}, ∑_{m≥1} \frac{1}{m}\underline{Y_{i}^{m}}) = \frac{1}{p_{i}} = \frac{1}{p}.

But, according to Lalonde [17], one has

(\underline{C}, log 𝕄(A, θ)) = (\underline{C}, ∑_{l∈Ly(A,θ)} ∑_{m} \frac{1}{m}l^{m}) = \frac{1}{p}.

Hence

(4)  (\underline{C}, ∑_{j∈J} ∑_{m≥1} \frac{1}{m}\underline{Y_{j}^{m}}) = (\underline{C}, log 𝕄(A, θ)) .

Now, if C is not connected, by assertion 3), one has again

(5)  (\underline{C}, ∑_{j∈J} ∑_{m≥1} \frac{1}{m}\underline{Y_{j}^{m}}) = 0 = (\underline{C}, log 𝕄(A, θ)) .

Let ϕ be the natural morphism from 𝕄(A, θ) in the totaly commutative monoid 𝕄_{A} = 𝕄(A, A×A−Δ) ∼ ℕ^{A}. For each x ∈ 𝕄_{A}, the set ϕ^{−1}(x) is an union of conjugacy classes and by (4) and (5) one obtains

(6)  (\underline{ϕ^{−1}(x)}, log(𝕄(A, θ)) = (\underline{ϕ^{−1}(x)}, ∑_{j∈J} ∑_{m≥1} \frac{1}{m}\underline{Y_{j}^{m}}) .

The morphism ϕ can be extend to a unique morphism of algebra from the algebra of partially commutative formal series ℚ⟨⟨A, θ⟩⟩ onto the algebra commutative series ℚ[[A]], by ϕ(S) = ∑_{x} (\underline{ϕ^{−1}(x)}, S) x. From

(6), one obtains

ϕ (log(\underline{𝕄(A, θ)})) = ϕ (∑_{j∈J} ∑_{m≥1} \frac{1}{m}\underline{Y_{j}^{m}}) .

The continuity of ϕ implies

log (ϕ(\underline{𝕄(A, θ)})) = log (∏_{i∈J} ϕ(\underline{⟨Y_{j}⟩})) .

and

(7)  ϕ(\underline{𝕄(A, θ)}) = ∏_{i∈J} ϕ(\underline{⟨Y_{j}⟩}).

By Assertion 1) or 2), there exists a series S ∈ ℚ_{+}⟨⟨A, θ⟩⟩ verifying

(8)  \underline{𝕄(A, θ)} = ∏_{i∈J} ϕ(\underline{⟨Y_{j}⟩}) ± S

Applying ϕ to (8) and comparing with (7), one proves that ϕ(S) is zero. The positivity of the coefficient of S implies S = 0 and our result. □

Denote by Cont(𝔽) = ⋃_{i∈J} Y_{i} the contents of the factorization 𝔽 = (Y_{i})_{i∈I}. The following result is an extension of a classical result due to Schützenberger [27].

Corollary 2.4. Let 𝔽 be a complete factorization of 𝕄(A, θ) (i.e., each Y_{i} is a singleton). Then for each conjugacy class C we have

Card(C ∩ Cont(𝔽)) = \{ \begin{matrix}1 & if C is strongly connected \\ & (i.e., C is connected and \sqrt{C} = C), \\ 0 & otherwise. \end{matrix}

Hence, complete factorizations of 𝕄(A, θ) receive the same combinatorics than in the free case. In particular, one recovers that the generating series of a complete factorization is equal to the Hilbert series of the free partially commutative Lie algebra.

3. Transitive Lazard sets

3.1. Complete elimination strings and transitive Lazard sets. Let M(2, A) be the free magma on A whose product will be denoted by (., .) (i.e., the set of binary trees with leaves in A endowed with the natural non associative product). The canonical morphism M(2, A) → 𝕄(A, θ) which is identical on A will be called the foliage morphism and denoted by f as in [26]. Observe that θ_{𝕄} = {(w, w′)|ww′ = w′w and Alph(w)∩Alph(w′) = ∅} is a commutation relation on 𝕄(A, θ) ([11]).

We consider a commutation alphabet (A, θ) and some graphs whose vertices belong to M(2, A) and such that (t_{1}, t_{2}) is an edge if and only if (f(t_{1}), f(t_{2})) ∈ θ_{𝕄}.

Let G = (V, E) be such a graph, we call an Elimination String (ES) in G a n-uple of vertices (a_{1}, ⋯, a_{n}) such that for each i ∈ [1, n] and v_{1}, v_{2} ∈ V − {a_{1}, ⋯, a_{i}}

(9)  (v_{1}, v_{2}) ∈ E ⇒ (v_{1}, a_{i}) ∈ E or (v_{2}, a_{i}) ∈ E

The vertex a_{1} will be called the starting point of the ES.

An ES (a_{1}, ⋯, a_{n}) will be called complete (CES in the sequel) if V = {a_{1}, ⋯, a_{n}}. A graph admitting a CES will be called type-H graph. We will prove, in the last section, that when the commutation relation is a type-H graph, we can construct analogues of Hall sets for trace monoids.

In the sequel, we will denote by M(2, A)^{≤n} the set of trees with fewer than n leaves.

Example 3.1. (1) Let us consider the following graph

(A, θ) = \begin{matrix}a & − & d & − & e \\ | & & | \\ b & − & c \end{matrix}

the family (a, d, b, c, e) is a CES of (A, θ) and then it is a type H graph.

(2) The graph

(A, θ) = \begin{matrix}a & − & b \\ c & − & d \end{matrix}

is not a type-H graph.

Type-H graphs admits a nicer graph-theoretic characterization.

Proposition 3.2. A graph is a type-H graph if and only if each of its induced subgraphs^{2} contains at most one connected component of with two vertices.

Proof. Let G = (V, E) such that each of its (induced) subgraphs contains at most one connected component with two vertices. We prove by induction on the cardinality of V that G admits a CES. If Card(V) = 1, the result is straightforward. Suppose now Card(V) > 1. Our strategy consists in proving the existence of a starting point of the ES in G. Suppose that such a vertex does not exist: for each vertex a, there exist b, c ≠ a such that (b, c) ∈ E and (a, b), (a, c) ∉ E. Let a, b, c such vertices. There exists a pair (d, e) verifying d, e ≠ b, (d, e) ∈ E and (d, b), (b, d) ∉ E. Hence, the subgraph generated by the vertices {b, c, d, e} is the union of connected components with two vertices. This contradicts our hypothesis on G and proves that there exists a vertex a ∈ V, such that for each (b, c) ∈ E, (b, a) ∈ E pr (c, a) ∈ E. Now, the subgraph of G generated by V \ {a} is such that each of its subgraph contains at most one connected component with two vertices. Hence, by induction, it has a CES, s = (a_{1}, …, a_{n}). It is easy to see that the sequence (a_{0} = a, a_{1}, …, a_{n}) is a CES of G. This proves that G is a type-H graph.

Conversely, let G be a type-H graph and s = (a_{1}, …, a_{n}) be a CES of G. Suppose that there exists a subgraph G′ of G with two connected components G′_{1} = (V′_{1}, E′_{1}), G′_{2} = (V′_{2}, E′_{2}) with at least two vertices. Let (a_{i}, a_{j}) ∈ E′_{1} ⊂ E and (a_{k}, a_{l}) ∈ E′_{2} ⊂ E. The fact that (a_{i}, a_{k}), (a_{i}, a_{l}), (a_{j}, a_{k}), (a_{j}, a_{l}) ∉ E implies that s is not a CES. □

2An induced subgraph G′ = (V′, E′) of a graph G = (V, E) is a graph such that V′ ⊂ V and E′ = E ∩ (V′ × V′).

According to this characterization, the type-H graphs are rare. Nevertheless, we will prove that it is a sufficient and necessary condition for producing complete factorizations using a Lazard elimination process which preserves the property of ”being a trace monoid” for every factor.

3.2. Transitive Lazard sets. Let v be a vertex of G, the H-star of G for v of rank n > 0 is the graph G_{n}^{∗v} = (V_{n}^{∗v}, E_{n}^{∗v}) defined by (10)

\begin{cases}V_{n}^{∗v} = (V ∩ M(2, A)^{≤n} − v) \\ ∪\{(v′v^{m}) ∈ M(2, A)^{≤n}|m > 0, (v′, v) ∉ E\}, \\ E_{n}^{∗v} = \{(v_{1}, v_{2}) ∈ (V_{n}^{∗})^{2}|(f(v_{1}), f(v_{2})) ∈ θ_{𝕄}\}. \end{cases}

Example 3.3. For the following graph

(A, θ) = a − b − c − d

then

(A_{4}^{∗c}, θ_{4}^{∗c}) = \begin{aligned}& & ac \\ & & | \\ a & − & b & −((a, c), c) & d \\ & & | \\ & & (((a, c), c), c) \end{aligned}

Proposition 3.4. Let G be a type-H graph and a_{1} be the starting point of a CES then G_{n}^{∗a_{1}} is a type-H graph.

Proof. Let λ = (a_{1}, ⋯, a_{m}) be a CES of G. We construct a list Λ of vertices of G_{n}^{∗a_{1}} = (V^{∗}, E^{∗}) removing a_{1} from λ and substituting each a_{i} such that (a_{i}, a_{1}) ∉ E by the sequence

(a_{i}, a_{1}^{m−1}), …, (a_{i}, a_{1}), a_{i}.

Set Λ = (a′_{1}, ⋯, a′_{M}) and suppose that Λ is not a CES, then there exists α < β < γ such that (a′_{β}, a′_{γ}) ∈ E^{∗}, (a′_{α}, a′_{β}) ∉ E^{∗} and (a′_{α}, a′_{γ}) ∉ E^{∗}. If a′_{α} = (a_{i}, a_{1}^{p}), a′_{β} = (a_{j}, a_{1}^{q}) and a′_{γ} = (a_{k}, a_{1}^{r}), then the construction implies i ≤ j < k and p = 0 or q = 0. If i = j then p ≠ 0 which gives (a_{i}, a_{1}) ∉ E and r = 0. Hence, (a_{1}, a_{k}) ∉ E and q = 0. This implies that (a_{i}, a_{k}) ∈ E, (a_{1}, a_{i}) ∉ E and (a_{1}, a_{k}) ∉ E and contradicts the fact that λ is a CES. If i < j, suppose that r = 0 (the case q = 0 is symmetric), we need to examine several cases

(1) If p = 0, then q ≠ 0 (otherwise (a_{i}, a_{j}), (a_{i}, a_{k}) ∉ E and (a_{j}, a_{k}) ∈ E, which contradicts the fact that λ is a CES). But, as (a_{k}, a_{i}) ∉ E, (a_{j}, a_{k}) ∈ E and λ being a CES, one has (a_{i}, a_{j}) ∈ E and hence (a_{1}, a_{i}) ∉ E. Finally (a_{1}, a_{j}) ∉ E, which contradicts the fact that λ is a CES.

(2) If p ≠ 0 and q = 0, then, as λ is a CES, either (a_{i}, a_{j}) ∈ E, either (a_{i}, a_{k}) ∈ E. Suppose that (a_{i}, a_{j}) ∈ E (the other case is symmetric), one has (a_{1}, a_{j}) ∈ E (otherwise (a′_{α}, a′_{β}) ∈ E^{∗}). But, λ being a CES, one gets (a_{1}, a_{k}) ∈ E and by (a′_{α}, a′_{γ}) ∉ E^{∗} one obtains (a_{i}, a_{k}) ∉ E. Finally (a_{1}, a_{j}), (a_{1}, a_{i}) ∉ E and (a_{i}, a_{j}) ∈ E contradicts the fact that λ is a CES.

(3) If p, q ≠ 0 then, as (a′_{γ}, a′_{β}) ∈ E^{∗}, one as (a_{1}, a_{k}) ∈ E and by (a′_{α}, a′_{γ}) ∉ E^{∗}, one obtains (a_{i}, a_{k}) ∉ E. The sequence λ being a CES, (a_{i}, a_{j}) ∈ E. Hence (a_{1}, a_{j}), (a_{1}, a_{i}) ∉ E and (a_{i}, a_{j}) ∈ E contradicts the fact that λ is a CES.

This proves that Λ is a CES. □

The definition of a transitive Lazard set follows:

Definition 3.5. Let G = (A, θ) be a commutation alphabet considered as a graph and L ⊂ M(2, A), we will say that L is a transitive Lazard set if and only if for each n > 0, L ∩ M(2, A)^{≤n} = {s_{1}, ⋯, s_{k}} such that there exist k + 1 graphs G_{1} = (A_{1}, θ_{1}), …, G_{k+1} = (A_{k+1}, θ_{k+1}) satisfying the following conditions:

(1) The first graph G_{1} is equal to G.

(2) The last graph G_{k+1} is empty (i.e., G_{k+1} = (∅, ∅))

(3) The graphs G_{2}, …, G_{k+1} are defined by induction

(a) For each i < k + 1, s_{i} ∈ A_{i} and s_{i} is the starting point of a CES of G_{i}.

(b) We have G_{i+1} = (G_{i})_{n}^{∗s_{i}}.

3.3. Type-H graphs and the transitive factorization theorem. Classicaly, we will denote by L(A, θ) the free partially commutative Lie algebra on the alphabet A for the commutation relation θ. The well known properties of the (noncommutative) Lazard sets hold true and can be seen as consequences of the transitive factorization theorem [11]. We recall it here.

Let (A, θ) be a partially commutative alphabet and B ⊂ A. Then 𝕄(B, θ_{B}) is the left (resp. right) factor of a bisection of 𝕄(A, θ). Explicitly,

\underline{𝕄(A, θ)} = \underline{𝕄(B, θ_{B})}.\underline{⟨β_{Z}(B)⟩}

where ⟨β_{Z}(B)⟩ means the submonoid generated by the set

β_{Z}(B) = {zw/z ∈ Z, w ∈ 𝕄(B, θ_{B}), IA(zw) = {z}}

and IA(t) = {z ∈ A|t = zw} is the initial alphabet of the trace t.

Let B ⊂ A, we say that B is a transitively factorizing subalphabet (TFSA) if and only β_{Z}(B) is a partially commutative code. We prove the following theorem.

Theorem 3.6 (Duchamp–Luque [11]). Let (B, Z) be a partition of A.

(1) The following assertions are equivalent.

(i) The subalphabet B is a TFSA. (ii) The subalphabet B satisfies the following condition.

For each z_{1} ≠ z_{2} ∈ Z and w_{1}, w_{2}, w′_{1}, w′_{2} ∈ 𝕄(A, θ) such that

IA(z_{1}w_{1}) = IA(z_{1}w′_{1}) = {z_{1}}

and

IA(z_{1}w_{2}) = IA(z_{2}w′_{2}) = {z_{2}}

we have

z_{1}w_{1}z_{2}w_{2} = z_{2}w′_{2}z_{1}w′_{1} ⇒ w_{1} = w′_{1}, w_{2} = w′_{2}.

(iii) For each (z, z′) ∈ Z^{2} ∩ θ, the dependence graph (i.e., noncommutation) has no partial graph like

z − b_{1} − ⋯ − b_{n} − z′.

with b_{1}, …, b_{n} ∈ B. We have the decomposition

L(A, θ) = L(B, θ_{B}) ⊕ J

where J is the Lie ideal generated (as a Lie algebra) by

τ_{Z}(B) = {[… [z, b_{1}], … b_{n}] | zb_{1} … b_{n} ∈ β_{Z}(B)}.

Furthermore,

(2) (i) The subalgebra J is a free partially commutative Lie algebra if B is a TFSA of A. (ii) Conversely if J is a free partially commutative Lie algebra with code τ_{Z}(B) then B is a TFSA.

Applying Theorem 3.6 and taking the inductive limit of the process one obtains.

Proposition 3.7. Let L be a transitive Lazard set.

(1) The foliage f(L) is a complete factorization of 𝕄(A, θ).

(2) Let Π be the unique morphism M(2, A) → L(A, θ) such that Π(a) = a for each letter a ∈ A. Then Π(L) is a basis of the Free Lie algebra L(A, θ).

Such a factorization will be called Transitive Lazard Factorization (TLF). Not all the trace monoids possess a TLF. For example, in the graph \begin{matrix}a−b \\ c−d \end{matrix} we can not find a CES. Nevertheless, the property “having a TLF” is decidable as shown by the following result.

Theorem 3.8. A trace monoid admits a TLF if and only if its commutation alphabet is a type-H graph.

Proof. It suffices to observe that a trace monoid has a TLF if and only if one can construct a transitive Lazard set from its commutation graph, which is a consequence of proposition 3.4. □

3.4. An alternative definition for transitive Lazard sets. In order to generalize the correspondance between Hall and Lazard sets, we introduce the notion of F-Lazard sets.

Definition 3.9. Let E be a finite set. A subset S of M(2, A) will be called Local Transitive Complete Elimination relatively to E if and only if, denoting S ∩ E = {s_{i}, …, s_{k}}, there exist k + 1 graphs G_{1} = (A_{1}, θ_{1}),… G_{k+1} = (A_{k+1}, θ_{k+1}) verifying

(1) The initial graph is G_{1} = (A, θ)

(2) The last graph is G_{k+1} = (∅, ∅)

(3) The intermediate graphs are constructed following the two rules

(a) for each i < k + 1, s_{i} ∈ A_{i} and s_{i} is the starting point of a CES of G_{i}.

(b) for each i < k + 1, the commutation graphs G_{i+1} is defined by its alphabet

A_{i+1} = (A_{i} − s_{i}) ∪ {(bc_{i}^{n}) ∈ E|n > 0, ∈ A_{i} and (b, c_{i}) ∉ θ_{i}}

and its commutation rules

θ_{i+1} = θ_{A_{i+1}} := {(t, t′) ∈ A_{i}^{2}|Alph(t) × Alph(t′) ⊂ θ}

Definition 3.10. Let ∅ ⊂ F_{0} ⊂ F_{1} ⊂ ⋯ ⊂ F_{n} ⊂ ⋯ be a filtration of M(2, A). And denote F = (F_{n})_{n∈ℕ}. A set L ⊂ M(2, A) has the F-Lazard property if and only if for each i ∈ ℕ, L is a LTCE of A relatively to F_{i}.

Observe that each transitive Lazard set is a F-Lazard set when F denotes the filtration by degree.

We will say that a filtration F = (F_{i})_{i∈ℕ} of M(2, A) is admissible if and only if each F_{i} is finite and each subtree of an item of F_{i} belongs again in F_{i} (A set having this property is called closed set in [26]). The next result proves that, when F is an admissible filtration, the notion of F-Lazard sets is independent of the choice of the filtration and hence coincides with the notion of transitive Lazard sets.

Lemma 3.11. A set L is a transitive Lazard set if and only if it is a F-Lazard set for an admissible filtration F.

Proof. The ”if” part is straightforward. Let us prove the converse denoting by L a F-Lazard set for an admissible filtration F. We have to prove that L is a LTCE relatively to M(2, A)^{≤n} for each n ≥ 0. We set L ∩ M(2, A)^{≥n} = {s_{1}, …, s_{k}} and p = max{q|L ∩ M(2, A)^{≥n} ⊂ F_{q}}. The set L is a LTCE of A relatively to F_{p}. Hence, if we set L ∩ F_{p} = {r_{1}, …, r_{l}}, one can construct l + 1 graphs G′_{1} = (A′_{1}, θ′_{1}), ⋯, G′_{l+1} = (A′_{l+1}, θ′_{l+1}) according to the definition of F-Lazard sets. Consider the indices i_{1}, …, i_{k} for which s_{j} = r_{i_{j}} and let G_{1} = (A_{1}, θ_{1}), …, G_{k} = (A_{k}, θ_{k}) be the commutation graphs defined by A_{j} = A′_{i_{j}} ∩ M^{≤n} and θ_{j} = θ′_{j} ∩ (A_{j} × A_{j}). Such a sequence of graphs satisfies the items (1)-(3) of the definition of a LTCE relatively to M(2, A)^{≥n}. We conclude that L is a transitive Lazard set. □

As an immediate consequence of Lemma 3.11, one has the following lemma.

Lemma 3.12. A set of trees L is a transitive Lazard set if and only if it is a LTCE of (A, θ) relatively to each closed set.

4. Transitive Hall sets

4.1. A total order on a transitive Lazard set.

Definition 4.1. A Transitive Hall Set (THS) H is a family of trees (h)_{h∈H} endowed with a total order < such that

(1) The family (f(h))_{h∈H} is a complete factorization of 𝕄(A, θ) (for the reverse order).

(2) The set H contains the alphabet A.

(3) If h = (h′, h′′) ∈ H − A then h′′ ∈ H and h < h′′.

(4) If h = (h′, h′′) ∈ M(2, A) − A then h ∈ H if and only if the following four assertions are true:

(a) The two sub-trees h′ and h′′ belong to H.

(b) We have the inequality h′ < h′′.

(c) The foliage of the two sub-trees are not related by the “disjoint commutation” relation (i.e., (f(h′), f(h′′)) ∉ θ_{𝕄}).

(d) Either h′ ∈ A or h′ = (x, y) with y ≥ h′′.

Although no condition on the shape of the graph is apparent in the definition, we will see that part (1) strongly restricts implicitly the possibilities. For example, let us consider the commutation graph

a b − c

and a set H such that

\begin{aligned}H ∩ M(2, A)^{≤3} & = & \{a, (b, a), ((c, a), a), c, ((c, a), c), (c, a), (b, (c, a)), \\ & & ((b, a), c), b, ((b, a), b), (b, a)\}. \end{aligned}

We suppose that trees above are ordered from the right to the left. Clearly, trees listed here verify axioms (2), (3) and (4) of the definition of transitive Hall sets, but the trace cba admits two decreasing decomposition cba = f(c).f((b, a)) = c.ba = bca = f(b, (c, a)).

As in the free case we have a perfect correspondence between the notions of transitive Hall and Lazard sets.

Theorem 4.2. A set L is a transitive Lazard set if and only if it is a transitive Hall set.

Proof. A slight adaptation of the noncommutative case (see [26]) shows that each transitive Lazard set is a transitive Hall set.

Let us prove the converse. According to Lemma 3.12, it suffices to prove that a transitive Hall set H is a LTCE relatively to any finite closed set E. Let us show it by induction on Card E. If Card E = 1 the result is obvious. Now, we suppose Card E > 1 and set

c = max{h ∈ H ∩ E}

X = {(ac^{n}) ∈ E|a ∈ A − c, n ≥ 0, (a, c) ∈ θ} ∩ {b|(b, c) ∈ θ}

θ_{X} = θ_{𝕄} ∩ X × X
H′ = H ∩ M(2, X)
and E′ = E ∩ M(2, X)

We endow H′ with the restriction to H′ of the total order < on H.

First, we check that H′ is a transitive Hall set for the alphabet (X, θ_{X}).

(1) The family (f_{X}(h))_{h∈H′} is a complete factorization of 𝕄(X, θ_{X}) where f denotes here the natural morphism

M(2, X) → 𝕄(X, θ).

The result follows from the isomorphism between 𝕄(X, θ_{X}) and 𝕄(f_{A}(X), θ_{f_{A}(X)}) and the fact that the (f_{A}(h))_{h∈H} is a complete factorization of 𝕄(A, θ).

(2) The generator set X belongs to H′ (it suffices to observe that X ⊂ H).

(3) If (h′, h′′) ∈ H′, either h′′ = c and in this case h′, (h′, h′′) ∈ X, either h′′ ∈ H′ and as one has h < h′′ in H the same inequality occurs in H′.

(4) If h = (h′, h′′) ∈ H′ − X, then (a) As H′ ∈ M(2, A), h′, h′′ ∈ H′,

(b) the inequality h′ < h′′ follows from H′ ⊂ H,

(c) Suppose that (f_{X}(h′), f_{X}(h′′)) ∈ θ_{X}, this implies (f(h′), f(h′′)) ∈ θ which is in contradiction with h = (h′, h′′) ∈ H′ ⊂ H.

(d) If h′′ ∉ X, then h′′ = (x, y) with x, y ∈ H′ ⊂ H which implies h′ ≤ y (by restriction of < to H′).

Conversely, if we let h = (h′, h′′) ∈ M(2, X) such that h′, h′′ ∈ H′, (f_{X}(h′), f_{X}(h′′)) ∉ θ_{X} and h′ < h′′. If h′′ ∈ A then h ∈ H ∩ M(2, X) = H′. If h′′ ∈ X − A, then h′′ = (x, c) but c > h′ which implies (from the fact that H is a transitive Hall set) h ∈ H. Finally, if h′′ ∈ H′ − X one has h′′ = (x, y) and y ≥ h′ implies h ∈ H.

It follows that H′ is a transitive Hall set over the alphabet (X, θ_{X}). Observe that Card E′ < Card E, hence by induction H′ is a LTCE of (X, θ_{X}) relatively to E′. According to the definition of a LTCE, one sets H′ ∩ E′ = {s1, …, s_{k}} and one constructs the associated graphs G_{1} = (A_{1}, θ_{1}), …, G_{k+1} = (A_{k+1}, θ_{k+1}). If we denote (a_{1}, ⋯, a_{n−1}) the subsequence of the letters of A appearing in (s_{1}, …, s_{k}), then (a_{1}, …, a_{n−1}) is a CES of A − c. The fact that H is a transitive Hall set implies that (c, a_{1}, …, a_{n−1}) is a CES of A. In fact, if we suppose that (c, a_{1}, …, a_{n−1}) is not a CES, then there exist i, j ∈ {1, …, n−1} such that (a_{i}, a_{j}) ∉ θ, (a_{i}, c) ∉ θ and (a_{j}, c) ∉ θ. But (a_{i}, c), (a_{j}, c) ∈ H by definition of H, and a_{i}.a_{j}c = a_{j}.a_{i}c contradicts the first point of the definition of transitive Hall sets. Then (c, a_{1}, ⋯, a_{n−1}) is a CES of G_{0} = (A, θ) and c is its starting point. Furthermore, (A_{0}−c)∪{(ac^{n}) ∈ E|n > 0, a ∈ A and (a, c) ∉ θ} = X = A_{1}. It follows that H is a LTCE of (A, θ) relatively to E with associated graphs G_{0}, G_{1}, ⋯, G_{k+1}. Applying Lemma 3.12, one deduces that H is a transitive Lazard set. □

This correspondence is very useful to construct decomposition algorithms.

4.2. Rewriting process. We can construct standard sequences of Hall trees (h_{1}, ⋯, h_{n}) such that for each i ∈ [1, n] either h_{i} ∈ A, or h_{i} = (h′_{i}, h′′_{i}) with h′′_{i} ≥ h_{i+1}, …, h_{n}. In a standard sequence an ascent is an index i such that h_{i} < h_{i+1} and a legal ascent is an ascent i such that h_{i+1} ≥ h_{i+2}, ⋯, h_{n} (these definitions are due to Schützenberger [28]). Let s be a standard sequence and i a legal ascent. We write s → s′ if s′ = (h_{1}, ⋯, h_{i−1}, (h_{i}, h_{i+1}), h_{i+2}, ⋯, h_{n}) when (f(h_{i}), f(h_{i+1})) ∉ θ_{𝕄} and s′ = (h_{1}, ⋯, h_{i−1}, h_{i+1}, h_{i}, h_{i+2}, ⋯, h_{n}) otherwise. The transitive closure →^{∗} of → is such that for each standard sequence there exists a unique decreasing standard sequence s′ such that s →^{∗} s′. Using this property on a sequence of letters, we obtain an algorithm which allows to find the factorization of a trace in a decreasing concatenation of Hall traces.

Example 4.3. Let us consider the following commutation alphabet:

(A, θ) = a − b − c − d.

and let H be a transitive hall set such that

H ∩ M(2, A)^{≤3} = {c, b, a, (a, c), ((a, c), c), (a, (a, c)), (d, b), ((d, b), b), (d, (b, a)), (d, (a, c)), (d, a), ((d, a), a), (d, (d, b)), (d, (d, a)), d}.

We can compute the factorization of the word bcaccbdbddad in the following way

(b, c, a, c, c, b, d, b, d, d, a, d)
↓
(b, c, a, c, c, b, d, b, d, (d, a), d)
↓
(b, c, a, c, c, b, d, b, (d, (d, a)), d)
↓
(b, c, (a, c), c, b, (d, b), (d, (d, a)), d)
↓
(b, c, ((a, c), c), b, (d, b), (d, (d, a)), d)
↓
(b, c, b, ((a, c), c), (d, b), (d, (d, a)), d)
↓
(c, b, b, ((a, c), c), (d, b), (d, (d, a)), d)

which gives bcaccbdbddad = c.b.b.acc.db.dda.d.

Let s = (h_{1}, ⋯, h_{n}) be a standard sequence and i a legal ascent, we define

(11)  λ_{i}(s) = (h_{1}, …, h_{i−1}, (h_{i}, h_{i+1}), h_{i+2}, …, h_{n})

and

(12)  ρ_{i}(s) = (h_{1}, ⋯, h_{i−1}, h_{i+1}, h_{i}, h_{i+2}, ⋯, h_{n}).

The derivation tree of s is the tree T (s) satisfying the following

(1) if s is a decreasing sequence then T (s) is only the root labeled s

(2) otherwise, we consider the greatest legal ascent i of s. Then

(a) if (h_{i}, h_{i+1}) ∈ θ_{𝕄}, the root of the tree T (s) is s and T (s) has only one subtree T (ρ_{i}(s)).

(b) otherwise, the root of T (s) is s, the left subtree of T (s) is T (λ_{i}(s)) and the right sub-tree of T (s) is T (ρ_{i}(s))

If we denote [s] = [h_{1}] ⋯ [h_{n}], one obtains

(13)  [s] = ∑_{s′∈𝔉(T (s))}[s′]

where 𝔉(T (s)) denotes the set of the leaves of T (s). Applying this equality to sequences of words, one gets an algorithm allowing to decompose a polynomial in the PBW basis associated to a transitive Hall set.

Example 4.4. We use the transitive Hall set defined in the example 4.3. One has for example:

(b, c, a, c, c, b, d) (b, c, c, a, c, b, d) (b, c, c, c, a, b, d) (b, c, c, c, b, a, d) (c, b, c, c, b, a, d) (c, c, b, c, b, a, d) (c, c, c, b, b, a, d) (b, c, c, (a, c), b, d) (b, c, c, b, (a, c), d) (c, b, c, b, (a, c), d) (c, c, b, b, (a, c), d)  (b, c, (a, c), c, b, d) (b, c, c, (a, c), b, d) (b, c, c, b, (a, c), d) (c, b, c, b, (a, c), d) (c, c, b, b, (a, c), d)(b, c, ((a, c), c), b, d) (b, c, b, ((a, c), c), d) (c, c, b, ((a, c), c), d)

which allows us to write

bcaccbd = c.c.c.b.b.a.d + 2c.c.b.b.[a, c].d + c.b.b.[[a, c], c].d.

5. Conclusion

The stable concept of a transitive factorization allows the adaptation of the Hall machinery as it has been here made explicit. The construction is characteristic free. It would be interesting to investigate such constructions in the case of p-commutations [5, 6, 12].

Another effective construction of bases of free partially commutative Lie algebras (Klyachko idempotents) has been obtained recently by F. Patras and C. Reutenauer [25]. Their construction holds without restriction on the commutation rules but is not characteristic free.

Acknowledgments

We thank Christophe Tollu for his assistance.

References

[1] P. Cartier, Développements récents sur les groupes de tresses, applications à la topologie et à l’algèbre, Séminaire Bourbaki, vol. 1989/90, Astérisque, no. 189-190 (1990), Exp. No. 716, pp. 17–67.

[2] P. Cartier, D. Foata, Problèmes combinatoires de commutation et réarrangement, Lect. Notes in Math., vol. 85, 1969.

[3] B. Chandler, W. Magnus, The history of combinatorial group theory: a case study in the theory of ideas. Springer, 1982.

[4] C. Choffrut, Free partially commutative monoids, Technical Report 86, LITP, Université Paris 7, 1986.

[5] N. Dobrynin, G. Duchamp, A. Michalev, V. Petrogradsky On free p-super algebras, Comm. Algebra 28 (2000), 5275–5302.

[6] N. Dobrynin The free color Lie superstructures: elimination of variables, in press.

[7] C. Duboc, Commutations dans les monoïdes libres: un cadre théorique pour l’étude du parallélisme, thesis, Université de Rouen, 1986.

[8] G. Duchamp, D. Krob, The free partially commutative Lie algebra: bases and ranks, Adv. Math. 95 (1992), 92–126.

[9] G. Duchamp, D. Krob, Free partially commutative structures, J. Algebra 156 (1993), 318–361.

[10] G. Duchamp, D. Krob, Partially commutative Magnus transformation, Int. J. Alg. Comp. 3 (1993), 15–41.

[11] G. Duchamp, J.G. Luque, Transitive factorizations of partially commutative free monoids and Lie algebras, Discrete Math. 246 (2002), 83–97.

[12] G. Duchamp, J.G. Luque, Congruences compatible with the shuffle product/, FPSAC’00, Moscow, 2000.

[13] V. Diekert and G. Rozenberg, The book of traces, World Scientific, Singapour, 1995.

[14] S. Gaubert, J. Modeling and analysis of timed petri nets using heaps of pieces, IEEE Trans. Autom. Control 44 (1999), 683–697.

[15] T. Kohno, Linear representations of braid groups and classical Yang-Baxter equations, in: “Braids”, Contemporary Math. 78 (1988), 339–363.

[16] D. Krob and P. Lalonde, Partially commutative Lyndon words, Lect. Notes in Comp. Sci. 665 (1993), 237–246.

[17] P. Lalonde, Bases de Lyndon des algèbres de Lie libres partiellement commutatives, Theoret. Comput. Sci. 117 (1993), 217–226.

[18] P. Lalonde, Lyndon heaps: An analogue of Lyndon words in free partially commutative monoids, Discrete Math. 145 (1995), 171–189.

[19] P. Lalonde, Contribution à l’étude des empilements, thèse de doctorat, LACIM, 1991.

[20] M. Lazard, Groupes anneaux de Lie et problème de Burnside, Inst. Math. de l’Universita Roma, 1960.

[21] J. Mairesse, L. Vuillon, Asymptotic behavior in a heap model with two pieces, Theoret. Comput. Sci. 270 (2002), 525–560.

[22] G. Mélançon, Combinatorics of Hall trees and Hall words, J. Combin. Theory Ser. A 59 (1992), 285–308.

[23] G. Mélançon, C. Reutenauer, Computing Hall Exponents in the Free Group, Int. J. Alg. Comp. 3 (1993), 275–294.

[24] G. Mélançon, Bases of free Lie algebras, “are Lyndon words better ?”, 3rd SIAM Conference on Control and its Applications, Symposium on Combinatorial Methods in Control Theory, Saint-Louis, Missouri, 1995.

[25] F. Patras and C. Reutenauer, On Dynkin and Klyachko idempotents in graded bialgebras, Adv. Appl. Math. 28 (2002), 560–579.

[26] C. Reutenauer, Free Lie algebras, Oxford University Press, New-York, 1993.

[27] M.P. Schützenberger, On a factorization of free monoids, Proc. Amer. Math. Soc. 16 (1965), 21–24.

[28] M.P. Schützenberger, Sur une propriété combinatoire des algèbres de Lie libre pouvant être utilisée dans un problème de Mathématiques appliquées, Seminaire Dubreuil–Pisot Année 1958–1959, Paris, 1958.

[29] G.X. Viennot, Algèbres de Lie libres et monodes libres, Thèse d’Etat, Université Paris 7, 1974.

[30] G. Viennot, Algèbre de Lie libres et Monoïdes Libres, Lecture Notes in Math., vol. 691, 1978.

[31] G.X. Viennot, Heaps of pieces, I: basic definitions and combinatorial lemmas, in: Combinatoire Énumérative, G. Labelle and P. Leroux (eds.), Springer–Verlag, Berlin, 1986, pp. 321–350.