LATTICE POINTS IN POLYTOPES, BOX SPLINES, AND TODD
OPERATORS

arXiv:1305.2784v1 [math.CO] 13 May 2013

MATTHIAS LENZ

Abstract. Let X be a list of vectors that is totally unimodular. In a previous
article the author proved that every real-valued function on the set of interior
lattice points of the zonotope defined by X can be extended to a function
on the whole zonotope of the form p(D)BX in a unique way, where p(D) is
a differential operator that is contained in the so-called internal P-space. In
this paper we construct an explicit solution to this interpolation problem in
terms of Todd operators. As a corollary we obtain a slight generalisation of
the Khovanskii-Pukhlikov formula that relates the volume and the number of
integer points in a smooth lattice polytope.

1. Introduction
Box splines and multivariate splines measure the volume of certain variable polytopes. The vector partition function that measures the number of integral points
in polytopes can be seen as a discrete version of these spline functions. Splines and
vector partition functions have recently received a lot of attention by researchers
in various fields including approximation theory, algebra, combinatorics, and representation theory. A standard reference from the approximation theory point of
view is the book [10] by de Boor, Höllig, and Riemenschneider. The combinatorial
and algebraic aspects are stressed in the book [11] by De Concini and Procesi.
Khovaniskii and Pukhlikov proved a remarkable formula that relates the volume
and the number of integer points in a smooth polytope [18]. The connection is
∂x
made via Todd operators, i. e. differential operators of type 1−e
∂x . The formula
is closely related to the Hirzebruch-Riemann-Roch Theorem for smooth projective
toric varieties (see [7, Chapter 13]). De Concini, Procesi, and Vergne have shown
that the Todd operator is in a certain sense inverse to convolution with the box
spline [13]. This implies the Khovanskii-Pukhlikov formula and more generally the
formula of Brion-Vergne [6].
In this paper we will prove a slight generalisation of the deconvolution formula
by De Concini, Procesi, and Vergne. The operator that we use is obtained from
the Todd operator, but it is simpler, i. e. it a polynomial contained in the so-called
internal P-space. Our proof uses deletion-contraction, so in some sense we provide
a matroid-theoretic proof of the Khovanskii-Pukhlikov formula.
Furthermore, we will construct bases for the spaces P− (X) and P(X) that were
studied by Ardila and Postnikov in connection with power ideals [2] and by Holtz
and Ron within the framework of zontopal algebra [15]. Up to now, no general
construction for a basis of the space P− (X) was known.
Date: 14th May 2013.
2010 Mathematics Subject Classification. Primary: 05B35, 19L10, 52B20, 52B40; Secondary:
13B25, 14M25, 16S32, 41A15, 47F05.
Key words and phrases. lattice polytope, box spline, vector partition function, KhovanskiiPukhlikov formula, matroid, zonotopal algebra.
The author was supported by a Junior Research Fellowship of Merton College (University of
Oxford).
1

2

MATTHIAS LENZ

Let us introduce our notation. It is similar to the one used in [11]. We fix a
d-dimensional real vector space U and a lattice Λ ⊆ U . Let X = (x1 , . . . , xN ) ⊆ Λ
be a finite list of vectors that spans U . We assume that X is totally unimodular
with respect to Λ, i. e. every basis for U that can be selected from X is also a lattice
basis for Λ. Note that X can be identified with a linear map X : RN → U . Let
u ∈ U . We define the variable polytopes
ΠX (u) := {w ∈ RN
≥0 : Xw = u}

and

Π1X (u) := ΠX (u) ∩ [0; 1]N .

(1)

Note that any convex polytope can be written in the form ΠX (u) for suitable X
and u. The dimension of these two polytopes is at most N − d. We define the
vector partition function TX (u) := ΠX (u) ∩ ZN ,
T −1/2

(2)
volN −d Π1X (u),

(3)

and the multivariate spline TX (u) := det(XX T )−1/2 volN −d ΠX (u).

(4)

the box spline BX (u) := det(XX )

Note that we have to assume that 0 is not contained in the convex hull of X in order
for TX and TX to be well-defined. Otherwise, ΠX (u) is an unbounded polyhedron.
The zonotope Z(X) is defined as
(N
)
X
Z(X) :=
λi xi : 0 ≤ λi ≤ 1 = X · [0, 1]N .
(5)
i=1

We denote its set of interior lattice points by Z− (X) := int(Z(X)) ∩ Λ. The
symmetric algebra over U is denoted by Sym(U ). We fix a basis s1 , . . . , sd for the
lattice Λ. This makes it possible to identify Λ with Zd , U with Rd , Sym(U ) with
the polynomial ring R[s1 , . . . , sd ], and X with a (d × N )-matrix. Then X is totally
unimodular if and only if every non-singular square submatrix of this matrix has
determinant 1 or −1. The base-free setup is more convenient when working with
quotient vector spaces.
We denote the dual vector space by V = U ∗ and we fix a basis t1 , . . . , td that is
dual to the basis for U . An element of Sym(U ) can be seen as a differential operator
on Sym(V ), i. e. Sym(U ) ∼
= R[s1 , . . . , sd ] ∼
= R[ ∂t∂1 , . . . , ∂t∂d ]. For f ∈ Sym(U ) and
p ∈ Sym(V ) we write f (D)p to denote the polynomial in Sym(V ) that is obtained
when f acts on p as a differential operator. It is known that the box spline is
piecewise polynomial and its local pieces are contained in Sym(V ). We will mostly
use elements of Sym(U ) as differential operators on its local pieces.
Note that a vector
Q u ∈ U defines a linear form u ∈ Sym(U ). For a sublist Y ⊆ X,
we define pY := y∈Y y. For example, if Y = ((1, 0), (1, 2)), then pY = s21 + 2s1 s2 .
Furthermore, p∅ := 1. Now we define the
central P-space P(X) := span{pY : rk(X \ Y ) = rk(X)}
\
and the internal P-space P− (X) :=
P(X \ x).

(6)
(7)

x∈X

The space P− (X) was introduced in [15] where it was also shown that the dimension
of this space is equal to |Z− (X)|. The space P(X) first appeared in approximation
theory [1, 9, 14]. These two P-spaces and generalisations were later studied by
various authors, including [2, 5, 16, 19, 21, 22].
In [20], the author proved the following theorem, which will be made more explicit
in the present paper.
∼ Rd be a list of vectors that is totally unimodular
Theorem 1. Let X ⊆ Λ ⊆ U =
and spans U . Let f be a real valued function on Z− (X), the set of interior lattice
points of the zonotope defined by X.

LATTICE POINTS, BOX SPLINES, AND TODD OPERATORS

3

Then there exists a unique polynomial p ∈ P− (X) ⊆ R[s1 , . . . , sd ], s. t. p(D)BX
is a continuous function and its restriction to Z− (X) is equal to f .
Here, p(D) denotes the differential operator obtained from p by replacing the
∂
variable si by ∂s
and BX denotes the box spline defined by X.
i
P
k
Let z ∈ U . As usual, the exponential is defined as ez := k≥0 zk! ∈ R[[s1 , . . . , sd ]].
We define the (z-shifted) Todd operator
Y
x
∈ R[[s1 , . . . , sd ]].
(8)
Todd(X, z) := e−z
1 − e−x
x∈X

The Todd operator can be expressed in terms of the Bernoulli numbers B0 = 1,
B1 = − 21 , B2 = 16 ,. . . Recall that they are defined by the equation:
X Bk
s
=
sk .
(9)
es − 1
k!
k≥0

P
One should note that e
=
= k≥0 Bk!k (−z)k . For z ∈ Z− (X) we can
fix a list S ⊆ X s. t. z = x∈S x. Let T := X \ S. Then we can write the Todd
operator as




Y X Bk
Y X Bk
Xx Xx


Todd(X, z) =
xk 
(−x)k  = 1 +
−
+ ...
k!
k!
2
2
z

x∈S

k≥0

z
ezP
−1

z
1−e−z

x∈T

x∈T

k≥0

x∈S

A sublist C ⊆ X is called a cocircuit if rk(X \ C) < rk(X) and C is inclusion
minimal with this property. We consider the cocircuit ideal J (X) := ideal{pC :
C cocircuit} ⊆ Sym(U ). It is known [14, 15] that Sym(U ) = P(X) ⊕ J (X). Let
ψX : P(X) ⊕ J (X) → P(X)

(10)

denote the projection. Note that this is a graded linear map and that ψX maps
any homogeneous polynomial to zero whose degree is at least N − d + 1. This
implies
P that there
P is a canonical extension ψX : R[[s1 , . . . , sd ]] → P(X) given by
ψX ( i (gi )) := i ψX (gi ), where gi denotes a homogeneous polynomial of degree i.
Let
fz = fzX := ψX (Todd(X, z)).

(11)

Theorem 2 (Main Theorem). Let X ⊆ Λ ⊆ U ∼
= Rd be a list of vectors that
is totally unimodular and spans U . Let z be a lattice point in the interior of the
zonotope Z(X).
Then fz ∈ P− (X), Todd(X, z)(D)BX extends continuously on U , and
fz (D)BX |Λ = Todd(X, z)(D)BX |Λ = δz .

(12)

Here, fz and Todd(X, z) act on the box spline BX as differential operators.
Dahmen and Micchelli observed that
TX = BX ∗d TX :=

X

BX (· − λ)TX (λ)

(13)

λ∈Λ

(cf. [11, Proposition 17.17]). Using this result, the following variant of the KhovanskiiPukhlikov formula [18] follows immediately.
Corollary 3. Let X ⊆ Λ ⊆ U ∼
= Rd be a list of vectors that is totally unimodular
and spans U , u ∈ Λ and z ∈ Z− (X). Then
|ΠX (u − z) ∩ Λ| = TX (u − z) = Todd(X, z)(D)TX (u) = fz (D)TX (u).

(14)

4

MATTHIAS LENZ

Remark 4. The box spline BX is piecewise polynomial. Hence each of its local
pieces is smooth but the whole function is not smooth where two different regions
of polynomiality intersect. De Concini, Procesi, and Vergne [13] proved the following deconvolution formula, where BX is replaced by a suitable local piece pc :
Todd(X, 0)(D)pc |Λ = δ0 . In Section 2 we will explain the choice of the local piece.
One can deduce from [13, Remark 3.15] that Todd(X, z)(D)BX can be extended
continuously if z ∈ Z− (X). It is also not difficult to show that Todd(X, z)(D)BX =
fz (D)BX (see Lemma 27) and that multiplying the Todd operator by e−x corresponds to translating Todd(X, z)(D)BX by x. The novelty of the Main Theorem
is that the operator fz for z ∈ Z− (X) is shorter than the original Todd operator
operator (cf. Example 15), i. e. it is contained in P− (X). Furthermore, we provide
a new proof for De Concini, Procesi, and Vergne’s deconvolution formula.
We will also prove a slightly different version of the Main Theorem (Theorem 12)
that only holds for local pieces of the box spline but where lattice points in the
boundary of the zonotope are permitted as well. This theorem implies the following
result.
Corollary 5. Let X ⊆ Λ ⊆ U ∼
= Rd be a list of vectors that is totally unimodular
and spans U and let z be a lattice point in the zonotope Z(X). Let u ∈ Λ and
let Ω ⊆ cone(X) be a chamber s. t. u is contained in its closure. Let pΩ be the
polynomial that agrees with TX on Ω. Then
|ΠX (u − z) ∩ Λ| = TX (u − z) = Todd(X, z)(D)pΩ (u) = fz (D)pΩ (u).

(15)

The original Khovanskii-Pukhlikov formula is the case z = 0 in Corollary 5. For
more information on this formula, see Vergne’s survey article on integral points in
polytopes [24]. An explanation of the Khovanskii-Pukhlikov formula that is easy
to read is contained in the book by Beck and Robins [4, Chapter 10].
Corollary 6. Let X ⊆ Λ ⊆ U ∼
= Rd be a list of vectors that is totally unimodular
and spans U . Then
X
BX (z)fz = 1.
(16)
z∈Z− (X)

This implies formula (13).
The central P-space and various other generalised P-spaces have a canonical
basis [15, 21]. Up to now, no general construction for a basis of the internal space
P− (X) was known (cf. [3, 15, 19]). The polynomials fz form such a basis.
Corollary 7. Let X ⊆ Λ ⊆ U ∼
= Rd be a list of vectors that is totally unimodular
and spans U . Then {fz : z ∈ Z− (X)} is a basis for P− (X).
We also obtain a new basis for the central space P(X). Let w ∈ U be a short
affine regular vector, i. e. a vector whose Euclidian length is close to zero that
is not contained in any hyperplane generated by sublists of X. Let Z(X, w) :=
(Z(X) − w) ∩ Λ (see Figure 4 for an example). It is known that dim P(X) =
|Z(X, w)| = vol(Z(X)) [15].
Corollary 8. Let X ⊆ Λ ⊆ U ∼
= Rd be a list of vectors that is totally unimodular
and spans U . Then {fz : z ∈ Z(X, w)} is a basis for P(X).
This corollary will be used to prove the following new characterisation of the
internal space P− (X).
Corollary 9. Let X ⊆ Λ ⊆ U ∼
= Rd be a list of vectors that is totally unimodular
and spans U . Then
P− (X) = {f ∈ P(X) : f (D)BX is a continuous function}.

(17)

LATTICE POINTS, BOX SPLINES, AND TODD OPERATORS

5

Remark 10. There is a related result due to Dahmen-Micchelli ([8] or [11, Theorem 13.21]): for every function f on Z(X, w) there exists a unique function in
DM(X) that agrees with f on Z(X, w). Here, DM(X) denotes the so-called discrete Dahmen-Micchelli space. The proof of the deconvolution formula in [13] relies
on this result.
Organisation of the article. The remainder of this article is organised as follows:
in Section 2, we will first define deletion and contraction. Then we will describe
a method to make sense of derivatives of piecewise polynomial functions via limits
and state a different version of the Main Theorem.
In Section 3 we will give some examples. In Section 4 we will recall some facts
about zonotopal algebra, i. e. about the space P(X), the dual space D(X) and their
connection with splines. These will be needed in the proof of the Main Theorem
and its corollaries in Section 5. In the appendix we will give an alternative proof
of the Main Theorem in the univariate case that uses residues.
Acknowledgements. The author would like to thank Michèle Vergne for her comments on [20] which lead to the present article. Some examples where calculated
using the Sage Mathematics Software System [23].
2. Deletion-contraction, limits, and the extended Main Theorem
In the first subsection, we will first define deletion and contraction and discuss the
idea of the deletion-contraction proof of the Main Theorem. In the second subsection, we will describe a method to make sense of derivatives of piecewise polynomial
functions via limits and then state a different version of the Main Theorem.
2.1. Deletion and contraction. Let x ∈ X. We call the list X \ x the deletion of
x. The image of X \ x under the canonical projection πx : U → U/ span(x) =: U/x
is called the contraction of x. It is denoted by X/x.
The projection πx induces a map Sym(U ) → Sym(U/x) that we will also denote
by πx . If we identify Sym(U ) with the polynomial ring R[s1 , . . . , sd ] and x = sd ,
then πx is the map from R[s1 , . . . , sd ] to R[s1 , . . . , sd−1 ] that sends sd to zero and
s1 , . . . , sd−1 to themselves. The space P(X/x) is contained in the symmetric algebra
Sym(U/x).
Note that since X is totally unimodular, Λ/x ⊆ U/x is a lattice for every x ∈ X
and X/x is totally unimodular with respect to this lattice.
Let x ∈ X. Using matroid theory terminology, we call x a loop if x = 0 and we
call x a coloop if rk(X \ x) < rk(X).
Recall that we defined fz = ψX (Todd(X, z)) for z ∈ Z− (X). By Theorem 1,
there is a unique polynomial qzX = qz ∈ P− (X) s. t. qz (D)BX |Λ = δz for every
z ∈ Z− (X). In order to prove the Main Theorem it is sufficient to show that fz = qz .
In fact, qz and fz behave in the same way under deletion and contraction: they
X\x
X/x
X
both satisfy the equalities xqz
= qzX − qz+x
and πx (qzX ) = qz̄ . Unfortunately,
it is not obvious that fz ∈ P− (X).
Therefore, we have to make a detour. Since P− (X) is in general not spanned by
polynomials of type pY for some Y ⊆ X (cf. [3]), it is quite difficult to handle this
space. The space P(X) on the other hand has a basis which is very convenient for
deletion-contraction (cf. Proposition 20). Therefore, we will work with the larger
space P(X) and do a deletion-contraction proof there. An extended version of
the Main Theorem will be stated in the next subsection. This will require some
adjustments since for f ∈ P(X), f (D)BX |Λ might not be well-defined.

6

MATTHIAS LENZ

1 − s2

1 − s1 − s2
2 − t2

1 + s1

2 − t1

1 + t1 − t2

1

t1

1 − t1 + t2

1 − s1

t2

1 + s1 + s2

1 + s2

Figure 1. The box spline and the polynomials fz corresponding
to Example 14.
2.2. Differentiating piecewise polynomial functions and limits.
Definition 11. Let H by a hyperplane spanned by a sublist Y ⊆ X. A shift of such
a hyperplane by a vector in the lattice Λ is called an affine admissible hyperplane.
An alcove is a connected component of the complement of the union of all affine
admissible hyperplanes
A vector w ∈ U is called affine regular, if it is not contained in any affine
admissible hyperplane. We call w short affine regular if its Euclidian length is close
to zero.
Note that on the closure of each alcove c, BX agrees with a polynomial pc . For
example, the six triangles in Figure 1 are the alcoves where BX agrees with a
non-zero polynomial.
Fix a short affine regular vector w ∈ U . Let u ∈ U . Let c ⊆ U be an alcove s. t.
u and u + εw are contained in its closure for some small ε > 0 and let pc be the
polynomial that agrees with BX on the closure of c. We define limw BX (z) := pc (z)
and for f ∈ Sym(U )
lim f (Dpw )BX (u) := f (D)pc (u)
w

(18)

(pw stands for piecewise). Note that the limit can be dropped if f (D)BX is continuous at u. Otherwise, the limit is important: note for example that limw B(1) (0)
is either 1 or 0 depending on whether w is positive or negative. More information
on this construction can be found in [13] where it was introduced. We will later
see that fz (D)BX (D) is continuous if z ∈ Z(X) ∩ Λ is in the interior of Z(X) and
discontinuous if it is on the boundary.
Recall that Z(X, w) := (Z(X) − w) ∩ Λ.
Theorem 12. Let X ⊆ Λ ⊆ U ∼
= Rd be a list of vectors that is totally unimodular
and spans U . Let w be a short affine regular and let z ∈ Z(X, w). Then
lim fz (Dpw )BX |Λ = lim Todd(X, z)(Dpw )BX |Λ = δz .
w

w

(19)

3. Examples
Example 13. We consider the three smallest one-dimensional examples. For X =
(1, 1) we obtain Todd((1, 1), 1) = (1 + B1 s + . . .)(1 − B1 s + . . .) = 1 + 0s + . . .
(1,1)
Hence f1
= 1. Furthermore,
s
s
(1,1,1)
(1,1,1)
f1
=1+ ,
f2
=1− ,
2
2
s2
s2
s2
(1,1,1,1)
(1,1,1,1)
(1,1,1,1)
f1
=1+s+ ,
f2
=1− ,
and f3
=1−s+ .
3
6
3

LATTICE POINTS, BOX SPLINES, AND TODD OPERATORS

7

