Funzioni aritmetiche e disuguaglianze

[Boll]

Problema #3: provare che, per ogni intero $ n > 0 $: $ \varphi(n)\sigma(n) \leq n^2 $, e quindi determinare tutti e soli gli interi positivi per i quali sussiste (in particolare) l'uguaglianza (btw, in quanto alle notazioni, si vedano i problemi precedenti).

Premesse:
Le funzioni $ \phi(\cdot) $ e $ \sigma(\cdot) $ sono moltiplicative e hanno le formule generali da me enunciate nella dimostrazione del Problema 1 di Hitleuler

Lemmino::
Siamo sugli interi positivi, quindi se
$ a< b $
$ c< d $ allora
$ ac< bd $

Dimostrazione

Solo per $ n=1 $ vale l'uguaglianza

Ora, per $ n=p^k $, $ \forall p\in \mathfrak{P},k\in \mathbb{N}_0 $ la disuguaglianza è verificiata in modo stretto.
Dimostriamolo
La disug diviene:
$ (p^k-p^{k-1})(1+p+p^2+\dots+p^k)< p^{2k} $
$ p^k+p^{k+1}+\dots+p^{2k}-p^{k-1}-p^k-\dots-p^{2k-1}< p^{2k} $

$ -p^{k-1}< 0 $
banalmente vero poichè $ k\geq 1 $ e $ p $ è in intero positivo.

Ora dimostriamolo per un $ n $ generico $ >1 $, quindi, in coerenza con il Th. fondamentale dell'Aritmetica scrivibile come
$ n={p_1}^{e_1}{p_2}^{e_2}...{p_k}^{e_k} $

Avremo che, per quando dimostrato in precedenza:
$ \phi({p_1}^{e_1})\sigma({p_1}^{e_1})<{p_1}^{2e_1} $
$ \phi({p_2}^{e_2})\sigma({p_2}^{e_2})<{p_1}^{2e_2} $
$ \phi({p_3}^{e_3})\sigma({p_3}^{e_3})<{p_1}^{2e_3} $
$ \dots $
$ \phi({p_k}^{e_k})\sigma({p_k}^{e_k})<{p_k}^{2e_k} $

Applicando il Lemmino
$ \displaystyle \prod_{i=1}^{k}\sigma({p_i}^{e_i})\phi({p_i}^{e_i})<\prod_{i=1}^{k}{p_i}^{2e_i} $
Sfruttando la moltiplicatività delle funzioni
$ \sigma(n)\phi(n)<n^2 $
che è la tesi.

[HiTLeuLeR]

$ p^k+p^{k+1}+\dots+p^{2k}-p^{k-1}-p^k-\dots-p^{2k-1}\le p^{2k} $ $ -p^{k-1}< 0 $

Voglio immaginare che ad ultimo membro di questa catena di disuguaglianze dovesse esserci scritto $ p^{2k} $, e non $ 0 $... In quanto al resto, tutto funzia! Direi che possiamo perciò già passare alla successiva.

Problema #4: provare ch'esiste una costante reale $ \gamma > 0 $ t.c., per ogni $ n\in\mathbb{N}_0 $: $ \varphi(n)\sigma(n) \geq \gamma n^2 $, e quindi determinare il valore ottimo d'una tale costante (i.e, il valore massimo per cui la disuguaglianza indicata continua a sussistere).

[Boll]

$ p^k+p^{k+1}+\dots+p^{2k}-p^{k-1}-p^k-\dots-p^{2k-1}\le p^{2k} $ $ -p^{k-1}< 0 $

Voglio immaginare che ad ultimo membro di questa catena di disuguaglianze dovesse esserci scritto $ p^{2k} $, e non $ 0 $...

No, Euler, era giusto scritto così solo dovevi andare a capo, era un altro passaggio. Ora l'ho indicato con due "INVIO" ma credevo uno bastasse.

[Simo_the_wolf]

