Polynomials

Study Sheet

Polynomials

Newton and the roots-of-unity filter

Symmetric Functions of Roots

Tip
Newton's identities

Power sums pk=∑rikp_k = \sum r_i^k come from the Vieta sums eje_j: p1=e1p_1 = e_1, p2=e1p1−2e2p_2 = e_1p_1 - 2e_2, p3=e1p2−e2p1+3e3p_3 = e_1p_2 - e_2p_1 + 3e_3.

In plain terms. You can compute the sum of the kkth powers of the roots step by step from the coefficients — without ever finding the roots.

Example. If roots sum to e1=3e_1 = 3 and pair-sum to e2=1e_2 = 1, then p2=∑ri2=3⋅3−2⋅1=7p_2 = \sum r_i^2 = 3\cdot 3 - 2\cdot 1 = 7.

Reminder — Vieta's formulas:  r1+r2=−ba,r1r2=car_1+r_2=-\frac{b}{a},\qquad r_1 r_2=\frac{c}{a}

The Roots of Unity Filter

Concept
Extracting every nth coefficient

To sum the coefficients of x0,xn,x2n,…x^0, x^n, x^{2n},\dots in PP, average PP over the nnth roots of unity: 1n∑jP(ωj)\tfrac1n\sum_{j} P(\omega^j).

In plain terms. Plugging the symmetric roots of unity in and averaging cancels every term except the ones whose exponent is a multiple of nn.

Example. (n0)+(n3)+(n6)+⋯=13(2n+2cos⁡nπ3)\dbinom n0+\dbinom n3+\dbinom n6+\cdots = \tfrac13\big(2^n + 2\cos\tfrac{n\pi}{3}\big) via the cube roots of unity.

Formulas, Proofs & Tips

Tip
The distributive property
a(b+c)=ab+aca(b+c)=ab+ac

What it means. Multiplying a sum multiplies each piece of it.

Example. 3(x+2)=3x+63(x+2)=3x+6.

Why it works. a(b+c)a(b+c) is b+cb+c added aa times. Regrouping those copies gives bb added aa times plus cc added aa times, i.e. ab+acab+ac. It is also the area of an a×(b+c)a\times(b+c) rectangle split into two.

Tip. Distribute the sign too: −(x−4)=−x+4-(x-4)=-x+4. Run it backwards to factor.

Tip
Degree and end behaviour
deg⁡(fg)=deg⁡f+deg⁡g;leading term controls the ends\deg(fg)=\deg f+\deg g;\qquad \text{leading term controls the ends}

What it means. The highest-power term decides what the graph does far left and far right.

Example. −2x3+⋯-2x^3+\cdots rises to the left and falls to the right (odd degree, negative lead).

Why it works. For very large ∣x∣|x|, xnx^{n} dwarfs every lower power, so the leading term dominates the sum. Multiplying polynomials multiplies their leading terms, adding the exponents.

Tip. Even degree: both ends go the same way. Odd degree: opposite ways. A positive leading coefficient sends the right end up.