Concepts¶

This document provides a theoretical overview of the algebraic structures used in algebrax. Understanding these concepts helps clarify why certain operations are grouped together and how they generalize across different domains (graphs, logic, probability).

[!TIP] Semiring Mental Model Think of a Semiring as an arithmetic engine where you swap out standard Addition (+) and Multiplication (×) for any custom rules — like $(\min, +)$ for shortest paths, or $(\max, \times)$ for link reliability. The exact same sparse matrix multiplication algorithm (dot) then solves completely different problems just by switching the semiring!

Algebraic Structures¶

Hierarchy of Structures (Ordered by Complexity)

1. Monoid $(M, \cdot)$¶

A set $M$ with a single binary operation $\cdot$ that satisfies:

Closure: If $a, b \in M$, then $a \cdot b \in M$.
Associativity: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$.
Identity: There exists $e \in M$ such that $a \cdot e = e \cdot a = a$.

Example:

Natural numbers under addition $(\mathbb{N}, +)$. Identity is 0.
Strings under concatenation. Identity is "".

2. Group $(G, \cdot)$¶

A Monoid where every element has an Inverse.

Inverse: For every $a \in G$, there exists $a^{-1}$ such that $a \cdot a^{-1} = e$.

Example in Library:

Permutations (algebra.group): The set of bijective mappings forms a group under composition.
- Operation: compose(f, g)
- Inverse: invert(f)
- Identity: {k: k}

3. Abelian Group¶

A Group where the operation is also Commutative:

$a \cdot b = b \cdot a$.

Example: Integers under addition $(\mathbb{Z}, +)$.

4. Groupoid $\mathcal{G}$¶

A Groupoid generalizes a Group to multi-state systems. It can be defined as a small Category in which every morphism is an isomorphism (invertible), or as a set equipped with a partial binary composition $\circ$ satisfying:

Partial Composition: $g \circ f$ is defined only when the codomain (target) of $f$ equals the domain (source) of $g$.
Associativity: $(h \circ g) \circ f = h \circ (g \circ f)$ whenever composable.
Identities: For every state/object $A$, there exists an identity morphism $\text{id}_A$.
Inverses: For every morphism $f: A \to B$, there exists an inverse morphism $f^{-1}: B \to A$ such that: $$f \circ f^{-1} = \text{id}_B \quad \text{and} \quad f^{-1} \circ f = \text{id}_A$$

Examples & Applications:

Group vs Groupoid: A Group is a Groupoid with only one object (all elements are everywhere composable).
Patch Theory (Darcs VCS): Repository states are objects; diff patches $P: \text{State}_1 \to \text{State}_2$ are groupoid morphisms. Every patch has a formal inverse $P^{-1}$, and patches compose along valid execution paths.
Topological Fundamental Groupoid $\Pi_1(X)$: Continuous path transformations in point clouds and simplicial complexes (algebrax.homology).
Permutations (algebrax.group): Full permutations form a single-object groupoid (a Group), while partial bijection transformations form a multi-object groupoid.

5. Semiring $(S, \oplus, \otimes)$¶

A set $S$ with two operations, Addition ($\oplus$) and Multiplication ($\otimes$), satisfying:

$(S, \oplus)$ is a Commutative Monoid (Identity $\mathbf{0}$).
$(S, \otimes)$ is a Monoid (Identity $\mathbf{1}$).
Distributivity: Multiplication distributes over Addition.
Annihilation: $a \otimes \mathbf{0} = \mathbf{0}$.

Crucially: Semirings do not require additive inverses (subtraction) or multiplicative inverses (division).

Examples in Library (algebrax.semiring):

