1 00:00:00,012 --> 00:00:06,801 Okay, now we'll talk about mappings, which is a combinatorial structure that is 2 00:00:06,801 --> 00:00:10,356 related to many of the things that we studied. 3 00:00:10,356 --> 00:00:14,106 And it really is an appropriate topic on which to close. 4 00:00:14,106 --> 00:00:18,498 It's kind of a poster child for analytic combinatorics. 5 00:00:18,499 --> 00:00:22,856 So what is a mapping? A mapping is an N-word of length N. 6 00:00:22,856 --> 00:00:28,596 So that is we've got N characters and every one of the characters can be 7 00:00:28,596 --> 00:00:33,969 anything from one to N. So obviously there's N to the N, different 8 00:00:33,969 --> 00:00:40,059 N words of length N or mappings. That, that seems simple enough but 9 00:00:40,059 --> 00:00:46,364 actually there's lots of interesting structure hidden under this. 10 00:00:46,364 --> 00:00:53,543 Because the idea is that every mapping corresponds to a digraph. 11 00:00:53,543 --> 00:01:00,985 So that is, you have for every position in the word you make a node. 12 00:01:00,985 --> 00:01:06,156 So this 37 positions is where we have 37 nodes. 13 00:01:06,156 --> 00:01:13,272 And for every node, you just draw an arrow from the node to its value. 14 00:01:13,273 --> 00:01:19,719 Since there's N different possible values, there's N different possible places to 15 00:01:19,719 --> 00:01:23,104 point. So, so every node has out degree 1, 16 00:01:23,104 --> 00:01:26,843 there's only one place every node can point to. 17 00:01:26,844 --> 00:01:33,265 That's it's position in the mapping, so 30 points to 18, 29 points at 23 and so 18 00:01:33,265 --> 00:01:37,386 forth. But some nodes could be pointed to a lot. 19 00:01:37,386 --> 00:01:41,851 That's the, like 33 is pointed to by 4, 14, 19, and 28. 20 00:01:41,852 --> 00:01:49,130 That appears four times in the mapping. So the sequence of numbers kind of masks 21 00:01:49,130 --> 00:01:57,201 this interesting combinatorial structure. And so once you see this structure then 22 00:01:57,201 --> 00:02:04,167 there's all kinds of it, it breaks up into things that are kind of like trees. 23 00:02:04,167 --> 00:02:09,152 Well they are trees that eventually go to a cycle. 24 00:02:09,153 --> 00:02:15,576 So it's a cycle of trees. But there's independent components too. 25 00:02:15,576 --> 00:02:22,949 So natural questions that come up is well, what's the probability the thing is 26 00:02:22,949 --> 00:02:27,183 connected? Or if it's not connected, what's the 27 00:02:27,183 --> 00:02:33,313 average number of connected components? Or how many nodes are on cycles and how 28 00:02:33,313 --> 00:02:38,516 many of them are on trees? All, all these types of questions turn out 29 00:02:38,516 --> 00:02:43,213 to be of great interest for important applications. 30 00:02:43,214 --> 00:02:49,972 In just, but just as a mathematical curiosity it's quite a fascinating 31 00:02:49,972 --> 00:02:58,002 structure to get out of a simple idea like an N word function from a set of integers 32 00:02:58,002 --> 00:03:02,895 onto itself. So in order to address those kinds of 33 00:03:02,895 --> 00:03:09,825 questions we'll start with something simpler called, a Cayley trees. 34 00:03:09,826 --> 00:03:15,196 So a Cayley tree is a labeled, rooted unordered tree. 35 00:03:15,196 --> 00:03:19,403 So labeled means all the nodes are labeled. 36 00:03:19,403 --> 00:03:25,622 Rooted means that there's one distinguished root. 37 00:03:25,622 --> 00:03:32,554 And unordered means we don't consider the order if there's two children of a root. 38 00:03:32,554 --> 00:03:37,685 We don't consider the order of the two children to be significant. 39 00:03:37,685 --> 00:03:42,933 So there's 9 different Cayley trees of 3 nodes. 40 00:03:42,934 --> 00:03:49,392 So these 6 are all different because of the labels and these 3 are all different 41 00:03:49,392 --> 00:03:54,009 because of the labels. 1, 2, or 3 could be at the root. 42 00:03:54,010 --> 00:03:59,621 But it doesn't matter what order the sub-trees of the root are. 43 00:03:59,621 --> 00:04:06,191 Those are called Cayley trees. Now rather than write out all the 44 00:04:06,191 --> 00:04:12,976 possibilities that a short form to do this is to just write the unlabeled trees. 45 00:04:12,976 --> 00:04:18,121 And then write all the N-words that give those same trees. 46 00:04:18,121 --> 00:04:25,546 So for example, 112 so that's this first tree here 1 points to 1, 2 points to 1. 47 00:04:25,546 --> 00:04:29,378 So that's 1, 1 and then 3 points to 2 and so forth. 48 00:04:29,379 --> 00:04:35,892 111 and that's 1, 2 and 3 all point to 1, so that's the inward and that's the tree 49 00:04:35,892 --> 00:04:39,926 structure that comes out of it for all those cases. 50 00:04:39,926 --> 00:04:45,889 So that's Cayley trees. So now the answer is the number of Cayley 51 00:04:45,889 --> 00:04:49,624 trees. You might have guessed that there's a 52 00:04:49,624 --> 00:04:53,592 power going on, it turns out to be N to the N minus 1. 53 00:04:53,593 --> 00:04:57,046 But that's not at all an elementary result. 54 00:04:57,046 --> 00:05:03,745 We're going to use a technique called Lagrange Inversion eventually to get to 55 00:05:03,745 --> 00:05:08,216 this result. That, that is described on the next slide. 56 00:05:08,217 --> 00:05:13,802 Lagrange Inversion is a classic method for computing a functional inverse. 57 00:05:13,803 --> 00:05:17,952 And it's a, a, a very important and deep theorem. 58 00:05:17,952 --> 00:05:21,117 I'm not going to go into all of the ramifications. 59 00:05:21,117 --> 00:05:29,267 Locations because we use it in, in not quite a, a straightforward way. 60 00:05:29,268 --> 00:05:36,849 So, for example, if I have a function f of u equals z like, f of u equals u over 1 61 00:05:36,849 --> 00:05:43,076 minus u Well then, the inverse of that is the function U equals G of C. 62 00:05:43,076 --> 00:05:49,220 So if I take set Z equal to U minus U, and solve for U, I get U equals Z over 1 plus 63 00:05:49,220 --> 00:05:52,813 Z. That's the inverse and so Lagrange 64 00:05:52,813 --> 00:05:57,651 Inversion's a classical method for, for computing this. 65 00:05:57,651 --> 00:06:01,377 And we'll, we'll see how it applies for us. 66 00:06:01,377 --> 00:06:08,871 So this is the Lagrange inversion theorem that is in, in our situation will be a 67 00:06:08,871 --> 00:06:15,467 transfer theorem to get us from a generating function to coefficients for 68 00:06:15,467 --> 00:06:21,874 problems where we're counting trees. So what it says that if you have a 69 00:06:21,874 --> 00:06:27,808 generative function and it says g of z, and it satisfies this equation z equals f 70 00:06:27,808 --> 00:06:30,977 of g of z. So it's sort of, like it, and I want to 71 00:06:30,977 --> 00:06:35,380 compute the inverse. We have g of z and we want to know what f. 72 00:06:35,380 --> 00:06:40,587 So f of 0 has to be 0 and f prime of 0 has to be non-zero. 73 00:06:40,587 --> 00:06:47,289 Then g of n equals 1 over n coefficient of u to the n minus 1, u over f of u to the n 74 00:06:47,289 --> 00:06:50,794 in, in the function u over f of u to the n. 75 00:06:50,794 --> 00:06:57,103 And again, we're just going to look at applications of, of this theorem. 76 00:06:57,103 --> 00:07:06,118 So just for our example, if f of u is u over 1 minus u then g sub n so u over 1 77 00:07:06,118 --> 00:07:11,647 minus u, so u over f of u to the n, so u over f of u. 78 00:07:11,647 --> 00:07:15,021 The u's cancel. It's just 1 minus u to the n. 79 00:07:15,021 --> 00:07:20,949 So it says that g sub n equals 1 over n coefficient of u to the n minus 1, and 1 80 00:07:20,949 --> 00:07:25,825 minus u to the n. And just from the binomial theorem, that's 81 00:07:25,825 --> 00:07:30,930 exactly minus 1 to the n minus 1. So that says the g is sum of minus 1 to 82 00:07:30,930 --> 00:07:37,076 the nz to the n, which is z over 1 plus c, which is what would have got from algebra. 83 00:07:37,076 --> 00:07:42,257 Now, you can't always get it from algebra. Is the point you have to use the Lagrange 84 00:07:42,257 --> 00:07:46,857 Inversion theorem. So from in the analytic combinatorics 85 00:07:46,857 --> 00:07:54,137 context we're going to apply this as a, as a transfer theorem and you'll see examples 86 00:07:54,137 --> 00:07:57,175 of it. And we'll talk more about it in the 87 00:07:57,175 --> 00:08:03,350 context of the complex plain in part two. Actually we use as a more general 88 00:08:03,350 --> 00:08:11,724 formulation of it where you can for any function h of, of the generating function, 89 00:08:11,724 --> 00:08:18,402 you can get the coefficient of z to the n in that, and it just includes an extra 90 00:08:18,402 --> 00:08:23,073 factor h prime of u, h of u is the basic theorem. 91 00:08:23,073 --> 00:08:29,559 So that's the Lagrange inversion theorem and that's the technique that we're going 92 00:08:29,559 --> 00:08:36,181 to use to analyze mappings. So now let's just before let's look at how 93 00:08:36,181 --> 00:08:42,692 it works for binary trees. So for binary trees we have the standard 94 00:08:42,692 --> 00:08:50,759 construction in the OGF equation. So with Lagrange Inversion we can extract 95 00:08:50,759 --> 00:08:57,950 coefficients immediately form that equation, because it has the form z equals 96 00:08:57,950 --> 00:09:02,462 function. So, so, for use f of u equals u minus u 97 00:09:02,462 --> 00:09:10,977 squared for Lagrange Inversion. So we want to find the coefficient of z to 98 00:09:10,977 --> 00:09:20,122 the n and T of z, and f is that links that square so it's use f of u as u minus u 99 00:09:20,122 --> 00:09:24,632 squared. So we want to find u over f of u is 1 over 100 00:09:24,632 --> 00:09:31,652 1 minus u, so uh,coefficient z to the n and T of z is according to the theorem 1 101 00:09:31,652 --> 00:09:37,268 over n coefficient u to the n minus 1, and 1 of 1 minus u to the n. 102 00:09:37,269 --> 00:09:41,482 And that is easily shown to be the Catalan number. 103 00:09:41,482 --> 00:09:48,831 So that's one example of the application of Lagrange inversion. 104 00:09:48,831 --> 00:09:55,960 So now let's look at Cayley trees. So where we want is the class of labeled, 105 00:09:55,960 --> 00:10:01,561 rooted ordered trees. So in a word that just has that one, one 106 00:10:01,561 --> 00:10:07,986 root and, and it's labeled. And, and we can, sorry unordered trees. 107 00:10:07,986 --> 00:10:15,038 We don't care about the orders. So with the symbolic method we just used 108 00:10:15,038 --> 00:10:22,616 the construction that say a tree is a root connected to a set of trees. 109 00:10:22,616 --> 00:10:31,402 The order doesn't matter so we use set. So that immediately translate to the EGF 110 00:10:31,402 --> 00:10:36,940 equation. These are labeled objects, so we use EGFs. 111 00:10:36,940 --> 00:10:44,178 It's c of z equals ze to the c of z. That's called the Cayley function, that's 112 00:10:44,178 --> 00:10:52,339 the one that enumerates Cayley trees. So in other words z equals c of z over e 113 00:10:52,339 --> 00:10:57,402 to the c of z. So that's using Lagrange inversion with f 114 00:10:57,402 --> 00:11:03,020 of u equals u over e to the u, so coefficient is z to the n and c of z by 115 00:11:03,020 --> 00:11:09,590 the Lagrange Inversion theorem. We look at u over f of u, which is just e 116 00:11:09,590 --> 00:11:15,189 to the u, u over u over u again. So it's the coefficient of u to the N 117 00:11:15,189 --> 00:11:20,385 minus 1, 1 over n times the coefficient u minus 1, e to the un. 118 00:11:20,385 --> 00:11:27,175 Which is n to the n minus n factorial. So the number of Cayley tress is N to the 119 00:11:27,175 --> 00:11:31,325 N minus 1, and that checks with our small values. 120 00:11:31,325 --> 00:11:37,780 So that's a Lagrange Inversion, now there to enumerate Cayley trees. 121 00:11:37,780 --> 00:11:45,556 Now that's just trees now we can work up to look at more complicated structures 122 00:11:45,556 --> 00:11:52,556 like connected compliments and mappings. Remember, mappings are cycles of trees. 123 00:11:52,556 --> 00:11:57,989 So this isn't all the mappings theses are the ones that are just the single 124 00:11:57,989 --> 00:12:02,522 connected component. So these are all the possible things that 125 00:12:02,522 --> 00:12:08,257 can happen, all the possible structures, connected structures that you can get. 126 00:12:08,257 --> 00:12:18,632 With three words with three mappings so, so for example we saw 111 so that's, or 127 00:12:18,632 --> 00:12:24,371 222 so that's when they all point to the same thing. 128 00:12:24,371 --> 00:12:31,827 But you can get a structure like this, where two of them point to each other and 129 00:12:31,827 --> 00:12:35,407 so forth. So these words, so one points to two, say 130 00:12:35,407 --> 00:12:40,130 this is one, one points to two, two points to one, or this would be one. 131 00:12:40,130 --> 00:12:45,320 One points to two, two points to one, three points to one, that corresponds to 132 00:12:45,320 --> 00:12:48,613 that. So these are all the ways to label and get 133 00:12:48,613 --> 00:12:54,442 bad structure and those are connected so how many different ways are there to get 134 00:12:54,442 --> 00:13:00,358 cycles of Cayley trees that's what the component is and that turns out to be n to 135 00:13:00,358 --> 00:13:06,384 the nth times square root of pi over 2n. And the analysis of that is it's again 136 00:13:06,384 --> 00:13:12,104 straightforward using the symbolic method and the Lagrange Inversion. 137 00:13:12,104 --> 00:13:18,680 So, this is a typical cycle of trees and clearly the construction we're going to 138 00:13:18,680 --> 00:13:22,441 use is cycles components of cycle of trees. 139 00:13:22,442 --> 00:13:27,504 And then from the symbolic method, just log of 1 over 1 minus. 140 00:13:27,505 --> 00:13:32,900 And that is immediately available for a Lagrange Inversion. 141 00:13:32,901 --> 00:13:39,066 Again we've got, f of u equals u over e to the u and now our function is because 142 00:13:39,066 --> 00:13:45,788 that's what the Cayley function does. And then our extra function in the Berman 143 00:13:45,788 --> 00:13:52,378 form is H of U is log of 1 over 1 minus U. That's going to immediately get it, so H 144 00:13:52,378 --> 00:13:57,900 prime of U is 1 over 1 minus U. And then we still have the E to the UN 145 00:13:57,900 --> 00:14:04,907 that's U over F of U to the N. So, our number of connected components is 146 00:14:04,907 --> 00:14:13,432 1 over N coefficient minus 1 in, in that formula and so just doing the convolution 147 00:14:13,432 --> 00:14:21,877 it's N to the K minus 1 over K factorial. And change N to N minus K and we, our 148 00:14:21,877 --> 00:14:30,017 coefficient is N factorial times that and that's our familiar Ramanution function, 149 00:14:30,017 --> 00:14:35,947 which leads to an enumeration result. So that's a number of connective 150 00:14:35,947 --> 00:14:40,222 components in mapping. So the probability that components is 151 00:14:40,222 --> 00:14:43,975 connected is divide that by N to the N square root of pi. 152 00:14:43,975 --> 00:14:50,130 Connected components in mapping comes directly from symbolic method coupled with 153 00:14:50,130 --> 00:14:54,910 Lagrange Inversion. And then mappings, how many mappings are 154 00:14:54,910 --> 00:14:59,371 there? So that's going to cover all possibilities 155 00:14:59,372 --> 00:15:04,720 and again what's a mapping? A mapping is a set of cycles of Caley 156 00:15:04,720 --> 00:15:08,348 Trees. So it's going to be E to the log of 1 over 157 00:15:08,348 --> 00:15:11,676 1 minus Cz which is just 1 over 1 minus Cz. 158 00:15:11,677 --> 00:15:19,235 And that one we can get with the extended Lagrange inversion with our h function 159 00:15:19,235 --> 00:15:25,348 equals 1 over 1 minus If you do the math, h prime of u is 1 over 1 minus u squared. 160 00:15:25,348 --> 00:15:31,492 So it's coefficient of uvn minus 1 over n and, and 1 over 1 minus u squared, you 161 00:15:31,492 --> 00:15:35,885 could do UN. You do that convolution in this time, the 162 00:15:35,885 --> 00:15:39,816 sums collapse. Just works out n minus k from 1 minus u 163 00:15:39,816 --> 00:15:45,549 squared, [inaudible] factorial [inaudible] and then we just get two sums and they, 164 00:15:45,549 --> 00:15:50,238 they all cancel except for the last term, n to the n over n factorial. 165 00:15:50,239 --> 00:15:53,740 So, so the numbers of mappings is n to the n. 166 00:15:53,740 --> 00:15:59,608 As expected from the trivial argument. So sure there's a trivial argument that 167 00:15:59,608 --> 00:16:04,920 tells us the number of mappings but analysis gives the entire structure that 168 00:16:04,920 --> 00:16:11,228 we can use for, for analyzing all sorts of properties and we'll go into the details 169 00:16:11,228 --> 00:16:15,559 later on. Just for example an interesting property 170 00:16:15,559 --> 00:16:19,266 of these functions is something called a rho length. 171 00:16:19,266 --> 00:16:26,510 So the Rho Length of a function, so if we start at a given point and just apply the 172 00:16:26,510 --> 00:16:30,776 function. Say you have a function like x squared 173 00:16:30,776 --> 00:16:37,012 plus 1 mod 99. So 3 goes to 10, 10 100 plus 1 101 99's, 174 00:16:37,013 --> 00:16:41,437 is 2. And that square that and go to 1 that's 5, 175 00:16:41,437 --> 00:16:47,012 and so forth. You eventually get to a point where you 176 00:16:47,012 --> 00:16:51,035 hit a cycle. So that's called the Rho Length, the 177 00:16:51,035 --> 00:16:56,620 number of times that you iterate the function until it finally repeats. 178 00:16:56,620 --> 00:17:02,212 Now so in the mapping wherever you start, you're always going to wind up in a cycle, 179 00:17:02,212 --> 00:17:06,633 so there's a roll length associated with each point in the mapping. 180 00:17:06,634 --> 00:17:11,627 And this is a mapping where we have a formula to tell us what it is, but random 181 00:17:11,627 --> 00:17:15,889 mappings tell us the same thing. Well, one thing to think about is, what 182 00:17:15,889 --> 00:17:18,498 about an algorithm to compute the row length? 183 00:17:18,498 --> 00:17:22,713 It's kind of a fun problem. You could say, well I'll just use the 184 00:17:22,713 --> 00:17:25,586 symbol table. I'll keep track of all the values I've 185 00:17:25,586 --> 00:17:29,214 computed. And then that way, I'll know when I get a 186 00:17:29,214 --> 00:17:32,900 repeated value. But in practice you can't do that because 187 00:17:32,900 --> 00:17:37,490 we talked about in real applications we're doing this for huge numbers like 100 188 00:17:37,490 --> 00:17:40,643 digits number. And it's no way you can have enough 189 00:17:40,643 --> 00:17:44,825 memories to keep all the possible values. So what do you do? 190 00:17:44,826 --> 00:17:50,992 Well there's a famous method due to Floyd. Which is the tortoise and hare algorithm 191 00:17:50,992 --> 00:17:56,177 where you keep two variables. One that iterates the function just once 192 00:17:56,177 --> 00:18:03,453 and the other one iterates it Twice, So, so, for example, so a and b start at the 193 00:18:03,453 --> 00:18:10,303 same time, place at time t equals zero. And we iterate a by 1 and b by 2. 194 00:18:10,303 --> 00:18:18,078 So, then iterate a by 1 and b by 2. And so you know, B's going to go around 195 00:18:18,078 --> 00:18:24,775 the cycle and eventually they catch up. And it's not difficult to see that 196 00:18:24,775 --> 00:18:30,895 eventually they're always going to catch up and when they do, actually, the roll 197 00:18:30,895 --> 00:18:36,835 length of starting at that point is between T and 2T if T's is the number of 198 00:18:36,835 --> 00:18:40,883 times that you had to go to get [unknown] to match. 199 00:18:40,883 --> 00:18:47,930 So that's an interesting in that doesn't use any extra memory, it's just comparing 200 00:18:47,930 --> 00:18:52,885 those two variables, so that's computing the rho length. 201 00:18:52,885 --> 00:19:00,031 So, with mappings, again starting at every point you've got a rho length and that's a 202 00:19:00,031 --> 00:19:06,806 parameter that's interesting to study. In this other like tail length. 203 00:19:06,806 --> 00:19:14,228 That's how long until you hit the cycle. And again, number of components, number of 204 00:19:14,228 --> 00:19:20,039 trees and so forth. Now using the same method of construction. 205 00:19:20,040 --> 00:19:26,137 And using bi-variate exponential generating functions it turns out that 206 00:19:26,138 --> 00:19:31,626 just, just give an example. So like number of components is a mapping 207 00:19:31,626 --> 00:19:38,087 is a set of cycles of trees but we mark the cycles and that will tell us the, the 208 00:19:38,087 --> 00:19:42,161 number of components. There's one for each cycle. 209 00:19:42,161 --> 00:19:47,364 So immediately, we get the EGF equation 1 over 1 minus Cz to the u. 210 00:19:47,365 --> 00:19:53,554 And then we can work with that equation to answer questions like, what's the average 211 00:19:53,554 --> 00:19:58,688 number of components? Or if you do a number of trees then it's a 212 00:19:58,688 --> 00:20:04,125 set of cycles of trees, and they just mark the trees, and you get this other 213 00:20:04,126 --> 00:20:08,468 function. So we'll talk about this analysis in more 214 00:20:08,468 --> 00:20:12,514 detail in part 2. But for now I just want to motivate the 215 00:20:12,514 --> 00:20:18,814 study of mappings and it works out to be actually without that much work, that we 216 00:20:18,814 --> 00:20:25,402 can get all these properties of mapping. So for example, the expected Rho Length in 217 00:20:25,402 --> 00:20:29,639 a random mapping is about the square root of pi N over two. 218 00:20:29,639 --> 00:20:35,788 You know, so why is all this relevant? Well here's a, an actual, application 219 00:20:35,788 --> 00:20:40,969 where, it matters. This is a famous method for factoring an 220 00:20:40,969 --> 00:20:46,131 integer a huge integer. And so what is called Pollard's method, 221 00:20:46,131 --> 00:20:51,466 and what it does is it iterates a random quadratic function to find a cycle. 222 00:20:51,466 --> 00:20:57,664 It's pretty much like the function that I just talked about we take f of x equals x 223 00:20:57,664 --> 00:21:01,643 squared plus c. Until finding a cycle and we do it like 224 00:21:01,643 --> 00:21:06,972 with Floyd's, Floyd's algorithm where we take two variables and iterate it once for 225 00:21:06,972 --> 00:21:10,575 one of the variables, and iterate it twice for the other. 226 00:21:10,575 --> 00:21:14,705 And now we use a random value of c, and a random starting point. 227 00:21:14,706 --> 00:21:21,525 And, and keep going until this particular condition is satisfied having to do with 228 00:21:21,525 --> 00:21:25,473 the GCD and when it's done you get a factor out. 229 00:21:25,473 --> 00:21:32,427 It's, it's quite an amazing algorithm. So this is just an example that is doing 230 00:21:32,428 --> 00:21:38,886 the same thing as Floyd's algorithm does. And when the GCD of these things is not 231 00:21:38,886 --> 00:21:43,941 one then you've found a factor. So you know, why does it work? 232 00:21:43,941 --> 00:21:48,597 Well, it's actually not too difficult to see how it works if you know number 233 00:21:48,597 --> 00:21:51,494 theory. Although it's definitely magic if you 234 00:21:51,494 --> 00:21:54,867 don't. That's not really the point of why I want 235 00:21:54,867 --> 00:21:59,162 to bring it up now. The question is, how many iterations does 236 00:21:59,162 --> 00:22:04,410 Pollard's algorithm take? And, well one things that seems reasonable 237 00:22:04,410 --> 00:22:09,088 to do is to assume that this function is not a random mapping. 238 00:22:09,088 --> 00:22:13,937 But since you're taking a random C and a random starting point. 239 00:22:13,937 --> 00:22:19,221 Maybe it's got the same kind of characteristics as a random mapping. 240 00:22:19,221 --> 00:22:25,902 And it's conjectured, actually, that the, random quadtratic function of this type is 241 00:22:25,902 --> 00:22:29,645 asymptotically equivalent to a random mapping. 242 00:22:29,645 --> 00:22:34,967 And in a random mapping, the rho length is square root of pi N over two. 243 00:22:34,967 --> 00:22:39,888 So you can factor, a number you can factor a number N. 244 00:22:39,888 --> 00:22:46,126 And square root of N cycles, which is a lot faster than trying every factor. 245 00:22:46,127 --> 00:22:51,201 And Pollard actually used this method to factor his integers a while ago. 246 00:22:51,201 --> 00:22:55,407 And it's typical of the kinds of thing that people are trying to do in 247 00:22:55,407 --> 00:23:00,091 cryptography now a days is study properties of these kinds of functions. 248 00:23:00,091 --> 00:23:04,981 Analytic combinatorics and properties of mappings plays a role in this kind of 249 00:23:04,981 --> 00:23:11,120 research. So I wanted to end with a real application 250 00:23:11,120 --> 00:23:22,064 like that, and, and with mappings they are quite fascinating combinatorial 251 00:23:22,064 --> 00:23:23,742 structures.