Parole che non contengono frasiacaso

Analisi, algebra lineare, topologia, gruppi, anelli, campi, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Parole che non contengono frasiacaso

Messaggio da jordan » 23 gen 2014, 16:26

Sia $S(n)$ l'insieme di stringhe di lettere di lunghezza $n$, anche senza alcun senso, che non contengono "frasiacaso". Mostrare che
$$\lim_{n\to \infty}{|S(n)|^{1/n}}$$
esiste.
The only goal of science is the honor of the human spirit.

Gulliver
Messaggi: 17
Iscritto il: 10 set 2013, 19:08

Re: Parole che non contengono frasiacaso

Messaggio da Gulliver » 24 gen 2014, 03:35

Se consideriamo $24s(n)$ aggiungendo a caso l'ultima lettera ad una stringa ammissibile lunga n, vuol dire che stiamo sbagliando esattamente per le parole contate da s(n) che hanno per ultime 9 lettere "frasiacas" e che noi abbiamo stolidamente completato con "o",d'altronde tali stringhe sono esattamente determinate dal fare stringhe ammissibili lunghe n-9(assumiamo n>9 altrimenti sono $24^i$) e completarle con "frasiacas"(qui usiamo implicitamente che non è una cosa come "frasiacaf").

Pertanto abbiamo trovato la seguente formula $s(n+1)=24s(n)-s(n-9)$ per n>9, altrimenti $s(n)=24^n$ per n<10.
Pertanto sia $F(t)=\sum_{n=1}^{+\infty}s(n)t^n$. Abbiamo che $(24t-t^9)F(t)=F(t)-24t$. Quindi abbiamo $F(t)=\frac{24t}{t^9-24t+1}$. Osservando che la frazione è scomposta ai minimi termini, abbiamo che è sufficente dimostrare che $t^9-24t+1$ ha la radice di minimo modulo reale(segue subito dall'espansione in fratti semplici). Usando http://en.wikipedia.org/wiki/Argument_principle: abbiamo che sul cerchio unitario non vi sono zeri($t^9+1=24t$ passando ai moduli e alla disuguaglianza triangolare si ha 2 a sinistra maggiore di 24 a destra assurdo); pertanto integriamo lì ed abbiamo $\frac{1}{2i\pi}\int_{S^1}\frac{9z^8-24}{z^9-24z+1}dz$,stimando sopra e sotto brutalmente con la disuguaglianza triangolare(sotto messa al contrario,cioè con quella con le differenze, per minimizzare ovviamente) si ha (9+24)/22=33/22, quindi il numero di zeri nel cerchio unitario è(ovviamente)un intero, al più 33/22, quindi è al più 1.
D'altronde valutando $t^9-24t+1$ in 0 e 1, si trova che vi è una radice in (0,1). Quindiabbiamo una radice reale di modulo minimo,$\alpha$.
Dunque sviluppando in fratti semplici abbiamo che $s(n)=A(\frac{1}{\alpha})^n+A_2(\frac{1}{\alpha_2})^n+...+A_9(\frac{1}{\alpha_9})^n$. Raggruppiamo dal secondo addendo in poi, che sarò un numero reale il cui andamento in funzione di n è maggiorato da un esponenziale di base minore di $\frac{1}{\alpha}$.

Pertanto prendendo le radici n-esime scompare pure la costante A, ed otteniamo al limite $\frac{1}{\alpha}$.
Ammetto che alcuni conti li ho fatti di fretta, ci potrebbero essere sviste abbastanza serie(forse un modo veloce per stabilirlo è se a jordan torna il risultato finale)
Ciao!
p.s:è confortante aggiungere che $t^9-24t+1$ è positiva in $1/24$ che avendosi derivata negativa in (0,1), ci dà che $1/24<\alpha$ quindi $\frac{1}{\alpha}<24$, come deve essere(col minore uguale)in modo ovvio dal fatto che $s(n)<(24)^n$.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Parole che non contengono frasiacaso

Messaggio da jordan » 30 gen 2014, 00:32

Gulliver ha scritto:...pertanto integriamo lì ed abbiamo $$\frac{1}{2i\pi}\int_{S^1}\frac{9z^8-24}{z^9-24z+1}dz$$stimando sopra e sotto brutalmente con la disuguaglianza triangolare(sotto messa al contrario,cioè con quella con le differenze, per minimizzare ovviamente) si ha (9+24)/22=33/22,...
Mi manca un pezzo di teoria per capire la tua soluzione; immagino che $S^1$ sia $\{z \in \mathbb{C}\colon |z|=1\}$, ma il resto? Cioè, perchè si sceglie quell'integrale, come si calcola, come si fanno gli upper e lower bound?

Ps. La mia soluzione è del tutto diversa, e non calcola quant'è esattamente il limite..
The only goal of science is the honor of the human spirit.

Gulliver
Messaggi: 17
Iscritto il: 10 set 2013, 19:08

Re: Parole che non contengono frasiacaso

Messaggio da Gulliver » 30 gen 2014, 15:42

Qui http://en.wikipedia.org/wiki/Argument_principle spiega abbastanza bene.

Questo è un argomento su cui si può andare avanti per ore, sotto ti ho provato a scrivere i conti e un minimo di euristica, però se vuoi vedere davvero bene la storia penso che ti piacerà studiare un libro di analisi complessa(il Conway dovresti trovarlo sui soliti siti, ed io mi sono trovato bene, anche il libro di Elias Stein, Complex analisys è molto buono a mio avviso).
In 1) ti dico come si calcola quell'integrale, come coppia di integrali usuali(parte reale e parte immaginaria). Ti dò subito un esempio che è quello chiave che genera la formula che ho usato e che ti dà un minimo di motivazione alla domanda "da dove salta fuori tutta questa roba?"(risposta "dal provare a definire il logaritmo sui complessi"), motivazione che provo goffamente a spiegarti nella parentesi in 1) e nella parentesi in 3)(ma se vuoi vedere tutt per benino è meglio prendere un libro). In 2) aggiungo una postilla a 1) che serve per darti un accenno di dimostrazione della formula in 3)(2) corrisponde a" cosa comporta il fatto di poter definire su alcune regioni il logaritmo" ). In 4) uso quanto detto in 1) e 3) per fare i conti sul mio polinomio. In p.s ti dico a chi è iniziata a venire in mente questa roba e come l'ha usata per trovare un teorema importante.

1)Ora prima di tutto della notazione per scrivere conti espliciti sotto: se hai una curva $z=\gamma(t)$ allora hai che $dz=d\gamma(t)=\gamma'(t)dt$. Quindi quella formula indica $\int_{\gamma}f(z)dz=\int_{a}^{b}f(\gamma(t))\gamma'(t)dt$ dove $\gamma:[a,b] \to \mathbb{C}$ è una curva(con sufficente grado di derivabilità), il che ti risponde alla domanda "come si calcolano quegli integrali scritti in quel modo?". Ora considera come C la circonferenza unitaria parametrizzata al solito come $\gamma(t)=e^{2\pi i t}$. Ora considera $\int_{C}\frac{1}{z}dz$ ossia il calcolo che ho fatto io con i polinomio $f(z)=z$, ottieni $\int_{0}^{1}\frac{1}{e^{2\pi i t}}2\pi ie^{2\pi i t}dt=2\pi i$.
Parentesi on Ti invito incidentalmente(ma qui è il cuore della faccenda)a osservare che $\frac{1}{z}$ è formalmente la derivata di log(z), però non potrà esserlo analiticamente su tutto il piano senza lo 0, perchè se lo fosse l'ultimo integrale farebbe 0(l'integrale su una curva di f' farebbe la differenza di f agli estremi, quindi 0 su una curva chiusa:$\int_{a}^{b}f'(\gamma(t))\gamma'(t)dt=\int_{a}^{b}\frac{d}{dt}(f(\gamma(t))dt=f(\gamma(b))-f(\gamma(a))$ dunque 0 se $\gamma(a)=\gamma(b)$). Parallelamente immagina la seguente cosa:supponi di voler definire il logaritmo sulla circonferenza unitaria, definiscilo in 1 come 0, e inizia a muoverti sulla circonferenza in senso antiorario e definisci nel modo naturale il log di $e^{2\pi i t}$ come $2\pi i t$, quando ritorni a casa per t=1, hai come sorpresa che il logaritmo fa $2\pi i$ e non di nuovo 0, questo ti dice euristicamente perchè non lo potrai definire e ti dice da dove salta fuori quel $2\pi i$: tu non lo puoi definire esattamente perchè al termine di ogni giro devi aggiungere un intero, e nei conti questo ti ritorna come, se integro quella che formalmente è la sua derivata su un cerchio ottengo un multiplo intero di $2\pi i$ che corrisponde al numero di giri che ho fatto. Tutto questo si può ripetere per ogni curva(http://en.wikipedia.org/wiki/Winding_number, guarda la parte complex analisys) e corrisponde al fatto che il gruppo fondamentale della circonferenza http://en.wikipedia.org/wiki/Fundamental_group è $\mathbb{Z}$. Parentesi off

2)Però come hai visto non dappertutto ma in parte il logaritmo lo puoi definire(perchè non hai più il problema di ritornare a casa con un valore dell'angolo aumentato di $2\pi$), ad esempio se su un cerchio molto lontano dall'origine che non ha l'origine all'interno, puoi definire al bordo il logaritmo e trovi quindi, per quanto detto prima, che l'integrale di $1/z$ su quel cerchio ti verrà 0(in quanto integrale della derivata di una funzione, su un percorso chiuso)

3)Ora quello che succede è che se consideri $\frac{p'(z)}{p(z)}=\sum_{\alpha,p(\alpha)=0}\frac{m(\alpha)}{z-\alpha}$, dove $m(\alpha)$ è la molteplicità; con p un polinomio(si può fare più in generale). Ora se integri diciamo sulla circonferenza unitaria $\frac{p'(z)}{p(z)}=\sum_{\alpha,p(\alpha)=0}\frac{m(\alpha)}{z-\alpha}$ porti l'integrale dentro la somma, e ottieni che per 1) le radici interne al cerchio danno contributo(ciascua) $2\pi im(\alpha)$, quelle fuori al cerchio per 2) danno contributo nullo(ah e bisogna sincerarsi che non ce ne sono sul bordo, verifica che io ho fatto al primo post). Quindi in totale hai realizzato che quell'integrale $\int_{C}\frac{p'(z)}{p(z)}$ sulla circonferenza unitaria parametrizzata con un solo giro(sennò dovresti moltiplicare il tutto per il numero di giri) ti ridà $2\pi i(\sum_{|\alpha_i|<1}m(\alpha))$.

Parentesi onIncidentalmente ti faccio notare che $f'(z)/f(z)$ è formalmente la derivata del logaritmo di f(z). Quindi $\int_{C}\frac{f'(z)}{f(z)}dz$ corrisponde al numero di giri attorno all'origine della curva f(C) e puoi fare usando 2) e 1) un discorso completamente euristico che giustifica perchè il numero di zeri interni a C, corrisponde al numero di volte che f(C) si avvolge attorno all'origine(questo spero ti dia una risposta non solo formale alla domanda perchè considerare quel rapporto: la risposta è che quel rapporto è formalmente la derivata di log(f) e analiticamente questa cosa non è vera e non è vera esattamente perchè log(f) riesce a essere definita solo a patto di segnalare il numero di volte in cui f ti fa avvolgere la regione attorno all'origine(e questo ti dovrebbe uscire chiaro dal cosa manca al logaritmo per essere definito)e questa cosa corrisponde al numero di volte che f si annulla nella tua regione(gli esempi $z,z^2,..,z^n$ nel conto a 1) dovrebbero essere illuminanti, la funzione $z^n$ ti fa avvolgere il disco unitario n volte attorno a se stesso, avendo uno zero interno di molteplicità n, ora se f è prodotto di $(z-a_1)^{n_1}...(z-a_m)^{n_m}$, con $a_i$ interni, allora ciascun fattore da un contributo di $n_i$ e questi contributi si sommano). Se questo ti ha incuriosito, ti consiglio di passare alla lettura di un libro rigoroso(se hai tempo). Parentesi off

4)Sfruttando 3) ho che $\int_{0}^{1}\frac{9e^{8(2\pi it)}-24}{e^{9(2\pi it)}-24e^{2\pi it}+1}e^{2\pi i t}dt$(ho usato la formula in 1) e semplificato il $2\pi i$ che viene dalla derivata di $e^{(2\pi it)}$), mi dà il numero di zeri interni al disco unitario. Ora uso la disuguaglianza triangolare $|\int_{0}^{1}h(t)dt|\leq \int_{0}^{1}|h(t)|dt$(la puoi ottenere usando quella classica per le approssimazioni con somme finite dell'integrale e portarle al limite). Ora uso sul numeratore a sua volta la disuguaglianza triangolare avendo che $|9e^{8(2\pi it)}-24| \leq |9e^{8(2\pi it)}|+|24|=33$, poi sul denominatore debbo trovare il modulo minimo per maggiorare, quindi $|-e^{9(2\pi it)}+24e^{2\pi it}-1| \geq ||24|-|(e^{9(2\pi it)}+1)||\geq 22$(l'ultimo pezzo ha modulo al più 2 sempre per disuguaglianza triangolare). Quindi abbiamo che punto per punto $|\frac{9e^{8(2\pi it)}-24}{e^{9(2\pi it)}-24e^{2\pi it}+1}e^{2\pi i t}|=\frac{|9e^{8(2\pi it)}-24|}{|e^{9(2\pi it)}-24e^{2\pi it}+1|}|e^{2\pi i t}| \leq \frac{33}{22}$, pertanto otteniamo che $|\int_{0}^{1}\frac{9e^{8(2\pi it)}-24}{e^{9(2\pi it)}-24e^{2\pi it}+1}e^{2\pi i t}dt| \leq \int_{0}^{1}\frac{3}{2}dt=\frac{3}{2} $. Pertanto dovendo essere il numero di zeri interni, e quindi un numero intero nonnegativo, otteniamo che vale o 0 oppure 1. Dopodichè studio la funzione in (0,1) per ottenere che lì ha uno zero(fortunatamente maggiore di $1/24$ dato il valore del limite). E quindi tutto questo per dire che la funzione ha uno e un solo zero di minimo modulo che risulta reale(anzi è sufficente dire che ha un solo zero di minimo modulo, a quel punto è per forza reale dato che il polinomio è a coefficenti reale e quindi gli zeri complessi si accoppiano in coniugati). Da lì con la scomposizione in fratti semplici ho che l'inverso di questa radice domina l'espressione ed è il risultato del limite(come esempio opposto si pensi un polinomio con 9 radici su un 9-agono regolare centrato in 0, le cui somme di potenze alternano tra 0 e $9/r^n$ dove r è la distanza dall'origine e compare ai multipli di 9, e il resto fa 0, quindi in tal caso se r<1, il limite non esisteva, ecco perchè ho usato questo argomento per dimostrare che c'era una radice reale isolata che dominava l'espressione non interagendo con le altre potenze.
Ciao!

p.s:E' interessante notare che tutto il discorso in 3) risale a Gauss, e infatti un'applicazione carina è il teorema fondamentale dell'algebra: prendi un cerchio di raggio enorme, allora hai che $p'(z)/p(z)$ va asintoticamente come n/z, e il cerchio ti dà un contributo lineare nella distanza dall'origine che semplifica il denominatore, e quindi asintoticamente ottieni $lim_{r \to +\infty}\int_{rS^1}\frac{p'(z)}{p(z)}dz=2\pi in$. Ossia dato un polinomio per un cerchio abbastanza grande vi sono n radici(contate con molteplicità). In altri termini l'idea è che su un cerchio abnormemente grande, l'effetto di un polinomio, in termini di avvolgimento attorno all'origine quando applicato sul cerchio, è dato dal termine di grado più alto(perchè gli altri possono essere pensati come una perturbazione asintoticamente irrilevante), e quindi l'effetto, in termini di avvolgimento attorno all'origine, è quello della funzione $z^{deg(p)}$, cioè deg(p) avvolgimenti, ma una volta compreso che questo corrisponde al numero di zeri(come abbozzato in 3)) si ottiene chiaramente il teorema fondamentale dell'algebra.

Rispondi