0
$\begingroup$

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}]
$\endgroup$
1
  • 1
    $\begingroup$ The relationship doesn't seem to be valid for n=1. $\endgroup$ Jul 10, 2021 at 22:18

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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