Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

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

share|improve this answer
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
add comment

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.

share|improve this answer
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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.