\documentstyle[12pt]{article}
\textwidth=6.5in \textheight=8.9in \topmargin -0.5in
\parskip 6pt
\oddsidemargin=0.1in \evensidemargin=0.1in
\newcommand{\B}{{\cal B}}
\newcommand{\A}{{\cal A}}
\newcommand{\C}{{\cal C}}
\newcommand{\Hh}{{\cal H}}
\newcommand{\Pp}{{\cal P}}
\newcommand{\G}{{\cal G}}
\newcommand{\Z}{{\bf Z}}
\newcommand{\qed}{\hfill $\Box$}
\newcommand{\U}{{\cal U}}
\newcommand{\Proof}{{\em Proof.\ }}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}{Definition}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{construction}[theorem]{Construction}
\newtheorem{conjecture}[theorem]{Conjecture}

\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Construction}[Theorem]{Construction}
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem{Remark}[Theorem]{Remark}

\def\whitebox{{\hbox{\hskip 1pt
\vrule height 6pt depth 1.5pt \lower 1.5pt\vbox to 7.5pt{\hrule
width
  3.2pt\vfill\hrule width 3.2pt}%
\vrule height 6pt depth 1.5pt \hskip 1pt } }}
\def\qed{\ifhmode\allowbreak\else\nobreak\fi\hfill\quad\nobreak
     \whitebox\medbreak}
\title{\LARGE\textbf{Decomposing Complete Graphs into $r\times 4$ Grid-Blocks with $r=3,4$}}

\author{\small   Rucong Zhang and Gennian Ge\thanks{Corresponding author. Email: gnge@zju.edu.cn} \thanks{Research supported by National
Natural Science Foundation of China under Grant No.~10471127,
Zhejiang Provincial Natural Science Foundation of China under Grant No.~R604001, and   the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry}\\
%The Project-sponsored by SRF for ROCS, SEM.
\small          Department of Mathematics\\
\small          Zhejiang  University\\
\small          Hangzhou 310027, Zhejiang, P. R. China\\
\and \small Hung-Lin Fu and Jyh-Ming Kuo\thanks{Research supported
by NSC 94-2115-M-009-017}\\
\small Department of Applied Mathematics\\
\small National Chiao Tung University\\
\bigskip \small Hsin Chu, Taiwan 30050
\and \small Yukiyasu Mutoh\thanks{Research supported
by JSPS Research Fellow 09978} \\
\small Department of Mathematics \\
\small Keio University \\
\small Yokohama, Kanagawa, Japan 223-8522\\
}

\begin{document}
\date{}
\maketitle
\section{\Large\textbf{$3\times 4$-Grid Block Design}}



\begin{Lemma}
\label{existence}The necessary conditions for the existence of a
$D_{r\times c}$$(K_{v})$ are:
\begin{enumerate}
\item$(v - 1) \equiv 0\ (\bmod\ {r+c-2})$ and \\
\item$v(v - 1) \equiv 0\ (\bmod\ {rc(r+c-2)})$.
\end{enumerate}
\end{Lemma}
\hspace*{1.5em}Hence, a routine verification shows the following
fact.


\begin{Lemma}If a $D_{3\times4}(K_{v})$ exists, then $v\equiv 1,16,21,36\ (\bmod\
{60})$.
\end{Lemma}
\hspace{1.5em}In this paper, we will prove that the necessary
conditions $v\equiv 1,21\ (\bmod\ {60})$ are also sufficient. And
the others remain unknown. In other words, in this paper we want
to prove the following theorem.
\begin{Theorem}The necessary conditions $v\equiv 1,21\ (\bmod\ {60})$
for the existence of a $D_{3\times4}(K_{v})$ are also sufficient.
\end{Theorem}
\subsection{\Large\textbf{$v\equiv 1\ (\bmod\ {60})$}}
\hspace{1.5em}In this paper, the methods which we adopt are mainly
direct constructions. These direct constructions are based on
familiar difference method, where a finite abelian group is used
to generate the set of grid-blocks for a given design.  Thus,
instead of listing all the grid-blocks of the design, we list a
set of base grid-blocks and generate the others by an additive
group and perhaps some further automorphisms.\\
\hspace*{1.5em}Before describing our result, we need several
essential lemmas. Let $K_{m}(n)$ denote the balanced complete
$m-$partite graph with each partite set of size n. Then, the
following lemma holds.
\begin{Lemma}The necessary conditions for the existence of a $D_{r\times
c}(K_{m}(n))$ are:
\begin{enumerate}
\item$(m - 1)n \equiv 0\ (\bmod\ {r+c-2})$ and \\
\item$mn^2(m - 1) \equiv 0\ (\bmod\ {rc(r+c-2)})$.
\end{enumerate}
\end{Lemma}
\hspace{1.5em}We list some recursive constructions obtained by FU
et al.\cite{fu} and Mutoh et al.\cite{mutoh}.


\begin{Lemma}
\label{base}A $D_{r\times c}(K_{m\times n+1})$exists if a
$D_{r\times c}(K_{n+1})$ and a $D_{r\times c}(K_{m}(n))$exists.
\end{Lemma}
\begin{Lemma}
\label{gdd}There exists a $D_{r\times c}(K_{vt+1})$ if there exist
a GDD(v,$\mathcal{K}$,$\mathcal{M}$), $D_{r\times c}(K_{mt+1})$
and $D_{r\times c}(K_{k}(t))$ for any m $\in \mathcal{M}$ and k
$\in \mathcal{K}$.
\end{Lemma}
\begin{Lemma}
\label{oa}There exists a $D_{r\times c}(K_{s}(tu))$ if there
exists a $D_{r\times c}(K_{s}(t))$ and an OA(u,s), where OA(u,s)
is an orthogonal array of order u, degree s and index 1.
\end{Lemma}

\begin{Lemma}
\label{gdde}For any integer $v\ge$ 12, there exists a
GDD(v,$\mathcal{K}$,$\mathcal{M}$), where $\mathcal{K}$ =\{4,5\}
and $\mathcal{M}$=\{1,2,...,7\}.
\end{Lemma}
\hspace{1.5em}Lastly, we extend the construction in \cite{three}
to grid-block designs to obtain such designs easily. For a
positive integer e, let q be a prime power such that $q\equiv 1
(\bmod\ e)$ . The cyclic multiplicative subgroup of nonzero
elements in GF(q) has a unique subgroup $C^e_0$ of index e. The
multiplicative cosets $C^e_0$,$C^e_1$,...,$C^e_{e-1}$ of $C^e_0$
are called the cyclotomic
classes of index e.\\
\hspace{1.5em}Let A=$(a_{ij})$ be a $r\times c$ grid-block designs
with elements in GF(q). We define an ordered list of differences
of
A as follows:\\
\begin{center}
$\vec{\partial} A$=$(a_{jl}-a_{il}:1\le i < j \le r,1\le l\le
c)+(a_{lj}-a_{li}:1\le l \le r,1 \le i<j \le c)$.
\end{center}
\hspace{1.5em}Then the following Lemma is obtained:
\begin{Lemma}
\label{construct}For a prime power $q\equiv 1(\bmod rc(r+c-2))$,
let e=rc(r+c-2)/2. If there exists a $r\times c$ array
$A=(a_{ij})$over GF(q) such that $\vec{\partial}A$ are a system of
representative for the cosets of $C^e_0$, then there exists a
$D_{r\times c}(K_{q})$.
\end{Lemma}

\textbf{Remark}. We can view the grid-block A as the base
block.And the all grid-blocks of $D_{r\times c}(K_{q})$ are
obtained by calculating cA+x for $c\in C^e_0/\{1,-1\}$ and $x\in
GF(q)$.

\begin{Lemma}
\label{20^4} There exist both a $D_{3\times 4}(K_{4}(20))$ and  a
$D_{3\times 4}(K_{4}(60))$.
\end{Lemma}
\textbf{Proof:} The design is constructed on the Abelian group
$V=Z_{80}$. In order to obtain the base grid-blocks, we use
difference method. Then we can get all grid-blocks by V acting on
the base grid-blocks. This design has only one base grid-block.
The only one base grid-block is following $3 \times 4$ array:
\begin{center}
\begin{tabular}{|l|l|l|l|}\hline
0 & 1 & 3 & 10 \\
\hline
11 & 16 & 54 & 33 \\
\hline
66 &47 &21 &60\\
\hline
\end{tabular}
\end{center}
\hspace*{1.5em}It is known that there is an OA(3,4). Thus the
$D_{3\times 4}(K_{4}(60))$ can be obtained by applying Lemma
~\ref{oa}.\qed


\begin{Lemma}
\label{15^5}There exist both a $D_{3\times 4}(K_{5}(15))$ and a
$D_{3\times 4}(K_{5}(60))$.
\end{Lemma}
\textbf{Proof:} The design is constructed on the Abelian group
$V=Z_{75}$ generated by the group V acting on the points. This
design
has exactly only one base grid-block. It is:\\
\begin{center}
          \begin{tabular}{|l|l|l|l|}\hline
             0 & 1 & 3 & 7\\
             \hline
             14& 38 & 66 & 25\\
             \hline
             43 &60 & 24 & 51\\
             \hline
             \end{tabular}
          \end{center}
And an OA(4,5) also exists. So we can get the $D_{3\times
4}(K_{5}(60))$ by using the Lemma ~\ref{oa}.\qed

\begin{Lemma}
\label{t}There exists a $D_{3\times 4}(K_{60t+1})$ for t=1,2,3,7.
\end{Lemma}
\textbf{Proof:} According to Lemma ~\ref{construct}, we use
computer to find the array A for t=1,2,3,7. These A are listed in
the
following table:\\
\begin{center}
\begin{tabular}{|c||c|llll|}\hline
t & primitive element or polynomial &\multicolumn{4}{c|}{A}\\
\hline 1 &2&0 &1 &3 &7\\
         &  &5 &25 &56 &43\\
         &   &19 &47 &30 &59\\
\hline 2 &$\omega^2+\omega^1+7$ &$\omega^\infty$ &$\omega^0$
&$\omega^1$ &$\omega^2$\\
         & &$\omega^3$ &$\omega^5$ &$\omega^{15}$ &$\omega^{98}$\\
         & &$\omega^{24}$ &$\omega^{95}$ &$\omega^{97}$ &$\omega^{45}$\\
\hline 3&2 &0 &1 &3 &7\\
        &  &5 &13 &23 &63\\
        &  &99 &90 &142 &39\\
\hline

\hline 7&2 &0 &1 &3 &7\\
        &  &5 &13 &23 &37\\
        &  &105 &365 &281 &86\\
\hline
\end{tabular}
\end{center}
\hspace*{1.5em}It is easy to show the existence of the desired
grid-block designs. For example, we verify the case t=1. First, we
can get q=61, e=30 and f=(q-1)/e=2 easily. We denote
$F^*$=GF(q)/\{0\},\ $\omega$ to be the primitive element of
$F^*$ and $\varepsilon$=$\omega^{e}$. Second, we compute the all  cosets of $C^e_0$. They are:\\
\begin{center}
\begin{tabular}{|l|}\hline
$C^e_0$=$\{1,\varepsilon,\varepsilon^2,...,\varepsilon^{f-1}\}$=$\{1,60\}$\\
\hline
$C^e_1$=$\{\omega,\omega\varepsilon,\omega\varepsilon^2,...,\omega\varepsilon^{f-1}\}$=$\{2,59\}$\\
\hline
$C^e_2$=$\{\omega^2,\omega^2\varepsilon,\omega^2\varepsilon^2,...,\omega^2\varepsilon^{f-1}\}$=$\{4,57\}$\\
\hline
.\\
\hline
.\\
\hline
.\\
\hline
$C^e_{e-2}$=$\{\omega^{e-2},\omega^{e-2}\varepsilon,\omega^{e-2}\varepsilon^2,...,\omega^{e-2}\varepsilon^{f-1}\}$=$\{15,46\}$\\
\hline
$C^e_{e-1}$=$\{\omega^{e-1},\omega^{e-1}\varepsilon,\omega^{e-1}\varepsilon^2,...,\omega^{e-1}\varepsilon^{f-1}\}$=$\{30,31\}$\\
\hline
\end{tabular}
\end{center}
Third, we compute $\vec{\partial}A$ and take the 30 differences
all less than 31, that is to say, if the difference is 41, we
write it down as 20. So the all differences are
$\vec{\partial}A$=$(5,14,19,24,15,22,8,26, 27,\\
25,16,9, 1,2,3,4,6,7, 20,30,10,13,18,23,28,17,11,29,12,21)$. The
30 different differences are exactly the elements 1 to 30.
According the cosets of $C^e_0$, we know the elements 1 to 30 are
exactly in the 30 different cosets. So according to Lemma
~\ref{construct}, the $D_{3\times4}(K_{61})$ exists. The all
grid-blocks are obtained by calculating cA+x for $c\in
C^e_0/\{1,-1\}$ and $x\in GF(q)$.\qed


\begin{Lemma}
\label{t4}There exists a $D_{3\times 4}(K_{60t+1})$ for t=4.
\end{Lemma}
\textbf{Proof:} By Lemma~\ref{20^4} and Lemma~\ref{t}, there exist
both a $D_{3\times 4}(K_{4}(60))$ and a $D_{3\times 4}(K_{61})$.
Thus, there exists the $D_{3\times 4}(K_{60\times 4+1})$ by Lemma
~\ref{base}.\qed

\begin{Lemma}
\label{t5}There exists a $D_{3\times 4}(K_{60t+1})$ for t=5.
\end{Lemma}
\textbf{Proof:} By Lemma ~\ref{15^5} and Lemma ~\ref{t}, there
exist both a $D_{3\times 4}(K_{5}(60))$ and a $D_{3\times
4}(K_{61})$. Thus, there exists the  $D_{3\times 4}(K_{60\times
5+1})$ by Lemma ~\ref{base}.\qed


\begin{Lemma}
\label{t6}There exists a $D_{3\times 4}(K_{60t+1})$ for t=6.
\end{Lemma}
\textbf{Proof:} First, we construct $D_{3\times 4}(K_{6}(60))$. We
know the 5-GDD of type $4^{6}$ exists, see \cite{ge} for a
reference. Then for the each point in the each partite set, we
inflate it to 15 points. In other words, we view each point in the
each partite set as a subset(each of size 15). So We can get the
$D_{3\times 4}(K_{6}(60))$ by using Lemma ~\ref{15^5} to obtain 75
grid-blocks for each $K_{5}$ in a $K_{5}$-design of $K_{6}(4)$.
Then, by the Lemma~\ref{t}, we know the $D_{3\times 4}(K_{61})$
exists. So, we get the $D_{3\times 4}(K_{60\times 6+1})$ by Lemma
~\ref{base}.\qed


\begin{Lemma}
\label{t8}There exists a $D_{3\times 4}(K_{60t+1})$ for t=8.
\end{Lemma}
\textbf{Proof:}  We have known the $D_{3\times 4}(K_{4}(40))$
exists. Then we can get the $D_{3\times 4}(K_{4}(120))$ by
applying Lemma ~\ref{oa} and OA(3,4). Also there is a $D_{3\times
4}(K_{121})$ by Lemma ~\ref{t}. Thus the desired grid-block design
can be obtained by Lemma~\ref{base}.\qed
\begin{Lemma}
\label{15^9} There exists a $D_{3\times 4}(K_9(15))$.
\end{Lemma}
\textbf{Proof:} The design is constructed on the Abelian group
$V=Z_{135}$ generated by the group V acting on the points. This
design has two base
grid-blocks. They are:\\
\begin{center}
\begin{tabular}{|l|l|l|l|}\hline
0 &1 &3 &7\\
\hline 5 &13 &24 &37\\
\hline 15 &44 &79 &104\\
\hline
\end{tabular}
\begin{tabular}{|l|l|l|l|}\hline
0 &14 &61 &83\\
\hline 50 &115 &89 &66\\
\hline 98 &58 &5 &25\\
\hline
\end{tabular}
\end{center}\qed

