How can I construct polynomials with "small" coefficients generating a prime "late"?

Question

Let $f(x)$ be a polynomial with degree $5$, integer coefficients and positive leading coefficient. Let $M$ be the maximum of the absolute values of the coefficients. Assume the smallest non-negative integer $n$ such that $f(n)$ is prime is greater than $10\ 000$, but that such an $n$ exist.

• Can I construct polynomials with the desired property and "small" $M$ ?
• Can the smallest possible $M$ be determined efficiently ?

Idea : Construct an irreducible polynomial such that the $\gcd$ of its values is $1$. This should generate at least one prime due to the Bunyakovsky-conjecture. The problem is to avoid an "earlier" prime.

Motivation : Constructing "hard cases" for the bunyakovsky conjecture.

Answer 1

Let's start by generalizing the notation a little ($d$ and $B$ will be positive integers):

• $H(P)$ will denote the height of a polynomial (maximum of absolute values of its coefficients).
• $S_d(B)$ will denote the set of polynomials $P(x)$ of degree $d$ with integer coefficients for which:
  • $|P(k)|$ is prime for some positive integer $k$ but
  • $|P(k)|$ is not prime for $0\leq k\leq B$.
• Finally, define $M_d(B)=\min\limits_{P\in S_d(B)} H(P)$

In this notation, the original question was asking for $M_5(10^6)$ and the simplified version is looking for $M_5(10^4)$.

Note that the definition of $M_d(B)$ relies on $S_d(B)$ being non-empty; a property that is not as obvious as it may seem (or I might have missed the easy proof of it). Since we are only going to focus on a few specific cases, we can overlook this as a technical detail.

Using computer-assisted search, I found the polynomial $$P_5(x)=39x^5 + 6x^4 + 21x^3 - 44x^2 + 47x + 15$$ which doesn't produce a prime until $x=13076$ and thus belongs to $S_5(10^4)$. This implies $M_5(10^4)\leq 47$. Note that the search was not exhaustive, so the bound is not necessarily the optimal one.

As expected, if we let the degree increase, the coefficients of the polynomial can be lowered: For example, another search found $$P_6(x)=25x^6 + 24x^5 + 11x^4 + 10x^3 + 25x^2 - 4x + 14$$ which is non-prime until $x=10905$, so $M_6(10^4)\leq 25$ (again, the search was non-exhaustive, thus the inequality).

On the other hand, going down to degree $4$ yields polynomial $$P_4(x)=11x^4 - 146x^3 - 99x^2 + 19x + 105$$ which isn't prime until $x=10774$. Thus, $M_4(10^4)\leq 146$.