Hyperelliptic Curves and Quadratic Residue Codes
David Joyner, Jon-Lark Kim · Applied and numerical harmonic analysis · 2011
For an odd prime p and a nonempty subset S⊂GF(p), consider the hyperelliptic curve X S defined by $$y^2=f_S(x),$$ where f S (x)=∏a∈S(x−a). Since the days of E. Artin in the early 1900s, mathematicians have searched for good estimates for the number of points on such curves. In the late 1940s and early 1950s, A. Weil developed good estimates when the genus is small relative to the size of the prime p. When the genus is large compared to p, good estimates are still unknown. A long-standing problem has been to develop “good” binary linear codes to be used for error-correction. For example, is the Gilbert–Varshamov bound asymptotically exact in the case of binary codes? This chapter is devoted to explaining a basic link between these two unsolved problems. Using a connection between binary quadratic residue codes and hyperelliptic curves over GF(p), this chapter investigates how coding theory bounds give rise to bounds such as the following example: for all sufficiently large primes p, there exists a subset S⊂GF(p) for which the bound |X S (GF(p))|>1.39p holds.