appunti stage
- mattilgale
- Messaggi: 372
- Iscritto il: 01 gen 1970, 01:00
- Località: Lucca
- Contatta:
appunti stage
sto lentamente ricopiando tutti i miei appunti dello stage...
e incontro lacune di argomenti lontanissimi... ed anche banali dimostrazioni che non riesco a farmi da solo
ne mtto una prima carrellata
1.qualcuno sa dove posso trovare un dimostrazione completa del Bunching in italiano???
2.media dei cicli in cui può essere scomposta una permutazione in S_n (numeri di Stirling???)
in pratica ci avevate spigato che la media è (ovviamente questo)
$ \displaystyle\frac{1}{n!}\sum_{k=1}^nkf(n,k) $
dove f(n,K)={permutazioni in S_n che si decompongono in k cicli}
dopodichè si vedeva come
$ \displaystylef(n+1,k)=f(n,k-1)+nf(n,k) $
e fin qui, con un po' di difficoltà ma ci arrivo
solo che dopo non riesco a sviluppare la sommatoria ed a dimostrare che
$ \displaystyle\mu(n)=\frac{1}{n!}\sum_{k=1}^nkf(n,k)=\mu(n-1)+\frac{1}{n} $
3.cosa significa fare una media pesata???
4. come si dimostra che esistono infinite frazioni
$ \displaystyle\frac{p_n}{q_n} t.c. \left|\alpha-\frac{p_n}{q_n}\right|<=\frac{1}{q_n^2} $
?
alpha è ovviamente irrazionale... all'esistenza ci arrivo, ma all'infinità no
per ora mi fermo qui
lo so che alcuni sono anche inutili come chiarimenti però sto cercando di apprendere + cose possibili per avere sempre chiaro come giungo a qualcosa...
grazioe 10^3 a chiunque mi aiuterà
e ancjhe agli altri
e incontro lacune di argomenti lontanissimi... ed anche banali dimostrazioni che non riesco a farmi da solo
ne mtto una prima carrellata
1.qualcuno sa dove posso trovare un dimostrazione completa del Bunching in italiano???
2.media dei cicli in cui può essere scomposta una permutazione in S_n (numeri di Stirling???)
in pratica ci avevate spigato che la media è (ovviamente questo)
$ \displaystyle\frac{1}{n!}\sum_{k=1}^nkf(n,k) $
dove f(n,K)={permutazioni in S_n che si decompongono in k cicli}
dopodichè si vedeva come
$ \displaystylef(n+1,k)=f(n,k-1)+nf(n,k) $
e fin qui, con un po' di difficoltà ma ci arrivo
solo che dopo non riesco a sviluppare la sommatoria ed a dimostrare che
$ \displaystyle\mu(n)=\frac{1}{n!}\sum_{k=1}^nkf(n,k)=\mu(n-1)+\frac{1}{n} $
3.cosa significa fare una media pesata???
4. come si dimostra che esistono infinite frazioni
$ \displaystyle\frac{p_n}{q_n} t.c. \left|\alpha-\frac{p_n}{q_n}\right|<=\frac{1}{q_n^2} $
?
alpha è ovviamente irrazionale... all'esistenza ci arrivo, ma all'infinità no
per ora mi fermo qui
lo so che alcuni sono anche inutili come chiarimenti però sto cercando di apprendere + cose possibili per avere sempre chiaro come giungo a qualcosa...
grazioe 10^3 a chiunque mi aiuterà
e ancjhe agli altri
"la matematica è il linguaggio con cui Dio ha plasmato l'universo"
Galileo Galilei
Galileo Galilei
- FrancescoVeneziano
- Site Admin
- Messaggi: 606
- Iscritto il: 01 gen 1970, 01:00
- Località: Genova
- Contatta:
Re: appunti stage
Dunque, si tratta solo di armeggiare con le sommatorie. Scrivo qui i passaggi, se qualche uguaglianza non ti torna dimmi puremattilgale ha scritto: 2.media dei cicli in cui può essere scomposta una permutazione in S_n (numeri di Stirling???)
in pratica ci avevate spigato che la media è (ovviamente questo)
$ \displaystyle\frac{1}{n!}\sum_{k=1}^nkf(n,k) $
dove f(n,K)={permutazioni in S_n che si decompongono in k cicli}
dopodichè si vedeva come
$ \displaystylef(n+1,k)=f(n,k-1)+nf(n,k) $
e fin qui, con un po' di difficoltà ma ci arrivo
solo che dopo non riesco a sviluppare la sommatoria ed a dimostrare che
$ \displaystyle\mu(n)=\frac{1}{n!}\sum_{k=1}^nkf(n,k)=\mu(n-1)+\frac{1}{n} $
$ \displaystyle\mu(n)=\frac{1}{n!}\sum_{k=1}^nkf(n,k)= $
$ \displaystyle\frac{1}{n!}\sum_{k=1}^nkf(n-1,k-1)+\frac{1}{n!}\sum_{k=1}^nk(n-1)f(n-1,k)= $
$ \displaystyle\frac{1}{n!}\sum_{k'=0}^{n-1}(k'+1)f(n-1,k')+\frac{n-1}{n}\frac{1}{(n-1)!}\sum_{k=1}^{n-1}kf(n-1,k)= $
$ \displaystyle\frac{1}{n}\frac{1}{(n-1)!}\sum_{k'=1}^{n-1}k'f(n-1,k')+\frac{1}{n!}\sum_{k'=0}^{n-1}f(n-1,k') $$ \displaystyle+\frac{n-1}{n}\frac{1}{(n-1)!}\sum_{k=1}^{n-1}kf(n-1,k)= $
$ \displaystyle\frac{1}{n}\mu(n-1)+\frac{1}{n}+\frac{n-1}{n}\mu(n-1)=\mu(n-1)+\frac{1}{n} $
Wir müssen wissen. Wir werden wissen.
- mattilgale
- Messaggi: 372
- Iscritto il: 01 gen 1970, 01:00
- Località: Lucca
- Contatta:
- mattilgale
- Messaggi: 372
- Iscritto il: 01 gen 1970, 01:00
- Località: Lucca
- Contatta:
Ammettiamo $ p\equiv 1 \bmod 2 $. Se $ \gcd(b,p) = 1 $, dal piccolo teorema di Fermat: $ p \mid (b^{(p-1)/2}-1)(b^{(p+1)/2}+1) $, ovvero $ p \mid (b^{(p-1)/2}-1) $ oppure $ p \mid (b^{(p-1)/2}+1) $, per il lemma di Euclide. Eppure $ b $ non è un residuo quadratico $ \bmod\;\! p $, , dunque a forza $ p \mid (b^{(p-1)/2}+1) $. Ne risulta la tesi.
1) se la trovi, faccelo sapere! io non ne ho mai vista una, neppure in inglese.. forse potrei guardare se su "inequalities" c'è, ma non credo.. (controllerò).
3) fare una media pesata..
beh, intanto devi assegnare dei pesi.. comunque, quella che facevi al punto 1, riguardo alla media dei cicli, _è_ una media pesata: stai facendo la media del numero di cicli, pesando tale numero col numero di permutazioni che ci hai associato...
in generale, se ad $ a_1, \dots, a_n $ hai assegnato dei pesi $ \mu_1, \dots, \mu_n $, chiami media pesata degli $ a_k $ (rispetto ai pesi $ \mu_k $) la quantità $ \displaystyle M(a,\mu) = \frac{\displaystyle\sum_{k=1}^n \mu_k a_k}{\displaystyle\sum_{k=1}^n \mu_k} $.
4) in realtà c'è un altro enunciato, più preciso: per ogni $ n $ esistono $ p,q \in \mathbb{N} $ tali che $ \left|\alpha - \frac{p}{q}\right| < \frac1{q(n+1)} $, e da questo segue l'infinità... (perché? a voi...)
riguardo all'ultima questione...
dunque, se $ a $ è un residuo quadratico $ \mod p $, allora esiste $ x | x^2 \equiv a (\mod p) $. inoltre, per ogni $ n \not\equiv 0 (\mod p) $, $ n^{p-1} \equiv 1 (\mod p) $, quindi in particolare $ x^{p-1} = a^{\frac{p-1}2} = 1 (\mod p) $.
adesso, il piccolo teorema di fermat ti dice anche che $ x^{p-1} \equiv 1 $, quindi $ \left(x^{\frac{p-1}2} + 1\right)\left(x^{\frac{p-1}2} - 1\right) \equiv 0 $, quindi o $ \left(x^{\frac{p-1}2} - 1\right) \equiv 0 $ (*) o $ \left(x^{\frac{p-1}2} - 1\right) \equiv 0 $ (**).
ora, si dimostra che i residui quadratici $ \mod p $ sono $ \frac{p-1}2 $ (fallo!), e siccome i residui non hanno divisori dello zero (... qualcuno potrebbe bastonarmi per quello che dico, però intuitivamente funziona, circa), allora, un'equazione di grado $ k $ ha al più $ k $ soluzioni. ma tu hai $ \frac{p-1}2 $ soluzioni della (*), quindi le altre $ \frac{p-1}2 $ classi di resto sono soluzioni della (**), quindi i non residui hanno quella proprietà.
3) fare una media pesata..
beh, intanto devi assegnare dei pesi.. comunque, quella che facevi al punto 1, riguardo alla media dei cicli, _è_ una media pesata: stai facendo la media del numero di cicli, pesando tale numero col numero di permutazioni che ci hai associato...
in generale, se ad $ a_1, \dots, a_n $ hai assegnato dei pesi $ \mu_1, \dots, \mu_n $, chiami media pesata degli $ a_k $ (rispetto ai pesi $ \mu_k $) la quantità $ \displaystyle M(a,\mu) = \frac{\displaystyle\sum_{k=1}^n \mu_k a_k}{\displaystyle\sum_{k=1}^n \mu_k} $.
4) in realtà c'è un altro enunciato, più preciso: per ogni $ n $ esistono $ p,q \in \mathbb{N} $ tali che $ \left|\alpha - \frac{p}{q}\right| < \frac1{q(n+1)} $, e da questo segue l'infinità... (perché? a voi...)
riguardo all'ultima questione...
dunque, se $ a $ è un residuo quadratico $ \mod p $, allora esiste $ x | x^2 \equiv a (\mod p) $. inoltre, per ogni $ n \not\equiv 0 (\mod p) $, $ n^{p-1} \equiv 1 (\mod p) $, quindi in particolare $ x^{p-1} = a^{\frac{p-1}2} = 1 (\mod p) $.
adesso, il piccolo teorema di fermat ti dice anche che $ x^{p-1} \equiv 1 $, quindi $ \left(x^{\frac{p-1}2} + 1\right)\left(x^{\frac{p-1}2} - 1\right) \equiv 0 $, quindi o $ \left(x^{\frac{p-1}2} - 1\right) \equiv 0 $ (*) o $ \left(x^{\frac{p-1}2} - 1\right) \equiv 0 $ (**).
ora, si dimostra che i residui quadratici $ \mod p $ sono $ \frac{p-1}2 $ (fallo!), e siccome i residui non hanno divisori dello zero (... qualcuno potrebbe bastonarmi per quello che dico, però intuitivamente funziona, circa), allora, un'equazione di grado $ k $ ha al più $ k $ soluzioni. ma tu hai $ \frac{p-1}2 $ soluzioni della (*), quindi le altre $ \frac{p-1}2 $ classi di resto sono soluzioni della (**), quindi i non residui hanno quella proprietà.
- mattilgale
- Messaggi: 372
- Iscritto il: 01 gen 1970, 01:00
- Località: Lucca
- Contatta:
- mattilgale
- Messaggi: 372
- Iscritto il: 01 gen 1970, 01:00
- Località: Lucca
- Contatta:
Questo è in generale falso, se non metti che il modulo è primo. Ad esempio: le "radici quadrate" di 1 modulo 8 sono 1, 3, 5, 7.mattilgale ha scritto:ma si può passsare senza difficoltà anche sulle congruenze che un'equazione di grado k ha al + k soluzioni???????????
Invece, se metti che il modulo è primo, allora la dimostrazione classica sui reali (quella che usa il Teorema di Ruffini, per capirci...) funziona anche per i polinomi a coefficienti interi mod. p.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Ciao anche a te. Non sono del tutto d'accordo. Escludiamo il caso anomalo del polinomio nullo (che non ha un grado ben definito e quindi le considerazioni avrebbero poco senso...).HiTLeuLeR ha scritto:bisogna imporre che il polinomio non sia identicamente congruo a zero
In tutti gli altri casi torna: anche se il polinomio fosse identicamente nullo mod. p senza essere il polinomio nullo, allora avrebbe almeno grado p e quindi ha al più tante soluzioni quanto il grado. Non è un controsempio.
E del resto:
-----------------------------
Teorema: Sia f(x) un polinomio non nullo di grado d a coefficienti negli interi mod. p (dove p è un primo). Allora f() ha al massimo d radici.
Dim.: Per induzione sul grado. Se d = 0, allora f è costante e, dato che non è nullo, allora non ha radici.
Supponiamo il teorema vero fino al grado d-1. Sia allora f di grado d. Se f non ha radici, allora la tesi è vera, in quanto 0 <= d.
Supponiamo allora che f(a) = 0 (mod. p) per a un'opportuna classe di resto mod. p.
Usando il Teorema di Ruffini (o la regola del resto, o la divisione dei polinomi o qualunque altra roba equivalente), si ricava che f(x) è multiplo di (x-a) e f(x) = (x-a) g(x), per un opportuno g(x) polinomio mod.p di grado <= d-1. Ovviamente g(x) non è il polinomio nullo (altrimenti anche f lo sarebbe).
Mi sono così ricondotto al caso con grado inferiore, quindi vale l'ipotesi induttiva e g ha al massimo d-1 radici.
Del resto, l'insieme delle radici di f è l'insieme delle radici di g, con l'aggiunta eventuale di a. Perciò f ha al massimo d radici. []
-----------------------------
[mode=non-olimpic] Perché la dimostrazione funzioni, serve solo che si possa fare la classica divisione dei polinomi (e, a dirla giusta, nemmeno una divisione generica, ma la divisione per polinomi lineari; gran lusso!....).
La qual cosa è vera da qualunque campo si vadano a pigliare i coefficienti dei polinomi. Non serve che valga il principio di identità dei polinomi (come in Z/p) oppure che il campo sia di char 0 o perfetto. [/mode]
-----------------------------
Detto questo, esercizio per Mattilgale: dove fallisce la dimostrazione se p non è primo?
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Re: appunti stage
Non è necessario!mattilgale ha scritto: alpha è ovviamente irrazionale...
Prova a dimostrarlo anche per i razionali, automaticamente avrai una risposta per il tuo quesito originale.
-
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
4. (scusa se non ti ho risp prima (via e-mail dico) ma non riesco più ad accederci da lì... )
Allora, diciamo che hai trovato il tuo $ q_1 $ tale che ci sia il $ p_1 $ tale che $ \displaystyle |\alpha - \frac{p_1}{q_1} | \leq \frac 1{q_1^2} $
e diciamo che sia tale che $ \displaystyle |\alpha - \frac{p_1}{q_1} | > \frac 1{k_1} $ per un certo $ k_1\in N_0 $. Ora, riapplicando il procedimento noto prendendo $ k_1 $ come parti in cui divido $ (0,1) $ otterremo un $ q_2 $ e un $ p_2 $ tali che $ \displaystyle |\alpha - \frac{p_1}{q_1} | \leq \frac 1{k_1q_2} \leq \frac 1{q_2^2} $
Ma la prima parte della disuguaglianza ci dice che $ q_2 \neq q_1 $ altrimenti avremmo l'assurdo. Spero si sia capito bene tutto
Se ti può aiutare, il bounching in inglese si chiama disuguaglianza di Muirhead mi pare...
Allora, diciamo che hai trovato il tuo $ q_1 $ tale che ci sia il $ p_1 $ tale che $ \displaystyle |\alpha - \frac{p_1}{q_1} | \leq \frac 1{q_1^2} $
e diciamo che sia tale che $ \displaystyle |\alpha - \frac{p_1}{q_1} | > \frac 1{k_1} $ per un certo $ k_1\in N_0 $. Ora, riapplicando il procedimento noto prendendo $ k_1 $ come parti in cui divido $ (0,1) $ otterremo un $ q_2 $ e un $ p_2 $ tali che $ \displaystyle |\alpha - \frac{p_1}{q_1} | \leq \frac 1{k_1q_2} \leq \frac 1{q_2^2} $
Ma la prima parte della disuguaglianza ci dice che $ q_2 \neq q_1 $ altrimenti avremmo l'assurdo. Spero si sia capito bene tutto
Se ti può aiutare, il bounching in inglese si chiama disuguaglianza di Muirhead mi pare...
- mattilgale
- Messaggi: 372
- Iscritto il: 01 gen 1970, 01:00
- Località: Lucca
- Contatta:
marco: credo che la dim fallisca perchè se f(a)==0 (mod m) con m non primo NON è detto che f(x) sia divisibile per (x-a)... perchè dato un generico prodotto
ab==0 (mod m)
se m è qualsiasi NON si sa nulla, mentre se m è primo bisogna che a==0 (m) o b==0 (m) ...
SImo: credo dia ver capito alla lontana... stasera me lo rileggo con calma
ma "inequalities" è un libro?? un sito??
grazie mille a tutti per l'aiuto!!
ab==0 (mod m)
se m è qualsiasi NON si sa nulla, mentre se m è primo bisogna che a==0 (m) o b==0 (m) ...
SImo: credo dia ver capito alla lontana... stasera me lo rileggo con calma
ma "inequalities" è un libro?? un sito??
grazie mille a tutti per l'aiuto!!
"la matematica è il linguaggio con cui Dio ha plasmato l'universo"
Galileo Galilei
Galileo Galilei