7
$\begingroup$

Good afternoon. I have a particular summation,

$$\zeta_{n,k}(N)=\frac{k!}{N^{n+1-k}}\sum_{j=0}^n\sum_{i=0}^{N-1}\binom{n}{j}w_N^{(j-k)i}$$ Here, the $w_N$ is the root of unity $w_N=e^\frac{2i\pi}{N}$. Given certain conditions on the $n$ and $k$, it is pretty easy to show that for positive integers $k, m, n, N$,

$$n<k\Rightarrow \zeta_{n,k}(N)=0$$ $$n=k\Rightarrow \zeta_{n,k}(N)=k!$$ $$k+m<2n\Rightarrow \zeta_{n,k}(N)=\frac{k!}{N^j}\binom{k+n}{m}$$

Once you are past this threshold, i've been having trouble nailing down a closed form. For cases where $j\neq k$, the term will be $0$ due to the nature of the sums of powers of complex roots of unity. Therefore, the meaningful terms occur when $j=k$ or when $i=N\cdot r$, with $r\in \mathbb{N}$. Is there a way to simplify this expression given this without involving floor function bounds on the outer sum? is there a closed form for the numbers generated?

$\endgroup$
  • 1
    $\begingroup$ The sum $\sum_{i=0}^{N-1} w_N^{s\cdot i}$ equals $N$ for $s$ divisible by $N$ and 0 otherwise, hence your sum equals $k!N^{k-n}\sum_{j\leq n, j\equiv k \pmod N} \binom{n}{j}$ $\endgroup$ – Fedor Petrov Dec 31 '15 at 18:40
1
+50
$\begingroup$

I will elaborate on Fedor Petrov's comment.

Interchanging the order of summation and using the binomial theorem, we remain with $$\frac{k!}{N^{n+1-k}}\sum_{i=0}^{N-1} \omega_N^{-ki} (\sum_{j=0}^{n} \binom{n}{j} \omega_N^{ji} (1+\omega_N^i)^n)=$$ $$(*)\frac{k!}{N^{n+1-k}}\sum_{i=0}^{N-1} \omega_N^{(N-k)i} (1+\omega_N^i)^n.$$

Let $f(x):=x^{N-k}(1+x)^n=\sum_{l} a_l x^l$. Your sum is $$\frac{k!}{N^{n-k}} \frac{\sum_{i=0}^{N-1} f(\omega_N^i)}{N}$$

Now, using the formula for the geometric sum $\sum_{i=0}^{N-1} (\omega_N^{i})^{\ell}$ (0 when $N \nmid l$, and otherwise $N$), we find that your sum is essentially just the sum of certain coefficients of $f(x)$: $$\frac{k!}{N^{n-k}} \sum_{l \equiv 0 \mod N} a_l = \frac{k!}{N^{n-k}}\sum_{j \equiv k \mod N} \binom{n}{j}.$$ This trick is sometimes called "roots of unity filter".

The best closed form seems to be expression $(*)$ - for fixed $N$ this is a simple, finite sum to evaluate and understand (try $N=2$), and it also allows one to perform asymptotic analysis - the term $i=0$ contributes the majority of the sum ($2^n$ times a simple expression), the other terms contribute an exponential term in $n$ of smaller magnitude.

Thinking of $N,k$ as fixed, and ignoring the outer term, your sum is a linear combination of $N$ geometric sequences: $$\sum_{i=0}^{N-1} \lambda_i c_i^n,$$ where $$c_i=1+\omega_N^i, \lambda_i = \omega_N^{(N-k)i}.$$ Such a sequence necessarily satisfies a homogeneous recurrence relation, whose coefficients belong to a polynomial vanishing on all the $c_i$'s simultaneously.

Since the $c_i$'s are algebraic integers, a recurrence exists with integer coefficients. We can find it: Since $x^n-1$ vanishes on $\omega_n^i=c_i-1$, the polynomial $$(x-1)^n-1=x^n+\sum_{i=1}^{n-1}x^{n-i}\binom{n}{i}(-1)^{i}+((-1)^n-1)$$ vanishes on the $c_i$'s, and hence the sequence $$S(n):=\frac{1}{N}(\sum_{i=0}^{N-1} \omega_N^{(N-k)i} (1+\omega_N^i)^n)=\sum_{j \equiv k \mod N} \binom{n}{j}$$ satisfies the following linear homogeneous recurrence relation with integer coefficients:

$$S(n) = \sum_{j=0}^{N-1}(-1)^{j-1} \binom{N}{j}S(n-j) + (1+(-1)^{n-1})S(n-N).$$

If you want a reference for all of this, I suggest this short, elementary paper by Konvalina and Liu.

$\endgroup$
  • $\begingroup$ Very interesting elaboration. I reached the point of the "root of unity filter" before and was hoping to stay away from a summation over congruence, but i was thinking that was not going to be the case. I also appreciate the link you provided as I have been working with multisections of power series and was happy to see some of that in there. Thanks again. I will award the bounty when overflow lets me grant it. $\endgroup$ – Eleven-Eleven Jan 1 '16 at 5:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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