Benutzer:CoTangent/Butcher-Gruppe

Im mathematischen Teilgebiet der Numerik bezeichnet die Butcher-Gruppe eine bestimmte Gruppe, die beim Studium von Runge-Kutter-Verfahren zur Lösung von gewöhnlichen Differenzialgleichungen auftritt. Sie ist nach dem neuseeländischen Mathematiker John C. Butcher benannt.

Connes und Kreimer haben 1999 herausgefunden, dass diese Gruppe außerdem die Charaktergruppe einer bestimmten Hopf-Algebra über gewurzelten Bäumen auftritt und dass diese bereits vollkommen unabhängig von der Verbindung zur Numerik in der Renormierung von Quantenfeldtheorien in der Physik verwendet wurde.

Motivation: Anfangswertproblem

Viele Vorgänge in Natur und Technik lassen sich mit Hilfe von gewöhnlichen Differentialgleichungen formulieren. Eine solche Gleichung lässt sich immer in die folgende Form bringen:

$\displaystyle {dx(s) \over ds}=f(x(s)),\,\,x(0)=x_{0},$

Hierbei ist $f:U\to \mathbb {R} ^{N}$ ein (zeitunabhängiges) Vektorfeld auf einer offenen Menge $U\subseteq \mathbb {R} ^{N}$. Wenn wie hier der Wert $x_{0}\in U$ ist vorgegeben ist, spricht man auch von einem Anfangswertproblem.

Wenn das Vektorfeld $f$ beliebig oft differenzierbar ist, dann folgt aus dem Satz von Picard-Lindelöf, dass dieses Anfangswertproblem eine eindeutige Lösung besitzt und diese Lösungskurve selbst auch beliebig oft differenzierbar ist. Allerdings ist es meistens nicht möglich, die Lösung in einer geschlossenen Form anzugeben.

Eine Möglichkeit, die Lösung zu untersuchen ist ein Potenzreihenansatz um den Punkt $0$: Dafür benötigt man die höheren Ableitungen der gesuchten Funktion, also $x'(s),x''(s),x^{(3)}(s),\ldots$. Hierzu kann man grundsätzlich die gegebene Differentialgleichung einfach mehrfach ableiten, aber da jedes Mal mehr Terme hinzukommen, wird die Sache schnell unübersichtlich. Im Jahre 1857 fand Arthur Cayley eine kompkate Formel, um die höheren Ableitungen einer Lösung $x$ eines Anfangswertproblems zu berechnen, hierfür benötigen wir aber als kombinatorische Hilfsmittel gewurzelte Bäume:

Differentiale und gewurzelte Bäume

Die gewurzelten Bäume mit zwei, drei und vier Knoten, aus Cayleys Originalarbeit

Ein gewurzelter Baum ist ein Graph mit einem ausgezeichneten Knoten, genannt Wurzel, in dem jeder andere Knoten mit der Wurzel durch einen eindeutigen Weg verbunden ist. Wenn die Wurzel eines gewurzelten Baumes $t$ (mit allen $m$ Kanten, die an sie angrenzen) entfernt wird, dann zerfällt der Originalbaum in $m$ gewurzelte Bäume $t_{1},\ldots ,t_{m}$, wobei als Wurzeln der neuen Bäume immer die Knoten genommen werden, die mit der Orginalwurzel verbunden waren. Umgekehrt kann man immer aus $m$ verschiedenen gewurzelten Bäumen $t_{1},\ldots ,t_{m}$ einen neuen Baum $t$ konstruieren, indem man eine neue Wurzel hinzufügt und diese mit allen bisherigen Wurzeln verbindet. Diesen neuen Baum bezeichnet man auch mit eckigen Klammern: $t=[t_{1},\ldots ,t_{m}]$.

Die Anzahl der Knoten eines Baumes $t$ bezeichnet man mit $|t|$. Der Baum mit nur einem Knoten (die isolierte Wurzel) wird mit $t=\bullet$ bezeichnet.

