There is no prime functional digraph: Seifert's proof revisited

This paper provides an accessible, modernized proof of Ralph Seifert's 1971 result that no prime functional digraphs exist, thereby resolving a recent conjecture by Antonio E. Porreca.

The Gist

Here is an explanation of the paper "There is no prime functional digraph: Seifert's proof revisited" using simple language and everyday analogies.

The Big Picture: A World of Digital Machines

Imagine a world made entirely of digital machines.

• The Machine (Functional Digraph): Think of a machine as a group of rooms (vertices). In every room, there is exactly one door leading to the next room. You can't choose where to go; the machine decides for you. If you keep walking through these doors, you will eventually get stuck in a loop (a cycle) or fall into a dead-end that leads to a loop.
• The Rules: These machines can be combined.
  • Addition (+): You just put two machines side-by-side in a warehouse. They run independently.
  • Multiplication (·): You connect them so they run in perfect sync. If Machine A moves from Room 1 to Room 2, and Machine B moves from Room X to Room Y, the combined machine moves from (Room 1, Room X) to (Room 2, Room Y).

The Mystery: Are There "Prime" Machines?

In math, we love Prime Numbers. A prime number (like 7) cannot be built by multiplying smaller numbers together (except 1 and itself). Also, if a prime number divides a product (like $7 \times 14$), it must divide one of the factors.

Mathematicians asked: Do "Prime Machines" exist?
A "Prime Machine" would be a machine that:

1. Cannot be built by multiplying two smaller, non-trivial machines.
2. If it "divides" a combined machine (meaning it is a building block of it), it must be a building block of one of the original parts.

For a long time, people thought these prime machines might exist. In 2020, a mathematician named Antonio Porreca asked, "Do they exist?" and guessed "No." In 2024, it was discovered that a man named Ralph Seifert had already proven the answer was "No" back in 1971.

The Problem: Seifert's 1971 proof was written in very old, very dense, and overly complex language. It was like trying to read a manual written in ancient hieroglyphs when a simple English translation would do.

The Goal of This Paper: Adrien Richard (the author) wanted to translate Seifert's ancient, complex proof into modern, simple language to show why prime machines don't exist.

---

The Three-Step Proof (The Detective Story)

Richard breaks the proof down into three logical steps, like a detective eliminating suspects.

Step 1: The Prime Machine Must Be One Single Unit

The Analogy: Imagine a "Prime Machine" is a single, unbreakable Lego brick.
If you have a machine made of two separate, disconnected parts (like a toy car and a toy boat sitting next to each other), can it be prime?
The Logic: No. Richard shows that if a machine has two disconnected parts, you can always "trick" the math to show it's actually made of smaller pieces.

• Conclusion: A Prime Machine must be connected. All its rooms must be linked together in one big web.

Step 2: The Prime Machine Must Have a "Stop" Button

The Analogy: Imagine a machine where you walk through rooms forever. Eventually, you must hit a "fixed point"—a room that leads back to itself immediately (a loop of length 1).
The Logic: Richard proves that if a connected machine doesn't have this simple "stop" loop, you can construct a scenario where it fails the "Prime" test.

• Conclusion: A Prime Machine must contain a loop of length 1 (a room that points to itself).

