\magnification=\magstep1
\overfullrule4pt
\voffset-1pc
\def\qed{\nobreak\enskip\vbox{\hrule height5pt width 5pt depth 0pt}}
\def\wt{\hskip4pt \hbox{wt}}
\def\F{{\cal F}_2}
\def\SS{{\cal S}}
\def\E{{\cal E}}
\def\C{{\cal C}}
\def\Z{{\cal Z}}
\def\D{{\cal D}}
\def\H{{\cal H}}
\def\ss{\scriptstyle}
\def\wt{\hbox{\rm wt\thinspace}}
\def\Rsigma{R^{\langle\sigma\rangle}}
\newcount\NUM \NUM=0
\newcount\secno \secno=0
\def\sec#1.{\vskip12pt\global\advance\secno by 1\goodbreak{\noindent\secfont 
\number\secno. #1}\vskip 8pt}
\def\procno{\global \advance \NUM by 1 \number\NUM}
\long\def\proc#1.#2\endproc{\par\vskip6pt{\bf #1.}\kern4pt {\sl #2}\vskip6pt}
\font\title=TimesB at 16 pt%TimeNRB at 16pt   %
\font\name=Times at 14pt%TimeNRR at 14pt %
\font\secfont=TimesB at 14 truept%TimeNRB at 14truept%
\ 
\vskip6pc

\centerline{\title Construction of  Self-Dual Binary Codes of  Even Length}
\vskip6pt
\centerline{\name Gerald J. Janusz}
\vskip4pt
\centerline{\it University of Illinois at Urbana-Champaign}
\vskip4pc

{\leftskip3pc\rightskip3pc ABSTRACT: We use the algebra
 $\F[x]/(x^k-1)$, or equivalently the group algebra $\F[\langle X
\rangle]$ of a cyclic group $\langle X \rangle$ of order $k$, and its
automorphism  that inverts $X$,   to construct  a family of
self-orthogonal codes of  length $k$.  For even $k$, the codes  are
self-dual of Type I, while for odd $k$, they are maximal
self-orthogonal codes which produce self-dual codes of length
$k+1$.  In case $k$ is divisible by 8, some of the codes have
adjacent codes that are self-dual of Type II.  We consider  special
cases of lengths 32, 34,  36 and 38.  The construction produces (at
least) 78 inequivalent codes with parameters $[34,17,6]$,  3
inequivalent extremal codes with parameters $[36,18,8]$  having
the same weight enumerator, and 2 inequivalent extremal codes
with parameters $[38,19,8]$ having the same weight enumerator.
For the case $k=32$,  it produces 13 (non-extremal) inequivalent
codes with parameters $[32,16,6]$ having 3 different weight
enumerators.  \smallskip}

\bigskip
\sec Introduction.

The study of cyclic codes is often placed as the study of  ideals 
of the ring $R=\F[\langle X\rangle]$, the group algebra of a cyclic
group $\langle X\rangle$ of order $k$ over the field $\F$ of two
elements. A great deal of information is known about such codes
[see MS, Chs. 7,8,9], especially in the case  where the order of $X$
is an odd number.  In this work, we study the ring $R$ (mainly
with $k$ even) and use it to produce a number of  noncyclic
self-dual codes both of Type I and Type II (singly even and doubly
even).  In the specific cases $k=34$ we obtain many new codes;
for $k=36$ we obtain three inequivalent extremal codes, at least
two of which seem to be new; for $k=38$ we obtain two
inequivalent extremal codes, one of which seems to be new.  We
also examine some of the (non extremal) codes at length 32 finding
13 inequivalent codes with parameters $[32,16,6]$.
\vfill\eject

\sec Notation and  a description of some self-dual codes.

Let $k$ be a positive integer with factorization $k=2^{\alpha}k_0$ for some $\alpha$ and some odd integer $k_0$.  Let
$$
R=R_k = {\F[x] \over (x^k-1)}
$$
so that $R$ is a $k$-dimensional algebra over the field $\F$ of two elements.  We write $X$ for the coset of $(x^k-1)$ containing $x$ so that $X^k=1$ and
$
R=\F + \F\,X +\cdots+\F\,X^{k-1}.
$

It will sometimes be useful to also regard $R$ as the group algebra of the cyclic group $\langle X \rangle$ of order $k$ over the field $\F$.
In general, if $G$ and $H$ are finite groups and $\mu:G\to H$ is a homomorphism of groups, then there is a extension of $\mu$ to a homomorphism from the group algebra $\F[G]$ to the group algebra $\F[H]$ that agrees with $\mu$ on $G$ and is a homomorphism of rings.  In particular the trivial homomorphism $\langle X \rangle\to 1$  induces the homomorphism $\epsilon: R\to \F$ called the {\bf augmentation} map. Since $\langle X \rangle$ has an automorphism that sends $X$ to $X^{-1}$, it has an extension to an
 algebra  automorphism  $\sigma$ of $R$  sending $X^i$ to its inverse $X^{-i}$. 

The group of units of $R$ is denoted by $U=U(R)$ or sometimes $U_k$.  The subring consisting of all elements left fixed by $\sigma$ is 
$$
\Rsigma = \{  r\in R: \sigma(r)=r\}.
$$

A convenient  basis for $\Rsigma$ consists of the elements
$$
f_0=1, f_i=X^i+X^{-i},\quad  i=1,2,\ldots,{k\over 2}-1,\quad  f_{k/2} = 1+X^{k/2} \eqno(1)
$$ where, in case $k$ is odd,  the last element is omitted and $i$ is restricted to $1\leq i\leq (k-1)/2$.
We summarize these facts:

\proc Proposition \procno . The dimension of $\Rsigma$ over $\F$ is $1+(k/2)$ if $k$ is even and $(k+1)/2$ is $k$ is odd. \endproc

Let $\epsilon:R\longrightarrow \F$ be the augmentation map and let the weight $\wt(y)$ of an element $y\in R$
 be the number of nonzero coefficients in the canonical representation of $y$ as a linear combination of powers of $X$.  If $y=\sum a_iX^i$, then
$$
\epsilon(y) =\sum a_i \equiv \wt(y) \pmod 2.
$$
These remarks are used to prove the following.

