Skip to content →

Author: lievenlb

Lockdown reading : Penumbra

In this series I’ll mention some books I found entertaining, stimulating or comforting during these Corona times. Read them at your own risk.



It’s difficult to admit, but Amazon’s blurb lured me into reading Mr. Penumbra’s 24-Hour Bookstore by Robin Sloan:

“With irresistible brio and dazzling intelligence, Robin Sloan has crafted a literary adventure story for the 21st century, evoking both the fairy-tale charm of Haruki Murakami and the enthusiastic novel-of-ideas wizardry of Neal Stephenson or a young Umberto Eco, but with a unique and feisty sensibility that’s rare to the world of literary fiction.” (Amazon’s blurb)

I’m a fan of Murakami’s later books (such as 1Q84 or Killing Commendatore), and Stephenson’s earlier ones (such as Snow Crash or Cryptonomicon), so if someone wrote the perfect blend, I’m in. Reading Penumbra’s bookstore, I discovered that these ‘comparisons’ were borrowed from the book itself, leaving out a few other good suggestions:

One cold Tuesday morning, he strolls into the store with a cup of coffee in one hand and his mystery e-reader in the other, and I show him what I’ve added to the shelves:

Stephenson, Murakami, the latest Gibson, The Information, House of Leaves, fresh editions of Moffat” – I point them out as I go.

(from “Mr Penumbra’s 24-Hour Bookstore”)

This trailer gives a good impression of what the book is about.

Why might you want to read this book?

  • If you have a weak spot for a bad ass Googler girl and her tecchy wizardry.
  • If you are interested in the possibilities and limitations of Google’s tools.
  • If you don’t know what a Hadoop job is or how to combine it with a Mechanical Turk to find a marker on a building somewhere in New-York.
  • If you never heard of the Gerritszoon font, preinstalled on every Mac.

As you see, Google features prominently in the book, so it is kind of funny to watch the author, Robin Sloan, give a talk at Google.

Some years later, Sloan wrote a (shorter) prequel Ajax Penumbra 1969, which is also a good read but does not involve fancy technology, unless you count tunnel construction among those.



Read it if you want to know how Penumbra ended up in his bookstore and how he recovered the last surviving copy of the book “Techne Tycheon”.

More information (together with reading suggestions) can be found at Mr Penumbra’s 24-hour bookstore: a reading map.

Leave a Comment

The strange logic of subways

“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!).

Leave a Comment

Conway’s musical sequences (2)

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.

Leave a Comment