# The multivariate arithmetic Tutte polynomial

Petter Brändén¹† and Luca Moci²‡

¹Department of Mathematics, Royal Institute of Technology, Stockholm, Sweden

²Department of Mathematics, Università di Roma “La Sapienza”, Italy

**Abstract.** We introduce an arithmetic version of the multivariate Tutte polynomial recently studied by Sokal, and a quasi-polynomial that interpolates between the two. We provide a generalized Fortuin-Kasteleyn representation for representable arithmetic matroids, with applications to arithmetic colorings and flows. We give a new proof of the positivity of the coefficients of the arithmetic Tutte polynomial in the more general framework of pseudo-arithmetic matroids. In the case of a representable arithmetic matroid, we provide a geometric interpretation of the coefficients of the arithmetic Tutte polynomial.

**Résumé.** Nous introduisons une version arithmétique du polynôme de Tutte multivariée récemment étudié par Sokal, et un quasi-polynôme qui interpole entre les deux. Nous proposons une représentation de Fortuin-Kasteleyn gener-alisée pour les matroïdes arithmétiques représentables, avec des applications aux colorations et flux arithmétiques. Nous donnons une nouvelle preuve de la positivité des coefficients du polynôme de Tutte arithmétique dans le cadre plus général des matroïdes pseudo-arithmétiques. Dans le cas d’un matroïde arithmétique représentable, nous pro-posons une interpretation geometrique des coefficients du polynôme de Tutte arithmetique.

**Keywords:** Potts model, Tutte polynomial, chromatic polynomial, matroids, arithmetic matroids, abelian groups.

## 1 Introduction

In this paper we introduce a multivariate arithmetic Tutte polynomial, which generalizes many polynomi-als that have appeared in the literature.

Recall that the *Tutte polynomial* is a bivariate polynomial with several well-known specializations: for instance the chromatic polynomial of a graph, or the characteristic polynomial of a hyperplane arrange-ment can be obtained by specializing the Tutte polynomial. Also, its coefficients are nonnegative, as proved by Crapo by providing an explicit combinatorial interpretation ([12], [4]).

Recently, in [6, 9, 10], an arithmetic version of this polynomial has been studied. Namely, to a finite list $\mathcal{L}$ of elements in a finitely generated abelian group $G$, one associates an *arithmetic Tutte polynomial*. This is a bivariate polynomial, such that several geometric, algebraic or combinatorial invariants appear as its specialization, for instance:

* the characteristic polynomial of the toric arrangement $T(\mathcal{L})$. This is a family of subvarieties in the linear algebraic group $\text{Hom}(G, \mathbb{C}^*)$ (see [9, Section 5]);

<footnote>†Royal Swedish Academy of Sciences Research Fellow supported by a grant from the Knut and Alice Wallenberg Foundation.</footnote>

<footnote>‡supported by PRIN 2009 "Spazi di moduli e teoria di Lie"</footnote>
* the Hilbert series of the Dahmen-Micchelli space $DM(\mathcal{L})$. This vector space was introduced in order to study vector partition functions (see [9, Section 6]);

* the Ehrhart polynomial of the zonotope $\mathcal{Z}(\mathcal{L})$ (see [9, Section 4] and [7]).

Furthermore, the arithmetic Tutte polynomial has applications to graph theory [7], and it has non-negative coefficients, as proved in [6] by providing a combinatorial interpretation that extends Crapo's theorem.

The Tutte polynomial is naturally defined in the general framework of *matroids*, while the arithmetic Tutte polynomial is associated to an *arithmetic matroid* $\mathcal{A}$, which is a matroid and a *multiplicity function* $m$. When $\mathcal{A}$ is represented by a list of elements of $G$, the function $m$ encodes arithmetic information, likewise the rank function encodes linear-algebraic information.

Recently, Sokal [11] studied a remarkable multivariate generalization of the Tutte polynomial. This is a multivariate *Tutte polynomial*, having one variable $v_e$ for each element $e$ of the matroid (or edge $e$ of the graph), and one extra variable $q$. If all the variables $v_e$ are set to be equal, we obtain a bivariate polynomial that is essentially equivalent to the standard Tutte polynomial. In the case of graphs, Sokal's polynomial is known to physicists as the *partition function of the q-state Potts model*, which along with the related *Fortuin-Kasteleyn random-cluster model* plays an important role in the theory of phase transitions and critical phenomena. In this paper we introduce a multivariate arithmetic Tutte polynomial

$$Z_{\mathcal{A}}(q, \mathbf{v}) := \sum_{A \subseteq E} m(A) q^{-\mathrm{rk}(A)} \prod_{e \in A} v_e.$$

(Here $E$ is the ground set of the arithmetic matroid $\mathcal{A}$, while rk and m are the rank and the multiplicity functions respectively). As the name suggests, $Z_{\mathcal{A}}(q, \mathbf{v})$ generalizes the polynomials above. It is naturally defined starting from an arithmetic matroid, or more generally from what we call a *pseudo-arithmetic matroid* (see Section 2). Actually, our polynomial encodes all the structure of the (pseudo-)arithmetic matroid, i.e., it is possible to reconstruct $\mathcal{A}$ from $Z_{\mathcal{A}}(q, \mathbf{v})$.

For this polynomial we prove a deletion-contraction recurrence (Lemma 3.2). Then we give a new proof of the nonnegativity of the coefficients of the arithmetic Tutte polynomial in the framework of pseudo-arithmetic matroids (Theorem 3.5). Even more, we show that pseudo-arithmetic matroids are the most general objects closed under deletion and contraction and such that the associated arithmetic Tutte polynomials have nonnegative coefficients. We also provide a generalization of Crapo's formula (Theorem 4.3).

