Associahedron

The previous post looked at ways of associating a product of four things. This post will look at associating more things, and visualizing the associations.

The number of ways to associate a product of n+1 things is the nth Catalan number, defined by

C+n = \frac{1}{n+1} {2n \choose n}

The previous post looked at products of 4 things, and there are 5 ways to do that because C3 = 5.

If we look at products of 5 things, there are 14 possibilities because C4 = 14.

In the 1950s Dov Tamari had the idea of visualizing the way associations are related. Jim Stasheff independently came up with the idea in the 1960s.

Imagine parenthesized products as vertices of a polyhedron, and connect two vertices with an edge if you can get from one to the other by one application of the associative law. The product of n terms corresponds to a polyhedron in n-2 dimensions. Such a polyhedron is called an associahedron.

If we were to do this with 4 items, we’d get a pentagon in the plane. This associahedron comes up as the commutative diagram describing the pentagon identity for monoidal categories.

If we do this with 5 items, we get a polygon in 3D. It has 14 vertices, because C4 = 14. It also has 21 edges and 9 faces.

(Quick check: VE + F = 14 – 21 + 9 = 2. Thanks, Euler.)

I recently learned about Excalidraw, and so I drew an associahedron with Excalidraw to try it out. Here’s what I got:

The dashed lines are edges you couldn’t see if the polyhedron were made of opaque material, but that you would see if it were transparent.

It’s not a regular solid because three faces have 4 sides and six faces have 5 sides.

Excalidraw is easy to use. It has more features than are apparent at first, which is good: you’re not immediately overwhelmed with options when you open it up, and yet when you need something you may be able to find it. For example, it’s obvious how to draw straight lines, which is probably what you want to do most of the time. But you can draw smooth curves if you need to.

Related posts

Aesthetic uses of Latin squares

We think they like randomness in design, but we don’t exactly. People like things that are sorta random, but not too random. When you literally scatter things randomly, they looked too clumped [1].

There are many ways around this problem, variations on randomness that people find more aesthetically pleasing. One of these ways is random Latin squares.

A Latin square of size n is an n × n grid filled with n different things—numbers, letters, colors, etc.— such that each kind of thing appears exactly once in each row and in each column. For example, 26 × 26 grid filled with the letters of the English alphabet is a Latin square if every row and every column contains the entire alphabet; no letters repeated and no letters missing.

A random Latin square is an arrangement that is random but subject to the constraint that it be a Latin square. Random Latin squares look nice because they’re somewhat random but they avoid certain kinds of repetition.

Suppose you have five different colors of tile and you need to lay down the tiles in a 10 × 20 grid. You want to lay down the tiles “randomly” but you don’t want too many of any one color to appear in a small area.

One way to do this would be to divide the 10 × 20 space into a grid of grids. Each subgrid is a 5 × 5 Latin square. Here’s an example.

The image above is a 2 × 4 grid of 5 × 5 grids, and each of the 5 × 5 grids is a Latin square chosen at random.

Here’s another example with five different colors and different random Latin squares.

If you look carefully, you’ll spot a few places where tiles of the same color touch on an edge. This cannot happen within a Latin square, but it can happen where two different Latin squares are next to each other. So the randomization scheme described here allows for a few tiles of the same color to touch but not many.

I expect randomized Latin squares are used this way fairly often. You’d never know, and that’s kinda the point. Someone would have to stare at a pattern like this a long time before they realized that horizontal or vertical segments of five do not repeat a color.

Related posts

[1] One way to detect fraud is to look for fake randomness. When people try to make something look random, they usually fail and leave statistically detectable fingerprints.

Unicode and Emoji, or The Giant Pawn Mystery

I generally despise emoji, but I reluctantly learned a few things about them this morning.

My latest couple blog posts involved chess, and I sent out a couple tweets using chess symbols. Along the way I ran into a mystery: sometimes the black pawn is much larger than other chess symbols. I first noticed this in Excel. Then I noticed that sometimes it happens in the Twitter app, and sometimes not, sometimes on the twitter web site, and sometimes not.

For example, the following screen shot is from Safari on iOS.

screenshot of tweet with giant pawn

What’s going on? I explained in a footnote to this post, but I wanted to make this its own post to make it easier to find in the future.

In a nutshell, something in the software environment is deciding that 11 of the twelve chess characters are to be taken literally, but the character for the black pawn is to be interpreted as an emojus [1] representing chess. I’m not clear on whether this is happening in the font or in an app. Probably one, both, or neither depending on circumstances.

I erroneously thought that emoji were all outside Unicode’s BMP (Basic Multilingual Plane) so as not to be confused with ordinary characters. Alas, that is not true.

Here is a full list of Unicode characters interpreted (by …?) as emoji. There are 210 emoji characters in the BMP and 380 outside, i.e. 210 below FFFF and 380 above FFFF.

***

[1] I know that “emoji” is a Japanese word, not a Latin word, but to my ear the singular of “emoji” should be “emojus.”

How to make a chessboard in Excel

I needed to make an image of a chessboard for the next blog post, and I’m not very good at image editing, so I make one using Excel.

There are Unicode characters for chess pieces— white king is U+2654, etc.—and so you can make a chessboard out of (Unicode) text.

    ♔♕♖♗♘♙♚♛♜♝♞♟

I placed the character for each piece in an cell and changed the formatting for all the cells to be centered horizontally and vertically. The following is a screenshot of the Excel file.

Chessboard: screenshot from Excel file

The trickiest part is getting the cells to be square. By default Excel uses different units for height and width, with no apparent way to change the units. But if you switch the View to Page Layout, you can set row height and column width in inches or centimeters.

Another quirk is that you may have to experiment with the font to get all the pieces the same size. In some fonts, the black pawns were larger than everything else [1].

You can download my Excel file here. You could make any chessboard configuration with this file by copying and pasting characters where you want them.

When I tested the file in Libre Office, it worked, but I had to reset the row height to match the column width.

Related posts

[1] Thanks to a reply on twitter I now understand why black’s pawn is sometimes outsized. The black pawn is used as an emoji, a sort of synecdoche representing chess. That’s why some fonts treat U+265E, black knight, entirely differently than U+265F, black pawn. The latter is interpreted not as a peer of the other pieces, but as the chess emoji. See the chess pawn entry in Emojipedia.

More images from an oddball coordinate system

Three months ago I posted some images created by graphing equations in circular coordinates. Not polar coordinates as you might expect, but a strange coordinate system based on circles in another way. The most interesting thing about this coordinate system is that familiar functions product unfamiliar graphs.

This morning I played around with the code from that earlier post and made some new images.

The following image was based on exp(x+7)/10 + 10*tan(x/5).

This image was based on the same function over a different range.

And this hummingbird-line images was based on exp(x) – x.

Here are a few more blog posts that have interesting images.

Drawing commutative diagrams with Quiver

I recently discovered quiver, a tool for drawing commutative diagrams. It looks like a nice tool for drawing diagrams more generally, but it’s designed particularly to include the features you need when drawing the kinds of diagrams that are ubiquitous in category theory.

You can draw diagrams using the online app and export the result to LaTeX (tikz).

Here are some examples.

quiver diagrams

The app is mostly easy to figure out. The object and arrow labels are specified using LaTeX.

Quiver lets you position labels on either side of an arrow, or even inside the arrow as in the e in the first diagram above.

You can change the arrow and arrowhead styles, as in the second example.

It took me a little while to figure out how to have two arrows with the same destination and source, as in the third example. You use the “offset” setting to move arrows up or down do that they’re not on top of each other. And by default, the software helpfully assumes that if you want to move one arrow up a bit from center, you probably want to move the other one down from center by the same amount.

You can use the “curve” setting to draw arrows as in the final example. You can also draw arrows between arrows, as is common when working with 2-categories.

More category theory posts

Some mathematical art

This evening I ran across a paper on an unusual coordinate system that creates interesting graphs based from simple functions. It’s called “circular coordinates,” but this doesn’t mean polar coordinates; it’s more complicated than that. [1]

Here’s a plot reproduced from [1], with some color added (the default colors matplotlib uses for multiple plots).

The plot above was based on a the gamma function. Here are a few plots replacing the gamma function with another function.

Here’s x/sin(x):

Here’s x5:

And here’s tan(x):

Here’s how the plots were created. For a given function f, plot the parametric curves given by

\begin{align*} x(t) &= \frac{2t \left(f(t) \right )^2}{t^2 + \left(f(t) \right )^2} \\ y(t) &= \frac{2t^2 f(t)}{t^2 + \left(f(t) \right )^2} \\ \end{align*}

See [1] for what this has to do with circles and coordinates.

The plots based on a function g(x) are given by setting f(x) = g(x) + c where c = -10, -9, -8, …, 10.

Related posts

[1] Elliot Tanis and Lee Kuivinen, Circular Coordinates and Computer Drawn Designs. Mathematics Magazine. Vol 52 No 3. May, 1979.

Hand-drawn Graphviz diagrams

The Sketchviz site lets you enter GraphViz code and get out something that looks hand-drawn. I decided to try it on some of the GraphViz diagrams I’ve made for this blog.

Here’s a diagram from my post on Rock, Paper, Scissors, Lizard, Spock.

