# Conjecture 8: From Proof to Theory

**Aidan Edward Lawson · September 2026**

**Status:** Computer-assisted candidate proof. The complete argument is given below; independent verification remains open.

While writing *The Inner Apocalypse*, I sent a mathematician an eight-page proof and a machine checker. Asking for criticism was reasonable. I had also left the recipient with much of the work of turning that proof into something other people could understand and use.

The next day I started **Proof-to-Theory (PTT)**: a project for extracting the mechanism behind a proof, testing what survives when the assumptions change, and making the resulting mathematics accessible without requiring everyone to repeat the original research.

The gap is straightforward. A proof can establish that a result follows from its assumptions without giving a reader a useful picture of why it works. A summary can shorten the proof without closing that gap. PTT adds examples, alternative representations, and counterexamples that show what the explanation can and cannot predict.

It began with this automaton family. The work then expanded to modified machines, more compact certificates, other finite structures, and methods for selecting useful mathematical questions. For Conjecture 8, the important developments were a shorter description of the lower-bound certificate, an explicit whole-machine reset word, and examples in which the same long operations conceal different shortest paths. Those developments are brought together here.

## 1. The question

An automaton is a finite machine with states and rules for moving between them. This one has two inputs, **a** and **b**. Each input sends every current state to exactly one next state. A sequence of inputs is called a *word*.

Apply the same word from two different starting states. If their paths meet, they remain together under every later shared input. A *reset word* brings **all** starting states to one final state. A machine that has a reset word is *synchronizing*.

The Dżyga–Szykuła family has $n=3k+6$ states, for integers $k\ge1$. Conjecture 8 asks whether these machines synchronize and whether the history starting at state 0 first becomes mergeable with another starting history after exactly

$$\tau(0)=4k+8=\frac{4n}{3}$$

inputs. The minimum is over every possible companion of 0 and every possible word. It is **not** the time needed to reset the whole machine. [1]

We will use the twelve-state example, $k=2$. Its complete transition table is:

| State | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|:---|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|
| **a** | 0 | 2 | 1 | 4 | 3 | 6 | 5 | 8 | 9 | 3 | 11 | 10 |
| **b** | 1 | 0 | 3 | 2 | 5 | 4 | 7 | 6 | 2 | 10 | 9 | 11 |

For example, **b** moves 0 to 1; **a** then moves 1 to 2. Words are read left to right.


## 2. A route and a lower bound

The word

```text
babababaabababab
```

merges the histories starting at 0 and 2. It consists of four repetitions of **ba**, followed by four repetitions of **ab**.

| Inputs used | History from 0 | History from 2 |
|---:|---:|---:|
| 0 | 0 | 2 |
| 8 | 8 | 1 |
| 15 | 3 | 8 |
| 16 | 2 | 2 |

The last **b** causes the collision. Five possible images of the whole machine still remain.

This gives an **upper bound**: sixteen inputs suffice. A lower bound must exclude every shorter word, including words using a different companion of 0.

To do that, treat each pair of current states as one point in a new graph. A letter moves the pair according to the transition table. Pairs with equal entries, such as $(2,2)$, are the collision targets. The question becomes a shortest-path problem from the initial pairs $(0,p)$ to those targets.

The original proof assigns a *Bellman potential* to each pair. It starts at sixteen on every permitted initial pair, reaches zero at a collision, and cannot decrease by more than one per input. A collision therefore needs at least sixteen inputs. Its general formula covers $k\ge5$, with the four smaller cases handled by exact graph search; see **Mathematical reference B** below.

The later PTT work gives a compact **progress certificate**, $F$, valid for every $k\ge1$. It starts at zero, takes value sixteen on collision targets in this example, and obeys

$$F(\text{next pair})\le F(\text{current pair})+1.$$

After fifteen inputs, its value is at most fifteen. It cannot yet be at a collision target. The complete formula, including all boundary cases, is in **Mathematical reference B** below.

The successful word and the certificate meet at sixteen. In general, write $m=k+2$, so $n=3m$. The word

$$W=(ba)^m(ab)^m$$

has $4m$ letters and merges 0 with 2. The certificate excludes every shorter collision involving 0. Together they give $\tau(0)=4m=4n/3$.

## 3. Resetting the whole machine

The sixteen-letter word leaves five possible states in the twelve-state machine. Applying it again leaves the same five. Its transformation is *idempotent*: $W$ has no further effect once it has acted.

