Sia $ p \in \mathbb{P} $ fissato. Esistono due permutazioni $ \{y_1,y_2,\ldots,y_{p-1}\} $ e $ \{x_1,x_2,\ldots,x_{p-1}\} $ di $ \{1,2,\ldots,p-1\} $ tali che $ p \mid y_i-\prod_{j=1}^i{x_j} $ per ogni $ i=1,2,\ldots,p-1 $?
(Nazionali polacche)
Edit: grazie a una segnalazione privata di kn, mi sono accorto che il testo è poco chiaro; il quesito è riferito all'esistenza di entrambe le permutazioni {x_i} e {y_i}, in altre parole {x_i} non è fissata..
Permutazioni di {1,2,...,p-1}
Permutazioni di {1,2,...,p-1}
Ultima modifica di jordan il 06 ott 2009, 23:09, modificato 2 volte in totale.
The only goal of science is the honor of the human spirit.
Dimostro che non esiste mai una permutazione come quella richiesta.
Vado a dimostrare per assurdo che non esiste mai una permutazione come quella richiesta:Lemma 1: $ \displaystyle n>m\Rightarrow\ p\not| \prod_{i=1}^nx_i-\prod_{j=1}^mx_j $
Lo dimostro per assurdo:
Assumo $ \displaystyle \prod_{i=1}^nx_i\equiv \prod_{j=1}^mx_j\equiv a\pmod{p} $
Ma allora per ipotesi ottengo $ y_n\equiv a\equiv y_m \pmod p $ che è un assurdo, quindi il lemma è vero.
Step 1:$ \displaystyle x_1=1 $
Lavoro per assurdo, assumo che $ x_{k+1}=1 $ ma allora basta notare:
$ \displaystyle \prod_{i=1}^{k+1}x_i\equiv\prod_{j=1}^kx_j \pmod p $
che è assurdo per il lemma.
Per quanto ottenuto basta considerare $ n=p-1 $ e $ m=1 $ per ottenere un assurdo dal lemma.Step 2: $ \displaystyle \prod_{i=1}^{p-1}x_i\equiv 1\pmod p $
Sfrutto i generatori (ormai sono fissato, li uso ovunque xD). Chiamo g un generatore modulo p e ottengo:
$ \displaystyle \prod_{i=1}^{p-1}x_i\equiv g^0g^1g^2\dots g^{p-1}\equiv g^{\frac{(p-1)(p-2)}{2}}\equiv g^0\equiv 1\pmod p $
Che era il risultato cercato.
Allora, con calma 
Come prima cosa, ci metti la citazione a chi è riferita e quale post? Inoltre il lemma1 è banalmente vero (serviva chiamarlo lemma? in fondo stai dicendo che la differenza tra due interi positivi differenti e minori di p non è multipla di p), lo step 1 è corretto, ma se k=0? Infine non capisco il significato del lemma 2 (oltre che la somma sugli esponenti dei generatori non è corretta) 
Come prima cosa, ci metti la citazione a chi è riferita e quale post? Inoltre il lemma1 è banalmente vero (serviva chiamarlo lemma? in fondo stai dicendo che la differenza tra due interi positivi differenti e minori di p non è multipla di p), lo step 1 è corretto, ma se k=0? Infine non capisco il significato del lemma 2 (oltre che la somma sugli esponenti dei generatori non è corretta) The only goal of science is the honor of the human spirit.
Le citazioni servono per dare alla dimostrazione un che di elegante xD
k è diverso da 0... non l'ho detto perchè mi pareva scontato.
Sullo step 2... ho toppato a riscrivere la produttoria... correggo:
$ \displaystyle \prod_{i=1}^{p-1}x_i\equiv g^0g^1g^2\dots g^{p-2}\equiv g^{\frac{(p-2)(p-1)}{2}}\equiv g^0\equiv 1\pmod p $
Ora spero sia giusto :)
p.s. il lemma l'ho scritto per comodità d'uso dopo :)
k è diverso da 0... non l'ho detto perchè mi pareva scontato.
Sullo step 2... ho toppato a riscrivere la produttoria... correggo:
$ \displaystyle \prod_{i=1}^{p-1}x_i\equiv g^0g^1g^2\dots g^{p-2}\equiv g^{\frac{(p-2)(p-1)}{2}}\equiv g^0\equiv 1\pmod p $
Ora spero sia giusto :)
p.s. il lemma l'ho scritto per comodità d'uso dopo :)
LOLdario2994 ha scritto:Le citazioni servono per dare alla dimostrazione un che di elegante xD
Ok, ma in quel caso come definisci la produttoria a destra dello step 1?dario2994 ha scritto:k è diverso da 0... non l'ho detto perchè mi pareva scontato.
The only goal of science is the honor of the human spirit.
Casomai $ \displaystyle~ \prod_{i=1}^{p-1}x_i\equiv g^0g^1g^2\dots g^{p-1}\equiv g^{\frac{(p-1)p}{2}}\not\equiv g^0\pmod p $dario2994 ha scritto:Sfrutto i generatori (ormai sono fissato, li uso ovunque xD). Chiamo g un generatore modulo p e ottengo:
$ \displaystyle \prod_{i=1}^{p-1}x_i\equiv g^0g^1g^2\dots g^{p-1}\equiv g^{\frac{(p-1)(p-2)}{2}}\equiv g^0\equiv 1\pmod p $
Cmq non sforzarti di dimostrare una cosa falsa
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
Una produttoria per i da 1 a 0 ti sembra logico eh?dario2994 ha scritto:Alur... uno per volta:
@ Jordan: se k=0 allora il lemma è vero xD e non serve che io definisca nulla
@kn: ho toppato xD
E comunque volevo solo farti capire dov'era l'errore, altrimenti potevo limitarmi a "non è quella la risposta quindi è sbagliato"The only goal of science is the honor of the human spirit.
Posto giusto per uppare dato che mi interessa la soluzione di questo problema (sul quale mi sono abbattuto per 2-3 giorni con i miseri risultati che seguono):
1) Mi sono accorto che io nel primo post avevo "dimostrato" il contrario del teorema di Wilson xD
2) Ho ricondotto il problema a trovare per quale p esiste una permutazione $ \displaystyle (a_1,a_2,\dots,a_{p-2}) $ di $ \displaystyle (2,3,\dots,p-1}) $ tale che:
$ \displaystyle\prod_{i=b}^ca_i\not\equiv 1 \pmod p\ \ \forall\ \ 1\le b\le c\le p-2 $
Non sono molto convinto che questo semplifica il problema (non posto la dimostrazione del fatto tanto è abbastanza banale... e forse inutile xD)
p.s. Jordan se nessuno posta una soluzione puoi mettere un hint...
1) Mi sono accorto che io nel primo post avevo "dimostrato" il contrario del teorema di Wilson xD
2) Ho ricondotto il problema a trovare per quale p esiste una permutazione $ \displaystyle (a_1,a_2,\dots,a_{p-2}) $ di $ \displaystyle (2,3,\dots,p-1}) $ tale che:
$ \displaystyle\prod_{i=b}^ca_i\not\equiv 1 \pmod p\ \ \forall\ \ 1\le b\le c\le p-2 $
Non sono molto convinto che questo semplifica il problema (non posto la dimostrazione del fatto tanto è abbastanza banale... e forse inutile xD)
p.s. Jordan se nessuno posta una soluzione puoi mettere un hint...
Metto la mia soluzione se non vuoi non leggerla:
dimostriamo che per ogni primo esistono le due permutazioni.. Ragioniamo in $ \displaystyle~\mathbb{Z}_{/p\mathbb{Z}} $ per comodità. La tesi in pratica chiede se esiste una permutazione $ \displaystyle~\{x_i\} $ (non so se è la notazione giusta) tale che la funzione $ \displaystyle~f(\cdot):\{\prod_{j=1}^i{x_j}\}\to\{1,...,p-1\} $ è iniettiva (o suriettiva).
Di conseguenza basta prendere una permutazione $ \displaystyle~\{x_i\} $ tale che non esistano $ \displaystyle~1<m\le M<p $ tali che $ \displaystyle~\prod_{j=m}^M x_j=1 $ (chiameremo le produttorie $ \displaystyle~\prod_{j=a>1}^b x_j $ "sottoprodotti"). Infatti ciò è equivalente ad avere $ \displaystyle~f(\cdot) $ iniettiva, dato che $ \displaystyle~\nexists(m,M):\prod_{j=1}^{m-1} x_j=\prod_{j=1}^M x_j\Leftrightarrow\nexists(m,M):\prod_{j=m}^M x_j=1 $ (essendo tutti gli $ \displaystyle~x_i $ primi con $ \displaystyle~p $). Costruiamo dunque una permutazione $ \displaystyle~\{x_i\} $ in modo che non ci siano sottoprodotti $ \displaystyle~=1 $ e nel frattempo una successione $ \displaystyle~\{S_i\} $ di sottoinsiemi di $ \displaystyle~\{1,...,p-1\} $:
$ \displaystyle~S_1=\{1\} $;
$ \displaystyle~x_1=1 $ (dato che lo deve essere obbligatoriamente, come hai dimostrato)
scelto un $ \displaystyle~x_i $ definiamo $ \displaystyle~S_{i+1} $ in modo che contenga i valori che non devono assumere i sottoprodotti che partono da $ \displaystyle~x_{i+1} $ o termini successivi per farci avere sottoprodotti $ \displaystyle~=1 $: dunque $ \displaystyle~S_{i+1}=\{x_i^{-1}r,~r\in S_i\}\cup\{1\} $. Ad ogni scelta di un nuovo valore $ \displaystyle~x_i $ della permutazione, facciamo in modo che se $ \displaystyle~i>1 $ $ \displaystyle~x_i\in\{1,...,p-1\}-S_i $. Finita la costruzione, se esistessero $ \displaystyle~1<a<b<p:\prod_{j=a}^b x_j=1 $ avremmo $ \displaystyle~\prod_{j=a+1}^b x_j=x_a^{-1}\in S_{a+1} $, allo stesso modo $ \displaystyle~\prod_{j=a+2}^b x_j\in S_{a+2} $, ..., fino a $ \displaystyle~\prod_{j=b}^b x_j=x_b\in S_b $, assurdo per come abbiamo scelto gli $ \displaystyle~x_i $.
Ma possiamo veramente costruire una permutazione così? Basta che $ \displaystyle~S_i $ non contenga mai $ \displaystyle~p-1 $ o più elementi: ma ciò è ovvio dato che $ \displaystyle~|S_{i+1}|\le |S_i|+1 $ e $ \displaystyle~|S_1|=|S_2|=1 $, da cui $ \displaystyle~|S_i|\le i-1\le p-2 $.
Mi rendo conto di essermi spiegato malissimo.. spero almeno che riuscirai ad afferrare l'idea..
dimostriamo che per ogni primo esistono le due permutazioni.. Ragioniamo in $ \displaystyle~\mathbb{Z}_{/p\mathbb{Z}} $ per comodità. La tesi in pratica chiede se esiste una permutazione $ \displaystyle~\{x_i\} $ (non so se è la notazione giusta) tale che la funzione $ \displaystyle~f(\cdot):\{\prod_{j=1}^i{x_j}\}\to\{1,...,p-1\} $ è iniettiva (o suriettiva).
Di conseguenza basta prendere una permutazione $ \displaystyle~\{x_i\} $ tale che non esistano $ \displaystyle~1<m\le M<p $ tali che $ \displaystyle~\prod_{j=m}^M x_j=1 $ (chiameremo le produttorie $ \displaystyle~\prod_{j=a>1}^b x_j $ "sottoprodotti"). Infatti ciò è equivalente ad avere $ \displaystyle~f(\cdot) $ iniettiva, dato che $ \displaystyle~\nexists(m,M):\prod_{j=1}^{m-1} x_j=\prod_{j=1}^M x_j\Leftrightarrow\nexists(m,M):\prod_{j=m}^M x_j=1 $ (essendo tutti gli $ \displaystyle~x_i $ primi con $ \displaystyle~p $). Costruiamo dunque una permutazione $ \displaystyle~\{x_i\} $ in modo che non ci siano sottoprodotti $ \displaystyle~=1 $ e nel frattempo una successione $ \displaystyle~\{S_i\} $ di sottoinsiemi di $ \displaystyle~\{1,...,p-1\} $:
$ \displaystyle~S_1=\{1\} $;
$ \displaystyle~x_1=1 $ (dato che lo deve essere obbligatoriamente, come hai dimostrato)
scelto un $ \displaystyle~x_i $ definiamo $ \displaystyle~S_{i+1} $ in modo che contenga i valori che non devono assumere i sottoprodotti che partono da $ \displaystyle~x_{i+1} $ o termini successivi per farci avere sottoprodotti $ \displaystyle~=1 $: dunque $ \displaystyle~S_{i+1}=\{x_i^{-1}r,~r\in S_i\}\cup\{1\} $. Ad ogni scelta di un nuovo valore $ \displaystyle~x_i $ della permutazione, facciamo in modo che se $ \displaystyle~i>1 $ $ \displaystyle~x_i\in\{1,...,p-1\}-S_i $. Finita la costruzione, se esistessero $ \displaystyle~1<a<b<p:\prod_{j=a}^b x_j=1 $ avremmo $ \displaystyle~\prod_{j=a+1}^b x_j=x_a^{-1}\in S_{a+1} $, allo stesso modo $ \displaystyle~\prod_{j=a+2}^b x_j\in S_{a+2} $, ..., fino a $ \displaystyle~\prod_{j=b}^b x_j=x_b\in S_b $, assurdo per come abbiamo scelto gli $ \displaystyle~x_i $.
Ma possiamo veramente costruire una permutazione così? Basta che $ \displaystyle~S_i $ non contenga mai $ \displaystyle~p-1 $ o più elementi: ma ciò è ovvio dato che $ \displaystyle~|S_{i+1}|\le |S_i|+1 $ e $ \displaystyle~|S_1|=|S_2|=1 $, da cui $ \displaystyle~|S_i|\le i-1\le p-2 $.
Mi rendo conto di essermi spiegato malissimo.. spero almeno che riuscirai ad afferrare l'idea..
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
Quasi... Io ho proposto un algoritmo per costruire una permutazione buona e nel frattempo una successione di insiemi $ \displaystyle~\{S_i\} $ ($ \displaystyle~S_i\in\{1,...,p-1\} $) ausiliaria, cioè:
$ \displaystyle~x_1=1 $
$ \displaystyle~S_1=S_2=\{1\} $ ($ \displaystyle~S_1 $ non serve)
facciamo quanto segue per $ \displaystyle~i=2 $, quindi $ \displaystyle~i=3 $, ..., fino a $ \displaystyle~i=p-1 $: è già definito l'insieme $ \displaystyle~S_i $, quindi scegliamo $ \displaystyle~x_i $ in $ \displaystyle~\{1,...,p-1\}-S_i $ e definiamo $ \displaystyle~S_{i+1}=\{x_i^{-1}r,~r\in S_i\}\cup\{1\} $.
Nel post precedente ho cercato di spiegare perché quest'algoritmo funziona.. È più chiaro adesso?
$ \displaystyle~x_1=1 $
$ \displaystyle~S_1=S_2=\{1\} $ ($ \displaystyle~S_1 $ non serve)
facciamo quanto segue per $ \displaystyle~i=2 $, quindi $ \displaystyle~i=3 $, ..., fino a $ \displaystyle~i=p-1 $: è già definito l'insieme $ \displaystyle~S_i $, quindi scegliamo $ \displaystyle~x_i $ in $ \displaystyle~\{1,...,p-1\}-S_i $ e definiamo $ \displaystyle~S_{i+1}=\{x_i^{-1}r,~r\in S_i\}\cup\{1\} $.
Nel post precedente ho cercato di spiegare perché quest'algoritmo funziona.. È più chiaro adesso?
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
Jordan... che figo xD Io non so come mai mi ero convinto che fosse impossibile (tranne che per 2 e 3... dato che non avevo trovato un modo con p=5 xD)... la tua costruzione è davvero bella... e chiarissima xD
@ kn ho letto la prima parte della tua dimostrazione... almeno il fatto che ho postato serviva a qualcosa xD La sceonda parte è davvero confusionaria xD Sopratutto non ho capito a pieno perchè costruisci $ \displaystyle S_i $
@ kn ho letto la prima parte della tua dimostrazione... almeno il fatto che ho postato serviva a qualcosa xD La sceonda parte è davvero confusionaria xD Sopratutto non ho capito a pieno perchè costruisci $ \displaystyle S_i $