26
$\begingroup$

Is the following claim true: Let $\zeta(s)$ be the Riemann zeta function. I observed that as for large $n$, as $s$ increased,

$$ \frac{1}{n}\sum_{k = 1}^n\sum_{i = 1}^{k} \bigg(\frac{\gcd(k,i)}{\text{lcm}(k,i)}\bigg)^s \approx \zeta(s+1) $$

or equivalently

$$ \frac{1}{n}\sum_{k = 1}^n\sum_{i = 1}^{k} \bigg(\frac{\gcd(k,i)^2}{ki}\bigg)^s \approx \zeta(s+1) $$

A few values of $s$, LHS and the RHS are given below

$$(3,1.221,1.202)$$ $$(4,1.084,1.0823)$$ $$(5,1.0372,1.0369)$$ $$(6,1.01737,1.01734)$$ $$(7,1.00835,1.00834)$$ $$(9,1.00494,1.00494)$$ $$(19,1.0000009539,1.0000009539)$$

Note: This question was posted in MSE. It but did not have the right answer.

$\endgroup$
  • 4
    $\begingroup$ Am I understanding correctly that you don't actually claim for the two sides to be equal, but rather them getting asymptotically closer? By your numerical data, a reasonable conjecture might be that $LHS-1\sim\zeta(s+1)-1$ in the sense of the ratio of the two tending to $1$. Since $\zeta(s+1)-1\sim 2^{-s-1}$, it should be enough to look at which terms in your LHS are $1$ and $2^{-s}$ and crudely estimating the rest. $\endgroup$ – Wojowu Dec 18 '19 at 10:57
  • $\begingroup$ @Wojowu Yes, you understanding is correct. I have edited the question. $\endgroup$ – Nilotpal Kanti Sinha Dec 18 '19 at 11:09
  • 1
    $\begingroup$ Beautiful result. $\endgroup$ – The_Sympathizer Dec 23 '19 at 3:40
43
$\begingroup$

Let me denote your LHS by $f(n,s)$. For fixed even $n$ I shall show that $f(n,s)-1\sim\zeta(s+1)-1$ as $s\to\infty$, that is, $$\lim_{s\to\infty}\frac{f(n,s)-1}{\zeta(s+1)-1}=1.$$ This result nicely expresses your numerical observations, which show that the parts after the decimal point seem to be asymptotically the same.

On one hand, we have $\zeta(s+1)-1=2^{-s-1}+3^{-s-1}+\dots$. The terms after the second can be estimated from above by the integral $\int_2^\infty x^{-s-1}dx=\frac{2^{-s}}{s}$, so we see that $\zeta(s+1)-1\sim 2^{-s-1}$.

On the other hand, among pairs $(k,i)$ with $1\leq k\leq n,1\leq i\leq k$, the expression $\frac{\gcd(k,i)}{\operatorname{lcm}(k,i)}$ is equal to $1$ for exactly $n$ pairs $(k,k)$, and is equal to $2^{-1}$ for exactly $n/2$ pairs $(2k,k)$. All other terms, of which there are certainly fewer than $n^2$, are at most $3^{-1}$. Therefore we find $$f(n,s)=\frac{1}{n}\left(n\cdot 1+\frac{n}{2}\cdot 2^{-s}+O(n^23^{-s})\right)=1+2^{-s-1}+o(2^{-s})$$ proving $f(n,s)-1\sim 2^{-s-1}$. It follows that $f(n,s)-1\sim\zeta(s+1)-1$, as we wanted.

Let me emphasize that in the above calculation it was crucial that $n$ was even. If $n$ is odd, then we instead only get $\frac{n-1}{2}$ pairs $(2k,k)$ and the asymptotics get slightly skewed - we then get $f(n,s)-1\sim\frac{n-1}{n}(\zeta(s+1)-1)$. For large $n$ the difference is however, pretty negligible.

| cite | improve this answer | |
$\endgroup$
39
$\begingroup$

A variety of formulas of this type (in the sense of a relation between $\zeta(s)$ and a sum over gcd or lcm) has been derived by Titus Hilberdink and László Tóth in On the average value of the least common multiple of k positive integers (2016), see also On the distribution of the greatest common divisor by Diaconis and Erdȍs. I quote

