All Questions
62 questions
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
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
2
votes
0
answers
101
views
Are the alternating pentultimate and the $2$-alternating pentultimate isomorphic?
Consider a physical puzzle which is in the shape of a dodecahedron where the pieces that move are the face centers and you can slice it through a plane parallel to two opposite faces going through the ...
- 31
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
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
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
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
0
votes
1
answer
213
views
A particular permutation on $\mathbb{Z}_n$
Let us consider $\mathbb{Z}_N=\{0,1,\cdots N-1\}$.
Does there exist any permutation $\sigma$ on $\mathbb{Z}_N$ satisfying :
$$\exists p,q\in\mathbb{N}, ~~p,q\neq0 (mod~N) ~~\forall i,j\in \mathbb{Z}...
- 4,058
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
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
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
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
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
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
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$ ...
1
vote
2
answers
1k
views
Generators for permutation groups
Consider (e.g.) the full permutation group $G=S_6$. A valid set of generators and equations for $G$ is $r^6=m^2=(rm)^5=1$. I say this system has width $3$ (because there are $3$ equations), length $10$...
- 4,829
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
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
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
1
vote
0
answers
90
views
What is an upper limit of relative size of conjugacy class of the transitive finite group?
What is
$$ \limsup_{n\to\infty} \sup_{\deg(G)=n} \left( \frac{\max_{x\in G} \left|\operatorname{conj}(x)\right|}{\operatorname{ord}(G)}\right),$$
$G$ transitive permutation group?
And what are the ...
- 119
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
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
1
vote
1
answer
80
views
Complexity to decide for permutation group if every element fixed at most $k$ points
I want to consider the following problem, which generalises the decision problem to decide if a given finite permutation group is a Frobenius group:
Given a finite permutation group in terms of its ...
- 798
1
vote
2
answers
207
views
Complexity of decision problem to decide if permutation group is $k$-transitive
Given a finite permutation group $G$ (a subgroup of the symmetric group on a finite set) in terms of its generators, what is known about the decision problem of deciding if $G$ is $k$-transitive for a ...
- 798
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
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
1
vote
0
answers
242
views
Counting elements having a given cycle structure in maximal subgroups of a generalized symmetric group
Let $G$ be the wreath product $C_7\wr S_{18}$, where $C_7$ is the cyclic group of order 7 and $S_{18}$ is the symmetric group on 18 symbols. Consider $G$ to be embedded in the group $S_{126}=S_{7\cdot ...
- 1,021
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
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
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
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
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
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
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
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
1
vote
0
answers
179
views
Are the finite groups inclusions, almost all relatively cyclic?
Definition: An inclusion of finite groups $(A \subset B)$ is relatively cyclic if $\exists b \in B$ such that $\langle A,b \rangle = B$.
Definition: Two inclusions of finite groups are equivalent, $(...
0
votes
0
answers
142
views
Subgroups of powers of the alternating group on 5 elements
Definition: Let $G$ be a group, and let $H \leq G$ be a subgroup. We say that $H$ is big in $G$ if for every intermediate subgroup $H \leq L \leq G$ there exists some $x \in L$ such that $\langle H \...
- 11.3k
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
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
2
votes
0
answers
156
views
Special sets of involutions generating ${\rm S}_n$
For which positive integers $k$ and $r$ are there involutions $g_{n,i} \in {\rm S}_n$
$(n \in \mathbb{N}, \ i = 1, \dots, k)$ such that the following hold?:
for any $n$, the $g_{n,i}$ $(i = 1, \dots, ...
- 19.6k
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
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
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
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$...
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 ...
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: ...
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$.
...
9
votes
1
answer
578
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
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