\proc Proposition \procno.  Let $M$ be the set of elements of $R$ with even weight and $V$ the set of elements of $\Rsigma$ of even weight.  Then:
\item{i.} $M$  is the kernel of $\epsilon$ and is a maximal ideal of $R$; 
\item{ii.} $V$  is the kernel of $\epsilon$ restricted to $\Rsigma$ so $V$ is a maximal ideal of $\Rsigma$.
\item{iii.}All units of $R$ have odd weight.
\endproc 
The maximal ideal $V$ of $\Rsigma$ is 
$$ 
V=  \sum_{i=1}^{k/2} \F\,f_i
$$
with the $f_{k/2}$ omitted if $k$ is odd.

\bigskip

We view subspaces of  $R$ as linear codes with the powers of $X$ as the canonical basis, the usual dot-product is  given by the following rule:

For $y=\sum a_i X^i$ and $z=\sum b_iX^i$,
$$
y \cdot z = \sum a_ib_i.
$$
To study properties of the dot product, we introduce
the linear map $\rho:R\to \F$  defined by
$$
\rho(X^i) =\cases{1&if $i=0$\cr 0& if $1\leq i <k.$\cr}
$$


\proc Proposition  \procno. The dot product, the maps  $\rho$ and
$\sigma$ are related by the rules 
$$\eqalign{
i.&\qquad y\cdot z =\rho(y\sigma(z))=\rho(\sigma(y)z),\cr
ii.&\qquad y\cdot zw = y\sigma(w)\cdot z\cr}
$$ for all $y,z,w \in R$.

\endproc

Proof.  For $y=\sum a_i X^i$ and $z=\sum b_iX^i$, we see 
$$y\sigma(z) = \sum_{i,j}a_ib_j X^{i-j} = \sum a_ib_i + \sum_{t\neq 0}\sum a_i b_{i-t}X^t.
$$ 
It follows that
$$
y\cdot  z = \sum a_ib_i =\rho(y\sigma(z)) = \rho(\sigma(y)z).
$$ Property (ii) follows from (i) because both sides of the equation equal $\rho(y\sigma(z)\sigma(w))$.\qed



The dual $C^{\perp}$ of a subspace $C$ of $R$ is the set 
$$
C^{\perp} = \{y\in R\,:\,\rho(\sigma(y)c)=0,\hbox{ for all }\ c\in C\}.
$$

We  can now describe the codes we wish to study. The set $V$ is the collection of all elements of $\Rsigma$ having even weight.   For a unit $u\in U_k$, let
$$
Vu=\{vu:\ v\in \Rsigma,\ \wt(v) =\hbox{\ even}\ \}
$$
These are usually self-dual codes as we now show.

\medskip
\proc  Theorem \procno.   Let $V$ be the maximal ideal of $\Rsigma$ consisting of all elements of even weight,  $u$  any unit of $R$ and $Vu = \{vu: v\in V\}$.
 Then: 
\item{ (1)}  If  $k$ is odd,  $Vu$ is a maximal self-orthogonal  subcode of $R$. 
\item{(2)} If $k$ is even, $Vu$ is a self-dual subcode of $R$.
\endproc

Proof.  Since $V$ is the kernel of a homomorphism from $\Rsigma$ onto $\F$, 
  $V$ has dimension $(k-1)/2$, if $k$ is odd, and dimension $k/2$ if $k$ is even. A basis for $V$ consists of the elements
$f_1,\ldots,f_{k/2}$ with $f_{k/2}$ omitted when $k$ is odd. The dot products $f_i \cdot f_j $ are all 0, 
which  we see by noticing that the different $f_i$ have no common powers of $X$.  Thus $V \subseteq V^{\perp}$.  The equality $V=V^{\perp}$  holds for even $k$  by dimension counting. For $k$ odd, $V$ is a maximal self-orthogonal subcode of $R$ having dimension $(k-1)/2$.

Now let 
$u$ be any unit of $R$.  Then multiplication by $u$ gives an isomorphism of $R$ with itself (as vector spaces) and so $Vu$  has the same dimension as  $V$.  The elements $f_iu$ with $f_i$ running over the basis for $V$, give a basis for $Vu$.  For any $i,j$ we have (by Proposition 3)
$$
f_iu \cdot f_ju = f_iu\sigma(u)\cdot f_j.
$$
The element $u\sigma(u)$ is a unit in $\Rsigma$ and so $Vu\sigma(u)=V$ as $V$ is an ideal of $\Rsigma$. Thus $f_iu\sigma(u)\cdot f_j=0$ as $V$ is self-orthogonal. This  proves that $Vu$ is self-orthogonal.
 
Thus $Vu\subseteq (Vu)^{\perp}$ with equality when $k$ is even, proving  statements (1) and (2). \qed
\medskip
\noindent
{\bf Remark:}  For $k$ odd, we obtain a self-dual code $(Vu)^{\dagger}$ of length $k+1$ by adding one coordinate, then adjoining the all 1 vector {\bf  1} to $Vu$ to obtain a self-dual code $Vu+\F\,\hbox{\bf 1} $ with parameters $[k+1,(k+1)/2]$.

\bigskip

\sec The Unit Group.

Next we describe  the unit group and obtain a useful parameterization of the units of $R$.  The unit group $U(R)$ is a direct product of its subgroup of 2-power order and its maximal subgroup of odd order.  We compute the orders of each separately. 

Let $k=2^{\alpha}k_0$ with $k_0$ an odd integer and $\alpha \geq 0$. Set $Y=X^{2^\alpha}$ so that the order of $Y$ is $k_0$.  The subring $\F[Y]$ of $R$ is isomorphic to $R/\hbox{rad}(R)$ where $\hbox{rad}(R)$ is the radical of $R$, which is equal to the set of nilpotent elements of $R$. In particular $\F[Y]$ is a commutative semisimple ring and must be a direct sum of fields.  Thus
$$
\F[Y] = \F[Y]e_1  \oplus\cdots\oplus \F[Y]e_t,\qquad e_ie_j=\cases{e_i&if $i=j$\cr 0&otherwise.\cr}
$$
Each  summand $\F[Y]e_i$ is a field extension of $\F$;  we let $d_i$ denote its dimension, so that $\F[Y]e_i
=GF(2^{d_i})$, the field with $2^{d_i}$ elements.   Exactly one of the $d_i$ is 1 so we assume $d_1=1$ and $\F[Y]e_1=\F e_1$.