Semirings are organized into categorical sub-modules under algebrax.semiring: * arithmetic: StandardSemiring over real numbers $(\mathbb{R}, +, \times)$ or complex amplitudes $(\mathbb{C}, +, \times)$ (quantum path integrals, discrete wave interference). * optimization: TropicalSemiring $(\mathbb{R} \cup \{\infty\}, \min, +)$, ArcticSemiring, ViterbiSemiring, ReliabilitySemiring, BottleneckSemiring, MinTimesSemiring. Shortest path and capacity algorithms. * logic: BooleanSemiring $(\{T, F\}, \lor, \land)$, LukasiewiczSemiring, DigitalSemiring. Reachability, fuzzy logic, and post-quantum digital operations. * statistical: LogSemiring, ExpectationSemiring, VarianceSemiring, SkewnessSemiring, KurtosisSemiring, StatisticalMomentSemiring, BivariateVarianceSemiring, MultivariateMomentSemiring. Probabilistic inference, higher-order statistical moments, multivariate covariance matrices. * structures: StringSemiring, KCollapsedSemiring. Formal path languages, bounded counting. * algebraic: DualNumberSemiring, BinomialConvolutionSemiring, MultivariateBinomialConvolutionSemiring, MonoidAlgebraSemiring, PolynomialSemiring, KnotSemiring, ProvenanceSemiring, QuotientMonoidAlgebraSemiring, CliffordSemiring ($Cl(p,q,r)$ geometric algebras and Spacetime Dirac spinors), GeneralizedCliffordSemiring, QuantumCliffordSemiring, GaloisFieldSemiring. Free & quotient monoid algebras, divided power polynomial rings, skein modules, Clifford multivectors, finite fields.

6. Ring $(R, +, \cdot)$¶

A Semiring that has additive inverses.

$(R, +)$ is an Abelian Group (Subtraction is defined).

Example: Integers $\mathbb{Z}$, Square Matrices $M_n (\mathbb{R})$.

[!NOTE] Why the Graph Laplacian Requires a Ring/Field While reachability ($\lor, \land$) and shortest paths ($\min, +$) operate over Semirings without additive inverses, the Graph Laplacian $L = D - W$ and discrete exterior calculus inherently require subtraction (additive inverse). The Laplacian measures the difference between a node's self-degree and its incident neighbors. Consequently, spectral graph theory and discrete Laplace-Beltrami diffusion operators are housed in linear rings and fields over $\mathbb{R}$.

7. Field $(F, +, \cdot)$¶

A Ring where multiplication has inverses (for non-zero elements).

$(F \setminus \{0\}, \cdot)$ is an Abelian Group (Division is defined).

Example: Real Numbers $\mathbb{R}$, Complex Numbers $\mathbb{C}$.

8. Algebra (over a Field)¶

A Vector Space equipped with a bilinear product.

Elements can be added and scaled (Vector Space).
Elements can be multiplied (Ring-like).

Example: The set of $N \times N$ matrices forms an Algebra.

9. Ideal¶

A subset $I$ of a Ring $R$ that absorbs multiplication.

If $x \in I$ and $r \in R$, then $r \cdot x \in I$.
Used to define Quotient Rings (e.g., Modular Arithmetic).

10. Clifford Algebra (Geometric & Quantum Generalizations)¶

An associative algebra equipped with a quadratic form or root-of-unity commutation rule, unifying scalars, vectors, and higher-order blades (bivectors, trivectors).

Standard Clifford / Geometric Algebra $Cl(p, q, r)$: $\mathbf{e}_i \mathbf{e}_j = -\mathbf{e}_j \mathbf{e}_i$ ($i \ne j$), $\mathbf{e}_i^2 \in \{+1, -1, 0\}$, with geometric product $ab = a \cdot b + a \wedge b$. Generalizes complex numbers, quaternions, and Dirac spinors.
Generalized Clifford Algebra (GCA) $C_n^{(m)}$: Clock-and-shift commutation $\mathbf{e}_j \mathbf{e}_k = \omega \mathbf{e}_k \mathbf{e}_j$ ($j < k$) where $\omega = \exp(2\pi i / n)$ is a primitive $n$-th root of unity and $\mathbf{e}_j^n = \alpha_j \mathbf{1}$.
$q$-Deformed Quantum Clifford Algebra $Cl_q(m)$: Braided quantum deformation $\mathbf{e}_j \mathbf{e}_k = -q \mathbf{e}_k \mathbf{e}_j$ ($j < k$).

Discrete Exterior Calculus (DEC) & Simplicial Homology¶

The algebrax.analysis and algebrax.homology modules implement concepts from DEC and Topological Homology on graphs and $k$-dimensional simplicial complexes.

