Polynomials as lists and power series

Polynomials are versatile and interesting objects in mathematics. A polynomial is a finite expression with the form:

$a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 + \cdots$

Polynomials represent everything we can do using only the operations of addition, subtraction, and multiplication applied finitely many times. Because of this, they naturally reside in rings - multiplying two polynomials will yield a new polynomial, and the same can be said for adding and subtracting polynomials. As elements of a ring, the factors $x, x^2, x^3, ...$ become arbitrary; so that they are just there to keep track of the coefficients $a_0, a_1, a_2, ...$. This should make sense, as $x^2 + 3x^5 -2$ is the same polynomial as $-2 + x^2 + 3x^5$. Since the order of the terms can be freely changed, we're going to stick with a pre-defined order by writing $x^n$ terms by increasing $n$ as above. This lets us ignore $x^n$ completely and write polynomials only in terms of $a_0, a_1, a_2, ...$. To take advantage of this fact, let's introduce some new notation to represent polynomials:

$1 \to [1 ]$ $x \to [0, 1 ]$ $-2 + x^2 + 3x^5 \to [-2, 0, 1, 0, 0, 3 ]$

This notation abstracts polynomials into the form of an ordered list of numbers. This is an extremely powerful idea, but here we're only going to scratch the surface of it.

We can take this notation further by introducing an "indexing" operation that extracts coefficients.

$[a_0, a_1, a_2, ... ] (x^k) = a_k$

This is defined for every $k$. If a polynomial has no term of the form $a_k x^k$, then that means $a_k = 0$. For example, consider a polynomial like $3 + 6x - x^3 + 8x^4$, which we will write as $[3, 6, 0, -1, 8]$.

$[3, 6, 0, -1, 8](x) = 6$ $[3, 6, 0, -1, 8](x^2) = 0$ $[3, 6, 0, -1, 8](x^{23456}) = 0$

This suggests that we can write these as infinite lists which terminate in a trail of 0's.

$[3, 6, 0, -1, 8] \to [3, 6, 0, -1, 8, 0, 0, 0, 0, ...]$

Addition, subtraction, and multiplication are defined like they normally are for polynomials. Showing the first two in this notation is straightforward.

$[a_0, a_1, a_2, ...] \pm [b_0, b_1, b_2, ... ] = [a_0 \pm b_0, \; a_1 \pm b_1, \; a_2 \pm b_2, \; ... ]$ $\text{e.g.} \: [0, 5, 5] + [1, 0, 1, 1, 7 ] = [1, 5, 6, 1, 7]$

Or, using coefficient extraction:

$([a_0, a_1, a_2, ...] \pm [b_0, b_1, b_2, ... ])(x^n) = a_n + b_n$

Which is just a reflection of the fact that only "like" terms can be added. Multiplication isn't immediately clear in this notation. In terms of coefficient extraction, it is:

$([a_0, a_1, a_2, ... ] \cdot [b_0, b_1, b_2, ... ])(x^n) = \displaystyle\sum_{j+k = n}^n a_j b_k$

Multiplying two polynomials happens term-wise. A term like $a_j x^j$ from the first polynomial and a term like $b_k x^k$ from the second will multiply together to give the term $a_j b_k x^{n}$ in the product, where $j+k=n$. Since $j$ and $k$ are allowed to vary, this results in a sum over all $j$ and $k$ where $j+k = n$.

Since polynomials are finite lists appended with an infinite list of zeroes, what sort of object does an infinite list of nonzero elements represent? This is a polynomial with infinitely many terms, a new kind of object known as a power series. One of the simplest of these is

$[1, 1, 1, 1, ...] = 1 + x + x^2 + x^3 + \cdots = \displaystyle\sum_{n=0}^\infty x^n$

Just from looking at this it's hard to pin down what exactly it means. Polynomials form a ring, and so do power series by extension. The identity element is then $1 \to [1, 0, 0, 0, ...]$. A natural approach would be to find the inverse of this.

$[1, 1, 1, 1, ...] \cdot [d_0, d_1, d_2, d_3, ...] = [1, 0, 0, 0, ... ]$

We can deduce $d_n$ from the multiplication formula above:

$[1, 0, 0, 0, ... ](x^0) = 1 \cdot d_0 = 1 \: \: \to \: d_0 = 1$ $[1, 0, 0, 0, ... ](x^1) = 1 \cdot d_0 + 1 \cdot d_1 = 0\: \: \to \: d_1 = -1$ $[1, 0, 0, 0, ... ](x^n) = \sum_{k=0}^n d_k = 0\: \: \to \: d_n = 0$

Which means that $[1, 1, 1, 1, ...] \cdot [1, -1, 0, 0, ...] = [1, 0, 0, 0, ... ]$, or:

$\displaystyle\sum_{n=0}^\infty x^n = \frac{1}{1-x}$

This is true, but since the meaning of $x^n$ is being abstracted here, taking $x$ as a literal numerical value won't always work. To see why, simply plug in something like $x=2$ and watch the lefthand side diverge rapidly. To find what limitations to place on the value of $x$, we can consider a finite polynomial approximation of $1, 1, 1, ...$. For example, one with five terms.

$[1, 1, 1, 1, 1] \approx [1, 1, 1, ...]$ $[1, 1, 1, 1, 1] \cdot [1, -1] = [1, 0, 0, 0, 0, -1]$

