Esercizio carino facile di algebra

[NightKnight]

Volevo sottoporre all'attenzione degli utenti del forum questo inutile ma curioso risultato di algebra:

Sia $mathbb(K)$ un campo finito; sia $f : mathbb(K) -> mathbb(K)$ una qualsiasi funzione.
Allora esiste $p(X) in mathbb(K)[X]$ polinomio a coefficienti in $mathbb(K)$ tale che $forall a in mathbb(K) \ , \ f(a)=p(a)$.

Cioè ogni funzione $mathbb(K) -> mathbb(K)$ è polinomiale.

[dissonance]

è vero...curioso! Per dimostrarlo, penserei a un discorso di cardinalità: le funzioni $K\toK$ (a proposito: io con Firefox non riesco a visualizzare il \mathbb, quindi lascio la K così com'è) sono $(#K)^(#K)$. I polinomi sono infiniti ma le funzioni polinomiali sono in numero finito. Infatti per il principio di identità dei polinomi le funzioni polinomiali sono tante quanti i polinomi di grado $<=#K$. E quanti sono questi polinomi? Guarda caso sono proprio $(#K)^(#K)$! Quindi ${f:K\toK}={"funzioni polinomiali "K\toK}$. Giusto?

[NightKnight]

Si giusto!
Solo che ti resta da dimostrare questo fatto:

per il principio di identità dei polinomi le funzioni polinomiali sono tante quanti i polinomi di grado $<=#K$.

Non so bene cosa tu intenda per il principio d'identità dei polinomi, ma per dimostrarlo per bene si considera la mappa $Phi : K[X] -> Fun(K,K)=K^K$ che associa ad ogni polinomio la corrispondente funzione polinomiale. Si verifica facilmente che $Phi$ è un omomorfismo di anelli e si vede bene che posto $q(X) = prod_(a in K) (X-a)$ il nucleo di $Phi$ è $Ker Phi = {f(X) in K[X] | forall a in K \ , \ f(a)=0} = {f(X) in K[X] | forall a in K \ , X-a | f(X)} = (q(X))$. Inoltre si vede che $K[X] // Ker Phi$ assume in maniera naturale una struttura di spazio vettoriale sul campo $K$ di dimensione $dim_K K[X] // Ker Phi = deg \ q(X) = #K$ (una base è ad esempio ${X^i + (q(X))}_(i=0,...,deg \ q(X) - 1)$);
per cui $#K[X] // Ker Phi = (#K)^(#K)$; per il teorema di omomorfismo $K[X] // Ker Phi$ è isomorfo al sottoanello di $Fun(K,K)$ costituito dalle funzioni polinomiali; e quindi ${text{funzioni polinomiali} K->K} = Im Phi$ ha cardinalità $(#K)^(#K)$.

Dimmi se intendevi qualcosa di diverso.

[dissonance]

Mamma mia quanta algebra... E chi se la ricorda più ...
La costruzione che hai fatto là sopra mi dice qualcosa, probabilmente l'avrò letta su qualche libro.

Io veramente pensavo a questa strada più elementare, ma non sono entrato nei dettagli. Spero che non sia sbagliata:

Teorema: (Principio di identità dei polinomi) Due polinomi a coefficienti in un campo $K$ (andrebbe bene un dominio con unità), dello stesso grado $d$, sono identici se e solo se come funzioni coincidono in almeno $d+1$ punti.
La dimostrazione è facile: quale polinomio di grado $d$ può avere $d+1$ radici in $K$? Da qui segue tutto.

Come conseguenza, in un campo di $p$ elementi ($p=#K$), ogni polinomio di grado $p+1$ e superiore deve coincidere come funzione ad una funzione di grado più basso (*). E quindi il numero totale di funzioni polinomiali è pari al numero totale di polinomi di grado $p$.

(*) Questo punto intuitivamente mi sembrava ovvio...Adesso che ci penso però tanto ovvio non mi sembra più. Che ne pensi?

[NightKnight]

in un campo di $p$ elementi ($p=#K$), ogni polinomio di grado $p+1$ e superiore deve coincidere come funzione ad una funzione di grado più basso (*). E quindi il numero totale di funzioni polinomiali è pari al numero totale di polinomi di grado $p$.

(*) Questo punto intuitivamente mi sembrava ovvio...Adesso che ci penso però tanto ovvio non mi sembra più. Che ne pensi?

Infatti, non è ovvio; per dire che ogni polinomio coincide come funzione ad un polinomio di grado $< #K$ devi fare la divisione euclidea per il polinomio $q(X) = prod_(a in K) (X-a)$ ,che ha grado $deg \ q(X) = #K$, e considerarne il resto; allora il resto e il polinomio di partenza coincidono come funzioni.
Comunque sono le stesse cose che ho fatto io, scritte in un altro modo.

Un'altra osservazione che c'entra poco: se $K=F_(p^n)$ allora $q(X) = prod_(a in F_(p^n)) X-a \ = X^(p^n) - X$.