1. Jan 23, 2017

Terrell

1. The problem statement, all variables and given/known data
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
2. Relevant equations
remainder factor theorem

3. 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.

2. Jan 23, 2017

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.

3. Jan 23, 2017

Terrell

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.

4. Jan 23, 2017

Staff: Mentor

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.

5. Jan 23, 2017

Terrell

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

6. Jan 23, 2017

Staff: Mentor

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

7. Jan 23, 2017

Buffu

8. Jan 23, 2017

Staff: Mentor

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$.

9. Jan 24, 2017

Terrell

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.

10. Jan 24, 2017

Staff: Mentor

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.

11. Jan 24, 2017

Terrell

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.

12. Jan 24, 2017

Terrell

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

13. Jan 24, 2017

Staff: Mentor

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$.

14. Jan 24, 2017

Terrell

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))?

15. Jan 24, 2017

Terrell

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?

16. Jan 24, 2017

Staff: Mentor

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)$.

17. Jan 27, 2017

Terrell

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.

18. Jan 28, 2017

Staff: Mentor

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$.

19. Jan 28, 2017

Terrell

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

20. Jan 28, 2017

Staff: Mentor

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.

21. Jan 28, 2017

Terrell

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

22. Jan 28, 2017

Staff: Mentor

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.)

23. Jan 28, 2017

Buffu

Should I post this question on MSE ?

24. Jan 28, 2017

Terrell

25. Jan 28, 2017

Terrell

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