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

Journal logoFOUNDATIONS
ADVANCES
ISSN: 2053-2733

Coordination sequences of crystals are of quasi-polynomial type

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: nakamura@ms.u-tokyo.ac.jp

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].

1. Introduction

For a graph Γ and a fixed vertex v0 of Γ, and for a non-negative integer n, the coordination sequence sn is defined as the number of vertices of Γ at distance n from v0. For example, the first few terms of the coordination sequence of the graph in Fig. 1[link] are s0 = 1, s1 = 4, s2 = 16, s3 = 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 sn = 8n ([n\geq 2]).

[Figure 1]
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 s1 is nothing but the usual coordination number and the coordination sequence (sn)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[link]) by Grosse-Kunstleve et al. (1996[Grosse-Kunstleve, R. W., Brunner, G. O. & Sloane, N. J. A. (1996). Acta Cryst. A52, 879-889.]). 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[Conway, J. & Sloane, N. (1997). Proc. R. Soc. London A, 453, 2369-2389.]), Eon (2002[Eon, J.-G. (2002). Acta Cryst. A58, 47-53.], 2012[Eon, J. (2012). Struct. Chem. 23, 987-996.]), Goodman-Strauss & Sloane (2019[Goodman-Strauss, C. & Sloane, N. J. A. (2019). Acta Cryst. A75, 121-134.]), O'Keeffe (1995[O'Keeffe, M. (1995). Z. Kristallogr. 210, 905-908.], 1998[O'Keeffe, M. (1998). Z. Kristallogr. 213, 135-140.]), Shutov & Maleev (2018[Shutov, A. & Maleev, A. (2018). Acta Cryst. A74, 112-122.], 2019[Shutov, A. & Maleev, A. (2019). Z. Kristallogr. 234, 291-299.], 2020[Shutov, A. & Maleev, A. (2020). Z. Kristallogr. 235, 157-166.]).

The purpose of this paper is to give the affirmative answer to the question posed by Grosse-Kunstleve et al. (1996[Grosse-Kunstleve, R. W., Brunner, G. O. & Sloane, N. J. A. (1996). Acta Cryst. A52, 879-889.]) (see Theorem 2.2[link] 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) = pi(n) holds if N divides [n-i].

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[link], we prove Theorem 1.1[link] in more general settings (Theorem 2.2[link]). The key ingredient of the proof of Theorem 2.2[link] is monoid theory in abstract algebra. Readers unfamiliar with monoid theory are advised to read Appendix A[link] first, where we summarize definitions and propositions in monoid theory with typical examples. In Appendix A[link], we also prove Theorem A12[link], which is a key to the proof of Theorem 2.2[link]. In Section 3[link], we explain how to apply Theorem 2.2[link] 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[Eon, J. (2012). Struct. Chem. 23, 987-996.]).

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[link] can be used for a graph whose edges have a direction. See Example 3.5[link] 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[link], 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 v0 = 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 trans­lations 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[link].

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[link]).

For a subset [S\subset F], we define a monoid MS 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)[link]].

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 MS 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)[link]].

Remark 2.9

For a generator (d,x) of MS, 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 yi 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[link] for a concrete example.

Lemma 2.10

For a non-empty subset S of F, the monoid MS is finitely generated. More precisely, MS 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 MS is generated by elements with degree at most #S. Since there exist only finitely many such elements, MS 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 MS-module in Lemma 2.13[link].

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 yi 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[link]. The set [(X^{\alpha,\beta}_{S})_{d}] consists of the β-type vertices with such a special path. See Example 3.3[link] 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 MS-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 MS-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)[link]]. Since each element of MS can be written as the sum of generators of the form in Definition 2.8[link], it is sufficient to show that any generator (d,x) of MS of the form in Definition 2.8[link] 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[link], 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 MS-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: = jl 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 MS. 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[link]. 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 x0 = 0 and xm = 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[link]

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[link] 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[link] and Proposition A6(3)[link] show that [\bigcap_{S\in\Lambda}M_{S}] is a finitely generated graded monoid. Furthermore, Lemma 2.13[link] and Theorem A12[link] 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[link] implies that the function [\varphi_{\alpha,\Lambda}] is of quasi-polynomial type, which completes the proof of the first assertion.

