Irreducibility of extremal synchronizing automata

Let A=(Q,Σ,δ)\mathcal{A}=(Q,\Sigma,\delta) be a synchronizing automaton with n=Qn=|Q|. Its rank is the cardinality of the image of the state set under a word, and it is extremal if its shortest reset word has length exactly (n1)2(n-1)^2. An automaton is irreducible when it has no nontrivial invariant subspaces in the representation used in the paper. Conjecture on extremal automata. Every extremal synchronizing automaton is irreducible.

The conjecture would extend the known relationship between extremal synchronizing automata and irreducibility beyond the examples currently available. The source notes that every known extremal automaton is irreducible, but does not establish the assertion in general.

Sources & referencesView supporting material

Primary source

Riccardo Venturi, “Simplicity and irreducibility in circular automata”, arXiv:2511.16611 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.