All Questions
Tagged with gr.group-theory permutation-groups
139 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.8k
7
votes
1
answer
224
views
Generating set of permutation group such that generators do not "contain" other group elements
Let $(G, X)$ be a permutation group with domain $X$. Let $O=\{o_1,\dots,o_m\}$ be the set of orbits of $G$. I am interested in generating sets $S$ with the following property:
Let $g\in S$ be a ...
- 5,792
6
votes
0
answers
156
views
What are the possible symmetry groups of n-point constructions in the projective plane?
Let $k$ be an infinite field, perhaps take $k = \mathbb{C}$ if it simplifies matters.
I will be asking a question about $\mathbb{P}^2$ for definiteness and to simplify definitions/notations, but feel ...
- 32.4k
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
7
votes
1
answer
460
views
Does every transitive permutation group contain a permutation whose cycle lengths have a common divisor?
Let $H$ be a transitive subgroup of $\mathfrak{S}_n$, $n \geq 2$.
Using Jordan's lemma ($H$ is not a union of conjugate proper subgroups), we see that $H$ contains a permutation without fixed points.
...
- 413
1
vote
0
answers
94
views
cycle types of all words in a permutation group
I have been working with permutation groups. For a given $G\subset S_n$, what I have been computing depends only on the conjugacy class of $G$.
Say all permutation groups in this question are ...
- 2,287
5
votes
1
answer
282
views
Questions about algorithms for permutation groups
Let $G < S_n$ be a permutation group of degree $n$, $\mathcal{P(n)}$
denote the set of all partitions of $n$, and $c: G \rightarrow
\mathcal{P}(n)$, where $c(g)$ is the partition given by the ...
- 4,636
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,525
1
vote
0
answers
91
views
Totally imprimitive groups
Following [Neumann P.M., The lawlessness of groups of finitary permutation groups, Arch. Math. 55(6) 1990, 521-532], we define totally imprimitive groups in a more general form as follows:
Let $G$ be ...
- 69
2
votes
0
answers
115
views
Conjugacy classes of $P\Gamma L(2,q)$
$\DeclareMathOperator\PGaL{P\Gamma L}\DeclareMathOperator\GF{GF}$May I know whether there are any developments made on the conjugacy classes of $\PGaL(2,q)$ where $q$ is a prime power but not a prime? ...
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
3
votes
0
answers
181
views
Centralizer of each element of a subgroup contained in the normalizer of the subgroup
Let $G \leq \operatorname{Sym}(\Omega)$ be a permutational group. A base for $G$ is a sequence of elements of $\Omega$ whose pointwise stabilizer is the identity. A base is called irredundant if no ...
8
votes
1
answer
209
views
Asymptotic number of permutation representations of a given group
Let $G$ be a finitely generated group.
I am trying to count the number of permutation representations on $n$ elements, i.e. homomorphisms from $G$ to the symmetric group $S_n$.
Equivalently this is ...
- 974
5
votes
1
answer
252
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
369
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
2
votes
1
answer
267
views
On Sylow subgroups of finitary symmetric groups
$\DeclareMathOperator\FSym{FSym}$Let $p$ be a prime and $S$ be a transitive Sylow $p$-subgroup of $\FSym(\mathbb{N})$, the finitary symmetric group of the set of all natural numbers.
Question: Is $S$ ...
- 379
2
votes
1
answer
196
views
Isomorphic Sylow p-subgroups of FSym$(\mathbb{N})$
Let FSym$(\mathbb{N})$ denote the finitary symmetric group on the natural numbers. Are all Sylow p-subgroups of FSym$(\mathbb{N})$ isomorphic (maybe to the iterated wreath product $C_p\wr C_p\wr\dots$ ...
- 379
0
votes
1
answer
113
views
Sylow $p$-subgroups of FSym($\mathbb N$)
$\DeclareMathOperator\FSym{FSym}$Let $\FSym(\mathbb{N})$ denote the finitary symmetric group on the set of natural numbers. How many Sylow $p$-subgroups does $\FSym(\mathbb{N})$ have for any prime $p$?...
- 379
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
0
votes
1
answer
284
views
Given the index of two permutations, Is there a direct way to compute the index of their composition? [closed]
Suppose you are given two indexed permutations, (7 followed by 4, for instance)
What is the best way to go about finding their composition, given the indices themselves? I'd imagine that the answer ...
- 13
2
votes
0
answers
135
views
Permutation group with a nice lattice of block systems
Let $X$ be a finite set and $G$ be a transitive subgroup of the symmetric group on $X.$ Recall that a (complete) block system for this action is a partition of $X = B_1 \cup \cdots \cup B_k$ into ...
- 396
0
votes
0
answers
102
views
classification for some groups
Let $G$ be a finite group. Suppose that $G$ acts on a set, say $X$, transitively such that for every $x\in X$, $G_x^g=G_x$ or $G_x^g\cap G_x=\{1\}$. Could you please tell me if there is a ...
- 1
6
votes
1
answer
252
views
Is there a known classification of regular multiplicity-free permutation groups?
The question is in the title, but let me clarify the terminology. I consider a permutation group $\Sigma\subseteq\mathrm{Sym}(\Omega)$ on a finite set $\Omega$.
$\Sigma$ is regular if it acts ...
- 13.6k
2
votes
1
answer
129
views
Source for: a permutation group is multiplicity-free if and only if its 2-orbits define an association scheme
I have recently proven the following (at least, so I believe):
Theorem. Given a permutation group $\Sigma\subseteq\mathrm{Sym}(\Omega)$ on the set $\Omega:=\{1,...,n\}$, the following are equivalent:
...
- 13.6k
0
votes
0
answers
181
views
Request for a modern Reference for Frobenius' paper "Über die Charaktere der mehrfach transitiven Gruppen"
I'm interested in the paper of Jan Saxl "The Complex Characters of the Symmetric Groups that Remain Irreducible in Subgroups".
I have only (not yet enough!) standard background on the ...
- 1,013
3
votes
1
answer
206
views
Does the Hawaiian Earring Group embed into the permutation group of $\mathbb N$?
Recall that the Hawaiian earring group, $\mathbb G$, is the fundamental group of the Hawaiian Earing using the point at the origin. It can be understood more combinatorially as a subgroup of the ...
- 1,882
7
votes
1
answer
215
views
Automorphism group of a putative strongly regular graph
The smallest feasible parameters for which no strongly regular graph is known to exist are $(69,48,32,36)$, as per Brouwer's table. What is known on the automorphism group of such a graph?
- 221
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
6
votes
1
answer
287
views
Group action with unique word
This must be known or easy for some of you, but here goes:
Suppose $f_0,f_1:[n]\to [n]$ are invertible functions, where $[n]=\{0,\dots,n-1\}$ is a set of $n$ elements.
For a word $w=w_1\dots w_m\in\{...
- 24.8k
7
votes
0
answers
115
views
Extensions of oligomorphic groups
Recall that a permutation group $G\le\mathfrak{S}(\mathbb N)$ is oligomorphic if, for any positive integer $k$, the induced $G$-action on $k$-tuples of distinct elements of $\mathbb N$ has only ...
- 321
9
votes
2
answers
329
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
12
votes
0
answers
277
views
How many steps on $S_n$ are required to span $V\wedge V$, $V = K^n$?
Let $A$ be a set of generators of $G=S_n$; assume $e\in A$,
$A=A^{-1}$. Let $V = K^n$, $K$ a field. Consider the natural
action of $G$ on $V$ (namely, $g(e_i) = e_{g(i)}$) and on $W = V\wedge V$
(...
- 20.2k
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
237
views
Permutation groups generated by finitely many point stabilisers
Assume that $G\leq\operatorname{Sym}(X)$ is a permutation group generated by all its point stabilisers, i.e. $G=\langle G_x \mid x\in X\rangle$. There is no cardinality restriction on $X$. Furthermore,...
- 327
7
votes
1
answer
578
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
21
votes
1
answer
622
views
If $S_\mathbb N$ is partitioned into finitely many pieces, must one piece contain a "skew copy" of every countable group?
Suppose $G$ and $H$ are groups. $C \subseteq H$ is called a skew copy of $G$ in $H$ if $C = hK$ for some $h \in H$ and some subgroup $K$ of $H$ with $K \cong G$.
Question 1: Suppose the infinite ...
- 18.5k
6
votes
2
answers
384
views
Irreducible factors of primitive permutation group representation
Consider a primitive permutation group $\Gamma\subseteq\mathrm{Sym}(N)$ on the $n$-element set $N=\{1,...,n\}$, that is, $\Gamma$ does not preserve any non-trivial partition of $N$.
Consider the ...
- 13.6k
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$ ...
4
votes
1
answer
378
views
Is $(\mathbb{R},+)$ isomorphic to a subgroup of $S_\omega$?
Is $(\mathbb{R},+)$ isomorphic to a subgroup of $S_\omega$, the group of permutations of the set of non-negative integers $\omega$?
- 48.8k
9
votes
1
answer
460
views
Connections between linear representations and permutation representations
A finite group $\Gamma$ might be represented by a linear transformation
$$\rho : \Gamma\to\mathrm{GL}(\Bbb R^d),$$
or by permutations
$$\phi :\Gamma\to\mathrm{Sym}(n).$$
Of course, latter ones can ...
- 13.6k
3
votes
1
answer
158
views
Multiplication in $Z(\mathbb{C}S_n)$ [duplicate]
I am trying to multiply two generators of center $Z(\mathbb{C}[S_n])$ of ring algebra of symmetric group of $n$ elements. We know that these generators are given by sums of conjugacy classes in $S_n,$ ...
- 1,677
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,525
11
votes
1
answer
289
views
Permutation groups having a regular cyclic subgroup and a conjectured algebra of characters
Let $G$ be a transitive permutation group of degree $d$ having a cyclic regular subgroup $K = \langle k \rangle \cong C_d$. Let $\pi(g) = |\mathrm{Fix}(g)|$ be the permutation character of $G$ and let
...
- 11.2k