The ring $\F[Y]$ is invariant under the action of $\sigma$ and so $\sigma$ permutes the $e_i$ (as the set of primitive idempotents is unique).  We arrange the notation so that $e_i=\sigma(e_i)$ for $1\leq i\leq r$ and $\sigma(e_{r+i})= e_{r+i+s}$ for $1\leq i\leq s$.  Thus the number of distinct primitive idempotents is $r+2s$. Note that the $e_i$ correspond one-to-one with the irreducible factors of the polynomial $y^{k_0}-1$ in the polynomial ring $\F[y]$. The correspondence is such that an irreducible factor of degree $d$ corresponds to an $e_i$ with $d=d_i$.


As an aside, we remind the reader how the  primitive idempotents $e_i$ are computed.  Let $x^{k_0}+1$ be factored in the polynomial ring as
$$
x^{k_0}+1 = \prod_{i=1}^{r+2s} p_i(x),
$$
with each $p_i(x)$ an irreducible polynomial in $\F[x]$ and $p_1(x)=x+1$.  Let
$$
h_i(x) = {x^{k_0}+1 \over p_i(x)}
$$
so that the collection $h_(x),\ldots,h_{r+2s}(x)$ has no common divisor of positive degree.  Hence by the Euclidean algorithm, there exist polynomials $a_i(x)$ such that
$$
1=h_1(x)a_1(x) +\cdots+h_{r+2s}(x)a_{r+2s}(x).
$$
If the $p_i(x)$ are numbered to suit our conventional arrangement of the  $e_i$, then $e_i$ is the coset of $h_i(x)a_i(x)$ modulo $x^{k_0}+1$.


A unit $u$  of $R$ having odd order lies in $\F[Y]$. This holds because $u$ and $u^2$ generate the same cyclic subgroup and so $u$ is in the subgroup generated by $u^{2^{\alpha}}$, which lies in $\F[Y]$.
The odd part of the unit group $U(R)$ has order
$$
\prod_{i=1}^{r} (2^{d_i}-1) \prod_{j=1}^s (2^{d_{r+j}}-1)^2,
$$
since the units in $\F[Y]$ have the form $\sum_i u_ie_i$ with $u_ie_i$ a unit in the field $GF(2^{d_i})$.

We also will need to notice that the dimension $k_0$ of $\F[Y]$ over $\F$ is related to the $d_i$ by
$$
dim\, \F[Y]=k_0 = \sum_{i=1}^r d_i + \sum_{j=1}^s 2d_j.
$$
We summarize the computations so far.

\proc Proposition \procno. The units of  $R$ having odd order  have the form
$$
e_1+\sum_{i=1}^r p_i(Y)e_i + \sum_{j=1}^s (q_j(Y)e_{r+j}+q_j(Y^{-1})e_{r+s+j})
$$
where $p_i(Y)$ and $q_j(Y)$ are nonzero  polynomials in $Y$ having degrees less than $d_i$ and $d_j$ respectively.\endproc 


If $k=k_0$ is odd, then all units of $R$ have odd order and we are finished with the units. So assume that $k$ is even.
We determine the units of 2-power order.   An element $u$ of 2-power order has the form $u=1+r$ with $r\in \hbox{rad}(R)$. This is easily seen for if $u$ has order $2^\beta$ and if we write $u=1+r$, then
$$
1=u^{2^\beta}=(1+r)^{2^\beta}=1+r^{2^\beta}
$$
from which we conclude $r$ is nilpotent and therefore lies in the radical. Conversely for any element $r$ in the radical, the same consideration implies $u=1+r$ is a unit with order a power of 2.  Hence the 2-part of the order of the unit group is $2^D$ with   $D=dim(\hbox{rad}(R))$. We may determine the dimension easily because we know the dimension of $R/\hbox{rad}(R)$ is $k_0$. Thus
$$
D=dim(R)-dim(\F[Y]) = k-k_0.
$$
We obtain the following parameterization of the units of order a power of 2.

\proc Proposition \procno. The units of  $R$ having  order a power of 2 have the form
$$
1+\sum_{i=1}^{-1+2^{\alpha}} p_i(Y)\xi^i 
$$
where $\xi=1+X^{k_0}$ and $p_i(Y)$  is a polynomial in $Y$ having degree less than $k_0$.
\endproc

Proof. The radical of $R$ is the ideal generated by $\xi$ and every element in the radical can be expressed uniquely in the form  $\sum_{i=1}^{-1+2^{\alpha}} p_i(Y)\xi^i $  with $p_i(Y)$ an arbitrary element in $\F[Y]$. \qed


Next we turn to the analogous computation for the ring $\Rsigma$ of $\sigma$-fixed points.  We first consider the fixed points in $\F[Y]$.    The case $e_1$ is special in that $\F[Y]e_1=\F e_1$ is fixed by $\sigma$.  If $i\neq 1$ and $e_i$ is fixed by $\sigma$,  then $\langle\sigma\rangle$ is a group of automorphisms of  the field $\F[Y]e_i$ and the fixed field must have codimension 2. The dimension $d_i$ must be even and the fixed field is isomorphic to $GF(2^{d_i/2})$.  For the idempotents that are not fixed, $\sigma$ may be regarded as a ``switching" automorphism that acts on $\F[Y]e_{r+j}\oplus \F[Y]e_{r+j+s}$ by exchanging the summands.  The fixed subring is a diagonal ring isomorphic to $GF(2^{d_{i+r}})$.  Hence the odd part of the unit group of $\Rsigma$ has order
$$
|U(\Rsigma)_{odd}|= \prod_{i=2}^r (2^{d_i/2}-1) \prod_{j=1}^s (2^{d_{r+j}}-1).
$$
The even part of the order is computed in the same way as for $U(R)$. For even $k$, the dimension of  $\Rsigma$ is $1+(k/2)$ and the dimension of the radical of $\Rsigma$ is 
$$\eqalign{
D^{\sigma} &= {k\over 2}+1-\left(d_1+\sum_{i=2}^r {d_i\over 2} + \sum_{j=1}^s d_{r+j}\right)\cr
&={k\over 2}+1-{k_0+1\over 2}= {k-k_0+1\over 2}.\cr}
$$


It follows that the even part of the unit group of $\Rsigma$ has order $2^{D^\sigma}$. 

