Disuguaglianza $\phi$ga

[Troleito br00tal]

Own (tanto adesso arriverà enigma che mi dirà che la somma delle $\phi$ è boundata palese dal basso grazie al teorema di $\epsilon M \alpha Nu L$ $\tau Rohn$).

Dimostrare che per ogni intero positivo $n$ vale:
\begin{equation}
\sum_{i=1}^{2n} \phi(i) > n^2
\end{equation}

[lucaboss98]

EDIT: errore

[Troleito br00tal]

Controedit

[Gottinger95]

Mmm, quel lato mi è ostico, ma rilancio con
\[ \sum_{i=1}^{2n} \varphi(i) < (2n)^2 \frac{6}{\pi^2} \sim n^2 \cdot 2.43.. \]
che unito al fatto tuo è bello, perchè insomma, \(LHS\) va proprio come \(n^2\) !
P.S. Il problema è strafigo fes ma purtroppo lunedì ho la maturità, e tutto ciò che faccio sull'oliforum è illegale e all'insaputa di me stesso. Grande vecchio!
P.P.S Ti conviene usare \varphi invece che \phi

[Gottinger95]

Dimostreremo una cosa un po' più debole ma un po' più precisa, quindi manca ancora un pezzo da sporcaccioni per risponderti (c'è un \(n\) sufficientemente grande di mezzo).
Fatto. Detto \( \displaystyle S_m = \sum_{k=1}^m \varphi(k) \), vale
\[ \lim_{m \to \infty} \frac{S_m}{m^2} = \frac{3}{\pi^2}\]
Da questo segue che, per \(m\) sufficientemente grande vale :
\[ S_{2m} > \frac{12}{\pi^2} m^2 - \varepsilon > m^2 \]

Sfruttiamo il fatto che \(\displaystyle \varphi(n) = \sum_{d \mid n} \mu(d) \frac{n}{d} \) (come si ottiene? In mille modi: scrivendo \(\varphi(n)/n\) esplicitamente, con l'inversione di moebius..), abbiamo, per double counting:
\[ S_m = \sum_{k=1}^m \varphi(k) = \sum_{k=1}^m \sum_{d \mid k} \mu(d) \frac{k}{d} = \sum_{d=1}^m \mu(d) \sum_{d \mid k}^m \frac{k}{d} = \sum_{d=1}^m \mu(d) \sum_{j=1}^{[m/d] } j = \frac{1}{2} \sum_{d=1}^m \mu(d) [m/d] ( [m/d] +1 ) \]
Minoriamolo usando questa notazione (che mi rompo se no): \(\mu+\) in pedice alla sommatoria significa al variare degli addendi \(d\) che hanno \(mu(d)=+1\), e \(\mu-\)... lo lascio all'immaginazione. Vamos:
\[ S_m \ge \frac{1}{2} \left ( \sum_{d=1, \mu + }^m \mu(d) \frac{m}{d} ( \frac{m}{d} -1 ) + \sum_{d=1, \mu - }^m \mu(d) \frac{m}{d} (\frac{m}{d} +1) \right )= \frac{1}{2} \left ( m^2 \sum_{d=1}^m \frac{\mu(d)}{d^2} - m \sum_{d=1 }^m \frac{|\mu(d) |}{d} \right ) \ge \frac{1}{2} \left ( m^2 \sum_{d=1}^m \frac{\mu(d)}{d^2} - m \sum_{d=1}^m \frac{1}{d} \right ) \]
\[ = \frac{m^2}{2} \left ( \sum_{d=1}^m \frac{\mu(d) }{d^2} - \frac{H_m}{m}\right )\ \ (1) \]
dove \(H_m\) è la somma dei primi \(m\) inversi. Analogamente la maggiorazione dà
\[ S_m \le \frac{m^2}{2} \left ( \sum_{d=1}^m \frac{\mu(d) }{d^2} + \frac{H_m}{m} \right ) \ \ (2) \]
Per \(m \to \infty\), sfruttando in stile prodotto di eulero:
\[ \sum_{d=1}^{\infty} \frac{\mu(d)}{d^2} = \prod_{p \in \mathbb{P} } \left (1- p^{-2} \right ) = \left ( \prod_{p \in \mathbb{P} } \left (\frac{1}{1- p^{-2}} \right ) \right )^{-1}= \left (\sum_{n=1}^{\infty} \frac{1}{n^2} \right )^{-1} = \frac{6}{\pi^2} \]
e il fatto che \(H_m \sim \ln m\) (vedi qui), da cui:
\[ \lim_{m \to \infty} \frac{H_m}{m} = 0\]
abbiamo
\[ \lim_{m \to \infty } (1) = (2) = \frac{3}{\pi^2} m^2 \]
Per il teorema dei caramba, \(S_m\) è compreso tra due cose che hanno lo stesso limite, quindi
\[ \lim_{m \to \infty} \frac{S_m}{m^2} = \frac{3}{\pi^2} \]
che è la tesi.
Zan-zan! E' arrivato il momento delle zozzerie! Stimiamo da quando vale la disuguaglianza \(>m^2\). Sia \(R_m\) il termine tra parentesi nella (1).
Enunciamo un principio generale (una sorta di versione fast di induzione sulle disuguaglianze) che ci alleggerirà di molto:
Siano \( f,g: \mathbb{N} \to \mathbb{R} \). Se \(n_0\) è tale che
1. \(f(n_0) > g(n_0) \)
2. \( f(n+1) - f(n) > g(n+1)-g(n) \) per ogni \(n \ge n_0\)
Allora \(f(n) > g(n)\) per ogni \(n \ge n_0\) (semplicemente per induzione).

A noi piacerebbe che \( R_m > 1/2 \). Vogliamo applicare il lemma. Si può verificare che per \(m=34\) si ha \(R_m > 1/2\).
Per la cond. (1) vorremmo \(R_{m+1}-R_m > 0 \ \ \) (A) . Vale:
\[ R_{m+1} - R_m = \frac{\mu(m)}{m^2} + \frac{H_m}{m} - \frac{H_ {m+1} }{m+1} > -\frac{1}{m^2} + H_m \left ( \frac{1}{m} - \frac{1}{m+1} \right ) - \frac{1}{(m+1)^2}\]
\[ \frac{H_m}{m(m+1)} \stackrel{?}{\ge} \frac{1}{(m+1)^2}+ \frac{1}{m^2} \]
\[ H_m \stackrel{?}{\ge} \frac{m}{m+1} + \frac{m+1}{m} \ \ \ (B) \]
Riapplichiamo il lemma. Si può verificare che per \(m=4\) la disuguaglianza qui sopra vale. D'altronde, prendendo la "derivata discreta" da entrambe le parti e qualche conto al RHS:
\[ \frac{1}{m} \stackrel{?}{\ge} \frac{-2m}{(m+1)(m-1)} + \frac{2}{m} \]
che si riduce a \(m^2 \ge -1\), vera sempre. Quindi vale la (B) per \(m \ge 4\), quindi vale la (A) per \(m \ge 34\).
I casi \( 2m < 34 \) (16 casi) si verificano essere veri.

P.S. Con l'aiuto di questo programmino si possono anche trovare i valori arbitrariamente vicini a \( \frac{6}{\pi^2} \) che \(R_m\) assume da un certo punto in poi.

[Troleito br00tal]

Bella! Posto la mia.

Indichiamo con $S=\sum_{i=1}^{2n} \varphi(i)$. Il numero di coppie ordinate $(a;b)$ tali che $(a;b)=1$ e $1 \le a;b \le 2n$ è $2S-1$. Fissato $1 \le a \le 2n$, i valori che può assumere $b$ in modo che $(a;b)=1$ e $1 \le b \le 2n$ sono al più $\varphi(a) \cdot \lfloor \frac{2n}{a} \rfloor$. Quindi $2S-1 \ge \sum_{i=1}^{2n} \varphi(i) \cdot \lfloor \frac{2n}{i} \rfloor$. Fissiamo un numero $1 \le m \le 2n$ e contiamo il numero di coppie $(a;b)$ tali che $1 \le b \le a \le 2n$ e $\frac{a}{(a;b)}=m$: sono $\varphi(m) \cdot \lfloor \frac{2n}{m} \rfloor$. Al variare di $m$, contiamo esattamente una volta ogni coppia $(a;b)$ con $1 \le b \le a \le 2n$, quindi $\sum_{m=1}^{2n} \varphi(m) \cdot \lfloor \frac{2n}{m} \rfloor = \frac{2n \cdot (2n+1)}{2}=2n^2+n$. Ma allora $2S-1 \ge \sum_{i=1}^{2n} \varphi(i) \cdot \lfloor \frac{2n}{i} \rfloor = 2n^2+n \rightarrow S \ge n^2+\frac{n+1}{2} > n^2$.

[Gottinger95]

Ah, bella cavolo! In realtà è sempre double counting, solo che la tua è più combinatorica e la mia è più algebrica! Comunque chiedo venia per il post lungo e apparentemente un po' cannonoso, però in realtà la cosa più complicata che ho usato è il prodotto di eulero, e boh, alla fine mi pare abbastanza liscia, anche se incomparabilmente più lunga della tua..!
Comunque, piccolo rilancio: che succede se sostituiamo \(\varphi(n)\) con \(d(n)\)? Come si può stimare dal basso e dall'alto? E' più semplice assai!
E invece, dal punto sopra \(d(n)\), che possiamo dire per \(\omega(n)\)?