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

Question

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\}\})$

Answer 1

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

Answer 2

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