# Correlating the von Mangoldt function with periodic sequences

The Dirichlet inverse of the Euler totient function is: $$\varphi^{-1}(n) = \sum_{d \mid n} \mu(d)d \tag{1}$$ and the von Mangoldt function can be expanded/computed as: $$\Lambda(n) = \sum\limits_{k=1}^{\infty}\frac{\varphi^{-1}(\gcd(n,k))}{k} \tag{2}$$ Consider the sequences: $$a(n)=\sum _{k=1}^{j} \frac{\varphi^{-1}(\gcd (n,k))}{k}$$ $$b(n)=\sum _{k=1}^{j+1} \frac{\varphi^{-1}(\gcd (n,k))}{k}$$

Question:

For what values of $$j$$ does $$b(n)$$ eventually correlate better than $$a(n)$$ with the von Mangoldt function $$\Lambda(n)$$ as $$n \rightarrow \infty$$?

The exceptions of $$j$$ when $$b(n)$$ correlates worse than $$a(n)$$ appear to be:
$$j=7, 15, 24, 26, 31$$ which when added with $$1$$ gives initially a sequence of powers of some sort:
$$j+1=8, 16, 25, 27, 32$$

A very slow Mathematica program that computes the sequences $$a(n)$$ and $$b(n)$$ and compares their Pearson correlation with the von Mangoldt function, is:

Clear[a, n, k, start, end]
nnn = 200;
a[n_] := Total[Divisors[n]*MoebiusMu[Divisors[n]]];
Do[column = j;
earlier =
Table[Correlation[
Table[Sum[a[GCD[n, k]]/k, {k, 1, column}], {n, 1, nn}],
Table[N[MangoldtLambda[n]], {n, 1, nn}]], {nn, 2, nnn}];
later = Table[
Correlation[
Table[Sum[a[GCD[n, k]]/k, {k, 1, column + 1}], {n, 1, nn}],
Table[N[MangoldtLambda[n]], {n, 1, nn}]], {nn, 2, nnn}];
sign = Sign[later - earlier];
Print[If[Last[sign] == -1, j, 0]], {j, 2, 32}]


nnn = 200; is considered a large number that serves as the substitute for $$n \rightarrow \infty$$ in the program.

Edit 10.7.2021:

Correlations of partial sums:

Clear[a, n, k, start, end]
nnn = 400;
a[n_] := Total[Divisors[n]*MoebiusMu[Divisors[n]]];
Do[column = j;
earlier =
Table[Correlation[
Accumulate[
Table[Sum[a[GCD[n, k]]/k, {k, 1, column}], {n, 1, nn}]],
Accumulate[Table[N[MangoldtLambda[n]], {n, 1, nn}]]], {nn, 2,
nnn}];
later = Table[
Correlation[
Accumulate[
Table[Sum[a[GCD[n, k]]/k, {k, 1, column + 1}], {n, 1, nn}]],
Accumulate[Table[N[MangoldtLambda[n]], {n, 1, nn}]]], {nn, 2,
nnn}];
sign = Sign[later - earlier];
Print[{earlier, Count[sign, 1], sign, j}], {j, 2, 32}]

• The relationship doesn't seem to be valid for n=1. Jul 10, 2021 at 22:18

TL;DR: This is not a full answer. I compute asymptotically the correlation of $$b(n)$$ and $$\Lambda (n)$$ (it turns out to be $$0$$) and the correlation of $$b(n)$$ and $$a(n)$$ in a relatively closed form sum (I don't think there's really a simpler expression). Although I do not show when the correlation of $$b(n)$$ and $$a(n)$$ is larger or smaller than $$0$$, I show that it is never equal exactly to $$0$$ except for $$j = 1$$.

For the rest of the answer let us denote by $$\mathbb{E}_N$$ the average of a function on the numbers $$1, \dots, N$$. We will always look at correlations up to $$N$$, and then let $$N \to \infty$$. We also assume that $$j > 1$$.

First notice that the correlation of $$b(n)$$ and $$\Lambda(n)$$ tends to $$0$$ as $$N \to \infty$$. This is simply because $$b(n)$$ is a bounded sequence and $$\Lambda (n)$$ fluctuates wildly. More precisely, the correlation is equal to $$\frac{\mathbb{E}_N \left[ \Lambda (n) b(n) \right] - \mathbb{E}_N \left[ \Lambda (n) \right] \mathbb{E}_N \left[ b(n) \right]}{\left( \mathbb{E}_N \left[ \Lambda (n)^2 \right] - \mathbb{E}_N \left[ \Lambda(n) \right]^2 \right)^{\frac{1}{2}} \left( \mathrm{Var}_N \left( b(n) \right) \right)^{\frac{1}{2}}}$$

As $$b(n)$$ is bounded, the numerator is at most a constant times $$\mathbb{E}_N \left[ \Lambda (n) \right]$$, which by the Prime Number Theorem is asymptotically equal to $$1$$. Also by the Prime Number Theorem we have $$\mathbb{E}_N \left[ \Lambda (n)^2 \right] \sim \log N$$, and as $$b(n)$$ is a non constant periodic sequence (with period $$\mathrm{lcm} \left( 1, \dots, j + 1 \right)$$) its variance is bounded by below. Therefore the correlation of $$b(n)$$ and $$\Lambda (n)$$ is bounded in absolute value by a constant times $$\frac{1}{\log N}$$, which tends to $$0$$.