Eine Heap-Ordnung auf einem Baum $t$ ist eine Verteilung der Zahlen $\{1,\ldots ,|t|\}$ auf die Knoten des Graphen, sodass die Zahlen immer in aufsteigender Reihenfolge erscheinen, wenn man sich auf einem Weg von der Wurzel wegbewegt. Zwei Heap-Ordnungen heißen äquivalent, wenn einen Automorphismus von gewurzelten Bäumen gibt, der die eine Heap-Ordnung auf die andere überträgt. Die Anzahl der Äquivalenzklassen von Heap-Ordnungen wird mit $\alpha (t)$ bezeichnet und kann mit Butchers Formel berechnet werden:

$\displaystyle \alpha (t)={|t|! \over t!|S_{t}|},$

wobei $S_{t}$ die Symmetriegruppe von $t$ ist und die Fakultät eines Baumes rekursiv definiert wird durch

$[t_{1},\dots ,t_{n}]!=|[t_{1},\dots ,t_{n}]|\cdot t_{1}!\cdots t_{n}!$

und die Fakultät einer isolierten Wurzel auf $1$ gesetzt wird:

$\bullet !=1.$

Als nächstes definieren wir die sogenannten elementaren Differentiale rekursiv:

$\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}.$

Unter Verwendung dieser Notation gibt es nun eine kompakte Darstellung der $m$-ten Ableitung der Lösungskurve:

${d^{m}x \over ds^{m}}=\sum _{|t|=m}\alpha (t)\delta _{t},$

Im einfachsten Fall N = 1 (dann sind x und f reellwertige Funktionen einer reellen Variable) ergibt die obige Formel:

$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,$

wobei die vier Terme genau den vier gewurzelten Bäumen auf vier Knoten entsprechen (siehe Diagramm). Im Falle N = 1 entspricht diese Formel der bereits früher bekannten Formel_von_Faà_di_Bruno von 1855, in der die Baumstruktur keine Rolle spielt. Wenn aber $N>1$, so muss man die Formel vorsichtiger in der folgenden Form schreiben: $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))),$ wobei die Baumstruktur entscheidend wird.

Damit erhalten wir eine geschlossene Formel für die Taylor-Reihe der Lösungskurve mit Entwicklungspunkt 0:

$\displaystyle x(s)=x_{0}+\sum _{t}{s^{|t|} \over |t|!}\alpha (t)\delta _{t}(0).$

--

Butcher series and Runge–Kutta method

Das oben schon erwähnte Anfangswertproblem

${dx(s) \over ds}=f(x(s)),\,\,\,x(0)=x_{0},$

lässt sich näherungsweise mit dem Runge-Kutta-Verfahren lösen. Bei diesem nimmt man eine $m\times m$-Matrix

$A=(a_{ij})$

und einen Vektor

$b=(b_{i})$

mit m Komponenten.

Bei diesem Verfahren werden iterativ Näherungslösungen $x_{n}$ gefunden, indem zuerst eine LösungX₁, ... , 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}).$

Vorlage: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}{s^{|t|} \over |t|!}\alpha (t)t!\sum _{j=1}^{m}a_{ij}\varphi _{j}(t)\delta _{t}(0),\,\,\,\,x(s)=x_{0}+\sum _{t}{s^{|t|} \over |t|!}\alpha (t)t!\varphi (t)\delta _{t}(0),$

where φ_j and φ are determined recursively by

$\varphi _{j}(\bullet )=1.\,\,\,\varphi _{i}([t_{1},\cdots ,t_{k}])=\sum _{j_{1},\dots ,j_{k}}a_{ij_{1}}\dots a_{ij_{k}}\varphi _{j_{1}}(t_{1})\dots \varphi _{j_{k}}(t_{k})$

and

