Video 8-7: Nisan-Wigderson construction

0:03 We left off proving the Nisan victim pseudo random generator construction works. And just to briefly recap, uh we're we're essentially after a statement like this in a a slightly weaker form. We'll only show this for specifically um exponential functions as uh the key idea of the con of the generator is um in a way super simple. we take our um our small number of seat random bits, we apply a hard function. So specifically in the sense of circuit complexity even if you're only trying to compute this function or uh more than half of the inputs correctly then you need a circuit of a certain size. If you have such a function then we um apply this and for each input we generate one pseudo random output bit and what we feed into the function is a certain specifically selected subset of the bits in set. uh that's what I was trying to draw to draw here and where we left off yesterday is proving that there is a way to pick subsets with the properties stated in this definition. So there's uh if you pick parameters ln n and d correctly uh then you can pick m subsets out of a subset of size l indeed you can pick exponentially many they're all of size n the other parameter given and their pair-wise intersection is never bigger than d positions and we've seen a specific choice of parameters or most more correctly I I guess Okay, under some assumptions on the parameters in particular that L is a good deal bigger than N.

1:55 Uh you can do a very simple brute force construction algorithm and that finds such a design. This part I won't go over the proof again.

2:15 The next step towards uh generating this this pseudo random generator is a kind of intermediate step to make it a little easier to go about the proof. Um in general we would have to show that the pseudo random generator has the properties from the definition namely it it generates sequence of bits so that no no circuit up to a certain size can behave very differently on these bits as a whole as compared to really random bits. um it's a lot easier to um to prove uh this intermediate step where you um you say I'm have a a sequence of of random bits. One way to say they're random intuitively is that whenever I have a prefix of the pseudo random bits. So maybe here this is all of our how do we we call it uh g of set uh for set the seed right? Do they have a name for the output already?

3:30 Let me just uh cheat and look if I already used the name Y. So let's call this Y. Um that's a long sequence of of bits. We'll use it for pseudo random bits. But of course the definition is kind of uh general. If you see a prefix of those, so you see these parts, you don't know what this is. If these are supposed to be random, then it must be hard to take the next position I and predict it from all the previous positions.

4:10 If that was easily possible for all the positions, certainly the thing isn't random. Um so the first step is is this definition that we say uh some function it'll be our pseudo random generator in the end has a similar setup as the pseudo random generator for that for that purpose. So it's it's a function that maps uh binary strings to binary strings and it blows them up. So if you input l initial bits you get s of l bits out. That's the parameters how we used it before. And then we call this um this function G unpredictable if there's some constant and every position I is such that you cannot predict the I bit from just knowing the bits up to position I minus one. And formally what does predict mean? It means uh for every circuit up to a certain size uh you cannot get if you put in real random bits and compute your y from that you cannot predict the next bit better than 1/2 plus uh a little bit. So 1/2 is always possible. You can just guess randomly. You could uh output a random bit and say that's that's my prediction that's going to be right half the time.

5:34 or you can't expect it to be wrong more than half of the time for every possible bit. Uh but the the definition says no matter what you do, no matter what circuit you put in, if it's small enough, no matter how long the prefix is that you give me, um the uh probability to correctly predict the next bit is is just slightly above 1/2.

6:00 And you already see that um if if you have a function s that grows very quickly, then this is actually a minuscule little probability on top of 1/2. What's maybe not obvious from the definition. I mean it's it's uh it's stated on the slide but I I think it's clear if if the input is pseudo random then this unpredictability should hold because intuitively uh if you could predict every position from the previous one you could just regenerate the random string and that's not exactly random. It's not so clear why this would be enough uh if if some function is unpredictable in this more specific sense that every single bit is unpredictable that the whole thing would be pseudo random in our according to our definition from earlier. Um but indeed that's the case. It's a non-trivial result. So um we'll we'll have a theorem for that and I'll I'll give you some some sketch of the proof but not the full detailed computations in this case but they're not not very hard. It's more like the the main contribution was coming up with the right definitions and making this connection I think.

7:17 So the formal statement is uh we have some stretch function s how many more bits do you generate out of l seed bits and we have um a function g so it just means this part it maps from binary strings to binary strings uh it's output is s of l when l is the input and it's poly time computable so um I polomial in the output size though I think this has to be taken with a grain of salt. Um the output is supposed to be exponentially bigger than a polinomial of the output. I think what we want is we can probably do with a much weaker restriction.

