A proof of the Welch and Niho conjectures on cross-correlations of binary \(m\)-sequences (Q5941619)

The authors study the number of values attained by the cross-correlation of a binary \(m\)-sequence and its decimation by a factor of \(t\). This number equals the number of nonzero weights in the dual of \(C_{1,t}\), the binary cyclic code of length \(2^m-1\) with defining zeros \(\alpha\) and \(\alpha^t\), where \(\alpha\) is primitive in \(\mathrm{GF}(2^m)\). A unified method is presented for proving that \(C^\perp_{1,t}\) has three weight for the following pairs \((m,t)\): (a) \(t= 2^r+1\) if \((r,m)= 1\) (proved by Gold in 1968), (b) \(t= 2^{2r}- 2^r+ 1\) if \((r,m)= 1\) (proved by Welch (1969) and Kasami (1971)), (c) \(m= 2r+ 1\), \(t= 2^r+ 3\) (conjectured by Welch in 1972), (d) \(m\) is odd, \(4r\equiv-1\pmod m\), \(t= 2^{2r}+ 2^r- 1\) (conjectured by Niho, 1972). The method uses the Pless power moment identities, a deep theorem of McEliece on the divisibility of nonzero weights in cyclic codes by powers of two, and an ingenious counting method. In the application of the Pless power moment identities, Dobbertin's breakthrough result [\textit{H. Dobbertin}, IEEE Trans. Inf. Theory 45, 1271--1275 (1999; Zbl 0957.94021); Inf. Comput. 151, 57--72 (1999; Zbl 1072.94513)] is used, which states that in cases (c) and (d), \(C_{1,t}\) has minimum distance 5.