F. M. Malyshev, “Realization of permutations of even degree by products of three fixed-point-free involutions”, Sb. Math., 215:12 (2024), 1720

Abstract: We consider representations of a permutation $\pi$ of degree $2n$, $n\geqslant3$, by a product of three so-called pairwise-cycle permutations, all of whose cycles have length $2$. This is a valid question for even permutations if $n$ is even and for odd permutations if $n$ is odd. We prove constructively that for $n\geqslant4$, $n\neq8$, such a representation holds for all permutations $\pi$ of the same parity as $n$, apart from four exceptional conjugacy classes. For $n=8$ there are five exceptional conjugacy classes, and for $n=3$ there is one such class.
Bibliography: 32 titles.

§ 1. Introduction

If a group $G$ is generated by a subset $Q$ of $G$ such that $Q=Q^{-1}=\{q^{-1}\mid q\in Q\}$, then the length $l_Q(x)$ of an element $x\in G$ with respect to $Q$ is the least nonnegative integer $r$ such that $x$ is a product of $r$ elements of $Q$ (see [1]). The lengths of symplectic and orthogonal transformations with respect to involutions in the form of symmetries were studied by É. Cartan and Dieudonné (see [2]). We recall that involutions are nonidentity elements $q\in Q$ for which $q^2=e$ is the identity of the group.

In the early 1970s Kostrikin conjectured that each element of a finite simple group can be represented as a product of at most four involutions of the group. Tits believed that elements of a simple algebraic group over an algebraically closed field can be represented as products of at most three involutions. Earlier it was proved in [3] that a unitary transformation of an infinite-dimensional complex Hilbert space can be represented as a product of four involutions. For unitary transformations with determinant 1 of finite-dimensional complex Hilbert spaces this fact was established later in [4]. In [5] it was proved that real square matrices with determinant 1 can be represented as products of several involutions. This result was extended in [6] to arbitrary skew fields. Finally, it was shown in [7] that any square matrix with determinant $\pm1$ over a field can be represented as a product of at most four involutions. In [8] a necessary and sufficient condition was presented for the representation of a permutation of degree $m$ with a fixed cycle structure as a product of $k$ involutions consisting of $t$ cycles of length 2, where $t<m/2$. Involutions in a symmetric group have cycles of length at most 2.

If $G=A_m$ is an alternating group, which, as we know, is generated for $m\geqslant5$ by the set $I_m$ of involutions of the form $(i,j)(k,l)$, $i,j,k,l\in\{1,2,\dots,m\}$, then $\lim_{m\to\infty}\max_{\pi\in A_m}l_{I_m}(\pi)=\infty$. The situation changes drastically when all involutions are regarded as a wider set of generators of $\mathcal{I}_m$. Then $l_{\mathcal{I}_m}(\pi)\leqslant3$ for all $\pi\in A_m$ with $m>6$ (see [9]–[11]). For arbitrary finite simple groups $G$ it was proved in [11] that there exists an absolute constant $L\leqslant20$ such that, if $\mathcal{I}\subset G$ is the set of all involutions, then $l_\mathcal{I}(g)\leqslant L$ for all $g\in G$.

Various questions relating to symmetric groups $G=S_m$ with some sets of generators were considered in [12]–[22]. For symmetric and alternating groups there are natural questions of the requisite number of factors $l_P(\pi)$ in products representing $\pi$ in situations when, in place of the set $\mathcal{I}_m$, we consider some of its subsets $P$.

In this paper we look at the system of generators $P_n\subset S_{2n}$, $n\geqslant3$, consisting of all involutions without fixed points, so-called pairwise-cycle permutations. This is a single conjugacy class of involutions, which is far from being the largest one in cardinality. For example, the number of involutions with precisely two fixed points in the group $S_{2n}$ is $|P_n|$ times $n$.

As a consequence of Proposition 1 in [11], which claims that $l_{\mathcal{I}_m}(\pi)\leqslant3$ for permutations $\pi$ in the alternating group $A_{2n}$ for $n>3$, we have $l_{P_n}(\pi)\leqslant6$, since every involution $\sigma\in A_{2n}$ can be represented as a product of two involutions from $P_n$. For the symmetric group $S_{2n}$ a similar argument is impossible. In the symmetric group every permutation is a product of two involutions. If, for example, a cycle of length $k$ is represented by a central rotation of a regular $k$-gon through an angle of $2\pi/k$, then this rotation is the product of the mirror symmetries with respect to two diameters with an angle of $\pi/k$ between them. For even $k$ the involution corresponding to one of these symmetries is an odd permutation, which cannot be represented as a product of two pairwise-cycle permutations.

In [23] it was proved that any even permutation can be represented as a product of four pairwise-cycle permutations. Examples of even permutations not representable as products of three pairwise-cycle permutations can also be found there. In our paper [24] these results were proved constructively. As a consequence, it was shown that any odd permutation can be realized (for odd $n$) as a product of five pairwise-cycle permutations, and there are odd permutations that cannot be realized as a product of three pairwise-cycle permutations. These counterexamples can be obtained using a criterion due to Ree and formulated in terms of lengths of cycle in permutations (see [25]–[27]).

In the present paper we show using effective constructions, as in [24], that for even (odd) $n\geqslant3$ almost all even (respectively, odd) permutations are realized as a product of three pairwise-cycle permutations. The only exceptional cases that cannot be realized in this way are four conjugacy classes of permutations for $n\geqslant4$, $n\neq8$, five conjugacy classes for $n=8$, and one conjugacy class for $n=3$.

Below, in § 2 we state a theorem containing the main result of the paper. In § 3 we present preliminary assertions used in the proof of the theorem. In § 4, which constitutes the main content of the paper, we give the proof of the theorem. In the final short section, § 5, we indicate the connections of the issues under consideration with cubic graphs.

§ 2. Notation and the statement of the main result

We consider only even integers $m=2n$, $n\geqslant3$, as degrees of permutations. We denote pairwise-cycle permutations by $p$, $p_i\in S_{2n}$, $i\in\mathbb{N}$.

For the cardinality of the set $P_n\subset S_{2n}$ of all pairwise-cycle permutations $p\in S_{2n}$ we have $|P_n|=(2n-1)\cdot(2n-3)\dotsb5\cdot3=(2n-1)!!$ Since $(2n)!/2=2n\cdot(2n- 2)\dotsb 6\cdot4\cdot(2n-1)\cdot(2n-3)\dotsb5\cdot3>|P_n|^2$, it follows that, if for all even or all odd permutations $\pi\in S_{2n}$ we have a representation

In this paper there is no need to specify permutations $\pi\in S_{2n}$ from a particular class of conjugate permutations, and thus we denote such a permutation by listing the lengths of its cycles in parentheses. We indicate the number of cycles of the same length by a superscript. When the lengths of cycles do not exceed 9, we do not separate them from one another by commas. We also indicate the number of cycles of length 1. For example, $p=(2^n)$ for $p\in P_n$, $((2n)^1)$ represents all $(2n-1)!$ full-cycle permutations, $(n^2)$ denotes permutations representable by two cycles of length $n$ each, and $(1^{2n})$ is the identity permutation, all of whose cycles have length 1. We consider only one permutation from the whole set of permutations with a fixed cycle structure. Our notation in terms of the lengths of cycles distinguishes a whole class of conjugate permutations; therefore, for specific permutations ${\pi\in S_{2n}}$ one should write $\pi\in(1^{i_1},2^{i_2},\dots,(2n)^{i_{2n}})$ rather than $\pi=(1^{i_1},2^{i_2},\dots,(2n)^{i_{2n}})$ as we actually write in what follows. (We have already written above $p=(2^n)$ instead of $p\in(2^n)$.) This does not lead to misunderstanding because of the specifics of the problems we consider, and we use the above notation both for a whole conjugacy class of permutations and for any particular representative of this class.

In products, permutations are applied from left to right. We use without special mention the results that permutations $\pi$, $\pi^{-1}$, and $\sigma\pi\sigma^{-1}$, where $\pi,\sigma\in S_k$, have the same cycle structure, as also do $\pi\sigma$ and $\sigma\pi=\sigma(\pi\sigma)\sigma^{-1}$. Conversely, for any pair of permutations $\pi_1,\pi_2\in S_k$ with the same cycle structure there is always a permutation $\sigma\in S_k$ for which $\pi_1=\sigma\pi_2\sigma^{-1}$. For $p_1,p_2,p_3\in P_n$ all six products $p_{i_1}p_{i_2}p_{i_3}$, $\{i_1,i_2,i_3\}=\{1,2,3\}$, are conjugate to one another and have the same cycle structure. We also recall that the parity of a permutation coincides with the parity of the sum of the lengths of all of its cycles minus 1.

Theorem 1. Let $\pi\in A_{2n}$ for even $n>3$ or $\pi\in S_{2n}\setminus A_{2n}$ for odd $n\geqslant3$. Then the permutation $\pi$ is $3$-representable if and only if it does not belong to one of the following seven families of conjugacy classes:

(a) $(5^13^12^i)$, $i\geqslant0$; (b) $(5^11^i)$, $i\equiv3\,(\operatorname{mod}4)$, $i\geqslant3$; (c) $(4^13^11^i)$, $i\equiv3\,(\operatorname{mod}4)$, $i\geqslant 3$; (d${}_{a}$) $(3^11^12^i)$, $i\geqslant0$; (d${}_{b}$) $(3^11^i)$, $i\equiv1\,(\operatorname{mod}4)$, $i\geqslant5$; (d${}_{c}$) $(2^13^11^i)$, $i\equiv1\,(\operatorname{mod}4)$, $i\geqslant5$; (d${}_{0}$) $(3^51^1)$.

