6

For a polynomial, all coefficients of each term of it are 1, 0 or -1. Given that all roots of it are integers, how many different 2016-degree polynomials satisfy these conditions are there?

I first consider the product of all roots $x_1x_2x_3...x_{2016}$, it can be 0, 1 or -1. So there must be at least one root equaling to 0 or all roots are 1 or -1. But later I found it's hard to let all the coefficients be 1, 0 or -1 if we merely consider the combination of 1s and -1s. Is there anyone who could solve this problem or providing some hints?

YANGyu
  • 433
  • 3
    Can you show that all roots of the polynomial are $0, 1$ or $-1$? So we can factor the polynomial as $x^a (x-1)^l (x+1)^k$ for some integers $a,l$ and $k$ summing up to $2016$. What are the possible values of $l$ and $k$? – koifish Dec 07 '23 at 13:34
  • only when the constant term isn't 0, otherwise it will be any integer if we have a zero root – YANGyu Dec 07 '23 at 13:48
  • Okay, but you can factorize. If $k$ is the order of $0$ as a root, we can factorize the polynomial into $x^k f(x)$, where now $f$ is a polynomial with each coefficient being $1$, $0$ or $-1$, and the roots of $f$ are too integers. – koifish Dec 07 '23 at 13:49
  • you are right. I was thinking about using some recursive method... – YANGyu Dec 07 '23 at 13:54
  • I'll post a short answer, because I think the rest of the proof isn't that easy, but I won't work out the precise number. But it should be enough for you to work out the rest. – koifish Dec 07 '23 at 13:58
  • thank you I got a rough work already. my answer is 12. – YANGyu Dec 07 '23 at 14:10
  • @YANGyu Please show your work, even if it's rough and you're not fully certain of it. – Calvin Lin Dec 07 '23 at 14:13
  • @YANGyu I got 6... might be missing something though – koifish Dec 07 '23 at 14:14
  • 1
    we have the same answer actually. I just put a negative sign before each of your six polynomials. – YANGyu Dec 07 '23 at 14:27

2 Answers2

9

Hints (please also let me know if I make any mistakes):

As above, one can show that all the roots of the polynomial are $0, -1$ or $1$. So we can factor the polynomial into $$ x^a (x-1)^l (x+1)^k, $$ with $a, l$ and $k$ summing up to $2016$.

Now, we can do brute-forcing on the values $l$ and $k$ can take, which will determine $a$ as well. It is much faster to see which values of $l$ and $k$ fail.

If $l = 0$ and $k \geq 2$, we get a contradiction since there is a coefficient that is not $1, 0$ or $-1$. Similarly, if $k= 0$ and $l \geq 2$.

If $l \neq 0$ and $k \neq 0$ and $l \geq k$, we put $p = \min(l,k)$ and $q = l-k$. Now we can rewrite the polynomial as: $$ x^a (x^2 - 1)^p (x-1)^q. $$ Discard the $x^a$ term. We only consider the expansion of $(x^2 - 1)^p (x-1)^q$. The coefficient of $x^{2p + q - 1}$ in this expansion is $\binom{q}{1}$. Hence, $q = 1$. Using $q = 1$, one can deduce (after some calculation) that $p = 1$.

Similarly, one can conclude the same when $k \geq l$.

This leaves you with a (very) finite set of values that $(l, k, a)$ can take. They are $$ (0,0, 2016), (1, 0, 2015), (0, 1, 2015), (1, 1, 2014), (1,2, 2013), (2, 1, 2013). $$

koifish
  • 2,779
4

I'm going to expand this question to any given degree and show my procedure for calculating.

Suppose that there are $P_n$ such polynomials of $n$ degree, consider the constant term of it.

  • If the constant term is $0$, the polynomial has a root of $0$, thus, it can be produced by timing an $x$ on the polynomials of degree $n-1$. $(P_{n-1}\in P_n)$
  • If the constant term is not $0$, all roots must be ether $1$ or $-1$, otherwise there will be fractions.

In the second condition, suppose the # of roots of $1$ is a and # of roots of $-1$ is b. Considering the second coefficient of the polynomials, we will have $$a=b\quad or\quad|a-b|=1$$ Now consider the third coefficient for odd $n$ and even $n$ respectively,

  • When $n=2k$, it can only be $a=b=k$, |the third coefficient|$=|2\binom k2-k^2|=|k(k-1)-k^2|=k$. Thus, only when $k=1$ will we have additional polynomials. $$x\quad-x\quad x+1\quad x-1\quad-x+1\quad-x-1\quad (n=1)$$ $$P_1=6$$ Besides timing an $x$ on each of four above, we have two additional ones: $$x^2-1\quad-x^2+1$$ $$P_2=8$$
  • When $n=2k+1$, it can only be $|a-b|=1$, we only consider $a=k+1\quad b=k$ because $b-a=1$ is symmetric. |the third coefficient|$=|\binom{k+1}2+\binom k2-k(k+1)|=k^2$. $k=1$ is the biggest value for k if we want additional polynomials. Besides timing an $x$ on each of the previous eight ones, we have $$x^3-x^2-x+1\quad x^3+x^2-x-1\quad -x^3+x^2+x-1\quad -x^3-x^2+x+1$$ $$P_3=12$$

For $n>3$, no more new polynomials will be produced. $$P_1=6\\P_2=8\\P_n=12$$ for all $n\ge3$ and $n\in\Bbb N$.

YANGyu
  • 433