We determine conditions on q for the nonexistence of deep holes of the standard Reed-Solomon code of dimension k over F_q generated by polynomials of degree k+d. Our conditions rely on the existence of q-rational points with nonzero, pairwise-distinct coordinates of a certain family of hypersurfaces defined over F_q. We show that the hypersurfaces under consideration are invariant under the action of the symmetric group of permutations of the coordinates. This allows us to obtain critical information concerning the singular locus of these hypersurfaces, from which the existence of q-rational points is established.
For generalized Reed-Solomon codes, it has been proved [7] that the problem of determining if a received word is a deep hole is co-NP-complete. The reduction relies on the fact that the evaluation set of the code can be exponential in the length of the code - a property that practical codes do not usually possess. In this paper, we first present a much simpler proof of the same result. We then consider the problem for standard Reed-Solomon codes, i.e. the evaluation set consists of all the nonzero elements in the field. We reduce the problem of identifying deep holes to deciding whether an absolutely irreducible hypersurface over a finite field contains a rational point whose coordinates are pairwise distinct and nonzero. By applying Cafure-Matera estimation of rational points on algebraic varieties, we prove that the received vector (f(α))α∈Fpfor the Reed-Solomon [p - 1, k]p, k < p1 4-Ɛ, cannot be a deep hole, whenever f(x) is a polynomial of degree k + d for 1 ≤ d ≤ p3 13-Ɛ. We show explicit estimates on the number of q-ratinoal points of an F"q-definable affine absolutely irreducible variety of [email protected]?"q^n. Our estimates for a hypersurface significantly improve previous estimates of W. Schmidt and M.-D. Huang and Y.-C. Wong, while in the case of a variety our estimates improve those of S. Ghorpade and G. Lachaud in several important cases. Our proofs rely on elementary methods of effective elimination theory and suitable effective versions of the first Bertini theorem.