appunti stage

[mattilgale]

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

[FrancescoVeneziano]

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} $

[mattilgale]

grazie 10^3

non so perchè mi ero bloccato.. mah

vabbeh, comunque c'è nessuno che mi aiuta sugli altri punti???

[mattilgale]

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) $

[HiTLeuLeR]

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]

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

[mattilgale]

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

[mattilgale]

e grazie mille

[Marco]

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.

[HiTLeuLeR]

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!

[Marco]

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?

[Azarus]

alpha è ovviamente irrazionale...

Non è necessario!

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

[Simo_the_wolf]

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

[talpuz]

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

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

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ò

[mattilgale]

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