La secuencia de interpolación polinómica mod p tiene un grado pequeño

Question

Que $p$ un primer impar y $a_1, a_2,...,a_p$ enteros. Demostrar que las dos condiciones siguientes son equivalentes:

1) existe un polinomio $P(x)$ % grado $\leq \frac{p-1}{2}$tal que $P(i) \equiv a_i \pmod p$ % todo $1 \leq i \leq p$

2) para cualquier natural $d \leq \frac{p-1}{2}$, $$ \sum{i=1}^p (a{i+d} - a_i )^2 \equiv 0 \pmod p$ $ donde los índices se toman $\pmod p$

Answer 1

Vamos a expresar nuestras expresiones en $\mathbb{F}_p$.

Primer aviso de que la declaración no cambia si el obligado en $d$ se omite: usted puede reemplazar a $d$$-d$, y para $d=0$ se cumple con la condición, por lo que puede permitir a todos los $d\in\mathbb{F}_p$.

La principal herramienta en la solución de esta identidad. Si $0\le m<2p-2$ es un entero no negativo, a continuación, $$ \sum_{i\in\mathbb{F}_p} i^m = \begin{cases} -1 & \text{if } m=p-1 \\ 0 & \text{otherwise.} \\ \end{casos} $$ (definimos $0^0=1$.)

Prueba: El caso de $m=0$ es trivial. Para $m=p-1$ podemos aplicar el teorema de Fermat. En el resto de los casos se tomará un raíz primitiva $g$ modulo $p$. Entonces $$ \sum_{\in\mathbb{F}_p} i^m = \sum_{j=1}^{p-1} g^{jm} \equiv \frac{g^{m(p-1)}-1}{g^m-1}=0. $$

Ahora vamos a $P(x)$ ser el único polinomio con $P(i)\equiv a_i\pmod{p}$$D=\deg P\le p-1$. Podemos expandir $(P(x+y)-P(x))^2$ $$ (P(x+y)-P(x))^2 = \sum_{k=0}^{2p-4} a_k(y) x^k $$ con algunos polinomios $a_k(y)$. (Observe que $\deg_x(P(x+y)-P(x))=D-1\le p-2$.) Nos centramos en el coeficiente de $a_{p-1}(y)$.

Si $D\le\frac{p-1}2$$\deg_x (P(x+y)-P(x))^2=2(D-1)<p-1$, lo $a_{p-1}(y)=0$. Por lo tanto, para cada $d$ hemos $$ \sum_{i\in\mathbb{F}_p} (P(i+d)-P(i))^2 = \sum_{i\in\mathbb{F}_p} \sum_{k=0}^{p-2} a_k(d) i^k = \sum_{k=0}^{p-2} a_k(d) \sum_{i\in\mathbb{F}_p}^p i^k = \sum_{k=0}^{p-2} a_k(d) \cdot 0 . $$

Si $D\ge\frac{p-1}2+1=\frac{p+1}2$, entonces decimos que el polinomio $a_{p-1}$ es distinto de cero. En efecto, si el líder plazo en $P$$Ax^D$, entonces el coeficiente de $x^{p-1}y^{2D-p+1}$ en $(P(x+y)-P(x))^2$ $\Big(A\binom{D}{(p-1)/2}\Big)^2\ne0$ . El grado de $a_{p-1}(y)$$2D-p+1<p$.

Por lo tanto, existe un valor de $d$ tal que $a_{p-1}(d)\not\equiv 0\pmod{p}$. Para ese $d$ hemos $$ \sum_{i\in\mathbb{F}_p}^p (P(i+d)-P(i))^2 = \sum_{i\in\mathbb{F}_p}^p \sum_{k=0}^{2p-4} a_k(d) i^k = \sum_{k=0}^{2p-4} a_k(d) \sum_{\in\mathbb{F}_p}^p i^k = -a_{p-1}(d) \ne 0. $$