Perfect sphere packings (as opposed to perfect ball packings) I came across this question when I was discussing the rather wonderful Devil's Chessboard Problem with my colleague, Francis Hunt.
We realised that there is a nice connection to a packing question in $(\mathbb{F}_p)^n$ and I want to ask what is known about this.
Construction: Let $d$ be a positive integer and let $n=2^d$. Now construct the $d$-by-$2^d$ matrix $M$ over $\mathbb{F}_2$ which has vectors in $(\mathbb{F}_2)^d$ as columns (in some order). So, for instance, when $d=2$, we might have
$$
M= \begin{pmatrix}
0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \end{pmatrix}.$$
Now let $U$ be the solution set in $V=(\mathbb{F}_2)^{2^d}$ for the homogeneous system with coefficient matrix $M$. (In coding terminology, $U$ is the code with parity-check matrix $M$.) So, in the example above, we have
$$
U=\left\{\begin{pmatrix}0\\0\\0\\0\end{pmatrix}, \begin{pmatrix}0\\1\\1\\1\end{pmatrix}, \begin{pmatrix}1\\0\\0\\0\end{pmatrix}, \begin{pmatrix}1\\1\\1\\1\end{pmatrix}\right\}.
$$
In general $U$ has $2^{2^d-d}$ vectors $v_i$. For each $i$, let $S_i$ be the sphere in $V$ of radius $1$ with centre $v_i$. Then $|S_i|=2^d$ and it is easy to verify that the spheres $S_i$ partition the vectors in $V$. In other words these spheres are a perfect packing of the vector space.

Question: Is this the only way to construct a perfect sphere packing in a finite vector space?

Some comments:

*

*There's obviously loads of stuff in the literature on perfect packings but, so far as I can tell, they normally involve packing balls rather than spheres. Packing balls is the sensible thing to do when working with codes.

*The subspace $U$ is clearly some kind of extension of the Hamming code... But not the extension that goes by the name of "the extended Hamming code"! In coding theory adding that column of 0's to the parity-check matrix is a dumb thing to do, but it works if you think about spheres instead of balls.

*I have had some very preliminary thoughts about the numbers involved here. Suppose we are in a vector space $V=(\mathbb{F}_p)^n$ and, for $r=1,\dots, n-1$, we let $S_r$ be a sphere of radius $r$. Observe that $|S_r|=\binom{n}{r}(p-1)^r$. For a perfect packing to exist we need $|S_r|$ to divide $p^n$. Thus we must have $p=2$. We must also have $\binom{n}{r}$ equal to a power of $2$. I'm thinking that this can only happen if $r\in\{1,n-1\}$ but haven't been able to write down a proof. So...


Question. Is it true that $\binom{n}{r}$ is only equal to a prime power when $r\in\{1,n-1\}$?



*Observe that in $(\mathbb{F}_2)^n$ any sphere of radius $r$ is also a sphere of radius $n-r$ (take the centre $v$ of the first sphere, change all the entries so that you get the unique vector at distance $n$ from $v$ and this will be the centre of the second sphere). Thus the construction given above can be thought of as a partition by $1$-spheres or by $(n-1)$-spheres.

 A: 
Question: Is this the only way to construct a perfect sphere packing in a finite vector space?

No. Take the linear space $V$ generated by the following vectors in $\mathbb{F}_2^8$:
$(0,0,0,1,1,1,1,0)$
$(0,0,1,0,1,1,0,1)$
$(0,1,0,0,1,0,1,1)$
$(1,0,0,0,0,1,1,1)$.
One can see that any two different elements in $V$ differs in at least $4$ places. Projecting $V$ to its first $7$ coordinates generates the Hamming(7,4) code, so any two different elements differs in at least $3$ places. Furthermore, all the elements of $V$ have even weight, so no two elements could differ in exactly $3$ places.
By a counting argument, there are $2^4 \times 8= 128$ elements in $\mathbb{F}_2^8$ that differ from some element of $V$ in exactly $1$ place, and they are exactly the elements with odd weight.
One can take a copy of $V$ and permute its coordinates to get a different linear space $V'$. This is possible because $|V|=16$, and there are $70$ weight-4 vectors in $\mathbb F_2^8$. Displace $V'$ by a odd-weight vector $\alpha$ and call it $U$. The elements that differ from some element of $U$ in exactly $1$ place are exactly those with even weight. Thus $V \cup U $ is a perfect sphere packing.
The only thing left is to check that $V \cup U $ is not a linear space. To see this, let $v\in V \text{\\} V'$. Then $0$, $\alpha$, $v$ are elements of $V \cup U$, but $v+\alpha$ is not, so $V \cup U$ is not a linear space.
