Mobius inversion over the divisor lattice

Given \(f(n) = \sum_{d | n} g(d)\), recover \(g(n) = \sum_{d | n} \mu(n/d) f(d)\).

Usage

morie_mobius_inversion(f_values)

Arguments

f_values

f_values[i] is \(f(i)\).

Value

A list with g, mobius, reconstruction_residual, mobius_identity_residual, divisor_sums.

Details

The check that matters is the defining property of \(\mu\): \(\sum_{d | n} \mu(d)\) is 1 at \(n = 1\) and 0 everywhere else. That is an identity, and the residual is returned rather than assumed.

References

Stanley RP (2011) vol. 1, Sec 3.7.

Examples

V <- c(1, 2, 3, 4, 5, 6, 7, 8)
morie_mobius_inversion(V)
#> $g
#> [1] 1 1 2 2 4 2 6 4
#> 
#> $mobius
#> [1]  1 -1 -1  0 -1  1 -1  0
#> 
#> $divisor_sums
#> [1] 1 0 0 0 0 0 0 0
#> 
#> $reconstruction_residual
#> [1] 0
#> 
#> $mobius_identity_residual
#> [1] 0
#> 
#> $n
#> [1] 8
#> 
#> $method
#> [1] "Mobius inversion (Stanley 3.7)"
#>