# Arithmetic matroids and Tutte polynomials

Michele D'Adderio<fnref n="1" />† and Luca Moci<fnref n="2" />‡

**Abstract.** We introduce the notion of arithmetic matroid, whose main example is provided by a list of elements in a finitely generated abelian group. We study the representability of its dual, and, guided by the geometry of toric arrangements, we give a combinatorial interpretation of the associated arithmetic Tutte polynomial, which can be seen as a generalization of Crapo's formula.

**Résumé.** Nous introduisons la notion de matroïde arithmétique, dont le principal exemple est donné par une liste d'éléments dans un groupe abélien fini. Nous étudions la représentabilité de son dual, et, guidé par la géométrie des arrangements toriques, nous donnons une interprétation combinatoire du polynôme de Tutte arithmétique associée, ce qui peut être vu comme une généralisation de la formule de Crapo.

**Keywords:** arithmetic matroids, Gale duality, Tutte polynomial, toric arrangements

## 1 Introduction

Several mathematical constructions arise from a finite list of vectors $X$: hyperplane arrangements and zonotopes in geometry, box splines in numerical analysis, root systems and parking functions in combinatorics are only some of the most well-known examples. More recently, Holtz and Ron in [11], and Ardila and Postnikov in [1] introduced various algebraic structures capturing a rich description of these objects.

A central role in this framework is played by the combinatorial notion of *matroid*, which axiomatizes the linear dependence of the elements of $X$.

If the list $X$ lies in $\mathbb{Z}^n$, an even wider spectrum of mathematical objects appears. In their recent book [8], De Concini and Procesi explored (among other things) the connection between the *toric arrangement* associated to such a list and the *vector partition function*. Inspired by earlier work of Dahmen and Micchelli ([6], [7]), they view this relation as the discrete analogue of the one between hyperplane arrangement and multivariate spline. This approach has also surprising applications to the equivariant index theory ([9]). While the spline and the hyperplane arrangement only depend on the “linear algebra” of $X$, the partition function and the toric arrangement are also influenced by its “arithmetic”.

In fact, in order to have effective inductive methods, one needs to enlarge the picture from $\mathbb{Z}^n$ to its possible quotients, i.e. finitely generated abelian groups.

<footnote n="1">¹Max-Planck-Institut für Mathematik, Bonn, Germany</footnote>

<footnote n="2">²Dipartimento di Matematica "Guido Castelnuovo", Sapienza Università di Roma, Italy</footnote>

<footnote>†supported by the Max-Planck-Institut für Mathematik.</footnote>

<footnote>‡supported by PRIN 2009 - De Concini</footnote>
In this paper we introduce the notion of an arithmetic matroid: this is going to be a matroid $\mathfrak{M}$ together with a multiplicity function $m$ (see the definition in Section 2.3). This object axiomatizes both the linear algebra (via the matroid) and the arithmetics (via the multiplicity function) of a list of elements in a finitely generated abelian group. When an arithmetic matroid actually comes from such a list we will say that it is representable.

We introduce also the notion of a dual arithmetic matroid, and show that the dual of a representable matroid is representable. We provide an explicit construction that extends the Gale duality to our setting (Theorem 3.1).

To every arithmetic matroid $(\mathfrak{M}, m)$ we associate an arithmetic Tutte polynomial

$$M(x, y) := \sum_{A \subseteq X} m(A)(x-1)^{rk(X)-rk(A)}(y-1)^{|A|-rk(A)},$$

where $X$ is the list of vectors of $\mathfrak{M}$. When the multiplicity function $m$ is trivial (i.e. $m \equiv 1$), this gives the classical Tutte polynomial of the underlying matroid $\mathfrak{M}$. When $(\mathfrak{M}, m)$ is representable, this is the polynomial defined in [13], where it is shown to have several applications to vector partition functions, toric arrangements and zonotopes (cf. also [14], [3]). More recently, in [5] we provided also applications to graph theory, generalizing classical results about graphs due to Tutte ([17]) to graphs with edges labelled by integers.

The main result of this paper is to provide a combinatorial interpretation of the arithmetic Tutte polynomial of an arithmetic matroid, showing in particular the positivity of its coefficients (see Theorem 6.1). Our interpretation can be seen as an extension of the one given by Crapo in [2] for the classical Tutte polynomial: in fact, when the multiplicity function is trivial, we recover exactly Crapo's formula.

Our combinatorial ideas have their roots in the notion of a generalized toric arrangement, which provides the geometric inspiration and motivation of our work (see [4, Section 4]).

# 2 Arithmetic matroids: definitions and examples

## 2.1 Some notation

We will use the word *list* as a synonymous of multiset. Hence a list may contain several copies of the same element.

Given a list $X$, $\mathbb{P}(X)$ is the power set of $X$, i.e. the set of all sublists (including the empty list) of $X$.

## 2.2 Classical matroids

The axioms of a matroid can be given in several ways (see [15]). We state them in terms of the rank function, since they turn out to be more suitable for our work.

A matroid $\mathfrak{M} = \mathfrak{M}_X = (X, rk)$ is a list of vectors $X$ with a rank function $rk: \mathbb{P}(X) \to \mathbb{N} \cup \{0\}$ which satisfies the following axioms:

1. if $A \subseteq X$, then $rk(A) \le |A|$;

2. if $A, B \subseteq X$ and $A \subseteq B$, then $rk(A) \le rk(B)$;

3. if $A, B \subseteq X$, then $rk(A \cup B) + rk(A \cap B) \le rk(A) + rk(B)$.
A sublist $A \subseteq X$ is said to be *independent* if $rk(A) = |A|$. A maximal independent sublist is called a *basis*. It turns out that all the basis have the same cardinality ($rk(X)$), which is called the *rank* of the matroid. It is easy to see (see [15]) that the collection of the bases determines the matroid structure.

The dual of the matroid $\mathfrak{M} = (X, I)$ is defined as the matroid with the same list $X$ of vectors, and with bases the complements of the bases of $\mathfrak{M}$. We will denote it by $\mathfrak{M}^*$. Notice that the rank function of $\mathfrak{M}^*$ is given by $rk^*(A) := |A| - rk(X) + rk(X \setminus A)$. In particular the rank of $\mathfrak{M}^*$ is the cardinality of $X$ minus the rank of $\mathfrak{M}$.

We say that $v \in X$ is *dependent* on $A \subseteq X$ if $rk(A \cup \{v\}) = rk(A)$, while we say that $v \in X$ is *independent* on $A$ if $rk(A \cup \{v\}) = rk(A) + 1$.

## 2.3 Arithmetic matroids

An arithmetic matroid is a pair $(\mathfrak{M}_X, m)$, where $\mathfrak{M}_X$ is a matroid on a list of vectors $X$, and $m$ is a multiplicity function, i.e. $m : \mathbb{P}(X) \to \mathbb{N} \setminus \{0\}$ has the following properties:

(1) if $A \subseteq X$ and $v \in X$ is dependent on $A$, then $m(A \cup \{v\})$ divides $m(A)$;

(2) if $A \subseteq X$ and $v \in X$ is independent on $A$, then $m(A)$ divides $m(A \cup \{v\})$;

(3) if $A \subseteq B \subseteq X$ and $B$ is a disjoint union $B = A \cup F \cup T$ such that for all $A \subseteq C \subseteq B$ we have $rk(C) = rk(A) + |C \cap F|$, then

$$m(A) \cdot m(B) = m(A \cup F) \cdot m(A \cup T).$$

(4) if $A \subseteq B \subseteq X$ and $rk(A) = rk(B)$, then

$$\mu_B(A) := \sum_{A \subseteq T \subseteq B} (-1)^{|T|-|A|} m(T) \geq 0.$$

(5) if $A \subseteq B \subseteq X$ and $rk^*(A) = rk^*(B)$, then

$$\mu_B^*(A) := \sum_{A \subseteq T \subseteq B} (-1)^{|T|-|A|} m(X \setminus T) \geq 0.$$

When $B = X$ we will denote $\mu_B(A)$ and $\mu_B^*(A)$ by $\mu(A)$ and $\mu^*(A)$ respectively.

A discussion of these axioms can be found in [4, Remarks 3.2 and 3.6].

The idea of enriching the matroid structure with a multiplicity function was hinted in [13]. However no axioms were given for this function, so the concept remained vague. We have chosen the name “arithmetic matroid” to avoid confusion with previous constructions, and to emphasize the meaning of the multiplicity function.

By abuse of notation, we sometimes denote by $\mathfrak{M}$ both the arithmetic matroid and its underlying matroid.

We define the dual of an arithmetic matroid $(\mathfrak{M}_X, m)$ as the pair $(\mathfrak{M}_X^*, m^*)$, where $\mathfrak{M}_X^*$ is the dual of $\mathfrak{M}_X$, and for all $A \subseteq X$ we set $m^*(A) := m(X \setminus A)$. It can be shown (see [4, Lemma 1.2]) that this is in fact an arithmetic matroid.
**Remark 2.1** Notice that setting $m(S) = 1$ for all the sublists $S \subseteq X$ of vectors in a matroid we get trivially a multiplicity function, and hence a structure of an arithmetic matroid. In this case we call $m$ trivial. In fact this multiplicity function does not add anything to the matroid structure. In this sense the notion of an arithmetic matroid can be seen as a generalization of the one of a matroid. Of course there are more interesting examples.

## 2.4 The main example

The prototype of an arithmetic matroid (which in fact inspired our definition) is the one that we are going to associate now to a finite list $X$ of elements of a finitely generated abelian group $G$. We recall that such a group is isomorphic to $G_f \oplus G_t$, where $G_t$ is the torsion subgroup of $G$, which is finite, and $G_f$ is free abelian, i.e it is isomorphic to $\mathbb{Z}^r$ for some $r \ge 0$. Notice that in general we have many choices for $G_f$, while $G_t$ is intrinsically defined.

Given a sublist $A \subseteq X$, we will denote by $\langle A \rangle$ the subgroup of $G$ generated by the underlying set of $A$.

