3
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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.) $\endgroup$ – Thomas Andrews Jul 18 '19 at 14:55
  • 2
    $\begingroup$ Is this math.stackexchange.com/a/672847/42969 the answer to your question? $\endgroup$ – Martin R Jul 18 '19 at 14:57
  • $\begingroup$ It would be interesting to learn what is known about solving such problems with integer coefficients. $\endgroup$ – hardmath Jul 18 '19 at 15:53
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Jul 18 '19 at 16:18
  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews Jul 18 '19 at 17:19
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.