Butcher group

Template:Short description In mathematics, the Butcher group, named after the New Zealand mathematician John C. Butcher by Template:Harvtxt, is an infinite-dimensional Lie group first introduced in numerical analysis to study solutions of non-linear ordinary differential equations by the Runge–Kutta method. It arose from an algebraic formalism involving rooted trees that provides formal power series solutions of the differential equation modeling the flow of a vector field. It was Template:Harvtxt, prompted by the work of Sylvester on change of variables in differential calculus, who first noted that the derivatives of a composition of functions can be conveniently expressed in terms of rooted trees and their combinatorics.

Template:Harvtxt pointed out that the Butcher group is the group of characters of the Hopf algebra of rooted trees that had arisen independently in their own work on renormalization in quantum field theory and Connes' work with Moscovici on local index theorems. This Hopf algebra, often called the Connes–Kreimer algebra, is essentially equivalent to the Butcher group, since its dual can be identified with the universal enveloping algebra of the Lie algebra of the Butcher group. As they commented: Template:Cquote

Differentials and rooted trees

Rooted trees with two, three and four nodes, from Cayley's original article

A rooted tree is a graph with a distinguished node, called the root, in which every other node is connected to the root by a unique path. If the root of a tree t is removed and the nodes connected to the original node by a single bond are taken as new roots, the tree t breaks up into rooted trees t₁, t₂, ... Reversing this process a new tree t = [t₁, t₂, ...] can be constructed by joining the roots of the trees to a new common root. The number of nodes in a tree is denoted by |t|. A heap-ordering of a rooted tree t is an allocation of the numbers 1 through |t| to the nodes so that the numbers increase on any path going away from the root. Two heap orderings are equivalent, if there is an automorphism of rooted trees mapping one of them on the other. The number of equivalence classes of heap-orderings on a particular tree is denoted by α(t) and can be computed using the Butcher's formula:

$\alpha (t)=\frac{|t|!}{t!|S_t|},$

where S_t denotes the symmetry group of t and the tree factorial is defined recursively by

$[t_1,\dots ,t_n]!=|[t_1,\dots ,t_n]|\cdot t_1!\cdots t_n!$

with the tree factorial of an isolated root defined to be 1

$\bullet !=1.$

The ordinary differential equation for the flow of a vector field on an open subset U of R^N can be written

$\frac{dx(s)}{ds}=f(x(s)),x(0)=x_0,$

where x(s) takes values in U, f is a smooth function from U to R^N and x₀ is the starting point of the flow at time s = 0.

Template:Harvtxt gave a method to compute the higher order derivatives x^(m)(s) in terms of rooted trees. His formula can be conveniently expressed using the elementary differentials introduced by Butcher. These are defined inductively by

${\delta }_{\bullet }^i=f^i,{\delta }_{[t_1,\dots ,t_n]}^i=\sum _{j_1,\dots ,j_n=1}^N({\delta }_{t_1}^{j_1}\cdots {\delta }_{t_n}^{j_n}){\partial }_{j_1}\cdots {\partial }_{j_n}{f}^i.$

With this notation

$\frac{d^{m}x}{d{s}^m}=\sum _{|t|=m}\alpha (t){\delta }_t,$

giving the power series expansion

$x(s)=x_0+\sum _t\frac{s^{|t|}}{|t|!}\alpha (t){\delta }_t(0).$

As an example when N = 1, so that x and f are real-valued functions of a single real variable, the formula yields

$x^{(4)}=f^{\prime \prime \prime }{f}^3+3f^{\prime \prime }{f}^{\prime }{f}^2+f^{\prime }{f}^{\prime \prime }{f}^2+(f^{\prime }{)}^{3}f,$

where the four terms correspond to the four rooted trees from left to right in Figure 3 above.

In a single variable this formula is the same as Faà di Bruno's formula of 1855; however in several variables it has to be written more carefully in the form

$x^{(4)}=f^{\prime \prime \prime }(f,f,f)+3f^{\prime \prime }(f,f^{\prime }(f))+f^{\prime }(f^{\prime \prime }(f,f))+f^{\prime }(f^{\prime }(f^{\prime }(f))),$

where the tree structure is crucial.

Definition using Hopf algebra of rooted trees

The Hopf algebra H of rooted trees was defined by Template:Harvtxt in connection with Kreimer's previous work on renormalization in quantum field theory. It was later discovered that the Hopf algebra was the dual of a Hopf algebra defined earlier by Template:Harvtxt in a different context. The characters of H, i.e. the homomorphisms of the underlying commutative algebra into R, form a group, called the Butcher group. It corresponds to the formal group structure discovered in numerical analysis by Template:Harvtxt.

The Hopf algebra of rooted trees H is defined to be the polynomial ring in the variables t, where t runs through rooted trees.

• Its comultiplication $\mathrm{\Delta }:H\to H\otimes H$ is defined by

$\mathrm{\Delta }(t)=t\otimes I+I\otimes t+\sum _{s\subset t}s\otimes [t\mathrm{\setminus }s],$

where the sum is over all proper rooted subtrees s of t; $[t\mathrm{\setminus }s]$ is the monomial given by the product the variables t_i formed by the rooted trees that arise on erasing all the nodes of s and connected links from t. The number of such trees is denoted by n(t\s).

• Its counit is the homomorphism ε of H into R sending each variable t to zero.
• Its antipode S can be defined recursively by the formula

$S(t)=-t-\sum _{s\subset t}(-1{)}^{n(t\mathrm{\setminus }s)}S([t\mathrm{\setminus }s])s,S(\bullet )=-\bullet .$

The Butcher group is defined to be the set of algebra homomorphisms φ of H into R with group structure

${\phi }_1\star {\phi }_2(t)=({\phi }_1\otimes {\phi }_2)\mathrm{\Delta }(t).$

The inverse in the Butcher group is given by

${\phi }^{-1}(t)=\phi (St)$

and the identity by the counit ε.

Using complex coefficients in the construction of the Hopf algebra of rooted trees one obtains the complex Hopf algebra of rooted trees. Its C-valued characters form a group, called the complex Butcher group G_C. The complex Butcher group G_C is an infinite-dimensional complex Lie group which appears as a toy model in the Template:Section link of quantum field theories.

Butcher series and Runge–Kutta method

The non-linear ordinary differential equation

$\frac{dx(s)}{ds}=f(x(s)),x(0)=x_0,$

can be solved approximately by the Runge–Kutta method. This iterative scheme requires an m x m matrix

$A=(a_{ij})$

and a vector

$b=(b_i)$

with m components.

The scheme defines vectors x_n by first finding a solution X₁, ... , X_m of

$X_i=x_{n-1}+h\sum _{j=1}^m{a}_{ij}f(X_j)$

and then setting

$x_n=x_{n-1}+h\sum _{j=1}^m{b}_{j}f(x_j).$

Template:Harvtxt showed that the solution of the corresponding ordinary differential equations

$X_i(s)=x_0+s\sum _{j=1}^m{a}_{ij}f(X_j(s)),x(s)=x_0+s\sum _{j=1}^m{b}_{j}f(X_j(s))$

has the power series expansion

$X_i(s)=x_0+\sum _t\frac{s^{|t|}}{|t|!}\alpha (t)t!\sum _{j=1}^m{a}_{ij}{\phi }_j(t){\delta }_t(0),x(s)=x_0+\sum _t\frac{s^{|t|}}{|t|!}\alpha (t)t!\phi (t){\delta }_t(0),$

where φ_j and φ are determined recursively by

${\phi }_j(\bullet )=1.{\phi }_i([t_1,\cdots ,t_k])=\sum _{j_1,\dots ,j_k}{a}_{i{j}_1}\dots a_{i{j}_k}{\phi }_{j_1}(t_1)\dots {\phi }_{j_k}(t_k)$

and

$\phi (t)=\sum _{j=1}^m{b}_j{\phi }_j(t).$

The power series above are called B-series or Butcher series. The corresponding assignment φ is an element of the Butcher group. The homomorphism corresponding to the actual flow has

$\mathrm{\Phi }(t)=\frac{1}{t!}.$