When $\mathcal{A}$ is represented by a list $\mathcal{L}$ of elements in a finitely generated abelian group $G$, we provide a *Fortuin-Kasteleyn formula for $Z_{\mathcal{A}}(q, \mathbf{v})$* (Theorem 6.6), with applications to arithmetic colorings. This can be seen as a generalization of the “finite field method” for computing the characteristic polynomial or the Tutte polynomial of a rational hyperplane arrangement [1, 2, 13], as well as a generalization of a similar result for toric arrangements [8]. We also introduce a generalized “flow polynomial” with applications to arithmetic flows (see Theorem 7.1), which allows us to extend the results proved in [7] for graphs with labeled edges (Corollary 8.1).

Furthermore, we introduce a quasi-polynomial $Z_{\mathcal{L}}^P(q, \mathbf{v})$ that interpolates between the ordinary and the arithmetic multivariate Tutte polynomial (Theorems 6.3, 6.5, 6.6), and hence between ordinary and arithmetic chromatic and flow polynomials. This quasi-polynomial is the partition function of a generalized Potts models similar to the one studied by Caracciolo, Sportiello and Sokal, see [11, Section 3.2].
Finally we give a geometrical interpretation for $M_A(x, y)$, holding for any representable $A$ and generalizing various formulae proved in [9, 6].

This is an extended abstract of the paper in preparation [3]; the reader may refer to it for the proofs and updates.

## 2 Arithmetic matroids and multivariate Tutte polynomials

The notion of an arithmetic matroid tries to capture the linear algebraic and arithmetic information contained in a finite list of vectors in $\mathbb{Z}^n$.

Let $\mathbb{N} := \{0, 1, 2, \dots\}$ and $2^E := \{A : A \subseteq E\}$, where $E$ is a finite set. We recall that a matroid, $\mathcal{M}$, on $E$ may be defined via its rank function, which is a function $\mathrm{rk} : 2^E \to \mathbb{N}$ such that $\mathrm{rk}(\emptyset) = 0$ and satisfying

(R1) if $A, B \subseteq E$ and $A \subseteq B$, then $\mathrm{rk}(A) \le \mathrm{rk}(B)$;

(R2) if $A, B \subseteq E$, then $\mathrm{rk}(A \cup B) + \mathrm{rk}(A \cap B) \le \mathrm{rk}(A) + \mathrm{rk}(B)$.

If $R \subseteq S \subseteq E$ let $[R, S] := \{A : R \subseteq A \subseteq S\}$. We say that $[R, S]$ is a molecule if $S$ is the disjoint union $S = R \cup F \cup T$ and for each $A \in [R, S]$

$$ \mathrm{rk}(A) = \mathrm{rk}(R) + |A \cap F|. $$

A pseudo-arithmetic matroid $\mathcal{A} = (\mathcal{M}, m)$ is a matroid $\mathcal{M}$ with a function $m : 2^E \to \mathbb{R}$, called pseudo-multiplicity, satisfying the following axiom:

(P) If $[R, S]$ is a molecule, then

$$ \rho(R, S) := (-1)^{|T|} \sum_{A \in [R, S]} (-1)^{|S|-|A|} m(A) \ge 0. $$

An arithmetic matroid $\mathcal{A}$ is a set $E$ with two functions $\mathrm{rk} : 2^E \to \mathbb{N}$, $m : 2^E \to \mathbb{N} \setminus \{0\}$, called rank and multiplicity respectively, satisfying the axioms (R1), (R2), (P), and:

(A1) if $A \subseteq E$, $v \in E$, and $\mathrm{rk}(A \cup \{e\}) = \mathrm{rk}(A)$, then $m(A \cup \{v\})$ divides $m(A)$; otherwise $m(A)$ divides $m(A \cup \{v\})$;

(A2) if $[R, S]$ is a molecule, then $m(R) \cdot m(S) = m(R \cup F) \cdot m(R \cup T)$.

The dual of an arithmetic (or pseudo-arithmetic) matroid is defined as the matroid with the same ground set $E$, rank function defined by $\mathrm{rk}^*(A) := |A| - \mathrm{rk}(E) + \mathrm{rk}(E \setminus A)$ and multiplicity function defined by $m^*(A) := m(E \setminus A)$. Notice that each of axioms (A1), (A2) and (P) is self-dual, so the dual of an arithmetic matroid is indeed an arithmetic matroid.

Our definition of arithmetic matroid is equivalent to the one given in [6]. The main example of an arithmetic matroid is the one associated to a finite list of elements of a finitely generated abelian group $G$, see Section 5.
Recall [4, 12] that to each matroid $\mathcal{M}$ is associated the *Tutte polynomial*

$$T_{\mathcal{M}}(x, y) = \sum_{A \subseteq E} (x-1)^{\mathrm{rk}(E)-\mathrm{rk}(A)} (y-1)^{|A|-\mathrm{rk}(A)}$$

that Sokal [11] generalized by defining a *multivariate Tutte polynomial* in the variables $q^{-1}$, $v = \{v_e\}_{e \in E}$:

$$Z_{\mathcal{M}}(q, v) := \sum_{A \subseteq E} q^{-\mathrm{rk}(A)} \prod_{e \in A} v_e.$$

Similarly, to each arithmetic matroid $\mathcal{A}$, is associated the *arithmetic Tutte polynomial*

$$M_{\mathcal{A}}(x, y) = \sum_{A \subseteq E} m(A)(x-1)^{\mathrm{rk}(E)-\mathrm{rk}(A)} (y-1)^{|A|-\mathrm{rk}(A)},$$

see [6, 9], that we are going to generalize by defining a *multivariate arithmetic Tutte polynomial*

