# Existence of a certain composition series for the group $2^{\mathbb Z / 2^n \mathbb Z}$

This question is essentially to come up with a solution for this problem in the case where there are $$2^n$$ coins. Let $$C_n$$ be the group $$\{f : \mathbb Z / 2^n \mathbb Z \to \mathbb Z / 2 \mathbb Z\}$$ equipped with the group operation pointwise addition. Let $$R_n = \mathbb Z / 2 \mathbb Z \times \mathbb Z / 2^n \mathbb Z$$, and let $$R_n$$ act on $$C_n$$ via $$(\alpha, x) \cdot f(y) = \bar{\alpha} + f(x + y)$$, where $$\bar \alpha = (\alpha, \alpha, ..., \alpha)$$. I would like to exhibit the existence of a series $$\{0\} = G_0 < G_1 < G_2 < ... < G_{2^n} = C_n$$ such that the following holds:

(1) $$|G_i| = 2^i$$

(2) $$(G_i \setminus G_{i-1}) \cdot (G_i \setminus G_{i-1}) \subset G_{i-1}$$. Edit: Sean Eberhard correctly pointed out that this condition is superfluous.

(3) Each $$G_i$$ is closed under the action of $$R_n$$ for $$i > 0$$.

I can exhibit such a series for $$n = 1, 2, 3$$. I'd like to know if such a series exists for all $$n$$. We will denote an element of $$C_n$$ as a subset of $$\{0, 1, ..., 2^n\}$$, so that $$S$$ denotes the function $$f_S$$ such that $$f_S(x) = 1$$ if and only if $$x \in S$$. For a set $$T \subset C_n$$, we will use the notation $$gen(T)$$ to denote the subgroup generated by elements of the form $$r \cdot t$$ for $$r \in R_n, t \in T$$.

For $$n = 1$$, we can take

• $$G_1 = gen(\{\{0, 1\}\})$$
• $$G_2 = gen(G_1 \cup \{\{0\}\})$$

For $$n=2$$, we can take

• $$G_1 = gen(\{\{0, 1, 2, 3\}\})$$
• $$G_2 = gen(G_1 \cup \{\{0, 2\}\})$$
• $$G_3 = gen(G_2 \cup \{\{0, 1\})$$
• $$G_4 = gen(G_3 \cup \{\{0\}\})$$

For $$n=3$$, we can take

• $$G_1 = gen(\{\{0, 1, 2, 3, 4, 5, 6, 7\}\})$$
• $$G_2 = gen(G_1 \cup \{\{0, 2, 4, 6\}\})$$
• $$G_3 = gen(G_2 \cup \{\{0, 1, 4, 5\}\})$$
• $$G_4 = gen(G_3 \cup \{\{0, 4\}\})$$
• $$G_5 = gen(G_4 \cup \{\{0, 1, 2, 3\}, \{0, 1, 3, 6\}\})$$
• $$G_6 = gen(G_5 \cup \{\{0, 1, 2, 5\}, \{0, 2\}\})$$
• $$G_7 = gen(G_6 \cup \{\{0, 1\}, \{0, 3\}, \{0, 1, 3, 5\}, \{0, 1, 2, 4\}\})$$
• $$G_8 = gen(G_7 \cup \{\{0\}\})$$
• (2) is redundant, because $G_i / G_{i-1}$ must be cyclic of order 2. Oct 22, 2021 at 10:08
• Thanks, good point. I didn't mean to impose the restriction that $G_{i-1}$ be a normal subgroup of $G_i$ (looks like I misused the phrase "composition series" in the title; apologies: it's been almost a decade since I took an algebra course). But in any case any subgroup of index 2 is automatically normal. Oct 22, 2021 at 16:41

You found a construction yourself but I will add another answer anyway in case it useful for generality or context.

Let $$G$$ be a $$p$$-group acting on a finite-dimensional vector space $$V$$ over a field $$F$$ of characteristic $$p$$. I claim there are $$G$$-invariant subspaces $$0 = V_0 < \cdots < V_d = V$$, where $$d = \dim V$$ (sometimes a "complete $$G$$-invariant flag"). Moreover $$V_i / V_{i-1}$$ is the trivial $$G$$-module for each $$i$$. This is something like a version of Engel's theorem for finite $$p$$-groups in characteristic $$p$$.

