In this video will prove lemma, which will use in various context about the number of routes off a given polynomial of bounded degree. So let's state this lemma. So lemma can be attributed to Lipton DeMillo Schwartz Zippel, Schwartz and Zippel proved the same result independently, a bit later than Lipton and DeMillo. And in the literature this lemma is usually called the Schwartz Simple lemma. So let b be a polynomial of n variables with coefficients taken off some field F. For now for intuition you can treat it is a polynomial with say reall coefficients or rational coefficients pore coefficients being residues over sometime P it doesn't matter. So currently you can treat this as a polynomial with really valued coefficients. And now let's S1 through Sn be subsets of this field F. So now the lemma gives an estimate for the number of ways to choose the values of each of the variable from the corresponding subset so that's the given to pull of values is a root of this polynomial. So we'll assume that all these sets Si have cardinality at most m and the bond which is given by this lemma for the number of ways to choose a tupelo S1 through Sm such that S1 belongs to the set capital S1. Sm belongs to the set capital Sm such that P vanishes on these tupelo values. The number of these Stupples does not exceed the degree of the polynomial multiplied by m to the power of m minus 1. We can treat this as a generalization of a theory on the number of routes of polynomial over a field. So if P is a polynomial of a single variable x, which is not identical 0, then the number of routes of this polynomial does not exceed the degree of this polynomial. And this is a special case off this statement because here we have n equal to 1 the number of variables so here would have just 1 hence all just down to the statement, and the number of routes off a polynomial does not exceed its degree. But we'll actually use this theorem of algebra as the base case for our induction, while proving this lemma. So we'll assume this as a known fact for a polynomial of a single variable and now will prove the lemma by induction on the pair of values induction on both degree off the polynomial and the number of variables. So what does it mean to carry out the induction from the pair off values? So usually, when we have just one perimeter of the induction, this perimeter is often times just a natural number. We prove our statements for the smallest number, then we prove that we can translate it into a larger one, and thus we can cover all the positive integers proving that each of them satisfies our statements. Or to put it the other way around if we're to prove our theorem for the largely in texture, we can rely on the smaller one to prove it. We can rely on the smaller one before we come to the base case, which we also prove separately and thus we know that our proposition calls for a all the positive integers. So now the picture for the induction carried out for a pair of parameters would look approximately like this. So if we plot this space of our parameters, so here we say, have degree of the polynomial growing, here we have the number of variables growing. Our base case would be when n is equal to 1 or when d is equal to 1. So we essentially have all these points covered by the base case when n is equal to 1 and all these points covered by the base case, when degree of the polynomial is equal to 1. And then taking some pair of the polynomial of some degree and some number of variables will prove the really The sea off our proposition for despair by relying on the validity of the same proposition for some peers, which have at least one of the parameters smaller. So to prove the proposition for some point of parameters, we rely on pairs of parameters that are standing to the bottom and to the left off this point. So thus, eventually we get toe one off. Our base case is so that's our proposition is true for all the possible combinations off their emitters. So let's now prove the induction base. So the base case, when N is equal to one, is just a standard theory. Of algebra that's a polynomial off a single variable has no more routes than the degree of this polynomial. Now, the second type off base case is when the degree of the polynomial is equal to one. Here we have a polynomial p off X one up to X m. Being just a linear combination of the variables. Without loss of generality, we can assume, let's say the coefficients see one is non zero, and let's now estimate the number of pupils when which the polynomial P vanishes. So, for such troubles, x one should be won over C one off minus C two x two minus C n xn. So now whatever values which was for X two through xn for every such choice, this thing take some value and there's only one choice for the variable x one so that these equality could hold. So if we have cardinal ity off us two choices for X two up to Cardinal TSN choices for X n the number of choices for a while, the values off access is the product of the car tonalities. Now, every such choice leads to some specific value here. And so there is just a single X one. Well, actually, at most one x one because X one should be an element off s one. So if S one does not contain an element which exactly equals tow this thing than we have actually zero choices for X one. But anyway, even if s one contains such a value, then there is the most one choice for X one. And so the number of two poles does not exceed just the product of cardinal. It is from S two to S n, which perfectly corresponds toe What we're proving degree of p is in this case, one and the product of the cardinal. It ease off s two through sm does not exceed to the powerful minus one. Let's now proceed with the induction. Step off our proof. So let's assume that variable X one without loss of generality enters our polynomial with degree at least one so it actually is included in our polynomial. And let's write our polynomial over various degrees off the variable x one. So that is well group all the Manami ALS that contain only variables X two and X m not containing X one and will group these together and will name this the polynomial p zero off x two through xn. Then we'll take away their remaining Manami ALS that have variable X one in exactly first degree in them and will take X one away from them and they together without X one and will be named by P one off X two through xn and so on and so forth. So the last portion of Manami als they contain X one to some degree key and we take X one out of them and they will be grouped together and called a polynomial peaky. That's just contains variable X two through X m. So now let's estimate the number of pupils s one through sn such that be ventures in these tubules. Now these people's can be off two kinds The first kind of the troubles that pupils on which peaky vanishes so that peaky off s two through S N is equal to zero and the second kind are the two poles on which peaky doesn't finish. So let's now first bond the number of these guys such that the sub pupil as to through sn, makes peaky avenge now the degree or the pulling of L. P K does not exceed the degree of polynomial p minus K because whatever Manami a we take out of PK when we multiplied by x one to the power of K this phenomenal will not vengeful when we add it with other Manami als from here because it has the highest possible degree off x one, and thus it will eventually enter the polynomial p. And when we take products off to play normals, the degree of the products is equal to the sum of the degree off the individual components and thus we cannot have Manami ALS off degree higher than this one in pity so that we can apply induction hypothesis toe polynomial p k, and say that if PK vanishes, then the number of ways to choose esto through sn does not exceed by induction hypothesis the degree of the polynomial which does not exceed itself that p minus k times m to the power one less than the number off components here. So that's a then minus two we have here and each of these pupils can be augmented to a complete pupil from s one through sn in it most end ways because they're at most in ways to choose the variable X one. So now let's bond the number off these Stupples. The number of ways to choose s two through sn does not exceed I m to the power of n minus one. But then, for each fixed choice off s two through sn for which peaky does not vanish our polynomial p turns into a polynomial off a single variable x one a polynomial of degree key And now the number of routes The polynomial off degree key off a single variable concave Is it most k? So there are at most K weighs toe opens our triple toe form A to pull off values s one through sn And now adding these two things up gives us exactly the thing that we're looking for. So these completes the induction step and thus it completes the proof off the lemma and the lemma that we have just proved has a very nice probabilistic interpretation. So if we use a corollary of this llama, which is when all the cardinal it ease off, our sets are exactly equal to M. We can state is lama in terms of probability, so suppose that we have are polynomial p off X one through xn and we're choosing the values for all the variables each value from its own set independently at random. Usually there is a notation for a random choice like this. So it's variable as I is chosen independently off the other variables at random, uniformly from its own set s I So then what would be the probability that these stupid off values makes our polynomial Vinge? So when we plug s one through sm into our polynomial, the probability that's p will avenge on these stupid of values can be bounded by the number off the pupils on which our polynomial vanish. So that's this one According Toa our standard formulation off the deep end English words Ekulama divided by the number of all the pupils. And when all the cardinals these are equal to m the number of all pupils is just m to the power of again. So it simplifies tojust degree of p over. And this is actually the variant of the actual Siple Emma that will use later on for designing probabilistic algorithms