Slide 1Slide 2Slide 3Polynomials in one variable over the realsRepresenting a polynomialAre we working over the reals?the field (Zp, +p, *p)Slide 8Adding, Multiplying PolynomialsZp[x] is a commutative ring with identitySlide 11Evaluating a polynomialThe roots of a polynomialLinear PolynomialsSlide 15Slide 16Slide 17Slide 18Slide 19Slide 20Two different representationsSlide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Error Correcting CodesSlide 39Slide 40Slide 41Slide 42Think polynomials…Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 5915-251Great Theoretical Ideas in Computer SciencePolynomials, Lagrange, and Error-correctionLecture 16 (March 5, 2009) X3 X2 + + X1 + P(X) =Definition: A field F is a set together with two binary operations + and ×, satisfying the following properties:1. (F,+) is a commutative group2. (F-{0},×) is a commutative group3. The distributive law holds in F:(a + b) × c = (a × c) + (b × c)FieldsPolynomials in one variable over the realsP(x) = 3 x2 + 7 x – 2Q(x) = x123 – ½ x25 + 19 x3 – 1R(y) = 2y + √2S(z) = z2 – z - 1T(x) = 0W(x) = πRepresenting a polynomialA degree-d polynomial is represented by its (d+1) coefficients:P(x) = cd xd + cd-1 xd-1 + … + c1 x1 + c0The d+1 numbers cd, cd-1, …, c0 are coefficients.E.g. P(x) = 3x4 – 7x2 + 12x – 19Coefficients 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 Zpthe 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 groupAddition distributes over multiplication.Let Zp[x] denote the set of polynomials with variable x and coefficients from Zp(Zp, +p, *p)is a fieldMultiplying Polynomials(x2+2x-1)(3x3+7x) = x2(3x2 + 7x) + 2x(3x2 + 7x) – (3x3 + 7x)= 3x5 + 6x4 + 4x3 + 14x2 – 7x(say from Z11[x])= 3x5 + 6x4 + 4x3 + 3x2 + 4xAdding, Multiplying PolynomialsLet 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 identityLet 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 associative0 (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 groupZp[x] is a commutative ring with identityLet 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 associative1 (the “unit” polynomial) is the multiplicative identityMultiplication is commutativeFinally, addition distributes over multiplication(Zp[x], +, *) is a commutative ring with identity(mult. inverses may not exist)Evaluating a polynomialSuppose:P(x) = cd xd + cd-1 xd-1 + … + c1 x1 + c0E.g. P(x) = 3x4 – 7x2 + 12x – 19P(5) = 3×54 – 7×52 + 12×5 – 19P(-1) = 3×(-1)4 – 7×(-1)2 + 12×(-1) – 19P(0) = -19The roots of a polynomialSuppose:P(x) = cd xd + cd-1 xd-1 + … + c1 x1 + c0Definition: r is a “root” of P(x) if P(r) = 0E.g., P(x) = 3x + 7 root = -(7/3).P(x) = x2 – 2x + 1roots = 1, 1P(x) = 3x3 -10x2 + 10x – 2 roots = 1/3, 1, 2.Linear PolynomialsP(x) = ax + bOne root: P(x) = ax + b = 0 x = -b/aE.g., P(x) = 7x – 9 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 PolynomialsA non-zero degree-d polynomial P(x) hasat most d roots.This fact has many applications…An application: TheoremGiven pairs (a1, b1), …, (ad+1, bd+1) of values there is at most onedegree-d polynomial P(x) such that:P(ak) = bk for all kwhen we say “degree-d”, we mean degree at most d.we’ll always assume ai ak for i kAn application: TheoremGiven pairs (a1, b1), …, (ad+1, bd+1) of values there is at most onedegree-d polynomial P(x) such that:P(ak) = bk for all kLet’s prove the contrapositiveAssume P(x) and Q(x) have degree at most dSuppose a1, a2, …, ad+1 are d+1 points such that P(ak) = Q(ak) for all k = 1,2,…,d+1Then P(x) = Q(x) for all values of xProof: Define R(x) = P(x) – Q(x)R(x) has degree dR(x) has d+1 roots, so it must be the zero polynomialTheorem: Given pairs (a1, b1), …, (ad+1, bd+1) of values there is at most onedegree-d polynomial P(x) such that:P(ak) = bk for all kdo there exist d+1 pairsfor which there are no such polynomials??Revised Theorem:Given pairs (a1, b1), …, (ad+1, bd+1) of values there is exactly onedegree-d polynomial P(x) such that:P(ak) = bk for all kThe algorithm to construct P(x)is called Lagrange InterpolationTwo different representationsP(x) = cd xd + cd-1 xd-1 + … + c1 x1 + c0can be represented either bya) its d+1 coefficientscd, cd-1, …, c2, c1, c0b) Its value at any d+1 pointsP(a1), P(a2), …, P(ad), P(ad+1)(e.g., P(1), P(2), …, P(d+1).)Converting Between The Two RepresentationsCoefficients to Evaluation:Evaluation to Coefficients:Evaluate P(x) at d+1 pointsUse Lagrange InterpolationNow for some Lagrange InterpolationGiven pairs (a1, b1), …, (ad+1, bd+1) of values there is exactly onedegree-d polynomial P(x) such that:P(ak) = bk for all kSpecial caseWhat if the points were like:(a1, 1)(a2, 0)(a3, 0)…(ad+1, 0)Special caseSuppose we can get degree-d poly h1(x): h1(a1) = 1 h1(at) = 0 for all t = 2,…,d+1 “switch” polynomial #1Special caseSuppose 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 caseSuppose 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 kFinally, P(x) = k Hk(x)Hence, all we need to doGiven numbers a1, a2, …, ad+1Build a degree-d “switch” poly h1(x): h1(a1) = 1 h1(at) = 0 for all t = 2,…,d+1construction by examplewant a quadratic h with h(3) = 1,
View Full Document