# What's polynomial composition useful for?

I've made this question here. But I got no answer then I'll make a question with it:

I remember of studying:

• Sum of two polynomials;
• Difference of two polynomials;
• Product of a constant and a polynomial;
• Product of two polynomials;

And they kinda make sense for me, but I have a doubt on composition of two polynomials, what is composition of two polynomials useful for?

EDIT: This image made me understande it more easily, I've found it on wikipedia.

-
Composition of functions is an important operations. Every polynomial induces a polynomial function by evaluation, and the composition of two polynomial functions is again a polynomial function, corresponding to the composition of the polynomials. – Arturo Magidin Jul 24 '12 at 19:16
Simple shift of argument is given by a composition of two polynomials. Well, one of them simple. – Sasha Jul 24 '12 at 19:17
You may as well ask why composition of functions is useful. Is there some reason why you are particularly interested in the special case of composition of polynomial functions? Perhaps you didn't notice that polynomial composition may be viewed as a special case of composition of functions? – Bill Dubuque Jul 24 '12 at 19:46
You can create formal group laws with polynomial composition. – anon Jul 24 '12 at 20:34
@BillDubuque I'm reading Barbeau's polynomials. In the page I'm in, he said only about composition of two polynomials. – Voyska Jul 24 '12 at 23:07

Composition of polynomials is usually used when we have two polynomial functions, say $f(x)$ and $g(x)$, and we wish to perform something like:

$$f(g(x))=(f\circ g)(x),$$

If we needed to know the result of this for some value of $x$, we could of course simply compute $g(x)$ and then use this as our argument $x$ in $f(x)$.

However, say we are writing a computer program, and we need to calculate $f(g(x))$ several thousand times over the course of the program. Computing $g(x)$ for each value of $x$ first, and then computing $f(g(x))$ based on the output of $g(x)$ can be expensive. A much more efficient approach would be to sit down and actually perform the composition of the two polynomials (which will result in a polynomial of degree $\deg{f} + \deg{g}$), $(f\circ g)(x)$.

Of course, the difference in efficiency here would be fairly negligible, but it is just a simple example of where you could encounter polynomial composition.

EDIT: Incorrect. The output degree is $\deg{f} \times \deg{g}$. In general, the composition written out contains much more terms than the two separate, so it is not useful to expand them. In fact, there are algorithms that explicitly rely on iteration or composition because it is an efficient and numerically stable way to construct polynomials of very high degree.

-

It might be very useful if you need to make a substitution in an integral. Say you need to substitute $y=x^2+1$ to make part of the integral simpler, and then you need to do the same in another part of the integrand, which happens to be another polynomial.

-
But what are integrals useful for? :) – Bruno Joyal Jul 24 '12 at 22:17
@Bruno What you mean? – Voyska Jul 25 '12 at 1:50

Iteration is a special case of composition (namely, composition with itself). Studying $$f(x), f(f(x)), f(f(f(x)))...$$ is an entire field, see for example Mandelbrot sets and Julia sets. Now, a special case of the latter is Newtons method on solving polynomial equations numerically: every time you ask your calculator to numerically solve a polynomial equation, it will most likely use repeated polynomial composition somewhere in the algorithm. (This is a bit rough, what really is done is a bit more involved).

-