Posts Tagged ‘maximum order’

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


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 2k \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}.