\documentclass[a4paper]{article}
\usepackage{amssymb}
%\pagestyle{empty}

%\usepackage{type1cm,times,mathptmx}
%\usepackage[dvips, a4paper, bookmarks, bookmarksopen, pdfstartview={FitBH -32768}, pdftitle={On construction and generalization of algebraic geometry codes}, pdfauthor={Ryutaroh Matsumoto and Shinji Miura}]{hyperref}

\newtheorem{proposition}{Proposition}[section]
\newtheorem{theorem}[proposition]{Theorem}
\newtheorem{lemma}[proposition]{Lemma}
\newtheorem{definition}[proposition]{Definition}
\newtheorem{example}[proposition]{Example}
\newtheorem{remark}[proposition]{Remark}
\newtheorem{corollary}[proposition]{Corollary}

\newcommand{\qed}{\hspace*{\fill}\rule{1.3ex}{1.3ex}}
\hyphenation{IEICE}

\title{On construction and generalization of\\
algebraic
geometry codes\thanks{%
This paper appeared in the Proceedings of
Algebraic Geometry,
Number Theory, Coding Theory
and Cryptography, University of Tokyo,
Tokyo, Japan, January 19--20, 2000
(ed.\ T. Katsura et~al.), pp.~3--15.
The proceedings was published July 2000.}}
\author{Ryutaroh Matsumoto\thanks{He is supported by
JSPS Research Fellowships for Young Scientists.}\\
Department of Electrical and Electronic Engineering,\\
Tokyo Institute of Technology, 152-8552 Japan\\
Email: ryutaroh@ss.titech.ac.jp\vspace{3mm}\\
\vspace{3mm}and\\
Shinji Miura\\
SONY Corporation\\
Information and Network Technologies Laboratories\\
Japan\\
Email: miura@av.crl.sony.co.jp}
\date{March 4, 2000}

%\renewcommand{\baselinestretch}{2}

\begin{document}
\maketitle
\begin{abstract}
The construction, estimation of minimum distance,
and decoding algorithms of algebraic geometry codes
can be explained without using
advanced mathematics by the notion of weight domains.
We clarify the relation between algebraic geometry codes
and linear codes from weight domains.
Then we review a systematic construction which
yields all weight domains.
\end{abstract}
%\thispagestyle{empty}
\section{Introduction}
Algebraic geometry codes were defined in an algebraic geometric way,
and many facts about them, in particular estimation of minimum distance
and decoding algorithms, are also stated and proved algebraic
geometrically. So it had been difficult to understand
algebraic geometry codes without the theory of algebraic curves.
Recently H\o holdt et~al.\  \cite{hoholdt97,hoholdt98}
observed that
definition, estimation of minimum distance,
and decoding algorithms of algebraic geometry codes
could be explained using only
the notion of a weight function,
which is essentially a discrete valuation,
and made understanding of algebraic geometry codes much easier.
First we survey the construction of linear codes
with weight functions.

Linear codes obtained with weight functions
are generalization of so-called one-point algebraic geometry codes.
Next we survey a characterization of linear codes from weight functions
and their comparison to the ordinary one-point AG codes.

We construct linear codes from a commutative ring equipped with
a weight function, which we call a weight domain.
Finally we survey a systematic construction which
yields all weight domains.

We omit proofs of assertions and refer the reader to appropriate
literatures when they are available in English.

\section{Evaluation codes and weight functions}
\subsection{Definition of evaluation codes}
Throughout this paper $K$ denotes a fixed finite field,
and $\mathbf{N}_0$ the set of nonnegative integers.
$R$ denotes a commutative $K$-algebra,
and $n$ a positive integer in this section.
\begin{definition}\label{weightdef}\textup{\cite[Definition 3.5]{hoholdt98}}
A function $\rho : R \rightarrow \mathbf{N}_0
\cup \{-\infty\}$ is said to
be a \emph{weight function on $R$}
if
\begin{enumerate}
\item $\rho(f) = -\infty$ iff $f=0$.
\item $\rho(cf) = \rho(f)$ for all nonzero $c \in K$.
\item $\rho(f+g) \leq \max\{\rho(f),\rho(g)\}$ and
the equality holds if $\rho(f) \neq \rho(g)$.
\item If $\rho(f) = \rho(g) \neq - \infty$,
then there exists $c \in K$ such that
$\rho(f -cg) < \rho(g)$.
\item $\rho(fg) = \rho(f) + \rho(g)$,
where the sum of an integer and $-\infty$ is $-\infty$.
\end{enumerate}
\end{definition}

\begin{remark}
A weight function is a generalization
of the degree of univariate polynomials.
\end{remark}

If $R$ is a $K$-algebra with a weight function $\rho$,
then there exists a $K$-basis
$\{f_1$, $f_2$, \ldots $\}$ such that
$\rho(f_i) < \rho(f_{i+1})$ for all $i$
\cite[Proposition 3.12]{hoholdt98}.
We regard the set $K^n$ consisting of
$n$-tuples of elements in $K$ as a commutative ring
with the componentwise addition and multiplication.
Let $\varphi : R \rightarrow K^n$
be an epimorphism of $K$-algebras.
For a positive integer $\ell$,
we define the \emph{evaluation code $E_\ell \subset K^n$}
by the linear space spanned by
$\varphi(f_1)$, \ldots, $\varphi(f_\ell)$,
and its dual code $C_\ell$.

Let $F/K$ be an algebraic function field of one variable
\cite{bn:stichtenoth},
$Q$ a place of degree one of $F/K$,
$v_Q$ the discrete valuation at $Q$,
and $\mathcal{L}(\infty Q) = \bigcup_{i=0}^\infty
\mathcal{L}(iQ)$.
Then $-v_Q$ is a weight function on the ring $\mathcal{L}(\infty Q)$.
Let $P_1$, \ldots, $P_n$ be pairwise distinct places of degree one,
and $\varphi : \mathcal{L}(\infty Q) \rightarrow K^n$,
$f \mapsto (f(P_1)$, \ldots, $f(P_n))$.
Then $\varphi$ is an epimorphism of $K$-algebras,
$E_\ell$ is a functional one-point algebraic geometry code,
and $C_\ell$ is a residual one.

Let $g = \sharp \{ m \in \mathbf{N}_0 \mid$
there is no $f \in R$ such that $\rho(f) = m \}$.
By elementary arguments
we can show that $E_\ell$ is an $[n,\ell,d]$ code
such that $d \geq n+1-\ell-g$ if $\rho(f_\ell) < n$
\cite[Corollary 5.19]{hoholdt98}, and
the minimum distance of $C_\ell$ is at least
$\ell + 1 - g$ \cite[Theorem 5.24]{hoholdt98}.
They correspond to the Goppa bound for the minimum distance
of algebraic geometry codes.

\subsection{Relation between an evaluation code
and a one-point AG code}
It is interesting what we can say about a
ring with a weight function. The following is known.
\begin{theorem}\textup{\cite{matsumoto99weight}}
Let $R$ be a $K$-algebra with a weight function $\rho$
and $R \neq K$.
Then there exist an algebraic function field $F/K$,
its place $Q$ of degree one,
and a positive integer e
such that $F$ is the quotient field of $R$,
$R \subseteq \mathcal{L}(\infty Q) = \bigcup_{i=0}^\infty
\mathcal{L}(iQ)$, and
$\rho = -e \times v_Q$.
In other words,
there exist a projective algebraic curve $\chi$ defined over $K$
and a $K$-rational point $Q \in \chi$
such that $R$ is the ring of $K$-rational functions
regular at $\chi \setminus \{Q\}$
and $\rho$ is a multiple of the pole order of rational functions
at $Q$.
In particular,
$R$ is finitely generated over $K$,
and is an integral domain.
\end{theorem}
Hereafter we call a $K$-algebra with a weight function
a \emph{weight domain}.

Evaluation codes and their duals are generalization
of one-point AG codes.
It is interesting whether we can obtain a good linear code
as (the dual of) an evaluation code
that is never obtained as a one-point AG code.
Suppose that $R$ is a weight domain with a weight function $\rho$.
If $R$ is integrally closed,
then the evaluation code $E_\ell$ and its dual $C_\ell$
can be obtained as one-point AG codes.
Thus to compare evaluation codes and ordinary AG codes,
it is enough to compare evaluation codes (and its duals)
on $R$ with evaluation codes (and its duals) on the normalization
of $R$.
It is shown that
we cannot obtain an evaluation code on $R$ better than that
on the normalization of $R$ \cite{matsumoto98b}.
For precise statements, see \cite{matsumoto98b}.

\section{Construction of weight domains}
\subsection{Construction of general weight domains}\label{generalweight}
In this section,
we review a class of defining equations which yields
all weight domains.
The results in this section were already shown in
\cite{miurathesis,miura98b,pellikaanorder},
and they were in part shown in the earlier paper \cite{miura94}.
But our proofs are new and simpler than the original given
in \cite{miurathesis,miura98b}
and similar to the proofs in \cite{pellikaanorder}.
The second author proved his results \cite{miurathesis,miura98b}
using the theory of algebraic function fields \cite{bn:stichtenoth},
while we prove all the results in an elementary way.
Note that the second author did not know the notion of weight domains
and he did not state facts in his papers
\cite{miura94,miurathesis,miura98b}
in the framework of the weight domain.

Let $H$ be a subsemigroup of $\mathbf{N}_0$.
We call $\{ \rho(f) \mid 0\neq f \in R\}$
the \emph{associated semigroup}
of a weight domain $R$ with a weight function $\rho$.
We shall consider a weight domain $R$ with the
associated semigroup $H$.

\begin{lemma}
If $H=\{0\}$ then $R=K$.
\end{lemma}
\noindent\emph{Proof.}
Let $x \in R$ and $\rho(x) = 0$.
By the condition 4 in Definition \ref{weightdef},
there exists $c \in K$ such that $\rho(x - c) = -\infty$,
which implies $x = c$. \qed