The last family in the statement of Theorem 1 consists of the single conjugacy class of permutations $(3^51^1)$. It follows from Theorem 1 that for $n=3$ only the permutations $(1^12^13^1)$ are not 3-representable. For odd $n>4$ only the following four classes of permutations are not 3-representable: $(5^13^12^{n-4})$, $(4^13^11^{2n-7})$, $(3^12^{n-2}1^1)$ and $(3^12^11^{2n-5})$. For even $n\geqslant4$, $n\neq8$, only the permutations in the conjugacy classes $(5^13^12^{n-4})$, $(5^11^{2n-5})$, $(3^12^{n-2}1^1)$ and $(3^11^{2n-3})$ are not 3-representable, and for $n=8$ the conjugacy class $(3^51^1)$ is added to the last four classes $(5^13^12^4)$, $(5^11^{11})$, $(3^12^61^1)$ and $(3^11^{13})$.

In connection with the above remark and Brenner’s problem in [23] (solved in [27]) on sufficient conditions for conjugacy classes $D\subset A_m$ ($m=2n$ in our case) to satisfy the equality $D^3=A_{2n}$, the following question arises: to what extent is it ‘fair’ to exclude the class of pairwise-cyclic permutations, as proposed in [23], and whether the concept of the exponent of a conjugacy class must be adjusted?

The proof that permutations in the families (a), (d${}_{a}$), (b), (d${}_{b}$), (c) and (d${}_{c}$) have no 3-representations is presented in § 4.4; it is not that difficult since we deal every time with large series of cycles of the same length, either 1 or 2, and the number of other cycles is at most two. The most intricate case is the conjugacy class of permutations $(3^51^1)$, which contain a series of length 5 of 3-cycles. For a greater number of $l$-cycles, where $l\geqslant3$ (which is luckily not the case here) this complexity would only increase.

As noted in § 4.5, it follows from the constructive proof of Theorem 1 given in § 4 that there is a polynomial algorithm solving the equation $p_1p_2p_3=\pi$ with respect to the unknowns $p_1,p_2,p_3\in P_n$ (provided that the right-hand side $\pi\in S_{2n}$ does not belong to the exceptional families).

The referee of this paper pointed out the work [28] by Moran, unknown to the author, where, in particular, 3-representable permutations $\pi$ in the symmetric group $S_{X}$ acting on an arbitrary infinite set $X$ were distinguished. In addition to finite cycles, permutations $\pi\in S_X$ can have infinite cycles of the form of addition of 1 to the integers in $\mathbb{Z}$, and then permutations can naturally be represented in the form $\pi=(1^{i_1},2^{i_2},\dots,\mathbb{Z}^i)$, where $\mathbb{Z}$ is an infinite cycle and each symbol $i_1,i_2,\dots,i$ takes values in the set $\{0,1,2,\dots,\infty\}$, where $\infty$ denotes the cardinality of some infinite set. The corresponding result of Moran is more concise than Theorem 1.

Moran’s theorem can be deduced from Theorem 1. In § 4.6 we present, as a supplement, the most elementary proof of Moran’s theorem (of the ones known to the author).

The author does not know how to deduce Theorem 1 from Moran’s theorem, apart from the proof in §§ 4.4.2–4.4.4 that permutations in the families (b), (d${}_{b}$), (c) and (d${}_{c})$ have no 3-representations, which follows from Moran’s theorem immediately by contradiction, since otherwise (as the permutations $(1^4$) are 3-representable) the permutations $(5^11^\infty)$, $(3^11^\infty)$, $(4^13^11^\infty)$ and $(2^13^11^\infty)$, respectively, would also be 3-representable. The impossibility of 3-representations for permutations in the series (a), (d${}_{a}$) and (d${}_{0}$) does not follow from Moran’s theorem.

§ 3. Preliminary results

This section presents some preliminary assertions. They are rather obvious and are accompanied by necessary comments.

This is the so-called Klein four-group. By Proposition 3.1, for $n=2$ one cannot obtain even permutations $(3^11^1)$ or odd permutations $(4^1)$ and $(2^11^2)$ in $S_4$ from products (1) of any length $l>0$.

We use this simple statement in the following situation. Let $\pi\in S_X$, $|X|=2n$, let $X=X_1\sqcup X_2$, $|X_1|=2n_1$, $|X_2|=2n_2$, and let $\pi=\pi_1\pi_2$, where $\pi_1|_{X_2}=\mathrm{id}_{X_2}$, $\pi_2|_{X_1}=\mathrm{id}_{X_1}$, $\pi_1|_{X_1}=p'_1\dotsb p'_l$, $p'_i\in S_{X_1}$, $p'_i\in P_{n_1}$, $i=1,\dots,l$, and $\pi_2|_{X_2}=p''_1\dotsb p''_l$, $p''_i\in S_{X_2}$, $p''_i\in P_{n_2}$, $i=1,\dots,l$. Then $\pi=p_1\dotsb p_l$, where $p_i|_{X_1}=p'_i$ and $p_i|_{X_2}=p''_i$, $i=1,\dots,l$. We will often mean, without mentioning it explicitly, that permutations $\pi|_{X_2}=\mathrm{id}_{X_2}$ can be represented in the form $p''^l$ for some even $l$, where $p''\in S_{X_2}$ and $p''\in P_{n_2}$, while permutations $\pi|_{X_2}\in P_{n_2}$ can be represented in the form $(\pi|_{X_2})^l$ for some odd $l$. We will also use the notation $\pi=\pi_1\sqcup\pi_2$.

This follows from Proposition 3.2. The even number of cycles of length 2 of an even involution $\sigma\in A_{2n}$ falls into pairs to which Proposition 3.1 is applicable. Cycles of length 2 in the required pairwise-cycle permutations $p_1,p_2\in P_n$ must coincide on the set of fixed points of $\sigma$.

Here the lengths of cycles in two different pairs can be different in general. If ${p_1=p_2}$ and $p_1p_2=(1^{2n})$, then we have pairs of cycles of length 1. For permutations $\pi$ in Proposition 3.4 the number of cycles of any fixed length is even. Permutations whose cycles are grouped into pairs of the same length are called $2$-representable.

To prove Proposition 3.4 it suffices to consider a graph $\Gamma$ on $2n$ vertices with two types of edges. One type of edges corresponds to 2-cycles of the pairwise-cycle permutation $p_1$, which are shown by

in Figure 1, and the other type of edges corresponds to 2-cycles of $p_2$, which are shown by

in Figure 1. The graph $\Gamma$ is partitioned into cycles of even length $2k$, $k\leqslant n$, on which the edge types alternate sequentially (see Figure 1 for $k=6$). Every cycle in $\Gamma$ ‘contains’ two similarly oriented cycles of the product of permutations $p_1p_2$, with arcs (above and below) shown by

Figure 1. (We adhere to this convention of showing the first factor by

, the second factor by

, and the result by

in figures throughout the paper.)

The converse statement is proved using the same construction. Every pair of similarly oriented cycles of the same length must be arranged as in Figure 1: one cycle above the other.

The proof follows from Proposition 3.4 and the fact that for the single-cycle permutation $\pi\colon x\mapsto x+1$ and the pairwise-cycle permutation $p\colon x\mapsto x+n$, $x\in\mathbb{Z}_{2n}$, we have $\pi p=(n^2)$. Here $\mathbb{Z}_{2n}=\{0,1,\dots,2n-1\}$ is the residue ring $\operatorname{mod}2n$.

Two permutations $\pi_1,\pi_2\in S_{2n}$ are considered below to be close if $\pi_1p=\pi_2$ for some pairwise-cycle permutation $p\in P_n$. The closeness relation is symmetric. We will use it for classes of permutations with the same cycle structure. It is convenient to represent this relation by an undirected graph, not all possible edges of which are necessarily indicated.

Proposition 3.6 (together with Proposition 3.4) is our main tool for the proof of the 3-representability of permutations. We will repeatedly construct a permutation close to $\pi$ whose cycles can be grouped into pairs of cycles of equal length, so that it is a 2-representable permutation close to $\pi$. Then $\pi p=p_1p_2$, and thus $\pi=p_1p_2p$ is a 3-representable permutation.

These closeness relations are justified, respectively, by Figure 1, by the proof of Proposition 3.5 for odd $n$, and (within the same proof) by the closeness of the class $((2n)^1)$ to itself for even $n$, which follows from the fact that the integers $2n$ and ${n+1}$ are coprime.

The proof follows from Proposition 3.7, Proposition 3.6 in combination with Proposition 3.8, and Figures 3–6 below.

In Propositions 3.10–3.20 below some cycles can have an arbitrarily large length. In these cases, for the proof we provide figures with some concrete lengths of cycles, from which the general situations can simply be reproduced by analogy. We will ‘embed’ large cycles of a permutation $\pi\in S_{2n}$ in the environment of transpositions of a pairwise-cycle permutation $p\in P_n$, by bringing close two pieces of cycles so that they be oppositely oriented and the corresponding pairs of vertices of different pieces form a 2-cycle of the permutation $p$, as in Figure 7 below. Then the overwhelming majority of cycles in the permutation $\pi p$ are of length 2 in accordance with Figure 7, and we can also achieve that the remaining cycles (left outside the figure) have length at most four.

§ 4. Proof of Theorem 1

Let us distinguish cycles of a permutation $\pi\in S_{2n}$, $n\geqslant1$, by their lengths $l$. We distinguish seven types of $l$-cycles. First of all, these are cycles of length $l\in\{1,5,3\}$, and there are four other types defined in terms of the residues of $l\,(\operatorname{mod} 4)$.

