I am solving a problem that has already a plan for the solution. As a subproblem I have to find the value of $$S = \sum\limits_{t \in E} \sum\limits_{x \in E} (t + x)(t + x^2)...(t+x^{2p})$$
where $E$ is a set of all $p$-th roots of unity and $p$ is a prime number.
I also know the right answer (but cannot get the solution yet): $$S = p (\binom{2p}{p} + 4p - 2)$$
Small clarification: you don't have to read the wall of text below. This is just my attempt to get an answer and the real problem has been already told in the begging.
So, what I have done:
The plan goes like this:
- First fix $t$ and sum $x$
- Split the sum into two sums for $x = 1$ and $x \neq 1$ ($S(t) = S_1(t) + S_2(t)$)
- The last step is to sum $t$.
Lets find out $S_1(t) = \sum\limits_{t \in E} (t + 1)(t + 1^2)...(t+1^{2p})$. Obviously, it is $S_1(t) = \sum\limits_{t \in E} (t + 1)^{2p}$
The first problem is to find out $S_2(t)$. I think, I can prove that: $$S_2(t) = \sum\limits_{w \in E \setminus \{1\} } (t + w)(t + w^2)...(t+w^{2p}) = (p - 1)(t + w_1)(t + w_1^2)...(t+w_1^{2p})$$ where $w_1 = exp(\frac{2\pi i}{p})$
But I am not sure that is actually true. this is can be rewritten as: $$(p - 1)((t + w_1)(t + w_1^2)...(t+w_1^p))^2$$ The next problem is to find the value of $$(t + w_1)(t + w_1^2)...(t+w_1^p)$$ It is easy to find the coefficient of $t^p$ (clearly, it is $1$), $t^{p-1}$ (not so obvious, but it is $0$ for sure) and $t^0$ (easy to show that it is $1$). So, my guess is that the hole polynomial equals to $t^p+1$.
If I was correct (but I still want the proof for all this statements), then: $$S = \sum\limits_{t \in E} [(t+1)^{2p} + (p - 1)(t^p+1)^2]$$ Let's split it again: $$S' = \sum\limits_{t \in E} (p - 1)(t^p+1)^2 = 4 p (p - 1)$$ $$S'' = \sum\limits_{t \in E}(t+1)^{2p} = \sum\limits_{t \in E} \sum\limits_{i=0}^{2p} \binom{2p}{i} t^i = \sum\limits_{i=0}^{2p} \binom{2p}{i} \sum\limits_{t \in E} t^i$$ But I think (but have not proven that yet) that $\sum\limits_{t \in E} t^i = 0$ for every $i \neq p$. And then we can rewrite $S''$: $$S'' = p \binom{2p}{p}$$
And the final result is then: $$S = S' + S'' = 4 p (p - 1) + p \binom{2p}{p} = p(\binom{2p}{p} + 4p - 4)$$ And it is not correct, so I have somewhere a mistake =(
Well, I am sorry for such a long introduction. You can help me a lot if you find a mistake in my thoughts and/or help with missing proofs. Alternative solutions are welcome as well =)
Here's an evaluation of your sum with the usual machinations of changing order of the summands and factors. However, there is a combinatorial twist at the end.
Let $p$ be a prime and $\omega=e^{2\pi i/p}$. Then your sum is $$S=\sum_{k=1}^p\sum_{\ell=1}^p\prod_{m=1}^{2p}(\omega^k+\omega^{\ell m}).$$ Factor out $\omega^k$ from each term in the product. This gives a combined factor of $\omega^{2pk}=1$. So, \begin{eqnarray*} % \nonumber to remove numbering (before each equation) S &=& \sum_{k=1}^p\sum_{\ell=1}^p \omega^{2pk}\prod_{m=1}^{2p}(1+\omega^{\ell m-k}) \\ &=& \sum_{k=1}^p\sum_{\ell=1}^p \prod_{m=1}^{2p}(1+\omega^{\ell m-k}) . \end{eqnarray*} Now expand the product and use the property of exponentials $\omega^a\omega^b=\omega^{a+b}$. As notation for this expansion, let $\wp(n)$ denote the collection of all subsets of $\{1,\ldots,n\}$, and let $\sum M$ denote the sum of the elements of the set $M$.
\begin{eqnarray*} % \nonumber to remove numbering (before each equation) S &=& \sum_{k=1}^p\sum_{\ell=1}^p\sum_{M\subseteq\wp(2p)}\prod_{m\in M}\omega^{\ell m-k} \\ &=& \sum_{k=1}^p\sum_{\ell=1}^p\sum_{M\subseteq\wp(2p)}\omega^{\ell\sum M}\cdot\omega^{-k|M|}. \end{eqnarray*} Then change the order of the summands and factor.
\begin{eqnarray*} % \nonumber to remove numbering (before each equation) S &=& \sum_{M\subseteq\wp(2p)}\sum_{k=1}^p\sum_{\ell=1}^p\omega^{\ell\sum M}\cdot\omega^{-k|M|} \\ &=& \sum_{M\subseteq\wp(2p)}\left(\sum_{k=1}^p\omega^{-k|M|}\right)\cdot\left(\sum_{\ell=1}^p\omega^{\ell\sum M}\right). \end{eqnarray*} The last algebraic step is to evaluate the inner sums, each of which is a finite geometric series. There are two types. If $n$ is an integer with $n=0\bmod p$, then $\sum_{k=1}^p\omega^{kn}$ degenerates to a sum of $p$. However, if $n\ne0\bmod p$, then $\sum_{k=1}^p\omega^{kn}=(1-\omega^{np})/(1-\omega^n)$, which is outright $0$. Putting all this together, we have $$S=p^2\cdot|\{M\subseteq\{1,\ldots,2p\}: \textstyle{\sum} M=0\bmod p \quad\text{and}\quad |M|=0\bmod p\}|.$$ There are two boundary cases: $M=\varnothing$ and $M=\{1,\ldots,2p\}$, and in both of these cases $ \sum M=0\bmod p$. Otherwise, we've reduced the evaluation of this sum to the combinatorial problem of enumerating the subsets of $\{1,\ldots,2p\}$ with $p$ elements which have a sum divisible by $p$. There are $\binom{2p}p$ subsets of $\{1,\ldots,2p\}$ with $p$ elements. A consequence of Wilson's theorem is that $\binom{2p}p=2\bmod p$, and there are two exceptional such subsets here, namely the lower members$\{1,2,3,\ldots,p\}$ and the upper members $\{p+1,p+2,\ldots,2p\}$. In both of these cases $p$ divides the sum of the members of the sets. The remaining $\binom{2p}p-2$ sets have sums that are uniformly distributed among the $p$ remainders $0,1,\dots,p-1\bmod p$. As a result, $$S=p^2\Big(\underbrace{2}_{\text{boundary cases}}+\underbrace{2}_{\text{lower and upper}}+\underbrace{\frac1p(\binom{2p}p-2)}_{\text{sum}=0\bmod p}\Big),$$ which is equivalent to your claim.