Bounds on the growth rate of the peak sidelobe level of binary sequences
Denis Dmitriev, Jonathan Jedwab · Advances in Mathematics of Communications · 2007
The peak sidelobe level (PSL) of a binary sequence is the largest absolute value of all its nontrivial aperiodic autocorrelations. A classical problem of digital sequence design is to determine how slowly the PSL of a length $n$ binary sequence can grow, as $n$ becomes large. Moon and Moser showed in 1968 that the growth rate of the PSL of almost all length $n$ binary sequences lies between order $\sqrt{n\log n}$ and $\sqrt{n}$, but since then no theoretical improvement to these bounds has been found. We present the first numerical evidence on the tightness of these bounds, showing that the PSL of almost all binary sequences of length $n$ appears to grow exactly like order $\sqrt{n\log n}$, and that the PSL of almost all $m$-sequences of length $n$ appears to grow exactly like order $\sqrt{n}$. In the case of $m$-sequences, a key algorithmic insight reveals behaviour that was previously well beyond the range of computation.