dafnis
Craig S. KaplanHow small can a set of aperiodic tiles be? The first aperiodic set had over 20000 tiles. Subsequent research lowered that number, to sets of size 92, then 6, and then 2 in the form of the famous Penrose tiles. https://youtu.be/48sCx-wBs34 1/6
YouTube
Penrose's work dates back to 1974. Since then, others have constructed sets of size 2, but nobody could find an "einstein": a single shape that tiles the plane aperiodically. Could such a shape even exist? https://en.wikipedia.org/wiki/Einstein_problem 2/6
Taylor and Socolar came close with their hexagonal tile. But that shape requires additional markings or modifications to tile aperiodically, which can't be encoded purely in its outline. https://en.wikipedia.org/wiki/Socolar%E2%80%93Taylor_tile 3/6
In a new paper, David Smith, Joseph Myers (@jsm28), Chaim Goodman-Strauss and I prove that a polykite that we call "the hat" is an aperiodic monotile, AKA an einstein. We finally got down to 1! https://arxiv.org/abs/2303.10798 4/6
An aperiodic monotile
A longstanding open problem asks for an aperiodic monotile, also known as an "einstein": a shape that admits tilings of the plane, but never periodic tilings. We answer this problem for topological disk tiles by exhibiting a continuum of combinatorially equivalent aperiodic polygons. We first show that a representative example, the "hat" polykite, can form clusters called "metatiles", for which substitution rules can be defined. Because the metatiles admit tilings of the plane, so too does the hat. We then prove that generic members of our continuum of polygons are aperiodic, through a new kind of geometric incommensurability argument. Separately, we give a combinatorial, computer-assisted proof that the hat must form hierarchical -- and hence aperiodic -- tilings.
Please visit https://cs.uwaterloo.ca/~csk/hat/ for more information. There you'll find an interactive, browser-based application for constructing your own patches of hats. 5/6
The paper includes two proofs of aperiodicity. The first is a computer-assisted, case-based analysis of the structure of tilings by hats. The second makes use of the fact that the hat is one member of a continuum of aperiodic monotiles! https://youtu.be/W-ECvtIA-5A 6/6
Aperiodic monotile animation
Patrick Honner@csk Congratulations!
Tiota Sram@csk question (which might have an answer out there I simply haven't found it might not): I'm interested in noise functions, and for various purposes, an aperiodic noise function would be swell. But true noise functions need to be locally evaluatable in time not related to distance-from-origin. My gut as a computer scientist tells me it is not possible to have that property and aperiodicity, and so far I've settled on log-time algorithms as a compromise. Do you know if it had been proven either way that aperiodicity is incompatible with computable-at-arbitrary-coordinates-in-coordinates-independant time? (Or does this question even make sense to you?)
@csk actually, upon more thinking I think there's a simple proof for O(log(r)) being a lower bound for time to compute an arbitrary patch of an aperiodic tiling: if it's deterministic (which I think it must be), to get different outputs in different places you need different inputs, and coordinates which are your inputs need log(r) bits (where r is the distance from the origin), all of which your algorithm must depend on. I already have some techniques for doing aperiodic stuff in log-n time using fractal coordinates, so I guess I've answered my question here. But I'm still curious what the big-O time for computing an arbitrary patch of these hats is as a function of R. Naively I'd guess r-squared (i.e., fill in a circle into you get big enough to include r) but I'd guess you could probably or something O(r) together that filled in a line from the origin... I wonder if you can do better though?
Cassidy Curtis@tiotasram @csk I remember seeing a really elegant interactive demo that generated tilings out of Penrose rhombi by treating them as the faces of 5-D hypercubes, viewed from a certain angle. Seems like that might be independent of distance from origin, right?
@tiotasram @csk For example: http://gregegan.net/APPLETS/12/12.html
(Created by @gregeganSF if I’m not mistaken!)
(Created by @gregeganSF if I’m not mistaken!)
Greg EganWith the Penrose tiling, there are details encoded in the coordinates of the location where you are computing the tiling that will require more and more bits of precision to maintain accurately as you get farther away. I’ve never really tried to quantify this aspect of the tiling, though, and it is not an issue for the applet shown when run for, say, several hours. But in the infinite limit you would need ever more precision.
@csk @gregeganSF @tiotasram The other thing that could pose a problem is that the Penrose tiles are all aligned with certain axes, so the resulting noise would still have the same type of directional biases that you get from any grid-based noise. (Although maybe adding more axes reduces the bias? Hmm, now I’m curious!)
@otherthings @gregeganSF @tiotasram A very good starting point for further study of these statistical noise properties would be this old paper by Victor Ostromoukhov et al.: http://www.iro.umontreal.ca/~ostrom/ImportanceSampling/. They use the Penrose Tiling as a scaffolding for importance sampling. So you can count on Fourier spectra characterizing the blue noise and anisotropy.
@csk @otherthings @gregeganSF thanks so much for the discussion and links here! This is super helpful.
@otherthings @tiotasram Yeah, again, the computational cost is independent of distance from the origin. But of course, if you get far enough way then your numerical representations will start to break down. I think you can do all the computation with big integers, but, uh, not on the GPU.
グレェ「grey」@tiotasram Some relatively (2021) recent examples exploring TRNGs in @bunnie's Precursor here:
https://www.bunniestudios.com/blog/?p=6094
Though if you look at the math break down here:
https://www.bunniestudios.com/blog/?p=6097
You'll see that NIST SP 800-90B section 4.4 has at least one logarithmic function.
There are some comments with other perspective in the second link that are food for thought.
AFAIK, not many people discuss these subjects too widely or openly, IMHO I think because most people aren't nerdy enough? ;)
Andreas Grois@tiotasram @csk Physicist here, so not an expert on computation, but quasi-crystals can be generated by looking at a slice of a higher-dimensional periodic lattice. The angle has to be irrational, iirc. I would expect this to be implementable in constant time (but haven't tried this, so I might talk nonsense right now).
@soulsource @csk wow, that's really useful to know actually! Sounds like an easier and maybe more flexible way to make (maybe families of?) aperiodic tilings that can be computed piecewise. Also makes me wonder what it would look like if you took a hyperbolic or other non-planar slice.
@tiotasram @soulsource That's right! You can draw aperiodic tilings using a sampling algorithm that runs in constant time (but, uh, with a high constant). I don't think this is published anywhere, but here are two examples (one by me): https://www.shadertoy.com/view/XdtBzH https://www.shadertoy.com/view/ldcfzN, For a long time I've thought about creating a more efficient algorithm, but it's a hard problem (it even seems to connect somehow to lattice crypto).
rjf_berger@tiotasram @soulsource @csk The method is sometimes called "cut and project". Say you have 2d quadratic grid and you draw a stripe of some finite breadth and with irrational slope into the grid. Then projeting the gridpoints that come to fall within the stripe onto a say central line of the stripe you obtain a 1D quasi periodic/quasicrystalline pattern. Like the sequence of S and L in the penrose tiling.
The analog works for Dan Shechtmans real world 3D quasicrystalls, they can be described as an irrational intersection of a 3D slath with a 4D periodic (translational) tiling (pattern).
As far as I know it's open if there are quasi periodic patterns that cannot be described by "cut and project". In any case the basic idea can be used to compute fourier tranforms, i. e. the (electron) diffraction patterns of the quasiperiodic patterns that can be described like that.
Freeman Dyson wrote famously in "From Birds and Frogs" about the idea that the Riemann zeta zeros could be 1D quasicrystals in some sense and that a "complete understanding" of 1D quasicrystals might open a way to the RH.
@tiotasram @soulsource @csk Lagarias wrote on quasiperiodic sets (https://dept.math.lsa.umich.edu/~lagarias/doc/diffraction.pdf) and their diffraction patterns. He gives a general definition and if I understand correctly there should be both a finite upper and lower bound to the gaps between the points (sorry for my wild descriptions I am no mathematician) of a quasiperiodic lattice. This seems to be a valid generalization to me of what one can obtain from "cut and project".
I wonder about the gaps of the zeta zeros. As far as I know there are upper and lower bounds but they do depend on the zeros, I mean they are as far as I know no constants. If one can fix this somehow, say transform the zeta function such that these bounds become constants, I don't know.
@rjf_berger you've gone a bit beyond my math + physics level here, and web search isn't proving useful to figure out what a "quadratic grid" is since it also appears to name a teaching technique for polynomial multiplication. If you have a reference handy for "quadratic grid" I'd appreciate that, although I can keep searching more carefully on my own.
The idea of slicing an n+1 dimensional repeating grid at an irrational angle and projecting the included points down to n dimensions makes sense to me.
I saw some other papers referencing a Fibonacci grid, but I'll have to dig into that more, because they glossed over the definition of the Fibonacci grid and the paper they cited for that didn't have a full text I could access very easily.
But thanks for drawing additional connections!
@tiotasram Well sorry for my clumsy language. Its just a plane full of squares (="Quadrate" in germ.). Like the paper pupils use for maths: (and here some literatutre on the fib chain construction and its FT http://arxiv.org/pdf/cond-mat/0309008v2.pdf).
tjhowse@csk BRB firing up the laser cutter.
@csk The great irony is that I had to lay them out in a grid to laser cut them, rather than tessellating them to save on plywood. 😆
forresto@tj @csk "Aperiodic Monotile" for #LaserCutting, parametric layout in #CuttleXYZ
https://cuttle.xyz/@forresto/An-aperiodic-monotile-BgC9jiVONijH
(I vote that it's an untucked shirt over a hat, and think the cut could catch on.)
raboof@raboof @csk No! It's just I imported a single hat shape and didn't spend the time to carefully arrange the copies to tessellate. I could've used the interactive web app released with this paper to produce bigger blocks of hats, but it outputs SVGs that are... lightly compliant with the SVG spec. I had to manually tweak them in a text editor before they'd import into Inkscape or Lightburn.
Jesse Clark
nick
0xDE@csk Someone posted a link for more discussion at https://www.metafilter.com/198657/Coming-to-a-bathroom-floor-near-you-soon
This is a splashy result so I bet there will soon be many more links across the web to it.
Congratulations!
Stijn De Baerdemacker@csk Always love to see penrose darts 🙂
Bill Ricker@csk periodic tiles as the degenerate case in a continuum of aperiodic tiles, elegant! Congrats!
Richard "RichiH" Hartmann@csk If you want to print a few billions pieces for an empirical proof, you now can :)
I added a link to arXiv; if you prefer a different citation, please let me know. Once it's peer reviewed I will update links & citations.
https://www.printables.com/model/430171-einstein-worlds-first-aperiodic-monotile
Owen Maresh@csk what does this look like when this animation is converted to an extrusion of its frames in 3d?
Globaltom@Globaltom Yes. Three points along our continuum of shapes are *not* aperiodic. This is one of them.
@csk Ooh, interesting. What are the other two?
Deborah Pickett@csk This is amazing, and I have just ordered the materials to make a quilt based on tiling hats, so watch this space!
A question, inspired by figure 2.12 in the preprint: at large scale, can you always trace a path from one F metatile to any other F metatile through only F metatiles? Similarly, from one H/P metatile to any other H/P metatile through only H/P metatiles? My intuition is that at most only one of these can be yes, but they could both be no.
SupposeNot@csk this is incredibly exciting news, and I really look forward to reading the paper and playing with the tiles!
S Bodzin, Real American 🇺🇸
Ianagol@stevenbodzin @csk @jsm28 You’ll have two have two tiles manufactured, since some of the tiles are isometric by a reflection (and bathroom tiles usually cannot be flipped over).
Christian Lawson-Perfect
Louis Evans
LE Murphy@VividConfusion @jsm28 Well, we never said it looked like a kite -- it's made out of eight copies of a small unit kite shape. We agree that it looks like a shirt too, but the hat won out in the end.
That Dirk Guy@csk @VividConfusion @jsm28
Man, you missed out on a great monetization opportunity: T-Shirts printed with the tshirt monotile!
Man, you missed out on a great monetization opportunity: T-Shirts printed with the tshirt monotile!
me@csk
Sometimes I wish M.C. Escher would still be alive to see this.
Sometimes I wish M.C. Escher would still be alive to see this.
CurtAdams
Bill Woodcock@csk @jsm28
Sorry, naive question from a non-mathematician... Your figure on pp.2 uses two tile-shapes with mirror symmetry. Am I not understanding the claim that this is a single non-repeating tile, or is it just not easy to actually find a fit that allows tiling?
Sorry, naive question from a non-mathematician... Your figure on pp.2 uses two tile-shapes with mirror symmetry. Am I not understanding the claim that this is a single non-repeating tile, or is it just not easy to actually find a fit that allows tiling?
benjohn
Joseph Myers@benjohn @csk The idea for those proof structure diagrams came from e.g. Greenfeld-Tao 2022 (see page 5 of their preprint). https://arxiv.org/abs/2211.15847
A counterexample to the periodic tiling conjecture
The periodic tiling conjecture asserts that any finite subset of a lattice $\mathbb{Z}^d$ which tiles that lattice by translations, in fact tiles periodically. In this work we disprove this conjecture for sufficiently large $d$, which also implies a disproof of the corresponding conjecture for Euclidean spaces $\mathbb{R}^d$. In fact, we also obtain a counterexample in a group of the form $\mathbb{Z}^2 \times G_0$ for some finite abelian $2$-group $G_0$. Our methods rely on encoding a "Sudoku puzzle" whose rows and other non-horizontal lines are constrained to lie in a certain class of "$2$-adically structured functions," in terms of certain functional equations that can be encoded in turn as a single tiling equation, and then demonstrating that solutions to this Sudoku puzzle exist, but are all non-periodic.