The number of cycles in a permutation $\pi$ of length $4k$, $k\geqslant1$, is denoted by $\nu_o$. A cycle of this length is called an $o$-cycle. The number of cycles in a permutation of length $2(2k+1)$, $k\geqslant0$, is denoted by $\nu'_o$, and we call these $o'$-cycles. The number of 2-cycles (for $k=0$) is also denoted by $\nu_2$. We also consider two types of cycles of odd length. The number of cycles of length $4k+1$, $k\geqslant2$, is denoted by $\nu_{\alpha}$, and that of cycles of length $4k-1$, $k\geqslant2$, by $\nu_{\beta}$. We call these $\alpha$- and $\beta$-cycles, respectively. We denote the numbers of 5-, 3-, and 1-cycles by $\nu_5$, $\nu_3$, and $\nu_1$, respectively. We also use the notation of the form $\alpha\beta$-cycle for cycles of length $4k\pm1$, $k\geqslant2$, and denote their total number by $\nu_{\alpha\beta}=\nu_\alpha+\nu_\beta$ .

We split the proof into several parts and statements. The general structure of the proof is as follows.

In Propositions 4.1–4.8 we distinguish certain special families of cycles which form 3-representable permutations. We call them blocks. The cardinality of a block can be one (Proposition 4.2), two (Propositions 4.1 and 4.6–4.8), or four (Propositions 4.3–4.5).

The main part of the proof of Theorem 1 consists in justifying the 3-representability of permutations whose cycles do not contain blocks. We say that such permutations are reduced. By removing successive blocks from a permutation, we transform it into a reduced permutation (of course, of a different degree).

It will result from Propositions 4.1–4.8 that the following conditions hold for the number of cycles in reduced permutations:

In the case when $\nu_0=0$, the proof that reduced (even) permutations are 3-representable is carried out in § 4.1, split into §§ 4.1.1–4.1.3, treating the cases $\nu_\beta\in\{1,2,3\}$, $\nu_\alpha\in\{1,2,3\}$ and $\nu_\alpha=\nu_\beta=0$, respectively.

Similarly, in the case when $\nu_0=1$, the proof that reduced (odd) permutations are 3-representable is carried out in § 4.2, split into § 4.2.1, where $\nu_\beta\in\{1,2,3\}$, § 4.2.2, where $\nu_\alpha\in\{1,2,3\}$, and § 4.2.3, where $\nu_\alpha=\nu_\beta=0$.

In § 4.1 the 3-representability of even reduced permutations distinct from $(5^13^1)$, $(1^35^1)$ and $(1^13^1)$ is proved, and in § 4.2 the 3-representability of odd reduced permutations distinct from $(1^33^14^1)$ is proved.

In § 4.3 we prove 3-representability for permutations not included in any of the families (a)–(d). (By the family (d) of permutations we mean the union of the four families $\mathrm{(d_a)}$, $\mathrm{(d_b)}$, $\mathrm{(d_c)}$ and $\mathrm{(d_0)}$.) In §§ 4.3.1–4.3.4 we prove this separately for permutations whose set of cycles, in addition to several blocks, contains cycles of permutations $(5^13^1)$, $(1^35^1)$, $(1^33^14^1)$ and $(1^13^1)$, respectively.

In § 4.4, split into §§ 4.4.1–4.4.4, we prove the that permutations in the families (a)–(d), respectively, have no 3-representations.

We recall that the 3-representability of a permutation $\pi$ is equivalent to the existence of a 2-representable permutation close to it. The main tool in the proofs of 3-representability is Proposition 3.6, which we usually apply without special mention. We also use without special mention Proposition 3.1, which is applied to the case of an even number of 2-cycles.

The proof of the 3-representability of a particular permutation $\pi$ or a family of permutations is always carried out in accordance with the following scheme. First we divide the whole family of cycles of the permutation under study into (at most four) disjoint subsets. We apply one of Propositions 3.8–3.20 to every subset; in doing this we select such variants of close permutations that the whole family of their cycles (obtained as a union over the subsets of cycles of $\pi$ mentioned above) forms a 2-representable permutation (with cycles grouped into pairs of equal length).

Throughout the proof we assume that the permutation $\pi\in S_{2n}$, $n\geqslant1$, has the same parity as $n$. The question of 3-representability is legitimate only in this case.

The proof follows from Proposition 3.12, (a) as applied to each of the two pairs of cycles.

The proof follows from Proposition 3.4, since the two existing pairs of cycles are (separately) close to two permutations with the same cycle structure.

The proof follows from Proposition 3.12, (b) in the case of a 5-cycle and from Proposition 3.14, (c) in the case of a 1-cycle.

When we try to prove 3-representability for a specific permutation $\pi$ of even degree using Proposition 3.2 and Propositions 4.1–4.8, by excluding some families of cycles (in the form of blocks) considered there, we eventually arrive at the situation where $\nu_o\leqslant1$; $\nu'_o=0$; $\nu_\alpha\leqslant3$; $\nu_\beta\leqslant3$; $\nu_i\leqslant3$, $i=1,3,5$; if there is an $\alpha$-cycle, then there are neither $\beta$- nor 3-cycles; if there is a $\beta$-cycle, then there are neither $\alpha$-, 1-, nor 5-cycles. Permutations $\pi$ with these properties were called above reduced permutations.

After deleting an $o'$-cycle, the parities of the permutation and the corresponding parameter $n$ are reversed. When other blocks are deleted from cycles, the parities of the permutation and the corresponding parameter $n$ are preserved. In either case the parity of the permutation remains equal to the parity of one half of its degree.

For $\nu_o=0$ and $\nu_o=1$ alike we specify reduced permutations $\pi$ by strings of the form $\nu_1\nu_5\nu_{\alpha\beta}\nu_3$ which correspond to permutations $(1^{\nu_1}5^{\nu_5}(2k_1+1)^{\nu_{\alpha\beta}^{(1)}} (2k_2+1)^{\nu_{\alpha\beta}^{(2)}}(2k_3+1)^{\nu_{\alpha\beta}^{(3)}}3^{\nu_3})$, where $k_i\geqslant3$, $i=1,2,3$, and $\nu_{\alpha\beta}^{(1)}+\nu_{\alpha\beta}^{(2)}+\nu_{\alpha\beta}^{(3)}= \nu_{\alpha\beta}$. If $\nu_o=0$, then the permutation $\pi$ is even; therefore, one half of its degree is even, which is expressed by the equality

The following statement is often used in proofs of the 3-representability of reduced permutations.

Proof. If $\nu_{\alpha\beta}=0$, then we have a permutation $(k^2,l^2)$, $k\neq l$, $k,l\in\{1,5,3\}$. From Proposition 3.2 we conclude that the two permutations $(k^1,l^1)$ and $(k^1,l^1)$ (of degree $k+l$ each) are separately close to two permutations with the same cycle structure. It remains to combine their cycles of the same length into pairs and apply Proposition 3.4.

Let $\nu_{\alpha\beta}=2$. The lengths of the other two cycles in the even reduced permutation $\pi$ are the same and equal to 1, 5, or 3. According to Proposition 3.2, the permutation $\pi$ is represented by two reduced permutations $\pi_1$ and $\pi_2$ specified by strings in which twos are replaced by ones. To each of these permutations we apply Proposition 3.14, (a), 3.12, (a), or 3.13, (a). As a result, we obtain a permutation close to $\pi$ whose cycles are grouped into pairs of equal length, including 2-cycles, whose number is even. Applying Proposition 3.4 we obtain the required result.

This completes the proof of the proposition.

Now we consider separately the cases $\nu_o=0$ in § 4.1 and $\nu_o=1$ in § 4.2. In §§ 4.1 and 4.2 we prove 3-representability for reduced permutations not included in the series (a)–(d) in the statement of Theorem 1. In § 4.3 we prove 3-reducibility in the general case, for permutations $\pi$ not included in the series (a)–(d). In § 4.4 we prove that permutations $\pi$ in the series (a)–(d) are not 3-representable.

4.1.

Let $\nu_o=0$. Then a reduced permutation $\pi$ is even since it consists of cycles of odd lengths 1, 5 and 3 and also of $\alpha\beta$-cycles of odd length. The string $\nu_1\nu_5\nu_{\alpha\beta}\nu_3$ specifying it satisfies equality (3). We consider separately the cases $\nu_\beta\in\{1,2,3\}$ in § 4.1.1, $\nu_\alpha\in\{1,2,3\}$ in § 4.1.2, and $\nu_\alpha=\nu_\beta=0$ in § 4.1.3.

4.1.1.

Let $\nu_\beta\in\{1,2,3\}$. In this case, for the reduced permutation $\pi$ we have $\nu_1=\nu_5=\nu_\alpha=0$, and equality (3) looks as follows:

The 3-representability of the permutation 0031 is proved similarly, and our notation allows us to limit ourselves to a shorthand record of the proof:

4.1.2.

Let $\nu_\alpha\in\{1,2,3\}$. In this case, for the reduced permutation $\pi$ we have $\nu_3=\nu_\beta=0$, and equality (3) looks like

4.1.3.

Let $\nu_\alpha=\nu_\beta=0$. In this subsubsection we prove the following statement.

Proof. This statement was proved in § 4.1.1 for $\nu_\beta\neq0$, and in § 4.1.2 for ${\nu_\alpha\neq0}$. It remains to prove it for $\nu_\alpha=\nu_\beta=0$. Then equality (3) takes the form $\nu_3=\nu_1+\nu_5\,(\operatorname{mod}4)$. As a result, for the string $\nu_1\nu_50\nu_3$ we have 16 possibilities. The string 0000 represents the identity permutation, it is even, and one half of its degree is also even; therefore, it is 3-representable by Proposition 3.1. Further, $3302=2200\sqcup1102$; therefore, in view of Proposition 4.9 it remains to verify the 3-representability of only eight permutations: 0303, 1102, 1203, 1300, 2103, 2301, 3003 and 3201. We consider these permutations now:

