Permutation Groups Generated by γ-Cycles

Abstract

A $\gamma$-cycle is a cycle of the form $(i+1,i+2,\dots ,i+m)$ in the symmetric group $S_n$. We study the subgroups of $S_n$ generated by several sets of $\gamma$-cycles. Our mathematical development is strongly supported by computational experiments and proofs based on do-it-yourself programming with the logic-based language Maude.

1. Introduction

Permutation group theory constitutes one of the origins of group theory, and is currently a very developed mathematical area. From the rather rich literature on the subject, we recommend the works [1,2,3,4,5].

Basic facts in this theory include that every permutation in the symmetric group $S_n$ decomposes as a product (composition) of disjoint cycles and that each cycle is a product of transpositions, with the immediate consequences that each permutation itself decomposes as a product of transpositions. Moreover, it is well known that the adjacent transpositions $(i,i+1)$ are in fact enough to generate the whole of $S_n$. In computer science, this is represented by the rather famous bubble sort algorithm. Such adjacent transpositions are the simplest form of γ-cycles, which are cycles $(i+1,i+2,\dots ,i+m)$ with consecutive entries. This terminology is introduced in this article by adopting the abbreviation of ‘consecutive’ by $\gamma$, as this is the Greek alphabet correspondent of ‘c’, which is the first letter of ‘consecutive’. Although general $\gamma$-cycles have a rather obscure presence in the literature on permutation group theory, their importance has been recognized for a long time. For instance, they are instrumental in the proof of the main results in Piccard’s work [6], namely, that for any non-identity permutation $\sigma \in S_n\left(A_n\right)$ (except three permutations in the Klein group in the case of $S_n$) there is at least one permutation $\tau$ such that both permutations generate $S_n\left(A_n\right)$.

An important result concerning $\gamma$-cycles stated (though not proved) in the article [6] is P.4; we state it below in a slightly more particular form:

For any integers $0\le i<m\le n$ such that

$$(i,m,n)\notin \left\{\right(2,4,6),(3,4,6),(3,5,6\left)\right\}$$

distinct $\gamma$-cycles $(1,2,\dots ,m)$ and $(i+1,i+2,\dots ,n)$ generate $S_n$ when $m(n-i)$ is even and $A_n$ otherwise.

Our paper develops new results on the generating power of $\gamma$-cycles that provide answers to questions left unanswered by P.4 of [6]. From the beginning, our endeavour was an experimental mathematical one, as we were crucially assisted by proper programming that contributed in various ways to the development of our results. By programming computational experiments, we discovered new mathematical truths, were able to check some of our guesses, and arrived at more elegant proofs. Several of our guesses were actually invalidated by such experiments, leading to a better understanding of the conditions underlying our results as well as to interesting new questions.

The programming part of this investigation was performed in a do-it-yourself style by using the general purpose logic-based programming language Maude, described in the book [7]. On the one hand, this allowed us to avoid the use of dedicated software programs that are now popular with mathematicians (Maple, Mathematica, Wolfram, MATLAB, GAP, etc.), which although powerful and useful in many ways lack transparency and provide little access on the computational side. On the other hand, Maude is very different from common programming languages such as C, Python, Java, etc., as it is very high-level (in the sense of being closer to human mathematical language and thinking rather to a machine). It is based upon a form of model theory, while its execution engine is based upon the advanced computational paradigm of algebraic term rewriting. There is a good analogy to make here; dedicated software is like climbing a mountain by cable car, while our method it is more like climbing by foot equipped with very good mountain gear. On the other hand, common programming is like going by foot with very poor gear. In terms of connection with the mountain and nature, in terms of freedom to go anywhere and explore anything, nothing compares to the second option.

The programming experience with Maude comes as close as possible to the common mathematical problem solving experience while maintaining an intimate connection to the computational aspects. By employing several of the uniquely powerful computational paradigms implemented by Maude, most notably non-deterministic programming, we were able to achieve programs that are both short and clear. In fact, the mix between programming and mathematical reasoning involved in our endeavour can be a truly unified and very satisfactory problem solving experience.

The contents of our paper are as follows:

• We provide a brief presentation of our method for computational experiments with permutations. Maude can be understood mathematically through a few elementary forms of model theory, which we present briefly.
• We develop a general formula for factoring any $\gamma$-cycle as a product of other $\gamma$-cycles of arbitrary fixed length. A corollary of this is a general result of the generating power of $\gamma$-cycles of fixed length. Although this can be derived from P.4 of [6], our formulas provide a very different proof route to this consequence.
• We establish the exact generating properties of the three exceptions from P.4 of Piccard’s article [6].

