We use the generating function approach to derive simple expressions for the factorial moments of the distance distribution over Reed-Solomon codes. We obtain better upper bounds for the error term of a counting formula given by Li and Wan, which gives nontrivial estimates on the number of polynomials over finite fields with prescribed leading coefficients and a given number of linear factors. This improvement leads to new results on the classification of deep holes of Reed-Solomon codes.

Let Fq be the finite field of q elements. In this paper we obtain bounds on the following counting problem: given a polynomial f (x) ∈ Fq[x] of degree k + m and a non-negative integer r, count the number of polynomials g(x) ∈ Fq[x] of degree at most k - 1 such that f (x) + g(x) has exactly r roots in Fq. Previously, explicit formulas were known only for the cases m = 0, 1, 2. As an application, we obtain an asymptotic formula on the list size of the standard Reed-Solomon code [q, k, q - k + 1]q.

For a linear code, deep holes are defined to be vectors that are further away from codewords than all other vectors. The problem of deciding whether a received word is a deep hole for generalized Reed-Solomon (GRS) codes is proved to be co-NP-complete by Guruswami and Vardy. For the extended Reed-Solomon codes RSq(Fq, k), a conjecture was made to classify deep holes by Cheng and Murray. Since then efforts have been made to prove the conjecture, or its various forms. In this paper, we classify deep holes completely for GRS codes RSp(D, k), where p is a prime, |D| > k ≥ (p - 1)/2. Our techniques are built on the idea of deep hole trees, and several results concerning the Erdös-Heilbronn conjecture.

Computing the minimum distance of a linear code is one of the fundamental problems in algorithmic coding theory. Vardy [1] showed that it is an NP-hard problem for general linear codes. In practice, one often uses codes with additional mathematical structure, such as cyclic codes and algebraic geometry (AG) codes, etc. In this paper, we study the minimum distance of a family of AG codes. For AG codes of genus 0 (generalized Reed-Solomon codes), the minimum distance has a simple explicit formula. An interesting result of Cheng [2] says that the minimum distance problem is already NP-hard (under RP-reduction) for general elliptic curve codes (ECAG codes, or AG codes of genus 1). In this paper, we show that the minimum distance of ECAG codes also has a simple explicit formula if the evaluation set is suitably large (at least 2=3 of the group order). Our method is purely combinatorial and based on a new sieving technique from Li-Wan [3].