Ok, abbiamo che, detto $ n=p_1^{\alpha_1}p_1^{\alpha_1} \cdots p_k^{\alpha_k} $:
- $ \displaystyle \phi(n)=n(1-\frac 1{p_1})(1-\frac 1{p_2}) \cdots (1-\frac 1{p_k}) $
- $ \displaystyle \sigma(n)=\frac {p_1^{\alpha_1+1}-1}{p_1-1}\frac {p_2^{\alpha_2+1}-1}{p_2-1} \cdots \frac {p_k^{\alpha_k+1}-1}{p_k-1} $
Quindi abbiamo che:
$ \displaystyle \phi(n) \sigma(n)=n (p_1^{\alpha_1}-\frac 1{p_1})(p_2^{\alpha_2}-\frac 1{p_2}) \cdots (p_k^{\alpha_k}-\frac 1{p_k}) \geq \gamma n^2 $
Questo implica:
$ \displaystyle (1-\frac 1{p_1^{\alpha_1+1}})(1-\frac 1{p_2^{\alpha_2+1}}) \cdots (1-\frac 1{p_k^{\alpha_k+1}}) \geq \gamma $
Se vogliamo minimizzare il membro di sisistra deve risultare $ \alpha_1=\alpha_2= \cdots =\alpha_k=1 $ e dobbiamo prendere più primi possibile. Prendendoli tutti, all'infinito abbiamo:
$ \displaystyle \frac {\phi(n) \sigma(n)}{n^2} \geq \prod_{\text{p primo}} (1-\frac 1{p^2})=\frac 1{\zeta (2)}=\frac 6{\pi^2}=\gamma $

[HiTLeuLeR]

Splendido, Simo! Inserirei soltanto un'osservazione preliminare: $ \varphi(1)\sigma(1) = 1 $.

$ \displaystyle \sigma(n)=\frac {p_1^{\alpha_1+1}-1}{p_1-1}\frac {p_2^{\alpha_2}-1}{p_2-1} \cdots \frac {p_k^{\alpha_k}-1}{p_k-1} $

Qua e là, aggiungerei inoltre un 1 agli esponenti, giusto per far quadrare i conti, ecco...

Problema #5: mostrare che, per ogni intero positivo $ n $ composito: $ \varphi(n) \leq n - \sqrt{n} $. Determinare quindi tutti e soli i casi in cui la relazione indicata si riduce effettivamente a un'uguaglianza.

[Simo_the_wolf]

Se n è composto allora almeno un suo fattore primo $ p $ è tale che $ p \leq \sqrt{n} $. Quindi ci sono $ n/p $ numeri non maggiori di n e multipli di p e quindi essi sono almeno $ \sqrt{n} $. Quindi $ \varphi(n) \leq n-\sqrt{n} $ e l'uguaglianza vale solo quando $ p=\sqrt{n} $ cioè quando $ n $ è il quadrato di un primo

[Boll]

Problema #5: mostrare che, per ogni intero positivo $ n $ composito: $ \varphi(n) \leq n - \sqrt{n} $. Determinare quindi tutti e soli i casi in cui la relazione indicata si riduce effettivamente a un'uguaglianza.

Allora, in coerenza con il teorema fondamentale dell'Aritmetica scrivo $ \displaystyle n=\prod_{i=1}^{k}p_{i}^{e_i} $. Pongo $ q_i=p_i^{e_i} $, quindi $ \displaystyle n=\prod_{i=1}^{n}q_i $. Ragiono per induzione sul numero dei $ q_i $

Caso k=1

$ \phi(p^j)\le p^j-\sqrt{p^j} $
$ p^j-p^{j-1}\le p^j-\sqrt{p^j} $
$ p^{j-1}\ge \sqrt{p^j} $
$ p^{2j-2}\ge p^j $
$ p^{j-2}\ge 1 $
vera sse $ j\ge 2 $ quindi se $ n $ è composto, e l'uguaglianza vale sse $ n=p^2 $ con $ p\in \mathfrak{P} $

Passo induttivo: pongo vero k-1 e dimostro k

