[L07] $n$-fold application 2.0

Numeri interi, divisibilità, primalità, ed equazioni a valori interi.

[L07] $n$-fold application 2.0

Messaggioda Federico II » 09/12/2016, 23:55

Sia $f:\mathbb{Z^+}\rightarrow\mathbb{Z^+}$ una funzione tale che $$\frac{f^n(m)-m}{n}$$ è un intero positivo per ogni $m,n\in\mathbb{Z^+}$. Supponendo che esista al più un numero finito di interi positivi che non fanno parte dell'immagine di $f$, dimostrare che la sequenza $f(1)-1,f(2)-2,f(3)-3,\ldots$ è periodica. Con $f^n(m)$ si intende l'iterata $n$-esima di $f$ calcolata in $m$.
Il responsabile della sala seminari
Avatar utente
Federico II
 
Messaggi: 449
Iscritto il: 14/05/2014, 14:53

Re: [L07] $n$-fold application 2.0

Messaggioda cip999 » 11/12/2016, 23:37

Testo nascosto:
Prima un po' di cose base.

Fatto 1. Per ogni intero positivo $m$, $f(m) > m$.
Dimostrazione. $n = 1$ nel testo.

Fatto 2. $f$ è iniettiva.
Dimostrazione. Supponiamo che per $a < b$ si abbia $f(a) = f(b)$. Sia $n = b - a + 1$. Allora $n \mid f^n(a) - a$ e $n \mid f^n(b) - b$, ma $f^n(a) = f^n(b)$ quindi $n \mid f^n(a) - a - (f^n(b) - b) = b - a$, evidentemente assurdo.

Fatto 3. Per ogni $m, \: n \in \mathbb{Z}^+$, vale $f(m) - m \equiv f^{n + 1}(m) - f^n(m) \pmod{n}$.
Dimostrazione. Abbiamo $m \equiv f^n(m)$ e $f(m) \equiv f^n(f(m)) = f^{n + 1}(m) \pmod{n}$, da cui $f(m) - m \equiv f^{n + 1}(m) - f^n(m) \pmod{n}$.

Ora le immancabili ***definizioni***!

Definizione 1. Fissato $a \in \mathbb{Z}^+ \setminus \text{Im} \: f$, chiamiamo catena di $a$ l'insieme $$C_a = \{f^n(a): \: n \in \mathbb{N}\}$$ (dove $f^0(m) = m$).
Corollari. Poiché le catene sono in ovvia bigezione con gli interi positivi che non stanno nell'immagine di $f$, le catene sono in numero finito. Inoltre, dal Fatto 2 segue banalmente che le catene sono a due a due disgiunte, ossia ogni intero positivo appartiene a una e una sola catena.

Definizione 2. Diciamo che la catena $C$ è limitata se l'insieme $\{f(m) - m: \: m \in C\}$ è limitato superiormente. Definiamo invece stabile una catena $C$ se esiste un intero positivo $r$ tale che $f(m) - m = r$ per ogni $m \in C$; in tal caso, chiameremo $r$ la ragione di $C$.

E adesso passiamo alle cose serie.

Lemma 1. $C$ è una catena. Se $C$ è limitata, allora è anche stabile.
Dimostrazione. Sia $\displaystyle D = \max_{m \in C} \{f(m) - m\}$ (esiste!) e $m_0 \in C$ tale che $f(m_0) - m_0 = D$. Ora, per ogni $n \ge D$, per il Fatto 3 vale $$f^{n + 1}(m_0) - f^n(m_0) \equiv f(m_0) - m_0 = D \pmod{n}$$ e quindi, dato che $n \ge D$, $f^{n + 1}(m_0) - f^n(m_0) \ge D \implies f^{n + 1}(m_0) - f^n(m_0) = D$. Dunque $C$ è definitivamente stabile.
Ora sia $m_1$ tale che $f(m) - m = D$ per ogni $m_1 \le m \in C$, e supponiamo esista $m' \in C$ per cui $f(m') - m' < D$. Allora scegliamo $n \ge D$ tale che $f^n(m') \ge m_1$. Allora sempre per il Fatto 3 $f(m') - m' \equiv f^{n + 1}(m') - f^n(m')$, ma per quanto appena dimostrato $f^{n + 1}(m') - f^n(m') = D$, quindi $n \mid D - (f(m') - m')$ e questo è assurdo perché $n \ge D > D - (f(m') - m')$.

Lemma 2. Tutte le catene sono limitate (e quindi, per il Lemma 1, anche stabili).
Dimostrazione. Sia $s$ il numero di catene e supponiamo, per assurdo, che $k < s$ di queste siano limitate/stabili e le restanti $s - k$ no. Dette $r_1, \: r_2, \: \dots, \: r_k$ le ragioni delle $k$ catene stabili, poniamo $t = r_1r_2\cdots r_k$. Allora abbiamo una "periodicità parziale" di periodo $t$, cioè: se $m$ appartiene a una delle $k$ catene stabili (diciamo la $j$-esima), allora $f(m) - m = f(m + t) - (m + t) = r_j$ (questo perché, essendo $t$ multiplo di $r_j$, anche $m + t$ appartiene a tale catena). Adesso si dimostra (ma in realtà è circa ovvio, quindi non lo sto a giustificare) che esiste un intero positivo $h$ tale che, per infiniti interi positivi $a$, tra i numeri $a + 1, \: a + 2, \: \dots, \: a + ht$ ce ne sono almeno $s - k + 1$ che appartengono a una delle catene non limitate (non necessariamente la stessa per tutti). Ma allora, tra questi numeri, ce ne sono almeno $2$ che appartengono alla stessa catena non limitata, e quindi possiamo trovare interi $m$ grandi a piacere tali che $m$ appartiene a una catena non limitata e $f(m) - m < ht$.
D'altra parte, se $C$ è una catena non limitata, allora esiste un $m_2 \in C$ tale che $f(m_2) - m_2 = d \ge ht$. Per ogni $n \ge d$ abbiamo $$d = f(m_2) - m_2 \equiv f^{n + 1}(m_2) - f^n(m_2) \pmod{n}$$ e, poiché $n \ge d$, questo implica $f^{n + 1}(m_2) - f^n(m_2) \ge d$. Dunque esiste un $m_3$ tale che, per ogni catena non limitata $C$ e per ogni $m_3 \le m \in C$, $f(m) - m \ge d \ge ht$, e questo contraddice quanto detto sopra.

A questo punto abbiamo praticamente finito, perché abbiamo dimostrato che le $s$ catene sono tutte stabili. Dette quindi $r_1, \: r_2, \: \dots, \: r_s$ le loro ragioni e posto $T = r_1r_2\cdots r_s$, la successione $f(1) - 1, \: f(2) - 2, \: \dots$ è periodica di periodo $T$. Questo perché, se $m$ è un intero positivo che appartiene alla catena $j$-esima, vale $$m + T = f(m) + (T - r_j) = f^2(m) + (T - 2r_j) = \cdots = f^{T/r_j}(m)$$ quindi anche $m + T$ appartiene a quella stessa catena, e quindi banalmente $$f(m + T) - (m + T) = f(m) - m = r_j$$
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 584
Iscritto il: 26/02/2014, 16:47

Re: [L07] $n$-fold application 2.0

Messaggioda Federico II » 12/12/2016, 17:35

Sì è (abbastanza) giusta.
Ma anche tu le hai chiamate catene?
Il responsabile della sala seminari
Avatar utente
Federico II
 
Messaggi: 449
Iscritto il: 14/05/2014, 14:53

Re: [L07] $n$-fold application 2.0

Messaggioda cip999 » 12/12/2016, 20:10

Sì sì lo so, ci sono delle parti in cui bisogna andare un po' a interpretazione, e probabilmente alcune cose che ho scritto sono false (ma stanno a significare cose vere che si riescono a intuire con un po' di buonsenso).

Federico II ha scritto:Ma anche tu le hai chiamate catene?

Evidentemente è il modo più sensato di chiamarle... :mrgreen:
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 584
Iscritto il: 26/02/2014, 16:47

Re: [L07] $n$-fold application 2.0

Messaggioda bern1-16-4-13 » 29/12/2016, 13:41

Via posto anche la mia soluzione, non so quanto sarà simile a quella di Cip..
Testo nascosto:
Innanzitutto notiamo che $f$ é iniettiva. Infatti se per assurdo esistessero $a,b\in\mathbb{Z}^+:\ \ f\left(a\right)=f\left(a+b\right)$ allora per ipotesi dovremmo avere che $b+1\mid f^{b+1}\left(a\right)-a$ e che $b+1\mid f^{b+1}\left(a+b\right)-a-b=f^{b+1}\left(a\right)-a-b\Rightarrow b+1\mid f^{b+1}\left(a\right)-a+1$ che é assurdo poiché $b+1\ge 2$ non puó dividere due numeri consecutivi.
Definiamo ora catena ogni successione infinita di interi positivi $\left\{a_n\right\}_{n\ge 1}$ tale che $a_1\not\in\text{Im}\left(f\right)$ e $a_{n+1}=f\left(a_n\right)$. La prima cosa da notare é che essendo $\mathbb{Z}^+\setminus\text{Im}\left(f\right)$ un insieme finito, anche le catene dovranno essere in numero finito. Inoltre per l'iniettivitá di $f$ segue subito che le catene sono disgiunte a due a due.

LEMMA 1.0
Data la generica catena $\left\{\alpha_n\right\}$ si ha che la funzione $$g:\ \mathbb{Z}^+\rightarrow\mathbb{Z}^+,\ \ \ g\left(n\right)=\alpha_{n+1}-\alpha_n$$ o é costante da un certo punto in poi, o non é limitata superiormente.
Intanto riscriviamo l'ipotesi del testo del problema in questo modo: per ogni $a<b$ interi positivi si ha che $b-a\mid\sum_{i=a}^{b-1}g\left(i\right)$.
Mostriamo adesso che se $g$ é limitata allora dev'essere costante da un certo punto in poi. Sia $j$ un intero positivo tale che $$g\left(j\right)=k=\max\left\{g\left(i\right)\right\}$$Allora dimostriamo che $g\left(x\right)=k\ \ \forall\ x\ge j+k+1$. Sia quindi $x$ un generico intero $\ge j+k+1$. Allora per l'ipotesi del testo si deve avere che $$x-j\mid\sum_{i=j}^{x-1}g\left(i\right)$$ e che $$x-j\mid\sum_{i=j+1}^{x}g\left(i\right)$$Ma allora $x-j\mid g\left(x\right)-g\left(j\right)=g\left(x\right)-k$. Da qui é evidente che, essendo $g\left(x\right)\ge 1$ e essendo $x-j\ge j+k+1-j=k+1$, $g\left(x\right)\ge k$, ma allora per come abbiamo definito $k$ si deve per forza avere l'uguaglianza.
Come corollario si ha inoltre che se la catena é costantemente uguale a $c$ da un certo punto in poi, allora $c$ é anche il massimo dell'immagine di $g$.
Un altro corollario é che se $g$ non fosse costante da un certo punto in poi allora per ogni intero positivo $u$ esiste $v$ tale che $g\left(n\right)\ge u\ \ \forall\ n\ge v$.

LEMMA 1.1
Se la funzione $g$ relativa alla generica catena $\alpha$ é costante da un certo punto in poi allora dev'essere sempre costante, quindi la catena é una progressione aritmetica. Supponiamo per assurdo che $g\left(n\right)$ sia costantemente uguale a $c$ se $n>t$ e che $g\left(t\right)\ne c$. Per il primo corollario del LEMMA 1.0 si deve quindi avere $g\left(t\right)<c$. Da qui il ragionamento per arrivare all'assurdo é praticamente identico al LEMMA 1.0.

Forti di questi lemmi dimostriamo adesso che $g$ é costante per ogni catena a cui viene applicata. Da qui seguirebbe per ovvi motivi la periodicità chiesta dalla tesi.
Supponiamo per assurdo che esista un insieme $S$ non vuoto di catene le cui $g$ non sono costanti. Allora segue facilmente dal secondo corollario del LEMMA 1.0 che esiste un intervallo $I$ arbitrariamente grande che non contiene nessun elemento delle catene in $S$. Quindi questo intervallo deve essere coperto interamente dagli elementi delle catene che sono progressioni aritmetiche. Ma il "pattern" che le catene in progressione aritmetica creano sulla linea dei numeri dev'essere periodico (con un antiperiodo che arriva fino al piú grande elemento iniziale di una catena in progressione aritmetica), quindi se coprono interamente $I$ che é arbitrariamente grande allora devono coprire tutti gli interi positivi (tranne eventualmente gli elementi dell'antiperiodo, che sono peró in numero finito). Assurdo perché in questo modo le catene "divergenti" devono per forza avere elementi in comune con le catene in progressione aritmetica.
mentre il mondo persiste nei suoi sanguinosi conflitti, la vera guerra è combattuta dai matematici
bern1-16-4-13
 
Messaggi: 179
Iscritto il: 27/11/2014, 22:10
Località: Firenze

Re: [L07] $n$-fold application 2.0

Messaggioda Federico II » 01/01/2017, 3:09

Sì dovrebbe andare.
Il responsabile della sala seminari
Avatar utente
Federico II
 
Messaggi: 449
Iscritto il: 14/05/2014, 14:53


Torna a Teoria dei Numeri

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti