Algebraic Geometry Codes: The Goppa Construction and the TVZ Bound

Intuition Beginner

Reed-Solomon codes are powerful error-correcting codes built from polynomials. You evaluate a polynomial of degree less than $k$ at $n$ distinct points. The result is a codeword of length $n$, and the code can correct up to $(n-k)/2$ errors. The trick is that two distinct polynomials of degree less than $k$ can agree on at most $k-1$ points.

Valery Goppa had an idea in 1970: what if instead of evaluating polynomials (which live on a line), you evaluate more general functions on a curve? A curve is a one-dimensional geometric object — a circle, an ellipse, or more exotic shapes defined over finite fields. Functions on a curve have more room than polynomials on a line, and this extra room translates into better codes.

The key parameter is the genus of the curve, written $g$. The genus measures the complexity of the curve. A line (or any conic) has genus 0. An elliptic curve has genus 1. A curve of genus $g$ supports functions with up to about $g$ independent "holes" or constraints. The Riemann-Roch theorem tells you exactly how many independent functions a curve can support for a given level of complexity.

The Goppa construction evaluates these functions at rational points — points on the curve whose coordinates lie in the finite field ${\mathbb{F}}_q$. A curve of genus $g$ can have many rational points: by the Hasse-Weil bound, at least $q+1-2g\sqrt{q}$ and at most $q+1+2g\sqrt{q}$. More rational points mean longer codes.

The breakthrough came in 1982 when Tsfasman, Vladut, and Zink showed that for sufficiently large finite fields (where $q$ is a perfect square at least 49), these curve-based codes beat the Gilbert-Varshamov bound — the best known lower bound on code performance. This was the first time any explicit construction was shown to exceed GV, and it shocked the coding theory community.

Visual Beginner

Code family	Parameters	Asymptotic bound ($q$ large)
Reed-Solomon	$[n,k,n-k+1]$ over ${\mathbb{F}}_q$, $n\le q$	Singleton bound (optimal)
Gilbert-Varshamov	Existence only	$R\ge 1-H_q(\delta )$
AG codes (genus $g$)	$[n,k,d]$, $k+d\ge n+1-g$	$R+\delta \ge 1-1/(\sqrt{q}-1)$
TVZ (1982)	$q\ge 49$ a square	Beats GV for $\delta$ in certain range

Figure: A graph showing the rate-distance trade-off. The horizontal axis is relative distance $\delta =d/n$, the vertical axis is rate $R=k/n$. The Gilbert-Varshamov lower bound curves upward from $(0,1)$ to $(1-1/q,0)$. The TVZ line $R+\delta =1-1/(\sqrt{q}-1)$ sits above the GV curve for $\delta$ roughly between 0.05 and 0.35 when $q=49$. The Singleton bound $R+\delta =1$ is the absolute ceiling. The plot shows the TVZ line passing above the GV curve in the middle range, marking the first explicit construction to do so.

Worked example Beginner

Consider the Hermitian curve over ${\mathbb{F}}_4=\{0,1,\alpha ,{\alpha }^2\}$ where ${\alpha }^2+\alpha +1=0$. The curve is defined by the equation $y^2+y=x^3$.

This curve has genus $g=1$ (it is an elliptic curve over ${\mathbb{F}}_4$). Let us count the rational points. Over ${\mathbb{F}}_4$, there are 4 possible $x$-values and 4 possible $y$-values, but not all pairs satisfy the equation. The Hasse-Weil bound gives $N\ge q+1-2g\sqrt{q}=4+1-2\sqrt{4}=5-4=1$ and $N\le 4+1+4=9$. Direct counting shows the curve has $N=5$ rational points (including the point at infinity).

For $n=5$ points and genus $g=1$, the Goppa construction gives a code with parameters satisfying $k+d\ge n+1-g=5+1-1=5$. If we choose $k=3$, then $d\ge 2$. So we get a $[5,3,2]$ code over ${\mathbb{F}}_4$.

