Mathematical Games Hosted by Ed Pegg Jr. [Episode 21: Ordering and Canonical Forms]

Sa. Hello, everyone. I'm going to wait until 11 here, which will be quite soon. I don't have a second hand on my clock. Here we go. Okay, Ed. I'm Ed Pegg Jr. Of Wolfram Research, and today I'm going to talk about ordering in canonical forms. This mathematical game series is part of a homage to Martin Gardner, who used to run mathematical games for Scientific American. And he talked about many things, including sometimes the best way of presenting something for human understanding. He tried to keep things very simple, but that didn't mean he didn't manage to present a lot of material, because sometimes something that's a complicated concept, if you present it the right way, it's somewhat simple to understand. So we've got many things and demonstrations that relate to ordering and canonical forms and whatnot. So what is canonical? It's a standard way of representing something. And Wikipedia mentions it's the form which provides the simplest representation of an object and allows it to be identified in a unique way. So one famous canonical unsolved problem is Fermat's last theorem. A to the n plus B to the n equals C to the N. And that was sort of the canonical unsolved problem until 30 years ago today, when Andrew Weil saved it, solved it. But I don't have the space to go into that one interesting way of presenting things. Martin Gardner wrote a column about graceful graphs. So you've got a graph and you label the vertices with numbers, and you want all the edges to represent the numbers 1 to n, where N is the number of vertices. So, for example, in this first graph, 0 and 1 have a difference of 1. So this edge would be labeled 1. I'm not sure where 2 is. Oh, 2 is 16, 18 has a difference of 2, and so on, ending with 0, 20 for 20. So this has 20 edges, and if you put the differences on the edges, you'll get the numbers at 1 to 20. So one thing, I reread Martin Gardner's book column on graceful graphs a few years ago, and when I saw that, I decided I would find all of the smallest graceful graphs with valences five through eight. And they're rather interesting. And this is a unique graph. These seem to be the best way of presenting these particular graphs. Here's the valence 9 graph. This looks pretty good. And one thing that came out of this study was this conjecture that the smallest graceful graph of even valence has 3n squared edges. We haven't proved that, but that's something that bears out from these constructions. I made from graceful graphs. So easier than graphs are numbers. What's the canonical form of a number? Well, usually it's a finite sequence of digits that doesn't begin with zero. So this is not canonical. This is a canonical rational fraction uses two relatively prime integers such as these here. And a canonical rational number is either an integer or a canonical rational fraction. So here's some examples. So we can go further into fractions. If a fraction is in the correct form, it has a position within the calcan wilf sequence. So for each of these fractions, their positions within the sequence is the numbers 1 to 42. So we've got various functions where you. You can enter any integer number and it'll give you the fraction that corresponds. And you can enter any fraction and get the number that corresponds with it. So when something is in a canonical form, it usually has a canonical ordering. And you can, if you know how that ordering works, you can go anywhere into it and pull out what the relation is. Here's a tree showing how the calc and well function can be constructed. We're basically. There's a certain way that the numerators and denominators work. So we can list the denominators. If we prepend a one to them, we get the numerators are the same as the denominators, but with a one at the start. And this whole sequence is known as the thus sequence, which when plotted, gives a weird structure. If we look at the various fractions, we can take their radii, and when you order them, they make this nice pattern called the forward circles. So if you have a continued fraction where you represent a rational number as an ever increasingly complicated fraction, you get odd things. For a rational number, the list of digits in the continued fraction is finite. For most numbers, such as PI, it's an infinite series. But for quadratic numbers, it has a repeating form. So basically you'll want to indicate how it starts repeating. So here's the first few fractions 1 to 99, showing how they increase in size. So 94 has a very long square root of 94, whereas square root of 56 has only two digits in the repeating fraction form. And here's a list of. Square roots with increasingly large size. You can see they get pretty big. So here's a number. What's the canonical form of an integer? Well, usually you write up the number unless it gets big. When it's a really large number, you usually want to represent it in the simplest way. So this number is 3 to the 3rd to the 3rd 18 factorial is this number. So what is the canonical form of a large number? Usually that can be difficult to find. Here's an example of three numbers that are very close to each other. But it's. And all of them have. All three of these methods have simple forms. But if you were given these three numbers, it wouldn't automatically be obvious how you could find these things. So one trick that is usually used in number theory is to represent numbers in a factored form. That doesn't always work. I forgot to explain where I was going with that. But some numbers do have nice forms. And one way of finding them usually is to look them up in oeis, the online encyclopedia of integer sequences. So, for example, I could look up this number which has this odd property that it's almost divisible by its reverse, and you can find a index entry about that has that number in it and it gives more examples of it. So one thing I did with this sequence was I managed to find more examples of it since it was unsolved. I used a concatenate integers and I just basically looked at the numbers there and saw if I could add anything. Here's a nice property of 2024. The square of 2024 is 4,096,576, which is the concatenation of two square 64 squared and 24 squared. Another way to look up numbers is the inverse symbolic calculator. So I made this number up randomly. It's nothing special. And here are the close entries for that number within the inverse symbolic calculator. WolframAlpha also has something similar to this. Did I have something at the end of this? No. So the canonical form of an integer also has where it's being stored. If it's on a computer, it's usually in binary. So here are the important cutoffs for a for a number when you're dealing with computers. Hacking dates back to 1972 with the MIT research memo hackmem, which was greatly expanded. And the original hacking was basically how to do fast and interesting things with numbers in computer memory. But that was 52 years ago. So much has been changed. But the exact form a number is stored in is usually interesting. So 18 factorial would be stored in hexadecimal, which looks something like this on a computer. So we can look at the base form in base 16 and it looks something like that. So we can use this function to see how various numbers are stored on a computer system. And here's a few examples we can go Back and forth, real to hex string or hex string to real. If you're ever dealing with a memory dump from a system, this is something that could be useful. And here's how various numbers would look like in memory on a computer system. So for decimals, usually the question is how many digits do you want? So here's PI to 20 digits. How many decimal numbers have two digits of accuracy? I get a count of 282. But I'm not sure that because of things like this repetition here due to Randolph errors with padding or repetition, though, for example, 1 or 11, we often represent these numbers in a recurring form. So there's two canonical ways of representing decimals, and here's various recurring decimal forms for numbers in the very sequence, which is all the numbers with a denominator of 16 or less. And here's a list of increasingly large recurring decimals with these numbers, which I found in oeis. For algebraic numbers, things get more tricky. For example, these four numbers, we can do a union of them, but it turns out these are all the same number when they're sufficiently simplified. This is something I deal with a lot. I almost always use root reduce when I'm dealing with numbers, which might simplify that usually will make everything the same one thing under radicals, often you'll have a problem with negative something. The radicals can have up to four different forms for the same number. So that can lead to spurious results. So I almost hit things with root reduce when I'm trying to get concrete answers. And that gives a canonical form that I can rely on for a number. So here's 10 different powers of the golden ratio. And I can represent them as an algebraic number in the form of that number field for the golden ratio, and it gives the A plus B times the item representation for that number. You'll notice that there's a Fibonacci sequence going on. When I'm trying to figure out what algebraic field I'm in, the first thing I do is I look at the discriminant. When I see a discriminant of 5, I know I'm in the golden ratio. When I see -23, I know I'm within the plastic constant. When I see -31, I know I'm within the super golden ratio. So if you were ever dealing with algebraic fields, those are some interesting tricks. And this whole talk will be on Community shortly after this talk is over. The canonical form for a line. Here's some random points. What is the fastest way we can identify all the lines with three or more points. So basically we want to get line equations between everything and one way is to use the Hessian line form. One issue I found with this problem is that if you just toss these to a program with nothing but hope, you'll get multiple equations representing the same line and that doesn't work. The Hessian line works, but it's not a very fast method. It turns out I found that the fastest way by a great order of magnitude is to use row reduce. First append 1 to the points, for example for 3, 2, 7, 5, appending 1 to the end and then do a row reduction gives this form and this is about a million times faster than other ways that I've tried. So for example, for random sets of points on this particular line, here's row reductions of the row reduce and they're all the same. So this method seems to work well for given random points on a given line, it always returns the same thing. This happens to work in higher dimensions as well. So an extraordinary line is a line with three or more points. Going back to this original problem, where are the lines of three or more points? We can do all the pairs of lines and it turns out these points in cyan are the extraordinary lines, the lines of three or more points. And we can continue doing this. There's a resource function findextraordinarylines that does all this automatically very quickly. The canonical form of a line also can be in a normal form. So we have a point on a grid. This is the normal form for the line, And it's basically a perpendicular vector. The canonical form for a plane works similarly. One thing I played around with making this talk, the row reduce method seems to work very well for this, for planes as well. But I haven't looked at a program for that yet. But I plan to look at that as a programming exercise to see whether that actually does work as a nice way of representing planes quickly. And vectors and planes, same thing here. The there's a vector for representing a plane. And the three points will also determine a Hessian plane, which we have a function for. So matrices also have canonical forms and there's many canonical ways of tearing a matrix apart. Here are some of them and here's some examples of what those look like. Canonical forms are rather far reaching I found while putting this talk together a few weeks ago. Elkies and Klein Sprun found an elliptic curve of rank 29 at least 29. And here it is. Here it uses 60 digit numbers. So it's rather extreme I'm not going to say this number. And I decided I would look at the past records to see what they look like. So what do these points look like? So, for example, with the one by Alky's, here's what the points look like if you plot them out. Looks like points on a line. So they look better if we can use log on them. So here's a curve that pops out when you use log. And I decided to look at all of them. So here's all the record setting elliptic curves as sets of points. These are the independent points of the elliptic curves, but some of them don't show up. Well, I plan to continue working on this to see if I can give a really good presentation for all these curves. Here's a simpler elliptic curve for any set of three numbers adding to zero, for example, 1 plus 6 minus 7, that adds up to zero. Any set of three numbers that adds to zero is a line of three points in this figure. For example, 6 minus 2 minus 4 is zero. So there are 32 tuples making lines of three. So there's three in a row, 32 times in here, and each time it adds up to zero. So when I've shown this to people, minus one minus two plus three is zero. People have asked me how I found this. Well, I found it with using canonical forms. So if you have nine random points, you can make a cubic. So for example, here's nine points, they make this cubic. But the coefficients here are kind of high. Is there a way we can reduce the coefficients? Well, if we just subtract numbers from them, we find that subtracting 6 and 2 from the given numbers gives this one with smaller coefficients. So this is a. Since this is the simplest one I can readily find, I'm calling this the canonical form. If I wanted to go further with this, I would also look at the eight rotations and reflections for these and get something even further down. And then once you have nine points, you basically just plug them into this matrix and a curve will pop out based on any nine points. So I did that on a small lattice and we get these various nice curves that have a lot of lattice points, but each of these, each time I put in a set of points, each of these graphs that I'm showing here would pop up thousands of times. But since I was canonicalizing everything, I eliminated all that repetition. So I only had to look at a few hundred graphs instead of millions. And these were the ones that popped up as being very nice. So this is the main point of canalation. It removes a lot of repetition when you're going through results. So one thing that pops up frequently is you have an array of values. Say you had the F Pentomino. If it's just as a grid of five ones in a three by three matrix, how do you represent that? The best way, and one way is just to rotate it and reflect it in all the various ways. And you get these. And this would be after a sort would be the first. So just by a simple sort you can get something canonical after an array rotation. And this is a resource function. Here's a community post that does fun things with the 120 cell. And he used about 80 lines of code to produce the 600 vertices. So I decided I would shorten that code to something really short. This is about 1/50 the length of the code that he used. Usually shorter code is canonical, but not always. And to be fair to Clayton, he published this community post a year before I published the signed permutations WFR function. So I mentioned short is usually better with programming. So here's a short program for finding whether 19,519 is prime. Well, it's not. It's divisible by 149. It's 149 and whatever the opposite number is. But brute force is usually at terrible programming methods. It's simple to write, and I write brute force problem programs all the time, but they're almost never the best program. So the canonical algorithm for solving something is really the fastest algorithm, no matter what length it is. We can look at canonical point placements, e.g. the Thompson problem. What's the best way of putting points on a sphere? This is a problem that's unsolved over 12 points, even though they have configuration they believe are optimal. But no one knows how to prove that they're optimal. There's also the Heilbronn problem. What's the largest possible smallest triangle within a square within a unit square? This one also is on shaky ground over about 13 points. We can also look at canonical forms of proof. Here's one proof that's believed to be canonical by Euclid. Are the primes finite? Assume they are. Multiply all the primes and add one. The resulting number is either prime or a product of unlisted primes. Therefore, the primes are infinite. This is a proof that's 2,500 years old. Paul Erdos would call this a book proof. He believed there was a somewhere in the universe was a book that held all the Best proofs. And he frequently mentioned whether something was in the book or not. And this is a proof that's definitely in the book. One type of book proof would be purely visual ones, proofs without words. So this is a visual proof that the sum of cubes is equal to the square of the sum of the values, which is Nicomaches theorem. Here's another example of a more visual proof by Branchian. If you have a hexagon. Oops. And you. Oops. Now it's going crazy. If you move the points of a inscribed hexagon, the diagonals are always concurrent. And this is a demonstration showing that it seems to be true. It's not an actual proof, but it's visually very compelling. Here's another visual item. We have some random points that make a polygon. Now it's easy to just take the midpoints of the polygon and connect up to make a another polygon. But can you go backwards? If you're given a set of points that are midpoints, is there a polygon that has those points as its midpoints? Well, it turns out that you can go backwards. There is a program that does that and I'm calling that the midpoint polygon program. And here it is. So for these given points up here, here's the midpoint polygon and here's a picture of it here in green. The green polygon here is the original. So it is possible to go backwards. And let's just see what happens if I try this again for something random going to run. Is that working? My code doesn't seem to be actually functioning. Oh well, doesn't seem to want to run that. You can also do here's proof without words that the infinite sum of the super golden ratio in this form. Has a finite set. So this whole thing is equal to the super golden ratio. This part here is equal to the super golden ratio to the power of minus 2 to the power of minus 3 to the power of minus 4 to the power of minus 5 to the power of minus 6, and so on. So the infinite sum of the super golden ratio to the negative power starting with two is itself. The supergolden ratio is related to the Neriana cow problem of 1536, where in Fibonacci's rabbit problem each generation had a number of offspring equal to itself. So starting with one and two rabbits, there's three in the next and five in the generation after that. For Neriyama, he had things skip a generation. So one plus three is four, two plus four is six. Three plus six is nine and so on. So this is a super golden ratio. Here. We can also look at canonical diagrams. So when does a diagram become obvious? Once its existence is known. So using the super golden ratio again we get a complex root and then we look at powers 0, 1, 2, 3, 4 and negative the second power. If we. And this is for the polynomial psi squared plus one equals psi to the third. And these points actually are one apart. This is the origin here. This is psi to the 0 or 1. So these values are actually marking their positions based on the actual powers. And if you divide them up like this, you get a substitution fractal. All the quadrilaterals are similar to each other and scale by the super golden ratio. I've described this to a few mathematicians and basically this is. Once you give it just this much info and say that this diagram exists, that's enough information to create the diagram it's self describing. There's something similar with the plastic constant which has the rho as its variable. You get the same sort of thing. If you take a look at these powers and connect up the points, you get a substitution fractal. And again these points here, zero and rho to the zero is one, rho to the first plus one equals rho to the third. And rho here is the complex root of this, the positive complex root. This is just knowing this function here, rho plus one equals rho to the third is enough to build the diagram. The plastic constant allows weird things with distances. The distances here between the vertices are the various powers. And you get a K5 of powers with distances from 0 to 8 with the distance of 3 repeating. Here's another weirdly visual item is Martin's ellipse. You can take any triangle and if you represent the points as complex values, multiply them together. So basically x plus this value, x plus this value x plus this value, multiply them together and you take the derivative, you get the foci of an ellipse perpendicular to the midpoint of the triangle. So with the function point, set derivative roots, where you take the points and you take the derivative, you get that with these three points, their derivative, the foci of the ellipse is 1 and minus 1 0. And here's a picture. So we can do something similar with the 3, 4, 5 triangle. But I twisted it so that we would get the same vertices. And here's the Martens ellipse again. And one thing I wondered while making this top is what happens if you take all triangles and you Transform them so that their foci are one and minus one. How do those triangles look? Well, I didn't manage to finish that, but that's something I plan to look at soon. You can look at the canonical presentation for a knot. So here's various knots and they're represented to have as few crossings as possible. And that could be a tricky thing to find out, especially when there's more than one ways of representing the same knot with the same number of crossings. A person by the name of Schubert came up with another way of representing a knot using what he called bridges. So here's a knot in the normal form that's shown. In fact, this is the canonical crossing form, but over here is the Schubert 2 bridge form. Unfortunately, all the knots Schubert looked at needed only two bridges. But there's more complicated knots such as this one here, which require three bridges. And even though I spent almost half an hour looking for it, I was not able to find the simplest four bridge knot or five bridge knot knot. So the Schubert method was more or less abandoned. But I'd still be interested in finding out all the various bridge forms of various knots. We can also do such simple things as canonical list rotation. So you've got these numbers and you want them to stay in the same order, but it's fine to rotate it or reverse it. What's the canonical form of that list? And you basically just rotate it in all possible ways and reflect it. And you get that. I end up using this one quite a bit. Some of these things, once you've got a method for simplifying things and eliminating repetition, you wind up using that much more frequently than you would ever expect. This is something I talked about in a previous talk, the canonical form of a polyhedron. You can always represent a polyhedron so that each edge is tangent to the unit sphere. So this is the canonical form of this particular polyhedron here. And here's other canonical forms of polyhedra with six vertices. And here's the hexahedra and the heptahedra. One. One polyhedron that came up with a canonical form in a weird way is the ten sided die. If you've ever done any gaming, take a look at your ten sided die. You'll notice that it has a square cross section. After making in the early years. That wasn't the case back in the 1980s. They had different sizes for ten sided dice, which is the Scalene trapezohedron. But once they figured out that you could do a square cross section for this particular polyhedron everybody started doing it. So all 10 sided dice made now have this square cross section. If you look at it the right way. In fact, it'll have 10 square cross sections. If you look at it in all possible ways of getting that particular configuration. For graph. If it's possible to represent it in as few crossings as possible, that's usually what you want to do. So here's a planarity exercise. And I mentioned that here, what is the best way to present a graph. You usually want to have maximum symmetry. Minimal crossings if possible. All edges the same length. And if you're really being picky, all vertices on lattice points. Now usually it's impossible to do all of those things. So here's a Pederson graph. The first few have symmetry. We can put it into a pentagon, hexagon, octagon or nonagon. We can also do minimal crossings. Here's two ways of doing it with two crossings. Here's a way of doing it so that all the edges are the same. And here's a way of putting it onto a lattice. Also over here, which is the best graph presentation? Well, this one sort of wins out for most commonly used. But all of these are good graph representations. Here's a similar set of representations for the dodecahedral graph. Here's a planar representation, but the other representations here look rather nice. So it can be done with zero crossings. Here's a lattice method that shows that you can have what is that? Eight dominoes representing the decahedral graph and all lines the same length. We're always trying to present things in the best possible way. So for example, if you look at version 12 and you look at this particular graph, it has this form. But I found that you can make it nicer with this form. So this is how it looks like in the current version. There's many graphs where we don't have a nice form. For example, the 47 cage graph. Rather nasty looking. And so far as I know, no one knows how to present this particular graph nicely. If you can find a nice form for it or any of the other graphs in graph data that look ugly, I'd love to see them. And there's quite a few. I mentioned ordering and sort is usually a good way of doing so here I've got a random ordering of the values 1 to 9 and if I apply sort, you get numbers 1 to 9. That's the canonical ordering for the numbers. For points things get a little bit trickier. So here's nine points. We could expand it to 25 points. And here's how the graphs, here's how the points look like if we order them just by plain sort. We could also sort by last and we get a different ordering. If we sort by their total, we get this stranger arrangement of the points. Things get much stranger if you have negative values tossed in. So if we look at the ABS of the total, it's a complete mess because the angles aren't being accounted for. When I just do absolute value, things look nicer if I do the ABS ARG form of the complex numbers. Things tend to be more rotational that way. But there's still a lot of messiness over here. So usually if we're dealing with two dimensional space, a, a spiral is sometimes used. For. How do we sort is another question. What is the optimal sorting method? So for a given number of points there are various networks that are shown to be better than all others. Here Steven has listed various sorting methods. Here's the transposition method, insertion method, pairwise batcher and the optimal. So here's the optimal sort for 14 points. Your optimal for 16 is that incrementing. This doesn't seem to be incrementing. We can also look at different sorting methods this way. So here's the shell sort of which takes 172 steps. The bubble sort which takes 467. Insertion sort which takes 42 steps and cocktail, I'm not sure what that one is, which does another 467. So one of the first algorithms that's covered is how to sort of. And there's different optimizations that can be done, but we can also order things in a different way. For example, the gray code orders integers like this. And the reason for that is you'll only want one bit to change at a time while you're going through the numbers. So where might that be used? One frequent use of this is in satellites where you're trying to get the intensity of light from a star. They've got these very sensitive detectors that only lets a small point of light in at a time and it's hitting a collector which is based on the gray code to figure out what the angle is. You don't want the number to change radically just going over these detection lines. So they use the gray code to eliminate wide fluctuations. So one thing I looked at a while ago is the primitive polynomials in binary. And the columns here are the, are the primitive polynomials. I wondered what's the best way of presenting these. They. They look rather blase when you just sort them normally. So I Wondered is it possible to make something that looks like a connected cavern? And I found out that it was possible to do that. And I thought this looked better than this. And so here's different presentations for the canonical polypolynomials, particular Galois fields, I think they look better than others, but that's perhaps subject to taste. If you have a canonical ordering, you can get a canonical indexing. So for example, with subsets, tuples, permutations and order tuples. So here's subset ordering. If we order by the reverse order by the greatest value, we can get a series of three tuples that extends up to infinity and we can also get their particular indices for them. So for example, here's some three tuples that have index of a billion and 1 billion and 2 and so on. And we can also say look at the n tuple that has index 20, 24, that's 724 for a 2 tuple, and so on. 21, 22, 23 is the 2024th free tuple, and so on. Here's what the first few three tuples look like where 012 is 0 comma 1, comma 2. Here's the trillionth number that has binary weight 5. So there's if we look at the binary form of this number, there'll be eight ones. We can also order tuples. For example, we can map tuple index to these tuples here. And this is the tenth tuple with 000 being the first tuple. If we order by maximal element, tuples have a natural ordering. So if we look at these tuples and sort by their maximum element, they're in a nice order. Here's what the two tuples look like initially. And here's the trillionth 2 tuple, the trillionth 3 tuple, trillionth for tuple, and so on. Here's a map of what the tuples look like in three space. And here's the Google 6 tuple here. Once you've got good code for canonicalization of ordering, and if it's fast enough, you can basically find the index for anything. And you can find a tuple with any index and permutation index and Larmor quotes work similarly. If you have a certain permutation, you can find out what its index is within the space of all permutations. The way the Lamer codes work is related to the factorial number system. So here's a puzzle by Sam Lloyd called the moving day puzzle. You've got a two by three grid and you've got five objects, and you're trying to swap two objects. So one way of presenting all these is to make a graph where 2:1 means there's 2. Item 2 is above item 1 on the right, and blue 3:5 means item 3 is above item 5 on the left. And that's the top edge here. So 35 on the left, 21 on the right, and missing item 4. This is a graph of all 60 positions you can get with the moving day graph. And with this graph, it's rather easy to solve the problem. And this is what I would call a canonical graph. It's a very symmetrical and nice way of presenting this particular set of data. One thing I see often in movies and TV shows is an evidence board. They'll have a. A board up somewhere and there's strings connecting all sorts of strange things around, and usually it makes no sense. So here's a sample board that makes no sense. But we can rearrange things in a more canonical form. We represent all the numbers in binary and we can notice quickly that the ones are never in the same place within two connected items. So, for example, this first one, there's no one in the last position, so we color it red, and all the other numbers just basically mesh. And none of these pairs of numbers have a one in the same place. And all the reds here indicate that the Last digit is 0. Each color represents where the shared 0 is between two values. So this looks much better, and it's much more visually apparent what's going on than this. But I've never seen them reorder an evidence board in any TV show or movie. I regret that while I was on Numbers, we didn't have an episode where we had an evidence board that fix. So what is the best presentation for things and within math, physics, literature, advertising, architecture, and pretty much anything else. That's kind of an unsolved question. But if you know something in mathematics and you have a better way of presenting something, it's something I would like to hear about. So that's what I had prepared and I'll be glad to answer any questions people have. Just post them if you have any. Thanks. I think we can end it there and there'll be a community post soon. Feel free to go there and post items at the community post if you have anything that you'd like to discuss. And many thanks.