There's now an error term at the very end that's not present in the infinite case. When $|x| > 1$, this error term diverges, and this divergence gets worse as the approximation becomes better. This is because $|x^n| > |x^{n-1}|$ when $|x| > 1$. $|x| = 1$ trivially doesn't work either, since $\frac{1}{1-x}$ has a singularity there. Ultimately, this will only hold when $|x| < 1$.

From this series we can build others. For example,

$[1, a, a^2, a^3, a^4, ...] = \displaystyle\sum_{n=0}^\infty (ax)^n = \frac{1}{1-ax}$

Which is valid when $|x| < 1/a$. This shows a direct relationship between the growth of a power series' coefficients and the location of its singularities.

Derivatives can also come into play:

$\frac{d}{dx} \displaystyle\sum_{n=0}^\infty x^n = \frac{d}{dx} \frac{1}{1-x}$ $\displaystyle\sum_{n=1}^\infty n x^{n-1}= [1, 2, 3, 4, 5, ...] = \frac{1}{(1-x)^2}$

In general,

$\displaystyle\sum_{k=0}^\infty \binom{k+n}{k} x^k = \frac{1}{(1-x)^n}$

Antiderivation can be done as well, and this leads to a series for the logarithm:

$\displaystyle\int \displaystyle\sum_{n=0}^\infty x^n dx = \displaystyle\int \frac{dx}{1-x}$ $\displaystyle\sum_{k=1}^\infty \frac{x^k}{k} = [0, 1, 1/2, 1/3, 1/4, ...] = \ln \left( \frac{1}{1-x} \right)$

Power series can be used to represent functions that are clearly non-polynomial. This effectively translates nontrivial functions into the "language" of polynomials, which opens them up for a much deeper analysis.

This treatment can be done for more interesting sequences than $[1,1,1,1,...]$. This is where this approach really shines - encoding sequences as a power series can lead to non-trivial information about that sequence. This is the main theme of analytic combinatorics, a branch of mathematics that studies this connection. Here's a well-known example of what I'm talking about: deriving an explicit formula for the Fibonacci numbers. These are defined by:

$f_n = f_{n-1} + f_{n-2}$ $f_0 = 1$ $f_1 = 1$

The first few numbers of this sequence are $[1,1,2,3,5,8,13,21,34,...]$. As a power series, it's not immediately obvious what function this represents, but we can apply the same procedure above by finding its multiplicative inverse:

$[1,1,2,3,5,8,13,21,34,...] \cdot [d_0, d_1, d_2, ...] = [1, 0, 0, ...]$ $d_0 = 1$ $d_0 + d_1 = 0 \to \: d_1 = -1$ $2d_0 + d_1 + d_2 = 0 \to \: d_2 = -1$ $3d_0 + 2d_1 + d_2 + d_3 = f_3 - f_2 - f_1 = 0 \to \: d_3 = 0$

The last step suggests how to continue this for any $d_n$. The recurrence relation above for the Fibonacci sequence ensures that $f_n - f_{n-1} - f_{n-2} = 0$ for all $n \ge 2$, which implies that the rest of the $d_n$ are 0.

$[1,1,2,3,5,8,13,21,34,...] \cdot [1, -1, -1, 0, 0, 0...] = [1, 0, 0, ...]$ $[1,1,2,3,5,8,13,21,34,...] = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + \cdots = \frac{1}{1-x-x^2}$

I mentioned above that the singularities of a function give us information about its coefficients. In this case, the singularities are enough to completely determine them. Since the denominator is a quadratic polynomial, it has two zeroes and thus the function has two singularities. We can separate them by factoring the denominator and decomposing the fraction.

$\frac{1}{1-x-x^2} = \frac{-1}{(x - \frac{-1 + \sqrt{5}}{2})(x - \frac{-1 - \sqrt{5}}{2})} = \frac{1}{\sqrt{5}}\left( \frac{1}{x - \frac{-1 - \sqrt{5}}{2}} - \frac{1}{x - \frac{-1 + \sqrt{5}}{2}} \right)$

The terms $\frac{1}{x - \frac{-1 \pm \sqrt{5}}{2}}$ can be written as a power series. Setting $\phi_{\pm} = \frac{-1 \pm \sqrt{5}}{2}$ for brevity,

$[1,1,2,3,5,8,13,21,34,...] = \frac{1}{\sqrt{5}}\left( \frac{1}{x - \phi_-} - \frac{1}{x - \phi_+} \right)$ $= \frac{1}{\sqrt{5}}\left( \displaystyle\sum_{k=0}^\infty \frac{x^k}{\phi_+^{k +1}} - \displaystyle\sum_{k=0}^\infty \frac{x^k}{\phi_-^{k +1}} \right)$

Extracting the coefficients of both sides gives us a closed formula for the nth Fibonacci number:

$[1,1,2,3,5,8,13,21,34,...](x^n) = f_n = \frac{1}{\sqrt{5}} \left( \phi_+^{-n-1} - \phi_-^{-n -1} \right) = \frac{1}{\sqrt{5}} \left( ( \frac{2}{-1 + \sqrt{5}})^{n+1} - ( \frac{2}{-1 - \sqrt{5}})^{n +1} \right)$