Funzioni moltiplicative modulo p

[edriv]

Propongo questo magnifico problema iraniano, dedicato agli amanti dei problemi iraniani (si congettura che questo insieme coincida con quello dei wintercampisti o con l'insieme vuoto):

Sia p un numero primo e $ ~ \mathbb{Z}_p^* $ il gruppo degli interi modulo p diversi da 0.

Diciamo che una funzione $ f: \mathbb{Z}_p^* \rightarrow \mathbb{Z}_p^* $ è moltiplicativa se, per ogni $ ~ a,b \in \mathbb{Z}_p^* $ si ha $ ~ f(ab) = f(a)f(b) $.

a) Quante sono le funzioni moltiplicative $ f: \mathbb{Z}_p^* \rightarrow \mathbb{Z}_p^* $?

b) Quante sono le funzioni moltiplicative biunivoche $ f: \mathbb{Z}_p^* \rightarrow \mathbb{Z}_p^* $?

c) Sia A l'insieme delle funzioni descritte al punto a. Per ogni $ ~ x \in \mathbb{Z}_p^* $, calcolare
$ \displaystyle \sum_{f \in A} f(x) $ (modulo p)

d) Sia B l'insieme delle funzioni descritte al punto b. Per ogni $ ~ x \in \mathbb{Z}_p^* $, calcolare
$ \displaystyle g(x) = \sum_{f \in B} f(x) $ (modulo p)

e) Dimostrare che
$ \displaystyle \sum_{x \in \mathbb{Z}_p^*} g(x) = 0 $ (modulo p)


Il punto d) è quello più interessante... ed iraniano
Infatti richiede un po' più di conoscenze... ma non dico cosa se no dico troppo

[Stoppa2006]

a) Sia g un generatore di $ \mathbb{Z}_p^* $ allora ogni funzione moltiplicativa $ f:\mathbb{Z}_p^*\rightarrow \mathbb{Z}_p^* $ è completamente determinata da $ f(g) $ infatti per ogni $ x\in\mathbb{Z}_p^* $ esiste $ n\in\mathbb{Z} $ tale che $ x=g^n $, allora $ f(x)=f(g^n)=f(g^{n-1}g)=f(g^{n-1})f(g)=...=f^n(g) $. Quindi il numero di funzioni cercate è uguale al numero di possibili assegnazioni a $ f(g) $. Affinchè la funzione sia moltiplicativa si deve avere che $ Ord(f(g))|Ord(g)=|\mathbb{Z}_p^*|=\phi(p)=p-1 $ infatti poichè per ipotesi che g sia un generatore si ha che $ g^{p-1}=1 $ (inoltre $ p-1 $ è il minimo esponente strettamente positivo per cui succede), quindi se $ f(g)=x $ si deve avere che $ x^{p-1}=f^{p-1}(g)=f(g^{p-1})=f(1)=1 $ (funzioni moltiplicative mandano 1 in 1). Indichiamo con $ x_d=\{x\in\mathbb{Z}_p^*|Ord(x)=d\} $ allora per quanto detto sopra il numero di funzioni cercate è:
$ \displaystyle\sum_{d|p-1}|x_d|=\displaystyle\sum_{d|p-1}\phi(d)=p-1 $

[Stoppa2006]

b) Affinchè $ f $ sia bigettiva è sufficiente che sia surgettiva (manda un insieme finito in se stesso). Sia g un generatore di $ \mathbb{Z}_p^* $ allora $ f(\mathbb{Z}_p^*)=\{f^n(g)|n\in\mathbb{Z}\} $ quindi affinchè la funzione sia surgettiva si deve avere che $ f(g) $ generi $ \mathbb{Z}_p^* $. Allora ci sono $ \phi(p-1) $ funzioni bigettive (tante quante i generatori di $ \mathbb{Z}_p^* $).

[edriv]

Bene!

Avrei qualcosa da ridire sul punto a), che è solo un po' troppo contorto. Una volta detto che "il numero di funzioni cercate è uguale al numero di possibili assegnazioni a f(g)", serviva tanto casino per vedere che si può fare in p-1 modi?

[Stoppa2006]

Effettivamente hai ragione sono stato MOLTO contorto , però volevo sottolineare il fatto che non sempre una funzione moltiplicativa può mandare un generatore in un qualunque elemento dell' "insieme moltiplicativo" di arrivo.

c) Cerchiamo di riscrivere quella sommatoria. Sia $ g $ il solito generatore di $ \mathbb{Z}_p^* $ allora esiste $ n\in\{1,...,p-1\} $ tale che $ x=g^n $ per cui:
$ \displaystyle\sum_{f\in A}f(x)=\displaystyle\sum_{f\in A}f(g^n)=\displaystyle\sum_{f\in A}(f(g))^n=\displaystyle\sum_{x\in \mathbb{Z}_p^*}x^n=\displaystyle\sum_{k=1}^{p-1}k^n $
Definiamo Sum$ (n,p)=\displaystyle\sum_{k=1}^{p-1}k^n $(modulo p), e dividiamo vari casi:
i) p=2: banalmente si ha Sum$ (2,n) $=1

