%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2018}
\articlenumber{94}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{example}[theorem]{Example}

\usepackage{lipsum}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{epstopdf}
\usepackage{color}
\usepackage{url}
\usepackage{verbatim}
\usepackage[lined,algonl,boxed,norelsize]{algorithm2e}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}

\DeclareRobustCommand{\rchi}{{\mathpalette\irchi\relax}}
\newcommand{\irchi}[2]{\raisebox{\depth}{$#1\chi$}}


\def\M{\mathcal{M}}
\def\B{\mathcal{B}}
\def\O{\mathcal{O}}
\def\J{\mathcal{J}}
\def\P{\mathcal{P}}
\def\I{\mathcal{I}}
\def\Jac{\rm Jac}
\newcommand{\Ofrak}{{\mathfrak O}}

\renewcommand{\AA}{\mathbb{A}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}

%% define your title in the usual way
\title{Geometric bijections for regular matroids, zonotopes, and Ehrhart theory}
%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Spencer Backman\thanks{\href{mailto:spencer.backman@mail.huji.ac.il}{spencer.backman@mail.huji.ac.il}}\addressmark{1},
Matthew
Baker\thanks{\href{mailto:mbaker@math.gatech.edu}{mbaker@math.gatech.edu}}\addressmark{2},
and Chi Ho Yuen\thanks{\href{mailto:chi.yuen@math.unibe.ch}{chi.yuen@math.unibe.ch}}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Einstein Institute of Mathematics, Hebrew University of Jerusalem \\ \addressmark{2}School of Mathematics, Georgia Institute of Technology \\ \addressmark{3}Department of Mathematics and Statistics, University of Bern}

%% put the date of submission here
\received{November 14th, 2017}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{Let $M$ be a {\em regular matroid}.  The {\em Jacobian group} ${\rm Jac}(M)$ of $M$ 
is a finite abelian group whose cardinality is equal to the number of {\em bases} of $M$. This group
generalizes the definition of the Jacobian group (also known as the critical group or sandpile group) ${\rm Jac}(G)$ of a graph $G$ (in which case bases of the corresponding regular matroid are spanning trees of $G$).  

There are many explicit combinatorial bijections in the literature between the Jacobian group of a graph ${\rm Jac}(G)$ and spanning trees.  However, most of the known bijections use {\em vertices} of $G$ in some essential way and are inherently ``non-matroidal''. In this work, we construct a family of explicit and easy-to-describe bijections between the Jacobian group of a regular matroid $M$ and bases of $M$, many instances of which are new even in the case of graphs. We first describe our family of bijections in a purely combinatorial way in terms of orientations; more specifically, we prove that the Jacobian group of $M$ admits a canonical simply transitive action on the set ${\mathcal G}(M)$ of circuit-cocircuit reversal classes of $M$, and then define a family of combinatorial bijections $\beta_{\sigma,\sigma^*}$ between ${\mathcal G}(M)$ and bases of $M$.  (Here $\sigma$ (resp $\sigma^*$) is an {\em acyclic signature} of the set of circuits (resp. cocircuits) of $M$.)
We then give a geometric interpretation of each such map $\beta=\beta_{\sigma,\sigma^*}$ in terms of zonotopal subdivisions which is used to verify that $\beta$ is indeed a bijection. 



Finally, we give a combinatorial interpretation of lattice points in the zonotope $Z$; by passing to dilations we obtain
a new derivation of Stanley's formula linking the Ehrhart polynomial of $Z$ to the Tutte polynomial of $M$. }

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{chip-firing, Ehrhart theory, Jacobian, regular matroid, zonotope. }

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{94-Backman-Baker-Yuen.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Overview of results}

\subsection{The main bijection in the case of graphs}

Let $G$ be a connected finite graph.
The {\em Jacobian group} ${\rm Jac}(G)$ of $G$ (also called the sandpile group, critical group, etc.) is a finite abelian group canonically associated to $G$ whose cardinality equals the number of spanning trees of $G$. Although there is no canonical bijection\footnote{Consider, for example, a 3-cycle: since ${\rm Aut}(G)$ acts transitively on the set of spanning trees, there can be no distinguished member of this 3-element set corresponding to the identity element of $\Jac(G)$.} between $\Jac(G)$ and the set ${\mathcal T}(G)$ of spanning trees of $G$, many constructions of combinatorial bijections starting with some fixed additional data are known.  We mention, for example: the Cori--Le Borgne bijections that use an ordering of the edges as well as a fixed vertex \cite{cori2001burning}, Perkinson, Yang and Yu's bijections that use an ordering of the vertices \cite{perkinson2015dfs}, and Bernardi's bijections that use a cyclic ordering of the edges incident to each vertex \cite{bernardi2008tutte}.

In this work we describe a new family of combinatorial bijections between $\Jac(G)$ and ${\mathcal T}(G)$.  Our bijections are very simple to state, though proving that they are indeed bijections is not so simple.  Another feature is that our bijections are formulated in a ``purely matroidal'' way, and in particular they generalize from graphs to {\em regular matroids}.  We will first state the main result of this paper in the language of graphs, and then give the generalization to regular matroids.

What we will in fact do is establish a family of bijections between ${\mathcal T}(G)$ and the set ${\mathcal G}(G)$ of {\em cycle-cocycle equivalence classes} of orientations of $G$.  The latter was introduced by Gioan \cite{gioan2007enumerating,gioan2008circuit} and is known to be a torsor\footnote{This means that there is a canonical simply transitive group action of $\Jac(G)$ on ${\mathcal G}(G)$.} for $\Jac(G)$ in a canonical way. By fixing a class in ${\mathcal G}(G)$ to correspond to the identity element of $\Jac(G)$, we then obtain a bijection between $\Jac(G)$ and ${\mathcal T}(G)$. (By definition, ${\mathcal G}(G)$ is the set of equivalence classes of orientations of $G$ with respect to the equivalence relation generated by directed cycle reversals and directed cut reversals. We will write $[{\mathcal O}]$ to denote the equivalence class containing an orientation ${\mathcal O}$.)

To state our main bijection for graphs, let ${\mathcal C}(G)$ (resp. ${\mathcal C}^*(G)$) denote the set of simple cycles (resp. simple cuts, i.e., bonds) of $G$, and define a {\bf cycle signature} (resp. {\bf cut signature}) on $G$ to be a choice, for each $C \in {\mathcal C}(G)$ (resp. $C \in {\mathcal C}^*(G)$), of an orientation of $C$, identified with an element of the cycle lattice $\Lambda(G)$ (resp. the cut lattice $\Lambda^*(G)$). We call a cycle signature $\sigma$ (resp. cut signature $\sigma^*$) {\bf acyclic} if whenever $a_C$ are nonnegative reals with
\[
\sum_{C \in {\mathcal C}(G)} a_C \sigma(C) = 0
\]
in $\Lambda(G)$ 
(resp. $\sum_{C \in {\mathcal C}^*(G)} a_C \sigma^*(C) = 0$ in $\Lambda^*(G)$) we have $a_C = 0$ for all $C$.

\begin{example} \label{ex:smallestedge}
Fix a total order and reference orientation on the set $E(G)$ of edges of $G$, and orient each simple cycle (resp. simple cut) $C$ compatibly with the reference orientation of the smallest edge in $C$.  This gives an acyclic signature of ${\mathcal C}(G)$ (resp. ${\mathcal C}(G)$).

\end{example}



Recall that if $T$ is a spanning tree of $G$ and $e \not\in T$ (resp. $e \in T$), there is a unique simple cycle  $C(T,e)$ (resp. simple cut $C^*(T,e)$) contained in $T \cup \{ e \}$ (resp. containing $T \backslash \{ e \}$), called the {\em fundamental cycle} (resp. {\em fundamental cut}) associated to $T$ and $e$. With this notation in place, we can now state our main bijection in the case of graphs:

\begin{theorem} \label{thm:mainbijectionforgraphs}
Let $G$ be a connected finite graph, and fix acyclic signatures $\sigma$ and $\sigma^*$ of ${\mathcal C}(G)$ and ${\mathcal C}^*(G)$, respectively. Given a spanning tree $T \in {\mathcal T}(G)$, let ${\mathcal O}(T)$ be the orientation of $G$ in which we orient each $e \not\in T$ according to its orientation in $\sigma(C(T,e))$ and each $e \in T$ according to its orientation in $\sigma^*(C^*(T,e))$. Then the map $T \mapsto [{\mathcal O}(T)]$ is a bijection between ${\mathcal T}(G)$ and ${\mathcal G}(G)$.
\end{theorem}

The bijection in Theorem~\ref{thm:mainbijectionforgraphs} appears to be new even in the special case where $\sigma$ and $\sigma^*$ are defined as in Example~\ref{ex:smallestedge} As we now explain, by specializing our choice of $\sigma$ and $\sigma^*$, we can recover some previously known bijections.


Let $G$ be a graph, and fix a vertex $q$ of $G$. In \cite{an2014canonical}, the authors prove that the break divisors of $G$ are the divisors associated to $q$-connected orientations offset by a chip at $q$. In other words (in the notation of \cite[Lemma 3.3]{an2014canonical}), a divisor $D$ is a break divisor if and only if $D = (q) + \nu_{\mathcal O}$ for some $q$-connected orientation $\mathcal O$.   They also show that break divisors of the corresponding metric graph $\Gamma$ induce a canonical subdivision of the $g$-dimensional torus $Pic^g(\Gamma)$ into parallelepiped indexed by spanning trees of $G$, with the vertices of the subdivision corresponding to the break divisors of $G$. By applying a small generic shift to the vertices, this yields a family of ``geometric bijections'' between break divisors and spanning trees (cf.~\cite[Remark 4.26]{an2014canonical}).

We claim that the geometric bijections defined in \cite{an2014canonical} can be thought of as special cases of the bijections afforded by Theorem~\ref{thm:mainbijectionforgraphs}.  To see this,
note first that by \cite[Theorem 10]{yuen2017geometric}, each geometric bijection gives rise in a natural way to an acyclic orientation $\sigma$ of the cycles of $G$.  To orient the cocycles of $G$, we fix a spanning tree $T_0$ of $G$.  Orient the edges of $T_0$ away from $q$ and label them $e_1$ through $e_{n-1}$ in a way such that every edge has a larger label than its ancestors.  Extend this data on $T_0$ arbitrarily to a total order and reference orientation of $E(G)$.  Let $\sigma^*$ be the corresponding acyclic orientation of the set of cocircuits of $G$ given by Example~\ref{ex:smallestedge}.  
Given a spanning tree $T$, the orientation $\O_T$ associated to the pair $(\sigma,\sigma^*)$ by Theorem~\ref{thm:mainbijectionforgraphs} will have the property that every edge $e$ in $T$ (considered as a tree rooted at $q$) is oriented away from $q$, and therefore $\O_T$ is $q$-connected \cite[Section 3]{backman2014partial}.  Let $D_T = \nu_{\O_T} + (q)$ be the corresponding break divisor.
Then $T \mapsto D_T$ will be the geometric bijection we started with.



For another application of Theorem~\ref{thm:mainbijectionforgraphs}, suppose that $G$ is a plane graph and define $\sigma$ by orienting each simple cycle of $G$ counterclockwise.  Similarly, define $\sigma^*$ by orienting each simple cycle of the dual graph $G^*$ clockwise and composing with the natural bijection between oriented cuts of $G$ and oriented cycles of $G^*$.
In this case, the simply transitive action of $\Jac(G)$ on ${\mathcal T}(G)$ afforded by Theorem~\ref{thm:mainbijectionforgraphs} coincides with the ``Bernardi torsor'' defined in \cite{baker2017bernardi} and {\em a posteriori} with the ``rotor-routing torsor'' defined in \cite{chan2015rotor,chan2015duality}.  In particular, we get a new ``geometric'' proof of the bijectivity of the Bernardi map. 
 
\subsection{Generalization to regular matroids} \label{sec:introregular}

As mentioned previously, an interesting feature of the bijection given by Theorem~\ref{thm:mainbijectionforgraphs} is that it admits a direct generalization to {\em regular matroids}.

Regular matroids are a particularly well-behaved and widely studied class of matroids which contain graphic (and co-graphic) matroids as a special case. More precisely, a regular matroid can be thought of as an equivalence class of totally unimodular integer matrices\footnote{An $r \times m$ integer matrix $A$ with $r \leq m$ is called {\em totally unimodular} if every $k \times k$ submatrix has determinant in $\{ 0, \pm 1 \}$ for all $1 \leq k \leq r$. We say that totally unimodular $r \times m$ matrices $A,A'$ are {\em equivalent} if one can transform $A$ into $A'$ by multiplying on the left by an $r \times r$ unimodular matrix $U$, then permuting columns or multiplying columns by $-1$.}.  

If $G$ is a graph, one can associate a regular matroid $M(G)$ to $G$ by letting $A$ be the modified adjacency matrix of $G$, where we choose a vertex $q \in V(G)$ and the rows of $A$ are indexed by $V(G) \backslash \{ q \}$.
By a theorem of Whitney, the equivalence class of $A$ determines the graph $G$ up to ``2-isomorphism'' (and in particular determines $G$ up to isomorphism if $G$ is assumed to be $3$-connected).

Let $M$ be a regular matroid.  In Section 4.3 of his Ph.D. thesis, Criel Merino defined the {\em critical group} (which we will call the {\em Jacobian}) ${\rm Jac}(M)$ of $M$, generalizing the critical group of a graph.  The group ${\rm Jac}(M)$ is a finite abelian group whose cardinality is equal to the number of {\em bases} of $M$.\footnote{The fact that these cardinalities are equal is essentially a translation of the natural extension of Kirchhoff's Matrix-Tree theorem to regular matroids \cite{maurer1976matrix}, \cite[Theorem 4.3.2]{merino1999matroids}. A ``volume proof'' of the Matrix-Tree theorem for regular matroids based on zonotopal subdivisions is given in \cite{dall2014polyhedral}.  These authors do not consider the problem of giving explicit combinatorial bijections between bases of $M$ and the Jacobian group.}


One can also define the set ${\mathcal C}(M)$ of {\em signed circuits} of $M$ (resp. the set ${\mathcal C}^*(M)$ of {\em signed cocircuits} of $M$) in a way which generalizes the corresponding objects when $M=M(G)$.  Similarly, one has a set $B(M)$ of {\bf bases} of $M$, generalizing the notion of spanning tree for graphs, and a set ${\mathcal G}(M)$ of cycle-cocycle equivalence classes generalizing the corresponding set for graphs. By results of Merino and Gioan, the cardinalities of $\Jac(M)$, $B(M)$, and ${\mathcal G}(M)$ all coincide. (Our results in this paper give independent proofs of these facts.)

Generalizing the known case of graphs \cite{backman2014riemann}, we prove:

\begin{theorem} \label{thm:torsortheorem}
${\mathcal G}(M)$ is canonically a torsor for $\Jac(M)$.
\end{theorem}


In view of this result, in order to construct a bijection between elements of $\Jac(M)$ and bases of $M$, it suffices to give a bijection between $B(M)$ and ${\mathcal G}(M)$.
One can generalize the notion of acyclic signature and fundamental cycles (resp. cuts) in a straightforward way from graphs to regular matroids. 
Theorem~\ref{thm:mainbijectionforgraphs} then admits the following generalization to regular matroids:


\begin{theorem} \label{thm:mainbijectionforregularmatroids}
Let $M$ be a regular matroid, and fix acyclic signatures $\sigma$ and $\sigma^*$ of ${\mathcal C}(M)$ and ${\mathcal C}^*(M)$, respectively. Given a basis $B \in B(M)$, let ${\mathcal O}(B)$ be the orientation of $M$ in which we orient each $e \not\in B$ according to its orientation in $\sigma(C(B,e))$ and each $e \in B$ according to its orientation in $\sigma^*(C^*(B,e))$. Then the map $B \mapsto [{\mathcal O}(B)]$ gives a bijection $\beta : B(M) \to {\mathcal G}(M)$. 
\end{theorem}



\medskip

Most known combinatorial bijections between elements of ${\rm Jac}(G)$ and spanning trees of a graph $G$ do not readily extend to the case of regular matroids, as they use vertices of the graph in an essential way.
The only other work we are aware of giving explicit bijections between elements of $\Jac(M)$ and bases of a regular matroid $M$ are the papers of Gioan and Gioan--Las Vergnas \cite{gioan2002correspond,gioan2005activity}\footnote{ Technically speaking, Gioan and Las Vergnas do not produce a bijection between bases and elements of $\Jac(M)$; they produce a bijection between $B(M)$ and $\mathcal{X}(M;\sigma,\sigma^*)$ (see Definition \ref{sigma-compatible}), where $(\sigma,\sigma^*)$ are determined by a total order on the edges and a reference orientation.} and the as-yet unpublished recent work of Shokrieh \cite{farbod2016draft}. Our family of combinatorial bijections appears to be quite different from those of Gioan--Las Vergnas. 



\subsection{Brief overview of the proof of the main combinatorial bijections}

Although the statement of Theorem~\ref{thm:mainbijectionforgraphs} and its generalization Theorem~\ref{thm:mainbijectionforregularmatroids} to regular matroids $M$ are completely combinatorial, we do not know any simple combinatorial proof.  Our proof involves the geometry of a zonotopal subdivision associated to a matrix $A$ representing $M$.



Concretely, fix a totally unimodular $r \times m$ matrix $A$ representing $M$, where $r$ is the rank of $A$. Denote by $V^* \subseteq \RR^E$ the row space of $A$ and by $\pi_{V^*}$ the orthogonal projection from $\RR^E$ to $V^*$. Let $u_e \in \RR^E$ be the standard coordinate vector corresponding to $e \in E$.  The {\em column zonotope} $Z_A \subset \RR^r$ (resp. {\em row zonotope} $\widetilde{Z_A} \subset \RR^E$) associated to $A$ is defined to be the Minkowski sum of the columns of $A$ (resp. the Minkowski sum of the vectors $\pi_{V^*}(u_e)$ for $e \in E$).
One checks easily that the linear transformation $L : v \mapsto Av$ gives an isomorphism from $V^*$ to $\RR^r$ taking $\widetilde{Z_A}$ to $Z_A$.
In particular, the $r$-dimensional zonotopes $\widetilde{Z_A}$ and $Z_A$ are isomorphic via a unimodular transformation.


An {\em orientation} $\O$ of $M$ is a function $E \to \{ -1, 1 \}$.
An orientation $\O$ is {\em compatible} with a signed circuit $C$ of $M$ if $\O(e) = C(e)$ for all $e$ in the support of $C$. If $\O$ is an orientation and $C$ is a signed circuit compatible with $\O$, we can perform a {\em circuit reversal} taking $\O$ to the orientation $\O'$ 
defined by $\O'(e) = \O(e)$ if $e$ is not in the support of $C$ and $\O'(e) = -\O(e)$ if $e$ is in the support of $C$.  Let $\sigma$ be an acyclic signature of ${\mathcal C}(M)$.
We say that $\O$ is {\em $\sigma$-compatible} if every signed circuit $C$ of $M$ compatible with $\O$ is oriented according to $\sigma$.

\begin{theorem}
Every circuit-reversal equivalence class of orientations contains a unique $\sigma$-compatible orientation.
\end{theorem}

The connection between $\sigma$-compatible orientations and the zonotopes defined above is given by the following result.
For the statement, given an orientation $\O$ of $M$ and $e \in E$, define $w_e \in \RR^r$ to be $0$ if $\O(e) = -1$ and 
to be the $e^{\rm th}$ column of $A$ if $\O(e) = 1$.
Define $\psi(\O) \in Z_A$ by

\begin{equation}
\psi(\O) := \sum_{e \in E} w_e \in Z_A.
\end{equation}

\begin{theorem}
The map $\psi$ induces a bijection between circuit-reversal classes of orientations of $M$ and lattice points of the zonotope $Z_A$.
\end{theorem}

Fix a reference orientation $\O_0$ of $M$.
Each acyclic signature $\sigma$ of ${\mathcal C}(M)$ gives rise to a subdivision of $Z_A$ into smaller zonotopes $Z(B)$, one for each basis $B$ of $M$,
in the following way.  Let $B$ be a basis of $M$.  For each $e \not\in B$, define $v_e \in V^*$ to be $0$ if the reference orientation of $e$ coincides with the orientation of $e$
in $\sigma(C(B,e))$, and to be the $e^{\rm th}$ column of $A$ otherwise.
Define 
\[
Z(B) := \sum_{e \in B} [0,A_e] + \sum_{e \not\in B} v_e \subseteq Z_A \subset \RR^r.
\]

Note that $Z(B)$ is itself a zonotope, as it is congruent via translation to $\sum_{e \in B} [0,A_e]$.
Let $\widetilde{Z(B)}$ be the corresponding subset $L^{-1}(Z(B))$ of $\widetilde{Z_A}$.
The following result can be paraphrased as saying that the various $Z(B)$'s give a {\em zonotopal subdivision}\footnote{Also known in the literature on zonotopes as a {\em fine tiling} of $Z_A$.} $\Sigma$ of $Z_A$.

\begin{theorem} 
The union of $Z(B)$ over all bases $B$ of $M$ is equal to $Z_A$, and if $B,B'$ are distinct bases then the intersection of $Z(B)$ and $Z(B')$ is a (possibly empty) face of each.
\end{theorem}

%Similarly, via the map $L$, the various $\widetilde{Z(B)}$'s give a zonotopal subdivision $\widetilde{\Sigma}$ of $\widetilde{Z_A}$.

\begin{definition}\label{sigma-compatible}
We now explain briefly how these results are used to prove Theorem~\ref{thm:mainbijectionforregularmatroids}.  Let $\sigma,\sigma^*$ be acyclic signatures of $C(M)$ and $C^*(M)$, respectively. An orientation is called {\em $(\sigma,\sigma^*)$-compatible} if it is both $\sigma$-compatible and $\sigma^*$-compatible, and we denote the set of such orientations by $\mathcal{X}(M;\sigma,\sigma^*)$.
\end{definition}

 \begin{theorem} \label{thm:SScompatibleorientation}
Let $\hat{\beta}$ be the map which sends a basis $B$ to the orientation $\mathcal{O}_B$ defined in Theorem~\ref{thm:mainbijectionforregularmatroids}. Let $\chi$ be the map which sends an orientation $\mathcal{O}$ to its circuit-cocircuit reversal class $[\mathcal{O}]$, so that  
 $\beta=\chi\circ\hat{\beta}$. 
 
\begin{enumerate}

\item The image of $\hat{\beta}$ is contained in $\mathcal{X}(M;\sigma,\sigma^*)$, and $\hat{\beta}$ gives a bijection between $B(M)$ and $\mathcal{X}(M;\sigma,\sigma^*)$.

\item The map $\chi$ restricted to $\mathcal{X}(M;\sigma,\sigma^*)$ induces a bijection between $\mathcal{X}(M;\sigma,\sigma^*)$ and $\mathcal{G}(M)$. 

\end{enumerate}
\end{theorem}


\begin{remark}
The proofs of Theorem~\ref{thm:torsortheorem} and Theorem~\ref{thm:mainbijectionforregularmatroids} do not assume {\em a priori} that  $|B(M)|=|\mathcal{X}(M;\sigma,\sigma^*)|=|\mathcal{G}(M)|=|{\rm Jac}(M)|$ for a regular matroid, thus our work provides an independent proof of these equalities. Furthermore, we will shows that $|B(M)|=|\mathcal{X}(M;\sigma,\sigma^*)|$ for any matroid representable over $\mathbb{R}$, which is Theorem~\ref{thm:realizablemainthm} below.

\end{remark}

\medskip


Choose a vector $w \in {\mathbb R}^E$ which is compatible with $\sigma^*$, in the sense that $w \cdot \sigma^*(C) > 0$ for each cocircuit $C$ of $M$.
(The existence of such a vector is guaranteed by a simple application of the Farkas Lemma.) 
Since oriented circuits are orthogonal to oriented cocircuits, and the row space $V^*$ of $A$ is the span of the oriented cocircuits, 
modifying $w$ by an element of $(V^*)^\perp$ will give the same inner product $w \cdot \sigma^*(C)$ for each circuit $C$ of $M$.
Therefore it is natural to consider the orthogonal projection $w'$ of $w$ onto $V^*$.  Note that the zonotopal subdivision $\widetilde{\Sigma}$ of $\widetilde{Z_A}$ depends only on $\sigma$ (and the reference orientation $\O_0$) and the vector $w'$ depends only on $\sigma^*$.

The following theorem shows that the combinatorially defined map $\hat{\beta} : {\mathcal B}(M) \to {\mathcal X}(M)$ can be interpreted geometrically as first identifying a basis with a maximal cell in our zonotopal subdivision and then applying a ``shifting map''.


\medskip


\begin{theorem} \label{thm:betaphiagree}
\begin{enumerate}
\item Let $B$ be a basis of $M$. For all sufficiently small $\epsilon > 0$ the image of $\widetilde{Z(B)}$ under the map $v \mapsto v + \epsilon w'$ contains a unique lattice point $\widetilde{z_B}$ of $\widetilde{Z_A}$, which corresponds to a unique $\sigma$-compatible discrete orientation $\mathcal{O}'_B$.
\item The map $\phi$ which takes each basis $B$ to the orientation $\mathcal{O}'_B$ coincides with the map $\hat{\beta}$ appearing in the statement of Theorem~\ref{thm:mainbijectionforregularmatroids}; and $\phi$ (hence $\hat{\beta})$ is a bijection between $B(M)$ and $\mathcal{X}(M;\sigma,\sigma^*)$.
\end{enumerate}
\end{theorem}

\begin{figure}
\centering
\includegraphics[width=0.8\textwidth]{zonotopeK3_7.pdf}
\caption{An illustration of Theorem \ref{thm:betaphiagree} for $K_3$.}
\label{fig:plot}
\end{figure}


See Figure \ref{fig:plot} for an example of this shifting map.  Theorem~\ref{thm:mainbijectionforregularmatroids} is a simple consequence of Theorem \ref{thm:SScompatibleorientation} and Theorem \ref{thm:betaphiagree}. 

\subsection{Continuous orientations}
It is useful to give a combinatorial interpretation of {\em all} points of the zonotope $Z_A$ (not just the lattice points) in terms of equivalence classes of {\em continuous orientations} of $M$.  Recall that an orientation is a function $E \to \{ -1, 1 \}$.
We define a {\em continuous orientation} of $M$ to be a function $E \to [-1,1]$;

If we fix an acyclic signature $\sigma$ of $C(M)$, there is a natural way (generalizing the discrete case) to pick out a distinguished {\em $\sigma$-compatible} orientation from each continuous circuit-reversal class.  We will show:

\begin{theorem} 
There is a natural bijection between circuit-reversal classes of continuous orientations of $M$ and points of the zonotope $Z_A$.  
\end{theorem}

We use this result to give an alternate description of the zonotopal subdivisions $\Sigma$ and $\widetilde{\Sigma}$ of $Z_A$ and $\widetilde{Z_A}$, respectively, which were defined above.

\subsection{A Partial Extension to Oriented Matroids over $\mathbb{R}$} \label{sec:realizablecase}

The equality $|B(M)|=|\mathcal{G}(M)|=|\Jac(M)|$ is not true for general oriented matroids (indeed, $\Jac(M)$ is not even well-defined in the general case). Nevertheless, the notions of acyclic circuit/cocircuit signatures and $(\sigma,\sigma^*)$-compatible orientations are still valid for an oriented matroid over $\mathbb{R}$. Furthermore, the geometric setup used to prove Theorem~\ref{thm:betaphiagree} as well as the first half of Theorem~\ref{thm:SScompatibleorientation} does not require $M$ to be regular but only realizable over $\mathbb{R}$. Therefore we have the following bijectivity result.

\begin{theorem} \label{thm:realizablemainthm}
Let $M$ be a oriented matroid over $\mathbb{R}$ and let $\sigma,\sigma^*$ be acyclic signatures of $C(M),C^*(M)$, respectively. Then the map $\hat{\beta}:B(M)\rightarrow\mathcal{X}(M;\sigma,\sigma^*)$ is a bijection.
\end{theorem}

\subsection{Random sampling of bases} 

As in \cite{baker2013chip}, any computable bijection between bases and elements of $\Jac(M)$ gives rise to an algorithm for randomly sampling bases of $M$. The idea is simple: by computing the Smith Normal Form of a matrix $A$ representing $M$, we can explicitly compute $\Jac(M)$ as a direct sum of finite abelian groups, and it is clear how to uniformly sample elements of such a group.

In order to make this into a practical method, one needs efficient algorithms for computing both the element of $\Jac(M)$ associated to a given basis and vice-versa.  We provide polynomial-time computable algorithms for these tasks with respect to the family of bijections given by Theorem~\ref{thm:mainbijectionforregularmatroids}.
Both our algorithm for computing the inverse of the map $\beta$ (resp. $\hat{\beta}$) from Theorem~\ref{thm:mainbijectionforregularmatroids} and our algorithm for computing the group action use ideas from linear programming.  

%We also present a simple recursive procedure based on deletion and contraction for randomly sampling bases in a regular matroid which does not make use of Theorem~\ref{thm:mainbijectionforregularmatroids}.  This algorithm was inspired by a similar folklore result in the case of graphs \cite{kalaiblog}.

\subsection{Connections to Ehrhart theory and the Tutte polynomial}

Every matroid $M$ of rank $r$ has an associated {\em Tutte polynomial} $T_M(x,y)$, and every lattice polytope $P$ (e.g. the zonotope $Z_A$) has an associated {\em Ehrhart polynomial} $E_P(q)$ which counts the number of lattice points in positive integer dilates of $P$.  Using the relationship between $Z_A$ and $\sigma$-compatible (discrete or continuous) orientations of $M$ (see Figure \ref{fig:plot2}), we obtain a new proof of the following identity originally due to Stanley:

\begin{equation} \label{eq:stanley}
E_Z(q) = q^r T_{M}(1 + 1/q,1).
\end{equation}

The proof involves defining a ``dilation'' $qM$ of $M$ for each positive integer $q$, with associated zonotope $qZ_A$.   We also describe a direct bijective proof (without appealing to Ehrhart reciprocity) of the fact that the number of interior lattice points in $qZ_A$ is 
\[
q^r T_{M}(1-1/q,1).
\]

%for an illustration of our identification of lattice points in the second dilate of $Z_A$ with the $\sigma$-compatible discrete orientations of $M$.
 
 \begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{zonotopeK3_5!.pdf}
\caption{An identification of the lattice points in $2Z_A $ with $\sigma$-compatible orientations of $2K_3$.}
\label{fig:plot2}
\end{figure}



\subsection{Related literature}

The study of zonotopal tilings, i.e. tilings of a zonotope by smaller zonotopes, is a classical topic in the theory of oriented matroids first initiated by Shepard \cite{shephard1974zonotopes}.   The central theorem in this area is the Bohne--Dress Theorem \cite{bohne1992zonotopaler,dress1989oriented}, which states that the poset of zonotopal tilings ordered by refinement is isomorphic to the poset of 1-element lifts of the associated oriented matroid M.  It should be possible to use the Bohne--Dress Theorem and the results in \cite{bayer1997discriminantal} to prove that the set of tilings of $Z_A$ arising from acyclic orientations of $C(M)$ is precisely the set of regular tilings of $Z_A$ (which correspond to the realizable lifts in the Bohne--Dress Theorem).  It should also be possible to use the results of \cite{birkett2000cayley} to give a more high-level explanation, in terms of Lawrence polytopes, Lawrence ideals, and Gr{\"o}bner bases, of the relationship between continuous and discrete $\sigma$-compatible orientations.  Farbod Shokrieh has indicated to us that his forthcoming paper \cite{farbod2016draft} may shed some light on these connections.
%\lipsum[3]

%\begin{equation}\label{eqn:eq1}
%\int_0^\infty \exp(-x)dx = 1.
%\end{equation}

%\begin{lem}\label{lem:lem1}
%\lipsum[11]
%\end{lem}

%\lipsum[10]

%\begin{figure}
%\centering
%\includegraphics[width=0.5\textwidth]{plot}
%\caption{A plot of a function.}
%\label{fig:plot}
%\end{figure}

%\subsection{A subsection}

%\lipsum[5]

%\begin{align*}
%1 + 1 + 1 &= 2 + 1 \\ &= 3.
%\end{align*}

%\subsubsection{A subsubsection}

%\lipsum[17]

%Here is a citation~\cite{greenwade93} with URL. Here is another citation~\cite{MR4}, which is the earliest-numbered Math Review with a
%functioning DOI: MR0000004. Finally, a reference to
%equation~\eqref{eqn:eq1}. And a reference to Figure~\ref{fig:plot}.

\acknowledgements{The first author thanks Sam Hopkins for introducing him to the connection between zonotopes and Tutte polynomial evaluations, and Raman Sanyal for explaining that regular tilings of a zonotope can alternately be viewed as dual to generic perturbations of the associated hyperplane arrangement. 
The second author's work was partially supported by the NSF research grant DMS-1529573. The third author thanks Yin Tat Lee for the discussion on linear programming.
}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
