AG codes#

Algebraic geometry codes or shortly AG codes are linear codes defined using functions or differentials on algebraic curves over finite fields. Sage implements evaluation AG codes and differential AG codes as Goppa defined in [Gop1981] and provides decoding algorithms for them in full generality.

EXAMPLES:

sage: k.<a> = GF(4)
sage: A.<x,y> = AffineSpace(k, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: pls.remove(Q)
sage: G = 5*Q
sage: codes.EvaluationAGCode(pls, G)
[8, 5] evaluation AG code over GF(4)
sage: codes.DifferentialAGCode(pls, G)
[8, 3] differential AG code over GF(4)

>>> from sage.all import *
>>> k = GF(Integer(4), names=('a',)); (a,) = k._first_ngens(1)
>>> A = AffineSpace(k, Integer(2), names=('x', 'y',)); (x, y,) = A._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> pls.remove(Q)
>>> G = Integer(5)*Q
>>> codes.EvaluationAGCode(pls, G)
[8, 5] evaluation AG code over GF(4)
>>> codes.DifferentialAGCode(pls, G)
[8, 3] differential AG code over GF(4)

As is well known, the two kinds of AG codes are dual to each other.

sage: E = codes.EvaluationAGCode(pls, G)
sage: D = codes.DifferentialAGCode(pls, G)
sage: E.dual_code() == D
True
sage: D.dual_code() == E
True

>>> from sage.all import *
>>> E = codes.EvaluationAGCode(pls, G)
>>> D = codes.DifferentialAGCode(pls, G)
>>> E.dual_code() == D
True
>>> D.dual_code() == E
True

Decoders for both evaluation and differential AG codes are available.

A natural generalization of classical Goppa codes is Cartier codes [Cou2014]. Cartier codes are subfield subcodes of differential AG codes.

EXAMPLES:

sage: F.<a> = GF(9)
sage: P.<x,y,z> = ProjectiveSpace(F, 2);
sage: C = Curve(x^3*y + y^3*z + x*z^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: Z, = C([0,0,1]).places()
sage: pls.remove(Z)
sage: G = 3*Z
sage: codes.CartierCode(pls, G)  # long time
[9, 4] Cartier code over GF(3)

>>> from sage.all import *
>>> F = GF(Integer(9), names=('a',)); (a,) = F._first_ngens(1)
>>> P = ProjectiveSpace(F, Integer(2), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3);
>>> C = Curve(x**Integer(3)*y + y**Integer(3)*z + x*z**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> Z, = C([Integer(0),Integer(0),Integer(1)]).places()
>>> pls.remove(Z)
>>> G = Integer(3)*Z
>>> codes.CartierCode(pls, G)  # long time
[9, 4] Cartier code over GF(3)

AUTHORS:

  • Kwankyu Lee (2019-03): initial version

class sage.coding.ag_code.AGCode(base_field, length, default_encoder_name, default_decoder_name)[source]#

Bases: AbstractLinearCode

Base class of algebraic geometry codes.

A subclass of this class is required to define _function_field attribute that refers to an abstract functiom field or the function field of the underlying curve used to construct a code of the class.

base_function_field()[source]#

Return the function field used to construct the code.

EXAMPLES:

sage: k.<a> = GF(4)
sage: A.<x,y> = AffineSpace(k, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: pls.remove(Q)
sage: G = 5*Q
sage: code = codes.EvaluationAGCode(pls, G)
sage: code.base_function_field()
Function field in y defined by y^2 + y + x^3

>>> from sage.all import *
>>> k = GF(Integer(4), names=('a',)); (a,) = k._first_ngens(1)
>>> A = AffineSpace(k, Integer(2), names=('x', 'y',)); (x, y,) = A._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> pls.remove(Q)
>>> G = Integer(5)*Q
>>> code = codes.EvaluationAGCode(pls, G)
>>> code.base_function_field()
Function field in y defined by y^2 + y + x^3
class sage.coding.ag_code.CartierCode(pls, G, r=1, name=None)[source]#

Bases: AGCode

Cartier code defined by rational places pls and a divisor G of a function field.

INPUT:

  • pls – a list of rational places

  • G – a divisor whose support is disjoint from pls

  • r – integer (default: 1)

  • name – string; name of the generator of the subfield \(\GF{p^r}\)

OUTPUT: Cartier code over \(\GF{p^r}\) where \(p\) is the characteristic of the base constant field of the function field

Note that if r is 1 the default, then name can be omitted.

EXAMPLES:

sage: F.<a> = GF(9)
sage: P.<x,y,z> = ProjectiveSpace(F, 2);
sage: C = Curve(x^3*y + y^3*z + x*z^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: Z, = C(0,0,1).places()
sage: pls.remove(Z)
sage: G = 3*Z
sage: code = codes.CartierCode(pls, G)  # long time
sage: code.minimum_distance()           # long time
2

>>> from sage.all import *
>>> F = GF(Integer(9), names=('a',)); (a,) = F._first_ngens(1)
>>> P = ProjectiveSpace(F, Integer(2), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3);
>>> C = Curve(x**Integer(3)*y + y**Integer(3)*z + x*z**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> Z, = C(Integer(0),Integer(0),Integer(1)).places()
>>> pls.remove(Z)
>>> G = Integer(3)*Z
>>> code = codes.CartierCode(pls, G)  # long time
>>> code.minimum_distance()           # long time
2
designed_distance()[source]#

Return the designed distance of the Cartier code.

The designed distance is that of the differential code of which the Cartier code is a subcode.

EXAMPLES:

sage: F.<a> = GF(9)
sage: P.<x,y,z> = ProjectiveSpace(F, 2);
sage: C = Curve(x^3*y + y^3*z + x*z^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: Z, = C(0,0,1).places()
sage: pls.remove(Z)
sage: G = 3*Z
sage: code = codes.CartierCode(pls, G)  # long time
sage: code.designed_distance()          # long time
1

>>> from sage.all import *
>>> F = GF(Integer(9), names=('a',)); (a,) = F._first_ngens(1)
>>> P = ProjectiveSpace(F, Integer(2), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3);
>>> C = Curve(x**Integer(3)*y + y**Integer(3)*z + x*z**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> Z, = C(Integer(0),Integer(0),Integer(1)).places()
>>> pls.remove(Z)
>>> G = Integer(3)*Z
>>> code = codes.CartierCode(pls, G)  # long time
>>> code.designed_distance()          # long time
1
generator_matrix()[source]#

Return a generator matrix of the Cartier code.

EXAMPLES:

sage: F.<a> = GF(9)
sage: P.<x,y,z> = ProjectiveSpace(F, 2);
sage: C = Curve(x^3*y + y^3*z + x*z^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: Z, = C(0,0,1).places()
sage: pls.remove(Z)
sage: G = 3*Z
sage: code = codes.CartierCode(pls, G)  # long time
sage: code.generator_matrix()           # long time
[1 0 0 2 2 0 2 2 0]
[0 1 0 2 2 0 2 2 0]
[0 0 1 0 0 0 0 0 2]
[0 0 0 0 0 1 0 0 2]

>>> from sage.all import *
>>> F = GF(Integer(9), names=('a',)); (a,) = F._first_ngens(1)
>>> P = ProjectiveSpace(F, Integer(2), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3);
>>> C = Curve(x**Integer(3)*y + y**Integer(3)*z + x*z**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> Z, = C(Integer(0),Integer(0),Integer(1)).places()
>>> pls.remove(Z)
>>> G = Integer(3)*Z
>>> code = codes.CartierCode(pls, G)  # long time
>>> code.generator_matrix()           # long time
[1 0 0 2 2 0 2 2 0]
[0 1 0 2 2 0 2 2 0]
[0 0 1 0 0 0 0 0 2]
[0 0 0 0 0 1 0 0 2]
class sage.coding.ag_code.DifferentialAGCode(pls, G)[source]#

Bases: AGCode

Differential AG code defined by rational places pls and a divisor G

INPUT:

  • pls – a list of rational places of a function field

  • G – a divisor whose support is disjoint from pls

If G is a place, then it is regarded as a prime divisor.

EXAMPLES:

sage: k.<a> = GF(4)
sage: A.<x,y> = AffineSpace(k, 2)
sage: C = A.curve(y^3 + y - x^4)
sage: Q = C.places_at_infinity()[0]
sage: O = C([0,0]).place()
sage: pls = [p for p in C.places() if p not in [O, Q]]
sage: G = -O + 3*Q
sage: codes.DifferentialAGCode(pls, -O + Q)
[3, 2] differential AG code over GF(4)

sage: F = C.function_field()
sage: G = F.get_place(1)
sage: codes.DifferentialAGCode(pls, G)
[3, 1] differential AG code over GF(4)

>>> from sage.all import *
>>> k = GF(Integer(4), names=('a',)); (a,) = k._first_ngens(1)
>>> A = AffineSpace(k, Integer(2), names=('x', 'y',)); (x, y,) = A._first_ngens(2)
>>> C = A.curve(y**Integer(3) + y - x**Integer(4))
>>> Q = C.places_at_infinity()[Integer(0)]
>>> O = C([Integer(0),Integer(0)]).place()
>>> pls = [p for p in C.places() if p not in [O, Q]]
>>> G = -O + Integer(3)*Q
>>> codes.DifferentialAGCode(pls, -O + Q)
[3, 2] differential AG code over GF(4)

>>> F = C.function_field()
>>> G = F.get_place(Integer(1))
>>> codes.DifferentialAGCode(pls, G)
[3, 1] differential AG code over GF(4)
basis_differentials()[source]#

Return the basis differentials associated with the generator matrix.

EXAMPLES:

sage: k.<a> = GF(4)
sage: A.<x,y> = AffineSpace(k, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: Q, = C.places_at_infinity()
sage: pls.remove(Q)
sage: code = codes.DifferentialAGCode(pls, 3*Q)
sage: matrix([[w.residue(p) for p in pls]
....:         for w in code.basis_differentials()])
[    1     0     0     0     0 a + 1 a + 1     1]
[    0     1     0     0     0 a + 1     a     0]
[    0     0     1     0     0     a     1     a]
[    0     0     0     1     0     a     0 a + 1]
[    0     0     0     0     1     1     1     1]

>>> from sage.all import *
>>> k = GF(Integer(4), names=('a',)); (a,) = k._first_ngens(1)
>>> A = AffineSpace(k, Integer(2), names=('x', 'y',)); (x, y,) = A._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> Q, = C.places_at_infinity()
>>> pls.remove(Q)
>>> code = codes.DifferentialAGCode(pls, Integer(3)*Q)
>>> matrix([[w.residue(p) for p in pls]
...         for w in code.basis_differentials()])
[    1     0     0     0     0 a + 1 a + 1     1]
[    0     1     0     0     0 a + 1     a     0]
[    0     0     1     0     0     a     1     a]
[    0     0     0     1     0     a     0 a + 1]
[    0     0     0     0     1     1     1     1]
designed_distance()[source]#

Return the designed distance of the differential AG code.

If the code is of dimension zero, then a ValueError is raised.

EXAMPLES:

sage: k.<a> = GF(4)
sage: A.<x,y> = AffineSpace(k, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: Q, = C.places_at_infinity()
sage: pls.remove(Q)
sage: code = codes.DifferentialAGCode(pls, 3*Q)
sage: code.designed_distance()
3

>>> from sage.all import *
>>> k = GF(Integer(4), names=('a',)); (a,) = k._first_ngens(1)
>>> A = AffineSpace(k, Integer(2), names=('x', 'y',)); (x, y,) = A._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> Q, = C.places_at_infinity()
>>> pls.remove(Q)
>>> code = codes.DifferentialAGCode(pls, Integer(3)*Q)
>>> code.designed_distance()
3
generator_matrix()[source]#

Return a generator matrix of the code.

EXAMPLES:

sage: k.<a> = GF(4)
sage: A.<x,y> = AffineSpace(k, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: Q, = C.places_at_infinity()
sage: pls.remove(Q)
sage: code = codes.DifferentialAGCode(pls, 3*Q)
sage: code.generator_matrix()
[    1     0     0     0     0 a + 1 a + 1     1]
[    0     1     0     0     0 a + 1     a     0]
[    0     0     1     0     0     a     1     a]
[    0     0     0     1     0     a     0 a + 1]
[    0     0     0     0     1     1     1     1]

>>> from sage.all import *
>>> k = GF(Integer(4), names=('a',)); (a,) = k._first_ngens(1)
>>> A = AffineSpace(k, Integer(2), names=('x', 'y',)); (x, y,) = A._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> Q, = C.places_at_infinity()
>>> pls.remove(Q)
>>> code = codes.DifferentialAGCode(pls, Integer(3)*Q)
>>> code.generator_matrix()
[    1     0     0     0     0 a + 1 a + 1     1]
[    0     1     0     0     0 a + 1     a     0]
[    0     0     1     0     0     a     1     a]
[    0     0     0     1     0     a     0 a + 1]
[    0     0     0     0     1     1     1     1]
class sage.coding.ag_code.EvaluationAGCode(pls, G)[source]#

Bases: AGCode

Evaluation AG code defined by rational places pls and a divisor G.

INPUT:

  • pls – a list of rational places of a function field

  • G – a divisor whose support is disjoint from pls

If G is a place, then it is regarded as a prime divisor.

EXAMPLES:

sage: k.<a> = GF(4)
sage: A.<x,y> = AffineSpace(k, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: Q, = C.places_at_infinity()
sage: pls.remove(Q)
sage: G = 5*Q
sage: codes.EvaluationAGCode(pls, G)
[8, 5] evaluation AG code over GF(4)

sage: G = F.get_place(5)
sage: codes.EvaluationAGCode(pls, G)
[8, 5] evaluation AG code over GF(4)

>>> from sage.all import *
>>> k = GF(Integer(4), names=('a',)); (a,) = k._first_ngens(1)
>>> A = AffineSpace(k, Integer(2), names=('x', 'y',)); (x, y,) = A._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> Q, = C.places_at_infinity()
>>> pls.remove(Q)
>>> G = Integer(5)*Q
>>> codes.EvaluationAGCode(pls, G)
[8, 5] evaluation AG code over GF(4)

>>> G = F.get_place(Integer(5))
>>> codes.EvaluationAGCode(pls, G)
[8, 5] evaluation AG code over GF(4)
basis_functions()[source]#

Return the basis functions associated with the generator matrix.

EXAMPLES:

sage: k.<a> = GF(4)
sage: A.<x,y> = AffineSpace(k, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: Q, = C.places_at_infinity()
sage: pls.remove(Q)
sage: code = codes.EvaluationAGCode(pls, 3*Q)
sage: code.basis_functions()
(y + a*x + 1, y + x, (a + 1)*x)
sage: matrix([[f.evaluate(p) for p in pls] for f in code.basis_functions()])
[    1     0     0     1     a a + 1     1     0]
[    0     1     0     1     1     0 a + 1     a]
[    0     0     1     1     a     a a + 1 a + 1]

>>> from sage.all import *
>>> k = GF(Integer(4), names=('a',)); (a,) = k._first_ngens(1)
>>> A = AffineSpace(k, Integer(2), names=('x', 'y',)); (x, y,) = A._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> Q, = C.places_at_infinity()
>>> pls.remove(Q)
>>> code = codes.EvaluationAGCode(pls, Integer(3)*Q)
>>> code.basis_functions()
(y + a*x + 1, y + x, (a + 1)*x)
>>> matrix([[f.evaluate(p) for p in pls] for f in code.basis_functions()])
[    1     0     0     1     a a + 1     1     0]
[    0     1     0     1     1     0 a + 1     a]
[    0     0     1     1     a     a a + 1 a + 1]
designed_distance()[source]#

Return the designed distance of the AG code.

If the code is of dimension zero, then a ValueError is raised.

EXAMPLES:

sage: k.<a> = GF(4)
sage: A.<x,y> = AffineSpace(k, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: Q, = C.places_at_infinity()
sage: pls.remove(Q)
sage: code = codes.EvaluationAGCode(pls, 3*Q)
sage: code.designed_distance()
5

>>> from sage.all import *
>>> k = GF(Integer(4), names=('a',)); (a,) = k._first_ngens(1)
>>> A = AffineSpace(k, Integer(2), names=('x', 'y',)); (x, y,) = A._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> Q, = C.places_at_infinity()
>>> pls.remove(Q)
>>> code = codes.EvaluationAGCode(pls, Integer(3)*Q)
>>> code.designed_distance()
5
generator_matrix()[source]#

Return a generator matrix of the code.

EXAMPLES:

sage: k.<a> = GF(4)
sage: A.<x,y> = AffineSpace(k, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: Q, = C.places_at_infinity()
sage: pls.remove(Q)
sage: code = codes.EvaluationAGCode(pls, 3*Q)
sage: code.generator_matrix()
[    1     0     0     1     a a + 1     1     0]
[    0     1     0     1     1     0 a + 1     a]
[    0     0     1     1     a     a a + 1 a + 1]

>>> from sage.all import *
>>> k = GF(Integer(4), names=('a',)); (a,) = k._first_ngens(1)
>>> A = AffineSpace(k, Integer(2), names=('x', 'y',)); (x, y,) = A._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> Q, = C.places_at_infinity()
>>> pls.remove(Q)
>>> code = codes.EvaluationAGCode(pls, Integer(3)*Q)
>>> code.generator_matrix()
[    1     0     0     1     a a + 1     1     0]
[    0     1     0     1     1     0 a + 1     a]
[    0     0     1     1     a     a a + 1 a + 1]