The following came up in a problem on reconstruction of digraphs. I determined enough about the answer to satisfy the application completely, but still I am curious to know what the complete solution is. My group theory is weak, so apologies if this is too simple.

Let $T$ be a full binary tree with depth $k$. Call its levels $L_0,\ldots,L_k$. Here is the case $k=4$:

    tree with 4 levels  (source)

The number of leaves is $n=2^k$.

Let $A$ be the full automorphism group of $T$ and let $f$ be its (faithful) action on the leaves of the tree, i.e. on $L_k$. Obviously $f(A)$ is an iterated wreath product of $\mathbb{Z}_2$ with itself and has order $2^{n-1}$. It is, indeed, the Sylow 2-subgroup of $S_n$.

The problem is: what are the subgroups of $f(A)$ of index 2?

Here is what I think the answer is. Let $X$ be a union of levels of $T$, including at least one level other than $L_0$. Let $P$ be the set of all $f(\gamma)$ such that $\gamma\in A$ and the action of $\gamma$ on $X$ is an even permutation. Then $P$ is a subgroup of the desired index. I'm guessing there are no others...


You can easily count the number of maximal subgroups of $W(k)$, the $k$-fold iterated wreath product of $\mathbb{Z}_{2},$ by calculating the index of the Frattini subgroup. You can inductively prove that the number of generators is $k,$ which is clear for $k =1,2.$

To proceed, note that $W(k) = W(k-1) \wr \mathbb{Z}_{2}.$ Factor out the Frattini subgroup of the base group, and by induction, you are left with $E(k-1) \wr \mathbb{Z}_{2}$, where $E(k-1)$ is elementary Abelian of order $2^{k-1}.$ If $x$ is an element of order $2$ outside the new base group, then $[E(k-1) \times E(k-1),x]$ has order $2^{k-1},$ so that the largest elementary Abelian factor group of the original wreath product does have order $2^{k},$ as claimed.

Hence the group $W(k)$ has $2^{k}-1$ maximal subgroups, since there is a bijection between maximal subgroups of $W(k)$ and maximal subgroups of $W(k)/\Phi(W(k)).$ 

  • $\begingroup$ That's great. Since the subgroups I identified are all distinct (ignoring whether $L_0\subseteq X$) and there are exactly $2^k-1$ of them, your proof establishes that my wild guess was correct (for once). Thanks! $\endgroup$ – Brendan McKay Sep 2 '12 at 11:41
  • $\begingroup$ And it thereby establishes that the Frattini subgroup is that which has even action on every level. $\endgroup$ – Brendan McKay Sep 2 '12 at 11:54
  • $\begingroup$ @brendan: Good- I hadn't enumerated your subgroups, but was expecting that you would have $\endgroup$ – Geoff Robinson Sep 2 '12 at 13:40
  • $\begingroup$ Regarding the answer, how do you find the Frattini subgroup of the base group? And what do you do for the induction? I am trying to solve a similar problem and knowing this would greatly help. Thanks. $\endgroup$ – Trevor Dec 3 '17 at 11:58
  • $\begingroup$ The fact that $W(k)$ has $2^{k}-1$ maximal subgroups is equivalent to saying that the Frattini subgroup of $W(k)$ has index $2^{k}$, which is what we are trying to establish by induction. Since this is clear for $k =1,2$, as noted, we may assume by induction that $W(k-1)$ has Frattini factor of index $2^{k-1}$, as used in the above proof. $\endgroup$ – Geoff Robinson Dec 3 '17 at 14:02

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.