Proof: Let $$\Gamma$$ be the semidirect product $$V \rtimes G$$. Then $$\Gamma$$ is a $$p$$-group and $$V$$ is a normal subgroup, so $$V \cap Z(\Gamma)$$ is nontrivial (well-known fact/exercise, see this previous question). Let $$V_1 \leq V \cap Z(\Gamma)$$ be a subgroup of size $$p$$. Then $$V_1$$ is $$G$$-invariant (with trivial $$G$$-action) so we can look $$V / V_1$$ and use induction. $$\square$$

Moreover, suppose $$V$$ is a permutation representation $$V = \mathbf{F}_p^\Omega$$, where $$G$$ acts on $$\Omega$$. Then we are free to choose $$V_1 = \langle \mathbf1 \rangle$$, where $$\mathbf1$$ is the all-one vector. If we do this then $$V_i + \mathbf1 = V_i$$ for all $$i > 0$$.

In your case, $$p = 2$$ and $$G = \Omega = \mathbf{Z}/2^n \mathbf{Z}$$.

The group $$G$$ is the group of subsets of $$\mathbb Z / 2^n \mathbb Z$$ equipped with the operation symmetric difference. Let $$A^{(n)} = \mathbb Z / 2^n \mathbb Z$$, and let $$A$$ act on $$G$$ similarly to $$R$$, i.e. $$a \cdot S = a + S = \{a + x : x \in S\}$$. It's enough to construct the composition series $$\{G_h\}_{h=0}^{2^n}$$ such that each $$G_i$$ is invariant under the action of $$A$$, so long as $$G_1 = \{\emptyset, \mathbb Z / 2^n \mathbb Z\}$$. Letting $$G = G^{(n)}$$, we will construct the composition series by induction on $$n$$. For $$n = 0$$, we can just take $$G^{(0)}_0 = \{\emptyset\}$$ and $$G^{(0)}_1 = G^{(0)}$$. In general, we will let $$G_h^{(n)} = \langle S_i^{(n)} : 1 \leq i \leq h \rangle$$. This guarantees (1) so long as $$S_i^{(n)} \notin G_{i-1}^{(n)}$$.

For $$i \leq 2^{n-1}$$, let $$S_i^{(n)} = S_i^{(n-1)} \cup (S_i^{(n-1)} + 2^{n-1})$$. Note that, if $$a \in A^{(n)}$$, $$a \cdot S_i^{(n)} = \bar a \cdot S_i^{(n-1)} \cup (\bar a \cdot S_i^{(n-1)} + 2^{n-1}),$$ where $$\bar a = a$$ if $$a < 2^{n-1}$$ and $$\bar a = a - 2^{n-1}$$ otherwise. By the inductive hypothesis, $$\bar a \cdot S_i^{(n-1)} \in G_i^{(n-1)}$$. It also follows by induction that $$G_i^{(n)} = \{S \cup (S + 2^{n-1}) : S \in G_i^{(n-1)}\}.$$ From this we obtain that $$G_i$$ is invariant under the action of $$A$$ for $$i \leq 2^{n-1}$$.

For $$i > 2^{n-1}$$, we let $$S_i^{(n)} = S_{i - 2^{n-1}}^{(n-1)}$$. Note that, in particular, for any $$\bar a \in A^{(n-1)}$$, $$\bar a S_{i-2^{n-1}}^{(n-1)} \in G^{(i)}$$. Now, for any $$a \in A^{(n)}$$, $$a \cdot S_i^{(n)} = {\Big (} \prod\limits_{j=0}^{a-1} \{j, j + 2^{n-1}\} {\Big )} (- \bar a \cdot S_{i-2^{n-1}}^{(n-1)}).$$ Note that $$\{j, j + 2^{n-1}\} \in G_{2^{n-1}}$$ for all $$j$$, and so $$a \cdot S_i^{(n)} \in G_i^{(n)}$$. From this it follows that $$A \cdot G_i^{(n)} = \langle G_{i-1}^{(n)}, A \cdot S_i^{(n)} \rangle = G_i^{(n)}$$, so $$G_i^{(n)}$$ is invariant under the action of $$A$$.