All Questions
62 questions
32
votes
3
answers
3k
views
Order of products of elements in symmetric groups
Let $n \in \mathbb{N}$. Is it true that for any $a, b, c \in \mathbb{N}$ satisfying
$1 < a, b, c \leq n-2$ the symmetric group ${\rm S}_n$ has elements of order $a$ and $b$
whose product has order $...
- 19.6k
31
votes
2
answers
1k
views
Does the symmetric group $S_{10}$ factor as a knit product of symmetric subgroups $S_6$ and $S_7$?
By knit product (alias: Zappa-Szép product), I mean a product $AB$ of subgroups for which $A\cap B=1$. In particular, note that neither subgroup is required to be normal, thus making this a ...
- 1,068
28
votes
3
answers
2k
views
When is $S_n \times S_m$ a subgroup of $S_p$?
I asked the following question on math.stackexchange several months ago:
Let $n,m,p>1$ be such that $S_n \times S_m \hookrightarrow S_p$. Does it imply that $p \geq n+m$?
Derek Holt gave a ...
- 2,371
20
votes
3
answers
940
views
What did Frobenius prove about $M_{12}$?
I am interested in this paper which I can't read because it's in German:
Frobenius, G., Über die Charaktere der mehrfach transitiven Gruppen., Berl. Ber. 1904, 558-571 (1904). ZBL35.0154.02.
A free ...
- 11.2k
17
votes
1
answer
1k
views
Does O'Nan-Scott depend on CFSG?
My question is in the title. Some context: there are two versions of the O'Nan-Scott theorem. The first, weaker version, is due to O'Nan and Scott (independently) and gives the structure of the ...
- 11.2k
16
votes
2
answers
722
views
Minimal maximal subgroup of the symmetric group
The question is pretty much in the title: What is the maximal subgroup of $S_d$ of maximal index (so minimal size)? A slight variant (I am not sure if it leads to a different answer) is: what if we ...
- 96.4k
16
votes
1
answer
1k
views
Tensor power of the natural representation of Sn
The symmetric group $S_n$ acts over $V=\mathbb{R}^n$ by permuting the canonical basis.
So it acts over $V^{\otimes p}$ with a diagonal action (acts the same over each element of the tensor product).
...
- 583
14
votes
1
answer
959
views
The number of involutions in a permutation group
If $G$ is a group let $I(G)$ be the number of involutions (elements of order 2) in $G$. My question is then easily stated: does there exists a constant $C > 1$ such that for every $n \ge 1$ and ...
- 3,399
12
votes
1
answer
450
views
abelian quotients of permutation groups
Let $G$ be a subgroup of the permutation group $S_n$, and let $H$ be a normal subgroup of $G$ such that the quotient group $G/H$ is abelian. What is the best known upper estimate for the cardinality $...
- 1,294
12
votes
0
answers
699
views
Solving a set of equations in a finite symmetric group
A standard way to find solutions to a finite set of equations in a finite symmetric group
${\rm S}_n$ is to take the equations as relators of a finitely presented group, to use
the low index subgroups ...
- 19.6k
11
votes
1
answer
248
views
How many steps are required for double transitivity?
Let $A$ be a set of generators of $S_n$, or of a doubly transitive
subgroup of $S_n$. Assume $e\in A$, $A=A^{-1}$. What is the least $k$
such that $A^k$ is doubly transitive as a set? That is, what is ...
- 20.2k
10
votes
0
answers
194
views
Permutation groups with diameter $O(n \log n)$
I suspect that many permutation puzzles can be solved in $O(n \log n)$ moves, which has led me to the following question/conjecture:
Suppose that
1. $P_i$ for $i<k=O(1)$ are permutations on an $n$ ...
- 7,545
9
votes
1
answer
579
views
Generalization of Frobenius groups
Frobenius group is a transitive permutation group on a finite set, such that no non-trivial element fixes more than one point and some non-trivial element fixes a point.
In other words, if in a ...
- 323
9
votes
2
answers
330
views
Can $1\ne H\cap H^g\lhd H$ happen if $G$ is a primitive permutation group with stabiliser $H$?
Assume everything is finite.
Let $G$ be a primitive permutation group with point stabiliser $G_\alpha$ for some $\alpha$. For $\beta\ne\alpha$, by an arc stabiliser we mean $G_{\alpha\beta}=G_\alpha\...
- 379
9
votes
2
answers
432
views
Vertex-primitive graphs with two vertices having almost the same neighbourhood
Hypothesis: Let $\Gamma$ be a vertex-primitive graph with two vertices $u$ and $v$ such that $$|N(u) \cap N(v)|=|N(v)|-1$$
Question: Is it true that $\Gamma$ must either be a complete graph or have ...
- 3,291
8
votes
2
answers
586
views
How hard is it to compute the diameter and the growth function of a finite permutation group of small degree?
Let $G \leq {\rm S}_n$ be a finite permutation group, and let
$S = \{g_1, \dots, g_k\}$ be a generating set for $G$ which is closed
under inversion and which does not contain the identity.
The growth ...
- 19.6k
7
votes
6
answers
1k
views
Transitive permutation groups which all of their proper subgroups are intransitive
Let $G$ be a transitive permutation group on a finite set $\Omega$. It is clear
that if $G$ is regular, then every proper subgroup of $G$ is intransitive. Is
there any other class of groups with this ...
- 792
7
votes
2
answers
422
views
Automorphism group of a special commuting graph
Suppose $S_6$ is the symmetric group on six letters and let $X$ denote the conjugacy class containing $(12)(34)$. Define a graph $\Gamma$ with vertex set $X$ and edges precisely the 2-element subsets ...
- 81
7
votes
2
answers
547
views
Classification of generously transitive groups
A permutation group $G \lt S_n$ is called generously transitive, if for each $i,j$ there exists a permutation that interchanges them. Is there a reasonable classification of such (finite) groups?
- 972
7
votes
1
answer
729
views
number of maximal subgroups of the symmetric group
What is the asymptotics of the number of the maximal subgroups of $S_n$ (as a function of $n$)? This must be written down somewhere...
EDIT I am actually more interested in the number of conjugacy ...
- 96.4k
7
votes
1
answer
344
views
For which $n$ can $S_n$ act transitively on $n+k$ elements?
It is known that the symmetric group $S_n$ can act transitively on $n+1$ elements if and only if $n=5$.
Are there similar classifications for $S_n$ acting transitively on $n+k$ elements, where $k$ is ...
- 13.6k
7
votes
1
answer
582
views
Wreath product $S_k\wr S_n$ inside $S_{kn}$
I want to understand wreath products a little better.
Currently, my intuition about them is as follows. Take $nk$ disks, pile them in order forming $n$ piles of $k$ disks (one pile contains disks {1,...
- 1,549
6
votes
2
answers
623
views
Two groups acting on a set.
Suppose we are given a set S of points on which two different groups G and G' (given by sets of generating permutations) act. Is there an efficient algorithm for finding generators the largest pair ...
- 397
6
votes
1
answer
2k
views
Are there infinitely many insipid numbers?
A number $n$ is called insipid if the groups having a core-free maximal subgroup of index $n$ are exactly $A_n$ and $S_n$. There is an OEIS enter for these numbers: A102842. There are exactly $486$ ...
6
votes
1
answer
462
views
Primitive, non-2-transitive groups with very large orbitals?
Let $G$ be a transitive permutation group on a set $X$ with $n$ elements. Assume that $G$ is primitive, i.e., $G$ preserves no non-trivial partition of $X$. Assume as well that $G$ is not $2$-...
- 20.2k
6
votes
1
answer
435
views
Doubly primitive groups with simple socle
The classification of doubly transitive groups with simple socle is
known. A good account of such classification can be found for example
in this paper:
Cameron, Peter J. Finite permutation groups ...
- 3,078
5
votes
2
answers
2k
views
Transitive subgroup of $S_p$ containing a $p$-cycle and a double transposition
Let $p$ be a prime other than 5 or 7. Are $A_p$ and $S_p$ the only subgroups of $S_p$ that contains a $p$-cycle and a double transposition?
As for $p = 5$, the dihedral group $D_{10}$ contains a 5-...
- 263
5
votes
1
answer
502
views
Time Complexity of the Word Problem for Finite Permutation Groups
Given a finite permutation group, i.e. a subgroup of the symmetric group on $n$ symbols in terms of generators, what is the complexity of the word problem? That is, computing if two words in the ...
- 798
5
votes
3
answers
498
views
Generation of permutation groups by fixed elements subgroups
Suppose $(H,X)$ is a permutation group (with $H$ a group acting faithfully on the set $X$). Under what circumstances is $H$ generated by its subgroups $H_x$, where $H_x$ is the subgroup of $H$ fixing $...
- 4,547
5
votes
1
answer
253
views
Irreducible deleted permutation module for a finite group
Let $G$ be a subgroup of the symmetric group $S_n = \operatorname{Sym}(X)$.
Let $k$ be a field, and let $V$ be the permutation module corresponding to $X$.
Then $V$ is not irreducible, it has a $1$-...
- 2,821
5
votes
1
answer
193
views
composition factors of primitive components
A finite transitive permutation group $G$ can always be ``decomposed'' into primitive permutation groups, called its primitive components, although the decomposition is not unique. See Chapter 1 of ...
- 537
5
votes
1
answer
441
views
Minimum word length for an unusual set of generators of the symmetric group
Problem. Let $n\geq 2$ and let $T$ be the set of all permutations in $S_n$ of the form
$$t_k:=\prod_{1\leq i\leq k/2}(i,k-i) \qquad \hbox{for $k=3,4,\ldots,n+1$}.$$
Find the least integer $f_n$...
5
votes
0
answers
300
views
Uniqueness of the direct product decomposition of inclusions of finite groups
This post is a generalization of Uniqueness of the direct product decomposition of finite groups.
Here we look inclusions of finite groups $(H \subset G)$ instead of just finite groups.
Definition: ...
5
votes
0
answers
181
views
Information about permutation character from local action
Let $G$ be a finite permutation group acting transitively, but not regularly, on a set $V$. Let $H$ be the stabilizer of some point $v\in V$, and suppose that $H$ acts 2-transitively on one of its (...
- 11.2k
4
votes
3
answers
328
views
Is a point stabilizer in the Mathieu group $M_{20}$ half-transitive?
The background: We recall/define the following:
$\Omega_n=\{1,\dots,n\}$.
$M_n$ is the Mathieu group of degree $n$. We follow the Wikipedia article "Mathieu group" and define these groups ...
- 1,068
4
votes
2
answers
370
views
Minimal degree of primitive permutation group
Helmut Wielandt discussed an old question (Chap. 2, Section 15, which can be dated back to Camille Jordan):
Let $g\neq 1$ be a permutation in some finite primitive permutation group $G$ of degree $n$. ...
- 3,337
4
votes
1
answer
448
views
Generalization of a property of $A_n; n\geq 5$
Let $H$ and $K$ be two proper non-trivial subgroups of the
alternating group $A_n; n\geq 5$.
Then there exists a maximal subgroup $M$ of $A_n$
such that $H\not\leq M$ and $K\not\leq M$.
To see this
...
- 487
4
votes
1
answer
152
views
Diameter for permutations of bounded support
Let $S\subset \textrm{Sym}(n)$ be a set of permutations each of which is of bounded support, that is, each $\sigma\in S$ moves $O(1)$ elements of $\{1,2,\dotsc,n\}$. Let $\Gamma$ be the graph whose ...
- 20.2k
4
votes
1
answer
202
views
Example of primitive permutation group with a regular suborbit and a non-faithful suborbit
I would like some examples of groups $G$ satisfying all of the following criteria:
$G<Sym(n)$, the symmetric group on $n$ letters, and $G$ is primitive.
$G$ has a regular suborbit, i.e. if $M$ is ...
- 11.2k
4
votes
0
answers
115
views
Complexity to find "short" (e.g. polynomial in diameter) decomposition of the permutation into the product of generators?
Question 1: Consider the symmetric group $S_n$ and some set of permutations $p_i$. Given permutation $g$ - what is known about the algorithmic complexity to decompose $g$ into product of $p_i$ ...
- 24.9k
4
votes
0
answers
88
views
Diameters of permutation groups with transitive generators
Suppose that for a permutation puzzle on $n$ elements we have a subroutine to place any $m>3$ elements in arbitrary positions (possibly scrambling the rest). Can we solve the puzzle (if it is ...
- 7,545
3
votes
2
answers
338
views
Length of composition series in a primitive group
Let $G$ be a primitive group acting on a set $\Omega$ with $n$ elements. By Cameron/Liebeck (essentially a consequence of the Classification + O'Nan-Scott), there are two possibilities:
(a) $G$ has a ...
- 20.2k
3
votes
1
answer
129
views
Holt's Theorem on doubly transitive groups with $2$-central involutions fixing only one letter
In D. F. Holt, Transitive permutation groups in which an involution central in a Sylow 2-subgroup fixes a unique point, Proc. London Math. Soc. 37 (1978), 165–192, Derek Holt classifies finite doubly ...
- 4,547
3
votes
2
answers
275
views
If d("G/H") < d(G) = 2, must H contain a primitive element?
Let $G$ be a finite group that can be generated by $2$ elements, and let $H \leq G$ be a (not necessarily normal) subgroup for which there exists some $g \in G$ such that $H \langle g\rangle = G$. ...
- 11.3k
3
votes
0
answers
302
views
What's the ratio of inclusions of finite groups with a distributive lattice?
Definition: Two inclusions of finite groups are equivalent, $(A \subset B) \sim (C \subset D)$, if: $(A/A_B \subset B/A_B) \simeq (C/C_D \subset D/C_D)$ with $A_B$ the normal core of $A$ in $B$.
...
3
votes
0
answers
111
views
Double coset relation for unique intermediate subgroup (with homogeneity)
Let $G$ be a group and $H$ a subgroup such that there is a unique (non-trivial) intermediate subgroup $K$ (i.e. $H < S < G$ implies $S=K$) and $(H \subset K) \sim (K \subset G)$ (homogeneity) ...
2
votes
1
answer
964
views
Is there a formula for the number of elements in $S_n$ having length $k$ with respect to the generators taken to be the transpositions?
Define the length of a permutation as the minimum number of adjacent transpositions needed to describe it.
We know that there is only one element of length $0$ in $S_n$ and $n-1$ elements of length $1$...
- 21
2
votes
2
answers
527
views
Does the hyperoctahedral group have only 3 maximal normal subgroups?
An hyperoctahedral group $G$ is the wreath product of $S_2$ and $S_n$, where $S_{n}$ is the symmetric group on $n$ letters, or in other words the semi-direct product $G=S_2^n\rtimes S_n$, w.r.t. the ...
- 3,362
2
votes
1
answer
137
views
Intransitive finite irreducible linear groups whose orbits are all large
I am interested in intransitive irreducible linear subgroups $G\subseteq\mathrm{GL}_n(\mathbb{F}_p)$ acting on $V-\{0\}=\mathbb{F}_p^n-\{0\}$ in the natural way, such that all of the orbits are very ...
- 537
2
votes
1
answer
254
views
Classification of indecomposable inclusions $(H \subset G)$ with $G$ decomposable
Definition: A group $G$ is indecomposable if: $G = G_1 \times G_2 \Rightarrow \exists i \ G_i = 1$.
We can generalize the notion of indecomposable from groups to inclusion of groups as ...