Sparse binary cyclotomic polynomials (Q661965)

Let \(\Phi_n(x)\) denote the \(n\)-th cyclotomic polynomial. Let \(2<p<q\) be two primes. Then \(\Phi_{pq}(x)\) is said to be binary. Its coefficients are in \(\{-1,0,1\}\). Let \(\theta_n\) be the number of nonzero terms of \(\Phi_n\). \textit{L. Carlitz} [Am. Math. Mon. 73, 979--981 (1966; Zbl 0146.26704)] proved that for \(n=pq\) we have \(\theta_n=2p'q'-1\), where \(q'\) denotes the inverse of \(q\) modulo \(p\) and similarly \(p'\) is the inverse of \(p\) modulo \(q\). It can be easily proved that \(\sqrt{n}<\theta_n<n/2\). \textit{H. W. Lenstra} jun. [Proc. bicenten. Congr. Wiskd. Genoot., Part II, Amsterdam 1978, Math. Cent. Tracts 101, 249--268 (1979; Zbl 0411.12003)] proved that for every \(\varepsilon>0\) there exist infinitely many binary numbers \(n\) such that \(\theta_n<n^{8/13+\varepsilon}\). Let \(B_{\varepsilon}(N)\) denote the number of binary \(n\leq N\) for which \(\theta_n<n^{1/2+\varepsilon}\). The author shows, by a method different from that used by Lenstra, that \[ N^{1/2+\varepsilon'}\ll B_{\varepsilon}(N)\ll N^{1/2+\varepsilon}, \] where \(0<\varepsilon'<\varepsilon<1/2\) are fixed and the implied constants may depend on \(\varepsilon'\), respectively \(\varepsilon\). By a well-known result of Landau the total number of binary \(n\leq N\) is asymptotically equal to \(N(\log N)^{-1}\log\log N\) and thus, for fixed \(0<\varepsilon<1/2\), the set of binary \(n\) with \(\theta_n<n^{1/2+\varepsilon}\) has relative density 0 in the set of binary \(n\).