6
$\begingroup$

We know that the probability $P(k)$ of $k$ randomly chosen integers $(k \ge 2)$ from the set of natural number are coprime is

$$ P(k) = \frac{1}{\zeta(k)}. $$

I am looking at a special case of this problem. Let $S_n$ be the set of all natural numbers which do not have a prime factor greater than $n$-th prime (i.e $S_n$ is the set of natural numbers that can be formed using only the first $n$ prime numbers). What is the probability $P(k, S_n)$ that $k$ randomly chosen integers $(k \ge 2)$ from the set $S_n$ are coprime?

I do not know the answer but I think it could be in a parametric form involving $n$ such that in the trivial case when $n\to \infty$, $P(k, S_{\infty}) = P(k) = 1/\zeta(k)$.

Edit: Explained the meaning of "all natural numbers."

$\endgroup$
3
  • $\begingroup$ @ Daniel: Let me explain with an example. Say $n=2$, i.e. we are considering the first two prime numbers. So the set of all natural numbers that can be formed using only the first two primes is the set {2, 3, 4, 6, 8, 9, 12, ...} i.e. every natural numbers of the form $2{a}.3{b}$ where $a≥0$ and $b \ge 0$. $\endgroup$ Jan 30, 2013 at 7:42
  • $\begingroup$ @ Daniel: Thanks for bringing it up. I have tried to make the meaning of 'all natural numbers' clearer in the new edit. $\endgroup$ Jan 30, 2013 at 7:45
  • $\begingroup$ Cool--I've removed my earlier comments. $\endgroup$ Jan 30, 2013 at 8:08

4 Answers 4

9
$\begingroup$

First of all, note that there is no canonical notion of equidistribution on a countable set like the integers.

When asking for the probability that $k$ 'randomly chosen' integers are coprime, it is more-or-less intuitively clear what is meant by 'randomly chosen'. This is basically because the density of integers divisible by a given prime $p$ is (up to 'differences from rounding') the same in any interval $\{1, \dots, n\}$, namely $1/p$.

In your question this is not the case: for example in $S_4 \cap \{1, \dots, 10\}$, 5 of 10 numbers (= 50 percent) are even, while in $S_4 \cap \{1, \dots, 10^6\}$, 1070 of 1273 integers are even (which is about 84 percent) and in $S_4 \cap \{1, \dots, 10^{30}\}$, already 445064 of 462692 are even, which is about 96 percent.

So in order to make your question well-defined you need to be explicit about what you mean by 'randomly chosen'.

$\endgroup$
6
$\begingroup$

A reasonable thing to do would be to look at the number of pairs in $S_k \cap \{1 \cdots N\}$ which are relatively prime. For fixed $k$ this would go to zero and indeed the probability would go to $1$ that a randomly selected element is not relatively prime to anything else in the set (other than $1$ of course).

Looking further at the set $S_4 \cap \{2..10^{30}\}$ we can also say that over $78\%$ of the members are less than $10^{28}$ (So in the bottom $1\%$ sizewise) and that over $73\%$ are not relatively prime to anything else (i.e. divide by $2,3,5$ and $7$). The number of relatively prime pairs is $0.013\%.$

Perhaps looking at integers $m$ with all prime factors less than $m^{2/3}$ or something like that would be interesting but I do not have a feel for what the right question would be.

$\endgroup$
1
  • 2
    $\begingroup$ On the last statement, there are some results. $\psi(x,y)$ denotes the number of positive integers $\leq x$ such that all of their prime factors are $\leq y$. Then for $u\geq 0$, $\psi(x,x^{1/u})=\rho(u)x+O(x/\log x)$. where $\rho(u)$ is called Dickman's function. In case $1\leq u\leq 2$, it is just equal to $1-\log u$. $\endgroup$ Feb 8, 2013 at 1:52
4
$\begingroup$

This question, at least for $k=2$, was studied by Gunderson, Coppersmith and Granville. Surprisingly, the motivation has to do with the first case of Fermat's Last Theorem, but I won't elaborate on that. See specifically Granville's paper "On positive integers $\le x$ with prime factors $\le t \log x$" (Number Theory and Applications (ed R.A. Mollin) (Kluwer, NATO ASI, 1989), pages 403-422, PDF link).

Let me formalize the problem and explain some results.

