Using Möbius inversion to count primtive vectors in $\mathbb{Z}^n$

41 Views Asked by At

Let $\mathbb{Z}^n_\text{prim}$ be the set of vectors $\mathbf{x} \in \mathbb{Z}^n$ such that $\gcd(x_1, ..., x_n) = 1$. Let $\|\cdot\|$ be the $L^2$-norm. Let $N^*(T) = \# \{ \mathbf{x} \in \mathbb{Z}^n_\text{prim}: \| \mathbf{x}\| \leq T \}$ and $N(T) = \# \{ \mathbf{x} \in \mathbb{Z}^n: \| \mathbf{x}\| \leq T \}$. Can somebody please explain me how I get the following from Möbius inversion: $$ N^*(T) = \sum_{1 \leq \ell \leq T} \mu(\ell) \# \{ \mathbf{x} \in \mathbb{Z}^n: \mathbf{x} \not = \mathbf{0}, \frac{1}{\ell}\mathbf{x} \in \mathbb{Z}^n, \|\mathbf{x}\| \leq T \} $$ It seems more like an application of the inclusion-exclusion principle to me, but the text says by Möbius inversion, and I would appreciate some explanation. Thank you very much.

1

There are 1 best solutions below

0
On BEST ANSWER

By definition $\sum_{d|n}\mu(d)=0$ if $n > 1$ and $=1$ if $n=1$ thus $$\sum_{\|x\|\le T, \gcd(x)=1} 1 = \sum_{\|x\|\le T} \sum_{d| \gcd(x)} \mu(d)= \sum_{\|x\|\le T} \sum_{d| x} \mu(d)=\sum_d \mu(d)\sum_{\|x\|\le T,d|x}1$$

(removing the vector $x=0$ from the sums to avoid the case $\gcd(x)=0$ )