[proofplan]
We prove the dual inequality by viewing the additive large sieve as a finite-dimensional operator norm estimate. Define the [linear map](/page/Linear%20Map) taking a sequence indexed by $M < n \leq M+N$ to its exponential sums over $\Theta$. The standard additive large sieve gives an upper bound for the norm of this operator, and finite-dimensional [Hilbert space](/page/Hilbert%20Space) duality gives the same bound for its adjoint. The adjoint contains $e(-n\theta)$ rather than $e(n\theta)$, so we apply the same estimate to the reflected set $-\Theta$, whose spacing is unchanged.
[/proofplan]
[step:Encode the additive large sieve as an operator norm estimate]
Define the exponential notation $e: \mathbb{R}/\mathbb{Z} \to \mathbb{C}$ by
\begin{align*}
e(x) := \exp(2\pi i x).
\end{align*}
This is well-defined on $\mathbb{R}/\mathbb{Z}$ because $\exp(2\pi i(x+k))=\exp(2\pi i x)$ for every $k \in \mathbb{Z}$. Let
\begin{align*}
I := \{n \in \mathbb{Z} : M < n \leq M + N\}
\end{align*}
denote the interval of integer indices. Since $N \in \mathbb{N}$, the set $I$ has cardinality $N$. Equip $\mathbb{C}^{I}$ with the Hilbert norm
\begin{align*}
\|a\|_{\ell^2(I)}^2 := \sum_{n \in I}|a_n|^2
\end{align*}
for $a = (a_n)_{n \in I} \in \mathbb{C}^{I}$, and equip $\mathbb{C}^{\Theta}$ with the Hilbert norm
\begin{align*}
\|c\|_{\ell^2(\Theta)}^2 := \sum_{\theta \in \Theta}|c_\theta|^2
\end{align*}
for $c = (c_\theta)_{\theta \in \Theta} \in \mathbb{C}^{\Theta}$.
Define the linear map $T: \mathbb{C}^{I} \to \mathbb{C}^{\Theta}$ as follows: for each $a \in \mathbb{C}^{I}$, the vector $Ta \in \mathbb{C}^{\Theta}$ is defined coordinatewise by
\begin{align*}
(Ta)_\theta := \sum_{n \in I} a_n e(n\theta).
\end{align*}
The [Additive Large Sieve Inequality](/theorems/7181), in the form with sharp interval constant $N-1+\Delta^{-1}$, states that because $\Theta$ is $\Delta$-spaced with $0 < \Delta \leq 1$ and the integer interval $I$ has cardinality $N$,
\begin{align*}
\|Ta\|_{\ell^2(\Theta)}^2 \leq \left(N - 1 + \Delta^{-1}\right)\|a\|_{\ell^2(I)}^2
\end{align*}
for every $a \in \mathbb{C}^{I}$. Define $\mathcal{L}(\mathbb{C}^{I},\mathbb{C}^{\Theta})$ to be the space of complex-linear maps from $\mathbb{C}^{I}$ to $\mathbb{C}^{\Theta}$, equipped with the operator norm induced by $\|\cdot\|_{\ell^2(I)}$ and $\|\cdot\|_{\ell^2(\Theta)}$. Therefore the operator norm of $T$ satisfies
\begin{align*}
\|T\|_{\mathcal{L}(\mathbb{C}^{I},\mathbb{C}^{\Theta})}^2 \leq N - 1 + \Delta^{-1}.
\end{align*}
[guided]
The point of this step is to rephrase the known additive large sieve in Hilbert-space language. We use the exponential notation $e: \mathbb{R}/\mathbb{Z} \to \mathbb{C}$ defined by
\begin{align*}
e(x) := \exp(2\pi i x).
\end{align*}
This definition descends from $\mathbb{R}$ to $\mathbb{R}/\mathbb{Z}$ because adding an integer $k \in \mathbb{Z}$ to $x$ multiplies $\exp(2\pi i x)$ by $\exp(2\pi i k)=1$. We first isolate the finite index set
\begin{align*}
I := \{n \in \mathbb{Z} : M < n \leq M + N\}.
\end{align*}
This set has exactly $N$ elements, so a sequence $(a_n)_{n \in I}$ is an element of the finite-dimensional Hilbert space $\mathbb{C}^{I}$ with norm
\begin{align*}
\|a\|_{\ell^2(I)}^2 := \sum_{n \in I}|a_n|^2.
\end{align*}
Similarly, a family $(c_\theta)_{\theta \in \Theta}$ lies in $\mathbb{C}^{\Theta}$ with norm
\begin{align*}
\|c\|_{\ell^2(\Theta)}^2 := \sum_{\theta \in \Theta}|c_\theta|^2.
\end{align*}
Now define the map $T: \mathbb{C}^{I} \to \mathbb{C}^{\Theta}$ by declaring that, for each $a \in \mathbb{C}^{I}$, the vector $Ta \in \mathbb{C}^{\Theta}$ has coordinates
\begin{align*}
(Ta)_\theta := \sum_{n \in I} a_n e(n\theta)
\end{align*}
for each $\theta \in \Theta$. This is linear because each coordinate $(Ta)_\theta$ is a finite complex linear combination of the coordinates $a_n$.
The Additive Large Sieve Inequality applies to this exact map in the form with constant $N-1+\Delta^{-1}$: its hypotheses are that the frequencies form a $\Delta$-spaced subset of $\mathbb{R}/\mathbb{Z}$, that $0 < \Delta \leq 1$, and that the summation interval has length $N$, all of which are part of the theorem statement after the spacing range is made explicit. Thus, for every $a \in \mathbb{C}^{I}$,
\begin{align*}
\|Ta\|_{\ell^2(\Theta)}^2 = \sum_{\theta \in \Theta}\left|\sum_{n \in I} a_n e(n\theta)\right|^2 \leq \left(N - 1 + \Delta^{-1}\right)\sum_{n \in I}|a_n|^2.
\end{align*}
Equivalently,
\begin{align*}
\|Ta\|_{\ell^2(\Theta)}^2 \leq \left(N - 1 + \Delta^{-1}\right)\|a\|_{\ell^2(I)}^2.
\end{align*}
Taking the supremum over all nonzero $a \in \mathbb{C}^{I}$ gives
\begin{align*}
\|T\|_{\mathcal{L}(\mathbb{C}^{I},\mathbb{C}^{\Theta})}^2 \leq N - 1 + \Delta^{-1}.
\end{align*}
This is the only place where the primal additive large sieve is used.
[/guided]
[/step]
[step:Compute the adjoint of the exponential sum operator]
Use the Hermitian inner products
\begin{align*}
(a,a')_{\ell^2(I)} := \sum_{n \in I} a_n\overline{a'_n}
\end{align*}
on $\mathbb{C}^{I}$ and
\begin{align*}
(c,c')_{\ell^2(\Theta)} := \sum_{\theta \in \Theta} c_\theta\overline{c'_\theta}
\end{align*}
on $\mathbb{C}^{\Theta}$. Let
\begin{align*}
T^*: \mathbb{C}^{\Theta} \to \mathbb{C}^{I}
\end{align*}
be the Hilbert-space adjoint of $T$. For $a \in \mathbb{C}^{I}$ and $b \in \mathbb{C}^{\Theta}$,
\begin{align*}
(Ta,b)_{\ell^2(\Theta)} = \sum_{\theta \in \Theta}\left(\sum_{n \in I}a_n e(n\theta)\right)\overline{b_\theta}.
\end{align*}
Since both sums are finite, we may interchange their order:
\begin{align*}
(Ta,b)_{\ell^2(\Theta)} = \sum_{n \in I} a_n \overline{\left(\sum_{\theta \in \Theta} b_\theta e(-n\theta)\right)}.
\end{align*}
Therefore
\begin{align*}
(T^*b)_n = \sum_{\theta \in \Theta} b_\theta e(-n\theta)
\end{align*}
for every $n \in I$.
[guided]
We now identify the adjoint explicitly. The [inner product](/page/Inner%20Product) on $\mathbb{C}^{I}$ is
\begin{align*}
(a,a')_{\ell^2(I)} := \sum_{n \in I} a_n\overline{a'_n},
\end{align*}
and the inner product on $\mathbb{C}^{\Theta}$ is
\begin{align*}
(c,c')_{\ell^2(\Theta)} := \sum_{\theta \in \Theta} c_\theta\overline{c'_\theta}.
\end{align*}
These are finite-dimensional Hilbert inner products, linear in the first argument. Let
\begin{align*}
T^*: \mathbb{C}^{\Theta} \to \mathbb{C}^{I}
\end{align*}
denote the Hilbert-space adjoint of $T$, so by definition
\begin{align*}
(Ta,b)_{\ell^2(\Theta)} = (a,T^*b)_{\ell^2(I)}
\end{align*}
for every $a \in \mathbb{C}^{I}$ and every $b \in \mathbb{C}^{\Theta}$.
We compute the left-hand side from the definition of $T$:
\begin{align*}
(Ta,b)_{\ell^2(\Theta)} = \sum_{\theta \in \Theta}\left(\sum_{n \in I}a_n e(n\theta)\right)\overline{b_\theta}.
\end{align*}
Both $I$ and $\Theta$ are finite in this finite-dimensional formulation, so finite summation permits us to interchange the order of summation. This gives
\begin{align*}
(Ta,b)_{\ell^2(\Theta)} = \sum_{n \in I} a_n\left(\sum_{\theta \in \Theta} e(n\theta)\overline{b_\theta}\right).
\end{align*}
Since $e(-n\theta)=\overline{e(n\theta)}$, the inner sum is the complex conjugate of $\sum_{\theta \in \Theta} b_\theta e(-n\theta)$. Hence
\begin{align*}
(Ta,b)_{\ell^2(\Theta)} = \sum_{n \in I} a_n \overline{\left(\sum_{\theta \in \Theta} b_\theta e(-n\theta)\right)}.
\end{align*}
Comparing this with
\begin{align*}
(a,T^*b)_{\ell^2(I)} = \sum_{n \in I} a_n\overline{(T^*b)_n}
\end{align*}
for arbitrary $a \in \mathbb{C}^{I}$, we obtain
\begin{align*}
(T^*b)_n = \sum_{\theta \in \Theta} b_\theta e(-n\theta)
\end{align*}
for every $n \in I$.
[/guided]
[/step]
[step:Transfer the operator norm bound to the adjoint]
In finite-dimensional Hilbert spaces, the adjoint has the same operator norm as the original operator:
\begin{align*}
\|T^*\|_{\mathcal{L}(\mathbb{C}^{\Theta},\mathbb{C}^{I})} = \|T\|_{\mathcal{L}(\mathbb{C}^{I},\mathbb{C}^{\Theta})}.
\end{align*}
Indeed,
\begin{align*}
\|T^*b\|_{\ell^2(I)} = \sup_{\|a\|_{\ell^2(I)} = 1}|(a,T^*b)_{\ell^2(I)}| = \sup_{\|a\|_{\ell^2(I)} = 1}|(Ta,b)_{\ell^2(\Theta)}| \leq \|T\|_{\mathcal{L}(\mathbb{C}^{I},\mathbb{C}^{\Theta})}\|b\|_{\ell^2(\Theta)}
\end{align*}
for every $b \in \mathbb{C}^{\Theta}$, so $\|T^*\| \leq \|T\|$. Applying the same argument to $T^*$ gives $\|T\| = \|(T^*)^*\| \leq \|T^*\|$, hence equality. Combining this equality with the bound from the first step gives
\begin{align*}
\|T^*b\|_{\ell^2(I)}^2 \leq \left(N - 1 + \Delta^{-1}\right)\|b\|_{\ell^2(\Theta)}^2
\end{align*}
for every $b \in \mathbb{C}^{\Theta}$.
[guided]
The purpose of this step is to turn the bound for $T$ into the same bound for $T^*$. In finite-dimensional Hilbert spaces, the adjoint has the same operator norm as the original operator. We verify this directly for the present spaces. For $b \in \mathbb{C}^{\Theta}$, the Hilbert-space norm can be recovered by duality:
\begin{align*}
\|T^*b\|_{\ell^2(I)} = \sup_{\|a\|_{\ell^2(I)} = 1}|(a,T^*b)_{\ell^2(I)}|.
\end{align*}
Using the defining property of the adjoint, the scalar product on the right becomes
\begin{align*}
(a,T^*b)_{\ell^2(I)} = (Ta,b)_{\ell^2(\Theta)}.
\end{align*}
The [Cauchy-Schwarz inequality](/theorems/432) in the finite-dimensional Hilbert space $\mathbb{C}^{\Theta}$ gives
\begin{align*}
|(Ta,b)_{\ell^2(\Theta)}| \leq \|Ta\|_{\ell^2(\Theta)}\|b\|_{\ell^2(\Theta)}.
\end{align*}
By the definition of the operator norm of $T$,
\begin{align*}
\|Ta\|_{\ell^2(\Theta)} \leq \|T\|_{\mathcal{L}(\mathbb{C}^{I},\mathbb{C}^{\Theta})}\|a\|_{\ell^2(I)}.
\end{align*}
Taking the supremum over all $a$ with $\|a\|_{\ell^2(I)}=1$ yields
\begin{align*}
\|T^*b\|_{\ell^2(I)} \leq \|T\|_{\mathcal{L}(\mathbb{C}^{I},\mathbb{C}^{\Theta})}\|b\|_{\ell^2(\Theta)}.
\end{align*}
Thus $\|T^*\|_{\mathcal{L}(\mathbb{C}^{\Theta},\mathbb{C}^{I})}\leq \|T\|_{\mathcal{L}(\mathbb{C}^{I},\mathbb{C}^{\Theta})}$. Applying the same argument to the operator $T^*$ and using $(T^*)^*=T$ gives the reverse inequality, so the norms are equal. Combining this equality with the operator norm estimate obtained from the Additive Large Sieve Inequality gives
\begin{align*}
\|T^*b\|_{\ell^2(I)}^2 \leq \left(N - 1 + \Delta^{-1}\right)\|b\|_{\ell^2(\Theta)}^2
\end{align*}
for every $b \in \mathbb{C}^{\Theta}$.
[/guided]
[/step]
[step:Reflect the frequency set to obtain the desired sign]
The preceding step gives
\begin{align*}
\sum_{n \in I}\left|\sum_{\theta \in \Theta} b_\theta e(-n\theta)\right|^2 \leq \left(N - 1 + \Delta^{-1}\right)\sum_{\theta \in \Theta}|b_\theta|^2.
\end{align*}
To obtain the sign appearing in the theorem, define the reflected set
\begin{align*}
-\Theta := \{-\theta : \theta \in \Theta\} \subset \mathbb{R}/\mathbb{Z}.
\end{align*}
The map $\theta \mapsto -\theta$ is an isometry of $\mathbb{R}/\mathbb{Z}$, so $-\Theta$ is also $\Delta$-spaced. Given $b = (b_\theta)_{\theta \in \Theta}$, define $c = (c_\varphi)_{\varphi \in -\Theta} \in \mathbb{C}^{-\Theta}$ by
\begin{align*}
c_{-\theta} := b_\theta
\end{align*}
for each $\theta \in \Theta$. Applying the adjoint estimate to the $\Delta$-spaced set $-\Theta$ and to $c$ gives
\begin{align*}
\sum_{n \in I}\left|\sum_{\varphi \in -\Theta} c_\varphi e(-n\varphi)\right|^2 \leq \left(N - 1 + \Delta^{-1}\right)\sum_{\varphi \in -\Theta}|c_\varphi|^2.
\end{align*}
Substituting $\varphi = -\theta$ and $c_{-\theta}=b_\theta$, the left-hand side becomes
\begin{align*}
\sum_{n \in I}\left|\sum_{\theta \in \Theta} b_\theta e(n\theta)\right|^2,
\end{align*}
and the right-hand side becomes
\begin{align*}
\left(N - 1 + \Delta^{-1}\right)\sum_{\theta \in \Theta}|b_\theta|^2.
\end{align*}
Since $I = \{n \in \mathbb{Z}: M < n \leq M+N\}$, this is exactly
\begin{align*}
\sum_{M < n \leq M + N} \left|\sum_{\theta \in \Theta} b_\theta e(n\theta)\right|^2 \leq \left(N - 1 + \Delta^{-1}\right)\sum_{\theta \in \Theta}|b_\theta|^2.
\end{align*}
This proves the stated dual additive large sieve inequality.
[guided]
The estimate obtained from the adjoint is
\begin{align*}
\sum_{n \in I}\left|\sum_{\theta \in \Theta} b_\theta e(-n\theta)\right|^2 \leq \left(N - 1 + \Delta^{-1}\right)\sum_{\theta \in \Theta}|b_\theta|^2.
\end{align*}
This has the opposite sign from the theorem statement. To correct the sign without changing the spacing, define the reflected frequency set
\begin{align*}
-\Theta := \{-\theta : \theta \in \Theta\} \subset \mathbb{R}/\mathbb{Z}.
\end{align*}
The map $\theta \mapsto -\theta$ preserves distance on $\mathbb{R}/\mathbb{Z}$, so if $\Theta$ is $\Delta$-spaced, then $-\Theta$ is also $\Delta$-spaced. Now define $c = (c_\varphi)_{\varphi \in -\Theta} \in \mathbb{C}^{-\Theta}$ by
\begin{align*}
c_{-\theta} := b_\theta
\end{align*}
for each $\theta \in \Theta$. The map $\theta \mapsto -\theta$ is a bijection from $\Theta$ to $-\Theta$, so this definition assigns exactly one value to each coordinate $c_\varphi$.
Apply the adjoint estimate to the $\Delta$-spaced set $-\Theta$ and to the coefficient vector $c$. We get
\begin{align*}
\sum_{n \in I}\left|\sum_{\varphi \in -\Theta} c_\varphi e(-n\varphi)\right|^2 \leq \left(N - 1 + \Delta^{-1}\right)\sum_{\varphi \in -\Theta}|c_\varphi|^2.
\end{align*}
Substitute $\varphi=-\theta$. Since $c_{-\theta}=b_\theta$ and $e(-n(-\theta))=e(n\theta)$, the left-hand side becomes
\begin{align*}
\sum_{n \in I}\left|\sum_{\theta \in \Theta} b_\theta e(n\theta)\right|^2.
\end{align*}
The same bijection gives
\begin{align*}
\sum_{\varphi \in -\Theta}|c_\varphi|^2 = \sum_{\theta \in \Theta}|b_\theta|^2.
\end{align*}
Therefore
\begin{align*}
\sum_{n \in I}\left|\sum_{\theta \in \Theta} b_\theta e(n\theta)\right|^2 \leq \left(N - 1 + \Delta^{-1}\right)\sum_{\theta \in \Theta}|b_\theta|^2.
\end{align*}
Finally, $I = \{n \in \mathbb{Z}: M < n \leq M+N\}$, so the left-hand summation is exactly over the integers $M<n\leq M+N$. This is the desired dual additive large sieve inequality.
[/guided]
[/step]
