Golay–Rudin–Shapiro Polynomials and Phased Arrays

A single-frequency plane wave propagating at speed c in the direction of the unit vector \(\mathbf{N}\) is given by $$S(\mathbf{X},t) =\exp i\omega \left (t -\frac{\mathbf{N} \cdot \mathbf{X}} {c} \right ).$$ (1) Suppose \(\left \{{\mathbf{X}}_{1},\ldots,{\mathbf{X}}_{N}\right \} \subset {\mathbf{R}}^{n}\) is a fixed set of locations, called the array, and \({w}_{1},\ldots,{w}_{N} \subset \mathbf{C}\) is a set of weights. The linear combination $$\begin{array}{rcl} G(t)& =& {\sum \nolimits }_{k=1}^{N}{w}_{ k}S(\mathbf{X},t) ={ \sum \nolimits }_{k=1}^{N}{w}_{ k}\exp \left (i\omega t\right )\exp \left (\frac{i\omega } {c} \mathbf{N} \cdot {\mathbf{X}}_{k}\right ) \\ & =& \exp i\omega t{\sum \nolimits }_{k=1}^{N}{w}_{ k}\exp \left (-2\pi i\left (\frac{\mathbf{N} \cdot {\mathbf{X}}_{k}} {\lambda } \right )\right ) = (\exp i\omega t)H(\mathbf{N}) \end{array}$$ (2) is the output of the “phased array”. Given unit vector \({\mathbf{N}}_{0}\), if we let $${w}_{k} =\exp \left (2\pi i\left (\frac{{\mathbf{N}}_{0} \cdot {\mathbf{X}}_{k}} {\lambda } \right )\right )$$ (3) then \(H({\mathbf{N}}_{0}) = N\) and \(\vert H(\mathbf{N})\vert \leq N\) for all \(\mathbf{N}\). The “phased array problem” is to find \(\left \{{\mathbf{X}}_{1},\ldots,{\mathbf{X}}_{N}\right \}\) such that \(\vert H(\mathbf{N})\) looks as much like a delta function as possible. We study this problem in the simplified case where \(\left \{{\mathbf{X}}_{1},\ldots,{\mathbf{X}}_{N}\right \}\) lie on a line. In this case, through a mild change of variables, \(H(\mathbf{N})\) is replaced by the 1-periodic trigonometric polynomial $$A(x) ={ \sum \nolimits }_{k=1}^{N}{\mathrm{e}}^{2\pi i{n}_{k}x},$$ (4) where the integers n k specify the location of the \({\mathbf{X}}_{k}\) on the line. Then the problem is to chose the n k so that A(x) looks like a (periodic) delta function with mass at x =0. In order to achieve a sharp peak at x=0 the n k must be very spread out. When this is so, the array is referred to as a “thin phased array”. However if the n k are too uniformly spaced there will be large peaks at locations other than x=0. The graph of|A(x)|is fairly insensitive to the distribution of the n k in the region close to x=0, called the “main lobe region”. The complement of the main lobe region is called the “sidelobe region”. The problem is to minimize the maximum of|A(x)|in the sidelobe region. Energy considerations show that the maximum of|A(x)|in the sidelobe region cannot be less than \(O(\sqrt{N})\). Random choices of the n k cannot do better than \(O(\sqrt{N\log N})\) for sidelobe maxima. In this chapter we give a construction which achieves \(O(\sqrt{N})\) sidelobe maxima. Specifically we use the theory of generalized golay–rudin–shapiro polynomials to construct asymptotically optimal thin phased arrays. More precisely, given \(n \geq 2\) and prime \(p \geq 2\) we construct integer sets \(\{{n}_{1},\ldots,{n}_{N}\}\) contained in \(\{0,1,\ldots,{p}^{n+1}\}\) such that $$\left \vert {\sum \nolimits }_{k=1}^{N}{\mathrm{e}}^{2\pi i{n}_{k}x}\right \vert \leq \left \vert \frac{\sin \pi {p}^{n+1}x} {p\sin \pi x} \right \vert + O({p}^{n/2}),$$ where \(N = {p}^{n} + O({p}^{n/2})\).