Prime-generating polynomials.

[mathbalarka]

Given that $k^2 + k + n$ is always prime for all positive integer $k$ in the interval $\left (0, (n/3)^{1/2} \right )$. Find the largest interval for which the same can be stated.

This easily follows from Heegner-Stark theorem, but can you show the same bypassing it, without going through the finititude of class-1 numbers?

 

[mathbalarka]

One can find my solution below :

Spoiler

Let $m$ be the least integer for which $f(m)$ is composite, where $f(x) = x^2 + x + n$.

As the hypothesis go, $m > \sqrt{n/3}$, hence $n < 3m^2$.

Let $p$ be the smallest prime dividing $f(m)$. We get then that $p \leq \sqrt{f(m)}$.

$$p^2 \leq f(m) < m^2 + m + 3m^2 < (2m + 1)^2$$

Hence, $p \leq 2m$.

Now, consider the product $\prod_{k = 0}^{m-1} \left [ f(m) - f(k) \right ]$. If we factor out $f(m) - f(k)$ as $(m - k)(m + k + 1)$, this gives :

$$\prod_{k = 0}^{m-1} \left [ f(m) - f(k) \right ] = \prod_{k = 0}^{m-1} \left [ (m - k)(m + k + 1) \right ] = (2m)!$$

As $p \leq 2m$, $p$ divides $(2m)!$, hence $p$ divides in turn on of the factors $(m - \mathcal{l})(m + \mathcal{l} + 1)$, implying $p \leq m + \mathcal{l} + 1$ for some $\mathcal{l} \leq m - 1$.

Also, as a consequence, $p$ divides $f(m) - f(\mathcal{l})$, and since $p$ also divides $f(m)$, p must divide $f(\mathcal{l})$. By the definition of $m$, $f(\mathcal{l})$ is prime, hence $ p = f(\mathcal{l}) $. This can equivalently be stated as $p - \mathcal{l} = \mathcal{l}^2 + n$.

Combined together with the inequality before, we have :

$$m + 1 \geq p - \mathcal{l} = \mathcal{l}^2 + n \geq n$$

Hence, the largest possible interval for which $f(x)$ is prime in general, is $ ( 0, n - 1) $. $\blacksquare$