1
$\begingroup$

I am looking for the exact asymptotic for this partial sum:

$$a(N) = \sum_{n=1}^{n=N}\sum_{k=1}_{GCD(n,k)=1}^{k=n*m} \frac{1}{k}$$

where $m$ is some integer $1,2,3,4,5,...$

My guess was that since this is closely related to the Euler totient: $$\phi(N) = \sum_{n=1}^{n=N}\sum_{k=1}_{GCD(n,k)=1}^{k=n} 1$$

it should be a combination of the average order $\zeta(2) = \frac{\pi ^2}{6}$ of the Euler totient, and the asymptotics for the partial sums of the Harmonic numbers, and therefore:

$$a(N) \sim \frac{\int (\log (m n)+\gamma ) \, dn}{\frac{\pi ^2}{6}}$$

$$a(N) \sim \frac{n \log (m n)+\gamma n-n}{\frac{\pi ^2}{6}}$$

would be a good approximation. However, it appears that:

$$a(N) \sim \frac{\int (\log (m n)+1.988\gamma ) \, dn}{\frac{\pi ^2}{6}}$$

$$a(N) \sim \frac{n \log (m n)+1.988\gamma n-n}{\frac{\pi ^2}{6}}$$

is better. But where does the factor $1.988$ come from, and should it be there at all?

Plotting them it looks like a good fit:

enter image description here

where the staircase is $a(N)$ for the case $m=1$ and the yellow line is the asymptotic.

Included is the overestimate (green curve):

$$\frac{n \log (m n)+(1.988+1)\gamma n-n}{\frac{\pi ^2}{6}}$$

and the underestimate (red curve):

$$\frac{n \log (m n)+(1.988-1)\gamma n-n}{\frac{\pi ^2}{6}}$$

I don't know if they really are over- and underestimates. I am just guessing. For small $N$ they are not.

Anyways, differentiating we have for the overestimate:

$$\frac{\log (m n)+(1.988+1)\gamma )}{\frac{\pi ^2}{6}}$$

and the underestimate:

$$\frac{\log (m n)+(1.988-1)\gamma )}{\frac{\pi ^2}{6}}$$

Plotting the staircase $a(N)$ minus the asymptotic $\frac{n \log (m n)+1.988\gamma n-n}{\frac{\pi ^2}{6}}$ with conjectured bounds from differentiated over- and underestimates:

with bounds

Ultimately I am interested in the von Mangoldt function:

$$\Lambda(N) = \lim_{m-->\infty} \sum_{n=1}^{n=N}\sum_{k=1}^{k=n*m} \frac{b(G(n,k))}{k}$$

and the Chebyshev function. In the formula the sequence "b" is the Dirichlet inverse of the Euler totient function.

There might be an error in the $\Lambda(N)$ formula above, but expressed simpler, the von Mangoldt function is:

$$\Lambda(n) =\sum_{k=1}^{\infty} \frac{b(GCD(n,k))}{k}$$

where again the sequence "b" is the Dirichlet inverse of the Euler totient function.

Some related Mathematica code:

(*Det här programmet ger asymptoter för alla triangulära GCD matriser \
för alla "m"*)
nn = 80;
q = 10;
a1 = Table[Sum[1/(n*q), {n, 1, Floor[k]}], {k, 0, nn, 1/10}];
a2 = Table[(Log[k] + EulerGamma)/q, {k, 0, nn, 1/10}];
Show[ListLinePlot[a1], ListLinePlot[a2]]
ListLinePlot[Sign[N[a1 - a2]]]


a1 = Table[Sum[1/(n), {n, 1, Floor[k]}], {k, 0, nn, 1/10}];
a2 = Table[Log[k + EulerGamma] + EulerGamma, {k, 0, nn, 1/10}];
Show[ListLinePlot[a1], ListLinePlot[a2]]
ListLinePlot[Sign[N[a1 - a2]]]

a1 = Table[Sum[1/(n), {n, 1, Floor[k]}], {k, 0, nn, 1/10}];    
a2 = Table[Log[k - EulerGamma] + EulerGamma, {k, 0, nn, 1/10}];
Show[ListLinePlot[a1], ListLinePlot[a2]]
ListLinePlot[Sign[N[a1 - a2]]]

