Abdenacer Makhlouf is a Professor and head of the mathematics department at the University of Haute Alsace, France. His research covers structure, representation theory, deformation theory and cohomology of various types of algebras, including non-associative algebras, Hopf algebras and n-ary algebras.

• PrefacexiAbdenacer MAKHLOUFChapter 1. Algebraic Background for Numerical Methods, Control Theory and Renormalization 1Dominique MANCHON1.1. Introduction 11.2. Hopf algebras: generalproperties 21.2.1. Algebras 21.2.2. Coalgebras 31.2.3. Convolution product 61.2.4. Bialgebras andHopf algebras 71.2.5. Some simple examples of Hopf algebras 81.2.6. Some basic properties of Hopf algebras 91.3. ConnectedHopf algebras 101.3.1. Connectedgradedbialgebras 101.3.2. An example: the Hopf algebra of decorated rooted trees 131.3.3. Connectedfiltered bialgebras 141.3.4. The convolution product 151.3.5. Characters 171.3.6. Group schemes and the Cartier–Milnor–Moore–Quillen theorem 191.3.7. Renormalization in connected filtered Hopf algebras 211.4. Pre-Lie algebras 241.4.1. Definition and general properties 241.4.2. The groupof formalflows 251.4.3. The pre-Lie Poincaré–Birkhoff–Witt theorem 261.5. Algebraicoperads 281.5.1. Manipulatingalgebraicoperations 281.5.2. The operad of multi-linear operations 291.5.3. A definition for linear operads 311.5.4. Afewexamplesof operads 321.6. Pre-Lie algebras (continued) 351.6.1. Pre-Lie algebras and augmented operads 351.6.2. A pedestrian approach to free pre-Lie algebra 361.6.3. Right-sided commutative Hopf algebras and theLoday–Roncotheorem 381.6.4. Pre-Lie algebras of vectorfields 401.6.5. B-series, composition and substitution 421.7. Other related algebraic structures 441.7.1. NAPalgebras 441.7.2. Novikovalgebras 481.7.3. Assosymmetric algebras 481.7.4. Dendriformalgebras 481.7.5. Post-Lie algebras 491.8. References 50Chapter 2. From Iterated Integrals and Chronological Calculus to Hopf and Rota–Baxter Algebras 55Kurusch EBRAHIMI-FARD and Frédéric PATRAS2.1. Introduction 552.2. Generalizediterated integrals 582.2.1. Permutations andsimplices 592.2.2. Descents,NCSFand theBCHformula 642.2.3. Rooted trees and nonlinear differential equations 672.2.4. Flows and Hopf algebraic structures 712.3. Advances in chronological calculus 742.3.1. Chronological calculus and half-shuffles 752.3.2. Chronological calculus and pre-Lie products 792.3.3. Time-ordered products and enveloping algebras 812.3.4. Formal flows and Hopf algebraic structures 832.4. Rota–Baxter algebras 872.4.1. Origin 872.4.2. Definition and examples 912.4.3. Related algebraic structures 952.4.4. Atkinson’s factorization and Bogoliubov’s recursion 1012.4.5. Spitzer’s identity: commutative case 1032.4.6. Free commutativeRota–Baxter algebras 1072.4.7. Spitzer’s identity: noncommutative case 1082.4.8. FreeRota–Baxter algebras 1112.5. References 113Chapter 3. Noncommutative Symmetric Functions, Lie Series and Descent Algebras 119Jean-Yves THIBON3.1. Introduction 1193.2. Classical symmetric functions 1203.2.1. Symmetric polynomials 1203.2.2. The Hopf algebra of symmetric functions 1223.2.3. The λ-ringnotation 1243.2.4. Symmetric functions and formal power series 1253.2.5. Duality 1263.3. Noncommutativesymmetric functions 1293.3.1. Basic definitions 1293.3.2. Generators andlinear bases 1313.3.3. Duality 1333.3.4. Solomon’sdescent algebras 1363.4. Lie series andLie idempotents 1393.4.1. Permutational operators on tensor spaces 1393.4.2. TheHausdorff series 1393.4.3. Lie idempotents in the descent algebra 1433.5. Lie idempotents as noncommutative symmetric functions 1443.5.1. Noncommutativepower-sums 1443.5.2. The Magnus expansion 1463.5.3. The continuous BCH expansion 1483.5.4. Another proof of the Magnus expansion 1503.5.5. The (1 − q)-transform 1503.5.6. Hopf algebras enter the scene 1513.5.7. A one-parameter family of Lie idempotents 1523.5.8. The iterated q-bracketing and its diagonalization 1533.6. Decompositionsof the descent algebras 1553.6.1. Complete families of minimal orthogonal idempotents 1553.6.2. Eulerianidempotents 1563.6.3. GeneralizedEulerianidempotents 1603.7. Decompositionsof the tensor algebra 1603.8. General deformations 1623.9. Lie quasi-idempotents as Lie polynomials 1633.9.1. The left derivative 1633.9.2. Multilinear Lie polynomials 1643.9.3. Decompositions on other bases 1673.10. Permutations and free quasi-symmetric functions 1693.10.1. Free quasi-symmetricfunctions 1693.11. Packed words and word quasi-symmetric functions 1713.12. References 175Chapter 4. From Runge–Kutta Methods to Hopf Algebras of Rooted Trees 179Ander MURUA4.1. Numerical integration methods for ordinary differential equations 1794.1.1. Introduction 1794.1.2. Runge–Kutta methods 1804.2. Algebraic theory of Runge–Kutta methods 1824.2.1. The order conditions of RK methods 1824.2.2. The independence of order conditions 1864.2.3. Proof of necessary and sufficient order conditions 1884.2.4. Composition of RK methods, rooted trees and forests 1914.2.5. TheButchergroup 1954.2.6. Equivalence classes of RK methods 1974.2.7. Bibliographicalcomments 1984.3. B-series and relatedformal expansions 1984.3.1. B-series 1984.3.2. Backward error analysis, the exponential and the logarithm 1994.3.3. Series of linear differentialoperators 2034.3.4. The Lie algebra of the Butcher group 2054.3.5. The pre-Lie algebra structure on g 2064.3.6. Bibliographicalcomments 2094.4. Hopf algebrasof rootedtrees 2094.4.1. The commutative Hopf algebra of rooted trees 2104.4.2. The dual algebra H∗ and the dual Hopf algebra H◦ 2124.4.3. B-series and series of differential operators revisited 2134.4.4. A universal property of the commutative Hopf algebra of rootedtrees 2154.4.5. The substitution law 2164.4.6. Bibliographicalcomments 2174.5. References 217Chapter 5. Combinatorial Algebra in Controllability and Optimal Control 221Matthias KAWSKI5.1. Introduction 2215.1.1. Motivation: idealized examples 2235.1.2. Controlled dynamical systems 2255.1.3. Fundamental questions in control 2265.2. Analytic foundations 2285.2.1. State-space models and vector fields on manifolds 2285.2.2. Chronological calculus 2305.2.3. Piecewise constant controls and theBaker–Campbell–Hausdorff formula 2335.2.4. Picard iterationand formal series solutions 2355.2.5. The Chen–Fliess series and abstractions 2375.3. Controllability and optimality 2415.3.1. Reachable sets and accessibility 2415.3.2. Small-time local controllability 2435.3.3. Nilpotent approximatingsystems 2475.3.4. Optimality and the maximum principle 2515.3.5. Control variations and approximating cones 2555.4. Product expansions and realizations 2625.4.1. Variation of parameters and exponential products 2635.4.2. Computations using Zinbiel products 2675.4.3. Exponential products and normal forms for nilpotent systems 2695.4.4. Logarithmof theChen series 2735.5. References 279Chapter 6. Algebra is Geometry is Algebra – Interactions Between Hopf Algebras, Infinite Dimensional Geometry and Application 287Alexander SCHMEDING6.1. The Butcher group and the Connes–Kreimer algebra 2886.1.1. The Butcher group and B-series from numerical analysis 2886.1.2. Beyond the Butcher group 2916.2. Character groups of graded and connected Hopf algebras 2926.2.1. The exponential and logarithm 2946.3. Controlled groups of characters 2976.3.1. Conventions for this section 2976.3.2. Combinatorial Hopf algebras and the inverse factorial character 3046.4. Appendix: Calculus in locally convex spaces 3056.4.1. Cr-Manifolds and Cr-mappingsbetween them 3066.5. References 306List of Authors 311Index 313

