1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ How are the $x_1,\dots,x_n$ chosen? If they are all multiples of two, then the gcd condition never happens. $\endgroup$ Jan 20, 2013 at 18:28
  • $\begingroup$ I thought it was clear that they are chosen at random. Just fixed the possible ambiguity. $\endgroup$
    – Alex G
    Jan 20, 2013 at 18:35
  • $\begingroup$ 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 $\endgroup$ Jan 20, 2013 at 20:12

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 20, 2013 at 22:13
  • $\begingroup$ Nice. Even though as you might have guessed, I was hoping for an answer involving the zeta function. $\endgroup$
    – Alex G
    Jan 21, 2013 at 2:11
  • $\begingroup$ 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. $\endgroup$ Jan 22, 2013 at 1:28
  • 1
    $\begingroup$ 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 $\endgroup$ Jan 25, 2013 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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