We consider the aperiodic correlation properties of sequences derived from additive and multiplicative finite field characters. The additive characters produce the maximal linear recursive sequences (m-sequences), while the multiplicative characters produce the Legendre sequences and their relatives. For communications networks, one wants families of sequences where no sequence resembles any shifted version of itself (this is the problem of obtaining low autocorrelation), and no sequence resembles any shifted version of any other sequence (this is the problem of obtaining low crosscorrelation). Autocorrelation is the special case of crosscorrelation where the two sequences being compared are equal. Autocorrelation has been studied extensively in the merit factor problem, where one attempts to minimize the mean square autocorrelation. Crosscorrelation is significantly more challenging to study than autocorrelation. Thus considerably less is known about crosscorrelation, but some foundational results can be found in a 1984 paper of Sarwate, in which he shows that the typical crosscorrelation performance of a pair of binary m-sequences is on par with the average performance of a pair of randomly selected binary sequences.

We present the first proofs that there are infinite families of sequence pairs whose mean square crosscorrelation is significantly lower than that of random sequence pairs. For example, we can do significantly better than random sequence pairs by using pairs of m-sequences where one is obtained by reversing the other and shifting appropriately. We construct sequence pairs with even lower mean square crosscorrelation by taking a Legendre sequence, cyclically shifting it, and

then cutting it (approximately) in half and using the halves as the sequences of the pair. And we can further lower the mean square crosscorrelation by employing linear combinations of multiplicative characters and periodically extending (appending) the sequences. There is typically a tradeoff between autocorrelation and crosscorrelation performance, but our constructions give examples of infinite families of sequence pairs that significantly outperform randomly selected sequence pairs with respect to both autocorrelation and crosscorrelation simultaneously. We prove exact asymptotic formulae for the mean squared autocorrelation and crosscorrelation of our sequences, and data is presented that shows that sequences of modest length have performance that closely approximates the asymptotic formulae. (some of this is joint work with Tomas Boothby)