Binary sequences with good autocorrelation have applications in CDMA communication systems, cryptography and physics. A binary sequence of period N = 1 (mod 4) is said to have optimal autocorrelation if its out-of-phase autocorrelation values take on only -3 and 1.
In 1798, Adrien-Marie Legendre introduced the Legendre symbol and hence the Legendre sequence of period p, where p is a prime. If p = 1 (mod 4), the Legendre sequence has only out-of-phase autocorrelation values -3 and 1. The reference is: A. M. Legendre Essai sur la theorie des nombres Paris 1798, p 186.
In 1962 Whiteman discovered the so-called two-prime difference sets [Illinois J. Math. 6 (1962) 107-121] and thus the twin-prime sequences with optimal autocorrelation value -1. In 1991, the two-prime sequences, which are a generalization of the twin-prime sequences, were described in:
J.M. Jensen, H.E. Jensen, T. Hoholdt, The merit factor of binary sequences related to difference sets, IEEE Trans. IT 37(3) (1991) 617--626.
However, the autocorrelation values of the two-prime sequences were not known until 1998. In 1998, Ding determined the autocorrelation values under the condition that gcd(p-1, q-1) = 2 in:
C. Ding, Autocorrelation values of generalized cyclotomic sequences of order two, IEEE Trans. Information Theory 44 (1998) 1698--1702.
Independently in 1998, two physicists at Germany published the autocorrelation values of the two-prime sequences in:
S. Mertens and C. Bessenrodt, On the ground states of the Bernasconi model, J. Phys. A: Math. Gen. 31 (1998) 3731--3749.
So exactly 200 years after the Legendre sequences, it was discovered that the two-prime sequences have optimal autocorrelation values -3 and 1 when q - p = 4.
One year after the 200-year breakthrough, another construction of binary sequences of period N = 1 (mod 4) with optimal autocorrelation was discovered and published in:
C. Ding, T. Helleseth, K. Y. Lam, Several classes of sequences with three-level autocorrelation, IEEE Trans. Information Theory 45 (1999) 2606--2612.
By now these are the only three known constructions of binary sequences of period N = 1 (mod 4) with optimal autocorrelation. Details about these constructions and open problems can be found in the following slides:
Lecture slides on binary sequences with optimal autocorrelation
The reader is invited to attack the open problems presented in the slides.