Overlap coincidence to strong coincidence in substitution tilingdynamics
Shigeki Akiyama a , Jeong-Yup Lee b∗
a: Institute of Mathematics, University of Tsukuba, 1-1-1 Tennodai,
Tsukuba, Ibaraki, Japan (zip:305-8571); akiyama@math.tsukuba.ac.jp
b: Dept. of Math. Edu., Kwandong University, 24, 579 Beon-gil, Beomil-ro, Gangneung,Gangwon-do, 210-701 Republic of Korea; jylee@kd.ac.kr, jeongyuplee@yahoo.co.kr;
Tel. 82-33-649-7776*Corresponding author

Abstract
Overlap coincidence is an equivalent criterion to pure discrete spectrum of the dynamics of self-aﬃne tilings in Rd . In the case of d = 1, strong coincidence on m-letter
irreducible substitution has been introduced in [10, 8] which implies that the system
is metrically conjugate to a domain exchange in Rm−1 . However being a domain exchange does not imply the property of pure discrete spectrum of the tiling dynamics.
The relation between two coincidences has not been established completely. In thispaper we generalize strong coincidence to higher dimensions and show the implicationfrom overlap coincidence to the new strong coincidence when the associated heightgroup is trivial. Furthermore we introduce a new criterion ‘simultaneous coincidence’and show the implication from overlap coincidence to the simultaneous coincidence.
The triviality of height group is shown in [6, 18] for 1-dimension irreducible Pisot
substitutions.
Keywords: Overlap coincidence, Strong coincidence, Simultaneous coincidence,
Pure discrete spectrum, Pisot substitution.
2008 MSC: Primary: 52C23
1. Introduction
The principal aim of this paper is to give a better understanding of pure discrete spectrum of self-aﬃne tiling dynamical systems which have zero-entropy andwhose spectral type varies from weakly-mixing to pure discrete. The study is strongly
motivated by atomic conﬁgurations of quasicrystals, which show pure point diﬀraction. Indeed, equivalence of pure point diﬀraction of quasicrystal structure and pure

Preprint submitted to European Journal of Combinatorics

February 3, 2014

discrete spectrum of its associated dynamical system is known in quite a general setting. If we restrict ourselves to 1-dimension substitutive systems, the problem of purediscrete spectrum can be reformulated using notions of ‘coincidence’ on word combinatorics. Many notions of coincidences have been introduced in the study of the
dynamical spectrum of self-aﬃne tilings. A lot of coincidences among these are proved
to be equivalent. However relation between strong coincidence of 1-dimension Pisot
substitution and other coincidences is not completely understood.
Overlap coincidence is deﬁned in self-aﬃne tiling and characterizes pure discrete
spectrum of the tiling dynamics [19, 14, 13]. Basically what it means is that every
two tiles in the tiling, which overlap after translating by a return vector, have atleast one tile in common after some iterations (see subsection 2.3 for the detail). This
coincidence has been proved to be equivalent with algebraic coincidence [13] and supercoincidence [17]. For an irreducible Pisot substitution in 1-dimension, all of thesecoincidences are equivalent to the fact that balanced pair algorithm terminates andeach balanced pair leads to a coincidence [11, 20]. This is a combinatorial condition
that we can quickly check for a given substitution.
Strong coincidence has been introduced by [10] in constant length substitution
sequences, generalized in unimodular Pisot substitutions by [8], and extended in thecase of non-unimodular Pisot substitutions by [17]. This combinatorial condition
guarantees that there is a geometric realization of substitutions which is metricallyconjugate to a domain exchange. In view of the balanced pair algorithm, strong coincidence only implies that every balanced pair leads to a coincidence, i.e., terminationof the balanced pair algorithm seems to be necessary to assume. In [11] Hollander andSolomyak proved the termination of the balanced pair algorithm in two letter case,establishing the equivalence between strong coincidence and pure discrete spectrum.
From this equivalence with the result of Barge and Diamond [5] which guarantees thestrong coincidence in two-letter case, we obtained that two-letter irreducible Pisot
substitution dynamical systems have pure discrete spectrum.
However apart from two-letter irreducible Pisot substitution sequences, the relation between the strong coincidence and pure discrete spectrum is not clearly understood. This relation is important for an approach towards ‘Pisot substitution
conjecture’ [2]. Recently Nakaishi [16] claimed that the dynamics of irreducible unimodular Pisot substitution sequence satisfying strong coincidence has pure discrete
spectrum through domain exchange ﬂow. Though we do not yet have a full accountof this claim, it indicates that strong coincidence in irreducible unimodular Pisot

2substitution sequences implies overlap coincidence in irreducible unimodular Pisot
substitution tilings in R. This gives us a motivation to look at the other direction. As
mentioned above, strong coincidence and overlap coincidence are both combinatorial
objects which are deﬁned in 1-dimension substitution sequence. However, it seems
that there is no reason to restrict it to 1-dimension substitutions to see the relationship between these coincidences and seems to be better to transfer the problem into
geometric setting. So we ﬁrst generalize strong coincidence in substitution sequences
into substitution tiling in Rd , and give a stronger version ‘simultaneous coincidence’ in§2 and show that overlap coincidence implies simultaneous coincidence in Pisot family
substitution tiling in Rd provided that the associated substitution Delone multi-color
set is ‘admissible’ (Def. 3.2) and the corresponding ‘height group’ (Def. 3.10) is trivial.
Since it is shown in [6, 18] that this group is trivial for irreducible Pisot substitutions,
we know that every irreducible Pisot substitution having pure discrete spectrum must
admit the simultaneous coincidence.
Here we point out that our higher dimensional generalization of strong coincidence
is somewhat too weak condition by itself. It must be fulﬁlled in conjunction with someconstraints to make a reasonable connection to other coincidences. Indeed, without
the constraints of admissibility and trivial height group, for a given substitution tiling,
it is always possible to build an associated substitution Delone multi-color set satisfying our extended notion of strong coincidence. The ﬁrst author [1] obtained a converse
statement from strong coincidence to overlap coincidence using the extended notionof strong coincidence deﬁned in this paper. But in [1], strong coincidence is required
for many choices of admissible control points having trivial height group to deduceoverlap coincidence. It is of interest to minimize the constraints which are suﬃcient
to derive converse direction from strong coincidence to overlap coincidence.
2. Preliminary
2.1. Tiles and tilings
A tile in Rd is deﬁned as a pair T = (A, i) where A = supp(T ) (the support of T )is a compact set in Rd which is the closure of its interior, and i = l(T ) ∈ {1, . . . , m}is the color of T . We let g + T = (g + A, i) for g ∈ Rd . We say that a set P of tiles isa patch if the number of tiles in P is ﬁnite and the tiles of P have mutually disjoint∪
interiors. A tiling of Rd is a set T of tiles such that Rd = {supp(T ) : T ∈ T } anddistinct tiles have disjoint interiors.

3

Definition 2.1. Let A = {T1 , . . . , Tm } be a ﬁnite set of tiles in Rd such that Ti =(Ai , i); we will call them prototiles. Denote by PA the set of non-empty patches.
We say that Ω : A → PA is a tile-substitution (or simply substitution) with a d × dexpansive matrix Q if there exist ﬁnite sets Dij ⊂ Rd for i, j ≤ m such thatΩ(Tj ) = {u + Ti : u ∈ Dij , i = 1, . . . , m}

(2.1)

with
QAj =

m
∪

(Dij + Ai ) for j ≤ m.

(2.2)

i=1

Here all sets in the right-hand side must have disjoint interiors; it is possible for someof the Dij to be empty.
The substitution (2.1) is extended to all translates of prototiles by Ω(x + Tj ) =∪Qx+Ω(Tj ) and to patches and tilings by Ω(P ) = {Ω(T ) : T ∈ P }. The substitutionΩ can be iterated, producing larger and larger patches Ωk (P ). We say that T is a
substitution tiling if T is a tiling and Ω(T ) = T with some substitution Ω. In thiscase, we also say that T is a ﬁxed point of Ω. We say that a substitution tiling isprimitive if the corresponding substitution matrix S, with Sij = ♯(Dij ), is primitive,
and irreducible if the characteristic polynomial of S is irreducible. We say that T
has ﬁnite local complexity (FLC) if ∀ R > 0, ∃ ﬁnitely many translational classes ofpatches whose support lies in some ball of radius R. A tiling T is repetitive if for
any compact set K ⊂ Rd , {t ∈ Rd : T ∩ K = (t + T ) ∩ K} is relatively dense. A
repetitive ﬁxed point of a primitive tile-substitution with FLC is called a self-aﬃnetiling. Let λ > 1 be the Perron-Frobenius eigenvalue of the substitution matrix S.
Let D = {λ1 , . . . , λd } be the set of (real and complex) eigenvalues of Q. We say that
Q (or the substitution Ω) fulﬁlls a Pisot family if for every λ ∈ D and every Galois
conjugate λ′ of λ, if λ′ ̸∈ D, then |λ′ | < 1.
Given a tiling T in Rd , we deﬁne the tiling space as the orbit closure of T under
the translation action: XT = {−g + T : g ∈ Rd }, in the well-known “local topology”:
for a small ϵ > 0 two tilings S1 , S2 are ϵ-close if S1 and S2 agree on the ball of radius
ϵ−1 around the origin, after a translation of size less than ϵ. Then XT is compact and
we get a topological dynamical system (XT , Rd ) where Rd acts by translations. Thissystem is minimal (i.e. every orbit is dense) whenever T is repetitive.
2.2. Point sets
Recall that a Delone set is a relatively dense and uniformly discrete subset of Rd .
We say that Λ = (Λi )i≤m is a Delone multi-color set in Rd if each Λi is Delone and4dsupp(Λ) := ∪m
i=1 Λi ⊂ R is Delone. A cluster of Λ is a family of points P = (Pi )i≤m

