29
$\begingroup$

At the time of writing, question 5191 is closed with the accusation of homework. But I don't have a clue about what is going on in that question (other than part 3) [Edit: Anton's comments at 5191 clarify at least some of the things going on and are well worth reading] [Edit: FC's excellent answers shows that my lack of clueness is merely due to ignorance on my own part] so I'll ask a related one.

My impression is that it's generally believed that there are infinitely many Mersenne primes, that is, primes of the form $2^n-1$. My impression is also that it's suspected that there are only finitely many Fermat primes, that is, primes of the form $2^n+1$ (a heuristic argument is on the wikipedia page for Fermat primes). [EDIT: on the Wikipedia page there is also a heuristic argument that there are infinitely many Fermat primes!]

So I'm going to basically re-ask some parts of Q5191, because I don't know how to ask that a question be re-opened in any other way, plus some generalisations.

1) For which odd integers $c$ is it generally conjectured that there are infinitely many primes of the form $2^n+c$? For which $c$ is it generally conjectured that there are only finitely many? For which $c$ don't we have a clue what to conjecture? [Edit: FC has shown us that there will be loads of $c$'s for which $2^n+c$ is (provably) prime only finitely often. Do we still only have one $c$ (namely $c=-1$) for which it's generally believed that $2^n+c$ is prime infinitely often?]

2) Are there any odd $c$ for which it is a sensible conjecture that there are infinitely many $n$ such that $2^n+c$ and $2^{n+1}+c$ are simultaneously prime? Same question for "finitely many $n$".

3) Are there any pairs $c,d$ of odd integers for which it's a sensible conjecture that $2^n+c$ and $2^n+d$ are simultaneously prime infinitely often? Same for "finitely often".

$\endgroup$
5
  • $\begingroup$ Fermat primes have the form $2^{2^n}+1$. $\endgroup$ Oct 21, 2011 at 1:21
  • 9
    $\begingroup$ Yes but it's an easy exercise to check that if $2^n+1$ is prime then it's a Fermat prime. $\endgroup$ Oct 22, 2011 at 8:37
  • $\begingroup$ In the book "Number Theory Revealed, A Masterclass" by Granville, it is written: Calculations suggest there might be infinitely many primes of the form 2^n − 3, though we cannot compute very far since the numbers grow so rapidly. The most optimistic conjecture would be: Fix integer k. • Either there is a finite set of primes P such that for every positive integer n, the number 2^n + k is divisible by some element of P (and so is not prime). • Or there are infinitely many positive integers n for which 2n + k is prime. $\endgroup$
    – Watson
    Jun 5, 2022 at 7:43
  • $\begingroup$ (Note that it is nowadays NOT believed that for every Sierpinski number k, there is a finite set of primes P = P_k such that 2^n + k is divisible by some element of P). Also, the heuristic for infinitude of Fermat primes has been removed from Wikpedia in 2019. $\endgroup$
    – Watson
    Jun 5, 2022 at 7:43
  • $\begingroup$ According to Ofir Gorodetsky, « Fermat primes are special because they have the shape $2^n\pm 1$. More generally, $2^n\pm a^n$ enjoy special structure related to the decomposition of the polynomial $x^n\pm a^n$. For $2^n+3$ there is no such structure to exploit, and in absence of structure, we believe that the behavior is of a random number, in the sense that $2^n+3$ is prime with probability $\sim 1/\log(2^n) \sim 1/n$, as the PNT predicts, and the divergence of $\sum_n 1/n$ suggests that there are infinitely many primes $2^n+3$ (using the 2nd Borel–Cantelli lemma). » $\endgroup$
    – Watson
    Jun 5, 2022 at 7:45

6 Answers 6

34
$\begingroup$

Buzzard is correct to be skeptical of the most naive arguments: Erdos observed that $2^n + 9262111$ is never prime.

