Products add, composition multiplies

There are two ways to put two polynomials together. Multiply them, $x \mapsto p(x)q(x)$, or compose them, $x \mapsto p(q(x))$. Both give you a polynomial back. Both are older than algebra. And they do completely different things to the degree.

$\deg(p \cdot q) = \deg p + \deg q, \qquad \deg(p \circ q) = \deg p \cdot \deg q.$

interactive · the degree of a product and the degree of a compositionopen ↗

Interactive demo: the degree of a product and the degree of a composition. Requires JavaScript to run — the source is at /interactive/funcspace/degree-arithmetic.html.

The demo lets you set $\deg p$ and $\deg q$ independently and watch the two answers come out of the coefficient array. The bars are aligned by power of $x$: the grey series is $p\cdot q$, which stops at $x^{m+n}$, and the orange is $p \circ q$, which runs all the way out to $x^{mn}$. Set both degrees to 4 and the product ends at $x^8$ while the composition ends at $x^{16}$.

Neither law is deep, but both have the same load-bearing hypothesis, and it is easy to miss. For the product, the top coefficient is $c_m d_n$, the two leading coefficients multiplied. For the composition, plugging $q$ into the highest term $c_m x^m$ gives $c_m (d_n x^n + \cdots)^m$, whose top coefficient is $c_m d_n^{\,m}$. In both cases the answer is a product of nonzero numbers, and the laws hold because a product of nonzero numbers is nonzero. Over the reals that is invisible. Over the integers mod 6, where $2 \cdot 3 = 0$, it fails: $2x$ and $3x$ both have degree 1, and their product is the zero polynomial, of degree $-\infty$. The degree laws are a statement about the coefficient ring being an integral domain, dressed up as a statement about polynomials.

Look at the product from the coefficient side and it is a convolution. If $p$ has coefficients $c_0, \ldots, c_m$ and $q$ has $d_0, \ldots, d_n$, then

$(p\cdot q)_k = \sum_{i+j=k} c_i\, d_j,$

which is exactly the operation you perform when you multiply two integers in long form without carrying, and exactly the operation two probability distributions undergo when you add independent random variables. The length of the result is $(m+1) + (n+1) - 1$, one less than the sum of the lengths, which is the coefficient-counting version of degrees adding. Multiplication of polynomials, convolution of sequences, and addition of degrees are three views of one thing.

Composition has no such formula. There is no tidy expression for the $k$-th coefficient of $p \circ q$ in terms of the coefficients of $p$ and $q$ — you get one by summing over all the ways to choose a term from each of $m$ copies of $q$, which is the multinomial expansion, and it is a mess. What is tidy is the degree, precisely because the mess cannot cancel at the top.

Here is the part worth the price of admission. Suppose $p$ and $q$ are polynomials with $p \circ q = x$, the identity: $q$ is a genuine inverse function for $p$, and it is itself a polynomial. Take degrees. Then $\deg p \cdot \deg q = 1$, a product of two non-negative integers equal to one, so $\deg p = \deg q = 1$. Both are affine. There is no cubic whose inverse is a polynomial, no quintic, nothing. The cube root of $x$ is a perfectly good function and it is not a polynomial, and the reason is a fact about the integer 1 having only one factorization. That is the whole proof. Nothing about calculus, nothing about the graph, nothing about $\mathbb{R}$ — just the degree law, which is a homomorphism from composition of polynomials to multiplication of integers, and a homomorphism carries invertible things to invertible things. The only invertible element of $(\mathbb{N}, \times)$ is 1, and so the only invertible polynomials under composition are the degree-one ones, which is to say the affine group of the previous article, arrived at from a completely different direction.

It is worth being precise about what kind of maps these two operations are. Multiplication by a fixed $q$ is linear in $p$, and it has a matrix — a banded, lower-triangular-ish one, the convolution matrix, with $q$‘s coefficients repeated down each diagonal. Composition is linear in the outer argument and violently nonlinear in the inner one:

$(p_1 + p_2) \circ q = p_1 \circ q + p_2 \circ q, \qquad p \circ (q_1 + q_2) \neq p \circ q_1 + p \circ q_2.$

The first is why substituting a fixed map into a polynomial has a matrix at all, which is what made the whole of the previous article possible. The second is why composition is the hard operation, and why iterating a map — $q \circ q \circ q \circ \cdots$, degrees multiplying, $n, n^2, n^3, \ldots$ — leaves linear algebra behind almost immediately. A quadratic iterated twenty times has degree $2^{20}$, more than a million, with a million-odd coefficients you will never write down and roots you cannot solve for. That object is the Mandelbrot set’s twentieth-level structure, and the reason it is worth looking at rather than computing is that its degree grew exponentially while its definition did not grow at all.

Both operations are associative, both have an identity ($1$ for the product, $x$ for composition), and the two distribute over each other in exactly one direction, $(p \cdot q) \circ r = (p \circ r)\cdot(q \circ r)$, which says that substituting into a product is the product of substitutions. Sitting on the same set are a commutative monoid whose grading adds and a non-commutative monoid whose grading multiplies, glued by that one distributive law. Degree is the only map that sees both structures, sending one to $(\mathbb{N}, +)$ and the other to $(\mathbb{N}, \times)$, and it is not an accident that those two are the same set: the exponential $n \mapsto 2^n$ takes one to the other, and that exchange is the last article in this series.