Piccolo teorema di Fermat e collane

[Zorro_93]

Non ho capito cos'è k. Inoltre non è chiaro dove (e se) usi la minimalità di d.

In effetti non la uso... e non è neanche la definizione di segmenti lunghi d

[Zorro_93]

ci riprovo:
Se $ (a_i,a_i+1,\cdots,a_i+d) $ è una parte della collana, tramite la rotazione si vede che deve coincidere con $ (a_{i+d+1},a_{i+d+2},\cdots,a_{i+2d}) $ per ogni i (sempre modulo la lunghezza della collana). Questa dovrebbe essere la definizione che stabilisce l'uguaglianza di segmenti lunghi d.

In particolare $ (a_1,\cdots,a_d)=(a_{d+1},\cdots,a_{2d})=\cdots=(a_{(q-1)d+1},\cdots,a_{qd}) $ dove $ qd=p $

Anche qui non uso la minimalità di d.

[Tibor Gallai]

Allora, l'ipotesi è che $ $a_i=a_{i+d} $ per ogni $ $i\in \{ 0, \ldots , n-1\} $. Inoltre, per ogni $ $d' $ tale che $ $0<d'<d $, esiste un $ $j\in \{ 0, \ldots , n-1\} $ tale che $ $a_j \neq a_{j+d'} $.
Tutti gli indici, al solito, vanno considerati modulo $ $n $.
La tesi è che $ $d\mid n $.

L'ipotesi sulla minimalità di $ $d $ è essenziale (perché?), e quindi va usata.

Una possibile dimostrazione è questa:
sia $ $n=qd-r $, con $ $0\leqslant r<d $. Allora $ $a_i = a_{i+d} = a_{i+2d} = \ldots = a_{i+qd} = a_{i+n+r} = a_{i+r} $, per ogni $ $i\in \{ 0, \ldots , n-1\} $. Quindi $ $r=0 $, altrimenti la stringa avrebbe periodo al più $ $r<d $.

[Zorro_93]

ok... cerco di ricapitolare:

Il dubbio era questo: perchè se p è primo ho p permutazioni cicliche e quindi dividendo $ a^p-a $ ottengo un intero e con p composto no?


Poi ci sono queste proposizioni:

(a)d|p
(b)Con una rotazione di d>0 posti otteniamo una collana coincidente

Noi dobbiamo far vedere che $ $\neg(a) \to \neg (b)$ $ per ogni d>0 (ovvero che $ $(b)\to (a)$ $), a quel punto, prendendo p primo $ $\neg(a)$ $ è vera per ogni d>1 e quindi le rotazioni di più di un posto non coincidono mai.

E questo l'ha fatto Tibor.



