Kenyon’s squarespirals

The other day by chance I happened to look at Richard Kenyon’s web page, and was struck by a very beautiful animated image there. The image is of a region tiled by colored squares, which are slowly rotating. As the squares rotate, they change size in such a way that the new (skewed, resized) squares still tile the same region. I thought it might be fun to try to guess how the image was constructed, and to produce my own version of his image.

I already know a little bit about square tilings. This is a subject with a history, going back at least to the work of Tutte and his colleagues. The basic problem is just to tile a rectangular region by squares. Easy enough, you say.

silly_tiling

Well, yes; if the rectangle has sides which are rationally related, in can be filled up by squares with commensurable side lengths pretty easily. Here a 4 by 8 rectangle is filled with 7 squares of edge length 1, 1 square of edge length 3, and 1 square of edge length 4. It’s more amusing to look for a tiling in which all the squares have different lengths. One well-known tiling, found by Tutte’s colleague Stone, is as follows:

stone_tiling

Obviously the problem becomes more interesting and challenging if one starts in advance with the combinatorics of a square tiling, and then tries to assign edge lengths to squares in such a way that they fit together nicely. One elegant method, developed by Brooks, Smith, Stone and Tutte, assigns a directed graph to the tiling, with one vertex for each vertical edge (say) and one directed edge for each square. Here’s the graph associated to Stone’s tiling:

stone_graph

The condition that the sum of square lengths on either side of a vertical edge sum to the length of that edge implies that the incoming edge weights and the outgoing edge weights at each vertex sum to the same value (except for at the leftmost and rightmost vertices). On the other hand, the fact that the squares are all square implies that each edge weight (as above) is equal to the length of its projection to a horizontal line; this means that the sum of edge weights around each loop in the graph (with sign changed when the orientation disagrees with the orientation on the loop) is equal to zero. These two conditions are precisely Kirchoff’s two laws for the current flowing through an electrical network where every edge has resistance 1, and the voltage difference between left and right vertices is the width of the rectangle. There is a unique solution; it might have some weights negative, in which case we can reverse the orientation of the edge so that the weights are all positive, and determine a square tiling with slightly different combinatorics. By the way, the uniqueness of the solution has an interesting (and well-known) consequence: since Kirchoff’s laws both impose linear conditions on the edge weights, the space of solutions is a rational affine space (in units for which the width is equal to 1). Since this space of solutions consists of a single point, this point has rational coordinates; this implies in particular that the height of the rectangle is a rational multiple of the width, and so are the widths of the squares.

In more homological language, the assignment of weights to edges is a (simplicial) 1-chain. The condition that the incoming and outgoing edge weights at each vertex have equal sum says that this 1-chain is actually a (relative) 1-cycle; i.e. that it is closed. The condition that the sum around every loop is zero says that if we think of this 1-chain as a 1-cochain it is actually a 1-cocycle; i.e. it is co-closed. A (co)-chain which is both closed and co-closed is said to be harmonic, and the uniqueness of a solution corresponds to the uniqueness of a harmonic representative of a (relative co-) homology class.

Incidentally, if we form the graph with one vertex for each vertical horizontal line and one edge for each square, this will be the (planar) dual to the graph above. Edges in one graph correspond to edges in the other, and the closed condition for one set of edge weights becomes the co-closed condition for the other, and vice versa.

Now instead of considering a square tiling of a rectangle, let’s consider a square tilings of a Euclidean torus. A combinatorial tiling gives us a graph, and a harmonic 1-cycle gives us a square tiling with the desired combinatorics. Changing the 1-cycle by rescaling it just rescales the torus and all the squares by the same factor, which is not very interesting. However, there is something interesting we can do. The homology of a torus is 2-dimensional, so we can consider a 1-parameter family of homology classes whose projective classes are changing, and a 1-parameter family of harmonic 1-cycles and of square tilings.

Let’s start with the simplest possible example. We fix a graph G embedded in the torus. Since we want G to be able to carry every homology class, we need at least two edges. So let’s take as G the graph with one vertex and two edges, one of which wraps horizontally once around the torus, and one of which wraps vertically around. Any assignment of weights to the edges will be both closed and co-closed, so a 1-parameter family is given by taking weights cos(t), sin(t) for t in the unit circle. The resulting square tilings of the torus have two squares, one of side length cos(t) and one of side length sin(t). The total area of the torus is thus normalized to be 1. The pattern of tilings “rotates” with t as follows:

rotating_squares_1

(click on the image to see it rotate)

OK, how about a more complicated example? Let’s let G be some complicated embedded graph on the torus (so that it can carry any homology class). For the sake of concreteness, let’s let G be the following graph:

torus_graph

G has 10 edges (corresponding to 10 squares in the tiling), 5 vertices and 5 complementary faces. There are 5 vertex conditions and 5 face conditions; however, this system of 10 equations is redundant, and has a 2 dimensional space of solutions.

Weights on the edges of G form a vector space, and there is an inner product on this space which is just the ordinary Euclidean inner product with co-ordinates the weights on each each edge. We want to normalize our weights to have length (i.e. square root of their inner product with themselves) equal to 1, so that the resulting torus will have area 1. All we need to do is find two orthogonal weights M and L which are closed and co-closed, orthogonal to each other (i.e. the inner product of M and L is zero) and of length 1, and then we can form the family cos(t)M + sin(t)L of weights, and the associated square tilings.

The resulting rotating family of tilings is as follows:

rotating_squares_3

(click on image to see it rotate)

Something else is needed to get the “spiraling” evident in Kenyon’s picture. For our square tilings of a torus above, the result of laying down a sequence of squares that winds once around a loop in the torus is to displace the tiling by a translation of the plane; this translation is called the holonomy around the loop, and only depends on its homotopy class (actually: on its homology class). Essentially, this is the result of integrating the (dual) 1-form associated to the weight. An educated guess is that in Kenyon’s picture, the holonomy is not a translation, but rather a dilation of the plane, centered at some point. At the level of homology, one can think of the dilation factor around a loop as a representation of the fundamental group, and we need to consider (harmonic) 1-cycles with coefficients twisted by this representation.

How to translate this into the language of square tilings and weights? Instead of thinking of a weight on the graph G, let’s let G~ denote the lift of G to the universal cover of the torus; i.e. G~ is a periodic graph in the plane. A twisted weight on G with coefficients in a representation is the same thing as a weight on G~ that transforms according to the given representation. For the sake of simplicity, let’s work with the graph G with one vertex and two edges as in the first example above, so that G~ has one vertex, one horizontal edge, and one vertical edge for each pair of integers. Pick a pair of edges H,V of G~, going to the right and up incoming to the vertex (0,0) respectively and let h,v be the weights on these edges.

If we let A denote the multiplication factor for horizontal translation, and B the multiplication factor for vertical translation, the vertex equation at (0,0) is

h(A-1)+v(B-1)=0

The vertex equations at every other vertex are obtained from this one by scaling by power of A and B, so they are satisfied if this one is. The face equation for the face with vertices (-1,-1), (0,-1), (0,0), (-1,0) is

h(B^{-1}-1)+v(1-A^{-1})=0

Eliminating h from this pair of equations and dividing out by v gives

A+A^{-1}+B+B^{-1}=4

In order to enforce spiraling, we would like moving “horizontally” some fixed number of steps to be the same as moving “vertically” some (other) fixed number of steps; this can be imposed by setting A^pB^q=1 for some coprime integers p,q. With these constraints, there is a unique solution h,v in complex numbers, up to scale. The real  part of any such solution gives a “spiral” tiling, and the 1-parameter family obtained by multiplying by e^{it} before taking the real part gives a rotating spiral.

Let’s try an example. Taking p=2,q=1 gives A=(-3-\sqrt{5})/2=-2.618033 and B=A^{-2}=0.145898. There is a totally real solution, giving rise to the following “degenerate” spiral:

rotating_squares_4

Since this solution is totally real, it can’t be “rotated”. Hmm, I wasn’t expecting that. OK, taking p=3,q=1 gives A=-0.742934-1.52909i and B=0.198893-0.0432177i.

rotating_squares_4

(click on image to see it rotate)

Success!

Getting more squares in the picture is a matter of spiraling slower, which can be achieved by taking p and q bigger. Let’s try p=7,q=1.

rotating_squares_5

(click on image to see it rotate)

