La funzionale che risolleverà il forum

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Avatar utente
Troleito br00tal
Messaggi: 679
Iscritto il: 16 mag 2012, 22:25

La funzionale che risolleverà il forum

Messaggio da Troleito br00tal » 19 mag 2015, 21:37

Own.

Sia $f: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ tale che $f(\phi(x))=\phi(f(x))$ per ogni $x \in \mathbb{Z}^+$ ($\phi$ è la funzione di Eulero). Determinare la più piccola costante $c$ tale che $f(x+1) \le 2x^c$ per ogni $x \in \mathbb{Z}^+$.

Talete
Messaggi: 666
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: La funzionale che risolleverà il forum

Messaggio da Talete » 20 mag 2015, 14:51

Dato che questa funzionale risolleverà il forum (o almeno dovrebbe) non la risolvo (anche perché non l'ho risolta) ma faccio delle osservazioni da cui altri potranno trarre spunto e risollevare il forum:

1. Sostituendo valori bassi ottengo che $f(1)=\phi(f(1))$, quindi $f(1)=1$, che deriva dal fatto che l'unico numero uguale alla sua $\phi$ è $1$.

2. So che $f$ non è univocamente determinata. Infatti, $f(x)\equiv1$ costantemente e $f(x)=x$ rispettano la condizione (basta sostituire).

3. Provando i numeri piccoli, ottengo che $f(2)\in\{1,2\}$, che $f(3)\in\{1,2,3,4,6\}$, che $f(4)\in\{1,2,3,4,6\}$... insomma, posso dire che:
\[f(x)\in\{y\mid \phi(y)<x\}\]
che è una scrittura carina che però non serve a niente, se non a dire che:
\[\max\{f(x+1)\}=\max\{y\mid \phi(y)\le x\}.\]

E poi boh...

EDIT: con $f(x)\in A$ intendo che tutti i valori raggiungibili da $f(x)$ sono nell'insieme $A$.
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

erFuricksen
Messaggi: 158
Iscritto il: 28 lug 2014, 10:01
Località: Genova

Re: La funzionale che risolleverà il forum

Messaggio da erFuricksen » 20 mag 2015, 15:31

Io ieri sera avevo trovato una bella linea da seguire, però ho ancora dei buchi.. diciamo che con il tuo fatto 3 dovrei avere la soluzione.. come lo dimostri?
$ x^2 + (y - \sqrt {|x|} )^2 = 2 $

Talete
Messaggi: 666
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: La funzionale che risolleverà il forum

Messaggio da Talete » 20 mag 2015, 20:05

In mente l'idea ce l'ho, ma formalizzarla... comunque era falso (o meglio, non del tutto vero), quindi boh, faccio il mio lemma:

Lemma overpowered che serve (solo) ad erFuricksen. Siano definiti infiniti insiemi (disgiunti, ma chissene frega?) $A_n:=\{x\mid \phi(x)=n\}$ per tutti gli $n$ interi positivi. Allora $A_1=\{1,2\}$, $A_2=\{3,4,6\}$, $A_3=\emptyset$ etc. Cosa mi piace di questi insiemi? Che, in pratica il mio lemma è:

\[\max\{f(x)\}=\max\left\{\bigcup_{i=1}^{\phi(x)} A_i\right\},\]

che deriva dal fatto che:

\[f(x)\in\bigcup_{i=1}^{\phi(x)} A_i\hspace{1cm}(\star).\]

Ora quindi devo dimostrare $(\star)$ per avere il lemma. Considerazione: cos'è cambiato dall'osservazione 3 (falsa) al mio lemma (che ora dimostrerò vero?) Be', semplicemente la 3 aveva un $x-1$ che in realtà era una $\phi(x)$, dovuto al fatto che per i casi piccoli era vero...

Allora, induciamo estesamente. Passo base, per $2$ è banalmente vero (non posso farlo per $1$ perché ci sarebbe un'unione di nessun insieme...).

Passo induttivo, suppongo per tutti i numeri fino a $n-1$, in particolare per $\phi(n)$, $(\star)$ vera. Allora $f(m)=\phi(f(n))$. Ora dunque $f(\phi(n))$ può per ipotesi induttiva variare su tutti gli elementi di tutti gli insiemi $A_i$ per $i$ da $1$ a $\phi(n)$: quindi $f(n)$ può variare su tutti gli elementi $z$ con $\phi(z)\le\phi(n)$, che è proprio $(\star)$ per il numero $n$. Evvai! Ce l'ho fatta!

[_] (solito quadratino di "dimostrato!" che non so fare, \qed non va). Credo sia vero...
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

erFuricksen
Messaggi: 158
Iscritto il: 28 lug 2014, 10:01
Località: Genova

Re: La funzionale che risolleverà il forum

Messaggio da erFuricksen » 21 mag 2015, 14:27

Grazie mille! :D

Ora dovrebbe andare tutto, spero non ci siano errori:

Chiamiamo per comodità di scrittura
$$ \max\{f(x)\}=\max\left\{\bigcup_{i=1}^{\phi(x)} A_i\right\} = \alpha $$
Ovviamente $ f(x) \le \alpha $
e dalla definizione è evidente che $ \phi ( \alpha) \le \phi (x)$

Fatto importante: $ \phi (n) \ge \sqrt{{n \over 2}}$

Usando questo fatto ricaviamo che $ 2 (\phi (\alpha)) ^2 \ge \alpha $ da cui
$f(x) \le \alpha \le 2 (\phi (\alpha))^2 \le 2(\phi(\alpha))^2 \le 2(x-1)^2$ perciò $c=2$ :D
Notiamo che $c$ non può essere minore perché se considero la valida relazione $f(3)=6$ ad esempio, vedo che $c=1$ non è accettabile

Ma per non lasciare nulla al caso, dimostriamo il fatto importante!

Vogliamo che $\phi (n) \ge \sqrt{{n \over 2}}$
che equivale a ${p_1}^{\alpha _1 -1} \cdot {p_2}^{\alpha _2 -1} ... {p_k}^{\alpha _k -1} (p_1 -1)(p_2 -1) ... (p_k - 1) \ge \sqrt{{n \over 2}}$
${p_1}^{2\alpha _1 -2} \cdot {p_2}^{2\alpha _2 -2} ... {p_k}^{2\alpha _k -2} (p_1 -1)^2(p_2 -1)^2 ... (p_k - 1)^2 \ge {n \over 2}$
$2{p_1}^{\alpha _1 -2} \cdot {p_2}^{\alpha _2 -2} ... {p_k}^{\alpha _k -2} (p_1 -1)^2(p_2 -1)^2 ... (p_k - 1)^2 \ge 1$
Ora, se $\alpha _i \ge 2$ non ci sono problemi, se invece $\alpha _i =1$ accoppiamo in questo modo:
${p_i}^{-1}(p_i -1)^2$ , e questa cosa è maggiore di 1 per ogni $p \ne 2$ , se invece ci fosse nella fattorizzazione $p=2$ allora sarebbe compensato dal 2 che compare all'inizio del prodotto... dovremmo esserci :)
Ultima modifica di erFuricksen il 02 giu 2015, 13:55, modificato 2 volte in totale.
$ x^2 + (y - \sqrt {|x|} )^2 = 2 $

Talete
Messaggi: 666
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: La funzionale che risolleverà il forum

Messaggio da Talete » 21 mag 2015, 19:20

Grande!!! ;) Avevo congetturato fosse $c=2$, ma dimostrarlo... comunque c'è un typo nella dimostrazione del fatto importante: accorpi $p_i^{-1}(p_i)^2$ invece di $p_i^{-1}(p_i-1)^2$ però il resto è a posto... :) Adesso manca solo il punto (b): risollevare il forum... ;)
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

erFuricksen
Messaggi: 158
Iscritto il: 28 lug 2014, 10:01
Località: Genova

Re: La funzionale che risolleverà il forum

Messaggio da erFuricksen » 21 mag 2015, 21:04

L'ho corretto!
Avevo già provato a dimostrare per induzione che $f(\phi (x)) < x$ ma non sono arrivato da nessuna parte, non avevo pensato a fare un'induzione sulle immagini della funzione!
$ x^2 + (y - \sqrt {|x|} )^2 = 2 $

Avatar utente
Troleito br00tal
Messaggi: 679
Iscritto il: 16 mag 2012, 22:25

Re: La funzionale che risolleverà il forum

Messaggio da Troleito br00tal » 22 mag 2015, 16:30

Talete ha scritto: Ora dunque $f(\phi(n))$ può per ipotesi induttiva variare su tutti gli elementi di tutti gli insiemi $A_i$ per $i$ da $1$ a $\phi(n)$: quindi $f(n)$ può variare su tutti gli elementi $z$ con $\phi(z)\le\phi(n)$.
Non ho del tutto capito: perché?

@erFuricksen: quello che dici funziona, non sono troppo sicuro del Lemma. Ora prova con $c$ reale :D

Avatar utente
Troleito br00tal
Messaggi: 679
Iscritto il: 16 mag 2012, 22:25

Re: La funzionale che risolleverà il forum

Messaggio da Troleito br00tal » 22 mag 2015, 16:34

@Talete:

Ad esempio dal tuo ragionamento avrei che $f(2)=2$ va bene, come $f(4)=6$, ma allora non andrebbe bene $f(5)=18$ (difatti $\phi(18) > 4$). Però questi valori localmente soddisfano tutti i requisiti dell'ipotesi (e per me volendo si potrebbe costruire una funzione in cui questi valori funzionano...).

Comunque l'idea di lavorare sulle immagini è ottima, anche se mi sa che non ti basta il semplice bound formato da $A_1,...,A_{\phi(x)}$ ;)

Avatar utente
gpzes
Messaggi: 172
Iscritto il: 01 gen 1970, 01:00

Re: La funzionale che risolleverà il forum

Messaggio da gpzes » 23 mag 2015, 10:27

Sapevo del classico $\frac{1}{2}\sqrt{n}\le \varphi \left( n \right)\le n$ …ma anche $\varphi(2)=1$..
$\varphi(5186)=\varphi(5187)=\varphi(5188)$...
se c è reale non saprei…la sparo grossa, magari qualcosa simile al famoso $\frac{{{\pi }^{2}}}{6}$ ?? :oops: :oops:

Sicuramente cancellerò post :lol: :wink:

Avatar utente
<enigma>
Messaggi: 873
Iscritto il: 24 set 2009, 16:44

Re: La funzionale che risolleverà il forum

Messaggio da <enigma> » 23 mag 2015, 11:26

$f(3)=6$ non esclude $c=1$ perché la disuguaglianza del testo non è stretta. Anzi, visto che questo è uno dei casi in cui il rasoio di Occam funziona, non dovrebbe esserci molto mistero sul valore di $c$...
PS. dov'è l'own?!
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)

EvaristeG
Site Admin
Messaggi: 4506
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: La funzionale che risolleverà il forum

Messaggio da EvaristeG » 23 mag 2015, 14:42

<enigma> ha scritto: PS. dov'è l'own?!
Sono caduto in cespugli di ortiche più simpatici.

Ok, tu conoscevi già l'esercizio, probabilmente qualcuno si sarà già posto questa domanda e, se era un matematico di professione, ci ha speculato e poi ci ha pubblicato. Magari c'ha pure un nome. E sticazzi, non ce lo metti?

Avatar utente
<enigma>
Messaggi: 873
Iscritto il: 24 set 2009, 16:44

Re: La funzionale che risolleverà il forum

Messaggio da <enigma> » 23 mag 2015, 15:19

EvaristeG ha scritto:Ok, tu conoscevi già l'esercizio, probabilmente qualcuno si sarà già posto questa domanda e, se era un matematico di professione, ci ha speculato e poi ci ha pubblicato. Magari c'ha pure un nome. E sticazzi, non ce lo metti?
No, non lo conoscevo, e non so da dove arrivi o se qualcuno ci abbia pubblicato qualcosa su. Per me un problema own è un problema molto difficile che richiede diverso tempo per essere risolto; visto che sul forum è durato la bellezza di un paio di giorni, o ho ragione io e oggettivamente non è own, o la definizione che uso è sbagliata. Ma visto che era un commento in calce a un'osservazione sul problema direi non valga la pena discettare su frivolezze come la definizione che ciascuno ha di problema "own".

Per non uscire dal seminato, consiglio ai baldi solutori di mostrare che per ogni $\varepsilon,C>0$, si ha $\varphi(n)/n^{1-\varepsilon}>C$ per tutti gli $n$ abbastanza grandi. :wink:
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)

EvaristeG
Site Admin
Messaggi: 4506
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: La funzionale che risolleverà il forum

Messaggio da EvaristeG » 23 mag 2015, 18:39

"Own" vuol dire "proprio" e si riferisce alla provenienza. Se il problema lo ha inventato chi lo sta postando, di solito ci scrive own, per dire che non viene da gare, libri, siti e quindi potrebbe essere arduo involontariamente (avendo ad esempio il postante una soluzione errata) non essendoci alcuna fonte ufficiale da cui trarre la soluzione.

In quale modo contorto la parola "own" potrebbe entrarci con difficoltà e, peggio ancora, tempo medio di vita?

Avatar utente
<enigma>
Messaggi: 873
Iscritto il: 24 set 2009, 16:44

Re: La funzionale che risolleverà il forum

Messaggio da <enigma> » 23 mag 2015, 19:47

Devo ammettere che forse è che mi sono sempre autocensurato sui problemi che inventavo, evitando di postare quelli che mi prendessero meno di una settimana per essere risolti, e nella mia testa un problema con specificato "own" è per forza molto difficile mentre di per sé non è in effetti necessariamente così, sorry.
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 7 ospiti