Category: geometry

The strange logic of subways

Published March 5, 2021 by lievenlb

“A subway is just a hole in the ground, and that hole is a maze.”

“The map is the last vestige of the old system. If you can’t read the map, you can’t use the subway.”

Eddie Jabbour in Can he get there from here? (NYT)

Sometimes, lines between adjacent stations can be uni-directional (as in the Paris Metro map below in the right upper corner, 7bis). So, it is best to view a subway map as a directed graph, with vertices the different stations, and directed arrows when there’s a service connecting two adjacent stations.

Aha! But, directed graphs form a presheaf topos. So, each and every every subway in the world comes with its own logic, its own bi-Heyting algebra!

Come again…?

Let’s say Wally (or Waldo, or Charlie) is somewhere in the Paris metro, and we want to find him. One can make statements like:

$P$ = “Wally is on line 3bis from Gambetta to Porte des Lilas.”, or

$Q$ = “Wally is traveling along line 11.”

Each sentence pinpoints Wally’s location to some directed subgraph of the full Paris metro digraph, let’s call this subgraph the ‘scope’ of the sentence.

We can connect such sentences with logical connectives $\vee$ or $\wedge$ and the scope will then be the union or intersection of the respective scopes.

The scope of $P \vee Q$ is the directed subgraph of line 11 (in both directions) together with the directed subgraph of line 3bis from Gambetta to Porte des Lilas.

The scope of $P \wedge Q$ is just the vertex corresponding to Porte des Lilas.

The scope of the negation $\neg R$ of a sentence $R$ is the subgraph complement of the scope of $R$, so it is the full metro graph minus all vertices and directed edges in $R$-scope, together with all directed edges starting or ending in one of the deleted vertices.

For example, the scope of $\neg P$ does not contain directed edges along 3bis in the reverse direction, nor the edges connecting Gambetta to Pere Lachaise, and so on.

In the Paris metro logic the law of double negation does not hold.

$\neg \neg P \not= P$ as both statements have different scopes. For example, the reverse direction of line 3bis is part of the scope of $\neg \neg P$, but not of $P$.

So, although the scope of $P \wedge \neg P$ is empty, that of $P \vee \neg P$ is not the full digraph.

The logical operations $\vee$, $\wedge$ and $\neg$ do not turn the partially ordered set of all directed subgraphs of the Paris metro into a Boolean algebra structure, but rather a Heyting algebra.

Perhaps we were too drastic in removing all “problematic edges” from the scope of $\neg R$ (those with a source or target station belonging to the scope of $R$)?

We might have kept all problematic edges, and added the missing source and/or target stations to get the scope of another negation of $R$: $\sim R$.

Whereas the scope of $\neg \neg R$ always contains that of $R$, the scope of $\sim \sim R$ is contained in $R$’s scope.

The scope of $R \vee \sim R$ will indeed be the whole graph, but now $R \wedge \sim R$ does no longer have to be empty. For example, $P \wedge \sim P$ has as its scope all stations on line 3bis.

In general $R \wedge \sim R$ will be called the ‘boundary’ $\partial(R)$ of $R$. It consists of all stations within $R$’s scope that are connected to the outside of $R$’s scope.

The logical operations $\vee$, $\wedge$, $\neg$ and $\sim$ make the partially ordered set of all directed subgraphs of the Paris metro into a bi-Heyting algebra.

There’s plenty more to say about all of this (and I may come back to it later). For the impatient, there’s the paper by Reyes and Zolfaghari: Bi-Heyting Algebras, Toposes and Modalities.

Right now, I’m more into exploring whether this setting can be used to revive an old project of mine: Heyting Smullyanesque problems (btw. the algebra in that post is not Heyting, oops!).

Conway’s musical sequences (2)

Published March 3, 2021 by lievenlb

A Conway musical sequence is an infinite word in $L$ and $S$, containing no two consecutive $S$’s nor three consecutive $L$’s, such that all its inflations remain musical sequences.

We’ve seen that such musical sequences encode an aperiodic tiling of the line in short ($S$) and long ($L$) intervals, and that such tilings are all finite locally isomorphic.

But, apart from the middle $C$-sequences (the one-dimensional cartwheel tilings) we gave no examples of such tilings (or musical sequences). Let’s remedy this!

Take any real number $c$ as long as it is not an integral combination of $1$ and $\tfrac{1}{\tau}$ (with $\tau$ the golden ratio) and assign to any integer $a \in \mathbb{Z}$ a tile
\[
P_c(a) = \begin{cases} S \\ L \end{cases} ~\text{iff}~\lceil c+(a+1)\frac{1}{\tau} \rceil – \lceil c+a \frac{1}{\tau} \rceil = \begin{cases} 0 \\ 1 \end{cases} \]
(instead of ceilings we might have taken floors, because of the restriction on $c$).