Abdenacer Makhlouf is a Professor and head of the mathematics department at the University of Haute Alsace, France. His research covers structure, representation theory, deformation theory and cohomology of various types of algebras, including non-associative algebras, Hopf algebras and n-ary algebras.

• PrefacexiAbdenacer MAKHLOUFChapter 1. Algebraic Background for Numerical Methods, Control Theory and Renormalization 1Dominique MANCHON1.1. Introduction 11.2. Hopf algebras: generalproperties 21.2.1. Algebras 21.2.2. Coalgebras 31.2.3. Convolution product 61.2.4. Bialgebras andHopf algebras 71.2.5. Some simple examples of Hopf algebras 81.2.6. Some basic properties of Hopf algebras 91.3. ConnectedHopf algebras 101.3.1. Connectedgradedbialgebras 101.3.2. An example: the Hopf algebra of decorated rooted trees 131.3.3. Connectedfiltered bialgebras 141.3.4. The convolution product 151.3.5. Characters 171.3.6. Group schemes and the Cartier–Milnor–Moore–Quillen theorem 191.3.7. Renormalization in connected filtered Hopf algebras 211.4. Pre-Lie algebras 241.4.1. Definition and general properties 241.4.2. The groupof formalflows 251.4.3. The pre-Lie Poincaré–Birkhoff–Witt theorem 261.5. Algebraicoperads 281.5.1. Manipulatingalgebraicoperations 281.5.2. The operad of multi-linear operations 291.5.3. A definition for linear operads 311.5.4. Afewexamplesof operads 321.6. Pre-Lie algebras (continued) 351.6.1. Pre-Lie algebras and augmented operads 351.6.2. A pedestrian approach to free pre-Lie algebra 361.6.3. Right-sided commutative Hopf algebras and theLoday–Roncotheorem 381.6.4. Pre-Lie algebras of vectorfields 401.6.5. B-series, composition and substitution 421.7. Other related algebraic structures 441.7.1. NAPalgebras 441.7.2. Novikovalgebras 481.7.3. Assosymmetric algebras 481.7.4. Dendriformalgebras 481.7.5. Post-Lie algebras 491.8. References 50Chapter 2. From Iterated Integrals and Chronological Calculus to Hopf and Rota–Baxter Algebras 55Kurusch EBRAHIMI-FARD and Frédéric PATRAS2.1. Introduction 552.2. Generalizediterated integrals 582.2.1. Permutations andsimplices 592.2.2. Descents,NCSFand theBCHformula 642.2.3. Rooted trees and nonlinear differential equations 672.2.4. Flows and Hopf algebraic structures 712.3. Advances in chronological calculus 742.3.1. Chronological calculus and half-shuffles 752.3.2. Chronological calculus and pre-Lie products 792.3.3. Time-ordered products and enveloping algebras 812.3.4. Formal flows and Hopf algebraic structures 832.4. Rota–Baxter algebras 872.4.1. Origin 872.4.2. Definition and examples 912.4.3. Related algebraic structures 952.4.4. Atkinson’s factorization and Bogoliubov’s recursion 1012.4.5. Spitzer’s identity: commutative case 1032.4.6. Free commutativeRota–Baxter algebras 1072.4.7. Spitzer’s identity: noncommutative case 1082.4.8. FreeRota–Baxter algebras 1112.5. References 113Chapter 3. Noncommutative Symmetric Functions, Lie Series and Descent Algebras 119Jean-Yves THIBON3.1. Introduction 1193.2. Classical symmetric functions 1203.2.1. Symmetric polynomials 1203.2.2. The Hopf algebra of symmetric functions 1223.2.3. The λ-ringnotation 1243.2.4. Symmetric functions and formal power series 1253.2.5. Duality 1263.3. Noncommutativesymmetric functions 1293.3.1. Basic definitions 1293.3.2. Generators andlinear bases 1313.3.3. Duality 1333.3.4. Solomon’sdescent algebras 1363.4. Lie series andLie idempotents 1393.4.1. Permutational operators on tensor spaces 1393.4.2. TheHausdorff series 1393.4.3. Lie idempotents in the descent algebra 1433.5. Lie idempotents as noncommutative symmetric functions 1443.5.1. Noncommutativepower-sums 1443.5.2. The Magnus expansion 1463.5.3. The continuous BCH expansion 1483.5.4. Another proof of the Magnus expansion 1503.5.5. The (1 − q)-transform 1503.5.6. Hopf algebras enter the scene 1513.5.7. A one-parameter family of Lie idempotents 1523.5.8. The iterated q-bracketing and its diagonalization 1533.6. Decompositionsof the descent algebras 1553.6.1. Complete families of minimal orthogonal idempotents 1553.6.2. Eulerianidempotents 1563.6.3. GeneralizedEulerianidempotents 1603.7. Decompositionsof the tensor algebra 1603.8. General deformations 1623.9. Lie quasi-idempotents as Lie polynomials 1633.9.1. The left derivative 1633.9.2. Multilinear Lie polynomials 1643.9.3. Decompositions on other bases 1673.10. Permutations and free quasi-symmetric functions 1693.10.1. Free quasi-symmetricfunctions 1693.11. Packed words and word quasi-symmetric functions 1713.12. References 175Chapter 4. From Runge–Kutta Methods to Hopf Algebras of Rooted Trees 179Ander MURUA4.1. Numerical integration methods for ordinary differential equations 1794.1.1. Introduction 1794.1.2. Runge–Kutta methods 1804.2. Algebraic theory of Runge–Kutta methods 1824.2.1. The order conditions of RK methods 1824.2.2. The independence of order conditions 1864.2.3. Proof of necessary and sufficient order conditions 1884.2.4. Composition of RK methods, rooted trees and forests 1914.2.5. TheButchergroup 1954.2.6. Equivalence classes of RK methods 1974.2.7. Bibliographicalcomments 1984.3. B-series and relatedformal expansions 1984.3.1. B-series 1984.3.2. Backward error analysis, the exponential and the logarithm 1994.3.3. Series of linear differentialoperators 2034.3.4. The Lie algebra of the Butcher group 2054.3.5. The pre-Lie algebra structure on g 2064.3.6. Bibliographicalcomments 2094.4. Hopf algebrasof rootedtrees 2094.4.1. The commutative Hopf algebra of rooted trees 2104.4.2. The dual algebra H∗ and the dual Hopf algebra H◦ 2124.4.3. B-series and series of differential operators revisited 2134.4.4. A universal property of the commutative Hopf algebra of rootedtrees 2154.4.5. The substitution law 2164.4.6. Bibliographicalcomments 2174.5. References 217Chapter 5. Combinatorial Algebra in Controllability and Optimal Control 221Matthias KAWSKI5.1. Introduction 2215.1.1. Motivation: idealized examples 2235.1.2. Controlled dynamical systems 2255.1.3. Fundamental questions in control 2265.2. Analytic foundations 2285.2.1. State-space models and vector fields on manifolds 2285.2.2. Chronological calculus 2305.2.3. Piecewise constant controls and theBaker–Campbell–Hausdorff formula 2335.2.4. Picard iterationand formal series solutions 2355.2.5. The Chen–Fliess series and abstractions 2375.3. Controllability and optimality 2415.3.1. Reachable sets and accessibility 2415.3.2. Small-time local controllability 2435.3.3. Nilpotent approximatingsystems 2475.3.4. Optimality and the maximum principle 2515.3.5. Control variations and approximating cones 2555.4. Product expansions and realizations 2625.4.1. Variation of parameters and exponential products 2635.4.2. Computations using Zinbiel products 2675.4.3. Exponential products and normal forms for nilpotent systems 2695.4.4. Logarithmof theChen series 2735.5. References 279Chapter 6. Algebra is Geometry is Algebra – Interactions Between Hopf Algebras, Infinite Dimensional Geometry and Application 287Alexander SCHMEDING6.1. The Butcher group and the Connes–Kreimer algebra 2886.1.1. The Butcher group and B-series from numerical analysis 2886.1.2. Beyond the Butcher group 2916.2. Character groups of graded and connected Hopf algebras 2926.2.1. The exponential and logarithm 2946.3. Controlled groups of characters 2976.3.1. Conventions for this section 2976.3.2. Combinatorial Hopf algebras and the inverse factorial character 3046.4. Appendix: Calculus in locally convex spaces 3056.4.1. Cr-Manifolds and Cr-mappingsbetween them 3066.5. References 306List of Authors 311Index 313

