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

Dit artikel presenteert een toegankelijker bewijs, gebaseerd op een vergeten artikel uit 1971 van Ralph Seifert, dat aantoont dat er geen priemfunctionele digraphen bestaan.

De kern

De Grote Misvatting: Bestaan er "Onbreekbare" Digitale Systemen?

Stel je voor dat je een wereld hebt vol met machines. Elke machine heeft een knop. Als je op de knop drukt, gaat de machine naar precies één volgende toestand. Geen keuzes, geen twijfel: drukken = resultaat. In de wiskunde noemen we dit een functioneel digraaf.

De schrijver van dit paper, Adrien Richard, vertelt ons een verhaal over een mysterie dat decennia lang onopgelost leek te zijn.

1. Het Speelgoeddoosje (De Wiskundige Wereld)

Stel je voor dat je al deze machines in een speelgoeddoos hebt. Je kunt twee dingen doen met deze machines:

• Optellen (+): Je plakt twee machines naast elkaar. Ze werken onafhankelijk van elkaar.
• Vermenigvuldigen (·): Je koppelt twee machines aan elkaar. Ze werken tegelijkertijd. Als machine A naar toestand 1 gaat en machine B naar toestand 2, gaat de gekoppelde machine naar de combinatie (1, 2).

In deze wereld is er een speciaal soort machine: een priemmachine (prime).
Een priemmachine is als een onbreekbaar blokje. De definitie is:

"Als je deze machine vermenigvuldigt met een andere machine en het resultaat is een combinatie van twee andere machines, dan moet de oorspronkelijke machine eigenlijk al in één van die twee stekken hebben gezeten."

Klinkt ingewikkeld? Denk aan getallen. Het getal 7 is een priemgetal. Als je 7 vermenigvuldigt met iets, en dat resultaat is te splitsen in twee andere getallen, dan moet 7 in één van die getallen zitten. In de wereld van de getallen bestaan er dus priemgetallen.

2. Het Grote Vraagstuk

In 2020 vroeg de wiskundige Antonio Porreca zich af: "Bestaan er priemmachines in onze speelgoeddoos?"
Hij dacht van wel. Hij dacht dat er misschien een machine was die zo fundamenteel was, dat je hem niet uit kleinere stukjes kon bouwen, en die je ook niet kon 'ontleden' als je hem vermenigvuldigde.

Hij stelde zelfs de hypothese dat ze misschien niet bestaan, maar hij had geen bewijs.

