数理解析研究所講究録 1222 巻 2001 年 50-52

50
Irreducibility in equal length for finite semigroups
P\’al D\"OM\"OSI
Institute of Mathematics and Informatics, Debrecen University
Debrecen, Egyetem t\’er 1, H-4032, Hungary

e-mail:domosi@math.klte.huand

Masami ITO (伊藤 正美)

Faculty of Science, Kyoto Sangyo University
Kyoto 603, Japane-mail:ito@ksuvx0. kyoto-su.ac.jp

By the-known Krohn-Rhodes theorem (see, for example, [4]) the finite irreducible semigroups are exactly the finite simple groups and the subsemigroups of the monoid with tworight-zero elements. It is trivial that all finite cyclic simple groups are irreducible in equallength. Moreover, it is easy to see that all subsemigroups of the monoid with two right-zeroelements also have this property. Using the D\‘en\mbox{\boldmath $\varpi$}Hermann theorem [3], we can also showthatfinite non-commutative simple groups are irreducible in equal length. Therefore,
the finite irreducible semigroups are irreducible in equal length too. Z. Esik (see [1] and [2])gave adirect proof of this statement such that he did not use the Dines Hermann theorem.
$[5]$ , we give another direct, elementary proof. (We note that theUsing an idea of P.
only known proof of the D\’en\infty Hermam theorem uses the Feit-Thompson theorem.)$\mathrm{w}\mathrm{e}\mathrm{U}$au$\mathrm{P}\mathrm{g}$It is said that asemigroup divides asemigroup , written $S\preceq T$, iff $T$ has asuksemigroup having ahomomorphism onto . If $H$ is asubset of the semigroup $T$ and thesubsemigroup $T’$ generated by $H$ has ahomomorphism onto then we also say that
divides $T$ with respect to $H$ and we write $S\preceq_{H}T$.
Let $H$ be anonvoid subset of elements of the semigroup $T$ and consider asubsemigroup$T’$ ofgenerated by $H$. Consider ahomomorphism : $T’arrow S$ of $T’$ onto agiven semigroup. Put $S|^{\iota,H}’ T$ iff
for all $s\in S$. In addition, we put $S|^{H}T$ iff $S|^{n,H}T$
holds for some .
, we define the wreath product
Given two transformation semigroups $(X, S)$ and$( \mathrm{Y},T)\int(X,S)$ to be the transformation semigroup with set
and action semigroupwith action $(y,x).(f,s)=(y.f(x),x.s)$ .
to be if contains an identity element $1\in S$
Given asemigroup , we definewith $s1=1s=s$ for aU $s\in S$, otherwise we taketo be with new identity element 1adjoined. Thusis the minimal monoid containing as asubsemigroup.
with $s.s’=ss’$
For asemigroup , we consider the transformation semigroup$T$$s’\inS$$1.5=s,s\in
S$. If and are semigroups then we shall write $T \int S$ for
andfor all ,, we put $H_{1}=\{t|$. For every subset $H$ ofthe wreath product of, $(f, s)\in H:t=f(s’)\}$ and $H_{2}=\{ss\in S:\exists(f,s)\in H\}$ .
,necessarily
If for arbitrary semigroups $S,T$, and asubset $H$ of$S’$implies that eitherorthen it is said thatis irreducible.
Adirect consequence of the Krohn-Rhodes Theorem [4] is thestatement.
$T$

$S$

$S$

$S$

$T$

$S$

$\psi$$S$$\psi^{-1}(s)\cap H^{n}\neq\emptyset$$n$$(\mathrm{Y},T)$$\mathrm{Y}\mathrm{x}X$$T^{X}\mathrm{x}S$$S$$S^{\lambda}$

$S$

$S$

$S$

$S^{\lambda}$$S$$S^{\lambda}$$S$$(S^{\lambda},S)$

$S$

$s$

$T^{S^{\lambda}}\mathrm{x}S$$(T^{\lambda},T) \int(S^{\lambda},S)$$t\in T:\exists s’\in S^{\lambda}$$T^{S^{\lambda}}\mathrm{x}S$$S’\preceq_{H_{1}}T$$S’\preceq_{H}T^{S^{\lambda}}\cross S$$S’\preceq_{H_{2}}S$$\mathrm{n}\infty \mathrm{c}\mathrm{t}$Theorem 1. The finite irreducible semigroups are exactly the finite simple groups and thesubsemigroups of the monoid with two right-zero elements.

51
again and consider $H_{1}=\{t|t\in T:\exists s’\in S^{\lambda}$ , $(f,s)\in$
Let $H$ be asubset of$H$ : $t=f(s’)\}$ and $H_{2}=\{s |s \in S:\exists(f,s) \in H\}$ as before.
, and apositive integer ,If for arbitrary semigroups $S,T$, aauket $H$ of$S’|^{H_{1}}T$$S’|^{H_{2}}S$
necessarily implies that either
orthen it is said that $S’$ is$iMuc:ble$ in equal lengh. By this definition, asemigroup is irreducible if it is irreduciblein equal length.
The following statement is obvious.
$T^{S^{\lambda}}\mathrm{x}S$$T^{S^{\lambda}}\mathrm{x}S$$n$$S’|^{r\iota,H}T^{S^{\lambda}}\mathrm{x}S$

