2
$\begingroup$

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

$$a(N) = \sum_{n=1}^{n=N}\sum_{\substack{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_{\substack{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$

1 Answer 1

4
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .