Exact formula for partial sums of Liouville function $L(n)$ (OEIS sequence A002819)

Question

I am wondering if it is possible to get a useful exact formula, or at least some useful asymptotics, for the partial sums of the Liouville function (OEIS sequence A002819) $$L(n)=\sum_{k=1}^n \lambda(k),$$ by exploiting the identity $$\sum_{k=1}^n \lambda(k)\Big\lfloor \frac{n}{k}\Big\rfloor = \lfloor \sqrt{n}\rfloor.$$

The behavior of $L(n)$ is strongly related to the Riemann hypothesis; see here for a great related MO question asked 11 years ago. The above formula, in theory, allows you to compute $L(n)$ exactly as a linear combination

$$L(n)=a_1\cdot\lfloor\sqrt{1}\rfloor +\cdots +a_n\cdot\lfloor\sqrt{n}\rfloor$$

with integer coefficients, by inverting a somewhat complicated $n \times n$ triangular matrix. Not sure if anyone tried to do it. I tried to give it a shot, and something more interesting than I would have expected, came out of it. My question is whether it is possible to go beyond what I discovered so far, maybe like getting a more complete solution, or more importantly, see whether some asymptotics can be derived, which could potentially bring some insights about RH.

If anything, my solution leads to a fast, exact computation of $L(n)$ for large $n$, since the immense majority of the coefficients in the linear combination mentioned above, are zero.

What I found and where I am stuck

The main result is this:

$$L(n)=A(n)+B(n), \mbox{ } \mbox{ } \mbox{with}\\ A(n)=\sum_{k=1}^{u_n} \mu(k)\Big\lfloor\sqrt{\frac{n}{k}}\Big\rfloor, \mbox{ } \mbox{ } B(n)=\sum_{1}^{v_n} a_k \Big\lfloor\sqrt{k}\Big\rfloor.$$

Here $\mu(\cdot)$ is the Moebius function and $v_n=\lfloor \sqrt{n/u_n}\rfloor - 1$. It's not obvious to me how large $u_n$ can be, that is, how far can I extend $A(n)$. If you can determine $u_n$, that is enough for your answer to be accepted. Likewise, I haven't managed to find strong patterns in the coefficients $a_k$ in $B(n)$. If you have a simple explicit formula for those $a_k$'s, that would also be an accepted answer. In any case, $a_k$ can be computed explicitly, be it one of the numerous zeros, one of the Moebius coefficients in $A(n)$ or one of the unknown coefficients in $B(n)$.

You can compute the $a_k$'s using the backward following recurrence, with initial condition $a_n=1$, and the iteration

$$a_{n-k}=1-\sum_{j=0}^{k-1} \Big\lfloor\frac{n-j}{n-k}\Big\rfloor a_{n-j}$$

successively for $k=1, 2, \cdots,n-1$. Note that the summation formula $L(n)=A(n)+B(n)$ seems to have $o(n)$ terms. For instance, if $n=22500$ we have 95 non-zero terms in $A(n)$, and 210 non-zero terms total.

Note

The sequence $(u_n)$ is increasing. It would be interesting to see its asymptotic behavior. I am also interested in an asymptotic formula for total number of non-zero terms in my formula. Finally, an answer involving the Mertens function (instead of Liouville) is also acceptable.

Approximations and asymptotics

The plot below corresponds to $n=22501$. The Y-value on the far left corresponds to the first non-zero term $a_n \lfloor \sqrt{n}\rfloor$. Of course, $a_n=\mu(1)=1$. The more we move to the right, the more non-zero terms are added, until at the far right where all the 210 non-zero terms have been added and the Y-value represents $L(n)$. Terms are being added in decreasing order, starting with $\lfloor\sqrt{n}\rfloor$ and ending with $\lfloor\sqrt{1}\rfloor$.

The lower and upper curves corresponds to $95\%$ empirical percentiles. This band gives a very good idea about possible range of values for $L(n)$, even after adding only the top 15 non-zero terms. Also, because $\mu(1)=1$, $\mu(2)=\mu(3)=\mu(5)=-1$ and $\mu(4)=0$, we start with a large positive value, but quickly drop to largely negative values and have a hard time getting back into positive territory. This explains why $L(n)$ is negative for about the first billion values of $n$.

The plot below shows the values of $a_k \lfloor \sqrt{k}\rfloor$ in decreasing order of the square root, only for those 210 $a_k$'s that are non-zero. The smooth portion on the left corresponds to terms in $A(n)$, with $a_k\in\{-1,+1\}$. The right side corresponds to terms in $B(n)$, with a more chaotic behavior. It would be interesting to know if $A(n)$ dwarfs $B(n)$ or not, my guess is that they have the same order of magnitude and are balancing out each other.

Update on 5/21/2021

Below are two new developments that may be of interest to the reader.

Update 1

The sum of the first $10^2$ terms of $A(n)$, which is always the same if $n$ is large enough, is very negative and approximately equal to $-\sqrt{n}$, regardless of $n$. This remains true even for the sum of the first $10^3$, $10^4$ or $10^5$ terms, as illustrated in the plot below. In the plot below, $n=10^{60}$, the $Y$-axis represents the sum of the first $k$ terms of $A(n)$ up to $k=10^5$, and the $X$-axis represents $k$.

This means that it is very hard for $L(n)$ to be positive, and it is typically more often negative than positive. However $L(n)$ changes sign infinitely many times. For $L(n)$ to be positive, you need to have $n$ very large and hope that there are enough terms in $A(n)$ to make $A(n)$ positive (probably unlikely to happen) or that $B(n)$ is very high, approximately equal to $+\sqrt{n}$ to cancel out the highly negative $A(n)$.

Update 2

About replacing the integer part function in the backward recurrence formula that defines $a_{n-k}$, by a smooth approximation (e.g. based on Fourier series expansions). I tested the following approximation:

$$a_{n-k}=1-\sum_{j=0}^{k-1} \Big(\frac{n-j}{n-k} - \frac{1}{2}\Big) a_{n-j},$$

($k=1,2,\cdots,n-1$) still with $a_n=1$. The result is that now, all $a_k$'s are non-zero. The new $a_k$'s are totally different from the old ones, but the new $L(n)$ is not much different, its magnitude seemingly unchanged. To avoid confusion, the new $L(n)$ obtained with the approximation discussed here is denoted as $L^*(n)$, and we can decompose it as follows:

$$L^*(n)=C(n) + D(n), \mbox{ } \mbox{ } \mbox{ } \mbox{ with } \\ C(n)=\sum_{k=0}^{w_n} a_{n-k}\lfloor\sqrt{n-k}\rfloor, \mbox{ } \mbox{ } \mbox{ } D(n) =\sum_{k=w_n +1}^{n-1} a_{n-k}\lfloor\sqrt{n-k}\rfloor. $$

The nice result is that $w_n$ is extremely small compared to $n$, and all the $a_k$'s in $D(n)$ are almost identical, so you get the following excellent approximation for $D(n)$:

$$D(n) \sim a_{w_n +1} \sum_{k=w_n +1}^{n-1} \lfloor\sqrt{n-k}\rfloor \sim \frac{2 a_{w_n +1}}{3} \cdot n^{3/2}.$$

Also $C(n)\sim 2\sqrt{n}$ and $a_{w_n +1}\sim -4/n$. Thus $L^*(n) \sim -\frac{2}{3}\sqrt{n}$. For instance, if $n=22500$, you can choose $w_n=20$. It results in $C(n)=298.55$ and $a_{w_n +1}=-0.000177$. The approximate $D(n)$ using the above formula is $398.25$. Thus $L^*(n)\approx 298.55-398.25 \approx -99.7$. The true value is $L^*(n)=-99.013\dots$ and the true value of $L(n)$ is $L(n)=-86$. The big question is how well $L^*(n)$ approximates $L(n)$. It is my hope that there are two strictly positive constants $c_1,c_2$ such that $c_1 < L^*(n)/L(n) < c_2$ is bounded. If that is the case, then you can use either $L$ or $L^*$ to determine the abscissa of convergence of

$$\sum_{k=1}^\infty \frac{\lambda(k)}{k^s}=\frac{\zeta(2s)}{\zeta(s)}.$$

The abscissa in question is

$$\sigma_c=\lim\sup_{n\rightarrow\infty}\frac{\log|L(n)|}{\log n} \stackrel{?}{=}\lim\sup_{n\rightarrow\infty}\frac{\log|L^*(n)|}{\log n}=\frac{1}{2}.$$

If $\sigma_c=\frac{1}{2}$, it would prove RH. Using more terms in the Fourier expansion of $\lfloor\cdot\rfloor$ does not help.

Source code

Here is raw source code in Perl, just in case there are typos left in my text. The source code does the correct computations, both for Louiville, Mertens, and other related functions.=.

### Approx [x]: x-0.5
### Sum[LiouvilleLambda[k],{k,1,10000}]=-94   | My Approx: -66.864752863936
### Sum[LiouvilleLambda[k],{k,1,20000}]=-54   | My Approx: -95.8592077112619
### Sum[LiouvilleLambda[k],{k,1,40000}]=-180  | My approx: -129.653234371957
### Sum[LiouvilleLambda[k],{k,1,60000}]=-268  | My approx: -156.18294813206
### Sum[LiouvilleLambda[k],{k,1,80000}]=-136  | My approx: -189.98311248939
### Sum[LiouvilleLambda[k],{k,1,100000}]=-288 | My approx: -211.563785745252

### Sum[Moebius[k]*int(2000/k),{k,1,2000}]

$pi=3.14159265358979323846;

$n=600;
$M=40;
$aa=1.5;    # 0.5 Liouville | 0 Moebius
$bb=1.5;    # 1 Liouville   | 1 Moebius

$a[$n]=1;  
$divisor=1;
$term=int($n**$aa);    #  
$L=$term;  

open(OUT,">liou2.txt");
print OUT "$n\t$a[$n]\t$divisor\t$term\t$L\n";

for ($k=1; $k<$n; $k++) { ### $k<$n;
  $sum=0;
  for($j=0; $j<$k; $j++) {
    $x=($n-$j)/($n-$k);  
    $x=$x**$bb;    #  
$c=int($x);   ## exact solution L(n)
#$c=$x-0.5;   ## approximation L*(n)
### +(1/$pi)*( sin(2*$pi*$x)/1 ); ### + sin(4*$pi*$x)/2  + sin(6*$pi*$x)/3 )+ sin(8*$pi*$x)/4 + sin(10*$pi*$x)/5 + sin(12*$pi*$x)/6 );
    $b=$a[$n-$j];
    $sum+=$b*$c;

  }
  $a[$n-$k]=1-$sum;
  $m=$n-$k;
  $divisor=int($n/$m);
  $term=$a[$m]*int($m**$aa); # 
  $L+=$term; 

  if ($k==$M) { $C=$L; $aw=$a[$n-$k]}
  if ($a[$m] != 0) { print OUT "$m\t$a[$m]\t$divisor\t$term\t$L\n"; }
}
close(OUT);

$D=(2/3)*$aw*$n**(3/2);
$Lapprox=$C+$D;

print "\nL($n) = $L\nLapprox($n) = $Lapprox\n";

Answer 1

$$\lambda(n)=(-1)^{\Omega(n)}=\sum\limits_{d^2|n}\mu\left(\frac{n}{d^2}\right)\tag{1}$$

$$L(x)=\sum\limits_{n\le x}\lambda(n)=\sum\limits_{n^2\le x} M\left(\frac{x}{n^2}\right)\tag{2}$$

where

$$M(x)=\sum _{n\le x}\mu(n)\tag{3}$$

---

The Mertens function $M(x)$ can also be evaluated as follows:

$$\quad M(x)=\sum\limits_{n=\left\lfloor\frac{x-2}{4}\right\rfloor+1}^{\left\lfloor\frac{x-1}{2}\right\rfloor}\mu(2\,n+1)\tag{4}$$

---

The summatory Liouville function $L(x)$ is related to the floor function $\lfloor x\rfloor$ as follows where $\nu(n)$ is the number of distinct primes dividing $n$:

$$L(x)=\sum\limits_{n\le x}2^{\,\nu(n)}\,\lambda(n)\left\lfloor\frac{x}{n}\right\rfloor\tag{5}$$

$$\lfloor x\rfloor=\sum _{n=1}^x 2^{\,\nu(n)}\,L\left(\frac{x}{n}\right)\tag{6}$$

---

Relationship (5) above leads to the following analytic representations of $L_o(x)=\underset{\epsilon\to 0}{\text{lim}}\frac{L(x-\epsilon)+L(x+\epsilon)}{2}$ and it's first-order derivative $L_o'(x)$ where the evaluation frequency $f$ is assumed to be a positive integer.

---

$$L_o(x)=\underset{N,f\to\infty}{\text{lim}}\left(\sum _{n=1}^N 2^{\,\nu(n)}\,\lambda(n) \left(\frac{x}{n}-\left(\frac{1}{2}-\frac{1}{\pi}\sum _{k=1}^{f\,n}\frac{\sin\left(\frac{2 \pi k x}{n}\right)}{k}\right)\right)\right),\quad x>0\tag{7}$$

$$L_o'(x)=\underset{N,f\to\infty}{\text{lim}}\left(\sum\limits_{n=1}^N\frac{2^{\,\nu(n)}\,\lambda(n)}{n}\left(1+2\sum\limits_{k=1}^{f\,n}\cos\left(\frac{2 \pi k x}{n}\right)\right)\right),\quad x>0\tag{8}$$

---

Figure (1) below illustrates $L_o(x)$ defined in formula (7) above in orange overlaid on the blue reference function $L(x)$ where formula (7) is evaluated at $N=111$ and $f=4$. I generally try to select $N$ such than $L_o(0)$ evaluates close to zero, and in the case of $N=111$, $L_o(0)$ evaluates to $\frac{1}{2}$. The red discrete portion of Figure (1) below illustrates the evaluation of $L_o(x)$ at positive integer values of $x$, and note this evaluation is consistent with the Heaviside step function half-step convention.