We define the rank of a sublist $A \subseteq X$ as the maximal rank of a free (abelian) subgroup of $\langle A \rangle$. This defines a matroid structure on $X$.

For $A \in \mathbb{P}(X)$, let $G_A$ be the maximal subgroup of $G$ such that $\langle A \rangle \le G_A$ and $|G_A : \langle A \rangle| < \infty$, where $|G_A : \langle A \rangle|$ denotes the index (as subgroup) of $\langle A \rangle$ in $G_A$. Then the multiplicity $m(A)$ is defined as $m(A) := |G_A : \langle A \rangle|$.

Since we are interested in the multiplicities, clearly we can always assume (and we will do it) that $\langle X \rangle$ has finite index in $G$: otherwise we just replace $G$ by $G_X$, i.e. the maximal subgroup of $G$ in which $\langle X \rangle$ has finite index.

Notice that $m(\emptyset)$ equals the cardinality of $G_t$. In particular $m(\emptyset) = 1$ if and only if $G$ is free abelian.

We need to check that the function $m$ that we just defined is a multiplicity function. The first axiom is easy to check. The second axiom for $m$ is just the first axiom for the dual. Hence it would follow from the first one if we can realize the dual arithmetic matroid as a list of elements in a finitely generated group as we just did. This is the content of the next section.

The third axiom for $m$ is a Lemma in algebra which is proved in [4, Lemma 1.4].

The fourth axiom for $m$ is a consequence of geometry: in fact by [4, Lemma 4.1], $\mu_B(A)$ equals the cardinality of a set of subvarieties of a torus (see [4, Section 1.4]). Therefore it is clearly nonnegative.

The fifth axiom for $m$ is the dual of the fourth one, and again it will follow from the realization of the dual arithmetic matroid by a list of elements in a finitely generated abelian group, which is proved in the next section.

**Example 2.2** Consider the list $X := \{v_1 := (3,0), v_2 := (2,-2), v_3 := (-3,3)\} \subseteq G := \mathbb{Z}^2$.

**Remark 2.3** Notice that in $\mathbb{Z}^m$, to compute the multiplicity of a list of elements, it is enough to see the elements as the columns of a matrix, and to compute the greatest common divisor of its minors of order the rank of the matrix (cf. [16, Theorem 2.2]).

Applying Remark 2.3 we compute $m(\emptyset) = m(\{v_2, v_3\}) = 1$, $m(\{v_2\}) = 2$, $m(\{v_1, v_2, v_3\}) = m(\{v_1\}) = m(\{v_3\}) = 3$, $m(\{v_1, v_2\}) = 6$, $m(\{v_1, v_3\}) = 9$. It is easy to check that this is a multiplicity function.
## 2.5 Representability

We recall that a (classical) matroid is said to be *representable in characteristic 0* or *0-representable* if it is realized by a list of vectors in $\mathbb{R}^n$.

We say that an arithmetic matroid is *representable* if it is realized by a list of elements in a finitely generated abelian group.

By “realized” we mean that the rank and the multiplicity functions are defined as in Section 2.4.

We say that an arithmetic matroid is:

* 0-representable if its underlying matroid is;

* torsion-free if $m(\emptyset) = 1$;

* GCD if its multiplicity function satisfies the GCD rule:

$m(A)$ equals the greatest common divisor (GCD) of the multiplicities of the maximal independent sublists of $A$, i.e.

$$m(A) := \text{GCD}(\{m(B) \mid B \subseteq A \text{ and } |B| = rk(B) = rk(A)\}).$$

**Remark 2.4** If an arithmetic matroid is representable, then it is clearly 0-representable (just tensor with the rational numbers $\mathbb{Q}$). Moreover, if it is also torsion-free, then it is easily seen to be GCD (cf. Remark 2.3).

This provides two classes of examples of non-representable arithmetic matroids:

**Example 2.5** Let $\mathfrak{M}$ be non-0-representable. For example, consider the Fano matroid, i.e. the matroid defined by the 7 nonzero elements of $\mathbb{F}_2$, where $\mathbb{F}_2$ is the field with two elements. Then every multiplicity function (e.g. the trivial one) will make it into a non-representable arithmetic matroid.

**Example 2.6** Let us take $X = \{a, b, c\}$ and define $\mathfrak{M}$ as the matroid on $X$ having bases $\{a, b\}$, $\{b, c\}$ and $\{a, c\}$. Clearly, $\mathfrak{M}$ is realized by three non-collinear vectors in a plane. Now set the multiplicities of the bases to be 2 and all the others to be 1. It is easy to check that this is an arithmetic matroid, but it is not GCD, since $m(X) = 1 \neq 2$. Hence it is not representable.

# 3 Representability of the dual

In this section we state that the dual of a representable arithmetic matroid is still representable. Our construction gives an extension of the Gale duality [10] to our setting.

Consider an arithmetic matroid $\mathfrak{M}$ represented by a list $X$ of elements of a finitely generated abelian group $G$. We are looking for a finitely generated abelian group $G'$ and a finite list $X'$ of its elements representing the matroid $\mathfrak{M}^*$.

