11
$\begingroup$

Main question: How can we describe the double covers $(2\cdot\mathfrak{S}_n)^+$ and $(2\cdot\mathfrak{S}_n)^-$ of the symmetric group $\mathfrak{S}_n$ as permutation groups? (I.e., what sort of set with combinatorial structure do they act faithfully upon?)

I am not necessarily asking for the minimal permutation degree (I think this is an open problem; also see PS at bottom), but for some explicit combinatorial construction, reasonably uniform in $n$, that is hopefully reasonably small (perhaps merely exponential in $n$).

For a long time, I wrongly believed that one could form such a permutation representation of degree $2^{\lfloor n/2\rfloor}$ (or perhaps twice or four times that, or thereabouts) by taking an appropriate basis in the basic spin representation (and their negatives, and perhaps also times the imaginary unit), but I now realize that this does not work (at least, not as I thought it would). So I wonder if something else can be done.

The following question may is closely related to the above (trying to lift some $\mathfrak{S}_n$-set $X$ to a $(2\cdot \mathfrak{S}_n)$-set $\tilde X$ consisting of "signed" elements of $X$):

Alternate question: Given a set $X$ on which $\mathfrak{S}_n$ acts faithfully and transitively, with stabilizer $H$, is there some way to detect (merely by looking at $X$) whether $H$ lifts in $2\cdot \mathfrak{S}_n$ to a direct product $\{\pm 1\}\times H$, or equivalently (see below), whether the wreath product $1 \to \{\pm 1\}^X \to \{\pm 1\}\wr_X\mathfrak{S}_n \to \mathfrak{S}_n\to 1$ contains a non-split extension $1 \to \{\pm 1\} \to 2\cdot \mathfrak{S}_n \to \mathfrak{S}_n\to 1$?

Indeed, if $2\cdot \mathfrak{S}_n$ acts transitively on a set $\tilde X$, with stabilizer $H$, and the action does not factor through $\mathfrak{S}_n$, then $H$ intersects $\{\pm 1\}$ (center of $2\cdot\mathfrak{S}_n$) trivially, so maps isomorphically to a subgroup of $\mathfrak{S}_n$, which we can also call $H$, and the latter lifts to $2\cdot\mathfrak{S}_n$ as a direct product $\{\pm 1\}\times H$ (and we can see $\tilde X = (2\cdot\mathfrak{S}_n)/H$ as a double covering of $X = \mathfrak{S}_n/H$). But then, it follows from Derek Holt's paper "Embeddings of Group Extensions into Wreath Products" (Quarter. J. Math. Oxford 29 (1978) 463–468), theorem 2, that the wreath product contains our $2\cdot \mathfrak{S}_n$. Conversely, when this is the case, $2\cdot \mathfrak{S}_n$ acts faithfully and transitively (through the wreath product) on $\tilde X := \{\pm 1\}\times X$.

For example, if $H$ is generated by an $n$-cycle, and either $n$ is odd or we $n\equiv 2\pmod{4}$ if we are considering $(2\cdot\mathfrak{S}_n)^+$, we get a permutation action of degree $2(n-1)!$ on the set $\mathfrak{S}_n/H$ of cyclic orders with a sign added. But this isn't a great improvement over the regular action ($2n!$) and it's not very explicit, so I'm hoping we can do better.

PS: If my computations with Gap are correct, the minimal permutation representation for (Gap's choice) $(2\cdot\mathfrak{S}_n)^-$ is $16,48,80,240,240,480$ for $n=4,5,6,7,8,9$. This is not in the OEIS, I wonder if it's worth adding.

PPS: The corresponding values for $(2\cdot\mathfrak{S}_n)^+$ are $8,40,80,240,480,480$ (also not in the OEIS), so apparently they're not the same. (The trick I found to represent $(2\cdot\mathfrak{S}_n)^+$ under Gap is to multiply by a fourth root of unity the generators of $(2\cdot\mathfrak{S}_n)^-$ that lift an odd permutation.)

$\endgroup$
  • 2
    $\begingroup$ A good place to start might be to take a maximal odd order subgroup $X$ of $S_{n}$ and notice that this lifts to a subgroup $X \times Z$ of the extension of $S_{n}$ by $Z.$ This is one explanation for the first two minimal degrees in your list. $\endgroup$ – Geoff Robinson Jun 5 '18 at 16:41
  • $\begingroup$ @GeoffRobinson Indeed, this is already a progress compared to my $n$-cycle approach. Incidentally, searching the OEIS for the size of the largest odd order subgroup of $\mathfrak{S}_n$ returns the same first $10$ values as A000198, the size of the largest automorphism group of a tournament on $n$ vertices: I can see why a tournament defines an odd order subgroup, but not why the largest odd order subgroup would always be defined in such a way. $\endgroup$ – Gro-Tsen Jun 5 '18 at 21:01
  • $\begingroup$ I'm not sure about the link with tournaments but I think that every odd order subgroup of $S_{n}$ has order at most $3^{\frac{n-1}{2}}$ (a theorem of R. Gow), and the upper bound can probably only be attained when $n$ is a power of $3$ (it is indeed attained by a Sylow $3$-subgroup of $S_{n}$ when $n$ is a power of $3$). $\endgroup$ – Geoff Robinson Jun 6 '18 at 10:41
  • $\begingroup$ Could you explain what goes wrong with the spin representations? Does not the double cover of the symmetric group embed into the inverse image of permutation matrices in $Pin$? $\endgroup$ – მამუკა ჯიბლაძე Jun 6 '18 at 20:51
  • 1
    $\begingroup$ @მამუკაჯიბლაძე The spin representation works fine as a linear representation, but permutation matrices don't act on spinors like permutation matrices, i.e., the basis elements get linearly mixed in various ways and we don't get a permutation representation. $\endgroup$ – Gro-Tsen Jun 6 '18 at 22:34
8
$\begingroup$

I hope you are correct that minimal degree is an open question, as I am currently working on the related question of minimal degree for $2\cdot A_n$, but as this embeds into $(2\cdot S_n)^\pm$ with index $2$ I can give you a permutation representation which I believe to have degree at most $4$ times the minimal degree (for large enough $n$).

For a particularly good permutation representation assume $n$ is even and take the natural embedding $A_\frac{n}{2}\times A_\frac{n}{2}\hookrightarrow S_n$ or $A_\frac{n}{2}\times A_\frac{n}{2}\hookrightarrow S_{n+1}$ (to deal with odd case) and let $H$ be the subdirect product of $A_\frac{n}{2}\times A_\frac{n}{2}$ consisting of all pairs $(\sigma,\sigma)$ with $\sigma\in A_\frac{n}{2}$. The preimage of $H$ is $S_n$, or $S_{n+1}$ is isomorphic to $C_2\times H$. Hence we may identify $H$ as a subgroup of $2\cdot S_n$ or $2\cdot S_{n+1}$. The action of $G$ on the cosets of $H$ is faithful of degree $4n!/\frac{n}{2}!$ or $4(n+1)!/\frac{n}{2}!$.

It's not a particularly nice combinatorial structure (or at least I can't identify it as one), but it's what I've used to construct $2\cdot A_n$ as a permutation group in MAGMA.

Explanation:

As the socle $Z$ of $(2\cdot S_n)^\pm$ is a simple group, it has a minimal permutation representation which is transitive and is therefore the coset action of $(2\cdot S_n)^\pm$ on one of its subgroups. In fact, one can show that any minimal permutation representation of $(2\cdot S_n)^\pm$ is given by the coset action of $(2\cdot S_n)^\pm$ on one of its largest core-free subgroups, where a subgroup is core-free if it contains no normal subgroup of $(2\cdot S_n)^\pm$. In this case a subgroup $H$ of $(2\cdot S_n)^\pm$ is core-free if and only if it intersects $Z$ trivially. It can therefore be identified with it's image in $S_n$.

The choice of $H$ I've given is a particularly good one, though when $n$ is divisible by $8$ you may take $H\times C_2$ where $C_2$ 'swaps' the two copies of $A_n$.

It's a bit of work, but you can show $H$ is core-free using the finite presentation of $2\cdot S_n$. The main restriction is that whenever an element of order $2$ appears in $H$ it has to be a product of a multiple of $4$ transpositions. Hence two copies of $A_n$. Anything significantly larger than $A_\frac{n}{2}$ will end up having an element of order $2$ which does not satisfy this, so you really can't get much better than this.

