% LaTex
\documentstyle[12pt]{article}
%  ##############################
\topmargin=-30pt
\textheight=648pt
\oddsidemargin=0pt
\textwidth=468pt
%  ##############################
\pagestyle{plain}
%%%%%%%%%%%%%%% New Font %%%%%%%%%%%%%%%%%%
%  #############################
%  -----  For 12pts  --------
\font\msbm=msbm10 at 12pt
\newcommand{\ZZ}{\mbox{\msbm Z}}
\newcommand{\RR}{\mbox{\msbm R}}
%  -----  For Section  --------
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\newcommand\ZZ{Z}
%\newcommand\RR{R}
%\newcommand\ZZZ{Z}
%\newcommand\ZZZZ{Z}
%\newcommand\Z-t{Z}
%%%%%%%%%%%%%% New Font %%%%%%%%%%%%%%%%%%%
\newtheorem{thm}{Theorem}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{fact}[thm]{Fact}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\pf}{{\bf Proof.\ }}
\newcommand{\qed}{\hfill $\Box$ \\}
%%%%%%%%%%
\renewcommand{\baselinestretch}{1.1}
%%%%%%%%%%
\renewcommand{\thefootnote}{\fnsymbol{footnote}}



\begin{document}

\title{New $5$-Designs Constructed from the Lifted Golay Code over 
{\bf Z}$_4$\footnote{To appear in J. Combin. Designs}}

\author{
Masaaki Harada \\
Department of Mathematical Sciences \\
Yamagata University \\
Yamagata 990, Japan}


\maketitle


\maketitle

\begin{abstract}
It is shown that the lifted Golay code over $\ZZ_4$ contains
several $5$-designs.
In particular, a $5$-$(24,12,1584)$ design and a $5$-$(24,12,1632)$ design
are constructed for the first time.
\end{abstract}


%%%%%%%%%%%%%%%%%%%%%    SECTION 1   %%%%%%%%%%%%%%%%%%%%%

\section{Introduction}

A $t$-$(v,k,\lambda)$ design $D$ is a set of $v$ points
with a collection of $k$-subsets called blocks, so that any $t$-points
are contained in exactly $\lambda$ blocks.
A design with no repeated block is called {\em simple}.
In this paper, we consider only simple designs.
The complementary design of $D$ is a design obtained 
by replacing each block in $D$ by its complement.
The incidence matrix of $D$ is the matrix $M=(m_{ij})$ where $m_{ij}=1$
if the $j$-th point is contained in the $i$-th block and $m_{ij}=0$
otherwise.
Two designs are {\em isomorphic} if the incidence matrix of one
design can be obtained from the incidence matrix of the other
by permuting its rows and columns.

A fundamental problem in design theory is to determine if there exists 
a design for a given set of parameters.
Coding theory has made a substantial contribution to design theory.
For example, the Assmus-Mattson theorem~\cite{A-M}
determines whether the codewords of a specified weight in
a code over $GF(q)$ form a $t$-design.
In particular, it is well known that the codewords of weight $8$ in the binary
extended Golay code form the Steiner system $S(5,8,24)$, 
which is the unique $5$-$(24,8,1)$ design.  
Moreover, the codewords of weight $12$ form a $5$-$(24,12,48)$ design
which is known as the dodecad design.
This $5$-design is a unique design for the parameters  
such that every two blocks intersect in an even number of points 
(cf.~\cite{tonchev-witt}).

Recently a number of papers have studied self-dual codes over $\ZZ_4$
the ring of integers modulo $4$
(cf., e.g. \cite{Z4-B-S-Cal}, \cite{Z4-B-S-B-M}, \cite{Z4-C-S}, 
\cite{Z4-G-H-DCC} and the references given therein).
Connections of self-dual codes over $\ZZ_4$ with unimodular lattices and
binary nonlinear codes have been found.
In this paper, we present a conncetion with desgins.
Type~II codes have been introduced 
by Bonnecaze, Sol\'e, Bachoc and Mourrain~\cite{Z4-B-S-B-M},
as a class of self-dual codes over $\ZZ_4$.
This class includes the octacode $O_8$ of length $8$ and 
the Hensel lifted Golay code of length $24$.
In this paper, we demonstrate that certain codewords in the lifted Golay
code over $\ZZ_4$ form $5$-designs.  
In particular, a $5$-$(24,12,1584)$ design and a $5$-$(24,12,1632)$ design
are constructed.
	From \cite{KMM} and 
Table 3.37 in~\cite{CRC-Handbook}, these two designs
are the first designs with these parameters.

%%%%%%%%%%%%%%%%%%%%%    SECTION 2   %%%%%%%%%%%%%%%%%%%%%

\section{Self-dual codes and the lifted Golay code}

\subsection{Self-dual codes}
A code $C$ of length $n$ over $\ZZ_4$ is an additive subgroup of $\ZZ_4^n$.
An element of $C$ is called a codeword.
The Hamming weight of a codeword is the number of its non-zero components.
The dual code $C^\perp$ of $C$ is defined as 
$C^\perp=\{x \in {\ZZ}_4^n |\ x \cdot y=0 \mbox{ for all } y\in C\}$
where $x \cdot y = x_1 y_1 + \cdots + x_n y_n \pmod 4$, 
$x=(x_1,\dots,x_n)$ and $y=(y_1,\dots,y_n)$.  
$C$ is {\em self-dual} if $C=C^\perp$.
We say that two codes are {\em permutation-equivalent} 
if one can be obtained from the other by permuting the coordinates.
The symmetrized weight enumerator (s.w.e.) of a code $C$ over $\ZZ_4$ is
\[
swe_C(X,Y,Z) = \sum_{c \in C}
X^{n_0(c)}Y^{n_{1}(c)}Z^{n_2(c)},
\]
where $n_0(c), n_1(c)$ and $n_2(c)$ are the numbers of $0, \pm 1$ and
$2$ components of $c$, respectively.


Any code is permutation-equivalent to a code with generator matrix of the form
\begin{equation}
\label{Z4-g-matrix}
\left(\begin{array}{ccc}
I_{k_1} & A & B \\
0    &2I_{k_2} & 2D \\
\end{array}\right),
\end{equation}
where $A$ and $D$ are matrices over $\ZZ_2$ and $B$ is a matrix
over $\ZZ_4$.
We say that a code with generator matrix (\ref{Z4-g-matrix}) is of 
{\em type~$4^{k_1}2^{k_2}$} (cf.~\cite{Z4-C-S}).
Every code $C$ over $\ZZ_4$ has two binary codes 
$C^{(1)}$ and $C^{(2)}$ associated with $C$:
\begin{eqnarray*}
C^{(1)}         &=& \{ c \pmod 2\ |\ c \in C \} \mbox{  and} \\
C^{(2)}        &=& \{ \frac{1}{2}c\ |\ c \in C,\ c \equiv 0 \pmod 2 \}.
\end{eqnarray*}
If $C$ is of type~$4^{k_1}2^{k_2}$ then
$C^{(1)}$ is a binary $[n,k_1]$ code and $C^{(2)}$ is a binary 
$[n,k_1+k_2]$ code.   
Moreover, 
if $C$ is a self-dual code of length $n$ and type~$4^{\frac{n}{2}}$,
then $C^{(1)} = C^{(2)}$ and $C^{(1)}$ is a doubly-even self-dual code
(cf.~\cite{Z4-C-S}).
Our terminology for codes over $\ZZ_4$ follows that in~\cite{Z4-C-S}.  


%%%%%%%%%%%%%%%
\subsection{The lifted Golay code}