The code is constructed by evaluating functions in the Riemann-Roch space $L(G)$ at the 5 rational points. For $G=3P_{\infty }$ (three times the point at infinity), $\dim L(G)=3$ by the Riemann-Roch theorem. A basis is $\{1,x,y\}$. Evaluating at each of the 5 rational points gives the 5 columns of the generator matrix, producing a $[5,3,2]$ code.

This is modest, but the power of the construction emerges at larger genus and larger fields. A curve of genus 50 over ${\mathbb{F}}_{49}$ with many rational points produces codes whose parameters beat the GV bound.

Check your understanding Beginner

Formal definition Intermediate+

Let $\mathcal{X}$ be a smooth projective algebraic curve of genus $g$ defined over the finite field ${\mathbb{F}}_q$. Let $\mathcal{X}({\mathbb{F}}_q)=\{P_1,P_2,\dots ,P_n\}$ be the set of ${\mathbb{F}}_q$-rational points on $\mathcal{X}$.

Definition (Divisor). A divisor on $\mathcal{X}$ is a formal finite sum $D={\sum }_P{a}_{P}P$ where $a_P\in \mathbb{Z}$ and only finitely many $a_P$ are nonzero. The degree of $D$ is $\mathrm{deg}D={\sum }_P{a}_P$.

Definition (Riemann-Roch space). For a divisor $G$ on $\mathcal{X}$, the Riemann-Roch space is:

$$L(G)=\{f\in {\mathbb{F}}_q(\mathcal{X}):(f)+G\ge 0\}\cup \{0\},$$

where $(f)$ is the principal divisor of $f$. The space $L(G)$ is a finite-dimensional vector space over ${\mathbb{F}}_q$.

Definition (Goppa code / Algebraic geometry code). Let $D=P_1+P_2+\cdots +P_n$ be the sum of $n$ distinct rational points, and let $G$ be a divisor with $\text{supp}(G)\cap \text{supp}(D)=\varnothing$ and $2g-2<\mathrm{deg}G<n$. The Goppa code $C_L(D,G)$ is the image of the evaluation map:

$${\text{ev}}_D:L(G)\to {\mathbb{F}}_q^n,f\mapsto (f(P_1),f(P_2),\dots ,f(P_n)).$$

Theorem (Code parameters). The code $C_L(D,G)$ has parameters $[n,k,d]$ where:

$$k=\dim L(G)-\dim L(G-D),d\ge n-\mathrm{deg}G.$$

If $\mathrm{deg}G>2g-2$, then $\dim L(G)=\mathrm{deg}G+1-g$ (by the Riemann-Roch theorem), and:

$$k=\mathrm{deg}G+1-g,d\ge n-\mathrm{deg}G.$$

Counterexamples to common slips

• The genus is fixed, the length grows. For Reed-Solomon codes (genus 0), the length is bounded by $n\le q$. For higher-genus curves, the length can exceed $q$ because curves of positive genus can have more than $q+1$ rational points.

• The minimum distance is a lower bound, not exact. The actual minimum distance may be larger than $n-\mathrm{deg}G$. Computing the exact distance requires knowledge of the specific curve and divisor.

• The TVZ bound requires $q$ to be a perfect square at least 49. For small $q$, AG codes do not beat GV. The construction uses modular curves whose existence is guaranteed only for certain field sizes.

Key theorem with proof Intermediate+

Theorem (TVZ bound, Tsfasman-Vladut-Zink 1982). For $q={\ell }^2$ with $\ell \ge 7$ a prime power, there exist sequences of AG codes over ${\mathbb{F}}_q$ with asymptotic parameters satisfying:

$$R+\delta \ge 1-\frac{1}{\sqrt{q}-1}.$$

This bound exceeds the Gilbert-Varshamov bound $R\ge 1-H_q(\delta )$ for certain values of $\delta$ when $q\ge 49$.

Proof sketch. The proof has three ingredients.

Step 1: Curves with many points. For $q={\ell }^2$, Ihara (1981) and Tsfasman-Vladut-Zink (1982) showed the existence of families of curves $\{{\mathcal{X}}_i\}$ over ${\mathbb{F}}_q$ of genus $g_i\to \infty$ with:

$$\underset{i\to \infty }{\lim }\frac{N_i}{g_i}\ge \sqrt{q}-1,$$

where $N_i=|{\mathcal{X}}_i({\mathbb{F}}_q)|$ is the number of rational points. This is achieved using modular curves $X_0(N)$ over ${\mathbb{F}}_{{\ell }^2}$, which have an exceptional number of rational points due to the theory of complex multiplication.

Step 2: Goppa construction gives good codes. For each curve ${\mathcal{X}}_i$ with $n_i$ rational points and genus $g_i$, choose $D_i$ as the sum of $n_i$ rational points and $G_i$ with $\mathrm{deg}{G}_i=\lfloor \alpha n_i\rfloor$ for some $0<\alpha <1$. The resulting code has:

$$k_i\ge \alpha n_i+1-g_i,d_i\ge n_i-\alpha n_i=(1-\alpha )n_i.$$

Step 3: Asymptotic analysis. The rate is $R_i=k_i/n_i\ge \alpha +(1-g_i)/n_i$. The relative distance is ${\delta }_i\ge 1-\alpha$. Since $n_i/g_i\ge \sqrt{q}-1$:

$$R_i\ge \alpha +\frac{1-g_i}{n_i}=\alpha -\frac{g_i-1}{n_i}\ge \alpha -\frac{1}{\sqrt{q}-1}.$$

Substituting $\alpha =1-\delta$:

$$R+\delta \ge 1-\frac{1}{\sqrt{q}-1}.\square$$

To show this beats GV, compare numerically. For $q=49$: TVZ gives $R+\delta \ge 1-1/6=5/6\approx 0.833$. The GV bound at $\delta =0.2$ gives $R\ge 1-H_{49}(0.2)\approx 1-0.569=0.431$, so $R+\delta \approx 0.631$. Since $0.833>0.631$, TVZ beats GV at this $\delta$.

Bridge. The TVZ bound builds toward the general theory of asymptotically good codes 40.06.06, where the central question is whether explicit constructions can match the GV existence lower bound. The Riemann-Roch theorem appears again in the theory of zeta functions of curves over finite fields 04.01.01 as the functional equation relating the number of rational points to the genus. The foundational reason AG codes beat GV is that curves over ${\mathbb{F}}_{q^2}$ can have many more rational points than expected from the Hasse-Weil bound alone — the Ihara constant $A(q)=\mathrm{limsup}N/g$ reaches $\sqrt{q}-1$ for square $q$. The central insight is that the geometric constraint $k+d\ge n+1-g$ weakens as $g/n\to 0$, and this is exactly the condition satisfied by curves with many rational points. Putting these together, the TVZ bound converts the existence of curves with many points into the existence of codes that beat the best known combinatorial lower bound.

Exercises Intermediate+

Lean formalization Intermediate+

Mathlib has CommRing, Field, FiniteField, Polynomial, and the beginnings of algebraic geometry (ProjectiveSpace, AffineVariety), but it does not define algebraic curves over finite fields, divisors on curves, Riemann-Roch spaces, or the evaluation map for Goppa codes. The genus of a curve, the Riemann-Roch theorem ($\dim L(G)=\mathrm{deg}G+1-g$ for $\mathrm{deg}G>2g-2$), the Hasse-Weil bound, and the TVZ construction using modular curves are all absent. The modular curve theory (level structures on elliptic curves, the theory of complex multiplication) is far beyond current Mathlib. A Codex.CodingTheory.AlgebraicGeometry module defining curves, divisors, and Riemann-Roch spaces over finite fields, with the evaluation map and code parameter bounds, would be the load-bearing first step. This unit ships without formalization.

Advanced results Master

The Riemann-Roch theorem

The Riemann-Roch theorem is the engine that drives AG code parameters. For a smooth projective curve $\mathcal{X}$ of genus $g$ over ${\mathbb{F}}_q$ and a divisor $G$:

$$\dim L(G)=\mathrm{deg}G+1-g+\dim L(K-G),$$

where $K$ is the canonical divisor (the divisor of any nonzero differential form), with $\mathrm{deg}K=2g-2$. When $\mathrm{deg}G>2g-2$, the term $\dim L(K-G)=0$ (since $\mathrm{deg}(K-G)<0$ and no nonzero function can have poles bounded by a negative-degree divisor), giving the simplified formula $\dim L(G)=\mathrm{deg}G+1-g$.

For the Goppa construction, we need $\mathrm{deg}G$ in the range $(2g-2,n)$. This ensures $\dim L(G)$ is exactly computable and the evaluation map is injective. The code parameters then satisfy:

$$k=\mathrm{deg}G+1-g,d\ge n-\mathrm{deg}G.$$

Eliminating $\mathrm{deg}G$: $k+d\ge n+1-g$. Compare with the Singleton bound $k+d\le n+1$. The "gap" is exactly the genus $g$. For genus 0 (the projective line), AG codes achieve the Singleton bound (these are RS codes). For positive genus, the gap reduces the achievable parameters but allows longer codes (more rational points than the field size).

The Drinfeld-Vladut bound

The asymptotic performance of AG codes depends on the ratio $N/g$ — the number of rational points per unit of genus. The Drinfeld-Vladut bound (1983) shows:

$$A(q)=\underset{g\to \infty }{\mathrm{limsup}}\frac{N_q(g)}{g}\le \sqrt{q}-1.$$

This means no family of curves can have $N/g$ exceeding $\sqrt{q}-1$. For square $q={\ell }^2$, this bound is tight (achieved by modular curves), giving $A(q)=\sqrt{q}-1$. For non-square $q$, the exact value of $A(q)$ is unknown but believed to be strictly less than $\sqrt{q}-1$.

The TVZ bound follows from $A(q)=\sqrt{q}-1$: the code rate satisfies $R\ge \alpha -g/N\ge \alpha -1/(\sqrt{q}-1)$, and with $\delta =1-\alpha$, we get $R+\delta \ge 1-1/(\sqrt{q}-1)$.

Decoding AG codes: the Skorobogatov-Vladut algorithm

Decoding AG codes is more involved than for RS codes, but polynomial-time algorithms exist. The fundamental approach (Skorobogatov and Vladut, 1988) extends the Berlekamp-Massey algorithm to the curve setting.

The key idea: to correct $t$ errors, find a function $f$ in a Riemann-Roch space $L(G^{\prime })$ for a suitable divisor $G^{\prime }$ that vanishes at the error positions. The divisor $G^{\prime }$ must satisfy $\mathrm{deg}{G}^{\prime }\ge t+g$, and the error positions are determined by the zeros of $f$. The algorithm runs in $O(n^3)$ time for fixed $q$ and genus.

More efficient algorithms (Guruswami-Sudan, 1999) can correct up to $n-\sqrt{n\cdot k}$ errors for RS codes and have analogues for AG codes. The basic Goppa decoding algorithm corrects up to $(d-1-g)/2$ errors, where the genus reduces the correction capability by $g/2$ compared to a Singleton-bound-achieving code.

Hermitian codes in detail

The Hermitian curve $y^q+y=x^{q+1}$ over ${\mathbb{F}}_{q^2}$ is the workhorse of AG code constructions because it has the maximum possible number of rational points for its genus. The genus is $g=q(q-1)/2$ and the number of rational points is $N=q^3+1$ (including the point at infinity).

For $q=2$ (${\mathbb{F}}_4$): $g=1$, $N=9$. For $q=4$ (${\mathbb{F}}_{16}$): $g=6$, $N=65$. For $q=8$ (${\mathbb{F}}_{64}$): $g=28$, $N=513$. The ratio $N/g$ approaches $2q/(q-1)\to 2$ as $q\to \infty$, which for $q^2$ fields gives $N/g\approx 2\sqrt{q^2}/(\sqrt{q^2}-1)\approx 2$, far below the Drinfeld-Vladut bound $q-1$.

Hermitian codes are popular in practice because the curve has a simple equation, the rational points can be enumerated efficiently, and the Riemann-Roch spaces have explicit bases (monomials $x^i{y}^j$ with $iq+j(q+1)\le \mathrm{deg}G$).

Synthesis. Algebraic geometry codes convert the existence of curves with many rational points into codes whose parameters beat the best known combinatorial lower bounds; the Riemann-Roch theorem is the central insight that determines the code parameters from the curve geometry. The TVZ bound is the bridge between algebraic geometry and coding theory: for $q\ge 49$ a square, $R+\delta \ge 1-1/(\sqrt{q}-1)$ exceeds the Gilbert-Varshamov bound. This generalises the RS construction from genus 0 to positive genus, where the penalty $g$ in the Singleton-like bound $k+d\ge n+1-g$ is compensated by the ability to have $n>q$ rational points. The Drinfeld-Vladut bound shows that $\sqrt{q}-1$ is the absolute ceiling on $N/g$, and the TVZ construction reaches it. Putting these together, AG codes demonstrate that algebraic structure (the geometry of curves) can produce codes that purely combinatorial methods cannot match, and the foundational reason is that the Riemann-Roch theorem translates geometric data (genus, divisor degree) directly into coding-theoretic data (dimension, minimum distance).

Full proof set Master

Proposition (Minimum distance of Goppa codes). The minimum distance of the Goppa code $C_L(D,G)$ satisfies $d\ge n-\mathrm{deg}G$.

Proof. Let $c=(f(P_1),\dots ,f(P_n))$ be a nonzero codeword, so $f\in L(G)$ is nonzero. The weight of $c$ is the number of positions where $f(P_i)\ne 0$. The number of zero positions is the number of $P_i$ where $f(P_i)=0$, which is the number of $P_i$ in the support of the divisor of zeros of $f$.

Since $f\in L(G)$: $(f)+G\ge 0$, so $(f)\ge -G$. The zeros of $f$ contribute positively to $(f)$, and the poles contribute negatively. The total degree $\mathrm{deg}(f)=0$. The number of zeros is $\mathrm{deg}(\text{zeros of }f)$, which equals $\mathrm{deg}(\text{poles of }f)$. Since $(f)\ge -G$, the poles are bounded by $G$: $\mathrm{deg}(\text{poles})\le \mathrm{deg}G$. Therefore $\mathrm{deg}(\text{zeros})\le \mathrm{deg}G$.

Each rational point $P_i$ where $f(P_i)=0$ contributes at least 1 to the zero count. So the number of zero positions is at most $\mathrm{deg}G$. The weight (number of nonzero positions) is at least $n-\mathrm{deg}G$. $\square$

Proposition (Injectivity of the evaluation map). If $\mathrm{deg}G<n$ and $\text{supp}(G)\cap \text{supp}(D)=\varnothing$, then ${\text{ev}}_D:L(G)\to {\mathbb{F}}_q^n$ is injective.

Proof. Suppose $f\in L(G)$ and $f(P_i)=0$ for all $i$. Then each $P_i$ is a zero of $f$ of order at least 1, so $(f)\ge D$. Since $f\in L(G)$: $(f)\ge -G$. Combining: $(f)\ge D-G^{\prime }$ for some effective divisor related to the poles. The degree of $(f)$ is 0, and the degree of the effective divisor $D$ (from the zeros) is $n$. The poles of $f$ have degree at most $\mathrm{deg}G$ (from $(f)\ge -G$). Since $\mathrm{deg}(f)=0$: degree of zeros $=$ degree of poles, so $n\le \mathrm{deg}G$. But $\mathrm{deg}G<n$ by hypothesis. Contradiction. Therefore $f=0$ and the map is injective. $\square$

Connections Master

• 46.07.01 — Weight enumerators and the LP bound provide the benchmark that AG codes beat; the MacWilliams identity gives the algebraic machinery for analysing AG code weight distributions.
• 40.06.06 — The Gilbert-Varshamov bound is the classical lower bound; AG codes are the first explicit family shown to exceed it for $q\ge 49$.
• 04.01.01 — Algebraic varieties are the geometric substrate; the Riemann-Roch theorem is the key result from algebraic geometry that determines code parameters.
• 46.01.01 — Entropy and the $q$-ary entropy function $H_q$ appear in the GV bound; the TVZ line is compared against the GV curve in the rate-distance plane.
• 46.03.01 — Channel capacity provides the Shannon limit; AG codes approach it with algebraic structure rather than random coding.

Historical & philosophical context Master

Valery Goppa introduced the construction of codes from algebraic curves in a series of papers starting in 1970. His insight was that the evaluation of functions on a curve — the same construction that gives Reed-Solomon codes from the projective line — could be generalised to arbitrary curves, with the Riemann-Roch theorem replacing the polynomial degree count. The initial papers (published in Russian in Problemy Peredachi Informatsii) attracted little attention outside the Soviet Union.

The breakthrough came in 1982 when Michael Tsfasman, Sergei Vladut, and Thomas Zink published their result showing that AG codes beat the Gilbert-Varshamov bound for $q\ge 49$. Their paper "Modular Curves, Shimura Curves, Goppa Codes, and Algebraic Geometry Codes" (appearing in Math. USSR Izvestiya 20, 317-330) used modular curves $X_0(N)$ over ${\mathbb{F}}_{{\ell }^2}$ to construct curves with an exceptional number of rational points. The result stunned the coding theory community because the GV bound had been believed to be tight for decades.

Yuri Ihara had independently established in 1981 that $A(q)\ge \sqrt{q}-1$ for square $q$, using the same modular curve construction. The Drinfeld-Vladut bound $A(q)\le \sqrt{q}-1$ (1983) then showed this was optimal. The combination of these results with Goppa's construction gave the TVZ bound as a corollary.

The philosophical significance is that purely combinatorial reasoning (counting arguments, sphere packing, linear programming) could not produce codes beating GV. The geometric approach — using the deep structure of curves over finite fields — provided the extra leverage. This demonstrated that coding theory is fundamentally connected to number theory and algebraic geometry, not merely an applied branch of combinatorics.

The practical impact was initially limited because the TVZ construction uses modular curves whose explicit equations are hard to compute. Later work by Garcia and Stichtenoth (1995, 1996) gave recursive tower constructions of curves with many points, making AG codes more practical. These towers are defined by simple recursive equations and reach the Drinfeld-Vladut bound without modular curves.

Bibliography Master

@book{macwilliams-sloane1977,
  author    = {MacWilliams, F. J. and Sloane, N. J. A.},
  title     = {The Theory of Error-Correcting Codes},
  publisher = {North-Holland},
  year      = {1977},
}
@article{tsfasman-vladut-zink1982,
  author  = {Tsfasman, M. A. and Vladut, S. G. and Zink, T.},
  title   = {Modular Curves, Shimura Curves, and Goppa Codes, Better Than {Varshamov-Gilbert} Bound},
  journal = {Math. USSR Izvestiya},
  volume  = {20},
  pages   = {317--330},
  year    = {1983},
  note    = {Russian original 1982},
}
@incollection{hoholdt-vanlint-pellikaan1998,
  author    = {H{\o}holdt, T. and van Lint, J. H. and Pellikaan, R.},
  title     = {Algebraic Geometry Codes},
  booktitle = {Handbook of Coding Theory},
  editor    = {Pless, V. S. and Huffman, W. C.},
  publisher = {Elsevier},
  year      = {1998},
}
@article{garcia-stichtenoth1995,
  author  = {Garcia, A. and Stichtenoth, H.},
  title   = {A Tower of Artin-Schreier Extensions of Function Fields Attaining the {Drinfeld-Vladut} Bound},
  journal = {Inventiones Mathematicae},
  volume  = {121},
  pages   = {211--222},
  year    = {1995},
}
@article{drinfeld-vladut1983,
  author  = {Drinfeld, V. G. and Vladut, S. G.},
  title   = {The Number of Points of an Algebraic Curve},
  journal = {Funktsional. Anal. i Prilozhen.},
  volume  = {17},
  pages   = {68--69},
  year    = {1983},
}
@book{tsfasman-vladut-nogin2007,
  author    = {Tsfasman, M. A. and Vladut, S. G. and Nogin, D.},
  title     = {Algebraic Geometric Codes: Basic Notions},
  publisher = {American Mathematical Society},
  year      = {2007},
}