A number $n$ is $y$-smooth (or $y$-friable) if all its prime factors $p$ are less than or equal to $y$. Let us set $$\Psi(x,y) :=\# \{ n \le x: n \text{ is }y\text{-smooth}\},$$ which appeared in Sungjin Kim's comment. One can consider the quantity $$S_k(x,y) := \# \{ n_1,\ldots,n_k \le x: \gcd(n_1,n_2,\ldots,n_k)=1, \, n_i \text{ is }y\text{-smooth}\}.$$ The ratio $S_k(x,y)/\Psi(x,y)^k$ is exactly the probability that $n$ positive integers chosen uniformly at random from the set of $y$-smooth numbers up to $x$ have no non-trivial common factor. Equivalently, it is the probability that a vector of $y$-smooth numbers and $L^1$-norm $\le x$ is visible from the origin.

If $n \le x$ then $n$ is $x$-smooth, so $S_k(x,x)/\Psi(x,x)^k = S_k(x,x)/\lfloor x \rfloor^k$ is the probability that $n$ positive integers $\le x$ chosen uniformly at random have no common factor, and this converges to $1/\zeta(k)$. You seem to ask about $S_k(x,y)/\Psi(x,y)^k$ when $y$ is fixed.

We can use inclusion-exclusion to express $S_k(x,y)$ as $$\begin{align} S_k(x,y) &= \sum_{d \mid \prod_{p \le y}}\mu(d) \# \{ m_1,\ldots,m_k \le x/d: m_i \text{ is }y\text{-smooth}\}\\ &=\sum_{d\text{ is }y\text{-smooth}} \mu(d)\Psi(x/d,y)^k\end{align}$$ where $d$ stands for the common divisor of $k$ $y$-smooth numbers $n_1,\ldots,n_k$. So we need to understand $$ \sum_{d\text{ is }y\text{-smooth}} \mu(d)\frac{\Psi(x/d,y)^k}{\Psi(x,y)^k}.$$

A special case of a result of Ennola (1969, see discussion here) says that for fixed $y$, $\Psi(x,y) \sim C_y (\log x)^{\pi(y)}(1+O_y(1/\log x))$ where $\pi(y)$ is the number of primes up to $y$ and $C_y$ is an explicit positive constant.

Since $\log x \sim \log (x/d)$ for any fixed $d$, and since $\sum_{d\text{ is }y\text{-smooth}}\mu(d)=0$ for $y \ge 2$, this immediately implies that the above fraction is $O_y(1/\log x)$, so the probability tends to $0$. So most (in a limit sense) $k$-tuples of $y$-smooth integers have a common factor, as observed numerically by Stefan Kohl and Aaron Meyerowitz.


In Granville's paper linked above, he studies the quantity $\Psi(x,x',y)$, which counts pairs $(a,b)$ of coprime $y$-smooth integers with $a \le x$ and $b\le x'$. For $x'=x$, $\Psi(x,x,y)$ is precisely $S_2(x,y)$. In pages 8--9 he quickly derives the following results, and the arguments should extend to $S_k(x,y)$:

  • For $2 \le y \le (\log x)^{1/2}$, we have $\Psi(x,x,y) \sim \binom{2\pi(y)}{\pi(y)} \Psi(x,y)$ as $x \to \infty$. Note that this implies that for fixed $y \ge 2$, the probability $S_2(x,y)/\Psi(x,y)^2$ decays like $1/\Psi(x,y) \asymp (\log x)^{-\pi(y)}$.

  • For $x \ge y \ge 2$ with $y/\log x \to 0$ as $ x \to \infty$, we have $\Psi(x,x,y) = \Psi(x,y)^{1+o(1)}$.

  • For $x \ge y \ge 2$ with $y/\log x \to \infty$ we have $\Psi(x,x,y)=\Psi(x,y)^{2+o(1)}$ as $x \to \infty$.

  • For $x \ge y \ge (\log x)^{2+\varepsilon}$ we have $\Psi(x,x,y) \sim \Psi(x,y)^2/\zeta(2\alpha)$ as $x \to \infty$ where $\alpha$ is the saddle point associated with $x$ and $y$. (I'll include a proof below.)

This leaves out the range $y \asymp \log x$, which is the main focus of Granville's paper. In Theorem 3 he proves an asymptotic formula in this remaining case.


Below I explain how one treats the case where $y$ grows sufficiently fast with $x$ (namely, $y \ge (\log x)^{1+1/(k-1)+\varepsilon}$), but I'll start with a general discussion.

First of all, in this case it is often useful to introduce a truncation parameter $T>0$ into the above inclusion-exclusion formula, and obtain via the union bound the estimate $$ (\star)\, S_k(x, y) = \sum_{d \text{ is }T\text{-smooth}} \mu(d) \Psi(x/d,y)^k + O\left( \sum_{y\ge p > T} \Psi(x/p,y)^k \right).$$ The ratio $\Psi(x/d,y)/\Psi(x,y)$ ('local density') was studied extensively in the literature, namely in

  1. Adolf Hildebrand and Gérald Tenenbaum, "On integers free of large prime factors". Trans. Amer. Math. Soc. 296 (1986), no. 1, 265–290.
  2. Aleksandar Ivić and Gérald Tenenbaum, "Local densities over integers free of large prime factors". Quart. J. Math. Oxford Ser. (2) 37 (1986), no. 148, 401–417.
  3. Régis de la Bretèche and Gérald Tenenbaum, "Propriétés statistiques des entiers friables", Ramanujan J. 9 (2005), no. 1-2, 139–202.
  4. See also Theorem III.5.22 in Tenenbaum's book (3rd edition of English version).

These papers prove either asymptotic results or bounds on $\Psi(x/d,y)/\Psi(x,y)$ in terms of $d^{-\alpha}$ where $\alpha\in (0,1)$ is a certain 'saddle point' defined in terms of $x$ and $y$. Below is a quick lemma one can prove using the paper of Ivić and Tenenbaum, which is the strategy hinted by Granville.


Corollary: Fix $k \ge 2$. Suppose $x \ge y$ and that $y$ grows with $x$ faster than any power of $\log x$ (i.e. $\log y /\log \log x \to \infty$). Then $$\frac{S_k(x,y)}{\Psi(x,y)^k} \sim \zeta(k)^{-1}$$ as $x \to \infty$.

This is immediate from

Lemma: Fix $k \ge 2$. Suppose $x \ge y \ge (\log x)^{1 + \frac{1}{k-1}+\varepsilon}$ for some $\varepsilon>0$. Then $$(\star \star)\, \frac{S_k(x,y)}{\Psi(x,y)^k} \sim \zeta(k\beta(x,y))^{-1}$$ as $x \to \infty$, where $\beta:=1-\frac{\xi(u)}{\log y}$, $u:=\log x / \log y$ and $\xi(u)\sim \log u$ is defined via $e^{\xi(u)}-1=\xi(u)$. In particular, the infinite product in $(\star \star)$ is bounded away from $0$.

Proof: Lemma 2 of the Ivić--Tenenbaum paper says that, for the above $\beta$, $$\Psi(x/d,y) = \Psi(x,y)d^{-\beta}\left(1 + O_{\varepsilon}\left( \frac{\log d}{\log x} + \frac{\log \log y}{\log y}\right)\right).$$ when $1 \le d \le y$ and $y \ge (\log x)^{1+\varepsilon}$. Lemma 3 says that $$\Psi(x/d,y) \ll \Psi(x,y) d^{-\beta + \frac{c}{\log y}}$$ uniformly for $1 \le d \le x$ and $y \ge (\log x)^{1+\varepsilon}$, and $c$ is an absolute positive constant. We use $(\star)$ with $T$ tending to infinity sufficiently slow (we want $d \le y$ and $\log d/\log x \to 0$. Since $d$ is at most $\prod_{p \le T}p=e^{T(1+o(1))}$ we can take, say, $T=\log y/\log \log y$), and these two estimates to obtain $$\begin{align} \frac{S_k(x, y)}{\Psi(x,y)^k} &= \prod_{p \le T} \left(1-p^{-k\beta}\right) + O\left(\sum_{y \ge p > T} p^{-\beta k}\right)\\ &+O_{\varepsilon}\left( \left( \frac{T}{\log x} + \frac{\log \log y}{\log y}\right) \prod_{p \le T} \left(1+p^{-k\beta}\right)\right). \end{align}$$ The assumption $y \ge (\log x)^{1+1/(k-1)+\varepsilon}$ implies $\beta k \ge 1+c\varepsilon$, and the lemma follows. $\blacksquare$

$\endgroup$
1
$\begingroup$

Consider the case for k=2. Now if we say two numbers are relatively prime , we mean they dont share a common prime factor(it is enough to check prime factors). In other words:(m,n)=1, the gcd of m and n =1 => p a prime doesn't divide m and p doesn't divide n. So p^2 doesn't divide mn. But as m and n range through positive integers they represent all the positive integers. So we can simply write mn=l, l belongs to Z+. But this is exactly the probability that a randomly chosen number is square free, which again is zeta(2). We can extend this to k>2.

$\endgroup$
0

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.