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.

February 9, 2008

Metric Spaces

Posted by John Baez

guest post by Tom Leinster

While the world goes wild for categorification (and the part that doesn’t, should!), I seem to be fixated on decategorification — or counting as it’s popularly known. And right now I’m obsessed with counting metric spaces.

We’ve talked about how you can count a category. There, counting went under other names still, ‘Euler characteristic’ and ‘cardinality’. With your mind on autopilot, you can extend this definition to enriched categories. And a metric space is a special kind of enriched category! So we obtain a definition of the cardinality of a metric space.

I’ve known for a while that this can be done, but it’s only in the last few weeks that I’ve started to see the point. Below, I explain where this idea leads: to the geometry of convex sets, to fractal dimension, and to how the world looks when you take off your glasses.

This is also a cry for help! It seems that there’s a really nice story to be told, but I’m frustratingly stuck on a couple of elementary lemmas. They’re probably the sort of thing that a bright schoolkid could settle — but they’ve defeated me.

Background: the cardinality of a category

Here I’ll whizz through a definition that some of you already know… but if you don’t know it, you don’t need to. It just provides some extra motivation for the definition of the cardinality of a metric space, which I’ll define directly anyway. If you prefer, skip ahead to the definition (‘Let AA be a finite metric space…’) a screen or so below.

Let A\mathbf{A} be a finite category (finitely many objects, finitely many arrows). Put the objects in some order: a 1,,a na_1, \ldots, a_n. Let ZZ be the n×nn \times n matrix whose (i,j)(i, j)-entry is |Hom(a i,a j)||Hom(a_i, a_j)|, the cardinality of the set of arrows from a ia_i to a ja_j. Assuming that ZZ is invertible, the cardinality of the category A\mathbf{A} is the sum of all n 2n^2 entries of Z 1Z^{-1}. (Some of you know that you can sometimes get away without assuming ZZ to be invertible, but never mind.)

It’s easy to adapt this definition to enriched categories A\mathbf{A}. For instance, suppose that A\mathbf{A} is a category enriched in finite-dimensional vector spaces (and with only finitely many objects): then simply change ‘|Hom(a i,a j)||Hom(a_i, a_j)|’ to ‘dim(Hom(a i,a j))dim(Hom(a_i, a_j))’.

In general, suppose that A\mathbf{A} is enriched in some monoidal category VV, and that we have some notion of the cardinality of objects of VV. Mindlessly parroting the definition above, we can write down the definition of the cardinality of a VV-enriched category with only finitely many objects. For the definition to behave sensibly, we probably want |XY|=|X||Y||X \otimes Y| = |X| \cdot |Y| and |I|=1|I| = 1, where X,YVX, Y \in V, vertical bars denote cardinality, and II is the unit object of VV.

And… metric spaces are enriched categories! This was pointed out by Lawvere. Take [0,][0, \infty], the set of non-negative reals with \infty adjoined. It’s an ordered set under \geq, and so becomes a category — but that’s with the reverse of the usual ordering, so that there’s one arrow xyx \to y if xyx \geq y and none otherwise. Indeed, it’s a monoidal category, with tensor product ++ and unit 00. A VV-enriched category is a set AA of ‘points’ together with, for each a,bAa, b \in A, an element Hom(a,b)=d(a,b)[0,]Hom(a, b) = d(a, b) \in [0, \infty], satisfying some axioms. A few moments’ reflection should convince you that any metric space is a VV-enriched category.

(In fact, you don’t need all the classical metric space axioms to show this, and Lawvere argues persuasively that the classical definition is wrong, but I won’t go into that.)

So it looks as if we can talk about the cardinality of a finite metric space. The only missing ingredient is a notion of the ‘cardinality’ of an element of [0,][0, \infty]. In other words, we need a way to assign a number |x||x| to every x[0,]x \in [0, \infty]! That’s not quite as trivial as it looks — I said that cardinality should turn tensor product into multiplication, which here means that |x+y|=|x||y||x + y| = |x| \cdot |y| and |0|=1|0| = 1. Assuming that cardinality takes values in the real numbers and is continuous, the only possibility is |x|=α x|x| = \alpha^x for some constant α0\alpha \geq 0. Later I’ll try to convince you of what value I think α\alpha should take. If you can guess already, I want to know how!

Mr Motivator has been and gone; here’s the definition. In it, α0\alpha \geq 0 is a constant.

Let AA be a finite metric space, with points a 1,,a na_1, \ldots, a_n and metric dd. Write ZZ for the n×nn\times n matrix whose (i,j)(i, j)-entry is α d(a i,a j)\alpha^{d(a_i, a_j)}. The cardinality |A||A| of AA is the sum of all n 2n^2 entries of Z 1Z^{-1}.

I’ll assume from now until nearly the end that ZZ is always invertible — though this is a question that has cost me much sleep and Simon Willerton much computing time.

Example  Let’s run through the case of a two-point space AA. It has points a 1a_1 and a 2a_2, distance d(a 1,a 2)=dd(a_1, a_2) = d apart. So Z=(1 α d α d 1), Z = \left( \begin{matrix} 1 &\alpha^d \\ \alpha^d &1 \end{matrix} \right), and a short calculation shows that the sum |A||A| of the entries of Z 1Z^{-1} is 2/(1+α d)2/(1 + \alpha^d). Suppose that 0<α<10 \,&lt;\, \alpha \,&lt;\, 1. Then |A||A| is ‘how many points there appear to be to someone with bad eyesight’. As dd increases from 00 to \infty, |A||A| increases from 11 to 22. If dd is small then |A||A| is close to 11: it looks as if there’s only one point. If dd is large then |A||A| is nearly 22: the points are far enough apart that you can see that there really are two of them.

This is the first piece of evidence that we should take α\alpha to be between 00 and 11. Taking different values of α\alpha in this range amounts to rescaling the metric by a constant factor, so is not tremendously significant.

(Probe your psyche with the following question: what does the formula 2/(1+α d)2/(1 + \alpha^d) remind you of? For some people it’s Fermi–Dirac statistics; for some it’s Todd classes; for others still it’s the exponential generating function for the Bernoulli numbers.)

For many months I could make nothing of this. But now I can! Read on…

Background: geometric measure theory

There’s a subject variously known as geometric measure theory, geometric probability, integral geometry, and (as a Rotary joke) continuous combinatorics. It contains, for instance, a fantastic solution to the Buffon needle problem. And it also has good things to say about cardinality.

Let’s start with a simple observation. Steve Schanuel has a paper ‘What is the length of a potato?’ in which he points out that a closed interval of length 1 centimetre is not very good as a ruler: if you put two of them end-to-end then you don’t quite get an interval of 2cm — there’s a point in the middle left over. A half-open interval would be better. Thus, the measure of the closed interval isn’t really 1cm1 cm: it’s 1cm+1point1 cm + 1 point, or 1cm 1+1cm 01 cm^1 + 1 cm^0, or simply 1cm+11 cm + 1. Similarly, a closed interval of length acma cm has length acm+1a cm + 1.

What about a closed rectangle, say [0,a]×[0,b][0, a] \times [0, b]? From a formal point of view, its measure ought to be (acm+1)×(bcm+1)=abcm 2+(a+b)cm+1. (a cm + 1) \times (b cm + 1) = a b cm^2 + (a + b) cm + 1. You can justify this formula by asking how much paint you’d need to cover the rectangle. Certainly you need to paint the abcm 2a b cm^2 in the middle. You also need to paint the boundary, which you might think would require (2a+2b)cm(2a + 2b) cm, but as you’re only painting the inside of the boundary, it’s half of that. Similarly, you have to paint 90 /360 =1/490^\circ/360^\circ = 1/4 of each of the four corner points, which requires 4×(1/4)cm 0=14 \times (1/4) cm^0 = 1 unit of paint.

In the same fashion, you can calculate the measure of a right-angled triangle, using the fact that two of them stuck together make a rectangle, and you can play the game in higher dimensions, calculating the measure of cubes and so on. Schanuel explains how to do it for a spherical potato.

A big result in this field is Hadwiger’s Theorem, nicely explained in Klain and Rota’s book Introduction to Geometric Probability. Fix a natural number nn. A subset of n\mathbb{R}^n is polyconvex if it can be expressed as a finite union of compact convex sets. Let V nV_n be the set of ‘measures’ on the polyconvex subsets of n\mathbb{R}^n. Here I don’t mean measures in the usual sense. A ‘measure’ in this sense assigns a real number |A||A| to every polyconvex A nA \subset \mathbb{R}^n, and is finitely additive: |AB|=|A|+|B||AB|. |A \cup B| = |A| + |B| - |A \cap B|. The other axioms for a measure are simple enough, and you can read them here.

Now, V nV_n is a real vector space in an obvious way. If we asked for infinite additivity, it would be one-dimensional, consisting of the multiples of Lebesgue measure. Hadwiger’s Theorem says that, in fact, dim(V n)=n+1\dim(V_n) = n + 1. Specifically, V nV_n has a basis || 0,|| 1,...,|| n |\,\,|_0, |\,\,|_1, ..., |\,\,|_n where the measure || d|\,\,|_d is dd-dimensional: writing tAt A to mean a polyconvex set AA scaled up by a factor of tt, it satisfies |tA| d=t d|A| d|t A|_d = t^d |A|_d. For instance, Eulercharacteristic,perimeter,area Euler characteristic, perimeter, area is a basis for V 2V_2. Give or take a constant factor, these are the coefficients in the formula above for the measure of a rectangle. So Hadwiger’s Theorem goes some way towards formalizing ‘potato theory’.

The point

Here’s where it all comes together. The idea is to define the cardinality of infinite metric spaces by approximating them by finite ones. This turns out to produce many of the invariants of geometric measure theory.

For example, take an interval [0,a][0, a] of length aa. Let (A k) k(A_k)_{k \in \mathbb{N}} be a sequence of finite subsets of [0,a][0, a] that converges to [0,a][0, a] in an obvious sense:

for all ε>0\varepsilon \,&gt;\, 0 there exists KK \in \mathbb{N} such that for all kKk \geq K, the ε\varepsilon-balls centred on the elements of A kA_k cover [0,a][0, a].

Theorem  The sequence (|A k|) k(|A_k|)_{k \in \mathbb{N}} of cardinalities converges to a+1a + 1.

This is just like Schanuel’s observation that a closed interval of length acma cm should have measure acm+1a cm + 1!

Recall, however, that the definition of the cardinality of a metric space depends on the choice of a constant α0\alpha \geq 0. To make the theorem true, we have to take α=e 2\alpha = e^{-2}; otherwise, the sequence of cardinalities converges to Ca+1C a + 1 for some positive constant C1C \neq 1. So from now on, α=e 2\alpha = e^{-2}.

Assuming that every metric space has cardinality, lots of good things follow. Using the fact that every compact metric space is a limit (in the Gromov–Hausdorff metric) of a sequence of finite metric spaces, it can be shown that every compact metric space has a well-defined cardinality. Products behave well with respect to cardinality, so the rectangle [0,a]×[0,b][0, a] \times [0, b] has cardinality ab+a+b+1a b + a + b + 1, and so on.

The Ancient Greeks knew that ratios are more significant than lengths. Lengths depend on the unit of measurement, but ratios don’t. So when we have a metric space AA, it’s often worth considering the whole family (tA) 0<t<(t A)_{0 &lt; t &lt; \infty} of spaces, where tAt A means AA with the metric multiplied by a factor of tt. With this in mind, let’s define for each space AA a function χ A: (0,) t |tA|. \begin{matrix} \chi_A: &(0, \infty) &\to &\mathbb{R} \\ &t &\mapsto &|t A|. \end{matrix} I’ll call χ A\chi_A the cardinality function of AA. It tells us the cardinality not only of AA, but also of all its brothers and sisters tAt A.

Examples  Let AA be a closed interval of length aa. Then χ A(t)=at+1. \chi_A(t) = a t + 1. Let AA be a closed a×ba \times b rectangle. Then χ A(t)=abt 2+(a+b)t+1, \chi_A(t) = a b t^2 + (a + b) t + 1, exactly the formula from the section on geometric measure theory, but with ‘tt’ instead of ‘cm’.

Conjecture  Let AA be a convex subset of n\mathbb{R}^n. Then χ A(t)=|A| nt n++|A| 1t+|A| 0 \chi_A(t) = |A|_n t^n + \, \cdots \, + |A|_1 t + |A|_0 where the || d|\,\,|_d’s are the measures of Hadwiger’s Theorem, suitably normalized.

The conjecture says in particular that χ A\chi_A is a polynomial and that its degree is the dimension of AA.

We can also attempt to calculate the cardinality functions of some self-similar spaces. (For this I’ll assume some plausible-seeming but unproved statements on how cardinality behaves with respect to colimits.) Taking the hoariest example, let AA be Sierpiński’s gasket. Since tAt A is the union of 33 copies of (t/2)A(t/2)A, overlapping at 33 points, we’d expect χ A(t)=3χ A(t/2)3. \chi_A(t) = 3\chi_A(t/2) - 3. Solving this gives χ A(t)=bt D+3/2 \chi_A(t) = b t^D + 3/2 where D=(log3)/(log2)D = (\log 3)/(\log 2) and bb is some other constant. Although this isn’t a polynomial, its ‘degree’ in some analytic sense is DD. And DD is the Hausdorff dimension of AA! So just as in the conjecture, the degree of χ A\chi_A is the dimension of AA.

In all these examples, the constant term is the Euler characteristic. The higher coefficients depend on the metric, but the constant term is purely topological.

In summary, the story seems to go like this. The notion of the cardinality of a category leads to the notion of the cardinality of a finite metric space, which leads to the notion of the cardinality of a compact metric space, which encompasses the most important invariants of geometric measure theory: all of the measures on real polyconvex sets, Hausdorff dimension, and maybe more.

Cry for help

All of the above depends on some elementary lemmas that I’ve been unable to prove. This has been driving me up the wall! Kind reader: now that you’ve seen where this story seems to lead, perhaps you will be moved to help.

The main unproved assumption is that every metric space has cardinality. It’s true for metric spaces with 3\leq 3 points, and Simon has tested millions of other spaces without finding a counterexample. But I can’t prove or disprove it!

I’ll state the problem in a completely elementary form, and I’ll try to give you the psychological advantage by calling it an exercise:

Exercise 1  Say that a square matrix ZZ is metric if it is symmetric, its diagonal entries are all 11, its off-diagonal entries are all in [0,1)[0, 1), and Z ijZ jkZ ikZ_{i j} Z_{j k} \leq Z_{i k} for all i,j,ki, j, k. Prove, or disprove, that every metric matrix is invertible.

Thinking of the cardinality of a finite space as how many points there appear to be to someone with bad eyesight, you’d expect spaces with points spaced more widely apart to have greater cardinality. This suggests the following.

Exercise 2  In this exercise, assume that the metric spaces involved have cardinality. Let AA be a finite metric space.

  1. Let A˜\tilde{A} be another metric space with the same set of points as AA and with d A˜(a,b)d A(a,b)d_{\tilde{A}}(a, b) \geq d_A(a, b) for all a,ba, b. Show that |A˜||A||\tilde{A}| \geq |A|.
  2. Show that |tA||A||t A| \geq |A| for all t1t \geq 1. (A special case of the previous part.)
  3. Show that if AA has nn points then 1|A|n1 \leq |A| \leq n.

These exercises are conjectures! It’s not obvious, but they’re closely related: the statements of Exercise 2 very nearly imply the statement of Exercise 1.

Simon’s tests suggest that the symmetry assumption might not be necessary to prove the conjecture in Exercise 1 or to prove that |A|n|A| \leq n in the last part of Exercise 2. He has a potential non-symmetric counterexample to the conjecture that |A|1|A| \geq 1, but isn’t sure if it’s due to a rounding error or not. I’m most concerned to settle these conjectures in the symmetric case: metric spaces in the completely classical sense.

Posted at February 9, 2008 7:18 PM UTC

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

58 Comments & 9 Trackbacks

Re: Metric Spaces

Amazing post, Tom! I hope someone does those ‘exercises’!

Tom wrote:

Probe your psyche with the following question: what does the formula 2/(1+α d)2/(1 + \alpha^d) remind you of? For some people it’s Fermi–Dirac statistics; for some it’s Todd classes; for others still it’s the exponential generating function for the Bernoulli numbers.

For what it’s worth, Alain Connes makes some cryptic remarks about Bernoulli numbers in the book Triangle of Thoughts, which suggest that all three of these things are closely linked — except maybe Bose–Einstein statistics rather than Fermi–Dirac!

The first remark goes like this: “Planck had been interested in the black body problem since 1894. Living in Berlin, he was familiar with the experiments by Rubens and Kurlbaum. In the fall of 1900, he had the amazing intuition of a function of a single variable that fit beautifully with the two types of experimental results, and reconciled Lord Rayleigh’s law with Wien’s displacement law. This function is not at all simple, and even from a purely mathematical view it contains an enormous number of hidden treasures, such as Bernoulli numbers…”

In the second remark, Marcel Schutzenberger says, “The origin of Bernoulli numbers lies in the symmetric functions of integers. They play a role in the sum of the kkth powers of integers from 11 to nn,” and Connes replies “These numbers appear in the asymptotics of x/(1exp(x))x/(1-exp(-x)), almost by definition.”

There are two more such remarks, which you can find by going to the Amazon link above and searching under ‘Bernoulli’. (I don’t usually link to sites that sell books, but this time I’ll make an exception.)

I’ve been trying to understand this stuff more deeply for years. Here are some comments designed to explain Connes’ remarks to people who know little of the history of physics, or indeed physics.

Suppose you have a system which can be in states labelled 0,1,2,0, 1, 2, \dots, and the probability of being in the nnth state is proportional to exp(nx)exp(-n x) for some parameter xx. Then the actual probability of being in the nnth state is exp(nx)/Zexp(-n x)/Z, where the normalizing factor ZZ is

Z= n=0 exp(nx)=11exp(x)Z = \sum_{n = 0}^\infty exp(-n x) = \frac{1}{1 - exp(-x)}

To physicists this is the ‘partition function of the harmonic oscillator’, deeply intertwined with ‘Bose–Einstein statistics’. The similar function for Fermi–Dirac statistics is 1+exp(x)1 + exp(-x).

If you try to Taylor expand this function

11exp(x)\frac{1}{1 - exp(-x)}

you run into a minor problem: it blows up at x=0x = 0. You can just do a Laurent expansion instead — but the easiest way to do that is do a Taylor expansion of

x1exp(x)\frac{x}{1 - exp(-x)}

and then divide by xx. This Taylor expansion turns out to be

x1exp(x)= n=0 B nx nn! \frac{x}{1 - exp(-x)} = \sum_{n = 0}^\infty B_n \frac{x^n}{n!}

where the coefficients B nB_n are called the Bernoulli numbers.

The fun then lies in finding ways to compute and understand the Bernoulli numbers. I wrote a lengthy annotated problem set about this which contains my best insights so far about what’s ‘really going on’; you can also see answers by Jeff Morton. This problem set explains why Bernoulli numbers show up when you sum

1 k++n k1^k + \cdots + n^k

In a nutshell, they’re deeply linked to the discrete analogue of integration — obtained as the inverse of the discrete analogue of differentiation.

There’s still a lot that remains mysterious to me. I don’t really know why Bernoulli numbers show up in Kervaire and Milnor’s formula for the number of smooth structures on the (4n1)(4n-1)-sphere.

More importantly, I don’t really know why the function x/(1exp(x))x/(1 - exp(-x)) is so crucial in the theory of Todd classes, and whether this is related to the partition function of the harmonic oscillator somehow. I think it is…

Anyway, it’s quite possible that none of this will help you at all. Maybe you’re secretly dealing with Fermi–Dirac statistics and dividing something by the partition function 1+exp(x)1 + exp(-x) — but if so, I sure don’t see why!

Posted by: John Baez on February 9, 2008 8:47 PM | Permalink | Reply to this

Re: Metric Spaces

We were chatting about Bernoulli numbers and species back in 2003. Something about the ordered set of unordered sets.

Posted by: David Corfield on February 9, 2008 11:52 PM | Permalink | Reply to this

Re: Metric Spaces

I asked John’s contemporary Jonathan Weitsman about this some time ago, and will presume I can quote his answer here:

Me: “I vaguely understand why x/(e^x-1) shows up in both the Euler summation formula and the Todd class. But why does it show up in the Planck distribution of black-body radiation? Is the tangent bundle radiating particles at me?”

JW: “Instead of answering your question, I’ll ask another one: Why does Td^{-1} appear in the derivative of the exponential map on a Riemannian manifold? (See for example Helgason, DGLGSS, Chapter 1, Theorem 6.5).

“Here is a more direct answer. The trace of the Hamiltonian of the Harmonic oscillator is given by Feynman-Kac as the determinant of the Laplacian on the circle. On the other hand, you could compute the path integral by the fixed point formula. The denominator you would get by Atiyah-Bott would involve the translation action of the circle on the tangent bundle of the fixed loops. But this is the same determinant that leads to Td in the index theorem (in the Atiyah-Bott form, which is the easiest one for me to understand).

“The comparison of these two approaches is at the heart of Getzler’s proof of the index theorem.”

Posted by: Allen Knutson on February 9, 2008 10:19 PM | Permalink | Reply to this

Re: Metric Spaces

Hi Tom,

This is a beautiful post. I REALLY enjoyed reading it. Thank you.

With each sentence, flashes were going off in my mind that this is related to stuff near and dear to my heart, but alas, I am cursed with the ability to “sense” something is deep without ever having the ability to see it myself. That is why it was so much fun working with Urs. I would just point in vague directions where my nose picked up something and he would see it immediately.

I’ll put some thought into your exercises, but don’t have any realistic expectation of being able to help. Just wanted to say thank you for adding a bit of beauty to this sunny southern California day.

Posted by: Eric on February 10, 2008 12:39 AM | Permalink | Reply to this

Re: Metric Spaces

Unfortunately, Exercise 1 is false. Observe that the space of metric matrices is connected (indeed, the logarithms of the coordinates cut out a convex set). Hence if Exercise 1 were true, all metric matrices would not only be invertible; they must also be positive definite. But one can easily disrupt positive definiteness by testing against a signed vector. For instance, consider a 2n×2n2n \times 2n matrix whose entries are equal to aa on the upper left and bottom right n×nn \times n blocks (except on the diagonal, where they are 11), and equal to bb on the other two blocks. This is a metric matrix whenever b 2ab<1b^2 \leq a \leq \sqrt b \lt 1. But by testing it against the vector which consists of nn 1s followed by nn -1s, we see that it ceases to be positive definite once 1+(n1)anb1 + (n-1) a \leq n b. The two conditions become compatible for n3n \geq 3, e.g. take a=1/2a=1/2 and b=2/3b=2/3. (Actually this gives an explicitly non-invertible metric matrix.)
Posted by: Terence Tao on February 10, 2008 5:59 AM | Permalink | Reply to this

Re: Metric Spaces

Terence said:

Unfortunately, Exercise 1 is false.

But all is not lost! Take the 2n×2n2n \times 2n matrix you gave with 0a,b<10\le a,b \lt 1, but don’t necessarily force it to be metric. The determinant is given by

(1)(a1) 2n2((n1)a+1+nb)((n1)a+1nb)(a-1)^{2n-2}\bigl((n-1)a+1+nb\bigr)\big((n-1)a+1-n b\big)

(at least according to maple – I haven’t checked properly). So the matrix is singular when a=1n1a=\frac{1}{n-1} and b=2nb=\frac{2}{n}. However, one can still formally compute the cardinality from the adjoint matrix and get a lovely cancellation, so that the cardinality is given by

(2)2n(n1)a+1+nb\frac{2n}{(n-1)a+1+n b}

which lies between 11 and 2n2n as one would hope!

Posted by: Simon Willerton on February 10, 2008 9:56 AM | Permalink | Reply to this

Re: Metric Spaces

A quick note – it is easy to prove that Z has the determinent you claim above. Let M be the 2n x 2n matrix, divided into n x n blocks, which is 0 in the diagonal blocks and 1 in the nondiagonal blocks. So Z=(1a)+bM+aM 2/nZ=(1-a)+b M + a M^2/n. Now, M has rank 2, and M acts on the 2-dimensional space (u,u,…,u,v,v,…,v) with eigenvalues n and -n. So the eigenvalues of M are n, -n and 0, the last with multiplicity (2n-2) and the eigenvalues of Z are (1a)+bn+an(1-a)+bn+an, (1a)bn+an(1-a)-bn+an and 1a1-a, the last with multiplicty 2n-2.

Similarly, it is easy to show that the sum of the entries of Z^{-1} is 2n/((n1)a+1+nb)2n/((n-1)a+1+nb). Let v be the vector (1,1,..,1). Then we want to compute vZ 1v Tv Z^{-1} v^T. Now, Zv T=(1+(n1)a+nb)v TZ v^T=(1+(n-1)a+nb) v^T so Z 1v T=(1+(n1)a+nb) 1v TZ^{-1} v^T=(1+(n-1)a+nb)^{-1} v^T and vZ 1v T=(1+(n1)a+nb) 1vv T=2n/(1+(n1)a+nb)v Z^{-1} v^T=(1+(n-1)a+nb)^{-1} v v^T = 2n/(1+(n-1)a+nb)

More generally, if M is any metric space with n elements and a transitive symmetry group, the cardinality of M is n/ jMd(i,j)n/\sum_{j \in M} d(i,j)

Posted by: David Speyer on February 10, 2008 7:21 PM | Permalink | Reply to this

Re: Metric Spaces

Very nice David. It’s decidedly more pleasant than my hacking away with maple.

Posted by: Simon Willerton on February 10, 2008 8:14 PM | Permalink | Reply to this

Re: Metric Spaces

Thanks, Terry! It’s fantastic to have that sorted out.

It might look as if this is a disaster, but it’s not. The conjecture of Exercise 1 — that the matrix of a metric space is always invertible — was a sufficient condition for being able to develop geometric measure theory via the cardinality of enriched categories, but it might not be a necessary one.

To explain… The shortest way to define the cardinality of a category AA is as the sum of the entries of Z 1Z^{-1}, where ZZ is the square matrix whose entries are the cardinalities of the hom-sets of AA. (This also applies to enriched categories, and in particular to metric spaces.) However, we know a couple of ways to avoid the assumption that ZZ is invertible. Given Terry’s discovery, it looks as if we’ll have to press them into action.

The first way is via ‘weightings’. Let AA be a (possibly enriched) category and ZZ its associated matrix. A weighting on AA is a column vector ww such that Zw=(1 1). Z w = \left( \begin{matrix} 1 \\ \vdots \\ 1 \end{matrix} \right). A coweighting on AA is a row vector w˜\tilde{w} such that w˜Z=(1,,1)\tilde{w}Z = (1, \ldots, 1). A category AA has cardinality if it admits both a weighting and a coweighting; its cardinality |A||A| is the sum iw i= jw˜ j\sum_i w_i = \sum_j \tilde{w}_j for any weighting ww and coweighting w˜\tilde{w}. An easy lemma shows that |A||A| is independent of the choices involved.

When ZZ is invertible, there are a unique weighting and coweighting and the cardinality is the sum of the entries of Z 1Z^{-1}. When ZZ is not invertible, there are either no weightings or infinitely many. The possibility of multiple weightings is what makes life harder, and why I hoped that Exercise 1 would be true.

For metric spaces, ZZ is symmetric and a weighting is the same as a coweighting. Hence a metric space has cardinality if it has at least one weighting; its cardinality is then the total weight iw i\sum_i w_i for any weighting ww. This notion of ‘has cardinality’ is more generous than the one in my post (that ZZ is invertible). Exercise 1 now becomes:

Exercise 1 1^\prime  Say that a square matrix ZZ is metric if it is symmetric, its diagonal entries are all in [0,1)[0, 1), and Z ijZ jkZ ikZ_{ij} Z_{jk} \leq Z_{ik} for all i,j,ki, j, k. Prove, or disprove, that (1,,1)(1, \ldots, 1) is in the row-span of every metric matrix.

Terry’s answer doesn’t settle Exercise 1 1^\prime. Indeed, the class of metric matrices that he constructs all have cardinality in this wider sense; it’s given by the same formula that Simon found. When you choose aa and bb so that ZZ is not invertible, the cardinality comes out as 1/b1/b.

If Exercise 1 1^\prime is false, this still isn’t a disaster! But it would seem to complicate things — there’d be some singularities around.

The second way of avoiding the assumption that ZZ is invertible is to use a suggestion of Clemens Berger, discussed previously. Write adj(M)adj(M) for the adjugate, or classical adjoint, of a matrix MM. If ZZ is invertible then the sum of the entries of Z 1Z^{-1} is sumofentriesofadj(Z)det(Z). \frac{sum of entries of adj(Z)}{det(Z)}. But for every ZZ there’s a rational function g(t)=sumofentriesofadj(Zt)det(Zt) g(t) = \frac{sum of entries of adj(Z - t)}{det(Z - t)} and this is well-defined at t=0t = 0 in many cases where ZZ is not invertible. You can then take g(0)g(0) to be the substitute for ‘sum of the entries of Z 1Z^{-1}’. That’s essentially what Simon did in his previous comment.

So, we have progress! Exercise 1 is false, but Exercises 1 1^\prime and 2 remain open.

Posted by: Tom Leinster on February 10, 2008 5:25 PM | Permalink | Reply to this

Re: Metric Spaces

Dear Tom, Unfortunately, Exercise 1’ is false also. The analysis I gave earlier indicates that the set of non-invertible metric matrices is an algebraic subvariety of codimension 1 inside the space of all metric matrices (it is where the determinant vanishes; this vanishing is pretty generic, and can happen well away from the boundaries of the space cut out by the triangle inequalities z ijz jkz ikz_{ij} z_{jk} \leq z_{ik}). On the other hand, the variety of matrices which are non-invertible but have (1,,1)(1,\ldots,1) in its rowspace has codimension 2 inside the affine space of symmetric matrices with 1s on the diagonal (in which the space of metric matrices form an open subset). So a generic non-invertible metric matrix will necessarily be a counterexample to Exercise 1’. One can probably cook up an explicit example by looking at perturbations of the example I described earlier; one needs to find a perturbation in which the determinant is zero, but the n1×n1n-1 \times n-1 cofactors fail to sum to zero. Any sufficiently generic perturbation that obeys the determinant-zero constraint should work for this.
Posted by: Terence Tao on February 10, 2008 11:09 PM | Permalink | Reply to this

Re: Metric Spaces

With Terry solving problems posed here and framing lecture material in terms of categories of dynamical systems at his blog, has the gulf between the two cultures been overstated?

Posted by: David Corfield on February 11, 2008 8:44 AM | Permalink | Reply to this

Re: Metric Spaces

Very interesting.

We now know that there exist ‘singularities’ in the space of metric matrices: points ZZ where neither the most simple-minded approach to cardinality nor the weighting approach returns an answer. The next step is to understand what those singularities look like.

Specifically, fix nn and a non-invertible metric matrix ZZ. There are plenty of invertible metric matrices near ZZ, since a generic metric matrix is invertible. Each one has a ‘cardinality’ — the sum of the entries of its inverse. How do the cardinalities of the invertible metric matrices near ZZ behave? There are three possibilities:

  1. their cardinalities converge towards some value at ZZ
  2. their cardinalities don’t converge at ZZ, but they do stay within some bounded interval
  3. their cardinalities don’t stay within any bounded interval.

Do we have any idea which of these might occur?

Exercise 2(3) conjectured that the cardinality stays within the interval [1,n][1, n].

Posted by: Tom Leinster on February 11, 2008 5:05 AM | Permalink | Reply to this

Re: Metric Spaces

Oh, hang on — I can answer part of that myself. Since the cardinality of a matrix is a rational function in its entries, namely sumofentriesofadj(Z)det(Z), \frac{sum of entries of adj(Z)}{\det(Z)}, (2) doesn’t happen. The question is whether any metric matrices are poles of this function.

Posted by: Tom Leinster on February 11, 2008 5:18 AM | Permalink | Reply to this

Re: Metric Spaces

By may Aesthetic, this is already one of the most Beautiful threads in n-Category Cafe history.

Hear hear. Just a random question from the dog-box concerning Exercises 1 and 1’: is there a “flow equation” for inverting a matrix? Maybe I’ve been giving too many calculus tutorials, but recall the row-echelon method for inverting a matrix AA. You write down AA on the left, and a copy of the identity matrix next to it on the right. Then you perform elementary row operations to both sides until AA is magically transformed into the identity matrix, at which point the right-hand matrix gives you A 1A^{-1}.

Is there a differential equation that implements this procedure? Some pair of equations, I guess of the form

(1)dAdt=f(A),dBdt=f(A) \frac{dA}{dt} = f(A), \quad \frac{dB}{dt} = f(A)

with the initial conditions A(0)=A,B(0)=idA(0) = A, B(0) = id, and having the property that A()=id,B()=A 1A(\infty) = id, B(\infty) = A^{-1}. If there is such a differential equation, does it represent the gradient flow lines of some interesting functional?

Posted by: Bruce Bartlett on February 11, 2008 10:05 PM | Permalink | Reply to this

Re: Metric Spaces

Life is trickier than that when considering real valued rational functions of more than one variable. Consider the rational function

2u 2v 2u 4+v 4\frac{2 u^2 v^2}{u^4+v^4}

As you approach (0,0)(0,0) in any direction, this stays in the interval [0,1][0,1], yet it does not have a well defined limit.

I am 99% sure that this problem can only arise when the zero locus of the denominator is singular at the limit point. The function det\det is singular at the matrices of corank 2 and higher, which is codimension 4, so you should be able to dodge it pretty easily. As Terry says, perturbing his example (while staying singular) will probably exhibit divergence of type (3).

Posted by: David Speyer on February 13, 2008 8:20 PM | Permalink | Reply to this

Re: Metric Spaces

Thanks, David. I realized later that I didn’t understand how rational functions of several variables behave near singularities.

Let me run through your example. Write f(u,v)=2u 2v 2u 4+v 4, f(u, v) = \frac{2 u^2 v^2}{u^4 + v^4}, which is defined for all (u,v) 2(u, v) \in \mathbb{R}^2 except (0,0)(0, 0). Since (u 2v 2) 20(u^2 - v^2)^2 \geq 0, we have u 4+v 42u 2v 2u^4 + v^4 \geq 2 u^2 v^2, so f(u,v)1f(u, v) \leq 1 for all (u,v)(u, v). Obviously f(u,v)0f(u, v) \geq 0, so f(u,v)[0,1]f(u, v) \in [0, 1] for all (u,v)(u, v). However, if we take any nonzero real λ\lambda and consider f(u,λu)f(u, \lambda u) as u0u \to 0, we find lim u0f(u,λu)=lim u02λ 2+1/λ 2=2λ 2+1/λ 2, \lim_{u \to 0} f(u, \lambda u) = \lim_{u \to 0} \frac{2}{\lambda^2 + 1/\lambda^2} = \frac{2}{\lambda^2 + 1/\lambda^2}, which, of course, depends on λ\lambda. So there’s no way to extend ff continuously to (0,0)(0, 0).

I’ve been trying to digest what Terry wrote, and I think I agree that divergence of type (3) does occur. In fact, I think I’ve got some examples to back up this claim, but I’ll check the calculations again before I post.

Posted by: Tom Leinster on February 13, 2008 11:22 PM | Permalink | Reply to this

Re: Metric Spaces

Nice post, Tom! By the way, Rota was and I am fascinated by profinite mathematics which can be used to study infinite spaces (groups or categories) via the techniques of finite spaces (groups or categories).

Posted by: Charlie Stromeyer Jr on February 10, 2008 1:28 PM | Permalink | Reply to this

Beautiful Math; Re: Metric Spaces

By may Aesthetic, this is already one of the most Besutiful threads in nN-Category Cafe history.

The Baez/ Tao / Leinster subthread alone is gorgeous.

If you enter “bernoulli numbers” in the Online Encyclopedia of Integer Sequences, you get 378 results.

I wonder if there’s a deep Physics connection to Irregular Primes, just as we have connections between primes and eigenvalues of random matrices and physical systems, and the Reimann hypothesis.

A000928 Irregular primes: p is regular if and only if the numerators of the Bernoulli numbers B_2, B_4, …, B_{p-3} (A000367) are not divisible by p.

n a(n)
1 37
2 59
3 67
4 101
5 103
6 131
7 149
8 157
9 233
10 257
11 263
12 271
13 283
14 293
15 307
16 311
17 347
18 353
19 379
20 389
21 401
22 409
23 421
24 433
25 461
26 463
27 467
28 491
29 523
30 541
31 547
32 557
33 577
34 587
35 593
36 607
37 613
38 617
39 619
40 631
41 647
42 653
43 659
44 673
45 677
46 683
47 691
48 727
49 751
50 757
51 761
52 773
53 797
54 809
55 811
56 821
57 827
58 839
59 877
60 881
61 887
62 929
63 953
64 971
65 1061
OFFSET
1,1

COMMENT
Jensen proved in 1915 that there are infinitely many irregular primes. It is not known if there are infinitely many regular primes.

“The pioneering mathematician Kummer, over the period 1847-1850, used his profound theory of cyclotomic fields to establish a certain class of primes called ‘regular’ primes. … It is known that there exist an infinity of irregular primes; in fact it is a plausible conjecture that only an asymptotic fraction 1/Sqrt(e) ~ 0.6 of all primes are regular” [Ribenboim]

Posted by: Jonathan Vos Post on February 10, 2008 5:42 PM | Permalink | Reply to this

Typos corrected; Re: Beautiful Math; Re: Metric Spaces

“may” ==> “my”

“Besutiful” ==> beautiful

“nN” ==> n

It’s so hard to proofread in the microscopic form box that I get on Firefox on my Linux PC. Sorry.

Posted by: Jonathan Vos Post on February 10, 2008 5:45 PM | Permalink | Reply to this

Re: Typos corrected; Re: Beautiful Math; Re: Metric Spaces

Jonathan wrote:

It’s so hard to proofread in the microscopic form box that I get on Firefox on my Linux PC.

This is what the ‘Preview’ feature is for. After you’ve composed your comment, you have to click ‘preview’ before you can post it. You then either get error messages or a preview of your comment, showing how it’ll look when it appears. Look at it and see if it’s right.

If you don’t like the microscopic form box in which you compose your comment, you’re in luck — since you use Firefox. You can download a plugin called Greasemonkey, which let people to write scripts to modify the behavior of websites. Then, you can download Mike Stay’s script specially made for the nn-Category Café.

You can then expand the microscopic form box simply by clicking on the lower right corner and dragging it.

Usually when people say stuff like this — “just download Zot, version 5.3 or higher, and turn on the degluxifier, and all your problems will be solved” — I decide I have something better to do with my time. But this was actually not so hard, and it worked.

Mike Stay is my grad student, so you can trust him not to have inserted viruses in the script that’ll infect your computer and make all your comments contain sentences like “What happens if we categorify this?” Honest.

But, if you prefer a script that only does this resizing thing, you can use this one on my website.

Posted by: John Baez on February 10, 2008 8:16 PM | Permalink | Reply to this

Re: Metric Spaces

Going off on a tangent (or more precisely an integral) about Bernoulli numbers, JB’s notes and Jeff Morton’s solutions have been very helpful. Falhauber’s fabulous formula relates the sum of the kth powers to an integral via the Bernoulli numbers. It is my suspicion that there are higher dimensional reasons to believe that these formulas hold. For example, that the polynomial formulas in n-choose-2 that hold for odd powers (see eg. Knuth ) must be combinatorial versions of the decomposition of various higher dimensional volumes. I think there must be scissor’s congruences between the pyramidal objects that the sum of kth powers represent and the polynomial expressions in the triangles. Here n is the number of terms that are added together.

For example, Dylan Thurston told me a proof that he, Walter Neumann and Dave Bayer worked out in 4d for the sum of cubes. The sum of cubes represents the cone o a cube, this can be decomposed as the union of two cones on two pyramids, and the square of a triangle can also be decomposed as the union of two cones on two pyramids.

Dror Bar-Natan gave a proof in the continuous case by considering the cone on a cube as the set \{ (x,y,z,w) \in [0,1]x[0,1]x[0,1]x[0,1]: x \le y,z,w \}, and then considering this as two cones on pyramids. One pyramid has z \le w and y can be anything (x is still to the left of all). The other has w \le z. The triangles times triangle has x \le y and z \le w but no relations hold between {x,y} and {z,w}.

A geometric interpretation of the Bernoulli numbers would help discover these connections.

Posted by: Scott Carter on February 10, 2008 7:15 PM | Permalink | Reply to this

Re: Metric Spaces

There’s something curious going on here. Tom Leinster, discussing his postmodern approach to geometric measure theory, ponders the cardinality of the set of two points a distance xx apart:

2/(1+e 2x) 2/(1 + e^{-2 x})

and says it reminds him of Bernoulli numbers, whose genenerating function is

x/(1e x) x /(1 - e^{-x})

This led me to chat about the Bernoulli numbers, and now Scott is talking about proving stuff about Bernoulli numbers using scissors congruences between polyhedra… which is very much all about geometric measure theory!

So, there’s a strange loop of ideas here. It could be interesting or it could be just junk, the result of too much free-association. Simulated annealing is great, but now maybe we should lower the temperature a bit.

So, Tom: you say the cardinality of two points a distance xx apart should be

2/(1+e 2x) 2/(1 + e^{-2 x})

Here’s a simple question: what coefficients do you get when you Taylor-expand this about x=0x = 0?

And here’s a more open-ended one: what do these coefficients mean?

You have a nice conjecture about how the cardinality of a convex subset of n\mathbb{R}^n changes as you rescale it by a factor of xx: you hope to get a Taylor series in xx where the coefficients are certain geometric measures showing up in Hadwiger’s Theorem.

What does Hadwiger say about nonconvex sets? What about the 2-point set?

Posted by: John Baez on February 10, 2008 9:30 PM | Permalink | Reply to this

Re: Metric Spaces

John asked me to Taylor-expand 2/(1+e 2x) 2/(1 + e^{-2x}) about x=0x=0. Since 21+e 2x=1+tanh(x), \frac{2}{1 + e^{-2x}} = 1 + \tanh(x), I can cheat and look it up. According to Wikipedia, the answer is 1+ n1B 2n4 n(4 n1)(2n)!x 2n1 1 + \sum_{n \geq 1} \frac{B_{2n} 4^n (4^n - 1)}{(2n)!} x^{2n - 1} where the B 2nB_{2n}’s are the Bernoulli numbers. (For those who haven’t met the Bernoulli numbers, I highly recommend Cartier’s paper.) And using the formula at the bottom of p.54 of Cartier’s paper, the coefficients look rather similar to the values of the Riemann ζ\zeta function at even positive integers.

John also asked:

What does Hadwiger say about nonconvex sets? What about the 2-point set?

Good questions. Hadwiger’s Theorem is phrased in terms of polyconvex sets, i.e. finite unions of compact convex sets. My conjecture was only about convex sets. This is because even for the simplest non-convex sets, it’s clearly false. For a space AA consisting of two points distance dd apart, the cardinality function χ A\chi_A is given by χ A(t)=2/(1+e 2dt) \chi_A(t) = 2/(1 + e^{-2d t}) whereas the polynomial on the right-hand side of the conjecture, given by the Hadwiger measures, is just 22. (Incidentally, the ‘Hadwiger measures’ are usually called ‘intrinsic volumes’.)

Whether Hadwiger’s Theorem is really about convex or polyconvex sets is a moot point. In the definition of ‘measure’ that I didn’t tell you, one of the conditions is continuity. A measure is a certain type of function ||:{polyconvexsets}, |\,\,|: \{polyconvex sets\} \to \mathbb{R}, so without clicking the link, you could take a guess at what continuity means: continuity with respect to the Hausdorff metric on the domain. But that’s wrong: imagine a sequence of progressively more crinkly versions of [0,1][0, 1], converging to [0,1][0, 1] itself, and consider their lengths. (I can explain that more clearly if anyone wants.) What the condition actually says is that the restriction of the measure to convex sets is continuous with respect to the Hausdorff metric.

Posted by: Tom Leinster on February 10, 2008 11:11 PM | Permalink | Reply to this

RH, pi-permian era; Re: Metric Spaces

In the Google-assic era, as opposed to when Taylorosurs walked the Earth, your cheat is valid, but needs the caveat:

“for |x| less than pi/2”

Also, your “the coefficients look rather similar to the values of the Riemann ζ function at even positive integers” is, by free groupoid free-associational Simulated annealing, related to my hunch about random matrices, RH, and systems whose energy levels are irregular primes.

And thanks, John Baez, for your useful suggestions for virus-free downloads to enhance my proofreading of my occasionally useful but sometimes annoying comments.

Posted by: Jonathan Vos Post on February 11, 2008 12:06 AM | Permalink | Reply to this

Re: Metric Spaces

Rather more can be said about 1+tanhx1 + tanh x, and this ought to be right up Jonathan Vos Post’s alley, since he seems to be very fond of integer sequences.

It’s actually a little nicer to consider its cousin 1+tanx1 + tan x, where the odd Taylor coefficients are all positive integers (whereas for 1+tanhx1 + tanh x, they alternate in sign, since the Bernoulli numbers alternate in sign).

These Taylor coefficients are called, for evident reasons, tangent numbers. Actually, they should be considered in tandem with secant numbers. These are the odd and even Taylor coefficients in the expansion

tanx+secx= n0E nx n/n!tan x + sec x = \sum_{n \geq 0} E_n x^n/n!

where the E nE_n are collectively called Euler numbers, which have been much studied by combinatorialists. A most remarkable fact is that the Euler numbers count something: E nE_n is the number of “alternating permutations” of nn elements. (A permutation, or rather a listing of the numbers 11 through nn in some order a 1,a 2,,a na_1, a_2, \ldots, a_n, is said to be alternating if a 1a_1 > a 2a_2 < a 3a_3 > ….)

For a proof, I refer to page 149 of Stanley’s Enumerative Combinatorics. Let me define E nE_n as the number of alternating permutations on nn elements. We will count the number of alternating permutations of n+1n + 1 elements in two ways. First, the number of such alternating permutations is the same as the number of “reverse alternating” permutations where a 1a_1 < a 2a_2 > a 3a_3 < …; a bijection between them is given by a in+2a ia_i \leftrightarrow n + 2 - a_i. Let’s collect them together, and call a permutation Alternating if it is either alternating or reverse alternating. Hence the number of Alternating permutations on n+1n+1 elements is 2E n+12E_{n+1}.

On the other hand, every Alternating permutation on n+1n+1 elements is determined by three pieces of data:

  • A subset SS of {2,,n+1}\{2, \ldots, n+1\} of those numbers a 1,,a_1, \ldots, which come before 1 in the permutation, and its complement S¯\bar{S} of those which come after. The number of such subsets SS with ii elements is (ni)\binom{n}{i}.
  • Writing the Alternating permutation as a 1a i1a i+2a n+1a_1 \ldots a_i 1 a_{i+2} \ldots a_{n+1} we notice that the first ii elements a ia ia_i \ldots a_i, as a permutation on SS, is alternating if we read it in reverse order (i.e., a ia 1a_i \ldots a_1 is alternating).
  • The remainder a i+2a n+1a_{i+2} \ldots a_{n+1}, as a permutation on S¯\bar{S}, is a reverse alternating permutation on nin-i elements.

From this, we derive the recurrence relation

2E n+1= 0in(ni)E iE ni.2E_{n+1} = \sum_{0 \leq i \leq n} \binom{n}{i} E_i E_{n-i}.

But now if we take the exponential generating function of the E nE_n, call it f(x)f(x), then this recurrence relation yields

2f (x)=1+f(x) 2,2f^\prime(x) = 1 + f(x)^2,

and we can easily solve this differential equation, with help from the fact that f(0)=1f(0) = 1. We then find

f(x)=tan(x2+π4)=tanx+secxf(x) = tan(\frac{x}{2} + \frac{\pi}{4}) = tan x + sec x

as desired.

More fun can be had. The Euler numbers occur at the edges of a triangle

11

0,10, 1

1,1,01, 1, 0

0,1,2,20, 1, 2, 2

