La funzione di Möbius è una funzione molto utile in matematica. È definita nella maniera seguente:
$$\mu(n)=\begin{cases} 1 & \mathrm{se}\,n\,\mathrm{e’\,senza\,quadrati\,e\,ha\,un\,numero}\,pari\,\mathrm{di\,fattori\,primi}\\
-1 & \mathrm{se}\,n\,\mathrm{e’\,senza\,quadrati\,e\,ha\,un\,numero}\,dispari\,\mathrm{di\,fattori\,primi}\\
0 & \mathrm{se}\,n\,\mathrm{non\,e’\,senza\,quadrati}
\end{cases}$$
Un numero intero $n$ è senza quadrati se non è divisibile da nessun quadrato perfetto ad eccezione di $1$. Un numero senza quadrati ha una fattorizzazione in fattori primi in cui ogni fattore appare esattamente una volta, cioè con moltiplicità $1$. Ad esempio
- $\mu(1)=1$ perché $1$ è divisibile solo da se stesso, e quindi è senza quadrati. Inoltre $1$ non appare mai nella scomposizione a fattori, e quindi ha un numero pari di fattori. In altri termini $1$ non è un numero primo, quindi abbiamo zero fattori primi.
- $\mu(2)=-1$ perché $2$ è divisibile solo da $1$ e $2$, nessuno dei quali è un quadrato e quindi $2$ è senza quadrati. Inoltre la sua scomposizione in fattori primi è $2=2^1$ e quindi contiene un solo fattore primo. Per lo stesso ragionamento $\mu(p)=-1$ per ogni $p$ primo.
- $\mu(4)=0$ perché $4$ è divisibile per $4$, che è un quadrato perfetto; perciò $4$ non è senza quadrati.
- $\mu(6)=1$ perché $6$ è senza quadrati e $6=2\cdot 3$, per cui ha due fattori primi.
- $\mu(8)=0$ perché $8$ è divisibile per $4$, che è un quadrato perfetto.
- $\mu(12)=0$ perché $12$ è divisibile per $4$, che è un quadrato perfetto.
- $\mu(30)=-1$ perché $30=2\cdot 3 \cdot 5$, per cui è senza quadrati e ha tre distinti fattori primi.
Una proprietà molto utile della funzione di Möbius è che la somma della funzione di tutti i divisori di un numero è nulla a meno che il numero non sia $1$:
$$\sum_{d | n} \mu(d) = \begin{cases} 1 & n=1\\ 0 & \mathrm{altrimenti} \end{cases}$$
dove $d | n$ significa che $d$ divide $n$, e la somma è quindi sui divisori di $n$. Possiamo dimostrare la formula nella maniera seguente. Per $n=1$ l’unico divisore è $d=1$ e poiché $\mu(1)=1$ allora la formula è dimostrata per questo caso. Ora se invece $n > 1$ scomponiamolo in fattori primi, cioè $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$. Allora i divisori di $d$ sono dati da $d = p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k}$ dove i $b_i$ sono tutte le possibili combinazioni tali che $0 \leq b_i \leq a_i$. Tuttavia, se un qualche $b_i \geq 2$ allora $d$ è divisibile per un quadrato e quindi $\mu(d)=0$. Perciò gli unici $d$ che contribuiscono sono quelli con $b_i = 0,1$, ovvero con fattori distinti. Perciò
$$\sum_{d | n} \mu(d) = 1 + \mu(p_1)+\cdots+\mu(p_k) + \mu(p_1 p_2) + \mu(p_{k-1}p_k) + \cdots + \mu(p_1 p_2 \cdots p_k)$$
ovvero abbiamo una somma su tutte le combinazioni con un fattore primo, poi col prodotto di esattamente due fattori primi, poi con tre e via dicendo. Per la definizione di $\mu(d)$ se $d$ è il prodotto di esattamente $l$ fattori primi, allora $\mu(d)=(-1)^l$. Inoltre possiamo contare quanti divisori ci sono con esattamente $l$ fattori primi; si tratta infatti di scegliere $l$ fattori primi tra $k$ fattori primi e ciò può essere fatto in ${k \choose l}$ modi. Perciò
$$\sum_{d | n} \mu(d) = 1 + (-1) {k \choose 1} + (-1)^2 {k \choose 2} + \cdots + (-1)^k {k \choose k}= \sum_{l=0}^k (-1)^l {k \choose l} = 0$$
L’ultima uguaglianza è ben nota e può essere dimostrata a partire dalla formula del binomio di Newton.
La funzione di Möbius può anche essere scritta con una formula esplicita, ovvero:
$$\mu(n) = \sum_{\substack{1 \leq k \leq n \\ \mathrm{gcd}(k,n)=1}} e^{2\pi i \frac{k}{n}}$$
Possiamo dimostrare questa formula a partire dall’uguaglianza precedente. Abbiamo infatti
$$\sum_{\substack{1 \leq k \leq n \\ \mathrm{gcd}(k,n)=1}} e^{2\pi i \frac{k}{n}} = \sum_{1 \leq k \leq n} \pqty{\sum_{d | \mathrm{gcd}(k,n)} \mu(d)}e^{2\pi i \frac{k}{n}}$$
Questo perché la quantità tra parentesi, come abbiamo visto, è non-nulla e uguale ad $1$ solo se $\mathrm{gcd}(k,n)=1$. Ora vogliamo raccogliere tutti i termini con lo stesso $\mu(d)$. Poiché $k$ arriva fino a $n$ e $\mathrm{gcd}(n,n)=n$, allora tutti e soli i divisori di $n$ compariranno come argomento di $\mu$. Perciò alla fine avremo una somma del tipo $\sum_{d | n} \mu(d) \chi(d)$ per un qualche $\chi(d)$, dove $\chi(d)$ sarà dato dalla somma di termini della forma $e^{2\pi i \frac{k}{n}}$. Provando un caso esplicito, risulta chiaro che $\chi(d)$ è la somma di tutti i $e^{2\pi i \frac{k}{n}}$ per $1 \leq k \leq n$ dove $k$ è un multiplo di $d$. Questo perché $e^{2\pi i \frac{k}{n}}$ comparirà nella somma sopra moltiplicato da $\mu(d)$ solo se $d | \mathrm{gcd}(k,n)$, perciò se $d | n$ allora $d | \mathrm{gcd}(k,n)$ se e solo se $k$ è un multiplo di $d$. perciò abbiamo
$$\sum_{\substack{1 \leq k \leq n \\ \mathrm{gcd}(k,n)=1}} e^{2\pi i \frac{k}{n}} = \sum_{1 \leq k \leq n} \pqty{\sum_{d | \mathrm{gcd}(k,n)} \mu(d)}e^{2\pi i \frac{k}{n}}=\sum_{d | n} \mu(d) \sum_{l=1}^{n/d} e^{2\pi i d \frac{l}{n}}$$
L’ultima somma è la somma delle radici $m-$esime dell’unità per $m=n/d$, ed è ben noto che questa somma è nulla tranne quando $m=1$, ovvero per $n=d$. Perciò l’espressione finale è semplicemente $\mu(n)$ e abbiamo il risultato che cercavamo.