# Vaughan's Identity

## Theorem

Let $\Lambda$ be von Mangoldt's function.

Let $\mu$ be the Möbius function.

Then for $y, z \ge 1$ and $n > z$:

$\ds \map \Lambda n = \sum_{\substack {d \mathop \divides n \\ d \mathop \le y}} \map \mu d \map \ln {\frac n d} - \mathop {\sum \sum}_{\substack {d c \mathop \divides n \\ d \mathop \le y, \, c \mathop \le z}} \map \mu d \map \Lambda c + \mathop {\sum \sum}_{\substack {d c \mathop \divides n \\ d \mathop > y, \, c \mathop > z} } \map \mu d \map \Lambda c$

where $\divides$ denotes divisibility.

## Proof

$\ds \ln n = \sum_{d \mathop \divides n} \map \Lambda d$

Hence:

 $\ds \map \Lambda n$ $=$ $\ds \sum_{d \mathop \divides n} \map \mu d \map \ln {\frac n d}$ Möbius Inversion Formula $\ds$ $=$ $\ds \sum_{\substack {d \mathop \divides n \\ d \mathop \le y} } \map \mu d \map \ln {\frac n d} + \sum_{\substack {d \mathop \divides n \\ d \mathop > y} } \map \mu d \map \ln {\frac n d}$

Taking the second summation in that last line:

 $\ds \sum_{\substack {d \mathop \divides n \\ d \mathop > y} } \map \mu d \map \ln {\frac n d}$ $=$ $\ds \sum_{\substack {d \mathop \divides n \\ d \mathop > y} } \map \mu d \sum_{c \mathop \divides n / d} \map \Lambda c$ $\ds$ $=$ $\ds \mathop {\sum \sum}_{\substack {d c \mathop \divides n \\ d \mathop > y} } \map \mu d \map \Lambda c$ $\ds$ $=$ $\ds \mathop {\sum \sum}_{\substack {d c \mathop \divides n \\ d \mathop > y, \, c \mathop > z} } \map \mu d \map \Lambda c + \mathop {\sum \sum}_{\substack {d c \mathop \divides n \\ d \mathop > y, \, c \mathop \le z} } \map \mu d \, \map \Lambda c$

Again, taking the second summation in that last line:

$\ds \mathop {\sum \sum}_{\substack {d c \mathop \divides n \\ d \mathop > y, \, c \mathop \le z} } \map \mu d \map \Lambda c = \mathop {\sum \sum}_{\substack {d c \mathop \divides n \\ c \mathop \le z} } \map \mu d \map \Lambda c - \mathop {\sum \sum}_{\substack {d c \mathop \divides n \\ d \mathop \le y, \, c \mathop \le z} } \map \mu d \map \Lambda c$

Putting this together:

$\ds \map \Lambda n = \sum_{\substack {d \mathop \divides n \\ d \mathop \le y} } \map \mu d \map \ln {\frac n d} + \mathop {\sum \sum}_{\substack {d c \mathop \divides n \\ d \mathop > y, c \mathop > z} } \map \mu d \map \Lambda c + \mathop {\sum \sum}_{\substack {d c \mathop \divides n \\ c \mathop \le z} } \map \mu d \map \Lambda c - \mathop {\sum \sum}_{\substack {d c \mathop \divides n \\ d \mathop \le y, c \mathop \le z} } \map \mu d \map \Lambda c$

It remains to be shown that:

$\ds \mathop {\sum \sum}_{\substack {d c \mathop \divides n \\ c \mathop \le z} } \map \mu d \map \Lambda c = 0$

The summation is expressed as:

$\ds \mathop {\sum \sum}_{\substack {d c \mathop \divides n \\ c \mathop \le z} } \map \mu d \map \Lambda c = \sum_{\substack {c \mathop \le z \\ c \mathop \divides n} } \map \Lambda c \sum_{d \mathop \divides \frac n c} \map \mu d$

Now we have $c \le z < n$, so:

$\dfrac n c > 1$

Therefore, by Sum of Möbius Function over Divisors:

for each $c$ the inner sum vanishes.

This shows that:

$\ds \mathop {\sum \sum}_{\substack {d c \mathop \divides n \\ c \mathop \le z} } \map \mu d \map \Lambda c = 0$

as required.

$\blacksquare$

## Source of Name

This entry was named for Robert Charles Vaughan.