format: text

text:
# On the polycirculant conjecture

## 1 Introduction

A permutation group $`G`$ on a $`n`$-element set $`V`$ is called regular, if its every stabilizer (a subgroup that fixes some element $`vV`$) is trivial. Every permutation of the regular group can be decomposed into cycles of the same length.

A permutation group, containing a regular subgroup, is called semiregular.

Let $`G`$ be a permutation group on a $`n`$-element set $`V`$, $`V^k`$ be Cartesian power of $`V`$ and $`V^{(k)}V^k`$ be the non-diagonal part of $`V^k`$, i.e. every $`k`$-tuple of $`V^{(k)}`$ has $`k`$ different values of its coordinates. The action of $`G`$ on $`V`$ forms the partition of $`V^{(k)}`$ on classes of $`k`$-tuples related with $`G`$. This partition is called the system of $`k`$-orbits of $`G`$ on $`V^{(k)}`$ and we write it as $`Orb_k(G)`$. If $`v_1\mathrm{}v_kV^{(k)}`$, then $`Gv_1\mathrm{}v_k\{gv_1\mathrm{}gv_k:gG\}`$ is a $`k`$-orbit from $`Orb_k(G)`$.

For considered tasks it is of interest a maximal subgroup of $`Aut(Orb_k(G))`$ that maintains $`k`$-orbits from $`Orb_k(G)`$. We shall denote this subgroup as $`aut(Orb_k(G))`$. Thus $`aut(Orb_k(G))_{X_kOrb_k(G)}Aut(X_k)`$ and $`Gaut(Orb_k(G))`$.

###### Definition 1

We call a permutation group $`G`$ a *$`k`$-defined* group, if $`G=aut(Orb_k(G))`$.

There is the obvious property of a $`k`$-defined group:

###### Proposition 2

If a group $`G`$ is $`k`$-defined, then it is $`(k+1)`$-defined.

Proof: If a group $`G`$ is $`k`$-defined, then, on the one hand, $`aut(Orb_{k+1}(G))<aut(Orb_k(G))=G`$ and, on the other hand, $`G<aut(Orb_{k+1}(G)`$. $`\mathrm{}`$

The $`k`$-defined group is called $`k`$-closed if it is not $`(k1)`$-defined.

P. Cameron  has described the conjecture of M. Klin, that every $`2`$-closed transitive group is semiregular, and the similar polycirculant conjecture of D. Maru$`\stackrel{˘}{\mathrm{s}}`$i$`\stackrel{˘}{\mathrm{c}}`$, that every vertex-transitive finite graph has a regular automorphism.

We shall prove these conjectures in the next reformulation:

###### Definition 3

We shall emphasize in the conventional definition of primitivity and imprimitivity of permutation groups the case of cyclic group of a prime order. We shall say that these groups are *trivial primitive* and *trivial imprimitive*. The reason of such consideration will be clear below.

###### Theorem 4

The $`2`$-closure of a transitive, imprimitive permutation group contains a regular element.

###### Lemma 5

A primitive permutation group contains a transitive, imprimitive subgroup.

In order to prove these statements we shall study symmetry properties of $`k`$-orbits.111The objects, that generalize symmetry properties of $`k`$-orbits, were applied by author for the polynomial solution of graph isomorphism problem. The part of such investigations is used in http://arXiv.org/find/math/1/AND+au:+Golubchik\_Aleksandr+ti:+AND+polynomial+algorithm/0/1/0/2002/0/1

## 2 $`k`$-Orbits

A $`k`$-orbit $`X_k`$ is a set of $`k`$-tuples with property $`X_k=Aut(X_k)\alpha _k`$ for a $`k`$-tuple $`\alpha _kX_k`$. Such $`k`$-sets we shall call *automorphic* $`k`$-sets.

All, what is written below, can become easier for understanding, if to represent a $`k`$-orbit as a matrix, whose lines are $`k`$-tuples and columns are values of coordinates of $`k`$-tuples. A $`k`$-orbit can be represented by various matrices that differ by lines permutation. Various orders of lines in matrices demonstrate various symmetry properties of $`k`$-orbit. For example $`3`$-orbit of symmetric group $`S_3`$ we can represent as

$$\begin{array}{ccc}\begin{array}{ccc}& & \\ 1& 2& 3\\ 2& 3& 1\\ 3& 1& 2\\ & & \\ 1& 3& 2\\ 3& 2& 1\\ 2& 1& 3\end{array}\hfill & \text{ or }& \hfill \begin{array}{c}& & \multicolumn{-1}{c}{}\\ 1& 2& 3\\ 2& 1& 3\\ & & \multicolumn{-1}{c}{}\\ 1& 3& 2\\ 3& 1& 2\\ & & \multicolumn{-1}{c}{}\\ 2& 3& 1\\ 3& 2& 1\end{array}.\end{array}$$

In order to indicate number of $`k`$-tuples in a $`k`$-orbit $`X_k`$ of power $`l`$ we shall call it $`(l,k)`$-orbit or write as $`X_{lk}`$.

$`k`$-Orbits have the next general number property:

###### Proposition 6

Let $`X_k`$ be a $`k`$-orbit and $`lk`$, then all $`l`$-tuples with the same coordinates $`i_1,\mathrm{}i_l[1,k]`$ form a homogeneous multiset (i.e. all $`l`$-tuples in this multiset have the same multiplicity).

Proof: Let two $`k`$-subsets $`Y_k(u_1,u_2,\mathrm{},u_l),Z_k(v_1,v_2,\mathrm{},v_l)X_k`$ consist of all $`k`$-tuples, that have their $`l`$ coordinates $`i_1,\mathrm{}i_l`$ equal to $`u_1,u_2,\mathrm{},u_l`$ and $`v_1,v_2,\mathrm{},v_l`$ correspondingly. Let $`gAut(X_k)`$ be such permutation that $`v_1\mathrm{}v_l=gu_1\mathrm{}gu_l`$, then $`Z_k=gY_k`$. $`\mathrm{}`$

Following constructions simplify the study of $`k`$-orbits. We call a $`k`$-orbit as a *cyclic $`k`$-orbit* or simply a *$`k`$-cycle*, if it is generated by single permutation. A $`k`$-cycle, that consists of $`l`$ $`k`$-tuples, we write as $`(l,k)`$-cycle. The order of a generating $`k`$-cycle permutation can differ from the number of $`k`$-tuples in the $`k`$-cycle. The structure of $`k`$-cycles is enough simple and can be represented with four structure elements:

###### Example 7

$$\begin{array}{cccc}& & & \\ 1& 2& 3& 4\\ 2& 1& 4& 3\end{array},\begin{array}{cccc}& & & \\ 1& 2& 3& 4\\ 2& 1& 3& 4\end{array},\begin{array}{cccc}& & & \\ 1& 2& 3& 4\\ 2& 1& 5& 6\end{array},\begin{array}{cccccc}& & & & & \\ 1& 2& 3& 4& 5& 6\\ 2& 3& 4& 1& 6& 5\\ 3& 4& 1& 2& 5& 6\\ 4& 1& 2& 3& 6& 5\end{array}.$$

The first example shows the $`(2,4)`$-cycle that is a *concatenation* of two $`(2,2)`$-cycles. Such $`(k,k)`$-cycle, that is a $`k`$-orbit of a cycle of length $`k`$, we shall call a *$`k`$-rcycle*. This term is an abbreviation from a “right cycle” and indicates on invariance of such $`(k,k)`$-cycle relative to cyclic permutation of not only its $`k`$-tuples but also the coordinates of $`k`$-tuples, or on invariance of the $`(k,k)`$-cycle relative to not only the left but also the right action of permutation (s. below).

The second is the $`(2,4)`$-cycle with fix-points. It is represented by the concatenation of the $`2`$-rcycle and the trivial $`(2,2)`$-multiorbit, consisting of the single $`2`$-tuple. Such $`k`$-multiorbit we shall call a *$`k`$-multituple* or $`(l,k)`$-multituple.

The third example is the concatenation of the $`2`$-rcycle and a $`2`$-orbit that consists of two $`2`$-tuples with not intersected values of coordinates. This kind of $`(l,k)`$-orbit we shall call *$`S_l^k`$-orbit*. It designates that this $`(l,k)`$-orbit consists of $`lk`$ elements of $`V`$ and its automorphism group is subdirectproduct of symmetric groups $`S_l(B_i)`$, where $`B_iV`$, $`i[1,k]`$, $`|B_i|=l`$ and $`B_iB_j=\mathrm{}`$ for $`ij`$. From this definition follows that any $`(l,1)`$-orbit ($`l`$-element set) is $`S_l^1`$-orbit.

The fourth example shows the possible structure of a $`k`$-cycle whose length is not prime. It is seen that the fourth case can be represented through first three cases. So these three cases are fundamental for constructing of any $`k`$-orbit of any finite group.

One of our tasks is the study of a permutation action on $`k`$-orbits. Indeed, there exist different possibilities of the permutation action on $`k`$-orbits, which are arisen from their different symmetry properties.

We shall start with consideration of permutation actions on a $`n`$-orbit $`X_n`$ of a group $`G`$ of the degree $`n`$.

### 2.1 The actions of permutations on $`n`$-sets

A $`n`$-orbit $`X_n`$ of a group $`G`$ is a set of all $`n`$-tuples, any pair of which defines a permutation from $`G`$. So we can represent any $`n`$-tuple $`\alpha _n=u_1\mathrm{}u_n`$ as a permutation

$$g_{\alpha _n}=\left(\begin{array}{ccc}v_1& \mathrm{}& v_n\\ u_1& \mathrm{}& u_n\end{array}\right),$$

where $`n`$-tuple $`v_1\mathrm{}v_n`$ is related to the unit of $`G`$ and will be called as the *initial* $`n`$-tuple. Of course, any $`n`$-tuple from $`X_n`$ can be chosen as the initial. The property of the initial $`n`$-tuple is the equality of number value to order value of each its coordinate. Here is accepted that sets of number values and order values of coordinates are equal and for ordering of coordinates it is determinate (any time if it is necessary) certain linear order on this set. The next example shows two different orders of coordinates of the same $`2`$-orbit:

$$\begin{array}{ccc}\begin{array}{cc}& \\ 1& 2\\ & \\ 1& 2\\ 2& 1\end{array},\hfill & & \hfill \begin{array}{cc}& \\ 2& 1\\ & \\ 1& 2\\ 2& 1\end{array}.\end{array}$$

In first case the initial $`2`$-tuple is $`12`$, in the second it is $`21`$.

Further we shall take the next rule for permutation multiplication:

$$\left(\begin{array}{ccc}v_1& \mathrm{}& v_n\\ u_1& \mathrm{}& u_n\end{array}\right)\left(\begin{array}{ccc}v_1& \mathrm{}& v_n\\ w_1& \mathrm{}& w_n\end{array}\right)=\left(\begin{array}{ccc}w_1& \mathrm{}& w_n\\ x_1& \mathrm{}& x_n\end{array}\right)\left(\begin{array}{ccc}v_1& \mathrm{}& v_n\\ w_1& \mathrm{}& w_n\end{array}\right).$$

From this rule follows that the left action of the permutation

$$\left(\begin{array}{ccc}v_1& \mathrm{}& v_n\\ u_1& \mathrm{}& u_n\end{array}\right)$$

on the $`n`$-tuple $`\alpha _n=w_1\mathrm{}w_n`$ gives the $`n`$-tuple $`\beta _n=x_1\mathrm{}x_n`$ that can be considered as:

1. the changing of (number) values of coordinates of the $`n`$-tuple $`\alpha _n`$;
2. the mapping of $`n`$-tuple $`\alpha _n`$ coordinate-wise on a $`n`$-tuple $`\beta _n`$.

The right action of the permutation

$$\left(\begin{array}{ccc}v_1& \mathrm{}& v_n\\ w_1& \mathrm{}& w_n\end{array}\right)$$

on the $`n`$-tuple $`\alpha _n=u_1\mathrm{}u_n`$ gives the $`n`$-tuple $`\beta _n=x_1\mathrm{}x_n`$ that can be interpreted as:

1. the permutation of coordinates of the $`n`$-tuple $`\alpha _n`$;
2. the mapping of $`n`$-tuple $`\alpha _n`$ coordinate-wise on a $`n`$-tuple $`\beta _n`$.

We shall choose every time such interpretation of permutation action that will be more suitable.

If a $`n`$-orbit $`X_n`$ contains a $`n`$-tuple $`\alpha _n=v_1\mathrm{}v_n`$, then $`X_n=\{gv_1\mathrm{}gv_n:gG\}`$ and $`|X_n|=|G|`$. Here we have used the first method of permutation action on $`n`$-tuple, namely: a permutation $`g`$ changes values of coordinates of $`\alpha _n`$ or acts on the permutation $`g_{\alpha _n}`$ from left ($`gg_{\alpha _n}`$). We shall say also that a permutation $`g`$ acts from left on the $`n`$-tuple $`\alpha _n`$ and write this action as $`g\alpha _n`$.

The second method gives $`X_n=\{v_{g1}\mathrm{}v_{gn}:gG\}`$. It is an action of a permutation $`g`$ on the order of coordinates of $`n`$-tuple $`\alpha _n`$ or the action $`g_{\alpha _n}g`$ of $`g`$ on $`g_{\alpha _n}`$ from right. We shall say in this case that $`g`$ acts on the $`n`$-tuple $`\alpha _n`$ from right and write this action as $`\alpha _ng`$.

##### $`n`$-Orbits of left, right cosets of a subgroup.

Let $`A`$ be a subgroup of $`G`$, $`Y_n`$ be a $`n`$-orbit of $`A`$ and $`gG`$, then $`gY_n`$ is a subset of $`X_n`$ that represents permutations from a left coset of $`A`$ in $`G`$ and a subset $`Y_ng`$ represents permutations from a right coset of $`A`$ in $`G`$.

###### Definition 8

For convenience we shall write the sets of left $`G\backslash A`$ and right $`G/A`$ cosets of $`A`$ in $`G`$ as $`GA\{gA:gG\}`$ and $`AG\{Ag:gG\}`$.

The defined notation can be easily distinguished from the group multiplication, because the product of a group with its subgroup is always trivial. The same reasoning will be used in the like formulas by the action of a group on $`k`$-orbits.

Corresponding to this remark we write $`GY_n=\{gY_n:gG\}`$, $`Y_nG=\{Y_ng:gG\}`$, $`AX_n=\{A\alpha _n:\alpha _nX_n\}`$ and $`X_nA=\{\alpha _nA:\alpha _nX_n\}`$.

From this definition and notions of left and right cosets of a subgroup we obtain:

###### Lemma 9

Let $`n`$-orbit $`Y_n`$ of a subgroup $`A<G`$ contains initial $`n`$-tuple, then partitions of $`X_n`$ on $`n`$-subsets of left, right cosets of $`A`$ in $`G`$ are $`L_n=GY_n=X_nA`$ and $`R_n=Y_nG=AX_n`$.

Let $`Y_n`$ be a $`n`$-orbit of a subgroup $`A`$ of a group $`G`$ and $`gG`$.

###### Lemma 10

The $`n`$-subset $`Y_ng`$ is also a $`n`$-orbit of the subgroup $`A`$.

Proof: The right action of a permutation on a $`n`$-orbit changes the order of coordinates of $`n`$-tuples. The permutation that is defined by any pair of $`n`$-tuples does not depend on order of coordinates, hence every permutation that is defined by any pair of $`n`$-tuples from $`Y_ng`$ belongs to $`A`$. $`\mathrm{}`$

###### Lemma 11

The $`n`$-subset $`gY_n`$ is a $`n`$-orbit of the conjugate to $`A`$ subgroup $`B=gAg^1`$.

Proof: The $`n`$-subsets $`gY_n`$ and $`gY_ng^1`$ define, as in lemma 10, the same sets of permutations from $`G`$. But the set of $`n`$-tuples $`gY_ng^1`$ is by definition equivalent to the set of permutations $`B=gAg^1`$. $`\mathrm{}`$

###### Proposition 12

$`n`$-Subsets of left and right cosets of a subgroup $`A<G`$ are connected with elements of $`G`$.

Proof: Let $`Y_n`$ be a $`n`$-orbit of $`A`$, $`Y_n^{}`$ be the $`n`$-subset of a left coset of $`A`$ and $`Y_n^{\prime \prime }`$ be the $`n`$-subset of a right coset of $`A`$, then there exist permutations $`g,fG`$ so that $`Y_n^{}=gY_n`$ and $`Y_n^{\prime \prime }=Y_nf`$. Hence $`Y_n^{}=gY_n^{\prime \prime }f^1`$. $`\mathrm{}`$

We shall say further “$`n`$-orbit of coset” instead of “$`n`$-subset of coset”, in order to show that this $`n`$-subset is a $`n`$-orbit. It will be referred also to a $`k`$-subset, if it is a $`k`$-orbit.

###### Proposition 13

Let $`H`$ be a normal subgroup of $`G`$, then sets of $`n`$-orbits of left and right cosets of $`H`$ are equal and if to choose an arbitrary $`n`$-tuple from $`n`$-orbit $`Y_n`$ of an arbitrary coset of $`H`$ as the initial, then $`Y_n=gY_ng^1`$ for any permutation $`gG`$.

Proof: The sets of $`n`$-orbits of left and right cosets of $`H`$ are equal, because the sets of left and right cosets of $`H`$ are equal.

$`Y_n=gY_ng^1`$ for every permutation $`gG`$, because the choice of the initial $`n`$-tuple determines an equivalence between $`Y_n`$ and $`H`$ relative to the defined above action of $`G`$ on its $`n`$-orbit. $`\mathrm{}`$

###### Proposition 14

Let $`A`$ be a subgroup of a group $`G`$, $`Y_n`$ be a $`n`$-orbit of $`A`$ and $`Y_n^{}`$, $`Y_n^{\prime \prime }`$ be $`n`$-orbits of left and right cosets of $`A`$ correspondingly. Let $`Y_n^{}=Y_n^{\prime \prime }Y_n`$, then $`A`$ has non-trivial normalizer $`N_G(A)`$.

Proof: There exist permutations $`g,fGA`$ so that $`Y_n^{}=gY_n=Y_nf=Y_n^{\prime \prime }`$. From this equality and lemma 10 follows that $`gY_ng^1`$ is a $`n`$-orbit of $`A`$. As $`Y_n`$ contains the initial $`n`$-tuple, then $`gY_ng^1Y_n\mathrm{}`$ and hence $`gY_ng^1=Y_n`$. So $`gAg^1=A`$. $`\mathrm{}`$

###### Proposition 15

Let $`A`$ be a subgroup of $`G`$, $`g,fG`$, $`gag^1=a`$ for every $`aA`$, $`faf^1a`$ for some $`aA`$ and $`fAf^1=A`$. Let $`Y_n`$ be a $`n`$-orbit of $`A`$ and $`\stackrel{}{Y_n}`$ be the arbitrary ordered set $`Y_n`$, then $`g\stackrel{}{Y_n}=\stackrel{}{Y_n}g`$, $`fY_n=Y_nf`$, but $`f\stackrel{}{Y_n}\stackrel{}{Y_n}f`$.

###### Lemma 16

Let $`X_n`$ be a $`n`$-orbit of a group $`G`$ and $`L_n`$ be a partition of $`X_n`$. If the left action of $`G`$ on $`X_n`$ maintains $`L_n`$, then classes of $`L_n`$ are $`n`$-orbits of left cosets of some subgroup of $`G`$.

Proof: Let $`Y_nL_n`$. Since $`L_n`$ is a partition, the left action of $`Aut(Y_n)`$ on $`Y_n`$ is transitive and hence $`Y_n`$ is a $`n`$-orbit. $`\mathrm{}`$

The same we have

###### Lemma 17

Let $`X_n`$ be a $`n`$-orbit of a group $`G`$ and $`R_n`$ be a partition of $`X_n`$. If the right action of $`G`$ on $`X_n`$ maintains $`R_n`$, then classes of $`R_n`$ are $`n`$-orbits of right cosets of some subgroup of $`G`$.

##### Intersections and unions of left- and right-automorphic partitions.

###### Proposition 18

Let $`Y_n`$ and $`Z_n`$ be $`n`$-orbits, then $`T_n=Y_nZ_n`$ is a $`n`$-orbit and $`Aut(T_n)=Aut(Y_n)Aut(Z_n)`$.

Proof: It is sufficient to choose an initial $`n`$-tuple from $`T_n`$. $`\mathrm{}`$

###### Definition 19

Let $`M`$ be a set and $`A`$ be a system of subsets of $`M`$. We say that $`A`$ is a covering of $`M`$ if classes of $`A`$ contain all elements of $`M`$ and have non-vacuous intersections. If the all intersections are vacuous then we say that (the covering) $`A`$ is a partition of $`M`$. So we say that $`A`$ is a covering, if it is not a partition. We say also that $`A`$ is a covering, if we do not know, whether it is a partition.

###### Definition 20

Let $`X_n`$ be a $`n`$-orbit of a group $`G`$ and $`Y_n`$ be an arbitrary subset of $`X_n`$, then we say that $`L_n=GY_n`$ is *left-automorphic* and $`R_n=Y_nG`$ is *right-automorphic* covering of $`X_n`$. This definition we shall apply also to corresponding coverings of a $`k`$-orbit $`X_k`$ of a group $`G`$ for $`k<n`$.

###### Corollary 21

Let $`L_n`$ and $`R_n`$ be partitions of a $`n`$-orbit of a group $`G`$ on $`n`$-orbits of left and right cosets of a subgroup $`A<G`$, then $`L_n`$ and $`R_n`$ are left-automorphic and right-automorphic partitions.

###### Definition 22

Let $`M`$ be a set and $`P,Q`$ be partitions of $`M`$. We write:

* $`PQ`$ if for every $`AP`$ there exists $`BQ`$, so that $`AB`$.
* $`PQ`$ for partition of $`M`$ that consists of intersections of classes from $`P`$ and $`Q`$.
* $`PQ`$ for partition of $`M`$ whose class is a union of intersected classes from $`P`$ and $`Q`$.

###### Proposition 23

Let $`A,B<G`$, then $`GAGB=G(AB)`$, $`AGBG=(AB)G`$, $`GAGB=Ggr(A,B)`$ and $`AGBG=gr(A,B)G`$.

Proof:

* Since $`GAGB=G(GAGB)`$ and $`ABGAGB`$, $`GAGB=G(AB)`$. Analogously $`AGBG=(AB)G`$.
* Let $`\{A_i:i[1,l]\}GA`$, $`\{B_j:j[1,m]\}GB`$, $`A_1=A`$, $`B_1=B`$ and $`U=_{(i=1,l)}A_i=_{(j=1,m)}B_j`$, then $`UGAGB`$ and $`eU`$. Let $`fA_i`$, $`gA_k`$ and $`B_j`$ has non-vacuous intersections with $`A_i`$ and $`A_k`$, then $`f=gaba^{}`$ for some elements $`a,a^{}A`$ and $`bB`$. It shows that every element from $`U`$ can be represented as a product of elements from $`A`$ and $`B`$. Hence $`U=gr(A,B)`$ and $`GAGB=Ggr(A,B)`$. The same $`AGBG=gr(A,B)G`$$`\mathrm{}`$

From this proposition follows:

###### Lemma 24

Let $`A,B<G`$ and $`X_nOrb_n(G)`$, then $`X_nAX_nB=X_n(AB)`$, $`AX_nBX_n=(AB)X_n`$, $`X_nAX_nB=X_ngr(A,B)`$ and $`AX_nBX_n=gr(A,B)X_n`$.

##### Intersection and union of left-automorphic partition with right-automorphic partition.

Let $`L_n=X_nA`$ and $`R_n=AX_n`$. First we see that $`L_n`$ and $`R_n`$ have at least one common class the $`n`$-orbit of $`A`$ containing initial $`n`$-tuple. Then from proposition 14 we know that if $`L_n`$ and $`R_n`$ have more as one common class, then $`A`$ has non-trivial normalizer in $`G`$.

###### Lemma 25

Let $`L_nR_n`$ be not trivial, i.e. it contains a class $`Z_n`$ by power $`l`$, where $`1<l<|A|`$, then conjugate to $`A`$ subgroups have non-trivial intersections and $`Z_n`$ is a $`n`$-orbit of a some subgroup $`B<A`$.

Proof: Let $`U_nL_n`$, $`W_nR_n`$ and $`Z_n=U_nW_n`$, then $`U_n`$ is a $`n`$-orbit of some conjugate to $`A`$ subgroup $`D`$ and $`W_n`$ is a $`n`$-orbit of $`A`$. Taking in opinion that we can choose an initial $`n`$-tuple from $`Z_n`$, we obtain that $`Z_n`$ is a $`n`$-orbit of a subgroup $`B=AD`$. $`\mathrm{}`$

###### Corollary 26

Let $`A`$ be a prime order cyclic group, then $`L_nR_n`$ is trivial.

The union $`L_nR_n`$ can contain non-automorphic classes:

$$\begin{array}{c}\\ 123\\ 213\\ \\ 132\\ 312\\ \\ 231\\ 321\end{array}\begin{array}{c}\\ 123\\ 213\\ \\ 132\\ 231\\ \\ 312\\ 321\end{array}=\begin{array}{c}\\ 123\\ 213\\ \\ 132\\ 231\\ 312\\ 321\end{array}$$

and therefore it is not of interest for investigation, nevertheless the symmetry properties of this union can give an information about the structure of the studied group $`G`$ and help to find subgroups of $`G`$ that are supergroups for $`A`$.

### 2.2 The actions of permutations on $`k`$-sets

In order to consider the actions of permutations on $`k`$-sets we shall need to have some special operations that we introduce from the beginning.

#### 2.2.1 Operations on $`k`$-sets

##### Projecting and multiprojecting operators.

Let $`\alpha _k=v_1\mathrm{}v_k`$ be a $`k`$-tuple, $`lk`$ and $`i_1,i_2,\mathrm{},i_l`$ be $`l`$ different coordinates from $`[1,k]`$. Then $`\beta _l=v_{i_1}\mathrm{}v_{i_l}`$ is a $`l`$-tuple that we call a *projection* of the $`k`$-tuple $`\alpha _k`$ on the ordered set of coordinates $`I_l=\{i_1<i_2<\mathrm{}<i_l\}`$. We shall enter a projecting operator $`\widehat{p}`$ and write this projection as $`\beta _l=\widehat{p}(I_l)\alpha _k`$. The projection of all $`k`$-tuples of a $`k`$-set $`X_k`$ on $`I_l`$ gives a $`l`$-set $`X_l=\widehat{p}(I_l)X_k`$.

The projection of all $`k`$-tuples of the $`k`$-set $`X_k`$ on $`I_l`$, that distinguishes the equal $`l`$-tuples, is a multiset that we call a *multiprojection* of $`X_k`$ on $`I_l`$ and denote it as $`_{X_k}X_l`$ or simply $`X_l`$, if from context it is clear, what a multiprojection we consider. By definition $`|X_l|=|X_k|`$. Using a multiprojecting operator $`\widehat{p}_{}`$, we shall write that $`X_l=\widehat{p}_{}(I_l)X_k`$.

##### Concatenating operation.

Let $`\beta _l=v_1\mathrm{}v_l`$ and $`\gamma _m=u_1\mathrm{}u_m`$ be $`l`$\- and $`m`$-tuple, then $`(l+m)`$-tuple $`v_1v_2\mathrm{}v_lu_1u_2\mathrm{}u_m`$ we call a concatenation of $`\beta _l`$ and $`\gamma _m`$ and write this as $`\beta _l\gamma _m`$.

It will be also suitable to use the concatenation of intersected tuples. We shall consider such concatenation as multiset of coordinates, for example $`1223=1223`$.

We shall use this concatenating operation also for multisets of tuples in the next way:

Let $`Y_l`$ and $`Z_m`$ be multisets with the same number of tuples and $`\varphi :Y_lZ_m`$, then $`Y_l\stackrel{\varphi }{}Z_m`$ is the $`(m+l)`$-multiset, that consists of concatenations of $`l`$-tuples of $`Y_l`$ with $`m`$-tuples of $`Z_m`$ accordingly to the map $`\varphi `$. We shall not write the map $`\varphi `$, if it is clear from context.

##### Operation properties.

###### Lemma 27

$`l`$-projection of a $`k`$-orbit is a $`l`$-orbit.

Let $`g`$ be a permutation, $`\alpha _n=v_1\mathrm{}v_n`$ be a $`n`$-tuple and $`I_k`$ be a $`k`$-subspace.

###### Lemma 28

$`g\widehat{p}(I_k)\alpha _n=\widehat{p}(I_k)g\alpha _n`$.

Proof: It is sufficient to show the equality for $`I_k[1,k]`$.

$$g\widehat{p}(I_k)\alpha _n=gv_1\mathrm{}v_k=gv_1\mathrm{}gv_k$$

and

$$\widehat{p}(I_k)g\alpha _n=\widehat{p}(I_k)gv_1\mathrm{}gv_n=gv_1\mathrm{}gv_k.\mathrm{}$$

###### Lemma 29

$`\widehat{p}(I_k)(\alpha _ng)=\widehat{p}(gI_k)\alpha _n`$.

Proof:

$$\widehat{p}(I_k)(\alpha _ng)=\widehat{p}([1,k])v_{g1}\mathrm{}v_{gn}=v_{g1}\mathrm{}v_{gk}$$

and

$$\widehat{p}(gI_k)\alpha _n=\widehat{p}(g[1,k])v_1\mathrm{}v_n=\widehat{p}(\{g1<\mathrm{}<gk\})v_1\mathrm{}v_n=v_{g1}\mathrm{}v_{gk}.\mathrm{}$$

The equality $`\widehat{p}(I_k)(\alpha _ng)=(\widehat{p}(I_k)\alpha _n)g=\alpha _k(I_k,\alpha _n)g`$ has not an interest application, because the corresponding right permutation action on $`k`$-tuple $`\alpha _k`$ cannot be disengaged from the $`n`$-tuple $`\alpha _n`$, as it takes place by the left permutation action on $`k`$-tuple $`\alpha _k`$. But we shall write for convenience $`\alpha _kg`$ instead of $`\widehat{p}(I_k)(\alpha _ng)`$, where it will not lead to misunderstanding. Similarly, we consider a $`k`$-projection of equalities $`GY_n=X_nA`$ and $`AX_n=Y_nG`$ (lemma 9).

From $`\widehat{p}(I_k)GY_n=\widehat{p}(I_k)X_nA`$, it follows $`G\widehat{p}(I_k)Y_n=\widehat{p}(AI_k)X_n`$, where on definition 8

$$\widehat{p}(AI_k)X_n\{\widehat{p}(AI_k)\alpha _n:\alpha _nX_n\}\text{ and }\widehat{p}(AI_k)\alpha _n=\{\widehat{p}(aI_k)\alpha _n:aA\},$$

so we can write the $`k`$-projection of this equality as $`GY_k(I_k)=\widehat{p}(AI_k)X_n`$ or (by correct understanding) simply as $`GY_k=X_kA`$.

For the second equality we have $`\widehat{p}(I_k)AX_n=A\widehat{p}(I_k)X_n=AX_k(I_k)`$ and

$$\widehat{p}(I_k)Y_nG=\widehat{p}(GI_k)Y_n\{\widehat{p}(gI_k)Y_n:gG\}.$$

For convenience we will write the $`k`$-projection of second equality simply as $`AX_k=Y_kG`$.

###### Proposition 30

Let $`X_n`$ be a $`n`$-set and $`P_n`$, $`Q_n`$ be two partitions of $`X_n`$. Let $`P_k=\widehat{p}(I_k)P_n`$ and $`Q_k=\widehat{p}(I_k)Q_n`$ be partitions of $`X_k=\widehat{p}(I_k)X_n`$. It does not necessitate the equality $`\widehat{p}(I_k)(P_nQ_n)=\widehat{p}(I_k)P_n\widehat{p}(I_k)Q_n)`$.

Proof: $`X_n=\{15,26,36,45\}`$, $`P_n=\{\{15,26\},\{36,45\}\}`$ and $`Q_n=\{\{15,36\},\{26,45\}\}`$$`\mathrm{}`$

#### 2.2.2 Some additional definitions and auxiliary statements

###### Definition 31

The presentation $`GY_k=\{gY_k:gG\}`$ that we use for the action of a group $`G`$ on a $`k`$-subset $`Y_k`$ we shall apply also for the action of a group $`G`$ on a system of $`k`$-subsets $`P_k`$ as $`GP_k=\{gP_k:gG\}`$ and $`gP_k=\{gY_k:Y_kP_k\}`$.

###### Definition 32

Let $`M`$ be a set and $`Q`$ be a set of subsets of $`M`$, then we write $`Q_{(UQ)}U`$. From such definition follows that for $`GP_k`$ we can consider two kinds of unions: $`GP_k`$ and $`GP_k`$. For example, let we have two sets $`\{\{1,2\},\{2,3\}\}`$ and $`\{\{2,3\},\{4,5\}\}`$, then the first union of these sets is the set $`\{\{1,2\},\{2,3\},\{4,5\}\}`$ and the second is $`\{1,2,3,4,5\}`$.

The symbol $``$ we shall apply to union of intersected classes of a system of sets, as in example: $`\{\{1,2\},\{2,3\},\{4,5\}\}=\{\{1,2,3\},\{4,5\}\}`$.

###### Definition 33

Let $`\alpha _k`$ be a $`k`$-tuple. We shall write the set of coordinates of $`\alpha _k`$ as $`Co(\alpha _k)`$. We shall use this notation also for a $`k`$-set $`Y_k`$, where $`Co(Y_k)=\{Co(\alpha _k):\alpha _kY_k\}`$.

###### Lemma 34

Let $`M`$ be a $`m`$-element set and $`M`$ be a homogeneous multiset with multiplicity $`k`$. Let $`P_m`$ be a multipartition of $`M`$ on $`k`$-element multisubsets of $`M`$, then $`P_m`$ is a union of $`k`$ distributions of $`m`$ elements of set $`M`$ between $`m`$ $`k`$-element classes of $`P_m`$.

Proof: We do an induction on $`m`$. Let us to represent $`P_m`$ as $`m\times k`$ matrix, whose lines are classes of $`P_m`$. Let $`m=1`$, then the statement is evidently correct. Let $`m>1`$ and first $`lk`$ lines contains all $`k`$ occurences of an element $`uM`$. By permutation of elements in these $`l`$ lines we can placed element $`u`$ in all $`k`$ columns. Now by permutation of elements in $`k`$ columns we can replaced element $`u`$ in the first line. Thus we have obtained $`(m1)\times k`$ matrix (without the first line) that by induction hypothesis can be transformed (with permutation of elements in lines) to $`m1`$ different elements in each column. Now we need only to do the inverse permutation of element $`u`$ from the first line with corresponding elements in other $`l1`$ lines. $`\mathrm{}`$

From this lemma follows

###### Corollary 35

Let $`M`$ be a $`m`$-element set and $`M_2=MM`$, where $`M`$ is homogeneous, then $`M_2`$ can be partition in $`m`$-element subsets that are concatenations $`MM`$.

Proof: Let $`|M|/|M|=k`$, $`M_2`$ be associated with space $`I_2=I_1^1I_1^2`$ and $`L_2`$ be the partition of $`M_2`$ on $`k`$-element classes so that $`\widehat{p}(I_1^1)L_2=M`$, then $`\widehat{p}(I_1^2)L_2=P_m`$ from lemma 34. $`\mathrm{}`$

###### Lemma 36

Let $`M_2`$ be a set of pairs that is associated with space $`I_2=I_1^1I_1^2`$. Let $`\widehat{p}_{}(I_1^1)M_2=\widehat{p}_{}(I_1^2)M_2`$, then $`M_2`$ can be partition in cycles.

Proof: Let $`u_1u_2M_2`$, then there exists a pair $`u_2u_3M_2`$. The continuation gives a first cycle $`C_2=\{u_1u_2,u_2u_3,\mathrm{},u_ru_1\}`$. The set $`M_2C_2`$ holds the property of the set $`M_2`$. $`\mathrm{}`$

###### Definition 37

Let $`Y_k`$ be a $`k`$-subset defined on the subset $`UV`$, then under $`Aut(Y_k)`$ we shall understand the permutation group on the set $`U`$. An extension of $`Aut(Y_k)`$ on the set $`V`$ we shall write as $`Aut(Y_k;V)`$.

###### Definition 38

Let $`c_1c_2\mathrm{}c_l`$ be decomposition of a permutation $`g`$. Product $`a`$ of some cycles from this decomposition we shall call a subdecomposition of $`g`$ and write this as $`ag`$.

Let $`a`$ be a subdecomposition of an automorphism $`gG`$. We shall call the permutation $`a`$ as a *subautomorphism* of $`G`$ and write this as $`aG`$. Let $`B`$ be an intransitive subgroup of $`G`$ and $`A(U)`$ be a transitive component of $`B`$ on the subset $`UV`$. We shall write this fact as $`A(U)<<G`$ and say that $`A(U)`$ is a projection of $`B`$. It is clear that $`A(U)`$ is generated by some subautomorphisms of $`G`$.

We can consider an action of a subautomorphism $`a`$ on a $`k`$-orbit $`X_k`$ of a group $`G`$, extending it to an action of some automorphism $`gG`$.

###### Definition 39

Let $`X_k`$ be a $`k`$-orbit of a group $`G`$ and $`Y_kX_k`$ be a $`k`$-orbit of a subgroup of $`G`$, then we say that $`Y_k`$ is a $`k`$-suborbit of $`G`$.

###### Definition 40

Let $`G`$ be a group, $`X_nOrb_n(G)`$, $`I_k`$ be a $`k`$-subspace and $`Co(I_k)`$ be a $`1`$-orbit of some subgroup $`A<G`$, then we say that number $`k`$ is automorphic, $`I_k`$ is an *automorphic subspace* and $`X_k=\widehat{p}(I_k)X_n`$ is a *right-automorphic $`k`$-orbit* or a *$`k`$-rorbit*.

#### 2.2.3 The left action of permutations on $`k`$-sets

The left action of a permutation on a $`k`$-set is the same as its action on a $`n`$-set. The right action of a permutation on a $`k`$-set follows from its action on a $`n`$-set. The right action is not just visible combinatorially as the left action, so we shall begin with the left action.

We say that two sets of $`k`$-tuples $`Y_k`$ and $`Y_k^{}`$ are $`S_n`$-isomorphic or simply isomorphic if there exists permutation $`gS_n`$ so that $`Y_k^{}=gY_k`$, for example $`Y_2=\{12,21\}`$ and $`Y_2^{}=\{13,31\}`$. We shall say that $`Y_k`$ and $`Y_k^{}`$ are $`G`$-isomorphic, if $`gG<S_n`$ and we study invariants of $`G`$. We shall not indicate a group relative to that we consider the symmetry, if it is clear from context. From this definition follows:

###### Proposition 41

Let $`X_k`$ be a $`k`$-orbit and $`Y_k`$ be an arbitrary $`k`$-subset of $`X_k`$, then $`Aut(X_k)Y_k`$ is a covering of $`X_k`$ on isomorphic to $`Y_k`$ classes.

and

###### Corollary 42

$`n`$-Orbits of left cosets of a subgroup $`A`$ of a group $`G`$ are isomorphic.

The $`n`$-orbits of right cosets of a subgroup $`A`$ in general are not isomorphic. An example is $`3`$-orbits of the subgroup $`A=gr((12))<S_3`$:

$$\begin{array}{ccc}& & \\ 1& 2& 3\\ 2& 1& 3\end{array}\text{ and }\begin{array}{ccc}& & \\ 1& 3& 2\\ 2& 3& 1\end{array}.$$

The same is valid for $`k`$-orbits of left, right cosets of a subgroup $`A`$ by $`k<n`$.

###### Proposition 43

Let $`G`$ be a group, $`X_nOrb_n(G)`$, $`X_kOrb_k(G)`$ and $`A<G`$, then

* $`n`$-Orbits of left cosets of $`A`$ form a partition of $`X_n`$.
* The $`G`$-isomorphic $`k`$-orbits of left cosets of $`A`$ belong to the same $`k`$-orbit $`X_k`$ and form a covering of $`X_k`$.

Proof: The first statement is evident. Let $`Y_kOrb_k(A)`$ be subset of $`X_k`$ , then a covering $`L_k=GY_k`$ of $`X_k`$ contains all $`G`$-isomorphic to $`Y_k`$ $`k`$-orbits. The example of such covering is $`L_1=\{\{1,2\}\{2,3\}\{1,3\}\}`$ $`\mathrm{}`$

A $`k`$-orbit $`X_k`$ of a group $`G`$ can have different representations through $`k`$-orbits of the same subgroup $`A<G`$, because $`X_k`$ can contain non-isomorphic $`k`$-orbits of $`A`$. For example, $`1`$-orbit of the symmetric group $`S_n`$ can be represented, on the one hand, as a covering by $`1`$-orbits of left cosets of $`gr((12\mathrm{}(n1)))`$ that are $`(n1)`$-element subsets of $`V`$ and, on the other hand, as a partition on $`1`$-orbits of left cosets of this subgroup that are $`1`$-element subsets of $`V`$.

###### Lemma 44

Let $`A<G`$, $`X_nOrb_n(G)`$, $`Y_nX_n`$ be a $`n`$-orbit of $`A`$ and $`Y_k=\widehat{p}(I_k)Y_n`$. Let $`U_nX_n`$ be the union of such classes of $`GY_n`$ whose $`I_k`$-projection is $`Y_k`$, then $`U_n`$ is a $`n`$-orbit.

Proof: $`Aut(U_n)=Aut(Y_k;V)G`$. $`\mathrm{}`$

The subset $`U_n`$ can contain not all $`n`$-tuples whose $`I_k`$-projections belongs to $`Y_k`$. An example is given by the group $`S_3`$, $`U_3=Y_3=\{123,213\}`$ and $`k=1`$:

$$\begin{array}{ccc}& & \\ 1& 2& 3\\ 2& 1& 3\\ & & \\ 1& 3& 2\\ 3& 1& 2\\ & & \\ 2& 3& 1\\ 3& 2& 1\end{array}.$$

In this case $`U_1=\{1,2\}`$ and the intersections $`\{1,2\}\{1,3\}`$ and $`\{1,2\}\{2,3\}`$ are not vacuous.

##### Now we consider when a subgroup $`A<G`$ forms a partition of a $`k`$-orbit $`X_kOrb_k(G)`$.

Let a $`k`$-set $`X_k`$ be a $`k`$-projection of a $`(k+1)`$-set $`X_{k+1}`$, then we shall say that $`X_{k+1}`$ is an *extension* of $`X_k`$ on a $`(k+1)`$-subspace or is a $`(k+1)`$-extension of $`X_k`$.

###### Lemma 45

Let $`X_kOrb_k(G)`$, $`A<G`$ and $`X_kA=GY_k`$ be a partition. Let $`X_{k+1}Orb_{k+1}(G)`$ be an extension of $`X_k`$, then $`X_kA`$ generates a partition $`X_{k+1}A`$.

Proof: Let $`Y_{k+1}X_{k+1}`$ and $`Y_k=\widehat{p}(I_k)Y_{k+1}`$. If $`GY_{k+1}`$ is not a partition, then evidently $`GY_k`$ contains intersected classes. $`\mathrm{}`$

###### Lemma 46

Let $`X_kOrb_k(G)`$, $`A,B<G`$ be not conjugate subgroups or $`A,B`$ be conjugate subgroups and $`Y_k,Z_kX_k`$ be not isomorphic $`k`$-orbits of $`A`$ and $`B`$ correspondingly. Let $`Y_k,Z_k`$ be intersected and $`X_kA=GY_k,X_kB=GZ_k`$ be partitions, then $`X_kAX_kB=X_kgr(A,B)`$.

Proof: $`G(GY_kGZ_k)=GY_kGZ_k`$. Then $`X_kAX_kB=GT_k=X_kC`$, where $`C=gr(A,B)`$ accordingly to lemma 24. $`\mathrm{}`$

Without condition $`Y_kZ_k\mathrm{}`$ the equality $`X_kAX_kB=X_kgr(A,B)`$ can lead to misunderstanding for conjugate subgroups $`A,B`$. Consider an example:

$$\begin{array}{cc}& \\ 1& 2\\ 2& 1\\ & \\ 1& 3\\ 3& 1\\ & \\ 2& 3\\ 3& 2\end{array},\begin{array}{cc}& \\ 1& 3\\ 2& 3\\ & \\ 1& 2\\ 3& 2\\ & \\ 2& 1\\ 3& 1\end{array}.$$

* The subgroups $`A=gr((12))`$ and $`B=gr((13))`$ are conjugate in $`G=S_3`$, so they determine the same partitions of $`2`$-orbits of $`G`$, if we consider isomorphic (not intersected) $`2`$-orbits of these subgroups. Therefore in this case $`X_kAX_kB=X_kAX_kgr(A,B)`$.
* If we consider not isomorphic and not intersected $`2`$-orbits of the same subgroup $`A=gr((12))`$, then we have two different partitions $`L_1,L_2`$ of $`2`$-orbit $`X_2`$ of $`S_3`$. So it can be seen that $`X_2AX_2AX_2gr(A,A)=X_2A`$. This misanderstansing follows from interpretation $`X_2A`$, first, as $`S_3Y_2^{}`$, $`Y_2^{}=\{12,21\}`$, and, second, as $`S_3Y_2^{\prime \prime }`$, $`Y_2^{\prime \prime }=\{13,23\}`$, where $`Y_2^{}Y_2^{\prime \prime }=\mathrm{}`$. If we take $`Y_2^{\prime \prime }=\{12,32\}`$, then $`A=gr((12))`$, $`B=gr((13))`$ and formula $`X_kAX_kB=X_kgr(A,B)`$ gives correct result.

###### Lemma 47

Let $`X_kOrb_k(G)`$, $`Y_kX_k`$, $`\alpha _kY_k`$ and $`Y_k`$ be a maximal subset with property: $`Co(Y_k)=Co(\alpha _k)`$, then $`L_k=GY_k`$ is a partition of $`X_k`$.

Proof: On the condition the permutations of coordinates of $`Y_k`$ that maintains $`Y_k`$ maintains also each class of $`L_k=GY_k`$. $`\mathrm{}`$

##### In the next statements we shall study reverse question.

Namely, when a subset of a $`k`$-orbit of a group $`G`$ generates a subgroup of $`G`$.

###### Lemma 48

Let $`X_kOrb_k(G)`$ and $`L_k`$ be a partition of $`X_k`$. If the left action of $`G`$ on $`X_k`$ maintains $`L_k`$, then classes of $`L_k`$ are $`k`$-orbits of left cosets of some subgroup $`A<G`$.

Proof: Let $`Y_kL_k`$, then $`L_k=GY_k`$, hence a subgroup $`A=Aut(Y_k:V)G`$ acts on $`Y_k`$ transitive. $`\mathrm{}`$

###### Remark 49

It can be seen that the partitioning of $`X_n`$ (and hence $`X_k`$) on $`G`$-isomorphic classes is not sufficient for the automorphism of this partition. This shows the next partition $`L_n`$ of a $`n`$-orbit $`X_n`$ of the group $`G=C_6`$:

$$\begin{array}{cccccc}& & & & & \\ 1& 2& 3& 4& 5& 6\\ 2& 3& 4& 5& 6& 1\\ & & & & & \\ 3& 4& 5& 6& 1& 2\\ 4& 5& 6& 1& 2& 3\\ & & & & & \\ 5& 6& 1& 2& 3& 4\\ 6& 1& 2& 3& 4& 5\end{array}.$$

The classes of $`L_n`$ are connected with permutation $`(135)(246)`$, but are not automorphic. Let $`Y_nL_n`$, then in this case $`|GY_n|`$ is a covering of $`X_n`$.

From lemmas 47 and 48 follows

###### Corollary 50

Let $`X_kOrb_k(G)`$, $`Y_kX_k`$, $`\alpha _kY_k`$ and $`Y_k`$ be a maximal subset with property: $`Co(Y_k)=Co(\alpha _k)`$, then $`Y_k`$ is a $`k`$-suborbit of $`G`$.

Consider a generalization of lemma 48.

###### Theorem 51

Let $`X_kOrb_k(G)`$, $`Y_kX_k`$ and $`L_k=GY_k`$ be a covering of $`X_k`$. If $`|Y_k||L_k|`$ divides $`|G|`$, then $`Y_k`$ is a $`k`$-orbit of some subgroup $`A<G`$.

Proof: On condition, there exists a partition $`L_n`$ of a $`n`$-orbit $`X_nOrb_n(G)`$ so that $`\widehat{p}(I_k)L_n=L_k`$ and $`|L_n|=|L_k|`$. Then there exists $`Y_nL_n`$ so that $`\widehat{p}(I_k)Y_n=Y_k`$, $`G\widehat{p}(I_k)Y_n=\widehat{p}(I_k)GY_n=GY_k`$. Hence $`L_n=GY_n`$ is a partition of $`X_n`$ and we can apply the lemma 16. $`\mathrm{}`$

###### Corollary 52

Let $`X_kOrb_k(G)`$, $`Y_kX_k`$ and $`L_k=GY_k`$ be a covering of $`X_k`$. Let classes of $`L_k`$ can be assembled in isomorphic partitions of $`X_k`$. Let $`Q_k`$ be a system of these partitions and $`|Q_k||X_k|`$ divides $`|X_n|`$. Let $`L_k^{}Q_k`$ and $`Y_kL_k^{}`$, then $`X_k`$ is a $`k`$-orbit of a subgroup $`B=Aut(L_k^{})G`$, $`L_k^{}=BY_k`$ and $`Y_k`$ is a $`k`$-orbit of some subgroup $`A<B`$.

Proof: Let $`X_nOrb_n(G)`$ and $`X_k=\widehat{p}(I_k)X_n`$. Since $`|Q_k||X_k|`$ divides $`|X_n|`$, there exists a partition $`L_n`$ of $`X_n`$ so that $`\widehat{p}(I_k)L_n=X_k`$ and permutations of classes of $`L_n`$ correspond with permutations of partitions from $`Q_k`$. So the classes of $`L_n`$ are $`n`$-orbits of subgroups of $`G`$ and hence $`X_k`$ is a $`k`$-orbit of the subgroup $`B=Aut(L_k^{})G`$. Since $`BY_k=L_k^{}`$ is a partition of $`X_k`$ and $`B`$ acts on $`L_k^{}`$ transitive, the subgroup $`A=Aut(Y_k;V)B`$ acts on $`Y_k`$ transitive. $`\mathrm{}`$

The example of such $`G`$-isomorphic system of partitions is

$$Q_1=\{\begin{array}{c}\\ 1\\ 2\\ \\ 3\\ 4\end{array},\begin{array}{c}\\ 1\\ 3\\ \\ 2\\ 4\end{array},\begin{array}{c}\\ 1\\ 4\\ \\ 2\\ 3\end{array}\},$$

where $`Q_1`$ is formed by $`1`$-orbits of left cosets of the subgroup $`gr((12)(34))<A_4`$.

Let $`Q_k`$ be a set of $`S_n`$-isomorphic partitions that therefore do not belong to the same $`k`$-orbit $`X_k`$, then the action of $`G`$ on $`X_k`$ maintains simultaneously all partitions $`L_k^i`$ as in the previous example, where now $`Q_1`$ is formed by $`1`$-orbits of not conjugate subgroups $`gr((12)(34))`$, $`gr((13)(24))`$ and $`gr((14)(23))`$ of the group $`S_2S_2`$.

###### Corollary 53

Let $`X_k`$ be a $`k`$-rorbit of a group $`G`$ that contains a $`k`$-rcycle $`rC_k`$, then $`rC_k`$ is a $`k`$-orbit of some subgroup $`A<G`$.

Proof: It is a special case of the corollary 50. $`\mathrm{}`$