With a little bit of work we see that the deflated word determined by $P_c$ is again of this type, more precisely $def(P_c) = P_{-(c-\lfloor c \rfloor)\frac{1}{\tau}}$. But then it also follows that inflated words are of this type, meaning that all $P_c$ define a musical sequence.

Let’s just check that these sequences satisfy the gluing restrictions. If there is no integer between $c+a\tfrac{1}{\tau}$ and $c+(a+1)\tfrac{1}{\tau}$, because $2 \tfrac{1}{\tau} \approx 1.236$ there must be an interval in the preceding and the following $\tfrac{1}{\tau}$-interval, showing that an $S$ in the sequence has an $L$ on its left and right, so there are no two consecutive $S$’s in the sequences.

Similarly, if two consecutive $\tfrac{1}{\tau}$-intervals have an integer in them, the next interval cannot contain an integer as $3 \tfrac{1}{\tau} \approx 1.854 < 2$.

Now we come to the essential point: these sequences can be obtained by the cut-and-project method.

Take the line $L$ through the origin with slope $\tfrac{1}{\tau}$ and $L^{\perp}$ the line perpendicular it.

Consider the unit square $H$ and $H_{\vec{\gamma}}=H + \vec{\gamma}$ its translation under a shift vector $\vec{\gamma}=(\gamma_x,\gamma_y)$ and let $\pi$ (or $\pi^{\perp}$) be the orthogonal projection of the plane onto $L$ (or onto $L^{\perp}$). One quickly computes that
\[
\pi(a,b) = (\frac{\tau^2 a + \tau b}{1+\tau^2},\frac{\tau a + b}{1+\tau^2}) \quad \text{and} \quad
\pi^{\perp}(a,b) = (\frac{a-\tau b}{1+\tau^2},\frac{\tau^2b-\tau a}{1+\tau^2}) \]
In the picture, we take $\vec{\gamma}=(c,-\tau c)$.

The window $W$ will be the strip, parallel with $L$ with basis $\pi^{\perp}(H_{\vec{\gamma}})$.

We cut the standard lattice $\mathbb{Z}^2$, of all points with integer coordinates in the plane, by retricting to the window $\mathcal{P}=\mathbb{Z}^2 \cap W$.

Next, we project $\mathcal{P}$ onto the line $L$, and we get a set of endpoints of intervals which divide the line $L$ into short intervals of length $\tfrac{1}{\sqrt{1+\tau^2}}$ and long intervals of length $\tfrac{\tau}{\sqrt{1+\tau^2}}$.

For $(a,b) \in W$, the interval will be short if $(a,b+1) \in W$ and long if $(a+1,b) \in W$.

Because these intervals differ by a factor $\tau$ in length, we get a tiling of the line by short intervals $S$ and long intervals $L$. It is easy to see that they satisfy the gluing restrictions (remember, no two consecutive short intervals and no three consecutive long intervals): the horizontal width of the window $W$ is $1+\tau \approx 2.618$ (so there cannot be three consecutive long intervals in the projection) and the vertical width of the window $W$ is $1+\tfrac{1}{\tau} = \tau \approx 1.618$ so there cannot be two consecutive short intervals in the projection.

Ready for the punchline?

The sequence obtained from projecting $\mathcal{P}$ is equal to the sequence $P_{(1+\tau^2)c}$. So, we get all musical sequences of this form from the cut-and-project method!

On $L^{\perp}$ the two end-points of the window are
\[
\begin{cases}
\pi^{\perp}(c+1,-\tau c) = (\frac{(1+\tau^2)c+1}{1+\tau^2},- \tau \frac{(1+\tau^2)c+1}{1+\tau^2}) \\
\pi^{\perp}(c,-\tau c+1) = (\frac{(1+\tau^2)c-\tau}{1+\tau^2},-\tau \frac{(1+\tau^2)c-\tau}{1+\tau^2})
\end{cases} \]
Therefore, a point $(a,b) \in \mathbb{Z}^2$ lies in the window $W$ if and only if
\[
(1+\tau^2)c-\tau < a-\tau b < (1+\tau^2)c+1 \] or equivalently, if \[ (1+\tau^2)c+(b-1)\tau < a < (1+\tau^2)c+b \tau + 1 \] Observe that \[ \lceil (1+\tau^2)c + b\tau \rceil - \lceil (1+\tau^2)c+(b-1)\tau \rceil = P_{(1+\tau^2)c}(b-1) + 1 \in \{ 1,2 \} \] We separate the two cases: (1) : If $\lceil (1+\tau^2)c + (b+1)\tau \rceil - \lceil (1+\tau^2)c+b \tau \rceil =1$, then there must be an integer $a$ such that $(1+\tau^2)c +(b+1) \tau -1 < a < (1+\tau^2) b+1$, and this forces $\lceil (1+\tau^2)c + (b+2)\tau \rceil - \lceil (1+\tau^2)c+(b+1)\tau \rceil =2$. With $b_i = (1+\tau^2)c+(b+i)\tau$ and $d_i = b_i+1$ we have the situation