3. De Vergeten Schat (Seifert's Bewijs)

Toen kwam Barbora Hudcová in 2024 met een verrassing. Ze vond een vergeten paper uit 1971 van een man genaamd Ralph Seifert.
Seifert had het antwoord al 50 jaar geleden gegeven: Nee, er bestaan geen priemmachines.

Het probleem? Seifert's paper was geschreven in een taal die niemand meer sprak. Het was vol met zware wiskundige jargon en bewijzen die veel te complex waren voor het simpele vraagstuk. Het was alsof iemand een recept voor een boterham had geschreven in de taal van de quantumfysica.

4. De Oplossing: Een Simpel Recept

Adrien Richard (de auteur van dit paper) zegt: "Laten we Seifert's bewijs nemen, maar dan vertalen naar begrijpelijke taal en de overbodige zware gewichten eraf halen."

Hij bewijst in drie simpele stappen waarom er geen priemmachine bestaat:

• Stap 1: De machine moet één stuk zijn.
  Stel je hebt een machine die uit twee losse delen bestaat (bijvoorbeeld een auto en een fiets die niet aan elkaar vastzitten). Richard zegt: "Als je zo'n losse machine vermenigvuldigt, kun je altijd een trucje bedenken om te laten zien dat hij 'samenstelling' is, en dus niet 'priem'."
  Conclusie: Een echte kandidaat-priemmachine moet één samenhangend geheel zijn.

• Stap 2: De machine moet een 'stop' hebben.
  Elke machine in onze wereld heeft een cyclus (een lus). Een priemmachine moet een cyclus hebben van lengte 1. Dat betekent: er is een knop die je kunt indrukken die de machine direct terugstopt naar zichzelf. Een 'rustpunt'.
  Conclusie: Als je machine geen rustpunt heeft, is hij geen priemmachine.

• Stap 3: De Onmogelijke Constructie (Het Geniale Deel).
  Dit is het moeilijkste stukje. Stel je hebt een machine die wel één stuk is en wel een rustpunt heeft. Richard (volgend op Seifert) zegt: "Ik ga nu een nieuwe machine bouwen die eruitziet alsof hij uit jouw machine is gemaakt, maar dat is hij niet."

  Hij gebruikt een creatieve constructie:

  1. Hij neemt jouw machine.
  2. Hij bouwt een 'spiegelbeeld' en een 'uitbreiding' ervan.
  3. Hij laat zien dat je jouw machine kunt maken door twee andere machines te vermenigvuldigen.
  4. Maar! Die twee andere machines bevatten jouw machine niet.

  De Analogie:
  Stel je hebt een unieke LEGO-blok (je machine). Je denkt: "Dit blok is zo uniek, dat je het niet kunt maken door andere blokken te combineren."
  Richard pakt dit blok, bouwt er een gigantisch kasteel omheen, en zegt: "Kijk, dit kasteel kan worden opgebouwd uit twee andere kasteeltjes. Maar als je die twee kasteeltjes uit elkaar haalt, zit jouw unieke blok er niet in."

  Omdat hij dit voor elke mogelijke machine kan doen, betekent het dat geen enkele machine aan de definitie van "priem" voldoet.

5. Waarom is dit belangrijk?

In de wereld van de getallen zijn priemgetallen de bouwstenen. Alles is een combinatie van priemgetallen.
Richard laat zien dat in de wereld van deze digitale systemen (machines die naar één volgende toestand gaan), er geen bouwstenen zijn. Alles is op een of andere manier "samengesteld" uit andere dingen. Er is geen "atoom" dat niet verder te splitsen is.

Samenvattend:
Het paper is een vertaling van een oud, moeilijk wiskundig bewijs naar een helder verhaal. Het antwoord op de vraag "Bestaan er priemmachines?" is een definitief Nee. Er is geen machine die zo fundamenteel is dat hij niet uit andere machines kan worden opgebouwd of ontbonden.

Het is als zeggen: "In dit universum van machines is er geen 'Goddelijke Munt' die je niet kunt vervalsen of opbouwen uit andere munten." Alles is verbonden, alles is samengesteld.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "There is no prime functional digraph: Seifert's proof revisited" van Adrien Richard, vertaald en samengevat in het Nederlands.

Titel en Context

Titel: Er bestaat geen priem functioneel digraaf: Seifert's bewijs herzien
Auteur: Adrien Richard
Datum: 11 maart 2026
Onderwerp: Combinatoriek, algebraïsche structuur van dynamische systemen, digrafen.

1. Het Probleem

Het artikel behandelt de algebraïsche structuur van functionele digrafen. Een functioneel digraaf is een eindige gerichte graaf waarbij elke knop precies één uitgaande buur heeft (een deterministisch dynamisch systeem). Deze verzameling, genoteerd als $\mathcal{F}$, vormt een commutatieve halve ring (semiring) onder twee operaties:

• Optelling ($A+B$): De disjuncte unie van twee digrafen.
• Vermenigvuldiging ($A \cdot B$): Het directe product, waarbij de knoppen $V(A) \times V(B)$ zijn en de dynamica parallel evolueert.

In deze context is een digraaf $X$ priem (prime) als:

1. $X$ niet de eenheid is voor vermenigvuldiging (de cyclus van lengte 1, $C_1$).
2. Voor alle $A, B \in \mathcal{F}$ geldt: als $X$ een deler is van $AB$ (d.w.z. $X \cdot Y \cong AB$ voor zekere $Y$), dan moet $X$ een deler zijn van $A$ of een deler zijn van $B$.

De vraag: Bestaan er priem functionele digrafen?
In 2020 stelde Antonio E. Porreca deze vraag en vermoedde in 2023 dat het antwoord "nee" is. In 2024 werd ontdekt dat Ralph Seifert dit resultaat al in 1971 had bewezen in een vergeten paper. Seifert's bewijs was echter zeer technisch, gebruikte een bredere, abstracte raamwerk (unitaire algebra's) en was moeilijk toegankelijk voor hedendaagse onderzoekers.

2. Methodologie

Adrien Richard presenteert een vereenvoudigd en toegankelijker bewijs van Seifert's stelling, volledig vertaald naar de moderne terminologie van functionele digrafen. Het bewijs verloopt in drie logische stappen:

