$x_m$ termina con molti zeri - parte 2.

[jordan]

Own. Sia definito un polinomio $p(x_1,x_2,\ldots,x_k)$ in $k$ variabili a coefficienti interi, dove $k$ è un intero positivo fissato. Definiamo ora la successione \[ y_{n+k+1}=p(y_{n+1},y_{n+2},\ldots,y_{n+k}) \]
per ogni $n\ge 1$, dove $y_1,y_2,\ldots,y_k$ sono degli interi fissati.



1) Dimostrare che, per ogni intero $m\ge 2$, esiste un intero $f(m)\ge 2$ e un intero $0\le g(m)\le f(m)-1$ tale che
\[ m \mid \text{gcd}\left( y_{i+1}-y_{f(m)+i+1}, y_{i+2}-y_{f(m)+i+2}, \ldots, y_{i+k}-y_{f(m)+i+k}\right) \]
per ogni $i \ge g(m)$, cioè che la successione è definitivamente periodica modulo $m$.

2) Dimostrare che se $p$ è lineare in tutte le variabili allora possiamo porre $g(m)=0$.

3) Dimostrare che possiamo scegliere $f(m)$ di modo tale che \[ f(m) \le m^k+m \]

[Simo_the_wolf]

Penso che ti serva l'invertibilità nella prima variabile, altrimenti se prendi come esempio $k=1$ e $p(x)=x^2$ allora la tua successione diventa $y_{n+1}=y_n^2$ che però modulo $8$ ad esempio se parti con $y_1=3$ poi sei costantemente $1$ e quindi non potrà mai essere che $8|y_1-y_{1+k}$ con $k>0$, giusto?

[jordan]

Si hai ragione Simo; puo' andare adesso? Non capisco cosa intendi esattamente con "invertibilità nella prima variabile"

[Simo_the_wolf]

ok direi che ora è vero! quello che dicevo è che se puoi scrivere anche $x_{n+1}=q(x_{n+k+1},x_{n+k}, \ldots , x_{n+2})$ allora vale come l'avevi scritto tu, ad esempio nel caso in cui $x_{n+k+1}=x_{n+1} + \tilde{p} ( x_{n+2} , x_{n+3}, \ldots , x_{n+k} )$. Un'altra osservazione che però non sono sicuro che serva, è che i polinomi devono essere a coefficienti interi. Forse possono anche non esserlo, e mandare interi in interi, però il bound sale.

[Gottinger95]

1) Visto le \(k\)-uple modulo \(m\) (domanda di notazione: l'insieme corrispondente come si scrive, così \(\mathbb{Z}^k/m\mathbb{Z}^k\) ?) sono in numero finito e gli elementi della serie infiniti, una \(k\)-upla prima o poi (cioè dopo \(f(m)\)) si ripeterà, e da lì, vista la ricorrenza, i numeri modulo \(m\) si ripeteranno uguali.

2) Visto che \(p\) è lineare, è anche bigettivo su \(\mathbb{Z}^k/m\mathbb{Z}^k\) (domanda: va dimostrato?). Sia per comodità \(Y_i = (y_i, \ldots, y_{i+k})\), e definiamo \(Y_{n+1} =\Theta(Y_n)\) tale che \(\Theta(Y_n) = \Theta(y_{n+1}, \ldots, y_{n+k}) = (y_{n+2}, \ldots, y_{n+k}, p(Y_n))\). Dalla bigettività di \(p\) discende anche la bigettività di \(\Theta\).

Visto che la successione è periodica, esistono \(j,h\) tali che \( Y_j = Y_h\), con \(j>h \geq 1\). Scriviamo \(Y_j = \Theta^{j-1}(Y_1)\) e \(Y_h = \Theta^{h-1}(Y_1)\):
\( Y_j = Y_h \ \ \ \ \Rightarrow\ \ \ \ \Theta^{j-1}(Y_1) = \Theta^{h-1}(Y_1)\)
Dal momento che \(\Theta\) è bigettiva, esiste anche \(\Theta^{-1}\). La applichiamo \(h-1\) volte ad entrambi i membri e otteniamo:
\(\Theta^{j-h}(Y_1) = Y_1\),
Questo significa che il primo elemento a ripetersi è proprio \(Y_1\) \(\ \ \Rightarrow\ \ \) \(g(m)=0\).

3) Senza saper nè leggere nè scrivere, potrebbe accadere che la nostra signora successione decida di provare tutte le \(k\)-uple in \(\mathbb{Z}^k/m\mathbb{Z}^k\) prima di tornarsene su una già fatta. Il numero di modi di scegliere una \(k\)-upla con \(m\) elementi a disposizione è \(m^k\); per pidgeonhole, se ne prendo \(m^k+1\) per forza una se ne deve ripetere. Per ipotesi \(Y_{g(m)+1}\) è il primo elemento a ripetersi, perciò si avrà al massimo \(Y_{m^k+g(m)+1} = Y_{g(m)+1}\), ossia \(f(m) \leq m^k\).

Dove sbaglio? Quel \(+\ m\) proprio non mi esce fuori!