1000 Degree Polynomial

Algebra Level 5

How many polynomials f ( x ) f(x) are there, which satisfy all the following conditions:

  1. f ( x ) f(x) is monic.
  2. f ( x ) f(x) has degree 1000.
  3. f ( x ) f(x) has real coefficients.
  4. f ( x ) f(x) divides ( x 1 ) f ( 2 x ) (x-1)f(2x) .
  5. f ( 2 ) f(2) is an integer.

Details and assumptions

A polynomial is monic if its leading coefficient is 1. For example, the polynomial x 3 + 3 x 5 x^3 + 3x - 5 is monic but the polynomial x 4 + 2 x 3 6 -x^4 + 2x^3 - 6 is not.

As stated in the problem, the coefficients are real values, not necessarily integer valued.

Clarification: The divisibility condition in 4 is about polynomials, not integer values obtained upon evaluation. For example, x 1 x-1 divides x 2 1 x^2 -1 . since x 2 1 = ( x 1 ) ( x + 1 ) x^2-1 = (x-1)(x+1) . x 2 x-2 does not divide x 2 1 x^2-1 , even though when " x = 3 x=3 ", 1 divides 8.


The answer is 45.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

9 solutions

Jorge Tipe
May 20, 2014

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

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

Putting x = 1 x=1 in ( 3 ) (\ast_3) we get g ( 1 ) = 0 g(1)=0 , so 1 is a root of g g and using the result of the previous paragraph we get that the 1000 n 1000-n following numbers: 1 , 2 1 , 2 2 , , 2 ( 999 n ) 1, 2^{-1}, 2^{-2}, \ldots, 2^{-(999-n)} are roots of g g , but g g has degree 1000 n 1000-n and is monic, so: g ( x ) = ( x 1 ) ( x 2 1 ) ( x 2 ( 999 n ) ) g(x)=(x-1)(x-2^{-1})\cdots(x-2^{-(999-n)}) and then f ( x ) = x n ( x 1 ) ( x 2 1 ) ( x 2 ( 999 n ) ) 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 f ( 2 ) = 2 n k 2 0 2 1 2 2 2 999 n \displaystyle f(2)=\frac{2^n\cdot k}{2^0\cdot 2^1\cdot 2^2 \cdots 2^{999-n} } , where k k is a odd integer, so f ( 2 ) f(2) is integer if and only n 0 + 1 + 2 + + ( 999 n ) n\geq 0+1+2+\cdots+(999-n) , and solving this inequality we obtain 956 n 999 956\leq n \leq 999 . So, for each such n n we get one polynomial.

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

All submitted solutions were essentially correct, and all of them shared the same strategy: first find all polynomials satisfying the first four conditions, looking at their roots, and then look at the last condition. The details of the justification varied considerably, though the main ideas were the same. The two featured solutions are a good example of that.

The 2-adic valuation of a rational number, referred to in the last paragraph of the second solution, is the difference between the order of 2 in its numerator and the order of 2 in its denominator. It is a very useful notion in number theory, that serves as a starting point for the theory of p-adic numbers, for the prime number p=2. For more on p-adic numbers see, for example, http://en.wikipedia.org/wiki/P-adic_number

Calvin Lin Staff - 7 years ago
Erick Wong
May 20, 2014

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

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

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

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

It's easy to see that for any m 999 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 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 ) f(2) is easily seen to be 999 m 1 2 3 m = 999 m ( m + 3 ) / 2 999 - m - 1 - 2 - 3 - \cdots - m = 999 - m(m+3)/2 , and this is non-negative precisely when 0 m 43 0 \le m \le 43 , which gives 44 more solutions in addition to x 1000 x^{1000} .

This is a very clearly and carefully written solution. The 2-adic valuation of a rational number, referred to in the last paragraph, is the difference between the order of 2 in its numerator and the order of 2 in its denominator. It is a very useful notion in number theory, that serves as a starting point for the theory of p-adic numbers, for the prime number p=2. For more on p-adic numbers see, for example, http://en.wikipedia.org/wiki/P-adic_number

