[proofplan] We extend the summand $e(P(n))$ by zero outside the interval $\{1,\dots,N\}$ and average it over $H$ consecutive shifts. Cauchy-Schwarz bounds the square of the original sum by the support size of this averaged family times the sum of squared local averages. Expanding the square produces correlations indexed by pairs of shifts; reparametrising the pair by the difference $h$ gives exactly the triangular weight $1-|h|/H$. Finally, the zero extension restricts the correlation to $I_h$, and the identity $e(a)\overline{e(b)}=e(a-b)$ gives the displayed phase. [/proofplan] [step:Extend the summand by zero and express $S$ as an average of shifted short sums] Define the function $z:\mathbb Z\to\mathbb C$ by setting $z(n):=e(P(n))$ for $1\le n\le N$ and $z(n):=0$ otherwise. Then $|z(n)|\le 1$ for every $n\in\mathbb Z$, and \begin{align*} S=\sum_{n\in\mathbb Z}z(n). \end{align*} Define the map $A:\mathbb Z\to\mathbb C$ by $A(m):=\sum_{r=1}^{H}z(m+r)$ for each $m\in\mathbb Z$. Since each fixed $n\in\mathbb Z$ occurs exactly once in the sum $z(m+r)$ for each $r\in\{1,\dots,H\}$, namely with $m=n-r$, finite summation gives \begin{align*} \sum_{m\in\mathbb Z}A(m)=\sum_{r=1}^{H}\sum_{m\in\mathbb Z}z(m+r)=H\sum_{n\in\mathbb Z}z(n)=HS. \end{align*} Moreover, $A(m)=0$ unless the interval $\{m+1,\dots,m+H\}$ intersects $\{1,\dots,N\}$. Hence $A(m)=0$ unless $1-H\le m\le N-1$, and there are $N+H-1$ such integers. [/step] [step:Apply Cauchy-Schwarz to the shifted averages] By the finite [Cauchy-Schwarz inequality](/theorems/432) applied to the finite sequence $(A(m))_{1-H\le m\le N-1}$ and the constant sequence equal to $1$, we obtain \begin{align*} |HS|^2=\left|\sum_{m=1-H}^{N-1}A(m)\right|^2\le (N+H-1)\sum_{m=1-H}^{N-1}|A(m)|^2. \end{align*} Since $N+H-1\le N+H$, division by $H^2$ gives \begin{align*} |S|^2\le \frac{N+H}{H^2}\sum_{m\in\mathbb Z}|A(m)|^2. \end{align*} [guided] The purpose of the shifted sums $A(m)$ is to replace one long sum by many overlapping sums of length $H$. The identity from the previous step says \begin{align*} HS=\sum_{m\in\mathbb Z}A(m). \end{align*} Although this is written as a sum over all integers, it is finite: $A(m)$ can be nonzero only if one of $m+1,\dots,m+H$ lies in $\{1,\dots,N\}$. This is equivalent to \begin{align*} m+H\ge 1 \end{align*} and \begin{align*} m+1\le N, \end{align*} so $1-H\le m\le N-1$. Thus at most $N+H-1$ values of $m$ contribute. We now apply the finite Cauchy-Schwarz inequality to the two sequences $(A(m))_{1-H\le m\le N-1}$ and $(1)_{1-H\le m\le N-1}$. It gives \begin{align*} \left|\sum_{m=1-H}^{N-1}A(m)\right|^2 \le \left(\sum_{m=1-H}^{N-1}1^2\right) \left(\sum_{m=1-H}^{N-1}|A(m)|^2\right). \end{align*} The first factor is $N+H-1$, so \begin{align*} |HS|^2\le (N+H-1)\sum_{m=1-H}^{N-1}|A(m)|^2. \end{align*} The theorem allows the slightly larger factor $N+H$, and replacing $N+H-1$ by $N+H$ preserves the inequality. Dividing by $H^2$ gives \begin{align*} |S|^2\le \frac{N+H}{H^2}\sum_{m\in\mathbb Z}|A(m)|^2. \end{align*} This is the point where the boundary cost enters the proof: the translated length-$H$ windows have support on an interval of length at most $N+H$ in the shift parameter $m$. [/guided] [/step] [step:Expand the square and group the correlations by the shift difference] Using the definition of $A(m)$ and finite distributivity, \begin{align*} \sum_{m\in\mathbb Z}|A(m)|^2 = \sum_{m\in\mathbb Z}\sum_{r=1}^{H}\sum_{s=1}^{H}z(m+r)\overline{z(m+s)}. \end{align*} For a fixed integer $h$ with $|h|<H$, the number of pairs $(r,s)\in\{1,\dots,H\}^2$ satisfying $r-s=h$ is $H-|h|$. For each such pair, substituting $n=m+s$ gives \begin{align*} \sum_{m\in\mathbb Z}z(m+r)\overline{z(m+s)} = \sum_{n\in\mathbb Z}z(n+h)\overline{z(n)}. \end{align*} Therefore \begin{align*} \sum_{m\in\mathbb Z}|A(m)|^2 = \sum_{|h|<H}(H-|h|)\sum_{n\in\mathbb Z}z(n+h)\overline{z(n)}. \end{align*} Taking absolute values term by term with the triangle inequality yields \begin{align*} \sum_{m\in\mathbb Z}|A(m)|^2 \le \sum_{|h|<H}(H-|h|)\left|\sum_{n\in\mathbb Z}z(n+h)\overline{z(n)}\right|. \end{align*} [/step] [step:Identify the correlations with the stated differenced exponential sums] By the definition of $z$, the product $z(n+h)\overline{z(n)}$ is nonzero exactly when both $n$ and $n+h$ lie in $\{1,\dots,N\}$, that is, exactly when $n\in I_h$. For $n\in I_h$, the exponential has modulus one and \begin{align*} z(n+h)\overline{z(n)} = e(P(n+h))\overline{e(P(n))} = e(P(n+h)-P(n)). \end{align*} Thus, for every $h\in\mathbb Z$, \begin{align*} \sum_{n\in\mathbb Z}z(n+h)\overline{z(n)} = \sum_{n\in I_h}e(P(n+h)-P(n)). \end{align*} Combining this identity with the previous estimate gives \begin{align*} |S|^2 \le \frac{N+H}{H^2} \sum_{|h|<H}(H-|h|) \left|\sum_{n\in I_h}e(P(n+h)-P(n))\right|. \end{align*} Since \begin{align*} \frac{H-|h|}{H^2}=\frac{1}{H}\left(1-\frac{|h|}{H}\right), \end{align*} this is precisely \begin{align*} |S|^2 \le \frac{N+H}{H}\sum_{|h|<H}\left(1-\frac{|h|}{H}\right)\left|\sum_{n\in I_h}e(P(n+h)-P(n))\right|. \end{align*} This proves the claimed inequality. [/step]