login  home  contents  what's new  discussion  bug reports help  links  subscribe  changes  refresh  edit

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
)lib )dir PAFF/spad
UnivariateTaylorSeriesCZero is now explicitly exposed in frame
initial
UnivariateTaylorSeriesCZero will be automatically loaded when needed
SetCategoryWithDegree is now explicitly exposed in frame initial
SetCategoryWithDegree will be automatically loaded when needed from
RootsFindingPackage is now explicitly exposed in frame initial
RootsFindingPackage will be automatically loaded when needed from
ProjectiveSpaceCategory is now explicitly exposed in frame initial
ProjectiveSpaceCategory will be automatically loaded when needed
ProjectiveSpace is now explicitly exposed in frame initial
ProjectiveSpace will be automatically loaded when needed from
ProjectivePlaneOverPseudoAlgebraicClosureOfFiniteField is now
explicitly exposed in frame initial
ProjectivePlaneOverPseudoAlgebraicClosureOfFiniteField will be
ProjectivePlane is now explicitly exposed in frame initial
ProjectivePlane will be automatically loaded when needed from
ProjectiveAlgebraicSetPackage is now explicitly exposed in frame
initial
ProjectiveAlgebraicSetPackage will be automatically loaded when
needed from
PolynomialPackageForCurve is now explicitly exposed in frame initial
PolynomialPackageForCurve will be automatically loaded when needed
Plcs is now explicitly exposed in frame initial
Plcs will be automatically loaded when needed from
PlacesOverPseudoAlgebraicClosureOfFiniteField is now explicitly
exposed in frame initial
PlacesOverPseudoAlgebraicClosureOfFiniteField will be automatically
PlacesCategory is now explicitly exposed in frame initial
PlacesCategory will be automatically loaded when needed from
Places is now explicitly exposed in frame initial
Places will be automatically loaded when needed from
PackageForPoly is now explicitly exposed in frame initial
PackageForPoly will be automatically loaded when needed from
ParametrizationPackage is now explicitly exposed in frame initial
ParametrizationPackage will be automatically loaded when needed from
PackageForAlgebraicFunctionFieldOverFiniteField is now explicitly
exposed in frame initial
PackageForAlgebraicFunctionFieldOverFiniteField will be
PackageForAlgebraicFunctionField is now explicitly exposed in frame
initial
PackageForAlgebraicFunctionField will be automatically loaded when
PseudoAlgebraicClosureOfRationalNumberCategory is now explicitly
exposed in frame initial
PseudoAlgebraicClosureOfRationalNumberCategory will be automatically
PseudoAlgebraicClosureOfRationalNumber is now explicitly exposed in
frame initial
when needed from
PseudoAlgebraicClosureOfPerfectFieldCategory is now explicitly
exposed in frame initial
PseudoAlgebraicClosureOfPerfectFieldCategory will be automatically
PseudoAlgebraicClosureOfFiniteField is now explicitly exposed in
frame initial
when needed from
PseudoAlgebraicClosureOfFiniteFieldCategory is now explicitly
exposed in frame initial
PseudoAlgebraicClosureOfFiniteFieldCategory will be automatically
PseudoAlgebraicClosureOfAlgExtOfRationalNumberCategory is now
explicitly exposed in frame initial
PseudoAlgebraicClosureOfAlgExtOfRationalNumberCategory will be
PseudoAlgebraicClosureOfAlgExtOfRationalNumber is now explicitly
exposed in frame initial
PseudoAlgebraicClosureOfAlgExtOfRationalNumber will be automatically
NeitherSparseOrDensePowerSeries is now explicitly exposed in frame
initial
NeitherSparseOrDensePowerSeries will be automatically loaded when
NewtonPolygon is now explicitly exposed in frame initial
NewtonPolygon will be automatically loaded when needed from
LocalParametrizationOfSimplePointPackage is now explicitly exposed
in frame initial
LocalParametrizationOfSimplePointPackage will be automatically
LinesOpPack is now explicitly exposed in frame initial
LinesOpPack will be automatically loaded when needed from
LocalPowerSeriesCategory is now explicitly exposed in frame initial
LocalPowerSeriesCategory will be automatically loaded when needed
LinearSystemFromPowerSeriesPackage is now explicitly exposed in
frame initial
LinearSystemFromPowerSeriesPackage will be automatically loaded when
InterpolateFormsPackage is now explicitly exposed in frame initial
InterpolateFormsPackage will be automatically loaded when needed
InterfaceGroebnerPackage is now explicitly exposed in frame initial
InterfaceGroebnerPackage will be automatically loaded when needed
IntersectionDivisorPackage is now explicitly exposed in frame
initial
IntersectionDivisorPackage will be automatically loaded when needed
InfinitlyClosePoint is now explicitly exposed in frame initial
InfinitlyClosePoint will be automatically loaded when needed from
InfinitlyClosePointOverPseudoAlgebraicClosureOfFiniteField is now
explicitly exposed in frame initial
InfinitlyClosePointOverPseudoAlgebraicClosureOfFiniteField will be
InfinitlyClosePointCategory is now explicitly exposed in frame
initial
InfinitlyClosePointCategory will be automatically loaded when needed
InfClsPt is now explicitly exposed in frame initial
InfClsPt will be automatically loaded when needed from
GeneralPackageForAlgebraicFunctionField is now explicitly exposed in
frame initial
when needed from
FiniteFieldSquareFreeDecomposition is now explicitly exposed in
frame initial
FiniteFieldSquareFreeDecomposition will be automatically loaded when
FiniteFieldFactorizationWithSizeParseBySideEffect is now explicitly
exposed in frame initial
FiniteFieldFactorizationWithSizeParseBySideEffect will be
FactorisationOverPseudoAlgebraicClosureOfRationalNumber is now
explicitly exposed in frame initial
FactorisationOverPseudoAlgebraicClosureOfRationalNumber will be
FactorisationOverPseudoAlgebraicClosureOfAlgExtOfRationalNumber is
now explicitly exposed in frame initial
FactorisationOverPseudoAlgebraicClosureOfAlgExtOfRationalNumber will
be automatically loaded when needed from
DesingTreePackage is now explicitly exposed in frame initial
DesingTreePackage will be automatically loaded when needed from
DesingTree is now explicitly exposed in frame initial
DesingTree will be automatically loaded when needed from
DesingTreeCategory is now explicitly exposed in frame initial
DesingTreeCategory will be automatically loaded when needed from
DivisorCategory is now explicitly exposed in frame initial
DivisorCategory will be automatically loaded when needed from
Divisor is now explicitly exposed in frame initial
Divisor will be automatically loaded when needed from
BlowUpPackage is now explicitly exposed in frame initial
BlowUpPackage will be automatically loaded when needed from
BlowUpWithQuadTrans is now explicitly exposed in frame initial
BlowUpMethodCategory is now explicitly exposed in frame initial
BlowUpMethodCategory will be automatically loaded when needed from
BlowUpWithHamburgerNoether is now explicitly exposed in frame
initial
BlowUpWithHamburgerNoether will be automatically loaded when needed
AffineSpaceCategory is now explicitly exposed in frame initial
AffineSpaceCategory will be automatically loaded when needed from
AffineSpace is now explicitly exposed in frame initial
AffineSpace will be automatically loaded when needed from
AffinePlaneOverPseudoAlgebraicClosureOfFiniteField is now explicitly
exposed in frame initial
AffinePlaneOverPseudoAlgebraicClosureOfFiniteField will be
AffinePlane is now explicitly exposed in frame initial
AffinePlane will be automatically loaded when needed from
AffineAlgebraicSetComputeWithResultant is now explicitly exposed in
frame initial
when needed from
AffineAlgebraicSetComputeWithGroebnerBasis is now explicitly exposed
in frame initial
AffineAlgebraicSetComputeWithGroebnerBasis will be automatically
/var/aw/var/LatexWiki/PAFF/spad/AFALGGRO.NRLIB/AFALGGRO
fricas
)lib )dir PAFF/spad
UnivariateTaylorSeriesCZero is already explicitly exposed in frame
initial
UnivariateTaylorSeriesCZero will be automatically loaded when needed
SetCategoryWithDegree is already explicitly exposed in frame initial
SetCategoryWithDegree will be automatically loaded when needed from
RootsFindingPackage is already explicitly exposed in frame initial
RootsFindingPackage will be automatically loaded when needed from
ProjectiveSpaceCategory is already explicitly exposed in frame
initial
ProjectiveSpaceCategory will be automatically loaded when needed
ProjectiveSpace is already explicitly exposed in frame initial
ProjectiveSpace will be automatically loaded when needed from
explicitly exposed in frame initial
ProjectivePlaneOverPseudoAlgebraicClosureOfFiniteField will be
ProjectivePlane is already explicitly exposed in frame initial
ProjectivePlane will be automatically loaded when needed from
ProjectiveAlgebraicSetPackage is already explicitly exposed in frame
initial
ProjectiveAlgebraicSetPackage will be automatically loaded when
needed from
PolynomialPackageForCurve is already explicitly exposed in frame
initial
PolynomialPackageForCurve will be automatically loaded when needed
Plcs is already explicitly exposed in frame initial
Plcs will be automatically loaded when needed from
exposed in frame initial
PlacesOverPseudoAlgebraicClosureOfFiniteField will be automatically
PlacesCategory is already explicitly exposed in frame initial
PlacesCategory will be automatically loaded when needed from
Places is already explicitly exposed in frame initial
Places will be automatically loaded when needed from
PackageForPoly is already explicitly exposed in frame initial
PackageForPoly will be automatically loaded when needed from
ParametrizationPackage is already explicitly exposed in frame
initial
ParametrizationPackage will be automatically loaded when needed from
explicitly exposed in frame initial
PackageForAlgebraicFunctionFieldOverFiniteField will be
PackageForAlgebraicFunctionField is already explicitly exposed in
frame initial
PackageForAlgebraicFunctionField will be automatically loaded when
exposed in frame initial
PseudoAlgebraicClosureOfRationalNumberCategory will be automatically
in frame initial
when needed from
exposed in frame initial
PseudoAlgebraicClosureOfPerfectFieldCategory will be automatically
PseudoAlgebraicClosureOfFiniteField is already explicitly exposed in
frame initial
when needed from
exposed in frame initial
PseudoAlgebraicClosureOfFiniteFieldCategory will be automatically
explicitly exposed in frame initial
PseudoAlgebraicClosureOfAlgExtOfRationalNumberCategory will be
exposed in frame initial
PseudoAlgebraicClosureOfAlgExtOfRationalNumber will be automatically
NeitherSparseOrDensePowerSeries is already explicitly exposed in
frame initial
NeitherSparseOrDensePowerSeries will be automatically loaded when
NewtonPolygon is already explicitly exposed in frame initial
NewtonPolygon will be automatically loaded when needed from
exposed in frame initial
LocalParametrizationOfSimplePointPackage will be automatically
LinesOpPack is already explicitly exposed in frame initial
LinesOpPack will be automatically loaded when needed from
LocalPowerSeriesCategory is already explicitly exposed in frame
initial
LocalPowerSeriesCategory will be automatically loaded when needed
LinearSystemFromPowerSeriesPackage is already explicitly exposed in
frame initial
LinearSystemFromPowerSeriesPackage will be automatically loaded when
InterpolateFormsPackage is already explicitly exposed in frame
initial
InterpolateFormsPackage will be automatically loaded when needed
InterfaceGroebnerPackage is already explicitly exposed in frame
initial
InterfaceGroebnerPackage will be automatically loaded when needed
IntersectionDivisorPackage is already explicitly exposed in frame
initial
IntersectionDivisorPackage will be automatically loaded when needed
InfinitlyClosePoint is already explicitly exposed in frame initial
InfinitlyClosePoint will be automatically loaded when needed from
InfinitlyClosePointOverPseudoAlgebraicClosureOfFiniteField is
already explicitly exposed in frame initial
InfinitlyClosePointOverPseudoAlgebraicClosureOfFiniteField will be
InfinitlyClosePointCategory is already explicitly exposed in frame
initial
InfinitlyClosePointCategory will be automatically loaded when needed
InfClsPt is already explicitly exposed in frame initial
InfClsPt will be automatically loaded when needed from
exposed in frame initial
when needed from
FiniteFieldSquareFreeDecomposition is already explicitly exposed in
frame initial
FiniteFieldSquareFreeDecomposition will be automatically loaded when
explicitly exposed in frame initial
FiniteFieldFactorizationWithSizeParseBySideEffect will be
explicitly exposed in frame initial
FactorisationOverPseudoAlgebraicClosureOfRationalNumber will be
FactorisationOverPseudoAlgebraicClosureOfAlgExtOfRationalNumber is
already explicitly exposed in frame initial
FactorisationOverPseudoAlgebraicClosureOfAlgExtOfRationalNumber will
be automatically loaded when needed from
DesingTreePackage is already explicitly exposed in frame initial
DesingTreePackage will be automatically loaded when needed from
DesingTree is already explicitly exposed in frame initial
DesingTree will be automatically loaded when needed from
DesingTreeCategory is already explicitly exposed in frame initial
DesingTreeCategory will be automatically loaded when needed from
DivisorCategory is already explicitly exposed in frame initial
DivisorCategory will be automatically loaded when needed from
Divisor is already explicitly exposed in frame initial
Divisor will be automatically loaded when needed from
BlowUpPackage is already explicitly exposed in frame initial
BlowUpPackage will be automatically loaded when needed from
BlowUpMethodCategory is already explicitly exposed in frame initial
BlowUpMethodCategory will be automatically loaded when needed from
BlowUpWithHamburgerNoether is already explicitly exposed in frame
initial
BlowUpWithHamburgerNoether will be automatically loaded when needed
AffineSpaceCategory is already explicitly exposed in frame initial
AffineSpaceCategory will be automatically loaded when needed from
AffineSpace is already explicitly exposed in frame initial
AffineSpace will be automatically loaded when needed from
explicitly exposed in frame initial
AffinePlaneOverPseudoAlgebraicClosureOfFiniteField will be
AffinePlane is already explicitly exposed in frame initial
AffinePlane will be automatically loaded when needed from
in frame initial
when needed from
exposed in frame initial
AffineAlgebraicSetComputeWithGroebnerBasis will be automatically
/var/aw/var/LatexWiki/PAFF/spad/AFALGGRO.NRLIB/AFALGGRO

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)
 (3)
Type: Type
fricas
-- We defined now the polynomial of the curve.
C:R:=X**5 + Y**2*Z**3+Y*Z**4
There are no library operations named **
Use HyperDoc Browse or issue
)what op **
to learn if there is any operation containing " ** " in its name.
Cannot find a definition or applicable library operation named **
with argument type(s)
DistributedMultivariatePolynomial([X,Y,Z],PrimeField(2))
PositiveInteger
Perhaps you should use "@" to indicate the required return type,
or "\$" to specify which version of the function you need.

 Subject:   Be Bold !! ( 15 subscribers )