So we assume that $H \neq \{0\}$.
$\mathbf{N}_0 \setminus H$ is finite iff the greatest common divisor
of $H$ is $1$ \cite[Corollary 5.12]{hoholdt98}.
$\rho / \gcd(H)$ is also a weight function on $R$.
So we may assume without loss of generality
that $\mathbf{N}_0 \setminus H$ is finite
by replacing $\rho$ with $\rho/\gcd(H)$ if necessary.
If $H = \mathbf{N}_0$ then $R$ is the univariate polynomial ring
over $K$ \cite{matsumoto99weight}. So hereafter we also assume
that $H \neq \mathbf{N}_0$.

Suppose that $A_t = \{a_1$, \ldots, $a_t\}$ is a generating set
of $H$ and $a_i \neq 0$ for $i=1$, \ldots, $t$.
We shall introduce a monomial order induced from $A_t$.
\begin{definition}
For $(m_1$, \ldots, $m_t)$, $(n_1$, \ldots, $n_t) \in
\mathbf{N}_0^t$,
we define $(m_1$, \ldots, $m_t)$ $\succ$ $(n_1$, \ldots, $n_t)$
if
\[
a_1 m_1 + \cdots + a_t m_t > a_1 n_1 + \cdots + a_t n_t,
\]
or
\[
a_1 m_1 + \cdots + a_t m_t = a_1 n_1 + \cdots + a_t n_t,
\]
and $m_1 = n_1$, $m_2 = n_2$, \ldots,
$m_{i-1} = n_{i-1}$, $m_i<n_i$, for some $1 \leq i \leq t$.
\end{definition}
Notice that the definition of $\succ$ depends on the order of
elements in $A_t$.

\begin{definition}\textup{\cite[Definition 6 and 8]{miura94},
\cite[Section 5.2]{miurathesis},
\cite[pp.~1408--1409]{miura98b}}
We define $B(A_t) = \{ (n_1$, \ldots, $n_t) \in \mathbf{N}_0^t \mid$
if
$a_1 n_1 + \cdots + a_t n_t = a_1 m_1 + \cdots + a_t m_t$ for
some $(m_1$, \ldots, $m_t) \in \mathbf{N}_0^t$ then
$(n_1$, \ldots, $n_t) \preceq (m_1$, \ldots, $m_t) \}$, and
$V(A_t)$ to be the set of minimal elements in $\mathbf{N}_0^t
\setminus B(A_t)$ with respect to
the partial order in $\mathbf{N}_0^t$ such that
$(m_1$, \ldots, $m_t)$ is smaller than
$(n_1$, \ldots, $n_t)$ if
$m_i \leq n_i$ for $i=1$, \ldots, $t$.
\end{definition}

Choose $x_i \in R$ such that $\rho(x_i) = a_i$.
Let $X_i$ be variable over $K$ for $i=1$, \ldots, $t$,
and $I \subset K[X_1$, \ldots, $X_t]$
the kernel of the evaluation homomorphism
$X_i \mapsto x_i$.
We shall show that $R=K[x_1$, \dots, $x_t]$ (Corollary \ref{rkx}),
and characterize the form of the reduced Gr\"{o}bner basis
for $I$ with respect to $\prec$ (Theorem \ref{maintheorema}).
Then we shall show that if a set of polynomials
is in such a form then it defines a weight domain conversely (Theorem
\ref{conversetheorem}).
Basic facts in the Gr\"{o}bner basis theory
can be found in \cite{adams94,bn:cox}.
We assume that the reader is familiar with Gr\"{o}bner bases.
For $N = (n_1$, \ldots, $n_t) \in \mathbf{N}_0^t$,
we denote 
$X_1^{n_1} \cdots X_t^{n_t}$ (resp. $x_1^{n_1} \cdots
x_t^{n_t}$) by $X^N$ (resp. $x^N$).

\begin{proposition}\label{basis}\textup{\cite[Lemma 10]{miura94},
\cite[Lemma 5.13]{miurathesis},
\cite[p.~1410]{miura98b}}
$\{ x^N \mid N \in B(A_t)\}$ forms a $K$-basis for $R$.
\end{proposition}
\noindent\emph{Proof.}
By the definitions of $B(A_t)$ and the weight function,
the elements in $\{ x^N \mid N \in B(A_t)\}$ are linearly
independent.

Let $h$ be a nonzero element in $R$.
There exists $N \in B(A_t)$ such that
$\rho(x^N) = \rho(h)$,
and $c_N \in K$ such that $\rho(h - c_N x^N) < \rho(h)$.
By repeating this argument,
we can write $h$ as
\[
\sum_{N \in B(A_t)} c_N x^N.
\]
We have shown that
$h$ can be written as a linear combination of elements in
$\{ x^N \mid N \in B(A_t)\}$. \qed

\begin{corollary}\label{rkx}\textup{\cite[Lemma 9]{miura94},
\cite[Lemma 5.3]{miurathesis},
\cite[p.~1406]{miura98b}}
$R = K[x_1, \ldots, x_t]$. \qed
\end{corollary}

