Edit detail for PAFF revision 1 of 1

changed:
-
"PAFF":http://www-rocq.inria.fr/codes/Gaetan.Hache/PAFF.html
: Package for Algebraic Function Fields in one variable

by Gaétan Haché

PAFF is a package written in Axiom and one of its many purpose is to construct geometric Goppa codes (also called algebraic geometric codes or AG-codes). I wrote this package in the frame work of my doctorate thesis on "Effective construction of geometric codes": this thesis was done at Inria in Rocquencourt at project CODES and under the direction of Dominique LeBrigand at Université Pierre et Marie Curie (Paris 6). Here is a
"résumé":http://www-rocq.inria.fr/codes/Gaetan.Hache/these/resumeThese.html
of my thesis.

It is well known that the most difficult part in constructing AG-code is the computation of a basis of the vector space "L(D)" where D is a divisor of the function field of an irreducible curve. To compute such a basis, PAFF used the Brill-Noether algorithm which was generalized to any plane curve by D. !LeBrigand and J.J. Risler (see ![7] ). In ![4] you will find more details about the algorithmic aspect of the Brill-Noether algorithm. Also, if you prefer, as I do, a strictly algebraic approach, see ![3]. This is the approach I used in my thesis (![4]) and of course this is where you will find complete details about the implementation of the algorithm. The algebraic approach use the theory of algebraic function field in one variable : you will find in ![8] a very good introduction to this theory and AG-codes.

It is important to notice that PAFF can be used for most computation related to the function field of an irreducible plane curve. For example, you can compute the genus, find all places above all the singular points, compute the adjunction divisor and of course compute a basis of the vector space L(D) for any divisor D of the function field of the curve.

There is also the package PAFFFF which is especially designed to be used over finite fields. This package is essentially the same as PAFF, except that the computation are done over "dynamic extensions" of the ground field. For this, I used a simplify version of the notion of dynamic algebraic closure as proposed by D. Duval (see ![1]).

References

  1 Duval (D.). -- Évaluation dynamique et clôture algébrique en Axiom. Journal of Pure and Applied Algebra, no99, 1995, pp. 267--295.

  2 Garcia (A.) et Stichtenoth (H.). -- A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound. Invent. Math., vol. 121, 1995, pp. 211--222.

  3 Haché (G.). -- Computation in algebraic function fields for effective construction of algebraic-geometric codes. Lecture Notes in Computer Science, vol. 948, 1995, pp. 262--278.

  4 Haché (G.). -- Construction effective des codes géométriques. -- Thèse de doctorat de l'Université Pierre et Marie Curie (Paris 6), Septembre 1996.

  5 Haché (G.) et Le Brigand (D.). -- Effective construction of algebraic geometry codes. IEEE Transaction on Information Theory, vol. 41, n'27 6, November 1995, pp. 1615--1628.

  6 Huang (M.D.) et Ierardi (D.). -- Efficient algorithms for Riemann-Roch problem and for addition in the jacobian of a curve. In: Proceedings 32nd Annual Symposium on Foundations of Computer Sciences. IEEE Comput. Soc. Press, pp. 678--687.

  7 Le Brigand (D.) et Risler (J.J.). -- Algorithme de Brill-Noether et codes de Goppa. Bull. Soc. Math. France, vol. 116, 1988, pp. 231--253.

  8 Stichtenoth (H.). -- Algebraic function fields and codes. -- Springer-Verlag, 1993, University Text. 


Example 1

  This example compute the genus of the projective plane curve defined by::

       5    2 3      4
      X  + Y Z  + Y Z  = 0

  over the field GF(2).

First load the PAFF library (must be done twice).

\begin{axiom}
)lib )dir PAFF/spad
)lib )dir PAFF/spad
\end{axiom}

\begin{axiom}

-- First we define the field GF(2).

K:=PF 2  

-- Next, we define the polynomial ring over which
-- the polynomial is defined. 
-- You have the choice for the name of 
-- the three variables (always three !!) but  
-- the domain  DMP must be used. 
-- DMP  is an AXIOM domain and stands for DistributedMultivariatePolymnomial.

R:=DMP([X,Y,Z],K)

