Simplifying Root of Unity Double Summation

Question

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?

Answer 1

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.