Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

May 17, 2012

Integrating Against the Euler Characteristic

Posted by Tom Leinster

The Euler characteristic of topological spaces behaves something like a measure. For example, under suitable hypotheses,

χ(XY)=χ(X)+χ(Y)χ(XY). \chi(X \cup Y) = \chi(X) + \chi(Y) - \chi(X \cap Y).

One of the main things you can do with a measure is integrate with respect to it — or ‘against’ it, as they say.

So: what happens if you try to integrate against the Euler characteristic?

I don’t completely understand the answer myself, but I’ll explain as well as I can. Along the way, we’ll see:

  • how this train of thought helps us to define Euler characteristic
  • how it also leads to the notion of curvature.

Simple functions on the line

Let’s begin in one dimension. Our aim is to define the integral fdχ\int f \; d \chi for suitable functions f:RRf\colon \mathbf{R} \to \mathbf{R}.

Whatever we think Euler characteristic is, the Euler characteristic of a compact, nonempty interval AA should be 11. So, writing I AI_A for the indicator function (or characteristic function) of AA, we should have

I Adχ=1. \int I_A \;d \chi = 1.

Since integration is supposed to be linear, this tells us how we must integrate any finite linear combination of indicator functions of compact nonempy intervals. I’ll call these simple functions on R\mathbf{R}. So, for a simple function

f= r=1 kc rI A r, f = \sum_{r = 1}^k c_r I_{A_r},

where each A rA_r is a compact nonempty interval, we should have

fdχ= r=1 kc r. \int f \;d \chi = \sum_{r = 1}^k c_r.

Do I hear you sigh? If you’ve seen this kind of thing before, you’ll recognize the standard problem: the definition isn’t obviously consistent, since ff can be expressed as a combination of indicator functions in multiple ways, and maybe these give multiple different values for the integral. In that case, you’ll also know that the standard solution, involving common refinements, is pretty tedious work.

Happily, we can avoid it. Here’s how. For a simple function ff, put

J(f)= xR(f(x)f(x)) J(f) = \sum_{x \in \mathbf{R}} (f(x) - f(x-))

where f(x)f(x-) means lim ε0+f(xε)lim_{\varepsilon \to 0+} f(x - \varepsilon). This quantity J(f)J(f) is well-defined, linear in ff, and takes value 11 when ff is the indicator function of a compact nonempty interval. So, J(f)=c rJ(f) = \sum c_r whenever f=c rI A rf = \sum c_r I_{A_r}. We therefore put

fdχ=J(f), \int f \;d \chi = J(f),

and the consistency problem evaporates.

Let’s have some examples. What, for instance, is the integral against the Euler characteristic of this function?

The solid and empty circles indicate that f(a)=f(b)=0f(a) = f(b) = 0. So

f=3I (a,b)=3I [a,b]3I [a,a]3I [b,b] f = 3I_{(a, b)} = 3I_{[a, b]} - 3I_{[a, a]} - 3I_{[b, b]}

and

fdχ=333=3. \int f \;d\chi = 3 - 3 - 3 = -3.

Since f=3I (a,b)f = 3I_{(a, b)}, this tells us that we’re treating the Euler characteristic of the open interval (a,b)(a, b) as 1-1. That might strike you as wrong if you’re used to Euler characteristic being invariant under homotopy equivalence. But as James Propp pointed out long ago, there’s a tension between the requirement that Euler characteristic is homotopy-invariant and the requirement that it behaves like a finitely additive measure. You can’t have both at once. (See also John Baez’s excellent talk on the mysteries of counting.) Here we’re not worrying about homotopy invariance; we’re using what Propp would call ‘Euler measure’.

What about this function?

It’s not hard to see that gdχ=7\int g \;d\chi = 7, whatever the unlabelled values on the axes might happen to be. I chose the letter JJ to stand for ‘jump’: J(f)=fdχJ(f) = \int f \;d\chi is the total vertical jump occurring at jump discontinuities from the left.

One more example: what is the integral against the Euler characteristic of the following function?

Here

h=3I [a,d]+5I [a,b]+I [c,d], h = 3 I_{[a, d]} + 5 I_{[a, b]} + I_{[c, d]},