\begin{definition}
The delta set of $I$, denoted by $\Delta(I)$,
is $\{ N \in \mathbf{N}_0^t \mid X^N$ is not the leading monomial of
any nonzero polynomial in $I$ with respect to $\prec\}$.
\end{definition}

\begin{lemma}\textup{\cite[Section 5.4]{miurathesis},
\cite[p.~1417]{miura98b}}
$\Delta(I) = B(A_t)$.
\end{lemma}
\noindent\emph{Proof.}
We claim that $\Delta(I) \subseteq B(A_t)$.
Suppose that there is $N \in \Delta(I) \setminus B(A_t)$.
By Proposition \ref{basis},
we can write $x^N$ as
\[
\sum_{\begin{array}{cc}\scriptstyle M \in B(A_t)\\
\scriptstyle \rho(x^M) \leq \rho(x^N)\end{array}} c_M x^M.
\]
Consider the polynomial
\[
X^N - \sum_{\begin{array}{cc}\scriptstyle M \in B(A_t)\\
\scriptstyle \rho(x^M) \leq \rho(x^N)\end{array}} c_M X^M.
\]
Then it belongs to $I$ and by the definition of $B(A_t)$
its leading monomial is $X^N$,
which is a contradiction.

Since $\{ x^N \mid N \in \Delta(I) \}$ forms a $K$-basis for $R$
\cite[Proposition 2.1.6]{adams94},
we can see that $\Delta(I) = B(A_t)$ by Proposition \ref{basis}. \qed

\begin{lemma}\textup{\cite[Lemma 7]{miura94},
\cite[Lemma 5.10]{miurathesis},
\cite[p.~1409]{miura98b}}
$V(A_t)$ is finite.
\end{lemma}
\noindent\emph{Proof.}
The assertion is a special case of Dickson's Lemma \cite[Exercise 1.4.12]{adams94}.
\qed

\begin{definition}
For each $N \in V(A_t)$,
we can write $x^N$ as
\[
\sum_{M\in B(A_t)} c_M x^M,
\]
in a unique way.
We define the polynomial $F_N \in K[X_1$, \ldots, $X_t]$
to be
\[
X^N - \sum_{M\in B(A_t)} c_M X^M.
\]
\end{definition}

\begin{theorem}\label{maintheorema}\textup{\cite[Lemma 14]{miura94},
\cite[Theorem 5.16]{miurathesis},
\cite[pp.~1410--1411]{miura98b}}
$\{ F_N \mid N \in V(A_t)\}$ is the reduced Gr\"{o}bner basis
for $I$ with respect to $\prec$.
\end{theorem}
\noindent\emph{Proof.}
$F_N \in I$ for each $N \in V(A_t)$,
and $\{ X^N \mid N \in V(A_t)\}$ is the set of minimal elements
in the set of leading monomials of $I$.
Thus by the definition of Gr\"{o}bner basis,
$\{ F_N \mid N \in V(A_t)\}$ is a Gr\"{o}bner basis.
It is clear that $\{ F_N \mid N \in V(A_t)\}$ is the
reduced Gr\"{o}bner basis for $I$. \qed

We shall prove a converse to Theorem \ref{maintheorema}.
\begin{theorem}\label{conversetheorem}\textup{\cite[Theorem 1]{miura94},
\cite[Theorem 5.17]{miurathesis},
\cite[p.~1411]{miura98b},
\cite[Theorem 5.11]{pellikaanorder}}
For $M = (m_1$, \ldots, $m_t) \in \mathbf{N}_0^t$,
we define $\Psi(M) = a_1 m_1 + \cdots + a_t m_t$.
For each $N \in V(A_t)$ choose a polynomial $G_N$ in $K[X_1$,
\ldots, $X_t]$ of the form
\[
X^N + c_M X^M + \sum_{L\in B(A_t),\; \Psi(L)<\Psi(N)} c_L X^L,
\]
such that $\Psi(N) = \Psi(M)$, $M\in B(A_t)$, and $c_M \neq 0$.
Let $J$ be the ideal generated by $\{G_N \mid N\in V(A_t)\}$.
If $\{G_N \mid N\in V(A_t)\}$ is a Gr\"{o}bner basis
(automatically becoming the reduced one) with respect to $\prec$,
then
$K[X_1$, \ldots, $X_t]/J$ is a weight domain
with the weight function
$\rho(X^L \bmod J) = \Psi(L)$ for $L\in B(A_t)$.
\end{theorem}
\noindent\emph{Proof.}
Notice that
$V(A_t) + \mathbf{N}_0^t = \mathbf{N}_0^t\setminus B(A_t)$.
Since $\{G_N \mid N\in V(A_t)\}$ is a Gr\"{o}bner basis,
$\Delta(J) = \mathbf{N}_0^t \setminus
(V(A_t) + \mathbf{N}_0^t)$.
Thus $\Delta(J) = B(A_t)$
and
$\{X^L \bmod J \mid L \in B(A_t)\}$ forms a $K$-basis for
$K[X_1$, \ldots, $X_t]/J$.

