A Character Formula for the Sidelnikov-Lempel-Cohn-Eastman Sequences

We obtain a formula expressing the character values of the almost difference sets associated with the Sidelnikov-Lempel-Cohn-Eastman (SLCE) sequences in terms of certain Jacobi sums. As a result, we are able to obtain new insight into the pseudo-randomness properties of the SLCE sequences.We consider the problem of determining maximal sets of shift-inequivalent decimations of SLCE sequences, or rather the equivalent problem of determining the multiplier groups of the SLCE almost difference sets. Using our character formula in conjunction with some tools from algebraic number theory (such as Stickelberger's Theorem) we obtain a numerical necessary condition for a residue to be a multiplier of an SLCE almost difference set. We use this necessary condition to prove that if p is a prime congruent to 3 modulo 4, the multiplier group of an SLCE almost difference set over the prime field of order p must be trivial. Consequently, we obtain families of shift-inequivalent decimations of SLCE sequences.We also consider the problem of determining the linear complexity of the SLCE sequences. Due to certain technical considerations, this problem is rather difficult and has resisted the efforts of a number of mathematicians over the past 15 years. Making use of our character formula together with explicit evaluations of Jacobi sums in the pure and small index cases, we obtain new upper bounds on the linear complexity of these sequences.