\documentclass[12pt]{article}
% \documentstyle[12pt]{article}

\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newcommand{\Proof}{ \noindent{\bf Proof:}\quad }
\newcommand{\qed  }{\hfill$\Box$\medskip}
\newcommand{\Ff}{{\bf F}}
\newcommand{\Zz}{{\bf Z}}

\title{Small additive quaternary codes}
\author{A. Blokhuis \& A. E. Brouwer}
\begin{document}
\maketitle

\begin{abstract}
We determine the parameters of the optimal additive quaternary
codes of length at most 12 over $\Zz_2 \times \Zz_2$.
Equivalently, we determine how many lines one can pick
in a binary projective space such that any $t$ are independent.
Or again, how many lines one can pick in a binary projective space
such that no hyperplane contains more than $m$ of them.
\end{abstract}

\section{Introduction}
Let $Q$ be a finite set (called {\em alphabet}).
A code of word length $n$ and minimum distance $d$ over $Q$
is a collection $C$ of elements of $Q^n$, called codewords,
such that any two differ in at least $d$ positions.
The code is called {\em optimal} when it has the largest possible
size given $n$ and $d$ (and $Q$).
Now suppose that $Q$ has the structure of an Abelian group.
Then also $Q^n$ has the structure of an Abelian group, and
we call the code {\em additive} if it is a subgroup of $Q^n$,
i.e., when the coordinatewise sum of two codewords again is a codeword.
Finally, if $Q$ is a field, then $Q^n$ is a vector space over $Q$,
and we call the code {\em linear} when it is a subspace of $Q^n$.

In this note we determine (the parameters of) the optimal
additive codes of word length at most 12 over the alphabet
$Q := \Zz_2 \times \Zz_2$ (with two exceptions). Some of
the codes found improve on the best quaternary codes known.

An additive code over $Q$ is a vector space over $\Ff_2$,
of some dimension, $k$ say, and hence has size $2^k$.
In this note we shall call it an $[n,k,d]$-code.

We shall also consider linear codes over the alphabet $\Ff_4$,
and call them $[n,k,d]_4$ codes.

Of course a linear $[n,k,d]_4$ code is an additive $[n,2k,d]$ code,
but there are additive quaternary codes better
than any linear code as we shall see below.

\section{Projective formulation}
We can view an $[n,k,d]$-code as a binary code of word length $2n$
and dimension $k$. Write down a generator matrix of the latter code,
and view the $2n$ columns as points in a vector space of dimension
$k$ over $\Ff_2$. Look at the subspaces that are spanned by two columns
belonging to the same $Q$-coordinate. We find $n$ subspaces spanned
by two points, such that each hyperplane contains at most $n-d$ of them.
Formulating this projectively, an additive $[n,k,d]$-code is equivalent
to a collection of $n$ lines in $PG(k-1,2)$ such that each hyperplane
contains at most $n-d$ of these lines.

Dually, an additive $[n,k,d]$-code is equivalent to a collection
of $n$ lines in $PG(2n-k-1,2)$ such that any $d-1$ are independent,
i.e., span a $PG(2d-3,2)$.

(Here, the lines may be repeated, and a line is the span of two
not necessarily distinct points.)

Let $Q(n,d)$ be the maximum possible value of $k$ for an additive
$[n,k,d]$-code over $Q$.

\begin{Lemma} $Q(n,d) = 0$ when $n < d$.
\end{Lemma}

\begin{Lemma} $Q(n,1) = 2n$.
\end{Lemma}

(Indeed, $n$ lines span at most a $2n$-space.)

\begin{Lemma} $Q(n,2) = 2n-2$ if $n \ge 1$.
\end{Lemma}

(Indeed, $PG(2n-k-1,2)$ contains $PG(1,2)$ precisely when $k \le 2n-2$.)

