Mutually orthogonal binary frequency squares


Abstract in English

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 $kle(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(nlog n)}$ isomorphism classes of complete MOFS$(n)$. For $2<nequiv2pmod4$ 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 $kin{1,17}$ or $5le kle 15$. We show that up to isomorphism there is a unique $1$-maxMOFS$(n)$ if $nequiv2pmod4$, whereas no $1$-maxMOFS$(n)$ exists for $nequiv0pmod4$. We also prove that there exists a $5$-maxMOFS$(n)$ for each order $nequiv 2pmod{4}$ where $ngeq 6$.

Download