The order of the subgroup $`A`$ in the corollary can differ from $`k`$. The example gives the subgroup $`A=gr((1234)(56))<S_6`$ and $`rC_2=\{56,65\}`$.

Projections of $`k`$-rcycles from $`X_k`$ on $`l`$-subspace ($`l<k`$) can have non-trivial intersections as in example:

$$\begin{array}{ccc}\begin{array}{ccc}& & \\ 1& 2& 3\\ & & \\ 2& 3& 1\\ 3& 1& 2\end{array}\hfill & \text{ and }& \hfill \begin{array}{c}& & \multicolumn{-1}{c}{}\\ 1& 2& 4\\ & & \multicolumn{-1}{c}{}\\ 2& 4& 1\\ 4& 1& 2\end{array}.\end{array}$$

So these projections form a covering of $`X_l`$.

#### 2.2.4 The special left action of permutations on $`k`$-sets

There exists a left action of permutations on a $`k`$-orbit $`X_k`$ of a group $`G`$ that forms a partition $`R_k`$ of $`X_k`$ on $`k`$-orbits of right cosets of a subgroup $`A<G`$. It is a partition $`R_k=AX_k`$.

Classes of $`AX_k`$ as well as classes of $`AX_n`$ are in general case not isomorphic. Moreover, if the classes of $`AX_n`$ have the same order, then the classes of $`AX_k`$ satisfy to this property not always. For example $`R_1=gr((12))\{1,2,3\}=\{\{1,2\},\{3\}\}`$.

$`k`$-Orbits of left cosets of a subgroup $`A`$ can have intersections, $`k`$-Orbits of right cosets of a subgroup $`A`$ have no intersection.

$`k`$-Orbits of left cosets of a subgroup $`A`$ are $`k`$-orbits of subgroups that are conjugate to $`A`$, $`k`$-orbits of right cosets of a subgroup $`A`$ are $`k`$-orbits of the subgroup $`A`$. These properties we shall assemble in the following statements:

###### Lemma 54

Let $`A,B`$ be conjugate subgroups of a group $`G`$ and $`X_n`$ be a $`n`$-orbit of $`G`$, then

1. The partitions of $`G`$ on left (right) cosets of subgroups $`A,B`$ are not equal.
2. The partitions of $`X_n`$ on $`n`$-orbits of left cosets of subgroups $`A,B`$ are equal and this partition consists of isomorphic classes.
3. The partitions of $`X_n`$ on $`n`$-orbits of right cosets of subgroups $`A,B`$ are not equal and each partition consists of not isomorphic classes of power $`|A|`$.

Proof: The first statement is the fact from the group theory, the second is the repeating of lemma 11 and the third follows from lemma 10. $`\mathrm{}`$

###### Corollary 55

Let $`A,B`$ be conjugate subgroups of a group $`G`$ and $`X_k`$ be a $`k`$-orbit of $`G`$, then

1. The coverings of $`X_k`$ on isomorphic $`k`$-orbits of left cosets of subgroups $`A,B`$ are equal.
2. The partitions of $`X_k`$ on $`k`$-orbits of right cosets of subgroups $`A,B`$ are not equal, each partition consists of not isomorphic classes, which can differ by power.

##### $`k`$-orbit property of normal subgroups.

###### Lemma 56

Let $`X_kOrb_k(G)`$, $`A<G`$ and $`R_k=AX_k=X_kA=L_k`$. If $`A`$ is the maximal subgroup, then $`AG`$.

Proof: Let $`X_nOrb_n(G)`$, then $`R_n=AX_n=X_nA=L_n`$, because $`L_n`$ is the only partition of $`X_n`$ with property $`\widehat{p}(I_k)L_n=L_k`$ and $`|L_n|=|L_k|`$, hence $`AG`$. $`\mathrm{}`$

###### Corollary 57

Let $`Y_k`$ be a maximal subset of a $`k`$-orbit $`X_k`$ so that $`Co(Y_k)=Co(\alpha _k)`$ for some $`k`$-tuple $`\alpha _kY_k`$, then a stabilizer $`Stab(\alpha _k)Stab(Y_k)`$.

###### Lemma 58

Let $`AG`$ and $`X_kOrb_k(G)`$, then $`R_k=AX_k=X_kA=L_k`$.

Proof: It is given that $`R_n=AX_n=X_nA=L_n`$, then $`\widehat{p}(I_k)AX_n=\widehat{p}(I_k)X_nA`$ or $`AX_k=X_kA`$$`\mathrm{}`$

So we have

###### Theorem 59

A group $`G`$ is a simple group if and only if $`AX_kX_kA`$ for arbitrary $`k`$, arbitrary $`X_kOrb_k(G)`$ and each subgroup $`A<G`$.

##### Intersections and unions of $`k`$-orbits

Above we have seen (proposition 18) that the intersection of $`n`$-orbits is a $`n`$-orbit. The same is correct

###### Lemma 60

Let $`Y_k`$ and $`Z_k`$ be $`k`$-orbits, then $`T_k=Y_kZ_k`$ is a $`k`$-orbit of $`Aut(T_k)=Aut(Y_k)Aut(Z_k)`$.

Proof: It is sufficient to consider the intersection of $`n`$-orbits of $`Aut(Y_k)`$ and $`Aut(Z_k)`$ and then their corresponding $`k`$-projections. $`\mathrm{}`$

###### Corollary 61

Let $`Y_k`$ and $`Z_k`$ be $`k`$-suborbits of a $`k`$-orbit $`X_k`$, $`A=Aut(Y_k)Aut(X_k)`$ and $`B=Aut(Z_k)Aut(X_k)`$, then $`(AB)X_k=AX_kBX_k`$.

For subgroups $`G<Aut(Y_k)`$ and $`G^{}<Aut(Z_k)`$ with $`k`$-orbits $`Y_kOrb_k(G)`$ and $`Z_kOrb_k(G^{})`$ the similar relation is not correct. Let us to give a counterexample:

The partition $`R_1=AX_1=AV`$ is a system of orbits of $`A`$ on $`V`$ in the conventional meaning. Let $`A=gr((12))<S_3`$ and $`B=gr((123))<S_3`$, then $`AV=\{\{1,2\},\{3\}\}`$, $`BV=\{\{1,2,3\}\}`$, $`AVBV=\{\{1,2\},\{3\}\}`$ and $`(AB)V=\{\{1\},\{2\},\{3\}\}`$.

This example, lemma 60 and corollary 61 determine the relation between intersections of groups, their $`k`$-orbits and corresponding systems of $`k`$-orbits of right cosets of this groups (subgroups). The same is valid for the intersection of systems of $`k`$-orbits of left cosets.

The union of partitions of $`X_kOrb_k(G)`$ on $`k`$-orbits of left cosets of subgroups $`A,B<G`$ we have considered in lemma 46.

For the union of partitions of $`X_kOrb_k(G)`$ on $`k`$-orbits of right cosets of subgroups $`A,B<G`$ we have:

###### Lemma 62

$`AX_kBX_k=gr(A,B)X_k`$.

##### The condition of automorphism of a subspace $`I_kV`$.

###### Lemma 63

Let $`X_n`$ be a $`n`$-orbit of a transitive group $`G`$, $`X_k=\widehat{p}(I_k)X_n`$, $`|X_n|/|X_k|>1`$ and $`I_k`$ contains all elements of $`V`$ that are fixed with $`Stab(I_k)<G`$, then $`I_k`$ is automorphic.

Proof: Let $`Co(I_k)=\{v_i:i[1,k]\}`$, $`T_k^1Orb_k(Stab(v_1))`$, $`T_k^1X_k`$, $`\widehat{p}(v_1)T_k^1=v_1`$ and $`L_k^{}=GT_k^1`$. Let $`T_k^iOrb_k(Stab(v_i))`$ be a class of $`L_k^{}`$, then $`Stab(I_k)T_k^i=T_k^i`$. It follows that all $`T_k^i`$ consist of $`k`$-orbits of right cosets of $`Stab(I_k)`$ and systems of these $`k`$-orbits of right cosets of $`Stab(I_k)`$ for different $`i`$ are isomorphic. Hence each $`T_k^i`$ contains a fix $`k`$-tuple $`\alpha _k^i`$ for that $`Co(\alpha _k^i)=Co(I_k)`$. The union $`_{(i=1,k)}\alpha _k^i`$ is a $`k`$-orbit of a normalizer $`N_G(Stab(I_k))`$ (corollary 57) that acts transitive on the subset $`Co(I_k)`$. Hence $`I_k`$ is automorphic. $`\mathrm{}`$

#### 2.2.5 The right action of permutations on $`k`$-sets

##### Right action isomorphism.

Under right action of a permutation $`g`$ on a $`k`$-tuple $`\alpha _k`$ we understand the mapping of $`\alpha _k`$ on a $`k`$-tuple $`\beta _k\alpha _kg`$ that is placed on the position of coordinates of $`\alpha _k`$ in the same $`n`$-tuple $`\alpha _n`$ under the right action of $`g`$ on $`\alpha _n`$. If $`\alpha _k=v_1v_2\mathrm{}v_k`$, then on definition we write $`\alpha _kg=v_{g1}v_{g2}\mathrm{}v_{gk}`$. Thus we consider the $`k`$-tuple $`\alpha _k\alpha _n`$ with its certain position in $`\alpha _n`$ that we define by $`k`$-subspace of coordinates $`I_k`$.

Let $`X_nOrb_n(G)`$, $`Y_nX_n`$, $`Y_k=\widehat{p}(I_k)Y_n`$, $`gS_n`$ and $`Y_k^{}=Y_kg=\widehat{p}(gI_k)Y_n`$, then we say that $`Y_k`$ and $`Y_k^{}`$ are right $`S_n`$-related. If $`gG`$, then $`Y_k`$ and $`Y_k^{}`$ are right $`G`$-related. In general case the image $`Y_k^{}`$ is not isomorphic to its original $`Y_k`$. We shall study, when the right action of a permutation transforms $`k`$-subset $`Y_k`$ on isomorphic $`k`$-subset $`Y_k^{}`$.

##### Two kinds of right action isomorphism.

###### Definition 64

If we study $`k`$-orbits of a group $`G`$, $`X_kOrb_k(G)`$, $`Y_kX_k`$, $`a,bS_n`$ and a $`k`$-subset $`Y_k^{}=Y_ka=bY_k`$, then we say that $`Y_k^{}`$ and $`Y_k`$ are right $`S_n`$-isomorphic (as in first case of example 7). If $`a,bG`$, then we say that $`Y_k^{}`$ and $`Y_k`$ are right $`G`$-isomorphic.

Let $`Y_k=\widehat{p}(I_k)Y_nX_k`$, $`X_k^{}Orb_k(G)`$, $`Y_k^{}=\widehat{p}(I_k^{})Y_nX_k^{}`$ and $`Y_k^{}=Y_ka=bY_k`$. If $`aG`$ then $`X_k^{}=X_k`$, and $`Y_k^{}X_k`$ too. Now we shall find, when from $`aG`$ it follows $`bG`$.

###### Proposition 65

Let $`Y_k`$ and $`Y_k^{}`$ be arbitrary $`S_n`$-isomorphic subsets of a $`k`$-orbit $`X_k`$, then $`Y_k`$ and $`Y_k^{}`$ are not with necessary $`Aut(X_k)`$-isomorphic.

Proof: The $`2`$-subsets $`\{12,23\}`$ and $`\{12,24\}`$ from the $`2`$-orbit $`X_2^{}`$ (page 100) are $`S_n`$-isomorphic, but not $`Aut(X_2^{})`$-isomorphic. $`\mathrm{}`$

###### Proposition 66

Let $`Y_k`$ and $`Y_k^{}`$ be arbitrary right $`S_n`$-isomorphic $`k`$-subsets of a $`k`$-orbit $`X_k`$ of a group $`G`$, then $`Y_k`$ and $`Y_k^{}`$ are $`G`$-isomorphic.

Proof: Let $`Y_k=\{I_k(i):i[1,|Y_n|]\}`$ and $`Y_k^{}=\{I_k^{}(i):i[1,|Y_n|]\}`$, then $`Y_k=\widehat{p}(I_k(i))Y_n`$ and $`Y_k^{}=\widehat{p}(I_k^{}(i))Y_n`$. Maps $`I_k(i)I_k^{}(i)`$ are restrictions of automorphisms. Hence a map $`I_k(i)I_k^{}(i)`$ is also a restriction of an automorphism. $`\mathrm{}`$

##### General properties of right permutation action.

###### Proposition 67

$`k`$-Orbits of left, right cosets of a subgroup $`A`$ are connected with elements of $`G`$.

Proof: From proposition 12 we obtain $`Y_k^{}(I_k)=\widehat{p}(I_k)Y_n^{}=\widehat{p}(I_k)gY_n^{\prime \prime }f^1=g\widehat{p}(I_k)Y_n^{\prime \prime }f^1=gY_k^{\prime \prime }(I_k)f^1=gY_k^{\prime \prime }(f^1I_k)`$. $`\mathrm{}`$

###### Proposition 68

The right action of any automorphism $`gG`$ on a $`k`$-orbit of a normal subgroup $`HG`$ is isomorphic.

Proof: Accordingly to proposition 13 $`\widehat{p}(I_k)gY_n=\widehat{p}(I_k)Y_ng`$ or $`gY_k=Y_kg`$. $`\mathrm{}`$

Now we give a generalization of proposition 14.

###### Lemma 69

Let $`A<G`$, $`X_kOrb_k(G)`$, $`L_k=X_kA=GY_k`$, $`R_k=AX_k`$ and $`Q_k=L_kR_k\mathrm{}`$. Let $`A`$ be a maximal subgroup, then $`A`$ has non-trivial normalizer $`B=N_G(A)`$.

Proof: Let $`Z_k=Q_k`$, then $`Aut(Y_k;V)Aut(Z_k;V)Aut(Z_k;V)`$, where $`Z_k`$ is not with necessary automorphic. Hence $`A=Aut(Y_k;V)Aut(Z_k;V)GAut(Z_k;V)G=B`$. $`\mathrm{}`$

###### Proposition 70

Let $`A`$ be a subgroup of $`G`$, $`g,fG`$, $`gag^1=a`$ for every $`aA`$ and $`faf^1a`$ for some $`aA`$, but $`fAf^1=A`$. Let $`Y_k`$ be a $`k`$-orbit of $`A`$ and $`\stackrel{}{Y_k}`$ be the arbitrary ordered set $`Y_k`$, then $`g\stackrel{}{Y_k}=\stackrel{}{Y_k}g`$ and $`fY_k=Y_kf`$, but $`f\stackrel{}{Y_k}\stackrel{}{Y_k}f`$.

Proof: It follows from proposition 15. $`\mathrm{}`$

##### Right permutation action on $`k`$-rcycles.

###### Lemma 71

Let $`C_{lk}`$ be a $`(l,k)`$-cycle, then $`C_{lk}=C_{l_1p_1}C_{l_2p_2}\mathrm{}C_{l_qp_q}`$, where $`_{i=1}^qp_i=k`$, $`l_i`$ divides $`|C_{l_ip_i}|=l`$, $`C_{l_ip_i}`$ is a $`p_i`$-projection of a $`l_i`$-rcycle and different $`l_i`$-rcycles have no intersection on $`V`$.

Proof: From definition it follows that $`C_{lk}=gr(g)\alpha _k`$ for some permutation $`g`$ and $`k`$-tuple $`\alpha _k`$. Let $`n`$-tuple $`\beta _n=\beta _{l_1}\beta _{l_2}\mathrm{}\beta _{l_q}`$, $`g=(\beta _{l_1})(\beta _{l_2})\mathrm{}(\beta _{l_q})`$ and $`m=_{i=1}^ql_i`$, then $`g`$ generates $`(l,m)`$-cycle $`C_{lm}=rC_{l_1}rC_{l_2}\mathrm{}rC_{l_q}`$. The $`(l,k)`$-cycle $`C_{lk}`$ is a $`k`$-projection of the $`(l,m)`$-cycle $`C_{lm}`$$`\mathrm{}`$

The $`(l,k)`$-cycle $`C_{lk}`$ can be represented as a concatenation of $`(l,p_i)`$-multiorbits, whose $`p_i`$-projections are either $`p_i`$-tuple, or $`S_{l_i}^{p_i}`$-orbits, or $`p_i`$-projections of $`l_i`$-rcycles. It is obtained from lemma 71 by doing singled out the concatenation of fix $`1`$-tuples and reassembling the cycles in $`S_{l_i}^{p_i}`$-orbits as in example:

$$\begin{array}{cccccccc}& & & & & & & \\ 1& 2& 3& 4& 5& 7& 6& 8\\ 2& 1& 3& 4& 7& 5& 8& 6\end{array}=\begin{array}{cccccccc}& & & & & & & \\ 1& 2& 3& 4& 5& 6& 7& 8\\ 2& 1& 3& 4& 7& 8& 5& 6\end{array}.$$

The difference in representations of type

$$\begin{array}{cccc}& & & \\ 5& 7& 6& 8\\ 7& 5& 8& 6\end{array}\text{ and }\begin{array}{cccc}& & & \\ 5& 6& 7& 8\\ 7& 8& 5& 6\end{array}$$

can be important if rcycles $`\{57,75\}`$ and $`\{68,86\}`$ are not $`G`$-isomorphic.

There exist cases, where the partitioning of a $`(l,k)`$-cycle on right $`G`$-related concatenation components cannot be represented as projections of base three types $`p`$-orbits. The simplest of these cases gives the $`3`$-orbit of subgroup $`gr((12))<S_3`$. For this case we have the next right $`G`$-related $`2`$-orbits of $`gr((12))`$:

