Mathematica programs to compute overlap coincidence

We implemented Mathematica programs to compute overlap coincidence for general self-affine tilings in Rd. Readers can refer to our paper [AL] "Algorithm for determining pure pointedness of self-affine tilings" by S. Akiyama and J.-Y. Lee, Adv. Math. 226 (2011) 2855-2883, for the theoretical justification.

1. For symbolic substitutive systems, you can try:

CoincidenceSubst.nb (zip file : Minor Bug fix 2 Oct 2010), or a quicker version CoincidenceSubstFixedLetter.nb (zip file : 12 March 2014).

These check overlap coincidence of the suspension of symbolic substitutive dynamics, by associating canonical length to each letter. It is easy to use and works for any symbolic primitive substitution whose Perron-Frobenius root is a Pisot number. It covers reducible and/or non-unit Pisot substitutions. If it is not Pisot, then the computation may not terminate. Of course, it is not worthy to try such a case, because the system is known to be weakly mixing.

2. For all self-affine tilings in Rd, you can use:

CoincidenceComputation-revised-II.nb (zip file : corrected 16 June 2010, Minor bug fix 8 Sep 2010.).

3. Socolar-Taylor's tiling is found here:

Algorithm to compute overlap coincidence of Taylor-Socolar tiling (zip file : uploaded May 14 2012),

for details, see "The computation of overlap coincidence in Taylor-Socolar substitution tiling" by S. Akiyama and J.-Y. Lee, Osaka Journal Math, vol. 51 (2014) 597-607.

4. Systematic example computation (c.f. "Determining pure discrete spectrum on some self-affine tilings." by S. Akiyama, F.Gähler and J.-Y. Lee, submitted) is found in:

CoincidenceSubst2Automatic4.nb and CoincidenceKenyon0Automatic.nb (zip file: uploaded 27 Feb 2014, updated 12 March 2014)

To use Program 2, you have to prepare the input data: an expanding matrix Q and digits Dij in the sense of Lagarias-Wang "Substitutive Delone sets" (see (2.2) and (2.5) in [AL]). They must be written in the AlgebraicNumber package form using a common field. Put them in the form of a matrix function system which produces a Delone multi-color set. When your data is an iterated function system (IFS) of a self similar tiling, do not forget to make the transpose of the digit matrix, because we are using the duality between tilings and point sets. The format of the data is understood by the 1-st paragraph of the program. Basically our programs accept real entries of Q and Dij using a fixed field and a common embedding. But in cases, the IFS is written by using complex numbers and/or algebraic conjugates and most of our examples are also in such forms. Taking a decomposition field would make computation heavy. Thus we allow such input using different embeddings by the following rule: If you wish to use complex/algebraic conjugate entries, Q must be diagonal and complex conjugates are located in pairs before real conjugates in the diagonal. Each element of Dij is a vector whose entries are algebraic conjugates (complex conjugates come first in pairs) which correspond to the diagonal entries of Q. As complex data have 2 dimensional information, we essentially use one complex conjugate in the actual computation.

If the data is correct and the point set forms a Meyer set, then the computation should be automatic. Just execute the Mathematica paragraphs one by one. It returns the output whether the tiling dynamical system has pure point dynamical spectrum (overlap coincidence) or not.

If the data is incorrect, you usually get warnings on the way or immediately notice by having strange pictures of tilings. In unlucky case, without any warning you obtain a surprising result, e.g., the boundary of a d-dim tile is less than d-1! We guess in this case, your digits are not distinct and the point set does not form a Delone set. Better to check this point. If you have any question on the program, please contact us (akiyama at or jylee at We are grateful to have your comments and bug-reports.

The execution time depends on the paragraph to prepare initial overlaps. It could take very long time if the tiling is self-affine or the dimension is greater than 2. Most of examples we computed in the preprint [AL] takes less than a few minutes in computation, except the fractal Penrose tiling (Ex. 5.8), Kenyon-Solomyak tiling (Ex. 5.4) and Pisot dual tiling (Ex. 5.6(2)). They take not more than a day, but you have to be patient.

Q1. An error occured in AlgebraicNumber[...].

A1. This is a version conflict. We used Mathematica version 7 or 8 to implement the program. Some older version expresses algebraic number in a different way. For e.g. AlgebraicNumber[Root[#^4-#-1&,3],{0,1}] was Algebraic[#^4-#-1&,{0,1},3]. Also you have to explicitly add-on the package AlgebraicNumberFields in the beginning in the old version. I hope this helps solving serious problems. The best is to consult someone who knows well Mathematica.

Q2. 'Lagarias Wang condition does not hold' or `Substitution rule: Not irreducible' by our examples.

A2. We found this in some early versions of Mathematica 7. This seems to be a bug of 'FromAdjacencyMatrix' under `Type -> Directed', giving wrong direction to some edges. To settle this, you can import the old `Combinatorica' which is somewhere in your hard disk, but better after renamed.

To the top