% A LaTeX file for a six page document
%
\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\setlength{\textwidth}{6.2in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\topmargin}{0pt}
\hyphenpenalty=1000
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics \textbf{7}
(2000),
\#R56\hfill}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remark}[theorem]{Remark}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\
\rule{0.5em}{0.5em}}
\bibliographystyle{plain}
\title{\textbf{Frequency squares and affine designs}}
\author{V\ C\ Mavron\\
Department of Mathematics,\\
University of Wales,\\
Aberystwyth, SY23 3BZ\\
U.K.\\
{\small\texttt vcm@aber.ac.uk}\\
{Submitted: May 17, 2000; Accepted: November 22, 2000.}
}
\date{}
\begin{document}
\thispagestyle{empty}
\maketitle
\begin{abstract}
The known methods for constructing complete sets of mutually
orthogonal
frequency squares all yield one of two parameter sets.
We show that almost all these
constructions can be derived from one basic design theory
construction.
\par\medskip
\noindent
{{\em Key words\/}: Matrices, block designs, orthogonal arrays,
Latin squares.
\hfill}\\
{{\em AMS subject classifications\/}: Primary 05B20, Secondary 05B05,
05B15.}
\end{abstract}
\section{Introduction}
Frequency squares are an extension of the concept of latin squares.
Investigations have centred on finding analogues to Bose's theorem: a
set of
mutually orthogonal $n\times n$ latin squares has at most $n-1$
squares. The
set is complete if it has $n-1$ squares.
Laywine and Mullen
(\cite{LMa}, \cite{LMb})
have investigated frequency squares from this
viewpoint. See also
\cite{CD}
for an account. There are at present only two known
parameter sets of complete sets of mutually orthogonal frequency
squares
(MOFS). We shall show that most of the known constructions may be
obtained
through just one general design theory construction involving
parallel classes
of lines in affine designs.
More detailed information on basic design theorems, definitions and
terminology used in this paper may be found in
\cite{BJL}, \cite{CD}, \cite{DK} and \cite{LMb}.
Here we
give a brief outline.
Let $D$ be a 1-$(v,k,r)$ design, with $v$ points, $k$ points on each
block,
$b$ blocks and $r$ blocks on each point. If the blocks of $D$ can be
partitioned into $r$ subsets of $m=v/k$ disjoint blocks, called
parallel
classes, then $D$ is \emph{resolvable. }In this case, if further any
two
blocks from different parallel classes (i.e. non-parallel blocks)
meet in a
constant number $\mu$ points, then $\mu=k/m$ and $D$ is said to be
\emph{affine,} or $D$ is an $(m,r;\mu)$\emph{ net.}
Suppose $D$ is affine. If the dual design $D^{\ast}$ of $D$ (which is
a
1-$(b,r,k)$ design) is resolvable, then it can be shown that $r\leq
k$
(\cite{BJL}, \cite{Mb}, \cite{MT})
with equality if and only if $D^{\ast}$ is also affine. When
$D,D^{\ast}$ are both affine then $b=v=\mu m^{2}$ and $r=k=\mu m$ and
$D$ is
called a \emph{symmetric} $(\mu,m)$-\emph{net.}
Note that \emph{transversal }designs are just the duals of affine
designs.
An $n\times n$ matrix $F$ is a \emph{frequency square }of \emph{type}
$F(n,\mu)$ over an $m$-set $S$ if each element of $S$ occurs with
\emph{frequency }$\mu$ $(=n/m)$ in each row and each column. Thus $F$
is a
latin square when $\mu=1$.
Two $n\times n$ frequency squares over $S$ are \emph{orthogonal }\ if
when one
is superimposed on the other, each ordered pair from $S\times S$
occurs
exactly $\mu^{2}$ times. (This clearly agrees with the idea of
orthogonality
in latin squares.)
We remark that there is a more general definition for frequency
squares which
allows the frequencies of different elements of $S$ to differ.
Hedeyat et al
\cite{HRS}
showed that a set of type $F(\mu m,\mu)$ MOFS has at most\break%%%
$(\mu m-1)^{2}/(m-1)$ squares. The set is \emph{complete} if it has
this
many squares.
According to
\cite{CD},
the only complete sets of MOFS known are of type $F(n,\mu)$
with either: (i) $m$ a prime power and $n$ a power of $m;$ or (ii)
$n=2m$ is
the order of a Hadamard matrix, where $n=\mu m$.
\section{A construction}
The construction described here for complete sets of MOFS is based on
a
technique for constructing affine 2-designs with parallel classes of
lines.
A \emph{line} in an affine 2-$(\mu m^{2},\mu m,(\mu m-1)/(m-1))$
design $D$ is
the intersection of all blocks containing two given points. Thus a
line $L$ is
contained in exactly $\lambda=(\mu m-1)/(m-1)$ blocks. A block $B$ is
\emph{parallel to }$L$ if $B$ is parallel to a block containing $L$.
(So $B$
either contains $L$ or misses $L.)$ A parallel class is parallel to
$L$ if
some (and hence every) block in it is parallel to $L$.
Thus a line is parallel to exactly $\lambda$ parallel classes. We say
two
lines are parallel if they are parallel to the same $\lambda$
parallel classes.
It is well known and easy to prove that a line $L$ has at most $m$
points; and
$L$ has exactly $m$ points if and only if each block not parallel to
$L$ meets
$L$ in a point.
\begin{theorem}
If there exists an affine 2-$(\mu m^{2},\mu m,(\mu m-1)/(m-1))$
design with a
parallel class of lines, then there exists a complete set of MOFS of
type
$F(\mu m,\mu)$.
\end{theorem}
\begin{proof}
Let the affine 2-design be $\Gamma$ and let $\mathcal{L}=\left\{
L_{1}%
,L_{2},...,L_{\mu m}\right\} $ be a parallel class of lines.
Choose any parallel class of blocks $E=\left\{
E_{1},E_{2},...,E_{m}\right\}
$ of $\Gamma$ not parallel to $\mathcal{L}$. Let $E_{j}$ meet $L_{i}$
in the
point $L_{ij}$ $(1\leq i\leq m;\,\,1\leq j\leq\mu m)$. Then each
point of
$\Gamma$ is uniquely expressible in the form $L_{ij}$.
Choose $X$ from any of the $\lambda=(\mu m-1)/(m-1)$ parallel classes
that are
parallel to $\mathcal{L}$. Now $\Gamma$ has $r=(\mu m^{2}-1)/(m-1)$
parallel
classes and so has $r-\lambda=\mu m$ not parallel to $\mathcal{L}$.
Choose $Y$
from any of the $\mu m-1$ parallel classes not parallel to
$\mathcal{L}$,where
$Y\neq E$. Then we define a frequency square $F=F(X,Y)$ as follows.
Given $i,j$ where $1\leq i,j\leq\mu m$, then $F_{ij}$ is determined
thus. Let
$X_{t}\,\,(1\leq t\leq m)$ be the unique block of $X$ containing the
line
$L_{i}$. Then if the block in $Y$ on $L_{jt}$ is $Y_{\alpha}$ $(1\leq
\alpha\leq m)$, we define $F_{ij}=\alpha$.
We show $F$ is a frequency square of type $F(\mu m,\mu)$. Given $j$
$(1\leq
j\leq\mu m)$ and $\alpha$ $(1\leq\alpha\leq m)$, we count $i$ for
which
$F_{ij}=\alpha$. Now if $L_{jt}$ is the unique point of $L_{j}$ on
$Y_{\alpha
}$, then $L_{i}$ can be any of the $\mu$ lines of $\mathcal{L}$
contained in
$X_{t}$. So there are $\mu$ values of $i$.
Next, given $1\leq i\leq\mu m$ and $\alpha$, let $X_{t}$ be the
unique block
of $X$ containing $L_{i}$. Then for $F_{ij}=\alpha$, we can choose
$L_{j}$ to
be any of the $\mu$ lines in the intersection of $E_{t}$ and
$Y_{\alpha}$. It
follows that $\alpha$ appears $\mu$ times in each row and column of
$F$. So
$F$ is a frequency square as required.
Consider another such frequency square
$F^{\prime}=F(X^{\prime},Y^{\prime})$,
where either $X\neq X^{\prime}$ or $Y\neq Y^{\prime}$. We shall show
that $F$
and $F^{\prime}$ are orthogonal.
Given $\alpha,\beta$ $(1\leq\alpha,\beta\leq m)$, consider the
simultaneous
equations in $i$ and $j$: $F_{ij}=\alpha$,
$F_{ij}^{^{\prime}}=\beta$.
There are two cases to examine:\vspace{0.2in}
\noindent\textbf{Case }$X\neq X^{\prime}$:\ Then $\lambda>1$ and so
$\mu>1$.
Choose any $j$ $(1\leq j\leq\mu m)$. Let $Y_{\alpha}$ and
$Y_{\beta}^{\prime}$
meet the line $L_{j}$ at $L_{jt}$ and $L_{ju}$, respectively. In
$\Gamma$,
$X_{t}$ and $X_{u}^{\prime}$ meet in $\mu$ points, and hence in
$\mu/m$ lines
of $\mathcal{L}$.
If $L_{i}$ is any of these lines, then the above equations both hold.
\noindent\textbf{Case }$X=X^{\prime}$: Then $Y\neq Y^{\prime}$. Let
$L_{jt}$
be any of the $\mu$ points in which $Y_{\alpha}$ meets
$Y_{\beta}^{\prime}$.
Choose $i$ so that $L_{i}$ is one of the $\mu$ lines of $\mathcal{L}$
contained in $X_{t}$. Then again the equations both hold.
Therefore $F$ and $F^{\prime}$ are orthogonal. It follows that by
varying $X$
and $X^{\prime}$ we get a complete set of type $F(\mu m,\mu)$
MOFS.\vspace{0.25in}
\end{proof}
Observe that in the case $\mu=1$, $\Gamma$ is an affine plane of
order $m$ and
the theorem gives a complete set of $n-1$ MOLS of order $n$.
Affine 2-designs with parallel classes of lines can be constructed
using the
following result
(see \cite{Mb}, \cite{Str}, \cite{MT} or \cite{JS}).
\begin{theorem}
The symmetric subnets of an affine 2-design are in one-to-one
correspondence
with its parallel classes of lines. There exists an affine 2-$(\mu
m,\mu,
\break%%%
(\mu-1)/(m-1))$ design and a symmetric $(\mu,m)$-net if and only if
there
exists an affine 2-$(\mu m^{2},\mu m,(\mu m-1)/(m-1))$ design with a
parallel
class of lines.
\end{theorem}
Using this theorem we easily deduce the following corollary to
Theorem 1.
\begin{corollary}
If there exists an affine 2-$(\mu m,\mu,(\mu-1)/(m-1))$ design and a
symmetric
$(\mu,m)$-net, then there exists a complete set of MOFS of type
$F(\mu m,\mu)$.
\end{corollary}
\begin{remark}
It is well known (see
\cite{BJL} or \cite{CD},
for instance) that the existence of a
symmetric $(\mu,m)$-net is equivalent to that of a generalized
Hadamard $\mu
m\times\mu m$ matrix over a group of order $m$.
\end{remark}
In particular it follows from this remark, putting $m=2$, that the
existence
of a symmetric $(\mu,2)$-net is equivalent to that of a Hadamard
matrix of
order $2\mu$.
Using this connection between symmetric nets and Hadamard matrices we
obtain
the next result.
\begin{theorem}
If there is a Hadamard matrix of order 2$\mu$, then there is a
2-$(4\mu
,2\mu,\break%%%
2\mu-1)$ design with a parallel class of lines. (The design is
necessarily affine and is in fact a 3-$(4\mu,2\mu,\mu-1)$ design.)
\end{theorem}
\begin{proof}
{From} Remark 4 we deduce the existence of a symmetric ($\mu,2)$-net.
It is
well
known
(see \cite{BJL}, \cite{CD} or \cite{UM})
that the existence of a Hadamard matrix of order
$n$ implies that of 2-$(4\mu,2\mu,2\mu-1)$ design which is
necessarily affine
and a 3-design. Now apply Theorem 2.
\end{proof}
\begin{remark}
$\left. {}\right. $
(a) A comparison of Theorems 2.1 and 2.2 suggests, broadly speaking,
that the
existence of a symmetric ($\mu,m)$-net is equivalent to that of a
complete set
of type $F(\mu m,\mu)$ MOFS, perhaps under some extra conditions.
(b) It is well known
(see \cite{BJL}, \cite{CD} or \cite{UM})
that the existence of a Hadamard
matrix of order $2\mu$ implies that of a Hadamard matrix of order
4$\mu$ by
the `doubling' method, and that the existence of a Hadamard matrix of
order
4$\mu$ implies that of a design with the parameters given in Theorem
2.5.
However, Theorem 5 guarantees the existence of a parallel class of
lines in
the design.
\end{remark}
Now we can show how Theorem 1 implies some of the known and perhaps
some new
ways of looking at constructions of complete sets of MOFS.
\begin{enumerate}
\item If we take $\Gamma$ in Theorem 1 to be the affine design
formed by the
points and hyperplanes of the $n$-dimensional affine space over
$GF(m)$ and
choose any of its parallel classes of lines, we obtain complete sets
of MOFS
of type $F(m^{n-1},m^{n-2})$ for any prime power $m$.
This technique seems to be new.
\item
(\cite[IV.20.2, Theorem 20.8(4)]{CD}).
Given an affine %%%\break
2-$(m^{2h},m^{2h-1},(m^{2h-1}-1)/\break%%%
(m-1))$ design $D$ (i.e. an $AD(m^{2h-1},m))$
of dimension at least $2h-2$,
(see \cite{Ma} or \cite{Shr} for definitions),
let
$C_{1}$, $C_{2}$, $\ldots$, $C_{2h-1}$, be independent classes where
$C_{1}$, $C_{2}$, $\ldots$, $C_{2h-2}$ are prime.
Then for any choice of representatives $c_{i}\in C_{i}$
$(1\leq i\leq2h-1)$, the intersection of the $c_{i}$ is a line of
size
$m$ of $D$. Thus we get $m^{2h-1}$ disjoint lines of size $m$ which
are
evidently parallel. Hence we have a parallel class of lines in $D$.
Hence
Theorem 1 applies, giving a complete set of MOFS of type
$F(m^{2h-1},m^{2h-2})$.
\item Street
\cite{Str}
showed there exists a complete set of type $F(\mu m,\mu)$
MOFS if there is a generalized Hadamard $\mu m\times\mu m$ matrix
over a group
of order $m$, and an affine 2-$(\mu m,\mu,(\mu-1)/(m-1))$ design. We
can
deduce this as follows. The existence of a symmetric $(\mu,m)$-net
follows
from Remark 4. Then, from Theorem 2, Corollary 3 and Remark 4 we
deduce that
there exists a complete set of $F(\mu m,\mu)$ MOFS.
\end{enumerate}
\begin{remark}
There exist symmetric nets which cannot be constructed from
generalized
Hadamard matrices (see Mavron and Tonchev
\cite{MT}).
Thus Corollary 3 extends
Street's result.
\end{remark}
\begin{remark}
Laywine \cite{L} constructs an affine 2-design which is not
obtainable
from a family of MOFS.
Then Remark 6 suggests that the affine design does not have a
symmetric
subnet.
However, this is not immediately obvious and further investigation of
the
relationship between nets and MOFS is needed as well as an analysis
of
Laywine's construction.
\end{remark}
\begin{enumerate}
\item [4.]Federer
\cite{F}
showed that there is a complete set of MOFS
of type $F(2\mu,\mu)$ if there is a Hadamard matrix of order $2\mu$.
As a parameter existence result, we can deduce it from Theorems 1 and
5.
\end{enumerate}
Before giving the next existence result for complete sets of MOFS, we
state
the following theorem from Mavron
\cite{Mb}.
\begin{theorem}
If there exists an affine plane of order $m$ and an affine 2-$(\mu
m,\mu,
\break%%%
(\mu-1)/(m-1))$, then there exists a symmetric $(\mu,m)$-net.
\end{theorem}
\begin{enumerate}
\item [5.]
(\cite[IV.20.2, Theorem 20.8(5)]{CD})
\ Suppose there exists an affine
plane of order $m$ and an affine 2-($\mu m,\mu,(\mu-1)/(m-1))$
design. Then
there exists a complete set of type $F(\mu m,\mu)$ MOFS.
This can be obtained from Theorem 1 in the following way. {From}
Theorem 8 we
have the existence of a symmetric ($\mu,m)$-net, and hence from
Corollary 3 the
existence of the MOFS.
\end{enumerate}
\newpage
\begin{thebibliography}{99}
\bibitem{BJL}T Beth, D Jungnickel, H Lenz:
Design Theory, 2nd edition\ (Cambridge University Press, 1999).
\bibitem{CD}C\ J\ Colbourn, J\ H\ Dinitz (eds.),
The CRC Handbook of Combinatorial Designs (CRC\ Press, 1996).
\bibitem{DK}J\ Den\'{e}s, A\ D\ Keedwell:
Latin Squares: New Developments in the Theory and Applications
(Elsevier,
1991).
\bibitem{F}W\ T\ Federer:
On the existence and construction of a complete set of orthogonal
$F(4t;2t,2t)$-square designs,
Ann. Statistics, 5 (1977), 561-564.
\bibitem{HRS}A Hedeyat, D Raghavarao, E Seiden:
Further contributions to the theory of $F$-squares design,
Ann. Statist. 3, (1975), 712-716.
\bibitem{JS}D Jungnickel, S\ S\ Sane:
On existence of nets,
Pacific J. Math. 103 (1982), 437-455.
\bibitem{L}C\ F\ Laywine:
An affine design with $v=m^{2h}$ and $k=m^{2h-1}$ not equivalent to
a complete set of $F(m^h;m^{h-1})$ MOFS,
J. Combin. Designs 7 (1999), 331-340.
\bibitem{LMa}C\ F\ Laywine, G\ L\ Mullen:
Generalizations of Bose's equivalence between complete sets of
mutually orthogonal latin squares and affine planes,
J. Comb. Theory A, 61 (1992), 13-35.
\bibitem{LMb}C\ F\ Laywine, G\ L\ Mullen:
Discrete Mathematics Using Latin Squares (Wiley, 1998).
\bibitem{Ma}V\ C\ Mavron:
On the structure of affine designs,
Math. Z. 125 (1972), 298-316.
\bibitem{Mb}V\ C\ Mavron:
Translations and parallel classes of lines in affine designs,
J. Comb. Theory A, 22 (1977), 322-330.
\bibitem{MT}V\ C\ Mavron, V\ D\ Tonchev:
On symmetric nets and generalized Hadamard matrices from affine
designs,
J. Geom. 67 (2000), 180-187.
\bibitem{Shr}S\ S\ Shrikhande:
Affine resolvable balanced incomplete block designs: a survey,
Aequat. Math. 14 (1976), 251-269.
\bibitem{Str}D\ J\ Street:
Generalized Hadamard matrices, orthogonal groups and $F$-squares,
Ars. Comb. 8 (1979), 131-141.
\bibitem{UM}S\ Ud Din, V\ C\ Mavron:
On designs constructed from Hadamard matrices,
Proc. London Math. Soc. (3), 49 (1984), 274-288.
\end{thebibliography}
\end{document}