Wednesday 14 March 2018

Prime conjunctions and Dickson's conjecture

Way back in 2013 I blogged about "Prime Conjunctions". If you want to get the most out of this posting you will need to read that article first (use the search box) but I will supply some background here anyway.

This all started when one day I noticed that all my children's ages were prime numbers (and, of course, they remained like that until one of them had a birthday and spoilt everything). Not every set of people are destined to enjoy such a prime conjunction but how lucky do they have to be to have one? Since most prime numbers are odd it is unsurprising that a major thing to investigate is whether there will be a period when all their ages are odd and this was the main focus of my previous posting. But before recounting that story let's briefly consider the case that the prime 2 might occur as part of a prime conjunction. To determine whether that is possible all you need do is note the ages of your other children in the full year of one of your children being two; throughout the year these ages will change slightly as your other children have their birthdays and you see whether they ever become prime together. You have to do this for each child and the period in which they are two.

Having dispensed with the case that a prime conjunction might involve the prime number 2 we shall, from now on, just consider whether a prime conjunction with odd primes only can occur. So we shall begin by considering whether your children can have an odd conjunction: a period when all their ages are odd. It is not difficult to find the condition. If you list their ages at the beginning of the year in the order in which their birthdays occur you can look forward to them all being odd if that list is either a bunch of odds followed by a bunch of evens or a bunch of evens followed by a bunch of odds.

For example if on 1 January the ages in birthday order through the year are 10, 6, 9 then when the 6 year old turns 7 the ages will be 11, 7, 9 (because the 10 year old has already turned 11). On the other hand if their ages on 1 January had been 10, 5, 8 there is never a period when all their ages are odd.

It is also easy to see that even when an odd conjunction is possible there is only one period between birthdays when it occurs (in the example 10, 6, 9 that is the period in the year when the first two birthdays have occurred but the third not yet - and this is in every other year).

Essentially then if we are given a set of people we can tell if an odd conjunction is possible and, if it is possible, we can determine the unique interval in the year when it occurs. I shall mention in passing here that, obviously, if an odd conjunction occurs, then other odd conjunctions occur at two year intervals so once we have one odd conjunction we shall have infinitely many. That suggests a related question: if there is a prime conjunction are there infinitely many? That may seem like a much stronger requirement but we shall see that it really isn't. So, for the moment, let's consider whether there are an infinite number of prime conjunctions. At the end of this article I'll return to the original question.

So let's assume you have carried out the calculation above and found that your children do have an odd conjunction. If there are going to be prime conjunctions then they must occur in the same period of the year when the odd conjunctions occur. The mathematical expression of the question therefore is: given k odd numbers a1, a2, ..., ak can we find some number n (indeed, an infinite collection of numbers n) to add to all of them making them prime? These numbers n will, of course, all be even.

As an easy test case consider divisibility by 3. Is it possible that no matter what value n we add to the set of ages we shall always find one that is a multiple of 3? Yes, indeed! The condition is simply that among the k remainders when the ak are divided by 3 all the possible remainders 0, 1 and 2 occur; if so this condition must persist when a number n is added. For example the ages 7, 9, 11 never become prime if we a positive number n to all of them as their remainders on division by 3 are 1, 0 and 2. But notice also that if only two (or one) possible remainders occurred (as, for example, 7, 9, 13) then there will be an infinite set of values n (1, 4, 7, 10, ... ) where none of a1 + n, a2 + n, ..., ak + n are divisible by 3.

A similar condition must hold for every prime p: if the remainders when a1, a2, ..., ak
are divided by p do not include every possible remainder 0, 1, ..., p-1 then there are infinitely many values of n for which every sum a1 + n, a2 + n, ..., ak + n is not divisible by p. It's convenient to give a name to this phenomenon.We shall say that a1, a2, ..., ak satisfies the p-condition if, among the remainders on dividing a1, a2, ..., aby p, at least one remainder does not occur. The point is that, when the p-condition holds, then there will be infinitely many values of n for which the set al + n, a+ n,...,ak + n contains a number not divisible by p. So if we are looking for an infinite number of prime conjunctions we want the p-condition to hold for all values of p. This seems like a strong condition to require but it isn't: it's easy to see that the p-condition almost always holds. Indeed it holds for all p>k (because then k remainders cannot exhaust the set of all possible remainders).

So here's the $64000 question. Well, actually, it's more like the $64000000000 question. If the p-condition always holds will we necessarily have a prime conjunction? This is where Dickson's conjecture enters the scene. It states: Let a1, a2, ..., ak and b1, b2, ..., bk be positive integers. Suppose that there is no prime p which divides the product (al + nb1)(a+ nb2)...(ak + nbk) for all values of n. Then there are infinitely many values of n for which all of al + nb1, a+ nb2,...,ak + nbk are prime.

Let's restate that conjecture in the special case that all the bi are equal to 1. It then states: suppose there is no prime p that divides at least one of al + n, a+ n, ... , ak + n for all values of n. Then, for infinitely many values of n, all of al + n, a+ n, ...,, ak + n are prime. To put this in the language we have been using the conjecture says: if the p-condition holds for all primes p then al, a,..., ak have infinitely many prime conjunctions.

Thus, assuming Dickson's conjecture, the bottom line on how to find a prime conjunctions (if they exist) given a set of ages a1, ..., ak on 1 January is the following:
  • Determine whether there is an interval in the next two year period when all the ages are odd. If so replace the ages by this new set.
  • For the primes p≤k see if the p-condition holds
Having made these checks there will be an infinite number of prime conjunctions and we find them by searching.

Of course the big downside of all of this is that we don't know whether Dickson's conjecture is indeed true! A proof of it is not likely to be found any time soon. Notice that the case k=2 and with n and n+2 is the twin primes conjecture: whether there are infinitely many primes differing by 2. The twin primes conjecture is a famous unproven conjecture and widely thought to be true. Clearly Dickson's conjecture is an even tougher nut.

Finally, let's return to the original question: does there exist at least one prime conjunction? One case that may arise is when one of the primes occurring in the conjunction is 2: it's easy to check such cases. So let's consider just odd primes again.  We shall need the condition that odd conjunctions exist just as before. Also, we can rely on Dickson's conjecture if the p-condition holds for all odd primes. So the only cases where we might have a prime conjunction not covered by the analysis above is when the p-condition fails for one or more primes. But such a prime p is necessarily no more than k so there are only a finite number of primes to consider. Here, in any prime conjunction, one of the terms must be divisible by p and so must be p itself. So the prime conjunctions in question must have some prime no more than k and these can be inspected on a case by case basis.

For example, 2, 5, 7 is a prime conjunction which never reoccurs. And 3,5,7 is another because the 3-condition fails.