Figure 2. The pentagon D, square , and triangle ∆ that we
discuss in Example 15.
Example 14. Let X = ((1, 0), (0, 1), (1, 1)) ⊆ Z2 . Then P− (X) = R, P(X) =
span{1, s1 , s2 }, Z− (X) = {(1, 1)}, and f(1,1) = 1. ΠX (u1 , u2 ) ∼
= [0, min(u1 , u2 )] ⊆
R1 . The multivariate spline and the vector partition function are:
(
(
u2 for 0 ≤ u2 ≤ u1
u2 + 1 for 0 ≤ u2 ≤ u1
and TX (x, y) =
.
TX (u1 , u2 ) =
u1 for 0 ≤ u1 ≤ u2
u1 + 1 for 0 ≤ u1 ≤ u2
(20)
Corollary 3 correctly predicts that TX (u)|Z2 = TX (u − (1, 1)). Figure 1 shows the
six non-zero local pieces of BX and the seven polynomials fz attached to the lattice
points of the zonotope Z(X).
Example 15. We consider the polygons in Figure 2, which we will denote by D,
, and ∆. These polytopes are defined by the matrix


1 0 0 1 0
(21)
X = 0 1 0 0 1 ,
0 0 1 1 1
where the first three columns correspond to slack variables and the rows of the
last two are the normal vectors of the movable facets. The corresponding zonotope
has two interior lattice points: (1, 1, 1) corresponds to  and (1, 1, 2) to ∆. The
projections of the Todd operators are f = 1 + s3 /2 and f∆ = 1 − s3 /2, where s3
corresponds to shifting the diagonal face of the pentagon. Elementary calculations
show that shifting this face outwards1 by ε ∈ [−1, 1] increases the volume of the
pentagon by (ε − 21 ε2 ). This implies ∂s∂ 3 vol(pentagon) = 1.
The volume of the pentagon is 3.5. Corollary 3 correctly predicts that
1 ∂
vol(D) = 4
2 ∂s3
1 ∂
= vol(D) −
vol(D) = 3.
2 ∂s3

 ∩ Z2 = vol(D) +
and ∆ ∩ Z2

(22)
(23)

The projection to P(X) of the unshifted Todd operator Todd(X, 0) is a lot more
complicated: fD = 1 + s1 + s2 + 23 s3 + s1 s2 + s1 s3 + s2 s3 + s23 .
On the other hand, since Z− (X) contains only two points, the box spline BX
must assume the value 21 at both points. Then (13) correctly predicts that the
volume of the pentagon is the arithmetic mean of the number of integer points in
the square and the triangle.
Remark 16. If X is not totally unimodular, then ψX (Todd(X, z)) is in general
not contained in P− (X). Consider for example X = (2, 1) and Todd(X, z) =
x
2x
e2x −1 1−e−x . Then
ψX (fz ) = ψX (2(1 + 2B1 x)(1 − B1 x)) = 2 − x 6∈ P− (X) = R.
1This means replacing the inequality a + b ≤ 3 by a + b ≤ 3 + ε.

(24)

8

MATTHIAS LENZ

Figure 3. The zonotope corresponding to Example 17. It has six
interior lattice points.
Example 17. Let X be a reduced oriented incidence matrix of the complete graph
on 4 vertices / the set of positive roots of the root system A3 (cf. Figure 3), i. e.


1 0 0
1
1
0
0
1 .
(25)
X =  0 1 0 −1
0 0 1
0 −1 −1
1
1
1
1
1
1
f(1,1,0) = − t1 t2 − t1 t3 + t2 t3 + t1 − t2 − t3 + 1
(26)
6
6
3
2
2
2
1
1
1
1
1
1
f(1,1,−1) = − t1 t2 + t1 t3 − t2 t3 + t1 − t2 + t3 + 1
(27)
6
3
6
2
2
2
1
1
1
1
1
1
f(2,0,−1) = − t1 t2 − t1 t3 + t2 t3 − t1 + t2 + t3 + 1
(28)
6
6
3
2
2
2
1
1
1
1
1
1
f(1,0,0) = t1 t2 − t1 t3 − t2 t3 + t1 + t2 − t3 + 1
(29)
3
6
6
2
2
2
1
1
1
1
1
1
f(2,1,−1) = t1 t2 − t1 t3 − t2 t3 − t1 − t2 + t3 + 1
(30)
3
6
6
2
2
2
1
1
1
1
1
1
f(2,0,0) = − t1 t2 + t1 t3 − t2 t3 − t1 + t2 − t3 + 1
(31)
6
3
6
2
2
2
4. Zonotopal Algebra
In this section we will recall a few facts about the space P(X) and its dual, the
space D(X) that is spanned by the local pieces of the box spline. The theory around
these spaces was named zonotopal algebra by Holtz and Ron in [15]. This theory
allows us to explicitly describe the map ψX . This description will then be used to
describe the behaviour of the polynomials fz under deletion and contraction. This
section is an extremely condensed version of [21].
Recall that the list of vectors X is contained in a vector space U ∼
= Rd and
that we denote the dual space by V . We start by defining a pairing between the

LATTICE POINTS, BOX SPLINES, AND TODD OPERATORS

9

symmetric algebras Sym(U ) ∼
= R[s1 , . . . , sd ] and Sym(V ) ∼
= R[t1 , . . . , td ]:
h·, ·i : R[s1 , . . . , sd ] × R[t1 , . . . , td ] → R
 
 
∂
∂
hp, f i := p
,...,
f (0),
∂t1
∂td

(32)

i. e. we let p act on f as a differential operator and take the degree zero part
of the result. Note that this pairing extends to a pairing h·, ·i : R[[s1 , . . . , sd ]] ×
R[t1 , . . . , td ] → R.
It is known that the box spline BX agrees with a polynomial on the closure
of each alcove. These local pieces and their partial derivatives span the DahmenMicchelli space D(X). This space can be described as the kernel of the cocircuit
ideal J (X), namely
D(X) = {f ∈ Sym(V ) : hp, f i = 0 for all p ∈ J (X)}.

(33)

We will now explain a construction of certain polynomials that is essentially due
to De Concini, Procesi, and Vergne [12]. Let Z ⊆ U be a finite list of vectors
and let B = (b1 , . . . , bd ) ⊆ Z be a basis. It is important that the basis is ordered
and that this order is the order obtained by restricting the order on Z to B. For
i ∈ {0, . . . , d}, we define Si = SiB := span{b1 , . . . , bi }. Hence
{0} = S0B ( S1B ( S2B ( . . . ( SdB = U ∼
= Rd

(34)

is a flag of subspaces. Let u ∈ Si \ Si−1 . The vector u can be written as u =
Pi
ν=1 λν bν in a unique way. Note that λi 6= 0. If λi > 0, we call u positive and if
λi < 0, we call u negative. We partition Z ∩ (Si \ Si−1 ) as follows:

and

PiB := {u ∈ Z ∩ (Si \ Si−1 ) : u positive}

(35)

NiB

(36)

:= {u ∈ Z ∩ (Si \ Si−1 ) : u negative}.

We define
TiB+ := (−1)|Ni | · TPi ∗ T−Ni and TiB− := (−1)|Pi | · T−Pi ∗ TNi .

(37)

Note that TiB+ is supported in cone(Pi , −Ni ) and that
TiB− (x) = (−1)|Pi ∪Ni | TiB+ (−x).

(38)

Now define
RiB := TiB+ − TiB−

and

B
RZ
= RB := R1B ∗ · · · ∗ RdB .

(39)

We denote the set of all sublists B ⊆ X that are bases for U by B(X). Fix a basis
B ∈ B(X). A vector x ∈ X \B is called externally active if x ∈ span{b ∈ B : b ≤ x},
i. e. x is the maximal element of the unique circuit contained in B ∪ x. The set of
all externally active elements is denoted E(B).
Definition 18 (Basis for D(X)). Let X ⊆ U ∼
= Rd be a finite list of vectors that
spans U. We define
B
Б(X) := {|det(B)| RX\E(B)
: B ∈ B(X)}.

(40)

Proposition 19 ([14, 17]). Let X ⊆ U ∼
= Rd be a finite list of vectors that spans
U. Then the spaces P(X) and D(X) are dual under the pairing h·, ·i, i. e.
D(X) → P(X)∗
f 7→ h·, f i
is an isomorphism.

(41)

10

MATTHIAS LENZ

Proposition 20 ([14]). Let X ⊆ U ∼
= Rd be a finite list of vectors that spans U. A
basis for P(X) is given by
B(X) := {QB : B ∈ B(X)},

(42)

where QB := pX\(B∪E(B)) .
Theorem 21 ([21]). Let X ⊆ U ∼
= Rd be a finite list of vectors that spans U. Then
Б(X) is a basis for D(X) and this basis is dual to the basis B(X) for the central
P-space P(X).
Remark 22. Theorem 21 yields an explicit formula for the projection map ψX :
R[[s1 , . . . , sd ]] → P(X) that we have defined on page 3:
X
fz := ψX (Todd(X, z)) =
hTodd(X, z), RB i QB .
(43)
B∈B(X)

5. Proofs
In this section we will prove the Main Theorem and its corollaries. The proof
uses a deletion-contraction argument. Deletion-contraction identities for the polynomials fz will be obtained based on the following idea: one can write ψX (f ) as
X
X
X
ψX (f ) =
hf, RB i QB =
hf, RB i QB +
hf, RB i QB (44)
x6∈B∈B(X)

B∈B(X)

x∈B∈B(X)

(cf. Remark 22). We will see that the first sum on the right-hand side of (44)
corresponds to P− (X \ x) and the second to P− (X/x). Note that ψX (f ) is by
definition independent of the order imposed on the list X, while each of the two
sums depends on this order.
It is an important observation that for x ∈ X and z ∈ Λ
x · Todd(X \ x, z) = Todd(X, z) − Todd(X, z + x)
holds because

x
1−e−x (1

−e

−x

(45)

) = x.

Lemma 23. Let x ∈ X and let f ∈ Sym(U ). Then
xψX\x (f ) = ψX (xf ).

(46)

X
xfzX\x = fzX − fz+x
.

(47)

Furthermore, for all z ∈ Λ,

Proof. Note that the statement is trivial for x = 0, so from now on we assume that
x is not a loop. Since ψX (f ) is independent of the order imposed on X, we may
rearrange the list elements s. t. x is minimal.
Let x ∈ B ∈ B(X). Since x is minimal, span(x) ∩ (X \ E(B)) = {x}. By
Lemma 4.5 in [21], this implies that hxf, RB i = hf, Dx RB i = hf, 0i = 0.
Let x 6∈ B ∈ B(X). Since x is minimal, this implies that x 6∈ E(B). Then
B
B
B
hxf, RX\E(B)
i = hf, Dx RX\E(B)
i = hf, RX\(E(B)∪x)
i.

Using the two previous observations we obtain:
X
X
B
ψX (xf ) =
hxf, RX\E(B)
i QB +

=

{z

=0

X

(49)

x6∈B∈B(X)

x∈B∈B(X)

|

B
hxf, RX\E(B)
i QB

(48)

}
X\x

B
hf, RX\(E(B)∪x)
i x QB

= xψX\x (f ).

(50)

B∈B(X\x)

The second to last equality follows from the fact that QX
B = pX\(B∪E(B)) =
X\x

xpX\(B∪E(B)∪x) = QB

if x 6∈ B ∪ E(B).

LATTICE POINTS, BOX SPLINES, AND TODD OPERATORS

11

Figure 4. Deletion and contraction for the set Z(X, w).
We can deduce the second claim using (45):
xfzX\x = xψX\x (Todd(X \ x, z)) = ψX (x Todd(X \ x, z))
= ψX (Todd(X, z) − Todd(X, z + x)) =

fzX

−

X
fz+x
.

(51)


Recall that πx : Sym(U ) → Sym(U/x) denotes the canonical projection.
Lemma 24. Let x ∈ X be neither a loop nor a coloop. Let z ∈ Λ and let z̄ =
πx (z) ∈ Λ/x. Then
πx (fz ) = fz̄ .

(52)

Proof. Since the maps πx and ψX are independent of the order imposed on X, we
may rearrange the list elements s. t. x is minimal.
B\x
Let x ∈ B ∈ B(X). Given that x is minimal, RB = (Tx − T−x ) ∗ RX\(E(B)∪x)
follows. Hence RB is constant in direction x so we can interpret it as a function on
U/x and identify it with RB̄ . In Todd(X, z), the factor x/(1 − e−x ) becomes 1 if
we set x to 0. Note that x divides QB if x 6∈ B since x is minimal. Then
!
X
B
πx (fz ) = πx
hTodd(X, z), R i QB
x6∈B∈B(X)

|

{z

=0, since x|QB .

}

(53)
!

X

+ πx

hTodd(X, z), RB i QB

x∈B∈B(X)

=

X

hTodd(X/x, z̄), RB̄ i QB̄ = fz̄ .



B̄∈B(X/x)

In [20], the author showed that the function
γX : P− (X) → Ξ(X) := {f : Λ → R : supp(f ) ⊆ Z− (X)}

(54)

that maps p to p(D)BX |Λ is an isomorphism. We will now extend γX to a map
that is an isomorphism between P(X) and a superspace of Ξ(X).
For a short affine regular vector w ∈ U we define
w
γX
: P(X) → Ξw (X) := {f : Λ → R : supp(f ) ⊆ Z(X, w)}

p 7→ lim p(Dpw )BX |Λ .

(55)

w

∼ Rd be a list of vectors that is totally unimodProposition 25. Let X ⊆ Λ ⊆ U =
ular and spans U . Let x ∈ X be neither a loop nor a coloop.

12

MATTHIAS LENZ

Then the following diagram of real vector spaces is commutative, the rows are
exact and the vertical maps are isomorphisms:
0

/ P(X \ x)

·x

w
γX\x

0


/ Ξw (X \ x)

/ P(X)

πx


/ Ξw (X)

/0

(56)

w̄
γX/x

w
γX

∇x

/ P(X/x)

Σx


/ Ξw̄ (X/x)

/0

where ∇x (f )(z) := f (z) − f (z − x)
X
X
and Σx (f )(z̄) :=
f (x) =
f (λx + z) for some z ∈ z̄.
x∈z̄∩Λ

λ∈Z

Proof. First note that the map Z(X, w) \ Z(X \ x, w) → Z(X/x, w̄) that sends z
to z̄ is a bijection. This is a variant of [20, Lemma 17] and it can be proved in
the same way, using the fact that dim P(X) = vol(Z(X)) = |Z(X, w)|, which was
established in [15]. See also Figure 4. This implies that the second row is exact.
Exactness of the first row is known (e. g. [2, Proposition 4.4]).
If X contains only loops and coloops, then P(X) = R and BX is the indicator
function of the parallelepiped spanned by the coloops. For every short affine regular
w
w, Z(X, w) contains a unique point zw and limw BX (zw ) = 1. Hence γX
is an
isomorphism in this case. Note that this also holds for U = Λ = {0}. In this case
w = 0, Z(X) = {0} = Z(X, w), and BX = limw BX = 1.
The rest of the proof is analogous to the proof of [20, Proposition] and therefore
omitted.

w −1
) (δz ) ∈ P(X). By construction, this
For z ∈ Z(X, w), let qzX,w = qzw := (γX
w
polynomial satisfies limw qz (Dpw )BX |Λ = δz .

Lemma 26. Let w ∈ U be a short affine regular vector and let z ∈ Z(X, w). Then
qzw = fz .
0
In particular, qzw = qzw for short affine regular vectors w and w0 s. t. z ∈
Z(X, w) ∩ Z(X, w0 ).
Proof. Fix a short affine regular w. We will show by induction that qzw = fz for all
z ∈ Z(X, w).
If X contains only loops and coloops, then P(X) = R and BX is the indicator
function of the parallelepiped spanned by the coloops. Hence fz = ψX (1 + . . .) =
1 = qzw . Note that this is also holds for U = Λ = {0}. In this case w = 0,
Z(X) = {0} = Z(X, w), and BX = limw BX = 1.
Now suppose that there is an element x ∈ X that is neither a loop nor a coloop
and suppose that the statement is already true for X/x and X \ x.
Let gzw = gz := fz − qzw ∈ P(X).
X\x
Step 1. If z 0 = z + λx for some λ ∈ Z, then gz = gz0 : by Lemma 23, xfz
=
X\x,w
X
X
w
fz − fz+x . Because of the commutativity of (56), γX (xqz
) = ∇x (δz ). Since
X\x,w
X\x
X,w
w
γX
is an isomorphism this implies xqz
= qzX,w − qz+x
. By assumption, qz
=
X\x
X,w
X
X
X,w
fz . Hence we can deduce that fz − fz+x = qz − qz+x and the claim follows.
Step 2. πx (gz ) = 0: it follows from Proposition 25 that πx (qzw ) = qz̄w̄ . Taking
into account Lemma 24 this implies πx (gz ) = fz̄ − qz̄w̄ . This is zero by assumption.
Step 3. gz = 0: using the commutativity of (56) again and steps 1 and 2, we
obtain
w
w
w̄
|Z(X, w) ∩ (span(x) + z)| · γX
(gz ) = Σx (γX
(gz )) = γX/x
(πx (gz )) = 0.
w
w
Hence γX
(gz ) = 0 and the claim follows since γX
is an isomorphism.

(57)


LATTICE POINTS, BOX SPLINES, AND TODD OPERATORS

13

Lemma 27. Let f ∈ R[[s1 , . . . , sd ]] and let w be a short affine regular vector.
(1) Then limw f (Dpw )BX = limw ψX (f )(Dpw )BX .
(2) If ψX (f )(D)BX is continuous, then f (D)BX can be extended continuously
s. t. ψX (f )(D)BX = f (D)BX .
Proof. Let u ∈ U and let c be the alcove s. t. u + εw ∈ c for all sufficiently small
ε > 0. Let pc be the polynomial that agrees with BX on the closure of c. By
definition of the map ψX , for all i the degree i part of j = f − ψX (f ) is contained
in J (X). By definition of D(X), pc ∈ D(X). Then (33) implies j(D)pc = 0. Hence
limw f (Dpw )BX (u) = f (D)pc (u) = ψX (f )(D)pc (u) = limw ψX (f )(Dpw )BX (u).
If ψX (f )(D)BX is continuous, then
ψX (f )(D)BX (u) = lim ψX (f )(Dpw )BX (u) = lim f (Dpw )BX (u)
w

w

(58)

for all short affine regular vectors w, so if we define f (D)BX (u) := ψX (f )BX (u)
for all u ∈ U , we obtain a continuous extension of f (D)BX to U .

Proof of Theorem 2 (Main Theorem) and of Theorem 12. If w is a short affine regular vector and z ∈ Z(X, w), then limw fz (Dpw )BX |Λ = δz by Proposition 25 and
Lemma 26.
Now let z ∈ Z− (X). Then by Theorem 1, there exists qz− ∈ P− (X) s. t.
−
qz (D)BX |Z− (X) = δz and qz− (D)BX is continuous. Continuity implies that qz− (D)BX
vanishes on the boundary of Z(X), so qz− (D)BX |Λ = δz . Furthermore, for any short
w
is injective, qz− = qzw = fz must
affine regular w, limw qz− (Dpw )BX |Λ = δz . Since γX
hold. Hence, fz ∈ P− (X).
To finish the proof, note that Lemma 27 implies that limw fz (Dpw )BX |Λ =
limw Todd(X, z)(Dpw )BX |Λ and if fz (D)BX is continuous it is possible to extend
Todd(X, z)(D)BX continuously s. t. fz (D)BX = Todd(X, z)(D)BX .

P
Proof of Corollary 6. Let p :=
z∈Z− (X) BX (z)fz . By the Main Theorem, p ∈
P− (X) and p(D)BX and BX = 1(D)BX agree on Z− (X). By the uniqueness part
of Theorem 1 this implies p = 1.
Using the previous observation and Corollary 3 we can deduce (13):
X
X
BX ∗d TX (u) =
BX (u − λ)TX (λ) =
BX (z)TX (u − z)
(59)
z∈Λ

λ∈Λ

=

X

BX (z)fz (D)TX (u) = TX (u).



z∈Λ

Proof of Corollary 7. By Theorem 2, {fz : z ∈ Z− (X)} is a linearly independent
subset of P− (X). This set is actually a basis since |Z− (X)| = dim P− (X). This
equality follows from Theorem 1. It was also proven in [15].

Proof of Corollary 8. By construction, {fz : z ∈ Z(X, w)} ⊆ P(X). Proposition 25
and Lemma 26 imply that the set is actually a basis.

Proof of Corollary 9. “⊆” is part of Theorem 1.
“⊇”: Let p ∈ P(X) and suppose that p(D)BX is continuous. Let w be a short
affinePregular vector. By Corollary 8, there exist uniquely determined λz ∈ R s. t.
p = z∈Z(X,w) λz fz .
Let z ∈ Z(X, w) \ Z− (X). Since z − w 6∈ Z(X), lim−w p(Dpw )BX (z) = 0 holds.
As we assumed that p(D)BX is continuous, this implies that
X
0 = lim p(Dpw )BX (z) =
λy δy (z) = λz .
(60)
w

y∈Z(X,w)

Hence p =

P

z∈Z− (X)

λz fz , which is in P− (X) by the Main Theorem.



14

MATTHIAS LENZ

Appendix A. The univariate case and residues
In this appendix we will give an alternative proof of (a part of) the Main Theorem
in the univariate case. This proof was provided by Michèle Vergne.
A totally unimodular list of vectors X ⊆ Z1 ⊆ R1 contains only entries in
{−1, 0, 1}. Suppose that it contains a times −1 and b times 1. The zonotope Z(X)
is then the interval [−a, b]. We may assume that X does not contain any zeroes and
we choose N s. t. a + b = N + 1. Then P(X) = R[s]≤N and P− (X) = R[s]≤N −1 .
Let z ∈ Z− (X) = {−a + 1, . . . , b − 1}. Then there exist positive integers α and
β s. t.
b 
β
a 
α 

s
s
s
s
−zs
=
. (61)
Todd(X, z) := e
es − 1
1 − e−s
es − 1
1 − e−s
In this case, ψX : R[s] → R[s]≤N is the map that forgets all monomials of degree
greater or equal N + 1.
Lemma 28. Let X ⊆ Z1 ⊆ R1 be a list of vectors that is totally unimodular and let
z be an interior lattice point of the zonotope Z(X). Then fz = ψX (Todd(X, z)) ∈
P− (X).
Proof. Suppose that X contains N + 1 non-zero entries. Todd(X, z) agrees with its
Taylor expansion
Todd(X, z) = 1 + c1 s + . . . + cN sN + . . .

(62)

The coefficients ci depend on z and X and can be expressed in terms of Bernoulli
numbers. It is sufficient to show that cN = 0. This can be done by calculating the
residue at the origin. Let γ ⊆ C be a circle around the origin. Using the residue
theorem and the considerations at the beginning of this section we obtain:


1
cN = Res0 (z −(N +2) Todd(X, z)) = Res0
(63)
(es − 1)α (1 − e−s )β
I
I
1
1
1
1
1
ds
=
dσ (64)
=
−s
α
s
β
−1
α
β
2πi γ (1 − e ) (e − 1)
2πi exp(γ) (1 − σ ) (σ − 1) σ
I
I
α−1
X α − 1 
1
σ α−1
1
(σ − 1)−(α+β)+i dσ.
=
dσ
=
2πi exp(γ) (σ − 1)α+β
2πi exp(γ) i=0
i
The last equality can easily be seen by substituting y = σ + 1, expanding, and
resubstituting. Note that exp(γ) is a curve around 1. Since α and β are positive
the residue of the integrand of the last integral at one is 0. Hence cN = 0.

References
[1] A. A. Akopyan and A. A. Saakyan, A system of differential equations that is related to the
polynomial class of translates of a box spline, Mat. Zametki 44 (1988), no. 6, 705–724, 861.
[2] Federico Ardila and Alexander Postnikov, Combinatorics and geometry of power ideals,
Trans. Amer. Math. Soc. 362 (2010), no. 8, 4357–4384.
[3]
, Two counterexamples for power ideals of hyperplane arrangements, 2012, arXiv:
1211.1368, submitted as a corrigendum for [2].
[4] Matthias Beck and Sinai Robins, Computing the continuous discretely, Undergraduate Texts
in Mathematics, Springer, New York, 2007, Integer-point enumeration in polyhedra.
[5] Andrew Berget, Products of linear forms and Tutte polynomials, European J. Combin. 31
(2010), no. 7, 1924–1935.
[6] Michel Brion and Michèle Vergne, Residue formulae, vector partition functions and lattice
points in rational polytopes, J. Amer. Math. Soc. 10 (1997), no. 4, 797–833.
[7] David A. Cox, John B. Little, and Henry K. Schenck, Toric varieties, Graduate Studies in
Mathematics, vol. 124, American Mathematical Society, Providence, RI, 2011.
[8] Wolfgang Dahmen and Charles A. Micchelli, On the local linear independence of translates
of a box spline, Studia Math. 82 (1985), no. 3, 243–263.

LATTICE POINTS, BOX SPLINES, AND TODD OPERATORS

15

[9] Carl de Boor, Nira Dyn, and Amos Ron, On two polynomial spaces associated with a box
spline, Pacific J. Math. 147 (1991), no. 2, 249–267.
[10] Carl de Boor, Klaus Höllig, and Sherman D. Riemenschneider, Box splines, Applied Mathematical Sciences, vol. 98, Springer-Verlag, New York, 1993.
[11] Corrado De Concini and Claudio Procesi, Topics in hyperplane arrangements, polytopes and
box-splines, Universitext, Springer, New York, 2011.
[12] Corrado De Concini, Claudio Procesi, and Michèle Vergne, Vector partition functions and
index of transversally elliptic operators, Transform. Groups 15 (2010), no. 4, 775–811.
[13]
, Box splines and the equivariant index theorem, Journal of the Institute of Mathematics of Jussieu (2012), 1–42, published online.
[14] Nira Dyn and Amos Ron, Local approximation by certain spaces of exponential polynomials,
approximation order of exponential box splines, and related interpolation problems, Trans.
Amer. Math. Soc. 319 (1990), no. 1, 381–403.
[15] Olga Holtz and Amos Ron, Zonotopal algebra, Advances in Mathematics 227 (2011), no. 2,
847–894.
[16] Olga Holtz, Amos Ron, and Zhiqiang Xu, Hierarchical zonotopal spaces, Trans. Amer. Math.
Soc. 364 (2012), 745–766.
[17] Rong-Qing Jia, Subspaces invariant under translations and dual bases for box splines., Chin.
Ann. Math., Ser. A 11 (1990), no. 6, 733–743 (Chinese).
[18] A. G. Khovanskiı̆ and A. V. Pukhlikov, The Riemann-Roch theorem for integrals and sums
of quasipolynomials on virtual polytopes, Algebra i Analiz 4 (1992), no. 4, 188–216.
[19] Matthias Lenz, Hierarchical zonotopal power ideals, European J. Combin. 33 (2012), no. 6,
1120–1141.
[20]
, Interpolation, box splines, and lattice points in zonotopes, 2012, arXiv:1211.1187.
[21]
, Zonotopal algebra and forward exchange matroids, 2012, arXiv:1204.3869v2.
[22] Nan Li and Amos Ron, External zonotopal algebra, 2011, arXiv:1104.2072v1.
[23] W. A. Stein et al., Sage Mathematics Software (Version 5.6), The Sage Development Team,
2013, http://www.sagemath.org.
[24] Michèle Vergne, Residue formulae for Verlinde sums, and for number of integral points in
convex rational polytopes, European women in mathematics (Malta, 2001), World Sci. Publ.,
River Edge, NJ, 2003, pp. 225–285.
E-mail address: lenz@maths.ox.ac.uk
Mathematical Institute, 24-29 St Giles’, Oxford, OX1 3LB, United Kingdom

