Funzioni aritmetiche e disuguaglianze

[HiTLeuLeR]

Prima di procedere nella lettura dei problemi proposti in questo topic, consiglio vivamente (in particolare, ai giovincelli) di dare un'occhiatina qui, giusto per formarsi un'idea di massima!

Problema #1: provare che, per ogni $ n\in\mathbb{N}_0 $: $ \varphi(n) + \sigma(n) \geq 2n $, ove $ \varphi(\cdot) $ indica la funzione dei totienti di Eulero e $ \sigma(\cdot) $ la funzione dei divisori di ordine $ 1 $. Determinare quindi l'insieme di tutti e soli gli $ n\in\mathbb{N}_0 $ per i quali sussiste l'uguaglianza.

[Boll]

Provo anche questo, su, così se devi flagellarmi fai tutto in una volta :D:D

Problema #1: provare che, per ogni $ n\in\mathbb{N}_0 $: $ \varphi(n) + \sigma(n) \geq 2n $, ove $ \varphi(\cdot) $ indica la funzione dei totienti di Eulero e $ \sigma(\cdot) $ la funzione dei divisori di ordine $ 1 $. Determinare quindi l'insieme di tutti e soli gli $ n\in\mathbb{N}_0 $ per i quali sussiste l'uguaglianza.

Il caso di $ n=1 $ ce le togliamo subito, vale l'uguaglianza

Premesse
Banalmente avremo che $ \phi(n)<n $ $ \forall n>1 $ per come è definita la totiente e poichè almeno $ n $ non è coprimo con sè stesso. Quindi la $ \phi(\cdot) $ vale al massimo $ n-1 $.

Altrettanto banalmente si avrà che $ \sigma(n)>n $ $ \forall n>1 $ poichè al minimo un intero ha due divisori, sè stesso è l'unità, la somma di questi due dà già un numero maggiore di n. Pertanto la funzione $ \sigma(\cdot) $ vale, al minimo $ n+1 $

Se ne deduce che $ \sigma(n)>n>\phi(n) $

Si utilizzeranno ma non si dimostreranno in seguito i seguenti fatti:
- la funzione $ \phi(\cdot) $ è moltiplicativa, ma non strettamente moltiplicativa
- la funzione $ \sigma(\cdot) $ presenta a medesima proprietà
- preso $ n={p_1}^{e_1}{p_2}^{e_2}...{p_k}^{e_k} $ avremo che
$ \phi(n)=({p_1}^{e_1}-{p_1}^{e_1-1})({p_2}^{e_2}-{p_2}^{e_2-1})...({p_k}^{e_k}-{p_k}^{e_k-1}) $
e $ \sigma(n)=(1+p_1+{p_1}^{2}+...+{p_1}^{e_1})...(1+p_k+{p_k}^{2}+...+{p_k}^{e_k}) $
Le variabili successivamente introdotte sono sempre da pensarsi come interi positivi.

Ora la tesi (disug)

Prendiamo $ n={p_1}^{e_1}{p_2}^{e_2}...{p_\omega}^{e_\omega} $. Chiamiamo $ q_i={p_i}^{e_i} $ quindi $ n=q_1q_2q_3...q_\omega $
Dimostriamo la tesi per induzione sul numero dei $ q_i $. Chiamiamo tale numero $ \omega $

Per $ \omega=1 $ avremo $ n=p^k $
Quindi
$ p^k-p^{k-1}+1+p+p^2+...+p^k\geq 2p^k $
$ 2p^k+1+p+p^2+...+p^{k-2}\geq 2p^k $
ciò dimostra che in tal caso vale sempre la disug e l'uguaglianza sse $ k=1 $, cioè se $ n $ è un numero primo.

Ora supponiamo che funzioni per $ \omega $ e dimostriamolo per $ \omega+1 $ chiamiamo $ g={p_1}^{e_1}{p_2}^{e_2}...{p_\omega}^{e_\omega} $
quindi, per ipotesi,
$ \phi(g)+\sigma(g)\geq 2g $
La tesi diventa
$ \phi(g)\phi(q_{\omega+1})+\sigma(g)\sigma(q_{\omega+1})\geq 2gq_{\omega+1} $
cioè,
$ \phi(g){p_{\omega+1}}^{e_{\omega+1}}-\phi(g){p_{\omega+1}}^{e_{\omega+1}-1}+\sigma(g) $ $ +\sigma(g)p_{\omega+1}+...+\sigma(g){p_{\omega+1}}^{e_{\omega+1}}\geq 2gp_{\omega+1}^{e_{\omega+1}} $
Posto $ \sigma(g){p_{\omega+1}}^{e_{\omega+1}-1}-\phi(g){p_{\omega+1}}^{e_{\omega+1}-1}=k $, $ k\in \mathbb{N}_0 $ per quanto precedentemente dimostrato avremo che la disuguaglianza diviene

$ \phi(g){p_{\omega+1}}^{e_{\omega+1}}+\sigma(g){p_{\omega+1}}^{e_{\omega+1}}+k+\sigma(g)+ $$ \sigma(g)p_{\omega+1}+...+\sigma(g)p_{\omega+1}^{e_{\omega+1}-2}\geq 2gp_{\omega+1}^{e_{\omega+1}} $
Raccogliendo il fattore comune dei due addendi più a sinistra, per ipotesi induttiva la disuguaglianza è verificata e l'addendo $ k $ rende la disuguaglianza stretta. Quindi l'uguaglianza vale sse $ n=p $, con $ p\in \mathfrak{P} $

[HiTLeuLeR]

[...] poichè al minimo un intero ha due divisori, se stesso è l'unità, la somma di questi due da già un numero [...]

Mamma mia, Boll, se non meriteresti davvero di essere rispedito a calci in c**o sui banchi della scuola materna...

Prendiamo $ n={p_1}^{e_1}{p_2}^{e_2}...{p_k}^{e_k} $. Chiamiamo $ q_i={p_i}^{e_i} $ quindi $ n=q_1q_2q_3...q_k $
Dimostriamo la tesi per induzione sul numero dei $ q_i $. Chiamiamo tale numero $ \omega $. Per $ \omega=1 $ avremo $ n=p^k $

Cioè dimmi... Forse stai assumendo massicce dosi di betametasone? Nel giro di qualche rigo, chiami $ \omega $ quel che già hai indicato con $ k $, e quindi utilizzi $ k $ per tutt'altro scopo. Vada che si tratta soltanto di notazioni, ma per l'amor di Dio...

Quindi [...] $ 2p^k+1+p+p^2+...+p^{k-2}\geq 2p^k $

Perché si possa scrivere quest'ultima relazione, è necessario ammettere (purché sia detto da qualche parte) che sia $ k \geq 2 $, nel qual caso la disuguaglianza indicata vale (incidentalmente) con il segno di maggiore stretto.

Bon, prima di leggere il seguito, vo' a pranzare! Sai, non si vive certo di sola Matematica...

[HiTLeuLeR]

[...] un intero ha due divisori, sè stesso è l'unità, la somma di questi [...]

Ma loool! Hai corretto quel ch'era giusto, Bollo... Ma per tutti gli ippopotami, sei una vera chiavica!!!

$ \phi(g){p_{\omega+1}}^{e_{\omega+1}}+\sigma(g){p_{\omega+1}}^{e_{\omega+1}}+k+\sigma(g)+ $$ \sigma(g)p_{\omega+1}+...+\sigma(g)p_{\omega+1}^{e_{\omega+1}-2}\geq 2gp_{\omega+1}^{e_{\omega+1}} $

Scritto così, il passaggio precedente impone di distinguere il caso $ e_{\omega+1} = 1 $ dal caso $ e_{\omega+1} \geq 2 $. Per renderti la vita più comoda, pertanto, puoi semplicemente osservare che:

$ \phi(g){p_{\omega+1}}^{e_{\omega+1}}-\phi(g){p_{\omega+1}}^{e_{\omega+1}-1}+\sigma(g) $ $ +\sigma(g)p_{\omega+1}+...+\sigma(g){p_{\omega+1}}^{e_{\omega+1}}\geq $ $ \phi(g){p_{\omega+1}}^{e_{\omega+1}}+\sigma(g){p_{\omega+1}}^{e_{\omega+1}}+k $.

