We got a cubic polynomial which is unexpectedly prime rich.

Let $f(x)=29160 x^3 + 30132 x^2 + 8046 x + 643$ and

$\pi_f(n)$ the number of primes values of $f(x)$ for $x \in [1,n]$.

Let $F(n)=\frac{\pi_f(n)}{\frac{n}{\log{n}}}$.

$F(n)$ is greater than one on $F(10^n)$ experimentally increasing for $n \ge 4$.

Here is some data

  n   \pi_f(n) F(n)
10^3  200     1.381551055796
10^4  1455    1.340104524122
10^5  11772   1.355301585736
10^6  100279  1.385405583242
10^7  877710  1.414701373380
10^8  7807058 1.43811322967 #pseudoprimes according to pari/gp

In the range $[10^{100},10^{100}+10^4]$ there are $28$ primes while $f(n)$ is prime $67$ times. (Independent verification will be appreciated).

Maybe this is just the law of small numbers, but $f$ appears more prime rich than the naturals, which surprises us.

Q1 How to explain this experimental data? (Especially more primes values in the large range).

Q2 What is the constant $C$ in Bateman–Horn conjecture?

If someone tests experimentally, for large numbers pseudoprimality tests are significantly faster than deterministic tests and will be accepted.

If $f$ were linear, congruences likely would explain this.

  • 5
    $\begingroup$ For polynomial, say, $f(x)=6x+1$, such ratio $F(n)$ tends to 3. I mean that the reason is likely in behaviour of $f$ modulo small primes. $\endgroup$ – Fedor Petrov Aug 13 '15 at 10:19
  • $\begingroup$ @FedorPetrov You might be right, but shouldn't the degree decrease the ratio enough for large values? $\endgroup$ – joro Aug 13 '15 at 10:21
  • 1
    $\begingroup$ Degree 3 makes values of order $n^3$, that is, probability of being prime becomes 3 times less, where $3=\log(n^3)/\log(n)$. Small primes give another factor. Total factor may become about $1.5$, why not? $\endgroup$ – Fedor Petrov Aug 13 '15 at 10:56
  • $\begingroup$ @FedorPetrov What ratio F(n) do you expect for $f(x)=6x^2+1$ and $f(x)=6x^3+1$? Do you expect $primorial(k)x^3+1$ to give increasing ratio as $k$ gets larger? Limited numerical evidence suggests for $k=7$ the ratio is smaller at 10^n. $\endgroup$ – joro Aug 13 '15 at 11:08
  • 2
    $\begingroup$ For $f(x)$ of degree $d$ I expect that $F(n)$ tends to $d^{-1}\prod_p (1-n_p/p)/(1-1/p)$, where $n_p$ denotes the number of roots of polynomial $f(x)$ modulo $p$. $\endgroup$ – Fedor Petrov Aug 13 '15 at 11:37

The expected constant in the Bateman-Horn conjecture is $$\frac1d \prod_p\frac{1-\frac{n_p}{p}}{1-\frac1p},$$ where $n_p$ is the number of roots of $f(x)$ modulo $p,$ and $d$ is the degree of $f(x).$ For the particular polynomial in question, this converges quite rapidly, and when the product is taken over the first 10000 primes, the constant is approximately $1.6235,$ which does not disagree with the experimental result.

For posterity, here is the Mathematica program:

f[x_] := 29160 x^3 + 30132 x^2 + 8046 x + 643
nn[p_] := Length[Solve[ff[x] == 0, x, Modulus -> p]]
rat[p_] := (1 - nn[p]/p)/(1 - 1/p)
bh[n_] := Product[rat[Prime[k]], {k,1,n}]/3
  • $\begingroup$ Thanks. This might be sage bug or my mistake, but I get quite lower constant in sage. $\endgroup$ – joro Aug 13 '15 at 17:11
  • $\begingroup$ Did you compute infinite or finite product? If finite to what bound? $\endgroup$ – joro Aug 14 '15 at 6:34
  • $\begingroup$ Cohen has a draft preprint, on fast computation of Hardy-Littlewood constants. Maybe it is already in GP/PARI? math.u-bordeaux1.fr/~cohen/hardylw.dvi $\endgroup$ – ABCDveve Aug 14 '15 at 7:52
  • $\begingroup$ @joro first 10000 primes. $\endgroup$ – Igor Rivin Aug 14 '15 at 10:59
  • 1
    $\begingroup$ Oh, it was my mistake, now I confirm your result. $\endgroup$ – joro Aug 14 '15 at 11:50

When calculating the chance of f(n) being prime versus arbitrary integers of similar size, the factor of 1/d in the Bateman-Horn formula, for d being the degree of the polynomial, is omitted. In other words, if f(n) is roughly 10^19, compare its prime density with integers of size 10^19. This puts the density constant at around 4.87, which may qualify as 'rich' in primes.

A cubic example I found would be n^3 + n^2 - 349, which has a relative density of about 6.89 through primes < 310 (not accounting for its degree). This is impressive, although I have discovered dozens of quadratic equations with densities higher than 9 times that of arbitrary integers of the same size.

If you build a sieve, however, I'm sure you could find cubic functions with densities above 8.


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.