2

What is the minimal number $n$ such that symmetry group $S_n$ contains subgroup of order 2019? Is it the biggest factor of 2019, which is 673?

Edit: Sorry I missed a key property. The subgroup with order 2019 need to be a cyclic group.

Yuyi Zhang
  • 1,442
  • 3
    We can take a disjoint product of a $3$-cycle and a $673$-cycle in $S_{676}$ to obtain an element of order $2019$. But there may be a nonabelian subgroup of order $2019$ in a smaller symmetric group. So do you want to consider perhaps abelian subgroups? The general cas is considered to be hard, see this MO-post. – Dietrich Burde Feb 26 '20 at 12:35
  • 3
    I suspect that it'll be the sum of the two (prime) factors of $2019$, i.e. $n = 3 + 673$. – Ben Grossmann Feb 26 '20 at 12:35
  • This article gives a nice presentation of the non-abelian group of order $2019$. – Ben Grossmann Feb 26 '20 at 12:45
  • For this unique nonabelian group $G$ of order $2019$, what is the minimal $n$ such that $G$ embedds to $S_n$? See also this post. – Dietrich Burde Feb 26 '20 at 12:53
  • 1
    I think $n=673$ is enough. Consider $S_{673}$ as the permutation group of $\mathbb{Z}/673\mathbb{Z}$. Take $$a=(0;;1;;2;;\ldots;;672).$$ Suppose that the group $(\mathbb{Z}/673\mathbb{Z})^\times$ modulo the subgroup ${1,g,g^2}$ where $g=255$ consists of cosets ${0}$, ${x_1,gx_1,g^2x_1}$, ${x_2,gx_2,g^2x_2}$, $\ldots$, ${x_{224},gx_{224},g^2x_{224}}$. Let $$b=(x_1;;gx_1;;g^2x_1)(x_2;;gx_2;;g^2x_2)\cdots(x_{224};;gx_{224};;g^2x_{224}).$$ Then the subgroup of $S_{673}$ generated by $a$ and $b$ is a non-abelian group of order $3\cdot 673=2019$ (this is a guess). – Batominovski Feb 26 '20 at 13:08
  • If the group is nonabelian, the 3-Sylow subgroup cannot be normal (because otherwise the group would be abelian as the 673 Sylow is normal). So the action on the cosets of the 3-Sylow must be faithful. – ahulpke Feb 26 '20 at 13:53
  • 1
    You really shouldn't change a question after it has been correctly answered with a detailed solution. Why not ask a new question? – Derek Holt Feb 26 '20 at 15:04

3 Answers3

7

Yes, it is 673. It is not a general principle that you can use the biggest prime factor though. The reasoning is specific to the fact that 2019 is a product of 2 distinct primes and the bigger one is 1 mod the smaller one. In general, the smallest such $n$ has to be at least the biggest prime factor (for the same reason as below), but it can be more. Here's the argument:

The prime factorization of $2019$ is $3\times 673$, thus the desired subgroup has $pq$-order. The problem is find the smallest $n$ such that a group of order $pq$ embeds into $S_n$.

Without loss of generality let $p<q$. (So here, $p=3$ and $q=673$.) Up to isomorphism, there are 2 groups of order $pq$ if $q=1\operatorname{mod} p$ (which holds in this case, as $672$ is a multiple of $3$): there is a cyclic group of order 2019, and the semidirect product $C_q\rtimes C_p$ where $C_p$ acts nontrivially on $C_q$. (See here for proof and examples.) The latter nonabelian group is isomorphic to the group of permutations of the points of the finite field $\mathbb{F}_q$ that have the form

$$ x\mapsto ax+b,$$

where $a$ is a $p$th root of unity in $\mathbb{F}_q$, while $b$ is any element of $\mathbb{F}_q$ at all. (A way to see why the condition $q=1\operatorname{mod}p$ is necessary for this group to exist is that this is the circumstance under which $\mathbb{F}_q$ contains the $p$th roots of unity.)

This construction realizes the nonabelian group of order $2019$ as a subgroup of $S_{673}$.

There is no smaller $n$ such that either of the groups of order $2019$ embed in $S_n$, because if $n<673$, then $S_n$'s order does not have 673 as a factor, so it cannot have a subgroup of order divisible by 673.

To see that the biggest prime factor is not enough in general, the smallest $n$ such that a group of order $p^2$ ($p$ prime) embeds in $S_n$ is $2p$. (The group generated by a pair of disjoint $p$-cycles has the right order; and no smaller $n$ allows $|S_n|$ to be divisible by $p^2$.) If $p$ and $q$ are two primes that do not satisfy $q=1\operatorname{mod}p$, then the only group of order $pq$ is the cyclic group, and this does not embed in $S_n$ for $n\leq p+q$, as there is no permutation of order $pq$ smaller than a product of a disjoint $p$-cycle and $q$-cycle.

Addendum: I see that the question has been edited to require that the embedded subgroup of order 2019 be cyclic. Dietrich Burde has answered the question in this form, and the final paragraph in this answer also implicitly answers it.

