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.

$\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$ 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
    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$ 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
    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$ Aug 13, 2015 at 11:37

2 Answers 2

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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