b = Table[DivisorSum[m, # MoebiusMu[#] &], {m, nn}];
m = 1;
Monitor[a1 = 
   Table[Total[
     Table[If[GCD[n, k] == 1, 1/(k*q), 0], {k, 1, m*n}]], {n, 1/q, nn,
      1/q}], N[n]];
Monitor[a1 = 
   Table[Sum[
     If[GCD[n, k] == 1, b[[GCD[n, k]]]/(k*q), 0], {k, 1, m*n}], {n, 
     1/q, nn, 1/q}], N[n]];
a1[[1 ;; 4*q]]
ListLinePlot[{Accumulate[a1] - 
   Table[-n + (1.988)*EulerGamma n + n Log[m n], {n, 1/q, nn, 1/q}]/
     Zeta[2]/q, -Table[(1.988 - 0.8) EulerGamma + Log[n*m], {n, 1/q, 
       nn, 1/q}]/Zeta[2]/q, 
  Table[(1.988 + 0.8) EulerGamma + Log[n*m], {n, 1/q, nn, 1/q}]/
    Zeta[2]/q}]
ListLinePlot[{Accumulate[a1], 
  Table[-n + (1.988 - 1)* EulerGamma n + n Log[m n], {n, 1/q, nn, 
      1/q}]/Zeta[2]/q, 
  Table[-n + 1.988* EulerGamma n + n Log[m n], {n, 1/q, nn, 1/q}]/
    Zeta[2]/q, 
  Table[-n + (1.988 + 1)* EulerGamma n + n Log[m n], {n, 1/q, nn, 
      1/q}]/Zeta[2]/q}]
ListPlot[Accumulate[a1] - 
  Table[-n + 1.988* EulerGamma n + n Log[m n], {n, 1/q, nn, 1/q}]/
    Zeta[2]/q]
$\endgroup$
2
$\begingroup$

Here is a modest contribution that can perhaps initiate a discussion.

We compute the asymptotics of $$A(N) = \sum_{n=1}^N \sum_{k=1 \atop (n,k)=1}^n \frac{1}{k}.$$

Introduce $$q(N,k) = \sum_{n=1\atop (n,k)=1}^N 1 \sim N \frac{\varphi(k)}{k}.$$

Rewrite the sum in terms of $q(N,k),$ getting $$\sum_{k=1}^N \frac{1}{k} \sum_{n=k\atop (n,k)=1}^N 1 = 1 + \sum_{k=1}^N \frac{1}{k} (q(N,k) - \varphi(k)).$$ The one term in front compensates for the fact that when $k=1$ we have $$\sum_{n=1\atop (n,k)=1}^N 1 = q(N, k)$$ and not $q(N,k)-1.$ Now switching to asymptotics we obtain $$ \sum_{k=1}^N \frac{1}{k} \left(N \frac{\varphi(k)}{k} - \varphi(k)\right).$$ We will use the Mellin-Perron formula to predict the first term of the asymptotics (a rigorous proof would include a bound on the remainder integral).

Recall the Mellin-Perron summation formula: $$\sum_{k=1}^{n-1} \lambda_k + \frac{1}{2} \lambda_n = \frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty} L(s) \frac{n^s}{s} ds \quad\text{where}\quad L(s) = \sum_{k\ge 1} \frac{\lambda_k}{k^s}.$$

Now the well-known $$\sum_{d|n} \varphi(d) = n \quad \text{immediately implies}\quad \sum_{k\ge 1} \frac{\varphi(k)}{k^s} = \frac{\zeta(s-1)}{\zeta(s)}.$$ Therefore $$ \sum_{k\ge 1} \frac{\varphi(k)/k^2}{k^s} = \frac{\zeta(s+1)}{\zeta(s+2)} \quad\text{and}\quad \sum_{k\ge 1} \frac{\varphi(k)/k}{k^s} = \frac{\zeta(s)}{\zeta(s+1)}.$$

Thus by Mellin-Perron, $$A(N) \sim N\times\operatorname{Res}\left(\frac{\zeta(s+1)}{\zeta(s+2)} \frac{N^s}{s}; s=0\right) - \operatorname{Res}\left(\frac{\zeta(s)}{\zeta(s+1)} \frac{N^s}{s}; s=1\right).$$ Computing the residues we thus obtain $$A(N) \sim \frac{6}{\pi^2} N\log N + \frac{6}{\pi^2} \left(\gamma - \frac{6}{\pi^2} \zeta'(2)-1\right) N.$$

This approximation is quite good, for example $A(1000) \approx 4291.209545$ and the approximation gives $4288.884325$. For $A(2000) \approx 9423.976478$ we get $9420.534562.$ Even more impressive, $A(5000)\approx 26339.64158$ and the asymptotic formula gives $26336.52625$.

Observe that $$1.988\gamma-1 \approx 0.147504742 \quad\text{and}\quad \gamma-\frac{6}{\pi^2}\zeta'(2)-1 \approx 0.147176658,$$ confirming the numeric result from the original query.

We really needed Mellin-Perron because the pole of the first sum term is a double pole and Wiener-Ikehara only applies to simple poles, like the one in the second term.

$\endgroup$

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.