3
$\begingroup$

Suppose I have a set whose cardinality is a power of 2, i.e. made of $N=2^n$ elements. If we consider the group of all the permutations of this set (the symmetric group $S_N$), we can say that it has $(2^n)!$ elements. Now suppose I define a family of partitions of this set, specifically a tree of binary partitions: I divide the set into two equipotent subsets (i.e., I define a binary partition), then I divide each subset into two equipotent sub-subsets, and so on, until I obtain single-element sets. It is easy to show that the number of subdivision is n.

The penultimate level of partitions (before we obtain singletons), which I identify by $k=1$, has $N/2$ (or $2^{(n-1)}$) subsets. I consider the permutations within each two-element subset (which are two). They generate $2^{(N/2)}$ possible permutations of the elements in the set, because the subsets are $N/2$.

Then I go to the larger set level (the $k=2$ one): it has $N/4$ subsets, each one has two of the k=1 level subsets. I consider the operation that exchanges the two k=1 level subsets within each two $k=2$ level subset. We have $2^{(N/4)}$ possible permutations of the subsets of the $k=2$ level subset because the subsets are $N/4$.

I go on until I reach the largest set ($k=1$), which has 2 permutations of its subsets (of $N/2$ elements). If I multiply the permutations I can apply for each level, I obtain that they are $2^{(2^n-1)}$. Is it easy to verify that this number is less than $N!$, the total number of permutations of the group. Thus, if we apply the permutations only within each subset of the binary partition tree, we cannot reach all the permutations of the large set.

This is not surprising because there is not only one possible binary tree of partitions. We can divide the starting set in two equipotent subsets in many ways, and the same applies to his subsets. If we consider all the binary trees of partitions, and count all the possible exchanges within each binary partition at each level, then we can reach all the permutations of the large set.

Is it true? Is it a known result?

ChatGPT (Wolfram GPT) told me that what I am describing is Sylow 2-subgroup of $S_{2^n}$, and that: "Yes — this is essentially known and related to the fact that:

The full symmetric group $S_N$ can be generated by the union of all Sylow 2-subgroups (and their conjugates), which correspond exactly to permutations that arise from binary tree structures with different underlying partitions."

Is that true? Are there references for this topic?

UPDATE I found a related question here

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ I think you are asking whether the subgroup $G_{2^n}$ generated by all Sylow 2-subgroups of $S_{2^n}$ (or more generally, $S_m$) is all of $S_{2^n}$. The subgroup $G_{2^n}$ is normal. For $m>4$ the only normal subgroups of $S_m$ are $S_m$, the alternating group $A_m$, and the one-element group. Since a Sylow 2-subgroup contains an odd permutation (e.g., any transposition) $G_m\neq A_m$. Hence $G_m=S_m$ for $m>4$. $\endgroup$ Commented Mar 26 at 18:39
  • $\begingroup$ Actually I need a reference to assert (in my paper) that the permutations within each binary partition are nothing but the subgroup generated by all Sylow 2-subgroups. My purpose is to show that if I take all the possible binary tree partitions and all the permutations within each subset of the partitions, I obtain $S_{2^n}$. $\endgroup$ Commented Mar 26 at 20:42

1 Answer 1

Reset to default
2
$\begingroup$

Yes, this is true, and we can give a proof without appealing to the simplicity of $A_n, n \ge 5$ that two binary trees suffice.

In fact $S_{2^k}$ is generated by two elements of order a power of $2$. It will turn out to be convenient to think of $S_{2^k}$ as acting on $\{ 0, 1 \dots 2^k - 1 \}$. Then the two generators can be taken to be a $2^k$-cycle

$$a = (0123 \dots 2^k-1)$$

and an adjacent transposition

$$b = (01).$$

This is because the conjugates of $b$ by powers of $a$ give us all adjacent transpositions $(k, k+1)$, and adjacent transpositions generate all permutations.

As Stanley says in the comments, the subgroups you are studying are the Sylow $2$-subgroups of $S_{2^k}$, so $a$ and $b$ must each be contained in one of them by Sylow II. But we can be more explicit: $a$ is contained in the Sylow given by automorphisms of the binary tree structure on $\{ 0, 1, \dots 2^k - 1 \}$ which sorts according to the binary expansion starting from the last bit, while $b$ is contained in the Sylow given by automorphisms of the binary tree structure which sorts according to the binary expansion starting from the first bit. That is, starting from the root, the $a$-tree has levels given by the partitions

$$\{ w0, w1 \}$$ $$\{ w00, w01, w10, w11 \}$$ $$\{ w000, w001, w010, \dots \}$$

etc. where $w00$ denotes numbers whose binary expansion ends in $00$, etc., while the $b$-tree has levels given by the partitions

$$\{ 0w, 1w \}$$ $$\{ 00w, 01w, 10w, 11w \}$$

etc. The automorphism groups of these binary trees are given by permutations on binary strings of length $k$ with the property that, for every $d$, the effect of the permutation on the last resp. first $d$ bits of a string only depend on those bits. $a$ just adds $1 \bmod 2^k$, so it has this property with respect to the last $d$ bits, while $b$ exchanges only the two strings $000 \dots 0$ and $000 \dots 1$, so it has this property with respect to the first $d$ bits.

It is also true that $S_n$ is generated by its Sylow $2$-subgroups for any $n$, and we can again give a proof for all $n$ without appealing to the simplicity of $A_n$: $S_n$ is generated by transpositions, and transpositions live in some Sylow. Incidentally, Gemini 2.5 Pro Experimental can correctly answer this question, independently generates this argument, and gives a simpler proof than mine that two binary trees suffice for any $S_n$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Your link doesn't open (auth error). $\endgroup$ Commented Mar 29 at 22:03
  • $\begingroup$ Incidentally, your two trees look to me like a $q=1$ analogue of the fact that a general linear group $\operatorname{GL}_n\left(F\right)$ over a field $F$ is always generated by its upper-triangular and its lower-triangular matrices. Here, instead of invertible matrices, you have permutations of $\left(\mathbb{Z}/2\right)^n$, and instead of "upper-triangular", you have "the first $k$ bits of the output depend only on the first $k$ bits of the input" and likewise for lower-triangularity. Maybe there is a $q=1$ analogue of the Bruhat decomposition as well? $\endgroup$ Commented Mar 29 at 22:11
  • $\begingroup$ @darij: that's strange, I have no idea what's going on with the share settings. And yes, these are closely analogous to lower and upper triangular matrices. $\endgroup$ Commented Mar 30 at 0:36

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.