[L06] n-fold application

[Veritasium]

Sia [tex]p(x)[/tex] un polinomio non costante a coefficienti interi. Dimostrare che non esiste alcuna funzione [tex]T : \mathbb Z \longrightarrow \mathbb Z[/tex] tale che il numero di soluzioni intere [tex]x[/tex] dell'equazione [tex]T^n(x) = x[/tex] sia uguale a [tex]p(n)[/tex] per [tex]n[/tex] intero positivo.
[tex]T^n(x)[/tex] è definita come [tex]T^1(x) = T(x)[/tex] e [tex]T^{n+1}(x) = T(T^n(x)).[/tex]

[Ale99]

Bello bello !

Testo nascosto:

Supponiamo per assurdo esiste una tale funzione, ora introduciamo un po' di notazione :
sia [tex]S_i[/tex] l'insieme delle soluzioni intere di [tex]T_i(x)=x[/tex] che non siano soluzioni di [tex]T_j(x)=x[/tex] per [tex]j<i[/tex]
sia [tex]N_i[/tex] l'insieme delle soluzioni intere di [tex]T_i(x)=x[/tex]

Avremo chiaramente dunque che i vari [tex]S_i[/tex] saranno a due a due disgiunti e che [tex]|N_i|=p(i)[/tex]

Notiamo ora che se [tex]d|i[/tex] allora [tex]N_d \in N_i[/tex]

Consideriamo ora [tex]d,i,r,q[/tex] con [tex]0<r<d[/tex] tali che [tex]i=qd+r[/tex] dimostriamo ora che se [tex]a \in S_d[/tex] allora [tex]a[/tex] non appartiene a [tex]N_i[/tex]
Per la proprietà precedentemente notata avremo che [tex]T_{i=qd+r}(a)=T_r(T_{qd}(a))=T_r(a) \neq a[/tex] in quanto [tex]r<d[/tex] e [tex]a \in S_d[/tex] per ipotesi

Avremo ora dunque che [tex]N_i= \sum_{d|i} S_d[/tex]

Notiamo che se [tex]a \in S_i[/tex] allora [tex]\{a,T(a), \ldots , T_{i-1}(a) \} \in S_i[/tex] dunque [tex]i ||S_i|[/tex] [tex]\forall i \in \mathbb{N}[/tex]

Consideriamo ora [tex]2^nq,2^{n+1}q[/tex] con [tex]n \ge 0[/tex] e [tex]q[/tex] primo :
[tex]p(2^{n+1}q)-p(2^nq)=|N_{2^{n+1}q}|-|N_{2^nq}|= \sum_{d|2^{n+1}q} |S_d| - \sum_{k|2^nq} |S_k| = |S_{2^{n+1}q}|+|S_{2^{n+1}}|[/tex]
per un lemma noto avremo ora che $2^nq=2^{n+1}q-2^nq|p(2^{n+1}q)-p(2^nq)=|S_{2^{n+1}q}|+|S_{2^{n+1}}|$
ma come precedentemente notato $2^nq|2^{n+1}q||S_{2^{n+1}q}|$
dunque abbiamo che [tex]q|2^nq||S_{2^{n+1}}[/tex] per ogni primo $q$ dunque chiaramente $|S_{2^n}|=0$ per ogni scelta di $n$

Avremo dunque che $p(1)=p(2)=\ldots=p(2^n)$ per ogni scelta di $n$ dunque [tex]p(x)[/tex] è costante in infiniti valori dunque è costante, ma per ipotesi $p(x)$ è non costante

Non esiste dunque alcuna siffatta funzione $T(x)$

[Veritasium]

Corretta e pulita! (Un typo, $\le$ al posto di $\ge$)

[Ale99]

Ma da dove viene? Comunque mi è sembrato più facile di L06 hahahahahahah ... comunque ora correggo il typo

[Veritasium]

Nah, è un IMO shortlist N5, è molto tecnico (si conclude anche in inversione di Moebius)

[Ale99]

Ah ottimo, allora mi sento bravo anche se sono scarso ... comunque posti sempre problemi belli, complimenti

[Veritasium]

Ahahah ma va, grazie comunque​