Notice that of course we need to have $|X| = |X'|$. Also, the rank of $\mathfrak{M}^*$ must be $|X|$ minus the rank of $\mathfrak{M}$.

We start with a presentation of our finitely generated abelian group $G$ as $\mathbb{Z}^r \oplus (\mathbb{Z}/d_1\mathbb{Z}) \oplus (\mathbb{Z}/d_2\mathbb{Z}) \oplus \cdots \oplus (\mathbb{Z}/d_s\mathbb{Z})$, where $d_i$ divides $d_{i+1}$ for $i = 1, 2, \dots, s-1$. It is well known that such a presentation exists and it is unique up to isomorphism. We realize this presentation as a quotient $\mathbb{Z}^{r+s}/\langle Q \rangle$, where $Q$ is the list of vectors $q_1, q_2, \dots, q_s \in \mathbb{Z}^{r+s}$, where $q_i$ has $d_i$ in the $(r+i)$-th position, and 0 elsewhere. We remember the order in which the elements of the list $Q$ are given.
Now a finite list $X \subseteq G$ is given by a list of cosets $X = \{\bar{v}_1, \bar{v}_2, \dots, \bar{v}_k\}$, where of course with $\bar{v}_i$ we denote the coset $v_i + \langle Q \rangle$ for $v_i \in \mathbb{Z}^{r+s}$. We choose representatives $v_i \in \mathbb{Z}^{r+s}$ for the cosets, which are determined up to linear combinations of elements from $Q$. We set $\tilde{X} := \{v_1, v_2, \dots, v_k\}$ a list of elements in $\mathbb{Z}^{r+s}$. Also in this case we remember the order in which the elements of $\tilde{X}$ are given.

Hence we consider the $(r+s) \times (k+s)$ matrix $[\tilde{X} \sqcup Q]$, whose columns are the elements from $\tilde{X}$ in the given order first and from $Q$ in the given order next. We call $(\tilde{X}Q)^t$ the list of its rows in the given order from top to bottom, which are vectors in $\mathbb{Z}^{k+s}$. Hence we set $G' := \mathbb{Z}^{k+s}/\langle (\tilde{X}Q)^t \rangle$, and $X' := \{\bar{e}_1, \bar{e}_2, \dots, \bar{e}_k\}$ will be the list of cosets in $G'$, where as usual $e_i \in \mathbb{Z}^{k+s}$ denotes the vector with 1 in the $i$-th position and 0 elsewhere.

We call $(\mathfrak{M}', m')$ the arithmetic matroid associated to the pair $(G', X')$.

