October 1st 2005

Admissible Prime Sets

main page - page 1 - page 2 - page 3

1. Introduction

This topic is based on 2 conjectures made by Hardy-Littlewood in the early 20th century. The first one is the k-Tuple Conjecture. The second one claims that the prime counting function is convex. These conjectures are incompatible with each other, which was proved in 1972 (see counter-example in this paper on page 3). It is possible that both conjectures are wrong, but both cannot be true at the same time.

An Admissible Set is a set which fullfills the requirements for the k-Tuple Conjecture, i.e. a set of natural numbers 0 = a1 < a2 < ... < ak so that (m + a1)(m + a2)...(m + ak) does not have a permanent divisor independant from m. The construction of such a set is easy:
Take the set of natural numbers [0, n[. For each prime number p < n eliminate a residue class which does not hold 0 or n-1. If 0 and n-1 are not in the same residue class modulo p, there are p-2 possibilities, otherwise p-1 possibilities. The remaining set obviously satisfies the condition of the k-Tuple Conjecture.
k is the size of such a set, n the length. While finding any set for a given length n is trivial, finding a set with maximal size k requires exhaustive search. Let r(n) = max k over all possible sets. A necessary requirement for a counter-example for the second Hardy-Littlewood conjecture is that r(n) > p(n), where p(n) is the prime counting function.

I had two goals:
  • Find the smallest number N with r(n) > p(n)
  • Find r(n) for all n < N
  • In September 2004, I found that 447 = r(3159) > p(3159) = 446. I have been calculating r(n) for 2048 < n < 3159 since then (n < 2049 has already been calculated exhaustively).
    Without proof, here are my results.

    main page - page 1 - page 2 - page 3