Coordination sequences of crystals are of quasi-polynomial type

Nakamura, Y.; Sakamoto, R.; Mase, T.; Nakagawa, J.

doi:10.1107/S2053273320016769

research papers

FOUNDATIONS
ADVANCES

ISSN: 2053-2733

Volume 77| Part 2| March 2021| Pages 138-148

https://doi.org/10.1107/S2053273320016769

Open

access

Coordination sequences of crystals are of quasi-polynomial type

Yusuke Nakamura,^a ^* Ryotaro Sakamoto,^b Takafumi Mase ^a and Junichi Nakagawa ^a

^aGraduate School of Mathematical Sciences, University of Tokyo, 3-8-1, Komaba, Meguro-ku, Tokyo, 153-8914, Japan, and ^bDepartment of Mathematics Faculty of Science and Technology, Keio University, 3-14-1 Hiyoshi, Kohoku-ku, Yokohama, 223-8522, Japan
^*Correspondence e-mail: [email protected]

Edited by P. M. Dominiak, University of Warsaw, Poland (Received 28 September 2020; accepted 28 December 2020; online 18 February 2021)

The coordination sequence of a graph measures how many vertices the graph has at each distance from a fixed vertex and is a generalization of the coordination number. Here it is proved that the coordination sequence of the graph obtained from a crystal is of quasi-polynomial type, as had been postulated by Grosse-Kunstleve et al. [Acta Cryst. (1996), A52, 879–889].

Keywords: coordination sequences; graph theory; Hilbert polynomial; monoid theory.

1. Introduction

For a graph Γ and a fixed vertex v₀ of Γ, and for a non-negative integer n, the coordination sequence s_n is defined as the number of vertices of Γ at distance n from v₀. For example, the first few terms of the coordination sequence of the graph in Fig. 1 are s₀ = 1, s₁ = 4, s₂ = 16, s₃ = 24. That is, the graph has only one point at distance 0 from the origin (by definition), has four vertices at distance 1, and so on. An easy observation shows that in this case we have s_n = 8n ( $[n\geq 2]$ ).

Figure 1
Graph with a $[{\bb Z}^{2}]$ translation symmetry. The number attached to each vertex represents the graph distance from the origin O.

In this paper, we consider a periodic graph Γ in the following sense:

(A) Γ is a (possibly directed) graph with a free $[{\bb Z}^{n}]$ action such that the quotient graph $[\Gamma/{\bb Z}^{n}]$ is finite.

This assumption is motivated from the crystallographic viewpoint. Our main example is a graph obtained by a crystal, i.e. the vertices of Γ are the set of atoms of the crystal, and to each atomic bond connecting two atoms u and v, we associate an edge connecting the vertices u and v. Then, the number s₁ is nothing but the usual coordination number and the coordination sequence (s_n)_n can be thought of as its generalization.

The coordination sequences of periodic graphs are predicted to be of quasi-polynomial type (see Definition 1.2) by Grosse-Kunstleve et al. (1996 ). After that, various mathematical methods to calculate coordination sequences have been developed and they are actually calculated in many specific cases as in the work of Conway & Sloane (1997 ), Eon (2002 , 2012 ), Goodman-Strauss & Sloane (2019 ), O'Keeffe (1995 , 1998 ), Shutov & Maleev (2018 , 2019 , 2020 ).

The purpose of this paper is to give the affirmative answer to the question posed by Grosse-Kunstleve et al. (1996) (see Theorem 2.2 for the more general statement).

Theorem 1.1

The coordination sequence of a graph satisfying the condition (A) is of quasi-polynomial type. In particular, its generating function is rational. Furthermore, it becomes of polynomial type if the quotient graph $[\Gamma/{\bb Z}^{n}]$ has only one vertex.

Here, we recall the definition of functions of quasi-polynomial type.

Definition 1.2

A function $[p:{\bb Z}_{\geq 0}\longrightarrow{\bb Z}]$ is called a quasi-polynomial if there exist an integer $[N\,\gt\,0]$ and polynomials $[p_{0},\ldots,p_{N-1}\in{\bb Q}[X]]$ with the following condition:

(i) For any $[n\in{\bb Z}_{\geq 0}]$ , the equality p(n) = p_i(n) holds if N divides Mathematical equation .

We say that a function $[f:{\bb Z}_{\geq 0}\longrightarrow{\bb Z}]$ is of quasi-polynomial type if there exist an integer $[M\geq 0]$ and a quasi-polynomial $[p:{\bb Z}_{\geq 0}\longrightarrow{\bb Z}]$ such that f(n) = p(n) holds for any integer $[n\geq M]$ . As a special case, we say that f is of polynomial type when N = 1.

The paper is organized as follows: in Section 2, we prove Theorem 1.1 in more general settings (Theorem 2.2). The key ingredient of the proof of Theorem 2.2 is monoid theory in abstract algebra. Readers unfamiliar with monoid theory are advised to read Appendix A first, where we summarize definitions and propositions in monoid theory with typical examples. In Appendix A, we also prove Theorem A12, which is a key to the proof of Theorem 2.2. In Section 3, we explain how to apply Theorem 2.2 to the graph obtained from a crystal, and we give some examples.

2. Coordination sequences of graphs with abelian group action

In this paper, a graph $[\Gamma = (V,E)]$ means a directed simple graph, i.e. V is the set of vertices and $[E\subset V\times V\setminus\{(x,x)\mid x\in V\}]$ is the set of edges. We say that a graph $[\Gamma = (V,E)]$ is finite when both V and E are finite sets.

Remark 2.1

