Semirings of formal sums and injective partial transformations

1. Problem Statement and Motivation

Context:
The paper addresses the algebraic modeling of deterministic systems, specifically focusing on the semiring of discrete dynamical systems. In this model:

• Objects: Finite transformations (functions from a finite set to itself), viewed as directed graphs (functional digraphs) up to isomorphism.
• Operations:
  • Sum ($+$): Disjoint union of systems (independent application on distinct sets).
  • Product ($\times$): Parallel composition (direct product of digraphs).

The Challenge:
While the semiring of full transformations has been studied, many real-world systems (e.g., in system biology or computer science) involve partial transformations (where some states have no defined successor, leading to "crashes" or undefined behavior). Furthermore, solving the division equation $ax = b$ in the original semiring (even restricted to permutations, i.e., sums of cycles) is computationally hard; the fastest known algorithms run in sub-exponential time, and the problem is suspected to be NP-complete for general cases.

Objective:
The authors aim to:

1. Extend the semiring of transformations to include partial transformations.
2. Introduce additive torsion by working with formal sums over the binary field $\mathbb{F}_2$ (counting modulo 2).
3. Solve the division problem $ax = b$ efficiently within this new algebraic structure, specifically for injective partial transformations (sums of chains and cycles).

---

2. Methodology and Framework

The authors construct a general framework for semirings of formal sums and then specialize it to the case of injective partial transformations over $\mathbb{F}_2$.

A. General Framework: Semirings of Formal Sums

Let $G$ be a set (e.g., isomorphism classes of graphs) and $S$ be a commutative semiring. The set $S_G$ consists of formal sums $\sum s_g g$ with coefficients in $S$ and finite support.

• Addition: Point-wise addition of coefficients.
• Multiplication: Defined via a bilinear extension of a product map $G \times G \to S_G$.
• Key Insight: If $G$ is a semilattice and $S = \mathbb{F}_2$, the structure $S_G$ becomes a Boolean algebra. This allows the use of lattice-theoretic tools (atoms, intervals, complements) to solve algebraic equations.

B. Specialization to Injective Partial Transformations

The authors focus on the set of injective partial transformations, which decompose uniquely into:

• Chains ($L_d$): Paths of length $d$ ending in a sink (no successor).
• Cycles ($C_d$): Cycles of length $d$.

The study is conducted in the semiring $\mathbb{F}_2(L \cup C)$, where coefficients are modulo 2.

• Modulo 2 Arithmetic: $C_d + C_d = 0$. This introduces significant simplification. For example, $C_d^2 = 0$ if $d$ is even, and $C_d^2 = C_d$ if $d$ is odd.
• Decomposition: Any element can be decomposed into parts based on parity (even/odd lengths) and type (chains/cycles).

---

3. Key Contributions and Results

The paper provides a comprehensive algebraic characterization of the semiring $\mathbb{F}_2(L \cup C)$ and solves the division problem efficiently.

A. The Semiring of Cycles ($\mathbb{F}_2 C$)

The authors first analyze the subsemiring generated by cycles ($S = \mathbb{F}_2 C$).

1. Structure: $S$ is a commutative ring. Elements can be uniquely written as $s = s_0 + s_+$, where $s_0$ contains only odd-length cycles (idempotents) and $s_+$ contains even-length cycles (nilpotent-like behavior).
2. Boolean Algebra of Idempotents: The set of idempotents $S_0$ forms an infinite atomless Boolean algebra.
3. Division Algorithm (Theorem 3.9):
   • The equation $ax = b$ is solved by characterizing the solution set as an interval in the underlying Boolean algebra.
   • Specifically, if $a = \sum a_i C_{2^i}$ and $b = \sum b_i C_{2^i}$, the solution $x = \sum x_i C_{2^i}$ exists if and only if certain conditions on the coefficients $x_i$ hold.
   • Result: The set of solutions is non-empty iff $\lambda_0 \leq \upsilon_0$ (where $\lambda, \upsilon$ are derived from $a$ and $b$). If a solution exists, it can be found in polynomial time (specifically $O(n)$ operations where $n$ is related to the logarithm of the maximum cycle length), contrasting sharply with the sub-exponential complexity of the original semiring.
4. Green's Relations: The authors classify Green's relations ($\mathcal{R}, \mathcal{R}^*, \tilde{\mathcal{R}}$) and show that the multiplicative semigroup is a restriction semigroup. They also classify units, regular elements, and co-regular elements.
5. Injective Polynomials: They classify univariate polynomials $P(x)$ that are injective (and thus surjective) over this semiring, showing they are determined by specific conditions on their coefficients modulo 2.

B. The Semiring of Injective Partial Transformations ($\mathbb{F}_2(L \cup C)$)

The authors extend the results to include chains ($L$).

1. Decomposition: The problem is split into independent sub-problems based on the parity of chain lengths and the interaction between chains and cycles.
2. Chain Algebra: The subsemiring of chains $\mathbb{F}_2 L$ forms a semilattice isomorphic to the lattice of finite subsets of $\mathbb{N}$.
3. Main Division Theorem (Theorem 4.2):
   • The equation $ax = b$ in $\mathbb{F}_2(L \cup C)$ is solved by decoupling the cycle part and the chain part.
   • The cycle part $x(C)$ must satisfy the interval conditions derived in Section 3.
   • The chain part $x(\epsilon)$ (for even/odd lengths) is constrained by intervals in the Boolean algebra generated by chains of specific heights.
   • Efficiency: The solution set is characterized by finite intervals in Boolean algebras, allowing for efficient verification and construction of solutions.

---

4. Significance and Impact

1. Algorithmic Breakthrough: The most significant contribution is the efficient (polynomial-time) solution to the division problem $ax = b$ for sums of cycles and injective partial transformations over $\mathbb{F}_2$. This resolves a major open complexity issue in the original semiring of discrete dynamical systems, where no efficient algorithm was known.
2. Algebraic Unification: The paper successfully unifies the study of transformations, partial transformations, and formal sums under a single framework of semirings of formal sums. It demonstrates how introducing torsion (modulo 2) transforms a complex combinatorial problem into a tractable algebraic one involving Boolean algebras.
3. Structural Insights: The characterization of Green's relations, units, and regular elements provides a deep understanding of the multiplicative structure of these systems. The identification of the semigroup as a restriction semigroup connects this work to broader semigroup theory.
4. Practical Applications: By modeling systems with partial information or potential crashes (partial transformations) and utilizing the simplifications of $\mathbb{F}_2$, the framework offers new tools for analyzing modularity in complex systems like Boolean networks, cellular automata, and biological systems where exact state transitions may be unknown or undefined.

Conclusion

The paper establishes that by shifting the perspective from natural numbers to the binary field $\mathbb{F}_2$ and extending the domain to partial transformations, the algebraic complexity of the division problem is drastically reduced. The solutions are no longer hidden in sub-exponential search spaces but are explicitly described as intervals within Boolean algebras, providing a powerful new tool for the analysis of modular deterministic systems.