[math-fun] Nice solution of "einstein" 1D tile problem
Nice solution of "einstein" 1D tile problem Warren D. Smith Nov 2011 Rich Schroeppel stimulated my brain rather like LSD, and overnight I found a solution! Plan of this post: 1. re-state the problem 2. re-state Schroeppel's impossibility proof plus some souped-up versions of it 3. Construct the sought-for 1D einstein tile (which indeed is "fractal" in nature) and prove it tiles but only in an aperiodic manner. 1. THE PROBLEM Does there exist a 1D einstein tile, i.e. a subset T of the real line with positive measure, such that (a) it tiles the whole line (b) it does so only in an aperiodic manner? "Tiles" for us shall mean there is a countably-infinite set S of translates of T [and we optionally could also permit mirror(T)] which are interior-disjoint and which cover the whole line. A sufficient condition for "aperiodic" is that the set S of translations cannot include any arithmetic progression. 2. IMPOSSIBILITY THEOREMS THM 1 (R.C.Schroeppel): If your single 1D tile can be reduced to a finite set of nonnegative integers, including 0 for definiteness, then any tiling can be converted to a periodic one. PROOF: Suppose the integers are covered by some tiling. For each K, consider the set of integers >K which are covered by some tile that begins at a value <=K. This set is of bounded width, not exceeding the width of the tile. So there are at most 2^width possible shapes for the set. BY pigeonhole principle, somewhere in the first 2^width+1 integers, there will be a K' and K'' with congruent sets (i.e., shifted by K''-K'). The supertile defined by the shift, i.e. tiles covering up to K'' but not entirely <=K', has a set of holes on the left that matches the covered squares on the right. So this supertile makes a periodic covering of the integers. QED. THM 2: Any tile consisting of a finite number of connected components, if it tiles at all, can also be tiled in a periodic manner. PROOF: Assume tile T has width=W, #connected components=C, and measure=A, all positive, C finite. It is easy to see neither W nor A can be infinite: if W were, A would be; if A is then at most 2 tiles could be interior-disjoint, but our defn of "tiling" demands infinite set of tiles. [There do exist tilings of the real line by 2 infinite tiles, of course. They are boring.] Consider the tiles which lie entirely within the right half-line, ordered by leftmost point. After some finite start, each has location given by the first gap in the set composed of the tiles to its left. Hence all locations are specified for us (after some finite start). The tiling is a set of intervals on the real line each labeled with its tile# and tile-orientation {0,1}. Within each segment of length W on the line sufficiently far to the right there can be at most 3*W/A tiles involved and the number of intervals involved is <=3*C*W/A and the number of possible patterns within said segment is thus <=(6*C*W/A)^(3*C*W/A). So now within a segment of length W*[(6*C*W/A)^(3*C*W/A) + 1] chopped into (6*C*W/A)^(3*C*W/A)+1 subsegments of length W we must by pigeonhole principle have at least two subsegments containing identical patterns... hence can tile periodically. QED. THM 3: Any tile of finite width W>0, if it tiles at all, can also be tiled in a periodic manner. PROOF SKETCH: Let tile T have measure=A, width=W, all these positive, W finite. It has C connected components. By THM 2 we may assume wlog that C=infinity. Hence there must be at least one accumulation point within T. The accumulation points cannot be everywhere dense within T otherwise T would be unmeasurable. So there must be some isolated accumulation points. Now if two tiles's minimum containing intervals overlap, then the accumulation points of one, must either lie within an empty subinterval of the other, or must coincide with an accumulation point of the other. Every accumulation point within a tile, must coincide with at least one accumulation point within some other tile of the tiling. Argue similarly to last proof but note the pattern after some point can be described by a binary string like 01100110101010101001... which means "walk rightward; each time you encounter a real not within a previous tile, add a new tile that starts there and is oriented according to the next bit." The number of possible binary patterns within a region of width W is <=2^(3*W/A) since at most 3*W/A tiles can be involved. Now the accumulation-point matchup requirements among these <=3*W/A tiles force each tile to contain at most a FINITE set of accumulation points, say at most F. Call two tiles "AP-adjacent" if one of the firsts's accumulation points coincides with one of the second's. Consider the subset of our tiling got by starting at tile #1 and then finding all tiles AP-adjacent to it, and all tiles AP-adjacent to any of them, and so on forever. This subtiling has finite density lower bounded by a positive constant. Now we can pigeonhole argue like before that it must contain a repeating pattern and hence must be periodic. There can be at most some finite number G of these subtilings (i.e. there are at most G different AP-connected components in the tiling). Hence we can now do a larger pigeonhole argument that shows we get a repeating pattern on the whole shebang which therefore must be periodic-ifiable. QED. 3. CONSTRUCTION of 1D EINSTEIN TILE THM 4: The following subset of the integers, will tile the nonnegative integers by translation only (no mirroring needed) but will only do so aperiodically: T = {nonnegative integers whose digits all are even}. PROOF: A suitable set S of translations is S = {nonnegative integers whose digits all are either 0 or 1}. Then every integer>=0 is covered, and every such integer is covered exactly once. Now to prove no periodic tiling is possible, note that S+T=Znonneg where "+" denotes Minkowski sum of sets, i.e the set of all s+t wwhere s in S and t in T. Because tiling, these s+t all are DISJOINT. Now the key thing is S+T=T+S whenever we have such disjointness. Therefore, we can also "dually" regard the tiling by tiles T via translations S, as a tiling of S by translations T. Note T is infinite but has density=0. (Also our recommended S is infintie and with density=0.) But if any other S worked and that S contained an arithmetic progresion, then this S would have density>0. Hnece it would be impossible to tile an infinite number of disjoint copies of S. Hence by duality it is impossible to tile T by any set S of translations, where S contains an arithmetic progression. QED. FRACTALITY: Note that our set T is "fractal" in that the number of integers x in T with 0<=x<X, behaves for large X like X^(ln5/ln10) = X^0.69897000433601880... And our recommended set S also is fractal in that the number of integers x in S with 0<=x<X, behaves for large X like X^(ln2/ln10) = X^0.301029995663981195... --end.
Warren, Your sets S and T came up in an earlier post by Tom Rokicki (September 29, 2010): "Another simple decimal pair: a is all numbers composed of 0's and 1's. b is all numbers composed of even digits. -tom" Socolar and Taylor (S & T again!) came up with a nice 2D einstein: http://arxiv.org/abs/1009.1419 While it's not connected, it's not fractal. Veit On Nov 12, 2011, at 8:06 AM, Warren Smith wrote:
Nice solution of "einstein" 1D tile problem
Warren D. Smith Nov 2011
Rich Schroeppel stimulated my brain rather like LSD, and overnight I found a solution! Plan of this post: 1. re-state the problem 2. re-state Schroeppel's impossibility proof plus some souped-up versions of it 3. Construct the sought-for 1D einstein tile (which indeed is "fractal" in nature) and prove it tiles but only in an aperiodic manner.
1. THE PROBLEM
Does there exist a 1D einstein tile, i.e. a subset T of the real line with positive measure, such that (a) it tiles the whole line (b) it does so only in an aperiodic manner?
"Tiles" for us shall mean there is a countably-infinite set S of translates of T [and we optionally could also permit mirror(T)] which are interior-disjoint and which cover the whole line.
A sufficient condition for "aperiodic" is that the set S of translations cannot include any arithmetic progression.
2. IMPOSSIBILITY THEOREMS
THM 1 (R.C.Schroeppel): If your single 1D tile can be reduced to a finite set of nonnegative integers, including 0 for definiteness, then any tiling can be converted to a periodic one.
PROOF: Suppose the integers are covered by some tiling. For each K, consider the set of integers >K which are covered by some tile that begins at a value <=K. This set is of bounded width, not exceeding the width of the tile. So there are at most 2^width possible shapes for the set. BY pigeonhole principle, somewhere in the first 2^width+1 integers, there will be a K' and K'' with congruent sets (i.e., shifted by K''-K'). The supertile defined by the shift, i.e. tiles covering up to K'' but not entirely <=K', has a set of holes on the left that matches the covered squares on the right. So this supertile makes a periodic covering of the integers. QED.
THM 2: Any tile consisting of a finite number of connected components, if it tiles at all, can also be tiled in a periodic manner.
PROOF: Assume tile T has width=W, #connected components=C, and measure=A, all positive, C finite. It is easy to see neither W nor A can be infinite: if W were, A would be; if A is then at most 2 tiles could be interior-disjoint, but our defn of "tiling" demands infinite set of tiles. [There do exist tilings of the real line by 2 infinite tiles, of course. They are boring.] Consider the tiles which lie entirely within the right half-line, ordered by leftmost point. After some finite start, each has location given by the first gap in the set composed of the tiles to its left. Hence all locations are specified for us (after some finite start). The tiling is a set of intervals on the real line each labeled with its tile# and tile-orientation {0,1}. Within each segment of length W on the line sufficiently far to the right there can be at most 3*W/A tiles involved and the number of intervals involved is <=3*C*W/A and the number of possible patterns within said segment is thus <=(6*C*W/A)^(3*C*W/A). So now within a segment of length W*[(6*C*W/A)^(3*C*W/A) + 1] chopped into (6*C*W/A)^(3*C*W/A)+1 subsegments of length W we must by pigeonhole principle have at least two subsegments containing identical patterns... hence can tile periodically. QED.
THM 3: Any tile of finite width W>0, if it tiles at all, can also be tiled in a periodic manner.
PROOF SKETCH: Let tile T have measure=A, width=W, all these positive, W finite. It has C connected components. By THM 2 we may assume wlog that C=infinity. Hence there must be at least one accumulation point within T. The accumulation points cannot be everywhere dense within T otherwise T would be unmeasurable. So there must be some isolated accumulation points. Now if two tiles's minimum containing intervals overlap, then the accumulation points of one, must either lie within an empty subinterval of the other, or must coincide with an accumulation point of the other. Every accumulation point within a tile, must coincide with at least one accumulation point within some other tile of the tiling.
Argue similarly to last proof but note the pattern after some point can be described by a binary string like 01100110101010101001... which means "walk rightward; each time you encounter a real not within a previous tile, add a new tile that starts there and is oriented according to the next bit." The number of possible binary patterns within a region of width W is <=2^(3*W/A) since at most 3*W/A tiles can be involved. Now the accumulation-point matchup requirements among these <=3*W/A tiles force each tile to contain at most a FINITE set of accumulation points, say at most F.
Call two tiles "AP-adjacent" if one of the firsts's accumulation points coincides with one of the second's. Consider the subset of our tiling got by starting at tile #1 and then finding all tiles AP-adjacent to it, and all tiles AP-adjacent to any of them, and so on forever. This subtiling has finite density lower bounded by a positive constant. Now we can pigeonhole argue like before that it must contain a repeating pattern and hence must be periodic.
There can be at most some finite number G of these subtilings (i.e. there are at most G different AP-connected components in the tiling). Hence we can now do a larger pigeonhole argument that shows we get a repeating pattern on the whole shebang which therefore must be periodic-ifiable. QED.
3. CONSTRUCTION of 1D EINSTEIN TILE
THM 4: The following subset of the integers, will tile the nonnegative integers by translation only (no mirroring needed) but will only do so aperiodically: T = {nonnegative integers whose digits all are even}.
PROOF: A suitable set S of translations is S = {nonnegative integers whose digits all are either 0 or 1}. Then every integer>=0 is covered, and every such integer is covered exactly once.
Now to prove no periodic tiling is possible, note that S+T=Znonneg where "+" denotes Minkowski sum of sets, i.e the set of all s+t wwhere s in S and t in T. Because tiling, these s+t all are DISJOINT. Now the key thing is S+T=T+S whenever we have such disjointness. Therefore, we can also "dually" regard the tiling by tiles T via translations S, as a tiling of S by translations T. Note T is infinite but has density=0. (Also our recommended S is infintie and with density=0.) But if any other S worked and that S contained an arithmetic progresion, then this S would have density>0. Hnece it would be impossible to tile an infinite number of disjoint copies of S. Hence by duality it is impossible to tile T by any set S of translations, where S contains an arithmetic progression. QED.
FRACTALITY: Note that our set T is "fractal" in that the number of integers x in T with 0<=x<X, behaves for large X like X^(ln5/ln10) = X^0.69897000433601880... And our recommended set S also is fractal in that the number of integers x in S with 0<=x<X, behaves for large X like X^(ln2/ln10) = X^0.301029995663981195...
--end.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Sorry, it appears my "proof sketch" of the impossibility theorem 3 was too facile... though probably the same general idea just done more carefully, will prove it... I hope. The other theorems there still are ok, far as I currently know... By using mixed-radix number systems instead of base 10, the einstein-tile construction can be redone in any of a continuum-infinite number of genuinely different ways. (Can this infinity be boosted to an even higher infinity?) It also is interesting to note that the tilings suggested are not even a "quasicrystal." As a sanity check (always a good idea...) it might be interesting to draw a picture of one of them. I guess the nicest (?) is the version based on radix=4 at all positions. In the picture, if we color touching-tiles differently, then how many colors will be required? For each K>0 there is a tile which touches at least K others (as you can see by considering the numbers ending in a <=K-long string of 9s or string of 0s...). But this alone does not suffice to show we need infinity colors. And in fact I think every tile only touches a finite number of others with the "average" number of neighbors being bounded, which suggests that only a small finite number of colors is required.
Veit Elser: Your sets S and T came up in an earlier post by Tom Rokicki (September 29, 2010): "Another simple decimal pair: a is all numbers composed of 0's and 1's. b is all numbers composed of even digits. -tom" Socolar and Taylor (S & T again!) came up with a nice 2D einstein: http://arxiv.org/abs/1009.1419 While it's not connected, it's not fractal. --truly this list is all-knowing :) This Rokicki/Smith construction actually works in any number D of dimensions, if you use the tile got by cartesian-producting my tile with itself D times. [Then there is no D-vector arithmetic progression contained in the translations, which is a strong non-periodicity statement.]
participants (2)
-
Veit Elser -
Warren Smith