Coincidences, Colourings and Similarities
Manuel J. Loquias, Peter Zeiner
University of Bielefeld
Bielefeld, Germany
Abstract
This contribution is based on a talk given by the second author inKyoto at RIMS, June 2010. It gives an overview of some recent developments in the theory of coincidence site lattices (CSLs). In particular, theconnections between similar sublattices and CSLs, coincidences of latticecolourings, and coincidences of shifted lattices are discussed.

1

Coincidence Site Lattices (CSLs)

1.1

Brief historical overview

1911: first ideas by Friedel [1]mid sixties, seventies: CSLs are investigated to discribe grain boundaries incrystals
Ranganathan, Bollmann, Grimmer, . . . [2, 3, 4]. . .
mid ninties: generalization for quasicrystals: Coincidence Site Modules (CSMs)
Baake, Pleasants, Warrington, . . . [5, 6]. . .
2002: Quantizing Using Lattice Intersections
Sloane, Beferull–Lozano [7]20xy: Baake, Grimm, Heuer, Moody, Pleasants, Scharlau, Loquias, Glied,Huck, PZ, Zou, . . .

1.2

Commensurate Lattices

A key notion is the concept of commensurability. We call two lattices Γ1 andΓ2 commensurate, if one of the following properties is satisfied.
Lemma 1.1. The following are equivalent:• Γ1 ∩ Γ2 is a sublattice of both Γ1 and Γ2 .
• Γ1 ∩ Γ2 is a sublattice of Γ1 or Γ2 .
• There exists an m ∈ N such that mΓ1 ⊆ Γ2 and mΓ2 ⊆ Γ1 .
• There exists an m ∈ N such that mΓ1 ⊆ Γ2 or mΓ2 ⊆ Γ1 .
1

1.3

Ordinary CSLs

Definition 1.1. Let Γ ⊂ Rd be a lattice, R ∈ O(d). ThenΓ(R) := Γ ∩ RΓis called a (simple,ordinary) coincidence site lattice (CSL), if Γ and RΓ arecommensurate. The index
Σ(R) := [Γ : Γ(R)] < ∞is called coincidence index.
For a concise introduction we refer to [8].

Figure 1: The figure shows a square lattice (black dots) and a copy (red cir2+icles) rotated by eiϕ = 2−i(corresponding to a rotation through an angle
ϕ = arctan 4/3). One clearly sees the CSL formed by the coinciding dots andcircles. The shaded areas indicate a fundamental domain for each of the lattices.

1.4

Coincidence isometries

Lemma 1.2. The set of all coincidence isometries
OC(Γ) := {R ∈ O(d) Σ(R) < ∞}forms a group, a subgroup of O(d). LikewiseSOC(Γ) := OC(Γ) ∩ SO(d)is a group.
2

The group of coincidence isometries is never empty. In particular, if P (Γ)
denotes the point group of Γ, we have
Lemma 1.3. The following are equivalent:
1. R ∈ P (Γ)
2. Σ(R) = 1
Corollary 1.4. P (Γ) = {R ∈ OC(Γ) Σ(R) = 1} ⊆ OC(Γ)

1.5Some Properties of the Coincidence Index

Lemma 1.5. For any coincidence isometry R
Σ(R) = Σ(R−1 ).

1.6

Coincidences of the dual lattice

Lemma 1.6. Γ and its dual lattice Γ∗ have the same coincidence isometries,i.e.
OC(Γ∗ ) = OC(Γ).
SOC(Γ∗ ) = SOC(Γ).
The coincidence index is the same for both lattices:Σ(R)∗ = Σ(R).

1.7

Coincidences of Sublattices

Lemma 1.7. Let Γ1 ⊆ Γ with index m := [Γ : Γ1 ]. Then
OC(Γ1 ) = OC(Γ).
Let Σ1 (R) be the coincidence index with respect to Γ1 . Then
Σ(R) mΣ1 (R)Σ1 (R) mΣ(R).
Compare [8, 9].

1.8Example Z2 ≃ Z[i]For more details on this example, see [8].

3

1.8.1

Coincidence rotations

Let ε ∈ {±1, ±i} be a unit of Z[i], and write any splitting prime p = 1 (mod 4)
as p = ωp ω̄p . Then the coincidence rotations are all of the formY  ωp npiϕe =ε,ω̄pp≡1 (4)

where only finitely many np 6= 0.
1.8.2

Coincidence indexYΣ(eiϕ ) =p|np |p≡1 (4)1.8.3

Spectrumset of all integers that contain only prime factors p ≡ 1 (mod 4).
1.8.4CSLs of Z[i]Let
ω(ϕ) :=Yωpnpp≡1 (4)
np >0Yω̄pnp

