## Question on Dickson's Conjecture.

Expand Messages
• Can I interpret Dickson s conjecture as saying, that for any number of distinct arithmetical progressions of positive integer terms, providing some terms in
Message 1 of 3 , Feb 6, 2007
Can I interpret Dickson's conjecture as saying, that for any number of
distinct arithmetical progressions of positive integer terms, providing
some terms in each AP are prime, that there is a common integer
multiplier for the constant difference in each AP, such that the
resulting terms are all prime?
Thanks folks.
Bill Sindelar
• ... Well, I m no expert, but I think that sounds almost but not quite right. Let me try to say it in math. ... OK, so far so good. a_1 n + d_1 a_2 n + d_2 ...
Message 2 of 3 , Feb 6, 2007
On 2/6/07, w_sindelar@... <w_sindelar@...> wrote:
> Can I interpret Dickson's conjecture as saying, that for any number of
> distinct arithmetical progressions of positive integer terms, providing
> some terms in each AP are prime, that there is a common integer
> multiplier for the constant difference in each AP, such that the
> resulting terms are all prime?
> Thanks folks.
> Bill Sindelar

Well, I'm no expert, but I think that sounds almost but not quite right.
Let me try to say it in math.

> distinct arithmetical progressions of positive integer terms,
OK, so far so good.
a_1 n + d_1
a_2 n + d_2
...
a_k n + d_k

> providing some terms in each AP are prime,

That's not enough.
For instance, suppose that you take
2n+3
2n+5
2n+7

Well, clearly they'll all be prime pretty often, since they all cover
each odd number > 7.
But there's equally clearly no value of n that makes them simultaneously prime.

The "obvious" criterion is that if you take the product of the first
term of each arithmetic progression, call it p_1, and so on with p_2,
p_3, and so on,
then there must be no prime p that is a divisor of p_n for ALL n.

In my 2n+3, 2n+5, 2n+7 example, the product
(2n+3)(2n+5)(2n+7) = 8n^3+60n^2+142n+105 is "obviously" always
divsible by 3, so it's no good.

This is the part where you need to be very careful in your statement
-- what is it that rules out certain sets of values?

I think a good statement is that the sequence of products of terms of
your arithmetic progressions must have GCD = 1.

> that there is a common integer
> multiplier for the constant difference in each AP,

In other words, a particular value of n,

> such that the
> resulting terms are all prime?

so that a_1 n + b_1, ..., a_k n + b_k,
are all primes for that one value of n.
Indeed.

And I think that if there's always one such value, there must always
be infinitely many such values, because once you've found one such n,
you can re-set the b's (by adding a_i * n to each b_i) and then
generate another value of n, and another ...

But this is quite a powerful conjecture! Pretty much every unsolved
problem about primes (twin primes, arithmetic progressions, etc, etc)
will be solved if this conjecture is proven.

--Joshua Zucker
• ... No, as Joshua Zucker explained. A simple counter example is 3n+1 and 3n+2 (one of them is always even). See
Message 3 of 3 , Feb 7, 2007
Bill Sindelar wrote:
> Can I interpret Dickson's conjecture as saying, that for any number
> of distinct arithmetical progressions of positive integer terms,
> providing some terms in each AP are prime, that there is a common
> integer multiplier for the constant difference in each AP, such
> that the resulting terms are all prime?

No, as Joshua Zucker explained.
A simple counter example is 3n+1 and 3n+2 (one of them is always
even).

See http://primes.utm.edu/glossary/page.php?sort=DicksonsConjecture
for an exact statement of Dickson's conjecture:

Given a family of linear functions with integer coefficients a_i > 1
and b_i:
a_1*n + b_1, a_2*n + b_2,  a_k*n + b_k,
then there are infinitely many integers n > 0 for which these are
simultaneously prime unless they "obviously cannot be" (that is,
unless there is a prime p which divides the product of these for all
n).

(The exact statement is not "obviously cannot be", but the
explanation of that: "unless there is a prime p which divides the
product of these for all n".)

A brute force way to test whether there is such a prime p without
using modular arithmetic:
For each prime p <= k, test whether p divides the product of the
linear functions for all n from 0 to p-1.
The condition of the conjecture is satisfied iff there is no such p.

In the above example, 2 divides (3n+1)*(3n+2) for both n=0 and n=1,
so the condition is not satisfied.
Zucker gave the example 2n+3, 2n+5, 2n+7.
3 divides (2n+3)*(2n+5)*(2n+7) for n = 0, 1, 2.

Note however that a case of simultaneuos primes may be possible if
one of the primes is p itself. For example, 2n+1, 2n+3, 2n+5 are all
prime for n=1, although 3 always divides their product. (If n=0 is
allowed then Zucker's example gives all primes).

A more powerful conjecture about polynomials which includes Dickson's
as a special case is Schinzel's Hypothesis H:
http://primes.utm.edu/glossary/page.php?sort=HypothesisH

--
Jens Kruse Andersen
Your message has been successfully submitted and would be delivered to recipients shortly.