("Inoltre, per ogni $ $d' $ tale che $ $0<d'<d $, esiste un $ $j\in \{ 0, \ldots , n-1\} $ tale che $ $a_j \neq a_{j+d'} $." è l'ipotesi di minimalità, giusto?)

L'ipotesi sulla minimalità di $ $d $ è essenziale (perché?), e quindi va usata.

Bhe, l'hai usata chiaramente alla fine della dimostrazione, no?

Credete che mi sia chiarito le idee nel modo giusto?

[Tibor Gallai]

Noi dobbiamo far vedere che $ $\neg(a) \to \neg (b)$ $ per ogni d>0
[...]
E questo l'ha fatto Tibor.

Assolutamente no, io ho per l'appunto dimostrato (e ti invito a rileggere) che quell'implicazione vale se a (b) si aggiunge la minimalità di d, e non che vale per ogni d>0 senza minimalità, perché altrimenti avrei dimostrato il falso.

("Inoltre, per ogni $ $d' $ tale che $ $0<d'<d $, esiste un $ $j\in \{ 0, \ldots , n-1\} $ tale che $ $a_j \neq a_{j+d'} $." è l'ipotesi di minimalità, giusto?)

Giusto.

L'ipotesi sulla minimalità di $ $d $ è essenziale (perché?), e quindi va usata.

Bhe, l'hai usata chiaramente alla fine della dimostrazione, no?

Che l'abbia usata io non significa che sia essenziale. A priori potrebbero esistere dimostrazioni che non usano la minimalità di d. Per che motivo invece sappiamo che non possano esistere siffatte dimostrazioni?

[Zorro_93]

Che l'abbia usata io non significa che sia essenziale. A priori potrebbero esistere dimostrazioni che non usano la minimalità di d. Per che motivo invece sappiamo che non possano esistere siffatte dimostrazioni?

Se $ c $ è la sottostringa minima e $ d $ è una più lunga e sia quindi $ 0<c<d<n $. Allora $ a_i=a_{i+c} $ e $ a_i=a_{i+d} $ per ogni i, ma allora $ a_{i+c}=a_{i+d} $ per ogni i e quindi $ a_{i}=a_{d-c} $, quindi esiste una stringa di lunghezza $ d-c $, a questo punto possiamo ripetere il ragionamento e vediamo che $ a_i=a_{d-2c} $, in generale si può continuare così e a un certo punto si troverà che esiste una stringa più piccola di c se $ c\nmid d $ (assurdo) e una stringa lunga n o 0 se $ c|d $ (ma questo caso si può escludere perchè è banalmente sempre vero). Quindi $ c|d $, a questo punto si può prendere benissimo una collana di lunghezza multipla di c (e lo deve essere, come mostrato da Tibor), ,ma di lunghezza non divisibile per d. Infatti se è soddisfatta la condizione $ a_i=a_{i+c} $ è soddisfatta anche $ a_i=a_{i+qc} $ e quindi $ a_i=a_d $.

Ok?

[Tibor Gallai]

$ a_{i}=a_{d-c} $, quindi esiste una stringa di lunghezza $ d-c $

2 cose:
La premessa ($ a_{i}=a_{d-c} $) equivale a dire che la stringa è costante. Quindi non ci siamo... Non è chiaro come tu l'abbia dedotta, ma è certamente falsa.
La conseguenza (esiste una stringa di lunghezza d-c) non è nemmeno molto chiara... Esistono stringhe di lunghezza d-c a bizzeffe, ma questo che c'entra?

Comunque, a parte i dettagli, il modo di procedere è sconveniente a livello logico. Se devi dimostrare che un'ipotesi è essenziale, in generale è irrilevante che ti poni nel caso in cui quest'ipotesi non vale, e inizi a dedurre roba. Infatti, se per tua fortuna arrivassi a negare la tesi, avresti addirittura rafforzato il teorema di partenza, passando da "Hp1 et Hp2 --> Th" a "Hp1 --> (Hp2 <--> Th)", mentre a te interessa soltanto dimostrare che "Hp1 et not Hp2 -/-> Th" (semplificando, "Hp1 -/-> Th").

Purtroppo in generale le due cose non si equivalgono (come nel nostro caso, perché?). Puoi dunque far vedere che l'ipotesi è essenziale, banalmente esibendo l'esistenza di una stringa che soddisfa Hp1, ma non soddisfa Hp2 e Th, che è un fatto abbastanza debole, ma che ha la decenza d'esser vero.

Esempio: stringa="ababab", n=6, d=4. E' vero che la stringa coincide con la sua rotazione di 4 posizioni, ma non è vero che d=4 è il minimo (infatti la stessa cosa avviene ruotando di 2), e non è vero che d|n.

La stessa costruzione è possibile per qualsiasi n composto, e un'opportuna scelta di d (come?).

[Zorro_93]

Esempio: stringa="ababab", n=6, d=4. E' vero che la stringa coincide con la sua rotazione di 4 posizioni, ma non è vero che d=4 è il minimo (infatti la stessa cosa avviene ruotando di 2), e non è vero che d|n.

Probabilmente sto sbagliando di grosso, però era a quello che stavo pensando in via generale:

-intanto, non ho capito l'obiezione sulla logica: io faccio vedere (o almeno ci provo) che se c'è un numero minimo c e uno più grande d per cui una rotazione di c e di d mi da una collana coincidente allora c|d e quindi non è detto (e qui si può costruire un esempio in 2 secondi) che, se p è il numero di perle, d divida p. E questo dimostra che la minimalità è essenziale perchè si possono costruire casi che non funzionano (come hai fatto tu).

-$ a_i=a_{d-c} $ è una cavolata, è vero, ma credo che sia stato un errore di distrazione:
l'ho dedotto confrontando $ a_i=a_{i+c} $ e $ a_i=a_{i+d} $ (che sono vere per ipotesi), ottengo $ a_{i}=a_{i+d-c} $ (che è anch'essa una probabile cavolata). Arrivo quindi a una forma generale $ $a_i=a_{i+d-nc}$ $ e quindi se $ c\nmidd $ ottengo una relazione $ a_i=a_e $ con $ e<c $ ed è assurdo. Quindi $ c|d $.

[Tibor Gallai]

Allora. Ricapitoliamo.

Diciamo (impropriamente, ma per capirci!) che d>0 è un periodo di una stringa se $ $a_i=a_{i+d} $. Allora, io dimostro che il minimo periodo divide n. E chiedo: l'ipotesi sulla minimalità è essenziale? Che è un altro modo per dire: esistono stringhe con periodo d (non minimo, ovviamente) tali che d non divide n? La risposta è semplicemente: sì, per esempio la stringa "ababab", con d=4.

Poi tu giustamente (modulo refusi) dimostri che ogni periodo è multiplo del minimo periodo, il che è una generalizzazione del mio enunciato, perché n è ovviamente un periodo (e aggiungo che vale il viceversa: ogni multiplo del minimo periodo è un periodo). Questo, per quanto giusto, è slegato dalla mia domanda di cui sopra, ed è superfluo ai fini della mera risposta alla domanda. La risposta alla domanda è il controesempio brutale, puro e semplice, e magari anche dei controesempi per n arbitrariamente alti, se si vuole eccellere in zelo. Puoi fare quelle considerazioni là per "restringere il campo" alla ricerca di un controesempio, ma il controesempio è necessario e sufficiente, e tutto il resto può essere lasciato in brutta senza controindicazioni.

Si può anche aggiungere, completando il discorso, che non è necessario che d sia il minimo periodo affinché valga la tesi, come accennavo nell'altro post. Ad esempio, "abababab" ha come periodo 4, che non è minimo ma divide la lunghezza della stringa.

[Zorro_93]

Ok. Ora mi è chiaro. Grazie mille Tibor della pazienza