21
$\begingroup$

Yesterday I met professor Halfbrain at an art gallery. The professor told me that recently he had been spending his time with constructing $n\times n$ tables for integers $n\ge3$: the entry at the crossing of row $i$ and column $j$ of such a table equals $\gcd(i,j)$, that is, the greatest common divisor of the integers $i$ and $j$.

The professor carefully analyzed these tables, and made the following striking observations: when he adds up all the $n^2$ entries in a table, then the resulting sum is usually a fairly large number. In particular, the professor has proved the following theorem:

Professor Halfbrain's theorem:
For $n\ge700$, the sum of all the $n^2$ entries in the $n\times n$ table is at least $4n^2$.

Is the professor's theorem indeed true, or has the professor once again made one of his well-known mathematical blunders?

$\endgroup$
  • 4
    $\begingroup$ Upvoted the question before I read it :) I always love your puzzles and I've been waiting for the next one since it's been a while $\endgroup$ – Ivo Beckers May 3 '16 at 9:01
  • $\begingroup$ Well, it's definitely true for $n$ up to $10\,000\,000$. And it looks like the sum grows as $O(n^2\log n)$. $\endgroup$ – 2012rcampion May 3 '16 at 9:22
  • $\begingroup$ I don't quite understand: What do you mean when you say "he adds up all the $n^2$ entries in a table"? $\endgroup$ – Shuri2060 May 3 '16 at 10:58
  • 1
    $\begingroup$ @Question Asker: It is an $n\times n$ table, so that it contains $n^2$ entries. The professor adds up all these entries. $\endgroup$ – Gamow May 3 '16 at 10:59
  • 1
    $\begingroup$ The sum of entries in the table is ~ n^2 log n / zeta(2) where zeta(2) = pi^2/6, which means that we expect the average to reach 4 when log n ~= 4 zeta(2), which is equivalent to n ~= 720. So that number 700 is not a coincidence. The answer is surely yes (especially given that 2012rcampion has checked the "early" cases) but the awkward thing will be getting good enough explicit bounds to prove it. $\endgroup$ – Gareth McCaughan May 5 '16 at 12:23
14
$\begingroup$

Essentially what we need to do is find a lower bound on the sum:

$$ \sum_{i=1}^{n}\sum_{j=1}^{n}\operatorname{gcd}(i,j) \tag{1} $$

This is the total of the entries in the $n\times n$ table of GCD's. We can compute this sum more efficiently by noting that the GCD is commutative, so the table is symmetric about its diagonal. Therefore, the sum (1) is equal to twice the sum of the lower triangular part, minus the sum of the diagonal entries (which would otherwise be counted twice):

$$ \sum_{i=1}^{n}\sum_{j=1}^{n}\operatorname{gcd}(i,j) = 2\sum_{i=1}^{n}\sum_{j=1}^{i}\operatorname{gcd}(i,j) - \sum_{i=1}^{n}\operatorname{gcd}(i,i) \tag{2} $$


We can start simplifying this with the identity:

$$ \operatorname{gcd}(i,i)=i $$

Which is true for all nonnegative integers $i$. This turns the last part of (2) into the well-known:

$$ \sum_{i=1}^{n}i=\frac{n(n+1)}{2} \tag{3} $$


Now we will tackle the sum:

$$ \sum_{j=1}^{i}\operatorname{gcd}(i,j) \tag{4} $$

For any two integers $i$ and $j$, if we know that:

$$ \operatorname{gcd}(i,j)=d $$

Then, by the definition of the GCD, we know that there exists a unique pair of coprime integers $a$ and $b$ such that:

$$ \begin{align} i &= ad \\ j &= bd \end{align} $$

Now in the sum (4) we have $0<j\le i$. This means that $0<bd\le ad$, and for positive $d$, $0<b\le a$. Now for a given value of $a$, the number of integers $b$ satisfying these two conditions ($0<b\le a$ and $b$ is coprime to $a$) is defined as $\varphi(a)$, the Euler totient function.

For given values of $i$ and $d$, $a$ is fixed, and therefore $\varphi(a)$ is also the number of values of $j$ that yield $\operatorname{gcd}(i,j)=d$. This means that for every value of $d$ that appears in (4), the number of times it appears is $\varphi(i/d)$, allowing us to rearrange the sum:

$$ \sum_{j=1}^{i}\operatorname{gcd}(i,j)=\sum_{d|i}d\cdot\varphi\left(\frac{i}{d}\right) $$

Where the notation $\sum_{d|i}$ means the sum over all $d$ that divide $i$.

Our final trick is to reverse the order of the sum. For every divisor $d$, $i/d$ is also a divisor, allowing us to switch the two:

