Solutions to an Integer Polynomial

I'm not entirely sure this is right, but here goes:

Consider $g(x) = f(x) - 6$ . It is a polynomial with integer coefficients which passes through $-6$ and $-4$ at integer values, and we want to maximize its number of roots.

We can shift our $g(x)$ such that $g(0) = -4$ . This means that the constant term of $g(x)$ is $-4$ , and that any rational roots must have their numerators be factors of $4$ . This already caps the number of roots of $g(x)$ at $6$ (for $\pm 1$ , $\pm 2$ , and $\pm 4$ ). More importantly, however, if we factor out all the integer roots $r_i$ of $g(x)$ and write $g(x) = (x - r_1)(x - r_2)\ldots(x - r_n) P(x)$ , then $P(x)$ will have integer coefficients as well. This means that the constant $c$ of $P(x)$ is also an integer, so if $-4 = g(0) = (-r_1)(-r_2)\ldots (-r_n) c$ , then not only must each of the integer roots be a divisor of $4$ but their product must be as well. This limits the number of integer roots to $4$ (we could have $\pm 1$ and $\pm 2$ , for example, but we cannot take more than $4$ different members of the group above without the product exceeding $4$ ).

Finally, there is some integer $x$ such that $g(x) = -6$ . If we write: $g(x) = a_n x^n + a_{n - 1} x^{n - 1} + \ldots + a_1 x + a_0,$ then the reasoning above told us that $a_0 = -4$ . Thus, there is some $x$ such that: $a_n x^n + a_{n - 1} x^{n - 1} + \ldots + a_1 x - 4 = -6, \ \mathrm{or}$ $x (a_n x^{n - 1} + a_{n - 1} x^{n - 2} + \ldots + a_1) = -2$

Hence, since the expression in parentheses is an integer polynomial and $x$ is an integer as well, it must be the case that $x$ is a divisor (positive or negative) of $2$ . This means that $x$ is an element of the set $\{\pm 1, \pm 2\}$ , thus knocking out a prospective root from above.

This reduces the maximum number of roots to $3$ . A quick check shows that, quite conveniently, $g(x) = (x + 2) (x - 2) (x + 1)$ has the value $-4$ at $x = 0$ and $-6$ at $x = 1$ . Thus, the maximum of $3$ is indeed attainable.

Since the maximum number of roots of $g(x)$ corresponds to the maximum number of times $f(x)$ can be $6$ , we know that the maximum is indeed $\boxed{3}$ .

I'm not sure if there is a faster way.

Since the polynomial $f(x)$ takes the value $0$ for some integer, we can assume (by replacing $f(x)$ by $f(x-u)$ for some integer $u$ if necessary) that $f(0) = 0$ , and hence $f(x) = xg(x)$ for some polynomial $g(x) \in \mathbb{Z}[x]$ . There exists an integer $v$ such that $2 = f(v) = vg(v)$ , and hence $v|2$ . By replacing $f(x)$ by $f(-x)$ if necessary, we can assume that $v = 1$ or $2$ .

1. If $v=1$ then $f(x) = x\big[(x-1)h(x) + 2\big]$ for some $h(x) \in \mathbb{Z}[x]$ . If $w \in \mathbb{Z}$ is such that $f(w) = 6$ , then $w$ must divide $6$ , and $w$ cannot be $1$ . For the different possible values of $w$ , there are matching required values of $h(w)$ for $f(w)$ to be equal to $6$ : $\begin{array}{|c|c|} \hline w & h(w) \\ \hline 6 & -\tfrac15 \\ 3 & 0 \\ 2 & 1 \\ -1 & 4 \\ -2 & \tfrac53 \\ -3 & 1 \\ -6 & \tfrac37 \\ \hline \end{array}$ and so $w$ cannot be $6$ , $-2$ or $-6$ . It is not possible to find a polynomial $h(x) \in \mathbb{Z}[x]$ such that $h(3)=0$ , $h(2)=0$ , $h(-1)=4$ and $h(-3)=1$ (if $h(3)=0$ then $6$ must divide $h(-3)$ ), but $h(x) = 3-x$ satisfies three out of four of these conditions (at $x=3,2,-1$ ).

2. If $v=2$ then $f(x) = x\big[(x-2)h(x) + 1\big]$ for some $h(x) \in \mathbb{Z}[x]$ . Again, if $w\in \mathbb{Z}$ is such that $f(w)=6$ , then $w|6$ and $w \neq 2$ , and we have the following table of required values of $h(w)$ : $\begin{array}{|c|c|} \hline w & h(w) \\ \hline 6 & 0 \\ 3 & 1 \\ 2 & -5 \\ -1 & \tfrac73 \\ -2 & 1 \\ -3 & \tfrac35 \\ -6 & \tfrac14 \\ \hline \end{array}$ and so $w$ cannot be $-1$ , $-3$ or $-6$ . It is not possible to find a polynomial $h(x) \in \mathbb{Z}[x]$ such that $h(6)=0$ , $h(3)=1$ , $h(2)=-5$ and $h(-2)=1$ (if $h(6)=0$ then $8$ divides $h(-2)$ ).