Avremo che $ \phi(n)\le n-\sqrt{n} $ per hp induttiva e che
$ \phi(p_k^{e_k})\le p_k^{e_k}-\sqrt{p_k^{e_k}} $ per quanto provato prima. Quindi avremo che:
$ \phi(n)\phi(p_k^{e_k})\le(n-\sqrt{n})(p_k^{e_k}-\sqrt{p_k^{e_k}}) $
$ \phi(n)\phi(p_k^{e_k})\le np_k^{e_k}-\sqrt{n}p_k^{e_k}+\sqrt{p_k^{e_k}}\sqrt{n}-n\sqrt{p_k^{e_k}} $
ma $ np_k^{e_k}-\sqrt{n}p_k^{e_k}+\sqrt{p_k^{e_k}}\sqrt{n}-n\sqrt{p_k^{e_k}}< np_k^{e_k}-\sqrt{np_k^{e_k}} $
poichè
$ \sqrt{np_k^{e_k}}<\sqrt{n}p_k^{e_k} $
$ \sqrt{np_k^{e_k}}<\sqrt{p_k^{e_k}}n $
perchè sia $ n $ che $ p $ sono fuori da $ [0,1] $
Quindi sommando quelle due ho la tesi.

[HiTLeuLeR]

Quindi $ \varphi(n) \leq n-\sqrt{n} $ e l'uguaglianza vale solo quando $ p=\sqrt{n} $ cioè quando $ n $ è il quadrato di un primo

Intanto voglio dirti che trovo il tuo proof incantevole, Simo, e questo è un fatto! Lasciami aggiungere tuttavia che, pur avendo tu mostrato come la diseguaglianza di Schinzel-Sierpinski si riduca a un'uguaglianza solo se $ n = p^2 $, per qualche $ p\in\mathfrak{P} $, non hai altresì provato che la condizione indicata è pure sufficiente (lo so, è banale, ma ciò nondimeno indispensabile per ambire ad un punteggio pieno). Non temere, ti risparmio la noia. Dico infatti che, se $ n = p^2 $ e $ p\in\mathfrak{P} $: $ \varphi(n) = \varphi(p^2) = p(p-1) = p^2 - p = n - \sqrt{n} $, q.e.d.

[...] Passo induttivo: pongo vero k-1 e dimostro k
Avremo che $ \phi(n)\le n-\sqrt{n} $ per hp induttiva e che $ \phi(p_k^{e_k})\le p_k^{e_k}-\sqrt{p_k^{e_k}} $ per quanto provato prima. Quindi avremo che: $ \phi(n)\phi(p_k^{e_k})\le(n-\sqrt{n})(p_k^{e_k}-\sqrt{p_k^{e_k}}) $

E veniamo quindi a te, Bollazzo... Immagino che in tutto questo $ n $ sia un intero positivo $ > 1 $ la cui scomposizione canonica euclidea contiene esattamente $ k-1 $ fattori primi distinti (con $ k $ intero $ > 1 $); che $ p_k\in\mathfrak{P} $ sia coprimo con $ n $; e che $ e_k $ sia un numero naturale positivo. Sarò pedante, ma in verità vi dico... anche un po' mitomane!?! E speriamo che qualcuno almeno intuisca la pessima battuta, gh...

[...] $ \sqrt{np_k^{e_k}}<\sqrt{n}p_k^{e_k} $; $ \sqrt{np_k^{e_k}}<\sqrt{p_k^{e_k}}n $
perchè sia $ n $ che $ p $ sono fuori da $ [0,1] $ [...]

Suppongo tu intenda significare che $ n $ e $ p $ sono entrambi (strettamente) maggiori di $ 1 $...

[Boll]

Uff, ma a parte tutto questo, che ha una rilevanza incredibbbile, è giusto, vero?

[Simo_the_wolf]

in effetti se avessi scritto $ \geq $ al posto di "almeno", si sarebbe al volo capito che i segni di ugaglianza c'erano se e solo se c'era nella prima disuguaglianza... Cmq sono felice che il mio "proof" ti piaccia

P.S.: frattanto mi sto ancora scervellando x Cullen...

[HiTLeuLeR]

@Boll: sinteticamente?!? Sì...

@Simo_the_wolf: il problema dei Cullen non è certo fra i più facili che abbia mai proposto, ecco perché! Sarei tentato di darti un suggerimento, ma non credo di volerlo fino in fondo, per cui...