1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ In other words, you're toggling a $2\times\cdots\times 2$ cube of lattice points, right? $\endgroup$ Sep 9, 2013 at 14:25
  • $\begingroup$ I am imagining it to be $1 \times 1 \times \dots \times 1 \times 1$. Am I making a mistake? The cube has $2^k$ vertices if that is what you mean. $\endgroup$
    – Turbo
    Sep 9, 2013 at 14:26

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Will the same trick work if we replace cube we some other arbitrary figure that need not be convex? $\endgroup$
    – Turbo
    Sep 11, 2013 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.