p≡1 (4)
np <0Then the CSL corresponding to the rotation eiϕ is given by
Z[i] ∩ eiϕ Z[i] = ω(ϕ)Z[i]1.8.5

Generating fuctions

The number f (m) of different CSLs can be nicely expressed in terms of theDirichlet series
Φ(s) =∞Xf (m)

m=1ms

=

Y 1 + p−s
1 − p−sp≡1(4)

2222222=1+ s + s + s + s + s + s + s
51317252937412242+ s + s + s + s + ...
5361
65
73

1.9

Example: Ammann-Beenker tiling

Coincidences of aperiodic tilings can be described via their underlying limit
translation module, giving rise to CSMs (coincidence site modules). For theapplication to tilings an additional so–called acceptance factor has to be taken
into account. [6, 8]

4

Figure 2: Amman Beenker tiling. The black dots √indicate
the coincidences
for a rotation R about the center by θ = tan−1 −2 2 ≈ 109.5◦ , Σ(R) = 9
acceptance factor = 0.980572924 . . . [9, 10]

1.10

Equal CSLs
S ∈ P (Γ)

Lemma 1.8.

=⇒Γ(R) = Γ(RS)Though the converse is true for several lattices, like the square and triangle
lattice in d = 2 and the cubic lattices in d = 3, it does not hold in general.
In particular, there are rotations S 6∈ P (Γ) such that Γ(R) = Γ(RS) for thefollowing lattices: Γ = (2Z)2 × Z, Z4 , D4 , A4
Open question: When does Γ(R) = Γ(RS) imply S ∈ P (Γ)?
1.10.1

Example: Root lattice A4

Let f (m) be the number of CSLs and |P (A4 )|f rot (m) the number of coincidence
isometries of the root lattice A4 of index m, where |P (A4 )| denotes the orderof the point group P (A4 ). Clearly f rot (m) ≥ f (m). The following generating
functions show that they are not equal in general.
Φrot
A4 (s) ==∞Xf rot (m)ms

m=11−sY

1+5
1 − 52−sp≡±1(5)(1 + p−s )(1 + p1−s )(1 − p1−s )(1 − p2−s )Yp≡±2(5)

1 + p−s1 − p2−s

10 20 30 50 50 80 90 150 144
5= 1 + s + s + s + s + s + s + s + s + s + s + ···2345678910115ΦA4 (s) ==

1+6=1+∞Xf (m)m=1
−s51−52−smsQp≡±2(5)1+p−s
1−p2−sQp≡±1(5)1+p−s +2p1−s +2p−2s +p1−2s +p1−3s(1−p2−s )(1−p1−2s )10 20
650 50 80 90
30
144
5+ s + s + s + s + s + s + s + s + s + ···2s34567891011For more details, see [11, 12, 13]

1.11

Multiple CSLs

Definition 1.2. Let Γ ⊂ Rd be a lattice, Ri ∈ OC(Γ). Then
Γ(R1 , . . . , Rn ) := Γ ∩ R1 Γ ∩ . . . ∩ Rn Γ = Γ(R1 ) ∩ . . . ∩ Γ(Rn )is called a multiple coincidence site lattice (MCSL).
The index
Σ(R1 , . . . , Rn ) := [Γ : Γ(R1 , . . . , Rn )] < ∞is called coincidence index.
For more information, see [14, 15, 16].

1.12

Known CSLs (and similar sublattices)• Square lattice, hexagonal lattice [8, 17]• certain planar modules with N –fold symmetry [6, 17]• cubic lattices and related modules [4, 18, 8, 19, 20]• hypercubic lattices [8, 21]• A4 –lattice, ring of icosians [11, 12, 13]

2Similar Sublattices

For more details see [22, 23, 24, 25].

2.1

Similarity Transformations

Definition 2.1. Let α ∈ R+ and R ∈ O(d). Then
A : Rd → Rd

x → αRx

is called a linear similarity transformation.
6

2+iFigure 3: A square lattice and two copies of it rotated by eiϕ = 2−i(red circles)
2−i−iϕiϕ −iϕand e= 2+i (green circles), respectively. The MCSL Γ(e , e ) consistsof all points where the black dots and the red and green circles coincide, afundamental domain of it is given by the yellow area.

2.2

Similar Sublattice

Definition 2.2. Let A = αR be a linear similarity transformation and Γ ⊆ Rda lattice. Then A is called a similarity transformation of Γ ifAΓ = αRΓ ⊆ Γ.
In this case AΓ = αRΓ is called a similar sublattice (similarity sublattice).

2.3

Index of a Similar Sublattice

Lemma 2.1. For any similar sublattice of the lattice Γ ⊆ Rd :[Γ : αRΓ] = αd ∈ N.

2.4

Similarity Isometries

Definition 2.3. An isometry R ∈ O(d) is called a similarity isometry of Γ,
if there exists an α ∈ R+ such that αR is a similarity transformation of Γ.

7

Figure 4: Similar sublattices of a square lattice of index 2 and 5, the latter also
occuring as CSL, see above.
Lemma 2.2. The set of all similarity isometries of Γ forms a group, calledOS(Γ). In particular OS(Γ) is a countable subgroup of O(d). Likewise SOS(Γ) :=OS(Γ) ∩ SO(d) is a countable subgroup of SO(d).

3Coincidence Isometries versus Similarity Isometries

Theorem 3.1. For any d–dimensional lattice Γ we have
• OC(Γ) ⊆ OS(Γ)• OS(Γ)/OC(Γ) is abelian.
• Moreover g d = e for any g ∈ OS(Γ)/OC(Γ).
• In particular, if d = p for some prime p, then OS(Γ)/OC(Γ) is a p–group.
See [26, 27].

3.1

Coincidence Isometries versus Similarity Isometries

Lemma 3.2.
OC(Γ) = {R ∈ OS(Γ) den(R) ∈ N} ⊆ OS(Γ) ⊂ O(d)3.2

Denominator (“Minimal Blow–up factor”)

Definition 3.1. Let R ∈ OS(Γ). ThendenΓ (R) := min{α ∈ R+ αRΓ ⊆ Γ}.
8Lemma 3.3. Let R ∈ OS(Γ). Then{α ∈ R αRΓ ⊆ Γ} = denΓ (R)Z.
Lemma 3.4. denΓ (R) = 1 if and only if R ∈ P (Γ).
Lemma 3.5. Let R ∈ OS(Γ). ThendenΓ (R)d ∈ N

3.3

Coincidence Index and Denominator

Lemma 3.6. Let m := lcm(denΓ (R), denΓ (R−1 )) and n := gcd(denΓ (R), denΓ (R−1 )).
Thenm Σ(R) ndΣ(R)2 md

andRemark 3.1. If d = 2 thenΣ(R) = denΓ (R) = denΓ (R−1 ).

3.4

Primitive Similar Sublattices

Definition 3.2. A similar sublattice Γ1 of Γ is called primitive, if n1 Γ1 6⊆ Γ forall n > 1.
Lemma 3.7. A similar sublattice Γ1 of Γ is primitive if and only if there exists
an R ∈ OS(Γ) such that
Γ1 = denΓ (R)RΓ.

3.5

Example: square lattice

Let a(m) and apr (m) denote the number of similar and primitive similar sublattices of the square lattice. These functions are multiplicative and have thefollowing generating function. See [23].
DZ2 (s) =∞
Xa(m)

m=1ms

= ζQ(i) (s) =Y
11−s1−2(1 − p−s )2p≡1(4)

112
1122
1+ s + s + s + s + s + s + s + ...
2s4589101316∞
Xapr (m)1DZpr2 (s) ==DZ2 (s)smζ(2s)m=1=1+= (1 + 2−s )Y 1 + p−s
1 − p−sp≡1(4)1222222= 1 + s + s + s + s + s + s + s + ...
25101317252694Colourings

Here we consider special colourings of lattices. For a fixed sublattice Γ2 of Γ1 weassign all points of a coset the same colour, with different colours for different
cosets. [28, 29, 30, 9]

4.1

Colour symmetries

symmetry operation leaves lattice and colours fixedcolour symmetry leaves lattice fixed but permutes colors
In our case:• all lattice translations are colour symmetries• there is a bijection between colours and cosets• to each colouring (up to colour
S permutations) there corresponds a uniquecoset decomposition Γ1 = ℓ (cℓ + Γ2 ) and vice versa

4.2

Coincidences and colourings

Idea: use colourings of lattices to find out more about coincidence indices ofsublattices [10, 9]
Let Γ2 a sublattice of Γ1 of index m, and let Σi (R) be the coincidence index
of R with respect to Γi for i ∈ {1, 2}.
Theorem 4.1.

s · v · Σ1 (R)t · u · Σ1 (R)=mm
and s, t, u, v | m. Here s and t are the number of colours in the induced coulouring of Γ1 (R−1 ) and Γ1 (R), respectively. u is the number of colours cj with theproperty that some point of Γ1 (R−1 ) coloured cj is mapped under R onto a point
coloured c0 = 0 in Γ1 (R); v is the number of colours in the colouring of Γ1 (R)that are intersected by the images under R of those points of Γ1 (R−1 ) colouredc0 .
Σ2 (R) =4.3