-- Then we tell to the package PAFF over which field the computation must be done.
-- Also, you must give the same list of variables which is used to defined the polynomial.
-- BLQT Stand for BlowUpWithQuadTrans which specified the method
-- used for blowing-up (there will be another one (when ?) 
-- using similar thechnics to Hamburger-Nother expansions).


P:=PAFF(K,[X,Y,Z],BLQT)

-- We defined now the polynomial of the curve.

C:R:=X**5 + Y**2*Z**3+Y*Z**4

-- We give it to the package PAFF(K,[X,Y,Z]) which was assigned to the
-- variable "P"


setCurve(C)$P

-- To compute the genus of the curve, simply do 


genus()$P


-- To compute the genus, the package use the genus formula 
-- given by the blowin-up theory. That means that the singular points
-- has been computed. 

singularPoints()$P

-- The results of singularPoints()$P is the list of all
-- the singular points of the curve in the projective plane.
--
--
-- The Brill-Noether algorithm use the notion of "adjunction divisor".
-- To compute it simply do "adjunctionDivisor()$P"
-- You should obtained something like
--
--            1
--       8 %I1
--
-- This is a divisor of the function field of the curve, consisting
-- of 8 times the place %I1 which is of degree 1 (the exponant).
-- The place %I1 is a place above a singular point (the unique one for this example).
-- This mean that the "desingularization tree" has been computed. See next step.

adjunctionDivisor()$P


-- To compute the "desingularization tree" simply do:
-- desingTree()$P
--
-- For this example, you should obtained from desingTree()$P
--
--        ["UU.."]
--
-- This a list of desingularization tree for each singular point.
-- Here there is only one, which is "UU..".  
-- To interpret the result, you have to do some manual drawing.
-- The letter U means "Up", and a . (dot) means "down".
-- 
--
--
--              o
--              |  
--           ^  |  |
--           |  |  | .
--         U |  |  | 
--           |  |  v
--              |
--              |
--              o
--              |  
--           ^  |  |
--           |  |  | .
--         U |  |  |
--           |  |  v
--              |
--              |
--              o
--         

desingTree()$P

-- To see more information about the desingularization trees,
-- issue the command, fullDesTree()$P, and recall the command 
-- desingTree()$P. Here you have a bit more information about
-- the infinitly near points in the desingularization trees.
-- For this example, the result corresponds to the following
--
--         %I1  o  multiplicity = 1
--              |  
--              |
--              |
--              |
--              |
--              |
--              |
--         %I0  o  multiplicity = 2
--              |  
--              |
--              |
--              |
--              |
--              |
--              |
--         %P0  o  multiplicity = 3
--         


fullDesTree()$P
desingTree()$P


-- To see everything about desingularization trees, issue
-- the following

fullInfClsPt()$P
--desingTree()$P


-- You can ask for all the place of degree 1
--

placesOfDegree(1)$P


-- With those places, you can create divisors 


listOfDiv:=placesOfDegree(1)$P :: List DIV PLACES PF 2

-- You can add the divisors.

D:=reduce(+, listOfDiv)

-- You can multiply the divisor by an integer

D10 := 10 * D


-- You can ask for the degree of the divisor

degree D10


-- You can compute the basis of the vector space L(D10).
-- The results is an Axiom Record. The first selector "num"
-- corresponds to the numerators of the elements of the basis,
-- and the second selector "den" is the common denominator.


baseOfLofD:= lBasis(D10)$P

-- Of course, the number of element in the list of numerator
-- is the dimension of the vector space L(D10). According to the 
-- Riemann-Roch Theorem, since 
-- 
--  deg D10 >= 2 g - 1
-- 
-- we should have 
--
-- dim L(D10) = deg D10 - g + 1
--
--

