Mutually orthogonal binary frequency squares

Abstract

A \emph{frequency square} is a matrix in which each row and column is a permutation of the same multiset of symbols. We consider only {\em binary} frequency squares of order $n$ with $n/2$ zeroes and $n/2$ ones in each row and column. Two such frequency squares are \emph{orthogonal} if, when superimposed, each of the 4 possible ordered pairs of entries occurs equally often. In this context we say that a $k$-MOFS$(n)$ is a set of $k$ binary frequency squares of order $n$ in which each pair of squares is orthogonal. A $k$-MOFS$(n)$ must satisfy $k\le (n-1{)}^2$, and any MOFS achieving this bound are said to be \emph{complete}. For any $n$ for which there exists a Hadamard matrix of order $n$ we show that there exists at least $2^{n^2/4-O(n\log n)}$ isomorphism classes of complete MOFS$(n)$. For $2<n\equiv 2(\mathrm{mod}4)$ we show that there exists a $17$-MOFS$(n)$ but no complete MOFS$(n)$. A $k$-maxMOFS$(n)$ is a $k$-MOFS$(n)$ that is not contained in any $(k+1)$-MOFS$(n)$. By computer enumeration, we establish that there exists a $k$-maxMOFS$(6)$ if and only if $k\in \{1,17\}$ or $5\le k\le 15$. We show that up to isomorphism there is a unique $1$-maxMOFS$(n)$ if $n\equiv 2(\mathrm{mod}4)$, whereas no $1$-maxMOFS$(n)$ exists for $n\equiv 0(\mathrm{mod}4)$. We also prove that there exists a $5$-maxMOFS$(n)$ for each order $n\equiv 2(\mathrm{mod}4)$ where $n\ge 6$.