$$ \sum_{d|i}d\cdot\varphi\left(\frac{i}{d}\right)=\sum_{d|i}\varphi(d)\left(\frac{i}{d}\right) \tag{5} $$


Now we can work on the outer part of the sum from (2). We can use (5) to rewrite the inner part:

$$ \sum_{i=1}^{n}\sum_{j=1}^{i}\operatorname{gcd}(i,j) =\sum_{i=1}^{n}\sum_{d|i}\varphi(d)\left(\frac{i}{d}\right) \tag{6} $$

Now for a given value of $d$, the integers $i$ for which $d$ are a divisor are $d,2d,3d,\ldots,kd$. The largest $k$ such that $kd\le n$ is $\lfloor n/d\rfloor$. This allows us to change the order of the sums for $i$ and $d$:

$$ \sum_{i=1}^{n}\sum_{d|i}\varphi(d)\left(\frac{i}{d}\right) = \sum_{d=1}^{n}\sum_{k=1}^{\lfloor n/d\rfloor}\varphi(d)\left(\frac{kd}{d}\right) $$

Moving $\varphi(d)$ out of the inner sum and canceling the factors of $d$ gives us:

$$ \sum_{d=1}^{n}\sum_{k=1}^{\lfloor n/d\rfloor}\varphi(d)\left(\frac{kd}{d}\right) = \sum_{d=1}^{n}\varphi(d)\sum_{k=1}^{\lfloor n/d\rfloor}k $$

The inner sum simplifies to just:

$$ \sum_{d=1}^{n}\varphi(d)\sum_{k=1}^{\lfloor n/d\rfloor}k = \sum_{d=1}^{n}\varphi(d)\frac{1}{2}\left\lfloor\frac{n}{d}\right\rfloor\left(\left\lfloor\frac{n}{d}\right\rfloor+1\right) \tag{7} $$


Now we can substitute (3) and (7) into (2), giving us an expression for the sum of the entire table:

$$ \sum_{i=1}^{n}\sum_{j=1}^{n}\operatorname{gcd}(i,j) = \sum_{d=1}^{n}\varphi(d)\left\lfloor\frac{n}{d}\right\rfloor\left(\left\lfloor\frac{n}{d}\right\rfloor+1\right) - \frac{n(n+1)}{2} \tag{8} $$

We can obtain a lower bound on (8) by replacing $\lfloor n/d\rfloor \to n/d-1$: $$ \sum_{d=1}^{n}\varphi(d)\left(\frac{n^2}{d^2}-\frac{n}{d}\right) - \frac{n^2}{2}-\frac{n}{2} = \left[\sum_{d=1}^{n}\frac{\varphi(d)}{d^2}-\frac{1}{2}\right]n^2 - \left[\sum_{d=1}^{n}\frac{\varphi(d)}{d}+\frac{1}{2}\right]n \tag{9} $$

We are only interested in values of $n$ above $700$. Therefore, we can take the first $700$ terms of sum (8)—which are always present when $n\ge 700$—and drop the remaining terms. Since all the terms in (8) are positive, this is a lower bound on the true value of the sum. Dropping the corresponding terms in (9) lets us obtain our final lower bound:

$$ (4.1801349420713611\ldots)n^2-(426.1576422933951583\ldots)n \tag{10} $$

This lower bound doesn't actually exceed $4n^2$ until $n\ge 2366$, so we need to check all the sums from $700\le n\le 2365$. We can do this quickly using the untruncated sum (8).

If we do this, we find that Professor Halfbrain's theorem is:

correct.


Inspired by the paper: Olivier Bordellès. "The Composition of the gcd and Certain Arithmetic Functions." Journal of Integer Sequences, Vol. 13 (2010)

$\endgroup$
  • 7
    $\begingroup$ I like this answer, but if there isn't an easier one, i guess the question should have gone to mathoverflow, not puzzling. $\endgroup$ – Guntram Blohm supports Monica May 6 '16 at 8:53
  • $\begingroup$ @GuntramBlohm I've been working on simplifying the derivation, there's only one step left that isn't 'elementary.' $\endgroup$ – 2012rcampion May 6 '16 at 11:04
  • $\begingroup$ I thought I could eliminate the last check, but my math was borked. Still don't like using computers to eliminate a bunch of ns though :P $\endgroup$ – ffao May 7 '16 at 8:10
  • $\begingroup$ @2012rcampion for 700 the sum is $2075576$ and $4*n^2 = 1960000$ so the two results are very close. I think the approximation of the floor is too violent to reach a good result but I don't see how not to use it $\endgroup$ – Fabich May 10 '16 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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