\begin{Lemma}
\label{t9}There exists a $D_{3\times 4}(K_{60t+1})$ for t=9.
\end{Lemma}
\textbf{Proof:} Firstly,we know the $(37,\{5,9^*\})$-PBD exists,
see \cite{ge1} for a reference, where the  $9^*$ means there is
only one 9 points block B. Secondly, we delete one point which is
not in B. So there are 36 points remain. Then, we can get the
\{5,9\}-GDD of type $4^9$. We inflate each one point to 15 points.
In other words, we view each point in the each partite set as a
subset(each of size 15). Finally, because of the existence of the
$D_{3\times 4}(K_5(15))$ and the $D_{3\times 4}(K_9(15))$ by Lemma
~\ref{15^5} and Lemma ~\ref{15^9} respectively, we get the
$D_{3\times 4}(K_{60\times 9+1})$.\qed

\begin{Lemma}
\label{t10}There exists a $D_{3\times 4}(K_{60t+1})$ for t=10.
\end{Lemma}
\textbf{Proof:} By Lemma~\ref{15^5}, we know the $D_{3\times
4}(K_{5}(15))$ exists. And also the OA(8,5) exists. So we get the
$D_{3\times 4}(K_{5}(120))$ by Lemma ~\ref{oa}. There exists the
$D_{3\times 4}(K_{121})$ by Lemma ~\ref{t}. So we get the
$D_{3\times 4}(K_{60\times 10+1})$by Lemma ~\ref{base}.\qed

\begin{Lemma}
\label{t11}There exists a $D_{3\times 4}(K_{60t+1})$ for t=11.
\end{Lemma}
\textbf{Proof:} We know the 5-GDD of type $4^{11}$ exists, see
\cite{ge} for a reference. Then for the each point in the each
partite set, we inflate it to 15 points. In other words, we view
each point in the each partite set as a subset(each of size 15).
So We can get the $D_{3\times 4}(K_{11}(60))$ by using Lemma
~\ref{15^5} to obtain 75 grid-blocks for each $K_{5}$ in a
$K_{5}$-design of $K_{11}(4)$. Then, by the Lemma~\ref{t}, we know
the $D_{3\times 4}(K_{61})$ exists. So we get the $D_{3\times
4}(K_{60\times 11+1})$ by Lemma ~\ref{base}.\qed


\begin{Theorem}
There exist $D_{3\times 4}(K_{60t+1})$ for each positive integer
t.
\end{Theorem}
\textbf{Proof:} When t $\ge$ 12, we know
GDD(t,$\mathcal{K}$,$\mathcal{M}$) exist, where $\mathcal{K}$
=\{4,5\} and $\mathcal{M}$=\{1,2,...,7\} by Lemma~\ref{gdde}. We
also know the $D_{3\times4}(K_{60m+1})$ for any $m \in
\mathcal{M}$ and the $D_{3\times4}(K_{k}(60))$ for any $k\in
\mathcal{K}$ exist by above Lemmas. So by Lemma ~\ref{gdd}, the
$D_{3\times4}(K_{60t+1})$ exist when t $\ge$ 12. Thus, together
with Lemma
~\ref{t},~\ref{t4},~\ref{t5},~\ref{t6},~\ref{t8},~\ref{t9},~\ref{t10}
and ~\ref{t11} we get the theorem.\qed


\subsection{\Large\textbf{$v\equiv 21\ (\bmod\ {60})$}}
\hspace{1.5em}So according to Lemma ~\ref{base}, if we want to
prove for each positive integer $t$ a $D_{3\times 4}(K_{60t+21})$
exists. We should prove a $D_{3\times 4}(K_{21})$ exists and for
each positive integer $t$ a $D_{3\times 4}(K_{3t+1}(20))$ exists.

\begin{Lemma}
\label{21}There exists a $D_{3\times 4}(K_{21})$ .
\end{Lemma}
\textbf{Proof: }The design is constructed on $V=Z_{7}\times I_{3}$
generated by the group $Z_{7}$ acting on the points. We select
this V, because V is isomorphism to $Z_{21}$. There is only
one base grid-block. The base grid-block is following $3\times 4$ array: \\
          \begin{center}
          \begin{tabular}{|l|l|l|l|}\hline
             (0,0)&(1,0)&(3,0)&(0,1)\\
             \hline
             (2,1)&(4,1)&(1,1)&(0,2)\\
             \hline
             (3,2)&(6,2)&(5,2)&(6,0)\\
             \hline
             \end{tabular}
          \end{center}\qed


\begin{Lemma}
\label{20^7}There exists a $D_{3\times 4}(K_{7}(20))$ .
\end{Lemma}
\textbf{Proof:} The design is constructed on the Abelian group
$V=Z_{140}$ generated by the group V acting on the points. This
design has two base
grid-blocks. They are:\\
\begin{center}
\begin{tabular}{|l|l|l|l|}\hline
0 &1 &3 &9\\
\hline 4 &14 &19 &31\\
\hline 23 &61 &90 &123\\
\hline
\end{tabular}
\begin{tabular}{|l|l|l|l|}\hline
0 &11 &45 &86\\
\hline 37 &101 &81 &7\\
\hline 88 &70 &113 &31\\
\hline
\end{tabular}
\end{center}\qed

\begin{Lemma}
\label{20^10}There exists a $D_{3\times 4}(K_{10}(20))$ .
\end{Lemma}
\textbf{Proof:} The design is constructed on the Abelian group
$V=Z_{200}$ generated by the group V acting on the points. This
design has three base
grid-blocks. They are:\\
\begin{center}
\begin{tabular}{|l|l|l|l|}\hline
199 &74 &46 &122\\
\hline 38 &195 &103 &141\\
\hline 132 &181 &90 &159\\
\hline
\end{tabular}
\begin{tabular}{|l|l|l|l|}\hline
44&69 &78 &133\\
\hline 139 &110 &54 &52\\
\hline 55 &38 &192 &126\\
\hline
\end{tabular}
\begin{tabular}{|l|l|l|l|}\hline
61 &53 &2 &8\\
\hline 96 &192 &18 &91\\
\hline 73 &74 &70 &106\\
\hline
\end{tabular}
\end{center}\qed


\begin{Lemma}
\label{20^19}There exists a $D_{3\times 4}(K_{19}(20))$ .
\end{Lemma}
\textbf{Proof:} In order to obtain the $D_{3\times
4}(K_{19}(20))$, we first construct the $D_{3\times
4}(K_{6}(60))$, and then together with the $D_{3\times
4}(K_{4}(20))$ we can get the desired design.\\
\hspace*{1.5em}Now we construct the $D_{3\times 4}(K_{6}(60))$.
First, we know the 5-GDD of type $4^{6}$ exists, see \cite{ge} for
a reference. Then for the each point in the each partite set, we
inflate it to 15 points. In other words, we view each point in the
each partite set as a subset(each of size 15). So We can get the
$D_{3\times 4}(K_{6}(60))$ by using Lemma ~\ref{15^5} to obtain 75
grid-blocks for each $K_{5}$ in a
$K_{5}$-design of $K_{6}(4)$.\\
\hspace*{1.5em}Then we can construct the desired design-
$D_{3\times 4}(K_{19}(20))$. We first partitioning each partite
set of $K_{6}(60)$ into 3 subsets(each of size 20). Second, we add
20 new points to $K_{6}(60)$. We view 20 points as a subset A
which is different from the subsets in $K_{6}(60)$. So we have 19
subsets(each has 20 points)altogether. We view each subset as a
partite set. We select two points from two different partite sets,
we have two cases. First, if the two points are all from
$K_{6}(60)$, then the existence of $D_{3\times 4}(K_{6}(60))$
ensure these two points occur in same row or in same column in
some block; Second, if one point from $K_{6}(60)$ and the other
point from A, then Lemma~\ref{20^4} ensure these two points occur
in same row or in same column in some block. So we get the
$D_{3\times 4}(K_{19}(20))$.\qed

\begin{Lemma}
\label{3t+1}For each positive integer $t$ a $D_{3\times
4}(K_{3t+1}(20))$ exists.
\end{Lemma}
\textbf{Proof:} We have known the (v,\{4,7,10,19\},1)-PBD exists,
where $v\equiv 1(\bmod3)$ and $v\ge 4$, that is to say
\B(\{4,7,10,19\})is a PBD-closed set. We can view the
(v,\{4,7,10,19\},1)-PBD as the \{4,7,10,19\}-GDD of type $1^v$.
 Then we can inflate each point to 20 points. In other words, we view
each point of $K_{v}(1)$ as a subset (each of size 20). Therefore,
we can conclude the proof by using Lemma ~\ref{20^4},~\ref{20^7}
,~\ref{20^10} and ~\ref{20^19}.\qed

\begin{Theorem}
For each positive integer $t$ a $D_{3\times 4}(K_{60t+21})$
exists.
\end{Theorem}
\textbf{Proof:} We can easily get the theorem by using
Lemma~\ref{3t+1}, Lemma~\ref{21} and Lemma~\ref{base}. \qed
\section{\Large\textbf{$4\times 4$-Grid Block Design}}
\hspace{1.5em}According to Lemma ~\ref{existence}, we have the
following
lemma:\\


\begin{Lemma}
\label{4*4}If a $D_{4\times 4}(K_{v})$ exists, then $v\equiv
1(\bmod 96)$.
\end{Lemma}
\hspace{1.5em}In this paper, we will prove the above necessary
conditions in Lemma ~\ref{4*4} are also sufficient, that is to
say, we will
prove the following theorem:\\


\begin{Theorem}
A $D_{4\times 4}(K_{v})$ exists if and only if $v\equiv 1(\bmod
96)$.
\end{Theorem}


