Velleda Baldoni
email: baldoni@mat.uniroma2.it

Nicole Berline
email: berline@math.polytechnique.fr

Jesús A De Loera
email: deloera@math.ucdavis.edu

M K Öppe

Michèle Vergne
email: vergne@math.jussieu.fr

Matthias Köppe

INTERMEDIATE SUMS ON POLYHEDRA II: BIDEGREE AND POISSON FORMULA

We continue our study of intermediate sums over polyhedra, interpolating between integrals and discrete sums, which were introduced by A. Barvinok [Computing the Ehrhart quasipolynomial of a rational simplex, Math. Comp. 75 (2006Comp. 75 ( ), 1449Comp. 75 ( -1466]]. By well-known decompositions, it is sufficient to consider the case of affine cones s+c, where s is an arbitrary real vertex and c is a rational polyhedral cone. For a given rational subspace L, we integrate a given polynomial function h over all lattice slices of the affine cone s + c parallel to the subspace L and sum up the integrals. We study these intermediate sums by means of the intermediate generating functions S L (s+ c)(ξ), and expose the bidegree structure in parameters s and ξ, which was implicitly used in the algorithms in our papers [Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra, Found. Comput. Math. 12 (2012), 435-469] and [Intermediate sums on polyhedra: Computation and real Ehrhart theory, Mathematika 59 (2013), 1-22]. The bidegree structure is key to a new proof for the Baldoni-Berline-Vergne approximation theorem for discrete generating functions [Local Euler-Maclaurin expansion of Barvinok valuations and Ehrhart coefficients of rational polytopes, Contemp. Math. 452 (2008), 15-33], using the Fourier analysis with respect to the parameter s and a continuity argument. Our study also enables a forthcoming paper, in which we study intermediate sums over multi-parameter families of polytopes.

Introduction

Let p be a rational polytope in V = R d . Computing the volume of the polytope p and counting the integer points in p are two fundamental problems in computational mathematics, both of which have a multitude of applications. The same is true for weighted versions of these problems. Let h(x) be a polynomial function on V . Then we consider the problems to compute the integral 1.1. Intermediate sums. The integral I(p, h) and the sum S(p, h) have an interesting common generalization, the so-called intermediate sums S L (p, h), where L ⊆ V is a rational vector subspace. These sums interpolate between the discrete sum S(p, h) and the integral p h(x) dx as follows. For a polytope p ⊂ V and a polynomial h(x), we define

I(p, h) =

S L (p, h) = y p∩(y+L) h(x) dx,
where the summation variable y runs over a certain projected lattice, so that the polytope p is sliced along affine subspaces parallel to L through lattice points and the integrals of h over the slices are added up. For L = V , there is only one term in the sum, and S V (p, h) is just the integral I(p, h). For L = {0}, we recover the discrete sum S(p, h). Intermediate sums were introduced as a key tool in a remarkable construction by Barvinok [START_REF]Computing the Ehrhart quasi-polynomial of a rational simplex[END_REF]. Consider the one-parameter family of dilations tp of a given polytope p by positive integers t, which is studied in Ehrhart theory. A now-classic result is that the number S(tp, 1) is a quasi-polynomial function of the parameter t. 1 Its crudest asymptotics (the highest-degree coefficient) is given by the volume I(p, 1) of the polytope. Barvinok's construction in [START_REF]Computing the Ehrhart quasi-polynomial of a rational simplex[END_REF] provides efficiently computable refined asymptotics for S(tp, 1) in the form of the highest k coefficients of the quasi-polynomial, where k is a fixed number. This is done by computing certain patched sums, which are finite linear combinations L∈L ρ(L)S L (p, 1) of intermediate sums. In [START_REF]Computation of the highest coefficients of weighted Ehrhart quasipolynomials of rational polyhedra[END_REF] and [START_REF] Baldoni | Intermediate sums on polyhedra: Computation and real Ehrhart theory[END_REF], we gave a refinement and generalization of Barvinok's construction, based on the Baldoni-Berline-Vergne approximation theorem for discrete generating functions [START_REF] Baldoni | Local Euler-Maclaurin expansion of Barvinok valuations and Ehrhart coefficients of rational polytopes[END_REF], in which we handle the general weighted case 1 A quasi-polynomial takes the form of a polynomial whose coefficients are periodic functions of t, rather than constants. In traditional Ehrhart theory, only integer dilation factors t are considered, and so a coefficient function with period q can be given as a list of q values, one for each residue class modulo q. However, the approach to computing Ehrhart quasi-polynomials via generating functions of parametric polyhedra leads to a natural, shorter representation of the coefficient functions as closed-form formulas (so-called step-polynomials) of the dilation parameter t, using the "fractional part" function. These closed-form formulas are naturally valid for arbitrary non-negative real (not just integer) dilation parameters t. This fact was implicit in the computational works following this method [START_REF] Verdoolaege | Counting integer points in parametric polytopes using Barvinok's rational functions[END_REF][START_REF] Verdoolaege | Incremental loop transformations and enumeration of parametric sets[END_REF], and was made explicit in [START_REF] Köppe | Computing parametric rational generating functions with a primal Barvinok algorithm[END_REF]. The resulting real Ehrhart theory has recently caught the interest of other authors [START_REF] Linke | Rational Ehrhart quasi-polynomials[END_REF][START_REF] Henk | Lattice points in vector-dilated polytopes[END_REF].

and compute the periodic coefficients as closed-form formulas (so-called step-polynomials) of the dilation parameter t. These formulas are naturally valid for arbitrary non-negative real (not just integer) dilation parameters t.

1.2. Multi-parameter families of polyhedra and their intermediate generating functions. In the present article, we continue our study. Our ultimate goal, which will be achieved in the forthcoming article [START_REF]Three Ehrhart quasi-polynomials[END_REF], is to study intermediate sums for families of polyhedra governed by several parameters. This interest is motivated in part by the important applications in compiler optimization and automatic code parallelization, in which multiple parameters arise naturally (see [START_REF] Clauss | Parametric analysis of polyhedral iteration spaces[END_REF][START_REF] Verdoolaege | Incremental loop transformations and enumeration of parametric sets[END_REF][START_REF] Verdoolaege | Counting integer points in parametric polytopes using Barvinok's rational functions[END_REF] and the references within). However, as we will explain below, the parametric viewpoint enables us to prove fundamental results about intermediate sums that are of independent interest.

Similar to [START_REF] Köppe | Computing parametric rational generating functions with a primal Barvinok algorithm[END_REF][START_REF] Beck | Multidimensional Ehrhart reciprocity[END_REF][START_REF] Henk | Lattice points in vector-dilated polytopes[END_REF], let p(b) be a parametric semi-rational [START_REF] Baldoni | Intermediate sums on polyhedra: Computation and real Ehrhart theory[END_REF] polyhedron in V = R d , defined by inequalities p(b) = x ∈ V : µ j , x ≤ b j , j = 1, . . . , N , where µ 1 , µ 2 , . . . , µ N are fixed linear forms with integer coefficients, and the parameter vector b = (b 1 , . . . , b N ) varies in R N . The study of the counting functions b → S(p(b), 1) then includes the classical vector partition functions [START_REF] Brion | Residue formulae, vector partition functions and lattice points in rational polytopes[END_REF] as a special case. Then the counting function is a piecewise quasi-polynomial function of the parameter vector b. 2 We can extend this result to the general weighted intermediate case in the forthcoming paper [START_REF]Three Ehrhart quasi-polynomials[END_REF].

As in the well-known discrete case (L = 0), it is a powerful method to take this study to the level of generating functions. We consider the intermediate generating function

S L (p(b))(ξ) = y p∩(y+L)
e ξ,x dx, (

for ξ ∈ V * , where the summation variable y again runs over a certain projected lattice. If p(b) is a polytope, the function S L (p(b))(ξ) is a holomorphic function of ξ. Then it is not hard to see that, once the generating function S L (p(b))(ξ) is computed, the value S L (p(b), h) for any polynomial function h(x) can be extracted [START_REF]Computation of the highest coefficients of weighted Ehrhart quasipolynomials of rational polyhedra[END_REF][START_REF] Baldoni | Intermediate sums on polyhedra: Computation and real Ehrhart theory[END_REF]. Indeed, if ξ ∈ V * , then 2 Again this fact is well-known for the "classical" case, when b runs in Z N . That it holds as well for arbitrary real parameters b follows from the computational works using the method of parametric generating functions [START_REF] Verdoolaege | Counting integer points in parametric polytopes using Barvinok's rational functions[END_REF][START_REF] Verdoolaege | Incremental loop transformations and enumeration of parametric sets[END_REF]; it is made explicit in [START_REF] Köppe | Computing parametric rational generating functions with a primal Barvinok algorithm[END_REF].

h(x) = ξ,x m m! is a polynomial function on V , homogeneous of degree m. Then the homogeneous component S L (p(b)) [m] (ξ) of the holomorphic function S L (p(b))(ξ) is equal to the intermediate sum S L (p(b), h).
For a general polynomial function h(x), the result then follows by well-known decompositions as sums of powers of linear forms [START_REF] Baldoni | How to integrate a polynomial over a simplex[END_REF].

If p(b) is a polyhedron, not necessarily compact, the generating function S L (p(b))(ξ) still makes sense as a meromorphic function of ξ with hyperplane singularities (near ξ = 0), that is, the quotient of a function which is holomorphic near ξ = 0 divided by a finite product of linear forms. Then, a well-known decomposition of space allows us to write the generating function S L (p(b))(ξ) of the polyhedron p(b) as the sum of the generating functions of the affine cones s + c at the vertices (Brion's theorem). Note that within a chamber, s will be an affine linear function of b. A crucial observation is that for such meromorphic functions, homogeneous components are still well-defined, and the operation of taking homogeneous components commutes with Brion's decomposition and other decompositions.

Brion's decomposition allows us to defer the discussion of the piecewise structure of S L (p(b)) corresponding to the chamber decomposition of the parameter domain to the forthcoming paper [START_REF]Three Ehrhart quasi-polynomials[END_REF]. In the present paper, we study the more fundamental question of the dependence of the generating function S L (s + c)(ξ) of an affine cone s + c and its homogeneous components S L (s + c) [m] (ξ) on the apex s and the dual vector ξ, i.e., as functions of the pair (s, ξ) ∈ V × V * . 1.3. First contribution: Bidegree structure of S L (s + c)(ξ) in parameters s and ξ. Instead of the intermediate generating function S L (s + c)(ξ), it is convenient to study the shifted function

M L (s, c)(ξ) = e -ξ,s S L (s + c)(ξ);
it already appears implicitly in the algorithms in our papers [START_REF]Computation of the highest coefficients of weighted Ehrhart quasipolynomials of rational polyhedra[END_REF][START_REF] Baldoni | Intermediate sums on polyhedra: Computation and real Ehrhart theory[END_REF]. This function depends only on s modulo Z d + L, in other words it is a function on V /L which is periodic with respect to the projected lattice.

To illustrate the main features of this function, let us first describe the dimension one case with V = R, L = {0} and c = R ≥0 . We denote by {t} the fractional part of a real number t, defined by {t} ∈ [0, 1[ and t -{t} ∈ Z. Then

S(s + c)(ξ) = n≥⌈s⌉ e nξ = e ⌈s⌉ξ 1 -e ξ = e (s+{-s})ξ 1 -e ξ , M(s, c)(ξ) = e -sξ S(s + c)(ξ) = e {-s}ξ 1 -e ξ .
The function M(s, c)(ξ) admits a decomposition into homogeneous components, which in this example are given by the Bernoulli polynomials:

M(s, c) [m] (ξ) = - B m+1 ({-s}) (m + 1)! ξ m .
Thus, as a function of s ∈ R, M(s, c) [m] (ξ) is a polynomial in {-s} of degree m+ 1. (We will prove that, in general, it will be of degree m+ d, where d is the dimension of V ; so the ξ-degrees and the s-degrees are linked.) Hence it is periodic (with period 1), and it coincides with a polynomial on each semi-open interval ]n, n + 1]. In particular, it is left-continuous.

To describe this structure in general, we introduce the algebras of step-polynomials and quasi-polynomials on V . A (rational) step-polynomial is an element of the algebra of functions on V generated by the functions

s → { λ, s }, where λ ∈ Q d . If qλ ∈ Z d , then s → { λ, s } is a function periodic modulo qZ d .
A quasi-polynomial is an element of the algebra of functions on V generated by step-polynomials and ordinary polynomials. Thus a step-polynomial is periodic with respect to some common multiple qZ d , and a quasi-polynomial f (s) is piecewise polynomial in the sense that it restricts to a polynomial function on any alcove associated with the rational linear forms λ ∈ Q d entering in its coefficients. (Alcoves are open polyhedral subsets of V defined in Definition 2.19).

Our first result is to prove that the homogeneous components M L (s+ c) [m] (ξ) are such step-polynomial functions of s, and we compute their degrees as step-polynomials. It turns out that the degree as steppolynomial functions of s and the homogeneous degree in ξ are linked. This bidegree structure gives a blueprint for constructing algorithms, based on series expansions in a constant number of variables, that extract refined asymptotics from the generating function. (We introduced such algorithms in [START_REF]Computation of the highest coefficients of weighted Ehrhart quasipolynomials of rational polyhedra[END_REF][START_REF] Baldoni | Intermediate sums on polyhedra: Computation and real Ehrhart theory[END_REF] to compute coefficients of Ehrhart quasipolynomials; algorithms for general parametric polyhedra will appear in the forthcoming paper [START_REF]Three Ehrhart quasi-polynomials[END_REF].) Furthermore, we prove that these homogeneous component functions enjoy the following property of one-sided continuity (Proposition 2.28): Let s ∈ V . For any v ∈ Lc, we have

lim t→0 t>0 M L (s + tv, c) [m] (ξ) = M L (s, c) [m] (ξ).
1.4. Second contribution: A new, Fourier-theoretic proof of the Baldoni-Berline-Vergne approximation theorem. Our second main result concerns the Fourier series of the periodic function s → M L (s + c)(ξ), in the sense of periodic L 2 -functions with values in the space of meromorphic functions of ξ. The Fourier coefficient at γ ∈ Z d is easy to compute: it is 0 if γ is not orthogonal to L, and otherwise it is the meromorphic continuation of the integral

I(c)(ξ + 2iπγ) = c e ξ+2iπγ,x dx.
We prove that s → M L (s + c)(ξ) is the sum of its Fourier series, in the above sense. As a corollary, Theorem 3.1, we obtain the Fourier expansion (Poisson formula) of the homogeneous component

M L (s, c) [m] (ξ) = γ∈Λ * ∩L ⊥ e 2iπγ,s I(c)(ξ + 2iπγ) [m] . (1.2)
For instance, in the dimension one case, we recover the well-known Fourier series of the Bernoulli polynomials, for k ≥ 1,

B k ({s}) k! = - n =0 e 2iπns (2iπn) k .
We also determine the poles and residues of S L (s + c)(ξ) (Proposition 3.5). This will be of importance for the forthcoming paper [START_REF]Three Ehrhart quasi-polynomials[END_REF].

We then give a new proof of the Baldoni-Berline-Vergne theorem [START_REF] Baldoni | Local Euler-Maclaurin expansion of Barvinok valuations and Ehrhart coefficients of rational polytopes[END_REF] on approximating the discrete generating function S(s + c) of an affine cone by a linear combination of functions S L (s + c). We use Fourier analysis in this proof, as did Barvinok [START_REF]Computing the Ehrhart quasi-polynomial of a rational simplex[END_REF] in his proof of his theorem regarding the highest k + 1 coefficients of Ehrhart quasi-polynomials. We sketch the crucial idea.

Let 0 ≤ k ≤ d and let L be a family of subspaces L of V which contains the faces of codimension ≤ k of c and is closed under sum. Consider the subset L∈L L ⊥ of V * and write its indicator function as a linear combination of the indicator functions of the spaces L ⊥ :

L∈L L ⊥ = L∈L ρ(L)[L ⊥ ].
We define a function that we call Barvinok's patched generating function by

S L (s + c)(ξ) = L∈L ρ(L)S L (s + c)(ξ).
Let us compute the difference S(s+c)(ξ)-S L (s+c)(ξ). By the Poisson formula, we have (in the sense of local L 2 -functions of s)

S(s + c)(ξ) = γ∈Λ * I(s + c)(ξ + 2iπγ)
whereas for each of the terms corresponding to L ∈ L,

S L (s + c)(ξ) = γ∈Λ * ∩L ⊥ I(s + c)(ξ + 2iπγ). As [ L∈L L ⊥ ] = L∈L ρ(L)[L ⊥ ], we obtain S(s + c)(ξ) -S L (s + c)(ξ) = γ∈Λ * γ / ∈ L∈L L ⊥ I(s + c)(ξ + 2iπγ).
(1.

3)

The poles of the function ξ → I(s + c)(ξ + 2iπγ) are on a collection of affine hyperplanes depending on the position of γ. For γ outside of L∈L L ⊥ , which is what we sum over in (1.3), the homogeneous components of ξ-degree ≤ -d + k vanish (Proposition 4.8).

As a consequence of the results on the bidegree structure, Equation (1.3) actually holds in the sense of local L 2 -functions of s, separately for each of the homogeneous components in ξ-degree. Using the one-sided continuity results, it follows that it actually holds as a pointwise result for all s.

This yields a straightforward proof of the Baldoni-Berline-Vergne approximation theorem (Theorem 4.7), i.e., the fact that the functions S(s + c)(ξ) and S L (s + c)(ξ) have the same homogeneous components in ξ-degree ≤ -d + k. We showed in [START_REF]Computation of the highest coefficients of weighted Ehrhart quasipolynomials of rational polyhedra[END_REF] that this approximation theorem implies generalizations of Barvinok's results in [START_REF]Computing the Ehrhart quasi-polynomial of a rational simplex[END_REF] on the highest k + 1 coefficients of Ehrhart quasi-polynomials. In the forthcoming paper [START_REF]Three Ehrhart quasi-polynomials[END_REF], we extend these results to the case of parametric polytopes.

Intermediate generating functions S L

Λ (p)(ξ) 2.1. Notations. In this paper, V is a rational vector space of dimension d, that is to say V is a finite-dimensional real vector space with a lattice denoted by Λ. We will need to consider subspaces and quotient spaces of V , this is why we cannot simply let

V = R d and Λ = Z d . A subspace L of V is called rational if L ∩ Λ is a lattice in L.
If L is a rational subspace, V /L is also a rational vector space. Its lattice, the image of Λ in V /L, is called the projected lattice and denoted by Λ V /L . A rational space V , with lattice Λ, has a canonical Lebesgue measure for which V /Λ has measure 1, denoted by dm Λ (x), or simply dx.

A point s ∈ V is called rational if there exists q ∈ Z, q = 0, such that qs ∈ Λ. A rational affine subspace is a rational subspace shifted by a rational element s ∈ V . A semi-rational affine subspace is a rational subspace shifted by any element s ∈ V .

In this article, a (convex) rational polyhedron p ⊆ V is the intersection of a finite number of closed halfspaces bounded by rational hyperplanes, a (convex) semi-rational polyhedron is the intersection of a finite number of closed halfspaces bounded by semi-rational hyperplanes. The word convex will be implicit. For instance, if p ⊂ V is a rational polyhedron, t is a real number and s is any point in V , then the dilated polyhedron tp and the shifted polyhedron s + p are semirational. All polyhedra will be semi-rational in this paper. When a stronger assumption is needed, it will be stated explicitely.

In this article, a cone is a convex polyhedral rational cone (with vertex 0) and an affine cone is the shifted set s + c of a rational cone c by any s ∈ V . A cone c is called simplicial if it is generated by linearly independent elements of V . A simplicial cone c is called unimodular if it is generated by independent lattice vectors v 1 , . . . , v k such that {v 1 , . . . , v k } is part of a basis of Λ. An affine cone a is called simplicial (respectively, unimodular) if the associated cone is. An (affine) cone is called pointed if it does not contain a line.

A polytope p is a compact polyhedron. The set of vertices of p is denoted by V(p). For each vertex s, the cone of feasible directions at s is denoted by c s .

The dual vector space of V is denoted by V * . If L is a subspace of V , we denote by L ⊥ ⊂ V * the space of linear forms ξ ∈ V * which vanish on L. The dual lattice of Λ is denoted by Λ * ⊂ V * . Thus Λ * , Λ ⊆ Z.

The indicator function of a subset E is denoted by [E].

Basic properties of intermediate generating functions. If

p is a polytope in the vector space V , its generating function S Λ (p)(ξ) defined by x∈p∩Λ e ξ,x is a holomorphic function on the complexified dual space V * C . This is the reason why we consider functions on the dual space V * in the following definition. Definition 2.1. (a) We denote by M ℓ (V * ) the ring of meromorphic functions around 0 ∈ V * C which can be written as a quotient

φ(ξ) N j=1 ξ,w j
, where φ(ξ)

is holomorphic near 0 and w j are non-zero elements of V in finite number. (b) We denote by R [≥m] (V * ) the space of rational functions which can be written as

P (ξ) N j=1 ξ,w j
, where P is a homogeneous polynomial of degree greater or equal to m + N. These rational functions are said to be homogeneous of degree at least m. (c) We denote by R [m] (V * ) the space of rational functions which can be written as

P (ξ) N j=1 ξ,w j
, where P is homogeneous of degree m + N.

These rational functions are said to be homogeneous of degree m.

A function in R [m] (V * ) need not be a polynomial, even if m ≥ 0. For instance, ξ → ξ 1 ξ 2 is homogeneous of degree 0. Definition 2.2. For φ ∈ M ℓ (V * ), not necessarily a rational function, the homogeneous component φ [m]
of degree m of φ is defined by considering φ(τ ξ) as a meromorphic function of one variable τ ∈ C, with Laurent series expansion

φ(τ ξ) = m≥m 0 τ m φ [m] (ξ). Thus φ [m] ∈ R [m] (V * ).
The intermediate generating functions of polyhedra which we study in this article are elements of M ℓ (V * ) which enjoy the following valuation property. Definition 2.3. An M ℓ (V * )-valued valuation on the set of semi-rational polyhedra p ⊆ V is a map F from this set to the vector space M ℓ (V * ) such that whenever the indicator functions [p i ] of a family of polyhedra p i satisfy a linear relation i r i [p i ] = 0, then the elements F (p i ) satisfy the same relation

i r i F (p i ) = 0.
Recall some of the definitions we introduced in [START_REF] Baldoni | Intermediate sums on polyhedra: Computation and real Ehrhart theory[END_REF].

Proposition 2.4. Let L ⊆ V be a rational subspace. There exists a unique valuation which associates a meromorphic function S L Λ (p) ∈ M ℓ (V * ) to every semi-rational polyhedron p ⊆ V , so that the following properties hold:

(i) If p contains a line, then S L Λ (p) = 0. (ii) S L Λ (p)(ξ) = y∈Λ V /L p∩(y+L) e ξ,x dx, (2.1)
for every ξ ∈ V * such that the above sum converges. Here, Λ V /L is the projected lattice and dx is the Lebesgue measure on y + L defined by the intersection lattice L ∩ Λ. When there is no risk of confusion, we will drop the subscript Λ. The intermediate generating function interpolates between the integral

I Λ (p)(ξ) = p e ξ,x dx
which corresponds to L = V , and the discrete sum

S Λ (p)(ξ) = x∈p∩Λ e ξ,x
which corresponds to L = {0}.

Formula (2.1) does not hold around ξ = 0 when p is not compact. Near ξ = 0, S L Λ (p)(ξ) has to be defined by analytic continuation. For instance in dimension one, with

L = V = R, the integral ∞ 0 e ξx dx = -1
ξ converges only for ξ < 0. Similarly the discrete sum n≥0 e ξn = 1 1-e ξ converges only for ξ < 0.

Let us give the simplest example of the meromorphic functions S L Λ (p)(ξ) so obtained when V = R is one-dimensional. The formulae are written in terms of the fractional part {t} ∈ [0, 1[ of a real number t, such that t -{t} ∈ Z (see Figure 2.3).

Example 2.6. Let V = R, Λ = Z, and consider the cones R ≥0 and R ≤0 . Then

S R Z (s + R ≥0 )(ξ) = - e sξ ξ , S R Z (s + R ≤0 )(ξ) = e sξ ξ while S {0} Z (s + R ≥0 )(ξ) = e sξ e {-s}ξ 1 -e ξ , S {0}
Z (s + R ≤0 )(ξ) = e sξ e -{s}ξ 1 -e -ξ .
For L = {0}, the fact that S L Λ (p) is actually an element of M ℓ (V * ), is proven in [START_REF] Baldoni | Intermediate sums on polyhedra: Computation and real Ehrhart theory[END_REF], as a consequence of explicit computations which we recall in the next section.

The valuation p → S L Λ (p)(ξ) extends by linearity to the space of linear combinations of indicator functions of semi-rational polyhedra. In particular, if p is a semi-open polytope defined by rational equations and inequalities, S L Λ (p)(ξ) is holomorphic and still given by Equation (2.1).

Let us note an obvious but important property.

Lemma 2.7. If v ∈ Λ + L, let v + p be the shifted polyhedron, then

S L Λ (v + p)(ξ) = e ξ,v S L Λ (p)(ξ). 2.3.
Case of a simplicial cone. We recall some results of [START_REF] Baldoni | Intermediate sums on polyhedra: Computation and real Ehrhart theory[END_REF].

We look first at the discrete generating function. Let c be a simplicial cone and let v i , i = 1, . . . , d, be lattice generators of its edges (we do not assume that the v i 's are primitive

). Let b = d i=1 [0, 1[ v i , the corresponding semi-open cell. Let vol Λ (b) = |det Λ (v 1 , . . . , v d )|
be its volume with respect to the Lebesgue measure defined by the lattice. Then

I Λ (s + c)(ξ) = e ξ,s (-1) d vol Λ (b) d i=1 ξ, v i .
(2.

2)

The discrete generating function for the cone can be expressed in terms of that of the semi-open cell:

S Λ (s + c)(ξ) = S Λ (s + b)(ξ) 1 d i=1 (1 -e ξ,v i ) . (2.3)
It follows from (2.3) that the intermediate functions S Λ (s + c)(ξ) belong to the space M ℓ (V * ). More precisely, their poles are given by the edges of the cone. Lemma 2.8. Let c be a polyhedral cone with edge generators v i , i = 1, . . . , N and let s ∈ V . The function N i=1 ξ, v i S Λ (s + c)(ξ) is holomorphic near ξ = 0.

Proof. The case where the cone c is simplicial follows immediately from (2.3), as S Λ (s + b)(ξ) is holomorphic. The general case follows from the valuation property, by using a decomposition of c into simplicial cones without added edges. 3 3 Suppose c is generated by v i , i = 1, . . . , N . Triangulating c without adding edges gives a primal decomposition of the form

[c] = j [c j ] + j ǫ j [l j ]
, where c j are (full-dimensional) simplicial cones and l j are lower-dimensional cones that arise in an inclusion-exclusion formula with coefficients ǫ j . Both c j and l j are generated by subsets of v i , i = 1, . . . , N . As shown in [START_REF] Köppe | Computing parametric rational generating functions with a primal Barvinok algorithm[END_REF][START_REF] Brion | Residue formulae, vector partition functions and lattice points in rational polytopes[END_REF], we can also construct decompositions that only involve full-dimensional cones. For example, as shown in [START_REF] Köppe | Computing parametric rational generating functions with a primal Barvinok algorithm[END_REF], we can find a decomposition of the form [c] = j [c j ], where cj are fulldimensional semi-open cones whose closures are c j . Then, as shown in [START_REF] Brion | Residue formulae, vector partition functions and lattice points in rational polytopes[END_REF], modulo indicator functions of cones with lines, we can replace the semi-open cones cj by closed cones cj and thus obtain a decomposition of the form [c] ≡ j ǫ j [c j ] (modulo indicator functions of cones with lines), where ǫ j ∈ {±1} and cj are simplicial cones which are generated by subsets of ±v i , i = 1, . . . , N . Next, we consider the intermediate generating function in the case where c is simplicial and L is one of its faces. In this case, the intermediate generating function S L Λ (s + c) decomposes as a product. For I ⊆ {1, . . . , d}, we denote by L I the linear span of the vectors v i , i ∈ I. Let I c be the complement of I in {1, . . . , d}. For x ∈ V , we write x = x I + x I c with respect to the decomposition V = L I ⊕ L I c . Thus we identify the quotient V /L I with L I c and we denote the projected lattice by Λ I c ⊂ L I c . Write c I for the cone generated by the vectors v j , for j ∈ I and c I c for the cone generated by the vectors v j , for j ∈ I c . The projection of the cone c on V /L I = L I c identifies with c I c . We write also ξ = ξ I + ξ I c , with respect to the decomposition V * = L * I ⊕ L * I c . Then we have the product formula

S L I Λ (s + c)(ξ) = S Λ I c (s I c + c I c )(ξ I c ) I Λ∩L I (s I + c I )(ξ I ). (2.4)
Finally, the general case is reduced to the case where c is simplicial and L is parallel to one of its faces by the Brion-Vergne decomposition (Theorem 19 in [START_REF] Baldoni | Intermediate sums on polyhedra: Computation and real Ehrhart theory[END_REF]), which we summarize in the following proposition and illustrate on an example in Figure 1.

Proposition 2.9 (Brion-Vergne decomposition). Let c be a full-dimensional cone. Then there exists a decomposition of its indicator function

[c] ≡ i ǫ i [c i ],
where each c i is a simplicial full-dimensional cone with Proof. The case where c is simplicial is Theorem 19 in [START_REF] Baldoni | Intermediate sums on polyhedra: Computation and real Ehrhart theory[END_REF]. Moreover, for any full-dimensional cone c, there exists a decomposition [c] ≡ a ǫ a [c a ] (modulo indicator functions of cones with lines), where c a are fulldimensional simplicial cones. 4 Lemma 2.8 holds also for intermediate generating functions S L Λ (s + c)(ξ). We will deduce it below from the Poisson summation formula for S L Λ (s + c)(ξ), (Theorem 3.1), and the following weaker result. Lemma 2.10. For a given cone c, there exist a finite number of vectors w j ∈ Λ such that N j=1 ξ, w j S L Λ (s + c)(ξ) is holomorphic near ξ = 0. In other words, the function S L Λ (s + c)(ξ) belongs to the space M ℓ (V * ). Proof. By Proposition 2.9 and the valuation property, we have

S L Λ (s + c)(ξ) = i ǫ i S L Λ (s + c i )(ξ),
where each c i is simplicial with a face parallel to L. However, this process may introduce new edges. Finally, when c is a simplicial cone with a face parallel to L, the result follows from Formulas (2.4) and (2.3).

Let us give some examples when V is two-dimensional. 4 The most well-known way to construct such a decomposition is using the "duality trick" (going back to [START_REF] Brion | Points entiers dans les polyèdres convexes[END_REF] Example 2.11 (positive quadrant). Let V = R 2 , Λ = Z 2 , and let c be the positive quadrant. For s = (s 1 , s 2 ) and ξ = (ξ 1 , ξ 2 ), S L Z (s + c)(ξ) is given by

e s 1 ξ 1 +s 2 ξ 2 e {-s 1 }ξ 1 e {-s 2 }ξ 2 (1 -e ξ 1 ) (1 -e ξ 2 ) , if L = {0}, e s 1 ξ 1 +s 2 ξ 2 e {-(s 1 +s 2 )}ξ 1 1 -e ξ 1 - e {-(s 1 +s 2 )}ξ 2 1 -e ξ 2 1 ξ 1 -ξ 2 , if L = R(1, -1), e s 1 ξ 1 +s 2 ξ 2 e {s 2 -s 1 }ξ 1 1 -e ξ 1 - e -{s 2 -s 1 }ξ 2 1 -e -ξ 2 -1 ξ 1 + ξ 2 , if L = R(1, 1).
(2.5) The first formula just follows from (2.3). The second and the third formula follow from Brion-Vergne decompositions and the product formula (2.4). The decomposition used for the third formula, for

L = R(1, 1), is [c] = [c 1 ] -[c 2 ] -[{x 1 ≥ 0}],
where

c 1 = {x 2 ≥ 0, x 1 -x 2 ≥ 0} and c 2 = {x 1 ≥ 0, x 1 -x 2 ≥ 0},
as depicted in Figure 1 (top). The decomposition is not unique. We can compute S L (s + c) using the other Brion-Vergne decomposition, depicted in Figure 1 (bottom),

[c] = -[c ′ 1 ] + [c ′ 2 ] + [{x 2 ≥ 0}], where c ′ 1 = {x 2 ≥ 0, x 1 -x 2 ≤ 0} and c ′ 2 = {x 1 ≥ 0, x 1 -x 2 ≤ 0}.
Then we obtain an expression of S L (s + c) in terms of {s 1 -s 2 } instead of {s 2 -s 1 }.

Intermediate sum S L

Λ (s + c)(ξ) as a function of the pair (s, ξ).

Step-polynomials and quasi-polynomials on a rational space. In this section, c is a rational cone of full dimension d.

The function M L

Λ (s, c)(ξ). We study the properties of S L Λ (s + c)(ξ) considered as a function of the two variables s ∈ V , ξ ∈ V * . Actually, as we will see, these properties are more striking and useful when read on the function

M L Λ (s, c)(ξ) = e -ξ,s S L Λ (s + c)(ξ). (2.6)
The following lemma is immediate.

Lemma 2.12. Let p be a semi-rational polyhedron. Let s ∈ V , and let M L Λ (s, p)(ξ) = e -ξ,s S L Λ (s + p)(ξ). Then, for v ∈ Λ + L, we have

M L Λ (s + v, p)(ξ) = M L Λ (s, p)(ξ).
Thus the function s → M L Λ (s, p)(ξ) can be considered as a function on V /L which is periodic with respect to the projected lattice Λ V /L . We will often drop the subscript Λ.

e {-s 1 }ξ 1 e {-s 2 }ξ 2 (1 -e ξ 1 ) (1 -e ξ 2 ) , if L = {0}, (2.7a) e {-(s 1 +s 2 )}ξ 1 1 -e ξ 1 - e {-(s 1 +s 2 )}ξ 2 1 -e ξ 2 1 ξ 1 -ξ 2 , if L = R(1, -1), (2.7b) e {s 2 -s 1 }ξ 1 1 -e ξ 1 - e -{s 2 -s 1 }ξ 2 1 -e -ξ 2 -1 ξ 1 + ξ 2 , if L = R(1, 1). (2.7c) 2.4.2.
Step-polynomials and quasi-polynomials on V . A crucial role in our study is played by the individual homogeneous components

S L (s + c) [m] (ξ) and M L (s, c) [m] (ξ).
A pleasant feature is that, when c is fixed, the homogeneous component of ξ-degree m can be viewed as a function of s ∈ V with values in a finite-dimensional vector space, namely the space of rational functions of homogeneous ξ-degree m which can be written in the form P (ξ) j ξ,w j , where the family of vectors w j is given by Lemma 2.10.

We introduce an algebra of functions on V × V * in order to describe these homogeneous components. Let us start with an example.

Example 2.14 (Continuation of Example 2.11). Let L = R(1, 1). We expand (2.7c), using the Bernoulli polynomials, defined by

e tz z e z -1 = ∞ n=0 B n (t) n! z n , (2.8)
obtaining

M L (s, c) [-2] (ξ) = 1 ξ 1 ξ 2 , M L (s, c) [-1] (ξ) = 0, M L (s, c) [0] (ξ) = B 2 ({s 2 -s 1 }) 2 = {s 2 -s 1 } 2 -{s 2 -s 1 } + 1 6 2 , M L (s, c) [1] (ξ) = B 3 ({s 2 -s 1 }) 3! (ξ 1 -ξ 2 ) = {s 2 -s 1 } 3 -3 2 {s 2 -s 1 } 2 + 1 2 {s 2 -s 1 } 6 (ξ 1 -ξ 2 ).
From these formulas, we obtain

S L (s + c) [-2] (ξ) = 1 ξ 1 ξ 2 , S L (s + c) [-1] (ξ) = s 1 ξ 1 + s 2 ξ 2 ξ 1 ξ 2 , S L (s + c) [0] (ξ) = (s 1 ξ 1 + s 2 ξ 2 ) 2 + ξ 1 ξ 2 ({s 2 -s 1 } 2 -{s 2 -s 1 } + 1 6 ) 2ξ 1 ξ 2 .
We observe that the numerators above are written as polynomial functions of s 1 , s 2 , {s 2 -s 1 }, ξ 1 , ξ 2 . We next describe the general case.

Let

V * Q = Λ * ⊗ Q be the set of rational elements of V * . Definition 2.15. Q(V ) is the algebra of functions on V generated by the functions s → { λ, s }, where λ ∈ V * Q . An element of Q(V ) is called a (rational) step-polynomial on V .
Remark 2.16. Note that there are many relations between these generators. For example, if V = R, consider for λ ∈ Q the function f λ (s) = 1 -({λs} + {-λs}), which is 1 if λs is an integer and 0 otherwise. Then we have the polynomial relation

f 1 (s) = f 2 (s)f 3 (s).
Since the generators s → { λ, s } are bounded functions, it follows that a step-polynomial is a bounded function on V .

The space Q(V ) has a natural filtration, where Q [≤k] (V ) is the subspace generated by products of at most k functions { λ, s }.

For η ∈ Λ * , the function s → { η, s } is Λ-periodic. For a given step-polynomial f (s), let q ∈ N be such that qλ ∈ Λ * for all the λ's involved in an expression of f (s) (such an expression is not unique). Then f is qΛ-periodic.

Next, we consider the algebra of functions on V generated by Q(V ) and P(V ), where P(V ) is the algebra of polynomial functions on V . It is clear that this algebra is the tensor product Q(V ) ⊗ P(V ). We denote it by QP(V ).

Definition 2.17. The elements of QP(V ) = Q(V ) ⊗ P(V ) are called quasi-polynomials on V . Now, let Ψ be a finite subset of V * Q . There corresponds a subalgebra of quasi-polynomials on V . Definition 2.18. (i) Q Ψ (V ) is the algebra of functions on V generated by the functions s → { η, s }, with η ∈ Ψ. (ii) Q Ψ

[≤k] (V ) is the subspace of Q Ψ (V ) generated by products of at most k functions { η, s }, with η ∈ Ψ. The quasi-polynomials in QP Ψ (V ) are piecewise polynomial, in a sense which we describe now. Definition 2.19. Let Ψ be a finite subset of V * Q . We consider the hyperplanes in V defined by the equations η, x = n for η ∈ Ψ and n ∈ Z.

A connected component of the complement of the union of these hyperplanes in V is called a Ψ-alcove.

Thus, an alcove is the interior of a polyhedron whose faces are some of the hyperplanes above. If Ψ generates V * , all alcoves are bounded. Otherwise, they are unbounded. If s is any element of V , and v ∈ V is a fixed element such that η, v = 0 for η ∈ Ψ, then the curve s + tv is contained in a Ψ-alcove for small t < 0.

If η ∈ Ψ, the restriction to any Ψ-alcove of the function s → { η, s } is affine. Therefore the restriction of a quasi-polynomial f (s) ∈ Q Ψ

[≤k] (V ) ⊗ P [r] (V ) to an alcove is a polynomial in s of degree ≤ k + r. This motivates the following definition.

Definition 2.20. (i) A function f (s) ∈ Q Ψ

[≤k] (V ) ⊗ P [r] (V ) is said to be of polynomial degree r and of local degree (at most) k + r.

(ii) We define QP Ψ

[≤q] (V ) to be the subspace of quasi-polynomials of local degree at most q.

In Figure 3, we draw the graph of a quasi-polynomial function on R (with Λ = Z and Ψ = {1}) of local degree 4.

2.4.3.

Properties of homogeneous components of generating functions of shifted cones. We start with the case L = {0}. Given a cone c ⊂ V , we define a subalgebra of step-polynomials associated with c. The fundamental fact here is the existence of a decomposition of the indicator function of c as a signed sum

[c] ≡ u ǫ u [u],
(2.9)

where the cones u are unimodular, and the congruence is modulo the space spanned by indicator functions of cones which contain lines. If c is full-dimensional, we can assume that the cones u are also fulldimensional, see [START_REF]Integer points in polyhedra[END_REF] for instance. By the valuation property, we have

S(s + c)(ξ) = u ǫ u S(s + u)(ξ).
For each unimodular cone u in (2.9), let v u j ∈ Λ, 1 ≤ j ≤ d, be the primitive generators of the cone u, and let η u j ∈ Λ * , 1 ≤ j ≤ d, be the dual basis. Definition 2.21. We denote by Ψ c ⊂ Λ * the set of all η u j , for j = 1, . . . , d, where u runs over the set of unimodular cones entering in the decomposition (2.9) of [c]. Ψ c depends of the choice of the decomposition, but we do not record it in the notation, for brevity.

We can now state the important bidegree properties of the homogeneous components of the functions S(s + c)(ξ) and M(s, c)(ξ). Here "bidegree" refers to the interaction between the (local) degree in s and the homogeneous degree in ξ.

Q Ψc [≤m+d] (V ) ⊗ R [m] (V * ). (ii) The function (s, ξ) → S(s + c) [m] (ξ) belongs to the space QP Ψc [≤m+d] (V ) ⊗ R [m] (V * ).
More precisely,

S(s + c) [m] (ξ) = m+d r=0 ξ, s r r! M(s, c) [m-r] (ξ).
(iii) The homogeneous component in ξ of lowest degree has degree m = -d and does not depend on s. It is given by the integral

S(s + c) [-d] (ξ) = M(s, c) [-d] (ξ) = I(c)(ξ).
To rephrase (ii), we can say that the numerator of the homogeneous component S(s + c) [m] (ξ) is a quasi-polynomial function of s (with coefficients polynomials in ξ), and the local degree in s of this quasi-polynomial (and so its complexity) grows with the homogeneity degree m in ξ.

Proof. Let u be one of the unimodular cones in the decomposition of [c].

We write ξ = j ξ j η u j . Then S(s + u)(ξ) is directly computed by summing a multiple geometric series (cf. Example 2.6), hence

M(s, u)(ξ) = exp j {-η u j , s }ξ j d j=1 1 1 -e ξ j , M(s, u) [m] (ξ) = d+m k=0 ( j {-η u j , s }ξ j ) k k! d j=1 1 1 -e ξ j [m-k] .
In this formula, it is clear that the k-th term belongs to Q Ψc

[≤k] (V ) ⊗ R [m] (V * ). As k ≤ m + d, we obtain (i). The homogeneous components S(s + c) [m] (ξ) are immediately computed out of those of M(s, c)(ξ), hence (ii). Part (iii) was proved in [START_REF]Computation of the highest coefficients of weighted Ehrhart quasipolynomials of rational polyhedra[END_REF], Lemma 16. Now let L ⊆ V be any rational subspace. In order to obtain a similar result for the intermediate generating function S L (s + c)(ξ), we follow the steps of the proof of Lemma 2.10. First, we decompose [c] into a signed sum of simplicial cones with a face parallel to L. For each of these cones, we decompose the projected cone in V /L into a signed sum of cones which are unimodular with respect to the projected lattice Λ V /L . We thus have a collection of unimodular cones u ⊂ V /L. When (V /L) * is identified with L ⊥ ⊂ V * , the dual lattice (Λ V /L ) * is identified with Λ * ∩L ⊥ . For each u, we let v u j ∈ Λ V /L be primitive edge generators of u and consider the dual basis η u j ∈ Λ * ∩ L ⊥ .

Definition 2.23. We denote by Ψ L c ⊂ Λ * ∩ L ⊥ the set of all η u j .

Then the functions in Q Ψ L c (V ) are functions on V /L and are Λ V /Lperiodic. Using the product formula (2.4), the proof of the following theorem is similar to the case L = {0} (Theorem 2.22). Theorem 2.24. Let m ∈ Z.

(i) The function (s, ξ) → M L (s, c) [m] (ξ) belongs to the space

Q Ψ L c [≤m+d] (V ) ⊗ R [m] (V * ). (ii) The function (s, ξ) → S L (s + c) [m] (ξ) belongs to the space QP Ψ L c [≤m+d] (V ) ⊗ R [m] (V * ). More precisely S L (s + c) [m] (ξ) = m+d r=0 ξ, s r r! M L (s, c) [m-r] (ξ). (2.10) (iii)
The homogeneous component in ξ of lowest degree has degree m = -d and does not depend on s. It is given by the integral

S L (s + c) [-d] (ξ) = M L (s, c) [-d] (ξ) = I(c)(ξ). Remark 2.25. If L = V , then Ψ L c is empty, hence Q Ψ L c (V )
is just the scalars. Indeed, e -ξ,s I(s + c)(ξ) = I(c)(ξ) does not depend on s.

Remark 2.26. As we showed in [2, Theorems 31 and 38] and [4, Theorems 24 and 28], the computation of these functions and their homogeneous components can be made effective, and the bidegree structure, i.e., the interaction of the local degree in s and the homogeneous degree in ξ, takes a key role in extracting the refined asymptotics. We have developed Maple implementation of such algorithms, which work with a symbolic vertex s; the resulting formulas are naturally valid for any real vector s ∈ V .

2.5.

One-sided continuity. The meromorphic functions M L (s, c)(ξ) and S L (s + c)(ξ) and their homogeneous components M L (s, c) [m] (ξ) and S L (s + c) [m] (ξ) enjoy some continuity properties when s tends to s 0 along some directions that we will describe. Let us look again at the simplest example (Example 2.6). We have

S {0} Z (s + R ≥0 )(ξ) = e sξ e {-s}ξ
1 -e ξ , and

S {0} Z (s + R ≤0 )(ξ) = e sξ e -{s}ξ
1 -e -ξ . Then observe that as functions of s, the first formula is continuous from the left, while the second formula is continuous from the right. These directions are the opposite of the direction of the corresponding cones, and the result is intuitively clear. For instance, the set (s + R ≥0 ) ∩ Z itself does not change when s is moved slightly to the left; but it does change if s is moved slightly to the right from an integer.

s ′ + tv + c, t > 0 0 s + tv + c, t > 0 L + Λ s s ′ + c s ′ s + c c L -c
We state a generalization of this result in higher dimensions. In order to state the result, we observe that, in Theorem 2.24, the infinitedimensional space R [m] (V * ) can be replaced by the following finitedimensional subspace. Definition 2.27. Let (v j ) N j=1 be a set of vectors in V such that the function N j=1 ξ, v j S L (s+c)(ξ) is holomorphic near ξ = 0. Then as rational functions of ξ, both M L (s, c) [m] (ξ) and S L (s + c) [m] (ξ) lie in the finitedimensional space of functions f (ξ) such that N j=1 ξ, v j f (ξ) is a polynomial of degree m + N. We denote this space by

1 N j=1 v j P [m+N ] (V * ). Proposition 2.28. Let (v j ) N j=1 be a set of vectors in V such that the function N j=1 ξ, v j S L (s + c)(ξ) is holomorphic near ξ = 0. (i) The restriction of s → M L (s, c) [m] (ξ) and s → S L (s + c) [m] (ξ) to a Ψ L c -alcove a ⊂ V are polynomial functions of s with values in the finite-dimensional space 1 N j=1 v j P [m+N ] (V * ). s + tv + c, t > 0 s 0 L + Λ c s + c L -c = V Figure 5.
One-sided continuity of the functions M L (s, c)(ξ) and S L (s+c)(ξ) and their homogeneous components, as functions of the apex s. In this example, Lc = V , and thus the functions actually depend continuously on s.

(ii) Let s ∈ V . For any v ∈ Lc, we have the following one-sided limit (cf. Figures 4 and5),

lim t→0 t>0 M L (s + tv, c) [m] (ξ) = M L (s, c) [m] (ξ).
Proof. Part (i) is an immediate consequence of Theorem 2.24.

For part (ii) we assume that c is pointed, otherwise there is nothing to prove. Recall the definition of S L (s + c)(ξ). Fix s 0 ∈ V . There is a non-empty open subset U ⊂ V * C such that for s near s 0 and ξ ∈ U, the following sum

S L (s + c)(ξ) = y∈Λ V /L (s+c)∩(y+L)
e ξ,x dx converges uniformly to a holomorphic function of ξ. Intuitively, the lemma is based on the observation that if v ∈ Lc and t > 0 is small enough, then the projections of the shifted cones s + c and s + tv + c on V /L have the same lattice points. Let us look first at the extreme cases, L = {0} or L = V . If L = {0}, for v ∈ L-c and t > 0 small enough, the shifted cones s+c and s+tv+c have the same lattice points, hence S(s + tv + c)(ξ) = S(s + c)(ξ) for ξ ∈ U. It follows that these meromorphic functions are equal. If L = V , then S L (s + c)(ξ) = I(s + c)(ξ) = e ξ,s I(c)(ξ) depends continuously on the apex s. Now, let L be arbitrary. Let v ∈ Lc and t > 0 small enough. Then the projections of the shifted cones s + c and s + tv + c on V /L have the same lattice points. Consider a given y ∈ Λ V /L . If y does not lie in this projection, then (s+tv+c)∩(y+L) e ξ,x dx = 0. Otherwise, it is clear that the integral (s+tv+c)∩(y+L) e ξ,x dx depends continuously on t. Hence, for all y ∈ Λ V /L , we have lim

S L (s + tv + c)(ξ) = S L (s + c)(ξ),
uniformly for ξ ∈ U. The difficulty is that 0 / ∈ U. To deal with it, it is enough to prove that there exists a finite set of vectors v j ∈ V and a ball B ⊂ V * C of center 0 intersecting U, such that N j=1 ξ, v j S L (s + c)(ξ) is holomorphic and uniformly bounded on B, for s in neighborhood of a given s 0 . By the Montel compactness theorem, it will follow that lim

t→0 t>0 N j=1 ξ, v j S L (s + tv + c)(ξ) = N j=1 ξ, v j S L (s + c)(ξ)
uniformly for ξ ∈ B, therefore the limit will hold also for homogeneous components.

To prove the uniform boundedness property above, we use the Brion-Vergne decomposition (Proposition 2.9) of c as a signed sum of simplicial cones, each with a face parallel to L, modulo cones with lines. We take (v j ) to be the collection of all edge generators for all these cones. So now we need only prove uniform boundedness for a simplicial cone for which L is a face. By the product formula, we are reduced to the extreme cases S(s + c) and I(s + c). The latter is continuous with respect to s, so uniform boundedness holds. For the discrete sum, uniform boundedness follows from Formula (2.3).

Remark 2.29. Although the result is intuitively clear, a proof is needed because we have an infinite sum. Indeed, consider the sequence of holomophic functions f n (z) = e nz -1 nz . This sequence converges pointwise to 0 for ℜz < 0. However, the homogeneous components n k (k+1)! z k do not converge to 0.

Example 2.30. Let us look again at the positive quadrant from Examples 2.11 and 2.14, with L = R(1, 1) (see Figure 5). By means of the Brion-Vergne decomposition of the quadrant depicted in

L (s, c) [m] (ξ) in terms of the Bernoulli polynomial B m+2 ({s 2 -s 1 }). Let v 1 < 0, v 2 < 0, so v ∈ -c. s s + c L + Λ 0 s + tv + c, t > 0 c L -c Figure 6.
One-sided continuity of the functions M L (s, c)(ξ) and S L (s+c)(ξ) and their homogeneous components, as functions of the apex s. In this example, L-c is a halfspace, and so Proposition 2.28 only predicts onesided continuity. However, the functions actually depend continuously on s.

Then lim t→0,t>0 {s 2 + tv 2 -s 1 -tv 1 } = {s 2 -s 1 } if v 2 -v 1 > 0. But if v 2 -v 1 < 0 and s 2 -s 1 ∈ Z, then lim t→0,t>0 {s 2 + tv 2 -s 1 -tv 1 } = 1 while {s 2 -s 1 } = 0. However, observe that if t > 0 is small, then s 2 + tv 2 -s 1 -tv 1 / ∈ Z, hence {s 2 + tv 2 -s 1 -tv 1 } = 1 -{-(s 2 + tv 2 -s 1 -tv 1 )}.
Thus the limit statement in the lemma holds also for v 2 -v 1 < 0, due to the property of Bernoulli polynomials:

B n (1 -u) = (-1) n B n (u).
Another way to reach this conclusion is to use the other Brion-Vergne decomposition of the quadrant, depicted in Figure 1 (bottom). Then we obtain an expression of S L (s + c) in terms of {s 1 -s 2 } instead of {s 2 -s 1 }. We see here the well-known link between the valuation property of generating functions and the functional equation of Bernoulli polynomials.

Remark 2.31. Actually, the functions s → M L (s, c) [m] (ξ) and s → S L (s + c) [m] (ξ) enjoy stronger continuity properties on the boundary of alcoves than claimed in Proposition 2.28. For instance, for a twodimensional cone c, if L is not parallel to an edge of the cone and L = {0}, it is intuitively clear that these functions depend continuously on s, see Figure 6. It is also enlightening to check the continuity property on the formulas.

Poisson summation formula and Fourier series of

s → M L (s, c)(ξ) = e -ξ,s S L (s + c)(ξ)
The Poisson summation formula reads, for suitable functions φ on V ,

x∈Λ φ(x) = γ∈Λ * φ(2πγ).
Here φ is the Fourier transform of φ, with respect to the Lebesgue measure defined by Λ. Let us apply formally this formula to the series

S(s + c)(ξ) = x∈(s+c)∩Λ e ξ,x = x∈Λ e ξ,x [s + c](x). (3.1)
Formally, the Fourier transform of φ

(x) = e ξ,x [s + c](x) is φ(2πγ) = s+c e ξ+2iπγ,x dx = I(s + c)(ξ + 2iπγ).
So, heuristically, we obtain

S(s + c)(ξ) = γ∈Λ * I(s + c)(ξ + 2iπγ). (3.2)
This heuristic result admits a precise formulation given in Corollary 3.3 below, valid also for intermediate generating functions S L (s + c).

For a given γ ∈ Λ * , the function ξ → I(s+c)(ξ+2iπγ) belongs also to M ℓ (V * ). More precisely, if (v j ) are the generators of c, this function has simple hyperplane singularities near ξ = 0, with singular hyperplanes given by ξ, v j = 0, for the indices j such that γ, v j = 0. Thus we can also define the homogeneous components I(s + c)(ξ + 2iπγ) [m] , and

I(s + c)(ξ + 2iπγ) [m] belongs to R [m] (V * ).
For example, for n = 0, the expansion of -1 ξ+2iπn in homogeneous components is

- 1 ξ + 2iπn = ∞ m=0 (-1) m+1 (2iπn) m+1 ξ m .
3.1. Fourier series of M L (s, c)(ξ). The starting point is, once again, the important fact that the function

s → M L (s, c)(ξ) = e -ξ,s S L (s + c)(ξ),
which is a function on V /L, is periodic with respect to the projected lattice Λ V /L . Each homogeneous component M L (s, c) [m] (ξ) is periodic as well, and piecewise polynomial, hence bounded. We are going to compute its Fourier coefficients.

M L (s, c) [m] (ξ) = γ∈Λ * ∩L ⊥ e 2iπγ,s I(c)(ξ + 2iπγ) [m] . (3.3)
Proof. Given c and L, we decompose [c] ≡ i ǫ i [c i ], where now each cone c i is simplicial with a face parallel to L and full-dimensional (Proposition 2.9). By linearity of homogeneous components and Fourier coefficients, we can assume that c is simplicial with a face parallel to L.

Then we write S L (s + c)(ξ) as a tensor product of a discrete generating function in dimension k = codim L with a continuous one in dimension dim L. Thus, we are reduced to the cases L = {0} and L = V . We observe that the result is true when L = V , as M V (s, c)(ξ) = I(c)(ξ) does not depend on s.

There remains to prove the theorem for L = {0}. We will do this by reduction to the dimension one case as follows. If c ⊂ V is a fulldimensional cone, we can decompose [c] ≡ ǫ a [c a ] modulo indicators of cones with lines, where (c a ) is a finite set of unimodular cones of full dimension. By linearity of homogeneous components and Fourier coefficients, we can assume that c is unimodular. Then S(s + c) and I(c)(ξ + 2iπγ) are tensor products of corresponding one-dimensional generating functions. Thus the theorem follows from the dimension one case.

Thus, finally let us consider the dimension one case with L = {0}. Without loss of generality, let c = R ≥0 and Λ = Z. In the following, we write

n = γ ∈ Λ * = Z. Recall M(s, c)(ξ) = e {-s}ξ 1 -e ξ , I(c)(ξ + 2iπn) = - 1 ξ + 2iπn
.

To determine the left-hand side of (3.3), we write the Laurent series of M(s, c)(ξ), which is given by

M(s, c)(ξ) = e {-s}ξ 1 -e ξ = - 1 ξ - ∞ m=0 B m+1 ({-s}) (m + 1)! ξ m ,
where B m (t) is the Bernoulli polynomial. To compare this with the right-hand side of (3.3), note that the term in the sum for n = 0 gives the contribution -1 ξ , whereas for n = 0, I(c)(ξ + 2iπn) is holomorphic near ξ = 0, with Taylor series

- 1 ξ + 2iπn = ∞ m=0 (-1) m+1 (2iπn) m+1 ξ m .
Comparing coefficients, we see that we only need to verify the following Fourier series of -

Bm({-s}) m! for m ≥ 1, - B m ({-s}) m! = n∈Z,n =0 (-1) m (2iπn) m e 2iπns .
By replacing s with -s and n with -n in the sum, this formula becomes the more familiar Fourier series of the m-th periodic Bernoulli polynomial

B m ({s}) m! = - n∈Z,n =0
e 2iπns (2iπn) m .

(3.4)

Let us give a short proof of (3.4). Denote φ(s, ξ) = e sξ ξ e ξ -1 .

This is an holomorphic function of (s, ξ), for ξ in a small disc around 0. By definition of the Bernoulli polynomial, the Taylor series of φ(s, ξ)

at ξ = 0 is ∞ m=0 Bm(s)
m! ξ m . Fix ξ small, consider s → φ(s, ξ) as a L 2 -function of s ∈ [0, 1], and compute its nth Fourier coefficient. We can now take the Taylor series with respect to ξ of both extreme sides of these equalities, and we obtain that the nth Fourier coefficient of the m-th periodic Bernoulli polynomial Bm({s}) m! is -1 (2iπn) m for n = 0, and 0 if n = 0.

S L (s + c) [m] (ξ) = γ∈Λ * ∩L ⊥ I(s + c)(ξ + 2iπγ) [m] (3.5)
holds in the sense of locally L 2 -functions of s ∈ V with values in the finite-dimensional space

1 N j=1 v j P [m+N ] (V * ).
3.2. Poles and residues of S L (s + c)(ξ). As a first consequence of the Poisson formula and left-continuity properties, we determine the poles and residues of the intermediate generating functions. As we promised in Section 2.3, we can now prove the following result.

Proposition 3.4. Let c be a cone in V with edge generators v 1 , . . . , v N and let s be any point in V . Let L ⊆ V be a linear subspace. The product N j=1 ξ, v j • S L (s + c)(ξ) is holomorphic near ξ = 0.

Proof. It is enough to prove that N j=1 ξ, v j •M L (s, c)(ξ) is holomorphic near ξ = 0 or, equivalently, that for each homogeneous degree m ∈ Z, the product

N j=1 ξ, v j • M L (s, c) [m] (ξ) (3.6)
is a polynomial in ξ. By Theorem 3.1, (3.6) is polynomial in ξ for almost all s ∈ V /Λ. Moreover, by Proposition 2.28, (3.6) is continuous with respect to s on every alcove. For a given s 0 ∈ V , and any alcove a such that s 0 is in the boundary of (s

0 + c) ∩ a, N j=1 ξ, v j • M L (s 0 , c) [m] (ξ) = lim s→s 0 s∈a N j=1 ξ, v j • M L (s, c) [m] (ξ),
where the limit holds in the space of polynomials in ξ of degree m + N. It follows that (3.6) is a polynomial in ξ for every s ∈ V /Λ.

Furthermore, there is a nice formula for the residue along a hyperplane v ⊥ j ⊂ V * . Proposition 3.5. Let c be a cone in V and let s ∈ V . Let L ⊆ V be a linear subspace. Let v ∈ V . The projection V → V /Rv is denoted by p. The dual space (V /Rv) * is identified with the hyperplane v ⊥ ⊂ V * .

(i) The function ξ, v S L (s + c)(ξ) restricts to the hyperplane v ⊥ in a meromorphic function, element of M ℓ (v ⊥ ). (ii) If v is not an edge of c, then this restriction is 0. (iii) Let v ∈ Λ be a primitive vector, generating an edge of c. Then the restriction of ξ, v S L (s + c)(ξ) to v ⊥ is given by

ξ, v S L (s + c, Λ)(ξ) v ⊥ = -S p(L) (p(s + c), p(Λ)).
Proof. (i) and (ii) follow immediately from the previous proposition.

Let v be a primitive edge generator of c. We compute each homogeneous component of the restriction

( ξ, v M L (s, c)(ξ)) [m] | v ⊥ .
This restriction in the sum of the Fourier series of restrictions

γ∈Λ * ∩L ⊥ e 2iπγ,s ξ, v I(c)(ξ + 2iπγ) [m] v ⊥ .
By subdivision without added edges, 5 we can assume that c is simplicial, with primitive edge generators v

1 = v, v 2 , . . . , v d . Fix γ ∈ Λ * . Then ξ, v I(c)(ξ + 2iπγ) = |det Λ (v 1 , . . . , v d )|(-1) d ξ, v d j=1 ξ + 2iπγ, v j .
We can assume that v 1 belongs to a basis of Λ, so that |det

Λ (v 1 , . . . , v d )| = |det p(Λ) (p(v 2 ), . . . , p(v d ))|. If γ, v 1 = 0, we have ξ, v 1 d j=1 ξ + 2iπγ, v j v ⊥ 1 = 0. If γ, v 1 = 0, we have ξ, v 1 d j=1 ξ + 2iπγ, v j v ⊥ 1 = d j=2 ξ + 2iπγ, p(v j ) .
Hence, we have proved the equality

ξ, v 1 I(c)(ξ + 2iπγ) v ⊥ 1 = -I(p(c))(ξ + 2iπγ).
Then we complete the proof of (iii) as we did for Proposition 3.4.

Barvinok's patched generating functions. Approximation of the generating function of a cone

Following Barvinok [START_REF]Computing the Ehrhart quasi-polynomial of a rational simplex[END_REF], we introduce some particular linear combinations of intermediate generating functions of a polyhedron. 4.1. Barvinok's patched generating function associated with a family of slicing subspaces. Let L be a finite family of linear subspaces L ⊆ V which is closed under sum. Consider the subset

L∈L L ⊥ of V * . Because L ⊥ 1 ∩ L ⊥ 2 = (L 1 + L 2 ) ⊥ for any L 1 , L 2 , the family { L ⊥ : L ∈ L } is stable under intersection. Thus there exists a unique function ρ on L such that L∈L L ⊥ = L∈L ρ(L)[L ⊥ ].
We will say that L → ρ(L) is the patching function of L. It is related to the Möbius function of the poset L as follows. Let L be the poset obtained by adding a smallest element 0 to L. Denote by µ its Möbius function.

4.2.

Example: the patching function of a simplicial cone. For a subset f ⊆ V , the subspace lin(f) is defined as the linear subspace of V generated by p -q for p, q ∈ f. Definition 4.3. If p ⊂ V is a polyhedron, and k an integer, we denote by L k (p) the smallest family closed under sum which contains the subspace lin(f) for every face f of p of codimension ≤ k.

Let d = dim V and let c be a simplicial cone with edge generators v 1 , . . . , v d . We computed the patching function of L k (c) in [START_REF]Computation of the highest coefficients of weighted Ehrhart quasipolynomials of rational polyhedra[END_REF]. Let us recall the result. In the case of a simplicial cone, L k (c) is just the family of subspaces lin(f) for faces of codimension ≤ k. This family is already closed under sum. If L I with I ⊆ {1, . . . , d} is the linear space spanned by the vectors v i , i ∈ I, then L k (c) is the family of subspaces

L I with |I| ≥ d -k. Proposition 4.4. The patching function of L k (c) is given by ρ d,k (L I ) = (-1) |I|-d+k |I| -1 d -k -1 (4.1)
where a b = a! b!(a-b)! is the binomial coefficient. 4.3. Approximation of the generating function of a cone. In this section we state and prove an approximation theorem, inspired by the results of Barvinok in [START_REF]Computing the Ehrhart quasi-polynomial of a rational simplex[END_REF]. For a cone s + c, we construct a meromorphic function S L (s + c)(ξ) which approximates S(s + c)(ξ) in the sense that these two functions have the same lowest homogeneous degree components in ξ. A proof of this theorem, based on the local Euler-Maclaurin formula, appeared in [START_REF] Baldoni | Local Euler-Maclaurin expansion of Barvinok valuations and Ehrhart coefficients of rational polytopes[END_REF].

If c is simplicial, the set of faces of codimension ≤ k of c is already closed under sum, and its patching function is very simple (cf. Section 4.2). For this particular family L, we gave a simple proof of the theorem in [START_REF]Computation of the highest coefficients of weighted Ehrhart quasipolynomials of rational polyhedra[END_REF].

Below we will give a proof closer to the approach of Barvinok. It is based on the Poisson formula of Section 3 and on the following Proposition 4.8, which is analogous to Theorem 3.2 of [START_REF]Computing the Ehrhart quasi-polynomial of a rational simplex[END_REF]. Proof. We prove this statement by induction on the dimension d. Let S k (c) be the family of subspaces of V consisting of the spaces lin(f), where f runs over the faces of codimension k of c. As L∈S k (c) L ⊥ is contained in L∈L L ⊥ , it is sufficient to prove the proposition for γ / ∈ L∈S k (c) L ⊥ . We use the following formula (cf. [START_REF] Barvinok | Computing the volume, counting integral points, and exponential sums[END_REF], for instance), I(c)(ξ) = 1 ξ, v q ν q , v I(q)(ξ).

(4.4)

Here, the sum runs over the set of facets q of c. For each facet q, we take ν q ∈ V * to be the primitive outer normal vector, i.e., the linear form orthogonal to lin(q) which is outgoing with respect to c and primitive with respect to the dual lattice. The vector v is arbitrary. Therefore I(c)(ξ + 2iπγ) = 1 ξ + 2iπγ, v q ν q , v I(q)(ξ + 2iπγ).

(4.5)

Let us choose v so that γ, v = 0. Thus the factor 1 ξ+2iπγ,v is analytic near ξ = 0.

If k = 0, Formula (4.5) together with (2.2) shows that I(c)(ξ + 2iπγ) has no homogeneous term of ξ-degree ≤ -d, so I(c)(ξ + 2iπγ) belongs to M [≥-d+1] (V * ) as claimed.

If k ≥ 1, S k (c) is the union over the facets q of c of the families S k-1 (q). Hence, by the induction hypothesis, the meromorphic function I(q)(ξ+2iπγ) has no homogeneous term of ξ-degree ≤ -(d-1)+k-1 = -d + k, so I(c)(ξ + 2iπγ) belongs to M [≥-d+k+1] (V * ).

Example 4.9. Let c be the standard cone in R 3 , with generators e 1 , e 2 , e 3 . Thus I(c)(ξ) = -1 ξ 1 ξ 2 ξ 3 . Let γ = (γ 1 , γ 2 , γ 3 ).

First, let k = 2. Then L contains the subspaces Re j for j = 1, 2, 3. If γ / ∈ L∈L L ⊥ , then γ j = 0 for j = 1, 2, 3. Hence I(c)(ξ + 2iπγ) = -1 (ξ 1 + 2iπγ 1 )(ξ 2 + 2iπγ 2 )(ξ 3 + 2iπγ 3 ) is analytic near ξ = 0, so its expansion starts at homogeneous ξ-degree 0, and thus it belongs to M [≥0] (V * ).

Next, let k = 1. Then L contains the subspaces Re 1 +Re 2 , Re 2 +Re 3 , and Re 1 + Re 3 . If γ / ∈ L∈L L ⊥ , at least two of its coordinates must be nonzero, say γ 1 = 0 and γ 2 = 0. Then the factor

1 (ξ 1 +2iπγ 1 )(ξ 2 +2iπγ 2 )
is analytic near ξ = 0. So, at worst, if γ 3 = 0, the expansion of I(c)(ξ + 2iπγ) = Thus, by Proposition 4.8, we see that F [m] (s) vanishes for almost all s. For a given alcove a, the restriction to a of F [m] (s) is a polynomial function of s, therefore it vanishes for all s ∈ a. For a given s 0 ∈ V , and any alcove a intersecting s 0 + c and with s 0 in its boundary, F [m] (s 0 ) is the limit of F [m] (s), when s → s 0 , s ∈ a. Hence F [m] (s) vanishes for every s ∈ V . Equation (4.3) follows from (4.2) by multiplying by the analytic function e ξ,s .

  p h(x) dx and the sum of values of h(x) over the set of integer points of p, S(p, h) = x∈p∩Z d h(x).

Definition 2 .

 2 5. S L Λ (p)(ξ) is called the intermediate generating function of p (associated to the subspace L).

2 Figure 1 .

 21 Figure 1. Two Brion-Vergne decompositions of a cone c into cones with a face parallel to the subspace L, modulo cones with lines.

Figure 2 .

 2 Figure 2. The fractional part {t}

  ): We triangulate the dual cone c • ⊆ V * and obtain a decomposition [c • ] ≡ a [c • a ] (modulo indicator functions of lower-dimensional cones of V * ), where c • a are simplicial cones of V * . This implies the decomposition [c • ] ≡ a [(c • a ) • ] (modulo cones with lines).

Example 2 . 13 (

 213 Continuation of Example 2.11). M L Z (s, c)(ξ) is given by:

Figure 3 .

 3 Figure 3. The function s → {s} 3 s(iii) QP Ψ (V ) is the algebra of functions on V generated by Q Ψ (V )and P(V ).

Theorem 2 .

 2 22. Let m ∈ Z. (i) The function (s, ξ) → M(s, c) [m] (ξ) belongs to the space

Figure 4 .

 4 Figure 4. One-sided continuity of the functions M L (s, c)(ξ) and S L (s+c)(ξ) and their homogeneous components, as functions of the apex s. Discontinuities arise when one of the copies of L in L+Λ intersects the boundary of the cone s + c; in this case we still have one-sided continuity when we move in a direction v ∈ Lc.

  Figure 1 (top), we computed a formula for M

Theorem 3 . 1 . 1 N j=1 v j P

 311j Let c ⊂ V be a full-dimensional cone with edge generators v 1 , . . . , v N . Let L ⊆ V be a rational linear subspace. For s ∈V , let M L (s, c)(ξ) = e -ξ,s S L (s + c, Λ)(ξ).For every m ∈ Z, consider the homogeneous component M L (s, c) [m] (ξ) as a periodic function of s ∈ V with values in the finite-dimensional space [m+N ] (V * ) of rational functions in ξ of homogeneous degree m whose denominator divides N j=1 ξ, v j . Then the Fourier series of M L (s, c) [m] (ξ) is

1 0e

 1 -2iπns φ(s, ξ) ds =

Remark 3 . 2 .

 32 Moreover, in dimension one, we have the following pointwise result. When m > 1, both sides of (3.4) define continuous functions of s, the series of the right hand side is absolutely convergent, and the equality above is pointwise. If m = 1, the series of the right hand side is convergent in the L 2 -sense and coincides with a function on R \ Z, linear on each open interval. The left hand side (a function Corollary 3.3. For every m ∈ Z, the equality

Lemma 4 . 1 .

 41 The patching function ρ(L), L ∈ L is given by ρ(L) = -µ( 0, L).Proof. The function L → ρ(L) is the patching function of L if and only if for every L 0 ∈ L we haveL∈L L 0 ⊂L ρ(L) = 1.We consider the following linear combination of intermediate generating functions. Definition 4.2. Barvinok's patched generating function of a semirational polyhedron p ⊆ V (with respect to the family L) is S L (p)(ξ) = L∈L ρ(L)S L (p)(ξ).

Definition 4 . 5 .

 45 We introduce the notation M[≥q] (V * ) for the space of functions φ in M ℓ (V * ) such that φ [m] (ξ) = 0 if m < q.For brevity, let us introduce a notation similar to Definition 4.2. Definition 4.6.M L (s, c)(ξ) = e -ξ,s S L (s + c)(ξ) = L∈L ρ(L)M L (s, c)(ξ).

Theorem 4 . 7 .

 47 Let c be a rational cone. Fix k, 0 ≤ k ≤ d. Let L be a family of subspaces of V , closed under sum, such that lin(f) ∈ L for every face f of codimension ≤ k of c. Let ρ be the patching function on L, let S L (s + c)(ξ) be Barvinok's patched generating function of Definition 4.2 and let M L (s, c)(ξ) be as in Definition 4.6. Then, for any s ∈ V ,M(s, c)(ξ) -M L (s, c)(ξ) ∈ M [≥-d+k+1] (V * ) (4.2) and S(s + c)(ξ) -S L (s + c)(ξ) ∈ M [≥-d+k+1] (V * ). (4.3)

Proposition 4 . 8 .

 48 Let c be a full-dimensional cone in V . Fix k, 0 ≤ k ≤ d. Let L be a family of subspaces of V such that lin(f) ∈ L for every face f of codimension ≤ k of c. Let γ ∈ V * . Assume that γ / ∈ L∈L L ⊥ . Then I(c)(ξ + 2iπγ) ∈ M [≥-d+k+1] (V * ).

1 (ξ 1 1 ξ 3

 113 +2iπγ 1 )(ξ 2 +2iπγ 2 )starts at homogeneous ξ-degree -1, and so it belongs to M [≥-1] (V * ). Now we give the new proof of Theorem 4.7.Proof of Theorem 4.7. Fix m ≤ -d + k. Let us denoteF [m] (s) = M(s, c) [m] (ξ) -L∈L ρ(L)M L (s, c) [m] (ξ).We compute the term of homogeneous ξ-degree m of M L (s, c) by looking at its Fourier series (Theorem 3.1). For L = {0} (first term in F [m] (s)), we obtainM(s, c) [m] (ξ) = γ∈Λ * e 2iπγ,s I(c)(ξ + 2iπγ) [m] ,(4.6)whereas for each of the terms corresponding to L ∈ L, we obtainM L (s, c) [m] (ξ) = γ∈Λ * ∩L ⊥ e 2iπγ,s I(c)(ξ + 2iπγ) [m] .(4.7)As[ L∈L L ⊥ ] = L∈L ρ(L)[L ⊥ ], we see that (in the L 2 -sense) F [m] (s) = γ∈Λ * γ / ∈ L∈L L ⊥ e 2iπγ,s I(c)(ξ + 2iπγ) [m] .

V. BALDONI, N. BERLINE, J. A. DE LOERA, M. K ÖPPE, AND M. VERGNE

V. BALDONI, N. BERLINE, J. A. DE LOERA, M. K ÖPPE, AND M. VERGNE

See remarks in the proof of Lemma 2.8.

Acknowledgments

This article is part of a research project which was made possible by several meetings of the authors, at the Centro di Ricerca Matematica Ennio De Giorgi of the Scuola Normale Superiore, Pisa in 2009, in a SQuaRE program at the American Institute of Mathematics, Palo Alto, in July 2009, September 2010, and February 2012, in the Research in Pairs program at Mathematisches Forschungsinstitut Oberwolfach in March/April 2010, and at the Institute for Mathematical Sciences (IMS) of the National University of Singapore in November/December 2013. The support of all four institutions is gratefully acknowledged. V. Baldoni was partially supported by a PRIN2009 grant. J. De Loera was partially supported by grant DMS-0914107 of the National Science Foundation. M. Köppe was partially supported by grant DMS-0914873 of the National Science Foundation.

of s defined for every s) is recovered from the right hand side by taking left limits at every integral point.

Thanks to the one-sided continuity properties of M L (s, c) [m] (ξ) (Proposition 2.28), we will deduce similar pointwise results from Theorem 3.1 in any dimension.

By writing S L (s+c)(ξ) = e ξ,x M L (s, c)(ξ), we obtain a precise statement for the Poisson summation formula discussed above. However, as we have already seen and will see again, the technically useful function is the Λ-periodic function M L (s, c)(ξ) and its Fourier series.


Konstantin Avrachenkov
email: konstantin.avratchenkov@inria.fr

Mahmoud El Chamie
email: mahmoud.elchamie@inria.fr

Giovanni Neglia
email: giovanni.neglia@inria.fr

Graph Clustering Based on Mixing Time of Random Walks *

Clustering of a graph is the task of grouping its nodes in such a way that the nodes within the same cluster are well connected, but they are less connected to nodes in different clusters. In this paper we propose a clustering metric based on the random walks' properties to evaluate the quality of a graph clustering. We also propose a randomized algorithm that identifies a locally optimal clustering of the graph according to the metric defined. The algorithm is intrinsically distributed and asynchronous. If the graph represents an actual network where nodes have computing capabilities, each node can determine its own cluster relying only on local communications. We show that the size of clusters can be adapted to the available processing capabilities to reduce the algorithm's complexity.

I. INTRODUCTION

Ac o m m u n i t yo fn o d e s( o rac l u s t e ro fn o d e s )i nan e t w o r k is a group of vertices that are well connected to each other, but are less connected with the remaining part of the network. Detecting clusters in networks has many applications. Communities in social networks are formed by people having common interest. Clusters in the web graph can group pages with similar topics. E-commerce, classification, computer vision, bioinformatics, and machine learning are only few areas of application of network clustering.

Comparing different possible graph clustering outputs and selecting the best outcome are carried out by introducing a quality metric that serves as an objective function. There is still no consensus in the literature on which quality metric for graph clustering is the best one. One of the most used metrics is the modularity [START_REF] Newman | Finding and evaluating community structure in networks[END_REF] which gives a score to the cluster by comparing the number of edges falling inside the clusters with the number of edges of a random graph having similar characteristic as the original one. Although the modularity is widely used in applications, it is shown that it cannot distinguish small clusters having links of order O( √ m) where m is the total number of links [START_REF] Fortunato | Resolution limit in community detection[END_REF]. The silhouette index [START_REF] Tan | B o s t o n , M A , U S A : A d d i s o n -W e s l e y L o n g m a n P u b[END_REF] uses distances between the nodes presented in the cluster and those outside it, its drawback being its high computational cost asit requires to compute the shortest path between all node pairs. Another approach [START_REF] Kannan | On clusterings-good,b a da n d spectral[END_REF] evaluates a clustering score by using the concept of inter-cluster conductance, but it ignores internal cluster density. Some graph partitioning algorithms based on PageRank vectors of a graph have been proposed in [START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF] to find a cut with a certain conductance in the graph. All these metrics turn out to be biased toward large communities [START_REF] Almeida | Is there a best quality metric for graph clusters?[END_REF]. Many practical algorithms have been proposed as hierarchical clustering [START_REF] Krivánek | Np-hard problems in hierarchical-tree clustering[END_REF], Markov clustering [START_REF] Van Dongen | Graph clustering via a discrete uncoupling process[END_REF], bisecting K-means, and spectral clustering [START_REF] Kannan | On clusterings-good,b a da n d spectral[END_REF]. Their drawback is that they are global clustering methods which require as input the entire graph to calculate the clustering. Moreover their output is biased toward equal size clusters (so small communities tend to disappear using these algorithms). A complete survey of fitness measures and clustering is given in [START_REF] Schaeffer | Survey: Graph clustering[END_REF].

In this paper, we introduce a new fitness measure for evaluating a clustering algorithm based on random walks' properties. Roughly speaking, our fitness index is higher the fastera random walk constrained to the cluster reaches its stationary distribution and the slower it escapes from the cluster in the unconstrained case. Both effects can be quantified considering the eigenvalues of appropriate matrices. Beside introducing this new metric, we propose a randomized algorithm for clustering the network accordingly. The algorithm is local because it relies only on a partial view of the entire network.In particular, if the graph represents the topology of a network where nodes have computing capabilities, the algorithm can run in parallel at each node without the need of a central unit. Being local, clusters can be formed in parallel and the computation complexity is distributed among clusters. The algorithm can also find small clusters that are more difficult to be detected by the global clustering methods. We present in the next section the notation used across the paper.

II. NOTATION

Let G =( V, E) be an undirected unweighted connected graph withoug self-loops, where V = {1,...n} is the set of vertices and E is the set of m = |E| edges. Let d G (i)= |{j ∈ V, (i, j) ∈ E}| be the degree of a node i in G, D G be a diagonal matrix having on its diagonal the degree of the nodes in G and let A G be the adjacency matrix of the graph G where a ij =1if (i, j) ∈ E,a n da ij =0otherwise. For any set S ⊆ V ,letD G (S) (resp. A G (S))bethesub-matrixof D G (resp. A G )o b t a i n e dc o n s i d e r i n go n l yr o w sa n dc o l u m n s corresponding to the vertices in S.L e tG(S)=( S, E(S)) be the subgraph induced by S ⊆ V where E(S)={(i, j) ∈ E|i, j ∈ S}.ObservethatingeneralD G (S) = D G(S) because D G (S) contains the degree of nodes in the original graph G which are different from their degrees in the induced subgraph G(S).C o n v e r s e l y ,A G (S)=A G(S) as the adjacency matrix is not changed. If P is a substochastic matrix (a square matrix with nonnegative entries so that every row adds up to at most 1), let σ(P )=|λ 1 (P )| be the largest eigenvalue in module of P .WhenP is stochastic, let s(P )=1-|λ 2 (P )|∈[0, 1] be its spectral gap 1 where |λ 2 (P )| is the second largest eigenvalue in module of P .F i n a l l y ,I is the identity matrix. Ac l u s t e r i n gC G of a graph G is a partition of the vertices such that

C G = {C 1 ,...C k } where C 1 ∪ ... ∪ C k = V and C u ∩ C v = φ for all clusters C u and C v in C G .L e tC(i)= {C u ∈C G ; i ∈ C u
} be the cluster that contains node i.L e t f : V → R be a scoring function for the nodes, define a cluster score f (C u )= i∈Cu f (i),a n dac l u s t e r i n ga l g o r i t h ms c o r e

f (C G )= k u=1 f (C u )= n i=1 f (i).

III. THE RANDOM WALK FITNESS MEASURE

In this section, we introduce a new scoring function f (.) that can serve as a quality measure for a clustering algorithm. Ag o o dc l u s t e r i n ga l g o r i t h mi d e n t i fi e sc l u s t e r st h a ta r ew e l l connected internally, but weakly connected with the rest of the network. Inspired by this intuitive definition, the function f should have the following properties: 1) A cluster whose induced subgraph is disconnected should receive the minimum score. 2) A clique graph clustered as a single cluster should have the highest score among all clusterings for graphs with the same number of nodes. 3) For a given clustering, adding links within clusters should increase the score while removing them should only decrease the score. 4) For a given clustering, adding links between different clusters should decrease the score while removing them should increase the score. 5) Within a cluster, the higher the degree of a node, the more it contributes to the score. 6) Boundary nodes in a cluster that have links to other clusters have less score than internal nodes. Given a graph clustering C G = {C 1 , ..., C k },w ed e fi n et h e score of a vertex i ∈ V is given by

f (i)=α i × s C(i) × σ C(i) ,
where s C(i) quantifies how fast a random walk on G(C(i)) (and then constrained to the cluster C(i))r e a c h e si t ss t e a d y state distribution, σ C(i) corresponds to the probability that ar a n d o mw a l ko nt h ew h o l eg r a p hG that starts inside the cluster C(i) keeps staying inside the cluster at a following step (see below for a more formal definition), and finally α i differentiates among different nodes in the same cluster according to the last two properties. Given this definition of the scoring function, the score of cluster C u is:

f (C u )= i∈Cu α i s Cu σ Cu .
1 If P is a scalar, we consider s(P )=1by convention.

Below we define formally the different quantities α i , s Cu and σ Cu and show that f (.) satisfies the required properties of a good clustering function.

First, we define s Cu as

s Cu s (D G(Cu) + I) -1 (A G(Cu) + I) ,
that is the spectral gap of the transition probability matrixo f as i m p l er a n d o mw a l ko nt h es u b g r a p hi n d u c e db yt h ec l u s t e r nodes C u adding self-loops [START_REF] Landau | Bounds for eigenvalues of certain stochastic matrices[END_REF]. This value ranges between 0 for a disconnected graph and 1 for a fully connected network (a clique). Given a random walk starting at time 0 from a node in the cluster, the difference between the probability distribution of the position of the random walker at time t and its stationary distribution can be bounded by A(1 -s Cu ) t , with A being an appropriate constant. Then the larger s Cu ,the faster the distribution converges to its stationary distribution, i.e. the faster the random walk mixes.T h es p e c t r a lg a po ft h e transition probability matrix is then also a measure of how well connected the network within a cluster is. The presence of s Cu as a multiplicative factor in the scoring function guarantees that the first two properties are satisfied. Moreover, due to the interlacing property of eigenvalues [START_REF] Chen | A n interlacing result on normalized laplacians[END_REF], adding more links between the nodes of the same cluster usually increases the spectral gap while removing links decreases it, which supports the third property of a good clustering function. Second, we define

σ Cu σ D G (C u ) -1 A G (C u ) .
Given that D G (C u ) considers the degrees of the nodes2 in the original graph

G, Q = D G (C u ) -1 A G (C u ) is a substochastic matrix.
If we consider the transition probability matrix of ar a n d o mw a l ko nt h ew h o l eg r a p hG, Q is the submatrix obtained by extracting only the rows and the columns corresponding to the nodes in C u .G i v e nar a n d o mw a l ko n G starting at a node i in C u ,a n da s s u m i n gt h a tQ is a primitive matrix, it is possible to show [START_REF] Darroch | On quasi-stationary distributions in absorbing discrete-time finite markov chains[END_REF] that the conditional probability distribution given that the random walk does not exit from C u converges to π ∈ [0, 1] |Cu| (we consider only the probabilities for the nodes in C u ,f o ra l lt h eo t h e rn o d e s the probability is clearly 0 under the conditioning event), that satisfies the following equation

π T Q = π T σ(Q).
T h e nσ(Q) can be interpreted as the probability that at each step the random walker does not exit from C u ,giventhatithasalready spent a long time in C u 3 .T h et e r mσ Cu quantifies then the effect of outer links connecting the cluster C u to other clusters. Obviously, it ranges between 0 and 1.I ti se q u a lt o1 when there is no link between nodes in C u and nodes in V \C u and then in particular when C u = V since the graph is connected. It is equal to 0 if the subgraph G(C u ) has no links. Adding links between clusters can only decrease σ while removing them can only increase it. The factor σ Cu guarantees that the fourth property is satisfied.

Finally, α i represents the contribution of a node to the final score depending on its connectivity to other clusters. To satisfy the last two properties required for the function f ,t h ev a l u e α i is chosen as follows:

α i d in i 1+d out i ,
where

d in i = d G(C(i)) (i) is the number of nodes in C(i) connected to i and d out i = d G (i) -d in i is the number of nodes in V \C(i) connected to i.

IV. CLUSTERING ALGORITHM

The function f presented in the previous section gives as c o r i n gm e c h a n i s mt oe v a l u a t eac l u s t e r i n ga l g o r i t h m .I n particular, the optimal clustering algorithm can be writtena s follows:

Argmax CG={C1,...,C k } f (C G ). (1)
Let C * G be the solution of (1) and f * = f (C * G ) be its value. The optimal clustering and its value are computationally difficult to find, so we will give first some bounds on the optimal value f * and we will propose a local search clustering algorithm that can be implemented with an acceptable complexity and in a distributed way.

A. Bounds on f * Proposition 1. Fo r t h e c l u s t e r i n g o p t i m i z a t i o n p ro b l e m (1),

the following bounds hold for the optimal value f * :

2 × m × s V ≤ f * ≤ 2 × m, ( 2
)
where s V is the spectral gap of the simple random walk on all the graph G (s V =1-λ 2 (D + I) -1 (A + I) ).

Proof: For any clustering

C G = {C 1 , ..., C k } of the graph G we have, f (C G )= i f (i)= i d in i 1+d out i s C(i) σ C(i) ≤ i d in i 1+d out i ≤ i d in i ≤ i d G (i) =2× m,
where m is the number of links in the graph G and the first inequality follows from both s Cu and σ Cu being at most equal to one. From this upper bound, it follows that f (C * G ) ≤ 2 × m. The optimal clustering has a value greater than any possible clustering. Taking the graph as one cluster C G = {V } is a valid clustering of G.T h u s ,al o w e rb o u n do nt h eo p t i m a lv a l u ei s given as follows:

f * ≥ f (C G = {V })= i d in i × s V × 1=2× m × s V ,
where s V is the spectral gap of the simple random walk on all the graph G (s V =1-λ 2 (D + I) -1 (A + I) ).

We observe that both of the bounds are tight for the fully connected graph (let us denote it K n ). Indeed nodes in K n are grouped in a single cluster (C G = V )a n df (V )=2 m since d out i =0for any vertex i and s V = σ V =1. Due to the following proposition, the subgraph induced by ac l u s t e ro ft h eo p t i m a lc l u s t e r i n gi sc o n n e c t e da sl o n ga si t has at least an internal link. Proposition 2. Let C * G = {C 1 , ..., C k } be an optimal clustering for a graph G,t h e nf o ra n yC u ∈C * G ,i ft h es u b g r a p h G(C u ) has at least one link, it is connected.

Proof: We sketch a proof of the proposition by contradiction. Suppose there exists a graph whose optimal clustering C * G outputs a cluster C u such that G(C u ) has at least one link, but it is disconnected. It follows that f (C u )=0since s Cu =0for disconnected graphs. However, there is a subset of vertices H ⊂ C u such that |H|≥2 and G(H) is connected (because there is at least one link in G(C u ))a n di th o l d s f (H) > 0.N o wi fw er e p l a c eC u with two clusters H and C u -H,t h en e wc l u s t e r i n gh a sas t r i c t l yh i g h e rv a l u et h a n C * G (contradiction).

B. Local Search Clustering Algorithm

The optimal clustering can be computationally costly because calculating the spectral gap of a random walks has complexity O(n 3 ).Inthissection,wepresentalocalclustering algorithm that allows the clustering to be done in a distributed way. The algorithm applies the generic local search approach. Let X be the set of all possible clusterings of graph G.W e define two cluster x and y belonging to X to be neighbors if and only if they differ only for a single vertex that belongs to two different clusters in x and in y.Al o c a ls e a r c ha l g o r i t h m for clustering operates as follows:

1) Let x be some initial clustering; 2) While there is a neighboring G-clustering y with higher score value (f (y) >f(x)), set x := y. 3) Return the final (locally optimal) solution x. The algorithm is an iterative one. In our local clustering algorithm we follow the above steps but we add some randomness in choosing the neighbor in step two. In fact, at every iteration, a cluster, say it C u ,i sc h o s e nu n i f o r m l ya t random. This random cluster selects one of the outgoing links uniformly at random and proposes to the endpoint node j in the adjacent cluster, to disconnect from that cluster and to join C u .I fj o i n i n gC u can increase the value of the clustering then j will accept the proposal, otherwise it will reject it and no change in the clustering will take place. In particular, a detailed description of the local clustering algorithm is given in Algorithm 1. The algorithm runs at most for T stop iterations, but it can easily changed so that it stops after a given number of consecutive iterations without any change of the clustering.

