The Hidden Oscillations Behind Prime Numbers: Mertens Function Revealed

 

Introduction to the Mertens Function

The Mertens function, denoted M(x) is one of the central objects in analytic number theory. It is defined as the cumulative sum of the Möbius function:

where  encodes the arithmetic structure of integers:  if  has a squared prime factor,  if  is a product of an even number of distinct primes, and  if  is a product of an odd number of distinct primes.

This deceptively simple definition hides deep connections to the distribution of prime numbers and the zeros of the Riemann zeta function. The oscillatory behavior of  reflects the delicate balance between integers with an even versus odd number of prime factors, and its growth rate is intimately tied to the truth of the Riemann Hypothesis. In fact, the famous (and now disproven) Mertens conjecture once claimed that   for all , a bound that would have implied the Riemann Hypothesis.

Beyond its theoretical significance, the Mertens function plays a practical role in computational number theory. Efficient algorithms for evaluating  rely on identities that reduce large computations to smaller recursive calls, making it possible to explore its values far beyond what direct summation would allow.

In this article, we will examine the definition, properties, and computational techniques for , highlighting both its historical importance and its modern role in analytic number theory.

The Möbius function

The Möbius function  is defined as follows:

If  then .

If  and its prime factorization is

 then if all exponents are equal to ,  (i.e.,  is square free),

where  is the number of distinct prime factors.

Otherwise (if  has a squared prime factor) .

Note that  if  has a square factor > 1.

In essence, the Möbius function, encodes whether an integer is square-free and, if so, the parity of its number of prime factors.

Example

The first ten values of the Möbius function are:

,  ,

 ,  ,

 ,  ,  

,  ,

,  .

Multiplicativity

The Möbius function is an arithmetic function, and one of its key properties is multiplicativity.

An arithmetic function  is called multiplicative if it is not identically zero and if

whenever .

For the Möbius function:

If either  or  has a squared prime factor, then so does . In this case,

If both  and  are square-free, write

with distinct primes . Then

This confirms that  is multiplicative.

Remarks

Note that . This illustrates that multiplicativity only applies when the arguments are coprime.

If  is a prime with , then

Möbius and the Riemann Zeta Function

Consider the product taken over all the distinct prime divisors of an integer :

 If  are the primes dividing , then

Expanding this product gives

where the first sum is over all the reciprocals of prime divisors, the second is over all products of reciprocals taken two at a time and so on. Note that each term is of the form  where  is a divisor of . The numerator  is precisely the Möbius function value . Thus,

Generalization with Exponent

More generally, for  complex,

Letting  , we obtain the celebrated identity:

Obviously using the unity function  for every  we can write:

Since both series are absolutely convergent for , we can multiply and rearrange the terms in any way we please without altering the sum. We chose to collect together those terms for which  is a constant for all possible values of the constant, i.e.,

This proves that

where

() is the indicator of .

What it means

If you take all divisors  of  and sum their Möbius values, the result is zero unless .

For , the only divisor is , and , so the sum equals 1. 

For any larger , the positive and negative contributions of  cancel out, or a square factor forces terms to vanish, so the sum is 0.

 

Application: Möbius Summation Identity

Obviously

Substitute this into the sum:

Now set . Then , and for each  the possible  are precisely the divisors of .

Hence the sum becomes

The standard Möbius identity

yields:

Thus,

or

The last two equivalent formulas describe the known Möbius Summation Identity.

From Möbius Summation to Perron’s Formula

Now, hold onto the fundamental identity

In The Riemann Hypothesis Revealed: A Comprehensive Guide through Complex Analysis, the reader encounters a classical result from complex analysis: the Heaviside step function can be expressed as the inverse Mellin transform of . Specifically,

That is, the integral equals  for ,  for , and takes the value  at  This identity plays a central role in explicit formulas of analytic number theory, where constant or slowly varying analytic terms translate into step-function contributions in the variable . Full details and derivations are provided in the book available in all Amazon Marketplaces.

Perron’s formula.

From this Mellin-transform identity, one derives Perron’s formula.

Let  be an arithmetic function and let

be its corresponding Dirichlet series. Let  be absolutely convergent for , where  is the abscissa of convergence. We also consider , . Then we define

The prime on the summation indicates that the last term of the sum must be multiplied by  when  is an integer.

Then, provided  we have:

This is Perron’s formula. The integral on the left side represents an Inverse Mellin transform (in some sense).

 

Perron’s Formula and the Mertens Function

Set

Then

By Perron’s formula we have

or

In Number theory the Mertens function is defined by

When  is an integer, the last term in the sum contributes fully as . However, in Perron’s formula, the summation is taken with a prime notation, meaning that if  is an integer, the last term is counted with weight . Thus we obtain

The discrepancy between  and the integral representation is therefore at most  or zero. This minor difference is negligible in asymptotic considerations as .

Residue Calculation for Perron’s Formula

We consider the rectangular contour with vertices

and let . By the Residue Theorem, the integral in Perron’s formula is equal to the sum of the residues of the integrand

at the enclosed poles. For , this contour eventually encloses:

the trivial zeros of  at negative even integers,

the nontrivial zeros of  in the critical strip, and

the pole of the integrand at .

Residues at the Trivial Zeros

At  ():

Using the functional equation of the zeta function,

and differentiating at , one obtains

Hence,

 

Residues at the Nontrivial Zeros

For a nontrivial zero  of  in the critical strip,

Finally for the pole at :

Final Expression for the Mertens Function

By the Residue Theorem, the Mertens function can be expressed as

All of these topics — Perron’s formula, the Residue Theorem, the functional equation of the Riemann zeta function, and the role of Mellin transforms — are presented and explained in full detail in my book: The Riemann Hypothesis Revealed: A Comprehensive Guide through Complex Analysis. All Amazon marketplaces 

This representation of the Mertens function is valid under the assumption that all nontrivial zeros of the Riemann zeta function are simple. 

If a zero  had multiplicity greater than one, the residue calculation would involve higher-order terms, and the formula would require modification to account for those contributions.

Thus, the elegant form above holds provided  has only simple roots — a condition widely believed to be true but not yet proven.

Speculative Considerations on Convergence

The trivial-zero series (the sum over ) converges absolutely and very rapidly for large  because of the factorial   in the denominator and the factor ; it is a small correcting tail for large .

The nontrivial-zero sum

is only conditionally convergent and must be understood with a symmetric ordering: sum zeros with imaginary parts in pairs  and  (or sum with  and let ).

Assuming all zeros are simple and lie on the critical line, i.e.,  we have

Let . Then

For  we have  and

where . This is a real oscillatory series with “frequencies” . Each  is a zero ordinate — so they increase roughly linearly with index.

A natural next step would be to examine the density of the zeta zeros and the spacing of the associated oscillatory frequencies, followed by an analysis of the size of the coefficients. This would allow one to apply the Dirichlet test for series of oscillatory terms.

Dirichlet test (classical form):

If  is a sequence of real numbers whose partial sums  are bounded, and  is a monotone sequence tending to ,then converges.

Density of zeros and spacing of frequencies

The Riemann–von Mangoldt formula, which describes the distribution of the zeros of the Riemann Zeta function, states that the number  of zeros of the Zeta function with imaginary parts greater than  and less than or equal to  satisfies

Hence the average spacing between consecutive zeros near height  is about

So as  grows, the zeros (and hence the oscillation frequencies ) become denser and denser.

This means the terms of  oscillate increasingly rapidly with alternating signs and phases, a behavior highly favorable to convergence (it’s like an “almost continuous” cosine integral).

Remark

The discussion above is speculative. Exploring the convergence of  through the interplay of zero density, coefficient size, and oscillatory cancellation could be a fascinating quest for the curious reader — one that lies at the heart of analytic number theory and the mysteries surrounding the Riemann Hypothesis.

Back to Concrete Computations: The Mertens Function

Let’s return to something more down-to-earth — the actual computation of the Mertens function. A particularly useful identity is

This recursive relation expresses  entirely in terms of values of  at smaller arguments, making it a handy tool for both theoretical analysis and numerical computation.

To prove it consider

Swap the order of summation:

Now rewrite this as a sum over integers :

By the fundamental identity  (the indicator of ), we have

Therefore,

Isolate the term for :

Thus

which rearranges to

 

Implementation (c++)

