\documentclass[10pt]{amsart}
\usepackage{epsfig,enumerate,amssymb}
\usepackage{amsmath}
\usepackage{amsthm}

\def\Z{{\mathbb Z}}
\def\Ff{{\mathbb F}}
\def\F{{\mathcal F}}
\def\G{{\mathcal G}}
\def\B{{\mathcal B}}

\newcommand\header[1]{\bigskip\noindent{\bf #1.}}
\newcommand\subheader[1]{\medskip\noindent{\em #1.}}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{main}{Main~Theorem}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remark}{Remark}
\newtheorem{example}{Example}

\theoremstyle{definition}
\theoremstyle{remark}
\newtheorem*{notation}{Notation}
\numberwithin{equation}{section}

\newcommand{\vect}[1]{\boldsymbol{#1}}



\title{Fractional factorial designs of strength 3 and small run sizes}
\author{Andries E. Brouwer, Arjeh M. Cohen, Man V.M. Nguyen}


\date{November 1, 2003}
\keywords{ Fractional factorial designs, orthogonal arrays. }

\begin{document}


\begin{abstract}
All mixed (or asymmetric) orthogonal arrays of strength 3
with run size at most 64 are determined.
\end{abstract}

\maketitle

\section{Introduction}
In this paper we study mixed orthogonal arrays of strength $3$.  Let
$s_1,s_2, \ldots, s_k$ be a list of natural numbers, and for each
$i$, let $Q_{s_i}$ be a set of size $s_i$.
For natural numbers $t$, $N$, a multiset $\F$ of size $N$ whose
elements are from $Q_{s_1}\times Q_{s_2}\times\cdots\times Q_{s_k}$
is called an {\em orthogonal array of strength} $t$, notation
$OA(N, s_1,s_2, \cdots, s_k, t)$, if $t \le k$, and,
for every index set $I \subseteq \{1, \cdots, k\}$ of size at most $t$,
each row of $\prod_{i\in I} Q_{s_i}$ occurs equally often
in the projection of $\F$ onto the coordinates indexed by $I$.

We refer to the elements of $\F$ as {\em runs}, so $N$ is the number of runs
of $\F$, also called its {\em run size}. The coordinates of
$Q_{s_1}\times Q_{s_2}\times\cdots\times Q_{s_k}$ are called {\em factors},
so $k$ is the number of factors.
Moreover, $s_i$ is called the {\em level} of the factor $i$.  Instead of
$s_1, s_2, s_3, \ldots$ we also write $2^a\cdot 3^b\cdot 4^c\cdots$,
where the exponents $a,b,c,\cdots$ indicate the number of factors
at level 2, 3, 4, etc.
An orthogonal array is called {\em trivial} if it contains each
element of $Q_{s_1}\times Q_{s_2}\times\cdots\times Q_{s_k}$
the same number of times.

Orthogonal arrays of strength 2 have been studied extensively.
In this paper, we study the case of strength $t = 3$.
We restrict ourselves mainly to $N \le 64$. 

\begin{theorem}\label{main-thm}
For every set of parameters $N, s_1,s_2, \cdots, s_k, t$
with $t = 3$ and $N \le 64$ such that an orthogonal array
$OA(N, s_1,s_2, \cdots, s_k, t)$ exists, we construct at
least one such array. More precisely, if $k = 3$ such an
array is trivial, and if $k > 3$ a construction is indicated
in Table \ref{tab-1}.
\end{theorem}

Of course the existence of $OA(N, s_1,s_2, \cdots, s_k, t)$
does not depend on the ordering of the parameters $s_j$,
and we can take them in non-decreasing order if we wish.

\begin{table}
\begin{tabular}{|l|l|l|c|c|}
\hline
 N& Levels              & Existence     & Construction & Nonexistence   \\
\hline
8 & $2^a$               & $a \le 4$     &  (H) & \\
16& $2^a \cdot 4$       & $a \le 3$     &  (M) & \\
16& $2^a$               & $a \le 8$     &  (H) & \\
24& $2^a \cdot 6$       & $a \le 3$     &  (M) & \\
24& $2^a \cdot 3$       & $a \le 4$     &  (M) & $a=5$ \\
24& $2^a$               &   $a \le 12$  &  (H) & \\
27& $3^b$               &   $b \le 4$   &  (L) & $b=5$ \\
32& $2^a \cdot 8$       &   $a \le 3$   &  (M) & \\
32& $2^a \cdot 4^2$     &   $a \le 4$   &  (AD) & \\
32& $2^a \cdot 4$       &   $a \le 7$   &  (M) & \\
32& $2^a$               &   $a \le 16$  &  (H) & \\
36& $2^2 \cdot 3^2$     &               &  (T) & \\
40& $2^a \cdot 10$      &   $a \le 3$   &  (M) & \\
40& $2^a \cdot 5$       &   $a \le 6$   &  (X$_1$) & $a=7$ \\
40& $2^a$               &   $a \le 20$  &  (H) & \\
48& $2^a \cdot 12$      &   $a \le 3$   &  (M) & \\
48& $2^a \cdot 4\cdot 6$&   $a \le 2$   &  (M) & $a=3$ \\
48& $2^a \cdot 6$       &   $a \le 7$   &  (M) & \\
48& $2^a \cdot 3\cdot 4$&   $a \le 4$   &  (X$_2$) & $a=5$ \\
48& $2^a \cdot 4$       &   $a \le 11$  &  (M) & \\
48& $2^a \cdot 3$       &   $a \le 9$   &  (X$_3$) & $a=10$ \\
48& $2^a$               &   $a \le 24$  &  (H) & \\

54& $3^b \cdot 6$       &  $b \le 3$    &  (M) & $b=4$ \\
54& $2^a \cdot 3^b$     &  $a \le 1$, $b \le 5$ & (X$_4$) & $(a,b)=(0,6)$\\
56& $2^a \cdot 14$      &  $a \le 3$    &  (M) & \\
56& $2^a \cdot 7$       &  $a \le 6$    &  (J) & $a=7$ \\
56& $2^a$               &  $a \le 28$   &  (H) & \\
60& $2^2 \cdot 3\cdot 5$&               &  (T) & \\
64& $2^a \cdot 16$      &   $a \le 3$   &  (M) & \\
64& $2^a \cdot 4\cdot 8$&   $a \le 4$   &  (M) & \\
64& $2^a \cdot 8$       &   $a \le 7$   &  (M) & \\
64& $4^c$               &   $c \le 6$   &  (L) & \\
64& $2^a \cdot 4^5$     &   $a \le 2$   &  (S) & $a=3$ \\
64& $2^a \cdot 4^4$     &   $a \le 6$   &  (X$_5$) & \\
64& $2^a \cdot 4^3$     &   $a \le 8$   &  (S) & $a=9$ \\
64& $2^a \cdot 4^2$     &   $a \le 12$  & (AD) & \\
64& $2^a \cdot 4$       &   $a \le 15$  &  (M) & \\
64& $2^a$               &   $a \le 32$  &  (H) & \\
\hline
\end{tabular}
\caption{Parameters of orthogonal arrays of strength 3 with $N\le64$.}
\label{tab-1}
\end{table}

We prove the main theorem in three parts.  In Section \ref{S:basic},
we recall known facts, establish some upper bounds on the parameters
of a strength 3 orthogonal array with run size at most 64, and provide
further basic material. In Section \ref{S:feasiblepars} we determine
the feasible parameter sets. In Section \ref{S:existencecases}, we provide
explicit constructions for all cases mentioned in Table \ref{tab-1}. In
Section \ref{S:nonexistence}, we give the non-existence proof for
parameters not appearing in the table.

We briefly explain the table. In the second and third column, a set of
 levels $2^a3^b4^c\cdots$ is specified for which there exists an
 orthogonal array of strength 3 and run size $N$ as indicated in the
 first column. In the fourth column we give a reference to a construction.
 In the fifth column we give references to nonexistence proofs.

 Appendix II lists some of the obtained arrays.
 We use the terms ``factor'' and ``column''; ``fractional design''
 and ``array'' alternatively in the whole paper.

\newpage
\section{Basic facts}
\label{S:basic}
 We start by fixing some notation and recalling well-known results
 which will be used throughout the paper.

 \subsection{Taking the derived design}

\begin{proposition}
  Let $k \ge t \ge 1$.
  From an orthogonal array $OA(N, s_1,s_2, \cdots, s_k, t)$, we find,
  for each choice of column $j$ ($1 \le j \le k$) and each choice of
  symbol $s \in Q_{s_j}$, an orthogonal array
  $OA(N/s_j, s_1, \cdots, s_{j-1},s_{j+1}, \cdots, s_k, t-1)$
  by taking the runs that have an $s$ in the $j$-th position,
  and deleting that coordinate position.
\end{proposition}

\begin{proof}
  This is immediately clear from the definition.
\end{proof}

 \subsection{Rao's generalized bound}

 We recall the following well-known result. Its proof can be found in
  \cite{Wiebe}.


\begin{theorem}  [Rao's generalized bounds for mixed orthogonal arrays]
 \label{T:Raobounds}  \hfill

  Let $k \ge t \ge 1$, and
  assume an orthogonal array $OA(N, s_1,s_2, \cdots, s_k, t)$ exists.
   \begin{itemize}
   \item If t is even, then
       \begin{equation} \label{Rao1}
           N \geq \sum_{j=0}^{t/2} \sum_{|I|=j} \Pi_{i \in I} (s_i-1).
       \end{equation}

   \item If $t$ is odd, then a lower bound for $N$ is found by applying
         the above bound to the derived design
         $OA(N/s_k, s_1,s_2, \cdots, s_{k-1}, t-1)$, where $s_k$ is the
         largest among the $s_j$. \label{Rao2}
 \end{itemize}
\end{theorem}


We'll need this result for $t = 2$ and $t = 3$.
Let us give the explicit form of the above bound in case $t = 2$.

 \begin{corollary}  [Rao's bound when $t=2$]  \label{L:Rao1}  \hfill

 Assume an orthogonal array of the form $OA(N, s_1,s_2, \cdots, s_k, 2)$
 exists. Then
      \begin{equation}
          N \geq 1 + \sum_{i=1}^k (s_i - 1) .
      \end{equation}
 \end{corollary}

For instance, an $OA(N, 2.3^5, 3)$ has derived design
$OA(N/3, 2.3^4, 2)$, so that $N/3 \geq 1 + 4.(3-1) + (2-1) = 10$,
that is, $N \geq 30$.

These bounds are very well known. It is possible to derive additional
information in case equality holds.

 \begin{proposition}\label{raoequality}
 Let $\F$ be an $OA(N, s_1,s_2, \cdots, s_k, 2)$ with $N = 1 + \sum (s_i - 1)$.
 Then for any two runs we have $\sum_{j \in J} s_j = k-1$, where $J$ is the
 set of columns where the two runs agree.
 \end{proposition}

A proof is given in Appendix I.

\subsection{Divisibility condition for the run size}

  For any orthogonal array $\F$, the fact that derived designs exist
  implies a divisibility condition for the run size of $\F$.

  \begin{lemma}
   Let $k \ge t \ge 0$.
   In an  $OA(N, s_1,s_2, \cdots, s_k, t)$, the run size $N$
   is divisible by the least common multiple {\rm (lcm)}
   of all numbers $ \prod_{i \in I} s_i $  where $|I| = t$.
  \end{lemma}

  \begin{proof}
   This says that the $t$ times derived design has an integral run size.
  \end{proof}

 For example, in an $OA(N, 3^5.2^1, 3)$, the run size $N$ must be
 a multiple of
 $\rm{lcm}(3 \cdot 3 \cdot 3, 2 \cdot 3 \cdot 3) = 54$.

\subsection{Strength 3 transversal designs}
Orthogonal arrays are equivalent to trans\-versal designs.
Here the version appropriate for mixed arrays.

\begin{definition} \hfill

A {\em transversal design} (TD) of {\em strength} $t$,
 is a triple ($X, \G, \B$), where $X$ is a set of points;
 $\G$ is a  partition of  $X$ into $\textit{groups}$;
 and  $\B$ is a collection of subsets of $X$ called
 $\textit{blocks}$ such that:
 \begin{enumerate}
  \item $t \le |\G|$,
  \item every block meets every group in precisely one point,
  \item for every choice of $t$ distinct groups, all $t$-sets
        meeting each of those groups in precisely one point
        are contained in the same number of blocks.
 \end{enumerate}

\end{definition}

 If there are $e_i$ groups of size $s_i$, $i=1,\cdots, k$, the group type
 of $\G$ is defined to be the list $T := [s_1^{e_1}, \cdots, s_k^{e_k}]$.
 Notice that a mixed orthogonal array $OA(N, s_1^{e_1} \cdots s_k^{e_k}, t)$
 is equivalent to a transversal design of strength $t$ with group type
 $[s_1^{e_1}, \cdots, s_k^{e_k}]$ and with $N$ blocks.

 The ``factors'' (columns) and the ``runs'' (rows) in orthogonal arrays
 are ``groups'' and ``blocks'' in transversal designs.

 For instance, an array  $OA(72, 2^5. 3^2, 3)$ can be viewed as a transversal
 design on a set $X$ with 16 points, $G$ consists of 7 groups,
 $B$ has 72 blocks; the frequency of (2,3,3)-level triples is 4,
 of (2,2,3)-level triples is 6, and of (2,2,2)-level triples is 9.

\section{Enumeration of feasible parameters} \label{S:feasiblepars}

 First, we have to find all reasonable parameters for putative
 mixed orthogonal arrays, then we have to construct the arrays
 that exist, and finally we have to show nonexistence in the
 cases where no array exists.

 Let us say that a parameter set is {\em reasonable} if it satisfies
 the divisibility conditions and the Rao bound.
 Let us say that a parameter set $OA(N, s_1,s_2, \cdots, s_k, t)$
 is {\em trivial} if $k = t$.
 (Then a design with these parameters is necessarily trivial.
 Parameter sets with $\prod s_i | N$ allow a trivial design,
 but there may also be nontrivial solutions.)
 We find the following list.

\begin{lemma}
 The nontrivial reasonable parameter sets for mixed orthogonal arrays
 of strength 3 and run size at most 64 are
 \begin{enumerate}
 \item $OA(4m, 2^a, 3)$, $4 \le a \le 2m$, $m$ even, $2 \le m \le 16$,
 \item $OA(4m, 2^3.m, 3)$, $m$ even, $2 \le m \le 16$,
 \item $OA(8m, 2^a.m, 3)$, $3 \le a \le 7$, $3 \le m \le 8$,
 \item $OA(8m, 2^a.4.m, 3)$, $2 \le a \le 4$, $m$ even, $4 \le m \le 8$,
 \item $OA(9m, 3^b.m, 3)$, $3 \le b \le 4$, $m = 3,6$,
 \item $OA(36, 2^2.3^2, 3)$,
 \item $OA(48, 2^a.3, 3)$, $3 \le a \le 15$,
 \item $OA(48, 2^a.3.4, 3)$, $2 \le a \le 9$,
 \item $OA(48, 2^a.4, 3)$, $3 \le a \le 11$,
 \item $OA(54, 2^a.3^b, 3)$, $a = 0,1$, $b \ge 1$, $a+b \ge 4$, $a+2b \le 19$,
 \item $OA(60, 2^2.3.5, 3)$,
 \item $OA(64, 2^a.4^c, 3)$, $a \ge 0$, $c \ge 1$, $a+c \ge 4$, $a+3c \le 18$,
 \end{enumerate}

\end{lemma}

We see that Table \ref{tab-1} is complete, in the sense that it
lists, for each reasonable nontrivial parameter set, either
a construction or a nonexistence proof.

The following section has the constructions, the section after that
the nonexistence proofs.

\section{Constructions}  \label{S:existencecases}

 \subsection{General constructions}
  \subsubsection{Trivial designs \rm{(T)}} \hfill

  If $\prod s_i | N$, then  a trivial design (a multiple of the full design)
  exists.
  This settles arrays $OA(36, 2^2.3^2, 3)$ and $OA(60, 2^2.3.5, 3)$.

  Note that in these cases also nontrivial designs may exist.
  For example, up to isomorphism there are precisely 3 nonisomorphic
  $OA(36, 2^2.3^2, 3)$ and 6 nonisomorphic $OA(60, 2^2.3.5, 3)$.

  \subsubsection{Hadamard construction \rm{(H)}} \hfill

  If $H$ is a Hadamard matrix of order $k$, $4 | k$, then
  {\scriptsize{$\left(\begin{array}{c} H \\ -H \\ \end{array}\right)$}}
  is an orthogonal array $OA(2k, 2^k, 3)$.

  Conversely, every $OA(2k, 2^k, 3)$ is (equivalent to one) found this way.

  \subsubsection{Taking multiples \rm{(M)}} \hfill

  Given a design $OA(N, s_1, s_2, \cdots, s_k, t)$,
  we make an $OA(sN, s s_1, s_2, \cdots, s_k, t)$
  for any positive integer $s$ by taking $s$ copies of the design,
  each copy with its own choice of symbols in the first column, and
  identical otherwise.
  Arrays $OA(8s, 2^3.2s, 3)$ are found in this way from $OA(8,2^4,3)$.
  Also, $OA(24, 2^4.3, 3)$ is found in this way from
  $OA(8, 2^4.1, 3)$, that is, $OA(8, 2^4, 3)$.

  \subsubsection{Juxtaposition \rm{(J)}}  \hfill

  More generally, given an $OA(N', s', s_2, \cdots, s_k, t)$
  and an $OA(N'', s'', s_2, \cdots, s_k, t)$ we can construct an
  $OA(N'+N'', s'+s'', s_2, \cdots, s_k, t)$ by putting one above the other,
  making sure that both use disjoint symbol sets in the first column,
  and identical symbol sets in the other columns.
  In this way one obtains $OA(56,2^a.7,3)$ from $OA(40,2^a.5,3)$ and
  $OA(16,2^{a+1},3)$ for $a \le 6$.

  \subsubsection{Linear codes \rm{(L)}}  \hfill

  A $[n,k,d]_q$ code is a linear code of word length $n$, dimension $k$,
  and minimum distance $d$. The code words of the dual code (that has
  dimension $n-k$) form an $OA(N, q^n, d-1)$ with $N = q^{n-k}$.
  In particular, the $[4,1,4]_3$ repetition code gives an $OA(27,3^4,3)$,
  and the $[6,3,4]_4$ hexacode gives an $OA(64, 4^6, 3)$.

% \subsubsection{Additive codes \rm{(A)}}  \hfill

  \subsubsection{Split \rm{(S)}}  \hfill

  Given an $OA(N, st, s_1, s_2, \cdots, s_k, t)$, we can
  make an $OA(N, s, t, s_1, s_2, \cdots, s_k, t)$ by replacing the
  symbols in $Q_{st}$ by those of $Q_s \times Q_t$.
  In particular, a 4-level column can be split into two 2-level columns,
  and a 6-level column can be split into a 2-level and a 3-level column.

 \subsubsection{Agrawal-Dey construction \rm{(AD)}}  \hfill

  Agrawal \& Dey \cite{Agrawal} construct an $OA(8m, 4^2.2^{2m-4}, 3)$
  given a Hadamard matrix of order $m \ge 4$.
  This yields $OA(32, 2^4.4^2, 3)$ and $OA(64, 2^{12}.4^2, 3)$.
  See also Gupta \& Nigam \cite{Gupta}.

% \newpage
 \subsection{Explicit constructions}

  \subsubsection{$OA(40, 2^6.5, 3)$ \rm{(X$_1$)}}  \hfill

  Let $M$ be the binary matrix 
\begin{equation}
 \begin{array} {llllll}
0 &0 &0 &0 &0 &1 \\
1 &1 &1 &0 &0 &1 \\
1 &0 &0 &0 &1 &0 \\
0 &1 &1 &0 &1 &0 \\
0 &0 &1 &1 &0 &0 \\
1 &1 &0 &1 &0 &0 \\
1 &0 &1 &1 &1 &1 \\
0 &1 &0 &1 &1 &1
 \end{array}
\end{equation}
  and let $M_i$ $(0 \le i \le 4)$ be the matrix obtained from $M$
  by fixing the first column and cyclically permuting the remaining
  five $i$ times. Let $N_i$ be the matrix obtained from $M_i$ by
  adding a constant column of all $i$'s.
  Construct an $OA(40, 2^6.5, 3)$ by juxtaposing the five matrices $N_i$.

  \subsubsection{$OA(48, 2^4.3.4, 3)$ \rm{(X$_2$)}}  \hfill

  See the explicit matrix given in Appendix II.
  There are precisely 19 such designs.

  \subsubsection{$OA(48, 2^9.3, 3)$ \rm{(X$_3$)}}  \hfill

  See the explicit matrix given in Appendix II.
  There are precisely 3 such designs.

  \subsubsection{$OA(54, 2.3^5, 3)$ \rm{(X$_4$)}}  \hfill

  See the explicit matrix given in Appendix II.
  There are precisely 4 such designs.

  \subsubsection{$OA(64, 2^6.4^4, 3)$ \rm{(X$_5$)}}  \hfill

  Let $A$ and $B$ be the subsets $\{0,1\}$ and $\{2,3\}$ of
  the cyclic group $\Z_4$ of residues mod 4.
  Take $Q_4 = \Z_4$ and $Q_2 = \{A,B\}$.
  One obtains an $OA(64, 2^6.4^4, 3)$ by taking in
  $Q_2^6 \times Q_4^3$ the vectors
  $(S_1,S_2,S_3,S_4,S_5,S_6,x_1,x_2,x_3,x_4)$ such that
  $x_1 + x_2 + x_3 + x_4 = 0$, and $\sum_{j=1}^4 a_j^{(i)} x_j \in S_i$
  $(1 \le i \le 6)$, where the $a^{(i)}$ are the six vectors
  $(0,1,2,3)$, $(0,1,3,2)$, $(0,2,1,3)$, $(0,2,3,1)$, $(0,3,1,2)$, $(0,3,2,1)$.

  This is the unique design with these parameters.


\section{Nonexistence} \label{S:nonexistence}

\subsection{Nonexistence of $OA(24, 2^5.3, 3$)} \label{SS:nonexist2531}

Suppose we have an $OA(24, 2^5.3, 3)$.
Consider the three derived designs at the ternary column:
each is an $OA(8, 2^5, 2)$.

Let there be $n_i$ rows in one of these $OA(8, 2^5, 2)$
that have $i$ coincidences (agreements) with
an arbitrary fixed given binary reference vector. Then

\[  \sum  n_i = 8, \]
\[  \sum  i n_i = 20, \]
\[  \sum  \binom{i}{2} n_i = 20. \]

These three equations have only three possible solutions $(n_i)_{i=0}^5$
in nonnegative integers:

\[ A = [0,1,4,2,0,1] ; \]
\[ B = [1,0,2,4,1,0] ; \]
\[ C = [0,2,2,2,2,0].  \]

For each of the three derived designs we find one of these three
vectors, say $n^{(0)}$, $n^{(1)}$ and $n^{(2)}$. For the original
design with 24 blocks we have an agreement count vector
$t = n^{(0)} + n^{(1)} + n^{(2)}$ that also satisfies

\[  \sum  \binom{i}{3} t_i = 30. \]

Now $\sum \binom{i}{3} n_i$ equals 12, 8, 10 for $n = A,B,C$, respectively.
We see that for each choice of reference vector there are two possibilities:
$\{n^{(0)},n^{(1)},n^{(2)}\} = \{A,B,C\}$ or $n^{(0)}=n^{(1)}=n^{(2)}=C$.

Each time we pick a row of one of the three parts as reference vector
we find a vector $A$ for that part, and hence a vector $B$ for another
part, so that this other part contains the complementary row.
Thus, the design is self-complementary, but none of the three parts
contains a pair of complementary vectors.

Pick the reference vector in one of the parts, so that that part
is of type A. Of the two vectors in the part of type C that agree
in four positions with the reference vector, at least one has its
complement in that same part, contradiction.


\subsection{Nonexistence of $OA(27, 3^5, 3)$} \label{SS:nonexist35}

First proof: an $OA(27, 3^5, 3)$ would be a ternary code
(not necessarily linear) of size 27, word length 5,
and dual distance at least 4, contradicting the Delsarte
linear programming bound.

Second proof: Nonexistence follows from Bush's inequality.
(Suppose one of the runs is $00000$. There are 6 runs
with precisely two 0's in the first two positions. These runs
do not have 0's in the final two positions, and have mutually
distinct tails. But only 4 possible tails are available.)

% Third proof: this violates Bierbrauer's ineq.


\subsection{Nonexistence of $OA(40, 2^7.5, 3)$ and $OA(56, 2^7.7, 3)$} \label{SS:nonexist2751}

We show nonexistence of $OA(8m, 2^7.m, 3)$ for odd $m$.

There is a unique $OA(8, 2^7, 2)$, constructed, e.g., by taking
the seven characteristic vectors of the lines of the Fano plane
and the all-1 vector. This design has strength 2, and if we
consider three columns, then half of the combinations occur twice
and half of the combinations do not occur at all, so that each
3-symbol pattern occurs an even number of times.
Now consider an $OA(8m, 2^7.m, 3)$.
All $m$ derived designs are $OA(8, 2^7, 2)$, but every 3-symbol pattern
must occur $m$ times. This is impossible if $m$ is odd.


\subsection{Nonexistence of $OA(48, 2^3.4.6, 3)$}

The derived design of an $OA(48, 2^3.4.6, 3)$ at the 4-level column
is an $OA(12, 2^3.6, 2)$. But no such design exists.
More generally we show nonexistence of $OA(4m, 2^3.2m, 2)$ for odd $m$.
Such an array must have $2m$ pairs of rows of which the binary part
is complementary. Look at the $2m$ rows with 0 in the first column.
Of these, $m$ have a 1 in the second column,
and $m$ have a 1 in the third column, so that second and third column
agree in an even number of places in these $2m$ rows.
But if two bits agree, then their complements agree, so
the total number of agreements between second and third column
is divisible by 4. But it is $2m$. Contradiction.


\subsection{Nonexistence of $OA(48, 2^5.3.4, 3)$}

The derived design of an $OA(48, 2^5.3.4, 3)$ at the 4-level column
is an $OA(12, 2^5.3, 2)$. But no such design exists.

Indeed, suppose we have such an array. We build a new array
of dimensions 3 by 5 and symbols in $\{A,B,C\}$.
For each of the three derived $OA(4, 2^5, 1)$ of our $OA(12, 2^5.3, 2)$
we make a row of the new array, by writing $A$ for each column
$(0011)^T$ or $(1100)^T$, $B$ for each column $(0101)^T$ or $(1010)^T$,
and $C$ for each column $(0110)^T$ or $(1001)^T$.

In $OA(4, 2^5, 1)$, if two columns get different symbols, then
every possible pair occurs once. If two columns get the same symbol
then every possible pair occurs an even number of times.

Now the fact that every possible binary pair in $OA(12, 2^5.3, 2)$
occurs 3 times means that every two columns in the new array
differ in 1 or 3 places.

But there is no 3-by-5 ternary array in which every two columns
have an odd distance. The arrays
{\scriptsize $\begin{array}{ccc} AAA \\ AAA \\ ABC \\ \end{array}$}
and
{\scriptsize $\begin{array}{cccc} AABB \\ AABC \\ ABCC \\ \end{array}$}
and
{\scriptsize $\begin{array}{ccc} ABC \\ ABC \\ ABC \\ \end{array}$}
show that the array has at most three columns when there are
three columns pairwise at distance 1, or three columns pairwise
at distance 3, and at most four columns otherwise.


\subsection{Nonexistence of $OA(48, 2^{10}.3,3)$} \hfill

 This follows by exhaustive computer search.


\subsection{Nonexistence of $OA(54, 3^4.6, 3)$} \hfill

 This follows by exhaustive computer search, either directly,
 or by observing that by construction (S) one gets
 $OA(54, 3^5.2, 3)$, and none of the four nonisomorphic such arrays
 allows going back.


\subsection{Nonexistence of $OA(54, 3^6, 3)$} \hfill

 This follows by the Delsarte linear programming bound.
 See also \cite{Hedayat1}.

\subsection{Nonexistence of $OA(64, 2^3.4^5, 3)$} \hfill

 Suppose an $OA(64, 2^3.4^5, 3)$ exists. The derived designs at
 a 4-level factor are designs $OA(16, 2^3.4^4, 2)$, but there is
 a unique such design.

 The unique $OA(16, 2^3.4^4, 2)$ can be obtained from the
 unique $OA(16, 4^5, 2)$ by letting the three groups of size 2
 be the three partitions into two pairs of the group of size 4
 that they replace.

 $OA(16, 4^5, 2)$ can be viewed as the projective plane of order 4
 minus a point $P$, where the groups are the five lines on $P$,
 and the blocks are the 16 lines not on $P$.
 Consequently, $OA(16, 2^3.4^4, 2)$ can be viewed as the affine plane
 of order 4, with the groups being the four lines in one direction $d$
 and the three partitions of the set of directions different from $d$
 into two disjoint pairs.

 Note that parallel lines have the same direction, and hence are incident
 with the same pairs. Now take a run 00000000 of $OA(64, 2^3.4^5, 3)$.
 For each of the five choices of 0 in one of the 4-level columns
 there are three lines parallel to 0000000 in the derived design,
 and each of these starts with 000. Altogether the binary triple 000
 is covered 16 times, but it should be covered only 8 times.

\subsection{Nonexistence of $OA(64, 2^9.4^3, 3)$} \hfill

Consider a design $OA(16, 2^9.4^2, 2)$. It has equality in the Rao bound,
and Proposition \ref{raoequality} tells us that any two rows agree in
precisely 5 places, when agreements in 4-level columns are counted twice.

Now consider $OA(64, 2^9.4^3, 3)$, and without loss of generality
assume that its top row is 00000000000. Then that row has pattern $0^9 0^2$,
9 rows have pattern $(0^3 1^6)(0^2 *^1)$,
27 rows have pattern $(0^5 1^4)(0^1 *^2)$, and
27 rows have pattern $(?^9)(*^3)$, where $*$ denotes any nonzero symbol.

Let there be $m_i$ rows with $i$ zeros in binary columns.
Two rows that agree in a quaternary column have binary parts
at even Hamming distance. Since the graph on the 64 rows
defined by ``agreeing in some quaternary column'' is connected,
it follows that any two binary parts have even Hamming distance,
so that $m_i$ is only nonzero for odd $i$. Also $m_9 \ge 1$. We obtain
$$\sum m_i = 64,$$
$$\sum i m_i = 9.32 = 288,$$
$$\sum \binom{i}{2} m_i = \binom{9}{2}.16 = 576,$$
$$\sum \binom{i}{3} m_i = \binom{9}{3}.8 = 672.$$
This has solution $(m_1,m_3,m_5,m_7,m_9) = (3,18,36,6,1)$ or $(4,14,42,2,2)$.

If $m_9 = 2$ then we have rows say $0^9 000$ and $0^9 111$.
Now the row $?^9 110$ must have both 3 and 5 zeros in binary columns.
Contradiction.

It follows that $(m_1,m_3,m_5,m_7,m_9) = (3,18,36,6,1)$.
Subtract the known part, for the rows that have a 0 in the
quaternary part. They contribute $(0,9,27,0,1)$, so that
$(3,9,9,6,0)$ is contributed by rows without 0 in the quaternary part.

Look at the three rows with precisely one 0. They mutually agree
in at least seven binary positions, hence have no agreements in
quaternary positions, and w.l.o.g. we have the rows
$011111111 111$ and $101111111 222$ and $110111111 333$.
Any row with seven zeros in binary positions has at most three
agreements with each of these three rows, so in its quaternary part
every symbol occurs zero or two times. But 3 is odd, contradiction.

\begin{thebibliography}{9}
 \bibitem{BoseBush} R.C Bose and K.A Bush,
{\it Orthogonal arrays of strength 2 and 3},
Ann. Math. Statistics {\bf 23} (1952) 508 - 524.

 \bibitem{Agrawal} V. Agrawal and A. Dey
{\it Orthogonal resolution-IV designs for some asymmetrical factorials},
Technometrics {\bf 25} (1983) 197-199.

 \bibitem{Wiebe} Wiebe S. Diestelkamp,
{\it Parameter inequalities for orthogonal arrays with mixed levels},
Department of Mathematics, University of Dayton.

 \bibitem{Gupta} V.K. Gupta and A.K. Nigam,
{\it A class of asymmetrical orthogonal resolution IV designs},
J. Statist. Plann. Inf. {\bf 11} (1985) 381-383.

 \bibitem{Hedayat1} A.S. Hedayat, Esther Seiden, John Stufken,
{\it On the maximal number of factors and the enumeration of
3-symbol orthogonal arrays of strength 3},
Journal of Statistical Planning and Inference {\bf 58} (1997) 43-63.

 \bibitem{Hedayat2} A.S. Hedayat, N.J.A Sloane, John Stufken,
{\it Orthogonal Arrays}, Springer, 1999.

 \bibitem{Sloane} N.J.A. Sloane, Hadamard Matrices,
{\tt \verb#http://www.research.att.com/~njas/hadamard/#}.

 \bibitem{CFJWu} C.F.J. Wu,
{\it Nearly orthogonal arrays with mixed levels and small runs},
Technometrics {\bf 34} (1992) 409-422.

 \end{thebibliography}

\newpage
\section*{Appendix I: Proof of Proposition \ref{raoequality}}

The proof of the Rao bound is a very simple dimension argument, but that
does not give additional information in case equality holds.
Let us give a different proof here (for the case $t = 2$),
that yields something for the equality case.

 \setcounter{theorem}{\ref{raoequality}}
 \addtocounter{theorem}{-1}
 \begin{proposition}
 Let $\F$ be an $OA(N, s_1,s_2, \cdots, s_k, 2)$ with $N = 1 + \sum (s_i - 1)$.
 Then for any two runs we have $\sum_{j \in J} s_j = k-1$, where $J$ is the
 set of columns where the two runs agree.
 \end{proposition}

 \begin{proof}
  Fix one run, say, the top row.
  Let the {\em weight} of row $r$ be $w = \sum_{j \in J(r)} s_j$, where
  $J(r)$ is the set of columns where row $r$ agrees with the top row.
  Let there be $n_w$ rows of weight $w$.
  Put $\sigma = \sum (s_i - 1)$.
  Double counting (over all rows other than the top row) now yields
$$\sum_w n_w = N-1,$$
$$\sum_w w n_w = \sum_i (\frac{N}{s_i} - 1)s_i = Nk - \sigma - k,$$
$$\sum_w w^2 n_w = \sum_{i \ne j} (\frac{N}{s_i s_j}-1)s_i s_j +
 \sum_i (\frac{N}{s_i} - 1) s_i^2 = Nk(k-1) - (\sigma+k)^2 +N(\sigma+k)$$
so that
$$\sum (w-c)^2 n_w = \frac{N\sigma}{N-1}(N-1-\sigma)$$
for $c = k - \sigma/(N-1)$. Since this last sum is nonnegative,
$N \ge 1 + \sigma$. In case equality holds, every weight is equal to $c$,
and $c = k-1$.
 \end{proof}

For example, if an $OA(24, 2^{21}.3, 2)$ exists, then any two runs
have 21 weighted agreements. Since all weights are even except that
on the last column, any two runs agree in the last column. Contradiction,
so no such array exists.

\section*{Appendix II: List of some strength 3 arrays}
  For each explicit construction, we give an array.
  To save space, we give the transposed matrix: runs are columns here.

\subsection*{Construction (X$_1$)}

 $OA(40, 5.2^6, 3)$.

\[ 0000000011111111222222223333333344444444 \]
\[ 0110011001100110011001100110011001100110 \]
\[ 0101010101011010000011110011001111000011 \]
\[ 0101101000001111001100111100001101010101 \]
\[ 0000111100110011110000110101010101011010 \]
\[ 0011001111000011010101010101101000001111 \]
\[ 1100001101010101010110100000111100110011 \]


\subsection*{Construction (X$_2$)}

 $OA(48, 4.3.2^4, 3)$.

\[ 000000000000111111111111222222222222333333333333 \]
\[ 000011112222000011112222000011112222000011112222 \]
\[ 001100110011001100110011001100110011001100110011 \]
\[ 010101010101010101010101010101010101010101010101 \]
\[ 001111001001110000110110001111001001110000110110 \]
\[ 010110011010101001100101101001100101010110011010 \]


\subsection*{Construction (X$_3$)}

 $OA(48, 3.2^9, 3)$.

\[ 000000000000000011111111111111112222222222222222 \]
\[ 000000001111111100000000111111110000000011111111 \]
\[ 000011110000111100001111000011110000111100001111 \]
\[ 000011111111000001110001000101110111000100010111 \]
\[ 001100110011001100010111011100011011001000101011 \]
\[ 001100111100110010101010001100110101010101101001 \]
\[ 010101010101010100101011110101001110100001001101 \]
\[ 010101011010101011001100010101010011001111001100 \]
\[ 011010010110100101001101101100101101010010001110 \]
\[ 011010011001011010010110100101100110100110101010 \]


\subsection*{Construction (X$_4$)}

 $OA(54, 3^5.2, 3)$.

\[ 000000000000000000111111111111111111222222222222222222 \]
\[ 000000111111222222000000111111222222000000111111222222 \]
\[ 001122001122001122001122001122001122001122001122001122 \]
\[ 001122120201120201120201001122120201120201120201001122 \]
\[ 010212121020202101121020021201010212202101010212120102 \]
\[ 011001011001100110100110100101011001011001100110010110 \]


\subsection*{Construction (X$_5$)}

 $OA(64, 4^4.2^6, 3)$.

\[ 0000000000000000111111111111111122222222222222223333333333333333 \]
\[ 0000111122223333000011112222333300001111222233330000111122223333 \]
\[ 0123012301230123012301230123012301230123012301230123012301230123 \]
\[ 0123103223103201103201233201231023103201103201233201231001231032 \]
\[ 0011110000111100110000111100001111000011001111000011110011000011 \]
\[ 0011110011000011110000110011110000111100001111001100001111000011 \]
\[ 0101010110101010101010100101010110011001011001100110011010011001 \]
\[ 0101101010010110010110101001011010100101011010011010010101101001 \]
\[ 0110011010011001100110010110011001010101101010101010101001010101 \]
\[ 0110100101011010011010010101101010010110101001011001011010100101 \]


\end{document}

\begin{lemma}
 The nontrivial reasonable parameter sets for mixed orthogonal arrays
 of strength 3 and run size at most 100 are
 \begin{enumerate}
 \item $OA(4m, 2^a, 3)$, $4 \le a \le 2m$, $m$ even, $2 \le m \le 24$,
 \item $OA(4m, 2^3.m, 3)$, $m$ even, $2 \le m \le 24$,
 \item $OA(8m, 2^a.m, 3)$, $3 \le a \le 7$, $3 \le m \le 12$,
 \item $OA(8m, 2^a.4.m, 3)$, $2 \le a \le 4$, $m$ even, $4 \le m \le 12$,
 \item $OA(9m, 3^b.m, 3)$, $3 \le b \le 4$, $m = 3,6,9$,
 \item $OA(12m, 2^a.m, 3)$, $3 \le a \le 11$, $m$ even, $4 \le m \le 8$,
 \item $OA(12m, 2^a.3.m, 3)$, $2 \le a \le 9$, $m$ even if $a > 2$, $3 \le m \le 8$,
 \item $OA(12m, 2^a.6.m, 3)$, $2 \le a \le 6$, $m = 6,8$,
 \item $OA(16m, 2^a.m, 3)$, $3 \le a \le 15$, $3 \le m \le 6$,
 \item $OA(16m, 2^a.4.m, 3)$, $2 \le a \le 12$, $4 \le m \le 6$,
 \item $OA(54, 2^a.3^b, 3)$, $a = 0,1$, $b \ge 1$, $a+b \ge 4$, $a+2b \le 19$,
 \item $OA(64, 2^a.4^c, 3)$, $a \ge 0$, $c \ge 1$, $a+c \ge 4$, $a+3c \le 18$,
 \item $OA(72, 2^a.3^b, 3)$, $b = 1,2$, $a+b \ge 4$, $a+2b \le 25$,
 \item $OA(72, 2.3^2.4, 3)$,
 \item $OA(80, 2^a.4, 3)$, $3 \le a \le 19$,
 \item $OA(81, 3^b, 3)$, $4 \le b \le 14$,
 \item $OA(90, 2.3^2.5, 3)$,
 \item $OA(96, 2^a.3, 3)$, $3 \le a \le 31$,
 \item $OA(96, 2^a.3^b.4^c, 3)$, $b = 0,1$, $c = 1,2$, $a+b+c \ge 4$, $a+2b+3c \le 26$,
 \item $OA(96, 2^a.4^2.6, 3)$, $1 \le a \le 9$,
 \item $OA(100, 2^2.5^2, 3)$.
 \end{enumerate}
\end{lemma}
