1000 Degree Polynomial

By (4) there exists a polynomial $P(x)$ such that $f(x)\cdot P(x)=(x-1)\cdot f(2x) \ldots (\ast_1) ,$ since $f$ is monic and has degree 1000, $P$ is linear and his leading coefficient is $2^{1000}$ . Let $n$ be the greatest integer such that $x^n$ divides $f(x)$ (note that $n$ can be 0) then we can write $f(x)=x^n\cdot g(x)$ , where $g$ is monic and $g(0)\neq 0$ . Replacing in $(\ast_1)$ we get: $x^n\cdot g(x) \cdot P(x)=(x-1)\cdot 2^n\cdot x^n \cdot g(2x)$ then $g(x)\cdot P(x)=2^n\cdot (x-1)\cdot g(2x) \ldots (\ast_2)$ Put $x=0$ in the last equation, since $g(0)\neq 0$ , we have $P(0)=-2^n$ . So $P(x)=2^{1000}x-2^n$ , and replacing this in $(\ast_2)$ we get: $g(x)\cdot (2^{1000-n}x-1)=(x-1)\cdot g(2x) \ldots (\ast_3)$ For $n=1000$ we get $f(x)=x^{1000}$ which of course is a solution.

Consider now $n\leq 999$ . If $g(r)=0$ and $r\neq 2^{n-999}$ then by $(\ast_3)$ we get $g(r/2)=0$ ; in other words: if $r$ is a root of $g$ and $r\neq 2^{n-999}$ then $r/2$ is also a root of $g$ .

Putting $x=1$ in $(\ast_3)$ we get $g(1)=0$ , so 1 is a root of $g$ and using the result of the previous paragraph we get that the $1000-n$ following numbers: $1, 2^{-1}, 2^{-2}, \ldots, 2^{-(999-n)}$ are roots of $g$ , but $g$ has degree $1000-n$ and is monic, so: $g(x)=(x-1)(x-2^{-1})\cdots(x-2^{-(999-n)})$ and then $f(x)=x^n\cdot(x-1)(x-2^{-1})\cdots(x-2^{-(999-n)})$ , and it is clear that this polynomial satisfies properties (1) to (4).

Finally, note that we can write $\displaystyle f(2)=\frac{2^n\cdot k}{2^0\cdot 2^1\cdot 2^2 \cdots 2^{999-n} }$ , where $k$ is a odd integer, so $f(2)$ is integer if and only $n\geq 0+1+2+\cdots+(999-n)$ , and solving this inequality we obtain $956\leq n \leq 999$ . So, for each such $n$ we get one polynomial.

Taking in account $f(x)=x^{1000}$ , we conclude that the answer is $999-955+1=45$ .

Since $f$ is monic, it determined by its complex roots (including multiplicity). By Property 4, note that if $f(z_0) = 0$ then either $z_0=1$ or $f(2z_0) = 0$ . We claim that every root of $f$ is either 0 or $2^{-n}$ for some nonnegative integer $n$ , for if $w$ is a non-zero root and $2^n w$ is never equal to $1$ then the polynomial $f$ would have the infinite set of roots $w, 2w, 4w, \ldots$ .

One solution is given by making all the roots $0$ , namely $x^{1000}$ . For any other solution, define $m\ge 0$ to be the largest integer such that $f(2^{-m})=0$ . Then $f$ has roots $1, 1/2, 1/4, \ldots, 2^{-m}$ , and possibly $0$ . We next determine the multiplicities of these roots, so let $o(z)$ denote the multiplicity of the root $z$ .

The RHS of Property 4 is divisible by $x-1$ but not by $(x-1)^2$ , since 2 is not a root of $f$ . Thus $o(1) = 1$ , and the RHS of Property 4 is divisible by $2x-1$ but not by $(2x-1)^2$ . This implies $o(1/2) \le 1$ , and continuing inductively we see that all non-zero roots must be simple.

Since $f$ has degree 1000, we deduce that $f(x) = x^{999-m} (x-1)(x-1/2) \cdots (x-2^{-m})$ .

It's easy to see that for any $m \le 999$ , this polynomial satisfies Properties 1, 2, 3, and 4 (property 3 being somewhat unnecessary), but Property 5 places a stricter bound on $m$ .

By considering each factor separately, we see that each factor after the first has odd numerator and denominator a power of 2. The 2-adic valuation of $f(2)$ is easily seen to be $999 - m - 1 - 2 - 3 - \cdots - m = 999 - m(m+3)/2$ , and this is non-negative precisely when $0 \le m \le 43$ , which gives 44 more solutions in addition to $x^{1000}$ .

First, we use the fundamental theorem of algebra with conditions 1 and 2 to write:

$f(x) = (x - a_1)(x - a_2)...(x - a_{1000})$

Note that the $a_i$ are in complex conjugate pairs, by condition 3.

The important condition is 4. That says that if b is a root of f(x), and b is not 1, then 2b is also a root of f(x) with no smaller multiplicity.

Suppose we have a root c that's not zero or the reciprocal of a power of 2 (includes complex roots). So c, 2c, 4c, etc must all be roots, contradiction (as there are only 1000 at most). Likewise, any root that's a reciprocal of a power of 2 can only appear with multiplicity 1, and there is one smallest such root and all larger such roots appear (including 1 itself).

So any solution with any nonzero root will look like

$(x-1)(x-\frac{1}{2})...(x - \frac{1}{2^n})*x^{999-n}$

And we calculate that this satisfies condition 5 iff $\frac{n(n+1)}{2} \leq 999 - n$ , which is satisfied for n at most 43, giving 45 solutions if we include the one with only zero roots.

We know $f(x)$ has 1000, not necessarily distinct, roots, $r_1, r_2, ..., r_{1000}$ . Therefore $g(x)=(x-1)f(2x)$ has the 1001 roots $1, \frac{r_1}{2}, \frac{r_2}{2}, ..., \frac{r_{1000}}{2}.$ For criterion 4 to be met, the 1000 roots of $f$ must all be included in the 1001 roots of $g.$ Clearly, if all the roots of $f$ are $0,$ that is, $f(x)=x^{1000}$ , all four criterion are met. If not, then consider the root with the largest absolute value. Note that this root must equal $1,$ or else it will not appear in the 1001 roots of $g$ . It follows from there that the remaining roots must be either be $0$ or successively lower powers of 2. In other words, our possibilities for $f$ are: $f(x)=x^{1000}$ $f(x)=x^{999}(x-1)$ $f(x)=x^{998}(x-1)\left(x-\frac{1}{2}\right)$ $f(x)=x^{997}(x-1)\left(x-\frac{1}{2}\right)\left(x-\frac{1}{4}\right)$ $\cdots$ Now, we must also have an integer value of $f(2)$ . Suppose $f$ has $m$ nonzero roots. Hence, $f(2)=2^{1000-m}\prod_{i=0}^{m-1} \left(2-\left(\frac{1}{2}\right)^i\right).$ For this to be an integer, we must have $1000-m \ge \sum_{i=0}^{m-1} i \Longrightarrow m \le 44.$ This gives us $45$ values for $m,$ and a quick check confirms that they all work, so $45$ is our final answer.

Note that by comparing degrees and leading coefficients we have the equality $(x-1)f(2x)=2^{1000}(x-\alpha)f(x)$ for some real number $\alpha$ . If $\alpha=1$ , then $f(2x)=2^{1000}f(x)$ and the only way this can happen is if $f(x)=x^{1000}$ . So suppose that $\alpha\neq 1$ .

Then $x-1$ is a factor of $f(x)$ , so $f(x)=(x-1)f_1(x)$ , and $f(2x)=(2x-1)f_1(2x)$ , implying that $2x-1$ (or equivalently $x-\frac{1}{2}$ ) is a factor of $(x-\alpha)f(x)$ . Again, either $\alpha=\frac{1}{2}$ or $x-\frac{1}{2}$ is a factor of $f(x)$ .

We repeat this process of extracting a factor of $f(x)$ and then obtaining a new factor on the left hand side. of the polynomial equation in the first line above. We see that among the roots of $f(x)$ are $1,\frac{1}{2},\frac{1}{4},\dots\,2^{1-r}$ and that $\alpha=2^{-r}$ for some integer $r\ge 1$ . The polynomial equation transforms as follows:

