9
$\begingroup$

If $N$ is a random $y$-bit integer, what is the probability that it has

  • at least one $x$-bit prime factor?
  • at least two $x$-bit prime factors?

I am assuming $x$ is large and that $y > x$.

If $N$ is a $y$-bit integer then $2^{y-1} \leq N < 2^y$. Similarly, we say a prime factor $p$ has $x$ bits iff $2^{x-1} \leq p < 2^x$.

For the first question, I have the following attempt.

For a random integer $N$ and prime $p$, the probability that $p$ divides $N$ is approximately $\frac{1}{p}$. Hence the probability that $N$ is not divisible by any $x$-bit prime is approximately:

$$\prod_{2^{x-1} \leq p < 2^x} \left(1-\frac{1}{p}\right).$$

Using Mertens' third theorem, we know that

$$\prod_{p \leq n} \left(1-\frac{1}{p}\right) \approx \frac{e^{-\gamma}}{\ln{n}}$$

where $\gamma$ is the Euler-Mascheroni constant. Therefore,

$$\prod_{2^{x-1} \leq p < 2^x} \left(1-\frac{1}{p}\right) \approx \frac{\ln(2^{x-1})}{\ln(2^x)} = \frac{x-1}{x}.$$

Therefore the probability that there is an $x$-bit prime factor is approximately $1 - \frac{x-1}{x} = \frac{1}{x}$.

Is this result correct asymptotically?

The second part of the question is:

what is the approximate probability of having at least two $x$-bit prime factors?

Numerical experiments suggest it might be close to $\frac{1}{2x^2}$.

This is related but is not about asymptotics

$\endgroup$
3
  • $\begingroup$ By 'x bit prime factor', do you mean 2 <= p < 2^x or 2^(x-1) <= p < 2^x? $\endgroup$ Commented Dec 24, 2024 at 14:39
  • $\begingroup$ @SimonGoater I added a clarifying sentence. $\endgroup$ Commented Dec 24, 2024 at 16:26
  • 3
    $\begingroup$ Intuitively you'd expect the number of $x$-bit prime factors to have Poisson distribution. If the expectation $\lambda$ of such a distribution is close to $0$ (so that $e^{-\lambda} \approx 1$), then $P(X \geq 1) \approx P(X=1)\approx\lambda$ and $P(X \geq 2) \approx P(X = 2) \approx \frac{1}{2} \lambda^2$. This matches the numerical experiments you performed for question 2. $\endgroup$ Commented Dec 29, 2024 at 0:05

1 Answer 1

4
+50
$\begingroup$

Short answer: Yes to your questions.

Your reasoning is intuitively correct. As pointed out, the event that two given primes divides $N$ are roughly independent, so the number of prime factors roughly follows a Poisson distribution.

The trick is to go from "approximately" to some precise estimate. We can make it rigorous by showing that as $y\to\infty$, the distribution of the number of divisors in $[2^{x-1}, 2^x-1]$ of $N$ uniform in $[2^{y-1}, 2^y-1]$ converges to an explicit distribution (that of a sum of independent random variables, hence justifying your initial, intuitive approximation). This sum of independent variables can then be controlled as $x\to\infty$, giving your asymptotics in $\frac 1 x$. Note the double limit, which makes it delicate to quantify the quality of the approximation.

Step 1: number of integers in $[A,B-1]$ without divisors in $Q \subset P$.

Let $P$ be the set of prime numbers, and $Q\subset P$. For every integer $m$, there are exactly $\left\lfloor \frac{n}{m}\right\rfloor$ integers in $\{1, \dots, n\}$ that are divisible by $m$. By the inclusion-exclusion principle, the number of integers in $\{1, \dots, n\}$ that are divisible by no $q\in Q$ is $$ E_Q([1,n]) := \sum_{J\subset Q} (-1)^{|J|} \left\lfloor \frac{n}{\prod_{q\in J} q} \right\rfloor , $$ and for $A < B$, the set of integers in $[A, B-1]$ that are divisible by no $q\in Q$ is $$ E_Q([A, B-1]) := \sum_{J\subset Q} (-1)^{|J|} \left( \left\lfloor \frac{B-1}{\prod_{q\in J} q} \right\rfloor - \left\lfloor \frac{A-1}{\prod_{q\in J} q} \right\rfloor \right) . $$ Observe that since $|x-\lfloor x\rfloor|\leq 1$, $$ \left| E_Q([A,B-1]) - (B-A) \sum_{J\subset Q} \frac{(-1)^{|J|}}{\prod_{q\in J} q} \right| \leq 2 \sum_{J\subset Q} 1 = 2^{1+|Q|} . $$ We can simplify this further by noticing that $$ \sum_{J\subset Q} \frac{(-1)^{|J|}}{\prod_{q\in J} q} = \prod_{q\in Q} \left(1 - \frac 1 q \right) . $$

Step 2: the moment generating function.