$$Z_{\mathcal{A}}(q, v) := \sum_{A \subseteq E} m(A) q^{-\mathrm{rk}(A)} \prod_{e \in A} v_e.$$

Of course these polynomials are also defined for a pseudo-arithmetic matroid. Note that

$$Z_{\mathcal{M}}((x-1)(y-1), y-1) = (x-1)^{-\mathrm{rk}(E)} T_{\mathcal{M}}(x, y); \qquad (1)$$

$$Z_{\mathcal{A}}((x-1)(y-1), y-1) = (x-1)^{-\mathrm{rk}(E)} M_{\mathcal{A}}(x, y). \qquad (2)$$

(By $v = y-1$ we mean that each variable $v_e$ is evaluated at $y-1$).

## 3 Deletion-contraction and nonnegativity

Let $\mathcal{A}$ be an arithmetic matroid. Given an element $e \in E$, the deletion of $\mathcal{A}$ by $e$ is the arithmetic matroid $\mathcal{A}_1$ on the set $E_1 := E \setminus \{e\}$, with rank function $\mathrm{rk}_1$ and multiplicity function $m_1$ that are just the restriction of the corresponding functions of $\mathcal{A}$.

We also define the contraction of $\mathcal{A}$ by $e$ as the matroid $\mathcal{A}_2$ on the set $E_2 := E \setminus \{e\} = E_1$, with rank function $\mathrm{rk}_2$ given by $\mathrm{rk}_2(A) := \mathrm{rk}(A \cup \{e\}) - \mathrm{rk}(\{e\})$ and multiplicity function given by $m_2(A) := m(A \cup \{e\})$ for all $A \subseteq E_2$.

Clearly, the same constructions hold for pseudo-arithmetic matroids.

If an arithmetic matroid $\mathcal{A}$ is represented by a list $\mathcal{L}_E$ of elements of a finitely generated abelian group $G$ (see Section 5), it is easy to check that the deletion $\mathcal{A}_1$ is represented by the list $\mathcal{L}_{E_1}$ in $G$, while the contraction $\mathcal{A}_2$ is represented by the list $E_2 := \{g_a + \langle g_e \rangle : a \in E \setminus \{e\}\}$ of cosets in $G/\langle g_e \rangle$.

We say that $e \in E$ is:

* free (or a coloop) if both $\mathrm{rk}_1(E \setminus \{e\}) = \mathrm{rk}(E \setminus \{e\}) = \mathrm{rk}(E) - 1$ and $\mathrm{rk}_2(E \setminus \{e\}) = \mathrm{rk}(E) - 1$;

* torsion (or a loop) if both $\mathrm{rk}_1(E \setminus \{e\}) = \mathrm{rk}(E)$ and $\mathrm{rk}_2(E \setminus \{e\}) = \mathrm{rk}(E)$;

* proper otherwise, i.e. if both $\mathrm{rk}_1(E \setminus \{e\}) = \mathrm{rk}(E)$ and $\mathrm{rk}_2(E \setminus \{e\}) = \mathrm{rk}(E) - 1$.
**Remark 3.1** An interval $[R, S]$ is a molecule if and only if, after contracting the arithmetic matroid defined by $S$ by all the elements in $R$, each of the remaining elements is either a coloop or a loop. In this sense we use the word "molecule" with a slightly more general meaning than in [6].

Let $\mathcal{A}$ be an arithmetic matroid, and let $\mathcal{A}_1$ and $\mathcal{A}_2$ be its deletion and contraction by an element $e \in E$.

**Lemma 3.2**

$$Z_{\mathcal{A}}(q, \mathbf{v}) = \begin{cases} Z_{\mathcal{A}_1}(q, \mathbf{v}) + v_e Z_{\mathcal{A}_2}(q, \mathbf{v}), & \text{if } e \text{ is a loop;} \\ Z_{\mathcal{A}_1}(q, \mathbf{v}) + (v_e/q) Z_{\mathcal{A}_2}(q, \mathbf{v}), & \text{otherwise} \end{cases}$$

We end this section by proving that the coefficients of the arithmetic Tutte polynomial of a pseudo- arithmetic matroid are nonnegative.

Let $\mathbb{B}$ be the set of bases that can be extracted from $E$, and $\mathbb{B}^*$ the bases of the dual matroid. Let us fix a total order on $E$, and let us take $B \in \mathbb{B}$. We say that $e \in E \setminus B$ is externally active on $B$ if $e$ is dependent on the list of elements of $B$ following it (in the total order fixed on $E$). We say that $e \in B$ is internally active on $B$ if in the dual matroid $e$ is externally active on the complement $B^c := E \setminus B \in \mathbb{B}^*$.

We denote by $E(B)$ the set of externally active elements and by $e(B)$ its cardinality, which is called the *external activity* of $B$. In the same way, we denote by $I(B) = E^*(B^c)$ the set of internally active elements, and by $i(B)$ its cardinality, which is called the *internal activity* of $B$.

The proof of the following Proposition may be found in [4].

**Proposition 3.3** Suppose that $M$ is a matroid with ground set $E$ and set of bases $\mathbb{B}$. Then:

i) $2^E$ is the disjoint union

$$2^E = \bigcup_{B \in \mathbb{B}} [B \setminus I(B), B \cup E(B)].$$

ii) for each $B \in \mathbb{B}$, $[B \setminus I(B), B \cup E(B)]$ is a molecule with $F = I(B)$ and $T = E(B)$.

**Lemma 3.4** Let $[R, S]$ be a molecule. Then