Now, let us compute the correlation of $$a(n)$$ and $$b(n)$$. As they are periodic non-constant sequences, their variance is bounded by below. We will see that their covariance is asymptotically equal to a certain number, and whether this number is greater or lesser than $$0$$ exactly determines whether $$b(n)$$ is better correlated with $$a(n)$$ or with $$\Lambda (n)$$. First, we will compute their averages.

$$\mathbb{E}_N \left[ a(n) \right] = \frac{1}{N} \sum_{n = 1}^{N} \sum_{k = 1}^{j} \frac{1}{k} \sum_{d | k, n} d \mu (d) = \frac{1}{N} \sum_{d = 1}^{j} d \mu(d) \left[ \frac{N}{d} \right] \sum_{k \leq \frac{j}{d}} \frac{1}{d k}$$ As $$N \to \infty$$ this is is asymptotically equal to $$\sum_{d = 1}^{j} \frac{\mu (d)}{d} H_{\left[ \frac{j}{d} \right]}$$ where $$H_m = \sum_{k = 1}^{m} \frac{1}{k}$$ is the Harmonic number. Replacing $$j$$ with $$j + 1$$ we get that $$\mathbb{E}_N \left[ b(n) \right]$$ is asymptotically equal to $$\sum_{d = 1}^{j + 1} \frac{\mu (d)}{d} H_{\left[ \frac{j + 1}{d} \right]}$$ as $$N \to \infty$$. Now, we compute

$$\mathbb{E}_N \left[ a(n) b(n) \right] = \frac{1}{N} \sum_{n = 1}^{N} a(n) b(n) = \frac{1}{N} \sum_{n = 1}^{N} \sum_{k_1 = 1}^{j} \sum_{k_2 = 1}^{j + 1} \frac{1}{k_1 k_2} \sum_{d_1 | n, k_1} \sum_{d_2 | n, k_2} d_1 d_2 \mu(d_1) \mu(d_2)$$ Notice that $$d_1 | n$$ and $$d_2 | n$$ if and only if $$\mathrm{lcm} \left( d_1, d_2 \right) | n$$. Interchanging the order of summation, and applying the fact that $$\frac{1}{N} \left[ \frac{N}{m} \right] \sim \frac{1}{m}$$ for $$m \in \mathbb{N}$$ we see that this sum is equal to $$\sum_{d_1 = 1}^{j} \sum_{d_2 = 1}^{j + 1} \frac{\mu(d_1) \mu(d_2)}{\mathrm{lcm} \left( d_1, d_2 \right)} H_{\left[ \frac{j}{d_1} \right]} H_{\left[ \frac{j + 1}{d_2} \right]}$$

To sum it up, the covariance of $$b(n)$$ and $$a(n)$$ is asymptotically $$\sum_{d_1 = 1}^{j} \sum_{d_2 = 1}^{j + 1} \frac{\mu(d_1) \mu(d_2)}{\mathrm{lcm} \left( d_1, d_2 \right)} H_{\left[ \frac{j}{d_1} \right]} H_{\left[ \frac{j + 1}{d_2} \right]} - \left( \sum_{d_1 = 1}^{j} \frac{\mu(d_1)}{d_1} H_{\left[ \frac{j}{d_1} \right]} \right) \left( \sum_{d_2 = 1}^{j + 1} \frac{\mu (d_2)}{d_2} H_{\left[ \frac{j + 1}{d_2} \right]} \right)$$ Let us show that this number is non-zero. For all $$j > 1$$, there exists a prime $$\frac{j + 1}{2} < p < j + 1$$. It turns out that the covariance has a factor of $$p^2$$ in the denominator. To prove this, let us see what terms could contribute such a factor. In order for $$p$$ to appear in the denominator of $$H_m$$, we must have $$m \geq p$$, and since $$p > \frac{j + 1}{2}$$, in order for $$p$$ to appear in $$H_{\left[ \frac{j}{d_1} \right]}$$ or $$H_{\left[ \frac{j + 1}{d_2} \right]}$$ we must have $$d_1 = 1$$ or $$d_2 = 1$$.

In order for $$p$$ to appear in $$d_1, d_2$$ or $$\mathrm{lcm} \left( d_1, d_2 \right)$$ at least one of $$d_1, d_2$$ must be equal to $$p$$. Going over the very limited options, we see that $$\sum_{d_1 = 1}^{j} \sum_{d_2 = 1}^{j + 1} \frac{\mu(d_1) \mu(d_2)}{\mathrm{lcm} \left( d_1, d_2 \right)} H_{\left[ \frac{j}{d_1} \right]} H_{\left[ \frac{j + 1}{d_2} \right]}$$ contains $$\frac{1}{p^2} - \frac{2}{p^2} = - \frac{1}{p^2}$$ and $$\left( \sum_{d_1 = 1}^{j} \frac{\mu(d_1)}{d_1} H_{\left[ \frac{j}{d_1} \right]} \right) \left( \sum_{d_2 = 1}^{j + 1} \frac{\mu (d_2)}{d_2} H_{\left[ \frac{j + 1}{d_2} \right]} \right)$$ contains in total $$\frac{0}{p^2}$$, thus proving the claim.