# Parallelogram frameworks and flexible quasicrystals

S. C. Power  Dept. Math. Stats.
Lancaster University
Lancaster LA1 4YF
U.K<EMAIL_ADDRESS>
###### Abstract.

The first-order flex space of the bar-joint framework ${\mathcal{G}}_{P}$ of a
parallelogram tiling $P$ is determined in terms of an explicit free basis.
Applications are given to braced parallelogram frameworks and to quasicrystal
frameworks associated with multigrids in the sense of de Bruijn and Beenker.
In particular we characterise rigid bracing patterns, identify quasicrystal
frameworks with finite dimensional flex spaces, and define a zero mode
spectrum.

2010 Mathematics Subject Classification. 52C25, 52C23
Key words and phrases: braced parallelogram frameworks, multigrid
quasicrystals, zero modes.

##  1\. Introduction

A characterisation is obtained for the infinitesimal flex space of the bar-
joint framework ${\mathcal{G}}_{P}$ of a parallelogram tiling $P$ of the
plane. Of particular interest are the quasicrystal frameworks arising from
substitution systems or from tilings that are dual to multigrids. The Penrose
rhomb tilings and the Ammann-Beenker octagonal tilings given in Section 3.2
are perhaps the most well-known but there are many other striking tilings,
with $n$-fold symmetries, for arbitrary $n\geq 4$. See, for example, Baake and
Grimm [2] and the online resource [12]. The determination of infinitesimal
flexes is obtained in terms of a countable free basis, in the sense of Badri,
Kitson and Power [4], for the vector space of all infinitesimal flexes, where
the vector fields of the basis are explicit and are related to the infinite
ribbon structure of the tiling. Such an identification generally gives diverse
information on flexibility and rigidity and this is the case here.

In Theorem 2.3 we characterise the bracings of infinite parallelogram
frameworks which ensure first-order rigidity. The necessary and sufficient
condition, that the braces graph be connected and spanning, is the same
requirement as the well-known Bolker-Crapo condition [6], [20] for the
rigidity of finite braced rectangular grids. Finite braced Penrose frameworks
and parallelogram frameworks have been considered by Wester [25] and Francis
and Duarte [10] who show the sufficiency of the condition. Other proofs of
necessity and sufficiency in the finite case are due to Nagy Kem [17], through
a characterisation of associated tensegrity frameworks, and to Graseggar and
Legerský [14] who employ elegant combinatorial colouring arguments. These
methods are different from our direct approach exploiting the geometry of
parallelogram ribbons.

Bar-joint frameworks and their forms of flexibility provide mathematical
models in materials science for the flexibility and rigidity of network
materials. This can be seen in the analysis of floppy modes (infinitesimal
flexes) for Penrose rhomb quasicrystals and zero modes (floppy modes with wave
vectors) for crystals. For some recent examples see Rocklin et al [21],
Stenull and Lubensky [23], and Zhou et al [26]. In this direction we show that
general parallelogram frameworks do not admit floppy modes that tend to zero
at infinity (Corollary 2.4). Also, in Section 3 we consider regular multigrid
parallelogram tilings and associated quasicrystal frameworks which are
obtained by bracing patterns. We define _checkered quasicrystals_ in this way
and determine the finite dimension of their space of floppy modes (Theorem
3.10).

For multigrid parallelogram frameworks ${\mathcal{G}}_{P}$ we also
characterise linearly localised floppy modes (Theorem 3.7). The set of lines
through the origin for such flexes is shown to be equal to the _ribbon figure_
RF$(P)$ of $P$, a finite set of lines representing the directions of the
ribbons, and these directions are determined explicitly in Proposition 3.8.

For a crystallographic material the zero modes (rigid unit modes) and zero
mode spectrum (RUM spectrum) are determined, in accordance with Bloch’s
theorem, by a finite geometric data set, for a repeating block of bars and
joints, and by phase variations over translated blocks [8], [9], [19], [24].
Despite this apparent limitation zero modes capture many aspects of global
first order motion. Indeed, the RUM spectrum can be viewed as a generalised
Bohr spectrum for which the associated modes have dense linear span in the
space of almost periodic first-order motions [3]. It is of interest then to
formulate analogues, in the case of quasicrystals. We discuss some aspects of
this in the final section and define zero modes and a zero mode spectrum for
some quasicrystal bar-joint frameworks associated with multigrid parallelogram
tilings.

##  2\. Parallelogram frameworks

We first discuss general parallelogram bar-joint frameworks ${\mathcal{G}}$ in
${\mathbb{R}}^{2}$ and the nature of their first-order motions. In particular
we determine the structure of linearly localised motions and we characterise
the bracing patterns for a parallelogram framework that make it rigid.

A bar-joint framework ${\mathcal{G}}=(G,p)$ in ${\mathbb{R}}^{d}$ is a finite
or countable simple graph $G=(V,E)$ together with a placement
$p:V\to{\mathbb{R}}^{d}$ of its vertices. A real _infinitesimal flex_ of
${\mathcal{G}}$ is a vector field, or velocity field,
$u:p(V)\to{\mathbb{R}}^{d}$, that satisfies the first-order flex condition for
every bar. That is,

$\langle u(p(v))-u(p(w)),p(v)-p(w)\rangle=0,\quad\mbox{ for }vw\in E.$

The space ${\mathcal{F}}({\mathcal{G}})$ of these fields is a subspace of the
vector space ${\mathcal{V}}({\mathcal{G}})$ of all velocity fields, and
${\mathcal{G}}$ is said to be _infinitesimally rigid_ , or _first-order rigid_
, if it coincides with the space of _rigid motion infinitesimal flexes_. For
$d=2$ this is the 3-dimensional space spanned by a non-zero rotation
infinitesimal flex and 2 linearly independent translation infinitesimal
flexes.

A _parallelogram tiling_ $P$ is an embedded graph in ${\mathbb{R}}^{2}$
associated with a tiling of ${\mathbb{R}}^{2}$ by contiguous nondegenerate
parallelogram tiles. That is, nondisjoint tiles meet at a common vertex or
common edge, and tiles have positive area. We assume, moreover, to avoid
nonstandard tilings, that the set of tiles is connected in the sense that any
pair of tiles is connected by a path of contiguous tiles. A _parallelogram
bar-joint framework_ ${\mathcal{G}}_{P}$ in ${\mathbb{R}}^{2}$ is a bar-joint
framework whose embedded graph is a parallelogram tiling $P$. In particular
${\mathcal{G}}_{P}$ possesses evident shearing motions associated with so-
called ribbons of parallelograms. A _ribbon_ of $P$ is a 2-way infinite path
of adjacent tiles for which the shared edges have a common direction. We
define a _ribbon shear_ of ${\mathcal{G}}_{P}$ to be an infinitesimal flex
which is the zero vector on all joints on one side of the ribbon, including
the ribbon boundary, and assigns a common non-zero velocity vector to the
other joints.

The following simple fact will be useful in the proof of Theorem 2.3. See also
Frettlöh and Harriss [11].

Figure 1. A pair of impossible ribbons.

######  Lemma 2.1.

A pair of ribbons of a parallelogram tiling share at most one tile.

###### Proof.

Suppose that distinct ribbons $R_{1}$ and $R_{2}$ cross twice, at tiles
$T_{a},T_{b}$. These tiles are necessarily translationally equivalent.
Consider the parts of these ribbons that exit tile $T_{a}$ and enter tile
$T_{b}$. By the parallelogram structure of the ribbons these parts lie
entirely in the same closed region bounded by lines $L_{1},L_{2}$ through two
edges of $T_{b}$. Therefore, as Figure 1 illustrates, these parts of the
ribbons must cross at another tile. However we could have chosen $T_{b}$ to be
the first tile encountered for a further crossing. This gives the desired
contradiction. ∎

###  2.1. The flex space of a parallelogram framework

Let ${\mathcal{G}}$ be a countable bar-joint framework. A sequence $u^{(n)}$
of velocity fields in ${\mathcal{V}}({\mathcal{G}})$ _tends to zero strictly_
if for every joint $p_{i}$ of ${\mathcal{G}}$ the velocities $u^{(n)}(p_{i})$
are nonzero for finitely many $n$. In this case any infinite sum
$\sum_{n}\alpha_{n}u^{(n)}$, with real scalars $\alpha_{n}$, defines a
velocity field. A _free spanning set_ for the space
${\mathcal{F}}({\mathcal{G}})$ of infinitesimal flexes is a countable set in
${\mathcal{F}}({\mathcal{G}})$ that tends to zero strictly, in any
enumeration, and is such that every infinitesimal flex in
${\mathcal{F}}({\mathcal{G}})$ has such an infinite sum representation. When
those sums are unique then we have the following definition of a free basis.
Free spanning sets and bases, and their symmetric variants for crystal
frameworks, were examined in Badri, Kitson and Power [4].

######  Definition 2.2.

A _free basis_ for the infinitesimal flex space ${\mathcal{F}}({\mathcal{G}})$
of a countable bar-joint framework ${\mathcal{G}}$ in ${\mathbb{R}}^{d}$ is a
countable set $u^{(n)}$ in ${\mathcal{F}}({\mathcal{G}})$ which tends to zero
strictly and is such that each infinitesimal flex has a unique infinite sum
representation $\sum_{n}\alpha_{n}u^{(n)}$.

In the proof of the next theorem we use the following notation for a
parallelogram framework ${\mathcal{G}}$ with a distinguished base joint
$p_{1}$. For each ribbon $\rho$ let $u^{\rho}$ be a nonzero ribbon shear for
$\rho$ which assigns the zero velocity vector to $p_{1}$. Thus $u^{\rho}$ has
zero velocities at all joints to one side of $\rho$, the side containing
$p_{1}$, and is a fixed velocity vector at all other joints. Let
${\mathcal{S}}$ be the set of these ribbon shears. In particular
${\mathcal{S}}$ is countable and in any enumeration the $u^{\rho}$ tend to
zero strictly. Let $u^{x},u^{y}$ be nonzero infinitesimal flexes for
translation in the direction of the $x$-axis and the $y$-axis respectively.

######  Theorem 2.3.

Let ${\mathcal{G}}$ be a parallelogram bar-joint framework with base joint
$p_{1}$ and an associated set ${\mathcal{S}}$ of ribbon shears. Then
${\mathcal{S}}\cup\\{u^{x},u^{y}\\}$ is a free basis for
${\mathcal{F}}({\mathcal{G}})$.

###### Proof.

Let $z$ be an infinitesimal flex. Subtract a unique linear combination of
$u^{x},u^{y}$, say $w_{1}$, to obtain the infinitesimal flex $z_{1}=z-w_{1}$
with $z_{1}(p_{1})=0$. Let $T_{0}$ be a tile that contains $p_{1}$ and let
$\rho_{a}$ and $\rho_{b}$ be the ribbons through $T_{0}$. We may add to
$w_{1}$ a unique linear combination of the two corresponding ribbon shears to
create $w_{2}$ and $z_{2}=z-w_{2}$ so that $z_{2}$ is zero on the 4 joints for
$T_{0}$. We say that the linear combination $w_{2}$ _cancels $z$ on the tile_
$T_{0}$, and that the ribbons ${\rho_{a}},{\rho_{b}}$ and the flexes
$u^{x},u^{y},u^{\rho_{a}},u^{\rho_{b}}$, _have been used_.

$a$$b$$c$$p_{1}$

Figure 2. Three ribbons for the patch $T_{0}\cup T_{1}\cup T_{2}$. The lower
tile, $T_{0}$, contains the vertex for the base joint $p_{1}$.

Let $T_{1}$ be a tile that is contiguous to $T_{0}$, in the sense that it
shares a tile edge with $T_{0}$, and lies on the unused ribbon $\rho_{c}$.
Since $u^{\rho_{c}}$ vanishes on the joints for $T_{0}$ we may add an
appropriate unique scalar multiple of $u^{\rho_{c}}$ to $w_{2}$ to obtain
$w_{3}$, which cancels $z$ on $T_{0}\cup T_{1}$. In this case we add
$\rho_{c}$ to the set of used ribbons.

If there is a further tile $T_{2}$ contiguous to the patch $T_{0}\cup T_{1}$
which lies on 2 used ribbons then 3 of its joints lie at boundary vertices of
this patch and so $z$ is also cancelled by $w_{3}$ on the larger connected
patch ${\mathcal{P}}_{0}=T_{0}\cup T_{1}\cup T_{2}$. Figure 2 illustrates such
a patch.

For the purposes of induction, assume that ${\mathcal{P}}$ is a simply
connected patch of tiles, containing $T_{0}$, whose topological boundary is a
simple closed curve. Also, suppose that ${\mathcal{S}}_{\mathcal{P}}$ is a
finite set of ribbon shears $u^{\rho}$ which have been used to obtain a unique
linear combination $w_{\mathcal{P}}$ that cancels $z$ on ${\mathcal{P}}$. In
particular each such ribbon $\rho$ includes at least one tile of the patch. We
also assume that, like ${\mathcal{P}}_{0}$, the patch is maximal in the sense
that there are no tiles outside ${\mathcal{P}}$ that have 3 or 4 vertices on
the boundary of ${\mathcal{P}}$.

Consider a tile $T$ not in ${\mathcal{P}}$ which shares an edge $e$ of
${\mathcal{P}}$. There is a unique ribbon $\tau$ which contains $T$ with $e$
lying in one of the two components of the boundary of $\tau$. We claim first
that $\tau$ contains no tiles of ${\mathcal{P}}$. Suppose that this were so.
Then, by the maximal property of ${\mathcal{P}}$ there is a nonempty patch
${\mathcal{Q}}$ of tiles between ${\mathcal{P}}$ and the boundary of $\tau$
containing $e$. See Figure 3. Indeed, if ${\mathcal{Q}}$ is empty then there
would have to be a final tile of $\tau$ outside ${\mathcal{P}}$ with 3
vertices in the boundary of ${\mathcal{P}}$. However, ${\mathcal{Q}}$ being
nonempty is also not possible. To see this assume that ${\mathcal{Q}}$ has the
least number of tiles for such a patch and that $T^{\prime}$ is a tile in
${\mathcal{Q}}$ contiguous to ${\mathcal{P}}$. Then there is a ribbon though
$T^{\prime}$ which, by Lemma 2.1, must re-enters ${\mathcal{P}}$, and this
contradicts the minimality of ${\mathcal{Q}}$.

Similarly, the set of tiles in $\tau$ that are contiguous to ${\mathcal{P}}$
must form a connected subset, or finite subribbon, of $\tau$. For otherwise
there is a tile in ${\mathcal{Q}}$ which shares an edge $f$ of the boundary of
${\mathcal{P}}$, as in Figure 3. This tile lies on a ribbon $\tau^{\prime}$
with $f$ in one of its boundary curves. By Lemma 2.1 $\tau^{\prime}$ must re-
enter ${\mathcal{P}}$ and this is not possible.

$e$$f$$\mathcal{P}$$\mathcal{Q}$

Figure 3. An impossible patch ${\mathcal{Q}}$ when $\tau$ is contiguous to
${\mathcal{P}}$.

Now let ${\mathcal{P}}^{+}$ be the union of the tiles of the subribbon with
${\mathcal{P}}$. Then there is a unique multiple of $u^{\tau}$ which when
added to $w_{\mathcal{P}}$ cancels $z$ on ${\mathcal{P}}^{+}$. Let
${{\mathcal{P}}_{1}}$ be the, necessarily finite, patch obtained from
${\mathcal{P}}^{+}$ by successively adding tiles that share 3 vertices of the
boundary.

In this way we complete an induction step. Moreover we may choose $T$
arbitrarily and so, since the tile-adjacency graph is connected, by our
standing assumptions for $P$, it follows that a sequence of such choices is
possible so that the union of the tiles of the resulting patch chain
${\mathcal{P}}_{1},{\mathcal{P}}_{2},\dots$ is the tiling $P$.

Note that the patch chain construction is independent of the infinitesimal
flex $z$, and so we obtain a set ${\mathcal{S}}_{0}$ of ribbon shears which,
together with $u^{x},u^{y}$ give a free basis for
${\mathcal{F}}({\mathcal{G}})$.

Finally we show that ${\mathcal{S}}_{0}={\mathcal{S}}$. Let
$u^{\sigma}\in{\mathcal{S}}\backslash{\mathcal{S}}_{0}$. Then, since
$u^{\sigma}(p_{1})=0$ there is, by the construction above, a unique
representation of the form
$u^{\sigma}=\sum_{\rho\in{\mathcal{S}}_{0}}\alpha_{\rho}u^{\rho}$ (where we
write ${\rho\in{\mathcal{S}}_{0}}$ to denote
${u^{\rho}\in{\mathcal{S}}_{0}}$). Let $\tau\in{\mathcal{S}}_{0}$ be a ribbon
that crosses $\sigma$. Such ribbons exist since by the inductive construction
every parallelogram lies on some ribbon of ${\mathcal{S}}_{0}$. Let
${\mathcal{T}}$ be the 4-bar framework for the tile $T$ common to $\sigma$ and
$\tau$. Since the restriction $u^{\sigma^{\prime}}|_{\mathcal{T}}$ is an
infinitesimal translation of ${\mathcal{T}}$, for every
$\sigma^{\prime}\neq\sigma,\tau$, it follows that $u^{\sigma}|_{\mathcal{T}}$
and $\alpha_{\tau}u^{\tau}|_{\mathcal{T}}$ differ by a translation. But
$u^{\sigma}$ and $u^{\tau}$ both have zero velocity vector on a joint of
${\mathcal{T}}$ and so we obtain the contradiction
$u^{\sigma}|_{\mathcal{T}}=\alpha_{\tau}u^{\tau}|_{\mathcal{T}}$, as desired.
∎

In view of our assumptions for a parallelogram tiling $P$ there are only
finitely many vertices of $P$ in any disc $D(0,r)$ about the origin of finite
radius $r$. We say that an infinitesimal flex $u$ of ${\mathcal{G}}_{P}$
_tends to zero at infinity_ if for each $\epsilon>0$ there is a radius $R>0$
such that $\|u(p_{i})\|_{2}<\epsilon$ for all joints $p_{i}$ located outside
$D(0,R)$. Equivalently, for any enumeration of the joints,
$p_{1},p_{2},\dots$, the sequence of velocities $u(p_{1}),u(p_{2}),\dots$
tends to zero.

######  Corollary 2.4.

A parallelogram framework has no nonzero infinitesimal flex which tends to
zero at infinity. In particular there are no nonzero infinitesimal flexes
which are finitely supported or which are square-summable.

###### Proof.

Suppose that the infinitesimal flex $u$ of a parallelogram framework
${\mathcal{G}}$ tends to zero at infinity. Consider a free basis as in the
previous theorem, normalised so that the non zero velocity vector for each
$u_{\rho}$ has unit norm, and consider a representation

$u=\alpha_{x}u^{x}+\alpha_{y}u^{y}+\sum_{\rho\in{\mathcal{S}}}\alpha_{\rho}u^{\rho}.$

Consider a ribbon $\rho$ for which the coefficient $\alpha_{\rho}$ is nonzero.
Let $T_{1},T_{2},\dots$ be a sequence of tiles of $\rho$ which lie on the
distinct ribbons $\tau_{1},\tau_{2},\dots$. By our assumption, the restriction
of $u$ to the associated subframeworks ${\mathcal{T}}_{k}$ tends to zero. It
follows that there exists $k$ such that the restriction of
$\alpha_{\rho}u^{\rho}+\alpha_{\tau_{k}}u^{\tau_{k}}$ to the 4 joints of
${\mathcal{T}}_{k}$ have magnitude less than $1$. Indeed the restriction of
any other basis flex $u^{\sigma}$ is a translation flex of ${\mathcal{T}}_{k}$
and so, in view of the series representation, the restriction of
$\alpha_{\rho}u^{\rho}+\alpha_{\tau_{k}}u^{\tau_{k}}$ can be made arbitrarily
close to a translation. On the other hand these restrictions have a zero
velocity at one of the 4 joints of ${\mathcal{T}}_{k}$ and so the conclusion
follows. We now have a contradiction since each of the ribbon shears
$u^{\tau_{k}}$ vanishes on a joint of ${\mathcal{T}}_{k}$ where $u^{\rho}$ has
unit norm. ∎

######  Remark 2.5.

In Badri, Kitson and Power [4] it is shown by general infinite dimensional
linear algebra that the infinitesimal flex space of every countable bar-joint
framework ${\mathcal{G}}$ possesses free bases. However the proof is
nonconstructive and for a specific framework the utility of a free basis or
free spanning set comes from its association with the geometry of
${\mathcal{G}}$.

###  2.2. When braced parallelogram frameworks are rigid

A _braced parallelogram framework_ , denoted ${\mathcal{G}}({\mathcal{B}})$,
or ${\mathcal{G}}_{P}({\mathcal{B}})$, is a bar-joint framework obtained from
a parallelogram bar-joint framework ${\mathcal{G}}_{P}$ by the addition of
bars, known as braces, to parallelogram bar 4-cycles of ${\mathcal{G}}_{P}$.
The set ${\mathcal{B}}$ denotes the set of these bars and it is assumed that
at most one bar is added to any parallelogram bar 4-cycle. The associated
_braces graph_ , denoted $G({\mathcal{B}})$, has vertex set labelled by the
ribbons and edge set labelled by ${\mathcal{B}}$, or, equivalently, by the set
of tiles $T$ whose bar 4-cycles are braced. Thus, the edge associated with $T$
is $(\rho,\sigma)$ where $\rho,\sigma$ are the ribbons through $T$.

######  Theorem 2.6.

The braced parallelogram framework ${\mathcal{G}}({\mathcal{B}})$ is
infinitesimally rigid if and only if $G({\mathcal{B}})$ is connected and
spanning.

###### Proof.

We first show sufficiency. Let $u$ be an infinitesimal flex of
${\mathcal{G}}({\mathcal{B}})$. Subtracting a rigid motion infinitesimal flex
we may assume that the restriction of $u$ to the 4 joints of a braced tile
subframework ${\mathcal{T}}_{1}$, for the tile $T_{1}$, is zero. We show that
$u=0$. Considering the previous theorem, where $p_{1}$ a joint of $T_{1}$, we
have a representation $u=\sum_{\rho\in{\mathcal{S}}}\alpha_{\rho}u^{\rho}$.
Moreover, from the inductive specification of the coefficients in this sum we
have $\alpha_{\tau}=\alpha_{\sigma}=0$ for the ribbons $\tau,\sigma$ through
$T_{1}$. Let ${\mathcal{T}}_{2}$ be a braced tile subframework for a tile
$T_{2}$ which lies on $\tau$. Then, in view of the brace, the restriction
$u|_{{\mathcal{T}}_{2}}$ is a rigid motion infinitesimal flex. On the other
hand, if $\kappa$ is the other ribbon through $T_{2}$ then the restriction of
$\sum_{\rho\in{\mathcal{S}}}\alpha_{\rho}u^{\rho}$ to ${\mathcal{T}}_{2}$ is
equal to the restriction of $\alpha_{\kappa}u^{\kappa}$ plus an infinitesimal
translation. It follows that $\alpha_{\kappa}=0.$ Since the braces graph is
connected and spanning it follows that $\alpha_{\sigma}=0$ for every ribbon
$\sigma$, as required.

Note that if $G({\mathcal{B}})$ is not spanning then there is a ribbon $\rho$
with no associated braces and in this case $u^{\rho}$ is a nontrivial (non
rigid motion) infinitesimal flex of ${\mathcal{G}}({\mathcal{B}})$.

It remains to show that if $G({\mathcal{B}})$ is not connected then
${\mathcal{G}}({\mathcal{B}})$ has a nontrivial infinitesimal flex. Assume
then that the braces graph is a disjoint union of 2 graphs, with an associated
proper partition of the ribbons,
${\mathcal{R}}={\mathcal{R}}_{1}\cup{\mathcal{R}}_{2}$, and the braces,
${\mathcal{B}}={\mathcal{B}}_{1}\cup{\mathcal{B}}_{2}$. Let $u$ be an
infinitesimal flex with $u(p_{1})=0$. By Theorem 2.3 there exists a unique
representation

$u=u_{1}+u_{2},\quad
u_{1}=\sum_{\rho\in{\mathcal{R}}_{1}}\alpha_{\rho}u^{\rho},\quad
u_{2}=\sum_{\rho\in{\mathcal{R}}_{2}}\alpha_{\rho}u^{\rho}.$

We first show that in view of the partitioning the velocity field $u_{1}$, and
therefore $u_{2}$ also, is an infinitesimal flex of
${\mathcal{G}}({\mathcal{B}})$. Let ${\mathcal{T}}$ be the bar 4-cycle for a
tile $T$. If $T\in{\mathcal{B}}_{1}$ then every shearing flex $u^{\rho}$ for
$\rho\in{\mathcal{R}}_{2}$ restricts to an infinitesimal translation of
${\mathcal{T}}$. Thus $u_{2}$ restricts to an infinitesimal translation of
${\mathcal{T}}$ and so $u_{1}=u-u_{2}$ restricted to ${\mathcal{T}}$ is an
infinitesimal flex of ${\mathcal{T}}$. On the other hand if
$T\in{\mathcal{B}}_{2}$ then, similarly, $u_{1}$ restricts to a infinitesimal
translation of ${\mathcal{T}}$. It follows that $u_{1}$ is an infinitesimal
flex of ${\mathcal{G}}({\mathcal{B}})$.

To obtain the desired contradiction assume further that $u$ is a nonzero
infinitesimal rotation with $u(p_{1})=0$. Consider a pair
$\rho_{1}\in{\mathcal{R}}_{1},\rho_{2}\in{\mathcal{R}}_{2}$ with common tile
$T$. Since the restriction of $u$ to the corresponding 4-joint framework
${\mathcal{T}}$ is an infinitesimal rotation it follows that both
$\alpha_{\rho_{1}}$ and $\alpha_{\rho_{2}}$ are nonzero. This is because the
restriction of every $u^{\rho}$ with $\rho\neq\rho_{1},\rho_{2}$ is an
infinitesimal translation. Thus the restriction $u_{1}|{\mathcal{T}}$ is not a
rigid motion infinitesimal flex of ${\mathcal{T}}$ and so neither is $u_{1}$
itself. ∎

######  Remark 2.7.

It should be clear from the proofs that Theorem 2.3 and Theorem 2.6 have
counterparts for a finite parallelogram framework which is a maximal patch
with simply connected boundary, where maximal means that there are no triple
or quadruple of joints on the boundary which are the joints of a tile not in
the patch. Indeed in the inductive step from patch ${\mathcal{P}}$ to patch
${\mathcal{P}}^{+}$ in Theorem 2.3 there is a free choice of contiguous tile
$T$ to add to ${\mathcal{P}}$. Moreover, for the same reason, the proof also
applies to infinite patches which are simply connected and have the maximal
property.

In their combinatorial approach to the finite case Graseggar and Legerský [14]
consider a wider class of parallelogram frameworks, allowing crossing bars and
nonplanar underlying structure. Their requirement on the underlying graph is
that every ribbon is an edge cut in the sense that removing the edges of the
ribbon makes the graph disconnected.

Recently we have obtained characterisations of rigidity for finite and
infinite braced grids in the plane with respect to some non-Euclidean norms
[20]. It would be interesting to determine corresponding characterisations for
braced parallelogram frameworks and general norms.

###  2.3. Linearly localised flexes

A subset of vertices (resp. joints) of an embedded graph (resp. bar-joint
framework) in ${\mathbb{R}}^{2}$ is said to be _linearly localised_ , or
$H$-localised, if every vertex (resp. joint) of the subset is located within a
fixed distance of a line $H$ through the origin. Also a velocity field for a
bar-joint framework in the plane is said to be $H$-localised if its support is
$H$-localised.

######  Theorem 2.8.

Let ${\mathcal{G}}_{P}$ be a parallelogram bar-joint framework, with a choice
of ribbon shears $u^{\rho}$ relative to a particular base joint, and let $u$
be a velocity field. If $u$ is a nonzero $H$-localised infinitesimal flex then
it is a finite sum $u=\sum_{\rho\in F}\alpha_{\rho}u^{\rho}$, over
$H$-localised ribbons.

###### Proof.

By Theorem 2.3 an infinitesimal flex $u$ has an infinite sum representation
$u=\alpha_{x}u^{x}+\alpha_{y}u^{y}+\sum_{\rho}\alpha_{\rho}u^{\rho}$. Let $T$
be any tile with ribbons $\sigma,\tau$ and associated 4-bar framework
${\mathcal{T}}$. The restriction of any infinitesimal flex to ${\mathcal{T}}$
is a sum of an infinitesimal translation and a unique linear combination of
the restrictions of $u^{\sigma}$ and $u^{\tau}$. Also the restriction of other
ribbon shears to ${\mathcal{T}}$ are translation flexes. Thus, if the
restriction of $u$ to ${\mathcal{T}}$ is zero, then
$\alpha_{\sigma}=\alpha_{\tau}=0$.

Suppose now that $u$ is $H$-localised. If the ribbon $\rho$ is not
$H$-localised then it travels outside the support of $u$ and from the previous
paragraph $\alpha_{\rho}=0$. It remains to show that the number of ribbons
contained in a band of finite width is finite. This follows from our standing
assumptions for $P$. These imply that there is a finite path of tiles which
connects a pair of tiles on opposite sides of the ribbon. ∎

For an $H$-localised ribbon $\rho$ in a general parallelogram tiling $P$ we
may assign a unit vector nρ normal to $H$, a unit vector mρ in the direction
of the internal edges, and a unit vector tρ orthogonal to mρ. These vectors
are determined up to sign, and ${\bf t}_{\rho}$ or $-{\bf t}_{\rho}$ is the
flex direction for all the nonzero velocities of a ribbon shear $u^{\rho}$ of
${\mathcal{G}}_{P}$. See Figure 4. We refer to tρ and $-{\bf t}_{\rho}$ as
_tangential flex vectors_ for the ribbon $\rho$.

${\bf m}$${\bf n}$${\bf t}$$H$

Figure 4. An $H$-localised ribbon $\rho$ with associated unit vectors nρ, mρ
and tρ.

The following notation is useful for the next definition. For a line $H$
through the origin and $c>0$ let $U(H,c),V(H,c)$ be the closed connected sets
whose union is the set of points whose distance to $H$ is at least $c$.

######  Definition 2.9.

Let ${\mathcal{G}}$ be a countable bar-joint framework in ${\mathbb{R}}^{2}$.
A _bulk shear_ , or _$H$ -localised bulk shear_, of ${\mathcal{G}}$ is an
infinitesimal flex $u$ with the following property. There are distinct
velocity vectors $a,b$ in ${\mathbb{R}}^{2}$ and a pair $H,c$ such that if
$p_{i}\in U(H,c)$ (resp. $p_{i}\in V(H,c)$) then $u(p_{i})=a$ (resp.
$u(p_{i})=b$).

######  Theorem 2.10.

Let ${\mathcal{G}}_{P}$ be a parallelogram bar-joint framework with a choice
of ribbon shears $u^{\rho}$ relative to a particular base joint. Then a
velocity field $u$ of ${\mathcal{G}}_{P}$ is an $H$-localised bulk shear if
and only if it is a sum of a translational infinitesimal flex and a finite sum
$\sum_{\rho\in F}\alpha_{\rho}u^{\rho}$, over a set $F$ of $H$-localised
ribbons.

###### Proof.

Let $u$ be an $H$-localised bulk shear, with vector pair $a,b$ for the sets
$U(H,c),V(H,c)$. By Theorem 2.8 $u$ has a representation $u_{\rm
tr}+\sum_{\rho}\alpha_{\rho}u^{\rho}$, where $u_{\rm tr}$ is an infinitesimal
translation. Let $T$ be a tile lying in $U(H,c)$ or $V(H,c)$. Then the
restriction of $u$ to the associated bar 4-cycle ${\mathcal{T}}$ is a
translation. As in the proof of Theorem 2.8, it follows that $\alpha_{\rho}=0$
if the ribbon $\rho$ passes through $T$. Thus the summation for $u$ is the
same as the summation over $H$-localised ribbons. Once again, by our standing
assumptions for $P$, the sum is finite. ∎

Figure 5. Tilings with (a) no linearly localised ribbons, (b) two linearly
localised ribbons.

We now define two elementary geometric invariants for a general countable bar-
joint framework. These are particularly appropriate for parallelogram
frameworks.

######  Definition 2.11.

Let ${\mathcal{G}}$ be a countable bar-joint framework in ${\mathbb{R}}^{d}$,
for $d\geq 2$.

(i) The _linear flex figure_ , LFF$({\mathcal{G}})$, is the union of the set
of lines $H$ through the origin for which there exists a nonzero $H$-localised
infinitesimal flex.

(ii) The _bulk shear figure_ , BSF$({\mathcal{G}})$, is the union of the set
of lines $H$ through the origin for which there exists a nonzero $H$-localised
bulk shear.

Note that if ${\mathcal{G}}$ has a locally supported infinitesimal flex then
LFF$({\mathcal{G}})={\mathbb{R}}^{2}$. On the other hand Figure 5 indicates
parallelogram tilings with few linearly localised ribbons, the first having
none and the second with two, say $\rho,\sigma$. In fact the second tiling
gives a bar-joint framework ${\mathcal{G}}_{P}$ with no linearly localised
infinitesimal flexes, since the tangential flex vectors tρ and tσ are
different. Nevertheless ${\mathcal{G}}_{P}$ has $H$-localised bulk shears and
BSF$({\mathcal{G}}_{P})$ is equal to a vertical line through the origin.

##  3\. Multigrid frameworks

We now define parallelogram tilings $P$ that are associated in a dual way with
sets of lines. In the case of those determined by multigrids it is shown that
the ribbons are linearly localised and an explicit recipe is given for the
_ribbon figure_ RF$(P)$, which is defined as the union of lines through the
origin that record their directions. Also we identify various quasicrystal
frameworks whose infinitesimal flex spaces are finite dimensional.

###  3.1. Dual parallelogram tilings

Consider a tiling $P_{*}$ of the plane by convex polygons that arises from a
countable set of lines where no more than 2 lines intersect at a given point.
We assume moreover that the angles of intersection of the lines, and the
distances between parallel lines are bounded away from zero. We call such a
tiling a _regular line tiling_ and it follows that the lines fall into
finitely many equivalence classes of parallel lines. From $P_{*}$ we may
construct parallelogram tilings $P$ by the following scheme, where $P_{*}$
represents a plan for the construction of tiles of $P$ from the vertices of
$P_{*}$, and where the ribbons of $P$ correspond to the lines of $P_{*}$.

Start the construction with a choice of base face, $f_{*}$ say, of the regular
line tiling $P_{*}$ and a choice of positive _length_ or _weight_ ,
$\lambda(H)$, for each line $H$ through the origin representing a class of
parallel lines of $P_{*}$. If the face $f_{*}$ has $n$ edges then associate
with it a base vertex $v$ (in a another copy of ${\mathbb{R}}^{2}$) together
with $n$ incident edges where these edges are orthogonal to the directions $H$
of the edges of $f_{*}$ and have lengths $\lambda(H)$. From this star graph,
denoted $S(v)$, add pairs of edges to consecutive pairs of edges to create $n$
parallelograms incident to $v$. In this way we create $n$ new vertices,
$v_{1},\dots,v_{n}$. These vertices correspond to the faces of $P_{*}$ which
are contiguous to $f_{*}$, say $f_{1}^{*},\dots,f_{n}^{*}$. Thus, the vertex
$v$ for the base face $f_{*}$ defines a base patch $P(v,1)$ which is
determined in 2 steps, namely, the addition of edges to $v$, to create its
star graph, followed by parallelogram completion.

This 2-step construction can be repeated for the new vertices; the base patch
is enlarged by completing the star graph $S(v_{1})$ for $v_{1}$ (some edges
are already determined) together with its parallelogram completion. The result
can be viewed as the join of the patch $P(v,1)$ with the patch $P(v_{1},1)$
over their common edges. It follows from this that the process of star patch
addition can be continued in a unique way for the vertices $v_{2},\dots,v_{n}$
(in any order). In view of our assumptions for $P_{*}$ there is a lower bound
for the areas of constructed parallelograms and so the construction can be
continued to create a unique parallelogram tiling $P$. Specifically we may
choose the order of star patch additions to follow an exhaustive enumeration
of the faces of $P_{*}$ where consecutive faces of the sequence are adjacent.
We denote the parallelogram tiling $P$, which is determined uniquely up to
translation, as $P(P_{*},\lambda)$.

######  Definition 3.1.

A _dual parallelogram tiling_ is a parallelogram tiling of the form
$P(P_{*},\lambda)$ for some regular line tiling $P_{*}$.

Not all parallelogram tilings have preduals which are regular line tilings.
This is the case for the tiling suggested by Figure 6, where a crossing pair
of ribbons lies between a noncrossing pair. On the other hand one can view
general parallelogram tilings as constructed in a similar dual way relative to
a network of curves running through the ribbons [5].

Figure 6. Part of a parallelogram tiling $P$ that is not dual to a regular
line tiling.

###  3.2. Multigrid quasicrystals

A significant family of dual parallelogram tilings arises from multigrids. The
following definitions are convenient.

######  Definition 3.2.

(i) A _multigrid_ in ${\mathbb{R}}^{2}$ is a set of lines
$A_{1}({\mathcal{L}})\cup\dots\cup A_{r}({{\mathcal{L}}})$ where
${\mathcal{L}}$ is the set of lines parallel to the $y$-axis, with integer
intercepts on the $x$-axis, and where $A_{1},\dots,A_{r}$ are affine
automorphisms of ${\mathbb{R}}^{2}$. A multigrid is _regular_ if the component
grids $A_{i}({{\mathcal{L}}})$ have distinct directions and every triple of
lines has an empty intersection.

(ii) A _multigrid parallelogram tiling_ is a parallelogram tiling that is dual
to a multigrid.

Define a _regular de Bruijn pentagrid_ to be the regular multigrid given by
$A_{1},\dots,A_{5}$ where
$A_{k}(z)=R_{k}z+(\gamma_{k},0),z\in{\mathbb{R}}^{2},$ where $R_{k}$ is
clockwise rotation by $2\pi(k-1)/5$, and where
$\gamma_{1}+\dots+\gamma_{5}=0$. The associated multigrid parallelogram
tilings, with rhombic parallelograms, are examples of Penrose tilings. For
these tilings $P$ the ribbon figure RF$(P)$ consists of 5 lines through the
origin parallel to the 5 individual grid lines of the pentagrid.

Figure 7. Two arrow-decorated rhombs, with interior angles
$72^{\circ},36^{\circ}$.

To be more precise about the nature of Penrose tilings, consider the thick and
thin rhomb tiles of Figure 7, with base edges parallel to the $x$-axis, each
with an arrow decoration. Two further decorations arise by rotation by $\pi$
and a totality of 20 decorated rhomb tiles is obtained by including the 16
further decorated tiles obtained by rotations by $2(k-1)\pi/5$, for $2\leq
k\leq 5$.

######  Definition 3.3.

A _decorated Penrose rhomb tiling_ , or arrowed rhomb tiling (AR tiling), is a
decoration-matched tiling of the plane by thick and thin decorated rhombs. A
_Penrose rhomb tiling_ is a tiling obtained by undecorating an AR tiling.

In 1981 de Bruijn [7] defined Penrose rhomb tilings in this way and showed how
they are related to (possibly nonregular) pentagrid parallelogram tilings.
Also he obtained fundamental properties, such as aperiodicity, local
isomorphism and substitution rules, and showed the connection with the
projection method construction via lattices in ${\mathbb{R}}^{5}$. Penrose’s
original inflation construction gives a particular subset of the AR tilings.
An overview of de Bruijn’s work and connections with physical quasicrystals
and diffraction is given by Au-Yang and Perk [1].

Beenker [5] extended de Bruijn’s algebraic methods to tetragrids, that is, to
4-fold grids. These multigrids give rise in particular to the so-called
Ammann-Beenker tilings, or octagonal tilings, with 2 tile types up to
congruency, namely a square and a $\pi/4$ rhombus. Despite the simplicity of
their construction there are 41 different types of vertex up to translation.
Socolar [22] subsequently gave a detailed geometric analysis including the
decagonal case, with tilings by hexagons, squares and $\pi/12$ rhombs.
Moreover, Gahler and Rhyner [13] have given the equivalence between a somewhat
more general construction of parallelogram tilings for multigrids and the
projection method construction.

The following observations follow from Theorem 2.6.

######  Corollary 3.4.

(i) Let $P$ be a regular Penrose rhomb tiling and let ${\mathcal{B}}$ be the
set of thick tiles or the set of thin tiles. Then the braced framework
${\mathcal{G}}_{P}({\mathcal{B}})$, obtained from ${\mathcal{G}}_{P}$ by
bracing the tiles of ${\mathcal{B}}$, is infinitesimally rigid. (ii) Let $P$
be an Ammann-Beenker tiling and let $B$ be the set of square tiles. Then the
braced framework ${\mathcal{G}}({\mathcal{B}})$ is infinitesimally flexible.

###### Proof.

(i) Suppose ${\mathcal{B}}$ is the set of thin tiles. The ribbons of $P$
correspond to the grid lines of the regular multigrid $P_{*}$, and a pair of
ribbons meet at a thin tile if and only if their grid lines meet at angle
$\pi/5$. These ribbons represent vertices in the braces graph
$G({\mathcal{B}})$ that are connected by an edge. Since any 2 grid lines
either meet at angle $\pi/5$ or have an intermediate grid line at angle
$\pi/5$ to each of them, it follows that $G({\mathcal{B}})$ is connected and
spanning. A similar argument holds when ${\mathcal{B}}$ is the set of thick
tiles.

(ii) The square tiles correspond to the edges of the braces graph. However,
there are 2 types of square up to translation and each ribbon only contains
squares of one type. It follows that $G({\mathcal{B}})$ is not connected and
so, by Theorem 2.6, ${\mathcal{G}}({\mathcal{B}})$ is infinitesimally
flexible. ∎

In the next lemma we show that ribbons are necessarily linearly localised. The
proof gives a formula for the directions of the ribbons and this is summarised
in Proposition 3.8.

######  Lemma 3.5.

Every ribbon of a regular multigrid parallelogram tiling is linearly
localised.

###### Proof.

Let $\rho$ be a ribbon, of a regular multigrid parallelogram tiling $P$, which
corresponds to a line $L$ of the component grid $A_{1}({\mathcal{L}})$ of the
predual multigrid $P_{*}$. Assume that $L$ is not a vertical line and and is
parametrised by arclength by the real variable $s$ measured from a vertex of
$P_{*}$, and let $T_{1}$ be the tile of $\rho$ corresponding to this
intersection point. Then the set $X_{1,j}$ of parameter values $s$ for points
of intersection of $L$ with lines of a grid $A_{j}({\mathcal{L}})$, with
$j\neq 1$, has the form

$X_{1,j}=\\{\beta_{1,j}n+\gamma_{1,j}:n\in{\mathbb{Z}}\\},$

where, without loss of generality, $\beta_{1,j}>0$ and $\gamma_{1,j}\geq 0$.

Note that the points of the parameter set $X_{1,j}$ correspond to the
appearance of congruent tiles in the ribbon $\rho$ and we say that these tiles
are of type $(1,j)$. Here $2\leq j\leq r$ where $r$ is the number of grids for
$P_{*}$. Viewing these sets as containing points of the same colour, the
multi-coloured set $X_{1}$, formed by the union of the distinctly coloured
sets $X_{1,j}$, encodes the sequential appearance of the tile types of $\rho$.

To show that $\rho$ is linearly localised, introduce a copy $L^{\prime}$ of
$L$ in the separate ambient space for $P$, with its origin, for parameter
value $s=0$, located at a vertex $v_{1}$ of $T_{1}$. Let $T_{1},T_{2},\dots$
be the tiles of $\rho$ in sequential order corresponding to the positive
$s$-direction of $L^{\prime}$ and, rechoosing $v_{1}$ if necessary, arrange
that $v_{1}$ is not a vertex of $T_{2}$. Also let $M^{\prime}$ be a line
through this vertex which is orthogonal to $L^{\prime}$, with arclength
parametrised by $t$. The vertex $v_{1}$ has $(s,t)$-coordinates $(0,0)$ and
lies on a two-way infinite piecewise linear boundary curve $C$ of the ribbon
$\rho$. We show that $C$ is linearly localised and this will complete the
proof.

Let $v_{1},v_{2},\dots$ be the vertices on $C$ in their sequential order with
$(s,t)$-coordinates $(s_{k},t_{k}),k=1,2,\dots.$ Let $T$ be a tile of $\rho$
of type $(1,j)$. It has an edge $e$ which is not parallel to $M^{\prime}$ and
we define the _$s$ -increment_ (resp. $t$-increment) of $T$, for $\rho$, to be
the length $s_{1,j}$ (resp. $t_{1,j}$) of the projection of $e$ onto
$L^{\prime}$ (resp. $M^{\prime}$). See Figure 8.

$T$$L^{\prime}$$M^{\prime}$$t_{1,j}$$s_{1,j}$

Figure 8. Increments $s_{1,j}>0$ and $t_{1,j}\in{\mathbb{R}}$ associated with
a tile $T$ of type $(1,j)$ in a ribbon associated with a grid line of the grid
$A_{1}({\mathcal{L}})$.

Let $s_{*}$ be a parameter value for the line $L$. Then, for $s_{*}>0$ the
finite coloured set $X_{1}\cap[0,s_{*}]$ encodes a finite stretch of the
ribbon $\rho$. For each $j,$ we define the subset cardinalities

$n_{1,j}(s_{*})=|X_{1,j}\cap[0,s_{*}]|=|{\mathbb{Z}}\cap[\frac{-\gamma_{1,j}}{\beta_{1,j}},\frac{s_{*}-\gamma_{1,j}}{\beta_{1,j}}]|.$

Then the coordinates $(s_{k+1},t_{k+1})$ of the final vertex $v_{k+1}$ for
this stretch of $C$ are

$s_{k+1}=\sum_{j=2}^{r}n_{1,j}(s_{*})s_{1,j},\quad
t_{k+1}=\sum_{j=2}^{r}n_{1,j}(s_{*})t_{1,j}.$

For each $j$ we have

$n_{1,j}(s_{*})=\frac{s_{*}}{\beta_{1,j}}+o(s_{*}),\quad\mbox{as}\quad
s_{*}\to\infty,$

and so

$\frac{t_{k}}{s_{k}}\to m,\quad\mbox{as}\quad
k\to\infty,\quad\mbox{where}\quad
m=\frac{\sum_{j=2}^{r}\delta_{1,j}t_{1,j}}{\sum_{j=2}^{r}\delta_{1,j}{s_{1,j}}},$

and where $\delta_{1,j}$ is the relative frequency of the colour $j$, namely
the ratio

$\delta_{1,j}=\frac{\beta_{1,j}^{-1}}{\sum_{j=2}^{r}\beta_{1,j}^{-1}}.$

The same argument holds for $s_{*}<0$, and it follows that the ribbon $\rho$
is $H$-localised for the line $H$ through the origin with gradient $m$. ∎

######  Definition 3.6.

The _ribbon figure_ , or _ribbon line figure_ , RF$(P)$ of a parallelogram
tiling $P$ is the set of lines $H$ through the origin for which there exists
an $H$-localised ribbon.

######  Theorem 3.7.

Let ${\mathcal{G}}_{P}$ be the bar-joint framework of a regular multigrid
parallelogram tiling $P$. Then the bulk shear figure BSF$({\mathcal{G}}_{P})$
and the linear flex figure LFF$({\mathcal{G}}_{P})$ are equal to the ribbon
figure RF$(P)$.

###### Proof.

This follows from Theorem 2.10. ∎

For any set ${\mathcal{M}}$ of lines, not necessarily passing through the
origin, let LF$({\mathcal{M}})$, the _line figure_ of ${\mathcal{M}}$, be the
set of lines through the origin which are parallel to some line of
${\mathcal{M}}$. For a parallelogram or rhombus tiling $P$, given by a
multigrid $P_{*}$, the line figure LF$(P_{*})$ need not agree with the ribbon
figure RF$(P)$. The details for this, in terms of increments of projections,
are given in the proof of Lemma 3.5 and summarised in the following
proposition.

######  Proposition 3.8.

Let $P=P(P_{*},\lambda)$ where $P_{*}$ is a regular multigrid, with $r$
nonparallel component grids $P_{*}^{i}$ and line figure
LF$(P_{*})=\\{L_{1},\dots,L_{r}\\}$. For $1\leq i\leq r$, and for each tile
$T_{i,j},j\neq i,$ associated with the pair $L_{i},L_{j}$, let $s_{ij}>0$
(resp. $t_{ij}\in{\mathbb{R}}$) be the length of the projection onto $L_{i}$
(resp. $L_{i}^{\perp}$) of the edge of the tile which is not orthogonal to
$L_{i}$. Also, let $\delta_{i,j}$, for $j\neq i$, be the relative frequencies
in $L_{i}$ of the points of intersection with $P_{*}^{j}$, with $\sum_{j:j\neq
i}\delta_{i,j}=1$. Then the ribbon for $L_{i}$ is $H$-localised, where the
tangent of the angle between $H$ and $L_{i}$ is

$\frac{\sum_{j:j\neq i}\delta_{i,j}t_{i,j}}{\sum_{j:j\neq
i}\delta_{i,j}{s_{i,j}}}$

The multigrid line figure and the ribbon figure may coincide for reasons of
symmetry and this is so for the Penrose rhomb tilings. Specifically, for a
given ribbon direction associated with a grid line $L$ the 4 other
intersecting grid line types can be paired (by bilateral symmetry with respect
to an orthogonal line to $L$), and their associated rhombs at intersection
points similarly paired. These pairs of rhombs, with bilateral symmetry, have
cancelling $t$-increments.

###  3.3. Finitely flexible quasicrystals

Let $P$ be the dual parallelogram tiling $P(P_{*},\lambda)$ defined by the
regular multigrid $P_{*}$ with component grids $A_{i}({\mathcal{L}})$, for
$1\leq i\leq r$, as in Definition 3.2. For each pair of distinct indices $i,j$
let $W(i,j)$ be the lattice of vertices of $P_{*}$, when viewed as an embedded
graph, which is determined by the component grids for $i,j$. Let
$W(i,j)=\\{w(i,j,k,l):(k,l)\in{\mathbb{Z}}^{2}\\}$ where the labelling
corresponds to the lines of the grid $A_{i}({\mathcal{L}})$ (resp.
$A_{j}({\mathcal{L}})$) being ordered by indices $k\in{\mathbb{Z}}$ (resp.
$l\in{\mathbb{Z}}$). For definiteness we assume that the linear part of each
$A_{i}$ has positive determinant and the labelling is inherited from the
$x$-coordinate labelling of the lines of ${\mathcal{L}}$. The parallelogram
tiles of $P$ have a corresponding labelling, $T(i,j,k,l)$, for $i\neq
j,(k,l)\in{\mathbb{Z}}^{2}$.

######  Definition 3.9.

A _checkered multigrid parallelogram tiling_ , with integer _density index_
$p\geq 2$, is a pair $(P,{\mathcal{B}})$ where $P$ is a regular multigrid
parallelogram tiling and ${\mathcal{B}}$ is the set of tiles

${\mathcal{B}}=\\{T(i,j,k,l):1\leq i,j\leq r,i\neq
j,(k,l)\in{\mathbb{Z}}^{2},k=l\mod p\\}.$

A _checkered quasicrystal framework_ is a bar-joint framework
${\mathcal{G}}_{P}({\mathcal{B}})$ for such a pair which is obtained from the
parallelogram framework ${\mathcal{G}}_{P}$ by adding bracing bars for the
tiles of ${\mathcal{B}}$.

If the tiles of ${\mathcal{B}}$ are considered as being coloured black, rather
than the default colour white, then for $p=2$, the coloured tiling
$(P,{\mathcal{B}})$ is a quasicrystal counterpart of an infinite checkerboard.
Accordingly in this case we refer to ${\mathcal{G}}_{P}({\mathcal{B}})$ as a
_checkerboard quasicrystal_.

It is straightforward to see that there exist $p-1$ tiles which when added to
the black set ${\mathcal{B}}$ create a bracing set ${\mathcal{B}}^{+}$ whose
braces graph $G({\mathcal{B}}^{+})$ is connected and spanning. By Theorem 2.6,
${\mathcal{G}}({\mathcal{B}}^{+})$ is infinitesimally rigid and
$\dim{\mathcal{F}}({\mathcal{G}}({\mathcal{B}}))\leq 3+(p-1).$ In fact we have
equality.

######  Theorem 3.10.

Let ${\mathcal{G}}_{P}({\mathcal{B}})$ be a checkered quasicrystal framework
determined by a pair $(P,{\mathcal{B}})$ with index $p\geq 2$. Then the
infinitesimal flex space ${\mathcal{F}}({\mathcal{G}}_{P}({\mathcal{B}}))$ has
dimension $p+2$.

###### Proof.

The braces graph $G({\mathcal{B}})$ is spanning since on every ribbon of type
$(i,k)$, determined by the $k^{th}$ line of the grid $A_{i}({\mathcal{L}})$ of
$P_{*}$, there is a tile $T(i,j,k,l)$ in ${\mathcal{B}}$ for some $j\neq i$
and $l\in{\mathbb{Z}}$. The braces graph has $p$ components, say $G_{t},0\leq
t\leq p-1,$ where the vertices/ribbons of $G_{t}$ are of type $(i,k)$ with
$k=t\mod p$. Let $p_{1}$ be a fixed joint and let
${\mathcal{F}}({\mathcal{G}}_{P}({\mathcal{B}}))_{0}$ be the subspace of
infinitesimal flexes $z\in{\mathcal{F}}({\mathcal{G}}_{P}({\mathcal{B}}))$
with $z(p_{1})=0$. Note that every infinitesimal flex of
${\mathcal{G}}_{P}({\mathcal{B}})$ is an infinitesimal flex of the
parallelogram framework ${\mathcal{G}}_{P}$. By Theorem 2.3 it follows that
each $z\in{\mathcal{F}}({\mathcal{G}}_{P}({\mathcal{B}}))_{0}$ has a unique
representation

$z=\sum_{t=0}^{p-1}\sum_{n=1}^{\infty}\alpha_{t,n}u_{t,n}$

where $\\{u_{t,n}:n\in{\mathbb{N}},0\leq t\leq p-1\\}$ is a set of ribbon
shears, associated with $p_{1}$ and the set of ribbons
$\\{\rho_{t,n}:n\in{\mathbb{N}},0\leq t\leq p-1\\}$ of ${\mathcal{G}}_{P}$.
Here the index $t$ indicates the component $G_{t}$ of $G({\mathcal{B}})$ for
which the $t$-labelled ribbons are vertices.

Since the subgraphs $G_{t}$ are the connected components of $G({\mathcal{B}})$
it follows, as in the proof of Theorem 2.6, that the velocity fields

$z_{t}=\sum_{n=1}^{\infty}\alpha_{t,n}u_{t,n}$

are also infinitesimal flexes of ${\mathcal{G}}_{P}({\mathcal{B}})$. Moreover,
since $G_{t}$ is connected the coefficients $\alpha_{t,n},n=2,3,\dots,$ are
determined by $\alpha_{t,1}$ for each $t$, and so the subspace of
infinitesimal flexes $z_{t}$ is either 1-dimensional or the zero subspace. It
remains to show that they are 1-dimensional. This follows since if $z$ is an
infinitesimal rotation flex about $p_{1}$ then its component flexes $z_{t}$
are nonzero. ∎

######  Remark 3.11.

The alternatingly braced squares framework, for the usual infinite
checkerboard, is perhaps the paradigm example of a crystallographic framework
with a single nontrivial zero mode (up to scalar multiples). See, for example,
Figure 2 and Example (f) of Power [19], and Figure 6 of Dove [9]. The
framework also features as cross-sections of the three dimensional perovskite
framework of corner connected octahedra, and is responsible for lines in the
zero mode spectrum.

######  Remark 3.12.

As we have noted in the introduction, bar-joint frameworks provide a
fundamental model for network materials and it seems to us that explicit free
basis methods can provide a useful new perspective. In particular this
viewpoints avoids considerations of periodic approximants, or periodic
boundary conditions, which can be problematic [16].

##  4\. Zero mode spectra for quasicrystals

The notion of a zero mode, as opposed to a floppy mode (infinitesimal flex),
of an infinite bar-joint framework in ${\mathbb{R}}^{d}$ is that of an
excitation state (first-order simple harmonic motion oscillatory state) with
an associated wave vector k. For a crystallographic framework ${\mathcal{C}}$
these wave vectors live in the reciprocal space, ${\mathbb{R}}^{d}_{\bf k}$
say, determined by a basis $\underline{a}=\\{a_{1},\dots,a_{d}\\}$ of
periodicity vectors for ${\mathcal{C}}$. The periodic reduction of the set of
wave vectors is the RUM spectrum (or reduced zero mode spectrum) for the pair
${\mathcal{C}},\underline{a}$, denoted $\Omega({\mathcal{C}},\underline{a})$,
and this can be defined more directly, as we do below, in terms of complex
infinitesimal flexes that are periodic up to a multiphase factor [18], [19].
In this section we give a definition of a zero mode spectrum for some
quasicrystal frameworks, and which are motivated by results in the previous
sections.

###  4.1. Zero mode spectra for crystals

We first summarise the formulation of a zero mode of a crystal framework in
terms of _phase fields_ for a cell partition of the ambient space.

A _cell partition_ for a basis $\underline{a}$ of ${\mathbb{R}}^{d}$ is a
partition ${\mathcal{P}}=\\{C_{k}:k\in{\mathbb{Z}}^{d}\\}$ where $C_{k}$ is
the semi-open parallelepiped

$C_{k}=[k_{1}a_{1},(k_{1}+1)a_{1})\times\dots\times[k_{d}a_{d},(k_{d}+1)a_{d}).$

A wave vector ${\bf k}=(\gamma_{1},\dots,\gamma_{d})$ corresponds to the phase
field map $\phi_{\bf k}:{\mathbb{R}}^{d}\to{\mathbb{C}}$ given by

$\phi_{\bf k}(x)=e^{2\pi i{\gamma_{1}}k_{1}}\dots e^{2\pi
i{\gamma_{d}}k_{d}},\quad x\in C_{k},\quad k\in{\mathbb{Z}}^{d}.$

This phase field, in physical space, is constant on each individual cell of
the partition. Let ${\mathcal{C}}$ be a crystallographic framework with a set
of periodicity vectors $\underline{a}=\\{a_{1},\dots,a_{d}\\}$ which is a
basis for ${\mathbb{R}}^{d}$. Define an associated phase-periodic velocity
field $u$, for the wave vector ${\bf k}$, to be a map from the set of joints
of ${\mathcal{C}}$ to velocity vectors in ${\mathbb{C}}^{d}$, with the
property

$u(T_{k}(p_{i}))=\phi_{\bf k}(T_{k}(p_{i}))u(p_{i}),\quad p_{i}\in C_{0},$

where $T_{k}(p_{i})$ is the joint in $C_{k}$ which is the translate of the
joint $p_{i}$, in the cell $C_{0}$, given by

$T_{k}(p_{i})=p_{i}+k_{1}a_{1}+\dots+k_{d}a_{d}.$

The $d$-tuple

$\omega=(\omega_{1},\dots,\omega_{d})=(e^{2\pi i{\gamma_{1}}},\dots,e^{2\pi
i{\gamma_{d}}})$

is the _multiphase_ of $u$ and, with the usual multinomial notation
convention, we have

$u(T_{k}(p_{i}))=\omega^{k}u(p_{i}),\quad k\in{\mathbb{Z}}^{d},p_{i}\in
C_{0}.$

######  Definition 4.1.

The rigid unit mode spectrum, or RUM spectrum,
$\Omega({\mathcal{C}},\underline{a})$, of a crystallographic bar-joint
framework ${\mathcal{C}}$ and periodicity basis $\underline{a}$, is the set of
multiphases $\omega$ for which there exists a nonzero phase-periodic complex
infinitesimal flex. The unreduced zero mode spectrum is the set of wave
vectors ${\bf k}$ whose multiphase $\omega$ is a point of
$\Omega({\mathcal{C}},\underline{a})$.

######  Example 4.2.

For a simple but relevant illustration let $d=2$ and let
${\mathcal{C}}_{{\mathbb{Z}}^{2}}$ be the parallelogram bar-joint framework
for the tiling by squares where the joints have integer coordinates. The basis
$\underline{a}=\\{(1,0),(0,1)\\}$ is a periodicity basis and each set
$C_{k},k\in{\mathbb{Z}}^{2}$, contains a single joint, say $p_{k}$. For each
$\lambda\in{\mathbb{T}}$ the velocity fields

$u_{x,\lambda}(p_{k})=\lambda^{k_{2}}(1,0),\quad
u_{y,\lambda}(p_{k})=\lambda^{k_{1}}(0,1),\quad
k=(k_{1},k_{2})\in{\mathbb{Z}}^{2},$

are infinitesimal flexes and so $\Omega({\mathcal{C}},\underline{a})$ contains
the set $(\\{1\\}\times{\mathbb{T}})\cup({\mathbb{T}}\times\\{1\\})$. Note
moreover, that the complex infinitesimal flex vector space of
${\mathcal{C}}_{{\mathbb{Z}}^{2}}$ has a free basis of complex infinitesimal
flexes which are supported on horizontal and vertical lines of joints, and
$u_{x,\lambda}$ (resp. $u_{y,\lambda}$) is an infinite linear combination of
the horizontal (resp. vertical) line flexes. One can use this free basis to
show that there are no other points in the RUM spectrum. To see this, consider
the free basis of infinitesimal flexes $u_{x,t},u_{y,t}$, for
$t\in{\mathbb{Z}}$, where $u_{x,t}(p_{k})=(1,0)$ if $t=k_{2}$, and
$u_{y,t}(p_{k})=(0,1)$ if $t=k_{1}$. Suppose that $z$ is a zero mode for
$\lambda=(\lambda_{1},\lambda_{2})$. Then $z$ has a representation

$z=\sum_{t}\alpha_{x,t}u_{x,t}+\alpha_{y,t}u_{y,t}.$

Thus

$\lambda_{1}^{i}\lambda_{2}^{j}z(p_{0,0})=z(p_{i,j})=\alpha_{x,j}(1,0)+\alpha_{y,i}(0,1)=(\alpha_{x,j},\alpha_{y,i}).$

Since $z$ is nonzero the velocity vector $z(p_{0,0})$ is also nonzero. Now the
equations above, for $0\leq i,j\leq 1$, imply that at least one of
$\lambda_{1},\lambda_{2}$ is equal to 1.

For a direct general approach to the determination of
$\Omega({\mathcal{C}},\underline{a})$, one considers the infinitesimal flex
equations for a representative set of bars, such as the bars in the building
block motif. For the pair ${\mathcal{C}},\underline{a}$ these equations are
satisfied for a nonzero phase-periodic velocity field $u$ of the form

$u(p_{k})=\lambda_{1}^{k_{1}}\lambda_{2}^{k_{2}}(a,b),$

if the conjugate $(\overline{\lambda_{1}},\overline{\lambda_{2}})$ is a point
of rank degeneracy of a $2\times 2$ matrix-valued function $\Phi(z_{1},z_{2})$
on ${\mathbb{T}}^{2}$, with $(a,b)$ in the null-space of
$\Phi(\overline{\lambda_{1}},\overline{\lambda_{2}})$. This also leads to the
identification of $\Omega({\mathcal{C}},\underline{a})$ as
$(\\{1\\}\times{\mathbb{T}})\cup({\mathbb{T}}\times\\{1\\})$.

It is also convenient, and common in applications, to record the RUM spectrum
as a reduced set of wave vectors. For this example the spectrum is represented
as the subset of the unit square $[0,1)\times[0,1)$ of points
$(\gamma_{1},\gamma_{2})$ with $\gamma_{1}=0$ or $\gamma_{2}=0$.

The matrix function is known as the _symbol function_ of the crystal framework
with respect to the periodicity basis $\underline{a}$. See [18], [19] and [15]
for further details.

###  4.2. Zero mode spectra for quasicrystals

In the absence of an underlying periodic structure for an aperiodic framework
we consider some notions of zero mode spectra which relate to generalised
phase fields. In the case of multigrid parallelogram frameworks
${\mathcal{G}}_{P}$ we define zero modes in terms of multiparameter phase
fields. As in the crystallographic case these modes are in fact determined by
the points $\omega$ of rank degeneracy of a multi-variable matrix-valued
function and the associated null space vectors. However, the independent
variables range in an $r$-torus, ${\mathbb{T}}^{r}\subset{\mathbb{C}}^{r}$,
rather than a 2-torus, where $r$ is the number of component grids of the
associated multigrid $P_{*}$.

Consider a regular multigrid $P_{*}$, in the ambient space
${\mathbb{R}}^{2}_{*}$, with $r$ component grids, no two of which are
parallel. Each grid defines a partition of ${\mathbb{R}}^{2}_{*}$ by semi-open
bands. If ${\mathcal{A}}=\\{A_{1},\dots,A_{r}\\}$ is the set of affine
transformations determining this multigrid then a partition of
${\mathbb{R}}^{2}$ is given by the images under $A_{i}$ of the partition by
vertical left-closed bands $B_{m},m\in{\mathbb{Z}}$, associated with the
integer lattice ${\mathcal{L}}$, where $B_{m}=[m,m+1)\times{\mathbb{R}}$.
Taking the intersection of these $r$ partitions gives a partition $C(P_{*})$
of ${\mathbb{R}}^{2}_{*}$ by semi-open polygonal regions. Each set of the
partition has the form $C_{m}=A_{1}(B_{m_{1}})\cap\dots\cap A_{r}(B_{m_{r}})$
for some $r$-tuple $m=(m_{1},\dots,m_{r})$. Let ${\mathcal{M}}$ be the subset
of ${\mathbb{Z}}^{r}$ consisting of these $r$-tuples. The interiors of the
polygon sets give a partition of the complement of $P_{*}$ in
${\mathbb{R}}^{2}_{*}$, and their closures are the faces (or tiles) of
$P_{*}$, when $P_{*}$ is viewed as a regular line tiling. Since faces, $f$
say, of $P_{*}$ correspond to vertices of $P$ we may denote the set of joints
of ${\mathcal{G}}_{P}$ as $\\{p_{f}:f\in F(P_{*})\\}$, or
$\\{p_{m}:m\in{\mathcal{M}}\\}$.

######  Definition 4.3.

Let ${\mathcal{G}}_{P}$ be a parallelogram framework for the regular multigrid
$P_{*}$. For each $r$-tuple $\omega=(\omega_{1},\dots,\omega_{r})$ in
${\mathbb{T}}^{r}$ the phase field $\phi_{\omega}$ on the set of joints
$\\{p_{m}:m\in{\mathcal{M}}\\}$ is given by
$\phi_{\omega}(p_{m})=\omega^{m}=\omega_{1}^{m_{1}}\dots\omega_{r}^{m_{r}},$
for $m\in{\mathcal{M}}$.

A regular multigrid framework ${\mathcal{G}}_{P}$ has finite local complexity
and indeed the joints are of finitely many translation types according to the
translation types of the star graphs of vertices of $P$. Suppose that there
are $n$ translation types and let $p_{f_{1}},\dots,p_{f_{n}}$ be a choice of
representatives. Also write $p_{f}\equiv p_{f_{i}}$ if $p_{f}$ is of the same
translation type as $p_{f_{i}}$.

######  Definition 4.4.

Let ${\mathcal{G}}_{P}$ be a parallelogram framework of a regular multigrid
with $r$ component grids given by the set of affine transformations
${\mathcal{A}}=\\{A_{1},\dots,A_{r}\\}$, and let $p_{f_{1}},\dots,p_{f_{n}}$
be a set joints representing the $n$ possible translation types of joints.

(i) A _phase-periodic velocity field_ $u$ for ${\mathcal{G}}_{P}$, with phase
factor $\omega\in{\mathbb{T}}^{r}$, is a complex velocity field such that

$u(p_{f})=\phi_{\omega}(p_{f})b_{i},\quad\mbox{if}\quad p_{f}\equiv
p_{f_{i}},$

where $b_{1},\dots,b_{n}$ is a set of velocity vectors in ${\mathbb{C}}^{2}$.

(ii) A _zero mode_ of ${\mathcal{G}}_{P}$, with phase factor $\omega$, is a
phase-periodic velocity field for $\omega$ that is an infinitesimal flex.

(iii) The _reduced zero mode spectrum_ of ${\mathcal{G}}_{P}$ is the set
$\Omega({\mathcal{G}}_{P},{\mathcal{A}})$ of phase factors
$\omega\in{\mathbb{T}}^{r}$ for the zero modes of ${\mathcal{G}}_{P}$.

In this definition the phase fields $\phi_{\omega}$ are defined only on the
set of joints. However, these fields may be viewed as restrictions of phase
fields on ${\mathbb{R}}^{2}$ that are constant on the sets of a partition of
${\mathbb{R}}^{2}$ induced by the partition $C(P_{*})$, as we now indicate. In
particular the spectrum $\Omega({\mathcal{G}},{\mathcal{A}})$ may be defined
in the same way if ${\mathcal{G}}$ is obtained from ${\mathcal{G}}_{P}$ in a
systematic way by local moves with bars and joints.

The regular multigrid $P_{*}$ defines an ${\mathbb{R}}^{2}_{*}$-embedded graph
$G(P_{*})=(V(P_{*}),E(P_{*})$) where $V(P_{*})$ is the set of intersection
points of the grids of $P_{*}$, and $E(P_{*})$ is the set of line segments
joining consecutive vertices on the lines of the grids. Also, in
${\mathbb{R}}^{2}$ the _skeleton_ sk$(P)$ of $P$ is defined as the union of
the piecewise linear curves formed by the line segments joining the midpoints
of opposite edges of the tiles of $P$. Using these curves define the
${\mathbb{R}}^{2}$-embedded graph (the skeleton graph) $G_{\rm sk}(P)=(V_{\rm
sk},E_{\rm sk})$ where $V_{\rm sk}$ is the set of centres of the tiles and
where $E_{\rm sk}$ is the double line segment path in the skeleton joining
these vertices for adjacent tiles. The definition of $P$ determines a
bijection $V(P_{*})\to V_{\rm sk}$ and this extends to a (nonunique) piecewise
linear bijection $\beta:G(P_{*})\to G_{\rm sk}(P)$. This in turn induces a
unique partition $C(P)=\beta(C(P_{*}))$. The sets of this partition are the
sets

$\beta(C_{m})=\beta(A_{1}(B_{m_{1}}))\cap\dots\cap\beta(A_{r}(B_{m_{r}}))$

and these are intersections of semi-open irregular bands
$\beta(A_{i}(B_{m_{i}}))$ that are located between the skeletal curves of
adjacent ribbons.

######  Definition 4.5.

Let $P$ be the parallelogram tiling for a regular multigrid with ribbon
partition $\\{C_{m}:m\in{\mathcal{M}}\subset{\mathbb{Z}}^{r}\\}$ and let
$\omega$ in ${\mathbb{T}}^{r}$ be a multiphase. Then the _ribbon phase field_
$\phi_{\omega}:{\mathbb{R}}^{2}\to{\mathbb{C}}$ is given by

$\phi_{\omega}(x)=\omega^{m},\quad\mbox{for}\mbox{\quad}x\in\beta(C_{m}).$

The potential utility of ribbon phase fields is firstly that, in analogy with
the crystallographic case, phase-periodic velocity fields can be defined by
their restrictions when considering bar-joint frameworks ${\mathcal{G}}$ which
are derived from ${\mathcal{G}}_{P}$ in some systematic manner. Secondly,
taking a submultigrid, such as
$P_{*}^{\prime}=\\{A_{1}({\mathcal{L}}^{\prime}),\dots,A^{\prime}_{r}({\mathcal{L}}^{\prime})\\}$
where ${\mathcal{L}}^{\prime}$ is the lattice
$2{\mathcal{L}}=2{\mathbb{Z}}\times 2{\mathbb{Z}}$, leads to a courser
partition and associated phase fields which may be relevant to such derived
frameworks. This is analogous to the crystallographic move of replacing a
primitive periodicity basis by some other periodicity basis which enlarges the
choice of building block.

Let $\rho_{i,k},k\in{\mathbb{Z}},$ be a consecutive enumeration of the ribbons
of a regular multigrid parallelogram tiling $P$ which are associated with the
$i^{th}$ component grid. Recall that a ribbon shear $u_{i,k}$ for $\rho_{i,k}$
is an infinitesimal flex that has zero velocity vectors for the joints on one
side of the ribbon and which has a common velocity vector on the other side.
The latter vector ${\bf t}_{\rho}$ is orthogonal to the internal edges of the
ribbon. We can therefore choose ribbon shears $w_{i,k},k\in{\mathbb{Z}},$ in a
consistent way, with common velocity ${\bf t}_{i}$, and with the support of
$w_{i,k}$ contained in the support of $w_{i,k-1}$. Thus the differences
$z_{i,k}=w_{i,k}-w_{i,k-1}$ are linearly localised infinitesimal flexes that
are supported on the joints contained in the bands $\beta(A_{i}(B_{k}))$, for
$k\in{\mathbb{Z}}$.

The infinitesimal flexes $z_{i,k}$, for $k\in{\mathbb{Z}},$ have disjoint
supports and so for each $\lambda\in{\mathbb{T}}$ the velocity vector
$z_{i,\lambda}=\sum_{k}\lambda^{k}z_{i,k}$ is an infinitesimal flex. It
follows that $z_{i,\lambda}$ is a zero mode with phase-factor $\omega$ where
$\omega_{i}=\lambda$ and $\omega_{j}=1,j\neq i$. Thus, the zero mode spectrum
$\Omega({\mathcal{G}}_{P},{\mathcal{A}})$ contains the $r$-fold union

$({\mathbb{T}}\times\\{1\\}\times\dots\times\\{1\\})\cup\dots\cup(\\{1\\}\times\dots\times\\{1\\}\times{\mathbb{T}}).$

It can be shown that each infinitesimal flex $z_{i,k}$ can be represented as a
pointwise convergent infinite linear combination of the zero modes
$z_{i,\lambda}$, with $1\leq i\leq r,k\in{\mathbb{Z}},$ and $\lambda=e^{2\pi
i\gamma},\gamma\in{\mathbb{Q}}$. In the light of this, and in analogy with
Example 4.2, we expect that $\Omega({\mathcal{G}}_{P},{\mathcal{A}})$ is equal
to the $r$-fold union above.

######  Remark 4.6.

Finally we remark that there are other forms of zero mode spectrum that can be
defined, for aperiodic bar-joint frameworks ${\mathcal{G}}$, which are based
in part on the presence linearly localised flexes which can be phase-periodic
in their localised directions. We consider this in detail elsewhere. The main
idea for plane frameworks is to consider phase fields for band partitions in
the ambient space of ${\mathcal{G}}$, associated with unrestricted
parallelogram partitions, and to consider infinitesimal flexes with
approximate forms of phase-periodicity. This leads to an associated zero mode
spectrum, consisting of lines of wave vectors ${\bf k}$ in a reciprocal space
${\mathbb{R}}^{2}_{\bf k}$ relative to an arbitrary reference basis for
${\mathbb{R}}^{2}$. For a regular multigrid parallelogram framework
${\mathcal{G}}_{P}$ this “essential linear spectrum” is identified with the
reciprocal figure of $RF({\mathcal{G}}_{P})$.

## References

  * [1] H. Au-Yang, J. H. H. Perk, Quasicrystals - The impact of N.G. de Bruijn, Indagationes Mathematicae 24 (2013), 996-1017.
  * [2] M. Baake and U. Grimm, Aperiodic Order, Vol. 1, A Mathematical Invitation, C.U.P. 2014, 545pp.
  * [3] G. Badri, D. Kitson and S. C. Power, The almost periodic rigidity of crystallographic bar-joint frameworks, Symmetry 6 (2014), 308-328. https://www.mdpi.com/2073-8994/6/2/308/xml
  * [4] G. Badri, D. Kitson and S. C. Power, Crystal flex bases and the RUM spectrum, Arxiv:1807.00750, Proc. of the Edinburgh Math. Soc., to appear.
  * [5] F. P. M. Beenker, Algebraic theory of non-periodic tilings of the plane by two simple building blocks: a square and a rhombus, EUT report. WSK, Dept. of Mathematics and Computing Science; Vol. 82-WSK-04, Eindhoven University of Technology, 1982.
  * [6] E. D. Bolker and H. Crapo, Bracing Rectangular Frameworks. I, SIAM J. App. Math., 36 (1979), 473-490.
  * [7] N. G. de Bruijn, Algebraic theory of Penrose’s non-periodic tilings of the plane I and II, in Koninklijke Nederlandse Academie v. Wetenschappen, series A 84 1981. pp 37-66.
  * [8] M. T. Dove, A. K. A. Pryde, V. Heine and K. D. Hammonds. Exotic distributions of rigid unit modes in the reciprocal spaces of framework aluminosilicates, J. Phys., Condens. Matter 19 (2007) doi:10.1088/0953-8984/19/27/275209.
  * [9] M. T. Dove, Flexibility of network materials and the Rigid Unit Mode model: a personal perspective. Phil. Trans. R. Soc. A 377: 20180222. http://dx.doi.org/10.1098/rsta.2018.0222.
  * [10] E. M. Duarte Gélvez, G. K. Francis, Stability of Quasicrystal Frameworks in 2D and 3D, Proceedings of the First Conference Transformables 2013, Starbooks. Felix Escrig and Jose Sanchez (eds.)
  * [11] D. Frettlöh and E. Harriss, Parallelogram tilings, worms, and finite orientations, Discrete Comput. Geom., 49 (2013), 531-539.
  * [12] D. Frettlöh, E. Harriss and F. Gähler, _Tilings encyclopedia_ , https://tilings.math.uni-bielefeld.de/
  * [13] F. Gähler and J. Rhyner, Equivalence of the generalised grid and projection methods for the construction of quasiperiodic tilings, 1986 J. Phys. A: Math. Gen. 19 267.
  * [14] G. Grasegger and J. Legerský, Bracing frameworks consisting of parallelograms, arXiv:2008.11521.
  * [15] E. Kastis, D. Kitson and J. E. McCarthy, Symbol functions for symmetric frameworks, Journal of Mathematical Analysis and Applications 497 (2021), DOI: 10.1016/j.jmaa.2020.124895.
  * [16] C. F. Moukarzel and G. G. Naumis, Penrose Tilings as Jammed Solids, Phys. Rev. Lett. 115, 209801
  * [17] G. Nagy Kem, Bracing rhombic structure by one-dimensional tensegrities, Meccanica, 52 (2017), 1283-1293.
  * [18] J. C. Owen and S. C. Power, Infinite bar-joint frameworks, crystals and operator theory, New York J. Math., 17 (2011), 445-490.
  * [19] S. C. Power, Polynomials for crystal frameworks and the rigid unit mode spectrum, Royal Society Philosophical Transactions A, Vol. 372, No. 2008, 20120030, 2014, http://dx.doi.org/10.1098/rsta.2012.0030.
  * [20] S. C. Power, Non-Euclidean braced grids, Mathematical Proceedings of the Royal Irish Academy, 120A (2020), 43-57.
  * [21] D. Z. Rocklin, B. Gin-ge Chen, M. Falk, V. Vitelli, and T. C. Lubensky, Mechanical Weyl Modes in Topological Maxwell Lattices, Phys. Rev. Lett. 116, 135503 (2016).
  * [22] J. E. S. Socolar, Simple octagonal and dodecagonal quasicrystals, Phys. Rev. B 39, 10519, 1989.
  * [23] O. Stenull and T.C. Lubensky, Penrose tilings as jammed solids, Phys. Rev. Lett. 113, 158301, 2014.
  * [24] F. Wegner, Rigid-unit modes in tetrahedral crystals, J. Phys.: Condens. Matter 19 (2007), 406-218.
  * [25] T. Wester, The structural morphology of Penrose and quasicrystal pattern, Part I, International Conference on Adaptable Building Structures, Adaptables 06, Eindhoven University of Technology, 2006. pp. 290-294
  * [26] D. Zhou, L. Zhang, and X. Mao, Topological boundary floppy modes in quasicrystals, Physical Review, X 9, 021054 (2019), DOI:10.1103/PhysRevX.9.021054


Writing concurrent code that is both correct and efficient is notoriously difficult:  thus, programmers often prefer to use synchronization abstractions, which render  code simpler and easier to reason about. Despite a wealth of work on this topic, there is still a gap between the rich semantics provided by  synchronization abstractions in modern programming languages—specifically, fair FIFO ordering of synchronization requests and support for abortable operations—and frameworks for implementing such semantics correctly and efficiently.
Supporting such semantics is critical given the rising popularity of constructs for asynchronous programming, such as coroutines, which abort frequently, and should be cheaper to suspend and resume compared to native threads.

We introduce a new framework called the  (CQS),
which enables efficient fair and abortable implementations of fundamental synchronization primitives such as mutexes, semaphores, barriers, count-down-latches, and blocking pools.
Our first contribution is algorithmic, as implementing both fairness and abortability efficiently at this level of generality is  non-trivial.
Importantly, all our algorithms come with formal proofs in the Iris framework for Coq. These proofs are modular, so it is easy to prove correctness for new primitives implemented on top of CQS.
To validate practical impact, we integrated CQS into the Kotlin Coroutines library. Compared against Java's , the only practical abstraction to provide similar semantics,
CQS shows significant improvements across all benchmarks, of up to two orders of magnitude.
In sum, CQS is the first framework to combine expressiveness with formal guarantees and strong practical performance, and should be  extensible to other languages and other families of synchronization primitives.

§ INTRODUCTION

Providing the “right” set of programming abstractions to enable efficient and correct concurrent code is a question as old as the field of concurrency <cit.>.
One of the most basic primitives is the mutex, which allows access to the critical section to at most one thread, via  and  invocations.
Standard libraries, e.g. the Java concurrency library <cit.>,
provide more general primitives, such as the semaphore, which allows at most a fixed number of threads to be in the critical section concurrently, the barrier, which allows a set of threads to wait for each other at a common program point,
or the count-down latch, which allows threads to wait until a given set of operations is completed.

