We think about the concept of distance all the time—how far is it to go visit a friend, is my phone close enough to the router to get wifi?—but in mathematics there are many ways of measuring the distance between things.

Mathematics is sometimes thought to be a world of dense, dry formulae and esoteric logic, but its structures, especially when paired with modern computing, can generate images of arresting complexity like the one above. The goal of this article is to introduce and explore these images, which arise from attempts to visualise a notion of distance on the integers called Hamming distance.

A distance function assigns a non-negative number to any pair of objects to serve as a measure of how far apart they are. In order to qualify as a distance, such an assignment needs three key features. First, the distance from an object to itself is zero. Second, the distance from object $x$ to object $y$ is always the same as the distance from object $y$ to object $x$. Finally, a path from one object to another that goes through a third is never shorter than the direct path between the two objects.

More formally, if we denote the distance from $x$ to $y$ by $D(x,y)$, then for any object $z$, $$D(x,y)\leq D(x,z)+D(z,y).$$ In what follows, we will consider two different ways of measuring the distance between positive integers.

Euclidean distance and Hamming distance

The most common way to measure the distance between two numbers is using Euclidean distance, with which you may already be familiar. Given two numbers $x$ and $y$, the Euclidean distance between them, expressed as $E(x,y)$, is simply $\vert x-y\vert$.

In the mid-twentieth century, the American mathematician Richard Hamming developed the Hamming distance to measure the distance between sequences of zeros and ones by counting the number of positions in which the sequences differ, a measure that has the three features necessary for a distance. So, for example, the Hamming distance between 10110 and 11110 is 1 as they only differ in the second position from the left—these strings are close.

Working in the early days of computer science, Hamming used this distance measure in his analysis of the effectiveness of error detection and correction in the transmission of messages encoded by strings of zeros and ones. The number of errors an encoding could correct was related to how ‘spread out’ the space of code words was as measured by Hamming distance. Hamming distance can also be thought of as a distance on the integers by using binary representations.

For example, \begin{align*} 22 & = 1 {\color{gray}\times 2}^4 + 0 {\color{gray}\times 2}^3 + 1 {\color{gray}\times 2}^2 + 1 {\color{gray}\times 2}^1 + 0 {\color{gray}\times 2}^0 = 10110_2,\\ 30 & = 1 {\color{gray}\times 2}^4 + 1 {\color{gray}\times 2}^3 + 1 {\color{gray}\times 2}^2 + 1 {\color{gray}\times 2}^1 + 0 {\color{gray}\times 2}^0 = 11110_2. \end{align*} Here, the subscript $2$ indicates that the number is in base 2 rather than base 10. Writing $H(x,y)$ for the Hamming distance between two positive integers $x$ and $y$, $H(22,30)=1$ because the binary representations of 30 and 22 differ in one position. Of course, the Euclidean distance is $E(22,30) = \vert 22-30\vert=8$.

The binary representation of the number six, $110_2$, has only three digits, but we can measure the distance from 6 to a number like 22 whose binary representation has five digits by padding with extra zeros on the left, which has no effect on the underlying number. So $6 = 110_2=00110_2$, and \[ H(6,22) = H(00110_2, 10110_2) = 1. \] Hamming distance clearly measures distance between positive integers quite differently than the standard Euclidean distance does. For example, $H(22,25)=4$, so 22 is much further from 25 than it is from 6 as measured by Hamming distance, but 22 is much closer to 25 than to 6 on the number line. While we can ‘see’ the Euclidean distance between two numbers in their separation on the number line, it is not immediately clear how or whether we can visualise Hamming distance.

Euclidean distance in a square

Euclidean distance visualised in a square. If $E(i,j)=E(i’,j’)$ then $(i,j)$ and $(i’,j’)$ are the same colour; cells with $E(i,j) =16$ are outlined.

Distance is a function of two variables, so let us try to visualise $E(i,j)$ and $H(i,j)$ as the pair $(i,j)$ ranges over a grid of integer pairs. We’ll define $B_n$ to be the set of positive integers whose binary representation contains $n$ or fewer digits, so ${B_n = \left\{ 0,1,\dots, 2^n-1\right\}}$.