The lifted Golay code $G_{24}$ over $\ZZ_4$ is defined in~\cite{Z4-B-S-Cal}
as the extended Hensel lifted quadratic residue code of length $24$.
$G_{24}$ is a Type~II code constructed from 
the cyclic code with generator polynomial
\[
x^{11} + 2x^{10} + 3x^{9} + 3x^{7} + 3x^{6} + 3x^{5} + 2x^{4} + x + 3,
\]
by appending $3$ to the last coordinate of the generator vectors.
The s.w.e. of $G_{24}$ is given in~\cite{Z4-B-S-B-M}:
\begin{eqnarray*}
W&=&
X^{24}
+{Z^{24}}
+24288{Y^{16}}{Z^8}
+4096{Y^{24}}
+61824{X}{Y^{12}}{Z^{11}}
\\ &&
+12144{X^2}{Y^8}{Z^{14}}
+680064{X^2}{Y^{16}}{Z^6}
+1133440{X^3}{Y^{12}}{Z^9}
+170016{X^4}{Y^8}{Z^{12}}
\\ &&
+1700160{X^4}{Y^{16}}{Z^4}
+4080384{X^5}{Y^{12}}{Z^7}
+765072{X^6}{Y^8}{Z^{10}}
+680064{X^6}{Y^{16}}{Z^2}
\\ &&
+4080384{X^7}{Y^{12}}{Z^5}
+759{X^8}{Z^{16}}
+1214400{X^8}{Y^8}{Z^8}
+24288{X^8}{Y^{16}}
\\ &&
+1133440{X^9}{Y^{12}}{Z^3}
+765072{X^{10}}{Y^8}{Z^6}
+61824{X^{11}}{Y^{12}}{Z}
+2576{X^{12}}{Z^{12}}
\\ &&
+170016{X^{12}}{Y^8}{Z^4}
+12144{X^{14}}{Y^8}{Z^2}
+759{X^{16}}{Z^8}.
\end{eqnarray*}
%%%
%%%
%%%




The automorphism group of the binary Golay code is the Mathieu group
$M_{24}$.
In~\cite{sole-private} Chapman shows that the automorphism group
of the lifted Golay code is $SL(2,23)$.


Since $G_{24}$ is of type~$4^{12}$, $G_{24}^{(1)} = G_{24}^{(2)}$.
Moreover $G_{24}^{(1)}$ is the binary Golay code of length $24$.
Thus the supports of the codewords of Hamming weight $8$ 
form the Steiner system $S(5,8,24)$.
Similarly, the supports of the $2576$ codewords corresponding to
$X^{12}Z^{12}$ in $W$ form a $5$-$(24,12,48)$ design
and the supports of the $759$ codewords corresponding to
$X^{8}Z^{16}$ in $W$ form a complementary design of $S(5,8,24)$.
It is shown in~\cite{Z4-G-H-DCC} that the supports of the codewords of 
Hamming weight $10$ in the lifted Golay code and certain extremal 
double circulant Type~II
codes of length $24$ form a $5$-$(24,10,36)$ design.
In this paper, we consider not only the codewords
of Hamming weight $12$ but also the codewords corresponding to
$X^{12}Y^{8}Z^4$.
These are used to
construct a $5$-$(24,12,1584)$ design and a $5$-$(24,12,1632)$ design.

%%%%%%%%%%%%%%%%%%%%%%%% SECTION 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{5-designs in the lifted Golay code}

\subsection{A 5-(24, 12, 1584) design and a 5-(24, 12, 1632) design}
We first investigate the $170016$ codewords corresponding to 
$X^{12}Y^{8}Z^{4}$ in $W$.
Let $A$ be a $170016$ by $24$ matrix whose rows are the above
codewords.
If $v$ is a codeword corresponding to $X^{12}Y^{8}Z^{4}$
then $3v$ is also a codeword corresponding to $X^{12}Y^{8}Z^{4}$,
but $2v$ is not.
Moreover it is easy to see that 
\[
A=
\left(\begin{array}{r}
B_1       \\
3B_1      \\
\end{array}\right),
\]
where $B_1=(b_{ij})$ is an $85008$ by $24$ matrix over $\ZZ_4$.
Now define an $85008$ by $24$ $(1,0)$-matrix $M_1= (m_{ij})$ where
$m_{ij}=1$ if $b_{ij} \ne 0$ and $m_{ij}=0$ otherwise.
We have verified by computer that $M_1$ is an incidence matrix
of a (simple) $5$-$(24,12,1584)$ design.