We shall check whether $\rho$ is a weight function.
The conditions 1--4 of weight functions (Definition \ref{weightdef})
are satisfied by the discussion in the previous paragraph.
We shall check the condition 5.
Let $E_1, E_2$ be polynomials written as linear combinations
of monomials in $\{ X^N \mid N\in B(A_t)\}$.
In order to calculate the weight of $E_1 E_2 \bmod J$,
we have to write $E_1 E_2$ as a linear combination
of monomials in $\{ X^N \mid N\in B(A_t)\}$,
which can be done by Gr\"{o}bner basis division.
Let $E_3$ be the remainder on division of $E_1 E_2$ by
$\{G_N \mid N\in V(A_t)\}$.
By the form of $\{G_N \mid N\in V(A_t)\}$,
we can see that $\rho(E_1 E_2 \bmod J) = \rho(E_3 \bmod J)$.
\qed

\begin{remark}
In this survey a weight function has values in $\mathbf{N}_0$.
Pellikaan and Geil \textup{\cite{geil99}} extend the notion of weight functions to taking
values in a general semigroup and genelarize Theorem
\textup{\ref{conversetheorem}} in \textup{\cite[Theorem 1.7.1]{geil99}}.
\end{remark}

\begin{proposition}\label{weightexponent}\textup{\cite[Lemma 5.21]{miurathesis},
\cite[p.~1413]{miura98b}}
We retain notations from
Theorem \textup{\ref{conversetheorem}}.
$\rho(X^L \bmod J) = \Psi(L)$ for all $L \in \mathbf{N}_0^t$.
\end{proposition}
\noindent\emph{Proof.}
In order to calculate 
$\rho(X^L \bmod J)$,
we have to write $X^L \bmod J$
as a linear combination of
$\{ X^{L'} \bmod J \mid L' \in B(A_t) \}$,
which can be done by dividing
$X^L$ by $\{G_N \mid N\in V(A_t)\}$.
Let $L''$ be the exponent of the leading monomial
of the remainder on division of $X^L$
by $\{G_N \mid N\in V(A_t)\}$.
Then by definition $\rho(X^L \bmod J) = \Psi(L'')$.
By the form of $\{G_N \mid N\in V(A_t)\}$,
we can see that $\Psi(L) = \Psi(L'')$. \qed

\begin{remark}
When we construct a weight domain as in Theorem \textup{\ref{conversetheorem}},
we can
easily find a $K$-basis for the weight domain with pairwise distinct
weights as in the proof of Theorem \textup{\ref{conversetheorem}}.
Such a basis is indispensable with code construction and
decoding algorithms of AG codes.
This fact is stated in a different way in \textup{\cite[Proposition 13]{saints95}}.
\end{remark}

\begin{remark}
Saints and Heegard defined the notion of a projective algebraic curve
in special position \textup{\cite[Definition 11]{saints95}}.
The projective closure of the
affine algebraic curve defined in Theorem \textup{\ref{conversetheorem}}
is in special position
if it is nonsingular and $a_1 < \cdots < a_t$.
Conversely,
if a projective algebraic curve $\chi$ is
in special position with respect to a point $Q$,
then the affine coordinate ring of the affine algebraic curve
$\chi \setminus \{Q\}$ is a weight domain.
\end{remark}

For construction of weight domains and linear codes on them,
we have to calculate $B(A_t)$ and $V(A_t)$.
It is not obvious how to calculate $B(A_t)$ and $V(A_t)$.
We shall clarify it.
\begin{definition}\label{li}
For $i=0$, \ldots, $a_1-1$,
we define $b_i = \min\{ x \in H \mid x \equiv i \pmod{a_1}\}$,
and $L_i$ to be the minimum element $N \in \mathbf{N}_0^t$
with respect to $\prec$ such that $\Psi(N) = b_i$,
where $\Psi$ is as in Theorem \textup{\ref{conversetheorem}}.
\end{definition}
Notice that we can easily calculate $L_0$, \ldots, $L_{a_1-1}$
when we are given a sequence $a_1$, \ldots, $a_t$.

\begin{lemma}
Let $L_i = (\ell_1$, \ldots, $\ell_t)$.
Then $\ell_1 = 0$.
\end{lemma}
\emph{Proof.}
Suppose that $\ell_1 > 0$.
Then $b_i = \ell_1 a_1 + \ell_2 a_2 + \cdots + \ell_t a_t
> \ell_2 a_2 + \cdots + \ell_t a_t \in H$,
which contradicts to the definition of $b_i$. \qed

\begin{proposition}\label{batvat}\textup{\cite[Lemma 5 and 7]{miura94},
\cite[Lemma 5.9 and 5.10]{miurathesis},
\cite[pp.~1408--1409]{miura98b}}
Let
\[
e_i = (\overbrace{0,\ldots,0}^{i-1},1,0,\ldots,0) \in \mathbf{N}_0^t,
\]
for $i=2$, \ldots, $t$. Then
\begin{eqnarray*}
B(A_t) &=& \{ L_i + (j,0,\ldots,0) \mid 0\leq i\leq a_1-1,\; 0\leq j\},\\
V(A_t) &\subseteq& \{ L_i + e_j \mid 0\leq i\leq a_1-1,\; 2\leq j\leq t \}.
\end{eqnarray*}
\end{proposition}
\noindent\emph{Proof.}
The second assertion follows from the first and the definition
of $V(A_t)$. We shall prove the first.

Let $x \in H$,
$i = x \bmod a_1$, and
$j = (x-b_i) / a_1$.
Then $x = b_i + j a_1$, and
$\Psi(L_i + (j,0$, \ldots, $0)) = x$.
Suppose that $\Psi(N) = x$ for some $N \in \mathbf{N}_0^t$.
It is enough to show that
$L_i + (j,0$, \ldots, $0) \preceq N$ to prove the first assertion
by the definition of $B(A_t)$.

Let $N = (n_1$, \ldots, $n_t)$.
If $n_1 < j$ then $L_i + (j,0$, \ldots, $0) \prec N$
by the definition of $\prec$.
If $n_1 > j$ then
$\Psi(0$, $n_2$, \ldots, $n_t) = x - n_1 a_1 < x - j a_1 = b_i$,
which is a contradiction.
So hereafter we assume that $j = n_1$.

Since $\prec$ is a monomial order,
it is enough to show that $L_i \preceq (0,n_2$, \ldots, $n_t)$.
Because $\Psi(0,n_2, \ldots, n_t) = b_i$,
$L_i \preceq (0,n_2$, \ldots, $n_t)$ by the definition of $L_i$.
\qed

\subsection{Construction of telescopic weight domains}
It is difficult to check whether a given set of polynomials
in Theorem \ref{conversetheorem} is a Gr\"{o}bner basis
by hand.
We shall show that if $H$ is telescopic then
the set of polynomials in Theorem \ref{conversetheorem}
automatically forms a Gr\"{o}bner basis
and we can write $B(A_t)$ and $V(A_t)$ in a more explicit way
than Proposition \ref{batvat}.
We call a weight domain telescopic if the associated semigroup
is telescopic.

\begin{definition}\label{telescopicdef}
A sequence $a_1$, \ldots, $a_t$ is said to be
\emph{telescopic}
if $a_i/d_i$ belongs to the semigroup generated by
$a_1/d_{i-1}$, \ldots, $a_{i-1}/d_{i-1}$ for $i=2$,
\ldots, $t$,
where $d_i$ is the greatest common divisor of
$a_1$, \ldots, $a_i$.
A subsemigroup of $\mathbf{N}_0$ is said to be telescopic
if it can be generated by a telescopic sequence.
\end{definition}

\begin{lemma}
Let $L_i$ be as in Definition \textup{\ref{li}}.
If $a_1$, \ldots, $a_t$ is telescopic,
then $\{ L_i \mid i=0$, \ldots, $a_1-1\} = \{
(0,n_2$, \ldots, $n_t) \mid 0 \leq n_i < d_{i-1}/d_i$
for $i=2$, \ldots, $t\}$.
\end{lemma}
\noindent\emph{Proof.}
Suppose that $L_i = (0,\ell_2$, \ldots, $\ell_t)$, and
$\ell_j \geq d_{j-1}/d_j$ for some $j\geq 2$.
By the definition of telescopic sequences,
$(d_{j-1}/d_j)a_j$ belongs to the semigroup
generated by $a_1$, \ldots, $a_{j-1}$.
Let $\alpha_1 a_1 + \cdots + \alpha_{j-1} a_{j-1}
= (d_{j-1}/d_j)a_j$,
and $L'_i = (\ell_1+\alpha_1$, \ldots, $\ell_{j-1}+\alpha_{j-1}$,
$\ell_j - (d_{j-1}/d_j)$, $\ell_{j+1}$, \ldots, $\ell_t)$.
Then $\Psi(L_i) = \Psi(L'_i)$ and
$L'_i \prec L_i$,
which contradicts to the definition of $L_i$.
We have shown that
$\{ L_i \mid i=0$, \ldots, $a_1-1\} \subseteq \{
(0,n_2$, \ldots, $n_t) \mid 0 \leq n_i < d_{i-1}/d_i$
for $i=2$, \ldots, $t\}$.

Is is easy to see that both sets have $a_1$ elements.
So the assertion is proved. \qed

\begin{corollary}\label{telescopicform}\textup{\cite[Theorem 1 (VI)]{miura94},
\cite[Theorem 5.43]{miurathesis},
\cite[p.~1419]{miura98b}}
Suppose that the sequence $a_1, \ldots, a_t$ is telescopic.
Then
\begin{eqnarray*}
B(A_t)&=&\{(n_1,\ldots,n_t) \in \mathbf{N}_0^t \mid
0\leq n_i < d_{i-1}/d_i\mbox{ for }i=2,\ldots,t\},\\
V(A_t) &=& \{ (\overbrace{0,\ldots,0}^{i-1}, d_{i-1}/d_i, 0,\ldots,0) \mid
i=2,\ldots,t\}.
\end{eqnarray*}
\end{corollary}
\noindent\emph{Proof.}
The assertions follow directly from
the previous lemma, Proposition \ref{batvat},
and the definition of $\prec$
and $V(A_t)$. \qed

\begin{remark}
A similar fact to Corollary \textup{\ref{telescopicform}} is
shown in \textup{\cite[Lemma 6.4]{kirfel95}}
and \textup{\cite[Lemma 5.34]{hoholdt98}}.
\end{remark}

\begin{theorem}\textup{\cite[p.~462, Remark]{miura94},
\cite[Corollary 5.36]{miurathesis},
\cite[p.~1418]{miura98b}}
Suppose that $a_1$, \ldots, $a_t$ is telescopic.
Then the set of polynomials $\{G_N \mid N\in V(A_t)\}$
forms a Gr\"{o}bner basis.
\end{theorem}
\noindent\emph{Proof.}
The assertion follows directly from Theorem 3 and
Proposition 4 in \cite[Section 2.9]{bn:cox}. \qed

\begin{remark}
A special case of the previous theorem is in
\textup{\cite[Example 5.36]{hoholdt98}, \cite[Proposition 5.12]{pellikaanorder}}.
\end{remark}

\begin{remark}
Further 
applications of telescopic semigroups in coding theory
can be found in \textup{\cite{hoholdt98,kirfel95}}.
Research articles on telescopic semigroups
are listed in \textup{\cite[Remark 6.7]{kirfel95}}.
\end{remark}

\begin{remark}
It is desirable to choose generators $a_1$, \ldots,
$a_t$ as few as possible.
A generating set of $H$ is said to be \emph{minimal}
if $H$ is not generated by its proper subset.
We can prove that a minimal generating set is unique,
each generating set contains the minimal one, and
if $H$ is telescopic then we can make the minimal generating
set a telescopic sequence.
A proof can be found in \textup{\cite{miurathesis,miura98b}}.
\end{remark}

\subsection{Construction of plane weight domains}
If the associated semigroup is generated by two numbers,
then the weight domain can be obtained as the affine coordinate ring
of a plane affine algebraic curve.
We call such a weight domain plane.
In this subsection we write down the defining equation of
a plane weight domain explicitly.

We retain notations from Section \ref{generalweight}
unless otherwise specified.
Let $a = a_1$, $b = a_2$, $X=X_1$, and $Y=X_2$.
Since we assume that $\mathbf{N}_0 \setminus H$ is finite
and not empty,
$a$ and $b$ are relatively prime \cite[Corollary 5.12]{hoholdt98}
and greater than $1$.
Note that in this case $a,b$ is a telescopic sequence
and a plane weight domain is a special case of a telescopic weight
domain.

As a special case of Corollary \ref{telescopicform}
we have
\begin{corollary}\textup{\cite[Section 7.2]{miurathesis}}
\begin{eqnarray*}
B(A_t) &=& \{ (i,j) \in \mathbf{N}_0^2 \mid 0 \leq i,\;
0\leq j < a \},\\
V(A_t) &=& \{ (0,a) \}.
\end{eqnarray*}
$F_N$ in Theorem \textup{\ref{maintheorema}} and $G_N$ in
Theorem \textup{\ref{conversetheorem}} is of form
\begin{equation}
Y^a + c_{b,0} X^b + \sum_{ia+bj < ab} c_{i,j} X^i Y^j,\label{cab}
\end{equation}
where $c_{b,0} \neq 0$ and $c_{i,j} \in K$. \qed
\end{corollary}

We shall clarify which algebraic curve can have a plane model
of the form (\ref{cab}).
\begin{proposition}\textup{\cite[Theorem 5.17 (9)]{miurathesis},
\cite[p.~1412]{miura98b}}
Let $\chi$ be a nonrational nonsingular projective algebraic curve
over $K$.
If there is a $K$-rational point $Q \in \chi$,
then $\chi$ can have a plane model of the form \textup{(\ref{cab})}.
\end{proposition}
\noindent\emph{Proof.}
Let $F$ be the field of $K$-rational functions on $\chi$,
$v_Q$ the discrete valuation at $Q$,
and $x,y \in F\setminus K$ functions such that
they are regular at $\chi \setminus \{Q\}$
and $v_Q(x)$ and $v_Q(y)$ are relatively prime. From
the definition of $x,y$,
the pole divisor of $x$ (resp. $y$) is
$-v_Q(x)Q$ (resp. $-v_Q(y)Q$).

$[F:K(x)] = -v_Q(x)$ and $[F:K(y)] = -v_Q(y)$ \cite[Theorem I.4.11]{bn:stichtenoth},
and $[F:K(x,y)]$ divides both $[F:K(x)]$ and $[F:K(y)]$.
Thus $[F:K(x,y)] = 1$.

$K[x,y]$ is a weight domain with the weight function $-v_Q$.
Thus $K[x,y]$ is the affine coordinate ring of an affine algebraic
curve defined by a polynomial of the form (\ref{cab}),
where we set $a = -v_Q(x)$ and $b = -v_Q(y)$.
\qed

\begin{remark}
The second author observed that we can easily construct algebraic geometry
codes on affine algebraic curves defined by polynomials
of form \textup{(\ref{cab})} in \textup{\cite{miura92}}.
\end{remark}

\begin{remark}
An overlapping but different construction of weight domains
is in \textup{\cite[Proposition 3.17]{hoholdt98},
\cite[Proposition 4.6]{pellikaanorder}}.
\end{remark}

%\bibliographystyle{amsalpha}
%\bibliography{mrabbrev,mybib2}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\begin{thebibliography}{HvLP98}
\bibitem[AL94]{adams94}
William~W. Adams and Phillippe Loustaunau, \emph{An introduction to {G}r\"obner
  bases}, Graduate Studies in Mathematics, vol.~3, American Mathematical
  Society, 1994.

\bibitem[CLO96]{bn:cox}
David Cox, John Little, and Donal O'Shea, \emph{Ideals, varieties, and
  algorithms}, 2nd ed., Springer-Verlag, Berlin, 1996.

