Resolving the Existence of Full-Rank Tilings of Binary Hamming Spaces
Patric R. J. Östergård, Alexander Vardy · SIAM Journal on Discrete Mathematics · 2004
A tiling of $\F^n$ is a pair (V,A) of subsets of $\F^n$ such that every $x \in \F^n$ can be written in exactly one way as x = v + a with $v \in V$ and $a \in A$. A tiling (V,A) of $\F^n$ is said to be full-rank if $\rank(V)=\rank(A)=n$ and $\zero \in (V\! \cap A)$. It is known that every tiling (V,A)$ decomposes into smaller tilings that are either trivial or full rank. It is furthermore known that full-rank tilings of $\F^n$ exist for all $n \geq 10$ and do not exist for $n \leq 8$. The last case n= 9 is resolved in this paper, thereby proving that full-rank tilings of $\F^n$ exist if and only if $n \ge 10$. To establish this result, we use two different methods. The first method employs group characters to show that the sets V and A in a full-rank tiling (V,A) of $\F^9$ must have a certain structure. The second method is based on the classification of [14,5,3] binary linear codes and uses a fast algorithm for the exact cover problem. Both methods rely on a carefully designed exhaustive computer search to complete the proof.