We strive to present two remarkable discoveries in discrete geometry: the formulas established by Michel Brion [1], James Lawrence [2], and Alexander N. Varchenko [3]. Initially, these formulas may appear incredulous, and even after dedicating considerable time to studying them, they continue to evoke a sense of intrigue and fascination.

Brion Formula

Let us start with some examples. Let us consider the task of enumerating all positive integers. Despite their infinite nature, we can represent them succinctly using a generating function:

\begin{equation} x^{1} + x^{2} + x^{3} + … = \sum_{k>0}x^{k}= \dfrac{x}{1-x} \end{equation}

Similarly, all the integers less than or equal to \(5\), \begin{equation} …+x^{-1} + x^{0} + x^{1} + x^{2} + … = \sum_{k≤ k}x^{k}= \dfrac{x^{5}}{1-x^{-1}}. \end{equation}

Adding the rational functions leads to a miraculous cancellation,

\begin{equation} \dfrac{x}{1-x} + \dfrac{x^{5}}{1-x^{-1}} = \dfrac{x}{1-x} + \dfrac{x^{6}}{x-1} = \dfrac{x - x^{6}}{1-x} = x + x^{2} + x^{3} + x^{4} +x^{5}. \end{equation}

The sum of rational functions, which captures the essence of two infinite series, remarkably simplifies into a polynomial expression, representing a finite series. This fascinating phenomenon can be seen as a special case of a theorem formulated by Michel Brion for the one dimensional case. In a certain sense, the sum of these generating functions acts as the intersection of sets.

If we focus on the two-dimensional scenario, the equivalence of the generating functions from before can be found in the generating functions associated with the cones formed at each vertex generated by the edges at that vertex. Once more, the sum of rational functions simplifies to a polynomial, capturing exactly the integer points that lie within the quadrilateral.

Brion’s theorem says that this magic happens for any polytope \(\mathcal{P}\) in any dimension \(d\), provided that \(\mathcal{P}\) has rational vertices. Let be \(\mathcal{K_v}\) denote the vertex cone at vertex \(v\), that is the cone with apex \(v\) and generators the edge directions emanating from \(v\). The generating function will be,

\begin{equation} \sigma_{\mathcal{K_v}}(x) = \sum_{m\in \mathcal{K_v}\cap \mathbb{Z}^{d}}x^{m}. \end{equation}

The generating function for such a cone is a rational function. According to Brion’s Formula, the rational functions that correspond to the integer points within each vertex cone combine together to yield the polynomial \(\sigma_{\mathcal{P}}(x)\), which encapsulates the information about the integer points in the polytope \(\mathcal{P}\), \begin{equation} \sigma_{\mathcal{P}}(x) = \sum_{v\in \mathcal{P}} \sigma_{\mathcal{K_v}}(x). \end{equation}

James Lawrence and to Alexander Varchenko Formula

Another theorem, independently discovered by James Lawrence and Alexander Varchenko, demonstrates a similar collapsing behavior of generating functions associated with cones. Lawrence–Varchenko procedure is the following. First, we choose a direction vector \(\epsilon\) that is not perpendicular to any edge of the quadrilateral \(\mathcal{Q}\). At each vertex \(v\) of \(\mathcal{Q}\), we create a cone (which may not be closed) by using the edge directions \(m\). If the dot product of \(m\) and \(\epsilon\) is greater than \(0\) (\(m \cdot \epsilon > 0\)), we consider the nonnegative span of the edge direction. Conversely, if the dot product is less than \(0\) (\(m \cdot \epsilon < 0\)), we consider the negative span of the edge direction.

The Lawrence–Varchenko Formula says that adding the generating functions of these cones with appropriate signs gives the polynomial \(\sigma_{\mathcal{P}}(x)\) encoding the integer points in \(\mathcal{P}\), \begin{equation} \sigma_{\mathcal{P}}(x) = \sum_{v\in \mathcal{P}} (-1)^{|E_{v}^{-}(\epsilon)|} \sigma_{\mathcal{K_{\epsilon, v}}}(x). \end{equation}

Proofs

Brion’s original proof of his formula [1] involved the application of the Lefschetz-Riemann-Roch theorem in equivariant K-theory to a singular toric variety. However, there is good news! The remarkable formulas established by Brion and Lawrence-Varchenko now have accessible proofs that rely on counting techniques. This development makes understanding and verifying these formulas much simpler. The proof can be divided in four following steps.

1. Proving that the apex of the cone do not need to be rational.

In the first part we need to prove that we do not require that the apex \(v\) of the cone to be rational, but only that the generators \(w_i\) of the cone be linearly independent vectors in \(\mathbb{Z}^{d}\).

A simple rational \(\mathcal{K}\) cone in \(\mathbb{R}^{d}\) has the form,

\begin{equation} \mathcal{K} = \left\{v + \sum_{i=1}^{d}\lambda_{i}w_{i} \quad \Big |\quad \lambda_{i}\in \mathbb{R_{\geq 0}} = v + \sum_{i=1}^{d} \mathbb{R_{\geq 0}}w_{i}\right\}, \end{equation} where \(w_{1}, \ldots, w_{d}\in \mathbb{Z}^{d}\) are l.i.

The idea behind proving this is to tile a simple cone by translating its fundamental parallelepiped, denoted as \(\mathcal{P}\). By summing up the generating functions of all the translations of \(\mathcal{P}\), we obtain the generating function of the cone, denoted as \(\mathcal{K}\).

2. Decomposing the cone into simplicial cones.

