\documentclass[11pt]{article}
\usepackage{times,fullpage}
\usepackage{amsfonts}
\usepackage{amsmath}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}


\newcommand{\GF}[1]{\ensuremath{\mathsf{GF}(#1)}}
\newcommand{\PGL}[2]{\ensuremath{\mathsf{PGL}_{#1}(#2)}}
\newcommand{\alt}{\ensuremath{\mathsf{Alt}}}
\newcommand{\sym}{\ensuremath{\mathsf{Sym}}}
\newcommand{\R}{\ensuremath{\mathsf{R}}}
\newcommand{\D}{\ensuremath{\mathsf{D}}}
\newcommand{\C}{\ensuremath{\mathsf{C}}}
\newcommand{\B}{\ensuremath{\mathsf{B}}}
\newcommand{\A}{\ensuremath{\mathsf{A}}}
\newcommand{\M}{\ensuremath{\mathsf{M}}}
\newcommand{\zed}{\ensuremath{\mathbb{Z}}}
\renewcommand{\P}{\ensuremath{\mathbb{P}}}
\newcommand{\Res}{\ensuremath{\mathcal{R}}}

\def\endproofbox{\hskip 1.3em\hfill\rule{3pt}{9pt}}
\newenvironment{proof}%
{%
 \noindent{\bf Proof:}
}%
{%
 \quad\hfill\endproofbox\vspace*{2ex}
}


\title{Pooling, Lattice Square, and Union Jack Designs}

\author{
Mark A. Chateauneuf\\
Department of Mathematical Sciences,\\
Michigan Technological University,\\
Houghton, MI 49931-1295, USA\\
{\tt machatea@mtu.edu}\\[1ex]
Charles J. Colbourn\\
Department of Computer Science,\\
University of Vermont,\\
Burlington, VT 05405, USA\\
{ \tt Colbourn@emba.uvm.edu }\\[1ex]
Donald L. Kreher\\
Department of Mathematical Sciences,\\
Michigan Technological University,\\
Houghton, MI 49931-1295, USA\\
{\tt kreher@mtu.edu}\\[1ex]
Esther R. Lamken\\
Department of Mathematics, 253-37,\\
California Institute of Technology,\\
Pasadena, CA 91125, USA\\
{\tt lamken@cco.caltech.edu}\\[1ex]
and\\[1ex]
David C. Torney\\
Theoretical Biology and Biophysics,\\
T-10 MS K710,\\
Los Alamos National Laboratory,\\
Los Alamos, NM 87545, USA\\
{\tt dct@lanl.gov}
}
\begin{document}
\maketitle

\begin{abstract}
Simplified pooling designs employ rows, columns, and principal diagonals
from square and rectangular plates. The requirement that every two samples
be tested together in exactly one pool leads to a novel combinatorial
configuration, the union jack design. Existence of union jack designs is
settled affirmatively whenever the order $n$ is a prime and $n \equiv 3 \pmod{4}$.
\end{abstract}

\section{Introduction}

Pooling experiments are used to screen large recombinant DNA libraries
to isolate {\em clones} (sets of subintervals) containing a particular
DNA sequence \cite{BBKT,PPBT}.
Since it is not practical to screen each clone individually, subsets
of clones, called {\em pools}, are used. The specification and
collection of these pools is referred to as a {\em ``pooling design''}.
The primary objective is to determine, for each pool in the
design, whether any of the clones in the pool contain a
specified (small) subinterval. Given the results for each
pool, we want to determine which clones contain the subinterval,
and to do so unambiguously.

Clones are often stored and produced on square or rectangular
plates, and hence, performing the pooling experiment requires
the merging of material from a number of different positions
on the plate. This operation is greatly simplified by defining
the pools to be in a pattern, and in practice, the 
clones from an individual plate can be combined along lines
such as rows, columns, and diagonals \cite{Letal}. 
These combinations are sub-pools which form components
of the final pools. Thus, the pooling design includes the
specification of the templates used to obtain the sub-pools and
the way that the sub-pools are combined to obtain the
final pools.
Since the physical limitations imposed by the templates and 
the presence of experimental error in the pooling outcomes 
must also be taken into account, it can be a challenge to 
construct pooling experiments \cite{KBT}. 

When the rows and columns are considered, designs useful 
for constructing templates in pooling have been studied previously
for the design of experiments \cite{Rag71}.
A {\em lattice square design} of order $n$ is a set of $\frac{n+1}{2}$ arrays,
each $n \times n$ and each containing $n^2$ symbols once. Every pair of
symbols occurs together once either in a row or a column, in exactly one
of the arrays, and does not appear together in a row or column elsewhere.
Note that the rows and columns of the arrays of a lattice 
square design of order $n$
form the blocks of a resolvable $2$-$(n^2,n,1)$ design \cite{BJL,handbook}.
Here is a lattice square design
of order three:
\vspace*{4mm}
\begin{center}
\begin{tabular}{ccccc}
\begin{tabular}{c}
\\
\\
$\! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \!
 \! \! \! $ \\
\end{tabular}
$\left\{ \; \; \left[
\begin{tabular}{ccc}
0 & 1 & 2 \\
3 & 4 & 5 \\
6 & 7 & 8 \\
\end{tabular} \right.\right]$ &
\begin{tabular}{c}
$\! \! \! \! \! \! \! \! \! \! \! \! \! \!$ \\
$\! \! \! \! \! \! \! \! \! \! \! \! \! \!$ \\
$\! \! \! \! \! \; ,\! \! \! \! \! \! \! \! \! \! \! \!$ \\
\end{tabular} &
$\left.\left[
\begin{tabular}{ccc}
0 & 5 & 7 \\
4 & 6 & 2 \\
8 & 1 & 3 \\
\end{tabular} \right] \; \; \right\}$ &
\begin{tabular}{c}
\\
\\
$\! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \!
 \! \! \!$
.\\
\end{tabular}
\end{tabular}
\end{center}
 
Lattice square designs, known initially as {\em quasi-Latin square designs}, were one of the variants of Latin square designs
examined by Yates \cite{yates}; see also \cite{c&c,federer}.
An explicit construction is given in \cite{f&w}.
Raghavarao \cite[p. 171]{Rag71} 
remarks that such lattice square designs can always be obtained from an
affine plane of odd order $n$; partition the $n+1$ parallel
classes of blocks into pairs, and form an $n\times n$ array for each pair by
interpreting blocks in one parallel class as rows and in the other as
columns.
This does not depend on the structure of the plane and so
every affine plane of odd order gives rise to at least one lattice square design.
Different pairings of the parallel classes can lead
to different lattice square designs, and the enumeration of different lattice square
designs appears to be more complex than the (already difficult)
enumeration of the underlying planes. 
The affine plane can always be recovered from the lattice square design, since the $n+1$ parallel classes
from the rows and columns of the $\frac{n+1}{2}$ arrays form such a
plane.

Naturally this approach requires the construction of an affine plane in
order to obtain the lattice square design, and a direct
construction might be preferred. 
However, whenever $n$ is the order of a known affine plane,
$n$ is a power of a prime \cite{BJL}. In this case, there is an affine
plane (which we define subsequently) arising from the finite field of order
$n$. It is a relatively simple matter to write a direct prescription for
an affine plane using the field, and equally straightforward to write a
prescription for the arrays of a lattice square design; we leave the details
to the interested reader.

In this paper, we show that affine planes can also be used to construct
analogous designs in which the rows, columns, front diagonals, and
back diagonals of the arrays each form a parallel class of the plane.
A {\em front diagonal} is a set of array entries $(i,j)$ satisfying
$i-j \equiv b \pmod{n}$ for $b$ a constant and $i,j \in \zed_n$.
Similarly, a {\em back diagonal} satisfies $i+j \equiv b \pmod{n}$.

An {\em RCF design} of order $n$ is a set of $\frac{n+1}{3}$ arrays,
each $n \times n$ and containing $n^2$ symbols once. Every pair of
symbols occurs together once in a row, column, or front diagonal in exactly one
of the arrays, and does not appear together in a row, column, or front diagonal
elsewhere. Here is an RCF design of order 5 defined on 
$\zed_5 \times \zed_5$:

\[
\left\{\left[
\begin{array}{ccccc}
00 & 10 & 20 & 30 & 40 \\[1mm]
01 & 11 & 21 & 31 & 41 \\[1mm]
02 & 12 & 22 & 32 & 42 \\[1mm]
03 & 13 & 23 & 33 & 43 \\[1mm]
04 & 14 & 24 & 34 & 44 
\end{array} \right],\quad
\left[
\begin{array}{ccccc}
00 & 12 & 24 & 31 & 43 \\[1mm]
34 & 41 & 03 & 10 & 22 \\[1mm]
13 & 20 & 32 & 44 & 01 \\[1mm]
42 & 04 & 11 & 23 & 30 \\[1mm]
21 & 33 & 40 & 02 & 14 
\end{array} \right] \right\}.
\]

\medskip

\frenchspacing
RCF designs also arise from affine planes in the following manner.
Form the affine plane from the finite field as follows(see \cite{BJL} 
for relevant background).
Let $X = \{ (x,y) : x,y \in \GF{n}\}$
be the $n^2$ points. Define for each $\M ,b\in \GF{n}$
the line
$L_{\M,b} =\{ (x,\M x +b) : x \in \GF{n} \}$.
Further define for each $b \in \GF{n}$ the line
$L_{\infty,b} =\{ (b,y) : y \in \GF{n} \}$.
Let $\P_n = \GF{n} \cup \{\infty\}$ denote the projective line.
Then the $(n+1)n$ lines $L_{\M,b}$ with
$\M \in \P_n$ and $b\in \GF{n}$ are the blocks of the
affine plane of order $n$. They form a resolvable $2$-$(n^2,n,1)$ design.
The parameter $\M \in \P_n$ of the line $L_{\M,b}$
is called the \emph{slope} of $L_{\M,b}$.
For each $\M\in\P_n$, the set
$\Res(\M) = \{ L_{\M,b} : b \in \GF{n} \}$
contains $n$ lines which partition the $n^2$ points in $X$.
We say that $\Res(\M)$ is the resolution class of lines with slope $\M$.
The $n+1$ resolution classes $R(\M)$, $\M \in \P_n$, partition the
$(n+1)n$ lines of the affine plane.

If $n$ is a prime, then $n \equiv 5 \pmod{6}$,
and it is easy to construct an RCF design from the affine plane.
Partition $\P_n$ into classes of size three, $X_1, \dots, X_{(n+1)/3}$
so that $X_1 = \{\infty,0,1\}$.
The lines with slopes in $X_1$
lead directly to an array
in which the parallel classes form rows, columns,
and front diagonals. Now the group
\PGL{2}{n} acts 3-transitively on the set of slopes $\P_n$,
and hence there is a group element mapping $X_i$ to $X_1$ for each
$i$, $2 \leq i \leq \frac{n+1}{3}$. Applying this automorphism places the
parallel classes corresponding to the slopes in $X_i$ in the roles of
rows, columns, and front diagonals in an $n \times n$ array, and hence
produces the arrays required.
This establishes the following.

\begin{theorem}
If $n$$\equiv$$5 \pmod{6}$ is a prime, then there exists an RCF design of order $n$.
\end{theorem}

Primality of $n$ is employed here to ensure that the lines of slope one
in the field are genuine front diagonals when interpreted in the $n \times n$
array. When $n$ is a prime power but not a prime, this is not guaranteed;
the prime power case is discussed in the last section.

\section{Union Jack Designs of Prime Order }

Simultaneous consideration of rows, columns, front diagonals, and
back diagonals underlies the following
combinatorial definition.
A \emph{union jack design} of order $n$ is a collection
of $n$$\times$$n$ arrays with distinct entries from
a set $X$ of $n^2$ points such that every pair of points
appears exactly once among the rows, columns, front diagonals,
and back diagonals of the arrays. 
Thus, the number of arrays in a union jack design is
${\binom{n^2}{2}}/{4n{\binom{n}{2}}} = \frac{n+1}{4}$.
For example, here is a union jack design of order 7
defined on $\zed_7 \times \zed_7$:
\[
\left \{ {
\left [
\begin{array}{ccccccc}
00&01&02&03&04&05&06\\
10&11&12&13&14&15&16\\
20&21&22&23&24&25&26\\
30&31&32&33&34&35&36\\
40&41&42&43&44&45&46\\
50&51&52&53&54&55&56\\
60&61&62&63&64&65&66
\end{array}
\right ]
,\quad
\left [
\begin{array}{ccccccc}
00&15&23&31&46&54&62\\
56&64&02&10&25&33&41\\
35&43&51&66&04&12&20\\
14&22&30&45&53&61&06\\
63&01&16&24&32&40&55\\
42&50&65&03&11&26&34\\
21&36&44&52&60&05&13
\end{array}
\right ]
} \right \}.
\]


When $n$ is a prime and $n\equiv 3 \pmod{4}$, we give a construction
using the blocks of
the affine plane arising from the finite field
on the set $X = \zed_n\times\zed_n$.
Given $\M,\D\in \P_n$ with $\M$$\neq$$\D$, define $L_{\M,\D,i}$
to be the unique line in $\Res(\M)$ that intersects the line
$L_{\D,0}$ in the pair
\[
\left\{
\begin{array}{ll}
(i,\D i)&\mbox{if } \D \neq \infty\\
(0,i)&\mbox{if } \D = \infty\\
\end{array}
\right\}
\]
Let $\R,\C,\D \in \P_n$ and define
$M=M_{\R,\C,\D}$ to be the $n$ by $n$ matrix whose $[i,j]$-entry
is
\[
M[i,j] = L_{\R,\D,i} \cap L_{\C,\D,j} = (X_{ij},Y_{ij})
\]
where $i,j \in \zed_n$.
Observe that

\begin{flushleft}
(1) every element of $\zed_n \times \zed_n$ appears in some cell of $M$,\\
(2) the rows of $M$ are the lines in $\Res(\R)$, and\\
(3) the columns of $M$ are the lines in $\Res(\C)$.
\end{flushleft}

\begin{theorem}
\label{RCDB}
Let $\R,\C,\D\in\P_n$, $\R$$\neq$$\C$$\neq$$\D$$\neq$$\R$.
Then the front diagonals of $M{=}M_{\R,\C,\D}$, contain
the lines in $\Res(\D)$ and the back diagonals
contain the lines in $\Res(\B)$, where
\[
\B=\B_{\R,\C,\D}=\frac{\R\D + \C\D -2\R\C}{2\D-\R-\C}.
\]
\end{theorem}
\begin{proof}
To simplify calculations, observe that

\begin{eqnarray*}
\B_{\infty,\C,\D}&=&2\C - \D\\[3mm]
\B_{\R,\infty,\D}&=&2\R - \D\\[3mm]
\B_{\R,\C,\infty}&=&{\frac{\R+\C}{2}}\\
\end{eqnarray*}


\noindent{\emph{Case 1: $\R \neq \infty, \C \neq \infty, \mbox{ and } \D \neq \infty$}}.
In this case,
\begin{eqnarray*}
L_{\R,\D,i}&=&\{(X,Y):Y=\R X+(\D-\R)i\}
\end{eqnarray*}
and
\begin{eqnarray*}
L_{\C,\D,j}&=&\{(X,Y):Y=\C X+(\D-\C)j\}.
\end{eqnarray*}
The intersection of these two lines is $(X_{ij},Y_{ij})$ where
\begin{eqnarray*}
X_{ij} &=& \frac{(\D-\C)j-(\D-\R)i}{\R-\C }\\[2mm]
Y_{ij} &=& \R X_{ij} + (\D-\R) i 
= \C X_{ij} + (\D-\C) j
\end{eqnarray*}
Observe that
\begin{eqnarray*}
\frac{\Delta Y}{\Delta X}&=&\frac{Y_{i+1,j+1}-Y_{i,j}}{X_{i+1,j+1}-X_{i,j} }
= \frac{ \R \Delta X +(\D-\R) }{ \Delta X}
= \R + \frac{ (\D-\R) }{ \Delta X}\\[2mm]
&=& \R + \frac{ (\D-\R) (\R -\C) }{ (\D-\C)-(\D-\R)}
= \R + \frac{ (\D-\R) (\R -\C) }{ \R-\C}
= \D .
\end{eqnarray*}
Thus, the ordered pairs that appear on any front diagonal are
on a line that has slope $\D$. They account for all of the lines in $\Res(\D)$
since every ordered pair in $\zed_n$$\times$$\zed_n$ occurs
exactly once among the cells of $M$.
Observe that
\begin{eqnarray*}
\frac{\Delta Y }{ \Delta X}&=&\frac{ Y_{i-1,j+1}-Y_{i,j} }{ X_{i-1,j+1}-X_{i,j} }
= \frac{ \R \Delta X -(\D-\R) }{ \Delta X}
= \R - \frac{ (\D-\R) }{ \Delta X}\\[2mm]
&=& \R - \frac{ (\D-\R) (\R -\C) }{ -(\D-\C)-(\D-\R)}
= \R + \frac{ (\R-\D) (\R -\C) }{ 2\D-\R-\C}\\[2mm]
&=& \frac{\R\D + \C\D -2\R\C }{ 2\D-\R-\C}
= \B .
\end{eqnarray*}
Thus the ordered pairs that appear on any back diagonal are
on a line that has slope $\B$. They account for all of the lines in $\Res(\B)$
since every ordered pair in $\zed_n \times \zed_n$ occurs
exactly once among the cells of $M$.

\medskip

\noindent{\emph{Case 2: $\R = \infty$}}.
In this case,
\begin{eqnarray*}
L_{\R,\D,i}&=&\{(i,Y):Y \in \zed_n\}\mbox{ and}
\end{eqnarray*}
and
\begin{eqnarray*}
L_{\C,\D,j}&=&\{(X,Y):Y=\C X+(\D-\C)j\}.
\end{eqnarray*}
The intersection of these two lines is $(X_{ij},Y_{ij})$ where
\begin{eqnarray*}
X_{ij} &=& i \\[2mm]
Y_{ij} &=& \C X_{ij} + (\D-\C) j 
= \C i + (\D-\C) j
\end{eqnarray*}
Observe that
\begin{eqnarray*}
\frac{\Delta Y }{ \Delta X}&=&\frac{ Y_{i+1,j+1}-Y_{i,j} }{ X_{i+1,j+1}-X_{i,j} }
= \frac{ \C \Delta X +(\D-\C) }{ \Delta X}
= { \C +(\D-\C) }
= \D .
\end{eqnarray*}
Thus the ordered pairs that appear on any front diagonal are
on a line that has slope $\D$. They account for all of the lines in $\Res(\D)$
since every ordered pair in $\zed_n$$\times$$\zed_n$ occurs
exactly once among the cells of $M$.
Observe that
\[
\frac{\Delta Y}{\Delta X}=\frac{Y_{i-1,j+1}-Y_{i,j}}{ X_{i-1,j+1}-X_{i,j}}
= \frac{\C\Delta X-(\D-\C)}{\Delta X}
= \C-\frac{\D-\C}{\Delta X}
= 2\C-\D
= \B .
\]
Thus the ordered pairs that appear on any back diagonal are
on a line that has slope $\B$. They account for all of the lines in $\Res(\B)$
because every ordered pair in $\zed_n$$\times$$\zed_n$ occurs
exactly once among the cells of $M$.

\medskip

\noindent{\emph{Case 3: $\C = \infty$}}.
This case is the transpose of Case 2 (interchange $\R$ and $\C$ and
repeat the argument in Case 2).

\medskip

\noindent{\emph{Case 4: $\D = \infty$}}.
In this case,
\[
L_{\R,\D,i}=\{(X,Y):Y=\R X+i\}
\]
and
\[
L_{\C,\D,j}=\{(X,Y):Y=\C X+j\}.
\]
The intersection of these two lines is $(X_{ij},Y_{ij})$ where
\begin{eqnarray*}
X_{ij} &=& \frac{j-i}{\R-\C}\\
Y_{ij} &=& \R X_{ij}+j = \frac{\R(j - i)}{\R-\C} +j
\end{eqnarray*}
Observe that
\begin{eqnarray*}
\frac{\Delta Y}{\Delta X}&=&\frac{Y_{i+1,j+1}-Y_{i,j}}{ X_{i+1,j+1}-X_{i,j}}
= \frac{1}{\Delta X}
= \frac{1}{ 0}
= \D .
\end{eqnarray*}
Thus the ordered pairs that appear on any front diagonal are
on a line that has slope $\D$. They account for all lines in $\Res(\D)$
since every ordered pair in $\zed_n \times \zed_n$ occurs
exactly once among the cells of $M$.
Observe that
\begin{eqnarray*}
\frac{\Delta Y }{ \Delta X}&=&\frac{ Y_{i-1,j+1}-Y_{i,j} }{ X_{i-1,j+1}-X_{i,j} }
= \frac{\R\Delta X-1}{\Delta X}
= \R - \frac{1}{\Delta X}\\
&=& \R - \frac{\R-\C}{ 2}
= \frac{\R+\C }{ 2}
= \B .
\end{eqnarray*}
Thus the ordered pairs that appear on any back diagonal are
on a line that has slope $\B$. They account for all lines in $\Res(\B)$
because every ordered pair in $\zed_n \times \zed_n$ occurs
exactly once among the cells of $M$.
\end{proof}
\frenchspacing
To construct a union jack designs of prime order $n$, 
we need matrices $M_i = M_{\R_i,\C_i,\D_i}$
for $i$$=$$1,2,\ldots,(n+1)/4$ so that
$\{ \{\R_i,\C_i,\D_i,\B_i\}{:\;}i=1,2,\ldots,(n+1)/4 \}$
partitions $\P_n$, where $\B_i = \B_{\R_i,\C_i,\D_i}$.
For each $\A \in \P_n$,
$\B_{-\A,\frac{1}{\A},\frac{\A+1}{ \A-1}}=\frac{1-\A}{ 1+\A}$.
Thus for each $\A \in \P_n$,
$M_{\A} = M_{-\A,\frac{1}{\A},\frac{\A+1}{\A-1}}$
handles the set of slopes
${\cal S}_\A = \{-\A,\frac{1}{\A},\frac{\A+1}{\A-1},\frac{1-\A}{1+\A}\}$.
The condition that $n \equiv 3 \pmod{4}$ implies that $-1$ is not a square modulo
 $ n$.
Thus, ${\cal S}_\A$ consists of four distinct elements.
When $\A=\infty$, this set is ${\cal S}_\infty = \{\infty,0,1,-1\}$.
Consider the subgroup
$H{=}\left\{
f_\M(X){=}\frac{\M X + 1 }{ -X + \M}{:\;}\M \in \P_n
\right\}$
of \PGL{2}{n}. This subgroup is transitive on $\P_n$,
because $f_{-\A}(\infty) = \A$.
Furthermore,
\begin{eqnarray*}
f_\A({\cal S}_\infty)&=&
\{f_\A(\infty),f_\A(0),f_\A(1),f_\A(-1)\}\\
&=&\left\{-\A,\frac{1}{\A},\frac{\A+1}{ \A-1},\frac{1-\A}{ 1+\A}\right\}
= {\cal S}_\A .
\end{eqnarray*}
Thus the orbit of ${\cal S}_\infty$
under $H$ is
$\{ {\cal S}_\A : \A \in \P_n \}$.
The stabilizer of ${\cal S}_\infty$ in $H$ is
\[
K=\left\{ {f_\infty, f_0,f_1,f_{-1}} \right\}
=\left\{
{
X \mapsto X,
X \mapsto \frac{-1 }{ X},
X \mapsto \frac{1+X }{ 1-X},
X \mapsto \frac{X-1 }{ X+1}
} \right\}.
\]
Hence the number of distinct items in the orbit
$\{ {\cal S}_\A : \A \in \P_n \}$
is $|H|/|K| = (n+1)/4$. The transitivity of $H$ shows that they
partition $\P_n$.
As a result, we may choose $(n+1)/4$ 
elements $\A_1,\A_2,\ldots,\A_{(n+1)/4}{\in}\P_n$
so that the $(n{+}1)/4$ matrices $M_\A$ form a union jack 
design of order $n$,
when $n \equiv 3 \pmod{4}$. Consequently, we have:
\nonfrenchspacing
\begin{theorem}
If $n \equiv 3 \pmod{4}$ is a prime, then there exists a union
jack design of order $n$.
\end{theorem}


\section{A Dual Formulation}

Suppose a lattice square, RCF, or union jack design of order $n$ exists.
Each defines a set of $n+1$ resolution classes $\Res_0, \dots, \Res_n$
on $n^2$ points so that every pair of points occurs in exactly one block of
exactly one class; hence the design is an affine plane. The association of
resolution classes with the arrays from which they arose partitions the
set of resolution classes $\Res_0, \dots, \Res_n$ into $\frac{n+1}{s}$ sets
of $s$ resolution classes each, where $s = 2,3$, or 4, depending on whether
the underlying design is a lattice square, RCF, or union jack design.

Given\,the\,affine\,plane\,on%
\,elements\,$X$\,with\,lines\,$\mathcal{B}$,\,
define\,a\,dual\,design\,$(V{,}\mathcal{D})\,$where 
%
$V = \{ v_B : B \in {\cal B}\}$ and
${\cal D}{=}\{D_x{:\,}x \in X\}$, by placing $v_B$ in block $D_x$ whenever
$x \in B$.
(Elements of the affine plane become lines of the dual and lines of the plane become elements
of the dual.)
So $|D_x| = n+1$ for all $x \in X$.
Moreover, from each resolution class $\Res_i$, we can define a {\em group}
of points $G_i = \{v_B : B \in \Res_i \}$. Two points from the same group
do not appear together in a block of $\cal D$, but two points from
different groups appear together in exactly one block of $\cal D$. Hence
$(V,{\cal D})$ is a {\em transversal design} $TD(n+1,n)$
(see \cite{BJL} for an extensive discussion of transversal designs).

The partition of resolution classes into sets of size $s$ corresponds to a
partition of the groups of a $TD(n{+}1,n)$, and hence to a collection of
$TD(s,n)$s. Each such $TD(s,n)$ must be obtained by applying the same
dualization to a single array from the lattice square, RCF, or union jack design.

There is essentially only one $TD(2,n)$, and hence every $TD(n+1,n)$ admits
a partition into appropriate $TD(2,n)$s. However, when we turn to RCF and
union jack 
designs, the picture is more complex. For RCF designs, a careful
examination of the dual of a single array shows that it is a $TD(3,n)$
isomorphic to one with points $\zed_n \times \{0,1,2\}$; groups
$\zed_n{\times}\{i\}$ for $i{\in}\{0,1,2\}$, and
blocks $\{\{(i,0),(j,1),(i-j,2)\}{:\,} i,j \in \zed_n\}$.\,Equivalently,\,this 
transversal design is the one obtained from the addition
table of the cyclic group $\zed_n$.
In the same manner, the dual of a single array in a union jack design
is isomorphic to one with points $\zed_n \times \{0,1,2,3\}$, groups
$\zed_n \times \{i\}$ for $i \in \{0,1,2,3\}$, and
blocks $\{\{(i,0),(j,1),(i-j,2),(i+j,3)\} : i,j \in \zed_n\}$.

If an affine plane is to underlie an RCF or union jack design, a
necessary condition is that the corresponding $TD(n+1,n)$ contain a
$TD(3,n)$ isomorphic to the cyclic one.
Immediately we see that the planes arising from the finite field
cannot underlie such designs when their order is a prime power but not
a prime. Indeed, in this case, every $TD(3,n)$ in the $TD(n+1,n)$
when $n = p^\alpha$ is isomorphic to that arising from $\zed_p \times \zed_p \times \cdots \times \zed_p$, the elementary Abelian group, rather than from
the cyclic group $\zed_{p^\alpha}$.

There exist numerous planes\,of\,prime power order which\,do\,not arise from the finite 
field,\,and so it is possible that some other class\,of\,affine planes
could be used to produce RCF\,or\,union jack designs.\,We do not know\,of\,any other examples
of affine planes that can be used, but
we cannot exclude the possibility since the classification of all such planes is not complete.
Nevertheless, one natural class of planes to explore, the
translation planes, can be eliminated from consideration using basic facts
about the relation between translation planes and `quasifields' (see
\cite{Kallaher}). All translation planes arise from quasifields, and all
quasifields have an additive group which is elementary Abelian. It follows
directly that the corresponding $TD(n{+}1,n)$ cannot contain a $TD(3,n)$ of
the cyclic type, and hence that translation planes do not underlie 
RCF or union jack designs. 

\bigskip

\section*{Acknowledgments.} 
This research was supported by ARO grant DAAG55-98-1-0272 (Colbourn),
NSA grant MDA904-97-1-0072 (Kreher),
NSF grant DMS-9753244 (Lamken),
and USDOE contract W-7405-ENG-35 (Torney).
Thanks to Rick Wilson for making the observation about translation planes.
We also thank the Los Alamos Center for Nonlinear Studies.

%XXX

\small
\begin{thebibliography}{99}

%\setlength{\parsep}{0pt}
\setlength{\itemsep}{0mm}
\bibitem{BBKT}
D.J. Balding, W.J. Bruno, E. Knill, and D.C. Torney,
A comparative survey of nonadaptive pooling designs, In:
{Genomic Mapping and DNA Sequencing}, IMA 81 (1996), pp. 133-154.
\bibitem{BJL}
T. Beth, D. Jungnickel and H. Lenz, {Design Theory},
Cambridge University Press, Cambridge, 1986.
\bibitem{c&c}
W. G. Cochran and G. M. Cox,
{Experimental Designs},
John Wiley \& Sons, Inc., New York, 1950, pp. 346-369.
\bibitem{handbook}
C.J. Colbourn and J.H. Dinitz, Eds.,
{The CRC Handbook of Combinatorial Designs},
CRC Press, Boca Raton, 1996.
\bibitem{federer}
W. T. Federer,
{Experimental Design},
Macmillan \& Co., New York, 1955, pp. 378-388.
\bibitem{f&w}
W. T. Federer and J. Wright,
Construction of lattice square designs,
{Biom. J.} {\bf 1} (1988) 77-85.
\bibitem{Kallaher}
M. Kallaher, Translation planes, In: {Handbook of Incidence
Geometry}, F. Buekenhout, ed., Elsevier North-Holland, 1995, pp. 137-192.
\bibitem{KBT}
E. Knill, D.J. Balding, and D.C. Torney,
Interpretation of pooling experiments using the Markov chain Monte Carlo method,
{J. Comput. Biol.} {\bf 3} (1996) 395-406.
\bibitem{Letal} 
K. Longmire {et al.}, 
Semi-automated high precision pooling of large genomic libraries using the Robbins hydra,
{Biotechniques}, in preparation.
\bibitem{PPBT}
J.K. Percus, D.E. Percus, W.J. Bruno, and D.C. Torney,
Asymptotics of pooling design performance,
{J. Applied Prob.}, to appear.
\bibitem{Rag71}
D. Raghavarao, {Constructions and Combinatorial Problems in Design
of Experiments}, John Wiley \& Sons, New York, 1971.
\bibitem{yates}
F. Yates,
A further note on the arrangement of variety trials:
quasi-Latin squares,
{Ann. Eugenics} {\bf 7} (1937), 319-331.
\end{thebibliography}

\end{document}


