# A conjecture about integer polynomials and primes

Conjecture:

For all sets of non constant polynomials $\{f_1,\dots,f_n\}\subset \mathbb Z[X]$, it exists $m\in\mathbb N$ such that $f_k(m)\notin\mathbb P$, for all $1\leq k\leq n$. Where $\mathbb P$ is the set of primes.

Can this be proved?

The original conjecture with $\mathbb R[X]$ seems too difficult and may depend on an open conjecture.

• It was incorrect. – Pedro Tamaroff Aug 20 '16 at 6:08
• One may first think about the case $n=1$. – Fei Li Aug 20 '16 at 6:24

The conjecture is true, even allowing for polynomials in $\Bbb C[x]$.

As a first step, we show that if $f(x)\in\Bbb C[x]$ takes infinitely many integer values on inputs $x\in\Bbb N$, then its coefficients must actually be (real) rational numbers. (This reduces the problem from $\Bbb C[x]$ to $\Bbb Q[x]$, since any polynomial in $\Bbb C[x] \setminus \Bbb Q[x]$ only takes finitely many prime values and thus can be deleted from the set of polynomials without changing the conjectured property.)

Indeed, let $f(x) \in \Bbb C[x]$ have degree $d\ge1$ (constant polynomials being trival for this fact), and write it as $f(x) = c_d x^d + c_{d-1}x^{d-1} \cdots + c_1 x + x_0$. Suppose that $n_0,\dots,n_d\in\Bbb N$ are such that $v_0=f(n_0),\dots,v_d=f(n_d)$ are all integers. The coefficients can be recovered from these outputs, since they satisfy the linear system of equations \begin{align*} n_0^d c_d + n_0^{d-1} c_{d-1} + \cdots + n_0 c_1 &= v_0-c_0 \\ n_1^d c_d + n_1^{d-1} c_{d-1} + \cdots + n_1 c_1 &= v_1-c_0 \\ \vdots& \\ n_d^d c_d + n_d^{d-1} c_{d-1} + \cdots + n_d c_1 &= v_d-c_0. \end{align*} The coefficient matrix on the left-hand side is a Vandermonde matrix, so it is invertible; moreover, all its entries are integers, and so its inverse has rational entries. Therefore the vector of $c_j$s, being the product of this inverse matrix with the vector of $(v_j-c_0)$s, has rational entries.

Now let $f_1(x),\dots,f_k(x)\in\Bbb Q[x]$, and choose a huge common denominator $A$ for their coefficients, so that $g_1(x)=Af_1(x),\dots,g_k(x)=Af_k(x)\in\Bbb Z[x]$. We will show that there is a composite number $B$ with the following property: there are infinitely many integers $n$ such that $AB$ divides each $g_j(n)$. In particular, for these infinitely many integer inputs, each $f_j(n)$ is an integer multiple of $B$ and therefore not prime.

We use the following fact about polynomials with integer coefficients: if $g(n_0)=v\ne0$, then $g(n_0+mv)$ is a multiple of $v$ for all integers $m$. (Verify by expanding each term with binomial coefficients, or just use congruences modulo $v$.)

So, let $n_0$ be an integer with each $|g_j(n_0)|\ge2$ (a nonconstant polynomial takes the values $-1,0,1$ only finitely many times). Let $v_j = g_j(n_0)$ for each $j$, and let $V=v_1v_2\cdots v_k$. Then each $g_j(n_0+mV)$ is a multiple of $v_j$ for all integers $m$. Moreover, with finitely many exceptions, $g_j(n_0+mV)$ is a proper multiple of $v_j$; and since $|v_j|\ge2$, no proper multiple of $v_j$ can be prime. Therefore all but finitely many inputs of the form $n_0+mV$ yield all composite outputs, which is (stronger than) what we wanted to show.

• All outputs composite is much more interesting than the conjecture. – Lehs Aug 20 '16 at 7:28
• Note that it's not the case that all outputs in the world must be composite—only that there exists an infinite arithmetic progression of inputs where all the outputs are positive. – Greg Martin Aug 20 '16 at 8:52
• What I ment was that $\notin\mathbb P$ is changed to 'composite'. – Lehs Aug 20 '16 at 14:06