I was reading Martin Gardner's Mathematical Games column on the Ulam spiral which appeared in the March 1964 issue of Scientific American. (The spiral actually featured on the cover of that issue.) Gardner makes the following statement:

The grid on the cover suggests that throughout the entire number series expressions of this form are likely to vary markedly from those "poor" in primes to those that are "rich," and that on the rich lines an unusual amount of clumping occurs.

By "this form" Gardner means the form $4x^2+bx+c$. I'm curious - and a little bit skeptical - about his last statement concerning clumping. I know that the existence of prime-rich and prime-poor polynomials is a longstanding conjecture, going back to Euler's discovery that polynomials such as $x^2-x+41$ generate unusually many primes, and that Hardy and Littlewood and also Bateman and Horn made concrete proposals as to what the density of primes in such polynomials ought to be.

My question is whether there is any evidence, either numerical or heuristic, that there should be a large amount of clumping in the primes of the form $x^2-x+41$. Famously, the first 40 values of $x$ all give primes, but if one goes to higher values of $x$ are there more long clusters of primes than one would expect if the primes were randomly distributed?

Rephrasing the question: I am aware of the conjecture that $x^2-x+41$ has more primes than other, similar lines. The question is whether there is a conjecture saying that $x^2-x+41$ has more dense clusters of primes than expected.


You will find this paper of interest:

Fung and Williams, "Quadratic polynomials which have a high density of prime values", Mathematics of Computation, 55:191, July 1990, 345-353.

  • $\begingroup$ Thanks for the suggestion. That's a very nice paper, which I actually had run across previously. I'll have to take a closer look so see whether they address the clumping issue. $\endgroup$ Nov 21 '10 at 6:04

It is easy to check numerically. For $x^2-x+41$ I found the following values:

x $\leq$ - number of primes - number of expected primes - ratio

$1000000 - 261082 - 39313 - 6.64$

$5000000 - 1157818 - 174318 - 6.64$

For $x^2-x+43$ :

$1000000 - 49233 - 39313 - 1.25$

$5000000 - 219098 - 174318 - 1.25$

For $x^2-x+45$ :

$1000000 - 32060 - 39313 - 0.81$ $ 5000000 - 141501 - 174318 - 0.81$

For the expected number of primes I summed up the probabilities that a number x (that is choosen randomly) is prime, $\frac{1}{ln(x)}$. Not only are there much more primes in $x^2-x+41$ than the other two polynomials, the ratio as I calculated it looks like it's converging. Withoug having read the whole paper Matthew Conroy linked, I'm pretty sure that the ratios are in fact the Hardy-Littlewood constants.

Edit: I see what you mean now. I'm trying to find a mathematical definition of "clumping", but it is all somewhat vage...

Edit2: Perhaps this is an approach: We start small with the number of expected "twinprimes", which in our case means $f(x)=x²-x+41$ is prime for consecutive integers. The probability should be about $\sum \frac{6.64^2}{\ln{f(x)}\ln{f(x+1)}}$. The $6.64$ is due to the fact that our polynomial has about that much more primes than normally expected.

$1000000 - 69152 - 68885 - 1.003870966737562$

$2000000 - 124384 - 123599 - 1.0063466049598313$

$3000000 - 175873 - 174474 - 1.008017081247298$

$4000000 - 225335 - 223075 - 1.0101310763434574$

$5,000,000 - 273080 - 270083 - 1.011093447429278$

It is pretty close to what I expected. Perhaps you need to look at bigger clumps to see a big difference.

$100,000,000 - 3723447 - 3678470 - 1.0122270933045168$

$200,000,000 - 6877502 - 6797647 - 1.0117473483885233$

  • $\begingroup$ Yes, I don't really have much doubt about the existence of prime-rich and prime-poor polynomials, and I have done such numerical experiments myself. But my reading of Gardner is that he's making an additional claim in the last part of the quoted text. I'm not sure how to make this precise, but I think that by "clumping" he means to say that density on the prime-rich lines has more variance from point to point than expected. I'm not sure what "expected" means in this context. My question is whether there are conjectures or experiments about this question. $\endgroup$ Jun 26 '14 at 14:52
  • $\begingroup$ Thanks for your edits. This looks promising. Would it be possible to elaborate on what you meant by "It is pretty close to what I expected."? The ratio looks very close to $1,$ which is what would happen if $f(x+1)$ being prime were independent of $f(x)$ being prime. This isn't my field, and I'm a bit confused about the right way to think about modeling primality probabilistically. (After all, it's really deterministic.) If the ratio really is $1$ asymptotically, then I wouldn't expect to see the ratio getting farther from $1,$ which is what your data show. $\endgroup$ Jun 29 '14 at 15:27
  • $\begingroup$ I expected it to be 1 since I expected it to be independend. But it is only close to 1, and the trend isn't what I expected. I will let it run for a couple hours and see where we end up. $\endgroup$ Jun 30 '14 at 9:02
  • $\begingroup$ Another thing to remember is the constant 6.64(1967462449105) I use in the sum is an approximaion as well. So if it is not that correct, the ratios will not be 100% correct as well. $\endgroup$ Jun 30 '14 at 9:25
  • $\begingroup$ I think the constant is actually closer to 6.6395, but I don't have high confidence in that. This was obtained using Hardy and Littlewood's formula, but I don't have a fast-converging method, hence my doubts. If correct, however, this would make things worse, I believe? $\endgroup$ Jun 30 '14 at 14:51

Clumps of primes from such quadratic equations should behave similarly to variations in the gaps between all primes. In general, richer functions in primes are more likely to find groups. There are other quadratics that generate streaks of consecutive outputs that are prime, such as:

2n^2 - 272431: Prime for n = 371 to 393 (23 in a row) 2n^2 + 144251: Two streaks, n = 34 to 50 (17) and n = 583 to 602 (20). n(n+1) - 1776433: Prime for n = 1424 to 1443 (20); my JVM has calculated the prime density of this one at about 8.32 (versus Euler's ~6.64). Its smallest dividing primes are 41, 59, 97, and 101. It's nowhere near the records for the richest functions, though.

  • $\begingroup$ Thank you for your answer. Is it possible to elaborate on what expectations are for the distribution of gaps (or clusters, or other quantitative measures of "clumping")? I have looked a bit at the work on quadratics with very large prime density, and at the work on finding long streaks. I remains unclear to me whether there is more clumping than number theorists would have predicted. It's been a while since I thought about this, but recent news suggests that the issue of what is expected is, itself, a subtle one. $\endgroup$ Dec 5 '16 at 15:41
  • $\begingroup$ Each prime is independent of each other prime. In other words, the solutions of a univariate polynomial of any degree modulo a prime p don't tell anything about the solutions modulo another prime. For instance, Euler's function has 39 of 41 outputs not divisible by 41; of those numbers, 41 of 43 are not divisible by $\endgroup$ Dec 5 '16 at 20:25
  • $\begingroup$ 43, which is the same proportion for all the outputs (ignoring the influence of 41). $\endgroup$ Dec 5 '16 at 20:26
  • $\begingroup$ A function has to get "lucky" to generate many primes in a row; Euler's simply produces a lot that are too small to be divisible by any primes that divide the function (other than the outputs themselves); 41 is the minimum dividing prime, 1681 is the smallest possible composite (41<sup>2</sup>). $\endgroup$ Dec 5 '16 at 20:30
  • $\begingroup$ 41^2, that is. The example of 2n^2 + 144251 is pretty unusual, the arguments of 583 to 602 simply don't give multiples of the first few possible factors (beginning with 67 and 73). The real drawback is that the mean number of roots modulo each prime seems to converge to 1 in any case, so the prime density can't keep growing as it's calculated through more primes. $\endgroup$ Dec 5 '16 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.