Growth functions of periodic space tessellations

Naskręcki, B.; Malinowski, J.; Dauter, Z.; Jaskolski, M.

doi:10.1107/S2053273324010763

research papers

FOUNDATIONS
ADVANCES

ISSN: 2053-2733

Volume 81| Part 1| January 2025|

https://doi.org/10.1107/S2053273324010763

Open

access

Growth functions of periodic space tessellations

Bartosz Naskręcki,^a,^b ^* Jakub Malinowski,^c ^* Zbigniew Dauter ^d and Mariusz Jaskolski ^e,^f

^aFaculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań, Poland, ^bMathematical Institute, Polish Academy of Sciences, Warszawa, Poland, ^cFaculty of Pure and Applied Mathematics, Wrocław University of Science and Technology, Wrocław, Poland, ^dMacromolecular Crystallography Laboratory, NCI, Argonne National Laboratory, Argonne, USA, ^eDepartment of Crystallography, Faculty of Chemistry, Adam Mickiewicz University, Poznań, Poland, and ^fInstitute of Bioorganic Chemistry, Polish Academy of Sciences, Poznań, Poland
^*Correspondence e-mail: bartnas@amu.edu.pl, jakub.malinowski@pwr.edu.pl

Edited by A. Altomare, Institute of Crystallography - CNR, Bari, Italy (Received 9 November 2022; accepted 6 November 2024)

This work analyzes the rules governing the growth of the numbers of vertices, edges and faces in all possible periodic tessellations of the 2D Euclidean space, and encodes those rules in several types of polynomial growth functions. These encodings map the geometric, combinatorial and topological properties of the tessellations into sets of integer coefficients. Several general statements about these encodings are given with rigorous mathematical proof. The variation of the growth functions is represented graphically and analyzed in orphic diagrams, so named because of their similarity to orphic art. Several examples of 3D space groups are included, to emphasize the complexity of the growth functions in higher dimensions. A freely available Python library is presented to facilitate the discovery of the growth functions and the generation of orphic diagrams.

Keywords: tiling of the plane; tessellations; modified Euler characteristic; orphic diagrams; topological growth functions; crystallographic growth functions.

1. Introduction

Our focus in this paper is on periodic tessellations of space. In 2D there are 11 possible, topologically distinct, periodic tilings by congruent polygons, also known as Laves tilings (see Appendix A, where some terms are explained in the glossary). These tilings are designated by listing the numbers of edges that meet at each of the vertices (the number of edges meeting at a vertex is called its valence) of the tile (cf. Fig. 1). For example, 4444 denotes a grid created by two sets of parallel lines. The unit cell of such a grid is a parallelogram. In the familiar case of crystallographic tessellation, the space is covered by a periodic (lattice) arrangement of identical unit cells. The unit cells are in turn subdivided, according to space-group symmetry, into asymmetric units (ASUs), which can be selected in many ways, but cannot be subdivided further without loss of symmetry. We start from a lattice node in $[{\bb R}^{3}]$ and expand our frame of coverage, which is congruent to the crystallographic unit cell, and count the number of interiors (I) covered. That number grows in a cubic fashion, as do the counts of other geometrical elements, such as vertices (V), edges (E) and faces (F). In the general Euclidean space $[{\bb R}^{N}]$ , the same polynomial type of count holds for any k-dimensional cell (Appendix A) for k between 0 and N. In the case of $[{\bb R}^{2}]$ , the polynomials are quadratic functions. But what exactly are these functions? Do they depend on the choice of the origin, or the choice of ASU, or on the frame that we expand to cover a growing area of the lattice? Are there rules governing their form? These and other questions were at the root of our interest in the subject of growth functions. In our previous work (Dauter & Jaskolski, 2020 ; Naskręcki et al., 2021a , 2021b , 2022 ) we investigated the general asymptotic behavior of the growth functions. In the current paper we present, with proof, the exact formulas for the polynomial growth functions of the permitted periodic tessellations in the $[{\bb R}^{2}]$ space.

Figure 1
Eleven topologically distinct types of planar tilings in their most symmetric representation. Each type is characterized by the vertex valences and by the space-group symmetry (in parentheses). 4444 (p4mm), 333333 (p6mm), 666 (p6mm), 884 (p4mm), 44333 (c2mm), 43433 (p4gm), 6363 (p6mm), 6434 (p6mm), 1264 (p6mm), 12123 (p6mm), 63333 (p6).

We also probe the possibility of using the growth functions to expose the underlying lattice when its regularity is distorted by, e.g., lattice defects; that particular application of the growth functions might be of practical utility (cf. Section 7.2). Finally, we remark that a similar problem of tessellating the $[{\bb R}^{3}]$ space by parallelohedra would be dramatically more complicated.

2. Panorama of the ideas

To aid the readers in navigation through the text, we describe in this section the main ideas of our work and illustrate their flow in the paper in Fig. 2.

Figure 2
Flow of ideas throughout the paper.

Topology. Our point of departure is an idea from topology to treat the process of tessellating the space $[{\bb R}^{N}]$ as one in which we start from a single point (0-cell or vertex) and attach to it certain N-dimensional cells. The collection of cells (with the information about how the edges, faces etc. are connected) will constitute a fundamental topological structure of our objects. Our principal requirement is that these N-cells, taken together, must satisfy the property that under shifts in space (by integral multiples of N linearly independent vectors) they give an exhaustive tessellation of the space, or the so-called periodic tessellation.

Combinatorics. Our major goal is to encode topological and combinatorial data in the form of functions that count, for a fixed k, the number of k-cells of the tessellation within the bounded number of copies of the fundamental region (Appendix A). We will discuss in detail two very different approaches to this counting procedure. One, which we call topological, relies only on the combinatorial data, i.e. the count of connected cells etc. The other way, which we call crystallographic, will count the cells with respect to their position in a growing parallelepiped rooted in various points. The crystallographic version is very sensitive to shifts, hence we encode those functions in the form of a color diagram, called an orphic diagram (Appendix A).

Symmetry. A major reason to look at the above two variants is that the former one is `crude', i.e. it is insensitive to the change of the symmetry group of a tessellation when the topological type is preserved. For a simple example think about a tiling of the plane by squares and a tiling by general parallelograms. Topologically they are identical but they differ at a subtler level of geometric deformations.

Tilings. We build a complete set of formulas for the topological growth functions of 2D tilings. This idea is then enhanced by using a certain modification of the topological growth function construction. We change our counting procedure by making a reference to the expanding unit cell. These so-called crystallographic growth functions can be visualized by color diagrams.

The classification of the possible topological growth functions is important for the more refined crystallographic approach. Many properties of these functions are shared but, as we illustrate in several examples, the crystallographic growth functions have the potential to completely encode the symmetry group, i.e. two isometric tessellations will have similar growth function diagrams.

Feature detection. We discuss certain simple applications of this encoding of the properties of the tilings and are laying the ground for space-group symmetry recognition in future projects.

Higher dimensions. Finally, we discuss the prospects of generalizing our results to higher dimensions. Serious obstacles arise both conceptually and practically. In principle, the tools that we have developed are easy to apply to any particular tessellation in higher dimension but building a conceptual description of the growth functions in higher dimensions is more challenging.

3. Tessellations

We denote by $[{\bb R}]$ the set of real numbers and by $[{\bb Z}]$ the set of integers contained in $[{\bb R}]$ . Let $[{\bb R}^{N}]$ denote the N-dimensional Euclidean space, i.e. the set of N-tuples (Appendix A) $[(x_{1},\ldots,x_{N})]$ of real numbers x_i. Let $[{\bb Z}^{N}]$ denote the set of N-tuples $[(x_{1},\ldots,x_{N})]$ of integers x_i. By construction, the set $[{\bb Z}^{N}]$ is properly contained in $[{\bb R}^{N}]$ . (Notice that the set of integers $[{\bb Z}]$ is countable, while the set of real numbers $[{\bb R}]$ is uncountable.)

In this paper we deal with the notion of a tessellation of the Euclidean space. We discuss in this section the necessary mathematical preliminaries from geometry, topology and combinatorics that will be used throughout the paper. The different notions of equivalence between tessellations are explained by Grünbaum & Shephard (1987 , Sections 1.3, 4.1).

3.1. Normal tessellations

In this paper we work with the so-called normal tessellations in the sense of Grünbaum & Shephard (1987, Section, 3.2). This definition can be applied to tessellations in an arbitrary number of dimension of the Euclidean space $[{\bb R}^{N}]$ . In the sense given above, a tessellation is a countable family of closed sets $[\{T_{1},T_{2},\ldots\}]$ which cover the space without `gaps' or `overlaps'. The lack of gaps means that the union $[\cup_{i}T_{i}]$ of the covering sets gives us $[{\bb R}^{N}]$ . The lack of overlaps means that the interiors of T_i and T_j for any $[i\neq j]$ do not overlap, i.e. the sets T_i, T_j can meet only on the boundary (cf. Grünbaum & Shephard, 1987, Section 1.1). The tessellation is normal if:

(i) Every set T_i is a topological N-dimensional ball, i.e. up to bi-continuous bijection (homeomorphism) every set T_i is an N-dimensional ball.

(ii) The intersection of every two sets T_i, T_j is a connected set.

(iii) The sets T_i are uniformly bounded, i.e. there exist two radii r and R such that every set T_i contains a ball of radius r and is contained in a ball of radius R.

Conditions (i)–(iii) represent for us the most interesting and easy to understand ways of tessellating a space. In particular, all regular tessellations, e.g. the crystallographic ones, are contained in this class. Notice also that it follows from (i) and (ii) that the intersection of every two different T_i,T_j consists of a single `part'. Conditions (i)–(iii) imply that the tessellation of space with T_i `grows' moderately (Grünbaum & Shephard, 1987, Section 3.2).

3.2. Periodic tessellations

Our focus in this paper is exclusively on periodic normal tessellations.

Let $[X+v = \{x+v:x\in X\}]$ be a shift of the set $[X\subset{\bb R}^{N}]$ by a vector v. We denote by $[S_{\bf n}^{u}(X) = X+\sum_{i = 1}^{N}n_{i}u_{i}]$ a shift of X by the linear combination of vectors from $[u = \{u_{i}\}_{i = 1}^{N}]$ indexed by $[{\bf n} = (n_{1},\ldots n_{N})]$ .

Definition 3.1

We say that a normal tessellation $[{\cal T}]$ (of $[{\bb R}^{N}]$ ) is periodic if there exists a covering family {T_j} and N linearly independent vectors $[\{u_{i}\}_{i = 1}^{N}]$ such that, for any T_k, T_l there exists an N-tuple of integers $[{\bf n} = (n_{1},\ldots n_{N})]$ for which

$[T_{k} = S^{u}_{{\bf n}}(T_{l})]$

holds. Since all sets T_i are equivalent by integral shifts, we fix one of them, say T₁, and denote it Ω. We call Ω a generating region of $[{\cal T}]$ .

For every two distinct vectors $[{\bf n}\neq{\bf m}]$ , the shifts $[S^{u}_{\bf n}(\Omega)]$ , $[S^{u}_{\bf m}(\Omega)]$ overlap possibly on the boundaries. We denote by $[{\cal T}_{\bf n}]$ a CW complex (Appendix A) which is the union of CW complexes $[S^{u}_{\bf m}(\Omega)]$ where $[-{\bf n}\leq {\bf m}\leq {\bf n}]$ . Every complex $[{\cal T}_{\bf n}]$ is finite and satisfies $[{\cal T}_{\bf n}\subset{\cal T}_{{\bf n}^{\prime}}]$ for every $[{\bf n}\leq {\bf n}^{\prime}]$ (the inequality relation is lexicographic). We call the family $[\{{\cal T}_{\bf n}\}]$ indexed by N-tuples $[{\bf n}]$ a stratification of $[{\cal T}]$ .

