Euler-Maclaurin formula and Riemann-Roch

Let $Df$ denote the derivative of a function $f(x)$ and $\bigtriangledown f=f(x)-f(x-1)$ be the discrete derivative. Using the Taylor series expansion for $f(x-1)$, we easily get $\bigtriangledown = 1- e^{-D}$ or, by taking the inverses, $$\frac{1}{\bigtriangledown} = \frac{1}{1-e^{-D}} = \frac{1}{D}\cdot \frac{D}{1-e^{-D}}= \frac{1}{D} + \frac12+ \sum_{k=1}^{\infty} B_{2k}\frac{D^{2k-1}}{(2k)!} ,$$ where $B_{2k}$ are Bernoulli numbers.

(Edit: I corrected the signs to adhere to the most common conventions.)

Here, $(1/D)g$ is the opposite to the derivative, i.e. the integral; adding the limits this becomes a definite integral $\int_0^n g(x)dx$. And $(1/\bigtriangledown)g$ is the opposite to the discrete derivative, i.e. the sum $\sum_{x=1}^n g(x)$. So the above formula, known as Euler-Maclaurin formula, allows one, sometimes, to compute the discrete sum by using the definite integral and some error terms.

Usually, there is a nontrivial remainder in this formula. For example, for $g(x)=1/x$, the remainder is Euler's constant $\gamma\simeq 0.57$. Estimating the remainder and analyzing the convergence of the power series is a long story, which is explained for example in the nice book "Concrete Mathematics" by Graham-Knuth-Patashnik. But the power series becomes finite with zero remainder if $g(x)$ is a polynomial. OK, so far I am just reminding elementary combinatorics.

Now, for my question. In the (Hirzebruch/Grothendieck)-Riemann-Roch formula one of the main ingredients is the Todd class which is defined as the product, going over Chern roots $\alpha$, of the expression $\frac{\alpha}{1-e^{-\alpha}}$. This looks so similar to the above, and so suggestive (especially because in the Hirzebruch's version $$\chi(X,F) = h^0(F)-h^1(F)+\dots = \int_X ch(F) Td(T_X)$$ there is also an "integral", at least in the notation) that it makes me wonder: is there a connection?

The obvious case to try (which I did) is the case when $X=\mathbb P^n$ and $F=\mathcal O(d)$. But the usual proof in that case is a residue computation which, to my eye, does not look anything like Euler-Maclaurin formula.

But is there really a connection?

An edit after many answers: Although the connection with Khovanskii-Pukhlikov's paper and the consequent work, pointed out by Dmitri and others, is undeniable, it is still not obvious to me how the usual Riemann-Roch for $X=\mathbb P^n$ and $F=\mathcal O(d)$ follows from them. It appears that one has to prove the following nontrivial

Identity: The coefficient of $x^n$ in $Td(x)^{n+1}e^{dx}$ equals $$\frac{1}{n!} Td(\partial /\partial h_0) \dots Td(\partial /\partial h_n) (d+h_0+\dots + h_n)^n |_{h_0=\dots h_n=0}$$

A complete answer to my question would include a proof of this identity or a reference to where this is shown. (I did not find it in the cited papers.) I removed the acceptance to encourage a more complete explanation.

-
A comment on the nice answers and the references contained in them. It appears that for Hirzebruch-Riemann-Roch one uses not the Euler-Maclaurin formula written up above but a version from Khovanskii-Pukhlikov's paper, spelled out in D. Speyer's answer. For $g(x)$ which is a quasipolynomial (combination of polynomials and exponential functions) this gives an exact formula. For the most important case of $X=P^n$ and $F=O(d)$, the polytope is the standard simplex dilated by $d$ and $g(x)=1$. (But Karshon-Sternberg-Weitzman also consider formulas with remainders for more general $g(x)$). –  VA. Jan 4 '10 at 23:24
I didn't answer this question. Do you mean an answer of mine elsewhere, or have you confused me with someone else? –  David Speyer Jan 11 '10 at 19:10
@ David Speyer: indeed, I meant Steve Huntsman's answer. My apologies to both of you. –  VA. Jan 12 '10 at 2:06
I added the proof of this combinatorial identity below. I don't want to reedit the question, however, so as not to push the question in the community wiki abyss. –  VA. Jan 24 '10 at 16:04

As far as I understand this connection was observed (and generalised) by Khovanskii and Puhlikov in the article

A. G. Khovanskii and A. V. Pukhlikov, A Riemann-Roch theorem for integrals and sums of quasipolynomials over virtual polytopes, Algebra and Analysis 4 (1992), 188–216, translation in St. Petersburg Math. J. (1993), no. 4, 789–812.

This is related to toric geometry, for which some really well written introduction articles are contained on the page of David Cox http://www3.amherst.edu/~dacox/

Since 1992 many people wrote on this subject, for example

EXACT EULER MACLAURIN FORMULAS FOR SIMPLE LATTICE POLYTOPES

http://arxiv.org/PS_cache/math/pdf/0507/0507572v2.pdf

Or Riemann sums over polytopes http://arxiv.org/PS_cache/math/pdf/0608/0608171v1.pdf

-

Euler-Maclaurin's formula transforms the integral $I=\int_a^b f(x)dx$ into the finite sum $S=\sum_a^b f(x)$, for two integers $a,b$. As Dmitri pointed out, in 1993 Khovanskii and Pukhlikov gave a multi-dimensional generalization of Euler-Maclaurin which, in particular says the following:

Let $P$ be an $n$-dimensional polytope in $\mathbb R^n\supset\mathbb Z^n$ with integral vertices, and further assume that $P$ defines a nonsingular toric variety (i.e. $P$ is simplicial and at every vertex the integral generators of the edges give a basis in $\mathbb Z^n$). Let us say the facets of $P$ are defined by the inequalities $l_j(x)\le a_j$ for some primitive integral linear functions $l_j(x_1,\dots,x_n)$. Denote by $P(h)$ the polytope defined by the inequalities $l_j(x)\le a_j+h_j$. Finally, let $$I(f,h)= \int_{P(h)} f(x)dx, \quad S(f)= \int_{P\cap \mathbb Z^n} f(x).$$ Then for any quasipolynomial $f(x)$ (a sum of products of polynomial and exponential functions) one has $$S(f) = \prod_j Td(\partial / \partial h_j)\ I(f,h)\ |_{h_j=0}.$$

Here is how the Hirzebruch-Riemann-Roch for the sheaf $\mathcal F=\mathcal O(d)$ on $X=\mathbb P^n$ follows from the Khovanskii-Pukhlikov's version of Euler-Maclaurin's formula:

Taking $P$ to be a simplex of side $d$ and $f(x)=1$, the Khovanskii-Pukhlikov's formula gives $$h^0(\mathbb P^n, \mathcal O(d)) = \prod_{j=0}^n Td(\partial/\partial h_j) \frac{(d+h_0+\dots+h_n)^n}{n!} \ |_{h_j=0}$$ which by making a substitution $y=d+h_0+\dots+h_n$ transforms into $Td(\partial/\partial y)^{n+1} (y^n/n!)\ |_{y=d}.$

The usual Hirzebruch-Riemann-Roch, on the other hand, says that $h^0(\mathbb P^n,\mathcal O(d))$ is the coefficient of $x^n$ in the expression $Td(x)^{n+1} e^{dx}$. So why is this the same? Because $$Td(x)^{n+1} e^{dx} = Td(\partial/ \partial y)^{n+1} e^{yx}\ |_{y=d}$$ (here we used the fact that $(\partial/ \partial y)^k e^{yx} = x^k e^{yx}$) and the coefficient of $x^n$ in $e^{yx}$, expanded as a power series in $x$, is $(y^n/n!)$. QED

Now that wasn't so hard, but why isn't this written somewhere? Or am I missing a reference?

So what does this suggest conceptually about the meaning of Hirzebruch-Riemann-Roch? I think, clearly, it suggests that

1. The pushforward $$f_!:K(X)\to K(pt)=\mathbb Z, \qquad \mathcal F\mapsto \chi(\mathcal F) = h^0(F)-h^1(F)+\dots$$ between the K-groups should be considered to be the "discrete summation" of a "function" $f=f(\mathcal F)$. Indeed, for say a toric variety $X$ and an ample line bundle $\mathcal F$ we are just counting integral points in a polytope $P$. So that fits.

2. The pushforward $$f_*: A(X)_Q\to A(pt)_Q=\mathbb Q$$ between the Chow groups should be considered to be a "continuous" version, an integral. Indeed, for a cycle on $X$ its pushforward can be interpreted as, and computed by, an integral of a corresponding differential form. So this makes perfect sense as well.

So now the Riemann-Roch, = the Euler-Maclaurin for this situation, transforms the integral into the sum, by multiplying it by the differential operator given by the Todd class. This also explains why in HRR the Todd class of $T_X$ appears and not, say, of $\Omega^1_X$. The tangent bundle is the place where the derivations $\partial/\partial z$ live.

-

Last year, Leonhard Euler posted a note, Finding the sum of any series from a given general term on the arXiv. In recent years, this idea has been extended to sums over lattice approximations of convex polytopes $\Delta \cap \mathbb{Z}^n$ as shown in the other responses.

-
Euler didn't post it, because he's been dead for quite some time. This is, if I'm not mistaken, a translation into English of the original paper in which Euler derived the Euler-Maclaurin formula. –  Michael Lugo Jan 4 '10 at 16:31
Your answer brought a smile to my face. :-) –  Dan Piponi Jan 4 '10 at 17:39
Thank you for this reference. I wouldn't have thought of searching for Euler's paper on arXiv. –  VA. Jan 6 '10 at 22:14
@VA - You can actually find all of Euler's papers online at the Euler Archive: math.dartmouth.edu/~euler –  Ben Linowitz Jan 9 '10 at 17:42

Yes, this is a big area of research. I'll add some references to the ones Dmitri provides.

Here are references from a question about Moment map for toric actions:

More on the topic itself:

A series of papers on arXiv by Michèle Vergne, especially:

Also papers by Brion and Vergne, which seem to be missing from arXiv (Google Scholar, thanks to Steve).

-
When I studied this area I personally found the joint work of Brion and Vergne and the book Combinatorial Convexity and Algebraic Geometry by Ewald to be very helpful. There is also a Springer UTM called Computing the Continuous Discretely that handles a lot of the polytope stuff without invoking algebraic geometry. –  Steve Huntsman Jan 4 '10 at 14:34
@Steve: thanks, do you think you could fill in the links for them? We can make this post community wiki or you could also post a new post which I'll upvote :) –  Ilya Nikokoshev Jan 4 '10 at 15:00
Posting below in my original post –  Steve Huntsman Jan 4 '10 at 15:21

I thought I'd give a more explicit answer showing how the Todd class appears. Let $Td(x) := \frac{x}{1-e^{-x}} = -\sum_{j=0}^\infty B_j \frac{x^j}{j!}$. Now for $a,b \in \mathbb{Z}$, $z \in \mathbb{R}$, $|z| << 1$, we have that $Td(\partial_h)e^{hz} = -\sum_{j=0}^\infty B_j \frac{\partial_h^{(j)}}{j!}e^{hz} = -\sum_{j=0}^\infty B_j \frac{z^j}{j!}e^{hz} = Td(z)e^{hz}$. So

$Td(\partial_g)|_{g=0} Td(\partial_h)|_{h=0} \int_{a-g}^{b+h} e^{xz} dx$

$= Td(\partial_g)|_{g=0} Td(\partial_h)|_{h=0} \frac{e^{(b+h)z} - e^{(a-g)z}}{z}$

$= \frac{Td(z)e^{bz} - Td(-z)e^{az}}{z} = \frac{e^{bz}}{1-e^{-z}} + \frac{e^{az}}{1-e^z}$

$= \sum_{k=a}^b e^{kz}$.

It follows for suitable functions $f$ (as VA pointed out below) that $\sum_{k=a}^b f(k) = Td(\partial_g)|_{g=0} Td(\partial_h)|_{h=0} \int_{a-g}^{b+h} f(x) dx$.

As far as references:

Brion and Vergne give a good treatment of the problem. Their key paper is available at http://www.jstor.org/pss/2152855

Ewald's introduction to toric varieties takes place in the context of convex polytopes and is more concrete than others (e.g., Fulton): see http://books.google.com/books?id=bz8SfJId3BgC

[PPS--I used this work to complete a structure theory for the equilibrium hybridization thermodynamics of DNA about 7 or 8 years ago: see The Matrix Tree Theorem for Weighted Graphs.

-
David--How did you fix the TeX? –  Steve Huntsman Jan 4 '10 at 16:49
You can put a backslash in front of the underscores to escape them. –  S. Carnahan Jan 4 '10 at 17:24
I think for a general smooth function $f$ convergence is a far more delicate question than you indicate. Indeed, I think the equality does not hold for some very simple functions. But this formula with two $Td$ operators is an identity if $f$ is a hyperpolynomial. –  VA. Jan 6 '10 at 22:58
The signs in your expansion of $Td$ are wrong; the question gives the right expansion. In particular, $Td(x)$ starts with $1=B_0$, not with $-1$. Further, in the 6th line it should be $e^{az}/(1-e^z)$. –  VA. Jan 9 '10 at 17:10
Fixed the 6th line, thanks. I probably used a different convention for the Bernoullis. And I think you are correct about the convergence issue. I was basically just pasting old notes and am not current on this. Sorry. –  Steve Huntsman Jan 11 '10 at 19:07

I was about to post the same question and came across yours. I wasn't aware of the "toric" direction here that other people have referred to, but I know a pretty answer in the particular case when $X$ is the flag variety of a semi-simple algebraic group. In this case RR reduces to saying that $\chi(F)={\mathrm{const}} \int ch(F\otimes L^{-1})$ where $L$ is the square root of the canonical class and the constant is explicit. So in this case at least multiplication by Todd does amount to shift (by half-forms) as in Euler-Maclaurin formula. Furthermore, in this form the formula has a very short proof via characteristic $p$, deducing it from the fact that $Fr_*(L)=L^{p^d}$, $d=\dim(X)$.

[Well, in fact it also follows from Weyl dimension formula which of course has many other proofs, I just happen to like this char p proof.] It would be cool to have a proof of the general case along these lines. Something related has been done by Pink and Rossler, arXiv:0812.0254.

-

Historically the Euler Maclaurin formula originates from the Supplement to De Moivre's Miscellanea Analytica (1730) where the terms include the Bernoulli numbers which unfortunately diverge. Euler corrects this divergence in his 1735 paper E47 page 118 which also mentions the Euler constant which could have been calculated by comparing the second to last term of the Harmonic series with its logarithm.

-