Day 15 — Polynomials

Day 15 — Polynomials

Stage II · concept day
Goal: Define polynomials; identify degree and leading coefficient; add and multiply; evaluate efficiently with Horner; preview roots vs factors; perform one polynomial long division.

Why this matters

Polynomials model discrete sums, generating functions (later), Taylor truncations, and simple regressions. Horner’s method is how CPUs and libraries evaluate polynomials with minimal multiplies. Factor/root links unlock equation solving (Day 16).

Theory

Definition

A polynomial in \(x\) over \(\mathbb{R}\) (or \(\mathbb{Q}\), \(\mathbb{Z}\)) is \[p(x)=a_n x^n+a_{n-1}x^{n-1}+\cdots+a_1 x+a_0\] with coefficients \(a_i\) and \(n\in\mathbb{Z}_{\ge 0}\). The zero polynomial is \(p\equiv 0\).

• Degree \(\deg(p)=n\) if \(a_n\neq 0\) (leading coefficient \(a_n\)).
  
• \(\deg(0)\) is defined as \(-\infty\) or left undefined—by convention \(\deg(0)<\) all others.
  
• Monic: leading coefficient \(1\).
  
• Constant polynomials: degree \(0\) if nonzero.

Equality

Two polynomials are equal iff corresponding coefficients are equal (as formal polynomials / as functions on infinite fields like \(\mathbb{R}\)).

Addition and scalar multiplication

Add coefficients of like powers.
\(\deg(p+q)\le \max(\deg p,\deg q)\), with equality unless leading terms cancel.

Multiplication

\[ \biggl(\sum_{i=0}^{n}a_i x^i\biggr)\biggl(\sum_{j=0}^{m}b_j x^j\biggr)=\sum_{k=0}^{n+m}\biggl(\sum_{i+j=k}a_i b_j\biggr)x^k. \]

Theorem. If \(p,q\neq 0\), then \(\deg(pq)=\deg p+\deg q\), over integral domains like \(\mathbb{R}[x]\) (no zero divisors).

Proof idea. Leading term \(a_n b_m x^{n+m}\) with \(a_n b_m\neq 0\). \(\square\)

Evaluation

\(p(c)\) is the number obtained by substituting \(x=c\).
Remainder theorem preview: dividing by \(x-c\) leaves remainder \(p(c)\) (see division).

Horner’s method

\[p(x)=a_n x^n+\cdots+a_0=(\cdots((a_n x+a_{n-1})x+a_{n-2})\cdots)x+a_0.\]

Same structure as Day 6 base conversion. About \(n\) multiplies and \(n\) adds for degree \(n\).

Roots and factors (preview)

\(c\) is a root (zero) of \(p\) if \(p(c)=0\).
Factor theorem (statement): \(p(c)=0\) iff \((x-c)\) divides \(p(x)\) (proved via division algorithm for polynomials).

Polynomial division (lite)

Divide \(p\) by nonzero \(d\): unique \(q,r\) with \[p=d\cdot q+r,\qquad r=0\text{ or }\deg r<\deg d.\]

Long division: mimic integer division—leading term of current dividend over leading term of divisor; multiply; subtract; repeat.

Example setup: divide \(x^3+0x^2-x-1?\) wait standard: \(x^2+3x+2\) by \(x+1\), etc.

Special products (recall)

\((x+a)(x+b)=x^2+(a+b)x+ab\).
\((x+a)^2=x^2+2ax+a^2\).
\((x+a)^3=x^3+3ax^2+3a^2x+a^3\).
\(x^3\pm y^3=(x\pm y)(x^2\mp xy+y^2)\).
\(x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\cdots+y^{n-1})\).

Remainder and factor theorems (formal)

Division algorithm. For \(p,d\in\mathbb{R}[x]\) with \(d\neq 0\), there exist unique \(q,r\) with \(p=dq+r\) and \(r=0\) or \(\deg r<\deg d\).

Remainder theorem. Dividing by \(x-c\) gives remainder \(p(c)\): \(p(x)=(x-c)q(x)+p(c)\).
Proof. Apply division: remainder is constant \(r\); set \(x=c\): \(p(c)=r\). \(\square\)

Factor theorem. \(p(c)=0\) iff \((x-c)\) divides \(p\) in \(\mathbb{R}[x]\).
Proof. Remainder theorem: \(p(c)=0\) iff remainder \(0\) iff \((x-c)\) divides \(p\). \(\square\)

At most \(n\) roots

Theorem. A nonzero polynomial of degree \(n\) over \(\mathbb{R}\) (or any field) has at most \(n\) roots.
Proof. If \(p(c_1)=0\), write \(p=(x-c_1)q_1\) with \(\deg q_1=n-1\). Induct: each new distinct root factors out another linear factor; after \(n+1\) distinct roots, \(p\) would be zero polynomial. \(\square\)

