Sequential machines realized by group representations (Q807027): Difference between revisions

The Krohn-Rhodes theorem characterizes finite automata in terms of permutation machines and reset-machines. The author suggests to replace the finite permutation group G corresponding to a permutation machine by a faithful low dimensional ordinary matrix representation of G. In a second stage he then reduces the constants to get a faithful low dimensional representation of G over a small finite field. In the introduction the author writes: ``The major new result given in the present paper is that computation over a finite field Z modulo p \((Z_ p)\) will always suffice for these methods. These new results yield a dramatic increase in the flexibility of the method as well as giving very tight control over the realizations.'' This sounds like a sensation but a closer look at this paper shows that nothing is new! Even worse, classical results (resp. methods) are reproved (resp. reformulated) in a complicated way. As an example, investigating ``the worst case'' M. Conner needs about five (!) pages to reprove the well-known result that the symmetric group \(S_ n\) (n\(\geq 3)\) has a faithful linear representation over GF(3) of degree n-1. In addition, it is well-known see e.g. \textit{G. D. James} [The representation theory of the symmetric groups, Berlin-Heidelberg-New York (1978; Zbl 0393.20009)] how to improve this result: For \(n\geq 3\), \(S_ n\) has a faithful linear representation over GF(2) of degree d, where \(d=n-2\) if n is even and \(d=n-1\) if n is odd. Proof: \(S_ n\) acts linearly on \(GF(2)^ n\) by permuting the standard basis: \(\pi e_ i:=e_{\pi (i)}\). The line \(L_ n\) generated by \(e_ 1+...+e_ n\) is an \(S_ n\)-submodule as well as its ``orthogonal complement'' \(M_ n\), freely generated by \(e_ 1+e_ 2,...,e_ 1+e_ n\). Obviously, \(M_ n\) is faithful for \(n\geq 3\). Now let n be even. Then \((e_ 1+e_ 2)+...+(e_ 1+e_ n)=e_ 1+...+e_ n\), hence \(L_ n\) is a submodule of \(M_ n\), and \(M_ n/L_ n\) is a faithful \(S_ n\)-module of dimension n-2. Done. After such a short proof, the author would have had enough space to describe the effect of his suggestion to automata theory. I could not find any serious statement in this direction.