{'fraction_non_alphanumeric': 0.06501323094484512, 'fraction_numerical': 0.010584755876096093, 'mean_word_length': 3.33123595505618, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 36, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The non-symmetric operad pre-Lie is free

We prove that the pre-Lie operad is a free non-symmetric operad.


Introduction
Operads are a specific tool for encoding type of algebras. For instance there are operads encoding associative algebras, commutative and associative algebras, Lie algebras, pre-Lie algebras, dendriform algebras, Poisson algebras and so on. A usual way of describing a type of algebras is by giving the generating operations and the relations among them. For instance a Lie algebra L is a vector space together with a bilinear product, the bracket (the generating operation) satisfying the relations [x, y] = −[y, x] and [x, [y, z]] + [y, [z, x]] + [z, [x, y]] = 0 for all x, y, z ∈ L. The vector space of all operations one can perform on n distinct variables in a Lie algebra is Lie(n), the building block of the symmetric operad Lie. Composition in the operad corresponds to composition of operations. The vector space Lie(n) has a natural action of the symmetric group, so it is a symmetric operad. The case of associative algebras can be considered in two different ways. An associative algebra A is a vector space together with a product satisfying the relation (xy)z = x(yz). The vector space of all operations one can perform on n distinct variables in an associative algebra is As(n), the building block of the symmetric operad As. The vector space As(n) has for basis the symmetric group S n . But, in view of the relation, one can look also at the vector space of all order-preserving operations one can perform on n distinct ordered variables in an associative algebra: this is a vector space of dimension 1 generated by the only operation x 1 · · · x n . So the non-symmetric operad As describing associative algebras is 1-dimensional for each n: this is the terminal object in the category of non-symmetric operads.
Here is the connection between symmetric and non-symmetric operads. A symmetric operad P starts with a graded vector space (P(n)) n≥0 together with an action of the symmetric group S n on P(n) for each n. This data is called a symmetric sequence or an S-module or a vector species. There is a forgetful functor from the category of vector species to the category of graded vector spaces, forgetting the action of the symmetric group. This functor has a left adjoint S which corresponds to tensoring by the regular representation of the symmetric group. A symmetric (non-symmetric) operad is a monoid in the category of vector species (graded vector spaces). Again there is a forgetful functor from the category of symmetric operads to the category of non-symmetric operads admitting a left adjoint S. The symmetric operad As is the image of the non-symmteric operad As by S. It is clear that Lie is not in the image of S since the Jacobi relation does not respect the order of the variables x < y < z nor the anti-symmetry relation. Still one can regard Lie as a non-symmetric operad applying the forgetful functor. Salvatore and Tauraso proved in [5] that the operad Lie is a free non-symmetric operad.
A free non-symmetric operad describes type of algebras which have a set of generating operations and no relations between them. For instance, magmatic algebras are vector spaces together with a bilinear product. There is a well known free nonsymmetric operad, the Stasheff operad, built on Stasheff polytopes, see e.g. [6]. An algebra over the Stasheff operad is a vector space V together with an n-linear product: V ⊗n → V for each n. From the point of view of homotopy theory, the category of operads is a Quillen category and free operads play an essential role in the homotopy category. One wants to replace an operad P by a quasi-free resolution, that is, a morphism of operads Q → P where Q is a free operad endowed with a differential realizing an isomorphism in homology. For instance, a quasi-free resolution of As, in the category of non-symmetric operads, is given by the Stasheff operad. Algebras over this operad are A ∞ -algebras (associative algebras up to homotopy). This gives us the motivation for studying whether a given symmetric operad is free as a non-symmetric operad or not.
In this paper we prove that the operad pre-Lie is a free non-symmetric operad. Pre-Lie algebras are vector spaces together with a bilinear product satisfying the relation (x * y) * z − x * (y * z) = (x * z) * y − x * (z * y). The operad pre-Lie is based on labelled rooted trees which are of combinatorial interest. In the process of proving the main result, we describe another operad denoted T Max also based on rooted trees and having the advantage of being the linearization of an operad in the category of sets. We prove that it is a free non-symmetric operad. The link between the two operads is made via a gradation on labelled rooted trees.

The pre-Lie operad and rooted trees
We first recall the definition of the pre-Lie operad based on labelled rooted trees as in [2]. For n ∈ N * , the set {1, . . . , n} is denoted by [n] and [0] denotes the empty set. The symmetric group on k letters is denoted by S k . There are many equivalent definitions of operads and we refer to [4] for basics on operads. We work over the ground field k and vector spaces are considered over k. Here are the definitions needed for the sequel. Definition 1.1. A (reduced) non-symmetric operad is a graded vector space (P(n)) n≥1 , with a unit 1 ∈ P(1) = k, together with composition maps • i : P(n) ⊗ P(m) → P(n + m − 1) for 1 ≤ i ≤ n satisfying the following relations: for a ∈ P(n), b ∈ P(m) and c ∈ P(ℓ) A non-trivial composition is a composition a • i b with a ∈ P(n), b ∈ P(m) and n, m > 1. If in addition each P (n) is acted on the right by the symmetric group S n and the composition maps are equivariant with respect to this action, then the collection (P(n)) n forms a symmetric operad. An algebra over an operad P is a vector space X endowed with evaluation maps ev n : compatible with the composition maps • i : for p ∈ P(n), q ∈ P(m), x ′ i s ∈ X one has (p • i q)(x 1 , . . . , x n+m−1 ) = p(x 1 . . . , x i−1 , q(x i , . . . , x i+m−1 ), x i+m , . . . , x n+m−1 ).
In the sequel an operad will always mean a reduced operad. Definition 1.2. In this paper we will consider two type of trees: planar rooted trees will represent the composition maps in a non-symmetric operad (see 1.3) and rooted trees will be the objects of our study (see 1.4). Here are the definitions we will use in the sequel.
By a (planar) tree we mean a non empty finite connected contractible (planar) graph. All the trees considered are rooted.
In the planar case some edges (external edges or legs) will have only one adjacent vertex; the other edges are called internal edges. There is a distinguished leg called the root leg. The other legs are called the leaves. The choice of a root induces a natural orientation of the graph from the leaves to the root. Any vertex has incoming edges and only one outgoing edge. The arity of a vertex is the number of incoming edges. A tree with no vertices of arity one is called reduced. A planar rooted tree induces a structure of poset on the vertices, where x < y if and only if there is an oriented path in the tree from y to x. Let x be a vertex of a planar rooted tree T . The full subtree T (x) of T at x is the subtree of T containing all the vertices y > x and all their adjacent edges. The root leg of T (x) is the half edge with adjacent vertex x induced by the unique outgoing edge of x. One represents a planar rooted tree like this: In the abstract case (non-planar trees) every edge is an internal edge. The root vertex will be a distinguished vertex. The choice of a root induces a natural orientation of the graph towards the root. Any vertex has incoming edges and at most one outgoing edge. The other extremity of an incoming (outgoing) edge of the vertex v is called an incoming (outgoing) vertex of the vertex v. The root vertex has no outgoing vertex. A rooted tree induces a structure of poset on the vertices, where x < y if and only if there is an oriented path in the tree from y to x. A leave is a maximal vertex for this order. The root is the only minimal vertex for this order. Let x be a vertex of a rooted tree T . The full subtree T (x) of T derived from the vertex x is the subtree of T containing all the vertices y > x. The root of T (x) is x. One represents a rooted tree like this: The resulting tree has n + m − 1 leaves (counted from left to right) and represents an element of P(n + m − 1). The two first relations in Definition 1.1 corresponds to the following two trees: for a ∈ P(n), b ∈ P(m) and c ∈ P(ℓ) we can have Each relation is obtained by writing down the two ways of interpreting the tree as a composition of operations. In general a planar tree T(a 1 , a 2 , . . . , a k ) with k vertices labelled by elements a i ∈ P(n i ) where n i is the number of incoming edges at the ith vertex, corresponds to a unique composition of operations in P independent of any relations.
The two last relations in Definition 1.1 say that one can consider reduced trees (no vertices of arity 1) for reduced operads to represent non-trivial composition maps.
Any full subtree of T(a 1 , a 2 , . . . , a k ) is completely determined by the position of its leaves; they form an interval [p, q] where 1 ≤ p ≤ q ≤ n 1 + n 2 + · · · n k − k + 1. A tree in position [p, q] will mean the full subtree determined by the position [p, q] of its leaves. If a full subtree in position [p, q] has a single vertex labelled by a ∈ P(n) we identify this tree with the element a ∈ P(n). It is clear that n = q − p + 1.
Two trees of operations T(a 1 , a 2 , . . . , a k ) and Definition 1.4. Let S be a set. An S-labelled rooted tree is a non planar rooted tree as in Definition 1.2 whose vertices are in bijection with S. If S = [n], then we talk about n-labelled rooted trees and denote by T (n) the set of those trees. It is acted on by the symmetric group by permuting the labels.
The set T (3) has for elements: In general T (n) has n n−1 elements (see [1] for more details).
We denote by kT (n) the k-vector space spanned by T (n).
Theorem 1.5. [2, theorem 1.9] The collection (kT (n)) n≥1 forms a symmetric operad, the operad pre-Lie denoted by PL. Algebras over this operad are pre-Lie algebras, that is, vector spaces L together with a product * satisfying the relation We recall the operad structure of PL as explained in [2]. A rooted tree is naturally oriented from the leaves to the root. The set In(T, i) of incoming vertices of a vertex i is the set of all vertices j such that (j, i) is an edge oriented from j to i. There is also at most one outgoing vertex of a vertex i, i.e. a vertex r such that (i, r) is an oriented edge from i to r, depending whether i is the root of T or not. For T ∈ T (n) and S ∈ T (m), we define

A gradation on labelled rooted trees
We introduce a gradation on labelled rooted trees. We prove that in the expansion of the composition of two rooted trees in the operad pre-Lie there is a unique rooted tree of maximal degree and a unique tree of minimal degree, yielding new non-symmetric operad structures on labelled rooted trees.  In case a) the degree of the pair in U f is the same as it was in S. In case b), let {a ′ , b ′ } be the corresponding pair in T before relabelling. The degree d of the pair {a, b} in U f is the same as the degree There is a unique f Min such that deg(U f Min ) is minimal and there is a unique f Max such that deg(U f Max ) is maximal: which ends the proof. Proof-A rooted tree T is naturally oriented from its leaves to its root. Any edge is oriented and we denote by (a, b) an edge oriented from the vertex a to the vertex b. Let E T be the set of the oriented edges of the tree T . For an integer a = i we denote byã m i the integer a if a < i or a + m − 1 if a > i. Given a map f : In(T, i) → [m], the set E T • f i S has different type of elements: Let T ∈ T (n), S ∈ T (m) and U ∈ T (p). In order to avoid confusion, we denote by f i,p Max the map sending k < i to p and l > i to 1. We would like to compare the trees The proof of The two operads on labelled rooted trees defined by the theorem are denoted by T Max and T Min . Note that they are linearization of operads in the category of sets. Actually the composition maps are defined at the level of the sets T (n) and not only at the level of the vector spaces kT (n). There is another operad built on rooted trees which has this property: the operad NAP encoding non-asociative permutative algebras in [3], in which f NAP is the constant map with value the root of S. This operad has the advantage of being a symmetric operad.

