Remainder factor theorem: me reason this out

[Terrell]

Homework Statement

find the number of polynomials f(x) that satisfies the condition:
f(x) is monic polynomial, has degree 1000, has integer coefficients, and it can divide f(2x^3 + x)

i would very much prefer that you guys give me hints first. thanks

Homework Equations

remainder factor theorem

The Attempt at a Solution

since f(2x^3 + x) = q(x)*f(x) such that q(x) is of degree 2000 and f(x) is of degree 1000 because f(2x^3 + x) is of degree 3000.

since the problem asked for the number of f(x) that satisfies the condition, then i think it would be the number of ways to choose 1000 first degree polynomials in a group of 3000 first degree polynomials, which i think would be 3000C1000...? but wolfram alpha tells me the number has 829 digits which i think must be wrong because it doesn't fit the answer box that I'm trying to input my answer into.

 

[RUber]

I don't have a complete solution at this point, but I think the fact that p is monic tells you to start with the leading coefficients. You should be able to constrain the possible q's based on that.

 

[Terrell]

I don't have a complete solution at this point, but I think the fact that p is monic tells you to start with the leading coefficients. You should be able to constrain the possible q's based on that.

i may have thought of that one too using rational root theorem, but the last term is not given so i don't know how to proceed from there.

 

[fresh_42]

My idea was to use $f(g(x))'=f'(x)g'(x) = f'(x)q(x)+f(x)q'(x)$ with $g(x)=2x^3+x$ and then to think about the leading and lowest terms.

 

[Terrell]

My idea was to use $f(g(x))'=f'(x)g'(x) = f'(x)q(x)+f(x)q'(x)$ with $g(x)=2x^3+x$ and then to think about the leading and lowest terms.

i'll give this one a go when i get up tomorrow. thanks

 

[fresh_42]

i'll give this one a go when i get up tomorrow. thanks

Not sure, whether it leads somewhere. I just thought it might be interesting.

 

[Buffu]

My idea was to use $f(g(x))'=f'(\color{red}{g(x)})g'(x) = f'(x)q(x)+f(x)q'(x)$ with $g(x)=2x^3+x$ and then to think about the leading and lowest terms.

 

[fresh_42]

i'll give this one a go when i get up tomorrow. thanks

Meanwhile, I think that leads nowhere. But the considerations of $f(0), f(x)=x^n\cdot h(x)$ with $n\geq 0$ and $h(0)\neq 0$ give the highest and lowest term of $q(x)$ and the consideration of all (complex) zeros yields a strong statement for these, i.e. the question whether $f(a)=0$ can hold for real $a$ beside $a=0$ and for which complex $a$.

 

[Terrell]

Meanwhile, I think that leads nowhere. But the considerations of $f(0), f(x)=x^n\cdot h(x)$ with $n\geq 0$ and $h(0)\neq 0$ give the highest and lowest term of $q(x)$ and the consideration of all (complex) zeros yields a strong statement for these, i.e. the question whether $f(a)=0$ can hold for real $a$ beside $a=0$ and for which complex $a$.

i agree with your statement with f(x)= (x^n)*h(x) including f(0), following the idea.. what i was thinking is... can a thousand degree polynomial be factored into linear terms? since the question asked how many different polynomials, but never told us that it's factors cannot have non-integer coefficients.

 

[fresh_42]

I haven't considered the factorization, which of course could be done over $\mathbb{C}$, even if we are not able to explicitly write down all $1,000$ roots as root expressions. I iterated $f(g(x))=q(x)f(x)$ instead. With $f(x) =: x^nh(x)\, , \,h(0)\neq 0$ we get $(2x^2+1)^nh(g(x))=q(x)h(x)$ which gives $q(0)$ and the highest term of $q(x)$. Now $f(z)=0$ has a $n-$fold zero at $z=0$ ($n\geq 0$) and the rest of its roots are the same as those of $h(x)$ which doesn't have a root at zero. But if $h(z)=0$, what can you say about $h(g(z))$ and all other iterations with $g(x)=x(2x^2+1)\,$? Can $z$ be real? What does it mean for complex solutions (roots) $z=re^{i\varphi}$ of $h(x)$, resp. $f(x)\,$? I haven't done it to the end, but it looks as these considerations give a lot of conditions, especially an investigation of $r$ looks promising.

 

[Terrell]

I haven't considered the factorization, which of course could be done over $\mathbb{C}$, even if we are not able to explicitly write down all $1,000$ roots as root expressions. I iterated $f(g(x))=q(x)f(x)$ instead. With $f(x) =: x^nh(x)\, , \,h(0)\neq 0$ we get $(2x^2+1)^nh(g(x))=q(x)h(x)$ which gives $q(0)$ and the highest term of $q(x)$. Now $f(z)=0$ has a $n-$fold zero at $z=0$ ($n\geq 0$) and the rest of its roots are the same as those of $h(x)$ which doesn't have a root at zero. But if $h(z)=0$, what can you say about $h(g(z))$ and all other iterations with $g(x)=x(2x^2+1)\,$? Can $z$ be real? What does it mean for complex solutions (roots) $z=re^{i\varphi}$ of $h(x)$, resp. $f(x)\,$? I haven't done it to the end, but it looks as these considerations give a lot of conditions, especially an investigation of $r$ looks promising.

hmm... i thought we were saying the same thing, but i misunderstood f(x) = (x^n)(h(x)) give the highest and lowest degree of q(x). the way i understand it is... as n gets bigger then obviously the degree of q(x) must go lower to satisfy the degree of f(g(x)). However, you seem to be saying something different. i do not understand why ((2x^2 + 1)^n)*h(g(x)) = q(x)h(x). i also do not know what an n-fold means.

 

[Terrell]

I haven't considered the factorization, which of course could be done over $\mathbb{C}$, even if we are not able to explicitly write down all $1,000$ roots as root expressions. I iterated $f(g(x))=q(x)f(x)$ instead. With $f(x) =: x^nh(x)\, , \,h(0)\neq 0$ we get $(2x^2+1)^nh(g(x))=q(x)h(x)$ which gives $q(0)$ and the highest term of $q(x)$. Now $f(z)=0$ has a $n-$fold zero at $z=0$ ($n\geq 0$) and the rest of its roots are the same as those of $h(x)$ which doesn't have a root at zero. But if $h(z)=0$, what can you say about $h(g(z))$ and all other iterations with $g(x)=x(2x^2+1)\,$? Can $z$ be real? What does it mean for complex solutions (roots) $z=re^{i\varphi}$ of $h(x)$, resp. $f(x)\,$? I haven't done it to the end, but it looks as these considerations give a lot of conditions, especially an investigation of $r$ looks promising.

this problem was lifted from an article on remainder factor theorem, but it seems much more complicated than that or am i just missing something here

 

[fresh_42]

Just substitute $f(x)=x^nh(x)$ in $f(g(x))=f(x(2x^2+1))=q(x)f(x)$. Well, $x=0$ or in other words $x\,\vert \,f(x)$ or $f(0)=0$ is one possible solution. And we cannot say what the maximal $n$ with $x^n\,\vert \,f(x)$ is. So all $n$ between $0$ and $1,000$ are on principle possible. After we separated the maximal possible factor $x^n$ we can concentrate on $h(x)$ with $h(0)\neq 0$.

 

[Terrell]

Just substitute $f(x)=x^nh(x)$ in $f(g(x))=f(x(2x^2+1))=q(x)f(x)$. Well, $x=0$ or in other words $x\,\vert \,f(x)$ or $f(0)=0$ is one possible solution. And we cannot say what the maximal $n$ with $x^n\,\vert \,f(x)$ is. So all $n$ between $0$ and $1,000$ are on principle possible. After we separated the maximal possible factor $x^n$ we can concentrate on $h(x)$ with $h(0)\neq 0$.

if f(x) = (x^n)(h(x)) and g(x) = x(2x+1) then f(g(x)) = (x^n)((2x^2 + 1)^n) * h(x(2x^2 + 1))?

 

[Terrell]