\begin{Lemma} $Q(n,3) = 2n-h$ where $h$ is the smallest number
such that $h$ is even and $2^h \ge 3n+1$, or $h$ is odd and $2^h \ge 3n+5$.
\end{Lemma}

(Indeed, we have to find $n$ pairwise disjoint lines in $PG(h-1,2)$.
If $h$ is even, then $PG(h-1,2)$ has a spread and the condition is
$n \le (2^h - 1)/3$. If $h$ is odd and at least 3, then any partial spread
leaves at least 4 points uncovered, and there do exist partial spreads
that leave precisely 4 points uncovered, so the condition is
$n \le (2^h - 5)/3$.)

For example, we find a $[9,13,3]$ additive code over $Q$, that is,
a quaternary code of word length 9, minimum distance 3 and 8192 code words.
The best linear quaternary code of word length 9 and minimum distance 3
has only 4096 code words.

One way of constructing the partial spreads needed in the previous lemma
is by induction on the dimension, repeatedly using the following lemma.

\begin{Lemma}
\label{pspread}
If $h > 1$ then $PG(h+1,2) \setminus PG(h-1,2)$ has a spread
(with $2^h$ lines). No hyperplane contains more than $2^{h-2}$ lines
from this spread, and the hyperplanes on $PG(h-1,2)$ contain no
lines from this spread.
\end{Lemma}

(Indeed, let $F = \Ff_q$, where $q = 2^h$. Since $h > 1$,
we can find three nonzero elements $a,b,c$ in $F$ with $a+b+c=0$.
Now consider the $(h+2)$-space $V$ of vectors $(d,i,j)$, with $d \in F$
and $i,j \in \Ff_2$. The $2^h$ lines
$\{(ax,0,1),(bx,1,0),(cx,1,1)\}$ with $x \in F$
are pairwise disjoint lines in the projective space $PV$ (identified
with $V \setminus \{0\}$), and the complement of their union is
the $PG(h-1,2)$ consisting of the points $(z,0,0)$.
If a hyperplane $H$ contains $N$ of these lines, then
$2^h-N+3N = |H \setminus PG(h-1,2)|$, so that $N = 0$ or $N = 2^{h-2}$.)

For example, we find a $[8,5,6]$ additive code over $Q$.
(And, more generally, we find for $q = 2^h$ that $Q(q,3q/4) \ge h+2$.)

To this partial spread we may add an arbitrary set of lines
in the so far empty $PG(h-1,2)$. Thus, if a $[n,h,d]$ exists,
then we find an $[n+q, h+2, d+3q/4]$ (where $q = 2^h$)
as long as $d \le q/4$.

For example, since $[3,3,2]$ exists, we find an $[11,5,8]$ code.

\section{Linearity over $\Ff_4$}
\begin{Proposition}
Let ${\cal L}$ be a collection of 2-spaces in a vector space
$V$ of dimension $2k$ over $\Ff_2$. Then $V$ can be given
a structure $V_4$ of vector space over $\Ff_4$, preserving
the old addition, and such that each element of ${\cal L}$
becomes a 1-space in $V_4$ if and only if each subcollection of
${\cal L}$ spans an even-dimensional subspace in $V$.
\end{Proposition}

\Proof
`Only if' is obvious. For the `if' part we may assume that
${\cal L}$ spans $V$. Each line $L$ has precisely two possible
$\Ff_4$-structures---indeed, if $\Ff_4 = \{0,1,\omega,\omega^2\}$
then it suffices to define multiplication by $\omega$, and there
are two possible 3-cycles on the nonzero elements of $L$.
Our job is to choose compatible $\Ff_4$-structures for all
lines in ${\cal L}$, so that multiplication by $\omega$ becomes
a linear transformation.

To this end, construct a hypergraph ${\cal E}$ with vertex set
${\cal L}$, where the edges are the minimal dependent sets of lines.
If $L \in E$ for some edge $E$ in ${\cal E}$, then an $\Ff_4$-structure
on $L$ determines uniquely an $\Ff_4$-structure on each $M \in E$.
Indeed, since every collection of lines spans an even-dimensional
subspace of $V$, and $E$ is a minimal dependent collection of lines
we can put $E = \{L_1,...,L_m\}$ and $L_i = \{0,x_i,y_i,z_i\}$
where $\sum x_i = \sum y_i = \sum z_i = 0$. To see this, note that
$x_m$ must be dependent on the set of $3m-3$ points of $L_i$, $i<m$,
and this dependence can be written so that it involves at most one
(but also at least one) point of each of the $L_i$. The corresponding
dependence for $y_m$ necessarily involves different points, since
otherwise combining them would yield a dependence of fewer than $m$
of the $L_i$. Now if $\omega x_1 = y_1$
then the only possible choice of $\Ff_4$-structure on the span of $E$
is obtained by putting $\omega x_i = y_i$ and $\omega y_i = z_i$ for all $i$.

So, it remains to check that there is no bad circuit in ${\cal E}$,
where consecutive edges force the $\Ff_4$-structure until we come
back to the starting point and force an $\Ff_4$-structure different
from the one we started with.
Assume we have a minimal counterexample to the proposition, with
bad circuit formed by the edges $E_1$, ..., $E_g$, where the edges
$E_i$ and $E_{i+1}$ have the line $M_i$ in common (indices mod $g$).
If some vertex $M_i$ occurs in some edge $E_j$ other than
$E_i$ and $E_{i+1}$, then we find a shorter bad circuit.
If some edge $E_j$ contains a line $M$ other than $M_j$ and $M_{j-1}$,
then make the quotient $V/M$, sending each line $L$ to
$(L+M)/M$. Again we find a smaller counterexample.
So, our edges all have size 2 (each containing the same line twice)
and we have a chain of equalities, which cannot be bad. QED

\medskip
This proposition explains why in all small cases the best
even-dimensional additive codes are in fact $\Ff_4$-linear.

In coding terms it says that an additive code over $Q$
is a linear code over $\Ff_4$ if and only if it and all
its truncations are evendimensional.

\section{Table}
The table below gives the maximum possible minimum distance $d$ for a code
with given word length $n$ and dimension $k$.

{\footnotesize\noindent\hspace{-50pt}
\begin{tabular}{c|cc|cc|cc|cc|cc|cc|cc|cc|cc|cc|cc|cc|}\hline
$n\backslash k$&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&21&22&23&24\\
\hline\\
1&1&1\\
2&2&2&1&1\\
3&3&3&2&2&1&1\\
4&4&4&3&3&2&2&1&1\\
5&5&5&4&4&3&3&2&2&1&1\\
6&6&6&5&4&4&4&3&2&2&2&1&1\\
7&7&7&6&5&5&4&4&3&3&2&2&2&1&1\\
8&8&8&6&6&6&5&4&4&3&3&3&2&2&2&1&1\\
9&9&9&7&7&6&6&5&5&4&4&3&3&3&2&2&2&1&1\\
10&10&10&8&8&7&6&6&6&5&5&4&4&3&3&2&2&2&2&1&1\\
11&11&11&9&8&8&7&7&6&6&6&5&5&4&4&3&3&2&2&2&2&1&1\\
12&12&12&10&9&8&8&8&7&?&6&6&6&5&?&4&4&3&3&2&2&2&2&1&1\\
\end{tabular}
}

\medskip
For comparison a small table with the maximum possible minimum distance
of quaternary linear codes.
\medskip

{\footnotesize\noindent
\begin{tabular}{c|cccccccccccc}\hline
$n\backslash k$&1&2&3&4&5&6&7&8&9&10&11&12\\
\hline\\
1&1\\
2&2&1\\
3&3&2&1\\
4&4&3&2&1\\
5&5&4&3&2&1\\
6&6&4&4&2&2&1\\
7&7&5&4&3&2&2&1\\
8&8&6&5&4&3&2&2&1\\
9&9&7&6&5&4&3&2&2&1\\
10&10&8&6&6&5&4&3&2&2&1\\
11&11&8&7&6&6&5&4&3&2&2&1\\
12&12&9&8&7&6&6&4&4&3&2&2&1\\
\end{tabular}
}