Our first strategy to visualise Euclidean and Hamming distance is to use the grid $G_n = \{(i,j)\mid i,j\in B_n \}$ as our canvas and give each different value of $E(i,j)$ a different colour. For Euclidean distance, this gives a fairly simple picture. Points $(i,j)$ that satisfy $E(i,j)=k$ lie either on the line $y=x+k$ or $y=x-k$, and so the points whose coordinates are at Euclidean distance $k$ consist of two parallel lines. On the right, the squares are $128\times 128$ cells, with the cell at position $(i,j)$ corresponding to that point in the grid.

While this picture is fairly simple, there are some features worth noting. First, the image is symmetric about the line $y=x$ because $E(x,y) = E(y,x)$, a symmetry that would be present for any distance measure. Second, the image is unchanged if we translate along the line $y=x$ because for any $z$, \begin{equation} \label{EuclideanSymmetry}\tag{?} E(x+z, y+z) = E(x,y). \end{equation}

Hamming distance in a square

Using the same strategy to visualise Hamming distance produces more interesting images. The picture below shows a few colourings of the $128 \times 128$ grid $G_7$ using different values of the Hamming distance between cell coordinates. Colouring all the points in the grid $G_9$ according to the Hamming distance between their coordinates gives the image at the start of the article.

One thing to notice is that there are only $n$ possible values for the Hamming distance between two points in $B_n$, so there are only $n$ colours used in the grid, whereas there are $2^n$ possible values for the Euclidean distance between two such points. What is interesting about this picture is the nested structure of the grids $G_n$—the image is a fractal in that the same patterns recur at progressively smaller scales.

The fractal looks like a quilt made of squares of similar structure. Moving from a point $(i,j)$ in some sub-square of the grid to a similarly positioned point in another sub-square involves translating one or both components by a power of two. To explore this, let’s use the notation $x+A$ for the set of numbers  in the set $A$ shifted by $x$. So formally, $x+A = \{x+a\mid a\in A \}$, and, for example, $3+\{8,9,10\} = \{11,12,13\}$. This notation allows us to recognise $B_{n}$ as consisting of $B_{n-1}$ together with $2^{n-1} + B_{n-1}$. For example: \[ B_2 = \left\{ 0,1,2,3 \right\} \quad \textrm{and} \quad B_3 = \left\{ 0,1,2,3,0+2^2, 1+2^2, 2+2^2, 3+2^2 \right\}. \] This means that the grid $G_{n}$ is built from four quadrants that are shifts of $G_{n-1}$ (depicted below right).

If $i\in B_{n-1}$, then the binary representation of $i+2^{n-1}$ is identical to that of $i$ except for having a 1 in the $2^{n-1}$th place instead of a 0. It follows that if $j$ is also in $B_{n-1}$, then $i+2^{n-1}$ and $j$ differ in all the same places $i$ and $j$ do, with an additional difference in the $2^{n-1}$th place. If, for example, $i=01101_2$, $j=00111_2$ where $i,j\in B_5$, then $i+2^5=101101_2$. Stated more precisely: \begin{equation} \label{HammingShiftEquation}\tag{⭐} H(i+2^{n-1}, j) = H(i,j) + 1. \end{equation} This means that the cells in the lower right quadrant will have a colour value of exactly one more than the cell in the corresponding position in the lower left quadrant. A similar calculation shows that \begin{equation} \label{HammingShiftEquation2}\tag{?} H(i, j+2^{n-1}) = H(i,j) + 1. \end{equation} In a similar way, the upper left quadrant has the same relationship to the lower left quadrant as the lower right quadrant does. In particular, the upper left and lower right quadrants have identical colouring. If $i,j\in B_{n-1}$, then $i+2^{n-1}$ and $j+2^{n-1}$ both have a 1 in the $2^{n-1}$th place and differ in precisely the same places as $i$ and $j$. If we again take $i=01101_2$, $j=00111_2\in B_5$, then $i+2^5=101101_2$ and $j+2^5=100111_2$. That is, \begin{equation} \label{HammingShiftEquation3}\tag{?} H(i+2^{n-1}, j+2^{n-1}) = H(i,j). \end{equation} This means the colouring of the upper right block will be identical to that of the lower left block. Since this block structure holds for $n=1,2,\dots$, we can build the Hamming fractal starting with $G_1$. The first few steps are shown below:

The nested structure illustrated here causes the fractal nature of the grids $G_n$ to become increasingly apparent as $n\to \infty$. For larger values of $n$, the images contain finer detail and more complex self-similarity. In fact,  Equations (⭐) to  (?) which cause the structure in these images, have generalisations that involve a type of addition called the XOR sum.

The block structure and XOR sums

Hamming distance counts the number of positions in which the binary representations of $i$ and $j$ differ and is closely related to the binary operation of XOR addition. The XOR sum of two natural numbers $i$ and $j$, which we will denote $i\oplus j$, is the natural number whose binary representation has a 1 in any position where the binary representations of $i$ and $j$ differ and a 0 in any position where they are the same. For example, \[ \begin{array}{l l | l l} & 61 & & 111101_2 \\ \oplus & 15 & \oplus & 001111_2 \\ \hline & 50 & & 110010_2 \end{array} \] If we use the notation $\Vert i \Vert$ for the number of ones in the binary representation of $i$, then $\Vert i \Vert = H(0,i)$. The binary representation of $i\oplus j$ has as many 1s as positions where the binary representations of $i$ and $j$ differ, so $H(i,j) = \Vert i\oplus j \Vert$. Because the binary representation of $2^{n-1}$ contains all zeros except for a one in the $2^{n-1}$ position, for any $i$, $i\oplus 2^{n-1}$ will have an identical binary representation to $i$ except in the $2^{n-1}$ position, where it will differ.

Another way of thinking of the block structure in the images in the previous section is in terms of the $\oplus$ operation. If $i,j\in B_{n-1}$, so both $i$ and $j$ have zeros to the left of the $2^{n-2}$th place in their binary representations, then adding $2^{n-1}$ to either number affects their binary representations only by adding a one in the $2^{n-1}$th place. That is, equations (⭐) and (?) can be generalised if $i+2^{n-1}$ is replaced by $i\oplus 2^{n-1}$, so that it becomes \[ \Vert (i\oplus 2^{n-1}) \oplus j \Vert = \Vert i\oplus j \Vert+1\quad \textrm{and} \quad \Vert i \oplus (j\oplus2^{n-1}) \Vert =\Vert i\oplus j \Vert+1. \] Moreover equation (?) generalises to become $\Vert (i\oplus2^{n-1})\oplus (j\oplus2^{n-1}) \Vert =\Vert i+j \Vert$.

Equations (⭐) to (?), as well as giving rise to this nested structure, can also be generalised using the XOR sum to explain more intricate symmetries of this image. Suppose the numbers $i$ and $j$ agree at some position of their binary expansions like $i =01\mathbf{1}01_2$ and $j=10\mathbf{1}10_2$, which agree in the third position. Then ‘$\oplus$-ing’ the same number to both doesn’t change this agreement. If, for example, $a=10100_2$, then $i\oplus a = 11\mathbf{0}01_2$ and $j\oplus a = 00\mathbf{0}11_2$ both also agree in this position.

If, on the other hand, $i$ and $j$ disagree at the some position of their binary expansions like $i =01\mathbf{0}01_2$ and $j=10\mathbf{1}10_2$, which disagree in the third position, then ‘$\oplus$-ing’ the same number to both doesn’t change this disagreement either. Here, $i\oplus a = 11\mathbf{1}01_2$ and $j\oplus a = 00\mathbf{0}11_2$ both also disagree in this position. Thus, the binary expansions of $i\oplus a$ and $j \oplus a$ differ in precisely the same positions as the binary expansions of $i$ and $j$, so \begin{equation} \label{HammingSymmetry}\tag{?} H(i\oplus a, j\oplus a) = H(i,j). \end{equation} Comparing this to equation (?), we see that the operation $\oplus$ is to Hamming distance much as the operation of ordinary addition is to Euclidean distance.

Visualisations on a circle

Connect $i$ and $j$ in $B_4$ if $H(i,j)=2$.