If there exist a vector \(\epsilon\) such that \(\epsilon \cdot w_{i} >0\) for all \(i\), then \(\mathcal{K}\) is strictly convex. If \(\mathcal{K}\) is strictly convex, then it may be decomposed into simple cones having pairwise disjoint interiors, each with apex \(v\) and with the generators \(w_{i}\) of \(\mathcal{K}\). We would like to add the generating functions for each cone \(\mathcal{K_i}\) to obtain the generating function for \(\mathcal{K}\). However, some of the cones may have lattice points in common, so we needed to treat the subsequent overcounting.

An elegant approach to address this is by circumventing the issue of overcounting through the process of translating all the cones. There exists a short vector \(s \in \mathbb{R}^{d}\) such that and no facet of any cone contains any integer points. This gives the disjoint irrational decomposition, \begin{equation} \mathcal{K}\cap \mathbb{Z}^{d} = \bigcup_{i=1}^{l} \left (s+\mathcal{K_{i}}\right ), \end{equation}

and so,

\begin{equation} \sigma_{\mathcal{K}}(x) = \sum_{m\in \mathcal{K}\cap \mathbb{Z}^{d}}^{l} x^{m}=\sum_{i=1}^{l} \sigma_{s+\mathcal{K_{i}}}(x), \end{equation} is a rational function.

3. Connecting Formal Laurent Series with Rational Functions

While the Lawrence-Varchenko formula relies on simple cones and Brion’s formula involves strictly convex cones, we can employ even more general cones in the proof of these formulas. For this, we define a rational (closed) halfspace as the convex subset of \(\mathbb{R}^{d}\) that is defined by, \begin{equation} \left \{x\in \mathbb{R}^{d} \quad | \quad w\cdot x \geq b \right \}, \end{equation} A (closed) cone, denoted as \(\mathcal{K}\), is formed by the intersection of a finite number of closed halfspaces, where the boundary hyperplanes of these halfspaces share at least one common point. The apex of \(\mathcal{K}\) is the intersection of these boundary hyperplanes, which is an affine linear subspace. The generating function for the integer points in \(\mathcal{K}\) is the formal Laurent series, \begin{equation} \mathcal{S_{\mathcal{K}}} = \sum_{m\in \mathcal{K}}x^{m}. \end{equation} This formal series makes sense as a rational function only if \(\mathcal{K}\) is strictly convex, that is, if its apex is a single point.

The following theorem connects the formal Laurent series with rational functions. Furthermore, it states that there exists a unique homomorphism between the two spaces. This crucially enables us to establish Brion’s Formula by manipulating the formal Laurent series associated with each vertex and then employing the aforementioned theorem to obtain the rational function representing the entire simplex.

Theorem 1. There is a unique homomorphism of \(\mathbb{C}[x_{1}^{\pm 1}, \ldots, x_{d}^{\pm 1}]\)-modules, \begin{equation} \rho: PL \rightarrow \mathbb{C}(x_{1}, \ldots, x_{d}), \end{equation} s.t. \(\rho(\mathcal{S_{\mathcal{K}}}) = \sigma_{\mathcal{K}}\) for every simple cone \(\mathcal{K}\) in \(\mathbb{R}^{d}\)

  • PL denotes the polyhedral Laurent series, which is the \(\mathbb{C}[x_{1}^{\pm 1}, \ldots, x_{d}^{\pm 1}]\)-submodule of \(\mathbb{C}[[x_{1}^{\pm 1}, \ldots, x_{d}^{\pm 1}]]\) generated by the set of formal series \(\mathcal{S_{\mathcal{K}}}\) where \(\mathcal{K}\) is a simple rational cone.

  • \(\mathbb{C}(x_{1}, \ldots, x_{d})\) represents the field of rational functions in \(\mathbb{C}^{d}\), which is the quotien field of \(\mathbb{C}[x_{1}^{\pm 1}, \ldots, x_{d}^{\pm 1}]\).

With this theorem, we can deduce the following lema,

Lema. If a rational polyhedral cone \(\mathcal{K}\) is not strictly convex, then \(\rho(\mathcal{S_{\mathcal{K}}}) = 0\).

4. Connecting all together

We can now prove the Brion’s Formula for a simplex, and then extend it using irrational decomposition for the general case. A simplex is formed by the intersection of \(d+1\) halfspaces, with each facet corresponding to one of the halfspaces.

Theorem 2. If \(P\) is a simplex, then \begin{equation} 0 = \sum_{F} (-1)^{dim(F)} \mathcal{S_{\mathcal{K_{F}}}}, \end{equation} the sum over all the faces of \(P\).

Now applying the valuation map \(\rho\) to the formula above, and we obtain the Brion’s Formula for a simplex.

Just as for rational cones, every polytope may be decomposed into simplices having pairwise disjoint interiors, using only the vertices of \(\mathcal{P}\). This way we can procceed to prove the Brion’s Formula for a general polytope.

References

This is a summary of the ideas developed in the famous work Beck, M., Haase, C., & Sottile, F. (2009). (Formulas of Brion, Lawrence, and Varchenko on rational generating functions for cones). The Mathematical Intelligencer, 31, 9-17.

[1] M. Brion, Points entiers dans les polyèdres convexes, Ann. Sci. École Norm. Sup. 21 (1988), no. 4, 653–663.

[2] A.N. Varchenko, Combinatorics and topology of the arrangement of affine hyperplanes in the real space, Funktsional. Anal. i Prilozhen. 21 (1987), no. 1, 11–22.

[3] S. Verdoolaege, software package barvinok (2004), electronically available at http://freshmeat.net/projects/barvinok/.