1. Reductie naar samenhangende digrafen:
   Het wordt bewezen dat elke priem functionele digraaf noodzakelijkerwijs samenhangend moet zijn. Als een digraaf uit meerdere componenten bestaat, kan deze altijd worden ontbonden in een product dat de priemeigenschap schendt.

2. Reductie naar digrafen met een cyclus van lengte 1:
   Het wordt bewezen dat elke samenhangende priem digraaf een cyclus van lengte 1 (een vast punt) moet bevatten. Digrafen met cycli van lengte $>1$ kunnen worden ontbonden door gebruik te maken van eigenschappen van het product van cycli en de irreducibiliteit van bepaalde structuren.

3. Constructief bewijs voor $F_1$:
   De kern van het bewijs is het tonen dat er geen priem digraaf bestaat binnen de klasse $F_1$ (samenhangende digrafen met een cyclus van lengte 1).

   • Voor een willekeurige $X \in F_1$ (met $X \neq C_1$) construeert Richard expliciet twee andere digrafen $A$ en $B$ en een digraaf $Y$ zodanig dat:
     $$X \cdot Y \cong A \cdot B$$
   • Echter, $X$ deelt noch $A$ noch $B$.
   • Deze constructie is gebaseerd op Seifert's originele ideeën maar wordt hier stap voor stap uitgewerkt met duidelijke definities van de knoppen, randen en een expliciete isomorfisme $\phi$ tussen $XY$ en $AB$.

3. Belangrijkste Resultaten

• Hoofdstelling (Theorem 1): Er bestaat geen priem functioneel digraaf.
  Dit betekent dat de verzameling $\mathcal{F}$ geen "priemelementen" kent in de algebraïsche zin van de definitie. Elk niet-triviaal element kan worden "gefactoriseerd" op een manier die de priemdefinitie schendt.
• Vereenvoudiging van Seifert's werk:
  Het artikel toont aan dat Seifert's complexe lemmata over algemene digrafenklassen (zoals $D$, $S$, $R$) en parameters zoals $k(A)$ (een groep-generator gerelateerd aan cycli) overbodig zijn voor dit specifieke resultaat. De essentie kan worden bewezen met elementaire eigenschappen van de cyclische delen en constructieve isomorfismen.
• Isomorfisme-construktie:
  Het artikel biedt een gedetailleerde constructie (Lemma 5) van de digrafen $A$, $B$ en $Y$ en het isomorfisme $\phi$, wat in Seifert's originele paper slechts impliciet of zeer technisch werd gepresenteerd.

4. Bijdragen en Significance

• Toegankelijkheid: Het grootste deel van de bijdrage is het "ontgrendelen" van een historisch resultaat. Seifert's paper uit 1971 werd nauwelijks geciteerd en was onbegrijpelijk voor de huidige gemeenschap vanwege de gebruikte terminologie en de overmatige generalisatie. Richard maakt dit resultaat beschikbaar voor onderzoekers in dynamische systemen, automata-netwerken en combinatoriek.
• Klaarheid in Algebraïsche Structuur: Het resultaat verduidelijkt de multiplicatieve structuur van de halve ring van functionele digrafen. Het toont aan dat, in tegenstelling tot de natuurlijke getallen $\mathbb{N}$ of polynomen, er hier geen unieke factorisatie in priemelementen mogelijk is (en zelfs geen priemelementen bestaan).
• Historische Correctie: Het artikel erkent en valideert Seifert's prioriteit, terwijl het tegelijkertijd de onafhankelijke vermoedens van Porreca en zijn studenten bevestigt.
• Didactische Waarde: Door de constructieve stappen expliciet uit te werken (zoals in Figuur 1-4 van het artikel), biedt het een blauwdruk voor het analyseren van productstructuren in functionele digrafen, wat nuttig kan zijn voor toekomstig onderzoek naar complexiteit en factorisatieproblemen in deze domeinen.

Conclusie:
Adrien Richard bewijst dat de zoektocht naar priem functionele digrafen vruchteloos is. Door Seifert's complexe bewijs te herschrijven in moderne taal en te reduceren tot de essentie, levert hij een fundamenteel inzicht in de algebraïsche eigenschappen van deterministische dynamische systemen. Het resultaat is dat de "priem" eigenschap in deze context triviaal is: ze bestaat niet.