# Ruelle zeta functions for finite dynamical systems and Koyama-Nakajima's l-functions.

1. Introduction. Koyama and Nakajima [KN] introduce a class of L-functions associated with complex reflections, a genreralization of the Artin-Mazur zeta functions for finite dynamical systems. They define the L-functions in the form of Euler product, and give a simple determinant expression. Let [sigma] be an element of the symmetric group [S.sub.n] acting on a set X = {1,2, ... ,n} of n points. The pair (X, [sigma]) forms a finite discrete dynamical system. Let m be a positive integer. An m-periodic point is an element x [member of] X satisfying [[sigma].sup.m](x) = x. The set of m-periodic points is denoted by Fix([[sigma].sup.m]), and [N.sub.m] denotes the cardinality of Fix([[sigma].sup.m]). Let u be an indeterminate. Then the formal power series

exp ([summation over (m[greater than or equal to]1)] [N.sub.m]/m [u.sup.m])

is called the Artin-Mazur zeta function ([AM]; see also [Y]) associated with (X, [sigma]), or simply a, denoted by [Z.sup.AM.sub.(X,[sigma])] (u), or simply [Z.sub.[sigma]](u). For any permutation a, the Artin-Mazur zeta function [Z.sub.[sigma]] (u) always has an Euler product and a determinant expression. Let [sigma] = [p.sub.1] [p.sub.2] ... pr be the cyclic decomposition of [sigma], and let Cyc ([sigma]) = {[p.sub.1],[p.sub.2], ... ,[p.sub.r]}. One can easily show that the Euler product of [Z.sup.AM.sub.[sigma]] (u) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where l(p) denotes the number of elements in the cyclic domain of p. Let [M.sub.[sigma]] = ([[delta].sub.[sigma](i)j])ij=1,2, ... ,n] be the permutation matrix representing [sigma], where [delta] denotes the Kronecker delta. It is known that [Z.sup.AM.sub.[sigma]] (u) has the determinant expression

1/det(I--u[M.sub.[sigma]])

where I stands for the identity matrix.

Zeta functions that arise from combinatorial settings are called combinatorial zeta functions. In [MS], we observe that combinatorial zeta functions whose determinant expressions are of the form 1/det(I-A) should be constructed as Ruelle zeta functions [R] for essentially finite dynamical systems defined for finite digraphs. Koyama and Nakajima [KN] introduce their L-functions by Euler product, and show that its determinant formula is of the form 1/det(I-uM) for a square matrix M. Hence their L-functions should be expressed as Ruelle zeta functions.

Note that, if the components of M are commutative, then it is well known that 1/det(I-uM) equals

exp ([summation over (m [greater than or equal to] 1)] tr [M.sup.m]/m [u.sup.m])

where tr X denotes the trace of a square matrix X. Thus, one can always reformulate 1/det(I-uM) into the generating function. So the problem treated in the present article lies in constructing a dynamical system which characterizes tr [M.sup.m] in terms of its m-periodic points.

In the sequel, [absolute value of X] denotes the cardinality of a set X, Z the set of integers, [Z.sub.P] the set of integers satisfying a property P, and R a commutative Q-algebra with an identity element 1. For each n [member of] [Z.sub.[greater than or equal to]1], [n] denotes the finite set {1,2, ... ,n}.

2. L-functions. The symmetric group [S.sub.n] of the set [n] acts on the direct product [(Z/rZ).sup.n] of n copies of the cyclic group Z/rZ of order [tau] [member of] [Z.sub.[greater than or equal to]1]. An element [tau] of the semi-direct product G(r, n) = [(Z/rZ).sup.n] [??] [S.sub.n] is called a complex reflection. Thus there exists a unique [sigma] [member of] [S.sup.n] and a unique sequence ([s.sub.1], ..., [s.sub.n]) of nonnegative integers smaller than r, satisfying [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [xi] is a primitive r-th root of unity. Let Dom (p) denote the cyclic domain for a cyclic permutation p [member of] Cyc ([sigma]). [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Definition 1. Let [tau] [member of] G(r,n) and u an indeterminate. Then Koyama-Nakajima's L-function [L.sub.[tau]] (u) is defined by the Euler product

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For example, if [tau] = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then Cyc([sigma]) = {(123), (45)}, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Note that if r = 1 then [L.sub.[tau]] (u) is nothing but the Artin-Mazur zeta function [Z.sup.AM.sub.[sigma]] (u). A complex reflection [tau] [member of] G(r, n) is associated with a square matrix

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For example, the matrix [M.sub.[tau]] representing [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (123)(45) is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If r = 1, then [M.sub.[tau]] coincides with the permutation matrix [M.sub.[sigma]] corresponding to the permutation [sigma] [member of] [S.sub.n].

Let [tau] [member of] G(r, n). Koyama and Nakajima [KN] show that the L-function [L.sub.[tau]] (u) has the determinant expression

1/det(I--u[M.sub.[tau]])

If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (123)(45), then one can easily confirm the identity by direct caluculation. Note that, as is mentioned in Introduction, for a square matrix A whose components lie in a commutative ring R, the form 1/det(1-uA) can always be reformulated in a generating function of exponential type, that is, if we let [N.sub.m] = tr [A.sup.m] for each m [member of] [Z.sub.[greater than or equal to]1], then the form equals

exp ([summation over (m [greater than or equal to] 1)] [N.sup.m]/m [u.sup.m]

If one wants to show this, through the argument in the algebraic closure of R, then it is enough to consider the case where A is upper-triangular, and takes logarithm of both sides for the identity. It is, however, not trivial that the quantities [N.sub.m] have an interpretation in terms of dynamical systems, as in the case of Artin-Mazur zeta function.

3. Dynamical systems. Let [sigma] [member of] [S.sub.n], and X = [n]. Then we have a finite discrete dynamical system (X, [sigma]). This dynamical system is called a Z-dynamical system. Let R be a commutative Q-algebra with the identity element 1. A map

w : X [right arrow] R

is called a weight map of (X, [sigma]), or simply a weight of X. Let (X, [sigma]; w) be a weighted Z-dynamical system with a weight map w : X [right arrow] R. For x [member of] X and m [member of] [Z.sub.[greater than or equal to] 1], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [N.sub.m] (w) = [[SIGMA].sub.x[member of]X] [w.sub.m] (x). Let u be an indeterminate. The formal power series

exp ([summation over (m [greater than or equal to] 1)] [N.sup.m] (w)/m [u.sup.m]

is called the Ruelle zeta function [R] for the weighted Z-dynamical system (X, [sigma]; w), denoted by [Z.sup.R.sub.(X,[sigma])] (u; w), or simply [Z.sub.[sigma]] (u; w). The Ruelle zeta function [Z.sup.R.sub.(X,[sigma])] (u; w) is an element of the ring R[u] of formal power series the coefficients of which lie in R. Note that [N.sub.m] (1) equals the number [absolute value of Fix([[sigma].sup.m])] of m-periodic points. Therefore we have [Z.sub.[sigma]] (u; w) = [Z.sub.[sigma]] (u) if w = 1. For p [member of] Cyc([sigma]), we define w(p) = [[PI].sub.i[member of]Dom(p)] w(i).

Lemma 2. For each integer m [greater than or equal to] 1, it follows that [N.sub.m] = 1(p)w[(p).sup.m/1(p)].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. Since [w.sub.m] (x) = 0 if x [not equal to] Fix ([[sigma].sup.m]), it follows that [N.sub.m](w) [[SIGMA].sub.x[member of]Fix([[sigma].sup.m)] [[PI].sup.m-1.sub.k=0] w([[sigma].sup.k] (x)). One can easily see that an element i [member of] X belongs to Fix([[sigma].sup.m]) if and only if there exists p [member of] Cyc ([sigma]) satisfying i [member of] Dom(p) and l(p)|m. Thus one has a disjoint union

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let x [member of] Fix([[sigma].sup.m]), and suppose that x [member of] Dom(p) for p [member of] Cyc([sigma]) satisfying l(p)|m. It follows from the assumption that [[PI].sup.m-1.sub.k=0] w([[sigma].sup.k](x)) = l(p)w[(p).sup.m/l(p)]. This completes the proof. ?

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and X = [n]. Then [tau] defines a weighted Z-dynamical system (X, [sigma]; w), where the weight map is defined by w (i) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Consider the case where n = 5 and [sigma] = (123)(45). We have Fix([[sigma].sup.1]) = [empty set], Fix([[sigma].sup.2]) = {4, 5}, Fix([[sigma].sup.3]) = {1,2, 3}, Fix([[sigma].sup.4]) = {4, 5}, Fix([[sigma].sup.5]) = [empty set], Fix([[sigm].sup.6]) = {1,2, 3,4, 5}, and so on. We shall examine the value of [N.sub.m] (w) in this case. One can readily see that [w.sub.1] (x) = 0 for any x [member of] X and [N.sub.1] (w) =0. If m = 2, then it follows that [w.sub.2] (1) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that the coefficient 2 coincides with the number of 2-periodic points of (X, a). Similar inspection shows that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [N.sub.4] (w) = 2[[xi].sup.2([s.sub.4] + [S.sub.5])] and [N.sub.5] (w) = 0. In the case where m = 6, we have [w.sub.6] (1) = [w.sub.6] (2) = [w.sub.6] (3) = [[xi].sup.2([s.sub.1] + [S.sub.2] + [S.sub.3])] and [w.sub.6] (4) = [w.sub.6] (5) = [[xi].sup.3([s.sub.4]+[S.sub.5])]. Hence we have [N.sub.6] (w) = [3[xi].sup.2([s.sub.1] + [s.sub.2] + [s.sub.3])] + [2[xi].sup.3([s.sub.4]+[s.sub.5])]. One should notice here again that the coefficient 3 (resp. 2) coincides with the number of 3-periodic points (resp. 2-periodic points) of (X, [sigma]).

4. Foata-Zeilberger. A theorem of Foata and Zeilberger [FZ] gives an Euler product to the form 1/det(I - M) in a general setting. Let X = {1, 2, ..., n} be a finite alphabet of n letters, totally ordered by 1 < 2 < ... < n. Let X* denote the free monoid generated by X. An element of X* is called a word on X. The monoid X* is also totally ordered by the lexicographical order induced from the total order < on X. Let w = [i.sub.1] [i.sub.2] ... [i.sub.r] [member of] X* be a word. A set Re(w) = {[i.sub.1] [i.sub.2] ... [i.sub.r],[i.sub.2]i ... , [i.sub.r] [i.sub.1], ... , [i.sub.r] [i.sub.1] ... [i.sub.r-1]} of r words is called the cyclic rearrangement class of w. Remark that a cyclic rearrangement class of a word is a multiset in general. A word w [member of] X* is called a Lyndon word if w is the unique minimum in Re(w). The set of Lyndon words in X* is denoted by L = L(X). For example, in the case where X = {1, 2, 3}, 1212 [not member of] L, 1312 [not member of] L and 1213 [member of] L. The Lyndon words are the "primes" of the monoid X* in the following sense. The factorization of w stated in Proposition 3 is called the Lyndon factorization of w. A proof of the following will be found in [L].

Proposition 3 (The Lyndon Factorization Thoerem, LFT). Let w be a word on X. Then there exists a unique non-increasing sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of Lyndon words on X satisfying [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let [L] = {[l] | l [member of] L} be a set of commutative variables which is in one-to-one correspondence with L, and let A denote the Z-algebra Z[ [l] | l 2 L] of formal power series generated by [L]. Let M = [([m.sub.ij]).sub.i,j[member of]X] be a square matrix whose components lie in a commutative Q-algebra R. Note that the size of the matrix M is n x n. Let B be the Z-algebra Z [[m.sub.ij] | i,j [member of] X] of formal power series generated by the components of M. For a word w = [i.sub.1] [i.sub.2] ... [i.sub.r] [member of] X*, we denote the element [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Since the algebras A and B are commutative, we can define a ring homomorphism in the following manner:

[[phi].sub.M] : A [right arrow] B : [l] [??] [circ.sub.M] (l).

Let A be an element of A defined by A = [[PI].sub.l[member of]L] (1 - [l]). Note that A is invertible in the algebra A: [[LAMBDA].sup.-1] = [[PI].sub.l[member of]L] (1 + [l] + [[l].sup.2] + ...) [member of] A. Foata-Zeilberger's thorem states that the form 1/det(1 - M) is the image of [[LAMBDA].sup.-1] by [[phi].sub.M].

Proposition 4 (Foata-Zeilberger). [[phi].sub.M] (A) = det (I - M).

Since A is invertible and [[phi].sub.M] is an algebra homomorphism, it follows that [[phi].sub.M] ([[LAMBDA].sup.-1]) = 1/ det(I - M). Thus we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

that is, the form 1/det(1 - M) can always be reformulated into an Euler product.

5. Main results. Let X = [n] and (X, [sigma]; w) a Z-dynamical system. Suppose p [member of] Cyc([sigma]). Let w(p) = [[PI].sub.i[member of]Dom(p)] w(i). The Ruelle zeta function [Z.sub.[sigma]](u; w) has the following Euler product.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. By Lemma 2, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since the sum in the right-hand side ranges all over Cyc(a), it follows that this equals

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Therefore we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We assign a matrix [M.sub.[sigma]] (w) to the weighted Z-dynamical sysytem (X, [sigma]; w), defined by [M.sub.[sigma]] (w) = [(w(i)[[delta].sub.[sigma](i)j]).sub.ij[member of]X]. In the case where X = [5] and [sigma] = (123)(45), the matrix [M.sub.[sigma]] (w) is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where w(i) [member of] R for i [member of] X. One can observe that the reciprocal of the determinant det(1 - u[M.sub.[sigma]] (w)) coincides with the Euler product (1 - w [((123))[u.sup.3]).sup.-1] [(1 - w((45))[u.sup.2]).sup.-1], that is, by Theorem 5, we have a determinant expression

[Z.sub.(123)(45)](u; w) = 1/det(1 - u[M.sub.(123)(45)](w))

This identity actually holds in a general case.

Theorem 6. For any [sigma] [member of] [S.sub.n], it holds that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since each cyclic permutation can be regarded as an element of X*, the set Cyc([sigma]) is considered to be a subset of X*. Suppose that l = [i.sub.1] [i.sub.2] ... [i.sub.r] is a Lyndon word on X. By the definition of M = [M.sub.[sigma]] (w), it follows that [circ.sub.uM] (l) [not equal to] 0 if and only if l [member of] Cyc([sigma]). Hence we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [circ.sub.uM] (p) = [circ.sub.M] (p)[u.sup.l] (p), the right hand side equals

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that [circ.sub.M] (p) = w(p). Then by Theorem 5, the assertion follows. ?

Let [tau] [member of] G(r, n) and [xi] a primitive r-th root of unity. Since G(r ,n) = [(Z/rZ).sup.n] [??] [S.sub.n], there exists a unique sequence ([s.sub.1], ... , [s.sub.n]) of nonnegative integers smaller than r and a unique element [sigma] of [S.sub.n] satisfying [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then, as in Section 3, [tau] settles the weighted Z-dynamical system (X, [sigma]; w), where the weight map w is defined by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. On the dynamical system (X , a; w), one has [M.sub.[sigma]] (w) = [M.sub.[tau]]. Thus we have an expression of Koyama-Nakajima's L-functions [L.sub.[tau]] (u) in the form of generating functions of exponential type, founded on a dynamical systematic setting.

Corollary 7. Let (X, [sigma]; w) be the weighted Z-dynamical system determined by [tau] [member of] G (r, n), say [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as in Section 2. Then we have [L.sub.[tau]] (u) = [Z.sup.R.sub.(X,[sigma])] (u; w), that is, Koyama-Nakajima's L-function associated with [tau] is the Ruelle zeta function for the weighted Z-dynamical system (X, [sigma]; w).

Unit of Mathematical Science, Muroran Institute of Technology, 27-1 Mizumoto-cho, Muroran 050-8585, Hokkaido, Japan

(Communicated by Kenji FUKAYA, M.J.A., Oct. 12, 2016)

2010 Mathematics Subject Classification. Primary 11M41, 05C50.

Doi: 10.3792/pjaa.92.107

Acknowledgments. The authors would like to express their deep gratitude to Prof. Iwao Sato, Oyama National College of Technology, who guided them to this area of research, for his valuable comments and enthusiastic encouragement. They also would like to thank the referee for careful reading and helpful comments that improve readability of the paper.

The second-named author is partially supported by Grant-in-Aid for Scientific Research (C) of the Japan Society for the Promotion of Science (Grant No. 26400001).

References

[AM] M. Artin and B. Mazur, On periodic points, Ann. of Math. (2) 81 (1965), 82-99.

[FZ] D. Foata and D. Zeilberger, A combinatorial proof of Bass's evaluations of the Ihara-Selberg zeta function for graphs, Trans. Amer. Math. Soc. 351 (1999), no. 6, 2257-2274.

[KN] S. Koyama and S. Nakajima, Zeta functions of generalized permutations with application to their factorization formulas, Proc. Japan Acad. Ser. A Math. Sci. 88 (2012), no. 8, 115-120.

[L] M. Lothaire, Combinatorics on words, Encyclopedia of Mathematics and its Applications, 17, Addison-Wesley Publishing Co., Reading, MA, 1983.

[MS] H. Morita and I. Sato, Ruelle zeta functions for finite digraphs. (in preparation).

[R] D. Ruelle, Dynamical zeta functions for piecewise monotone maps of the interval, CRM Monograph Series, 4, Amer. Math. Soc., Providence, RI, 1994.

[Y] T. Yoshida, The Burnside ring and the universal zeta function of finite dynamical systems, RIMS Kokyuroku 1872 (2014), 122-131.