The reset mechanism becomes visible when we group inputs. The operation **ab** rotates these six states:

$$0\to1\to3\to5\to7\to2\to0.$$

Each displayed arrow costs two inputs. On this cycle, $W$ fixes every state except 0, which it sends to 2. Thus **ab** supplies a rotation and $W$ supplies a fold.

After the first $W$, the possible states are $\{1,3,5,7,2\}$. Apply **ab**, then $W$. The rotation brings another surviving position into 0; the fold merges it into 2. Four possible states remain. Repeating that block reduces the count to three, two, and one.

For every member of the family, the later PTT construction supplies the explicit reset word

$$\mathcal R=W\big((ab)W\big)^m,$$

of length $4m^2+6m$. In the twelve-state example, its length is **88**. This is an explicit reset construction, not a claim that 88 is the shortest possible reset word.

The original manuscript proves synchronization through a related rotation and reflection/fold argument. The later construction makes one reset sequence available directly. Both distinguish rotation from merging: repeating **ba** alone preserves a cycle and cannot synchronize the machine; see **Mathematical reference D**.

## 4. What changes when two arrows move?

A useful explanation should also expose its limits.

In the twelve-state machine, change **b(7)** from 6 to 5. The shortest collision involving the history from 0 still takes sixteen inputs.

Restore that arrow and change **b(10)** from 9 to 4. Again, sixteen.

Make both changes together. The shortest collision now takes **fifteen** inputs:

```text
babababaabababb
```

| Machine | Shortest collision involving 0 |
|:---|---:|
| Original | 16 |
| Only b(7) changed | 16 |
| Only b(10) changed | 16 |
| Both changed | 15 |

These changes preserve the complete transformations produced by $(ba)^4$ and $(ab)^4$. Each long block sends every starting state to the same final state as before. The old word $W$ therefore still works exactly as before. It is simply no longer shortest when both arrows change; see **Mathematical reference E**.


This separates two kinds of understanding. The long-block description explains the common witness and reset mechanism. It cannot, on its own, distinguish the original sixteen-input threshold from the modified fifteen-input threshold. That difference lives in the intermediate transitions.

There is a further distinction. A one-arrow change can invalidate the original progress certificate even while the threshold remains sixteen. A failed certificate does not automatically make the claimed bound false. The fifteen-letter word in the two-arrow case actually does refute the old bound **for that modified machine**.

This is the gap PTT closes here. The result becomes more than a number and a proof: the reader can distinguish the mechanism, the optimality argument, and a concrete way that one can survive while the other changes.

## 5. What the public version adds

The original manuscript already contained the transition rules, a synchronization proof, and the lower-bound certificate. This version connects those arguments to visible examples and later extensions. The mathematical reference is included below; no research archive is needed to read it.

The browser edition lets a reader run inputs, inspect intermediate states, and compare the altered machines. The Markdown and PDF contain the explanation and mathematical reference without the interactive controls.

A specialist can still find an error, improve an argument, identify a connection, or formalize a step. They no longer have to provide the first explanation before anyone else can begin. Readers can inspect the same objects at different levels, and the author can do more of that preparation before requesting review.

## Mathematical reference

### A. Family and statement

Let $m=k+2\ge3$, $Q=\{0,\ldots,3m-1\}$, and $e=3m-1$. Write $\delta(q,w)$ for the state reached from $q$ after applying word $w$ from left to right. The transitions are:

| State $q$ | $a(q)$ | $b(q)$ |
|:---|:---|:---|
| $0$ | $0$ | $1$ |
| $1\le q<2m$, odd | $q+1$ | $q-1$ |
| $1\le q<2m$, even | $q-1$ | $q+1$ |
| $2m$ | $2m+1$ | $2$ |
| $2m+1$ | $3$ | $2m+2$ |
| $2m+2\le q<e$, even | $q+1$ | $q-1$ |
| $2m+2\le q<e$, odd | $q-1$ | $q+1$ |
| $e$, even | $e$ | $e-1$ |
| $e$, odd | $e-1$ | $e$ |

Define

$$\tau(0)=\min\{\,|w|:\exists p\ne0,\ \delta(0,w)=\delta(p,w)\,\}.$$

The result is that this family is strongly connected and synchronizing, with $\tau(0)=4m$. The matching word is $W=(ba)^m(ab)^m$. It merges 0 with 2 and ends at 2.

