{'fraction_non_alphanumeric': 0.05263474856970792, 'fraction_numerical': 0.008882866606443843, 'mean_word_length': 3.230700636942675, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 33, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A discrete Lefschetz formula

A Lefschetz formula is given that relates loops in a regular finite graph to traces of a certain representation. As an application the poles of the Ihara/Bass zeta function are expressed as dimensions of global section spaces of locally constant sheaves.


Introduction
In the nineteensixties Yasutaka Ihara [13,14,15,16] defined a Selberg-type zeta function for rank one p-adic groups. This zeta function can also be considered as a zeta function attached to a quotient of the Bruhat-Tits building which is a special graph. The theory was later extended by Ki-Ichiro Hashimoto [10,11,12] to cover arbitrary bipartite graphs and by Hyman Bass [1] to arbitrary graphs. For further results see [19,20].
For a finite graph Y this zeta function is defined as where the product runs over all prime loops in Y (see section 2). Bass showed that Z Y (u) extends to a rational function without zeros, so the inverse, Z Y (u) −1 , is a polynomial.
In this paper we use Harmonic Analysis of the automorphism group G of the universal covering tree X of Y to describe the zeta function. We prove a Lefschetz formula (Theorem 5.2) that relates lengths of loops to the trace of co-invariants of the induced representation. This Lefschetz formula gives rise to two descriptions of the poles of the zeta function. Firstly, the poles are given by co-invariants of the regular G-representation given by the fundamental group, and secondly they can be described in terms of a family of locally constant sheaves F λ , λ ∈ C arising from homogeneous line bundles on the boundary of the tree. The relation is that the pole-order of Z Y (u) at the point u = λ is given by This assertion may be viewed as a discrete version of the Patterson conjecture [3].
The method of proof is an extension of the Harmonic Analysis of p-adic groups to the automorphism group G. We define the analogues of parabolic groups, split tori, and the like. It turns out that a parabolic P satisfies a Langlands decomposition P = MAN, but the group M does not centralize the "split torus" A. Therefore we are forced, when considering "Jacquet modules", to take co-invariants not with respect to the "unipotent radical" N but with respect to the group S = MN.
There are two appendices in which generalizations of the theory of Ihara/Bass zeta functions are suggested. The first extends the well known generalization to twists by locally constant sheaves. It is shown that certain constructible sheaves may serve the same purpose. In the second the theory is extended to infinite graphs of the type that occurs as quotients of Bruhat-Tits trees of arithmetic groups in positive characteristic [18].
In writing this paper up I did not strive for the most general version of each assertion, simply because it is much easier to read this way. Advanced readers may convince themselves that the theory extends to multigraphs, ie, where multiple edges and non-regular edges are allowed and that the zeta function may also be twisted by hermitian locally constant sheaves of finite rank, ie, by finite dimensional unitary representations of the fundamental group. It is, however, unclear to me how far the regularity condition can be relaxed, ie, whether the results of the paper (or modified versions thereof) hold for general finite graphs.

The zeta function
In this paper, a graph X consists of a set V X, called the set of vertices, together with a set EX of subsets of V X of order two, called edges. We say that the edge e = {x, y} connects the vertices x and y and we also write e = x, y. We then say that x and y are adjacent. The graph is called a finite graph if V X is a finite set. For a vertex x the number val(x) ∈ {0, 1, 2, . . . , ∞} of edges ending at x is called the valency of x. The graph is called univalent or regular if the valency is finite and the same for all vertices.
Sometimes we will also consider a graph as a one dimensional CW-complex, so all edges are identified with the unit interval. It does then make sense to speak of points of the graph and in particular of midpoints of edges. Further we have a path-length metric d(., .) on X giving each edge the length one.
A (combinatorial) path p is a sequence (v 0 , . . . , v n ), n > 0 of vertices such that v j and v j+1 are adjacent for j = 0, . . . , n − 1. The number n = l(p) is called the length of the path. Likewise, a path can also be described by the oriented edges it passes through. The path is closed A tail-less closed path with no backtracking is called reduced. Two reduced paths (v 0 , . . . v n ) and (w 0 , . . . , w k ) are said to be shift-equivalent if k = n and there is an s = 0, 1, 2, . . . such that v j = w j+k where j runs modulo n. A shift equivalence class of reduced paths is called a loop. If c is a loop, then c 2 = cc also is a loop and so is any power c k , k ∈ N. Let Y be a finite connected graph. Its zeta function is defined by where the product runs over all prime loops in Y . It has been shown by H. Bass in [1] that Z Y (u) always is a rational function, indeed, its inverse Z Y (u) −1 is a polynomial. In this paper we want to study Z Y (u) of a regular finite graph via the universal covering X of Y .

The tree
Let X be a tree, ie, X is a countable, connected graph that admits no loops. We assume that X is regular. Let q + 1 be its valency where q ∈ N. Let G be the group of automorphisms of X. The group G carries a totally disconnected topology. A basis of neighbourhoods of the unit is given by the compact open subgroups where E is an arbitrary nonempty finite set of vertices. Every compact subgroup of G fixes a point x which is either a vertex or the midpoint of an edge. So every maximal compact subgroup is a stabilizer K x of such a point x. Another way to describe the topology of G is to say that a sequence (g n ) in G converges to g ∈ G iff for every vertex x there is a natural number N(x) such that for every n ≥ N(x) we have g n (x) = g(x).
A ray in X is a one sided infinite path without backtracking, so it is a sequence of vertices (v 0 , v 1 , . . . ) such that v j and v j+1 are adjacent and Two rays (v 0 , v 1 , . . . ) and (w 0 , w 1 , . . . ) are called parallel if there are s ∈ Z and N ∈ N such that v j = w j+s for every j ≥ N. Parallelity is an equivalence relation. The boundary ∂X of X is by definition the set of all parallelity classes of rays in X. A boundary point c ∈ ∂X also is called a cusp of X.
The group G acts on the boundary ∂X. A parabolic subgroup P of G is the stabilizer of a cusp b ∈ ∂X geo . We fix such a pair (P, b). Every vertex x can be joined by a ray to b. In other words, given x, there exists a ray (x = v 0 , v 1 , . . . ) which lies in the parallelity class b. This ray is unique.
Loosely speaking a horosphere is the set of all vertices of the same distance to b. If p ∈ P preserves a horosphere, it will preserve every horosphere. Let S ⊂ P be the subgroup of those elements that preserve horospheres. Fix a finite ring R with q elements. At each vertex v there are q edges which do not point towards ∞. We label these edges with the elements of R in a way that • for v ∈ l the edge pointing towards the cusp 0 is labelled by 0 ∈ R.
• The labelling is invariant under the action of A.
For each labelled edge e let lab(e) ∈ R denote the label. For b ∈ ∂X \ {∞} there is a unique line (. . . , w −1 , w 0 , w 1 . . . ) joining b to ∞. Define ψ(b) in the ring of formal Laurent series R((t)) by The map ψ is a bijection from ∂X \ {∞} to the ring R((t)).
Note that the action of S on ∂X \ {∞} defines an injection S ֒→ Per(∂X \ {∞}). Let N denote the subgroup of S consisting of all n ∈ S for which there is n R ∈ R((t)) such that In other words, N consists of those elements of S which act by addition of an element of R((t)) on ∂X. The group N thus is isomorphic to the additive group of R((t)) and acts transitively on ∂X \ {∞}. It follows that S = MN and P = MAN. The group N is a closed subgroup of G. Indeed, it carries the t-adic topology of R((t)).
LetP denote the stabilizer of the cusp 0. DefineN in an analogous fashion to N to getP = MAN .
There is an element w ∈ G with w 2 = 1 and wv j = v −j for every j. Further w is supposed to be chosen so that for every a ∈ A. Then w is called the non-trivial Weyl element and W = {1, w} is the Weyl group to A.

Lemma 2.1 (Bruhat decomposition)
The group G can be decomposed into disjoint sets, Further, P wP = NwP = P wN.

Proof:
The group N acts transitively on the cusps different from ∞. This implies that for every g ∈ G \ P there is n ∈ N with ng∞ = 0. This implies wng ∈ P and so g ∈ NwP .

Trace formula and duality
Let G be a totally disconnected locally compact group, so G has a basis of unit neighbourhoods consisting of compact open subgroups. By a representation of G we mean a group homomorphism from π : G → GL(V π ) for some complex vector space V π . By abuse of notation we will write π for the space V π as well. For every compact open subgroup K of G let π K denote the space of K-fixed vectors. We say that the representation π is smooth if every v ∈ π is fixed by some compact open subgroup K.
Let π be a smooth representation. For a compact subgroup K of G and v ∈ π let the projection to the K-invariants. In other words, P K is a linear map on π given as follows. For given v ∈ π there exists a subgroup K ′ of finite index in K such that v is invariant under K ′ . Then It is easy to see that π is the direct sum of the space π K and the kernel π[K] of the linear map P K .
A smooth representation π is admissible if for every compact open subgroup K the space π K is finite dimensional.
Suppose that G admits a uniform lattice Γ, ie, a discrete subgroup such that Γ\G is compact. Then G is unimodular (Ex 14.2 in [8]). The space of C ∞ (Γ\G) locally constant functions on Γ\G carries an admissible representation R given by .
A function f on G is called a Hecke function if f is integrable and there is a compact open subgroup K of G such that f factors over K\G/K. For any Hecke function f the integral defines a linear operator on C ∞ (Γ\G). For g ∈ G and f a function on G define the orbital integral whenever the integral exists. Here G g is the centralizer of g in G. We have to fix a Haar measure on G g here.

Proposition 3.1 (Trace formula) Let f be a Hecke function. Then
where the sum on the right hand side runs over the set of all conjugacy classes in the group Γ and Γ γ denotes the centralizer of γ in Γ.
The proof is the same as that of the corresponding assertion for p-adic linear groups [6].
The trace formula can also be used to show the Ihara/Bass-identity (see [21,22]).
We now turn to duality. Let Adm(G) denote the category of all admissible smooth representations of G. We introduce the setup of topological (continuous) representations. Let C(G) denote the category of continuous representations of G on locally convex, complete, Hausdorff topological vector spaces. The morphisms in C(G) are continuous linear G-maps.
To any V ∈ C(G) we can form V ∞ , the space of smooth vectors, which is by definition the space of all vectors in V which have an open stabilizer. By the continuity of the representation it follows that V ∞ is dense in V . We call the representation V admissible if V ∞ is admissible. Let Adm top (G) denote the category of all admissible topological representations. The functor: is easily seen to be exact.
To V ∈ Adm(G) let V * = Hom C (V, C) be the dual module and letṼ be the space of smooth vectors in V * . ThenṼ is admissible again and the natural map from V toṼ is an isomorphism.
On the space C(G) of continuous maps from G to the complex numbers we have two actions of G, the left and the right action given by where g, x ∈ G and ϕ ∈ C(G). For V ∈ Adm(G) let where we take G-homomorphisms with respect to the right action, so V −∞ is the space of all linear maps f fromṼ to The next lemma and the next Proposition will justify this terminology. First observe that the topology of locally uniform convergence may be installed on This map is clearly injective. To check It follows that the functor R maps Adm(G) to Adm top (G) and that F R = Id.
we have a functorial isomorphism: Proof: We have a natural map Since W ∞ is dense in W this map is injective. For surjectivity we first construct a map ψ : W → (W ∞ ) −∞ . For this let W ′ be the topological dual of W and for w ′ ∈ W ′ and w ∈ W let The map w → ψ .,w gives an injection The restriction then gives From this we get an injection which is continuous. Let ζ : W ∞ → V be a morphism in Adm(G). We get Let now Γ denote a cocompact torsion-free discrete subgroup of G and let C(Γ\G) denote the space of all continuous functions on Γ\G.
The next theorem is a version of the classical duality theorem [9] adapted to our context.
There is a version for higher cohomologies in [6] but this won't be needed here.
since any G-homomorphism from the smoothṼ to C(Γ\G) has image in C ∞ (Γ\G). Dualizing gives

A character identity
The proofs in this section are inspired by [4,5].
. Let ∞ denote the cusp given by the ray (v 0 , v 1 , . . . ) and let 0 denote the cusp given by the ray Let P, L, M, S, A be the groups defined above.
Then K 0 is a maximal compact subgroup and the K j form a basis of neighbourhoods of the unit in G.
For any set X let 1 X denote its characteristic function. For f, g ∈ L 1 (G) denote by f * g their convolution product, so which impliesn j kn j ∈ M j . Now the first part of (a) follows. The second is obtained by taking inverses. The point (b) is immediate from the fact that av j = v j+v(a) and N j being the stabilizer of v j in N.
For (c) note that the map k 1 ak 2 → k 1 induces a bijection between the sets Finally, we show (d). As sets one has K j aK j · K j bK j = K j abK j because for By (c) above also the measures agree.
Let π be an admissible representation of G. For any subgroup H on G let π[H] denote the complex vector space generated by all elements of the form Then π S is the largest P -module quotient on π on which S acts trivially.
Proof: This follows from Lemma 4.1.

Proposition 4.3
Suppose π is finitely generated as G-module. Then π S is a finitely generated A-module.
Proof: Let E be a finite generating set of π. Let K ⊂ G be a compact open subgroup such that E ⊂ π K . Let Λ be a finite subset of G such that P ΛK = G. Since π is the linear span of π(G)E it follows that π S is as A-module generated by the image of π(Λ)E.
(b) The canonical projection from π M to π S is surjective.
(c) The canonical projection from π K 1 to π S is surjective. In particular, π S is finite dimensional.
Proof: The first assertion is an easy consequence of the Iwahori decomposition. Let π M be the largest quotient on which M acts trivially. Since M is compact, integration over M induces an isomorphism π M → π M . Since the map π M → π S is surjective, the second claim follows.
For the third let U S be a finite dimensional subspace of π S and let U be a finite dimensional subspace of π M mapping to U S . There is j ∈ N such that U ⊂ π M 1Nj . Choose a ∈ A such that a −1N 1 a ⊂N j . Then π(a)U ⊂ π M 1N1 . The decomposition K j =N j M j N j for j = 1 implies that the image of π M 1N1 in π S equals the image of π K 1 . So it follows that π(a)U S lies in the image of π K 1 . Hence its dimension, ie, the dimension of U S , is bounded by the dimension of π K 1 . We conclude that π S is finite dimensional. Thus one can take U S to be equal to π S . But then U S = π(a)U S lies in the image of π K 1 .

Proposition 4.5 Let a 1 be the unique generator of
Proof: We need the following lemma.
This shows that v lies in π[H]. Lemma 4.7 If a n 1 Ua −n 1 ⊂ S j and v ∈ π[S] ∩ π K j , then π 1 K j a n 1 K j v = 0.
Proof: The vector π 1 K k a n 1 K j v differs from P K j (π(a n 1 )v) only by a scalar. By Proposition 4.4 the latter equals P N j (π(a n 1 )v). But P N j (π(a n 1 )v) = (const) N j π(n)π(a n 1 )v dn = (const) π(a n 1 ) a n 1 N j a −n 1 π(n)v dn = 0.
Choose n to be large enough that a n 1 Ua −n 1 ⊂ S j and define π K j 1 to be π(K j a n 1 K j )V K j . We first show that thw projection from π K j 1 to π S is surjective. For this let u ∈ π S . By Proposition 4.4 there is v ∈ π K j whose image in π S equals π S (a −n 1 )u. By Corollary 4.2, P K j (π(a n 1 )v) has image u. For the injectivity let v 0 ∈ π K j and assume that v = π(K j a n 1 K j )v 0 lies in π[S]. We have to show that v = 0.
To prove (b) note that the above is valid for every large enough n, so all the spaces π(K j a n 1 K j )π K j have the same dimension. But for m ≥ 0, Finally, statement (c) follows from the definition.
We now state the main theorem of this section.
An element g of G is called elliptic if it fixes a point of X. This point can be chosen to be a vertex or a midpoint of an edge. If g fixes a midpoint, then g 2 fixes both vertices of that particular edge. If g does not fix a point of X then it is called hyperbolic. In that case the minimum is attained exactly on a line l(g) = (. . . , v −1 (g), v 0 (g), v 1 (g), . . . ) which is preserved by g. Since this line l(g) can be mapped to our given line by some h ∈ G, it follows that g is conjugate to an element of L = AM. It is not hard to see that every hyperbolic element of L is conjugate to a uniquely determined element of A − . Let G hyp denote the set of hyperbolic elements of G.

Corollary 4.9
Let π be an admissible representation. On G hyp define a conjugation invariant function θ π by θ π (a) = tr (a|π S ), a ∈ A − . Then for every Hecke function f which is supported on G hyp , Proof: The claim follows from the theorem for Hecke functions of the form f = 1 K j aK j , a ∈ A − . Every Hecke function with support in G hyp is a linear combination of functions which are conjugate to functions of the latter form.

The Lefschetz formula
Recall that G is the automorphism group of a q + 1-regular tree. Note that such a group G admits a lattice Γ as above, hence G is unimodular. Let g be a hyperbolic element of G. Let l(g) = l = (. . . , v −1 , v 0 , v 1 , . . . ) be the line that is preserved by g. After renumbering we can achieve that gv j = v j−l(g) . Let b be the parallelity class of the ray (v 0 , v 1 , . . . ). Let P, S, M, A be defined as before. Then g ∈ L = AM. The centralizer G g of g preserves l and therefore is a subgroup G g = L g of L. Let M g = G g ∩ M, then we have an exact sequence 1 → M g → L g → C → 1 for an infinite cyclic group C. Let A g ⊂ L g be an image of a splitting s : C → L g , then L g = A g M g . We normalize the Haar measure on the compact group M g to have volume one and on A g we choose l(a 0 ) times the counting measure, where a 0 is a generator of A g . Then the volume of < g > \L g equals l(g).
Alternatively we call an element τ of Γ a primitive element if τ = σ n for σ ∈ Γ and n ∈ N implies n = 1. Then γ 0 is the unique primitive element such that γ = γ µ 0 with µ > 0.
Proof: This follows from the trace formula.

Theorem 5.2 (Lefschetz Formula) Let Γ ⊂ G be a discrete cocompact subgroup which acts freely on X. Then for every function ϕ on
The proof will occupy the rest of the section. We start with the simple observation that the length map l : G → N 0 is continuous and hence l −1 (n) is open for every n ∈ N 0 . An element g ∈ G is elliptic iff l(g) = 0 and hyperbolic iff l(g) > 0.
We next need an integration formula. Fix the Haar measure on G that gives the stabilizer K x of a vertex x the volume one. On A install the counting measure as Haar measure.
For j ∈ Z let K(j) be the stabilizer of the point v j and set K = Then N(j) is a compact open subgroup of N that stabilizes v k for every k ≥ j. The group N is the union of all the subgroups N(j). We give N the Haar measure such that N(0) gets volume one. Then vol(N(j)) = q j .

If f is supported in the open set of hyperbolic elements,
For later use we also note that for a ∈ A, f ∈ L 1 (S), Here v(a) ∈ Z is defined by a(v j ) = v j+v(a) . Then a ∈ A − is equivalent to v(a) < 0.
The natural projection identifies NA with K\G, so this measure gives a Haar measure on the group NA. But dn da also is a Haar measure, so the uniqueness of Haar measures gives the first assertion up to a scalar. Plugging in the test function f = 1 K gives the claim.
Let G hyp denote the set of all hyperbolic elements of G. Note that the map is surjective and proper. Hence there is a nowhere vanishing function B on The projection G → G/A identifies KN with the quotient G/A. Via the first integral equality we get an identification of the measure on G/A with the measure dk dn. Thus, We are going to compute B(a) by plugging in special test functions. First let a 1 ∈ A − be the unique element with l(a 1 ) = 1. For k ∈ N write B(k) instead of B(a k 1 ). Fix some a = a k 1 ∈ A − . Let f be the indicator function of the set KaK ∩ G hyp . This function is K-central. The set KaK equals the set of all g ∈ G that satisfy d(gv 0 , v 0 ) = k. Since there are (q + 1)q k−1 vertices in distance k to v 0 it follows that |KaK/K| = (q + 1)q k−1 .
An element g of KaK is elliptic iff g fixes a point x half-way between v 0 and g(v 0 ). Since for every point x in distance k/2 there are q [k/2] points in distance k that lie beyond x it follows that the volume of the set of elliptic elements in KaK equals q [k /2] . Hence where k = max(j, j − v(a)). For a ∈ A − and s ∈ S we have d(sas −1 v 0 , v 0 ) = d(as −1 v 0 , s −1 v 0 ) and this number equals l(a) if s ∈ S 0 . If s ∈ S j+1 \ S j for some j ≥ 0, then d(as −1 v 0 , s −1 v 0 ) = 2(j + 1) + l(a).
Using vol(S 0 ) = 1 and vol(S j+1 \ S j ) = q j (q − 1) we get The unique solution to this recurrence formula is B(k) = q k . This implies the second assertion of the lemma. For the third note that S f (asa −1 ) ds is a Haar measure on S, therefore equals c(a) S f (s) ds for a constant c(a). Plugging in the test function f = 1 K gives c(a) = q v(a) .
Let η ≥ 0 be compactly supported function on N, left invariant under K ∩ N and such that N η(n) dn = 1. Define a function f on G by We have seen that am is conjugate to a. so that If we plug this function f into the trace formula we readily see that the geometric side will give the geometric side of the Lefschetz formula. For the spectral side we compute for an admissible representation π, So Theorem 5.2 follows from the trace formula.

Rationality of the zeta function
Let Y be a finite regular graph of valency, say, q + 1, X its universal covering and G the automorphism group of X. Then there is a uniform torsion-free lattice Γ in G such that Y = Γ\X. Recall the zeta function of Y , where the product runs over all prime loops in Y . Since Γ is the fundamental group of Y the set of prime loops is in bijection to the set of prime conjugacy classes [γ 0 ] in Γ. Hence, We compute the logarithmic derivative of Z Y , Here the last sum runs over all nontrivial conjugacy classes in Γ and γ 0 is the underlying prime to γ. The last expression equals the geometric side of the Lefschetz formula for the test function which for |u| < 1 q satisfies the condition of the Lefschetz formula. So in that range the function Z ′ Y /Z Y equals a∈A − u l(a) u q l(a) tr (a|R S ).
For every group homomorphism ψ from A to C × there is a unique number λ ∈ C × such that ψ(a) = λ v(a) .
For λ ∈ C × let R S (λ) be the generalized λ-eigenspace, ie, R S (λ) is the largest A-submodule on which (a − λ v(a) ) acts nilpotently for every a ∈ A. Then Let m λ denote the dimension of R S (λ). Then We have proved the following theorem.
Theorem 6.1 The function Z Y (u) extends to a rational function on C with Z Y (u) being a polynomial. The pole-order of Z Y at u = λ/q, λ ∈ C × , equals

The Patterson conjecture
For λ ∈ C × let δ λ be the character of P = AS given by Let I λ denote the representation of G induced from δ λ . Then I λ is the representation on the space of locally constant functions on G that satisfy for p ∈ P and x ∈ G. The representation is given by The representation I λ is admissible.

Lemma 7.3
Let π be an irreducible admissible representation of G. If λ = ± √ q, then A acts semisimply on π S (λ). In any case the length of the Amodule π S (λ) is at most 2.
Proof: Let C λ denote the one dimensional P -module C on which P acts by δ λ . For α ∈ Hom(π, I λ ) let α(1) : π → C be given by For s ∈ S we get α(1)π(s)v = α(1)v and so α(1) factors over π S . In this way we get an isomorphism So, if π S is not zero, then π, being irreducible, will inject into one I λ and so π S will inject into I λ,S . So it suffices to show the assertion for π = I λ .
The map ψ : π = I λ → C λ given by f → f (1) is a P -homomorphism. The group A acts on the image by δ λ and this defines an irreducible quotient of π S . We will show that the kernel of ψ gives an irreducible subrepresentation of π S on which A acts by δ q/λ .
Recall the Bruhat decomposition G = P ∪ P wN. Let f be in the kernel of ψ. Then f vanishes in a neighbourhood of 1 and thus the function s → f (ws) is compactly supported on S, so the integral S f (ws) ds converges. This integral defines an isomorphism ker(ψ) S → C. The group A acts as The lemma follows.
To be able to apply Lemma 7.3 we have to show that C ∞ (Γ\G) is the direct sum of irreducible representations with finite multiplicities. This follows readily from the corresponding assertion for L 2 (Γ\G). So suppose λ = ± 1 √ q . Then by semisimplicity, In the last equation we have used the duality theorem. This proves the first assertion of the theorem. For the second replace A with A 2 = v −1 (2Z) and P by the finite index subgroup A 2 S and follow the proof above.
For the Corollary use the functional equation which is proved in ( [1] Cor. 3.10). Here r 0 and r 1 are the number of vertices and edges respectively.
Finally, we give the sheaf-theoretic version of Theorem 7.1.
The projection onto the first factor F λ → Γ\X = Y makes F λ a locally constant sheaf over Y . Since for a locally constant sheaf the sheaf-cohomology coincides with the group cohomology of the fundamental group, we get the following corollary.

A Zeta functions for constructible c-sheaves
In this appendix we suggest a generalization of the Ihara/Bass zeta function.
A well know generalization is the twist with a finite dimensional representation of the fundamental group Γ. The latter amounts to the same as the choice of a locally constant sheaf of vector spaces over the graph. Here we show how the theory can be extended to a certain class of constructible sheaves.
A constructible sheaf of a stratified space X = X n ⊃ X n−1 ⊃ · · · ⊃ X 0 is a sheaf which is locally constant on each stratum X j \X j−1 . A graph X, viewed as a one dimensional CW-complex, has a natural two-step stratification X = X 1 ⊃ X 0 , where X 0 is the set of vertices, or the 0-skeleton. Let F be a constructible sheaf of abelian groups on X.
For each edge s let x e be its midpoint and let F e denote the stalk at x e . Let v be an endpoint of e. Let F v be the stalk at v. Recall that Since F is constant on the contractible space e there is a canonical isomorphism F y ∼ = F e , so s U defines an element of F e . Since F is constant on e this element does not depend on the choices of y or s U , but only on s. Thus we get a map ϕ e v : F v → F e . It is easy to see that the sheaf F can be recovered up to isomorphism from the stalks F v , F e and the maps ϕ e v . So a constructible sheaf on a graph is given by the following data • an abelian group F v for every vertex v, • an abelian group F e for every edge e, and • a group homomorphism ϕ e v : F v → F e whenever v is an endpoint of e.
A cosheaf is the dual construction to a sheaf, so a constructible cosheaf is given abelian groups F v , F e as above and group homomorphisms whenever v is an endpoint of e. Instead of sheaves abelian groups one can also consider sheaves of vector spaces, general groups, etc.
An example for a cosheaf of groups on a graph X is given as follows. Let G be the automorphism group of X. For each vertex v let G v be its stabilizer in G. For each edge e let G e be its pointwise stabilizer in G. If v is an endpoint of e then G e is a subgroup of G v , so the injection ψ v e : G e → G v defines a constructible cosheaf of groups on X.
Next, let (ρ, V ) be a representation of G. For each vertex v let V v be the space of fixed points V v = V Gv . Likewise for edges. If v is an endpoint of e then V v is a subspace of V e , so the inclusion ϕ e v : V v ֒→ V e defines a sheaf V of vector spaces over X.
Assume the representation ρ to be smooth. Then we also have a cosheaf structure on V given by In this case we have ψ v e ϕ e v = Id Vv . This motivates the following definition. By a c-sheaf we mean a constructible sheaf V of finite dimensional complex vector spaces that also carries the structure of a constructible cosheaf such that ψ v e ϕ e v = Id Vv for every edge e and every endpoint v of e. Let V be a c-sheaf on X. Let u, v be two adjacent vertices and e their connecting edge. define T v u = ψ v e ϕ e u , then T v u maps V u linearly to V v . For a path p = (v 0 , . . . , v n ) let T p : V v 0 → V vn be given by Let c le a loop in X given by the path (v 0 , . . . , v n ). Consider the operator Note that this operator depends on the choice of the underlying path. However, for every j ∈ N the expression tr (T j c ) does not depend on the choice of a path. Therefore also does only depend on the loop c.
Theorem A.1 Let X be a finite graph and V a c-sheaf on X. Then the infinite product which runs over all prime loops in X, converges for u small and extends to a rational function in u. The inverse Z V (u) −1 is a polynomial.
Proof: First note that Next consider the set OE = OE(X) of oriented edges. For each oriented edge e let e −1 denote the same edge with reversed orientation and letē be the underlying simple edge. Define V e to be a copy of Vē and let T : where s ∈ V e and the sum runs over all oriented edges e ′ = e −1 such that the target point of e equals the start point of e ′ . It emerges that tr T n = c:l(c)=n l(c 0 ) tr T c . Therefore, This finishes the proof.

B Graphs with infinite ends
Linear algebraic groups over local fields of positive characteristic may contain arithmetic subgroups Γ which are of finite covolume but not cocompact. The quotient Γ\X of the Bruhat-Tits building X then is infinite. The finite covolume condition amounts to the following. For each vertex v of X let Γ v be its stabilizer in Γ. Then Γ v is a finite group. It follows that If the building is a tree then the graph Γ\X has the structure described below [18].
Let Y be a connected graph. Since it does not affect the zeta function we may assume that Y has no finite ends, ie, no vertices of valency one. Next we assume the Y decomposes as where Y c is finite (compact core) and each S j is a cusp sector, ie, the vertices in S j are v 0 , v 1 , v 2 . . . . , each v j for j ≥ 1 has valency 2, being adjacent exactly to v j−1 and v j+1 . The intersection of Y c and S j is {v 0 }.
This decomposition is not uniquely determined and the zeta function given below will depend on the choice. One can, however, make the choice canonical by insisting, for example, that each end-vertex v 0 of a cusp sector has valency greater that 2. We will now define the zeta function for such a graph in analogy with the Selberg zeta function for noncompact arithmetic quotients of the upper half plane.
For each vertex v let d(v) denote the distance of v to Y c . We say that a path p = (v 0 , . . . , v n ) is essentially backtracking-free if, whenever v j−1 = v j+1 , then d(v j−1 ) < d(v j ). This means that the only backtracking happens in the cusp sectors where one walks in and turns back once to walk out again. Next a closed path is essentially tail-less if it either is indeed tail-less or if d(v 0 ) > d(v 1 ), ie, the path starts in a cusp sector. An S-loop is an equivalence class of essentially backtracking-free, essentially tail-less, closed paths under index shift as before. An S-loop is called prime if it is not a power of a shorter one.
As before let OE denote the set of oriented edges. We choose a weight w : OE → (0, ∞) such that e∈OE w(e) < ∞.
This is the finite volume condition. For each S-loop c given by the oriented edges (e 1 , . . . , e n ) let w(c) def = w(e 1 ) · · · w(e n ).
Then w(c j ) = w(c) j for every j ∈ N. Proof: Once we know that T is of trace class the formula for the trace is clear. To see that T is of trace class let e be an oriented edge and define ϕ e = e ′ δ e ′ , where δ e ′ is the delta function at e ′ and the sum runs over all e ′ ∈ OE with start(e ′ )=target(e) and e ′ = e −1 except if e is in a cusp sector and pointing outward in which case e ′ = e −1 is allowed. Then we have for f ∈ l(OE, w), T f = e∈OE f, ϕ e δ e .
To show that T is of trace class it therefore suffices to show that e∈OE ||ϕ e || ||δ e || < ∞.
Let λ 1 , λ 2 , . . . be the non-zero eigenvalues of T , each repeated according to its multiplicity. Then j |λ j | < ∞ and so the product det(1 − uT ) = j (1 − uλ j ) converges for every u ∈ C and defines an entire function with zeros at the numbers λ −1 j , j ∈ N. Using the lemma, the same computation as in the last section yields det(1 − uT ) = Z Y (u) −1 .