7
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 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
    Commented Aug 13, 2015 at 10:19
  • $\begingroup$ @FedorPetrov You might be right, but shouldn't the degree decrease the ratio enough for large values? $\endgroup$
    – joro
    Commented Aug 13, 2015 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
    Commented Aug 13, 2015 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
    Commented Aug 13, 2015 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
    Commented Aug 13, 2015 at 11:37

2 Answers 2

Reset to default
8
$\begingroup$

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
Improve this answer
$\endgroup$
9
  • $\begingroup$ Thanks. This might be sage bug or my mistake, but I get quite lower constant in sage. $\endgroup$
    – joro
    Commented Aug 13, 2015 at 17:11
  • $\begingroup$ Did you compute infinite or finite product? If finite to what bound? $\endgroup$
    – joro
    Commented Aug 14, 2015 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
    Commented Aug 14, 2015 at 7:52
  • $\begingroup$ @joro first 10000 primes. $\endgroup$
    – Igor Rivin
    Commented Aug 14, 2015 at 10:59
  • 1
    $\begingroup$ Oh, it was my mistake, now I confirm your result. $\endgroup$
    – joro
    Commented Aug 14, 2015 at 11:50
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .