2
$\begingroup$

The "probability" that a number $n$ is prime, is roughly $\frac{1}{\ln(n)}$.

How does this probability increase, if it is known, that the prime factors must have the form $km+1$ for some given $m\in \mathbb N$ ?

Motivation : I wonder, how likely the generalized fermat numbers $b^{2^l}+1\ ,\ b\ even\ $ are prime. It is known that the factors of such a number must have the form $2^{l+1}k+1$. This should increase the probability of being prime, but I have no idea of the magnitude of the increase.

$\endgroup$
  • $\begingroup$ i've checked numbers smaller than $N = 1000000$ and the "probability" of being prime gets multiplied by $6.2$ when you restrict to numbers whose prime factors are congruent to $1 $mod $3$. This factor tends to increase slowly as $N$ gets larger. $\endgroup$ – mercio Sep 30 '15 at 12:44
  • 1
    $\begingroup$ Why did you ask this question without at least linking to this one? I would have thought that my answer there goes a long way towards answering this question, and at least is relevant enough that it should be linked to avoid unnecessary duplication of efforts. $\endgroup$ – joriki Sep 30 '15 at 13:56
3
$\begingroup$

Let $S_m$ be the set of integers whose prime factors are all congruent to $1$ mod $m$. We know from the Prime Number Theorem for Arithmetic Progressions, as described in Julián's answer, that

$$ \# \{ p \le x : p \in S_m, p \text{ prime} \} = c_m \frac{x}{\log x} + O_m\big(\frac{x}{\log^2 x}\big),$$

where $c_m = 1/\phi(m)$. To answer the question, we only need an asymptotic for the counting function of $S_m$. Since $S_m$ excludes a fraction of $(1-c_m)$ of all primes, one expects heuristically that $$ \# \{ n \le x : n \in S_m \} \asymp \frac{x}{(\log x)^{1-c_m}},$$ and in fact it can be obtained rigorously by a theorem of Odoni that the following precise asymptotic holds: $$ \# \{ n \le x : n \in S_m \} = D_m x(\log x)^{c_m-1} + O_m(x(\log x)^{c_m-2+\epsilon}),$$ where $D_m > 0$ is given by a certain convergent Euler product. Specifically, if $\chi_m(p)$ is the indicator function of $\{ p : p \equiv 1 \pmod m\}$, then $$D_m = \frac{1}{\Gamma(c_m)} \prod_{p} \big(1 - \frac1p\big)^{c_m-\chi_m(p)}.$$ The "probability" you're seeking is just the ratio of primes to all numbers in $S_m$ up to $x$, namely $$\frac{c_m}{D_m (\log x)^{c_m}}.$$

I think in this case, the $\epsilon$ in the error term can be removed by applying the Selberg-Delange method, but I haven't checked the details (see, for instance, this paper).

However, as pointed out in Aravind's answer, even though this is provable, it still only amounts to a heuristic when you try to apply it to much thinner sets such as $\{n^2+1\}$ or $\{2^{2^n}+1\}$ that are not defined purely in terms of the prime composition.

$\endgroup$
1
$\begingroup$

I believe this question is impossible to answer in general and very hard for even simple instances.

Firstly, we are looking at a set $S$ of numbers such that all prime factors of numbers in $S$ are of the form $km+1$. The question is about the fraction of primes in $S$ among the first $n$ numbers in $S$.

It is not clear why this function should be greater than $\frac{1}{\log n}$ or indeed how we can say anything about it for arbitrary $S$. If we choose $S$ as a subset of the composites, then the probability is zero, while we could make it 1 by choosing $S$ to be a subset of the primes.

Also consider the example $S=\{n^2+1: n \in \mathbb{N}, \text{ n even}\}$. We know that all prime factors must be of the form $4k+1$, but clearly this is not sufficient information; we don't even know if the probability is positive!

The same is true for any set $S$ for which whether it has infinitely many primes is itself open, such as the set of Fermat numbers.

$\endgroup$
  • $\begingroup$ Not sure the example is particularly relevant. We don't know the number of primes in $\{n^2+1\}$, but we certainly know the number of primes in $\{n : p \mid n \implies p \equiv 1 \pmod 4\}$, and we also know the counting function of the latter set. $\endgroup$ – Erick Wong Sep 30 '15 at 14:00
1
$\begingroup$

The probability that a number smaller than $n$ of the form $k\,m+1$ is prime is of the order of $$ \frac{m}{\phi(m)}\,\frac{1}{\log N}\ . $$ This is an upper bound on the probability you are looking for. To get a better estimate you would need to know the number of integers less than $n$ all whose factors are $\equiv1\mod m$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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