Finite transformation monoids

Minimum faithful transformation degree

A marked word kernel is an exact test for whether a compactly generated monoid has a faithful realization on fewer points. It gives a PSPACE upper bound for transformation monoids; the group restriction has a polynomial-size coset-action certificate.

FPRD-TM-D01 · definition

Marked presentations and word kernels

Let $T_n$ be the monoid of total functions on $\{1,\ldots,n\}$ . Two supplied generators define

$\eta_{\mathbf s}:\{a,b\}^*\to T_n,\qquad \eta_{\mathbf s}(a)=s_1,\quad \eta_{\mathbf s}(b)=s_2.$

Its image is $\langle s_1,s_2\rangle$ . Its kernel records every identity between words in the marked generators:

$u\equiv_{\mathbf s}v\quad\Longleftrightarrow\quad \eta_{\mathbf s}(u)=\eta_{\mathbf s}(v).$

FPRD-TM-L01 · lemma

An exact criterion for a smaller realization

Lemma. The marked monoid generated by $s_1,s_2$ embeds in $T_m$ exactly when there are $t_1,t_2\in T_m$ satisfying

$\ker(\eta_{\mathbf s})=\ker(\eta_{\mathbf t}).$

Proof. An embedding sends the marked generators to a pair with the same word equalities. Conversely, equal kernels make $\eta_{\mathbf s}(w)\longmapsto \eta_{\mathbf t}(w)$ well-defined and injective; concatenation makes it a monoid homomorphism. ∎

The main statement uses identity-preserving embeddings. A non-unital convention can instead track the idempotent image of the identity and work in its local monoid.

FPRD-TM-T01 · theorem

The transformation problem is in PSPACE

For a candidate target pair, follow a word simultaneously in the source and target. There are at most

$N=n^n m^m$

paired transformation values. Every reachable pair therefore has a representative of length below $N$ .

Theorem. Given two transformations on $n$ points, deciding whether their generated monoid embeds in some $T_m$ with $m<n$ belongs to PSPACE.

Proof. If the kernels differ, choose words $u,v$ witnessing equality on one side and inequality on the other. Replace each word separately by a shortest representative of its reachable paired value. Both replacement words have length below $N$ , and they retain the same two paired values, so they still witness the kernel difference. Guess both words symbol by symbol while storing only four current transformations and two logarithmic counters. This places kernel inequality in NPSPACE. Since NPSPACE = PSPACE and PSPACE is closed under complement, kernel equality is in PSPACE. Enumerate each smaller target pair and reuse the same workspace. The kernel lemma gives soundness and completeness. ∎

This proof bounds space, not time. It supplies no PSPACE-hardness result.

FPRD-TM-T02 · theorem

For groups, transformation degree is permutation degree

Theorem. For every finite group $G$ ,

$\min\{m:G\hookrightarrow T_m\}=\min\{m:G\hookrightarrow S_m\}=\mu(G).$

In a unital embedding, every image element has a two-sided inverse and is therefore a permutation. For a non-unital embedding, let $e$ be the image of the identity; restriction to $\operatorname{im}(e)$ gives a faithful permutation action of no larger degree. The other inequality follows from $S_m\subseteq T_m$ .

FPRD-TM-T03 · theorem

The group problem is in NP

Every finite $G$ -set is a disjoint union of coset actions

$G/H_1\;\dot\cup\;\cdots\;\dot\cup\;G/H_r.$

Its degree and kernel are

$\sum_i[G:H_i]\qquad\text{and}\qquad \bigcap_i\operatorname{Core}_G(H_i).$

A certificate lists subgroups whose total index is below $n$ and whose cores intersect trivially. Fewer than $n$ subgroups are needed, and each has a polynomial-size generating set. Standard permutation-group algorithms verify membership, indices, the coset actions, and faithfulness in polynomial time.

This is the standard minimum-faithful-action certificate. Kantor and Luks's quotient-group algorithms supply the required polynomial-time permutation-group operations; the general NP upper bound is also stated explicitly in the current survey by Levet, Srivastava, and Thakkar. Their faster NC/RNC algorithms require the additional Fitting-free hypothesis.

Independent finite audit

A separate checker exhausts 12,409 small source/target marked pairs, verifies the shortest-representative bound in every case, and compares transformation and permutation targets in 76 small group-degree tests. It also checks a non-unital idempotent-image example. These finite checks corroborate the mechanisms above; they are not proofs of the unbounded complexity statements.

Read the audit output or inspect the checker.

Scope and sources

The exact complexity of both general problems remains open in this analysis.
Two generators do not imply that the generated monoid has polynomial size.
The newer Fitting-free algorithms do not cover every two-generated group.

Problem source. Transformation monoid minimisation, contributed by Ismaël Jecker to Automata Exchange.

Kantor and Luks, Computing in Quotient Groups, STOC 1990, pp. 524–534, supplies the permutation-group algorithmic foundation used by the NP certificate. For current neighboring results, see Levet, Srivastava, and Thakkar, Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups (arXiv:2501.16039v4, 2026), which records the general NP boundary and stronger algorithms for Fitting-free groups. Margolis and Steinberg's On the Minimal Faithful Degree of Rhodes Semisimple Semigroups, Journal of Algebra 633 (2023), 788–813, arXiv:2302.06539, concerns partial-transformation degree for a substantial semigroup class; it does not decide the compactly generated total-transformation problem studied here.