6
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Primes are plentiful; it's really, really, really hard for a relatively slow growing sequence like a polynomial to miss the primes so often. $\endgroup$ – Excluded and Offended Mar 29 '18 at 21:35
  • 1
    $\begingroup$ $M=10^6+1$ works with $f=X^5-(10^6+1)X^4+2$ $\endgroup$ – Mastrem Mar 29 '18 at 21:41
  • 1
    $\begingroup$ @Shalom $12$ is the smallest $x$ giving a prime. $\endgroup$ – Peter Mar 29 '18 at 22:41
  • 1
    $\begingroup$ For what is worth, with $M=8$ the record is $6-3 x-6 x^2+7 x^3+5 x^4+6 x^5$. The first prime value comes at $x = 827$. $\endgroup$ – Julián Aguirre Mar 30 '18 at 17:12
  • 1
    $\begingroup$ With the problem changed to the first $10^4$ values, the estimate I was making drops to $M= 10^{18}$. But I know this time I'm outside the domain where my estimates are good, because the size of $x^5$ is no longer negligible as compared to the size of $M$. $\endgroup$ – Excluded and Offended Mar 30 '18 at 20:45
0
$\begingroup$

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$.

|cite|improve this answer
$\endgroup$

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.