Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
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
add comment

2 Answers 2

up vote 12 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.