Butcher showed that the Runge–Kutta method gives an nth order approximation of the actual flow provided that φ and Φ agree on all trees with n nodes or less. Moreover, Template:Harvtxt showed that the homomorphisms defined by the Runge–Kutta method form a dense subgroup of the Butcher group: in fact he showed that, given a homomorphism φ', there is a Runge–Kutta homomorphism φ agreeing with φ' to order n; and that if given homomorphims φ and φ' corresponding to Runge–Kutta data (A, b) and (A' , b' ), the product homomorphism $\phi \star {\phi }^{\prime }$ corresponds to the data

$\left(\begin{array}{cc}A& 0\\ 0& A^{\prime }\end{array}\right),(b,b^{\prime }).$

Template:Harvtxt proved that the Butcher group acts naturally on the functions f. Indeed, setting

$\phi \circ f=1+\sum _t\frac{s^{|t|}}{|t|!}\alpha (t)t!\phi (t){\delta }_t(0),$

they proved that

${\phi }_1\circ ({\phi }_2\circ f)=({\phi }_1\star {\phi }_2)\circ f.$

Lie algebra

Template:Harvtxt showed that associated with the Butcher group G is an infinite-dimensional Lie algebra. The existence of this Lie algebra is predicted by a theorem of Template:Harvtxt: the commutativity and natural grading on H implies that the graded dual H* can be identified with the universal enveloping algebra of a Lie algebra $𝔤$. Connes and Kreimer explicitly identify $𝔤$ with a space of derivations θ of H into R, i.e. linear maps such that

$\theta (ab)=\epsilon (a)\theta (b)+\theta (a)\epsilon (b),$

the formal tangent space of G at the identity ε. This forms a Lie algebra with Lie bracket

$[{\theta }_1,{\theta }_2](t)=({\theta }_1\otimes {\theta }_2-{\theta }_2\otimes {\theta }_1)\mathrm{\Delta }(t).$

$𝔤$ is generated by the derivations θ_t defined by

${\theta }_t(t^{\prime })={\delta }_{t{t}^{\prime }},$

for each rooted tree t.

The infinite-dimensional Lie algebra $𝔤$ from Template:Harvtxt and the Lie algebra L(G) of the Butcher group as an infinite-dimensional Lie group are not the same. The Lie algebra L(G) can be identified with the Lie algebra of all derivations in the dual of H (i.e. the space of all linear maps from H to R), whereas $𝔤$ is obtained from the graded dual. Hence $𝔤$ turns out to be a (strictly smaller) Lie subalgebra of L(G).

Renormalization

Template:Harvtxt provided a general context for using Hopf algebraic methods to give a simple mathematical formulation of renormalization in quantum field theory. Renormalization was interpreted as Birkhoff factorization of loops in the character group of the associated Hopf algebra. The models considered by Template:Harvtxt had Hopf algebra H and character group G, the Butcher group. Template:Harvtxt has given an account of this renormalization process in terms of Runge–Kutta data.

In this simplified setting, a renormalizable model has two pieces of input data:

• a set of Feynman rules given by an algebra homomorphism Φ of H into the algebra V of Laurent series in z with poles of finite order;
• a renormalization scheme given by a linear operator R on V such that R satisfies the Rota–Baxter identity

$R(fg)+R(f)R(g)=R(fR(g))+R(R(f)g)$

and the image of R – id lies in the algebra V₊ of power series in z.

Note that R satisfies the Rota–Baxter identity if and only if id – R does. An important example is the minimal subtraction scheme

$R(\sum _n{a}_n{z}^n)=\sum _{n<0}{a}_n{z}^n.$

In addition there is a projection P of H onto the augmentation ideal ker ε given by

$P(x)=x-\epsilon (x)1.$

To define the renormalized Feynman rules, note that the antipode S satisfies

$m\circ (S\otimes \mathrm{i}\mathrm{d})\mathrm{\Delta }(x)=\epsilon (x)1$

so that

$S\circ P=P\circ S=-m\circ (S\otimes P)\mathrm{\Delta },$

The renormalized Feynman rules are given by a homomorphism ${\mathrm{\Phi }}_S^R$ of H into V obtained by twisting the homomorphism Φ • S. The homomorphism ${\mathrm{\Phi }}_S^R$ is uniquely specified by

${\mathrm{\Phi }}_S^R=-m(S\otimes {\mathrm{\Phi }}_S^R\circ P)\mathrm{\Delta }.$

Because of the precise form of Δ, this gives a recursive formula for ${\mathrm{\Phi }}_S^R$.

For the minimal subtraction scheme, this process can be interpreted in terms of Birkhoff factorization in the complex Butcher group. Φ can be regarded as a map γ of the unit circle into the complexification G_C of G (maps into C instead of R). As such it has a Birkhoff factorization

$\gamma (z)={\gamma }_{-}(z{)}^{-1}{\gamma }_{+}(z),$

where γ₊ is holomorphic on the interior of the closed unit disk and γ_– is holomorphic on its complement in the Riemann sphere C $\cup \{\mathrm{\infty }\}$ with γ_–(∞) = 1. The loop γ₊ corresponds to the renormalized homomorphism. The evaluation at z = 0 of γ₊ or the renormalized homomorphism gives the dimensionally regularized values for each rooted tree.

In example, the Feynman rules depend on additional parameter μ, a "unit of mass". Template:Harvtxt showed that

${\partial }_{\mu }{\gamma }_{\mu -}=0,$

so that γ_μ– is independent of μ.

The complex Butcher group comes with a natural one-parameter group λ_w of automorphisms, dual to that on H

${\lambda }_w(t)=w^{|t|}t$

for w ≠ 0 in C.

The loops γ_μ and λ_w · γ_μ have the same negative part and, for t real,

$F_t=\underset{z=0}{\lim }{\gamma }_{-}(z){\lambda }_{tz}({\gamma }_{-}(z{)}^{-1})$

defines a one-parameter subgroup of the complex Butcher group G_C called the renormalization group flow (RG).

Its infinitesimal generator β is an element of the Lie algebra of G_C and is defined by

$\beta ={\partial }_t{F}_t{|}_{t=0}.$

It is called the beta function of the model.

In any given model, there is usually a finite-dimensional space of complex coupling constants. The complex Butcher group acts by diffeomorphisms on this space. In particular the renormalization group defines a flow on the space of coupling constants, with the beta function giving the corresponding vector field.

More general models in quantum field theory require rooted trees to be replaced by Feynman diagrams with vertices decorated by symbols from a finite index set. Connes and Kreimer have also defined Hopf algebras in this setting and have shown how they can be used to systematize standard computations in renormalization theory.

Example

Template:Harvtxt has given a "toy model" involving dimensional regularization for H and the algebra V. If c is a positive integer and q_μ = q / μ is a dimensionless constant, Feynman rules can be defined recursively by

$\mathrm{\Phi }([t_1,\dots ,t_n])=\int \frac{\mathrm{\Phi }(t_1)\cdots \mathrm{\Phi }(t_n)}{|y{|}^2+q_{\mu }^2}(|y{|}^2{)}^{-z(\frac{c}{2}-1)}{d}^{D}y,$

where z = 1 – D/2 is the regularization parameter. These integrals can be computed explicitly in terms of the Gamma function using the formula

$\int \frac{(|y{|}^2{)}^{-u}}{|y{|}^2+q_{\mu }^2}{d}^{D}y={\pi }^{D/2}(q_{\mu }^2{)}^{-z-u}\frac{\mathrm{\Gamma }(-u+D/2)\mathrm{\Gamma }(1+u-D/2)}{\mathrm{\Gamma }(D/2)}.$

In particular

$\mathrm{\Phi }(\bullet )={\pi }^{D/2}(q_{\mu }^2{)}^{-zc/2}\frac{\mathrm{\Gamma }(1+cz)}{cz}.$

Taking the renormalization scheme R of minimal subtraction, the renormalized quantities ${\mathrm{\Phi }}_S^R(t)$ are polynomials in $\log q_{\mu }^2$ when evaluated at z = 0.

References

• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation (also in Volume 3 of the Collected Works of Cayley, pages 242–246)
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation, Chapter 14.
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• John C. Butcher: "B-Series : Algebraic Analysis of Numerical Methods", Springer（SSCM, volume 55), ISBN 978-3030709556 (April, 2021).