Mathematical Games Hosted by Ed Pegg Jr. [Episode 6: Sparse Rulers, Golomb Rulers & Difference Sets]

Sa. Hello, everyone are gonna wait for the crowd to settle here. I'm Ed Pegg Jr. And I'll be repeating myself over the next minute, most likely. All right. Okay. We've got some people visiting us. Okay. Welcome to the sixth episode of Mathematical Games. Today I'll be talking about sparse rulers, Gollum rulers, different sets, and other related items. And this is part of a series I'm doing in homage to Martin Gardner, who ran mathematical games for Scientific American. I'm trying to do some talks in sort of the style of what he did, where we're pushing the boundaries of what's known in recreational mathematics. And in the course of making this talk, I managed to push a few boundaries. So let's review what we're going to be talking about. What is a sparse ruler? So here's an example. It's a ruler with six marks and it can measure all of the distances from 1 to 12. For example, from 0 to 1. That measures the distance from 1 0, 2 measures a distance of 2, 6 to 9 measures a distance of 3. And this is the minimal number of marks that can, that can measure everything from 1 to 12. You can't do it with fewer marks. And one of the questions from, from the 1930s was what is the minimal number of marks? A general length. And it turns out that it's this formula. The XSN that are the number of marks is equal to this with some excess and E to the E sub n is always 0 or 1 for all n. And this, this funny bracketing here, that means the round function. So here are a few sparse rulers here. And here's a larger ruler. Here's a ruler of length 214. Here's the marks in it. And this is my favorite of the sparse rulers. I call this my 1 meter ruler because it has a gap in it of 100 centimeters. And I've got some, some copies of this actual word basically just, just marked these places on a, on a normal fiberglass measuring tape and you get this, this nice sequence. And it's pretty easy to pick out the sets of marks you need to measure a given distance just because everything is so regular. And we can check that this works if we set the number of marks here and we tally all the differences, we get that all the differences 1 to 214 are covered somewhere within these sets of marks. So that's a sparse ruler. All differences must be covered, but they can be repeated. You can see some. Like for 102, there's, there's two different ways of measuring 102, there's seven ways of measuring measuring one and there's various ways of measuring three. A golem ruler. Differences can be missed, but nothing can be repeated. So if we do the same thing with this golem ruler of length 216, you'll see that everything here ends with a one. When we, when we tally all the possible differences, there's only one representation for each distance. And it turns out that the length of 91 cannot be measured by this golem ruler. Neither can 93 or any of these other measurements. With the golem ruler you miss distances, but nothing's repeated. With the sparse ruler you cover all differences, but some are repeated. If you go modular, you get what's something called a different set. For example, here is a different set, there's only three points in it. MOD7,013 is an example of a MOD7 different set. And so from 0 to 1 you have this one arc from 1 to 3, it's a difference of 2, but it's modular. So you could go either direction for your differences. And there are differences, different sets known of various size. And in this demonstration on different sets, you basically get. I give the arcs for every single possible set of modular differences. With a different set, for example, this one, this is a different set. Springer found James Springer in 1938. We can look at all the different possible differences, modulo 183, and we get that everything is represented exactly once. And we can check that if we, if we do this bit of math and look at the comparison, it's exactly equal to range 182. So it's all the differences one to 182. So those are the three major types here. If you use modularity, you can cover all distances uniquely. With a golem ruler you can, you can avoid repeating anything, but you'll wind up missing things. And with a different set you cover everything, but things can be repeated. So here's a bit of history on the problem. First, rulers were looked at under a different name originally. And Paul Erdos managed to prove that a limit exists for the number of marks based on the square root of the length. And I think we can show this here. Let's see here. Here's erdos problem number 170, the sparse ruler problem. This is@erdos problems.com. In 1956, John Leach managed to come up with bounds. John Leach is the same mathematician who did the leech lattice in 63. Brian Wickman came up with a paper which will be discussed later, and he's now credited for having solved this problem. He was able to find this upper bound of square root of three almost in his 1963 paper. I managed to make a trivial addition to it so that he wound up getting credit. Let's see. In 1967 Robinson and Bernstein predicted the best 24 mark Golem ruler. And then they in 1984 predictions were made for Golem rulers under 100 marks. And we'll be getting to that. In 2014. Distributed.net did a giant computer search and managed to prove that the 24 mark golem ruler was correct using tens of thousands of hours of computer time. And also the same year Archd Robinson verified sparse rulers up to 25 marks using another big system he worked for Intel. He was given access to about 600 intel processors. And with those he was able to compute sparse rulers up to length 213. In 2016 Thomas Rokiki and Dogon made predictions for the best Golem rulers with under 40,000 marks. So that's a list at, @Cube20.net I think that's it. And I managed to come up with the sparse ruler formula in 2020 which basically proved this. And just last year distributed.net verified the 28 mark Golem ruler. So I'll be getting to all of these. Let's get to a few more sparse rulers. So here's a sample case disperse ruler of length 13. And if there is only 5 marks you could only do 10 distances. So that's not enough. But with 6 marks you can get 15 differences. So that might be enough. And we can check that this set with six marks actually does cover everything. Here's difference one, difference two, three, four, all the way up to difference 13. And we can check this in various different ways. So for length 13 you need 6 marks and that's easily provable. For length 50 it's, it's a, it's non trivial. To prove that 12 marks is minimal, you pretty much need to do a brute force search, which is what I've already forgotten his name, which is what Archd Robinson did in nineteen twenty fourteen. So here's a visualization of this ruler showing how each difference from from 1 to 50 is measured with this set of marks. We could also show that ruler as this set of marks here. The differences between the marks is this pattern here. One, two, three, a bunch of sevens, two fours and a one. Well, we could represent that in what's called the split form. 1, 2 and 3 each occur once, 7 occurs 5 times, 4 occurs twice and 1 occurs once. This sort of representation is very useful first for sparse rulers, because it's really pervasive how often these numbers repeat. So I could show you a sparse ruler of length a Google 10 to the 100, and it's basically in this form. It fits nicely within about three lines. If. If we weren't allowed to repeat the numbers, it would of course, fill a large book for the case for a Google. So for. Where are we? Okay, Brian Wickman was the one who kind of cracked the problem. And this is the recipe he used. And this is for that split form I was just showing. So, for example, this recipe gives the ruler we were just looking at. If we plug in 1 and 5, we get that split form. You were just seeing 1, 1, 2 and 3 once, 7, 5 times, 4 twice, and 1 once. A related recipe, what I call W2, is here. It's very similar to Wickman recipe number one up here. I believe this. Where is it? Right here. It's one plus R. Here is just R. And that one plus R moves over here. So basically, we're moving one mark for. For the second Wickman recipe. And it turns out that causes the length of the ruler to be one less. So we can set up a whole bunch of these Wickman recipes and see what they. So here's a rundown again. We've got the ruler form, which is just the marks, the differences form, which is a list of the differences between the values and the split form, where the number of repeats for each number is given. And if. If a number is repeated more than once and sections, you just basically start the count over again. And here's various pieces of code to convert back and forth between these forms. For Ruler 50, we can basically do this. That gives the split form and it returns the differences form. And if we do the differences on that, we get back and forth. And this is basically just showing the various ways of getting back and forth. And here's a table showing the original recipe. Here's the recipe down here. If we plug r equals 1 and s equals 5 into these, we get these values. So basically, this isn't actual exponentiation. This is basically. We're basically. Seven is repeating five times. One occurs once, two occurs two occurs once, three occurs once, seven occurs five times, four occurs twice, one occurs one time. So we can make larger rule rulers making this recipe. So here's the one I've been showing. Length 50. And if you plug in the various values here for R and S, you get these rulers here, for example, for 21319 occurs six times in a row, then 10 five times in a row. Here is the last known ruler which is but both optimal but not a Wickman ruler. It has length 58 and it's predicted that this is the last non wickman optimal ruler. It has 13 marks and there it is. It's a somewhat unusual construction and I believe that this is the last one. I'm not sure of that though, and I have no, no way of proving it. We do know that this is the last one up until length 213 because there's been a brute force search up to that. So in 2018 I got involved in the problem and basically I just wanted to use the data that Robinson collected because I read about it. So I wrote to him and he said, oops, I accidentally lost all the data. So basically there was nothing left of his big run except for a few sequences in the online encyclopedia Integer Sequences. So basically we knew what a few answers were, but we didn't actually know what the sparse rulers were and the number of marks. This, this is what it looks like up to 214. It starts to wiggle at 130 and no one knew what was going on here. With this sequence I was able to use Wickman rulers to reverse engineer this as a formula. And it seemed like we can boil down all the solutions that Robinson found into a series of zeros and ones using this formula. And there's the, there's the series here. You've got 50 zeros in a row and then a one and then more zeros and a one. And it was just a puzzling sequence. And when I extended on on with more best known results, I tried making various rectangles with it, but it didn't seem to make any sense until I decided to look at the best known rulers at each case and set those as a floor value. And that's when we got this pattern. Everything started nicely clumping together. Here are the unusual cases where the wriggles were and there are various odd values at the top. These, these values up here at the top. We probably could have modified this formula to make these go to zero instead. But this was a really simple formula and these were always just going to be one. So I figured it's best just to keep the formula simple. And this looked like a really good way of seeing the data. I showed this to N.J. sloan and he called this pattern Dark Mills on a cloudy day. When he saw this is we extended this to 10,000 and this is the weird pattern that formed and these this area down Here is what Dr. Sloan called the dark mills. And up here there's various places where it was also one, the excess here. Excess is a number of marks minus three times the length plus nine four square root and rounded. Unusual little formula. And we got this. That's long series of zeros and ones. And this is what happened when we plotted out those zeros and ones. And pretty much from the moment this image was produced, the problem has been sort of considered understood because everybody that, that looks at this for more than a few minutes basically says, yeah, there's a pattern there of some sort. There's probably lots of lots wrong in this pattern. But it's. It's pretty accepted that something like this pattern is true. So we can take a look at why this problem is really difficult by looking at unique cases. For example, length 88 is only findable with a computer search. Here's the solution for 88 and it's unique. Ruler 110 is also unique. And that's. That's what it looks like. Let's see, here's some more of the unique ones. I'm showing them in the split form. The. These rules at the bottom here past 178. These probably aren't actually unique. I just don't have a computer sufficiently powerful enough to find them. And it's possible that no computer or system in the world is powerful enough to solve say 334. That might be doable. And if we went with all the computers in the world, we might be able to do this case. I'm not sure though. Actually distributed net managed to solve length 585 for. For. For golem rulers in four years on thousands of computers. So, So I might be wrong, but it's. So this one probably is able to be looked at, but it would be a whole lot of much of work for, for solving a small problem. So there's also some very difficult solutions to find. This was the, this was the really hard one here for me. I wanted to show that the access was always zero or one for all sparse rulers. But 1792 was a particularly difficult one to solve. But I finally managed to solve it on an old system that I had running for months and it finally spit out an answer. There's various sequences or OEIs for this. We can take a look at one of them here. Here's. Here's the one that has lots of data on it. And if you go to this bottom link, these are basically example rulers for all lengths up to 10,000. And the the number of marks is given, the length is given, and the excess is given plus a representation of the split form. So once I had a whole bunch of different Wickman recipes, I managed to find about 800 different ones. I started making different recipes. And this, this is the original recipe. Here we can basically vary rnf. And if the red dot is in the white here you basically get a ruler that has an excess of 0. If it's in black, it has an excess of 1. So here are the I, this is a demonstration Wickman like rulers. It's on the demonstration project. You can basically play with these different recipes. So for example, here's recipe number nine. It uses this set of values and you can. This is the what the ruler looks like for those RNs. And here, over here is the split form of that ruler. And we can keep on going here. All these different recipes are, are quite similar to each other, but they have obvious differences. And I still don't know how to find more of these recipes. What I'd like to do is find three variable recipes. Rst1.1 recipe I know of is adding a T value at the end of one of these items. Here I used Whitman recipe number one and just added a a T value at the end, which was the size of a size less than R. And with that I could basically just add one mark but cover a whole bunch of extra differences for a ruler with only an excess of one. And that was enough to prove the square root of three bound for the Erdos problem. Since I basically just added one mark to Wickman's problem, that was considered a trivial addition. So Wickman got credit for solving the Erdos problem. Here are a whole bunch of different sparse rulers. We can, this is another demonstration. We can basically. Oops. Not sure why that happened. Oh, let's skip that one. But this is a demonstration that works better outside of a slideshow. And hopefully I'm not going to crash here. It wants to format things. Okay, anytime. I might need to restart my talk here. All right, let's see. I'm trying to get my notebook back here, and I'm going to open up in a different version of Mathematica. All right, Just one moment. All right. Okay. Sorry about that. Okay. Oops. So for some reason that one didn't want to cooperate. So with, with the Wickman recipe, we can just add a single mark and that's what I'm doing in this demonstration called Wickman columns. And we can basically pick the number of marks, say 100, 800 marks. So that gives rulers of length 213,000 plus X. So for X and any of these values, we get items that that work. The red indicates that a sparse ruler cannot be generated, and blue indicates ruler with excess 0. Green indicates a ruler with excess 1, and I forget where. But after a certain length, for example, here's some ones that don't work for 433 marks, these values cannot be covered just by adding an extra mark. But for anything over about 800, everything always worked. So basically for rulers under a length of a million, there's some, there's some problems that need to be solved. But for anything greater than a million, just using the Wickman recipe and adding a single mark solves everything. So basically it turns out for this problem it's a rare case. The big values were easy to solve. It was the small problem, small values that caused problems. So that led to my proof of sparse rulers, which is basically big values are easy. Here's solutions for all the small values. And done. And I gave that proof in much gorier detail in a blog post a few years back, back in 1920, back in 2020, right before the pandemic hit. Just look in our blog and you can see the full proof. So one thing I didn't cover in the proof is whether the excess value can be minus 1. We haven't been able to prove that's impossible, but it seems highly unlikely. And if it, if such a ruler exists, it has a length of greater than 213. Each of these solutions, when they're really good, it causes a big splash. Basically for every excess zero solution, I was able to do some tweaks on it to get thousands of other solutions. And if a super ruler with this occurred, basically it would leave a big mark in the solution space. And I did a large search in the solution space founding finding millions of these first rulers. And there was no evidence that anything was causing a splash of that magnitude. So here's a few examples. So here's length 58 is the last known non Wichman optimal ruler. Here's the last ruler with just three differences, 1, 9 and 8. Here's the last one where the greatest difference between values is 12 at 181. Here's the last one with just four differences. Everything is either 1, 62, 4 or 5. Here's the last one where only five differences are used in the split form and basically half the ruler is right there. Here's the last one without consecutive repeats. And here's the last known with a large gap greater than 1/3 the length of. And this 582 is what's called a cloud value. So let's switch to column rulers. In 1938, James Singer developed a method for finding different sets and Golem rulers using generalized Fibonacci sequences. So here's an example of one, say no. So here's a generalized Fibonacci sequence with 1301 this linear occurrence. Now if we take the mod values, we get various values of 0 to 4 and we can partition this 01. And if we sort them, we get, we get basically all the, all the pairs 000 or 01 to the 44 here except, except for the first 1 00. If we, if we don't sort these, we get this 011114 and so on. So where does each of these coordinates occur in a zero in a five by five grid? Well, we can find that. And with MapIndex we basically get this sequence which we can put into a grid. 00 is skipped. And for any pair here, that, that is maximally Fibonacci, such as these, we can get this grid with ha, which has rows and columns. Well, it turns out that each of these rolls and columns is a Golem ruler with no repeats. And I show them up here with, with the marks. And that is something we can do for any prime. For example, here's Prime 23 makes this big grid and every single one of these rows and columns is a Golem ruler. This is what James Springer found back in 1938. He used this method to generate the sets and he was mostly looking for what's called different sets because these work is in a modular way. And this is, this is how he developed the Springer difference sets. So basically, no, no, no differences repeat due to a peculiarity in and how generalized Fibonacci number works and on for prime values. This is basically either an affine plane or projective plane based on how you approach the problem. And thomas rukiki@cube20.org use this method to extend it out to a lot of marks. I think he went up to half a million. And one thing he found was that prime gaps can mess up how the projective geometry and affine geometry works. And it turns out that for this particular number of marks, 42,116 marks, that the Springer method completely fails. It's unknown how to make a Golem ruler with that many marks. However, since we're only up to 29 marks for what's been verified true, we probably are never going to get to solving this particular problem. But the, the toolbox that we use this, the Springer method that's been used since, since the 30s, won't be applicable for that particular number of marks, but which I found quite interesting. And this is another demonstration. Here's the name of it. Up, up here again. Golem rulers and Fibonacci sequences. You just basically make the generalized Fibonacci sequence. You pick your prime and you get a whole bunch of possible golem rulers. Now they may not be minimal, but they won't repeat any, any differences. So let's take a look at all the cases involving 11. So for 11, these are the pairs in a linear recurrence that are maximal, that'll hit all 120 values. So if we, if we pick one of these, this is the, the grid that gets generated. And let's see the last one. This is what 7, 9 generates. So each one of these generates a whole bunch of rows and columns. And we can look at all the rows and columns generated for each one and then also take a look at their, since they're modular, do all the various rotations. And it turns out if you look at that, look at all those, the shortest golem ruler that comes out of that is this one here has length 34. Well, it turns out that the best golem rulers found with computer search have a length 32. So this is one case where the Springer method did not work. There was a computer search that found it. However, there's only eight known occurrences where the Springer method did not work. In all of these searches, nothing in the past 20 years has been something new. Here. Here's all the known golem rulers that have been proven. There's only 37 of them. Here's the last one that was found last November. We can, we can sort these in various ways. This is going to be a new demonstration sometime soon. It'll be called Golem rulers. Just, just watch the demonstration site. So each one of these basically shows the, the various places, the various differences that could be found, but some are missing. For example, for 17, length 17 and 6 marks, these are gaps and what's representable. And I'm not sure which of the, which, which eight of these are not found with the Springer method. That's something I should probably mark in this. But the, all the, all the larger ones were found with the Springer method much earlier. These golem rulers are also called side on sets. If you take any golem ruler and add up the values, all the sums are distinct. So for example, with this particular set, if we do all the possible sums, we get this list and none of these are repeated. It turns out that every golem ruler is a side on set, and every side onset is a golem ruler. And it's easy to prove that. Basically, if there was a case that you had a golem ruler that did not generate a site on set, then you could take two values in that site on set that represented a repeat. And then if you so that's say A plus B is equal to C plus D. Well then you just use a little bit of arithmetic. A minus C is equal to B minus D. But that would indicate that the golem ruler had a repeat in it. And because of that, that's not possible. Therefore, all golem rulers are side unsets, and all side unsets are golem rulers. We can extend this to two dimensions. For example, if you're given a number of points, how close can they be so that no distance repeats? Well, it turns out this was an Al Zimmerman contest problem and here are all the best known solutions. Up to how many points? 26 points. And it's believed that due to the amount of computer power devoted to this during the contest, that these are the minimal solutions. And this is another demonstration. No, no repeated distances demonstration. What about covering all differences? Well, this is a new demonstration that I that will be published next week. This is sort of the 2D equivalent to sparse rulers. You have to cover all differences, but it's possible to repeat. So for example, when there's more than one green line, that means that, for example here, that means that that distance of square root of 26 repeats. With this set of points, we've managed to solve this up to a 10 by 10 grid. There's a search going on for the 11 by 11 grid right now, but so far for all solutions 5 to 10, the minimal solution needs n + 1, n + 2 points. Whether that will continue on, we don't know. This is an unsolved problem. Oops. So these are examples of that problem. Etsy at the community site here, this loss number 26653076, I give data for 3 million sparse rulers. And you can, you can look it up here and if anybody plays with it and manage to manages to find more sparse rulers, I'd be very interested in seeing what the results are. I tried all sorts of computer methods to take a solution and find more solutions, but maybe there are some new methods that could be developed. So in there you can see various things like here's a whole bunch of lengths, 214 rulers. And here's a extension to the dark mills pattern. Everything is proven up to 213. This is what it looks like one block after 213. These values here, 226, 244, 262, 300, those are all highly suspect values. It's. It's likely that one of those four the solution is actually excess zero instead of excess one. It's just that my computer search wasn't sufficiently powerful enough to find whether or not those were actual the minimals. I'm pretty sure one of those four is wrong. So let's see. Here's some other problems that are unsolved. What about three dimensions? How close can can points be without repeated distances? And a 3D grid that's not been looked at so far as I know was the minimal number of points to cover distance. All distances in a 3D grid of the the 2D grid is something that was just looked at this week. So I'm Pretty sure the 3D grid has not been looked at either. What about other lattices like the octahedron tetrahedron lattice and similar things? What are the minimal cases in those? Just for in 2D, a simple triangular grid. What is the minimal sets of points in those? Those are all unsolved problems and that is what I had prepared. So I'll be glad to answer any questions this. You can just post them and I'll be glad to take a look at them. Let me see here. Oh, and my other screen finally resolved. Let me close that. All right. Tilings. For example, the go in in tilings, a conference room can be set up with Golem ruler partitions. And with those that minimal set of partitions, you can basically throw up two partitions so that the conference room is of any desired size. And there are some hotels that do that use Golem ruler partitioning for how they split up their rooms. So that's one tiling application for at least golem rulers. Spurs rulers would work better for partitioning though because they can cover all sizes, whereas Golem this things. Any other questions? All right, many thanks. I look forward to seeing everybody again next month where I'll have something figured out for the next talk. Many thanks everyone.