{'fraction_non_alphanumeric': 0.05485547691658515, 'fraction_numerical': 0.010031263785795117, 'mean_word_length': 3.862258696260375, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 35, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Hopf algebras of formal diffeomorphisms and numerical integration on manifolds

B-series originated from the work of John Butcher in the 1960s as a tool to analyze numerical integration of differential equations, in particular Runge-Kutta methods. Connections to renormalization theory in perturbative quantum field theory have been established in recent years. The algebraic structure of classical Runge-Kutta methods is described by the Connes-Kreimer Hopf algebra. Lie-Butcher theory is a generalization of B-series aimed at studying Lie-group integrators for differential equations evolving on manifolds. Lie-group integrators are based on general Lie group actions on a manifold, and classical Runge-Kutta integrators appear in this setting as the special case of R^n acting upon itself by translations. Lie--Butcher theory combines classical B-series on R^n with Lie-series on manifolds. The underlying Hopf algebra combines the Connes-Kreimer Hopf algebra with the shuffle Hopf algebra of free Lie algebras. We give an introduction to Hopf algebraic structures and their relationship to structures appearing in numerical analysis, aimed at a general mathematical audience. In particular we explore the close connection between Lie series, time-dependent Lie series and Lie--Butcher series for diffeomorphisms on manifolds. The role of the Euler and Dynkin idempotents in numerical analysis is discussed. A non-commutative version of a Faa di Bruno bialgebra is introduced, and the relation to non-commutative Bell polynomials is explored.


Outline of the paper
The main point of this paper is to explore algebraic structures underlying groups of formal diffeomorphisms on manifolds. The paper focuses on some important mathematical structures appearing in numerical integration on manifolds that are likely to find applications also in other areas of mathematics. The relationship between classical Lie series on manifolds, time-dependent Lie series and Lie-Butcher series is explained in detail. Furthermore, we develop the algebraic structures introduced in [37,38,39,41,44,43,3] and in particular explore connections between Hopf-and Lie algebras, differential geometry and analysis of numerical integration on manifolds. Due to space limitation, the paper does not go into a detailed study of applications of these algebraic structures in numerical analysis, but we sketch briefly several of the many applications in this field.
The introductory Chapters 2 and 3 give an overview of well-known results. Chapter 2 contains a brief introduction to numerical integration and algebraic structures appearing in numerical analysis, both classical methods on R n and Lie group methods generalizing to manifolds. Chapter 3 presents a brief introduction to Hopf algebraic structures.
Chapter 4 contains more new and recent material. A main goal is to detail the algebraic structures of Lie-Butcher theory, and discuss the interplay between algebraic and differential geometric viewpoints. In particular we want to emphasize the strong connections between the algebraic theory of Lie series, time-dependent Lie series and Lie-Butcher series. Chapter 4 therefore starts with a discussion of classical Lie series and pullback formulas on manifolds, continuing with an exploration of some less known time-dependent pullback formulas. We will explain the relevance of the Euler and Dynkin idempotents in numerics and introduce a non-commutative Dynkin-Faà di Bruno bialgebra, related to non-commutative Bell polynomials appearing in various contexts in earlier works: numerical analysis [38], control theory [36] and quantization [31]. This Dynkin-Faà di Bruno bialgebra is related to, but different from, the Hopf algebras explored by Brouder et. al. in [6].
In the final part of Chapter 4, we discuss Lie-Butcher series. In particular we explore backward error analysis and the substitution law in the setting of algebras of non-commuting frames on manifolds. Although space does not allow for a detailed exposition and application of these subjects, we hope that this presentation will systematize the theory and open these topics for further future research.

Introduction to numerical integrators and their analysis
Let M be a manifold and F : M → T M a vector field. By the flow of an autonomous vector field F we mean the diffeomorphism Φ t,F : M → M, defined for t ∈ R such that Φ s,F •Φ t,F = Φ s+t,F , Φ 0,F = Id and ∂/∂t| t=0 Φ t,F (p) = F (p) for all p ∈ M.
Numerical integration of ODEs is about constructing good numerical approximations to Φ t,F for a given vector field F . A numerical integration algorithm yields a diffeomorphism Ψ h,F , henceforth called the numerical integrator. The real parameter h is called the stepsize. For an initial point y 0 ∈ M, and a chosen stepsize h > 0, the numerical method produces a discrete sequence of solution points y i = Ψ h,F (y i−1 ) with the goal of arriving at y k ≈ Φ kh,F (y 0 ). Note that, unlike the exact flow, numerical integrators are not 1-parameter Lie groups in h. In general we have Ψ h,F •Ψ s,F = Ψ h+s,F , and Ψ −h,F = Ψ −1 h,F . Integrators for which the latter identity holds are called (time-)symmetric methods. Most integrators satisfy the consistency conditions Ψ 0,F = Id and ∂/∂t| t=0 Ψ t,F (p) = F (p) as well as scaling homogeneity Ψ h,F = Ψ 1,hF .
Many algebraic aspects of numerical integration is related to the computation of compositions, logarithms and exponentials of numerical integrators. In recent years surprising connections between numerical analysis and renormalization in perturbative quantum field theory have been revealed. In this introduction, we will introduce some basic algebraic structures arising in the analysis of numerical integrators. In particular we will focus on structures that originate from the study of Lie group integrators, which are numerical integrators on general manifolds. The resulting theory combines Lie theory with the classical Butcher theory that describes numerical integrators on R n . This first section presents a survey of well known results from numerical analysis. A detailed understanding of this introductory section is not necessary for reading the rest of the paper, and readers mainly interested in algebraic structures may jump directly to Section 3.

Classical integrators
In the early 1960s John Butcher set out on a journey to explore the algebraic territory of numerical algorithms for integrating ODEs evolving on vector spaces y (t) = F (y), y ∈ R n , F : R n → R n . (2.1) In particular he studied the family of Runge-Kutta methods. Given a timestep h ∈ R, these methods advance the solution from y 0 = y(0) to y 1 ≈ y(h) as: for r = 1 : s do Y r = s k=1 a rk F k + y 0 F r = hF (Y r ) end This basic step is iterated: y 0 → y 1 → . . . → y n , with constant or variable stepsizes h, until the final solution y n ≈ y(t n ) is reached. The coefficients a rk and b k for r, k ∈ {1, . . . , s} define a particular s-stage RK method.
A goal of numerical analysis is to characterize coefficients a rk and b k which yield 'good' methods (when applied to a given class of differential equations). The view of what a good integration method is has, however, evolved over the last decades. Traditionally, order theory and stability were the most important properties to consider. A numerical integrator is of order p if the first p+1 terms of the Taylor expansion of the analytical solution agrees with the first p+1 terms of the numerical method (developed in the parameter h). Requiring a certain order results in algebraic conditions, called order conditions, on the coefficients of the method.
Many numerical methods for solving the equation (2.1) can be studied by using B-series (see e.g. [25]), introduced by Hairer and Wanner in 1974 [26]. A B-series is a (formal) series indexed over the set of rooted trees T and can for a vector field F be written as Here a is a map a : T → R, I is the empty tree, |τ | is the number of vertices of τ (the order of the tree τ ) and σ is a certain symmetry factor. The map F F (τ ) : R n → R n is the elementary differential of the tree τ and is given recursively as follows: where τ = B + (τ 1 , ..., τ m ) is the tree constructed by adding a common root to the subtrees τ 1 . . . τ m , and F (m) is the m'th derivative of the vector field. One way in which B-series can be applied to the study of numerical methods is to order theory. For example, the order conditions for Runge-Kutta methods can easily be obtained by writing the method as a B-series and then comparing the coefficients of this series with the exact solution written as a B-series (see e.g. [25, Chapter. III.1.2]).
The composition of Runge-Kutta methods is also of great interest, and this leads to the study of the composition of B-series. A series B hF (a) is inserted into another series B hF (b), and this gives the B-series B hF (a)(B hF (y)(b)) = B hF (a · b)(y). The resulting product a · b gives rise to a group, called the Butcher group [9,16].
Butcher realized early that the set of Runge-Kutta methods forms a group, and characterized algebraically the composition and inverse in this group. Much later, this group was identified with the character group of the Connes-Kreimer Hopf algebra [17,19,5].
In recent years the importance of preserving various geometric properties of the underlying continuous dynamical system has become better understood. The research topic Geometric Numerical Integration [25] emphasizes this view. Geometric integration algorithms have been successfully developed for various classes of differential equations, such as volume preserving flows, Hamiltonian equations, systems with first integrals and equations evolving on manifolds. An important tool for investigating the geometrical properties of a numerical integrator is through its backward error analysis. For a given numerical method Ψ h,F , we seek a series expansion of a modified vector field (h, F ) →F h such that the numerical solution equals 1 the analytical flow of the modified vector This is computed as a formal logarithmF h = Log(Ψ h,F ), in Hopf algebraic language expressed by the Eulerian idempotent (Section 3.2.2).
Still another idea, which has been developed in [14], is to ask for a series development of a modified vector field F h , such that when the numerical method is applied to F h , the exact analytical solution is produced: Ψ h,F h = Φ h,F . This has been taken much further in recent work [15,10]. The algebraic operation (h, F ) → F h is commonly referred to as a substitution law. The Hopf algebra of the substitution law is introduced in [10].
B-series is often a very important component in a numerical analyst's toolbox, and is used to study order theory, backward error analysis, modified vector fields and structure preserving properties of numerical integrators.

Lie group integrators
Numerical Lie group integrators for ODEs is a generalization of numerical integration of ODEs from the classical setting of equations on R n to differential equations on manifolds. In this section, we will give a short introduction to this topic. See [28] for an extensive survey.

Exponential Euler method
Let M denote a manifold, X M its Lie algebra of vector fields with the Jacobi bracket and Diff(M) the group of diffeomorphisms on M. Let exp : X M → Diff(M) denote the flow operator. We want to numerically integrate an ODE on M, given as having the analytical solution y(t) = exp(tF )·y 0 . Here exp(tF )·y 0 denotes the evaluation of the diffeomorphism exp(tF ) at y 0 ∈ M.
Assumption 2.1. The fundamental assumption for numerical Lie group integrators is the existence of a subalgebra g ⊂ X M such that • All vector fields V ∈ g can be exponentiated exactly.
• The Lie algebra g defines a frame on T M, i.e. g spans the tangentspace T p M at all points p ∈ M. In other words, the action generated by g is transitive on M.
The vector fields in g are called the frozen vector fields. Due to the frame assumption, we can always express the vector field F and the ODE (2.4) in terms of frozen vector fields via a function f : M → g as F (y) = f (y)·y, where f (y) ∈ X M and f (y)·y denotes evaluation of this vector field in y. Thus (2.4) can be written in the form y (t) = f (y)·y, y(0) = y 0 ∈ M. (2.5) In the case where g forms a basis for T y M, the function f (y) is uniquely defined. In more general situations, g is an overdetermined frame for T y M, and there is a freedom in the choice of f . This is called a choice of isotropy, and is of major importance for the quality of the numerical integrator.
With the equation written as (2.5), we can present the simplest of all Lie group integrators, the exponential Euler method. Given a timestep h ∈ R, the method advances the solution from y 0 = y(0) to y 1 ≈ y(h) as:  In each step the method advances the solution y k → y k+1 by integrating the frozen vector field equation y (t) = f (y k )·y, y(0) = y k from t = 0 to t = h. We will in the sequel present methods of higher order and with superior qualities compared to this simple scheme. The main theme of the paper is the algebraic structures arising from the numerical analysis of such integration schemes.

Choosing a good action
In practice it is of importance that exp : g → Diff(M) can be computed fast, and furthermore that the given vector field F (y) is locally well approximated by f (y 0 ) · y. Exactly what 'well' means, depends on what we want to achieve. In many situations we can choose g so that certain first integrals of the original system are exactly preserved by the frozen flows. Choosing g and f : M → g is in many ways similar to choosing a preconditioner in iterative methods for solving linear equations; we want a good approximation which is easy to compute. A simple choice of g is obtained by embedding M ⊂ R n and choosing g = R n as the (commutative) algebra generated by {∂/∂x j } n j=1 , i.e. the constant vector fields on R n . Since the vector fields are constant, we have f (y 0 )·y = f (y 0 ), so the function f simply becomes f (y 0 ) = F (y 0 ) ∈ R n , all commutators in g vanish and the exponential on g is exp(V )·p = V + p for V, p ∈ R n . In this case all Lie group integrators will reduce to classical integrators, e.g. exponential Euler becomes the classical Euler y 1 = hF (y 0 ) + y 0 .
The other extreme is g = X M and f (y) = F for all y, in which case exponential Euler yields the analytical solution exactly. However, in this case the computation of the exponential on g is just as difficult as solving the original equation. We seek efficient choices in between these two extremes.
In many cases g is given as the infinitesimal generators of a (e.g. left) Lie group action on M. For example, consider the sphere M = S 2 acted upon from left by the group G = SO(3) of orthogonal 3 × 3 matrices, with the Lie algebra so(3) consisting of skew 3 × 3 matrices. Any matrix V ∈ so(3) is uniquely identified with the infinitesimal generator 2 ξ V ∈ X M, given by matrix-vector multiplication ξ V · y = V y for y ∈ S 2 . Therefore (2.5) becomes y (t) = V (y)y, where V (y) is a skew symmetric matrix. The exponentiation is related to the matrix exponential expm(V ) as exp(ξ V )·y = expm(V )y.
Another important example of group actions arise in the solution of isospectral differential equations, where GL(n) acts on gl(n) by the adjoint action (similarity transform) A · Y = AY A −1 for A ∈ GL(n), Y ∈ gl(n). In these problems M ⊂ gl(n) is one of the (isospectral) orbits of the action. For this action (2.5) acquires the isospectral form Y (t) = [B(Y ), Y ] for some B(Y ) ∈ gl(n). Since the action is a similarity transform it is guaranteed that all the eigenvalues of Y (t) are preserved also by the numerical integrator.
Yet another example, which occurs in Lie-Poisson problems in computational mechanics, is the coadjoint action of a Lie group on the dual of its Lie algebra, g * . In this case M ⊂ g * is a coadjoint orbit. Using this action we can guarantee that the numerical Lie group integrator exactly preserves the Casimirs of the continuous system.
For other problems it may be advantageous to choose g by simplifying the original equation to a family of integrable equations. A simple example is the computation of the motion of charged particles in a magnetic field. The solution in the case of constant magnetic fields is given by helical motions around the field lines. The corresponding Lie algebra yields fast and accurate Lie group integrators for the full problem of non-constant magnetic fields. Another example is integration of a spinning top, where we obtain simpler equations by considering the direction of gravity as being constant in body coordinates. In both these problems, the action preserves important first integrals of the system. A third example is integration of stiff equations on R n , where an integrable Lie algebra is obtained by considering all affine linear vector fields. This connects the theory of Lie group integrators with the so-called exponential integrators. See [28] for details.

Higher order methods
Most Lie group methods for integrating (2.5) are built from linear operations and commutators in g and compution of flows of frozen vector fields (exponentials). Runge-Kutta type methods with basic motions expressed in terms of an exponential of a sum of elements in g are commonly referred to as RKMK methods [28], as in the following example: Algorithm 2.3 (4'th order RKMK from [38]).
Methods where the basic motions are products of exponentials of simple elements in g are called Crouch-Grossman methods [18,44].
More recently methods have been developed which combine exponentials of sums and products of exponentials, as in the commutator free Lie group methods [13]. An example is: Algorithm 2.5 (4'th order commutator free method from [13]).
For equations of Lie type y (t) = f (t) · y, numerical methods based on Magnus and Fer expansions have been developed in [29,27], and the algebraic theory has recently been developed further in [21].
To study order conditions, backward error analysis and structure preservation of such methods, it is important to understand B-series in a general setting of group actions on manifolds. A first attempt at combining Lie and B-series in a common mathematical framework appeared in [37,38]. Hopf-algebraic aspects have been explored further in [39,3,41].

Hopf algebras
This section is meant as a short collection of facts and properties of Hopf algebras that we will use in this work. For a more thorough introduction, see e.g. [1], [34], [47], [30], [11].

Basic definitions
Let k be a field containing Q.
Definition 3.1. A k-algebra A consists of a k-vector space A together with two maps µ : A⊗A → A and η : k → A, called the product and the unit of A, such that: Here I denotes the identity map.
Definition 3.2. A k-coalgebra C is a k-vector space equipped with two maps ∆ : C → C ⊗ C and : C → k, the coproduct and the counit, such that: A bialgebra H is called commutative if it is commutative as an algebra, and cocommutative if it is cocommutative as a coalgebra.

Remark 3.4.
There is symmetry in the definition of a bialgebra. Rather than requiring the coalgebra structure to respect the algebra structure in the above sense, we could have switched the role of the two structures. To complete the symmetry, we could in addition reverse the arrows in the two diagrams above. This would result in an equivalent definition.
Grading. Let H be a graded k-vector space, i.e. H = n≥0 H n . There is a notion of a graded bialgebra, obtained by requiring the following of the algebra and coalgebra structure, respectively: The grading of an algebra H gives rise to the grading operator Y : H → H given by . Let H be a connected, graded bialgebra. Then, for any x ∈ H n , n ≥ 0, we have: We will often use the Sweedler notation for the coproduct: x ⊗ x . 3 All diagrams were created using Paul Taylor's diagram package, available from http://www.paultaylor.eu/diagrams/ Definition 3.6. A Hopf algebra is a bialgebra (H, µ, η, ∆, ) together with an antihomomorphism S on H, called the antipode, with the property given by the commutativity of the following diagram: A Hopf algebra is graded if it is graded as a bialgebra and the antipode satisifies S(H n ) ⊂ H n . If a bialgebra is graded and connected, then it is automatically a graded Hopf algebra: 34]). Any connected graded bialgebra is a Hopf algebra. The antipode S is given recursively by S(1) = 1 and Example 3.8. The Shuffle Hopf algebra. Recurring in the sequel are Hopf algebras built from letters in an alphabet. We follow the notation of Reutenauer [46]. Consider a finite or infinite alphabet of letters A = {a, b, c, . . .}. We write A * for the collection of all empty or nonempty words over A, where I is the empty word. Let k A be the k-algebra of non-commutative polynomials in A. A polynomial P ∈ k A will be written as a sum where (P, ω) ∈ k is non-zero only for a finite number of ω. Let P, Q ∈ k A . The product of P and Q, written as P Q, has coefficients The k-linear dual space denoted k A := Hom k (k A , k) is identified with all infinite k-linear combinations of words. An α ∈ k A can be written as an infinite series where (α, ω) ≡ α(ω) ∈ k and (·, ·) is the dual pairing defined such that words in A * are orthogonal, (ω 1 , ω 2 ) = δ ω1,ω2 for all ω 1 , ω 2 ∈ A * .
We define two different associative products on k A . The concatenation product ω 1 , ω 2 → ω 1 ω 2 obtained by concatination of words and the shuffle product ω 1 , ω 2 → ω 1 ω 2 obtained by linearly combining all possible shuffles of the two words i.e. combinations where the letters within each word are not internally permuted, e.g.
The shuffle product can be defined recursively as where a, b ∈ A and ω 1 , ω 2 ∈ A * . The unit of both concatenation and shuffle is the empty word I.
By dualization of these products we obtain the deconcatenation and the deshuffle coproducts. The deconcatination coproduct ∆ d : k A → k A ⊗k A , defined for ω = a 1 a 2 · · · a k ∈ A * as: This coproduct is the dual of the concatenation product, so for any P, Q ∈ k A The deshuffle product ∆ : k A → k A ⊗k A is similarly defined such that The two coproducts can also be characterized by requiring that the letters in the alphabet A are primitive, i.e. that ∆(a) = 1⊗a+a⊗1 for a ∈ A, and then extending ∆ to be a homomorphism with respect to either of the two products on k A . We refer to [46] for explicit presentations of the deshuffle coproduct.
We remark that the vector space k A can now be turned into Hopf algebras in two different ways. The cocommutative concatenation Hopf algebra is obtained by taking the concatenation as product and the deshuffle as coproduct. The commutative shuffle Hopf algebra H Sh (A) is obtained by taking the shuffle as product and the deconcatenation as coproduct. Both these Hopf algebras share the same antipode: In both cases the unit and counit is given by η(1) = I and (I) = 1, (ω) = 0 for all ω ∈ A * \I. We write H Sh when A is understood. The vector space k A can be identified with the vector space underlying the tensor algebra T (V ) on the vector space V generated by the alphabet A. The two algebra structures (concatination and shuffling) correspond to the usual algebra structures given to the tensor algebra T (V ) and the tensor coalgebra T c (V ), respectively.
Let (H, µ, η, ∆, ) be a graded bialgebra, and (A, ·, η A ) an algebra. The set Hom k (H, A) of linear maps from H to A sending η H (1) =: 1 H to η A (1) =: 1 A has an algebra structure given by the convolution product: The convolutional unit is the composition of the counit of H and the unit of A: δ := η A • . The convolution can be written using the Sweedler notation: where S is the antipode of H.
In the special case A = k, we get the group of characters of H, written as G(H) := G(H, k).
The grading on H splits the group of A-valued characters into graded components: This is not a graded vector space, but rather the completion of one (see e.g. [20]), but we will still call it a graded vector space. The restriction of a character α : H → A to the degree n component H n of H will be denoted by α n .

Infinitesimal characters, the exponential and the logarithm
The infinitesimal A-valued characters, written g(H, A) are the linear maps α from H to A such that: This is a Lie algebra under the bracket induced by the convolution product: The characters and the infinitesimal characters are connected via the exponential and the logarithmic map. Let α ∈ Hom k (H, A). The exponential and logarithm with respect to convolution are given by the formal series: If H is graded and connected, and if α(1) = 0, where 1 ∈ k = H 0 , then α * k = α * · · · * α = 0 on H n for n < k, and therefore both these sums are finite when restricted to H n , provided α(1) = 0. The maps exp * and log * give a bijection between G(H, A) and g(H, A).
Example 3.10. Let H Sh denote the shuffle algebra over A. Consider the dual space k A equipped with the convolution product Note that convolution is just concatenation of series α * β = αβ. The characters and infinitesimal characters g(H Sh ), G(H Sh ) ⊂ k A are given as The convolutional unit δ is given as (δ, I) = 1 and (δ, ω) = 0 for all ω ∈ A\I. The logarithm of α ∈ G(H Sh ) can be computed as log(α) = n>0 (−1) n−1 n (α − δ) * n . For any ω ∈ A * we find that (log(α), ω) is given by a finite sum expressed in terms of the Eulerian idempotent.

Eulerian idempotent
Let H be a commutative, connected and graded Hopf algebra. Consider End k (H) = Hom k (H, H) equipped with the convolution product * . Let Id ∈ End k (H) be the identity endomorphism and δ = η • ∈ End k (H) the unit of convolution.
where J = Id −δ. The practical importance of the Eulerian idempotent in numerical analysis arises in backward error analysis, where the following lemma provides a computational formula for the logarithm: In other words, the logarithm can be written as right composition with the eulerian idempotent: The result follows from the following computation, which uses that α is a homomorphism: where (−) l denotes l-fold application.

The graded Dynkin operator
There is another bijection between the infinitesimal characters and the characters in any commutative graded Hopf algebra H, described in [20]. The bijection is given in terms of the Dynkin operator D : H → H. Classically, the Dynkin operator is a map D : k A → Lie(A), where Lie(A) = g(H Sh ) ∩ k A are the Lie polynomials. The classical Dynkin operator is given by left-to-right bracketing: Letting Y (ω) = #(ω)ω denote grading operator, where #(ω) is word length, it is known that the Dynkin idempotent, given as Y −1 D, is an idempotent projection on the subspace of Lie polynomials. As in [20], the Dynkin operator can be written as the convolution of the antipode S and the grading operator D = S * Y . This description can be generalized to any graded, connected and commutative Hopf algebra H:   The inverse is given by Γ : g(H) → G(H) as Γ(α) = n k 1 + · · · + k l = n, k 1 , ..., k l > 0 α k1 * · · · * α k l k 1 (k 1 + k 2 ) · · · (k 1 + · · · + k l ) , Later we will apply the Dynkin operator and its inverse in the setting of a shuffle algebra H Sh (OT), where OT is an alphabet of all ordered rooted trees, and the grading |τ | of τ ∈ OT counts the nodes in the tree.

Algebras of formal diffeomorphisms on manifolds
The main goal of this section is to arrive at Lie-Butcher series and the underlying Hopf algebra H N . This Hopf algebra contains the Connes-Kreimer Hopf algebra as a subalgebra and is also closely related to H Sh . To emphasize the natural connection between Lie-Butcher series, H N and more classical Lie series, we start with a discussions of Lie series (autonomous and non-autonomous).

Autonomous Lie series
In this section we review the well-known theory of Lie series on manifolds and the corresponding Hopf algebraic structures of the free Lie algebra. The algebraic theory is detailed in [46,11] and for the analytical theory we refer to [2].
Let F be a vector field on a manifold M and Φ t,F : M → M its flow. Let ψ : M → E be a section of a vector bundle over M, and let Φ * t,F ψ denote the pullback. For the applications later in this paper we will only consider trivial bundles, in which case we write ψ : M → V for some vector space V and define pullback as composition Φ * t,F ψ = ψ•Φ t,F . The Lie derivative of ψ is defined as Composition of Lie derivatives defines an associative, non-commutative product of vector fields F, G → F G, where vector fields are first order differential operators. The product F G is the second order differential operator (F G)[ψ] = F [G[ψ]] etc. We let I denote the 0'th order identity operator I[ψ] = ψ. The linear span of all differential operators of all orders forms the universal enveloping algebra U (X M).

The basic pullback formula is [2]
Iterating this we find ∂ n /∂t n | t=0 Φ * t,F ψ = F [F [· · · [ψ]]] := F n [ψ], and hence follows the (Taylor)-Lie form of a pullback series: Fundamental questions are: Which series in U (X M) represent vector fields and which represent pullback series? How do we algebraically characterize compositions and the inverse of pullback series? How do we understand the Exp map taking vector fields to their pullback series, and the inverse Log operation? These questions are elegantly answered in terms of the shuffle Hopf algebra. We will detail these issues, and see that the same structures reappear in the discussion of B-series later.
An algebraic abstraction of Lie series starts with fixing a (finite or infinite) alphabet A and a map ν : A → X M assigning each letter to a vector field. As in Example 3.8 we let R A denote all finite R-linear combinations of words built from A and H Sh the shuffle algebra. The map ν can be uniquely extended to a linear F ν : R A → U (X M) as a concatenation homomorphism: We extend F ν to a map B t taking an infinite series α ∈ R A to an infinite formal series B t (α) ∈ U (X M) * , defined for t ∈ R as follows: Consider the alphabet A with a grading |a| ∈ N + for all a ∈ A. This extends to H Sh as |ω| = |a 1 | + . . . + |a k | for all ω = a 1 . . . a k ∈ A * , |I| = 0, thus H Sh becomes a graded connected Hopf algebra. Given the grading we define Consider H Sh * = R A with the convolution α * β = αβ as in Example 3.10. By construction B t is a convolution homomorphism, For a real valued infinitesimal character α ∈ g(H Sh ), and a fixed t = h, B h (α) is a formal vector field on M. For a real valued character β ∈ G(H Sh ), B h (β) represents a formal diffeomorphism Φ h on M via the pullback series Note, however, that pullbacks compose contravariantly with respect to composition of diffeomorphisms: Thus to summarize: Composition of diffeomorphisms is modelled by convolution in G(H Sh ) (in opposite order), the inverse of a diffeomorphism is computed by right composing with the antipode, the convolutional exponential maps to the exponential of Lie series and the logarithm is computed by composing with the Eulerian idempotent, In the next section we discuss flows of non-autonomous equations, and we will see that right composition with the Dynkin idempotent represents algebraically the operation of finding a nonautonomous vector field corresponding to a diffeomorphism on a manifold. Remark 4.1. In [40] the Lie algebra of infinitesimal characters g(H Sh ) is studied as a graded free Lie algebra. An explicit formula for the dimension of the homogeneous components g k = g(H Sh )| k is derived for general gradings. This is very useful for the study of the complexity of Lie group integrators.

Time-dependent Lie series
The classical Faà di Bruno Hopf algebra models the composition of formal diffeomorphisms on R ( [23], [22], [24]). In this section we will see that this has a natural generalization to compositions of time-dependent flows on manifolds. We introduce a Dynkin-Faà di Bruno bialgebra describing the composition of flows of time-dependent vector fields on a coarse level that considers only the grading of the terms in the t-expansion of the time-dependent vector fields.

Non-commutative Bell polynomials and Dynkin-Faà di Bruno bi-algebra
Let I = {d j } ∞ j=1 be an infinite alphabet in 1-1 correspondence with N + , and consider the free associative algebra D = R I with the grading given by |d j | = j and |d j1 · · · d j k | = j 1 + · · · + j k . Let ∂ : D → D be the derivation given by ∂(d i ) = d i+1 , linearity and the Leibniz rule ∂(ω 1 ω 2 ) = ∂(ω 1 )ω 2 + ω 1 ∂(ω 2 ) for all ω 1 , ω 2 ∈ I * . We let #(ω) denote the length of the word ω. The first of these are given as The polynomials B n are introduced in [37,38] to explain the Butcher order theory of Runge-Kutta methods in a manifold context, and generalize to certain classes of numerical integrators on manifolds.
We find by induction that (d 1 + ∂) n satisfies the binomial relation which yields the formula and also the recursion The non-commutative partial Bell polynomials B n,k ≡ B n,k (d 1 , . . . , d n−k+1 ) are defined as the part of B n consisting of the words ω of length #(ω) = k > 0, e.g.
A bit of combinatorics yields an explicit formula: where for ω = d j1 d j2 · · · d j k n ω ≡ n |d j1 |, |d j2 |, . . . , |d j k | := n! j 1 !j 2 ! · · · j k ! are the multinomial coefficients and the coefficients κ(ω) are defined as κ(ω) ≡ κ(|d j1 |, |d j2 |, . . . , |d j k |) := j 1 j 2 · · · j k j 1 (j 1 + j 2 ) · · · (j 1 + j 2 + · · · + j k ) . (4.8) The coefficients κ form a partition of unity on the symmetric group S k , where σ(ω) denotes a permutation of the letters in ω. E.g. κ(1, 2) + κ(2, 1) = 2 3 + 1 3 = 1. It is often useful to employ polynomials Q n and Q n,k related to B n and B n,k by the following rescaling: Note that B n and B n,k become the classical Bell-and partial Bell polynomials when the product in R I is commutative, i.e. in the free commutative algebra on I. A non-commutative Faà di Bruno Hopf algebra is studied in [6]. However, their definition differs from the present by defining the polynomials Q n,k without the factor κ that associates different factors to different permutations of a word (adding up to 1 over all permuatations).
These Bell polynomials are closely related to the graded Dynkin operator on a connected graded Hopf algebra H. For α ∈ H * , define a graded algebra homomorphism d i → d i (α) : D → H * as Proposition 4.4. The operator defined as is a bijection from infinitesimal characters to characters Q : g(H) → G(H) with inverse given by right composition with the Dynkin idempotent Y −1 •D, where Y is the grading operator on H and D = S * Y is the graded Dynkin operator.
The non-commutative Dynkin-Faà di Bruno bialgebra D is obtained by taking the algebra structure of D and defining the coproduct ∆ D as This extends to all of D by the product rule . Thus, e.g.
Note that the coproduct is not graded by | · |, thus Proposition 3.7 does not hold for D. By a lengthy (but not enlightening) induction argument we can prove: Lemma 4.5. The coproduct of the partial Bell polynomials are given as Note that B n,1 = d n , thus (4.17) is a special case of (4.18). Summing the partial B n,k over k, we find the coproduct of the full Bell polynomials Using Lemma 4.5 and the fact that B n,k = 0 for k > n, one can easily show that D is a bialgebra.
Proposition 4.6. D = R I with the non-commutative concatenation product and the coproduct ∆ D form a bialgebra D which is neither commutative nor cocommutative.

Pullback along time-dependent flows
. Let Φ t,Ft be the solution operator of the corresponding non-autonomous equation, such that y(t) = Φ t,Ft y 0 solves y (t) = F t (y(t)), y(0) = y 0 .
(Note that Φ t,Ft is not a 1-parameter subgroup of diffeomorphisms in t.) Lemma 4.7.
[37] The n-th time derivative of the pullback of a (time-independent) function ψ along the time-dependent flow Φ t,Ft is given as where B n (F t ) is the image of B n under the homomorphism from D to U (X M) given by d i → F Proof. The non-autonomous vector field F t on M corresponds to the autonomous field F t + ∂/∂t on M×R, thus (4.2) yields Consider the homomorphism induced from d 1 → F t and ∂ → ∂/∂t, thus d i → F Remark 4.8. Note that (4.5) yields a space-time split formula for pullback which is valid also for pullback of a time-dependent function ψ t . The pullback for t ∈ [0, h] developed at t = 0 becomes The Dynkin idempotent relates pullback series with their corresponding time-dependent vector fields. Let A be an arbitrary alphabet with a grading | · | : A → N + , let H Sh = H Sh (A) be the corresponding graded shuffle algebra and let B t (α) be defined in (4.3).
Using (4.15) we obtain the result.

Lie-Butcher theory
Pullback formulas such as (4.21) relate the time derivatives of F t with the spatial derivatives of a function ψ. We have captured the algebraic structure of the temporal derivations through the Dynkin idempotent Y −1 •D : G(H Sh ) → g(H Sh ) and its inverse Γ•Y : g(H Sh ) → G(H Sh ). However, the spatial Lie derivation B t (β)[ψ] cannot be algebraically characterized within this structure. In order to do this, we need to refine the Hopf algebra H Sh . On the manifold, we obtain a refined version of U (X M) by expanding differential operators in terms of a non-commuting frame on X M. If the manifold is R n and the frame is the standard commutative coordinate frame, the construction yields the classical Butcher formulation and the Connes-Kreimer Hopf algebra [4]. More generally we obtain a Hopf algebra H N , built on forests of planar trees, which contains the Connes-Kreimer algebra as a subalgebra. In H N we can represent Lie derivation in terms of tree graftings.

Differential operators in U (X M) expanded in a non-commuting frame
Let X M denote the Lie algebra of all vector fields on M and let g ⊂ X M be a transitive Lie subalgebra, in the sense that g everywhere spans T M. This means that g defines a frame on the tangent bundle. We do not assume that the frame forms a basis. In general dim(g) ≥ dim(M), and in case of strict inequality we have a non-trivial isotropy subgroup at any point.
Let U (g) denote the universal enveloping algebra of g. We let g M and U (g) M denote maps from M to g and from M to U (g). Since g is assumed to be transitive, we can represent any vector field F ∈ X M with a function f ∈ g M as in Section 2.2.1. Similarly, any higher order differential operator in U (X M) can be represented as a function in U (g) M . We have the natural inclusion g ⊂ g M and U (g) ⊂ U (g) M as constant maps, called frozen vector fields and higher order differential operators.
We identify U (g) M with sections of the trivial vector bundle M⊗U (g) → M and for a dif- Pullback in this bundle defines a parallel transport which gives rise to a flat connection with torsion. For f, g ∈ U (g) M we define the connection f [g] ∈ U (g) M pointwise from the Lie derivative as Similarly, the concatenation in U (g) is extended pointwise to a concatenation product f g ∈ U (g) M as This is called the frozen composition of f and g. We can also compose f and g as non-frozen differential operators f •g ∈ U (g) M : This is identical to the composition in U (X M), which in Section 4.1 was written as F, G → F G for F, G ∈ X M. It might be illustrative to write out the operations explicitly in terms of a basis {∂ k } n k=1 of (non-commuting) vector fields spanning g. Writing f, g ∈ g M in terms of the frame as f = k f k ∂ k and g = g ∂ for f k , g ∈ R M , we have The connection f [g], the frozen composition f g and nonfrozen composition f •g are related as: Lemma 4.10. Let f ∈ g M and g, h ∈ U (g) M . Then we have where I ∈ U (g) M is the constant identity map.
The proof is given in [41]. Note the difference between f g and f •g. In the concatenation the value of g is frozen to g(p) before the differentiation with f is done, whereas in the latter case the spatial variation of g is seen by the differentiation using f . Interestingly, the work of Cayley from 1857 [12] starts with the same result for vector fields expanded in the commuting frame ∂/∂x i . From this lemma we may compute the torsion and curvature of the connection. Let f, g ∈ g M . We henceforth let [f, g] • := f •g − g•f denote the Jacobi bracket and [f, g] = f g − gf the frozen bracket. The frozen bracket is computed pointwise from the bracket in g as [f, g](p) = [f (p), g(p)] g . Writing the connection as ∇ f g := f [g], we find Note that if g is commutative, then [f, g] = 0 and the connection is both flat and torsion free.
In this case f [g] is a pre-Lie product generating the Jacobi bracket: The product f •g is associative, and thus U (g) M with the binary operations f, g → f [g] and f, g → f •g forms a unital dipterous algebra [33], however, it has more structure than this. Following [41] we define: Definition 4.11. Let A = I ⊕ A be a unital associative algebra with product f, g → f g, and also equipped with a non-associative composition f, g We assume that D(A) generates A. We call A a D-algebra if for any derivation f ∈ D(A) and any g, h ∈ A we have

Free D-algebras and elementary differentials
The following definitions are detailed in [41]. Let OT denote the alphabet of all ordered (planar) rooted trees: More generally, we consider decorated ordered rooted trees, where C is a (finite or infinite) set of colors. Decorated trees are trees with a color from C assigned to each node. As above, we let OT * denote words of trees (forests), let I be the empty word and let ω 1 , ω 2 → ω 1 ω 2 denote concatenation for ω 1 , ω 2 ∈ OT * . Identifying C ⊂ OT with 1-node trees, we can recursively build all words in OT * from C by concatenation and adding roots. For c ∈ C and ω ∈ OT * , define B + c (ω) ∈ OT as the tree with branches ω and root c. Often we will be interested in the case where C = { }, just one color.
As above, let R OT denote real polynomials (finite R-linear combinations of words) and R OT the dual space of infinite series, such as e.g.
On R OT we define left grafting (·)[·] : R OT ×R OT → R OT by linearity and for all c ∈ C, all τ ∈ OT and all ω, ω ∈ OT * we define: Compare this with Lemma 4.10. The left grafting τ [ω] is obtained by attaching τ in all possible ways from the left to the vertices of ω, and (τ τ )[ω] is obtained by attaching from left first τ and then τ on all nodes of ω: We henceforth let |ω| denote the grading counting the total number of nodes, i.e. |c| = 1 for all c ∈ C, |ωω | = |ω| + |ω | and |ω[ω ]| = |ω| + |ω |.
Proposition 4.13. Let OT be planar trees decorated with colors C. Consider N = R OT with concatenation ω, ω → ωω , left grafting ω, ω → ω[ω ] and unit I as defined above. N is a free D-algebra over C, such that for any D-algebra A and any map ν : C → D(A) there exists a unique D-algebra homomorphism map F ν : N → A such that F ν (c) = ν(c) for all c ∈ C.
Definition 4.14. We define the ordered Grossman-Larson 4 product on N for all ω, ω ∈ OT * as I.e. we add a root to ω , graft on ω and finally remove the root again.  [8]). These are explicitly given in (2.3). The images of the forests F(ω), for ω ∈ OT * , are called elementary differential operators in Merson's theory (see [35]).

A generalized Connes-Kreimer Hopf algebra of planar trees
We recall from [41] the definition of the Hopf algebra H N . On the vector space R OT we define the shuffle product , and we define the coproduct ∆ N as the dual of the ordered GL product, i.e. such that (α•β)(ω) = (ω)∆ N α(ω (1) )β(ω (2) ) for all α, β ∈ R OT }. (4.30) The motivation for this construction is the representation of U (X M) in terms of a frame g ⊂ X M as U (g) M . The shuffle product is the correct product to characterize which series in R OT represent vector fields on M and which represent diffeomorphisms. The composition in U (X M) appears as the product • on U (g) M , thus with the coproduct ∆ N the convolution on R OT represents composition in U (X M). It remains to give a precise characterization of ∆ N and the antipode in H N . As in the Connes-Kreimer case, both ∆ N and the antipode can be defined directly in terms of admissible cuts or in a recursive fashion. Recursively ∆ N is given as where τ = B + c (ω 1 ) ∈ OT, where ω, ω 1 ∈ OT * and where · denotes shuffle on the left and concatenation on the right, (ω 1 ⊗τ 1 ) ·(ω 2 ⊗τ 2 ) = (ω 1 ω 2 )⊗(τ 1 τ 2 ). The direct formula is given as where FALC denoted Full Admissible Left Cuts, P (ω) is the shuffle of all the cut off parts, and R (ω) is the remaining part containing the root, see [41]. Calculations of the coproduct for forests up to order 4 can be found in Table 1. Then H N is a Hopf algebra with an antipode S N given by the recursion S N (I) = I, where τ = B + i (ω 1 ) ∈ OT and ω, ω 1 ∈ OT * .

Lie-Butcher series and flows on manifolds
The set of maps U (g) M from M to U (g) is a D-algebra where the derivations are the vector fields g M . Thus, given a set of colors C and a map ν : C → g M there exists a unique map F ν : N → U (g) M such that for all c ∈ C and all g, h ∈ N we have Note that N can be turned into a Hopf algebra two different ways: either as H Sh with product and deconcatenation coproduct ∆ d , or as H N with the same product , but where the coproduct ∆ N is the dual of the ordered GL product. This gives rise to two different convolutions on N * , the frozen composition α, β → αβ in Example 3.10, and the non-frozen composition α, β → α•β as in (4.30). Since the product is the same, we have that the characters and the infinitesimal characters are the same as vector spaces Hovever, the exponential, logarithm, Dynkin and Eulerian idempotents, as well as the antipode depend on whether they are based on H Sh or H N . Which to use in practice depends on which operation we want to express on the manifold. Recall that frozen elements of U (g) M are constant functions g : M → U (g). If g is frozen then f [g] = 0 for all f , and hence f •g = f g. The subalgebra of frozen vector fields thus reduces to H Sh .
We summarize the basic properties of LB-series: B t sends infinitesimal characters to (formal) vector fields on M and characters to pullback series representing formal diffeomorphisms on M. LB-series preserve both frozen and non-frozen composition and sends left grafting to the connection on U (g) M , Note that if α ∈ G(H N ), then α[β] represents algebraically the pullback (parallel transport) of β along the flow of α. On the manifold where Φ is the diffeomorphism represented by α ∈ G(H N ) at t = h. Since the connection is flat, the pullback depends only on the endpoint Φ(y 0 ) and not on the actual path.
There are (at least) three ways to represent a flow y 0 → y t = Φ t (y 0 ) on M, using LB-series: 1. In terms of pullback series. Find α ∈ G(H N ) such that ψ(y(t)) = B t (α)[ψ](y 0 ) for any ψ ∈ U (g) M . (4.40) This representation is used in the analysis of Crouch-Grossman methods by Owren and Marthinsen [44]. In the classical setting, this is called a S-series [42].
2. In terms of an autonomous differential equation. Find β ∈ g(H N ) such that y(t) solves In the classical setting, this is called backward error analysis. In the Lie group setting, this formulation has, however, never been investigated in detail (but it should!).
3. In terms of a non-autonomous equation of Lie type (time dependent frozen vector field). Find γ ∈ g(H Sh ) such that y(t) solves This representation is used in [37,38]. In the classical setting this is (almost) the standard definition of B-series. The connection with the classical B-series is discussed below.
The algebraic relationship between α, β and γ is given as follows: where f t = f (y(t)) ∈ g is the pullback of f along the time dependent flow of f t . Letting This is known as a combinatorial Dyson-Schwinger equation [24]. Solving by iteration yields Remarkably, the LB-series of the exact solution is just a combination of trees, and not commutators of trees. Thus in Type 3 LB-series developments of numerical integrators, commutators of trees must be zero up to to the order of the method.
Composition and inverse is simplest for pullback series, Type 1. For series of Type 3, we must map to Type 1, compose (or invert) and map back again. If γ,γ are series of Type 3, then the basic operations are done as:

Relations to classical B-series
The relation between classical B-series and LB-series is detailed in [41]. Classical B-series are expressed in terms of linear combinations of non-planar trees T , resulting in the Connes-Kreimer Hopf algebra H C built from non-planar trees [4]. In the classical setting the connection is torsionfree, and concatenation is commutative. Therefore g(H C ) = span(T ). That is, g(H C ) is just linear combinations of trees. This fact is the reason why many discussions in the classical setting can avoid series involving forests of trees (words in T * ). Also the difference between series of Type 1 and Type 3 is in many papers not emphasized. Since the coefficients κ of the Q-polynomials add up to one under symmetrization, we find in the classical setting that Q(α)(ω) = α(τ 1 )α(τ 2 ) · · · α(τ k )ω, for ω = B + (τ 1 τ 2 · · · τ k ), thus formulas involving pullbacks are often expressed directly from Bseries (Type 3) using the Q-polynomials in this form. Our claim that classical B-series fits best into series of Type 3, is based on the trivial observation that the curve y t = B t (α)(y) in (4.42) solves a differential equation with a time dependent frozen vector field given as A question is why the symmetrization σ(τ ) is natural to include in the classical setting, but not in the LB-series setting. To explain the relationship between the two theories we define a symmetrization operator: The shuffle product permutes the trees in a forest in all possible ways, and the symmetrization of a tree is a recursive splitting in sums over all permutations of the branches. The symmetrization defines an equivalence relation on OT * , that is Ω(ω 1 ) = Ω(ω 2 ) ⇐⇒ ω 1 ∼ ω 2 .
Let ι : H C → H N be an inclusion where a tree is identified with one of its equivalent planar trees. In [41] we show thatΩ = Ω•ι : H C → H N is a Hopf algebra isomorphism onto its image, i.e. H C is a proper subalgebra of H N . The adjoint mapΩ * : H * N → H * C is given as The tree symmetrization σ(ω) enters exactly such that the LB-series as given in (4.18) maps to the classical B-series in (2.2).

Substitution law for LB-series
The so-called substitution law for B-series [14] can without much difficulty be generalized to LB series. Consider N as a D-algebra where the derivations are the Lie polynomials D(N ) = g(H N ) ∩ N . By the universality property of N , we know that for any map a : C → D(N ) there exists a unique D-algebra homomorphism F a : N → N such that F a (c) = a(c) for all a ∈ C. This is called the substitution law. The properties of this substitution law, together with applications of it, will be studied in a forthcoming paper. We just mention that many of the useful properties of the substitution law follow immediately from the fact that a : N → N is a homomorphism. For example, for all n, n ∈ N we have: a I = I a (nn ) = (a n)(a n ) a (n[n ]) = (a n)[a n ] a (n•n ) = (a n)•(a n )

Final remarks and outlook
Inspired by problems in numerical analysis we have discussed various algebraic structures arising in the study of formal diffeomorphisms on manifolds. We have seen that the Connes-Kreimer Hopf algebra naturally extends from commutative frames on R n to non-commutative frames on general manifolds. In particular we have presented the Dynkin and Euler operators and non-commutative Faà di Bruno type bialgebras in this generalized setting.
The formalism in this paper has many applications in numerical analysis, and analysis of Lie group integrators in particular. However, the underlying structures are general constructions with possible applications in other fields, such as geometric control theory and sub-Riemannian geometry. Connections to stochastic differential equations on manifolds is an other topic which is worth investigating further.