Celtic Knots on Einstein Lattice
I recently posted about doing Celtic Knots on a Hexagonal lattice ( https://www.lesswrong.com/posts/tgi3iBTKk4YfBQxGH/celtic-knots-on-a-hex-lattice ).
There were many nice suggestions in the comments. @Shankar Sivarajan suggested that I could look at a Einstien lattice instead, which sounded especially interesting. ( https://en.wikipedia.org/wiki/Einstein_problem . )
The idea of the Einstein tile is that it can tile the plane (like a hexagon or square can), but it does so in a way where the pattern of tiles never repeats.
The tile I took from Wikipedia looks like this:
On the left is the full tile. On the right is a way of decomposing it into four-thirds of a hexagon.
For some reason I think of it as a lama. On the left top is its head, facing left. On tie right top its its tail. The squarish bit coming down is the legs.
First problem: the tile has 13 sides. So if we run a string into/out of every edge we are going to have a loose end. Second problem, sometimes a face in the tiling touches a corner:
Image from Wikipedia. In the pink circle the face of the red tile connects to a corner between the orange and white ones. This is a problem, if we had a string going off that edge of the red tile it would get split.
The solution is to identify a subset of the edges to put strings on, where this will never happen. The hex grid underlay on Wikipedia reveals a strategy—take only those facets touching a hexagon separator line. IE for each of the 4 thirds of a hexagon, the two long edges of those third pieces, are used. This gives 6 total per tile (an even number, woo!), meaning that the connectors joining each in/out to each other fill this table:
(Each entry point can connect to any exit except itself.)
Notice that a couple of the ropes trespass slightly outside the tile. This seems like it will be fine, if it does touch a rope in another tile it can just go over or under it.
Combining these connectors every possible way we get this tile set:
Pretty weird looking.
Using them to semi-randomly tile the plane using the pattern from Wikipedia we get something as weird as might be expected:
I like the “clover” that formed in the middle of the design.
One big downside compared to hexagons is I can’t just put tiles down fluently, while concentrating on the aesthetics. After picking up a tile to use I typically spend 20+ seconds rotating and mirroring it while consulting the mapping scheme, before finally working out how it goes in. At that point I could do similar for a different tile and then pick the one that looked better, but my patience did not stretch so far as that. I am getting faster, and putting the map underneath helps, but its still not an effortless process like with hexagons.
Using copies of just one tile again and again is still chaotic looking, barring the obvious counter-example:
I added all this stuff to the shared folder(as inkscape .svg files) in case anyone wanted a play with the tiles. https://drive.google.com/drive/folders/1BS42moNocDLIwFGeEAESK0ttX4CANo-5
The sidelengths for the Einstein tile are all either 1 or √3, except for a single side of length 2. I think it makes more sense to treat that side as two sides, with a 180∘ angle between them. Then you would get fourteen entry/exit points:
The aperiodic tiling from the paper cannot be put onto a hexagonal grid, and some of the tiles are flipped vertically, so you need every edge to have an entry/exit to make a Celtic knot out of it. Also, I would recommend using Tile(1,1) rather than Tile(1,√3) so the arcs turn out pretty:
That is a nice idea. The “two sides at 180 degrees” only occurred to me after I had finished. I may look into that one day, but with that many connections is needs to be automated.
In the 6 entries/exits ones above you pick one entry, you have 5 options of where to connect it. Then, you pick the next unused entry clockwise, and have 3 options for where to send it, then you have only one option for how to connect the last two. So its 5x3x1 = 15 different possible tiles.
With 14 entries/exits, its 13x11x9x7x5x3x1 = 135,135 different tiles. (13!!, for !! being double factorial).
You also have (I think) 13+12+11+10+… = 91 different connection pieces.
One day, I may try and write a code to make some of those. I strongly suspect that they won’t look nice, but they might be interesting anyway.
Your math is correct, it’s 13!! and (142)=91 for the number of tiles and connections. I wrote some code here:
https://github.com/programjames/einstein_tiling
Here’s an example:
An interesting question I have is: suppose we tied off the ends going clockwise around the perimeter of the figure. What is the probability we have exactly one loop of thread, and what is the expected number of loops? This is a very difficult problem; I know several MIT math students who spent several months on a slightly simpler problem.
This is really wonderful, thank you so much for sharing. I have been playing with your code.
The probability that their is only one loop is also very interesting. I worked out something, which feels like it is probably already well known, but not to me until now, for the simplest case.
In the simplest case is one tile. The orange lines are the “edging rule”. Pick one black point and connect it to another at random. This has a 1⁄13 chance of immediately creating a closed loop, meaning more than one loop total. Assuming it doesn’t do that, the next connection we make has 1⁄11 chance of failure. The one after 1⁄9. Etc.
So the total probability of having only one loop is the product: (12/13) (10/11) (8/9) (6/7) (4/5) (2/3), which can be written as 12!! / 13!! (!! double factorial). For a single tile this comes out at 35% ish. (35% chance of only one loop).
If we had a single shape with N sides we would get a probability of (N-2)!! / (N-1)!! .
The probability for a collection of tiles is, as you say, much harder. Each edge point might not uniformly couple to all other edge points because of the multi-stepping in between. Also loops can form that never go to the edge. So the overall probability is most likely less than (N-2)!!/(N-1)!! for N edge dots.
So, I’m actually thinking about something closer to this for “one loop”:
This is on a single square tile, with four ports of entry/exit. What I’ve done is doubled the rope in each connection, so there is one connection going from the top to the bottom and a different connection going from the bottom to the top. Then you tie off the end of each connection with the start of the connection just clockwise to it.
Some friends at MIT solved this problem for a maths class, and it turns out there’s a nice recurrence. Let P(n,ℓ) be the probability there are ℓ loops in a random knot on a single tile with 2n sides. Then
P(n,ℓ)=2n+1P(n−1,ℓ−1)+n−1n+1P(n−2,ℓ).So, if you’re looking for exactly one loop, you’d have
P(n,1)=n−1n+1P(n−2,1)⟹P(n,1)={1n+1n is even0n is odd.I can’t really explain where this recurrence comes from; their proof was twenty pages long. It’s also too complicated to really apply to multiple tiles. But, maybe there’s a more elementary proof for this recursion, and something similar can be done for multiple tiles.
I think I am not understanding the question this equation is supposed to be answer, as it seems wrong to me.
I think you are considering the case were we draw arrowheads on the lines? So each line is either an “input” or an “output”, and we randomly connect inputs only to outputs, never connecting two inputs together or two outputs? With those assumptions I think the probability of only one loop on a shape with N inputs and N outputs (for a total of 2N “puts”) is 1/N.
The equation I had ( (N-2)!! / (N-1)!!) is for N “points”, which are not pre-assigned into inputs and outputs.
These diagrams explain my logic. On the top row is the “N puts” problem. First panel on the left, we pick a unmatched end (doesn’t matter which, by symmetry), the one we picked is the red circle, and we look at the options of what to tie it to, the purple circles. One purple circle is filled with yellow, if we pick that one then we will end up with more than one loop. The probability of picking it randomly is 1⁄7 (as their are 6 other options). In the next panel we assume we didn’t die. By symmetry again it doesn’t matter which of the others we connected to, so I just picked the next clockwise. We will follow the loop around. We are now looking to match the newly-red point to another purple. Now their are 5 purples, the yellow is again a “dead end”, ensuring more than one loop. We have a 1⁄5 chance of picking it at random. Continuing like this, we eventually find that the probability of having only one loop is just the probability of not picking badly at any step, (6/7)x(4/5)x(2/3) = (N-2)!! / (N-1)!!.
In the second row I do the same thing for the case where the lines have arrows, instead of 8 ports we have 4 input ports and 4 output ports, and inputs can only be linked to outputs. This changes things, because now each time we make a connection we only reduce the number of options by one at the next step. (Because our new input was never an option as an output). The one-loop chance here comes out as (3/4)x(2/3)x(1/2) = (N-1)! / N! = 1/N. Neither expression seems to match the equations you shared, so either I have gone wrong with my methods or you are answering a different question.
The bottom row is close to what I imagine, but without IO ports on the same edge being allowed to connect to each other (though that is also an interesting problem). These would be the three diagrams for the square:
The middle one makes a single loop which is one-third of them, and n=4/2=2 in this case. My guess for how to prove the recurrence is to “glue” polygons together:
There are n+1 pairs of sizes (k,n+1−k) we can glue together (if you’re okay with 2-sided polygons), but I haven’t made much progress in this direction. All I’ve found is gluing two polygons together decreases the number of loops by zero, one or two.
I had the same thought. I expect the probability of one loop trivially goes to zero as the tiling goes to infinity—because of the small loops—and that a better question would be whether there is an infinite loop. That looks an interesting (and hard!) percolation problem.
You could split each full tile into its four sub-tiles, each with six connection points. Then, each sub-tile can be one of 15 flavors.
Neat! I think the same strategy works for the spectre tile (the ‘true’ Einstein tile) as well, which is what’s going on in this set.
Ah, what a fun idea! I wonder if coloring or marking the ropes and/or edges somehow would make it easier to assemble ad hoc- I think Veritaseum’s video about non-periodic tilings included some sort of little markers on the edges that helped him orient new tiles, but that was on Penrose tiles and I’m not sure this shape has the same option.