Cada Función en un Campo Finito es una Función Polinómica

Question

A partir de un banco de maestro de exámenes voy a través de:

Deje $F$ ser un campo finito. Demostrar que cualquier función de $F$ $F$es una función polinómica.

Sé que finito campos son campos de $p$ elementos para $p$ prime [EDIT: en realidad Es $p^n$ $p$ prime; véase el comentario de abajo]. Desde que he a $p$ opciones para la $p$ elementos del mapa, entonces he a $p^p$ funciones distintas. Creo que cada función puede ser escrita en la forma $f(x) = a_{p-1}x^{p-1} + \dots + a_0x^0$. Para, a continuación, dados los valores de $f(0), f(1), \ldots f(p-1)$, puedo resolver para el coefficents por el sistema de ecuaciones lineales

$$ a_0 + \sum_{i=1}^{p-1} n^i a_i = f(n).$$

Entonces, esto me da un $p-1 \times p-1$ matriz cuadrada sobre el campo $\mathbb{F}_p$:

$$\left( \begin{array}{ccccc} 1& 0 & 0 & \ldots & 0 \\ 1& 1 & 1 & \dots & 1 \\ 1& 2 & 4 & \dots & 2^{p-1} \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & p-1 & (p-1)^2 & \dots & (p-1)^{p-1} \end{array} \right) \left( \begin{array}{c} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{p-1} \end{array}\right) = \left( \begin{array}{c} f(0) \\ f(1) \\ f(2) \\ \vdots \\ f(p-1) \end{array} \right)$$

Si puedo mostrar esta matriz es invertible, entonces siempre se puede encontrar el $a_i$. Pero estoy un poco confundido sobre cómo mostrar este (parcialmente porque no creo que jamás he hecho álgebra lineal en un espacio vectorial sobre un campo finito). No parece fácil demostrar independencia lineal, o determinante distinto de cero, o de una fila completa de rango.

---

Alternativamente, (se me acaba de ocurrir esto), puedo demostrar que esto es cierto, argumentando que el mapa entre los dos grupos (el conjunto de polinomios de grado $p-1$; y el conjunto de funciones de $F \to F$) es inyectiva, y que debe ser un bijection debido a que los conjuntos tienen la misma cardinalidad $p^p$?

Answer 1

Podría ser interesante para la búsqueda de Interpolación de Lagrange de la Fórmula. Dada una función de $f$ desde el campo finito a sí mismo, se le dará una explícita polinomio $P$ de manera tal que la asociada a la función polinómica es igual a $f$.

Answer 2

Sí, su segundo método funciona y de hecho se generaliza perfectamente a las funciones de $n$ variables.

Un método similar para demostrar que toda función en $f: \mathbb{F}_q^n \rightarrow \mathbb{F}_q$ está dada por un polinomio en el cual el grado en que cada variable es en la mayoría de las $q-1$ es dar una explícita fórmula polinómica para el "delta de Dirac de la función" $\mathbb{1}_0(x)$ que es igual a $1$ si $x = (0,\ldots,0)$ $0$ lo contrario. De hecho, hemos

$\mathbb{1}_0(x_1,\ldots,x_n) = \prod_{i=1}^n (1-x_i^{q-1})$

como se trata de un agradable y sencillo ejercicio para comprobar.

De nuevo una cardinalidad argumento muestra que cualquier función $f$ tiene una única representación de un polinomio reducido, es decir, por un polinomio cuyo grado en que cada variable es en la mayoría de las $q-1$. Estas observaciones conducen rápidamente a una prueba de la célebre Chevalley-Advertencia Teorema: ver estas notas para un tratamiento de todos estos temas.

Answer 3

Sugerencia: matriz de Vandermonde.

Answer 4

En primer lugar, un campo finito no necesariamente tiene $p$ elementos para $p$ prime. Para cada prime $p$ natural y número de $m>0$ hay un campo finito con $p^m$ elementos.

Segundo, su enfoque es el sonido - la única pieza que le falta es que su matriz es una matriz de Vandermonde que, por encima de cualquier campo, tiene una expresión sencilla para su determinante.

Answer 5

Es muy sencillo argumento basado sólo en la dimensión y la raíz de conteo. Quiere mostrar que el mapa de$~g$ a partir de los polinomios en la $\def\Fq{{\Bbb F_q}}\Fq[X]$ a sus funciones polinómicas en $\Fq^\Fq=\{\,f:\Fq\to\Fq\mid\,\}$ es surjective. Es fácil ver el mapa es $\Fq$-lineal y que $\dim(\Fq^\Fq)=q$. En realidad, es más fácil demostrar la declaración más fuerte que la restricción$~\tilde g$$~g$ a el subespacio $V=\{\,P\in\Fq[X]\mid\deg(P)<q\,\}$ es bijective (así, en particular,$~\tilde g$ es surjective, y , a fortiori, así es $g$).

Ahora $\dim(V)=q$ $~\tilde g$ es lineal en el mapa entre dos espacios vectoriales de la misma dimensión; tales mapas son bijective si y sólo si, se inyectiva, es decir, tienen $\{0\}$ como núcleo. Ahora $\ker(\tilde g)$ se compone de los $P\in V$ cuya función polinómica es la función cero. La parte $P\in V$ significa que $\deg(P)<q$, y el polinomio de la función es cero significa que todos los $q$ elementos de$~\Fq$ son raíces de$~P$. Es bien sabido que un polinomio distinto de cero sobre un campo no puede tener más raíces de su grado. Esto demuestra que $\ker(\tilde g)=\{0\}$, lo $\tilde g$ es bijective, como se desee.