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

Hi there, the motivation for this question is to better understand the heuristics of Mersenne primes, and I was motivated by the recent questions (Mersenne quasi-primes) and (Primes in generalized Fibonacci sequences). I'd appreciate being told if this approach is misguided or pointless, and I appreciate any effort spent in reading it.

In the paper

S. Wagstaff, "Divisors of Mersenne numbers", Math. Comp., 40(1983), no.161, 385--397,

Wagstaff counts Mersenne primes by already using the knowledge that $2^n-1$ has no chance to be prime when $n$ is composite, and thus he only needs to consider prime factors of $2^n-1$ when $n$ is prime when estimating heuristics.

On the other hand, I wonder if the following is possible. Suppose I pretend that I do not know that $n$ must be prime in order for $2^n-1$ to be prime. Then I would naively conjecture that the number of Mersenne primes less than $x$ is

$$ (\mbox{some factor})\sum_{n \leq ( \log x / \log 2)}\frac{1}{n \log 2}. $$

Denis Chaperon de Lauzières correctly pointed out an earlier mistake I made in the post "Infinitely many primes of the form $2^n+c$ as $n$ varies?" regarding the possible factor in front of the sum, and I will try to modify that later. Now, if you think about it, this approach has some similarity to what is done in the Hardy-Littlewood conjecture F/Bateman-Horn conjecture. For example, we already know that when $n \equiv 2 \bmod 5$, $n^2+1$ will not be prime except when $n=2$, but instead of excluding those $n$, we still count over all $n$ and push that local information into the Hardy-Littlewood/Bateman-Horn constant.

Therefore, the motivation here is simply this: to formulate a conjecture for asymptotics of Mersenne primes which will agree with the Lenstra-Pomerance-Wagstaff heuristics, but in which we deliberately count over all $n$ (instead of excluding composite $n$) and push all the other information into the product before the sum. To phrase it another way - there must be some factor which, if one tries to count Mersenne primes in this way (not excluding composite $n$), can still be multiplied in front of what is obtained so that the resulting estimate must agree with the Lenstra-Pomerance-Wagstaff heuristics - what is that factor?

Now, as mentioned earlier, Denis Chaperon de Lauzières correctly pointed out that an earlier conjecture I made for the constant was wrong. I did not account for the fact that often, for odd primes $p_1 \not= p_2$, the GCD of the orders of $2$ in $(\mathbb{Z}/p_1\mathbb{Z})^{*}$ and $(\mathbb{Z}/p_2\mathbb{Z})^{*}$ is greater than $1$. But this information can be captured as follows. Let

$$ N(x) = \prod_{2< p\leq x}p. $$

Let $M(x)$ be the order of $2$ in $(\mathbb{Z}/N(x)\mathbb{Z})^{*}$. We have $M(x) \leq \lambda(N(x))$ where $\lambda$ is the Carmichael function. Now let $R(x)$ be the number of solutions to $(2^n-1,N(x))>1$, $n\in \mathbb{Z}/M(x)\mathbb{Z}$. Then consider

$$ C = \lim_{x \rightarrow \infty}\left(\frac{M(x)-R(x)}{M(x)}\right)\left(\frac{N(x)}{\varphi(N(x))}\right). $$

The first question is, does the limit exist? Now, assuming it does, we say the following:

(a) The constant does not account for the prime $2$, but that can be handled. (b) Part of this constant is not an Euler product, due to the $M(x)$. (c) This constant gives some clue that it can "absorb" some of the inaccuracy from deliberate consideration of $2^n-1$, $n$ composite, when we know better than to do so. For example, we know that we should not bother with $2^{4n}-1$, since $5$ divides those, but this is at least partially adjusted for by the $R(x)$.

Basically, $C$ is an attempt to adjust for local probabilities like in the Hardy-Littlewood/Bateman-Horn constants, also accounting for issues with the GCD of the orders of $2$ in the various $(\mathbb{Z}/p\mathbb{Z})^{*}$. More refined treatment is still probably necessary.

I'd appreciate any comments. Thank you very much.

EDIT:

Thanks very much to all who edited and viewed this. I will make this community wiki. There are two possible generalizations of this, both of which might well be subsumed under an even more general generalization.

Generalization (1): Primes in Lucas sequences $U_n(P,Q)$. (See Wikipedia)

This is completely inherent in the post (Primes in generalized Fibonacci sequences).

Since the Mersenne numbers are $U_n(3,2)$, we set $C = C_{3,2}$, $N(x) = N(3,2;x)$, $M(x) = M(3,2;x)$, and $R(x) = R(3,2;x)$.

For a general Lucas sequence $U_n(P,Q)$, let $\mathbb{P}(P,Q)$ be the set of primes $p$ which never divide any member of $U_n(P,Q)$. For example, $\mathbb{P}(3,2) = \{2\}$. Let

$$N(P,Q;x) = \prod_{\substack{p \leq x\\p \not\in \mathbb{P}(P,Q)}}p.$$

Let $M(P,Q;x)$ be the period of $U_n(P,Q) \bmod N(P,Q;x)$. So $M(P,Q;x)$ is the LCM of the periods of $U_n(P,Q)$ modulo each of the primes dividing $N(P,Q;x)$.

Let $R(P,Q;x)$ be the number of solutions to $(U_n(P,Q), N(P,Q;x))>1$, $n \in \mathbb{Z}/M(P,Q;x)\mathbb{Z}$. Then let

$$ C_{P,Q} = \lim_{x \rightarrow \infty}\left(\frac{M(P,Q;x)-R(P,Q;x)}{M(P,Q;x)}\right)\left(\frac{N(P,Q;x)}{\varphi(N(P,Q;x))}\right). $$

Now use the Binet-type formula (See Wikipedia):

$$ U_n(P,Q) = \frac{a^n-b^n}{a-b}. $$

Let $c = c_{P,Q} = \max(|a|,|b|)$.

Finally, we naively conjecture (subject to likely future refinement) that the number of primes assumed by $|U_n(P,Q)|$, less than $x$, is asymptotic to

$$ (\mbox{factor from future refinement})\prod_{p \in \mathbb{P}(P,Q)}\frac{p}{p-1}C_{P,Q}\sum_{n \leq (\log x/\log c)}\frac{1}{n\log c}. $$

Generalization (2): Primes of the form $A^n+B$, $A,B\in \mathbb{Z}$, $A>1$.

Please also see (Infinitely many primes of the form $2^n+c$ as $n$ varies).

Let $\mathcal{P}(A,B)$ be the set of primes $p$ which never divide $A^n+B$. Let

$$\mathcal{N}(A,B;x) = \prod_{\substack{p \leq x\\p \not\in \mathcal{P}(A,B)}}p.$$

Let $\mathcal{M}(A,B;x)$ be the period of $A^n+B \bmod \mathcal{N}(A,B;x)$. So $\mathcal{M}(A,B;x)$ is the LCM of the periods of $A^n+B$ modulo each of the primes dividing $\mathcal{N}(A,B;x)$.

Let $\mathcal{R}(A,B;x)$ be the number of solutions to $(A^n+B,\mathcal{N}(A,B;x))>1$, $n \in \mathbb{Z}/\mathcal{M}(A,B;x)\mathbb{Z}$. Then let

$$ \mathcal{C}_{A,B} = \lim_{x \rightarrow \infty}\left(\frac{\mathcal{M}(A,B;x)-\mathcal{R}(A,B;x)}{\mathcal{M}(A,B;x)}\right)\left(\frac{\mathcal{N}(A,B;x)}{\varphi(\mathcal{N}(A,B;x))}\right). $$

Finally, we naively conjecture (subject to likely future refinement) that the number of primes assumed by $A^n+B$, less than $x$, is asymptotic to

$$ (\mbox{factor from future refinement})\prod_{p \in \mathcal{P}(A,B)}\frac{p}{p-1}\mathcal{C}_{A,B}\sum_{n \leq (\log x/\log A)}\frac{1}{n\log A}. $$

The constant $\mathcal{C}_{A,B}$ is able to detect when $A^n+B$ is unable to assume infinitely many prime values, and will be zero in those cases. (Example: $3^n-1$).

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.