We denote $\{1, 2, \dots, k\}$ by $[k]$, and for $S \subseteq [k]$ we denote by $S^c$ its complement in $[k]$, and we set $\bar{v}_S := \{\bar{v}_i \in X \mid i \in S\}$ and $\bar{e}_S := \{\bar{e}_i \in X' \mid i \in S\}$.

The main result of this section is the following theorem. For a proof see [4, Theorem 2.2].

**Theorem 3.1** The bijection $\bar{e}_S \leftrightarrow \bar{v}_S$ for $S \subseteq [k]$ is an isomorphism of arithmetic matroids between $\mathfrak{M}'$ and $\mathfrak{M}^*$, i.e. it preserves both the rank and the multiplicity functions.

This completes the proof that the “main example” (Section 2.4) gives indeed an arithmetic matroid.

**Example 3.2** Consider again the list $X := \{v_1 := (3,0), v_2 := (2,-2), v_3 := (-3,3)\} \subseteq G := \mathbb{Z}^2$ of Example 2.2.

Consider the matrix $$ \begin{pmatrix} 3 & 2 & -3 \\ 0 & -2 & 3 \end{pmatrix} $$ whose columns are $v_1, v_2, v_3$, and call $w_1 := (3, 2, -3)$, $w_2 := (0, -2, 3)$ the rows. Consider the list

$$ X' := \{\bar{e}_1, \bar{e}_2, \bar{e}_3\} \subseteq G' := \mathbb{Z}^3 / \langle w_1, w_2 \rangle. $$

It is easy to check that the bijection given by $v_i \leftrightarrow \bar{e}_i$, for $i = 1, 2, 3$ is an isomorphism of arithmetic matroids between $(\mathfrak{M}_X^*, m^*)$ and the one associated to $X'$ in $G'$, i.e. it preserves ranks and multiplicities.

# 4 Arithmetic Tutte polynomial and deletion-contraction

## 4.1 Arithmetic Tutte polynomial

Following [13], we associate to an arithmetic matroid $\mathfrak{M}_X$ its arithmetic Tutte polynomial $M_X(x, y) = M(\mathfrak{M}_X; x, y)$ defined as

$$ M_X(x, y) := \sum_{A \subseteq X} m(A)(x-1)^{rk(X)-rk(A)}(y-1)^{|A|-rk(A)}. \quad (4.1) $$

Notice that in case $m \equiv 1$, we get the classical Tutte polynomial of the underlying matroid (cf. [4, Section 3]).

**Example 4.1** Consider again the list $X := \{v_1 := (3,0), v_2 := (2,-2), v_3 := (-3,3)\} \subseteq G := \mathbb{Z}^2$ of
Example 2.2. We compute

$$
\begin{align*}
M_X(x, y) &= \sum_{A \subseteq X} m(A)(x-1)^{rk(X)-rk(A)}(y-1)^{|A|-rk(A)} \\
&= (x-1)^2 + (3+2+3)(x-1) + (x-1)(y-1) + (6+9) + 3(y-1) \\
&= x^2 + 5x + 6 + xy + 2y.
\end{align*}
$$

**Remark 4.2** If ($\mathfrak{M}_X, m$) is an arithmetic matroid, then the arithmetic Tutte polynomial of the dual ($\mathfrak{M}_X^*, m^*$) is

$$
\begin{align*}
M(\mathfrak{M}_X^*; x, y) &= \\
&= \sum_{A \subseteq X} m^*(A)(x-1)^{rk^*(X)-rk^*(A)}(y-1)^{|A|-rk^*(A)} \\
&= \sum_{A \subseteq X} m(X \setminus A)(x-1)^{|X|-rk(X)+rk(\emptyset)-(|A|-rk(X)+rk(X\setminus A))}(y-1)^{|A|-|(|A|-rk(X)+rk(X\setminus A))} \\
&= \sum_{A \subseteq X} m(X \setminus A)(x-1)^{|X\setminus A|-rk(X\setminus A)}(y-1)^{rk(X)-rk(X\setminus A)} = M(\mathfrak{M}_X; y, x).
\end{align*}
$$

Hence interchanging the variables x and y in the arithmetic Tutte polynomial of the original arithmetic
matroid gives the arithmetic Tutte polynomial of its dual.

This polynomial has many applications to toric arrangements (see [13], or [4, Section 4]), zonotopes ([3]), Dahmen-Micchelli spaces ([13], [7], [6]; see also [8], [12] for related topics) and labelled graphs ([5]).

Our main goal will be to give a combinatorial interpretation of the polynomial $M_X$ for an arithmetic
matroid. By doing this, we will get in particular the positivity of its coefficients.

4.2 Deletion and contraction

We introduce two fundamental constructions. Recall that given a matroid $\mathfrak{M}_X$ and a vector $v \in X$, we can define the *deletion* of $\mathfrak{M}_X$ as the matroid $\mathfrak{M}_{X_1}$, whose list of vectors is $X_1 := X \setminus \{v\}$, and whose independent lists are just the independent lists of $\mathfrak{M}_X$ contained in $X_1$. Notice that the rank function $rk_1$ of $\mathfrak{M}_{X_1}$ is just the restriction of the rank function $rk$ of $\mathfrak{M}_X$.

Given an arithmetic matroid $(\mathfrak{M}_X, m)$ and a vector $v \in X$, we define the *deletion* of $(\mathfrak{M}_X, m)$ as
the arithmetic matroid $(\mathfrak{M}_{X_1}, m_1)$, where $\mathfrak{M}_{X_1}$ is the deletion of $\mathfrak{M}_X$ and $m_1(A) := m(A)$ for all
$A \subseteq X_1 = X \setminus \{v\}$. It is easy to check that this is in fact an arithmetic matroid.

Recall that given a matroid $\mathfrak{M}_X$ and a vector $v \in X$, we can define the *contraction* of $\mathfrak{M}_X$ as the
matroid $\mathfrak{M}_{X_2}$, whose list of vectors is $X_2 := X \setminus \{v\}$, and whose rank function $rk_2$ is given by $rk_2(A) :=$
$rk(A \cup \{v\}) - rk(\{v\})$, where of course $rk$ is the rank function of $\mathfrak{M}_X$.

Given an arithmetic matroid $(\mathfrak{M}_X, m)$ and a vector $v \in X$, we define the *contraction* of $(\mathfrak{M}_X, m)$ as the arithmetic matroid $(\mathfrak{M}_{X_2}, m_2)$, where $\mathfrak{M}_{X_2}$ is the contraction of $\mathfrak{M}_X$ and $m_2(A) := m(A \cup \{v\})$ for all $A \subseteq X_2 = X \setminus \{v\}$. It is easy to check that this is in fact an arithmetic matroid.
**Example 4.3** If an arithmetic matroid $(\mathfrak{M}_X, m)$ is represented by a list $X$ of elements of $G$, it is easy to check that the deletion corresponds to the arithmetic matroid $(\mathfrak{M}_{X_1}, m_1)$ of the sublist $X_1 := X \setminus \{v\}$, while the contraction corresponds to the arithmetic matroid $(\mathfrak{M}_{X_2}, m_2)$ of the list $\bar{X} := \{a + \langle v \rangle \mid a \in X \setminus \{v\}\}$ of cosets in $G/\langle v \rangle$.

Observe that the deletion of $v \in X$ in $\mathfrak{M}_X$ corresponds to the contraction of $v \in X$ in $\mathfrak{M}_X^*$, and viceversa the contraction of $v \in X$ in $\mathfrak{M}_X$ corresponds to the deletion of $v \in X$ in $\mathfrak{M}_X^*$.

The following theorem is proved in [4, Lemmas 6.4, 6.6 and 7.6].

**Theorem 4.4** Let $(\mathfrak{M}_X, m)$ be an arithmetic matroid. Let $v \in X$ and set $X_1 = X_2 := X \setminus \{v\}$. We denote by $M_{X_1}(x, y)$ and $M_{X_2}(x, y)$ the arithmetic Tutte polynomials of the deletion and the contraction of $v$ respectively.

$$M_X(x, y) = \begin{cases} M_{X_1}(x, y) + M_{X_2}(x, y) & \text{if } rk(\{v\}) = 1 \text{ and } rk(X \setminus \{v\}) = rk(X); \\ (x-1)M_{X_1}(x, y) + M_{X_2}(x, y) & \text{if } rk(X \setminus \{v\}) = rk(X) - 1; \\ M_{X_1}(x, y) + (y-1)M_{X_2}(x, y) & \text{if } rk(\{v\}) = 0. \end{cases}$$

# 5 Towards the combinatorial interpretation

## 5.1 General considerations

We want to give a combinatorial interpretation of the arithmetic Tutte polynomial. Let us look at a very easy but already nontrivial example.

**Example 5.1** Consider the list

$$X = \{v_1 := (3, 0), v_2 := (2, -2)\} \subseteq \mathbb{Z}^2.$$

In this case $X$ is the only basis of the matroid $\mathfrak{M}_X$. Here the multiplicity function is given by $m(\emptyset) = 1$, $m(\{v_2\}) = 2$, $m(\{v_1\}) = 3$ and $m(X) = 6$.

If we compute the polynomial $M_X(x, y)$ using the defining formula we get

$$M_X(x, y) = x^2 + 3x + 2.$$

Notice that the dual matroid $\mathfrak{M}_X^*$ is a rank 0 matroid, whose only basis is the empty list. Moreover in the dual arithmetic matroid $(\mathfrak{M}_X^*, m^*)$ the empty list has multiplicity 6.

We start our analysis with some general considerations. First of all we observe that specializing at $x = 1$ and $y = 1$ the polynomial $M_X(x, y)$ we get the sum of the multiplicities of the bases of the matroid. Notice also that the bases in the matroid $\mathfrak{M}_X$ correspond bijectively with the bases of $\mathfrak{M}_X^*$ under the involution of complementing with respect to $X$, and in fact by definition the multiplicity of a basis in $(\mathfrak{M}_X, m)$ is the same as the multiplicity of the complement in the dual $(\mathfrak{M}_X^*, m^*)$.

Hence, keeping in mind what Crapo did with the Tutte polynomial, it is natural to try to interpret the polynomial $\mathfrak{M}_X(x, y)$ as a sum over the bases counted with multiplicity of monomials in $y$ and $x$, whose exponents give some statistics on the basis and its complement (in the dual) respectively.

Already in the very simple Example 5.1 we see one of the difficulties of our task: in this example we only have one basis counted with multiplicity 6 both in $(\mathfrak{M}_X, m)$ and in $(\mathfrak{M}_X^*, m^*)$, but there are three distinct types of monomials!
The problem here is that the monomials of $M_X(x, y)$ are counted by a list and not just a set. Moreover, apparently for identical elements of the list the statistic may differ.

It turns out that a key ingredient for the understanding of the combinatorics behind the polynomial $M_X(x, y)$ is a suitable list of maximal rank sublists of $X$. The geometric considerations exposed in [4, Section 4] suggested us to look at them in the first place.

## 5.2 Two fundamental lists

Starting with our arithmetic matroid $(\mathfrak{M}_X, m)$, we construct a list $L_X$ of maximal rank sublists of $X$ in the following way.

To every maximal rank sublist $S$ of $X$ we associate the nonnegative (axiom (4)) integer

$$ \mu(S) := \sum_{T \supseteq S} (-1)^{|T| - |S|} m(T). $$

Then the list $L_X$ is defined as the list in which each maximal rank sublist $S$ appears $\mu(S)$ many times.

Notice that if we extract the bases from our list $L_X$, each basis $B$ will show up exactly $m(B)$ times: in fact, by inclusion-exclusion, each basis $B$ will appear $\sum \mu(T) = m(B)$ times, where the sum is taken over the sublists $T$ that contain $B$.

Dually, we construct the list $L_X^*$ in the same way from the dual arithmetic matroid $(\mathfrak{M}_X^*, m^*)$.

**Example 5.2** We consider again the Example 5.1. In this case we have $L_X = (X^6)$, while $L_X^* = (X, \{v_1\}, \{v_2\}^2, \emptyset^2)$, where we use an exponential notation for keeping track of the multiple copies of the sublists.

We introduce the following notation. The list of pairs $(B, T)$, where $B$ is a basis, $B \subseteq T$ and $T \in L_X$, counted with multiplicity $\mu(T)$, will be denoted by $B$. The corresponding list in the dual will be denoted by $B^*$.

## 5.3 Local external activity

We already observed that the multiplicity of the basis $B$ in $\mathfrak{M}_X$ is the same as the multiplicity of the basis $B^c$ in $\mathfrak{M}_X^*$. So it is now natural to interpret the polynomial $M_X(x, y)$ as a sum over the elements of $B$ of monomials in $x$ and $y$.

Let us fix a total order on $X$, and let $B$ be a basis extracted from $X$. We say that $v \in X \setminus B$ is *externally active* on $B$ if $v$ is dependent on the list of elements of $B$ following it (in the total order fixed on $X$). We say that $v \in B$ is *internally active* on $B$ if $v$ is externally active on the complement $B^c := X \setminus B$ in the dual matroid (where $B^c$ is a basis).

For every such pair $(B, T) \in B$ we define the statistic $e(B, T)$ to be the *local external activity* of the basis $B$ in the list $T$, i.e. the number of elements of $T \setminus B$ that are externally active on $B$. Notice that the torsion elements of $T$ are always active (if you don't want to deal with the empty list, this is a convention). Dually, we define $e^*(B^c, \tilde{T})$ in the same way for the basis $B^c$ in the dual and $B^c \subseteq \tilde{T} \in L_X^*$.

We would like to see $M_X(x, y)$ as $\sum x^{e^*(B^c, \tilde{T})} y^{e(B, T)}$.

**Example 5.3** We consider again the Example 5.1. In this case we have six identical pairs $(X, X)$ in the original arithmetic matroid, where obviously $e(X, X) = 0$, while in the dual we have four distinct pairs $(\emptyset, X)$, $(\emptyset, \{v_1\})$, $(\emptyset, \{v_2\})$ and $(\emptyset, \emptyset)$, where $e^*(\emptyset, X) = 2$, $e^*(\emptyset, \{v_1\}) = e^*(\emptyset, \{v_2\}) = 1$ and $e^*(\emptyset, \emptyset) = 0$.
In fact in this case the polynomial $M_X(x, y)$ is $x^2 + 3x + 2$.

In order to conclude our construction we need to face a nontrivial problem.

## 5.4 The matching problem

The problem here is again that we have a list of pairs and not just a set. So a pair $(B, T)$ can appear several times, as we have seen in the example above, and it needs to be matched with a suitable pair $(B^c, \tilde{T})$. In the last example we didn't have the problem of the matching since the statistic for the $y$ was always 0. But in general there could be many choices.

In general we have the problem of matching a pair $(B, T)$ with a suitable pair $(B^c, \tilde{T})$.

The idea is that we want to match the copies of a pair $(B, T) \in \mathcal{B}$ evenly among the copies of pairs $(B^c, \tilde{T}) \in \mathcal{B}^*$, and viceversa. With this we mean the following. Let $\ell((B, T), (B^c, \tilde{T}))$ be the number of copies of $(B, T)$ that we match with copies of $(B^c, \tilde{T})$. Than for distinct $T_1$ and $T_2$ in $L_X$ we want that

$$ \frac{\mu(T_1)}{\mu(T_2)} = \frac{\ell((B, T_1), (B^c, \tilde{T}))}{\ell((B, T_2), (B^c, \tilde{T}))} $$

for every $\tilde{T} \in L_X^*$. Dually, we want also

$$ \frac{\ell((B, T), (B^c, \tilde{T}_1))}{\ell((B, T), (B^c, \tilde{T}_2))} = \frac{\mu^*(\tilde{T}_1)}{\mu^*(\tilde{T}_2)} $$

for distinct $\tilde{T}_1$ and $\tilde{T}_2$ in $L_X^*$, and for every $T \in L_X$.

We call this property *equidistribution* of the matching. Notice that if such matching exists, than it must be unique up to identification of the copies of the pairs.

In general, we want to define for each basis $B$ in $X$ an equidistributed matching $\psi_B$ of the pairs in $\mathcal{B}$ of the form $(B, T)$ with the pairs in $\mathcal{B}^*$ of the form $(B^c, \tilde{T})$, and then “join” them together in a (necessarily equidistributed) matching $\psi$ from $\mathcal{B}$ to $\mathcal{B}^*$.

First of all we fix a total order on the elements of $X$.

For each basis $B$ in $X$, denote by $\mathcal{B}_B$ the sublist of pairs of $\mathcal{B}$ whose first coordinate is $B$. For each pair $(B, T)$ in this list, we ignore the elements of $T$ that are not externally active on $B$, identifying the pairs that differ only for such nonactive elements. We do the same for $B^c$ in $\mathcal{B}^*$. We claim that we can match evenly these pairs and we call $\psi_B$ such an equidistributed matching. Then $\psi$ will be just the “join” of these matchings.

Notice that in general the matching $\psi$ depends on the order that we choose.

The existence of the matching $\psi: \mathcal{B} \to \mathcal{B}^*$ is established in [4, Sections 6 and 7].

# 6 The main result

The following is the main result of the paper. A proof can be found in [4, Sections 6 and 7].

**Theorem 6.1** If $(\mathfrak{M}_X, m)$ is an arithmetic matroid, then

$$ M_X(x, y) = \sum_{(B, T) \in \mathcal{B}} x^{e^*(\psi(B, T))} y^{e(B, T)}, $$

where $\psi$ is the bijection between $\mathcal{B}$ and $\mathcal{B}^*$ described above.
**Remark 6.2** Notice that, even if in general the matching $\psi$ depends on the order that we choose, the polynomial $M_X(x, y)$ will not depend on it.

Also, observe that in the special case when all the multiplicities are equal to 1 the arithmetic Tutte polynomial reduces just to the classical Tutte polynomial of the matroid. Moreover in this case $L_X = (X) = L_{X^*}$, and our combinatorial description corresponds exactly to the one given by Crapo in [2]. In this sense our result can be seen as a generalization of Crapo's Theorem.

**Example 6.3** Consider again the list $X := \{v_1 := (3, 0), v_2 := (2, -2), v_3 := (-3, 3)\} \subseteq G := \mathbb{Z}^2$ of Example 2.2, and fix the total order $v_1 < v_2 < v_3$ on $X$.

We have

$$L_X = (\{v_1, v_2, v_3\}^3, \{v_1, v_2\}^3, \{v_1, v_3\}^6)$$

and

$$L_X^* = (\{v_1, v_2, v_3\}, \{v_1, v_2\}^2, \{v_1, v_3\}, \{v_2, v_3\}^2, \{v_2\}^4, \{v_3\}^2).$$

According to our combinatorial interpretation, the basis $\{v_1, v_2\}$ gives the summand $x^2 + 3x + 2$ (here the matching is trivial, since we don't have external activity), while the basis $\{v_1, v_3\}$ gives the summand $xy + 2y + 2x + 4 = (x + 2)(y + 2)$.

**Remark 6.4** This computation reveals a general pattern: the summand corresponding to a basis is always a product of a polynomial in $x$ times a polynomial in $y$. This is the actual meaning of the equidistributivity.

Their sum gives $x^2 + 5x + 6 + xy + 2y = M_X(x, y)$, as predicted.

The key of the proof of Theorem 6.1 is to show that the right hand side of the equality satisfies the recursions stated in Theorem 4.4 for the left hand side.

## Acknowledgements

We are deeply grateful to Petter Brändén for having pointed out a mistake in an earlier choice of the axioms in Section 2.3, and for having suggested how to fix it. We are very grateful to Emanuele Delucchi for several stimulating and insightful discussions. We would also like to thank Anders Björner, Corrado De Concini, Alicia Dickenstein, Michael Falk, Matthias Lenz, Alex Postnikov and Frank Sottile for many interesting conversations and valuable suggestions.

## References

[1] F. ARDILA, A. POSTNIKOV, *Combinatorics and geometry of power ideals*, Trans. Amer. Math. Soc., to appear.

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

[3] M. D'ADDERIO, L. MOCI, *Ehrhart polynomial of the zonotope and multiplicity Tutte polynomial*, arXiv:1102.0135, to appear in European Journal of Combinatorics.

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

[5] M. D'ADDERIO, L. MOCI, *Graph colorings, flows and arithmetic Tutte polynomial*, arXiv:1108.5537.
[6] W. DAHMEN AND C. A. MICCHELLI, *On the solution of certain systems of partial difference equations and linear dependence of translates of box splines.*, Trans. Amer. Math.Soc., 292(1): 305-320, 1985.

[7] W. DAHMEN AND C. A. MICCHELLI, *The number of solutions to linear Diophantine equations and multivariate splines*, Trans. Amer. Math. Soc., 308(2): 509-532, 1988.

[8] C. DE CONCINI, C. PROCESI, *Topics in hyperplane arrangements, polytopes and box-splines*, Universitytext, Springer-Verlag, New-York (2010), XXII+381 pp.

[9] C. DE CONCINI, C. PROCESI, M. VERGNE, *Vector partition functions and index of transversally elliptic operators*, arXiv: math 0808.2545

[10] D. GALE, *Neighboring vertices on a convex polyhedron*, Annals of Math. Studies 38, 255-263, Princeton Univ. Press, 1956.

[11] O. HOLTZ, A. RON, *Zonotopal Algebra*, arXiv:0708.2632v2, Advances in Mathematics, 227 (2011), no.2, 847-894.

[12] O. HOLTZ, A. RON, ZHIQIANG XU, *Hierarchical zonotopal spaces*, arXiv:0910.5543v2, to appear in Trans. Amer. Math. Soc.

[13] L. MOCI, *A Tutte polynomial for toric arrangements*, arXiv:0911.4823v4 [math.CO], Trans. Amer. Math. Soc. 364 (2012), 1067-1088.

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

[15] J. G. OXLEY, *Matroid Theory*, Oxford University Press, Oxford 1992.

[16] R. P. STANLEY, *A zonotope associated with graphical degree sequences*, in Applied Geometry and Discrete Combinatorics, DIMACS Series in Discrete Mathematics, vol. 4, 1991, pp. 555-570.

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