$$\sum_{A \in [R, S]} m(A)(x-1)^{\mathrm{rk}(S)-\mathrm{rk}(A)}(y-1)^{|A|-\mathrm{rk}(A)} = \sum_{K \subseteq F, L \subseteq T} \rho(R \cup L, S \setminus K) x^{|K|} y^{|L|} = \\ = \frac{1}{m(R)} \left( \sum_{K \subseteq F} \rho(R, R \cup (F \setminus K)) x^{|K|} \right) \left( \sum_{L \subseteq T} \rho(R \cup L, R \cup T) y^{|L|} \right)$$

**Theorem 3.5** The coefficients of the arithmetic Tutte polynomial $M_{\mathcal{A}}(x, y)$ of a pseudo- arithmetic matroid $\mathcal{A}$ are nonnegative. Moreover, pseudo- arithmetic matroids are the most general objects closed under deletion and contraction and such that the associated arithmetic Tutte polynomials have nonnegative coefficients.

# 4 Generalizations of Crapo's formula

The following combinatorial interpretation of the coefficients of the Tutte polynomial was proved in [4].

**Theorem 4.1 (Crapo)**

$$T(x, y) = \sum_{B \in \mathbb{B}} x^{i(B)} y^{e(B)}.$$
Crapo's formula has been extended in [6] to arithmetic matroids. In order to do that, one constructs a list $L_E$ in which each maximal rank sublist $S$ appears $\rho(S) \doteq \rho(S, E)$ many times. Notice that if we extract the bases from our list $L_E$, each basis $B$ will show up exactly $m(B)$ times (by inclusion-exclusion).

Dually, we construct the list $L_E^*$ in the same way from the dual arithmetic matroid.

We denote by $\mathcal{B}$ the list of pairs $(B, T)$, where $B$ is a basis, $B \subseteq T$ and $T \in L_E$. The corresponding list in the dual will be denoted by $\mathcal{B}^*$. For every such pair $(B, T)$ we define $E(B, T)$ to be the set of elements of $T$ which are externally active for $B$. Then we define the local external activity $e(B, T) = |E(B, T)|$. Dually, we define $E^*(B^c, \tilde{T})$ in the same way for the basis $B^c$ in the dual and $\tilde{T} \in L_E^*$.

Let $\psi$ be the bijection between $\mathcal{B}$ and $\mathcal{B}^*$ introduced in [6], and defined as follows. For every basis $B$, identify the pairs $(B, T)$ and $(B, T') \in \mathcal{B}$ whenever $E(B, T) = E(B, T')$; dually, identify the pairs $(B^c, S)$ and $(B^c, S') \in \mathcal{B}^*$ whenever $E^*(B^c, S) = E^*(B^c, S')$. Then let $\psi_B$ be a bijection between the pairs $(B, \cdot)$ and the pairs $(B^c, \cdot)$ that equidistributes these pairs among each others (this exists by [6]; see this paper for details and examples). Let $\psi$ be the "join" of all these matchings $\psi_B, B \in \mathcal{B}$. We denote by $I(B, T) \doteq E^*(\psi(B, T))$ and we define the local internal activity $i(B, T) = |I(B, T)|$.