$\endgroup$
  • $\begingroup$ This has the benefit of being explicit, and reasonably easy to visualize. However, unless I misunderstood something, it can't be minimal (I didn't care about that, but apparently you do): your construction gives a permutation representation of $2\cdot\mathfrak{S}_8$ or $2\cdot\mathfrak{A}_8$ of degree $6720$ or $3360$ or something, but the minimal degree in this case is $240$. $\endgroup$ – Gro-Tsen Jun 5 '18 at 22:56
  • $\begingroup$ Yes, it will only be minimal for large $n$. In the small cases there are some other possible representations, but they don't work as $n$ gets large. The reasoning I've found for this is to do with primitive groups growing to slowly if they're not alternating. I haven't got a precise value for when my representation is better but my guess is at around $n=30$. In any case I think it's a good standard. I'd like to see more interesting or intuitive representations of similar degree that work for all $n$ (I just happen to have been looking at minimality anyway) $\endgroup$ – Robert Chamberlain Jun 5 '18 at 23:29
  • $\begingroup$ I think I have a proof of your statement that the "diagonal" $\mathfrak{A}_{n/2}$ splits $2\cdot\mathfrak{A}_n \to \mathfrak{A}_n$, without using a presentation: this follows from the same statement for the diagonal (compact Lie group) $SO_{n/2}$ for $\mathit{Spin}_n\to SO_n$. But it is easily checked by connexity that when $p,q\geq 2$, the inverse image of the obvious $SO_p\times SO_q \to SO_{p+q}$ by $\mathit{Spin}_{p+q} \to SO_{p+q}$ is $(\mathit{Spin}_p\times\mathit{Spin}_q)/\langle(-1,-1)\rangle$, so for $p=q=n/2$ the diagonal is just $SO_n$. $\endgroup$ – Gro-Tsen Jun 6 '18 at 0:57
  • 1
    $\begingroup$ I conjecture that the permutation representation of $2.A_n$ described here by Robert is of minimal degree for $n \ge 28$. We can describe the minimal degree representations for $n \le 27$, and for $n=27$, $2.A_n$ has smallest index core-free subgroup ${\rm P \Gamma L}(2,8) \wr C_3$. $\endgroup$ – Derek Holt Jun 6 '18 at 7:47
  • $\begingroup$ @DerekHolt If you are able to compute the minimal permutation degrees of both groups for as many as $27$ values (do your values match mine?), I think it would be worth submitting the sequences to the OEIS. $\endgroup$ – Gro-Tsen Jun 6 '18 at 19:57
5
$\begingroup$

According to my calculations, the minimal permutation degrees of $2.A_n$ for $n=5,\ldots, 24$ are as follows. In each case $H$ is a core-free subgroup of $2.A_n$ of largest order. The minimal permutation degree of both versions of $2.S_n$ is at most twice this amount, and I think in each case it is exactly twice it, but I haven't tried to check that. I have only gone up to $n=24$ because that is as far as I have got with exact computations (mainly in Magma). I may be able to do a couple more values of $n$ but I would need to think harder to get much further.

G    H                           |H|             |G:H|
2A5  5                           5               24
2A6  3^2                         9               80
2A7  7.3                         21              240
2A8  L27 or 2^3.7.3              168             240
2A9  L28.3                       1512            240
2A10 L28.3                       1512            2400
2A11 M11                         7920            5040
2A12 M11                         7920            60480
2A13 M11                         7920            786240
2A14 M11x3                       23760           3669120
2A15 M11x3                       23760           55036800
2A16 L27^2.2 or (2^3.7^3)^2.2    56448           370656000
2A17 (L27 or 2^3.7.3) x L28.3    254016          1400256000
2A18 (L28.3)^2                   2286144         2800512000
2A19 (L28.3)^2                   2286144         53209728000
2A20 M11 x L28.3                 11975040        203164416000
2A21 M11 x L28.3                 11975040        4266452736000
2A22 M11^2                       62726400        17919101491200
2A23 M11^2                       62726400        412139334297600
2A24 S12                         479001600       1295295050649600
$\endgroup$
  • 1
    $\begingroup$ Is it because Magma is incredibly more powerful than Gap or simply because I don't know how to use the latter well enough? I can construct $2\cdot 𝔄_{10}$ under Gap (as a matrix group), but I pretty much can't do anything with it without running out of memory or patience, certainly not list its subgroups, so going up to $24$ seems incredible. And how does Magma represent elements of $2\cdot 𝔄_n$ anyway? Permutations are too big (that's the whole point) and even $2048×2048$ matrices seem a bit large… $\endgroup$ – Gro-Tsen Jun 6 '18 at 23:03
  • 2
    $\begingroup$ I m using the $\mathtt{LowIndexSubgroups}$ command in Magma to find subgroups of $A_n$ of bounded index and then looking for subgroups that contains no involutions in which the number of transpositions is $2$ mod $4$. In all examples so far these have turned out to be core-free subgroups of $2.A_n$. $\endgroup$ – Derek Holt Jun 7 '18 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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