8:38 Let me replace this with um 2 to the O of L, which sounds like a lot. We'll mostly use this for small L. So this will be polomial in terms of the over uh the the algorithm's input that we use it in. Um but the function itself it cannot be polinomial time in its input size simply because it produces such a big output.

9:06 Okay. So let's take um function P as above. The function S can be poly time computable. Okay. That's that's fine. uh but G uh needs to at least produce its output if it's unpredictable then it is a pseudo random generator and of course with the same same stretch.

9:23 So uh how can we how can we prove this uh basically by um a contradiction and constructing some some circuit again that distinguishes the pseudo random bits from the real random bits. So again assume uh we have that this function is unpredictable but still it doesn't work as a pseudo random generator that means there must be some uh circuit that behaves differently on the output. So, circuit C behaves substantially different on uh real random bits and uh sorry on on real random bits is this part and on the output of G on real random bits but only L of them and what this formally means is that the probability that they are the same is uh is less than 110th. So, uh, that's from all all the way back. I don't want to lick through a million slides.

10:47 So, the probability that C on let's give this a name. Let's say this is said and this is Y. Let's call it R. R and the difference between that must be is 1 / 10. That's what this substantially different is supposed to mean. That's exactly taken from the definition of of pseudo random. And uh if we say there's a a a circuit that distinguishes them, we mean the probability that it uh behaves differently is is is at least 1 / 10. All right.

11:35 Now uh what we have to do is from this um somehow derive a contradiction and what we'll do is we'll construct uh distinguisher that shows that G is not unpredictable that it is predictable and again for predictable maybe it would be good to have the uh definition here.

12:27 So it's it's unpredictable if for every position I in and every small circuit the uh probability that the circuit correctly predicts the I bit is small. So to counter that um it will eventually be enough to show that for one position I uh it doesn't work. Is there a question? Okay. uh it will be enough to find one position I where we can correctly predict the next bit with a larger probability uh but the uh construction is is only um probabilistic in that sense so we only show there is an I we can't name it so we'll start with um for every position I we'll build a predictor circuit B I uh that's using C and tries to predict the next bit so how would it do That's uh the idea is um again C is some maybe draw some some pictures up here. C is some unknown box that takes in random bits or takes in some some bits that it hopes to be random.

13:43 And so I'm comparing putting in R the real random bits are all unknown. And I'm comparing it to feeding to see this much shorter random bit string set which I'm blowing up by G to uh the same size as what I had before.

14:13 So it's pseudo random and I feed that in. Now uh by assumption this is actually not very this is uh not always the same. Um there's indeed a good probability that C behaves differently.

14:31 Uh but I don't know on which input. So it's kind of tricky. And now what I'm what I'm trying to build this B I it's supposed to take the first um I minus one of these bits up here. So the prefix up there is prefix here or prefix here. We don't know. And we're trying to predict the next bit. Now, we don't really uh have a way to call C with fewer um inputs than than it needs. We have to fill in some values. And so what we do is uh we fill up this rest of the space with truly random bits. And for the left part here, of course, this is exactly what we would have done before anyways. But for the right part, it might make things a bit different. So I'm I'm kind of uh deviating from this scenario. So I don't know if uh the output of C will still be uh very different.

15:40 Uh but either way, I can simulate C using this mixture of pseudo random bits and real random bits. And for each I get a slightly different mixture. Uh but the the idea then is if um if C outputs one then I'm I'm going to output this single random bit that is here the first of the ones I add and otherwise one minus that and so the thing is I'm doing this for both cases so if I'm on the left uh this is um it's going to be equally likely to to work out um whatever whatever C does here. Um whereas on the right uh this might be um might be a different outcome. Okay. So I don't know this is um that was that was very clear. The the trick to observe is if you compare what these uh different B's run on, then um for for small I you essentially feed only random bits and for the last B I you feed the entire string of uh of pseudo random bits maybe except for the last one.

17:02 So if you remember this picture here at the very end between you could say this this corresponds um come on the left picture where you do real random bits corresponds to i equals z and the original right picture where you feed in the pseudo random bits is i equals s of So for those we know that C behaves differently. So as we increase I slowly from zero to S of L at some point something must be happening. There must be some eye where things are different or at least it cannot be that all of those guess correctly with uh essentially spreading out this 1 / 10 difference um over over all the s of l steps I'm making from i= 0 to i= s of l.

18:22 I could map the um the difference in the probability to output a one between um bi and bi minus one. let's try to draw it this way. So I is on the x- axis and uh this one would be the difference in probability. So probability of C with this weird input.

19:07 Let me define a short hand for that. That's going to going to get too chaotic. Let's say PI is difference. Okay. D I the difference in probability between this input and the next larger I.

19:34 Ah, it's the Y missing. Come on. Y one up to I minus one followed by the random bits from Z. That's the one probability that the output of this thing is one and I'm subtracting the probability for the same but with a different I. Okay, let's say uh let's do I minus two here and then set one up to SL one close and the absolute value doesn't fit.

20:23 Okay, that that would never have fit on this axis down here. So let's let's put D of I on this axis. Now we know between I= Z and I= S of L there must be some some movement uh of 1 / 10 and uh I'm I'm steadily moving up here. So it's not possible that none of the steps from i to i + 1 are at least this 1 / 10 divided by s of l because in total they sum up to 1 / 10 and so in the best case it's evenly spread out then I would get this more likely is that some jumps are larger somes are smaller maybe even some are positive and negative but there must be one where absolute value I'm I'm changing by by more than this. Okay, that's why I called it a proof sketch. Didn't want to do the the full math detail, but I guess that's that's already giving you the main idea. Uh it's just not possible that you don't have any I where this jumps by more and that's almost what we need. Um it means there is some index I where our our predictor for the next bit given the previous pseudo random bits filled up with with real random bits. uh there's some i where this correctly predicts the next pseudo random bit with this um probability still just a tiny bit over 12 plus epsilon over s of l but this was uh the definition of predictable if you remember there we had exactly this this term which of course it's kind of chosen uh to match this uh this proof uh but so we've shown that G is not unpredictable.

22:21 That term is predictable. Uh and so that means our uh assumption must have been false which means G is actually a pseudo random generator.

22:33 So zoom out of the uh um bit chaotic proof. Uh if as soon as you show that um some some function is unpredictable, it already will be a pseudo random generator. So in the proof of the next part we can restrict to showing just this next bit prediction um that that is unlikely to be correct.

23:04 And that's the basically last step of the of the con of the construction. Uh what we'll still have to do at the end is pick all these parameters. That's what we'll come back to because there's L, there's N, there's D, there's M and F and S and it gets all a bit uh messy. The thing is the proofs are cleaner if you keep the parameters generic. So uh bear with me for two more slides and then we'll make things more concrete. Um the beauty is you can in this in this general uh setup can show that you get some pseudo random bits out of this.

23:41 So the the main key here, the main message is if you take this Nissan Victorson construction as we've seen, take your your function f that's supposed to be a hard function. Meaning even if you're uh only taking this this average case notion, you need a circuit of size at least 2 to the 2 to the d where d is some parameter. Um then uh uh if you feed that into our construction and you use a combinatorial design with the parameters ln and D. So many of these subsets of the seat bits then what you get as an output is uh is a pseudo random sequence of bits with a epsilon of 110 and uh the guarantee of how large do the distinguishing circuits have to be before they can distinguish this sequence from real random bits of effectively this uh hardness of the function. Again, we lose this constant factor 1 over 10. But this these are all in the end uh not not important.

24:48 Okay. So, how are we possibly going to show this? Of course, we're going to use what we've just shown Yao's theorem. So, we won't show that this is pseudo random. We will show that it's unpredictable.

25:01 So, that's the first step. We'll show that this uh Nissan Victor predictor is And um based on that uh well we we will show that um if we had some some predictor circuit for this unpredictable function. So again uh proof by by contradiction assume um that it's not unpredictable that it is predictable. That means there is a circuit that predicts one of the i bits and from that we will construct a small circuit for f in this uh weird average sense. So maybe you can see how this will fit together at the end. But the point is uh you can build a small circuit for f that violates this assumption on its hardness and that's where this all fits together. Uh again I haven't stated that today. Um the assumption that there that there are functions with a high exponentially high in the end uh average circuit hardness is a conjecture or is a hypothesis that we don't have a proof for. Um but there's some we discussed bit more yesterday. There's some indications that these are likely to exist.

26:24 Okay. So let's do this. Uh first step let's give this um hardness the name it had before. S is a function. Uh so here f is um is again you should imagine f to be a function that can take inputs of different sizes. And then uh the hardness also depends on the input size. So s is really a function of the input size. Um and the input size for f will be n. This is different from the L before. So I'm just going to uh point that out. Um I probably should So S is used for different things. It's the size of the circuit. And so it makes sense to be used for the hardness of the function. We also used it as the um uh what did I call it? The stretch of a generator. So how many more bits it generates their s also made sense but it will be a different s here. So the stretch of our generator will not be this s at the very end.

27:28 Um okay, a bit of a warning. So keep keep in mind the parameters. N is what we'll put into the function f. It's on the slides. I'm just trying to uh I don't know. We should maybe keep some some legend on the side. Okay. S is the hardness of the function. So intuitively if f uh to to compute the value of f on inputs of size n you need a circuit at least as large as s of n. And again computing here just means in the sense of um Monte Carlo algorithm it's okay to be wrong on a bit less than half of the inputs. And the specific uh requirement from this average hardness was you have to be correct for 12 + 1 / s a fraction of all inputs.

28:27 Okay, just rewriting the definition. Now we're trying to um try to prove that this is uh refute the circuit predictability. Okay. Uh we assume it's um we assume it's um unpredictable. No, we assume it's predictable. Is this double negation too much now?

29:23 We assume there's a circuit and some position where we can predict the next bit and the thing it has to match with um the definition of unpredictable. This one and it says that every position must be unpredictable. only then is the function unpredictable.

29:49 And to show that uh overall um the predictor is unpredictable, we do a proof by contradiction assuming that it is predictable. So uh assume it was not predictable.

30:06 Yeah, I don't know this this formulation I don't like anymore. But suppose it's not it's not unpredictable. That means there must be an index that is predictable. So there's some position I and a circuit of a small size. And again, this has to fit. I wish again we had this here. So even if it's too small to read, uh what I underlined here is circuits of size at most 2 s of n s here was the stretch. So if you output s of uh n bits, then you're supposed to um have hardness against circuits up to size 2 * s of n. The size of the output of our uh nissan victor predictor is m. That's the number of of uh sets in the design. That's the number of output bits. So we need a circuit that's less than 2 m to match that that definition.

31:24 that the NW predict um generator is predictable. I think I I tried to avoid writing predictable because we formally only defined unpredictable. So I should say not unpredictable.

31:42 Um I guess that's what but this is also writing predictable let's say okay assume it's predictable then that means there's this circuit and what's true for that circuit? Well, um it's sorry the the greater equal was was correct. It can predict the next bit. So its probability to be correct is larger than 12 plus 1 / 10 m. Again m is the s of l from the unpredictability definition.

32:18 And here r are the the pseudo random bits and um these are computed based on set. Okay, so so far uh is really just plugging in the definitions and not being lost in all the formal formal statements.

32:41 Now at this point we have to plug in what we uh know about how the construction works and um that's uh remember the picture with uh we have L input bits and then we pick subsets feed them into F and that each gets out one output bit of the NW uh predictor or generator. So also our r i the i bit that we try to predict um is the output of our hard function f on some subset of these truly random bits. And now to make life a bit convenient let's just assume we rename the variables if necessary uh so that this i bit that we care about now is indeed computed just from the first n bits of the pseudo random string so of of the random seed. If that wasn't the case, you can you can rename the variables instead to make it so this is not a it's not a problem. They're random anyway. So there's fully they're fully symmetric. I will only do this once. Uh so to write it more conveniently, there's there's now um from set there's a prefix of size n.

33:48 These are used in computing the i bit and only those. And then there's a long part n l minus n and that's what we call set two here. So set one is these first bits. Set two is the others. And not much has changed. Um I'm just taking this probability and plugging in what I know now for r i function computed on set one. The first n bits. Uh for all the other bits the r1 up to r i minus one. These are still computed from some subsets of the overall bits. They may use some of set one. They will mostly use some of set two because the design can only have D things in overlap. Um but exactly spelling out which ones we don't we don't actually need. Um and the rest is just copied. Okay.

34:49 Now at this point um it it looks like we're we're stuck in the sense that uh there's there's various things going on and these are not independent. I cannot say that this bit here is in any way independent as a random variable from these other random bits in the prefix because they are partly computed from the same seat bits. That's exactly the the point of this design. they can overlap with up to D bits. Uh but maybe this overlap with D bits is is enough to create enough uh dependence that we can't predict or that we that we can predict. Sorry. But in principle it could be that if you base it on the same seat bits that then the output becomes predictable and the reason why that's not the case in the end is that D is small enough. Uh but how to make progress on this one? um in particular because set two is also random. We don't really know uh what it is. Uh but there's a a clever trick which I think in the end is is just the um probabilistic method in disguise but you can abstractly state it um is known as the the averaging principle.

36:03 Um and I'll connect it to this one to this task in a second. Suppose you have some some event on some some random event that depends on two random variables and um we care about the probability of that event happening um then we can always find some specific choice for the first random variable so that the probability remaining so you fix x to be that specific value that's what I mean here little x is a fixed value capital x random variable So you fix x to be that specific value and only average over the possible choices for y and then the probability for the resulting um conditioned event is is never smaller than where you have the total total expectation. And effectively the probabilistic method just means if this is this this is really an expected value right it's the the expectation over both X and Y of this indicator random variable for for the event A of X and Y and an expected value um it cannot be that all possible values that the random variable can take are strictly smaller than the expected value. There must be one choice for X where the expectation on the left is is at least as big as the overall expectation and that's that's the probabilistic method. Okay, so uh nothing really fancy at play. Um the usefulness of this thing is that it's so general and you can apply it to all sorts of events and specifically we'll stick it onto this event. Namely that uh our our circuit on some weirdly defined random bits is the same as this other random bit where there's some dependence between them. Again here the important part maybe uh the important bit here in the averaging principle is the thing that is not stated. There's no assumption on uh x and y to be independent or anything like that.

38:30 I guess if they were independent, you could even uh simplify things. Okay. So let's let's apply this averaging principle to uh our probability here. Um we'll pick as the event where the variable we want to fix is set two. All these other this long string of random bits and the thing that we keep random is set one. And so the event is exactly uh what we had before. The circuit on these previous bits is this uh predicts correctly the next bit. And if we apply the averaging principle, it means there's a a fixed choice little set two. So that this inequality from above is uh is still fulfilled. This one right here it was stated with uh probability over all all of set set one and set two. And now I'm using it to get the same inequality but for a specific choice of set two. Of course I have no idea which ones but uh they exist. So here uh we can again I kept the notation here. Um f is still computed from this subset as picking certain positions in the capital set.

39:49 But capital set now is not really uh as random as before. Is only random on the first n positions and the rest is this fixed string.

39:58 Okay. Now we're using these are still dependent random variables. So it's not clear if we can compute this probability further. But what we know is that our uh our sets I1, I2 and so on come from an L & D design, a combinatorial design. So they have at most D bits in common. In particular, each of these Fs up here can only depend on D bits from set one because our uh one of the sets is exactly the first n bits. So all the others can only use D of those. And that means uh well the other n minus d are fixed to whatever is in uh in set two. And that means all of those these first um I guess there should be a j less than or equal i minus one uh for these first fs uh these are all with a fixed set two functions of at most d variable variables. The rest is hardcoded and that means whatever this is a boolean function with d variables the rest is constant. So you can always write down uh say the conjunctive normal form formula will have essentially this size at at most maybe can be written much more concisely but you'll never need more than essentially all the possible like you do this um truth table and read off uh each row gives you the end of all the variables and then you get an an ore of all the ones. That's your formula. You can read this off in uh with a simple algorithm.

41:45 So in specifically this means each of these fs can be computed with a small circuit uh of of this size. Now we're almost done. Uh we have all of those uh circuits. Now this is not a circuit for f, right? Don't get me wrong. Um this is only a circuit of f evaluated with a lot of the variables fixed to specific values. So that's not a contradiction to f being uh hard for circuits. Not yet. Uh but we can take um all of those circuits for the pseudo random bits that C gets together. All of those written next to each other. Um in the worst case that's that's up to M of those. And uh we also could we also take our circuit C. So that's a long while ago. Let me go um back up here. So that's that's this assumption we started with assuming NW is predictable. So there is some circuit C that simulates the prediction of the next random bits. That was the assumption. And the size of that circuit is bounded by M.