\begin{Lemma}
\label{97}There exists a $D_{4\times 4}(K_{97})$.
\end{Lemma}
\textbf{Proof:} According to Lemma ~\ref{construct}, we use
computer to find the array A
when q=97. The A is:\\
\begin{center}
          \begin{tabular}{|l|l|l|l|}\hline
             0 & 1 & 3 & 7\\
             \hline
             5& 13 & 81 & 38\\
             \hline
             16 &60 & 26 & 86\\
             \hline
             46 &74 &61  &29\\
             \hline
             \end{tabular}
          \end{center}
\hspace{1.5em}Now we check the array A whether satisfy the
condition of Lemma ~\ref{construct} or not. First,we can get
q=97,e=48 and f=(q-1)/e=2 easily. We denote $F^*$=GF(q)/\{0\} ,
$\omega$ to be the primitive element of
$F^*$, here $\omega$=5 and $\varepsilon$=$\omega^{e}$. Second, we compute the all  cosets of $C^e_0$. They are:\\
\begin{center}
\begin{tabular}{|l|}\hline
$C^e_0$=$\{1,96\}$\\
\hline
$C^e_1$=$\{5,92\}$\\
\hline
$C^e_2$=$\{25,72\}$\\
\hline
.\\
\hline
.\\
\hline
.\\
\hline
$C^e_{e-2}$=$\{31,66\}$\\
\hline
$C^e_{e-1}$=$\{58,39\}$\\
\hline
\end{tabular}
\end{center}
Third, we calculate  $\vec{\partial}A$ and take the 48 differences
all less than 49, that is to say, if the difference is 61, we
write it down as 36. So the all differences are
$\vec{\partial}A$=$(5,11,16,30,41,46,12,47,38,14,\\36,24,
19,42,23,35,20,39,31,48,18,40,9,22,1,2,3,4,6,7,8,29,21,43,25,33,44,34,10,37,26,\\
27,28,13,15,32,45,17)$. The 48 different differences are exactly
the elements 1 to 48, that is to say, the 48 different differences
are exactly in the 48 different cosets. So according to Lemma
~\ref{construct}, the $D_{4\times4}(K_{97})$ exists. The all
grid-blocks are obtained by calculating cA+x for $c\in
C^e_0/\{1,-1\}$ and $x\in GF(q)$.\qed


\begin{Lemma}
\label{4^4}There exists a $D_{4\times 4}(K_{4}(4))$ .
\end{Lemma}
\textbf{Proof:} Let the four partite sets of $K_{4}(4)$ be
$A_{0}$=\{0,4,8,12\},$A_{1}$=\{1,5,9,13\},$A_{2}$=\{2,6,10,14\}
and $A_{3}$=\{3,7,11,15\}. Then $D_{4\times 4}(K_{4}(4))$ contains
exactly two $4\times 4$ grid-blocks as following:\\
\begin{center}
\begin{tabular}{|l|l|l|l|}\hline
0 &1 &2 &3\\
\hline 5 &4 &7 &6\\
\hline 10 &11 &8 &9\\
\hline 15&14 &13 &12\\
\hline
\end{tabular}
\begin{tabular}{|l|l|l|l|}\hline
0 &9 &14 &17\\
\hline 13 &4 &3 &10\\
\hline 6 &15 &8 &1\\
\hline 11 &2  &5 &12\\
\hline
\end{tabular}
\end{center}\qed
We note here that if $K_{m}(n)$ has a decomposition into subgraphs
$K_{k}$, then we have a group divisible design, an (n,m;k;1)-GDD,
see \cite{abcde} for a reference. The following result is known
for some time.


\begin{Theorem}\cite{abcde}
\label{gddex}An (n,m;4;1)-GDD exists if and only if
\begin{enumerate}
\item $3|(m-1)n $ and \item $12|n^2m(m-1)$.
\end{enumerate}
\end{Theorem}
\hspace{1.5em}By using Lemma ~\ref{4^4} and Theorem ~\ref{gddex},
we can prove the following lemma.


\begin{Lemma}
\label{m}For each $m\ge 4$, a $D_{4\times 4}(K_{m}(96))$ exists.
\end{Lemma}
\textbf{Proof:} First, by partitioning each partite set of
$K_{m}(96)$ into 24 subsets (each of size 4), we have a new graph
G $\cong K_{m}(24)$ in which each vertex represents a subset of
size 4. Denote the m partite sets of G by
$A_{0}$,$A_{1}$,...,$A_{m-1}$, where $A_{i}$ =
\{$A_{i,0}$,$A_{i,1}$,...,$A_{i,23}$\}, $i\in \Z_{m}$. Therefore,
$V(G)=\{A_{i,j}|i \in \Z_{m}\ and\ j \in \Z_{24}\}$. By Theorem
~\ref{gddex}, a (24,m;4;1)-GDD exists for each $m\ge 4$.
Therefore, we conclude the proof by using Lemma ~\ref{4^4} to
obtain two grid-blocks for each $K_{4}$ in a $K_{4}$-design of
G.\qed


\begin{Lemma}
\label{193}There exists a $D_{4\times 4}(K_{193})$ .
\end{Lemma}
\textbf{Proof:} According to Lemma ~\ref{construct}, we use
computer to find the array A
when q=193. The A is:\\
\begin{center}
          \begin{tabular}{|l|l|l|l|}\hline
             0 & 1 & 3 & 7\\
             \hline
             5& 14 & 25 & 39\\
             \hline
             35 &72 & 131 & 62\\
             \hline
             82 &150 &110  &183\\
             \hline
             \end{tabular}
          \end{center}