Thus we deduce that the most number of integers $w$ such that $f(w)=6$ is $3$ , with $f(x) \; = \; x\big[(x-1)(3-x) + 2\big] \; = \; x(-x^2 + 4x - 1)$ achieving the value $6$ for $x=3,2,-1$ , the value $0$ at $x=0$ and the value $2$ at $x=1$ .

We can simplify this by applying the transformation

$F(x) = 6 - f(x)$

Then we need to find the largest possible number of distinct roots of $F$ , given that there must be values such that $F(n) = 6$ and $F(m) = 4$ .

Letting $r_i$ be the integer roots of $F$ , we can write it as: $F(x) = g(x)h(x)$ where $g(x) = \prod_{i}(x - r_i)^{s_i}$ and $h(x)$ is the quotient $F / g$ .

Now, $h$ has no integer roots by definition; and since dividing a polynomial with integer coefficients by a factor $x-r$ must leave a quotient with integer coefficients, $h(x)$ must be a polynomial with integer coefficients; therefore $h(m)$ and $h(n)$ must be integers.

So, if $F(n) = 6$ then $g(n) \lvert 6$ , and similarly, $g(m) \lvert 4$ .

In order that $g(m) \lvert 4$ , the most number of possible distinct factors is four, and there's only one way of doing it: $2 \times -2 \times 1 \times -1$ , i.e.

$g(x) = (x-2)(x-1)(x+1)(x+2)$

and $g(0) = 4$ . However, it can be readily checked that there is no solution to $g(n) = 6$ here, so we can rule out this case.

The next possible case is that $g$ only has three factors. In this case,

$g(x) = (x+2)(x-1)(x-2)$

gives $g(0) = 4$ and $g(-1) = 6$ .

Conveniently, $h(x) = 1$ will do here, and so we will get an $f$ with $\boxed{3}$ distinct integer roots.

It we are interested in finding an explicit form for $f$ , then taking $h = 1$ : $\begin{aligned} f(x) &= 6 - (x+2)(x-1)(x-2) \\ &= -x^3 + x^2 + 4x + 2 \end{aligned}$

with $f(0) = 2, f(-1) = 0, f(-2) = f(1) = f(2) = 6$ .

WLOG, after a change of variable, we can take $f(0) = 0$ and $f(a) = 2$ for an integer value of $a > 0$ . So we can write $f(x) = xh(x)$ , so $a | 2$ , so $a = 1$ or $2$ .

If $a = 1$ , we can write $f(x) = x((x-1)g_1(x) + 2).$ If $a = 2$ , we can write $f(x) = x((x-2)g_2(x) + 1).$ Here the $g_i$ are polynomials with integer coefficients. In both cases $f(x) = 6$ can only be true for $a|6$ , so we only need to check $x = \pm 1, \pm 2, \pm 3, \pm 6.$ There are seven values to check in each case (since $1$ in case 1 and $2$ in case 2 are already ruled out). Note that $f(x) = 6 \Leftrightarrow g_1(x) = \frac{6-2x}{x(x-1)}$ in case 1, and $g_2(x) = \frac{6-x}{x(x-2)}$ in case 2, so we first need to see for which values of $x$ this is an integer.

So we get $g_1(-1) = 4$ , $g_1(2) = 1$ , $g_1(-2) = 5/3,$ , $g_1(3) = 0$ , $g_1(-3) = 1$ , $g_1(6) = -1/5$ , $g_1(-6) = 3/7$ . Throwing out the non-integer values, we see that there are at most four solutions, and the max is attained only if there is a polynomial $g_1$ with integer coefficients whose graph passes through $(-1,4), (2,1), (3,0), (-3,1)$ . But these last two are impossible since $(x-3)$ would divide $g_1(x)$ and we'd get $-6|1$ . Hence the max in case 1 is at most $3$ .

Similarly for $g_2$ , we get that there are at most four solutions, and the max is attained only if there is a polynomial $g_2$ with integer coefficients whose graph passes through $(-1,5), (-2,1), (-3,1), (6,0)$ . Again the last two points don't work because $(x-6)$ would divide $g_2(x)$ and we'd get e.g. $-9 | 1$ . So the max in case 2 is at most $3$ .

Finally, to show that the max is in fact $3$ , we exhibit such a polynomial by setting $g_1(x) = 3-x$ and solving to get $f(x) = -x^3+4x^2-x.$ Here $f(0) = 0, f(1) = 2,$ , and $f(x) = 6$ has the solutions $x=-1, 2, 3$ .

Knowing that: $f(n)=0$ By the Polynomial remainder theorem we get that there is a polynomial $Q(x)$ with integer coefficients such that $f(x)$ can be written as

$f(x)=Q(x)(x-n)$

Now we know that $f(m)=2$ so

$f(m)=Q(m)(m-n)=2$

And dividing by $(m-n)$ we get

$Q(m)=\frac{2}{m-n}$

$Q(m)$ has to be an integer, so $m-n$ divides $2$ , it is important that $m-n$ is a constant, we will call it $k$ , knowing that the only possible values for $k$ are: $1$ , $2$ , $-1$ and $-2$ . Proceeding with calculations we obtain

$Q(m)-\frac{2}{k}=0$

Now we can consider the $LHS$ as a polynomial in the variable $m$ and we notice that the polynomial must have integer coefficients so (as before) there is a polyinomial $R(x)$ with integer coefficients such that:

$Q(x)-\frac{2}{k}=R(x)(x-m)$

$Q(x)=R(x)(x-m)+\frac{2}{k}$

Substituting this in the alternative form of $f(x)$ we found we obtain

$f(x)=\left( R(x)(x-m)+\frac{2}{k} \right) (x-n)$

Without loss of generality we can substitute $x$ with $X+n$

$f(X+n)=\left( R(X-n)(X-(m-n))+\frac{2}{k} \right) (X)$

we will call $R(X-n)$ as $R'(X)$ , and we notice that $R'(X)$ is a polynomial with integer coefficients. We recall that $k=m-n$ so

$f(X+n)=\left( R'(X)(X-k)+\frac{2}{k} \right) (X)$

The problem is equivalent to find for how many values of $X$ the $RHS$ is equal to $6$ .

$6$ can be written as the product of two numbers (where the order matters) only in the following $8$ ways:

1. $6\cdot 1$
2. $3\cdot 2$
3. $2\cdot 3$
4. $1\cdot 6$
5. $(-6)\cdot (-1)$
6. $(-3)\cdot (-2)$
7. $(-2)\cdot (-3)$
8. $(-1)\cdot (-6)$

We proceed with four cases, one for each possible value of $k$ .

• $k=2$ we get: $\left( R'(X)(X-2)+1 \right) (X)=6$ we have that when $X=2$ the other factor is $1$ (so case $2.$ has to be excluded), when $X=-1$ the other factor must have reminder $1$ when divided by $3$ (case $5.$ has to be excluded), in the same way when $x=-3$ the other factor can not be $-2$ (case $6.$ has to be excluded) and when $x=-6$ the other factor can not be $-1$ (case $8.$ has to be excluded). Therefore we are left with $4$ cases. They can not be all true! In fact we have that for $X=6$ , $R'(6)$ must be $0$ , so there is a polynomial with integer coefficients $S(X)$ such that $R'(X)=S(X)(X-6)$ Now substituting $3$ in $R'(X)$ we get that $R'(3)$ must be a multiple of $3$ . On the other hand $\left( R'(X)(X-2)+1 \right)$ can not be $2$ in this case. We can say that at most there are $3$ possible values for $X$ .

• $k=1$ we get: $\left( R'(X)(X-1)+2 \right) (X)=6$ we have that when $X=1$ the other factor is $2$ (so case $1.$ has to be excluded), when $X=-2$ the other factor must have reminder $1$ when divided by $3$ (case $6.$ has to be excluded), in the same way when $x=6$ the other factor can not be $1$ (case $4.$ has to be excluded) and when $x=-6$ the other factor can not be $-1$ (case $8.$ has to be excluded). Therefore we are left with $4$ cases. It is easy to find a polynomial such that it works for $X=-1$ , $X=2$ and $X=$ , in fact it is sufficient to show that $R'(-1)$ has to be $4$ , $R'(2)$ has to be $1$ and $R'(3)$ has to be $0$ . We can set $R'(X):=-X+3$ and we got a proper example. Using the Polynomial remainder theorem we have that all such polynomials must be of the form $R'(X)=S(X)(X+1)(X-2)(X-3)+(-X+3)$ Where $S(X)$ is a polynomial with integer coefficients. It is easy to see that there are no integer values of $S(3)$ such that $R'(-3)=1$ . So we can not have a solution for case $7.$ .

• $k=-2$ we get the same as $k=2$ changing the sign of $X$

• $k=-1$ we get the same as $k=1$ changing the sign of $X$ .

Therefore there are at most $3$ solutions and they are given by the polynomial: $f(X-n)=\left((-X+3)(X-1)+2 \right) (X)$ That is equivalent to: $f(x)=\left((-x+3+n)(x-n-1)+2 \right) (x-n)$