43:03 And uh well we're using this part here. Uh if you look at what m is, it's 2 to the d / 10 and s as of is is at least 2 to the 2d. So there's actually a lot of slack in this inequality here, but that's that's sufficient for that argument. So we have the m copies at most of this little circuit and then we have uh the circuit c from before. Let's see. And in total, that's uh that's at most s at least if you make um make the input size big enough. So you take all of those together. That's one big circuit. Now we call it B. And B has the property that it only takes the random variables from set one as input. Depends on nothing else. And it computes F of set, the thing on the right, with this probability, the same as as before. I'm just inserting what m is and uh using how m and s relate you get this this inequality.

44:12 And now that means we've built a circuit that computes f on well random variables but if you take the average over all possible inputs you compute it correctly with a good bit more than half of the inputs. And that's exactly uh what is not possible because uh we have this assumption that f has a certain hardness against circuits. So the specifically this was the definition of of f h average of f in case you remember.

44:47 So with that again uh we've arrived at a contradiction a long while ago we've assumed that the uh Nissan victim predictor would be predictable that brought a contradiction so that is refuted which means it is unpredictable which by Yao's theorems theorem means it produces a pseudo random output.

45:21 So far this was a a very uh a sequence of very abstract theorems. Um so time to make it um a bit more concrete. Um and I've actually not told you the uh the general algorithm. So there's there's uh one generic part and then we'll make it concrete. I'm going I'm going to show both already. Um the generic algorithm this is just recap the input where the setup is we have some function f a boolean function that supposedly has um this high circuit complexity and then from a random seed we're trying to produce many pseudo random bits how are we going to do exactly the construction because there's all these parameters we have to pick in the full general sense the algorithm is is spelled out here so you pick some uh n first and for that you take um uh you take the largest n that you can pick so that it certain uh condition is true um you stay below your input size and essentially this comes from the uh combinatorial design there we needed uh l to be bigger than 10 n^ 2 divided something I forget and uh that's that's essentially this inequality so you pick n uh as big as you can being below this threshold.

46:45 Uh then you pick a D so that it matches things. Uh you construct a certain design using the algorithm from back then which uh produces 2 to the 10 D over 10 output bits and then you run the generator on on that construction and by the lema we've just shown uh this is pseudo random with the specific parameters.

47:10 Now uh if you uh remember what we we actually want to use this for and the hypothesis about hard functions we can simplify the construction a whole lot the hypothesis back then was there is a function f where the hardness is exponential and you I could have written some constant to the n but it's more convenient to write it as 2 to the delta n um because everything is happening in the exponent then the this inequality for L can be simplified and so effectively you pick N to be like that. If uh if you know your number of uh seat bits L and you know your delta then that's a simple function. It's linear in L. So in a way uh you pick some some the the input size for your heart function is linear in the number of of random bits uh seat bits that you start with but it's actually a good bit smaller right delta is probably a a constant much smaller than one and then then you divide it by 100 still you compute d as well and this weird con this weird expression here simplifies a lot to uh essentially uh something linear in n and hence linear in l.

48:32 Uh here this is even more ridiculously small, right? Um L the number of seat bits we should think of them as being logarithmic. Uh delta is probably a constant less than one. You square that and you divide by a thousand. So that's going to be tiny. Okay, but asmtoically it's it's some uh growing function. And then we generate from that m bits which was 2 to the d over 10. So if you put that in that's the number of pseudo random bits you generate and so this is an epsilon that is a constant. It depends on the delta from the hardness and then divided by 100 and square the whole thing. So it's going to be tiny but it's a constant that doesn't depend on L or any other input parameter.

49:33 And then the um the guarantee you get uh how how pseudo random is it pseudo random against what size of circuit uh that you can also express uh and you have to check that it's it's good enough um which here is is a for for a pseudo random generator we want the guarantee here to be a this uh cube of the output size that was all the way back in the definition pseudo random generator generator needs to generate some s of n cubed comma 110 pseudo random output and that's where this comes from. So you have to check that uh your guarantee that you get is bigger than this this required guarantee and that's also working out with these parameters. So very very long story short uh this construction under the assumption that you can you can have a function f with this exponential uh average hardness. It gives you a pseudo random generator with another exponential um stretch and you can even work out what the epsilon is. It's right here. Okay.

50:57 And um that proves this theorem we had um a long while back where essentially this was this was the claim.