Proposition 2. The finite simple cyclic groups are$\dot{|}muc.\emptyset$

le in equal length.

Next we prove
Proposition 3. The subsemigroups of the finite monoid with two right-zero elements are
irreducible in equal lengffi.

Proof: Let $S=\{e,z_{1},z_{2}\}$ be the monoid with the identity and distinct right zeros. By Theorem 1, all subsemigroups of are irreducible. Prove that they are irreducible$e$$z_{1}$,$S$$z_{2}$in equal length.
Consider asemigroup $T$ with $S\preceq T$ and let $T’$ be asubsemigroup of $T$ having ahomomorphism: $T’arrow S$ onto . Consider an arbitrary subset $H$ of $T’$ having strings, $p_{2}\in H^{+}$ with. Take words
having$q_{0}=(\eta)^{|p_{1}||p_{2}|}$ ,. It is clear that $|qo|=|q_{1}|=|oe|$ , and, $\psi(q_{1})=z_{1}$ , $\psi(q_{2})=z_{2}$ . Obviously, $S|^{n,H}T$ withsimultaneously,
.
$T$
$H$
$S\preceq_{H}T$$S|^{H}T$
impliesThis shows that for every subset of ,. On the other hand, isirreducible. Clearly, then is irreducible in equal length. We omit the easy proof for theappropriate subsemigroups.
$S$$\psi$$\mathrm{V}(\mathrm{p}\mathrm{o})=e,\psi(p_{1})=z_{1},\psi(p_{2})=z_{2}$$p_{0},p_{1}$$\mathrm{q}\mathrm{o},\mathrm{q}\mathrm{i},\mathrm{Q}2\in T^{\prime+}$$q_{1}=(p_{1})^{|\mathrm{P}\mathrm{o}||\mathrm{p}_{2}|},\infty=(\ )^{\mathrm{I}\mathrm{r}\mathrm{o}||p_{2}|}$$\psi(q\mathrm{o})=e$$n=\mathrm{b}||p_{1}|[\infty|$

$S$

$S$

Next we prove
Theorem 4.

{$gP(1)\cdots$ $gP(n)$ :

Let

$G$

$=$

$\{g_{1}, \ldots,g_{n}\}$be$=$(finite) ordergroup.
Put$G$, }. If is simple and noncommutative$P_{G}$$n$$a$

is a permutation over {1,then therea positive integer $m$ with $7=G$ .
, we have $|P_{G}^{t+1}|\geq|rP_{G}^{t}|=|P_{G}^{t}|$ ,Proof: First, for every positive integer andand the group is finite. Therefore, this growing should be finished, i.e., there exists an. Let $m\geq t_{0}$ be such that $e\in P_{G}^{m}$ , wheresuch that $t\geq t_{0}$ implies
denotes the identity element of the group G. (Of course, for every $r\in P_{G}$ ,.
Thus, for example, $m$ may be an arbitrary positive even number with $m\geq t_{0}.$ ) Thenand. But they have the same number of elements, thus
, therefore,is asubgroup. Prove that for arbitrary $r\in G$ ,.
, $’\in G$ . Then, using the fact that forIndeed, let)every , $g’\in G$ ,: $garrow g’g,g\in G$ and , : $garrow gf’,g\in G$ aremappings, forevery $i=1$ , , $m$ , $\{rg_{P\dot{.}(1)}r^{-1}, \ldots,rg_{P_{}(n)}r^{-1}\}=G$. In other words, for every $:=1$ , , $m$ ,$rg_{P.(1)}.r^{-1}\ldots$ $rg_{P.(’*)}.r^{-1}\in Pg$ , leading to $rP_{G}^{m}r^{-1}=P_{G}^{n}$ , i.e.,. Therefore,
every element of normalizes 7, and thus 7is normal subgroup in $G$ . Since $G$ is non$f_{nm-2}\neq$
conmutative, there arewith
But then we get$g_{nm-2}’,$, $g_{nm-2}’\in G$ . Thus, of course,. Therefore, by the simplicity
of , $P_{G}^{m}=G$ necessarily holds$P$$\ldots$$n\}$$\dot{\varpi}sb$

$t$

$r$

$\in P_{G}$$|P_{G}^{t}|=|P_{G}^{t_{\mathrm{O}}}|$$t_{0}$$e$$\mathrm{r}\mathrm{r}^{-1}=e$$P_{G}^{2m}\subseteq eP_{G}^{m}=P_{G}^{m}$$P_{G}^{m}P_{G}^{m}=P_{G}^{2m}$$P_{G}^{m}P_{G}^{m}=P_{G}^{m}$$rP_{G^{\hslash}}=\mathrm{P}\mathrm{g}r$$P_{G}^{m}$$gP_{1}(1)\ldots$ $gP_{1}(n)\ldots$ $gP_{\mathrm{m}}(1)\ldots$ $g_{P_{m}}(|*)\in P_{G}^{m}$$\mathrm{y}$$\mathrm{o}\mathrm{n}\triangleright \mathrm{t}\infty \mathrm{c}$$\varphi_{g’}’$$\varphi_{g}’$$\mathrm{n}\mathrm{e}$$\ldots$$\ldots$$r\dot{P}_{G}^{m}=P_{G}^{m}r$$G$$g_{\dot{l}},g_{\mathrm{j}}\in G$$g_{i}g_{i}g_{1}’\ldots$$G$$j_{1},\ldots$$g_{\dot{l}}g_{\dot{f}}\neq g_{\mathrm{j}}g\ldots$$|P_{G}^{m}|\geq 2$$g.\cdot g_{\mathrm{j}}g_{1}’\ldots$52
Let be agroup. An element $g\in G$ is called comrr utator if $g=aba^{-1}b^{-1}$ for someelements , $b\in G$ . The smalest subgroup that contains all commutators of is called thecommutator subgroup or derived subgroup of , and is denoted by $G’$ . It is well-h ove that$G=G’$ wheneveris simple and non-commutative. Thus we can also get our previous
result as adirect consequence of the following well-known theorem.
orderTheorem) Let $G=\{g_{1}, \ldots,g_{n}\}$ be
Theorem 5. ($G’$ its
commutator subgroup. Put $P_{G}=\{gP(1)\cdots$
non-commutative group and denote$P$,: is a permutation over 1,}. There this a $g\in G$ with $P_{G}=G’g$ . Thus
$P_{G}=G$ , whenever $G=G’$ .
$G$

$G$

$a$

$G$

$G$

$a$

$\mathrm{D}6\mathrm{n}\varpi \mathrm{H}\mathrm{e}\mathrm{r}$$(fin\cdot te)$

$n$

$\{$

$g_{P(n)}$$\ldots$$n\}$Now we show the following
Theorem 6. The non-commutative finite simple groups are $imduc\dot{|}ble$ in equal length.
Suppose that $S=\{g_{1}, \ldots,g_{n}\}$ is anon-cyclic simple group. Consider asemigroup: $T’arrow$with $S\preceq T$ and let $T’$ be asubsemigroup of having ahomomorphism
onto . Consider an arbitrary subset $H$ of $T’$ having strings , $\ldots,r_{n}\in H^{+}$ with, $:\in\{1, \ldots,n\}$ . Then, using Theorem 4., there exists apositive integer $m$over 1, , , withsuch that for every $s\in S$ there are permutations $P.,1$ , ,,. But then, of$=g_{P..(1)}1\ldots$ $g_{P.,(n)}1\ldots$) $=\psi(r_{P.,(1)}1\cdots r_{P_{1}(’\iota)}.,\cdots r_{P.,(1)}" \cdots r_{P_{n}(n)}.,)=s$. Consequently, there,
apositive integer $t(=m(|r_{1}|+\ldots+|r_{n}|))$ such that for every $s\in S$, there is at-length$p\inH^{+}$ with. Thus we have $S|^{t,H}$ . Therefore, for every subset $H$ of ,word$S\preceq_{H}T$ implies $S|^{H}T$. On the other hand, by Theorem 1,is irreducible. It is easy toshow that in this case is irreducible in equal length too. This ends the proof.
$T$

$T$

$\psi$$S$$S$$r_{1}$$\psi(r\dot{.})=g.\cdot$$P_{l,m}$$\ldots$$\infty \mathrm{u}\mathrm{r}\mathrm{s}\mathrm{e}$$g_{P.,,(1)}n\ldots$ $g_{P.,,(n)}\hslash$$\delta$$\{$$\ldots$$n\}$$\psi(r_{P.,(1)}\cdots r_{P}1\cdot.1(’\iota)\cdots$$r_{P_{n}(1)}.$ $\cdots$ $r_{P_{\mathrm{m}}(n)}.,$$\mathrm{n}\cdot 8\mathrm{t}\mathrm{s}$$\psi(p)=\epsilon$

$T$

$T$

$S$

$S$

, [2].
Thus we received anew proof of the following result of Z.
Theorem 7. The irreducible semigroups are $iMu\dot{\alpha}bk$ in equal length too.
$\acute{\mathrm{E}}\mathrm{s}\underline{\mathrm{i}\mathrm{k}}[1]$References[1] Z.

ffi.A An extension of the Krohn-Rhodes decomposition of automab$\dot{l}n:$Pmc.

IMYC 1989, SmoUmice, LNCS, 381, Springer, 1989, 66-71.

[2] Z. ffi.k, Results on homomorphic realzation of automata by1991, 229-249.

$\alpha 0$-products, TCS, 87,, On the product of all elements in afinite group, Ann. of[3] J. Dines and P.
Discrete Math., 15, 1982, 107-111.
$\mathrm{H}\ovalbox{\tt\small REJECT}$[4] K. B. Krohn, J. L. Rhodes and B. R. Tilson, The prime decomposition theorem of
the algebraic theory of machines, in: M. Arbib, ed., Algebraic Theory of Machines,Languages and $Sem\dot{.g}mups$, Academic Press, New York, 1968.
[5] P. P. Pilfy, On generating systems of non-commutative finite simple groups, personalcommunication, 1989