# Primes $p$ for which $pk+1$ is prime for small $k$ (or approximating Sophie Germain)

The twin prime conjecture says there are infinitely many pairs $p,p+2$ that are both prime, and although we still don't know whether it's true there's been a lot of progress recently showing that there are infinitely many pairs $p,p+k$ that are both prime, for $k$ bounded by a constant.

It's also an old conjecture that there are infinitely many pairs $p,2p+1$ that are both prime (Sophie Germain primes and safe primes respectively). Is there any hope of adapting the recent twin prime progress to approximate the constant 2 in the Sophie Germain conjecture by something larger? That is, can it be proven that there are infinitely many pairs $p,kp+1$ that are both prime, with $k=O(1)$?

Of course Dirichlet and Linnik say that for every $p$ there is eventually a $k$ such that $pk+1$ is prime, but I'm more interested in the case of infinitely often rather than for all $p$, and I'd like $k$ to be significantly smaller than the proven bounds in Linnik's theorem. The best bound I know how to prove is $k=O(p)$, which follows from the existence of infinitely many "pseudo Sophie Germain primes", numbers $q$ that are prime or the product of two primes and for which $2q+1$ is prime (see arXiv:math/0603439). Letting $p$ be the largest prime factor of $q$ gives $k=2q/p\le 2p$. So I think any bound $k=o(p)$ would be interesting.

-
Peripheral to the question, but why do people say "Sophie Germain primes" instead of just "Germain primes"? We don't say "Pierre de Fermat primes" or "Marin Mersenne primes", and there's been no other famous mathematician called Germain, as far as I know. If it's some outdated convention based on gender, isn't it time we abandoned it? – Tom Leinster Nov 23 '13 at 15:04
In case anyone is curious what this was for: see arxiv.org/abs/1408.1422. The largest prime factor of another prime provides a lower bound on degree (as a function of graph size) for finding an exact solution to certain graph-drawing problems by iterated polynomial root-finding methods. – David Eppstein Aug 12 '14 at 20:49

This paper uses "$\hspace{.01 in}P(n)$ to denote the greatest prime factor of an integer $n\hspace{.01 in}$",
and obtains the following result as Theorem 2 on page 2.

Let $a\in \mathbb{Z},\theta < 1-\frac12 \exp \left(-\frac14 \right) = 0.6105\cdots$ .
Then there exist effectively computable constants $X_1(a,\theta),\delta(\theta)>0$, such that, if $x > X_1$, we have $$\displaystyle\sum_{\substack{p\leq x \\ P(p+a)>x^{\theta}}} 1 > \delta(\theta) \frac{x}{\log x}.$$

In particular, this implies that for all $b$, $\:\:$ if $\;\; \frac{\exp\left(-\frac14 \right)}{2-\exp\left(-\frac14 \right)} \: < \: b \;\;$ then there are
infinitely many pairs $\;\; p\:,\:p\hspace{-0.04 in}\cdot\hspace{-0.04 in}k+1 \;\;$ that are both prime, with $\:\: k < p^b \;\;$.

Since $\; \frac{\exp\left(\hspace{-0.02 in}-\frac14 \hspace{-0.03 in}\right)}{2\hspace{.02 in}-\hspace{.03 in}\exp\left(\hspace{-0.02 in}-\frac14 \hspace{-0.03 in}\right)} < \frac23 < 1 \;$, $\;$ that gives a bound $\: k\in o(\hspace{.03 in}p) \;$.

(Incidentally, I only knew about that paper due to Mark's answer to my question here.)

-
Thanks! Yes, this is very similar to your earlier question — I am looking for large prime factors of $p-1$, while you are looking for large prime factors of $p+1$. – David Eppstein Nov 23 '13 at 23:10
@David, Harmen's result applies in the case of $p-1$ as well. See Theorem 2 in the paper. – Mark Lewko Nov 23 '13 at 23:43
Yes, I agree. I was just describing how our two questions resemble each other, but the papers that answer one also answer the other apparently. Through the reference you gave me, I also found R. C. Baker and G. Harman. Shifted primes without large prime factors. Acta Arith. 83(4):331–361, 1998, which has a stronger bound on $k$ (in terms of the largest prime factor of $p-1$, they show it is infinitely often at least $p^{0.677}$). – David Eppstein Nov 24 '13 at 0:08

Consider a tuple of the form $(n,a_1 n +1, a_2 n+1, \ldots a_k n+1)$ where the $a_k$'s are chosen such that there is no local obstruction to the numbers in the tuple being simultaneous prime. Then the GYP/Zhang method allows one to prove that two of these are prime infinity often if $k$ is larger than some fixed $K_0$ (see: http://michaelnielsen.org/polymath1/index.php?title=Bounded_gaps_between_primes for the most up-to-date value of $K_0$). The Maynard/Tao argument allows one to get more primes in the tuple at the expense of making $K_0$ larger.

The main issue with getting something of the form of the Sophie Germain conjecture is that one does not have any control over where in the tuple the primes occur. If one could somehow force the first term of the tuple to be one of the primes then we could deduce that the pair $(p, ap+1)$ were simultaneously prime for some a in any admissible tuple of sufficiently large size. However, there seems to be no way to deduce/force restrictions of this form with the current method. [Of course getting the Sophie Germain conjecture with precisely $2$ is probably even harder and of a similar difficulty to the twin prime problem.]

On the other hand, by the pigeonhole principle, one can deduce that there are infinity many prime pairs of the form (say) $(an+1, bn+1)$ which is of a similar flavor.

Of course, given the recent breakthroughs in this area, problems of this form do seem tantalizingly close.

-