define(TEX_IN,`tex/code.tex.eights') define(DATA_IN,`inputs/code.data.eights') define(newresultcounter,0) include(src/MACROS) |-> TEX_IN \hfuzz 10pt % Set up a svb macro, which is like verbatim, but doesn't put % vertical spacing at the beginning and end. \catcode`\@=11 \begingroup \catcode `|=0 \catcode `[= 1 \catcode`]=2 \catcode `\{=12 \catcode `\}=12 \catcode`\\=12 |gdef|@xsvb#1\end{svb}[#1|end[svb]] |gdef|@sxsvb#1\end{svb*}[#1|end[svb*]] |endgroup \def\@svb{ \leftskip\@totalleftmargin\rightskip\z@ \parindent\z@\parfillskip\@flushglue\parskip\z@ \@tempswafalse \def\par{\if@tempswa\hbox{}\fi\@tempswatrue\@@par \penalty\interlinepenalty}% \obeylines \tt \catcode``=13 \@noligs \let\do\@makeother \dospecials} \def\svb{\@svb \frenchspacing\@vobeyspaces \@xsvb} \let\endsvb=\relax \def\mindex{\@bsphack\begingroup\@sanitize\@wrindexa} \catcode`\@=12 \def\ul{\underline} {\par\noindent\Large\bf The smallest length of eight-dimensional binary} \vspace{0.05in} {\par\noindent\Large\bf linear codes with prescribed minimum distance} \vskip 0.2in \def\boxitTable{\lower3pt\hbox{\vbox{\hrule\hbox{\vrule\kern3pt \vbox{\kern3pt\hbox{Table}\kern3pt}\kern3pt\vrule}\hrule}}} \def\makeaddress{ \vskip 0.15in \par\noindent {\footnotesize Department of Mathematics and Statistics, University of Nebraska} \par\noindent {\footnotesize Lincoln, NE 68588-0323, USA\ \ (\email)}} \def\thefootnote{\fnsymbol{footnote}} \par\noindent Iliya Bouyukliev\protect\footnote{Partially supported by the Bulgarian National Science Fund under Contracts No.\ MM-502/1995.} \vskip 0.15in \par\noindent{\footnotesize Institute of Mathematics and Informatics, Bulgarian Academy of Sciences} \par\noindent{\footnotesize P.O.\ Box 323, 5000 Veliko Tarnovo, Bulgaria \ \ (lpmivt{\kern0.5pt}@{\kern0.5pt}vt.bia-bg.com)} \vspace{0.2in} \setcounter{footnote}{6} \par\noindent David B. Jaffe\protect\footnote{Partially supported by the U.S.\ National Science Foundation.} \makeaddress \def\thefootnote{\arabic{footnote}}\setcounter{footnote}{0} \vspace{0.2in} \par\noindent Vesselin Vavrek \vskip 0.15in \par\noindent{\footnotesize Institute of Mathematics and Informatics, Bulgarian Academy of Sciences} \par\noindent{\footnotesize P.O.\ Box 323, 5000 Veliko Tarnovo, Bulgaria \ \ (lpmivt{\kern0.5pt}@{\kern0.5pt}vt.bia-bg.com)} \vspace{0.1in} \begin{center} \fbox{% \begin{minipage}{6.0in} Let $n(8,d)$ be the smallest integer $n$ for which a binary linear code of length $n$, dimension $8$ and minimum distance $d$ exists. We prove that $n(8,18)=42$, $n(8,26)=58$, $n(8,28)=61$, $n(8,30)=65$, $n(8,34)=74$, $n(8,36)=77$, $n(8,38)=81$, $n(8,42)=89$, and $n(8,60)=124$. After these results, all values of $n(8,d)$ are known. \par\noindent{\bf Index terms:}\ binary linear code, bounds, minimum distance. \end{minipage}% } \end{center} \def\framesection#1{\refstepcounter{section}% \addcontentsline{toc}{section}{\thesection \hspace{1em}#1}% \section*{\fbox{\bf \S\thesection\ #1}}} \framesection{Introduction} We prove that there do not exist binary linear codes with parameters $[41,8,18]$, $[57,8,26]$, $[60,8,28]$, $[64,8,30]$, $[73,8,34]$, $[76,8,36]$, $[80,8,38]$, $[88,8,42]$, or $[123,8,60]$. These results are established with the aid of the computer programs {\tt Extension} of the first author and {\tt Split} of the second author. Building on prior published work by Baumert, Belov, Bierbrauer, Blokh, Bouyukliev, Chen, Dodunekov, Edel, Helleseth, Hirasawa, Jaffe, Kasahara, Kostova, Loga\v cev, Manev, McEliece, Namekawa, Palazzo, Piret, Said, Sandimirov, Simonis, Solomon, Stiffler, Sugiyama, van Tilborg, Ytrehus, and Zyablov [.baumert mceliece.], [.belov griesmer baikal.], [.belov logacev sandimirov.], [.bierbrauer edel reed solomon.], [.blokh zyablov.], [.boukliev dodunekov helleseth ytrehus.], [.boukliev sozopol 1998.], [.chen computer results.], [.dodunekov ytrehus 1987.], [.dodunekov manev 1985.], [.dodunekov manev proit 1987.], [.helleseth characterization 1981.], [.helleseth new constructions 1983.], [.helleseth tilborg griesmer 1981.], [.helleseth ytrehus 33_8_14.], [.jaffe simonis dual transform.], [.kostova manev.], [.piret 1980.], [.said palazzo.], [.solomon stiffler.], [.sugiyama 1976.], [.tilborg quasi-cyclic.], [.tilborg 1979.], [.tilborg 1981 discrete.], [.ytrehus helleseth 1990.], and unpublished work by Groneick, Grosse, and Said appearing in [.brouwer verhoeff 1993.], the problem of determining the best possible minimum distance of an eight-dimensional binary linear code is now settled. Let $n(k,d)$ denote the smallest $n$ for which an $[n,k,d]$ code exists. Let $g(k,d)$ denote $\sum_{i=0}^{k-1} \ceiling{d/2^i}$; Griesmer [.griesmer 1960.] has observed that $n(k,d) \geq g(k,d)$. Baumert and McEliece [.baumert mceliece.] showed that for fixed $k$, one has equality for $d \gg 0$. For $k \leq 7$, our knowledge of $n(k,d)$ was completed in $1981$ by van Tilborg [.tilborg 1981 discrete.]. Now we present the complete picture regarding $n(8,d)$ with the following table: \begin{center} \begin{tabular}{|c|c|}\hline \boldmath$d$ {\bf(even)} & \boldmath$n(8,d) - g(8,d)$\\ \hline\hline $2$ & $0$\\ \hline $4$ -- $8$ & $1$\\ \hline $10$ -- $20$ & $2$\\ \hline $22$ -- $24$ & $1$\\ \hline $26$ -- $32$ & $3$\\ \hline $34$ -- $58$ & $2$\\ \hline $60$ & $3$\\ \hline \end{tabular} \kern0.8in \begin{tabular}{|c|c|}\hline \boldmath$d$ {\bf(even)} & \boldmath$n(8,d) - g(8,d)$\\ \hline\hline $62$ & $1$\\ \hline $64$ -- $66$ & $0$\\ \hline $68$ -- $92$ & $1$\\ \hline $94$ -- $98$ & $0$\\ \hline $100$ -- $104$ & $1$\\ \hline $\geq 106$ & $0$\\ \hline \end{tabular} \end{center} The number of cases is smaller than one might think, and in fact this is the least complicated way we know of to describe the function $n(8,d)$. Of course we would like to see more structure! \framesection{Software tools} In this section we briefly describe some of the software tools that are used in the proofs. The next section will say more about the program {\tt Extension}, so we will not say too much here about it. There are three primary strands of computation which we utilize. One involves linear programming based on various weight enumerators. Another involves extension from residual codes (as will be explained further in the next section). Finally, as part of the extension procedure, it is necessary to test isomorphism of codes. The proofs are encoded completely in the language {\tt Split}. Although some comments have been added to facilitate their digestion by the reader unacquainted with {\tt Split}, it will not be possible to completely understand them without reference to some other source. In particular, an introduction to split linear programming may be found in [.brief tour split main.]. Also [.jaffe optimal binary 30.] and [.boukliev jaffe dimension seven.] may be helpful. Ultimately, the reader may need to refer to [.jaffe split guide.]. In fact most of the calculations involving extension from residual codes were originally performed using {\tt Extension}. More specifically, all lines in the {\tt Split} program having the word {\tt Unresidue} in them (except that for $[73,8,34]$ codes) have been confirmed using {\tt Extension}. To test isomorphism of codes, {\tt Split} utilizes Brendan McKay's program {\tt nauty}. We refer to [.practical graph isomorphism.] and [.nauty guide onepointfive.] for more information about the latter. The calculations were carried out on a $500$ MHz Alpha 21264 processor. A single command (the one involving {\tt Unresidue} for $[73,8,34]$ codes) took about five weeks. The corresponding line for $[57,8,26]$ codes took a bit over two hours; that for $[76,8,36]$ codes took one hour. Everything else took in total less than one half hour. \framesection{Main ideas of {\tt Extension}}\label{extension-section} Let $C_x$ be $[n,k,d]$ codes and $C_0$ be their residual code $\Res(C_x,w)$ with respect to a codeword of weight $w<2d$. In this section we describe how to construct all the $[n,k,d]$ codes $C_x$ if we know a residual code $C_0$. The inequivalent optimal linear codes in the considered dimensions are not so many. The presented method is convenient for investigation of such codes. The next theorem gives us a condition which ensures relatively big minimum distance for residual code of an optimal code: \vspace{0.05in} \par\noindent{\bf Theorem}\ Let $C$ be an $[n,k,d]$ code and let $c\in C$ be a vector of weight $w$ with $w<2d$. Then the code $\Res(C;w)$ has the parameters $[n-w,k-1,d_0]$, where $d_0\geq d-\floor{w/2}$. \vspace{0.05in} In many cases the residual code of an optimal code is also optimal. This gives us the possibility of building a hierarchy of extensions of linear codes, beginning with codes of small length and dimension. Let us denote a generator matrix of the code $C_0$ by $G_0$. Then there exist generator matrices of $C_x$ in the following form: $$ G_{x}= \left( \begin{array}{c} 1~1~ \dots ~~~~1\\ \hline \dots \dots \dots\\ \dots \dots \dots\\ \\ \dots \dots \dots\\ \end{array} \right. \left\vert \begin{array}{c} ~0~\dots~0~0~ \\ \hline ~~~~~~~~~~ \\ ~~~G_0~~~~~ \\ ~~~~~~~~~~ \\ ~~~~~~~~~~\\ \end{array} \right) $$ \noindent We suggest a backtrack algorithm for finding all solutions for the second row (having fixed the first) and all solutions for the row $t+1$ (having fixed the first $t$ rows). Our basic information will be the number and length of the intervals in which the columns (between $1$ and $w$) of the matrix of the first $t$ rows are the same. We will call a solution in the $t+1$-th step the number of $1$'s in any interval for a possible $t+1$-th row of the generator matrix. Let us denote the possibilities for the number of ones in position $1 \dots w$ by $x_2^1$ for the second row, by $x_3^1$ for the third row and $x_k^1$ for the last row. It is not very difficult to find using exhaustive search all the values of the variables depending on $W$ (where $W$ is the set of possible nonzero weights) and $G_0$. Let us denote all the values of the solutions by $\{x_2^1\},\{x_3^1\},\dots,\{x_k^1\}$. Actually, in the beginning we have only one interval. Let $z \in \{x_2^1\}$. We may put $z$ ones in positions $1 \dots z$ in the second row without loss of generality. Then some of the codes $C_x$ (if such codes exist for $z$) will have generator matrices in the following form: $$ G_{x}^{\prime}= \left( \begin{array}{c} 1~1~ \dots ~~~~1\\ 1 \dots 1~0 \dots0\\ %\hline \dots \dots \dots\\ \\ \dots \dots \dots\\ \end{array} \right. \left\vert \begin{array}{c} ~0~\dots~0~0~ \\ % \hline ~~~~~~~~~~ \\ ~~~G_0~~~~~ \\ ~~~~~~~~~~ \\ ~~~~~~~~~~\\ \end{array} \right) $$ We denote the number of ones in positions $1 \dots z$ and $z+1 \dots w$ in the third row by $x_{3_1}^2,x_{3_2}^2$ and in row $k$ by $x_{k_1}^2,x_{k_2}^2$. The upper index means that we have two fixed rows and the other indices fix the row and the interval. We have the following conditions:\\ $$ 0 \le x_{r_1}^2 \le z , 0 \le x_{r_2} ^2 \le (w-z)$$ $$ x_{r_1}^2+x_{r_2} ^2 \in \{x_r^1 \}.$$ Using exhaustive search we can obtain all solutions of $\{x_{i_1}^2 ,x_{i_2}^2 \}_{i:=3 \dots k}$. Suppose that we have a solution for the row with number $t$. Let the intervals in this step be: {\large $$ [1 \dots j_{t_1}] \ ; \ [(j_{t_1}+1) \dots j_{t_2}]; \ \dots \ ; \ [(j_{t_{m_t-1}}+1) \dots w].$$} Let us denote the possibilities for the number of ones in the different intervals by $$x_{(t+1)_1}^t,x_{(t+1)_2}^t, \dots x_{(t+1)_{m_t}}^t,$$% and all solutions for the $t+1$-th row with fixed $t-1$ rows by $S_{t+1}^{t-1}= \{ x_{(t+1)_1}^{t-1},x_{(t+1)_2}^{t-1}, \dots x_{(t+1)_{m_{(t-1)}}}^{t-1} \}$. If $f=(f_1,f_2,\dots,f_{m_{(t-1)}} ) \in S_{t+1}^{t-1} $ we have the following conditions:\\ {\large \begin{equation} 0 \le x_{(t+1)_1}^t \le j_{t_1} \ ; \ 0 \le x_{(t+1)_2}^t\le j_{t_2}-j_{t_1} \ ; \ \dots \ ; \ 0 \le x_{(t+1)_{m_t}}^t \le w-j_{t_{m_t-1}} \end{equation}} and {\large \begin{equation} x_{(t+1)_{i-1}}^t+ x_{(t+1)_{i}}^t=f_{i^\prime}^s \ \ or \ \ x_{(t+1)_{i}}^t=f_{i^\prime} \ \ {\rm for} \ \ i:= 1 \dots m_t \ \ {\rm and} \ \ \forall f \in S_{t+1}^{t-1} \end{equation}} The last condition depends on whether the interval $i^\prime$ (in step $t-1$) is partitioned in step $t$ (into intervals $i-1$ and $i$) or not. Using exhaustive search and these two conditions we can obtain all the sets $S_{t+1}^{t}$ and then the sets $S_{t+2}^{t} \dots S_{k}^{t}$. Similarly we can continue until $t+1=k$. \\ \noindent {\bf Comments on efficiency:} Let's suppose that in step $k-1$ we have obtained a projective linear $[n,k-1,W]$ code. If we use only condition (1) at the \th{k} step we have to make $2^w$ checks but if we use conditions (1) and (2) we have to make only $\vert S_{k}^{k-1} \vert$ checks. \\ In the realization of these ideas we obtain a hierarchic structure of solutions. Each solution in row $t$ is a successor of a solution in row $t-1$. For effective work it is necessary that the tree of solutions be as small as possible. So it is better to eliminate the equivalent solutions (up to extension). Let $y_1$ and $y_2$ be two solutions for the \th{t} row with corresponding codes $C_{y_1}$ and $C_{y_2}$. These codes are generated from the first $t$ rows of $G_x$. $y_1$ and $y_2$ are equivalent (up to extension) if $\sigma_1\sigma_2(C_{y_1})=C_{y_2}$ for some permutations $\sigma_1$ of the first $w$ coordinates and $\sigma_2\in \Aut(C_0)$. \vspace{0.1in} \par\noindent{\bf Remark.}\ Vesselin Vavrek made an independent realization of {\tt Extension} using the main ideas. His realization contains an original program for isomorphisms of codes. \framesection{Other tools} In this section we briefly describe other (known) tools for establishing restrictions on the existence of codes. These tools fall into two main categories. First, inferences about $[n,k,d]$ codes may sometimes be made from knowledge of codes with other parameters. One important instance of this is the case of residual codes, as follows. Suppose that an $[n,k,d]$ code $C$ has a codeword of weight $w$, where $d \leq w < 2d$. Then the ``projection off $w$'' is a $[n-w,k-1,d - \floor{w/2}]$ code, called the {\it residual code\/} of $C$ \WRT\ $w$. Nonexistence of such codes would tell us that in fact $C$ had no word of weight $w$, but more generally information about the residual code yields information about $C$, which is used (for example) in computations about split weight enumerators. Another instance of inferences about $[n,k,d]$ codes $C$ from codes with other parameters arises by looking at the subcode disjoint from a word in the dual code $C^\perp$. That is, if $C^\perp$ has a word of weight $r$, then there exists an $[n-r,k-r+1,d]$ code. One more inference about $[n,k,d]$ codes $C$ comes from the work of Brouwer [.brouwer linear programming bound.], who shows that if $C$ is even, its number of doubly even words is restricted, and sometimes restricted by the existence of certain doubly even codes. Second, inferences about $[n,k,d]$ codes $C$ may be obtained from various weight enumerators, by linear programming. Originally, following [.delsarte bounds unrestricted.], this was done with the ordinary weight enumerator of the code. One may work with split weight enumerators, following MacWilliams and Sloane ([.macwilliams sloane book.]\ pp.\ 149-150), Simonis [.simonis partitions.], and Heijnen [.heijnen.]; the state of the art is described in [.brief tour split main.], to which we refer for further details. One may also carry out computations with the joint weight enumerator of a code, and we do so in the next section. \framesection{The proofs} In this section we outline the proofs of our results. The reader may also wish to consult the appendix, where arguments in the {\tt Split} language are given, exactly parallel to (but more complete than) the explanations given here. In any case it must be understood that certain results (namely those in [.boukliev jaffe dimension seven.] and [.jaffe optimal binary 30.]) are regarded as ``known'', and consequently certain inferences (such as nonexistence of certain weights in codes with certain parameters) are made without comment if they follow formally from the results in these earlier papers. \vspace{0.1in} \par\noindent{\bf Theorem 1}\ {\it There is no code with parameters $[41,8,18]$.} \vspace{0.15in} \par\noindent{\sc Proof.}\ We consider even codes with these parameters and begin by showing that there are no codewords of weights $34$, $32$, or $30$. This is accomplished by three applications of split linear programming. (See e.g.{\ }[.brief tour split main.].) Then we use joint linear programming to obtain constraints on the number $\verb|y|_i$ of words of weight $i$ in such a code, and on the number $\verb|div|_4$ of words whose weight is divisible by $4$ (via Brouwer [.brouwer linear programming bound.]): $82 \leq \verb|y|_{18} \leq 90$, $95 \leq \verb|y|_{20} \leq 122$, $\verb|y|_{22} \leq 28$, $\verb|y|_{24} \leq 15$, $23 \leq \verb|y|_{26} \leq 39$, $8 \leq \verb|y|_{28} \leq 13$, $112 \leq {\tt div}_4 \leq 136$. This computation is iterative, employing a primitive form of integer linear programming. Next we show by split linear programming that given a word of weight $28$, where exists a word of weight $20$ meeting it along $10$ ones. Then we show that the split linear programming problem associated to the corresponding two-dimensional code is infeasible, thereby deducing the nonexistence of even $[41,8,18]$ codes, and hence all $[41,8,18]$ codes. \qed \vspace{0.1in} \par\noindent{\bf Lemma}\ {\it There are exactly $36$ codes with parameters $[32,7,14]$.} \vspace{0.1in} \par\noindent{\sc Proof.}\ The statement of the lemma is a bit deceptive: of course what we actually do is classify the $[32,7,14]$ codes. In any case, we begin by classifying codes with parameters $[19,6,8]$, and thence codes with parameters $[18,6,7]$. To classify the $[19,6,8]$ codes, we first show that such a code has a word of weight $8$, and then that for every word of weight $8$, there is another word of weight $8$ meeting it along $4$ ones. Starting with a two-dimensional code (corresponding to two such words of weight $8$), we then establish (via a search process) that there are exactly $30$ $[19,6,8]$ codes. From there one easily classifies the $[18,6,7]$ codes by deleting columns from generator matrices. One finds $113$ codes. Then we look at $[32,7,14]$ codes. First we show that they have no word of weight $28$, as follows. Suppose that a word of weight $28$ exists. It would have to contain a word of weight $14$. Relative to the partition $14,14,4$ of $32$, corresponding to the words of weight $28$ and $14$, we show (by three successive applications of split linear programming on three-dimensional subcodes), that there are no codewords of multiweight $(7,7,4)$, $(4,6,4)$, or $(4,7,3)$. At this point, the split linear programming problem (associated to just the words of weight $28$ and $14$) becomes infeasible, and we thus deduce the nonexistence of a word of weight $28$. A similar but more involved computation (exhibited in the appendix) shows that there is no word of weight $30$. Now by extension from the $[18,6,7]$ codes, we are thus to find all the $[32,7,14]$ codes. \qed \vspace{0.1in} \par\noindent{\bf Theorem 2}\ {\it There is no code with parameters $[57,8,26]$.} \vspace{0.15in} \par\noindent{\sc Sketch.}\ Using mechanical methods, we show that such a code would have weights in the set $\{26,28,30,32,34,36,38,40,42,44\}$. We classify the $[31,7,13]$ codes, of which there are $533$. Then we show by extension from these that there is no $[57,8,26]$ code. \qed \vspace{0.1in} \par\noindent{\bf Theorem 3}\ {\it There is no code with parameters $[60,8,28]$.} \vspace{0.15in} \par\noindent{\sc Sketch.}\ Using mechanical methods, we show that such a code would have weights in the set $\{28,32,36,40,44\}$. Then we show by extension (from the $22$ $[20,7,8]$ codes) that there is no $[60,8,28]$ code. \qed \vspace{0.1in} \par\noindent{\bf Theorem 4}\ {\it There is no code with parameters $[64,8,30]$.} \vspace{0.15in} \par\noindent{\sc Sketch.}\ First show that any $[35,7,16]$ code must have weights in the set $\{16,20,24,28\}$. The result then drops out. \qed \vspace{0.1in} \par\noindent{\bf Theorem 5}\ {\it There is no code with parameters $[73,8,34]$.} \vspace{0.15in} \par\noindent{\sc Sketch.}\ First we classify $[39,7,17]$ codes, of which there are $5649$. Turning to even $[73,8,34]$ codes, we use tricks (like that in the proof of Theorem 1, but deeper) to show that there are no words with weights in the set $\{72, 70, 68, 66, 64, 62, 60\}$. Then we show by extension from the $[39,7,17]$ codes that there is no $[73,8,34]$ code. \qed \vspace{0.1in} \par\noindent{\bf Theorem 6}\ {\it There is no code with parameters $[76,8,36]$.} \vspace{0.15in} \par\noindent{\sc Sketch.}\ First show that all the weights must lie in the set $\{36,40,44,48,52,56\}$. Then by extension from the $172$ codes with parameters $[40,7,18]$, show that no $[76,8,36]$ code exists. \qed \vspace{0.1in} \par\noindent{\bf Theorem 7}\ {\it There is no code with parameters $[80,8,38]$.} \vspace{0.15in} \par\noindent{\sc Sketch.}\ First we get some information about $[40,5,20]$ codes, namely that they have weights in the set $\{20,24,28,32\}$ and that their numbers of codewords $y_i$ satisfy the constraints $26 \leq \verb|y|_{20} \leq 28$, $2 \leq \verb|y|_{24} \leq 5$, $\verb|y|_{28} \leq 1$, and $\verb|y|_{32} \leq 1$. Next this helps us get similar information about $[80,6,40]$ codes, namely that they have weights in the set $\{40,48,56,64\}$ and satisfy the constraints $58 \leq \verb|y|_{40} \leq 60$, $2 \leq \verb|y|_{48} \leq 5$, $\verb|y|_{56} \leq 1$, and $\verb|y|_{64} \leq 1$. Then we turn to even $[80,8,38]$ codes. Using split linear programming, we show that they have no words of weight $80$, $64$, $62$, or $44$. Then we use iterated joint linear programming to obtain the following constraints: $150 \leq \verb|y|_{38} \leq 151$, $58 \leq \verb|y|_{40} \leq 59$, $34 \leq \verb|y|_{46} \leq 36$, $3 \leq \verb|y|_{48} \leq 5$, $6 \leq \verb|y|_{54} \leq 7$, $\verb|y|_{56} \leq 1$, $184 \leq \mu_3 \leq 188$, and $\verb|div|_4 = 64$. Here $\mu_3$ denotes the number of words of weight $3$ in the dual code. Fifteen applications of split linear programming (detailed in the appendix) now yield the desired conclusion. \qed \vspace{0.1in} \par\noindent{\bf Theorem 8}\ {\it There is no code with parameters $[88,8,42]$.} \vspace{0.15in} \par\noindent{\sc Sketch.}\ It just drops out. \qed \vspace{0.1in} \par\noindent{\bf Theorem 9}\ {\it There is no code with parameters $[123,8,60]$.} \vspace{0.15in} \par\noindent{\sc Sketch.}\ First we show that there is a unique $[47,7,22]$ code. Turning to $[123,8,60]$ codes, we show that they must have weights in the set $\{60,64,76\}$, and then by extension (from the unique $[47,7,22]$ code) that they do not exist. \qed \framesection{Appendix: {\tt Split} code for the proofs} As a supplement to the sketchy arguments given above, we give here a formalized argument of the results of the paper, in {\tt Split}. What you will see below is an executable file, interspersed with a few comments, which are not strictly part of the argument, but are included so that some sense can be made of what is done without reading the full {\tt Split} documentation. The comments become progressively sparser, as we tend to explain each command type only once. \begin{svb} data_comment( ![ \par First we load the {\tt Split} data file from [.boukliev jaffe dimension seven.], and indirectly, the data file from [.jaffe optimal binary 30.]. We refer to the latter papers for the details about the codes and results which appear in the data files. In particular, we are not going to repeat here the definitions of optimal codes which appear in them, nor the nonexistence results contained therein, which are silently utilized in what follows. ]! ) accept inputs/code.data.sevens; type [41,8,18_2]; kill y34, y32, y30; show (joint, iterate) 82 <= y18 <= 90, 95 <= y20 <= 122, y22 <= 28, y24 <= 15, 23 <= y26 <= 39, 8 <= y28 <= 13, 112 <= div4 <= 136; kill [current] by (x_28|x_10_10); no [41,8,18]; data_comment( ![ \par We explain what these commands do. The {\tt type} command merely declares that {\it even\/} $[41,8,18]$ codes are under consideration. Then the {\tt kill} command shows by split linear programming (see e.g.{\ }[.brief tour split main.]) that there is no word of weight $34$. Then in the same manner, words of weight $32$ and $30$ are eliminated. The {\tt show} command uses joint linear programming (i.e.\ linear programming based on the joint weight enumerator) to bound the numbers of words of various weights, and {\tt div4}, the number of words whose weight is divisible by $4$. The latter utilizes results of Brouwer [.brouwer linear programming bound.]. The {\tt show} is iterative, employing a primitive form of integer linear programming. The second {\tt kill} command gives three applications of (split) linear programming, which complete the proof. Specifically: there must be a word of weight $28$; for any such word of weight $28$, there must exist a word of weight $20$ meeting it along $10$ ones; the split linear programming problem associated to the corresponding two-dimensional code is infeasible. The last command ({\tt no}) merely deduces the nonexistence of a $[41,8,18]$ code from the fact (now known) that no even $[41,8,18]$ code exists. ]! ) [19_6_8] type [19,6,8]; [x44] config from x8|x44; CLASS_TO([base], ![[a1..30] := Build( [19_6_8], [x44] )]!) data_comment( ![ \par The {\tt type} command declares that $[19,6,8]$ codes are under consideration and attaches the label \verb|[19_6_8]| to the work that follows. Then the {\tt config from} command establishes first that such a code has a word of weight $8$, and then that for every word of weight $8$, there is another word of weight $8$ meeting it along $4$ ones. Starting with a two-dimensional code (corresponding to two such words of weight $8$), the next command then establishes (via a search process) that there are exactly $30$ $[19,6,8]$ codes. They are labelled $\verb|[a1]|, \ldots, \verb|[a30]|$ for now, and are accessible later as $\verb|[19_6_8.a1]|, \ldots, \verb|[19_6_8.a30]|$. ]! ) [18_6_7] type [18,6,7]; CLASS_TO([base], ![[a1..113] := [19_6_8.a1..30] - column]!) data_comment( ![ \par The above two commands classify $[18,6,7]$ codes, of which there are $113$. This is easy because it is enough to delete columns from generator matrices for the just classified $[19,6,8]$ codes. ]! ) [32_7_14] type [32,7,14]; config 28,4 : {10}; config from x_14_0; kill [current] by (x774, x464, x473); @[base] infer y28 = 0; config 30,2 : {10}; config from x_12_2|x482; kill [current] by (x13352, x13442, x04451, x23450, x22352); @[base] infer y30 = 0; status: weights = 14_2 - {28..32}; CLASS_TO([base], ![[a1..36] := Unresidue( [32_7_14], [base], [18_6_7.a1..113] )]!) data_comment( ![ The first {\tt config} command puts us in the situation of considering a word (say $v$) of weight $28$ within such a code. The {\tt config from} command uses split linear programming to show that there then must be a word (say $w$) of weight $14$ inside $v$. Now the {\tt kill} line proceeds as follows. Consider a word of weight $7+7+4$ meeting $w$ along $7$ ones and $v$ along $7+7$ ones. To the associated three-dimensional code, there is a split linear programming problem, which the program shows is infeasible. This accounts for the \verb|x774|. Similar things happen for \verb|x464| and \verb|x473|. Then the split linear programming problem associated to $\inn{v,w}$ has three less variables, and another linear programming calculation confirms that it is infeasible. The {\tt infer} line then deduces (without computation) that in fact a $[32,7,14]$ code cannot have a word of weight $28$. The entire following paragraph accomplishes the same goal for words of weight $30$. It is similar but more complicated, and we omit the details. The {\tt status} command then asserts that a $[32,7,14]$ code has weights in the set \setof{0,14,16,18,20,22,24,26}. The {\tt status} command invokes a canned procedure which does this (in general) by a combination of split and joint linear programming. The final command determines all $[32,7,14]$ codes from their residuals \WRT\ a word of weight $14$, in approximately the manner specified in \S\ref{extension-section}. This utilizes the classification of $[18,6,7]$ codes. ]! ) [31_7_13] type [31,7,13]; CLASS_TO([base], ![[a1..533] := [32_7_14.a1..36] - column]!) no [55,7,26]; [57_8_26] type [57,8,26]; status: weights = {26,28,30,32,34,36,38,40,42,44}; CLASSIFICATION_OF5( [base], ![Unresidue( [57_8_26], [base], [31_7_13.a1..533] )]! ) no [57,8,26]; data_comment( ![ \par In light of previous explanations, the above commands are roughly self-explanatory. The one thing we might add is that the {\tt no} command is actually a rather complicated canned procedure, which uses a variety of methods. In the two cases here, what is actually done is not deep. ]! ) [60_8_28] type [60,8,28]; status: weights = {28,32,36,40,44}; CLASSIFICATION_OF5( [base], ![Unresidue( [60_8_28], [base], [20_7_8.{a1..21,b}] )]! ) no [60,8,28]; type [35,7,16]; status: weights = {16,20,24,28}; no [64,8,30]; no [39,7,18]; [39_7_17] type [39,7,17]; CLASS_TO([base], ![[x1..5649] := [40_7_18.x1..172] - column]!) [73_8_34] type [73,8,34_2]; kill y72, y70, y68, y66, y64, y62, y60 by (x_25_13, x_27_13, x_26_12, x_25_11, x_27_11, x_29_9, x_26_10, x_30_10, x_27_7, x_29_7, x_29_5, x_24_12); CLASSIFICATION_OF5( [base], ![Unresidue( [73_8_34], [base], [39_7_17.x1..5649] )]! ) no [73,8,34]; data_comment( ![ \par We comment only on the {\tt kill} line. It first uses split linear programming to eliminate many weights. In the case of words of weight $60$, this is more involved. We kill the local variable \verb|x_25_13|. That is, if there is a word of weight $60$, we show that there is no word of weight $25+13$ meeting it along $25$ ones. We do the same thing for many other local variables, finally arriving at the point where split linear programming yields a contradiction (directly) to the existence of a codeword of weight $60$. ]! ) [76_8_36] type [76,8,36]; status: weights = {36,40,44,48,52,56}; CLASSIFICATION_OF5( [base], ![Unresidue( [76_8_36], [base], [40_7_18.x1..172] )]! ) no [76,8,36]; no [78,7,38]; type [40,5,20]; status: weights = {20,24,28,32}, constraints = {26 <= y20 <= 28, 2 <= y24 <= 5, y28 <= 1, y32 <= 1}; type [80,6,40]; status: weights = {40,48,56,64}, constraints = {58 <= y40 <= 60, 2 <= y48 <= 5, y56 <= 1, y64 <= 1}; type [80,8,38_2]; kill y80, y64, y62, y44; show (joint, iterate) 150 <= y38 <= 151, 58 <= y40 <= 59, 34 <= y46 <= 36, 3 <= y48 <= 5, 6 <= y54 <= 7, y56 <= 1, 184 <= mu3 <= 188, div4 = 64; [38] config from x_38; config 38,42 : {10} :: {x_19_35 != 0}; kill x_18_36, x_14_32, x_16_32, x_10_28, x_15_31, x_12_28, x_18_28, x_11_27; via lp [current] = ; @[38] infer x_19_35 = 0; kill [current] by (x_16_32, x_15_31, x_12_28, x_18_28, x_11_27); no [80,8,38]; data_comment( ![ \par Our commentary starts at the paragraph beginning with \verb|config 38,42|. Here we put ourselves in the situation of supposing that we have a codeword $u$ of weight $38$, and in addition a codeword $v$ of weight $19+35$ meeting $u$ along $19$ ones. At the {\tt kill} line we consider first a codeword $w$ of weight $18+36$ meeting $u$ along $18$ ones. By split linear programming (applied to the two-dimensional code $\inn{u,w}$) we obtain a contradiction (to the existence of $w$). In total, eight such calculations are performed. At the {\tt via lp} line we then exploit this by considering the split linear programming problem associated to the one-dimensional code $\inn{u}$: it has eight less variables. As it is found to be infeasible, we deduce that $v$ did not exist. The remainder of the calculation is similar to what we have seen before. ]! ) no [88,8,42]; [47_7_22] type [47,7,22]; [a] := Cyclic( {15,15,15}, 47, 7, 00110100101010001111101100011000001110100010011 ); STATUS_WE(1 + 78t^22 + 30t^24 + 18t^30 + t^32) CLASSIFICATION_OF( [base], x_22|x_10_12|x4488, [a] ) status: unique; data_comment( ![ \par We define a $[47,7,22]$ code. Then we show that it is unique. This is accomplished by first determining its weight enumerator, then building (via split linear programming) a three-dimensional subcode of it, and finally achieving uniqueness by a search. ]! ) [123_8_60] type [123,8,60]; status: weights = {60,64,76}; CLASSIFICATION_OF( [base], ![Unresidue( [123_8_60], [base], [47_7_22.a] )]!, ) no [123,8,60]; data_comment( ![ \vspace{0.1in} \par\noindent{\footnotesize{\it Acknowledgements.} I.\ Bouyukliev wishes to thank Prof.\ Stoyan Kapralov and Dr.\ Svetlana Topalova. He has used a source code of Prof.\ Kapralov as a base of his program about isomorphisms of codes in {\tt Extension}. He has also used details from the algorithm of Dr.\ Topalova on isomorphisms of designs [.topalova thesis.].} ]! ) |-> TEX_IN \end{svb} \section*{\fbox{\bf References}} \addcontentsline{toc}{section}{References} \ \par\noindent\vspace*{-0.25in} .[] \end{document} |-> tex/run_tex_e # setkeyx tr %  < code.tex.eights > tempx tibline echo \\documentstyle\[amssymb,12pt\]\{invent\} > t.tex tr  % < t.tex0 | cat -s | sed -f sed.in > t.tex1 awk 'BEGIN {found=0} \ {if ($1 ~ /\\def\\Astr\{\\Underlinemark\}\%/) \ {if (found) {print} else {found=1}} else {print}}' < t.tex1 >> t.tex if ($status != 0) goto fail latex t | tail +8 endif fail: /bin/rm -f tempx t.tex0 t.tex1 temp >& /dev/null