\hspace*{1.5em}Now we check the array A whether satisfy the
condition of Lemma ~\ref{construct} or not. First, we can easy get
q=193, e=48 and f=(q-1)/e=4. We denote $F^*$=GF(q)/\{0\}, $\omega$
to be the primitive element of
$F^*$, here $\omega$=5 and $\varepsilon$=$\omega^{e}$. Second, we compute the all  cosets of $C^e_0$. They are:\\
\begin{center}
\begin{tabular}{|l|l|l|l|}\hline
$C^e_0=\{1\ 112\ 192\ 81\}$&$C^e_1=\{5\ 174\ 188\
19\}$&$C^e_2=\{25\ 98\ 168\ 95\}$&$C^e_3=\{125\ 104\ 68\ 89\}$\\
\hline $C^e_4=\{46\ 134\ 147\ 59\}$&$C^e_5=\{37\ 91\ 156\ 102 \}$&$C^e_6=\{185\ 69\ 8\ 124\}$&$C^e_7=\{153\ 152\ 40\ 41 \}$\\
\hline$C^e_8=\{186\ 181\ 7\ 12\}$&$C^e_9=\{158\ 133\ 35\ 60\}$&$C^e_{10}=\{18\ 86\ 175\ 107 \}$&$C^e_{11}=\{90\ 44\ 103\ 149 \}$\\
\hline$C^e_{12}=\{64\ 27\ 129\ 166\}$&$C^e_{13}=\{127\ 135\ 66\ 58\}$&$C^e_{14}=\{56\ 96\ 137\ 97 \}$&$C^e_{15}=\{87\ 94\ 106\ 99 \}$\\
\hline$C^e_{16}=\{49\ 84\ 144\ 109 \}$&$C^e_{17}=\{52\ 34\ 141\ 159\}$&$C^e_{18}=\{67\ 170\ 126\ 23\}$&$C^e_{19}=\{142\ 78\ 51\ 115 \}$\\
\hline$C^e_{20}=\{131\ 4\ 62\ 189 \}$&$C^e_{21}=\{76\ 20\ 117\ 173\}$&$C^e_{22}=\{187\ 100\ 6\ 93\}$&$C^e_{23}=\{163\ 114\ 30\ 79 \}$\\
\hline$C^e_{24}=\{43\ 184\ 150\ 9\}$&$C^e_{25}=\{22\ 148\ 171\ 45 \}$&$C^e_{26}=\{110\ 161\ 83\ 32\}$&$C^e_{27}=\{164\ 33\ 29\ 160\}$\\
\hline$C^e_{28}=\{48\ 165\ 145\ 28\}$&$C^e_{29}=\{47\ 53\ 146\ 140 \}$&$C^e_{30}=\{42\ 72\ 151\ 121 \}$&$C^e_{31}=\{17\ 167\ 176\ 26\}$\\
\hline$C^e_{32}=\{85\ 63\ 108\ 130\}$&$C^e_{33}=\{39\ 122\ 154\ 71 \}$&$C^e_{34}=\{2\ 31\ 191\ 162 \}$&$C^e_{35}=\{10\ 155\ 183\ 38\}$\\
\hline$C^e_{36}=\{50\ 3\ 143\ 190\}$&$C^e_{37}=\{57\ 15\ 136\ 178 \}$&$C^e_{38}=\{92\ 75\ 101\ 118  \}$&$C^e_{39}=\{74\ 182\ 119\ 11 \}$\\
\hline$C^e_{40}=\{177\ 138\ 16\ 55\}$&$C^e_{41}=\{113\ 111\ 80\ 82 \}$&$C^e_{42}=\{179\ 169\ 14\ 24\}$&$C^e_{43}=\{123\ 73\ 70\ 120\}$\\
\hline$C^e_{44}=\{36\ 172\ 157\ 21\}$&$C^e_{45}=\{180\ 88\ 13\ 105 \}$&$C^e_{46}=\{128\ 54\ 65\ 139\}$&$C^e_{47}=\{61\ 77\ 132\ 116\}$\\
\hline
\end{tabular}
\end{center}
\hspace*{1.5em}Third, we calculate $\vec{\partial}A$ and take the
48 differences all less than 97, that is to say, if the difference
is 100, we write it down as 93. And the all differences are
$\vec{\partial}A$=$(5,30,35,47,77,82,13,58,71,\\
78,57,44,22,87,65,21,85,86,32,23,
55,72,49,17,1,2,3,4,6,7,9,11,20,14,25,34,37,59,96,69,\\
10,27,68,40,28,73,33,92)$ . By means of computer, we find the 48
different differences are exactly in the 48 different cosets. So
by Lemma ~\ref{construct}, the $D_{4\times 4}(K_{193})$ exists.
And all grid-blocks are obtained by calculating cA+x for $c\in
C^e_0/\{1,-1\}=\{1,112\}$ and $x\in GF(q)$.\qed