where Pi ⊂ Λi is ﬁnite for all i ≤ m. We say that Λ ⊂ Rd is a Meyer set if it is a
Delone set and Λ − Λ is uniformly discrete in Rd [12]. The colors of points in the
Delone multi-color set have the same meaning as the colors of tiles on tilings. Various
notions such as primitivity, FLC and repetitivity in point sets are deﬁned in similar
way as in tilings.
Definition 2.2. Λ = (Λi )i≤m is called a substitution Delone multi-color set if Λ is a
Delone multi-color set and there exist an expansive matrix Q and ﬁnite sets Dij fori, j ≤ m such that
Λi =

m
∪

(QΛj + Dij ),i ≤ m,(2.3)

j=1

where the unions on the right-hand side are disjoint.
For any given substitution Delone multi-colour set Λ = (Λi )i≤m , we deﬁne Φij ={f : x 7→ Qx + a : a ∈ Dij }. Then Φij (Λj ) = QΛj + Dij , where i ≤ m. We
deﬁne Φ an m × m array for which each entry is Φij . For any k ∈ Z+ and x ∈ Λjwith j ≤ m, we let Φk (x) = Φk−1 ((Φij (x))i≤m ). For any k ∈ Z+ , Φk (Λ) = Λ and∪Φk (Λj ) = i≤m (Qk Λj + (Dk )ij ) where(Dk )ij =∪(Din1 + QDn1 n2 + · · · + Qk−1 Dn(k−1) j ).

n1 ,n2 ,...,n(k−1) ≤m

We say that a cluster P is legal if it is a translate of a subcluster of a cluster generated∪kkfrom one point of Λ, that is to say, a + P ⊂ Φk (x) (i.e. a + P ⊂ m
i=1 (Q x + (D )ij ))for some k ∈ Z+ , a ∈ Rd , x ∈ Λj , and j ≤ m.
Definition 2.3. Let Λ be a primitive substitution Delone multi-color set in Rd withan expansive matrix Q. We say that Λ admits an algebraic coincidence if there
exist M ∪∈ Z+ and ξ ∈ Λi for some i ≤ m such that QM Ξ(Λ) ⊂ Λi − ξ, whereΞ(Λ) = i≤m (Λi − Λi ).
Since Λ is primitive, there exists N ∈ N such that QN Ξ(Λ) ⊂ Λi − Λi for any
i ≤ m. So Λ admits an algebraic coincidence if and only if there exists M ∈ N andξ ∈ Λi such that QM (Λi − Λi ) ⊂ Λi − ξ. We say that Λ is a Pisot family substitution
Delone multi-color set if Q fulﬁlls the condition of Pisot family.
If a self-aﬃne tiling T is given, we can get an associated substitution Delone multicolor set ΛT = (Λi )i≤m of T taking representative points of tiles in the relatively same
positions for the same color tiles in the tiling (see [13, Lemma 5.4]). On the other5

hand, if Λ is a primitive substitution Delone multi-color set for which every Λ-cluster
is legal, then Λ + A := {x + Ti : x ∈ Λi , i ≤ m} is a tiling of Rd , where A is the setof prototiles from the associated tile equations (see [14]). This bijection establishes a
topological conjugacy of (XΛ , Rd ) and (XT , Rd ).
Note that if we translate representative points of tiles of T by Λ′i = Λi − gi , thenthe set equation will be
Λ′i =

m
∪

QΛ′j + Dij′

j=1

with Dij′ = {dij − Qgj + gi

: dij ∈ Dij , 1 ≤ i, j ≤ m}, or in short, Dij′ = Dij −Qgj +gi .

The corresponding tile equation becomes
QA′j =∪

A′i + Dij′

which is satisﬁed by A′j = Aj + gj . So we set supp(Tj′ ) = A′j and the color of Tj′ to be
the one of Tj . Such modiﬁcation only translates supports of tiles and corresponding
point sets, which causes non essential changes of the description of T . Hereafter, we
do not distinguish such changes of reference points and use the same symbols Λi andTi .
Since the representative points of tiles in a tiling T are taken in the relatively
same position for the same type of tiles, for each i ≤ m we deﬁne a reference pointci ∈ Rd for the prototile Ti and can take an associated substitution Delone multi-colorset Λ = ΛT = (Λi )i≤m satisfying T = {Ti − ci + u | u ∈ Λi , i ≤ m}.
The topological dynamical system (XT , Rd ) has a unique invariant Borel probability measure µ when the tiling T is a self-aﬃne tiling (see [19, 14]). The dynamical
spectrum of the system (XT , Rd , µ) refers to the spectrum of the unitary operator
Ux arising from the translational action on the space of L2 -functions on XT . We saythat the tiling T has pure discrete dynamical spectrum if the eigenfunctions for the
Rd -action span a dense subspace of L2 (XT , µ) [19].
2.3. Overlap coincidence
Let Ξ(T ) = {y ∈ Rd : T = y + S, where T, S ∈ T }. A triple (u, y, v), withu + Ti , v + Tj ∈ T and y ∈ Ξ(T ), is called an overlap if(u + Ai − y)◦ ∩ (v + Aj )◦ ̸= ∅,where Ai = supp(Ti ) and Aj = supp(Tj ). An overlap (u, y, v) is a coincidence if
u − y = v and u + Ti , v + Ti ∈ T for some i ≤ m.
6

