galois.mobius(n: int) → int

Evaluates the Möbius function \(\mu(n)\).

Parameters:
n: int

A positive integer.

Returns:

The Möbius function \(\mu(n)\), which takes values in \(\{-1, 0, 1\}\) and is defined by

\[\begin{split}\mu(n) = \begin{cases} 1, & \text{if } n = 1, \\ 0, & \text{if } p^2 \mid n \text{ for some prime } p, \\ (-1)^k, & \text{if } n = p_1 p_2 \cdots p_k \text{ is a product of } k \text{ distinct primes}. \end{cases}\end{split}\]

See also

euler_phi, carmichael_lambda, totatives, is_square_free

Notes

The Möbius function \(\mu(n)\) is a multiplicative arithmetic function that encodes the square-free structure of \(n\):

  • \(\mu(1) = 1\).

  • \(\mu(n) = 0\) if \(n\) is divisible by the square of a prime (i.e., \(n\) is not square-free).

  • If \(n\) is square-free with prime factorization \(n = p_1 p_2 \cdots p_k\), then \(\mu(n) = (-1)^k\), so \(\mu(n) = -1\) when \(n\) has an odd number of distinct prime factors, and \(\mu(n) = 1\) when \(n\) has an even number.

The Möbius function plays a central role in Dirichlet convolution and inversion. If \(f\) and \(F\) are arithmetic functions related by

\[ F(n) = \sum_{d \mid n} f(d), \]

then Möbius inversion recovers \(f\) from \(F\) via

\[ f(n) = \sum_{d \mid n} \mu(d)\, F\!\left(\frac{n}{d}\right). \]

A classical identity characterizing \(\mu\) is

\[\begin{split}\sum_{d \mid n} \mu(d) = \begin{cases} 1, & \text{if } n = 1, \\ 0, & \text{if } n > 1, \end{cases}\end{split}\]

meaning that \(\mu\) is the Dirichlet inverse of the constant function \(1(n) \equiv 1\).

This implementation uses the prime factorization

\[ n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}. \]

If any exponent \(e_i > 1\), then \(\mu(n) = 0\). Otherwise \(n\) is square-free and \(\mu(n) = (-1)^k\) where \(k\) is the number of distinct prime factors.

References

Examples

Basic values of the Möbius function.

In [1]: [galois.mobius(n) for n in range(1, 21)]
Out[1]: [1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, 0]

Values for powers of primes and square-free products.

# 1 by definition
In [2]: assert galois.mobius(1) == 1

# 2, one prime factor
In [3]: assert galois.mobius(2) == -1

# 2 * 3, two distinct primes
In [4]: assert galois.mobius(6) ==  1

# 2^2 * 3, not square-free
In [5]: assert galois.mobius(12) ==  0

Verify the identity \(\sum_{d \mid n} \mu(d) = 0\) for \(n > 1\).

In [6]: for n in range(1, 100):
   ...:     s = sum(galois.mobius(d) for d in range(1, n + 1) if n % d == 0)
   ...:     if n == 1:
   ...:         assert s == 1
   ...:     else:
   ...:         assert s == 0
   ...: