Lucian M. IONESCU* and Papa A. SISSOKHO
Illinois State University, Normal, IL 61790-4520, USA
Received date: December 21, 2006; Revised date: May 29, 2007
Visit for more related articles at Journal of Generalized Lie Theory and Applications
We study the Maurer-Cartan equation of the pre-Lie algebra of graphs controlling the deformation theory of associative algebras. We prove that there is a canonical solution (choice independent) within the class of graphs without circuits, i.e. at the level of the free operad, without imposing the Jacobi identity. The proof is a consequence of the unique factorization property of the pre-Lie algebra of graphs (tree operad), where composition is the insertion of graphs. The restriction to graphs without circuits, i.e. at “tree level”, accounts for the interpretation as a semi-classical solution. The fact that this solution is canonical should not be surprising, in view of the Hausdorff series, which lies at the core of almost all quantization prescriptions.
The present article presents a combinatorial solution of the Maurer-Cartan equation in the Lie algebra of binary graphs (g, [· , ·]) which controls the deformation theory of associative algebras:
where B is the natural basis of graphs of g. The specific solution is “canonical” in the sense that it does not depend on choices made iteratively to extend the solution from one degree to the next, as in the cohomological context, nor it depends on a particular choice of contraction as in .
The main result is that the underlying pre-Lie algebra multiplication, although not associative, has the unique factorization property. This in turn amounts to checking that the left and right Gerstenhaber composition multiplicity coefficients are equal.
The deformation quantization of Poisson manifolds was brilliantly solved by Kontsevich in a breakthrough article  which generated a “shower” of subsequent research papers.
Deformation quantization amounts, essentially, to the deformation of the usual classical commutative product of classical observables into a non-commutative star product, accommodating Heisenberg’s canonical commutation relations corresponding to the given Poisson structure encoding the classical dynamics of the classical system. Kontsevich solution used the sophisticated machinery of perturbative quantum field theory, allowing to write the star product as a formal power series. The difficulty of finding such a “continuation” of the expansion starting with the commutative product as the zero term and the Poisson bracket as the first order term, resides in the requirement of achieving associativity. This amounts to the fact that the coefficients must satisfy a cocycle equation, which is combinatorial in nature. It is a fact that Kontsevich’s coefficients  do not depend on the Poisson structure, and are Feynman integrals corresponding to any closed form, not just for the specific angle form, chosen for definiteness  (see also [17,16]).
In  it was claimed that the initial value deformation problem in the pre-Lie algebra of graphs has a canonical solution when restricted to graphs without circuits. It was first shown that the “coefficients problem” can be pulled back to the differential graded Lie algebra of graphs (, §5), which leads to a certain universal framework for deformation theory with the corresponding solutions of the Maurer-Cartan equation governing the space of deformations .
The claimed existence from  still relied on Kontsevich solution, i.e. on a star-product corresponding to a general Poisson structure which conjecturally yields a star-product when restricted to graphs without circuits. In  was realized that a different argument is needed to prove the existence of a solution when restricting the class of graphs (quasi-isomorphic complexes).
To get to the our main concern, the pre-Lie algebra of graphs, we will browse through Kontsevich’s construction.
The combinatorial problem regarding the coefficients of a star-product is captured by the “graphical calculus” we will call Kontsevich rule, a sort of a “dual Feynman rule”:
Here G is the class of graphs described below, (D, ο,m) is some pointed pre-Lie algebra  with a distinguished element m such that m ο m = 0 and is a Poisson structure (say on Rn):
It is an antisymmetric 2-tensor satisfying the Jacobi identity,
To a particular type of Poisson structure (e.g. constant/linear coefficients) corresponds a specific class of directed labeled graphs: those graphs Γ which are not in the kernel of the Kontsevich rule (kG/KerK). Once the “Problem” is pull back to graphs, it amounts to solving the equation
In this article we prove that if the pre-Lie algebra has the unique factorization property, a canonical solution exists (Theorem 3.1), namely the “graph exponential”
We develop general tools to investigate this property and we succeed to prove that this is the case for the class of Lie admissible graphs (Corollary 3.1). We also conjecture that the property is still enjoyed by graphs without circuits.
The proof relies on the result regarding the multiplicity coefficient for the the graph insertion at a boundary point as a pre-Lie operation (The Coefficient Theorem 3.1). A sort of Galois theory relating the symmetry of graphs with their extensions emerges. In this article we have dealt only with the simple case of unique incoming arrow case.
The article is organized as follows.
In Section 2 we recall the class of graphs  together with the pre-Lie composition from  (see also [21,11]). The core of the article is Section 3 which claims the “obvious solution” and introduces the main properties of graph insertion used in the subsequent proof.
In Section 4 we discuss some related questions.
Lie admissible graphs
Let Gn,m be the set of orientation classes of Lie admissible edge labeled graphs of , p. 3. An element Γ ∈ Gn,m is a directed graph with n internal vertices, m labeled boundary vertices 1, 2, . . . ,m such that each internal vertex is trivalent with exactly two descendants. The corresponding arrows will be labeled left/right, defining the orientation class of the graph Γ up to a transposition of the edge labeling in any two internal vertices . The corresponding (graded set) is denoted by G =∪Gm, where Gm = ∪n∈NGn,m.
Note that this class of graphs, with only one incoming arrow at a node, corresponds to linear Poisson structures, i.e. in such a case, graphs with more than one incoming arrow would yield a zero contribution under the graphical calculus of derivations.
Graphical representation and notation
The order of the boundary vertices is “fixed” once and for all and will be represented graphically by placing the boundary vertices on a oriented line.
The left/right labels on the outgoing edges at each internal vertex are implicit in a graphical representation of a graph Γ, as embedded in the upper half-plane with edge ordering induced by counter clockwise orientation. To “brake the symmetry” of graphs like c2 shown below, a labeling should be used instead, if needed (not present below).
The graphs from Gn,2 with n = 0, 1, 2 internal vertices are the Bernoulli graphs b0, b1, or the products of Bernoulli graphs ( = b1 · b1, to be defined shortly) as follows:
The “connected” graphs (see 2.4) from Gn,3 are represented below.
Antisymmetry and Jacobi relation
The Kontsevich rule has an obvious kernel since the Poisson tensor is antisymmetric and satisfies the Jacobi identity.
Since we solve the Maurer-Cartan equation “on the nose”, we do not assume the Jacobi relation being satisfied at the level of graphs.
We will only consider the anti-symmetry relation ˜: a permutation of the edge order at an internal vertex is equivalent to a change of sign. This relation includes (is compatible) with the equivalence relation on edge labeling from the previous section §2.2. The resulting quotient is denoted by H = kG/ ˜.
Product of graphs
The product of graphs (L-graph multiplication , p. 23; , p. 3, , p. 5) is defined by identifying their corresponding boundary points (thought as embedded in the upper half-plane). A graph is prime if by “cutting its boundary” it yields a “graph” with only one component. For example, , is not a prime graph.
Viewed as an “abstract graph” (incidence matrix), a graph is prime if the set of transition paths has more then one component. We will also call such a graph, connected.
Note that the product is compatible with the equivalence relation on edge-labeled graphs, and will be extended linearly on H.
The subspace generated by prime graphs is denoted by g. For this purpose the unit b0 is considered prime.
Composition of graphs
The graph composition of  was introduced in  (p. 8) at the level of unlabeled graphs, as the pullback of the Gerstenhaber composition through Kontsevich rule (see also ). It acquires Leibniz rule in this process, since under Kontsevich representation the arrows carry differential operators, while boundary vertices are “colored” by functions. For example,
where with • the only graph in G0,1 and •Γ denotes the “concatenation” of the corresponding graphs.
Note that graph composition is compatible with the grading by the number of boundary vertices (see , Appendix p. 22):
The above composition does not invary the class of Lie admissible graphs corresponding to linear Poisson structures. Since we are interested in the graphs not in the kernel of the Kontsevich representation, we will consider the truncation of the above composition due to the (orthogonal) projection Pr from all admissible graphs to our class of Lie admissible edge-labeled graphs G. The resulting composition of graphs is now an internal operation, still graded by degb.
Definition 2.1. The internal composition of graphs of G is defined as follows:
where οi is the insertion of Γ2 at the ith boundary vertex of Γ1 using “Leibniz rule” i.e. summing over all possible graphs where the “ith legs” of Γ1 lend on vertices of Γ2 , internal and external. The edge-labeling of the resulting graph is inherited from the edge-labeling of the two graphs Γi.
Graph composition is compatible with the anti-symmetry relation ˜, inducing a graph composition on H (, p.5).
If Ii denotes the set of incoming edges at the ith boundary point of Γ1 and [n2], [m2] denote the sets of internal and respectively external vertices of Γ2 , then the “Leibniz rule” at the ith vertex yields
where denotes the operation of replacing the vertex i with a disjoint copy of the set , with the edges e = (v → i) 2 Ii now pointing to f(e). The “two components” of f, fi, fb denote their co-restriction to internal and boundary vertices, respectively.
Now in order for the resulting graph to have internal vertices with only one incoming arrow, the component fi must be injective, yielding the following formula for graph composition.
where fi is 1:1.
We are now ready to prove that the “sum of all graphs” is a solution.
We will study a particular solution of [Z,Z] = 0 in the graded pre-Lie algebra of graphs, with possibly multiple incoming arrows at internal nodes. The tools developed apply to this level of generality, yet we have been able to prove the key result of unique factorization only for Lie admissible graphs (only one incoming arrow at a node).
Let In order to prove Z ο Z = 0 we need to investigate the coefficients of
where the coefficient BΓ is the difference between the coefficients (possibly zero) of the graph Γ resulting from left and from right graph insertions (ο1 and ο2): . To simplify notation, for any Γ ∈ Gn,m, Γ denotes the corresponding normalized basis element, i.e. Γ/|Aut(Γ)|.
The normalized bases of kG is .
The key fact (Proposition 3.1) is that ο1 is “injective” (similarly ο2), i.e. from the composition Γ1 ο1 Γ2 one can recover the operands Γ1 and Γ2 (“left groupoid structure” Γ : Γ1 → Γ2 ). In general the pair (Γ1, Γ2 ) responsible for a summand Γ as a result of a left insertion ο1 is different from the unique pair yielding a sum involving Γ in a right insertion ο2 (is the “left groupoid” isomorphic to the “right groupoid”?).
Now comparing the two sums
corresponding to left, and respectively right insertions, we obtain that the respective coefficients are equal (Corollary 3.3), a fact expected due to the left/right symmetry, and proved as The Coefficient Theorem 3.1.
To prove the above claims, we start with some preparatory lemmas.
For Γ ∈ G, let V in(Γ) denote its set of internal vertices, V bd(Γ) its set of boundary vertices, and let V (Γ) = V in [ V bd. For u 2 V in(Γ), let uL and uR be the left and right descendants of u, respectively. Moreover, denote by (u, . . . , v) a directed path starting at u and ending at the vertex v.
Proof. Define a partial order on internal vertices corresponding to the “flow” direction corresponding to the oriented edges (no loops→). Since any internal vertex has two descendants, clearly there is a path starting at u ending at a boundary point, say L. Now not all paths may end at L, since one may trace back last arrow and descend on the other arrow, until the end of the path is not L.
In particular, binary graphs without loops are connected.
Remark 3.1. Note that the lemma may fail for graphs with loops, and for m = 0, 1, Gn,m contains no binary admissible graph without loops.
Lemma 3.2. Let Γ ∈ Gn,3 and be a normal subgraph of Γ, i.e. is still admissible, with at least one boundary point.
Proof. (i) follows from the fact that if u 2 V () and say uL 62 V (), then the edge (u, uL) is not present in . This would contradict that is a binary graph, since it has an internal vertex u with at most one outgoing edge. (ii) follows from a recursively application of (i), using Lemma 3.1.
Our next goal is to prove that for each graph Γ ∈ Gn,3 there is a unique factorization in terms of graphs with less boundary points: Each such decomposition will correspond to a “maximal factor” of Γ, so here too “maximal implies prime”→
Lemma 3.3. For Γ ∈ Gn,3 there are unique normal subgraphs of Γ, denoted αL(Γ), R(Γ) ∈ Gn,2, sitting on the leftmost, and respectively rightmost, two boundary vertices of Γ.
Proof. Recall that being normal ensures that the quotient Γ/αL(Γ) is still a binary (exactly two descendants) admissible graph.
Suppose that Γ1 and Γ2 are two different normal subgraphs of Γ sitting on boundary points 1 and 2 of Γ (the other case follows by symmetry):. Then there exist an internal vertex u of Γ1 but not in Γ2 , since they cannot both equal . Note that by Lemma 3.2, any path starting at u must end at a boundary vertex: 1 or 2.
Since Γ2 is normal, = Γ/Γ2 ∈ Gn,2 is a binary admissible graph. By definition, we have u 2 V in . However, there is no directed path from u to the right boundary vertex contradicting Lemma 3.1.
Definition 3.1. For Γ ∈ Gn,3,
We now prove the key fact, that the left and right insertions are “injective”.
Proposition 3.1. Let
Proof. Let ∈ Gn,2 be such that Γ ∈ Gn,3 is a summand of Then, there exists a way to land legs from the left boundary vertex of onto the vertices of so that the resulting graph is Γ.
Since is a normal subgraph of Γ sitting on the its 1st and 2nd boundary vertex, it follows that . Moreover is the maximal subgraph of Γ sitting on its 1st and 2nd boundary vertex. For otherwise, αL(Γ) contains an internal vertex u of. Now, by Lemma 3.1, there exist a path from u to the second boundary vertex of . By Lemma 3.2, all the vertices (internal and external) in are in αL(Γ). In particular, the second boundary vertex of Γ00 (which is the third boundary vertex of Γ) would also have to be in αL(Γ). This would contradict the fact that αL(Γ) has to sit on the 1st and 2nd boundary vertex of Γ. Thus = αL(Γ).
Since Γ is a summand of because ο1 splits the edges landing on the 1st boundary vertex of and land them on vertices of = αL(Γ) while collapsing αL(Γ) in Γ does the converse, recovering .
Similarly, if are such that Γ is a summand of and
Regarding graph insertions as partially defined binary operations, the above result may be rephrased as follows.
Corollary 3.1. Boundary graph insertions have the unique factorization property.
As an immediate consequence we obtain that the Γ-coefficients of [Z,Z] result from a unique left/right composition, namely the composition of the unique normal maximal left/right supported subgraphs.
Corollary 3.2. BΓ = CΓ.
Proof. As a consequence of Proposition 3.1, represents the contributions from a left composition of a unique pair of graphs (Γ1, Γ2 ) and of a right composition of a unique pair . The corresponding multiplicities are . Therefore
All that is left in order to prove the main theorem, is to prove that left insertions produce the same coefficients as right insertions, i.e. . Fix a summand Γ of a fixed pair of graphs Γ1, Γ2 , i.e. Γ has a non-trivial coefficient in the sum expressing the left boundary composition Γ1 ο1 Γ2 . Then there is a left extension , characterized by the insertion data π (see section 3.2 for additional details), with Γ2 collapsing to the left boundary vertex of Γ1.
The Coefficient Theorem 3.1. After normalization, the non-trivial coefficient of Γ as a summand of the left insertion operation of Γ2 in Γ1 is 1. Therefore, if non-trivial, the left/right normalized multiplicities are
where πL, πR are the left/right insertion data determined by the graph Γ.
We will first exploit the result, deferring the proof to section 3.2.
Proof. Any Γ ∈ Gn,3 appears as part of (Γ/αL(Γ)) ο1 α(Γ). The coefficient of Γ in both Σ1 and Σ2 (Equation 3.1) is |Aut(Γ)|, i.e (i) holds, and the two sums are equal.
It follows from Lemma 3.2 that BΓ = CΓ, which by the Corollary 3.3 vanis h for all graphs Γ. This implies that
which yields Z ο Z = 0, concluding the proof of the Main Theorem 3.1.
Consider the graphs Γ1, Γ2 , Γ3 ∈ G1,3, defined as follows:
(1) The constant Case. Any admissible graphs can be expressed as where Γi, i =1, 2, 3, is as defined earlier. Thus
Since the coefficient of and the coefficient of then
In the normalized bases (similarly for the other normalized coefficients below).
(2) The linear case with n = 2.There are 9 admissible graphs in
For example, let We have
Thus, the coefficient of
Similar computations take care of the other cases, yielding
Proof of Theorem 3.1
We prove that the multiplicity of a graph as a summand in a graph composition is only due to their groups of symmetries.
Fix graphs Γ1, Γ2 and a summand Γ of their left boundary insertion as follows:
Since similar considerations apply to right insertions and to the corresponding coefficient we will use the generic notation
Then there is a left graph extension determined by the left insertion data defining the way the left leg arrows of Γ1 land on the vertices of Γ2 ,internal or boundary. Each insertion data π yields an admissible graph Γπ. Its isomorphism class will be called the type of the insertion.
Recall that for a linear Poisson structure, the non-boundary portion of the insertion π is injective.
Let D be the set of all insertion data π. For any be those insertion data of the same type as Γ. Then
For any insertion data π, let Aut(Γπ, π) be the set of Automorphism Aut(Γπ) that fix π.
We claim that the multiplicity of a summand in a left (right) boundary composition is given by the following formula.
Lemma 3.4. We have
We delay the proof of Lemma 3.4 to make some general observations.
Consider the action of H = Aut(Γ1) × Aut(Γ2 ) on DΓ defined as follows. For all =(1, 2) 2 H and for all π 2 D with π : S V1 → Tπ V2, we have
Claim 3.1. For π 2 D, we have i. e the action τ is transitive on
Proof. By definition, Conversely, if then there exits such that. Hence, there exist such that H; then
and the claim follows.
Claim 3.2. For π 2 D, we have
Proof. We show that there exist a bijection define by first restricting to the unique normal subgraph Γ1, which therefore is invaried by Then, Ø induces an Automorphism of the quotient,
Thus, since, by definition of It is easy to see that f is injective, since V = V1∪V2.
To prove that f is surjective, let Then there exist unique Automorphisms obtained by extending 1 and 2 in such a way that and Thus
is such that i.e. Since f is a bijection, we have
Proof of Lemma 3.4. Using an orbit-stabilizer argument, (3.2), and Claims 3.1 and 3.2, we obtain
Proof of The Coefficient Theorem 3.1. For Γ ∈ Gn,3, let
If Hence, there exist two insertion data πL and πR such that Moreover, it follows from Lemma 3.4 that
Now it remains to show that if then
In fact both Automorphism groups equal Aut(Γ). In order to prove this, note that there are (natural) restriction monomorphisms,
since are invaried as being (unique) maximal left normal subgraphs.
Lemma 3.5. We have Aut(Γ, S) = Aut(Γ, π), where S is the domain of π and Aut(Γ, S) is the subset of Automorphisms of Γ which invary S, i.
Proof. It is enough to prove “”, since the other inclusion follows from the definition of .
Since S has the property that any of its points has a unique arrow towards V2, the vertices of
Now the unique factorization implies that the “Galois group” Aut(Γ, π) is the full Automorphism group.
Lemma 3.6. We have Aut(Γ, π) = Aut(Γ).
Proof. Let π be the left insertion data yielding Γ as a left extension (by unique factorization).
If not only invaries Γ1 and Γ2 , but also S, the domain of π as being the set of arrows lending on the left leg of Γ1. By the previous lemma, Φ invaries π.
Therefore Aut(Γ, πL) = Aut(Γ) = Aut(Γ, πR) is the stabilizer of the action and the normalized coefficients are trivial or equal to 1.
This concludes the proof of Theorem 3.1.
We proved the existence of a canonical solution of Maurer-Cartan equation in the pre-Lie algebra of Lie admissible graphs, “on the nose”, without assuming the Jacobi identity holds.
The main fact used in the proof is the unique factorization property enjoyed by graph insertions.
In this way a canonical solution is obtained, which is not surprising, in view of the Hausdorff Lie series, which lies at the core of almost all quantization prescriptions. This opens a pertinent question, the investigation of its relation with the other “universal solution”, the Haussdorf series, living on the “base space”.
It is also natural to look for a physical interpretation of our solution as a (semi-classical part of the) correlation function in the spirit of . The lack of circuits means in physics jargon finding a solution at “tree level”. This does not involve the quantum corrections due to circuits, and relates to the effective action (see also ).
Although we investigate the linear case corresponding to Lie admissible graphs, we introduced new tools which, we conjecture, may provide a proof of the general case.
For linear Poisson structures the structure of the Galois group of a left (right) extension is simpler (subobject of the fibered product of Aut(Γ1) and Aut(Γ2 )), since π, the insertion data, is injective at the level of interior points, and a permutation of S is equivalent to an inverse permutation of T. Nevertheless the “simplification” entailing the left-right symmetry (equal coefficients) seams to be due to the lack of circuits, rather than, as one might expect, from the one-incoming arrow property satisfied by the Lie admissible graphs (π injective on interior points).
We believe that these are interesting topics for further study, revealing some of the relationship between the mathematics and physics of quantum phenomena.