Let O = (u, y, v) be an overlap in T , we deﬁne ℓ-th inﬂated overlapΩℓ O = {(u′ , Qℓ y, v ′ ) : u′ + Tk ∈ Ωℓ (u + Ti ), v ′ + Tr ∈ Ωℓ (v + Tj ), and (u′ , Qℓ y, v ′ ) is an overlap}.
Definition 2.4. We say that a self-aﬃne tiling T admits overlap coincidence if there
exists ℓ ∈ Z+ such that for each overlap O in T , Ωℓ O contains a coincidence.
Theorem 2.5. [14, 13] Let T be a self-aﬃne tiling in Rd for which Ξ(T ) is a Meyer
set. Then (XT , Rd , µ) has pure discrete dynamical spectrum if and only if T admits
overlap coincidence.
Theorem 2.6. [13] Let T be a self-aﬃne tiling in Rd for which Ξ(T ) is a Meyer set
and Λ = ΛT = (Λi )i≤m be an associated substitution Delone multi-color set. Then T
admits overlap coincidence if and only if Λ admits algebraic coincidence.
3. Strong coincidence and Simultaneous coincidence in Rd
A substitution σ over m letters {1, 2, . . . , m} is called primitive, when its substitution matrix Mσ is primitive. We say that σ is irreducible if the characteristic
polynomial of Mσ is irreducible, and it is Pisot, if the Perron Frobenius root β of Mσ
is a Pisot number. Then we can construct a bi-inﬁnite sequence which is generated byσ from some ﬁxed letters around the origin and deﬁne the natural suspension tilingT in R with an expansion factor β arose from σ by associating to the letters of thebi-inﬁnite sequence the intervals whose lengths are given by a left eigenvector of Mσcorresponding to β. In this case, β is identiﬁed with the 1 × 1 expansive matrix
Q = (β). Let Ω be the corresponding tile-substitution and let A = {T1 , . . . , Tm }be the corresponding prototiles of the intervals whose left end points are all at theorigin. Taking the left end points of the intervals of tiles in the tiling, we can get anassociated substitution Delone multi-color set. We can interpret “strong coincidence”
of σ into the tiling setting in the following way:
Definition 3.1. Let T be the suspension tiling in R of a substitution σ. We say that
T admits preﬁx strong coincidence if for any pair of prototiles {Ti , Tj } ⊂ A, there
exists L ∈ N such that two supertiles ΩL Ti and ΩL Tj have at least one common tilewhere Ω is the tile-substitution.
We generalize this deﬁnition of strong coincidence to Rd by using the reference
points.
Definition 3.2. Let T be a self-aﬃne tiling in Rd . Let ci be the reference point of Ti
for i ≤ m. We say that the set of the reference points is admissible if ∩i≤m (supp(Ti ) −ci ) has non-empty interior.
7

Clearly, the left end points of the 1-dimensional suspension tiling form a set of admissible reference points.
Definition 3.3. Let T be a self-aﬃne tiling in Rd with an expansion Q. Let A ={T1 , · · · , Tm } be the prototile set of T . Let ci be the reference point of Ti for i ≤ mwhose set is admissible. Let Λ be an associated substitution Delone multi-color set
for which T = {ui + (Ti − ci ) | ui ∈ Λi , i ≤ m}. If for any 1 ≤ i, j ≤ m, there is apositive integer L that
ΩL (Ti − ci ) ∩ ΩL (Tj − cj ) ̸= ∅,(3.1)

i.e. the left hand side contains at least one tile, then we say that Λ admits strong
coincidence.
Set
G :=

∞
∪

Q−k (Λi − Λi ),for some i ≤ m.

k=0This set is independent of the choice of i. Indeed by the primitivity of Λ, for any
i, j ≤ m, there exists n ∈ N that
Qn (Λi − Λi ) ⊂ Λj − Λj .
In plain words, G is the set of eventual return vectors, i.e., vectors v ∈ Rd such that
there is an n ∈ N that Qn v is a return vector of T .
Remark 3.4. If Λ admits strong coincidence, then notice that for any i, j ≤ m, there
is a common tile Tk − ck + η ∈ ΩL (Ti − ci ) ∩ ΩL (Tj − cj ) for some η ∈ Rd , L ∈ N andk ≤ m. Thus QL Λi + η ⊂ Λk and QL Λj + η ⊂ Λk . So

