Lemma di gauss
Lemma di gauss
Un polinomio a coefficienti interi e' detto primitivo se non esiste alcun primo che divide tutti i suoi coefficienti. Mostare che se a e b sono primitivi allora lo e' anche ab.
The only goal of science is the honor of the human spirit.
-
Sir Yussen
- Messaggi: 134
- Iscritto il: 23 feb 2010, 16:28
Re: Lemma di gauss
Qualche condizione sui gradi di a,b?
Re: Lemma di gauss
Non ne sono convintissimo...
Sia $ a(x)=\sum_{i=0}^n a_i\;x^i $e $ b(x)=\sum_{i=0}^m b_j\;x^j $ con n e m rispettivamente i gradi di a e b.
Si noti che ab contiene tutti i prodotti dei coefficienti presi a due a due. Quindi tutti i coefficienti sono nella forma $ a_ib_j $ con i che va da 0 a n e j che va da 0 a m. Si noti che per ogni primo p deve esistere almeno un $ a_r $ e un $ b_s $ tali che non siano divisibili per p: se così non fosse allora i polinomi iniziali non sarebbero primitivi perchè tutti i coefficienti sarebbero divisibili per il dato p. Di conseguenza esiste almeno una coppia $ a_r\;b_s $ nel polinomio ab che non è divisibile per p.
(si noti che questo fatto vale per ogni primo p, non necessariamente sulla stessa coppia)
Sia $ a(x)=\sum_{i=0}^n a_i\;x^i $e $ b(x)=\sum_{i=0}^m b_j\;x^j $ con n e m rispettivamente i gradi di a e b.
Si noti che ab contiene tutti i prodotti dei coefficienti presi a due a due. Quindi tutti i coefficienti sono nella forma $ a_ib_j $ con i che va da 0 a n e j che va da 0 a m. Si noti che per ogni primo p deve esistere almeno un $ a_r $ e un $ b_s $ tali che non siano divisibili per p: se così non fosse allora i polinomi iniziali non sarebbero primitivi perchè tutti i coefficienti sarebbero divisibili per il dato p. Di conseguenza esiste almeno una coppia $ a_r\;b_s $ nel polinomio ab che non è divisibile per p.
(si noti che questo fatto vale per ogni primo p, non necessariamente sulla stessa coppia)
"We' Inge!"
LTE4LYF
LTE4LYF
Re: Lemma di gauss
E' quello che devi dimostrare..Triarii ha scritto:Di conseguenza esiste almeno una coppia $ a_r\;b_s $ nel polinomio ab che non è divisibile per p.
The only goal of science is the honor of the human spirit.
Re: Lemma di gauss
Supponiamo per assurdo che esista un p che divida i coefficienti di ab, che sono nella forma $ a_i\;b_j $
p divide uno dei due coefficienti del prodotto: si noti che esistono almeno un $ a_r $ e un $ b_s $ che non sono divisibili per p, altrimenti a e b non sarebbero primitivi.
Prendo dunque il coefficiente di ab $ a_r\;b_s $(che esiste ed appartiene ad ab). Per ipotesi questo era divisibile per p, ma ciò è assurdo perchè nè $ a_r $ nè $ b_s $ sono divisibili per p. Quindi non esiste p che divide tutti i coefficienti di ab quindi ab è primitivo.
Dove sbaglio?
p divide uno dei due coefficienti del prodotto: si noti che esistono almeno un $ a_r $ e un $ b_s $ che non sono divisibili per p, altrimenti a e b non sarebbero primitivi.
Prendo dunque il coefficiente di ab $ a_r\;b_s $(che esiste ed appartiene ad ab). Per ipotesi questo era divisibile per p, ma ciò è assurdo perchè nè $ a_r $ nè $ b_s $ sono divisibili per p. Quindi non esiste p che divide tutti i coefficienti di ab quindi ab è primitivo.
Dove sbaglio?
"We' Inge!"
LTE4LYF
LTE4LYF
-
Sir Yussen
- Messaggi: 134
- Iscritto il: 23 feb 2010, 16:28
Re: Lemma di gauss
Non vorrei dire idiozie, ma i coefficienti di $ab$ non sono della forma $a_ib_j$. Per farti un esempio sciocco, considera il coefficiente di primo grado di $ab$: esso sarà $a_0b_1 + b_1a_0$
Re: Lemma di gauss
Già che scemo, il coefficiente di grado s+r è ovviamente nella forma$ a_rb_s+a_{r-1}b_{s+1}...+a_{r+1}b_{s-1}... $
"We' Inge!"
LTE4LYF
LTE4LYF
Re: Lemma di gauss
Si, esatto. Hai anche preso il coefficiente, ma come dimostri che non e' multiplo di p?Triarii ha scritto:Già che scemo, il coefficiente di grado s+r è ovviamente nella forma$ a_rb_s+a_{r-1}b_{s+1}...+a_{r+1}b_{s-1}... $
The only goal of science is the honor of the human spirit.
-
Sir Yussen
- Messaggi: 134
- Iscritto il: 23 feb 2010, 16:28
Re: Lemma di gauss
Provo io:
Chiamo $deg(a(x)) = n$ e $deg(b(x)) = m$. Inoltre, $a(x)b(x)=c(x)$. La scrittura di $b(x)$ e $a(x)$ è rispettivamente $a(x)= \sum^n{a_ix^i}$ e $b(x)= \sum^m{b_jx^i}$. Rispondendo da solo alla mia domanda di prima, ho che $n,m \geq 1$.
Voglio fare induzione su $m$.
Passo Base: $m=1$. Supponiamo per assurdo che esista un $p$ primo tale che $p|c_{n+1},c_{n}, \cdots ,c_1,c_0 $. In particolare, abbiamo che $p$ divide: $c_0 = b_0a_0$, $c_1$=$b_1a_0 + b_0a_1$, $c_{n+1} =a_nb_1$, $c_n=a_nb_0 + b_1a_{n-1}$.
Per rispettare la primitività di $b(x)$, non può essere che $p|b_0,b_1$. Ma se fosse che $p$ non divide ne $b_1$, ne $b_0$, per induzione risalendo da $c_0$ a $c_{n+1}$ avremmo che $p|a_0,a_1,\cdots, a_n$, non rispettando la primitività
di $a(x)$. Se $p|b_0$ e non divide $b_1$, avremmo di nuovo per induzione un assurdo con la primitività di $a(x)$, e lo stesso vale nel caso in cui $p|b_1$ e $p$ non divide $b_0$. (avete idea di quale sia il simbolo LaTeX di "non divide"..?)
Passo Dopobase: Suppongo che la tesi sia vera per $m$. Per passare ad $m+1$ riscalo i coefficienti, ovvero $b_{i+1} \leftarrow b_i$, e introduco un nuovo $b_0$. Ottengo gli stessi termini dell'ipotesi induttiva, più altri termini che hanno $b_0$, e per induzione come nel caso base si crea un assurdo con la primitività di $b(x)$ e $a(x)$. Amen.
Chiamo $deg(a(x)) = n$ e $deg(b(x)) = m$. Inoltre, $a(x)b(x)=c(x)$. La scrittura di $b(x)$ e $a(x)$ è rispettivamente $a(x)= \sum^n{a_ix^i}$ e $b(x)= \sum^m{b_jx^i}$. Rispondendo da solo alla mia domanda di prima, ho che $n,m \geq 1$.
Voglio fare induzione su $m$.
Passo Base: $m=1$. Supponiamo per assurdo che esista un $p$ primo tale che $p|c_{n+1},c_{n}, \cdots ,c_1,c_0 $. In particolare, abbiamo che $p$ divide: $c_0 = b_0a_0$, $c_1$=$b_1a_0 + b_0a_1$, $c_{n+1} =a_nb_1$, $c_n=a_nb_0 + b_1a_{n-1}$.
Per rispettare la primitività di $b(x)$, non può essere che $p|b_0,b_1$. Ma se fosse che $p$ non divide ne $b_1$, ne $b_0$, per induzione risalendo da $c_0$ a $c_{n+1}$ avremmo che $p|a_0,a_1,\cdots, a_n$, non rispettando la primitività
di $a(x)$. Se $p|b_0$ e non divide $b_1$, avremmo di nuovo per induzione un assurdo con la primitività di $a(x)$, e lo stesso vale nel caso in cui $p|b_1$ e $p$ non divide $b_0$. (avete idea di quale sia il simbolo LaTeX di "non divide"..?)
Passo Dopobase: Suppongo che la tesi sia vera per $m$. Per passare ad $m+1$ riscalo i coefficienti, ovvero $b_{i+1} \leftarrow b_i$, e introduco un nuovo $b_0$. Ottengo gli stessi termini dell'ipotesi induttiva, più altri termini che hanno $b_0$, e per induzione come nel caso base si crea un assurdo con la primitività di $b(x)$ e $a(x)$. Amen.
Re: Lemma di gauss
Il simbolo del non divide è nmid (e.g. $2\nmid 57$); il passo base pare funzionare. Ma potresti esplicitare meglio il "Passo Dopobase" quotato sopra?Sir Yussen ha scritto:Passo Dopobase: Suppongo che la tesi sia vera per $m$. Per passare ad $m+1$ riscalo i coefficienti, ovvero $b_{i+1} \leftarrow b_i$, e introduco un nuovo $b_0$. Ottengo gli stessi termini dell'ipotesi induttiva, più altri termini che hanno $b_0$, e per induzione come nel caso base si crea un assurdo con la primitività di $b(x)$ e $a(x)$. Amen.
The only goal of science is the honor of the human spirit.
-
Sir Yussen
- Messaggi: 134
- Iscritto il: 23 feb 2010, 16:28
Re: Lemma di gauss
Vediamo un pò che riesco a fare.. (con questa nuova conoscenza in mio possesso, seminerò il panico sull'oliforum)
Supponiamo la tesi vera per $m$. Un polinomio di $m+1$-esimo grado lo posso ottenere da uno di $m$-esimo grado, riscalando i coefficienti e aggiungendone uno nuovo.. Così faccio: $b_{i+1} \leftarrow b_i$, $b_0 \leftarrow K$ nuovo. Suppongo per assurdo che ci sia un $p$ tale che $p|c_{n+m}, \cdots ,c_1,c_0 $. In particolare, $p$ divide:
$c_0=a_0K$
$c_1=a_1K+a_0b_0$ (i coefficienti riscalati mantengono lo stesso nome del polinomio di $m$-esimo grado.
$c_2=a_2K + a_1b_0 + a_0b_1$
.
.
In pratica, i vari coefficienti di $c(x)$ sono gli stessi di prima più una costante aggiunta del tipo $a_iK$. Per ipotesi induttiva, i coefficienti di $c(x)$ ai tempi di $m$, danno $MCD=1$. Ora, se per assurdo c'è un primo $p$ che divide tutti i coefficienti, allora $p|a_0K$ : se $p|K$, avremmo che $p$ divide i pezzi di $c(x)$ "ai tempi di $m$, assurdo. Se invece $p|a_0$, ci sarebbe un $p$ che divide lo stesso tipo di roba, dove $K$ assume il ruolo di $a_0$.(sta cosa ora come ora non saprei dirla bene..Come faccio a dirla?) E quindi viene di nuovo contraddetta l'iptesi induttiva.
Supponiamo la tesi vera per $m$. Un polinomio di $m+1$-esimo grado lo posso ottenere da uno di $m$-esimo grado, riscalando i coefficienti e aggiungendone uno nuovo.. Così faccio: $b_{i+1} \leftarrow b_i$, $b_0 \leftarrow K$ nuovo. Suppongo per assurdo che ci sia un $p$ tale che $p|c_{n+m}, \cdots ,c_1,c_0 $. In particolare, $p$ divide:
$c_0=a_0K$
$c_1=a_1K+a_0b_0$ (i coefficienti riscalati mantengono lo stesso nome del polinomio di $m$-esimo grado.
$c_2=a_2K + a_1b_0 + a_0b_1$
.
.
In pratica, i vari coefficienti di $c(x)$ sono gli stessi di prima più una costante aggiunta del tipo $a_iK$. Per ipotesi induttiva, i coefficienti di $c(x)$ ai tempi di $m$, danno $MCD=1$. Ora, se per assurdo c'è un primo $p$ che divide tutti i coefficienti, allora $p|a_0K$ : se $p|K$, avremmo che $p$ divide i pezzi di $c(x)$ "ai tempi di $m$, assurdo. Se invece $p|a_0$, ci sarebbe un $p$ che divide lo stesso tipo di roba, dove $K$ assume il ruolo di $a_0$.(sta cosa ora come ora non saprei dirla bene..Come faccio a dirla?) E quindi viene di nuovo contraddetta l'iptesi induttiva.
Re: Lemma di gauss
Sì, funziona, ma è scritta molto male: prova a riscriverla, casomai con un'altra notazione, o magari evitando completamente l'induzione
The only goal of science is the honor of the human spirit.
-
Gottinger95
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Lemma di gauss
INTRODUZIONE (in pratica il pezzo che si potrebbe pure saltare, ma è giusto fare 
)
Per chiarezza, se eventualmente scrivessi un coefficiente che non esiste nel polinomio corrispondente, lo sottintendo uguale a 0. Non influisce sulla dimostrazione.
Siano \(c_0, \ldots, c_m\) i coefficienti del prodotto tra i due polinomi primitivi \(A(x), B(x)\), della forma \(c_s = \displaystyle \sum_{i=0}^s{a_ib_{s-i}}\).
Poniamo per assurdo che esista un \(p\) primo tale che \(p \mid MCD(c_0, \ldots, c_m) \).
OSSERVAZIONE del PiC (Passo induttivo Cicoria). Notiamo che se
\(p \mid a_0, \ldots, a_n\)
\(p \mid b_0, \ldots, b_{k-1}\) e \(p \nmid b_k\)
\(p \mid c_{n+k+1} = a_0b_{n+k+1} + \ldots + a_nb_{k+1} + a_{n+1}b_k +a_{n+2}b_{k-1} + \ldots + a_{n+k+1}b_0 \)
allora \(p \mid a_{n+1}\). Questo sarà il passo induttivo di due casi (notasi che l'induzione è su n, mentre k rimane costante).
DIMOSTRAZIONE
Visto che \(p \mid c_0 = a_0b_0\), ci sono due casi:
1. p divide uno dei due; WLOG \(p \mid a_0\) e \(p \nmid b_0\).
Usando il PiC con k=0, si ha per induzione estesa che p divide tutti gli \(a_i\) --> Assurdo.
2. p divide entrambi.
Notiamo che se
\(p \mid a_0, \ldots, a_{n-1}\)
\(p \mid b_0, \ldots, b_{n-1}\)
\(p \mid c_{2n} = a_0b_{2n} + \ldots + a_{n-1}b_{n+1} + a_nb_n + a_{n+1}b_{n-1} + \ldots + a_{2n}b_0\)
allora \(p \mid a_nb_n\). Qui si aprono due strade.
Se p li divide entrambi, allora si continua l'induzione estesa su \(a_n, b_n\) finchè p non divide tutti gli \(a_i\) o i \(b_i\) --> Assurdo.
Se p ne divide uno solo, WLOG \(p \mid a_n\) e \(p \nmid b_n\), allora usando il PiC con k=n si ha per induzione estesa che p divide tutti gli \(a_i\) --> Assurdo.
Domanda in più. Mi chiedo: quali sono i polinomi primitivi P(x) "primi", ossia tali che non esistono due primitivi A(x), B(x) tali che \(A(x) \cdot B(x) = P(x)\) ?
Notando che la definizione di primitivo ha senso solo per i polinomi non costanti, ossia con grado \(\geq\) 1, sicuramente i primitivi di primo grado sono "primi". Però è davvero ben poco rispetto a ciò che mi domando. Diciamo che la domanda è la stessa di: quali sono i polinomi a coefficienti interi irriducibili?
)Per chiarezza, se eventualmente scrivessi un coefficiente che non esiste nel polinomio corrispondente, lo sottintendo uguale a 0. Non influisce sulla dimostrazione.
Siano \(c_0, \ldots, c_m\) i coefficienti del prodotto tra i due polinomi primitivi \(A(x), B(x)\), della forma \(c_s = \displaystyle \sum_{i=0}^s{a_ib_{s-i}}\).
Poniamo per assurdo che esista un \(p\) primo tale che \(p \mid MCD(c_0, \ldots, c_m) \).
OSSERVAZIONE del PiC (Passo induttivo Cicoria). Notiamo che se
\(p \mid a_0, \ldots, a_n\)
\(p \mid b_0, \ldots, b_{k-1}\) e \(p \nmid b_k\)
\(p \mid c_{n+k+1} = a_0b_{n+k+1} + \ldots + a_nb_{k+1} + a_{n+1}b_k +a_{n+2}b_{k-1} + \ldots + a_{n+k+1}b_0 \)
allora \(p \mid a_{n+1}\). Questo sarà il passo induttivo di due casi (notasi che l'induzione è su n, mentre k rimane costante).
DIMOSTRAZIONE
Visto che \(p \mid c_0 = a_0b_0\), ci sono due casi:
1. p divide uno dei due; WLOG \(p \mid a_0\) e \(p \nmid b_0\).
Usando il PiC con k=0, si ha per induzione estesa che p divide tutti gli \(a_i\) --> Assurdo.
2. p divide entrambi.
Notiamo che se
\(p \mid a_0, \ldots, a_{n-1}\)
\(p \mid b_0, \ldots, b_{n-1}\)
\(p \mid c_{2n} = a_0b_{2n} + \ldots + a_{n-1}b_{n+1} + a_nb_n + a_{n+1}b_{n-1} + \ldots + a_{2n}b_0\)
allora \(p \mid a_nb_n\). Qui si aprono due strade.
Se p li divide entrambi, allora si continua l'induzione estesa su \(a_n, b_n\) finchè p non divide tutti gli \(a_i\) o i \(b_i\) --> Assurdo.
Se p ne divide uno solo, WLOG \(p \mid a_n\) e \(p \nmid b_n\), allora usando il PiC con k=n si ha per induzione estesa che p divide tutti gli \(a_i\) --> Assurdo.
Domanda in più. Mi chiedo: quali sono i polinomi primitivi P(x) "primi", ossia tali che non esistono due primitivi A(x), B(x) tali che \(A(x) \cdot B(x) = P(x)\) ?
Notando che la definizione di primitivo ha senso solo per i polinomi non costanti, ossia con grado \(\geq\) 1, sicuramente i primitivi di primo grado sono "primi". Però è davvero ben poco rispetto a ciò che mi domando. Diciamo che la domanda è la stessa di: quali sono i polinomi a coefficienti interi irriducibili?
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Re: Lemma di gauss
La tua soluzione è sostanzialmente la stessa di quella di sopra, scritta meglio [Si puo' comunque evitare l'induzione, ma va bien così]
Beh, è un domandone. Esistono criteri di irriducibilità che forniscono condizioni sufficienti a garantire che un polinomio $p \in \mathbb{Z}[x]$ sia irriducibile in $\mathbb{Q}[x]$ (sarà l'argomento del Lemma di Gauss - parte 3), ma non penso esista una risposta "completa" a cio' che chiediGottinger95 ha scritto:Però è davvero ben poco rispetto a ciò che mi domando. Diciamo che la domanda è la stessa di: quali sono i polinomi a coefficienti interi irriducibili?
The only goal of science is the honor of the human spirit.