Smallest symmetric group with subgroup Q

What is the smallest $n$ such that the quaternion group is a subgroup of $S_n$?

• Interesting question. My tiny contribution is that it's not $n=4$, because the subgroups of $S_4$ with order $8$ are all isomorphic to $D_8$ (the dihedral group of the square): see here and in fact, the same is true for $n=5$ since a subgroup of $S_5$ with order $8$ is still Sylow. – Bungo Dec 8 '15 at 0:59
• Since the order of $Q$ is 8, each element can be viewed as a permutation of the other elements when applied to the other elements. (Every group is isomorphic to a permutation group.) So $n$ is at most $8$. – Element118 Dec 8 '15 at 1:01
• One comment in mathoverflow.net/questions/60577/… says that $n=8$. – lhf Dec 8 '15 at 1:14
• – lhf Dec 8 '15 at 1:18

Equivalently, we want to know the smallest $n$ such that $G = Q_8$ acts faithfully on a set of size $n$. Any action $X$ of $G$ decomposes as a disjoint union of transitive actions
$$X \cong \sum_i G/H_i.$$
Now, $G$ has the strange property that all of its subgroups are normal, so the kernel of the action of $G$ on $G/H$ is $H$. The action of $G$ on $X$ therefore has kernel $\cap_i H_i$, so the game here is to find subgroups of $G$ whose intersection is trivial such that the sum of their indices in $G$ is minimal.
$G$ has another strange property, which is that all of its nontrivial subgroups contain its center $\pm 1$. Hence the intersection $\cap_i H_i$ can't be trivial unless some $H_i = 1$. This gives $n = 8$.