and from the inequalities above this implies that both $(a+1,b+1)$ and $(a+1,b+2)$ are in $W$, giving a short interval $S$ in the projection.

(2) : If $\lceil (1+\tau^2)c + (b+1)\tau \rceil – \lceil (1+\tau^2)c+b \tau \rceil =1$, then there must be an integer $a$ such that $(1+\tau^2)c+b \tau < a < (1+\tau^2)cv + (b+1)\tau -1$, giving the situation

giving from the inequalities that both $(a+1,b+1)$ and $(a+2,b+1)$ are in $W$, giving a long interval $L$ in the projection, finishing the proof.

Conway’s musical sequences

Published March 2, 2021 by lievenlb

Before we’ll come to applications of quasicrystals to viruses it is perhaps useful to illustrate essential topics such as deflation, inflation, aperiodicity, local isomorphism and the cut-and project method in the simplest of cases, that of $1$-dimensional tilings.

We want to tile the line $\mathbb{R}^1$ with two kinds of tiles, short ($S$) and ($L$) long intervals, differing by a golden ratio factor $\tau=\tfrac{1}{2}(1+\sqrt{5}) \approx 1.618$.

Clearly, no two tiles may overlap and we impose a gluing restriction: there can be no two consecutive $S$-intervals in the tiling, and no three consecutive $L$-intervals.

The code of a tiling is a doubly infinite word in $S$ and $L$ such that there are no two consecutive $S$’s nor three consecutive $L$’s. For example
\[
\sigma = \dots LSLLSLS\underline{L}LSLLSL \dots \]
We underline one tile to distinguish the sequence from shifts of it.

Conway’s musical sequences will be special codes (or tilings), allowing for the inverse operations of inflation and deflation, terms coined by John Conway in relation to Penrose tilings. The musical sequences are important to understand Conway’s worms (sometimes called “wormholes”) which are strings of Long and Short bow ties in a Penrose tiling, and to measure the distances between Amman bars. In fact, many of the properties of Penrose tilings and $3$-dimensional quasicrystals (for example, local isomorphism) have their counterparts for tilings having a musical sequence as code.

Conway’s investigations of Penrose tiles held up work on the ATLAS-project and caused some problems at home:

“In pursuing his investigations, he unsurped some of his wife Eileen’s territory, covering the dining table with an infinite nuisance of tiles. He cut them out himself, causing his right hand to hurt with cramps for days. To Eileen’s dismay, he studied the dining table mosaic for a year, relegating family meals to the kitchen and prohibiting dinner parties.”

From “Genius at Play – The curious mind of John Horton Conway” by Siobhan Roberts

Let’s investigate inflation and deflation of these tilings.

The point of the golden factor $\tau$ is to allow for deflation. That is, we can replace a tiling by another one with tiles $S$ and $L$ both a factor $\tfrac{1}{\tau}=\tau-1 \approx 0.618$ smaller than the original tiles. If the original $S$-tile has length $a$ (and the $L$-tile length $\tau a$), then the new tile $S$ wil have length $\tfrac{1}{\tau}a$ and the new $L$-tile length $a$.
We do this by replacing each old $S$-tile by a new $L$-tile, and to break up any old $L$-tile in a new $L$ and new $S$-tile, as $\tau a = a + \tfrac{1}{\tau}a$ (note that $\tau^2=\tau+1$)

To get the code of the deflated tiling we replace each letter $S$ by a letter $L$ and each $L$ by $LS$. The underlined letter will be the first letter of the deflated underlined letter in the original sequence. The deflated sequence of the one above is
\[
def(\sigma) = \dots LSLLSLSLLSL\underline{L}SLSLLSLSLLS \dots \]
and it is easy to see that the deflated tiling satisfies again the gluing condition.

Certain of these tilings (not all!) allow for an inverse to deflation, called inflation, increasing the size of the tiles by a factor $\tau$.

Starting from a tiling we divide each $L$-tile in half and these mid-points will be end-points of the tiles in the new tiling, erasing all endpoints of the original one. The inflated tiling will have two sorts of tiles, a new short one $S$ of length $\tau a$ obtained from the end-half of an original $L$-tile, followed b the start-half of an original $L$-tile, and a new long tile $L$ of length $\tau^2 a = (\tau+1) a$, made of the end-half of an original $L$, followed by an original $S$, followed by the start-half of an original $L$.

