The Monoid Algebra Semiring¶

The Monoid Algebra Semiring $R[M]$ (or Group Algebra $R[G]$) provides the foundational algebraic structure for formal linear combinations $\sum_{m \in M} a_m m$ over an arbitrary monoid $M$ and coefficient semiring $R$.

It serves as the parent abstraction for several specialized algebraic structures in algebrax, including the Polynomial Semiring ($R[x]$) and the Knot Semiring ($R[\text{Knots}]$).

Mathematical Definition¶

Set ($S$): Formal linear combinations of monoid elements $\sum_{m \in M} a_m m$, represented as sparse mappings {monoid_element: coefficient}.
Coefficient Semiring ($R$): An underlying semiring defining coefficient addition ($\oplus$) and multiplication ($\otimes$).
Monoid Operation (key_op): The associative binary operation $\cdot : M \times M \to M$ of the monoid $M$.
Addition ($+$): Element-wise addition of coefficients for matching keys: $$\left (\sum a_m m\right) + \left (\sum b_m m\right) = \sum (a_m \oplus b_m) m$$
Multiplication ($\cdot$): Cauchy product / discrete convolution using monoid multiplication and coefficient multiplication: $$\left (\sum a_m m\right) \cdot \left (\sum b_n n\right) = \sum_{m, n} (a_m \otimes b_n) (m \cdot n)$$
Additive Identity ($0$): The empty mapping {}.
Multiplicative Identity ($1$): {zero_key: R.one} (where zero_key is the monoid identity element $e \in M$).

Implementation in `algebrax`¶

The MonoidAlgebraSemiring class is generic over both key type K and coefficient type T:

import algebrax as ax

# 1. Define base coefficient semiring
int_semiring = ax.semiring.StandardSemiring(int)

# 2. Instantiate ax.semiring.MonoidAlgebraSemiring with custom string monoid (concatenation)
string_algebra = ax.semiring.MonoidAlgebraSemiring(
    coeff_semiring=int_semiring,
    key_op=lambda a, b: a + b,
    zero_key="",
)

# 3. Define formal linear combinations
a = {'x': 2, 'y': 3}
b = {'z': 4}

# Multiplication performs discrete convolution over key concatenation:
# (2x + 3y) * (4z) = 8xz + 12yz
res = string_algebra.mul(a, b)
# Result: {'xz': 8, 'yz': 12}
print(res)

Derived Subclasses¶

MonoidAlgebraSemiring forms the theoretical foundation for specialized semirings in algebrax:

PolynomialSemiring ($R[x]$): Monoid algebra over non-negative integer exponents $M = (\mathbb{N}_0, +)$ with key_op = lambda x, y: x + y and zero_key = 0.
KnotSemiring ($R[\text{Knots}]$): Monoid algebra over topological knots $M = (\text{Knots}, \#)$ with connected sum key_op = _combine_knots and zero_key = 'U'.
ProvenanceSemiring ($\mathbb{N}[X]$): Monoid algebra over multivariate tuple monomials $M = (\text{Monomials}, \cdot)$ with sorted variable concatenation key_op = _combine_monomials and zero_key = ().

Use Cases¶

Group Algebras: Constructing finite group rings $R[G]$ for representation theory and Fourier analysis.
Discrete Signal Processing: Defining generalized convolution operators over arbitrary monoid domains.
Formal Language Theory: Building formal power series and weighted automata over free monoids.

The Monoid Algebra Semiring¶

Mathematical Definition¶

Implementation in algebrax¶

Derived Subclasses¶

Use Cases¶

Implementation in `algebrax`¶