5,5,4,2,05, 5, 4, 2, 0

0,5,10,14,16,160, 5, 10, 14, 16, 16

\ldots

where each row contains partial sums of the preceding row, going alternately left-to-right and right-to-left (Graham-Knuth-Patashnik, Concrete Mathematics, p. 317). (The boustrophodon pattern, a nifty word I learned from the late Max Kelly. That is, the pattern in which you’d plow a field with a team of oxen [Greek boustros = ox].)

Posted by: Todd Trimble on February 11, 2008 3:24 AM | Permalink | Reply to this

Euler numbers; related sequences; Re: Metric Spaces

It is all very beautiful.

In OEIS we have:

A000364 Euler (or secant or “Zig”) numbers: expansion of sec x.

n a(n)
0 1
1 1
2 5
3 61
4 1385
5 50521
6 2702765
7 199360981
8 19391512145
9 2404879675441
10 370371188237525
11 69348874393137901
12 15514534163557086905
13 4087072509293123892361
14 1252259641403629865468285
15 441543893249023104553682821
16 177519391579539289436664789665
17 80723299235887898062168247453281

see the OEIS page for many pretty formulae and citations.

A000111 Euler or up/down numbers: expansion of sec x + tan x. Also number of alternating permutations on n letters.

n a(n)
0 1
1 1
2 1
3 2
4 5
5 16
6 61
7 272
8 1385
9 7936
10 50521
11 353792
12 2702765
13 22368256
14 199360981
15 1903757312
16 19391512145
17 209865342976
18 2404879675441
19 29088885112832
20 370371188237525
21 4951498053124096
22 69348874393137901

EXAMPLE

Sequence starts 1,1,2,5,16,… since possibilities are {}, {A}, {AB}, {ACB, BCA}, {ACBD, ADBC, BCAD, BDAC, CDAB}, {ACBED, ADBEC, ADCEB, AEBDC, AECDB, BCAED, BDAEC, BDCEA, BEADC, BECDA, CDAEB, CDBEA, CEADB, CEBDA, DEACB, DEBCA}, etc. - Henry Bottomley, Jan 17 2001

A008282 Triangle of Euler-Bernoulli or Entringer numbers read by rows: T(n,k) is the number of down-up permutations of n+1 starting with k+1.
1, 1, 1, 1, 2, 2, 2, 4, 5, 5, 5, 10, 14, 16, 16, 16, 32, 46, 56, 61, 61, 61, 122, 178, 224, 256, 272, 272, 272, 544, 800, 1024, 1202, 1324, 1385, 1385, 1385, 2770, 4094, 5296, 6320, 7120, 7664, 7936, 7936, 7936, 15872

OFFSET
1,5

COMMENT
Triangle begins

1

1 1

1 2 2

2 4 5 5

5 10 14 16 16

16 32 46 56 61 61

Each row is constructed by forming the partial sums of the previous row, reading from the right, and repeating the final term.

In fact, to make a long anthology of stories, short, if you enter “Euler numbers” into the OEIS search engine, you get 1020 results found.

I agree with the metaphysics underlying this thread: that there are deep and umplumbed depths in the embrace between continuous and discrete, real and complex, metric spaces and Bose–Einstein statistics and Fermi–Dirac statistics, and Todd classes, and Feynman-Kac and Atiyah-Bott, and scissors congruences between polytopes, and Hadwiger’s Theorem, and Ehrhart polynomial, and toric varieties.

We may be just scratching the hypersurface, or we may be about to take a great leap into an integrated multidisciplinary new paradigm.

You guys are the pioneers. I’m just an enthusiatic student, who started to be alive again (in the terminology of Erdos) at the age of 50, after being an applied guy in the corporate and governmental salt mines.

Thank you all again for such dazzling bright light in the transfinite darkness.

Posted by: Jonathan Vos Post on February 11, 2008 4:10 AM | Permalink | Reply to this

Re: Metric Spaces

John wrote:

So, Tom: you say the cardinality of two points a distance xx apart should be

2/(1+e 2x)2/(1+e^{&#8722;2x})

Here’s a simple question: what coefficients do you get when you Taylor-expand this about x=0x=0?

Tom essentially wrote:

1+ n1B 2n4 n(4 n1)(2n)!x 2n1 1 + \sum_{n \geq 1} \frac{B_{2n} 4^n (4^n - 1)}{(2n)!} x^{2n - 1}

Great! So, we’re seeing Bernoulli numbers show up even though we don’t exactly have the classic generating function for Bernoulli numbers.

It would be very good to understand what the individual coefficients in this series mean. I’m hoping they give some detailed information that the usual Hadwiger’s Theorem neglects! For example, maybe some information about the volume of the subset of n\mathbb{R}^n consisting of all points with distance <ϵ\lt \epsilon from the set consisting of two points a distance xx apart. Or something like that.

You’ve probably seen similar ideas in discussions of geometric representation theory. People do stuff like compute the volume of the set of all points of distance <ϵ\lt \epsilon from a polytope, expand the answer as a power series in ϵ\epsilon, and see how the coefficient of ϵ k\epsilon^k is related to the kk-dimensional volume of your polytope. This idea is related to the Ehrhart polynomial, too — I forget how.

But, the above power series could be probing regimes that these standard ideas miss, since you’ve got two parameters to play with: ϵ\epsilon and xx.

The idea Scott mentioned may be relevant. Say you build a square pyramid of unit cubes in 3 dimensions, so the iith layer has i 2i^2 cubes in it. If it has nn layers, the total volume is approximately

0 ni 2di=n 3/3 \int_0^n i^2 \; d i = n^3/3

but in fact, the volume is precisely

0 ni 2=(B+n+1) 3B 33 \sum_0^n i^2 = \frac{(B + n + 1)^3 - B^3}{3}

Here I’m using a sneaky notational trick where you’re supposed to expand out (B+n+1) 3(B + n + 1)^3 the usual way, and then at the last minute reinterpret B iB^i as the iith Bernoulli number.

This formula works in any dimension — just replace 3 by some other number. So, the Bernoulli numbers show up naturally as correction terms whenever we try to approximate a ‘continuous’ pyramid by a ‘discrete’ one built from little cubes.

And, it’s not just about pyramids. Bernoulli numbers show up whenever we approximate sums by integrals.

It would be nice to understand the cardinality of the 2-point space in some way vaguely related to this. I think the Bernoulli numbers there are trying to tell us something. But what???

It seems dull to consider the volume of the subset of n\mathbb{R}^n of distance ϵ\le \epsilon from 2 points — except insofar as the volume of a ball is interesting — until those 2 points get really close together, and the balls overlap. Then computing the volume can drive you loony (or at least lensy.) Maybe some fun stuff happens.

Posted by: John Baez on February 11, 2008 12:17 AM | Permalink | Reply to this

Re: Metric Spaces

John wrote:

Ehrhart polynomial

Hey, Simon and I have just been chatting about exactly that!

Quick summary: take a polytope PP in n\mathbb{R}^n with all the vertices in n\mathbb{Z}^n. (Or you can replace n\mathbb{Z}^n by an arbitrary lattice.) For every positive integer tt there’s a polytope tPt P, obtained by scaling PP up by a factor of tt. Count the number L(P,t)L(P, t) of lattice points in tPt P; that’s a function of tt, of course. Ehrhart showed that it’s a polynomial in tt, of degree nn and with rational coefficients.

So, the obvious question: is L(P,t)L(P, t) the cardinality function of some metric space?

Posted by: Tom Leinster on February 11, 2008 12:53 AM | Permalink | Reply to this

Re: Metric Spaces

John was talking about

too much free association

Well here’s some more (after all, it is very late on Sunday evening).

One thing that I was reminded of by all this was something that goes on in toric geometry that I went to a lecutre on by Sylvain Cappell about 12 years ago but found really fascinating. I won’t say much about it because there’s undoubtably people around here with more knowledge about this than I gained in one seminar in the last century.

Anyway, the idea is something like you can count the number of integer lattice points inside a polytope in R n\R^n with integer vertices by evaluating some characteristic number of an associated toric variety. The characteristic number is where the Todd classes slip in.

A toric variety is algebraic variety on which a torus (which to algebraic geometers means (C *) r(\C^*)^r for some rr) acts. The orbits of the action can be encoded in the combinatorial structure of a polytope and its faces. So for instance, take the Riemman sphere C\C\cup \infty with zC *z\in\C^* acting multiplicatively. You get three orbits {0}\{0\}, {}\{\infty\} and the dense orbit C *\C^*. These then get encoded into an interval, with the interior corresponding to the dense orbit and the two end-points correspoding to the two zero-dimensional orbits. I guess if zC *z\in\C^* acts by z pz^p then you would get a length p+1p+1 interval with pp interior points.

I think this characteristic class approach give you some hold on the Ehrhart polynomials that John’s just mentioned a minute ago elsewhere in this thread.

Posted by: Simon Willerton on February 11, 2008 1:07 AM | Permalink | Reply to this

Re: Metric Spaces

Here’s part of how to think of that.

On the toric variety associated to a polytope, we have a symplectic form ω\omega, or more simply a hyperplane class [ω][\omega]. Then there are two integrals we can do on the toric variety XX:

exp([kω])\int \exp([k\omega]) and exp([kω])Td(X)\int \exp([k\omega]) Td(X).

The first is just the volume of the polytope PP, times k dimPk^{\dim P}. The second is the full Ehrhart polynomial. The fact that Td(X)Td(X) starts with 11 fits with the idea that the leading term when counting lattice points is the volume.

So somehow Td(X)Td(X) is there to tease the discrete out of the continuous. (Tricky of it!) The same power series arises in the Euler summation formula. I learned the following not-wholly-bogus derivation from [Concrete Mathematics].

We want to sum f(0)+f(a+1)+...+f(b)f(0) + f(a+1) + ... + f(b). So we want to hit ff with the summation operator Σ\Sigma. Now,

Σ=1/Δ\Sigma = 1 / \Delta

where Δ\Delta is the differencing operator, (Δf)(x)=f(x+1)f(x)(\Delta f)(x) = f(x+1) - f(x). That is, Δ=shift1\Delta = shift - 1. But Taylor/Maclaurin is exactly the statement that shift=exp(d/dx)shift = \exp(d/d x). Putting this together,

Σ=1/(1exp(d/dx))\Sigma = 1 / (1 - \exp(d/d x) )

but as John mentioned, this has a pole when d/dx=0d/dx = 0, whatever that means. Better to split it off as

Σ=1/(d/dx)+\Sigma = 1/(d/dx) + stuff with Bernoulli numbers

and then point out that 1/(d/dx)=1/(d/d x) = \int. So summation is integration plus correction terms.

Unfortunately, the correction term summation is almost always divergent, so one actually has to do work and find out the error term. But it works for polynomials times exponentials.

The state of the art in doing Euler summation on polytopes (not just intervals like f(0)+f(1)+...+f(b)f(0) + f(1) + ... + f(b)) is here.

Posted by: Allen Knutson on February 13, 2008 3:38 PM | Permalink | Reply to this

Re: Metric Spaces

Allen wrote about trying to invert the difference operator 1shift1 - shift:

Taylor/Maclaurin is exactly the statement that shift=exp(d/dx)shift=exp(d/d x). Putting this together,

Σ=1/(1exp(d/dx))\Sigma = 1/(1&#8722;exp(d/d x))

but as John mentioned, this has a pole when d/dx=0d/d x=0, whatever that means.

One way to make this precise is to use the spectral theorem for normal operators. This says we think of any normal operator AA as a multiplication operator

(Aψ)(k)=f(k)ψ(k)(A \psi)(k) = f(k) \psi(k)

on L 2L^2 of some measure space. Then 1/(Aλ)1/(A - \lambda) ‘blows up’ at some value of λ\lambda \in \mathbb{R} — or technically, λ\lambda is in the spectrum of AA — precisely when ff takes values arbitrarily close to λ\lambda on sets of positive measure.

In the case A=id/dxA = i d/d x, the spectral theorem boils down to the Fourier transform. So, after conjugating by the Fourier transform, the operator

Σ=1/(1exp(d/dx))\Sigma = 1/(1&#8722;exp(d/d x))

becomes the operator on L 2()L^2(\mathbb{R}) given by multiplication by

1/(1exp(ik))1/(1&#8722;exp(i k))

where kk \in \mathbb{R}. This function has a pole where k=0k = 0 — that’s the pole you’re talking about. Here kk means ‘frequency’, as in exp(ikx)exp(i k x). So, this pole says that if you try to apply Σ\Sigma to a function of frequency zero — a constant function — your eyeballs will explode.

It also has a bunch of other poles at k2πZk \in 2 \pi Z. So, your eyeballs will also explode if you try to apply Σ\Sigma to the functions exp(2πinx)exp(2\pi i n x).

We can also study this issue with less analysis using formal power series instead of L 2L^2 functions, as I did in that Bernoulli number homework. However, then we only see the pole at k=0k = 0.

(I wish I could find an online copy of that great New Yorker cartoon about “learning math on the streets”. It has a series of frames, including one of a leering ragamuffin leaning against the wall of an alley, saying “Did you know that if you divide by zero, your eyeballs will explode?” Or something like that.)

Posted by: John Baez on February 15, 2008 7:50 PM | Permalink | Reply to this

Cardinality of a group

Somewhat unrelated, but part of my own processing of the definitions Tom is using.

A group-as-a-category has one object and |G| arrows. Hence, it would have the cardinality-matrix (|G|) with inverse (1/|G|).

So it would seem that a group “actually” has cardinality 1/|G|. Is this what’s expected? What’s the intuition behind this inversion; why should that be there?

Posted by: Mikael Vejdemo Johansson on February 11, 2008 9:27 AM | Permalink | Reply to this

Re: Cardinality of a group

Various insights into this occur after a comment of mine.

Posted by: David Corfield on February 11, 2008 10:26 AM | Permalink | Reply to this

Re: Cardinality of a group

Is this what’s expected?

Yes. The |G||G| arrows of the group, regarded as a one-object category, are |G||G| automorphisms that relate the single object to itself. Hence only the fraction 1/|G|1/|G| of it is genuine, the rest is “pure gauge” as the physicists say (in case that helps anyone here).

To make this more concrete, we need to think of free actions of GG on something.

So consider the finite group GG acting freely on the finite set SS with |S||S| elements. Since GG acts freely, there are precisely |G||G| elements in SS on each GG-orbit, and hence identifying all elements in SS which are related by an action of an element in GG leads to the quotient set S/GS/G which has |S/G|=|S|/|G| |S/G| = |S|/|G| many elements. Hence the factor of 1/|G|1/|G|.

This fractional cardinality of a group is a special case of groupoid cardinality. For more on groupoid cardinality see John Baez’s Winter 2004 lecture notes, especially starting on page 53 of week 6.

An nice explanation of the relevance of free actions in the definition of category cardinality is in Tom Leinster’s article and recalled explicitly by him in this comment.

Posted by: Urs Schreiber on February 11, 2008 11:27 AM | Permalink | Reply to this

Re: Cardinality of a group

Mikael wrote:

So it would seem that a group “actually” has cardinality 1/|G|. Is this what’s expected? What’s the intuition behind this inversion; why should that be there?

I guess I was the one who invented the concept of “groupoid cardinality” which says that a group GG, regarded as a 1-object groupoid, should have cardinality 1/|G|1/|G|. There were many clues pointing in this direction already, but I’d never seen anyone crazy enough to actually come out and define the cardinality of a groupoid this way.

James Dolan and I published this idea here, and you can see the transparencies of a talk about it here, together with lots of references to related ideas. The biggest new development is Tom’s definition of the cardinality of a category, which subsumes the groupoid case.

Anyway, to answer your question: if you have a finite group GG acting on a finite set SS, it would be nice if the quotient S/GS/G had cardinality |S|/|G||S|/|G|, where |G||G| is the usual cardinality of GG as a set.

This works sometimes, like if the action of GG on SS is free, but not usually.

The solution is to work with the ‘weak quotient’ S//GS//G — a groupoid where we put an isomorphism between sSs \in S and tSt \in S for each group element gg mapping ss to tt. Then if we define the cardinality of the groupoid correctly, we get

|S//G|=|S|/|G||S//G| = |S|/|G|

In short, we get a theory of cardinality that makes sense of fractional cardinalities!

In particular, the groupoid corresponding to a group GG is just 1//G1//G, and this has cardinality 1/|G|1/|G|.

Posted by: John Baez on February 11, 2008 7:04 PM | Permalink | Reply to this

Re: Metric Spaces

I was musing about the possible connections between Hadwiger’s theorem and cardinality a while back.

Anyway, I had a crazy idea there that this might this lead to an alternative approach to quantum field theory. In particular, can we replace path integrals with something like “path cardinalities” to get finite numbers from very large path spaces without tricks like renormalisation? Sound sensible to anyone?

Posted by: Dan Piponi on February 11, 2008 9:19 PM | Permalink | Reply to this

Re: Metric Spaces

this might this lead to an alternative approach to quantum field theory. In particular, can we replace path integrals with something like “path cardinalities” […]

Sound sensible to anyone?

Yes! I was fascinated by that idea for a while now.

Notice how Tom explained how the “weighting” assigned to each object of a category which one sums up to get the full category cardinality really plays the role of a measure which arises automatically when we “integrate functors”. See his equation 6.

So the natural question is: maybe we can regard the path integral as a colimit of a functor over a “configuration space category” such that the mysterious path integral measure arises automatically from the structure of that config space categroy?

By itself this may sound like vain speculation. I was really struck by this speculation though, when I realized that in simple cases we can check that it is actually true!

We know that this is precisely how it works for Dijkgraaf-Witten theory (the finite analog of Chern-Simons theory). This I recall in Canonical measures on configuration spaces.

We also know that this is precisely how it works for the Yetter model (a 4-dimensional TQFT which can be thought of as categorified Dijkgraaf-Witten theory). This I checked in Dijkgraaf-Witten and its categorification by Martins and Porter.

Finally, we also know (or at least I think I do), that this is precisely how it works for the free particle on the discretized line. This I describe The canonical 1-particle and The canonical 1-particle, Part II.

There I show how the exponentiated lattice Laplace operator propagator arises automatically from doing the “Leinster measure path integral” over the configuration space category of paths on the latticized line.

I was rather pleased when I got that, though I never got the impression that I managed to communicate this properly.

Recently I have been trying to understand what the extension of these considerations away from finite categories and finite models like Dijkgraaf-Witten to more real-world applications like Chern-Simons would be.

Of course this doesn’t make things easier. I tried to summarize my current understanding in this comment to Integration without integration.

I’d be most happy to talk more about any or all of this. Possibly there is a gold mine to be uncovered here. But it will require work.

Posted by: Urs Schreiber on February 11, 2008 9:40 PM | Permalink | Reply to this

Re: Metric Spaces

Recently I have been trying to understand what the extension of these considerations away from finite categories and finite models like Dijkgraaf-Witten to more real-world applications like Chern-Simons would be.

What if you were looking in the wrong direction and the real world was more appropriately described by the finite models where everything already works beautifully?

Posted by: Eric on February 12, 2008 4:53 AM | Permalink | Reply to this

Metric Entropy; Re: Metric Spaces

“…the doubling dimension of a metric space is the smallest number d such that any ball of radius e can be covered by at most 2^d balls of radius e/2. In recent years, it has been popular to explore the extent to which

‘metric space of bounded doubling dimension == bounded dimensional Euclidean space’

is true. Unfortunately, there are spaces of bounded VC-dimension that do not have bounded doubling dimension.”

“Another related proxy for the ‘dimension’ of a metric space is its metric entropy: Determine the minimum number of balls of radius e needed to cover all points in a metric space. The log of this number is the metric entropy, and among other things is useful as a measure of the number of points needed to ‘cover’ a space approximately (in a dominating set sense). It’s known that the metric entropy of concept classes is closely related to their VC-dimension, (where the underlying metric is symmetric difference between the classes). I am not aware of any general result that relates the two though.”

“For more on the dizzying array of numbers used to describe metric space dimension, do read Ken Clarkson’s magnificent survey.”

Wednesday, February 13, 2008
Metric spaces, VC-dimension, and metric entropy.

Posted by: Jonathan Vos Post on February 13, 2008 4:15 PM | Permalink | Reply to this

Counterexamples

All the Exercises are now solved!

Thanks to all who have helped. Thanks especially to Terry Tao, whose solutions to Exercises 1 and 1 1^\prime pointed the way towards solving the rest.

So, Simon and I have come up with the following explicit counterexamples. In each of them, ZZ is a symmetric matrix (1 a a b b b 1 a b b b 1 b b b 1 c c 1 c 1 ) \left( \begin{matrix} 1 &a &a &b &b &b \\ &1 &a &b &b &b \\ & &1 &b &b &b \\ & & &1 &c &c \\ & & & &1 &c \\ & & & & &1 \\ \end{matrix} \right) for certain values of aa, bb and cc.

(Recall that by definition, Z ij=e 2d ijZ_{i j} = e^{-2 d_{i j}} where d ijd_{i j} is the distance from the iith point to the jjth point. For ZZ to be the matrix of a metric space, we need the diagonal entries to be 11, the off-diagonal entries to be in [0,1)[0, 1), and the triangle inequalities Z ijZ jkZ ikZ_{i j} Z_{j k} \leq Z_{i k}. Here, this says that b 2ab^2 \leq a and b 2cb^2 \leq c.)

  • Counterexample to Exercise 1 1^\prime  Take (a,b,c)=(4/9,2/3,19/34)(a, b, c) = (4/9, 2/3, 19/34). Then ZZ has no weighting.
  • Counterexample to Exercise 2(3), that the cardinality of a nonempty space is always 1\geq 1  Take (a,b,c)=(4/9,2/3,341/612)(a, b, c) = (4/9, 2/3, 341/612). Then the cardinality is 27/17-27/17.
  • Counterexample to Exercise 2(3), that the cardinality of an nn-point space is always n\leq n  Take (a,b,c)=(4/9,2/3,647/1156)(a, b, c) = (4/9, 2/3, 647/1156). Then the cardinality is 129/17>6129/17 \,&gt;\, 6.

It follows that the conjectures in Exercises 2(1) and 2(2) are also false. (I can explain why it follows if anyone wants.)

This means that there exists a finite metric space AA and a number t>1t \,&gt;\, 1 such that when you scale AA up by a factor of tt, its cardinality goes down!

Posted by: Tom Leinster on February 14, 2008 6:20 PM | Permalink | Reply to this

Re: Counterexamples

This means that there exists a finite metric space AA and a number t>1t \gt 1 such that when you scale AA up by a factor of tt, its cardinality goes down!

Could you remind me what this means now for the program you are following?

In the entry above you wrote:

In summary, the story seems to go like this. The notion of the cardinality of a category leads to the notion of the cardinality of a finite metric space, which leads to the notion of the cardinality of a compact metric space, which encompasses the most important invariants of geometric measure theory: all of the measures on real polyconvex sets, Hausdorff dimension, and maybe more.

Is this still the expectation now?

Just remind me: where are we now? :-)

Posted by: Urs Schreiber on February 14, 2008 6:52 PM | Permalink | Reply to this

Re: Counterexamples

Urs asked for a status report.

Big picture unchanged. Some local difficulties.

(Yes, local…)

Imagine the set of all compact metric spaces, and inside it the set of all finite metric spaces. These sets are themselves metric spaces, via the Gromov–Hausdorff metric. Although the Gromov–Hausdorff metric is easy enough, you don’t really need to know what it is for what follows. Just think of it as a sensible way of measuring the distance between two compact metric spaces. It behaves in an intuitive way, e.g. if you take a metric space and change all the distances slightly then you haven’t moved far in Gromov and Hausdorff’s opinion.

Now, {\{finite metric spaces}\} is dense in {\{compact metric spaces}\}, since for any compact metric space AA you can find a sequence A 0A 1 A_0 \subseteq A_1 \subseteq \cdots of finite subsets of AA with nA n\cup_n A_n dense in AA, and then lim nA n=A\lim_{n \to \infty} A_n = A in the Gromov–Hausdorff metric. (Told you it behaved intuitively.) So we can try to get at compact metric spaces via finite metric spaces.

The idea is that in this situation, we try to define the cardinality |A||A| of the compact metric space AA by |A|=lim n|A n|. |A| = \lim_{n \to \infty} |A_n|. I’d hoped that every finite metric space had cardinality. In that case, for continuity reasons that no longer matter, this definition would have been consistent: different choices of sequence (A n)(A_n) converging to AA would have given the same value of |A||A|. So every compact metric space would have had a well-defined cardinality.

However, not every finite metric space has cardinality. And there are compact — even finite — spaces for which the definition in the last paragraph is inconsistent. That is, it’s possible to find a finite metric space AA and sequences (A n)(A_n), (B n)(B_n) of finite metric spaces converging to AA such that the sequences of cardinalities (|A n|)(|A_n|) and (|B n|)(|B_n|) converge to different values.

In retrospect, it was naive of me to imagine that every compact metric space would have a well-defined cardinality. I already knew that some finite categories and compact topological spaces don’t have a well-defined Euler characteristic (at least, not in \mathbb{R}), so I should have suspected that something similar would happen here.

So the fact is that some compact metric spaces have a well-defined cardinality and some don’t. One challenge is to identify classes of compact metric spaces that do. It may be, for instance, that every convex subset of n\mathbb{R}^n has cardinality; that was part of my Conjecture.

The finite metric spaces that don’t have cardinality are rare: if you throw a dart at the space of finite metric spaces, the space you hit has cardinality with probability 1. (This is because a sufficient condition for a space to have cardinality is that the determinant of its matrix is nonzero.) So every compact metric space AA can be expressed as the limit of a sequence of finite spaces that all have cardinality: take any old sequence (A n)(A_n) as above, then give a slight nudge to any A nA_n’s that don’t have cardinality.

There’s also a result that I haven’t mentioned so far:

Theorem  Let AA be a finite metric space with nn points. Given t>0t \,&gt;\, 0, write tAt A for AA scaled up by a factor of tt. Then

  1. tAt A has cardinality for all but finitely many values of tt
  2. there exists T>0T \,&gt;\, 0 such that for tTt \geq T, the function t|tA| t \mapsto |t A| is well-defined, increasing, and takes values in [0,n][0, n].

And this brings us to inequalities. I think I’m right in saying that if AA and BB are compact convex subsets of n\mathbb{R}^n with ABA \subseteq B then |A| d|B| d|A|_d \leq |B|_d for each of the ‘Hadwiger measures’ or ‘intrinsic volumes’ || d|\,\,|_d. For instance, if n=2n = 2 then this says that for planar convex sets ABA \subseteq B,

  • (Euler characteristic of AA) \leq (Euler characteristic of BB): trivial, as the Euler characteristic of a convex set is 00 if it’s empty and 11 otherwise
  • (perimeter of AA) \leq (perimeter of BB): not so obvious
  • (area of AA) \leq (area of BB): obvious.

My idea was (and is) that inequalities such as these could be deduced from inequalities involving cardinalities of finite spaces. Which inequalities for finite spaces? Well, not the ones I conjectured in Exercise 2, because they’re false! But that’s OK — I hadn’t got any further than that vague thought, so I wasn’t depending on those particular inequalities.

Posted by: Tom Leinster on February 15, 2008 5:53 AM | Permalink | Reply to this

Cardinality of a circle

The nice people at the CRM, Barcelona, where I am now, are letting me give a couple of talks on this next week. I’m very much hoping for some thought-provoking feedback, to add to all the useful things that people have said here.

I thought I’d better come up with some more examples to use in the talk. And I’ve just found one that seems both nice and intriguing: the cardinality of a circle.

In order to regard a metric space as an enriched category, you don’t need the symmetry axiom d(a,b)=d(b,a)d(a, b) = d(b, a). Lawvere argued forcefully that this should never have been accepted as a metric space axiom anyway. Here’s an example of a non-symmetric metric space. Let A rA_r be a circle of radius rr, and let d(a,b)d(a, b) be the length of the anticlockwise arc from aa to bb. This is a perfectly good non-symmetric metric. Picture A rA_r as a circular road on which you’re only allowed to drive anticlockwise; then the metric is just the length of the shortest path.

The cardinality of the circle A rA_r can be computed, as usual, by approximating it by finite subsets, using David Speyer’s result on the cardinality of a space with a transitive isometry group. I’ll spare you the details and just tell you the answer: it’s |A r| = n0B nn!(4πr) n =1+2πr+43π 2r 21645π 4r 4+ \begin{aligned} |A_r| &= \sum_{n \geq 0} \frac{B_n}{n!} (-4 \pi r)^n \\ &= 1 + 2 \pi r + \frac{4}{3} \pi^2 r^2 - \frac{16}{45} \pi^4 r^4 + \cdots \end{aligned} where the B nB_n are the Bernoulli numbers. Or to put it slightly differently, the cardinality function of the unit circle is t1+2πt+43π 2t 21645π 4t 4+. t \,\mapsto\, 1 + 2 \pi t + \frac{4}{3} \pi^2 t^2 - \frac{16}{45} \pi^4 t^4 + \cdots.

Of course, it’s nice to see 2πr2 \pi r appearing as the 1-dimensional term — it suggests that we’re doing the right thing. (There are, after all, other metrics on the circle that we might have considered.) But what can we make of the other terms? 43π 2r 2\frac{4}{3} \pi^2 r^2 is nearly familiar, but not quite, the constant term 11 is a puzzle, and I have no clue about 1645- \frac{16}{45}.

Posted by: Tom Leinster on February 21, 2008 9:30 PM | Permalink | Reply to this

Re: Cardinality of a circle

It’s there implicitly, but I should have said it explicitly: the cardinality of a circle of radius rr is 4πr1e 4πr. \frac{4\pi r}{1 - e^{-4\pi r}}.

Posted by: Tom Leinster on February 22, 2008 12:14 AM | Permalink | Reply to this

Re: Cardinality of a circle

Is there something more puzzling to the constant term 1 than that the cardinality of a single point is 1?

Posted by: David Corfield on February 22, 2008 10:01 AM | Permalink | Reply to this

Re: Cardinality of a circle

Are you thinking that the constant term is what you get when you take rr to be 00, which should therefore be the cardinality of a circle of radius 00, which is a point?

I’m not sure that this is a sound general principle. Other things suggest that the constant term should be the Euler characteristic. I know that’s not always true, e.g. for a 2-point space, but in my original post I calculated the cardinality function of Sierpiński’s gasket and got a constant term of 3/23/2, which is its Euler characteristic.

Posted by: Tom Leinster on February 22, 2008 2:05 PM | Permalink | Reply to this

Re: Cardinality of a circle

Isn’t it just a case of your ‘how many points there appear to be to someone with bad eyesight’?

Or to put it another way, for any nn points approaching each other, their ZZ matrix tends to the one with 1 in every entry.

And although noninvertible, there’s a weighting which gives a cardinality of 1.

This matrix is the same as that for a codiscrete groupoid.

Posted by: David Corfield on February 22, 2008 2:47 PM | Permalink | Reply to this

Re: Cardinality of a circle

Yes, I know what you mean. From the point of view you describe, the constant term should always be 11 for a bounded metric space.

However, another point of view — with Schanuel’s ideas and Hadwiger’s Theorem in mind — suggests that the constant term should be the Euler characteristic.

There’s obviously a conflict here, and I don’t know how to resolve it.

Posted by: Tom Leinster on February 22, 2008 3:35 PM | Permalink | Reply to this

Re: Cardinality of a circle

Tom,

I don’t see that the ‘radius’ of a circle has any implicit meaning. You’re taking a metric on the real-line and quotienting out by a lattice. I don’t think you are embedding this into Euclidean space at any point. If the abstract circle were embedded in some non-flat space such as a sphere then it would have a different radius.

For example the equator of a unit 2-sphere has circumference 2π2\pi and radius (ie distance from the pole) π/2\pi/2, which is greater than 1: so the radius is greater than you expect.

It would be therefore more meaningful to give your formulas in terms of the circumference (that is ‘length’) of the circle. This would give the cardinality of a circle of length aa as

(1)2a1e 2a.\frac{2a}{1-e^{-2a}}.

Hmmm. Now that looks familiar….

Do you know what you get if you take the symmetric metric on the circle of length aa?

Posted by: Simon Willerton on February 22, 2008 11:33 AM | Permalink | Reply to this

Re: Cardinality of a circle

Er, to answer my own question, using David Speyer’s formula and some help from maple, I get that the cardinality of the length aa circle with the usual metric on it is

(1)ae ae a1.\frac{a e^a}{e^a-1}.

There are many observations I could make about these formulas for various values of aa, but I should maybe digest things a little first.

Posted by: Simon Willerton on February 22, 2008 1:32 PM | Permalink | Reply to this

Re: Cardinality of a circle

Maybe I’ve digested things a smidgen more than I had yesterday, so here’s some thoughts.

Firstly I’ll sumarise what seems to be the picture for the cardinality of lines and circles of length aa.

(1) line circle symmetric a+1 a1e a non-symmetric 2a+1 2a1e 2a \array{\arrayopts{\collines{solid} \rowlines{solid}} & line & circle\\ symmetric & a+1 & \frac{a}{1-e^{-a}}\\ \text{non-symmetric} & 2a+1 & \frac{2a}{1-e^{-2a}} }

You can then make the immediate observation that the cardinality of the non-symmetric thing is the cardinality of the symmetric thing of twice the length. I have no idea why.

Secondly we can try to think about the Euler characteristic and constant term. Let’s denote by C aC_a the circle of length (i.e. circumference) aa with its usual (symmetric) metric. I think an important thing to note is that the cardinality is not a polynomial in aa, so it seems different to the Hadwiger/Schanuel picture. I don’t know the right way to say this, but the power-series expansion only makes sense sense near a=0a=0, by which I mean it is giving misleading information for large aa.

For small aa, the power-series expansion gives |C a|1+a/2|C_a|\sim 1 + a/2. This is consistent with a very small circle looking point-like and having Euler characteristic 1. As with Tom, I have no idea why the linear term should be half what you might expect.

However, for large aa you have |C a|a|C_a|\sim a, by which I mean the precise statement that |C a|a0|C_a|-a \to 0 as aa\to\infty. This has no constant term and is consistent with circles having zero Euler characteristic. Furthermore, the linear term is exactly what you would expect, namely the length of the circle.

Posted by: Simon Willerton on February 23, 2008 3:07 PM | Permalink | Reply to this

Re: Metric Spaces

Hi Tom,

here is a belated question:

you had originally motivated cardinality of a category from colimits.

Now that enrichment and metrics get into the game, is there a chance you could give an analogous kind of motivation of the resulting notion of cardinality in terms of weighted colimits aka indexed colimits aka coends?

I am asking just based on a gut feeling: the metric should serve to define a measure with which to weight a sum, and the enriched categorical version of weighted sums is indexed colimits/coends, as John has explained so very nicely here.

Posted by: Urs Schreiber on March 28, 2008 7:03 PM | Permalink | Reply to this

Re: Metric Spaces

Hi Urs,

This is just to let you know that I did see your question… and I haven’t got much to say. I thought about it a bit, but none of my thoughts were interesting.

My original reason for getting into the cardinality of ordinary categories was to do with colimits of finite sets. The analogue for VV-categories would be to consider (weighted?) colimits of VV-objects. In the case V=[0,]V = [0, \infty], colimits in VV are just infima, and I can’t see any kind of non-trivial analogue of what I was doing for ordinary categories. Perhaps I’m not thinking clearly, or perhaps there’s really nothing here.

Posted by: Tom Leinster on March 31, 2008 10:13 PM | Permalink | Reply to this

Re: Metric Spaces

Tom,

thanks a lot for the reply!

Maybe we could actually stay within the context of just plain Set-enrichment for a moment, then, and reconsider my question there, from the following point:

I noticed that there is a trivial though conceptually nicely pleasing (to me, at least) possibility to formalize my way of thinking of the way you conceived category cardinality in terms of a canonical measure:

when we are working just Set-enriched we are entitled to regard the low-brow colimit

colim XF colim_X F

as a coend

X(ΔI)F \int^X (\Delta I) \cdot F

(I think), where ΔI:X opSet\Delta I : X^{op} \to Set is the constant functor at the tensor unit, i.e. at the singleton set.

(My notation is probably bad, I hope you know what I mean.)

In general ΔI\Delta I could be replaced by a more interesting functor, which would then play the role of a measure as John explained so nicely here.

So from this point of view, we notice that on every category there is in fact a canonical measure: the one which just weights every object by the tensor unit.

And remarkably (if we allow ourselves to remark such trivialities) this “canonical measure” is considerably more interesting than the “canonical measure” on any set given by the constant function with value 1 on each element: the “canonical measure” actually does induce a nontrivial weighting, which in a special case at least (“good functors”) is the “Leinster weighting” , the one which you define category cardiality with.

So then here is another question:

is there a good way to generalize your formula (6) here from colimits to more general coends in the Set-enriched context?

As you can maybe deduce from my questions, I am trying to get a better feeling for the various flavors of “categorical version of weighted sum/integral” which are floating around here:

there is weighting induced by the connectedness structure of the domain category itself, and there is weighting induced “by hand”. And there is a way to talk about metrics on categories.

How could all that be nicely related?

Posted by: Urs Schreiber on March 31, 2008 10:47 PM | Permalink | Reply to this
Read the post News on Measures on Groupoids?
Weblog: The n-Category Café
Excerpt: Benjamin Bahr apparently thought about measures on groupoids of connections.
Tracked: July 17, 2008 10:05 AM
Read the post Entropy, Diversity and Cardinality (Part 1)
Weblog: The n-Category Café
Excerpt: Entropy in relation to biodiversity and categories
Tracked: October 16, 2008 9:17 AM

Re: Metric Spaces

Tom Leinster wrote:

“In all these examples, the constant term is the Euler characteristic. The higher coefficients depend on the metric, but the constant term is purely topological.”

On the other hand, Urs said that he expects that the Feynman integral itself should be computed in the spirit of this categorified measure theory, using some sort of inner homs between transport functors (for sigma-models). Now if one looks at Feynman integrals, they involve exponential kernel, and one can try to do the steepest descent method (stationary phase approximation) to evaluate quasiclassical approximation of them. The first term is typically constructed using Bott etc. localization formula and this is how geometrically one bumps into the Euler class. One can study further quantum corrections; normally WKB is approached differently and has its own rich geometry (Maslov indices, Stokes phenomenon etc.). The accident of nature is that for Wess Zumino model (hence Chern Simons) the full quantum corrections yield 1/2 factor correction to the quasiclassical term. Thus the finite group model, CS and WZNW and variants could give too simple intuition for general case. Also for A-model one should beware of some simplifying phenomena (unlike the earlier arguments, I can not back up with arguments the last sentence, I just recall impression from some explanations of Nikita Nekrasov). Finally, as counting for orbifolds is concerned, the localization arguments for Feynman integral were intuition behind some work of Lupercio and Uribe with topological consequences.

Now I think there is a connection to the business of Bernoulli numbers. Namely, one can look more general quantization problem in the spirit of BV quantization for nonlinear sigma model of Cattaneo and Felder. I heard some lectures of Tamarkin where in terms of D-modules he explained the geometry of singularities and derived version of symplectic reduction related to those models (both A- and B- model can appear as reductions). He wrote a difficult paper on BV renormalization, mainly for free theory in 4d, but had on paper a version for Poisson sigma model which was supposed to appear in the next paper but he abandoned it. Anyway, doing quantization in his picture amounts to do some business with homotopical resolutions
(hence it is like other forms of BV quite close to our business with Lie infinity integration), and other approaches (Costello etc.) do more or less the same.
Now it is known that Cattaneo-Felder model is actually the theory for which Feynman diagram expansion gives the Kontsevich’s formula for deformation quantization. So quantizing via Feynman integral or BV or deformation quantization should give the same answer, so this is just the restatement of what Urs says is that he wants to redefine Feynman integrals in terms related to inner homs, infinity integration and all that. The connection is kind of already present in some instances.

Now what Bernoulli numbers have to do with
Kontsevich formula for deformation quantization. Well, in works of Dror-Bar Natan and others, one can see many relations between the diagrams appearing in Kontsevich quantization and PBW formula. The original paper is of course

M. Kontsevich, Deformation quantization of Poisson manifolds, Lett.Math.Phys. 66 (2003) 157-216, q-alg/9709040

I myself better understand one very special case, and that is the case of linear Poisson structures. In that case, Kontsevich has found a relation between his quantization and Duflo formula in Lie theory; which involves square root of Todd class! Now Caldararu compared this with the work of Nikita Markarian and wrote a paper with deeper understanding of the issue. On the other hand, Kathotia has found that one can neglect a subclass of diagrams entering the Kontsevich quantization formula, and what one gets is the so-called PBW quantization which involves Todd class without square root. I was involved in a project starting with our paper

N. Durov et al. J. Alg. 309 (2007) 318-359 and math.RT/0604096

studying the appearance of the “universal formula” (involving Bernoulli numbers) for star products over any field containing rational numbers (and this work has continuations). Now here is a simple punch line: this kind of quantization (appearance of Bernoulli numbers) is related to exponentiating Lie algebra to a Lie group, namely realizing Lie algebra as the vector fields in the neighborhood of unit element and expressed in coordinates given by exponential map! From other point of view, these vector fields are dual to the components of the Maurer-Cartan form, hence the formula with Bernoulli numbers is just providing a solution to the Maurer-Cartan equation:

cf. S. Helgason: Differential geomety, Lie groups and symmetric spaces.

This is the way Lie was looking at this subject in his letter in 1874 when he discovered Lie algebras, by expanding to the second order the action of a Lie group of transformations on itself (on or more general manifold) and writing the equations for flows in terms of Lie structure constants which were the coefficients in his expansion (modern account of this letter is within the historical appendix of N. Bourbaki, Lie algebras and Lie groups, vol 1).

Now this appearance of Bernoulli numbers
in Lie theory (and euivalently in linear part of the Hausdorf (BCH) formula)
generalizes to all deformation problems! Not only because of Maurer-Cartan but more specifically, work of Ziv-Ran (lie atoms) and then in better version by Merkulov (formal homogeneous spaces generalizing above picture for groups) shown that in general one can indeed write what they call Bernoulli-Jacobi resolution for any deformation problem written in terms of dg-Lie algebras.

S. A. Merkulov, Operad of formal homogeneous spaces and Bernoulli numbers, Algebra and Number Theory, Vol. 2 (2008), No. 4, 407-433, arXiv:0708.0891

This explains appearance of the formulas with Bernoulli numbers in various instances, for example in the work of Morgan, Sullivan, Deligne on minimal models for Kaehler manifolds and so on.

In Lie theory, one can of course, use other charts, not the exponential chart, what amounts to choice of ‘orderings’ in the treatment of quantization (Weyl ordering corresponding to Bernoulli numbers). In the case of linear Poisson structures I now study some of the alternative orderings where interesting corrected exponential formulas appear among the rest.

I would also like to give a small unrelated comment to the statement about the relation of exponentiating d/dx to get finite difference operator. Generalizations of the arguments in that comment are related to numerous techniques in approximation theory involving Bernoulli numbers, Bernoulli polynomials and Euler numbers; maybe somebody could put several entries in nlab about those.

Posted by: Zoran Skoda on March 17, 2009 12:36 AM | Permalink | Reply to this

Re: Metric Spaces

Zoran’s quote

Tom Leinster wrote:

“In all these examples, the constant term is the Euler characteristic. The higher coefficients depend on the metric, but the constant term is purely topological.”

made me go back to Tom’s original statement above, about the expansion of

t|tA| t \mapsto |t A|

in powers of tt. It’s striking how reminiscent this is of heat kernel expansion.

(Possibly this was mentioned and discussed before in one of our threads on category measure, but I don’t recall it right now.)

See for instance slide 8 here where the first three coefficients of the heat kernel expansion for the standard Laplace operator on a domain Ω\Omega in 2\mathbb{R}^2 is recalled:

the constant coefficient is proportional to the Euler characteristic of Ω\Omega;

the next coefficient is proportional to the length of the boundary of Ω\Omega;

the next coefficients is proportional to the area of Ω\Omega

(both length and area measured with respect to the standard metric on 2\mathbb{R}^2).

Posted by: Urs Schreiber on March 17, 2009 11:09 AM | Permalink | Reply to this

Re: Metric Spaces

This is brilliant Urs (and Zoran)! This is what I’ve been trying to do for the last week - try and connect Tom’s notion of cardinality with heat kernels, zeta functions (it turns out there is both a “classical” and a “quantum” zeta function of a graph!), determinant of the Laplacian — that kind of stuff.

But I’m confused though. With the heat kernels, we can really think of that parameter tt as ‘time’, and we’re trying to understand how the total heat content of our manifold changes with time. In Tom’s setup, tt is a scaling parameter which scales the entire space. What is the connection here?

Let’s see. Suppose we look at some fixed small time, well darn it let’s just set t=1t = 1. The expansion of the heat content says:

(1)H(t=1)Area(Ω)Length(Ω)+Euler char(Ω)+ H(t=1) \sim \text{Area}(\Omega) - \text{Length}(\partial \Omega) + \text{Euler char}(\Omega) + \cdots

So apparantly scaling up our domain Ω\Omega by a factor of λ\lambda will result in:

(2)H λ(t=1)λ 2Area(Ω)λLength(Ω)+Euler char(Ω)+ H_\lambda (t = 1) \sim \lambda^2 \text{Area}(\Omega) - \lambda \text{Length}(\partial \Omega) + \text{Euler char}(\Omega) + \cdots

Mmm. No doubt I’ve just said something completely trivial.

Posted by: Bruce Bartlett on March 18, 2009 2:56 PM | Permalink | Reply to this

Re: Metric Spaces

It is usually helpful (for me anyway) when thinking about heat-related stuff, to pass to the discrete world, where heat dynamics (diffusion) is nicely encapsulated in the discrete calculus on a binary tree. See for example,

Financial Modelling Using Discrete Stochastic Calculus

which could just as well have been called “Heat Modelling Using Discrete Stochastic Calculus”. Equation (5.10) contains the heat equation in disguise, but looks more familiar when recast in Equation (5.16).

On a binary tree, there IS a nice relationship between time and the size of the space. With each tick of the clock, the space gets one node larger so that

SizeTime.Size \propto Time.

I’m not sure if that helps with anything though.

Somewhere here, I tried to work out some relations between time and the Leinster measure for a binary tree, but flailed around and eventually got distracted with other things.

PS: If anyone is interested, I made the (well known) relation between the finance and heat dynamics explicit here:

Black-Scholes and Schrodinger

and here

Gauge Transforming Black-Scholes

Posted by: Eric on March 18, 2009 8:15 PM | Permalink | Reply to this
Read the post More Magnitude of Metric Spaces and Problems with Penguins
Weblog: The n-Category Café
Excerpt: Learn about the tenuous link between emperor penguins and the magnitude of metric spaces.
Tracked: October 11, 2009 11:09 PM
Read the post The 1000th Post on the n-Category Café
Weblog: The n-Category Café
Excerpt: Meet our new hosts: Alex Hoffnung, Tom Leinster, Mike Shulman and Simon Willerton!
Tracked: November 13, 2009 3:31 AM
Read the post On the Magnitude of Spheres, Surfaces and Other Homogeneous Spaces
Weblog: The n-Category Café
Excerpt: See the details of a new paper on the magnitude of metric spaces.
Tracked: April 21, 2010 8:25 AM
Read the post Magnitude of Metric Spaces: A Roundup
Weblog: The n-Category Café
Excerpt: Resources on magnitude of metric spaces.
Tracked: January 10, 2011 3:59 PM
Read the post The Spread of a Metric Space
Weblog: The n-Category Café
Excerpt: Read how this notion of size for metric spaces has some interesting properties.
Tracked: September 6, 2012 11:43 AM
Read the post An Adventure in Analysis
Weblog: The n-Category Café
Excerpt: How a problem about magnitude of metric spaces was solved.
Tracked: October 30, 2012 8:39 PM
Read the post Whitney Twists
Weblog: The n-Category Café
Excerpt: Q. Is the magnitude of a graph invariant under Whitney twists? A. Sometimes.
Tracked: July 7, 2013 7:36 AM

Post a New Comment