## Maximum order of abelian subgroups in a symmetric group

Posted: April 21, 2012 in Elementary Algebra; Problems & Solutions, Groups and Fields
Tags: , ,

For any set $X,$ we denote by ${\rm{Sym}}(X)$ the group of bijective maps from $X$ to $X.$

Problem. Let $\alpha : \mathbb{N} \longrightarrow [1, \infty)$ be any map which satisfies the following two conditions: $\alpha(p) \geq p$ and $\alpha(p+q) \geq \alpha(p) \alpha(q)$ for all $p,q \in \mathbb{N}.$ Let $X$ be a set with $|X|=n.$ Prove that if $G$ is an abelian subgroup of ${\rm{Sym}}(X),$ then $|G| \leq \alpha(n).$

Solution.  The proof is by induction on $n.$ If $n=1,$ then $|G|=1 \leq \alpha(1).$ Let $X$ be a set with $|X|= n \geq 2$ and suppose that the claim is true for any set of size $< n.$ Let $G$ be an abelian subgroup of ${\rm{Sym}}(X).$ Clearly $gx=g(x), \ g \in G, x \in X,$ defines an action of $G$ on $X.$ Let $X_1, \ldots , X_k$ be the orbits corresponding to this action and consider two cases.

Case 1. $k=1$: Fix an element $x_1 \in X.$ Then $X=X_1=Gx_1.$ Suppose that $g_1x_1=x_1$ for some $g_1 \in G$ and let $x \in X.$ Then $x=gx_1$ for some $g \in G.$ Thus, since $G$ is abelian, we have

$x=gx_1=gg_1x_1=g_1gx_1=g_1x.$

Hence $g_1x=x$ for all $x \in X$ and thus $g_1=1.$ So the stabilizer of $x_1$ is trivial and therefore, by the orbit-stabilizer theorem, $|G|=|X|=n \leq \alpha(n).$

Case 2$k \geq 2$: Let $|X_i|=n_i, \ i=1,2, \ldots, k.$ Clearly $\sum_{i=1}^k n_i=n$ and, since $k \geq 2,$ we have $n_i < n$ for all $i.$ For every $g \in G$ and $1 \leq i \leq k$ let $g_i=g|_{X_i},$ the restriction of $g$ to $X_i,$ and put

$G_i=\{g_i: \ g \in G\}.$

Then $g_i \in {\rm{Sym}}(X_i)$ and $G_i$ is an abelian subgroup of ${\rm{Sym}}(X_i).$ Thus, by the induction hypothesis

$|G_i| \leq \alpha(n_i),$

for all $i.$ Now, define $\varphi : G \longrightarrow \bigoplus_{i=1}^k G_i$ by $\varphi(g)=(g_1, g_2, \ldots , g_k)$ for all $g \in G.$ It is obvious that $\varphi$ is one-to-one and so

$|G| \leq |\bigoplus_{i=1}^k G_i|=\prod_{i=1}^k |G_i| \leq \prod_{i=1}^k \alpha(n_i) \leq \alpha(\sum_{i=1}^k n_i)=\alpha(n). \ \Box$

Remark. The map $\alpha: \mathbb{N} \longrightarrow [1, \infty)$ defined by $\alpha(p)=3^{p/3},$ for all $p \in \mathbb{N},$ satisfies both conditions in the above Problem. So if $|X|=n$ and if $G$ is an abelian subgroup of ${\rm{Sym}}(X),$ then $|G| \leq 3^{n/3}.$