Let $f\in\mathbb Z[X]$, define $\operatorname{P}^+(f)$ as the number of primes $>0$ that $f$ assumes at distinct integral arguments.

Theorem: If $f\in\mathbb Z[X]$ is non constant and reducible of degree $n$, then $\operatorname{P}^+(f)\leq n$. And for all $n$ there are non constant reducible polynomials of degree n such that $\operatorname{P}^+(f)=n$.
[Acta Arith.,104.2 (2002) 117-127.]

Most polynomials are irreducible but using the theorem for an irreducibility test would be inefficient since a lot of irreducible polynomials has a fixed divisor $>1$ and wouldn't pass the test.

A conjecture related to the conjecture of Bunjakowsky states:

Conjecture: If $ f\in\mathbb Z[X]$ is non constant and irreducible, then $f(a)/d$ assumes primes for an infinit number of distinct integral arguments $a$, where $d$ is the largest fixed divisor of $f$.

Irreducibility of Polynomials Whose Coefficients are Integers Page 32.

This makes me wonder if the following hypothesis is true:

$f\in\mathbb Z[X]$ of degree $n>0$ with coprime coefficients is irreducible, iff $\;\operatorname{P}^+(d^{-1}\cdot f)> n$ or $\;\operatorname{P}^+(d^{-1}\cdot (-f))> n$, where $d$ is the greatest fixed divisor of $f$.

$\operatorname{P}^+$ is extended above and defined even for integer-valued polynomials with rational coefficients. Proofs or counter-examples?

With a test program using the hypothesis on Eisenstein polynomials $f$ with random coefficients between $-19$ and $19$ and random degree between $2$ and $5$, testing both $f$ and $-f$, resulted in no miss in $1,000,000$ polynomials. The only drawback is the risk of overflow when evaluating the polynomials for higher degrees and greater coefficients.

  • $\begingroup$ Bunjakowsky's conjecture starts with $d=1$ where $d = gcd(f(\mathbb{Z}))$. What do you get with your question assuming $d=1$ ? If $f(X)= g(X)h(X)$ is reducible and $f(n) = \pm p$ then $g(n) = \pm 1$ or $h(n) = \pm 1$. Write $g(X) = 1+g_2(X)\prod_{n \in g^{-1}(1)} (X-n)$. What happens if $g(m) = -1$ ? Do you see the problem when $d \ne 1$ ? $\endgroup$
    – reuns
    Jan 20, 2019 at 8:43
  • $\begingroup$ @reuns: No! Do you mean that the hypothesis would give false irreducible polynomials? $\endgroup$
    – Lehs
    Jan 20, 2019 at 9:18
  • 1
    $\begingroup$ @JovanRadenkovic: These two polynomials are not over $\mathbb Z$. Or what do you mean? $\endgroup$
    – Lehs
    Jan 7, 2023 at 16:30
  • 1
    $\begingroup$ @Lehs, I meant $x\cdot(x^2-8x+17)$ and $x\cdot(x^2+17)$, respectively. $\endgroup$
    – user1115547
    Jan 7, 2023 at 16:32
  • 1
    $\begingroup$ @JovanRadenkovic, You are right. $\endgroup$
    – Lehs
    Jan 7, 2023 at 20:36

1 Answer 1

  • The simplest case :

Let $f \in \mathbb{Z}[X]$. It is said irreducible iff $f(X) = g(X)h(X) \implies g(X)=\pm1$ or $h(X) = \pm1$. Let $d = gcd(f(\mathbb{Z}))$. Assume $d=1$ and $| f(n)|$ is prime more than $2 \deg(f)$ times.

If $f(X) = g(X)h(X)$ is reducible, then $f(n) = \pm p$ implies $n$ is a root of $g(X)^2-1$ or $h(X)^2-1$. But those polynomials are of degree $2\deg(g), 2 \deg(f)-2\deg(g)$, so they have at most $2\deg(f)$ roots. A contradiction. Whence $f$ is irreducible.

  • To improve the bound $2 \deg(f)$, you need to split each case : $g(n)=1,g(n)=-1,h(n)=1,h(n)=-1$ and factorize.

  • Then look at the case $d=2$, you'll have more cases and some of them will probably allow more than $\deg(f)$ prime values.

  • 1
    $\begingroup$ You are right and I have corrected the question. $\endgroup$
    – Lehs
    Jan 23, 2019 at 9:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .