appunti stage

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Avatar utente
mattilgale
Messaggi: 372
Iscritto il: 01 gen 1970, 01:00
Località: Lucca
Contatta:

appunti stage

Messaggio da mattilgale » 21 ott 2005, 20:50

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à :D :D :D :D :D :D
e ancjhe agli altri
"la matematica è il linguaggio con cui Dio ha plasmato l'universo"

Galileo Galilei

Avatar utente
FrancescoVeneziano
Site Admin
Messaggi: 600
Iscritto il: 01 gen 1970, 01:00
Località: Pisa
Contatta:

Re: appunti stage

Messaggio da FrancescoVeneziano » 21 ott 2005, 22:24

mattilgale 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} $
Dunque, si tratta solo di armeggiare con le sommatorie. Scrivo qui i passaggi, se qualche uguaglianza non ti torna dimmi pure

$ \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.

Avatar utente
mattilgale
Messaggi: 372
Iscritto il: 01 gen 1970, 01:00
Località: Lucca
Contatta:

Messaggio da mattilgale » 22 ott 2005, 13:36

grazie 10^3

non so perchè mi ero bloccato.. mah

vabbeh, comunque c'è nessuno che mi aiuta sugli altri punti???
"la matematica è il linguaggio con cui Dio ha plasmato l'universo"

Galileo Galilei

Avatar utente
mattilgale
Messaggi: 372
Iscritto il: 01 gen 1970, 01:00
Località: Lucca
Contatta:

Messaggio da mattilgale » 23 ott 2005, 18:21

e già che ci siamo...

qualcun mette la dimostrazione di perchè dato b, un non residuo quadratico mod p


$ \displaystyle b^{\frac{p-1}{2}}\equiv-1\ \ (mod\ p) $
"la matematica è il linguaggio con cui Dio ha plasmato l'universo"

Galileo Galilei

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 23 ott 2005, 18:42

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.

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go » 23 ott 2005, 18:58

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à.

Avatar utente
mattilgale
Messaggi: 372
Iscritto il: 01 gen 1970, 01:00
Località: Lucca
Contatta:

Messaggio da mattilgale » 24 ott 2005, 16:54

il discorso è chiaro... la soluzione del fatto che i residui quadratici sono (p-1)/2 la so...
ma si può passsare senza difficoltà anche sulle congruenze che un'equazione di grado k ha al + k soluzioni???????????
"la matematica è il linguaggio con cui Dio ha plasmato l'universo"

Galileo Galilei

Avatar utente
mattilgale
Messaggi: 372
Iscritto il: 01 gen 1970, 01:00
Località: Lucca
Contatta:

Messaggio da mattilgale » 24 ott 2005, 16:55

e grazie mille :D :D :D :D :D :D :D :D
"la matematica è il linguaggio con cui Dio ha plasmato l'universo"

Galileo Galilei

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 24 ott 2005, 17:08

mattilgale ha scritto:ma si può passsare senza difficoltà anche sulle congruenze che un'equazione di grado k ha al + k soluzioni???????????
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.

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."

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 24 ott 2005, 17:59

Beh, anche detto così non è che vada granché bene, Marco... Comunque bisogna imporre che il polinomio non sia identicamente congruo a zero $ \bmod\;\! p $. Dicesi teorema di Lagrange: nulla di straordinario, in fondo in fondo...

Comunque ciao! :wink:

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 25 ott 2005, 07:49

HiTLeuLeR ha scritto:bisogna imporre che il polinomio non sia identicamente congruo a zero
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...).

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."

Azarus
Messaggi: 580
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Re: appunti stage

Messaggio da Azarus » 26 ott 2005, 15:07

mattilgale ha scritto: alpha è ovviamente irrazionale...
Non è necessario!

Prova a dimostrarlo anche per i razionali, automaticamente avrai una risposta per il tuo quesito originale.

Simo_the_wolf
Moderatore
Messaggi: 1019
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf » 26 ott 2005, 20:10

4. (scusa se non ti ho risp prima (via e-mail dico) ma non riesco più ad accederci da lì... :oops: )

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...

Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz » 27 ott 2005, 00:04

una volta per tutte: si scrive BUNCHING!!!!!!!!!!! non bOunching!!

non c'è nulla che rimbalza, solo cose che vengono "raggruppate" :P :P

comunque su Inequalities sono abbastanza sicuro che la dimostrazione ci sia, anche se sinceramente non ho mai trovato la forza per leggerla.. prima o poi lo farò :wink:

Avatar utente
mattilgale
Messaggi: 372
Iscritto il: 01 gen 1970, 01:00
Località: Lucca
Contatta:

Messaggio da mattilgale » 27 ott 2005, 15:48

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 :D

ma "inequalities" è un libro?? un sito??

grazie mille a tutti per l'aiuto!! :wink: :lol: :D
"la matematica è il linguaggio con cui Dio ha plasmato l'universo"

Galileo Galilei

Rispondi