so

hdχ=3+5+1=9 \int h \;d\chi = 3 + 5 + 1 = 9

(regardless of the values of aa, bb, cc and dd). Alternatively, you can calculate hdχ\int h \;d\chi via the formula for J(f)J(f), giving 8+(43)=98 + (4 - 3) = 9 again.

More general functions on the line

Classical measure theory also involves things called ‘simple functions’ (with a different but analogous meaning). There, defining integration for simple functions is just a prelude to defining integration for a larger class of functions. Can we do something similar here, extending our integral to a larger class of functions?

We can. Indeed, the formula

xR(f(x)f(x)) \sum_{x \in \mathbf{R}} (f(x) - f(x-))

for fdχ\int f \;d\chi immediately makes sense for more than just the simple functions.

But before we charge ahead and generalize, let’s correct the ugly asymmetry you see here. In everything so far, we could equally well have used the formula

xR(f(x)f(x+)). \sum_{x \in \mathbf{R}} (f(x) - f(x+)).

It makes no difference: this is still equal to fdχ\int f \;d\chi for simple functions ff. Of course, it’s just as asymmetric. However, taking the average of the two formulas, we also have

fdχ=12 xR[f(x)+2f(x)f(x+)]. \int f \;d\chi = \frac{1}{2} \sum_{x \in \mathbf{R}} \bigl[-f(x-) + 2f(x) - f(x+)\bigr].

This is now symmetric, and therefore more likely to give us a useful definition for more general functions ff.

(Maybe you can see a hint of how curvature is going to enter the story: this looks like the expression f(x)=lim ε0f(xε)2f(x)+f(x+ε)ε 2 f''(x) = \displaystyle\lim_{\varepsilon\to 0} \frac{f(x-\varepsilon) - 2f(x) + f(x+\varepsilon)}{\varepsilon^2} for a second derivative, and second derivatives have something to do with curvature.)

So: let f:RRf\colon \mathbf{R} \to \mathbf{R} be a function such that the limits f(x)f(x-) and f(x+)f(x+) exist for all xRx \in \mathbf{R}, and are equal to f(x)f(x) for all but finitely many xRx \in \mathbf{R}. In other words, ff is continuous except for a finite number of jump discontinuities. The integral against the Euler characteristic of such a function ff is defined by the formula above:

fdχ=12 xR[f(x)+2f(x)f(x+)]. \int f \;d\chi = \frac{1}{2} \sum_{x \in \mathbf{R}} \bigl[ -f(x-) + 2f(x) - f(x+) \bigr].

Be warned: this has some properties that you might not expect of an integral. For instance, the integral of any continuous function is 00, the integral of a function that is everywhere strictly positive can be strictly negative, and changing the value of a function at a single point can change the value of the integral. On the other hand, this integral has some interesting properties too, as we’ll see when we get to higher dimensions.

Simple functions in higher dimensions

Let’s now consider functions on R n\mathbf{R}^n, for n1n \geq 1. The role of intervals will be played by convex sets. For brevity, I’ll use ‘convex’ to mean ‘compact, nonempty and convex’.

A function f:R nRf\colon \mathbf{R}^n \to \mathbf{R} is simple if it can be expressed as a finite linear combination of indicator functions of convex sets. Again, we want to ‘define’

fdχ= r=1 kc r \int f \;d\chi = \sum_{r = 1}^k c_r

whenever f= r=1 kc rI A rf = \sum_{r = 1}^k c_r I_{A_r} for some convex sets A rA_r, and again we might groan at the prospect of having to do those tedious consistency checks.

But once more, the jump functional JJ comes to the rescue. I’ll explain in the case n=2n = 2; the strategy for higher dimensions should be clear. Let f:R 2Rf\colon \mathbf{R}^2 \to \mathbf{R} be a simple function. For each xRx \in \mathbf{R}, the function

f(x,):RR f(x, -)\colon \mathbf{R} \to \mathbf{R}

is simple, and so we can define a function F:RRF\colon \mathbf{R} \to \mathbf{R} by F(x)=J(f(x,))F(x) = J(f(x, -)). This function FF, too, is simple, so we get a real number J(F)J(F). We define J(f)J(f) to be this number: J(f)=J(F)J(f) = J(F).