$$\begin{array}{cc}& \\ 1& 2\\ 2& 1\end{array},\begin{array}{cc}& \\ 1& 3\\ 2& 3\end{array}\text{ and }\begin{array}{cc}& \\ 2& 3\\ 1& 3\end{array}.$$

The existence of such decomposition of a $`(n,k)`$-cycle on condition $`k|n`$ leeds to some intricate structures as, for example, the automorphism group of Petersen graph (s. below).

##### Finite group permutation representation.

Let us to consider some examples with different properties of right permutation action. The $`2`$-orbit of subgroup $`gr((12))<S_3`$ shows an existence of cases with no non-trivial isomorphic right permutation action for $`k`$-orbits of non-normal subgroup. The example 95 (s. below) shows the existence of the right $`G`$-isomorphism for $`2`$-orbits $`\{12,21\}`$ and $`\{34,43\}`$ of normal subgroup $`gr((12)(34))`$ of group $`S_2S_2`$ that follows from proposition 68. The next example is a $`n`$-orbit of a group $`G`$ that is the regular permutation representation of $`S_3`$ in two assemblies.

###### Example 72

$$\begin{array}{ccc}\begin{array}{cccccc}& & & & & \\ 1& 2& 3& 4& 5& 6\\ & & & & & \\ 2& 1& 5& 6& 3& 4\\ & & & & & \\ 3& 4& 1& 2& 6& 5\\ & & & & & \\ 4& 3& 6& 5& 1& 2\\ & & & & & \\ 5& 6& 2& 1& 4& 3\\ & & & & & \\ 6& 5& 4& 3& 2& 1\end{array}\hfill & \text{and}& \hfill \begin{array}{cccc}& & \multicolumn{-1}{c}{}& & & \\ 1& 2& 3& 5& 4& 6\\ 2& 1& 5& 3& 6& 4\\ & & \multicolumn{-1}{c}{}& & & \\ 3& 4& 1& 6& 2& 5\\ 4& 3& 6& 1& 5& 2\\ & & \multicolumn{-1}{c}{}& & & \\ 5& 6& 2& 4& 1& 3\\ 6& 5& 4& 2& 3& 1\end{array}.\end{array}$$

The first table is partitioned relative to $`G`$-isomorphic $`2`$-subspaces and the second to $`S_n`$-isomorphic $`2`$-subspaces. The example shows no existence of a right $`G`$-isomorphism for $`2`$-rcycle $`\{12,21\}`$, but an existence of right $`S_6`$-isomorphism for this $`2`$-rcycle. This fact can be explained with next arguments: a subgroup defined by $`2`$-rcycle $`\{12,21\}`$ has the trivial normalizer and hence its $`2`$-orbits of left cosets are not necessitated to be $`G`$-isomorphic to the $`2`$-orbits of right cosets, on the one hand, but $`G`$ is regular and hence necessitates the existence of the isomorphic right action, on the other hand.

Given example shows the difference in properties of the right permutation action in various permutation representations of a finite group. We consider this difference and recall at first some facts from the finite group theory.

Let $`F`$ be a finite group, $`A<F`$, $`|F|/|A|=n`$ and $`\stackrel{}{L_n}`$, $`\stackrel{}{R_n}`$ be ordered partitions $`FA`$ and $`AF`$. It is known that every transitive permutation representation of $`F`$ is equivalent to the representation of $`F`$ given by $`n`$-orbits $`X_n^{}=\{f\stackrel{}{L_n}:fF\}`$ or $`X_n^{\prime \prime }=\{\stackrel{}{R_n}f:fF\}`$. It is also known that $`F`$ is homomorphic to its image $`Aut(X_n^{})`$ ($`Aut(X_n^{\prime \prime })`$) with the kernel of the homomorphism equal to a maximal normal subgroup of $`F`$ that is contained in $`A`$. Further we always assume that a finite group is isomorphic to its representation.

A maximal by inclusion subgroup $`A`$ of a finite group $`F`$ that contains no normal subgroup of $`F`$ we call a *md-stabilizer* of $`F`$ and the corresponding representation of $`F`$ we call a *md-representation*. A md-stabilizer $`A`$ of a finite group $`F`$ defines a minimal degree permutation representation of $`F`$ in the family of permutation representations of $`F`$ defined with subgroups of $`A`$. A maximal degree permutation representation of $`F`$ is correspondingly the permutation representation defined with trivial minimal subgroup given by the unit of the group and this representation is called a regular representation of $`F`$.

A finite group can have many (not conjugate) md-stabilizers. For example, $`S_5`$ contains a transitive md-stabilizer of order $`20`$ generated by permutations $`(12345)`$ and $`(1243)`$ and an intransitive md-stabilizer of order $`12`$ generated by permutations $`(123)(45)`$ and $`(23)`$. The $`n`$-orbits of these md-stabilizers are correspondingly:

###### Example 73

$$\begin{array}{ccc}\begin{array}{ccccc}& & & & \\ 1& 2& 3& 4& 5\\ 2& 3& 4& 5& 1\\ 3& 4& 5& 1& 2\\ 4& 5& 1& 2& 3\\ 5& 1& 2& 3& 4\\ & & & & \\ 5& 4& 3& 2& 1\\ 4& 3& 2& 1& 5\\ 3& 2& 1& 5& 4\\ 2& 1& 5& 4& 3\\ 1& 5& 4& 3& 2\\ & & & & \\ 1& 3& 5& 2& 4\\ 3& 5& 2& 4& 1\\ 5& 2& 4& 1& 3\\ 2& 4& 1& 3& 5\\ 4& 1& 3& 5& 2\\ & & & & \\ 4& 2& 5& 3& 1\\ 2& 5& 3& 1& 4\\ 5& 3& 1& 4& 2\\ 3& 1& 4& 2& 5\\ 1& 4& 2& 5& 3\end{array}\hfill & \text{ and }& \hfill \begin{array}{ccc}& & \multicolumn{-1}{c}{}& & \\ 1& 2& 3& 4& 5\\ 2& 3& 1& 4& 5\\ 3& 1& 2& 4& 5\\ & & \multicolumn{-1}{c}{}& & \\ 1& 2& 3& 5& 4\\ 2& 3& 1& 5& 4\\ 3& 1& 2& 5& 4\\ & & \multicolumn{-1}{c}{}& & \\ 1& 3& 2& 4& 5\\ 2& 1& 3& 4& 5\\ 3& 2& 1& 4& 5\\ & & \multicolumn{-1}{c}{}& & \\ 1& 3& 2& 5& 4\\ 2& 1& 3& 5& 4\\ 3& 2& 1& 5& 4\end{array}.\end{array}$$

The first md-stabilizer is a representation of group $`C_5C_4=C_4C_5`$. The representation of $`S_5`$ with this md-stabilizer has degree $`6`$ equal to maximal order of elements of $`S_5`$. The second md-stabilizer is a representation of group $`C_6C_2`$. The representation of $`S_5`$ with second md-stabilizer (as we shall see) is the automorphism group of Petersen graph.

Because of the property given in proposition 82, the special interest is presented by md-stabilizer of a finite group with the maximal order, which we call a *least degree stabilizer* or a *ld-stabilizer* of a finite group. The corresponding representation of a finite group we call a transitive least degree representation or *tld-representation*. That property urges also to consider a least degree intransitive representation or a *ild-representation* of a finite group, that for some groups, for example for $`C_6`$, has the degree less than the degree of tld-representation. So under a lowest degree representation or a *ld-representation* we shall understand the smallest degree representation among tld- and ild-representations.

The given consideration puts a question: *is there existing a finite group with two non-similar ld-representations?*. If there exists no two non-similar ld-representations, then the ld-representation is a full invariant of a finite group and hence the study of a finite group number invariants could be reduced to the study of ld-representation number invariants.

For a non-minimal degree representations a simple example, of the same degree non-similar permutation representations, is representations of $`S_4`$ on sets of right cosets of subgroups $`gr((12))`$ and $`gr((12)(34))`$. The first representation contains a stabilizer of $`2`$-tuple on a $`12`$-element set $`V`$ and the second contains a stabilizer of $`4`$-tuple on $`V`$.

Let $`\varphi :FS_n(V)`$. We shall denote the image $`\varphi (F)`$ of group $`F`$ by representation $`\varphi `$ as $`F(V)`$ and term $`F(V)`$ also as representation of $`F`$. The $`n`$-orbit of $`F(V)`$ we term for convenience also as representation of $`F`$.

##### One possible reformulation of the polycirculant conjecture.

Let $`F`$ be a finite group and $`A<F`$ be a md-stabilizer. Let $`F`$ contains a subgroup $`P`$ of a prime order $`p`$ that conjugates with no subgroup of $`A`$, then it follows that $`P`$ is a regular subgroup of a representation $`F(AF)`$ and hence $`p`$ divides $`n=|AF|`$.

So the polycirculant conjecture statements that if $`F(AF)`$ is a $`2`$-closed representation of a finite group $`F`$, then $`F`$ contains the corresponding subgroup $`P`$.

To all appearance this approach cannot be successful, because it lies out of the inside structure of a $`n`$-orbit.

##### Some properties of ld-representations.

###### Lemma 74

Let $`A_m`$ and $`B_l`$ be ld-representations, then the ld-representation of a group $`A_mB_l`$ has degree $`n=m+l`$.

The simplest example is

$$\begin{array}{cccc}& & & \\ 1& 2& 3& 4\\ 1& 2& 4& 3\\ & & & \\ 2& 1& 3& 4\\ 2& 1& 4& 3\end{array}.$$

###### Theorem 75

The ld-representation of a finite group $`F`$ is an ild-representation if and only if $`F`$ is a direct product.

Proof: If $`F`$ is a direct product, then the statement follows from lemma 74. So let $`X_n=X_{m+l}=X_mX_l`$ be an ild-representation of $`F`$, where $`X_m`$ and $`X_l`$ are transitive, then $`|X_n|/|X_m|`$ and $`|X_n|/|X_l|`$ greater than $`1`$. It follows that a stabilizer of $`m`$-tuple from $`X_m`$ and a stabilizer of $`l`$-tuple from $`X_l`$ are normal subgroups of $`F`$ (corollary 57) and elementwise commutative. $`\mathrm{}`$

###### Lemma 76

The ld-representation of a group $`F`$ is regular if and only if $`F`$ is not a direct product and has a trivial $`ld`$-stabilizer.

###### Corollary 77

The regular representation of cyclic $`p`$-group is ld-representation.

###### Corollary 78

Let $`C_n`$ be ld-representation of cyclic group $`C`$ of order $`p_1^{m_1}\mathrm{}p_q^{m_q}`$, where $`p_i`$ are prime, then $`C_n`$ is intransitive and $`n=p_1^{m_1}+\mathrm{}+p_q^{m_q}`$.

###### Lemma 79

Any finite group is a ld-stabilizer of some finite group.

Proof: Let $`A`$ be a finite group, then $`A`$ is a ld-stabilizer of a group $`F=gr(AB,d)`$, where a group $`B`$ is isomorphic to $`A`$, $`d`$ is an involution and $`dAB=ABd`$. $`\mathrm{}`$

The corresponding example gives the representation of dihedral group $`D_4`$:

$$\begin{array}{cccc}& & & \\ 1& 2& 3& 4\\ 1& 2& 4& 3\\ & & & \\ 2& 1& 3& 4\\ 2& 1& 4& 3\\ & & & \\ 3& 4& 1& 2\\ 3& 4& 2& 1\\ & & & \\ 4& 3& 1& 2\\ 4& 3& 2& 1\end{array}.$$

##### The following several sentences do the object, that we study, more visible.

###### Proposition 80

Let $`F`$ be a finite group and $`F(F)`$, $`F(V)`$ be two its images. Let $`\alpha _k(V),\beta _k(V)`$ be $`k`$-tuples from $`V^{(k)}`$ and $`l`$-tuples $`\alpha _l(F),\beta _l(F)`$ be their images from $`F^{(l)}`$, then $`\alpha _k(V)`$ and $`\beta _k(V)`$ have no intersection on $`V`$ if and only if $`\alpha _l(F)`$ and $`\beta _l(F)`$ have no intersection on $`F`$.

Proof: Let $`X_n`$ be a $`n`$-orbit of $`F(V)`$ and $`Y_m`$ ($`m=|F|`$) be a $`m`$-orbit of $`F(F)`$. The $`k`$-tuples $`\alpha _k(V)`$ and $`\beta _k(V)`$ are situated in $`X_n`$ and $`l`$-tuples $`\alpha _l(F)`$ and $`\beta _l(F)`$ are situated in $`Y_m`$. The statement follows from the method of reconstruction of $`Y_m`$ to $`X_n`$ that is a substitution of certain not intersected on $`F`$ $`(m/n)`$-tuples of $`Y_m`$ on certain not equal elements of $`V`$. $`\mathrm{}`$

From this proposition follows directly

###### Corollary 81

Let $`F`$ be a finite group, $`A<F`$ be a md-stabilizer, $`B<A`$, $`V=FB`$ and $`G=F(V)`$. Let $`|G|/|A|=l`$, $`|A|/|B|=k`$, $`kl=n`$, $`X_nOrb_n(G)`$, $`Y_nX_n`$ be a $`n`$-orbit of the subgroup $`A(V)<G`$ and $`L_n=GY_n=X_nA(V)`$. Let $`I_k=ABV`$, $`X_k=\widehat{p}(I_k)X_n`$ and $`Y_k=\widehat{p}(I_k)Y_n`$.

1. Let $`L_k=X_kA=GY_k=\widehat{p}(I_k)L_n`$, then classes of $`L_k`$ have no intersection on $`V`$ and hence $`L_k`$ is a partition of $`X_k`$.
2. Let $`Y_n^{}L_n`$, $`Y_k^{}=\widehat{p}(I_k)Y_n^{}`$ and $`Y_{nk}^{}=\widehat{p}(I_{nk})Y_n^{}`$, then $`Y_k^{}`$ and $`Y_{nk}^{}`$ have no intersection on $`V`$.

###### Proposition 82

Let $`F`$ be a finite group and $`p`$ be a prime divisor of $`|F|`$. Let $`\{n_1,n_2,\mathrm{}\}`$ be degrees of transitive components of the ld-representation of $`F`$, then $`pmax(n_i)`$.

Proof: The group $`F`$ contains a subgroup of order $`p`$. Any permutation $`gS_n`$ of prime order $`p`$ is decomposed in cycles of length either $`p`$ or $`1`$. $`\mathrm{}`$

From the definition of a minimal degree permutation representation follows

###### Proposition 83

Let a minimal degree permutation representation contains a regular element, then a subordinate non-minimal degree permutation representation contains a regular element too.

##### $`n`$-Orbits containing $`S_n`$-isomorphic $`𝐤`$-orbits.

###### Proposition 84

Let $`X_nOrb_n(G)`$, $`A<G`$, $`Y_nOrb_n(A)`$ and $`I_k,J_k`$ be $`k`$-subspaces. Let $`\widehat{p}(I_k)Y_n`$ be $`S_n`$-isomorphic to $`\widehat{p}(J_k)Y_n`$, then $`\widehat{p}(I_k)X_n`$ is not with necessary $`S_n`$-isomorphic to $`\widehat{p}(J_k)X_n`$.

Proof: The corresponding intransitive example is simply to construct:

$$\begin{array}{cccccc}& & & & & \\ 1& 2& 3& 4& 5& 6\\ 2& 1& 4& 3& 6& 5\\ & & & & & \\ 3& 4& 1& 2& 5& 6\\ 4& 3& 2& 1& 6& 5\end{array}.$$

Here $`2`$-suborbits $`\{12,21\}`$ and $`\{56,65\}`$ are $`S_n`$-isomorphic, but corresponding $`2`$-orbits have different power. The transitive example is not evident and is presented in $`n`$-orbit of the automorphism group of Petersen graph (s. below). $`\mathrm{}`$

###### Theorem 85

Non-minimal degree permutation representation of a finite group $`F`$ contains $`S_n`$-isomorphic $`k`$-orbits.

Proof: Let $`B<A<F`$, $`|FB|=n`$, $`|FA|=m`$ and $`|AB|=k`$. Let $`F(FA)`$ be minimal and $`F(FB)`$ be non-minimal degree permutation representations of a finite group $`F`$. Let $`X_n`$ be a $`n`$-orbit of $`F(FB)`$ and $`X_m^{}`$ be a $`m`$-orbit of $`F(FA)`$. Let $`Y_nX_n`$ be a $`n`$-orbit of $`A(FB)`$ and $`Y_m^{}X_m^{}`$ be a $`m`$-orbit of $`A(FA)`$. Let $`Z_nY_n`$ be a $`n`$-orbit of $`B(FB)`$ and $`Z_m^{}Y_m^{}`$ be a $`m`$-orbit of $`B(FA)`$. Let $`P<B`$ be a subgroup of a prime order $`p`$. Let $`T_nZ_n`$ be a $`n`$-orbit of $`P(FB)`$ and $`T_m^{}Z_m^{}`$ be a $`m`$-orbit of $`P(FA)`$.

Let $`Y_k`$, $`Z_kY_k`$ and $`T_kZ_k`$ be $`k`$-orbits of $`A(AB)`$, $`B(AB)`$ and $`P(AB)`$ correspondingly and let $`T_{nk}T_k=T_n`$.

