# Need to bound a trigonometric sum

Let $\boldsymbol{\theta}=(\theta_1,\ldots,\theta_m)$ be a vector of real numbers in $[-\pi,\pi]$. For $t\ge 0$, define $$f(t,\boldsymbol{\theta}) = \binom{m+t-1}{t}^{-1} \sum_{j_1+\cdots+j_m=t} \exp(ij_1\theta_1+\cdots+ij_m\theta_m),$$ where the sum is over non-negative integers $j_1,\ldots,j_m$ with sum $t$. Note that the number of terms in the sum is $\binom{m+t-1}{t}$, so $|f(t,\boldsymbol{\theta})|\le 1$ with equality occurring when all the $\theta_j$s are equal.

For a problem in asymptotic combinatorics, we need a bound on $|f(t,\boldsymbol{\theta})|$ that decreases rapidly as the $\theta_j$s move apart and is valid for all $\boldsymbol{\theta}$. Surely this problem has been studied before?

Note that $\binom{m+t-1}{t}f(t,\boldsymbol{\theta})$ is the coefficient of $x^t$ in $$\prod_{j=1}^m (1-xe^{i\theta_j})^{-1},$$ which suggests some sort of contour integral approach.

-

## 2 Answers

Another approach is to write ${m+t-1 \choose t} f(t,\theta)$ as a Schur function of the $z_j := \exp i \theta_j$, and thus as a quotient $\Delta' / \Delta$ of $m\times m$ determinants with unit-norm entries. Then $|\Delta'| \leq m^{m/2}$ by Hadamard, and $\Delta$ is the Vandermonde determinant of the $z_j$ so $$|\Delta| = \biggl| \prod_{1 \leq j < k \leq m} (z_j - z_k) \biggr| \phantom{+} = \prod_{1 \leq j < k < m} 2 \left| \sin (\theta_j^{\phantom{Y}} - \theta_k^{\phantom{Y}})/2 \right|.$$ Hence $$|f(t,\theta)| \leq \frac{m^{m/2}\strut} {{m+t-1 \choose t} \prod_{1 \leq j < k \leq m} 2 \left| \sin (\theta_j^{\phantom{Y}} - \theta_k^{\phantom{Y}})/2 \right|}.$$ This bound has the advantage of satisfying the desideratum of "decreasing rapidly as the $\theta_j$s move apart and [being] valid for all $\theta$", and of being sharp in some cases where the $\theta_j$ are equally spaced. It has the disadvantage of being larger than the trivial upper bound $|f(t,\theta)| \leq 1$ when some $\theta_j$ are very close, and indeed infinite when two or more $\theta_j$ coincide.

EDIT Expanding $\Delta'$ by the $z_j^{t+m-1}$ row yields the formula $${m+t-1 \choose t} f(t,\theta) = \sum_{j=1}^m \frac{z_j^{t+m-1}}{\prod_{k\neq j} (z_j-z_k)}.$$ Hence $$|f(t,\theta)| \leq {m+t-1 \choose t}^{-1} \sum_{j=1}^m \phantom{Y} \left[ 1 \left/ \prod_{k\neq j} \phantom{Y} \left| 2 \sin \frac12(\theta_j^{\phantom{Y}} - \theta_k^{\phantom{Y}}) \right| \right. \right]$$ which has the same overall advantages and disadvantages as before but is better when the $\theta_j$ are neither bunched together nor spaced exactly evenly.

The determinant formula also gives yet another interpretation of ${m+t-1 \choose t} f(t,\theta)$, in terms of polynomial interpolation: it is the $z^{m-1}$ coefficient of the unique polynomial $P$ with $\deg P < m$ such that $f(z_j) = z^{m+t-1}$ for each $j$.

-
Very interesting. I can't use it because it is important that the bound be at most 1, but it suggests that a deeper analysis of the numerator could pay off. Is it easy to give an explicit expression for $\Delta′$? – Brendan McKay Aug 20 '11 at 15:29
Well the bound $|f(t,\theta)| \leq \min(1,B)$ (where $B$ is the bound I gave) does satisfy the new "at most 1" desideratum ;-) and $\Delta'$ is the determinant of the matrix obtained from Vandermonde's $z_j^{n-1}$ (with $j,n=1,\ldots,m$) by changing $z_j^{m-1}$ to $z_j^{m+t-1}$.  Alternatively, it might be useful that ${m+t-1\choose t}f(t,\theta)$ is the value at ${\rm diag}(z_1,\ldots,z_m)$ of the character of ${\rm U}_m({\bf C})$ acting on the $t$-th symmetric power of the defining representation. – Noam D. Elkies Aug 20 '11 at 15:55

We shall prove that $$f(t,{\theta}) \le \frac{m-1}{t+m-1} \min_{1\le j,k \le m} \frac{1}{|\sin((\theta_j-\theta_k)/2)|}.$$ This shows that if the angles are not too close to each other, then the sum does get small.

Suppose without loss of generality that the minimum in our bound occurs for $\theta_1$ and $\theta_2$ (so these are the angles that are furthest apart). Then writing $j_1+j_2 =\ell$ we have $$|f(t,{ \theta})| \le \binom{m+t-1}{t}^{-1} \sum_{\ell=0}^{t} \sum_{j_3+\ldots+j_m=t-\ell} \Big| \sum_{j_1+j_2 =\ell} \exp(ij_1 \theta_1 + ij_2 \theta_2)\Big|.$$ Now the inner sum over $j_1$ (and $j_2=\ell -j_1$) is simply a geometric progression, and so \begin{align*} \Big| \sum_{j_1+j_2=\ell} \exp(ij_1 + i j_2 \theta_2) \Big| &= \Big| \sum_{j=0}^{\ell} \exp(ij (\theta_1-\theta_2))\Big| = \Big|\frac{\exp(i(\ell+1)(\theta_1-\theta_2))-1}{\exp(i(\theta_1-\theta_2))-1}\Big| \\ &\le \frac{2}{|\exp(i(\theta_1-\theta_2))-1|} = \frac{1}{|\sin((\theta_1-\theta_2)/2)|}. \end{align*} Therefore $$|f(t,{\theta})| \le \frac{1}{|\sin((\theta_1-\theta_2)/2)|}\binom{m+t-1}{t}^{-1} \sum_{\ell+j_3+\ldots+j_m=t} 1,$$ which proves our claimed bound.

As the original question suggests, one would be able to prove better bounds using contour integrals. The key would be to integrate on the circle centered at the origin and with radius $r=t/(m+t)$. One should be able to get good bounds in terms of $$\sum_{j,k} \sin^2 \Big(\frac{\theta_j-\theta_k}{2}\Big),$$ but I have not worked this out carefully.

-
Thanks! It will take a while for me to get to this but I'll come back with comments later. – Brendan McKay Aug 26 '13 at 0:38