Just substitute $f(x)=x^nh(x)$ in $f(g(x))=f(x(2x^2+1))=q(x)f(x)$. Well, $x=0$ or in other words $x\,\vert \,f(x)$ or $f(0)=0$ is one possible solution. And we cannot say what the maximal $n$ with $x^n\,\vert \,f(x)$ is. So all $n$ between $0$ and $1,000$ are on principle possible. After we separated the maximal possible factor $x^n$ we can concentrate on $h(x)$ with $h(0)\neq 0$.

then i think we're saying almost the same thing. just in case we have n already, how do you think can we deduce the number of polynomials that are like f(x) from there?

 

[fresh_42]

Yes. I think it's easier to keep $g(x)=x(2x^2+1)$ where possible, so $q(x)f(x)=q(x)x^nh(x)=f(g(x))=g(x)^nh(g(x))=x^n(2x^2+1)^nh(g(x))$.
Now $x^n$ can be divided and we are left with $h(x)$ and $h(g(x))\cdot (2x^2+1)^n=q(x)\cdot h(x)$.
Here we can look for the highest and lowest terms of $q(x)$. The lowest is easy, as it is $h(g(0)) = h(0) = q(0) \cdot h(0)$ and $h(0) \neq 0$. For the highest some considerations on the degrees of the polynomials involved might be necessary. And we can investigate the solutions of $h(z)=0$. First with $z \in \mathbb{R}$ and then with $z=r\cdot e^{i\varphi}$ for complex $z$.

then i think we're saying almost the same thing. just in case we have n already, how do you think can we deduce the number of polynomials that are like f(x) from there?

I'm not sure, but it seems to be an interesting problem. Maybe there is a trick which I don't see yet. But I think the $z$ with $h(z)=0$, which is also a root of $f(x)$ cannot be real. This limits the number of possible $n$, as the graph of $f(x)$ or $h(x)$ must not pass the $x-$axis. For similar reasons I think (but am not sure yet), that $r$ has to be $\pm 1$. That would leave us with very special cases for $h(x)$ and therefore also for $f(x)$.

 

[Terrell]

Yes. I think it's easier to keep $g(x)=x(2x^2+1)$ where possible, so $q(x)f(x)=q(x)x^nh(x)=f(g(x))=g(x)^nh(g(x))=x^n(2x^2+1)^nh(g(x))$.
Now $x^n$ can be divided and we are left with $h(x)$ and $h(g(x))\cdot (2x^2+1)^n=q(x)\cdot h(x)$.
Here we can look for the highest and lowest terms of $q(x)$. The lowest is easy, as it is $h(g(0)) = h(0) = q(0) \cdot h(0)$ and $h(0) \neq 0$. For the highest some considerations on the degrees of the polynomials involved might be necessary. And we can investigate the solutions of $h(z)=0$. First with $z \in \mathbb{R}$ and then with $z=r\cdot e^{i\varphi}$ for complex $z$.I'm not sure, but it seems to be an interesting problem. Maybe there is a trick which I don't see yet. But I think the $z$ with $h(z)=0$, which is also a root of $f(x)$ cannot be real. This limits the number of possible $n$, as the graph of $f(x)$ or $h(x)$ must not pass the $x-$axis. For similar reasons I think (but am not sure yet), that $r$ has to be $\pm 1$. That would leave us with very special cases for $h(x)$ and therefore also for $f(x)$.

there's a solution to this problem, i am just not quite ready to give up just yet. i'll get back to this problem once i have gained more experience and knowledge. i'll make sure that i update this post.

 

[fresh_42]

I think I got it. Consider $a_n := \sqrt[n]{i}\cdot 2^{-\frac{1}{2n}}$ and $f(a_n^n)\cdot q(a_n^n)=f(g(a_n^n))$ and next the iteration of $f(a)=0$.

 

[Terrell]

I think I got it. Consider $a_n := \sqrt[n]{i}\cdot 2^{-\frac{1}{2n}}$ and $f(a_n^n)\cdot q(a_n^n)=f(g(a_n^n))$ and next the iteration of $f(a)=0$.

please elaborate. i do not understand where that came from and do you have a value for it?

 

[fresh_42]

With $a_n:=\sqrt[n]{i}\cdot 2^{-\frac{1}{2n}}$ we get for the integer polynomial $f(x) \in \mathbb{Z}[x] \subseteq \mathbb{Q}[x] \subseteq \mathbb{C}[x]$ with $f(x)\cdot q(x)=f(g(x))$ and $g(x)=2x^3+x=x \cdot (2x^2+1)$
$$g(a_n^n)=a_n^n\cdot (2a_n^{2n}+1)=a_n^n \cdot (2(a_n^n)^2+1)= a_n^n \cdot (2\cdot i^2 \cdot \frac{1}{\sqrt{2}^2}+1)=0$$
and thus $f(a_n^n)\cdot q(a_n^n)=f(g(a_n^n))=f(0)\,.$ If $f(0)=0$ then we have a polynomial of finite degree on the left, that has infinitely many (complex) zeros. We don't have to bother the $i-$term which might or might not be periodic, because the real factor guarantees that all $a_n^n$ are different. So $f(x)=0$ in this case, which is a possible solution. Hence we may assume $f(0)\neq 0\,.$

Now we can consider an arbitrary zero of $f(x)$, say $f(a)=0$. By our assumption $a \neq 0$. The functional equation gives us $0=f(a)q(a)=f(g(a))$ which we can iterate to $f(g^k(a))=f(\underbrace{g( \ldots (g}_{k-\textrm{times}}(a)\ldots ))=0$ with all $g^k(a) \neq 0$.
For a polynomial of finite degree, this can only be true if $g^k(a)=g^l(a)$ for some $k,l$ or $g^n(a)=1$ for some $n \geq 0$.
So $g(a)=a^3+a$ is a $n-$th root of unity.

Now I'm stuck, because I had a typo in my draft (sorry). However, it reduces the number of possibilities a lot, because we know all these roots and the requirement $f(x)\; , \;f(g(x)) \in \mathbb{Z}[x]$ should give further hints.

 

[Terrell]

With $a_n:=\sqrt[n]{i}\cdot 2^{-\frac{1}{2n}}$ we get for the integer polynomial $f(x) \in \mathbb{Z}[x] \subseteq \mathbb{Q}[x] \subseteq \mathbb{C}[x]$ with $f(x)\cdot q(x)=f(g(x))$ and $g(x)=2x^3+x=x \cdot (2x^2+1)$

well at least you're still running with ideas. how did you get a_n? that baffles me

 

[fresh_42]

I was looking for the zeros of $2x^3+x$. The factor $2$ contradicts the iteration idea of $f(x)q(x)=f(g(x))$ somehow, because it separates the zeros and we cannot have infinitely many of them so they must cycle. Perhaps further considerations on the period $n$ in combination with $\deg f=1,000$ give more conclusions. The $2$ is really disturbing and the chance to narrow it down. (And it's an exciting riddle.)

 

[Buffu]

I was looking for the zeros of $2x^3+x$. The factor $2$ contradicts the iteration idea of $f(x)q(x)=f(g(x))$ somehow, because it separates the zeros and we cannot have infinitely many of them so they must cycle. Perhaps further considerations on the period $n$ in combination with $\deg f=1,000$ give more conclusions. The $2$ is really disturbing and the chance to narrow it down. (And it's an exciting riddle.)

Should I post this question on MSE ?

 

[Terrell]

Should I post this question on MSE ?

source of the problem: https://brilliant.org/problems/it-isnt-easy-for-fx-to-divide-f2x3x/

 

[Terrell]

I was looking for the zeros of $2x^3+x$. The factor $2$ contradicts the iteration idea of $f(x)q(x)=f(g(x))$ somehow, because it separates the zeros and we cannot have infinitely many of them so they must cycle. Perhaps further considerations on the period $n$ in combination with $\deg f=1,000$ give more conclusions. The $2$ is really disturbing and the chance to narrow it down. (And it's an exciting riddle.)

is this a problem of transforming the roots of a polynomial?

 

[fresh_42]

is this a problem of transforming the roots of a polynomial?

I think I confused $g^n(x)$ with $g(x)^n$ so there is a flaw in the above. But it's too late here to examine it any further now. But I admit, I wouldn't have expected this answer. I'll have a closer look tomorrow.

 

[Terrell]

I think I confused $g^n(x)$ with $g(x)^n$ so there is a flaw in the above. But it's too late here to examine it any further now. But I admit, I wouldn't have expected this answer. I'll have a closer look tomorrow.

have you viewed the answer? thanks!

 

[fresh_42]

I only looked at the number. I'm too tired to look at the proof now.

 

[Terrell]

I think I confused $g^n(x)$ with $g(x)^n$ so there is a flaw in the above. But it's too late here to examine it any further now. But I admit, I wouldn't have expected this answer. I'll have a closer look tomorrow.

if you misunderstood the question. would the way you have initially understood it still make a very interesting problem that is possible to solve?

 

[fresh_42]

No, I don't think I misunderstood the question. I probably simply overlooked something in my scribbles here, e.g. this silly mistake with the powers of g. The question itself is interesting because it contains so many different aspects: polynomials, iterations, the fundamental theorem of algebra, even and odd degrees, long divisions. The proof on the site didn't look straight forward (at first glance).

 

[Stephen Tashi]

Can we characterize the particular numerical values that can be roots of $f(x)$ ?

If $r_1$ is a root of $f(x)$ then the roots of $2x^3 + x = r_1$ are also roots of $f(2x^3 + x)$
If it happens that $2x^3 + x = r_1$ has 3 identical roots all equal to $r_1$ then no new roots are implied. However, if $2x^3 + x = r_1$ were to have 3 distinct roots $r_2,r_3,r_4$ then the solutions to each of the equations $2x^3 + x = r_2,\ 2x^3 +x = r_3,\ 2x^3 + x = r_4$ would also be roots of $f(2x^3 + x)$.

So some numerical values $r_1$ might lead to cascade of other roots that would exceed 3000 total roots.

 

[Terrell]

Can we characterize the particular numerical values that can be roots of $f(x)$ ?

If $r_1$ is a root of $f(x)$ then the roots of $2x^3 + x = r_1$ are also roots of $f(2x^3 + x)$
If it happens that $2x^3 + x = r_1$ has 3 identical roots all equal to $r_1$ then no new roots are implied. However, if $2x^3 + x = r_1$ were to have 3 distinct roots $r_2,r_3,r_4$ then the solutions to each of the equations $2x^3 + x = r_2,\ 2x^3 +x = r_3,\ 2x^3 + x = r_4$ would also be roots of $f(2x^3 + x)$.

So some numerical values $r_1$ might lead to cascade of other roots that would exceed 3000 total roots.

the problem only hinted it as being a monic polynomial with integer coefficients and its leading term raised to 1000.

 

[Stephen Tashi]

the problem only hinted it as being a monic polynomial with integer coefficients and its leading term raised to 1000.

But (whether it's useful or not) do you see what I'm saying? For example if $f(x)$ has the factor $(x-1)$ and root $r = 1$ then $f(2x^3 + x)$ has the factor $(2x^3 + x - 1)$ so the roots of $2x^3 + x - 1 = 0$ are roots of $f(2x^3 + x -1)$. And $r = 1$ is also a root of $f(2x^3 + x)$ since we are assuming $f(x)$ is a factor of $f(2x^3 + x)$

 

[Terrell]

But (whether it's useful or not) do you see what I'm saying? For example if $f(x)$ has the factor $(x-1)$ and root $r = 1$ then $f(2x^3 + x)$ has the factor $(2x^3 + x - 1)$ so the roots of $2x^3 + x - 1 = 0$ are roots of $f(2x^3 + x -1)$. And $r = 1$ is also a root of $f(2x^3 + x)$ since we are assuming $f(x)$ is a factor of $f(2x^3 + x)$

hmm... interesting insight. i will keep that in mind. thank you!