No label defined (Q4510797)

Let \(S(n,k)\) denote the set of polynomials \(X(z)\) of degree \(n-1\) with all coefficients in the set \(\{-1,1\}\) and that have at least a \(k\)th order zero at \(z = 1\). It is easy to see that \(S(n,k)\) is empty unless \(2^m\) divides \(n\), where \(m = \lfloor \log_2 k \rfloor + 1\). The authors show that if this condition holds then as \(n \to \infty\), \[ \log_2 |S(n,k)|= n - (k^2/2) \log_2 n + c_k + o(1), \] where \(c_k\) is an explicit constant. This answers a question of \textit{R. M. Roth, P. H. Siegel} and \textit{A. Vardy} [IEEE Trans. Inf. Theory 40, 1826-1840 (1994; Zbl 0826.94030)], concerning ``spectral null codes'', which are the coefficient vectors of elements of \(S(n,k)\). The proof makes an ingenious use of the Hardy-Littlewood circle method [see \textit{R. C. Vaughan}, Cambridge Tracts in Mathematics. 125. Cambridge: Cambridge University Press (1997; Zbl 0868.11046)]. The asymptotic result would seem to suggest that \(S(n,k)\) is non-empty if \(n > (1 + \epsilon)k^2/2\), but this is surprisingly far from the truth since the reviewer has shown that \(S(n,k)\) is empty unless \(n \geq \exp(\sqrt k (1 + o(1)))\) as \(k \to \infty\) [Math. Comput. 66, 1697-1703 (1997; Zbl 0893.12004)]. The explanation of this apparent discrepancy is simply that the error term \(o(1)\) in the authors' result depends on \(k\). A paper by the authors containing the same results appeared in [IEEE Trans. Inf. Theory 45, 1798-1807 (1999; Zbl 0958.94041)]. For the entire collection see [Zbl 0943.00048].