Esponenziale Tosta

[FrancescoVeneziano]

Era proprio tosta
Entrambe le dimostrazioni che conosco (che in effetti sono filosoficamente la stessa) arrivano a quella che hai scritto anche tu
$ \omega^n=a\pm \omega$
con $a$ intero.

Questa, vogliamo abbatterla a colpi di congruenze, che non promette bene perché di soluzioni ce ne sono, e anche non tanto banali (n=13). Quando ci sono di mezzo equazioni esponenziali, la speranza è di prendere congruenze modulo cose piuttosto grandi, fare in modo che le quantità in gioco diventino periodiche ad un certo punto, ma le soluzioni si trovino tutte nell'antiperiodo. (Spero di essermi spiegato. Esempio idiota: $2^n=8x+4$, modulo potenze di 2 si conclude).

Uno può lanciarsi in ardite congruenze già qui, con la complicazione di trovarci in $\mathbb{Z}[\omega]$, e finire per fare più o meno quello che ti era venuto in mente a scuola, come fa Nagell; oppure si può andare "al piano di sotto" con la successione $b_n$ che hai definito.
Per vedere che $b_n$ vale $\pm 1$ solo in quei casi lì, proviamo a costringere n in varie sottosuccessioni, fino a raggiungere un assurdo; a quel punto gli unici casi possibili saranno solo quei pochi casi "bassi" che ci eravamo lasciati da parte da fare a mano nel procedere della dimostrazione.

Primo passo: come si comporta $b_n$ modulo 16 ?

Visto che puntiamo a studiare $b_n$ quando n è in particolari sottosuccessioni, è utile ricavarci qualche formula per cose come $b_{nk}$, $b_{nk+1}$.
Si possono ricavare, per esempio, da $\omega^n=b_{n+1}-b_n \bar \omega$ elevando alla $k$ e sviluppando il binomio sulla destra, e poi liberandoci delle $\omega$ per rimanere con una complicata espressione per ricorrenza sugli interi che esprima $b_{nk+1}$ in termini di $b_n$, $b_{n+1}$ e i $b_j$ fino a $k$.

Buon lavoro.

[dario2994]

Qualche vago passo avanti ottenuto oggi a scuola:
-7 è residuo quadratico mod $2^k$: si dimostra facile... ad esempio con lifting the exponent.
Quindi $\omega$ è proprio un numero modulo $2^k$, senza la necessita di aggiungere nulla. Allora anche $\bar{\omega}$. Inoltre $\omega\cdot\bar{\omega}=2$ e perciò uno ha valutazione 2-adica esattamente 1, l'altro è dispari. Questo aiuta parecchio:
Prendo $n\ge k$ e assumo WLOG $\bar{\omega}$ pari:
$\displaystyle b_n\cdot \sqrt{-7}=\omega^n-\bar{\omega}^n\equiv \omega^n\pmod{2^k}$
E dato che $\sqrt{-7}$ è dispari, quindi invertibile ottengo che la sequenza dei $b_i$ modulo $2^k$ ha come antiperiodo $b_0,b_1,b_2,\dots b_{k-1}$ (dato che la valutazione 2-adica di $\bar{\omega}$ è esattamente 1 l'antiperiodo è tutto) e poi parte il periodo in cui la sequenza si comporta come le potenze di $\omega$.
Insomma bisogna sperare che le soluzioni di $\omega^n\equiv \pm \sqrt{-7}$ siano o minori di $k$ oppure abbastanza alte... Continuerò poi se riesco

[FrancescoVeneziano]

Hmm, parlavo delle complicazioni di trovarci in $\mathbb{Z}[\omega]$.
2 non è primo lì, si fattorizza proprio come $\omega\bar\omega$, quindi non puoi parlare di valutazione 2-adica o dire che uno dei due è "dispari": sono entrambi "un po'" pari, ma in modo diverso (piccola osservazione: i ruoli di $\omega$ e del suo coniugato devono essere assolutamente simmetrici, quindi che uno fosse pari e l'altro dispari stonava un po').

Io ti direi di pensare ai $b_n$. Ricava quella formula ricorsiva per $b_{nk+1}$ e comincia a fare considerazioni di congruenze per vedere quando $b_n$ può essere $\pm1$.
Il primo passo è guardare modulo 16.

[Mist]

Ok, mi sento un perfetto bifolco a chiederlo, ma cosa significa "un po' pari" ? In che senso ? Non è una domanda stizzita, sia chiaro

[dario2994]

Hmm, parlavo delle complicazioni di trovarci in $\mathbb{Z}[\omega]$.
2 non è primo lì, si fattorizza proprio come $\omega\bar\omega$, quindi non puoi parlare di valutazione 2-adica o dire che uno dei due è "dispari": sono entrambi "un po'" pari, ma in modo diverso (piccola osservazione: i ruoli di $\omega$ e del suo coniugato devono essere assolutamente simmetrici, quindi che uno fosse pari e l'altro dispari stonava un po').

Io ti direi di pensare ai $b_n$. Ricava quella formula ricorsiva per $b_{nk+1}$ e comincia a fare considerazioni di congruenze per vedere quando $b_n$ può essere $\pm1$.
Il primo passo è guardare modulo 16.

Sìsì ma quella roba centrava poco con gli hint... ho semplicemente guardato come si comportava $b_n$ modulo potenza di 2 Non sto mica in nessun campo strano sto proprio modulo $2^k$!

[dario2994]

Ok, mi sento un perfetto bifolco a chiederlo, ma cosa significa "un po' pari" ? In che senso ? Non è una domanda stizzita, sia chiaro

Un po' pari in questo caso si intende un po' divisibile per 2... è come dire che 13 è un po' divisibile per 39

[FrancescoVeneziano]

Sìsì ma quella roba centrava poco con gli hint... ho semplicemente guardato come si comportava $b_n$ modulo potenza di 2 Non sto mica in nessun campo strano sto proprio modulo $2^k$!

Hmm, ok ma cerca di fare attenzione ed avere sempre chiaro quello che stai facendo. Va bene che sei modulo $2^k$, ma quando guardi le congruenze di $\omega$, sei in $\mathbb{Z}[\omega]/2^k \mathbb{Z}[\omega]$, non in $\mathbb{Z}/2^k\mathbb{Z}$.
Quando dici che uno dei due ha valutazione due e l'altro è dispari è proprio sbagliato (non puoi parlare di valutazione 2-adica più di quanto tu non possa parlare di valutazione 10-adica), e quindi anche che ${\bar\omega}^n\equiv 0 \pmod 2^k$ quando $n\geq k$; il punto è che 2 non è più primo e per il teorema cinese $\mathbb{Z}[\omega]/2^k \mathbb{Z}[\omega] \simeq \mathbb{Z}[\omega]/\omega^k \mathbb{Z}[\omega] \times \mathbb{Z}[\omega]/{\bar\omega}^k \mathbb{Z}[\omega]$.

Spero che tutto ciò non ti stia solo confondendo...

[dario2994]

Un po' sono confuso... credevo di avere chiarissimo quello che scrivevo!
Riprovo a dirlo: io prendo un numero $\alpha$ tale che $\alpha^2\equiv -7\pmod{2^k}$. E questo esiste proprio negli interi!
Dopodichè chiamo $\omega=\frac{-1+\alpha}{2}$ e il coniugato come ovvio, e qui sto ancora negli interi!
E sempre rimanendo negli interi ottengo che $\omega\cdot \bar{\omega}$ ha valutazione esattamente 2! Poi passo solo $\pmod{2^k}$ senza far atro.

Non mi ero spiegato o c'è proprio una confusione mia che non capisco?

[Mist]

Chiedo scusa se interrompo ancora questa interessantissima conversazione ma volevo chiedervi dove posso imparare queste cose che state usando, almeno le basi... C'è qualche lezione del senior ? O se mi linkate qualche dispensa mi fate un favorone

[FrancescoVeneziano]

Un po' sono confuso... credevo di avere chiarissimo quello che scrivevo!
Riprovo a dirlo: io prendo un numero $\alpha$ tale che $\alpha^2\equiv -7\pmod{2^k}$. E questo esiste proprio negli interi!
Dopodiché chiamo $\omega=\frac{-1+\alpha}{2}$ e il coniugato come ovvio, e qui sto ancora negli interi!
E sempre rimanendo negli interi ottengo che $\omega\cdot \bar{\omega}$ ha valutazione esattamente 2! Poi passo solo $\pmod{2^k}$ senza far atro.

Non mi ero spiegato o c'è proprio una confusione mia che non capisco?

Temo sia una confusione tua.
Guardiamo un caso particolare, che aiuta sempre a capire. Per esempio, $k=3$.

Come dici, risolvi $\alpha^2\equiv -7 \pmod 8$ negli interi, e trovi delle soluzioni, precisamente, quattro soluzioni modulo 8 ($1,3,5,7\pmod 8$).

Adesso crei il tuo surrogato di $\omega$ ( e per farlo dividi anche per due, che non promette certo bene...) comunque, ti ritrovi con quattro classi di resto modulo 4 (hai diviso per 2, perdi un fattore due anche nel modulo), per la precisione "$\omega$"=$1,2,3,0\pmod 4$, che sono tutte le classi di resto modulo 4 ‽
Quindi non è questo quello che vuoi fare. Facciamo un'altra cosa, guardiamo le radici di $x^2-x+2$ modulo 8. Sono il numero giusto, per la precisione sono 3 e -2, ma attenzione, questo NON vuol dire che $\omega$ e $\bar\omega$ sono congrui a 3 e -2 modulo 8 (nell'unico posto dove questo a senso, cioè $\mathbb{Z}[\omega]/8\mathbb{Z}[\omega]$, infatti le differenze sono $\omega-3={\bar\omega}^3$ e $\omega+2=\omega^3$, che NON sono multiple di 8.
Qual è il tuo problema? Stai confondendo le radici di $x^2-x+2$ in $\bar{\mathbb{Q}}$, che abbiamo chiamato $\omega$ e $\bar\omega$, con le radici di quel polinomio in $\mathbb{Q}_2$; è chiaro che sono imparentate, ma non fanno quello che vuoi tu; se con $\omega$ e $\bar\omega$ intendi i numeri complessi $\frac{1\pm\sqrt{-7}}{2}$, le congruenze che hai scritto sono false.

[dario2994]

Riprovo a spiegarlo perchè sono ancora convinto che sia giusto, anche se avendo dato tanto per scontato mi ero perso qualche pezzo (come ad esempio un paio di fattori 2 ):
Allora prendo un numero intero $\alpha$ tale che $2^{k+2}|\alpha^2+7$ e inoltre $\frac{-1+\alpha}{2}$ è dispari. Chiamo $\omega=\frac{-1+\alpha}{2}$ e $\bar{\omega}=\frac{-1-\alpha}{2}$.
Vorrei mostrare che $b_n\equiv \frac{\omega^n-\bar{\omega}^n}{\alpha}\pmod{2^k}$ (in effetti prima chiedevo un paio di fattori 2 di troppo)
E questo sono certo che sia vero perchè mi sono messo proprio a dimostrarlo! $b_0,b_1$ tornano e poi l'induzione viene perchè $\omega,\bar{\omega}$ sono effettivamente radici di $x^2+x+2$ modulo $2^k$.
Mi sa che non ero stato chiaro perchè non avevo fatto ben capire che $\alpha$ doveva restare lo stesso, lo scelgo all'inizio e tale rimane!
In particolare per la scelta di $\alpha$ vale $\upsilon_2(\bar{\omega})=1$ e perciò l'addendo $\bar{\omega}^n$ scompare per $n\ge k$ e ottengo in questo caso: $b_n\equiv \alpha^{-1}\omega^n\pmod{2^k}$.

Poi ho dimostrato or ora che l'ordine di $\omega$ è sempre $2^{k-2}$ quindi, anche se probabilmente non servirà a nulla nella dimostrazione, la sequenza $b_i$ ha antiperiodo lungo $k$ e periodo lungo $2^{k-2}$ (per dimostrare il fatto dell'ordine basta capire come si costruisce $\alpha$ per $2^{k+1}$ avendo quello per $2^k$)

p.s. comunque dopo questa leggera digressione... oggi provo a usare l'hint che hai dato

[FrancescoVeneziano]

Metà del problema era che nei miei conti $\omega=\frac{1+\sqrt{-7}}{2}$, cioè il tuo $-\bar\omega$, e non mi tornava più nulla…

Chiamo $\omega=\frac{-1+\alpha}{2}$ e $\bar{\omega}=\frac{-1-\alpha}{2}$.

Questo non mi piace per ragioni di chiarezza. Visto che si tratta di cose diverse, riserva $\omega,\bar\omega$ per i due numeri complessi (o al massimo per le *loro* riduzioni), e chiama, per esempio $\beta,\bar\beta$ questi interi che hai definito. E osserva che ci sono due scelte per $\alpha$, che corrispondono alle due mappe da $\mathbb{Q}(\omega)\to\mathbb{Q}_2$, o alle due estensioni di $\upsilon_2$ a $\mathbb{Q}(\omega)$, e risolvono l'ambiguità sul perché una ti venga pari e l'altra dispari.
La cosa che osservavo è che non è vero che $\beta,\bar\beta\equiv \omega,\bar\omega$ in $\mathbb{Z}[\omega]/2^k \mathbb{Z}[\omega]$.

p.s. comunque dopo questa leggera digressione... oggi provo a usare l'hint che hai dato

Vanno benissimo le digressioni, se aiutano a chiarirsi le idee. Non sono sicurissimo di quanto tutto ciò vi giovi.

[FrancescoVeneziano]

Chiedo scusa se interrompo ancora questa interessantissima conversazione ma volevo chiedervi dove posso imparare queste cose che state usando, almeno le basi... C'è qualche lezione del senior ? O se mi linkate qualche dispensa mi fate un favorone

Eh, in realtà non lo so. Quando me ne occupavo io queste cose ancora non si facevano. Se ci sono delle lezioni del senior guarda quelle, ma altrimenti ti consiglierei di aspettare di essere all'università prima di lanciarti nella teoria algebrica dei numeri; se uno si specializza in analisi, per esempio, può arrivare ad una laurea specialistica in matematica e non riuscire a seguire questa conversazione.

[dario2994]

Uhm... di sicuro piever ha fatto una lezione circa su queste cose al senior 2010, Ludovico insieme a Darkcrystal (che forse non si scrive così) ne hanno fatta un'altra nel 2011.
Quella di piever era ad un livello delirante e faceva di tutto, con tanto di esercizi applicazioni e dimostrazioni di tutto. Quella di quest'anno è molto più seguibile (o forse io ne sapevo di più) ma tratta roba un po' diversa ed è più teorica che applicata: espone i campi finiti con tutti i teoremi vari ma senza molte dimostrazioni.
Quella di piever mi pare passasse sia per i campi finiti sia per le estensioni degli interi o dei razionali... e ricordo che la prima mezzora/un'ora era completamente incapibile
Poi anche qui sul forum è stato aperto un thread chiamato "congruenze plus" in cui ci sta un po' di roba... non ricordo altro.

[dario2994]

Ok credo di averla risolta Ma la soluzione non è certo delle più belle, serve un pc, e non ho seguito gli hint ma ho usato solo la digressione
Intanto già modulo 16 si vede che non si sono soluzioni a $b_n=1$ per $n>1$.
Allora... analizzando modulo $2^{14}$ ottengo che per $n>13$ $b_n\equiv -1\pmod{2^{14}}\iff n\equiv 2061\pmod{2^{12}}$
Poi analizzo modulo $40961$ e ottengo che se $n\equiv 2061\pmod{2^{12}}\to b_n\not\equiv -1\pmod{40961}$.
Bon intanto per analizzare modulo $2^{14}$ basta controllare fino a $b_{2^{12}+13}$ per quanto detto prima su $b_i$ modulo potenza di 2. E viene che vale $-1$ solo in $0,2,3,5,13$ che sono nell'antiperiodo e in $2061$.
Invece modulo $40961$ (che è primo tale che $2^{12}|40961-1$) basta analizzare fino a $40960$ perchè quello è un multiplo del periodo dato che $\left(\frac{-7}{40961}\right)=1$ (i $b_i$ non hanno antiperiodo) e esce che vale -1 solo per $n\equiv 0,2,3,5,13,20481\pmod{40960}$ e nessuno di questi rispetta $n\equiv 2061\pmod{4096}$ e perciò non ci sono soluzioni per $n>13$

Bon se qualcuno mi conferma che è giusta (con l'ausilio di un pc!) la posto tutta la soluzione in un unico post, magari spiegando anche un poco di più