$\varphi (t)=\sum _{j=1}^{m}b_{j}\varphi _{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

$\Phi (t)={1 \over 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, Vorlage: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 $\varphi \star \varphi ^{\prime }$ corresponds to the data

${\begin{pmatrix}A&0\\0&A^{\prime }\\\end{pmatrix}},\,\,(b,b^{\prime }).$

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

$\varphi \circ f=1+\sum _{t}{s^{|t|} \over |t|!}\alpha (t)t!\varphi (t)\delta _{t}(0),$

they proved that

$\varphi _{1}\circ (\varphi _{2}\circ f)=(\varphi _{1}\star \varphi _{2})\circ f.$

---

---

---

---

$\displaystyle x(s)=x_{0}+\sum _{t}{s^{|t|} \over |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 Vorlage: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 Vorlage: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 Vorlage: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 $\Delta :H\rightarrow H\otimes H$ is defined by

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

where the sum is over all proper rooted subtrees s of t; $[t\backslash 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\backslash s)}S([t\backslash s])s,\,\,\,S(\bullet )=-\bullet .$

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

$\varphi _{1}\star \varphi _{2}(t)=(\varphi _{1}\otimes \varphi _{2})\Delta (t).$

The inverse in the Butcher group is given by

$\varphi ^{-1}(t)=\varphi (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 Vorlage:Section link of quantum field theories.

Butcher series and Runge–Kutta method

The non-linear ordinary differential equation

${dx(s) \over 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}).$

Vorlage: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}{s^{|t|} \over |t|!}\alpha (t)t!\sum _{j=1}^{m}a_{ij}\varphi _{j}(t)\delta _{t}(0),\,\,\,\,x(s)=x_{0}+\sum _{t}{s^{|t|} \over |t|!}\alpha (t)t!\varphi (t)\delta _{t}(0),$

where φ_j and φ are determined recursively by

$\varphi _{j}(\bullet )=1.\,\,\,\varphi _{i}([t_{1},\cdots ,t_{k}])=\sum _{j_{1},\dots ,j_{k}}a_{ij_{1}}\dots a_{ij_{k}}\varphi _{j_{1}}(t_{1})\dots \varphi _{j_{k}}(t_{k})$

and

$\varphi (t)=\sum _{j=1}^{m}b_{j}\varphi _{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

$\Phi (t)={1 \over 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, Vorlage: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 $\varphi \star \varphi ^{\prime }$ corresponds to the data

${\begin{pmatrix}A&0\\0&A^{\prime }\\\end{pmatrix}},\,\,(b,b^{\prime }).$

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

$\varphi \circ f=1+\sum _{t}{s^{|t|} \over |t|!}\alpha (t)t!\varphi (t)\delta _{t}(0),$

they proved that

$\varphi _{1}\circ (\varphi _{2}\circ f)=(\varphi _{1}\star \varphi _{2})\circ f.$

Lie algebra

Vorlage: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 Vorlage: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 ${\mathfrak {g}}$. Connes and Kreimer explicitly identify ${\mathfrak {g}}$ with a space of derivations θ of H into R, i.e. linear maps such that

$\theta (ab)=\varepsilon (a)\theta (b)+\theta (a)\varepsilon (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})\Delta (t).$

${\mathfrak {g}}$ is generated by the derivations θ_t defined by

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

for each rooted tree t.

The infinite-dimensional Lie algebra ${\mathfrak {g}}$ from Vorlage: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 ${\mathfrak {g}}$ is obtained from the graded dual. Hence ${\mathfrak {g}}$ turns out to be a (strictly smaller) Lie subalgebra of L(G).

Renormalization

Vorlage: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 Vorlage:Harvtxt had Hopf algebra H and character group G, the Butcher group. Vorlage: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

$\displaystyle 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

$\displaystyle P(x)=x-\varepsilon (x)1.$

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

$m\circ (S\otimes {\rm {id}})\Delta (x)=\varepsilon (x)1$

so that

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

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

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

Because of the precise form of Δ, this gives a recursive formula for $\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

$\displaystyle \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 \{\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". Vorlage: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,

$\displaystyle F_{t}=\lim _{z=0}\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 diffeomorphims 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

Vorlage: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

$\displaystyle \Phi ([t_{1},\dots ,t_{n}])=\int {\Phi (t_{1})\cdots \Phi (t_{n}) \over |y|^{2}+q_{\mu }^{2}}(|y|^{2})^{-z({c \over 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

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

In particular

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

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

References

• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation (also in Volume 3 of the Collected Works of Cayley, pages 242–246)
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation, Chapter 14.
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation

[[Category:Combinatorics]] [[Category:Numerical analysis]] [[Category:Quantum field theory]] [[Category:Renormalization group]] [[Category:Hopf algebras]]