((# baseOfLofD.num) = degree D10 - genus()$P + 1 ) :: Boolean

\end{axiom}

PAFF : Package for Algebraic Function Fields in one variable

by Gaétan Haché

PAFF is a package written in Axiom and one of its many purpose is to construct geometric Goppa codes (also called algebraic geometric codes or AG-codes). I wrote this package in the frame work of my doctorate thesis on "Effective construction of geometric codes": this thesis was done at Inria in Rocquencourt at project CODES and under the direction of Dominique LeBrigand? at Université Pierre et Marie Curie (Paris 6). Here is a résumé of my thesis.

It is well known that the most difficult part in constructing AG-code is the computation of a basis of the vector space "L(D)" where D is a divisor of the function field of an irreducible curve. To compute such a basis, PAFF used the Brill-Noether algorithm which was generalized to any plane curve by D. LeBrigand and J.J. Risler (see [7] ). In [4] you will find more details about the algorithmic aspect of the Brill-Noether algorithm. Also, if you prefer, as I do, a strictly algebraic approach, see [3]. This is the approach I used in my thesis ([4]) and of course this is where you will find complete details about the implementation of the algorithm. The algebraic approach use the theory of algebraic function field in one variable : you will find in [8] a very good introduction to this theory and AG-codes.

It is important to notice that PAFF can be used for most computation related to the function field of an irreducible plane curve. For example, you can compute the genus, find all places above all the singular points, compute the adjunction divisor and of course compute a basis of the vector space L(D) for any divisor D of the function field of the curve.

There is also the package PAFFFF which is especially designed to be used over finite fields. This package is essentially the same as PAFF, except that the computation are done over "dynamic extensions" of the ground field. For this, I used a simplify version of the notion of dynamic algebraic closure as proposed by D. Duval (see [1]).

References

1. Duval (D.). -- Évaluation dynamique et clôture algébrique en Axiom. Journal of Pure and Applied Algebra, no99, 1995, pp. 267--295.
2. Garcia (A.) et Stichtenoth (H.). -- A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound. Invent. Math., vol. 121, 1995, pp. 211--222.
3. Haché (G.). -- Computation in algebraic function fields for effective construction of algebraic-geometric codes. Lecture Notes in Computer Science, vol. 948, 1995, pp. 262--278.
4. Haché (G.). -- Construction effective des codes géométriques. -- Thèse de doctorat de l'Université Pierre et Marie Curie (Paris 6), Septembre 1996.
5. Haché (G.) et Le Brigand (D.). -- Effective construction of algebraic geometry codes. IEEE Transaction on Information Theory, vol. 41, n'27 6, November 1995, pp. 1615--1628.
6. Huang (M.D.) et Ierardi (D.). -- Efficient algorithms for Riemann-Roch problem and for addition in the jacobian of a curve. In: Proceedings 32nd Annual Symposium on Foundations of Computer Sciences. IEEE Comput. Soc. Press, pp. 678--687.
7. Le Brigand (D.) et Risler (J.J.). -- Algorithme de Brill-Noether et codes de Goppa. Bull. Soc. Math. France, vol. 116, 1988, pp. 231--253.
8. Stichtenoth (H.). -- Algebraic function fields and codes. -- Springer-Verlag, 1993, University Text.

Example 1

This example compute the genus of the projective plane curve defined by:

       5    2 3      4
      X  + Y Z  + Y Z  = 0

over the field GF(2).

First load the PAFF library (must be done twice).

fricas

(1) -> )lib )dir PAFF/spad

   >> System error:
   The value
  73494
is not of type
  LIST

fricas

-- First we define the field GF(2).

K:=PF 2

(1)

Type: Type

fricas

-- Next, we define the polynomial ring over which
-- the polynomial is defined. 
-- You have the choice for the name of 
-- the three variables (always three !!) but  
-- the domain  DMP must be used. 
-- DMP  is an AXIOM domain and stands for DistributedMultivariatePolymnomial.

R:=DMP([X,Y,Z],K)

(2)

Type: Type

fricas

-- Then we tell to the package PAFF over which field the computation must be done.
-- Also, you must give the same list of variables which is used to defined the polynomial.
-- BLQT Stand for BlowUpWithQuadTrans which specified the method
-- used for blowing-up (there will be another one (when ?) 
-- using similar thechnics to Hamburger-Nother expansions).

P:=PAFF(K,[X,Y,Z],BLQT)

   There are no library operations named PAFF 
      Use HyperDoc Browse or issue
                                )what op PAFF
      to learn if there is any operation containing " PAFF " in its 
      name.

   Cannot find a definition or applicable library operation named PAFF 
      with argument type(s) 
                                    Type
                     List(OrderedVariableList([X,Y,Z]))
                               Variable(BLQT)

      Perhaps you should use "@" to indicate the required return type, 
      or "$" to specify which version of the function you need.