This completes the proof of Proposition 4.10.

4.2.

Let $\nu_o=1$. Then the reduced permutation $\pi$ is odd since it contains a unique cycle of even length. In addition to Proposition 4.10, we now prove the following result.

The exceptional permutations in Proposition 4.10 belong to the series (a), (b) and (d) from Theorem 1, and the permutation $(1^334)$ in Proposition 4.11 belongs to the series (c).

4.2.1.

Let $\nu_\beta\in\{1,2,3\}$. Then for the permutation $\pi$ in question we have $\nu_1=\nu_5=\nu_\alpha=0$, and equality (4) looks like

4.2.2.

Let $\nu_\alpha\in\{1,2,3\}$. In this case, for the reduced permutation $\pi$ we have $\nu_3=\nu_\beta=0$, and equality (4) looks like

4.2.3.

Let $\nu_\alpha=\nu_\beta=0$. Then equality (4) takes the form $\nu_3=\nu_1+\nu_5+2\,(\operatorname{mod}4)$. As a result, for the strings $\nu_1\nu_50\nu_3$ we have 16 possible cases. In view of Proposition 4.9 and since the string 1100 was analyzed in § 4.2.2, it is sufficient to prove 3-representability only for the nine strings 0002, 0103, 0200, 0301, 1003, 1201, 2000, 2101 and 3001, where the last string, presenting the exceptional permutation $(4^11^33^1)$ in Proposition 4.11, must be treated for the cycles $(4k)^1$, where $ k>1$. For the eight previous strings we have $k\geqslant1$:

4.3.

Continuing the proof of Theorem 1, in this subsection we show that if a permutation $\pi$ of the same parity as one half of its even degree is not contained in the families (a)–(d) from the statement of Theorem 1, then it is 3-representable. For reduced permutations $\pi$ this is the result of Propositions 4.10 and 4.11. Reduced permutations have turned out to be 3-representable, apart from only four permutations, $(5^13^1)$, $(1^35^1)$, $(4^11^33^1)$ and $(1^13^1)$. These are permutations from the families (a), (b), (c) and (d), respectively.

We recall that a permutation is said to be reduced if it does not contain the blocks of cycles forming 3-representable permutations that were treated in Propositions 4.1–4.8. We assign numbers from 1 to 11 to these blocks: (1) a pair of $o$-cycles, denoted by $(o^2)$; (2) one $o'$-cycle, $(o')$; (3) four $\alpha$-cycles, $(\alpha^4)$; (4) four $\beta$-cycles, $(\beta^4)$; (5) $(1^4)$; (6) $(3^4)$; (7) $(5^4)$; (8) $\alpha$- and $\beta$-cycles, $(\alpha,\beta)$; (9) 3- and $\alpha$-cycles, $(\alpha,3)$; (10) 1- and $\beta$-cycles, $(\beta,1)$; (11) 5- and $\beta$-cycles, $(\beta,5)$. In case of $(o^2)$, $(\alpha^4)$ or $(\beta^4)$ cycles of the same type do not necessarily have the same length. Further, throughout the part of the proof of Theorem 1 presented in § 4.3, if the notation for a conjugacy class of permutations contains no superscript at the length 1, 3, or 5 of a cycle or at the types $o'$, $o$, $\alpha$, or $\beta$ of a cycle, then this means automatically that the superscript is equal to 1: for example, $(\alpha^41^35^1)=(\alpha151\alpha^21\alpha)$. As before, the lengths and types of cycles in the notation are not always separated by commas.

For every exceptional permutation $(53)$, $(1^35)$, $(41^33)$ and $(13)$, in §§ 4.3.1–4.3.4, respectively, we verify the 3-reducibility of the combination of these permutations with each of the 11 excluded blocks, provided that this combination is not contained in the corresponding exceptional family. To do this we indicate every time a 2-representable permutation close to the combination under consideration. Combinations with an $o'$-cycle are considered separately for an $o'$-cycle of length at least 6 and for 2-cycles.

4.3.1.

(1) $(o^2,5,3)=(53)[3.13,\,\mathrm{c})]\sqcup(o)[3.10,\,\mathrm{a})]\sqcup(o)[3.10,\,\mathrm{b})]$ —— $(41^22)\sqcup(42^\kappa)\sqcup(1^22^{\kappa+1})$. Here and below square brackets $[\ ]$ contain a reference to the corresponding proposition in § 3. By $\kappa$ we denote some nonnegative even integer; their values can be different at different positions in the same formula.

(2) $(o',5,3)\,{=}\,(53)[3.13,\,\mathrm{c})]\sqcup(o')[3.10,\,\mathrm{a})]$ —— $(41^22)\sqcup(42^{\kappa+1})$. Here the length of the $o'$-cycle is al least 6, and a 2-cycle is not regarded as an $(o')$-cycle, since the permutation $(253)$ belongs to the family (a) from the theorem.

(3) $(\alpha^4,5,3)=(\alpha,3)[3.13,\,\mathrm{b})]\sqcup(\alpha,\alpha)[3.12,\,\mathrm{b})] \sqcup(\alpha,5)[3.12,\,\mathrm{b})]$ —— $(4^21^42^\kappa)\sqcup(442^{\kappa+1})\sqcup(442^{\kappa+1})$.

(4) $(\beta^4,5,3)=(\beta,3)[3.13,\,\mathrm{c})]\sqcup(\beta,\beta)[3.12,\,\mathrm{b})] \sqcup(\beta,5)[3.12,\,\mathrm{a})]$ —— $(41^22^\kappa)\sqcup(442^{\kappa+1})\sqcup(41^22^{\kappa+1})$.

(6) $(3^453)=(53)[3.13,\,\mathrm{a})]\sqcup(33)[3.9]\sqcup(33)[3.9]$ —— $(62)\sqcup(6)\sqcup(222)$.

(7) $(5^453)=(53)[3.13,\,\mathrm{c})]\sqcup(55)[3.12,\,\mathrm{a})]\sqcup(55)[3.12,\,\mathrm{b})]$ —— $(41^22)\sqcup(41^22^2)\sqcup(442)$.

(8) $(\alpha,\beta,5,3)=(\alpha,3)[3.13,\,\mathrm{c})]\sqcup(\beta,5)[3.12,\,\mathrm{a})]$ —— $(41^22^{\kappa+1})\sqcup(41^22^{\kappa+1})$.

(9) $(\alpha,3,5,3)=(53)[3.13,\,\mathrm{c})]\sqcup(\alpha,3)[3.13,\,\mathrm{c})]$ —— $(41^22)\sqcup(41^22^{\kappa+1})$.

(10) $(\beta,1,5,3)=(53)[3.13,\,\mathrm{c})]\sqcup(\beta,1)[3.14,\,\mathrm{b})]$ —— $(41^22)\sqcup(41^22^{\kappa+1})$.

(11) $(\beta,5,5,3)=(53)[3.13,\,\mathrm{c})]\sqcup(\beta,5)[3.12,\,\mathrm{a})]$ —— $(41^22)\sqcup(41^22^{\kappa+1})$.

4.3.2.

(1) $(o^2,1^3,5)=(15)[3.9]\sqcup(o,1,1)[3.17]\sqcup(o)[3.10,\,\mathrm{a})]$ —— $(41^2)\sqcup(332^\kappa)\sqcup(42^\kappa)$.

(2) $(o',1^3,5)=(15)[3.9]\sqcup(1,1)[3.8]\sqcup(o')[3.10,\,\mathrm{a})]$ —— $(41^2)\sqcup(2)\sqcup(42^{\kappa+1})$, $(21^35)[3.11]$ —— $(55)$.

(3) $(\alpha^4,1^3,5)=(\alpha,5)[3.12,\,\mathrm{b})]\sqcup(\alpha,1)[3.14,\,\mathrm{c})] \sqcup(\alpha,\alpha)[3.12,\,\mathrm{b})] \sqcup(11)[3.8]$ —— $(442^{\kappa+1})\sqcup(442^{\kappa+1})\sqcup(442^{\kappa+1})\sqcup(2)$.

(4) $(\beta^4,1^3,5)\,{=}\,(\beta,5)[3.12,\,\mathrm{b})]\sqcup(\beta,1)[3.14,\,\mathrm{c})] \sqcup(\beta,1)[3.14,\,\mathrm{c})] \sqcup(\beta,1)[3.14,\,\mathrm{c})]$ —— $(442^\kappa)\sqcup(442^\kappa)\sqcup(442^\kappa)\sqcup(442^\kappa)$.

(6) $(3^41^35)=(53)[3.13,\,\mathrm{a})]\sqcup(1113)[3.9]\sqcup(33)[3.9]$ —— $(62)\sqcup(6)\sqcup(222)$.

(7) $(5^41^35)=(1115)[3.8, 3.9]\sqcup(55)[3.12,\,\mathrm{a})]\sqcup(55)[3.12,\,\mathrm{b})]$ —— $(41^22)\sqcup(41^22^2)\sqcup(442)$.

(8) $(\alpha,\beta,1^3,5)=(\alpha,1)[3.14,\,\mathrm{c})]\sqcup(\beta,5)[3.12,\,\mathrm{b})] \sqcup(11)[3.8]$ —— $(442^{\kappa+1})\sqcup(442^\kappa)\sqcup(2)$.

(9) $(\alpha,3,1^3,5)=(1115)[3.8, 3.9]\sqcup(\alpha,3)[3.13,\,\mathrm{c})]$ —— $(41^22)\sqcup(41^22^{\kappa+1})$.

(10) $(\beta,1,1^3,5)=(1115)[3.8, 3.9]\sqcup(\beta,1)[3.14,\,\mathrm{b})]$ —— $(41^22)\sqcup(41^22^{\kappa+1})$.