\begin{Lemma}
\label{289}There exists a $D_{4\times 4}(K_{289})$.
\end{Lemma}
\textbf{Proof:} According to Lemma ~\ref{construct}, we use
computer to find the array A when q=289. We denote
$F^*$=GF$(17^2)$/\{0\} and $\omega$ to be the primitive element of
$F^*$, here $\omega$ is the root of
primitive polynomial $\omega^2+\omega+3$. The A is:\\
\begin{center}
          \begin{tabular}{|l|l|l|l|}\hline
             $\omega^\infty$ & $\omega^0$ & $\omega^1$ & $\omega^2$\\
             \hline
             $\omega^3$& $\omega^4$ & $\omega^5$ & $\omega^6$\\
             \hline
             $\omega^{20}$ &$\omega^{17}$ &$\omega^{155}$ & $\omega^{83}$\\
             \hline
             $\omega^{46}$ &$\omega^{70}$ &$\omega^{221}$  &$\omega^{7}$\\
             \hline
             \end{tabular}
          \end{center}
\hspace*{1.5em}Now we check the array A whether satisfy the
condition of Lemma ~\ref{construct} or not. First, we can easy get
e=48 and f=(q-1)/e=6. Second, we compute the all cosets of
$C^e_0$. They are:\\
\begin{center}
\begin{tabular}{|l|}\hline
$C^e_0=\{1,\omega^{48},\omega^{96},\omega^{144},\omega^{192},\omega^{240}\}$\\
\hline $C^e_1=\{\omega
,\omega^{49},\omega^{97},\omega^{145},\omega^{193},\omega^{241}\}$\\
\hline \\
. \\
\hline .\\
\hline .\\
\hline $C^e_{46}=\{\omega^{46}
,\omega^{94},\omega^{142},\omega^{190},\omega^{238},\omega^{286}\}$\\
\hline $C^e_{47}=\{\omega^{47}
,\omega^{95},\omega^{143},\omega^{191},\omega^{239},\omega^{287}\}$\\
\hline
\end{tabular}
\end{center}
\hspace*{1.5em}Third, we reckon $\vec{\partial}A$. We know all
differences have the form $\omega^i$. In order to check simply, we
take the all i are less than 48, that is to say, if the value of i
is 100, we write it down as 4. This is because $\omega^{4}$ and
$\omega^{100}$ are in the same coset. And the all differences are
$\vec{\partial}A$=$(\omega^{3},\omega^{8},\omega^{20},\omega^{30},\omega^{21},\omega^{46},\omega^{11},\omega^{36},\omega^{5},\omega^{7},\omega^{15},\omega^{35},\omega^{12},\omega^{39},
\omega^{27},\omega^{22},\omega^{23},\omega^{24},\omega^{13},\omega^{16},\omega^{14},\\
\omega^{31},\omega^{43},\omega^{19},
1,\omega^{37},\omega,\omega^{38},\omega^{6},\omega^{2},\omega^{40},\omega^{41},\omega^{9},\omega^{42},
\omega^{10},\omega^{4},\omega^{18},\omega^{45},\omega^{33},\omega^{29},\omega^{28},\omega^{47},\omega^{26},\omega^{25},\\
\omega^{32} ,\omega^{44},\omega^{34},\omega^{17})$. We can easy
find the all  value of i are exactly the elements  0 to 47, that
is to say, the 48 different differences are exactly from 48
different cosets. So the array A satisfy the
Lemma~\ref{construct}. Thus, the $D_{4\times 4}(K_{289})$ exists.
And all grid-blocks are obtained by calculating cA+x for $c\in
C^e_0/\{1,-1\}$ and $x\in GF(q)$.\qed


\begin{Theorem}
A $D_{4\times4}(K_{96t+1})$  exists for each positive integer t.
\end{Theorem}
\textbf{Proof:} By Lemma ~\ref{97} and ~\ref{m}, we know
$D_{4\times 4}(K_{96t+1})$ exists for each positive integer t,
where $t\ge 4$. So by using the Lemma~\ref{97}, ~\ref{193},
~\ref{289}, we get the theorem .\qed



\begin{thebibliography}
\frenchspacing
\bibitem{ge}
Gennian Ge and Alan C.H.Ling, Asymptotic results on the existence
of 4-RGDDs and uniform 5-GDDs, J.Combin.Des, {\bf 13}(2005),
222-237.

\bibitem{ge1}
R.Julian R.Abel, Gennian Ge, Malcolm Greig, and Alan C.H.Ling,
Futher Result on $(v,\{5,w^*\},1)$-PBDs, preprint.

\bibitem{abcde}
A.E Brouwer, A.Shrijver and H.Hanani, Group divisible designs with
block size 4, Discrete Math., {\bf 20}(1997), 1-10.

\bibitem{fu}
H.-L.Fu, F.K.Hwang, M.Jimbo,Y.mutoh and C.-L. Shiue, Decomposing
complete graphs into $K_{r}\times K_{c}'s$,
J.Statist.Plann.Inference, Vol.119, Issue 2(2004), 225-236.

\bibitem{mutoh}
Y.Mutoh, T.Morihara, M.Jimbo and H.L.Fu(2003), The existence of
$2\times 4$ grid-block dessigns and their applications,
SIAM.J.Discrete Mathematics, {\bf16}, 173-178.


\bibitem{three}
R.M.Wilson(1972), Cyclotomy and difference families in elementary
abelian groups, J.Number Theory, {\bf4}, 17-47.
 \nonfrenchspacing

\end{thebibliography}

\end{document}