Algorithm 1 presents some interesting features. In fact, at every iteration, only two clusters are involved in the algorithm, while the others are idle. It is then simple to distribute the algorithm among the different clusters that can work asynchronously and in parallel as follows: at any time an

Algorithm 1 Local Clustering Algorithm 1: G =(V, E) where V =1...n and E =1...m. 2: Initial clustering C 0 G = {C 1 , ..., C n } where C i = {i}. 3: E + Cu = {(i, j) ∈ E|i ∈ C u ,j / ∈ C u } is the set of C u 's outgoing links. 4: for k =1:T stop do 5: C k G = C k-1 G ; 6:
let C u be a cluster chosen uniformly at random from C k G ;

7:

let (i, j) be a link chosen uniformly at random from E + Cu ;

8:

let C v be the cluster containing j (i.e. C v = C(j)); C u proposes to j to join (if it didn't yet propose to j after the last change within C u occurred) ; 10:

if f (C u )+f (C v ) <f(C u ∪{j})+f (C v \{j}) then 11:
j accepts the proposal;

12:

C u ← C u ∪{j};

13: If all clusters don't have any more proposals break; 22: end for 23: return C k-1 G inactive cluster can wake up and can propose to a node from another inactive cluster to join it, both clusters will become active until acceptance or rejection of the proposal. Several matching clusters can be active at the same time and the computations is distributed in a parallel way. Finally, being that the algorithm randomized, it is possible to run it multiple times and then select the best solution across all the different runs.

C v ← C v \{j};
Moreover, at every iteration, a cluster can increase by maximum one node. The complexity of the algorithm originates from calculating the function f which in its turn depends on the number of nodes in the cluster. So depending on the available computational power, we can restrict the maximum number of nodes in a cluster. For example, if the calculation of the spectral gap is affordable for graphs with only few hundred nodes, then clusters reaching this limit will stop initiating the algorithm and stop proposing to other nodes to join.

In addition, the local clustering algorithm performs well on clique-like graphs. The following simple lemma will prepare the result: Lemma 1. Let g : A → R be a scalar strongly convex function, then for any x and y such that x, x +1,y,y-1 ∈ A and x ≥ y,w eh a v e : g(x +1)+g(y -1) >g(x)+g(y).

Proof: Let h(x)=g(x +1)-g(x),s i n c eg is strongly convex, then g (x) is strictly increasing, so x +1>x, ⇒ g (x +1)>g (x), ⇒ h (x) > 0, so h(x) is strictly increasing, and adding that x ≥ y we can write:

x>y-1, ⇒ h(x) >h(y -1), ⇒ g(x +1)-g(x) >g(y) -g(y -1),
and the lemma follows.

Proposition 3. The local clustering Algorithm 1 calculates

the optimal clustering for a clique graph K n in a finite number of iterations almost surely if T stop is large enough, i.e., Algorithm 1 on K n outputs a single cluster C G = {V }.

Proof: First note that the optimal clustering on a clique

K n is C * G = {V } since f (C G = {V })=2m
that is an upper bound on f * .I tr e m a i n st op r o v et h a tt h el o c a la l g o r i t h m terminates with one cluster of all nodes. Let C u be any cluster in this graph, and let n u = |C u | be its number of vertices, so s Cu =1since the subgraph induced by C u is also a clique, and

σ Cu = nu-1 n-1 since the matrix D G (C u ) -1 A G (C u
) has dimensions n u ×n u and any of its elements has the value 1 n-1 except the diagonal elements that are equal to 0,t h e r e f o r e

f (C u )= i∈Cu d in i 1+d out i s Cu σ Cu = i∈Cu n u -1 1+n -n u × 1 × n u -1 n -1 = n u (n u -1) 2 (n -1)(n -n u +1) ,
and it depends only on the size of the cluster. Let

g(n u )= f (C u ),sinceg(n u ) is strongly convex in n u when n u ∈ [1,n],
then according to the algorithm and due to Lemma 1, any node j (that belongs to the cluster C v )r e c e i v i n gap r o p o s a lf r o ma cluster C u will accept this proposal if |C u |≥| C v | and will reject otherwise due to the following equation,

f (C u ∪{j})+f (C v \{j})=g(|C u | +1)+g(|C v |-1) (3) >g(|C u |)+g(|C v |) (4) = f (C u )+f (C v ). (5)
The transition from (3) to ( 4) is due to Lemma 1. Therefore, any proposal from the cluster with largest number of vertices to other nodes is accepted (let C k max be the cluster with maximum number of vertices at iteration k), |C k max | cannot decrease while it can increase by one with a probability larger Fig. 1. The network of social relationship between the members of the Karate Club. After a split, the members represented by a square belongs to one sub-club and the members represented by a circle to the other sub-club (the image is taken from [START_REF] Newman | Finding and evaluating community structure in networks[END_REF]). than 1/n.Thealgorithmterminateswhen|C k max | = n,sowith probability 1 there is an iteration K such that all the nodes form a single cluster and the algorithm terminates. It is easy to check that E(K) ≤ n 2 .

V. N UMERICAL EXAMPLES

In this part, we study the performance of our local clustering algorithm. We consider real world networks whose ground truth is known. We apply our algorithm (we perform multiple independent runs of the Algorithm 1 and select the best local maximum) on these networks and compare the algorithm's results with actual clustering. The results are shown using the graph visualization platform Gephi [START_REF] Bastian | Gephi: An open source software for exploring and manipulating networks[END_REF]. We also compare our results with the built-in modularity clustering algorithm [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF] in Gephi. Our first example is the Zachary's Karate Club [START_REF] Zachary | An information flow model for conflict and fission in small groups[END_REF], it is a social network of friendships between 34 members of ak a r a t ec l u ba taU Su n i v e r s i t yi nt h e7 0 s .F i g .1s h o w st h e partition of the karate club.

We apply our local clustering algorithm to the karate club network and the results are given in Fig. 2. Starting from 34 different clusters as initial input (every node is considered ac l u s t e r )a n db a s e do nt h ec o n n e c t i o na n dt h es p e c t r a lg a p of the clusters, our algorithm identifies 3 clusters (one more than the ground truth). Moreover the two nodes 31 and 9 are not assigned to the correct cluster. Notice that this is just a local maximum for the optimization problem. For comparison, Fig. 3 shows the results of clustering using the modularity clustering algorithm, we see that it identifies even more clusters than our method (4) and node 10 is not correctly assigned in comparison to the ground truth.

The other example we consider is the network of American College football teams in Division I during Fall 2000 regular season [START_REF] Girvan | Community structure in social and biological networks[END_REF]. Division I was made up by 115 teams divided in 12 conferences. A link in the graph corresponds to a game played between the two teams. Teams in the same conference are more likely to play games than teams from different conferences. Fig. 4 shows the teams grouped according to the conference they belong to. While most of conferences have good clustering properties (good connections inside the clusters and week connections among them), there are some conferences for which this is not true. For conference 1 for example there is only one game (one link) among its members, Clustering the American College football network by applying Algorithm 1. Nodes with the same color are classified as one cluster (the algorithm terminates with 14 clusters, 2 more than the groundt r u t h ) .

between the ground truth and the spectral gap clustering is as follows: cluster 7 was divided into two clusters, cluster 12 was also divided into two clusters. Even though conference 1 is very difficult to identify, our algorithm clustered together the only two connected nodes and clustered the disconnected nodes into different clusters. In total there are only 6 nodes that are not well clustered 4 (out of the 115 nodes).

We also present the results of clustering using the modularity algorithm of [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF]. This allows us to compare the performance with other clustering algorithm and to check if the errors were due to failure of the algorithm or due to the ground truth graph structure. In the Fig. 6, the modularity algorithm classified the network into only 10 clusters (2 less clusters than the ground truth). Cluster 7 nodes were divided between two already existing clusters. Cluster 1 disappeared. Note that the same 6 nodes that were miss-classified by our algorithm were also here miss-classified which suggests that the errors are due to the structure but not to the algorithm.

VI. CONCLUSION

In this paper we proposed a new clustering metric based on the spectral gap of a random walk on clusters. We also proposed a randomized local clustering algorithm that outputs alocallyoptimalclusteringofthegraph.Thealgorithmcanbe distributed in a network and clusters are iteratively updated on the basis of local communication and processing. One of the strengths of our algorithm is its ability to detect small clusters. The complexity can also be adapted to available processing capabilities.

Fig. 2 .

 2 Fig. 2. Clustering the karate club by applying Algorithm 1.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Clustering the karate club by applying modularity algorithm.

Fig. 5 .

 5 Fig. 5.

Fig. 6 .

 6 Fig. 6. Clustering the American College football network by applying the modularity algorithm. Nodes with the same color are classified as one cluster (the algorithm terminates with 10 clusters).

The inverse D G (Cu) -1 always exists because D G (Cu) is a diagonal matrix having strictly positive diagonal values (d G (i) ≥ 1 because G is connected).

Otherwise if we consider that the random walk initial position in Cu follows the probability distribution π, σ(Q) is simply the probability that the random walker does not exit from Cu at each step.

The bad clustered nodes by Algorithm 1 in comparison to the ground truth are: 3 nodes in cluster 1, 2 nodes in cluster 9, and 1 node in cluster

which gives a total of

error nodes (without taken into consideration the split of the clusters

and 12).

This work has been partially supported by the European Commission within the framework of the CONGAS project FP7-ICT-2011-8-317672.

The authors are given in alphabetical order.