Let $x < y$ be integers, and for every $n$, let $D(n)$ be the number of prime divisors of $n$ in $[2^{x-1}, 2^x-1]$. Let $N$ be a uniformly distributed integer in $[2^{y-1}, 2^y-1]$. We have $$ \mathbb E[z^{D(N)}] = 2^{1-y} \sum_{n=2^{y-1}}^{2^y-1} z^{D(n)} . $$ The latter can be rewritten as follows. Let $Q = [2^{x-1}, 2^x-1] \cap P$. Then by partitioning the $n$ depending on the set $I$ of $p\in Q$ that divide it, since $n / \prod_{p \in I} p$ is divided by no $p \in Q \setminus I$ we get $$ \mathbb E[z^{D(N)}] = 2^{1-y} \sum_{I\subset Q} z^{|I|} E_{Q\setminus I} \left( \left[ \left\lfloor\frac{2^{y-1}}{\prod_{p\in I} p}\right\rfloor , \left\lfloor\frac{2^{y}-1}{\prod_{p\in I} p}\right\rfloor \right] \right) . $$ Using the approximation from step 1,

$$ (*) \quad \left| \mathbb E[z^{D(N)}] - \sum_{I\subset Q} \frac{z^{|I|}}{\prod_{p\in I} p} \prod_{q \in Q\setminus I} \left(1 - \frac 1 q \right) \right| \leq 2^{1-y} \sum_{I\subset Q} |z|^{|I|} 2^{1+|Q|-|I|} = 2^{2-y} (2 + |z|)^{|Q|} . $$ We can identify $\sum_{I\subset Q} \frac{z^{|I|}}{\prod_{p\in I} p} \prod_{q \in Q\setminus I} \left(1 - \frac 1 q \right) $ with $\mathbb E[z^{\sum_{p\in Q} B_p}]$, where $(B_p)_{p\in P}$ are independent random variables with $P(B_p = 1) = 1/p$ and $P(B_p = 0) = 1-1/p$. Since the right-hand side of $(*)$ converges to $0$ as $y\to\infty$, we deduce the following Lemma.

Lemma: Recall that $N$ is a uniform integer in $[2^{y-1}, 2^y-1]$, that $Q$ is the set of prime numbers in $[2^{x-1}, 2^x-1]$, and that $D(N)$ is the number of distinct prime divisors of $N$ in $Q$. As $y\to\infty$, $D(N)$ converges in distribution towards $\sum_{p\in Q} B_p$, where $(B_p)_{p\in P}$ are independent random variables with $P(B_p = 1) = 1/p$ and $P(B_p = 0) = 1-1/p$. In particular, for every fixed $k$, $P(D(N) \geq k) \to P(\sum_{p\in Q} B_p \geq k)$ as $y\to\infty$.

Step 3: Asymptotic as $x\to\infty$.

Immediately $$ P(\sum_{p\in Q} B_p = 0) = \prod_{p\in Q} \left(1 - \frac 1 p\right) . $$ There is a small tricky thing here: Merten's theorem, in its weaker form, only gives you $\sum_{p\in Q} \frac 1 p = O\left(\frac 1 x\right)$; you need one of the stronger versions to get that $\sum_{p\in Q} \frac 1 p = \frac 1 x + o\left(\frac 1 x\right)$. Still, you can get it, and it gives you the desired asymptotic $ x P(\sum_{p\in Q} B_p \geq 1) \to 1$ at $x \to\infty$.

Since $$ P(\sum_{p\in Q} B_p = 2) = \prod_{p\in Q} \left(1 - \frac 1 p\right) \sum_{p < p \in Q} \frac{1}{(p-1)(p'-1)} \approx \frac 1 2 \left(\sum_{p\in Q} \frac 1 p\right)^2 \approx \frac 1 {2x^2}$$ your second asymptotic follows once you are convinced that $P(\sum_{p\in Q} B_p \geq 3)$ is much smaller than $P(\sum_{p\in Q} B_p = 2)$. This, and the approximation in the last line, can be made rigorous.

$\endgroup$
4
  • $\begingroup$ The result for the probability of having at least two prime factors is great. But I wonder if this must be a looser approximation for finite $x$? $\endgroup$ Commented Jan 3 at 10:19
  • $\begingroup$ @Simd I am not sure what you mean, could you clarify? $\endgroup$ Commented Jan 5 at 16:49
  • $\begingroup$ The $1/x$ approximation will have some error bound for finite $x$. Maybe it can be derived from mathoverflow.net/a/357656/45564 but I don't know. I was asking if the $1/2x^2$ result might have a worse (less tight) error bound. $\endgroup$ Commented Jan 5 at 17:13
  • 1
    $\begingroup$ @Simd Your link allows to prove that the error in the asymptotic in $1/x$ will be $O(x^{-3})$. There may be results out there that would give a sharper (asymptotic) bound. As for the second, using the same link, the asymptotic is $\frac{1}{2x^2} - \frac{1}{2x^3} + O(x^{-5}) = \frac{1}{2x^2} + O(x^{-3})$. $\endgroup$ Commented Jan 7 at 21:30

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.