3
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Dietrich Burde Feb 26 at 12:35
  • 3
    $\begingroup$ I suspect that it'll be the sum of the two (prime) factors of $2019$, i.e. $n = 3 + 673$. $\endgroup$ – Omnomnomnom Feb 26 at 12:35
  • $\begingroup$ This article gives a nice presentation of the non-abelian group of order $2019$. $\endgroup$ – Omnomnomnom Feb 26 at 12:45
  • 1
    $\begingroup$ 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). $\endgroup$ – WE Tutorial School Feb 26 at 13:08
  • 1
    $\begingroup$ You really shouldn't change a question after it has been correctly answered with a detailed solution. Why not ask a new question? $\endgroup$ – Derek Holt Feb 26 at 15:04
5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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 $\endgroup$ – Nicky Hekster Feb 26 at 17:02
7
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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". $\endgroup$ – Dietrich Burde Feb 26 at 13:16
  • 3
    $\begingroup$ "The reasoning is specific to the fact that $673$ is a product of $2$ distinct primes" - you mean $2019$, not $673$. $\endgroup$ – Dietrich Burde Feb 26 at 13:22
  • 1
    $\begingroup$ @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. $\endgroup$ – Ben Blum-Smith Feb 26 at 14:40
  • 1
    $\begingroup$ @DietrichBurde and Nicky Hekster, thank you for the edit. $\endgroup$ – Ben Blum-Smith Feb 26 at 14:41
  • 1
    $\begingroup$ No problem guys. Thanks. Both +1 from me! $\endgroup$ – Nicky Hekster Feb 26 at 16:16
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you tell more on the "sets of subgroups", please? How are they formed? In particular, what is "$t$"? $\endgroup$ – user750041 Feb 26 at 16:37
  • 1
    $\begingroup$ 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$.) $\endgroup$ – the_fox Feb 26 at 16:49
  • $\begingroup$ 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? $\endgroup$ – user750041 Feb 26 at 17:04
  • 1
    $\begingroup$ 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.) $\endgroup$ – the_fox Feb 26 at 18:06

Not the answer you're looking for? Browse other questions tagged or ask your own question.