[edit Jan 2017 by Buzzard: the 9262111 has sat here for 7 years but there's a slip in Pomerance's slides where he calculates the CRT solution. The correct conclusion from Pomerance's arguments is that $2^n+1518781$ is never prime. Thanks to Robert Israel for pointing out that $2^{104}+9262111$ is prime.]

Question one is an incredibly classical problem, of course. Observe that the proof that $2^n + 3$ and $2^n + 5$ are both prime finitely often can plausibly work for a single expression $2^n + c$ for certain $c$. It suffices to find a finite set of pairs $(a,p)$ where $p$ are distinct primes such that every integer is congruent to $a$ modulo $p - 1$ for at least one pair $(a,p)$. Then take $-c$ to be congruent to $2^{a}$ modulo $p$. (Key phrase: covering congruences). I could write some more, but I can't really do any better than the following very nice elementary talk by Carl Pomerance:

www.math.dartmouth.edu/~carlp/PDF/covertalkunder.pdf

Apparently the collective number theory brain of mathoverflow is remaking 150 year old conjectures that have been known to be false for over 50 years! I was going to let this post consist of the first line, but I guess I'm feeling generous today. On the other hand, I'm increasingly doubtful that I'm going to get an answer to question 2339.

$\endgroup$
10
  • 7
    $\begingroup$ I didn't make a conjecture---I asked a question ;-) Fabulous post FC; thanks. $\endgroup$ Nov 13, 2009 at 15:38
  • 1
    $\begingroup$ Actually, looking at 2339 I see you've accused me of making a conjecture there too, whereas if I look at the source I again see that I only asked a question :-) $\endgroup$ Nov 13, 2009 at 15:41
  • 3
    $\begingroup$ @buzzard: it happens to the best of us, even Serre and Poincare. $\endgroup$ Nov 13, 2009 at 15:42
  • 7
    $\begingroup$ Finally I'll remark that it was Swinnerton-Dyer that has caused all this trouble. I had a couple of pints of cider with him once and then he let fly about conjectures these days not being worth anything, and how he remembered the good old days (by which I think he meant the sixties) when conjectures were things that were most certainly true, and everything else was just a question. Since that conversation I've been much more reluctant to conjecture anything! $\endgroup$ Nov 13, 2009 at 16:38
  • 3
    $\begingroup$ Unbelievable: this answer has been here over 6 years and nobody thought to check. FWIW the Pomerance slides give some congruences for which the correct solution (if I got it right) is $k=1518781$. $\endgroup$ Jan 15, 2017 at 9:15
4
$\begingroup$

There are certainly (many!) pairs of integers $c$, $d$ for which it's known that $2^n + c$, $2^n + d$ can't be simultaneously prime infinitely often -- take $c = 1$, $d = -1$, for instance, where $2^n - 1$ can only be prime if $n$ is prime, but $2^n + 1$ can only be prime if $n$ is a power of $2$. Alternatively, taking everything $\bmod 3$, we see that $c = -1$, $d = 7$ are only simultaneously prime at $n = 2$.

So there are lots of local obstructions to these pairs being simultaneously prime, although probably not enough to rule out all but finitely many of them.

[Edited because this is unlikely to fit in a comment]: Here's a rough stab at a really basic heuristic (for part 1 and part 3) which I don't see a way to make actually work, but maybe someone else will...

So let's fix $c$ and consider the $\bmod p$ behavior of $2^n + c$ for each odd prime $p$. Since $2^n$ is periodic $\bmod p$, for large $n$ we have some congruence classes $\bmod {(p-1)}$ for which $2^n + c$ is always composite. To simplify the analysis, we can just consider the behavior at $p$ such that $2$ is a primitive root $\bmod p$, in which case there's exactly one such congruence class $\bmod {(p-1)}$ for every $p$.

The problem now is that there's no obvious way to sieve this, since the primes minus one don't behave very nicely with respect to multiplication. My initial hunch -- which is only a hunch, not backed up by anything resembling logic -- is that generically speaking, we might see roughly the same behavior as if we were to sieve by the primes, i.e., $2^n + c$ is coprime to all the primes for which $2$ is a primitive root with probability $1/\log n$. This is much larger than the PNT predicts, of course, but notably it's still small enough that (assuming my back-of-the-envelope calculation and wildly speculative hunch are correct) we should expect that $2^n + c$, $2^n + d$ are typically simultaneously prime only finitely often.

[Edit 2]: So after some more thought I see where my hunch is horribly, horribly wrong, namely that there's no reason to believe that $a \equiv b \pmod {(p-1)}$ and $a \equiv d \pmod {(q-1)}$ has any solutions. But I do suspect that we do get some "new" forbidden exponents for almost every prime, which ::waves hands vigorously:: suggests that the values of $n$ with $2^n + c$ prime do have density $0$ and in particular probably have density at most $O(1/\log n)$, which is still good for a heuristic for (3). Can anyone make this more precise?

$\endgroup$
1
  • 1
    $\begingroup$ Yes. Indeed Anton's comment in 5191 gives another example (c=3,d=5) where there's a (similar-looking but slightly harder) proof that they can both only be prime finitely often. I also agree that probably the local conditions won't always save you (again follow Anton's idea and find explicit n,c,d such that 2^n+c and 2^n+d aren't prime but only have nice juicy prime factors of size > 10^6). So now we need some sensible heuristics to continue, if there are any sensible heuristics on these matters. I guess it's also worth remarking that no-one has said anything about Q1 yet. $\endgroup$ Nov 13, 2009 at 12:25
3
$\begingroup$

Hi there, I hope I'm not duplicating anything with what I will write. Here goes: If one considers the Bateman-Horn conjecture, it predicts that $$ \sum_{n \leq x}\Lambda(f(n)) \sim \prod_p\left(\frac{p-n_p}{p-1}\right)x $$

where $\Lambda(n)$ is the von Mangoldt function and $n_p$ is the number of solutions to the equation $f(n) \equiv 0 \bmod p$ in $\mathbb{Z}/p\mathbb{Z}$. The reason for the form of each Euler factor is as follows: For each $p$, usually there is $(p-1)/p$ chance of nondivisibility by $p$ in the integers. But if the set in consideration is the image of the polynomial $f$, then the new probability of nondivisibility by $p$ is $(p-n_p)/p$. So the Euler factor is $((p-n_p)/p)/((p-1)/p) = (p-n_p)/(p-1)$. Whether the infinite product over these factors is zero or not is like a competition between primes with $n_p=0$ and $n_p>1$. It really depends on the density of these primes with various $n_p$.

Therefore I'd be curious to know whether the above Bateman-Horn conjecture can be generalized to this case as follows(?): $$ \sum_{n \leq x}\Lambda(2^n+c) \sim \prod_p\left(\mbox{something}\right)x. $$

Or is there any reason why heuristics for $2^n+c$ must be treated differently from $f \in \mathbb{Z}[x]$?

It is interesting to consider something analogous to $n_p$ in the case of $2^n+c \equiv 0 \bmod p$. For $p|c$, we have $n_p=0$ since $2^n$ will never be $0 \bmod p$. For $p\nmid c$, one must consider the cyclic subgroup $<2>$ generated by $2$ in $(\mathbb{Z}/p\mathbb{Z})^{*}$. Let $h$ be the order of this subgroup. We have $h | p-1$. Let $\delta_p = 1$ if $c \in <2>$ and $\delta_p=0$ otherwise.

Then for each $p$, numbers of the form $2^n+c$ have probability $$(\delta_p \times (p-1)/h)/(p-1) = \delta_p / h$$ of divisibility by $p$. Therefore, perhas the Euler factor here should be (?) $$ \left(\frac{(h-\delta_p)/h}{(p-1)/p}\right). $$

Putting all this together, can one conjecture (?) $$ \sum_{n \leq x}\Lambda(2^n+c) \sim \prod_{p|c}\left(\frac{p}{p-1}\right)\prod_{p \nmid c}\left(\frac{(h-\delta_p)/h}{(p-1)/p}\right)x. $$

Thanks.

$\endgroup$
2
  • $\begingroup$ That seems unreasonable: the Euler product form in the twin prime, Schinzel, Bateman-Horn, etc, conjectures have their source in the Chinese Remainder Theorem (independence of reductions of integers modulo distinct primes). The analogue property fails for powers of $2$. (Or of any other integer $a\geq 2$). This is also why, for instance, sieve methods are unsuccessful for these types of questions. $\endgroup$ Oct 20, 2011 at 7:11
  • $\begingroup$ Ah, thanks very much. I really should have read the Lenstra-Pomerance-Wagstaff conjectures (en.wikipedia.org/wiki/Mersenne_conjectures) before I said the above. Thanks. $\endgroup$ Oct 20, 2011 at 9:39
1
$\begingroup$

Naive conjecture for (2) and (3) would be that there are only finitely many such $n$ (unless $c=d$, since then (3) becomes (1)). The reason is that heuristically the 'probability' that a number of order $m$ is prime is roughly $1/\log(m)$, and the sum $$\sum_n \frac{1}{\log(2^n+c)\log(2^n+d)}$$ converges.

$\endgroup$
4
  • 2
    $\begingroup$ In general I am nervous about these sorts of heuristics, because applied naively they would predict infinitely many Fermat primes, whereas applied more sensibly (i.e. think about which n can occur from an elementary viewpoint first and then heuristicise) they predict finitely many. On the other hand I don't think this specific objection (my nervousness about heuristics) applies to your heuristics (because if we made intelligent elementary observations which ruled out certain n first then the sum would only get smaller). So I think you've probably done (2) and (3). $\endgroup$ Nov 13, 2009 at 9:19
  • 1
    $\begingroup$ Actually, suddenly I am nervous about this argument. If c=1 then one can say a lot about possible factors of 2^n+c, for example, and a competing heuristic on the Wikipedia page for Fermat primes seems to say that incorporating these facts screws up the heuristic that there are only finitely many Fermat primes. Does a general heuristic look like this: "here are some things I can think of, now let's assume everything else is random and sum 1/log"? So implicit in such a heuristic is the assertion that you've not missed anything? $\endgroup$ Nov 13, 2009 at 10:13
  • $\begingroup$ Ok here is an explicit comment about your heuristic that I hope worries you. If 2 is not a primitive root mod a prime number q, then q might never divide 2^n+c (e.g. 7 never divides 2^n+9 and surely there will be other primes, possibly infinitely many more, with this property---certainly 2 never divides 2^n+9 either). Hence 2^n+9 is less likely to be composite than a random large number. For a proper heuristic you need to take this into account and recalculate. What I'm saying is that your heuristic might be too naive, and fixing it up to incorporate my comments might give a different answer $\endgroup$ Nov 13, 2009 at 10:17
  • $\begingroup$ I share your anxiety about these heuristics in general, and extreme naivete of mine in particular. For example, by these heuristics would give that if alpha is a real number, then floor(alpha^(3^n)) is prime finitely often. However, it is false for some alpha. $\endgroup$
    – Boris Bukh
    Nov 13, 2009 at 10:43
0
$\begingroup$

A heuristic approach might be to examine how many large primes are known for a given $c$.

A good source is Probable Primes Top 10000

The search form is here

Some results from the PRP Top 10000 dabase:

c largest-n number-of-primes-in-the-database:
3 479844 11
5 193965 4
7 566496 6
9 173727 6
11 345547 6
13 175628 2

Probably the computational effort for different $c$ in the database is quite different.

OEIS has data too.

$\endgroup$
-1
$\begingroup$

Hi, I believed that there are always an infinitude of primes in all forms of 2^n + c except c = 1 (fermat numbers). I don't have a proof though but gathering some data on my research of forms 2^x+3 and 2^x+5. I am interested the reason being that together they will produce infinite twin primes and prime arithmetic progression for (3,2^x+3,2^x+1 + 3), again just my belief and based on algorithm I am working on.

$\endgroup$
2
  • 3
    $\begingroup$ In the other thread there is already a proof that 2^x+3 and 2^x+5 will not produce infinitely many twin primes, and there is also a bunch of evidence to suggest that 3,2^x+3,2^{x+1}+3 will not produce infinitely many sets of three primes in an AP. $\endgroup$ Nov 13, 2009 at 14:21
  • $\begingroup$ Thanks for this, now I concede about this result, of course my original question still holds. How big x exponent is? I would imagine it to be big. $\endgroup$ Nov 13, 2009 at 18:41

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.