Mertens function

[carlo23]

Sia $M(x)$ la funzione di Mertens definita come

$M(x)=sum_(n<=x) mu(n)$

dove $mu$ è la funzione di Mobius che restituisce $(-1)^m$ se $n$ è libero da quadrati e ha $m$ fattori primi, $0$ altrimenti. Per convenzione $mu(1)=1$.

Dimostrare che per ogni $n$

$sum_(k=1)^n M(n/k)=1$

divertitevi, ciao ciao

[Thomas]

Sia $M(x)$ la funzione di Mertens definita come

$M(x)=sum_(n<=x) mu(m)$

giusto per correttezza, intendevi:

$M(x)=sum_(n<=x) mu(n)$

???

[carlo23]

Oh si, adesso ho corretto! mi deve essere scappato il dito sulla m

[Thomas]

Beh.. non provo spesso i problemi tuoi, carlo23 (troppo tecnici per me), ma questo se l'ho risolto pare veramente carino!!

Innanzitutto riscrivo la funzione contando quante volte per numero la funzione di moebius viene contata, ottenendo

$sum_(i=1)^(n) \mu(i)*[n/i]$

ove nelle quadre si intende la funzione "parte intera inferiore".

chiamo ora $p_1,...,p_k$ i primi minori o uguali ad n. La sommatoria si può riscrivere, utilizzando il fatto che se un fattore compare ad una potenza maggiore di 1, il numero non è "sqarefree" e quindi la funzione di moebius ivi si annulla... (è fatta così, vero? no perchè mi è venuto qualche dubbio...). Espando quindi la sommatoria (notare che "aggiungo dei pezzi", che però valgono 0):

$n - (sum_(i=1)^(k) [n/p_i] - sum_(i_1<i_2in(1..k)) [n/(p_(i_1)p_(i_2))] + ...+(-1)^(r-1) sum_(i_1<i_2<..<i_r) [n/(p_(i_1)*..*p_(i_r))]+...)$

ove la sommatoria finisce con r=k.

Ora osserviamo che all'interno della parentesi per il principio di inclusione-esclusione sono contati tutti i numeri minori od uguale ad n (è contata la cardinalità dell'unione degli insiemi t.c. ogni insieme conta i numeri divisibili per un certo $p_i$) a parte l'1. Il risultato quindi è n-(n-1)=1.

[carlo23]

Beh.. non provo spesso i problemi tuoi, carlo23 (troppo tecnici per me), ma questo se l'ho risolto pare veramente carino!!

è giusto, bravo!

Io invece l'ho dimostrato per induzione, supponiamo sia vero per $n>=1$ allora è vero per $n+1$

$sum_(k=1)^(n+1) M((n+1)/k) =sum_(k=1)^(n) M(n/k)+sum_(k=1)^(n+1) (-M(n/k)+M((n+1)/k))$

sappiamo che $M(x)=M([x])$ e che $[(n+1)/k]-[n/k]$ è $=1$ se $k|n+1$ altrimenti è $=0$

$sum_(k=1)^(n+1) M((n+1)/k) =1+sum_(k=1)^(n+1) (-M(n/k)+M((n+1)/k))$

$sum_(k=1)^(n+1) M((n+1)/k) =1+sum_(d|n+1) mu((n+1)/d)=1+sum_(d|n+1) mu(d)=1+(2^(epsilon(n+1)-1)-2^(epsilon(n+1)-1))=1$

dove $epsilon(n)$ è il numero di fattori primi distinti di $n$.

[Thomas]

sappiamo che $M(x)=M([x])$ e che $[n/k]-[(n+1)/k]$ è $=1$ se $k|n+1$ altrimenti è $=0$

credo sia

$[(n+1)/k]-[n/k]=1$

$1+sum_(d|n+1) mu(n/d)$

e quindi, (ho fatto notare quanto sopra per questo: non è bello vedere la mu con un argomento non naturale )

$1+sum_(d|n+1) mu((n+1)/d)$

Ok... a parte queste cavolate, carina anche la tua sol!! ...

[carlo23]

è che prima avevo scritto tutto dimostrando che se era vero per $n-1$ lo sarebbe stato per $n$, solo che poi ho pensato che qualcuno alle prime prese con l'induzione avrebbe subito chiesto spiegazioni, quindi ho riscritto andando da $n$ a $n+1$ e ho dimenticato qualche pezzo...