Pagina 1 di 1

$\text{gpf}(n^2+1)$

Inviato: 09 set 2013, 19:00
da <enigma>
Per il buon Kfp, dimostrazione guidata di un bound tutto sommato non troppo difficile per $\text{gpf}(n^2+1)$ (spero di non averlo già postato secoli addietro!). È ammesso (necessario?) l'uso del teorema di Dirichlet sulle progressioni aritmetiche.

Sia $ Q(n):= \prod_{k \leq n} (k^2+1)$.
  • Mostrare che $\log Q(n)=2n \log n+O(n)$.
  • Dimostrare che
    \[ v_p(Q(n)) \leq
    \begin{cases}
    n/2+O(1), & p=2; \\
    2n/(p-1)+O(\log_p n), &p \equiv 1 \pmod 4; \\
    0, & p \equiv 3 \pmod 4.
    \end{cases} \]
  • Dimostrare che esiste $C>0$ tale che $\text{gpf}(Q(n))>C n \log n$ definitivamente.
  • Dedurre che esistono infiniti $n$ per cui $\text{gpf}(n^2+1)>C n \log n$.

Re: $\text{gpf}(n^2+1)$

Inviato: 10 set 2013, 12:23
da jordan
Riguardo il primo punto, esiste un metodo che non passi per sommatoria parziale di Abel?

Re: $\text{gpf}(n^2+1)$

Inviato: 10 set 2013, 20:13
da <enigma>
La versione per i poveri di Stirling (quella che si fa facile con l'integrale e dà un errore $O(n)$) è più che sufficiente.

Re: $\text{gpf}(n^2+1)$

Inviato: 11 set 2013, 17:17
da dario2994
A tempo perso metto una parte della soluzione (anche perchè mi manca una parte)... sono stato abbastanza conciso.

$ \displaystyle\ln(Q(n))=\sum_{i=1}^n \ln(i^2+1)=\sum_{i=1}^n (\ln(i^2)+O(1))=O(n)+2\sum_{i=1}^n \ln(i) $
Ma con la versione povera di Stirling (che si ottiene appunto integrando il logaritmo) ottengo:
$ \displaystyle \sum_{i=1}^n \ln(i) = n\ln(n) + O(\ln(n)) $

Unendo i risultati ottengo proprio:
$ \displaystyle\ln(Q(n)) = 2n\ln(n) + O(n) $

Ora sia $p\equiv 1\pmod 3$, allora $p\nmid k^2+1$ per ogni $k$ e perciò ne ricavo $p\nmid Q(n)$.
Per $p=2$ vale che se k è pari $2\nmid k^2+1$, altrimenti $2||k^2+1$. Quindi ne ricavo $\upsilon_2(Q(n))=\frac n2 + O(1)$.

Infine sia $p\equiv 1\pmod 4$. Per il lemma di Hensel $k^2+1\equiv 0 \pmod{p^t}$ ha sempre esattamente 2 soluzioni.
Sia $V_t$ il numero di $k\le n$ tali che $k^2+1\equiv 0 \pmod{p^t}$. Fino al maggior multiplo di $p^t$ minore o uguale a $n$ ci sono $2 \lfloor \frac n{p^t}\rfloor$, mentre oltre quel valore ce ne sono alpiù 2. Unendo quanto trovato ricavo $V_t=\frac{2n}{p^t}+O(1)$.

Ora vale $\displaystyle \sum_{i=1}^\infty V_i =\upsilon_p(Q(n))$ per il solito double counting. Ma la sommatoria la posso troncare a $i_1=log_p(n^2+1)$, poichè tanto $V_i=0$ per ogni $i>i_1$. Allora vale:
$\displaystyle \upsilon_p(Q(n))=\sum_{i=1}^{i_1} V_i = 2n \sum_{i=1}^{i_1} \frac{1}{p^i} + O(i_1)$

Ma con ben pochi conti si verifica che $\displaystyle \sum_{i=1}^{i_1} \frac{1}{p^i}=\frac 1{1-p} + O(p^{-i_1-1})$, e unendo i risultati arrivo a:
$\displaystyle \upsilon_p(Q(n)) = \frac{2n}{p-1} + O(log_p(n))$.

Ora allora posso scrivere:
$ \displaystyle 2n\ln(n) + O(n) = \ln(Q(n)) = \ln(2)\left(\frac n2 +O(1)\right ) + \sum_{p\equiv 1\pmod 4} \ln(p)\upsilon_p(Q(n))$
Ora buttando in $O(n)$ quello che riesco ne ricavo:
$ \displaystyle 2n\ln(n) + O(n) = \sum_{p\equiv 1\pmod 4} \ln(p) \left ( \frac{2n}{p-1}+ O(log_p(n)) \right ) =2n \cdot \sum_{p\equiv 1\pmod 4} \frac{\ln(p)}{p-1} +\sum_{p\equiv 1\pmod 4} O(\ln(n))$

Ora il problema è la prima delle 2 sommatorie. Mentre la seconda si comporta come dovrebbe e se ci fosse solo lei ne otterrei la tesi, la prima mi sembra essere un $ln(n)^2$ che fa crollare tutta la dimostrazione, e non riesco a fare una stima più precisa.

Re: $\text{gpf}(n^2+1)$

Inviato: 11 set 2013, 18:46
da <enigma>
Voglio aiutarti: la prima in realtà è un $ \log n$. Scrivo una guida di soluzione anche per quella.

Sia dunque $\displaystyle T(n):=\sum_{k \leq n} \log k$.
  • Mostrare che $\displaystyle T(n)= n \log n-n+O(\log n)$. (Quando l'hai valutata hai scritto un $O(\ln n)$ che voleva essere un $O(n)$.)
  • Mostrare che $\displaystyle T(n)=\sum_{d \leq n} \Lambda (d)\left \lfloor \frac n d \right \rfloor$ (v. qui).
  • Osservare che $\displaystyle \sum_{d \leq n}\frac{\Lambda(d)}{d}=\sum_{p^k \leq n} \frac {\log p}{ p^k}$. Dedurne che $\displaystyle \sum_{p \leq n} \frac{\log p}{p}=\log n +O(1)$.
  • Usando il teorema di Dirichlet (e il fatto che se $p>n^2+1$ allora $v_p(Q(n))=0$), mostrare che $\displaystyle \sum_{p \leq n^2+1 \atop p \equiv 1 \pmod 4} \frac {\log p}{p-1}= \log n+O(1)$.
Questo mostra perlomeno che per concludere serve un'analisi più attenta di quel che sprechi... se per esempio tutti i fattori fossero al massimo $M=M(n)$, potresti troncare le somme lì invece che a $n^2+1$...