Weil sums of binomials, three-level cross-correlation, and a conjecture of Helleseth

Let q be a power of a prime p, let ψq:Fq→C be the canonical additive character ψq(x)=exp(2πiTrFq/Fp(x)/p), let d be an integer with gcd(d,q−1)=1, and consider Weil sums of the form Wq,d(a)=∑x∈Fqψq(xd+ax). We are interested in how many different values Wq,d(a) attains as a runs through Fq⁎. We show that if |{Wq,d(a):a∈Fq⁎}|=3, then all the values in {Wq,d(a):a∈Fq⁎} are rational integers and one of these values is 0. This translates into a result on the cross-correlation of a pair of p-ary maximum length linear recursive sequences of period q−1, where one sequence is the decimation of the other by d: if the cross-correlation is three-valued, then all the values are in Z and one of them is −1. We then use this to prove the binary case of a conjecture of Helleseth, which states that if q is of the form 22n, then the cross-correlation cannot be three-valued.