%%%%%%%%%%%%%%%%%%%%%%%%%


As mentioned in~Section~2, the supports of the codewords corresponding to
$X^{12}Z^{12}$ in $W$ form a simple $5$-$(24,12,48)$ design which is
isomorphic to the dodecad design.
Let $M_2$ be the incidence matrix of this design.
Then it is easy to see that the matrix
\[
M_3=
\left(\begin{array}{c}
M_1       \\
M_2      \\
\end{array}\right),
\]
is an incidence matrix for a $5$-$(24,12,1632)$ design, however
this design may contain a repeated block.
Let $v$ and $w$ be codewords corresponding to $X^{12}Y^{8}Z^{4}$
and $X^{12}Z^{12}$, respectively.
Assume that $v$ and $w$ have identical supports in $M_3$.
Then the codeword $v + w$ corresponds to $X^{16}Y^{8}$, which is
a contradiction.
Therefore the design is simple.


Kramer, Magliveras and Mesner~\cite{KMM} determined all 5-designs
with the Mathieu group $M_{24}$ as the automorphism group.
Thus the automorphism groups of our 5-designs are not $M_{24}$.
Information on simple $t$-designs is given in Table~3.37 
of~\cite[p.~52]{CRC-Handbook}.
	From this table,  
our designs are the first $5$-designs with these parameters.
Note that the table in~\cite{CRC-Handbook} misses some 5-designs
in~\cite{KMM}.


Since one can easily construct the two $5$-designs from the lifted Golay
code, to save space the incidence matrices are not listed here.
However the incidence matrices are available on the world
wide web at \verb+ http://kszaoh1.kj.yamagata-u.ac.jp/harada+.




%%%%%%%%%%%%%%%%%%%
\subsection{More 5-designs}

Our computer search shows that the supports of the codewords of
Hamming weight $13$ form the complementary design of a 
$5$-$(24,11,336)$ design.
Let $M_4$ be the matrix over $\ZZ_4$ obtained from the codewords of
Hamming weight $13$.
Since the Hamming weight $13$ corresponds to $61824X^{11}Y^{12}Z$ in $W$,
\[
M_4 \pmod 2 \equiv
\left(\begin{array}{c}
M_2 \\
M_2 \\
\vdots \\
M_2 
\end{array}\right).
\]
Moreover it is not hard to see that the automorphism group of this design
is $M_{24}$.  Thus this design must be isomorphic to the design 
in~\cite{KMM}.
In addition, the supports of the $24288$ codewords corresponding to
$X^{8}Y^{16}$ in $W$ form a complementary design of
the Steiner system $S(5,8,24)$.


%%%%%%%%%%%%%%
\subsection{Summary}
%In this paper, we presented that the lifted Golay code $G_{24}$ over $\ZZ_4$
%contains at least eight $5$-designs with at least six
%different parameters, two of which are constructed here for the first time.

As a summary, we give $5$-designs in the lifted Golay code in the
following proposition.  



\begin{prop}
There exist $5$-$(24,12,\lambda)$ designs for $\lambda = 1584$ and $1632$.
The lifted Golay code contains $5$-$(24,k,\lambda)$ designs for
$(k,\lambda) = (8,1), (10,36), (11,336), (12,48), (12,1584)$
and $(12,1632)$.
\end{prop}



%%%%%%%%%%%%%%%%%%%%%%%% SECTION 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Concluding remarks}



It is well known that the block intersection numbers of $S(5,8,24)$
are $0,2$ and $4$ and the incidence matrix of $S(5,8,24)$ generates 
the binary Golay code.
We have verified that the incidence matrix of any of the above eight
designs cannot generate a self-orthogonal code over $\ZZ_4$,
as well as the lifted Golay code.

Since the supports of the codewords of Hamming weight $8$
form $S(5,8,24)$, its automorphism group is $M_{24}$.
It is shown in~\cite{Z4-B-S-Cal} that the supports of the codewords
of Hamming weight $10$ form a $3$-$(24,10,360)$ design and $PSL(2,23)$
acts on the design.  This design is also a $5$-design.
Let $S$ be the set of the codewords of Hamming weight $10$, 
then $S \pmod 2$ is the $S(5,8,24)$.
Kitazume~\cite{kitazume-private} shows that the automorphism
group of the design is $PSL(2,23)$ using properties
of the design and $S(5,8,24)$.


Now we give an observation of the extremal Type~II codes 
in~\cite{Z4-G-H-DCC} such that the supports of the codewords of
Hamming weight $10$ form $5$-$(24,10,36)$ designs.

\begin{prop}
Let $D$ be a double circulant code of length $24$ such that 
$D^{(1)} = D^{(2)}$, $D^{(1)}$ is the binary Golay code and 
$D$ has the same symmetrized weight enumerator as the lifted Golay
code.
Then the supports of the codewords of
Hamming weight $10$ in $D$ form a $5$-$(24,10,36)$ design.
\end{prop}

We conjecture that the above proposition is ture for a code satisfying
the condition.
In general, we prompt the following question:


\bigskip
\noindent
{\bf Question.} Is there a result analogous to the Assmus-Mattson
theorem for a code over $\ZZ_4$?





\bigskip
\noindent
{\bf Acknowledgments.}
The author would like to thank Dr. Masaaki Kitazume for useful
discussions and comments.
The author would like to thank 
Dr. Edward F. Assmus, Jr., Dr. Steven T. Dougherty, 
Dr. T. Aaron Gulliver, Dr. Patrick Sol\'e and
Dr. Vladimir D. Tonchev
for reading the manuscript and making helpful comments.
The author would like to thank the referees for their useful comments,
in particular one of them supplied a useful reference~\cite{KMM}.
Thanks are due also to Dr. Akihiro Munemasa for helpful conversations.



%%%%%%%%%%%%%%%%%  References  %%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{99}

\bibitem{A-M} E.F. Assmus, Jr., and H.F. Mattson, Jr.,
{\sl New 5-designs},
{J. Combin. Theory}
{\bf 6} (1969), 122--151.

\bibitem{Z4-B-S-Cal} A. Bonnecaze, P. Sol\'e and A.R. Calderbank,
{\sl Quaternary quadratic residue codes and unimodular lattices},
{IEEE\ Trans.\ Inform.\ Theory}
{\bf 41} (1995), 366--377.

\bibitem{Z4-B-S-B-M} A. Bonnecaze, P. Sol\'e, C. Bachoc and B. Mourrain,
{\sl Type II codes over $\ZZ_4$},
{IEEE\ Trans.\ Inform.\ Theory}
{\bf 43} (1997), 969--976.


\bibitem{CRC-Handbook} C.J. Colbourn and J.H. Dinitz,
{\sl The CRC handbook of combinatorial designs},
CRC Press, Boca Raton, 
1996.

\bibitem{Z4-C-S} J.H. Conway and N.J.A. Sloane,
{\sl Self-dual codes over the integers modulo 4},
{J.\ Combin.\ Theory~Ser. A}
{\bf 62} (1993), 30--45.

\bibitem{Z4-G-H-DCC} T.A. Gulliver and M. Harada,
{\sl Extremal double circulant Type II codes over ${\ZZ}_4$ 
and construction of 5-$(24, 10, 36)$ designs},
(submitted to Discrete Math.).

\bibitem{kitazume-private}\ M. Kitazume,
private communication, October 1996.

\bibitem{KMM} E.S. Kramer, S.S. Magliveras and D.M. Mesner,
{\sl $t$-designs from the large Mathieu groups},
{Discrete Math.}
{\bf 36} (1981), 171--189.



\bibitem{sole-private} P. Sol\'e,
private communication, October 1996.


\bibitem{tonchev-witt} V.D. Tonchev,
{\sl A characterization of designs related to dodecads in the Witt
system $S(5,8,24)$},
{J.\ Combin.\ Theory~Ser. A}
{\bf 43} (1986), 219--227.



\end{thebibliography}


\end{document}



