Rook domains, Latin squares, affine planes, and error-distributing codes

Abstract

A problem originally suggested in the context of genetic coding leads naturally to the concept of {\em rook packing} and {\em error-distributing codes}. It is shown how various concepts in the theory of Latin squares, and also in coding theory, are best expressed in the form of questions about the placing of rooks on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</tex> -dimensional hyperchessboards of side <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</tex> . A new species of combinatorial design suggested by this is the concept of {\em optimal coloring}. It is shown that the optimal colorings in certain cases correspond to duals of desarguian projective planes. Light is thereby shed on the problems of the existence of both finite projective planes and close-packed single-error-correcting codes. In particular, the existence of a certain close-packed nonbinary single-error-correcting code, listed by Golay as the first unknown case, has been ruled out by a well-known result concerning Latin squares.