(11) $(\beta,5,1^3,5)=(1115)[3.8, 3.9]\sqcup(\beta,5)[3.12,\,\mathrm{a})]$ —— $(41^22)\sqcup(41^22^{\kappa+1})$.

4.3.3.

(1) $(o^2,4,1^3,3)=(134)[3.18,\,\mathrm{a})]\sqcup(11)[3.8]\sqcup(o)[3.10,\,\mathrm{a})] \sqcup(o)[3.10,\,\mathrm{b})]$ —— $(422)\sqcup(2)\sqcup(42^\kappa)\sqcup(1^22^{\kappa+1})$.

(2) $(o',4,1^3,3)=(1,o',3)[3.16]\sqcup(41^2)[3.9]$ —— $(441^22^\kappa)\sqcup(33)$, $(1^33)[3.9]\sqcup(42)[3.9]$ —— $(6)\sqcup(6)$.

(3) $(\alpha^4,4,1^3,3)=(134)[3.18,\,\mathrm{a})]\sqcup(\alpha,1)[3.14,\,\mathrm{b})] \sqcup(\alpha,1)[3.14,\,\mathrm{b})]\sqcup(\alpha,\alpha)[3.12,\,\mathrm{a})]$ —— $(422)\sqcup(41^22^\kappa)\sqcup(41^22^\kappa)\sqcup(41^22^\kappa)$.

(4) $(\beta^4,4,1^3,3)=(134)[3.18,\,\mathrm{a})]\sqcup(\beta,1)[3.14,\,\mathrm{c})] \sqcup(\beta,1)[3.14,\,\mathrm{c})]\sqcup(\beta,\beta)[3.12,\,\mathrm{a})]$ —— $(422)\sqcup(442^\kappa)\sqcup(442^\kappa)\sqcup(41^22^\kappa)$.

(6) $(3^441^33)=(134)[3.18,\,\mathrm{a})]\sqcup(13)[3.8]\sqcup(13)[3.8] \sqcup(33)[3.9]$ —— $(422)\sqcup(13)\sqcup(13)\sqcup(41^2)$.

(7) $(5^441^33)=(134)[3.18,\,\mathrm{a})]\sqcup(15)[3.9]\sqcup(15)[3.9] \sqcup(55)[3.12,\,\mathrm{a})]$ —— $(422)\sqcup(41^2)\sqcup(41^2)\sqcup(41^22^2)$.

(8) $(\alpha,\beta,4,1^3,3)=(134)[3.18,\,\mathrm{a})]\sqcup(\alpha,1)[3.14,\,\mathrm{b})] \sqcup(\beta,1)[3.14,\,\mathrm{c})]$ —— $(422)\sqcup(41^22^\kappa)\sqcup(442^\kappa)$.

(9) $(\alpha,3,4,1^3,3)=(134)[3.18,\,\mathrm{a})]\sqcup(11)[3.8]\sqcup(\alpha,3) [3.13,\,\mathrm{c})]$ —— $(422)\sqcup(2)\sqcup(41^22^{\kappa+1})$.

(10) $(\beta,1,4,1^3,3)\,{=}\,(134)[3.18,\,\mathrm{a})]\sqcup(11)[3.8] \sqcup(\beta,1)[3.14,\,\mathrm{b})]$ —— $(422)\sqcup(2)\sqcup(41^22^{\kappa+1})$.

(11) $(\beta,5,4,1^3,3)=(134)[3.18,\,\mathrm{a})]\sqcup(11)[3.8] \sqcup(\beta,5)[3.12,\,\mathrm{a})]$ —— $(422)\sqcup(2)\sqcup(41^22^{\kappa+1})$.

4.3.4.

First we prove 3-representability for permutations (consisting of cycles $(13)$ and blocks) that are not contained in a wider (in comparison to $(d)$) family of permutations, the so-called $\widehat{d}$-family: $(3^i2^j1^k)$, where $i\equiv1\,(\operatorname{mod}4)$, $j\geqslant0$, and $k\equiv1\,(\operatorname{mod}4)$. Thus, to begin with, we assume that cycles in the blocks $(o')$ have length at least 6, and defer the considerations of the blocks $(2)$, $(3^4)$ and $(1^4)$ to the end of § 4.3.4.

(1) $(o^2,1,3)=(o,1,3)[3.16]\sqcup(o)[3.10,\,(\mathrm{b})]$ —— $(441^22^{\kappa+1})\sqcup(1^22^{\kappa+1})$. In Proposition 3.16 the length of the $o$-cycle is al least 6, and in the case of length 4 we have $(4^213)=(413)[3.18,\,\mathrm{a})]\sqcup(4)[3.8]$ —— $(422)\sqcup(4)$.

(3) $(\alpha^4,1,3)=(\alpha,1)[3.14,\,\mathrm{b})]\sqcup(\alpha,3)[3.13,\,\mathrm{c})] \sqcup(\alpha,\alpha)[3.12,\,\mathrm{b})]$ —— $(41^22^\kappa)\sqcup(41^22^{\kappa+1})\sqcup(442^{\kappa+1})$.

(4) $(\beta^4,1,3)=(\beta,1)[3.14,\,\mathrm{c})]\sqcup(\beta,3)[3.13,\,\mathrm{c})] \sqcup(\beta,\beta)[3.12,\,\mathrm{a})]$ —— $(442^\kappa)\sqcup(41^22^\kappa)\sqcup(41^22^\kappa)$.

(7) $(5^413)=(15)[3.9]\sqcup(35)[3.13,\,\mathrm{c})]\sqcup(55)[3.12,\,\mathrm{b})]$ —— $(41^2)\sqcup(41^22)\sqcup(442)$.

(8) $(\alpha,\beta,1,3)=(\alpha,1)[3.14,\,\mathrm{b})]\sqcup(\beta,3)[3.13,\,\mathrm{c})]$ —— $(41^22^\kappa)\sqcup(41^22^\kappa)$.

(9) $(\alpha,3,1,3)=(\alpha,1)[3.14,\,\mathrm{c})]\sqcup(3,3)[3.9]$ —— $(442^{\kappa+1})\sqcup(222)$.

(10) $(\beta,1,1,3)=(\beta,1)[3.14,\,\mathrm{a})]\sqcup(1,3)[3.8]$ —— $(132^\kappa)\sqcup(13)$.

(11) $(\beta,5,1,3)=(\beta,3)[3.13,\,\mathrm{a})]\sqcup(1,5)[3.9]$ —— $(62^\kappa)\sqcup(6)$.

Next we turn to the $\widehat{d}$-family of permutations, which contains the 3-representable permutation $(3^51^5)=(3^21^2)[3.19]\sqcup(33)[3.9]\sqcup(31^3)[3.9]$ —— $(44)\sqcup(6)\sqcup(6)$. By adding any block to a 3-representable permutation we obtain a 3-representable permutation, which we do not mention explicitly below. In view of this, the permutations $(3^i2^j1^k)$ in the $\widehat{d}$-family in which $i\geqslant5$, $j\geqslant0$ and $k\geqslant5$ are 3-representable. As a result (apart from the permutations $(32^j1)$ in the family $(d)$, $j\geqslant0$), only permutations in two disjoint subfamilies of the $\widehat{d}$-family remain problematic: the $d'$-family of permutations of the form $(32^j1^k)$, where $j\geqslant0$ and $k\equiv1\,(\operatorname{mod}4)$, $k\geqslant5$, and the $d''$-family of permutations of the form $(3^i2^j1)$, where $i\equiv1\,(\operatorname{mod}4)$, $i\geqslant5$, and $j\geqslant0$.

The $d'$-family contains the 3-representable permutation $(32^21^5)=(31^3)[3.9]\sqcup(2^21^2)[3.9]$ —— $(6)\sqcup(6)$. Thus, all permutations in this family are 3-representable, with the exception of $(321^k)$ and $(31^k)$, where $k\equiv1\,(\operatorname{mod}4)$, $k\geqslant5$, which belong to the family (d).

The $d''$-family contains the 3-representable permutation $(3^52^21)$, which is close to $(6^24^2)$. This closeness is established in Figure 8. As a result, all permutations in the $d''$-family that do not belong to the $d'''$-family of permutations $(3^i2^j1)$, where $i\equiv1\,(\operatorname{mod}4)$, $i\geqslant5$, and $j\in\{0,1\}$, are 3-representable. The last family contains the 3-representable permutation $(3^521)=(123)[3.9]\sqcup(33)[3.9]\sqcup(33)[3.9]$ —— $(42)\sqcup(41^2)\sqcup(222)$. Thus, all permutations in the $d'''$-family that do not belong to the $d^{\mathrm{iv}}$-family of permutations $(3^i1)$, where $i\equiv1\,(\operatorname{mod}4)$, $i\geqslant5$, are 3-representable. The $d^{\mathrm{iv}}$-family contains the 3-representable permutation $(3^91)=(13)[3.8]\sqcup(3^4)[3.20] \sqcup(33)[3.9]\sqcup(33)[3.9]$ —– $(13)\sqcup(1362)\sqcup(6)\sqcup(222)$. Thus, all permutations in the $d''$-family are also 3-representable, with the exception of $(3^51)$, which belongs to the family (d).

The proof that each permutation outside the families (a)–(d) is 3-representable is complete.

Remark 1. For quite a while the statement of Theorem 1 also contained the problematic $d'''$-family of permutations, for which (with the exception of the permutation $(3^51^1)$) we could prove neither 3-representability nor the impossibility of a 3-representation. Page 15 of Tuzhilin’s paper [29] (pointed out to the author by B. A. Pogorelov) contains a computer-generated table presenting the numbers of $i$-representable, $i=2,3,4,5$, classes of permutations in the group $S_{2n}$ for $n=1,\dots,10$. From this table we can conclude that for $n=9$ four classes are not 3-representable, to which the permutations $(5^13^12^5)$ from the family (a), $(4^13^11^{11})$ from (c), and $(3^12^71^1)$ and $(3^12^11^{13})$ from (d) obviously belong. Hence the fifth permutation $(3^52^11^1)$ in the problematic $d'''$-family is 3-representable. Surprisingly, Proposition 3.9 is sufficient to prove this fact. Afterwards, we established Proposition 3.20 on the closeness $(3^4)$ —— $(1^13^16^12^1)$, which enabled us (using additionally only Proposition 3.9) to prove the 3-representability of the permutation $(3^91^1)$, and thus the 3-representability of the remaining permutations $(3^i1^1)$, for $i\equiv1\,(\operatorname{mod}4)$, $i\geqslant13$. Thus, only the non-3-representable permutation $(3^51^1)$ remained of the problematic $d'''$-family, which could naturally be included in the family (d).

4.4.

Below, in §§ 4.4.1–4.4.4 we prove that no permutations in the families (a)–(d), respectively, are 3-representable. Every time, given a permutation $\pi$, we have to prove that there are no 2-representable permutations among the ones close to $\pi$. When embedding cycles of $\pi$ in the environment of 2-cycles of a pairwise-cycle permutation $p$, we have to provide for all possible mutual arrangements of these cycles. In this connection we adhere to the model where the cycles of $\pi$ are prescribed and fixed, and the 2-cycles of the permutation $p$ float freely, like water molecules around a crystal lattice.

4.4.1.

Let $\pi=(5^13^12^i)$, $i\geqslant0$. All seven ways of embedding the cycles of $\pi$ in the set of transpositions of a pairwise-cycle permutation $p$ are shown in Figure 9.

Dashed lines in Figure 9 denote chains of alternating 2-cycles of the permutations $p$ and $\pi$, beginning and ending at a 2-cycle of $p$, so that the end of a chain cannot coincide with its beginning. There are $4=(5+3)/2$ chains in total. We characterize such a chain by its weight $s\geqslant0$ when it consists of $s+1$ 2-cycles of $p$ and $s$ 2-cycles of $\pi$. Before this, in § 3, we considered only chains of weight $s=0$, which consisted of one 2-cycle

of the permutation $p$. The embedding $(\mathrm{e})$, different from $(\mathrm{d})$ by the orientation of the 3-cycle, is shown in Figure 11.

An example of a chain

of weight $s=3$ with ends $B$ and $C$ is shown in Figure 10. In this figure the vertices $A$, $B$, $C$ and $D$ lie on cycles of the permutation $(5^1)\sqcup(3^1)$.

Generally speaking, chains without ends are possible in the form of simple closed chains (cycles) of $s$ 2-cycles of $p$ and $s$ 2-cycles of $\pi$ alternating between themselves, $s\geqslant1$. We exclude them from consideration in view of Proposition 3.4. Then each of the $2n$ points on which the permutation $\pi = (532^i)$ acts, where $n = i+4$, belongs to one of the four chains with ends at cycles of the permutation $(5^1)\sqcup(3^1)$.

It is clear from Figure 10 that the values of $s$ labelled on dotted edges denoting chains

provide a simple way to compute the cycle structure of the permutation $\pi p$ from the cycle structure of the permutation $\check{\pi}\check{p}$, where the permutations $\check{\pi}$ and $\check{p}$ are obtained from $\pi$ and $p$, respectively, by eliminating the 2-cycles

and

contained in the chains, and every chain

is regarded as a 2-cycle

of $\check{p}$. Every arc

of the permutation $\check{\pi}\check{p}$ corresponds to a directed chain of $1+s$ arcs in the permutation $\pi p$. The number of cycles in $\pi p$ does not depend on the values of $s\geqslant0$, which only affect the lengths of cycles.

Let us prove that Figure 9 shows all possible cases of embedding the permutation $\pi=(5^13^12^i)\in S_{2n}$, $n=4+i$, $i\geqslant0$, in the environment of 2-cycles of the permutation $p$. Each of the $2n$ points on which $\pi$ acts belongs to just one of the four chains as one of its interior or terminal vertices lying on cycles of the permutation $(5^1)\sqcup(3^1)$. Figures 9, (a)–(c) present the cases when there is only one chain with ends on the different cycles $(5^1)$ and $(3^1)$. Figures 9, (d)–(g) present the cases when all three chains starting from the 3-cycle end at the 5-cycle. Up to cyclic shifts (of the 5-cycle), the three vertices $\alpha$, $\beta$ and $\gamma$ which are the endpoints of the three chains can be positioned in two ways on the 5-cycle: either these vertices follow one another (cases (d) and (e)), or only two vertices (out of three) are adjacent (cases (f) and (g)). One cyclic ordering of the vertices $\alpha$, $\beta$ and $\gamma$ is induced by the ordering of the beginning points of the corresponding chains, and another by their embedding in the 5-cycle. As for the latter, there are two possible orders, which correspond to two possible necklaces of three beads. In Figure 9, (e), (g), to avoid intersections of chains, we depart from the general rule of arranging the vertices of cycles clockwise, which we have followed so far.

Now we verify the impossibility of 3-representations for the permutations $\pi=(5^13^12^i)$, $i\geqslant0$. We refer to Figure 11 only in the case (e).

The lengths of the four cycles of the permutation $\pi p$ in Figure 11 are $l_1=1+s_1$, $l_2=3+s_4+s_2+s_1$, $l_3=2+s_3+s_4$ and $l_4=2+s_2+s_3$. We have three ways to combine them into possibly coinciding pairs. For example, for $l_1=l_4$ and $l_2=l_3$ we obtain $s_1=1+s_2+s_3$ from the first equality, and then from the second equality we obtain $3+s_4+s_2+1+s_2+s_3=2+s_3+s_4$, which is impossible for $s_i\geqslant0$, $i=1,2,3,4$. For $l_1=l_2$, $l_3=l_4$ and for $l_1=l_3$, $l_2=l_4$ we arrive at similar contradictions.

The other cases in Figure 9 are analyzed in just the same way. Cases (c), (d), (f) and (g) are particularly easy to consider: then the permutations $\pi p$ have only two cycles, and their lengths cannot be equal.

The technique we demonstrate here enabled us to find the 3-representable permutation $(3^52^21^1)$ in Figure 8. For a particular pairwise-cycle permutation acting on the 16 vertices of the permutation $(3^51^1)$, we augmented $8=(3\times5+1)/2$ of its 2-cycles to chains with weights of the general form $s_1,\dots,s_8$. For one of the three partitions of the four cycles of the supposed permutation of $\pi p$ into pairs of potentially equal length, we found a confirming solution for $(s_1,\dots,s_8)$, involving six zeros and two ones, which correspond to the chains

and

in Figure 8.

4.4.2.

Let $\pi=(5^11^i)$, $i\equiv3\,(\operatorname{mod}4)$. We restrict ourselves to embeddings of cycles of the permutation $\pi$ in the set of transpositions of a pairwise-cycle permutation $p$ for which the number of fixed points of the product $\pi p$ (the number of 1-cycles) is even, that is, equal to 2 or 0. Otherwise $\pi p$ is certainly not a 2-representable permutation. A 1-cycle of $\pi p$ occurs when a 2-cycle of $p$ is parallel to an arc of $\pi$. In addition, only an odd number of vertices of a 5-cycle of the permutation $\pi$ can belong to a 2-cycle of $p$ the other end of which is a fixed point of $\pi$, and three such vertices cannot follow one another on a 5-cycle to exclude the case of a unique 1-cycle of $\pi p$. The only possible case when the permutation $\pi p$ has two 1-cycles is shown in Figure 3, (a), where the closeness $(1^15^1)$ —— $(1^24^1)$ is established. Two situations without fixed points are shown in Figure 12. The last (fourth) possible case (which is not shown) corresponds to the closeness relation $(1^55^1)$ —— $((10)^1)$ of general nature: $(1^kk^1)$ —— $((2k)^1)$, $k\geqslant2$, as established in Figure 4, (a) for $k=3$ and in Figure 13, (c) for $k=4$.

In all four cases there is a cycle of the permutation $\pi p$ which has no pair with the same length, since outside the fragments under consideration the permutation $\pi p$ has cycles of length 2. In each fragment shown in Figure 12 and in subsequent figures that follow we indicate where possible the lengths of cycles formed by dotted lines.

4.4.3.

Let $\pi=(4^13^11^i)$, $i\equiv3\,(\operatorname{mod}4)$. As in § 4.4.2, we list all possible embeddings of cycles of the permutation $\pi$ in the set of 2-cycles of the permutation $p$. We begin with the case when $p$ has no 2-cycles with one vertex on the 4-cycle and the other on the 3-cycle of the permutation $\pi$, that is, the 3-cycle and the 4-cycle are embedded independently of each other. There are two possible embeddings of the 3-cycle. One is described in Proposition 3.8, and the other is shown in Figure 4, (a). We obtain the closeness relations $(1^13^1)$ —— $(1^13^1)$ and $(1^33^1)$ —— $(6^1)$, respectively. For the embedding of the 4-cycle we have five options, three of which are shown in Figure 13, and the other two in Figure 2, (d), (e), point out the closeness relations $(4^1)$ —— $(1^22^1)$ and $(4^1)$ —— $(4^1)$.

Judging by the cycles $(1^15^1)$, $(3^2)$ and $(8^1)$ formed by dotted lines in Figure 13, no matter which of the $10=2\cdot 5$ combinations of embeddings of the 3-cycle and 4-cycle we consider, the permutation $\pi p$ always has a cycle without a pair of equal length.

In the remaining Figures 14–17 it is assumed that the permutation $p$ has a 2-cycle with vertices from both the 4-cycle and 3-cycle of the permutation $\pi$. In all figures the permutation $\pi p$ has a cycle without a pair of equal length.

In Figure 14 it is assumed that the permutation $\pi p$ has 1-cycles, and only an even number of these are admitted, so that there can only be two 1-cycles.

In Figures 15–17 it is assumed that the permutation $\pi p$ has no 1-cycles, and the permutation $p$ has, respectively, one, two and three 2-cycles with vertices from both the 4-cycle and 3-cycle of the permutation $\pi$.

4.4.4.

The proof of the impossibility of a 3-representation for permutations in the families (d${}_{a}$), (d${}_{b}$) and (d${}_{c}$) repeats the arguments in §§ 4.4.1–4.4.3 in a simpler form.

It remains to show that the permutation $\pi_0=(3^51^1)$ from the family $(d_0$) is not 3-representable. We limit ourselves to listing the possible embeddings of cycles of $\pi_0$ in the environment of the $8=(3\times5+1)/2$ transpositions forming the pairwise-cycle permutations $p$. We often leave to the reader the simple proof of the fact that the cycles in the corresponding product $\pi_1=\pi_0p$ do not combine into pairs of equal length. We begin with the permutations $p$ for which the number of connected components on 16 vertices is maximum possible, where we consider vertices of the same cycle of $\pi_0$ or the same cycle of $p$ to be connected. Every connected component has an even number of vertices (which is twice the number of the corresponding transpositions in $p$). On a component containing one 3-cycle of $\pi_0$ the permutation $\pi_1$ has a unique fixed point (see Proposition 3.8). Then $\pi_1$ must have another fixed point on a connected component containing two 3-cycles of $\pi_0$, on which yet another (third) fixed point of $\pi_1$ also inevitably occurs (see Proposition 3.9). A similar conclusion about the third connected component produces five fixed points of $\pi_1$.

Now let the cycles of the permutations $\pi_0$ and $p$ lie on two connected components. On these components the 3-cycles can be placed in accordance with the scheme $3+2$ or $1+4$. In the first case the loop of the permutation $\pi_0$ is positioned on the component containing three 3-cycles. On the other component the permutation $(3^2)$ is close only to the permutations $(2^3)$, $(6^1)$ and $(4^11^2)$ (see Proposition 3.9). On the first component we call the 3-cycle adjacent to the loop the first cycle. It is adjacent either to two 3-cycles or to a single cycle, which we call the second cycle and which is adjacent to the remaining third 3-cycle. There must be a fixed point of $\pi_1$ on the third 3-cycle and an even number of such points on the other component. Let the first 3-cycle be adjacent to two 3-cycles, which need not be adjacent to each other, in which case we have the closeness relation $(3^31^1)$ —— $(8^11^2)$, and $\pi_1$ has no cycle of length eight on the other component. Let the second and third 3-cycles be adjacent. Then two transpositions of the permutation $p$ can be arranged in two ways between pairs of vertices of these 3-cycles. In one case we have the closeness relation $(3^31^1)$ —— $(5^13^12^1)$, and in the other we have $(3^31^1)$ —— $((10)^1)$. The permutation $\pi_1$ has no cycles of lengths 10, 5 or 3 on the other connected component.

Let one of the two connected components have one 3-cycle and the other have four such cycles. On the first component we have the closeness relation $(3^11^1)$ —— $(3^11^1)$ (see Proposition 3.8). Therefore, on the other component the permutation $\pi_1$ must have odd numbers of cycles of length 1 and 3. If the other component of the permutation $\pi_1$ has three fixed points (and there can be no more such points), then we have the closeness relation $(3^4)$ —— $(9^11^3)$, and no second 3-cycle can be found in $\pi_1$. Let $\pi_1$ have a fixed point on the other component, which lies on a 3-cycle of $\pi_0$; we call it the first 3-cycle. It is adjacent to the second 3-cycle, which is adjacent to the two remaining 3-cycles. (We occur in a situation discussed already.) If the last pair of 3-cycles is not adjacent, then we have the closeness relation $(3^4)$ —— $(9^11^3)$, but if it is, then we have two cases of adjacency and, accordingly, two types of closeness relation, $(3^4)$ —— $(6^11^13^12^1)$ and $(3^4)$ —— $((11)^1,1)$. On the first connected component $\pi_1$ does not have cycles of length 9, 6, or 11. If the second 3-cycle were adjacent (apart from the first cycle) only to the third 3-cycle, which would be adjacent to the fourth, then $\pi_1$ would have its second fixed point (on the connected component under consideration) on this cycle, which would be a contradiction.

It remains to consider the situation when the cycles of $\pi_0$ and $p$ form a single connected component of 16 points. We represent 3-cycles of the permutation $\pi_0$ on the plane by triangles oriented clockwise and denoted by $\vartriangle_i$, $i=1,2,3,4,5$. The 3-cycle $\vartriangle_1$ adjoins a fixed point of $\pi_0$. We assume first that $\vartriangle_1$ is only adjacent to the triangle $\vartriangle_2$ (we consider this as a double adjacency, implemented by two transpositions of $p$). Then $\vartriangle_2$ is adjacent to only one another triangle $\vartriangle_3$. But $\vartriangle_3$ is already adjacent to two triangles, namely, $\vartriangle_4$ and $\vartriangle_5$. (If $\vartriangle_3$ were only adjacent to $\vartriangle_2$ and $\vartriangle_4$, which would be adjacent to $\vartriangle_5$, then, a single fixed point of the permutation $\pi_1$ would inevitably occur on $\vartriangle_5$.) Six cases arise now. Two cases arise when $\vartriangle_4$ and $\vartriangle_5$ are not adjacent, since the double adjacency between $\vartriangle_1$ and $\vartriangle_2$ can be realized in two ways. In the other four cases $\vartriangle_4$ and $\vartriangle_5$ are adjacent, namely, doubly adjacent. As the permutation $\pi_1$, in these six cases we obtain $((12)^12^11^2)$, $(1^24^1(10)^1)$, $(9^13^12^2)$, $((14)^12^1)$, $(4^17^13^12^1)$ and $(4^1(12)^1)$, respectively.

Now let the triangle $\vartriangle_1$ be adjacent to $\vartriangle_2$ and to $\vartriangle_3$. First assume that $\pi_1$ has two fixed points $A$ and $B$ (there cannot be four fixed points). The following cases are possible: (1) $\{A,B\}\subset\vartriangle_4\sqcup\vartriangle_5$; (2) $A\in\vartriangle_2\sqcup\vartriangle_3$ and $B\in\vartriangle_4\sqcup\vartriangle_5$. In the first case there are four ways to implement the adjacency between the triangles $\vartriangle_2$ and $\vartriangle_3$ (which must be adjacent). Then the permutations $(5^19^11^2)$, $((11)^13^11^2)$ and $(8^16^11^2)$ (twice) are implemented. In the second case there also are four ways. If, for example, $A\in\vartriangle_2$ and $B\in\vartriangle_5$, then the triangles $\vartriangle_4$ and $\vartriangle_5$ are adjacent, and $\vartriangle_3$ and $\vartriangle_4$ are doubly adjacent. Both this double adjacency and the choice of a triangle for the point $A$ can be implemented in two ways. In the second case both the permutations $((12)^12^11^2)$ and $(9^15^11^2)$ are implemented twice as $\pi_1$.

Now suppose that $\pi_1$ has no fixed points. Then the triangles $\vartriangle_4$ and $\vartriangle_5$ must be adjacent, since only four vertices of the triangles $\vartriangle_2$ and $\vartriangle_3$ are vacant for their vertices. The adjacency of $\vartriangle_4$ to $\vartriangle_5$ can be implemented either by one or two transposition of the permutation $p$. In the latter case the triangles $\vartriangle_2$ and $\vartriangle_3$ must also be adjacent, and this adjacency can be implemented in four ways. The double adjacency of $\vartriangle_4$ to $\vartriangle_5$ can also be realized in two ways. As a result, we have $8=4\times2$ possible embeddings of the permutation $\pi_0$ in the environment of eight transpositions of the permutation $p$, and we obtain the following permutations as possible options for $\pi_1$: $(7^13^14^12^1)$, $((14)^12^1)$ twice, $(5^24^12^1)$, $((13)^1,3^1)$, $(9^17^1)$ (twice) and $(5^1(11)^1)$.

Finally, let the triangles $\vartriangle_4$ and $\vartriangle_5$ be connected by one transposition of the permutation $p$. Then the triangles $\vartriangle_2$ and $\vartriangle_3$ are not adjacent, and we obtain $24=4!$ possible embeddings of $\pi_0$ into eight transpositions. These embeddings provide the following possibilities for $\pi_1$: $(7^15^12^2)$, $(7^19^1)$, $(6^14^13^2)$ and $((11)^1,5^1)$, all of which occur twice, and $((14)^12^1)$, $((12)^14^1)$, $((13)^13^1)$ and $((10)^16^1)$, occurring four times each.

While we have exhausted all possibilities for $\pi_1$ close to $\pi_0=(3^51^1)$, we have not obtained a 2-representable permutation, and thus the permutation $(3^51^1)$ is not 3-representable. This completes the proof of Theorem 1.

4.5.

Because the above proof of Theorem 1 is constructive, there exists a polynomial algorithm determining the 3-representability of a permutation $\pi\in S_{2n}$ and finding at least one 3-representation for it in the case of its 3-representability. A brief analysis of our proof of Theorem 1 confirms this conclusion. Throughout the proof, the closeness relations established in § 3 for pairs of permutations were used in fact as a ‘multiplication table’. The closeness relations for $n\in\{1,2,3\}$ were exhaustively listed in Propositions 3.8 and 3.9. Propositions 3.10 and 3.12–3.17 present 13 closeness relation between permutations with unbounded lengths of cycles, and Propositions 3.11 and 3.18–3.20 present five unique closeness relations for permutations with concrete lengths of cycles. The proof of 3-representability itself consists of constructing 97 so-called blocks in the form of permutations, for which close 2-representable permutations are explicitly presented. The number of cycles in these blocks varies from 1 to 10. The possible lengths of cycles in most blocks are unbounded. The cycles themselves are divided into seven types by length. The particular number of 97 can certainly be reduced, for example, in § 4.3.4 we leave the permutation $(3^52^21^1)$ out of consideration and limit ourselves to the permutation $(3^52^11^1)$ as a block, since $(3^52^21^1)=(3^52^11^1)\sqcup(2^1)$. Remark 1 suggests that the block $(3^52^21^1)$ must be kept. In the author’s opinion, we should not expect a significant reduction in the number of necessary blocks. Every permutation $\pi\in S_{2n}$ of the same parity as $n$ that is not related to the families (a)–(d) can be partitioned (see Proposition 3.2) into blocks from the distinguished set of 97 blocks. The number 97 is formed as follows in the process of the proof: 11 basic blocks are produced by Propositions 4.1–4.8, nine blocks related to reduced permutations are produced in Proposition 4.9, two, seven and eight blocks are obtained in §§ 4.4.1, 4.4.2 and 4.4.3, respectively, two, four and nine blocks are obtained in §§ 4.2.1, 4.2.2 and 4.2.3, respectively, and, finally, 11, 10, 10 and 14 blocks are obtained in §§ 4.3.1, 4.3.2, 4.3.3 and 4.3.4, respectively.

The author connects his hopes for possible simplifications of the proof of the theorem (at least as concerns the impossibility of a 3-representation for permutations in the families (a)–(d)) with Ree’s theorem (see [25]–[27]) and the machinery from [28].

4.6. Proof of Moran’s Theorem

Let $|X|=\infty$, $\pi\in S_X$ and, to begin with, let the set of pairs $\{(x,\pi(x))\mid x\in X,\, \pi(x)\neq x\}$ be infinite. We claim that then $\pi=p_1p_2p_3$. Consider a countable set of distinct elements $x_1,x_2,x_3,\dots$ for which $\pi(x_i)\neq x_i$, $i\in\mathbb{N}$, and $\{x_1,x_2,x_3,\dots\}\cap\{\pi(x_1),\pi(x_2),\pi(x_3),\dots\}=\varnothing$. Set $Y=\{x_2,x_4,x_6,\dots\}$. Consider a family of mutually disjoint subsets of $Y$ such that the number of subsets $Z$ of any fixed cardinality $i=1,2,\dots,\infty$ is infinite. For every subset $Z=\{z_0,z_1,\dots,z_{i-1}\}$ we consider $i$ transpositions of the form $(\pi(z_{j}),z_{j+1\,(\operatorname{mod}i)})$ for the permutation $p_3$, $j\in\mathbb{Z}_i$. For $i=\infty$ we consider the transpositions $(\pi(z_{j}),z_{j+1})$, $j\in\mathbb{Z}$. On the remaining infinite subset of $X$ we fix transpositions for $p_3$ arbitrarily. For every $i=1,2,3,\dots,\infty$ the permutation $\pi p_3$ has infinitely many cycles of length $i$, and we group them into pairs. By Proposition 3.4 we have $\pi p_3=p_1p_2$ for some $p_1$ and $p_2$.

Now let $X$ consist almost entirely, with the exception of finitely many points, of fixed points of a permutation $\pi\in S_X$. We present two ways of proving the 3-representability of $\pi\in S_X\setminus\{(5^11^\infty),(3^11^\infty),(4^13^11^\infty),(2^13^11^\infty)\}$. The first way is a direct consequence of Theorem 1. Let $\sigma\in S_k$ be a permutation consisting of all cycles of $\pi$ of finite length not less than 2, and let $i\geqslant2$ be such that $k+i$ is even and the parity of $(k+i)/2$ coincides with that of $\sigma$. Then the permutation $\sigma\sqcup(1^i)$ of the same parity is 3-representable, and therefore $\pi$ is too, because $(1^4)$ is 3-representable. Otherwise, if $\sigma\sqcup(1^i)$ is not 3-representable, then $\sigma\sqcup(1^i)$ belongs to one of the families (b), (d${}_{b}$), (c) and (d${}_{c}$) by Theorem 1, which leads to a contradiction: $\pi\in\{(5^11^\infty),(3^11^\infty),(4^13^11^\infty),(2^13^11^\infty)\}$.

Another direct proof of 3-representability for $\pi\,{\in}\, S_ X\setminus\{(5^11^\infty),(3^11^\infty),(4^13^11^\infty),(2^13^11^\infty)\}$, which is presented below, has the same structure as the argument in the proof of Theorem 1. By a block we mean a 3-representable permutation consisting of finitely many cycles of finite length complemented (which is assumed without special mention) by an infinite number of quadruples of cycles of length 1. By Propositions 3.10, (b) and 3.8 cycles of even length are blocks. By Proposition 3.14, (c), cycles of odd length which is not less than 7 are blocks. We consider blocks of these two types as basic blocks. A permutation is said to be reduced if it does not contain basic blocks. Cycles in a reduced permutation have length 1, 3 or 5.

Proof. By Propositions 3.4, 3.9 and 3.1, 3.2 the permutation $(3^21^\infty)$ is 3-representable because it is close to $(2^\infty)$, which is 2-representable (by Proposition 3.4). Thus, $(3^21^\infty)$ is a block. According to § 4.1.3, the permutation $(3^31^\infty)=(1^3 3^31^\infty)$ is also a block. We can similarly see that the permutations $(5^21^\infty)$ and $(5^31^\infty)=(1^1 5^31^\infty)$ are blocks. According to § 4.3.1, (5), the permutation $(3^15^11^\infty)=(1^45^13^11^\infty)$ is a block. Eliminating blocks of these five types from the permutation in question we obtain Proposition 4.12.

By Proposition 3.16 the pair of a 3-cycle and a cycle of even length distinct from 2 and 4 is a block. By Proposition 3.13, (b) the pair of a 3-cycle and a cycle of odd length not less than 9 is a block. By § 4.3.4, (10) the permutation $(371^\infty)=(1^2371^\infty)$ is a block. By Proposition 3.12, (b) the pair of a 5-cycle and an odd cycle is a block. By the last line in § 4.2.2 the pair of a 5-cycle and a cycle of even length which is a multiple of 4 is a block. According to § 4.3.2, (2), the pair of a 5-cycle and a cycle of even length not less than 6 which is not a multiple of 4 is a block. By Proposition 3.11 the permutation $(5^12^11^\infty)=(1^32^15^11^\infty)$ is a block.

Thus, only the permutations $(5^11^\infty)$, $(3^11^\infty)$, $(4^13^11^\infty)$ and $(2^13^11^\infty)$ can turn out not to be 3-representable. Now we prove the impossibility of a 3-representation for these permutations. For a contradiction suppose that we have $\pi=p_1p_2p_3$ for one of them, and let $X_0=\{x\in X\mid \pi(x)\neq x\}$. Consider an undirected graph on the vertex set $X$ with edges in the form of 2-cycles of $p_1$, $p_2$ and $p_3$, coloured with the colours $1$, $2$ and $3$, respectively. Let $X_1$ be the set of vertices in $X$ that are connected to some vertex in $X_0$ by a path with at most four edges. Every vertex $x\in X\setminus X_1$ is fixed and therefore lies on a triangle with edges of different colours. The other two vertices of this triangle are also fixed and lie on some other triangles with edges of different colours, which gives rise to a fourth vertex. This quadruple of vertices can be represented by the vertices of a tetrahedron whose opposite edges are similarly coloured. Excluding from $X$ the vertices of all such tetrahedra we obtain a finite set $X_{01}$ containing $X_0$ for which, on the one hand, $\pi|_{X_{01}}$ is a 3-representable permutation and, on the other hand, this permutation is contained in one of the families (b), $(\mathrm{d}_\mathrm{b})$, (c) and $(\mathrm{d}_\mathrm{c})$. This contradicts Theorem 1, which completes the proof of the proposition.

Moran’s theorem is proved. Here we have used one third of the ‘multiplication table’ of Propositions 3.8–3.20 and employed 11 blocks, instead of 96 blocks in the proof of Theorem 1.

§ 5. Relation to cubic graphs

To a cubic graph $\Gamma$ on the vertex set $\{1,\dots,2n\}$ which is edge-coloured with three colours so that every vertex is incident to three differently coloured edges (see [30])we can assign a triple of pairwise-cycle permutations $p_0$, $p_1$, $p_2$ in a naturally way, where each permutation in the triple consists of the transpositions of the endpoints of edges of the same colour. The cycle structure of the product of these permutations (taken in an arbitrary order) is an invariant of such graphs with respect to isomorphisms preserving the colouring.

By analogy with the construction of coordinate charts on two-dimensional surfaces (see [31]), every cycle of the permutation $\pi=p_0p_1p_2$ corresponds here to a thrice longer cycle $C$ formed by consecutive triples of arcs of the form $i\to p_0(i)\to p_1(p_0(i))\to p_2(p_1(p_0(i)))=\pi(i)$, $i\in\{1,\dots,2n\}$, which can be regarded as the boundary of a 2-cell or of several 2-cells and 0-cells, connected by line segments $i$ —— $k$ in the case when both the arcs $i\to k$ and $k\to i$ of the same colour lie on $C$. Gluing these cells together over all cycles of the permutation $\pi$ forms a two-dimensional polyhedron (see [32]) consisting of vertices, line segments, spheres and spheres with handles.