Welcome to MathOverflow

Question

9

What are the best known density results and conjectures for primes p where p - 1 has a large prime factor q, where by "large" I mean something greater than $\sqrt{p}$.

The most extreme case is that of a safe prime (Wikipedia entry), which is a prime p such that $(p - 1)/2$ is also a prime (the smaller prime is called a Sophie Germain prime). I believe it is conjectured (and not yet proved) that infinitely many safe primes exist, and that the density is roughly $c/\log^2 n$ for some constant $c$ (as it should be from a probabilistic model).

For the more general setting, where we are interested in the density of primes p for which p - 1 has a large prime factor, the only general approach I am aware of is the prime number theorem for arithmetic progressions, and some of its strengthenings such as the Bombieri-Vinogradov theorem (conditional to the GRH), the (still open) Elliott-Halberstam conjecture, Chowla's conjecture on the first Dirichlet prime, and some partial results related to this conjecture. All of these deal with the existence of primes $p \equiv a \pmod q$ for arbitrary q and arbitrary a that is coprime to q.

My question: can we expect qualitatively better results for the situation where q is prime and $a = 1$? Also, I am not interested in specifying q beforehand, so the existence of a p such that there exists any large prime q dividing $p - 1$ would be great. References to existing conjectures, conditional results, and unconditional results would be greatly appreciated.

edited Sep 13 2010 at 5:25

Charles
4,189●8●27

asked Feb 9 2010 at 19:00

Vipul Naik
4,935●13●43

Mark Lewko · Answer 1 · 2012-11-29 05:51:56Z UTC

6

See "On the number of primes p for which p+a has a large prime factor." (Goldfeld, Mathematika 16 1969 23--27.) Using Bombieri-Vinogradov he proves, for a fixed integer a, that

$\sum_{p \leq x} \sum_{ x^{1/2}< q \leq x : q | p+a} ln(q) = x/2 + O(x ln ln x / ln(x))$

where the summation is over p and q prime. Note that this implies that the number of primes $p$ less than $x$ such that $p-1$ has a prime factor greater than $p^{1/2}$ is asymptotically at least x/ 2ln(x).

edited Nov 29 at 5:51

answered Feb 12 2010 at 8:33

Mark Lewko
4,216●12●20

	Strange - the density of integers $n$ that have a prime factor greater than $n^{1/2}$ is $\log 2$ by results on friable (or smooth) numbers (see the Dickman rho function). I would think that the density of such shifted primes is also $\log 2$. I have proved this subject to a version of the Hardy-Littlewood prime tuples conjecture (see my J. Number Th. paper of 2002). – Greg Martin Mar 4 2011 at 19:48
	Mark, your conclusion that the number of primes less than x such that p-1 has a prime factor larger than $\sqrt(p)$ is asymptotic to x/(2ln(x)) is not correct. Note that we have a log(q) factor in the result not log(p) and for the relevant range of q we have $\log(p)/2 \leq \log(q) \leq \log(p)$ and they are not asymptotically equal. Greg is correct that the density should be $\log 2$. – Johan Andersson Nov 26 at 13:26
	Johan, thanks! I've adjusted the text. – Mark Lewko Nov 29 at 5:52

Victor Miller · Answer 2 · 2010-02-15 02:41:58Z UTC

4

Fouvry showed that the relative density is positive of primes $p$ for which the largest prime factor of $p+a$ is $\ge p^{\alpha}$ for $\alpha \approx .6687$.

Etienne Fouvry, Th ́eoreme de Brun-Titchmarsh; application au th ́eoreme de Fermat, Invent. Math 79 (1985), 383–407. MR0778134 (86g:11052)

edited Feb 15 2010 at 2:41

answered Feb 9 2010 at 22:48

Victor Miller
3,395●2●14●26

I didn't understand. Did you leave the statement incomplete? What is the conclusion about the relative density? – Vipul Naik Feb 9 2010 at 22:56

..."is positive"? – David Hansen Feb 9 2010 at 23:06

Did you mean $\alpha \le 0.6687$ above instead of $\alpha > 0.6687$? The larger the $\alpha$, the smaller the density, and the paper you've quoted also seems to suggest that. – Vipul Naik Feb 10 2010 at 1:07

@Vipul: I'm sure that I mean $\alpha > 0.6687$ since we're interested in $p-1$ have a large prime factor. – Victor Miller Feb 10 2010 at 3:31

1

@DavidHansen: perhaps I didn't state it clearly enough. Fouvry showed that there is an $\alpha$ which is approximately 0.6687 so that for a fixed $a \ne 0$ the set $\{p \text{ prime}: P(p+a) \ge p^{\alpha} \}$ has positive density in the set of all primes, where $P(n)$ denotes the larges prime factor dividing $n$. Bigger values of $\alpha$ are better. The post alluding to a result of Goldfeld had $\alpha = \frac 12$. – Victor Miller Feb 15 2010 at 3:50

show 1 more comment

François G. Dorais · Answer 3 · 2010-02-15 03:39:06Z UTC

I believe that sieve methods (in particular methods similar to Chen's result on "almost" Goldbach and twin primes) should give infinitely primes $p$ such $(p-1)/2$ is a product of two primes. That's more than what you asked.

Wikipedia quotes a result of Bombieri-Friedlander-Iwaniec stating that Linnik's constant is $2$ for almost all moduli. If the same is true for infinitely many prime moduli $q$, then you are in business. A prime $p \equiv 1 \mod q, p \ll q^2$ is what you want.

Maybe an analytic number theorist will come along and give precise references.

Wikipedia - Sieve Methods

Wikipedia - Linnik's Theorem

MRA · Answer 4 · 2010-02-10 00:22:54Z UTC

John A. Gordon introduced the notion of strong primes (try Wikipedia) which, beside other requirements, are primes $p$ satisfying $p \equiv 1 \mod r$ for some large prime $r$ of about the same size as $p$. In the following paper, it has been shown how to construct strong primes of arbitrary bit size efficiently and with high probability:

John A. Gordon: "Strong Primes Are Easy to Find", Proceedings of EUROCRYPT '84, LNCS 209, Springer, 1985.

Primes p for which p - 1 has a large prime factor

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

4 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.