For all results, we make very explicit the role played by programming computational experiments and even provide the programs. Being highly declarative and logic-based, these programs are short and easy to read and understand, especially in light of the section introducing our programming method.

2. Preordered Algebra and Its Computational Side

Programming in Maude is a fundamentally mathematical activity, as it consists essentially of specifying logical theories in a form based on model theory. Maude is a complex and sophisticated environment which can be understood and used in a myriad of ways. In this project, we use it in a rather basic way, which can be understood in terms of preordered algebra (abbreviated POA), a model theory which we present briefly now. More about the POA model theory can be read in the monograph [8].

2.1. Preordered Algebra

The conceptual pillars of any model theory, including POA, are fourfold:

• Signatures, which are language symbols that are structured in a certain way and that vary across logical theories;
• Sentences, which are logical formulas built with the symbols provided by the respective signatures;
• Models, which are interpretations of the signatures in set theory and provide meaning to logical theories;
• A satisfaction relation $M\vDash \rho$ between models (M) and sentences ($\rho$), which denotes which axioms hold in which models.

Concretely, in POA these are as follows.

We let $S^{*}$ denote the set of all finite sequences of elements from S, with $\left[\right]$ being the empty sequence. A (n S-sorted) signature$(S,F)$ is an $S^{*}\times S$-indexed family of sets $F=\{F_{w\to s}\mid w\in S^{*},s\in S\}$ of operation symbols. We call $\sigma \in F_{\left[\right]\to s}$ (sometimes denoted simply as $F_{\to s}$) a constant symbol of the sort s. That was about signatures.

An $(S,F)$-term t of sort $s\in S$ is a structure of the form $\sigma (t_1,\dots ,t_n)$, where $\sigma \in F_{w\to s}$ and $t_1,\dots ,t_n$ are $(S,F)$-terms of sorts $s_1\dots s_n$, where $w=s_1\dots s_n$. An $(S,F)$-equation is an equality $t=t^{\prime }$ between $(S,F)$-terms t and $t^{\prime }$ of the same sort. An $(S,F)$-rule is a sentence of the form $t\to t^{\prime }$, with t and $t^{\prime }$ being terms of the same sort. The POA atomic sentences are either such equations or rules. A POA sentence for a signature $(S,F)$ is of the form

$$\begin{array}{c}\hfill \forall X·{\rho }_1ʌ\dots ʌ{\rho }_n\Rightarrow \rho \end{array}$$

where X is a finite set of variables and ${\rho }_1,\dots ,{\rho }_n,\rho$ are atomic sentences for the signature $(S,F+X)$ that adjoins the variables X as new constants to F. That was about sentences.

Given a sort set S, an S-indexed (or sorted) set A is a family ${\left\{A_s\right\}}_{s\in S}$ of sets indexed by the elements of S. Given an S-indexed set A and $w=s_1$…$s_n\in S^{*}$, we let $A_w=A_{s_1}\times \dots \times A_{s_n}$; in particular, we let $A_{\left[\right]}=\{\star \}$, i.e., some one point set. An $(S,F)$-algebra (i.e., a model in POA) A consists of:

• an S-indexed set A (the set $A_s$ is called the carrier of A of sort s), and
• a function $A_{\sigma }:A_w\to A_s$ for each $\sigma \in F_{w\to s}$.

If $\sigma \in F_{\to s}$, then $A_{\sigma }$ determines a point in $A_s$, which may be denoted $A_{\sigma }$. Any $(S,F)$-term $t=\sigma (t_1,\dots ,t_n)$, where $\sigma \in F_{w\to s}$ is an operation symbol and $t_1,\dots ,t_n$ are $(S,F)$-(sub)terms corresponding to the parity w, is interpreted as an element $A_t\in A_s$ in an $(S,F)$-algebra A by $A_t=A_{\sigma }(A_{t_1},\dots ,A_{t_n})$.

A model in POA for a signature $(S,F)$, $(M,\le )$, called a preordered algebra, consists of an $(S,F)$-algebra M and a family $\le =\{{\le }_s\subseteq M_s\times M_s\mid s\in S\}$ of preorders such that the interpretation of each operation in F is monotonic with respect to ≤. That was about models.

The satisfaction relation between preordered algebras and sentences is the Tarskian satisfaction defined inductively on the structure of sentences. Given a fixed arbitrary signature $(S,F)$ and a preordered $(S,F)$-algebra $(M,\le )$,