Sul resto non ho nulla da eccepire, e per dimostrartelo ti dò ADDIRITTURA la sufficienza piena!

[Boll]

baah, quella roba è una sommatoria scritta con i puntini per essere più leggibile, nel caso in cui $ e_{\omega+1}=1 $ semplicemente tutto va a zero. Stesso discorso per l'osservazione fatta prima. Comunque, se ti piace di più, vedila come hai scritto tu.

P.S. OT:Riguardo all'italiano, butto dentro e non sprecarti troppo coi voti, mi raccomando

[HiTLeuLeR]

Bollazzo, bollazzo... S'io scrivo una roba del tipo $ \sum_{k=1}^n f(n) $, in cui $ f(\cdot) $ è una funzione di $ \mathbb{N}_0 $ a valori in un qualche magma additivo, debbo preventivamente assicurarmi che l'estremo superiore di sommazione sia un intero $ \geq 1 $, o comunque dichiarare esplicitamente che, là dove la condizione indicata non sia soddisfatta, la somma si assume (per convenzione) pari a zero. Poi tu puoi raccontarmi tutte le favolette che ti pare: resta il fatto che sei impreciso, sommario, arraffone e parecchio approssimativo, tié...

[HiTLeuLeR]

Problema #2: provare ch'esiste un insieme finito $ \mathcal{K}\subset \mathbb{N}_0 $ tale che, per ogni $ n\in\mathbb{N}_0\setminus\mathcal{K} $: $ \varphi(n) \geq \sqrt{n} $.

[ma_go]

cioè l'insieme degli $ n $ tali che $ \varphi(n) \le n $ è finito?
usa un italiano comprensibile, e meno arzigogolato, prima di guardare ai (fastidiosi) errori banalmente tipografici.

[HiTLeuLeR]

"Noi siamo quel che scriviamo e secondo il modo in cui lo scriviamo. Pertanto, se scriviamo ad esempio coi piedi, c'è da pensare sia imputabile al fatto che abbiamo la testa sotto i piedi."

L'oggetto del post contiene la risposta alla tua domanda, ma_go! La citazione, invece, risponde al tuo vaniloquio...

EDIT: rivisto a seguito della giusta considerazione di Bollazzo!!!

[Spider]

Problema #2: provare ch'esiste un insieme finito $ \mathcal{K}\subset \mathbb{N}_0 $ tale che, per ogni $ n\in\mathbb{N}_0\setminus\mathcal{K} $: $ \varphi(n) \geq \sqrt{n} $.

Questa non la so dimostrare, provo a dimostrare invece che esistono finiti $ n $ per cui $ \varphi(n) < \sqrt{n} $ o, meglio, che per $ n > 6 $ è vero che $ \varphi(n) \geq \sqrt{n} $. Spero andrà bene lo stesso anche enunciato così

Supponiamo di aver dimostrato l'enunciato per tutti i numeri squarefree (ossia non divisibili per il quadrato di un primo) e pari. Allora l'enunciato segue immediatamente anche per quelli dispari, osservando che se $ m $ è dispari, allora $ \varphi(2m) = \varphi(m) $. Da qui possiamo dedurre che esso è vero anche per tutti gli altri $ n $, infatti se $ \varphi(n) \geq \sqrt{n} $ e $ p\mid n $, allora $ \varphi(pn) = p\varphi(n) \geq p\sqrt{n} \geq \sqrt{pn} $. Ci siamo così ridotti a dimostrare la disuguaglianza per i numeri squarefree pari. Osserviamo che un numero $ n $ di questa forma si può scrivere come $ n = 2\cdot p_1\cdot p_2\cdot ... \cdot p_k $, dove supponiamo per comodità tutti i primi in ordine crescente. Per tutti i primi dispari $ p $ vale $ \varphi(p) \geq \sqrt{p} $, inoltre se $ n > 6 $, allora $ p_k \geq 5 $ e $ \varphi(p_k) = p_k - 1 \geq \sqrt{p_k}\cdot\sqrt{2} $, come è facile verificare.
Mettendo insieme tutto abbiamo che:
$ \varphi(n) = \varphi(2\cdot p_1\cdot p_2\cdot ... \cdot p_k) = $
$ = \varphi(p_1)\varphi(p_2)...\varphi(p_k) \geq \sqrt{p_1}\cdot\sqrt{p_2}\cdot ... \cdot \sqrt{p_{k-1}}\cdot \sqrt{2p_k} = \sqrt{n} $.