$$\sum_{i,k=1}^n \big(\text{lcm}(k,i)\big)^s=\frac{\zeta(s+2)}{\zeta(2)}\frac{n^{2s+2}}{(s+1)^2}+{\cal O}(n^{2s+1}\log n),$$ $$\sum_{i,k=1}^n \big(\gcd(k,i)\big)^s=\left(\frac{2\zeta(s)}{\zeta(s+1)}-1\right)\frac{n^{s+1}}{s+1}+{\cal O}(n^{s}\log n),$$ $$\sum_{i_1,i_2,\ldots i_s=1}^n \gcd(i_1,i_2,\ldots i_s)=\frac{\zeta(s-1)}{\zeta(s)}n^s+{\cal O}(n^{s-1}),\;\;s\geq 4.$$

The earliest reference for such series is Ernest Cesàro, Étude moyenne du plus grand commun diviseur de deux nombres (1885).

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Your summand is symmetric with respect to $k$ and $i$:

$$f(n,s) = \frac{1}{n}\sum_{k = 1}^n \sum_{i = 1}^{k} \bigg(\frac{\gcd(k,i)}{\operatorname{lcm}(k,i)}\bigg)^s$$

We can sum along skew diagonals to evaluate the sum. That is, we can convert $(k,i)$ to polar form $(\sqrt{k^2 + i^2}, tan^{-1}\frac{i}{k})$. By symmetry of the summand, the rays from the origin have the same value.

That is, when $\theta = tan^{-1}\frac{i}{k}$, $i = k \tan\theta$. We can vary $\theta$ from $[0, \frac{\pi}{4}]$. The $\gcd(j,j\tan \theta)$ is independent of $j$ but depends on $\theta$, we can therefore use $n$:

$$\frac{1}{n}\int_{0}^{\frac{\pi}{4}} \sum_{j=0}^{n} \left[\frac{\gcd(j,j\tan\theta)}{\operatorname{lcm}(j,j\tan\theta)}\right]^{s} d\theta = \int_{0}^{\frac{\pi}{4}} \left[\frac{\gcd(n,n\tan\theta)}{\operatorname{lcm}(n,n\tan\theta)}\right]^{s} d\theta = \sum_{k=0}^{n} \frac{1}{k^{s+1}} \rightarrow \zeta(s+1)$$

The polar integral(The integral is not continuous on $\theta$ but over the irrational($\tan\theta = \frac{i}{k}$ implies $\theta$ is irrational) values that correspond to the rays) to the sum is calculated easily enough because the values along each ray is constant w.r.t to $j$. Every ray corresponds to one of the values of $\frac{1}{k^s}$ but they have a weight of $\frac{1}{k}$.

E.g., the ray that accumulates $1$ has $\theta = \tan^{-1}(1) = \frac{\pi}{4}$, for $\frac{1}{2^s}$ it is $\theta = \tan^{-1}(2)$ but it has $\frac{1}{2}$ the density of $1$. Similarly for all the others.

If you are having trouble following this, simply look at $\frac{\operatorname{lcm}(k,i)}{\gcd(k,i)}$ in "polar" form, I'll make it easy for you(the text format obscures the patterns but they are there):

\begin{matrix} \color{green}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \\ \color{blue}2 & \color{green}1 & 6 & 2 & 10 & 3 & 14 & 4 & 18 & 5 & \\ \color{red}3 & 6 & \color{green}1 & 12 & 15 & 2 & 21 & 24 & 3 & 30 & \\ 4 & \color{blue}2 & 12 & \color{green}1 & 20 & 6 & 28 & 2 & 36 & 10 & \\ 5 & 10 & 15 & 20 & \color{green}1 & 30 & 35 & 40 & 45 & 2 & \\ 6 & \color{red}3 & \color{blue}2 & 6 & 30 & \color{green}1 & 42 & 12 & 6 & 15 & \\ 7 & 14 & 21 & 28 & 35 & 42 & \color{green}1 & 56 & 63 & 70 & \\ 8 & 4 & 24 & \color{blue}2 & 40 & 12 & 56 & \color{green}1 & 72 & 20 & \\ 9 & 18 & \color{red}3 & 36 & 45 & 6 & 63 & 72 & \color{green}1 & 90 & \\ 10 & 5 & 30 & 10 & \color{blue}2 & 15 & 70 & 20 & 90 & \color{green}1 & \\ \end{matrix}

If you look you can see $k$th ray which has the constant value $\frac{\color{green}1}{k^s}$(displayed as just $k$ in the table) but they repeat at a rate of $\frac{\color{green}1}{k}$ along the ray.

Alternatively, if write the table in polar coordinates(we are rotating coordinate space 45 degree's) we get \begin{matrix} \color{green}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \\ \color{green}1 & \color{blue}2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \\ \color{green}1 & 0 & \color{red}3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \\ \color{green}1 & \color{blue}2 & 0 & 4 & 0 & 0 & 0 & 0 & 0 & 0 & \\ \color{green}1 & 0 & 0 & 0 & 5 & 0 & 0 & 0 & 0 & 0 & \\ \color{green}1 & \color{blue}2 & \color{red}3 & 0 & 0 & 6 & 0 & 0 & 0 & 0 & \\ \color{green}1 & 0 & 0 & 0 & 0 & 0 & 7 & 0 & 0 & 0 & \\ \color{green}1 & \color{blue}2 & 0 & 4 & 0 & 0 & 0 & 8 & 0 & 0 & \\ \color{green}1 & 0 & \color{red}3 & 0 & 0 & 0 & 0 & 0 & 9 & 0 & \\ \color{green}1 & \color{blue}2 & 0 & 0 & 5 & 0 & 0 & 0 & 0 & \color{green}10 & \\ \end{matrix}

Where now the $k$th column is the "$k$th" ray. I.e., the first column in the above table corresponds to the diagonals/rays in the table above it.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What is $\gcd(j,j\tan \theta)$ even supposed to mean when the second term is not an integer? $\endgroup$ – Wojowu Dec 22 '19 at 19:56
  • $\begingroup$ I understand the integral over $\theta$ to stand for the sum over diagonals in the table. $\endgroup$ – Carlo Beenakker Dec 22 '19 at 22:14
  • $\begingroup$ @Wojowu It is an integer. One has to choose theta such that we get an integral. The standard integral is over a continuous range, but that will produce invalid values. The integral is meant to be a discrete integral over the appropriate choices of $\theta$. One can write it in a more explicit notation using lines in the integers: $i = m(k-1) + 1$. As you know though, $m = tan\theta$ for the general case. We could write it as a sum but the notation is far more confusing and verbose than just abstracting it away. Your failure to understand is because $j tan\theta$ is actually an integer. $\endgroup$ – JS Music Dec 24 '19 at 2:53
  • $\begingroup$ @Wojowu For example, when $\theta = tan^{-1}(1) = \frac{\pi}{4}$ we have the relationship $ i = k$ which is the main diagonal. Ok? Now $\theta = tan^{-1}(2) \approx 1.107$ and this gives us the diagonal for the 2's. Again, we end up with $i = 2(k-1)+1 = 2k+1$. So there is a correspondence between certain discrete values of $\theta$ and lines in $\mathbb{Z}^2$. The value of the original summand is constant along these lines. If the summand was continuous it would make perfect sense(basic calculus in polar coordinates) so that concept is used to simplify the notational representation w.l.o.g.. $\endgroup$ – JS Music Dec 24 '19 at 3:04
  • $\begingroup$ @Wojowu One can only do this because the summand is constant along these rays. If they were to change value then it would be a more difficult problem. For small values of n and s the result is invalid because we are assuming rays of constant length, but for a large matrix it is approximated by a circle since the values will be approximately zero($\frac{1}{k^s} \approx 0$ for large k and s). If one takes in to account that $r$ changes depending on $\theta$ one could probably get an exact value(but it might just end up being a collection of finite sums of the zeta type). $\endgroup$ – JS Music Dec 24 '19 at 3:14

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.