• $(M,\le )\vDash t=t^{\prime }$ if $M_t=M_{t^{\prime }}$ for equations,
• $(M,\le )\vDash t{t}^{\prime }$ if $M_t\le M_{t^{\prime }}$ for rules,
• $(M,\le )\vDash {\rho }_1\wedge {\rho }_2$ if $(M,\le )\vDash {\rho }_1$ and $(M,\le )\vDash {\rho }_2$, and similarly for ⇒, and
• for each $(S,F+X)$-sentence $(M,\le )\vDash \forall X·\rho$, if $(M^{\prime },\le )\vDash \rho$ for each expansion $M^{\prime }$ of M with interpretations of the variables of X as elements of M.

On the one hand, programming in Maude consists of writing down specifications of signatures and sentences according to syntactic rules that closely follow the mathematical definitions above. On the other hand, there is the semantic aspect, meaning that one has to make a permanent effort to ensure that what is written down accords with the intended class of models to be specified. In general, this may be a subtle issue where the mathematics of models and satisfaction play their role, however, trained mathematicians are in the best possible situation to cope with this.

2.2. Term Rewriting in Maude

The above dealt with the specification part of Maude. However, in addition Maude is a proper programming language with a powerful execution engine based on an advanced computational paradigm, namely, algebraic term rewriting. Its implementation in Maude consists of a complex software structure employing state of-the-art technologies. Computation by term rewriting follows the principle of computation as logical inference. POA admits an inference system that is sound and complete with respect to the model theory defined above. This inference system is just an extension of Birkhoff’s famous set of rules for equational deduction (presented in his work [9]) in a conditional form and with additional rules for atomic transitions (which are similar to the rules for the atomic equations minus the symmetry rule). Details of the POA inference system, including its soundness and completeness, can be found in the monograph [8]. In this way, term rewriting in Maude is an extension of the classical term rewriting paradigm from equational logic to POA, which means that it can be used in two different ways corresponding to the two types of atomic sentences.

• In order to compute equalities between elements of models using equations, terms are reduced to normal forms; for this, it is important that the set of equations enjoy the properties known as confluence and termination. The former means that when several equations can be used in rewriting, the choice does not matter. The latter means that the rewriting of any terms eventually comes to an end, and does not run indefinitely.
• In order to compute elements along preorder relations in models. In a more computing science-oriented terminology, elements of the models are states and the preorder relations are transitions. This approach concerns which statesare reached from which other states, and uses rules rather than equations. Here, neither the confluence nor the termination property is required. Lack of confluence means an open door to non-deterministic programming, a crucial distinctive computational paradigm that we use in the present project.

2.3. Implications

To summarise, POA has three strongly interconnected levels. At the top, there is model theory. At the bottom, there is term rewriting. In the middle, there is the sound and complete inference system of POA that bridges the model theory and the computational side.

The ultimate effect of this conceptual structure is a highly declarative, compact, computationally powerful and transparent programming and experimentation method. Transparency has at least two positive consequences: higher confidence in the correctness of the experiment and a great enhancement of understanding. These are two aspects that, in general, the dedicated mathematical software systems lack. Thus, we think that, when possible, it is worth avoiding opaque experimentation and instead aiming for transparent alternatives even at the cost of greater programming effort. However, when complex and sophisticated algorithms are unavoidable, i.e., for programming tasks that are too large or even impossible due to lack of knowledge, dedicated pre-built software can represent an alternative. What is most important when seeking transparency is to strike a right balance between the two.

The computation as logical inference principle underlying Maude programming implies that proofs that consist of a combination of mathematical reasoning and run on Maude programs are in fact 100% mathematical proofs, as the parts relying on programming can be considered simply as formal proofs. In this way,

“such a combination is just a mathematical proof consisting of more informal parts (i.e., the mathematical arguments in a conventional style) and of purely formal parts, and nothing else.”

Then, the transparency aspect additionally implies rather easy access to the formal parts of such proofs.

3. $\gamma$-Cycles Generated by $\gamma$-Cycles of Fixed Length

Let us recall a few basic notations and techniques from permutation group theory. We denote the product of permutations in the same order as functional compositions; in other words, if $\sigma$ and $\tau$ are permutations and $i\in \{1,2,\dots ,n\}$, then $\left(\sigma \tau \right)\left(i\right)=\sigma \left(\tau \right(i\left)\right)$. An easy corollary of the decomposition

$$(i_1,i_2,\dots ,i_k)=(i_1,i_2)(i_2,i_3)\cdots (i_{k-1},i_k)$$

of a cycle as a product of transpositions is the decomposition

$$(a,\dots ,b,\dots ,c)=(a,\dots ,b)(b,\dots ,c)$$

of a cycle as a product of subcycles. If $\sigma =(i_1,i_2,\dots ,i_k)$, then ${\sigma }^{-1}=(i_k,i_{k-1},\dots ,i_1)$.

