My 2018 Mathematics A To Z: Tiling


For today’s a to Z topic I again picked one nominated by aajohannas. This after I realized I was falling into a never-ending research spiral on Mr Wu, of Mathtuition’s suggested “torus”. I do have an older essay describing the torus, as a set. But that does leave out a lot of why a torus is interesting. Well, we’ll carry on.

Cartoon of a thinking coati (it's a raccoon-like animal from Latin America); beside him are spelled out on Scrabble titles, 'MATHEMATICS A TO Z', on a starry background. Various arithmetic symbols are constellations in the background.
Art by Thomas K Dye, creator of the web comics Newshounds, Something Happens, and Infinity Refugees. His current project is Projection Edge. And you can get Projection Edge six months ahead of public publication by subscribing to his Patreon. And he’s on Twitter as @Newshoundscomic.

Tiling.

Here is a surprising thought for the next time you consider remodeling the kitchen. It’s common to tile the floor. Perhaps some of the walls behind the counter. What patterns could you use? And there are infinitely many possibilities. You might leap ahead of me and say, yes, but they’re all boring. A tile that’s eight inches square is different from one that’s twelve inches square and different from one that’s 12.01 inches square. Fine. Let’s allow that all square tiles are “really” the same pattern. The only difference between a square two feet on a side and a square half an inch on a side is how much grout you have to deal with. There are still infinitely many possibilities.

You might still suspect me of being boring. Sure, there’s a rectangular tile that’s, say, six inches by eight inches. And one that’s six inches by nine inches. Six inches by ten inches. Six inches by one millimeter. Yes, I’m technically right. But I’m not interested in that. Let’s allow that all rectangular tiles are “really” the same pattern. So we have “squares” and “rectangles”. There are still infinitely many tile possibilities.

Let me shorten the discussion here. Draw a quadrilateral. One that doesn’t intersect itself. That is, there’s four corners, four lines, and there’s no X crossings. If you have that, then you have a tiling. Get enough of these tiles and arrange them correctly and you can cover the plane. Or the kitchen floor, if you have a level floor. It might not be obvious how to do it. You might have to rotate alternating tiles, or set them in what seem like weird offsets. But you can do it. You’ll need someone to make the tiles for you, if you pick some weird pattern. I hope I live long enough to see it become part of the dubious kitchen package on junk home-renovation shows.

Let me broaden the discussion here. What do I mean by a tiling if I’m allowing any four-sided figure to be a tile? We start with a surface. Usually the plane, a flat surface stretching out infinitely far in two dimensions. The kitchen floor, or any other mere mortal surface, approximates this. But the floor stops at some point. That’s all right. The ideas we develop for the plane work all right for the kitchen. There’s some weird effects for the tiles that get too near the edges of the room. We don’t need to worry about them here. The tiles are some collection of open sets. No two tiles overlap. The tiles, plus their boundaries, cover the whole plane. That is, every point on the plane is either inside exactly one of the open sets, or it’s on the boundary between one (or more) sets.

There isn’t a requirement that all these sets have the same shape. We usually do, and will limit our tiles to one or two shapes endlessly repeated. It seems to appeal to our aesthetics and our installation budget. Using a single pattern allows us to cover the plane with triangles. Any triangle will do. Similarly any quadrilateral will do. For convex pentagonal tiles — here things get weird. There are fourteen known families of pentagons that tile the plane. Each member of the family looks about the same, but there’s some room for variation in the sides. Plus there’s one more special case that can tile the plane, but only that one shape, with no variation allowed. We don’t know if there’s a sixteenth pattern. But then until 2015 we didn’t know there was a 15th, and that was the first pattern found in thirty years. Might be an opening for someone with a good eye for doodling.

There are also exciting opportunities in convex hexagons. Anyone who plays strategy games knows a regular hexagon will tile the plane. (Regular hexagonal tilings fit a certain kind of strategy game well. Particularly they imply an equal distance between the centers of any adjacent tiles. Square and triangular tiles don’t guarantee that. This can imply better balance for territory-based games.) Irregular hexagons will, too. There are three known families of irregular hexagons that tile the plane. You can treat the regular hexagon as a special case of any of these three families. No one knows if there’s a fourth family. Ready your notepad at the next overlong, agenda-less meeting.

There aren’t tilings for identical convex heptagons, figures with seven sides. Nor eight, nor nine, nor any higher figure. You can cover them if you have non-convex figures. See any Tetris game where you keep getting the ‘s’ or ‘t’ shapes. And you can cover them if you use several shapes.

There’s some guidance if you want to create your own periodic tilings. I see it called the Conway Criterion. I don’t know the field well enough to say whether that is a common term. It could be something one mathematics popularizer thought of and that other popularizers imitated. (I don’t find “Conway Criterion” on the Mathworld glossary, but that isn’t definitive.) Suppose your polygon satisfies a couple of rules about the shapes of the edges. The rules are given in that link earlier this paragraph. If your shape does, then it’ll be able to tile the plane. If you don’t satisfy the rules, don’t despair! It might yet. The Conway Criterion tells you when some shape will tile the plane. It won’t tell you that something won’t.

(The name “Conway” may nag at you as familiar from somewhere. This criterion is named for John H Conway, who’s famous for a bunch of work in knot theory, group theory, and coding theory. And in popular mathematics for the “Game of Life”. This is a set of rules on a grid of numbers. The rules say how to calculate a new grid, based on this first one. Iterating them, creating grid after grid, can make patterns that seem far too complicated to be implicit in the simple rules. Conway also developed an algorithm to calculate the day of the week, in the Gregorian calendar. It is difficult to explain to the non-calendar fan how great this sort of thing is.)

This has all gotten to periodic tilings. That is, these patterns might be complicated. But if need be, we could get them printed on a nice square tile and cover the floor with that. Almost as beautiful and much easier to install. Are there tilings that aren’t periodic? Aperiodic tilings?

Well, sure. Easily. Take a bunch of tiles with a right angle, and two 45-degree angles. Put any two together and you have a square. So you’re “really” tiling squares that happen to be made up of a pair of triangles. Each pair, toss a coin to decide whether you put the diagonal as a forward or backward slash. Done. That’s not a periodic tiling. Not unless you had a weird run of luck on your coin tosses.

All right, but is that just a technicality? We could have easily installed this periodically and we just added some chaos to make it “not work”. Can we use a finite number of different kinds of tiles, and have it be aperiodic however much we try to make it periodic? And through about 1966 mathematicians would have mostly guessed that no, you couldn’t. If you had a set of tiles that would cover the plane aperiodically, there was also some way to do it periodically.

And then in 1966 came a surprising result. No, not Penrose tiles. I know you want me there. I’ll get there. Not there yet though. In 1966 Robert Berger — who also attended Rensselaer Polytechnic Institute, thank you — discovered such a tiling. It’s aperiodic, and it can’t be made periodic. Why do we know Penrose Tiles rather than Berger Tiles? Couple reasons, including that Berger has to use 20,426 distinct tile shapes. In 1971 Raphael M Robinson simplified matters a bit and got that down to six shapes. Roger Penrose in 1974 squeezed the set down to two, although by adding some rules about what edges may and may not touch one another. (You can turn this into a pure edges thing by putting notches into the shapes.) That really caught the public imagination. It’s got simplicity and accessibility to combine with beauty. Aperiodic tiles seem to relate to “quasicrystals”, which are what the name suggests and do happen in some materials. And they’ve got beauty. Aperiodic tiling embraces our need to have not too much order in our order.

I’ve discussed, in all this, tiling the plane. It’s an easy surface to think about and a popular one. But we can form tiling questions about other shapes. Cylinders, spheres, and toruses seem like they should have good tiling questions available. And we can imagine “tiling” stuff in more dimensions too. If we can fill a volume with cubes, or rectangles, it’s natural to wonder what other shapes we can fill it with. My impression is that fewer definite answers are known about the tiling of three- and four- and higher-dimensional space. Possibly because it’s harder to sketch out ideas and test them. Possibly because the spaces are that much stranger. I would be glad to hear more.


I’m hoping now to have a nice relaxing weekend. I won’t. I need to think of what to say for the letter ‘U’. On Tuesday I hope that it will join the rest of my A to Z essays at this link.

Advertisements

Reading the Comics, November 25, 2017: Shapes and Probability Edition


This week was another average-grade week of mathematically-themed comic strips. I wonder if I should track them and see what spurious correlations between events and strips turn up. That seems like too much work and there’s better things I could do with my time, so it’s probably just a few weeks before I start doing that.

Ruben Bolling’s Super-Fun-Pax Comics for the 19th is an installment of A Voice From Another Dimension. It’s in that long line of mathematics jokes that are riffs on Flatland, and how we might try to imagine spaces other than ours. They’re taxing things. We can understand some of the rules of them perfectly well. Does that mean we can visualize them? Understand them? I’m not sure, and I don’t know a way to prove whether someone does or does not. This wasn’t one of the strips I was thinking of when I tossed “shapes” into the edition title, but you know what? It’s close enough to matching.

Olivia Walch’s Imogen Quest for the 20th — and I haven’t looked, but it feels to me like I’m always featuring Imogen Quest lately — riffs on the Monty Hall Problem. The problem is based on a game never actually played on Monty Hall’s Let’s Make A Deal, but very like ones they do. There’s many kinds of games there, but most of them amount to the contestant making a choice, and then being asked to second-guess the choice. In this case, pick a door and then second-guess whether to switch to another door. The Monty Hall Problem is a great one for Internet commenters to argue about while the rest of us do something productive. The trouble — well, one trouble — is that whether switching improves your chance to win the car is that whether it does depends on the rules of the game. It’s not stated, for example, whether the host must open a door showing a goat behind it. It’s not stated that the host certainly knows which doors have goats and so chooses one of those. It’s not certain the contestant even wants a car when, hey, goats. What assumptions you make about these issues affects the outcome.

If you take the assumptions that I would, given the problem — the host knows which door the car’s behind, and always offers the choice to switch, and the contestant would rather have a car, and such — then Walch’s analysis is spot on.

Jonathan Mahood’s Bleeker: The Rechargeable Dog for the 20th features a pretend virtual reality arithmetic game. The strip is of incredibly low mathematical value, but it’s one of those comics I like that I never hear anyone talking about, so, here.

Richard Thompson’s Cul de Sac rerun for the 20th talks about shapes. And the names for shapes. It does seem like mathematicians have a lot of names for slightly different quadrilaterals. In our defense, if you’re talking about these a lot, it helps to have more specific names than just “quadrilateral”. Rhomboids are those parallelograms which have all four sides the same length. A parallelogram has to have two pairs of equal-sized legs, but the two pairs’ sizes can be different. Not so a rhombus. Mathworld says a rhombus with a narrow angle that’s 45 degrees is sometimes called a lozenge, but I say they’re fibbing. They make even more preposterous claims on the “lozenge” page.

Todd Clark’s Lola for the 20th does the old “when do I need to know algebra” question and I admit getting grumpy like this when people ask. Do French teachers have to put up with this stuff?

Brian Fies’s Mom’s Cancer rerun for the 23rd is from one of the delicate moments in her story. Fies’s mother just learned the average survival rate for her cancer treatment is about five percent and, after months of things getting haltingly better, is shaken. But as with most real-world probability questions context matters. The five-percent chance is, as described, the chance someone who’d just been diagnosed in the state she’d been diagnosed in would survive. The information that she’s already survived months of radiation and chemical treatment and physical therapy means they’re now looking at a different question. What is the chance she will survive, given that she has survived this far with this care?

Mark Anderson’s Andertoons for the 24th is the Mark Anderson’s Andertoons for the week. It’s a protesting-student kind of joke. For the student’s question, I’m not sure how many sides a polygon has before we can stop memorizing them. I’d say probably eight. Maybe ten. Of the shapes whose names people actually care about, mm. Circle, triangle, a bunch of quadrilaterals, pentagons, hexagons, octagons, maybe decagon and dodecagon. No, I’ve never met anyone who cared about nonagons. I think we could drop heptagons without anyone noticing either. Among quadrilaterals, ugh, let’s see. Square, rectangle, rhombus, parallelogram, trapezoid (or trapezium), and I guess diamond although I’m not sure what that gets you that rhombus doesn’t already. Toss in circles, ellipses, and ovals, and I think that’s all the shapes whose names you use.

Stephan Pastis’s Pearls Before Swine for the 25th does the rounding-up joke that’s been going around this year. It’s got a new context, though.

Theorem Thursday: The Jordan Curve Theorem


There are many theorems that you have to get fairly far into mathematics to even hear of. Often they involve things that are so abstract and abstruse that it’s hard to parse just what we’re studying. This week’s entry is not one of them.

The Jordan Curve Theorem.

There are a couple of ways to write this. I’m going to fall back on the version that Richard Courant and Herbert Robbins put in the great book What Is Mathematics?. It’s a theorem in the field of topology, the study of how shapes interact. In particular it’s about simple, closed curves on a plane. A curve is just what you figure it should be. It’s closed if it … uh … closes, makes a complete loop. It’s simple if it doesn’t cross itself or have any disconnected bits. So, something you could draw without lifting pencil from paper and without crossing back over yourself. Have all that? Good. Here’s the theorem:

A simple closed curve in the plane divides that plane into exactly two domains, an inside and an outside.

It’s named for Camille Jordan, a French mathematician who lived from 1838 to 1922, and who’s renowned for work in group theory and topology. It’s a different Jordan from the one named in Gauss-Jordan Elimination, which is a matrix thing that’s important but tedious. It’s also a different Jordan from Jordan Algebras, which I remember hearing about somewhere.

The Jordan Curve Theorem is proved by reading its proposition and then saying, “Duh”. This is compelling, although it lacks rigor. It’s obvious if your curve is a circle, or a slightly squished circle, or a rectangle or something like that. It’s less obvious if your curve is a complicated labyrinth-type shape.

A labyrinth drawn in straight and slightly looped lines.
A generic complicated maze shape. Can you pick out which part is the inside and which the outside? Pretend you don’t notice that little peninsula thing in the upper right corner. I didn’t mean the line to overlap itself but I was using too thick a brush in ArtRage and didn’t notice before I’d exported the image.

It gets downright hard if the curve has a lot of corners. This is why a completely satisfying rigorous proof took decades to find. There are curves that are nowhere differentiable, that are nothing but corners, and those are hard to deal with. If you think there’s no such thing, then remember the Koch Snowflake. That’s that triangle sticking up from the middle of a straight line, that itself has triangles sticking up in the middle of its straight lines, and littler triangles still sticking up from the straight lines. Carry that on forever and you have a shape that’s continuous but always changing direction, and this is hard to deal with.

Still, you can have a good bit of fun drawing a complicated figure, then picking a point and trying to work out whether it’s inside or outside the curve. The challenging way to do that is to view your figure as a maze and look for a path leading outside. The easy way is to draw a new line. I recommend doing that in a different color.

In particular, draw a line from your target point to the outside. Some definitely outside point. You need the line to not be parallel to any of the curve’s line segments. And it’s easier if you don’t happen to intersect any vertices, but if you must, we’ll deal with that two paragraphs down.

A dot with a testing line that crosses the labyrinth curve six times, and therefore is outside the curve.
A red dot that turns out to be outside the labyrinth, based on the number of times the testing line, in blue, crosses the curve. I learned doing this that I should have drawn the dot and blue line first and then fit a curve around it so I wouldn’t have to work so hard to find one lousy point and line segment that didn’t have some problems.

So draw your testing line here from the point to something definitely outside. And count how many times your testing line crosses the original curve. If the testing line crosses the original curve an even number of times then the original point was outside the curve. If the testing line crosses the original an odd number of times then the original point was inside of the curve. Done.

If your testing line touches a vertex, well, then it gets fussy. It depends whether the two edges of the curve that go into that vertex stay on the same side as your testing line. If the original curve’s edges stay on the same side of your testing line, then don’t count that as a crossing. If the edges go on opposite sides of the testing line, then that does count as one crossing. With that in mind, carry on like you did before. An even number of crossings means your point was outside. An odd number of crossings means your point was inside.

The testing line touches a corner of the curve. The curve comes up to and goes away from the same side as the testing line.
This? Doesn’t count as the blue testing line crossing the black curve.

The testing line touches a corner of the curve. The curve crosses over, with legs on either side of the testing line at that point.
This? This counts as the blue testing line crossing the black curve.

So go ahead and do this a couple times with a few labyrinths and sample points. It’s fun and elevates your doodling to the heights of 19th-century mathematics. Also once you’ve done that a couple times you’ve proved the Jordan curve theorem.

Well, no, not quite. But you are most of the way to proving it for a special case. If the curve is a polygon, a shape made up of a finite number of line segments, then you’ve got almost all the proof done. You have to finish it off by choosing a ray, a direction, that isn’t parallel to any of the polygon’s line segments. (This is one reason this method only works for polygons, and fails for stuff like the Koch Snowflake. It also doesn’t work well with space-filling curves, which are things that exist. Yes, those are what they sound like: lines that squiggle around so much they fill up area. Some can fill volume. I swear. It’s fractal stuff.) Imagine all the lines that are parallel to that ray. There’s definitely some point along that line that’s outside the curve. You’ll need that for reference. Classify all the points on that line by whether there’s an even or an odd number of crossings between a starting point and your reference definitely-outside point. Keep doing that for all these many parallel lines.

And that’s it. The mess of points that have an odd number of intersections are the inside. The mess of points that have an even number of intersections are the outside.

You won’t be surprised to know there’s versions of the Jordan curve theorem for solid objects in three-dimensional space. And for hyperdimensional spaces too. You can always work out an inside and an outside, as long as space isn’t being all weird. But it might sound like it’s not much of a theorem. So you can work out an inside and an outside; so what?

But it’s one of those great utility theorems. It pops in to places, the perfect tool for a problem you were just starting to notice existed. If I can get my rhetoric organized I hope to show that off next week, when I figure to do the Five-Color Map Theorem.

To Apply Both My A To Z Essay Serieses All At Once


I did mean to include a mention of this in yesterday’s post, but I misplaced the link and feel a bit silly about that now. Anyway, over the course of the Summer 2015 and the Leap Day 2016 A To Z I’ve had the chance to talk about a bunch of concepts including duals and Riemann spheres and nontrivial subsets of things. Baking And Math, which combines discussions of mathematics with cooking tips, is as far as I know unaware of my existence. But the blog’s made use of these kinds of things in describing the Poincaré homology sphere. I’m not sure that I can explain why this is an interesting shape to study, especially not this weekend as I’ve been busy with some pinball events. But the shape looks great, and the essay describes some of the making of this wonderful shape. You can appreciate it for beauty bare.

Spherical Cycloids


Today I don’t have anything big. I just wanted to point people to “Spherical Cycloids”, a post on the WordPress blog The Inner Frame. Cycloids are somewhat familiar, at least to kids who grew up in the United States in my age cohort, because you get them out of spirographs. You make them by taking some point within a rotatable object. Roll that object along the path, normally one that’s defined by another shape. You can get wonderful and strange and exotic-looking curves, many with a hypnotic regularity.

The Inner Frame made a variation of this. It’s got cycloids drawn on the surface of the sphere. This immediately adds a new level of strangeness and wonder to the curves. The pictures are lovely and hypnotic. Folks with 3-D printers can probably also make some grand exotic candleholders from the pattern, too.

Dice and Compass Games


By the way, I wasn’t the only one to write about that dice problem the other day. Jim Doherty, with the MrDardy blog, also spoke about it. He’s actively teaching, and hopes to report what his classes made of it. He writes regularly about the teaching experience and the experiments to try to make it better.

This did get me into a fun bit of Twitter chatter about the odds of bloggers writing about the same question like this. I can’t imagine the question having a real answer, though. We both wrote about it because we saw the same initial question on Twitter. But we saw it because we both try following stuff in the mathematics blogosphere. Among other things, that seeks out and connects fun problems like this. And it’s a problem easy to write up.

In a bit more of mathematical puttering-about news, here’s a pleasant little tool for making geometric constructions. It’s got compass-and-straightedge, as well as protractor-and-ruler, features. I admit I’m not sure I have a practical use for it, but it’s pretty and fun.

And you can do amazing things with compass-and-straightedge constructions. For my money, the most amazing thing is quadrature. That’s starting from some other shape and constructing a square with the same area. There are shapes it’s easy to do this for: rectangles, triangles, polygons of all sorts. There are shapes it’s impossible to do this for: circles, most famously. And then there are shapes you’d think would be impossible but aren’t, such as certain lunes. These are crescent-moon shapes. If circles are impossible (and they are), wouldn’t you think a shape with edges are the arcs of two different circles would be impossible too? And yet, they’re possible, for at least the right lunes.

Here’s one. Draw a half-circle. Let’s say, for convenience, that you’ve drawn the upper half of one. Now draw the vertical line from the center of the circle to its top point. Then draw the line connecting the leftmost corner to the top corner. This will be the hypotenuse of a right triangle with two 45-degree angles.

Next, draw the half-circle that fits on that hypotenuse, and that points outward, past the edge of the original half-circle. The lune of interest is the one between the original half-circle and the new one. And you can, using only compass and straightedge, produce a square with exactly the same area as that curved shape. If that’s not remarkable enough, it’s the same area as that triangle we had to start out. But we can not, using compass and straightedge, make a square that’s the same area as that little wedge between lune and triangle.

The quadrature of the triangle isn’t too hard to work out, if you start from scratch. (If you don’t know how to start, try starting with the area of a rectangle instead.) The lune, I’ll admit, I didn’t figure out by myself, but it’s not absurd. That the remaining wedge is impossible you won’t prove on your own. I’m not sure how I would explain it, not in only a few essays.

And with that hook, I’d like to toss in one last appeal for any requests for the Winter 2016 Mathematics A To Z. Before you pull out calendars on me and work out how long three-a-week essays might last, remember that I live in a state that typically gets a long winter. Letters are filling up, but many are still open. And last time around I had to really dig to find a good y- or z- term. If you want a sure in, those are good letters to think up.

A Summer 2015 Mathematics A To Z: locus


Locus.

A locus is a collection of points that all satisfy some property. For example, the locus of points that are all equally distant from some center point is a circle. Or maybe it’ll be a sphere, or even a hypersphere. That depends whether we’re looking at points in a plane, in three-dimensional space, or something more. When we draw lines and parabolas and other figures like that in algebra we’re drawing locuses. Those locuses are the points that satisfy the property “the values of the coordinates of this point make that equation true”.

The idea is a bit different in connotation from “the curve of an equation”. We might not be talking about points that can be conveniently, or sensibly, described by an equation. We might want something like “the shape made by the reflection of this rectangle across this cylindrical mirror”. Or we might want “the points in space from which a space probe will crash into the moon, instead of crashing into Earth”. It’s convenient to have a shorthand way of talking about that idea. Using this word avoids necessarily tying ourselves to drawings or figures we might not be able to produce even in theory.