da ficus2002 » 13/04/2006, 20:46
Bisogna stimare la cardinalità dell'insieme
${(alpha,beta):p^alpha \cdot q^beta \le s}$
Per ogni $alpha$ tale che $p^alpha\le s$ si ha $q^beta\le s/(p^alpha)$ per ogni $beta=0,1,\ldots,[log (s/p^alpha)/log q]$. Inoltre si ha $p^alpha\le s$ per $alpha=0,1,\ldots,[log (s/p^alpha)]$. Quindi la cardinalità dell'insieme vale $sum_{alpha=0}^{[log s/log p]}[log (s/p^alpha)/log q]$.
Ora osserviamo che $sum_{alpha=0}^{[log s/log p]}log (s/p^alpha)/log q=1/2 (log^2 s) / (log p log q) - 1/2 log s / log q$.
Premettiamo questo
Lemma: Sia $a_k$ una successione. Se definitivamente è $sum_{k=0}^{n} a_n > c n$ per qualche costante $c>1$ allora $sum_{k=0}^{n} [a_k]$ e $sum_{k=0}^{n} a_k$ sono asintotiche per $n \rightarrow +oo$.
Dim: $1- n/(sum_{k=0}^{n} a_k) < (sum_{k=0}^{n} [a_k]) / (sum_{k=0}^{n} a_k) \le 1.
osserviamo che la sommatoria di prima soddisfa le ipotesi del Lemma, quindi $sum_{alpha=0}^{[log s/log p]}[log (s/p^alpha)/log q] ∼ 1/2 (log^2 s) / (log p log q) - 1/2 log s / log q$.