The Geometry of Frequency Squares

Dieter Jungnickel
University of Augsburg, Germany
(joint work with V.C.Mavron and T.P.McDonough)

The concept of a frequency square is a generalisation of that of a latin square: A type $F(n,\mu)$ frequency square over a set $S$ of order $m\geq2$ is an $n\times n$ matrix over $S$ such that each element of $S$ appears exactly $\mu$ times in every row and column, so $n=\mu m$. As in the case of latin squares, there is a natural concept of orthogonality: Two frequency squares $M,N$ of type $F(n,\mu)$ are orthogonal if they are over the same set $S$ and every element of $S^{2}$ occurs exactly $\mu ^{2}$ times among the pairs $(M_{ij},N_{ij})$, $1\leq i,j\leq n$.

The maximum number of latin squares that are mutually orthogonal to one another is bounded by a simple function of the order of the squares, and sets of latin squares realising this bound are called complete. R. C. Bose established that the existence of a complete set is equivalent to that of an affine plane. Laywine and Mullen investigated this situation with the aim of extending Bose's theorem to frequency squares. They established links between affine 2-designs and complete sets of mutually orthogonal frequency squares (MOFS). However, this approach does not give equivalence, as there are affine 2-designs which do not arise from complete sets of MOFS.

We shall provide a definitive answer to the problem of finding a geometric interpretation of MOFS by showing that they are equivalent to a certain special type of nets which we decided to call framed nets. We use this result to give a new proof for the bound on the maximum size of a set of MOFS by a counting argument which permits us to show that the existence of a complete set (that is one realising the bound) of MOFS is equivalent to the existence of a certain type of partial design (PBIBD). In the case of latin squares, this PBIBD is an affine plane with two parallel classes deleted. In consequence, we finally obtain the proper generalisation of Bose's theorem which had proved elusive for such a long time. We also discuss examples obtained from classical affine geometry and provide recursive construction methods for (completely) framed nets, in this way unifying all known construction methods for complete sets of MOFS.

For background, see either of the following references:

A. Hedayat, N. J. A. Sloane and J. Stufken, Orthogonal Arrays, Springer, 1999.

C. F. Laywine and G. L. Mullen, Discrete Mathematics using Latin Squares, Wiley-Interscience, 1998.