This is an interim version of Split. Some notes (mostly to myself) regarding work in progress follow. Feel free to skip ahead to the copyright notice. ------------------------------------------------------------------------------ @"Adjoin extra constraints if the code is even" - see file 96 for evidence it helps. ------------------------------------------------------------------------------ CharPoly2 undocumented ------------------------------------------------------------------------------ Make sure bypassing subdivision in add_constraint is OK. Document? ------------------------------------------------------------------------------ Note: DirectSum changed to Diag. ------------------------------------------------------------------------------ try ProjectOffWeight( [112_8_54.b1], 76 ); ------------------------------------------------------------------------------ solvefor undocumented ------------------------------------------------------------------------------ Refashion PVSF2 as List(List(List(F2))){partition}. ------------------------------------------------------------------------------ Revisions to generic class Int: attribute pos attribute nonneg attribute 1byte: forces storage as char (1 byte); must have -2^7 < x < 2^7 (or 0 <= x < 2^8 if pos or nonneg) attribute 4byte: forces storage as int (4 bytes), but must have -2^31 < x < 2^31 (or 0 <= x < 2^32 if pos or nonneg) Note that these effect the behavior of the FUN processor. ------------------------------------------------------------------------------ Symbols and their scope (plan) 1. A scope name has the form [s], where s consists of one or more letters or digits or underscores. 2. A temporary (and documented) scope command has been added, which is not completely consistent with what follows. (More thought is needed.) ------------------------------------------------------------------------------ Improvements to execute_build_web: 1. No [21,8,8] codes are shown even though we've classified the even ones. 2. Speed up config_to_web. ------------------------------------------------------------------------------ The following classifies [12,5,3] codes. What should be done with it? [13_5_4e] type [13,5,4_2]; via building [current] implies [x#]; classification of [base]: [x*]; type [12,5,3]; [x1..1285] := [13_5_4e.x*] - column; ??classification of [base]: [x*]; ------------------------------------------------------------------------------ Two concurrent Split processes can get into trouble by simultaneously writing the same hints file. ------------------------------------------------------------------------------ Eliminate QuadraticResidue. ------------------------------------------------------------------------------ % If a global variable is set equal to one, it should add_constraint should % infer that certain joint variables are zero. % Problem posed by Tor Helleseth, coming from an old problem: Is there % a projective [241,10,113] code having the all ones vector? % process_new_matrix doesn't check against config_list_on_disk's % [a1..200] := etc. doesn't set realizability flag for code type % pork19x.out: tons of stuff % Work in progress: 76, 76.out % [245,8,122]'s are classified but process_new_matrix still ends up % doing isomorphic checks on them % % config from doesn't allow repeated labels % % Lots of the stuff at (config) doesn't work correctly for nonrefined % configurations. % % roots undocumented and presumably temporary % show roots undocumented % % ec length limit, ec fill undocumented % % random code search only works for auto orbit transform % force improvement, alternate quality criterion undocumented % ------------------------------------------------------------------------------ % Copyright(c) 1998-1999 David B. Jaffe % Permission to use, copy, modify, and distribute any document (including this % one) which is part of the Split distribution is hereby granted without fee, % for any noncommercial purpose, provided that this paragraph is copied, % conspicuously referenced, that an explanation is included which % explains what portion of the Split distribution has been utilized, and that % no other person's copyright is thereby infringed. % % The following materials in the distribution are owned by other people: % Brendan McKay (the graph isomorphism package nauty; in NOT_MINE) % Keith Briggs (double-double precision arithmetic; in NOT_MINE) % Victor Shoup (ntl: a library for doing number theory; in NTL) % Free Software Foundation (prevector::sort; in CODE) % U. C. Berkeley (random.c; in NOT_MINE) % Hewlett-Packard (pair and make_pair; in CODE). define(VERSION, `0.6alpha') % Hints for selective recompilation: % % If you edit a class definition, you should probably recompile the % whole shebang. For other changes, search backwards for the string % "set_com". You will find the name of the file which needs to be % recompiled. % Hints for debugging: % % 1. Go through and activate all "#define DEBUG" lines by deleting % the "// " which preceeds them. % 2. Make SLList.h safer. % (a) Make a local copy. % (b) Modify "T& operator () (Pix p)" and the const version by adding % a line `if (!owns(p)) error("illegal Pix");'. % (c) Change #include so it fetches local copy instead. define(TEX_IN,`tex/code.tex') define(DATA_IN,`inputs/code.data') define(newresultcounter,9) include(src/MACROS) ifelse(UNAME,OPENSTEP,![DEFINE(UNAME,Openstep)]!) |-> tex/t.ista preamble "\\begin{theindexa}\n" postamble "\n\n\\end{theindexa}\n" |-> tex/t.istb preamble "\\begin{theindexb}\n" postamble "\n\n\\end{theindexb}\n" |-> tex/t.istz preamble "\\begin{theindexz}\n" postamble "\n\n\\end{theindexz}\n" |-> tex/code.tex % \second % [.stepanov lee.] \hfuzz 10pt % Create quote macros to sync with 5n character indentation in verbatim % environment. \def\quotea{\list{}{\def\leftmargin{62pt}\advance\linewidth -26pt}\item[]} \let\endquotea=\endlist \def\quoteaneg{\vspace{-0.35in}\list{}{\def\leftmargin{62pt}\advance\linewidth -26pt}\item[]} \let\endquoteaneg=\endlist \def\quoteb{\list{}{\def\leftmargin{93pt}\advance\linewidth -29pt}\item[]} \let\endquoteb=\endlist \def\quotebneg{\vspace{-0.35in}\list{}{\def\leftmargin{93pt}\advance\linewidth -29pt}\item[]} \let\endquotebneg=\endlist \def\quotec{\list{}{\def\leftmargin{124pt}\advance\linewidth -32pt}\item[]} \let\endquotec=\endlist \def\quotecneg{\vspace{-0.35in}\list{}{\def\leftmargin{124pt}\advance\linewidth -32pt}\item[]} \let\endquotecneg=\endlist \def\quoted{\list{}{\def\leftmargin{155pt}\advance\linewidth -35pt}\item[]} \let\endquoted=\endlist \def\quotee{\list{}{\def\leftmargin{186pt}\advance\linewidth -38pt}\item[]} \let\endquotee=\endlist % 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 \pagestyle{empty} \vspace*{0.8in} \widepost{40}{40}{/Times-Roman findfont 40 scalefont setfont (Binary linear codes:) dup stringwidth pop 2 div neg 0 moveto 50 0 rmoveto true charpath StrokeFill} \vspace{0.1in} \widepost{40}{40}{/Times-Roman findfont 40 scalefont setfont (new results on nonexistence) dup stringwidth pop 2 div neg 0 moveto 50 0 rmoveto true charpath StrokeFill} \vspace{0.4in} \widepost{28}{28}{/Times-Roman findfont 28 scalefont setfont (Draft, October 25, 1998) dup stringwidth pop 2 div neg 0 moveto 50 0 rmoveto true charpath StrokeFill} \vspace{-0.05in} \widepost{28}{28}{/Times-Roman findfont 28 scalefont setfont (\(Version 0.6alpha\)) dup stringwidth pop 2 div neg 0 moveto 50 0 rmoveto true charpath StrokeFill} \vspace{0.5in} \widepost{28}{28}{/Times-Roman findfont 28 scalefont setfont (David B. Jaffe) dup stringwidth pop 2 div neg 0 moveto 50 0 rmoveto true charpath StrokeFill} \vspace{0.3in} \widepost{28}{28}{/Times-Roman findfont 28 scalefont setfont (Department of Mathematics and Statistics) dup stringwidth pop 2 div neg 0 moveto 50 0 rmoveto true charpath StrokeFill} \widepost{28}{28}{/Times-Roman findfont 28 scalefont setfont (University of Nebraska) dup stringwidth pop 2 div neg 0 moveto 50 0 rmoveto true charpath StrokeFill} \widepost{28}{28}{/Times-Roman findfont 28 scalefont setfont (Lincoln, NE 68588-0323) dup stringwidth pop 2 div neg 0 moveto 50 0 rmoveto true charpath StrokeFill} \widepost{28}{28}{/Times-Roman findfont 28 scalefont setfont (e-mail: jaffe@cpthree.unl.edu) dup stringwidth pop 2 div neg 0 moveto 50 0 rmoveto true charpath StrokeFill} \newpage %% \ \newpage %% Insert to get even number of pages if needed. \pagestyle{plain} \def\GAPref{\protect{[.groups algorithms programming.]}} \vspace*{-0.4in} \begin{center} \LARGE\bf Preface \end{center} \addcontentsline{toc}{special}{Preface} \def\classbreak{\par\noindent\kern32pt% \hbox to 6.35in{\leaders\hbox{\vbox{\hrule width1mm height 0.5pt}}\hfil}} \newenvironment{classboxedquote}% {\vskip0.065in\par\noindent\kern31pt\begin{Sbox}\begin{minipage}{6in}}% {\end{minipage}\end{Sbox}\fbox{\TheSbox}\vskip0.065in} \def\classtext#1{\begin{classboxedquote}#1\end{classboxedquote}} \newenvironment{classboxedquotet}% {\vskip0.065in\par\noindent\kern31pt\begin{Sbox}\begin{minipage}{6in}% \begin{tabbing}}% {\end{tabbing}\end{minipage}\end{Sbox}\fbox{\TheSbox}\vskip0.065in} \def\classtextt#1{\begin{classboxedquotet}#1\end{classboxedquotet}} \newenvironment{classboxedquotefour}% {\vskip0.065in\par\noindent\begin{Sbox}\begin{minipage}{4in}}% {\end{minipage}\end{Sbox}\fbox{\TheSbox}} \vspace{0.25in} {\large This is a working draft of a report which describes a new language for proving results about binary linear codes, and moreover exhibits a program in this language which proves many new results. Source code ({\tt C++}) for the language is included. The author gratefully acknowledges partial support under NSF grants DMS-9100983 and DMS-9623205, and as well wishes to thank the NSF-sponsored Geometry Center for supercomputer access, which facilitated exploratory calculations. John Gregory, Spyros Magliveras, Eric Rains, and Neil J.\ A.\ Sloane provided helpful comments and suggestions. I thank Juriaan Simonis (and TU Delft) for supporting a stimulating visit during the second half of May 1996, for introducing me to the work of [.brouwer van eupen 1997.], and for several enlightening converations which led to the work of \S\ref{menagerie-section}. The language employs the graph isomorphism package {\tt nauty} of Brendan McKay, the double-double precision floating point arithmetic package {\tt doubledouble} of Keith Briggs [.briggs doubledouble.], and the number theory library of Victor Shoup [.shoup ntl.]. The routines {\tt prevector::sort} are in effect copyrighted by the Free Software Foundation. The definitions of {\tt pair} and \verb|make_pair| are copyrighted by Hewlett-Packard. A number of unpublished codes discovered by J.\ B.\ Shearer are included in this document, as well as one code discovered by M.\ Morii. The material on designs in \S\ref{some-unital-section}, the associated % Using {\it options} below had weird unintended consequences when using xdvi. ``options'' field in the {\tt type} command, and the implementation of the latter arose as part of joint work with Tonchev [.jaffe tonchev rank 20.]. \vspace{0.05in} To obtain this draft or the source code itself, see the World Wide \vspace{0.01in} \par\noindent Web at ``\verb|http://www.math.unl.edu/~djaffe/#coding|''. For a more leisurely introduction, see [.brief tour split main.]. } \newpage \vspace*{-0.3in} \par\noindent{\LARGE\bf Contents} \vspace{0.15in} {\footnotesize\ \catcode`\@=11 \@starttoc{toc} \catcode`\@=12} \newpage % Set up for indices. \def\indexnamez{Index of C++ classes} \def\indexnamea{Index of C++ methods} \def\indexnameb{Index of commands} \catcode`\@=11 \def\theindexz{\@restonecoltrue\if@twocolumn\@restonecolfalse\fi \columnseprule \z@ \addcontentsline{toc}{special}{\indexnamez} \columnsep 35\p@\twocolumn[{\Large\bf Index of C++ classes}\\ \\ ]% \@mkboth{\uppercase{\indexnamez}}{\uppercase{\indexnamez}}% \thispagestyle{plain}\parindent\z@ \parskip\z@ plus.3\p@\relax\let\item\@idxitem} \def\theindexa{\@restonecoltrue\if@twocolumn\@restonecolfalse\fi \columnseprule \z@ \addcontentsline{toc}{special}{\indexnamea} \columnsep 35\p@\twocolumn[{\Large\bf Index of C++ methods}\\ \\ This list should index all C++ methods and macros defined in the source code, except that not all constructors, destructors, and operators are included. We also do not include the {\tt execute\string_}$\ldots$ commands from \S\ref{main-program-section}, which execute particular commands. These may be found from the index of commands. \\ \\ ]% \@mkboth{\uppercase{\indexnamea}}{\uppercase{\indexnamea}}% \thispagestyle{plain}\parindent\z@ \parskip\z@ plus.3\p@\relax\let\item\@idxitem} \def\theindexb{\@restonecoltrue\if@twocolumn\@restonecolfalse\fi \columnseprule \z@ \addcontentsline{toc}{special}{\indexnameb} \columnsep 35\p@\twocolumn[{\Large\bf Index of commands}\\ \\ For each command, we give first the page on which the command is defined, and then the corresponding page in the source code. If the body of the command is executed as a separate subroutine, a page number is also given for that, intermediate between the first two numbers. \\ \\ ]% \@mkboth{\uppercase{\indexnameb}}{\uppercase{\indexnameb}}% \thispagestyle{plain}\parindent\z@ \parskip\z@ plus.3\p@\relax\let\item\@idxitem} \def\endtheindexa{\if@restonecol\onecolumn\else\clearpage\fi} \def\endtheindexb{\if@restonecol\onecolumn\else\clearpage\fi} \catcode`\@=12 \part{Introduction} \block{Synopsis} A basic problem in coding theory is to determine the maximum number $B(n,d)$ of codewords in a binary linear code in $\F_2^n$ having minimum weight $d$. While the original motivation for this problem came from practical problems of data transmission, continuing interest is due also to the fact that binary linear codes are such basic combinatorial structures. Many proofs of bounds for specific $B(n,d)$ have as input statements of bounds for $B(n',d')$, where $n' < n$. Proofs thus have a hierarchical nature, and if one wants specific results about the $B(n,d)$, one is naturally lead to construct tables. This has been done by Helgert and Stinaff [.helgert stinaff.], Verhoeff [.verhoeff 1987.], Brouwer and Verhoeff [.brouwer verhoeff 1993.], and Bierbrauer and Edel [.bierbrauer edel parameters binary.]. But the numbers $B(n,d)$ are extremely difficult to compute and there remain gaps even for small $n$ and $d$. The problem of finding lower bounds has been addressed by a vast array of fascinating constructions. These are of ongoing interest but do not form the subject matter of this report. Rather, we address the problem of how one may find {\it upper\/} bounds. Some of the major general contributions to this problem have been (in approximate historical order) Griesmer's bound [.griesmer 1960.], Johnson's bound [.johnson unrestricted.], Delsarte's linear programming method [.delsarte bounds unrestricted.], Hill and Traynor's examples [.hill traynor.], Brouwer's generalized parity type argument [.brouwer linear programming bound.], and Simonis's use of coordinate partitions [.simonis partitions.]. In addition, many people have contributed specific results, and thus methods, more often than not. A number of software packages have been developed for computing upper (and lower) bounds for $B(n,d)$. These packages include [.code buster.], [.guava.], LINCOR [.manev lincor 1987.], [.manev petkova golemanova.], and the system used by Brouwer and Verhoeff to generate [.brouwer verhoeff 1993.]. In addition, there exists software for computing automorphism groups of codes and for determining if two codes are isomorphic. We defer discussion of this to \S\ref{automorphismisomorphismsection}. In this report\footnote{This refers not only to this document, but also to [.jaffe optimal binary 30.], which contains results for length $\leq 30$.}, we give improved upper bounds for the $B(n,d)$, in total \ref{NewResultCount} improvements. This is actually quite modest progress: whereas before the first unknown case occurred when $n = 28$, now the first unknown case occurs when $n = 32$. As an example we establish that $B(28,9) = 2^{10}$ by showing that there is no $[28,11,9]$ binary linear code.% \footnote{General background on coding theory may be found in [.macwilliams sloane book.]. Another good reference is [.lint coding theory.]. In this paper we make the slightly non-standard convention that an $[n,k,d]$ binary linear code is a sub-vector space $C$ of $\F_2^n$ having dimension $k$, such that no non-zero element of $C$ has weight $< d$. Also, by {\bf code}, we shall always mean {\bf binary linear code}.} The vehicle for these improvements is a computer language which we present. Its general purpose is to investigate binary linear codes. We exhibit a program (written in the language) which yields the aforementioned improvements to the $B(n,d)$. This program is completely self-contained, in the sense that all needed results about specific codes are proved within the confines of the program. We do this to complement rather than supplant the ``pencil and paper'' proofs which exist in some cases. This report also includes (with proof) a complete table of all known specific upper bounds, for codes of length $85$ or less, and extensive information about the weight enumerators of codes which may or may not exist. The first part of this paper is the introduction. The second part is a description of the language and its theoretical basis. The third part is a program, written in the language, which yields specific results about binary linear codes. The forth part of the paper is C++ source code for an implementation of the language. These are also available electronically from the author.% \footnote{The program should be easy to install on any Unix-based machine. The current implementation includes a provisional implementation of the simplex method, and as an alternative also includes support for a much faster commercial linear programming package, CPLEX. As of October 1995, the cost to academic users of a CPLEX ``Linear Optimizer Single CPU License'' is \$495. Mail to \verb|info@cplex.com| for more information.} Both the language and the program are ongoing projects, to which contributions are invited. \block{Basic data structures and definitions}\label{definitions-section} We describe the basic data structures of the language, in a somewhat idealized fashion. For practical reasons the actual data structures differ slightly from the descriptions we give here; most of these differences are mentioned in \S\ref{variable-section} and \S\ref{proof-command-section}. The top-level structure in the language is a {\bf code type}. It is a triple $(n,k,\cal S)$ consisting of a positive integer $n$, an integer $k$ ($1 \leq k \leq n$), and a finite set $\cal S$ of inequalities (called {\bf assumed constraints}) having the form $$a_0 y_0 \many+ a_n y_n \leq r,$$% where $\VEC a0n,r$ are integers. The variables $y_i$ (for computer input written \verb|y|$i$) are called {\bf basic global variables}. The {\bf dimension} of a code type is $k$. The {\bf realization} of a code type $(n,k,\cal S)$ is the set of all codes $C \IN \F_2^n$ of dimension $k$ such that if $y_i$ denotes the number of words of weight $i$ in $C$, then all inequalities in $\cal S$ are satisfied. (We refer to this general sort of operation as {\bf evaluation} on a code.) A code type is {\bf unrealizable} if its realization is empty, otherwise it is {\bf realizable}. A {\bf global variable} is a $\Q$-linear combination of basic global variables, whose evaluation on every $[n,k]$ code is an integer. Below each code type $(n,k,\cal S)$ lives a family of structures called {\bf configurations}. Each such structure is a quadruple $(p, D, D', \cal T\kern2pt)$ consisting of a partition% \footnote{We mean by this that $\VEC p1r \in \N$ and that $p_1 \many+ p_r = n$.} $p = (\VEC p1r)$ of $n$, two subcodes $D, D'$ of $\F_2^r$, and a finite set $\cal T$ of inequalities (again called {\bf assumed constraints}) having the form $$a_0 y_0 \many+ a_n y_n + \sum_I a_I x_I \leq r,$$% where $I = (\VEC i1r)$ is a {\bf multi-index\/} (or more precisely a {\it multi-index for $p$}, meaning that $0 \leq i_j \leq p_j$ for each $j$), and $\VEC a0n, a_I, r \in \Z$. The variables $x_I$ (for computer input written \verb|x_|$i_1$\verb|_|$\ldots$\verb|_|$i_r$) are called {\bf basic local variables}; the {\bf trivial} basic local variable is $x_{(0,\ldots,0)}$. We say that $D$ is the {\bf small code} of the configuration, and that $D'$ is the {\bf dual small code} of it. The {\bf dimension} of a configuration is defined to be $\dim(D)$. For the duration of the introduction, we fix the above notations for code types and configurations. Supposing for simplicity that $D' = 0$ and that $\cal T = \emptyset$, we may visualize the configuration by exhibiting a basis for $D$. By way of an example, let us reverse this process. Suppose we wish to study codes $C \IN \F_2^{25}$ which contain a word of weight $10$ and a word of weight $12$, intersecting along $4$ bits: \widepost{70}{35}{ {{100 26 Box {(6) BigCenterPrint} 50 6 xyput} -150 4 xyput {100 26 Box {(4) BigCenterPrint} 50 6 xyput} -50 4 xyput {100 26 Box {(4) BigCenterPrint} 50 6 xyput} -50 -30 xyput {100 26 Box {(8) BigCenterPrint} 50 6 xyput} 50 -30 xyput} 50 xput} \par\noindent We would be led to consider the partition $(6,4,8,7)$ of $25$ and the small code $D$ with basis \setof{1100,0110}. It is the picture which justifies the term {\it configuration}: it conforms to the dictionary definition as it is a {\it relative arrangement of parts}. We return to the general situation.\label{action-def} Given $d \in D$, and a multi-index $I$, define a multi-index $d(I)$ by $$d(I)_j\ =\ \cases{i_j,&if $d_j = 0$;\cr p_j - i_j,&if $d_j = 1$.}$$% Then $D$ acts on the set of multi-indices, and accordingly on basic local variables. We regard two basic local variables as {\bf equivalent} if they lie in the same orbit \WRT\ this action. We define two configurations to be {\bf equivalent} if they differ only in changing $\cal T$ by replacing some occurrences of basic local variables by equivalent ones. Given a partition $p = (\VEC p1r)$, we shall say that a partition $\loP = (\loP_1,\ldots,\loP_s)$ {\bf refines} $p$ if there exist $$0 = \beta_0 < \beta_1 < \cdots < \beta_r = s$$% such that $$p_j\ =\ \loP_{\beta_{j-1}+1} \many+ \loP_{\beta_j}$$% for all $j = 1,\ldots,r$. There is an induced map \mp[[ \varphi || \F_2^r || \F_2^s ]] given by $\varphi(e_j) = e_{\beta_{j-1}+1} \many+ e_{\beta_j}$. Now given a configuration $c = (p,D,D',{\cal T})$ as before, and given a refinement $\loP$ of $p$ as above, we define the {\bf refinement $\loC$ of $c$ induced by $\loP$} to be $\loC = (\loP,\varphi(D),\varphi(D'),\ol{\cal T})$, where $\ol{\cal T}$ is yet to be defined. First define a {\bf pullback} map \mp[[ \Psi || \setofh{multi-indices of $\loP$} || \setofh{multi-indices of $p$} ]] by $$\Psi(\oI)_j = \oI_{\beta_{j-1}+1} \many+ \oI_{\beta_j}.$$ Now given $f \in \cal T$, define $\loF$ by replacing each basic local variable $x_I$ by $\sum x_{\oI}$, where $\oI$ ranges over the multi-indices of $\loP$ with $\Psi(\oI) = I$. Then $\ol{\cal T}$ is defined to be \setof{\loF: f \in \cal T}. Given the configuration $c$, and a basic local variable $x_I$ of $c$, we define a new configuration $c|x_I$, called the {\bf subdivision of $c$ along $x_I$}, as follows. First define a partition $\loP$ by $$q_j\ =\ \cases{(p_j),&if $i_j \notin \setof{0,p_j}$;\cr (i_j, p_j - i_j),&otherwise,}$$% and $\loP = (\VEC q1r)$ (with internal parentheses removed). Let $s$ be the length of $p$. Define $v$ by $$v_j\ =\ \cases{(0),&if $i_j = 0$;\cr (1),&if $i_j = p_j$;\cr (1,0),&otherwise,}$$ $$v\ =\ (\VEC v1r)\ \ \hbox{(with internal parentheses removed)}.$$% Let $\loC = (\loP,\oD,\ol{D'},\ol{\cal T})$ be the refinement of $c$ induced by $\loP$. Then $c|x_I = (\loP, \oD + \inn{v}, \ol{D'}, \ol{\cal T})$, where $\oD + \inn{v}$ is the subspace of $\F_2^s$ generated by $\oD$ and $v$. An element of $\F_2^r$ is a {\bf small word}. Let \mp[[ \pi_i || \F_2^n || \F_2^{p_i} ]] be the ``\th{i} projection map''. A {\bf basic word} is an element $x \in \F_2^n$ such that for each $i$, $\pi_i(x)$ is either $0\ldots0$ or $1\ldots1$. Evidently there is a bijective correspondence between small words and basic words. A {\bf basic code} is a code in $\F_2^n$ consisting entirely of basic words. For any code in $\F_2^r$, there is an {\bf associated} basic code in $\F_2^n$. If $w \in \F_2^n$, the \th{i}\ weight $\abs{w}_i$ of $w$ is the weight of $\pi_i(w)$. The {\bf multiweight} of $w$ is the $r$-tuple $(\abs{w}_1,\ldots,\abs{w}_r)$; its {\bf weight} $\abs{w}$ is $\abs{w}_1 \many+ \abs{w}_r$. The {\bf realization} of the configuration is the set of all codes $C$ in the code type, which, after permuting coordinates if need be, have all of the following properties: \begin{itemize} \item for each small word in $D$, the associated basic word lies in $C$; \item for each small word in $D'$, the associated basic word lies in $C^\perp$; \item if $y_i$ denotes the number of words of weight $i$ in $C$ and $x_I$ denotes the number of words in $C$ which have multiweight $I$, then all inequalities in $\cal T$ are satisfied. \end{itemize} For $c$ a configuration, we let ${\cal R}(c)$ denote its realization, and we let $\ol{\cal R}(c)$ denote the set of isomorphism classes in ${\cal R}(c)$. The same terminology {\bf unrealizable}, {\bf realizable} applies to configurations. A {\bf local variable} is a $\Q$-linear combination of basic local variables, whose evaluation on every code in the realization of the code type is an integer. Since basic global variables are expressible as linear combinations of basic local variables (upon evaluation), the inclusion of basic global variables in the definition of assumed constraints (for a configuration) is formally superfluous. However, it turns out to be convenient and economical to formally distinguish between local and global variables in constraints. To each configuration, the language associates a list of {\bf known} constraints. Initially, this list consists of the assumed constraints for the code type and the assumed constraints for the configuration. But as a program is executed, various commands may be used to prove that other constraints hold for the configuration: these constraints are also considered to be known. For every code type, there is the {\bf base} configuration, which by definition has the trivial partition $(n)$, $D = 0$, $D' = 0$, and $\cal T = \emptyset$. Obviously the realization of the base configuration is the same as the realization of the code type. We also refer to a {\bf basal} configuration, by which we mean a configuration with the properties of a base configuration, except that $\cal T$ may be arbitrary. Call a configuration {\bf full} if its dimension equals the dimension of the code type. A {\bf terminal} configuration is a full configuration having $D' = 0$, and whose assumed constraints involve only global variables. Obviously a terminal configuration admits (up to isomorphism) at most one realization, and if there is one, it is the basic code associated to $D$. We refer to $D$ as the code {\bf corresponding} to the given terminal configuration. If a realizable terminal configuration has assumed constraints, these constraints simply give facts which are deducible from the weight enumerator of $D$. A complete classification for a code type might be construed as being an exhibition of realizable terminal configurations $\VEC c1m$ such that $${\cal R}(\hbox{base})\ =\ {\cal R}(c_1) \sqcup \cdots \sqcup {\cal R}(c_m) \ \ \hbox{(disjoint union)}.$$% As this is a desirable goal and a feasible one so long as $\abs{\ol{\cal R}(\hbox{base})}$ is small, the language facilitates logical statements holding between the sets ${\cal R}(c)$, where $c$ ranges over the configurations associated to the code type. In brief, we refer to such statements as {\it logical statements holding between the configurations}. Even in lieu of a complete classification, such statements permit partial classification, for instance up to weight enumerator. A configuration is {\bf fully refined} if its partition has the form $1,\ldots,1$. An {\bf automorphism} of a configuration $c$ is a permutation $\sigma$ of $1,\ldots,r$ such that $\sigma(c)$ is equivalent to $c$. We let $\Aut(c)$ denote the group of all automorphisms of $c$. In case $c$ is realizable and terminal, and $p_i = 1$ for all $i$, we have $\Aut(c) = \Aut(D)$. \block{Method: finding automorphisms and isomorphisms of codes}% \label{automorphismisomorphismsection} The problem is to find generators for the automorphism group of a code $C$, and to determine if two given codes are isomorphic. There are two established schemes for solving such problems. For both schemes, one must start with a subset $S$ of $C$ which is stable under the action of $\Aut(C)$, and which is ``sufficiently large''. Here we take this to mean that $S$ generates $C$ as a vector space. In practice, one should expect the size of $S$ to grow exponentially as a function of $\dim(C)$. Thus both schemes will yield algorithms whose execution time grows exponentially, and not just for the worst cases. It remains an open problem to find algorithms whose execution time (on average, at least) is polynomial in $n$ (the length) and $k$ (the dimension). The first scheme proceeds by reducing to the analogous problems for graphs.% \footnote{This approach seems to be well-known but the author is indebted to D.\ Stinson and V.\ Tonchev for independently pointing it out to him.} One may form a zero-one matrix, with one row for each $x \in S$, by writing out $x$ as an element of $\F_2^n$. This matrix may be regarded as defining a bipartite graph $G$, and clearly $\Aut(G) = \Aut(C)$. If $C'$ is another code of length $n$, and a bipartite graph $G'$ is constructed in the same way, then $C \iso C'\ \Longleftrightarrow\ G \iso G'$. The complexity of the graph isomorphism problem is not well understood; more specifically, it is not known if the problem admits a polynomial-time algorithm, nor is it known if it is NP-complete. There do exist algorithms whose reported average running time is quadratic as a function of the number of vertices. McKay has implemented such an algorithm ([.practical graph isomorphism.], [.nauty guide onepointfive.]) and we employ his program {\tt nauty} here. The second scheme is that of Leon [.leon computing automorphism groups 1982.], [.leon computing automorphism groups 1984.]. It has the advantage of working with all linear codes, not just binary ones. The implementation [.leon partition backtrack manual.], [.leon partition backtrack source.], [.leon partition backtrack examples.] is a very impressive piece of work, over $25,000$ lines of code, the accessibility of which would be greatly enhanced by additional documentation. \block{Method: split linear programming}\label{split-intro-section} Now we turn to a method which we call {\bf split linear programming}. While the author came to this independently by combining the notion of split weight enumerator ([.macwilliams sloane book.]\ pp.\ 149-150) with Delsarte's linear programming method [.delsarte bounds unrestricted.], credit for the concept is due to Simonis [.simonis partitions.], and in fact the idea had been used successfully prior to the author by Heijnen [.heijnen.]. Having fixed a partition $(\VEC p1r)$ of $n$, let $C \IN \F_2^n$ be a code. For $I = (\VEC i1r)$ a multi-index, let $t^I$ denote $t_1^{i_1} \manycdot t_r^{i_r}$, where $\VEC t1r$ are indeterminates. An {\bf $I$-word\/} is a word of multiweight $I$; we let $x_I$ denote the number of $I$-words in $C$. Then the {\bf split weight enumerator} of $C$ is $$\sum_I x_I t^I,$$% where $I$ ranges over all multi-indices. We will show that the split weight enumerator of $C^\perp$ is $${1 \over \abs{C}} \sum_{I = (\VEC i1r)} x_I \prod_{j=1}^r (1+t_j)^{p_j - i_j} (1-t_j)^{i_j}.$$% This is not difficult to prove, and in fact the case where the partition is $(m,m)$ for some $m$ may be found as an exercise in [.macwilliams sloane book.], on p.\ 150. Regard this expression as a polynomial in $\VEC t1r$; its coefficients (say $m_I$) are $\Q$-linear combinations of the variables $x_I$. As these coefficients are evidently nonnegative, we arrive immediately at a linear programming problem, just as one would arrive at such a problem via Delsarte's original linear programming method. To actually use this method, one should start with a configuration, and not just a partition. Now if two basic local variables are equivalent, they will have the same evaluation on any realization of the configuration. Therefore we may select one basic local variable from each equivalence class, and modify the linear programming problem so that only these selected variables occur. This greatly reduces the complexity of the problem. As an example, in investigating $[31,13,10]$ codes (discussed below), we arrive at a configuration with partition $(10,10,11)$. This would (a priori) give rise to a system having $1452$ variables and $1452$ constraints. But by using equivalence of basic local variables (and other ideas, to be discussed next), we reduce this to a problem involving $136$ variables and $245$ constraints. This reduction is of paramount importance. There is a second way one can reduce the number of variables. A basic local variable $x_I$ (for a configuration $c$) is {\bf inadmissible} if at least one of the following three things happens: \begin{romanlist} \item For some equivalent basic local variable $x_J$ which is equivalent to $x_I$, the constraint $x_J = 0$ is known for the configuration. \item $x_I$ is not equivalent to the trivial basic local variable, and if $d$ is the subdivision of $c$ along $x_I$, then the weight enumerator of the basic code associated to the small code of $d$ contradicts a known constraint of the form $y_i \leq r$. \item For some equivalent basic local variable $x_J$ which is equivalent to $x_I$, there exists some $d' \in D'$ such that $d' \cdot J$ (dot product) is odd. \item It would violate the zeroness of a joint variable which is known to be zero. \end{romanlist} In any realization of the configuration, the inadmissible basic local variables will evaluate to zero. Therefore we may delete the inadmissible variables from the linear programming problem. A priori we get one constraint for each multi-index $I$. In fact, no information is lost if we use only some of the constraints, as follows. First, if $I \cdot d \not= 0$ (in $\F_2$) for some $d \in D$, then the constraint associated to $I$ is identically zero, and we may omit it. Second, for $d' in D'$, we can define $d'(I)$ just as we defined $d(I)$ (p.\ \pageref{action-def}), and we arrive thusly at a notion of {\bf dual equivalence} for the variables $m_I$. It is then sufficient to use one constraint from each equivalence class. In practice, one can do better by using (in place of $D'$) an enlarged version of it (say $(D')^+)$, which includes words known by the language to be dual. Thus if the constraint $y_j = 0$ is known for every odd $j$, then the word $1\ldots1$ is in $(D')^+$, and if the constraint $y_j = 0$ is known for every $j$ not divisible by four, then all of $D$ is in $(D')^+$ as well. Now we illustrate the application of the split linear programming method by means of a real example: we show that there is no $[31,13,10]$ code. In the program we will prove the stronger statement that there is no $[29,11,10]$ code, but this is more involved. In the course of the argument we will consider three configurations, and correspondingly apply the method three times. Only the last application will be nontrivial, as the conclusion of the first two may easily be recovered by other means. The split linear programming method gets applied three times: \begin{itemize} \item There is a word of weight $20$. This calculation corresponds to considering the trivial partition $(31)$ of $31$. One finds that \verb|x_20| is nonzero. In other words, the code has a word of weight $20$. Thus far the method is a mere rephrasing of Delsarte's linear programming method. \item Use the word of weight $20$ to subdivide the original partition, yielding the partition $(20,11)$. Show that \verb|x_10_0| $\not= 0$. That is, show that there is a word of weight $10$ in the code which is contained in the word of weight $20$. This statement is also obvious. \item Subdivide again, yielding the partition $(10,10,11)$. A final application of the method yields a contradiction. \end{itemize} In this example, $D'$ is always zero. In succession, $D$ consists of the zero code (in $\F_2^1$), then the code with basis \setof{10} (in $\F_2^2$), and finally the code with basis \setof{110,100} (in $\F_2^3$). Although there are in principle oodles of configurations, only certain ones are known to the program as it executes. These get created in various ways, for instance by explicit declaration in a ``{\tt config}'' command. (See the worked example below.) Also, the program automatically knows about the base configuration. The configurations are also the vertices of a directed multigraph\label{first-multigraph-occurrence}, whose connected components correspond to logical equivalence classes: if two configurations lie in the same connected component, then they have the same realization. There are two types of edges. The first type (which we call {\bf constructive}) corresponds to a basic local variable; a nontrivial variable is used to subdivide a given configuration, yielding another (the target of the edge). The second type of edge (which we call {\bf logical}) merely establishes that the source and target configurations have the same realization. We give here a taste of what the language is like by explaining in detail the formal code for the $[31,13,10]$ example. The following code is one way (not the shortest) or writing it in our language: \begin{verbatim} ??no [25,8,10]; type [31,13,10_2]; show x_20 != 0; config 20,11 : {10}; show x_10_0 != 0; !config 10,10,11 : {110,100}; no [31,13,10]; \end{verbatim} The first command tells the program to accept without proof the fact that there is no $[25,8,10]$ code. The proof of this (previously known) fact may also be exhibited in our language, and we do so in [.jaffe optimal binary 30.]. In a complete proof one would not have such a {\tt??no} command. The third command ({\tt type}$\ldots$) declares that our code type consists of even codes $C$ in $\F_2^{31}$ of dimension $13$, having minimum weight $\geq 10$. To conform to the description of code type given earlier, we could say the type consists of all codes in $\F_2^{31}$ of dimension $13$, satisfying the constraints $$y_1 = 0,y_2=0,\ldots,y_8=0,y_9=0,y_{11}=0,y_{13}=0,\ldots,y_{31}=0,$$% but this would be cumbersome. Given the knowledge that there is no $[25,8,10]$ code, the program automatically infers that the minimum weight of $C^\perp$ is $\geq 7$. The command ``\verb|show x_20 != 0|'' is self-explanatory. As it executes the \verb|show| command, the program automatically creates a configuration, which is then (it so happens) made the current configuration via the following \verb|config| command. Also, when the program executes the first \verb|show| command, it creates a constructive edge from the base configuration to the new configuration. The next \verb|show| and \verb|config| commands are similar. Again, the show command actually creates the configuration prior to it being made current by the \verb|config| command. Thus, after executing the second \verb|show| command, the configurations form a graph $$\begin{array}{c} \rnode{a}{\psframebox{\hbox{$\vcenter{\hbox{\kern30pt(base)}\vskip3pt% \hbox{\tt 31 : \{ \} : \{ \}}}$}}}\\[1.3cm] \rnode{b}{\psframebox{\hbox{\tt 20,11 : \{10\} : \{ \}}}}\\[1cm] \rnode{c}{\psframebox{\hbox{\tt 10,10,11 : \{110,100\} : \{ \}}}} \end{array} \arrow(a,b)\arrow(b,c)$$% where we use the format partition : small basis : dual small basis. The ``\verb|!config|'' command makes the bottom configuration current, and instructs the language to try to find a contradiction. That is, the bottom configuration is unrealizable. Following the arrows back to the base configuration, we conclude that it is unrealizable, and hence that the code type is unrealizable. As there is no {\it even\/} $[31,13,10]$ code, we conclude that there is no $[31,13,10]$ code at all, thereby justifying the final command. \block{Method: split linear programming + symmetry} Sometimes symmetry of a configuration can be employed to strengthen the split linear programming method. Let $v$ be an admissible basic local variable. Suppose we have a subgroup $G$ of the automorphism group of the configuration. Then $G$ acts on the admissible basic local variables. Use split linear programming to show that the sum over $g \in G$ of $gv$ is nonzero. Then the current configuration can be subdivided (along $v$), and a logical edge can be constructed from the current configuration to the new configuration. \block{Method: passing constraints between configurations} \def\lconfig{{\tt[}$\ell$\kern1pt{\tt]}} \def\hconfig{{\tt[}$h$\kern1pt{\tt]}} \def\lorconfigs{{\tt[}$\ell_1${\tt]}\kern5pt{\tt or}\kern5pt$\ldots$\kern5pt% {\tt or}\kern5pt{\tt[}$\ell_r${\tt]}} \def\rconfig{{\tt[}$r${\tt]}} \def\rpconfig{{\tt[}$r'$\kern1pt{\tt]}} \def\sconfig{{\tt[}$s${\tt]}} \def\spconfig{{\tt[}$s'$\kern1pt{\tt]}} \def\lconfigs{{\tt[}$\ell_1${\tt]}, $\ldots$, {\tt[}$\ell_r${\tt]}} \def\mconfig{{\tt[}$m${\tt]}} \def\miconfig{{\tt[}$m_i${\tt]}} \def\mconfigs{{\tt[}$\m_1${\tt]}, $\ldots$, {\tt[}$\m_r${\tt]}} Suppose we have a constructive edge \lconfig\ $\longrightarrow$ \mconfig\ of configurations. Let $x_J$ be a basic local variable for \lconfig, and let $x_{J_1},\ldots,x_{J_r}$ be the basic local variables of \mconfig\ which pull back to $x_J$. In an appropriate sense (which we leave to the reader to make precise), $$x_J\ =\ x_{J_1} \many+ x_{J_r}.$$% Therefore some known constraints of \mconfig\ will induce known constraints of \lconfig, and conversely. For example, if $x_{J_i} \geq c$ is a known constraint of \mconfig (for some $i$), then the constraint $x_J \geq c$ holds for \lconfig. One could have full and automatic propagation of constraints along constructive edges, but at present this feature is only partially implemented in the language. \block{Method: joint linear programming} The joint weight enumerator ${\cal J}_{C,C}$ of a code $C$ with itself gives rise to a linear programming problem because the coefficients of ${\cal J}_{C, C^{\perp}}$ are nonnegative. More information can be obtained from the fact that the coefficients of ${\cal J}_{C^{\perp}, C^{\perp}}$ are as well nonnegative, but this information comes at a great cost, as the resulting linear programming problem is much larger than that which one would get by using ${\cal J}_{C, C^{\perp}}$ alone. We define a {\it basic joint variable\/} to be a variable of the form {\tt jy}$r${\tt y}$s${\tt y}$t$, which represents $\abs{\setof{(v,w) \in C \times C: \abs{v} = r, \abs{w} = s, \abs{v+w} = t}}$. Note that $r$, $s$, and $t$ may be permuted without affecting the value on any realization. A basic joint variable is {\it minimal\/} if $r \leq s \leq t$. A basic joint variable is {\it inadmissible\/} if it is known to be zero (on any realization) for one of the following reasons: \begin{itemize} \item There is no word in the code of weight $p$, $q$, or $r$. \item We have $d \leq p < 2d$ (where $d$ is the minimum distance of the codes under consideration), and we know that an $[n-p, k-1, d-p/2]$ code cannot have a word of weight $(q+r-p)/2$. Thus the variable is inadmissible by the method of residual codes. With obvious modifications this also applies with $p$ replaced by $q$ or $r$. \end{itemize} To reduce the size of the linear programming problem this method gives rise to, one should first use split linear programming to kill as many as possible of the weights in the code. For more details, see the comments in the code for the C++ method\\ \verb|generate_joint_constraints|. \block{A canned procedure for table-building}\label{canned-section} In this section we describe an automated procedure for proving the nonexistence of $[n,k,d]$ codes. As such, the procedure has as input a triple $[n,k,d]$ and as output {\tt true} if it can show there is no $[n,k,d]$ code, else {\tt false}. The procedure is allowed to access all specific results known to the program at the time of its execution. The goodness of the procedure can be measured in two ways. On the one hand, the more often it returns {\tt true}, the better it is. On the other hand, faster is better. These two criteria compete, and we have done our best to find a compromise which runs reasonably fast and yields reasonably many results.\footnote{For experimental purposes, it makes sense to deemphasize speed. See the description of the {\tt no} command for modifications to this procedure which allow for this.} Almost any general nonexistence method can be evaluated in terms of how it could contribute to the goodness of this procedure. The less computationally intense the method, the better it can make the procedure. Thus a ``traditional theorem'' which yielded new general consequences would have great merit as a new ingredient of the procedure. The body of the procedure has three stages, but before starting it, we note that by replacing $[n,k,d]$ by $[n+1,k,d+1]$ if need be, we may reduce to the case where $d$ is even. The goal of the first stage is to simultaneously check general criteria (which would yield the nonexistence of $[n,k,d]$ codes) and to similarly derive inequalities involving the global variables. Thus the first stage is very fast; it proceeds as follows: \begin{itemize} \item If $\nexists [n,k,d]$ or $\nexists [n-1,k-1,d]$, return {\tt true}. \item We may assume that $\verb|y|_i = 0$ for $i$ odd. Also deduce $\verb|y|_i = 0$ for specific $i$ by the method of residual codes. \item If the Griesmer bound is violated, return {\tt true}. \item From known nonexistence results, deduce that $\verb|mu|_i = 0$ for $i < r$, where $r$ is as large as possible. \item If $\nexists [n,n-k,r]$, return {\tt true}. \item Use known nonexistence results in conjunction with Brouwer's results to bound the number of doubly even words in the code. \end{itemize} The goal of the second stage is to show that for various $i$, we have $\verb|y|_i = 0$, by using split linear programming applied to the configuration associated to the existence of a word of weight $i$. It is this stage which usually consumes the lion's share of the execution time: \begin{romanlist} \item If it is not known that $4 \nmid i \Longrightarrow y_i = 0$, use ordinary linear programming to try to show that $y_0 + y_4 + y_8 + \cdots > {3\over4}(2^k)$. In that case, we may by Brouwer's results delete those words whose weights are not divisible by $4$. \item Use ordinary linear programming to try to show that the system of inequalities is infeasible. If so, return {\tt true}. \item Let $i$ be the highest weight which the code might have, and which has not already been tested for. Attempt to show by split linear programming that there can be no word of weight $i$. If this succeeds, go back to step (i). If it fails, repeat this step again, but on a second consecutive failure, go on to the third stage. \end{romanlist} In the case where $k < n$, we stop now, as the third stage seems never to help. The goal of the third stage is to show that for various $i$, we have $\verb|mu|_i = 0$, by using split linear programming applied to the configuration associated to the existence of a dual word of weight $i$: \begin{romanlist} \item Let $i$ be the lowest weight which the dual code might have, which has not already been tested for. Attempt to show by split linear programming that there can be no dual word of weight $i$. If this fails, repeat with the next lowest weight. On a second consecutive failure, return {\tt false}. \item If at this point we know that there is no nonzero dual word of weight $\leq i$, check to see if we also know that there is no $[n,n-k,i+1]$ code. If so, return {\tt true}. \item Use ordinary linear programming to try to show that the system of inequalities is infeasible. If so, return {\tt true}. Otherwise, go to (i). \end{romanlist} Some technical details regarding this procedure will be given when we describe the {\tt no} command. \block{Method: finding extensions of a code}\label{extension-section} We describe how to classify extensions of a given code. First we give an example of how this comes up. We will prove $(*)$ that there is no $[29,11,10]$ code. This of course supersedes the result (described in \S\ref{split-intro-section}) that there is no $[31,13,10]$ code. Now $(*)$ works by showing that a $[29,11,10]$ code must contain a dual word $w$ of weight $5$, and thus must contain a $[24,7,10]$ subcode, disjoint from $w$. We classify the $[24,7,10]$ codes (itself a new result); there are six of them. For each of these we then show that there is no extension to a $[31,13,10]$ code, thereby proving $(*)$. Here is the main idea behind the extension classifier, which is based on ideas the author gleaned from Simonis [.simonis 1987 25_15_6.]. For the above example, we would have to first add a zero bit to make a $[25,7,10]$ code. In general, starting from an $[n-r,s]$ code $D$ (here $n = 29$, $r = 4$, $s = 7$), you look for extensions to an $[n-r+1,s+1]$ code $D_1$, thence to an $[n-r+2,s+2]$ code $D_2$, and ultimately to an $[n,s+r]$ code $D_r$, hoping (in the above example) that the process fails at some point. But there is a neat trick for doing this. Form a matrix $M$ ($n-r-s \times n-r)$ whose rows form a basis for $D^\perp$. Extending from $D$ to $D_1$ corresponds to adding a column to $M$, yielding a matrix $M_1$. Then to get to $D_2$, you add another column, yielding a matrix $M_2$. These columns lie in $V := \F_2^{n-r-s}$. Choose a total order on $V$. Let $\Lex^j(V)$ denote the set of lexicographically ordered $j$-element sequences of $V$. Call such a sequence {\it admissible\/} if the corresponding code $D_j$ is ``consistent'' with the larger code type. In the example, we can require that $D_j$ is even and has no word of weight smaller than $10$. Without loss of generality, we can also assume that the word of weight $j+1$ whose last $j+1$ bits are $1$ is in $D_j^\perp$. This corresponds to the disjointness of $D$ from $w$. Suppose you have a subgroup $G$ of $\Aut(D)$. (In practice it is sometimes convenient to let $G$ be a mere subset of $\Aut(D)$, and what follows will make sense in this setting.) There is an induced contravariant action of $G$ on $V$, as follows. For $\sigma \in \Aut(D)$, let $P$ be the associated permutation matrix ($n-r \times n-r$). Let $Q$ be the unique invertible $n-r-s \times n-r-s$ matrix such that $QMP = M$. Let $v \in V$. Then we define $\sigma(v)$ to be $Qv$. For the moment letting $|$ denote horizontal concatenation of matrices, we see that $M|v \sim MP|v \sim QMP|Qv = M|Qv$, where these matrices are equivalent in the sense that they define isomorphic codes. From the action of $G$ on $V$ we get an action of $G$ on $\Lex^j(V)$, by acting individually on the elements of a sequence, and then sorting. For $g \in G$, $M|x \sim M|gx$. Call an element $x$ of $\Lex^j(V)$ {\it $G$-minimal\/} if $gx \geq x$ for all $g \in G$. Then it is enough to find $$\Gamma_j\ :=\ \setof{G\hbox{-minimal, admissible elements of\ }\Lex^j(V)}.$$% Fortunately, if you take some $x \in \Gamma_j$, and discard its rightmost element, you get an element of $\Gamma_{j-1}$. Therefore the ``extension'' algorithm boils down to computing in succession $\Gamma_1,\Gamma_2,\ldots,\Gamma_r$. However, exactly how to compute $\Gamma_j$ from $\Gamma_{j-1}$ in an efficient way is an interesting problem open to further investigation. In the case where $\Gamma_r$ is nonempty, the user needs to provide in advance a list of configurations which the elements of $\Gamma_r$ can be tested against. Thus (for example) when we classify $[24,7,10]$ codes, we classify the extensions of one of the two $[21,5,10]$ codes by means of the command \begin{verbatim} via extension [21_5_10.a] implies [c], [d], [e0], [f]; \end{verbatim} To make full sense out of this one has to see the configurations labelled {\tt[c]}, and so forth. The method of this section is limited by the exponential growth of its execution time. In the present implementation, it takes roughly a small constant times $(2^{n-r-s})(n-r+1)(s)$ operations to find $\Lex^1(V)$. Thus for example, whereas it is practical to find extensions from $[24,7,10]$ to $[29,11,10]$, it is not practical to find extensions from $[35,4,18]$ to $[38,6,18]$, which would require almost 60,000 times the execution time of the $[24,7,10]$ case. Although one could almost certainly make the $\Lex^1(V)$ calculation much faster, it is not clear that the method can be made acceptably fast as a whole. \block{Method: finding the minimum weight of a code} In our extension algorithm, we have to repeatedly check partial extensions, with the goal of ruling out those whose minimum weight is too small. At present we do this by literally checking every element in the partial extension. This is almost certainly not optimal. Much faster probabilistic methods have been invented by Leon [.leon probabilistic algorithm.] and Stern [.stern codewords small weight.]; an analysis of these has been given by Chabaud [.chabaud asymptotic analysis.]. Since no harm will come if an occasional partial extension squeaks past this checker, such a method would probably speed up our algorithm. \newpage \part{Background and language structure} \block{The split weight enumerator of the dual code} We establish the formula for the split weight enumerator of $C^\perp$. This is just an elaboration on an exercise in [.macwilliams sloane book.]. Let $(\VEC p1r)$ be a partition of $n$. Define \mp[[ f || \F_2^n || \Z[\VEC t1r] ]] by $f(v) = \prod_{i=1}^r t_i^{\abs{v}_i}$. Let \mp[[ \lhF || \F_2^n || \Z[\VEC t1r] ]] be the Hadamard transform of $f$ ([.macwilliams sloane book.]\ pp.\ 54, 127) defined by $$\lhF(w) = \sum_{v \in \F_2^n} (-1)^{w \cdot v} f(v).$$% By (op.\ cit.\ Ch.\ 5, \S2, Lemma 2) we know that $$\sum_{w \in C^\perp} f(w)\ =\ {1 \over \abs{C}} \sum_{w \in C} \lhF(w).$$% So to prove the split weight enumerator formula, it is enough to show that $$\lhF(w) = \prod_{i=1}^r (1+t_i)^{p_i - \abs{w}_i} (1-t_i)^{\abs{w}_i}.$$% We proceed to prove this: \begin{eqnarray*} \lhF(w) & = & \sum_{v \in \F_2^n} (-1)^{w_1 v_1 \many+ w_n v_n} \prod_{i=1}^r t_i^{\abs{v}_i}\\ & = & \sum_{v \in \F_2^n} (-1)^{w_1 v_1 \many+ w_n v_n} \left( \prod_{i=1}^{p_1} t_1^{v_i} \right) \left( \prod_{i=p_1+1}^{p_1+p_2} t_2^{v_i} \right) \manycdot \left( \prod_{i=p_1 \many+ p_{r-1} +1}^n t_r^{v_i} \right)\\ & = & \sum_{v_1=0}^1 \sum_{v_2=0}^1 \cdots \sum_{v_n=0}^1 \left( \prod_{i=1}^{p_1} (-1)^{w_i v_i} t_1^{v_i} \right) \left( \prod_{i=p_1+1}^{p_1+p_2} (-1)^{w_i v_i} t_2^{v_i} \right) \manycdot \left( \prod_{i=p_1 \many+ p_{r-1} +1}^n (-1)^{w_i v_i} t_r^{v_i} \right)\\ & = & \left( \prod_{i=1}^{p_1} \sum_{u=0}^1 (-1)^{w_i u} t_1^u \right) \left( \prod_{i=p_1+1}^{p_1+p_2} \sum_{u=0}^1 (-1)^{w_i u} t_2^u \right) \manycdot \left( \prod_{i=p_1 \many+ p_{r-1} +1}^n \sum_{u=0}^1 (-1)^{w_i u} t_r^u \right)\\ & = & \left( \prod_{i=1}^{p_1} \left[ 1 + (-1)^{w_i} t_1 \right] \right) \left( \prod_{i=p_1+1}^{p_1+p_2} \left[ 1 + (-1)^{w_i} t_2 \right] \right) \manycdot \left( \prod_{i=p_1 \many+ p_{r-1} +1}^n \left[ 1 + (-1)^{w_i} t_r \right] \right)\\ & = & \prod_{i=1}^r (1+t_i)^{p_i - \abs{w}_i}(1-t_i)^{\abs{w}_i}. \kern1in \square \end{eqnarray*} \block{Exact linear programming} The split linear programming method leads to a system of linear inequalities, which we may write in the form $Ax \geq b$, where for some $r,s$ we have $A \in \Mat_{r \times s}(\Z)$ and $b \in \Z^r$; the solution set is $${\cal S}\ =\ \setof{x \in \Z^s: x \geq 0 \hbox{\ and\ } Ax \geq b}.$$% The basic problem is to prove that $\cal S$ is empty. This is because solutions have integer components, and thus to show that all solutions satisfy some inequality (e.g. $x_3 \geq 53$), we can always proceed by adjoining an additional constraint to the original system (e.g.\ $x_3 \leq 52$), and then showing that the new system has no solutions. While in practice this may not be efficient, it seems reasonable for purposes of discussion to consider only the case of showing ${\cal S} = \emptyset$. Beyond aiding in this simplification, the constraint that solutions have integer coefficients is not as useful as it might look: the analysis of integer solutions ({\it integer linear programming}) is computationally much more complex than the analysis of rational solutions. The simplex algorithm can in principle be used to directly show that a system has no solutions. But to actually get a proof from the algorithm, one would have to do exact arithmetic, rather than floating point calculation. As such, we do not know of an implementation which is acceptably fast. Indeed, we doubt it is possible, and offer the following heuristic argument as an explanation. Consider a random $n \times n$ matrix $M$ whose entries are $d$-digit (or less) integers, i.e.\ whose entries are chosen uniformly from $[-(10^d - 1), 10^d - 1]$. One would expect $\det(M)$ to have about $nd$ digits. Similarly, if one tries to compute $M^{-1}$ or an $LU$ decomposition of $M$, one would expect the average number of digits% \footnote{Define the {\it number of digits\/} in a rational number $a/b$ to be the maximum of the number of digits in $a$ and $b$, supposing of course that $\gcd(a,b) = 1$. Generally, we use base $10$ just for illustration.} in the entries of these matrices to have a comparable growth rate. Now fixing the number of digits, one should expect (for example) that computing the ``floating-point inverse'' of an $n \times n$ integer matrix will require $O(n^3)$ operations, but computing its exact inverse will require $O(n^4)$ operations; the extra $n$ comes from the $n$ in $nd$. But it may be difficult to make such statements precise, since (e.g.) $O(n^3)$ is not optimal for matrix inversion. The remarks of this paragraph are obviously provisional. A lemma of Farkas [.farkas 1902.] (see e.g.{\ }[.schrijver.] Corollary 7.1f) asserts that $${\cal S}_\Q\ :=\ \setof{x \in \Q^s: x \geq 0 \hbox{\ and\ } Ax \geq b}.$$% is empty \IFF\ there exists a $y \geq 0$ such that $A^T y \geq 0$ and $y \cdot b < 0$. Otherwise said, if the system is inconsistent, then one can find a nonnegative linear combination of the constraints which is in and of itself contradictory. (This may also be viewed as a consequence of duality.) Moreover, the simplex algorithm produces such a $y$. If an algorithm (via floating point calculations) can produce a $y$ as above, then we can form the corresponding {\it exact\/} linear combination of constraints and try to show (independently) that it gives rise to a contradiction. This turns out to work very nicely in practice. Here then is our approach. Given the original system (with integer coefficients), find a floating point $y$ which numerically appears to satisfy $A^T y \geq 0$ and $y \cdot b < 0$. Let $\loY$ be the best rational approximation to $y$. If $\VEC c1r$ are the original constraints, then we get a new constraint $\loY_1 c_1 \many+ \loY_r c_r$, which although perhaps not inherently contradictory, can be used to deduce a contradiction. Indeed the negative coefficients of variables (if any) on the \LHS\ will be small (close to $0$), and we have a priori upper bounds on the variables, so (barring misfortune) we will be able to prove that the original system is infeasible. The worst that can happen is that we will be forced to report that the calculation is inconclusive. Note too that the proof step is simple and moreover thoroughly insulated from the intricacies of linear programming calculation. The current implementation of the program contains both a provisional implementation of the simplex algorithm, and the ability as well to use a commercial solver, CPLEX, which is both faster and more robust. The included implementation however has the advantage of being able to use higher precision floating point arithmetic, which becomes critical when investigating codes of length about $70$ or greater. Aside from being slow, the included implementation has the disadvantage that it handles ``numerical anomalies'' poorly, and thus (depending on the state of an internal random number generator) will sometimes (but very infrequently) stop in the middle of a simplex calculation, and issue an error message indicating that the calculation has failed. For further information, we refer to a small subset the vast literature on linear programming: [.chvatal.], [.goldfarb todd.], [.gregory faq.], [.karloff linear programming.], [.more wright.], and [.murtagh advanced.] \block{Variables and constraints}\label{variable-section} There are three kinds of variables in the language: {\it local}, {\it global}, and {\it joint}. The first two have already been discussed in \S\ref{definitions-section}. In the language, a {\bf variable} will always mean a specific, predefined variable, global, local, or joint, and these are exhibited below. In discussing these, we refer to a code $C$, which is to be a code in the realization of the particular configuration one is working with. The basic global variables are \begin{center} {\tt y0},\ {\tt y1},\ $\ldots$,\ {\tt y}$n$ \end{center} where $n$ is the length of $C$; {\tt y}$i$ gives the number of words of weight $i$ in $C$. Other global variables are \begin{center} {\tt mu0},\ {\tt mu1},\ $\ldots$,\ {\tt mu}\kern1pt$n$ \end{center} which give the number of words of given weight in $C^\perp$. The last global variables are \begin{center} {\tt div2},\ {\tt div4},\ {\tt div8},\ $\ldots$, \end{center} which give the number of words in $C$ whose weight is divisible by the given power of $2$. Now we come to {\it local\/} variables. For a given configuration, the basic local variables have the form \begin{center} \verb|x_|$a_1$\verb|_|$\ldots$\verb|_|$a_r,$ \end{center} where $r$ is the number of parts in the partition of the configuration. Such a basic local variable must be {\it admissible}. If $\VEC a1r$ are all single digits, such a basic local variable may also be written as \begin{center} \verb|x|\kern1pt$a_1a_2 \ldots a_r$. \end{center} In addition to this formatting choice, each basic local variable has a number of equivalent forms, since the smallcode acts on wordtypes. For internal purposes, we select a canonical form for each basic local variable, which we call {\bf minimal}. Of course we could take minimal to mean lexicographically minimal, but this turns out to be computationally inconvenient. The actual definition is somewhat technical and of limited significance. \label{minimal-promise}We defer the details to \S\ref{partition-wordtype-mawhome-section}. Again for internal purposes, the minimal form is further translated to {\tt v}$i$, for some $i$, so that the basic local variables are (up to equivalence) \begin{center} {\tt v1}, {\tt v2}, $\ldots$, {\tt v}$t$. \end{center} To discourage reliance on the internal ordering scheme used for these variables, their use in the language is not permitted. By convention, {\tt v1} is the trivial basic local variable. See also the discussion of {\it basic joint variables}, below. There are various local variables which are derived from the basic local variables. The variable \begin{center} \verb|z_|$a_1$\verb|_|$\ldots$\verb|_|$a_r$ \end{center} denotes the number of words of multiweight $(\VEC a1r)$ in $C^\perp$. As with basic local variables, there is an abbreviated form without underscores. Now for each $i$ ($1 \leq i \leq r$), let $a_i$ be either an integer (between $0$ and $p_i$) or else the character {\tt z}. Then \begin{center} \verb|q_|$a_1$\verb|_|$\ldots$\verb|_|$a_r$ \end{center} is a local variable. To see what it represents, consider the subcode $D$ of $C$ consisting of words having zeroes in at least the positions marked by {\tt z} in the variable. (We regard $D$ as a code of length shorter than $C$ -- it is supported on the non-{\tt z} positions.) Let $I = (\VEC a1r)|_{\hbox{\small\tt z} \mapsto 0}$: each {\tt z} is replaced by a $0$. Then \verb|q_|$a_1$\verb|_|$\ldots$\verb|_|$a_r$ represents $\abs{D} \cdot \abs{\setofh{$I$-words in $D^\perp$}}$. Such variables arise during the processing of {\tt incorporate} commands. There is also an abbreviated form without underscores. Note that if $\VEC a1r$ are all integers, then \verb|q_|$a_1$\verb|_|$\ldots$\verb|_|$a_r$ = $\abs{C} \cdot$ \verb|z_|$a_1$\verb|_|$\ldots$\verb|_|$a_r$ in any realization. This introduces an apparent redundancy, which is needed because (in general) we do not know the value of $\abs{D}$, and we want every variable to take on only integer values. Relative to the current configuration, if $w$ is a small word (represented by a string of {\tt0}'s and {\tt1}'s), then \begin{center} {\tt sub}$w$ \hbox{\ \ and\ \ } {\tt sub}$w$\verb|_|$k$ \end{center} denote respectively the number of words in the subcode of $C$ supported on $w$, and the number of words of weight $k$ in that subcode. For a configuration whose partition has only one part, the basic local variable \verb|x_|$i$ will have the same evaluation as the basic global variable \verb|y|$i$. While this does not mean that \verb|x_|$i$ and \verb|y|$i$ may be used interchangeably, we have tried to minimize the number of places where the use of one variable as opposed to the other will make a difference. We have already defined basic joint variables. The minimal admissible basic joint variables are represented internally as as {\tt v1}, {\tt v2}, and so forth. Another joint variable is {\tt jy}$r${\tt d}$s${\tt i}$t$, which represents $$\abs{\setof{(v,w) \in C \times C^\perp: \abs{v} = r, \abs{w} = s, \abs{v \cap w} = t}}.$$% We also allow {\tt jy}$r${\tt d}$s$, which equals {\tt jy}$r${\tt d}$s${\tt i}$0$. The variable {\tt co}$r$ is defined to be equal to {\tt jy}$r${\tt d}$r${\tt i}$r$, and the variable {\tt co} is defined to be equal to $\sum_{j=0}^n \verb|co|j$, so $\verb|co| = \abs{C \cap C^\perp}$. The joint variable {\tt jd}$r${\tt d}$s${\tt d}$t$ represents $\abs{\setof{(v,w) \in C^\perp \times C^\perp: \abs{v} = r, \abs{w} = s, \abs{v + w} = t}}$. The joint variable {\tt jdiv2} represents $\abs{\setofh{$(v,w) \in C^2$: $v$, $w$, and $v \cap w$ all have even weight}}$. For purposes of data entry, a {\bf constraint} is a linear inequality or equality involving any of the above variables, with $\Z$-coefficients. Examples of the allowed forms are: \vspace{0.1in} \leavevmode\kern0.5in\begin{tabular}{ll} \verb|4y3 + 6x_2_5 >= 9| \\ \verb|-8y3 + y10 - 2y4 <= 40| \\ \verb|y32 = 1| \\ \verb|5y10 < 100| & (equivalent to \verb|5y10 <= 99|) \\ \verb|5y10 > 100| & (equivalent to \verb|5y10 >= 101|) \\ \verb|y6 != 0| & (equivalent to \verb|y6 >= 1|; \\ & \LHS\ must be a variable). \end{tabular} \vspace{0.1in} Note that the \RHS\ is always an integer, and you can't put an integer on the \LHS, unless it is used as a coefficient of a variable. We call a constraint {\bf simple} if its \LHS\ is a variable. Local and joint variables may not appear in the same constraint. Constraints are stored as is, and not converted to constraints involving only basic global and local variables, as would appear to be the case from the definitions in \S\ref{definitions-section}. Moreover, the order in which the terms are entered matters. Thus if {\tt y10 + y12 <= 20} is known, it does not follow that {\tt y12 + y10 <= 20} is known. This is a dorky ``feature'', but is unlikely to cause problems. A {\bf constraint list} is a list of zero or more constraints, separated by commas. However, certain compound forms are allowed, as in \par\noindent\kern0.5in\verb|5 <= y10 + y12 <= 20|; \par\noindent one or both of the inequalities may be replaced by strict inequalities, with the expected effect. \block{Language structure}\label{proof-command-section} Statements in the language could be divided into two general classes: {\bf proof} statements and {\bf exploratory} statements; in a finished proof one should have only proof statements. There are three main functions of proof statements: (1) establish a logical statement between configurations; (2) establish that a given configuration must satisfy a particular constraint; (3) establish that a given permutation is an automorphism of a given configuration. In addition the language permits the definition of constructive connections between configurations, as discussed in \S\ref{split-intro-section}. Before considering the commands themselves, we describe more carefully the data kept by the program. The abstract notion of {\it code type} is realized by the class {\tt codehome} and the abstract notion of {\it configuration} is realized by the class {\tt config}. Part of the {\tt codehome} definition is an {\bf assumed weight list}, a list of nonnegative integers which the weight sets of the codes are supposed to form subsets of. This would be formally equivalent to including assumed constraints of the form $y_i = 0$, but it is more efficient and convenient to keep track of weights instead. However, for the remainder of this report, if we say that a codehome has ``no assumed constraints'', we do not by this imply anything about its assumed weight list. Similarly, for each configuration, there is a {\bf working weight list}, which is a possibly smaller list of weights, such that each code realizing the configuration has weights in the smaller list. The {\tt codehome} definition also includes a directed multigraph as discussed on p.\ \pageref{first-multigraph-occurrence}; the graph structure is realized by a {\tt ShareGraph} object. Path components in this graph are realizability equivalence classes. To facilitate sharing, each path component has associated to it a \verb|config_share| object, which carries various pieces of information known about the configurations. For example, each \verb|config_share| object has a \verb|realizable| flag which indicates if the configurations are known to be realizable or unrealizable. Logical edges in the digraph are not explicitly recorded as data items. Rather, if we wish to ``add a logical edge'' from one configuration to another, we merge their \verb|config_share| objects. Constructive edges are labelled by the corresponding basic local variable (which is known to be nonzero); going from head to tail of the edge corresponds to subdivision. Labels may be associated by the user to code types, configurations, automorphisms, and {\tt incorporate} commands, to be described later. The latter command also creates new labels. When created by the user, a label is allowed to be any non-null sequence of letters, digits, and underscores, enclosed in square brackets. It is also permissible to use a configuration label of the form {\tt[}$a${\tt:}$b${\tt]}, where {\tt[}$a${\tt]} is the name of a code type (of the same length as the current code type) and {\tt[}$b${\tt]} is the name of a configuration of {\tt[}$a${\tt]}. The first time this is used, configuration {\tt[}$b${\tt]} is copied to the current code type. (Known facts cannot be copied.) In usage thereafter, the configuration {\tt[}$a${\tt:}$b${\tt]}, will be treated just like any other configuration of the current code type. A {\it\bf configuration-list} is a comma-separated sequence of zero or more configuration labels, except that amongst these, some configuration labels may be replaced by certain compound constructions, which we illustrate by examples: \begin{itemize} \item \verb|[xy*]| expands to all user-defined configuration labels which start with {\tt xy}. \item \verb|[21{r,s,tt}]| expands to \verb|[21r]|, \verb|[21s]|, \verb|[21tt]|. \item \verb|[21_8.{x*,y*,z}]| expands to \verb|[21_8.z]| and all user-defined configuration labels which start with either \verb|[21_8.x| or \verb|[21_8.y|. \item \verb|a2..15| expands to \verb|[a2]|, \verb|[a3]|, \ldots, \verb|[a15]|. \end{itemize} The {\tt*} construction never matches {\tt[base]} or {\tt[current]}, nor does the {\tt*} part ever match a string containing ``{\tt!}''. In the description of commands that follows, $n$ will always denote the dimension of the ambient space (i.e.\ the length of the codes under consideration), and $k$ will denote the dimension of the codes. All commands are terminated by a semicolon. White space is always irrelevant. Any command preceeded by ``??'' will be accepted without verification, as if a ``{\tt set gullible}'' command had been used. Any block of commands may bracketed as in the following example: \begin{verbatim} ... config 8,10,4,5 : {1100,1010} :: {y12 >= 31, y13 = 0, y14 >= 1}; { show div4 >= 44; ... show x1524 = 0, x2415 = 0, x2433 = 0, x2514 = 0, x2525 = 0, x3324 = 0, x3405 = 0, x3423 = 0, x3425 = 0, x3434 = 0, x3443 = 0, x3504 = 0 }; config from x4422; via building [current] implies ; ... \end{verbatim} The bracketed code is treated in the following way. In gullible mode, it is completely ignored. Otherwise, the code is executed as usual. In this way, code which executes slowly in gullible mode can be completely skipped over. Any command may be postfixed (before the semicolon) with ``{\tt<}{\it parameters}{\tt>}'', where {\it parameters\/} is a comma-separated list of parameters as in (for example) \begin{verbatim} no [43,20,12]; \end{verbatim} The given parameters are set prior to execution of the command and then restored to their original value at the end. See the {\tt set} command for the list of allowed parameters; one may not use {\tt gullible}, {\tt gullible commands}, or {\tt test mask} in this way. Do not use this option with a command which is expanded into a list of other commands, such as {\tt n =}. \def\config#1{{\tt[}$#1${\tt]}} \def\cconfig{{\tt[}$c${\tt]}} \def\mconfig{{\tt[}$m${\tt]}} \def\czconfig{{\tt[}$c_0${\tt]}} \def\coconfig{{\tt[}$c_1${\tt]}} \def\ctconfig{{\tt[}$c_2${\tt]}} \def\ciconfig{{\tt[}$c_i${\tt]}} \block{How to define a code type} A code type is defined with the {\tt type} command, as follows: \newenvironment{commanddeclaration}% {\vspace{0.1in}\begin{center}\begin{Sbox}\kern2pt}% {\end{Sbox}\psshadowbox{\TheSbox}\end{center}\vspace{0.1in}} \def\superopt#1{$\displaystyle{\overbrace{#1}^{\hbox{optional}}}$} \def\subopt#1{$\displaystyle{\underbrace{#1}_{\hbox{optional}}}$} \indexb{type} \begin{commanddeclaration} \subopt{\hbox{\lconfig}} {\tt type[}\kern2pt{\it length}{\tt, }{\it dimension}{\tt, }{\it weights}% \superopt{{\tt, }{\it dual weights}}\kern2pt{\tt]} \subopt{{\tt\{}\kern5pt{\it constraint list}\kern5pt{\tt\}}} \superopt{{\tt/}\kern5pt{\it options}\kern5pt{\tt/}}{\tt;} \end{commanddeclaration} Here {\it length\/} is the length of the code, i.e.\ $n$ if the code lives in $\F_2^n$; the {\it dimension\/} is the dimension $k$ of the code; {\it weights\/} represents a list $w$ of weights, and has several allowed formats: \vspace{0.05in} \begin{tabular}{lll} \verb|{|$w_1$\verb|,|$\ldots$\verb|,|$w_m$\verb|}|& -- & all weights in the given set, which should be in increasing order\\ & & (also $0$, which should not be listed)\\ $d$ & -- & $0$ and all weights $\geq d$\\ $d$\verb|_|$r$ & -- & $0$ and all weights $\geq d$ which are divisible by $r$\\ $d$ \verb| - {|$w_1$\verb|,|$\ldots$\verb|,|$w_m$\verb|}|& -- & $0$ and all weights $\geq d$, except $\VEC w1m$\\ $d$\verb|_|$r$ \verb| - {|$w_1$\verb|,|$\ldots$\verb|,|$w_m$\verb|}|& -- & $0$ and all weights $\geq d$ which are divisible by $r$,\\ & & except $\VEC w1m$ \end{tabular} \vspace{0.05in} Dual weights has the same format, defaulting to all weights. It is permissable to use ellipsis in the above situations, for example \begin{center} ``\verb|66_2 - {98,114,118..138}|'' \end{center} denotes all even weights $\geq 66$, except $98$, $114$, and those numbers lying between $118$ and $138$. \vspace{0.05in} As an example of a {\tt type} command, ``\verb|type [29,11,6_2]|'' would cause the program to think about even codes of dimension $11$ in $\F_2^{26}$, having minimum weight $\geq 6$. The program will automatically use the method of residual codes to infer that certain weights cannot occur. Let $d$ be the minimum weight in the weightlist. Suppose that $i$ satisfies $d \leq i < 2d$. Suppose that we know there is no code of type $[n-i,k-1,d - \floor{i/2}]$. Then weight $i$ does not occur. If the code is at the Griesmer bound, and its minimum weight is even, all its words have even weight ([.tilborg griesmer 1980.] 1.11). This is automatically known to the program. In the case of an even code, we automatically include lower and upper bounds on the number of words whose weights are divisible by $4$, in accordance with the results of Brouwer [.brouwer linear programming bound.]. If for a given $d'$, it is known that there is no $[n-(d'-1),k-(d'-1)+1,w]$ code, then it is automatically inferred that the minimum weight of the dual code is at least $d'$. The optional {\it constraint list\/} is a list of constraints, which all codes $C$ in the type are to satisfy. The optional argument \lconfig\ if present assigns the label \lconfig\ to the code type for future reference. The same label may not be used for two code types. The {\it options} field is a comma-separated list of fields. At this point there are five allowed fields, each of which may appear only once. The first field is: \par\noindent\kern0.5in\verb|dual_may_be_code_of_design(t = 2, k = |$\kappa$% \verb|, lambda = |$\lambda$\verb|)|. \par\noindent The effect of this option is to check that $C^\perp$ satisfies certain conditions which are necessary (but not sufficient) for it to be generated by a $t$-design $D$ with the given parameters. (We use $\kappa$ to avoid conflict with our convention that $k$ is the dimension of the code.) To explain these conditions, let $S(2)$ denote the set of all $2$-words in $\F_2^n$, and let $T(\kappa)$ denote the set of all $\kappa$-words in $C^\perp$. If $\lambda > 1$, we check only that every element of $S(2)$ is contained in at least $\lambda$ elements of $T(\kappa)$. In the case where $\lambda = 1$, we check the following more elaborate condition\label{elaborate-design-condition}: \vspace{0.1in} \par\noindent $A := S(2)$;\\ $B := T(\kappa)$;\\ $E := \emptyset$;\\ \begin{tabular}{ll} \kern-6pt repeat \{\ \ \ \ & (At this point every $a \in A$ lies in some element of $D \cap B$.)\\ & if $(\kern4pt \exists\kern1pt a \in A \hbox{\ not contained in any\ } b \in B\kern4pt )$ return false;\\ & $U := \setof{a \in A: \exists! \kern4pt b \in B \hbox{\ containing\ } a}$;\\ & if $( \kern4pt U = \emptyset \kern4pt )$ return (($\abs{E} \not= {n \choose 2}/{\kappa \choose 2}$) or ($E$ generates $C^\perp$));\\ & $F := \setof{b \in B \hbox{\ which contains an element\ } u \in U}$;\\ & (Note that $F \IN D$.)\\ & $E := E \cup F$;\\ & if $(\kern4pt \exists f_1, f_2 \in F \hbox{\ such that\ } \abs{f_1 \cap f_2} \geq 2\kern4pt )$ return false;\\ & $A_0 := \setof{a \in A: a \hbox{\ is contained in some\ } f \in F}$;\\ & $A := A - A_0$;\\ & $B := \setof{b \in B: b \hbox{\ contains no element of\ } A_0}$; \kern0.9cm\} \end{tabular} \vspace{0.1in} \par\noindent The second condition is \par\noindent\kern0.5in\verb|partition_of_word_by_dual_words(weight = |$w$% \verb|, dual_weight = |$d$\verb|)|. \par\noindent For this condition to be satisfied, every word of weight $w$ in $C$ must admit a nonoverlapping cover by words of weight $d$ in $C^\perp$. If both conditions (\verb|partition_of_word_by_dual_words|, \verb|dual_may_be_code_of_design|) are employed, $\lambda = 1$, and $d = \kappa$, the meaning of the two conditions is modified and the above tests are combined and strengthened, as follows. First, the change in meaning is that now we require that there exists a $t$-design $D$ with the given parameters, generating $C^\perp$, such that moreover every word of weight $w$ in $C$ admits a nonoverlapping cover by elements of $D$. As for the change in tests, make the following definition. A {\it covering plan\/} is a choice, for each word of weight $w$ in $C$, of a nonoverlapping cover by words of weight $\kappa$ in $C^\perp$, in such a way that no two words in the covering plan meet at more than one position. We cycle through all covering plans $\cal D$, and for each, we execute the condition outlined above, except that the initial choices for $A$, $B$, and $E$ are modified as follows: \begin{itemize} \item $A = \setof{w \in S(2):\ w \hbox{\ is not contained in any\ } d \in \cal D}$; \item $B = \setofh{words in $T(\kappa)$ not meeting any $d \in {\cal D}$ along more than one bit}$; \item $E = \cal D$. \end{itemize} In the above, we have used ${\cal D}$ to denote the set of all dual words appearing in the given covering plan. The third field is \par\noindent\kern0.5in\verb|doubly_even_part_is_subcode|. \par\noindent This condition says that the set $D$ of words in the code whose weight is divisible by four must constitute a subcode of $C$. This is equivalent to saying that $D \IN C^\perp$. The fourth field is \par\noindent\kern0.5in\verb|dual covering radius <= |$r$, \par\noindent where $r$ is a positive integer. This condition says that the covering radius of the dual code must not exceed $r$. The fifth field is \par\noindent\kern0.5in\verb|maybe subcode of |\lconfig, \par\noindent where \lconfig\ is a code type which has been defined already. The effect of this is to draw certain conclusions which would be known for subcodes of codes realizing type \lconfig. (Here {\it subcode\/} allows both for smaller dimension and shorter length.) Specifically, any constraints from \lconfig\ which set a basic local variable or basic global variable to zero are copied (and treated as assumed constraints) for the current type. If \verb|dual covering radius <= |$r$ was chosen for \lconfig, appropriate deductions are made for the current type. The possibility of drawing other conclusions is left open for future versions of the program. \vspace{0.1in} If at some point it is found that the code type is unrealizable, the language interpreter will discard all information about the code type except this fact. After a {\tt type} command is entered, that type remains in effect until the next {\tt type} command (or some other command which changes the type, such as ``{\tt no}''). See also the ``{\tt at}'' command. \block{Expressions}\label{matrix-descriptor-section} In this section, we define an {\it expression}. This is a string which can be evaluated to yield a mathematical object, subject to certain rules we shall give. All of this is in flux! Warning! See the directory {\tt functions} for more information about operators on expressions. The documentation to be found there will ultimately appear in this document. The following table presents the currently extant object types, along with the internal types which represent them: \def\dtext#1#2{\vbox{\hbox{\tt #1}\kern3pt\hbox{\tt #2}}} \def\dtextp#1#2{\vbox{\kern5pt\hbox{\tt #1}\kern3pt\hbox{\tt #2}}} \def\ttext#1#2#3{\vbox{\hbox{\tt #1}\kern3pt\hbox{\tt #2}\kern3pt\hbox{\tt #3}}} \def\ttextp#1#2#3{\vbox{\kern5pt\hbox{\tt #1}\kern3pt\hbox{\tt #2}\kern3pt% \hbox{\tt #3}}} \def\ftext#1#2#3#4{\vbox{\hbox{\tt #1}\kern3pt\hbox{\tt #2}\kern3pt% \hbox{\tt #3}\kern3pt\hbox{\tt #4}}} \begin{center} \begin{tabular}{|l|l|}\hline {\bf name} & {\bf meaning}\\ \hline\hline {\tt F2} & an element of $\F_2$\\ \hline {\tt MatF2} & a matrix over $\F_2$\\ \hline {\tt PVSF2} & \ttext{a partitioned vector space over $\F_2$,}% {represented by a list of lists of elements of $\F_2^n$,}% {which define a partition of it}\\ \hline {\tt Group} &\dtext{a finite group, given by generators}% {and transformation rules}\\ \hline {\tt Int} & an integer\\ \hline {\tt MatInt} & a matrix of integers\\ \hline {\tt Rat} & a rational\\ \hline {\tt MatRat} & a matrix of rationals\\ \hline {\tt Bool} & {\tt true} or {\tt false}\\ \hline {\tt LinearProgram} & a system of inequalities with integer coefficients\\ \hline {\tt String} & a string\\ \hline \end{tabular} \end{center} In addition, if $\alpha$ is an object type, $\verb|List(|\alpha\verb|)|$ denotes an ordered list (i.e.\ vector) of objects of type $\alpha$. There are as well attributes assigned to some types: for {\tt MatF2} there are potential attributes {\tt reduced} (meaning in \RREF, and having no zero rows) and {\tt invertible}. A {\tt List} of {\tt MatF2}'s has the potential attribute {\tt homogeneous}, meaning that the list is nonempty and all the matrices have the same size. The way that attributes may be indicated is illustrated by the following examples, both of which are so frequently used that we give an abbreviation: \vspace{0.1in} \par\noindent abbreviation: {\tt MatrixGroup(F2)} \par\noindent type name: \verb|List(MatF2{invertible}){homogeneous}| \par\noindent what it is: A nonempty list of invertible matrices (over $\F_2$) having the same size. \vspace{0.1in} \par\noindent abbreviation: {\tt HList(MatF2)} \par\noindent type name: \verb|List(MatF2){homogeneous}| \par\noindent what it is: A nonempty list of matrices (over $\F_2$) having the same size. \vspace{0.1in} There are a number of binary operators, and as a rule, there is no guarantee how ambiguous expressions (like $\alpha \kern5pt {\tt\#} \kern5pt \beta \kern5pt {\tt\-} \kern5pt \gamma$) are handled. Use parentheses. There is one exception: the \verb=|= operator has lowest precedence. Otherwise, evaluation tends to be from left to right. By {\it reducing\/} a matrix, we mean that it is converted to \RREF\ and moreover that its zero rows are removed. Some of the operators appear to return a finite graph. In such cases what we really mean is that a matrix having only weight two columns (one for each edge in the graph) is returned. We make the convention that when we refer to a column number of a matrix with $n$ columns, the number will be between $1$ and $n$. (And not between $0$ and $n-1$.) \vspace{0.1in} \par\noindent{\Large\bf Expression list \circno1} \vspace{0.1in} The following expressions are functions of one or more variables, but the arguments are not themselves objects. All the functions in this list yield as output an object of type {\tt MatF2}. \begin{itemize} \item $\verb|Choose|(n,\setof{\VEC k1r})$, representing the horizontal concatenation of $$\verb|Choose|(n, k_1), \verb|Choose|(n, k_2), \ldots, \verb|Choose|(n, k_r).$$ \item $\verb|AntiCode(|k,\vec T1r\verb|)|$, where $T_i \IN {\cal P}(\setof{1,\ldots,k})$ for all $i$. This represents the horizontal concatenation of certain matrices, one for each $i$. For a given $i$, first form the matrix which has all nonzero columns of length $k$, with entries in $\F_2$. Then for each $T_{ij}$ in $T_i$, delete those columns which lie in $\SPAN\setof{e_\ell : \ell \in T_{ij}}$. The codes having generator matrices of this type are modelled after the codes of Solomon and Stiffler [.solomon stiffler.]. \item $\verb|BCH(|r\verb|, |n\verb|, |${\it first}\verb|..|{\it last}% \verb|)|, representing the matrix of the BCH code of length $n$ over $\F_2$, associated to the powers $\hbox{\it first},\ldots,\hbox{\it last}$ of a primitive element in $\F_{2^r}$. \item $\verb|Coset(2^|m\verb|, |r\verb|, n = |n\verb|)|$, representing the matrix associated to the cyclic code of length $n$ associated to the union of $\setof{0}$ and the cyclotomic coset mod $2^m - 1$ generated by $r$. \item $\verb|Col(|i_1\verb|,|\ldots\verb|,|i_r\verb|)|$, representing a column vector having nonzero entries in positions $\VEC i1r$, where $1$ represents the top position. Here $\VEC i1r$ should be distinct, positive integers. The length of the column vector will equal $\max\setof{\VEC i1r}$. \item $\verb|MulMod(|f\verb|,|g\verb|)|$, representing the matrix of multiplication by $g$, in the ring $\F_2[t]/(f)$, relative to the standard basis $t^0, t^1, \ldots, t^{d-1}$, where $d$ is the degree of $f$. \end{itemize} \par\noindent{\Large\bf Expression list \circno2} \vspace{0.1in} The following expressions are irregular. They do not have objects as arguments. Except as noted, they yield as output an object of type {\tt MatF2}. \begin{itemize} \item \verb|{|$\VEC r1k$\verb|}|, where $\VEC r1k$ are zero-one vectors (e.g.\ $010001110$) which comprise the rows of the matrix to be defined. \item a nonnegative integer, yielding an {\tt Int} (note unresolved ambiguity with the previous item) \item {\tt[}$c.m${\tt]}, where \cconfig\ is a code type and \mconfig\ is a configuration for \cconfig\ having the same dimension as it. The associated matrix is the reduced generator matrix for the basic code associated to \mconfig. Some facility for lists of configurations is implemented in a similar way to the definition of configuration-list. Output type: {\tt HList(MatF2)}. \item {\tt[}$c.m${\tt-}$r${\tt]}, shorthand for {\tt[}$c.m${\tt] - column}\kern5pt$r$. \item $p$, a permutation, which represents the corresponding permutation matrix. The permutation $p$ is to be given as a product of cycles, e.g.\ as ``\verb|(1,4,5)(2,3)(6,8,7)|''. The size of the matrix is $r \times r$, where $r$ is the largest integer appearing in $p$. To avoid notational ambiguities, a permutation must be presented as the product of at least two cycles. \end{itemize} \par\noindent{\Large\bf Expression list \circno4} \vspace{0.1in} All the expressions in this list are binary operators, whose operands (labelled here $M$ and $N$) have type {\tt MatF2} and whose output has type {\tt MatF2}. \begin{itemize} \item {\bf[sharp]} $M \verb|#| N$ is defined in the following way. First let $A$ be the horizontal concatenation of $N\verb|.ncols|$ copies of $M$. Then let $B$ be obtained from $N$ by replicating each column $M\verb|.ncols|$ times. Finally $M \verb|#| N$ is the vertical concatenation of $A$ and $B$. \item {\bf[horizontal concatenation]} $M \verb=|= N$ is the horizontal concatenation of $M$ and $N$. If necessary, zero rows are first added to be bottom of $M$ (or $N$) to equalize the number of rows. \item {\bf[column complement]} Assume that $M$ and $N$ have the same number of rows. Then $M \verb|-| N$ is obtained from $M$ by deleting every column which appears in $N$. \end{itemize} \par\noindent{\Large\bf Expression list \circno5} \vspace{0.1in} All the expressions in this list are special binary operators. The left operand is an object of type {\tt MatF2} (which we label here $M$). The right operand does not have any objects in it. The output type is {\tt MatF2}. \begin{itemize} \item {\bf[parity check]} Let $C$ be the rowspace of $M$. Assume that $C$ has a word of odd weight. Then $M\verb| + check|$ is obtained from $M$ by adjoining a parity check as the last column. \item {\bf[column duplication]} Let $r$ be an integer between $1$ and $M\verb|.ncols|$. Then $M\verb| + column |r$ is obtained from $M$ by duplicating column $r$. \item {\bf[column deletion]} Let $r$ be an integer between $1$ and $M\verb|.ncols|$. Then $M\verb| - column |r$ is obtained from $M$ by deleting column $r$. Similarly, if $\VEC r1s \in \setof{1,\ldots,n}$, then $M\verb| - columns {|r_1\verb|,|\ldots\verb|,|r_s\verb|}|$ is obtained from $M$ by deleting columns $\VEC r1s$. It is also permissable to use {\tt..} to abbreviate a consecutive sequence, as in \verb|{1..4,9..12}|, which is equivalent to \verb|{1,2,3,4,9,12}|. \item {\bf[subcode disjoint from a bit]} Let $r$ be an integer between $1$ and $M\verb|.ncols|$. Then $M\verb| ~ column |r$ is obtained from $M$ by forming the reduced matrix spanning the subspace of the rowspace which is zero along column $r$; this column is deleted. \end{itemize} \par\noindent{\Large\bf Expression list \circno6} \vspace{0.1in} All the expressions in this list are special binary operators. The left operand is an object of type {\tt MatF2} (which we label here $M$). The right operand does not have any objects in it. The output type is {\tt HList(MatF2)}. \begin{itemize} \item {\bf[dual word deletion]} Let $r$ be an integer between $1$ and $M\verb|.ncols|$. Then \begin{center} $M\verb| - dual word of weight |r$ \end{center} represents the list of isomorphism classes of matrices obtainable from $M$ by deleting the columns corresponding to a word of weight $r$ dual to the rowspace of $M$, and then reducing. You can also do this with $M$ of type {\tt List(MatF2)}. \item {\bf[subcode disjoint from a dual word]} Let $r$ be an integer between $1$ and $M\verb|.ncols|$. Then $M\verb| ~ dual word of weight |r$ is obtained from $M$ by forming the reduced matrix spanning the subspace of the rowspace which is disjoint from a dual word $w$ of weight $r$; the corresponding columns are deleted. As $w$ varies, one obtains a list of matrices; a sublist of isomorphism class representatives is returned. You can also do this with $M$ of type {\tt List(MatF2)}. \item {\bf[dual word addition]} First reduce $M$. Let $r \in \setof{3,4}$. Then \begin{center} $M\verb| + dual word of weight |r$ \end{center} represents the list of isomorphism classes of matrices $M^+$ obtainable from $M$ by adding $r$ columns to it (and reducing), in such a way that the new codes $D := \Rowspace(M^+)$ have minimum distance two greater than $\Rowspace(M)$, and such that the weight $r$ word corresponding to the $r$ columns lies in $D^\perp$. You can also do this with $M$ of type {\tt List(MatF2)}. \end{itemize} \par\noindent{\Large\bf Expression list \circno7} \begin{itemize} \item{\bf[LinearProgram]} Let $f$ be of type \verb|String|, naming a file which contains a linear program, with integer coefficients. Then $\verb|LinearProgram($f\verb|)|$ is an internal representation of that linear program. \item{\bf[Bound]} Let $P$ be a {\tt LinearProgram}. Let $v$ be a variable which appears in $P$. Then $\verb|Bound(|P\verb|,|v\verb|)|$ returns {\it unverified\/} bounds (type \verb|List(Rat)|) on $v$ obtained by applying the simplex method to $P$. \item{\bf[..]} Let $a$ and $b$ be of type {\tt Int}, $a \leq b$. Then $a\verb|..|b$ expands to $a,a+1,\ldots,b$. \item{\bf[-]} Let $n$ be of type {\tt Int}. Then $\verb|-|n$ is its negation. \item{\bf[AsConfig]} Let $M$ be of type {\tt MatF2}. Then APPLY1(AsConfig,M) is a {\tt String} which indicates how $M$ might be defined by a {\tt config} command. The columns are sorted and repeated columns are contracted. \item{\bf[WeightEnumerator]} Let $M$ be of type {\tt MatF2}. Then APPLY1(WeightEnumerator,M) is the weight enumerator of the rowspace of $M$, as a list of integers. This may also be applied to an object of type {\tt List(MatF2)}. \item{\bf[AsPoly]} Convert an object of type {\tt List(Int)} into a polynomial in $t$, returning an object of type {\tt String}. Similarly convert {\tt List(List(Int))} to {\tt List(String)}. \item{\bf[WE]} Equivalent to $\verb|AsPoly| \circ \verb|WeightEnumerator|$. \item{\bf[Build]} Let \hconfig\ be a code type. Let \lconfig\ be a configuration for \hconfig. Then \verb|Build( |\hconfig, \lconfig\verb| )| returns the matrices that would have been obtained if a command of the form {\tt via building }\lconfig\ $= \ldots$ had been used from type \hconfig. \item{\bf[Random]} The syntax is \verb|Random( |{\it type}\verb|, |{\it size}\verb|, |{\it range}\verb|, |% {\it seed}\verb| )| where \begin{itemize} \item {\it type\/} is {\tt List(Int)} or {\tt MatInt} \item {\it size\/} is a single integer (if {\it type\/} $=$ {\tt List(Int)}) or two integers (separated by a comma) (if {\it type\/} $=$ {\tt MatInt}) \item {\it range\/} is two integers (separated by a comma), indicated low and high values for the random entries \item {\it seed\/} is a number to be used as a seed for the random number generator. \end{itemize} \item{\bf[A\_inverse\_b]} Let $A$ be of type {\tt MatInt}, which we assume is invertible. Let $b$ be of type {\tt List(Int)}. Then $\verb|A_inverse_b( |A\verb|, |b\verb| )|$ returns $A^{-1}b$, which is of type \verb|List(Rat)|. (This is experimental. Currently there is a third argument, the version number, which may be $0$ or $1$.) \item {\bf[Read]} The syntax is \verb|Read( |{\it type}\verb|, |{\it file name}\verb| )|, where {\it type\/} is the type of the object to be read and {\it file name\/} is the name of the file it is in. It must be at the beginning of the file. The only types which are currently allowed are {\tt List(Int)} and {\tt MatInt}. \item {\bf[Cyclic]} The syntax is $\verb|Cyclic(|c\verb|, |n\verb|, |k\verb|, |% {\it generator}\verb|, |{\it extra word}\verb|)|$. This yields a {\tt MatF2} $M$ of size $k \times n$, as follows. First one can define the {\it standard permutation\/} on $n$ of cycle type $(a_1,\ldots,a_r)$. By way of example, the standard permutation on $10$ of cycle type $(3,2)$ is given as a product of disjoint cycles by $(1,2,3)(4,5)$. Now the argument $c$ describes a permutation $\sigma$. It is the standard permutation on $n$ of a certain cycle type. First, if $c$ is a positive integer dividing $n$, the cycle type is $(n/c, \ldots, n/c)$, with $n/c$ appearing $c$ times. Otherwise, $c$ must itself be the cycle type. The generator and the extra word (if present) are to be zero-one vectors of length $\leq n$. Pad on the right with zeros to form vectors $v$ and $w$ of length $n$. If the extra word is not present, let $M$ have rows $\setof{v, \sigma(v), \ldots, \sigma^{k-1}(v)}$. Otherwise let the rows be $\setof{v, \sigma(v), \ldots, \sigma^{k-2}(v),w}$. Note that there is no guarantee that $\sigma$ is an automorphism of $M$. \item {\bf[OrbitCount]} If $G$ is a {\tt MatrixGroup(F2)}, then APPLY1(OrbitCount,G) returns the number of orbits of $G$ under its natural action on $\F_2^n$. In fact, \verb|OrbitCount| does more: it finds a system of orbit representatives. This information is not returned. \item {\bf[OrbitReps]} If $G$ is a {\tt MatrixGroup(F2)}, then APPLY1(OrbitReps,G) returns a matrix whose rows form a system of orbit representatives for $G$ under its natural action on $\F_2^n$. \item {\bf[DelsartePair]} $\verb|DelsartePair(|n\verb|,|k\verb|,|w\verb|,|r\verb|,{|c\verb|})|$ is the linear program associated to a the pair of linear codes consisting of an $[n,k,w]$ code, where $w$ is a list of integers, containing an $[n,k-1,r]$ code (where $r$ is a list of integers), subject to the constraint list $c$, involving global variables $Y_i$ for the larger code and $y_i$ for the smaller code. \item {\bf[Realizable]} Let $L$ be a list of matrices. Let \hconfig\ be a code type. Then $\verb|Realizable(|\hconfig\verb|, |L\verb|)|$ selects those matrices $L_i$ which realize the code type $L$. (In particular, their rowspaces must have the right dimension.) \item {\bf[Unresidue]} Let $L$ be a list of matrices. Let \hconfig\ be a code type and let \cconfig\ be a basal configuration for it. Then $\verb|Unresidue(|\hconfig\verb|, |\cconfig\verb|, |L\verb|)|$ returns a list of generator matrices for those codes (up to isomorphism) in \hconfig\ which satisfy the constraints of \cconfig and could have a residual code generated by a matrix in $L$. There is an optional fourth argument, a positive integer $r$, which causes computation to stop after $r$ codes, for each matrix in $L$. See also the parameters \verb|unresidue ! show all configs| and \verb|unresidue ! show extra info|. \item {\bf[Select]} Let $L$ be a list of matrices. Let $f$ be a constraint, or set-bracket-enclosed list of constraints, whose \LHS's are integer linear combinations of global variables, and whose \RHS's are integers. Then $\verb|Select(|L\verb|, |f\verb|)|$ selects those matrices $L_i$ whose rowspace (as a code) satisfies $f$. \item {\bf[subcodes disjoint from a bit]} If $M$ is of type {\tt MatF2}, then $M\verb| ~ column|$ is the list obtained by choosing isomorphism class members from $M\verb| ~ column |r$, as $r$ varies. Alternatively, $M$ may be of type {\tt List(MatF2)}, in which case $M_i\verb| ~ column|$ is computed and the lists are merged (taking only isomorphism class members). \item {\bf[Group]} Define an object of type {\tt Group}. given by generators and relations. We illustrate by examples. \begin{verbatim} Group( x, y : x^21, y^3, yx -> xy ) Group( x : x^65 ) Group( x, y, z : x^3, y^3, z^7, yx -> xy, zx -> xz, zy -> yz^2 ) \end{verbatim} Note the following. The generators must be letters. Positive powers of each generator (to be set equal to the identity) must always be given, immediately after the generators and in the same order. The other relations are given as replacement rules, as shown. These rules operate on words in the generators. It is the users responsibility to be sure that they work in the following sense: \begin{itemize} \item There are no infinite sequences of transformations. \item If $\alpha\verb| -> ... -> |\beta_1$ and $\alpha\verb| -> ... -> |\beta_2$, and $\beta_1$, $\beta_2$ are terminal (admitting no further transformations), then $\beta_1 = \beta_2$. \item The group is finite. \end{itemize} An error will be issued (perhaps later) if the group is larger than $1000$ or ``too many'' transformations seem to have occurred. \item {\bf[RegularRep]} For an object $G$ of type {\tt Group}, This generates the regular representation (over $\F_2$) of a finite group, given by generators and relations. We illustrate by examples. \begin{verbatim} RegularRep( x, y : x^21, y^3, yx -> xy ) RegularRep( x : x^65 ) RegularRep( x, y, z : x^3, y^3, z^7, yx -> xy, zx -> xz, zy -> yz^2 ) \end{verbatim} Note the following. The generators must be letters. Positive powers of each generator (to be set equal to the identity) must always be given, immediately after the generators and in the same order. The other relations are given as replacement rules, as shown. These rules operate on words in the generators. It is the users responsibility to be sure that they work in the following sense: \begin{itemize} \item There are no infinite sequences of transformations. \item If $\alpha\verb| -> ... -> |\beta_1$ and $\alpha\verb| -> ... -> |\beta_2$, and $\beta_1$, $\beta_2$ are terminal (admitting no further transformations), then $\beta_1 = \beta_2$. \item The group is finite. \end{itemize} An error will be issued if the group is larger than $1000$ or ``too many'' transformations seem to have occurred. \item {\bf[For]} Let $\verb|[|i\verb|]|$ be an indeterminate. This means that $i$ is a string that starts with a letter and is followed by zero or more alphanumeric characters (or underscores), and that $\verb|[|i\verb|]|$ is not already defined. Let $L$ be some sort of list. [So its type is $\verb|List(|\ldots\verb|)|$.] Let $s$ be any expression. Then $\verb|For( [|i\verb|], |L\verb|, |s\verb| )|$ is $\verb|{| s|_{[i] \mapsto L_1}, \ldots, s|_{[i] \mapsto L_n} \verb|}|$. \item {\bf[Transpose]} Assuming that $x$ has type $\verb|List(List(|\ldots\verb|)|$, APPLY1(Transpose,x) returns its transpose, assuming that it makes sense. \item {\bf[Reduce]} Let $M$ be of type {\tt MatF2}. Then APPLY1(Reduce,M) is the {\tt MatF2} obtained from $M$ by converting to \RREF\ and removing any zero rows. Also {\tt Reduce} may be applied to a {\tt List(MatF2)}, yielding another {\tt List(MatF2)}. \item {\bf[Orbits]} Let $L$ be of type {\tt MatrixGroup(F2)}, generating a group of $n \times n$ matrices $G$. Then $\verb|Orbits(|L\verb|)|$ is the set of orbits of $\F_2^n$ under the action of $G$. The output type is {\tt PVSF2}. Alternatively, if $L$ is of type {\tt List(MatrixGroup(F2))}, $\verb|{ Orbits(|L_1\verb|), |\ldots\verb|, Orbits(|L_n\verb|) }|$ is returned, which is of type {\tt List(PVSF2)}. \item {\bf[Diag]} If $\vec M1n$ are matrices (type {\tt MatF2}), then $\verb|Diag(|vec M1n\verb|)|$ is their direct sum, i.e.\ the matrix (type {\tt MatF2}) associated to the direct sum of the associated linear maps, \WRT\ the standard bases. If $\vec M1n$ instead have type {\tt List(MatF2)}, and each list has the same length, apply \verb|Diag| to their members in parallel, yielding a {\tt List(MatF2)}). \item {\bf[Length]} Let $L$ be a list (of some sort). Then APPLY1(Length,L) is the number of elements in the list, an object of type {\tt Int}. \item {\bf[P]} Let $M$ be of type {\tt MatF2}, which is replaced by its reduction. Let $\Simp$ be short for $\Simp({\tt M.nrows} - 1)$. Then APPLY1(P,M) is the reduction of $\BRMAT{1&0\cr\Simp&M}$. Also {\tt P} may be applied to an object of type {\tt HList(MatF2)}. \item {\bf[column deletion (without the column number)]} Let $M$ be of type {\tt MatF2}. Then $M\verb| - column|$ is obtained from $M$ by considering the list of all matrices obtainable from $M$ by deleting a column, and then choosing a sublist of isomorphism class representatives. In place of $M$, one may give a list of matrices, in which case the corresponding lists are merged, and again a sublist of isomorphism class representatives is returned. The output type is {\tt HList(MatF2)}. \item {\bf[perturbation]} For purposes of this paragraph, call one matrix a {\it perturbation\/} of another matrix if they have the same size and having differing entries in at most one column. Now let $M$ be of type {\tt MatF2}. Let $d$ be the minimum distance of the row space of $M$. For purposes of this paragraph, call a perturbation of some matrix {\it good\/} if its row space has minimum distance at least $d$. Then $\verb|Pert(|M\verb|)|$ is the list of all matrices (up to isomorphism) which are obtainable from $M$ via a sequence of good perturbations. The output type is {\tt HList(MatF2)}. There is an optional argument ``\verb|mu filter|'' which if used has the following effect. A perturbation $N$ is not used unless the code dual to its rowspace has a word of weight one or two. The input to $\verb|Pert|$ may be a list of matrices (generated by another operator). \item {\bf[double perturbation]} For $M$ of type {\tt MatF2}, $\verb|PertTwo(|M\verb|)|$ is defined in the same way as $\verb|Pert(|M\verb|)|$, except that here we use a different notion of perturbation: A matrix $N$ is a {\it perturbation\/} of a matrix $M$ if they have the same size, have differing entries in at most two columns (say $i$, $j$), and moreover $N^i - M^i = N^j - M^j$, where superscripts select columns. The optional argument ``\verb|mu filter|'' works the same way as it does for \verb|Pert|. There is also an optional argument ``\verb|ex triples|'' which if used has the following effect. Each time we consider making a perturbation a long columns $i$ and $j$, we check to see if there exists a dual word of weight $3$ whose support contains $i$ and $j$. If so, we do not make the perturbation. Usually when this option is used, one gets the same list of codes, but in a different order, and faster. There is also an optional argument of the form ``$\verb|stop after |r\verb| codes|$'', where $r$ is a positive integer, which will cause the perturbations to stop after a total of $r$ nonisomorphic matrices have been found. Example: $\verb|PertTwo(|M\verb|, stop after 10 codes)|$. The input to $\verb|PertTwo|$ may be a list of matrices (generated by another operator). A last option of the form {\tt start = }$r$ is allowed, which instructs the program to assume that perturbations of the first $r-1$ matrices are already included in the list. Note the following equivalent version of the perturbation employed by \verb|PertTwo|, provided that the rowspace of $M$ is an even code. In effect, you delete two columns from $M$, add a completely arbitrary column, and then add a parity check column. \item {\bf[macro substitution]} An expression of the type \begin{center} $\verb|Sub( {|\hbox{\it definition}_1,\ldots,\hbox{\it definition}_n\verb|}, |% \hbox{\it body}\verb| )|$ \end{center} is processed by substituting the given definitions into the body. A definition takes either the constant form \par\noindent \kern0.5in \hbox{\it name}\verb| := |{\it definition-body} \par\noindent or the variable form \par\noindent \kern0.5in \hbox{\it name}$\verb|(%1|,\ldots,\verb|%|n% \verb|) := |$\hbox{\it definition-body} \par\noindent where in the second case, the definition body may include the $\verb|%|i$'s. A {\it name\/} is to be an alphanumeric string (allowing underscores), which starts with a letter. Up to nine parameters are allowed. The output of a substitution is automatically enclosed in parentheses. \item {\bf[Isomorphic]} Let $A$ and $B$ be of type {\tt MatF2}. Then $\verb|Isomorphic(|A\verb|,|B\verb|)|$ is of type {\tt Bool}. It is {\tt true} \IFF\ $A \iso B$, meaning that after applying some permutation to the columns of $A$, it has the same rowspace as $B$. \item {\bf[Isomorphic]} Let $G$ and $H$ be of type {\tt MatrixGroup(F2)}. Then $\verb|Isomorphic(|G\verb|,|H\verb|)|$ is of type {\tt Bool}. It is {\tt true} \IFF\ $A \iso B$, meaning that the representations defined by $G$ and $H$ are isomorphic. However, this only works with semisimple representations $G$ and $H$. Otherwise an error will be issued. \item {\bf[Classify]} Let $L$ be of type {\tt List(MatrixGroup(F2))}. Then APPLY1(Classify,L) is of type {\tt List(Int)}. It is a list $v$ of positive integers, such that $\setof{A_i}_{i \in v}$ comprise a complete set of isomorphism class representatives (for the $L_i$, viewed as representations). The $L_i$ must all be semisimple. \item {\bf[Isomorphic]} Let $A$ and $B$ be of type {\tt PVSF2}. Then $\verb|Isomorphic(|A\verb|,|B\verb|)|$ is of type {\tt Bool}. It is {\tt true} \IFF\ $A \iso B$, meaning that both $A$ and $B$ are partitions of $\F_2^n$ and there exists a linear automorphism of $\F_2^n$ moving one partition to the other. \item {\bf[Classify]} Let $A$ be of type {\tt List(PVSF2)}. Then APPLY1(Classify,A) classifies $\vec A1n$ up to isomorphism, returning a {\tt List(Int)} $v$ of positive integers, such that $\setof{A_i}_{i \in v}$ comprise a complete set of isomorphism class representatives. \item {\bf[list]} Let $\vec A1n$ be objects of type $\alpha$. Then $\verb|{|A_1\verb|,|\ldots\verb|,|A_n|\verb|}|$ is of type $\verb|List(|\alpha\verb|)|$, provided that the latter type has been defined in the class \verb|generic_object|. \end{itemize} \par\noindent{\Large\bf Expression list \circno8} \midhead{The dual transform} Let $M$ be of type {\tt MatF2}, which is first reduced. The syntax of this operator is \begin{center} $M$\verb|^T using|\kern5pt$\setof{\VEC w1r}$, \end{center} where the $w_i$ are yet to be defined. Let $C$ be $M$'s row space. Each $w_i$ defines a certain subset $S_i$ of $C$, as follows. If $w_i$ is a nonnegative integer, then $S_i$ is the set of words of weight $w_i$ in $C$. If $w_i$ has the form ``$a$\verb|_{|$\VEC b1t$\verb|}|'', where each $b_i$ is a nonzero integer, then $S_i$ is the set of words of weight $a$ which for each $j$ have a $1$ in position $b_j$ (if $b_j > 0$), and a $0$ in position $-b_j$ (if $b_j < 0$). \par\noindent{\sc Note.}\ For purposes of display in the program part of this report, we will write (e.g.) $\ldots$\ {\tt using} $\{10,12_{\ol{1},2,\ol{5}},20\}$ instead of $\ldots$\ {\tt using} \verb|{10,12_{-1,2,-5},20}|. Let $S$ be the multiset $\bigcup_{i=1^r} S_i$. For $s \in S$, let $\lambda(s)$ denote its coordinate vector \WRT\ the ordered basis given by the rows of $M$. The value of the dual transform operator is the reduction of the matrix whose columns are $\setof{\lambda(s)}_{s \in S}$, in lexicographical order (for definiteness). The output type is {\tt MatF2}. \midhead{The dual orbit transform} Let $M$ be of type {\tt MatF2}. The syntax of this operator is \begin{center} $M$\verb|^T using {|\kern5pt% $\VEC g1r$\kern5pt\verb|:|\kern5pt$\VEC c1m$\verb|}|, \end{center} where $M$ is of type {\tt MatF2}; the $g_i$ and $c_i$ are yet to be defined. Let $C$ be $M$'s row space. Each $g_i$ is to have the form $\verb|$|r$, where $r \in \N$; it represents the \th{r}\ generating automorphism of $\Aut(M)$, as computed by {\tt Split}. As such these automorphisms are perilously dependent on slight changes to internal routines which might appear in a future version of {\tt Split}. Let $\VEC c1m$ be coordinate vectors for elements $\VEC w1m \in C$, relative to the rows of $M$. Let $S$ be the orbit of $\VEC w1m$ under the given automorphisms, viewed as a subset of $C$ (or a multiset in $C$ if there is repetition amongst $\VEC w1m$). Then proceed as with the dual transform. \block{More expressions} This section contains a collection of functions. We show the source code here, in a slightly prettified form. The actual source code is generated from the prettified source via a program {\tt parse_fun.cc}, which is included in {\tt CODE}. \input functions.tex \block{How to define a configuration} There are two main ways to define a configuration: the {\tt config} command, and the {\tt :=} command. We describe these first. Then we describe some other commands which can be used to define a configuration: {\tt config from}, {\tt incorporate}, and {\tt subdivide along}. \indexb{config} \begin{commanddeclaration} \vbox{\hbox{% $\displaystyle{\overbrace{\hbox{\tt=}}^{\hbox{optional}}} \displaystyle{\underbrace{\hbox{\lconfig}}_{\hbox{optional}}}$ {\tt config}\ \ {\it partition} {\tt:} {\it \{basis\}\/} $\displaystyle{\overbrace{\hbox{{\tt:} {\it \{dual basis\}} $\displaystyle{\underbrace{\hbox{{\tt:}\kern5pt{\tt\{}% \ {\it constraint list\/}\ {\tt\}}}}% _{\hbox{optional}}}$ }}^{\hbox{optional}}}$ {\tt;}% }% \hbox{\footnotesize{\ \ }}% \hbox{\footnotesize{\sc Note:}\ You never have to write ``{\tt\{\}}'' as part of this command -- replace it by the null string.}} \end{commanddeclaration} This command defines a {\it configuration}. We illustrate by an example: \begin{verbatim} type [32,14,10_2]; config 10,10,12 : {110,100}; \end{verbatim} These two commands tell us that we are looking at even codes of dimension $14$ in $\F_2^{32}$, which contain the following two words: \begin{verbatim} 1111111111 1111111111 000000000000 1111111111 0000000000 000000000000. \end{verbatim} (The spaces have been inserted to enhance readability.) If a dual basis is given, the dual code is expected to contain the given words. The elements of the ``basis'' are expected to be \LI, and likewise for the elements of the ``dual basis''. Use of the command \par\noindent\kern0.5in{\tt type [}$n${\tt, ...];} automatically generates the base configuration, as if the command ``{\tt config}\ $n$\ \verb|: { };|'' had been executed. If the {\it constraint list\/} is present, attention is restricted to those codes which satisfy the given constraints. A weight enumerator (e.g.\ \verb|1 + 6t^10 + t^20|) may be given as a ``constraint''. If a configuration is listed in the constraint list, it is expanded out to the list of all known global and joint constraints for the given configuration. The optional \lconfig\ is a label which is associated to the configuration for future reference. Within a given code type, a configuration label may not be defined more than once. The labels {\tt[base]} and {\tt[current]} are reserved for reference to the base and current configurations of the current code type. More complicated labels are created by the ``{\tt incorporate}'' ``{\tt:=}'' commands. The optional ``{\tt=}'' will cause the ``{\tt=}'' command to be automatically invoked on the configuration defined by this command and the configuration that was current prior to it. When a {\tt config} command is entered, aside from syntax, not much is checked. The language reserves the right to flag as errors certain things that no one would do deliberately. For example, for every word in the small code, the weight of the associated basic word should be in the working weight list for the base configuration. If at the some point it is found that a configuration is unrealizable, the language interpreter will discard all information about the configuration except this fact. \indexb{:=} \begin{commanddeclaration} {\it configuration-list\/}\kern5pt\verb|:= |{\it expression}\kern5pt% $\displaystyle{\underbrace{\hbox{{\tt::}\kern5pt{\tt\{}% \ {\it constraint list\/}\ {\tt\}}}}% _{\hbox{optional}}}${\tt;} \end{commanddeclaration} Usually the {\it configuration-list\/} consists of a single configuration \lconfig. In that case, create a fully refined configuration named \lconfig\ whose associated code has the generator matrix given by the expression. If \lconfig\ is terminal, is expected to be realizable. If {\it constraint list\/} is supplied, this command also automatically creates a configuration labelled {\tt[}$\ell${\tt!]} which is basal and has {\it constraint list\/} for its assumed constraints. As well, the implication ${\cal R}(\ell) \IN {\cal R}(\ell\hbox{\tt!})$ is noted. If the constraint list is ``\verb|{!}|'', it will automatically be replaced by the list of constraints which defines the weight enumerator of the code. If {\it configuration-list\/} has more than one configuration in it, then proceed as above, but the given expression should expand out to the same number of matrices, and the {\it constraint list\/} is not allowed (except for the ``\verb|{!}|'' format). \vspace{0.05in}\par\noindent{\sc Parameters:}\ The following parameters are associated to this command: \def\parwa{3.3in} \begin{longtable}{|l|l|l|l|}\hline \parbox{1.6in}{\bf parameter} & \parbox{1.0in}{\vskip 0.05in {\bf allowed}\\ {\bf values}\vskip 0.05in } & {\bf default} & \parbox{\parwa}{\bf meaning} \\ \hline\hline \endhead \dtext{:= !}{ingredient tracking} & $0$, $1$ & $1$ & \parbox{\parwa}{\vskip 0.05in If set to $0$, turn off a safety feature which causes a record to be made (in the {\tt hints} directory) of all configurations used as ingredients by the {\tt :=} command. If there are a huge number of these, you may want to turn off ingredient tracking. \vskip 0.05in}\\ \hline \end{longtable} \indexb{config from} \begin{commanddeclaration} $\displaystyle{\underbrace{\hbox{\lconfig}}_{\hbox{optional}}}$ {\tt config from }$v_1${\tt|}$\ldots${\tt|}$v_r${\tt;} \end{commanddeclaration} Let $v_1$ be a basic local variable for {\tt[current]}. Show that it is nonzero, and subdivide along it to obtain a new configuration, which $v_2$ should be a basic local variable for. Show that $v_2$ is nonzero, and subdivide along it. Continue in this manner. The last configuration is made current, and is named \lconfig\ if the optional label is present. \def\nconfig{{\tt[}$n${\tt]}} \indexb{incorporate} \begin{commanddeclaration} \nconfig\kern5pt{\tt incorporate}\kern5pt\lconfig\kern5pt{\tt below}% \kern5pt\mconfig\kern5pt{\tt via sub}$w${\tt;} \end{commanddeclaration} \par\noindent{\sc Idea:} \ The fact that one code is known to contain another code may be used to copy configurations from one code type to another. \vspace{0.05in}\par\noindent{\sc Requirements:} \begin{itemize} \item \lconfig\ is an existing code type, which has no joint variables in its assumed constraints, and such that none of its configurations have joint variables in their assumed constraints\footnote{Constraints which set a basic joint variable to zero are however allowed.}; \item \mconfig\ is a configuration of the current code type, which may not have local variables in its assumed constraints, except that it may have a constraint {\tt sub}$w$ {\tt=}$g$, for some $g$ (see below); \item \nconfig\ identifies the given {\tt incorporate} command; it may not be used to label any other {\tt incorporate} command within the current code type; \item $w$ is a small word (relative to \mconfig), which has weight $1$ (as a small word); \item it must be known that $\verb|sub|w \geq 2^d$, where $d$ is the dimension of the code type referred to by \lconfig; \item Let $r$ be the part of the partition corresponding to the $1$ in $w$. Then the code type referred to by \lconfig\ must have length $r$ and dimension $\log_2($\verb|sub|$w)$. Its assumed weight list must contain \mconfig's working weight list. (Weights greater than $r$ are ignored.) Its assumed constraints must lift to known constraints for \mconfig, as in the following example: \begin{verbatim} [c] type [30,10,10]{y14 >= 10}; ... [d] type [36,15,10]; ... show mu6 != 0; [x] config 30,6 :: {01}; ... show x_14_0 >= 10; infer sub10 = 1024; [u] incorporate [c] below [x] via sub10; \end{verbatim} \end{itemize} \vspace{0.05in}\par\noindent{\sc Action:} \ The {\tt incorporate} command causes more or less the entire body of information for \lconfig\ to be imported into the current code type, sort of below \mconfig. In particular, each configuration \sconfig\ of \lconfig\ is used to generate a configuration \spconfig\ of the current code type. To do this it is necessary to carry out a number of conversions: \begin{itemize} \item All variables which appear in assumed or known constraints of \sconfig\ are reconstituted in terms of appropriate variables for \spconfig. Global variables are translated into {\tt sub} variables or linear combinations of them. Known constraints involving joint variables are lost. \item Words in the dual small code of \sconfig\ do not induce words in the dual small code of \spconfig. So instead such words are converted into assumed constraints involving {\tt q} variables. \item \spconfig\ has the label {\tt[}$n${\tt->}$s${\tt]}. Iterative use of incorporate will lead to configurations whose labels have more than one {\tt->} in them. \end{itemize} Automorphism labels are unchanged in the process. Continuing the preceeding example, if code type \verb|[c]| has a configuration defined via \begin{verbatim} [a] config 8,10,12 : {110,001} :: {y6 <= 4, x_0_1_0 = 0}; \end{verbatim} then after the {\tt incorporate} command, code type \verb|[d]| will have a configuration defined as if via \begin{verbatim} [u->a] config 8,10,12,6 : {1100,0010} : {0001} : {sub1110_6 <= 4, x_0_1_0_0 = 0}; \end{verbatim} although it would not be permissable to make such a definition, since the label would not be accepted. \indexb{subdivide along} \begin{commanddeclaration} $\displaystyle{\underbrace{\hbox{\lconfig}}_{\hbox{optional}}}$ {\tt subdivide along}\kern5pt$v${\tt;} \end{commanddeclaration} Forcibly subdivide {\tt[current]} along the given basic local variable, passing all known constraints for {\tt[current]} to it. Label the new configuration \lconfig, and make it current. \block{Group manipulation commands} To each configuration, there is associated a data item which relates to automorphisms: the list of {\bf known} automorphisms. These are to be viewed as generators. Some of the automorphisms have labels. Note that whenever a constraint which sets a basic local variable $v$ to zero is proved, the program automatically computes the orbit of $v$ under the group of known automorphisms, and sets all these variables equal to zero. Here are the commands: \indexb{automorphism} \begin{commanddeclaration} $\displaystyle{\underbrace{\hbox{\lconfig}}_{\hbox{optional}}}$ {\tt automorphism }$\VEC a1r${\tt;} \end{commanddeclaration} Verify that the given permutation defines an automorphism of the current configuration. Append it to the list of known automorphisms for the current configuration. A label \lconfig\ may be given. Within a given configuration, automorphism labels may not be repeated. \indexb{group size} \begin{commanddeclaration} {\tt group size = }$m${\tt;} \end{commanddeclaration} Verify that the group generated by the list of known automorphisms has $m$ elements. The implementation is very inefficient. \indexb{full group size} \begin{commanddeclaration} {\tt full group size = }$m${\tt;} \end{commanddeclaration} Verify that the automorphism group of {\tt[current]} has $m$ elements. For this command, {\tt[current]} may not have local variables in its assumed constraints. \indexb{report group size} \begin{commanddeclaration} {\tt report group size [}$\ell_1${\tt]}, $\ldots$\kern2pt, {\tt[}$\ell_r${\tt];} \end{commanddeclaration} This is a purely exploratory command. Given automorphisms {\tt[}$\ell_1${\tt]}, $\ldots$, {\tt[}$\ell_r${\tt]}, this command reports in order the size of the group generated by {\tt[}$\ell_1${\tt]}, then the size of the group generated by {\tt[}$\ell_1${\tt]}, {\tt[}$\ell_2${\tt]}, and so forth, lastly reporting the size of the group generated by {\tt[}$\ell_1${\tt]}, $\ldots$, {\tt[}$\ell_r${\tt]}. However, if one of these groups turns out to be very large, the command may never finish. The implementation is very inefficient. \indexb{reduce variable set} \begin{commanddeclaration} {\tt reduce variable set;} \end{commanddeclaration} Compute the automorphism group of the configuration. From the list of minimal admissible basic local variables $v$ (for {\tt[current]}), find those which are carried by an automorphism to an inadmissible basic local variable, and adjoin the corresponding constraints $v = 0$ to the list of known constraints. Ideally this would be done automatically as needed. \block{Configuration relation makers} Many of the commands of the language create logical relationships between configurations. All of the commands of this section do this. The {\tt !config} command does too. In addition, certain logical relationships come for free and are automatically known to the language: \begin{itemize} \item every configuration \lconfig\ implies the base configuration, i.e.\ ${\cal R}(\ell) \IN {\cal R}(\hbox{\tt base})$. \end{itemize} All commands in this section leave the current configuration undefined upon termination. \indexb{via dual nonexistence infer} \begin{commanddeclaration} \verb|via dual nonexistence infer [base] = ;| \end{commanddeclaration} Assume that the code type has no assumed constraints. Let $d$ be the minimum weight in the working weight list $w$ for {\tt[base]}. Suppose the minimum weight of the dual code is known to be $\geq d'$. Suppose we know that no \par\noindent\kern0.5in \verb|[n, n-k, d']{mu1 = 0,|\kern5pt$\ldots$\verb|, mu|$(d-1)$\verb| = 0}| \par\noindent code exists. Then one may infer that {\tt[base]} is unrealizable. In the case where $w$ has no odd weights, it is enough to know that no \par\noindent\kern0.5in \verb|[n, n-k, d']{mu1 = 0,|\kern5pt$\ldots$\verb|, mu|$(d-1)$\verb| = 0, y|% \kern1pt$n$\verb| = 1}| \par\noindent code exists. The intended purpose of this command is to bypass numerical instability of linear programming problems arising from the split linear programming method. It is useful when $k > n/2$. \indexb{implies}\indexb{=} \begin{commanddeclaration} \vbox{% \hbox{\lconfig\kern5pt{\tt implies}\kern5pt\mconfig{\tt;}}% \hbox{\lconfig\kern5pt{\tt =}\kern5pt\mconfig{\tt;}}} \end{commanddeclaration} \def\ttvec#1#2#3{$#1_#2${\tt,}$\ldots${\tt,}$#1_#3$} Let \lconfig, \mconfig\ be configurations. These commands are placeholders for the most trivial of trivial implications, whose conclusion in the first case is that ${\cal R}(\ell) \IN {\cal R}(m)$ and in the second case that ${\cal R}(\ell) = {\cal R}(m)$. The following cases are handled at present: \begin{itemize} \item (for {\t