The $`m`$-orbit $`T_m^{}`$, the $`n`$-orbit $`T_n`$ and the $`k`$-orbit $`T_k`$, can be represent as a concatenation of $`p`$-rcycles and multituples.

A $`p`$-rcycle from $`T_m^{}`$ generates $`k`$ $`p`$-rcycles in $`T_{nk}`$ that are associated with cyclic permutation of $`k`$ right cosets of $`A`$. But a multituple from $`T_m^{}`$ generates $`p`$-rcycles and multituple in $`T_k`$. The latter $`p`$-rcycles are existing because $`P<B<A`$ and hence the action of $`P`$ on $`T_k`$ permutes right cosets of $`B<A`$.

A $`p`$-rcycle from $`T_n`$, that is generated by a $`p`$-rcycle from $`T_m^{}`$, is evidently not $`F(FB)`$-isomorphic to a $`p`$-rcycle from $`T_n`$, that is generated by a multituple from $`T_m^{}`$. $`\mathrm{}`$

This situation is demonstrated on example 72.

This property can be also emerged in a md-representation of a finite group $`F`$. An example gives the group $`F=C_6C_2`$ in the next representation:

###### Example 86

$$\begin{array}{cccccc}& & & & & \\ 1& 6& 2& 5& 3& 4\\ 6& 1& 5& 2& 4& 3\\ & & & & & \\ 2& 1& 3& 6& 4& 5\\ 1& 2& 6& 3& 5& 4\\ & & & & & \\ 3& 2& 4& 1& 5& 6\\ 2& 3& 1& 4& 6& 5\\ & & & & & \\ 4& 5& 3& 6& 2& 1\\ 5& 4& 6& 3& 1& 2\\ & & & & & \\ 3& 4& 2& 5& 1& 6\\ 4& 3& 5& 2& 6& 1\\ & & & & & \\ 5& 6& 4& 1& 3& 2\\ 6& 5& 1& 4& 2& 3\end{array}.$$

It is seen that the $`2`$-rcycle $`\{25,52\}`$ does not belong to $`2`$-orbit of $`G`$, containing the $`2`$-rcycle $`\{16,61\}`$. This matrix is a md-representation of a finite group $`F`$, but not ld-representation, and it contains a submatrix that is a non-minimal degree representation of subgroup $`S_3<F`$.

In this example the $`p`$-subgroup does not belong to a stabilizer, but, using the construction given in lemma 79, we obtain the property for a $`p`$-subgroup (of order $`p`$) of a stabilizer of $`F`$.

The considered example suggests us the next property of $`n`$-orbits.

###### Proposition 87

Let $`I=\{I_k^i:i[1,l]\}`$ be a partition of $`V`$ on $`G`$-isomorphic $`k`$-subspaces and $`W=\{Co(I_k):I_kI\}`$.

Let $`Z_n`$ be a maximal subset of $`X_nOrb_n(G)`$ so that $`Co(\widehat{p}(I_k^i)Z_n)=W`$ for each $`i[1,l]`$.

Let $`A<Aut(Z_n)`$, $`Y_nZ_n`$ be a $`n`$-orbit of $`A`$, $`Y_k^1=\widehat{p}(I_k^1)Y_n`$ be the representation $`A(I_k^1)`$ and $`Y_k^2=\widehat{p}(I_k^2)Y_n`$ be $`S_{|A|}^k`$-orbit, then $`Z_n`$ is a non-minimal degree representation.

Proof: $`Z_n`$ is automorphic, because $`GZ_n`$ is a partition of $`X_n`$. From proposition 68 follows that $`A`$ contains no normal subgroup of $`Aut(Z_n)`$. Hence $`Z_n`$, that is defined on $`V`$, is isomorphic to a $`l`$-orbit $`Z_l^{}`$, that is defined on $`W`$ and obtained by the evident reduction of $`Z_n`$. $`\mathrm{}`$

The next example of a minimal degree representation of the group $`S_5S_2`$ contains $`S_n`$-isomorphic $`p`$-orbits in the case $`(p,n)=1`$.

###### Example 88

$$\begin{array}{ccccc}& & & & \\ 1& 2& 5& 3& 4\\ 1& 5& 2& 4& 3\\ & & & & \\ 2& 3& 1& 4& 5\\ 2& 1& 3& 5& 4\\ & & & & \\ 3& 4& 2& 5& 1\\ 3& 2& 4& 1& 5\\ & & & & \\ 4& 5& 3& 1& 2\\ 4& 3& 5& 2& 1\\ & & & & \\ 5& 1& 4& 2& 3\\ 5& 4& 1& 3& 2\end{array}.$$

This example shows an existence of $`n`$-orbit of a subgroup of order $`p`$, that contains $`S_n`$-isomorphic $`p`$-rcycles, but no $`S_p^p`$-orbit $`G`$-isomorphic to a $`p`$-rcycle. Here: $`2`$-rcycles $`\{25,52\}`$ and $`\{34,43\}`$ are $`S_n`$-isomorphic, $`S_p^p`$-orbits $`2354`$ and $`5423`$ are equal and hence $`G`$-isomorphic and $`2`$-rcycle $`\{25,52\}`$ is $`G`$-isomorphic to a $`2`$-orbit $`\{13,14\}`$. We shall see that properties of this $`5`$-orbit give an appearance to unconventional properties of the $`10`$-orbit of the Petersen graph automorphism group.

###### Theorem 89

Let a prime $`p`$ divides $`|G|`$ and does not divide $`n`$, then $`G`$ is a md-representation.

Proof: Let $`(\alpha _p)`$ be a cycle, $`X_p=G\alpha _p`$, $`L_p=G(\alpha _p)\alpha _p`$ and $`L_1=\widehat{p}(I_1)L_p`$, then $`L_1=Co(L_p)`$ is a covering of $`V`$ on $`G`$-isomorphic $`p`$-subsets. We consider two possible cases.

1. Let $`L_1=V`$, then $`G`$ is a primitive group and hence there exists no partition $`Q`$ of $`V`$ on $`G`$-isomorphic subsets for that $`G(Q)`$ would be a representation of $`G(V)`$. Indeed, if $`gG`$ is a permutation of order $`p`$, then $`gQQQ`$ for any partition $`Q`$. It contradicts proposition 80.
2. Let now $`L_1=Q`$, where $`Q`$ is a partition of $`V`$, then $`Q`$ consists of $`G`$-isomorphic classes. But in this case, because of transitivity $`G`$ and $`(n,p)=1`$, there exists a $`n`$-orbit of a $`p`$-subgroup whose projections on subspaces from $`Q`$ are $`G`$-isomorphic and hence $`X_n`$ does not contain $`S_n`$-isomorphic $`(n/|Q|)`$-orbits. Thus, accordingly to theorem 85, $`X_n`$ is a minimal degree permutation representation. $`\mathrm{}`$

An example of the second case representation of a finite group $`F`$ can be obtained from lemma 79, if to assign $`A=A_4`$ and $`p=3`$. The consideration of this example for $`A=S_3`$ and $`p=2`$ shows that the condition, $`p`$ does not divide $`n`$, is not of principal for the second case of theorem 89. We shall see that namely this situation takes place in the $`10`$-orbit of the Petersen graph automorphism group.

##### Conditions of $`k`$-closure and properties of $`k`$-closed groups.

###### Proposition 90

Let $`Y_kOrb_k(Aut(X_k))`$, then it is not follows that $`Aut(Y_k)=Aut(X_k)`$.

Proof: An example: $`X_2=\{12,23,34,41\}`$, $`Y_2=\{13,31,24,42\}`$. $`\mathrm{}`$

###### Proposition 91

Let $`k`$-orbits $`Y_k`$ and $`X_k`$ be isomorphic and $`Aut(X_k)=Aut(Y_k)`$, then it is not follows that $`Y_k=X_k`$.

Proof: An example: $`X_2=\{13,24\}`$, $`Y_2=\{14,23\}`$. $`\mathrm{}`$

###### Proposition 92

Let $`X_k`$ and $`Y_k`$ be isomorphic $`k`$-rorbits with the same automorphism group, then it is not follows that $`X_k=Y_k`$.

Proof: The $`2`$-orbits $`X_2=\widehat{p}(23)X_5`$ and $`Y_2=\widehat{p}(45)X_5`$ from example 88 represent such case. $`\mathrm{}`$

###### Lemma 93

Let $`X_n`$ be a $`n`$-orbit of a $`k`$-closed group $`G`$, $`A<G`$ and $`Y_nX_n`$ be a $`n`$-orbit of $`A`$. Let $`Y_k(I_k)=\widehat{p}(I_k)Y_n`$, $`B=_{(I_kI_n)}Aut(Y_k(I_k))`$, $`P_n=G(BY_n)`$ and classes of $`P_n`$ have no intersections, then $`A`$ is $`k`$-closed.

Proof: Let $`X_k(I_k)=\widehat{p}(I_k)X_n`$. It is given that $`G=_{(I_kI_n)}Aut(X_k(I_k))`$. Further we have: $`Aut(Y_n)<B`$, $`Y_nBY_n`$, $`Y_nBY_n`$ and $`X_n=GY_nGBY_n=P_n`$. Let $`Y_n`$ be not $`k`$-closed, then every class of $`GY_n`$ is not $`k`$-closed. As classes of $`P_n`$ have no intersections, then $`X_nP_n`$ and hence $`X_n`$ is not $`k`$-closed. Contradiction. $`\mathrm{}`$

###### Theorem 94

Let a transitive $`n`$-orbit $`X_n`$ contains $`S_n`$-isomorphic $`k`$-projections ($`k2`$), then $`X_n`$ is $`2`$-closed.

Proof: We have two possibilities:

1. There exists a subspace $`I_4=1234`$ so that $`4`$-orbit $`X(1234)=\widehat{p}(1234)X_n`$ is not $`2`$-closed and $`2`$-orbits $`X(12)=\widehat{p}(12)X_n`$ and $`X(34)=\widehat{p}(34)X_n`$ are $`S_n`$-isomorphic. Then $`3`$-orbits $`X(123)=\widehat{p}(123)X(1234)`$ and $`X(234)=\widehat{p}(234)X(1234)`$ are also not $`2`$-closed.

Let $`A(ijk\mathrm{})=Aut(X(ij))Aut(X(ik))Aut(X(jk))\mathrm{}`$, then $`Aut(123)X(1234)`$ and $`Aut(234)X(1234)`$ have to be $`2`$-closed and equal, i.e. $`Aut(123)=Aut(234)=Aut(1234)`$. But such equality (for transitive $`4`$-orbit $`X(1234)`$) is impossible, because $`Aut(123)`$ and $`Aut(234)`$ are conjugate subgroups of $`S_n`$ and hence are not equal.
2. There exists a subspace $`I_6=123456`$ so that $`6`$-orbit $`X(123456)=\widehat{p}(123456)X_n`$ is not $`2`$-closed, $`3`$-orbits $`X(123)=\widehat{p}(123)X_n`$ and $`X(456)=\widehat{p}(456)X_n`$ are $`S_n`$-isomorphic and not $`2`$-closed. Then $`Aut(123)X(123456)`$ and $`Aut(456)X(123456)`$ have to be $`2`$-closed and equal or $`Aut(123)=Aut(456)=Aut(123456)`$. This equality is also impossible for the same reason. $`\mathrm{}`$

Let $`X_n`$, $`Y_m`$ and $`Z_l`$ be three representations of a finite group $`F`$. Let $`n>m>l`$. It is of interest the relation between a $`k`$-closure property of $`Z_l`$, $`Y_m`$ and $`X_n`$.

It is evident that, if $`Y_m`$ is not $`1`$-closed, then $`X_n`$ is not $`1`$-closed too and $`Z_l`$ can be $`1`$-closed. And, if $`Y_m`$ is $`k`$-closed for $`k>1`$, then $`X_n`$ is $`k`$-closed too and $`Z_l`$ can be not $`k`$-closed.

##### Unconventional cyclic structure on $`k`$-orbits.

Now we shall consider one interesting property of the right permutation action on $`k`$-orbits that has no analogy in the group theory. The right automorphism action on a $`n`$-orbit $`X_n`$ of a group $`G`$ maps a $`k`$-subspace $`I_k`$ on an isomorphic $`k`$-subspace $`I_k^{}`$ and so $`X_k=\widehat{p}(I_k)X_n=\widehat{p}(I_k^{})X_n=X_k^{}`$. The latter equality generates an unconventional cyclic structure on a $`k`$-orbit $`X_k`$, that one can see on next examples:

###### Example 95

$$\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 1& 4& 3\\ & & & \\ 3& 4& 1& 2\\ 4& 3& 2& 1\end{array}\right)\left(\begin{array}{cc}B& B^{}\\ & \\ B^{}& B\end{array}\right)\text{ }\text{and}\text{ }\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\\ 1& 3& 2\\ 3& 1& 2\\ 2& 3& 1\\ 3& 2& 1\end{array}\right)\left(\begin{array}{cccc}1& 2& 2& 3\\ 2& 1& 1& 3\\ & & & \\ 2& 3& 3& 1\\ 1& 3& 3& 2\\ & & & \\ 3& 1& 1& 2\\ 3& 2& 2& 1\end{array}\right)\left(\begin{array}{cc}B_1& B_2\\ & \\ B_2& B_3\\ & \\ B_3& B_1\end{array}\right).$$

We have introduced the right permutation action on $`n`$-orbits as a permutation of coordinates of $`n`$-tuples. Of course, we can consider this action as the permutation $`n`$-tuples with the same result. Such interpretation of the right permutation action leads to next

###### Lemma 96

Let $`X_k`$ be a $`k`$-orbit of a group $`G`$, $`A<G`$, $`R_k=AX_k`$ be a partition of $`X_k`$ on $`k`$-orbits of right cosets of $`A`$ in $`G`$ and $`Y_n`$ be $`n`$-orbit of $`A`$. Then for any $`k`$-orbit $`Y_kR_k`$ there exists a subspace $`I_k`$ so that $`Y_k=\widehat{p}(I_k)Y_n`$.

Proof: It follows from $`A\alpha _n=Y_n`$ for $`\alpha _nY_n`$ and $`A\alpha _kR_k`$ for $`\alpha _kX_k`$. $`\mathrm{}`$

###### Theorem 97

Let $`X_n`$ be a $`n`$-orbit of a group $`G`$, $`I_k,I_k^{}`$ be isomorphic subspaces, and $`X_{2k}=\widehat{p}(I_kI_k^{})X_n=X_kX_k`$. Let $`A<G`$, $`R_{2k}=AX_{2k}`$ and $`R_k=AX_k`$, then $`R_{2k}`$ can be partition in cycles on classes of $`R_k`$.

Proof: It follows from lemmas 96 and 36. $`\mathrm{}`$

Namely this property we can see on examples.

###### Remark 98

Let $`I_k^1`$, $`I_k^2`$ and $`I_k^3`$ be isomorphic subspaces of a $`n`$-orbit $`X_n`$, then $`\widehat{p}(I_k^1)X_n=\widehat{p}(I_k^2)X_n=\widehat{p}(I_k^3)X_n`$. But on the condition it does not follow that $`\widehat{p}(I_k^1I_k^2)X_n=\widehat{p}(I_k^2I_k^3)X_n`$.

Hence the corresponding cycle structure on $`lk`$-orbits of right cosets of a subgroup does not exist with necessary for $`l>2`$. This fact represents the difference between $`2`$-closed groups and $`m`$-closed groups for $`m>2`$.

###### Proposition 99

Let $`X_{2k}Orb_{2k}(G)`$, $`A<G`$, $`R_{2k}=AX_{2k}`$, $`Y_k^1`$ and $`Y_k^2`$ be isomorphic $`k`$-orbits of a subgroup $`A`$, $`Y_{2k}=Y_k^1Y_k^2R_{2k}`$ and $`C_{2k}R_{2k}`$ be a cycle containing $`Y_{2k}`$. Let the set $`Z_{2k}=C_{2k}`$ is a $`(2k)`$-orbit of some subgroup $`B<G`$, then $`A`$ is a normal subgroup of $`B`$.

Proof: Since $`Y_k^1`$ and $`Y_k^2`$ are isomorphic, $`k`$-orbits $`Y_k^i`$, that form the cycle $`C_{2k}`$, are $`k`$-orbits of left and right cosets of $`A`$ in $`B`$. Then statement follows from lemma 69. $`\mathrm{}`$

## 3 Correspondence between $`k`$-orbits and their automorphism
groups

###### Lemma 100

Every cycle $`cG`$ of length $`lk`$ corresponds to a $`(l,k)`$-cycle $`C_{lk}`$ of some $`k`$-orbit $`X_kOrb_k(G)`$.

Proof: If $`c=(\alpha _l)`$, then $`l`$-orbit $`X_l=G\alpha _l`$ contains $`l`$-rcycle $`rC_l=gr(c)\alpha _l`$. The $`X_k`$ and $`C_{lk}`$ are corresponding $`k`$-projections of $`X_l`$ and $`rC_l`$. $`\mathrm{}`$

For $`k>l`$ the counterexample is given by the cycle $`(56)`$ in fourth case of example 7, where there exists no $`(2,3)`$-cycle for subautomorphism $`(56)`$.

The reverse statement for $`k`$-orbits of not $`k`$-closed groups is not correct. An example is $`2`$-orbit of $`A_4`$ that contains $`(4,2)`$-cycle related to no subautomorphism of $`A_4`$.

