An additively recursive definition of the Moebius function

Description of the problem

The Moebius function is one of the fundamental functions in number theory and has been the subject of few recent conjectures: see here and here.

It is defined as \[ \mu(n) = \begin{cases} 1 & \text{ if } n=1\\ (-1)^k & \text{ if $n=p_1\cdots p_k$ where $p_i$'s are distinct primes}\\ 0 & \text{ otherwise} \end{cases} \]

Today, I will give a recursive definition of $\mu$ which does not require you to factor $n$, or use a variation of Sieve of Eratosthenes. In fact, the only thing you have to know is $\mu(1)$.

Solution

The key fact I am going to use is \[ \sum_{q\|n}\mu(q) = \begin{cases} 1& \text{ if } n=1\\ 0& \text{ otherwise} \end{cases} \] Then \[ 1 = \sum_{m=1}^n\sum_{q\|m} \mu(q) \] Let me define \[ \nu(m,q) = \begin{cases} 1 & \text{ if } q\|m\\ 0 & \text{ otherwise} \end{cases} \] Then

Since the inner sum $\sum_{m=q}^n\nu(m,q) = \left\lfloor\frac{n}{q}\right\rfloor$ we get \[ 1 = \sum_{q=1}^n\mu(q)\left\lfloor\frac{n}{q}\right\rfloor \] By re-arranging the terms we get \[ \mu(n) = 1 - \sum_{q=1}^{n-1}\left\lfloor\frac{n}{q}\right\rfloor\mu(q) \] We know that $\mu(1)=1$. See if we can get $\mu(i)$ correctly for $i=2,3,4$:

\[ \mu(2) = 1 - 2\mu(1) = -1 \]

\[ \mu(3) = 1 - 3\mu(1) - \mu(2) = 1 - 3 + 1 = -1 \]

\[ \mu(4) = 1 - 4\mu(1) - 2\mu(2) - \mu(3) = 1 - 4 + 2 + 1 = 0 \]

An implementation in C

 #include<stdio.h>
 #include<math.h>
 #include<stdlib.h>

 long int *mu_arr;

 int mu(long int n) {
   long int j, res, temp;
   res = mu_arr[n];

   if(res!=-2)
     return(res);

   res = 0;
   for(j=1;j<n;j++) {
     temp = mu_arr[j];
     if(temp == -2)
       res += (int)(floor(n/j))*mu(j);
     else
       res += (int)(floor(n/j))*temp;
   }

   res = 1-res;
   mu_arr[n] = res;

   return(res);
 }


 int main(int argc, char *argv[]) {
   long int n, i, j;
   long int res;

   if(argc<1)
     return(0);

   n = atoll(argv[1]);

   mu_arr = (long *)malloc((n+1)*sizeof(long));
   for(i=0;i<=n;i++)
     mu_arr[i]=-2;

   mu_arr[1] = 1;

   for(i=1;i<=n;i++)
     printf("mu(%d) = %d\n",i,mu(i));

   free(mu_arr);

   return(1);
 }

Discussion

I was not aware of such an additively recursive definition of $\mu(n)$. The time complexity of the implementation is slightly worse than $\mathcal{O}(n^2)$. Since I am using only the four basic arithmetic operations, if-then conditionals, and bounded for loops in the algorithm with recursive calls, it is easy to see that $\mu(n)$ must be primitive recursive.

The Kitchen Sink and Other Oddities

An additively recursive definition of the Moebius function

Description of the problem

Solution

An implementation in C

Discussion