Algebra and Applications 2

Prefacexi
Abdenacer MAKHLOUF

Chapter 1. Algebraic Background for Numerical Methods, Control Theory and Renormalization 1
Dominique MANCHON

1.1. Introduction 1

1.2. Hopf algebras: generalproperties 2

1.2.1. Algebras 2

1.2.2. Coalgebras 3

1.2.3. Convolution product 6

1.2.4. Bialgebras andHopf algebras 7

1.2.5. Some simple examples of Hopf algebras 8

1.2.6. Some basic properties of Hopf algebras 9

1.3. ConnectedHopf algebras 10

1.3.1. Connectedgradedbialgebras 10

1.3.2. An example: the Hopf algebra of decorated rooted trees 13

1.3.3. Connectedfiltered bialgebras 14

1.3.4. The convolution product 15

1.3.5. Characters 17

1.3.6. Group schemes and the Cartier-Milnor-Moore-Quillen theorem 19

1.3.7. Renormalization in connected filtered Hopf algebras 21

1.4. Pre-Lie algebras 24

1.4.1. Definition and general properties 24

1.4.2. The groupof formalflows 25

1.4.3. The pre-Lie Poincare-Birkhoff-Witt theorem 26

1.5. Algebraicoperads 28

1.5.1. Manipulatingalgebraicoperations 28

1.5.2. The operad of multi-linear operations 29

1.5.3. A definition for linear operads 31

1.5.4. Afewexamplesof operads 32

1.6. Pre-Lie algebras (continued) 35

1.6.1. Pre-Lie algebras and augmented operads 35

1.6.2. A pedestrian approach to free pre-Lie algebra 36

1.6.3. Right-sided commutative Hopf algebras and theLoday-Roncotheorem 38

1.6.4. Pre-Lie algebras of vectorfields 40

1.6.5. B-series, composition and substitution 42

1.7. Other related algebraic structures 44

1.7.1. NAPalgebras 44

1.7.2. Novikovalgebras 48

1.7.3. Assosymmetric algebras 48

1.7.4. Dendriformalgebras 48

1.7.5. Post-Lie algebras 49

1.8. References 50

Chapter 2. From Iterated Integrals and Chronological Calculus to Hopf and Rota-Baxter Algebras 55
Kurusch EBRAHIMI-FARD and Frederic PATRAS

2.1. Introduction 55

2.2. Generalizediterated integrals 58

2.2.1. Permutations andsimplices 59

2.2.2. Descents,NCSFand theBCHformula 64

2.2.3. Rooted trees and nonlinear differential equations 67

2.2.4. Flows and Hopf algebraic structures 71

2.3. Advances in chronological calculus 74

2.3.1. Chronological calculus and half-shuffles 75

2.3.2. Chronological calculus and pre-Lie products 79

2.3.3. Time-ordered products and enveloping algebras 81

2.3.4. Formal flows and Hopf algebraic structures 83

2.4. Rota-Baxter algebras 87

2.4.1. Origin 87

2.4.2. Definition and examples 91

2.4.3. Related algebraic structures 95

2.4.4. Atkinson's factorization and Bogoliubov's recursion 101

2.4.5. Spitzer's identity: commutative case 103

2.4.6. Free commutativeRota-Baxter algebras 107

2.4.7. Spitzer's identity: noncommutative case 108

2.4.8. FreeRota-Baxter algebras 111

2.5. References 113

Chapter 3. Noncommutative Symmetric Functions, Lie Series and Descent Algebras 119
Jean-Yves THIBON

3.1. Introduction 119

3.2. Classical symmetric functions 120

3.2.1. Symmetric polynomials 120

3.2.2. The Hopf algebra of symmetric functions 122

3.2.3. The -ringnotation 124

3.2.4. Symmetric functions and formal power series 125

3.2.5. Duality 126

3.3. Noncommutativesymmetric functions 129

3.3.1. Basic definitions 129

3.3.2. Generators andlinear bases 131

3.3.3. Duality 133

3.3.4. Solomon'sdescent algebras 136

3.4. Lie series andLie idempotents 139

3.4.1. Permutational operators on tensor spaces 139

3.4.2. TheHausdorff series 139

3.4.3. Lie idempotents in the descent algebra 143

3.5. Lie idempotents as noncommutative symmetric functions 144

3.5.1. Noncommutativepower-sums 144

3.5.2. The Magnus expansion 146

3.5.3. The continuous BCH expansion 148