Leading-term asymptotics (lite)

For large \(|x|\), \(p(x)\sim a_n x^n\): the sign of \(p(x)\) for large positive \(x\) matches \(\operatorname{sign}(a_n)\); for large negative \(x\) it matches \(\operatorname{sign}(a_n(-1)^n)\). End behavior of graphs follows.

Worked examples

Example 1 — Degree

\(p(x)=4x^3-x+7\): degree \(3\), leading coefficient \(4\), constant term \(7\).

Example 2 — Add

\((2x^2+3x-1)+(-2x^2+x+5)=4x+4\). Degree drops due to cancellation.

Example 3 — Multiply

\((x+2)(x^2-x+3)=x^3-x^2+3x+2x^2-2x+6=x^3+x^2+x+6\).

Example 4 — Evaluate naive

\(p(x)=2x^3-5x+1\) at \(x=3\): \(2\cdot 27-15+1=54-15+1=40\).

Example 5 — Horner

Coefficients \(2,0,-5,1\) for \(2x^3+0x^2-5x+1\) at \(x=3\):
\(2\); \(2\cdot3+0=6\); \(6\cdot3+(-5)=13\); \(13\cdot3+1=40\).

Example 6 — Root check

\(p(x)=x^2-5x+6\), \(p(2)=4-10+6=0\). Root \(x=2\). Factors \((x-2)(x-3)\).

Example 7 — Long division

Divide \(p(x)=x^3-2x^2-x+2\) by \(d(x)=x-1\).

• \(x^3/x=x^2\); multiply \(x^2(x-1)=x^3-x^2\); subtract: \(-x^2-x+2\) wait: \((-2x^2)-(-x^2)=-x^2\).
  
• \(-x^2/x=-x\); \((-x)(x-1)=-x^2+x\); subtract: \((-x)-(+x)=-2x\), bring \(+2\): \(-2x+2\).
  
• \(-2x/x=-2\); \((-2)(x-1)=-2x+2\); subtract \(0\).

Quotient \(x^2-x-2\), remainder \(0\). So \(p(x)=(x-1)(x^2-x-2)\).

Example 8 — Remainder

\(p(x)=x^2+x+1\) divided by \(x-2\): \(p(2)=7\), so \(p(x)=(x-2)(x+3)+7\) check: \((x-2)(x+3)=x^2+x-6\), plus \(7=x^2+x+1\).

Example 9 — Degree of product

\(\deg((x^2+1)(x^3+2x))=5\).

Example 10 — Zero divisors?

Over \(\mathbb{R}[x]\), \(pq=0\Rightarrow p=0\) or \(q=0\). (Unlike modular coefficient rings sometimes.)

Example 11 — Even/odd functions preview

\(p(x)=x^3+x\) is odd as a function: \(p(-x)=-p(x)\). \(q(x)=x^2+1\) even.

Example 12 — Nested Horner for multipoint

Same scheme for each evaluation point; reuse coefficients.

Example 13 — Expand

\((2x-1)^3=8x^3-3\cdot4x^2\cdot1+3\cdot2x\cdot1-1=8x^3-12x^2+6x-1\).

Example 14 — Missing terms

Write \(x^3+1\) as \(x^3+0x^2+0x+1\) for Horner/synthetic comfort.

Example 15 — Synthetic division

Divide \(x^3-2x^2-x+2\) by \(x-1\). Coefficients \(1,-2,-1,2\); synthetic with \(c=1\):
bring \(1\); \(1\cdot1-2=-1\); \((-1)\cdot1-1=-2\); \((-2)\cdot1+2=0\).
Quotient \(x^2-x-2\), remainder \(0\) (matches long division earlier).

Example 16 — Sum and difference of cubes

\(x^3-8=(x-2)(x^2+2x+4)\). Check: \(x^3+2x^2+4x-2x^2-4x-8=x^3-8\).
\(x^3+8=(x+2)(x^2-2x+4)\).

Example 17 — At most \(n\) roots application

\(p(x)=x^2-1\) has roots \(\pm 1\) only. Cannot have a third root without being identically zero. Identity theorem lite: if two degree-\(\le n\) polynomials agree at \(n+1\) points, they are equal as polynomials.

Example 18 — End behavior

\(p(x)=-2x^3+x\): as \(x\to+\infty\), \(p\to-\infty\); as \(x\to-\infty\), \(p\to+\infty\) (odd degree, negative lead).

Example 19 — Nested product expand carefully

\((x-1)(x+1)(x^2+1)=((x^2-1)(x^2+1))=x^4-1\). Degree \(4=1+1+2\).

Example 20 — Polynomial identity check

Is \(x^2+2x+1=(x+1)^2\) as polynomials? Expand RHS: yes, coefficients match. Checking three points would also suffice for degree \(\le 2\), but coefficient comparison is definitive.

Exercises

Easy

1. State degree and leading coefficient of \(7-3x+x^4\).
2. Add \((x^2+2x)+(3x^2-5)\).
3. Multiply \((x+3)(x-3)\).
4. Evaluate \(x^2-4x+1\) at \(x=-1\).
5. Is \(x^{-1}+x\) a polynomial? Why or why not?

Medium

6. Multiply \((2x^2-x+1)(x+4)\); give degree.
7. Use Horner to evaluate \(3x^4-2x^2+x-5\) at \(x=2\).
8. Show \(x= -2\) is a root of \(x^3+3x^2-4\); factor out \((x+2)\) via division or inspection.
9. Divide \(x^3+1\) by \(x+1\); find \(q,r\).
10. Prove \(\deg(pq)=\deg p+\deg q\) for nonzero \(p,q\) over \(\mathbb{R}\).
11. Find all roots of \((x-1)(x+2)(x-3)=0\).
12. Expand \((x+y)(x^2-xy+y^2)\) (sum of cubes pattern).
13. For \(p(x)=x^2+bx+c\), express \(p(0)\), \(p(1)\) in coefficients.

Hard

14. Perform long division: \((2x^3-3x^2+x-1)\div(x^2-1)\); state \(q,r\) with \(\deg r<\deg(x^2-1)\).
15. Prove remainder theorem: \(p(x)=(x-c)q(x)+p(c)\) using division algorithm uniqueness.
16. Show that if \(\deg p=n\), then \(p\) has at most \(n\) roots unless \(p\equiv 0\) (use factor theorem repeatedly).
17. Give polynomials \(p,q\) with \(\deg(p+q)<\max(\deg p,\deg q)\).
18. Compare operation counts: naive eval of degree \(n\) vs Horner.
19. Define addition and multiplication of polynomials formally; verify distributive law sketch.
20. Is every function \(\mathbb{R}\to\mathbb{R}\) a polynomial? Justify.

Challenge / CS-flavored

21. Horner is the same as parsing base-\(b\) integers—explain with \(p(b)\) for digit polynomial.
22. Complexity: multiplying two degree-\(n\) polynomials naive \(O(n^2)\) coefficient ops.
23. Generating function lite: \(1+x+x^2+\cdots+x^n=\frac{1-x^{n+1}}{1-x}\) for \(x\neq 1\)—polynomial identity for finite sum.
24. Why store coefficients in an array of length \(\deg+1\)? Index meaning?
25. Numeric stability: evaluating \(x^n\) via recurrence \(p\leftarrow p\cdot x\) (Horner-like) vs pow—qualitative.

Polynomial ring intuition

\(\mathbb{R}[x]\) denotes polynomials with real coefficients. Addition and multiplication make it a ring. Units (invertible elements) are nonzero constants. Irreducible polynomials play a prime-like role (Stage later if revisited).

Synthetic division (companion to long division)

For monic linear divisors \(x-c\), synthetic division packs coefficients efficiently—same results as long division. Example: coefficients of \(x^{3}-2x^{2}-x+2\) divided by \(x-1\): bring down, multiply-add cascade → quotient coeffs and remainder \(p(1)\).

Evaluation as nested form

Horner is optimal for multiplication count among algorithms that only use multiplies by \(x\) and adds (in a precise model)—culture fact; naive powering is worse.

Roots bound (optional)

For monic \(x^n+a_{n-1}x^{n-1}+\cdots+a_0\), any real root \(r\) satisfies \(|r|\le 1+\max |a_i|\) (crude bound)—useful for search intervals.

Extra exercises

26. Prove that the sum of two degree-\(n\) polynomials can have degree \(<n\).
    
27. Synthetic or long divide \(x^{3}+x^{2}-4x-4\) by \(x+2\).
    
28. Show \(x^{2}+1\) has no real roots; conclude it does not factor into real linears.
    
29. Count multiplications: Horner for degree \(5\) vs expanding powers \(x,x^{2},\ldots\) naively.
    
30. Write the general product coefficient formula for \((\sum a_i x^{i})(\sum b_j x^{j})\).

CS connection

Polynomials appear in hash polynomials, checksums, graphics curves (Bézier are polynomial), and coding theory. Horner minimizes multiplications—classic algorithm analysis example. Coefficient arrays are the data structure; sparse polynomials need maps.

Common pitfalls

Pitfall	What to do instead
Forgetting missing powers	Write \(0\) coefficients
\(\deg(p+q)=\max\) always	Leading terms may cancel
Calling rational functions polynomials	Denominator must be \(1\)
Horner wrong direction	Highest degree first
Root implies factor without proof	Factor theorem (use division)
Division degree condition on \(r\)	\(\deg r<\deg d\) or \(r=0\)