Strong connectivity follows directly: every state except the endpoint has an edge to its successor, so 0 reaches every state. Every positive state has an edge to a smaller index, including the jumps $2m\to2$ and $2m+1\to3$. Hence every state reaches 0.

### B. Lower bound: the compact certificate

Use unordered pairs, sorted as $0\le i\le j<3m$. Put $s=i+j$ and $d=j-i$. Apply the following cases in order.

First,

$$F(i,i)=4m,\qquad F(0,j)=0\quad(j>0).$$

For distinct positive pairs with even $s$,

$$F(i,j)=\begin{cases}
i,&s<4m,\\
2m+i-1,&s=4m,\\
4m,&s>4m.
\end{cases}$$

For distinct positive pairs with odd $s$, use the first applicable row:

| Condition | $F(i,j)$ |
|:---|:---|
| $s<2m+1$ or $d>2m-1$ | $i$ |
| $s=2m+1$ | $2m-2+\lvert i-3\rvert$ |
| $d=2m-1$ | $2m+i-1$ |
| $(i,j)=(3,2m)$ | $4m-1$ |
| Otherwise | $4m$ |

**Local inequality.** Substituting the transition rules into these cases gives, for either letter $c$ and every pair,

$$F\big(\operatorname{sort}(c(i),c(j))\big)\le F(i,j)+1.$$

The piecewise integer inequalities are the computer-assisted part of this certificate. Their checks range over arbitrary integers $m\ge3$, rather than a bounded list of machine sizes.

For example, $F(1,2m)=2m$. The letter **a** sends this pair to $(2,2m+1)$, whose difference is $2m-1$ and whose value is $2m+1$. At the final merge gate, $F(3,2m)=4m-1$, while $b(3)=b(2m)=2$ and $F(2,2)=4m$.

**Lower-bound proof.** Every initial pair $(0,p)$ has value zero. Induction using the local inequality gives $F(P_t)\le t$ after $t$ letters. If the first collision occurs after $\ell$ letters, its value is $4m$, so $4m\le\ell$. This covers every partner and every word.

This is a later certificate from PTT, not a transcription of the original manuscript's 25-case potential. It proves the same lower bound with a uniform domain $m\ge3$.

### C. Upper bound and the two cycles

Put $U=ba$ and $V=ab$. Their cycles are

$$C_U=(0,2,4,\ldots,2m,1),$$

$$C_V=(0,1,3,5,\ldots,2m-1,2).$$

Each has $m+2$ states, and its corresponding macro advances one position. The following phase and depth coordinates specify the powers $U^m$ and $V^m$ completely. Cycle indices are read modulo $m+2$. A row applies only when the indicated state belongs to $Q$; unspecified $r$ ranges over nonnegative integers.

| State | Phase under $U$ | Depth under $U$ |
|:---|:---|:---|
| $0$ | $0$ | $0$ |
| $1$ | $m+1$ | $0$ |
| $2r$, $1\le r\le m$ | $r$ | $0$ |
| $2r+1$, $1\le r\le m-1$ | $m+1-r$ | $r$ |
| $2m+1+2r$ | $r+1$ | $m-r$ |
| $2m+2+2r$ | $m-1-r$ | $r+2$ |

| State | Phase under $V$ | Depth under $V$ |
|:---|:---|:---|
| $0$ | $0$ | $0$ |
| $2$ | $m+1$ | $0$ |
| $2r-1$, $1\le r\le m$ | $r$ | $0$ |
| $2r$, $2\le r\le m-1$ | $m+2-r$ | $r-1$ |
| $2m+2r$ | $r+1$ | $m-r$ |
| $2m+1+2r$ | $m-r$ | $r+1$ |

Substitution into the transition rules gives three properties: each macro-step advances phase by one modulo $m+2$; positive depth decreases by at least one; and zero depth identifies the cycle state with that phase. Every depth lies between 0 and $m$. Therefore, after $m$ macro-steps, every state is on the relevant cycle, at its initial phase plus $m$.

In particular,

$$\{0,2\}U^m=\{2m,1\},\qquad \{2m,1\}V^m=\{2,2\}.$$

The second identity follows because both 1 and $2m$ have $V$-phase 1; their depths are 0 and $m$. After $m$ steps, both reach $C_V[m+1]=2$.

Thus $W=U^mV^m$ merges 0 with 2 in $4m$ letters. Combining this with B gives