For $`k`$-closed groups the reverse statement is also not correct. This shows an example of $`2`$-closed group that is defined by $`2`$-orbit $`X_2=\{14,25,36,41,52,63\}`$. The group $`Aut(X_2)`$ has a $`2`$-orbit $`X_2^{}=\{12,13,15,16,21,24,23,26,32,35,31,34,42,45,43,46,51,54,53,56,62,65,61,64\}`$. The automorphism group of $`2`$-suborbit $`\{12,13,15,16\}X_2^{}`$ contains a cycle $`(2536)`$ that does not belong to $`Aut(X_2^{})`$. We can see that the possibility for construction of this counterexample gives a concatenation of $`S_4^1`$-orbit with $`(4,1)`$-multituple. But $`X_2^{}`$ contains a suborbit $`\{12,24,43,31\}`$ that is a projection of a $`4`$-rcycle and also is not a $`2`$-orbit of a subgroup of $`Aut(X_2^{})`$. In latter case the length $`l`$ of a cycle $`(1243)`$ is not prime first and does not divide degree $`n`$ second. For a prime $`l`$ that does not divide $`|Aut(X_2^{})|=48`$ we have the next counterexample: an automorphic $`2`$-subset $`\{13,32,24,45,51\}X_2^{}`$.

### 3.1 The local property of $`k`$-orbits

The trivial case of reverse statement we obtain from corollary 50. For disclosing of a non-trivial local property of an automorphism group $`k`$-orbits we have to consider the case, where $`(p,k)`$-subset of a $`k`$-orbit $`X_k`$ is a $`k`$-projection of $`p`$-rcycle for $`p`$ being a prime divisor of $`|Aut(X_k)|`$. We shall write further a $`k`$-projection of $`l`$-rcycle for $`kl`$ as *$`(l,k)`$-rcycle* $`rC_{lk}`$.

###### Theorem 101

Let $`X_k`$ be automorphic, $`pk`$ be a prime divisor of $`|Aut(X_k)|`$ and $`rC_{pk}X_k`$ be a $`(p,k)`$-rcycle, then $`Aut(rC_{pk})<<Aut(X_k)`$.

Proof: Let $`L_k=Aut(X_k)rC_{pk}`$ and $`|L_k|p`$ divides $`|Aut(X_k)|`$, then the statement follows from theorem 51. Let $`|L_k|p>|Aut(X_k)|`$, then $`|L_k|=|Aut(X_k)|`$ and hence $`L_k`$ can be partition on subsets $`L_k^i`$, $`i[1,p]`$ so that $`|L_k^i|p=|Aut(X_k)|`$. Since subsets $`L_k^i`$ have no intersections, there exist subgroups $`A_i<Aut(X_k)`$ so that $`A_iL_k^i=L_k^i`$. It follows that $`|L_k|p`$ divides $`|Aut(X_k)|`$ and hence $`|L_k|p=|Aut(X_k)|`$. $`\mathrm{}`$

The theorem 101 and lemma 46 give a possibility for the reconstruction of subautomorphisms of $`k`$-orbit through its symmetry properties.

The next statement gives the relation between automorphism group of a $`k`$-orbit and automorphism group of its $`k`$-suborbit.

###### Proposition 102

Let $`X_k`$ be a $`k`$-orbit and $`Y_kX_k`$ be a $`k`$-orbit of a subgroup $`A=Aut(Y_k;V)Aut(X_k)`$, then $`Aut(Y_k)<<A<Aut(X_k)`$ if and only if $`Aut(Y_k)<<_{(Z_kAX_k)}Aut(Z_k;V)`$.

Proof: The statement follows from evident equality $`A=_{(Z_kAX_k)}Aut(Z_k;V)`$. $`\mathrm{}`$

## 4 Primitivity and imprimitivity.

Below a group $`G`$ is transitive.

Let $`X_k`$ be a $`k`$-rorbit, $`Y_kX_k`$ be a $`k`$-subrorbit, $`\alpha _kY_k`$ and $`Co(Y_k)=Co(\alpha _k)`$, then $`L_k=GY_k`$ is a partition of $`X_k`$ (lemma 47), but classes of $`L_k`$ can be intersected on $`V`$. We shall call a $`k`$-rorbit $`X_k`$ for $`k<n`$ *$`V`$-coherent*, if $`Co(X_k)=V`$ and *$`V`$-incoherent* if $`Co(X_k)`$ is a partition of $`V`$. We shall write simply coherent and incoherent, instead of $`V`$-coherent and $`V`$-incoherent, if it will be clear, what a set we consider.

###### Proposition 103

The automorphism group of an incoherent $`k`$-rorbit is imprimitive.

###### Corollary 104

A group $`G`$ is imprimitive if and only if it contains an incoherent $`k`$-rorbit.

###### Corollary 105

Non-minimal degree representations are imprimitive.

The automorphism group of a coherent $`k`$-rorbit can be imprimitive. The example is the $`2`$-rorbit $`\{13,31,24,42,14,41,23,32\}`$.

Let a coherent (incoherent) $`k`$-rorbit $`X_k`$ contains no $`V`$-coherent and no $`V`$-incoherent $`k`$-subrorbit, then $`X_k`$ can be called an *elementary coherent* (*elementary incoherent*) $`k`$-rorbit.

###### Lemma 106

The automorphism group of an elementary coherent $`k`$-rorbit is primitive.

###### Corollary 107

The group $`G`$ is primitive if and only if it contains an elementary $`V`$-coherent $`k`$-subrorbit.

A maximal $`k`$-subrorbit $`Y_k`$ of a $`k`$-rorbit $`X_k`$, that is a structure element of coherent (incoherent) $`k`$-subrorbits, we call a *$`k`$-block*.

Let $`Y_k`$ be a $`k`$-block of an incoherent $`k`$-rorbit $`X_k`$, then $`U=Co(Y_k)`$ is a $`1`$-block or $`k`$-element block of an imprimitive group $`G`$ in conventional definition.

Let us to give some examples of coherent and incoherent $`k`$-rorbits:

1. A $`2`$-orbit $`X_2`$ of $`S_3`$ is elementary coherent and a $`2`$-rcycle from $`X_2`$ is a $`2`$-block.
2. $`2`$-orbit of $`C_5C_2`$ is elementary coherent. This group contains $`S_5`$-isomorphic elementary coherent $`2`$-rorbits.
3. A $`2`$-orbit of $`A_5`$ is coherent but not elementary coherent. It contains an elementary coherent $`2`$-orbit of $`C_5C_2`$. A $`3`$-orbit of $`A_5`$ is elementary coherent and contains elementary coherent suborbits on $`4`$-element subsets of $`V`$.
4. All $`2`$-orbits of $`C_2C_2`$ and two from six $`2`$-orbits of $`D_4`$ are elementary incoherent. Other four $`2`$-orbits of $`D_4`$ are coherent.

###### Proposition 108

Let $`p`$ be prime and $`X_p`$ be an elementary incoherent $`p`$-rorbit, then there exists a subgroup $`A<Aut(X_p)`$ of order $`p`$ for that classes of a partition $`R_p=AX_p`$ are $`p`$-orbits of the base type, i.e. they are either $`p`$-rcycles, or $`S_p^p`$-orbits or $`p`$-tuples.

Proof: An elementary incoherent $`p`$-rorbit consists of not intersected on $`V`$ $`p`$-rcycles. $`\mathrm{}`$

The reverse statement:

###### Lemma 109

Let $`p`$ be prime, $`X_p`$ be a $`p`$-rorbit and $`rC_pX_p`$ be a $`p`$-rcycle that is a $`p`$-orbit of a subgroup $`A<Aut(X_p)`$ of order $`p`$. Let classes of $`R_p=AX_p`$ be $`p`$-orbits of the base type, then $`Aut(X_p)`$ is imprimitive.

Proof: Let the statement is not correct and $`Aut(X_p)`$ be primitive, then $`L_p=Aut(X_p)rC_p`$ contains intersected on $`V`$ classes and hence there exists a class of $`R_p`$ that has a $`(p,m<p)`$-multituple as a concatenation component. Contradiction. $`\mathrm{}`$

In the next example: $`L_1=\{\{124\},\{235\},\{346\},\{451\},\{562\},\{613\}\}`$, we see that $`L_1=V=[1,6]`$, where $`k=3`$ divides $`n=6`$, but the corresponding $`3`$-set $`X_3=\{124,241,421,\mathrm{}\}`$ is not automorphic.

###### Theorem 110

Let $`X_k`$ be an elementary coherent $`k`$-rorbit, then $`\neg (k|n)`$.

Proof: The statement is correct for $`n`$ being a prime, because of $`k<n`$, so we assume that $`n`$ is not prime. Let the statement is not correct for some $`k`$, then it is not correct also for a prime divisor $`p`$ of $`k`$. So we assume that $`k=p`$ is a prime. Let $`Y_pX_p`$ be a $`p`$-rcycle that is a $`p`$-orbit of a subgroup $`A<Aut(X_p)`$ of order $`p`$, $`R_p=AX_p`$ and $`L_p=Aut(X_p)Y_p`$. Since by hypothesis classes of $`L_p`$ are intersected on $`V`$, then $`R_p`$ contains classes that have a $`(p,l<p)`$-multituple as a concatenation component. Let $`X_nOrb_n(Aut(X_p))`$ and $`Y_nX_n`$ be a $`n`$-orbit of $`A`$, then $`Y_n`$ is a concatenation of (not with necessary $`Aut(X_p)`$-isomorphic) $`p`$-rcycles and a $`(p,pr)`$-multituple. Let $`I_{pr}`$ be a subspace defining $`(p,pr)`$-multituple, then, accordingly to lemma 63, the $`pr`$-orbit $`X_{pr}=\widehat{p}(I_{pr})X_n`$ is a $`pr`$-rorbit and hence $`l|pr`$. Another, the subspace $`I_{pr}`$ is a concatenation of $`m=pr/l`$ $`Aut(X_p)`$-isomorphic subspaces $`I_l^i`$ ($`i[1,m]`$). It follows that $`R_p`$ contains $`m`$ $`Aut(X_p)`$-isomorphic classes and that $`Aut(X_p)`$ contains a subgroup $`B`$ that acts transitive on the system of these $`m`$ classes. It follows that $`R_p`$ and hence $`X_p`$ can be partition on $`m`$ $`Aut(X_p)`$-isomorphic classes. Let $`L_p^{}=L_pR_p`$ be this partition of $`X_p`$ on $`m`$ $`Aut(X_p)`$-isomorphic classes, then classes of $`L_p^{}`$ are $`p`$-orbits of a normal subgroup of $`Aut(X_p)`$ and cannot be intersected on $`V`$. Hence $`X_p`$ is not elementary coherent $`p`$-rorbit. Contradiction. $`\mathrm{}`$

## 5 Petersen graph

Here we consider the properties of $`n`$-orbits that are not visible from the group theory and therefore had hindered to solve the polycirculant conjecture. It is the cases, where $`p|n`$, but there exists no transitive and imprimitive subgroup of order $`p`$ and therefore there exists no subgroup of order $`p`$, whose $`n`$-orbits could be represented as a concatenation of $`(p,p)`$-orbits of base type.

The simplest example is a $`(n=6)`$-orbit of a group $`G=S_3C_2`$.

###### Example 111

$$\begin{array}{cccccc}& & & & & \\ 1& 2& 3& 4& 5& 6\\ 2& 1& 3& 5& 4& 6\\ & & & & & \\ 1& 3& 2& 4& 5& 6\\ 3& 1& 2& 5& 4& 6\\ & & & & & \\ 2& 3& 1& 5& 6& 4\\ 3& 2& 1& 6& 5& 4\\ & & & & & \\ 4& 5& 6& 1& 2& 3\\ 5& 4& 6& 2& 1& 3\\ & & & & & \\ 4& 5& 6& 1& 3& 2\\ 5& 4& 6& 3& 1& 2\\ & & & & & \\ 5& 6& 4& 2& 3& 1\\ 6& 5& 4& 3& 2& 1\end{array}.$$

It is seen that the pair $`12`$ is $`G`$-isomorphic to $`45`$, but not $`G`$-isomorphic to $`36`$, so $`6`$-orbit of a subgroup $`gr((12)(45))`$ cannot be represented as a concatenation of $`p`$-orbits of base type. We shall say that this subgroup of a prime order and its $`n`$-orbit are *undecomposable*. Nevertheless the given group contains a *decomposable* (on the $`(p,p)`$-orbits of the base type) subgroup $`gr((14)(25)(36))`$, where $`\{14\},\{25\},\{36\}`$ are incoherent $`2`$-blocks of a corresponding imprimitive subgroup of $`G`$.

The Petersen graph gives an example, where for the least prime divisor $`p=2`$ of the degree $`n=10`$ there exists no decomposable subgroup with incoherent $`2`$-blocks. From here follows unconventional properties of the automorphism group of this graph. The automorphism group of Petersen graph is a representation $`G`$ of $`S_5`$ on $`10`$-element set $`V`$. It is a representation of $`S_5`$ with right (left) cosets of a subgroup of order $`12`$ represented in example 73. This representation can be also obtained by action of $`S_5`$ on unordered pairs from the set $`V^{}=\{1,2,3,4,5\}`$, where $`V=\{1=\{1,2\},2=\{1,3\},\mathrm{},0=\{4,5\}\}`$.

The following matrix is a $`10`$-orbit $`Y_{10}`$ of a transitive, imprimitive subgroup of $`G`$ (that is isomorphic to a first subgroup from example 73).

###### Example 112

$$\begin{array}{ccccccccccc}& & & & & & & & & & \\ 12& 23& 34& 45& 15& 14& 24& 25& 35& 13& \\ & & & & & & & & & & \\ & & & & & & & & & & \\ 1& 5& 8& 0& 4& 3& 6& 7& 9& 2& e\\ 5& 8& 0& 4& 1& 7& 9& 2& 3& 6& (12345)\\ 8& 0& 4& 1& 5& 2& 3& 6& 7& 9& (13524)\\ 0& 4& 1& 5& 8& 6& 7& 9& 2& 3& (14253)\\ 4& 1& 5& 8& 0& 9& 2& 3& 6& 7& (15432)\\ & & & & & & & & & & \\ 3& 6& 7& 9& 2& 4& 0& 8& 5& 1& (2453)\\ 6& 7& 9& 2& 3& 8& 5& 1& 4& 0& (1435)\\ 7& 9& 2& 3& 6& 1& 4& 0& 8& 5& (1254)\\ 9& 2& 3& 6& 7& 0& 8& 5& 1& 4& (1523)\\ 2& 3& 6& 7& 9& 5& 1& 4& 0& 8& (1342)\\ & & & & & & & & & & \\ 4& 0& 8& 5& 1& 2& 9& 7& 6& 3& (25)(34)\\ 0& 8& 5& 1& 4& 7& 6& 3& 2& 9& (15)(24)\\ 8& 5& 1& 4& 0& 3& 2& 9& 7& 6& (23)(14)\\ 5& 1& 4& 0& 8& 9& 7& 6& 3& 2& (45)(13)\\ 1& 4& 0& 8& 5& 6& 3& 2& 9& 7& (12)(35)\\ & & & & & & & & & & \\ 2& 9& 7& 6& 3& 1& 5& 8& 0& 4& (2354)\\ 9& 7& 6& 3& 2& 8& 0& 4& 1& 5& (1325)\\ 7& 6& 3& 2& 9& 4& 1& 5& 8& 0& (1534)\\ 6& 3& 2& 9& 7& 5& 8& 0& 4& 1& (1243)\\ 3& 2& 9& 7& 6& 0& 4& 1& 5& 8& (1452)\end{array}$$

and the reassembling of this example:

###### Example 113

$$\begin{array}{ccccccccccc}& & & & & & & & & & \\ 12& 15& 14& 13& 23& 35& 34& 45& 24& 25& \\ & & & & & & & & & & \\ & & & & & & & & & & \\ 1& 4& 3& 2& 5& 9& 8& 0& 6& 7& e\\ 4& 1& 2& 3& 0& 6& 8& 5& 9& 7& (25)(34)\\ & & & & & & & & & & \\ 5& 1& 7& 6& 8& 3& 0& 4& 9& 2& (12345)\\ 1& 5& 6& 7& 4& 9& 0& 8& 3& 2& (12)(35)\\ & & & & & & & & & & \\ 8& 5& 2& 9& 0& 7& 4& 1& 3& 6& (13524)\\ 5& 8& 9& 2& 1& 3& 4& 0& 7& 6& (45)(13)\\ & & & & & & & & & & \\ 0& 8& 6& 3& 4& 2& 1& 5& 7& 9& (14253)\\ 8& 0& 3& 6& 5& 7& 1& 4& 2& 9& (23)(14)\\ & & & & & & & & & & \\ 4& 0& 9& 7& 1& 6& 5& 8& 2& 3& (15432)\\ 0& 4& 7& 9& 8& 2& 5& 1& 6& 3& (15)(24)\\ & & & & & & & & & & \\ 3& 2& 4& 1& 6& 5& 7& 9& 0& 8& (2453)\\ 2& 3& 1& 4& 9& 0& 7& 6& 5& 8& (2354)\\ & & & & & & & & & & \\ 6& 3& 8& 0& 7& 4& 9& 2& 5& 1& (1435)\\ 3& 6& 0& 8& 2& 5& 9& 7& 4& 1& (1452)\\ & & & & & & & & & & \\ 7& 6& 1& 5& 9& 8& 2& 3& 4& 0& (1254)\\ 6& 7& 5& 1& 3& 4& 2& 9& 8& 0& (1243)\\ & & & & & & & & & & \\ 9& 7& 0& 4& 2& 1& 3& 6& 8& 5& (1523)\\ 7& 9& 4& 0& 6& 8& 3& 2& 1& 5& (1534)\\ & & & & & & & & & & \\ 2& 9& 5& 8& 3& 0& 6& 7& 1& 4& (1342)\\ 9& 2& 8& 5& 7& 1& 6& 3& 0& 4& (1325)\end{array}$$