Remark. A periodic tessellation can be constructed with a set Ω that is not necessarily a polygon (curvy edges). This would be rather unusual in crystallography but can be applied, for example, to the tilings of M. C. Escher etc.

3.3. CW structure

Tessellation in this paper is considered as a topological object, i.e. a CW complex (Appendix A). We refer the reader to our mathematical glossary for a fuller description. Also, more details about CW complexes can be found in standard textbooks (Whitehead, 1949 ; Hatcher, 2002 ). In brief, a CW complex is a topological space with extra data about how it was obtained from gluing simple pieces which are called cells. Every cell is topologically a ball of appropriate dimension. A tessellation of the space $[{\bb R}^{N}]$ is obtained by gluing together k-dimensional cells of dimensions ranging between 0 and N.

We start from a simple example. Consider a closed interval [0,1] on the real line $[{\bb R}^1]$ . The CW structure on [0,1] can be determined by the following procedure. We have two 0-dimensional cells, i.e. the vertices 0 and 1. We connect them by (glue to them) a closed interval [0,1], where the end point 0 of the interval matches vertex 0 and the end point 1 matches vertex 1. There are no other cells in this CW structure. The sets of k-dimensional cells will be denoted $[{\cal C}_{k}]$ .

In particular, for a tessellation in 2D, which we call a tiling, we write $[{\cal V} = {\cal C}_{0}]$ for the set of vertices, $[{\cal E} = {\cal C}_{1}]$ for the set of edges and $[{\cal F} = {\cal C}_{2}]$ for the set of faces. The sets T_i in this context are called tiles.

Example 3.2

Addition of the connectivity structure (CW structure) of a tessellation allows one to define objects such as paths and count properly the objects in the tessellation (such as faces or edges) that are similar. Consider the real line $[{\bb R}^{1}]$ as a union of closed intervals $[T_{i} = [i,i+1]]$ for $[i\in{\bb Z}]$ . The vertices which connect the segments T_i are the integers $[i = 0,1,-1,2,-2,\ldots]$ . Notice that the endpoints of the intervals T_i overlap between neighboring segments. The edges are represented by the segments T_i. Every point on the real line is contained either in a single segment (interior of the edge) or belongs to finitely many (in this case exactly two) segments; these are the points from the vertex set.

3.4. Vertex notation

Any monohedral tiling (i.e. having exactly one prototile, where a prototile in a tiling is a face which has no sub-faces) with tiles whose vertices (ordered cyclically) have valences (i.e. numbers of meeting edges) $[d_{1},\ldots,d_{n}]$ will be denoted $[d_{1}d_{2}\ldots d_{n}]$ . In our limited context, the numbers d_i belong to the set {3,4,6,8,12}, hence no confusion arises when we write a sequence like 12123, which stands for $[d_{1} = 12]$ , $[d_{2} = 12]$ and $[d_{3} = 3]$ . This is a simplified version of the notation introduced by Grunbaum & Shepherd (1987, Section 2.7).

4. Growth functions

In this section we introduce a certain topological and geometric tool that will be used to study tessellations, the growth functions. One can define such functions in various ways, depending on the context.

The growth functions that we introduce in this paper fit into a more general framework of mathematical objects that can be attached to tessellations. Our main motivation came from our previous work, where we investigated a variant of the classical Euler characteristic (Appendix A), which could be adopted for the notion of crystallographic tessellations. The connection makes use of the orbifold (Appendix A) variants of the Betti numbers used in topology to describe the number of `holes' in the topological space. In fact, the Betti numbers are in correspondence with the leading coefficients of our topological growth functions, provided that the structure of the associated orbifold is simple (Naskręcki et al., 2021a).

For general tilings, previous authors studied the combinatorics (counting the objects) of the tessellations using various tools like graphs and generating functions. The latter are especially suited and useful for studying tessellations which are non-periodic because in these situations a finite sequence of numbers cannot in general determine the structure of such tessellations. [Compare this with the famous Penrose tilings. The ways in which one can build such a tiling can be identified with the whole uncountable set of real numbers. This means that a finite amount of data is usually not enough to characterize such tilings (Senechal, 1995 , Section 6.2).]

We also notice some similarity with the work of Grosse-Kunstleve et al. (1996 ) on coordination sequences for zeolites. These authors build certain growth functions associated with zeolites and study their properties. In their approach the counting is done by introducing a shelling of the tiling.

4.1. Topological/combinatorial approach

Definition 4.1

(Topological growth function) For a normal periodic tessellation $[{\cal T}]$ of $[{\bb R}^{N}]$ with generating region Ω and with the finite stratification $[{\cal T}_{\bf n}]$ of the Euclidean space $[{\bb R}^{N}]$ we define for every integer k in the range between 0 and N a function $[f_{k}^{\rm top}(\Omega\semi {\bf n})]$ where $[{\bf n} = (n_{1},\ldots,n_{N})]$ is a coordinate vector of non-negative integers. The function $[f_{k}^{\rm top}(\Omega\semi {\bf n})]$ counts the number of k-cells in the finite CW complex $[{\cal T}_{\bf n}]$ .

It follows from Naskręcki et al. (2021a) that the functions $[f_{k}^{\rm top}(\Omega\semi {\bf n})]$ are polynomials of total degree N with integer coefficients.

For our particular Example 3.2, starting from any vertex (integer) m we obtain functions $[f_{0}^{\rm top}(\Omega\semi n) = 2n+1]$ and $[f_{1}^{\rm top}(\Omega\semi n) = 2n]$ , where $[\Omega = [0,1]]$ .

Example 4.2

Tiling 4444 – a mathematical perspective. The plane $[{\bb R}^{2}]$ can be given a CW structure by considering a union of unit squares (with boundary) which tiles the space. This CW structure has the following description:

( $[{\cal V}]$ ) The set of vertices is the set of pairs (x,y) with integer coordinates x,y, i.e. $[{\cal V} = \{(x,y)\in{\bb R}^{2}:x,y\in{\bb Z}\}]$ .

( $[{\cal E}]$ ) Edges are segments $[\overline{AB}]$ of length 1 [or ordered tuples (A,B)] which span the space between two distinct points $[A,B\in{\cal V}]$ , i.e. $[{\cal E} = \{(A,B):A,B\in{\cal V},A\neq B]$ }.

( $[{\cal F}]$ ) Faces are unit squares with vertices in the set $[{\cal V}]$ . One can identify such a face with an ordered tuple (A,B,C,D) of elements $[A,B,C,D\in{\cal V}]$ . Let U denote the quadruple ((0,0),(1,0),(1,1),(0,1)). Under a suitable translation vector $[u = [u_{1},u_{2}]]$ with integer coordinates every face (A,B,C,D) satisfies

Hence we define the set of quadruples $[{\cal F}]$ = $[\{(A,B,C,D):\exists_{u\in{\bb Z}^{2}}\ (u(A),u(B),u(C),u(D)) = U\}]$ .

For every face $[f\in{\cal F}]$ we define the geometric square, i.e. a subset of $[{\bb R}^{2}]$ which corresponds to f. The totality of such squares provides a tiling $[{\cal T}]$ of the space $[{\bb R}^{2}]$ with a generating region $[\Omega = [0,1]^{2}]$ .

For every vertex v and fixed k, the functions $[f_{k}^{\rm top}(\Omega\semi (n_{1},n_{2}))]$ are the same. In fact

$[f_{0}^{\rm top}(\Omega\semi (n_{1},n_{2})) = (2n_{1}+1)(2n_{2}+1),]$

$[f_{1}^{\rm top}(\Omega\semi (n_{1},n_{2})) = 8n_{1}n_{2}+2n_{1}+2n_{2},]$

$[f_{2}^{\rm top}(\Omega\semi (n_{1},n_{2})) = (2n_{1})(2n_{2}),]$

where n₁, n₂ are the number of positive and negative steps in both directions of the $[{\bb R}^{2}]$ space.

Note. In the following (except Section 5), each time we write a growth function we apply a standard normalization, i.e. instead of growth in each direction we only consider the growth in the `positive' directions. Hence the normalized forms of the latter functions would be (n₁+1)(n₂+1), 2n₁n₂+n₁+n₂ and n₁n₂, respectively.

4.2. Crystallographic approach

In our considerations we limit ourselves to the choice where the index set is the set of non-negative integers and we measure the growth of the tessellation $[{\cal T}]$ against the propagation of the unit cell, which is a parallelogram (or in general an N-parallelepiped), with a fixed starting point.

For a periodic tessellation with generating period vectors $[u = \{u_{i}\}]$ , we define an N-parallelepiped $[{\cal P}]$ = $[\{\sum_{i = 1}^{N}x_{i}u_{i}:0\leq x_{i}\leq 1\}]$ spanned by the vectors in u. Now, we have a family of growth functions (indexed by dimension k and starting point v₀) which for a given non-negative integer vector $[{\bf n}]$ count the number of k-cells of $[{\cal T}]$ which are completely contained in the set $[\{v_{0}+\sum_{i}x_{i}u_{i}:|x_{i}|\leq n_{i}\}]$ . We call such functions `crystallographic' growth functions, to distinguish them from the previously defined (for not necessarily periodic tessellations) more `topological' growth functions.

Let us formalize now the notion of crystallographic growth functions.

Definition 4.3

(Crystallographic growth function) Let $[{\cal T}]$ be a periodic normal tessellation of $[{\bb R}^{N}]$ with generating region Ω and translation vectors $[u = \{u_{i}\}_{i = 1}^{N}]$ . Let $[{\cal P}]$ denote the parallelepiped spanned by u.

We denote by $[f_{i}^{\rm crys}(\Omega,u\semi x_{0},{\bf n})]$ the number of i-dimensional cells of the tessellation $[{\cal T}]$ which are completely contained in the region $[x_{0}+\cup_{-{\bf n}\leq{\bf m}\leq{\bf n}}S^{u}_{{\bf m}}({\cal P})]$ . Similarly, we define $[f_{i}^{{\rm crys},+}(\Omega,u\semi x_{0},{\bf n})]$ as the function which counts the i-dimensional cells in $[x_{0}+\cup_{0\leq{\bf m}\leq{\bf n}}S^{u}_{{\bf m}}({\cal P})]$ .

We denote by $[f^{\rm crys}(\sigma,u\semi x_{0},{\bf n})]$ the number of u translates of the cell $[\sigma\in\Omega]$ of the tessellation $[{\cal T}]$ which are completely contained in the region $[x_{0}+\cup_{-{\bf n}\leq{\bf m}\leq{\bf n}}S^{u}_{{\bf m}}({\cal P})]$ . Similarly, we define $[f^{{\rm crys},+}(\sigma,u\semi x_{0},{\bf n})]$ as the function which counts the translate of σ in $[x_{0}+\cup_{0\leq{\bf m}\leq{\bf n}}S^{u}_{{\bf m}}({\cal P})]$ .

The crystallographic growth functions have a more interesting behavior, in particular they are sensitive to the choice of the starting point x₀ in $[{\bb R}^{N}]$ . Their behavior in 2D is discussed in detail in Section 6.

4.3. Mantissa equations

