Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Does there exist a positive real number $C$ and a positive integer $M$ such that for all $n > M$ we have: $$\sum_{i=1}^n\sum_{j=1}^n\gcd (i, j)\ge Cn^2 \log n$$

This originally appeared as an Olympiad problem in the case of $4n^2$ on the RHS. This case was much simpler; simply let $i$ only range on primes values and one quickly derives a $\omega \left ( n^2 \log \log \frac{n}{\log n} \right )$ bound if I didn't mess up. The motivation for above bound is derived from the fact that $$\sum_{j=1}^n \gcd(i,j) \approx \frac{n}{i} \sum_{d|i} \varphi(i/d) \cdot d \approx n \cdot \tau(i) \cdot \frac{6}{\pi^2}$$ So we have: $$\sum_{i=1}^n\sum_{j=1}^n\gcd (i, j) \approx \frac{6n^2}{\pi^2} \sum_{i=1}^n \frac{1}{i} \approx \frac{6}{\pi^2} n^2 \log n$$

However, this is pretty unrigorous reasoning. Does anybody have any ideas as to how to rigorously prove this bound? Of course, showing that the sum in fact gets "close" to $\frac{6}{\pi^2} n^2 \log n$ as $n \to \infty$ would be even better.

share|improve this question

2 Answers 2

up vote 7 down vote accepted

\begin{align} \sum_{i=1}^{n}{\sum_{j=1}^{n}{\gcd (i, j)}}& =2\sum_{1 \leq j \leq i \leq n}{\gcd (i, j)}-\sum_{i=1}^{n}{\gcd(i, i)} \\ & =2\sum_{i=1}^{n}{\sum_{d \mid i}{\varphi{\left(\frac{i}{d}\right)}d}}-\frac{n(n+1)}{2} \\ & =2\sum_{d=1}^{n}{d\sum_{k=1}^{\left\lfloor \frac{n}{d}\right\rfloor}{\varphi{(k)}}}-\frac{n(n+1)}{2} \\ & =2\sum_{d=1}^{n}{d(\frac{3}{\pi^2}\left\lfloor \frac{n}{d}\right\rfloor^2+O(\left\lfloor \frac{n}{d}\right\rfloor \log(\left\lfloor \frac{n}{d}\right\rfloor)))}+O(n^2) \\ & =2\sum_{d=1}^{n}{d((\frac{3}{\pi^2}(\frac{n}{d})^2+O(\frac{n}{d}))+O(\frac{n}{d} \log (\frac{n}{d})))}+O(n^2) \\ & =\frac{6n^2}{\pi^2}\sum_{d=1}^{n}{\frac{1}{d}}+O(n^2)+O(n^2\log(n)-n\sum_{d=1}^{n}{\log(d)})+O(n^2) \\ & =\frac{6n^2}{\pi^2}(\log n+O(1))+O(n^2)+O(n^2\log(n)-n(n \log n-n+O(1))) \\ & =\frac{6}{\pi^2}n^2\log n+O(n^2) \end{align}

share|improve this answer
    
Wow, very nice! I feel somewhat silly for not noticing breaking it up into a sum of $ 1 \le j \le i \le n$, but this is very elegant and answers my question perfectly. –  dinoboy Mar 10 '13 at 8:58
    
Here is a fun problem: What if I want to know the order $n^2$ term? –  Eric Naslund Mar 10 '13 at 19:32

Lemma: We have that $$\sum_{d\leq x}\frac{\phi(d)}{d^{2}}=\frac{6}{\pi^{2}}\log x+O(1).$$ This follows from the fact that $\sum_{n\leq x}\phi(n)=\frac{3}{\pi^2}x^2 +O(x\log x)$ along with partial summation.

Using the convolution identity $\left(1*\phi\right)(n)=n$, we see that $$\sum_{i,j\leq x}\gcd\left(i,j\right)=\sum_{i,j\leq x}\sum_{d|i,j}\phi(d),$$ and switching the order of summation yields $$\sum_{d\leq x}\phi(d)\sum_{i,j\leq\frac{x}{d}}1=\sum_{d\leq x}\phi(d)\left[\frac{x}{d}\right]^{2}.\ \ \ \ \ \ \ \ \ \ \ \ (1)$$ Expanding out $\left[\frac{x}{d}\right]=\frac{x}{d}-\left\{ \frac{x}{d}\right\},$ we arrive at the desired asymptotic $$\sum_{i,j\leq x}\gcd\left(i,j\right)=x^{2}\sum_{d\leq x}\frac{\phi(d)}{d^{2}}+O(x^2)=\frac{6}{\pi^{2}}x^2\log x+O(x^2).$$

Using the explicit identity in equation $(1)$, with a lot of work we can derive the second term in the asymptotic expansion.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.