The resolution of Niho's last conjecture concerning sequences, codes, and Boolean functions
This solves a specific theoretical problem in sequences and coding theory, but it is incremental as it addresses a known conjecture without broader application.
The paper resolves Niho's long-standing conjecture on the crosscorrelation spectrum of maximum length linear recursive sequences, showing there are at most five distinct values for even m and six for odd m, with implications for Walsh spectra and cyclic codes.
A new method is used to resolve a long-standing conjecture of Niho concerning the crosscorrelation spectrum of a pair of maximum length linear recursive sequences of length $2^{2 m}-1$ with relative decimation $d=2^{m+2}-3$, where $m$ is even. The result indicates that there are at most five distinct crosscorrelation values. Equivalently, the result indicates that there are at most five distinct values in the Walsh spectrum of the power permutation $f(x)=x^d$ over a finite field of order $2^{2 m}$ and at most five distinct nonzero weights in the cyclic code of length $2^{2 m}-1$ with two primitive nonzeros $α$ and $α^d$. The method used to obtain this result proves constraints on the number of roots that certain seventh degree polynomials can have on the unit circle of a finite field. The method also works when $m$ is odd, in which case the associated crosscorrelation and Walsh spectra have at most six distinct values.