OliForum Matematico

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}^+$.

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

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?

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

Grazie mille!

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$
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

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

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!

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

@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)}$

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}$ ??

Sicuramente cancellerò post

$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?!

<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?

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.

"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?

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.