Skip to main content
added alternative approach
Source Link
James Cranch
  • 3.1k
  • 23
  • 31

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.

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

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.

Edited answer to better reflect edited question: trying to hit a moving target.
Source Link
James Cranch
  • 3.1k
  • 23
  • 31

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 $2^{(n-1)^k}$$|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$.

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 the $k$-th tensor power of $V$, and hence the dimension is $(n-1)^k$, and hence the number of configurations is $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$.

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

Source Link
James Cranch
  • 3.1k
  • 23
  • 31

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 the $k$-th tensor power of $V$, and hence the dimension is $(n-1)^k$, and hence the number of configurations is $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$.