Mathematical Games Hosted by Ed Pegg Jr. [Episode 17: Combinatorial Codes and Designs]

Sa. Hello, everyone. This is Ed Peg and I'm waiting. Oh, we just got a whole bunch of people come in. This is Ed Peg and I'll be talking about combinatorial codes and designs today. I'm just going to wait a few seconds here and. Yes, okay. I'm Ed Peg Jr. And welcome to another episode of Mathematical Games. Today we're going to be talking about combinatorial codes and designs. Mathematical Games was run by Martin Gardner on scientific American for 25 years. He put 15 books together of his columns, and his columns are highly influential for later mathematicians, including myself. One of the things he talked about was combinatorial designs, including the Fano plane. So I thought I'd give a talk about that particular topic. And there's various demonstrations@demstrations.wolcom.com that involve codes and designs. Here's a few with designs here. For example, the social golfer problem, which is a very tricky problem I'll be covering a bit later. So to get right into it, a Steiner system is one of the combinatorial designs. And there's usually three parts. There's a group size. For example, if we want all possible pairs, the group size would be 2. So, for example, 12 is a pair of size 2. There's also a block size. Each of these blocks has a size of three. And then there's a number of elements in the whole thing. Everything here is 1, 2, 3, 4, 5, 6 or 7. So the, the number of elements in this is 7. So the Fano plane is a 2, 3, 7, Steiner system, where 2 is the group size. We're looking at all possible pairs. Three is the block size, and the total number of elements is seven. And you can take any pair. For example, 12 is in the 1, 2, 3 block, 23 is in the 1, 2, three block. And 13 is also in the 1, 2, 3 Block. For any possible pair from 1 to 7, it's in one of these seven blocks. Another way of showing another final plane is over here with a Singer different set. You can take any two numbers, for example, 1 and 4, and somehow that's yellow line 1 and 4 connects here. So there's seven different colored arcs here. There's, there's six lines in a circle. And in this is lossy polyhedron, there's seven faces. Each of the seven faces has three numbers on it. And this particular one corresponds to. Well, I think these are three different phenoplanes here. Yes, three different panel planes. So that's an example of a Steiner system there. Here's a Slightly more complicated Steiner system based on the lo shoe magic square. So we have nine elements this time, and we're looking at any pair. And we can do that with two different squares. One is just the rows and columns of 1 through 9 in order. For example, 14 is in the 147 column, and the alternate square is the low shoe, the magic square, where all the rows, columns and diagonals add up to 15. And if you combine these, the rows and columns make a complete set of all possible the 12 blocks. There's a total of six rows and six columns, and together they cover all possible pairs of digits. And an equivalent way of showing it is with these 12 triangles. There's three red triangles, three blue triangles, three green triangles, and three yellow triangles. And these two are basically equivalent to each other. The the set of triangles in the lower diagram is equivalent to the two sets of squares in the top. And if you'd like to rebuild this as a puzzle someday, just write 1 through 9 in order. And remember 49 at the top. And from the 4 and 9, you can logically deduce what the other what the where the other digits are placed. A slightly more complicated one is what I call the 94 puzzle. You have the digits in order in the first square, and you start out with 9 and 4 in the second square. And you basically want to place all the remaining digits so that any pair of numbers shows up exactly once in a row, column or main diagonal of exactly one of the two grids. And it's possible to solve all of this with logic. How many pairs of numbers are there where. Now our Alphabet size is 16. So we can calculate there's 160 different pairs we need to cover. And if we look at one of the squares, 60 of the pairs are covered in this first square. For example, all the subsets of 1, 2, 3, 4, 1 2, 2, 3, 3 4, 1, 3, 2, 4 and 1 4, those six are covered in this first row. And similarly, all the other 60 combinations of pairs you can get from this first square, you can redo the second square so that none of those pairs are in the second square. So one thing to note is there's we need to fill out the first row, but there's only three different numbers we can choose from. The all the items here in red have pretty much been eliminated because they're already in a row or column with nine or four or main diagonal. So basically, we need to put six and 15 in these two squares in order to finish this first row. One other thing to notice is that 6 is on the diagonal here and 15 is not on the diagonal. Well, the balance, since 6 needs to be in. Since 6 is in three different. It's in a. It's in one row, one column and one main diagonal. But 15 is. Is only in two. It's on a row and a column. So, so 15 would need to be on a main diagonal over here and. And six would need to be off a main diagonal over here. So we can finish off the first row, 6. 15 is here. 6 is here. Excuse me. So, completing this sort of logic, we can continue filling out the whole square. So only memorize the 6 and 9 when I show you this. This is a nice puzzle. If you're ever stuck somewhere and you just got pencil and paper, you can try to solve this. If you remember just placing 9 and 4 here, here's the full solution. And we can. We can show these in a. In a star formation. The blue lines indicate the rows. For example, 1, 2, 3, 4. The three blue lines have all the various rows. Magenta has the columns in the first square, 1, 5, 9, 13. And orange has the diagonals 1, 6, 11, 16. The diagonals of both squares in. In orange and yellow has the rows in the second square. Here's 9, 4, 6, 15. And Green has the columns of the second square. For example, 7, 2, 9, 16 is this column here. So usually with these combinatorial designs, this is the. The Steiner 24, 16 design. Usually there's both a. A pattern of blocks you can find and a geometric version you can come up with. Not always, though. Sometimes these get too complicated for graphics. In fact, I'm not sure that this particular picture has been shown. It's just one I came up with. We can extend this further with a magic hexagon of sorts. Here we're only looking at diagonals going in one direction. And it's also staggered diagonals, for example, 2, 8, 14, 20, 21, as if this was on a. On a cylinder. These are ways of showing the same things on a hexagonal grid. And it's easier to see that it's one way on the hexagons, another way on the hexagons or columns and the hexagons. So it's a little bit easier to see in this sort of format rather than these squares. When you force one of these squares to be in order like this, the pairing square is. Happens to be a magic square. And it's sometimes easier to show these with a clipped hexagon such as this. Somewhere I've Got the, the graphic that corresponds to the first square. This one corresponds to this square here. So I need to redo this graphic to show the in order sequence and we can continue this. Six is not a prime number, so there isn't a natural Steiner system that goes along with it. But seven is a prime number. So there is a 2, 7, 49 Steiner system. And here we do all staggered diagonals as if the grid is on a tourist. So for example, 1, 9, 17, we can do this diagonal, but there's also the orange diagonal going the other way. And that includes the numbers over here. And if we pair it up, the opposing one, here's one shown here. I set this up as a, as a puzzle that you can try to solve. If you do a screenshot, you can, you can see if you can perhaps fill in the grid. But it's, it's not too hard of a puzzle once you see what sort of pattern is going on between the two squares. But every possible pair of numbers is, is in a shared row, column or diagonal in one of the two squares. So that sort of leads me to one of the most influential, influential pages in all of mathematics. The Goal, a 1949 paper on digital coding in radio signals. They often had problems with data corruption. And Golay came up with a method of correcting the codes. And he suggested two different options. One that became known as the binary Golay code and the other as the ternary Golay code. It turns out the ternary system had been discovered a few years earlier. In, in betting, football betting, especially in soccer. A game can be a win, loss or a tie. And when you had a bunch of games happening on say a weekend, you'd usually need to make bets for what the outcomes were going to be for each game, whether it be a win, loss or tie for each team. And one question was if you had say 16 games, is there a minimal set of entries you can send in so that you can have just one loss in one of the games? And this betting pool scheme was, was found for this particular system a few years earlier. And the preliminary Golay system, here's a way of generating them. You've got these six generators and if you add up all possible combinations of, of 0, 1 or 2 of these columns, you get all 729 codes of the ternary Gole code. So if you're betting on 12 games, this is 729 results you could send in and at least one of them will be correct within at least 11 of the 12 submissions will be correct in your betting pool. But that's a huge bet you need to make to possibly win one. So usually these betting codes don't break out, but mathematically that's an interesting way of showing them. So these are representations here for the columns here. Show what the codes look like. Excuse me. You can see they make some sort of interesting pattern here. And if you take a look at the positions of zeros and the code words, you get the 5, 6, 12, Steiner system. And they come in pairs. The 1, 2, 3, 5, 12 is balanced by 6, 7, 8, 9, 10, 11. Basically, if I took all the codes and they pair up like so to make a complete Steiner system. Now let me transition to something developed by John Conway. You've got 18 coins. And on each turn you can turn over one to five coins. But the leftmost coin, the coins are in a row. The leftmost coin must flip from heads to tails. You can basically flip any coins you want. But the, but the, but the coin that is heads furthest to the left, that's when you must flip. The last person to flip a coin wins. And this is a game called turning turtles. And with this game, Mobius, you've got 18 coins and you can flip one to five coins. So we can set up a greedy system here to find all the winning positions. So I'm just running this here. We're starting with all zeros are all tails is a winning position. And we can just greedily find all the positions where a win is forced. And it shouldn't take too long to find all the solution. And there we go. We've got the Mobius code here. And here's a picture of what it looks like. There are, let's see, how many codes are there here? There are 512 winning codes. So if you're given any, any particular position, usually you'll have a, a single move you can make that can go to a winning position so that no matter what your opponent does, they'll need to make a move that isn't a winning position for them. And then you can put it back into a winning position for yourself. And for this greedily generated code here is a generating system. If you add all combinations of these, you get all of these 512 codes. And we can do a tally for the weights in these systems. And we get a set of 102 code words for Steiner system. 4, 6, 18. There's 18 letters in this Alphabet. Each of the blocks is six. And any group of four is represented somewhere in here. Like for example ABCD is represented in this one. ABC, E is represented in this one. And for any four different letters, it's somewhere within one of these code words here, one of these 102 code words. So we can do the same thing and generate the binary Golay code. But instead of the setup we had last time, we have 24 coins. And each time you flip one to seven coins and their left must flip, must be heads to tails. John Conway calls this game mogul. I could run the greedy code here, but it would take about five minutes. And it turns out it, it produces this set of generators once it's done. And the length is 2 to the 12. And pretty much that's all you need to do it. It's, it's that easy. You just show all the ways of flipping the coins and you generate the binary Golay code. It's, it's, it's really that easy. And you. And this is the generator set. And we can take a look at. At what? At the weights that are produced. Let's see here. I'm not sure I trust this set of numbers here. Yes, it must have been a different set of code. And there are 759 octads in the final code. Let's see here. So that is the natural way of generating the binary Golay code. So you might think, is there another way? Well, it turns out there is. We can take a look at an icosahedral system. So we'll just do this. Here's an icosahedron over here. And this is a. And a adjacency matrix. If we take a look at the opposite of it, we get another icosahedron, but with the diagonals added. And also self loops where the, where the edges connect to themselves. But I left those out for this picture because those loops make it look weird. So here's the identity matrix of the reverse icosahedron. Where you take the edges of an icosahedron and you remove those and you fill in the edges that weren't in the original and you get this sort of structure. With that combined with a identity matrix. This is a generator for the binary Golay code. And, and we can, we can take, take these together, Join them up. There's the generator for it, we can generate the full code. And we, when we take a look at the weight, we get 759 octads. It's, it's that easy. You just use the inverse of the octahedron and you get a generator for the binary Goli code. So is there another way? Well, it turns Out. Yes. If you take the digits of 22 and you square them and you look at those mod 23, you get this set of mod 23 non residues. And with those you can generate the binary Golay code. It's that easy. So we have the non residues here and we use those to make this, this cyclic generator. And we can add them all up and we get 759 octaves like before. So that's a natural way of generating the binary Golay curve. But you can also take a look at the, the factors of 8 to the 23 in binary. And this is one of the, one of the polynomials that drops out. And we can use that to make a generator for the binary Goli code. It's, it's that easy. Here's the generator here. We add all of those up and when we take a look at their distribution, there's 759 octaves. So it turns out there's a lot of different ways for generating the binary Golay code. It's one of the amazing objects in mathematics that plays very largely in both graph theory, group theory, coding theory and many other areas of mathematics. And it all dates back to that one page paper by Golay in 1949. So you might have heard that about the Voyager 1 system and we lost the signal with it last year. Well, just last week they managed to fix the Voyager 1 system and it's very far away. It's a 1977 era computer, 26 billion kilometers away or 16 billion miles. How do you fix a bad processor in an old computer that far away, considering how corrupted your signal is going to be by the time it gets there? Well, it, it turns out that the, the binary Golay code is very good for this purpose. And the Voyager mission mission happens to use the Golay code, for example. It, it's, it could be using this system. I'm, I'm not exactly sure which of the Golay code systems the Voyager system uses, but it's, it's one of them. And if a signal is sent to the spacecraft, for example, here, we can have an, a random code and it can, oops, let's try that again. And it can find the nearest code and then find out where the errors are. For for example, if this was the random code, it's these three bits that were wrong and the satellite can correct it. And we can try this out with the Golay code demonstration. If we have a particular code that's been sent in, we can compare it to the full code and then pull out where the difference probably is with the 23 bit system, it's a perfect code. Up to three errors will always be corrected with a 24 bit. Sometimes if there's four errors. If there's four errors, there's one. If there's four errors, There can be six possibilities for what the actual code is. So for something like that, you'd want to do a resend. Usually though, they use the 23 bit system because it's perfect. And that with that, they managed to fix. Voyager is now working again. They. They sent a set of code to bypass the faulty processor. So Voyager is sending messages again. The full code can make a 5, 8, 24 signer system, which is sort of unique in all of coding theory. There's nothing else quite like it. And for any set of five letters from A to X, one of these 759 octaves has it. For example, A, B, C, E is in this first one. ABCDG is in this one. And you can check for any set of five letters. It's in one of these codes somewhere. And this full talk will be on Community sometime soon. We can puncture that code by taking out the. Just. Just focusing on the ones that had the letter X. And what remains is a set of 253 heptads which has any set of four characters somewhere in it. For example, ABCD, ABCD, ABCD, A.B.C, e, ABCF is in this one, ABC, G is in this one, H, this one, and I, ABC, J and this one, ABC, K and so on. Any set of four letters ends in one of these 253 heptads. And this is a unique signer system, the 4, 7, 23 Steiner system. 23 letters in the Alphabet, all in sets of seven and the all in block sizes of seven. And any four items from the Alphabet are in here somewhere. We can puncture this again by say, taking all the ones from the previous group that had a W, and we get 77 characters left. Each has a length of six now, and that set of values makes an object called the 77 graph or the M22 graph. M22 is one of the sporadic special groups. And I'll be covering those in a little bit. So there's 77 of these blocks shown here. And here's what the graph looks like. These vertices are connected if. If no letters are shared. For example, abc, ILU and D, H, J, K, N, O don't share any letters. I don't think so. They would be connected in this graph. So this is a way of this series has been a way of puncturing a code to generate a smaller code. And any triple is in a block of size 6. And using one of one of the a triple of the 22 characters in this set. So that's showing the method of puncturing a code. Is it possible to go in the opposite direction? For example, in this column here, we've got the Fano plane. If we introduce a new concept called the room square, we can solve a larger problem. And this is one solved by Kayleigh the Kirkman school girl problem, which I covered in last month's talk. You basically have 15 schoolgirls, and they need to visit a school in triples over the course of a week. And no two girls can be in the same triple more than once during the week. And the question is whether it's possible to get a set of triples that satisfies that. So what is a room square? So in white, we have a room square. All possible pairs from 1 to 8 are given. For example, here's 1 2, here's 1, 3, 1 4, 1 5. Basically, the complete set of 18 dominoes without triples is in this square somewhere, 18 over here. Also, in each row and column, the numbers 1 to 8. Up here, for example, this has 1, 2, 3, 4, 5, 6, 7, and 8. And this one also has 1, 2, 3,4, 5, 6, 7, 8. So if you take a room square and a Fano plane, we can combine them so that ABC is one triple, D35, E17, F28, and G46 is another is it is another set of five triples combined together. So basically, the school girls would be the letters A to G and the numbers 1 to 8. And if you look at each row here, ADE would be 1 triple, B 26, C 48, F 15, G 37. Combined like that, we get 35 triples. And each one of these would be one day of the week in a method that solves Kirkman's problem. And to do that, all Caylee needed to do was combine a Fano plane and a room square, and that solved Kirkman's problem. However, the Fano plane wasn't developed until 21. Well, Gino Fano was born in 1871. It wasn't until much later that it got called the Fano plane and the Room square. Gerald Room was born in 1902. The concept of room square was introduced much later, but Cayley used both of them in 1850. A lot of things in mathematics are misnamed after people that didn't actually discover the items. Okay, I'm going to get some water here. So here's something you might want to take a screenshot of. This is a room Sudoko room square. So place all 45 non doubles from a complete set of double nine dominoes into the grid. Every, every row, column and square has the digits 0 to 9. So there's going to be some missing. This square here will only have five dominoes in it. Well, all of these will only have five dominoes. All 45 dominoes makes a orthogonally connected ring around the central square. So you'll be able to connect all the dominoes together to make a ring around this square. The given dominoes in each each orthogonally touch exactly one or three other dominoes. So for example, this domino here you can probably guess only only connects to the 23 here. If it connected to three others, you'd have a domino here and here. But then there would be no way of putting a domino over here because this uses up all five over here. There wouldn't be anything here. So you wouldn't be able to make a orthogonally connected ring if these three were empty. So you can deduce that 79 only touches one. All the givens only touch one or three dominoes. All the hidden dominoes orthogonally touch exactly two dominoes. And this is a solvable Sudoku like problem here using the concept of room squares. And the solution you'll be able to find in the community post that will be appearing sometime shortly. So, the Kirkman schoolgirl problem. Here's one way of solving it. With bit xor this is a set of triples. And you can arrange the triples like so for one week you'd use the site, or one day you'd use the cyan and and so on. Let's see here. This is, this is also the smallest projective plane in this 2315 Steiner system. One other way of generating interesting Steiner systems is what's called the SP Singer different sets. So for example, I started off with this set 1, 2, 4 as the differences. If you look at all possible distances between these points cyclically, you get 1, 2, 3, 4, 5 and 6 as the differences. So it's a complete set of all possible differences with only three points. And further up here's a set of four points on a disk of size 13 that has all the possible differences 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 and 12 on this cyclic system of size 13. So this first one, this one here, generates the final plane. The 2, 37 Steiner system. This next one generates the 2, 4, 13 Steiner system. And one more generates the 2521 Steiner system. And these are Singer difference sets. This is also called a Ganymede circle or an M switch. So we can use these points to generate a set of 13 parabolas so that every point is on four parabolas. And every parabola has four points so that for any possible pair of points, for example, 1, 2 is uniquely on this parabola, 13 is uniquely on this parabola. 14 is on this parabola, 1, 5. It has to be one of these. Not orange, not green, not blue. Oh, it's on this one. 15 is on this parabola. Every possible pair of digits is on one of these 13 parabolas. So this is a 2, 4, 13 system. Since there's 13 items and everything is in blocks of four and it's covering pairs, Another thing we can do is to look at Venn diagrams. So we put data in the center parts of the, of the Venn diagram, and then we add three more bits so that each circle has a parity, an even parity. And here's how it looks. Here we've got a set of data. We pull out three sets, and then we add parity bits so that the total item has zero parity. And then when we combine everything together, we get the hamming or 74 code, and it is able to, to fix an error if it occurs anywhere in the code. We can extend that to larger Venn diagrams to make bigger Hamming codes. And I thought I was going to add another Venn diagram, but I forgot to. There's also larger designs. For example, here's the, Here's a way of doing on 64. If we take any, any pair of numbers, it will share a. It'll be on a column or row or diagonal in one of the squares. So, for example, here it's. Here we have 21 and 28. It's in this square for 4,128. It's in this square. For 41 and 54, it's in this square. There's often other ways of combining these. And this particular set of, of blocks happens to be a unique system. If you've ever played the game of set, you, you. There's basically shapes, numbers, colors, and I forget what the other part of set is, but it's a set of 81 cards. It's possible so that if you get 40 decks, you can create all possible triples. And one of the triples will be in one of the the 40 sets you've laid out. And this is the, the 40 sets and the set of sets in set. So it's basically ternary representations, which is explained here. This is the set of sets and sets demo. And what we get out is the 812731 resolvable design. And it's resolvable because we've divided each, each solution into one of 40 parts. So with the 40 decks, we are able to lay out all the simul all the solutions simultaneously. And there's 1080 possible sets in the game of set. With the 40 decks, we show 27 sets at a time. One more complicated problem is what's known as the social golfers problem. So the Kirkman Schools problem can be considered as 15 golfers playing in triples for seven days, so that every pair of golfers plays with each other once. Now, if you have different group sizes and different numbers of golfers, it's a very complicated problem. If you have four golfers in eight groups, what's the maximum number of days you can play so that no two golfers plays together? So it turns out for the set with 32 golfers, you can play a maximum of 10 days. Now, not all of these are perfect combinatorial designs. Many of these, there's at least some pairs of golfers who wind up not playing with each other. The the math has to work out for the solution to be perfect. And even if a solution, even if the possibility of a perfect solution exists, that might not be a combinatorial problem that's been solved. In fact, there's many combinatorial problems of this sort that haven't been solved. And often that doesn't look good. Often with these, the solution is given in some sort of strange way you'll usually be given. If you follow this seven pages of mathematical advice, you'll get this solution if you follow what's given in these three other papers. Boiling these down to a solid set of solutions took quite a while. One thing that's related to all these, I've mentioned sporadic groups a few times. The Golay systems cover all five of these. First one here, the Matthew groups, it turns out that there's interesting generators based on just two matrices which you multiply together. And if you multiply the matrices together in all possible ways, you'll eventually get the full group. And these are the various group orders. I found it interesting that all of these sporadic groups could be generated with two matrices. And many of them deal with eventually unusual Steiner systems. So here's a A big triangle. And here, here we have the binary Golay code. It's a perfect code. And the maximal distance between different codes is seven. There's three different colors here. The perfect codes are in red and the near optimal ones are in, in cyan. So here's a, a BCH code. I believe those are, There's a few slides back. The one with the Venn diagram, the hamming codes. Those are hamming codes. Here. This is the Golay code. But there's also a whole bunch of other codes. For example, the padded greedy code here. Many of these are greedy codes. Padded optimal. This triangle was made by collecting data from codetables.de There's a cyclic code here. These different codes have all sorts of different properties and formats. And as you, as you increase the number of code bits versus the, the number of correction bits, you get all sorts of interesting patterns that develop for optimizing the, optimizing the code for that what, for what's particularly been given to it. And many of these, especially for larger systems, it's unsolved what the best code is. You can take a look at a whole bunch of different Steiner systems at our Wolfram data repository. Steiner systems. And here's some of what's in that set. So when I was putting this together last night, something came up in my feed of a new code published yesterday in Nature Physics, which is a very prestigious journal, one of the most prestigious, and they talk about quantum spherical codes and a little bit later down in the article it talks about a Mathematica notebook for the code used in the paper and it mentions the error correction zoo. So I took a look at that last night and this is a whole bunch of different codes that are available to play around with. So I found this very interesting. That week after the Voyager system got fixed with error correction codes based on the Golay codes, the most prestigious journal published more about error correction codes. Yesterday I mentioned this nice site on error correction codes. So this is relevant. There's still a lot of research in this area as in yesterday and I, I find this a very interesting topic just because so much geometric stuff falls out of it as shown in some of the geometric designs I showed earlier. So that's what I had. I'll be glad to take any questions if anybody has any. And yes, Kaylee knew about the Fano plane. That was a well known structure, but it was a genofano that kind of got credit for it. This particular problem is, is the one I'm most interested in for golfers in groups of five. Pretty much almost nothing is known for optimal solutions. I'd love to see groups of five, groups of six for, say, up to, say, 20 groups, but I don't think that will be solved anytime in my lifetime. But it would be great to see a nice set of solutions based on that, just because it's such a hard problem. And I get asked about this all the time because I've posted this. Whenever somebody has a golfing problem, I'm one of the first people that pops up in the Google search, so I'm often asked to solve what is an almost unsolvable problem. So it'd be nice if there was more data collected for these problems just so I could have something to point to. And that's what I had. If nobody else has any questions, we can wrap things up there. All right. Many thanks.