Abdenacer Makhlouf is a Professor and head of the mathematics department at the University of Haute Alsace, France. His research covers structure, representation theory, deformation theory and cohomology of various types of algebras, including non-associative algebras, Hopf algebras and n-ary algebras.

• PrefacexiAbdenacer MAKHLOUFChapter 1. Algebraic Background for Numerical Methods, Control Theory and Renormalization 1Dominique MANCHON1.1. Introduction 11.2. Hopf algebras: generalproperties 21.2.1. Algebras 21.2.2. Coalgebras 31.2.3. Convolution product 61.2.4. Bialgebras andHopf algebras 71.2.5. Some simple examples of Hopf algebras 81.2.6. Some basic properties of Hopf algebras 91.3. ConnectedHopf algebras 101.3.1. Connectedgradedbialgebras 101.3.2. An example: the Hopf algebra of decorated rooted trees 131.3.3. Connectedfiltered bialgebras 141.3.4. The convolution product 151.3.5. Characters 171.3.6. Group schemes and the Cartier–Milnor–Moore–Quillen theorem 191.3.7. Renormalization in connected filtered Hopf algebras 211.4. Pre-Lie algebras 241.4.1. Definition and general properties 241.4.2. The groupof formalflows 251.4.3. The pre-Lie Poincaré–Birkhoff–Witt theorem 261.5. Algebraicoperads 281.5.1. Manipulatingalgebraicoperations 281.5.2. The operad of multi-linear operations 291.5.3. A definition for linear operads 311.5.4. Afewexamplesof operads 321.6. Pre-Lie algebras (continued) 351.6.1. Pre-Lie algebras and augmented operads 351.6.2. A pedestrian approach to free pre-Lie algebra 361.6.3. Right-sided commutative Hopf algebras and theLoday–Roncotheorem 381.6.4. Pre-Lie algebras of vectorfields 401.6.5. B-series, composition and substitution 421.7. Other related algebraic structures 441.7.1. NAPalgebras 441.7.2. Novikovalgebras 481.7.3. Assosymmetric algebras 481.7.4. Dendriformalgebras 481.7.5. Post-Lie algebras 491.8. References 50Chapter 2. From Iterated Integrals and Chronological Calculus to Hopf and Rota–Baxter Algebras 55Kurusch EBRAHIMI-FARD and Frédéric PATRAS2.1. Introduction 552.2. Generalizediterated integrals 582.2.1. Permutations andsimplices 592.2.2. Descents,NCSFand theBCHformula 642.2.3. Rooted trees and nonlinear differential equations 672.2.4. Flows and Hopf algebraic structures 712.3. Advances in chronological calculus 742.3.1. Chronological calculus and half-shuffles 752.3.2. Chronological calculus and pre-Lie products 792.3.3. Time-ordered products and enveloping algebras 812.3.4. Formal flows and Hopf algebraic structures 832.4. Rota–Baxter algebras 872.4.1. Origin 872.4.2. Definition and examples 912.4.3. Related algebraic structures 952.4.4. Atkinson’s factorization and Bogoliubov’s recursion 1012.4.5. Spitzer’s identity: commutative case 1032.4.6. Free commutativeRota–Baxter algebras 1072.4.7. Spitzer’s identity: noncommutative case 1082.4.8. FreeRota–Baxter algebras 1112.5. References 113Chapter 3. Noncommutative Symmetric Functions, Lie Series and Descent Algebras 119Jean-Yves THIBON3.1. Introduction 1193.2. Classical symmetric functions 1203.2.1. Symmetric polynomials 1203.2.2. The Hopf algebra of symmetric functions 1223.2.3. The λ-ringnotation 1243.2.4. Symmetric functions and formal power series 1253.2.5. Duality 1263.3. Noncommutativesymmetric functions 1293.3.1. Basic definitions 1293.3.2. Generators andlinear bases 1313.3.3. Duality 1333.3.4. Solomon’sdescent algebras 1363.4. Lie series andLie idempotents 1393.4.1. Permutational operators on tensor spaces 1393.4.2. TheHausdorff series 1393.4.3. Lie idempotents in the descent algebra 1433.5. Lie idempotents as noncommutative symmetric functions 1443.5.1. Noncommutativepower-sums 1443.5.2. The Magnus expansion 1463.5.3. The continuous BCH expansion 1483.5.4. Another proof of the Magnus expansion 1503.5.5. The (1 − q)-transform 1503.5.6. Hopf algebras enter the scene 1513.5.7. A one-parameter family of Lie idempotents 1523.5.8. The iterated q-bracketing and its diagonalization 1533.6. Decompositionsof the descent algebras 1553.6.1. Complete families of minimal orthogonal idempotents 1553.6.2. Eulerianidempotents 1563.6.3. GeneralizedEulerianidempotents 1603.7. Decompositionsof the tensor algebra 1603.8. General deformations 1623.9. Lie quasi-idempotents as Lie polynomials 1633.9.1. The left derivative 1633.9.2. Multilinear Lie polynomials 1643.9.3. Decompositions on other bases 1673.10. Permutations and free quasi-symmetric functions 1693.10.1. Free quasi-symmetricfunctions 1693.11. Packed words and word quasi-symmetric functions 1713.12. References 175Chapter 4. From Runge–Kutta Methods to Hopf Algebras of Rooted Trees 179Ander MURUA4.1. Numerical integration methods for ordinary differential equations 1794.1.1. Introduction 1794.1.2. Runge–Kutta methods 1804.2. Algebraic theory of Runge–Kutta methods 1824.2.1. The order conditions of RK methods 1824.2.2. The independence of order conditions 1864.2.3. Proof of necessary and sufficient order conditions 1884.2.4. Composition of RK methods, rooted trees and forests 1914.2.5. TheButchergroup 1954.2.6. Equivalence classes of RK methods 1974.2.7. Bibliographicalcomments 1984.3. B-series and relatedformal expansions 1984.3.1. B-series 1984.3.2. Backward error analysis, the exponential and the logarithm 1994.3.3. Series of linear differentialoperators 2034.3.4. The Lie algebra of the Butcher group 2054.3.5. The pre-Lie algebra structure on g 2064.3.6. Bibliographicalcomments 2094.4. Hopf algebrasof rootedtrees 2094.4.1. The commutative Hopf algebra of rooted trees 2104.4.2. The dual algebra H∗ and the dual Hopf algebra H◦ 2124.4.3. B-series and series of differential operators revisited 2134.4.4. A universal property of the commutative Hopf algebra of rootedtrees 2154.4.5. The substitution law 2164.4.6. Bibliographicalcomments 2174.5. References 217Chapter 5. Combinatorial Algebra in Controllability and Optimal Control 221Matthias KAWSKI5.1. Introduction 2215.1.1. Motivation: idealized examples 2235.1.2. Controlled dynamical systems 2255.1.3. Fundamental questions in control 2265.2. Analytic foundations 2285.2.1. State-space models and vector fields on manifolds 2285.2.2. Chronological calculus 2305.2.3. Piecewise constant controls and theBaker–Campbell–Hausdorff formula 2335.2.4. Picard iterationand formal series solutions 2355.2.5. The Chen–Fliess series and abstractions 2375.3. Controllability and optimality 2415.3.1. Reachable sets and accessibility 2415.3.2. Small-time local controllability 2435.3.3. Nilpotent approximatingsystems 2475.3.4. Optimality and the maximum principle 2515.3.5. Control variations and approximating cones 2555.4. Product expansions and realizations 2625.4.1. Variation of parameters and exponential products 2635.4.2. Computations using Zinbiel products 2675.4.3. Exponential products and normal forms for nilpotent systems 2695.4.4. Logarithmof theChen series 2735.5. References 279Chapter 6. Algebra is Geometry is Algebra – Interactions Between Hopf Algebras, Infinite Dimensional Geometry and Application 287Alexander SCHMEDING6.1. The Butcher group and the Connes–Kreimer algebra 2886.1.1. The Butcher group and B-series from numerical analysis 2886.1.2. Beyond the Butcher group 2916.2. Character groups of graded and connected Hopf algebras 2926.2.1. The exponential and logarithm 2946.3. Controlled groups of characters 2976.3.1. Conventions for this section 2976.3.2. Combinatorial Hopf algebras and the inverse factorial character 3046.4. Appendix: Calculus in locally convex spaces 3056.4.1. Cr-Manifolds and Cr-mappingsbetween them 3066.5. References 306List of Authors 311Index 313