Como de costumbre, permita que$\gcd(a,b)$ sea el mayor divisor común de números enteros$a$ y$b$. ¿Qué es la asintótica de$$\frac{1}{n^2} \sum_{i=1}^{i=n} \sum_{j=1}^{j=n} \gcd(i,j)$ $
como $n \to \infty?$
Respuestas
¿Demasiados anuncios?
Hagen von Eitzen
Puntos
171160
El límite debe ser infinito. Un resultado conocido es que la "probabilidad" de$\gcd(i,j)=1$ es$\frac 6{\pi^2}>\frac12$ para$n$ lo suficientemente grande. Por lo tanto, para cualquier$k$ y suficientemente grande $n$, la suma (que es el valor esperado de$\gcd$) es$$>\frac12\cdot \left(1+2\cdot \frac1{2^2}+3\cdot \frac1{3^2}+\ldots +k\frac1{k^2}\right)=\frac12\left(1+\frac12+\cdots+\frac1k\right)\to\infty$ $
Podemos reescribir la suma como $$ \begin{align} S(n)&=\frac{1}{n^2}\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j) \\ &= \frac{1}{n^2}\sum_{g=1}^n\sum_{i\le\lfloor n/g\rfloor}\sum_{\substack{j\le\lfloor n/g\rfloor\\(i,j)=1}} g \\ &= \frac{1}{n^2}\sum_{g=1}^n g\left(-1+2\sum_{i=1}^{\lfloor n/g\rfloor} \varphi(i)\right) \\ &= -\frac{n(n+1)}{2n^2}+\frac{2}{n}\sum_{g=1}^n \frac{g}{n}\sum_{i=1}^{\lfloor n/g\rfloor} \varphi(i) \end{align} $$ Escribir $$ f(x) = \frac{1}{x}\sum_{i\le x}\varphi(i) = \frac{3x}{\pi^2}+E(x) \\ E(x) = o(\log x) $$ (ver Eric Naslund de la exposición), a continuación, $$ \begin{align} S(n) &= -\frac{1}{2}-\frac{1}{2n}+\frac{2}{n}\sum_{g=1}^{n}f(n/g) \\ &= -\frac{1}{2}-\frac{1}{2n}+\frac{6}{\pi^2}\sum_{g=1}^{n}\frac{1}{g}+\frac{2}{n}\sum_{g=1}^n E(n/g) \\ &= \frac{6}{\pi^2}\log n+\frac{6\gamma}{\pi^2}-\frac{1}{2}+C+o(1) \\ &= \frac{6}{\pi^2}\log n + C' + o(1) \end{align} $$ donde la constante $C$ surge de $$ E(x) = o(\log x) \\ \left|\frac{2}{n}\sum_{g=1}^n E(n/g)\right|< \frac{C}{n}\sum_{g=1}^n\log(n/g)=C\left(\log n - \frac{\log n!}{n}\right)=C+o(1) $$ por Stirling aproximación. Los cálculos sugieren $C=0.39344\cdots, C'=0.24434\cdots$.
Adam Kahtava
Puntos
383
El límite es infinito. La suma es igual a $$ \ frac {1} {n ^ 2} \ sum_ {k = 1} ^ n \ varphi (k) \ left \ lfloor \ frac nk \ right \ rfloor ^ 2 $$ y entonces usted ' preguntando sobre el comportamiento asintótico de $$ \ sum_ {k = 1} ^ \ infty \ frac {\ varphi (k)} {k ^ 2} $$ Claramente $$ \ sum_ {k <x} \ frac {\ varphi (k)} {k ^ 2}> \ sum_ {p <x} \ frac {\ varphi (p)} {p ^ 2} \ sim \ log \ log x $$ y $$ \ sum_ {k <x} \ frac {\ varphi (k)} {k ^ 2} <\ sum_ {k <x} \ frac {k-1} {k ^ 2} \ sim \ log x $$, por lo que da límites.
Shabaz
Puntos
403
De los puntos reticulares$[1,n] \times [1,n], 1-\frac 1{p^2}$ no tiene factor$p$% en$\gcd, \frac 1{p^2}-\frac 1{p^4}$ tiene un factor$p$ en$\gcd\frac 1{p^4}-\frac 1{p^6}$, tiene un factor$p^2$ en el $\gcd, \frac 1{p^6}-\frac 1{p^8}$ tiene un factor$p^3$ en$\gcd$ y así sucesivamente. Eso significa que un primer$p$% contribuye con un factor$(1-\frac 1{p^2}+p(\frac 1{p^2}-\frac 1{p^4})+p^2({p^4}-\frac 1{p^6})+\dots$ o$\sum_{i=0}^\infty(p^{-i}-p^{-i-2})=\sum_{i=0}^\infty p^{-i}(1-p^{-2})=\frac {1-p^{-2}}{1-p^{-1}}=1+\frac 1p$. No sé cómo justificar el uso del hecho de que$\gcd$ es multiplicativo para convertirlo en$$\lim_{m \to \infty}\prod_{p \text {prime}}^m(1+\frac 1p)$$ to get the asymptotics, but it seems like it should work by taking, say $ m = \ sqrt n$ and letting $ n \ to \ infty ps