A simple undirected graph can be regarded as a graph in the sense above. In fact, since a simple undirected graph $[\Gamma^{\prime}]$ consists of sets $[V^{\prime}]$ and $[E^{\prime}\subset\{A\subset V^{\prime}\mid\#A = 2\}]$ , we obtain a graph Γ from $[\Gamma^{\prime}]$ by setting $[V = V^{\prime}]$ and $[E = \{(x,y)\in V\times V\mid\{x,y\}\in E^{\prime}\}]$ . Here the symbol #A is employed to denote the cardinality of the set A.

For vertices $[x,y\in V]$ , we denote by $[{\rm dist}(x,y)\in{\bb Z}_{\geq 0}\cup\{\infty\}]$ the length of a shortest directed path in E from x to y. If there is no directed path connecting x and y, then the distance $[{\rm dist}(x,y)]$ is defined as infinite.

Let H be a group. We say that H acts on $[\Gamma = (V,E)]$ when H acts on both V and E and these actions are compatible, i.e. we assume that H acts on V and the action preserves the adjacency. We then obtain the quotient graph $[\Gamma/H: = (V/H,E/H)]$ . We say that an H-action on Γ is free when any element of H, except for the unit, does not fix a vertex. For more detail, we refer the reader to Eon (2012).

Theorem 2.2

Let $[\Gamma = (V,E)]$ be a graph and let $[v_{0}\in V]$ be a vertex. Suppose that an abelian group H acts freely on Γ and its quotient graph $[\Gamma/H]$ is finite. Then the function

$[{\bb Z}_{\geq 0}\longrightarrow{\bb Z}\semi \,\,\,n\mapsto\#\{y\in V\mid \,{\rm dist}(v_{0},y)\leq n\}]$

is of quasi-polynomial type. Hence, its difference

$[{\bb Z}_{\geq 0}\longrightarrow{\bb Z}\semi\,\,\,n\mapsto\#\{y\in V\mid \,{\rm dist}(v_{0},y) = n\}]$

is also of quasi-polynomial type. In particular, their generating functions are rational. Moreover, both the functions are of polynomial type if $[\Gamma/H]$ has only one vertex.

Remark 2.3

It is worth emphasizing that we consider not only an undirected graph, but also a directed graph. Hence Theorem 2.2 can be used for a graph whose edges have a direction. See Example 3.5 for a concrete example.

First, we may assume that there exists an abelian group G such that H is a subgroup of G and $[V\subset G]$ as a set. In fact, since the H-action on V is free, we have a bijective map $[H\times(V/H)\to V]$ and we can identify V = H×(V/H) as sets. Let $[C = {\bb Z}/c{\bb Z}]$ be the cyclic group with order c = #(V/H). Then, we can identify V/H = C as sets, and hence we may take G = H×C = V.

Remark 2.4

We note that if $[H = {\bb Z}^{n}]$ as in Theorem 1.1, then we may also take $[G = {\bb R}^{n}]$ . Indeed, for c = #(V/H), if $[{\bf v}_{1},\ldots,{\bf v}_{c}\in{\bb R}^{n}]$ satisfy $[{\bf v}_{i}-{\bf v}_{j}\not\in{\bb Z}^{n}]$ for any $[i \neq j]$ , then V can be realized as $[V = \bigsqcup_{1\leq i\leq c}({\bf v}_{i}+{\bb Z}^{n})\subset{\bb R}^{n}]$ . Here we use the symbol $[\bigsqcup]$ to denote the disjoint union of sets.

We regard the abelian group G as an additive group, and denote by $[0\in G]$ the identity element of G. For subsets $[A,B\subset G]$ and an element $[\alpha\in G]$ , we put

$[\eqalign{&A+B: = \{a+b\mid a\in A,\ b\in B\}\subset G,\cr &\alpha+A: = \{\alpha+a\mid a\in A \}\subset G.}]$

Since $[V\subset G]$ , we may assume that v₀ = 0 by translation. Since V/H is a finite set, there is a finite subset F of V such that $[0\in F]$ and

$[V = \bigsqcup_{\alpha\in F}(\alpha+H)]$

holds.

Definition 2.5

(1) For any two elements $[\alpha,\beta\in F]$ , we put

$[P_{\alpha,\beta}: = \{\beta+h-\alpha\mid(\alpha,\beta+h)\in E,\ h\in H\}\subset G.]$

Since the map $[P_{\alpha,\beta}\longrightarrow E/H\semi \,x\mapsto[(\alpha,\alpha+x)]]$ is injective, the finiteness of the set E/H implies that the set $[P_{\alpha,\beta}]$ is finite.

(2) For elements $[\alpha_{0},\ldots,\alpha_{m}\in F]$ with $[m\in{\bb Z}_{\geq 0}]$ , we put

$[P(\alpha_{0},\ldots,\alpha_{m}): = P_{\alpha_{0},\alpha_{1}}+P_{ \alpha_{1},\alpha_{2}}+\cdots+P_{\alpha_{m-1},\alpha_{m}}\subset G.]$

By convention, we define $[P(\alpha_{0}) = \{0\}]$ when m = 0. Note that $[P(\alpha_{0},\ldots,\alpha_{m})]$ is also a finite set since each $[P_{\alpha_{i},\alpha_{i+1}}]$ is a finite set.

Remark 2.6

Let $[\alpha,\beta\in F]$ . We say that a vertex $[v\in V]$ is of α-type if there is an element $[h\in H]$ such that $[v = \alpha+h]$ . For an α-type vertex $[v\in V]$ and $[x\in P_{\alpha,\beta}]$ , the vertex v+x is of β-type and $[(v,v+x)\in E]$ . In other words, $[P_{\alpha,\beta}]$ is the set of translations from an α-type vertex v to a β-type vertex connected to v. Therefore, for an $[\alpha_{0}]$ -type vertex $[v\in V]$ and $[x\in P(\alpha_{0},\ldots,\alpha_{m})]$ , the vertex v+x is of $[\alpha_{m}]$ -type and there is a path from v to v+x of length m. For a concrete example of $[P_{\alpha,\beta}]$ and $[P(\alpha_{0},\ldots,\alpha_{m})]$ , we refer the reader to Example 3.3.

Lemma 2.7

For elements $[\alpha_{0},\ldots,\alpha_{m}\in F]$ with $[m\in{\bb Z}_{\geq 0}]$ , it follows that

$[\alpha_{0}+P(\alpha_{0},\ldots,\alpha_{m})\subset\{x\in V\mid\,{\rm dist }(\alpha_{0},x)\leq m\}.]$

Proof

This lemma is obvious by definition (cf. Remark 2.6).

□

For a subset $[S\subset F]$ , we define a monoid M_S as a submonoid of $[{\bb Z}_{\geq 0}\times G]$ . We note that $[{\bb Z}_{\geq 0}\times G]$ admits a monoid structure by regarding $[{\bb Z}_{\geq 0}]$ and G as monoids by their addition [cf. Example A3(3)].

Definition 2.8

Let S be a subset of F. We define $[M_{S}\subset{\bb Z}_{\geq 0}\times G]$ as the submonoid of $[{\bb Z}_{\geq 0}\times G]$ generated by the elements in the set

$[\eqalign{&\Biggl\{(d,x)\in{\bb Z}_{\gt0}\times G\ \Big |\cr &\matrix{ x \in P(\alpha_{0},\alpha_{1},\ldots,\alpha_{m})\, {\rm for\ some}\, \alpha_{0},\ldots,\alpha_{m}\in S\cr {\rm with}\, 0\leq m\leq d \,{\rm and} \,\alpha_{0} = \alpha_{m} \hfill}\Biggr\}.}]$

Note that M_S admits a graded monoid structure by the first projection $[M_{S}\to{\bb Z}_{\geq 0}]$ , i.e. the degree of $[(d,x)\in M_{S}]$ is defined to be d [cf. Definition A9(1)].

Remark 2.9

For a generator (d,x) of M_S, there exists a path

$[y_{0}\to y_{1}\to\cdots\to y_{m-1}\to y_{m}]$

on Γ of length $[m\leq d]$ such that y_i is of $[\alpha_{i}]$ -type for some $[\alpha_{i}\in S]$ , $[\alpha_{0} = \alpha_{m}]$ and $[x = y_{m}-y_{0}]$ . Although the sum of generators is simply defined by the addition of $[{\bb Z}_{\geq 0}\times G]$ , it is not possible in general to interpret the sum as the procedure to connect paths, even if one is allowed to translate each path and to change the order of segments at will. For example, if $[S = \{\alpha_{0},\alpha_{1},\alpha_{2},\alpha_{3}\}]$ , $[x\in P(\alpha_{0},\alpha_{1},\alpha_{0})]$ and $[y\in P(\alpha_{2},\alpha_{3},\alpha_{2})]$ , then x+y does not always correspond to a path on Γ. See Example 3.3 for a concrete example.

Lemma 2.10

For a non-empty subset S of F, the monoid M_S is finitely generated. More precisely, M_S is generated by elements with degree at most #S.

Proof

Take an element $[x\in P(\alpha_{0},\alpha_{1},\ldots,\alpha_{m})]$ for some $[\alpha_{0},\ldots,\alpha_{m}\in S]$ with $[m\,\gt\,\#S]$ and $[\alpha_{0} = \alpha_{m}]$ . Since $[m\,\gt\,\#S]$ , one has $[\alpha_{i} = \alpha_{j}]$ for some $[0\leq i\,\lt\,j\,\lt\,m]$ , and hence

$[\eqalign{x&\in P(\alpha_{0},\alpha_{1},\ldots,\alpha_{i-1},\alpha_{i} = \alpha_{j},\alpha_{j+1},\ldots\alpha_{m})\cr &\quad +P(\alpha_{i},\alpha_{i+1},\ldots, \alpha_{j}).}]$

This fact shows that M_S is generated by elements with degree at most #S. Since there exist only finitely many such elements, M_S is finitely generated.

□

Next, for a subset $[S\subset F]$ and $[\alpha,\beta\in S]$ , we define $[X^{\alpha,\beta}_{S}]$ as a subset of $[{\bb Z}_{\geq 0}\times V]$ , which is proved to be a finitely generated M_S-module in Lemma 2.13.

Definition 2.11

(1) For any two elements $[\alpha,\beta\in F]$ , we define the set $[X^{\alpha,\beta}\subset{\bb Z}_{\geq 0}\times V]$ by

$[\eqalign{&X^{\alpha,\beta}: = \Biggl\{\matrix{(d,\alpha+x)\cr \in{\bb Z}_{\geq 0}\times V}\Big|\cr &\matrix{x\in P(\alpha_{0},\alpha_{1},\ldots,\alpha_{m})\,{\rm for\ some}\, \alpha_{0},\ldots,\alpha_{m}\in F\cr {\rm with}\, 0\leq m\leq d, \alpha_{0} = \alpha, \,{\rm and}\, \alpha_{m} = \beta.\hfill}\Biggr\}.}]$

(2) Let S be a non-empty subset of F and $[\alpha,\beta\in S]$ . We define the set $[X^{\alpha,\beta}_{S}\subset{\bb Z}_{\geq 0}\times V]$ by

$[\eqalign{&X^{\alpha,\beta}_{S}: = \Biggl\{\matrix{(d,\alpha+x)\cr \in{\bb Z}_{\geq 0}\times V}\Big| \cr &\matrix{x\in P(\alpha_{0},\alpha_{1},\ldots,\alpha_{m})\,{\rm with}\, 0\leq m \leq d,\cr \alpha_{0} = \alpha, \alpha_{m} = \beta, \,{\rm and}\, S = \{\alpha_{0},\ldots, \alpha_{m}\}\hfill}\Biggr\}.}]$

(3) For a subset $[Y\subset{\bb Z}_{\geq 0}\times G]$ and $[d\in{\bb Z}_{\geq 0}]$ , we define $[Y_{d}\subset G]$ by

$[Y_{d} = \{x\in G\mid(d,x)\in Y\}.]$

Remark 2.12

(1) By definition, for an element $[(d,y)\in X^{\alpha,\beta}]$ , the vertex y is of β-type and there is a path from α to y of length at most d. In other words, the set $[(X^{\alpha,\beta})_{d}]$ consists of the β-type vertices whose distance from α is less than or equal to d.

(2) If a β-type vertex y is in $[(X^{\alpha,\beta}_{S})_{d}]$ , then we have a special path from α to y, namely, there exists a path

$[\alpha = y_{0}\ \rightarrow\ y_{1}\ \rightarrow\ \cdots\ \rightarrow\ y_{m-1}\ \rightarrow\ y_{m} = y]$

of length $[m\leq d]$ such that y_i is of $[\beta_{i}]$ -type for some $[\beta_{i}\in S]$ and $[\{\beta_{0},\ldots,\beta_{m}\} = S]$ . Note that this special path must visit γ-type vertices at least once for each γ in S, which plays an essential role in the proof of Lemma 2.13. The set $[(X^{\alpha,\beta}_{S})_{d}]$ consists of the β-type vertices with such a special path. See Example 3.3 for a concrete example.

Lemma 2.13

Let S be a non-empty subset of F and let $[\alpha,\beta\in S]$ . Then, $[X_{S}^{\alpha,\beta}]$ is a finitely generated graded M_S-module, where the graded structure of $[X_{S}^{\alpha,\beta}]$ is induced by the first projection $[X_{S}^{\alpha,\beta}\longrightarrow{\bb Z}_{\geq 0}\semi (d,y)\mapsto d]$ .

Proof

First, we shall prove that $[X_{S}^{\alpha,\beta}]$ is a graded M_S-module, i.e. $[(M_{S})_{d}+(X_{S}^{\alpha,\beta})_{d^{\prime}}\subset(X_{S}^{\alpha,\beta})_{ d+d^{\prime}}]$ holds for $[d,d^{\prime}\geq 0]$ [cf. Definition A9(2)]. Since each element of M_S can be written as the sum of generators of the form in Definition 2.8, it is sufficient to show that any generator (d,x) of M_S of the form in Definition 2.8 and any element $[(d^{\prime},\alpha+y)\in X_{S}^{\alpha,\beta}]$ satisfy $[(d+d^{\prime},\alpha+x+y)\in X_{S}^{\alpha,\beta}]$ . Since (d,x) is a generator of the form in Definition 2.8, we have $[x\in P(\alpha_{0},\ldots,\alpha_{m})]$ for some $[\alpha_{0},\ldots,\alpha_{m}\in S]$ with $[0\leq m\leq d]$ and $[\alpha_{0} = \alpha_{m}]$ . Moreover, by the definition of $[X_{S}^{\alpha,\beta}]$ , we have $[y\in P(\alpha^{\prime}_{0},\ldots,\alpha^{\prime}_{m^{\prime}})]$ for some $[\alpha^{\prime}_{0},\ldots,\alpha^{\prime}_{m^{\prime}}\in S]$ with $[0\leq m^{\prime}\leq d^{\prime}]$ satisfying $[\alpha^{\prime}_{0} = \alpha]$ , $[\alpha^{\prime}_{m^{\prime}} = \beta]$ and $[S = \{\alpha^{\prime}_{0},\ldots,\alpha^{\prime}_{m^{\prime}}\}]$ .

Since $[S = \{\alpha^{\prime}_{0},\ldots,\alpha^{\prime}_{m^{\prime}}\}]$ , there exists $[0\leq i\leq m^{\prime}]$ such that $[\alpha_{i}^{\prime} = \alpha_{0} = \alpha_{m}]$ . Then, we obtain

$[\eqalign{y+x&\in P(\alpha^{\prime}_{0},\ldots,\alpha^{\prime}_{m^{\prime}})+P(\alpha_{0},\ldots,\alpha_{m})\cr &\subset P(\alpha^{\prime}_{0},\ldots,\alpha^{\prime}_{i-1},\alpha ^{\prime}_{i} = \alpha_{0},\alpha_{1},\ldots,\cr &\quad\alpha_{m} = \alpha^{\prime}_{i}, \alpha^{\prime}_{i+1},\ldots,\alpha^{\prime}_{m^{\prime}})\cr &\subset(X_{S}^{\alpha,\beta})_{d+d^{\prime}}-\alpha,}]$

which proves $[\alpha+x+y\in(X_{S}^{\alpha,\beta})_{d+d^{\prime}}]$ . Hence, we have $[(M_{S})_{d}+(X_{S}^{\alpha,\beta})_{d^{\prime}}\subset(X_{S}^{\alpha,\beta})_{ d+d^{\prime}}]$ and thus $[X_{S}^{\alpha,\beta}]$ is a graded M_S-module.

Next we shall see that $[X_{S}^{\alpha,\beta}]$ is generated by elements with degree at most $[(\#S)^{2}-1]$ . Let $[\alpha^{\prime}_{0},\ldots,\alpha^{\prime}_{m^{\prime}}\in S]$ be a sequence with $[m^{\prime}\geq(\#S)^{2}]$ , $[\alpha^{\prime}_{0} = \alpha]$ , $[\alpha^{\prime}_{m^{\prime}} = \beta]$ and $[S = \{\alpha^{\prime}_{0},\ldots,\alpha^{\prime}_{m^{\prime}}\}]$ . Since $[m^{\prime}\geq(\#S)^{2}]$ , there exist $[\gamma\in S]$ and a subset $[\Lambda\subset\{0,1,\ldots,m^{\prime}\}]$ such that $[\#\Lambda\,\gt\,\#S]$ and $[\alpha^{\prime}_{i} = \gamma]$ holds for any $[i\in\Lambda]$ .

Here we claim that there exist $[j,j^{\prime}\in\Lambda]$ with $[j\,\lt\,j^{\prime}]$ such that $[\{\alpha^{\prime}_{0},\ldots,\alpha^{\prime}_{j},\alpha^{\prime}_{j^{\prime}+1 },\ldots,\alpha^{\prime}_{m^{\prime}}\} = S]$ .

Let $[c = \#\Lambda]$ and let $[j_{1}\,\lt\,j_{2}\,\lt\,\cdots\,\lt\,j_{c}]$ be the elements of Λ. Since $[S = \{\alpha^{\prime}_{0},\ldots,\alpha^{\prime}_{m^{\prime}}\}]$ , for each $[\delta\in S\setminus\{\gamma\}]$ , we can take $[k_{\delta}]$ with $[1\leq k_{\delta}\leq c-1]$ such that δ appears among

$[\alpha^{\prime}_{j_{k_{\delta}}+1},\ \alpha^{\prime}_{j_{k_{\delta}}+2},\ \ldots, \ \alpha^{\prime}_{j_{k_{\delta}+1}-1}.]$

Since $[c = \#\Lambda\,\gt\,\#S]$ , we can take

$[\ell\in\{1,2,\ldots,c-1\}\setminus\bigl{\{}k_{\delta}\ \big{|}\ \delta\in S \setminus\{\gamma\}\bigr{\}}.]$

Then j: = j_l and $[j^{\prime}: = j_{\ell+1}]$ satisfy the claim.

Then the inclusion

$[P(\alpha^{\prime}_{0},\ldots,\alpha^{\prime}_{m^{\prime}})\subset P(\alpha^{ \prime}_{0},\ldots,\alpha^{\prime}_{j},\alpha^{\prime}_{j^{\prime}+1},\ldots, \alpha^{\prime}_{m^{\prime}})+P(\alpha^{\prime}_{j},\ldots,\alpha^{\prime}_{j^ {\prime}})]$

shows that an element of $[X_{S}^{\alpha,\beta}]$ of degree larger than $[(\#S)^{2}-1]$ can be written by the sum of an element of $[X_{S}^{\alpha,\beta}]$ of lower degree and an element of M_S. Therefore, $[X_{S}^{\alpha,\beta}]$ is generated by elements with degree at most $[(\#S)^{2}-1]$ . Since there exist only finitely many such elements, $[X_{S}^{\alpha,\beta}]$ is finitely generated.

□

Lemma 2.14

Let $[d\geq 0]$ be an integer. Then the following claims are valid.

(1) One has

$[\{x\in V\mid\,{\rm dist}\,(0,x)\leq d\} = \bigsqcup_{\alpha\in F}(X^{0, \alpha})_{d}.]$

(2) For any element $[\alpha\in F]$ , one has

$[(X^{0,\alpha})_{d} = \bigcup_{0,\alpha\in S\subset F}(X_{S}^{0,\alpha})_{d}.]$

Here S runs over the subsets of F containing 0 and α.

Proof

Claim (2) is obvious by definition. We only give a proof of claim (1). The inclusion

$[\{x\in V\mid\,{\rm dist}\,(0,x)\leq d\}\supset\bigsqcup_{\alpha\in F}(X^{ 0,\alpha})_{d}]$

follows from Lemma 2.7. Let us show the opposite inclusion. Take an element $[x\in V]$ with $[m: = {\rm dist}\,(0,x)\leq d]$ . By the definition of the distance, there are edges $[(x_{0},x_{1}),\ldots,(x_{m-1},x_{m})\in E]$ with x₀ = 0 and x_m = x. For each i, the unique element $[\alpha_{i}\in F]$ is determined by $[x_{i}\in\alpha_{i}+H]$ . Then $[x_{i+1}-x_{i}\in P_{\alpha_{i},\alpha_{i+1}}]$ , and so one has

$[x = x_{m} = \textstyle\sum\limits_{i = 0}^{m-1}(x_{i+1}-x_{i})\in P(\alpha_{0},\ldots,\alpha_{m}).]$

Since $[m\leq d]$ , we conclude $[x\in(X^{0,\alpha_{m}})_{d}]$ .

□

Proof of Theorem 2.2

For an element $[\alpha\in F]$ , put $[\Lambda_{\alpha}: = \{S\subset F\mid 0,\alpha\in S\}]$ and write $[{\cal P}(\Lambda_{\alpha})]$ for its power set. Then Lemma 2.14 and the inclusion–exclusion principle imply

$[\eqalign{ & \#\{x\in V\mid\,{\rm dist}\,(0,x)\leq d\} \cr & \quad \quad \quad = \textstyle\sum\limits_{\alpha\in F} \#(X^{0,\alpha})_{d}\cr & \quad \quad \quad = \textstyle\sum\limits_{\alpha\in F}\#\Bigl(\bigcup_{S\in\Lambda_{\alpha}}(X_{S} ^{0,\alpha})_{d}\Bigr)\cr & \quad \quad \quad = \textstyle\sum\limits_{\alpha\in F}\sum_{\Lambda\in{\cal P}(\Lambda_{\alpha})} (-1)^{\#\Lambda+1} \, \#\Bigl(\bigcap_{S\in\Lambda}(X_{S}^{0,\alpha})_{d}\Bigr).}]$

Hence it is enough to show that the function

$[\varphi_{\alpha,\Lambda}:{\bb Z}_{\geq 0}\longrightarrow{\bb Z}\semi \quad d\mapsto\#\bigcap_{S\in\Lambda}(X_{S}^{0,\alpha})_{d}]$

is of quasi-polynomial type.

Lemma 2.10 and Proposition A6(3) show that $[\bigcap_{S\in\Lambda}M_{S}]$ is a finitely generated graded monoid. Furthermore, Lemma 2.13 and Theorem A12 show that $[\bigcap_{S\in\Lambda}X_{S}^{0,\alpha}]$ is a finitely generated graded ( $[\bigcap_{S\in\Lambda}M_{S}]$ )-module. Hence Proposition A11 implies that the function $[\varphi_{\alpha,\Lambda}]$ is of quasi-polynomial type, which completes the proof of the first assertion.

By Lemma 2.10, the monoid M_S is generated by elements of degree one if #S = 1. Therefore if #F = 1, the functions in Theorem 2.2 turn out to be actually of polynomial type, which completes the proof of the second assertion.

□

Remark 2.15

It is natural to ask how to calculate the quasi-polynomials in Theorem 2.2 from the graph Γ in some concrete situations.

By the argument in this section, in order to determine the quasi-polynomials, it is sufficient to determine the Hilbert polynomial of $[\bigcap_{S\in\Lambda}(X_{S}^{0,\alpha})]$ for each Λ. If we know generators of the monoid $[\bigcap_{S\in\Lambda}M_{S}]$ and the module $[\bigcap_{S\in\Lambda}(X_{S}^{0,\alpha})]$ , then the Hilbert polynomial of $[\bigcap_{S\in\Lambda}(X_{S}^{0,\alpha})]$ can be calculated in principle via a free resolution (cf. Bruns & Herzog, 1993 , Lemma 4.1.13), and can be computed by the standard computational commutative algebra packages Singular and Macaulay2. Actually in Example 3.1, Example 3.2 and the face-centered cubic system in Example 3.4, generators of $[\bigcap_{S\in\Lambda}M_{S}]$ and $[\bigcap_{S\in\Lambda}(X_{S}^{0,\alpha})]$ are easily computed. Therefore, in these cases, it is not hard to calculate their Hilbert polynomials from the material in this section. It should be noted, however, that in many cases, even when generators are known, it is easier to calculate their coordination sequences by predicting the region that consists of the vertices with distance at most n and proving it by induction.

Computing generators of $[\bigcap_{S\in\Lambda}M_{S}]$ and $[\bigcap_{S\in\Lambda}(X_{S}^{0,\alpha})]$ is a more difficult problem in general situations. Indeed, Theorem A12 or even its proof does not give a procedure to compute their generators. For example, as we will see later, in the case of Example 3.3, computing generators of $[\bigcap_{S\in\Lambda}M_{S}]$ and $[\bigcap_{S\in\Lambda}(X_{S}^{0,\alpha})]$ by hand is not easy at all, whereas the graph itself looks simple.

3. Examples

In this section, we explain using some examples how to apply Theorem 2.2 to the graph obtained from crystals. In Example 3.3, we see the complicated notations defined in the previous section. It should be noted in advance, however, that although Theorem 2.2 guarantees that the coordination sequence of a crystal is of quasi-polynomial type, it is not practical in general to concretely calculate the whole sequence through the theorem or its proof (see Remark 2.15). Throughout this section, we take G as a Euclidean space so that the reader can easily visualize examples.

Example 3.1

One of the simplest examples of crystal structure is the square tiling. Let $[G = {\bb R}^{2}]$ , $[H = V = {\bb Z}^{2}]$ and let

$[E = \bigl\{({\bf v},{\bf v}\pm{\bf e}_{i})\ \big{|}\ {\bf v}\in V, \,i = 1,2\bigr\},]$

where $[{\bf e}_{1} = (1,0)]$ and $[{\bf e}_{2} = (0,1)]$ . It is obvious that this graph satisfies all the assumptions of Theorem 2.2. An easy observation shows that the coordination sequence of this graph from the origin is $[1,4,8,12,\ldots\,]$ , the general term of which can be written as s₀ = 1, s_n = 4n ( $[n\geq 1]$ ).

Let us briefly look at the notations in the previous section. In this case, the finite set F used in Section 2 consists of the origin O. To be precise, since F = {O}, we have $[P_{O,O} = \{\pm{\bf e}_{1},\pm{\bf e}_{2}\}]$ . Hence, the $[M_{F}\subset{\bb Z}_{\geq 0}\times{\bb Z}^{2}]$ is the graded monoid generated by (1,(0,0)), $[(1,\pm{\bf e}_{1})]$ and $[(1,\pm{\bf e}_{2})]$ , which coincides with the X_F since #F = 1.

In contrast, in the case where F consists of two or more points, calculating the coordination sequence by this procedure is much more complicated as seen in Remark 2.15 and Example 3.3.

Example 3.2

Let $[\Gamma = (V,E)]$ be the graph corresponding to the hexagonal tiling as in Fig. 2. Let $[{\bf v}_{1},{\bf v}_{2},{\bf v}_{3}]$ be the vectors corresponding to the edges from O, respectively. Note that these vectors satisfy $[{\bf v}_{1}+{\bf v}_{2}+{\bf v}_{3} = (0,0)]$ . Let $[G = {\bb R}^{2}]$ and $[H = {\bb Z}(2{\bf v}_{1}+{\bf v}_{2})+{\bb Z}({\bf v}_{1}- {\bf v}_{2})]$ . Then, V and E are H-invariant and the quotient graph $[\Gamma/H]$ is finite. Since $[V = H\sqcup({\bf v}_{1}+H)]$ , we have $[F = \{O,{\bf v}_{1}\}]$ . An easy observation shows that the coordination sequence of this graph is $[1,3,6,9,\ldots\,]$ , the general term of which can be written as s₀ = 1, s_n = 3n ( $[n\geq 1]$ ).

Figure 2
Hexagonal tiling. The number attached to each vertex represents the graph distance from the origin O.

Example 3.3

Let us see the notations used in Section 2 on an example. Let $[G = {\bb R}^{2}]$ and $[H = 2{\bb Z}^{2}]$ . Let

$[V = H\sqcup((1,1)+H)\sqcup((0,1)+H)]$

and let

$[E = \bigl{\{}({\bf v}_{1}+{\bf h},{\bf v}_{2}+{\bf h}),({\bf v}_{ 2}+{\bf h},{\bf v}_{1}+{\bf h})\ \big{|}\ ({\bf v}_{1},{\bf v}_ {2})\in E_{0},{\bf h}\in H\bigr{\}},]$

where

$[\eqalign{E_{0} = & \, \bigl{\{}(O,\pm(1,1)),(O,(1,-1)),(O,(0,-1)),\cr & \, ((-1,-1),(0,-1))\bigr{\}}.}]$

Then, the graph $[\Gamma = (V,E)]$ is as in Fig. 3.

Figure 3
Graph with a $[2 {\bb Z}^{2}]$ -translation symmetry. The number attached to each vertex represents the graph distance from the origin O. The color of each vertex represents the equivalence class in $[\Gamma/H]$ .

The group H acts freely on Γ as translations and the quotient graph $[\Gamma/H]$ has three vertices. The F in Section 2 can be taken as F = {A,B,C}, where A = O, Mathematical equation , . Then, the P_Z,Y for each $[Z,Y\in\{A,B,C\}]$ in Definition 2.5 is

$[\eqalign{ P_{A,A}& = P_{B,B} = P_{C,C} = \emptyset,\cr P_{A,B}& = \bigl{\{}\pm(1,1),(1,-1)\bigr{\}},\, P_{B,A} = \bigl{\{ }\pm(1,1),(-1,1)\bigr{\}},\cr P_{A,C}& = \bigl{\{}(0,-1)\bigr{\}},\, P_{C,A} = \bigl{\{}(0,1) \bigr{\}},\cr P_{B,C}& = \bigl{\{}(1,0)\bigr{\}},\, P_{C,B} = \bigl{\{}(-1,0) \bigr{\}}}]$

and, for example, one can compute

$[\eqalign{ P(A,B,C,B,A)& = P_{A,B}+P_{B,C}+P_{C,B}+P_{B,A}\cr &= \bigl{\{}\pm(1,1),(1,-1)\bigr{\}}+\bigl{\{}(1,0)\bigr{\}}+\bigl{ \{}(-1,0)\bigr{\}}\cr &\quad +\bigl{\{}\pm(1,1),(-1,1)\bigr{\}}\cr &= \bigl{\{}(0,0),\pm(0,2),\pm(2,0),\pm(2,2)\bigr{\}}.}]$

Next, let us see generators of the monoids and the modules in Definition 2.8 and Definition 2.11, respectively. For each subset $[S\subset\{A,B,C\}]$ satisfying $[A\in S]$ , a generator of the monoid M_S can be computed as

$[\eqalign{ M_{\{A\}} &= M_{\{A,C\}} = {\bb Z}_{\geq 0}\bigl{\{}(1,(0,0))\bigr {\}},\cr M_{\{A,B\}}& = M_{\{A,B,C\}} = {\bb Z}_{\geq 0}\bigl{\{}(1,(0,0)), (2,\pm(2,0)),(2,\pm(0,2)),\cr &\qquad\qquad\quad\quad(2,\pm(2,2))\bigr{\}},\cr}]$

i.e. for example, one can take

$[\{(1,(0,0)),(2,\pm(2,0)),(2,\pm(0,2)),(2,\pm(2,2))\}]$

as a generator of the monoid M_{A,B}. For each subset $[S\subset\{A,B,C\}]$ satisfying $[A\in S]$ and for each $[Y\in S]$ , a generator of the M_S-module X_S^A,Y can be taken as

$[\eqalign{ X_{\{A\}}^{A,A}& = M_{\{A\}}+\bigl{\{}(0,(0,0))\bigr{\}},\cr X_{\{A,B\}}^{A,A}& = M_{\{A,B\}}+\bigl{\{}(2,(0,0)),(2,\pm(2,0)),(2, \pm(0,2)),\cr &\quad(2,\pm(2,2))\bigr{\}},\cr X_{\{A,B\}}^{A,B} &= M_{\{A,B\}}+\bigl{\{}(1,\pm(1,1)),(1,(1,-1)) \bigr{\}},\cr X_{\{A,C\}}^{A,A} &= M_{\{A,C\}}+\bigl{\{}(2,(0,0))\bigr{\}},\cr X_{\{A,C\}}^{A,C} &= M_{\{A,C\}}+\bigl{\{}(1,(0,-1))\bigr{\}},\cr X_{\{A,B,C\}}^{A,A}& = M_{\{A,B,C\}}+\bigl{\{}(3,(0,0)),(3,\pm(2,0)),(3,\pm(2,2)),\cr &\quad (4,\pm(0,2))\bigr{\}},\cr X_{\{A,B,C\}}^{A,B}& = M_{\{A,B,C\}}+\bigl{\{}(2,(-1,-1)),(3,(1,\pm 1)),\cr &\quad(4,(3,\pm 1)), (4,(3,3))\bigr{\}},\cr X_{\{A,B,C\}}^{A,C}& = M_{\{A,B,C\}}+\bigl\{(2,(0, -1)),(2,(2,\pm 1)),(3,(0,1)),\cr &\quad (3,(0,-3)),(3,(-2,-1)),(3,(-2,-3))\bigr\}.}]$

For example, X_{A,B,C}^A,B contains Mathematical equation , which corresponds to the path

$[\eqalign{&(0,0)\ \rightarrow\ (-1,-1)\ \rightarrow\ (-2,-2)\ \rightarrow\ (-2,-3)\cr & \rightarrow\ (-3,-3)\rightarrow\ (-4,-2)\ \rightarrow\ (-3,-1)}]$

of length 6. Indeed, Mathematical equation decomposes as

Mathematical equation

where $[(2,(-2,-2)),(2,(0,2))\in M_{\{A,B,C\}}]$ and Mathematical equation is contained in the generator described above.

Using these data, it is possible in principle to calculate the coordination sequence of the graph. The actual calculation is, however, extremely laborious and shall be omitted in this paper. The coordination sequence of this graph is obtained by Wakatsuki (2018 ) as

$[s_{n} = \left\{\matrix{1\hfill &(n = 0),\hfill\cr {{9} \over {2}}n-{{1} \over {2}}&(n\,\gt\,0:\ {\rm odd}),\hfill\cr {{9} \over {2}}n-1&(n\,\gt\,0:\ {\rm even}),}\right.]$

which is not of polynomial type but of quasi-polynomial type.

Note that Γ has another simple realization on $[{\bb R}^{2}]$ as in Fig. 4. Since the coordination sequence depends only on its abstract graph structure, these two graphs have the same coordination sequence. As seen in this example, the choice of a realization of a graph is not relevant to Theorem 1.1.

Figure 4
Another realization of the graph in Fig. 3

. This graph can be obtained by adding vertices and edges to the graph in Fig. 2

. If $[{\bf v}\in V]$ is a vertex of a hexagon, then the graph distance between $[{\bf v}]$ and O is exactly the same as that in Example 3.2

Example 3.4

Let us consider the graphs corresponding to crystal structures of dimension 3. These graphs have such a translation symmetry that the corresponding quotient graph is finite. Therefore, it follows from Theorem 1.1 that the coordination sequences of these graphs are of quasi-polynomial type. It should be stressed that, by definition, any crystal structure of any dimension falls into this category.

Let us consider as an example the graph corresponding to the face-centered cubic system. Let G = $[{\bb R}^{3}]$ , H = V = $[{\bb Z}{\bf e}_{1}+{\bb Z}{\bf e}_{2}+{\bb Z}{{1} \over {2}}({\bf e}_{1}+{\bf e}_{2}+{\bf e}_{3})]$ and

$[E = \left\{\left({\bf v},{\bf v}+{{1} \over {2}}(\pm{\bf e}_{1}\pm{\bf e }_{2}\pm{\bf e}_{3})\right)\,\,\mid\,\,{\bf v}\in V\right\},]$

where $[{\bf e}_{1} = (1,0,0)]$ , $[{\bf e}_{2} = (0,1,0)]$ , $[{\bf e}_{1} = (0,0,1)]$ and the signs in the definition of E are arbitrary. Then, the graph $[\Gamma = (V,E)]$ corresponds to the face-centered cubic system. It is clear by definition that H acts on Γ and the quotient is finite. Note that while the H defined above is the largest translation symmetry of this system, it might be more natural to take $[H = {\bb Z}{\bf e}_{1}+{\bb Z}{\bf e}_{2}+{\bb Z}{\bf e}_{3}]$ when one considers crystal structure. Even in that case, the graph Γ has an H-action and the quotient is finite. As seen in this example, the choice of a unit cell is not relevant to Theorem 1.1.

Example 3.5

We give one of the simplest examples of a periodic directed graph (one should compare this with Example 3.1). Let $[G = {\bb R}^{2}]$ , $[H = V = {\bb Z}^{2}]$ and let

$[E = \{({\bf v},{\bf v}+{\bf e}_{i})\mid{\bf v}\in V,\,i = 1,2\},]$

where $[{\bf e}_{1} = (1,0)]$ and $[{\bf e}_{2} = (0,1)]$ . An easy observation shows that the coordination sequence of this graph from the origin is $[1,2,3,4,\ldots\,]$ , the general term of which can be written as s_n = n+1 ( $[n\geq 0]$ ).

In this case, the finite set F used in Section 2 consists of the origin O. To be precise, since F = {O}, we have $[P_{O,O} = \{{\bf e}_{1},{\bf e}_{2}\}]$ . Hence, the $[M_{F}\subset{\bb Z}_{\geq 0}\times{\bb Z}^{2}]$ is the graded monoid generated by (1,(0,0)), $[(1,{\bf e}_{1})]$ and $[(1,{\bf e}_{2})]$ , which coincides with the X_F since #F = 1.

Example 3.6

We give one of the simplest examples of a periodic graph with H having a torsion. Let $[G = {\bb R}^{2}]$ and $[H_{1} = 2{\bb Z}^{2}]$ . Let

$[V = \{(x,y)\in{\bb Z}^{2}\mid x+y\ {\rm is\ even}\}]$

and let

$[E = \{({\bf v}_{1}+{\bf h},{\bf v}_{2}+{\bf h}),({\bf v}_{2}+ {\bf h},{\bf v}_{1}+{\bf h})\mid({\bf v}_{1},{\bf v}_{2})\in E_ {0},{\bf h}\in H_{1}\},]$

where

$[\eqalign{E_{0} &= \{(O,(0,2)),(O,(2,0)),(O,(1,1)),((1,1),(1,3)),\cr &\quad ((1,1),(3,1))\}.}]$

Then, it is obvious that $[\Gamma = (V,E)]$ and H₁ satisfy all the assumptions of Theorem 2.2. In this case, we have $[V = H_{1}\sqcup((1,1)+H_{1})]$ and #(V/H₁) = 2.

The graph Γ also admits a $[{\bb Z}/2{\bb Z}]$ -action as follows. Let $[{\bb Z}/2{\bb Z} = \{e,\iota\}]$ , where e is the identity element of $[{\bb Z}/2{\bb Z}]$ . We define a $[{\bb Z}/2{\bb Z}]$ -action on V by the map $[\iota:V\longrightarrow V]$ satisfying

$[\iota(x,y) = \left\{\matrix{(x+1,y+1)\hfill&({\rm if}\ x\ {\rm is\ even}),\cr (x-1,y-1)&({\rm if}\ x\ {\rm is\ odd}).\hfill}\right.]$

Then, it is easy to see that the set E of edges is stable under the $[{\bb Z}/2{\bb Z}]$ -action, and that ι commutes with the H₁-action. Therefore the product $[H: = H_{1}\times({\bb Z}/2{\bb Z})]$ acts on Γ. Then, $[\Gamma = (V,E)]$ and H also satisfy all the assumptions of Theorem 2.2, and we have #(V/H) = 1 in this case. Therefore, according to Theorem 2.2, the coordination sequence of this graph should not only be of quasi-polynomial type, but also of polynomial type.

Actually, an easy observation shows that the coordination sequence of this graph from the origin is $[1,5,12,20,28,\ldots\,]$ , the general term of which can be written as s₀ = 1, s₁ = 5, $[s_{n} = 8n-4]$ ( $[n\geq 2]$ ).

4. Conclusion

In this paper, we proved that if a graph Γ has a free $[{\bb Z}^{n}]$ -action such that the quotient $[\Gamma/{\bb Z}^{n}]$ is finite, then the coordination sequence of Γ must be of quasi-polynomial type (Theorem 1.1 and Theorem 2.2). As we mentioned in Example 3.4, Theorem 2.2 can be applied to all crystals, which by definition have such a translation symmetry. It should be noted, however, that except for some simple cases, Theorem 2.2 or even its proof does not give a specific procedure to concretely calculate coordination sequences (Remark 2.15). Establishing a systematic method to calculate coordination sequences from an algebraic perspective is left for a future work. The first step would be to determine the period N and the number M in Definition 1.2. Once that is done, we can determine the quasi-polynomial by just calculating the first $[(\deg(p)+1)N+M-1]$ terms.

APPENDIX A

On finitely generated monoids

In this appendix, we first recall some basic definitions and results on finitely generated monoids [for more detail we refer the reader to Bruns & Gubeladze (2009 )]. Then, we will prove Theorem A12, which plays an essential role in the proof of Theorem 2.2.

A1. Monoids and modules

In this paper, all the monoids considered are commutative, that is, a monoid is a commutative semi-group with the unit element 0, and the operation is written additively.

Definition A1

(1) A monoid is a set M with a binary operation + with the following three conditions:

(i) (a+b)+c = a+(b+c) holds for $[a,b,c\in M]$ .

(ii) a+b = b+a holds for any $[a,b\in M]$ .

(iii) There exists an element $[0\in M]$ such that 0+a = a holds for any $[a\in M]$ .

(2) A monoid M is called integral when it has the cancelation property, i.e. when x+y = x+z implies y = z for all $[x,y,z\in M]$ .

(3) A submonoid of a monoid M is a subset $[N\subset M]$ such that N contains the unit of M and is closed under the additive operation of M.

(4) A map $[f:M\to N]$ between two monoids is called a homomorphism when f(0) = 0 and f(a+b) = f(a)+f(b) hold for any $[a,b\in M]$ .

(5) Let F be a subset of a monoid M. We say that F generates M if $[M = {\bb Z}_{\geq 0}F]$ holds, i.e. any element m can be written by

$[m = n_{1}m_{1}+\cdots+n_{r}m_{r}]$

for some $[r\geq 1]$ , $[n_{i}\in{\bb Z}_{\geq 0}]$ and $[m_{i}\in F]$ . A monoid M is said to be finitely generated when M is generated by a finite subset of M.

(6) For an integral monoid M, we define the group of differences $[M^{\rm gp}]$ by $[M^{\rm gp}: = (M\times M)/\sim]$ with the following relation ∼:

(i) $[(a,b)\sim(c,d)]$ if and only if a+d = b+c.

Note that $[M^{\rm gp}]$ becomes an abelian group by the addition [(a,b)]+[(c,d)] = [(a+c,b+d)]. Furthermore, we may consider M as a submonoid of $[M^{\rm gp}]$ by the injective homomorphism $[M\longrightarrow M^{\rm gp}\semi m\mapsto[(m,0)]]$ .

Remark A2

The notions in (3), (4) and (5) correspond to a subgroup, a group homomorphism and a finitely generated group in group theory, respectively. For a monoid M and a field k, we can associate the monoid ring k[M] (see Bruns & Gubeladze, 2009, p. 51 for detail). Then the finite generation of M is equivalent to the finite generation of k[M] as a k-algebra (cf. Bruns & Gubeladze, 2009, Proposition 2.7).

Example A3

(1) If each element of a monoid M has an inverse, then M is an abelian group. In particular, any abelian group is an integral monoid. All the monoids appearing in Section 2 are submonoids of abelian groups. Hence they are always integral.

(2) The set $[{\bb Z}_{\geq 0}]$ of non-negative integers is a typical example of a monoid that is not a group.

(3) For monoids M and N, their Cartesian product M×N admits a monoid structure by (a,b)+(c,d) = (a+c,b+d) for $[(a,b),(c,d)\in M\times N]$ .

(4) Using the notion of polyhedral convex geometry, we can obtain various non-trivial examples of monoids. A cone C in $[{\bb R}^{n}]$ is the intersection of finitely many linear closed halfspaces (cf. Bruns & Gubeladze, 2009, Definition 1.14). A linear closed halfspace here means a closed halfspace which is defined by a linear function on $[{\bb R}^{n}]$ , i.e. it is a set of the form $[\{(x_{1},\ldots,x_{n})\in{\bb R}^{n}\mid\sum_{i}a_{i}x_{i}\geq 0\}]$ where $[a_{i}\in{\bb R}]$ . Then $[C\cap{\bb Z}^{n}]$ is a submonoid of $[{\bb Z}^{n}]$ .

We say that a cone C is rational if C is the intersection of finitely many linear closed rational halfspaces, i.e. linear closed halfspaces defined by linear functions $[\sum_{i}a_{i}x_{i}]$ with rational coefficients $[a_{i}\in{\bb Q}]$ . In this case, $[C\cap{\bb Z}^{n}]$ is known to be a finitely generated monoid [see Proposition A8(1) below].

For example, if

$[\eqalign{&M_{1}: = \bigl{\{}(a,b)\in{\bb Z}^{2}_{\geq 0}\ \big{|}\ b\leq 2a\bigr{\}},\cr & M_{2}: = \bigl{\{}(a,b)\in{\bb Z}^{2}_{\geq 0}\ \big{|}\ b \leq {\sqrt 2} \, a \bigr\},}]$

M₁ is finitely generated, but M₂ is not. M₁ is actually generated by (1,0), (1,1) and (1,2). Furthermore, we have $[M_{1}^{\rm gp}]$ = $[M_{2}^{\rm gp}]$ = $[{\bb Z}^{2}]$ .

Next we introduce the notation of M-modules. It corresponds to the notation of R-modules for a commutative ring R in ring theory.

Definition A4

Let M be a monoid.

(1) An M-module is a set X equipped with an operation $[M\times X\longrightarrow X]$ , which is written as +, satisfying the following conditions for all $[m_{1},m_{2}\in M]$ and $[x\in X]$ :

(i) (m₁+m₂)+x = m₁+(m₂+x),

(ii) 0+x = x.

(2) Let F be a subset of an M-module X. The module X is said to be generated by F if M+F = X holds, where we set

$[M+F: = \{m+f\mid m\in M,\ f\in F\}\subset X.]$

The module X is said to be finitely generated if some finite subset $[F\subset X]$ generates X.

Example A5

(1) In Section 2, we mainly consider the following situation. M is a submonoid of an abelian group G, and X is a subset of G. Then X is an M-module (by the addition of G) if and only if $[M+X\subset X]$ holds.

(2) Let M be a submonoid of a monoid N. Then N and N-modules can be thought of as M-modules. Suppose that N is finitely generated as an M-module and X is a finitely generated N-module. Then X is finitely generated as an M-module.

We prove this claim below. Since N is finitely generated as an M-module, there exists a finite subset $[F\subset N]$ such that N = M+F. Furthermore, since X is finitely generated as an N-module, there exists a finite set $[E\subset X]$ such that X = N+E. Then we have

Mathematical equation

Since F+E is a finite set, X is finitely generated as an M-module.

(3) A polyhedron P in $[{\bb R}^{n}]$ is the (possibly unbounded) intersection of finitely many affine closed halfspaces (cf. Bruns & Gubeladze, 2009, Definition 1.1). An affine closed halfspace here means a closed halfspace which is defined by an affine function on $[{\bb R}^{n}]$ , i.e. it is a set of the form

$[\{(x_{1},\ldots,x_{n})\in{\bb R}^{n}\mid b+\sum_{i}a_{i}x_{i}\geq 0\}]$

for some $[b,a_{i}\in{\bb R}]$ . Let $[P = H_{1}\cap\cdots\cap H_{c}]$ be a polyhedron, where H_i is an affine halfspace. Then the recession cone $[{\rm rec}(P)]$ of P is defined by

$[{\rm rec}(P): = H_{1}^{\prime}\cap\cdots\cap H_{c}^{\prime},]$

where $[H_{i}^{\prime}]$ denotes the linear closed halfspace parallel to H_i. Then we have $[{\rm rec}(P)+P\subset P]$ since $[{\bf x}+{\bf y}\in H_{i}]$ holds for $[{\bf x}\in H^{\prime}_{i}]$ and $[{\bf y}\in H_{i}]$ for each i. Since $[{\rm rec}(P)+P\subset P]$ , we have

$[({\rm rec}(P)\cap{\bb Z}^{n})+(P\cap{\bb Z}^{n})\subset P\cap {\bb Z}^{n}.]$

Therefore, $[P\cap{\bb Z}^{n}]$ is a $[({\rm rec}(P)\cap{\bb Z}^{n})]$ -module.

We say that a polyhedron $[P = H_{1}\cap\cdots\cap H_{c}]$ is rational if each halfspace H_i is defined by an affine function $[b+\sum_{i}a_{i}x_{i}]$ of rational coefficients $[b,a_{i}\in{\bb Q}]$ . In this case, $[P\cap{\bb Z}^{n}]$ is known to be a finitely generated $[({\rm rec}(P)\cap{\bb Z}^{n})]$ -module [see Proposition A8(2) below].

For example, if

$[\eqalign{ H_{1}:& = \{(x,y)\in{\bb R}^{2}\mid x\geq 1\},\quad H_{2}: = \{(x, y)\in{\bb R}^{2}\mid y\geq 1\},\cr H_{3}:& = \{(x,y)\in {\bb R}^{2}\mid x+y\geq 4\},}]$

then we have

$[\eqalign{ H^{\prime}_{1}: &= \{(x,y)\in{\bb R}^{2}\mid x\geq 0\},\quad H^{ \prime}_{2}: = \{(x,y)\in{\bb R}^{2}\mid y\geq 0\},\cr H^{\prime}_{3}:& = \{(x,y)\in{\bb R}^{2}\mid x+y\geq 0\}.}]$

Therefore we have

$[\eqalign{ P\cap{\bb Z}^{n}& = \{(x,y)\in{\bb Z}^{2}\mid x\geq 1,y\geq 1, x+y\geq 4\},\cr {\rm rec}(P)\cap{\bb Z}^{n} &= \{(x,y)\in{\bb Z}^{2} \mid x\geq 0,y\geq 0\}.}]$

It is easy to see that $[P\cap{\bb Z}^{n}]$ is generated by (1,3), (2,2) and (3,1) as a $[({\rm rec}(P)\cap{\bb Z}^{n})]$ -module.

We list some properties on finite generation.

Proposition A6

(1) (Bruns & Gubeladze, 2009, Proposition 2.8) Let M be a finitely generated monoid and let X be a finitely generated M-module. Then any M-submodule of X is finitely generated as an M-module.

(2) (cf. Ogus, 2018 , ch. I, Theorem 2.1.17.6) Let $[f:M\longrightarrow N]$ be a homomorphism between integral monoids and let $[N^{\prime}\subset N]$ be a submonoid. If M and $[N^{\prime}]$ are finitely generated, then so is $[f^{-1}(N^{\prime})]$ .

(3) (cf. Bruns & Gubeladze, 2009, Corollary 2.11) Let N be an integral monoid and let M₁ and M₂ be submonoids of N. If M₁ and M₂ are finitely generated, then $[M_{1}\cap M_{2}]$ is also a finitely generated monoid.

Remark A7

Via the correspondence between a monoid M and a monoid ring k[M] (cf. Bruns & Gubeladze, 2009, Proposition 2.7), (1) is a corollary of the Hilbert basis theorem in ring theory, which states that a finitely generated k-algebra is Noetherian (cf. Eisenbud, 1995 , ch. I, Section 1.4).

In Ogus (2018, ch. I, Theorem 2.1.17.6), (2) is proved in a more general setting:

(4) Let $[f:M\to N]$ and $[g:P\to N]$ be monoid homomorphisms. If the monoids M and P are finitely generated and N is integral, then their fiber product M×_NP is a finitely generated monoid.

We note that the fiber product is defined as

$[M\times_{N}P: = \{(m,p)\in M\times P\mid f(m) = g(p)\},]$

and it is easy to see that M×_NP is a submonoid of M×P. (2) can be seen as a special case of (4) by setting g as the inclusion map $[N^{\prime}\to N]$ .

We note that in Bruns & Gubeladze (2009, Corollary 2.11), (3) is proved only when $[N = {\bb R}^{n}]$ . In general cases, the assertion follows from (2), applying it to the inclusion map $[M = M_{1}\to N]$ and $[N^{\prime} = M_{2}]$ . We also note that in Bruns & Gubeladze (2009), a monoid M is called affine when M is finitely generated and is isomorphic to a submonoid of $[{\bb Z}^{n}]$ .

If a cone and a polyhedron are rational [see Example A3(4) and Example A5(3)], then their restrictions to $[{\bb Z}^{n}]$ give a finitely generated monoid M and a finitely generated M-module. In (3), we denote by $[{\bb R}_{\geq 0}M]$ the cone which consists of the elements of the form $[\sum_{i = 1}^{c}r_{i}m_{i}\in{\bb R}^{n}]$ with $[c\in{\bb Z}_{\gt\,0}]$ , $[r_{i}\in{\bb R}_{\geq 0}]$ and $[m_{i}\in M]$ .

Proposition A8

(1) (Bruns & Gubeladze, 2009, Lemma 2.9) For a rational cone $[C\subset{\bb R}^{n}]$ , the monoid $[C\cap{\bb Z}^{n}]$ is finitely generated.

(2) (Bruns & Gubeladze, 2009, Theorem 2.12) For a rational polyhedron $[P\subset{\bb R}^{n}]$ , the set $[P\cap{\bb Z}^{n}]$ is a finitely generated ( $[{\rm rec}(P)\cap{\bb Z}^{n}]$ )-module.

(3) (Bruns & Gubeladze, 2009, Corollary 2.10) If M is a finitely generated submonoid of $[{\bb Z}^{n}]$ , then the monoid $[{\bb R}_{\geq 0}M\cap{\bb Z}^{n}]$ is finitely generated as an M-module.

(4) [Bruns & Gubeladze, 2009, Proof of Corollary 2.11(a)] If M and N are submonoids of $[{\bb Z}^{n}]$ , then $[{\bb R}_{\geq 0}M\cap{\bb R}_{\geq 0}N]$ = $[{\bb R}_{\geq 0}(M\cap N)]$ holds.

In the rest of this section, we summarize the fact on the Hilbert function of graded monoids.

Definition A9

(1) A (positively) graded monoid is a monoid M equipped with a monoid homomorphism $[\deg:M\to{\bb Z}_{\geq 0}]$ . We say that $[m\in M]$ is of degree i if deg(m) = i. Furthermore, we write $[M_{i}: = \{m\in M\mid\deg(m) = i\}]$ .

(2) Let M be a graded monoid. A graded M-module is an M-module X equipped with a map $[\deg:X\to{\bb Z}]$ with the condition $[M_{i}+X_{j}\subset X_{i+j}]$ for all $[i\geq 0]$ and $[j\in{\bb Z}]$ , where we set $[X_{i}: = \{m\in X\mid\deg(m) = i\}]$ . This condition is equivalent to saying that deg(m)+deg(x) = deg(m+x) holds for any $[m\in M]$ and $[x\in X]$ .

Definition A10

Let M be a graded monoid and X a graded M-module with $[\#X_{n}\,\lt\,\infty]$ for any $[n\geq 0]$ . The function

$[H(X,-):{\bb Z}_{\geq 0}\longrightarrow{\bb Z}_{\geq 0}\semi \quad n \mapsto\#X_{n}]$

is called the Hilbert function associated with X. Its generating function

$[H_{X}(t): = \textstyle\sum\limits_{n = 0}^{\infty}H(X,n)t^{n}\in{\bb Z}[[t]]]$

is called the Hilbert series of X. The Hilbert function and the Hilbert series depend on the grading of M and X.

Proposition A11

(Bruns & Gubeladze, 2009, Theorems 6.38 and 6.39; Bruns & Herzog, 1993, Theorem 4.1.3, Proposition 4.4.1, Theorem 4.4.3) Let M be a graded monoid which is generated by finitely many elements of positive degree. Let X be a finitely generated graded M-module. Then the Hilbert series H_X(t) is a rational function, and the Hilbert function Mathematical equation is of quasi-polynomial type. Moreover, if M is generated by elements of degree one, then is of polynomial type.

We note that the assumption $[\#X_{n}\,\lt\,\infty]$ in Definition A10 is satisfied under the assumption of Proposition A11.

A2. Finite generation of modules

The following theorem is the main theorem in this appendix.

Theorem A12

Let M₁ and M₂ be finitely generated submonoids of an integral monoid M and let $[X_{i}\subset M]$ be a finitely generated M_i-submodule for i = 1,2. Then the $[(M_{1}\cap M_{2})]$ -module $[X_{1}\cap X_{2}]$ is finitely generated.

Proof

Since X_i is a finitely generated M_i-module, there is a finite subset F_i of X_i such that M_i+F_i = X_i, and so one has

$[X_{1}\cap X_{2} = \bigcup_{f_{1}\in F_{1},\ f_{2}\in F_{2}}(f_{1}+M_{1})\cap(f_{ 2}+M_{2}).]$

Hence by replacing X_i with f_i+M_i, we may assume that X_i is the form of X_i = f_i+M_i for each i = 1,2. Next, replacing M with $[M^{\rm gp}]$ , we may assume that M is an abelian group. Furthermore, replacing M with the monoid generated by $[\pm f_{1},\pm f_{2}]$ and the elements of $[\pm M_{1},\pm M_{2}]$ , we may assume that M is finitely generated as a monoid. Let $[h_{1},\ldots,h_{n}]$ be a generator of M. Then, one can take a surjective homomorphism:

$[\varphi:{\bb Z}^{n}_{\geq 0}\longrightarrow M\semi \quad(m_{1},m_{2},\ldots, m_{n})\mapsto\textstyle\sum\limits_{i}m_{i}h_{i}.]$

Then, the monoid $[\varphi^{-1}(M_{i})]$ is finitely generated by Proposition A6(2). Take an element $[\beta_{i}\in{\bb Z}^{n}_{\geq 0}]$ satisfying $[\varphi(\beta_{i}) = -f_{i}]$ . Since X_i = f_i+M_i, we have

$[\beta_{i}+\varphi^{-1}(X_{i})\subset\varphi^{-1}(M_{i}).]$

Hence Proposition A6(1) shows that the $[\varphi^{-1}(M_{i})]$ -module $[\beta_{i}+\varphi^{-1}(X_{i})]$ is finitely generated, and hence its translation $[\varphi^{-1}(X_{i})]$ is also a finitely generated $[\varphi^{-1}(M_{i})]$ -module. Moreover, we have

$[\varphi(\varphi^{-1}(M_{1}\cap M_{2})) = M_{1}\cap M_{2}\,{\rm and }\, \varphi(\varphi^{-1}(X_{1}\cap X_{2})) = X_{1}\cap X_{2}]$

since φ is surjective. Thus, in order to prove that $[X_{1}\cap X_{2}]$ is finitely generated as a $[(M_{1}\cap M_{2})]$ -module, it is sufficient to show that $[\varphi^{-1}(X_{1}\cap X_{2})]$ is finitely generated as a $[\varphi^{-1}(M_{1}\cap M_{2})]$ -module. Since we have

$[\eqalign{&\varphi^{-1}(M_{1}\cap M_{2}) = \varphi^{-1}(M_{1})\cap\varphi^{-1}(M_{2}),\cr & \varphi^{-1}(X_{1}\cap X_{2}) = \varphi^{-1}(X_{1})\cap\varphi^{-1}(X_{2}),}]$

the proof is completed if we show the theorem in the case of $[M = {\bb Z}^{n}_{\geq 0}]$ .

The set $[f_{i}+{\bb R}_{\geq 0}M_{i}]$ is a rational polyhedron satisfying $[{\rm rec}(f_{i}+ {\bb R}_{\geq 0}M_{i}) = {\bb R}_{\geq 0}M_{i}]$ . Proposition A8(2) implies that the set

$[Y: = (f_{1}+{\bb R}_{\geq 0}M_{1})\cap(f_{2}+{\bb R}_{\geq 0}M_{2})\cap {\bb Z}^{n}]$

is a finitely generated $[({\bb R}_{\geq 0}M_{1}\cap{\bb R}_{\geq 0}M_{2}\cap{\bb Z}^{n})]$ -module. Since M₁ and M₂ are finitely generated monoids, so is the monoid $[M_{1}\cap M_{2}]$ by Proposition A6(3). Furthermore,

$[{\bb R}_{\geq 0}M_{1}\cap{\bb R}_{\geq 0}M_{2}\cap{\bb Z}^{n} = {\bb R}_{\geq 0}(M_{1}\cap M_{2})\cap{\bb Z}^{n}]$

holds by Proposition A8(4), and it is a finitely generated $[(M_{1}\cap M_{2})]$ -module by Proposition A8(3). Hence Y is a finitely generated $[(M_{1}\cap M_{2})]$ -module [cf. Example A5(2)]. Since $[X_{1}\cap X_{2}\subset Y]$ is an $[(M_{1}\cap M_{2})]$ -submodule, it is a finitely generated $[(M_{1}\cap M_{2})]$ -module by Proposition A6(1), which completes the proof.

□

Acknowledgements

We thank Professors Atsushi Ito, Masanori Kobayashi, Ryoko Oishi-Tomiyasu and Motoko Kato for many discussions. We also thank the referees, whose comments and suggestions have greatly improved the article.

Funding information

This work was supported by the Program for Leading Graduate Schools, MEXT, Japan. The first two authors are partially supported by the Grant-in-Aid for Young Scientists (KAKENHI No. 18K13438 and No. 18K13384, respectively).

References

Bruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer. Google Scholar
Bruns, W. & Herzog, J. (1993). Cohen–Macaulay Rings. Cambridge Studies in Advanced Mathematics, Vol. 39. Cambridge University Press. Google Scholar
Conway, J. & Sloane, N. (1997). Proc. R. Soc. London A, 453, 2369–2389. CrossRef Google Scholar
Eisenbud, D. (1995). Commutative Algebra. Graduate Texts in Mathematics, Vol. 150. New York: Springer-Verlag. Google Scholar
Eon, J.-G. (2002). Acta Cryst. A58, 47–53. Web of Science CrossRef CAS IUCr Journals Google Scholar
Eon, J. (2012). Struct. Chem. 23, 987–996. CrossRef CAS Google Scholar
Goodman-Strauss, C. & Sloane, N. J. A. (2019). Acta Cryst. A75, 121–134. Web of Science CrossRef IUCr Journals 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
Ogus, A. (2018). Lectures on Logarithmic Algebraic Geometry. Cambridge Studies in Advanced Mathematics, Vol. 178. Cambridge University Press. Google Scholar
O'Keeffe, M. (1995). Z. Kristallogr. 210, 905–908. CAS Google Scholar
O'Keeffe, M. (1998). Z. Kristallogr. 213, 135–140. CAS Google Scholar
Shutov, A. & Maleev, A. (2018). Acta Cryst. A74, 112–122. Web of Science CrossRef IUCr Journals Google Scholar
Shutov, A. & Maleev, A. (2019). Z. Kristallogr. 234, 291–299. CrossRef CAS Google Scholar
Shutov, A. & Maleev, A. (2020). Z. Kristallogr. 235, 157–166. CrossRef CAS Google Scholar
Wakatsuki, S. (2018). Suurikagaku Jissenkenkyu Letter, LMSR 2018-21. 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 77| Part 2| March 2021| Pages 138-148

https://doi.org/10.1107/S2053273320016769

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}}\)

Coordination sequences of crystals are of quasi-polynomial type

1. Introduction

Theorem 1.1

Definition 1.2

2. Coordination sequences of graphs with abelian group action

Remark 2.1

Theorem 2.2

Remark 2.3

Remark 2.4

Definition 2.5

Remark 2.6

Lemma 2.7

Proof

Definition 2.8

Remark 2.9

Lemma 2.10

Proof

Definition 2.11

Remark 2.12

Lemma 2.13

Proof

Lemma 2.14

Proof

Proof of Theorem 2.2

Remark 2.15

3. Examples

Example 3.1

Example 3.2

Example 3.3

Example 3.4

Example 3.5

Example 3.6

4. Conclusion

APPENDIX A

On finitely generated monoids

A1. Monoids and modules

Definition A1

Remark A2

Example A3

Definition A4

Example A5

Proposition A6

Remark A7

Proposition A8

Definition A9

Definition A10

Proposition A11

A2. Finite generation of modules

Theorem A12

Proof

Acknowledgements

Funding information

References

research papers