We get the code of the inflated tiling by replacing first each $L$ by $ll$ and subsequently replace each word $lSl$ by a letter $L$ and each $ll$ by $S$. An example,
\[
\sigma = \dots LSLLSLSLLSL\underline{L}SLSLLSLSLLS \dots \\
\dots llSllllSllSllllSlll\underline{l}SllSllllSllSllllS \dots \\
inf(\sigma) = \dots (l)LSLLSLS\underline{L}LSLLS(lS) \dots \]

But, the inflated tiling may no longer satisfy the gluing condition. An example
\[
\dots LSLSLSL \dots \mapsto \dots llSllSllSll \dots \mapsto \dots (l)LLL(l) \dots \]

A Conway musical sequence is the code of a tiling $\sigma$ such that all its consecutive inflations $inf^n(\sigma)$ satisfy the gluing condition. For the corresponding Conway tiling $\sigma$ we have that
\[
def(inf(\sigma))=\sigma=inf(def(\sigma)) \]

Let’s construct at least two such Conway tilings (later we’ll see that there are uncountably many). Take $C_n=def^n(LS\underline{L})$ and write it in a special form to highlight symmetries.
\begin{eqnarray*}
C_0 =& (L.S)\underline{L} \\
C_1 =& L(S.L)\underline{L}S \\
C_2 =& LSL(L.S)\underline{L}SL \\
C_3 =& LSLLSL(S.L)\underline{L}SLLS \\
C_4 =& LSLLSLSLLSL(L.S)\underline{L}SLLSLSL
\end{eqnarray*}

The even terms have middle-part $(L.S)$ and the odd ones $(S.L)$. The remaing left and right parts are each others reflexion (or part of it). This is easily seen by induction as are the inclusions
\[
C_0 \subset C_2 \subset C_4 \subset \dots \subset C_{even} \quad \text{and} \quad C_1 \subset C_3 \subset C_5 \subset \dots \subset C_{odd} \]

$C_{even}$ and $C_{odd}$ are special Conway musical sequences, called the middle $C$-sequences, and are each others inflation and deflation. If you are familiar with Penrose tilings, these are the $1$-dimensional counterparts of the cartwheel Penrose tiling (here with the $10$ Conway worms emanating from the center, and with the borders of the first few cartwheels drawn).

A direct consequence of inflation on Conway’s musical sequences is that the corresponding tiling is aperiodic, that is, it has no translation symmetry.

For, inflation only depends on the local configuration of tiles, so if translation by $R$ is a symmetry of a musical sequence $\sigma$ then it is also a symmetry of $inf(\sigma)$, and so also of $inf^n(\sigma)$. But for large $n$ we will have that $R < \tau^n a$ (with $a$ the size of the tiles in $\sigma$). But then a tile in $inf^n(\sigma)$ and its translation by $R$ must overlap which is impossible if $+R$ is a translation symmetry of $inf^n(\sigma)$. Done!

Returning to the middle C-sequences, what was the point of starting with $C_0 = LSL$? Well, it follows directly from the gluing restrictions that any letter in a musical sequence is part of a subword $LSL$ of $\sigma$. But then, every finite subword $W$ of $\sigma$ is also a subword of $C_{2n}$ for some large $n$.

For, let $d$ be the length of the interval corresponding to $W$ and choose $n$ such that $d > \tau^{2n} a$ then the interval of the line corresponding to $W$ is contained in a single tile in $inf^{2n}(\sigma)$ and this tile belongs to a subword $LSL$ of $inf^{2n}(\sigma)$. But then $W$ will be a subword of the $2n$-th deflation of that interval $LSL \subset inf^{2n}(\sigma)$, which is $C_{2n}$.

Or, as Conway would phrase it with respect to Penrose tilings (quote again from Siobhan Roberts’ book)

“Every points is in the cartwheel somewhere. If you jab your finger anywhere, on any point anywhere on teh pattern, you are part of a cartwheel. The whole ting is overlapping cartwheels.”

An immediate consequence is the local isomorphism theorem: Every subword of a musical sequence $\sigma$ appears infinitely many times as subword of any other musical sequence. That is, one cannot distinguish two tilings of the line with musical sequence codes from each other by looking at finite intervals!

The argument is similar to the one above. The finite interval corresponding to the subword lies in a unique tile of $inf^n(\sigma)$ for $n$ large enough. Now, take another musical sequence $\mu$ and consider any of the infinitely many tiles of the same type in $inf^n(\mu)$, then $def^n$ of such a tile will contain the subword in $\phi$.

Another time, we’ll see that musical sequences can be produced by the ‘cut-and-project’-method (what I called the ‘windows’-method before).
This time we will project parts of the standard $2$-dimensional lattice $\mathbb{Z}^2$ onto the line, which is a lot easier to visualise than de Bruijn’s projection from $\mathbb{R}^5$ to produce Penrose tilings or the projection from six dimensional space to harvest quasicrystals.