Back to Number Theory Dsa

Arithmetic Functions, Convolution & Möbius Inversion

September 22, 2026 Wasil Zafar 9 min read

Exploit multiplicativity and convolution to transform counting problems.

Table of Contents

  1. Intuition, Vocabulary and Foundations
  2. Step-by-Step Derivations and Algorithms
  3. Implementation, Complexity and Engineering
  4. Applications, Case Studies and Exercises

Intuition, Vocabulary and Foundations

Arithmetic functions attach information to each positive integer. If $n=12=2^2\cdot3$, then $\varphi(12)=4$ counts residues coprime to $12$, $\mu(12)=0$ records that a square divides $12$, $\tau(12)=6$ counts its divisors, and $\sigma(12)=28$ sums them. Think of the divisors as a dependency network: a value stored at $d$ can contribute to every multiple of $d$.

For $n=\prod_i p_i^{e_i}$, unique factorization gives

$$ \varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right),\qquad \tau(n)=\prod_i(e_i+1),\qquad \sigma(n)=\prod_i\frac{p_i^{e_i+1}-1}{p_i-1}. $$

The Möbius function is $\mu(1)=1$; it is $0$ when some $p^2$ divides $n$; otherwise it is $(-1)^k$ when $n$ is a product of $k$ distinct primes. An arithmetic function $f$ is multiplicative when $f(ab)=f(a)f(b)$ for $\gcd(a,b)=1$—not necessarily for arbitrary $a,b$. Dirichlet convolution combines functions by

$$ (f*g)(n)=\sum_{d\mid n}f(d)g(n/d). $$

Its identity is $\varepsilon(1)=1$ and $\varepsilon(n)=0$ for $n>1$. With $\mathbf 1(n)=1$, the defining inverse relation is $\mu*\mathbf 1=\varepsilon$. Therefore, if $F(n)=\sum_{d\mid n}f(d)$, then Möbius inversion recovers $f(n)=\sum_{d\mid n}\mu(d)F(n/d)$.

Treat divisor sums as a reversible transform on the divisor lattice: convolution with $\mathbf 1$ accumulates information upward to multiples, and convolution with $\mu$ removes exactly that accumulated contribution. Multiplicative prime-power formulas apply only after checking coprimality or using a valid factorization.

ConceptDefinition or notationExampleNon-example or boundaryQuestion answered
Euler totient$\varphi(n)$ counts $1\le k\le n$ with $\gcd(k,n)=1$$\varphi(12)=4$$\varphi(1)=1$, not $0$How many invertible residue classes exist?
Möbius function$\mu(n)$ detects square-free prime parity$\mu(30)=-1$$\mu(12)=0$ because $4\mid12$Can a divisor sum be inverted?
Divisor count$\tau(n)=\sum_{d\mid n}1$$\tau(12)=6$$\tau(1)=1$How many positive divisors exist?
Divisor sum$\sigma(n)=\sum_{d\mid n}d$$\sigma(12)=28$Proper-divisor sum is $\sigma(n)-n$What is the total divisor weight?
Multiplicativity$f(ab)=f(a)f(b)$ when $\gcd(a,b)=1$$\tau(12)=\tau(4)\tau(3)$$\tau(8)\ne\tau(4)\tau(2)$Can prime-power results be combined?
Dirichlet convolution$(f*g)(n)=\sum_{d\mid n}f(d)g(n/d)$$\mathbf1*\mathbf1=\tau$It is not pointwise multiplicationHow do divisor-indexed contributions compose?
Summatory function$S_f(x)=\sum_{n\le x}f(n)$$\sum_{n\le5}\varphi(n)=10$It is not the point value $f(x)$What is the aggregate through a bound?

Step-by-Step Derivations and Algorithms

A linear sieve evaluates several multiplicative functions while assigning every composite through its smallest prime factor. When processing $i$ and a prime $p$, form $x=ip$. If $p\mid i$, then $p$ extends an existing prime power: $\mu(x)=0$, $\varphi(x)=p\varphi(i)$, and the divisor formulas update the exponent of $p$. The loop then stops, ensuring that $x$ is generated once. If $p\nmid i$, a new coprime prime factor is introduced: $\mu(x)=-\mu(i)$ and $\varphi(x)=(p-1)\varphi(i)$.

For an array $a$, the divisor zeta transform computes $A(n)=\sum_{d\mid n}a(d)$ by adding $a(d)$ to $A(d),A(2d),A(3d),\ldots$. The number of additions is

$$ \sum_{d=1}^{N}\left\lfloor\frac Nd\right\rfloor=O(N\log N). $$

Möbius inversion reverses the transform with the same traversal pattern. For quotient-dependent sums, values of $\lfloor N/i\rfloor$ are constant on blocks. Starting at $l$, set $q=\lfloor N/l\rfloor$ and $r=\lfloor N/q\rfloor$; every $i\in[l,r]$ has quotient $q$. Replacing $N$ iterations by these blocks yields only $O(\sqrt N)$ distinct ranges.

Arithmetic Functions, Convolution & Möbius Inversion algorithm map
flowchart TD
    A["Prime factorization model"] --> B["Prime-power formulas"]
    A --> C["Linear sieve states"]
    B --> D["Multiplicative tables"]
    C --> D
    D --> E["Divisor zeta transform"]
    E --> F["Möbius inversion"]
    D --> G["Prefix sums"]
    G --> H["Harmonic quotient blocks"]

The linear-sieve invariant is that each composite is emitted exactly once, paired with its smallest prime factor; this proves $O(N)$ arithmetic updates and $O(N)$ storage. Dense divisor transforms take $\Theta(N\log N)$ operations, while a loop whose summand depends only on $\lfloor N/i\rfloor$ can be grouped into $\Theta(\sqrt N)$ quotient blocks.

Implementation, Complexity and Engineering

The reference implementation keeps pointwise tables separate from prefix or transformed arrays. It uses integer recurrences rather than floating-point product formulas, explicitly initializes the exceptional value at $1$, and exposes transformations as new arrays so callers cannot silently confuse the input with its divisor sum.

from typing import Iterable


def arithmetic_function_sieve(limit: int):
    """Return primes and pointwise phi, mu, tau, sigma tables through limit."""
    if limit < 1:
        raise ValueError("limit must be at least 1")

    primes: list[int] = []
    least = [0] * (limit + 1)
    phi = [0] * (limit + 1)
    mu = [0] * (limit + 1)
    tau = [0] * (limit + 1)
    sigma = [0] * (limit + 1)
    exponent = [0] * (limit + 1)
    prime_power = [1] * (limit + 1)

    phi[1] = mu[1] = tau[1] = sigma[1] = 1
    for value in range(2, limit + 1):
        if least[value] == 0:
            least[value] = value
            primes.append(value)
            phi[value] = value - 1
            mu[value] = -1
            exponent[value] = 1
            prime_power[value] = value
            tau[value] = 2
            sigma[value] = value + 1

        for prime in primes:
            composite = value * prime
            if composite > limit:
                break
            least[composite] = prime
            if prime == least[value]:
                exponent[composite] = exponent[value] + 1
                prime_power[composite] = prime_power[value] * prime
                rest = value // prime_power[value]
                phi[composite] = phi[value] * prime
                mu[composite] = 0
                tau[composite] = tau[rest] * (exponent[composite] + 1)
                sigma[composite] = sigma[rest] * (
                    (prime_power[composite] * prime - 1) // (prime - 1)
                )
                break
            exponent[composite] = 1
            prime_power[composite] = prime
            phi[composite] = phi[value] * (prime - 1)
            mu[composite] = -mu[value]
            tau[composite] = tau[value] * 2
            sigma[composite] = sigma[value] * (prime + 1)

    return primes, phi, mu, tau, sigma


def divisor_zeta_transform(values: Iterable[int]) -> list[int]:
    """Return sums[d over n] values[d] for indices 1..N."""
    source = list(values)
    if len(source) < 2:
        raise ValueError("values must contain indices 0 and 1")
    limit = len(source) - 1
    result = [0] * (limit + 1)
    for divisor in range(1, limit + 1):
        for multiple in range(divisor, limit + 1, divisor):
            result[multiple] += source[divisor]
    return result


def mobius_invert(divisor_sums: Iterable[int], mu: list[int]) -> list[int]:
    """Invert F(n)=sum_{d|n} f(d), given a Mobius table."""
    totals = list(divisor_sums)
    limit = len(totals) - 1
    if limit < 1 or len(mu) <= limit:
        raise ValueError("incompatible tables")
    result = [0] * (limit + 1)
    for divisor in range(1, limit + 1):
        if mu[divisor] == 0:
            continue
        for multiple in range(divisor, limit + 1, divisor):
            result[multiple] += mu[divisor] * totals[multiple // divisor]
    return result


def harmonic_blocks(limit: int):
    """Yield inclusive ranges [left, right] sharing floor(limit / i)."""
    if limit < 0:
        raise ValueError("limit must be nonnegative")
    left = 1
    while left <= limit:
        quotient = limit // left
        right = limit // quotient
        yield left, right, quotient
        left = right + 1


def count_ordered_coprime_pairs(limit: int, mu: list[int]) -> int:
    """Count ordered (x,y) with 1 <= x,y <= limit and gcd(x,y)=1."""
    if limit < 0 or len(mu) <= limit:
        raise ValueError("invalid limit or Mobius table")
    return sum(mu[d] * (limit // d) ** 2 for d in range(1, limit + 1))


if __name__ == "__main__":
    primes, phi, mu, tau, sigma = arithmetic_function_sieve(30)
    assert primes[:5] == [2, 3, 5, 7, 11]
    assert (phi[12], mu[12], tau[12], sigma[12]) == (4, 0, 6, 28)
    assert (phi[1], mu[1], tau[1], sigma[1]) == (1, 1, 1, 1)

    values = [0, 3, -1, 4, 1, 5]
    transformed = divisor_zeta_transform(values)
    assert mobius_invert(transformed, mu) == values
    assert list(harmonic_blocks(10)) == [
        (1, 1, 10), (2, 2, 5), (3, 3, 3),
        (4, 5, 2), (6, 10, 1),
    ]
    assert count_ordered_coprime_pairs(5, mu) == 19
    print("all tests passed")
MethodTimeSpaceNumeric concernCommon failureMitigation
Per-value factorization$O(\sqrt n)$ per query$O(1)$Large intermediate powersRepeating work over a batchUse a sieve when the maximum bound is moderate
Linear function sieve$O(N)$$O(N)$$\sigma(n)$ may exceed fixed-width typesUpdating a composite more than onceStop after extending its smallest prime factor
Divisor zeta transform$O(N\log N)$$O(N)$Accumulated sums can overflowConfusing divisor and multiple loopsTest against explicit divisor enumeration
Möbius inversion$O(N\log N)$ for all values$O(N)$Signed cancellationUsing pointwise multiplicationVerify by applying the forward transform again
Harmonic grouping$O(\sqrt N)$ blocks$O(1)$ excluding outputProducts of block width and valueAdvancing only one indexJump to $r=\lfloor N/q\rfloor$
Prefix summation$O(N)$ build, $O(1)$ range query$O(N)$Prefix totals may be much larger than termsTreating $S_f(n)$ as $f(n)$Use distinct names and types for pointwise and cumulative data

Applications, Case Studies and Exercises

Möbius inversion turns a condition about a greatest common divisor into divisor counts. Since $[\gcd(x,y)=1]=\sum_{d\mid\gcd(x,y)}\mu(d)$, the number of ordered coprime pairs in $[1,N]^2$ is

$$ \sum_{d=1}^{N}\mu(d)\left\lfloor\frac Nd\right\rfloor^2. $$

The same pattern counts coprime $k$-tuples by replacing the square with the $k$th power. In a batch analytics system, a divisor transform can aggregate device measurements by every calibration period that divides a timestamp; Möbius inversion then recovers the exact-period contribution rather than the cumulative contribution.

Practice

Apply Arithmetic Functions, Convolution & Möbius Inversion

Case study 1 — coprime grid points. Set $N=5$. Build $\mu(1),\ldots,\mu(5)$, then evaluate $\sum_{d=1}^{5}\mu(d)\lfloor5/d\rfloor^2$. Checkpoint: the contributions are $25,-4,-1,0,-1$, giving $19$. Verify by listing the $25$ ordered pairs and rejecting the six pairs whose gcd exceeds $1$.

Case study 2 — recovering exact subscription periods. Suppose $F(n)$ is the number of services whose period divides day $n$, with $F(1..6)=(2,5,3,7,4,8)$. Compute $f(n)=\sum_{d\mid n}\mu(d)F(n/d)$. Checkpoint: reconstruct each $F(n)$ from $\sum_{d\mid n}f(d)$; success means all six values match exactly.

Hands-on challenge. Implement a reusable table through $N=10^6$ and answer: $\varphi(n)$, $\mu(n)$, $\tau(n)$, $\sigma(n)$, and the number of ordered coprime pairs up to a requested bound. Test $N=1$, primes, prime powers, square-free composites, and values containing a squared prime. Measure build time and peak memory; success requires agreement with a naive factorization oracle for every $n\le1000$.

Tiered exercises. (1) Recall: compute $\mu(18)$, $\tau(72)$, and $\sigma(25)$. (2) Derivation: prove that the convolution of multiplicative functions is multiplicative. (3) Implementation: add prefix sums of $\mu$ and $\varphi$. (4) Debugging: find why failing to stop the inner linear-sieve loop double-processes composites. (5) Extension: use quotient blocks to evaluate a weighted floor sum without visiting every index.

Choose factorization for a few isolated inputs, a linear sieve for dense pointwise tables, divisor transforms for all-divisor aggregation, and harmonic grouping when only floor quotients matter. Never confuse multiplicative with completely multiplicative, or $f(n)$ with its summatory value; these tools lead naturally to faster summatory functions and coprimality-counting techniques.

Next in the Series

In Modular Combinatorics, we'll explore Evaluate combinatorial quantities under prime and composite moduli..

Continue the Series

Sieves & Bulk Precomputation

Precompute prime and factor information at scale.

Read Article