# Long cycles in linear thresholding systems

Anna Laddach  Francis Crick Institute, London  and  Michael Shapiro  Francis
Crick Institute, London

(Date: 22 November 2023)

## Introduction

Linear thresholding systems have been studied as models of neural activation
[1] and more recently as models of cell-intrinsic gene regulation [2]. More
generally, they represent dynamics on a set of $N$ objects which can be either
on or off. That is, they are maps

$\displaystyle
f=f_{(J,\theta)}:\mathcal{P}_{N}=\\{0,1\\}^{N}\subset\mathbb{R}^{N}\to\\{0,1\\}^{N}$
$\displaystyle f(x)=\theta(Jx)$

where $J$ is a linear map and $\theta$ is a thresholding function

$\displaystyle\theta(x_{1},\dots,x_{N})=(y_{1},\dots,y_{N})$ $\displaystyle
y_{i}=\begin{cases}0&\text{if }x_{i}\leq\theta_{i}\\\ 1&\text{if
}x_{i}>\theta_{i}\\\ \end{cases}$

We will restrict to the case in which each $\theta_{i}$ is positive. Since
there are $2^{N}$ elements of $\mathcal{P}_{N}$, this provides an upper bound
on the length of any cycle for a linear thresholding system in dimension $N$.
Under the assumption that the $\theta_{i}$ are positive, 0 is a fixed point
and this reduces this bound to $2^{N}-1$. Here we exhibit systems of
arbitrarily large $N$ with cycles of length greater than $e^{\sqrt{N}}$. Along
the way, we introduce a direct product on linear thresholding systems.

## Background and definitions

We record here some basic definitions and results.

######  Definition 1.

  * •

We say two linear thresholding systems $(J,\theta)$ and
$(J^{\prime},\theta^{\prime})$ are equivalent and write
$(J,\theta)\sim(J^{\prime},\theta^{\prime})$ if
$f_{(J,\theta)}=f_{(J^{\prime},\theta^{\prime})}$.

  * •

We say that $(J,\theta)$ is generic if for each $x\in\mathcal{P}$, and each
cooridinate $i$, $(Jx)_{i}\neq\theta_{i}$.

  * •

We will say that $(J,\theta)$ is robust if there is an open set $U_{J}$ around
$J$ and an open set $U_{\theta}$ around $\theta$ such that for each
$(J^{\prime},\theta^{\prime})\in U_{J}\times U_{\theta}$,
$(J,\theta)\sim(J^{\prime},\theta^{\prime})$

The following are not hard to see:

######  Proposition 1.

  * •

$(J,\theta)$ is robust if and only if it is generic.

  * •

Every linear thresholding system is equivalent to a generic system.

  * •

Every linear thresholding system is equivalent under a linear change of
coordinates to a system in which the $\theta_{i}$ are independent of $i$.
Further, their value can be taken to be any positive number.

We will take our thresholding value to be $\theta=\frac{1}{2}$. We will be
interested in cases where $J$ permutes $\mathcal{P}$, and here thresholding
acts as the identity.

The dynamics of a function $f$ on a finite set $X$ can be seen as a directed
graph $\Gamma(X,E)$ where the edges $E$ are the pairs $\\{(x,f(x))\mid x\in
X\\}$. Each connected component of $\Gamma$ consists of a recurrent cycle $C$
(possibly of length 1) possibly decorated with directed trees $T_{i}$. Each
$T_{i}$ is directed towards its root, which is a vertex of $C$. The vertices
on the cycles are recurrent, the others are transient.

## Long cycles

We start by defining a direct product on linear thresholding systems.

######  Definition 2.

Given two systems, $(J,\theta)$ and $(J^{\prime},\theta)$ where the first has
$N$ genes and the second has $N^{\prime}$ genes, the product system,
$(J,\theta)\oplus(J^{\prime},\theta)$ is the system $(\bar{J},\theta)$ on
$N+N^{\prime}$ genes where

$\bar{J}=\left[\begin{matrix}J&0\\\ 0&J^{\prime}\end{matrix}\right].$

######  Proposition 2.

The dynamics of the product system are the product of the dynamics of the two
systems. That is, let $f$ and $f^{\prime}$ be the functions of the two systems
and $\bar{f}$ be the function of the product system. Let $x$ and $x^{\prime}$
be elements of $\mathcal{P}(1,\dots,N)$ and $\mathcal{P}(1,\dots,N^{\prime})$.
Then

$\bar{f}\left(\left[\begin{matrix}x\\\
x^{\prime}\end{matrix}\right]\right)=\left[\begin{matrix}f(x)\\\
f^{\prime}(x^{\prime})\end{matrix}\right]$

∎

######  Corollary 1.

Suppose $x_{1},\dots,x_{r}$ is a cycle of $(J,\theta)$ of length $r$ and
$x^{\prime}_{1},\dots,x^{\prime}_{s}$ is a cycle of $(J^{\prime},\theta)$ of
length $s$. Then together, they form a cycle of length
$\mathop{\mathrm{lcm}}(r,s)$ in the product system. ∎

We now take a moment to consider the orbits of $(J_{p},\theta)$ where
$J=J_{p}$ is the matrix that cyclically permutes the bases of
$\mathbb{R}^{p}$, $p$ is prime and $\theta=\frac{1}{2}$. Observe that in this
case the thresholding operation is superfluous since it acts as the identity
on $J\mathcal{P}$. Note that $J$ generates the cyclic group $\mathbb{Z}_{p}$
and thereby induces an action of $\mathbb{Z}_{p}$ on $\mathcal{P}$.

######  Lemma 1.

  * •

$(J,\theta)$ has no transient states.

  * •

The number of coordinates which are one is constant on each orbit.

  * •

Each cycle of $(J,\theta)$ has length 1 or $p$.

  * •

There are two cycles of length 1.

  * •

There are $(2^{p}-2)/p$ cycles of length $p$.

###### Proof.

  * •

Since $J^{p}=I$, $J^{p}x=x$ for each $x\in\mathcal{P}$.

  * •

Each $x\in\mathcal{P}$ is a set coordinates which are one. $J$ acts to
cyclically permute this set. It follows that the number of coordinates which
are one is constant along the orbit.

  * •

The length of each orbit divides $p$. Since $p$ is prime, it follows that this
is necessarily 1 or $p$.

  * •

The points $(0,\dots,0)$ and $(1,\dots,1)$ are fixed by $J$. On the other
hand, if $x$ is neither of these, $x$ has two (cyclically) adjacent
coordinates which are not equal. Hence $Jx\neq x$, so the orbit of $x$ has
length $p$.

  * •

This follows directly from the previous statement.

∎

######  Corollary 2.

Let $p_{1},\dots,p_{k}$ be a sequence of distinct primes, $N=\sum p_{i}$,
$P=\prod p_{i}$. Then there is a system $(J,\theta)$ on $N$ genes with a cycle
of length $P$. ∎

Note that the sum of the first $n$ primes grows as $\frac{1}{2}n^{2}\log(n)$
[3] while the product of the first $n$ primes grows as $e^{(1+o(1))n\log(n)}$
[4]. Thus, for arbitrarily large values $N$ there are systems on $N$ genes
with cycles of length greater than $e^{\sqrt{N}}$.

In fact, $(J,\theta)$ is rich in long cycles. If $S\subset\\{1,\dots,k\\}$,
then there are

$\prod_{i\in S}(2^{p_{i}}-2)/p_{i}$

orbits of length $\prod_{i\in S}p_{i}$.

Our definition is restricted to the case where the two systems have the same
thresholding function $\theta$. However up to equivalence, they can be given
the same $\theta$ and the equivalence class of the product system depends only
on the equivalence class of the factors. Thus, up to equivalence, the product
is defined on arbitrary pairs of systems.

## References

  * [1] A C C Coolen, P Sollich, and R Kuehn.  Theory of neural information processing systems.  Oxford University Press, 2005.
  * [2] Ryan Hannam, Alessia Annibale, and Reimer Kühn.  Cell reprogramming modelled as transitions in a hierarchy of cell cycles.  Journal of Physics A Mathematical General, 50(42):425601, October 2017.
  * [3] E. Landau.  Handbuch der Lehre von der Verteilung der Primzahlen, volume 1.  Teubner, Leipzig und Berlin, 1909.
  * [4] Sebastian Martin Ruiz.  A result on prime numbers.  Math. Gaz., July 1997.


concern. With our virtual correlation technique, we can maintain a good
overlap value within the active space while producing accurate energies
overall. Given this, we are optimistic about routes to achieve quantum
advantage in fermionic ground state simulation through the QC-AFQMC algorithm.
The aforementioned complex quantum states such as hardware efficient ansatze,
UCC and 2D-MERA can be good candidates for trial wavefunctions although the
relevance of 2D-MERA for chemistry simulations is yet to be seen. An important
consideration here is how one actually obtains wavefunction parameters of
those complex quantum states. One may optimize them using the variational
quantum algorithm or one may take states that can be efficiently optimized
classically. For the latter case, it seems likely that approximating the
overlap between these states and an arbitrary Slater determinant up to
additive error is difficult despite the fact that some of them can be
optimized efficiently using classical algorithms.

We hope to observe quantum advantage either in the overlap estimation or in
the ground state energy computation using QC-AFQMC and believe that continued
advancement along this direction will lead us to one of the first realizations
of practical quantum advantage in NISQ fermionic simulations.


# On the zeros of reciprocal Littlewood polynomials

Benjamin Bedert
Mathematical Institute, University of Oxford

###### Abstract.

Let $P(z)=\sum_{n=0}^{N}a_{n}z^{n}$ be a Littlewood polynomial of degree $N$,
meaning that $a_{n}\in\\{\pm 1\\}$. We say that $P$ is reciprocal if
$P(z)=z^{N}P(1/z)$. Borwein, Erdélyi and Littmann posed the question of
determining the minimum number $Z_{\mathcal{L}}(N)$ of zeros of modulus 1 of a
reciprocal Littlewood polynomial $P$ of degree $N$. Several finite lower
bounds on $Z_{\mathcal{L}}(N)$ have been obtained in the literature, and it
has been conjectured by various authors that $Z_{\mathcal{L}}(N)$ must in fact
grow to infinity with $N$. Starting from ideas in recent breakthrough papers
of Erdélyi and Sahasrabudhe, we are able to confirm this.

<EMAIL_ADDRESS>
The author gratefully acknowledges financial support from the EPSRC

###### Contents

  1. 1 Introduction
  2. 2 Notation and prerequisites
  3. 3 Set up and outline of the proof
  4. 4 A structural result
  5. 5 Proof for even degrees
  6. 6 Proof for odd degrees

##  1\. Introduction

Littlewood in his 1968 monograph “Some Problems in Real and Complex Analysis”
[12, Problem 22] posed the following problem:

######  Problem 1.

If the $n_{j}$ are distinct integers, what is the lower bound on the number of
real zeros of $\sum^{N}_{j=1}\cos n_{j}\theta$ in a period $[0,2\pi]$?
Possibly $N-1$, or not much less.

No progress was made on this problem until the breakthrough of Borwein,
Erdélyi, Ferguson and Lockhart [2] who demonstrated the existence of cosine
polynomials $\sum^{N}_{j=1}\cos n_{j}\theta$ with $O(N^{5/6}\log N)$ roots in
a period, thus giving a counterexample to Littlewood’s proposed lower bound.
Their construction was later used independently by Konyagin [11] and
Juškevičius and Sahasrabudhe [10] to obtain the improved upper bound $O((N\log
N)^{2/3})$. Obtaining lower bounds for the number of zeros of

cosine polynomials of the form

$f(\theta)=\sum_{j=1}^{N}\cos n_{j}\theta$ (1)

with the $n_{j}$ being distinct non-negative integers seems to be a hard
problem; in fact it was only recently proved that the number of such zeros
grows to infinity as $N\to\infty$. This was proved independently by Erdélyi
[7], and by Sahasrabudhe [16] who further obtained the explicit lower bound
$(\log\log\log N)^{1/2-o(1)}$ for the number of zeros of (1). Erdélyi [8]
combined the arguments of [7] and [16] to obtain the slightly better exponent
$1-o(1)$ replacing $1/2-o(1)$ in Sahasrabudhe’s bound. Let us write $Z(f)$ for
the number of zeros of the cosine polynomial $f$ in $[0,2\pi]$. Then the
current best bounds for Problem 1 are

$(\log\log\log N)^{1-o(1)}\leqslant\min_{f}Z(f)\leqslant(N\log N)^{2/3},$ (2)

where the minimum is taken over all cosine polynomials of the form (1) with
$N$ terms, and it is an interesting open problem problem to determine the true
order of magnitude. The methods of [7, 8, 16] further prove lower bounds on
the number of zeros of a more general class of cosine polynomials. Let $R$ be
a finite set, let

$f(\theta)=\sum_{n=0}^{N}A_{n}\cos n\theta$ (3)

with coefficients $A_{n}\in R$ and let $Z_{R}(N)=\min_{f}Z(f)$ where the
minimum is taken over all cosine polynomials $f$ of degree $N$ with
coefficients in $R$, as in (3). The following lower bound is established in
[8] (following similar theorems in [7, 16]).

######  Theorem 1 ([8], Theorem 2.1).

Let $R\subset\mathbf{Z}$ be finite and $M(R)=\max_{r\in R}|r|$. Let $f$ be a
cosine polynomial as in (3) with coefficients $A_{n}\in R$. Then the number of
roots of $f$ satisfies

$Z(f)\geqslant\left(\frac{c}{1+\log
M(R)}\right)\frac{\log\log\log|f(0)|}{\log\log\log\log|f(0)|}-1,$

where $c>0$ is an absolute constant.

Applying this theorem with $R=\\{0,1\\}$ clearly yields the lower bound in
(2). One should note that for general sets of coefficients $R$, a lower bound
as in Theorem 1 has to depend on a slightly more subtle parameter like
$|f(0)|$ rather than simply the degree $N$ of (3). This is pointed out in [7]
using the explicit functions

$g_{N}(\theta)=\cos\theta+\sum_{j=0}^{N}(-1)^{j}\cos((2j+1)\theta)$ (4)

which have no more than 2 roots in $[0,2\pi]$ for all $N$.111This is
compatible with Theorem 1 as the sequence $|g_{N}(0)|$ is bounded Similarly,
if the set of coefficients $R$ has both positive and negative numbers, then
Theorem 1 does not show that the number of zeros of (3) tends to infinity with
the degree $N$ and hence it gives no lower bound on $Z_{R}(N)$. For a general
finite set $R$, Borwein and Erdélyi [1] proved that if $(a_{n})\in
R^{\mathbf{N}}$ is a fixed sequence with finitely many zero terms, then
$\lim_{n\to\infty}Z(f_{n})=\infty$ where
$f_{n}(\theta)=\sum_{j=0}^{n}a_{j}\cos j\theta$ are truncations of a fixed
series. Note however that this result also does not show that
$Z_{R}(N)\to\infty$ as $N\to\infty$. In fact, such a result is not true for
general $R$ as can been seen by taking $R=\\{0,\pm 1,2\\}$ corresponding to
(4).

In this paper we consider the class of cosine polynomials with coefficients in
$R=\\{\pm 1\\}$ which is of special interest in the literature, and our goal
will be to prove the conjecture that $Z_{\\{\pm 1\\}}(N)\to\infty$ as
$N\to\infty$. In this context, problems are usually formulated equivalently
using reciprocal Littlewood polynomials. Following the notation in [8], we
denote the class of Littlewood polynomials of degree $N$ by

$\mathcal{L}_{N}=\left\\{P:P(z)=\sum_{n=0}^{N}\varepsilon_{n}z^{n},\varepsilon_{n}\in\\{\pm
1\\}\right\\}$

and we say that a polynomial $P(z)=\sum_{n=0}^{N}a_{n}z^{n}$ is reciprocal if
$P(z)=z^{N}P(1/z)$, or equivalently $a_{j}=a_{N-j}$ for all $j$. Let us write
$Z(P)=\left|\\{\rho\in\mathbf{C}:|\rho|=1,P(\rho)=0\\}\right|$ for the number
of unimodular roots of $P$, and let

$Z_{\mathcal{L}}(N)=\min_{P\in\mathcal{L}_{N}\text{ reciprocal}}Z(P)$ (5)

be the minimum number of unimodular roots of a reciprocal Littlewood
polynomial of degree $N$. Borwein, Erdélyi and Littmann [3, Problem 1] asked
to determine $Z_{\mathcal{L}}(N)$. It was shown independently by Erdélyi [5]
and Mercer [13] that $Z_{\mathcal{L}}(N)\geqslant 1$ for $N\geqslant
1$.222Mercer also showed that ‘skew-reciprocal’ Littlewood polynomials do not
have any unimodular roots, justifying that the minimum in (5) is taken over
reciprocal polynomials only. Mukunda [14] improved this result by proving that
$Z_{\mathcal{L}}(N)\geqslant 3$ for odd degrees $N\geqslant 3$. The current
best bounds are due to Drungilas [4] who proved that
$Z_{\mathcal{L}}(N)\geqslant 5$ for odd $N\geqslant 7$ and
$Z_{\mathcal{L}}(N)\geqslant 4$ for even $N\geqslant 14$. It was also shown in
[2] that reciprocal polynomials in $\mathcal{L}_{N}$ have at least $n/4$ roots
on average. Erdélyi [6, 7, 8], Mukunda [14] and Drungilas [4] state the
conjecture that

$\lim_{N\to\infty}Z_{\mathcal{L}}(N)=\infty.$ (6)

Our main result confirms this conjecture.

######  Theorem 2.

We have that $Z_{\mathcal{L}}(N)\to\infty$ as $N\to\infty$.

The analogous question in the setting of cosine polynomials appeared recently
in Sahasrabudhe’s paper [16]. We also answer this, showing that the number of
zeros in $[0,2\pi]$ of a cosine polynomial
$f(\theta)=\sum_{n=0}^{N}\varepsilon_{n}\cos n\theta$ with
$\varepsilon_{n}\in\\{-1,1\\}$ tends to infinity with the degree $N$. Note
again that Theorem 1 does not apply in this setting since $|f(0)|$ can remain
bounded. Rewriting such $f$ as a reciprocal polynomial in $z=e^{i\theta}$
shows that Theorem 3 is essentially equivalent to the claim that
$Z_{\mathcal{L}}(2N)\to\infty$ as $N\to\infty$.

######  Theorem 3.

We have that $Z_{\\{\pm 1\\}}(N)\to\infty$ as $N\to\infty$.

Acknowledgements The author would like to thank Tamás Erdélyi and his
supervisor Ben Green for their useful comments on earlier versions of the
paper and for sharing helpful references. The author also gratefully
acknowledges financial support from the EPSRC.

##  2\. Notation and prerequisites

We will use the asymptotic notation $f=O(g)$ or $f\ll g$ if there is a
constant $C$ such that $|f(n)|\leqslant Cg(n)$ for all $n$, $f=\Theta(g)$ if
there exist constants $C,C^{\prime}$ such that $C^{\prime}g(n)\leqslant
f(n)\leqslant Cg(n)$ for all $n$, and we write $f=o(g)$ if
$\frac{f(n)}{g(n)}\to 0$ as $n\to\infty$. Sometimes we emphasise the limit by
writing $f=O_{n\to\infty}(g)$ or $f=o_{n\to\infty}(g)$. We also write
$f=O_{c}(g)$ if the constant $C$ above is allowed to depend on $c$, and
$f=o_{c}(g)$ if $\frac{f(n)}{g(n)}$ tends to $0$ as $n\to\infty$ for each
fixed $c$ but at a rate that may depend on $c$. We say that $z\in\mathbf{C}$
is unimodular if $|z|=1$, and we write $\Re(z),\Im(z)$ for its real and
imaginary parts. For a real number $t$, we use the notation $e(t)=e^{2\pi
it}$. We will make use of Parseval’s theorem, which for the group
$G=\mathbf{Z}/D\mathbf{Z}$ and functions $f,g:G\to\mathbf{C}$ states that

$\sum_{m=0}^{D-1}\hat{f}(m)\overline{\hat{g}(m)}=D^{-1}\sum_{m=0}^{D-1}f(m)\overline{g(m)},$

where $\hat{f}(m)=D^{-1}\sum_{j=0}^{D-1}f(j)e(-mj/D)$ denotes the Fourier
transform of $f$. For the group $G=\mathbb{T}$ and a trigonometric polynomial
$f(t)=\sum_{-N}^{N}c_{n}e(nt)$, Parseval’s theorem states that
$\int_{0}^{1}|f(t)|^{2}\;dt=\sum_{n}|c_{n}|^{2}$.

##  3\. Set up and outline of the proof

We prove Theorem 2 by contradiction, assuming that there is a fixed integer
$d$ and an infinite set $\mathcal{N}\subset\mathbf{N}$ such that for each
$N\in\mathcal{N}$ we can find a reciprocal Littlewood polynomial
$P_{N}(z)\in\mathcal{L}_{N}$ of degree $N$ that has at most $d$ unimodular
zeros. Our starting point is a structural result on trigonometric polynomials
with a bounded number of roots, appearing in the papers of Sahasrabudhe [16]
and Erdélyi [8].

######  Theorem 4.

[16, Theorem 4]. Let $R\subset\mathbf{Z}$ be finite and $d\in\mathbf{N}$. Then
there is a constant $D$ depending only on $R,d$ such that the following holds.
Let

$f(\theta)=\sum_{n=0}^{N}A_{n}\cos n\theta+\sum_{n=1}^{N}B_{n}\sin n\theta$

be a trigonometric polynomial with coefficients $A_{n},B_{n}\in R$ having at
most $d$ roots in $[0,2\pi]$. Then there exists $L<D$ and disjoint intervals
$I_{j}$ with $\cup_{j=1}^{L}I_{j}=[N]$ so that for each $j$, the sequences
$(A_{n})_{n\in I_{j}},(B_{n})_{n\in I_{j}}$ are periodic with period $D$.

The unimodular roots of a reciprocal polynomial
$P(z)=\sum_{n=0}^{N}a_{n}z^{n}$ with real coefficients correspond to the roots
of a cosine polynomial via the relations

$\displaystyle P(e^{i\theta})e^{-i\theta N/2}$
$\displaystyle=a_{N/2}+2\sum_{n=1}^{N/2}a_{N/2+n}\cos n\theta\;$ for $N$ even,
(7) $\displaystyle P(e^{2i\theta})e^{-iN\theta}$
$\displaystyle=2\sum_{n=1}^{(N+1)/2}a_{(N-1)/2+n}\cos((2n-1)\theta)$
$\displaystyle\text{for $N$ odd}.$

The polynomials $P_{N}$ with $N\in\mathcal{N}$ are reciprocal Littlewood
polynomials by assumption so we can write

$P_{N}(z)=\sum_{n=0}^{N}a^{(N)}_{n}z^{n}$ (8)

with coefficients $a^{(N)}_{n}\in\\{\pm 1\\}$ that satisfy
$a^{(N)}_{n}=a^{(N)}_{N-n}$. Let us define for each $N\in\mathcal{N}$ a
corresponding polynomial $Q_{M}$ of degree $M$ by

$\displaystyle Q_{N/2}(z)$
$\displaystyle\vcentcolon=\sum_{n=0}^{N/2}a^{(N)}_{N/2+n}z^{n}\;$ if $N$ is
even, (9) $\displaystyle Q_{N}(z)$
$\displaystyle\vcentcolon=\sum_{n=1}^{(N+1)/2}a^{(N)}_{(N-1)/2+n}z^{2n-1}$ if
$N$ is odd. (10)

Note that $Q_{N/2}$ is itself a Littlewood polynomial when $N$ is even. In
this case, we will show that there exist large $N\in\mathcal{N}$ for which the
function $\Re\left(Q_{N/2}(e^{i\theta})\right)$ oscillates sufficiently many
times between $-cN$ and $cN$ on $[0,2\pi]$ for some constant $c>0$. This is
enough to establish the conclusion of Theorem 2 for even degrees $N$ as from
(7) we obtain the following relation between $P_{N}$ and $Q_{N/2}$ for even
$N$:

$\displaystyle P_{N}(e^{i\theta})$ $\displaystyle=e^{i\theta
N/2}\Re\left(2Q_{N/2}(e^{i\theta})-a_{N/2}\right).$ (11)

The situation for odd $N$ is more delicate; in this case

$\displaystyle P_{N}(e^{2i\theta})$ $\displaystyle=2e^{i\theta
N}\Re\left(Q_{N}(e^{i\theta})\right)$ (12)

but we cannot show that a function $\Re\left(Q_{N}(e^{i\theta})\right)$ of the
form (10) has many roots by proving that it has large oscillations. The
functions
$h_{m}(\theta)=\Re\left(\sum_{n=0}^{2m}(-1)^{n}e^{i(2n+1)\theta}\right)$ which
are similar to (4) are an example of this and they even have a bounded number
of sign changes on $[0,2\pi]$ for all $m$. We will show that for odd $N$,
either $\Re\left(Q_{N}(e^{i\theta})\right)$ has large oscillations so that we
may conclude as before, or else we deduce a stronger periodicity condition for
its coefficients than one gets from Theorem 4. This additional structure will
allow us to conclude by a different argument.

##  4\. A structural result

As a first step, we prove the following lemma which shows that a sequence of
polynomials with a bounded number of roots contains a subsequence of
polynomials that all have the same structure.

######  Lemma 1.

Let $d\in\mathbf{N}$ and let $R\subset\mathbf{Z}$ be finite. Then there exists
a constant $D$ depending only on $R,d$ such that the following holds. Let
$\mathcal{N}\subset\mathbf{N}$ be an infinite set. Suppose that
$\\{Q_{N}(z):N\in\mathcal{N}\\}$ is a collection of polynomials with
coefficients in $R$, with $\deg Q_{N}=N$ and such that
$\Re\left(Q_{N}(e^{i\theta})\right)$ has at most $d$ roots in $[0,2\pi]$ for
each $N\in\mathcal{N}$. Then there exist an infinite subset
$\mathcal{N}^{\prime}\subset\mathcal{N}$, constants $l\leqslant D$ and
$0=\rho_{0}<\rho_{1}<\dots<\rho_{l}=1$, and a sequence
$(\varepsilon^{(j)}_{m})_{m=1}^{D}\in R^{D}$ for each $j\in[l]$ so that for
$N\in\mathcal{N}^{\prime}$:

$Q_{N}(z)=\sum_{j=1}^{l}\left(\sum_{n\in\big{(}\rho_{j-1}N,\rho_{j}N\big{)}}\varepsilon^{(j)}_{n\,(\\!\\!\\!\\!\\!\\!\mod
D)}z^{n}\right)+E_{N}(z),$ (13)

where the $E_{N}(z)$ are polynomials with $o(N)$ terms and whose coefficients
have size at most $2\max_{r\in R}|r|$.

######  Remark.

We remind the reader that here, $o(N)$ denotes a function $f$ defined on
$\mathcal{N}^{\prime}$ such that $f(N)/N\to 0$ as
$N\to\infty,N\in\mathcal{N}^{\prime}$.

###### Proof.

Let us write $Q_{N}(z)=\sum_{n=0}^{N}q^{(N)}_{n}z^{n}$ for each
$N\in\mathcal{N}$ so that $q^{(N)}_{n}\in R$ and $\deg Q_{N}=N$. Our aim is to
prove (13) for all $N$ in some infinite subset of $\mathcal{N}$, so we may
assume throughout this proof that $N$ is sufficiently large. As we are
assuming that the cosine polynomial $\Re(Q_{N})$ has at most $d$ roots, an
application of Theorem 4 shows that for each $N\in\mathcal{N}$ the sequence of
coefficients $(q^{(N)}_{n})_{0\leqslant n\leqslant N}$ consists of a bounded
number $L_{N}<D=O_{R,d}(1)$ of periodic sequences, each periodic with period
$D$. Let us write $I^{(N)}_{j}$ for the intervals partitioning $[N]$ such that
$(q^{(N)}_{n})_{n\in I^{(N)}_{j}}$ is $D-$periodic for each $1\leqslant
j\leqslant L_{N}$. By adding at most $D$ intervals, we may assume that the
startpoints of the $I^{(N)}_{j}$ are multiples of $D$ and hence, so are their
lengths. Since there are only finitely many values of $L_{N}$, we may restrict
to an infinite subset $\mathcal{N}_{1}\subset\mathcal{N}$ so that $L_{N}=L$ is
constant for each $N\in\mathcal{N}_{1}$. Note further that there are only
finitely many ways to choose $L$ sequences in $R^{D}$. Hence, after further
restricting to an appropriate subset $\mathcal{N}_{2}\subset\mathcal{N}_{1}$,
we may also assume that the $D-$periodic pattern of the sequences
$(q^{(N)}_{n})_{n\in I^{(N)}_{j}}$ depends only on $j\in[L]$ but not on $N$
when $N\in\mathcal{N}_{2}$. Formally, this means precisely that we can find
fixed sequences $(\epsilon^{(j)}_{m})_{m=1}^{D}$ in $R^{D}$, one for each
$j\in[L]$, so that for all $N\in\mathcal{N}_{2}$ we have

$q^{(N)}_{n}=\epsilon^{(j)}_{n(\\!\\!\\!\\!\\!\\!\mod D)}$ (14)

when $n\in I^{(N)}_{j}$. Therefore, when $N\in\mathcal{N}_{2}$, we can write

$Q_{N}(z)=\sum_{j=1}^{L}\left(\sum_{n\in
I^{(N)}_{j}}\epsilon^{(j)}_{n\,(\\!\\!\\!\\!\\!\\!\mod D)}z^{n}\right).$ (15)

Let us write the intervals as
$I^{(N)}_{j}=\left[s^{(N)}_{j-1},s^{(N)}_{j}\right)$ so
$0=s^{(N)}_{0}<\dots<s^{(N)}_{L}=N+1$. By a compactness argument and by again
restricting to an infinite subset $\mathcal{N}_{3}\subset\mathcal{N}_{2}$, we
may assume that the sequence of vectors
$\sigma_{N}=\left(\frac{s^{(N)}_{0}}{N},\frac{s^{(N)}_{1}}{N},\dots,\frac{s^{(N)}_{L}}{N}\right)$
converges to $\sigma=(\sigma_{0},\sigma_{1},\dots,\sigma_{L})\in[0,1]^{L+1}$
as $N\to\infty,N\in\mathcal{N}_{3}$. It is clear that
$0=\sigma_{0}\leqslant\sigma_{1}\leqslant\dots\leqslant\sigma_{L}=1$. Let us
now define $\rho=(\rho_{0},\rho_{1},\dots,\rho_{l})\in[0,1]^{l+1}$ to be the
vector obtained from $\sigma$ by taking $\rho_{0}=\sigma_{0}=0$ and for
$i\geqslant 1$ setting $\rho_{i}=\min\\{\sigma_{j}:\sigma_{j}>\rho_{i-1}\\}$,
so one gets $\rho$ by deleting repeated entries in the vector $\sigma$. Let us
also define for each $j\in[l]$ the index $k_{j}$ to be the least integer
$k_{j}\in[L]$ for which $\sigma_{k_{j}}=\rho_{j}$. Hence, if
$N\in\mathcal{N}_{3}$ it follows that for each $j\in[l]$:

$I^{(N)}_{k_{j}}=\left(\rho_{j-1}N+o(N),\rho_{j}N+o(N)\right)$ (16)

and that $\left|I^{(N)}_{i}\right|=o(N)$ if
$i\in[L]\setminus\\{k_{1},\dots,k_{l}\\}$. When $N\in\mathcal{N}_{3}$, we may
write

$Q_{N}(z)=\sum_{j=1}^{l}\left(\sum_{n\in\big{(}\rho_{j-1}N,\rho_{j}N\big{)}}\epsilon^{(k_{j})}_{n\,(\\!\\!\\!\\!\\!\\!\mod
D)}z^{n}\right)+E_{N}(z),$ (17)

where we observe from (15) that if

$\displaystyle E_{N}(z)$
$\displaystyle=Q_{N}(z)-\sum_{j=1}^{l}\left(\sum_{n\in\big{(}\rho_{j-1}N,\rho_{j}N\big{)}}\epsilon^{(k_{j})}_{n\,(\\!\\!\\!\\!\\!\\!\mod
D)}z^{n}\right)$

has a term $z^{n}$ with a non-zero coefficient, then
$n\notin\cup_{j=1}^{l}\left(I^{(N)}_{k_{j}}\cap(\rho_{j-1}N,\rho_{j}N)\right)$.
By (16) there are at most $o(N)$ such integers $n\in[N]$ so it follows that
the $E_{N}(z)$ are polynomials with $o(N)$ terms and coefficients of size at
most $2\max_{r\in R}|r|$. Hence, if we define the sequences
$(\varepsilon^{(j)}_{m})=(\epsilon^{(k_{j})}_{m})$ for $j$ in $[l]$, then we
obtain (13). ∎

For the final section of this paper, it is convenient to have following result
which describes the structure of the polynomials $Q_{N}$ in a more detailed
manner than Lemma 1 does, under the assumption that all the sequences
$(\varepsilon^{(j)}_{m})_{m=1}^{D}$ in (13) are identical.

######  Corollary 1.

Let $D=D(R,d)$ be the constant from Lemma 1, let
$\mathcal{N}^{\prime}\subset\mathbf{N}$ be an infinite set and let
$\\{Q_{N}:N\in\mathcal{N}^{\prime}\\}$ be a collection of polynomials
satisfying the conclusion of Lemma 1. Suppose that the sequences
$(\varepsilon^{(j)}_{m})_{m=1}^{D}\in R^{D}$ in (13) are identical for
$j\in[l]$ and let $(\varepsilon_{m})_{m=1}^{D}\in R^{D}$ be this common
sequence. Then there exist constants $L^{\prime}\leqslant D$ and
$0\leqslant\tau_{0}\leqslant\dots\leqslant\tau_{L^{\prime}}\leqslant 1$,
sequences $(\delta^{(j)}_{m})_{m=1}^{D}$ for $j\in[L^{\prime}]$, and for each
$N\in\mathcal{N}^{\prime}$ a collection of $L^{\prime}$ disjoint intervals
$J^{(N)}_{j}\subset[N]$, $j\in[L^{\prime}]$, such that the following holds.

  1. (i)

The starting point and the length of each of the intervals $J^{(N)}_{j}$ is a
multiple of $D$, and $\min J^{(N)}_{j},\max J^{(N)}_{j}=\tau_{j}N+o(N)$ for
each $j\in[L^{\prime}]$. In particular, the intervals have length
$\left|J^{(N)}_{j}\right|=o_{N\to\infty,N\in\mathcal{N}^{\prime}}(N)$.

  2. (ii)

For each $N\in\mathcal{N}^{\prime}$, we can write

$Q_{N}(z)=\left(\sum_{m=0}^{D-1}\varepsilon_{m}z^{m}\right)\frac{z^{N+1}-1}{z^{D}-1}+\sum_{j=1}^{L^{\prime}}\left(\sum_{m\in
J^{(N)}_{j}}\delta^{(j)}_{m\,(\\!\\!\\!\\!\\!\\!\mod D)}z^{m}\right).$

###### Proof.

This is essentially immediate from the proof of Lemma 1 by taking for each
$N\in\mathcal{N}^{\prime}$ the intervals $J^{(N)}_{j}$ to be all of the
intervals $I^{(N)}_{i}$ for which $i\in[L]\setminus\\{k_{1},\dots,k_{l}\\}$,
using the notation from the proof of Lemma 1. Indeed, to see that item (i)
holds, note that we chose the intervals $I^{(N)}_{i}$ in Lemma 1 to have
starting points that are multiples of $D$ so that their lengths are multiples
of $D$ and hence the same is true for the intervals $J^{(N)}_{j}$. Next,
recall that $I^{(N)}_{k_{j}}=\left(\rho_{j-1}N+o(N),\rho_{j}N+o(N)\right)$ for
$j\in[l]$ by (16). Hence, each of the intervals $J^{(N)}_{j}$, which is of the
form $I^{(N)}_{i}$ with $i\in[L]\setminus\\{k_{1},\dots,k_{l}\\}$, is
contained in an interval of the form
$\left(\rho_{j}N+o(N),\rho_{j}N+o(N)\right)$ so that $\min J^{(N)}_{j},\max
J^{(N)}_{j}=\tau_{j}N+o(N)$ for some
$\tau_{j}\in\\{\rho_{0},\dots,\rho_{l}\\}$. Finally, note that item (ii)
follows directly from (15) and the assumption of Corollary 1 that all the
sequences $(\epsilon^{(k_{j})}_{m})$ are equal to $(\varepsilon_{m})$ for
$j\in[l]$, if we define, corresponding to each interval
$J^{(N)}_{j}=I^{(N)}_{i}$ where $i\in[L]\setminus\\{k_{1},\dots,k_{l}\\}$, the
sequence $(\delta^{(j)}_{m})_{m=1}^{D}$ by

$\delta^{(j)}_{m}=\epsilon^{(i)}_{m}-\varepsilon_{m}.$ (18)

∎

The following lemma will be useful at several stages in our argument. It
allows us to show that a sequence of trigonometric functions with a certain
common structure contains a subsequence of functions that all behave, on an
appropriate scale, like the same fixed function.

######  Lemma 2.

Let $\mathcal{N}\subset\mathbf{N}$ be an infinite set, let
$R\subset\mathbf{C}$ be finite, let
$0\leqslant\rho_{0}<\dots<\rho_{l}\leqslant 1$ and let $l,D\in\mathbf{N}$. Let
$\\{H_{N}(\theta):[0,1]\to\mathbf{C}\\}_{N\in\mathcal{N}}$ be a set of
functions. Suppose that for each $N\in\mathcal{N}$ there are $l+1$
trigonometric polynomials $B^{(N)}_{j}(\theta)$ with coefficients in $R$, with
at most $D$ non-zero coefficients, and of degree $\deg B^{(N)}_{j}=o(N)$ so
that for each $N\in\mathcal{N}$ we can write

$H_{N}(\theta)=\sum_{j=0}^{l}B^{(N)}_{j}(\theta)e(r^{(N)}_{j}\theta),$ (19)

where the $r^{(N)}_{j}$ are real numbers satisfying
$r^{(N)}_{j}=\rho_{j}N+o(N)$. If $(\gamma_{N})_{N\in\mathcal{N}}$ is a
sequence of points $\gamma_{N}\in[0,1]$, then there exists an infinite subset
$\mathcal{N}^{\prime}\subset\mathcal{N}$ and constants $b_{j}\in\mathbf{C}$
such that the following holds. Let $C>0$, then for all
$N\in\mathcal{N}^{\prime}$ and $u\in(-C,C)$ we have

$H_{N}\left(\gamma_{N}+\frac{u}{N}\right)=\sum_{j=0}^{l}b_{j}e(\rho_{j}u)+o_{C;N\to\infty}(1).$
(20)

Moreover, for each $j$ we have

$\lim_{N\to\infty,N\in\mathcal{N}^{\prime}}B^{(N)}_{j}(\gamma_{N})e(r^{(N)}_{j}\gamma_{N})=b_{j}.$
(21)

######  Remark.

Here, we use the notation $o_{C;N\to\infty}(1)$ for a function $f(N,u)$ that
satisfies $\sup_{u\in(-C,C)}|f(N,u)|\to 0$ as
$N\to\infty,N\in\mathcal{N}^{\prime}$.

###### Proof.

This follows from the following elementary compactness argument. Note that
each trigonometric polynomial $B^{(N)}_{j}$ has at most $D$ non-zero terms and
coefficients in a finite set $R$ so that the vectors
$(B^{(N)}_{j}(\gamma_{N})e(r^{(N)}_{j}\gamma_{N}))_{j=0}^{l}$ with
$N\in\mathcal{N}$ form a bounded sequence in $\mathbf{C}^{l+1}$. By
compactness, there exists an infinite set
$\mathcal{N}^{\prime}\subset\mathcal{N}$ and constants $b_{j}\in\mathbf{C}$
such that $B^{(N)}_{j}(\gamma_{N})e(r^{(N)}_{j}\gamma_{N})\to b_{j}$ as
$N\to\infty,N\in\mathcal{N}^{\prime}$. Let $C>0$ be a fixed constant. Since
each $B^{(N)}_{j}$ has degree $o(N)$ and at most $D$ terms with coefficients
in $R$, we can use the basic bound $|e(\alpha)-e(\beta)|\ll|\alpha-\beta|$ for
$\alpha,\beta\in\mathbf{R}$ to deduce that for all $u\in(-C,C)$:

$\displaystyle\left|B^{(N)}_{j}(\gamma_{N}+u/N)e(r^{(N)}_{j}\gamma_{N})-B^{(N)}_{j}(\gamma_{N})e(r^{(N)}_{j}\gamma_{N})\right|$
$\displaystyle=\left|B^{(N)}_{j}(\gamma_{N}+u/N)-B^{(N)}_{j}(\gamma_{N})\right|\ll_{R,D,C}\deg
B^{(N)}_{j}/N=o_{C;N\to\infty}(1)$

and hence that $H_{N}(\gamma_{N}+u/N)=\sum_{j}b_{j}e(ur^{(N)}_{j}/N)+o_{C}(1)$
uniformly for all $u\in(-C,C)$. Using now that
$|e(ur^{(N)}_{j}/N)-e(u\rho_{j})|\ll_{C}o(1)$ when $|u|<C$ by the assumption
that $r^{(N)}_{j}=\rho_{j}N+o(N)$, it follows immediately that
$H_{N}(\gamma_{N}+u/N)=\sum_{j=0}^{l}b_{j}e(\rho_{j}u)+o_{C;N\to\infty}(1)$. ∎

We state one more lemma which provides us with a useful criterion for when a
trigonometric function with real frequencies, like those appearing in the
right hand side of (20), has many zeros.

######  Lemma 3.

Let $H$ be a function of the form

$H(u)=a_{0}+\sum_{j=1}^{l}\left(a_{j}e(\rho_{j}u)+\overline{a_{j}}e(-\rho_{j}u)\right)$
(22)

with coefficients $a_{0}\in\mathbf{R}$, $a_{j}\in\mathbf{C}$ and
$0<\rho_{1}<\dots<\rho_{l-1}<\rho_{l}=1$. Suppose that either
$2|a_{l}|>|a_{0}|$, or else that $2|a_{l}|\geqslant|a_{0}|$ and $a_{j}\neq 0$
for some $j$, $1\leqslant j\leqslant l-1$. Then $H$ has infinitely many sign
changes on $\mathbf{R}$.

To prove this lemma, we use the following classical theorem of Fejér [9] and
Riesz [15], see also [17, page 26] for a more modern discussion.

######  Theorem 5 (Fejér-Riesz Theorem).

Let $w(t)=\sum_{n=-N}^{N}c_{n}e^{itn}$ be a real-valued trigonometric
polynomial that is non-negative for all real $t$. Then $w$ is expressible in
the form $w(t)=|p(e^{it})|^{2}$ for some polynomial
$p(z)=\sum_{n=0}^{N}d_{n}z^{n}$ with $d_{n}\in\mathbf{C}$.

######  Corollary 2.

Let $w(t)=\sum_{n=-N}^{N}c_{n}e^{itn}$ be a real-valued trigonometric
polynomial. Suppose that either $2|c_{N}|>|c_{0}|$, or else that
$2|c_{N}|=|c_{0}|$ and that $c_{n}\neq 0$ for some $1\leqslant n\leqslant
N-1$. Then $w$ has a sign change in $[0,2\pi]$.

###### Proof.

We argue by contradiction, assuming that there is a choice of sign
$\epsilon\in\\{\pm 1\\}$ such that function $\epsilon w(t)$ is non-negative.
By Fejér-Riesz, there then exist $d_{j}\in\mathbf{C}$ such that

$\epsilon c_{n}=\sum_{j=0}^{N-n}d_{j}\overline{d_{n+j}}.$ (23)

Hence,
$|c_{N}|=|d_{0}d_{N}|\leqslant\frac{1}{2}\sum_{j=0}^{N}|d_{j}|^{2}=\frac{|c_{0}|}{2}$
so the inequality $|c_{N}|>\frac{|c_{0}|}{2}$ is false and the assumptions of
the lemma then imply that $c_{n}\neq 0$ for some $n\in[N-1]$. Since
$|c_{N}|\geqslant\frac{|c_{0}|}{2}$ by assumption, this chain of inequalities
also shows that $\sum_{j=1}^{N-1}|d_{j}|^{2}=0$. Hence, we deduce from (23)
that $c_{n}=0$ for all $1\leqslant n\leqslant N-1$, a contradiction. ∎

###### Proof of Lemma 3.

To apply Fejér-Riesz, we write (22) as $H(u)=w_{1}(u)+w_{2}(u)$, where

$\displaystyle
w_{1}(u)=a_{0}+\sum_{j:\rho_{j}\in\mathbf{Q}}\left(a_{j}e(\rho_{j}u)+\overline{a_{j}}e(-\rho_{j}u)\right)$
(24)

is a rescaled real-valued trigonometric polynomial, and

$\displaystyle
w_{2}(u)=\sum_{j:\rho_{j}\notin\mathbf{Q}}\left(a_{j}e(\rho_{j}u)+\overline{a_{j}}e(-\rho_{j}u)\right).$

By the assumptions of Lemma 3, we either have that $2|a_{l}|>|a_{0}|$, or else
that $2|a_{l}|=|a_{0}|$ and $a_{j}\neq 0$ for some $j\in[l-1]$. We consider
two cases. In the first case we assume that $2|a_{l}|>|a_{0}|$, or else that
$2|a_{l}|=|a_{0}|$ and $a_{j}\neq 0$ for some $j$ with
$\rho_{j}\in\mathbf{Q}\setminus\\{0,1\\}$. In the second case, we have that
$2|a_{l}|=|a_{0}|$, that $a_{j}=0$ for all $j$ with
$\rho_{j}\in\mathbf{Q}\setminus\\{0,1\\}$ and that $w_{2}$ has a non-zero
coefficient. The assumptions of the first case allow us to apply Corollary 2
and deduce that $w_{1}$ has a sign change, so there exist
$\theta_{+},\theta_{-}$ such that $w_{1}(\theta_{\pm})=\pm\kappa$, for some
$\kappa>0$. Note from the definition (24) of $w_{1}$ that $w_{1}$ is
$p$-periodic for some $p\in\mathbf{N}$. As
$\sum_{m=1}^{n}e(pm\rho)=O_{n\to\infty}(1)$ for each fixed irrational $\rho$
and as all exponentials in $w_{2}$ have irrational frequencies, we get that

$\sum_{m=1}^{n}H(\theta_{\pm}+pm)=\sum_{m=1}^{n}\left(w_{1}(\theta_{\pm}+pm)+w_{2}(\theta_{\pm}+pm)\right)=\pm\kappa
n+O_{n\to\infty}(1)$

showing that $H(u)>\kappa/2$ and $H(u^{\prime})<-\kappa/2$ for arbitrarily
large $u,u^{\prime}$. This implies the desired conclusion of Lemma 3 that $H$
oscillates between $-\kappa/2$ and $\kappa/2$ infinitely often on
$\mathbf{R}$. Now assume that we are in the second case. So
$2|a_{l}|=|a_{0}|$, $a_{j}=0$ for all $j$ with
$\rho_{j}\in\mathbf{Q}\setminus\\{0,1\\}$, and $w_{2}$ has a non-zero
coefficient. Note that in this case, (24) becomes
$w_{1}(u)=a_{0}+a_{l}e(u)+\overline{a_{l}}e(-u)$ and as $2|a_{l}|=|a_{0}|$ it
is clear that $w_{1}$ has a double root at
$\theta=1/2-\arg(a_{l}/a_{0})/2\pi$. By a similar calculation as above, we
therefore have

$\sum_{m=1}^{n}H(\theta+m)=O_{n\to\infty}(1)$ (25)

as $w_{1}$ is $1-$periodic. Consider now

$\displaystyle w_{2}^{2}(u)=$
$\displaystyle\sum_{j,j^{\prime}:\rho_{j},\rho_{j^{\prime}}\notin\mathbf{Q}}\left(a_{j}a_{j^{\prime}}e((\rho_{j}+\rho_{j^{\prime}})u)+\overline{a_{j}}\overline{a_{j^{\prime}}}e((-\rho_{j}-\rho_{j^{\prime}})u)\right)$
$\displaystyle+$
$\displaystyle\sum_{j,j^{\prime}:\rho_{j},\rho_{j^{\prime}}\notin\mathbf{Q}}\left(a_{j}\overline{a_{j^{\prime}}}e((\rho_{j}-\rho_{j^{\prime}})u)+\overline{a_{j}}a_{j^{\prime}}e((\rho_{j^{\prime}}-\rho_{j})u)\right)$

