10
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\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
    Commented Sep 2, 2012 at 11:41
  • $\begingroup$ And it thereby establishes that the Frattini subgroup is that which has even action on every level. $\endgroup$
    – Brendan McKay
    Commented Sep 2, 2012 at 11:54
  • $\begingroup$ @brendan: Good- I hadn't enumerated your subgroups, but was expecting that you would have $\endgroup$
    – Geoff Robinson
    Commented Sep 2, 2012 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
    Commented Dec 3, 2017 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
    Commented Dec 3, 2017 at 14:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .