# The search of Type I codes

Carolin Hannusch  Faculty of Informatics, University of Debrecen
<EMAIL_ADDRESS>Roland S. Major  Faculty of Informatics,
University of Debrecen
<EMAIL_ADDRESS>
###### Abstract

A self-dual binary linear code is called Type I code if it has singly-even
codewords, i.e. it has codewords with weight divisible by $2.$ The purpose of
this paper is to investigate interesting properties of Type I codes of
different lengths. Further, we build up a computer-based code-searching
program based on our knowledge about Type I codes. Some computation results
achieved by this program are given.
Keywords: Type I codes; self-dual linear codes
AMS Subject Classification: 94B05

##  1 Preliminaries and Motivation

A linear code of length $n$ is a subspace of the $n$-dimensional vectorspace
over a field $\mathbb{F}$. Throughout our paper, all linear codes are binary
codes, i.e. $\mathbb{F}=\mathbb{F}_{2}.$ Let $C$ be a linear code of length
$n$, dimension $k$ with minimum distance $d.$ Then we say that $C$ is an
$(n,k,d)$-code. Any two codewords $x$ and $y$ are orthogonal if their inner
product is $0.$ Each linear code has a dual code
$C^{\bot}=\\{c\in\mathbb{F}_{2}^{n}\mid c\bot x\mbox{ }\forall x\in C\\}.$ If
$C=C^{\bot}$, then $C$ is called self-dual. In this case we have
$k=\frac{n}{2}.$ It is well known (see e.g. Theorem 2.19 in [7]) that each
code $C$ is equivalent to a linear code generated by a generator matrix $G$ of
the form

$G=\left(\begin{array}[]{ccc}I_{k}&|&A\end{array}\right),$

where $I_{k}$ denotes the identity matrix of dimension $k$ and
$A\in\mathcal{M}_{k\times k}(\mathbb{F}_{2}).$ If $C$ is self-dual and it has
codewords of weight divisible by $2,$ then $C$ is called Type I code.
Otherwise (if $C$ has only codewords of weight divisible by $4$) $C$ is called
Type II code. By [8] we have the same upper bound for the minimum distance of
self-dual Type I and Type II codes, namely $d\leq
4\lfloor\frac{n}{24}\rfloor+4$ and $d\leq 4\lfloor\frac{n}{24}\rfloor+6$ if
$n\equiv 22\mod 24.$

Type I codes were investigated in [1], [2] and [5]. The investigation of Type
I codes is interesting, since several open problems can be found in literature
considering self-dual Type I codes (e.g. [4], [6]). For example, the existence
of a Type II self-dual $(72,36,16)$ code is still an open question and it is
equivalent to the existence of a Type I self-dual $(70,35,14)$-code ([4].)
Furthermore, the existence of a Type I self-dual $(56,28,12)$-code is also
still an open question.

This paper is organized as follows. In Section 2 we summarize and introduce
the main theoretical background for our code searching program. In Section 3
we investigate the relation of Type I codes to its neighbors. In Section 4 we
describe the code searching package itself. Afterwards, in Section 5 some
computational results are given. Finally, in Section 6 we draw our conclusion
so far.

##  2 Properties of Type I codes

###  2.1 General properties

###### Proposition 1

Let $n\equiv 0\mod 4$ and $C$ a self-dual binary $(n,k,d)$-code. If $G$ is a
generator matrix of $C$ in standard form, then the number of rows in $G$ with
singly-even weight is even.

Proof.  We denote the generator matrix by $G=\left(\begin{array}[]{c}g_{1}\\\
\vdots\\\ g_{k}\end{array}\right).$ The proposition follows by the fact that
$\textbf{1}\in C$ and $\textbf{1}=\sum_{i=1}^{k}g_{i}.$ Since
$w(c_{1}+c_{2})=w(c_{1})+w(c_{2})-2\mu(c_{1},c_{2}),$ we have
$w(c_{1}+c_{2})\equiv 0\mod 4\Leftrightarrow w(c_{1})\equiv w(c_{2})\mod 4.$
$\hfill\square$

###### Corollary 2.1

Let $G$ be a generator matrix of a Type I code in standard form. Then $G$ has
at least two singly-even rows.

###  2.2 Graph of a generator matrix

###### Definition 1

Let $A$ be a binary matrix with rows $a_{1},\ldots,a_{k}$ and
$w(a_{1})\geq\ldots\geq w(a_{k}).$ Further the $1$-s in row $a_{1}$ are in
consecutive order on the lefthand side, and the $0$-s are in consecutive order
on the righthand side, i.e. there exists a number $1\leq t\leq k,$ such that

$a_{1}=(\underbrace{1\ldots 1}_{t}\underbrace{0\ldots 0}_{k-t}).$

Let $\Gamma$ be a tree graph corresponding to $A$ defined in the following
way: It’s root is the set $\\{1,\ldots,k\\}$. The root has two child nodes:
One is the subset $S_{1}\subset\\{1,\ldots,k\\}$ containing those positions
which are $1$ in $a_{1}.$ Thus $S_{1}=\\{1,\ldots,t\\}.$ The other one is the
subset $S_{2}\subset\\{1,\ldots,k\\}$ containing those positions which are $0$
in $a_{1}.$ Thus $S_{2}=\\{t+1,\ldots,k\\}.$ Each of those nodes has again two
child nodes, defined in the same way. We repeat this step for all nodes and
branches until we get $k$ levels.

###### Example 1

Let

$A=\left(\begin{array}[]{cccccc}1&1&1&1&1&0\\\ 1&1&1&0&0&1\\\ 1&0&0&1&0&1\\\
1&0&0&0&1&0\\\ 0&0&0&1&1&0\\\ 0&0&0&1&0&1\end{array}\right)$

Then the graph $\Gamma$ corresponding to $A$ is:

###### Remark 1

The graph $\Gamma$ has at most $k$ leaf nodes.

###### Proposition 2

Let $A$ be a binary matrix with $k$ rows and let $\Gamma$ be its corresponding
graph defined in Definition 1 . $A$ exists if and only if $\Gamma$ is
connected, it has $k+1$ levels and the union of the leaf nodes is the set
$\\{1,\ldots,k\\}.$

Proof.  Let us denote the nodes of $\Gamma$ by
$S_{0},S_{1},S_{2},\ldots,S_{m},$ where $S_{0}=\\{1,\ldots,k\\}$ and
$S_{i}\subseteq S_{0}$ for each $i\in\\{1,\ldots,m\\}$ and $m$ is an arbitrary
integer. By definition, $\Gamma$ has $k+1$ levels. We use induction on $k.$ If
$k=1,$ then $\Gamma$ has 2 levels and the matrix $A_{1\times k}$ can be
constructed if $S_{1}\cup S_{2}=S_{0}.$ We assume that the statement is true
for $k=f.$ Now, let $k=f+1.$ Then the $f+1^{th}$ row of $A$ can be constructed
by the $f+1^{th}$ level in $\Gamma.$ Any coordinate of this row has an entry
only if it is contained in any leaf node. Thus if the union of the leaf nodes
is $\\{1,\ldots,k\\},$ then the $f+1^{th}$ row of $A$ can be constructed.
Otherwise, it cannot be constructed. $\hfill\square$

###  2.3 The $\mu$ table

Let $C$ be a binary self-dual $(n,k,d)$ code. For all $x,y\in C$ we have
$w(x+y)=w(x)+w(y)-2\mu(x,y),$ where $\mu(x,y)$ denotes the number of
coordinates which are $1$ in both, $x$ and $y.$ Since $d\leq w(x+y)\leq n-d,$
we get borders for $\mu(x,y).$ For example, we search for a singly-even
$(56,28,12)$ Type I code. If it exists, then it has a generator matrix
$G=(I_{28}\mbox{ }A).$ Let $r_{1}$ and $r_{2}$ be two arbitrary rows of $A.$
We summarize the possible values for $\mu(r_{1},r_{2})$ in the following
table.

Table 1: Possible values of $\mu(r_{1},r_{2})$

$w(r_{1}$) $w(r_{2}$) | 27 | 25 | 23 | 21 | 19
---|---|---|---|---|---
27 | - | - | - | - | $\\{18\\}$
25 | - | - | - | $\\{18\\}$ | $\\{16\\}$
23 | - | - | $\\{18\\}$ | $\\{16\\}$ | $\\{14,16\\}$
21 | - | $\\{18\\}$ | $\\{16\\}$ | $\\{14,16\\}$ | $\\{12,14\\}$
19 | $\\{18\\}$ | $\\{16\\}$ | $\\{14,16\\}$ | $\\{12,14\\}$ | $\\{10,12,14\\}$
17 | $\\{16\\}$ | $\\{14,16\\}$ | $\\{12,14\\}$ | $\\{10,12,14\\}$ | $\\{8,10,12\\}$
15 | $\\{14\\}$ | $\\{12,14\\}$ | $\\{10,12,14\\}$ | $\\{8,10,12\\}$ | $\\{6,8,10,12\\}$
13 | $\\{12\\}$ | $\\{10,12\\}$ | $\\{8,10,12\\}$ | $\\{6,8,10,12\\}$ | $\\{4,6,8,10\\}$
11 | $\\{10\\}$ | $\\{8,10\\}$ | $\\{6,8,10\\}$ | $\\{4,6,8,10\\}$ | $\\{2,4,6,8,10\\}$

$w(r_{1}$) $w(r_{2}$) | 17 | 15 | 13 | 11
---|---|---|---|---
27 | $\\{16\\}$ | $\\{14\\}$ | $\\{12\\}$ | $\\{10\\}$
25 | $\\{14,16\\}$ | $\\{12,14\\}$ | $\\{10,12\\}$ | $\\{8,10\\}$
23 | $\\{12,14\\}$ | $\\{10,12,14\\}$ | $\\{8,10,12\\}$ | $\\{6,8,10\\}$
21 | $\\{10,12,14\\}$ | $\\{8,10,12\\}$ | $\\{6,8,10,12\\}$ | $\\{4,6,8,10\\}$
19 | $\\{8,10,12\\}$ | $\\{6,8,10,12\\}$ | $\\{4,6,8,10\\}$ | $\\{2,4,6,8,10\\}$
17 | $\\{6,8,10,12\\}$ | $\\{4,6,8,10\\}$ | $\\{2,4,6,8,10\\}$ | $\\{0,2,4,6,8\\}$
15 | $\\{4,6,8,10\\}$ | $\\{2,4,6,8,10\\}$ | $\\{0,2,4,6,8\\}$ | $\\{0,2,4,6,8\\}$
13 | $\\{2,4,6,8,10\\}$ | $\\{0,2,4,6,8\\}$ | $\\{0,2,4,6,8\\}$ | $\\{0,2,4,6\\}$
11 | $\\{0,2,4,6,8\\}$ | $\\{0,2,4,6,8\\}$ | $\\{0,2,4,6\\}$ | $\\{0,2,4,6\\}$

###### Proposition 3

Let $C$ be a singly-even self-dual code of length divisible by $4.$ Then there
exists a chain of subcodes

$C_{1}=\left\langle\textbf{1}\right\rangle\subset C_{2}\subset\ldots\subset
C_{k-1}\subset C,$

where $C_{i}$ is doubly-even self-orthogonal for $i=1,\ldots,k-1.$

Proof.  We denote the length of $C$ by $n$ and its dimension by $k.$ On the
one hand $n\equiv 0\mod 4,$ which implies 1 is a doubly-even codeword of $C.$
On the other hand, we know that each singly-even code has a maximal doubly-
even subcode of 1-codimension. The existence of the subcodes between $1$ and
$C_{k-1}$ follows from here. $\hfill\square$

##  3 Neighbors

Pless and Brualdi [3] introduced the concept of neighbors within self-dual
codes. In this section we investigate the neighbors of Type I codes.

###### Definition 2

Two self-dual codes of length $n$ are called neighbors, provided their
intersection is a code of dimension $\frac{n}{2}-1.$

###### Theorem 3.1

Let $C$ be a self-dual code of Type I. Then $C$ has either two doubly-even
neighbors or two singly-even neighbors.

Proof.  We know that $C$ has a maximal doubly-even subcode $C_{max}\subset C.$
Then there exists $\gamma_{1}\in C_{max}^{\bot}$ such that $C=\langle
C_{max},\gamma_{1}\rangle,$ i.e. $w(\gamma_{1})\equiv 2\mod 4.$ Let
$\gamma_{2}\in C_{max}^{\bot}.$ Since $C$ is self-dual we have
$\gamma_{1}\not\perp\gamma_{2}$ and $C_{1}=\langle C_{max},\gamma_{2}\rangle$
and $C_{2}=\langle C_{max},\gamma_{1}+\gamma_{2}\rangle$ are neighbors of $C.$
Since $\gamma_{1}+\gamma_{2}\in C_{max}^{\bot}$ and $\textbf{1}\in C_{max}$ we
have on the one hand $w(\gamma_{1}+\gamma_{2})\equiv 0\mod 2.$ On the other
hand we have
$w(\gamma_{1}+\gamma_{2})=w(\gamma_{1})+w(\gamma_{2})-2\mu(\gamma_{1},\gamma_{2})\equiv
2+w(\gamma_{2})-2\equiv w(\gamma_{2})\mod 4.$ Thus either $C_{1}$ and $C_{2}$
are both singly-even or both doubly-even. $\hfill\square$

###### Theorem 3.2

Let $C_{1}$ be a binary singly-even self-dual $(n,k,d)$-code and $C_{2}$ a
binary doubly-even self-dual code. If $C_{1}$ and $C_{2}$ are neighbors, i.e.
they have the same maximal doubly-even subcode $C_{k-1},$ then all singly-even
codewords in $C_{k-1}^{\bot}$ have weight $w,$ where $d\leq w\leq n-d.$

Proof.  There exist $\gamma_{1},\gamma_{2}\in C_{k-1}^{\bot}$ such that
$C_{1}=\langle C_{k-1}\cup\\{\gamma_{1}\\}\rangle$ and $C_{2}=\langle
C_{k-1}\cup\\{\gamma_{2}\\}\rangle.$ Thus $w(\gamma_{1})\equiv 2\mod 4$ and
$w(\gamma_{2})\equiv 0\mod 4.$ Now we denote
$S:=C_{k-1}^{\bot}\setminus(C_{1}\cup C_{2}).$ Then $\mid S\mid=2^{k-1}.$ Then
all codewords of $C_{1}\setminus C_{k-1}$ have the form $a+\gamma_{1}$ for
some $a\in C_{k-1}$ and all codewords of $C_{2}\setminus C_{k-1}$ have the
form $a+\gamma_{2}$ for some $a\in C_{k-1}.$ Further all codewords of $S$ have
the form $a+\gamma_{1}+\gamma_{2}$ for some $a\in C_{k-1}.$

Since $C_{1}$ and $C_{2}$ are self-dual we have
$\gamma_{1}\not\perp\gamma_{2}.$ Thus $\mu(\gamma_{1},\gamma_{2})\equiv 1\mod
2.$ Then

$w(\gamma_{1}+\gamma_{2})=w(\gamma_{1})+w(\gamma_{2})-2\mu(\gamma_{1},\gamma_{2})\equiv
2+0-2\equiv 0\mod 4$ (1)

Since $\gamma_{1}+\gamma_{2}\in C_{k-1}^{\bot}$ we have
$\mu(a,\gamma_{1}+\gamma_{2})\equiv 0\mod 2$ for all $a\in C_{k-1}.$ Thus

$w(a+\gamma_{1}+\gamma_{2})=w(a)+w(\gamma_{1}+\gamma_{2})-2\mu(a,\gamma_{1}+\gamma_{2})\equiv
0+0-0\equiv 0\mod 4$ (2)

which means that $S$ consists only of codewords with doubly-even weight.

Since $\mid C_{k-1}^{\bot}\mid=2^{k+1}=\mid S\mid+\mid C_{2}\mid+\mid
C_{1}\setminus C_{k-1}\mid=2^{k-1}+2^{k}+2^{k-1},$ the number of singly-even
codewords in $C_{k-1}^{\bot}$ is $2^{k-1}.$ Therefore, for all singly-even
codewords $c\in C_{k-1}^{\bot}$ implies $c\in C_{1}.$ $\hfill\square$

###### Remark 2

Theorem 3.2 can help us to make the search for singly-even $(n,k,d)$-codes
faster, since it is a strong condition that in the dual code there cannot be
any singly-even word with weight smaller than $d.$

##  4 Torch code searching package

Based on the statements of Section 2 and Section 3 we build up a computer-
based code searching package. In this section we describe the software
implementation used for searching for linear codes. The package, named Torch,
is written in Python 3.x, and uses Sagemath 9.x (available at
https://www.sagemath.org/) for most linear code operations. Some operations
use the GAP guava package (available at https://www.gap-
system.org/Packages/guava.html) or Magma (available at
http://magma.maths.usyd.edu.au/magma/) when it is more efficient than the
solutions provided by Sagemath. The source code repository is currently not
publicly available.

The goal of the package is to provide a reusable, modular solution for
implementing linear code search algorithms, where adding a new search
condition or a modified algorithm for a computation step can be done as
quickly as possible. To achieve this, Torch uses a custom dependency injection
class which reads a .json format configuration file, describing the
relationships between the submodules, instantiates the necessary objects and
assembles the search algorithm described in the configuration.

The default configuration describes a depth-first search algorithm which
builds a generator matrix row by row. When searching for an (n,k,d) linear
code, the algorithm starts with an $(n,1,d)$ matrix, and when the search is at
depth $k^{\prime}$, then the generator matrix being built has dimension
$k^{\prime}$. When the search reaches depth $k$, a solution is found. At each
step of the search, a number of conditions are checked to see which possible
new rows should the algorithm use to continue, and which branches of the
search tree can be discarded.

Some of the modules in this configuration include:

  * •

mu$\\_$table: creates a table of possible $\mu$ values between codewords,
based on the target code’s $(n,k,d)$ and type.

  * •

starters: generator function that returns the possible $(n,1,d)$ matrices that
will be the root nodes of the search.

  * •

descendants: generator function that takes a $k^{\prime}$ dimensional matrix,
$k^{\prime}<k$, as input, and returns all $(n,k,d)$ generator matrices which
have the input matrix as their first $k^{\prime}$ rows.

  * •

children: generator function that takes a $k^{\prime}$ dimensional matrix,
$k^{\prime}<k$, as input, and returns all $(n,k^{\prime}+1,d)$ generator
matrices which have the input matrix as their first $k^{\prime}$ rows. Can be
given a set of conditions, which filter out possible solutions. Only those
matrices are returned which pass all conditions.

  * •

saver: provides the option to save a linear code object to a file when a code
with the target parameters are found. The default saver uses the pickle python
package to serialize objects.

  * •

logger: provides the option for other modules to log their activity. The
default logger logs to the console.

The search is carried out by calling the descendants module (which, in turn,
recursively calls the children module) on all the elements returned by the
starter module.

All modules can be instantiated on their own, for testing or experimental
purposes. Most modules have multiple implementing classes. In some cases, a
factory pattern is used to decide between implementations during build time,
based on information such as the target linear code’s type. In other cases,
modules can switch between implementations during runtime to try to pick the
most efficient solution, based on criteria such as the current code’s
dimension and other properties.

At the top level, the Torch package includes a function named get$\\_$code(),
which takes the parameters $(n,k,d)$ and code type. Other optional parameters
include a custom configuration file and arbitrary values to be passed to
submodules, such as silent mode, ascending/descending order, save file
destination and many others. Once instantiated, get$\\_$code() acts as a
generator function yielding Sagemath linear code objects of the given
parameters. The default configuration is an exhaustive search, with conditions
that ensure that at least one linear code from each permutation equivalence
class is yielded.

##  5 Code search for $n\leq 30$

In Table 2, we give some computation results which were achieved by our code
searching program. We give the number of found codes. These codes are not
necessarily inequivalent. In contrast, any existing binary $(n,k,d)$-code of
Type I is equivalent to at least one of the found codes.

Table 2: Type I codes of small length. (n,k,d) | Number of found codes
---|---
(12,6,4) | 2
(14,7,4) | 6
(16,8,4) | 43
(18,9,4) | 556
(20,10,4) | 1977+
(22,11,6) | 242
(24,12,6) | 1279+
(28,12,6) | 350+
(30,15,6) | 6000+

Where we write $+$ that means there are probably more codes than we found,
because we stopped the code searching program at this point. The searching
results depend not only on $n,k,d,$ but also on the searching strategy. For
example, when searching self-dual $(30,15,6)$-codes we experienced that the
searching program finds more than 6000 codes within one hour if we restrict
the row weights to $10.$ Where the number of found codes is completely given,
that means there exists no other $(n,k,d)$-code which is not equivalent to one
of the found codes. On the other hand, the number of found codes is not equal
to the number of inequivalent codes, but in some cases it is near to it
(because of the hierarchy in the generator matrix in the code searching
program).

##  6 Conclusion

In the current paper, we introduced a code searching program which is intended
to use all good facts we know about Type I codes. Beside this, the code
searching program is also able to generate Type II codes or any $(n,k,d)$
linear codes for relatively small $n.$ In Section 5 we give the number of
found Type I codes for $12\leq n\leq 30.$ This means the code searching
program found a generator matrix in standard form for each found code. Most of
the codes were found within some minutes. Therefore the strength of this
program lies in the capability to give generator matrices fast. Those
generator matrices can be used further in cryptographic systems, where small
code length is required, e.g. for mobile applications.

## References

  * [1] Stefka Bouyuklieva, Masaaki Harada and Akihiro Munemasa  “Nonexistence of certain singly even self-dual codes with minimal shadow”  In _arXiv preprint arXiv:1707.04059_ , 2017
  * [2] Stefka Bouyuklieva and Wolfgang Willems  “Singly even self-dual codes with minimal shadow”  In _IEEE Transactions on Information Theory_ 58.6 IEEE, 2012, pp. 3856–3860
  * [3] Richard A. Brualdi and VS Pless  “Weight enumerators of self-dual codes”  In _IEEE transactions on information theory_ 37.4 IEEE, 1991, pp. 1222–1225
  * [4] ST Dougherty, Jon-Lark Kim and Patrick Solé  “Open problems in coding theory”  In _Contemp. Math_ 634, 2015, pp. 79–99
  * [5] Masaaki Harada, Michael Kiermaier, Alfred Wassermann and Radinka Yorgova  “New binary singly even self-dual codes”  In _IEEE transactions on information theory_ 56.4 IEEE, 2010, pp. 1612–1617
  * [6] David Joyner and Jon-Lark Kim  “Selected unsolved problems in coding theory”  Springer Science & Business Media, 2011
  * [7] Yehuda Lindell  “Introduction to coding theory lecture notes”  In _Department of Computer Science Bar-Ilan University, Israel January_ 25, 2010
  * [8] Eric M Rains  “Shadow bounds for self-dual codes”  In _IEEE Transactions on Information Theory_ 44.1 IEEE, 1998, pp. 134–139