Mathematical Games Hosted by Ed Pegg Jr. [Episode 12: Configurations]

Sa. Welcome, everyone. Welcome to another episode of Mathematical Games. And we're waiting for numbers to stabilize here. This is a part of a series I'm doing in an homage to Martin Gardner, who used to run the column Mathematical Games for Scientific American. And today I'm going to be talking about configurations. This. This sort of fits with many things that Martin Gardner did for Scientific American. In fact, quite a few of the items that are important in the study of configurations are things that he mentioned within his columns. And there's. If you like to learn more about Martin Gardner's 15 books, Mathematical Games, you can find them in Elibrary, and they're widely available and you can look up many of them to define some of his writings on mathematical games. So, looks like numbers are stabilized. And I run the website demonstrations wolfram.com and there's many different demonstrations dealing with demonstrations, and I'll be mentioning a few of them in the course of the talk. So here's. Here's a few of them pictured here. So what is a configuration? First, let's talk about some of the history. David Hilbert, famous mathematician of the last century, once said there was a time when the study of configurations was considered the most important branch of geometry. A more modern mathematician, Branko Grunbaum, in his book Configurations of Points and Lines, had a different opinion. The author would like to conjecture that this is the greatest exaggeration of the truth that can be found in any of Gilbert's writings. So maybe they're important, maybe they're not important. So what are the rules for configuration? Well, each point is incident to the same number of lines, and each line is incident to the same number of points. And that's pretty much it. That's what defines a configuration. Instead of a line, it might be curves, it might be planes, it might be something else. So long as you've got the. The same number of points on each object, and each object has the same number of points, it's a configuration. So here's an example. A triangle. The 32 configuration. Each point has two lines and each line has two points. Slightly more complicated. The complete quadrangle. Each point has three lines and each line has two points, sort of the reverse of that. The complete quadrilateral. Every point has two lines and every line has three points. So that's sort of a starter for configurations, but it gets more complicated from there. The Fano plane, for example, here, each point has three lines and each line has three points where the circle is sort of a sheet for a line. This is also a projective plane. And the rules for that is every point pair defines a line and every line pair defines a point that's also four points not on a line. So the Fano plane is the smallest projective plane. There's a lot of overlap between configurations and projective planes. And here's another representation for the Phantom plane. We've got seven arcs all going through seven points each. Each arc has three points, each point has three lines. And if we connect up all of the points are connected to lines and how the lines are connected to points, we get something called the Haywood graph, which is a 14 point graph which is cubic symmetric. And it's the skeleton of this Lozi polyhedron which we show here. So here's an example of this seven sided toroidal polyhedron. Each face has six edges and these seven faces each touch each other. It's a way of doing this. The seven colored torus in a polyhedron. Seven seven faces. And we can take a look at these arcs here. For example, the point 7 is connected to 2, 5, 7, 3, 4, 7 and 1, 6, 7 up in the phenoplane up here. This is a way of putting the Fano plane on the Cuz Lasi polyhedron by numbering these edges. And if it's a three digit triple, it's a line connected to for example 2, 5, 7 is connected to 7, 5 and 2 here. So this is the Swiss lossy polyhedron, which is a seven colored torus. And also the Haywood graph and the phenoplane all in one object. Now it's, it's somewhat tricky to line things up if you want to have say just three objects in a row. In fact, it's a whole, it leads to a whole bunch of unsolved questions. For example, Here is a 52 by 52 square where there's two squares colored in for each row and column. However, in any direction, if you say, drew a line through these two squares, you wouldn't hit the centers of any other squares here. For these two, if you drew a line and you can take any pair of squares anywhere in this, in this object and if you, if you, if you connect them up and draw a line through them, you will not hit any other squares. It's. There's no three in a line in any direction. Now whether this can be done with a larger square, for example, is there a solution for 54 by 54? That's been an unsolved question since the 80s. And this is, this is a problem that's well suited for computer exploration at this point. Just because it hasn't been looked at for 30 years. We've got a billion times more power than the last time this problem was looked at. So probably somebody could find something if they took a look. And a more recent question is, say you have a connected polycube and you want to have no. 3 in a line. What is the maximum size of the polycube? Well, this was solved last week. Here's the object in any direction, not just up, not just the normal directions or diagonals, but in any direction. The centers of three cubes are not in a line. And this is a 20, a unique 26 cube object discovered by Jur Gart. So there's a. At our community site I wrote this up. You can find out more about this object and there's code there for doing it. This talk, by the way, will also be posted at the community site. Let's see here. Now, one way of extending this is to look at objects where there's no. There's no more than three in a line, however, and you also want to avoid using two cubes between each other. It turns out 75 cubes is the maximum object you can make with that rule set. It's. This is also unique and this was also found last week. So there's many unsolved of questions involved with just putting two or three objects on a line. The next step up from the fan plane is the Mobius Cantor configuration, where you've got eight points each on three lines and eight lines each with three points. Here's a way of doing this with arc arcs and we can also draw it like this with a little bit of cheating for one line. And that leads to the Mobius Cantor graph, which looks like this. Let's see here. Trying to get to my button here. But. Okay, the compass configuration is a way of. Here's. Here's a solution for the. What's called the orchard problem, where we've got 10 lines, but we want to avoid this. This middle line here. Here's a way of redrawing this. So we have exactly nine lines and nine points, each line having three points and each point having three lines. But it's possible to sometimes get more lines. And that's what's called the orchard problem. I've got a column about the Orchard problem in a previous blog post. I forget what the name of my. We can take a look at that here. Cultivating new solutions for the Orchard Planning problem. So here's a set of points which can give this pompous configuration here. But you could Also, just choose any three points, and if you connect them up the diagonals and draw the line through the intersection points, they'll always be in a line. That's the Pompous theorem. And it's easy to get the sort of set of points for the Poppas configuration. If you connect everything up, you get the POS graph. Here's another way of doing nine lines and nine points. And the ratios of these turns out to be based on the golden ratio. This is a different topologically distinct configuration from the Poppas graph from the Pompous configuration. And we have this in graph data under the, under one of the configurations in graph data. And here's a third nine, three configuration that's also in graph data. The next configuration of importance is the Zargs configuration, where you've got two triangles in perspective, which means that if you connect up the vertices of the triangle, for example, this blue triangle and this yellow triangle, if you connect up the points, their lines intersect at a, at a new point, a seventh point. Also, if you've extended the edges of the, of the triangles, for example, this edge and this edge, they meet at this point. If you do that with all the edges, they connect up at three points which happen to be on a line. And that's what's called the desargues configuration. If you have this one condition where the triangles are in perspective, then it turns out the axis of perspectivity will also always exist. And also if you have an axis of perspectivity, then you have a center of perspectivity. And that's what's called the desargs configuration. Now, I can show you a different disarg configuration for different triangles. And that's this. Here, here's two different triangles that lead to a point of perspectivity and an axis of perspective. And now we'll do a completely different configuration. This one here. These are two different triangles. But turns out for once you have a dessert configuration. Any point at any line can be the either the axis or the center. And you'll always get a different set of two triangles. And it turns out there's always 10 ways. You can pick a axis and a point and two triangles. And they will always work in all different 10 ways. If you have a desargu configuration, Kemp in 1983, decided to draw a graph with, with how these lines were connected up. And we can take a look at how these connect up here. We'll move this one up here. Let's put these two points here and here and move this one around there and this one. What am I doing here? I want this one here and these two points here and here. You might recognize this graph. This is the. The Peterson graph. But it was discovered 12 years earlier by Kemp looking at the desarg configuration. So this would probably be called the Kempe graph instead of the Peterson graph. Peterson pointed out that Kempe's graph had some really nice properties. So Kempe was the one who made it famous. There's some other 103 configurations we can get to this configuration, for example, and here's the method for solving for it, which leads to this curious root object. I always like looking at the algebraics for these geometries that I'm coming up with, because usually the algebra is also interesting. It turns out there's a total of 10 configurations and nine of them are realized with pure points and lines. This is the desargues configuration. And here's other configurations. These are in the demonstration 103 configurations. And you can move the points around and to modify the configuration. As such as so. So one. One challenge is to make each configuration look good. So far as I know, nobody's done that yet. For the 113 configurations they're all known, but coming up with nice pictures for them hasn't been done yet. Just a picture exists rather than an optimal picture. And in these there's 10 lines each with 3 points and 10 points each with 3 lines. One step up is The TUT configuration. The 12:3 TUT configuration. You've got 12 points and 12 lines each. Each point with three lines, each line with three points. I'm using the function findextraordinary line with many of these. What is an extraordinary line? It's a line with three or more points. And that's basically it. So you can give a set of points to this function and it'll find all the lines with three or more points. I forget what it's called. A non extraordinary line, a regular line, maybe boring line. I'll have to look up the terminology. But a line with only two points on it is not extraordinary. And one unsolved question in mathematics is for a set of points, what is the fewest number of lines you can have that are not extraordinary? I believe that's known to up to 20 points. And then. And then the math starts getting really, really difficult. If you make up the object of how the lines and points are connected, which is what's called the Levy graph, you get what's called the Nauru graph, which is also the rolling octahedron graph. If you roll an octahedron around, there's 24 different configurations for how the on how the faces of the octahedron are connected. And here's all 24 of them. And this is all drawn on a three torus. The Nauru graph is also the same as the positions of the 2 by 2 by 2 Rubik's Cube. If you only make half turn moves with the Rubik's Cube, there's a total of 24 positions you can get and they are described by the Nauru graph. So this configuration is sort of connected to rolling an eight sided die around and also the Rubik's cube in. In a weird. Another step up is the Cremona Richmond configuration, which is based on this Pentagon. 15 lines, 15 points. And if you come up with the Levy graph, which lines are connected to points, which points are connected to lines, you get 30 objects, which makes these 30 points, which is called the ATUT8 cage. This is the smallest graph where every every vertex is connected to three others such that the minimal cycle within the graph is 8. There's no way of getting moving from a point and getting back to itself with fewer than eight moves. And that's, that's what makes makes this a cage graph. And this configuration is connected to how this graph operates. Basically any set of three lines does not make a triangle in this graph. And that's I believe this is the smallest configuration that has that property. We get up to weirder things. Here's a an object called the generalized hexagon. And there's 63 lines, 63 points, 3 points on each line, 3 lines on each point. And connecting those up gives this graph Object called the Tut 12 cage. The smallest cycle is the is 12. So once these special graphs were found within triangle free configurations, there's a bigger study for for more of these objects. There's a article there. This is a triangle free 17 configuration, an 18 configuration, several examples and 20 and 21 configurations. These are something I'll need to make pictures of. We can also seat in various ways. For example, do a three by three by three lattice and do it without diagonals. So basically do this without diagonals. You get 27 lines and 27 points. And with that you get this object called the gray graph. And the mathematician Gray basically took this object and said this graph has a lot of nice properties. And he got a graph named after him. Just by basically looking at the three by three by three lattice of points. We can move up to slightly more. Here's a the CokeCenter configuration, 28. 3 configuration, which makes this lovely object. And with that you get the Foster 56C graph. So I mentioned the orchard problem earlier. It turns out that you can make an infinite number of lines and an infinite number of points where each line has three points and each point has, well, has many lines. An infinite number of lines and the way to do that. And we can see a little bit of what's going on here. We've got positive 7, negative 7 and 0. You add those up, you get 0, negative 4, positive 4, 0, you get 0, 4, 6, 5, you add those up mod 15, I 15 mod 15 is 0 minus 7 plus 2 plus 5 is 0. To name any triplet of numbers from minus 7 to 7. If those three numbers add up to 0, for example, 1 plus 6 minus 1 plus 5 minus 6 is 0. If they add up to 0 and they for any set of three numbers, they make a line in this diagram. So this is a way of building up what's called an orchard. And we could continue on. If we looked at, say here, where's 1 and 7? If we drew a line through 1 and 7, that would basically come this way. And then we drew a line through two and six, those two points would meet over here. We could add the point minus eight over here and it would go through one. Seven minus eight would make a triplet adding to zero and two, six, eight minus eight would add to zero. I described this in in the blog, cultivating new solutions for the orchard problem. And this is a demonstration for moving the points. For some reason this doesn't want to work right now and I'm getting a wheel. Oops. Well, let's try that again. Oops. Let's see if we can get this to work this time though. We've got this big thing of code here. And now it doesn't want to work. There'll be a demonstration with that code sometime soon. And here's a whole bunch of different orchard solutions. 11 points on 16 lines. This is one of the sporadic solutions. 19 points with 52 lines is another sporadic solution. There's only four or five sporadic solutions known for the orchard problem. The rest can all be built up by adding these triplets up that sum to that sum to zero. If we move away from lines, we can try looking at circles. For example, the McWell configuration has eight circles or, sorry, six circles and eight points, each circle having four points and each point on three circles. When you do the Levy graph of that, you get what's called the RHOMBIC dodecahedral graph. So it's basically very similar to a rhombic dodecahedron. We can move up to what's called the Singer difference sets. So for example, here's the, the 1, 1, 2, 4 singer different set. And we can use that to make a final plane. But the difference between 1 and 2 is 1, between 2 and 4 is 2, between 1 and 4 is 3, 3. And going the other way you get 4. Because we're doing it in a cycle. Any difference between 1 and 6 is possible as differences with this different set and these, these become larger. For some reason, none of my demonstrations want to work today. And there's a different set demonstration that you can look at. We can move up to the 13 different set. For example, 1, 3, 9 and 13 is a different set. And when you cycle them around, we get these 13 parabolas and 13 points where each parabola goes through four points and each point as four parabolas. And that there's a four point parabola resource function you can take a look at. So here's a 18, 4 configuration where we look at lines at infinity, our points at infinity. These red points, red lines connect to a point way over here somewhere. That's considered a point at infinity. There's also a, a For the blue lines there's a point at infinity. And for the green lines there's a point at infinity. And when you connect up the 3 points at infinity and the 15 lines, 3, 15 points here you get 18 points and 18 lines with 4 points on each line and 4 lines through each point. The Levy graph for that looks like this. And at the in the community site you can see some of the other four configurations that I've drawn. These are some samples here of some larger four configurations. Here was a configuration that was found just about 30 years ago. Basically, you connect up a heptagon with these, with these points and you get 28 lines and 28 points with four of each on the other. And connecting those together makes the Grunbaum Rigby graph. If you, if you add another point at the circle, you get a solution to the orchard problem with 22 points, making 28 lines of four. And that problem wasn't solved until three years ago. Four years ago it was conjectured to have a solution, but it wasn't until this set of mathematicians in China looked at the problem and they did years of math on it. And then finally one of them pointed out, we can just add a point to this diagram and it solves the problem. And that was the solution. I looked at this problem myself, I did not spot this. And quite a few other mathematicians I've talked to that were familiar with both the 22 points, four in a line problem and also the Grumbaugh Rigby configuration. Even though they were aware of both, they did not put together adding a point at the center of this thing. So that's something I obviously should have spotted and many others should have as well, but for some reason eluded everybody, even though it's a very simple thing. This is the 35 Danzer configuration. We've got 35 points each on four circles and 35 circles each on four points. They make this object. You can also do a unit distance graph. All the edges in this graph have a length of exactly one connecting up in this special way. And there's another way you can make this, which is somewhat complicated. So here's six points on an ellipse. And Kepler studied points on an ellipse. Blaise Pascal. And he noticed, for example, if you took the points and you drew a hexagon with them and extended the diagonals and then connected up the points on the diagonals, you could always get a set of three points on a line. And no matter how you, how you connected the points, there's 60 ways of connecting the points for any of these, any of these hexagons that you drew, no matter, no matter how strange of hexagon you make, you would always be able to extend those lines and get three connecting points where the, where the opposite edges met in your special hexagon. They would always form a line. And Pascal called that the hexagram Mysticum. Later, Kaylee found something else she could do with it to get other lines. And then another geometer, Pluker found something else with it, Kirkman found something else, Steiner found something else, and Salmon found something else. And later Conway added to the mesh. But the hexagram of Mysticum is now considered to be 95 lines and 95 points. And if you take the 20 Steiner points and the 15 Salmon points, for example, this is those 35 points. Based on these six, we can, we can use, find extraordinary lines on those points. And we get 35 lines. So this is the dancer 35, 4 configuration, 35 lines, 30, 35 points, 4 points on each line, 4 lines on each point. I will probably give a talk on the hexagram Mysticum at some point, but it will take a while, so I don't want to try to do it in this talk. So that's a way of A difficult way of coming up with the configuration for the 126 rays configuration. We have 12 points each on 6 planes and 12 planes each with 6 points. And we can adjust this object. There's a demonstration for it. Oh, but it looks like all my demonstrations are going to fail today. Race configuration is. This is more information about it. In the, in this configuration we basically have a 4 by 4 grid. We take a point on the grid and we look at the other six points on the row and column and that gives you 16 point sets to go along with 16 points and you get that configuration. And that leads to this graph. If we go up to five configurations, the first five configuration shown here was found by Leigh Berman and who's at the University of Alaska. This was an unsolved problem until 12 years ago when Lei found this and then he extended that further by finding a six configurations configuration. So this is 96 points, 96 lines. Each line on with having six points and each line going through each, each line going through six points and each point having six lines. Whether there's a seven configuration is currently unsolved or whether it's even possible. It probably is, but no one has been able to find it yet. So if anybody would like to find it, you can, you can be the first to find a seven configuration. So one thing I want to do is was find a set of points which defined a line and lines which defined a point. And in areal or barycentric coordinates you're able to do that. For example, if we have a triangle here like this, let the outer blue, blue dots be the triangle. So what's the, what's the barycentric coordinate for this point here? But turns out if you calculate the areas, relative areas of the triangle we can get what the, what the coordinates are. But turns out this area has area 1/7, 2/7 and 4/7 in ratio to the full area of the graph. The, the area of this triangle is, is 14 and the, these, these three triangles have areas of two, four and eight. So the very sacred coordinates for this point is what is 2/7, 4/7, 1/7. Basically. So once you. So basically for any point you basically find the areas of the triangle in relation to the area of the full triangle. When you use these barycentric coordinates you can get these nice things like, like this configuration here. I've forgotten who the mathematician is that found it. He was also the one who found special properties of cubic curves. But one thing I want to do is find a self dual configuration, a barycentric line has the same sort of structure as a barycentric point. And if you multiple, if you do the dot product of a line in a point in barycentrics, you get zero if the point is on the line. For example, here, this line is 2, 1, 0. If we multiply that by negative 1, 2, 1, you get minus 2, 2 and 0. So this point is on this line and this line here, 4, 2, 1. If we multiply 4 by minus 1, 2 by 2 and 1 minus 1 by 0, this point here, you get 0 in total when you add them up. So, so this is a set of 24 points and 24 lines where each line is a point and each point is a line in the diagram. So this is a, a self dual barycentric configuration. And once I found this, this, this, this three configuration, I wondered if there is a self dual four configuration that might work. And after a computer search I found one. This is a, this is a set of points, barycentric points, and also a set of barycentric lines, also called Arial points and Ariel lines. So for example, this line here, 2, 1, 1, has this point on it minus 1, 2, 0. And if we multiply minus 1 2, 0, take the dot product with 2, 1, 1, the dot product equals 0. So this point is on this line and this, this point, this line here corresponds to this point here. Similarly, say this line here. I'm gonna guess that the point is this one, maybe this one, 1, 201-20. So this, this point corresponds to this line and so on. All 27 of these points and lines are within this object. So this is a self dual areal configuration. Whether there's a self dual five configuration is an unsolved problem. If there is one, I'd love to see it. Here's a larger four configuration though. A 514 self dual configuration with 51 lines and 51 points. Each line is a point, each point is a line. Slightly weirder is the smallest projective space. We have 15 points each on seven planes and 15 planes each with seven points. For example, one of the planes is 1-4523-6-7, which makes a Fano plane. So these seven points here, we can rotate them around and get the five five more plane or four more planes. There's a total of four, five planes with that configuration of points. We look at this set of points here, 2, 4, 6, 9, 11, 13, 15. That gives another symmetric configuration which can be rotated around to make to get five more planes. And this Here is also a symmetric set which can be rotated for five different orientations. So those are the 15 planes of the smallest projective space. It turns out that the 35 lines here all have bit X or sum 0. So 2 plus 8 plus 10. If you look at the binary bits, they all cancel out to make zero. One of the biggest and weirdest configurations is what's called the Klein configuration, which is in a abstract complex space. This again uses dot products. If you take, if you look at these as, as planes you get it's a set of 60 planes. But you can also look at it as a set of 60 points. And for each of these there's 15 others where their dot product equals zero. This is the largest known such strange object that also has the self dual property. And we could play games with it. It's a very hard game, but we lay out 12 cards at random. Can you find a plane that has three points on it? So you'd basically pick one card and you'd find three others where the dot product is equal to zero. And for that set, I just did this one here. One I one I minus one, this one here, this one here could be the plane and these three points or these four points are all on that plane. So this would be a, a nice hard game for die hard mathematicians. I, I've, I've tried this myself and it's, it, it sort of breaks my brain a lot harder than set. And we can also say look at the Klein Graph. Klein Graph 120 is based on this object that, and this is sort of the, the big configuration. The 6015 configuration is considered one of the largest currently. So some of the unsolved problems with this is what are some other self dual barycentric Graphs? Is there a 7 configuration with just lines? What other graphs can come out of configurations? For example, the rolling cube graph. Is there a nice configuration that pairs up with the rolling cube graph? Do some of these other graphs here have nice matching configurations? So those are some of the unsolved questions I know about. Many thanks for listening and I'll be glad to take any questions that people might have. And you can just type them in if you'd like. We can look over some of these. If anybody would like me to go back to one of the slides, they can. And also this will be posted to Community sometime soon if it hasn't been posted already. I can try to see if I can get these demonstrations to work. This one work. I'm not sure why the, the ones that followed were that didn't work. This is. This problem here of three in a row is also very good if anybody's looking for a problem to try to solve. Oh, if there's no questions, I think we can wrap it up there. Many thanks for attending, everyone.