\documentclass[12pt]{article}

\def\bFq{{\mathbb F}_q}
\def\P{{\mathbb P}}
\def\X{{\cal X}}
\newcommand\bA{\mathbb A}
\newcommand\bF{\mathbb F}
\newcommand\bZ{\mathbb Z}
\renewcommand\a{\alpha}
\newtheorem{proposition}{Proposition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\usepackage{amssymb,epsfig,amscd}


\begin{document}


\title{On a key equation and error evaluation 
for codes from order domains}

\author{John B. Little\\
Department of Mathematics and Computer Science, \\
College of the Holy Cross,\\
Worcester, MA 01610, USA\\
E-mail: little@mathcs.holycross.edu}
\maketitle

The Berlekamp-Massey decoding algorithm for a Reed-Solomon code 
can be phrased as a method for solving the {\it key equation}
\begin{equation}
f S \equiv g \bmod \langle X^{2t}\rangle.\label{jbl:RSkeyeq}
\end{equation}
Here $S$ is the known univariate syndrome polynomial in $X$, 
and the error locator $f$ and error evaluator $g$ are 
unknown polynomials in $X$.

We identify an algebraic context for related key equations in the theory of
Macaulay's {\it inverse systems}, \cite{Maca16, North74}, 
and develop an analog of (\ref{jbl:RSkeyeq}) 
for codes from  order domains (\cite{HPvL98,OSul01a,GePe02,Litt07}).
We also relate O'Sullivan's general version of the Berlkamp-Massey-Sakata
(BMS) algorithm from \cite{OSul01b} to the process of solving 
this equation.  The key equation for 
$n$-dimensional cyclic codes studied by Chabanne and Norton,  
\cite{ChNo94,Norto95}, is a special case.  Althaler and D\"ur, \cite{AlDu96},
consider a form of (\ref{jbl:RSkeyeq}) from our point of view.
This note is a summary of the results of \cite{Litt03}
to which we refer for proofs.
 
\subsection*{Codes from order domains}
\label{jbl:codes}
A fundamental theorem of Geil and Pellikaan, \cite{GePe02},
shows that order domains all have presentations as
affine algebras $R \cong \bF_q[x_1,\ldots,x_s]/I$ where
$I$ is an ideal generated by a Gr\"obner basis with a 
very specific form.  We write $X_R = {\cal V}(I)$ for the 
corresponding algebraic variety.  
The value semigroup $\Gamma$ and the weight function $\rho: R \to \Gamma$
are defined using a suitable monomial 
order.  In this note, we will assume that $\Gamma$ 
can be put into order-preserving one-to-one correspondence 
with $\bZ_{\ge 0}$.  Such $\Gamma$ are said to be
{\it Archimedean} because
it follows that for all nonconstant $f \in R$ and all $g \in R$
there is some $n \ge 1$ such that $\rho(f^n) \succ \rho(g)$.
Let $\Delta$ be the ordered ``footprint'' basis of $R$
with ordering by $\rho$-value.  Let $\ell \in {\mathbb N}$ and 
let $V_\ell$ be the span of the first
$\ell$ elements of $\Delta$. 
In this way, we obtain evaluation
codes $Ev_\ell = ev(V_\ell)$ defined on $X_R(\bF_q)$
and dual codes $C_\ell = Ev_\ell^\perp$
for all $\ell$.
\subsection*{Inverse systems}\label{jbl:invsys}
Let $k$ be a field, let $S = k[X_1,\ldots,X_s]$ and
let $T$ be the formal power series ring $k[[X_1^{-1},\ldots,X_s^{-1}]]$
in the inverse variables.  $T$ is an $S$-module
under the {\it contraction} mapping $c : (f,g) \mapsto f\cdot g$
defined as follows.  First, given monomials
$X^\a$ in $S$ and $X^{-\beta}$ in $T$, 
$X^\a \cdot X^{-\beta}$ is defined to be $X^{\a-\beta}$ 
if this is in $T$, and $0$ otherwise.  We then extend by linearity 
to define $c : S\times T \to T$.

Let $Hom_k(S,k)$ be the dual vector space, which
is an $S$-module under $q\Lambda(p) = \Lambda(qp)$ for $p,q \in S$.
$Hom_k(S,k)$ and $T$ are isomorphic as $S$-modules via
$
\Lambda \leftrightarrow \sum_{\beta\in \bZ_{\ge 0}^s} \Lambda(X^\beta) X^{-\beta};
$
see \cite{North74} for more details.

For each ideal $I\subseteq S$, the annihilator,
or {\it inverse system}, of $I$ is
\[
I^\perp = \{\Lambda \in T : \Lambda(p) = 0,\ \forall\  p \in I\},
\]
an $S$-submodule of $T$.
Similarly, given an $S$-submodule $H \subseteq T$,
\[
H^\perp = \{p \in S : \Lambda(p) = 0,\ \forall\ \Lambda \in H\},
\]
an ideal in $S$.  The ideals of $S$ and the $S$-submodules
of $T$ are in inclusion-reversing
bijective correspondence,  and for all $I, H$ we have
$(I^\perp)^\perp = I$ and $(H^\perp)^\perp = H$.

\begin{theorem}\label{jbl:duality}
If $m_P$ is the maximal ideal of a point in affine space, 
then $(m_P)^\perp$ is generated by
$h_P = \sum_{u\in \bZ_{\ge 0}^s} P^u X^{-u}$.
For all $f\in S$, $f\cdot h_P = f(P)h_P$,
and the submodule $(m_P)^\perp$ is a one-dimensional vector space over $k$.
If $I = m_{P_1}\cap \cdots \cap m_{P_\ell}$, then 
$I^\perp = \oplus (m_{P_i})^\perp$ is generated by $\sum_i h_{P_i}$.
\end{theorem}

Both $S$ and $T$ are subrings of 
$K = k((X_1^{-1}, \ldots, X_s^{-1})),$
the field of fractions of $T$.  The full product
$fg$ for $f \in S$ and $g \in T$ is an element of $K$.  
The contraction product $f\cdot g$ is a projection of $fg$ into
$T \subset K$.  We can also consider the projection of $fg$ into 
$S_+ = \langle X_1,\ldots, X_s\rangle \subset S\subset K$.
We will denote this by $(fg)_+$.  
\subsection*{The key equation and the
BMS algorithm}\label{jbl:kebms}
Let $C_\ell$ be a dual evaluation code from an order domain $R$.  
Consider an error vector $e \in \bF_q^n$. 
If ${\cal E}$ is the support of the error, then we define
$$
I_{\cal E} = \{ f \in \bF_q[X_1,\ldots,X_s] : f(P) = 0,\ \forall P \in {\cal E}\}.
$$
For each monomial $X^u \in \bF_q[X_1,\ldots,X_s]$, the error syndrome is
\begin{equation}
E_u = \langle e, ev(X^u)\rangle = \sum_{P\in X_R(\bF_q)} e_P P^u.
\label{jbl:syn}
\end{equation}
Generalizing \cite{ChNo94}, we define the {\it syndrome series}
$$
{\mathcal S}_e = \sum_{u\in \bZ_{\ge 0}^s} E_u X^{-u}
\in T = \bF_q[[X_1^{-1},\ldots,X_s^{-1}]] \cong Hom_{\bF_q} (S,\bF_q).
$$

We substitute from (\ref{jbl:syn}) for the syndrome $E_u$ and 
change the order of summation to obtain:
\begin{equation}\label{jbl:syneq}
{\mathcal S}_e = \sum_{u\in \bZ_{\ge 0}^n} E_u X^{-u}
= \sum_{P\in X_R(\bF_q)} e_P \sum_{u\in \bZ_{\ge 0}^n} P^u X^{-u}
= \sum_{P\in X_R(\bF_q)} e_P h_P,
\end{equation}
where $h_P$ is the generator of $(m_P)^\perp$ from Theorem~\ref{jbl:duality}.

\begin{theorem}\label{jbl:mainth}
For each $e$ with $supp(e) = {\mathcal E}$, 
$I_{\mathcal E} = \langle {\mathcal S}_e\rangle^\perp$.
\end{theorem}

In other words, $f \in I_{\mathcal E}$ if and only if $f\cdot {\mathcal S}_e=0$ for
all error vectors $e$ with $supp(e) = {\mathcal E}$.
This result is a restatement of the standard fact
that the error locators give recurrences on the syndromes.
Let $f = \sum_m f_m X^m \in S$.  Then 
$$
f\cdot {\mathcal S}_e = (\sum_m f_m X^m)\cdot (\sum_{u\in \bZ_{\ge 0}^s} E_u X^{-u})
          = \sum_{r\in \bZ_{\ge 0}^s} (\sum_m f_m E_{m+r}) X^{-r}. 
$$
Hence $f\cdot {\mathcal S}_e = 0 \Leftrightarrow \sum_m f_m E_{m+r} = 0$
for all $r \ge 0$.

The equation $f\cdot {\mathcal S}_e = 0$ for $f \in I_{\cal E}$
will be called the general \emph{key equation}. In \cite{Litt03} it is
shown how this relates to known key equations for various classes of codes.  
Truncating ${\mathcal S}_e$, we could obtain
a congruence similar to (\ref{jbl:RSkeyeq}) involving only known 
syndromes (see the discussion following
(\ref{jbl:trunc}) below).  
The way to obtain error evaluators in this situation is to consider 
the ``purely positive parts'' $(f{\mathcal S}_e)_+$ for certain
solutions $f$ of our key equation.  
 
To relate solutions of 
our key equation and the BMS algorithm,
we refer to the {\it ``Basic Algorithm''} from \S 3 of \cite{OSul01b}, 
in which all needed syndromes are assumed known and no 
stopping criteria are specified.  The 
{\it syndrome mapping} is 
defined by $Syn_e(f) = \sum_{P\in {\cal E}} e_P f(P)$
where $f \in R$.
The proof of our Theorem~\ref{jbl:mainth} also
shows
$f \in I_{\mathcal E} \Leftrightarrow Syn_e(fg) = 0, \forall g \in R.$

From Geil and Pellikaan's presentation
theorem, we have the ordered monomial basis 
$\Delta = \{X^{\a(j)} : j \in {\mathbb N}\}$
of $R$.  The
$V_\ell = {\rm Span}\{X^{\a(j)} : j \le \ell\}$
exhaust $R$, so for $f\ne 0\in R$, we may define
$o(f) = \min \{\ell : f \in V_\ell\}$.
This induces a (nonstandard) semigroup 
operation on ${\mathbb N}$ defined by
$
i\oplus j = k \Leftrightarrow o(X^{\a(i)}X^{\a(j)})=k$.
Given $f\in R$, one defines
\begin{eqnarray*}
span(f) &=& \min\{\ell : \exists g \in V_\ell\ s.t.\ Syn_e(fg) \ne 0\}\\
fail(f) &=& o(f)\oplus span(f),
\end{eqnarray*}
so $f\in I_{\mathcal E} \Leftrightarrow span(f) = fail(f) = \infty$.

The $m$th iteration of the BMS algorithm produces a collection of 
polynomials $F_m$ satisfying $fail(f) > m$.  

\begin{theorem}
\label{jbl:keyeq}
With all notation as above,
suppose $f\in R$ satisfies $o(f) = s$, $fail(f) > m$.  Then
$$f\cdot {\mathcal S}_e \equiv 0 \bmod W_{s,m},$$
where $W_{s,m} = {\rm Span}\{ X^{-\a(j)} : s \oplus j > m\} \subset T$.
\end{theorem}

The subspace $W_{s,m}$ depends on $s=o(f)$.  In our
situation, though, note that if $s' = \max\{o(f) : f \in F_m\}$, 
then Theorem~\ref{jbl:keyeq} implies
\begin{equation}\label{jbl:trunc}
f \cdot {\mathcal S}_e \equiv 0 \bmod W_{s',m}
\end{equation}
for all $f = f_m(s)$ in $F_m$.  Moreover, only finitely
many terms from ${\mathcal S}_e$ enter into any one of these
congruences, so (\ref{jbl:trunc}) is, in effect,
a sort of general analog of (\ref{jbl:RSkeyeq}).  Moreover, 
as is well-known, BMS produces a Gr\"obner basis for $I_{\cal E}$.  

In \cite{Litt03} it is shown that univariate error locators
and evaluators can be produced as in \cite{ChNo94}.  
Moreover, O'Sullivan has shown in \cite{OSul02} that, for codes from curves, 
the BMS algorithm can be slightly modified to compute more useful error 
locators and error evaluators simultaneously.  We conjecture that
the same is true in our general setting.  
      
\small 
\begin{thebibliography}{12}

\bibitem{AlDu96} 
J. Althaler and A. D\"ur,
Finite linear recurring sequences and homogeneous ideals,
{\em Appl. Algebra. Engrg. Comm. Comput.}
{\bf 7}
(1996),
377-390.

\bibitem{ChNo94}
H. Chabanne and G. Norton,
The $n$-dimensional key equation and a decoding application,
{\em IEEE Trans. Inform Theory}
{\bf 40}
(1994),
200-203.

\bibitem{GePe02}
O. Geil and R. Pellikaan,
On the Structure of Order Domains,
{\em Finite Fields Appl.}
{\bf 8}
(2002),
369-396.

\bibitem{HPvL98}
T. H\o holdt, R. Pellikaan, and J. van Lint,
Algebraic Geometry Codes,
in: {\it Handbook of Coding Theory},
W. Huffman and V. Pless, eds.
(Elsevier, Amsterdam, 1998), 
871-962.

\bibitem{Litt03}
J. Little,
A key equation and the computation of error values
for codes from order domains,
{\em preprint},
ArXiv: math.AC/0303299.

\bibitem{Litt07}
J. Little,
The Ubiquity of Order Domains for the Construction of 
Error Control Codes,
{\em Advances in Mathematics of Communications}
{\bf 1}
(2007),
151-171.

\bibitem{Maca16}
F.S. Macaulay,
{\it Algebraic Theory of Modular Systems},
Cambridge Tracts in Mathematics and Mathematical 
Physics, v. 19,
(Cambridge University Press, Cambridge, UK, 1916)

\bibitem{North74}
D.G. Northcott, 
Injective envelopes and inverse polynomials,
{\em J. London Math. Soc. (2)}
{\bf 8} 
(1974), 
290-296.

\bibitem{Norto95}
G.H. Norton, 
On $n$-dimensional Sequences. I, II,
{\em J. Symbolic Comput.}
{\bf 20}
(1995), 
71-92, 769-770.

\bibitem{OSul01a}
M. O'Sullivan,
New Codes for the Berlekamp-Massey-Sakata Algorithm,
{\em Finite Fields Appl.}
{\bf 7}
(2001),
293-317.

\bibitem{OSul01b}
M. O'Sullivan,
A Generalization of the Berlekamp-Massey-Sakata Algorithm,
preprint, 2001.

\bibitem{OSul02}
M. O'Sullivan,
The key equation for one-point codes and efficient
error evaluation, 
{\em J. Pure Appl. Algebra}
{\bf 169}
(2002),
295-320.
\end{thebibliography}
\end{document}
