Some words on PWW #22

There are lots of patterns to be found in the picture from my previous post!

This is a really remarkable tiling. Here are a few special properties I know of:

  1. First of all, I hope you realized that the pattern can be extended infinitely to cover the whole plane with a hexagonal tiling. One way to convince yourself of this is to look at the horizontal strips of hexagons labelled 6 \dots 0. Each row of hexagons will just have 6 \dots 0 repeating forever; and each row is a copy of the row below it, offset by two and a half hexagons.

  2. Of course, there are seven different colors used (also indicated by the numbers 0 \dots 6).

  3. Instead of seeing it as made up of a bunch of repeating strips, you can also see it as made of a bunch of repeating parallelograms:

    Each parallelogram has four zeros at its corners, and contains one of every other color/number in its interior. (There’s actually nothing special about zero; you can make parallelograms using any number you choose for the corners.)

  4. Every hexagon touches six other hexagons, exactly one with each other color/number. For example, a hexagon labelled 1 will touch six hexagons labelled 0, 2, 3, 4, 5, and 6. (Can you see how to prove this? Think about how the whole tiling is built out of copies of the strip 6 \dots 0.) This explains what’s so special about having seven colors!

  5. If you pick any color and look at all the hexagons of that color, they are always arranged in the same pattern, at the vertices of an equilateral triangular grid. For example, below I have arbitrarily chosen to highlight all the number 3 hexagons:

    This means that if you pick any two colors/numbers, there is always some translation that will move all the hexagons of one color to the places that used to be occupied by the hexagons of the other color.

    Here’s what it looks like if we draw all these triangular grids overlaid on top of each other (with brighter colors just for fun). I think it’s remarkable that seven equilateral triangular grids fit together so precisely!

  6. In fact, since each hexagon touches one of each other color, for any two colors we can move all the hexagons of one color to those of the other by translating just one “hexagon unit”—that is, each hexagon will move to a hexagon next to it. For example, if we want to move all the number 3 hexagons so they match up with where the number 5 hexagons used to be, just move everything one hexagon down and to the right.

    I’ll reproduce the original image here so you can refer to it while thinking about this and the following properties:

  7. Each of the six directions we can translate corresponds to adding by a different number mod seven. For example, it’s easy to see that moving to the left corresponds to adding 1 (adding 1 to 6 wraps back around to 0 because we take the remainder when dividing by 7). In other words, pick any hexagon and look at its number; the hexagon to its left will have a number which is 1 bigger (mod 7). Moving down and to the right is adding 2: for example, starting at the 0 in the middle and following the line of hexagons down and to the right, we find 0, 2, 4, 6, 1, 3, 5, 0, where each number is two more than the previous (mod 7). Down and to the left is adding 3; and so on. I’ll let you work out the other three directions.

  8. As pointed out in a comment by Will, rotating corresponds to multiplication mod 7! For example, rotating 60 degrees counterclockwise around 0 corresponds to multiplying by 3 (mod 7). In counterclockwise order, the six numbers we find around 0 are 1, 3, 2, 6, 4, 5. We can check that 1 \times 3 = 3, and 3 \times 3 = 9 \equiv 2 \pmod 7, 2 \times 3 = 6, 6 \times 3 = 18 \equiv 4 \pmod 7, and so on. Rotating the other direction is multiplying by 5. Rotating by 120 degrees is multiplying by 2 or 4; rotating by 180 degrees is multiplying by 6.

  9. Pick a hexagon; say it contains the number n. We already know that none of the hexagons it touches contain n. But in fact, none of the hexagons those hexagons touch contain n either (except for the original hexagon we chose). This is because each hexagon touches exactly one copy of every other color/number. So, in other words, each hexagon is contained in two layers of hexagons, none of which share the same color with the central hexagon. For example, if we pick a zero hexagon and go two layers out from there, we can see that the zero in the middle is the only zero (and there are exactly 3 copies of each other number):

Let me know in the comments if you see any other patterns that I missed!

Posted in geometry, pattern | Tagged , , , | 4 Comments

Post without words #22

Image | Posted on by | Tagged , , , , , | 11 Comments

The Math Less Traveled on Patreon!

tl;dr: I’ve just created a Patreon page where you can pledge to support The Math Less Traveled with a small monthly donation and become part of a community that will help shape future posts and topics!

I’ve been writing this blog for almost twelve years (!). Over that time I’ve published more than 400 posts totaling almost 200,000 words. Writing The Math Less Traveled is not my job and I’ve never gotten paid for it; I just love to explore beautiful ideas and find creative ways to explain them to others.

Normally this is the place where I would say how The Math Less Traveled won’t be able to continue to exist without your support, and how I need to feed my family, and so on. But the honest truth is that my family is doing just fine, and I will probably continue writing The Math Less Traveled no matter what! It would just be nice to be rewarded for my hard work, and to at least be able to offset the cost of the frequent writing sessions in my favorite local coffee shop (where I’m writing this right now), buy some relevant books now and then, and upgrade my WordPress plan to have ads removed. I’m also excited to use Patreon as a platform to build a closer, more collaborative relationship with my readers: I will consult patrons at the $5/month level for things like feedback on drafts, research help, and ideas for topics, posts, and visualizations.

If you find my writing valuable, I hope you’ll consider becoming a patron, even at just a few dollars a month. Of course, there are also some cool rewards, like high-resolution versions of any graphics I make for the blog, and access to patron-only content (likely full of my random mathematical musings and stories about math conversations with my kids).

Thanks for reading regardless, and here’s to the next twelve years! Next up: how to color the plane using only seven colors (aka pretty pictures made by mathematically-minded bees!).

Posted in meta | Tagged , , | Leave a comment

The chromatic number of the plane, part 4: an upper bound

In my previous posts I explained lower bounds for the Hadwiger-Nelson problem: we know that the chromatic number of the plane is at least 5 because there exist unit distance graphs which we know need at least 5 colors. Someday, perhaps someone will succeed in constructing an even bigger unit distance graph that requires 6 colors, and then we’ll know CNP \geq 6.

But what about an upper bound? Can we say for sure that the CNP has to be smaller than some limit? Indeed, we can: we know that CNP \leq 7. Today I want to explain how we can show that CNP \leq 9; in another post I’ll show the proof that CNP \leq 7.

Proving an upper bound for the chromatic number of the plane is very different than proving a lower bound. A lower bound is all about showing that you can’t color the plane with a certain number of colors. An upper bound, on the other hand, is all about showing that you can. We know that CNP \leq 7 because there is a specific, valid way to color the plane using only seven colors! It might be possible to do it with fewer colors, using a very clever pattern, which is why 7 is only an upper bound. But at least we know it can be done with 7.

Let’s start with something simpler. Imagine coloring the whole plane with a repeating pattern like this:

Can this be a valid coloring of the plane? (Of course, we already know it can’t because it only uses four colors, and CNP > 4; but let’s see if we can give a more direct argument why this is not valid). First of all, the squares can’t be too big: we don’t want any pair of points inside the same square to be 1 unit apart. This means the diagonal of each square has to be less than 1.

So if the diagonals of the squares are less than 1, the sides of the squares have to be less than 1 / \sqrt 2. But the problem is that squares of the same color also have to be far enough apart so that no two points in same-colored squares are 1 unit apart. But in this scenario same-colored squares are separated by only one other square; if the sides of the squares is < 1 / \sqrt 2 \approx 0.707 then they are too close.

This idea can be easily salvaged, however: we just need more colors!

Now we are using nine colors, with a 3 \times 3 repeating pattern instead of 2 \times 2. Let’s see if we can make this work. Once again, the squares can’t be too big (lest two points inside the same square can be 1 unit apart) but same-color squares can’t be too close (lest two points in different same-color squares can be 1 unit apart). Call s the side length of the squares. The first condition once again gives us s < 1/\sqrt 2. What about the second condition? The shortest distance between two same-colored squares is now 2s, if you travel straight east-west or north-south. (You can confirm for yourself that any other line between same-colored squares is longer.) So we must have 2s > 1.

Can we pick a value of s that makes s < 1/\sqrt 2 and 2s > 1 both true? Yes! Rearranging a bit, this just says 1/2 < s < 1/\sqrt 2. Since 1/2 < 1/\sqrt 2 this gives us a valid range of values for s; any such value for s gives us a valid 9-coloring of the plane.

Hence, it is possible to color the plane using 9 colors, such that no two points at distance 1 from each other have the same color! We don’t know if this is the best way to color the plane (in fact, it isn’t!), but at least we know it is a way. So this shows that CNP \leq 9.

In my next post I’ll explain how we know that CNP \leq 7: the proof is similar in spirit, but more complex (and, of course, more efficient) due to its use of hexagons instead of squares.

Posted in geometry, proof | Tagged , , , , , , | Leave a comment

Iterating squared digit sums in other bases

In a previous post I wrote about iterating the squared digit sum function, which adds up the sum of the squares of the digits of a number; for example, s(149) = 1^2 + 4^2 + 9^2 = 1 + 16 + 81 = 98. Denis left a comment asking about other bases—what happens if we write a number in a base other than base ten and add up the squares of its digits in that base? It’s a good question, because the choice of adding up the squares of base ten digits, while natural from a human point of view, is mathematically quite arbitrary. We can sum the squares of the digits of a number written in any base.

As Denis noted in his comment, the argument from my previous post happily applies in any base, not just base 10! That is, if we consider a d-digit number in base b, the largest it can be is if it consists of d copies of the largest possible digit, which is b-1. In that case the sum of squares of its digits would be d(b-1)^2. For example, the largest sum of squares we could get with a six-digit number in base 5 is 444444, which gives us a sum of squares of 6 \cdot 4^2 = 96. But the claim is that this will be less than b^{d-1} as long as d \geq 4 and b \geq 2—which means that taking the sum of squares of the base-b digits of any number with four or more such digits will always result in a shorter base-b number. We can check that this is true when b = 2 and d = 4, since 4 \cdot 1^2 = 4 < 2^3 = 8; and intuitively, increasing either b or d will make the right-hand side increase more than the left-hand side, so it will always be true for b \geq 2 and d \geq 4. (This is an informal, hand-wavy argument—if you think you know of a way to prove it formally I would love to hear about it!)

The upshot is that for any base b \geq 2 we only have to try numbers with up to three digits to look for loops, since any bigger numbers will reduce until they have at most three digits. (One might wonder it will ever suffice to consider only two-digit numbers, when b gets large enough. The answer, perhaps surprisingly, is no. We would be looking for a base b such that 3(b-1)^2 < b^2—that is, a base for which three-digit numbers always reduce to two-digit numbers. As you can verify for yourself, the only solutions to this inequality are when b < 2! So four digits is the magic cutoff for every base b \geq 2. (I’m not going to consider negative bases here; maybe in another post.))

So I wrote a program which, for each base b, finds all the loops that happen on base-b numbers from 1 to b^3-1. It turns out that only a few bases have a single nontrivial loop, like base 10 (perhaps this is not surprising). The ones I have found are as follows. (After base 10 we quickly run out of digits; I use lowercase letters a to z to stand for digits 10 through 35, and then uppercase letters A to Z to stand for digits 36 through 61.)

  • Base 6: 32 \to 21 \to 5 \to 41 \to 25 \to 45 \to 105 \to 42
  • Base 10: 4 \to 16 \to 37 \to 58 \to 89 \to 145 \to 42 \to 20
  • Base 16: a9 \to b5 \to 92 \to 55 \to 32 \to d
  • Base 20: e9, dh, 12i, g9, gh, 175, 3f, be, fh, 15e, b2, 65, 31, a, 50, 15, 16, 1h, ea, eg, 12c, 79, 6a, 6g, ec, h0
  • Base 26: o1 \to m5 \to jf \to me \to 104 \to h \to b3 \to 50 \to p
  • Base 40: 3p \to fy \to yl \to DB \to 1wa \to s5 \to k9 \to c1

Base 20 is particularly magnificent: there is a single nontrivial loop, and it has length 26!

I let my program run all the way up to base 150 (which took about 3.5 minutes on my admittedly not-so-fast laptop). Here’s some trivia:

  • After base 40, I didn’t find any more bases with only a single nontrivial loop. I conjecture there aren’t any more.
  • There are two bases tied for longest loop: base 119 and base 146 both have a loop of length 110.
  • The record holder for most loops is base 73, which has twenty-nine distinct loops into which iterating squared digit sum can fall, many of which consist of a single number: in addition to 1, each of 82, 234, 533, 1125, 1640, 2080, 2665, 2738, 3321, 3757, 4264, 4840, 5125, and 5265 is equal to the sum of squares of its own digits when written in base 73. For example, 82_{10} = 19_{73}, and sure enough, 1^2 + 9^2 = 82.

Since each number involved in a loop has at most three digits, we can think of them as coordinates in a 3d space; I wonder what the trajectories of the loops would look like! Someone should do this. A data file containing all loops up to base 150 can be found here (note that after base 61 I just start writing the numbers in base 10 again).

The program I used to search can be found here. I think my program is fairly efficient but it could probably be sped up in various ways to search much farther.

Posted in arithmetic, computation, proof | Tagged , , , , | 7 Comments

The chromatic number of the plane, part 3: a new lower bound

In my previous post I explained how we know that the chromatic number of the plane is at least 4. If we can construct a unit distance graph (a graph whose edges all have length 1) which needs at least c colors, than we know the plane also needs at least c colors. We were able to construct a unit distance graph that needs at least 4 colors (the Moser spindle), and hence the chromatic number of the plane is at least 4.

It turns out that de Grey’s new proof follows exactly this same pattern: he constructs a unit distance graph which needs at least 5 colors. So why hasn’t anyone else done this before now? The Moser spindle (a unit distance graph with chromatic number 4) has been around since 1961; why did it take almost 60 years for someone to come up with a unit distance graph with chromatic number 5?

The reason is that the graph is very big! de Grey’s graph has 1581 vertices. Although it is itself constructed out of copies of smaller pieces, which are themselves constructed out of pieces, etc.—so it’s not quite as hard to analyze as any random 1581-vertex graph—proving that it requires 5 colors still required a computer. Even the process of finding the graph in the first place required a computer search. So that’s why no one had done it in the last 60 years.

A lot of people have been working on improving and extending this result. The current record-holder for smallest unit-distance graph with chromatic number 5 has 610 vertices, and was found by Marijn Heule using a computer search. Here’s a picture of it, provided by Marijn:

A 610-vertex unit-distance graph with chromatic number 5
A 610-vertex unit-distance graph with chromatic number 5

It’s unknown whether we will be able to find a proof that can be constructed and understood by humans without the help of a computer. It’s also unknown whether these techniques and the associated technology will be able to extend far enough to find a unit distance graph with chromatic number 6 (if such a thing exists—though it seems many mathematicians believe it should).

Posted in geometry, proof | Tagged , , , , , | 1 Comment

The chromatic number of the plane, part 2: lower bounds

In a previous post I explained the Hadwiger-Nelson problem—to determine the chromatic number of the plane—and I claimed that we now know the answer is either 5, 6, or 7. In the following few posts I want to explain how we know this! The proofs are not too hard to understand (with the possible exception of Aubrey de Grey’s new proof, but I’ll get to that later) and they are really cool.

In this post I’ll talk about lower bounds. That is, how do we know that the chromatic number of the plane (CNP) is at least 5?

CNP > 1

Let’s start with a smaller number. Can we argue that the CNP is at least 2? Sure, this is easy: if the entire plane is colored with only one color, then obviously any two points separated by a distance of 1 unit have the same color. So one color is not enough, and hence CNP \geq 2.

CNP > 2

Is two colors enough? If you play around with it a bit, most likely you will quickly get an intuition that this won’t work either. Here’s an intuitive argument why we need at least three colors. Suppose some region of the plane is colored, say, blue.

(It doesn’t have to be a circle, but let’s just think about a circular-ish region for simplicity’s sake.) The diameter of the region has to be smaller than 1, because otherwise there would be two points within the region that are 1 unit apart. But that means the entire area outside the region has to be, say, red.

But if the diameter of the blue region is less than 1 and the area outside the region is all red, then intuitively, we can find two red points which are a distance of 1 apart, as illustrated in the above picture.

This isn’t really a formal argument at all (what about really weirdly-shaped regions)? But we can give a different argument which is completely formal yet still quite simple. Consider the graph consisting of three vertices connected in a triangle.

As mentioned in my previous post, the chromatic number of this graph is 3—each vertex needs its own color since each vertex is adjacent to both other vertices. But this actually tells us something about the plane, since this graph can be drawn as an equilateral triangle with all its edges having length 1. If we pick any three points in the plane arranged in a unit equilateral triangle, they must all have different colors; hence at least three colors are needed to color the plane.

CNP > 3

Generalizing from the previous proof, we can see a general plan of attack to prove that three colors are not enough to color the plane. We want to find some graph G such that

  • the chromatic number of G is 4, and
  • G is a unit-distance graph, that is, it can be drawn in such a way that every edge has length 1.

If we can find such a graph, it immediately shows that we need at least four colors for the plane, since we can pick a set of points in the plane in exactly the same configuration as the vertices of the graph; since the vertices of the graph need four colors, so do the chosen points of the plane.

Well, such a graph G exists! In fact, there are many such graphs, but the simplest one is called the Moser spindle. (It’s named after William and Leo Moser, who published it in 1961; I have no idea why it is called a “spindle”.) Here it is:

As you can see, it’s made of four equilateral triangles, with two pairs glued together along an edge, a shared vertex at the top, and an extra edge of length exactly 1 connecting the bottom vertices. You can check for yourself that this is a unit-distance graph. But what is its chromatic number? Well, suppose we try coloring it with only three colors. Suppose the top vertex is red. That vertex is connected to two equilateral triangles; of course the other two vertices of each triangle must have the other two colors (say, green and blue). Then the two bottom vertices must again be colored red, since each is part of an equilateral triangle with one green and one blue vertex. But this isn’t allowed: the two bottom vertices are connected by an edge, so they can’t be the same color.

So, three colors aren’t enough to color the Moser spindle, and hence three colors aren’t enough to color the plane either!

CNP > 4?

So the above proofs are not that hard to grasp, and we have known that CNP > 3 since 1961 or so. So how did Aubrey de Grey prove that CNP > 4, and why did it take almost 60 years to go from 3 to 4? I’ll explain that in my next post!

Posted in geometry, proof | Tagged , , , , , | 3 Comments