3

When can a polynomial be written as a polynomial function of another polynomial? asks whether, given $p$ and $q$ polynomials, there is a polynomial $w$ with $$ p(x) = w(q(x)) $$ which is a good question with a nice answer. We can try to generalize to ask:

Given a polynomial $p$, do there exist polynomials $q$ and $w$ with $$ p(x) = w(q(x)). $$

That is to say, we can ask the question not for a specific $q$, but ask whether any such $q$ exists.

Alas, that question isn't interesting, for $q(x) = x$ and $w = p$ provides a solution for any $p$; indeed, we can let $q$ be any linear polynomial $q(x) = ax + b$ with $a \ne 0$ and then find $w$ (assuming we're working over a field, which is the case I'm thinking of), essentially by substitution. So my question is this:

Given a polynomial $p$ over a field, is there a (relatively easy) way to determine whether there's a non-linear polynomial $q$ and some polynomial $w$ with the property that $$p(x) = w(q(x))?$$

I'd be happy with an answer even over some specific field like $\Bbb R$ or $\Bbb C$.

John Hughes
  • 93,729
  • Since $\deg p = \deg w\cdot \deg q$ it it is necessary that $\deg p$ is not prime. This is far from sufficient. (And this assumes both $q$ and $w$ are non-linear.) – Thomas Andrews Jul 18 '19 at 14:55
  • 2
    Is this https://math.stackexchange.com/a/672847/42969 the answer to your question? – Martin R Jul 18 '19 at 14:57
  • It would be interesting to learn what is known about solving such problems with integer coefficients. – hardmath Jul 18 '19 at 15:53
  • There are efficient polynomial decomposition algorithms due to Ritt, Barton and Zippel, Kozen and Landau, etc, e.g. see here.. These are used in computer algebra systems. – Bill Dubuque Jul 18 '19 at 16:18
  • @ThomasAndrews: the final question explicitly requires $q$ non-linear. – John Hughes Jul 18 '19 at 16:38
  • @MartinR: thanks -- that's exactly what I was looking for. If you'd like to turn that pointer into an answer, I'll accept it; if not, I'll do so via a community-wiki answer, so that the question gets closed out. – John Hughes Jul 18 '19 at 16:39
  • 1
    When $p(x)=w(q(x))$ has $p'(x)=w'(q(x))q'(x),$ When $p,w,q\in\mathbb Q[x]$, then if $p'(x)$ is irreducible then $p(x)$ can't be written in this form. – Thomas Andrews Jul 18 '19 at 17:19

1 Answers1

1

@MartinR points out that math.stackexchange.com/a/672847/42969 answers my question quite well (with a solution developed by someone who was a high-school student at the time!)

@BillDubuque points out that computer algebra systems have algorithms to do this kind of thing as well, like this.

John Hughes
  • 93,729