crystals
Article
Methods for Calculating Empires in Quasicrystals
Fang Fang *,
ID , Dugan Hammock and Klee Irwin
ID
Quantum Gravity Research, Los Angeles, CA 90290, USA; dugan@QuantumGravityResearch.org (D.H.);
Klee@quantumgravityresearch.org (K.I.)
* Correspondence: fang@quantumgravityresearch.org; Tel.: +1-310-574-6934
Academic Editor: Dmitry A. Shulyatev
Received: 31 August 2017; Accepted: 29 September 2017; Published: 9 October 2017
Abstract: This paper reviews the empire problem for quasiperiodic tilings and the existing methods for
generating the empires of the vertex configurations in quasicrystals, while introducing a new and more
efficient method based on the cut-and-project technique. Using Penrose tiling as an example, this method
finds the forced tiles with the restrictions in the high dimensional lattice (the mother lattice) that can be
cut-and-projected into the lower dimensional quasicrystal. We compare our method to the two existing
methods, namely one method that uses the algorithm of the Fibonacci chain to force the Ammann bars
in order to find the forced tiles of an empire and the method that follows the work of N.G. de Bruijn
on constructing a Penrose tiling as the dual to a pentagrid. This new method is not only conceptually
simple and clear, but it also allows us to calculate the empires of the vertex configurations in a defected
quasicrystal by reversing the configuration of the quasicrystal to its higher dimensional lattice, where we
then apply the restrictions. These advantages may provide a key guiding principle for phason dynamics
and an important tool for self error-correction in quasicrystal growth.
Keywords: quasicrystals; empires; forced tiles; cut-and-project; defects
1. Introduction—What Is the Empire Problem?
When compared with regular crystals, quasicrystals present more complex structures and
variations and have dynamic patterns that can be non-local due to the non-local nature of the
quasicrystal itself [1]. Although not obvious, it is true that a given local patch of tiles in a quasicrystal
can force tiles to lie in non-adjacent (non-local) positions. This set of tiles, which are forced by a given
vertex type, or in this paper extended to any local patch of tiling, represents the empire of the local patch
in the quasicrystal [2], a term originally coined by Conway [3]. The problem of finding these forced
tiles for a certain configuration of a quasicrystal [4] is referred to as the empire problem in this paper.
Local matching rules serve as a tool to grow an infinite tiling by constraining the way neighboring
tiles can join together. However, these local rules tend to result in deception and/or “holes” or
“dead surfaces” and therefore cannot grow an infinite perfect quasicrystal [5]. Non-local information
is needed to guide a perfect growth of an infinite quasicrystal and its dynamics. The empires of the
quasicrystals contain this non-local information and therefore can in principle be used as generators of
quasicrystals. Mastering the efficient method of obtaining the empires is thus important for modeling
the quasicrystal growth and phason dynamics in quasicrystals.
In this paper, we discuss three methods for generating the empires of the vertex configurations in
quasicrystals, using Penrose tiling as an example. In Section 2, we calculate the empires of the simplest
one dimensional quasicrystal, the Fibonacci chain, using the legal matching rules between local tiles.
Then we demonstrate how to obtain the empires of a 2D quasicrystal, Penrose tiling, using the empires
of this 1D Fibonacci chain. This method was first introduced in [2] and named the Fibonacci chain
method in this paper. In Section 3, we review the multigrid method for generating the empires of
the Penrose tiling [4]. Based on the cut-and-project technique [6,7], we introduce a new method for
Crystals 2017, 7, 304; doi:10.3390/cryst7100304
www.mdpi.com/journal/crystals
Crystals 2017, 7, 304
2 of 21
calculating the empires of quasicrystals of any dimension in Section 4 and we compare it with the
previous methods in Section 5. In Section 6, we present our conclusions and outlook.
2. The Fibonacci-Grid Method
The empire problem, the problem of finding out which tiles are forced given an initial set of tiles,
was first explored by analyzing Ammann bars, a decoration for Penrose tiles realized as a network of
five sets of parallel lines. This method was extended by Minnick [8]. Due to the fact that it uses the
empire of the Ammann bars, which is in fact a Fibonacci pentagrid [9] of the Penrose tiling, we name
the method used in this case the Fibonacci-grid method.
The prolate and oblate rhombuses in Penrose tiling can be decorated using line segments as
shown in Figure 1. When two tiles meet along an edge, the line segments from one tile meet the
segments from the other at straight angles, forming extended lines which are called the Ammann
bars [2]. These matching rules using the Ammann bars are equivalent to the single- and double-arrow
matching rules for Penrose tiling.
Figure 1. The prolate and oblate rhombuses in Penrose tiling decorated with segment lines.
When looking at a large enough Penrose tiling, the Ammann bars extend to form lines which
crisscross the plane in a very structured way, as shown in Figure 2. These lines can be grouped together
to form five distinct families of parallel lines called grids, where each grid consists of lines normal to
one of the following five vectors~ei = (cos(2πi/5), sin(2πi/5)), where i = 0, 1, ..., 4. The gaps between
neighboring parallel lines are represented by two values, a “long” gap L and a “short” gap S, where the
ratio between these two distances is the golden ratio φ = (1 +
√
5)/2. The gaps for a particular grid
from a sequence of long and short gaps, denoted by a sequence of L’s and S’s.
These sequences turn out to be Fibonacci chains, or Fibonacci words, which represent the simplest one
dimensional quasicrystals and which can be generated by the following iterative process. Let us start with
the two words W0 = L and W1 = LS and let Wn = Wn−1Wn−2 be the concatenation of the previous two
words. The infinite Fibonacci word is defined to be the limit W∞ = LSLLSLSLLSLLS.... Alternatively, one
can start with W0 = L and apply the following substitution rules to iterate one word Wn to the next Wn+1.
L→ LS
S→
L
(1)
W0 = L
W1 = LS
W2 = LSL
W3 = LSLLS
W4 = LSLLSLSL
W5 = LSLLSLSLLSLLS
...
W∞ = LSLLSLSLLSLLSLSLLSLSLLSLLSLSLLSLLS . . .
(2)
Crystals 2017, 7, 304
3 of 21
Figure 2. Ammann bars in Penrose tiling.
The rules for creating the infinite Fibonacci word W∞ prohibit the formation of certain sub-words.
For instance, there cannot be three consecutive L’s appearing in W∞ nor can there be two S’s next to
each other. So LLL and SS are not valid Fibonacci chains, and if one has LL then the next letter must
be S. Likewise an S must always be followed by an L.
Since the Penrose tiling is indeed a network of these Fibonacci words, calculating the empires in
the Fibonacci words will directly lead us to the empires of the Penrose tiling.
Given an initial sub-word, W, one can identify its empires, which consists of all the letters that are
forced by the presence of W. For example, the word W = LL (shown in red) has the following empire
(shown in blue):
. . . SL · ·LSL · ·L · ·LSL · ·SLLLSL · ·LSL · ·L · ·LSL · ·LS . . .
(3)
While there is some freedom in choosing letters for the gaps in the empires, there is no freedom in
choosing letters at positions shown in blue. Whenever an LL is present in a Fibonacci chain, the 13th
letter following the LL is forced to be an L and the 19th letter is forced to be an S. The empires extend
to include an infinite number of letters.
We can apply this method to the Ammann bars, with the purpose of finding the empires in
Penrose tiling. For a given patch of tiles P = {T1, . . . , Tn}, where n is the number of tiles in T, there
will be some Ammann bars (from the same or from different parallel line sets) running through P.
Within each parallel line set i, the bars are separated with long and/or short gaps between them
forming the given initial word Wi, where i = 0, 1, ..., 4. The empires associated with each Wi can be
thus calculated and as a result, all other forced Ammann bars within the same grid can be found.
An example is shown in Figure 3, where the given patch at the center is colored red, the associated
bars are colored green and the empire or forced bars are colored blue. A tile or a small cluster of tiles is
forced where the Ammann lines intersect in a certain configuration. Detailed rules are discussed in [8].
As a result, the first set of the forced tiles are determined (colored blue in Figure 3). As the first set
of forced tiles are decided, more Ammann bars (colored red in Figure 3) can be forced by these tiles,
which in turn will force other tiles, as a result of the intersection of the red bars with other red or blue
Crystals 2017, 7, 304
4 of 21
bars, as shown in Figure 3. For solving the empire problem, this approach is workable but tedious,
therefore impractical in modeling the growth or dynamics of quasicrystals.
Figure 3. An example of the resulting empire of the star vertex configuration. The blue bars are the
first set of the forced bars and the red ones are the second set. The center patch is the given vertex
configuration and the tiles surrounding it are the forced tiles that make up the empire.
3. The Multigrid Method
The multigrid method offers a robust algorithm for generating quasicrystalline tilings or
quasicrystals of Euclidean space Rn as well as the empires of the quasicrystals. A multigrid G is
the superposition of distinct grids. A grid G ⊂ Rn is a family of parallel hyperplanes. A grid with an
equal spacing between hyperplanes can be expressed as a countable union of hyperplanes which are
all normal to a non-zero grid vector~e ∈ Rn:
G =
⋃
k∈Z
Gk =
⋃
k∈Z
{~x ∈ Rn|~x ·~e + γ = k},
(4)
where each hyperplane Gk = {~x ∈ Rn|~e ·~x + γ = k} is indexed by an integer k ∈ Z and the quantity
γ ∈ R provides a shift of the grid away from the origin. The distance between neighboring hyperplanes
is equal to 1
‖~e‖ .
A tiling T of Rn can be constructed by taking the dual of the multigrid, meaning a point where m
hyperplanes intersect in the multigrid space will correspond to a 2m-sided polytope in the tiling space,
with opposite sides being parallel [10].
For constructing a Penrose tiling in R2, the pentagrid, a multigrid consisting of five grids is used.
We define a pentagrid as a set of five grids in the plane (Figure 4) Gi ⊂ R2 for i = 0, . . . , 4,
where each grid Gi has an associated unit-length grid vector~ei and shift γi (Figure 5), but rather than
indexing the grids using the integers, we use the half-integers insteadk̃ = k + 1/2 ∈ Z+ 1/2.
Crystals 2017, 7, 304
5 of 21