Menu
We study groups generated by sets of pattern avoiding permutations. In the first part of the paper, we prove some general results concerning the structure of such groups. In particular, we consider the sequence \((G_n)_{n \geq 0}\), where \(G_n\) is the group generated by a subset of the symmetric group \(S_n\) consisting of permutations that avoid a given set of patterns. We analyze under which conditions the sequence \((G_n)_{n \geq 0}\) is eventually constant. Moreover, we find a set of patterns such that \((G_n)_{n \geq 0}\) is eventually equal to an assigned symmetric group. Furthermore, we show that any non-trivial simple group cannot be obtained in this way and describe all the non-trivial abelian groups that arise in this way. In the second part of the paper, we carry out a case-by-case analysis of groups generated by permutations avoiding a few short patterns.
The symmetric group \(S_n\) over \(n\) elements is ubiquitous in mathematics, indeed, it is studied both from a group-theoretical and a combinatorial point of view. In the first case the elements of \(S_n\) are thought as bijections acting on the set \(\{1,\,2,\,\ldots\,, n\}\) and are written as sequences of cycles, in the second case they are considered as words containing all the symbols from \(1\) to \(n\) exactly once.
The group-theoretical study of the symmetric group embodies the wide fields of representation theory of the symmetric group (see, e.g., [1]) and permutation groups (see, e.g., [2]). Combinatorics of permutations (see, e.g., [3]) includes many topics, among whom one of the most recently developed is the study of pattern avoiding permutations (see, e.g., [4]).
These two aspects are rarely considered together, due to the different nature of the two approaches. Papers that deal with both the perspectives are, for instance, [5-10].
In this paper we consider the problem of determining the group generated by a set of pattern avoiding permutations. This topic has never been investigated, to the best of our knowledge.
First of all, we introduce some notations and present some preliminary results (Sections 2 and 3).
Then, given a set of patterns \(T,\) we consider the subset \(S_n(T)\) of the symmetric group \(S_n\) consisting of permutations avoiding each pattern in \(T,\) and turn our attention to the group \(G_n\) generated by \(S_n(T).\)
When dealing with such groups some questions naturally arise. First of all, under which conditions the sequence \((G_n)_{n\geq 0}\) is eventually constant (under isomorphism) and which kind of groups arise?
In Section 4 we find a set of patterns such that \((G_n)_{n\geq 0}\) is eventually constant and equal to an assigned symmetric group \(S_k.\) In Section 5 we show that any non-trivial simple group can not be obtained in this way, and that the only non-trivial abelian groups that arise are \(\mathbb Z_2\) and \(\mathbb Z_2\times \mathbb Z_2.\) The proof of such results take advantage of a characterization of those sets of patterns such that the sequence \((G_n)\) has polynomial growth.
A further question is under which conditions \(G_n=S_n\) for every sufficiently large \(n.\) In Section 6 we present a fairly general condition under which this happens.
Sections 7 and 8 are devoted to the analysis of the groups generated by \(S_n(T)\) when \(T\) consists of few patterns, or patterns of small length. In the last section we present some open problems.
Firstly we recall some notations from group theory. We denote by
\(S_n\) the symmetric group, i.e., the set of permutations of \([n]=\{1,2,\ldots ,n\},\) with the operation of composition, and by \(S\) the union of all these sets, \[S=\bigcup_{n\geq 0} S_n,\]
\(A_n\) the alternating group, i.e., the subgroup of \(S_n\) of even permutations,
\(\mathbb Z_n\) the cyclic group with \(n\) elements,
\(D_n\) the dihedral group with \(2n\) elements, i.e., the group of symmetries of the regular \(n\)-agon.
As we mentioned above, every element \(\pi\) of \(S_n\) can be written either as a product of cycles, or as the sequence \(\pi=\pi_1\,\pi_2\,\ldots\,\pi_n\) of images of the elements \(1,2,\ldots,n.\) The presence or the absence of the brackets will make clear which notation we are using. We write products from right to left, that is, if \(\pi,\sigma \in S_n,\) \(\pi \sigma\) is the permutation obtained by applying \(\sigma\) first.
Given a set \(A \subseteq S_n,\) the symbol \(\langle A\rangle\) will denote the group generated by \(A.\)
We will use the following notation for some special elements of \(S_n.\)
the identity permutation will be denoted by \(id_n,\) \[id _n=1\,2\,\ldots \,n,\]
the decreasing permutation will be denoted by \(\psi_n,\) \[\psi_n= n\quad n-1\,\ldots\,2\; 1=\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor} (i,\; n+1-i).\]
We will use the symbols \(id\) and \(\psi\) when the size is clear from the context.
If \(\pi\in S_n\) we will say that \(\pi\) has length \(n\) and write \(|\pi|=n.\) A permutation \(\pi\) such that \(\pi=\pi^{-1}\) is called an involution. For example, the permutation \(\psi_n\) is an involution.
The reverse, the complement and reverse-complement of the permutation \(\pi\) are the permutations \(\pi^r=\pi \psi,\) \(\pi^c=\psi \pi\) and \(\pi^{rc}=\psi \pi\psi,\) respectively.
A permutation \(\pi\in S_n\) contains the pattern \(\tau\in S_k\) if there are indices \(1\leq i_1 < i_2 < \ldots <i_k\leq n\) such that the subsequence \(\pi_{i_1}\,\pi_{i_2}\,\ldots\,\pi_{i_k}\) is order isomorphic to \(\tau,\) and we write \(\pi\geq \tau.\)
Otherwise, we say that \(\pi\) avoids the pattern \(\tau.\)
The set of permutations of length \(n\) avoiding all the patterns in the set \(T=\{\tau_1,\tau_2,\ldots\}\) is denoted by \(S_n(T)\) or, with a slight abuse of notation, by \(S_n(\tau_1,\tau_2,\ldots).\)
We set \(S(T)=\cup_{n\geq 0} S_n(T).\)
Notice that the set \(S\) with the containment relation \(\leq\) is a poset. A downset in this order is called a permutation class or simply a class. Given a class \(\mathcal{C},\) we set \(\mathcal{C}_n=\mathcal{C}\cap S_n\) for every \(n\geq 0.\) A class can be specified by its basis, the minimal permutations not in the class. If \(T\) is the basis of a class \(\mathcal{C},\) then \(\mathcal{C}=S(T).\) Observe that the basis of a class can be infinite, since the poset \((S,\leq)\) contains infinite antichains.
We state some basic lemmas that will be useful in the following.
Lemma 1. Let \(T\) and \(T'\) be two subsets of \(S\), with \(T\subseteq T'\). Then \(\langle S_n(T')\rangle \subseteq \langle S_n(T)\rangle\).
Proof. This property follows immediately from the definition of pattern containment. ◻
Lemma 2. Let \(\sigma_1,\ldots,\sigma_k\) and \(\tau_1,\ldots,\tau_k\) be permutations of any length such that \(\sigma_i\leq \tau_i\) for every \(i\). Then \(\langle S_n(\sigma_1,\ldots,\sigma_k) \rangle \subseteq \langle S_n(\tau_1,\ldots,\tau_k) \rangle.\)
Proof. This fact is a straightforward consequence of the following inclusion: \(S_n(\sigma_1,\ldots,\sigma_k) \subseteq S_n(\tau_1,\ldots,\tau_k).\) ◻
Given a set of permutations \(A,\) let \(A^r\) be the set \(\{ \sigma^r\; |\; \sigma \in A\}.\) The sets \(A^c,\) \(A^{rc},\) \(A^{-1}\) are defined similarly. Notice that \(S_n(T)^r=S_n(T^r),\) and the same is true for the complement, the reverse-complement and the inverse map. Moreover, since \((\pi^r)^{-1}=(\pi^{-1})^c,\) \[(S_n(T^r))^{-1}=S_n((T^r)^{-1})=S_n((T^{-1})^c).\] A similar identity holds with \(r\) and \(c\) interchanged.
Lemma 3. Let \(T\subseteq S\) be a set of permutations of any length. Then \[\langle S_n(T) \rangle = \langle S_n(T^{-1}) \rangle=\langle S_n(T)\cup S_n(T^{-1}) \rangle,\] and \[\langle S_n(T) \rangle \cong \langle S_n(T^{rc}) \rangle.\]
Proof. Given \(\pi \in S_n,\) \(\pi^{rc}=\psi \pi \psi.\) This fact implies the second assertion. The first assertion is trivial. ◻
Lemma 4. Let \(T\subseteq S\) be a set of permutations of any length. If \(\psi_k \notin T\) for every \(k\geq 1,\) then \[\langle S_n(T)\rangle =\langle S_n(T)\cup S_n(T^r)\cup S_n(T^c)\cup S_n(T^{rc})\rangle.\]
Proof. Notice that if \(\psi_k \notin T\) for every \(k\geq 1,\) then \(\psi_n \in S_n(T).\) Since \(\sigma^r=\sigma \psi,\) \(\sigma^c=\psi \sigma\) and \(\sigma^{rc}=\psi \sigma \psi,\) the assertion follows. ◻
We recall a well-known result that presents some families of generating sets for the group \(S_n.\)
Lemma 5. The following sets generate \(S_n,\) for every \(n\geq 1.\)
\(\{(j,\;j+1),\;1\leq j\leq n-1\}.\)
\(\{(1,\;j),\;2\leq j\leq n\}.\)
\(\{(a,\;b),\;(1,\;2,\ldots ,n)\}\) if \(b-a\) and \(n\) are coprime.
First of all we ask the following question.
Question 1. Let \(G\) be any finite group. Is it possible to find a subset \(T\) of \(S\) and a positive integer \(n\) such that \(\langle S_n(T) \rangle=G?\)
Notice that if \(T\) can depend on \(n,\) then the answer to the previous question is trivially true for every \(G\). In fact, if \(G\) is a finite group, by Cayley’s theorem there exists \(n\) such that there is an isomorphic copy \(\widehat G\) of \(G\) into \(S_n.\) Then \[G\cong \langle S_n(S_n\setminus \widehat G)\rangle=S_n(S_n\setminus \widehat G).\]
If the set of patterns \(T\) must be independent of \(n\) the question is more subtle.
The next theorem shows that the question can be answered affirmatively for \(G=S_k,\) for any \(k.\)
Theorem 2. For all \(n\geq k\) we have \[\langle S_n(132,231,321,k\,1\,2\,\ldots\,k-2\quad k-1) \rangle \cong S_{k-1}.\]
Proof. The set \(S_n(132,231,321,k\,1\,2\,\ldots\,k-2\quad k-1)\) contains precisely the permutations \(id\) and \(t\,1\,2\,3\,\ldots\,t-1\quad t+1\,\ldots \,n-1\quad n\) for \(2\leq t\leq k-1.\) In fact, if \(\pi\) is in \(S_n(132,231,321,k\,1\,2\,\ldots\,k-2\quad k-1),\) the first symbol \(t=\pi_1\) must be smaller than or equal to \(k-1\) in order to avoid the patterns \(321\) and \(k\,1\,2\,\ldots\,k-2\quad k-1.\) If \(t=1,\) \(\pi=id\) because the other symbols must appear in increasing order, since \(\pi\) avoids \(132.\) If \(t\geq 2,\) the second symbol \(\pi_2\) must be equal to 1 in order to avoid \(231\) and \(321.\) All the other symbols must be in increasing order, in order to avoid \(132.\)
We deduce that the set \(S_n(132,231,321,k\,1\,2\,\ldots\,k-2\quad k-1)\) consists of the identity and the cycles \((1\,2),\) \((1\,3\,2),\) \((1\,4\,3\,2),\) \(\ldots\), \((1\,k-1\quad k-2\,\ldots \,2).\) Hence, it generates a group isomorphic to \(S_{k-1}.\) ◻
In this section we consider a refinement of Question 1.
Question 3. Let \(G\) be any finite group. Is it possible to find a subset \(T\) of \(S\) and a positive integer \(n_0\) such that \(\langle S_n(T) \rangle=G\) for every \(n\geq n_0?\)
We observe that Theorem 2 gives an answer to this question for every symmetric group, while the answer is negative for some families of groups, as we will show in the present section.
We need some preliminary results. Firstly notice that, if \(\langle S_n(T)\rangle\) is isomorphic to a fixed group \(G\) for every \(n\geq n_0,\) the cardinality of \(S_n(T)\) must be bounded above by the order of \(G.\) Actually, the set of pattern avoiding permutations with limited growth rate are well studied. See e.g. [11-18], to cite only a few. We recall some definitions and results about such permutations, following [13].
An interval in a permutation is a sequence of contiguous entries whose values form an interval of natural numbers. A monotone interval is an interval in which the entries are increasing or decreasing. Given a permutation \(\sigma\) of length \(m\) and (possibly empty) permutations \(\alpha_1,\ldots,\alpha_m,\) the inflation of \(\sigma\) by \(\alpha_1,\ldots,\alpha_m\) is the permutation \(\pi=\sigma[\alpha_1,\ldots,\alpha_m]\) obtained by replacing the \(i\)-th entry of \(\sigma\) by an interval that is order isomorphic to \(\alpha_i\), while maintaining the relative order of the intervals themselves. For example, \[3142[1, 321, 1, 12] = 6\; 321\; 7\; 45,\] while \[3142[1, 321, \emptyset, 12] = 6\; 321\; 45.\]
A peg permutation \(\tilde \rho\) is a permutation \(\rho\) where some elements are labeled by the symbol \(+\) and some other elements are labeled by the symbol \(-.\) For example, \(\tilde \rho =3^{+}1^{-}24^{-}\) is a peg permutation whose underlying (non-pegged) permutation is \(3124.\)
The grid class of the peg permutation \(\tilde \rho\), where \(\rho=\rho_1\ldots\rho_n,\) denoted by \(Grid(\tilde \rho)\), is the set of all permutations that may be obtained inflating \(\rho\) by monotone intervals of type determined by the signs of \(\tilde \rho\). More precisely, the symbol \(\rho_i\) of \(\rho\) may be inflated by an increasing (resp., decreasing) possibly empty interval if \(\rho_i\) is labeled with a \(+\) (resp., \(-\)), while it may only be inflated by a single entry (or the empty permutation) if \(\rho_i\) is not labeled.
For example, the permutation \(45621387\) is an element of the grid class \(Grid(3^+1^-24^-).\)
We say that two peg permutations are equivalent if their grid classes are the same.
Given a set \(\tilde P\) of peg permutations, we denote the union of their corresponding grid classes by \[Grid(\tilde P)=\cup_{\tilde \rho \in P}Grid(\tilde \rho).\]
We will need the following result (see [13, Thm. 1.3]), which in turn is a consequence of some results in [11] and in [14].
Theorem 4. For a permutation class \(\mathcal{C}\) the following are equivalent:
The cardinality \(|\mathcal{C}_n|\) is a polynomial in \(n,\) for sufficiently large \(n.\)
\(|\mathcal{C}_n|<F_n\) for some \(n,\) where \(F_n\) is the \(n\)-th Fibonacci number.
\(\mathcal{C}=Grid(\tilde P),\) where \(\tilde P\) is a finite set of peg permutations.
Example 1. Consider the class \(\mathcal{C}=S(123, 231, 312).\) It is easily seen that \[S(123, 231, 312)=\{k\quad k-1\;\ldots\;2\;1\;n\quad n-1\;\ldots\;k+1,\quad 1\leq k\leq n\}.\]
The class \(\mathcal{C}\) can be written as \(\mathcal{C}=Grid(\tilde P),\) where \(\tilde P\) contains only the peg permutation \(1^-2^-.\)
The previous theorem allows us to describe the structure of permutation classes with growth rate bounded above by a constant.
Proposition 1. For a permutation class \(\mathcal{C}\) the following are equivalent.
\(\mathcal{C}=Grid(\tilde P),\) where \(\tilde P\) is a finite set of peg permutations, each of which is equivalent to a peg permutation with at most one labeled element.
For every \(n\geq 1,\) \(|\mathcal{C}_n|<K\), where \(K\) is a constant independent of \(n.\)
For sufficiently large \(n,\) \(|\mathcal{C}_n|=D,\) where \(D\) is a constant independent of \(n.\)
Proof.
\([\textit 1.\implies \textit 2.]\)
If \(\mathcal{C}=Grid(\tilde P)\) where \(\tilde P\) is a finite set of peg permutations each of which has at most one labeled element, then the cardinality of \(\mathcal{C}_n=Grid(\tilde P)\cap S_n\) is bounded above. In fact, let \(\tilde \rho=a_1\ldots a_r b^+ c_1\ldots c_s\) an element of \(\tilde P.\) If \(n\geq r+s,\) such an element gives rise to at most \(2^{r+s}\) elements in \(\mathcal C_n\), depending on how many of the \(a_i'\)s or \(c_j'\)s are inflated by the empty permutation. The same holds when the element \(b\) has label \(-.\)
\([\textit 2.\implies \textit 3.]\)
If 2. holds, \(\mathcal{C}\) obviously satisfies assertion 2. of 4. This means that \(|\mathcal{C}_n|\) is eventually a polynomial in \(n.\) But any non-constant polynomial in \(n\) is unbounded, and hence we must have that \(|\mathcal{C}_n|\) is eventually constant.
\([\textit 3.\implies \textit 1.]\)
If for every \(n\geq 1,\) \(|\mathcal{C}_n|=D,\) where \(D\) is a constant independent of \(n,\) the growth rate of \(|\mathcal{C}_n|\) is polynomial (the constant polynomial \(D\)). Hence, by the Theorem 4, \(\mathcal{C}=Grid(\tilde P)\), where \(\tilde P\) is a finite set of peg permutations. Suppose that in \(\tilde P\) there is a peg permutation \(\tilde \rho\) with more than one labeled element. Let \(a\) and \(b\) be two labeled elements in \(\tilde \rho,\) with \(a<b.\) We distinguish three cases.
(i) \(a\) appears before \(b\) and both are labeled with \(+.\)
(ii) \(b\) appears before \(a\) and both are labeled with \(-.\)
(iii) None of the previous conditions holds.
We handle the case i., case ii. being similar. If there exists a number \(k\) such that \(a<k<b\) either before \(a^+\) or after \(b^+\) in \(\tilde \rho,\) then inflating \(k\) with a single element and inflating \(a\) and \(b\) with varying sizes, we obtain \(n\) distinct elements in \(\mathcal{C}_n.\) This gives us a contradiction. We obtain a similar contradiction if there is a number \(k\) between \(a^+\) and \(b^+\) where either \(k<a\) or \(k>b.\) If there are two numbers \(k_1\), \(k_2\) such that \(a<k_1<k_2<b\) that appear between \(a^+\) and \(b^+\) with \(k_2\) appearing before \(k_1,\) we again obtain a similar contradiction. The only case left is when all the numbers \(a<k<b\) appear between \(a^+\) and \(b^+\) in increasing order. If any of these integers are labeled with a \(-\), we can use this element along with \(a^+\) to obtain a contradiction. If these integers all are unlabeled or labeled with a \(+\), the peg permutation we obtain by deleting all the elements in \([a + 1, b]\) from \(\tilde \rho\) and appropriately reducing the values of other elements, gives us an equivalent peg permutation with fewer labeled terms. We continue this process until we reduce each peg permutation in \(\tilde P\) to a peg permutation having at most one labeled element.
In case iii., we can inflate \(a\) and \(b\) by increasing or decreasing sequences of arbitrary length. Hence \(Grid(\tilde P)\cap S_n\) has at least \(n+1\) elements of the form \(t_1\,t_2\,\ldots\, t_k\,s_1\,s_2\,\ldots \,s_{n-k},\) with \(0\leq k\leq n,\) where \(t_1\,t_2\,\ldots\, t_k\) is the monotone sequence obtained by inflating \(a,\) \(s_1\,s_2\,\ldots \,s_{n-k}\) is the monotone sequence obtained by inflating \(b,\) and all the other elements of \(\rho\) have been inflated by the empty interval. This is a contradiction.
◻
Example 2. Consider the class \(\mathcal{C}=S(132, 312, 321, 2314).\)
It is easily seen that \[S_n(132, 312, 321, 2314)=\{2\;3\;\ldots\;n\;1,\quad 2\;1\;3\;\ldots\;n,\quad id_n\}\] for every \(n\geq 3.\)
Hence \(|\mathcal{C}_n|=3\) for \(n\geq 3.\) The class \(\mathcal{C}\) can be written as \(\mathcal{C}=Grid(\tilde P)\) where \(\tilde P=\{213^+,\,2^+1\}.\)
Notice also that the group generated by \(S_n( 132, 312, 321, 2314)\) is \(S_n\) by Lemma 5.
Theorem 5. Let \(T\subseteq S\) and let \(G\) be a finite group. Suppose that there exists \(n_0 \in \mathbb N\) such that \(\langle S_n(T)\rangle \cong G\) for every \(n\geq n_0.\)
Then \(S(T)=Grid(\tilde P),\) where every peg permutation in \(\tilde P\) is either unlabeled, or of the form \[\tilde \rho=a_1\ldots a_r \; (r+1)^+\;b_1\dots b_s,\] or \[\tilde \rho=b_1\dots b_s \; (r+1)^-\;a_1\ldots a_r,\] where \(a_i<r+1\) and \(b_j>r+1\), for every \(i\) and \(j\).
In other terms, for \(n\) sufficiently large, every \(\pi\in S_n(T)\) is either of the form \[\pi=123[\tau, id,\sigma]\] or of the form \[\pi=321[\sigma,\psi,\tau]\] where \(\tau \leq \,a_1\ldots a_r,\) \(\sigma \leq\,b_1\ldots b_s\) and \(|\tau|+|id|+|\sigma|=|\tau|+|\psi|+|\sigma|=n.\)
Proof. Since \(\langle S_n(T)\rangle =G\) for every \(n\geq n_0,\) the cardinality of \(S_n(T)\) is bounded above by the constant \(|G|=K\) independent of \(n.\) By the previous proposition, each element of the class \(S(T)\) can be obtained inflating a peg permutation with at most one labeled element.
Let \(\tilde \rho\) be such a peg permutation with exactly one labeled element.
Suppose \[\tilde \rho=a_1\ldots a_r \; c^+\;b_1\dots b_s,\] where \(c\) is the only labeled element, and suppose that there exists \(1\leq i\leq r\) with \(a_i>c.\) Then, inflating such \(a_i\) by the permutation \(1,\) every other \(a_j\) and \(b_j\) by the empty permutation and \(c\) by the increasing permutation, we obtain the element \(n\;1\;2\;\ldots\;n-1\in S_n(T)\) for every \(n.\) But this is a cycle of order \(n.\) Hence \(\langle S_n(T)\rangle\) contains at least \(n\) elements and its cardinality is not constant.
Similarly, if there exists \(1\leq i\leq s\) with \(b_i<c,\) the set \(S_n(T)\) contains the cycle \((1\;2\;3\;\ldots\; n)\) of order \(n.\)
Suppose otherwise that \[\tilde \rho=b_1\dots b_s \; c^-\;a_1\ldots a_r,\] where \(c\) is the only labeled element, and suppose that there exists \(1\leq i\leq s\) with \(b_i<c.\) Then, inflating such \(b_i\) by the empty permutation or by the permutation \(1,\) every other \(b_j\) and \(a_j\) by the empty permutation and \(c\) by a decreasing permutation (that is, \(\psi\)), we obtain that the elements \(\psi_n\) and \(\alpha=1\;n\quad n-1\;\ldots\;2\in S_n(T)\) for every \(n.\) But \(\alpha \psi_n=(1\;2\;\ldots \; n),\) a cycle of order \(n,\) and hence \(\langle S_n(T)\rangle\) contains at least \(n\) elements and its cardinality would not be constant.
Similarly, if there exists \(1\leq i\leq r\) with \(a_i>c,\) the set \(S_n(T)\) contains the permutations \(\psi_n\) and \(\beta=n-1\quad n-2\;\ldots\; 1\;n\), whose composition \(\psi_n \beta=(1\;2\;\ldots\;n)\) is a cycle of order \(n.\)
This concludes the proof of the first assertion.
Now we consider the second assertion. Let \(U\) the set of all peg permutations in \(\tilde P\) with no labeled elements, and let \(h\) be the maximal length of of an element in \(U\). Then, if \(n>h\), every element in \(S_n(T)\) can be obtained by inflating a peg permutation in \(\tilde P\setminus U\), namely, of one of the two forms above. Consider \[\tilde \rho=a_1\ldots a_r \; (r+1)^+\;b_1\dots b_s.\] Let \(\tau\) be a pattern in \(a_1\ldots a_r\) and \(\sigma\) a pattern in \(b_1\ldots b_s.\) Now inflate every element of \(\tau\) and \(\sigma\) by the permutation \(1,\) the element \(r+1\) by an increasing permutation and every other element by the empty permutation. In this way, we get the permutation \(\pi=123[\tau,id,\sigma].\)
The permutation \(\pi=321[\sigma,id,\tau]\) can be obtained similarly from a peg permutation of the form \[\tilde \rho=b_1\dots b_s \; (r+1)^-\;a_1\ldots a_r.\] ◻
Example 3. Consider the class \(S(123,132,231,3214).\)
The permutations in \(S_n(123,132,231,3214),\) with \(n\geq 3\) are \(\psi,\) \[\alpha=n\quad n-1\quad n-2\ldots \;4\;2\;1\;3\] and \[\beta=n\quad n-1\quad n-2\ldots \;4\;3\;1\;2.\]
Hence \(S(T)=Grid(\tilde P),\) where \(\tilde P\) consists only of the peg permutation \(4^-213.\)
We submit that, with the aid of GAP, it is possible to verify that \[\langle S_n(123,132,231,3214)\rangle \cong (S_3\times S_3) \rtimes \mathbb Z_2,\] for every \(n\geq 6,\) a group of order \(72\) (the symbol \(\rtimes\) denotes the semidirect product).
Now we are in position to answer Question 3 for every abelian \(G.\)
Theorem 6. Let \(T\subseteq S\) and let \(G\) be a finite, nontrivial abelian group. If there exists \(n_0\) in \(\mathbb N\) such that \(\langle S_n(T)\rangle \cong G\) for every \(n\geq n_0,\) then either \(G\cong \mathbb Z_2\) or \(G\cong \mathbb Z_2 \times \mathbb Z_2.\)
Proof. Suppose that \(S_n(T)\) generates a fixed finite abelian group \(G\) for every \(n\geq n_0.\)
By Theorem 5, \(\cup_{n\geq 0} S_n(T)=Grid(\tilde P),\) where \(\tilde P\) is a finite set of peg permutations each of which is either unlabeled, or of the form \[\tilde \rho=a_1\ldots a_r \; (r+1)^+\;b_1\dots b_s,\] or \[\tilde \rho=b_1\dots b_s \; (r+1)^-\;a_1\ldots a_r,\] where \(a_i<r+1\) and \(b_j>r+1\) , for every \(i\) and \(j\).
(Case 1) Suppose that in \(\tilde P\) there exists a peg permutation \[\tilde \rho=a_1\ldots a_r \; (r+1)^+\;b_1\dots b_s.\]
If \(a_1\,\ldots \, a_r\) contains a subsequence \(a_x,a_y,a_z\) order isomorphic to \(132,\) then, inflating \(a_x,\) \(a_y\) and \(a_z\) by the permutation \(1,\) every other \(a_i\) and \(b_j\) with the empty permutation and \(c\) with an increasing permutation, we obtain in \(S_n(T)\) the permutation \(1\,3\,2\,4\,5\,\ldots\,n=(2\;3).\)
Inflating \(a_y\) and \(a_z\) by the permutation \(1,\) every other \(a_i\) and \(b_j\) with the empty permutation and \(c\) with an increasing permutation we obtain in \(S_n(T)\) the permutation \(2\,1\,3\,4\,\ldots\,n=(1\;2).\) But this is impossible since \((1\;2)\) and \((2\;3)\) do not commute.
Reasoning as above, if \(a_1\,\ldots \, a_r\) contains the pattern \(321\) we get the cycles \((1\;2)\) and \((1\;3)\) that do not commute.
If \(a_1\,\ldots \, a_r\) contains the pattern \(231\) we get the cycles \((1\;2)\) and \((1\;2\;3)\) that do not commute.
If \(a_1\,\ldots \, a_r\) contains the pattern \(312\) we get the cycles \((1\;2)\) and \((1\;3\;2)\) that do not commute.
As a consequence, \(a_1\,\ldots \, a_r \in S_r(132,231,312,321)\) and hence either \[a_1\,\ldots \, a_r=id_r,\] or \[a_1\,\ldots \, a_r=2\;1\;3\;4\;\ldots\;r.\]
Now we turn our attention to the suffix \(b_1\,\ldots\,b_s.\)
If \(b_1\,\ldots \, b_s\) contains the subsequence \(b_x,b_y,b_z\) order isomorphic to \(321,\) then, inflating \(b_x,\) \(b_y\) and \(b_z\) by the permutation \(1,\) every other \(a_i\) and \(b_j\) with the empty permutation and \(c\) with an increasing permutation, we obtain in \(S_n(T)\) the transposition \((n-2,\;n).\)
Inflating \(b_y\) and \(b_z\) by the permutation \(1,\) every other \(a_i\) and \(b_j\) by the empty permutation and \(c\) by an increasing permutation we obtain in \(S_n(T)\) the transposition \((n-1,\;n).\) But this is impossible since \((n-2,\;n)\) and \((n-1,\;n)\) do not commute.
Similarly, if \(b_1\,\ldots \, b_s\) contains the pattern \(231\) we get the cycles \((n-1\;n)\) and \((n-2\;n-1\;n)\) that do not commute.
If \(b_1\,\ldots \, b_s\) contains the pattern \(213\) we get the cycles \((n-1\;n)\) and \((n-2\;n-1)\) that do not commute.
If \(b_1\,\ldots \, b_s\) contains the pattern \(312\) we get the cycles \((n-1\;n)\) and \((n-2\;n\;n-1)\) that do not commute.
As a consequence, the suffix \(b_1\,\ldots \, b_s\) of \(\tilde\rho\) is a permutation of the symbols \(\{r+2,\ldots ,r+s+1\}\) that avoids \(213,231,312,\) and \(321\). It is easily seen that \(b_1\,\ldots \, b_s\) is either the identity or the transposition that exchanges the two last symbols.
We deduce that the peg permutation \(\tilde \rho\) is one of the following \[1^+,\; 213^+,\;1^+32,\;213^+54.\]
(Case 2) Suppose that in \(\tilde P\) there exists a peg permutation \[\tilde \rho=b_1\dots b_s \; (r+1)^-\;a_1\ldots a_r.\]
Inflating every \(a_i\) and every \(b_j\) by the empty permutation and \(r+1\) by a decreasing permutation, we get the permutation \(\psi_n\in S_n(T).\) Notice that every other permutation \(\alpha\) in \(S_n(T)\) must commute with \(\psi_n\) because we are supposing that \(S_n(T)\) generates a commutative group. But \(\alpha \psi_n=\psi_n \alpha\) is equivalent to \(\alpha=\alpha^{rc}.\) Hence every element of \(S_n(T)\) must be equal to its reverse-complement.
Now consider once more the peg permutation \[\tilde \rho=b_1\dots b_s \; (r+1)^-\;a_1\ldots a_r.\] If \(b_1\dots b_s\) contains the pattern \(12\) realized by the elements \(b_x\) and \(b_y\) (with \(x<y\)), inflating \(b_x\) and \(b_y\) by the permutation \(1,\) every other \(b_i\) and \(a_j\) by the empty permutation and \(r+1\) by a decreasing permutation, we get the permutation \(\alpha=n-1\quad n\quad n-2\quad n-3\;\ldots 1\in S_n(T).\) This is impossible since \(\alpha\neq \alpha^{rc}.\) As a consequence \(b_1\dots b_s\) and, similarly, \(a_1\dots a_r\), must be decreasing, and hence \(\tilde \rho\) is equivalent to the peg permutation \(1^-.\)
Case 1 and Case 2 prove that \(S(T)=Grid(\tilde P),\) where \(\tilde P\) contains either unlabeled permutations or elements from the set of peg permutation \[\{1^-,\;1^+,\; 213^+,\;1^+32,\;213^+54\}.\]
It is easily checked that if \(\tilde P\) contains \(1^-\), then \(\tilde P\) does not contain \(213^+,\) \(1^+32,\) \(213^+54\), since \(G\) is commutative. For every possible choice of \(\tilde P\) we can only get either \(G\cong \mathbb Z_2\) or \(G \cong \mathbb Z_2\times \mathbb Z_2\) for \(n\) large.
This concludes the proof. ◻
Example 4. Consider \(\langle S_n(213,231,312,321)\rangle.\) This group is isomorphic to \(\mathbb Z_2\) for \(n\geq 2\) as we will prove in Theorem 1.
Consider now the set \(S_n(231,321,312,1324).\) We have \[\langle S_n(231,312,321,1324)\rangle=\mathbb Z_2 \times \mathbb Z_2\] for every \(n\geq 4.\)
In fact, given a permutation in the generating set, the symbols \(n-1\) and \(n\) must occupy the last and the second last position, otherwise the permutation would contain 312 or 321. Similarly, the symbols 1 and 2 must occupy the first or the second position. The remaining symbols must be in increasing order since the permutation must avoid 1324.
Hence the set \(S_n(231,321,312,1324)\) contains only the identity, the elementary transpositions \((1\,2)\) and \((n-1\,n)\), and the involution \((1\,2)(n-1\,n),\) which generate \(\mathbb Z_2\times \mathbb Z_2.\)
Now we consider Question 3 when \(G\) is a simple group.
Theorem 7. Let \(T\subseteq S\) and let \(G\) be a finite simple group. If there exists \(n_0\) in \(\mathbb N\) such that \(\langle S_n(T)\rangle \cong G\) for every \(n\geq n_0,\) then \(|G|\leq 2.\)
Proof. Suppose by contradiction that \(S_n(T)\) generates a fixed simple group \(G,\) with \(|G|\geq 3,\) for every \(n\geq n_0.\)
We recall that a given subgroup of \(S_n\) that contains an odd permutation cannot be isomorphic to a simple group other than \(\mathbb Z_2,\) since it contains a subgroup of index \(2.\)
Theorem 5 implies that \(\cup_{n\geq 0} S_n(T)=Grid(\tilde P)\), where \(\tilde P\) is a finite set of peg permutations each of which is either unlabeled, or of the form \[\tilde \rho=a_1\ldots a_r \; (r+1)^+\;b_1\dots b_s,\] or \[\tilde \rho=b_1\dots b_s \; (r+1)^-\;a_1\ldots a_r,\] where \(a_i<r+1\) and \(b_j>r+1.\) , for every \(i\) and \(j\).
If one peg permutation of the second kind appears in \(\tilde P,\) inflating each \(a_i\) and \(b_j\) by the empty permutation and \(r+1\) by a decreasing permutation we get \(\psi_n\in S_n(T)\) for every \(n.\) But \(\psi_n\) is odd if \(n\equiv 3 \mbox{ (mod }4),\) which gives a contradiction. Hence every labeled peg permutation in \(\tilde P\) is of the first kind.
Let \[\tilde \rho=a_1\ldots a_r \; (r+1)^+\;b_1\dots b_s\] be one of the labeled peg permutations in \(\tilde P.\)
Suppose that \(a_1\ldots a_r\) contains the pattern \(21,\) realized by the elements \(a_x\) and \(a_y\) (with \(x<y\)). Then, inflating \(a_x\) and \(a_y\) by the permutation \(1,\) every other \(a_i\) and \(b_j\) by the empty permutation and \(r+1\) by the identity, we get the permutation \(2\,1\,3\,\ldots\,n=(1\;2)\in S_n(T).\) This is impossible, since this permutation is odd. Hence \(a_1\ldots a_r=id_r.\)
One can show similarly that \(b_1\ldots b_s\) must be the increasing permutation \(id_s.\)
As a consequence \(\tilde \rho\) is equivalent to \(1^+,\) the set \(S_n\cap Grid(\tilde P)\) contains only \(id_n\) for sufficiently large \(n\), and \(\langle S_n(T)\rangle= \{id_n\}.\)
But this contradicts the fact that \(|G|\geq 3.\) ◻
Corollary 1. Let \(T\subseteq S\) and let \(A_m\) be an alternating group. If there exists \(n_0\) in \(\mathbb N\) such that \(\langle S_n(T)\rangle \cong A_m\) for every \(n\geq n_0,\) then \(m \leq 2.\)
Proof. The result is a trivial consequence of the previous theorem, since the alternating group \(A_m\) is simple for every \(m\geq 3\) with the exception of \(m=4.\) In this last case the result can be proved with arguments similar to those used in the proof of the previous theorem. ◻
From now on we consider the groups \(\langle S_n(T) \rangle\) for particular sets of patterns \(T.\)
We are interested in determining when \(S_n(T)\) generates the whole symmetric group and which other groups arise.
First of all we state a rather general result that allows us to determine sets \(T\subseteq S\) such that \(\langle S_n(T) \rangle=S_n.\)
Theorem 8. Let \(T\subseteq S\). If either \[T\cap \{k\;2\;3\ldots k-1\quad 1,\quad k\;1\;2\ldots k-1,\quad 2\;3\ldots k\;1,\quad id_k \;|\; k\geq 1\}=\emptyset,\] or \[T\cap \{id_k,\quad(r-1\quad r)\;|\; 2\leq r\leq k \mbox{ and }k\geq 1 \}=\emptyset,\] or \[T\cap \{2\;3\ldots k\;1,\quad id_k,\quad 2\;1\;3\ldots k \;|\; k\geq 1\}=\emptyset,\] or \[T\cap \{1\;\ldots k-2\quad k\quad k-1,\quad id_k,\quad 2\;3\;\ldots k \;1 \;|\; k\geq 1\}=\emptyset,\] then \(\langle S_n(T)\rangle=S_n\) for every \(n.\)
Proof. For any \(n\geq k\) note that
the patterns of length \(k\) contained in at least one elementary transposition in \(S_n\) are \(id_k\) and \(\quad(r-1\, r)\mbox{ for }2\leq r\leq k,\)
the patterns of length \(k\) contained either in the cycle \((1\;n)\in S_n\) or in \((1\;2\;\ldots \;n)\in S_n\) are \(k\;2\;3\ldots k-1\quad 1,\quad k\;1\;2\ldots k-1,\quad 2\;3\ldots k\;1,\quad id_k,\)
the patterns of length \(k\) contained either in the cycle \((1\;2)\in S_n\) or in \((1\;2\;\ldots \;n)\in S_n\) are \(2\;3\ldots k\;1,\quad id_k,\quad 2\;1\;3\ldots k,\) and
the patterns of length \(k\) contained either in the cycle \((n-1\;n)\in S_n\) or in \((1\;2\;\ldots \;n)\in S_n\) are \(2\;3\ldots k\;1,\quad id_k,\quad 1\;2\ldots k-2\quad k\quad k-1.\)
The assertion now follows by Lemma 5. ◻
Corollary 2. We have
if \(T\subseteq S_3\) and \(\langle S_n(T)\rangle\neq S_n\) for some \(n\geq 3,\) then \(T\) shares at least an element with each one of the following sets \[\{123, 231, 312, 321\},\; \{123,132,213\},\;\{123,213,231\},\mbox{ and }\] \[\{123,132,231\}.\]
if \(T\subseteq S_4\) and \(\langle S_n(T)\rangle \neq S_n\) for some \(n\geq 4,\) then \(T\) shares at least an element with each one of the following sets \[\{1234, 2341, 4123, 4231\},\;\{1234,1243,1324,2134\},\] \[\{1234,2134, 2341\},\mbox{ and }\{1234,1243,2341\}.\]
In this section we consider the group generated by the set \(S_n(T)\), where \(|T|\leq 3.\)
We begin with the analysis of \(\langle S_n(T)\rangle\) when \(T\) consists of three patterns of length 3.
Theorem 9.
\(\langle S_n(123,321,\tau) \rangle = \{id_n\},\) for every \(n>4\) and for every \(\tau\in S_3.\)
\(\langle S_n(132,213,321) \rangle \cong \mathbb{Z}_n,\)
\(\langle S_n(123,231,312) \rangle \cong D_n,\) for every \(n\geq 3\).
\(\langle S_n(T)\rangle =S_n\) for every other set \(T\) of three patterns of length three.
Proof. The statement follows easily from the characterization of the sets of permutations avoiding patterns of length three and from Corollary 2. ◻
As a consequence, we can characterize all the groups \(\langle S_n(T) \rangle\) where \(T\) contains no more than three arbitrary patterns.
Corollary 3. Let \(T\subseteq S\) be a set of patterns of length at least three, with \(|T|\leq 3.\)
If \(\{ id_r,\psi_s\}\subseteq T,\) for some \(r,s \geq 1,\) then \(\langle S_n(T)\rangle = \{ id_n\}\) for \(n>(r-1)(s-1).\)
If for every \(r,s\geq 1\) \(\{ id_r,\psi_s\}\nsubseteq T,\) \(T\neq \{132,213,321\}\) and \(T\neq \{123,231,312 \},\) then \(\langle S_n(T)\rangle = S_n.\)
Proof. The first assertion is trivial since the set \(S_n(T)\) is empty for \(n\) sufficiently large when \(\{ id_r,\psi_s\}\subseteq T.\) In fact, every permutation of length \(n>(r-1)(s-1)\) must contain a monotonically increasing subsequence of length \(r\) or a monotonically decreasing subsequence of length \(s,\) by the Erdős-Szekeres Theorem [20].
To prove the second assertion, recall that, by Theorem 9, the only sets \(T\) of three patterns of length three such that \(\langle S_n(T)\rangle \neq S_n\) are \(\{123,321,\tau\}\) (for any \(\tau\in S_3\)), \(\{132,213,321\}\) and \(\{123,231,312\}\). Hence, the second assertion follows from Theorem 9 and from Lemmas 1 and 2 in all cases, except for the following ones.
\(T\) consists of three (distinct) patterns \(\tau_1,\tau_2\) and \(\tau_3\) with \(\tau_1\geq 123,\) \(\tau_2\geq 231\) and \(\tau_3\geq 312,\) with at least one of these patterns of length strictly greater than 3.
\(T\) consists of three (distinct) patterns \(\tau_1,\tau_2\) and \(\tau_3\) with \(\tau_1\geq 132,\) \(\tau_2\geq 213\) and \(\tau_3\geq 321,\) with at least one of these patterns of length strictly greater than 3.
\(T\) consists of three (distinct) patterns \(\tau_1,\tau_2\) and \(\tau_3\) with \(\tau_1\geq 123,\) \(\tau_2\geq 321,\) with at least one of these patterns of length strictly greater than 3.
Our goal now is to prove that \(\langle S_n(\tau_1,\tau_2,\tau_3)\rangle =S_n\) in all the previous cases. We can assume that two of the patterns have length 3 and the other one has length 4. The cases with longer patterns will follow from the previous one by Lemma 2.
A long but trivial case-by-case analysis led us to consider only the following sets of patterns, since the other ones can be excluded applying once again Lemma 2 and Theorem 9.
\[\{123,312, 3421\},\qquad \{132, 321, 2134\},\qquad \{132, 213, 4321\}\]
\[\{213,321,1243\},\qquad \{123,231,4312 \},\qquad \{231,312,1234\}.\]
We prove only that \[\langle S_n(231,312,1234)\rangle=S_n,\] the other cases being similar.
Notice that \[\langle S_n(231,312,1234)\rangle=\] \[\langle S_n(231,312,1234)\cup S_n(132,213,4321)\rangle\] by Lemma 4. This last group is \(S_n\) because \(S_n(132,213,4321)\) contains the cycles \((1\;n)\) and \((1\;2\;\ldots \;n),\) which generate \(S_n\) by Lemma 5. ◻
In this section we begin the study of the groups \(\langle S_n(T)\rangle\), where \(T\) has cardinality greater than three. We select some of the most meaningful cases.
The following theorem that follows directly from the results contained in [19] covers the cases of groups generated by \(S_n(T)\) for all the subsets \(T\subseteq S_3\) not considered so far.
Theorem 10.
\(\langle S_n(213,231,312,321) \rangle \cong \langle S_n(132,231,312,321) \rangle \cong\)
\(\langle S_n(132,213,231,312) \rangle\cong \mathbb{Z}_2,\)
\(\langle S_n(123,132,213,231) \rangle \cong \langle S_n(123,132,213,312) \rangle \cong D_4,\)
\(\langle S_n(132,213,312,321) \rangle \cong \langle S_n(132,213,231,321) \rangle \cong \mathbb{Z}_n,\)
\(\langle S_n(123,213,231,312) \rangle \cong \langle S_n(123,132,231,312) \rangle \cong D_n,\)
\(\langle S_n(123,132,213,231,312) \rangle \cong \mathbb Z_2,\)
\(\langle S_n(132,213,231,312,321) \rangle \cong \mathbb \{id_n\}.\)
The study of the groups generated by sets \(S_n(T)\) where \(T\subseteq S_4\) and \(|T|\geq 4\) is more cumbersome. We limit ourselves to state the following result whose proof is analogous to the proof of Corollary 3.
Theorem 11. Let \(T\subseteq S_4\) with \(|T|=4.\) Suppose that \(T\) does not contain \(\psi_4\) and that \(T\neq\{1234, 1432, 3214, 4312 \}\) and \(T\neq \{1234, 1432, 3214, 4231\}.\) Then \(\langle S_n(T)\rangle=S_n.\)
For the sake of completeness, we submit that routine arguments show that the sequences \((\langle S_n(1234, 1432,3214, 4312)\rangle)_{n\geq 0}\) and \((\langle S_n(1234, 1432,3214, 4231)\rangle)_{n\geq 0}\) are eventually constant. In particular, with the aid of GAP, [21] we verified that
\[\langle S_n(1234, 1432,3214, 4312)\rangle\cong (A_9\times A_9)\rtimes D_4\mbox{ for }n\geq 18\]
and
\[\langle S_n(1234, 1432,3214, 4231)\rangle\cong (A_6\times A_6)\rtimes D_4\mbox{ for }n\geq 12.\]
We conclude the paper with some open problems.
Firstly, suppose that the sequence \((S_n(T))_{n\geq 0}\) is eventually constant. What kind of groups arise in this way? For example, is it possible to obtain the dihedral group \(D_k,\) for \(k>4?\)
Another problem is that of completing the classification of \(\langle S_n(T)\rangle\) when \(T\) consists of four or more patterns. In particular, we wonder whether there exists a general procedure to determine the group \(\langle S_n(T)\rangle\) for any finite set of patterns \(T.\)
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
We would like to express our sincere gratitude to the anonymous referees, whose insightful comments and careful reading greatly enhanced the quality of this paper.
The authors declare no conflict of interest