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: + Ver.12 program 3 Sep 2022), or a quicker version CoincidenceSubstFixedLetter.nb (zip file : 12 March 2014: + Ver.12 program 3 Sep 2022).

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 worth trying 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 : + Ver.12 program 3 Sep 2022).

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 J. 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, Discrete Math. Theor. Comput. Sci., vol. 16:3 (2014) 305-316.) 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. Our programs accept real entries of Q and Dij using a fixed field and a common embedding. But in some 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 cases, 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 questions about the program, please contact us (akiyama at math.tsukuba.ac.jp or jylee at kias.re.kr). We are grateful to have your comments and bug reports.

The execution time depends on the paragraph to prepare initial overlaps. It could take a very long time if the tiling is self-affine or the dimension is greater than 2. Most of the examples we computed in [AL] take 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 occurred 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 differently. 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 at the beginning of the old version. I hope this helps solve 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 the wrong direction to some edges. To settle this, you can import the old `Combinatorica' which is somewhere in your hard disk, but better after being renamed.


Q3. My version of Mathematica does not work.

A3. Original programs are designed for Mathematica Version 7 or 8. Problems may occur around the `Combinatorica' package for a newer version. From Version 10 on, this package is already preinstalled and not necessary to add on. However, many functions are renamed, e.g., `InduceSubgraph -> Subgraph' or`TransitiveClosure -> TransitiveClosureGraph' in this inclusion process. Much worse, the function `FromOrderedPairs' had disappeared. Instead, we can use the `Graph' function to construct the overlap graph. Thanks to this change, the overlaps are not necessarily mapped to the set of positive integers. This gives a simpler coding but several corresponding changes are required. You find the new version in the above-zipped files adjusted for Mathematica Ver.12. Other programs may work by replacing the part between (* Construct and draw the graph *) and the final `If[Rd2 < Rd1,...]', by the corresponding part of the Ver.12 program.


To the top