Concept	Mathematical Object	Library Type / Function	Example / Application
0-form	Scalar Field (on nodes)	`SparseVector`	Temperature at each city
1-form	Vector Field (on edges)	`SparseMatrix`	Traffic flow between cities
Gradient ($d_0$)	$d_0: \Omega^0 \to \Omega^1$	`gradient()`	Difference in temp between cities
*Divergence ($d_0^$)**	$d_0^*: \Omega^1 \to \Omega^0$	`divergence()`	Net traffic flow out of a city
Laplacian ($\Delta$)	$\Delta = d^* d$	`laplacian()`	Heat diffusion rate
$k$-Simplex	$k$-dim face $(v_0, \dots, v_k)$	`SimplicialComplex`	Triangles, tetrahedra, cliques
Boundary ($D_k$)	$D_k: C_k \to C_{k-1}$	`boundary_matrix()`	Face boundary alternating sums
Nilpotency	$D_{k-1} \circ D_k = \mathbf{0}$	`verify_nilpotency()`	Fundamental homology boundary law
Hodge-Laplacian	$\Delta_k = D_{k+1} D_{k+1}^T + D_k^T D_k$	`hodge_laplacian()`	$k$-form diffusion & harmonic forms
Betti Numbers ($\beta_k$)	$\dim(\ker D_k) - \text{rank}(D_{k+1})$	`betti_numbers()`	Hole count ($\beta_0$ comp, $\beta_1$ loops)

Clifford Geometric Algebra ($Cl (p, q, r)$)¶

The algebrax.clifford module implements Clifford Geometric Algebra over QuotientMonoidAlgebraSemiring. Multivectors unify scalars, vectors, bivectors, and pseudoscalars into a single sparse mapping {blade_tuple: coeff}.

