15 251 Great Theoretical Ideas in Computer Science Polynomials Lagrange and Error correction Lecture 16 March 5 2009 P X X 3 X X1 2 Fields Definition A field F is a set together with two binary operations and satisfying the following properties 1 F is a commutative group 2 F 0 is a commutative group 3 The distributive law holds in F a b c a c b c Polynomials in one variable over the reals P x 3 x2 7 x 2 Q x x123 x25 19 x3 1 R y 2y 2 S z z2 z 1 T x 0 W x Representing a polynomial A degree d polynomial is represented by its d 1 coefficients P x cd xd cd 1 xd 1 c1 x1 c0 The d 1 numbers cd cd 1 c0 are coefficients E g P x 3x4 7x2 12x 19 Coefficients are Are we working over the reals We could work over any field set with addition multiplication division defined E g we could work with the rationals or the reals Or with Zp the integers mod prime p In this lecture we will work with Zp the field Zp p p Zp 0 1 2 p 1 is a commutative group Zp 1 2 3 p 1 Zp 0 is also a commutative group Zp p p is a field Addition distributes over multiplication Let Zp x denote the set of polynomials with variable x and coefficients from Zp Multiplying Polynomials say from Z11 x x2 2x 1 3x3 7x x2 3x2 7x 2x 3x2 7x 3x3 7x 3x5 6x4 4x3 14x2 7x 3x5 6x4 4x3 3x2 4x Adding Multiplying Polynomials Let P x Q x be two polynomials The sum P x Q x is also a polynomial i e polynomials are closed under addition Their product P x Q x is also a polynomial closed under multiplication P x Q x is not necessarily a polynomial Zp x is a commutative ring with identity Let P x Q x be two polynomials The sum P x Q x is also a polynomial i e polynomials are closed under addition Addition is associative 0 the zero polynomial is the additive identity P x is the additive inverse of P x Also addition is commutative Zp x is a commutative group Zp x is a commutative ring with identity Let P x Q x be two polynomials The sum P x Q x is also a polynomial i e polynomials are closed under multiplication Multiplication is associative 1 the unit polynomial is the multiplicative identity Multiplication is commutative Finally addition distributes over multiplication Zp x is a commutative ring with identity mult inverses may not exist Evaluating a polynomial Suppose P x cd xd cd 1 xd 1 c1 x1 c0 E g P x 3x4 7x2 12x 19 P 5 3 54 7 52 12 5 19 P 1 3 1 4 7 1 2 12 1 19 P 0 19 The roots of a polynomial Suppose P x cd xd cd 1 xd 1 c1 x1 c0 Definition r is a root of P x if P r 0 E g P x 3x 7 root 7 3 P x x2 2x 1roots 1 1 P x 3x3 10x2 10x 2 roots 1 3 1 2 Linear Polynomials P x ax b One root P x ax b 0 E g P x 7x 9 x b a in Z11 x root 9 7 9 7 1 9 8 72 6 mod 11 Check P 6 7 6 9 42 9 33 0 mod 11 The Single Most Important Theorem About Low degree Polynomials A non zero degree d polynomial P x has at most d roots This fact has many applications An application Theorem Given pairs a1 b1 ad 1 bd 1 of values there is at most one degree d polynomial P x such that P ak bk for all k when we say degree d we mean degree at most d we ll always assume ai ak for i k An application Theorem Given pairs a1 b1 ad 1 bd 1 of values there is at most one degree d polynomial P x such that P ak bk for all k Let s prove the contrapositive Assume P x and Q x have degree at most d Suppose a1 a2 ad 1 are d 1 points such that P ak Q ak for all k 1 2 d 1 Then P x Q x for all values of x Proof Define R x P x Q x R x has degree d R x has d 1 roots so it must be the zero polynomial Theorem Given pairs a1 b1 ad 1 bd 1 of values there is at most one degree d polynomial P x such that P ak bk for all k do there exist d 1 pairs for which there are no such polynomials Revised Theorem Given pairs a1 b1 ad 1 bd 1 of values there is exactly one degree d polynomial P x such that P ak bk for all k The algorithm to construct P x is called Lagrange Interpolation Two different representations P x cd xd cd 1 xd 1 c1 x1 c0 can be represented either by a its d 1 coefficients cd cd 1 c2 c1 c0 b Its value at any d 1 points P a1 P a2 P ad P ad 1 e g P 1 P 2 P d 1 Converting Between The Two Representations Coefficients to Evaluation Evaluate P x at d 1 points Evaluation to Coefficients Use Lagrange Interpolation Now for some Lagrange Interpolation Given pairs a1 b1 ad 1 bd 1 of values there is exactly one degree d polynomial P x such that P ak bk for all k Special case What if the points were like a1 1 a2 0 a3 0 ad 1 0 Special case Suppose we can get degree d poly h1 x h1 a1 1 h1 at 0 for all t 2 d 1 switch polynomial 1 Special case Suppose we can get degree d poly h1 x h1 a1 1 h1 at 0 for all t 2 d 1 Then we can get degree d poly H1 x H1 a1 b1 H1 at 0 for all t 2 d 1 Just set H1 x b1 h1 x Special case Suppose we can get degree d poly h1 x h1 a1 1 h1 at 0 for all t 2 d 1 Using same idea get degree d poly Hk x Hk ak bk Hk at 0 for all t k Finally P x k Hk x Hence all we need to do Given numbers a1 a2 ad 1 Build a degree d switch poly h1 x h1 a1 1 h1 at 0 for all t 2 d 1 construction by example want a quadratic h with h 3 1 h 1 0 h 6 0 Let s first get the roots in place say in Z11 x h x x 1 x 6 Are we done No We wanted h 3 1 But h 3 …
View Full Document
Unlocking...