Trovare radici modulo i primi
Trovare un polinomio [tex]P(x)[/tex] a coefficienti interi senza radici intere ma tale che per ogni primo [tex]p[/tex] il polinomio ridotto modulo [tex]p[/tex] ammetta radici in [tex]\mathbb{Z}/p\mathbb{Z}[/tex].
Domanda bonus: trovare un polinomio con le caratteristiche esposte il cui gruppo di Galois su [tex]\mathbb{Q}[/tex] sia [tex]S_3[/tex].
-------------
Questo è un esercizio ispirato dalla lettura dell'articolo "Polynomials with roots modulo every integer" di Daniel Berend e Yuri Bilu, in cui si può trovare la soluzione ai quesiti che ho posto.
Domanda bonus: trovare un polinomio con le caratteristiche esposte il cui gruppo di Galois su [tex]\mathbb{Q}[/tex] sia [tex]S_3[/tex].
-------------
Questo è un esercizio ispirato dalla lettura dell'articolo "Polynomials with roots modulo every integer" di Daniel Berend e Yuri Bilu, in cui si può trovare la soluzione ai quesiti che ho posto.
Risposte
Purtroppo la Teoria di Galois non l'ho ancora fatta, quindi per la domanda bonus passo, ma per il primo esercizio sono richieste conoscenze particolari?
nemmeno io conosco ancora la teoria di Galois, quindi vado con il numero 1.
io ho provato questa strada:
i numeri primi [tex]p[/tex] sono di tre tipi: [tex]$p=2\ \lor\ p\equiv 1\pmod{4}\ \lor\ p\equiv 3\pmod{4}$[/tex]
io ho trovato un polinomio che rispetta le richieste per quelli delle prime due forme:[tex]$x^2+1$[/tex]
come si può facilmente verificare, conoscendo un po' di proprietà.
quindi sarà [tex]$P(x)=(x^2+1)\cdot g(x)$[/tex] dove [tex]$g(x)$[/tex] è un polinomio, che soddisfa le richieste "soltanto" per i primi della terza forma (che sono infiniti, come quelli della seconda).
io ho provato questa strada:
i numeri primi [tex]p[/tex] sono di tre tipi: [tex]$p=2\ \lor\ p\equiv 1\pmod{4}\ \lor\ p\equiv 3\pmod{4}$[/tex]
io ho trovato un polinomio che rispetta le richieste per quelli delle prime due forme:[tex]$x^2+1$[/tex]
come si può facilmente verificare, conoscendo un po' di proprietà.
quindi sarà [tex]$P(x)=(x^2+1)\cdot g(x)$[/tex] dove [tex]$g(x)$[/tex] è un polinomio, che soddisfa le richieste "soltanto" per i primi della terza forma (che sono infiniti, come quelli della seconda).
Scusate, ma probabilmente non ho capito io una cosa...
Paolo90 devi mettere i quantificatori al posto giusto..
trovare $P(x) in ZZ[x]$ t.c. $AA p in ZZ$ si ha $P(p)=0$
trovare $P(x) in ZZ[x]$ t.c. $AA p in ZZ$ si ha $P(p)=0$
Ah, sì, scusa black. Ho capito adesso.
Grazie.
Grazie.
"mistake89":No, solo un po' di confidenza coi campi [tex]\mathbb{Z}/p\mathbb{Z}[/tex].
Purtroppo la Teoria di Galois non l'ho ancora fatta, quindi per la domanda bonus passo, ma per il primo esercizio sono richieste conoscenze particolari?
@Paolo: questo esercizio è legato al teorema di Chebotarev, di cui ti avevo parlato
ok credo di aver risolto, avevo la soluzione sotto il naso e l'ho vista solo adesso:
una volta capito che i primi [tex]$p$[/tex] sono in una delle tre forme: [tex]$p=2 \lor \ p\equiv1 \pmod{4}\lor \ p\equiv3 \pmod{4}$[/tex]
il polinomio più semplice che soddisfa la richiesta è del tipo [tex]$P(x)=f(x)\cdot g(x)\cdot h(x)$[/tex]
dove [tex]$f(x)$[/tex] si annulla per [tex]$p=2$[/tex]
e [tex]$g(x)$[/tex] si annulla per i [tex]$p\equiv1 \pmod{4}$[/tex] ovvero [tex]$p=1+4k$[/tex]
e [tex]$h(x)$[/tex] si annulla per i [tex]$p\equiv3 \pmod{4}$[/tex] ovvero [tex]$p=3+4k$[/tex]
e ovviamente deve essere che [tex]$P(x)$[/tex] non ha radici intere.
semplicemente, invece di sbattersi come ho fatto prima con residui quadratici e criterio di Eulero, sono ovviamente:
[tex]$g(x)=4x+1\ \text{e}\ h(x)=4x+3$[/tex] in quanto [tex]$k$[/tex] è una classe di [tex]$\mathbb{Z}_p$[/tex]
e poi [tex]$f(x)=x^2+1$[/tex]
quindi paradossalmente la soluzione concettualmente più semplice è proprio: [tex]$P(x)=(x^2+1)(4x+3)(4x+1)$[/tex]
mentre per quello che ho detto nel post precedente una soluzione più corta ma più dispendiosa è [tex]$P(x)=(x^2+1)(4x+3)=4x^3+3x^2+4x+1$[/tex]
una volta capito che i primi [tex]$p$[/tex] sono in una delle tre forme: [tex]$p=2 \lor \ p\equiv1 \pmod{4}\lor \ p\equiv3 \pmod{4}$[/tex]
il polinomio più semplice che soddisfa la richiesta è del tipo [tex]$P(x)=f(x)\cdot g(x)\cdot h(x)$[/tex]
dove [tex]$f(x)$[/tex] si annulla per [tex]$p=2$[/tex]
e [tex]$g(x)$[/tex] si annulla per i [tex]$p\equiv1 \pmod{4}$[/tex] ovvero [tex]$p=1+4k$[/tex]
e [tex]$h(x)$[/tex] si annulla per i [tex]$p\equiv3 \pmod{4}$[/tex] ovvero [tex]$p=3+4k$[/tex]
e ovviamente deve essere che [tex]$P(x)$[/tex] non ha radici intere.
semplicemente, invece di sbattersi come ho fatto prima con residui quadratici e criterio di Eulero, sono ovviamente:
[tex]$g(x)=4x+1\ \text{e}\ h(x)=4x+3$[/tex] in quanto [tex]$k$[/tex] è una classe di [tex]$\mathbb{Z}_p$[/tex]
e poi [tex]$f(x)=x^2+1$[/tex]
quindi paradossalmente la soluzione concettualmente più semplice è proprio: [tex]$P(x)=(x^2+1)(4x+3)(4x+1)$[/tex]
mentre per quello che ho detto nel post precedente una soluzione più corta ma più dispendiosa è [tex]$P(x)=(x^2+1)(4x+3)=4x^3+3x^2+4x+1$[/tex]
"blackbishop13":Hai ragione blackbishop
la soluzione concettualmente più semplice è proprio: [tex]$P(x)=(x^2+1)(4x+3)(4x+1)$[/tex]
Mi sono reso conto di aver proposto una versione "leggera" di quello che volevo proporre. Ora, mettiamola così:
Trovare un polinomio [tex]P(x)[/tex] a coefficienti interi senza radici razionali ma tale che per ogni primo [tex]p[/tex] il polinomio ridotto modulo [tex]p[/tex] ammetta radici in [tex]\mathbb{Z}/p\mathbb{Z}[/tex].
Più divertente così, no?
se è vero che come dice il signor I.N. Herstein: "il valore di un problema non sta tanto nel trovarne la soluzione, quanto nelle idee che fa sorgere in chi lo affronta" , allora questo problema è stato per me illuminante, grazie Martino, pensando a questo quesito ho scoperto cose nuove e compreso fino in fondo cose vecchie.
allora andiamo:
come detto il polinomio [tex]$f(x)=x^2+1$[/tex] soddisfa parte della richiesta, ovvero non ha radici in [tex]$\mathbb{Z}$[/tex] e
[tex]$-1$[/tex] è un residuo quadratico per ogni primo [tex]$p=2\ \lor\ p\equiv1\bmod{4}$[/tex]
non mi metto a dare spiegazioni su questo, diciamo che una ricerca su wikipedia riguardo "simbolo di Legendre" e "criterio di Eulero" lo rende chiaro.
come detto nel post precedente allora sarà [tex]$P(x)=f(x)\cdot g(x)$[/tex]
adesso mi metto a cercare [tex]$g(x)$[/tex] cioè prendo [tex]$p\text{ primo}\ \land\ p\equiv3 \bmod{4}$[/tex]
osserviamo che [tex]$\mathbb{Z}_p^{*}[/tex] ha ordine [tex]$p-1=2+4k$[/tex] per un certo [tex]$k$[/tex]
consideriamo il morfismo [tex]$\phi: \mathbb{Z}_p^{*} \to \mathbb{Z}_p^{*}$[/tex] definito da [tex]$\phi:x \mapsto x^4$[/tex]
siccome [tex]$4\nmid 2+4k$[/tex] avremo la seguente osservazione: [tex]$\nexists\ a \in \mathbb{Z}_p^{*}\ \text{t.c.}\ ord(a)=4$[/tex]
perciò [tex]$Ker(\phi)=\left\{+1,-1\right\}$[/tex].
ora, per il primo teorema di omomorfismo si ha [tex]Imm(\phi)=\mathbb{Z}_p^{*}/{Ker(\phi)}[/tex] che ha [tex]$\frac{p-1}{2}$[/tex] elementi,
e perciò ogni classe ha esattamente due elementi e in particolare osservo che, detta [tex]\bar{a} \in \mathbb{Z}_p^{*}/{Ker(\phi)}[/tex] la classe di [tex]a\in \mathbb{Z}_p^{*}[/tex] si ha che [tex]\bar{a}=\left\{a,-a\right\}[/tex].
quindi il polinomio [tex]$g(x)=\left(x^4+2\right) \cdot \left( x^4-2 \right)=x^8-4$[/tex] soddisfa la richiesta (uso il [tex]$2$[/tex] perchè così non ci sono radici razionali).
quindi ho con fatica trovato [tex]P(x)=\left( x^2+1 \right) \cdot \left( x^8-4 \right)$[/tex]
allora andiamo:
come detto il polinomio [tex]$f(x)=x^2+1$[/tex] soddisfa parte della richiesta, ovvero non ha radici in [tex]$\mathbb{Z}$[/tex] e
[tex]$-1$[/tex] è un residuo quadratico per ogni primo [tex]$p=2\ \lor\ p\equiv1\bmod{4}$[/tex]
non mi metto a dare spiegazioni su questo, diciamo che una ricerca su wikipedia riguardo "simbolo di Legendre" e "criterio di Eulero" lo rende chiaro.
come detto nel post precedente allora sarà [tex]$P(x)=f(x)\cdot g(x)$[/tex]
adesso mi metto a cercare [tex]$g(x)$[/tex] cioè prendo [tex]$p\text{ primo}\ \land\ p\equiv3 \bmod{4}$[/tex]
osserviamo che [tex]$\mathbb{Z}_p^{*}[/tex] ha ordine [tex]$p-1=2+4k$[/tex] per un certo [tex]$k$[/tex]
consideriamo il morfismo [tex]$\phi: \mathbb{Z}_p^{*} \to \mathbb{Z}_p^{*}$[/tex] definito da [tex]$\phi:x \mapsto x^4$[/tex]
siccome [tex]$4\nmid 2+4k$[/tex] avremo la seguente osservazione: [tex]$\nexists\ a \in \mathbb{Z}_p^{*}\ \text{t.c.}\ ord(a)=4$[/tex]
perciò [tex]$Ker(\phi)=\left\{+1,-1\right\}$[/tex].
ora, per il primo teorema di omomorfismo si ha [tex]Imm(\phi)=\mathbb{Z}_p^{*}/{Ker(\phi)}[/tex] che ha [tex]$\frac{p-1}{2}$[/tex] elementi,
e perciò ogni classe ha esattamente due elementi e in particolare osservo che, detta [tex]\bar{a} \in \mathbb{Z}_p^{*}/{Ker(\phi)}[/tex] la classe di [tex]a\in \mathbb{Z}_p^{*}[/tex] si ha che [tex]\bar{a}=\left\{a,-a\right\}[/tex].
quindi il polinomio [tex]$g(x)=\left(x^4+2\right) \cdot \left( x^4-2 \right)=x^8-4$[/tex] soddisfa la richiesta (uso il [tex]$2$[/tex] perchè così non ci sono radici razionali).
quindi ho con fatica trovato [tex]P(x)=\left( x^2+1 \right) \cdot \left( x^8-4 \right)$[/tex]
Bene, blackbishop 
Ora, te la sentiresti di trovare un esempio di grado 6?
Non è difficile, l'idea da usare è la tua: il sottogruppo dei quadrati ha indice 2 in [tex]\mathbb{Z}_p^{\ast}[/tex].
Trovarne uno di grado 5 è un po' più difficile.
Di grado minore di 5 non ne esistono (o sì?). Confermo che non ne esistono.
Ora, te la sentiresti di trovare un esempio di grado 6?
Non è difficile, l'idea da usare è la tua: il sottogruppo dei quadrati ha indice 2 in [tex]\mathbb{Z}_p^{\ast}[/tex].
Trovarne uno di grado 5 è un po' più difficile.
Di grado minore di 5 non ne esistono (o sì?). Confermo che non ne esistono.
ah ma in effetti anche semplicemente [tex]$(x^2+1)(x^2+2)(x^2-2)$[/tex] dovrebbe funzionare nello stesso identico modo no?
di grado 5 si deve usare qualche osservazione elementare come queste ma di diverso tipo o servono cannoni di teoria?
di grado 5 si deve usare qualche osservazione elementare come queste ma di diverso tipo o servono cannoni di teoria?
Già, mi sa che funziona anche [tex](x^2+2)(x^2-2)[/tex]... strano, mi devo ricredere su quello che ho detto prima sul grado minore di 5 (edit: no, vedi intervento successivo). Ti farò sapere sul grado 5.
"Martino":Nessuno mi ha corretto?
Già, mi sa che funziona anche [tex](x^2+2)(x^2-2)[/tex]... strano, mi devo ricredere su quello che ho detto prima sul grado minore di 5.
mi perdo i primi congrui a 1 modulo 4. Il polinomio più semplice che funziona è quello segnalato da blackbishop, [tex](x^2+1)(x^2-2)(x^2+2)[/tex].Quanto al grado 5, non credo sia facile, in effetti. Forse non trovabile con metodi puramente elementari. Il polinomio segnalato nell'articolo è questo:
Per la cronaca, ogni polinomio del tipo [tex](x^2-a)(x^2-b)(x^2-ab)[/tex], dove [tex]a,b[/tex] sono interi non quadrati il cui prodotto non è un quadrato, soddisfa la proprietà per il seguente semplice motivo: in [tex]\mathbb{Z}_p[/tex] se due elementi non sono quadrati il loro prodotto lo è
(appunto perché il sottogruppo dei quadrati ha indice 2 in [tex]\mathbb{Z}_p^{\ast}[/tex]).
In effetti si vede che si perdono "quei primi".
Una domanda per entrambi: non l'ho mai sentita questa partizione dei numeri primi [tex]$p$[/tex] in [tex]$p=2$[/tex] o [tex]$p\equiv1(\mathrm{mod}\,4)$[/tex] o [tex]$p\equiv3(\mathrm{mod}\,4)$[/tex], dove potrei trovarne una dimostrazione?
Una domanda per entrambi: non l'ho mai sentita questa partizione dei numeri primi [tex]$p$[/tex] in [tex]$p=2$[/tex] o [tex]$p\equiv1(\mathrm{mod}\,4)$[/tex] o [tex]$p\equiv3(\mathrm{mod}\,4)$[/tex], dove potrei trovarne una dimostrazione?
"j18eos":E' chiaro che i primi dispari sono 1 oppure 3 modulo 4 (non possono essere 0 né 2), non ti sembra?
Una domanda per entrambi: non l'ho mai sentita questa partizione dei numeri primi [tex]$p$[/tex] in [tex]$p=2$[/tex] o [tex]$p\equiv1(\mathrm{mod}\,4)$[/tex] o [tex]$p\equiv3(\mathrm{mod}\,4)$[/tex], dove potrei trovarne una dimostrazione?
Se non è di troppo disturbo, vorrei chiedere qualche chiarimento circa lo svolgimento.
Per prima cosa, partiamo dalla versione soft, quella sulle radici intere.
Non ho capito questo punto:
black, scusa, che cosa intendi di preciso quando dici $k$ è una classe di $ZZ_p$? Non capisco come puoi affermare che di sicuro esiste una classe in $ZZ_p$ che annulla uno di quei due polinomi (a secondo che $p=4k+1$ o $p=4k+3$). Potresti spenderci qualche parolina in più per piacere?
Riguardo la versione hard del problema non capisco questo passaggio:
Due domande:
1) tu affermi che ogni classe è composta da due elementi [tex]\bar{a}=\left\{a,-a\right\}$[/tex] e sono d'accordo. Mi domando però: perchè non si poteva dedurre subito da $x^4=y^4 <=>x=+-y$? Probabilmente qui commetto un errore grossolano dovuto alle mie scarse conoscenze sui gruppi... ma perchè non fila il mio ragionamento?
2) non capisco come arrivi a costruire il polinomio... ma credo che, una volta capito come mai funzionano i polinomi $4x+3$ e $4x+1$ nel caso delle radici intere, mi sarà chiaro anche questo punto.
Chiudo, ringraziando in anticipo chi farà luce e scusandomi per la mia ignoranza.
Ah, black, una cosa:
Mi devi una pizza (o una birra, fai tu
) per aver citato la mia firma
Per prima cosa, partiamo dalla versione soft, quella sulle radici intere.
Non ho capito questo punto:
"blackbishop13":
[...]
semplicemente, invece di sbattersi come ho fatto prima con residui quadratici e criterio di Eulero, sono ovviamente:
[tex]$g(x)=4x+1\ \text{e}\ h(x)=4x+3$[/tex] in quanto [tex]$k$[/tex] è una classe di [tex]$\mathbb{Z}_p$[/tex]
e poi [tex]$f(x)=x^2+1$[/tex]
black, scusa, che cosa intendi di preciso quando dici $k$ è una classe di $ZZ_p$? Non capisco come puoi affermare che di sicuro esiste una classe in $ZZ_p$ che annulla uno di quei due polinomi (a secondo che $p=4k+1$ o $p=4k+3$). Potresti spenderci qualche parolina in più per piacere?
Riguardo la versione hard
del problema non capisco questo passaggio: "blackbishop13":
[...]
ora, per il primo teorema di omomorfismo si ha [tex]$Imm(\phi)=\mathbb{Z}_p^{*}/{Ker(\phi)}$[/tex] che ha [tex]$\frac{p-1}{2}$[/tex] elementi,
e perciò ogni classe ha esattamente due elementi e in particolare osservo che, detta [tex]$\bar{a} \in \mathbb{Z}_p^{*}/{Ker(\phi)}$[/tex] la classe di [tex]a\in \mathbb{Z}_p^{*}$[/tex] si ha che [tex]\bar{a}=\left\{a,-a\right\}$[/tex].
quindi il polinomio [tex]$g(x)=\left(x^4+2\right) \cdot \left( x^4-2 \right)=x^8-4$[/tex] soddisfa la richiesta (uso il [tex]$2$[/tex] perchè così non ci sono radici razionali).
quindi ho con fatica trovato [tex]P(x)=\left( x^2+1 \right) \cdot \left( x^8-4 \right)$[/tex]
Due domande:
1) tu affermi che ogni classe è composta da due elementi [tex]\bar{a}=\left\{a,-a\right\}$[/tex] e sono d'accordo. Mi domando però: perchè non si poteva dedurre subito da $x^4=y^4 <=>x=+-y$? Probabilmente qui commetto un errore grossolano dovuto alle mie scarse conoscenze sui gruppi... ma perchè non fila il mio ragionamento?
2) non capisco come arrivi a costruire il polinomio... ma credo che, una volta capito come mai funzionano i polinomi $4x+3$ e $4x+1$ nel caso delle radici intere, mi sarà chiaro anche questo punto.
Chiudo, ringraziando in anticipo chi farà luce e scusandomi per la mia ignoranza.
Ah, black, una cosa:
"blackbishop13":
se è vero che come dice il signor I.N. Herstein: "il valore di un problema non sta tanto nel trovarne la soluzione, quanto nelle idee che fa sorgere in chi lo affronta" , allora questo problema è stato per me illuminante, grazie Martino, pensando a questo quesito ho scoperto cose nuove e compreso fino in fondo cose vecchie.
Mi devi una pizza (o una birra, fai tu
) per aver citato la mia firma
Certo, ma mi chiedevo: è una suddivisione ottimale oppure no?
@ j18eos: non credo di aver afferrato quello che tu chiedi, però ti dico come la vedo io.
Bada bene che vale solo un'implicazione, e cioè [tex]p \text{ primo} \Rightarrow p=2[/tex] o [tex]$p\equiv1(\mathrm{mod}\,4)$[/tex] o [tex]$p\equiv3(\mathrm{mod}\,4)$[/tex].
Di certo non vale l'implicazione opposta (15 - congruo a 3 modulo 4 - è il primo controesempio scemo che mi è venuto).
Ma credo che quanto detto si generalizzi facilmente, almeno ai primi dispari. Ad esempio, se un numero dispari è primo è sicuramente congruo a $+-1 mod6$. In generale, fissato un intero positivo $b$, penso si possa tranquillamente affermare che se un numero dispari è primo allora è congruo a $a mod b$ per qualche $a$ t.c. $(a,b)=1$ (o no?).
Bada bene che vale solo un'implicazione, e cioè [tex]p \text{ primo} \Rightarrow p=2[/tex] o [tex]$p\equiv1(\mathrm{mod}\,4)$[/tex] o [tex]$p\equiv3(\mathrm{mod}\,4)$[/tex].
Di certo non vale l'implicazione opposta (15 - congruo a 3 modulo 4 - è il primo controesempio scemo che mi è venuto).
Ma credo che quanto detto si generalizzi facilmente, almeno ai primi dispari. Ad esempio, se un numero dispari è primo è sicuramente congruo a $+-1 mod6$. In generale, fissato un intero positivo $b$, penso si possa tranquillamente affermare che se un numero dispari è primo allora è congruo a $a mod b$ per qualche $a$ t.c. $(a,b)=1$ (o no?).
L'implicazione l'avevo già afferrata come ha esplicitato da Martino, il problema è quello che tu hai descritto nelle ultime due righe: sono propenso come te che per ogni [tex]$\mathrm{m}$[/tex] pari i numeri primi li troviamo in tutte le classi [tex]$[\mathrm{d}]_\mathrm{m}$[/tex] con [tex]$\mathrm{d}$[/tex] numero dispari oppure no?
No, secondo me ti manca la condizione essenziale di coprimalità (un numero primo non può essere congruo a 3mod6).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo