Undo a divisor sum by controlled cancellation

Try

Suppose F(n) records the sum of unknown values f(d) over positive divisors d of n. Recovering f(n) requires subtracting contributions from proper divisors without overcounting their overlaps. Möbius inversion provides the exact cancellation pattern. Start with F(1)=f(1), F(2)=f(1)+f(2), and F(6)=f(1)+f(2)+f(3)+f(6); the final equation already shows why alternating corrections are needed.

Predict

Predict the coefficients needed to isolate f(6). Subtract F(2) and F(3) from F(6), then add F(1) because it was removed twice. The coefficients are 1,−1,−1, 1, corresponding to subsets of the two prime factors. Repeated prime factors require a different rule: a square factor makes the Möbius coefficient zero rather than continuing a simple sign pattern by total factor count.

Experiment

Inspect the function on divisors of twelve.

d	1	2	3	4	6	12
μ(d)	1	−1	−1	0	1	0

The sum is zero. Verify that only subsets of the distinct primes two and three contribute. Then use the coefficients to recover f(12) from the values F(12), F(6), F(4), F(2).

Understand

Define μ(1)=1; μ(n)=0 when a prime square divides n; otherwise μ(n)=(−1)^r for r distinct prime factors. If n>1 has r distinct primes, summing μ over its divisors gives (1−1)^r=0. At n=1 the sum is one. Now expand Σ_(d|n)μ(d)F(n/d) as a finite double sum using F(m)=Σ_(k|m)f(k). The coefficient of f(k) becomes Σ_(d|n/k)μ(d), which vanishes unless k=n. This proves inversion. No analytic interchange theorem is needed because all sums are finite, but the divisor indexing must be correct.

Apply

Applying inversion to Σ_(d|n)φ(d)=n gives φ(n)=Σ_(d|n)μ(d)n/d and recovers the product formula. Another application is squarefree counting: the indicator of squarefreeness is Σ_(d²|n)μ(d). Summing this identity over 1≤n≤N and reversing the finite sums gives the exact count Σ_(d≤√N)μ(d)⌊N/d²⌋. This is a finite computational formula. Replacing floors with real quotients and passing to an infinite series requires additional error estimates; the exact identity alone is not a proof of an asymptotic density.

For a worked inversion with a different quantity, let F(n) be the sum of an unknown function f over divisors. At n=6, inversion says f(6)=F(6)−F(3)−F(2)+F(1), because the squarefree divisors are one, two, three and six. Expand each F as a divisor sum and check that f(1), f(2) and f(3) cancel, leaving f(6). This is inclusion–exclusion on prime divisors in algebraic form. When n contains a repeated prime, μ assigns zero to divisors containing its square; this prevents counting a repeated prime as two independent choices.

Continue

Möbius inversion is an arithmetic form of inclusion–exclusion, but a correct proof should show the actual coefficient cancellation rather than rely only on that analogy. Test an inversion routine on a chosen f, form its divisor sums independently and recover the original values. Next, quadratic residues ask a different inversion question: which nonzero classes are squares, and how can their existence be decided without enumerating every square?

Return to the number theory unit to choose a targeted retry. Continue with identify which classes are squares.