Maximal partial packings of \(\mathbb Z_2^n\) with perfect codes (Q2384004)

This paper continues work on maximal partial packings of \( GF(2)^n \) with perfect 1-error correcting codes, that was started by \textit{O. Heden} [Discrete Math 256, 479--485 (2002; Zbl 1014.94014) and ``On tilings with different perfect codes'', manuscript (2000), submitted for publication]. The results shown in this paper heavily rely on results of \textit{F. Hergert} [Algebraische Methoden für nichtlineare Codes. Dissertation. Darmstadt (1985; Zbl 0578.94016)] and Heden (2000), which is mentioned to be a manuscript probably meaning that it is not published yet. I did not check these references for the stated results. Sections 1,2 and 3 introduce the reader to the subject and list some basic facts. Furthermore in Section 2 the author narrows down the notion of perfect codes to the ones that are 1-error correcting, so the title of the paper is somewhat misleading. Section 4 gives a condition on the duals of two Hamming codes, which is equivalent with certain translates of these codes being disjoint. Furthermore, by giving several counterexamples this result is shown to be untrue for translates of general (nonlinear) perfect codes. Nevertheless it still holds that if the codes satisfy the condition then certain translates are disjoint (i.e. one side of the equivalence still is valid). Using Fourier coefficients and the very powerful Proposition 2.3 (proved in [Heden, loc. cit.], the author derives in Section 5 the following range for the packing number \(p\) of maximal strictly partial Hamming packings in terms of the length \(n\) and dimension \(m\) of the Hamming codes: \( m+1 \leq p \leq n-1 \). The upper bound is easily seen to be true for the packing numbers of general packings but the restriction to Hamming codes puts in the requirement of linearity. Section 6 shows the existence of maximal strictly partial Hamming packings of length 7 and 15 realizing all packing numbers in the range \( m+1 \leq p \leq n-1 \). The examples were found by a computer search. In addition, Section 6 gives a construction method for a maximal strictly partial Hamming packing of length \(n\), dimension \(m+1\) and packing number \(n+1-r\) from a maximal strictly partial Hamming packing of length \(n'\), dimension m and packing number \(n'+1-r\). These two results show that the upper bound on the range for the packing number is tight. The motivation for the work lies in the similarity to the problem of finding maximal partial spreads in finite geometry, and the usefulness for some constructions of nonlinear 1-error correcting perfect codes. The paper was very worthwhile reading.