$$\boxed{\tau(0)=4m=4k+8=4n/3.}$$

### D. Synchronization and an explicit reset word

The original synchronization proof uses $C_U$, of length $M=m+2$, and the macro $S=aU^m$. On cycle phases $i=0,\ldots,M-1$,

$$S(i)=\begin{cases}
M-2-i,&0\le i\le M-3,\\
M-1,&i=M-2\text{ or }M-1.
\end{cases}$$

Every state reaches $C_U$ after at most $m$ applications of $U$. For any distinct pair on this cycle, orient its directed gap as $d\in\{1,\ldots,M-1\}$ and rotate the first endpoint to $M-2$. If $d=1$, $S$ merges the pair. If $d\ge2$, the second endpoint is at $d-2$; applying $S$ gives $M-1$ and $M-d$, with gap $d-1$ after choosing the latter as the first endpoint. Repeating reduces the gap to one and merges the pair.

Since every pair can merge, the whole machine synchronizes: choose two distinct states in the current image, apply a word merging them, and repeat. A deterministic map cannot separate already equal images, so the number of distinct images decreases until one remains.

The later PTT construction makes a single reset word explicit. Composing the powers in C gives the complete action $J(q)=\delta(q,W)$:

$$J(q)=\begin{cases}
2,&q\in\{0,2,2m+1\},\\
q,&1\le q<2m,\ q\text{ odd},\\
2m+3-q,&4\le q\le2m,\ q\text{ even},\\
q-2m+3,&q\ge2m+2,\ q\text{ even},\\
4m+2-q,&q\ge2m+3,\ q\text{ odd}.
\end{cases}$$

Its image is $C_V\setminus\{0\}$, and every point of that image is fixed. Write $C_V=(c_0,\ldots,c_{m+1})$, with $c_0=0$ and $c_{m+1}=2$.

After $W$, the missing cycle point is $c_0$. Suppose that after $j$ additional $VW$ blocks the missing points are $c_0,\ldots,c_j$. The next rotation moves the missing block to $c_1,\ldots,c_{j+1}$. For $j<m$, both $c_0$ and $c_{m+1}$ are now present; $W$ merges them and fixes the others. The missing block becomes $c_0,\ldots,c_{j+1}$.

After $m$ blocks only $c_{m+1}=2$ remains. Hence

$$\mathcal R=W(VW)^m,\qquad |\mathcal R|=4m^2+6m.$$

### E. The two-arrow comparison

For the twelve-state example, let $L$ denote changing $b(7)$ to 5 and $R$ changing $b(10)$ to 4. The complete maps below are the same in all four combinations. Entries are ordered by starting state $0,1,\ldots,11$.

```text
(ba)^4: [8,6,1,4,0,2,2,0,4,1,2,0]
(ab)^4: [7,2,5,0,3,1,1,3,2,3,0,1]
```

The exact shortest distances from 0, minimized over companions, are respectively 16, 16, 16, and 15. The last case has the word `babababaabababb`, merging 0 with 2. These are finite graph computations. No claim about arbitrary arrow changes follows from this example.

## References and scope

[1] Marek Szykuła, [*Synchronizing Automata: Open Problems*](https://arxiv.org/abs/2608.24245), EPTCS 451 (2026), 33–47, §2.3 and Figure 3. The survey credits the family to Michalina Dżyga's 2018 master's thesis.

[2] Aidan Edward Lawson, *The Dżyga–Szykuła 4n/3 Compress-with-Another Series*, September 2026, §§2–6. Original manuscript and accompanying CWA-004 checker.

[3] Aidan Edward Lawson, *Proof-to-Theory: Uniform Corridor Bounds and Common Macro-Powers*, September 2026. The later progress certificate, phase/depth coordinates, common reset construction, and deformation results are used above.

[4] Machina Mathematica / Korea Superintelligence Labs, [*The compress-with-another threshold of the series $A_k$*](https://ideosphere.ai/papers/cwa-series), version 1. This earlier work supplies the all-parameter upper bound and corrected witness. Its version-one record leaves the general lower bound and all-parameter synchronization open. Those upper-bound and correction results are not claimed as first discoveries here.

The result concerns the specified Dżyga–Szykuła family, not the general Černý conjecture or Conjecture 6. Finite examples illustrate the result; the all-parameter lower bound uses the explicit certificate and its universal arithmetic inequalities.
