Let $p(x)$ be an integer-valued polynomial of degree $n$. Is it possible to use up to $n$ consecutive values to potentially identify $p(x)$ as irreducible over the set of integer-valued polynomials?

I managed to prove that for $n=2$ there is a definite upper limit for the 3rd sequential value, but it is very difficult for higher degrees, even with induction. I encountered this question while considering some primes appearing in polynomial sequences. I have attempted to use Lagrange interpolation and binomial forms and I haven't made any progress past $n=2$.

Here is a sketch for the proof that there is an upper bound for the described polynomial with $n=2$:

We have fixed positive integers $v_1,v_2, v_1\le v_2$ and polynomial in binomial form

$$p(x) = a{x\choose 2}+(v_2-v_1)x+v_1$$

(Notice that we have set $p(0) = v_1,p(1) = v_2$.) Since we have $n=2$, we must have $p(2) = v_3$ for whatever positive integer value $v_3$ takes on, which means that we have $p(2) = a + 2v_2-v_1 = v_3$, and so we have $a = v_3-2v_2+v_1$ (which is correct by Finite Difference theory), giving us

$$p(x) = (v_3-2v_2+v_1){x\choose 2}+(v_2-v_1)x+v_1$$

This shows that only the (binomial-form) quadratic term will change in coefficient as $v_3$ changes. Now consider this value:

$$p\left(\frac 12\right)=\frac 14v_1+v_2-\frac 14v_3$$

We again have linear change in the value at this point as $v_3$ changes, and it is clear that it is possible for this value to be negative.

If $p(x)$ is composite with at least two non-constant integer-valued polynomial factors, and if $v_3$ is large enough to force $p\left(\frac 12\right)$ to be negative, then these factors are based exactly on the roots between $p(0)$ and $p(1)$, since each of these values is positive. So we would have

$$p(x) = (v_3-2v_2+v_1)(x-q_0)(x-q_1)=a(x-q_0)\cdot b(x-q_1)$$

In order for these factors to be considered "integer-valued", both $a$ and $b$ must be large enough that either the denominator of the rational $aq_0\le 2$ or the denominator of the rational $bq_1\le 2$. (For example, ${x\choose 2}={x(x-1)\over 2}$ and these factors are considered "integer-valued".) But we also notice that $q_0$ must be between $0$ and the intersection $(Q_0,0)$ of the line $y=0$ with the line segment connecting $(0,p(0))$ with $\left(\frac 12,p\left(\frac 12\right)\right)$, and this distance $Q_0$ is inverse-linear with $v_3$ (by similar triangles). But this means that $a$ must be asymptotically linear with $v_3$ and also (by the same argument for $Q_1$) that $b$ must be asymptotically linear with $v_3$, and therefore that

$$p(x) = (v_3-2v_2+v_1)(x-q_0)(x-q_1)=cv_3^2(x-q_0)(x-q_1)\tag 1$$

But $v_3$ is allowed to take on any value, and equation $(1)$ implies that $c$ must vary inverse-linearly with $v_3$, therefore there exists $N\in\Bbb N$ such that for all $v_3\gt N$ at least one of $a(x-q_0),b(x-q_1)$ cannot be integer-valued.

I'm fairly certain that this same argument applies in the same way for any given value of $n$.

  • $\begingroup$ Maximum possible value with regards to which parameters ? If $\nu_1, \nu_n$ are fixed, then $p$ is fixed and so is $p(n+1)$. $\endgroup$ – Joel Cohen Oct 19 '15 at 4:10
  • $\begingroup$ @JoelCohen: $v_{n+1}$ is the specific parameter which determines $p(x)$, and is not otherwise restricted in any way, except that $p(x)$ is composite as described. And no, $p(x)$ is not determined except by all $n+1$ points. $\endgroup$ – abiessu Oct 19 '15 at 4:23
  • $\begingroup$ Sorry, I misunderstood your question initially :) If I understand correctly, you chose the values $p(1), \ldots p(n)$ and want to know the maximal possible value of $p(n+1)$ such that $p$ is composite. Is that right ? $\endgroup$ – Joel Cohen Oct 19 '15 at 4:29
  • $\begingroup$ @JoelCohen: yes that is correct. Beyond that, the $v_1,\dots,v_n$ values are given such that they do not interfere with $p(x)$ being possibly composite... $\endgroup$ – abiessu Oct 19 '15 at 4:30
  • $\begingroup$ But what exactly do you mean by composite ? Real polynomials of degree $\ge 3$ are never irreducible in $\mathbb{R}[X]$ (although they might be in $\mathbb{Q}[X]$). $\endgroup$ – Joel Cohen Oct 19 '15 at 4:51

Here is one way to state the theorem:

Let $p(x)$ be a given integer-valued polynomial of degree $d$. There exists a value $M$ based on $d$ consecutive integral values of $p(x)$ starting at any value $a$ (i.e., $M$ is based on $p(a),p(a+1),\dots,p(a+d-1)$) such that if $|p(a+d)|\gt M$ then $p(x)$ is irreducible over the set of integer-valued polynomials.

Note: "irreducible" is used in a sense which ignores constant factors.

Proof: Let $p(x)$ be a given integer-valued polynomial of degree $d$. Suppose $p(x)$ is reducible over the set of integer-valued polynomials, having factors $q(x),r(x)$. Suppose w.l.o.g. that $d-1\ge\deg(q)\ge\deg(r)$. Consider the values $p(0), p(1), p(2),\dots,p(d-1)$. In particular, note that $q(0)\mid p(0), q(1)\mid p(1),\dots, q(d-1)\mid p(d-1)$, and this means that $q(0)$ can take on at most $\sigma_0(p(0))$ possible values, $q(1)$ can take on at most $\sigma_0(p(1))$ possible values, etc., and so there are at most


possible factors $q(x)$ of $p(x)$, as these are all the possible polynomials of degree $d-1$ passing through this set of values. Each of these polynomials $q(x)$ has a value at $q(d)$, and there is a finite set of such possible values arising from the possible polynomials $q(x)$. A finite set of integers has a maximum and a minimum element, and if we take $M$ as the greatest absolute value among this minimum and maximum, we have proven the theorem.

| cite | improve this answer | |

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.