Although basic versions of the above primitives exist in most specialized libraries,
programmers often require stronger semantics from synchronization abstractions, which are supported by modern programming languages such as Java, C#, Go, Kotlin and Scala.
One particularly desirable property is fairness <cit.>, by which the order of critical section traversals should respect the FIFO order of arrivals, to avoid starvation.
A second key property is abortability, which enables a thread to cancel its request, due to a time-out or user-specified behavior.
Abortability is especially important in the context of coroutines <cit.>, whose count in the system can be in the millions, and which can be frequently aborted.
Moreover, coroutines are also cheaper to suspend and resume compared to native threads, so using fair synchronization is more natural in this context.
Unfortunately, implementing fairness and cancellation efficiently in a concurrent context is known to be very  challenging <cit.>.
Thus, modern languages either restrict these general semantics, or, alternatively, provide very complex implementations which can often be inefficient or even buggy, e.g. <cit.>.

In this paper, we address the question of implementing fair and abortable synchronization primitives in a way that is both general and efficient, and introduce a construct which we call the  (CQS).
We show that the CQS can implement a wide range of synchronization primitives, for which we provide both formal proofs and extensive experimental validation, showing significant improvements over the state of the art.

For intuition, we start from the observation that most of the synchronization operations we focus on are inherently blocking: threads attempt to acquire a shared resource, and may have to wait if the resource is busy.
We choose to model such operations via  <cit.>, which split blocking operations into two parts at the points of suspension:
instead of suspending, blocking operations, such as the mutex , return a   instance, where the  operation on this Future returns  if the operation is not yet completed, or the completion value otherwise.

In this context, the goal of the  framework is to efficiently maintain a FIFO queue of waiters, corresponding to s to be completed. To this end, it provides two main operations:

1) , which adds a new waiter into the queue and returns the corresponding , and

2) , which tries to retrieve and resume the next waiter with the specified result.

One key advantage of the CQS semantics is that it allows operations to invoke  before : we actively use this property for implementation simplicity and better performance.
Despite the relative simplicity of the  API, its efficient data-structure implementation is highly non-trivial and allows us to support a rich set of synchronization semantics.

The main novelty behind  is the efficient built-in abort / cancellation support.
One naive way to implement such functionality is by linearly searching the waiting queue for the node corresponding to the waiter, which is then unlinked <cit.>. However, this would have worst-case linear time in the size of the queue: thus, frequent cancellations lead to major overheads.
We propose a more efficient base design, where instead of single elements, we organize waiters into fixed-sized cell segments, so that each cell stores a waiter. These segments form a concurrent doubly-linked list. When all waiters in a segment are cancelled, we can remove the entire segment in constant time via careful pointer manipulations. This allows us to support different cancellation modes: simple cancellation,  is allowed to fail if the waiter located in the next cell was cancelled, whereas smart cancellation provides a mechanism to efficiently skip cancelled waiters, but requires complex mechanisms to ensure that some waiter is always resumed.

Our main theoretical contribution consists of modular formal proofs for all the presented primitives, using the Iris  separation logic <cit.> with its Coq formalization <cit.>.
We formally specify the CQS operations, prove them, and then prove semantics corresponding to the primitives we consider.
One property we do not prove formally is the FIFO order, which is notoriously difficult to approach in Iris/Coq, but can be shown through classical proofs.
We emphasize the complexity of our formalization task, as few similar real-world implementations are  formally verified <cit.>.
Our proofs for CQS span approximately 8'000 lines of Coq code, often requiring non-trivial reasoning.
Yet, the proofs are modular, so they can be employed as the basis for proving new synchronization primitives implemented on top of CQS, reducing formalization effort.
For instance, proving each new CQS-based primitive takes around 500 lines of code.

Practical Applications. The main practical motivation behind our work is efficient synchronization support for coroutines.
Coroutines can be seen as lightweight threads, which are often suspended and resumed:  internally, they are scheduled on a thread pool, so when a coroutine becomes suspended, the corresponding thread immediately picks up another one and executes it instead, so the native thread does not block. Therefore, it is possible to have millions of coroutines active in the system, which can be viably cancelled much more often than native threads. In such a setting, efficient cancellation support is vital while fairness becomes less expensive. Coroutines are a key component of modern programming languages such as C++, Go, Scala, and Kotlin.

We integrated the CQS framework as part of the standard Kotlin Coroutines library and used it to implement several fundamental synchronization primitives.
To validate performance, we implemented  on the JVM and compared it against the state-of-the-art  framework in Java <cit.>, which aims to solve the same problem, and, to our knowledge, is the only practical abstraction that provides similar semantics.
In addition, we compared against the Kotlin Coroutines library implementations for specific primitives. We present different versions of mutex and semaphore, barrier and count-down-latch primitives, and two versions of blocking pools. Our algorithms outperform existing  implementations in almost all scenarios, and are often faster by orders of magnitude.

In particular, our semaphore implementation outperforms the standard Java solution up to  when the number of threads does not exceed the number of permits, and up to  in a highly-contended scenario.

Compared to the current, well-optimized mutex implementation in Kotlin Coroutines, our solution is  faster on average and up to  faster on large numbers of threads.

For the count-down-latch implementation, our solution shows an up to  speedup compared to the Java library, while the barrier synchronization is faster by up to .

For blocking pools, which share a limited set of resources, our presented solutions are faster than the Java library implementation by up to .
In some cases, the fair synchronization primitives we present even outperform the unfair variants in the Java standard library.
Our result analysis shows that these improvements come mainly because of the superior scalability of our design.

Related Work.
At the algorithmic level, our CQS implementation builds on ideas from both the classic Michael-Scott queue <cit.> and the highly-efficient LCRQ queue design of Afek and Morrison <cit.>. The latter was also used by Izraelevitz and Scott <cit.> to build blocking synchronous queues, and by Koval et al. <cit.> to build  channels. The CQS supports much more general semantics, requiring significant changes to the design, in particular to support cancellations.
To our knowledge, the only abstraction that provides similar semantics is the   in Java <cit.>, which, however, we outperform significantly.

Our work is part of a wider effort of formalizing and implementing support for asynchronous operations in modern programming languages that is expressive,  safe, and efficient <cit.>.
In this context, we focus on improvements at the algorithmic and semantic level. Specifically, we perform one of the first thorough explorations of how fairness and abortability semantics can be efficiently supported at the data structure level, and present one of the first formally-verified such designs. Importantly, our approach enables high-performance implementations in a range of practical applications, and could serve as a basis for standard library implementations in modern languages.

§ CORRECTNESS AND PROGRESS GUARANTEES

In this section, we discuss correctness and progress guarantees for both CQS operations and the primitives we built on top of our framework.

§.§ Formal Proofs of Correctness

Correctness is formally proven in the state-of-the-art concurrent higher-order separation logic Iris <cit.>, using its Coq formalization <cit.>. The proofs are available in an anonymized Github repository <cit.>. An outline of these proofs which should serves as a reader guide is provided in Appendix <ref>. Here, we highlight the key ideas and discuss limitations.

Operation Specifications.
Iris is a framework designed for reasoning about the safety of concurrent programs, and several non-trivial algorithms are formally proved using it <cit.>. When constructing formal proofs, one should provide a specification for each of the data structure operations. In the Iris logic, operations manipulate resources, which are pieces of knowledge about the system-wide state and can be held by threads or the data structure itself. These resources are logical and do not affect the program execution. A specification describes which resources are required for the operation to start and how they change when it finishes.

Consider again the mutex as an example. Intuitively, we parameterize it with a resource $R$, which serves as an exclusive right to be in the critical section and, thus, to invoke . Initially, this resource $R$ is held by the mutex object. The specification ensures that:

* when the  operation finishes, the resource $R$ is transferred to the caller thread, and

* when  starts, the corresponding thread must provide $R$.

If the resource $R$ is unique, the specification still holds; however, as it cannot be held by multiple threads by construction, the mutual exclusion contract is satisfied.

All our specifications are defined in a similar manner. For example, to specify the semaphore contract, we simply need to maintain $K$ non-distinguishable copies of $R$; thus, allowing at most $K$ threads to enter the critical section. However, the actual specifications in Coq contain many additional details, mainly due to support for cancellation semantics. Please refer to Appendix <ref> for details.

The Iris proofs are modular: specifications treat each operation separately and do not concern the state of the system as a whole, locally manipulating logical resources instead.

As a result, the proof of CQS itself spans 8000 lines of Coq; by comparison, the proof of the barrier, including its definition, takes only 400 lines, the semaphore proof requires less than 300 lines, and the proofs for the count-down-latch and blocking pools take up to 700 lines each. Modularity should significantly reduce the effort for someone wishing to formally verify their CQS-based primitive.

One main limitation is that the existing formal specifications do not highlight the FIFO semantics, allowing waiting operations to complete in any order. Instead, these specifications verify high-level properties, such as “at most one thread can be in the critical section” for the mutex. However, we do not find this limitation significant. First, it is easy to show fairness by following the basic CQS algorithm. Second, proving such strong contracts as linearizability requires huge effort even for simple data structures such as the classic Michael-Scott queue <cit.>, so constructing them for more complex algorithms is currently impractical.

Another limitation of the provided Iris specifications is that they do not assert the lack of memory leaks. In particular, they do not prevent us from always storing the whole infinite array. Nevertheless, the lack of memory leaks follows by construction, as we always physically remove segments full of canceled cells.

Finally, we assume a strong, sequentially-consistent memory model. We find this assumption reasonable as almost all the operations that manipulate shared data are atomic in the presented algorithms, while considering relaxed memory may significantly increase the proof complexity <cit.>. However, we plan to extend our proofs to support the release-acquire semantics <cit.> and, thus, match the LLVM memory model for languages such as C/C++ and Rust.

§.§ Progress Guarantees

Similarly to the dual data structures formalism <cit.>, we reason about progress independently from whether the operation was suspended or not. Thus, when we say that some blocking operation is lock- or wait-free, we mean that it performs all the synchronization and returns  with this progress guarantee, even if the operation logically suspends.

Unfortunately, the progress guarantees cannot be mechanized in our Iris proofs. The reason for this is that, at the time of writing, there are two forms of specifying program behavior in Iris. The first way is to use (partial) weakest preconditions, which do not ensure that an operation terminates. In fact, an infinite loop satisfies any such specification.

The second less popular form uses the total weakest precondition <cit.>, which requires that every operation must terminate in a bounded number of steps. This type of specification can be used to show wait-freedom of algorithms, but is not applicable to our case, as the segment removal procedure in the infinite array implementation only guarantees lock-freedom.

We do not consider the lack of the formal proofs of progress guarantees a major issue.
Although it is possible to write such proofs (see <cit.> for a comprehensive analysis), we find it much easier to discuss this question separately.

In essence, all the presented primitives, as well as the CQS framework itself, guarantee wait-freedom under no cancellation, and at least lock-freedom when requests may abort. Due to space limit, we provide the detailed analysis in Appendix <ref>.

§ DISCUSSION

We have presented a new  framework enabling efficient implementations for a whole range of fundamental synchronization primitives in a fair and abortable manner. We observed that the interplay between fairness and cancellation semantics can raise subtle semantic and correctness questions. We found formalization to be a useful tool when identifying correctness issues in our implementation, notably w.r.t. cancellation semantics. A practical consequence of our work is efficient support for such primitives in the context of Kotlin Coroutines, which we show to generally outperform existing designs offering similar semantics, in a wide range scenarios.

Specifically, our algorithms outperform existing Java implementations in almost all scenarios and are often faster by orders of magnitude. Surprisingly, the CQS-based primitives frequently surpass even the unfair versions of primitives from the standard Java library in our experiments. The main reason is the superior scalability of our design. More precisely, the  framework combines the classic CLH <cit.> lock algorithm with an integer counter, which represents the synchronization primitive state and is updated by  operations. In contrast, the CQS implementation uses  -s to update the data structure state and maintains a queue of waiters with -s on the contended path; thus, providing a more scalable solution.

Thus, CQS could serve as a basis for more complex semantics, designs, and primitives (e.g.  fair readers-writer locks and synchronous queues), not only for Kotlin Coroutines but for other languages, such as C++ and Rust. We plan to investigate this in future work, along with proof extensions to the  release-acquire memory model semantics <cit.>.