Trees FAQ
Q. Is it possible to multiply two trees?
It turns out that there is a natural multiplication on two rooted trees which is described in the 1989 paper [1]. A simple description of this multiplication is contained in [2].
It also turns out that not only is there a natural multiplication, but also a natural co-multiplication so that the algebra of rooted trees is a Hopf algebra [1].
Here are some simple examples:
Q. What are some of the applications of this Hopf algebraic structure on trees?
There are a wide variety of different applications, including:
- Symbolic computation. There is a natural homomorphism from higher order derivations to the Hopf algebra of trees which can be used to simplify symbolic expressions involving higher order derivations [6], [8].
- Geometric numerical integration. For example, computing Taylor series on Lie groups using the Hopf algebra of trees yields Runge-Kutta type integrators for any Lie Group [7].
- Nilpotent flows. A closely related algebra of trees called the Hall algebra can be used to compute explicitly nilpotent flows, even in very high dimensions [3].
- Nilpotent approximations. Nonlinear vector fields have linear approximations at each point. More generally, if certain symmetries are present, there are also higher order nilpotent approximations [4].
- Realization theorems. Realization theorems, which are formal series attached to nonlinear systems, relate the input-output representation and the state representation. In [5], a realization theorem is proved which generalizes the Fliess' realization theorem, as well as providing a realization theorem for Hopf algebras of trees.
Q. What is some recent work in this area?
In a 1999 paper, Alain Connes and Dirk Kreimer define a Hopf algebra of trees and describe in detail how this Hopf algebra gives a natural description of certain renormalization operations in quantum field theory (A. Connes and D. Kreimer, Hopf algebras, renormalization and noncommutative geometry, Communication in Mathematical Physics, Volume 199, pages 203-242, 1998.). There has been a fair amount of recent work on the Connes-Kreimer algebra.
It turns out that this Hopf algebra is dual to the Hopf algebra defined in [1], which is sometimes called the Grossman-Larson algebra. A nice description of both algebras and several applications using them is in the book: Elements of Noncommutative Geometry, by Joseph C. Varilly, Hector Figueroa, Jose M. Gracia-Bondia, Birkhauser Advanced Texts, 2000. Michael Hoffman has provided a nice proof of the isomorphism in Combinatorics of rooted trees and Hopf algebras, Transactions of the Amererican Mathematial Society Volume 355 (2003), pages 3795-3811.
References.
- R. Grossman and R. Larson, Hopf algebraic structures of families of trees, Journal Algebra, Vol. 26, 1989, pp. 184-210. draft in pdf
- R. Grossman and R. Larson, Hopf-algebraic structure of combinatorial objects and differential operators, Israel Journal Mathematics, Vol. 72, 1990, pp. 109-117. draft in pdf
- M. Grayson and R. Grossman, Models for free, nilpotent Lie algebras, Journal Algebra, Vol. 35, 1990, pp. 177-191. draft in pdf
- R. Grossman and R. Larson, Solving nonlinear equations from higher order derivations in linear stages, Advances in Mathematics, Vol. 82, 1990, pp. 180-202. draft in pdf
- R. Grossman and R. G. Larson, The realization of input-output maps using bialgebras, Forum Mathematicum, Volume 4, pp. 109-121, 1992. draft in pdf
- R. Grossman and R. Larson, The symbolic computation of derivations using labeled trees, Journal of Symbolic Computation, Volume 13, pp. 511-523, 1992. draft in pdf
- P. Crouch and R. Grossman, Numerical integration of ordinary differential equations on manifolds, Journal of Nonlinear Science, Volume 3, pp. 1-33, 1993.
- R. Grossman and R. G. Larson, Labeled trees and the efficient computation of derivations, Proceedings of 1989 International Symposium on Symbolic and Algebraic Computation, ACM, 1989, pp. 74-80. draft in pdf
- P. Crouch, R. Grossman, and R. G. Larson, Computations involving differential operators and their actions on functions, Proceedings of 1991 International Symposium on Symbolic and Algebraic Computation, ACM, 1991, pp. 301-307.
- P.E. Crouch and R. L. Grossman, The Explicit Computation of Integration Algorithms and First Integrals for Ordinary Differential Equations With Polynomial Coefficients Using Trees, Proceedings of the 1992 International Symposium on Symbolic and Algebraic Computation, ACM Press, pp. 89-94. draft in pdf
Here are some additional articles about trees and their applications:
- R. Grossman, The evaluation of expressions involving higher order derivations, Journal of Mathematical Systems, Estimation, and Control, Vol. 1, 1991, pp. 91-106.
- R. Grossman and R. Larson, The symbolic computation of higher order derivations: symmetries of expressions and actions of group algebras, Differential Geometry: The Interface Between Pure and Applied Mathematics, Contemporary Mathematics, 68, M. Luksic, C. Martin and W. Shadwick, editors, American Mathematical Society, Providence, 1987, pp. 121-131.
- R. Grossman and R. Larson, Labeled trees and the algebra of differential operators, Graphs and Algorithms, Contemporary Mathematics, 89, B. Richter, editor, American Mathematical Society, Providence, 1989, pp. 81-87.
- M. Grayson and R. Grossman, Nilpotent Lie algebras and vector fields, Symbolic Computation: Applications to Scientific Computing, R. Grossman, editor, SIAM, Philadelphia, 1989, pp. 77-96.
- R. Grossman, Using trees to compute approximate solutions of ordinary differential equations exactly, Differential Equations and Computer Algebra M. Singer, editor, Academic Press, New York, 1991, pp. 29-59.
- R. Grossman and R. G. Larson, The symbolic computation of vector field expressions, Algebraic Computing in Control 1991, edited by G. Jacob and F. Lamnabhi-Lagarrigue, Springer-Verlag, Berlin, 1991, pp. 1-10.
- R. Grossman and D. Radford, A simple construction of bialgebra deformations, Contemporary Mathematics: Quantum Groups and Deformations, AMS, pp. 115-117, 1992.
rlg, 8/28/03