If you want to have a play with this yourself, the source of the .eps file that generated these figures is below. To change the amount of spiraling, change the values of A and B, subject to the constraint that A+A^{-1}+B+B^{-1}=4. The resulting .eps file can be transformed to a layered .pdf (eg using Preview on a Mac) then to a .gif (eg in gimp). The case q=1 is pretty easy, since then A is the root of x^{2p} + x^{p+1} - 4x^p + x^{p-1} + 1 = 0 with smallest (nonzero) argument, and B=A^{-p}. Wolframalpha will cough up the values of A and B if you coax it long enough.

(Update January 16): Just for fun, here’s the tiling with p=101, q=1 (warning: the .gif file is quite large!)

rotating_squares_7

(click on image to see it rotate)


%!PS-Adobe-2.0 EPSF-2.0
%%BoundingBox: 0 0 400 400
gsave
400 400 scale
1 20 div setlinewidth
1 setlinejoin
0.5 0.5 translate
/square{4 dict begin
/z exch def
/y exch def
/x exch def
gsave
newpath
rand 10 mod 10 div rand 10 mod 10 div rand 10 mod 10 div setrgbcolor
x y moveto
x z add y lineto
x z add y z add lineto
x y z add lineto
closepath
fill
stroke
grestore
end } def
/simple_edge_squares{4 dict begin
/v exch def
/n v length def
0 1 n 1 sub{
/i exch def
0 0 v i get square
0 v i get translate
} for
end} def
/rcmul{2 dict begin
/t exch def
/z exch def
[ z 0 get t mul z 1 get t mul]
end} def
/ccmul{2 dict begin
/w exch def
/z exch def
[
z 0 get w 0 get mul z 1 get w 1 get mul sub
z 0 get w 1 get mul z 1 get w 0 get mul add
]
end} def
/cconj{1 dict begin
/z exch def
[
z 0 get 0 z 1 get sub
]
end} def
/cnorm{1 dict begin % |z|^2
/z exch def
z 0 get dup mul z 1 get dup mul add
end} def
/ccdiv{2 dict begin % w/z = w*zbar/|z|^2
/z exch def
/w exch def
w z cconj ccmul 1 z cnorm div rcmul
end} def
/ccadd{2 dict begin
/w exch def
/z exch def
[ z 0 get w 0 get add z 1 get w 1 get add ]
end} def
/creal{1 dict begin
/z exch def
z 0 get
end} def
/cimag{1 dict begin
/z exch def
z 1 get
end} def
0 5 355 {
/t exch def
0 srand
gsave
/A [0.71469 -0.870643] def % A is root of x^14+x^8-4x^7+x^6+1=0
/B [0.432505 -0.0429583] def % B = A^-7
% check: A^3B=1
/h [t cos t sin] def
/v h A [-1 0] ccadd ccmul [1 0] B -1 rcmul ccadd ccdiv def %
% h*(A-1)/(1-B)
/Ainv [1 0] A ccdiv def
/Aser [1 0] Ainv ccadd Ainv Ainv ccmul ccadd Ainv Ainv ccmul Ainv ccmul ccadd Ainv Ainv ccmul Ainv ccmul Ainv ccmul ccadd Ainv Ainv ccmul Ainv ccmul Ainv ccmul Ainv ccmul ccadd def
/Acom [1 0] Ainv -1 rcmul ccadd def
/htran h Acom ccdiv def
/vtran v Acom ccdiv def
t rotate
htran creal vtran creal -1 mul translate
[h A ccmul creal v B ccmul creal h [-1 0] ccmul creal v [-1 0] ccmul creal] simple_edge_squares
1 1 50{
h -1 rcmul creal v creal translate
/h h A ccdiv def
/v v A ccdiv def
[h A ccmul creal v B ccmul creal h [-1 0] ccmul creal v [-1 0] ccmul creal] simple_edge_squares
} for
showpage
grestore
} for
grestore
%eof

This entry was posted in Complex analysis, Euclidean Geometry and tagged , , , , . Bookmark the permalink.

19 Responses to Kenyon’s squarespirals

  1. John Mangual says:

    I wrote something similar in Mathematica: https://gist.github.com/4355233 in regards a tiling proof of Pythagorearn theorem www-stat.wharton.upenn.edu/~steele/Publications/…/paintings.pdf

    Tutte’s ideas about square-tiling seems to be embedded in Kenyon’s latest work, as a special case.

    • Hi John – yes, the tiling of the square torus by two squares is one of the prettier “dissection” proofs of Pythagoras; no doubt it has been rediscovered many times, but one of the more well-known accounts is Felix Bernstein, `Der Pythagoraische Lehrsatz’, Zeitschriften fur Mathematischen und Naturwissenschaftlichen Unterricht 55 (1924), pages 204 – 207.

      The formulation in terms of harmonic simplicial (co)cycles is probably one of the most direct ways to see the connection between square tilings and “discrete complex analysis”; this is a subject that has become increasingly important to people working in statistical mechanics/probability recently, especially through the connection to planar percolation theory. I am thinking for example of Stas Smirnov’s proof of the conformal invariance of percolation (on the honeycomb lattice) in the continuum limit, which is proved by a kind of discretization of the Cauchy-Riemann equations (see eg http://www.unige.ch/~smirnov/papers/icmp-final.pdf for an account). Of course I know something of this story, and of its connections to Kenyon’s interests, but I wanted to keep things reasonably elementary in this blog post, for pedagogical reasons.

      best,

      Danny

      • John Mangual says:

        OK. So there is something ‘holomorphic’ about square-tilings – perfectly packing squares into a rectangle – and now there’s also a statistical model associated to them. That is a little bit overwhelming.

        Are there any “important” or just fun math questions to think about here? Maybe just keep drawing spiral-square things!

        With many squares, the approximation to an actual conformal mapping is pretty clear. Something I didn’t appreciate when there are only 5 or 10 squares.

        Maybe, in a sense, holomorphic functions are “square” b/c the Cauchy-Riemann equations. But I didn’t take that too seriously, until I saw that page from Smirnov.

        This blog is the only geometric discussion of square-tilings I can find.

      • Hi John – (this is a reply to your comment – for some reason WordPress won’t allow replies to comments to nest further than depth 3) – first of all, I would hesitate to draw a firm distinction between “fun” and “important” math. But it is certainly true that a lot of deep and “important” math (as measured by “professional” standards) arises from investigations that have their origin in curiosity about “fun” math. The process is cumulative – yesterday’s curious counterexample might be the nugget of tomorrow’s comprehensive structure theorem.

        More specifically, the subject of “discrete” (1-dimensional) complex analysis is a great area for this kind of thing, since our visual intuitions about the plane are so strong and powerful, and can get us a huge way towards “important” math on their own. One of the great things about harmonic analysis is the interplay between a linear condition (being closed/co-closed) and a nonlinear condition (minimizing an L^2 norm); hence, as you say, `(things) are “square” because Cauchy-Riemann equations’. The point is that the C-R equations are “universal” for 2nd order linear elliptic PDEs, and so many a priori different looking variations on these equations give rise to essentially equivalent theories (and this is true in the discrete world as well as the continuous one).

      • Dylan Thurston says:

        John, these square-tilings also show up beautifully in Cannon, Floyd, and Perry’s theory of Combinatorial Riemann Mappings, as used to study subdivision rules.

  2. Dylan Thurston says:

    Very nice. This doesn’t seem to be as well known as it ought to be… I’m also a fan of the more general story with convex polygons, for instance in the dancing triangles you can find elsewhere on Rick’s page.

    It doesn’t seem like the aspect ratio of the overall torus changes (very much) as you rotate in the family you picked. Did you do anything to make this happen?

    • Hey Dylan! I wondered about that; it was just a random choice. Incidentally, one can do square packing on higher genus surfaces too; there is a slight subtlety in that a vertex of the graph might correspond to a 2n-prong singularity in the packing, depending on how many times the coefficients on the (oriented incoming) edges incident to that vertex change sign as one traverses them cyclically. So for a fixed combinatorial graph one gets a map from H_1 to cotangent space of Teichmuller space (by thinking of a square tiling as a Riemann surface together with a quadratic holomorphic differential). Scaling the coordinates just scales the surface, so the image in moduli space is bounded (of course), and in fact one can get an a priori bound on the size of the image directly from the coordinates by the length-area method. It would be cool to work out exactly what the image is in some special cases.

      • Dylan Thurston says:

        It’s not obvious to me that the image in moduli space is bounded. I’m a little skeptical in the higher-genus case. You could have a square in which two of the sides are identified, if it borders the same face on both sides of the corresponding edge in the resistor graph (or the same vertex at both ends of the edge). If that square shrinks to 0 area, aren’t you heading off to infinity in moduli space?

        Or maybe you’re thinking about the torus case. Do you have an easy proof in that case?

      • Hey Dylan – you’re right, I was being a bit glib; one should consider degenerate cases. But actually, I think that (at least for graphs which are sufficiently complicated) one should be able to estimate the modulus of enough annuli *just* from the combinatorics and the fact that the cells are *squares*. So I would guess that – again, apart from degenerate graphs where eg some vertex is joined by an edge to itself – one should be able to get an a priori bound on the size of the image in moduli space. But this is not an argument, just a suspicion.

      • Dylan Thurston says:

        Oh, and I’d love to think about the image is. In the torus case, it might not be so bad. A crucial feature will be the medial graph that you get by connecting the midpoints of the edges of the resistor graph, and think of it as a collection of paths. A beautiful result of Curtis, Ingerman, and Morrow says that a planar resistor network (with terminals on the boundary) is optimal in the sense that it has no redundant resistors iff no two of these paths cross twice. On the torus, I expect the optimal graphs to be those that come from taking a collection of curves at different slopes and superimposing them; that collection of slopes ought to control the image in moduli space somehow.

        The graph you picked above is not optimal in this sense; if you delete edge 8 (set the resistance to infinity) and contract edge 2 (set the resistance to 0), you get another graph that can realise the same set of shapes with an appropriate choice of resistances (i.e., tiling with rectangles of fixed aspect ratio rather than squares). That graph is much simpler, and maybe this explains why the aspect ratio doesn’t seem to be changing (much).

      • I didn’t know about the Curtis-Ingerman-Morrow result. Yes, I would also be very interested to find out what the image looks like, and how it depends on the combinatorics and coarse geometry of the graph.

      • I just wanted to follow up on this question about how the shape of the torus changes: In the case of a tiling of the torus, the total energy (area) is a quadratic function of the angle, so the shape changes in a predictable way. I think it’s true that if you stretch the squares to be rectangles of a different modulus (all the same), then the aspect ratio of the resulting torus doesn’t change at all as you rotate.

  3. Remarkable things here. I’m very happy to look your article. Thanks a lot and I’m taking a look ahead
    to touch you. Will you kindly drop me a mail?

  4. adam ponting says:

    Great page and discussion! Thanks. I’m just getting into these things, but on a related note: I’ve found a family of arrangements of consecutive integer squares, which can ‘sort of’ tile the plane. (And each one can be extended to..almost tile the plane, though not with unique sizes. Maybe one of them has no gap, not sure yet.) I’ve asked about it here (more info and links to pics) : http://math.stackexchange.com/questions/794092/squaring-the-plane-with-consecutive-integer-squares-and-a-related-arrangement .. Can anyone help with info about such things? I’ve no idea if they’re known. (Jim Henle and Stuart Anderson say they haven’t seen it before.) Thanks :-)

    • Hi Adam – your integer square pattern is very nice, and I hadn’t seen it before. It’s intriguing that it almost manages to close up; one thing to do would just be to compute the square packing with the topology you describe that exactly closes up, and then see what the square sizes are (there’s an issue with determining the boundary values; I don’t know what to do about that).

      • I played around a little bit with this very interesting pattern. It’s based off the simplest two-square tiling of the torus, but with a cocycle that makes it not quite periodic; it’s an additive cocycle rather than a multiplicative cocycle (as in the OP). If you extend the pattern, and shift the arithmetic progressions slightly so that it ends up symmetric, you end up with a discrete approximation to the function z^2 (or sqrt(z), depending how you think about it). It makes a really pretty picture.

    • Anonymous says:

      Could this be one of the quasi-periodic tilings, perhaps? It is a very simple packing. Interesting!

  5. adam ponting says:

    :-) Could I see some pictures? Uh your maths is above my head at the moment, but sounds like there is no gapless extended version? I was going to check, or try to, just by making a couple of simple (arithmetic series) equations, but life got in the way so far. Thanks for the helpful and nice comments.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s