**Theorem 4.2 (D'Adderio-Moci)**

$$M_{\mathcal{A}}(x, y) = \sum_{(B,T) \in \mathcal{B}} x^{i(B,T)} y^{e(B,T)}.$$

We can extend this theorem to the multivariate arithmetic Tutte polynomial:

**Theorem 4.3**

$$Z_{\mathcal{A}}(q, \mathbf{v}) = \bar{Z}_{\mathcal{A}}(q, \mathbf{v}) \doteq q^{-\mathrm{rk}(E)} \sum_{(B,T) \in \mathcal{B}} \prod_{b \in B} v_b \prod_{e \in E(B,T)} (v_e + 1) \prod_{i \in I(B,T)} \left(\frac{q}{v_i} + 1\right)$$

In particular when all the multiplicities are 1, we get an analogue of Crapo's formula for Sokal's polynomial, i.e. Corollary ??.

# 5 Representable arithmetic matroids

Let $\mathcal{L} = (g_e)_{e \in E}$ be a finite list of vectors in a finitely generated abelian group $G$. Recall that such a group is isomorphic to $G_f \oplus G_t$, where $G_t$ is finite and $G_f$ is free abelian, i.e., it is isomorphic to $\mathbb{Z}^r$ for some $r \ge 0$. Then $G_t$ is called the *torsion* of $G$ and $r := \mathrm{rk}(G)$ is the *rank* of $G$. A matroid with ground set $E$ is naturally defined by $\mathrm{rk}(A) = \mathrm{rk}(\langle \mathcal{L}_A \rangle)$ where $\mathcal{L}_A = (g_e)_{e \in A}$ and $\langle \mathcal{L}_A \rangle$ is the subgroup generated by $\mathcal{L}_A$. In addition to the matroid structure $\mathcal{L}$ carries arithmetic information which is encoded as multiplicities. For $A \subseteq E$, let $H_A$ be the maximal subgroup of $G$ such that $\langle \mathcal{L}_A \rangle \le H_A$ and $|H_A : \langle \mathcal{L}_A \rangle| < \infty$, where $|H_A : \langle \mathcal{L}_A \rangle|$ denotes the index (as subgroup) of $\langle \mathcal{L}_A \rangle$ in $H_A$. The multiplicity $m(A)$ is defined as $m(A) := |H_A : \langle \mathcal{L}_A \rangle|$.

Equivalently, we can define $G_A := (G/\langle \mathcal{L}_A \rangle)_t$ as the torsion subgroup of $G/\langle \mathcal{L}_A \rangle$, and $m(A) := |G_A|$.

The fact that this function satisfies the original five axioms for an arithmetic matroid (and hence our axioms) has been verified in [6]; for (A1)–(A2) this also follows from Lemma 5.2 and 5.3 below.

**Remark 5.1** The most familiar situation is when $G = \mathbb{Z}^n$. However if we want to allow for deletion and contraction (see Section 3) we need the above more general setup.
We will denote by $\mathcal{M}_L$ the matroid determined by $\mathcal{L}$, and by $\mathcal{A}_L = (\mathcal{M}_L, m)$ the arithmetic matroid determined by $\mathcal{L}$. We say that an arithmetic matroid is representable if it comes from such a list.

**Lemma 5.2** Let $A \subset E$ and $e \in E \setminus A$. If rk$(A) < rk(A \cup \{e\})$ then there exists a group monomorphism $G_A \hookrightarrow G_{A \cup \{e\}}$. If rk$(A) = rk(A \cup \{e\})$ then there exists a group epimorphism $G_A \twoheadrightarrow G_{A \cup \{e\}}$.

Furthermore, if $A \subseteq B \subseteq E$ are such that rk$(A) = rk(B)$, the composition morphism $G_A \to G_B$ does not depend on the order chosen on $B \setminus A$. In the same way, if rk$^*(A) = rk^*(B)$, the composition morphism $G_A \to G_B$ does not depend on the order chosen on $B \setminus A$.

**Lemma 5.3** For each molecule $[R, R \cup F \cup T]$

$$ \frac{G_{R \cup F}}{G_R} \cong \frac{G_{R \cup F \cup T}}{G_{R \cup T}}. $$

# 6 A Fortuin-Kasteleyn quasi-polynomial

Let $\mathcal{G} = (V, E)$ be a finite graph with vertex set $V$ and edge set $E$. In [11] the multivariate Tutte polynomial of a graph was defined as

$$ Z_{\mathcal{G}}(q, \mathbf{v}) := \sum_{A \subseteq E} q^{k(A)} \prod_{e \in A} v_e, $$

where $k(A)$ denotes the number of connected components in the subgraph $(V, A)$. The multivariate Tutte polynomial has an interpretation in statistical physics as the partition function of the q-state Potts model.

**Theorem 6.1 (Fortuin-Kasteleyn)** For any positive integer $q$,

$$ Z_{\mathcal{G}}(q, \mathbf{v}) = \sum_{\sigma: V \to [q]} \prod_{e=ij \in E} (1 + v_e \delta(\sigma(i), \sigma(j))), $$

where $\delta$ is the Kronecker delta and $[q] := \{1, \dots, q\}$.

Theorem 6.1 is known as the Fortuin-Kasteleyn representation of the q-state Potts model. Our main goal of this section is to generalize this theorem to list of vectors in finitely generated abelian groups.

We define here a generalization of the Potts model which is similar to the one studied by Caracciolo, Sportiello and Sokal, see [11, Section 3.2]. Let $\mathcal{L} = (g_e)_{e \in E}$ be a list of elements in a finitely generated abelian group $G$, and let $H$ be a finite abelian group. Then

$$ Z_{\mathcal{L}}(G, H, \mathbf{v}) := \sum_{\phi \in \mathrm{Hom}(G, H)} \prod_{e \in E} (1 + v_e \delta(\phi(g_e), 0)). $$

The special case when $H = \mathbb{Z}_q := \mathbb{Z}/q\mathbb{Z}$ will be particularly interesting, and we set

$$ Z_{\mathcal{L}}^{P}(q, \mathbf{v}) := \sum_{\phi \in \mathrm{Hom}(G, \mathbb{Z}_q)} \prod_{e \in E} (1 + v_e \delta(\phi(g_e), 0)). $$

We will prove that $Z_{\mathcal{L}}^P(q, \mathbf{v})$ is a quasi-polynomial in $q$ that interpolates between the arithmetic multi-variate Tutte polynomial $Z_{\mathcal{A}_L}(q, \mathbf{v})$ of the arithmetic matroid $\mathcal{A}_L$ and the multivariate Tutte polynomial $Z_{\mathcal{M}_L}(q, \mathbf{v})$ of its underlying matroid $\mathcal{M}_L$.
**Remark 6.2** Notice that $Z_{\mathcal{L}}^P(q, \mathbf{v})$ is not an invariant of the arithmetic matroid. For instance, the empty list in $\mathbb{Z}_4$ defines the same arithmetic matroid as the empty list in $\mathbb{Z}_2 \oplus \mathbb{Z}_2$, but $Z_{\mathcal{L}}^P(2, \mathbf{v})$ is equal to 2 in the former case, and to 4 in the latter.

For a group $G$ integer $q$ let $qG := \{qh : h \in G\}$, where $\mathbb{Z}$ acts on $G$ in the usual way.

**Theorem 6.3** If $H \cong \bigoplus_{i=1}^k \mathbb{Z}_{q_i}$ and $q = |H|$, then

$$Z_{\mathcal{L}}^{P}(G, H, \mathbf{v}) = q^{\mathrm{rk}(G)} \sum_{A \subseteq E} q^{-\mathrm{rk}(A)} \prod_{i=1}^{k} \frac{m(A)}{|q_i G_A|} \prod_{e \in A} v_e.$$

**Remark 6.4** Since $(q + |G|)G = qG$ holds for any finite group $G$ it follows that $Z_{\mathcal{L}}^P(q, \mathbf{v})$ is a quasi-polynomial in $q$.

Let LCM($\mathcal{L}$) denote the least common multiple of all $m(B)$, where $B \subseteq E$ is a bases. When $G = \mathbb{Z}^n$ and $\mathcal{L}$ has rank $r$, then LCM($\mathcal{L}$) equals the least common multiple of all non-zero $r \times r$ minors of $\mathcal{L}$. Define two subsets of $\mathbb{Z}_+ := \{n \in \mathbb{Z} : n > 0\}$ as follows

$$\mathbb{Z}_M(\mathcal{L}) := \{q \in \mathbb{Z}_+ : \mathrm{GCD}(q, \mathrm{LCM}(\mathcal{L})) = 1\},$$

$$\mathbb{Z}_A(\mathcal{L}) := \{q \in \mathbb{Z}_+ : qG_B = (0) \text{ for all bases } B \subseteq E\}.$$

For example if $q$ is a multiple of LCM($\mathcal{L}$), then $q \in \mathbb{Z}_A(\mathcal{L})$.

**Theorem 6.5** Let $|H| = q$. Then $q \in \mathbb{Z}_M(\mathcal{L})$ if and only if

$$Z_{\mathcal{L}}^{P}(G, H, \mathbf{v}) = q^{\mathrm{rk}(G)} Z_{\mathcal{M}_{\mathcal{L}}}(q, \mathbf{v}),$$

as a polynomial in $\mathbf{v}$.

Note that when $\mathcal{L} \subset \mathbb{Z}^n = G$ is a totally unimodular matrix, i.e., $m(B) = 1$ for all bases $B$, then $\mathbb{Z}_M(\mathcal{L}) = \mathbb{Z}_A(\mathcal{L}) = \mathbb{Z}_+$. Thus Theorem 6.5 extends [11, Theorem 3.1] and can also be seen as a refinement of the “finite field method” to compute the characteristic polynomial of a hyperplane arrangement, see [2] (or its Tutte polynomial, see [1, 13]). The proof of the following Theorem follows immediately from Theorem 6.3:

**Theorem 6.6** Let $q$ be a positive integer. Then $q \in \mathbb{Z}_A(\mathcal{L})$ if and only if

$$Z_{\mathcal{L}}^{P}(q, \mathbf{v}) = q^{\mathrm{rk}(G)} Z_{\mathcal{A}_{\mathcal{L}}}(q, \mathbf{v}),$$

as a polynomial in $\mathbf{v}$.

Theorem 6.6 is a refinement of the finite field method to compute the characteristic polynomial of a toric arrangement, see [8].

**Example 6.7** Let us see why Theorem 6.1 is a special case of Theorem 6.6. Let $G = (V, E)$ be a graph on $V = [n]$. Let further $G = \mathbb{Z}^n$ and $\mathcal{L} = (g_e)_{e \in E}$ where $g_e$ is the vector with $i$th coordinate 1 and $j$th coordinate $-1$ and the other coordinates $0$, where $e = \{i, j\}$ and $i < j$. Then $m(A) = 1$ for all $A$ since the matrix $\mathcal{L}$ is totally unimodular, and hence $G_A = (0)$ for all $A \subseteq E$. Moreover $\mathrm{Hom}(G, \mathbb{Z}_q) = \mathbb{Z}_q^V$ so Theorem 6.1 follows.
**Example 6.8** Let $G = \mathbb{Z}^3$ and

$$ \mathcal{L} = \begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}. $$

