11
$\begingroup$

This question is inspired by @Dan Brumleve's question on finding Pratt certificates efficiently. In a comment, I say that his problem is as hard as factoring, as long as the following problem is "easy" (i.e., can be solved in polynomial time):

Given $N > 2$, find a prime $p$ such that $$p \equiv 1 \pmod{N} \tag{1}.$$

(Of course, Dirichlet's theorem assures us that infinitely many such $p$ exist.)

Now, I do not know of a clever way to find such a $p$, so I suggested simply iterating through the arithmetic progression $1+kN$ for $k = 0, 1, 2, \ldots$, and terminating when we hit the first prime number. Clearly, this procedure is efficient if and only if the smallest prime $p$ satisfying $(1)$ is at most $N^{O(1)}$. (Edit: This claim is incorrect; see below.) I want to know if such a bound holds or not.

More generally,

Given an integer $N$, what upper bound do we know on the smallest prime satisfying $(1)$?

I did a quick check on Wikipedia and Mathworld, but cannot find any relevant results.

Edit: Turns out the claim in the question is false. The procedure will be efficient only if the smallest prime is $O(N \cdot\mathrm{poly}\log N)$, which seems very unlikely. In any case, I will just keep this question as it is, since it makes sense as a stand-alone question as well.

  • 0
    I apologize for the mistake (which is only tangentially related to this question anyway), and also not researching the topic properly. I overlooked the link to Linnik's theorem at the bottom of the wiki page.2011-09-05

2 Answers 2

11

The relevant results are found under the heading, Linnik's Theorem. Linnik proved that the least prime congruent to $a$ mod $d$ is at most $cd^L$ for some absolute constants $c$ and $L$. The current best bound is $L\le5.2$. On the Generalized Riemann Hypothesis, you can show there's a prime less than $(\phi(d)\log d)^2$, where that's Euler's phi-function. It is conjectured there's always a prime less than $d^2$.

  • 0
    Thanks! I guess my searching was quite sloppy then :).2011-09-05
  • 0
    Since a second answer has been posted, I unaccepted your answer for now. I hope you don't mind :). I will accept some answer after a few days...2011-09-05
  • 0
    @Srivatsan Narayanan: I support Gerry's answer. Mine is just a silly offhand remark; his points to a major theorem. :)2011-09-07
  • 0
    Is the constant $c$ known as well ?2015-10-14
  • 0
    @Peter, I don't know. I suppose one could chase through the literature on Linnik's Theorem to see. But since 5.2 is conjectured to be far from best possible for $L$, there may not be so much interest in pinning down a value for $c$.2015-10-14
6

Gerry Myerson has answered your main question, so I'll address the other part. I don't think that the claim is false, though certainly it's not proven. In any case I wouldn't say it's "very unlikely".

In fact it seems quite likely to me that the smallest k with $kn+1$ prime will be $O((\log n)^3)$ -- indeed, probably even $O((\log n)^2(\log\log n)^e)$ for some e.

Disregarding $n<20$, $e=0.18$ works up to 30 million with a constant of 1. A braver mathematician might conjecture that it holds for $e=0$ and a somewhat larger constant.

  • 0
    Oh, that's interesting. Thanks! Is there any conditional result or any explicit conjecture of this vein?2011-09-05
  • 0
    @Srivatsan Narayanan: I do not know of a conditional proof. I'm sure there's a conjecture on the subject--older than mine, that is--but I haven't found it in a cursory search.2011-09-05
  • 0
    Ok. Thank you. ${}{}{}{}$2011-09-05
  • 0
    Charles' conjecture is similar to Cramér's conjecture, generalized to arithmetic progressions, but concerning only the first gap; the same heuristic arguments apply. One thing I don't understand is why the log(log(n))^e term?2011-09-07
  • 1
    @Dan Brumleve: I'm quite confident that for every $\varepsilon>0$ there are only finitely many prime gaps larger than $(\log x)^{2+\varepsilon}$ but Maier's (1985?) paper shook my confidence in the Cramer model enough that I question not just $(\log x)^2$ but even $C(\log x)^2.$ (I wouldn't bet money that it fails for $C=2$, but it wouldn't shock me.) This problem is similar: I'm not confident enough on a theoretical or computational basis to say $(\log n)^2$. But in this case I opted for the slightly stronger form $(\log n)^2(\log\log n)^e$ rather than just $(\log n)^{2+\varepsilon}$.2011-09-07
  • 0
    My apologies, it looks like the font makes it quite hard to distinguish between the $\varepsilon$ (epsilon) and the $e$ (e) in exponents. The only exponent with $e$ is the penultimate, $(\log\log n)^e.$2011-09-07