Coding Theory 04: AG Evaluation Codes on Curves

Coding theory / 04

AG evaluation codes on curves

Goppa idea is to evaluate functions with controlled poles at many rational points of a curve.

Let \(X/\mathbb F_q\) be a smooth projective curve. Choose rational points \(P_1,\ldots,P_n\) and let \(D=P_1+\cdots+P_n\). Let \(G\) be a divisor with support disjoint from \(D\). The evaluation code is

\[C_L(D,G)=\{(f(P_1),\ldots,f(P_n)):f\in L(G)\}\subseteq\mathbb F_q^n.\]

The evaluation map is linear. Its kernel is \(L(G-D)\), because those functions vanish at every evaluation point. Hence

\[k=\ell(G)-\ell(G-D).\]

If \(n>\deg G\), then \(L(G-D)=0\) and \(k=\ell(G)\). If also \(\deg G>2g-2\), Riemann-Roch gives

\[k=\deg G+1-g.\]

Distance bound

A nonzero function \(f\in L(G)\) has at most \(\deg G\) zeros among the evaluation points, counted with multiplicity. Therefore every nonzero codeword has weight at least

\[d\ge n-\deg G.\]

This is the curve analogue of the fact that a nonzero degree \(m\) polynomial has at most \(m\) roots.

Example 1: Reed-Solomon as the genus-zero case

Take \(X=\mathbb P^1\), \(G=(k-1)P_\infty\), and evaluate at \(n\) finite rational points. Then \(L(G)\) consists of polynomials of degree at most \(k-1\). The code has parameters \([n,k,n-k+1]_q\) when the evaluation points are distinct.

Example 2: one-point elliptic codes

Let \(X\) be an elliptic curve with \(N\) rational points. Choose \(D\) as the sum of \(n=N-1\) rational points away from \(O\) and take \(G=mO\) with \(0<m<n\). Then \(k=m\) and \(d\ge n-m\). The construction resembles Reed-Solomon but uses functions on a genus-one curve.

Why many rational points matter

For fixed genus and pole degree, more rational evaluation points increase length without reducing dimension. This is why Chapter 2 quickly moves from the definition of AG codes to rational point counts and asymptotic bounds.

Example 3: same divisor, different length

If two elliptic curves over \(\mathbb F_q\) have different numbers of rational points, the same choice \(G=mO\) produces the same dimension estimate but different possible lengths. The curve with more rational points gives a longer code at the same pole budget.

Example 4: support disjointness is not cosmetic

If \(G=mO\) and one tries to evaluate at \(O\), functions in \(L(G)\) may have a pole there. The code definition requires evaluation points outside \(\operatorname{supp}(G)\) unless one chooses local normalizations that lead only to monomially equivalent variants.