Coding Theory 03: Curves, Divisors, and Riemann-Roch

Coding theory / 03

Curves, divisors, and Riemann-Roch

The passage from polynomial codes to AG codes replaces the projective line by an arbitrary smooth projective curve.

Let \(X/\mathbb F_q\) be a smooth projective curve with function field \(\mathbb F_q(X)\). A divisor is a formal finite sum \(D=\sum_P n_P P\). It is effective, written \(D\ge0\), if all coefficients are nonnegative. A nonzero rational function \(f\) has divisor

\[(f)=\sum_P v_P(f)P,\]

recording zeros and poles. Two divisors are linearly equivalent when they differ by a principal divisor. The quotient of divisors by principal divisors is the Picard group.

For a divisor \(G\), the Riemann-Roch space is

\[L(G)=\{f\in\mathbb F_q(X)^*:(f)+G\ge0\}\cup\{0\}.\]

It consists of rational functions whose poles are bounded by \(G\).

Example 1: the projective line

On \(\mathbb P^1\) with coordinate \(x\) and point \(P_\infty\), the space \(L(mP_\infty)\) is spanned by

\[1,x,x^2,\ldots,x^m.\]

Thus Reed-Solomon codes are AG codes on \(\mathbb P^1\): the pole bound is simply a polynomial degree bound.

Example 2: an elliptic curve has a pole-order gap

On an elliptic curve with point \(O\), there is no nonconstant function with a single simple pole at \(O\). The first nonconstant spaces are generated by functions with pole orders \(2\) and \(3\). This gap is one visible effect of genus in decoding.

Riemann-Roch

Let \(K\) be a canonical divisor and \(g\) the genus. The Riemann-Roch theorem says

\[\ell(G)-\ell(K-G)=\deg G+1-g,\]

where \(\ell(G)=\dim_{\mathbb F_q}L(G)\). If \(\deg G>2g-2\), then \(\ell(K-G)=0\) and

\[\ell(G)=\deg G+1-g.\]

This formula is the source of the dimension estimates in Chapter 2.

Example 3: genus zero gives exact polynomial dimension

For \(X=\mathbb P^1\), \(g=0\) and \(K\sim -2P_\infty\). For \(G=mP_\infty\) with \(m\ge0\), Riemann-Roch gives \(\ell(G)=m+1\), matching the basis \(1,x,\ldots,x^m\).

Example 4: genus one changes the count by one

For an elliptic curve, \(g=1\) and a canonical divisor has degree \(0\). If \(G=mO\) with \(m>0\), then \(\ell(G)=m\). The loss of one dimension compared with \(\mathbb P^1\) is the genus correction.

Differentials and residues

A rational differential \(\omega\) has a divisor \((\omega)\) of zeros and poles. Its residue at a point \(P\) is denoted \(\operatorname{res}_P(\omega)\). The global residue theorem says the sum of all residues is zero. This theorem is what later makes residue codes dual to evaluation codes.

Example 5: residues on the line

On \(\mathbb P^1\), the differential \(dx/(x-a)\) has residue \(1\) at \(x=a\) and residue \(-1\) at infinity. This is the simplest instance of the global residue theorem.

Example 6: principal divisors have degree zero

For \(f=(x-a)/(x-b)\) on \(\mathbb P^1\), the divisor is \((a)-(b)\). It has degree zero. Linear equivalence therefore preserves degree, which is why degree is the first numerical invariant of a divisor class on a curve.