Skip to main content
MathOverflow

Return to Question

Consistent TeX in title, while this is on the front page
Link
LSpice
LSpice
  • 12.9k
  • 4
  • 45
  • 69

Smallest n$n$ for which G$G$ embeds in $S_n$?

Edit: What do I want?
Source Link
Tim Dokchitser
Tim Dokchitser
  • 5.4k
  • 1
  • 34
  • 45

Question: Given a finite group $G$, how do I find the smallest $n$ for which $G$ embeds in $S_n$?

Equivalently, what is the smallest set $X$ on which $G$ acts faithfully by permutations? This looks like a basic question, but I seem not to be able to find answers or even this question in the literature. If this is known to be hard, is there at least a good strategy that would give a small (if not the smallest) $n$ for many groups?

Note: I do not care whether $G$ acts transitively on $X$, so for example for $G=C_6$ the answer is $n=5$ (mapping the generator to (123)(45)), not $n=6$ (regular action).

Edit: If this is not specific enough, is there a method that could find the smallest $n$ (or one close to the smallest one) for any group of size $\le 10^7$ in 5 seconds on some computer algebra system?

Question: Given a finite group $G$, how do I find the smallest $n$ for which $G$ embeds in $S_n$?

Equivalently, what is the smallest set $X$ on which $G$ acts faithfully by permutations? This looks like a basic question, but I seem not to be able to find answers or even this question in the literature. If this is known to be hard, is there at least a good strategy that would give a small (if not the smallest) $n$ for many groups?

Note: I do not care whether $G$ acts transitively on $X$, so for example for $G=C_6$ the answer is $n=5$ (mapping the generator to (123)(45)), not $n=6$ (regular action).

Question: Given a finite group $G$, how do I find the smallest $n$ for which $G$ embeds in $S_n$?

Equivalently, what is the smallest set $X$ on which $G$ acts faithfully by permutations? This looks like a basic question, but I seem not to be able to find answers or even this question in the literature. If this is known to be hard, is there at least a good strategy that would give a small (if not the smallest) $n$ for many groups?

Note: I do not care whether $G$ acts transitively on $X$, so for example for $G=C_6$ the answer is $n=5$ (mapping the generator to (123)(45)), not $n=6$ (regular action).

Edit: If this is not specific enough, is there a method that could find the smallest $n$ (or one close to the smallest one) for any group of size $\le 10^7$ in 5 seconds on some computer algebra system?

Source Link
Tim Dokchitser
Tim Dokchitser
  • 5.4k
  • 1
  • 34
  • 45

Smallest n for which G embeds in $S_n$?

Question: Given a finite group $G$, how do I find the smallest $n$ for which $G$ embeds in $S_n$?

Equivalently, what is the smallest set $X$ on which $G$ acts faithfully by permutations? This looks like a basic question, but I seem not to be able to find answers or even this question in the literature. If this is known to be hard, is there at least a good strategy that would give a small (if not the smallest) $n$ for many groups?

Note: I do not care whether $G$ acts transitively on $X$, so for example for $G=C_6$ the answer is $n=5$ (mapping the generator to (123)(45)), not $n=6$ (regular action).