and as $0<\rho_{j}<1$ for all irrational $\rho_{j}$, the only terms in
$w_{2}^{2}$ having frequencies that are integer multiples of $2\pi$ come from
the diagonal terms $j=j^{\prime}$ and some pairwise disjoint pairs
$\\{j,j^{\prime}\\}$ for which $\rho_{j}+\rho_{j^{\prime}}=1$. So we can
partition $\\{j:\rho_{j}\notin\mathbf{Q}\\}$ into a set $\Lambda_{1}$ of pairs
$\\{j,j^{\prime}\\}$ for which $\rho_{j}+\rho_{j^{\prime}}=1$ and a set
$\Lambda_{2}$ of the remaining $j$. As $w_{1}(\theta+m)=0$, applying the basic
bound that $\sum_{m=1}^{n}e(m\alpha)=O_{n\to\infty}(1)$ for each fixed
$\alpha\in\mathbf{R}\setminus{\mathbf{Z}}$ to the terms in $w_{2}^{2}$ shows
that

$\displaystyle\sum_{m=1}^{n}H(\theta+m)^{2}$
$\displaystyle=n\sum_{j:\rho_{j}\notin\mathbf{Q}}|a_{j}|^{2}+n\sum_{\\{j,j^{\prime}\\}:\rho_{j}+\rho_{j^{\prime}}=1}\left(a_{j}a_{j^{\prime}}e(\theta)+\overline{a_{j}}\overline{a_{j^{\prime}}}e(-\theta)\right)+O_{n\to\infty}(1)$
$\displaystyle=n\sum_{j\in\Lambda_{2}}|a_{j}|^{2}+n\sum_{\\{j,j^{\prime}\\}\in\Lambda_{1}}\left|a_{j}e(\theta/2)+\overline{a_{j^{\prime}}}e(-\theta/2)\right|^{2}+O_{n\to\infty}(1).$
(26)

Hence, if $\Lambda_{2}$ is non-empty, or if
$a_{j}e(\theta/2)+\overline{a_{j^{\prime}}}e(-\theta/2)\neq 0$ for some
$\\{j,j^{\prime}\\}\in\Lambda_{1}$ then (26) is $\gg n$ so that we can use the
following second moment argument to show that $H(\theta+m)$ takes both
positive and negative values for arbitrarily large $m$, implying the desired
conclusion of Lemma 3. Indeed, if for a contradiction we assume that
$H(\theta+m)$ has a constant sign for $m>n_{0}$, then

$\displaystyle\sum_{m=1}^{n}H(\theta+m)^{2}=O_{n\to\infty}(1)+O_{n\to\infty}\left(||H||_{\infty}\left|\sum_{n_{0}<m\leqslant
n}H(\theta+m)\right|\right)=O_{n\to\infty}(1)$

since $H$ is a finite sum of exponentials so bounded on $\mathbf{R}$ and by
(25), but this contradicts (26) as $n\to\infty$. Finally, suppose that
$\Lambda_{2}=\emptyset$ and that
$a_{j}e(\theta/2)+\overline{a_{j^{\prime}}}e(-\theta/2)=0$ for all
$\\{j,j^{\prime}\\}\in\Lambda_{1}$. Then (26) is $O_{n\to\infty}(1)$. We
repeat the calculation above for $H^{\prime}(u)$ to obtain

$\displaystyle\sum_{m=1}^{n}H^{\prime}(\theta+m)^{2}$
$\displaystyle=n\sum_{\\{j,j^{\prime}\\}\in\Lambda_{1}}\left|2\pi
i\rho_{j}a_{j}e(\theta/2)-2\pi
i\rho_{j^{\prime}}\overline{a_{j^{\prime}}}e(-\theta/2)\right|^{2}+O_{n\to\infty}(1)\gg
n,$ (27)

where we used that $w_{1}^{\prime}(\theta+m)=0$ as $w_{1}$ has a double root
at $\theta$, and for the final inequality that
$\rho_{j}a_{j}e(\theta/2)-\rho_{j^{\prime}}\overline{a_{j^{\prime}}}e(-\theta/2)\neq
0$ if $a_{j}e(\theta/2)+\overline{a_{j^{\prime}}}e(-\theta/2)=0$. From (27),
we see that $H^{\prime}(\theta+m)\gg 1$ for arbitrarily large integers $m$,
while the fact that (26) is $O_{n\to\infty}(1)$ implies that
$H(\theta+m)=o(1)$ as $m\to\infty$. Note that $H^{\prime\prime}(u)$ is a sum
of a finite number of exponentials so bounded on $\mathbf{R}$. It is an
elementary exercise in analysis that these three combined bounds on
$H,H^{\prime}$ and $H^{\prime\prime}$ imply that $H$ has infinitely many sign
changes on $\mathbf{R}$; note that if $H^{\prime}(\theta+m)>c$ and
$||H^{\prime\prime}||_{\infty}<C$, then Taylor’s theorem implies that
$H(\theta+m+c/C)>H(\theta+m)+c^{2}/2C$ and
$H(\theta+m-c/C)<H(\theta+m)-c^{2}/2C$. As we have shown that that there are
arbitrarily large $m$ satisfying $H^{\prime}(\theta+m)>c$, combined with the
fact that $H(\theta+m)=o_{m\to\infty}(1)$ this shows that $H(\theta+m+c/C)>0$
while $H(\theta+m-c/C)<0$ for each such large $m$. Hence, $H(u)$ takes
positive and negative values for arbitrarily large $u$, which is the desired
conclusion of Lemma 3. ∎

##  5\. Proof for even degrees

In this section we establish the result of Theorem 2 for even degrees, so our
goal is to show that $Z_{\mathcal{L}}(2N)\to\infty$ as $N\to\infty$. To prove
this, recall from Sect. 3 that we assume for a contradiction that there is an
infinite set of positive integers $\mathcal{N}\subset\mathbf{N}$ and for each
$N\in\mathcal{N}$ a reciprocal Littlewood polynomial $P_{2N}$ of the form (8)
and degree $2N$ which has at most $d$ unimodular roots. We write
$Q_{N}=\sum_{n=0}^{N}q^{(N)}_{n}z^{n}$ for the corresponding polynomials that
we defined in (9), and recall the relation (11) between $P_{2N}$ and $Q_{N}$.
As we are assuming that each $P_{2N}$ has at most $d$ unimodular roots, we
deduce that $\Re(Q_{N}(e^{i\theta})-\frac{1}{2}a_{N})$ also has at most $d$
roots in $[0,2\pi]$. Applying Lemma 1, we obtain an infinite subset
$\mathcal{N}^{\prime}\subset\mathcal{N}$, constants $D,l=O_{d}(1)$ and
$0=\rho_{0}<\dots<\rho_{l}=1$, and $l$ sequences

$\left(\varepsilon^{(j)}_{m}\right)_{m=1}^{D}\in\\{\pm 1\\}^{D},$ (28)

one for each $j\in[l]$, so that for each $N\in\mathcal{N}^{\prime}$:

$Q_{N}(z)=\sum_{j=1}^{l}\left(\sum_{n\in\big{(}\rho_{j-1}N,\rho_{j}N\big{)}}\varepsilon^{(j)}_{n\,(\\!\\!\\!\\!\\!\\!\mod
D)}z^{n}\right)+E_{N}(z),$ (29)

where the $E_{N}(z)$ are polynomials whose coefficients are $O(1)$ and with
$o(N)$ terms. Here and in the rest of the paper, unless explicitly stated
otherwise, the asymptotic notation describes the behaviour as $N\to\infty$. We
rewrite this expression in a form that is more convenient. Note first that we
may assume that $N\in\mathcal{N}^{\prime}$ is sufficiently large since we only
aim to find one polynomial $P_{2N}$ having more than $d$ unimodular roots in
order to get the required contradiction. Let $r^{(N)}_{j}$ be the largest
multiple of $D$ in $\big{(}\rho_{j-1}N,\rho_{j}N\big{)}$ for $j\in[l]$, and
let $r^{(N)}_{0}=0$. Clearly $r^{(N)}_{j}=\rho_{j}N+O(1)$, so we can sum the
geometric series in (29) to get that for each $N\in\mathcal{N}^{\prime}$:

$\displaystyle Q_{N}(z)$
$\displaystyle=\frac{1}{z^{D}-1}\sum_{j=1}^{l}(z^{r^{(N)}_{j}}-z^{r^{(N)}_{j-1}})\left(\sum_{m=0}^{D-1}\varepsilon^{(j)}_{m}z^{m}\right)+E^{\prime}_{N}(z),$
$\displaystyle=\frac{1}{z^{D}-1}\sum_{j=1}^{l}A_{j}(z)(z^{r^{(N)}_{j}}-z^{r^{(N)}_{j-1}})+E^{\prime}_{N}(z),$
(30)

where again the $E^{\prime}_{N}(z)$ are polynomials whose coefficients are
$O(1)$ and with $o(N)$ terms, and where for $1\leqslant j\leqslant l$ we
defined

$A_{j}(z)=\sum_{m=0}^{D-1}\varepsilon^{(j)}_{m}z^{j}.$ (31)

An important consequence of Lemma 1 is that the $A_{j}$ are fixed polynomials,
independent of $N\in\mathcal{N}^{\prime}$. We need the following somewhat
technical result to deduce that the functions $Q_{N}$ have large oscillations.

######  Proposition 1.

Let $l,D\in\mathbf{N}$, let $0=\rho_{0}<\dots<\rho_{l}=1$ and let
$R\subset\mathbf{C}$ be finite. Suppose that $B_{j}(\theta)$ is a
trigonometric polynomial of degree at most $D$ and with coefficients in $R$
for $0\leqslant j\leqslant l$. Define for each large $N\in\mathbf{N}$ the
integer $r^{(N)}_{j}$ to be the largest multiple of $D$ in
$(\rho_{j-1}N,\rho_{j}N)$, and let $r^{(N)}_{0}=0$ for all $N$. Define for
each $N\in\mathbf{N}$ the function $f_{N}$ by

$\displaystyle f_{N}(\theta)\vcentcolon=\Re\left(\frac{1}{e(\theta
D)-1}\sum_{j=1}^{l}B_{j}(\theta)\big{(}e(\theta r^{(N)}_{j})-e(\theta
r^{(N)}_{j-1})\big{)}\right).$ (32)

Suppose that there exists an integer $m$ such that

$\displaystyle\left|B_{l}(m/D)\right|\geqslant\left|\Im\left(B_{1}(m/D)\right)\right|,$
(33)

and if equality holds, then in addition

$\displaystyle B_{j+1}(m/D)\neq B_{j}(m/D)$ (34)

for some $j$, $1\leqslant j\leqslant l-1$. Let $C>0$ be given. Then there
exists a $c=c(C)>0$ such that for all sufficiently large $N$, the function
$f_{N}$ oscillates between $-cN$ and $cN$ at least $C$ times on $[0,1]$.

Here, we say that a function $f$ oscillates between $C_{1}$ and $C_{2}$ at
least $C$ times if there exist $\theta_{1}<\theta_{2}<\dots<\theta_{2C}$ such
that $f(\theta_{2j-1})=C_{1}$ and $f(\theta_{2j})=C_{2}$ for all $j$. Before
proving this proposition, we show how it may be used to deduce that
$Z_{\mathcal{L}}(2N)\to\infty$ as $N\to\infty$.

###### Proof.

Recall that we are supposing for a contradiction that there is an infinite set
$\mathcal{N}\subset\mathbf{N}$ and for each $N\in\mathcal{N}$ a reciprocal
Littlewood polynomial $P_{2N}$ of the form (8) with degree $2N$ having at most
$d$ unimodular roots. By (7) we have

$\displaystyle P_{2N}(e^{i\theta})$ $\displaystyle=e^{i\theta
N}\Re\left(2Q_{N}(e^{i\theta})-a_{N}\right),$

so to get a contradiction it suffices to prove that
$\Re\left(2Q_{N}(e^{i\theta})-a_{N}\right)$ has more than $d$ roots for some
large $N\in\mathcal{N}^{\prime}$. By (30), there is an infinite subset
$\mathcal{N}^{\prime}\subset\mathcal{N}$ so that for each
$N\in\mathcal{N}^{\prime}$ we can write

$\displaystyle\Re\left(2Q_{N}(e(\theta))-a_{N}\right)$
$\displaystyle=2\Re\left(\frac{1}{e(\theta
D)-1}\sum_{j=1}^{l}A_{j}(e(\theta))(e(\theta r^{(N)}_{j})-e(\theta
r^{(N)}_{j-1}))\right)+E^{\prime}_{N}(\theta),$ (35)

where $E^{\prime}_{N}(\theta)$ is a trigonometric polynomial with maximum
value $||E^{\prime}_{N}||_{\infty}=o(N)$. We show that condition (33) holds
with strict inequality for the polynomials $A_{j}$. Let $\zeta=e(1/D)$ be a
primitive $D$th root of unity. By Parseval’s identity and the definition (31)
of $A_{j}$, we have

$\displaystyle\sum_{m=0}^{D-1}\left|A_{l}(\zeta^{m})\right|^{2}$
$\displaystyle=D\sum_{m=0}^{D-1}\left|\varepsilon^{(l)}_{m}\right|^{2}=D^{2}$

since $\varepsilon^{(l)}_{m}=\pm 1$ by (28). Similarly

$\displaystyle\sum_{m=0}^{D-1}\left|\Im\left(A_{1}(\zeta^{m})\right)\right|^{2}$
$\displaystyle=D\sum_{m=1}^{D-1}\left(\frac{\varepsilon^{(1)}_{m}-\varepsilon^{(1)}_{D-m}}{2}\right)^{2}\leqslant
D(D-1).$

Hence, there exists some $m$ for which
$\left|A_{l}(\zeta^{m})\right|>\left|\Im\left(A_{1}(\zeta^{m})\right)\right|$
so that the condition of Proposition 1 is satisfied. Proposition 1 gives a
$c=c(2d)>0$ such that for $N$ sufficiently large, the function

$\displaystyle\theta\mapsto\Re\left(\frac{1}{e(\theta
D)-1}\sum_{j=1}^{l}A_{j}(e(\theta))(e(\theta r^{(N)}_{j})-e(\theta
r^{(N)}_{j-1}))\right)$

oscillates between $-cN$ and $cN$ at least $2d$ times. Since
$||E^{\prime}_{N}(\theta)||_{\infty}=o(N)$ as
$N\to\infty,N\in\mathcal{N}^{\prime}$, from (35) we get the required
contradiction that $\Re\left(2Q_{N}(e^{i\theta})-a_{N}\right)$ has at least
$2d$ roots for sufficiently large $N\in\mathcal{N}^{\prime}$. ∎

The same argument also establishes Theorem 3 if one uses the relation (7) to
reduce the problem for cosine polynomials to an equivalent problem for
reciprocal polynomials of _even_ degree. The polynomials that one gets are
reciprocal Littlewood polynomials of even degree up to a constant term that is
$O(1)$, so this makes no difference in the proof above. We now move on to
proving Proposition 1.

###### Proof of Proposition 1.

Let $m$ satisfy (33), and if there is equality in (33) then let (34) hold in
addition. Let $C>0$ be given, and let $f_{N}$ be the function defined in (32)
so that our aim is to show that the $f_{N}$ have at least $C$ oscillations of
size $\gg N$ for large $N$. We will consider angles
$\theta\in\left(\frac{m}{D}-\frac{C^{\prime}}{N},\frac{m}{D}+\frac{C^{\prime}}{N}\right)=\vcentcolon
I_{N}$, where $C^{\prime}>0$ is a sufficiently large constant (depending on
$C$) to be chosen later. First observe that we can rewrite