Ben Blum-Smith
  • 20,766
  • 2
    This construction only works if the group is nonabelian. Is it clear that the cyclic group $C_{2019}$ embedds into $S_{673}$? If not, then not every group of order $2019$ embedds into $S_{673}$. Of course, the question above hasn't asked this, if I understood correctly. But still, perhaps the OP forgot to say "abelian". – Dietrich Burde Feb 26 '20 at 13:16
  • 3
    "The reasoning is specific to the fact that $673$ is a product of $2$ distinct primes" - you mean $2019$, not $673$. – Dietrich Burde Feb 26 '20 at 13:22
  • 1
    @DietrichBurde - I see an edit has been made to the original post. It originally just asked for the smallest $n$ such that $S_n$ contains a subgroup of the desired order, and the discussion in comments at that point had focused on the question about whether the nonabelian group of order 2019 could embed in $S_{673}$, so I answered the question as originally asked, making sure to resolve the question that had been the focus of the comments. Subsequent comments have provided the same example as in this answer, and an edit to the OP asks specifically for cyclic groups. I'll make an addendum. – Ben Blum-Smith Feb 26 '20 at 14:40
  • 1
    @DietrichBurde and Nicky Hekster, thank you for the edit. – Ben Blum-Smith Feb 26 '20 at 14:41
  • Ben, I didn't make an edit. Thanks should go to Nicky! – Dietrich Burde Feb 26 '20 at 14:42
  • @DietrichBurde, you called attention to the mistake and Nicky made the actual edit, I was thanking you both! – Ben Blum-Smith Feb 26 '20 at 14:46
  • 1
    No problem guys. Thanks. Both +1 from me! – Nicky Hekster Feb 26 '20 at 16:16
5

The smallest $n$ such that $S_n$ contains a cyclic group of order $\prod_{p\in \Bbb P} p^{k_p}$ is given by $\sum_{p\in \Bbb P}p^{k_p}$. Hence $n=3+673$ is the smallest $n$ such that $S_n$ contains a cyclic subgroup of order $2019=3\cdot 673$.

Any group of order $2019=pq$ is either cyclic or a semidirect product of $C_p$ and $C_q$. So we have a unique nonabelian group of order $2019$, whose minimal $n$ for an embedding to $S_n$ is given by $673$ itself, as explained in the answer above.

In general, asking about a minimal permutation representation for finite groups is difficult, and there are whole books on this subject, e.g., this one.

Dietrich Burde
  • 130,978
  • 2
    Considering your last remark, the seeding paper belongs to D. L. Johnson Minimal Permutation Representations of Finite Groups American Journal of Mathematics Vol. 93, No. 4 (Oct., 1971), pp. 857-866 – Nicky Hekster Feb 26 '20 at 17:02
2

For a finite group $G$, let $\mu(G)$ be the least positive integer $n$ such that $G$ is embedded as a subgroup of the symmetric group on $n$ points. In other words, $\mu(G)$ is the minimal permutation representation degree of $G$.

The general method to find $\mu(G)$ for a finite group $G$ is this: $\mu(G)$ is the minimum of $\sum_{i=1}^t |G:H_i|$ over all sets of subgroups $H_1, H_2, \ldots, H_t$ such that $\bigcap_{i=1}^t\mathrm{Core}_G(H_i) = 1$, which is equivalent to $\mathrm{Core}_G(K) = 1$, $K = \bigcap_{i=1}^tH_i$.

Figuring out what $\mu(G)$ is when $G$ is a finite abelian group of order $pq$, for distinct primes $p$, $q$, is now easy.

the_fox
  • 5,805
  • Could you tell more on the "sets of subgroups", please? How are they formed? In particular, what is "$t$"? –  Feb 26 '20 at 16:37
  • 1
    You consider arbitrary collections of subgroups, i.e. ${H_1, \ldots, H_t}$ ranges in the set of all subsets of subgroups of $G$, and you look for the minimum of the quantity $\sum_{i=1}^t |G:H_i|$ subject to the condition that $\bigcap_{i=1}^t\mathrm{Core}G(H_i) = 1$. Work out for yourself what that is when $G = C{pq}$, the cyclic subgroup of order $pq$ to see the formula in action. (The variable $t$ can be any natural number which is at least $1$ and at most $n$, where $n$ is the number of subgroups of $G$.) – the_fox Feb 26 '20 at 16:49
  • Clear now, I'll try. In the meantime, as even more basic test, I expect the algorithm to give $\mu(G)=|G|$ if $G=C_p$, is it? –  Feb 26 '20 at 17:04
  • 1
    Yes. In fact, $\mu(G) = |G|$ whenever $G$ is cyclic of prime-power order. The reason that this holds is that if $G=C_{p^a}$ for some $a \in \mathbb{N}$ and $H, K \leq G$ then either $H \leq K$ or $K \leq H$. (In other words, the lattice of subgroups of $G$ forms a chain.) – the_fox Feb 26 '20 at 18:06