Calvin Lin Staff - 7 years ago
James Aaronson
May 20, 2014

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 ) f(x) = (x - a_1)(x - a_2)...(x - a_{1000})

Note that the a i 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 1 2 ) . . . ( x 1 2 n ) x 999 n (x-1)(x-\frac{1}{2})...(x - \frac{1}{2^n})*x^{999-n}

And we calculate that this satisfies condition 5 iff n ( n + 1 ) 2 999 n \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.

"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)." This is not a completely rigorous justification, but I do not want to be picky, most likely the author could have filled in the details if necessary.

Calvin Lin Staff - 7 years ago
Jesse Zhang
May 20, 2014

We know f ( x ) f(x) has 1000, not necessarily distinct, roots, r 1 , r 2 , . . . , r 1000 r_1, r_2, ..., r_{1000} . Therefore g ( x ) = ( x 1 ) f ( 2 x ) g(x)=(x-1)f(2x) has the 1001 roots 1 , r 1 2 , r 2 2 , . . . , r 1000 2 . 1, \frac{r_1}{2}, \frac{r_2}{2}, ..., \frac{r_{1000}}{2}. For criterion 4 to be met, the 1000 roots of f f must all be included in the 1001 roots of g . g. Clearly, if all the roots of f f are 0 , 0, that is, f ( x ) = x 1000 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 , 1, or else it will not appear in the 1001 roots of g g . It follows from there that the remaining roots must be either be 0 0 or successively lower powers of 2. In other words, our possibilities for f f are: f ( x ) = x 1000 f(x)=x^{1000} f ( x ) = x 999 ( x 1 ) f(x)=x^{999}(x-1) f ( x ) = x 998 ( x 1 ) ( x 1 2 ) f(x)=x^{998}(x-1)\left(x-\frac{1}{2}\right) f ( x ) = x 997 ( x 1 ) ( x 1 2 ) ( x 1 4 ) 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 ) f(2) . Suppose f f has m m nonzero roots. Hence, f ( 2 ) = 2 1000 m i = 0 m 1 ( 2 ( 1 2 ) i ) . 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 i = 0 m 1 i m 44. 1000-m \ge \sum_{i=0}^{m-1} i \Longrightarrow m \le 44. This gives us 45 45 values for m , m, and a quick check confirms that they all work, so 45 45 is our final answer.

"It follows from there that the remaining roots must be either be 0 0 or successively lower powers of 2" A little more details would be better... decided to be lenient, but not feature.

Calvin Lin Staff - 7 years ago
Dirk Basson
May 20, 2014

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

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

We repeat this process of extracting a factor of f ( x ) 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 ) f(x) are 1 , 1 2 , 1 4 , 2 1 r 1,\frac{1}{2},\frac{1}{4},\dots\,2^{1-r} and that α = 2 r \alpha=2^{-r} for some integer r 1 r\ge 1 . The polynomial equation transforms as follows:

( x 1 ) ( 2 x 1 ) ( 2 x 1 2 ) ( 2 x 2 r ) g ( 2 x ) = 2 1000 ( x 1 ) ( x 1 2 ) ( x 2 r ) ( x α ) g ( x ) (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 ) g(x) . All the linear terms cancel, and we are left with an extra factor of 2 r + 1 2^{r+1} on the left hand side. Dividing by this gives us g ( 2 x ) = 2 999 r g ( x ) g(2x)=2^{999-r}g(x) with the unique monic solution g ( x ) = x 999 r g(x)=x^{999-r} . This means that f ( x ) = x 999 r ( x 1 ) ( x 1 2 ) ( x 2 r ) f(x)=x^{999-r}(x-1)(x-\frac{1}{2})\cdots(x-2^r) .

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

A well-written solution. Could have been chosen as featured.

Calvin Lin Staff - 7 years ago
Anqi Li
Nov 11, 2013

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

Now let us rewrite the 4th condition as follow:

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

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

It necessarily follows that f ( x ) 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 , 0, 1, or of the form ( 1 2 ) k (\frac{1}{2})^k or else, f ( x ) f(x) would have an infinite number of roots since we can always double and get new roots, until we get 1 1 after a certain doubling.

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

f ( x ) = x p 0 ( x 1 ) p 1 ( x 1 2 ) p 2 ( x 1 / 4 ) p 3 ( x ( 1 2 ) r 1 ) p r 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 , , p r p_0, \ldots, p_r satisfy p 0 p 1 p r = 1000 p_0p_1 \ldots p_r = 1000 So subbing this into (*), we get:

2 p 0 x p 0 ( 2 x 1 ) p 1 ( 2 x 1 2 ) p 2 ( 2 x ( 1 2 ) r 1 ) p r ( x 1 ) = x p 0 ( x 1 ) p 1 ( x 1 2 ) p 2 ( x 1 4 ) p 3 ( x ( 1 2 ) r 1 ) p r × k 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 2 , it would be intuitive to pull out all the multiples of 2 2 to derive the following:

2 1000 x p 0 ( x 1 2 ) p 1 ( x 1 / 4 ) p 2 ( x ( 1 2 ) r ) p r ( x 1 ) = x p 0 ( x 1 ) p 1 ( x 1 2 ) p 2 ( x 1 4 ) p 3 ( x ( 1 2 ) r 1 ) p r × k 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 + 1 2 r × 2 1000 k = 2^{1000}x + \frac{1}{2}^{r} \times 2^{1000} , a linear equation in x x . After a simple transformation, we can also easily get p 1 = p 2 = = p r = 1 p_1 = p_2 = … = p_r = 1 . So f(x) is of the form:

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

where 0 r 1000 0 \leq r \leq 1000 .

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

f ( 2 ) = 2 1000 r ( 2 1 ) ( 2 1 2 ) ( 2 ( 1 2 ) r 1 ) f(2) = 2^{1000-r}(2-1)(2-\frac{1}{2})…(2-( \frac{1}{2})^{r-1}) = 2 1000 ( 1 1 2 ) ( 1 1 4 ) ( 1 1 8 ) ( 1 ( 1 2 ) r ) = 2^{1000} (1-\frac{1}{2})(1-\frac{1}{4})(1-\frac{1}{8})…(1-( \frac{1}{2})^r) = 2 1000 ( 1 2 ) ( 3 4 ) ( 7 8 ) ( 2 r 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 2 in the denominator of the product cannot exceed that of 1000 1000 , we need only solve r ( r + 1 ) 2 1000 \frac{r(r+1)}{2} \leq 1000 , which gives r 44 r ≤ 44 . It is routine to verify that r = 0 , 1 r = 0,1 work, giving a total of 45 solutions.

Muhammad Al Kahfi
May 20, 2014

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

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

Now, we see that : P ( x ) ( x 1 ) P ( 2 x ) P(x) | (x - 1)P(2x) i = 1 1000 ( x x i ) ( x 1 ) i = 1 1000 ( 2 x x i ) \prod_{i = 1}^{1000} (x - x_i) | (x - 1)\prod_{i = 1}^{1000} (2x - x_i) implies i = 1 1000 ( x x i ) 2 1000 . ( x 1 ) i = 1 1000 ( x x i 2 ) \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 1000 roots, but in RHS there are 1001 1001 roots. So, Between LHS and RHS should be share 1000 1000 roots. We will divide it into two case :

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

Case 2 : ( x 1 ) P ( x ) (x - 1) | P(x) . So, we can write it as i = 1 999 ( x x i ) 2 1000 . ( x 1 2 ) i = 1 999 ( x x i 2 ) \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, i = 1 1000 k ( x x i ) 2 1000 . ( x 1 2 k ) i = 1 1000 k ( x x i 2 ) \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})