By Lemma 2.10[link], the monoid MS is generated by elements of degree one if #S = 1. Therefore if #F = 1, the functions in Theorem 2.2[link] 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[link] 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[Bruns, W. & Herzog, J. (1993). Cohen-Macaulay Rings. Cambridge Studies in Advanced Mathematics, Vol. 39. Cambridge University Press.], Lemma 4.1.13), and can be computed by the standard computational commutative algebra packages Singular and Macaulay2. Actually in Example 3.1[link], Example 3.2[link] and the face-centered cubic system in Example 3.4[link], 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[link] 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[link], 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[link] to the graph obtained from crystals. In Example 3.3[link], we see the complicated notations defined in the previous section. It should be noted in advance, however, that although Theorem 2.2[link] 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[link]). 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[link]. 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 s0 = 1, sn = 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[link] 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 XF 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[link] and Example 3.3[link].

Example 3.2

Let [\Gamma = (V,E)] be the graph corresponding to the hexagonal tiling as in Fig. 2[link]. 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 s0 = 1, sn = 3n ([n\geq 1]).

[Figure 2]
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[link] 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[link].

[Figure 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[link] can be taken as F = {A,B,C}, where A = O, [B = (-1,-1)], [C = (0,-1)]. Then, the PZ,Y for each [Z,Y\in\{A,B,C\}] in Definition 2.5[link] 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[link] and Definition 2.11[link], respectively. For each subset [S\subset\{A,B,C\}] satisfying [A\in S], a generator of the monoid MS 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 MS-module XSA,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 [(6,(-3,-1))], 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, [(6,(-3,-1))] decomposes as

[(6,(-3,-1)) = (2,(-2,-2))+(2,(-1,-1))+(2,(0,2)),]

where [(2,(-2,-2)),(2,(0,2))\in M_{\{A,B,C\}}] and [(2,(-1,-1))] 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[Wakatsuki, S. (2018). Suurikagaku Jissenkenkyu Letter, LMSR 2018-21.]) 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[link]. 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[link].

[Figure 4]
Figure 4
Another realization of the graph in Fig. 3[link]. This graph can be obtained by adding vertices and edges to the graph in Fig. 2[link]. 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[link].

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[link] 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[link].

Example 3.5

We give one of the simplest examples of a periodic directed graph (one should compare this with Example 3.1[link]). 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 sn = n+1 ([n\geq 0]).

In this case, the finite set F used in Section 2[link] 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 XF 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 H1 satisfy all the assumptions of Theorem 2.2[link]. In this case, we have [V = H_{1}\sqcup((1,1)+H_{1})] and #(V/H1) = 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 H1-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[link], and we have #(V/H) = 1 in this case. Therefore, according to Theorem 2.2[link], 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 s0 = 1, s1 = 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[link] and Theorem 2.2[link]). As we mentioned in Example 3.4[link], Theorem 2.2[link] 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[link] or even its proof does not give a specific procedure to concretely calculate coordination sequences (Remark 2.15[link]). 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[link]. 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[Bruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer.])]. Then, we will prove Theorem A12[link], which plays an essential role in the proof of Theorem 2.2[link].

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[Bruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer.], 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[Bruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer.], 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[link] 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[Bruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer.], 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)[link] 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\},}]

M1 is finitely generated, but M2 is not. M1 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) (m1+m2)+x = m1+(m2+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[link], 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

[X = (M+F)+E = M+(F+E).]

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[Bruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer.], 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 Hi 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 Hi. 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 Hi 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)[link] 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[Bruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer.], 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[Ogus, A. (2018). Lectures on Logarithmic Algebraic Geometry. Cambridge Studies in Advanced Mathematics, Vol. 178. Cambridge University Press.], 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[Bruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer.], Corollary 2.11) Let N be an integral monoid and let M1 and M2 be submonoids of N. If M1 and M2 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[Bruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer.], 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[Eisenbud, D. (1995). Commutative Algebra. Graduate Texts in Mathematics, Vol. 150. New York: Springer-Verlag.], ch. I, Section 1.4).

In Ogus (2018[Ogus, A. (2018). Lectures on Logarithmic Algebraic Geometry. Cambridge Studies in Advanced Mathematics, Vol. 178. Cambridge University Press.], 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[Bruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer.], 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[Bruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer.]), 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)[link] and Example A5(3)[link]], 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[Bruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer.], 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[Bruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer.], 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[Bruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer.], 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[Bruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer.], 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[Bruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer.], Theorems 6.38 and 6.39; Bruns & Herzog, 1993[Bruns, W. & Herzog, J. (1993). Cohen-Macaulay Rings. Cambridge Studies in Advanced Mathematics, Vol. 39. Cambridge University Press.], 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 HX(t) is a rational function, and the Hilbert function [H(X,-)] is of quasi-polynomial type. Moreover, if M is generated by elements of degree one, then [H(X,-)] is of polynomial type.

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

A2. Finite generation of modules

The following theorem is the main theorem in this appendix.

Theorem A12

Let M1 and M2 be finitely generated sub­monoids of an integral monoid M and let [X_{i}\subset M] be a finitely generated Mi-submodule for i = 1,2. Then the [(M_{1}\cap M_{2})]-module [X_{1}\cap X_{2}] is finitely generated.

Proof

Since Xi is a finitely generated Mi-module, there is a finite subset Fi of Xi such that Mi+Fi = Xi, 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 Xi with fi+Mi, we may assume that Xi is the form of Xi = fi+Mi 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)[link]. Take an element [\beta_{i}\in{\bb Z}^{n}_{\geq 0}] satisfying [\varphi(\beta_{i}) = -f_{i}]. Since Xi = fi+Mi, we have

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

Hence Proposition A6(1)[link] 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)[link] 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 M1 and M2 are finitely generated monoids, so is the monoid [M_{1}\cap M_{2}] by Proposition A6(3)[link]. 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)[link], and it is a finitely generated [(M_{1}\cap M_{2})]-module by Proposition A8(3)[link]. Hence Y is a finitely generated [(M_{1}\cap M_{2})]-module [cf. Example A5(2)[link]]. 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)[link], 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

First citationBruns, W. & Gubeladze, J. (2009). Polytopes, Rings, and K-theory. Springer Monographs in Mathematics. Dordrecht: Springer.  Google Scholar
First citationBruns, W. & Herzog, J. (1993). Cohen–Macaulay Rings. Cambridge Studies in Advanced Mathematics, Vol. 39. Cambridge University Press.  Google Scholar
First citationConway, J. & Sloane, N. (1997). Proc. R. Soc. London A, 453, 2369–2389.  CrossRef Google Scholar
First citationEisenbud, D. (1995). Commutative Algebra. Graduate Texts in Mathematics, Vol. 150. New York: Springer-Verlag.  Google Scholar
First citationEon, J.-G. (2002). Acta Cryst. A58, 47–53.  Web of Science CrossRef CAS IUCr Journals Google Scholar
First citationEon, J. (2012). Struct. Chem. 23, 987–996.  CrossRef CAS Google Scholar
First citationGoodman-Strauss, C. & Sloane, N. J. A. (2019). Acta Cryst. A75, 121–134.  Web of Science CrossRef IUCr Journals Google Scholar
First citationGrosse-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
First citationOgus, A. (2018). Lectures on Logarithmic Algebraic Geometry. Cambridge Studies in Advanced Mathematics, Vol. 178. Cambridge University Press.  Google Scholar
First citationO'Keeffe, M. (1995). Z. Kristallogr. 210, 905–908.  CAS Google Scholar
First citationO'Keeffe, M. (1998). Z. Kristallogr. 213, 135–140.  CAS Google Scholar
First citationShutov, A. & Maleev, A. (2018). Acta Cryst. A74, 112–122.  Web of Science CrossRef IUCr Journals Google Scholar
First citationShutov, A. & Maleev, A. (2019). Z. Kristallogr. 234, 291–299.  CrossRef CAS Google Scholar
First citationShutov, A. & Maleev, A. (2020). Z. Kristallogr. 235, 157–166.  CrossRef CAS Google Scholar
First citationWakatsuki, 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.

Journal logoFOUNDATIONS
ADVANCES
ISSN: 2053-2733
Follow Acta Cryst. A
Sign up for e-alerts
Follow Acta Cryst. on Twitter
Follow us on facebook
Sign up for RSS feeds