Thus for any i, j ≤ m,

QL (Λi ∪ Λj ) ⊂ Λk − η .

(3.2)

QL (Λi − Λj ) ⊂ Λk − Λk

(3.3)

and we obtainΛ − Λ ⊂ G,

where Λ = ∪i≤m Λi .

Remark 3.5. Assume that Λ = ΛT = (Λi )i≤m admits algebraic coincidence. Thereis L ∈ N and η ∈ Rd that QL (Λi − Λi ) ⊂ Λi − η for some i. This implies
QL (Λi − Λi ) − QL (Λi − Λi ) ⊂ Λi − Λi .
This is equivalent to the fact that the set of eventual return vectors G forms an additive
group, i.e., G = ⟨G⟩Z , where ⟨G⟩Z is the additive group generated by the elements of
G. Among self-aﬃne tilings, it is interesting to characterize when G = ⟨G⟩Z holds.
For e.g., consider the suspension tiling of Thue-Morse substitution 0 → 01, 1 → 10
8

which does not admit overlap coincidence. Taking the left end points of the tiles inthe tiling, we have
{ ℓ
}
ℓ
∑
∑
Λk ∩ [0, ∞) =bi 2i : bi ∈ {0, 1},bi ≡ k (mod 2) and ℓ ∈ Z≥0
i=0

i=0

with k ∈ {0, 1}. One can easily express each element of Λ1 ∩ [0, ∞) as a diﬀerence ofΛ0 ∩ [0, ∞). So we can show that G = Z[1/2], which forms a group. This example
also shows that the converse of Remark 3.4 does not hold: Λ − Λ ⊂ G does not imply
strong coincidence. A similar idea using beta-integer√ with golden mean base works
in Example 4.6, and we can prove that G = Z[(1 + 5)/2]. We do not know yet any
example of a self-aﬃne tiling for which G is not a group.
Given a self-aﬃne tiling T , there are many ways to associate a substitution Delone
multi-color set. Indeed, Deﬁnition 3.1 used the left end points but one may choose
other reference points. Arnoux-Ito [8] gave the strong coincidence with respect toright end points as well, that is, suﬃx strong coincidence1 . There is a standard way
to associate Delone multi-color set to a given self-aﬃne tiling. A tile map γ : T → T
sends a tile T to the one in Ω(T ) such that γ(T1 ) and γ(T2 ) are located in the same
relative position in Ω(T1 ) and Ω(T2 ) whenever T1 and T2 have the same color. A
control point c(T ) of T ∈ T is deﬁned byc(T ) =∞∩Q−n (γ n T ).

n=1

The color of the control point c(T ) is given by the color of the tile (T ). By deﬁnition
control points of the same color tiles are located in the same relative position and theset of control points C is invariant under the expansion by Q, that is, QC ⊂ C. We
can choose control points as representative points. Let Λi be chosen to be the control
points of tiles in T of color i. Then C = (Λi )i≤m . The set of control points C forms a
substitution Delone multi-color set.
Example 3.6. The substitution σ deﬁned by a → aba, b → bab satisﬁes neither preﬁx
nor suﬃx strong coincidence. However deﬁne the tile map γ by choosing Tb in σ(Ta )and the left most Tb in σ(Tb ), then Λ admits strong coincidence by the choice of thecontrol points.
Now we introduce a stronger notion than Deﬁnition 3.3:
1

In [8], preﬁx (resp. suﬃx) strong coincidence is called positive (resp. negative) strong coinci-

dence.

9

Definition 3.7. Let T be a self-aﬃne tiling in Rd with expansion Q. Let A ={T1 , · · · , Tm } be the prototile set of T . Let ci be the reference point of Ti for i ≤ mwhose set is admissible. Let Λ be an associated substitution Delone multi-color set
for which T = {ui + (Ti − ci ) | ui ∈ Λi , i ≤ m}. If there is a positive integer L thatm∩

ΩL (Ti − ci ) ̸= ∅,

(3.4)

i=1

i.e. the left hand side contains at least one tile, then we say that Λ admits simultaneous
coincidence.
Remark 3.8. By the similar argument as Remark 3.4, if Λ admits simultaneous
coincidence then there exists L ∈ N, η ∈ Rd and k ≤ m such that
L

Q (

m
∪

Λi ) ⊂ Λk − η .

(3.5)

i=1

Remark 3.9. In d = 1 in Arnoux-Ito’s framework of [8], they have chosen the left
(or right) end points as control points. It is plausible that their deﬁnition of geometricsubstitution acting on broken segments would work by other choices of control points
by shifting the origin to the control points located on the 1-dimensional suspension
tiling in the expanding line of Mσ . In this case, a unit segment will grow in preﬁx
and suﬃx directions at a time, which ﬁts better with the preﬁx-suﬃx construction
by Canterini and Siegel [9]. The deﬁnition of strong coincidence would naturally be
extended in the form to assure that some iterates of every pair of two unit segments
share a common segment.
For a Pisot substitution tiling in R, one can consider a substitution Delone multicolor set Λ taking reference points from the left end points of tile intervals. The
height group of Λ is deﬁned by Sing [18] which generalizes an idea of Dekking [10] forconstant length substitution. We extend this deﬁnition to general substitution Delone
multi-color sets in Rd .
Definition 3.10. The height group of Λ = (Λi )i≤m in Rd is the quotient group⟨Λ − Λ⟩Z / ⟨Λi − Λi | i ≤ m⟩Z ,where Λ = ∪i≤m Λi .

Given a tiling T in Rd , the height group also depends on the choice of Λ.
Example 3.11. Consider again the substitution in Example 3.6. Taking the left
end points of Ta and Tb , we have Λ = Λa ∪ Λb = Z, ⟨Λ − Λ⟩Z = Z, and ⟨Λi −Λi | i ∈ {a, b}⟩Z = 2Z. Thus the height group is Z/2Z. The same is true for theright end points. However the third choice in Example 3.6 gives the height group(2/3)Z/2Z ≃ Z/3Z. We note that the height group is not trivial by any choice ofadmissible reference points. In fact, let ca and cb be reference points of the prototiles
Ta = ([0, 1], a) and Tb = ([0, 1], b) in R. To be admissible, |cb − ca | < 1. But if
the height group were trivial, then we have cb − ca ∈ 2Z, which shows ca = cb and⟨Λ − Λ⟩Z = Z.
10

4. From overlap coincidence to strong coincidence
A van Hove sequence for Rd is a sequence F = {Fn }n≥1 of bounded measurable
subsets of Rd satisfying
lim Vol((∂Fn )+r )/Vol(Fn ) = 0, for all r > 0,

n→∞

(4.1)

where (∂Fn )+r = {x ∈ Rd : dist(x, Fn ) ≤ r}.
For any S ⊂ T and van Hove sequence {Fn }n≥1 , we deﬁnevol(S ∩ Fn )n→∞vol(Fn )dens(S) := lim

if the limit exists. Here the density limit is dependent on the van Hove sequence. In
the case of a self-aﬃne tiling T , if S is a set of all the translates of a patch in T , thedensity exists uniformly [14].
The following theorem shows that overlap coincidence of T implies strong coincidence of ΛT as long as the reference points for the tiling can be chosen to satisfy(4.2). This theorem can be proved using various results for pure discrete spectrum
such as [19, Thm. 6.2] and [7, Prop. 1].
Theorem 4.1. Let T be a self-aﬃne tiling in Rd with expansion Q for which Ξ(T ) isa Meyer set. Let Λ = ΛT = (Λi )i≤m be an associated admissible substitution Delone
multi-color set. Assume thatΛ − Λ ⊂ ⟨G⟩Z ,
(4.2)
∪
−k
where Λ = ∪i≤m Λi and G == ∞k=0 Q (Λi − Λi ) for some i ≤ m. Then overlap
coincidence of T implies strong coincidence of Λ. Furthermore overlap coincidenceof T implies simultaneous coincidence of Λ.
Proof. For any i, j ≤ m, take vi ∈ Λi and vj ∈ Λj . Let α = vj − vi . By theassumption,α ∈ Λj − Λi ⊂ ⟨G⟩Z .
From Theorem 2.6 and Remark 3.5, G = ⟨G⟩Z . Therefore there is M ∈ N such that
QM α ∈ Λ1 − Λ1 . Overlap coincidence implies thatdens T ∩ (T − Qn α) −→ 1

(4.3)

as n → ∞ [19]. Since T has uniform patch frequencies [14], the density is notdependent on the choice of the van Hove sequence. So we can take a van Hove sequence11

{supp(Ωn (Ti − ci + vi ))}n≥1 . Then we observe that T admits strong coincidence,otherwise the density is bounded away from one.
Furthermore, we claim that Λ admits simultaneous coincidence. Fix k ≤ m andvk ∈ Λk . For any i ≤ m, choose vi ∈ Λi . Let αi = vk − vi . By the admissibility of Λ,∩i≤m supp(Ti − ci + vk ) has non-empty interior. Let
Pn =∩supp(Ωn (Ti − ci + vi + αi )) for n ∈ N.

i≤m

Then {Pn }n≥1 is a van Hove sequence and Ωn (Tk − ck + vk ) is a patch in T . From theoverlap coincidence of T , for each i ≤ mvol(Ωn (Tk − ck + vk ) ∩ Ωn (Ti − ci + vi + αi ) ∩ Pn ) n→∞−→ 1 .
vol(Pn )
Thus
1−

vol