Colour coincidences

Definition 4.1. We call R a colour coincidence, if one of the following two
equivalent conditions is satisfied
1. colouring of Γ1 (R) is a rotated copy of the colouring of Γ1 (R−1 ) (up tocolour permutations)
2. R leaves colour c0 fixed10

Theorem 4.2. If R is a colour coincidence, then Σ2 (R) divides Σ1 (R).
Open question: Do colour coincidences form a group?
What is known:• R colour coincidence ⇐⇒ R−1 colour coincidence• R, S colour coincidences and Σ1 (R), Σ1 (S) coprime ⇐⇒ RS colour coincidence

5

Shifted lattices

5.1

Coincidence isometries

Here we consider linear isometries of lattices shifted by some vector x ∈ Rd , i.e.
sets x + Γ. One extends all the definitions in the natural way. One gets
Theorem 5.1. OC(x + Γ) = {R ∈ OC(Γ) : Rx − x ∈ Γ + RΓ}• In general, OC(x + Γ) is not a group.
For further details and applications to multilattices and sublattices see [31,9].

5.2

Coincidence isometries of Z[i]Theorem 5.2. Let Γ = Z[i] and x ∈ C.
1. SOC(x + Γ) is a subgroup of SOC(Γ)
2. OC(x + Γ) is a subgroup of OC(Γ) if and only if T1 T2 ∈ SOC(x + Γ)forany T1 , T2 ∈ OC(x + Γ) \ SOC(x + Γ),
Lemma 5.3. Let x =pwhere p, q ∈ Z[i], p and q relatively prime. Thenq
1+ΓSOC(x + Γ) = SOCqLemma 5.4. If p and q are relatively prime, then
111SOC+ Γ = SOC+ Γ ∩ SOC+Γpqpq

11

5.3

Example Z[i]: specific shift vectors (1)1 62x0x11• x0 = 15 , 25 and x1 = 15 + 51 i, 25 + 52 i ⇒ 2q = 5• SOC(x0 + Γ) = SOC(x1 + Γ)
• OC(x0 + Γ) and OC(x1 + Γ) are groups
The generating function Φx (s) of the shifted CSLs reads as follows (thegenerating function Φ(s) of the CSLs of Z[i] is repeated for easier comparison)Φx (s) = 1 + 132s + 172s + 292s + 372s + 412s + 532s + 612s + 732s + . . .
Φ(s) = 1 + 52s + 132s + 172s + 252s + 292s + 372s + 412s + 532s+ 612s + 654s + 732s + . . .
The rotations and the orientation reversing isometries both generate the same
CSLs.

5.4

Example: Z[i]: specific shift vectors (2)1 6212i• x = 52 + 15 i = 1+2i
⇒ q = 1 + 2i• SOC(x + Γ) = SOC 51 + Γ• OC(x + Γ) is NOT a group!

Here rotations and orientation reversing isometries generate different CSLs.
Φx (s) generates the counting function of shifted CSLs that are generated byrotations only, whereas Ψx (s) generates the counting function of all shiftedCSLs. Again, Φ(s) of the unshifted Z[i] is included for comparison.
Φx (s) = 1 + 132s + 172s + 292s + 372s + 412s + 532s + 612s + 732s + . . .
Φ(s) = 1 + 52s + 132s + 172s + 252s + 292s + 372s + 412s + 532s+ 612s + 654s + 732s + . . .
Ψx (s) = 1 + 54s + 132s + 172s + 254s + 292s + 372s + 412s + 532s+ 612s + 658s + 732s + . . .
For further examples see [9].
126Conclusions

There are a lot of connections . . .
• colourings ↔ similar sublattices• similar sublattices ↔ CSLs
• CSLs ↔ colourings

Acknowledgements
This work was supported by the German Research Council (DFG), within the
CRC 701.

