Deep holes in Reed–Solomon codes based on Dickson polynomials

For an [n,k][n,k] Reed–Solomon code CC, it can be shown that any received word r   lies a distance at most n−kn−k from CC, denoted d(r,C)≤n−kd(r,C)≤n−k. Any word r   meeting the equality is called a deep hole. Guruswami and Vardy (2005) showed that for a specific class of codes, determining whether or not a word is a deep hole is NP-hard. They suggested passingly that it may be easier when the evaluation set of CC is large or structured. Following this idea, we study the case where the evaluation set is the image of a Dickson polynomial, whose values appear with a special uniformity. To find families of received words that are not deep holes, we reduce to a subset sum problem (or equivalently, a Dickson polynomial-variation of Waring's problem) and find solution conditions by applying an argument using estimates on character sums indexed over the evaluation set.