[Stoppa2006]

Supporremo sempre $ p\neq 2 $.
ii) $ n|p-1 $: Consideriamo la mappa $ j_n:\mathbb{Z}_p^*\rightarrow\mathbb{Z}_p^* $ che manda $ x $ in $ x^n $. Riscrivo la somma come:
$ \displaystyle\sum_{x\in\mathbb{Z}_p^*}x^n=\displaystyle\sum_{y\in j_n(\mathbb{Z}_p^*)}\displaystyle\sum_{x\in j_n^{-1}(y)}x $
Si può dimostrare che per ogni $ y\in j_n(\mathbb{Z}_p^*) $ la cardinalità di $ j_n^{-1}(y) $ è esattamente $ n $ (io nn ci riesco senza usare la parola "Lagrange" , e non sono sicuro di poterlo usare...). Allora ho che:
$ Sum(n,p)=n\displaystyle\sum_{y\in j_n(\mathbb{Z}_p^*)}y $
Claim: Per ogni $ x\in j_n(\mathbb{Z}_p^*) $ ho che:
$ x\displaystyle\sum_{y\in j_n(\mathbb{Z}_p^*)}y=\displaystyle\sum_{y\in j_n(\mathbb{Z}_p^*)}y $
Se questo è vero ho che:
$ (x-1)\displaystyle\sum_{y\in j_n(\mathbb{Z}_p^*)}y=0\ (mod \ p) $
Quindi se $ j_n(\mathbb{Z}_p^*)=\{1\} $ e questo succede se e solo se $ n=p-1 $ ('ordine di un generatore è esattamente $ p-1 $) allora:
$ Sum(p-1,p)=p-1 $
Altrimenti (cioè se $ n\neq p-1 $) poichè $ p $ è primo:
$ Sum(n,p)=0 $

Dimostriamo il claim:
Consideriamo per ogni $ x\in j_n(\mathbb{Z}_p^*) $ la mappa $ h_x:j_n(\mathbb{Z}_p^*)\rightarrow j_n(\mathbb{Z}_p^*) $ che moltiplica per $ x $. La mappa è chiaramente iniettiva (se $ xy=xz $ allora $ z=y $ poichè tutti gli elementi con cui abbiamo a che fare sono invertibili) e quindi bigettiva.

P.S. Spero di non aver scritto sfondoni data l'ora...
P.P.S. Primo sfondone: Il caso $ p=2 $ poteva rientrare tranquillamente in questo...

[Stoppa2006]

iii) $ n\nmid p-1 $: Consideriamo la solita mappa $ j_n:\mathbb{Z}_p^*\rightarrow\mathbb{Z}_p^* $ e notiamo che questa mappa è una bigezione, inatti è surgettiva poichè manda generatori in generatori. Infatti sia $ g $ un generatore di $ \mathbb{Z}_p^* $ allora anche $ j_n(g)=g^n $ genera $ \mathbb{Z}_p^* $ poichè $ (n,p-1)=1 $. Quindi:
$ \displaystyle\sum_{x\in\mathbb{Z}_p^*}x^n=\displaystyle\sum_{x\in\mathbb{Z}_p^*}j_n(x)=\displaystyle\sum_{x\in\mathbb{Z}_p^*}x=\displaystyle\sum_{k=1}^{p-1}k=\frac{p(p-1)}{2} $
Quindi poichè $ p\neq 2 $(servive scindere il caso $ p=2 $ ):
$ Sum(n,p)=0 $

[Stoppa2006]

Il punto (c) si poteva fare in poche righe, invece che in tre interminabli interventi...

Con la notazione di prima basta osservare che $ A=\{j_n|n=1,...,p-1\} $ allora se $ x\neq 1 $ (quindi $ p\neq 2 $):
$ \displaystyle\sum_{f\in A}f(x)=\displaystyle\sum_{k=1}^{p-1}x^k=\frac{x^p-1}{x-1}-1=0 $
Dove l'ultima uguaglianza è giustificata dal fatto di aver supposto $ x\neq 1 $ e dal teorema di Eulero.

(Tre righe sono meglio che 3 interventi... )

[edriv]

Bene anche questi, qualche commento:

- se $ ~ n \mid p-1 $ non è detto che quella funzione sia bigettiva, ma hai solo sbagliato di scrivere perchè la riga sotto usi appunto il fatto che $ ~ (n,p-1) = 1 $

- l'ultima dimostrazione del punto c) è proprio bella, non l'avevo vista neanche io!

- l'idea del claim del punto ii), cioè di moltiplicare ciascun membro della somma per x permutando gli elementi, si può anche applicare subito senza dividere in vari casi:
$ ~S = 1^k + 2^k + \ldots + (p-1)^k = (1x)^k + (2x)^k + \ldots + ((p-1)x)^k = Sx^k $
Comunque interessante il fatto che $ ~ x^k = a $ ha o 0 o k soluzioni.

[Stoppa2006]

Peccato che la soluzione "svelta" (anche se l'altra non era di 3 righe era pur sempre un numero di righe congruo a zero modulo 3 ) mi sia venuta dopo...
-Hai ragione non viene bigettiva, è quindi incopleto perchè quel ragionamento funziona solo se $ (n,p-1)=1 $.
-Sul Claim hai perfettamente ragione, è che prima avevo pensato al caso (iii) ma quella strada non andava bene per l'altro e ho trovato la scappatoia del Claim...
-Sul numero di soluzioni di quella congruenza, è un fatto molto più generale che vale per ogni "funzione moltiplicativa" e per ogni gruppo le controimmagini hanno tutte la stessa cardinalità (ogni riferimento ai gruppi è puramente casuale o involontario ).
Via provo l'(e), il punto (d) mi da ancora qualche problemino :

(e) Sia $ h $ (g era una notazione infelice...) il solito generatore allora:
$ \displaystyle\sum_{x\in\mathbb{Z}_p^*}g(x)=\displaystyle\sum_{k=1}^{p-1}g(j_k(h))=\displaystyle\sum_{k=1}^{p-1}\displaystyle\sum_{\ (n,p-1)=1}(h^k)^n=\displaystyle\sum_{\ (n,p-1)=1}\displaystyle\sum_{k=1}^{p-1}h^{nk} $$ =\displaystyle\sum_{\ (n,p-1)=1}\left(\frac{(h^n)^p-1}{h^n-1}-1\right)=0 $
Vale la penna notare che $ h\neq 1 $ poichè è un generatore (il caso $ p=2 $ penso non torni dovrebbe venire 1... comunque è poco interessante...).

[edriv]

Sì, infatti la mia prima soluzione del punto e) si basava sulla risposta al d), guardando la funzione g(x).... solo che è più semplice: stiamo sempre parlando di bigezioni, quindi la somma dei valori dell'immagine di una bigezione è appunto 1 + 2 + 3 + ... + (p-1), che chiaramente è un multiplo di p.
Quindi possiamo vedere la risposta al punto e) appunto come una somma di zeri modulo p. (ho riscritto la tua dimostrazione a parole).

[piever]

Uhm, mi sono un po' perso tra i post precedenti (senza cattiveria Stoppa). Pero' mi pare che il punto d) sia rimasto irrisolto, ed essendo io un grande appassionato dei problemi iraniani, non voglio lasciarmi sfuggire l'occasione.
Per evitare di incasinarmi troppo, non dimostro cose che richiedono passaggi lunghi e noiosi che farebbero perdere a me e ad altri il filo, se non vedete perche' sono vere, chiedete...

Allora:

Definiamo la funzione $ h(d) $ sui divisori di $ p-1 $:

$ h(d)=0 $ se $ d $ non e' square free (N.B.: nel mio modo di vedere il mondo, 1 e' square free)

Altrimenti $ h(d)=(-1)^k $ dove $ k $ e' il numero di divisori primi di $ d $.

Possiamo vedere per induzione che questa funzione rappresenta la somma dei valori tra $ 1 $ e $ p-1 $ con ordine moltiplicativo $ d $ modulo $ p $.


Ora definiamo la funzione $ ind(x) $ che a ogni valore intero $ x $ compreso tra $ 1 $ e $ p-1 $ associa un divisore di $ p-1 $ tale che:

$ g^{ind(x)}\equiv x \pmod p $ dove $ g $ e' un generatore.

E' abbastanza facile notare che il numero di generatori possibili tra cui scegliere sono $ \phi (ind(x)) $


L'originale $ g(x) $ chiedeva di trovare la somma dei generatori elevati alla $ ind(x) $

Vediamo che tale cosa equivale alla somma dei valori con odine moltiplicativo $ \frac{p-1}{ind(x)} $ moltiplicati il numero di volte che prendo ciascuno, quindi si ha:

$ g(x)=\phi (ind(x))h(\frac{p-1}{ind(x)}) $

Spero sia chiaro e vero.

Ciau


edit: mi dicono dalla regia che il tutto si puo' scrivere in modo piu' elegante come:

$ g(x)=\phi (ind(x))\mu (ord(x)) $

[Stoppa2006]

Hai ragione per il punto (c) non sono stato molto chiaro e ho fatto confusione... Comunque dopo ho postato una soluzione di 3 righe, che mi sembra abbastanza chiara...

Il punto (c) si poteva fare in poche righe, invece che in tre interminabli interventi...

Con la notazione di prima basta osservare che $ A=\{j_n|n=1,...,p-1\} $ allora se $ x\neq 1 $ (quindi $ p\neq 2 $):
$ \displaystyle\sum_{f\in A}f(x)=\displaystyle\sum_{k=1}^{p-1}x^k=\frac{x^p-1}{x-1}-1=0 $
Dove l'ultima uguaglianza è giustificata dal fatto di aver supposto $ x\neq 1 $ e dal teorema di Eulero.