# Questions tagged [permutation-groups]

The permutation-groups tag has no usage guidance.

**7**

votes

**0**answers

83 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$ ...

**11**

votes

**1**answer

165 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
...

**4**

votes

**1**answer

209 views

### Number of permutations that are products of disjoint cycles of distinct length

What is the number of permutations $\pi\in S_n$ that are products of disjoint cycles of distinct length? What is the number of permutations that are products of disjoint cycles such that no more than $...

**1**

vote

**0**answers

82 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 ...

**6**

votes

**1**answer

118 views

### Enlarging a subdegree-finite “almost transitive” permutation group to a transitive one? (follow-up)

Consider a permutation group $G$ acting on an infinite set $X$. Assume $G$ has finitely many orbits, and every point stabiliser $G_x$ has finite orbits.
Can we always find a permutation $\tau\in\...

**3**

votes

**1**answer

88 views

### Enlarging a subdegree-finite “almost transitive” permutation group to a transitive one?

Consider a permutation group $G$ acting on an infinite set $X$. Assume $G$ has finitely many orbits, and every point stabiliser $G_x$ has finite orbits. Now consider a permutation $\tau\in\...

**12**

votes

**0**answers

271 views

### Escaping from a centralizer

Let $G = Sym(n)$, $n$ even. Let $H<G$ be the stabilizer of the partition $\{\{1,2\},\{3,4\},\dotsc,\{n-1,n\}\}$, or, what is the same, the centralizer of $(1\;2) \dotsc (n-1\; n)$.
By Stirling's ...

**1**

vote

**1**answer

196 views

### A permutation with reflection property

Consider permutations $\pi$ of the set $\{1,\dots,n\}$ having the symmetry property $\pi \pi^* \pi = \pi^*$, where $\pi^*$ is the "reflection" $k \mapsto n+1-k$. Are there references or other ...

**8**

votes

**1**answer

164 views

### Is $\beta\mathbb N$ a unique compactification with the smallest possible permutation group?

For a compactification $c\mathbb N$ of $\mathbb N$ let $\mathcal H(c\mathbb N,\mathbb N)$ be the group of homeomorphisms $h:c\mathbb N\to c\mathbb N$ such that $h(x)=x$ for all $x\in c\mathbb N\...

**7**

votes

**1**answer

392 views

### Linear permutations commuting with $x\rightarrow x^{-1}$

Let $F = \operatorname{GF}(2^n)$ be a finite field. Define a permutation $\phi:F \rightarrow F$ by the formula
$$
\phi(x) = x^{-1}, \ x\neq 0; \ \phi(0) =0.
$$
We say that a permutations $\psi$ of $F$ ...

**8**

votes

**1**answer

149 views

### sum of character product over derangements

It is widely known that
$$ \frac{1}{n!}\sum_{\pi\in S_n}\chi_\lambda(\pi)\chi_\mu(\pi)=\delta_{\lambda,\mu},$$
where $S_n$ is the permutation group and $\chi$ are its irreducible characters.
In ...

**0**

votes

**0**answers

29 views

### What is an example of a constructive encoding of binary strings modulo an arbitrary permutation group $G$?

Given a group $G \leq S_n$ we can construct by the axiom of choice a function $f : \{0, 1\}^n \rightarrow \{0, 1\}^{ceil(log_2 |\{0, 1\}^n/G|)}$ such that for any orbit $O$ of binary strings under $G$,...

**3**

votes

**2**answers

179 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 ...

**0**

votes

**1**answer

59 views

### Sequence Generation with Combinations and Permutations

I am trying to generate a set of genetic sequences with conditions. The problem uses a base 4 numerical notation:
nucleotides = ['A','C','G','T']
From this, I'd ...

**2**

votes

**0**answers

73 views

### First appearance of “structure tree”?

Let $G$ be a transitive permutation group acting on a set $\Omega$. A structure tree $T$ for $(G,\Omega)$ is defined as follows: if $G$ is primitive, then it consists of a root node connected by edges ...

**4**

votes

**1**answer

154 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 ...

**1**

vote

**1**answer

72 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 ...

**1**

vote

**2**answers

121 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 ...

**19**

votes

**3**answers

652 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 ...

**2**

votes

**0**answers

50 views

### What are the transitive extensions of finite representations of cyclic groups?

This question is a generalisation of this one. Let $H$ be a finite, transitive permutation group of degree $n$. If the point stabiliser subgroup $H_n$ of degree $n-1$ is some faithful permutation ...

**14**

votes

**1**answer

409 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 ...

**1**

vote

**0**answers

103 views

### A question about permutation matrices

This question is trying to abstract out in a self-contained way the point that is probably being made in page 6 of this paper, https://arxiv.org/pdf/1604.03544.pdf and why Theorem 4.1 there works.
...

**10**

votes

**2**answers

509 views

### How do I know if an irreducible representation is a permutation representation?

I have a vague question, a less vague question and a lot of vaguer questions about permutation representations of a finite group $G$.
Vague question. Recall that if $G$ acts on a finite set $X$, we ...

**1**

vote

**0**answers

166 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 ...

**7**

votes

**0**answers

128 views

### Connection between Gauss's lemma and Zolotarev's lemma

So I was reflecting on the relationship between Gauss's Lemma and Zolotarev's Lemma in proofs of quadratic reciprocity:
GL: $(a/p) = -1^n$, where $n$ is the number of least positive residues of $ax$ ...

**1**

vote

**0**answers

80 views

### graphs with semiregular automorphisms

I need some "well-known" non-regular finite graphs (at least two vertices have different valency) whose automorphism groups contain a non-trivial subgroup that acts on the vertices semi-regularly (i....

**1**

vote

**1**answer

174 views

### Automorphism group of a graph

Suppose $\Gamma$ is a simple graph and $G=\mathrm{Aut}(\Gamma)$ is the automorphism group of $\Gamma$. If $G$ stabilizes a subgraph $\Gamma_1$,, and $G_0$ is the point-wise stabiliser of the set $V(\...

**7**

votes

**2**answers

335 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 ...

**11**

votes

**1**answer

349 views

### Outer automorphism action on representations of $S_6$

Let $S_6$ be the symmetric group on 6 letters and let $\alpha \colon S_6 \to S_6$ be an outer automorphism (note that $S_6$ is the only permutation group that has an outer automorphism and that $\...

**13**

votes

**1**answer

395 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).
...

**2**

votes

**0**answers

85 views

### What is the meaning of a linked group action?

Some definitions and Notations
Group Action see this link.
$G$-invariant partition $B_i$ means $\forall \sigma \in G, B_i^{\sigma} = B_i$.
Minimal block system see page no - 30
Let $V$ be a $k$-...

**0**

votes

**1**answer

104 views

### number of orbits of a proper subgroup

Let $G$ be a permutation group that acts on (say) $X=\{1,2,..,n\}$, and $H$ be a proper subgroup of $G$. Can one say anything precise about when the number of orbits of $H$ on $X$ will be equal to ...

**5**

votes

**1**answer

106 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 ...

**7**

votes

**2**answers

401 views

### sum-sets in a finite field

Let $\mathbb{F}_p$ be a finite field, $A=\{a_1,\dots,a_k\}\subset\mathbb{F}_p^*$ a $k$-element set, for $k<p$. $\mathfrak{S}_k=$permutation gp.
Question. Is it true there is always a $\pi\in\...

**2**

votes

**1**answer

128 views

### Endomorphism of the symmetric group of the set of positive integers via action on the prime numbers

For a positive integer $n$, let $p_n$ denote the $n$-th prime number.
Further let $f: {\rm Sym}(\mathbb{N}) \rightarrow {\rm Sym}(\mathbb{N})$
be the monomorphism which maps a permutation $\sigma$ to ...

**8**

votes

**2**answers

490 views

### Regular elementary abelian subgroups of primitive permutation groups

A finite group $B$ is said to be a B-group if every primitive permutation group having a regular (transitive) subgroup isomorphic to B is $2$-transitive.
Schur proved that a cyclic group of ...

**3**

votes

**1**answer

154 views

### Maximal subgroups of a generalized symmetric group

Let $G$ be the wreath product $C_m\wr S_n$, where $C_m$ is the cyclic group of order $m$ and $S_n$ is the symmetric group on $n$ letters. I would like to understand the maximal subgroups of $G$ up to ...

**2**

votes

**1**answer

151 views

### Permutation groups: is there a term for an arbitrarily-permuted subset of points?

Let $G$ be a permutation group on a set $X$ of points. How do we call a subset $S\subseteq X$ such that, for each permutation $\pi \in \mathrm{Sym}(S)$ there exists $g \in G$ acting like $\pi$ if ...

**10**

votes

**1**answer

375 views

### Eliminating constant in Rado graph

Let $R$ denote the Rado graph, and let $c$ be a fixed vertex.
Question 1. Is the structure obtained by extending $R$ by the constant $c$ interpretable in $R$ without parameters?
By interpretable I ...

**1**

vote

**0**answers

46 views

### Set of vectors closed under restricted permutation operations

Let $V=\{v_1,\cdots v_k\}$ a set of non zero different norm one vectors in $R^d$, $k>2$. I am trying to demonstrate that if $Q=\{P_i\in R^{k\times k},i=1,\cdots,k\}$ is a set of permutations such ...

**2**

votes

**1**answer

267 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$...

**6**

votes

**6**answers

611 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 ...

**2**

votes

**1**answer

446 views

### 2-closure of a permutation group

Let $G$ be a group acting on a set $\Omega$ faithfully. Then 2-closure of $G$ denoted by
$G^{(2)}$ is the largest subgroup of the symmetric group of $\Omega$ with
the same orbits as $G$ on $\Omega\...

**2**

votes

**1**answer

123 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 ...

**4**

votes

**1**answer

228 views

### Hyperoctahedral group acting on a special permutation

Let $[n]=\{1,...,n\}$ and $[\hat n]=\{\hat 1,...,\hat n\}$. Realize the hyperoctahedral group $H_n$ as the centralizer of the permutation $(1\hat 1)\cdots (n \hat n)$. It has $2^n n!$ elements.
Let $...

**6**

votes

**1**answer

145 views

### A sum over characters of $S_{2n}$ and zonal spherical functions of $(S_{2n},H_n)$

The hyperoctahedral group $H_n$ can be seen as the centralizer of the permutation $(12)(34)\cdots (2n-1\,2n)$ in $S_{2n}$. It has $2^nn!$ elements.
The quantities $$ \omega_\lambda(\pi)=\frac{1}{2^...

**-1**

votes

**1**answer

134 views

### Can someone explain how Sims's algorithm works on a permutation group with a simple example? [closed]

Can someone explain how Sims's algorithm works on a permutation group with a simple example? The book "Permutation group algorithms" by Seress is a pretty hard read with a whole bunch of confusing ...

**12**

votes

**1**answer

406 views

### A sum over characters of the symmetric group

Let $C_\mu$ be the size of the conjugacy class in $S_n$ of permutations whose cycletype is the partition $\mu\vdash n$. Let $\chi$ be the characters of the irreducible representations of $S_n$.
Let $\...

**6**

votes

**1**answer

479 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 ...

**15**

votes

**2**answers

585 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 ...