Reference for a conjecture on the first primes congruent to 1 modulo other primes

Question

Given a prime $p$, define $f(p)$ to be the smallest prime congruent to $1$ modulo $p$. For example, $f(7)=29$. It has been conjectured that $f(p)<p^2$ always: by Schinzel in his "Hypothesis H" paper with Schinzel (Acta Arith. 1958), and also by Kanold (Arch. Math. 1963). Of course this is also related to Linnik's theorem, and to the conjecture of Chowla that $f(p) \ll_\varepsilon p^{1+\varepsilon}$. (And all of these conjectures hold for any reduced residue class $a\pmod p$, not just $1\pmod p$.)

One surprising consequence of the conjectured bound $f(p)<p^2$ is that the function $f$ is injective! For if not, then there exist primes $p_1<p_2$ such that $f(p_1)=f(p_2)=q$. But then both $p_1$ and $p_2$, hence their product, divides $q-1$, and so $p_1^2<p_1p_2\le q-1<q=f(p_1)<p_1^2$, a contradiction.

Does anyone know where this latter conjecture - the injectivity of $f$ - appears in the literature? (with or without the relationship to the first conjecture)

(For that matter, if anyone knows where the aforementioned conjecture of Chowla appears in the literature, I'd be happy for that pointer as well.)

Answer 1

There are even stronger conjectures in the literature:

1) D.R. Heath-Brown, Almost-primes in arithmetic progressions and short intervals. Math. Proc. Cambridge Philos. Soc. 83 (1978), no. 3, 357–375. http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=2079092

quoting from the first few lines: "... if $(l,k)=1$, there exists a prime $p$ satisfying $$p \equiv l \bmod k, \quad p\leq k^2, \quad (k\geq 2).$$ Indeed the bound for $p$ may presumably be reduced to $p \ll k(\log k)^2$. "

Actually, Heath-Brown unconditionally proves that there are many (i.e. the expected number) $P_2$ numbers smaller than $k^{2-\delta}$, for small $0\leq \delta \leq 0.035$. Maybe this gives a partial result for your injectivity question.

Further references:

A paper by A. Granville (Least primes in arithmetic progressions. Th\'{e}orie des nombres (Quebec, 1987), 306–321, de Gruyter, Berlin, 1989) http://www.dms.umontreal.ca/~andrew/1989.htm

points to an even more explicit version of a least prime conjecture: following a heuristic of Wagstaff, see http://www.ams.org/journals/mcom/1979-33-147/S0025-5718-1979-0528061-7/ , McCurley observed that this heuristic implies: $\lim\sup_{k\rightarrow \infty} \frac{p(k)}{k(\log k)^2} =2$.

A final comment: Your function $f(p)$ is (presumably) injective on the primes, but not on all integers. (Say 11 is the least prime 1 mod 10, and the least 1 mod 5). This may explain why others, possibly, did not study the question from your point of view.

---

Update: Computing the first values of least primes 1 mod p, and checking the OEIS http://oeis.org/A035095

where we find the comment:

"Formula: According to a long-standing conjecture (see the 1979 Wagstaff reference), a(n) <= prime(n)^2+1. This would be sufficient to imply that a(n) is the smallest prime such that greatest prime divisor of a(n)-1 is prime(n), the n-th prime: A006530(a(n)-1)=A000040(n). This in turn would be sufficient to imply that no value occurs twice in this sequence. - Franklin T. Adams-Watters, Jun 18 2010"

It seems, the last half sentence is the injectivity you are looking for, based on an explicit bound of your $f(p)$.

Further, in http://oeis.org/A066674 we find the discussion, if the two sequences above are the same, with related comments by Poonen and Bach.

Answer 2

For your parenthetical request: S. Chowla, On the least prime in an arithmetic progression. J. Indian Math. Soc. 1 (1934) 1-3.