On perfect codes and tilings: Problems and solutions.

*(English)*Zbl 0908.94035This paper contains several new results concerning (linear or nonlinear) perfect binary codes and tilings of binary Hamming spaces, and it is at the same time a good survey of these topics. It is shown that for each \(m \geq 3\), there exists two perfect binary one-error-correcting codes of length \(2^m-1\) such that their intersection consists of two codewords. As all such perfect codes are self-complementary, this is the smallest possible nonempty intersection. Moreover, all possible intersection numbers are determined in the linear case. A necessary and sufficient condition for determining when a perfect binary code has a shorter perfect code embedded in it is given. Finally, the connection between perfect binary codes and tilings is considered. The paper is concluded with a list of important open problems.

Reviewer: P.R.J.Östergård (Helsinki)