# Bounding a sum involving a $\Re((z\zeta)^N)$ term

This is a follow up to this question. Any help would be very much appreciated.

Let $k\in\mathbb{N}$ be odd and $N\in\mathbb{N}$. You may assume that $N>k^2/4$ or some other $N>ak^2$.

Let $\zeta:=\exp(2\pi i/k)$ and $\alpha_v:=\zeta^v+\zeta^{-v}+\zeta^{-1}$.

Here there are five questions of varying intricacy. An answer to four is what I am hoping to achieve myself but an answer to an earlier part should go a long way towards helping and obviously an answer to part 5. would be amazing.

I have given a fairly trivial bound below which is good for my needs. If I don't get a better answer by the end of the bounty period I will accept my own (CW) answer and grant charMD the bounty.

1. Simplify, where $v\in\{1,2,\dots,(k-1)/2\}$, $$1-\sin^2\left(\frac{2\pi v}{k}\right)\Re\left((\alpha_v\zeta)^N\right)+|\alpha_v|^{2N}.$$

2. Upper bound, where $v\in\{1,2,\dots,(k-1)/2\}$, $$\sec^2\left(\frac{2\pi v}{k}\right)\left(1-\sin^2\left(\frac{2\pi v}{k}\right)\Re\left((\alpha_v\zeta)^N\right)+|\alpha_v|^{2N}\right)\leq f_2(v,k,N).$$

3. Simplify, where $v\in\{1,2,\dots,(k-1)/2\}$, $$\sec^2\left(\frac{2\pi v}{k}\right)\left(1-\sin^2\left(\frac{2\pi v}{k}\right)\Re\left((\alpha_v\zeta)^N\right)+|\alpha_v|^{2N}\right).$$

4. Upper bound $$\frac{1}{4^{2N-1}}\sum_{v=1}^{\frac{k-1}{2}}\sec^2\left(\frac{2\pi v}{k}\right)\left(1-\sin^2\left(\frac{2\pi v}{k}\right)\Re\left((\alpha_v\zeta)^N\right)+|\alpha_v|^{2N}\right)\leq f_4(k,N).$$

5. Sum $$\frac{1}{4^{2N-1}}\sum_{v=1}^{\frac{k-1}{2}}\sec^2 \left(\frac{2\pi\,v}{k}\right)\left(1-\sin^2\left(\frac{2\pi v}{k}\right)\Re\left((\alpha_v\zeta)^N\right)+|\alpha_v|^{2N}\right).$$

• I haven't made the computations myself, but checking for some values of $k$, it seems to me that your very first formula should rather be $\frac{1}{4^{2N-1}}\sum \limits_{v=1}^{\frac{k-1}{2}}\sec^2\left(\frac{2\pi v}{k}\right)=2 \cdot\frac{k^2-1}{4^{2N}}$ (with a $2$ instead of $\frac{1}{2}$) – charmd Apr 26 '16 at 20:39
• @charMD thanks - I had it written up elsewhere and wasn't careful with the constant. It can be shown using the secant to tangent identity and if you search this site there is a sum of tangent-squared identity. – JP McCarthy Apr 26 '16 at 20:57

The calculations were too awful and I haven't managed to find a simple form yet, but along with your first equality ($\sum \limits_{v=1}^{\frac{k-1}{2}} \sec^2 (\frac{2\pi v}{k} ) = \frac{1}{2} (k^2 - 1)$ ), you have also

$\sum \limits_{v=1}^{\frac{k-1}{2}} \frac{1}{\cos \big( \frac{2 \pi v}{k}\big)} = (-1)^\frac{k-1}{2} 2 \lfloor \frac{k-1}{4} \rfloor$.

And you can prove that $\sum \limits_{v=0}^{k-1} \cos ^j \big( \frac{2\pi v}{k} \big) = \frac{k}{2^j} \sum \limits_{\substack{0 \leqslant p \leqslant j\\ k \mid 2p - j}} \binom{j}{p}$.

Thus $$\sum \limits_{v=1}^{\frac{k-1}{2}} \cos ^j \big( \frac{2\pi v}{k} \big) = \frac{1}{2} \Big( \frac{k}{2^j} \sum \limits_{\substack{0 \leqslant p \leqslant j\\ k \mid 2p - j}} \binom{j}{p} - 1\Big)$$

And you can write your sum as a sum of sums of these types, which you can rewrite with the previous formula (but as I said, for now I haven't been able to do some real simplifications)

• That looks like something I can work with but I can't see how I can write my sum as a sum of those terms... – JP McCarthy May 1 '16 at 9:02
• I will try to obtain a more simplified form and complete my answer – charmd May 1 '16 at 17:29
• I awarded you the bounty because nobody else had a stab at it. My answer below is sharp enough though... there is another term in the calculation that dominates the upper bound below so this works fine --- wasn't that hard to get this crude bound in the end. – JP McCarthy May 3 '16 at 8:19

Consider first \begin{align} 1-\sin^2\left(\frac{2\pi v}{k}\right)\Re\left((\alpha_v\zeta)^N\right)+|\alpha_v|^{2N}&\leq 1+\sin^2\left(\frac{2\pi v}{k}\right)\left|\Re\left((\alpha_v\zeta)^N\right)\right|+|\alpha_v|^{2N} \\&\leq 1+\sin^2\left(\frac{2\pi v}{k}\right)\left|(\alpha_v\zeta)^N\right|+|\alpha_v|^{2N} \\&\leq 1+\sin^2\left(\frac{2\pi v}{k}\right)\left|\alpha_v\right|^N+|\alpha_v|^{2N} \\&\leq 1+\sin^2\left(\frac{2\pi v}{k}\right)3^N+3^{2N} \end{align} In terms of efficiency, I am interested in $k$ large but $N=\mathcal{O}(k^2)$ and for $N\approx \frac{k}{2}\mod k$, $$-\Re\left((\alpha_v\zeta)^N\right)\approx +\Re\left((\alpha_v)^N\right).$$ The largest problem is that $$\alpha_v=2\cos\left(\frac{2\pi v}{k}\right)+\zeta^{-1}$$ has a large real part for $k$ large and $v$ small but as $v\rightarrow \frac{k-1}{2}$ $$\alpha_v\approx -1,$$ rather than $\alpha_v\approx 3$ as is the case for $v$ small. Hopefully this doesn't make the bound unusable (should find out soon).

Therefore

\begin{align} &\frac{1}{4^{2N-1}}\sum_{v=1}^{\frac{k-1}{2}}\sec^2\left(\frac{2\pi v}{k}\right)\left(1-\sin^2\left(\frac{2\pi v}{k}\right)\Re\left((\alpha_v\zeta)^N\right)+|\alpha_v|^{2N}\right)\\ &\leq \frac{1}{4^{2N-1}}\sum_{v=1}^{\frac{k-1}{2}}\sec^2\left(\frac{2\pi v}{k}\right)\left(1+\sin^2\left(\frac{2\pi v}{k}\right)3^N+3^{2N}\right) \\&=\frac{1}{4^{2N-1}}\left((1+3^{2N})\sum_{v=1}^{\frac{k-1}{2}}\sec^2\left(\frac{2\pi v}{k}\right)+3^{N}\sum_{v=1}^{\frac{k-1}{2}}\tan^2\left(\frac{2\pi v}{k}\right)\right). \end{align} Now using $\sec^2A=1+\tan^2A$ and this answer of Joriki this is equal to \begin{align*} \frac{1}{4^{2N-1}}\left((1+3^{2N})\left(\frac{k-1}{2}+\frac{k(k-1)}{2}+3^{N}\frac{k(k-1)}{2}\right)\right)&=2\frac{k-1}{4^{2N}}\left[(k+1)3^{2N}+k\cdot 3^N+k+1\right] \end{align*}

Any sharpening would be most welcome in an answer. An ideal answer would be a good bound of the form:

$$\frac{1}{4^{2N-1}}\sum_{v=1}^{\frac{k-1}{2}}\sec^2\left(\frac{2\pi v}{k}\right)\left(1-\sin^2\left(\frac{2\pi v}{k}\right)\Re\left((\alpha_v\zeta)^N\right)+|\alpha_v|^{2N}\right)\leq f(N,k)e^{-\pi^2(2N-1)/k^2},$$

with the 'smaller' $f(N,k)$ the better. This answer here leads to an $$f(N,k)=6(k^2-1)\left(\frac{3}{4}e^{\pi^2/k^2}\right)^{2N}$$