Linear combinations of basic cubes on a torus board

Question

Consider an $n \times n \times n \times\dots\times n$ torus board of total size $n^k$ with $n > 4$ either even or odd.

Consider the basic cube of size $1 \times 1 \times \dots \times 1$ at a lattice point on the board and label the vertices from $\Bbb F_2$ with the vertices of the cube taking value $1$ and rest of the board taking value $0$. Translate the cube over each of the lattice points to get $n^k$ distinct $F_2$ configurations of the board. Call the set of configurations as $C$.

One can take $2^{n^k}$ possible $F_2$ linear combinations of the members of $C$ of which many resulting configurations would be the same. Call the new set of configurations $D$.

My question:

Is there a recurrence formula for the number of distinct elements of $D$ in terms of $n$ and $k$? What is $|D|$, the cardinality of $D$?

Answer 1

Note that the set of available configurations is in fact a $\mathbb{F}_2$-vector space.

In one dimension (that is, for $k=1$), it's easy to see that that vector space has dimension $n-1$: you can get all but one of the lattice points to be whatever you want, and then the last one is forced to be the sum of the ones that remain. Call that space $V\subset\mathbb{F}_2^n$.

Now, in general, you're working with $D$, which is just the $k$-th tensor power $V^{\otimes k}$ of $V$, and hence the dimension is $(n-1)^k$, and hence the number of configurations is $|D|=2^{(n-1)^k}$. Why's that? Well, the vector space of configurations, is generated by operations which are exactly tensor products of the generators of $V$.

---

A conceptually simpler, but perhaps less powerful, way of seeing that $|D|=2^{(n-1)^k}$ is this. First, observe that in any line, the status of any $n-1$ lattice points suffices to determine the last: this is true for parity reasons, since they're always changed two-at-a-time.

That means that (by straightforward induction on dimension), a cubical block of $(n-1)^k$ lattice points suffices to determine all the others, so there are at most $2^{(n-1)^k}$ configurations. And it's also easy to see that such a block can be configured in any way, by flipping boxes as appropriate in lexicographical order. Hence there are exactly $2^{(n-1)^k}$ configurations.