[Boll]

cioè l'insieme degli $ n $ tali che $ \varphi(n) \le n $ è finito?

Scusatemi, ma non capisco (che strano, eh :D), come scrissi prima, e Euler non contraddisse quindi suppongo sia giusto.
$ \phi(n)<n $ per tutti gli $ n $ diversi da $ 1 $ (e mi pare pure una considerazione banalissima). Come fa quindi a essere vera l'asserzione di ma_go????

[HiTLeuLeR]

Bollazzo, ci manca una radice quadrata, ecco tutto! Probabilmente, ma_go intendeva scrivere che esistono finiti $ n\in\mathbb{N}_0 $ tali che: $ \phi(n) < \sqrt{n} $, ecco tutto!!! Ed io pure che gli ho concesso il benestare...

[HiTLeuLeR]

[...] provo a dimostrare invece che [...], per $ n > 6 $ è vero che $ \varphi(n) \geq \sqrt{n} $. [...]

Supponiamo di aver dimostrato l'enunciato per tutti i numeri squarefree [...] e pari. Allora l'enunciato segue immediatamente anche per quelli dispari, osservando che se $ m $ è dispari, allora $ \varphi(2m) = \varphi(m) $. Da qui possiamo dedurre che esso è vero anche per tutti gli altri $ n $, infatti se $ \varphi(n) \geq \sqrt{n} $ e $ p\mid n $, allora $ \varphi(pn) = p\varphi(n) \geq p\sqrt{n} \geq \sqrt{pn} $.

Ahime', il tuo proof presenta qualche lacuna, che tuttavia ti obbliga soltanto a svolgere delle piccole considerazioni addizionali, senza per questo dover buttare all'aria tutto il lavoro già svolto. Orbene, per intenderci meglio, vediamo un po' se riesco a ricostruire la logica delle tue argomentazioni. Sostanzialmente, tu osservi (ineccepibile in questo!!!) che, se $ m $ è un intero squarefree $ > 1 $ tale da verificare la disuguaglianza di Kendall-Osborn, allora questa è pure soddisfatta da qualunque altro numero naturale $ n > 0 $ tale che ogni divisore primo intero di $ n $ sia pure un divisore primo intero di $ m $, e viceversa; e sulla base di questa considerazione ti restringi a operare sui soli interi positivi $ \equiv 2 \bmod 4 $. Dico giusto?

Bon, come tu stesso dimostri, l'argomento regge fintanto che gli squarefree presi in considerazione sono pari e maggiori di $ 6 $. E tuttavia, siccome $ 2 $ e $ 6 $ sono essi stessi liberi da quadrato, ma non soddisfano la disuguaglianza indicata, ne viene che i tuoi argomenti non sono sufficienti per coprire i casi in cui gli interi in gioco siano della forma $ 2^a, 3^b\mbox{ o }2^c 3^d $, con $ a, b, c, d \in \mathbb{N}_0 $ e $ c + d \geq 3 $. A te il diritto di replica...

[Spider]

Non te ne sfugge una, eh?

Se n è della forma $ 3^b $ allora $ \varphi(n) = 2 \cdot 3^{b-1} \geq \sqrt{3^b} $; se $ n = 2^a $ e $ a > 1 $, $ \varphi(2^a) = 2^{a - 1} >= \sqrt{2^a} $. Infine se $ n = 2^c3^d $, allora $ \varphi(2^c3^d) = 2^{c}3^{d-1} $, per la quale se $ c \geq 2 $ la disuguaglianza segue banalmente dai due casi precedenti, mentre se $ c = 1 $ è vera solo per $ d \geq 2 $, nel qual caso $ \varphi(2\cdot3^d) = 2\cdot3^{d-1} \geq \sqrt{2}\sqrt{3^d} $. La verifica è abbastanza banale.

Vediamo se mi butti giù anche questa

Spider

EDIT: errorini di battitura

[HiTLeuLeR]

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).

P.S.: ok, Spider, quella non la butta giù nessuno!!!