2

0

So I'm reading a paper which assumes the following statement but I would like to be able to prove it.

Let $S=Sym(\mathbb{N})$ denote the symmetric group on the set of natural numbers.

If $\emptyset\subset A \subset \mathbb{N}$ then: $$S_{A}= \{ q \in S : aq\in A,\;\forall a\in A \}$$ is a maximal subgroup of S.

Here is how I would like to prove it. I select $f\in S\setminus S_{{A}}$. I want to show that $\langle S_{{A}}, f \rangle = S$, otherwise we have a contradiction. So i take $g\in S$. If $g\in S_{{A}}$ or $g=f$ we are done so assume $g\in S\setminus (S_{{A}}\cup f )$. How can I show that $g\in \langle S_{{A}}, f \rangle$? I had thought about doing something like finding $h\in\langle S_{{A}}, f \rangle$ such that $gh\in S_{{A}}$ so that $g=ghh^{-1}\in\langle S_{{A}}, f \rangle$ but I can't seem to get it to work. Can anyone help? EDIT: I mean A finite. Why is it enought to show the transposition in the answer is in the group generated by these two?

  • is $A$ finite as in the title of this question? Because then it suffices to show that the permutation $(x; y)$ with $x \in A$ and $y\in \mathbb N \setminus A$ for fixed $x$ and $y$ is a member of $\langle S_A, f \rangle$ – Alexander Thumm Mar 21 '11 at 13:53
  • I'm not so sure, but consider the action of $S$ on subsets of $\mathbb N$ of order $|A|$. If $|A|>1$ this action is at least 2-transitive, therefore it is primitive, therefore stabilizers are maximal subgroups. – Myself Mar 21 '11 at 14:11
  • 1
    If A is infinite, then the setwise-stabilizer of A is not maximal for the same reason that the setwise stabilizer of {1,2} is not maximal in Sym({1,2,3,4}); it is contained in a wreath product subgroup. – Jack Schmidt Mar 21 '11 at 14:14
  • @Jack Schmidt: you mean if $A$ and $\mathbb N\setminus A$ are both infinite, right? I agree with you then, even though it implies something is wrong with my reasoning above and I'm not sure what. – Myself Mar 21 '11 at 14:37
  • @Myself: yes. If there is a bijection between A and X-A, then the setwise-stabilizer of A in Sym(X) is properly contained in Sym(A) wr Sym(2). – Jack Schmidt Mar 21 '11 at 14:42
  • EDIT: I mean A finite. Why is it enought to show the transposition in the answer is in the group generated by these two? –  Mar 21 '11 at 15:20
  • This question was also asked simultaneously on MathOverflow http://mathoverflow.net/questions/59059/the-setwise-stabiliser-of-a-finite-set-is-maximal-in-symn. Please post a link when you're doing this! – Scott Morrison Mar 24 '11 at 03:21

2 Answers2

2

I will asume $A \subset \mathbb N$ is finite and nonempty. Let $f \in S$ with $f \not \in S_A$. Fix a point $a \in A$ with $b := f(a) \in \mathbb N \setminus A$. Let $b' \in \mathbb N \setminus A$ with $c := f^{-1}(b') \in \mathbb N \setminus A$, which exists beacause $A$ was asumed to be finite. Now $(a \; c) = f^{-1} \circ (b\; b') \circ f \in \langle S_A, f \rangle$. The rest should be easy.

edit: We now formalize the rest of the proof:

Let $g\in S$. Let $o_1, \dots, o_n$ be all the elements of $A$ for which $g(o_k)\in\mathbb N \setminus A$. Since $g$ is bijective, and therefore $\mathrm{card }g(A) = \mathrm{card }A$ there must be exactly $n$ distinct elements $i_1, \dots, i_n$ of $\mathbb N \setminus A$ with $g(i_k)\in A$. Now consider $(o_k\;i_k) = (o_k\;a)\circ(i_k\;c)\circ(a\;c)\circ(i_k\;c)\circ(o_k\;a) \in \langle S_A, f \rangle$ and observe that $ h(A) := g\circ (o_n\;i_n)\circ\dots \circ(o_1\;i_1) (A) = A$ and therefore $h\in S_A$. This shows $g\in \langle S_A, f \rangle$.

Alexander Thumm
  • 5,112
  • I thought, this should be clarified a little more. The idea is basically that objects of $S_A$ permute the elements of $A$ and those of $\mathbb N \setminus A$ freely, but cannot mix those two sets. Adding any other object $f$ of $S$ must therefore transport an element from $A$ to $\mathbb N \setminus A$. We can now use this "door" to transport a finite (because we only have finite composits) number of elements of $A$ to $\mathbb N \setminus A$ within $\langle S_A, f \rangle$. But $A$ was finite and therefore this is sufficient. – Alexander Thumm Mar 21 '11 at 15:20
  • there's an edit-button hidden beneath your answer, a bit to the left. – Myself Mar 21 '11 at 15:26
  • I still don't really understand why it is enough just to show that we can move one point of A outside. –  Mar 21 '11 at 15:34
0

The similar result is in fact true for the symmetric group $S=\mathrm{Sym}(\Omega)$ of any infinite set $\Omega$: if $A$ is a finite nonempty subset of $\Omega,$ then the setwise stabilizer $S_{\{A\}}$ of $A$ is a maximal subgroup of $S.$ This fact is due to R.W.Ball and it is contained in the paper ``Subgroups of infinite symmetric group'' by Macpherson and Neumann [MN].

According to the standard notation, given a subset $\Gamma$ of $\Omega,$ the setwise stabilizer of $\Gamma$ is denoted by $S_{\{\Gamma\}}$ and the pointwise stabilizer of $\Gamma$ by $S_{(\Gamma)}.$ Also, it is convenient to write $\mathrm{Sym}(\Gamma)$ for the group of all permutations of $\Omega$ which fix $\Gamma$ setwise and fix $\Omega - \Gamma$ pointwise (and the latter condition clearly implies the former).

$\textbf{Lemma}$ ([MN, Lemma 2.1]). Let $\Gamma_1,\Gamma_2$ be infinite subsets of $\Omega$ satisfying $|\Gamma_1 \cap \Gamma_2| = |\Gamma_1 \cup \Gamma_2|.$ Then $$ \langle \mathrm{Sym}(\Gamma_1), \mathrm{Sym}(\Gamma_2) \rangle=\mathrm{Sym}(\Gamma_1 \cup \Gamma_2). $$ (if this result is unfamiliar it is certainly worth studying the rather short proof which actually is contained in another paper, namely ``Subgroups of small index in infinite symmetric groups'' by Dixon, Neumann, and Thomas).

Let a subgroup $G$ of $S$ strictly contain the setwise stabilizer $S_{\{A\}}$ of a finite nonempty subset $A$ of $\Omega.$ We claim that $G=S.$

We use induction on $|A|.$ Let then $A=\{a\},$ where $a \in\Omega.$ Suppose a permutation $g \in G$ takes the element $a$ to a different element $b \in \Omega.$ But then, by the lemma, $$ \begin{aligned} G &\geqslant \langle\, \mathrm{Sym}(\Omega - A), g\, \mathrm{Sym}(\Omega - A)\, g^{-1}\,\rangle \\ &= \langle\, \mathrm{Sym}(\Omega - A), \mathrm{Sym}(\Omega - gA)\, \rangle \\ &= \mathrm{Sym}(\, (\Omega - A) \cup (\Omega - gA)\,) \\ &= \mathrm{Sym}(\,\Omega - (A \cap gA)\,) \\ &= \mathrm{Sym}(\, \Omega - (\{a\} \cap \{b\})\,) \\ &= \mathrm{Sym}(\Omega)=S. \end{aligned} $$

Induction step: if an element $g \in G$ does not stabilize the set $A,$ that is, if $$ gA \ne A, $$ the set $$ B = A \cap gA $$ is of cardinality strictly less than $|A|.$ Arguing as before we see that $$ G \geqslant \langle\, \mathrm{Sym}(\Omega - A), g\, \mathrm{Sym}(\Omega - A)\, g^{-1}\,\rangle =\mathrm{Sym}(\, \Omega - (A \cap gA)\,)=\mathrm{Sym}(\,\Omega - B\,). $$ Now as $G$ contains the group $\mathrm{Sym}(A),$ $G$ contains its subgroup $\mathrm{Sym}(B),$ which implies that $$ G \geqslant S_{\{B\}}. $$ Since, however, $G = S_{\{B\}}$ is impossible due to $S_{\{B\}} \not\geqslant S_{\{A\}},$ we obtain that $G > S_{\{B\}},$ and hence $G=S$ by the induction hypothesis.

Olod
  • 1,840