We show in this section that the crystallographic functions are the same in certain `small' regions. More precisely, there exists a tessellation of $[{\bb R}^{N}]$ with the rescaled version of the parallelepiped $[{\cal P}]$ spanned by the period vectors u. Starting from a point v₀ we attach to it a scaled parallelepiped $[{\cal P}]$ and proceed accordingly further. The choice of scalings arises from the following simple observation.

Let $[x_{0}\in\Omega]$ be a point and let $[x_{0}+\sum_{i}k_{i}u_{i}]$ be a shifted point, where $[k_{i}\in{\bb Z}]$ . The parallelepiped $[{\cal P}]$ generates via the periodic translations a tessellation. It follows that

$[x_{0}+\sum_{i}k_{i}u_{i} = v_{0}+\sum_{i}(l_{i}+\alpha_{i})u_{i},]$

where $[0\leq\alpha_{i}\,\lt\,1]$ , $[l_{i}\in{\bb Z}]$ . Hence, we have

$[M^{-1}(x_{0}-v_{0}) = ((l_{i}+\alpha_{i}-k_{i}))^{\rm T},]$

where M is a matrix $[[u_{1}^{\rm T}|\ldots|u_{n}^{\rm T}]]$ formed from the vectors in the set u. It is invertible since $[{\cal P}]$ has non-zero volume. We let ω denote the vector $[M^{-1}(x_{0}-v_{0})]$ with elements $[\omega_{i}]$ . Let $[\lfloor x\rfloor]$ denote the integer $[\max\{m\in{\bb Z}:m\leq x\}]$ . Since $[0\leq\alpha_{i}\,\lt\,1]$ , it follows that for each i we have the following mantissa equations:

$[l_{i} = \lfloor k_{i}+\omega_{i}\rfloor.]$

The region in $[{\bb R}^{N}]$ for which $[\lfloor k_{i}+\omega_{i}\rfloor]$ is fixed is a parallelepiped. This condition determines for which values v₀ a growth function change (`jump') occurs (cf. Section 6).

We can summarize the properties of the crystallographic growth functions in the following.

Lemma 4.4

Let $[{\cal T}]$ be a normal periodic tessellation of $[{\bb R}^{N}]$ with generating region Ω and translation vectors u, spanning the parallelepiped $[{\cal P}]$ . The following hold:

(i) For any two points $[x_{0},x_{1}\in{\bb R}^{N}]$ such that $[x_{0}-x_{1}]$ is an integral linear combination of the vectors in u, the N-tuple of functions $[(f_{i}^{\rm crys}(\Omega,u\semi v,{\bf n}))_{i = 1}^{N}]$ is the same for $[v = x_{0},x_{1}]$ .

(ii) For any $[x_{0}\in{\bb R}^{N}]$ and any i, the function $[f_{i}^{\rm crys}(\Omega,u\semi x_{0},{\bf n})]$ is for a sufficiently large $[{\bf n}]$ a polynomial in variables $[{\bf n}]$ of total degree N with integer coefficients.

Proof

Property (i) follows from the mantissa equations discussed above. Proof of (ii) follows from the analogous calculations for the topological growth functions (cf. Naskręcki et al., 2021a).

□

Now we want to prove that the set

$[\{(f_{i}^{\rm crys}(\Omega,u\semi x_{0},{\bf n}))_{i = 0}^{N}:x_{0}\in{\bb R}^{N}\}]$

of vectors of crystallographic functions is finite. We decompose each function $[f_{i}^{\rm crys}(\Omega,u\semi x_{0},{\bf n}))]$ into a sum of constituents which count only the number of appearances of a single cell. We will show that for each cell the growth functions are particularly simple and explicit.

Let $[{\cal P}]$ be a parallelepiped generated by the vectors $[u = \{u_{i}\}_{i = 1}^{N}]$ . Let $[{\bf b} = (b_{1},\ldots,b_{N})]$ be a vector of any real numbers, including zero. Let $[\widetilde{{\cal P}}_{{\bf b}}]$ denote the set of vectors $[\{\sum_{i = 1}^{N}b_{i}\cdot x_{i}\cdot u_{i}:0\leq x_{i}\leq 1\}]$ . We call $[\widetilde{{\cal P}}_{{\bf b}}]$ a dilate of $[{\cal P}]$ .

We prove below that we have a periodic normal tessellation of $[{\bb R}^{N}]$ with dilates of $[{\cal P}]$ such that on every interior of any k-dimensional cell the N-tuple of crystallographic growth functions remains fixed.

Definition 4.5

We call a periodic normal tessellation $[{\cal T}]$ with translation vectors u a u tessellation if all cells are parallelepipeds generated by $[\{c_{i}u_{i}\}_{i = 1}^{N}]$ for some non-negative numbers c_i.

For any cell $[\sigma\subset{\bb R}^{N}]$ , we define:

$[\max_{i}(\sigma)]$ = $[\max\{y_{i}:(y_{1},\ldots,y_{N})\in\sigma\}]$ ,

$[\min_{i}(\sigma)]$ = $[\min\{y_{i}:(y_{1},\ldots,y_{N})\in\sigma\}]$ .

Here, y_i denotes the ith coordinate of the point $[(y_{1},\ldots,y_{N})\in\sigma\subset{\bb R}^{N}]$ . In other words, we are taking the maximum or minimum value of the ith coordinate across all points within the cell σ.

Definition 4.6

Let $[{\cal T}]$ be a periodic normal tessellation with generating region Ω and translation vectors u, and spanning the parallelepiped $[{\cal P}]$ . Let $[x_{0} = (x_{0}^{1},\ldots,x_{0}^{N})\in{\bb R}^{N}]$ be fixed. We say that a cell $[\sigma\in{\cal T}]$ appears after $[{\bf n}]$ = $[(n_{1},\ldots,n_{N})\geq(-1,\ldots,-1)]$ extensions with respect to x₀ if for $[{\bf n}_{0} = (\max(n_{i},0))_{i}]$ :

(i) $[\sigma\subset\cup_{0\leq{\bf m}\leq{\bf n}_{0}}S^{u}_{{\bf m}}({\cal P})]$ and $[\sigma\not\subset\cup_{0\leq{\bf m}\leq{\bf n}^{\prime}}S^{u}_{ {\bf m}}({\cal P})]$ for any $[{\bf n}^{\prime}\,\lt\,{\bf n}_{0}]$ ;

(ii) We have $[\min_{i}(\sigma) = \max_{i}(\sigma) = x_{0}^{i}]$ exactly for those i where $[n_{i} = -1]$ .

We say that $[{\bf n}]$ is the order of appearance of σ with respect to x₀.

Lemma 4.7

Let $[{\cal T}]$ be a periodic normal tessellation with generating region Ω and translation vectors u. Let $[x_{0}\in{\bb R}^{N}]$ be fixed. Let σ be a cell in Ω. Let $[n = (n_{1},\ldots,n_{N})]$ be the order of appearance of σ with respect to x₀. It follows that for $[{\bf m}\geq 0]$ we have