Geometric Product: $A B = A \cdot B + A \wedge B$ (computed via geometric_product()).
Canonical Blade Reduction: $\mathbf{e}_i \mathbf{e}_j = -\mathbf{e}_j \mathbf{e}_i$ and $\mathbf{e}_i^2 = +1$ ($i \le p$), $-1$ ($p < i \le p+q$), $0$ ($i > p+q$).
Rotor Sandwiching ($v' = R v R^\dagger$): Smooth 3D spatial rotations $R = \exp (-\theta/2 \mathbf{B})$ via rotor_rotation() without gimbal lock or matrix conversions.

Galois Finite Field Arithmetic ($\text{GF} (p^m)$)¶

The algebrax.galois module provides finite field arithmetic over QuotientMonoidAlgebraSemiring. Elements are represented as sparse polynomial vectors {exponent: coeff} modulo an irreducible polynomial $P (x)$.

Polynomial Modulo Reduction: Polynomial multiplication in $\mathbb{F}_p[x]$ reduced modulo $P (x)$ (e.g. $x^8 + x^4 + x^3 + x + 1$ for AES $\text{GF} (2^8)$).
Matrix Arithmetic: gf_matrix_mul() computes sparse matrix multiplication for cryptographic MixColumns transformations and Reed-Solomon generator matrices.

Category Theory & Kleisli Monadic Composition¶

The algebrax.category module formalizes category-theoretic compositions.

Morphisms as Matrices: Hom-sets $\text{Hom} (A, B)$ are sparse matrices $M[A][B]$.
Kleisli Monadic Composition: Effectful morphisms $f: A \to T (B)$ and $g: B \to T (C)$ compose via Kleisli matrix multiplication ($g \circ_T f = \text{dot} (f, g, \text{semiring})$) over probabilistic (Viterbi), cost-metric (Tropical), or reachability (Boolean) monad semirings.
Kan Extensions: Left Kan extensions $\text{Lan}_P F$ computed over sparse category graphs.

Functional Taxonomy¶

The following table categorizes the functions in the algebrax module by their Domain (Meaning) and Operation Type.

Legend¶

Structural: Transforms the shape or content of the data (returns a Mapping).
Metric: Reduces the data to a single number (returns float/int).
Predicate: Checks a property (returns bool).
Generator: Creates a new structure from scratch.

1. Linear Algebra (Matrix & Vector)¶

Input: Sparse Vectors/Matrices (representing physical systems or geometric transformations)

Function	Type	Meaning
`add`	Structural	Element-wise addition ($A + B$).
`dot`	Structural	Matrix Multiplication ($A \cdot B$).
`mat_vec`, `vec_mat`	Structural	Matrix-Vector multiplication (Transformation).
`transpose`	Structural	Flips rows and columns ($A^T$).
`inverse`	Structural	Finds $A^{-1}$ such that $A \cdot A^{-1} = I$.
`power`	Structural	Matrix exponentiation ($A^k$).
`adjoint`	Structural	Transpose of cofactor matrix.
`cofactor`	Structural	Matrix of cofactors.
`inner`	Metric	Dot product of two vectors (Similarity).
`determinant`	Metric	Volume scaling factor of the transformation.
`trace`	Metric	Sum of diagonal elements (Invariant).
`kronecker_delta`	Generator	Creates an Identity Matrix ($I$).

2. Lattice & Set Theory (Fuzzy Logic)¶

Input: Mappings as Sets or Fuzzy Sets (Values represent membership/intensity)

Function	Type	Meaning
`join`	Structural	Union / Max ($A \cup B$).
`meet`	Structural	Intersection / Min ($A \cap B$).
`difference`	Structural	Set Difference ($A - B$).
`symmetric_difference`	Structural	XOR ($A \Delta B$).
`combine`	Structural	Generalized element-wise operation.
`mask`	Structural	Keep keys in A that are also in B.
`exclude`	Structural	Keep keys in A that are NOT in B.
`product`	Structural	Element-wise product (Hadamard).
`ratio`	Structural	Element-wise division.
`average`, `geometric_mean`, `harmonic_mean`	Structural	Element-wise means.

3. Probability & Statistics¶

Input: Mappings as Probability Distributions (Values sum to 1)

Function	Type	Meaning
`bayes_update`	Structural	Posterior $\propto$ Likelihood $\times$ Prior.
`markov_step`	Structural	Advance state by $N$ steps ($v \cdot P^n$).
`markov_steady_state`	Structural	Find equilibrium distribution ($\pi = \pi P$).
`marginalize`	Structural	Sum over rows/cols (Joint $\to$ Marginal).
`normalize`	Structural	Scale values to sum to 1.
`entropy`	Metric	Uncertainty ($H(X)$).
`cross_entropy`	Metric	Difference between distributions ($H(P, Q)$).
`kl_divergence`	Metric	Information Gain ($D_{KL}(P \\| Q)$).
`mutual_information`	Metric	Dependence between variables ($I(X; Y)$).
`expected_value`	Metric	Mean of the distribution ($E[X]$).
`variance`, `skewness`, `kurtosis`	Metric	Higher-order moments.
`mode`	Metric	Most probable outcome.

4. Graph Analysis (Network Science)¶

Input: Mappings as Adjacency Matrices (Graphs)

Function	Type	Meaning
`laplacian`	Structural	Graph Laplacian ($D - A$). Diffusion operator.
`gradient`	Structural	Edge-based difference operator.
`divergence`	Structural	Node-based flow operator.
`eigen_centrality`	Structural	Node importance ranking.
`forman_ricci_curvature`	Metric	Local curvature of the graph (Geometry).

5. Signal Processing¶

Input: Mappings as Time Series or Signals

Function	Type	Meaning
`convolve`	Structural	Discrete convolution / polynomial multiplication ($f * g$).
`dft` / `idft`	Structural	Discrete Fourier Transform (Time $\leftrightarrow$ Freq).
`walsh_hadamard`	Structural	Walsh-Hadamard Transform (Orthogonal Hadamard mapping).
`gelfand_transform`	Structural	Generalized character evaluation over monoid algebras.
`legendre_fenchel`	Structural	Fenchel-Legendre transform (Slope transform).
`z_transform`	Structural	Z-Transform (Discrete Laplace / Semiring power series).
`hilbert`	Structural	Hilbert Transform (Analytic Signal).
`lorentz_boost`	Structural	Relativistic coordinate transformation.
`box_counting_dimension`	Metric	Fractal dimension of the signal.

6. Group Theory¶

Input: Mappings as Permutations (Bijective Functions)

Function	Type	Meaning
`compose`	Structural	Function composition ($f \circ g$).
`invert`	Structural	Inverse function ($f^{-1}$).
`signature`	Metric	Parity of permutation (+1 or -1).

7. Sparsity & Meta-Analysis¶

Input: Any Mapping

Function	Type	Meaning
`sparsity`	Metric	Fraction of zero elements ($1 - k/N$).
`density`	Metric	Fraction of non-zero elements ($k/N$).
`deepness`	Metric	Maximum nesting depth.
`wideness`	Metric	Maximum branching factor.
`uniformness`	Metric	Variance of value distribution (0 = uniform).
`is_sparse`	Predicate	Checks if density < threshold.

8. Automata¶

Input: State Machines (Transition Functions)

Function	Type	Meaning
`dfa_step`, `nfa_step`	Structural	Single transition.
`simulate_dfa`, `simulate_nfa`	Structural	Full execution trace.

9. Algebraic Structures¶

Input: Tries & Higher-Order Structures

Function/Class	Type	Meaning
`AlgebraicTrie`	Structure	Sparse Tensor / Prefix Tree over a Semiring.