Skip to section
Foundationsfor rotation-free search
Section 8 of 5215% of course
Contents
Chapter 2 Section 2.2 55 min

Part I · Mathematical foundations

A polynomial is a labeled list

Move fluently between coefficient arrays, terms, and polynomial notation.

Dress an indexed list in power labels

Let's start with an array: a = [4, −2, 7, 1]. Multiply every value by the corresponding power label for its position:

position 04 × 1
+
position 1−2 × x
+
position 27 × x²
+
position 31 × x³
A(x) = 4 − 2x + 7x² + x³

The notation A(x) just gives a name to the whole polynomial. It absolutely does not mean we are required to plug in a numerical value for x. Think of it as a structured list.

Think of polynomial notation as a serialization format

A coefficient list and a polynomial expression are just two different formats carrying the exact same payload. The array stores position implicitly via its memory address. The polynomial stores position explicitly using exponents. You can translate back and forth losslessly, as long as you remember to restore any coefficients that happen to be zero.

coefficients = [4, -2, 7, 1]

# conceptual decoding
for i, coefficient in enumerate(coefficients):
    term = coefficient * x**i

enumerate perfectly exposes the two fields living inside a term: the position i and the coefficient value. This code is purely illustrative; we don't need a numerical value for x to preserve the structure.

Read a polynomial back into a list

termpositioncoefficient
404
−2x1−2
7x²27
x³31

If we read the coefficients in increasing exponent order, we recover [4, −2, 7, 1]. A bare x³ has an implied coefficient of 1. A term like −x has an implied coefficient of −1.

Worked example

Do not lose missing positions

Let's convert P(x)=5+2x³ back to a length-5 coefficient list. Positions 1, 2, and 4 are completely absent, which means their coefficients must be zero:

P ↔ [5, 0, 0, 2, 0]

Degree versus storage length

The degree is simply the highest position that has a non-zero coefficient. Our list [5,0,0,2,0] requires a storage length of 5, but its polynomial degree is only 3. It's totally fine to have trailing zero storage beyond the degree.

Check your understanding

Which list correctly represents 3 − x + 4x³?

Worked example

Canonical form vs. allocated form

The arrays [2,−1] and [2,−1,0,0] describe the exact same polynomial: 2−x, because those trailing zeros don't add any new terms. But in software, they are different allocated arrays! Algebra usually ignores trailing zero storage, but an implementation with a fixed register width definitely cannot. It's important to always state which notion of equality your current layer of code is using.

Evaluation is a completely different operation

Writing A(x) doesn't force us to choose a value for x, but we can evaluate the polynomial if an application explicitly asks for it. For A(x)=4−2x+7x²+x³, setting x=2 gives 4−4+28+8 = 36. Evaluation collapses our beautifully structured coefficient list down into a single number. For our purposes in this chapter, we strongly prefer to preserve the structure so multiplication can reliably route coefficients using their exponents.

Check your understanding

What critical information is lost when A(x) is evaluated at one chosen value for x?

Why even bother changing notation?

As a plain list, "multiplication" has no single universal meaning. Should [a₀,a₁] × [b₀,b₁] mean matching coordinate products, an outer product, or something completely different? Switching to polynomial notation locks in a very precise rule: distribute every term across every other term, then combine the ones that share equal power labels.

Section summary

  • A coefficient list and its polynomial are just two views of the exact same data.
  • Power labels preserve positions flawlessly during multiplication.
  • Missing terms mean a coefficient is zero.
  • Degree and allocated list length are related concepts, but they are absolutely different.

Repository layer · second pass

How is a polynomial just a dense list with visible position labels?

A coefficient list [a₀,a₁,…] and the polynomial a₀+a₁x+a₂x²+… carry the same finite information. Missing terms mean zero coefficients; they do not cause later positions to slide left. This is exactly how a sparse display can represent a dense array.

Moving between the forms is a serialization exercise. The list is convenient for code and memory. Polynomial notation exposes the multiplication rule that will group products for us.

Reasoning chain

  1. 1

    Create one slot for every exponent from zero through the highest shown.

  2. 2

    Place each written coefficient in its matching exponent slot.

  3. 3

    Insert zero for every missing exponent.

  4. 4

    Preserve trailing zeros when the surrounding system fixes the dimension.

Worked trace

Do not collapse missing positions

  1. Read 3 − x + 4x³.
  2. The x⁰ coefficient is 3.
  3. The x¹ coefficient is −1.
  4. x² is absent, so its coefficient is 0; x³ has coefficient 4.

Result. The dense coefficient list is [3, −1, 0, 4].

Executable lens · Python

Make the hidden state visible

coefficients = [3, -1, 0, 4]
def evaluate(coefficients, x):
    return sum(value * x**i for i, value in enumerate(coefficients))
assert evaluate(coefficients, 2) == 3 - 2 + 4 * 8

Retype this example, predict each intermediate value, and then change one input that touches a boundary.

Misconception clinic

Tempting mistakes

  • Encoding 3−x+4x³ as [3,−1,4], which moves 4 into the x² slot.
  • Dropping fixed-width trailing zeros that another component expects.

Retrieval and transfer

Close the book first

  1. Convert [0,5,0,−2] to polynomial notation.
  2. Convert 1+7x⁴ into a dense length-six list.
  3. Explain why list equality and polynomial equality agree for dense coefficients.