On basic groups for the set of functions over a finite domain
Arto K. Salomaa · Annales Academiae Scientiarum Fennicae Series A I Mathematica · 1964
On basie groups for the set of tunctions over a finite ilomain l.Results.Let Go be the set of functions whose variables, finite in number, ra,nge over a fixed finite set Ir/:{f ,2,...,n},n}_2.and whose values are elements of .l[.If $ c @, we denote by I the closure of $ under composition.$ is said to be comgttete if I : G,.r) Every complete set contains a function satisfying slrytecki, cond,itions, i.e. depending essentially on at least two variables and assuming all z values.we say that a subset $ of G" is a basic set for g, if g is not complete but the addition to S of any function satisfying slupecki con- ditions yields a complete set.rf a basic set is a group with respect to com- position it is termed a basic group for §... rt, is shown in [], pp.72-76) that all l-place functions belonging to o, form a basic set 3r for §., provided n 2 B. This result has been strengthened to concern various subsets of d, which are closed under composition.rt is shown in [t] that the subset of 8r consisting of all I-place functions other than permutations is a basic set for @,, provide d n 2 B.on the other hand, it is shou.n in [2] that the symmetric group of degree n is a basic group for G,.2) tr'urthermore, according to [3], the alternaiing group of degree n is a basic group for G,.(Obviously, the latter result implies the former.)These results are valid for all values of n, 2 5. Counter- examples presented in [2] show that they are not valid for n : 2. 1, 4.rn this pa,per, we shall study the problem whether it is still possible to reduce basic groups, i.e. whether the alternating group can be replaced by a smaller group of degree n, provided n 2 5. rn proofs of completeness criteria for subsets of Uo, the essential fact concerning groups is the degree of transitivity.Therefore, it is natural to ask whether the alternating group can be replaced by an arbitrary group of degree n wilh some lo.vi,er limita- tion on the degree of transitivity.1) For a detailed discussion, cf.[r, pp.56-59].Throughout this paper, ', means the number of elements in the set N.2) rn fact, a slight modification in the proof of the theorem in [2] rvill yield this result.