\proc Theorem \procno.  Let $e_1,\ldots,e_{r+2s}$ be the set of primitive idempotents in  $R_k$ with $\sigma(e_i)=e_i$ for $1\leq i\leq r$ and $\sigma(e_{r+j}) = e_{r+j+s}$ for $1\leq j\leq s$.  Let $d_i$ be the dimension of the field $Re_i/rad(R)e_i$ over $\F$, with the notation chosen so that $d_1=1$. For even $k$, the  $d_2,\ldots,d_r$ are even integers and the  orders of the unit groups $U(R)$ and $U(\Rsigma)$ are
$$\eqalign{
|U(R)|&=2^{k-k_0}\prod_{i=2}^{r+2s} (2^{d_i}-1) ,\cr
|U(\Rsigma)|&= 2^{k-k_0+1\over 2}  \prod_{i=2}^r (2^{d_i/2}-1) \prod_{j=1}^s (2^{d_{r+j}}-1).\cr}
$$
For odd $k$, the above formulas must be modified by removing the initial 2-power factor and retaining the remaining terms.\endproc
\bigskip



\noindent {\bf The distinct $Vu$}
\smallskip
The stabilizer of $V$ is the group  $Stab(V) = \{u\in U(R): Vu=V\}$ of units that leave $V$ invariant. We determine this group in the next result.

\proc Theorem \procno.  Let $k=2^{\alpha}k_0$ with  $k_0$ an odd integer and $\alpha \geq 1$. Then the stabilizer of $V$ is the group
$$
Stab(V)=\cases{U^{\langle\sigma\rangle} & if $\alpha=1$\cr
\langle U^{\langle\sigma\rangle}, 1+(1+Z)e_1\rangle & if $\alpha=2$\cr
\langle U^{\langle\sigma\rangle}, 1+(Z+Z^3+\cdots+Z^{2^{\alpha-1}-1})e_1\rangle & if $\alpha>2.$\cr
}
$$
\endproc

\smallskip
\proc Corollary \procno. The number  $n_{\alpha}$ of distinct codes $Vu$ is
$$
n_{\alpha}=\cases{[U:U^{\langle\sigma\rangle}] & if $\alpha=1$\cr [U:U^{\langle\sigma\rangle}]/2 & if $\alpha \geq 2.$\cr}
$$
\endproc

Proof.    We first show that a unit $u$ lies in  $Stab(V)$  if and only if  $V\cdot Tr(u)=0$.   If $u\in U^{\langle\sigma\rangle}$ then $Tr(u)=0$ and  $Vu=V$ because $V$ is an ideal of $\Rsigma$. Assume $u \not\in \Rsigma$ and $u\in Stab(V)$. Then $w=u+\sigma(u)=Tr(u) \neq 0$.

  For any $v\in V$ we have $c=vu\in V$ so that $c=\sigma(c)=\sigma(vu)$ and so $c=v\sigma(u)$. Taking sums yields 
$$
0 = c+c= vu+v\sigma(u)=v Tr(u)=vw,\quad\hbox{and}\quad Vw=0.
$$
Conversely suppose $u$ is a unit such that $VTr(u)=0$.  Then for any $v\in V$ we have 
$$
v(u+\sigma(u))=0\quad\hbox{and}\quad vu = v\sigma(u) = \sigma(vu).
$$
Thus $vu\in \Rsigma$. Moreover  $\epsilon(vu)=\epsilon(v)\epsilon(u) = 0\cdot 1 = 0$ and so $vu$ has even weight.  Thus $vu \in V$ (by Proposition 2), as required to prove the first point.

For the second step, we determine the possibilities for $w=Tr(u)$ given that $Vw=0$. Assume $w\neq 0$.  Since $X+X^{-1}\in V$, we have $(X+X^{-1})w=0$ and 
$X^2 w= w$. Let
$$
g=1+X^2+X^4+\cdots +X^{k-2},
$$ 
Then $(X+X^{-1})g=0$ and the  annihilator of $V$ is contained in the ideal $Rg$. Thus the
 only  possibilities for $w$ are  the elements in the set $Rg=\{0,g,Xg,g+Xg\}$.
We   exclude $0$ as a possibility. Moreover, since $w=u+\sigma(u)$, the coefficient of 1 in $w$ must equal 0. Thus the only choice is
$$
w=Xg=X+X^3+X^5+\cdots+X^{k-1}.
$$
So  $w$ is unique; we need some of its properties.
The primitive idempotent $e_1=1+Y+Y^2+\cdots+Y^{k_0-1}$ has the property $Ye_1=e_1$.  Let us show 
$$w=(Z+Z^3+\cdots+Z^{2^{\alpha}-1})e_1.$$
 When the right side is expanded, it equals a sum of $2^{\alpha-1}k_0=k/2$ terms $Z^jY^r$ with $j$ an odd integer 
$1\leq j\leq 2^{\alpha}-1$ and $0\leq r<k_0$. Since $w$ is a sum of $k/2$ terms which can be expressed as an odd power of $Z$ times a power of $Y$, equality of the two sums follows.

Thus if $u\in Stab(V)$ but $Tr(u)\neq 0$, we get $Tr(u) \in Re_1$.  The ring $R$ is a direct sum
$$
R=Re_1\oplus R(1+e_1)
$$
of two $\sigma$-invariant subrings and we write $u = ue_1+u(1+e_1) $. It follows that
$$
we_1=Tr(u) = Tr(ue_1)+Tr(u(1+e_1))=Tr(u)e_1+Tr(u)(1+e_1),
$$
from which we conclude $ Tr(u)(1+e_1)=0$. In other words, $u(1+e_1)\in \Rsigma$. It follows that 
$h=e_1+u(1+e_1)$ is a unit in $\Rsigma$.  Now replace $u$ by $uh^{-1}$. 
Since $u$ and $uh^{-1}$ lie in the same coset of $U^{\langle\sigma\rangle}$, we may now assume that
$$
u = ue_1+(1+e_1) .
$$
It is simpler now to work in the ring $Re_1$ because $Re_1 = \F[Z]e_1 \cong \F[Z].$ 
It is necessary to find all units $q \in \F[Z]$ that satisfy 
$$Tr(q) = Z+Z^3+\cdots+Z^{2^{\alpha}-1}.$$
We treat three cases.

Case $\alpha=1$. Here we need $Tr(q)=Z$ but $Z$ is not a trace in $\F[Z]=\F+\F Z$ so there is no solution possible.  

Case $\alpha =2$. This time we need $Tr(q)=Z+Z^3 = Z+Z^{-1}$ with $q$ a unit of $\F[Z]$.  One obvious solution is $q=Z$.   Any other solution must equal $q=Z+c$ where $Tr(c)=0$. Since both $q$ and $Z$ are units of $\F[Z]$, their sum $c=q+Z$ is a nonunit. Thus $c\in V (=Ve_1)$.  Since $Z$ is in the stabilizer of $V$, it follows that $Z^{-1}c \in V$; in particular, $Z^{-1}c$ lies in $\Rsigma$. Thus $Z^{-1}q = 1+Z^{-1}c\in 
U^{\langle\sigma\rangle}$. Hence $q$ and $Z$ lie in the same coset of $U^{\langle\sigma\rangle}$. Returning to the larger ring $R$, the conclusion is that $Ze_1+(1+e_1) =1+(1+Z)e_1$ determines the unique additional coset of $U^{\langle\sigma\rangle}$ in $Stab(V)$.

Case $\alpha>2$. In this case we need $Tr(q) = Z+Z^3+\cdots+Z^{2^{\alpha}-1}$ for a unit $q$ in $\F[Z]$. There is an obvious choice of $q$, namely the sum of the first half of the terms, $Z^i$, for odd $i$ up to $2^{\alpha-1}-1$ except that this sum is not a unit (it has weight $2^{\alpha-2}$). So we add 1 to make it a unit:
$$
q=1+Z+Z^3+\cdots+Z^{2^{\alpha-1}-1}.
$$
This element is a unit because its $2^{\alpha-1}$ power equals 1. Moreover it has the correct trace. Any other unit with the same trace has the form $h=q+c$ with $Tr(c)=0$. By the same argument used in the previous case, $c\in V$ and $q^{-1}c \in V$.  Thus $h$ and $q$ lie in the same coset of $U^{\langle\sigma\rangle}$.
Returning this to the full ring $R$ means that the additional generator for $Stab(V)$ is $qe_1+(1+e_1)=1+(1+q)e_1$ as stated in the conclusion.  \qed



\sec Neighbors of $Vu$.
\vskip1pc
 Let $\C \subset \F^n$ be any self-dual code of length $n$. A {\it neighbor } of $\C$ is a code obtained by starting with some subcode $\H$ of codimension 1 in $\C$ and element $y \in \F^n$ that is not in $\C$  but is orthogonal to $\H$, and forming $\H+\F y$. This is a linear subcode of $\F^n$ and is self-dual if $y$ has even weight.  In  the special case where $\C$ is Type I and $\H$ is the subcode of $\C$ consisting of  all elements with weight divisible by 4, we refer to the neighbors as {\it adjacent codes} of $\C$. 

We describe some neighbors of the self-dual codes
 $Vu$, assuming that $k$ is even.

Let $\SS$ be any subset of $I=\{1,2,\ldots,-1+k/2\}$, allowing the empty set or $\SS = I$.  Let $V_{\SS}$ be the subspace of $V$ with basis $b_i$, $1\leq i <k/2$ defined by
$$
b_i=\cases{f_i& if $i\in \SS$\cr  f_i+f_{k/2}& if $i\not\in \SS$.\cr}
$$
Then clearly $V_{\SS}$ is a subspace of codimension 1 in $V$. We describe two elements orthogonal to $V_{\SS}$ as follows.

Let
$$ y=y_{\SS}=1+\sum_{{\ss 1\leq i < k/2 \atop \ss i \not\in \SS}}X^i
$$
and let $y'_{\SS} = f_{k/2}+y_{\SS}$.

\proc Lemma \procno. The dual of  $V_{\SS}$ equals $V_{\SS}+\F y_{\SS}+\F y'_{\SS}$. \endproc

Proof. Clearly $y\cdot b_i=0$ if $i\in \SS$ because  $b_i=X^i+X^{-i}$ and neither  $X^i$  nor $X^{-i}$ appears in $y$.  If $i\not\in\SS$, then exactly one of the terms $X^i$ and  $X^{-i}$ appears in $y$; in addition 1 appears in $b_i$ and  also in $y$ so that $b_i\cdot y = 1+1=0$.  A similar analysis shows that $y'\cdot b_i=0$ for each $i$. Since $y$ is not in $V$ (1 and $X^{k/2}$ have equal coefficients for every element of $V$) we know by dimension counting that the dual of $V_{\SS}$ is $V+\F y$ which equals $V_{\SS}+\F y_{\SS}+\F y'_{\SS}$.\qed

Now we obtain many self-dual codes.

\proc Theorem \procno. Let $u$ be any unit of $R$ and $\SS \subseteq \{1,2,\ldots,-1+k/2\}$  with $|S| \equiv k/2\!\!\! \pmod 2$.  Then the two codes
$$
V_{\SS,1}[u]=V_{\SS}u +\F y\sigma(u^{-1}) \quad V_{\SS,2}[u]=V_{\SS}u + \F y'\sigma(u^{-1})
$$ are self-dual neighbors of $Vu$.
\endproc

Proof.  Any two elements of $V_{\SS}u$ are orthogonal because $Vu$ is self-orthogonal. For $v\in V_{\SS}$ we have
$$
vu\cdot y\sigma(u^{-1})=vuu^{-1}\cdot y = v\cdot y = 0
$$
because $y$ is orthogonal to $V_{\SS}$. The weight of $y$ is  $k/2 - |S|$, as seen from the definition of $y$. By assumption on $k$ and $|\SS|$,  $k/2-|\SS|$ is even; thus $y\cdot y=0$ and $V_{\SS,1}[u]$ is 
self-dual. Use the analogous argument for the second case.\qed

\bigskip
\noindent {\secfont Code Types}
\medskip
 For a unit $u$ of $R$, we will show that $Vu$ is  self-dual
code of Type I and  investigate some neighbors to get Type II codes in certain cases.
\bigskip
We write an element $u$ in the form
$$
u=\sum_{i=1}^r X^{t_i}\quad\hbox{ with}\quad 0\leq t_1<t_2<\cdots <t_r<k\eqno(4.1)
$$ 
and define $\beta(s)=\beta_u(s)$ to be  the number of pairs $(p,q)$ such that $t_p-t_q \equiv s \pmod k$.