$\displaystyle f_{N}(\theta)=\frac{1}{2\sin(2\pi
D\theta)}\Im\left(\sum_{j=1}^{l}B_{j}(\theta)\left(e(\theta(r^{(N)}_{j}-D/2))-e(\theta(r^{(N)}_{j-1}-D/2)\right)\right).$

For all $\theta\in I_{n}$ we have that $|2\sin(2\pi D\theta)|\ll
C^{\prime}/N$.333The dependence on $m,l,D$ and $R$ will be suppressed
throughout this argument as they are fixed as far as Proposition 1 is
concerned. Hence, if we define the functions

$\displaystyle
H_{N}(\theta)=\Im\sum_{j=1}^{l}B_{j}(\theta)\left(e(\theta(r^{(N)}_{j}-D/2))-e(\theta(r^{(N)}_{j-1}-D/2))\right)$

then it suffices to show that there exists a constant $c>0$ such that the
$H_{N}$ oscillate at least $C$ times between $-c$ and $c$ on the interval
$I_{N}$, as this would imply that the $f_{N}$ have $C$ oscillations of size
$\gg_{c,C^{\prime}}N$ on $I_{N}$. Combining the terms in $H_{N}$ with equal
frequencies, we can rewrite

$\displaystyle H_{N}(\theta)$
$\displaystyle=\Im\left(B_{1}(\theta)+B_{l}(\theta)e(\theta(r^{(N)}_{l}-D/2))\right)$
$\displaystyle+\Im\sum_{j=1}^{l-1}\left(B_{j}(\theta)-B_{j+1}(\theta)\right)e(\theta(r^{(N)}_{j}-D/2)).$

Recall that by the assumptions of Proposition 1, the $B_{j}$ are trigonometric
polynomials of degree at most $D=O(1)$ with coefficients in a finite set $R$,
and also that $r^{(N)}_{j}-D/2=\rho_{j}N+o(N)$. Hence, we may apply Lemma 2
with the constant sequence $(\gamma_{N})_{N\in\mathbf{N}}=(m/D)$ to obtain an
infinite set $\mathcal{N}^{\prime}\subset\mathbf{N}$ and constants
$b_{j}\in\mathbf{C}$ such that for each $N\in\mathcal{N}^{\prime}$ and
$u\in(-C^{\prime},C^{\prime})$ we have444It is not hard to see from the proof
of Lemma 2 that we may in fact take $\mathcal{N}^{\prime}=\mathbf{N}$ since
the trigonometric polynomials $B_{j}$ appearing in Proposition 1 do not depend
on $N$.

$H_{N}\left(\frac{m}{D}+\frac{u}{N}\right)=\Im\left(\sum_{j=0}^{l}b_{j}e(\rho_{j}u)\right)+o_{C^{\prime};N\to\infty}(1).$
(36)

Let us now define

$\displaystyle H(u)$
$\displaystyle=\Im\left(\sum_{j=0}^{l}b_{j}e(\rho_{j}u)\right)=\Im(b_{1})+\frac{1}{2i}\sum_{j=1}^{l}(b_{j}e(\rho_{j}u)-\overline{b_{j}}e(-\rho_{j}u))$
(37)

to be the function of $u$ appearing in the right hand side above. Note that
$H(u)$ is a fixed function independent of $N$, so we have reduced our task to
showing that $H$ has at least $C$ sign changes on $\mathbf{R}$. Indeed, if we
can show this then there exists some $C^{\prime}$ and $c>0$ such that $H$
oscillates between $-c$ and $c$ at least $C$ times on the interval
$(-C^{\prime},C^{\prime})$. Hence, from (36) we would deduce the desired
result that the $H_{N}(\theta)$ oscillate between $-c/2$ and $c/2$ at least
$C$ times on $I_{N}$ for large $N$. To accomplish this final task, we simply
check that the conditions of Lemma 3 are satisfied by the function $H$. As the
trigonometric polynomials $B_{j}$ do not depend on $N$ and as we defined
$r^{(N)}_{0}=0$ in the statement of Proposition 1, we see from equation (21)
in Lemma 2 that the coefficients of $H$ satisfy

$\displaystyle b_{0}$ $\displaystyle=B_{1}(m/D)$ $\displaystyle|b_{j}|$
$\displaystyle=|B_{j+1}(m/D)-B_{j}(m/D)|$ for $1\leqslant j\leqslant l-1$,
$\displaystyle|b_{l}|$ $\displaystyle=|B_{l}(m/D)|$

Hence, the assumptions (33), $\eqref{prop1cond2}$ of Proposition 1 imply
precisely that $|b_{l}|\geqslant|\Im(b_{0})|$ and that if equality holds, then
$b_{j}\neq 0$ for some $j\in[l-1]$. By Lemma 3 these conditions imply that
$H(u)$ has infinitely many sign changes on $\mathbf{R}$, so this completes the
proof of Proposition 1. ∎

##  6\. Proof for odd degrees

We finish this paper by proving the remaining part of Theorem 2, namely that
$Z_{\mathcal{L}}(2N+1)\to\infty$ as $N\to\infty$. Let us briefly recall the
set up of our argument from Sect. 3. We assume for a contradiction that there
is a fixed integer $d$ and an infinite set $\mathcal{N}\subset\mathbf{N}$ of
odd integers such that for each $N\in\mathcal{N}$ there exists a reciprocal
Littlewood polynomial $P_{N}$ of the form (8) and degree $N$ which has at most
$d$ unimodular roots. The corresponding polynomials
$Q_{N}=\sum_{n=0}^{N}q^{(N)}_{n}z^{n}$ that we defined in (10) have
coefficients

$\displaystyle q^{(N)}_{n}=\begin{cases}\pm 1&\text{for $n$ odd}\\\
0&\text{for $n$ even.}\end{cases}$ (38)

and recall that for odd $N$ we have the relation (12) between $P_{N}$ and
$Q_{N}$. As we are assuming that each $P_{N}$ has at most $d$ unimodular
roots, we deduce that $\Re(Q_{N}(e^{i\theta}))$ has at most $2d$ roots in
$[0,2\pi]$ for each $N\in\mathcal{N}$ so that we may apply Lemma 1. We obtain
an infinite subset $\mathcal{N}^{\prime}\subset\mathcal{N}$, constants
$D,l=O_{d}(1)$ and $0=\rho_{0}<\dots<\rho_{l}=1$, and a sequence

$\left(\varepsilon^{(j)}_{m}\right)_{m=1}^{D}\in\\{-1,0,1\\}^{D}$ (39)

for each $j\in[l]$, so that for each $N\in\mathcal{N}^{\prime}$:

$Q_{N}(z)=\sum_{j=1}^{l}\left(\sum_{n\in\big{(}\rho_{j-1}N,\rho_{j}N\big{)}}\varepsilon^{(j)}_{n\,(\\!\\!\\!\\!\\!\\!\mod
D)}z^{n}\right)+E_{N}(z),$ (40)

where the $E_{N}(z)$ are polynomials whose coefficients are $O(1)$ and with
$o(N)$ terms. Note from the definition of the $\varepsilon^{(j)}_{m}$ in (14)
and from (38) that the period $D$ is even and that for each $j$:

$\varepsilon^{(j)}_{m}=\begin{cases}\pm 1&\text{for $m$ odd}\\\ 0&\text{for
$m$ even.}\end{cases}$ (41)

Let us again define for each large $N\in\mathbf{N}$ the integer $r^{(N)}_{j}$
to be the largest multiple of $D$ in $\big{(}\rho_{j-1}N,\rho_{j}N\big{)}$ for
$j\in[l]$ , and let $r^{(N)}_{0}=0$. Clearly $r^{(N)}_{j}=\rho_{j}N+O(1)$, so
we can sum the geometric series in (40) to get that for each large
$N\in\mathcal{N}^{\prime}$:

$\displaystyle Q_{N}(z)$
$\displaystyle=\frac{1}{z^{D}-1}\sum_{j=1}^{l}(z^{r^{(N)}_{j}}-z^{r^{(N)}_{j-1}})\left(\sum_{m=0}^{D-1}\varepsilon^{(j)}_{m}z^{m}\right)+E^{\prime}_{N}(z),$
$\displaystyle=\frac{1}{z^{D}-1}\sum_{j=1}^{l}A_{j}(z)(z^{r^{(N)}_{j}}-z^{r^{(N)}_{j-1}})+E^{\prime}_{N}(z),$
(42)

where the $E^{\prime}_{N}(z)$ are polynomials whose coefficients are $O(1)$
and with $o(N)$ terms, and where for $1\leqslant j\leqslant l$ we defined

$A_{j}(z)=\sum_{m=0}^{D-1}\varepsilon^{(j)}_{m}z^{j}.$ (43)

We show that the $Q_{N}$ with $N\in\mathcal{N}^{\prime}$ either satisfy the
conditions of Proposition 1 so that we may conclude as in the proof for even
degrees, or else that all of the sequences $(\varepsilon^{(j)}_{m})$ with
$j\in[l]$ are identical. By (42), we have for $N\in\mathcal{N}^{\prime}$ that

$\displaystyle\Re\left(Q_{N}(e(\theta))\right)$
$\displaystyle=\Re\left(\frac{1}{e(\theta
D)-1}\sum_{j=1}^{l}A_{j}(e(\theta))(e(\theta r^{(N)}_{j})-e(\theta
r^{(N)}_{j-1}))\right)+E^{\prime}_{N}(\theta),$ (44)

where $||E^{\prime}_{N}||_{\infty}=o_{N\to\infty}(N)$. Parseval’s identity and
the definition (43) of the $A_{j}$ give

$\displaystyle\sum_{m=0}^{D-1}\left|A_{l}(\zeta^{m})\right|^{2}$
$\displaystyle=D\sum_{m=0}^{D-1}\left|\varepsilon^{(l)}_{m}\right|^{2}=\frac{D^{2}}{2},$

as $\varepsilon_{m}^{(j)}=\pm 1$ for $m$ odd and $\varepsilon_{m}^{(j)}=0$ for
$m$ even by (41). Similarly,

$\displaystyle\sum_{m=0}^{D-1}\left|\Im\left(A_{1}(\zeta^{m})\right)\right|^{2}$
$\displaystyle=D\sum_{m=1}^{D-1}\left(\frac{\varepsilon^{(1)}_{m}-\varepsilon^{(1)}_{D-m}}{2}\right)^{2}\leqslant\frac{D^{2}}{2}.$
(45)

Hence, there either exists some $m$ for which
$\left|A_{l}(\zeta^{m})\right|>\left|\Im\left(A_{1}(\zeta^{m})\right)\right|$
so that the condition (33) of Proposition 1 holds with strict inequality, or
else equality must hold in (45) and condition (33) for all $m$. Now, if some
two of the sequences
$(\varepsilon^{(j)}_{m})_{m=1}^{D},(\varepsilon^{(j+1)}_{m})_{m=1}^{D}$ are
distinct, then (34) is satisfied for some $m$. We conclude that unless the
sequences $(\varepsilon_{m}^{(j)})$ are identical for all $j$, then the
conditions of Proposition 1 are satisfied and we deduce that (44) has more
than $2d$ roots for large $N\in\mathcal{N}^{\prime}$, which is the required
contradiction.

To finish our proof, it therefore only remains to show that the following
assumptions lead to a contradiction. Assume that
$\mathcal{N}\subset\mathbf{N}$ is an infinite subset and that
$\\{Q_{N}:N\in\mathcal{N}\\}$ is a collection of polynomials satisfying the
conclusion of Lemma 1 with all of the sequences
$(\varepsilon^{(j)}_{m})_{m=1}^{D}$ being identical, and such that
$\Re(Q_{N}(e^{i\theta}))$ has at most $2d$ roots in $[0,2\pi]$ for each
$N\in\mathcal{N}$. Recall from Sect. 3 that there do exist functions
$h_{m}(\theta)=\Re\left(\sum_{n=0}^{2m}(-1)^{n+1}e^{i(2n+1)\theta}\right)$
with a periodic sequence of coefficients that have a bounded number of sign
changes on $[0,2\pi]$ for all $m$. This shows that one cannot establish the
conclusion of Proposition 1 in this case, and hence we need to proceed by a
different argument. Note that our assumptions in this final case of the
argument correspond precisely to the assumptions of Corollary 1 and we obtain
the following from its conclusion. There exist constants $L=O_{d}(1)$ and
$0\leqslant\tau_{0}\leqslant\dots\leqslant\tau_{L}\leqslant 1$, sequences
$(\delta^{(j)}_{m})_{m=1}^{D}$ for $j\in[L]$, and for each $N\in\mathcal{N}$ a
collection of $L$ disjoint intervals $J^{(N)}_{j}\subset[N]$, $j\in[L]$, such
that the following holds.

  1. (i)

The starting point and the length of each of the intervals $J^{(N)}_{j}$ is a
multiple of $D$, and $\min J^{(N)}_{j},\max J^{(N)}_{j}=\tau_{j}N+o(N)$ for
each $j\in[L]$. In particular, the intervals have length
$|J^{(N)}_{j}|=o_{N\to\infty,N\in\mathcal{N}}(N)$.

  2. (ii)

For each $N\in\mathcal{N}$, we can write

$Q_{N}(z)=\left(\sum_{m=0}^{D-1}\varepsilon_{m}z^{m}\right)\frac{z^{N+1}-1}{z^{D}-1}+\sum_{j=1}^{L}\left(\sum_{m\in
J^{(N)}_{j}}\delta^{(j)}_{m\,(\\!\\!\\!\\!\\!\\!\mod D)}z^{m}\right).$ (46)

We collect some important properties of the sequence
$(\varepsilon_{m})_{m=0}^{D-1}$. Recall that we may assume that equality holds
in (45) and hence we deduce that the sequence $(\varepsilon_{m})_{m=0}^{D-1}$
satisfies

$\varepsilon_{m}=-\varepsilon_{D-m},$ (47)

and from (41) we see that

$\varepsilon_{m}=\begin{cases}\pm 1&\text{for $m$ odd}\\\ 0&\text{for $m$
even.}\end{cases}$ (48)

By comparing coefficients of the polynomials on both sides of (46) and by
using (38) and (48), we obtain the following useful description of the
sequences $(\delta^{(j)}_{m})_{m=0}^{D-1}$ for $j\in[L]$:

$\delta^{(j)}_{m}\in\\{-2\varepsilon_{m},0\\}.$ (49)

To get a contradiction, our goal is to show that $\Re(Q_{N}(e^{i\theta}))$ has
more than $2d$ roots for some $N\in\mathcal{N}$ and we begin by rewriting (46)
in the form

$\displaystyle\Re(Q_{N}(e^{i\theta}))=\frac{1}{2\sin(D\theta)}\Im\left(A_{0}(e^{i\theta})\left(e^{iN\theta}-1\right)+\sum_{j=1}^{L}A^{(N)}_{j}(e^{i\theta})\right)$
(50)

where

$A_{0}(z)\vcentcolon=\sum_{m=0}^{D-1}\varepsilon_{m}z^{m-D/2}$ (51)

is a fixed Laurent polynomial independent of $N$, and where for $j\in[L]$ we
write

$A^{(N)}_{j}(z)\vcentcolon=\left(z^{\max J^{(N)}_{j}+1}-z^{\min
J^{(N)}_{j}}\right)\sum_{m=0}^{D-1}\delta^{(j)}_{m}z^{m-D/2}.$ (52)

We record some useful properties of the polynomials $A^{(N)}_{j}$. Observe
first that for each $j\in[L]$, all terms in $A^{(N)}_{j}(z)$ have degree
$\tau_{j}N+o(N)$ as $\min J^{(N)}_{j},\max J^{(N)}_{j}=\tau_{j}N+o(N)$ by item
(i) above and because $D=O(1)$, and further observe that each $A^{(N)}_{j}$
consists of at most $2D=O(1)$ such terms. We remind the reader that for the
rest of the paper, unless explicitly stated otherwise, the asymptotic notation
describes the behaviour as $N\to\infty$. Our next step is to group together
the terms in (50) whose degrees have asymptotically the same size. Hence, let
$\rho_{1},\dots,\rho_{l-1}$ be the distinct values in the sequence
$\tau_{0},\dots,\tau_{L}$ other than $0,1$ and let $\rho_{0}=0,\rho_{l}=1$.
After combining terms in (50) with equal $\tau_{j}$, it clearly suffices to
show that the following function has more than $2d+2D$ roots for some
$N\in\mathcal{N}$:

$\displaystyle
H_{N}(\theta)=\Im\left(\sum_{j=0}^{l}B^{(N)}_{j}(\theta)e(\rho_{j}N\theta)\right),$
(53)

where

$\displaystyle
B^{(N)}_{j}(\theta)=\begin{cases}A_{0}(e(\theta))+e(-N\theta)\sum_{m:\tau_{m}=1}A^{(N)}_{m}(e(\theta))&\text{if
}j=l,\\\
e(-\rho_{j}N\theta)\sum_{j:\tau_{m}=\rho_{j}}A^{(N)}_{m}(e(\theta))&\text{if
}1\leqslant j\leqslant l-1,\\\
-A_{0}(e(\theta))+\sum_{m:\tau_{m}=0}A^{(N)}_{m}(e(\theta))&\text{if
}j=0.\end{cases}$ (54)

We see from (52) that each of the $B^{(N)}_{j}(\theta)$ has at most
$2D(L+1)=O(1)$ terms and since we noted that each term in $A^{(N)}_{j}$ has
degree $\tau_{j}N+o(N)$, we obtain the crucial fact that the $B^{(N)}_{j}$
have degree $o(N)$. Having written $H_{N}$ in this way, it is clear from the
properties of the $B^{(N)}_{j}$ that we just stated that the conditions of
Lemma 2 are satisfied. By applying Lemma 2 with a sequence $(\gamma_{N})$ with
$\gamma_{N}\in[0,1]$ and a constant $C>0$, we obtain an infinite subset
$\mathcal{N}^{\prime}\subset\mathcal{N}$ and constants $b_{j}\in\mathbf{C}$ so
that for $u\in(-C,C)$ and $N\in\mathcal{N}^{\prime}$:

$H_{N}\left(\gamma_{N}+\frac{u}{N}\right)=\Im\left(\sum_{j=0}^{l}b_{j}e(\rho_{j}u)\right)+o_{C;N\to\infty}(1).$
(55)

Note the important property that the $b_{j}$ are constants independent of $N$
and hence the first function on the right hand side is a fixed trigonometric
function independent of $N$. Our strategy is to find a good choice of the
sequence $\gamma_{N}$ so that this function will have many sign changes on
$(-C,C)$, and in practice this will involve us finding $(\gamma_{N})$ such
that the coefficients $b_{j}$ satisfy the assumptions of Lemma 3. To continue,
it is convenient to first handle the special case for which
$B^{(N)}_{l}(\theta)=-B^{(N)}_{0}(\theta)$ in a separate lemma.

######  Lemma 4.

Let $\mathcal{N}\subset\mathbf{N}$ be an infinite set, let
$R\subset\mathbf{Z}$ be finite and let $l,D\in\mathbf{N}$. Suppose that
$G_{N}(\theta),N\in\mathcal{N}$ are functions, that
$0=\rho_{0}<\dots<\rho_{l}=1$ and that for each $N\in\mathcal{N}$ there are
$l+1$ trigonometric functions $B^{(N)}_{j}(\theta)$ with coefficients in $R$,
with at most $D$ non-zero coefficients, and each having degree $\deg
B^{(N)}_{j}=o(N)$ so that we can write for $N\in\mathcal{N}$:

$G_{N}(\theta)=\Im\left(\sum_{j=0}^{l}B^{(N)}_{j}(\theta)e(\rho_{j}N\theta)\right).$
(56)

If $B^{(N)}_{l}(\theta)=-B^{(N)}_{0}(\theta)$ are identical as functions of
$\theta$ for infinitely many $N\in\mathcal{N}$, then for each constant $C$
there exists a function $G_{N}(\theta)$ having at least $C$ zeros.

###### Proof.

We split the argument into two cases. In the first case, we assume that there
is an infinite set $\mathcal{M}\subset\mathcal{N}$ so that
$B^{(N)}_{l}(\theta)=-B^{(N)}_{0}(\theta)$ for all $N\in\mathcal{M}$ and in
addition that each of the other trigonometric polynomials $B^{(N)}_{j}$ with
$1\leqslant j\leqslant l-1$ is identically $0$. Then from (56) we get that
$G_{N}(\theta)=\Im\left(-B^{(N)}_{0}(\theta)e(N\theta)+B^{(N)}_{0}(\theta)\right)$
and it is clear that $\theta=n/N$ is a root for all $n\in[N]$ so that we
obtain arbitrarily many roots for large $N\in\mathcal{M}$. In the second case,
we may assume that there is an infinite set $\mathcal{M}\subset\mathcal{N}$
and an index $j\in[l-1]$ so that $B^{(N)}_{l}(\theta)=-B^{(N)}_{0}(\theta)$
and that $B^{(N)}_{j}$ is not identically $0$ for any $N\in\mathcal{M}$. Note
that for every non-zero $B^{(N)}_{j}$ we have
$\int_{0}^{1}|B^{(N)}_{j}(\theta)|^{2}\,d\theta\geqslant 1$ by Parseval’s
Theorem and as all its Fourier coefficients are in $R\subset\mathbf{Z}$ by
assumption. It follows that for each $N\in\mathcal{M}$ there exists a
$\gamma_{N}\in[0,1]$ so that $|B^{(N)}_{j}(\gamma_{N})|\geqslant 1$. The
assumptions of Lemma 4 imply all of the assumptions of Lemma 2 so we may apply
it with the sequence $(\gamma_{N})_{N\in\mathcal{M}}$ to obtain the following.
There exists an infinite subset $\mathcal{N}^{\prime}\subset\mathcal{M}$ and
constants $b_{m}\in\mathbf{C}$ for $m\in\\{0,1,\dots,l\\}$ such that for
$u\in(-C,C)$ and $N\in\mathcal{N}^{\prime}$:

$G_{N}\left(\gamma_{N}+\frac{u}{N}\right)=\Im\left(\sum_{m=0}^{l}b_{m}e(\rho_{m}u)\right)+o_{C;N\to\infty}(1)$
(57)

and note that by (21) we can determine the size of the constants $b_{m}$ using

$\lim_{N\to\infty,N\in\mathcal{N}^{\prime}}\left|B^{(N)}_{m}(\gamma_{N})\right|=|b_{m}|.$

In particular, as $B^{(N)}_{l}(\theta)=-B^{(N)}_{0}(\theta)$ by assumption we
deduce that $|b_{l}|\geqslant|b_{0}|$ and as we chose the $\gamma_{N}$ so that
$|B^{(N)}_{j}(\gamma_{N})|\geqslant 1$ we also have that $b_{j}\neq 0$. Hence,
we can apply Lemma 3 to deduce that the first function on the right hand side
of (57) (which now is a fixed function of $u$, independent of $N$) has
infinitely many sign changes on $\mathbf{R}$. If we choose $C$ to be a
sufficiently large constant and then let $N\to\infty,N\in\mathcal{N}^{\prime}$
it follows that $G_{N}$ has arbitrarily many roots for large $N$, as desired.
∎

To deal with the remaining and more substantial case in which
$B^{(N)}_{l}(\theta)$ and $-B^{(N)}_{0}(\theta)$ are distinct functions of
$\theta$ for all large $N\in\mathcal{N}$, we establish the following
proposition.

######  Proposition 2.

Let $\mathcal{N}\subset\mathbf{N}$ be an infinite set, $D\in 2\mathbf{N}$ and
$C>0$. Suppose that $(\varepsilon_{m})\in\\{-1,0,1\\}^{D}$ is a sequence which
is not identically zero that satisfies $\varepsilon_{m}=-\varepsilon_{D-m}$,
and define the sine polynomial

$a(t)=i^{-1}\sum_{m=-D/2}^{D/2}\varepsilon_{m}e(mt)=2\sum_{m=0}^{D/2}\varepsilon_{m}\sin(mt).$
(58)

Suppose that for each $N\in\mathcal{N}$ we have two sine polynomials that are
not both identically zero:

$\displaystyle s_{1}^{(N)}(t)$
$\displaystyle=\sum_{m\in\Lambda_{1}^{(N)}}\delta_{m}\left(\sin
mt-\sin((m-p_{m}^{(N)}D)t)\right),$ (59) $\displaystyle s_{2}^{(N)}(t)$
$\displaystyle=\sum_{m\in\Lambda_{2}^{(N)}}\delta_{m}\left(\sin
mt-\sin((m-p_{m}^{(N)}D)t)\right),$

where $\Lambda_{j}^{(N)}$ are sets of positive integers of size at most $C$,
where $\delta:\mathbf{N}\to\mathbf{Z}$ is given by

$\delta_{m}=-2\varepsilon_{m(\\!\\!\\!\\!\mod D)}$ (60)

and where the $p_{m}^{(N)}$ are positive integers555It is a slight yet
unimportant abuse of notation that we use $p_{m}^{(N)}$ in the expressions of
both $s_{1}^{(N)}$ and $s_{2}^{(N)}$ since technically $p_{m}^{(N)}$ may also
depend on whether $m\in\Lambda^{(N)}_{1}$ or $m\in\Lambda^{(N)}_{2}$.
satisfying $|m|\geqslant|m-p_{m}^{(N)}D|$ for each $m\in\Lambda^{(N)}_{j}$.
Then there exists a $\kappa>0$ and an infinite subset
$\mathcal{N}^{\prime}\subset\mathcal{N}$ such that for each
$N\in\mathcal{N}^{\prime}$ we can find a $\gamma_{N}\in[0,1]$ satisfying

$\left|a(\gamma_{N})+s_{1}^{(N)}(\gamma_{N})\right|\geqslant\left|a(\gamma_{N})-s_{2}^{(N)}(\gamma_{N})\right|+\kappa.$
(61)

Before proving Proposition 2, let us show how it may be used to finish the
proof. Let $\mathcal{N}\subset\mathbf{N}$ be the infinite set such that the
functions $H_{N}$ in (53) have at most $2d+2D$ roots for $N\in\mathcal{N}$.
From Lemma 4 we deduce that $B^{(N)}_{l}(\theta)$ and $-B^{(N)}_{0}(\theta)$
are distinct functions of $\theta$ for all large $N\in\mathcal{N}$. We begin
by checking that, for each large $N\in\mathcal{N}$, we can write the functions
$B^{(N)}_{0},B^{(N)}_{l}$ from (54) in the form

$\displaystyle\Im\left(B^{(N)}_{l}(\theta)\right)$
$\displaystyle=a(\theta)+s^{(N)}_{1}(\theta)$
$\displaystyle\Im\left(B^{(N)}_{0}(\theta)\right)$
$\displaystyle=-a(\theta)+s^{(N)}_{2}(\theta),$

where $a(\theta)$ and $s^{(N)}_{1}(\theta),s^{(N)}_{2}(\theta)$ with
$N\in\mathcal{N}$ are functions that satisfy the conditions of Proposition 2.
From the definition of the $B^{(N)}_{j}$ in (54) we see that

$\displaystyle B^{(N)}_{l}(\theta)$
$\displaystyle=A_{0}(e(\theta))+e(-N\theta)\sum_{j:\tau_{j}=1}A^{(N)}_{j}(e(\theta)),$
$\displaystyle B^{(N)}_{0}(\theta)$
$\displaystyle=-A_{0}(e(\theta))+\sum_{j:\tau_{j}=0}A^{(N)}_{j}(e(\theta)).$

The definition (51) of $A_{0}$ and the fact that
$\varepsilon_{m}=-\varepsilon_{D-m}$ by (47) imply that
$\Im(A_{0})=i^{-1}\sum_{m=-D/2}^{D/2}\varepsilon_{m}e(mt)$, so
$a(t)\vcentcolon=\Im(A_{0}(e(t))$ does indeed satisfy the assumptions of
Proposition 2. We then take

$\displaystyle s^{(N)}_{1}(t)$
$\displaystyle=\Im\sum_{j:\tau_{j}=1}A^{(N)}_{j}(e(t))e(-Nt),$ $\displaystyle
s^{(N)}_{2}(t)$ $\displaystyle=\Im\sum_{j:\tau_{j}=0}A^{(N)}_{j}(e(t)).$

Recall the definition (52) of the polynomials $A^{(N)}_{j}$ so as they have at
most $2D=O(1)$ terms, as their coefficients satisfy (49) and as the lengths of
the intervals $J^{(N)}_{j}$ are multiples of $D$ by item (i) on page 46, we
see that $s^{(N)}_{1},s^{(N)}_{2}$ consist of $O(1)$ terms of the form
$-\delta_{m}(\sin mt-\sin(m-pD)t)$ where $|m|\geqslant|m-pD|$ and hence that
they are sine polynomials of the desired form (59). Finally, the functions
$s^{(N)}_{1},s^{(N)}_{2}$ are not both identically zero for any large
$N\in\mathcal{N}$ since we deduced from Lemma 4 that
$B^{(N)}_{l}\neq-B^{(N)}_{0}$ for all large $N\in\mathcal{N}$. Hence, we may
apply Proposition 2 to deduce that there exists an infinite set
$\mathcal{N}^{\prime}\subset\mathcal{N}$ and a sequence
$(\gamma_{N})_{N\in\mathcal{N}^{\prime}}$ such that (61) holds, which in this
setting means that

$\left|\Im(B^{(N)}_{l}(\gamma_{N}))\right|\geqslant\left|\Im(B^{(N)}_{0}(\gamma_{N}))\right|+\kappa.$
(62)

Similarly as in (55), we may then apply Lemma 2 with the functions
$H_{N}(\theta),N\in\mathcal{N}^{\prime}$ and the sequence
$(\gamma_{N})_{N\in\mathcal{N}^{\prime}}$ provided by Proposition 2 to obtain
an infinite subset $\mathcal{N}^{\prime\prime}\subset\mathcal{N}^{\prime}$ and
constants $b_{m}\in\mathbf{C}$ for $m\in\\{0,1,\dots,l\\}$ such that for
$u\in(-C,C)$ and $N\in\mathcal{N}^{\prime\prime}$ the functions $H_{N}$ in
(53) satisfy:

$H_{N}\left(\gamma_{N}+\frac{u}{N}\right)=\Im\left(\sum_{m=0}^{l}b_{m}e(\rho_{m}u)\right)+o_{C;N\to\infty}(1)$
(63)

and furthermore by (21) that

$\lim_{N\to\infty,N\in\mathcal{N}^{\prime}}B^{(N)}_{m}(\gamma_{N})e(\rho_{m}N\gamma_{N})=b_{m}.$

In particular, since (62) holds for all $N\in\mathcal{N}^{\prime}$ and as
$\rho_{0}=0$, we get that $|b_{l}|\geqslant|\Im(b_{0})|+\kappa$. Hence, the
first function on the right hand side of (63) (which is a trigonometric
function of $u$, independent of $N$) satisfies the conditions of Lemma 3, so
we may apply Lemma 3 to deduce that it has infinitely many sign changes on
$\mathbf{R}$. If we choose $C$ to be a sufficiently large constant and then
let $N\to\infty,N\in\mathcal{N}^{\prime\prime}$ it follows from (63) that
$H_{N}$ has arbitrarily many roots for large $N\in\mathcal{N}^{\prime\prime}$,
which is the required contradiction. Note that to obtain the crucial
inequality $|b_{l}|>|\Im(b_{0})|$ which allows us to use Lemma 3, we require
the constant $\kappa>0$ appearing in (62) to be independent of $N$. Showing
that such a $\kappa>0$ which is independent of $N$ exists is the main
difficulty in the proof Proposition 2. It seems possible that Proposition 2 is
in fact a special case of the following question to which the author does not
know the answer.

######  Problem 2.

Is it true that for any positive integer $k\in\mathbf{N}$, there exists a
$\kappa=\kappa(k)>0$ such that the following holds? Let $s_{1}(t),s_{2}(t)$ be
two distinct sine polynomials of the form
$s_{j}(t)=\sum_{n\in\Lambda_{j}}\varepsilon_{n,j}\sin nt$ with
$|\Lambda_{j}|\leqslant k$ terms and coefficients $\varepsilon_{n,j}=\pm 1$,
then there exists a $\gamma\in[0,1]$ such that
$|s_{1}(\gamma)|\geqslant|s_{2}(\gamma)|+\kappa.$

Returning to the main argument, it only remains to prove Proposition 2.

###### Proof of Proposition 2.

Our task consists of finding a constant $\kappa>0$ and an infinite subset
$\mathcal{N}^{\prime}\subset\mathcal{N}$ such that for each
$N\in\mathcal{N}^{\prime}$, there exists some $t=t(N)$ that satisfies

$\left|a(t)+s_{1}^{(N)}(t)\right|\geqslant\left|a(t)-s_{2}^{(N)}(t)\right|+\kappa.$
(64)

Let us define the function $p:\mathcal{N}\to\mathbf{N}$ by

$p=p(N)=\max\\{p_{m}^{(N)}:m\in\Lambda_{1}^{(N)}\cup\Lambda_{2}^{(N)}\\}.$
(65)

As the sets $\Lambda_{j}^{(N)}$ have size at most $C$ for all
$N\in\mathcal{N}$ by the assumptions of Proposition 2, we can use a
compactness argument to find an infinite subset
$\mathcal{N}_{1}\subset\mathcal{N}$ for which
$\Lambda_{1}^{(N)},\Lambda_{2}^{(N)}$ have fixed size and such that all of the
limits $\lim_{N\to\infty,N\in\mathcal{N}_{1}}\frac{p_{m}^{(N)}}{p(N)}$
converge to non-negative constants for
$m\in\Lambda_{1}^{(N)}\cup\Lambda_{2}^{(N)}$. It will be technically
convenient for later to get rid of the contribution from those
$m\in\Lambda_{1}^{(N)}\cup\Lambda_{2}^{(N)}$ for which
$p_{m}^{(N)}=o_{N\to\infty}(p)$, so let us define

$\Lambda^{(N)}\vcentcolon=\left\\{m\in\Lambda_{1}^{(N)}\cup\Lambda_{2}^{(N)}:\lim_{N\to\infty,N\in\mathcal{N}_{1}}\frac{p_{m}^{(N)}}{p(N)}>0\right\\}.$
(66)

Throughout the proof, the limit $N\to\infty$ should always be taken in an
appropriate infinite subset $\mathcal{N}_{i}\subset\mathcal{N}$ but we will
not explicitly state this every time. We define the following truncated
version of the functions in (59):

$\displaystyle s_{\Lambda}^{(N)}(t)\vcentcolon=$
$\displaystyle\sum_{m\in\Lambda_{1}^{(N)}\cap\Lambda^{(N)}}\delta_{m}\left(\sin
mt-\sin((m-p_{m}^{(N)}D)t)\right)$ (67) $\displaystyle+$
$\displaystyle\sum_{m\in\Lambda_{2}^{(N)}\cap\Lambda^{(N)}}\delta_{m}\left(\sin
mt-\sin((m-p_{m}^{(N)}D)t)\right)$

and let us call the first term on the right hand side $s_{1,\Lambda}^{(N)}(t)$
and the second $s_{2,\Lambda}^{(N)}(t)$. To find a $t$ for which (64) holds,
we will consider angles $t=\frac{2\pi r}{D}+\frac{u}{p(N)}$ where $u$ ranges
over $(-c,c)$ for a constant $c$ to be chosen later. We will need the
following lemma later to show that we may work with the functions
$s^{(N)}_{j,\Lambda}(t)$ instead of $s^{(N)}_{j}(t)$.

######  Lemma 5.

Let $s^{(N)}_{1},s^{(N)}_{2}$ be the sine polynomials in (59) and let
$s^{(N)}_{1,\Lambda},s^{(N)}_{2,\Lambda}$ be their truncations that we defined
in (67). Write $\gamma_{r}=\frac{2\pi r}{D}$ and define for $c>0$ the
intervals
$I_{N}(c)\vcentcolon=\left(\gamma_{r}-\frac{c}{p(N)},\gamma_{r}+\frac{c}{p(N)}\right)$
for $N\in\mathcal{N}_{1}$. Then for any given $\rho>0$, one can choose $c>0$
sufficiently small such that for all $N\in\mathcal{N}_{1}$ we have

$\sup_{t\in I_{N}(c)}\left|s_{j}^{(N)}\left(t\right)\right|<\rho,$ (68)

for $j=1,2$. Furthermore, we have for all $t\in I_{N}(c)$ that

$\displaystyle
s_{j}^{(N)}\left(t\right)=s_{j,\Lambda}^{(N)}\left(t\right)+o_{c;N\to\infty}(1).$
(69)

###### Proof.

We use the bound $|\sin\alpha-\sin\beta|\ll|\alpha-\beta|$ to deduce for
$t=\frac{2\pi r}{D}+\frac{u}{p}$ with $u\in(-c,c)$ that

$\displaystyle\left|\sin mt-\sin((m-p_{m}^{(N)}D)t)\right|\ll
p_{m}^{(N)}|u|/p(N)\leqslant c,$ (70)

where we used the definition (65) of $p=p(N)$ for the final inequality. Since
each sine polynomial $s^{(N)}_{j}$ is a sum of at most $C$ terms of the form
$\delta_{m}(\sin mt-\sin((m-p_{m}^{(N)}D)t))$ by the assumption of Proposition
2, this inequality implies that (68) holds when $c>0$ is chosen to be
sufficiently small in terms of $\rho$. Further, since we have that
$p_{m}^{(N)}=o(p(N))$ by definition (66) when $m\notin\Lambda^{(N)}$, the
second part of Lemma 5 follows immediately from the first inequality in (70).
∎

The next step in our approach is to find a useful decomposition of
$s_{\Lambda}^{(N)}$. Recall that $\Lambda^{(N)}$ is a finite set of fixed size
$\lambda$ for all $N\in\mathcal{N}_{1}$ and let us order it as
$\Lambda^{(N)}=\\{m_{1}^{(N)}<\dots<m_{\lambda}^{(N)}\\}$. We may then
restrict to an infinite subset $\mathcal{N}_{2}\subset\mathcal{N}_{1}$ such
that each of the limits

$\lim_{N\to\infty,N\in\mathcal{N}_{2}}\frac{m_{j}^{(N)}-m_{j-1}^{(N)}}{p(N)}$

converges for $2\leqslant j\leqslant\lambda$, either to a non-negative
constant or to $+\infty$. Our aim is to partition the set $\Lambda^{(N)}$ into
maximal sets whose elements all differ by $O(p(N))$. To achieve this, let
$m_{1}^{*}(N)<\dots<m_{\lambda^{\prime}}^{*}(N)$ be all of the
$m_{j}^{(N)}\in\Lambda^{(N)}$ for which
$\lim_{N\to\infty,N\in\mathcal{N}_{2}}\frac{m_{j}^{(N)}-m_{j-1}^{(N)}}{p}=\infty$,
and we then partition $\Lambda^{(N)}$ into the sets

$\Lambda^{(N,j)}\vcentcolon=\\{m\in\Lambda^{(N)}:m_{j}^{*}(N)\leqslant
m<m_{j+1}^{*}(N)\\}.$ (71)

Note that these $\Lambda^{(N,j)}$ indeed satisfy the desired property that
$m-m^{\prime}=O(p(N))$ if $m,m^{\prime}\in\Lambda^{(N,j)}$ are in the same
part of the partition, and that $|m-m^{\prime}|/p(N)\to\infty$ if
$m\in\Lambda^{(N,j)}$ and $m^{\prime}\in\Lambda^{(N,j^{\prime})}$ with $j\neq
j^{\prime}$. Hence, for each $N\in\mathcal{N}_{2}$ we may equivalently define
the parts of the partition by

$\Lambda^{(N,j)}\vcentcolon=\\{m\in\Lambda^{(N)}:|m-m_{j}^{*}(N)|=O(p)\\}.$
(72)

We may now obtain the useful decomposition of the function $s_{\Lambda}^{(N)}$
in (67) by combining the terms coming from those $m$ in the same
$\Lambda^{(N,j)}$ for each $j$, $1\leqslant j\leqslant\lambda^{\prime}$. First
however, we note that it will be a technical convenience to use the integers
$n_{j}(N)$ instead of the $m_{j}^{*}(N)$ in the decomposition, where we define
$n_{j}(N)$ to be the largest multiple of $D$ less than $m_{j}^{*}(N)-p(N)D$.
We can now write down the desired decomposition of the functions
$s^{(N)}_{\Lambda}$ for each $N\in\mathcal{N}_{2}$ and we collect its useful
properties in the following lemma.

######  Lemma 6.

For each $N\in\mathcal{N}_{2}$, we can write the sine polynomial
$s^{(N)}_{\Lambda}$ from (67) in the form

$s_{\Lambda}^{(N)}(t)=\Im\left(\sum_{j=1}^{\lambda^{\prime}}C_{j}^{(N)}(t)e^{in_{j}(N)t}\right)$
(73)

where the functions $C_{j}^{(N)}(t)$ are trigonometric polynomials of the form

$C_{j}^{(N)}(t)=e^{-in_{j}(N)t}\sum_{m\in\Lambda^{(N,j)}}\delta_{m}\left(e^{imt}-e^{i(m-p_{m}^{(N)}D)t}\right).$
(74)

Moreover, the decomposition (73) has the following properties.

  1. (i)

For each $N\in\mathcal{N}_{2}$, we have that

$n_{j}(N)=m^{*}_{j}(N)-p(N)D+O(1)$ (75)

and that the partition
$\Lambda^{(N)}=\cup_{j=1}^{\lambda^{\prime}}\Lambda^{(N,j)}$ from (72) can
equivalently be defined by

$\Lambda^{(N,j)}=\\{m\in\Lambda^{(N)}:|m-n_{j}(N)|=O(p(N))\\},$ (76)

for $1\leqslant j\leqslant\lambda^{\prime}$.

  2. (ii)

For each $N\in\mathcal{N}_{2}$, the $C_{j}^{(N)}$ are trigonometric
polynomials of degree $O(p)$ with $O(1)$ terms for $j\in[\lambda^{\prime}]$.

  3. (iii)

The ratios between the factors $e^{n_{j}(N)t}$ oscillate on a much faster
scale than the trigonometric polynomials $C^{(N)}_{j}(t)$, by which we mean
that

$\lim_{N\to\infty,N\in\mathcal{N}_{2}}\frac{n_{j+1}(N)-n_{j}(N)}{p(N)}=+\infty$
(77)

for all $j\in[\lambda^{\prime}-1]$.

###### Proof.

The proof is merely a matter of unpacking definitions. The fact that we may
write the sine polynomial $s^{(N)}_{\Lambda}$ from (67) in the form (73) is
immediate from the definitions (74) of the $C^{(N)}_{j}$ and the fact that
$\Lambda^{(N)}=\cup_{j=1}^{\lambda^{\prime}}\Lambda^{(N,j)}$. For item (i),
recall that just above the statement of Lemma 6, we defined the integers
$n_{j}(N)$ for $1\leqslant j\leqslant\lambda^{\prime}$ to be the largest
multiple of $D$ less than $m^{*}_{j}(N)-p(N)D$ so that (75) is clear. This
also shows that $n_{j}(N)=m^{*}(N)+O(p(N))$ so that the observation that the
partition of $\Lambda^{(N)}$ may be defined by (76) is immediate from (72).
For item (ii), we recall that $\mathcal{N}_{2}$ was in part defined so that
$|\Lambda^{(N)}|=\lambda$ for all $N\in\mathcal{N}_{2}$ so it follows that
each $C^{(N)}_{j}$ is a trigonometric polynomial with at most
$\lambda=O_{N\to\infty}(1)$ terms. We further observe from its definition (74)
that all frequencies of $C^{(N)}_{j}$ are of the form $m-n_{j}(N)$ or
$m-p^{(N)}_{m}D-n_{j}(N)$ for some $m\in\Lambda^{(N,j)}$. Hence, from (76) and
as $p^{(N)}_{m}=O(p(N)))$ holds trivially by the definition (65) of $p$, we
see that $\deg C^{(N)}_{j}(t)=O(p(N))$. Finally, item (iii) follows from the
definitions of the integers $m^{*}_{j}(N)$ just before (71) which state that
$|m^{*}_{j}(N)-m^{*}_{j-1}(N)|/p(N)\to\infty$ as
$N\to\infty,N\in\mathcal{N}_{2}$ and the fact that
$n_{j}(N)=m^{*}_{j}(N)+O(p)$ by (75). ∎

Next, we analyse the trigonometric polynomials $C_{j}^{(N)}(t)$. Recall that
we write $\gamma_{r}=\frac{2\pi r}{D}$ so from (74) it is clear that the
imaginary part of $C^{(N)}_{j}$ has the following second derivative at
$\gamma_{r}$:

$\displaystyle\Im(C_{j}^{(N)})^{\prime\prime}\left(\gamma_{r}\right)$
$\displaystyle=\sum_{m\in\Lambda^{(N,j)}}-\delta_{m}\left((m-n_{j}(N))^{2}-(m-n_{j}(N)-p_{m}^{(N)}D)^{2}\right)\frac{\zeta^{mr}-\zeta^{-mr}}{2i}$
$\displaystyle=D\sum_{m\in\Lambda^{(N,j)}}-\delta_{m}p_{m}^{(N)}(2m-2n_{j}(N)-p_{m}^{(N)}D)\frac{\zeta^{mr}-\zeta^{-mr}}{2i}.$

Note that by (75), the integers $2m-2n_{j}(N)-p_{m}^{(N)}D$ appearing here are
of magnitude $\Theta(p(N))$, for all $m\in\Lambda^{(N,j)}$. The function
$a(t)$ defined in (58) satisfies

$\displaystyle
a(\gamma_{r})=i^{-1}\sum_{m=-D/2}^{D/2}\varepsilon_{m}\zeta^{mr}=\sum_{m=-D/2}^{D/2}\varepsilon_{m}\frac{\zeta^{mr}-\zeta^{-mr}}{2i}.$

Since $\delta_{m}=-2\varepsilon_{m(\\!\\!\\!\\!\mod D)}$ and as
$\varepsilon_{m}=-\varepsilon_{D-m}$ by the assumptions of Proposition 2,
Parseval’s identity then shows for each $j\in[\lambda^{\prime}]$ that

$\displaystyle\sum_{r=0}^{D-1}a(\gamma_{r})\Im(C_{j}^{(N)})^{\prime\prime}\left(\gamma_{r}\right)$
(78)
$\displaystyle=D^{2}\\!\\!\\!\sum_{r\in\mathbf{Z}/D\mathbf{Z}}-\delta_{m}\varepsilon_{m}\\!\\!\left(\sum_{m\in\Lambda^{(N,j)},m\equiv
r(\\!\\!\\!\\!\\!\mod D)}p_{m}^{(N)}(2m-2n_{j}(N)-p_{m}^{(N)}D)\\!\right)$
$\displaystyle=2D^{2}\\!\\!\\!\sum_{m\in\Lambda^{(N,j)}}p_{m}^{(N)}(2m-2n_{j}(N)-p_{m}^{(N)}D)\\!$
$\displaystyle=\Theta(p(N)^{2})$

where the lower bound in the final line follows as $p^{(N)}_{m}\gg p(N)$ for
$m\in\Lambda^{(N)}$ by the definition (66) of $\Lambda^{(N)}$ and from the
fact that $2m-2n_{j}(N)-p_{m}^{(N)}D=\Theta(p)$ for $m\in\Lambda^{(N,j)}$ by
(75), and the corresponding upper bound from this same fact and as
$\left|\Lambda^{(N,j)}\right|\leqslant\lambda=O(1)$.

On the other hand, note that we have the trivial upper bound
$||\Im(C_{j}^{(N)})^{\prime\prime}||_{\infty}=O(p^{2})$ as $C_{j}^{(N)}$ is a
trigonometric polynomial of degree $O(p)$ with $O(1)$ terms by item (ii) in
Lemma 6. We also have the trivial bound $||a(t)||_{\infty}=O(1)$ since the
function $a(t)$ that we defined in (58) is a fixed sine polynomial,
independent of $N$. Combining these trivial upper bounds with the bound in
(78), we therefore deduce that for each $N\in\mathcal{N}_{2}$, there exists
some $r=r(N)$, $0\leqslant r\leqslant D-1$, such that

$\displaystyle|a(\gamma_{r})|$ $\displaystyle\gg 1\text{ and }$ (79)
$\displaystyle|\Im(C_{j}^{(N)})^{\prime\prime}(\gamma_{r})|$ $\displaystyle\gg
p(N)^{2},$

where the implied constants are independent of $N$, and moreover that
$a(\gamma_{r})$ and $\Im(C_{j}^{(N)})^{\prime\prime}(\gamma_{r})$ have the
same sign. Let us define for a constant $c>0$ the intervals

$\displaystyle
I_{N}(c)\vcentcolon=\left(\gamma_{r}-\frac{c}{p(N)},\gamma_{r}+\frac{c}{p(N)}\right)$

for $N\in\mathcal{N}_{2}$. Now as $a(t)$ is a fixed sine polynomial
independent of $N$ that satisfies $a(\gamma_{r})\neq 0$ by (79), we can choose
a sufficiently small constant $c>0$, also independent of $N$, so that
$\inf_{t\in(\gamma_{r}-c,\gamma_{r}+c)}|a(t)|\gg 1$ and hence we certainly
have that $\inf_{t\in I_{N}(c)}|a(t)|\gg 1$ for all $N\in\mathcal{N}_{2}$
because $p(N)\geqslant 1$ since it is a positive integer by definition (65).
By Lemma 5, we can choose the constant $c>0$ sufficiently small so the
functions $s_{j,\Lambda}^{(N)}$ will be arbitrarily small on the interval
$I_{N}(c)$ and hence we may choose such a $c>0$, independent of $N$, so that
all three of the functions $a(t),a(t)+s_{1,\Lambda}^{(N)}(t)$ and
$a(t)-s_{2,\Lambda}^{(N)}(t)$ have the same sign for $t\in I_{N}(c)$, for each
$N\in\mathcal{N}_{2}$. Hence, to prove the desired inequality (64), it
suffices to show that there exists a $\kappa>0$, independent of $N$, such that
the function
$s_{\Lambda}^{(N)}(t)=s_{1,\Lambda}^{(N)}(t)+s_{2,\Lambda}^{(N)}(t)$ that we
defined in (67) takes the value $\kappa\operatorname{sgn}(a(\gamma_{r}))$ in
the interval $I_{N}(c)$, as this would show precisely that

$|a(t)+s_{1,\Lambda}^{(N)}(t)|\geqslant|a(t)-s_{2,\Lambda}^{(N)}(t)|+\kappa$

for some $t=t(N)\in I_{(}c)$ since we just noted that
$a,a+s_{1,\Lambda}^{(N)}$ and $a-s_{2,\Lambda}^{(N)}$ have the same sign on
$I_{N}(c)$. From (69) in Lemma 5, we would then obtain the desired result that
$|a(t)+s_{1}^{(N)}(t)|\geqslant|a(t)-s_{2}^{(N)}(t)|+\kappa/2$ for all large
$N\in\mathcal{N}_{2}$. We state this final task in the proof of Proposition 2
as a lemma.

######  Lemma 7.

Let $s_{\Lambda}^{(N)}$ be the function defined in (67) for
$N\in\mathcal{N}_{2}$, let $r=r(N)$ satisfy both of the bounds in (79), and
let $c>0$ be a fixed constant. Then there exists a fixed constant $\kappa>0$,
independent of $N$, such that the following holds. For each sufficiently large
$N\in\mathcal{N}_{2}$, there is a
$t=t(N)\in(\gamma_{r}-c/p(N),\gamma_{r}+c/p(N))$ such that
$\operatorname{sgn}(a(\gamma_{r}))\times s_{\Lambda}^{(N)}(t)\geqslant\kappa$.

###### Proof.

We prove this under the assumption that $a(\gamma_{r})>0$ as the case where
$a(\gamma_{r})<0$ is analogous. We also have that
$\Im(C_{j}^{(N)})^{\prime\prime}(\gamma_{r})>0$ as we noted after (79) that
$a(\gamma_{r})$ and $\Im(C_{j}^{(N)})^{\prime\prime}(\gamma_{r})$ have the
same sign. Note that by the definition (74) in Lemma 6, the trigonometric
polynomials $C_{j}^{(N)}$ with $N\in\mathcal{N}_{2}$ each consist of a finite
number of terms which vanish at $\gamma_{r}=\frac{2\pi r}{D}$. We may
therefore use Taylor’s theorem to write for all $u\in(-c,c)$:

$\displaystyle\Im(C_{j}^{(N)})\left(\gamma_{r}+\frac{u}{p}\right)$
$\displaystyle=\frac{\Im(C_{j})^{\prime}(\gamma_{r})}{p}u+\frac{\Im(C_{j})^{\prime\prime}(\gamma_{r})}{2p^{2}}u^{2}+O\left(u^{3}\right),$
(80)

where we used the trivial bound for the third derivative
$\Im(C_{j}^{(N)})^{\prime\prime\prime}=O(p^{3})$ that holds as $C_{j}^{(N)}$
is a finite sum of exponential whose frequencies are $O(p)$ by item (ii) in
Lemma 6. Hence if we plug in the bound
$\Im(C_{j}^{(N)})^{\prime\prime}(\gamma_{r})\gg p^{2}$ that we obtained in
(79), then we deduce that there exists a $\kappa\gg_{c}1$, independent of $N$,
such that the function $\Im(C_{j}^{(N)})(\gamma_{r}+u/p)$ takes the value
$\kappa$ for some $u\in(-c,c)$. In fact, we have proven the slightly stronger
claim that for each $N\in\mathcal{N}_{2}$, there exists an interval
$J_{j}=J_{j}(N)\subset(-\gamma_{r}-\frac{c}{p(N)},\gamma_{r}+\frac{c}{p(N)})$
of length $|J_{j}|\gg p(N)^{-1}$ such that $\Im(C_{j}^{(N)}(t))>\kappa$ for
all $t\in J_{j}$. Let
$J\subset(-\gamma_{r}-\frac{c}{p},\gamma_{r}+\frac{c}{p})$ be such an interval
for $j=1$, so $|J|\gg p(N)^{-1}$ and we have for $t\in J$ that

$\Im(C_{1}^{(N)}(t))>\kappa.$ (81)

We are now in a position to finish the argument, but we need to consider two
cases based on whether $n_{1}(N)=O(p(N))$ or $p(N)=o(n_{1}(N))$ as
$N\to\infty,N\in\mathcal{N}_{2}$, where we remind the reader that the
$n_{j}(N)$ are integers such that the decomposition (73) of
$s^{(N)}_{\Lambda}$ holds. First, if $n_{1}(N)=O(p(N))$ then we note that we
could have simply defined $n_{1}(N)=0$ and
$C^{(N)}_{1}(t)=\sum_{m\in\Lambda^{(N,1)}}\delta_{m}\left(e^{imt}-e^{i(m-p^{(N)}_{m}D)t}\right)$
in the decomposition (73) of $s_{\Lambda}^{(N)}$ and we check that all of the
desired properties in items (i),(ii) and (iii) of Lemma 6 still hold: for item
(i) note that
$\Lambda^{(N,1)}=\\{m\in\Lambda:|m-n_{1}(N)|=O(p)\\}=\\{m\in\Lambda:|m|=O(p)\\}$
as we are assuming that $n_{1}(N)=O(p)$, item (ii) is clear as the function
$C^{(N)}_{1}$ above has degree $O(p)$ since we just noted that $m=O(p)$ for
all $m\in\Lambda^{(N,1)}$, and item (iii) is trivial as could only have
decreased $n_{1}(N)$. Hence, integrating the expression (73) over $J=J(N)$
gives

$\displaystyle\int_{J}s_{\Lambda}^{(N)}(t)\,dt$
$\displaystyle=\int_{J}\Im(C_{1}^{(N)}(t))\,dt+\sum_{j=2}^{\lambda^{\prime}}\int_{J}\Im(C_{j}^{(N)}(t)e^{in_{j}(N)t})\,dt$
$\displaystyle=\int_{J}\Im(C_{1}^{(N)}(t))\,dt+O\left(\sum_{j=2}^{\lambda^{\prime}}(n_{j}(N)+O(p))^{-1}\right)$

where the bound in the second line follows from items (i) and (ii) in Lemma 6
which show that the frequency of any term in $C_{j}^{(N)}(t)e^{in_{j}(N)t}$ is
of size $n_{j}(N)+O(p)$. Recall now (77) which certainly implies that
$p(N)=o(n_{j}(N))$ for $j\geqslant 2$ so that $n_{j}(N)^{-1}=o(p^{-1})$.
Hence, as $J$ was chosen so that $|J|\gg p^{-1}$ and (81) holds, the integral
above is $>\kappa|J|+o(p(N)^{-1})\gg\kappa|J|$ as
$N\to\infty,N\in\mathcal{N}_{2}$. This shows that for $N\in\mathcal{N}_{2}$
sufficiently large, there exists a $t\in
J\subset(-\gamma_{r}-\frac{c}{p},\gamma_{r}+\frac{c}{p})$ such that
$s_{\Lambda}(t)^{(N)}\gg\kappa$ which is the desired conclusion of Lemma 7.

Finally, in the second case we may assume that
$\frac{n_{1}(N)}{p(N)}\to\infty$ as $N\to\infty,N\in\mathcal{N}_{2}$. As we
showed that there exists an interval $J$ satisfying (81), there certainly
exists a $\gamma\in J\subset(-\gamma_{r}-\frac{c}{p},\gamma_{r}+\frac{c}{p})$
such that

$|\Im(C_{1}^{(N)}(\gamma))|>\kappa.$ (82)

Again recall that $p(N)=o(n_{j+1}(N)-n_{j}(N))$ for all $1\leqslant
j\leqslant\lambda^{\prime}-1$ by (77), and as we are assuming that
$p(N)=o(n_{1}(N))$ now, it is possible to define a variable $\omega=\omega(N)$
such that $p(N)=o(\omega)$ and

$\displaystyle\omega(N)=o\big{(}\min\\{n_{1}(N),n_{2}(N)-n_{1}(N),\dots,n_{\lambda}(N)-n_{\lambda-1}(N)\\}\big{)}.$
(83)

As the trigonometric polynomials $C_{j}^{(N)}$ consist of $O(1)$ terms of
degree $O(p(N))$ by item (ii) in Lemma 6, it follows that
$\left|C_{j}^{(N)}(t)-C_{j}^{(N)}(\gamma)\right|\ll
p(N)/\omega(N)=o_{N\to\infty}(1)$ holds uniformly for all
$t=\gamma+\frac{u}{\omega(N)}$ where $u$ ranges over $(-1,1)$. Hence, for
$u\in(-1,1)$ and $t=\gamma+\frac{u}{\omega(N)}$ we can rewrite (73) as

$s_{\Lambda}^{(N)}(t)=\Im\left(\sum_{j=1}^{\lambda^{\prime}}C_{j}^{(N)}(\gamma)e^{in_{j}t}\right)+o_{N\to\infty}(1)$
(84)

where $o_{N\to\infty}(1)$ denotes a function that tends to $0$ as $N\to\infty$
uniformly for all $u\in(-1,1)$. Note now that the $C_{j}^{(N)}(\gamma)$ are
fixed coefficients independent of $t$. Hence, if we integrate this expression
over the interval
$I=I(N)\vcentcolon=(\gamma-\frac{1}{\omega(N)},\gamma+\frac{1}{\omega(N)})$,
we get

$\displaystyle\int_{I}s_{\Lambda}^{(N)}(t)\,dt$
$\displaystyle=O\left(\sum_{j=1}^{\lambda^{\prime}}n_{j}^{-1}\right)+o(|I|)=o(\omega^{-1})+o(|I|)=o(|I|)$
(85)

as $N\to\infty$, and a similar calculation yields

$\displaystyle\int_{I}\left(s_{\Lambda}^{(N)}(t)\right)^{2}\,dt$
$\displaystyle=|I|\left(\frac{1}{2}\sum_{j=1}^{\lambda^{\prime}}|C_{j}^{(N)}(\gamma)|^{2}\right)+O(\max_{j>j^{\prime}}(n_{j}-n_{j^{\prime}})^{-1})+o(|I|)$
$\displaystyle\gg|I|$ (86)

as $N\to\infty$, where we used that $|I|=2\omega^{-1}$ so that
$\max_{j>j^{\prime}}(n_{j}-n_{j^{\prime}})^{-1})=o(\omega^{-1})=o(|I|)$ by the
definition (83) of $\omega$, and for the final inequality that
$|\Im(C_{1}^{(N)}(\gamma))|>\kappa$ as we chose $\gamma$ to satisfy (82). The
following straightforward second moment then shows that there exists a
$\kappa^{\prime}\gg 1$, independent of $N$, such that $s_{\Lambda}^{(N)}$
takes both the values $\pm\kappa^{\prime}$ in
$I(N)\subset(\gamma_{r}-\frac{c}{p(N)},\gamma_{r}+\frac{c}{p(N)})$ when
$N\in\mathcal{N}_{2}$ is sufficiently large, which implies the desired result
of Lemma 7. Indeed, note that if such a $\kappa^{\prime}$ did not exist, then
we could find functions $g^{(N)}(t)$ satisfying
$\sup_{I}|g^{(N)}(t)|=o_{N\to\infty}(1)$ such that
$f^{(N)}(t)\vcentcolon=\epsilon s_{\Lambda}^{(N)}(t)+g^{(N)}(t)$ is non-
negative for all $t\in I$, for some $\epsilon\in\\{\pm 1\\}$. Then, combined
with the fact that $\sup_{I}|g^{(N)}(t)|=o_{N\to\infty}(1)$ by definition,
(85) shows that $\int_{I}f^{(N)}=o(|I|)$ while (86) gives
$\int_{I}\left(f^{(N)}\right)^{2}\gg|I|$. However, note that the $f^{(N)}$ are
uniformly bounded on $I$ for $N\in\mathcal{N}_{2}$ because the $g^{(N)}$ are
uniformly bounded by definition and because $s_{\Lambda}^{(N)}$ is a
trigonometric polynomial with $\lambda^{\prime}=O(1)$ terms by (84) and all
these terms are $O(1)$ by item (ii) in Lemma 6. As $f^{(N)}$ is also non-
negative by definition, we deduce that
$\int_{I}\left(f^{(N)}\right)^{2}\ll\int_{I}f^{(N)}$ as
$N\to\infty,N\in\mathcal{N}_{2}$. This contradicts our estimates above and
therefore finishes the proof of Lemma 7;