We can get an alternative visualisation by identifying the points of $B_n$ with equally spaced points around a circle, and connecting points that are a given distance apart.

We place the number 0 at the three o’clock position on the circle and spread the numbers $0,1,\dots, 2^n-1$ evenly around the circle anticlockwise. If we connect points that correspond to numbers that are Hamming distance $k$ from one another, we get some interesting images. The image on the right corresponds to $n=4$ and $k=2$ and the image below to $n=6$ and $k=3$.

Connect $i$ and $j$ in $B_6$ if $H(i,j)=3$.

The relationship in equation (?) illuminates many symmetries of these images. If we ‘$\oplus$-shift’ all the points on the circle, that is, if we move every vertex $i$ to the vertex $i\oplus a$ for some $a$, then we don’t change any of the connections because such a shift doesn’t change Hamming distance.

For example, if $a=2^n-1$, the binary representation of $a$ consists of $n$ ones, and the binary representation $x\oplus a$ has ones precisely where that of $x$ has zeros, and has zeros precisely where that of $x$ has ones. That is, $x\oplus a = a-x$, and the image is symmetric with respect to the interchange of $x$ and $a-x$, which amounts to a reflection over a line through the centre of the circle.

In the image (below left) purple arrows connect each point $x$ with the point $a-x$. Choosing a different value of $a$, say $a=3$, then interchanging $x$ and $x\oplus a$ corresponds to a more subtle symmetry of the graph as shown on the right.

Symmetry with respect to swapping $x$ with $x\oplus (2^n-1)=15-x$ (left), and $x$ with $x\oplus 3$ (right).

Where can we go from here?

We have unlocked some, but by no means all of the mysteries presented by images like the Hamming fractal, and circle visualisations. There are many symmetries left to uncover, and fascinating questions to ask about these images. Why is there a white circle at the centre? How is the size of this circle related to $n$ and the chosen Hamming distance? Why does there seem to be more white space toward the centre of the circle pictures? What can be said about the structure of the white space around the centre circle, for example the eight ovals surrounding it?

While it is not at all obvious from the circle picture for $n=4$, $k=2$, this graph actually has two connected components shown on the right. Is it always the case for these graphs? If not, under what conditions is it the case? Can the number of connected components be described in terms of the numerical properties of the vertex numbers they contain? When do these graphs have other interesting properties; for example, when are they bipartite? Just two examples to illustrate the variety of circle virtualisations are below.

The circle visualisations for $B_7$ if $H(i,j)=5$ (left), and $B_8$ if $H(i,j)=2$ (right).

The Wolfram demonstration projects by Enrique Zeleny (2014) and Chris Boucher (2020) are freely available and offer a platform for quickly generating some of these images. I hope you share my enthusiasm for these pictures and will feel inspired to explore them yourself.

Against all the odds, your plan has worked. Your thief snuck in ahead of the team and got a surprise backstab, the paladin’s shield deflected the would-be deadly dragon’s fire breath and a well-aimed wizard’s frostbolt took out the columns of the building. You move your dwarven barbarian in for the killing blow. The trapped red dragon looks up with anger in its eyes. You know, all that stands between this creature and death is a single good hit of your axe. Even with all the work from the other players, the difficulty class of landing a hit on this creature is 16, meaning you will only hit it with a roll of 16 or higher on a d20 (a 20-sided die for those not in the know). That’s a $1/4$ chance of hitting.

Luckily, there is one last hope. The druid spent their turn giving you the help action. This means your next attack has advantage. Advantage allows you to now roll two d20s and choose the highest of those two values. This is obviously helpful, but what are the new odds that you will be able to give this dragon a one-way ticket to the afterlife?

Continue reading →

Mathematics is my secret—
                                 my secret weakness.
I feel like a stubborn, helpless fool in the middle of a problem.
          Trapped and crazed.
          Also, thrilled.
I’m gnawing on a bone and I fear
          for anyone who comes near and tries
          to make me stop.
I growl. I refuse to drop that bone.
I am dogged—
did I mention that math is funny too?
It’s hilarious how much time I secretly waste on it,
when there are more productive things to do,
like walk my dog,
          fold my laundry,
                    or finish my actual homework.

