Möbius Inversion & Dirichlet Convolution

Every positive integer $n$ has a collection of divisors, and many fundamental quantities in number theory — the count of divisors, the sum of divisors, Euler's totient — are defined by summing something simple over those divisors.

These are called arithmetic functions: maps $f : \mathbb{N} \to \mathbb{C}$. The most useful ones are multiplicative: whenever $\gcd(m,n)=1$, we have $f(mn) = f(m)f(n)$. The identity function $\text{id}(n)=n$, the constant function $\mathbf{1}(n)=1$, and Euler's totient $\phi(n)$ are all multiplicative.

What makes them powerful is that they can be composed through Dirichlet convolution: given $f$ and $g$, define

$$(f * g)(n) = \sum_{d \mid n} f(d)\, g\!\left(\tfrac{n}{d}\right).$$

This operation is commutative, associative, and — crucially — invertible. The identity element is $\varepsilon$ with $\varepsilon(1)=1$ and $\varepsilon(n)=0$ for $n>1$. The inverse of the constant function $\mathbf{1}$ is the Möbius function $\mu$, defined by August Ferdinand Möbius in 1832:

$$\mu(n) = \begin{cases} 1 & n = 1 \\ (-1)^k & n = p_1 p_2 \cdots p_k \text{ (distinct primes)} \\ 0 & p^2 \mid n \text{ for some prime } p. \end{cases}$$

The key identity $\sum_{d \mid n} \mu(d) = \varepsilon(n)$ says that $\mathbf{1} * \mu = \varepsilon$ — Möbius is the multiplicative inverse of 1 under Dirichlet convolution. This gives us Möbius inversion: if $g = f * \mathbf{1}$ (i.e., $g(n) = \sum_{d \mid n} f(d)$), then $f = g * \mu$ (i.e., $f(n) = \sum_{d \mid n} g(d)\,\mu(n/d)$). Any summatory function can be inverted in one formula.

Pick one of the classic arithmetic functions below. The demo computes its Dirichlet sum $g(n) = \sum_{d \mid n} f(d)$ for $n = 1 \ldots 12$, displays the results, then inverts with $f(n) = \sum_{d \mid n} g(d)\,\mu(n/d)$ and verifies you get back the original.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>{{choose_f}}</label>
  <div class="btn-group" id="fn-picker">
    <button class="fn-btn active" data-fn="id1" type="button">f(n) = 1</button>
    <button class="fn-btn" data-fn="id" type="button">f(n) = n</button>
    <button class="fn-btn" data-fn="phi" type="button">φ(n)</button>
    <button class="fn-btn" data-fn="sq" type="button">f(n) = n²</button>
  </div>
</div>
<div class="table-wrap">
  <table id="main-table">
    <thead>
      <tr>
        <th>n</th>
        <th>μ(n)</th>
        <th>f(n)</th>
        <th>g = f★1</th>
        <th>g★μ</th>
        <th class="check-col">{{col_ok}}</th>
      </tr>
    </thead>
    <tbody id="tbody"></tbody>
  </table>
</div>
<div class="status" id="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .7rem; }
.controls label { font-weight: 600; white-space: nowrap; }
.btn-group { display: flex; gap: .3rem; flex-wrap: wrap; }
.fn-btn { font: 600 13px system-ui; padding: .35rem .7rem; border: 1px solid #1d3557;
          background: #fff; color: #1d3557; border-radius: 6px; cursor: pointer; transition: all .12s; }
.fn-btn.active { background: #1d3557; color: #fff; }
.fn-btn:hover:not(.active) { background: #e8eef3; }
.table-wrap { overflow-x: auto; }
table { border-collapse: collapse; width: 100%; }
th, td { padding: .32rem .6rem; text-align: right; border: 1px solid #cdd9e3; }
th { background: #e8eef3; color: #1d3557; font-weight: 700; white-space: nowrap; }
td:first-child, th:first-child { text-align: center; font-weight: 700; }
.mu-neg { color: #c92f3c; }
.mu-zero { color: #888; }
.mu-pos { color: #0a7d33; }
.check-col { text-align: center; }
td.check-col { font-size: 1rem; }
.ok { color: #0a7d33; }
.fail { color: #c92f3c; }
.status { font-weight: 600; margin-top: .5rem; min-height: 1.4em; font-size: .95rem; }
.status.all-ok { color: #0a7d33; }
.status.has-fail { color: #c92f3c; }

// Code not found

Notice that inverting costs nothing extra: once you know $\mu$, it's just another divisor sum of the same size. The asymmetry is in computing $\mu$ for large squarefree numbers — that requires factoring, which connects back to problems like integer factoring and discrete logarithms.

Möbius inversion itself is proven and elementary (Möbius, 1832; Dedekind formalized it in the 1870s). The formula is exact, not an approximation. So where is the difficulty?

• Evaluating $\mu(n)$ requires factoring $n$: you must check whether $n$ is squarefree and count its prime factors. For small $n$ this is trivial; for 100-digit $n$ it is as hard as general integer factoring — a problem with no known polynomial-time algorithm (see integer factoring).
• The Mertens function $M(x) = \sum_{n \le x} \mu(n)$ encodes how the $\pm 1$ values of $\mu$ cancel. The Mertens conjecture — that $|M(x)| < \sqrt{x}$ always — was disproved in 1985 by Odlyzko and te Riele, though the actual counterexample is astronomically large.
• The Riemann Hypothesis is equivalent to $M(x) = O(x^{1/2+\varepsilon})$ for every $\varepsilon > 0$. The Möbius function is thus a direct window into the deepest open question in mathematics — and it remains open.
• Dirichlet series: the generating function of $\mu$ is $\sum_{n=1}^\infty \mu(n)/n^s = 1/\zeta(s)$, the reciprocal of the Riemann zeta function. Every zero of $\zeta$ shows up as a singularity of this series, cementing the connection.

So Möbius inversion is solved, but living right next to it is the hardest problem in pure mathematics.

The Dirichlet convolution ring of multiplicative functions appears everywhere:

• Euler's totient formula: $\phi = \text{id} * \mu$, or equivalently $\text{id} = \phi * \mathbf{1}$. Inverting with $\mu$ recovers $\phi(n) = n \prod_{p \mid n}(1-1/p)$ — the formula underlying RSA key generation.
• Prime-counting function: Meissel and Lehmer used Möbius-like inclusion-exclusion to count primes up to $x$ in $O(x^{2/3})$ operations, far faster than a sieve.
• Inclusion-exclusion principle: Möbius inversion over the divisor poset is inclusion-exclusion — the two are the same identity in different languages, and the Möbius function of a general poset generalizes both.
• Combinatorics and posets: the abstract Möbius function of a partially ordered set (Hall, 1936; Rota, 1964) unifies dozens of counting formulas across combinatorics, algebraic topology and coding theory.
• Cryptography: the structure of multiplicative functions modulo $n$ underlies Euler's theorem, the Chinese Remainder Theorem, and the security of most public-key systems.

Learning Möbius inversion means you've learned the backbone of analytic number theory — the same algebra that powers both the Riemann Hypothesis and the encryption protecting your browser.

Möbius inversion is one of mathematics' most elegant tools: a single formula $f = g * \mu$ that undoes any Dirichlet sum and recovers the original function exactly. It is proven (Möbius, 1832), elementary, and works for every multiplicative function.

Yet the Möbius function itself is a window into the unknown. Its partial sums, the Mertens function, are directly tied to the Riemann Hypothesis — the most famous unsolved problem in mathematics. A formula that is two centuries old and trivially computable for small inputs becomes, at scale, the edge of what humanity knows.

That is the double life of $\mu$: a complete, usable answer on one side, and the frontier of number theory on the other.