# 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$:

$\displaystyle \Lambda \left({n}\right) = \sum_{\substack {d \mathop \backslash n \\ d \mathop \le y}} \mu \left({d}\right) \ln \left({\frac n d}\right) - \mathop {\sum \sum}_{\substack {d c \mathop \backslash n \\ d \mathop \le y, \, c \mathop \le z}} \mu \left({d}\right) \Lambda \left({c}\right) + \mathop {\sum \sum}_{\substack{d c \mathop \backslash n \\ d \mathop > y, \, c \mathop > z}} \mu \left({d}\right) \Lambda \left({c}\right)$

where $\backslash$ denotes divisibility.

## Proof

$\displaystyle \ln n = \sum_{d \mathop \backslash n} \Lambda \left({d}\right)$

Hence:

 $\displaystyle \Lambda \left({n}\right)$ $=$ $\displaystyle \sum_{d \mathop \backslash n} \mu \left({d}\right) \ln \left({\frac n d}\right)$ $\quad$ Möbius Inversion Formula $\quad$ $\displaystyle$ $=$ $\displaystyle \sum_{\substack {d \mathop \backslash n \\ d \mathop \le y} } \mu \left({d}\right) \ln \left({\frac n d}\right) + \sum_{\substack {d \mathop \backslash n \\ d \mathop > y} } \mu \left({d}\right) \ln \left({\frac n d}\right)$ $\quad$ $\quad$

Taking the second summation in that last line:

 $\displaystyle \sum_{\substack {d \mathop \backslash n \\ d \mathop > y} } \mu \left({d}\right) \ln \left({\frac n d}\right)$ $=$ $\displaystyle \sum_{\substack {d \mathop \backslash n \\ d \mathop > y} } \mu \left({d}\right) \sum_{c \mathop \backslash n / d} \Lambda \left({c}\right)$ $\quad$ $\quad$ $\displaystyle$ $=$ $\displaystyle \mathop {\sum \sum}_{\substack {d c \mathop \backslash n \\ d \mathop > y} } \mu \left({d}\right) \Lambda \left({c}\right)$ $\quad$ $\quad$ $\displaystyle$ $=$ $\displaystyle \mathop {\sum \sum}_{\substack {d c \mathop \backslash n \\ d \mathop > y, \, c \mathop > z} } \mu \left({d}\right) \Lambda \left({c}\right) + \mathop {\sum \sum}_{\substack {d c \mathop \backslash n \\ d \mathop > y, \, c \mathop \le z} } \mu \left({d}\right) \Lambda \left({c}\right)$ $\quad$ $\quad$

Again, taking the second summation in that last line:

$\displaystyle \mathop {\sum \sum}_{\substack {d c \mathop \backslash n \\ d \mathop > y, \, c \mathop \le z} } \mu \left({d}\right) \Lambda \left({c}\right) = \mathop {\sum \sum}_{\substack {d c \mathop \backslash n \\ c \mathop \le z} } \mu \left({d}\right) \Lambda \left({c}\right) - \mathop {\sum \sum}_{\substack {d c \mathop \backslash n \\ d \mathop \le y, \, c \mathop \le z} } \mu \left({d}\right) \Lambda \left({c}\right)$

Putting this together:

$\displaystyle \Lambda \left({n}\right) = \sum_{\substack {d \mathop \backslash n \\ d \mathop \le y} } \mu \left({d}\right) \ln \left({\frac n d}\right) + \mathop {\sum \sum}_{\substack {d c \mathop \backslash n \\ d \mathop > y, c \mathop > z} } \mu \left({d}\right) \Lambda \left({c}\right) + \mathop {\sum \sum}_{\substack {d c \mathop \backslash n \\ c \mathop \le z} } \mu \left({d}\right) \Lambda \left({c}\right) - \mathop {\sum \sum}_{\substack {d c \mathop \backslash n \\ d \mathop \le y, c \mathop \le z} } \mu \left({d}\right) \Lambda \left({c}\right)$

It remains to be shown that:

$\displaystyle \mathop {\sum \sum}_{\substack {d c \mathop \backslash n \\ c \mathop \le z} } \mu \left({d}\right) \Lambda \left({c}\right) = 0$

The summation is expressed as:

$\displaystyle \mathop {\sum \sum}_{\substack {d c \mathop \backslash n \\ c \mathop \le z} } \mu \left({d}\right) \Lambda \left({c}\right) = \sum_{\substack {c \mathop \le z \\ c \mathop \backslash n} } \Lambda \left({c}\right) \sum_{d \mathop \backslash \frac n c} \mu \left({d}\right)$

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

$\dfrac n c > 1$

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

for each $c$ the inner sum vanishes.

This shows that :

$\displaystyle \mathop {\sum \sum}_{\substack {d c \mathop \backslash n \\ c \mathop \le z} } \mu \left({d}\right) \Lambda \left({c}\right) = 0$

as required.

$\blacksquare$

## Source of Name

This entry was named for Robert Charles Vaughan.