Then $M_\mathcal{L}$ is the non-Fano matroid $F_7^-$, which is not a regular matroid. The multiplicities of the bases are given by the absolute values of the nonzero $3 \times 3$ minors and are thus equal to 1 or 2. Hence for $q$ a positive integer

$$ Z_{\mathcal{L}}^{P}(q, \mathbf{v}) = q^3 \begin{cases} Z_{F_7^-}(q, \mathbf{v}), & \text{if } q \text{ is odd,} \\ Z_{A_{\mathcal{L}}}(q, \mathbf{v}), & \text{if } q \text{ is even.} \end{cases} $$

By analogy with the graphic case (see Section 8) we call an element $\phi \in \operatorname{Hom}(G, \mathbb{Z}_q)$ a proper $(\mathcal{L}, q)$-coloring if $\phi(g_e) \neq 0$ for all $e \in E$. We denote by $\chi_\mathcal{L}(q)$ the number of such colorings. Notice that by definition this is equal to the evaluation of $Z_\mathcal{L}^P(q, \mathbf{v})$ at $v_e = -1$ for all $e \in E$, that we denote by $Z_\mathcal{L}^P(q, -1)$. We call $\chi_\mathcal{L}(q)$ the chromatic quasi-polynomial. We get the following “color”-interpretation of the characteristic polynomial of $M_\mathcal{L}$ and the arithmetic characteristic polynomial of $A_\mathcal{L}$:

**Corollary 6.9** Let $q$ be a positive integer.

If $q \in \mathbb{Z}_M(\mathcal{L})$, then

$$ \chi_{\mathcal{L}}(q) = (-1)^{\mathrm{rk}(E)} q^{\mathrm{rk}(G)-\mathrm{rk}(E)} T_{\mathcal{L}}(1-q, 0). $$

If $q \in \mathbb{Z}_A(\mathcal{L})$, then

$$ \chi_{\mathcal{L}}(q) = (-1)^{\mathrm{rk}(E)} q^{\mathrm{rk}(G)-\mathrm{rk}(E)} M_{\mathcal{L}}(1-q, 0). $$

# 7 Generalized flows

For $A \subseteq E$ define a homomorphism $\Psi_A^q : \mathbb{Z}_q^A \to G/qG$ by

$$ \Psi_A^q(\phi) = \sum_{e \in A} \phi(e)g_e + qG. $$

By analogy with $q$-flows in graphs (see Section 8), an element $\phi \in \ker(\Psi_E^q)$ will be called a $(\mathcal{L}, q)$-flow. If in addition $\phi(e) \neq 0$ for all $e \in E$, $\phi$ is called nowhere-zero. Hence a nowhere-zero $(\mathcal{L}, q)$-flow is a map $\phi : E \to \mathbb{Z}_q \setminus \{0\}$ for which $\sum_{e \in E} \phi(e)g_e = 0$ in $G/qG$. We denote by $\chi_\mathcal{L}^*(q)$ the number of nowhere-zero $(\mathcal{L}, q)$-flows.

The multivariate arithmetic flow polynomial of $\mathcal{L}$ is defined by

$$ F_{\mathcal{L}}(q, \mathbf{v}) := \sum_{\phi \in \ker(\Psi_E^q)} \prod_{e \in E} (1 + v_e \delta(\phi(e), 0)). $$

Notice that by definition $\chi_\mathcal{L}^*(q)$ is equal to the evaluation of $F_\mathcal{L}(q, \mathbf{v})$ at $v_e = -1$ for all $e \in E$, that we denote by $F_\mathcal{L}(q, -1)$. We call $\chi_\mathcal{L}^*(q)$ the flow quasi-polynomial. Indeed we have:

**Theorem 7.1** For positive integers $q$,

$$ F_{\mathcal{L}}(q, \mathbf{v}) = q^{-\mathrm{rk}(G)} \frac{|qG_t|}{m(\emptyset)} \left( \prod_{e \in E} v_e \right) Z_{\mathcal{L}}^{P}(q, q/\mathbf{v}), $$

where $q/\mathbf{v} := \{q/v_e\}_{e \in E}$. Moreover,
1. If $q \in \mathbb{Z}_M(\mathcal{L})$, then

$$F_{\mathcal{L}}(q, \mathbf{v}) = \left( \prod_{e \in E} v_e \right) Z_{\mathcal{L}}^{M}(q, q/\mathbf{v}).$$

2. If $q \in \mathbb{Z}_A(\mathcal{L})$, then

$$F_{\mathcal{L}}(q, \mathbf{v}) = \frac{1}{m(\emptyset)} \left( \prod_{e \in E} v_e \right) Z_{\mathcal{L}}^{A}(q, q/\mathbf{v}).$$

The following result follows immediately from Theorem 7.1 and Formulae (1), (2).

**Corollary 7.2** Let $q$ be a positive integer.

1. If $q \in \mathbb{Z}_M(\mathcal{L})$, then

$$\chi_{\mathcal{L}}^{*}(q) = (-1)^{|E|-\mathrm{rk}(E)} T_{\mathcal{L}}(0, 1-q)$$

2. If $q \in \mathbb{Z}_A(\mathcal{L})$, then

$$\chi_{\mathcal{L}}^{*}(q) = (-1)^{|E|-\mathrm{rk}(E)} (m(\emptyset))^{-1} M_{\mathcal{L}}(0, 1-q)$$

# 8 Graphs

Let us see how colorings and flows on graphs may be generalized using the ideas in the previous sections.

Let $\mathcal{G} = (V, E)$ be a finite graph. Following [7], we assume that $E$ is a disjoint union $E = R \cup D$, where we call the elements of $R$ regular edges and the elements of $D$ dotted edges. (Of course we can assume $D = \emptyset$ and then $\mathcal{G}$ is a standard graph; however this general setting is necessary for having deletion-contraction).

For each $e = \{i, j\} \in E$ choose an element $\ell(e) \in \mathbb{Z}^V$ such that all coordinates except possibly the $i$th and $j$th are zero. Denote the $i$th coordinate of $\ell(e)$ by $e^i$. We denote by $\mathcal{L}_R$ and $\mathcal{L}_D$ the lists of vectors in $\mathbb{Z}^V$ corresponding to elements of $R$ and $D$ respectively.

Then we look at the group $G := \mathbb{Z}^n / \langle \mathcal{L}_D \rangle$, and we identify the elements of $\mathcal{L}_R$ with the corresponding cosets in $G$. This gives as an arithmetic matroid $\mathcal{A}_{\mathcal{G}, \ell}$. We denote by $Z_{\mathcal{G}, \ell}(q, \mathbf{v})$ the associated multivariate arithmetic Tutte polynomial.

A proper $(\ell, q)$-coloring is then a map $\phi : V \to \mathbb{Z}_q$ such that

* $\phi(i)e^i + \phi(j)e^j \neq 0$, for all edges $e = \{i, j\} \in R$;

* $\phi(i)e^i + \phi(j)e^j = 0$, for all edges $e = \{i, j\} \in D$.

A nowhere-zero $(\ell, q)$-flow is a map $\phi : E \to \mathbb{Z}_q$ such that $\phi(e) \neq 0$ for all $e \in R$ and such that the weighted Kirchhoff laws hold:

$$\sum_{e \in I} \phi(e) e^i = 0, \quad \text{for all } i \in V.$$

We define the arithmetic chromatic quasi-polynomial $\chi_{\mathcal{G}, \ell}(q)$ and the arithmetic flow quasi-polynomial $\chi_{\mathcal{G}, \ell}^{*}(q)$ of $(\mathcal{G}, \ell)$ to be the functions that assign to each positive integer $q$ the number of proper $(\ell, q)$-colorings and the number of nowhere-zero $(\ell, q)$-flows respectively. It is easy to see that these definitions agree with the more general ones given in the previous sections. Hence

$$\chi_{\mathcal{G}, \ell}(q) = Z_{\mathcal{G}, \ell}^{P}(q, -1)$$
and

$$ \chi_{G, \ell}^{*}(q) = F_{G, \ell}(q, -1) $$

are truly quasi-polynomials.

Clearly these functions generalize the classical chromatic and flow polynomial (in which $D = \emptyset$) and $e^i = 1$, $e^j = -1$ for all $e \in R$) and also their arithmetic versions introduced in [7] (in which $e^i = -e^j \neq 0$ and $q \in \mathbb{Z}_A(\mathcal{L})$).

