If $n-1$ is $f(n)$-smooth, $n$ is prime infinitely often. What is the best $f$?

For all primes $p$, $p-1$ is $\frac{p}{2}$-smooth, so $f(n) = \frac{n}{2}$ works.

If $q$ is a Fermat prime, then $q-1$ is $2$-smooth. Since we cannot prove there are a finite number of Fermat primes it is possible that $f(n) = 2$ works.

Can anything in between be established with certainty?

I considered $f(n) = \sqrt{n}$. The simplest kind of $\sqrt{n}$-smooth number is a square, and since we don't know if there are an infinite number of primes of the form $k^2+1$ we are in the same situation as with Fermat primes. I'm not sure how to approach the case when $n-1$ is $\sqrt{n}$-smooth but not square.

I feel like it should be possible to prove this for $f(n)=\frac{n}{\log{n}}$ (there are an infinite number of primes $p$ where $p-1$ is $\frac{p}{\log p}$-smooth). How can this be shown? What is the best that is known?


Is there any infinite set of primes for which membership can be decided quickly?

Are there infinitely many primes next to smooth numbers?


There has been many works on that problem. A result of Baker and Harman asserts that $p-1$ is $p^{0.2961}$-smooth infinitely often, and seems to be the current published record. It uses very strong results about primes in arithmetic progression. An earlier result of M. Goldfeld has $f(n)=\sqrt{n}$ using the theorems of Bombieri-Vinogradov and Brun-Titchmarsh.

It's not obvious to me that there should be an easy proof for $f(n)=n/\log n$, since this relates to good estimates for the number of primes of size $\approx x$ in a congruence class to a modulus between $x/\log x$ and $x$.


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.