# Probability that a vector in $\mathbb{Z}^n$ is primitive

A vector $v \in \mathbb{Z}^n$ is primitive if there does not exist some vector $v' \in \mathbb{Z}^n$ and some $k \in \mathbb{Z}$ such that $v = k v'$ and $k \geq 2$.

For a paper I'm writing right now, I'd like to know that a "random" vector in $\mathbb{Z}^n$ is primitive. Let me make this precise.

Let $\|\cdot\|_{1}$ be the $L^{1}$ norm on $\mathbb{Z}^n$, so $\|v\|_1 = \sum_{i=1}^n |v_i|$, where the $v_i$ are the components of $v$. Define $\mathcal{V}_k$ to be the number of vectors $v$ in $\mathbb{Z}^n$ such that $\|v\|_1 \leq k$. Define $\mathcal{P}_k$ to be the number of primitive vectors $v$ in $\mathbb{Z}^n$ such that $\|v\|_1 \leq k$.

I then want $$\lim_{k \rightarrow \infty} \frac{\mathcal{P}_k}{\mathcal{V}_k} = 1.$$ Assuming this is true, is there any nice estimate as to how fast it approaches $1$?

-
Even if you didn't know the exact answer to this question, the set of all vectors whose elements are even is a subset of non-primitive vectors of density 1/2^k, so the answer is manifestly less than 1. By inclusion-exclusion, it's at most (1 - 1/2^k)(1 - 1/3^k)(1 - 1/5^k)... for any finite collection of primes and at this point you might conjecture the relation with the zeta function. –  Qiaochu Yuan Nov 20 '10 at 12:29
@Qiaochu: Yes, that's the intuitive way to think about this. The probability of the vector not being a multiple of p is $1-1/p^n$. Inclusion exclusion or independence (from CRT) gives $\prod_p(1-1/p^n)$ for the probability of not being a multiple of any prime from a finite set. This quickly gives $1/\zeta(n)$ as an upper bound, but doesn't immediately give the lower bound or a rate of convergence. Expanding the product gives the expression in terms of the Mobius function in my answer from which, with a bit of work, you get the rate of convergence. –  George Lowther Nov 20 '10 at 13:04
@George: right. Using the argument given, for example, at qchu.wordpress.com/2010/11/09/… , you can show that if the natural density exists it must be 1/zeta(n), but you certainly need to do extra work to actually get that the density exists. –  Qiaochu Yuan Nov 20 '10 at 13:30

In the case where $n = 2$, you're asking for the "probability" that two integers are relatively prime; this is well-known to be $6/\pi^2$, not 1. In the general-$n$ case, the probability that $n$ integers are relatively prime is $1/\zeta(n)$.

Reference: http://en.wikipedia.org/wiki/Coprime

-
Thanks! Do you have a reference for this? –  T_P Nov 19 '10 at 20:20
@T_P : I have added a reference –  anonymous Nov 19 '10 at 20:23
Thanks, Chandru. I couldn't add a reference because I was teaching! –  Michael Lugo Nov 19 '10 at 21:07
No, problem sir! –  anonymous Nov 19 '10 at 21:29

Further to Michael's answer, not only does $\mathcal{P}_k/\mathcal{V}_k\to1/\zeta(n)$, but we can calculate a bound for the rate of convergence. I'll also give an argument which is a little different from the one given in his Wikipedia reference.

Noting that the set $\lbrace v\in\mathbb{R}^n\colon\Vert v\Vert_1\le k\rbrace$ has volume $ck^n$ (for a constant c depending only on the dimension n) and surface area proportional to $k^{n-1}$ gives $$\mathcal{V}_{k}-1=ck^n + O(k^{n-1}).\qquad\qquad{\rm(1)}$$ The '-1' on the left hand side is not relevant for large k as it can be absorbed into the O(kn−1) error term, and is just there so that (1) is also valid for small k < 1. Noting that every nonzero $v\in\mathbb{Z}^n$ decomposes uniquely as $v=mv^\prime$ for integer $m\ge1$ and primitive $v^\prime\in\mathbb{Z}^n$ leads to the following relation between $\mathcal{P}_k$ and $\mathcal{V}_k$, $$\mathcal{V}_k-1=\sum_{m=1}^\infty\mathcal{P}_{\frac{k}{m}}.$$ This can be inverted via the Möbius function μ, $$\mathcal{P}_k=\sum_{m=1}^\infty\mu(m)(\mathcal{V}_{\frac{k}{m}}-1).$$ In dimension $n > 2$, substituting (1) into this expression gives $$\mathcal{P}_k=\sum_{m=1}^\infty \mu(m)c k^n m^{-n} + O(k^{n-1}).\qquad\qquad{(2)}$$ The $O(k^{n-1})$ comes from the sum $\sum_m (k/m)^{n-1}$ from the remainder term of (1) which, for $n > 2$, gives $k^{n-1}$ multiplied by a convergent sum. Dividing through by $\mathcal{V}_k$, $$\mathcal{P}_k/\mathcal{V}_k=\sum_{m=1}^\infty\mu(m)m^{-n}+O(1/k)=1/\zeta(n)+O(1/k).$$ Edit: The case for $n=2$ is actually a little bit different, and we do not obtain such a good convergence rate. As the sum $\sum_m(k/m)^{n-1}$ does not converge, the error term in (2) does not apply. Instead, we can use $O(1_{\lbrace k\ge1\rbrace}k+1_{\lbrace k < 1\rbrace}k^2)$ for the error term in (1). This leads to an error of order $k\sum_{m\le k}m^{-1}+k^2\sum_{m > k}m^{-2}\sim k\log k$ in (2), giving $$\mathcal{P}_k/\mathcal{V}_k=1/\zeta(2)+O(\log k/k).$$ You can also look at the paper On the probability that k positive integers are relatively prime.

-