Step 3: The Final Blow (Seifert's Masterpiece)

The Analogy: Now we know a Prime Machine must be one connected unit with a "stop" button. Richard says, "Okay, let's try to build a Prime Machine with these rules."
He constructs a specific, tricky scenario:

1. He takes the suspected Prime Machine ($X$).
2. He builds two new, weird machines ($A$ and $B$) that look very different from $X$.
3. He proves that if you multiply $A$ and $B$, you get a result that looks exactly like $X$ multiplied by something else.
4. The Catch: Even though $X$ is part of the final result, it is not a building block of $A$ or $B$ individually.

The Metaphor: Imagine you have a secret recipe for a cake ($X$). You claim your recipe is "prime" because you can't make it from smaller recipes.
Richard shows you that if you mix two completely different ingredients ($A$ and $B$), you end up with a cake that looks like your recipe was used. But, if you look closely at $A$ and $B$, neither of them actually contains your secret recipe.
Because this trick works for any machine with a "stop" button, no such machine can be prime.

Why Was Seifert's Original Proof So Hard?

Richard explains that Seifert was trying to be a "General" rather than a "Specialist."

• Seifert's Approach: He built a massive, complex framework to prove the result for every possible type of graph (infinite ones, graphs with loops, graphs with many doors, etc.). He used heavy machinery (advanced algebra) to solve a simple problem.
• Richard's Approach: He stripped away the heavy machinery. He realized that for just functional digraphs (machines with one door per room), you don't need the complex framework. You just need to look at the loops and the paths.

The Takeaway

1. Prime Machines Don't Exist: Just like you can't find a "prime" Lego brick that can't be built from smaller bricks, you can't find a functional digraph that is "prime." Every single one of them can be broken down or "tricked" into showing it's composite.
2. History Matters: The result was known since 1971 but was forgotten because it was buried in a paper that was too difficult to read.
3. Simplicity Wins: By translating the proof into modern, simple language, Richard showed that the truth is much more elegant and accessible than the original 1971 version suggested.

In short: The paper is a rescue mission. It dug up a forgotten treasure (Seifert's proof), cleaned off the dust, and showed us that the treasure was actually a simple, beautiful key that unlocks the mystery of why "prime" machines are impossible.

Technical Summary

Here is a detailed technical summary of the paper "There is no prime functional digraph: Seifert's proof revisited" by Adrien Richard.

1. Problem Statement and Context

The Object of Study:
The paper focuses on functional digraphs (finite directed graphs where every vertex has exactly one outgoing edge). These structures represent deterministic, finite, discrete-time dynamical systems. The set of functional digraphs, denoted $\mathcal{F}$, is considered up to isomorphism and endowed with two algebraic operations:

• Addition ($+$): The disjoint union of two digraphs.
• Multiplication ($\cdot$): The direct product of two digraphs, where $V(AB) = V(A) \times V(B)$ and the dynamics evolve in parallel.

Under these operations, $\mathcal{F}$ forms a commutative semiring. The multiplicative identity is the cycle of length 1 ($C_1$).

The Core Question:
In 2020, Antonio E. Porreca asked whether prime functional digraphs exist. A functional digraph $X$ is defined as prime if:

1. $X \neq C_1$ (it is not the identity).
2. For all $A, B \in \mathcal{F}$, if $X$ divides $AB$ (i.e., $X \cdot Y \cong AB$ for some $Y$), then $X$ divides $A$ or $X$ divides $B$.

While irreducibility (cannot be factored into non-identity elements) and primality are equivalent in the integers ($\mathbb{N}$), they are distinct in $\mathcal{F}$. Porreca conjectured that no prime functional digraphs exist.

Historical Context:
In 2024, Barbora Hudcová discovered that this result was already proven by Ralph Seifert in 1971. However, Seifert's proof was buried in a paper using different terminology ("unitary algebras"), a much broader framework (general digraphs), and highly technical lemmas that obscured the core logic. The paper aims to revisit and simplify Seifert's proof using modern terminology and accessible arguments.

2. Methodology

The author provides a streamlined, three-step proof of the theorem that no prime functional digraph exists. The methodology involves:

1. Reduction to Connected Components: Proving that if a prime exists, it must be connected.
2. Reduction to Fixed Points: Proving that if a connected prime exists, it must contain a cycle of length 1 ($C_1$).
3. Constructive Counter-Example: Using Seifert's original constructive approach to show that any connected functional digraph containing a fixed point ($C_1$) is not prime.

The author explicitly simplifies Seifert's original arguments by avoiding the general theory of "tricky digraph parameters" (subgroups of $\mathbb{Z}$) used in the 1971 paper, focusing instead on direct combinatorial and structural properties of functional digraphs.

3. Key Contributions and Technical Steps

The proof is divided into three lemmas leading to the main theorem.

Step 1: Prime Functional Digraphs are Connected (Lemma 2)

• Logic: The author assumes a disconnected functional digraph $X$ is prime and derives a contradiction.
• Mechanism: Let $X = X_1 + X_2$ (disjoint union). The proof constructs a specific product involving a large prime $p$ (where $p > \text{max cycle length of } X$).
• Key Insight: By analyzing the cyclic parts (sums of cycles) of the products, the author shows that $X$ cannot divide a specific constructed sum $C_p X_1 + p X_2$ without violating properties of cycle lengths and irreducibility of prime-power cycles ($C_{p^\alpha}$).
• Result: Any prime functional digraph must be connected.

Step 2: Prime Functional Digraphs Contain a Cycle of Length 1 (Lemma 4)

• Logic: The author assumes a connected functional digraph $X$ with a cycle of length $\ell > 1$ is prime and derives a contradiction.
• Mechanism: Let $p$ be a prime factor of $\ell$. The proof utilizes the property of multiplying $X$ by $C_{p^\alpha}$ (where $p^\alpha$ is the highest power of $p$ dividing $\ell$).
• Key Insight: Using the formula $C_n X = (n \land \ell) X'$ (where $\land$ is GCD), the author shows that $X$ divides a product $C_{\ell^2}$ but fails to divide the factors in a way consistent with primality. Specifically, it leads to a contradiction regarding the number of vertices and cycle lengths in the resulting decomposition.
• Result: Any prime functional digraph must belong to the set $\mathcal{F}_1$ (connected digraphs with a unique fixed point/cycle of length 1).

Step 3: No Prime Exists in $\mathcal{F}_1$ (Lemma 5 - Seifert's Core)

• Logic: This is the most complex step. The author proves that for any $X \in \mathcal{F}_1$ (where $X \neq C_1$), there exist $A, B, Y$ such that $XY \cong AB$, but $X \nmid A$ and $X \nmid B$.
• Construction:
  • $A$: Constructed by taking the product $XP$ (where $P$ is a path-like structure) and adding a new vertex $u$ with a specific edge.
  • $B$: A complex product of subgraphs of $X$ (specifically $X|_i$, the subgraph of vertices at distance $\le i$ from the fixed point) with a specific "shift" structure.
  • $Y$: Constructed from $PB$ with additional vertices and edges to bridge the gap.
• Isomorphism: The author defines an explicit bijection $\phi: V(XY) \to V(AB)$ and proves it is an isomorphism by checking the dynamics on all cases of vertex distances.
• Non-Divisibility:
  • $X \nmid A$: Proven by a simple cardinality argument ($|A|/|X|$ is not an integer).
  • $X \nmid B$: Proven by analyzing the "height" (distance to the fixed point) and the number of equivalence classes of vertices under the $(d-1)$-th iteration of the map. The proof shows that if $X$ divided $B$, the height of $B$ would be strictly less than its actual height, a contradiction.
• Result: No element in $\mathcal{F}_1$ is prime.

4. Results

Theorem 1 (Main Result):
There is no prime functional digraph.

• Implication: The semiring of functional digraphs does not possess any prime elements. This contrasts sharply with the integers or polynomial rings, where unique factorization into primes is a fundamental property.

Comparison with Seifert (1971):

• Scope: Seifert proved this for a much broader class of digraphs (including those with minimum out-degree $\ge 1$ and loops).
• Complexity: Seifert's proof relied on defining a parameter $k(A)$ based on subgroups of $\mathbb{Z}$ derived from edge reversals and compositions. Richard's paper demonstrates that for functional digraphs, this heavy machinery is unnecessary; the result follows from elementary properties of cycle lengths, connectivity, and fixed-point distances.

5. Significance

1. Resolution of an Open Problem: The paper definitively resolves the question posed by Porreca in 2020, confirming the conjecture that prime functional digraphs do not exist.
2. Historical Recovery: It brings attention to Ralph Seifert's 1971 work, which had been largely overlooked by the modern community studying functional digraphs and automata networks.
3. Accessibility: By translating Seifert's abstract algebraic proof into the language of modern combinatorics and dynamical systems, the paper makes a deep result accessible to a wider audience of researchers in discrete mathematics, computer science, and network theory.
4. Algebraic Structure: It clarifies the multiplicative structure of the semiring of functional digraphs, highlighting that while unique factorization into irreducibles fails (as shown by $2C_2 = C_2 C_2 = (2C_1)C_2$), the failure is even more profound: there are no "building blocks" (primes) at all.

In summary, the paper provides a transparent, self-contained proof that the multiplicative structure of functional digraphs is fundamentally different from standard number systems, characterized by the total absence of prime elements.