#pragma once #include <bits/stdc++.h> using namespace std;   namespace mobius {     using int64 = long long;     using mobius_mu = vector<int>;     using mobius_prefixM = vector<int64>;       class mobius_cfg     {     public:         static constexpr int MAX_VALUE = 50000000;         explicit mobius_cfg(int64 x) : x_(x)         {             // Choose sieve bound L ~ x^(2/3)             L_ = max(100, (int)pow((long double)x, 2.0L / 3.0L));             L_ = min(L_, MAX_VALUE); // cap for memory safety         }         int64 input() const noexcept { return x_; }         int sieve_bound() const noexcept { return L_; }       private:         int64 x_;         int L_;           friend void mobius_m(const mobius_cfg &, mobius_mu *, mobius_prefixM *);     };       class mertens     {     public:         explicit mertens(int64 x)         {             mu = new mobius_mu();             prefixM = new mobius_prefixM();             init(x);         }           ~mertens()         {             delete mu;             delete prefixM;         }           int64 mertens_M(int64 n)         {             if (n <= L)                 return (*prefixM)[n];             if (memo.count(n))                 return memo[n];               int64 res = 1;             int64 k = 2;             while (k <= n)             {                 int64 q = n / k;                 int64 r = n / q; // largest r with floor(n/r) = q                 res -= (r - k + 1) * mertens_M(q);                 k = r + 1;             }             return memo[n] = res;         }       private:         mobius_mu *mu;         mobius_prefixM *prefixM;         unordered_map<int64, int64> memo;         int L;           void init(int64 x)         {             mobius_cfg cfg(x);             L = cfg.sieve_bound();               // Compute mu and prefixM             mobius_m(cfg, mu, prefixM);               memo.clear();             for (int i = 0; i <= L; ++i)                 memo[i] = (*prefixM)[i];         }     };       // Compute Möbius function mu[1..L] and prefix sums M[0..L]     inline void mobius_m(const mobius_cfg &cfg, mobius_mu *mu, mobius_prefixM *prefixM)     {         int L = cfg.sieve_bound();         mu->assign(L + 1, 0);           vector<int> primes;         vector<int> minPrime(L + 1, 0);           (*mu)[1] = 1;         for (int i = 2; i <= L; ++i)         {             if (minPrime[i] == 0)             { // i is prime                 minPrime[i] = i;                 primes.push_back(i);                 (*mu)[i] = -1;             }             for (int p : primes)             {                 int64 v = 1LL * p * i;                 if (v > L)                     break;                 minPrime[v] = p;                 if (i % p == 0)                 {                     (*mu)[v] = 0; // square factor                     break;                 }                 else                 {                     (*mu)[v] = -(*mu)[i];                   // mu[ p * i ] = (-1) mu[ i ] when gcd(p,i)=1                 }             }         }           // Build prefix sums of mu         prefixM->assign(L + 1, 0);         for (int i = 1; i <= L; ++i)             (*prefixM)[i] = (*prefixM)[i - 1] + (*mu)[i];     }   }

 

Remarks

This line

L_ = max(100, (int)pow((long double)x, 2.0L / 3.0L));

choses a sieve limit for precomputing the Möbius function. You don’t want to sieve all the way up to x (too slow if x is huge), but you need enough precomputed values to make the recursive algorithm efficient. A good compromise is to sieve up to about .

Why ?

This choice balances:

• Sieve cost: Computing Möbius values up to L costs .
• Recursion cost: The recursive formula for needs values of . If you sieve up to , the recursion depth is about . Together, this gives a total complexity of about , which is efficient for large .

Step-by-Step Explanation of the Loop

while (k <= n)             {                 int64 q = n / k;                 int64 r = n / q; // largest r with floor(n/r) = q                 res -= (r - k + 1) * mertens_M(q);                 k = r + 1;             }

1. Start with k = 2. We want to subtract terms of the form .
2. Compute q = n / k.
• This is the current quotient .
• For all values of in some interval, this quotient will stay the same.
3. Find r = n / q.
• This is the largest such that .
• In other words, for all in the range , the quotient is constant.
4. Group the contribution.
• Instead of subtracting  once for each  in that range, we subtract it multiplied by the number of terms:

This collapses many identical terms into one operation.

5. Advance k.
• Set  to move to the next range where the quotient changes.

 

Why This Is Efficient

Each distinct quotient  is processed once.
The number of distinct quotients is about , not .
This makes the recursion practical even for very large .

 

Run

Save the code as arithmetic.h in a folder named include and create the following main.cpp

#include <iostream> #include "include/arithmetic.h"      using namespace std; using namespace mobius;   int main() {     int64 x = 15000;       cout << "M(" << x << ") computation starting...\n";       // Configure the sieve/Mertens calculator     mertens calc(x);       // Compute values from 1..x     for (int64 i = 1; i <= x; ++i)     {         cout << "M(" << i << ") = " << calc.mertens_M(i) << "\n";     }       return 0; }