Hypercube Packings and Coverings with Higher Dimensional Rooks

Abstract

We introduce a generalization of classical $q$-ary codes by allowing points to cover other points that are Hamming distance $1$ or $2$ in a freely chosen subset of all directions. More specifically, we generalize the notion of $1$-covering, $1$-packing, and $2$-packing in the case of $q$-ary codes. In the covering case, we establish the analog of the sphere-packing bound and in the packing case, we establish an analog of the singleton bound. Given these analogs, in the covering case we establish that the sphere-packing bound is asymptotically never tight except in trivial cases. This is in essence an analog of a seminal result of Rodemich regarding $q$-ary codes. In the packing case we establish for the $1$-packing and $2$-packing cases that the analog of the singleton bound is tight in several possible cases and conjecture that these bounds are optimal in general.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.