\medskip
The lower bounds implicit in this latter table follow from the
existence of quaternary linear $[6,3,4]_4$ and $[12,6,6]_4$
quadratic residue codes, the $[10,2,8]_4$ obtained by juxtaposing
two $[5,2,4]_4$ codes, the $[12,2,9]_4$ obtained by shortening the
$[15,2,12]_4$ (from juxtaposing three $[5,2,4]_4$ codes),
the $[12,9,3]_4$ obtained by shortening the
$[21,18,3]_4$ Hamming code, the $[12,8,4]_4$ obtained by shortening the
$[17,13,4]_4$ (dual of the elliptic quadric), the $[13,4,8]_4$ obtained
by shortening the $[18,9,8]_4$ self-dual code constructed in \cite{MOSW}
(and the trivial $[n,n,1]_4$ and $[n,n-1,2]_4$ and $[n,1,n]_4$ codes).
Since the bounds given for $[n,2k,d]$ equal those given for $[n,k,d]_4$,
this proves all lower bounds for even $k$.

For a database of quaternary linear codes, see, e.g., \cite{www}.
For bounds on general quaternary codes, see \cite{BBKO}.

Concerning the lower bounds for odd $k$, we already explained all
values 1, 2 and 3. Trivially $Q(n,d) \le Q(n-1,d-1)$ and
$Q(n,d) \le Q(n-1,d)+2$. Remain 5 lower bounds that require
explanation. We find $[12,3,10]$ by juxtaposing two $[6,3,5]$ codes.
We found $[8,5,6]$ and $[11,5,8]$ codes in the discussion
following Lemma \ref{pspread}.

A $[7,7,4]$ can be constructed by taking the additive code
generated by the vector (3333333) and the 7 cyclic shifts of
(1110100) and of (0020222), where 00,01,10,11 are written 0,1,2,3.

We find a $[12,7,8]$ by taking the additive code generated
by the 7 vectors

\begin{center}
{\small
\begin{tabular}{ccc}
110301220013 & 022000231231 & 000220111111 \\
220000123123 & 020011022311 & 000202222222 \\
001101021133 \\
\end{tabular}}
\end{center}

We find a $[12,13,5]$ by taking the additive code generated
by the 13 vectors

\begin{center}
{\small
\begin{tabular}{ccc}
111110000000 & 130102100001 & 022001101000 \\
110001110000 & 110020201000 & 021200001001 \\
101001001100 & 011121021001 & 131121002002 \\
010100101010 & 101100102200 \\
211001000001 & 000121002020 \\
\end{tabular}}
\end{center}

