Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

A simple argument shows that if we choose $n$ positive integers at random, the probability of their greatest common divisor being 1 is $1/ \zeta (n)$ (in the sense that if we choose the numbers among $\lbrace 1, 2, 3, \dots , N \rbrace$ uniformly and independently, the above probability tends to some number $p(n)$ as $N \rightarrow \infty$).

In the above sense, what is the probability $p(n,k)$ that among n integers $x_1, x_2, \dots, x_n$ chosen at random we have $\gcd (x_{i_1}, x_{i_2}, \dots, x_{i_k})=1$ for all possible combinations of the $x_{i_j}$ (with $s \neq t$ if for $u \neq v$, $x_{i_u}=x_s$ and $x_{i_v}=x_t$) ?

share|improve this question
    
How are the $x_1,\dots,x_n$ chosen? If they are all multiples of two, then the gcd condition never happens. –  Eric Naslund Jan 20 '13 at 18:28
    
I thought it was clear that they are chosen at random. Just fixed the possible ambiguity. –  Alex G Jan 20 '13 at 18:35
    
You will need fewer than k of them even for that to be possible (which I think is Eric Naslund's point), which will likely be the most prominent condition determining the probability. Even if you study the relaxed condition that no k of the n numbers have a small prime factor in common, I think you will get good bounds on the probability you seek. Gerhard "Ask Me About System Design" Paseman, 2013.01.20 –  Gerhard Paseman Jan 20 '13 at 20:12

1 Answer 1

up vote 5 down vote accepted

For any prime $q$, define $$ \ell(q,n,k) = q^{-n} \sum_{j=0}^{n-k} \binom nj (q-1)^j, $$ so that $\ell(q,n,k)$ is the probability, if a biased coin that comes up heads only $1/q$ of the time is tossed $n$ times, that at least $k$ heads are obtained. Equivalently, $\ell(q,n,k)$ is the probability, if $n$ numbers are chosen uniformly and independently from the set $\{0,1,\dots,q-1\}$, that at least $k$ of the numbers equal $0$.

Then the same argument giving the $1/\zeta(n)$ result shows that the probability that the greatest common divisor of every $k$-subset of $n$ "randomly chosen" integers is $1$ equals $$ \prod_q \big( 1 - \ell(q,n,k) \big), $$ where the product is over all primes $q$. This product is convergent as long as $k\ge2$; it diverges to $0$ if $k=1$ (appropriately).

For example, if three integers are chosen at random, the probability that they are pairwise coprime is $$ \prod_q \big( 1 - \ell(q,3,2) \big) = \prod_q \bigg( 1-\frac1q \bigg)^2 \bigg( 1+\frac2q \bigg) \approx 0.286747. $$ (A million trials with random integers between $1$ and $10^{60}$ yielded $286912$ pairwise coprime triples, so this limiting probability seems accurate.) I don't believe this product has a closed form in terms of the zeta function.

share|improve this answer
1  
This .286747... is also the probability that two positive integers are "strongly carefree," that is, coprime and both squarefree, see Finch, Mathematical Constants, p. 110. Next page, Finch notes the probability $k$ integers are pairwise coprime is $\prod(1-p^{-1})^{k-1}(1+(k-1)p^{-1})$ for $k=2,3$, unproved for $k\gt3$. Some of Finch's references are to unpublished work of Moree. A published reference is Schroeder's book, Number Theory in Science and Communication, pp 25, 48-51, and 54. –  Gerry Myerson Jan 20 '13 at 22:13
    
Nice. Even though as you might have guessed, I was hoping for an answer involving the zeta function. –  Alex G Jan 21 '13 at 2:11
    
The formula in the answer certainly reduces, when $k=2$ (pairwise coprime), to $\prod_q (1-q^{-1})^{n-1}(1+(n-1)q^{-1})$, validating Finch's statement. –  Greg Martin Jan 22 '13 at 1:28
    
Indeed, Toth seems to have proved this statement (about $n$ randomly chosen integers being pairwise coprime) in a 2002 Fibonacci Quarterly paper. ams.org/mathscinet-getitem?mr=1885265 –  Greg Martin Jan 25 '13 at 1:19

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.