3
$\begingroup$

In my previous MO question (see here), I solved the case for arithmetic progressions $f_k(x)=q_k x+1$. The solution is this:

The list of sequences $f_k(x)$, each one corresponding to a specific $k$, has prime density achieving maximum asymptotic growth as $k\rightarrow \infty$ if for instance $q_k=k!$. In that case, the prime density attached to the $k$-th sequence is aymptotically $\log\log k$ times higher than that corresponding to $k=1$. The prime density $\pi_{f_k}(n)$ is the number of primes in the sequence $f_k$, among the first $n$ terms of the sequence. For $k=1$, we have $\pi_{f_1}(n) \sim n/\log n$. Of particular interest is the fact that $\log\log k\rightarrow\infty$. Among other things, it helped generate very large primes very quickly, for instance $(k=60, x=3)$ yields a prime with $82$ digits.

Now let $f_k(x) = q_k x^2 +1$ with $x=0, 1, 2\dots$ and $k$ fixed, be a sequence of positive integers, with $q_k$ an integer sequence to be chosen later. This is a particular case of quadratic progression.

I am wondering if such nice results are replicable for quadratic or higher order progressions, with the focus here bein on simple quadratic progressions. Just like the Prime Number Theorem for arithmetic progressions (see here) is the core result needed for arithmetic progressions, for quadratic progressions the core result used is Hardy and Littlewood's conjecture F (see here). I don't know if that conjecture has been proved recently, but this paper seems to provide some kind of a proof. Anyway, below is the conjecture in question, as it is needed to answer my question formulated in section 3.

1. Main result needed to answer my question

Conjecture F states that the prime density for the sequence $f(x)=ax^2+bx+c$ with $a,b,c$ fixed integer parameters and $x=0,1,2,\dots$, is

$$\pi_f(n)\sim\epsilon_f \cdot A_f \cdot B_f\cdot \frac{n}{\log n}$$

where

  • $\epsilon_f=\frac{1}{2}$ if $a + b$ is odd, and $1$ otherwise.
  • $A_f$ is the product of $\frac{p}{p-1}$ over the finite number of odd primes $p$ that divide $\gcd(a,b)$. If $b=0$, then $\gcd(a,b)=a$ (see here why).
  • $B_f$ is the product of $1-\frac{(\Delta/p)}{p-1}$ over the infinite number of odd primes $p$ not dividing $a$, and $(\Delta/p)\in\{0,1,-1\}$ is a Legendre symbol with $\Delta=b^2-4ac$.

Note that some sources (here and here) mention $\sqrt{n}/\log n$ as the main asymptotic factor in the prime density $\pi_f(n)$, while others (like myself, see also here) mention $n/\log n$ which is the one that makes sense to me and backed by empirical evidence.

2. Goal

The goal is to build a list of sequences $f_k(x)=q_k x^2+1$ of increasing prime density as $k$ increases, hoping that we are able to find a tractable, simple increasing sequence of integers $q_k$ such that

$$\lim_{k\rightarrow\infty} \lim_{n\rightarrow\infty}\frac{\pi_{f_k}(n)}{\pi_{f_1}(n)}=\infty.$$

An idea is to use $q_1=1,q_2=4$ and $q_{k+1}=p_{k-1}^2q_k$ if $k>1$, where $p_k$ is the $k$-th Gaussian prime. A Gaussian prime is a prime congruent to $3$ modulo $4$. With such a choice, if $k>2$, then none of the $f_k(x)$'s is divisible by a prime (Gaussian or not) less than the $p_{k-2}$-th Gaussian prime, and the factor $A_{f_k}$ in conjecture F slowly grows to $\infty$ as $k$ increases, as desired. But the factor $B_{f_k}$ is much more difficult to handle. Could it slowly decrease to zero? Infinitely faster than $A_{f_k}$ grows to $\infty$? The issue is that unlike for arithmetic progressions where divisibility by a prime $p$ exhibits a periodicity $p$ for any sequence $f_k(x)$, in the case of quadratic progressions, there can be a double periodicity, thus erasing the gains of not being divisible by any Gaussian prime.

Another approach is to define $q_k$ as a product of $k$ increasing primes $p_1,\dots,p_k$, and choose these primes sequentially as you iterate over $k$, in such a way as to maintain $B_{f_k} > \delta$ at all times, where $\delta>0$. Whether this is possible or not, is probably unknown. One simple strategy is to choose the newly added $p_k$, for a given $k$, such that the first three Legendre terms $(\Delta/p)$ appearing in $B_{f_k}$ are equal to $-1$ to give $B_{f_k}$ a good head start and a better chance that it won't be too small.

In this article dealing with a different quadratic progression, the author managed to achieve a prime density more than five times the baseline, but I believe it is possible to do much better. Yet the $n/\log n$ factor can not be improved, say to $n/\sqrt{\log n}$, only the constant $\epsilon A_{f_k} B_{f_k}$ can be improved.

3. My question

Is there a strategy that could lead to $A_{f_k} B_{f_k}\rightarrow \infty$ as $k\rightarrow \infty$? This would lead to quadratic progressions with very high prime densities. Put it differently, how do we build such sequences, maybe using my methodology, or by other means?

4. Progress made so far

The sequence $398x^2 -1$ has $414$ primes among its first $1000$ terms. The number $398 \cdot 2^4\cdot 5^6 \cdot 29^2 \cdot x^2 -1$ is prime for $x$ as low as $x=1$. A number this large, randomly selected, has about a 4% chance to be prime. So including these prime-producing sequences as test numbers when performing primilaty testing, will speed up the discovery of large primes by an order of magnitude.

Also, see table below.

enter image description here

$\endgroup$
1
$\begingroup$

OEIS A331947 and the X-Refs given there might be useful. 398 is one of its terms.

$\endgroup$
2
  • $\begingroup$ Thank you, very interesting. Yes there is definitely something special about $398$ like there is something special about $163$ for arithmetic progressions. $\endgroup$ – Vincent Granville Oct 30 '20 at 17:47
  • $\begingroup$ I noticed you are the author for the OEIS entry A331947. Congratulations! Maybe one day, I'll have one of my sequences listed there as well. $\endgroup$ – Vincent Granville Oct 31 '20 at 14:32

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.