\bibitem[Gei99]{geil99}
Olav Geil, \emph{Codes based on an $\mathbb{F}_q$-algebra}, Ph.D. thesis,
  Aalborg Univ., Denmark, December 1999.

\bibitem[HvLP97]{hoholdt97}
Tom H{\o}holdt, Jacobus~H. van Lint, and Ruud Pellikaan, \emph{Order functions
  and evaluation codes}, Proc. AAECC-12, Lecture Notes in Computer Science,
  vol. 1255, Springer-Verlag, 1997, pp.~138--150.

\bibitem[HvLP98]{hoholdt98}
Tom H{\o}holdt, Jacobus~H. van Lint, and Ruud Pellikaan, \emph{Algebraic
  geometry codes}, Handbook of Coding Theory (Vera Pless and William~Cary
  Huffman, eds.), Elsevier, 1998, pp.~871--961.

\bibitem[KP95]{kirfel95}
Christoph Kirfel and Ruud Pellikaan, \emph{The minimum distance of codes in an
  array coming from telescopic semigroups}, IEEE Trans.\  Inform.\  Theory
  \textbf{41} (1995), no.~6, 1720--1732.

\bibitem[Mat99a]{matsumoto98b}
Ryutaroh Matsumoto, \emph{Linear codes on nonsingular curves are better than
  those on singular curves}, IEICE Transactions on Fundamentals of Electronics,
  Communications and Computer Sciences (ISSN 0916-8508) \textbf{E82-A} (1999),
  no.~4, 665--670.

\bibitem[Mat99b]{matsumoto99weight}
Ryutaroh Matsumoto, \emph{Miura's generalization of one-point AG codes is
  equivalent to H\o holdt, van Lint and Pellikaan's generalization}, IEICE
  Transactions on Fundamentals of Electronics, Communications and Computer
  Sciences (ISSN 0916-8508) \textbf{E82-A} (1999), no.~10, 2007--2010.

\bibitem[Miu92]{miura92}
Shinji Miura, \emph{Algebraic geometric codes on certain plane curves},
  Transactions of IEICE (ISSN 0913-5707) \textbf{J75-A} (1992), no.~11,
  1735--1745 (Japanese).

\bibitem[Miu94]{miura94}
Shinji Miura, \emph{Constructive theory of algebraic curves}, Proceedings of
  the 17th Symposium on Information Theory and Its Applications (Hiroshima,
  Japan), December 1994, pp.~461--464 (Japanese).

\bibitem[Miu97]{miurathesis}
Shinji Miura, Ph.D. thesis, Univ.\  Tokyo, May 1997 (Japanese).

\bibitem[Miu98]{miura98b}
Shinji Miura, \emph{Linear codes on affine algebraic curves}, Transactions of
  IEICE (ISSN 0913-5707) \textbf{J81-A} (1998), no.~10, 1398--1421 (Japanese).

\bibitem[Pel]{pellikaanorder}
Ruud Pellikaan, \emph{On the existence of order functions}, to appear in
  Journal of Statistical Planning and Inference, available from {\tt
  http:/\slash www.\allowbreak win.\allowbreak tue.\allowbreak nl\slash
  math\slash dw\slash personalpages\slash ruudp/}.

\bibitem[SH95]{saints95}
Keith Saints and Chris Heegard, \emph{Algebraic-geometric codes and
  multidimensional cyclic codes: A unified theory and algorithms for decoding
  using {G}r\"{o}bner bases}, IEEE Trans.\  Inform.\  Theory \textbf{41} (1995),
  no.~6, 1733--1751.

\bibitem[Sti93]{bn:stichtenoth}
Henning Stichtenoth, \emph{Algebraic function fields and codes},
  Springer-Verlag, Berlin, 1993.
\end{thebibliography}
\end{document}