$(x-1)(2x-1)(2x-\frac{1}{2})\cdots (2x-2^{-r})g(2x)=2^{1000}(x-1)(x-\frac{1}{2})\cdots (x-2^{-r}) (x-\alpha) g(x)$ for some polynomial $g(x)$ . All the linear terms cancel, and we are left with an extra factor of $2^{r+1}$ on the left hand side. Dividing by this gives us $g(2x)=2^{999-r}g(x)$ with the unique monic solution $g(x)=x^{999-r}$ . This means that $f(x)=x^{999-r}(x-1)(x-\frac{1}{2})\cdots(x-2^r)$ .

Lastly we check for which values of $r$ is $f(2)$ an integer. The first factor contributes 2^{999-r . After that there are factors of $2$ only in the denominator, $2-2^{-k}$ contributing a factor of $2^{-k}$ . Hence we need $999-r\ge 1+2+\cdots+r=\frac{r(r+1)}{2}$ which happens (for non-negative $r$ ) when $r\le 43$ . So the valid solutions occur when $r=0,1,\cdots,43$ and adding the one at the start where $\alpha=1$ , gives a total of $45$ solutions.

One may fret at the fact that there are $5$ conditions, however, we can "group" the conditions. We will look at the first $4$ first, since they contain the variable $x$ , determine the set of functions, and evaluate using condition $5$ to see how many satisfy all the conditions.

Now let us rewrite the 4th condition as follow:

$f(2x)(x-1) = f(x) \times k$ (*)

where $k$ is a certain expression. In this form, we can easily notice that it is neat to consider the roots of $f(x)$ . Because, if $r$ is a root of $f(x)$ that $\neq 1$ , then we must have that $2x$ is also a root of $f(x)$ . By induction, it is clear that $2^mx$ is also a root for an integer $m$ .

It necessarily follows that $f(x)$ does not have any complex roots . For instance, we can always double them to get an infinite number of roots, which violates the conditions. In addition, we also have that all roots are either $0, 1,$ or of the form $(\frac{1}{2})^k$ or else, $f(x)$ would have an infinite number of roots since we can always double and get new roots, until we get $1$ after a certain doubling.

Whence, we can express $f(x)$ in the following form:

$f(x) = x^{p_0} (x-1)^{p_1} (x-\frac{1}{2})^{p_2} (x-1/4)^{p_3} … (x-(\frac{1}{2})^{r-1})^{p_r}$

where positive integers $p_0, \ldots, p_r$ satisfy $p_0p_1 \ldots p_r = 1000$ So subbing this into (*), we get:

$2^{p_0}x^{p_0} (2x-1)^{p_1} (2x-\frac{1}{2})^{p_2} … (2x-(\frac{1}{2})^{r-1})^{p_r} (x-1) = x^{p_0} (x-1)^{p_1} (x-\frac{1}{2})^{p_2} (x- \frac{1}{4})^{p_3} … (x-(\frac{1}{2})^{r-1})^{p_r} \times k$

Now, we see lots of multiples of $2$ , it would be intuitive to pull out all the multiples of $2$ to derive the following:

$2^{1000} x^{p_0} (x-\frac{1}{2})^{p_1} (x-1/4)^{p_2} … (x-(\frac{1}{2})^r)^{p_r} (x-1) = x^{p_0} (x-1)^{p_1} (x-\frac{1}{2})^{p_2} (x-\frac{1}{4})^{p_3} … (x-(\frac{1}{2})^{r-1})^{p_r} \times k$

Now, we can see that by matching coefficients we can set $k = 2^{1000}x + \frac{1}{2}^{r} \times 2^{1000}$ , a linear equation in $x$ . After a simple transformation, we can also easily get $p_1 = p_2 = … = p_r = 1$ . So f(x) is of the form:

$f(x) = x^{1000-r} (x-1)(x-\frac{1}{2})(x-\frac{1}{4})…(x-(\frac{1}{2})^{r-1})$

where $0 \leq r \leq 1000$ .

Now, we have to work on the final 5th condition, the interested reader can verify that when $r = 45$ , $f(2)$ is not an integer. In fact, try $r = 46, 47, 48$ will motivate us to conjecture that the last condition holds only for $r \leq 44$ . Let us rewrite the expression for $f(2)$ as follows:

$f(2) = 2^{1000-r}(2-1)(2-\frac{1}{2})…(2-( \frac{1}{2})^{r-1})$ $= 2^{1000} (1-\frac{1}{2})(1-\frac{1}{4})(1-\frac{1}{8})…(1-( \frac{1}{2})^r)$ $= 2^{1000} ( \frac{1}{2})( \frac{3}{4})( \frac{7}{8})…( \frac{2^{r}-1}{2^{r}})$

since the exponent of $2$ in the denominator of the product cannot exceed that of $1000$ , we need only solve $\frac{r(r+1)}{2} \leq 1000$ , which gives $r ≤ 44$ . It is routine to verify that $r = 0,1$ work, giving a total of 45 solutions.

SInce this polynom has $1000$ roots, we can written it as :

$P(x) = (x - a_1)(x - a_2) \ldots (x - a_{1000})$ , so this satisfy that $P(x)$ is monic and also has degree $1000$ . And WLOG that $|x_1| \le |x_2| \le |x_3| \ldots |x_{1000}|$

Now, we see that : $P(x) | (x - 1)P(2x)$ $\prod_{i = 1}^{1000} (x - x_i) | (x - 1)\prod_{i = 1}^{1000} (2x - x_i)$ implies $\prod_{i = 1}^{1000} (x - x_i) | 2^{1000}. (x - 1)\prod_{i = 1}^{1000} (x - \frac{x_i}{2})$ .

So, we see that, on LHS there are $1000$ roots, but in RHS there are $1001$ roots. So, Between LHS and RHS should be share $1000$ roots. We will divide it into two case :

Case 1 : $(x - 1) \nmid P(x)$ . So, In RHS and LHS should be has the same roots. But, $| \frac{a_1}{2} | \le |a_1| \le |a_2| \ldots \le |a_{1000}|$ . So, it should be $x_1 = x_2 = \ldots = x_{1000} = 0$ . So, $P(x) = x^{1000}$

Case 2 : $(x - 1) | P(x)$ . So, we can write it as $\prod_{i = 1}^{999} (x - x_i) | 2^{1000}. (x - \frac{1}{2} ) \prod_{i = 1}^{999} (x - \frac{x_i}{2})$ . And, see that pattern, $\prod_{i = 1}^{1000 - k} (x - x_i) | 2^{1000}. (x - \frac{1}{2^k} ) \prod_{i = 1}^{1000 - k} (x - \frac{x_i}{2})$ .

So, all of the subset polynomial that satisfy this Condition for this case is : $P(x) = (x - 1). (\prod_{i = 1}^{k} (x - \frac{1}{2^k}).x^{999 - k}$ .

But, as wee see that, $P(2)$ is integer, so $P(x) = (2 - 1). (\prod_{i = 1}^{k} (2 - \frac{1}{2^k}).2^{999 - k}$ should be integer. So,

$(\frac{1}{2})(\frac{1}{2^2})(\frac{1}{2^3}) \ldots (\frac{1}{2^k}). 2^{999-k}$ should be integer. So,

$\frac{1}{2^{1 + 2 + \ldots + k}. 2^{999-k}}$ . Thus $2^{\frac{k(k+1)}{2}} | 2^{999 - k} \implies k^2 + k \le 1998 - 2k \implies k^2 + 3k - 1998 \le 0$ . Since $k \ge 0$ . So, the values of $k$ take the range $0 \le k \le 43$ where $k$ is integer. So, for this case, there are only $44$ solutions that is $P(x) = (x - 1). (\prod_{i = 1}^{k} (x - \frac{1}{2^k}).x^{999 - k}$ for $0 \le k \le 43$ and $k$ is integer.

And see that, the coefficient all terms is real. So, satisfy the condition $3$ .

So, total for case $1$ and case $2$ is $44 + 1 = \boxed{45}$ solution.

Since $f(x)$ is monic of degree $1000$ and divides $(x-1)f(2x)$ , which has degree $1001$ and leading coefficient $2^{1000}$ , we deduce that there exists a constant $\alpha$ such that $(x-1)f(2x) \; = \; 2^{1000}(x-\alpha)f(x)$ If $\alpha = 0$ then (putting $x=0$ ) we see that $f(x)=0$ . But then $f(x) = x^bg(x)$ for some polynomial $g(x)$ where $g(0) \neq 0$ and some $b \in \mathbb{N}$ , and $2^bx^b(x-1)g(2x) \,=\, 2^{1000}x^{b+1}g(x)$ , which is impossible. Thus we deduce that $\alpha \neq 0$ .

If $\alpha = 1$ then $f(2x) = 2^{1000}f(x)$ , which is only possible when $f(x) = x^{1000}$ . That's one polynomial. Suppose now that $\alpha\neq 1$ , so that $f(1) = 0$ . Since $(\alpha-1)f(2\alpha) = 0$ , we see that $2\alpha$ is a zero of $f(x)$ .

Let $C \,=\, \{2^{-n} \,|\, n \ge 0\} \cup \{0\}$ . If $\beta$ is a zero of $f(x)$ which does not belong to $C$ , then $2\beta$ does not belong to $C$ either. Thus $\beta \neq 1$ and so, since $(\beta-1)f(2\beta) = 2^{1000}(\beta-\alpha)f(\beta) = 0$ , we deduce that $2\beta$ is a zero of $f(x)$ as well. Thus (by induction) we deduce that $2^m\beta$ is a zero of $f(x)$ for all $m \in \mathbb{N}$ , and hence $f(x)$ has infinitely many distinct zeros. We deduce that any zero of $f(x)$ is an element of $C$ .

Let $D \,=\, \{2^n\alpha \,|\, n \ge 1\} \cup \{0\}$ . If $\beta$ is a zero of $f(x)$ which does not belong to $D$ , then $\tfrac12\beta$ does not belong to $D$ either. Now $\tfrac12\beta \neq \alpha$ and so, since $0=(\tfrac12\beta-1)f(\beta)=2^{1000}(\tfrac12\beta-\alpha)f(\tfrac12\beta)$ , we deduce that $\tfrac12\beta$ is a zero of $f(x)$ as well. Thus (by induction) we deduce that $2^{-m}\beta$ is a zero of $f(x)$ for all $m \in \mathbb{N}$ , and hence $f(x)$ has infinitely many distinct zeros. We deduce that any zero of $f(x)$ is an element of $D$ .

Since $2\alpha$ is a nonzero zero of $f(x)$ , we deduce that $\alpha = 2^{-N}$ for some $N \in \mathbb{N}$ . Putting our results together, we deduce that the zeros of $f(x)$ form a subset of $\{2^{-m} \,|\, 0 \le m \le N-1\}\cup\{0\}$ . This implies that all zeros of $f(x)$ are real, and hence that the polynomial $f(x)$ factorizes completely over $\mathbb{R}$ . If we write $f(x) \; = \;x^c \prod_{j=0}^{N-1} \big(x-2^{-j}\big)^{d_j} \qquad c + d_0 + \cdots + d_{N-1} = 1000\;,$ then $\begin{array}{rcl}\displaystyle x^c (x-1)\prod_{j=1}^N \big(x-2^{-j}\big)^{d_{j-1}} & =& \displaystyle\frac{(x-1)2^c x^c}{2^{1000}} \prod_{j=0}^{N-1}\big(2x - 2^{-j}\big)^{d_j} \\ & = & 2^{-1000}(x-1)f(2x) \\ & = & \displaystyle(x-\alpha)f(x) \\ & = & \displaystyle x^c \prod_{j=0}^{N-1}\big(x-2^{-j}\big)^{d_j} \times \big(x - 2^{-N}\big) \end{array}$ and hence $d_0 = d_1 = \cdots = d_{N-1} = 1$ . Thus we deduce that $f(x) \; = \; x^{1000-N}\prod_{j=0}^{N-1}\big(x - 2^{-j}\big)$ and hence $\begin{array}{rcl}\displaystyle f(2) & =& \displaystyle2^{1000-N}\prod_{j=0}^{N-1}\big(2 - 2^{-j}\big) \\ & = & \displaystyle 2^{1000 - N - \frac12N(N-1)}\prod_{j=0}^{N-1}\big(2^{j+1}-1\big) \\ & = & 2^{1000 - \frac12N(N+1)}A \end{array}$ where $A$ is an odd integer. Thus we decuce that $\tfrac12N(N+1) \le 1000$ , which tells us that $1 \le N \le 44$ . We have found another $44$ polynomials.

Thus there are $1+44 = 45$ polynomials altogether.

First, find all f(x) that meet the first 4 requirements (it turns out there are 1001 of them). We are given that for some constants a, b:

f(2x)(x-1) = f(x)(ax+b) (Equation 1).

Suppose z is a point such that f(z)=0, and z is not 1. Then f(2z)(z-1) = 0, so f(2z) = 0. Thus, if z is a zero of f(x) and z is not 1, then 2z is also a zero.

It follows that f(x) has no complex roots, since then it would have an infinite number of roots as we double them to get new ones. Further, all roots are either 0, 1, or of the form 1/2^k (else, f(x) would have an infinite number of roots since we can always double and get new roots, until such doubling gives us 1). So f(x) is of the form:

f(x) = x^(d 0) (x-1)^(d 1) (x-1/2)^(d 2) (x-1/4)^(d 3) … (x-1/2^(r-1))^(d_r)

for some non-negative integers d 0, d 1, …, d r that satisfy d 0 + d 1 + … + d r = 1000. Then from equation 1: 2^(d 0)x^(d 0) (2x-1)^(d 1) (2x-1/2)^(d 2) … (2x-1/2^(r-1))^(d r) (x-1) = x^(d 0) (x-1)^(d 1) (x-1/2)^(d 2) (x-1/4)^(d 3) … (x-1/2^(r-1))^(d r)(ax+b)

Pulling out factors of 2 from the terms on the left-hand-side gives: 2^(d 0+d 1+…+d r) x^(d 0) (x-1/2)^(d 1) (x-1/4)^(d 2) … (x-1/2^r)^(d r) (x-1) = x^(d 0) (x-1)^(d 1) (x-1/2)^(d 2) (x-1/4)^(d 3) … (x-1/2^(r-1))^(d r)(ax+b)

So a = 2^(1000) and we simplify to: (x-1/2)^(d 1) (x-1/4)^(d 2) … (x-1/2^r)^(d r) (x-1) = (x-1)^(d 1) (x-1/2)^(d 2) (x-1/4)^(d 3) … (x-1/2^(r-1))^(d_r) (x + b/a)

so b/a = -1/2^r. Also, d 1=1, 1 = d 1 = d 2 = … = d r. Thus:

f(x) = x^(1000-r) (x-1)(x-1/2)(x-1/4)…(x-1/2^(r-1))

and any such form satisfies the first 4 requirements. That is, we can have: f(x) = x^1000 f(x) = x^999 (x-1) f(x) = x^998 (x-1)(x-1/2) f(x) = x^997 (x-1)(x-1/2)(x-1/4) … f(x) = x^1 (x-1)(x-1/2)(x-1/4)…(x-1/2^998). f(x) = (x-1)(x-1/2)(x-1/4) … (x-1/2^999).

So there are 1001 possibilities. Now let's check the 5th requirement f(2) = integer. Case r=0: f(x) = x^1000 works. Case r=1: f(x) = x^999*(x-1) works. Case r>1: f(2) = 2^(1000-r)(2-1)(2-1/2)…(2-1/2^(r-1)) = 2^(1000-r) 2^r (1-1/2)(1-1/4)(…)(1-1/2^r) = 2^1000 (1-1/2)(1-1/4)(1-1/8)…(1-1/2^r). = 2^(1000) (1/2)(3/4)(7/8)…((2^r-1)/2^r) = 2^(1000) Prod_{k=1}^r (2^k-1)/2^k

This is integer if and only if r <= 44. So there are 45 solutions.