∎

This completes the proof of Proposition 2. ∎

## References

  * [1] P. Borwein and T. Erdélyi.  Lower bounds for the number of zeros of cosine polynomials in the period: a problem of Littlewood.  Acta Arith., 128(4):377–384, 2007.
  * [2] P. Borwein, T. Erdélyi, R. Ferguson, and R. Lockhart.  On the zeros of cosine polynomials: solution to a problem of Littlewood.  Ann. of Math. (2), 167(3):1109–1117, 2008.
  * [3] P. Borwein, T. Erdélyi, and F. Littmann.  Polynomials with coefficients from a finite set.  Trans. Amer. Math. Soc., 360(10):5145–5154, 2008.
  * [4] P. Drungilas.  Unimodular roots of reciprocal Littlewood polynomials.  J. Korean Math. Soc., 45(3):835–840, 2008.
  * [5] T. Erdélyi.  On the zeros of polynomials with Littlewood-type coefficient constraints.  Michigan Math. J., 49(1):97–111, 2001.
  * [6] T. Erdélyi.  Polynomials with Littlewood-type coefficient constraints.  In Approximation theory, X (St. Louis, MO, 2001), Innov. Appl. Math., pages 153–196. Vanderbilt Univ. Press, Nashville, TN, 2002.
  * [7] T. Erdélyi.  The number of unimodular zeros of self-reciprocal polynomials with coefficients in a finite set.  Acta Arith., 176(2):177–200, 2016.
  * [8] T. Erdélyi.  Improved lower bound for the number of unimodular zeros of self-reciprocal polynomials with coefficients in a finite set.  Acta Arith., 192(2):189–210, 2020.
  * [9] L. Fejér.  Über trigonometrische Polynome.  J. Reine Angew. Math., 146:53–82, 1916.
  * [10] T. Juškevičius and J. Sahasrabudhe.  Cosine polynomials with few zeros.  Bull. Lond. Math. Soc., 53(3):877–892, 2021.
  * [11] S. V. Konyagin.  On zeros of sums of cosines.  Mat. Zametki, 108(4):547–551, 2020.
  * [12] J. E. Littlewood.  Some problems in real and complex analysis.  D. C. Heath and Company Raytheon Education Company, Lexington, MA, 1968.
  * [13] I. D. Mercer.  Unimodular roots of special Littlewood polynomials.  Canad. Math. Bull., 49(3):438–447, 2006.
  * [14] K. Mukunda.  Littlewood Pisot numbers.  J. Number Theory, 117(1):106–121, 2006.
  * [15] F. Riesz.  Über ein Problem des Herrn Carathéodory.  J. Reine Angew. Math., 146:83–87, 1916.
  * [16] J. Sahasrabudhe.  Counting zeros of cosine polynomials: on a problem of Littlewood.  Adv. Math., 343:495–521, 2019.
  * [17] B. Simon.  Orthogonal polynomials on the unit circle. Part 1, volume 54, Part 1 of American Mathematical Society Colloquium Publications.  American Mathematical Society, Providence, RI, 2005.  Classical theory.

Mathematical Institute, Andrew Wiles Building, University of Oxford, Radcliffe
Observatory Quarter, Woodstock Road, Oxford, OX2 6GG, UK.
<EMAIL_ADDRESS>