No one in my family thinks all this math is healthy.
Get some sleep.
Here, eat something.
Go outside for some fresh air!
And they’re probably right.
But here’s another secret:
                                                     I don’t care
About rest or nutrition or any of it.
blah
         blah
                  blah
I’m not even really listening.
Too busy gnawing away.

On a different day
Back out in the blaring, glaring, glittering world
I feel unfurled and chatty
Eager for random conversations and observations
Nosy for other people’s secrets, which surely must be
as weird and wild as the ones that define the inside of me.
And I notice
something fascinating
exasperating
in all the talking
                                  talking
                                                 talking.

Here’s what a lot of people say:

I’m just not a math person.
          Insert shrug and sheepish smile.
I can barely figure out the tip.
Wait, you take extra math classes? What for?
What do you mean, just for fun?
Wow, you must be a genius or something.

Here’s what no one says:

I’m just not a words person.
          Insert shrug and sheepish smile.
I can barely read a sentence.
Wait, you read an entire book this weekend? What for?
What do you mean, just for fun?
Wow, you must be a genius or something.

I feel silly being mistaken for a genius,
when I’m really just a nerd.
Struggling,
          stumbling,
                    pushing,
                              reaching
                              for more
                    of something
          that makes
me feel
mesmerised and uncomfortable,
lost,
hopeless,
hopeful,
real.

I’m sure some of you reading this may know about topology vaguely as “that one where the doughnut is the same as the mug”. And you would be right. In essence, topology is maths after you have forgotten what distance is, meaning that space is squishier than we’re used to. Then, the only defining feature of a mug is the hole between its body and its handle and the only defining feature of a doughnut is… well, its hole. A lot of topology is about saying whether one shape is the same as another (such as doughnuts and mugs).

Today we’re going to be going a step further; to ask when two shapes look the same ‘up close’, despite not necessarily being the same overall. For example, if we zoom in closely on any part of a circle, it will look like a line. However these shapes are not the same, since a circle is not a line. We’ll discuss this in more detail soon.

The question I want to answer is whether there is a way to intuitively create a shape that ‘covers’ another. I put it to you that there is. If shape $A$ covers a base shape $B$, there must be a way to map $A$ to $B$ such that

• the base $B$ is entirely covered by $A$ (ie this is a surjective map); and
• by zooming on any small patch of $B$, the map looks like the identity map.

The infinite plane covers the torus: the colouring has been added to illustrate how the covering map works.

For instance, we can say that a plane covers a torus. To visualise this, imagine taking the plane, rolling it up into a cylinder, then rolling down the edges of the cylinder, sort of like rolling down a sock. As the edges loop round, the resulting surface is—lo and behold—a torus! This way, every part of the torus is covered (satisfying surjectivity), and every small part of the plane looks like the surface of a torus if you zoom in close enough.

Another example of this is the circle. Any circle can cover another circle by winding round it some number of times. You can imagine that this is like wrapping an elastic band around your finger. Above on the right we have a circle mapping continuously onto a circle a third of its length.

But we can think bigger; the real number line can cover a circle by twisting it round into a helix. This satisfies surjectivity since every part of the circle is covered, and, as mentioned above, every part of the helix looks like a circle if you zoom in close enough. However, a finite interval cannot cover a circle since if we zoom in on the interval’s endpoints, we can’t find any point on the circle that looks like this.

Don’t worry though, our bounded interval can still play with other bounded intervals.

Infinity undercover

So, we’ve seen how to cover lines and circles, but how does this covering business work when lines intersect? The infinity symbol, $\infty$—since I always like to be able to call a symbol something in my head, we’ll pronounce this ‘infty’—has two edges intersecting at one vertex.

This is an example of a graph: a shape consisting of vertices and edges. Each vertex in a graph has a valency, ie the number of ‘arms’ it has. So if two edges meet at a vertex, they become four ‘arms’, and the intersection is a point with valency 4.

Now we can reinterpret the way we think about covers; a circle cannot cover infty since zooming in on the infty at the intersection we have a point where four lines join together, whereas no point on the circle has this property. One idea is to cover this with another infty, using the identity map. But, to make other covers, let’s look at more graphs that are 4-valent at each vertex.

