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).

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

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

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

K:=PF 2

(1)

-- 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)

-- 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.