MKW Hopf Algebra

The kauri.mkw sub-package implements the Munthe-Kaas–Wright (MKW) Hopf algebra [MKW08] \((H, \Delta_{MKW}, \shuffle, \varepsilon_{MKW}, \emptyset, S_{MKW})\), defined as follows.

  • \(H\) is the set of all planar (ordered) rooted trees, where sibling order matters.

  • The unit \(\emptyset\) is the empty ordered forest.

  • The counit map is defined by \(\varepsilon_{MKW}(\emptyset) = 1\), \(\varepsilon_{MKW}(t) = 0\) for all \(\emptyset \neq t \in H\).

  • Multiplication \(\shuffle : H \otimes H \to H\) is the commutative shuffle product of ordered forests.

  • Comultiplication \(\Delta_{MKW} : H \to H \otimes H\) is defined recursively by \(\Delta_{MKW}(B_+(t_1, \ldots, t_k)) = B_+(t_1, \ldots, t_k) \otimes \emptyset + (\mathrm{id} \otimes B_+)(\tilde{\Delta}(t_1) \bar{\shuffle} \cdots \bar{\shuffle} \tilde{\Delta}(t_k))\), where \(\tilde{\Delta} = \Delta - \mathrm{id} \otimes \emptyset\) is the reduced coproduct and \(\bar{\shuffle}\) shuffles left tensor factors while concatenating right factors.

  • The antipode \(S_{MKW}\) is a homomorphism (since the algebra is commutative), unlike the NCK antipode which is an anti-homomorphism.

Note

The MKW algebra is commutative but not cocommutative. It is the correct Hopf algebra for the analysis of Lie–Butcher series and Lie group integrators [MKW08]. The closely related noncommutative Connes–Kreimer algebra (kauri.nck) uses concatenation rather than shuffle as its product.

Example: MKW coproduct

import kauri as kr
import kauri.mkw as mkw
t = kr.PlanarTree([[],[]])
kr.display(mkw.coproduct(t))
⊗ ∅ + ∅ ⊗ + ⊗ + ⊗

Example: Shuffle product

import kauri as kr
import kauri.mkw as mkw
t1 = kr.PlanarTree([])
t2 = kr.PlanarTree([[]])
kr.display(mkw.shuffle_product(t1, t2))
+
counit = <kauri.maps.Map object>

The counit \(\varepsilon\) of the MKW Hopf algebra.

Type:

Map

Example usage:

print(mkw.counit(PlanarTree(None)))  # Returns 1
print(mkw.counit(PlanarTree([])))  # Returns 0

1
0
antipode = <kauri.maps.Map object>

The antipode \(S\) of the MKW Hopf algebra.

Since the MKW algebra is commutative (the shuffle product is commutative), the antipode is a homomorphism: \(S(f_1 \shuffle f_2) = S(f_1) \shuffle S(f_2)\).

Type:

Map

Example usage:

t = PlanarTree([[[]],[]])
kr.display(mkw.antipode(t))
− + + + 2 − 4 − 3 − 2 + 12
coproduct(t: PlanarTree) → TensorProductSum[source]

The coproduct \(\Delta\) of the MKW Hopf algebra.

The MKW coproduct uses the shuffle product to combine left factors from different children’s coproducts, unlike the NCK coproduct which uses concatenation. For ladder trees (chains), the two coincide.

Parameters:

t (PlanarTree) – planar tree

Return type:

TensorProductSum

Example usage:

t = PlanarTree([[],[]])
kr.display(mkw.coproduct(t))
⊗ ∅ + ∅ ⊗ + ⊗ + ⊗
shuffle_product(f1, f2) → ForestSum[source]

The shuffle product of two ordered forests (or planar trees).

Returns a ForestSum containing all interleavings of the two input forests that preserve the relative order within each.

Parameters:

  • f1 – first forest (or planar tree)

  • f2 – second forest (or planar tree)

Return type:

ForestSum

Example usage:

t1 = PlanarTree([])
t2 = PlanarTree([[]])
kr.display(mkw.shuffle_product(t1, t2))
+
map_product(f: Map, g: Map) → Map[source]

Returns the convolution product of scalar-valued maps in the MKW Hopf algebra, defined by

\[(f \cdot g)(t) := \mu \circ (f \otimes g) \circ \Delta_{MKW}(t)\]

where \(\mu\) is the shuffle product and \(\Delta_{MKW}\) is the left-admissible-cuts coproduct. The inputs are interpreted as shuffle-multiplicative scalar characters, and the returned Map carries extension="shuffle" so that subsequent evaluations on ordered forests apply the shuffle-symmetric 1/k! extension.

Note

Both maps must be scalar-valued (returning numbers, not trees/forests) and interpreted as shuffle-symmetric characters. The true-solution LB character on a Lie group has different tree values than the flat-space B-series character; e.g. alpha_exact(cherry) = 1/6 under MKW, not 1/3. See unit_tests/test_cf_methods.py::TestLBCompositionSemantics for the order-4 table.

Parameters:
Return type:

Map

Example usage:

f = Map(lambda x: 1 if x.list_repr is None else 0)
g = mkw.map_product(f, f)
print(g(PlanarTree([[]])))

0
map_power(f: Map, exponent: int) → Map[source]

Returns the convolution power of a scalar-valued map in the MKW Hopf algebra. The result carries extension="shuffle" so that forest evaluations obey the shuffle-symmetric \(1/k!\) extension.

Note

The map should be scalar-valued and interpreted as a shuffle-symmetric character. See map_product() for the conventions used.

Parameters:

  • f (Map) – f

  • exponent (int) – exponent

Return type:

Map

Example usage:

f = Map(lambda x: 1 if x.list_repr is None else x.nodes())
f_sq = mkw.map_power(f, 2)
print(f_sq(PlanarTree([[]])))

5