It can be seen that there exists no partition of $`2`$-projection $`\widehat{p}(14)Y_{10}`$ on not intersected on $`V`$ classes, but this covering of $`V`$ with $`2`$-tuples can be partition in two not intersected coverings: $`\{14,15,58,40,08\}`$ and $`\{23,36,29,79,67\}`$ that form elementary coherent $`2`$-orbits on corresponding two $`5`$-element subsets of $`V`$. This case is similar to we could see on example 88.

The following example of a $`(2,10)`$-orbit

$$\begin{array}{cccccccccc}& & & & & & & & & \\ 24& 35& 12& 14& 13& 15& 23& 25& 45& 34\\ & & & & & & & & & \\ & & & & & & & & & \\ 6& 9& 1& 3& 2& 4& 5& 7& 0& 8\\ 9& 6& 3& 1& 4& 2& 7& 5& 8& 0\end{array}$$

contains $`S_{10}`$ isomorphic $`2`$-rcycles $`\{69,96\}`$ and $`\{13,31\}`$, but the corresponding two projections of $`X_{10}`$ are not $`S_{10}`$ isomorphic, because the $`2`$-orbit $`X_2(69)`$ consists of $`30`$ pairs and $`2`$-orbit $`X_2(13)`$ consists of $`60`$ pairs. It is a transitive realization of the property of example from proposition 84.

###### Remark 114

One can see that given properties of $`X_n`$ cannot be obtained in the group theory, because they are properties of the internal structure of $`X_n`$. Of course, the internal structure of $`X_n`$ characterizes the group and therefore its properties are also group properties. But these properties of a group lie out the group algebra that characterizes $`X_n`$ as whole.

## 6 The proof of the polycirculant conjecture

### 6.1 The proof of lemma 5

The proof of lemma 5 follows from

###### Lemma 115

Let $`q`$ be the greatest prime divisor of $`n`$, then $`G`$ contains a transitive, imprimitive subgroup with incoherent $`q`$-blocks.

Proof: Let the statement is not correct, then every $`q`$-rorbit $`X_q(I_q)`$ contains a coherent $`q`$-subrorbit $`Y_q(I_q)`$ on some automorphic $`k`$-subspace $`I_k`$, where $`k`$ is a divisor of $`n`$ greater than $`q`$, $`I_qI_k`$ and $`X_k(I_k)`$ is an incoherent $`k`$-rorbit. Let $`p`$ be a prime divisor of $`k`$, then it follows that $`p<q`$ and hence there exists an automorphic $`p`$-subspace $`I_pI_q`$. Therefore there exists a coherent $`p`$-subrorbit $`Y_p(I_p)`$ of a $`p`$-rorbit $`X_p(I_p)`$ on the $`q`$-subspace $`I_q`$. Since $`q|n`$, classes of the partition $`L_p=GY_p(I_p)`$ of $`X_p(I_p)`$ are not intersected on $`V`$ and hence $`X_q(I_q)`$ can not contain a coherent $`q`$-subrorbit $`Y_q(I_q)`$ on the $`k`$-subspace $`I_k`$. Contradiction. $`\mathrm{}`$

### 6.2 The proof of theorem 4

Let $`G`$ be a transitive group, then it contains a transitive, imprimitive subgroup. So we can assume that $`G`$ is imprimitive. Then for some prime divisor $`p`$ of $`n`$ there exists a partition $`I=\{I_p^i:i[1,l]\}`$ of $`V`$ on $`G`$-isomorphic, automorphic $`p`$-subspaces. Let $`X_n`$ be a $`n`$-orbit of $`G`$, $`X_p=\widehat{p}(I_p^i)X_n`$ and $`X_{2p}^{ij}=\widehat{p}(I_p^iI_p^j)X_n=X_pX_p`$. Accordingly to corollary 35 $`X_{2p}^{ij}=_t(X_p\stackrel{\varphi _t(i,j)}{}X_p)L_p(i,j)`$ for some maps $`\{\varphi _t(i,j)\}`$. It follows that the action of any cycle of length $`p`$, that is generated with some $`p`$-rcycle from $`X_p`$, on partitions $`L_p(i,j)`$ generates cycles of length $`p`$ that are again connected with $`p`$-rcycles from $`X_p`$. Hence $`G`$ contains a regular permutation of order $`p`$.

## 7 Some applications of $`k`$-orbit theory

### 7.1 Solvability of groups of odd order

Now we shall show that the $`k`$-orbit theory gives a simple proof of the W. Feit, J.G. Thompson theorem: Solvability of groups of odd order .

In this section we do not difference between a finite group and its $`ld`$-representation. Also we assume that a finite group is not a direct product.

###### Lemma 116

Let $`X_kOrb_k(G)`$ be an incoherent $`k`$-orbit, then $`G`$ is not a simple group.

Proof: Let $`Y_kX_k`$ be a $`k`$-block and $`L_k=Aut(X_k)Y_k`$, then it is evident that a concatenation of classes from $`L_k`$ is a $`n`$-orbit of a normal subgroup $`HAut(X_k)=Aut(L_k)`$ and that every transitive subgroup $`G<Aut(L_k)`$ has non-trivial intersection with $`H`$. $`\mathrm{}`$

###### Corollary 117

Let $`G`$ be a (non-cyclic) simple group, then it is (non-trivial) primitive.

###### Theorem 118

Any primitive group $`G`$ contains an involution.

Proof: Let $`n`$ be odd, then there exist odd numbers $`k<ln`$, so that $`(k,l)=1`$ and there exist automorphic subspaces $`I_kI_l`$. If $`r=[l/k]`$ is odd, then $`m=lrk`$ is even and there exists an automorphic subspace $`I_m`$ (lemma 63). If $`r`$ is even, then $`m`$ is odd and, because of primitivity of $`G`$, we can choose $`l:=k`$ and $`k:=m`$, if $`(k,m)=1`$, or else $`l:=l`$ and $`k:=m`$. $`\mathrm{}`$

###### Corollary 119

Let $`G`$ be a (non-cyclic) simple group, then it contains an involution.

###### Corollary 120

Let $`G`$ be a group of odd order, then it is an imprimitive and hence solvable group.

### 7.2 A full invariant of a finite group

Here we shall discuss the problem of a full invariant of a finite group $`F`$ and assume that $`F`$ is not a direct product.

At first we can note that, if the ld-representation $`G`$ of $`F`$ is unique accurate to similarity, then a full invariant of $`F`$ is defined by a full invariant of $`G`$. Then we have two cases: $`G`$ is primitive and $`G`$ is imprimitive.

#### 7.2.1 Let $`G`$ be primitive

###### Proposition 121

Let $`\neg (l|n)`$, $`I_l`$ be an automorphic subspace and $`k=nl[n/l]`$, then

1. $`k`$ divides $`|G|`$;
2. there exists an automorphic $`k`$-subspace $`I_k`$;
3. a subgroup $`Stab(I_k)`$ has non-trivial normalizer in $`G`$.

Proof: The statements follows directly from lemmas 63 and 57. $`\mathrm{}`$

###### Proposition 122

Let $`\neg (k|n)`$ and $`X_k`$ be a $`k`$-rorbit, then $`X_k`$ contains an elementary $`V`$-coherent $`k`$-suborbit.

Proof: The statement follows from the definition of an elementary $`V`$-coherent $`k`$-orbit. $`\mathrm{}`$

So we see that $`|G|`$ and $`n`$ are high dependent and in general the degree $`n`$ allows to define whether there can exist a group $`G`$ of order $`\nu `$. Also an elementary $`U`$-coherent $`k`$-suborbit on every possible automorphic subset $`UV`$ is unique accurate to similarity.

All these facts suggest us the hypothesis that $`|G|`$ and $`n`$ could be a full invariant of $`G`$ in the considered case.

#### 7.2.2 Let $`G`$ be imprimitive

Let $`k`$ be a maximal automorphic divisor of $`n`$, then there exists an incoherent $`k`$-rorbit $`X_k`$ of $`G`$. Let $`Y_kX_k`$ be a $`k`$-block and $`L_k=Aut(X_k)Y_k=Aut(L_k)Y_k`$, then $`G<Aut(L_k)`$, $`L_k=GY_k`$ and $`Y_k`$ is a $`k`$-orbit of a maximal normal subgroup $`HG`$, because of lemma 116.

Let us to assume that we know $`Y_k`$, $`|G|`$ and $`n`$. It gives us the next information: $`|L_k|=n/k`$, $`|X_k|=|Y_k||L_k|`$, $`|H|=|G|/|L_k|`$ and $`|Stab(I_k)|=|G|/|X_k|=|H|/|Y_k|`$. In addition we know that $`n`$-orbit $`X_n`$ of $`G`$ is a $`|L_k|\times |L_k|`$ matrix $`M`$, whose elements are multi-classes of $`L_k`$ and which gives a regular representation of a factor group $`\mathrm{\Phi }=G/H`$. Since $`H`$ is a maximal normal subgroup, hence $`\mathrm{\Phi }`$ is a simple group.

Let $`\mathrm{\Phi }`$ be not a cyclic group, then it is not a ld-representation. But from here follows that $`G`$ is not a ld-representation too. This contradiction shows us that $`\mathrm{\Phi }`$ is always a cyclic group.

In order to give a full description of the group $`G`$ we have to find the elements of matrix $`M`$. Let $`L_k=\{Y_k^i:i[1,p]\}`$ and $`\mathrm{\Phi }=gr((1\mathrm{}p))`$, then we know that $`M_{ij}=Y_k^r`$, where $`r=i+j1(modp)`$. One of possible construction of $`M`$ is obtained as next. Every element $`M_{ij}`$ is obtained from the element $`M_{1j}`$ by permutation of columns and every element $`M_{1j}`$ is obtained from the element $`M_{11}`$ by permutation of lines. The columns of the element $`Mij`$ are permutated relative to the columns of the element $`M_{1j}`$ with automorphisms of $`M_{1j}`$ that are similar to automorphisms of $`M_{11}`$. The lines of the element $`M_{1j}`$ are permutated relative to lines of the element $`M_{11}`$ on the condition to maintain the automorphism property of $`M_{11}`$.

So, for obtaining of a full number invariant in this imprimitive case it wants to find the number invariants that allow to calculate corresponding $`p^21`$ permutations.

Now we consider the properties of $`Y_k`$.

###### Lemma 123

$`Aut(Y_k)`$ is imprimitive.

Proof: Let $`Aut(Y_k)`$ be primitive, then $`Y_k`$ contains an elementary coherent $`q`$-subrorbit for some prime $`q<k`$. From here follows that permutations generating elements of matrix $`M`$ are trivial and hence $`G`$ is a direct product. Contradiction. $`\mathrm{}`$

###### Corollary 124

$`Aut(Y_k)`$ is regular.

###### Corollary 125

$`G`$ is $`p`$-group.

So we can formulate

###### Hypothesis 126

Full invariant of not $`p`$-group is defined with $`|G|`$ and $`n`$ and full invariant of $`p`$-group of order $`p^m`$ is defined with maximum $`mp^2`$ permutations or corresponding numbers that define these permutations.

### 7.3 The polynomial algorithm of graph isomorphism testing

The graph isomorphism problem has a polynomial solution, if the problem of separating of orbits of the automorphism group of a graph has a polynomial solution. So we want to find the partition $`O_2=Aut(X_2)X_2Orb_2(Aut(X_2))`$ of a $`2`$-set $`X_2V^{(2)}`$ polynomially on $`n`$.

Let $`X_kV^{(k)}`$ be a $`k`$-set. We say that $`X_k`$ is *transitive*, if All $`1`$-projections of $`X_k`$, are equal. We say that $`X_k`$ is *regular*, if it satisfy to the two conditions:

1. Every $`l`$-multiprojection of $`X_k`$ for $`l[1,k]`$ is homogeneous.
2. All $`l`$-projections of $`X_k`$, containing the same $`l`$-tuple, are equal.

###### Lemma 127

Let $`X_2`$ be a regular $`2`$-set and $`X_1^1,X_1^2`$ be its $`1`$-projections. Let $`|X_2|=|X_1^1|`$. If $`X_1^1X_1^2`$, then $`X_2`$ is automorphic. If $`X_1^1=X_1^2`$, then the partition $`O_2=Aut(X_2)X_2`$ is detected directly.

So the problem presents, if $`|X_2|/|X_1^1|>1`$ and $`|X_2|/|X_1^2)|>1`$. Let $`X_2V^{(2)}`$ be a regular $`2`$-set and $`Co(X_2)=V`$, then $`Aut(X_2)`$ is (generally intransitive) group of degree $`n`$ and all prime cycles from $`Aut(X_2)`$ have the length not greater than $`n`$. Let $`X_2`$ be automorphic and $`Y_2X_2`$ be a $`2`$-orbit of a subgroup $`A<Aut(X_2)`$, then $`R_2=AX_2`$ is a partition of $`X_2`$ on $`2`$-orbits of $`A`$ and hence classes of $`R_2`$ are regular $`2`$-sets.

The fundamental role in polynomial solution of considered problem plays the theorem 97. One can see that cyclic structure, that was described for transitive $`(2k)`$-orbits, exists also on intransitive $`(2k)`$-orbits. But the direction (left, right, left, right, …) must be change to (left, right, right, left, left, …). We can also note that in general, if we have a regular $`2`$-set $`X_2V^{(2)}`$, then we have also a partition $`P_2`$ of $`V^{(2)}`$ on regular $`2`$-sets invariant relative to $`Aut(X_2)`$. Thus with given intransitive regular $`2`$-set $`X_2`$ we can also find transitive, regular, $`Aut(X_2)`$-invariant $`2`$-sets of $`P_2`$.

###### Algorithm 128

Let now $`X_2`$ be arbitrary regular, $`2`$-set and we try find its automorphism, then we follow the next steps:

1. Find an automorphic $`2`$-subset $`Y_2X_2`$ that is expected to be a $`2`$-suborbit of $`Aut(X_2)`$.
2. Construct a partition $`R_2^i`$, $`i=1,2,\mathrm{}`$, iterating the process that follows from theorem 97. By each iteration verify classes of $`R_2^i`$ on regularity and subpartition them if they are not regular.

This process leads to an automorphism, possibly trivial.

To find $`Y_2`$ is not difficult. At first it could be taken a subset $`Y_2(u)`$ of $`X_2`$ whose $`1`$-projection $`\widehat{p}(I_1^1)Y_2`$ is an element $`u`$ of $`V`$. Thus we can define whether $`Stab(u)`$ is trivial. If it is trivial, then it follows that $`X_2`$ is incoherent and can be partition on coherent $`2`$-subsets.

If $`Aut(X_2)`$ is trivial, then given algorithm detects this triviality in maximally $`n`$ steps, if to assume that in each step only one element of $`V`$ is separated.

Using lemma 62 we can, having automorphic partitions $`R_k^{}`$ and $`R_k^{\prime \prime }`$ of $`X_k`$, obtain new more big partition $`R_k=R_k^{}R_k^{\prime \prime }`$.

For simplification of the process it can be chosen for partitioning on $`i`$-th iteration the most suitable $`2`$-set $`X_2^i`$ from the partition $`P_2^i`$ of $`V^{(2)}`$, on regular $`2`$-sets invariant to $`Aut(X_2)`$, and, by partitioning of $`X_2^i`$, the whole partition $`P_2^i`$ can be further partitioned to regular classes $`P_2^{i+1}`$ and used in the next iteration.

## Conclusion

This work was initiated by the polycirculant conjecture, described by P. Comeron in his text  and represented on the site (http://www.maths.qmw.ac.uk/~pjc/homepage.html).

The using of $`k`$-orbits to the polynomial solution of the graph isomorphism problem was begun by Author in 1984. The generalization of $`k`$-orbits, regular $`k`$-sets, was used for describing of the structure of strongly regular graphs and their generalization on dimensions greater as two. This approach discovered the difference between the structure of strongly symmetrical but not automorphic partitions of $`V^{(k)}`$ and automorphic partitions of $`V^{(k)}`$.

From this point of view the polycirculant conjecture seemed enough simple. But nevertheless to find a correct proof was very difficult and only the analysis of two examples of permutation groups (one elusive group of order 72 and degree 12, and the automorphism group of Peterson graph), that was presented to author by P. Comeron, leaded to discovery of the specific properties of $`k`$-orbits, not detectable with group theory, that brought a proof of the conjecture.

In 1997 Author understood the connection between the graph isomorphism problem and the problem of a full invariant of a finite group and has done some attempts to obtain this full invariant by construction of some appropriate group representations. This work gave better understanding of the problem but did not bring the expected result. By construction of the $`k`$-orbit theory it was of interest to consider a finite group with new representation and this time the result was obtained.

Also the specific symmetry properties of $`k`$-orbits, that are not visible in other most algebraic theories, gave possibility for simple polynomial solution of the graph isomorphism problem.

## Acknowledgements

I would like to express many thanks to Prof. P. Cameron for encouraging to do this work and for the counterexamples to not correct hypotheses on the way to prove the polycirculant conjecture.