Math.NumberTheory.MoebiusInversion

Generalised Moebius inversion

Documentation

generalInversion :: (Int -> Integer) -> Int -> Integer

generalInversion g n evaluates the generalised Moebius inversion of g at the argument n.

The generalised Moebius inversion implemented here allows an efficient calculation of isolated values of the function f : N -> Z if the function g defined by

g n = sum [f (n `quot` k) | k <- [1 .. n]]

can be cheaply computed. By the generalised Moebius inversion formula, then

f n = sum [moebius k * g (n `quot` k) | k <- [1 .. n]]

which allows the computation in O(n) steps, if the values of the Moebius function are known. A slightly different formula, used here, does not need the values of the Moebius function and allows the computation in O(n^0.75) steps, using O(n^0.5) memory.

An example of a pair of such functions where the inversion allows a more efficient computation than the direct approach is

f n = number of reduced proper fractions with denominator <= n

g n = number of proper fractions with denominator <= n

(a proper fraction is a fraction 0 < n/d < 1). Then f n is the cardinality of the Farey sequence of order n (minus 1 or 2 if 0 and/or 1 are included in the Farey sequence), or the sum of the totients of the numbers 2 <= k <= n. f n is not easily directly computable, but then g n = n*(n-1)/2 is very easy to compute, and hence the inversion gives an efficient method of computing f n.

Since the function arguments are used as array indices, the domain of f is restricted to Int.

The value f n is then computed by generalInversion g n. Note that when many values of f are needed, there are far more efficient methods, this method is only appropriate to compute isolated values of f.

totientSum :: Int -> Integer

totientSum n is, for n > 0, the sum of [totient k | k <- [1 .. n]], computed via generalised Moebius inversion. Arguments less than 1 cause an error to be raised.