To make sure that we are not mixing up the two arms of each edge, let’s give each edge a direction so we can easily differentiate the ‘source’ end of the edge and the ‘target’… end. Also colouring the edges is a simple way of making sure that we distinguish the two different edges.A constraint for a graph to cover infty is that every vertex in the cover must have two red arrows (one source, one target) and two blue arrows (likewise). Let’s call the graph with arrows a directed graph, or a digraph for short. An example of such a cover is this:

From this we get infty by double-looping the blue-edged loop so that the two vertices end up on top of each other, with red edge on red edge and blue edge on blue.

An example of a case where this does not hold is on the right. This does not work for a few reasons. You might have noticed that its vertex has too many arms, or that there is more than one blue arrow pointing towards/away from the vertex. Is there some other way to colour and direct the graph to make it a cover of infty? Well, whichever colouring we choose, we will always have more than two of one colour. So sadly, I topologise: this graph is not destined to cover infinity.

Inftys all the way down

Another cover is the infinite grid. A way to conceptualise this map is thinking similarly to the example of the plane rolling up to make the torus. First we roll the graph into a vertical cylinder, then we roll the edges of this cylinder down so that each rung is mapped onto the same one.  Up until this point, taking a red path then a blue path in each cover will end up at the same point as taking a blue path and then red (try this out on the infinite grid). But can we break this pattern?

Here we find a special case I call the fractal cross, where the cover is so intricate that the path between any two vertices is unique. Try starting at any vertex on the graph, and mark out the path travelling red then blue. Now go back and do the same with blue then red. Your destination depends on the order of your steps! I call this the fractal cross because it is infinitely detailed—like a fractal. The fractal cross covers infty in a similar way to the infinite grid. This, *drum roll please*, is the largest cover of infty. More precisely, it covers every other cover of infty and nothing else covers it.

From cross to cover

All covers of infty can actually be derived from the fractal cross. As an example, if we take the central blue line of the graph, we can first wrap it around itself in the way that a line covers a circle; and then glue together all the branching red arms, and we will get this cover:

By repeatedly gluing and warping the fractal cross we can find more covers, and eventually get down to infty.

For instance, let’s again take a blue-edged line on the fractal cross, but this time wind it around until every third blue edge in the line is glued together creating a loop. Now do the same with a red-edged line intersecting this loop. Next glue the vertices of the loops together one by one. As you can see, this forms a triangle with vertices intersecting a circle. Finally this graph with six edges collapses down onto infty.

Illuminati confirmed?

Every cover we’ve looked at so far has been 4-valent; in fact we have now recognised the 4-valency of every vertex in the cover as a necessary condition to be a cover. But is it a sufficient condition? If we have a 4-valent graph, will it necessarily cover infinity?

We can generate complex, and often infinite covers of infty, all just by checking all our rules are satisfied. In this way, we have a surprising amount of flexibility to build up such a cover. You might enquire further; how much flexibility? Can we explore some artistic licence?

For example, would a Celtic knot cover infty? A Celtic knot is a traditional weaving pattern, which is drawn like a rope tied in a knot, with the notable property that the two rope ends are stuck together. If we shine a torch on such a knot and take a picture of its shadow, we can imagine that the resulting silhouette is a graph. All vertices of this shadow graph will be 4-valent since it is the junction of two lines crossing. So… does this cover infty?

A beautiful Celtic knot designed by Leonardo da Vinci is shown on the right. Below, I have drawn the digraph associated with the centre piece, verifying both that it indeed covers infty, and that I have far too much time on my hands. In fact, we find that a Celtic knot’s shadow will always qualify as a cover of infty. This is to say that there will always be a digraph of the knot satisfying the requirements—each vertex having a blue source, blue target, red source, and red target.

It is fascinating that an artistic piece could relate to such a mathematical idea as a topological cover, and all of this stemming from the theory of a torus being considered topologically identical to a mug—who would have thought? The realisation that all knots (apart from the circle) cover infty is non-trivial and—in my opinion—really cool. However, as cool as topological space is, just make sure you don’t try pouring any tea in your doughnut!