The operad pre-Lie is free as a non-symmetric operad
We show that T Max is a free non-symmetric operad. Using Proposition 2.2, we conclude that the operad pre-Lie is free as a non-symmetric operad. To this end we need to introduce some notation on rooted trees. Remark that X (c) is obtained from X [a,b] by grafting subtrees of X at the vertices a and b only. We can then characterize trees X that are obtained from a non-trivial composition T • a S as follows: ] is a rooted tree. Let c be the label of its root. One has a ≤ c ≤ b.  It is clear from the discussion above and the definition of the operad T Max that X is decomposable if and only if it is the result of a non-trivial composition. Consequently, we say that X is indecomposable if it is not decomposable. That is there is no 1 ≤ a < b ≤ n such that (i)-(iv) are satisfied. For example let X = , This tree X is decomposable since for 1 ≤ 3 < 5 ≤ 8 we have that X [3,5] is a single tree and the subtrees of X (5) − X [3,5]  Proof. If T Max is not free, then for some n there is a tree X ∈ T Max (n) with two distinct constructions from indecomposables. In Remark 1.3, a non-trivial composition of operations is completely determined by a unique reduced planar rooted tree. We then have that X = T(T 1 , T 2 , . . . , T r ) = Y(S 1 , S 2 , . . . , S k ) where T 1 , . . . , T r , S 1 , . . . , S k are indecomposables and T(T 1 , T 2 , . . . , T r ) and Y(S 1 , S 2 , . . . , S k ) are two distinct trees of operations in T Max with r, k > 1.
The tree X = T(T 1 , T 2 , . . . , T r ) is decomposable (by assumption r ≥ 2). We can find 1 ≤ a < b ≤ n, such that X [a,b] is isomorphic to a single T i in position [a, b] in If X [a,b] is also isomorphic to a tree S j in position [a, b] in Y(S 1 , S 2 , . . . , S k ), then we replace X by the smaller tree in T Max (n − b + a) that we obtain by removing T i in T(T 1 , T 2 , . . . , T r ) and removing S j in Y(S 1 , S 2 , . . . , S k ). Clearly, this new smaller X has two distinct constructions from indecomposables. We can thus assume that X [a,b] is not isomorphic to a single S j in position [a, b] in Y(S 1 , S 2 , . . . , S k ).
We now study how X [a,b] overlaps in the position [a, b] of Y(S 1 , S 2 , . . . , S k ). Remark first that since all S j are indecomposables, the interval [a, b] cannot be part of a single S j of Y(S 1 , S 2 , . . . , S k ). Indeed, that would imply that S j would contain a subtree satisfying Definition 3.2 which would be a contradiction.
We may assume that a > 1. To see this, assume that the only sub Similarly, since T i is indecomposable, we must have b < b ′ . This implies that b = b ′ and T i = S j . This possibility was excluded above. So we must have a > 1 or a ′ > 1. In the case where a = 1 and a ′ > 1 we could just interchange the role of T(T 1 , T 2 , . . . , T r ) and Y(S 1 , S 2 , . . . , S k ) and assume that we have a > 1.
such that X [c,d] is isomorphic to a full subtree of operations Y ′ (S j 1 , S j 2 , . . . , S j ℓ ). Assume we can find c < a ≤ d < b such that X [c,d] ∼ = Y ′ (S j 1 , S j 2 , . . . , S j ℓ ) satisfies the Definition 3.2.
The graph X [a,d] is contained in the trees X [a,b] and X [c,d] . Let e be the label of the root of X [a,b] and f be the label of the root of X [c,d] . The two full subtrees X (e) and X (f ) both contain X [a,d] . This implies that either X (f ) is fully contained in X (e) , or X (e) is fully contained in X (f ) .
Let us assume that X (f ) is fully contained in X (e) , that means X [a,b] and X [c,d] are both subtrees of X (e) . From Definition 3.2, we know that X (e) is obtained from X . Hence f = a for f ∈ ]a, b]. As a conclusion c is part of a subtree attached to a. By (iii) of Definition 3.2 applied to the tree X [a,b] , the subtree must have a root r ∈ [b + 1, n]. This is a contradiction, the root r is part of any path joining a and c and r ∈ [c, d], hence not in X [c,d] . The case where X (e) is fully contained in X (f ) is argued similarly, using condition (iv) of Definition 3.2, and leads to a contradiction as well.
The same argument holds in case we can find a < c ≤ b < d.
The only case remaining is that the interval [p, q] associated to any full subtree There is at least one interval satisfying [a, b] ⊂ [p, q] (take the full tree Y(S 1 , . . . , S k ) and [p, q] = [1, n]). Let [p, q] be the smallest interval such that [a, b] ⊂ [p, q] and let Y(S 1 , . . . , S k ) (S j ) = Y ′ (S i 1 , . . . , S i l ) be the full subtree it determines. Its root is labelled by S j . The interval [u, v] associated to any proper full subtree of Y ′ (S i 1 , . . . , S i l ) satisfies [a, b] ∩ [u, v] = ∅. Consequently X| [a,b] is isomorphic to S j | [α,β] for some interval [α, β] isomorphic to [a, b]. This is impossible since X satisfies the conditions of Definition 3.2 and S j is indecomposable.
We must conclude that T Max is free. Remark 3.5. Let kT 0 Max (n) denote the k-vector space spanned by the indecomposables of T Max (n) (n > 1) and let β n be its dimension. Let α(x) = n≥1 α n x n be the Hilbert series associated to the free non-symmetric operad generated by the vector spaces kT 0 Max (n). It is well known (see e.g. [5]) that one has the identity β(α(x)) + x = α(x), where β(x) = n≥2 β n x n . Theorem 3.3 implies that α n = n n−1 . As a consequence, we get that the Hilbert series for indecomposable of T Max is dim kT 0 Max (n) x n = 2x 2 + x 3 + 14x 4 + 146x 5 + +1994x 6 + 32853x 7 + 630320x 8 + 13759430x 9 + · · · .
Corollary 3.6. The non-symmetric operad pre-Lie is a free non-symmetric operad.
Proof. Let F be the free non-symmetric operad on indecomposable trees. By the universal property of F , there is a unique morphism of operads φ : F → PL extending the inclusion of indecomposable trees in PL. We prove that this map is surjective by induction on the degree of a tree. Trees of degree 1 are indecomposables (see Definition 3.2). Let t ∈ PL(n) be a tree of degree k ≥ n − 1. If t is indecomposable then t = φ(t). If t is decomposable there are trees u ∈ PL(r), v ∈ PL(s), with r, s < n such that t = u • f Max i v in T Max . By Proposition 2.2 one has in PL where t j ∈ PL(n) has degree k j < k. From equation (2.1) we deduce that the degrees of u and v are also lower than k. By induction, the trees u, v and t ′ j s are in the image of φ, so is t. Thus, the operad morphism φ is surjective. Theorem 3.3 implies that the vector spaces F (n) and PL(n) have the same dimension, thus the operad morphism φ is an isomorphism.
Remark 3.7. The Hilbert Series for the free non-symmetric operad on indecomposables and the operad PL are the same as in Remark 3.5.