\proc Lemma  \procno. Let $u$ be a unit of $R$ with the form in  Eq.(4.1).  Then  
$$u\sigma(u) = \sum_{s=0}^{k-1} \beta(s)X^s.$$\endproc
\smallskip

[Of course, we view the integer $\beta(s)$ as an element of $\F$ so all that matters  for the representation of $u\sigma(u)$ is the congruence of $\beta(s)$ modulo 2.]

Proof. This is just a restatement of the equation
$$
u\sigma(u) = \sum_i\sum_j X^{t_i-t_j}.\eqno\qed
$$


\proc Lemma \procno. Let $u$ be  a unit of $R$  as in Eq.(4.1) with $\beta(s)$ defined above.  For each $j$, $1\leq j < k/2$,  the weight of $f_j u$ is even and it is divisible by 4
if and only if $\beta(2j)$ is odd.  For $j=k/2$,   $\beta(k/2)$ is even
and $\wt(f_{k/2} u)\equiv 2 \pmod 4$.
\endproc

Proof. First assume $1\leq j<k/2$. Then
$$
f_j u = (X^j+X^{-j})\sum_{i=1}^r X^{t_i}=\sum_{i=1}^r X^{j+t_i}+\sum_{i=1}^r X^{-j+t_i}.
$$
The element $u$ has weight $r$ and the weight of $f_j u$ is $2(r-b)$ where $b$ is the number common terms (powers of $X$)  in the two sums; thus $b$ equals the number 
of ordered pairs $(p,q)$ such that  $j+t_p\equiv -j+t_q \!\! \pmod k$.  In the notation of the previous lemma,  $b=\beta(2j)$ is the number of pairs such that $2j\equiv t_q-t_p\!\! \pmod k$.

We also know that $r=\wt(u)$ must be odd  because $u$ is a unit. 
Hence we see for $1\leq j<k/2$,   that $\wt(f_j u)=2(r-\beta(2j))\equiv 0\!\! \pmod 4$  if and only if $\beta(2j)$  is odd, as required.

For the case $j=k/2$  we make the analogous analysis:
$$
f_{k/2} u = u + X^{k/2}u=\sum_{i=1}^r X^{t_i}+\sum_{i=1}^r X^{t_i+k/2}.
$$
Thus $\wt(f_{k/2}u)= 2(r-\beta(k/2))$.  Here  the number $\beta(k/2)$ is even because $t_i-t_j\equiv k/2 \pmod k$ implies $t_j-t_i\equiv-k/2\equiv k/2 \pmod k$.
Since $(t_i,t_j) \neq
(t_j,t_i)$,  it follows that the number  $\beta(k/2)$,  is even. Hence
 $\wt(f_{k/2} u)\equiv 2 \pmod 4$. \qed
\smallskip
Thus we see that $Vu$  always contains an element of weight congruent to 2 modulo 4.



\proc Corollary \procno. If $k$ is even and  $u$ is any unit of $R$ then $Vu$ is a self-dual code of Type I.
\endproc
\medskip
{\bf Remark:} The fact that $\beta_u(k/2)$ is even for any unit $u$ implies that $N(u)=u\sigma(u)$ has 0 as coefficient of $X^{k/2}$.
\medskip
Now we examine some neighbors  of $Vu$  that  will lead to some Type II codes.
 \medskip

Let $u$ be a unit of $R$ as in Eq. (7) and let $\beta$ be defined as above.  Let 
$$
\SS(u) =\{i : 1\leq i <  k/2\ \ \hbox{and}\ \ \beta(2i) \equiv 1 \pmod 2\}
$$ where the elements of $\SS(u)$ are regarded as integers modulo $k$.  Thus $\SS(u)$ is determined by the even powers of $X$ that have nonzero coefficient in $N(u)$.  In view of  lemma 13, we see that $i\in \SS(u)$ if and only if $\wt(f_i u)$ is divisible by 4.

It is of interest to determine the type of the codes $V_{\SS(u),1}[u]$ and $V_{\SS(u),2}[u]$.  The length of these codes is $k$ and so a code of Type II can occur only when $k$ is a multiple of 8. A relatively small number of examples suggests that this condition may also be sufficient but a  proof of this general statement is lacking at this time.  We give the following partial result supporting the conjecture. 

\proc Theorem \procno. Assume $k$ is divisible by 8.  Let $u$ be a unit of $R$ such that $\SS(u)$ is empty.   Then the codes $V_{\SS(u),1}[u]$ and $V_{\SS(u),2}[u]$ adjacent to $Vu$ are Type II self-dual codes.
\endproc

Proof. The assumption  that $\SS(u)$ is the empty set implies
$$
y_{\SS(u)}=y=\sum_{i=0}^{-1+k/2} X^i.
$$
Now observe that  $(1+X^{k/2})y = \zeta=\sum_{i=0}^{k-1}X^i$. Multiply by $\sigma(u^{-1})$ and use the condition $v\zeta=\wt(v)\zeta$ for any $v\in R$, to get
$$
(1+X^{k/2})y\sigma(u^{-1}) = \zeta \sigma(u^{-1}) = \zeta
$$
and so
$$
(1+X^{k/2})\left(y+y\sigma(u^{-1})\right) =0.
$$
The  set of elements of $R$ that annihilate  the ideal $(1+X^{k/2})R$ equals $(1+X^{k/2})R$;  so we obtain 
$$
y+y\sigma(u^{-1})= (1+X^{k/2})r
$$
for some $r\in R$.  Since $(1+X^{k/2})X^{k/2+j}=(1+X^{k/2})X^{j}$, we may assume that $r$ is a linear combination of powers $X^j$ with $0\leq j<k/2$.
Rewrite the above equation in the form
$$
y\sigma(u^{-1})= y+r+X^{k/2}r
$$
from which we determine the weights as follows.
The element $y$ is a sum of all the powers of $X$ up to the power $-1+k/2$ so adding $r$ cancels some of these terms and $y+r$ has weight $k/2-\wt(r)$. The term $X^{k/2}r$ involves $\wt(r)$ powers of $X$ greater than $-1+k/2$ so $y+r$ and $X^{k/2}r$ have no terms in common; thus
$$
\wt(y\sigma(u^{-1}))=\left({k\over 2}-\wt(r)\right)+\wt(r) = {k\over 2}.
$$
By assumption $k/2$ is divisible by 4 so $\wt(y\sigma(u^{-1})$ is divisible by 4.  The subcode $V_{\SS(u)}u$ has basis $(f_i+f_{k/2})u$, $1\leq i <k/2$ and all these elements have weight divisible by 4. It follows that
 $V_{\SS(u),1}[u]$ is a Type II code.  For the case of $V_{\SS(u),2}[u]$, we notice that $y' = Xy$ and so 
$$
\wt(y'\sigma(u^{-1}) ) = \wt(Xy\sigma(u^{-1}) ) = \wt(y\sigma(u^{-1}) ) ={k\over 2}.
$$
Hence  $V_{\SS(u),2}[u]$ is also Type II.\qed

\proc Corollary \procno. If $k$ is divisible by 8 and $u$ is a unit of $R$ satisfying $N(u)=u\sigma(u)=1$,  then the two codes, $V_{\SS(u),1}[u]$ and  $V_{\SS(u),2}[u]$ adjacent to $Vu$, are Type II self-dual codes.\endproc

Proof.  The condition $N(u)=1$ implies $\SS(u)$ is empty. The previous theorem applies to give the conclusion.\qed

\bigskip
\noindent{\bf Remarks:} We indicate that  many units $u$ can have $\SS(u)=\emptyset $.

\noindent 1.  There are many units satisfying $N(u)=1$. They  form a group of order $4[U:U^{\sigma}]$ which contains a subgroup of index 4 consisting of all elements $w^{-1}\sigma(w)$ for $w\in U$. Since these facts are not need here, proofs will be presented  in  another paper. 


\noindent  2.  There  exist units $u$ such  that  $N(u)\neq 1$ but for which $\SS(u)$ is empty.  For example, let $r$ be a linear combination of odd powers $<k/2$ of $X$ and let $u=1+r(1+X^{k/2})$. Then $u^2=1$ so $u$ is a unit and $N(u)=1+(r+\sigma(r))(1+X^{k/2})$ which need not be equal to 1. Since no even powers of $X$ appear in $(r+\sigma(r))(1+X^{k/2})$ with nonzero coefficient, $\SS(u)$ is empty.

\bigskip



\sec Examples.
\medskip
Here are the results of some computer computations for lengths $k=32, 34, 36, 38$.
\medskip
{\secfont Length 32} 
\medskip All extremal codes of length 32 are known by [CS] but the self-dual Type I codes of this length have not yet been classified.  We find at least 13 inequivalent codes $Vu$ with parameters $[32,16,6]$. There are  three possible weight enumerators:
\medskip
\item{1.} $1 + 16\,T^6 + 332\,T^8 + 
    2000\,T^{10} + 6848\,T^{12} + 14368\,T^{14} + 18406\,T^{16} + \cdots$
\smallskip
\item{2.} $1 + 24\,T^6 + 316\,T^8 + 1976\,T^{10} + 6912\,T^{12} + 14384\,T^{14} + 18310\,T^{16} + \cdots$
\smallskip
\item{3.} $1 + 32\,T^6 + 300\,T^8 + 1952\,T^{10} + 
    6976\,T^{12} + 14400\,T^{14} + 18214\,T^{16} +\cdots$.
\medskip
There are at least 2 inequivalent codes $Vu$ with weight enumerator (1); one such unit is $u= X^{11} + X^{10} + X^{9} + X^{8} + X^{7} + X^{4} + X^2 + X + 1$.

There are at least 4 inequivalent codes $Vu$ with weight enumerator (2); one such unit is $u=X^{12} + X^{11} + X^{10} + X^9 + X^5 + X + 1$.

There are at least 7 inequivalent codes $Vu$ with weight enumerator  (3); one such unit is $u= X^{12} + X^8 + X^5 + X + 1$.
\medskip

{\secfont Length 34}
\vskip8pt


  We consider self-dual codes of length $k=34$ having the maximum possible minimum distance, 6. According to the results of Conway and Sloane [ CS], the weight enumerator of a $[34,17,6]$ self-dual code is one of the following:

\item{(1)} $ W(T)=1+6T^6+411T^8+1165T^{10}+10886T^{12}+\cdots$
\item{(2)}  $W_{\beta}(T)=1+(34-4\beta)T^6+(255+4\beta)T^8 +(1921+20\beta)T^{10}+\cdots$.

Codes corresponding to (1) and (2) with $\beta=3$ are listed  in [CS] as ``having no known structure" meaning that they were found by a (more or less) random search. They also give a code corresponding to (2) 
 with     $\beta=0$, and assert the existence of codes for all $\beta$ in the range $0\leq \beta\leq 7$.  

None of the codes $Vu$ have  weight enumerator (1),  but all of the weight enumerators $W_{\beta}(T)$, (2) for $0\leq \beta\leq 7$, correspond to some (in most cases several) of the $Vu$. Only the weight enumerator $W_{0}(T)$ corresponds to a unique equivalence class of codes of the form $Vu$. In the other cases, the exact number of inequivalent codes was not determined mainly because verifying the equivalence of codes is a slow process on my computer using MAGMA. Instead of determining equivalence, we used a weaker relation. To  each code $\C$, a signature $sg(\C)$  is attached  having the property that if $\C$ and $\D$ are equivalent, then $sg(\C)=sg(\D)$. The table below indicates the number of codes having different signatures.  The signature of a code $\C$ is computed as follows.  For each coordinate $i$ let $g_i(T)$ be the covering polynomial
$$
g_i(T)=\sum_{\ss c\in \C\atop\ss i <c}T^{wt(c)-1}
$$
as studied in [J]. Here $i<c$ means that the codeword $c$ has a  1
in the $i^{th}$ coordinate. The set 
${\cal G}=\{g_1(T),\ldots,g_{34}(T)\}$ is invariant under a  
permutation of coordinates and is the same for two equivalent
codes.  If the set has $h$ distinct polynomials
$g_{i_1},\ldots,g_{i_h}$, the signature of the  code is a vector
$[a_1,\ldots,a_h]$ of positive integers such that 
$a_r$ elements of $\cal G$ equal $g_{i_r}$.  The signature  of
two codes can be computed in less than (roughly) $1/10^{th}$ of
the time required to determine the equivalence of two codes. In the
following table we give the number of codes having different
signatures. It is possible that two codes with the same signature
might  be inequivalent.
\def\tablerule{\hbox to \hsize{\hrulefill}}
\setbox0=\vbox{\hsize=4truein
\halign{\hfil\qquad#\qquad\hfil&\hfil\quad#\quad\hfil&\hfil\quad#\quad\hfil\cr
\noalign{\hfil Codes $Vu \sim [34,17,6]$\hfil}
\noalign{\tablerule}
$\beta$&\# inequiv. $Vu$ is $\geq$&sample $u$\cr
\noalign{\tablerule}
0&1&6079224421\cr
\noalign{\tablerule}
1&2 &16741490086\cr
\noalign{\tablerule}
2&4&7077887398\cr
\noalign{\tablerule}
3&12&10935757472\cr
\noalign{\tablerule}
4&17&13863006831\cr
\noalign{\tablerule}
5&21&9933424451\cr
\noalign{\tablerule}
6&19&13875327693\cr
\noalign{\tablerule}
7&2&9813101373\cr
\noalign{\tablerule}
}}
\vskip1pc
\centerline{\box0}
\vskip1pc
The column of sample units gives one unit for each indicated weight enumerator. To obtain the unit from the integer $n$ that appears, express $n$ as a sum of distinct powers of 2 and then replace the 2 by $X$.

\vskip1pc
{\secfont Length 36}
\vskip8pt
Now consider the case $k=36$. An extremal code of length 36 is a self-dual code with parameters $[36,18,8]$; in [CS] it is shown that such a code can have one of the two weight enumerators
\medskip
\item{1.} $W_1(T)=1+225T^8+2016T^{10}+9555T^{12}+28800T^{14}+55755T^{16} + 69440T^{18}+\cdots$
\item{2.} $W_2(T)= 1+289T^8+1632T^{10}+10387T^{12}+28288T^{14}+\cdots$.
\medskip
Conway and Sloane assert that there are at least 2 inequivalent $[36,18,8]$ codes.
They give one example of a code with each weight enumerator; the code with weight enumerator $W_2(T)$ is a double circulant whereas the code given with weight enumerator $W_1(T)$ is listed as having ``no known structure".  

We find exactly three inequivalent codes $Vu$ with minimum distance 8; each has weight enumerator 
$W_1(T)$. The codes are the $Vu_i$  corresponding to the three units
$$
\eqalign{
u_1&= X^{29}+ X^{27} + X^{23} + X^{21} + X^{20} + X^{19} + X^{17} + X^{16} + X^{13} +
 X^{9} +  X^{8} + X^{5} + 1\cr
u_2&=X^{27} + X^{25} + X^{21} + X^{19} + X^{17} + X^{15} + X^{14} + X^{12} + X^{10} + 
X^{7} + X^3 + X^2 + 1\cr
u_3&=X^{26} + X^{23} + X^{22} + X^{19} + X^{18} + X^{16} + X^{14} + X^{11} + X^8 + X^6 + X^3 + X^2 + 1.\cr
}
$$ 
Each $Vu_i$ has an automorphism group that is transitive on the 36 coordinates; the respective orders of the automorphism groups are 36, 288, and 36.
\vskip1pc
{\secfont Length 38}
\vskip8pt

In [CS], two extremal codes are presented with parameters $[38,19,8]$; one is a double circulant with weight enumerator
$$
W(T)=1+171T^8+1862T^{10}+10374T^{12}+ 36765T^{14} + 84759T^{16} + 128212T^{18} +\cdots
$$
and the other has weight enumerator $1+203T^8+1702T^{10}+\cdots$. None of the $Vu$ codes for $k=38$ have this latter weight enumerator.  There are exactly 2  inequivalent codes $Vu_i$ with weight enumerator $W(T)$ corresponding to the units
$$\eqalign{
u_1&=X^{30} + X^{28} + X^{27} + X^{26} + X^{25} + X^{23} + X^{22} + X^{19} + X^{18} + X^{16} + X^{15} +\cr
   &\qquad  X^{14} + X^{11} + X^{8} + X^{6} + X^{5} + X^{2} + 1\cr
u_2&=X^{34} + X^{32} + X^{30} + X^{29} + X^{26} + X^{24} + X^{22} + X^{20} + X^{19} + X^{16} + X^{15} +\cr
    &\qquad X^{13} + X^{10} + X^{9} + X^{6} + X^{4} + X^{3} + 1.\cr}
$$
The code $Vu_1$ has automorphism group of order 6; the code $Vu_2$ has automorphism group of order  342 which has normal subgroup of order 19. Each element of order 19 is the product of two cycles of length 19. When we use the canonical basis $\{X^i\}$, $1\leq i \leq 38$, the two sets consisting of the elements 
$X^i$ with $i$ odd and with $i$ even are either preserved or exchanged by all automorphisms of $Vu_2$.
\medskip
{\secfont Conclusion}
\smallskip 
There are obviously many classes of the $Vu$ codes that merit
further investigation.  The main obstacle is computing time; in all
the examples above, a subset of the full set of representatives of the
cosets of $Stab(V)$ in $U(R)$  was parameterized and each $Vu$
tested.   The number of units to be tested is (a bit less than) $2^{k/2
-1}$ and then the codes produced must be tested for equivalence. 
As $k$ increases, the number of tests grows exponentially so some
further reductions in the number of cases must be made. We have
not given examples to produce Type II codes by the neighbor
construction nor examples of codes  
$(Vu)^{\dagger}$ obtained by extending a code $Vu$ using  an
odd value of $k$.  Such examples will  be investigated in work 
currently in progress.

\vskip6pc
\centerline{\secfont References}
\vskip1pc
{\parindent 2pc

\item{[CS]} J.H. Conway and N.J.A. Sloane {\it A new upper 
bound on the minimal distance of self-dual codes}, IEEE Trans.
Info. Th., v.36 (1990)1319-1333.
\medskip

\item{[J]} G.J. Janusz {\it Overlap and covering polynomials 
with applications to designs and self-dual codes},  SIAM J. Disc.
Math., v.13, No.2, (2000)154-178.
\medskip}

\item{[MS]} F.J. MacWilliams and N.J.A. Sloane, {\it The 
Theory of Error Correcting Codes}, Elsevier Publishers,
Amsterdam, (1993).



\bye