---

Figure (1): Illustration of formula (7) for $L_o(x)$ (orange) overlaid on $L(x)$ (blue)

---

I believe formula (8) for $L_o'(x)$ above converges (in a distributional sense) to $L'(x)=\sum\limits_n\lambda(n)\,\delta(x-n)$.

---

Now consider the following formula for $f_o'(x)$ which is a subset of formula (8) above for $L_o'(x)$.

---

$$f_o'(x)=\underset{N,f\to\infty}{\text{lim}}\left(2\sum\limits_{n=1}^N\frac{2^{\,\nu(n)}\,\lambda(n)}{n}\sum\limits_{k=1}^{f\,n}\cos\left(\frac{2 \pi k x}{n}\right)\right),\quad x>0\tag{9}$$

---

Figure (2) below illustrates $f_o'(x)$ defined in formula (9) above where formula (9) is evaluated at $N=111$ and $f=4$. The two dashed-gray horizontal gridlines are at $y=\pm 8$. The red discrete portion of Figure (2) below illustrates $f_o'(x)$ defined in formula (8) above evaluates to exactly $2\,f$ times the step size of $L(x)$ at positive integer values of $x\le N$.

---

Figure (2): Illustration of formula (9) for $f_o'(x)$

Answer 2

Mathematica 8:

(*Mathematica start*)
Clear[A, a, n, k, nn, q, Q];
nn = 60;
numberOfColumns = 
  7;(*Increase this number for better precision of the Liouville \
Lambda function*)
q = Table[Sum[If[n == k^2, 1, 0], {k, 1, nn}], {n, 1, nn}];
TableForm[
  Q = Table[
    Table[If[Mod[n, k] == 0, q[[n/k]], 0], {k, 1, nn}], {n, 1, nn}]];
a[n_] := Total[Divisors[n]*MoebiusMu[Divisors[n]]];
Monitor[A = 
   Table[If[n == 1, 0, 
     Sum[-1*a[GCD[n, k]]/N[k]/Log[n], {k, 1, numberOfColumns}]], {n, 
     1, nn}];, n]
Show[ListLinePlot[
  Accumulate[
   approximatedLiouvilleLambda = (MatrixExp[
        Table[Table[If[Mod[n, k] == 0, A[[n/k]], 0], {k, 1, nn}], {n, 
          1, nn}]].Q)[[All, 1]]], PlotStyle -> Red], 
 ListLinePlot[Accumulate[LiouvilleLambda[Range[nn]]]]]
(*Mathematica end*)

gives the plot:

where the blue is the actual partial sums of the Liouville function, and the red plot is the approximation of the partial sums of the Liouville Lambda function given by the 7 first columns in the symmetric GCD expansion of the von Mangoldt function based on the relationship:

Let $\mu(n)$ be the Möbius function, then:

$$a(n) = \sum\limits_{d|n} d \cdot \mu(d)$$

$$T(n,k)=a(GCD(n,k))$$

$$T = \left( \begin{array}{ccccccc} +1&+1&+1&+1&+1&+1&+1&\cdots \\ +1&-1&+1&-1&+1&-1&+1 \\ +1&+1&-2&+1&+1&-2&+1 \\ +1&-1&+1&-1&+1&-1&+1 \\ +1&+1&+1&+1&-4&+1&+1 \\ +1&-1&-2&-1&+1&+2&+1 \\ +1&+1&+1&+1&+1&+1&-6 \\ \vdots&&&&&&&\ddots \end{array} \right)$$

$$\sum\limits_{k=1}^{\infty}\sum\limits_{n=1}^{\infty} \frac{T(n,k)}{n^c \cdot k^s} = \sum\limits_{n=1}^{\infty} \frac{\lim\limits_{z \rightarrow s} \zeta(z)\sum\limits_{d|n} \frac{\mu(d)}{d^{(z-1)}}}{n^c} = \frac{\zeta(s) \cdot \zeta(c)}{\zeta(c + s - 1)}$$

which is part of the limit:

$$-\frac{\zeta '(s)}{\zeta (s)}=\lim_{c\to 1} \, \left(\frac{\zeta (c) \zeta (s)}{\zeta (c+s-1)}-\zeta (c)\right)$$ $$\int -\frac{\zeta '(s)}{\zeta (s)} ds = -\log(\zeta(s))$$ $$\exp(-\log(\zeta(s)))$$ $$=\frac{1}{\zeta(s)}$$

Now 7 columns (or the 7 first terms of the Möbius function) give 65 correct terms of the Liouville function when rounded, and $\sqrt(49)=7$ and 49 is less than 65, so yes probably.