Namespaces
Variants
Actions

Difference between revisions of "Artin-Schreier code"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
Given an [[Algebraic curve|algebraic curve]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a1107301.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a1107302.png" /> is a [[Field|field]] of characteristic <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a1107303.png" />, a [[Covering|covering]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a1107304.png" /> is called an Artin–Schreier curve over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a1107305.png" /> if the corresponding extension of function fields <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a1107306.png" /> is generated by some function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a1107307.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a1107308.png" /> (where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a1107309.png" /> is a power of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073010.png" />, cf. also [[Extension of a field|Extension of a field]]). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073011.png" /> is a [[Finite field|finite field]], it turns out that Artin–Schreier curves often have many rational points.
+
<!--
 +
a1107301.png
 +
$#A+1 = 40 n = 0
 +
$#C+1 = 40 : ~/encyclopedia/old_files/data/A110/A.1100730 Artin\ANDSchreier code
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
To be precise, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073012.png" /> (respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073013.png" />) denote the number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073014.png" />-rational points (respectively, the genus) of a curve <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073015.png" />. The Hasse–Weil theorem states that
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073016.png" /></td> </tr></table>
+
Given an [[Algebraic curve|algebraic curve]]  $  X/K $,
 +
where  $  K $
 +
is a [[Field|field]] of characteristic  $  p > 0 $,
 +
a [[Covering|covering]]  $  Y \rightarrow X $
 +
is called an Artin–Schreier curve over  $  X $
 +
if the corresponding extension of function fields  $  K ( Y ) /K ( X ) $
 +
is generated by some function  $  y \in K ( Y ) $
 +
such that  $  y  ^ {l} \pm y = f \in K ( X ) $(
 +
where  $  l $
 +
is a power of  $  p $,
 +
cf. also [[Extension of a field|Extension of a field]]). If  $  K = \mathbf F _ {q} $
 +
is a [[Finite field|finite field]], it turns out that Artin–Schreier curves often have many rational points.
  
If the genus is large with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073017.png" />, this bound can be improved as follows. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073018.png" /> be a sequence of curves over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073019.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073020.png" />. Then
+
To be precise, let  $  N ( Y ) $(
 +
respectively,  $  g ( Y ) $)
 +
denote the number of  $  \mathbf F _ {q} $-
 +
rational points (respectively, the genus) of a curve  $  Y/ \mathbf F _ {q} $.  
 +
The Hasse–Weil theorem states that
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073021.png" /></td> </tr></table>
+
$$
 +
N ( Y ) \leq  q + 1 + 2g ( Y ) \sqrt q .
 +
$$
 +
 
 +
If the genus is large with respect to  $  q $,
 +
this bound can be improved as follows. Let  $  ( Y _ {i} ) _ {i \in \mathbf N }  $
 +
be a sequence of curves over  $  \mathbf F _ {q} $
 +
such that  $  g ( Y _ {i} ) \rightarrow \infty $.  
 +
Then
 +
 
 +
$$
 +
{\lim\limits }  \sup  {
 +
\frac{N ( Y _ {i} ) }{g ( Y _ {i} ) }
 +
} \leq  \sqrt q - 1
 +
$$
  
 
(the Drinfel'd–Vladut bound).
 
(the Drinfel'd–Vladut bound).
  
Curves over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073022.png" /> can be used to construct error-correcting linear codes, so-called geometric Goppa codes or algebraic-geometric codes (cf. [[Error-correcting code|Error-correcting code]]; [[Goppa code|Goppa code]]; [[Algebraic-geometric code|Algebraic-geometric code]]; [[#References|[a4]]], [[#References|[a5]]]). If the curves have sufficiently may rational points, these codes have very good error-correcting properties. Hence, one is interested in explicit constructions of curves with many rational points.
+
Curves over $  \mathbf F _ {q} $
 +
can be used to construct error-correcting linear codes, so-called geometric Goppa codes or algebraic-geometric codes (cf. [[Error-correcting code|Error-correcting code]]; [[Goppa code|Goppa code]]; [[Algebraic-geometric code|Algebraic-geometric code]]; [[#References|[a4]]], [[#References|[a5]]]). If the curves have sufficiently may rational points, these codes have very good error-correcting properties. Hence, one is interested in explicit constructions of curves with many rational points.
  
 
==Examples of Artin–Schreier curves.==
 
==Examples of Artin–Schreier curves.==
The Hermitian curve over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073023.png" />, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073024.png" />, is given by the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073025.png" />. It has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073026.png" /> rational points and its genus is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073027.png" />. Hence, for it the Hasse–Weil bound <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073028.png" /> is attained, see [[#References|[a4]]].
+
The Hermitian curve over $  \mathbf F _ {q} $,  
 +
for $  q = l  ^ {2} $,  
 +
is given by the equation $  y  ^ {l} + y = x ^ {l + 1 } $.  
 +
It has $  N = l  ^ {3} + 1 $
 +
rational points and its genus is $  g = { {l ( l - 1 ) } / 2 } $.  
 +
Hence, for it the Hasse–Weil bound $  N = q + 1 + 2g \sqrt q $
 +
is attained, see [[#References|[a4]]].
  
Again, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073029.png" /> be a square. Define a tower of function fields <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073030.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073031.png" /> (cf. [[Tower of fields|Tower of fields]]) by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073032.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073033.png" />, where
+
Again, let $  q = l  ^ {2} $
 +
be a square. Define a tower of function fields $  F _ {1} \subseteq F _ {2} \subseteq \dots $
 +
over $  \mathbf F _ {q} $(
 +
cf. [[Tower of fields|Tower of fields]]) by $  F _ {1} = \mathbf F _ {q} ( x _ {1} ) $,  
 +
$  F _ {n + 1 }  = F _ {n} ( z _ {n} ) $,  
 +
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073034.png" /></td> </tr></table>
+
$$
 +
z _ {n + 1 }  ^ {l} + z _ {n + 1 }  = x _ {n} ^ {l + 1 }  \textrm{ and  }  x _ {n} = {
 +
\frac{z _ {n} }{x _ {n -1 }  }
 +
}  ( \textrm{ for  }  n \geq 2 ) .
 +
$$
  
For the corresponding algebraic curves <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073035.png" />, the coverings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073036.png" /> are Artin–Schreier curves. This sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073037.png" /> attains the Drinfel'd–Vladut bound, i.e., <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073038.png" /> (see [[#References|[a1]]]).
+
For the corresponding algebraic curves $  Y _ {1} ,Y _ {2} , \dots $,  
 +
the coverings $  Y _ {n + 1 }  \rightarrow Y _ {n} $
 +
are Artin–Schreier curves. This sequence $  ( Y _ {n} ) _ {n \in \mathbf N }  $
 +
attains the Drinfel'd–Vladut bound, i.e., $  {\lim\limits } _ {i \rightarrow \infty }  { {N ( Y _ {i} ) } / {g ( Y _ {i} ) } } = l - 1 $(
 +
see [[#References|[a1]]]).
  
The geometric Goppa codes constructed using these curves <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073039.png" /> beat the Gilbert–Varshamov bound (cf. also [[Error-correcting code|Error-correcting code]]; [[#References|[a3]]]) for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110730/a11073040.png" />. This construction is simpler and more explicit than the construction based on modular curves (the Tsfasman–Vladut–Zink theorem, [[#References|[a5]]]).
+
The geometric Goppa codes constructed using these curves $  Y _ {n} $
 +
beat the Gilbert–Varshamov bound (cf. also [[Error-correcting code|Error-correcting code]]; [[#References|[a3]]]) for all $  q \geq 49 $.  
 +
This construction is simpler and more explicit than the construction based on modular curves (the Tsfasman–Vladut–Zink theorem, [[#References|[a5]]]).
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Garcia,  H. Stichtenoth,  "A tower of Artin–Schreier extensions of function fields attaining the Drinfeld–Vladut bound"  ''Invent. Math.'' , '''121'''  (1995)  pp. 211–222</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  G. van der Geer,  M. van der Vlugt,  "Curves over finite fields of characteristic two with many rational points"  ''C.R. Acad. Sci. Paris'' , '''317'''  (1993)  pp. 693–697</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J.H. van Lint,  "Introduction to coding theory" , Springer  (1992)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  H. Stichtenoth,  "Algebraic function fields and codes" , Springer  (1993)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  M.A. Tsfasman,  S.G. Vladut,  "Algebraic geometric codes" , Kluwer Acad. Publ.  (1991)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Garcia,  H. Stichtenoth,  "A tower of Artin–Schreier extensions of function fields attaining the Drinfeld–Vladut bound"  ''Invent. Math.'' , '''121'''  (1995)  pp. 211–222</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  G. van der Geer,  M. van der Vlugt,  "Curves over finite fields of characteristic two with many rational points"  ''C.R. Acad. Sci. Paris'' , '''317'''  (1993)  pp. 693–697</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  J.H. van Lint,  "Introduction to coding theory" , Springer  (1992)</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  H. Stichtenoth,  "Algebraic function fields and codes" , Springer  (1993) ISBN 3-540-58469-6 {{ZBL|0816.14011}}</TD></TR>
 +
<TR><TD valign="top">[a5]</TD> <TD valign="top">  M.A. Tsfasman,  S.G. Vladut,  "Algebraic geometric codes" , Kluwer Acad. Publ.  (1991)</TD></TR>
 +
</table>
 +
 
 +
[[Category:Information and communication, circuits]]

Latest revision as of 18:48, 5 April 2020


Given an algebraic curve $ X/K $, where $ K $ is a field of characteristic $ p > 0 $, a covering $ Y \rightarrow X $ is called an Artin–Schreier curve over $ X $ if the corresponding extension of function fields $ K ( Y ) /K ( X ) $ is generated by some function $ y \in K ( Y ) $ such that $ y ^ {l} \pm y = f \in K ( X ) $( where $ l $ is a power of $ p $, cf. also Extension of a field). If $ K = \mathbf F _ {q} $ is a finite field, it turns out that Artin–Schreier curves often have many rational points.

To be precise, let $ N ( Y ) $( respectively, $ g ( Y ) $) denote the number of $ \mathbf F _ {q} $- rational points (respectively, the genus) of a curve $ Y/ \mathbf F _ {q} $. The Hasse–Weil theorem states that

$$ N ( Y ) \leq q + 1 + 2g ( Y ) \sqrt q . $$

If the genus is large with respect to $ q $, this bound can be improved as follows. Let $ ( Y _ {i} ) _ {i \in \mathbf N } $ be a sequence of curves over $ \mathbf F _ {q} $ such that $ g ( Y _ {i} ) \rightarrow \infty $. Then

$$ {\lim\limits } \sup { \frac{N ( Y _ {i} ) }{g ( Y _ {i} ) } } \leq \sqrt q - 1 $$

(the Drinfel'd–Vladut bound).

Curves over $ \mathbf F _ {q} $ can be used to construct error-correcting linear codes, so-called geometric Goppa codes or algebraic-geometric codes (cf. Error-correcting code; Goppa code; Algebraic-geometric code; [a4], [a5]). If the curves have sufficiently may rational points, these codes have very good error-correcting properties. Hence, one is interested in explicit constructions of curves with many rational points.

Examples of Artin–Schreier curves.

The Hermitian curve over $ \mathbf F _ {q} $, for $ q = l ^ {2} $, is given by the equation $ y ^ {l} + y = x ^ {l + 1 } $. It has $ N = l ^ {3} + 1 $ rational points and its genus is $ g = { {l ( l - 1 ) } / 2 } $. Hence, for it the Hasse–Weil bound $ N = q + 1 + 2g \sqrt q $ is attained, see [a4].

Again, let $ q = l ^ {2} $ be a square. Define a tower of function fields $ F _ {1} \subseteq F _ {2} \subseteq \dots $ over $ \mathbf F _ {q} $( cf. Tower of fields) by $ F _ {1} = \mathbf F _ {q} ( x _ {1} ) $, $ F _ {n + 1 } = F _ {n} ( z _ {n} ) $, where

$$ z _ {n + 1 } ^ {l} + z _ {n + 1 } = x _ {n} ^ {l + 1 } \textrm{ and } x _ {n} = { \frac{z _ {n} }{x _ {n -1 } } } ( \textrm{ for } n \geq 2 ) . $$

For the corresponding algebraic curves $ Y _ {1} ,Y _ {2} , \dots $, the coverings $ Y _ {n + 1 } \rightarrow Y _ {n} $ are Artin–Schreier curves. This sequence $ ( Y _ {n} ) _ {n \in \mathbf N } $ attains the Drinfel'd–Vladut bound, i.e., $ {\lim\limits } _ {i \rightarrow \infty } { {N ( Y _ {i} ) } / {g ( Y _ {i} ) } } = l - 1 $( see [a1]).

The geometric Goppa codes constructed using these curves $ Y _ {n} $ beat the Gilbert–Varshamov bound (cf. also Error-correcting code; [a3]) for all $ q \geq 49 $. This construction is simpler and more explicit than the construction based on modular curves (the Tsfasman–Vladut–Zink theorem, [a5]).

References

[a1] A. Garcia, H. Stichtenoth, "A tower of Artin–Schreier extensions of function fields attaining the Drinfeld–Vladut bound" Invent. Math. , 121 (1995) pp. 211–222
[a2] G. van der Geer, M. van der Vlugt, "Curves over finite fields of characteristic two with many rational points" C.R. Acad. Sci. Paris , 317 (1993) pp. 693–697
[a3] J.H. van Lint, "Introduction to coding theory" , Springer (1992)
[a4] H. Stichtenoth, "Algebraic function fields and codes" , Springer (1993) ISBN 3-540-58469-6 Zbl 0816.14011
[a5] M.A. Tsfasman, S.G. Vladut, "Algebraic geometric codes" , Kluwer Acad. Publ. (1991)
How to Cite This Entry:
Artin-Schreier code. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Artin-Schreier_code&oldid=15256
This article was adapted from an original article by H. Stichtenoth (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article