Fully worked extra examples

E15 — Full long division tableau.
Divide \(2x^{3}+3x^{2}-x+5\) by \(x^{2}+1\):
\(\frac{2x^{3}}{x^{2}}=2x\); \(2x(x^{2}+1)=2x^{3}+2x\); subtract: \(3x^{2}-3x+5\).
\(\frac{3x^{2}}{x^{2}}=3\); \(3(x^{2}+1)=3x^{2}+3\); subtract: \(-3x+2\).
Quotient \(2x+3\), remainder \(-3x+2\). Check: \((x^{2}+1)(2x+3)+(-3x+2)=2x^{3}+3x^{2}+2x+3-3x+2=2x^{3}+3x^{2}-x+5\).

E16 — Horner multiprecision feel.
\(p(x)=x^{5}+x^{4}+x^{3}+x^{2}+x+1\) at \(x=2\): nested \(((((((1)\cdot2+1)2+1)2+1)2+1)2+1)=63\). Indeed \(\frac{2^{6}-1}{2-1}=63\).

E17 — Root multiplicity preview.
\((x-1)^{2}=x^{2}-2x+1\) has double root \(1\): graph touches axis. Factor theorem still applies: \((x-1)\) divides, and again divides the quotient.

E18 — Degree of sum cancellation.
\((x^{3}+x)+( -x^{3}+2)=x+2\) degree \(1\), not \(3\). Leading coefficients summed to zero.

End-of-day synthesis problems

S1. Multiply \((x^{2}-x+1)(x^{2}+x+1)\) and state degree.

S2. Horner-evaluate \(x^{4}-2x^{3}+x-7\) at \(x=-1\).

S3. Long divide \(x^{3}-3x+2\) by \(x-1\); relate remainder to \(p(1)\).

S4. Prove \(\deg(pq)=\deg p+\deg q\) for nonzero \(p,q\) over \(\mathbb{R}\).

S5. Show \(x=2\) is a root of \(x^{3}-6x^{2}+11x-6\); factor completely over \(\mathbb{R}\).

S6. Add \((3x^{3}+x)-(3x^{3}-2x^{2}+4)\) and explain degree drop.

S7. Write \(x^{3}+1\) with all intermediate zero coefficients for Horner.

S8. If \(p\) has degree \(4\) and \(q\) degree \(3\), what are possible degrees of \(p+q\) and \(pq\)?

Deep dive — Why Horner is standard

Naive evaluation of \(a_n x^n+\cdots+a_0\) computing each \(x^k\) separately costs about \(n+(n-1)+\cdots+1=\Theta(n^2)\) multiplies if each power is built from scratch, or \(\Theta(n)\) multiplies if you reuse \(x^{k}=x\cdot x^{k-1}\), plus \(n\) multiplies by coefficients—still more multiplies than Horner’s \(n\). Horner fuses powering and coefficient combination into \(n\) multiplies and \(n\) adds. In code, it is a tight loop with excellent locality. The same nested multiply-add is how base-\(b\) digit strings evaluate to integers (Day 6–7 link).

Synthesis

Polynomials form a ring closed under \(+,\cdot\) with degree additivity for products. Evaluation, Horner, division, and the factor/remainder theorems are one package: division by \(x-c\) is evaluation in disguise. Roots are not free—degree \(n\) allows at most \(n\) of them unless the polynomial is zero.

S9. Prove the remainder theorem in two sentences from the division algorithm.

S10. Use synthetic division to divide \(2x^3-3x+1\) by \(x+1\); report \(q\) and \(r\).

S11. Expand \((x+2)^3\) two ways (binomial and stepwise) and match coefficients.

S12. Show that if \(p\) and \(q\) agree on infinitely many reals, then \(p-q\equiv 0\) as a polynomial (use the root bound).

Checkpoint

• Define polynomial, degree, leading coefficient
  
• Add and multiply polynomials; track degree
  
• Evaluate with Horner
  
• State root \(\leftrightarrow\) factor idea
  
• Carry out one long division with remainder
  
• Finish S3 with full long-division tableau

Write two takeaways in your own words.

Quick reference card

Object	Symbol / formula
Degree	highest power with nonzero coeff
Leading coeff	coeff of \(x^{\deg p}\)
Horner	nested multiply-add
Remainder thm	\(p(x)=(x-c)q(x)+p(c)\)
Product degree	\(\deg p+\deg q\) if \(p,q\neq 0\)

Memorize the card; rebuild one long division from blank paper.

Tomorrow

Day 16 — Factoring. GCF, grouping, trinomials, difference of squares/cubes, factor theorem idea, solve quadratics by factoring.