((∩

)
)
i≤m,i̸=k Ω (Tk − ck + vk ) ∩ Ω (Ti − ci + vi + αi ) ∩ Pnnnvol(Pn ))n∑ (vol (Ω (Tk − ck + vk ) ∩ Ωn (Ti − ci + vi + αi ) ∩ Pn )≤1−−→ 0 .
vol(Pn)
i≤m,i̸=k

It implies that there exists n ∈ N such that∩Ωn (Tk − ck + vk ) ∩ Ωn (Ti − ci + vi + αi ) ∩ Pn ) ̸= ∅ .

i≤m,i̸=kThus∩Ωn (Tk − ck ) ∩ Ωn (Ti − ci ) ̸= ∅i≤m,i̸=k□

and the claim follows.

Corollary 4.2. Let T be a self-aﬃne tiling in Rd for which Ξ(T ) is a Meyer set.
Let Λ = ΛT = (Λi )i≤m be an associated admissible substitution Delone multi-color
set with a trivial height group. Then overlap coincidence of T implies simultaneous
coincidence as well as strong coincidence of Λ.
Proof. The trivial height group assumption implies Λ − Λ ⊂ ⟨G⟩Z .

□We provide a lemma.
Lemma 4.3. Let A be a m × m integer matrix whose characteristic polynomial isirreducible. Then the entries of an eigenvector of A are linearly independent over Q.

12Proof. Let α be an eigenvalue of A and (v1 , v2 , . . . , vm ) ∈ Q(α)m be a corresponding
eigenvector. Denote by αi (i = 1, . . . , m) the conjugates of α. Applying Galois conjugate map τi which sends α to αi , we obtain d diﬀerent eigenvectors (τi (v1 ), . . . , τi (vm )).
Since αi (i = 1, . . . , m) are all distinct, the corresponding eigenvectors are linearly independent over C. So B := (τi (vj )) is invertible. However if v1 , v2 , . . . , vm are linearly
dependent over Q, then the column vectors of B are linearly dependent over C which□

is a contradiction.

Now we consider an 1-dim substitution tiling and recall the following lemma from[18, Lemma 6.34] and [6, Thm. 12.1]).
Lemma 4.4. [18, 6] Let σ be a primitive irreducible substitution and consider its
suspension tiling of R with an expansion factor β, the Perron Frobenius root of thesubstitution matrix Mσ . Let Λ be an associated substitution Delone multi-color set
whose points are taken from the left end of tiles in the suspension tiling. Then wehave⟨Λi − Λi | i ≤ m⟩Z = ⟨(∪i≤m Λi ) − (∪i≤m Λi )⟩Z .

(4.4)

Corollary 4.2 and Lemma 4.4 give a combinatorial result on Pisot substitution
sequences: the overlap coincidence implies strong and simultaneous coincidence for
1-dim irreducible Pisot substitutions. This result agrees with the earlier results of[6, 4].
Corollary 4.5. Let σ be the irreducible Pisot substitution over letters {1, . . . , m}whose natural suspension tiling satisﬁes overlap coincidence. Then there are L ∈ N
and M ∈ N such that preﬁxes of length M of σ L (1), σ L (2), . . . , σ L (m) has the same
number of each letter j for 1 ≤ j ≤ m, and all ends with an identical letter.
Proof. As in Lemma 4.4, we choose the left end points as the set of control points.
Then it fulﬁlls the conditions of the admissibility and the trivial height group of
Theorem 4.1. Theorem 4.1 shows that the suspension tiling satisﬁes simultaneous
coincidence by taking n-th iterates of all prototiles. Since the suspension lengthsof prototiles form a left eigenvector of Mσ , they are linearly independent over Q by
Lemma 4.3. Counting the number of tile types in n-th iterate of each tile up to thetile where simultaneous coincidence occurs, we can claim the result.

□

Example 4.6. We give an example of a substitution tiling for which an associatedadmissible substitution Delone multi-color set has a trivial height group, but it admits neither overlap coincidence nor strong coincidence (simultaneous coincidence).
Consider the substitution σ over four letters {a, b, A, B} deﬁned bya → aB, b → a, A → Ab, B → A.
13

