Encontrar una suma $S = \sum\limits_{t \in E} \sum\limits_{x \in E} (t + x)(t + x^2)...(t+x^{2p})$

Question

Yo soy la solución de un problema que tiene ya un plan para la solución. Como subproblem tengo que encontrar el valor de $$S = \sum\limits_{t \in E} \sum\limits_{x \in E} (t + x)(t + x^2)...(t+x^{2p})$$

donde $E$ es un conjunto de todos los $p$-th raíces de la unidad y de la $p$ es un número primo.

También sé que la respuesta correcta (pero no puede obtener la solución): $$S = p (\binom{2p}{p} + 4p - 2)$$

Pequeña aclaración: usted no tiene que leer la pared de texto de abajo. Este es mi intento de obtener una respuesta y que el verdadero problema ha sido ya dicho en la mendicidad.

Así que lo que he hecho:

El plan va como esto:

1. La primera revisión $t$ y suma $x$
2. Dividir la suma de dos cantidades para $x = 1$ y $x \neq 1$ ($S(t) = S_1(t) + S_2(t)$)
3. El último paso es la suma de $t$.

Permite averiguar $S_1(t) = \sum\limits_{t \in E} (t + 1)(t + 1^2)...(t+1^{2p})$. Obviamente, es $S_1(t) = \sum\limits_{t \in E} (t + 1)^{2p}$

El primer problema es averiguar $S_2(t)$. Creo, puedo demostrar que: $$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})$$ donde $w_1 = exp(\frac{2\pi i}{p})$

Pero no estoy seguro de que es realmente cierto. esto se puede reescribir como: $$(p - 1)((t + w_1)(t + w_1^2)...(t+w_1^p))^2$$ El siguiente problema es encontrar el valor de $$(t + w_1)(t + w_1^2)...(t+w_1^p)$$ Es fácil encontrar el coeficiente de $t^p$ (claramente, es $1$), $t^{p-1}$ (no es tan obvio, pero es $0$ seguro) y $t^0$ (fácil demostrar que se es $1$). Por lo tanto, mi conjetura es que el agujero polinomio es igual a $t^p+1$.

Si estaba en lo correcto (pero todavía quiero la prueba de todas estas declaraciones), entonces: $$S = \sum\limits_{t \in E} [(t+1)^{2p} + (p - 1)(t^p+1)^2]$$ Vamos a dividir de nuevo: $$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$$ Pero creo (pero no han demostrado que aún) que $\sum\limits_{t \in E} t^i = 0$ por cada $i \neq p$. Y entonces podemos reescribir $S''$: $$S'' = p \binom{2p}{p}$$

Y el resultado final es entonces: $$S = S' + S'' = 4 p (p - 1) + p \binom{2p}{p} = p(\binom{2p}{p} + 4p - 4)$$ Y no es la correcta, así que tengo en algún lugar un error =(

Bueno, lo siento, para una larga introducción. Usted me puede ayudar mucho si usted encuentra un error en mis pensamientos y/o ayudar con falta de pruebas. Las soluciones alternativas son bienvenidas =)

Answer 1

Aquí está una evaluación de su suma con el habitual maquinaciones de cambiar el orden de los sumandos y factores. Sin embargo, hay una combinatoria giro al final.

Deje $p$ ser una de las primeras y $\omega=e^{2\pi i/p}$. Entonces su suma es $$S=\sum_{k=1}^p\sum_{\ell=1}^p\prod_{m=1}^{2p}(\omega^k+\omega^{\ell m}).$$ Factor $\omega^k$ de cada término en el producto. Esto le da un combinado factor de $\omega^{2pk}=1$. Así, \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*} Ahora expandir el producto y el uso de la propiedad de exponenciales $\omega^a\omega^b=\omega^{a+b}$. Como notación para esta expansión, vamos a $\wp(n)$ denotar la colección de todos los subconjuntos de a $\{1,\ldots,n\}$, y deje $\sum M$ denotar la suma de los elementos de las $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*} A continuación, cambiar el orden de los sumandos y el 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*} La última algebraicas paso es evaluar el interior de sumas de dinero, de cada uno de los cuales es una serie geométrica finita. Hay dos tipos. Si $n$ es un número entero con $n=0\bmod p$, $\sum_{k=1}^p\omega^{kn}$ degenera a una suma de $p$. Sin embargo, si $n\ne0\bmod p$,$\sum_{k=1}^p\omega^{kn}=(1-\omega^{np})/(1-\omega^n)$, lo cual es francamente $0$. Poniendo todo esto junto, tenemos $$S=p^2\cdot|\{M\subseteq\{1,\ldots,2p\}: \textstyle{\sum} M=0\bmod p \quad\text{and}\quad |M|=0\bmod p\}|.$$ Hay dos casos límite: $M=\varnothing$$M=\{1,\ldots,2p\}$, y en ambos de estos casos $ \sum M=0\bmod p$. De lo contrario, hemos reducido la evaluación de esta suma a la combinatoria del problema de la enumeración de los subconjuntos de a $\{1,\ldots,2p\}$ $p$ elementos que tienen una suma divisible por $p$. Hay $\binom{2p}p$ subconjuntos de a $\{1,\ldots,2p\}$ $p$ elementos. Una consecuencia del teorema de Wilson es que $\binom{2p}p=2\bmod p$, y hay dos excepcionales tales subconjuntos de aquí, es decir, las probabilidades de $\{1,3,5,\ldots,2p-1\}$ y la iguala $\{2,4,6,\ldots,2p\}$. En ambos de estos casos $p$ divide la suma de los miembros de los conjuntos. El resto de los $\binom{2p}p-2$ conjuntos de cantidades que son distribuidos de manera uniforme entre las $p$ resto $0,1,\dots,p-1\bmod p$. Como resultado, $$S=p^2\Big(\underbrace{2}_{\text{boundary cases}}+\underbrace{2}_{\text{evens and odds}}+\underbrace{\frac1p(\binom{2p}p-2)}_{\text{sum}=0\bmod p}\Big),$$ que es equivalente a su reclamo.

Answer 2

Inspirado por @RusMay's respuesta, he encontrado un error en mis cálculos propios. Me olvidé de trivial en la esquina de los casos que deben ser tratados con cuidado. Fue aquí:

Pero creo (pero no han demostrado que aún) que $\sum\limits_{t \in E} t^i = 0$ por cada $i \neq p$.

En realidad, es cierto para todos los $i$ que no es divisible por $p$. Así que, no he tenido en cuenta dos casos: $i = 0$$i = 2p$. Y ahora tenemos:

$$S'' = p \binom{2p}{p} + p \binom{2p}{0} + p \binom{2p}{2p} = p \binom{2p}{p} + 2p $$

Y la respuesta es:

$$S = S' + S'' = 4 p (p - 1) + p \binom{2p}{p} + 2p = p(\binom{2p}{p} + 4p - 2)$$

Sí, la respuesta correcta!