References[1] G. Friedel. Leçons de Cristallographie. Blanchard, Paris, 1911.
[2] S. Ranganathan. On the Geometry of Coincidence–Site Lattices. ActaCryst., 21:197–199, 1966.
[3] Walter Bollmann. Crystal Defects and Crystalline Interfaces. Springer,Berlin, 1970.
[4] H. Grimmer, W. Bollmann, and D. H. Warrington. Coincidence-site lattices
and complete pattern-shift lattices in cubic crystals. Acta Cryst., A 30:197–207, 1974.
[5] D. H. Warrington. Coincidence site lattices in quasicrystal tilings. Mat.
Science Forum, 126-128:57–60, 1993.
[6] P. A. B. Pleasants, M. Baake, and J. Roth. Planar coincidences for
N –fold symmetry. J. Math. Phys., 37:1029–1058, 1996. rev. version:
arXiv:math/0511147.
[7] N. J. A. Sloane and B. Beferull-Lozano. Quantizing using lattice intersections. In B. Aronov, S. Basu, J. Pach, and M. Sharir, editors, Discrete and Computational Geometry, pages 799–824, Berlin, 2003. Springer.
math.CO/0207147.
[8] Michael Baake. Solution of the coincidence problem in dimensionsd ≤ 4. In R. V. Moody, editor, The Mathematics of Long-Range
Aperiodic Order, pages 9–44, Dordrecht, 1997. Kluwer. Rev. version:
arXiv:math.MG/0605222.
[9] M. J. Loquias. Coincidences and Colorings of Lattices and Z–modules.
PhD thesis, University of Bielefeld, Bielefeld, Germany, 2010.

13

[10] M. J. Loquias and P. Zeiner. Colourings of lattices and coincidence sitelattices. in press. arXiv:1011.1001v1 [math.MG].
[11] M. Baake, M. Heuer, U. Grimm, and P. Zeiner. Coincidence rotationsof the root lattice A4 . Europ. J. Combinatorics, 29:1808–1819, 2008.
arXiv:0709.1341.
[12] M. Heuer and P. Zeiner. CSLs of the root lattice A4 . J. Phys.: Conf. Ser.,
226:012024, 2010.
[13] M. Heuer. Combinatorial Aspects of Root Lattices and Words. PhD thesis,
The Open University, Milton Keynes, UK, 2010.
[14] Michael Baake and Uwe Grimm. Multiple planar coincidences with N –foldsymmetry. Z. Kristallogr., 221:571–581, 2006. arXiv:math.MG/0511306.
[15] P. Zeiner. Multiple CSLs for the body centered cubic lattice. J. Phys.:Conf. Ser., 30:163–167, 2006. arXiv:math/0605521.
[16] M. Baake and P. Zeiner. Multiple coincidences in dimensions d ≤ 3. Phil.
Mag., 87:2869–2876, 2007.
[17] Michael Baake and Uwe Grimm. Multiple planar coincidences with N –foldsymmetry. Z. Kristallogr., 221:571–581, 2006. arXiv:math.MG/0511306.
[18] Hans Grimmer. The generating function for coincidence site lattices in thecubic system. Acta Cryst., A 40:108–112, 1984.
[19] P. Zeiner. Symmetries of coincidence site lattices of cubic lattices. Z.
Kristallogr., 220:915–925, 2005. arXiv:math/0605525.
[20] Michael Baake, Peter A. B. Pleasants, and Ulf Rehmann. Coincidencesite modules in 3–space. Discr. Comput. Geom., 38:111–138, 2007.
arXiv:math/0609793.
[21] P. Zeiner. Coincidences of hypercubic lattices in 4 dimensions. Z. Kristallogr., 221:105–114, 2006. arXiv:math/0605526.
[22] E. M. Rains J. H. Conway and N. J. A. Sloane. On the existence of similar
sublattices. Can. J. Math., 51:1300–1306, 1999.
[23] Michael Baake and Uwe Grimm. Bravais colourings of planar modules with
N –fold symmetry. Z. Kristallogr., 219:72–80, 2004. math.CO/0301021.
[24] M. Baake, M. Heuer, and R. V. Moody. Similar sublattices of the root
lattice A4 , 2008. arXiv:math/0702448.
[25] M. Baake, R. Scharlau, and P. Zeiner. Similar sublattices of planar lattices.
in press. arXiv:0908.2558v1 [math.MG].
[26] S. Glied and M. Baake. Similarity versus coincidence rotations of lattices.
Z. Krist., 223:770–772, 2008. arXiv:0808.0109.
14

[27] S. Glied. in press.
[28] B. L. van der Waerden and J. J. Burckhardt. Fargbruppen. Z. Krist.,
115:231–234, 1961.
[29] R. L. E. Schwarzenberger. Colour symmetry. Bull. Lond. Math. Soc.,
16:209, 1984.
[30] R.V. Moody and J. Patera. Colourings of quasicrystals. Can. J. Phys.,
72:442, 1994.
[31] M. J. Loquias and P. Zeiner. Coincidence isometries of a shifted squarelattice. J. Phys.: Conf. Ser., 226:012026, 2010. arXiv:1002.0519v1[math.MG].

15