3.5.4. Another proof of the Magnus expansion 150

3.5.5. The (1 q)-transform 150

3.5.6. Hopf algebras enter the scene 151

3.5.7. A one-parameter family of Lie idempotents 152

3.5.8. The iterated q-bracketing and its diagonalization 153

3.6. Decompositionsof the descent algebras 155

3.6.1. Complete families of minimal orthogonal idempotents 155

3.6.2. Eulerianidempotents 156

3.6.3. GeneralizedEulerianidempotents 160

3.7. Decompositionsof the tensor algebra 160

3.8. General deformations 162

3.9. Lie quasi-idempotents as Lie polynomials 163

3.9.1. The left derivative 163

3.9.2. Multilinear Lie polynomials 164

3.9.3. Decompositions on other bases 167

3.10. Permutations and free quasi-symmetric functions 169

3.10.1. Free quasi-symmetricfunctions 169

3.11. Packed words and word quasi-symmetric functions 171

3.12. References 175

Chapter 4. From Runge-Kutta Methods to Hopf Algebras of Rooted Trees 179
Ander MURUA

4.1. Numerical integration methods for ordinary differential equations 179

4.1.1. Introduction 179

4.1.2. Runge-Kutta methods 180

4.2. Algebraic theory of Runge-Kutta methods 182

4.2.1. The order conditions of RK methods 182

4.2.2. The independence of order conditions 186

4.2.3. Proof of necessary and sufficient order conditions 188

4.2.4. Composition of RK methods, rooted trees and forests 191

4.2.5. TheButchergroup 195

4.2.6. Equivalence classes of RK methods 197

4.2.7. Bibliographicalcomments 198

4.3. B-series and relatedformal expansions 198

4.3.1. B-series 198

4.3.2. Backward error analysis, the exponential and the logarithm 199

4.3.3. Series of linear differentialoperators 203

4.3.4. The Lie algebra of the Butcher group 205

4.3.5. The pre-Lie algebra structure on g 206

4.3.6. Bibliographicalcomments 209

4.4. Hopf algebrasof rootedtrees 209

4.4.1. The commutative Hopf algebra of rooted trees 210

4.4.2. The dual algebra H and the dual Hopf algebra H 212

4.4.3. B-series and series of differential operators revisited 213

4.4.4. A universal property of the commutative Hopf algebra of rootedtrees 215

4.4.5. The substitution law 216

4.4.6. Bibliographicalcomments 217

4.5. References 217

Chapter 5. Combinatorial Algebra in Controllability and Optimal Control 221
Matthias KAWSKI

5.1. Introduction 221

5.1.1. Motivation: idealized examples 223

5.1.2. Controlled dynamical systems 225

5.1.3. Fundamental questions in control 226

5.2. Analytic foundations 228

5.2.1. State-space models and vector fields on manifolds 228

5.2.2. Chronological calculus 230

5.2.3. Piecewise constant controls and theBaker-Campbell-Hausdorff formula 233

5.2.4. Picard iterationand formal series solutions 235

5.2.5. The Chen-Fliess series and abstractions 237

5.3. Controllability and optimality 241

5.3.1. Reachable sets and accessibility 241

5.3.2. Small-time local controllability 243

5.3.3. Nilpotent approximatingsystems 247

5.3.4. Optimality and the maximum principle 251

5.3.5. Control variations and approximating cones 255

5.4. Product expansions and realizations 262

5.4.1. Variation of parameters and exponential products 263

5.4.2. Computations using Zinbiel products 267

5.4.3. Exponential products and normal forms for nilpotent systems 269

5.4.4. Logarithmof theChen series 273

5.5. References 279

Chapter 6. Algebra is Geometry is Algebra - Interactions Between Hopf Algebras, Infinite Dimensional Geometry and Application 287
Alexander SCHMEDING

6.1. The Butcher group and the Connes-Kreimer algebra 288

6.1.1. The Butcher group and B-series from numerical analysis 288

6.1.2. Beyond the Butcher group 291

6.2. Character groups of graded and connected Hopf algebras 292

6.2.1. The exponential and logarithm 294

6.3. Controlled groups of characters 297

6.3.1. Conventions for this section 297

6.3.2. Combinatorial Hopf algebras and the inverse factorial character 304

6.4. Appendix: Calculus in locally convex spaces 305

6.4.1. Cr-Manifolds and Cr-mappingsbetween them 306

6.5. References 306

List of Authors 311

Index 313