Loading ...
Sorry, an error occurred while loading the content.

Question on Dickson's Conjecture.

Expand Messages
  • w_sindelar@juno.com
    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
    • 0 Attachment
      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
    • Joshua Zucker
      ... 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
      • 0 Attachment
        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
      • Jens Kruse Andersen
        ... 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
        • 0 Attachment
          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.