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.

  • $\begingroup$ It was incorrect. $\endgroup$ – Pedro Tamaroff Aug 20 '16 at 6:08
  • 1
    $\begingroup$ One may first think about the case $n=1$. $\endgroup$ – 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.

  • $\begingroup$ All outputs composite is much more interesting than the conjecture. $\endgroup$ – Lehs Aug 20 '16 at 7:28
  • $\begingroup$ 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. $\endgroup$ – Greg Martin Aug 20 '16 at 8:52
  • $\begingroup$ What I ment was that $\notin\mathbb P$ is changed to 'composite'. $\endgroup$ – Lehs Aug 20 '16 at 14:06

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.