\medskip
Next the upper bounds. We already explained all values 1, 2,
and the trivial inequalities $Q(n,d) \le Q(n-1,d-1)$ and $Q(n,d) \le Q(n-1,d)+2$
provide the trivial upper bounds. Next, the inequality $d \le n$ for codes with
at least two code words explains the `$k = 1$' column of the table.
Remain to be explained why no $[8,3,7]$, $[6,4,5]$, $[11,4,9]$,
$[12,5,9]$, $[10,6,7]$, $[8,7,5]$, $[8,9,4]$, $[12,9,7]$, $[12,14,5]$ exist.

By the linear programming bound, there are no $[8,3,7]$, $[6,4,5]$,
or $[11,4,9]$ codes, not even arbitrary quaternary codes
of the same size, word length and minimum distance.

Remain the 6 cases $[12,5,9]$, $[10,6,7]$, $[8,7,5]$,
$[8,9,4]$, $[12,9,7]$, $[12,14,5]$.

\subsection{No $[12,5,9]$ exists}
Suppose we have a collection of 12 lines (let us call them {\em code lines})
in $PG(4,2)$, at most 3 in any hyperplane.
On each line we have 7 hyperplanes, and $10 > 7$,
so there are no repeated code lines.

Given a code line $L$, let there be $n_j$ hyperplanes on $L$ that contain $j$
other code lines. We find $n_0 + n_1 + n_2 = 7$ and $n_1 + 2n_2 = 11 + 2t$
where $t$ is the number of code lines that meet $L$ in one point.
Thus $2n_0 + n_1 = 3 - 2t$, so that each code line meets at most
one other code line.

Let there be $m_i$ hyperplanes containing $i$ code lines.
Then $m_0 + m_1 + m_2 + m_3 = 31$ and $m_1 + 2m_2 + 3m_3 = 84$ and
$m_2 + 3m_3 = 66 + 2s$ where $s$ is the number of pairs of intersecting
code lines. Thus, $3m_0 + m_1 = 3 \cdot 31 - 2 \cdot 84 + 66 + 2s = 2s - 9$.

Let $H$ be a hyperplane with $h$ code lines.
Outside $H$ we see $12-h$ pairs of points, that is, $24-2h$ points,
in a 16-set. Thus, at least $8-2h$ points are repeated, and $s \ge 8-2h$.
Since $s \le 6$ we cannot have $h = 0$, so $m_0 = 0$.
Since $m_1 = 3m_0 + m_1 = 2s - 9 \ne 0$ we can take $h = 1$
and find $s = 6$.

Now each code line meets a unique other code line, so $t = 1$
and $n_0 = 0$, that is, no line is the only code line in a hyperplane,
and $m_1 = 0$, contradiction.

\subsection{No $[10,6,7]$ exists}
Suppose we have a collection of 10 lines, called code lines, in $PG(5,2)$,
at most 3 in any hyperplane.

These code lines must be disjoint, for if $L$ and $M$ are two
intersecting code lines, distinct triples $L,M,N$ of code lines
are in different hyperplanes, so $L,M$ are in at least 8 hyperplanes,
but a plane is in only 7 hyperplanes.

The 10 code lines contain 30 points, called code points.
Every hyperplane has 10, 12, 14 or 16 code points.
We shall call a thing with $i$ code points an $i$-thing.

There are at most 3 code points per line, 5 per plane,
9 per solid ($PG(3,2)$) and 16 per hyperplane.
[Indeed, if a solid contains $a$ code points, then altogether
we find at most $a + 3(16-a)$ code points, so that $a \le 9$.
And if a plane contains $b$ code points, then altogether
we find at most $b + 7(9-b)$ code points, so that $b \le 5$.]

The 7 solids around a 5-plane $\pi$ contain 25 more code points,
so at least 4 of them contain 4 more code points.
Since the solids around a plane form a Fano plane, and
since a hyperplane has at most 16 code points, the distribution of the
code points around $\pi$ is necessarily as follows: four $5+4$-solids,
forming a hyperoval in the local Fano plane, and three $5+3$-solids
forming a line.

The 15 planes around a 3-line together contain 27 more points.
These 15 planes form a $PG(3,2)$, of which the points are labeled with 
the integers 2, 1 and 0 (where a $(3+i)$-plane has label $i$),
such that all the labels add up to 27, and if we see a point with label 2,
then four lines through it have labels adding up to 6,
while 3 (coplanar) lines through it have labels adding up to 5.
It follows that all labels are 2 or 1,
and that the 3 points labeled 1 are on a line. As a consequence
we see that a 3-line is on three 14-hyperplanes and twelve
16-hyperplanes and not on any 12-hyperplane. Since a 12-hyperplane
necessarily contains a 3-line, there are no 12-hyperplanes.

Let there be $h_i$ $i$-hyperplanes. We find
$h_{10}+h_{14}+h_{16} = 63$, $10h_{10}+14h_{14}+16h_{16} = 30 \cdot 31$
and $45h_{10}+91h_{14}+120h_{16}=15 \cdot 29 \cdot 15$.
This gives $h_{10}=8$, $h_{14}=15$, and $h_{16}=40$.
In particular, there are 10-hyperplanes.

Let $H$ be a 10-hyperplane. Then $H$ does not contain a 3-line.
Each $k$-solid in $H$ is contained in three hyperplanes,
and the types of these turn out to be determined by $k$:
$k=0: 10+10+10$, $k=2: 10+10+14$, $k=3: 10+10+16$,
$k=4: 10+14+14$, $k=5: 10+14+16$, $k=6: 10+16+16$.

Let $s_k$ denote the number of $k$-solids in $H$.
The other seven 10-hyperplanes intersect $H$ in a solid,
and from this we get $2s_0+s_2+s_3=7$.
We also get the usual equations counting solids with incident
nothings, points, pairs and triples, since our hyperplanes
do not contain 3-lines:
$\sum s_k = 31$, $\sum ks_k=10.15$, $\sum k(k-1)s_k=10.9.7$,
$\sum k(k-1)(k-2)s_k=10.9.8.3$, from which we may compute
$\sum (k-4)(k-5)(k-6)s_k$ and find $20s_0+4s_2+s_3 = 20$.
Combining this with our earlier equation we get $18s_0+3s_2=13$,
which clearly has no solution.

\subsection{No $[8,7,5]$ exists}
Suppose we have a collection of 8 lines, called code lines, in $PG(6,2)$,
at most 3 in any hyperplane.
Three lines are always contained in a hyperplane, so no code line
is contained in the span of three other code lines.

Let there be $p_i$ hyperplanes on a given pair of intersecting
code lines $L$, $M$ containing $i$ other code lines.
Then $p_0 + p_1 = 15$ and $p_1 \ge 3 \cdot 6 = 18$, contradiction.
So, code lines are pairwise disjoint.

Let there be $q_i$ hyperplanes on a given pair of (disjoint)
code lines $L$, $M$ containing $i$ other code lines.
Then $q_0 + q_1 = 7$ and $q_1 = 6 + 2c$, where $c$ is the number
of code lines $N$ such that $L+M+N$ is a 5-space.
Thus $c = 0$, and every triple of code lines spans a 6-space.

This shows that the dual code is a $[8,9,4]$.
Now the next section shows nonexistence.

\subsection{No $[8,9,4]$ exists}
This was too boring to do by hand. A tiny backtrack program
finds no solutions. This took 0.01 seconds.
(Formulation used: Find 8 lines in 7-space, where any three
span a 6-space. This is fast, since 7-space is small.)

\subsection{$[12,9,7]$?}
A $[12,9,6]$ exists, since even $[11,9,6]$ exists.
We do not know whether $[12,9,7]$ exists.

\subsection{$[12,14,5]$?}
A $[12,14,4]$ exists, since even $[11,14,4]$ exists.
We do not know whether $[12,14,5]$ exists.

\begin{thebibliography}{}

\bibitem{BBKO}
G.T. Bogdanova, A.E. Brouwer, S.N. Kapralov \& P.R.J. \"Osterg\aa rd,
{\it Error-Correcting Codes over an Alphabet of Four Elements},
Designs, Codes and Cryptography {\bf 23} (2001) 333-342. 

\bibitem{www} A.E. Brouwer, On-line bounds for linear codes over small fields.
{\tt http://www.win.tue.nl/~aeb/voorlincod.html}

\bibitem{MOSW}
F.J. MacWilliams, A.M. Odlyzko, N.J.A. Sloane \& H.N. Ward,
{\it Self-dual codes over GF(4)}, J. Comb. Th. (A) {\bf 25} (1978) 288-318.
\end{thebibliography}

\end{document}