$[f^{{\rm crys},+}(\sigma,u\semi x_{0},{\bf m}) = \left\{\matrix{\prod_{i = 1}^{N }(m_{i}-n_{i}),&{\rm if }\ {\bf m}\geq{\bf n},\cr 0,\hfill&{\rm otherwise.}}\right.]$

Proof

We note that for two subsets $[A,B\subset{\bb R}^{N}]$ any linear transformation $[T:{\bb R}^{N}\rightarrow{\bb R}^{N}]$ that transforms the basis u into an orthonormal basis $[e = \{e_{1} = (1,0,\ldots)]$ , $[e_{2} = (0,1,0,\ldots),\ldots]$ , $[e_{N} = (0,\ldots,0,1)\}]$ satisfies the property $[A\subset B\Longrightarrow T(A)\subset T(B)]$ . The definition of $[f^{{\rm crys},+}(\sigma,u\semi x_{0},{\bf m})]$ is based purely on inclusions of sets, hence we can assume without loss of generality that . Let us denote in this proof the function $[f^{{\rm crys},+}(\sigma,u\semi x_{0},{\bf m})]$ by $[I_{\sigma}({\bf m})]$ . We will first prove that

$[I_{\sigma}({\bf m})\geq\prod_{i = 1}^{N}(m_{i}-n_{i}).]$

Let $[{\cal P}({\bf m})]$ be the parallelepiped $[\widetilde{{\cal P}}_{{\bf m}+(1,\ldots,1)}]$ . Let $[\sigma^{\prime}]$ be a certain u-integral translate of σ appearing after $[{\bf n} = (n_{1},n_{2},\ldots,n_{N})]$ extensions. We assume that $[{\bf n}]$ is coordinatewise minimal. Let $[\alpha_{1},\ldots,\alpha_{N}]$ and $[\beta_{1},\ldots,\beta_{N}]$ be natural numbers such that for all i we have inequalities $[\,0\leq\alpha_{i},\beta_{i}\,\lt\,m_{i}-n_{i}]$ . It follows that $[\sigma^{\prime}+\sum_{i = 1}^{k}\alpha_{i}u_{i}\subset{\cal P}({\bf m})]$ and $[\sigma^{\prime}+\sum_{i = 1}^{k}\beta_{i}u_{i}\subset{\cal P}({\bf m})]$ but if for any i we have $[\alpha_{i}\neq\beta_{i}]$ , then $[\sigma^{\prime}+\sum_{i = 1}^{N}\alpha_{i}u_{i}\neq\sigma^{\prime}+\sum_{i = 1}^{N }\beta_{i}u_{i}]$ . So the following inequality holds true:

$[I_{\sigma}({\bf m})\geq\prod_{i = 1}^{N}(m_{i}-n_{i}).]$

We will now demonstrate the inequality in the other direction. Without loss of generality, we can assume that x₀ is at the origin of the coordinate system. To prove the inequality by contradiction, let us suppose that $[I_{\sigma}({\bf m})\,\gt\,\prod_{i = 1}^{N}(m_{i}-n_{i})]$ . From this assumption, it follows that there exists a cell $[\sigma^{\prime\prime}]$ which is a u-integral translate of σ and is contained in $[{\cal P}(m)]$ such that if for all i we have $[0\leq\alpha_{i}\,\lt\,m_{i}-n_{i}]$ , then

$[\sigma^{\prime\prime}\neq\sigma^{\prime}+\sum_{i = 1}^{N}\alpha_{i}u_{i}.]$

On the other hand, $[\sigma^{\prime\prime} = \sigma^{\prime}+\sum_{i = 1}^{N}\alpha_{i}u_{i}]$ for some integral vector $[(\alpha_{1},\alpha_{2},\ldots,\alpha_{N})]$ . Hence, there exists i such that $[0\,\gt\,\alpha_{i}]$ or $[\alpha_{i}\geq m_{i}-n_{i}]$ .

Case: $[0\,\gt\,\alpha_{i}]$ . If $[0\,\gt\,\alpha_{i}]$ , then the ith coordinates of vertices of $[\sigma^{\prime}]$ are bigger than $[-\alpha_{i}]$ . So $[\sigma^{\prime\prime}]$ is contained in $[\widetilde{{\cal P}}_{(n_{1},n_{2},\ldots,n_{i}+\alpha_{i},\ldots,n_{N})}]$ . Note that $[n_{i}+\alpha_{i}\,\lt\,n_{i}]$ . So the cell σ appears inside the frame after $[(n_{1},n_{2},\ldots,n_{i}+\alpha_{i},\ldots,n_{N})]$ extensions, a contradiction with the assumption.

Case: $[\alpha_{i}\geq m_{i}-n_{i}]$ . If $[\alpha_{i}\geq m_{i}-n_{i}]$ , then the ith coordinates of vertices of $[\sigma^{\prime}]$ are less than or equal to $[m_{i}-\alpha_{i}]$ , which is not larger than n_i. Thus, the cell σ appears already after $[(n_{1},n_{2},\ldots,n_{i}-1,\ldots,n_{N})]$ extensions of the frame, a contradiction with our assumption.

□

Now we want to compute a formula for the order of appearance of any cell σ with respect to x₀, $[{\bf n}^{\sigma}(x_{0})]$ . For every $[1\leq i\leq N]$ , let $[n^{\sigma}_{i}(x_{0})]$ denote the ith coordinate of the vector $[{\bf n}^{\sigma}(x_{0})]$ .

For any set A, we denote by $[{\bf 1}_{A}(x)]$ the function that is equal to 1 for all $[x\in A]$ and 0 otherwise. We denote by $[\lfloor x\rfloor]$ the number $[\max\{m\in{\bb Z}\mid m\leq x\}]$ and by {x} the number $[x-\lfloor x\rfloor]$ .

Lemma 4.8

Let $[{\cal T}]$ be a periodic normal tessellation with generating region Ω and translation vectors $[u = e = \{e_{1}]$ = $[(1,0,\ldots),e_{2} = (0,1,0,\ldots),\ldots,e_{N} = (0,\ldots,0,1)\}]$ . Let $[x = (x_{1},\ldots,x_{N})\in[0,1)^{N}]$ be fixed. Let σ be a cell in Ω. For every $[1\leq i\leq N]$ we have

$[\eqalign{n^{\sigma}_{i}(x) &= \lfloor \max_{i}(\sigma)\rfloor-\lfloor \min_{i}(\sigma) \rfloor\cr &-{\bf 1}_{[0,x_{i}]}(\{\max_{i}(\sigma)\})+{\bf 1}_{[0,x_{i})}(\{ \min_{i}(\sigma)\}).}]$

Proof

The proof is independent and essentially identical for each fixed coordinate index i.

Let us fix i. The projection map $[\pi_{i}:{\bb R}^{N}\rightarrow{\bb R}]$ is an open mapping, hence the image $[\pi_{i}(\sigma)]$ is an interval $[[\min_{i}(\sigma),\max_{i}(\sigma)]]$ . The rank of appearance of σ in direction i with respect to x_i equals

$[\lfloor \max_{i}(\sigma)\rfloor-\lfloor \min_{i}(\sigma)\rfloor+\delta,]$

where δ depends on the location of the numbers $[\{\min_{i}(\sigma)\}]$ , $[\{\max_{i}(\sigma)\}]$ in the unit interval. We have

(i) δ = −1 when $[\{\max_{i}(\sigma)\}\leq x_{i}\leq\{\min_{i}(\sigma)\}]$ ;

(ii) δ = 0 when $[x_{i}\leq\{\min_{i}(\sigma)\}\,\lt\,\{\max_{i}(\sigma)\}]$ or $[\{\min_{i}(\sigma)\}\,\lt\,]$ $[\{\max_{i}(\sigma)\}\leq x_{i}]$ or $[\{\max_{i}(\sigma)\} = \{\min_{i}(\sigma)\}\neq x_{i}]$ ;

(iii) δ = 1 when $[\{\min_{i}(\sigma)\}\,\lt\,x_{i}\,\lt\,\{\max_{i}(\sigma)\}]$ .

□

Theorem 4.9

Let $[{\cal T}]$ be a periodic normal tessellation with generating region Ω and translation vectors u. Let σ be a cell in Ω. There exists a u tessellation $[{\cal T}^{\prime}]$ such that the function $[f^{\rm crys}(\sigma,u\semi x_{0},{\bf n})]$ of variable x₀ remains constant in the interior of every k-dimensional cell of the CW structure induced on $[{\cal T}^{\prime}]$ .

Proof

Since the function $[f(x_{0}) = f^{\rm crys}(\sigma,u\semi x_{0},{\bf n})]$ is a sum of finitely many functions of type $[f^{{\rm crys},+}(\sigma,u\semi x_{0},{\bf n})]$ , we just need to prove that such an invariant u tessellation exists for $[f^{{\rm crys},+}(\sigma,u\semi x_{0},{\bf n})]$ .

Without loss of generality we can assume that , the orthonormal standard basis. Indeed, it follows from Lemma 4.8 and Lemma 4.7 that the function $[f^{{\rm crys},+}(\sigma,u\semi x_{0},{\bf n})]$ has an invariant u tessellation which consists of 3^N parallelepipeds (possibly degenerate). In each coordinate direction the unit cell is divided into three segments, following the step function defined in Lemma 4.7.

□

Theorem 4.10

Let $[{\cal T}]$ be a periodic normal tessellation with generating region Ω and translation vectors u. Let $[x_{0}\in{\bb R}^{N}]$ be fixed. Let

$[\{(f_{i}^{\rm crys}(\Omega,u\semi x_{0},{\bf n}))_{i = 0}^{N}:x_{0}\in{\bb R}^{N}\}]$

be the set of crystallographic growth functions attached to $[(x_{0},\Omega,u)]$ . There exists a u tessellation $[{\cal T}^{\prime}]$ such that, for every i, the function $[f_{i}^{\rm crys}(\Omega,u\semi x_{0},{\bf n})]$ of variable x₀ remains constant in the interior of every i-dimensional cell of the CW structure induced on $[{\cal T}^{\prime}]$ .

Proof

For each i the function $[f_{i}^{\rm crys}(\Omega,u\semi x_{0},{\bf n})]$ is a sum of the functions $[f^{\rm crys}(\sigma,u\semi x_{0},{\bf n})]$ , where summation ranges over i-dimensional cells σ of Ω. In fact, the summation goes over the equivalence classes of cells up to translation relation.

It follows from Theorem 4.9 that each function $[f(x_{0}) = f^{\rm crys}(\sigma,u\semi x_{0},{\bf n})]$ has a u tessellation $[{\cal T}_{f}]$ for which the function f(x₀) remains fixed on the interiors of each cell. To conclude, we need the following claim.

Claim. When given two such functions $[f(x_{0},{\bf n})]$ and $[g(x_{0},{\bf n})]$ , with respective u tessellations $[{\cal T}_{f}]$ and $[{\cal T}_{g}]$ on which the functions f and g are constant (with respect to x₀) on the interiors of cells, the function f+g has a corresponding u tessellation $[{\cal T}_{f+g}]$ with the same constancy property as f and g. The new tessellation is obtained from the common subdivision of $[{\cal T}_{f}]$ and $[{\cal T}_{g}]$ .

Proof of the claim. To prove the Claim, it is enough to notice that an intersection of two parallelepipeds generated by rescales of u is again a parallelepiped.

□

Since the function $[f_{i}^{\rm crys}(\Omega,u\semi x_{0},{\bf n})]$ is a sum of $[f^{\rm crys}(\sigma,u\semi x_{0},{\bf n})]$ over finitely many cells σ, the claim proves our theorem.

□

The properties of the crystallographic growth functions, including their pictorial representations in 2D, are discussed in Section 6. A simple, yet non-trivial example of this setup is illustrated by the data in Fig. 11 and the dilated regions are shown in Fig. 5(a). Interested readers can check the actual ratios by executing our code (Malinowski, 2022 ) and inspecting the outputs.

Corollary 4.11

Let $[{\cal T}]$ be a periodic normal tessellation with generating region Ω and translation vectors u. The set of N-tuples of polynomials

$[\{(f_{i}^{\rm crys}(\Omega,u\semi x_{0},{\bf n}))_{i = 0}^{N}:x_{0}\in{\bb R}^{N}\}]$

is finite.

Proof

Let u denote the translation vectors associated with $[{\cal T}]$ and Ω. Let $[{\cal P}]$ be a parallelepiped spanned by u.

Because of Theorem 4.9, there exists a normal periodic tessellation $[{\cal M}]$ with dilates of $[{\cal P}]$ such that the vector $[(f_{i}^{\rm crys}(\Omega,u\semi x_{0},{\bf n}))_{i = 0}^{N}]$ remains fixed for every x₀ in the interior of every cell in $[{\cal M}]$ . Due to the periodic character of the tessellation and to the finite, up to translations in u, CW structure on the tessellation, we obtain the final conclusion.

□

Definition 4.12

Let $[{\cal T}]$ be a periodic normal tessellation with generating region Ω, translation vectors u and associated parallelepiped $[{\cal P}]$ . Due to Corollary 4.11 there exists a tessellation $[{\cal M}]$ of $[{\bb R}^{N}]$ built out of dilates of $[{\cal P}]$ such that we have a function $[C:{\cal M}\rightarrow S]$ to a certain finite set S. The function C has the following properties:

(i) The elements of the set S are in bijection with the set $[\{(f_{i}^{\rm crys}(\Omega,u\semi x_{0},{\bf n}))_{i = 0}^{N}:x_{0}\in{\bb R}^{N}\}]$ .

(ii) For every element $[s\in S]$ the preimage $[C^{-1}(s)]$ is the set of points $[x_{0}\in{\bb R}^{N}]$ for which the vector $[\{(f_{i}^{\rm crys}(\Omega,u\semi x_{0},{\bf n}))_{i = 1}^{N}:x_{0}\in{\bb R}^{N}\}]$ remains fixed.

(iii) For every closed cell σ in $[{\cal M}]$ the function C is closed on the interior of the cell σ.

We call $[({\cal M},C)]$ the `crystallographic coloring' of the space $[{\bb R}^{N}]$ with respect to the quadruple $[({\cal T},\Omega,u,{\cal P})]$ .

The beautiful pictorial representations of the crystallographic colorings are discussed further and shown in Section 6.

5. Topological growth functions of a tiling

Starting from the current section until the end of Section 8, we restrict our attention to the case of normal periodic tessellation of the plane. Such a tessellation $[{\cal T}]$ will be called a tiling and the fundamental domain which covers the plane by translations will be called a tile and denoted Ω. (In this context, the tile is the unit repeated only by translation; note that in the crystallographic context it may be further divided into smaller tiles, possibly related by other symmetry operations.) We consider Ω and the tiling $[{\cal T}]$ with their CW structure. The reason for the restriction to dimension 2 only is twofold. First, we have a complete description of the topological growth functions in terms of the combinatorial data attached to Ω, so far, only in dimension 2 (cf. Theorem 5.5). Second, in Section 6 we develop the theory of crystallographic growth functions of the tilings. This theory can be developed in higher dimensions as well but visualizations of the growth functions become very cumbersome in higher dimensions.

Assume we have a closed, simply connected CW complex $[\Omega\in{\bb R}^{2}]$ and two linearly independent vectors u₁,u₂ such that the shifts of Ω by ku₁+lu₂ for any $[k,l\in{\bb Z}]$ meet only at the boundaries and give rise to a normal periodic tiling of the plane. We require that the vertices are translated to other vertices and edges to edges. We fix a certain 0-cell (a vertex) x₀ which we call the origin of the tiling $[{\cal T}]$ . Let T_x,y denote a tile which is $[S_{x,y}^{u}(\Omega)]$ . We denote by $[{\cal T}_{n_{1},n_{2}}]$ the CW complex obtained as the union of all tiles T_x,y with $[-n_{1}\leq x\leq n_{1}]$ and $[-n_{2}\leq y\leq n_{2}]$ . We denote by $[{\cal T}_{n}]$ the CW complex which is the union of tiles T_x,y with $[-n\leq x,y\leq n]$ . We are going to describe the formulas $[f_{k}^{\rm top}(\Omega\semi (n,n))]$ for the number of k-dimensional cells in $[{\cal T}_{n}]$ . We will generalize this also to the growth function for $[{\cal T}_{n_{1},n_{2}}]$ . It turns out that the only data required to describe these functions are the combinatorial data attached to Ω, i.e. the number of vertices, edges and faces.

It is a consequence of the Laves classification (Grunbaum & Shepherd, 1987, Section 2.7; Girault-Beauquier & Nivat, 1991 ) that the boundary of Ω can be divided into six connected 1-complexes (two possibly degenerating to a single point) such that among them there are three pairs of congruent 1-complexes, i.e. unions of edges. The two model cases are a parallelogram and a hexagon. Topologically speaking, the parallelogram case corresponds to a standard construction of a topological torus with the identification of the translation-equivalent opposite pairs of edges. The hexagon case under the identification of the edges in the first pair leads to a tube with two boundary circles oriented in the `wrong way'. By twisting the tube by 180° (via imaginary topological willpower), one can correctly identify the missing two pairs, obtaining yet again a topological torus but with a non-trivial twisting along the tube.

Case I. The boundary of Ω is a union of four connected 1-complexes: $[\alpha^{+},\alpha^{-}]$ , which are congruent via translation, and $[\beta^{+},\beta^{-}]$ , which are congruent as well [Fig. 3(a)].

Figure 3
Each periodic tiling can be realized with a generalized quadrangle or hexagon. We distinguish the set of edges in both situations and divide them into two or three translation-equivalent pairs.

Case II. The boundary of Ω is a union of six connected interlocking 1-complexes: $[\alpha^{+},\alpha^{-}]$ , which are congruent via translation, and $[\beta^{+},\beta^{-}]$ congruent as well, and finally $[\gamma^{+},\gamma^{-}]$ [Fig. 3(b)].

Lemma 5.1

Let $[{\cal T}]$ be a normal periodic tiling with generating region Ω. Let $[f_{k}(n): = f_{k}^{\rm top}(\Omega\semi (n,n))]$ denote the number of k-cells in the finite tiling $[{\cal T}_{n}]$ . For a fixed $[k\in\{0,1,2\}]$ the function f_k(n) which counts the number of k-dimensional cells in $[{\cal T}_{n}]$ is a quadratic polynomial. Moreover, we have

$[f_{0}(n)-f_{1}(n)+f_{2}(n) = 1]$

for every n.

Proof

The first claim was proved by Naskręcki et al. (2021a). The second claim is a consequence of the fact that $[{\cal T}_{n}]$ is a simply connected region (it is actually contractible to a point). Then the Euler characteristic of such a polygonal region is $[f_{0}(n)-f_{1}(n)+f_{2}(n)]$ and equals 1 in that case [cf. Naskręcki et al. (2022) for such calculations].

□

By orbifolding the complex $[{\cal T}_{n}]$ by the action of the group $[(2n{\bb Z})^{2}]$ one obtains a CW complex $[{\bb T}_{n}]$ which is a 2D torus. We denote by $[f_{k}^{\rm tor}(\Omega\semi n)]$ the number of k-cells in the torus $[{\bb T}_{n}]$ .

Lemma 5.2

With the assumptions of Lemma 5.1 we have that there exists a triple of integers c₀,c₁,c₂ such that the vector $[(f_{0}^{\rm tor}(\Omega\semi n),f_{1}^{\rm tor}(\Omega\semi n),f_{2}^{\rm tor}(\Omega\semi n))]$ is a (2n)² multiple of a constant vector (c₀,c₁,c₂).

Proof

The number c₂ is equal to the number of 2-cells in Ω.

Case I. To compute $[f_{1}^{\rm tor}(\Omega\semi n)]$ we observe that the 1-cells in the boundary of Ω are naturally divided into four subsets $[\alpha^{+}]$ , $[\alpha^{-}]$ , $[\beta^{+}]$ and $[\beta^{-}]$ which get identified in the orbifolding process as a torus. Hence, the inner edges of Ω in $[f_{1}^{\rm tor}(\Omega\semi n)]$ contribute with c₁ⁱ(2n)² ( c₁ⁱ being the number of such inner edges in Ω) and the boundary edges contribute with $[(|\alpha^{+}|+|\beta^{+}|)(2n)^{2}]$ . Since the Euler characteristic of the torus is zero, it follows that $[f_{0}^{\rm tor}(\Omega\semi n)-f_{1}^{\rm tor}(\Omega\semi n)+f_{2}^{\rm tor}(\Omega\semi n) = 0]$ ; thus the polynomial $[f_{0}^{\rm tor}(\Omega\semi n)]$ is of the form c₀(2n)² as well.

Case II. We modify the argument of case I by introducing the third pair of 1-complexes $[\gamma^{+},\gamma^{-}]$ . The modification happens in the contribution of the boundary edges, which is now $[(|\alpha^{+}|+|\beta^{+}|+|\gamma^{+}|)(2n)^{2}]$ .

□

To compute explicitly the numbers $[f_{k}^{\rm top}(\Omega\semi n)]$ we study first the functions $[\delta_{k}(\Omega\semi n)]$ defined as $[f_{k}^{\rm top}(\Omega\semi n)-f_{k}^{\rm tor}(\Omega\semi n)]$ .

Lemma 5.3

Let $[({\cal T},\Omega)]$ be as defined in Lemma 5.1. We have

$[\eqalign{&\delta_{0}(\Omega\semi n) = 2n(|\alpha^{+}|+|\beta^{+}|)+1,\cr &\delta_{1}(\Omega\semi n) = 2n(|\alpha^{+}|+|\beta^{+}|),\cr &\delta_{2}(\Omega\semi n) = 0,}]$

for case I. For case II we have

$[\eqalign{&\delta_{0}(\Omega\semi n) = 2n(|\alpha^{+}|+|\beta^{+}|)+(4n-1)|\gamma^{ +}|+1,\cr &\delta_{1}(\Omega\semi n) = 2n(|\alpha^{+}|+|\beta^{+}|)+(4n-1)|\gamma^{ +}|,\cr &\delta_{2}(\Omega\semi n) = 0.}]$

Proof

The correction $[\delta_{k}(\Omega\semi n)]$ corresponds to the boundary contribution of the tiling $[{\cal T}_{n}]$ . Hence the term for vanishes.

Case I. For we observe that the boundary of $[{\cal T}_{n}]$ consists of 2n copies of elements in $[\alpha^{\pm}]$ and in $[\beta^{\pm}]$ . Since under the orbifolding to $[{\bb T}^{n}]$ the elements from the + set are identified with the elements of the set, the formula follows.

Case II. In this case we have two boundaries of type $[\alpha\gamma\ldots\gamma\alpha]$ , $[\beta\gamma\ldots\gamma\beta]$ with 2n+1 elements each and additionally one chain of type γ. These three chains are connected.

□

Let $[|\Omega_{k}|]$ denote the cardinality of the set of k-cells of the CW complex Ω. Similarly, let $[|\alpha^{\pm}|,\ldots]$ denote the number of 1-cells contained in $[\alpha^{\pm}]$ etc. Based on the Lemma 5.3, we obtain the following explicit formulas for the functions $[f_{i}^{\rm top}(\Omega\semi n)]$ .

Lemma 5.4

Let $[{\cal T}]$ be a normal periodic tiling with the generating region Ω. We have the following formulas for the growth functions $[(f_{0}^{\rm top}(\Omega\semi n),f_{1}^{\rm top}(\Omega\semi n),f_{2}^{\rm top}(\Omega\semi n))]$ expressed in the graph radius n.

Case I polynomials:

$[\eqalign{f_{0}^{\rm top}(\Omega\semi n) &= (|\Omega_{0}|-(1+|\alpha^{+}|+|\beta^{+}|))(2n)^{2}\cr &\quad +(|\alpha^{+}|+|\beta^{+}|)(2n)+1,}]$

$[f_{1}^{\rm top}(\Omega\semi n) = (|\Omega_{1}|-(|\alpha^{+}|+|\beta^{+}|)) (2n)^{2}+(|\alpha^{+}|+|\beta^{+}|)(2n),]$

$[f_{2}^{\rm top}(\Omega\semi n) = |\Omega_{2}|(2n)^{2}.]$

Case II polynomials:

$[\eqalign{f_{0}^{\rm top}(\Omega\semi n)& = (|\Omega_{0}|-(1+|\alpha^{+}|+|\beta^{+}|+ |\gamma^{+}|))(2n)^{2}\cr &\quad+(|\alpha^{+}|+|\beta^{+}|+2|\gamma^{+}|)(2n)+ 1-|\gamma^{+}|,}]$

$[\eqalign{f_{1}^{\rm top}(\Omega\semi n) &= (|\Omega_{1}|-(|\alpha^{+}|+|\beta^{+}|+| \gamma^{+}|))(2n)^{2}\cr &\quad +(|\alpha^{+}|+|\beta^{+}|+2|\gamma^{+}|)(2n)-| \gamma^{+}|,}]$

$[f_{2}^{\rm top}(\Omega\semi n) = |\Omega_{2}|(2n)^{2}.]$

Proof

Since $[f_{2}^{\rm top}(\Omega\semi n) = f_{2}^{\rm tor}(\Omega\semi n)]$ we have

$[f_{2}^{\rm top}(\Omega\semi n) = |\Omega_{2}|(2n)^{2},]$

where $[\Omega_{2}]$ is the set of faces of Ω. Case I: we have

$[f_{1}^{\rm tor}(\Omega\semi n) = (|\Omega_{1}^{\rm in}|+|\alpha^{+}|+|\beta^{+}|)(2n)^{2}]$

and

$[f_{1}^{\rm top}(\Omega\semi n) = f_{1}^{\rm tor}(\Omega\semi n)+(|\alpha^{+}|+|\beta^{+}|)(2n),]$

hence

$[f_{1}^{\rm top}(\Omega\semi n) = (|\Omega_{1}^{\rm in}|+|\alpha^{+}|+|\beta^{+}|)(2n)^{2}+(| \alpha^{+}|+|\beta^{+}|)(2n),]$

where $[\Omega_{1}^{\rm in}]$ is the set of inner edges of Ω (not in the boundary). Finally, notice that $[f_{0}^{\rm top}(\Omega\semi n)-f_{1}^{\rm top}(\Omega\semi n)+f_{2}^{\rm top}(\Omega\semi n)]$ = 1 and $[|\Omega_{0}|-|\Omega_{1}|+|\Omega_{2}| = 1]$ ( $[\Omega_{i}]$ is the set of i-dimensional faces of Ω) and $[|\Omega_{1}|]$ = $[|\Omega_{1}^{\rm in}|+2(|\alpha^{+}|+|\beta^{+}|)]$ , hence

$[\eqalign{f_{0}^{\rm top}(\Omega\semi n)& = (|\Omega_{0}|-1-|\alpha^{+}|-|\beta^{+}|)(2n)^{2}\cr &\quad +(| \alpha^{+}|+|\beta^{+}|)(2n)+1.}]$

A similar proof applies to Case II.

□

In a periodic tiling one can independently change two parameters, say n₁,n₂. Thus, when the periodic tiling is given with the fundamental domain Ω, we can generalize the argument presented in Lemmas 5.1–5.4 to this setup. As a result, we obtain the following formulas.

Theorem 5.5

Let $[{\cal T}]$ be a periodic normal tiling with the generating region Ω. For each positive n₁,n₂, one gets

$[\eqalign{f_{0}^{\rm top}(\Omega\semi n_{1},n_{2}) &= (|\Omega_{0}|-(1+|\alpha^{+}|+| \beta^{+}|+|\gamma^{+}|))(4n_{1}n_{2})\cr &+|\alpha^{+}|(2n_{2})+|\beta^{+}|(2 n_{1})+|\gamma^{+}|(2(n_{1}+n_{2}))\cr &+1-|\gamma^{+}|,}]$

$[\eqalign{f_{1}^{\rm top}(\Omega\semi n_{1},n_{2})& = (|\Omega_{1}|-(|\alpha^{+}|+| \beta^{+}|+|\gamma^{+}|))(4n_{1}n_{2})\cr &+|\alpha^{+}|(2n_{2})+|\beta^{+}|(2 n_{1})\cr &+|\gamma^{+}|(2(n_{1}+n_{2}))-|\gamma^{+}|,}]$

$[f_{2}^{\rm top}(\Omega\semi n_{1},n_{2}) = |\Omega_{2}|(4n_{1}n_{2}).]$

If we take into account the normalization of the variables discussed in Section 4.1, the formulas in Theorem 5.5 provide a way to compute the topological growth functions for periodic tilings that does not require any linear algebra computations. A numerical approach (which uses explicit matrix computations) is presented in Appendix B (Section B1). The importance of these formulas is theoretical. It shows that the coefficients are always integers and moreover we obtain a relation of the coefficients of the growth functions with the combinatorial data describing the fundamental domain Ω. For the tilings in Fig. 1 we have compiled in Table 1 a list of data attached to fundamental regions Ω that are indicated with thick black edges. The formulas from Theorem 5.5 together with Table 1 reproduce the normalized polynomials presented in Table 2.

Table 1
Numbers $[|\Omega_{i}|]$ are counts of i-dimensional cells of the fundamental region of Ω attached to a tiling of the type described in Fig. 1

The numbers $[|\langle {\rm letter} \rangle^{+}|]$ count the edges of a given type.

Tiling	$[\|\Omega_{0}\|]$	$[\|\Omega_{1}\|]$	$[\|\alpha^{+}\|]$	$[\|\beta^{+}\|]$	$[\|\gamma^{+}\|]$	$[\|\Omega_{2}\|]$
4444	4	4	1	1	0	1
333333	6	6	1	1	1	1
666	7	12	1	1	1	6
884	5	8	1	1	0	4
44333	8	9	2	1	1	2
43433	13	16	3	3	0	4
6363	7	9	1	1	1	3
6434	13	18	2	2	2	6
1264	13	24	2	2	2	12
12123	7	12	1	1	1	6
63333	19	24	3	3	3	6

Table 2
Topological growth functions for the polygonal units filling the plane by translations, corresponding to the 11 types of tilings shown in Fig. 1

Each row represents three functions, for the growth of the number of vertices (V), edges (E) and faces (F). Each function is normalized, e.g. the tiling of type 4444 from Fig. 1 has the growth functions n₁n₂+n₁+n₂+1, 2n₁n₂+n₁+n₂ and n₁n₂.

		V				E				F
Type	Symmetry	n₁n₂	n₁	n₂	1	n₁n₂	n₁	n₂	1	n₁n₂	n₁	n₂	1
4444	p4mm	1	1	1	1	2	1	1	0	1	0	0	0
333333	p6mm	2	2	2	0	3	2	2	−1	1	0	0	0
666	p6mm	3	2	2	0	9	2	2	−1	6	0	0	0
884	p4mm	2	1	1	1	6	1	1	0	4	0	0	0
44333	c2mm	3	2	3	0	5	2	3	−1	2	0	0	0
43433	p4gm	6	3	3	1	10	3	3	0	4	0	0	0
6363	p6mm	3	2	2	0	6	2	2	−1	3	0	0	0
6434	p6mm	6	4	4	−1	12	4	4	−2	6	0	0	0
1264	p6mm	6	4	4	−1	18	4	4	−2	12	0	0	0
12123	p6mm	3	2	2	0	9	2	2	−1	6	0	0	0
63333	p6	9	6	6	−2	15	6	6	−3	6	0	0	0

Example 5.6

The 11 Laves tilings. Among the 11 types of tilings presented in Fig. 1, some tiles have four neighbors and have the shape of a square (4444 and 884) or a `wobbly' square (43433), while others have six neighbors and the shape of a hexagon. However, certain tilings, shown in Fig. 1 as built from hexagons, can also be presented as built from rhombuses (666, 6434, 1264, 12123) or `wobbly' rhombuses (63333). For example, the 666 case in Fig. 4 is an alternative of Fig. 1(c). Such rhombuses represent the proper crystallographic unit cells of the hexagonal system. Each rhombus has then four (edge) neighbors. In the remaining three tilings (333333, 44333, 6363) the individual tiles can only be presented as hexagons, and not as rhombuses. Of course, even for the hexagonal 333333 and 6363 tilings the crystallographic unit cells can be selected as rhombuses, but such cells would not have their vertices at the hexagonal lattice nodes. The 44333 tiling has rectangular symmetry and each alternatively selected tile always has six neighbors. The topological growth functions for the 44333 tiling and the other ten Laves tilings are presented in Table 2.

Figure 4
The 666 tiling (thin lines) presented as rhombic tiles (one tile shaded gray) having four edge-neighbors each. The rhombic tiles, each comprised of two adjacent 666 triangular tiles, correspond to the crystallographic unit cells of the hexagonal system.

6. Crystallographic growth functions of a tiling

In this part, we will present a method to compute the topological and crystallographic growth functions that is based on linear algebra. The reason why these computational methods are useful stems from the fact that the identification of the boundary data for the domain Ω is not always easy and completely trivial. In comparison, the methods presented in Section B1 are straightforward to implement and very robust.

We fix a tiling $[{\cal T}]$ with the fundamental domain Ω. The translations in $[{\cal T}]$ are spanned by two non-parallel vectors u₁,u₂ which form a parallelogram $[{\cal P}]$ . We fix a starting point x₀ in Ω and consider, as discussed in Section 4.2, the set of three growth functions relative to $[{\cal P}]$ and its shifts. We are interested in finding a pattern for the growth functions relative to x₀. The main observation is that these functions vary with x₀ and are `locally constant', i.e. they stay fixed when x₀ moves within the relative interior of each fixed cell. The precise conditions at the boundaries were described in Section 4.3.

6.1. Properties of the crystallographic growth functions

In particular, we can attach to such domains of invariant growth functions a given color. Each such domain is either a point, a line segment or a parallelogram etc. Such colored diagrams carry rich information about the tiling itself.

We compare two tilings which are topologically, but not geometrically, identical. The topological growth functions are the same for them but the crystallographic growth functions are distinct.

One can notice that the leading terms of the growth functions are identical in both situations, but the geometric pattern in which these triplets of functions appear is different.

The patterns satisfy further properties, namely:

(i) Invariance of the color-encoding scheme under the change of basis for the crystallographic lattice.

(ii) Compared with the topological functions, the crystallographic ones are sensitive to the deformations of the lattice, i.e. they encode point-group symmetries in the color arrangement (there is a finite group action on the arrangements of colorings of cells).

(iii) The crystallographic growth functions encode locally the same information as the topological growth functions but the extra dependence on the relation with the frame of reference provides an additional input about the symmetry of the group (the topological growth functions are completely insensitive to the difference between two topologically equivalent, yet geometrically different, tilings).

We illustrate this idea using, as examples, the orphic diagrams in Figs. 5 and 6.

Figure 5
Diagram (a) represents the changes of the growth functions as we move across the plane tiled according to the topological 333333 pattern, with symmetry group p6mm. Diagram (b) has a tiling that is topologically equivalent but the symmetry group is reduced to c2mm. This is reflected in the color (growth functions) pattern.

Figure 6
Diagram (a) represents the changes of the growth functions as we move across the plane tiled according to the topological 44333 pattern, with symmetry group c2mm. Diagram (b) has a tiling that is topologically equivalent but the symmetry group is reduced to p2. This is reflected in the color (growth functions) pattern.

6.2. Orphic diagrams

We note that the diagrams color-coding the crystallographic growth functions bear striking similarity to the paintings of the orphists. We call, therefore, our diagrams orphic diagrams. Around 1912 a new style in art, called orphism, was born. We quote two descriptions of the orphic style.

`The term, sometimes called orphic cubism, was coined around 1912–13 by the French poet and art critic Guillaume Apollinaire and used to distinguish their work from cubism generally. The name comes from the legendary ancient Greek poet and musician Orpheus. Its use by Apollinaire relates to the idea that painting should be like music, which was an important element in the development of abstract art. Robert Delaunay himself used the term simultanism to describe his work' (https://www.tate.org.uk/).

Also

`Orphist painters were interested in the geometric fragmentation of Cubism, but – unlike the Cubists, who removed almost all color from their paintings, and rather like the Fauvists – they considered color to be a powerful esthetic element' (Encyclopedia Britannica, https://www.britannica.com/).

The main orphists were Robert Delaunay (Fig. 7), his wife Sonia Terk Delaunay, and František Kupka.

Figure 7
Robert Delaunay; Windows; Paris 1912; an example of orphic art.

More formally, we capture the `spirit' of the orphic diagrams in the following definition.

Definition 6.1

(Orphic diagram) Let $[{\cal T}]$ be a periodic normal tiling with a generating region Ω, translation vectors u and associated parallelogram $[{\cal P}]$ . The associated crystallographic coloring $[({\cal M},C)]$ in the sense of Definition 4.12 defines a function

$[c:\Omega\rightarrow S]$

which is obtained as the restriction of $[C:{\cal M}\rightarrow S]$ to the set Ω. The pair $[(\Omega,c)]$ is called the orphic diagram of $[({\cal T},\Omega,u,{\cal P})]$ .

In practice, the choice of the `colors' in the set S is arbitrary. In the pictorial representation of the orphic diagram we try to choose highly contrasting colors for the neighboring regions. Also, when faced with the representation of the 0D, 1D and 2D regions we decided to show the 0D and 1D features in a separate picture (cf. Fig. 9). The color mappings for each case are independent.

Example 6.2

Reconstruction of point-group symmetry from its orphic diagram. In this example we investigate the orphic diagram associated with tiling 43433 from Fig. 1. The coefficients of the crystallographic growth functions are given in Table 3.

Table 3
Growth function coefficients for the 0D, 1D and 2D regions of Fig. 8

(a) Coefficients of the growth functions for the 2D regions (their interiors) in Fig. 8. Each row represents three functions, for the growth of the number of vertices (V), edges (E) and faces (F). Each function is normalized, e.g. the region E has the growth functions 6n₁n₂, $[10n_{1}n_{2}-3(n_{1}+n_{2})+1]$ , $[4n_{1}n_{2}-3(n_{1}+n_{2})+2]$ .

	V				E				F
	n₁n₂	n₁	n₂	1	n₁n₂	n₁	n₂	1	n₁n₂	n₁	n₂	1
E	6	0	0	0	10	−3	−3	1	4	−3	−3	2
L	6	0	0	0	10	−3	−3	1	4	−3	−3	3
J	6	0	0	0	10	−3	−2	0	4	−3	−2	1
F	6	0	0	0	10	−3	−2	1	4	−3	−2	2
H	6	0	0	0	10	−2	−3	0	4	−2	−3	1
G	6	0	0	0	10	−2	−3	1	4	−2	−3	2
K	6	0	0	0	10	−2	−2	0	4	−2	−2	1

(b) Coefficients of the growth functions for the interiors of the line segments in Fig. 8. Each row represents three functions, for the growth of the number of vertices (V), edges (E) and faces (F). The syntax XYh/v indicates the interior of the edge between regions X and Y (v stands for vertical, h for horizontal edge).

	V				E				F
	n₁n₂	n₁	n₂	1	n₁n₂	n₁	n₂	1	n₁n₂	n₁	n₂	1
EEv, EJv	6	0	1	0	10	−3	−1	0	4	−3	−2	1
ELv, EFv	6	0	1	0	10	−3	−1	1	4	−3	−2	2
FLv	6	0	1	0	10	−3	−1	0	4	−3	−2	2
GHv, GKv, HKv	6	0	1	0	10	−2	−1	0	4	−2	−2	1
EEh, EHh	6	1	0	0	10	−1	−3	0	4	−2	−3	1
EGh, ELh	6	1	0	0	10	−1	−3	1	4	−2	−3	2
GLh	6	1	0	0	10	−1	−3	0	4	−2	−3	2
FJh, JKh, FKh	6	1	0	0	10	−1	−2	0	4	−2	−2	1

(c) Coefficients of the growth functions for the vertices in Fig. 8. Each row represents three functions, for the growth of the number of vertices (V), edges (E) and faces (F). The syntax XYZW indicates the vertex at the intersection of the 2D regions X, Y, Z and W.

	V				E				F
	n₁n₂	n₁	n₂	1	n₁n₂	n₁	n₂	1	n₁n₂	n₁	n₂	1
EEEE	6	1	1	1	10	−1	−1	0	4	−2	−2	0
EEGH, EGHL, EEFJ, EGJK, EFJL, EHJK, EFHK	6	1	1	0	10	−1	−1	0	4	−2	−2	1
EELL	6	1	1	0	10	−1	−1	1	4	−2	−2	2
FGKL	6	1	1	1	10	−1	−1	0	4	−2	−2	1

The orphic figure (Fig. 8) has interesting symmetry properties. For zero degrees of freedom (vertices), the figures are invariant (symmetric) with respect to n₁/n₂ exchange. For one and two degrees of freedom, only some regions possess this symmetry.

Figure 8
The orphic diagram generated for the 43433 tiling, in which each color represents a different triplet of growth functions. Each colored region (labeled by letters E to L) corresponds to growth functions obtained by assuming the origin of the crystallographic unit cell within that region. The letters A, B, C, D mark the vertices of the pentagonal tiles of the 43433 tiling. The pink lines mark the coordinates of the tile vertices in the x and y directions. Please note that the symmetry of this orphic diagram is p2gg. See the text for detailed explanations.

There is a true vertical glide line g passing through the centers of squares K1 and K4 (as well as through K2 and K3, and through the centers of regions F5, J3, F1, J2, F4). It allows a right–left reflection with a simultaneous parallel translation by 1/2 of the unit-cell edge, after which operation the color pattern is the same. For example, H4 is transformed into H1, E6 into E7, L1 into L7 etc. There are also horizontal glide lines through the centers of square pairs K2/K4 and K1/K3. The vertical and horizontal g lines are shifted by 1/2 of the unit-cell edge along y and x, respectively. Note that the unit-cell corners are at B1, B2, B3 and B4. In addition, there are twofold rotations around the centers of the four green squares, i.e. at the unit-cell corners (points B) and at its center (point A), as well as at the common vertices of two navy-blue squares (i.e. at the center of the unit-cell edge). The color pattern has, therefore, the rectangular p2gg symmetry.

One notes, however, that the pattern has in fact apparent higher symmetry, that we term `pseudosymmetry', which holds for the shapes of the orphic tiles but not for their color, and which is described as follows. There is a diagonal `pseudomirror line' passing through the centers of squares L6, L1, K1 and E7, which transforms these squares onto themselves, and the adjacent pairs of regions of different colors onto one another, e.g. F1–G3 or H1–J3. These varicolored pairs correspond to polynomials that differ only by a swap of the n₁/n₂ coefficients. It is a logical consequence of the fact that a diagonal inversion exchanges the horizontal and vertical directions. Analogous `pseudomirrors' bisect squares K4 and K3, as well as E8, K2, L2 and L5; and in the perpendicular direction K2, K1 etc. Also points A and B1–B4 are the sites of `pseudofourfold' axes, which exchange the polynomial coefficients within the square pairs H1/J2, H2/J2, F1/G2, F2/G1, as well as F5/G6, J3/H4 etc. Such a (pseudo)symmetry pattern corresponds to the square group p4gm, which is the space group of the original underlying 43433 tessellation of the plane with pentagons.

It is interesting that the navy-blue squares L (and their two edges) have `non-Eulerian' polynomials, for which the telescoping sum of coefficients is not equal to 1, but 2.

Example 6.3

Orphic diagrams of standard tilings, cf. Fig. 1. To illustrate the wealth of information contained in the orphic diagrams (which represent crystallographic growth functions), we tabulate them for the standard tilings presented in Fig. 1. Readers can find the precise polynomial functions describing each color in the supporting information files deposited in Zenodo (Malinowski, 2022). Each color represents a unique triple of polynomials, which correspond to the growth functions of the vertex set, edge set and face set, starting in the unicolored region. When the color changes, over a region boundary, we obtain a different triple of polynomial functions. We notice that the boundaries of the 2D unicolored regions typically have different growth functions, so in fact the orphic diagram contains information in its whole 2D structure as a CW complex. We record in Fig. 9 the orphic diagrams corresponding to the tilings of Fig. 1.

Figure 9
A pair of orphic diagrams generated for each tiling in Fig. 1

. In each case, the left diagram corresponds to changes of the growth functions in 2D regions and the right diagram shows how they change at the specific boundaries. For each tiling type, a given color represents a unique triple of growth functions.

7. Applications and properties of the growth functions

The main reason for studying the growth functions of tessellations is the expectation that such algebraic–combinatorial data might be sufficient to encode the information about a tessellation. (We want to define enough numerical properties that allow us to reconstruct a tessellation up to isometry.) This expectation is expressed using graph theory in the book by Sunada (2013 ). While the growth functions are easy to compute, the reconstruction of the information about the tessellation from the functions themselves is a more challenging problem. In the following subsections we point to places where the growth functions connect to other interesting invariants of tessellations.

Different variants of the growth functions carry a wealth of information about the tessellations. In particular, we show how such information can be extracted and used.

7.1. Relation to the modified Euler characteristic

Given a periodic tiling $[{\cal T}]$ , we consider its symmetry group G. The quotient space $[{\bb R}^{2}/G]$ is a topological space which carries a natural structure of an orbifold $[{\cal O}]$ (cf. Naskręcki et al., 2021a, 2021b). Computation of the associated Euler characteristic attached to the orbifold $[{\cal O}]$ consists of computing a vector $[u({\cal O}) = (\chi_{0},\chi_{1},\chi_{2})]$ of rational numbers such that $[\chi_{0}-\chi_{1}+\chi_{2}]$ is the orbifold Euler characteristic of $[{\cal O}]$ in the sense of Thurston (Naskręcki et al., 2021a). We proved that the vectors $[(\chi_{0},\chi_{1},\chi_{2})]$ and

$[\eqalign{&\left(|\Omega_{0}|-(1+|\alpha^{+}|+|\beta^{+}|+|\gamma^{+}|),\right.\cr &\left.|\Omega_{1}|-(| \alpha^{+}|+|\beta^{+}|+|\gamma^{+}|),|\Omega_{2}|\right)}]$

are proportional. The proportionality constant is computed from the quotient of the surfaces of Ω and the parallelogram $[{\cal P}]$ which is spanned by the translation subgroup vectors. The topological growth functions carry information about the orbifold $[{\cal O}]$ . However, the topological growth functions also contain information about the combinatorics of the boundary of Ω.

7.2. Identification of a tiling using the growth functions

To show the practical utility of the growth functions, we carried out the following simulation. Starting with the tiling 884 generated in a sufficiently large range (at least four steps in each direction), we randomly (with probability ) remove the central node of a square. Next, we generate the topological growth functions by starting the calculation at k² different points. The mean of the coefficients of the fixed-index polynomials is rounded to the nearest integer. We calculate for a given probability p how many times the tiling is classified as 884 or 4444 (or as `other'). The numerical results are summarized in Table 4. k represents the number of sampling points in each direction. In a column with fixed k, for each p we have three numbers, showing the number of polynomials that were recognized as the topological growth functions of tiling 884, tiling 4444 and unrecognized functions, respectively.

Table 4
The ability of the growth functions to recognize the tiling, when 884 is distorted towards 4444

1 − p is the probability of a removal of the central vertex (change from the 884 to 4444 tiling). k represents the number of sampling points in each direction. The three numbers in each row and column represent the numbers of generated polynomials that either are of type 884, of type 4444 or something else (cf. Section 7.2).

p/k	1			2			3			4
0.01	0	962	38	0	995	5	0	1000	0	0	1000	0
0.1	0	672	328	18	826	156	0	984	16	0	997	3
0.2	4	406	590	91	553	356	13	915	72	7	977	16
0.5	53	55	892	399	124	477	434	410	156	582	375	43
0.8	424	1	575	672	0	328	918	11	71	986	0	14
0.9	663	0	337	847	0	153	988	0	12	998	0	2
0.99	955	0	45	997	0	3	1000	0	0	1000	0	0

8. Outlook

In this paper we established some basic properties of the growth functions attached to 2D tilings. In Section 5 we showed that the leading terms of the growth functions form a vector that can be described in terms of the contributions to the modified Euler characteristic (orbifold characteristic). In Section 4 we proved several statements that describe the fundamental geometric properties of the crystallographic growth functions, encoded the properties of the tessellation in the crystallographic coloring functions, and explored the basic properties and applications of the coloring functions and orphic diagrams in Sections 6, 7.

We expect that it will be possible to find further properties of these functions. In particular, we think that it should be possible to find a relation between the polynomials that define the growth functions of dual tilings.

Is there a similar relation between the secondary terms of the growth functions and the properties of the region Ω? In particular, is there a relation (similar to isoperimetry) between the area and diameter of Ω? We plan to investigate these and other problems related to the tessellations of space as a continuation of this project, by means of convolutional neural networks and supervised machine learning. Among those other problems is the discovery of a precise relation between the symmetry group of a tessellation and the coefficients of the growth functions. We plan to implement this strategy following the general scheme proposed by Davies et al. (2021 ).

8.1. Higher dimensions

In 3D and higher dimensions of the Euclidean space, the growth functions become more complicated and their mutual relations are much harder to track. In addition, the number of different tessellations is unknown even in 3D (cf. Goodman et al., 2018 , Section 3.2, p. 74, p. 3). As a reconnaissance exercise, we have computed a handful of examples for some crystallographic 3D tessellations, and present them in Fig. 10 and Table 5.

Table 5
Crystallographic growth functions (of single variable n) of all elements of the unit cells shown in Fig. 10

Space group	V	E	F	I
P23	5n³+6n²+3n+1	23n³+18n²+3n	30n³+12n²	12n³
Pm $[\overline{3}]$	8n³+12n²+6n+1	44n³+24n²+6n	60n³+12n²	24n³
P432 and $[P\overline{4}3m]$	5n³+6n²+3n+1	29n³+18n²+3n	48n³+12n²	24n³
$[Pm\overline{3}]$ m	8n³+12n²+6n+1	56n³+36n²+6n	96n³+24n²	48n³

Figure 10
The unit cells of the primitive cubic symmorphic space groups, divided into individual asymmetric units, with one asymmetric unit highlighted in blue. (a) P23, (b) $[Pm\overline{3}]$ , (c) P432 and $[P\overline{4}3m]$ , (d) $[Pm\overline{3}m]$ .

APPENDIX A

Mathematical glossary

This is a glossary of the less familiar mathematical terms, ordered alphabetically. In the text, after the first use of a glossary term, we include a cross-reference to this appendix `(Appendix A)'.

An Archimedean tiling is a tiling where every vertex has the same valency. Its dual is called the Laves tiling.

A fundamental domain is a shape that has the property that the space group maps every point in the Euclidean space to a unique point in the fundamental domain via a unique symmetry group operation.

A CW complex is a way of building spaces by starting with a collection of points and attaching cells of different dimensions to these points.

Think of a cell as a simple shape, like a line segment, a triangle or a cube. You start by taking a collection of points, and then you attach 1D cells (line segments) between them to form a network of connected line segments. Then, you can attach 2D cells (triangles or squares) to these line segments to form a more complex shape. Finally, you can attach 3D cells (cubes) to build a solid object.

In this way, you can construct a space by attaching cells of different dimensions to a collection of points, and this is called a CW complex, according to Whitehead (1949). The name CW stands for closure-finite weak topology. The cells can be attached in many different ways to create a wide variety of shapes and spaces, and this makes CW complexes a useful tool for understanding topological spaces.

In particular, a k-cell is a k-dimensional ball which we use as a building block in constructing CW complexes.

The Euler characteristic of a finite CW complex is the alternating sum $[\sum_{k}(-1)^{k}f_{k}]$ , where f_k is the number of k-dimensional cells in the complex.

An orbifold is a topological space that is similar to a manifold, which is modeled locally with Euclidean space $[{\bb R}^{N}]$ . Orbifolds differ from manifolds at the so-called singular subset. These singular points reflect the fact that orbifolds are obtained by the process of taking a quotient space of the Euclidean space by finite group actions. The singular points correspond to points in the Euclidean space that are stabilized by the group action.

An orphic diagram is a pictorial representation of the crystallographic growth functions attached to a fixed normal periodic tiling. Since the crystallographic growth functions depend on the initial vertex of the tiling, we associate with every point on the 2D plane an identical color if the triple of growth functions (for the vertices, edges and faces) stays the same. This provides a coloring of the plane with finitely many colors. More generally, orphic diagrams may be used to illustrate by color certain mathematical properties of certain x,y areas of the 2D plane.

An (ordered) tuple of elements $[(a_{1},\ldots,a_{n})]$ is a mathematical object that stores elements a_i with a strict ordering from left to right. It is modeled set-theoretically, i.e. by the construction of Kuratowski (1921 ), namely the 2-tuple (a,b) is the set {{a},{a,b}} and the N-tuple is generated inductively.

In relative approach, given a CW complex structure on $[{\bb R}^{N}]$ , one can consider a family of growth functions which depend on another tessellation or metric and which allow us to generate an index set $[{\cal I}]$ and a family $[\{{\cal T}_{i}\}_{i\in{\cal I}}]$ of finite CW complexes such that $[{\cal T} = \cup_{i\in{\cal I}}{\cal T}_{i}]$ . In fact, we consider this sum as an inductive limit of finite CW complexes. For such a family we consider functions $[f:{\cal I}\rightarrow{\bb R}]$ which `measure' the `growth' of the tessellation $[{\cal T}]$ against the family $[\{{\cal T}_{i}\}_{i\in{\cal I}}]$ . We consider $[{\cal I}]$ as a partially ordered set (Rasiowa, 1973 , ch. IX), and consider the monotonic properties of the function f against such order.

APPENDIX B

Python code and algorithm

In the framework of this project we have developed a Python computer code that helps to illustrate the character of our theoretical results. In Section B1 we describe the algorithm for the calculation of the topological growth functions for arbitrary periodic tilings. The code is written in such a way that it can be easily adapted to any higher-dimensional case. In the supporting information files there is a loadable Python library that accepts as input a text file that describes completely the tiling of interest. An example input file encoding the 333333 tiling is presented in Fig. 11. The first line shows the number of cells in each dimension sorted in ascending order with respect to the cell dimension. The following lines encode the coordinates of the tiling vertices. The coordinates can be given using crystallographic or Cartesian convention. When describing vertices, the standard mathematical syntax can be used. Higher-dimensional cells are described after the vertices. Each line encodes one cell. Higher-dimensional cells are encoded with vertex indices. The last two lines contain information about translation vectors.

Figure 11
Sample input (a) encoding the 333333 tiling (b). The line 6 6 1 (red) gives $[V\ E\ F]$ , where V is the number of vertices, E is the number of edges and F is the number of faces. The next six (V) lines (green) describe the crystallographic coordinates of the vertices. The next six (E) (black) lines describe the connectivity of the vertices (i.e. edges). Finally, the next one (F) (red) line(s) describe the faces. The last two (blue) lines specify the translational lattice.

In Section B1 we discuss the details of the computation of the crystallographic growth functions. The theoretical foundations were discussed in Section 4.3.

B1. Finding the topological growth functions

The algorithm get_topological_growth_polynomials finds the growth functions based on a list of 0D cells of the repeating unit, the number of 2D cells of the repeating unit and the translation vectors. The function f₀ is of the following form:

$[f_{0}(n_{1},n_{2}) = a_{11}n_{1}n_{2}+a_{10}n_{1}+a_{01}n_{2}+a_{00}.]$

The algorithm finds the coefficients a₁₁,a₁₀,a₀₁,a₀₀ by solving the system of linear equations (1):

$[\left\{\matrix{f_0(1,1) &= & a_{11}+a_{10}+a_{01}+a_{00},\cr f_{0}(1,2) &= &2a_{11}+a_{10}+2a_{01}+a_{00},\cr f_{0}(2,1) &= &2a_{11}+2a_{10}+a_{01}+a_{00},\cr f_{0}(2,2) &= &4a_{11}+2a_{10}+2a_{01}+a_{00}.\cr} \right.\eqno(1)]$

The values of the function f₀ in (1) are found using the method get_k_cells_num described by Algorithm 1. The algorithm get_topological_growth_polynomials calculates the formula for function f₁ using the identity f₁(n₁,n₂) = $[f_{2}(n_{1},n_{2})+f_{0}(n_{1},n_{2})-1]$ . This identity is a simple consequence of the Euler characteristics for a simply connected CW complex.

B2. Finding the crystallographic growth functions

The method denoted get_crystallographic_growth_functions finds the crystallographic growth functions (let us denote them F₀,F₁,F₂) based on a list of 0D, 1D and 2D cells of the repeating unit, the generating period vectors, a starting point, and two rational numbers to scale the frame.

The polynomials defining the growth functions for particular groups of arguments are found using an algorithm analogous to that of get_topological_growth_function used to find the function f₀. Our algorithm for finding the crystallographic growth functions of a single variable is presented in Algorithm 2:

$[A_{N,s}^{i}:\left\{\matrix{F_{i}(2N+s,v)& = &a_{2}(2N+s)^{2}+a_{1}(2N+s)+a_{0} \cr F_{i}(3N+s,v)& = &a_{2}(3N+s)^{2}+a_{1}(3N+s)+a_{0}\cr F_{i}(4N+s,v)& = &a_{2}(4N+s)^{2}+a_{1}(4N+s)+a_{0}.\cr } \right.\eqno(2)]$

The algorithm for multivariable functions is analogous.

As in the case of finding the topological growth functions, also in this case we use information about the values of the growth function for given sets of arguments to find the polynomial coefficients. The required values are computed by the subroutine get_k_cells_num_parallelogram, which counts the numbers of k-cells of $[{\cal T}]$ that are completely contained within the parallelogram.

B3. Computer code availability

The Python computer code developed to generate the growth functions discussed in this paper is freely available at the DOI link given by Malinowski (2022). The input consists of a text string entered at a prompt. The output consists of the explicit polynomial growth functions and their illustrations by orphic diagrams.

Acknowledgements

BN and JM would like to thank Dr V. Kurlin of the Materials Innovation Factory, Liverpool, UK, for supporting their visit to the facility, during which time some of the ideas for this paper were crystallized.

Funding information

BN and JM acknowledge the support of the Dioscuri program initiated by the Max Planck Society, jointly managed with the National Science Centre (Poland), and mutually funded by the Polish Ministry of Science and Higher Education and the German Federal Ministry of Education and Research. We acknowledge with thanks the financial support of the Rector's Fund of the School of Exact Sciences of Adam Mickiewicz University in Poznań. This work was supported in part by the Intramural Research Program of the NIH, National Cancer Institute, Center for Cancer Research.

References

Dauter, Z. & Jaskolski, M. (2020). Acta Cryst. A76, 580–583. Web of Science CrossRef IUCr Journals Google Scholar
Davies, A., Veličković, P., Buesing, L., Blackwell, S., Zheng, D., Tomašev, N., Tanburn, R., Battaglia, P., Blundell, C., Juhász, A., Lackenby, M., Williamson, G., Hassabis, D. & Kohli, P. (2021). Nature, 600, 70–74. CrossRef CAS PubMed Google Scholar
Girault-Beauquier, D. & Nivat, M. (1991). Topology and category theory in computer science, pp. 291–333. Oxford University Press. Google Scholar
Goodman, J. E., O'Rourke, J. & Tóth, C. D. (2018). Editors. Handbook of discrete and computational geometry. Discrete mathematics and its applications. Boca Raton: CRC Press. Google Scholar
Grosse-Kunstleve, R. W., Brunner, G. O. & Sloane, N. J. A. (1996). Acta Cryst. A52, 879–889. CrossRef CAS Web of Science IUCr Journals Google Scholar
Grünbaum, B. & Shephard, G. C. (1987). Tilings and patterns. New York: W. H. Freeman and Company. Google Scholar
Hatcher, A. (2002). Algebraic topology. Cambridge University Press. Google Scholar
Kuratowski, C. (1921). Fundamenta Mathematicae, 2, 161–171. CrossRef Google Scholar
Malinowski, J. (2022). Orphic diagrams: Python package for computing growth functions of planar tessellations, DOI:10.5281/zenodo.7275211. Google Scholar
Naskręcki, B., Dauter, Z. & Jaskolski, M. (2021a). Acta Cryst. A77, 317–326. CrossRef IUCr Journals Google Scholar
Naskręcki, B., Dauter, Z. & Jaskolski, M. (2021b). Acta Cryst. A77, 126–129. CrossRef IUCr Journals Google Scholar
Naskręcki, B., Jaskolski, M. & Dauter, Z. (2022). J. Appl. Cryst. 55, 154–167. CrossRef IUCr Journals Google Scholar
Rasiowa, H. (1973). Introduction to modern mathematics. Amsterdam: North-Holland Publishing Co. Google Scholar
Senechal, M. (1995). Quasicrystals and geometry. Cambridge University Press. Google Scholar
Sunada, T. (2013). Topological crystallography, Vol. 6 of Surveys and tutorials in the applied mathematical sciences. Tokyo: Springer. Google Scholar
Whitehead, J. H. C. (1949). Bull. Am. Math. Soc. 55, 213–245. CrossRef Google Scholar

This is an open-access article distributed under the terms of the Creative Commons Attribution (CC-BY) Licence, which permits unrestricted use, distribution, and reproduction in any medium, provided the original authors and source are cited.

FOUNDATIONS
ADVANCES

ISSN: 2053-2733

Volume 81| Part 1| January 2025|

https://doi.org/10.1107/S2053273324010763

Open

access

Format		BIBTeX
		EndNote
		RefMan
		Refer
		Medline
		CIF
		SGML
		Plain Text
		Text

Format		BIBTeX
		EndNote
		RefMan
		Refer
		Medline
		CIF
		SGML
		Plain Text
		Text

Search IUCr Journals		doi		Advanced search
Author		volume	page

research papers\(\def\hfill{\hskip 5em}\def\hfil{\hskip 3em}\def\eqno#1{\hfil {#1}}\)

Growth functions of periodic space tessellations

1. Introduction

2. Panorama of the ideas

3. Tessellations

3.1. Normal tessellations

3.2. Periodic tessellations

Definition 3.1

3.3. CW structure

Example 3.2

3.4. Vertex notation

4. Growth functions

4.1. Topological/combinatorial approach

Definition 4.1

Example 4.2

4.2. Crystallographic approach

Definition 4.3

4.3. Mantissa equations

Lemma 4.4

Proof

Definition 4.5

Definition 4.6

Lemma 4.7

Proof

Lemma 4.8

Proof

Theorem 4.9

Proof

Theorem 4.10

Proof

Corollary 4.11

Proof

Definition 4.12

5. Topological growth functions of a tiling

Lemma 5.1

Proof

Lemma 5.2

Proof

Lemma 5.3

Proof

Lemma 5.4

Proof

Theorem 5.5

Example 5.6

6. Crystallographic growth functions of a tiling

6.1. Properties of the crystallographic growth functions

6.2. Orphic diagrams

Definition 6.1

Example 6.2

Example 6.3

7. Applications and properties of the growth functions

7.1. Relation to the modified Euler characteristic

7.2. Identification of a tiling using the growth functions

8. Outlook

8.1. Higher dimensions

APPENDIX A

Mathematical glossary

APPENDIX B

Python code and algorithm

B1. Finding the topological growth functions

B2. Finding the crystallographic growth functions

B3. Computer code availability

Acknowledgements

Funding information

References

research papers