FPRD cycle: the five-site rooted semantic-GCD obstruction

Date: 2026-07-29
Status: theorem proved for the pinned finite cyclic Boolean carrier; independently enumerated through five sites; physical WFL/THFL and D30 transport still open.

1. Strongest result

The smallest cyclic carrier with two named reflection generators already separates three notions that had been in danger of being conflated:

1. raw append/permutation updates have a canonical intersection GCD;
2. equality of complete legal future observations is a computable right congruence;
3. the resulting semantic factor preorder need not have a greatest common factor.

The failure occurs at five sites. It is caused by independent residual reframing under the two hinge symmetries: an edge and a diagonal are incomparable maximal common factors.

This closes the proposed “compute one canonical common divisor, then minimize its residual row” route for the pinned semantic carrier. It does not rule out direct minimization of the full future-row transition system.

2. Pinned causal carrier

Let

$$X=\mathbb Z/5\mathbb Z$$

and let

$$h_0(i)=-i,\qquad h_1(i)=2-i\pmod 5.$$

These two reflections generate $G=D_5$. A Boolean substrate is a set $S\subseteq X$ of opened sites. An update

$$x=(p,A)\in G\ltimes 2^X$$

acts by

$$T_x(S)=A\cup p(S). \tag{1}$$

Writes are append-only. The carrier has one $G$-orbit, hence one complete fiber, and

$$\operatorname{Look}(S)=1\iff S=X. \tag{2}$$

The controller is a singleton. The opened-site mask is persistent substrate history, not controller state.

Causal composition convention

If prefix update $x=(p,A)$ is followed by continuation $y=(q,B)$, the sequential composite is

$$x;y:=T_y\circ T_x,$$

so its final mask from the empty substrate is

$$B\cup q(A). \tag{3}$$

This order is load-bearing. It matches an inner prefix divisor followed by an outer residual update.

For a prefix $x$, retain its complete future row

$$R_x(y)=\operatorname{Look}(T_y(T_x(\varnothing))) \qquad(y\in G\ltimes2^X). \tag{4}$$

Because the carrier has one fiber,

$$R_{(p,A)}(q,B)=1 \iff B\cup q(A)=X. \tag{5}$$

3. The full-future quotient is exact and computable

Lemma 1 — complete future rows recover the archive mask

$$R_{(p,A)}=R_{(p',A')} \iff A=A'. \tag{6}$$

Proof. The forward implication is the only nontrivial one. If $x\in A\setminus A'$, take $q=1$ and $B=X\setminus A$. Then $B\cup A=X$, but $B\cup A'$ misses $x$. The reverse implication is immediate from (5). $\square$

