0

Let $b$ be any prime. Consider a set of $b-1$ buckets. Consider all prime numbers (except $b$) up to some $N$. Let us do the simple hash wherein each prime $x$ less than $N$ is assigned to the $x \bmod b$-th bucket.

  1. It is found that as $N$ increases, the number of primes getting assigned to the $b-1$ buckets get very close to each other very rapidly. Can this rapid reduction in the range of numbers of primes hashing to each bucket be quantified as a function of $N$ and $b$?

Note: If $b$ is not a prime, then, some of the buckets do not receive any of the primes (for example, if $b = 8$, for any prime $x$, $x \bmod 8$ can never be $2$ and bucket number $2$ remains empty) but even then, those buckets with non-zero numbers of primes tend to have very nearly equal numbers of primes (from the comment below from Pedraig O'Cathain, I understand, the numbers of primes in each bucket getting close follows from the 'prime number theorem for arithmetic progressions').

  1. Consider the special case $b =7$ and a specific value of the remainder, say $3$. Only for those primes that gave hash value (remainder) $3$, we looked at the buckets into which the next higher prime would go. It was found that for primes immediately greater than those that hash to $3$, their distribution among the buckets is always uneven (i.e., if a prime hashes to $3$, the next prime is not equally likely to hash to each possible value $1$ to $6$) and never seems to equalize among the buckets even if we go to very large $N$. If bucket $b_i$ gets more primes than bucket $b_j$ for some value of $N$, then $b_i$ continues to get more primes for larger values of $N$; however, the ratio of number of primes in $b_i$ to number in $b_j$ reduces with $N$ but never quite gets to $1$ it seems. Have these phenomena been quantified?

Note: Also checked numerically the buckets to which the second prime after a prime that hashes to bucket 3 goes. Now, the range of probabilities among the 6 possible buckets is much reduced but for even fairly large N, they don't quite equalize.

  1. Is there some hash function for primes that has the property: if any prime hashes to a particular bucket, the next higher prime is equally likely to hash to any of the buckets?
Nandakumar R
  • 5,473
  • 7
    Granville and Martin wrote a paper where this is discussed: https://arxiv.org/pdf/math/0408319.pdf

    They explain many details of the behaviour of these 'prime races'. Some buckets are fuller than others most of the time, as you have observed. They can quantify by how much some buckets lead, and how often. The tie all this to the Riemann hypothesis - it's a really nice paper.

     – Padraig Ó Catháin Mar 20 '24 at 18:50
  • 4
    Writing $b$-1 instead of $b-1$ is definitely incorrect usage in MathJax or LaTeX. That has been edited above. – Michael Hardy Mar 20 '24 at 19:21
  • 2
    As for the question of dependence of a prime on the previous prime, see Robert J Lemke Oliver and Kannan Soundararajan, Unexpected biases in the distribution of consecutive primes, Proc Nat Acad Sci 113 #31 (2016) E4446-E4454, available at https://www.pnas.org/doi/full/10.1073/pnas.1605366113. Abstract next comment. – Gerry Myerson Mar 21 '24 at 06:00
  • 3
    Prime numbers ... are well known to be very well distributed among the reduced residue classes $\bmod q$. Surprisingly, the same does not appear to be true for sequences of consecutive primes, with different patterns occurring with wildly different frequencies. We formulate a precise conjecture, based on the Hardy−Littlewood conjectures, which explains this phenomenon. In particular, we predict that all patterns do occur their fair share of the time in the limit, but that there are secondary terms only very slowly tending to zero that create the observed biases. – Gerry Myerson Mar 21 '24 at 06:03
  • The paper is discussed at https://mathoverflow.net/questions/233633/could-this-unexpected-bias-in-the-distribution-of-consecutive-primes-have-any-im and https://mathoverflow.net/questions/357379/how-to-explain-this-prime-gap-bias-around-last-digits and https://mathoverflow.net/questions/372572/the-bias-of-consecutive-prime-numbers-towards-being-incongruent-modulo-3 and https://mathoverflow.net/questions/234108/why-such-an-interest-in-studying-prime-gaps/234149#234149 and several other places on this website. – Gerry Myerson Mar 21 '24 at 06:07
  • Thanks to Padraig O'Cathain, Michael Hardy and Gerry Myerson. From these comments, questions 1 has a ready answer and 2 is discussed in the paper by Oliver and Soundararajan. That leaves question 3. – Nandakumar R Mar 21 '24 at 09:51
  • 1
    Doesn't the paper of Oliver and Soundararajan answer question 3, at least conjecturally? "...we predict that all patterns do occur their fair share of the time in the limit...." – Gerry Myerson Mar 22 '24 at 00:29
  • 1
    thank you again. what i gather from the conjecture is: if we allow N to be large enough, the number of entries in the 6 buckets will equalize even when we hash only those primes immediately following primes which give remainder 3 modulo 7(say). numerically, i could go up to N = 100 million and there is no clear indication that they do. but then, if N gets really large, things could be different. One can always ask for other hash functions for which one doesn't have to wait as long. – Nandakumar R Mar 22 '24 at 10:37

0 Answers0