Funzione identità su \( \mathbb{N} \).

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

1) Trovare tutte le funzioni suriettive \( f: \mathbb{N} \to \mathbb{N} \) che soddisfano le seguenti due proprietà contemporaneamente.
i) Per tutti i numeri primi \( p \), e dati \(n,m \in \mathbb{N} \) abbiamo che \( n \equiv m \mod p \) se e solo se \( f(n) \equiv f(m) \mod p \).
ii) Per tutti i numeri primi \(p \), abbiamo che \( p \mid n \) se e solo se \( p \mid f(n) \).
2) (Difficile) Dimostra che l'identità è l'unica funzione suriettiva \(f: \mathbb{N} \to \mathbb{N} \) tale che per ogni \(n,m \in \mathbb{N} \) e per ogni primo \(p \) risulta che \(f(m+n) \) è divisibile per \(p \) se e solo se \(f(m) + f(n) \) è divisibile per \(p \)
Hint: usa il punto 1)

[Overflow94]

A partire da una generica funzione che rispetta i punti i e ii si può costruire un automorfismo del gruppo $ (ZZ//pZZ,+) $ e ogni automorfismo del gruppo può essere "esteso" dalle classi a una biezione fra i rappresentanti di classe in modo da creare una funzione che rispetta i e ii.

$ |Aut(ZZ//pZZ)|=p-1 $ , è il numero di suddette funzioni che possono essere costruite come suggerito sopra.

Poiché una siffatta funzione deve "essere riconducibile" a un automorfismo di $ ZZ//pZZ $, pensandola definita su un generatore, essa è completamente specificata una volta che è stata definita su $ f(1) in {1, 2, .., p-1}$. Intuitivamente dirrei che l'unica funzione che è estendibile per ogni $ p $ contemporaneamente come automorfismo è l'identità $ f(1)=1 $.

Il modo in cui la funzione $ f(1) = a $ (con $ 1 <= a <= p - 1 $ ) si estende è il seguente:

- $f(0) = 0 $
- si estende agli elementi in $ {1, 2, .., p-1} $ come farebbe normalmente l'automorfismo associamo ovvero $
\ \ \ \ f(2) = 2a mod p $, $ f(3) = 3 a mod p$, ..., $ f(p-1) = (p-1)a mod p $.
- sul generico elemento $ b = qp + r $ con $ 0 <= r <= p - 1 $ vale $ f(b)=f(r) +q p $ .

Spero di aver reso l'idea, formalizzare il tutto è un bel casino.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Quello che hai detto credo sia giusto, ma non mi è chiaro il motivo per cui l'identità debba essere l'unica funzione che è estendibile per ogni \( p \) come automorfismo, onestamente.

E non mi è nemmeno chiaro il motivo per cui vi sia una biiezione tra \( \operatorname{Aut}(\mathbb{Z}/ p \mathbb{Z} ) \) e le funzione come il punto 1)

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Sicuramente, per ogni \(p \) primo, \( \operatorname{Aut}(\mathbb{Z}/p\mathbb{Z}) \) non è in biiezione con le funzioni come il punto 1, se intendiamo \( (\mathbb{Z}/p\mathbb{Z},+) \) come gruppo. Mentre credo sia vero che per ogni \( p \) primo, \( \operatorname{Aut}(\mathbb{Z}/p\mathbb{Z}) \) è in biiezione con le funzione che soddisfano il punto 1, se intendiamo \( (\mathbb{Z}/p\mathbb{Z},+,\cdot) \) come annello.
Bisognerebbe però dimostrarlo, e questo risolverebbe unicamente il punto 1).

[Overflow94]

Avevo letto male, non capendo che quelle proprietà devono valere contemporaneamente per tutti i primi
E anche nel caso $ p $ fissato le funzioni che ho descritto sopra non sono tutte quelle possibili.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"Overflow94":Avevo letto male, non capendo che quelle proprietà devono valere contemporaneamente per tutti i primi
E anche nel caso $ p $ fissato le funzioni che ho descritto sopra non sono tutte quelle possibili.

A dir la verità ne prendi di più.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Siccome nessuno ha più provato a risolvere il quesito, posto le soluzioni che ho trovato
1)

Dimostriamo che l'unica funzione che soddisfa le condizioni i) e ii) contemporaneamente è l'identità.
Sia \( f \) una funzione che soddisfa le condizioni del problema 1) dalla condizione ii) deduciamo che siccome per ogni \( p \) primo abbiamo che \( p \not\mid 1 \) segue che \( p \not\mid f(1) \) per ogni \( p \) primo e dunque \(f(1) =1 \).
Sia \( N > 1 \) supponiamo che per ogni \( n < N \) abbiamo che \(f(n)=n \). Siccome \(N>1\) abbiamo che esiste \( p \) primo tale che \( p \mid N \) e dunque \( p \mid f(N) \).
Supponiamo per assurdo che \( f(N) > N \), abbiamo allora che esiste un numero primo \(q\) tale che \( q \mid f(N) - N +1 \) poiché \( f(N)-N+1 >1\) pertanto segue che \( f(N) \equiv N-1 \mod q \).
Per ipotesi d'induzione abbiamo che \( N-1=f(N-1) \equiv f(N) \mod q \). Per la condizione i) abbiamo dunque che \(N-1 \equiv N \mod q \) che è assurdo!
Supponiamo dunque per assurdo che \( f(N) < N \), per ipotesi d'induzione abbiamo che \( f(f(N)-1) = f(N)-1\). Inoltre analogamente a prima abbiamo che esiste un numero primo \( q \) tale che \(q \mid N-f(N)+1 \) e segue che \( N \equiv f(N)-1 \mod q \). Grazie alla condizione i) segue che \( f(N)\equiv f(f(N)-1) = f(N)- 1 \mod q \) che è assurdo.
Pertanto \( f(N) = N \) è l'unica scelta possibile.
Chiaramente l'identità soddisfa le condizioni i) e ii)
\(\square \)

2)

La dimostrazione del punto 2) passa attraverso tre piccoli lemmi.
Sia \( p \) un numero primo arbitrario, ed \(f \) come nel problema 2), poniamo \[ m_p = \min \{ n \in \mathbb{N} : p \mid f(n) \} \]
\( m_p \) è ben definito poiché \(f \) è suriettiva. D'ora in poi siccome la scelta di \(p \) è arbitraria per alleggerire la notazione scriverò \(m \) per indicare \(m_p \).

Lemmi: Sia \( f \) come nel problema 2), \(p \) un primo arbitrario ed \(m \) definito qui sopra allora segue che:
a) \(p \mid f(n) \) se e solo se \( m \mid n \)
b) Dati \(x,y \in \mathbb{N} \) abbiamo che \( x \equiv y \mod m \) se e solo se \( f(x) \equiv f(y) \mod p \)
c) \( p = m \).

Dimostriamo b) grazie ad a) e dimostriamo c) grazie a b) infine dimostriamo 2) grazie ad c) e dunque ad 1).

Dimostrazione di a)
\( \Leftarrow \):
Se \( k = 1 \) abbiamo per definizione di \(m \) che \( p \mid f(m) \). Supponiamo vero che per \( k=n \) abbiamo che \( p \mid f(n m) \), abbiamo che \( p \mid f(nm) + f(m) \) e grazie alla proprietà della \(f \) abbiamo che \( p \mid f(nm+n)=f(m(n+1)) \)

\( \Rightarrow \):
Supponiamo per assurdo che esiste \( n \in \mathbb{N} \) tale che \( m \not\mid n \) e \( p \mid f(n) \)
Poniamo \( x = \min \{ n \in \mathbb{N} : m \not\mid n, p \mid f(n) \} \). Per definizione di \(m \) abbiamo chiaramente \( x > m \) e dunque \(x > x-m >0 \) e non è divisibile per \( m\) altrimenti \( x \) è divisbile per \(m\).
Per definizione di \(x \) abbiamo che \( p \not\mid f(x-m) \) ma al contempo abbiamo che \( p \mid f(m) \) e \( p \mid f(x)=f(m+x-m) \) e dunque per la proprietà di \( f \) abbiamo che \( p \mid f(x-m) \) contraddizione.

Dimostrazione di b):
\( \Rightarrow \):
Siano \(x,y \in \mathbb{N} \) tale che \( x \equiv y \mod m \).
Abbiamo grazie ad a) che \( p \mid f(2xm)=f(x+2xm-x) \), inoltre \( m \mid y + 2xm -x \) pertanto sempre grazie ad a) risulta che \( p \mid f(y+2xm-x) \)
Dunque grazie alla proprietà di \(f \) otteniamo che \( p \mid f(x) + f(2xm-x) \) e \( p \mid f(y) + f(2xm-y) \) pertanto segue che \( f(x) \equiv -f(2xm-x) \mod p \) e \( f(y) \equiv -f(2xm-x) \mod p \) e concludiamo che \( f(x) \equiv f(y) \mod p \).

\( \Leftarrow \):
Siano \( x,y \in \mathbb{N} \) tale che \( f(x) \equiv f(y) \mod p \).
Analogamente a prima otteniamo che \( p \mid f(x) + f(2xm-x) \). Deduciamo dunque grazie alla proprietà della funzione \(f \) che \(p \mid f(x) + f(2xm-x) + f(y)-f(x) = f(y) + f(2xm-x) \)
E dunque ancora otteniamo che \( p \mid f(y+ 2xm-x) \)
Grazie ad a) abbiamo che \( 0 \equiv y+ 2xm-x \equiv y-x \mod m \)

Dimostrazione di c)
Abbiamo che i numeri \( 1,2,3,\ldots,m \) appartengono due a due a classi di resto modulo \( m \) distinti. Grazie al lemma b) deduciamo che \( f(1), f(2),f(3),\ldots,f(m) \) appartengono due a due a classi di resto modulo \(p \) distinti, pertanto vi sono almeno \(m \) resti distinti e dunque \( p \geq m \).
Per suriettività di \(f \) abbiamo che esistono \(n_1,\ldots,n_p \) interi positivi tale che \( f(n_k)=k \) per ogni \( k =1,\ldots ,p \). Grazie al lemma b) abbiamo che gli interi \( n_k \) appartengono due a due a classi di resto modulo \(m \) distinti e pertanto siccome gli \(f(n_k) \) appartengono due a due a classi di resto modulo \(p \) distinti vi sono almeno \( p \) resti distinti e dunque \( m \geq p \).
Segue che \( m = p\).

Dimostrazione di 2)
Per la scelta arbitraria di \(p \) primo concludiamo dunque che una funzione \(f \) come nel problema 2) soddisfa contemporaneamente le condizioni i) e ii) del problema 1) per ogni primo \(p \) e dunque grazie ad 1) abbiamo che l'identità è l'unica funzione che possiede la proprietà del punto 2).
\(\square \)