Polynomials as lists and power series

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

a0+a1x+a2x2+a3x3+a4x4+ 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,x2,x3,...x, x^2, x^3, ... become arbitrary; so that they are just there to keep track of the coefficients a0,a1,a2,...a_0, a_1, a_2, .... This should make sense, as x2+3x52x^2 + 3x^5 -2 is the same polynomial as 2+x2+3x5-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 xnx^n terms by increasing nn as above. This lets us ignore xnx^n completely and write polynomials only in terms of a0,a1,a2,...a_0, a_1, a_2, .... To take advantage of this fact, let's introduce some new notation to represent polynomials:

1[1] 1 \to [1 ] x[0,1] x \to [0, 1 ] 2+x2+3x5[2,0,1,0,0,3] -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.

[a0,a1,a2,...](xk)=ak [a_0, a_1, a_2, ... ] (x^k) = a_k

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

[3,6,0,1,8](x)=6 [3, 6, 0, -1, 8](x) = 6 [3,6,0,1,8](x2)=0 [3, 6, 0, -1, 8](x^2) = 0 [3,6,0,1,8](x23456)=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][3,6,0,1,8,0,0,0,0,...] [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.

[a0,a1,a2,...]±[b0,b1,b2,...]=[a0±b0,  a1±b1,  a2±b2,  ...] [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, \; ... ] e.g.[0,5,5]+[1,0,1,1,7]=[1,5,6,1,7] \text{e.g.} \: [0, 5, 5] + [1, 0, 1, 1, 7 ] = [1, 5, 6, 1, 7]

Or, using coefficient extraction:

([a0,a1,a2,...]±[b0,b1,b2,...])(xn)=an+bn ([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:

([a0,a1,a2,...][b0,b1,b2,...])(xn)=j+k=nnajbk ([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 ajxja_j x^j from the first polynomial and a term like bkxkb_k x^k from the second will multiply together to give the term ajbkxna_j b_k x^{n} in the product, where j+k=nj+k=n. Since jj and kk are allowed to vary, this results in a sum over all jj and kk where j+k=nj+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+x2+x3+=n=0xn [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[1,0,0,0,...]1 \to [1, 0, 0, 0, ...] . A natural approach would be to find the inverse of this.

[1,1,1,1,...][d0,d1,d2,d3,...]=[1,0,0,0,...] [1, 1, 1, 1, ...] \cdot [d_0, d_1, d_2, d_3, ...] = [1, 0, 0, 0, ... ]

We can deduce dnd_n from the multiplication formula above:

[1,0,0,0,...](x0)=1d0=1d0=1 [1, 0, 0, 0, ... ](x^0) = 1 \cdot d_0 = 1 \: \: \to \: d_0 = 1 [1,0,0,0,...](x1)=1d0+1d1=0d1=1 [1, 0, 0, 0, ... ](x^1) = 1 \cdot d_0 + 1 \cdot d_1 = 0\: \: \to \: d_1 = -1 [1,0,0,0,...](xn)=k=0ndk=0dn=0 [1, 0, 0, 0, ... ](x^n) = \sum_{k=0}^n d_k = 0\: \: \to \: d_n = 0

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

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

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

[1,1,1,1,1][1,1,1,...] [1, 1, 1, 1, 1] \approx [1, 1, 1, ...] [1,1,1,1,1][1,1]=[1,0,0,0,0,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|x| > 1, this error term diverges, and this divergence gets worse as the approximation becomes better. This is because xn>xn1|x^n| > |x^{n-1}| when x>1|x| > 1. x=1|x| = 1 trivially doesn't work either, since 11x \frac{1}{1-x} has a singularity there. Ultimately, this will only hold when x<1 |x| < 1.

From this series we can build others. For example,

[1,a,a2,a3,a4,...]=n=0(ax)n=11ax [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 |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:

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

In general,

k=0(k+nk)xk=1(1x)n \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:

n=0xndx=dx1x \displaystyle\int \displaystyle\sum_{n=0}^\infty x^n dx = \displaystyle\int \frac{dx}{1-x} k=1xkk=[0,1,1/2,1/3,1/4,...]=ln(11x) \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,...] [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:

fn=fn1+fn2 f_n = f_{n-1} + f_{n-2} f0=1 f_0 = 1 f1=1 f_1 = 1

The first few numbers of this sequence are [1,1,2,3,5,8,13,21,34,...][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,...][d0,d1,d2,...]=[1,0,0,...] [1,1,2,3,5,8,13,21,34,...] \cdot [d_0, d_1, d_2, ...] = [1, 0, 0, ...] d0=1 d_0 = 1 d0+d1=0d1=1 d_0 + d_1 = 0 \to \: d_1 = -1 2d0+d1+d2=0d2=1 2d_0 + d_1 + d_2 = 0 \to \: d_2 = -1 3d0+2d1+d2+d3=f3f2f1=0d3=0 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 dnd_n. The recurrence relation above for the Fibonacci sequence ensures that fnfn1fn2=0f_n - f_{n-1} - f_{n-2} = 0 for all n2n \ge 2, which implies that the rest of the dnd_n are 0.

[1,1,2,3,5,8,13,21,34,...][1,1,1,0,0,0...]=[1,0,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+2x2+3x3+5x4+8x5+=11xx2 [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.

11xx2=1(x1+52)(x152)=15(1x1521x1+52) \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 1x1±52 \frac{1}{x - \frac{-1 \pm \sqrt{5}}{2}} can be written as a power series. Setting ϕ±=1±52 \phi_{\pm} = \frac{-1 \pm \sqrt{5}}{2} for brevity,

[1,1,2,3,5,8,13,21,34,...]=15(1xϕ1xϕ+) [1,1,2,3,5,8,13,21,34,...] = \frac{1}{\sqrt{5}}\left( \frac{1}{x - \phi_-} - \frac{1}{x - \phi_+} \right) =15(k=0xkϕ+k+1k=0xkϕk+1) = \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,...](xn)=fn=15(ϕ+n1ϕn1)=15((21+5)n+1(215)n+1) [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 weeks, 4 days ago

No vote yet
1 vote

  Easy Math Editor

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. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

Yajat Shamji - 2 weeks, 3 days ago

Log in to reply

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

Levi Walker - 2 weeks, 3 days ago

Log in to reply

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

Yajat Shamji - 2 weeks, 2 days ago

Log in to reply

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

Levi Walker - 2 weeks, 2 days ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...