The Sketchviz site defaults to Tinos font, which does not look hand-drawn. Maybe you’d want that sometimes: neatly typeset labels and hand-drawn boxes and arrows. In my case, I thought it looked better to use Sedgwick Ave which looks closer to handwriting.

***

Some posts with GraphViz diagrams:

Some of these posts include GraphViz source.

Optimization, Dominoes, and Frankenstein

Robert Bosch has a new book coming out next week titled OPT ART: From Mathematical Optimization to Visual Design. This post will look at just one example from the book: creating images of Frankenstein’s monster [1] using dominoes.

Frankenstein made from 3 sets of double nine dominoes

The book includes two images, a low-resolution image made from 3 sets of dominoes and a high resolution image made from 48 sets. These are double nine dominoes rather than the more common double six dominoes because the former allow a more symmetric arrangement of dots. There are 55 dominoes in a double nine set. (Explanation and generalization here.)

Image of Frankenstein's monster made from 48 sets of double nine dominoes

The images are created by solving a constrained optimization problem. You basically want to use dominoes whose brightness is proportional to the brightness of the corresponding section of a photograph. But you can only use the dominoes you have, and you have to use them all.

You would naturally want to use double nines for the brightest areas since they have the most white spots and double blanks for the darkest areas. But you only have three of each in the first image, forty eight of each in the second, and you have to make do with the rest of the available pieces. So you solve an optimization problem to do the best you can.

Each domino can be places horizontally or vertically, as long as they fit the overall shape of the image. In the first image, you can see the orientation of the pieces if you look closely. Here’s a little piece from the top let corner.

Domino orientation

One double six is placed vertically in the top left. Next to it are another double six and a double five placed horizontally, etc.

There are additional constraints on the optimization problem related to contrast. You don’t just want to match the brightness of the photograph as well as you can, you also want to maintain contrast. For example, maybe a five-two domino would match the brightness of a couple adjacent squares in the photograph, but a seven-one would do a better job of making a distinction between contrasting regions of the image.

Bosch explains that the problem statement for the image using three sets of dominoes required 34,265 variables and 385 domino constraints. It was solved using 29,242 iterations of a simplex algorithm and required a little less than 2 seconds.

The optimization problem for the image created from 48 sets of dominoes required 572,660 variables and 5,335 constraints. The solution required 30,861 iterations of a simplex algorithm and just under one minute of computation.

Related posts

[1] In the Shelley’s novel Frankenstein, the doctor who creates the monster is Victor Frankenstein. The creature is commonly called Frankenstein, but strictly speaking that’s not his name. There’s a quote—I haven’t been able to track down its source—that says “Knowledge is knowing that Frankenstein wasn’t the monster. Wisdom is knowing that Frankenstein was the monster.” That is, the monster’s name wasn’t Frankenstein, but what Victor Frankenstein did was monstrous.

Drawing with Unicode block characters

My previous post contained the image below.

The point of the post was that the numbers that came up in yet another post made the fractal image above when you wrote them in binary. Here’s the trick I used to make that image.

To make the pattern of 0’s and 1’s easier to see, I wanted to make a graphic with black and white squares instead of the characters 0 and 1. I thought about writing a program to create an image using strings of 0’s and 1’s as input, but then I thought of something more direct.

The Unicode character U+2588 is just a solid rectangle. I replaced the 1’s with U+2588 and replaced the 0’s with spaces. So I made a text file that looked like the image above, and took a screen shot of it. The only problem was that the image was rectangular. I thought the pattern would be easier to see if it were a square, so I changed the aspect ratio on the image.

Here’s another example using Unicode block elements, this time to make a little bar graph, sorta like Edward Tufte’s idea of a sparkline. The characters U+2581 through U+2588 produce bars of increasing height.

bar graph of English letter frequencies

To create images like this, your font needs to include glyphs for Unicode block elements. The font needs to be monospaced as well so the letters will line up under the blocks. The example above was created using the APL385. It also looks good in Hack and Input Mono. In some fonts the block characters don’t align consistently on the baseline.

Here’s the Python code that produced the above graph of English letter frequencies.

# Letter frequencies via
# http://www.norvig.com/mayzner.html
freq = [ 
  8.04, 1.48, 3.34, 3.82, 12.49,
  2.40, 1.87, 5.05, 7.57,  0.16,
  0.54, 4.07, 2.51, 7.23,  7.64,
  2.14, 0.12, 6.28, 6.51,  9.28,
  2.73, 1.05, 1.68, 0.23,  1.66,
  0.09,
]
m = max(freq)

for i in range(26):
    u = int(8*freq[i]/m)
    ch = chr(0x2580+u) if u > 0 else " "
    print(ch, end="")

print()
for i in range(26):
    print(chr(0x41+i), end="")