Dickson's Conecture says the following: If $f_1(n)=a_1+b_1n, f_2(n)=a_2+b_2n, \ldots, f_k(n)=a_k+b_kn$, with $b_j \geq 1$, $1 \leq j \leq k$ satisfy a congruence condition, then there exist infinitely many positive integers $n$ for which every $f_j(n)=a_j+b_jn$ is a prime number, $1 \leq j \leq k$.

(1) What is the congruence condition?

In Schinzel's hypothesis H, a condition is mentioned, which I suspect is the congruence condition that I am looking for; it says: "For every prime $p$, there is an $n$ such that all the polynomial values at $n$ are not divisible by $p$".

This condition obviously excludes the case $f_1(n)=3+n$ and $f_2(n)=4+n$, which is a trivial counterexample to Dickson's conjecture/Schinzel's hypothesis H, since always one of $\{3+n,4+n\}$ is an even number, so cannot be a prime number (this counterexample does not satisfy the above condition, since for $p=2$ there is no $n$ with $2 \nmid 3+n$ and $2 \nmid 4+n$).

(2) If the congruence condition is indeed: "For every prime $p$, there is an $m$ such that all the polynomial values at $m$, $\{f_j(m)\}$, are not divisible by $p$", then it seems to me that in practice it is very difficult to check (except trivial cases as $f_1(n)=3+n, f_2(n)=4+n$); Am I missing something?

I am interested in the special case where $\gcd(a_j,b_j)=1$, $1 \leq j \leq k$, $k=2$. In that case, if I wish to check the congruence condition, then, for a given prime $p$, all I know (by Dirichlet's theorem on arithmetic progressions) that there exists $m$ such that $p \nmid f_1(m)=a_1+b_1m$ (just take large enough $m$ such that $a_1+b_1m$ is a prime number greater than $p$, so clearly $p$ does not divide a greater prime number), but $p$ may divide $f_2(m)$.

Therefore, if we assume that Dickson's Conjecture is true, then even in the special case $k=2$, $\gcd(a_1,b_1)=1$, $\gcd(a_2,b_2)=1$, it seems not applicable.

Edit: This is a relevant paper that I have just found. In that paper an interesting result due to Maynard-Tao is mentioned ("Even more impressively... it was shown that one can take $k_2=50$"). However, they deal with $b_1=\cdots=b_k=1$.

Thank you very much!


In practice it is not that hard to check (2). Unless $b$ is itself divisible by $p$, there is exactly one congruence class of $m$ for which $a+bm$ is divisible by $p$. That means that in the generically-worst case, there are at most $k$ congruence classes of $m$ mod $p$ that could cause any of the $\{f_j(m)\}_j$ to be divisible by $p$.

If $p > k$ then there will always be some congruence class available that makes all the $\{f_j(m)\}$ non-zero, so we only need to be concerned with $p \le k$, at least when $p$ does not divide any $b_j$.

But there are only finitely many possible primes that divide any $b_j$, so those can be checked separately (as metamorphy's answer suggests, they are in fact completely harmless unless $p$ also divides $a_j$).

  • $\begingroup$ Thank you very much! The elaboration about checking $p \leq k$ helped me. (I do not know which of the two answers to choose..). $\endgroup$ – user237522 Sep 26 '18 at 0:59
  • $\begingroup$ "If $p > k$ then there will always be some congruence class available that makes all the $\{f_j(m)\}$ non-zero". Please, how many such $m$'s exist? (infinitely many?). $\endgroup$ – user237522 Sep 26 '18 at 8:51
  • $\begingroup$ There are finitely (and at least one) many congruence classes of $m$ that work. In each congruence class, of course, we have infinitely many $m$. For instance the congruence class of integers congruent to $3$ mod $5$ contains 3, 8, 13, etc... $\endgroup$ – Erick Wong Sep 26 '18 at 15:24
  • $\begingroup$ Thank you for the explanation. (Please, do you think that math.stackexchange.com/questions/2930893/… has a positive answer? It seems to me, though I may be wrong, that similar arguments to the ones you mentioned here will show that it has a positive answer). $\endgroup$ – user237522 Sep 26 '18 at 21:27
  • $\begingroup$ (If I understand right, we can find at least one congruence class $L$ mod $\epsilon$ such that $\epsilon \nmid u+Lm$ and $\epsilon \nmid v+Ln$. Then, inside that congruence class, we can choose large enough member $\tilde{L}$ that will make $v+\tilde{L}n$ a prime number). Oh, now I see that the problem is that perhaps none of the members $\hat{L}$ of that congruence class will make $v+\hat{L}n$ a prime number... $\endgroup$ – user237522 Sep 26 '18 at 22:01

I saw it, in addition to $a_j > 0$ and $(a_j, b_j) = 1$ ($1 \leq j \leq k$), in the following form: for any prime $\color{red}{p \leq k}$, the mapping $n \mapsto P(n) := \displaystyle\prod_{j = 1}^{k}(a_j + b_j n) \bmod p$ is not identically zero.

For $p > k$ this holds automatically, as any polynomial over $\mathbb{Z}/p\mathbb{Z}$ in $n$, which is identically zero as a function of $n$, must be a multiple of $n(n-1)\ldots(n-(p-1))\color{lightgray}{\equiv n^p-n}$ with degree $p>k$ (and in our case it cannot be identically zero as a polynomial).

Thus it's not that hard to check ($n^p - n$ should not divide $P$ over $\mathbb{Z}/p\mathbb{Z}$ for each prime $p \leq k$).

  • $\begingroup$ Some explanation of why it is sufficient to only check $p\le k$ (given the additional coprimality condition) would add a lot more value to this answer. $\endgroup$ – Erick Wong Sep 26 '18 at 0:41
  • $\begingroup$ Thank you very much for the answer! Sounds very nice that we only have to check primes $p \leq k$! (also in Wikipedia they have not mentioned that $\gcd(a_j,b_j)=1$, though this is the case I am interested in). Do you have any reference? $\endgroup$ – user237522 Sep 26 '18 at 0:45
  • $\begingroup$ @user237522 If $\gcd(a_j,b_j) > 1$, then there is no way for that collection of functions to satisfy the congruence condition, so it is not strictly necessary to stipulate that condition. It is important to stipulate it (or something of similar strength) in order to completely ignore all primes $p>k$. $\endgroup$ – Erick Wong Sep 26 '18 at 0:52
  • $\begingroup$ Thank you. Yes, I see, it is a trivial condition which also appears in Dirichlet's theorem on arithmetic progressions (a special case of Dickson's Conjecture). Obviously, if $\gcd(a_1,b_1)=d > 1$ then $f_1(n)=a_1+b_1n=d r$, which is not a prime number. $\endgroup$ – user237522 Sep 26 '18 at 0:56
  • 1
    $\begingroup$ @ErickWong A bit late, but I agree. Edited. $\endgroup$ – metamorphy Sep 28 '18 at 11:22

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.