In any group G, if $S\subseteq G$, then $\langle S\rangle$ denotes the subgroup of Ggenerated by S, which is the smallest subgroup of G that contains S. In any group G, the notation ${\sigma }^{\tau }$ means $\tau \sigma {\tau }^{-1}$ or the conjugation of $\sigma$ by $\tau$. A few helpful properties of conjugations are ${\left(\sigma \tau \right)}^{\pi }={\sigma }^{\pi }{\tau }^{\pi }$ (as, in addition, conjugation is bijective, meaning that it is automorphism) and ${\sigma }^{\tau \pi }={\left({\sigma }^{\pi }\right)}^{\tau }$. The conjugacy class of an element $\pi$ is ${\pi }^G=\{\sigma \pi {\sigma }^{-1}\mid \sigma \in G\}$. For the particular case of permutation groups, there is a helpful property for the cycles:

$${(i_1,i_2,\dots ,i_k)}^{\tau }=(\tau \left(i_1\right),\tau \left(i_2\right),\dots ,\tau \left(i_k\right)).$$

Definition 1

($\gamma$-cycles). In $S_n$, a $\gamma$-cycleis a cycle of the form

$$(i+1,i+2,\dots ,i+m-1,i+m)$$

where $0\le i\le n-m$. We may denote these cycles simply as $[i+1,i+m]$ An m-$\gamma$-cycleis a γ-cycle of length m. The γ-cycles $[1,m]$ are called initial while the $[i,n]$ are called final γ-cycles.

For instance, the 2-$\gamma$-cycle $[i,i+1]$ is just the adjacent transposition $(i,i+1)$.

The following results are established in the literature and are used in what follows. While the former is better known, the latter is much less known (it can be found in Conrad’s work [10]).

Proposition 1.

$S_n$ is generated by the set of all adjacent transpositions. $A_n$ is generated by the set of all 3-γ-cycles.

In the literature on group theory, these properties often receive unnecessarily difficult proofs, especially the result for 3-$\gamma$-cycles. However, both of them can be shown easily through algorithmic reasoning by sorting the permutations ($\pi$) as follows. In the former case, at each step we simply select any pair of adjacent elements that are not in order, i.e., $\pi \left(i\right)>\pi (i+1)$, and swap them. This algorithm terminates because at each step the number of inversions is decreased. Moreover, it can only terminate when the permutation is sorted. In the latter case, by successively applying 3-$\gamma$-cycles we first bring 1 to its place (i.e., such that $\pi \left(1\right)=1$), then we bring 2, 3, etc., until 1, 2, …, $n-2$ are all sorted. Now, if $\pi (n-1)=n-1$ and $\pi \left(n\right)=n$ the permutation is sorted; otherwise, it means that the starting permutation was odd.

3.1. Computational Experiments with Fixed Length $\gamma$-Cycles

The origin of our endeavour was not Piccard’s work [6] (in fact, we learned about it at a rather late stage), but rather a misinterpreted version (perhaps due to poor translation) of a problem proposed in 1994 to the participants at the Russian Mathematical Olympiad. In the end, the misinterpreted variant proved to be much more interesting and challenging than the true version. In higher algebra terminology, this was equivalent to the following question:

What is the subgroup of $S_n$ generated by all m-$\gamma$-cycles?

In order to obtain an answer to this question, in the beginning we wrote a program that generated all permutations in $S_n$ from m-$\gamma$-cycles. By embedding h of $S_{m+1}$ into $S_n$, now used in the proof of Theorem 1 below, and in the light of Proposition 1, we were able to reduce the problem to the case $n=m+1$. By running the program and by inspecting the cardinality of the generated group, we noticed quickly that $S_{m+1}$ is generated when m is even, while $A_{m+1}$ is generated when m is odd. With this understanding, we approached larger values for m in order to check this truth more thoroughly. For this, we had to abandon the generation of all permutation and instead rely on Proposition 1 to focus only on the adjacent transpositions when m is even and on the 3-$\gamma$-cycles when m is odd. This has carried out with two rules, as follows:

• We represented permutations as lists of numbers in the obvious way. For example, the list $\left(35241\right)$ represents the permutation $\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 3& 5& 2& 4& 1\end{array}\right)$. This choice of representation is motivated by the fact that Maude provides unparalleled computational support for lists through rewriting modulo associativity.
• One rule (denoted $r_1$) generates non-deterministically the inverses of all k-$\gamma$-cycles. Its corresponding logical formula is

  $$\begin{array}{c}\hfill \forall l,l^{\prime },L^{\prime }·\forall b·(\#L^{\prime }=k-1)\Rightarrow \left(l\left(b{L}^{\prime }\right)l^{\prime }\right)\to \left(l\left(L^{\prime }b\right)l^{\prime }\right)\end{array}$$

  where $l,l^{\prime },L^{\prime }$ are variables ranging over lists of naturals, b is a variable ranging over the naturals, and $\#L^{\prime }$ is the length of $L^{\prime }$.
• The other rule (denoted $r_2$) applies m-$\gamma$-cycles non-deterministically, its corresponding logical formula being

  $$\begin{array}{c}\hfill \forall l,l^{\prime },L^{\prime }·\forall b·(\#L^{\prime }=m-1)\Rightarrow \left(l\left(L^{\prime }b\right)l^{\prime }\right)\to \left(l\left(b{L}^{\prime }\right)l^{\prime }\right).\end{array}$$

We use a “flag” (i.e., a variable that takes either 0 or 1 as its values) to ensure that the former rule is applied exactly once at the beginning of the computation, while the latter can be applied any number of times. In this way, we can generate all compositions between an inverse of a k-$\gamma$-cycle and any sequence of m-$\gamma$-cycles. When this yields the identity, we can find the respective k-$\gamma$-cycle is a product of m-$\gamma$-cycles. In the light of Proposition 1, for our immediate purpose it is enough to run the program only for $k\in \{2,3\}$, although the program built in this way can be run more generally as well. For $m=3$ and $k=2$, this process can be represented by the diagram below:

This diagram can be interpreted in two ways. On the one hand, it is a fragment of any model satisfying the two logical formulas above. On the other hand, the computational angle shows the relevant fragment of the computation process. With Maude, these are the two sides of the same coin.

The actual Maude programs can be found in Appendix A.

3.2. The Mathematical Results

After assuring confidence with respect to the generation of $S_{m+1}$ and $A_{m+1}$ through experimentation with the programs discussed above, we assessed how k-$\gamma$-cycles for $k=1,2$ are generated, and noticed immediately that this was always carried out in $m+1$ steps. Then, we looked into the actual decomposition of those k-$\gamma$-cycles as products of m-$\gamma$-cycles, and by inspecting patterns we arrived at the following formulas:

(i)

If m is even, then $(i,i+1)=\left\{\begin{array}{cc}{\left(\tau \sigma \right)}^{\frac{i}{2}}\sigma {\left(\tau \sigma \right)}^{\frac{m-i}{2}},\hfill & i\mathrm{even}\hfill \\ {\left(\tau \sigma \right)}^{\frac{i-1}{2}}\tau {\left(\tau \sigma \right)}^{\frac{m+1-i}{2}},\hfill & i\mathrm{odd}.\hfill \end{array}\right.$

(ii)

If m is odd, then $[i,i+2]=\left\{\begin{array}{cc}{\left(\tau \sigma \right)}^{\frac{i}{2}}{\sigma }^2{\left(\tau \sigma \right)}^{\frac{m-i-1}{2}},\hfill & i\mathrm{even}\hfill \\ {\left(\tau \sigma \right)}^{\frac{i-1}{2}}{\tau }^2{\left(\tau \sigma \right)}^{\frac{m-i}{2}},\hfill & i\mathrm{odd}.\hfill \end{array}\right.$

where $\sigma =[1,m]$ and $\tau =[2,m+1]$ are the m-$\gamma$-cycles of $S_{m+1}$.

While working to prove these formulas, we came to understand that they hold more generally as well, and thus arrived at the results of Proposition 2 and its consequences, Corollary 1 and Theorem 1.

Proposition 2.

In $S_{m+1}$, let $\sigma =[1,m]$, $\tau =[2,m+1]$, $\alpha =[1,m+1]$. Then, for each i and ℓ

$$[i,i+\ell ]={\alpha }^i{\sigma }^{\ell }{\alpha }^{-(i+\ell )}={\alpha }^{i-1}{\tau }^{\ell }{\alpha }^{1-(i+\ell )}.$$

Proof. 

We begin with the proof of the first equality by induction on ℓ. For $\ell =1$, we have:

$$\begin{array}{cc}\hfill (i,i+1)=& [1,i-1](i-1,i+1)[i+1,m+1]{\alpha }^{-1}\hfill \\ \hfill =& {\sigma }^{{\alpha }^i}{\alpha }^{-1}={\alpha }^i\sigma {\alpha }^{-(i+1)}.\hfill \end{array}$$

For the inductive step, we have:

$$\begin{array}{ccc}\hfill (i,i+\ell +1)=& (i,i+1)[i+1,i+\ell +1]\hfill & \\ \hfill =& {\alpha }^i\sigma {\alpha }^{-(i+1)}{\alpha }^{i+1}{\sigma }^{\ell }{\alpha }^{-(i+\ell +1)}\hfill & \mathrm{by}\mathrm{the}\mathrm{induction}\mathrm{hypothesis}\hfill \\ \hfill =& {\alpha }^i{\sigma }^{\ell +1}{\alpha }^{-(i+\ell +1)}.\hfill \end{array}$$

The second equality is proven as follows:

$$\begin{array}{ccc}\hfill {\alpha }^i{\sigma }^{\ell }{\alpha }^{-(i+\ell )}=& {\alpha }^i{\left({\tau }^{{\alpha }^{-1}}\right)}^{\ell }{\alpha }^{-(i+\ell )}\hfill & \mathrm{because}\sigma ={\tau }^{{\alpha }^{-1}}\hfill \\ \hfill =& {\alpha }^i{\left({\tau }^{\ell }\right)}^{{\alpha }^{-1}}{\alpha }^{-(i+\ell )}\hfill & \\ \hfill =& {\alpha }^{i-1}{\tau }^{\ell }{\alpha }^{1-(i+\ell )}.\hfill \end{array}$$

 □

Corollary 1.

Under the notations used in Proposition 2, if $m·\ell$ is even, then $[i,i+\ell ]\in \langle \sigma ,\tau \rangle$. Moreover,

$$[i,i+\ell ]=\left\{\begin{array}{cc}{\left(\tau \sigma \right)}^{\frac{i}{2}}{\sigma }^{\ell }{\left(\tau \sigma \right)}^{-\frac{i+\ell }{2}},\hfill & (i-1)(\ell -1)\mathit{odd}\hfill \\ {\left(\tau \sigma \right)}^{\frac{i-1}{2}}{\tau }^{\ell }{\left(\tau \sigma \right)}^{\frac{1-(i+\ell )}{2}},\hfill & i(\ell -1)\mathit{odd}\hfill \\ {\left(\tau \sigma \right)}^{\frac{i}{2}}{\sigma }^{\ell }{\left(\tau \sigma \right)}^{\frac{m+1-(i+\ell )}{2}},\hfill & (i-1)\ell \mathit{odd}\hfill \\ {\left(\tau \sigma \right)}^{\frac{i-1}{2}}{\tau }^{\ell }{\left(\tau \sigma \right)}^{\frac{m+2-(i+\ell )}{2}},\hfill & i·\ell \mathrm{odd}.\hfill \end{array}\right.$$

Proof. 

The key to the derivation of this consequence is the equation $\tau \sigma ={\alpha }^2$, which can be checked easily. In order to use this, we have to see when the two exponents of $\alpha$ involved in one of the two equations in the statement of Proposition 2 are even. Indeed,

• when ℓ is even, then either both i and $i+\ell$ are even or else both $i-1$ and $i+\ell -1$ are even, and
• when ℓ is odd, then m is even, which implies that either both i and $m+1-(i+\ell )$ are even or else both $i-1$ and $m+2-(i+l)$ are even; in this case, in order to invoke the results of Proposition 2, we use ${\alpha }^{m+1}=1$.

 □

Note that while the formulas of Corollary 1 are new, its first conclusion can be derived from P.4 of [6].

The theorem below shows that all m-$\gamma$-cycles generate either $A_n$ or $S_n$ depending on the parity of m, thereby generalizing the results of Proposition 1.

Theorem 1.

Fix integers $m,n$, with $2\le m<n$. Then,

$$〈\left\{\right[k+1,k+m]\mid k=0,1,\dots ,n-m\}〉=\left\{\begin{array}{cc}{A}_n,\hfill & \mathit{if}m\mathit{is}\mathit{odd},\hfill \\ S_n,\hfill & \mathit{if}m\mathit{is}\mathit{even}.\hfill \end{array}\right.$$

Proof. 

For $[i,i+\ell ]\in S_n$, $\ell =1,2$, we consider $k+1\le i,i+\ell \le k+m+1\le n$. By applying Corollary 1 through homomorphic embedding h of $S_{m+1}$ into $S_n$ defined by

$$h\left(\pi \right)\left(q\right)=\left\{\begin{array}{cc}k+\pi (q-k),\hfill & k+1\le q\le k+m+1\hfill \\ q,\hfill & \mathrm{otherwise}\hfill \end{array}\right.$$

the $\gamma$-cycle $[i,i+\ell ]$ is generated by $[k+1,k+m]$ and $[k+2,k+m+1]$. This conclusion follows from the results of Proposition 1. □

4. The Three Exceptions

P.4 of [6] is a general result for the subgroups of $S_n$ generated by an initial and final $\gamma$-cycle that have a non-empty intersection. Three exceptions are stated therein where the result does not hold. The aim of this section is to establish the nature of the actual subgroups of $S_n$ generated by these exceptions.

We establish the following result through a combination of mathematical reasoning with programming and with classification theory know-how. This exception from P.4 of article [6] was actually discovered by us through programming independently before we were made aware of the above publication.

Proposition 3.

The subgroup $G=\langle [1,4],[2,6]\rangle$ of $S_6$ is isomorphic to $S_5$.

Proof. 

$S_5$ was suggested to us by the cardinality of G, which we noticed when generating its elements by programming. However, according to the database [11] there are 47 groups with cardinality 120.

In order to establish the isomorphism to $S_5$, we implemented the following steps:

• We computed the orders of all elements of G as follows. The program that computes the subgroup of $S_n$ generated by $[1,m]$ and $[2,n]$ implements the logical formulas

  $$\begin{array}{c}\hfill \forall x·\forall L,L^{\prime }·(\#L=m-1)\Rightarrow \left(xL\right)L^{\prime }\to \left(Lx\right)L^{\prime }\end{array}$$

  and

  $$\begin{array}{c}\hfill \forall x,y·\forall L·x\left(yL\right)\to x\left(Ly\right)\end{array}$$

  where $x,y$ range over naturals and $L,L^{\prime }$ over lists of naturals. Of course, the parts of the POA models considered refer only to the case in which the terms of the equations are permutations in $S_n$. To these, we added another sentence used for specifying powers of permutations:

  $$\begin{array}{c}\hfill \forall L,P·P\to P\circ L\end{array}$$

  where P and L are lists of naturals (which are used only as permutations) and $P\circ L$ is their composition as permutations. We implemented these three POA sentences as a Maude program, which is explained in detail in Appendix B. By running it for $m=4$ and $n=6$, we obtained the list of all elements of G together with their respective orders.
• We noticed that the set of the orders of the elements of G is $\{1,2,3,4,5,6\}$. We ran the program again in order to partition G into six order classes (the order class of $\pi \in G$, denoted $O\left(\pi \right)$, consists of all elements of G of the same order with $\pi$).
• Then, with a simple Maude program implementing the logical formulas

  $$\begin{array}{c}\hfill \forall P·P\to [1,4]\circ P\circ {[1,4]}^{-1}\end{array}\mathrm{and}\begin{array}{c}\hfill \forall P·P\to [2,6]\circ P\circ {[2,6]}^{-1}\end{array}$$

  we pick one element from each of the six order classes and compute its conjugacy class. For the orders 1, 3, 4, 5, 6, we have $\#{\pi }^G=\#O\left(\pi \right)$, which implies ${\pi }^G=O\left(\pi \right)$, because it is always the case that ${\pi }^G\subseteq O\left(\pi \right)$. This consumed five short computations. For the second order, we used a random permutation $\pi$ from the respective order class and obtained ${\pi }^G=15$. Then, we tried randomly with another permutation, ${\pi }^{\prime }\in O\left(\pi \right)\setminus {\pi }^G$, and obtained $\#{{\pi }^{\prime }}^G=10$. It follows that the set of the permutations in G of the second order is partitioned into two conjugacy classes. To summarise, with seven short computations we were able to establish that G has seven conjugacy classes of sizes 1(1), 10(2), 15(2), 20(3), 30(4), 24(5), and 20(6), where $a\left(b\right)$ means that the conjugacy class has size a and elements of order b.
• Finally, we relied on established knowledge about groups of order 120 as follows. According to the database [11], $S_5$ is the only group with order 120 and seven conjugacy classes, which means that G is isomorphic to $S_5$.

 □

In the proof of Proposition 3, programming is involved at two points, once explicitly and another time implicitly. On the one hand, we use highly transparent logic-based Maude programming to establish the conjugacy classes of G. On the other hand, at the end of the argument we rely on the result provided by the database in [11], namely, that $S_5$ is the only group with order 120 and seven conjugacy classes, which to our understanding has been obtained through the GAP system [12]. We can say that this is an implicit involvement of programming.

For the other two exceptions, we have two options: either to replicate the proof procedure of Proposition 3 or else to approach them by conventional mathematical reasoning, eventually by relying on the result of Proposition 3. The former option is straightforward, while the latter requires mathematical effort, the result being uncertain. However, for the case of the third exception there is no such dilemma, as we may note immediately a symmetry with the case in Proposition 3, meaning that we can rely on that result.

Corollary 2.

The subgroup $\langle [1,5],[3,6]\rangle$ of $S_6$ is isomorphic to $S_5$

Proof. 

Let $\beta =(1,6)(2,5)(3,4)$. Then, $[2,6]={\left({[1,5]}^{\beta }\right)}^{-1}$ and $[1,4]={\left({[3,6]}^{\beta }\right)}^{-1}$, hence, $\langle [1,5],[3,6]\rangle$ is isomorphic to $\langle [1,4],[2,6]\rangle$ through an automorphism of $S_6$. □

The remaining exception is less straightforward mathematically, and in this case it makes a lot of sense to approach it in the style of Proposition 3. However, that would not bring anything new to our exposition; therefore, in order to contrast the two approaches, we approach it in a conventional way. However, this does not mean we start from scratch; we rely on the result of Proposition 3, which is the most important result in this section and a base for deriving the other results.

Corollary 3.

The subgroup $\langle [1,4],[3,6]\rangle$ of $S_6$ is isomorphic to $S_5$.

Proof. 

Let $u=[1,4]$, $v=[3,6]$ and $\alpha =[1,6]$. Because

$${\left(u^{v^2}\right)}^{u^2}=u^{u^2{v}^2}=u^{{\alpha }^2}=v$$

it follows that

$$\langle u,v\rangle =\langle u,u^{v^2}\rangle =\langle u,u^{-1}{u}^{v^2}\rangle =\langle u,{\left(u^{-1}{u}^{v^2}\right)}^{-1}\rangle =\langle u,(2,3,4,6,5)\rangle .$$

Because $u^{(5,6)}=u$ and ${(2,3,4,6,5)}^{(5,6)}=[2,6]$, we obtain that $\langle u,v\rangle$ is isomorphic to $\langle [1,4],[2,6]\rangle$ through an automorphism of $S_6$. □

4.1. Grasping Concrete Isomorphisms

Proposition 3 tells us that there are isomorphisms $G=\langle [1,4],[2,6]\rangle \to S_5$. Now, we establish them concretely.

On the basis of Proposition 3, let us consider an isomorphism $\psi :G\to S_5$. Note that, as an isomorphism, $\psi$ preserves orders. In particular, it follows that the order of $\psi [2,6]$ is 5, becuase in $S_5$ all permutations of order 5 form a single conjugacy class (see the third stage in the proof of Proposition 3) and there exists $\pi \in S_5$ such that ${\left(\psi [2,6]\right)}^{\pi }=\alpha =[1,5]$. Let $\phi ={(-)}^{\pi }\circ \psi$ be the composition between $\psi$ and the automorphism defined by the conjugation with $\pi$. All we have to do now is establish the value of $\phi [1,4]$.

By programming, we non-deterministically generate all permutations P of $S_5$ as candidates for $\phi [1,4]$, and again by programming we check for each of them whether permutations generated by P and $\alpha$ have the same order as the corresponding permutations generated in $S_6$ by $[1,4]$ and $[2,6]$.

We try this gradually with permutations generated in 1, 2, and 3 steps. Upon inspecting the results, it can be seen that all of them share five solutions, while in certain cases (for example when $P_5=P·{[2,6]}^2$) these five are all solutions. Then, we note that these are $\{{(1,4,2,3)}^{{\alpha }^k}\mid k=\overline{0,4}\}$, which is expected, as for any solution P, because ${\alpha }^{\alpha }=\alpha$, we automatically have $P^{{\alpha }^k}$ for $k=\overline{0,4}$ as solutions as well. This means that up to a conjugation by ${\alpha }^k$ we have found only one possibility for $\phi [1,4]$; hence, we can formulate the following consequence of Proposition 3:

Corollary 4.

$\phi [1,4]=(1,4,2,3)$ and $\phi [2,6]=[1,5]$ define an isomorphism $G\to S_5$. Moreover, this is the unique such isomorphism up to a conjugation by a permutation in $S_5$.

Similar results may be established for the other two exceptions. This can be done either directly, as for Corollary 4, or else as a consequence of Corollary 4 through the isomorphisms of Corollaries 2 and 3, respectively. The program that establishes the value of $\phi [1,4]$ is presented in Appendix C.

5. Conclusions

We have introduced a new experimental mathematics method that combines conventional mathematical development with preordered algebra based computation with Maude programming language. The computation-as-logical-inference foundation of the programming parts means that, as a whole, our proofs are merely mathematical proofs that may contain a few formal parts. Moreover, the programming parts are highly transparent thanks to the strong declarative character of Maude and because we use general purpose programming rather than dedicated software.

In this way, we were able to discover formulas for generating any $\gamma$-cycles from arbitrary fixed length $\gamma$-cycles, then applied this to show that all $\gamma$-cycles of arbitrary fixed length generate either $S_n$ or $A_n$ depending upon the parity of their length. Then, we turned to the exceptions of an old general result on the generating power of two $\gamma$-cycles. By our method, we able to first discover and then prove that the subgroups generated within the context of all three exceptions correspond to certain uncommon embeddings of $S_5$ into $S_6$.