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

Note by Levi Walker
2 months, 2 weeks ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
• Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

WOW!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! (expressing happiness that is boundless, not anger), @Levi Walker

- 2 months, 2 weeks ago

I'm glad you like it! Definitely check out the book Analytic Combinatorics by Flajolet if you're interested in the subject, I've been reading it lately and I definitely plan to write more notes on it :)

- 2 months, 2 weeks ago

Any downloadable E-book for Analytic Combinatorics without payment? - I am insane about PDFs (recently went on a PDF spree and downloaded all the free UKMT past papers and the IMO papers) - any websites or tips to avoid payment will be nice as well. Also, I'm hoping to research Riemann's hypothesis when I get back to Year 11 school life and check out A Perfect Factorial Number (the discussion) @Levi Walker

- 2 months, 2 weeks ago

Luckily Flajolet has it up for free on his website: http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html

- 2 months, 2 weeks ago

×