Let $k$ be the number of connected components of the graph $G$, and $\bar{V}$ be the set of vertices of the graph obtained from $G$ by contracting all the dotted edges. Notice that $k = \mathrm{rk}(G) - \mathrm{rk}(E)$ and $|\bar{V}| = \mathrm{rk}(G)$. Then by Corollaries 6.9 and 7.2 we have the following results:

**Corollary 8.1**

$$ \chi_{G, \ell}(q) = \begin{cases} (-1)^{|\bar{V}|-k} q^k M_{G, \ell}(1-q, 0) & \text{if } q \in \mathbb{Z}_A(\mathcal{L}); \\ (-1)^{|\bar{V}|-k} q^k T_{G, \ell}(1-q, 0) & \text{if } q \in \mathbb{Z}_M(\mathcal{L}). \end{cases} $$

$$ \chi_{G, \ell}^{*}(q) = \begin{cases} (-1)^{|R|-|\bar{V}|+k} q^{|D|-|\bar{V}|+|\bar{V}|} M_{G, \ell}(0, 1-q) & \text{if } q \in \mathbb{Z}_A(\mathcal{L}); \\ (-1)^{|R|-|\bar{V}|+k} q^{|D|-|\bar{V}|+|\bar{V}|} T_{G, \ell}(0, 1-q) & \text{if } q \in \mathbb{Z}_M(\mathcal{L}). \end{cases} $$

# 9 A geometrical interpretation in the realizable case

We keep the notation of the previous Sections. In particular, let $\mathcal{L}$ be a list of elements in $G = G_f \oplus G_t$, and let $\mathcal{A}$ be the arithmetic matroid defined by $\mathcal{L}$ on the ground set $E$. For every $B \in \mathbb{B}$, we consider the molecule $[B \setminus I(B), B \cup E(B)]$.

Let $\mathcal{Z}(I(B)) = \sum_{e \in I(B), 0 \le t_e < 1} t_e g_e$ be the semi-open zonotope defined by $I(B)$, and let $\mathcal{P}(B)$ the set of its integer points. Notice that since $I(B)$ is an independent set, the coefficients $t_e$ are uniquely determined. Define a function

$$ \iota: \mathcal{P}(B) \to \mathbb{N} $$

in the following way: for every $p = \sum t_e g_e \in \mathcal{P}(B)$, let $\iota(p)$ be the number of $e \in I(B)$ such that $t_e = 0$.

Set $Y_B = ((B \setminus I(B)) \cup E(B))$. Let $\mathcal{T}(Y_B)$ be the generalized toric arrangement defined by $Y_B$; this is a set of subgroups (hence submanifolds) in the abelian compact Lie group $\mathrm{Hom}(G, S^1)$; namely, we have one subgroup $H_e$ for every $e \in Y_B$, having codimension 0 if $e$ is torsion and 1 otherwise. Let $\mathcal{C}(B)$ be the set of connected components of the subgroup $\cap_{e \in (B \setminus I(B))} H_e$. Define a function

$$ \eta: \mathcal{C}(B) \to \mathbb{N} $$

in the following way: for every $c \in \mathcal{C}(B)$, let $\eta(c)$ be the number of elements $e \in E(B)$ such that $H_e \supseteq c$. Then we have:

**Theorem 9.1**

$$ M_{\mathcal{L}}(x, y) = \sum_{B \in \mathbb{B}} \left( \sum_{p \in \mathcal{P}(B)} x^{\iota(p)} \right) \left( \sum_{c \in \mathcal{C}(B)} y^{\eta(c)} \right). $$
References

[1] F. ARDILA, *Computing the Tutte polynomial of a hyperplane arrangement*, Pacific J. Math.: 230, 1–26, 2007.

[2] C. A. ATHANASIADIS, *Characteristic polynomials of subspace arrangements and finite fields*, Adv. Math.: 122, 193–233, 1996.

[3] P. BRÄNDÉN, L. MOCI, *The multivariate arithmetic Tutte polynomial*, to appear on arXiv in June 2012.

[4] H. CRAPO, *The Tutte polynomial*, Aequationes Math., 3: 211-229, 1969.

[5] M. D'ADDERIO, L. MOCI, *Ehrhart polynomial of the zonotope and multiplicity Tutte polynomial*, arXiv:1102.0135 [math.CO], to appear on Eur. J. of Comb.

[6] M. D'ADDERIO, L. MOCI, *Arithmetic matroids, Tutte polynomial, and toric arrangements*, arXiv:1105.3220 [math.CO].

[7] M. D'ADDERIO, L. MOCI, *Graph colorings, flows and arithmetic Tutte polynomial*, arXiv:1108.5537 [math.CO].

[8] R. EHRENBORG, M. READDY, M. SLONE, *Affine and toric hyperplane arrangements*, Discrete Comput. Geom.: 41, 481–512, 2009.

[9] L. MOCI, *A Tutte polynomial for toric arrangements*, Trans. Amer. Math. Soc. 364 (2012), 1067–1088.

[10] L. MOCI, *Zonotopes, toric arrangements, and generalized Tutte polynomials*, Proceedings FPSAC 2010 (DMTCS).

[11] A. SOKAL, *The multivariate Tutte polynomial (alias Potts model) for graphs and matroids*, Surveys in combinatorics 2005, 173-226, London Math. Soc. Lecture Note Ser., 327, Cambridge Univ. Press, Cambridge, 2005.

[12] W. T. TUTTE, *A contribution to the theory of chromatic polynomials*, Canadian J. Math., 6: 80-91, 1954

[13] D. J. A. WELSH, G. P. WHITTLE, *Arrangements, channel assignments, and associated polynomials*, Adv. in Appl. Math. 23: 375–406, 1999.