Need to bound a trigonometric sum - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T08:18:21Z http://mathoverflow.net/feeds/question/73277 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/73277/need-to-bound-a-trigonometric-sum Need to bound a trigonometric sum Brendan McKay 2011-08-20T13:13:32Z 2011-08-20T18:34:41Z <p>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.</p> <p>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?</p> <p>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.</p> http://mathoverflow.net/questions/73277/need-to-bound-a-trigonometric-sum/73283#73283 Answer by Noam D. Elkies for Need to bound a trigonometric sum Noam D. Elkies 2011-08-20T15:18:02Z 2011-08-20T18:34:41Z <p>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 &lt; k \leq m} (z_j - z_k) \biggr| \phantom{+} = \prod_{1 \leq j &lt; k &lt; 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 &lt; 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.</p> <p><strong>EDIT</strong> 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.</p> <p>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 &lt; m$ such that $f(z_j) = z^{m+t-1}$ for each $j$.</p>