MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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...

share|cite|improve this question
up vote 7 down vote accepted

You can easily count the number of maximal subgroups of $W(k)$, the $k$-fold interated 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)).$

share|cite|improve this answer
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! – Brendan McKay Sep 2 '12 at 11:41
And it thereby establishes that the Frattini subgroup is that which has even action on every level. – Brendan McKay Sep 2 '12 at 11:54
@brendan: Good- I hadn't enumerated your subgroups, but was expecting that you would have – Geoff Robinson Sep 2 '12 at 13:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.