Thus future-row equivalence has exactly $2^5=32$ classes. It is a right congruence under causal extension: if $R_x=R_{x'}$, then for every continuation $y$ and suffix $z$,

$$R_{x;y}(z)=R_x(y;z)=R_{x'}(y;z)=R_{x';y}(z). \tag{7}$$

This proves that an intrinsic right congruence exists on the finite carrier. It also shows that it retains the whole site archive: there is no archive compression in this transitive instance.

4. Exact semantic factor order

Write $[A]\preceq[C]$ when a prefix with future-row class $A$ is a semantic causal factor of a target with class $C$. By (3) and (6),

$$[A]\preceq[C] \iff \exists q\in G,\ \exists B\subseteq X: B\cup q(A)=C \iff \exists q\in G:\ q(A)\subseteq C. \tag{8}$$

Association by hinge units is exactly membership in the same $G$-orbit.

For targets $C_1,\ldots,C_k$, define the common-subpattern family

$$\mathcal P(C_1,\ldots,C_k)= \{A\subseteq X:\forall j\ \exists q_j\in G,\ q_j(A)\subseteq C_j\}. \tag{9}$$

Theorem 2 — finite semantic-GCD criterion

A greatest common semantic causal factor exists up to units iff the inclusion-maximal members of $\mathcal P(C_1,\ldots,C_k)$ form one $G$-orbit.

Proof. Equation (8) identifies common factors with $\mathcal P$. If all maximal members are translates of $K$, every common factor is contained in a maximal member and therefore divides $K$; $K$ is greatest. Conversely, if $K$ is greatest and $D$ is maximal, then $D\preceq K$, so a translate of $D$ is contained in $K$. Maximality of both common factors forces equality. $\square$

The criterion is computable by finite subset-and-group enumeration and is invariant under simultaneous relabeling

$$(X,G,C_1,\ldots,C_k) \mapsto (\phi X,\phi G\phi^{-1},\phi C_1,\ldots,\phi C_k).$$

5. Five-site obstruction and finite certificate

Take

$$C_1=\{0,1,2\},\qquad C_2=\{0,1,3\}. \tag{10}$$

Their complements are, respectively, a diagonal and an edge, so $C_1$ and $C_2$ are not $D_5$-congruent.

Two common factors are

$$E=\{0,1\}\quad\text{(edge)},\qquad F=\{0,2\}\quad\text{(diagonal)}. \tag{11}$$

Each target contains a translate of both $E$ and $F$. The factors are not associated because dihedral symmetries preserve cyclic distance.

No three-site common factor exists. A three-site pattern that embeds into a three-site target must be congruent to that target; this would force $C_1$ and $C_2$ to be congruent. Therefore every maximal common factor has size two, and both the edge and diagonal orbits occur.

Theorem 3 — no canonical semantic common divisor at five sites

The targets $C_1,C_2$ have common semantic causal factors but no greatest one, even up to hinge units.

Proof. The edge and diagonal are nonassociated maximal common factors by the preceding paragraph. A greatest factor would have to dominate both. A two-site candidate cannot belong to both orbits, and a larger common factor does not exist. $\square$

The checkable certificate consists only of

$$(X,h_0,h_1; C_1,C_2;E,F)$$

and four finite checks:

1. $h_0,h_1$ generate $D_5$;
2. $E,F$ are the two distinct two-subset orbits;
3. each $C_j$ contains a translate of both $E$ and $F$;
4. $C_1,C_2$ are distinct three-subset orbits.

No numerical solver or heuristic search is involved.

6. Raw-versus-semantic contrast

In the raw syntactic append/permutation monoid, a target vector with write masks $A_j$ has ordinary left GCD

$$(1,\bigcap_j A_j), \tag{12}$$

unique up to permutation units. This follows because a raw factor with mask $A$ divides a raw target with mask $B$ exactly when $A\subseteq B$.

The semantic quotient changes the factor preorder. Each target component may choose its own legal hinge alignment $q_j$, producing the orbit-containment condition (8). For $C_1,C_2$, the raw intersection is the edge $\{0,1\}$, but semantic reframing exposes the diagonal as a second maximal factor and destroys greatestness.

This is not a contradiction. Full-future equivalence is a right congruence. It need not be a two-sided monoid congruence compatible with the raw semilattice meet. Quotienting a right action can therefore destroy the GCD property even when the raw update monoid has GCDs.

7. Repairs and exact boundary cases

The obstruction disappears under either of two stronger doctrines:

1. Pinned rooted alignment. If every residual must use $q=1$, then $A\preceq C$ is ordinary inclusion and the unique greatest common factor is $\bigcap_j C_j$.
2. One alignment shared across the vector. If the same $q$ must serve every target component, the independent edge/diagonal reframings used in the obstruction are unavailable.

The result therefore isolates symmetry-orbit ambiguity, not Boolean append-only storage alone.

The earlier current-Look quotient fails for a different reason: it is not even a right congruence. On the three-site transitive carrier, $\varnothing$ and $\{0\}$ both currently output zero, but appending $\{1,2\}$ separates them.

8. Computation and hostile audit

Two independent exhaustive programs were used.

• check_causal_future_gcd.py enumerates the correct prefix-then-continuation factor preorder. It checks all target pairs through $n=4$ and finds the first cyclic-family failure at $n=5$, with targets $7,11$ and maximal factor representatives $3,5$ in bit-mask notation.
• check_two_hinge_epi_gcd.py verifies the raw syntactic intersection-GCD theorem through $n=4$ and checks exact future observation kernels.

An independent hostile audit initially obtained a positive quotient-GCD claim by quotienting masks under coordinatewise union. That calculation is valid for the pinned-alignment semilattice, but it does not model independent hinge reframing in each semantic residual. Distinguishing a right observational quotient from a two-sided semidirect-product quotient resolves the apparent contradiction.

The census establishes minimality only in the pinned cyclic family. It does not establish minimality over all two-hinge physical geometries.

9. Comparator status

The closest exact primary comparator is Christian Bianchini and Gabriele Puppis, Minimization of Streaming Transducers, LICS 2026:

https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.18

They define update-vector GCDs/EGCDs, prove uniqueness up to isomorphism and compatibility with prefix sub-vectors under explicit hypotheses, and use them to construct minimal streaming transducers. They also give incomparable maximal-divisor examples when the legal update language cannot retain the required joint tuple. The FPRD pentagon obstruction is a new instantiation inside the pinned Boolean incidence carrier; no external novelty claim is made.

Other useful boundaries:

• Quentin Aristote, Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids, LMCS 2025: https://lmcs.episciences.org/16670. Semilattice infima alone do not supply cancellation or invariant residual normalization.
• Colcombet and Petrişan, Automata Minimization: a Functorial Approach, LMCS 2020: https://lmcs.episciences.org/6213. Reachability restriction and observational quotienting are separate steps.
• An–Demaine–Demaine–Ku, Computing Any Boolean Function by Folding and Unfolding, CCCG 2017: https://erikdemaine.org/papers/FoldCutMachine_CCCG2017/paper.pdf. This supports the physical Boolean Look comparator, not the divisor theorem.

10. What remains unproved

The carrier deliberately omits interval boundaries, orientation, layer order, thickness, partial folds, irreversible stacking, bounded-role generation, and D30 hold/advance head bonds. Therefore the following remain open:

1. a faithful embedding of the five-site certificate into an actual interval two-hinge WFL/THFL execution;
2. whether physical legality pins the alignment strongly enough to restore a canonical factor;
3. the corresponding restricted-D30 factor category and its legal epis;
4. whether a finite set of all maximal factors, rather than one GCD, yields a computable enriched atlas construction;
5. finite-index bounds when the observable archive grows with the grade.

11. Exact next attack

Compile the pentagon certificate into the smallest typed irreversible two-fold incidence category. Make phase, interval extent, material address, orientation/layer order, and reachable head bonds part of the object type. Then test the two alternatives:

• if both edge and diagonal residual alignments are physically legal but no common three-site carrier is, the present certificate transports to a real finite dual obstruction;
• if legal rooted geometry forces one alignment, record the repair theorem and compute the resulting enriched right congruence directly.

That experiment decides whether the semantic obstruction is genuinely physical or an artifact of treating hinge motions as freely reusable units.