Need to bound a trigonometric sum

2011-08-20T13:13:32Z

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.

Answer by Noam D. Elkies for Need to bound a trigonometric sum

2011-08-20T15:18:02Z

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$.

Need to bound a trigonometric sum - MathOverflow

Need to bound a trigonometric sum

Answer by Noam D. Elkies for Need to bound a trigonometric sum