Thus, we have defined J(f)J(f) for every simple function ff on R 2\mathbf{R}^2. It is linear in ff, with J(1 A)=1J(1_A) = 1 whenever AA is convex. So just as in the one-dimensional case, J(f)=c rJ(f) = \sum c_r when f=c rI A rf = \sum c_r I_{A_r}. This solves the consistency problem, and fdχ=J(f)\int f \;d\chi = J(f).

I learned this from Chapter 5 of Klain and Rota’s Introduction to Geometric Probability (source of so many wonderful things). It is remarkably little effort, and is even based on a very standard technique: reducing a multivariable integral to a sequence of single-variable integrals. But it has an immediate nontrivial consequence: the definition of Euler characteristic for a large class of subsets of R n\mathbf{R}^n.

Indeed, call a subset SS of R n\mathbf{R}^n polyconvex if it can be expressed as a finite union of convex sets. For example, any picture on a black and white television is polyconvex (assuming that each pixel is convex). And quite simply, we define

χ(S)=I Sdχ. \chi(S) = \int I_S \;d\chi.

You can prove, as Klain and Rota do, that this coincides with the usual definition.

More general functions in higher dimensions, and curvature

The rough idea now is that given a function f:R nRf\colon \mathbf{R}^n \to \mathbf{R} whose discontinuities are no worse than those of a simple function, we should be able to define fdχ\int f \;d\chi by repeating verbatim the definition for simple functions.

In the one-dimensional case, we first had to deal with the pesky problem that the formula

J(f)= xR(f(x)f(x)) J(f) = \sum_{x \in \mathbf{R}} (f(x) - f(x-))

isn’t symmetric, so probably wouldn’t generalize well. To fix that, we considered the formula (f(x)f(x+))\sum (f(x) - f(x+)) obtained by reversing the orientation of the line, and then we averaged over the two orientations to get something symmetric.

In higher dimensions, the asymmetry problem can no longer be brushed aside with this algebraic flick of the wrist. In fact, some interesting geometry comes in here. This asymmetry issue, which looked like a nuisance distracting us from the main business, turns out to be exactly the reason why integration against the Euler characteristic is closely related to curvature.

Again I’ll stick to n=2n = 2, leaving higher dimensions to your imagination.

In defining J(f)J(f) for simple functions f:R 2Rf\colon \mathbf{R}^2 \to \mathbf{R}, we used the standard coordinate system on R 2\mathbf{R}^2. When ff is simple, the choice of basis does not affect the value of J(f)J(f) (which is always equal to c r\sum c_r, if f=c rI A rf = \sum c_r I_{A_r}). But for more general functions ff, it certainly does make a difference. What we should do is consider all ordered orthonormal bases of R 2\mathbf{R}^2, calculate J(f)J(f) with respect to each basis, and define fdχ\int f \;d\chi to be the average.

(You can see that this generalizes what we did for R 1\mathbf{R}^1: there we took the average of two things, and there are two orthonormal bases of R 1\mathbf{R}^1.)

I don’t want to make this post any longer by explaining exactly what, for instance, ‘average’ means. Nor will I say much about which functions ff this will be a reasonable definition for. Instead, I’ll focus on the geometric interpretation of fdχ\int f \;d\chi.

Let’s think about a function f:R 2Rf\colon \mathbf{R}^2 \to \mathbf{R} of the form gI Ag \cdot I_A, where gg is continuous and AA is convex. Thus, ff is supported on AA and continuous everywhere except perhaps on the boundary of AA, where it might jump in value as it crosses the boundary. I’ve just been reading something that talks about functions `suffering a jump discontinuity’. The suffering of ff is limited to A\partial A.

What is fdχ\int f \;d\chi? How can we understand it?

Well, fdχ\int f \;d\chi is the average over all orthonormal bases of the quantity “J(f)J(f) with respect to that basis”. So, take an orthonormal basis — a coordinate system — and let’s consider J(f)J(f).

Recall that the definition of J(f)J(f) was slicewise. For each xRx \in \mathbf{R}, we take the function f(x,):RRf(x, -)\colon \mathbf{R} \to \mathbf{R} and put F(x)=J(f(x,))F(x) = J(f(x, -)). In the picture, the value of xx shown is in the vertical shadow of AA, so F(x)F(x) is equal to f(x,y)f(x, y).

Now since ff is continuous, FF is too, except that FF has a jump discontinuity at each end of the shadow. So, J(F)=f(x 0,y 0)J(F) = f(x_0, y_0). Finally, by definition, J(f)=J(F)J(f) = J(F), and so J(f)=f(x 0,y 0)J(f) = f(x_0, y_0).

So in the end, J(f)J(f) is something really trivial:

J(f)J(f) is the value of ff at the leftmost point of AA

where ‘leftmost’ refers to the basis concerned. (I’m assuming for simplicity that the boundary of AA is smooth and contains no line segments. This isn’t crucial.)

But this isn’t the same as fdχ\int f \;d\chi. To get that, we have to average over all orthonormal bases of R 2\mathbf{R}^2. That is, we slowly rotate our coordinate axes through 360 360^\circ, at each moment recording the value of ff at the ‘leftmost’ point of AA (with respect to the current axes), then taking the mean. As we rotate, that leftmost point works itself around the whole boundary of AA, never backtracking. And here’s the important thing:

It spends more time at some boundary points than others.

To see why, consider a convex set like this:

For almost all choices of axes, the leftmost point of AA will be in one of the red parts of the boundary. Only rarely will it be elsewhere.

So as we rotate the axes, the leftmost point with respect to the axes moves quickly over parts of the boundary with low curvature, and lingers where the curvature is high. We’d therefore imagine that fdχ\int f \;d\chi would be the integral of ff over the boundary of AA with respect to some kind of curvature measure on A\partial A.

This turns out to be true. In fact,

fdχ= Afdϕ \int f \;d\chi = \int_{\partial A} f d\phi

where ϕ\phi is the angle that the tangent makes with some fixed, arbitrarily chosen reference line:

This is good, but there’s another way to put it too. When we integrate along a curve, we usually do it with respect to the arclength measure, typically written as dsd s. And the rate of change of the angle ϕ\phi per unit arclength is nothing but the classical curvature κ\kappa. That is, κ=dϕ/ds\kappa = d\phi/d s. Putting this together with the last equation, we get

fdχ= Afκds. \int f \;d\chi = \int_{\partial A} f\cdot\kappa \; d s.

So, the integral against the Euler characteristic of a function of this type is naturally expressed in terms of curvature.

You can go further down this track. If you know about intrinsic volumes, you can ask and answer the question: what does it mean to integrate against an intrinsic volume? You’ll see that each intrinsic volume corresponds to a different curvature measure; in nn dimensions, we get nn different curvature measures on the boundary of a convex set.

What I’d like to know is how much of this story is well-known. Curvature measures are extremely well-studied, and connections between curvature and Euler characteristic go back to the Gauss–Bonnet theorem at least. On the other hand, I’ve never heard anyone talking explicitly about integration against the Euler characteristic. Does anyone know where this stuff is written up?

Posted at May 17, 2012 4:29 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2528

25 Comments & 0 Trackbacks

Re: Integrating Against the Euler Characteristic

Well, what it makes me think of isn’t terribly new (I don’t suppose), except that the later formulas look like inventing a change-of-variables from the geometric measure theorem V k(C)=c n,k W:AGr kχ(CW)dμ W V_{k} (C) = c_{n,k} \int_{W : AGr_k} \chi (C \cap W) d\mu_W writing the kk-homogeneous invariant volume of polyconvex (or very smooth, or …) object CC, as an integral over an affine Grassmannian. It’s a different change-of-variables that leads to those formulas involving Second Fundamental Forms and all that. Intriguing! I will have to re-read soon.

Posted by: Jesse C. McKeown on May 17, 2012 5:48 AM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

Thanks for your comment! I had in mind to use that formula to integrate against the higher intrinsic volumes V kV_k.

In the case k=nk = n, integration against V kV_k is just integration against Lebesgue measure. In the case k=nk = n we have V 0=χV_0 = \chi, so this is exactly what we’ve been talking about. In the general case, one can use the formula you cite to reduce integration against V kV_k to integration against V 0V_0.

For example, suppose we have a function f:R 2Rf\colon \mathbf{R}^2 \to \mathbf{R} of the type discussed at the end of the post: continuous except for some jumps across the boundary of a convex set AA. What is its integral against V 1V_1? In this case V 1V_1 is just perimeter (to within a scale factor), so we are ‘integrating against perimeter’.

What we do is take a line WW, not necessarily through the origin, and consider

(f W)dχ. \int (f\mid_W) \;d\chi.

Then we take the average over all lines WW:

fdV 1=c 2,1 AGr 1((f W)dχ)dμ 1(W) \int f \;d V_1 = c_{2,1} \int_{AGr_1} \Bigl( \int (f\mid_W) \;d\chi \Bigr) d\mu_1(W)

where I’m following your notation by using AGr 1AGr_1 for the space of all lines in the plane, μ 1\mu_1 for the canonical measure on AGr 1AGr_1, and c 2,1c_{2, 1} for a positive constant (whose value will depend on conventions).

In the end, this is nothing but the integral of ff around A\partial A, taken with respect to arclength measure. So this is nothing new. But it does point the way to how to do it in higher dimensions.

Posted by: Tom Leinster on May 17, 2012 9:45 AM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

… of course, what I mean by “change of variables” I think I ought to have called “changing order of integration”, or “integration by parts”… the renovators accross the alley from me had just woken me up dropping things into their dumpster, and then I remembered.

Posted by: Jesse C. McKeown on May 17, 2012 12:51 PM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

This is very interesting! I observe that while you mention the Gauss-Bonnet theorem, one noticeable difference between that and the situation you’re describing here is that the Gauss-Bonnet theorem (and its higher-dimensional generalization) is about intrinsic curvature (the Gaussian curvature of a surface depends only on its Riemannian structure), whereas what you have here is an extrinsic curvature (the curvature of a curve depends on its embedding into the plane).

Posted by: Mike Shulman on May 17, 2012 9:04 AM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

That’s a very good point.

It makes me wonder about different uses of the word “intrinsic”. Euler characteristic, for example, is one of the “intrinsic volumes”, but here “intrinsic” means that embedding the convex set into an R n\mathbf{R}^n of higher-than-necessary dimension doesn’t change the value of the invariant.

For any nn, there are the n+1n + 1 intrinsic volumes V 0,,V nV_0, \ldots, V_n, and the fact that it’s safe to call them V kV_k rather than (say) V k (n)V^{(n)}_k is a reflection of the wise normalization chosen: if AR nA \subseteq \mathbf{R}^n and i:R nR Ni\colon \mathbf{R}^n \hookrightarrow \mathbf{R}^N is an isometry, then it’s always the case that

V k (n)(A)=V k (N)(iA). V^{(n)}_k(A) = V^{(N)}_k(i A).

That’s the reason for the word “intrinsic”. But it doesn’t seem to be quite the same usage as the more classical one that you mention.

Simon and I have this conjecture that for any convex subset AA of Euclidean space, the magnitude of AA is given by

|A|= k=0 1k!ω kV k(A) |A| = \sum_{k = 0}^\infty \frac{1}{k!\omega_k} V_k(A)

where ω k\omega_k is the volume of the unit kk-ball. If this is true then

|tA|= k=0 1k!ω kV k(A)t k |t A| = \sum_{k = 0}^\infty \frac{1}{k!\omega_k} V_k(A) t^k

whenever t>0t \gt 0, and we can therefore recover all the intrinsic volumes from the function t|tA|t \mapsto |t A|. Since the magnitude of a space XX depends purely on the structure of XX as an abstract metric space, this would imply that the intrinsic volumes are intrinsic in a stronger sense too.

Posted by: Tom Leinster on May 17, 2012 9:59 AM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

Come to think of it, I guess it’s true that if two subsets of R n\mathbf{R}^n are isometric then there’s a self-isometry of R n\mathbf{R}^n carrying one to the other. (I haven’t thought this through completely.) If so, the intrinsic volumes are metric invariants for this more direct reason.

Still, it would be useful to have a formulation of the intrinsic volumes that (i) doesn’t even appear to depend on a choice of embedding into R n\mathbf{R}^n, and (ii) makes sense for non-Euclidean spaces. That’s what the conjecture I mentioned would provide.

Posted by: Tom Leinster on May 17, 2012 11:01 AM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

Robert Ghrist ( http://www.math.upenn.edu/~ghrist/research.html ) together with Yuriy Baryashnikov are working out most of this story, and its implications for signals, radar work, and various other applications. They count target foot prints in sensor networks with Euler integration, and use Euler integral transforms for things like target recognition in radar.

(I would sign the comment, but MacGPG is failing on me)

Posted by: Mikael Vejdemo-Johansson on May 17, 2012 9:17 AM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

That’s very interesting. Thanks! From the first paper of Ghrist’s that I clicked on, I immediately see the relevance.

Posted by: Tom Leinster on May 17, 2012 10:02 AM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

Incidentally, I see that Robert Ghrist was pointing us towards integration against Euler characteristic in this related conversation last year. I didn’t pick up on that at the time.

Posted by: Tom Leinster on May 17, 2012 10:35 PM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

This is called “Euler Calculus” http://en.wikipedia.org/wiki/Euler_calculus and have a lots of applicatons
in tropical geometry, toric varieties etc.

Posted by: Nikolai Mnev on May 17, 2012 9:53 AM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

Thanks! I’m genuinely glad this has been worked out: I want to use it rather than develop it for its own sake.

Posted by: Tom Leinster on May 17, 2012 10:05 AM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

I’ve had an hour or two to check this out now, and I have a question. Am I right in understanding that the Euler calculus is principally about integer-valued functions? Section 24 of this —

Justin Curry, Robert Ghrist, Michael Robinson, Euler calculus with applications to signals and sensing, www.math.upenn.edu/~ghrist/preprints/eulertome.pdf

— says so in black and white. They write at the start of that section:

The Euler calculus, being integer-valued, has a delimited purview.

But maybe that’s only the opinion of these authors, and others think differently — which is why I’m asking.

They do then go on to look at how Euler calculus could work for R\mathbf{R}-valued functions, but it’s more tentative. (Indeed, that part of the paper is called “Toward a R\mathbf{R}-valued Euler calculus”.)

The application I’m interested in very much involves non-integer-valued functions. I’m getting the impression now that this is closer to the fringes of what’s been done.

Posted by: Tom Leinster on May 17, 2012 10:31 PM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

A minor point: being integer-valued is a distraction. You just need the function to be continuous wrt discrete topology in the range.

Posted by: ymb on May 18, 2012 4:18 AM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

Thanks, but I think I must be misunderstanding. A continuous function from a connected space (such as R n\mathbf{R}^n) into a space with the discrete topology is, of course, constant. So you must mean something that I’m not getting.

Posted by: Tom Leinster on May 20, 2012 12:04 AM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

Integrating against a universal Euler characteristic, taking values in the Grothendieck group of a suitable collection of subsets, is precisely the idea behind motivic integration. I’m not sure about curvature…

Posted by: Moshe on May 17, 2012 3:06 PM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

Ah, good. Yes.

Seeing as I never seem to find the time to sit down and learn about motivic integration and measure properly, maybe this is a good moment to find out whether what I’ve absorbed by osmosis is accurate. I’ll sketch what I think is the basic set-up, in the hope that some kind expert points out my mistakes.

We begin by distinguishing certain subsets of R n\mathbf{R}^n as “nice”. I think the official word for this is probably “tame”, or possibly “definable” or “constructible”, but as I’m not sure, I’ll just go with “nice” for now. For what I’m about to say, I need the class of nice subsets to be closed under finite unions and intersections.

(My memory is that in the long run, the right thing to do is consider nn as varying, and to take a class of subsets of R n\mathbf{R}^n for each nn. These classes should interact well; for example, the product of a nice subset of R n\mathbf{R}^n with a nice subset of R m\mathbf{R}^m should be a nice subset of R n+m\mathbf{R}^{n+m}. With appropriate axioms, such a sequence of classes of subsets is called an o-minimal structure, I think.)

We want to be able to measure nice sets, but we try to do so in as free a way as possible. (That’s “free” in the sense of “free group”.) So, we don’t require that the measure of a nice set is a real number; we simply ask that every nice set does have a measure, and that measures can be added. We also ask, naturally, that measures satisfy some measure-like axioms. I think it’s just finite additivity we want.

In practice, this means the following (I believe). We form the free commutative monoid on the set of nice subsets of R n\mathbf{R}^n, then quotient out by the relations

[AB]+[AB]=[A]+[B],  []=0 [A \cup B] + [A \cap B] = [A] + [B],     [\emptyset] = 0

where [X][X] denotes the equivalence class of XX in this quotient. Let’s call this commutative monoid M\mathbf{M}. The motivic measure of a nice set AA is just [A]M[A] \in \mathbf{M}. Or is that called the Euler characteristic of AA? I don’t know.

Actually, Moshe mentioned a Grothendieck group, so I guess all occurrences of “commutative monoid” above should be “abelian group”. I don’t see immediately why we need subtraction, but subtraction has been known to come in handy.

For motivic integration, I guess we begin by doing something basic: integrating finite Z\mathbf{Z}-linear combinations of indicator functions of nice sets. If

f= r=1 kc rI A r, f = \sum_{r=1}^k c_r I_{A_r},

where each c rc_r is an integer and each A rA_r is a nice subset of R n\mathbf{R}^n, then we must have

f= r=1 kc r[A r]M. \int f = \sum_{r = 1}^k c_r [A_r] \in \mathbf{M}.

(I guess the notation f\int f isn’t quite right; there should be something after the ff to show what kind of integration we’re doing. Is it “dχd\chi”?)

It might be that the nice sets all have Euler characteristic in some traditional numerical sense — let’s say with values in Z\mathbf{Z}, for sake of argument. If this Euler characteristic

χ:{nicesets}Z \chi\colon \{nice sets\} \to \mathbf{Z}

satisfies the inclusion-exclusion principle (that is, finite additivity), then it induces a homomorphism MZ\mathbf{M} \to \mathbf{Z}, which I’ll also call χ\chi. Then

χ(f)= r=1 kc rχ(A r), \chi\Bigl(\int f\Bigr) = \sum_{r=1}^k c_r \chi(A_r),

which is more like the integral formulas in my post.

No one reading this should assume any of it’s correct! I hope someone who knows this stuff will tell me what I’ve done wrong or what crucial things I’ve left out.

Posted by: Tom Leinster on May 17, 2012 11:08 PM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

Yes, this is essentially the idea. Usually you would like the measure to be invariant under appropriate (“measure preserving”) bijections, for example translations, so you first pass to isomorphism classes under such bijections.

You are right about monoid vs. group: it’s better to have a theory with monoids, it’s just easier to have it with groups. But you lose information: for example, in the real line, [[0,)]=[[0,1)]+[[1,)][[0,\infty)]=[[0,1)]+[[1,\infty)], and [[0,)]=[[1,)][[0,\infty)]=[[1,\infty)] (by translation) so if you have cancellation, [[0,1)][[0,1)] must by 00.

More remarks:

  • It is possible to integrate more general functions, essentially functions whose graph is a nice set. The values lie in a localisation of the Grothendieck semi-ring, though.

  • Actual motivic integration takes place in valued fields, and the measure then turns out to have essentially two “components”: one in the value group, where the theory looks essentially as you described, and the other in the Grothendieck group of algebraic varieties, which is the same kind of construction, but for nice sets in the residue field.

Posted by: Moshe on May 18, 2012 3:06 PM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

It seems like you’ve rediscovered a fair bit of the Euler calculus for yourself!

First off, you need to work with Euler characteristic with compact supports in order to get the inclusion-exclusion principle.

The integer-valued theory works very nicely for the following reason: integer-valued functions can be thought of as the image of a constructible sheaf in the Grothendieck group. Euler integration is simply the derived pushforward to a point (with compact supports), other standard operations on sheaves manifest themselves as operations on constructible functions in the euler calculus. I’ve often wondered how the to get the real-valued theory as a de-categorification.

For a more concise treatment of the real-valued theory, see Baryshnikov and Ghrist’s paper:

http://www.math.upenn.edu/~ghrist/preprints/definable.pdf

I believe it is the first appearance in the literature of such a theory. Although folklore has it that other people developed it on the side and got discouraged by the non-linearity of the integral.

However, like you observed in your ellipse example, the integral does have interesting index theory – it “sees” critical points. I’d highly recommend Brocker and Kuppe’s paper “Integral Geometry over Tame Sets” for more on this Morse-theoretic perspective, as well as proofs of Gauss-Bonnet using this language.

Also, Matthew Wright’s thesis with Rob, dealt with these Hadwiger measures that you are referring to

http://arxiv.org/abs/1203.6120

-Justin

Posted by: Justin Curry on May 17, 2012 11:38 PM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

Superb; thanks. I was reading your big paper on the train, saw the reference to Matthew Wright’s thesis, thought to myself “I’d like to see that”, and wondered how I was going to get hold of it. (Apparently I’m an old-fashioned enough person that being on a train means no internet.) So I’m glad to have the link to the arXiv paper — and 13 pages is probably better than a whole thesis, to be honest…

The non-linearity of that integral is definitely a shocker. I don’t know what to think about that.

Posted by: Tom Leinster on May 17, 2012 11:47 PM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

One more thing. For more on the motivic perspective, I’d like to recommend the following paper:

Gusein-Zade, “Integration with respect to the Euler characteristic and its applications,”; Russ. Math. Surv., 65:3,2010, 399-432.

Posted by: Justin Curry on May 17, 2012 11:47 PM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

there’s a lot to tell about this subject. in brief:
1) i found euler integration to arise from the independent works of macpherson and kashiwara on constructible sheaves in the 1970s, as popularized by schapira and viro later.
2) the sheaf-theoretic definition (the euler integral of a constructible function h over a space X is the euler characteristic of X with coefficients in a complex of sheaves F_h associated to h) is very appealing, and avoids combinatorics of jumps, etc.
3) euler integration extends to, e.g., continuous functions, with a nice relationship to stratified morse theory; the price one pays is that the euler measure splits into two poincare-dual measures, and the integral operator is nonlinear.
4) the connection to curvature can be understood through the microlocal fourier transform from sheaf theory. brocker and kuppe worked out (though, alas, without using the language of euler integrals) the appropriate gauss-bonnet theorem.
5) matthew wright’s ph.d. thesis from 2011 is on extending euler integration to the other hadwiger/intrinsic volumes.

Posted by: Robert Ghrist on May 18, 2012 4:43 AM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

Thanks!

What about distributions? I’d really like a way to differentiate the intrinsic volumes.

I guess the nonlinearity of your integral puts a very different complexion on the concept of distribution.

Posted by: Tom Leinster on May 20, 2012 12:10 AM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

Back in the 80’s when I worked for SUNY Buffalo, I was introduced to this theme by Schanuel. He published in

Schanuel, Stephen H.(1-SUNYB)
What is the length of a potato? An introduction to geometric measure theory. Categories in continuum physics (Buffalo, N.Y., 1982), 118–126,
Lecture Notes in Math., 1174, Springer, Berlin, 1986.

Posted by: Charles Frohman on May 19, 2012 3:02 PM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

I first came across this lovely paper years ago, and have been citing it enthusiastically since, but I hadn’t realized how close it came to the subject of this post until I looked at it again just now. So, thanks. It really is a great piece of work.

Posted by: Tom Leinster on May 20, 2012 12:07 AM | Permalink | Reply to this

Re: Integrating Against the Euler Characteristic

Corresponding to this notion of integration is a numerical version that can be used to compute Euler integrals for functions sampled into a grid. It’s curious because like in the examples you draw above, you need to have a notion of whether or not a point is “attached” to the left or right side of a discontinuity. So instead of an ordinary rectangular grid of samples (with each sample thought of as living on a little square) you must keep track of the value of your function on the edges between squares and at the vertices where edges meet.

I wrote some code for this a couple of years back, all based on one of Ghrist’s paper. It’s a pretty surprising way to count (simply connected) blobs.

Posted by: Dan Piponi on May 22, 2012 5:38 PM | Permalink | Reply to this

Post a New Comment