Ancient xerox technology.

 July 28, 2008 personal

\newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}}

\newenvironment{question}[1][]{\par\textbf{Question (#1).}}{} \newenvironment{theorem}[1][]{\par\textbf{Theorem (#1).}}{} \newenvironment{lemma}[1][]{\par\textbf{Lemma (#1).}}{} \newenvironment{proof}{\textit{Proof.}}{}

The Romans (among others!) wrote in wax with a stylus; the wax was embedded in boards, which were bound together in pairs. If a Roman were to place clay between these boards, could they make a copy of their wax tablet in the clay?

It strikes me as remarkable that coins were minted so long before books were printed—though I guess the motivation behind minting coins and printing books are rather different.


Hyperbolization of Polyhedra

 July 26, 2008 talks mathematics

\newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}}

\newenvironment{question}[1][]{\par\textbf{Question (#1).}}{} \newenvironment{theorem}[1][]{\par\textbf{Theorem (#1).}}{} \newenvironment{lemma}[1][]{\par\textbf{Lemma (#1).}}{} \newenvironment{proof}{\textit{Proof.}}{}

I gave a talk in the Farb and Friends Student Seminar (back in March!) on [1].

This is an awesome paper—well-worth a few words on every blog!

The construction is way easier than you might think. The ingredients:
  • A model space X with a map f : X \to \Delta^n
  • Any simplicial complex K with a nondegenerate (edge-non-collapsing) map K \to \Delta^n (if having a map to \Delta^n seems like a bother, note that the barycentric subdivision K&39; comes with a map to \Delta^n for free).

Let X_J = f^{-1}(J) for J a subcomplex of \Delta^n ; we think of this as decomposing X into pieces resembling a simplex.

Now the construction is easy: replace each simplex in K with a corresponding piece of X . Or more formally, build the fiber product of X and \|K\| over \Delta^n ; this fiber product is denoted by X \tilde{\Delta} K in the paper. From this, we get a natural map f_K : X \tilde{\Delta} K \to K .

The vague upshot is this: features of X translate into features of X \tilde{\Delta} K , while nonetheless preserving features of K . Here are a couple of examples of how assumptions on X lead to consequence for X \tilde{\Delta} K .
  • If X is path-connected, and for each codimension 1 face \alpha of \Delta^n , we have Error:LaTeX failed:
    This is pdfTeX, Version 3.14159265-2.6-1.40.21 (TeX Live 2020/NixOS.org) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./working.tex LaTeX2e <2020-10-01> L3 programming layer <2020-10-05> xparse <2020-03-03> (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/base/article.cls Document Class: article 2020/04/10 v1.4m Standard LaTeX document class (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/base/size12.clo)) (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/preview/preview.sty (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/generic/luatex85/luatex85.sty) (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/preview/prtightpage.def)) (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/amsmath/amsmath.sty For additional information on amsmath, use the `?' option. (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/amsmath/amstext.sty (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/amsmath/amsgen.sty)) (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/amsmath/amsbsy.sty) (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/amsmath/amsopn.sty)) (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/amsfonts/amsfonts.sty) (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/base/fontenc.sty) (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/lm/lmodern.sty) (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/lm/t1lmr.fd) (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/l3backend/l3backend-dvips.def) No file working.aux. Preview: Fontsize 12pt (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/lm/ot1lmr.fd) (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/lm/omllmm.fd) (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/lm/omslmsy.fd) (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/lm/omxlmex.fd) (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/amsfonts/umsa.fd) (/nix/store/2imdihsig4v0b7w0jqh05yl05xky3gx6-texlive-combined-full-2020/share/t exmf/tex/latex/amsfonts/umsb.fd) ! Undefined control sequence. l.11 X_{\alpha} \neq \varnothing Preview: Tightpage -32891 -32891 32891 32891 [1] (./working.aux) ) (see the transcript file for additional information) Output written on working.dvi (1 page, 1772 bytes). Transcript written on working.log.
    , then \pi_1(f_K) : \pi_1(X \tilde{\Delta} K) \to \pi_1(K) is a surjection.
  • If X and K are PL-manifolds, and \dim X_J = \dim J , and \partial X_J = X_{\partial J} , then X \tilde{\Delta} K is a PL-manifold.

[1] M.W. Davis, T. Januszkiewicz, Hyperbolization of polyhedra, J. Differential Geom. 34 (1991) 347–388. http://projecteuclid.org/euclid.jdg/1214447212.


Solutions to Lights Out

 July 21, 2008 personal mathematics

\newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}}

\newenvironment{question}[1][]{\par\textbf{Question (#1).}}{} \newenvironment{theorem}[1][]{\par\textbf{Theorem (#1).}}{} \newenvironment{lemma}[1][]{\par\textbf{Lemma (#1).}}{} \newenvironment{proof}{\textit{Proof.}}{}

I’ll briefly introduce the Lights Out puzzle: the game is played on an n-by-n grid of buttons which, when pressed, toggle between a lit and unlit state. The twist is that toggling a light also toggles the state of its neighbors (above, below, right, left—although, on the boundary, lights have fewer neighbors). All the buttons are lit when the game begins, and the goal is to turn all the lights off.

There are two key observations:

  • toggling a light twice amounts to doing nothing,
  • toggling light A and then light B has the same effect as toggling B and then toggling A .
As a result, the order in which we press the buttons is irrelevant. So to solve the n-by-n puzzle, we just need to know whether a button needs to be pressed. My old website had some pictures I made showing solutions for boards of various sizes—pictures where a white pixel meant “press” and a black pixel meant “don’t press.” I assembled these pictures into a video, showing solutions to the Lights Out puzzle for n \leq 200 :

<%= movie( ‘lights-out.m4v’, 400, 400 ) %>

For as cool as that looks, there’s not much to be discovered (as far as I can tell) from watching these frames flash by. But it does look like about half the buttons have to be pressed to solve the puzzle: why is that?

The still frames of the movie are available here as PNGs in a zipped archive. Here is a solution to the 400-by-400 board:

Solution to 400x400 Lights Out

Finding that solution involved row-reducing a (400 \cdot 400 + 1) -by- 400 \cdot 400 matrix—that’s a matrix with over 25 billion entries. On the other hand, each entry is one bit, so that matrix fits (not coincidentally) in 3 gigabytes of memory. One could surely do better, considering how sparse the matrix is: perhaps we could have a little contest for solving very large Lights Out games.

Besides the fact that all these pictures look awesome, Lights Out is a neat example to motivate some linear algebra over a finite field. It illustrates how satisfying an “easy” local condition (each light must be turned off) might require a globally complicated solution—a lesson for mathematics and for life!


Percolation.

 July 20, 2008 personal mathematics

\newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}}

\newenvironment{question}[1][]{\par\textbf{Question (#1).}}{} \newenvironment{theorem}[1][]{\par\textbf{Theorem (#1).}}{} \newenvironment{lemma}[1][]{\par\textbf{Lemma (#1).}}{} \newenvironment{proof}{\textit{Proof.}}{}

I made a movie recently for my advisor. The movie is so pretty, that I thought I’d share it here: may I present to you randomly drawn dots, where two dots are the same color when they touch!

I’ll be a bit more explicit: a dot is drawn at a random location; if it does not overlap any previous dots, it gets a new color. Otherwise, the dot takes the color of the component it touches. Sometimes a new dot connects many components, and in this case, the new component takes on the color of the largest among the old components.

There’s a lot of neat questions to be asked about such a process: for instance, after drawing n dots, how many components should we expect to see? As you can see in the movie, when you draw only a few dots, most of those dots are isolated and have their own color; but after drawing a ridiculously large number of dots, they are all connected and the same color. And inbetween, something more interesting happens.

Here’s an example of “something more interesting” taken from a larger picture than the above movie:

25000 random points (close up)

Possible homology of closed manifolds.

 March 9, 2008 mathematics

\newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}}

\newenvironment{question}[1][]{\par\textbf{Question (#1).}}{} \newenvironment{theorem}[1][]{\par\textbf{Theorem (#1).}}{} \newenvironment{lemma}[1][]{\par\textbf{Lemma (#1).}}{} \newenvironment{proof}{\textit{Proof.}}{}

In this fun paper [1] it is pointed out that

  • homology is a very basic invariant, and
  • closed manifolds are very basic objects

and so a very basic question is: what sequences of abelian groups are the homology groups of a closed simply connected manifold?

It isn’t very hard to realize any sequence of abelian groups up to the middle dimension, but that middle dimension is tricky (e.g., classify (n-1) -connected 2n -manifolds).

Anyway, I was wondering: is this realization question solvable for homology with coefficients in \mathbb{Z}/2\mathbb{Z} or \mathbb{Q} ?

[1] M. Kreck, An inverse to the Poincaré conjecture, Arch. Math. (Basel). 77 (2001) 98–106. https://doi.org/10.1007/PL00000470.


Political relationships hidden in markets.

 March 8, 2008 personal

\newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}}

\newenvironment{question}[1][]{\par\textbf{Question (#1).}}{} \newenvironment{theorem}[1][]{\par\textbf{Theorem (#1).}}{} \newenvironment{lemma}[1][]{\par\textbf{Lemma (#1).}}{} \newenvironment{proof}{\textit{Proof.}}{}

I’m again applying Granger causality to time series data from Intrade. This time, however, I connect box A to box B with a
  • green arrow if A becoming more likely causes B to become more likely, and with a
  • red arrow if A becoming more likely causes B to become less likely.

Shorter arrows suggest stronger relationships (technically, a lower p-value).

Running the algorithm on the market data since January 1, 2008 with a lag of two days produces the following graph:

And so, we see that the market data is encoding some
  • tautologies (McCain’s nomination makes him more likely to be president, and McCain’s being president makes it more likely that a Republican is president) but also some
  • conventional wisdom (a recession makes Clinton more likely to be nominated, but Obama less likely to be nominated; perhaps the perception that Obama would fare better in the general election explains the red arrows from “Democrat President” to Clinton, and the green arrows from “Democrat President” to Obama).

It’s amazing to me (and hopefully also to you) that the relationships between the prices of these Intrade contracts manages to encode popular sentiments.


Granger causality and Intrade data.

 March 6, 2008 personal mathematics

\newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}}

\newenvironment{question}[1][]{\par\textbf{Question (#1).}}{} \newenvironment{theorem}[1][]{\par\textbf{Theorem (#1).}}{} \newenvironment{lemma}[1][]{\par\textbf{Lemma (#1).}}{} \newenvironment{proof}{\textit{Proof.}}{}

Granger causality is a technique for determining whether one time series can be used to forecast another; since the Intrade market provides time series data for political questions, we can look at whether political outcomes can be used to forecast other political outcomes.

There’s a library for the statistical package R to do the Granger test, and Intrade produces CSV market data. I fed the market data for various contracts since January 1, 2008 into R, and the output of that into GraphViz to make a nice-looking visualization; in particular, I connect a to b if a Granger-causes b with p -value less than 0.05. Darker arrows have smaller p -values. This is all an embarassing misuse of statistics and p -values, but it is quick and easy to do, and the results are fun to see.

Here is the graph for a lag of one day (i.e., does yesterday’s value of a predict today’s value of b ):

Here is the graph for a lag of two days (i.e., can the two previous days of data for a be used to forecast the next day of data for b ):

And here is the graph for a lag of three days:

Don’t take this too seriously. And one word of warning: an arrow from a to b does not mean that if a is more likely, then b is more likely—rather, it ought to mean that past knowledge of a can be used to forecast b . I suppose it would be interesting to add some color for the direction of the relationship, and maybe I’ll do that when I have another free hour.


Movies of some neat cubical complexes.

 February 25, 2008 personal mathematics

\newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}}

\newenvironment{question}[1][]{\par\textbf{Question (#1).}}{} \newenvironment{theorem}[1][]{\par\textbf{Theorem (#1).}}{} \newenvironment{lemma}[1][]{\par\textbf{Lemma (#1).}}{} \newenvironment{proof}{\textit{Proof.}}{}

I made some movies of some of my favorite complexes: let I^n be the n -dimensional cube, and let e_1, \ldots, e_n be the n edges around the origin, and let e_i e_j be the square face containing the edges e_i and e_j . Define a subcomplex \Sigma^2_n \subset I^n consisting of the squares e_1 e_2, e_2 e_3, \ldots, e_{n-1} e_n, e_n e_1 and all the squares in I^n parallel to these. It turns out that \Sigma^2_n is a surface with a lot of symmetries.

In particular \Sigma^2_4 is a torus in \mathbb{R}^4 , and here is a movie of it spinning:


Books that are useless on a desert island.

 February 1, 2008 personal

\newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}}

\newenvironment{question}[1][]{\par\textbf{Question (#1).}}{} \newenvironment{theorem}[1][]{\par\textbf{Theorem (#1).}}{} \newenvironment{lemma}[1][]{\par\textbf{Lemma (#1).}}{} \newenvironment{proof}{\textit{Proof.}}{}

Drew Hevle raises a very interesting question: suppose you are stranded on a desert island; what books would be entirely useless in this situation?

Here are a few books that I wouldn’t want to be stranded on an island with:

Do you have other ideas for awful desert island reading?


Visualizing pineapple pancakes.

 January 30, 2008 personal

\newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}}

\newenvironment{question}[1][]{\par\textbf{Question (#1).}}{} \newenvironment{theorem}[1][]{\par\textbf{Theorem (#1).}}{} \newenvironment{lemma}[1][]{\par\textbf{Lemma (#1).}}{} \newenvironment{proof}{\textit{Proof.}}{}

The pineapple sauce pancake graph has English words as vertices, and a directed edge from a to b if the concatenation ab is also an English word. For instance, there is a vertex labeled pine, and a vertex labeled apple, and an edge from pine to apple.

Anyway, the graph is huge; and the usual visualization tool (Graphviz) doesn’t work particularly well on the whole graph, so I took a few hundred vertices around pine, apple, sauce, pan, and cake. The result was the following:

Small pineapple graph.