This is Z/2Z-extension of Fibonacci substitution. The suspension tiling dynamics
does not satisfy overlap coincidence as it is computed in [3]. The suspension lengths
of capital letter and non capital letter are the same. Introduce a letter to the letter
involution τ which interchanges capital letter to non capital letter and vice versa.
Then τ and σ commutes from τ (σ n (a)) = σ n (A) for all n ∈ N, we see that σ does notsatisfy preﬁx (nor suﬃx) strong coincidence. However taking the left end points as
reference points, the height group is trivial which is conﬁrmed by collecting all return
vectors.
Example 4.7. Consider the substitution σ over six letters {a, b, c, A, B, C} deﬁned
bya → aB, b → aC, c → a, A → Ab, B → Ac, C → A.
This is Z/2Z-extension of the Rauzy substitution. The suspension tiling dynamicsof σ satisﬁes overlap coincidence which is checked by the algorithm in [3]. By thesame reasoning as Example 4.6, this substitution does not satisfy preﬁx nor suﬃx
strong coincidence. Taking the left end points and collecting all return vectors, we
can compute that the height group is equal to Z/2Z.
On the other hand, taking the tile map γ which sends
a → B, b → C, c → a, A → A, B → A, c → A,
the set of control points is admissible and satisﬁes simultaneous coincidence. One canalso check that the height group associate to this control points is trivial. So thisgives an example of Corollary 4.2 for a reducible substitution.
Remark 4.8. Nakaishi [16] claimed that unimodular Pisot substitutions with preﬁx
strong coincidence generate pure discrete spectrum of the dynamical system. It would
mean that strong coincidence implies overlap coincidence in the associated substitution tilings in R. So together with Corollary 4.5 the equivalence between overlap
coincidence and strong coincidence could be established. We hope directly to observe
the result of [16], the implication from strong coincidence to overlap coincidence inthe framework of this paper.
Acknowledgment
The authors would like to thank the referees for the valuable comments and references. This research was supported by Basic Research Program through the National
Research Foundation of Korea(NRF) funded by the Ministry of Education, Scienceand Technology(2010-0011150) and the Japanese Society for the Promotion of Science(JSPS), Grant in aid 21540010. The second author is grateful for the support of KIAS
for this research.

14

References[1] S.Akiyama, Strong coincidence and overlap coincidence, submitted.
[2] S. Akiyama, M. Barge, V. Berthé, J.-Y. Lee and A. Siegel, On the Pisot substitution conjecture, Preprint.
[3] S. Akiyama and J.-Y. Lee, Algorithm for determining pure pointedness of selfaﬃne tilings, Adv. Math. 226 (2011), 2855–2883.
[4] V. Baker, M. Barge and J. Kwapisz, Geometric realization and coincidence for
reducible non-unimodular Pisot tiling spaces with an application to shifts, J.
Instit. Fourier. 56(7) (2006), 2213–2248[5] M. Barge and B. Diamond, Coincidence for substitutions of Pisot type, Bull. Soc.
Math. France 130 (2002), no. 4, 619–626.
[6] M. Barge and J. Kwapisz, Geometric theory of unimodular Pisot substitutions,Amer. J. Math. 128(5) (2006), 1219–1282.
[7] M. Barge, S. Stimac and R. F. Williams, Pure discrete spectrum in substitution
tiling spaces, Discrete and Continuous Dynamical Systems -A, 2 (2013), 579–597.
[8] P. Arnoux and S. Ito, Pisot substitutions and Rauzy fractals, Bull. Belg. Math.
Soc. Simon Stevin 8 (2001), 181–207.
[9] V. Canterini and A. Siegel, Geometric representation of substitutions of Pisot
type, Trans. Amer. Math. Soc. 353 (12) (2001), 5121–5144.
[10] M. Dekking, The spectrum of dynamical systems arising from substitutions ofconstant length, Z. Wahrsch. Verw. Gebiete 41 (1978), 221–239.
[11] M. Hollander and B. Solomyak, Two-symbol Pisot substitutions have pure discrete spectrum, Ergodic Theory Dynam, Systems 23(2) (2003), 533–540.
[12] J. C. Lagarias, Meyer’s concept of quasicrystal and quasiregular sets, Commm.
Math. Phys. 179 (1996), 365–376.
[13] J.-Y. Lee, Substitution Delone sets with pure point spectrum are inter-model
sets, Journal of Geometry and Physics 57 (2007), 2263-2285.

15

[14] J.-Y. Lee, R. V. Moody, and B. Solomyak, Consequences of pure point diﬀraction
spectra for multiset substitution systems, Discrete Comp. Geom. 29 (2003), 525–
560.
[15] J.-Y. Lee and B. Solomyak, Pisot family self-aﬃne tilings, discrete spectrum, andthe Meyer property. Discrete and Continuous Dynamical Systems - A. 32 (2012),
935 - 959.
[16] K. Nakaishi, Pisot conjecture and Rauzy fractals, Preprint.
[17] A. Siegel, Répresentation des systèmes dynamique substitutifs non unimodulaires, Ergodic Theory Dynam. Systems 23(4) (2003), 1247–1273.
[18] B. Sing, Pisot substitutions and beyond, Ph. D. Thesis (2006).
[19] B. Solomyak, Dynamics of self-similar tilings, Ergodic Th. Dynam. Sys. 17 (1997),
695–738. Corrections to ‘ Dynamics of self-similar tilings’, ibid. 19 (1999), 1685.
[20] V. F. Sirvent and B. Solomyak, Pure discrete spectrum for one-dimensional substitution systems of Pisot type. Canad. Math. Bull. 45(4) (2002) 697–710. Dedicated to Robert V. Moody.

16