Metric Spaces

February 9, 2008

Posted by John Baez

$MathML-enabled post (click for more details).$

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.

$MathML-enabled post (click for more details).$

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 $A$ be a finite metric space…’) a screen or so below.

Let $A$ be a finite category (finitely many objects, finitely many arrows). Put the objects in some order: $a_{1}, \dots, a_{n}$ . Let $Z$ be the $n \times n$ matrix whose $(i, j)$ -entry is $∣ Hom (a_{i}, a_{j}) ∣$ , the cardinality of the set of arrows from $a_{i}$ to $a_{j}$ . Assuming that $Z$ is invertible, the cardinality of the category $A$ is the sum of all $n^{2}$ entries of $Z^{- 1}$ . (Some of you know that you can sometimes get away without assuming $Z$ to be invertible, but never mind.)

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

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

And… metric spaces are enriched categories! This was pointed out by Lawvere. Take $[0, ∞]$ , the set of non-negative reals with $∞$ 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 $x \to y$ if $x \geq y$ and none otherwise. Indeed, it’s a monoidal category, with tensor product $+$ and unit $0$ . A $V$ -enriched category is a set $A$ of ‘points’ together with, for each $a, b \in A$ , an element $Hom (a, b) = d (a, b) \in [0, ∞]$ , satisfying some axioms. A few moments’ reflection should convince you that any metric space is a $V$ -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, ∞]$ . In other words, we need a way to assign a number $∣ x ∣$ to every $x \in [0, ∞]$ ! 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 ∣ \cdot ∣ y ∣$ and $∣ 0 ∣ = 1$ . Assuming that cardinality takes values in the real numbers and is continuous, the only possibility is $∣ x ∣ = α^{x}$ for some constant $α \geq 0$ . Later I’ll try to convince you of what value I think $α$ should take. If you can guess already, I want to know how!

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

Let $A$ be a finite metric space, with points $a_{1}, \dots, a_{n}$ and metric $d$ . Write $Z$ for the $n \times n$ matrix whose $(i, j)$ -entry is $α^{d (a_{i}, a_{j})}$ . The cardinality $∣ A ∣$ of $A$ is the sum of all $n^{2}$ entries of $Z^{- 1}$ .

I’ll assume from now until nearly the end that $Z$ 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 $A$ . It has points $a_{1}$ and $a_{2}$ , distance $d (a_{1}, a_{2}) = d$ apart. So $Z = (\begin{matrix} 1 & α^{d} \\ α^{d} & 1 \end{matrix}),$ and a short calculation shows that the sum $∣ A ∣$ of the entries of $Z^{- 1}$ is $2 / (1 + α^{d})$ . Suppose that $0 < α < 1$ . Then $∣ A ∣$ is ‘how many points there appear to be to someone with bad eyesight’. As $d$ increases from $0$ to $∞$ , $∣ A ∣$ increases from $1$ to $2$ . If $d$ is small then $∣ A ∣$ is close to $1$ : it looks as if there’s only one point. If $d$ is large then $∣ A ∣$ is nearly $2$ : 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 $α$ to be between $0$ and $1$ . Taking different values of $α$ 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})$ 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 $1 cm$ : it’s $1 cm + 1 point$ , or $1 {cm}^{1} + 1 {cm}^{0}$ , or simply $1 cm + 1$ . Similarly, a closed interval of length $a cm$ has length $a cm + 1$ .

What about a closed rectangle, say $[0, a] \times [0, b]$ ? From a formal point of view, its measure ought to be $(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 $a b {cm}^{2}$ in the middle. You also need to paint the boundary, which you might think would require $(2 a + 2 b) cm$ , but as you’re only painting the inside of the boundary, it’s half of that. Similarly, you have to paint $90^{\circ} / 360^{\circ} = 1 / 4$ of each of the four corner points, which requires $4 \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 $n$ . A subset of $ℝ^{n}$ is polyconvex if it can be expressed as a finite union of compact convex sets. Let $V_{n}$ be the set of ‘measures’ on the polyconvex subsets of $ℝ^{n}$ . Here I don’t mean measures in the usual sense. A ‘measure’ in this sense assigns a real number $∣ A ∣$ to every polyconvex $A \subset ℝ^{n}$ , and is finitely additive: $∣ 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_{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$ . Specifically, $V_{n}$ has a basis $∣ ∣_{0}, ∣ ∣_{1}, . . ., ∣ ∣_{n}$ where the measure $∣ ∣_{d}$ is $d$ -dimensional: writing $t A$ to mean a polyconvex set $A$ scaled up by a factor of $t$ , it satisfies $∣ t A ∣_{d} = t^{d} ∣ A ∣_{d}$ . For instance, $Euler characteristic, perimeter, area$ is a basis for $V_{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]$ of length $a$ . Let $(A_{k})_{k \in ℕ}$ be a sequence of finite subsets of $[0, a]$ that converges to $[0, a]$ in an obvious sense:

for all $ε > 0$ there exists $K \in ℕ$ such that for all $k \geq K$ , the $ε$ -balls centred on the elements of $A_{k}$ cover $[0, a]$ .

Theorem The sequence $(∣ A_{k} ∣)_{k \in ℕ}$ of cardinalities converges to $a + 1$ .

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

Recall, however, that the definition of the cardinality of a metric space depends on the choice of a constant $α \geq 0$ . To make the theorem true, we have to take $α = e^{- 2}$ ; otherwise, the sequence of cardinalities converges to $C a + 1$ for some positive constant $C \neq 1$ . So from now on, $α = 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] \times [0, b]$ has cardinality $a 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 $A$ , it’s often worth considering the whole family $(t A)_{0 < t < ∞}$ of spaces, where $t A$ means $A$ with the metric multiplied by a factor of $t$ . With this in mind, let’s define for each space $A$ a function $\begin{matrix} χ_{A} : & (0, ∞) & \to & ℝ \\ t & \mapsto & ∣ t A ∣ . \end{matrix}$ I’ll call $χ_{A}$ the cardinality function of $A$ . It tells us the cardinality not only of $A$ , but also of all its brothers and sisters $t A$ .

Examples Let $A$ be a closed interval of length $a$ . Then $χ_{A} (t) = a t + 1 .$ Let $A$ be a closed $a \times b$ rectangle. Then $χ_{A} (t) = a b t^{2} + (a + b) t + 1,$ exactly the formula from the section on geometric measure theory, but with ‘ $t$ ’ instead of ‘cm’.

Conjecture Let $A$ be a convex subset of $ℝ^{n}$ . Then $χ_{A} (t) = ∣ A ∣_{n} t^{n} + \dots + ∣ A ∣_{1} t + ∣ A ∣_{0}$ where the $∣ ∣_{d}$ ’s are the measures of Hadwiger’s Theorem, suitably normalized.

The conjecture says in particular that $χ_{A}$ is a polynomial and that its degree is the dimension of $A$ .

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 $A$ be Sierpiński’s gasket. Since $t A$ is the union of $3$ copies of $(t / 2) A$ , overlapping at $3$ points, we’d expect $χ_{A} (t) = 3 χ_{A} (t / 2) - 3 .$ Solving this gives $χ_{A} (t) = b t^{D} + 3 / 2$ where $D = (\log 3) / (\log 2)$ and $b$ is some other constant. Although this isn’t a polynomial, its ‘degree’ in some analytic sense is $D$ . And $D$ is the Hausdorff dimension of $A$ ! So just as in the conjecture, the degree of $χ_{A}$ is the dimension of $A$ .

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 $\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 $Z$ is metric if it is symmetric, its diagonal entries are all $1$ , its off-diagonal entries are all in $[0, 1)$ , and $Z_{i j} Z_{j k} \leq Z_{i k}$ for all $i, 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 $A$ be a finite metric space.

Let $\tilde{A}$ be another metric space with the same set of points as $A$ and with $d_{\tilde{A}} (a, b) \geq d_{A} (a, b)$ for all $a, b$ . Show that $∣ \tilde{A} ∣ \geq ∣ A ∣$ .
Show that $∣ t A ∣ \geq ∣ A ∣$ for all $t \geq 1$ . (A special case of the previous part.)
Show that if $A$ has $n$ points then $1 \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 ∣ \leq n$ in the last part of Exercise 2. He has a potential non-symmetric counterexample to the conjecture that $∣ 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: http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1596

58 Comments & 8 Trackbacks

Re: Metric Spaces

$MathML-enabled post (click for more details).$

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})$ 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 $k$ th powers of integers from $1$ to $n$ ,” and Connes replies “These numbers appear in the asymptotics of $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, \dots$ , and the probability of being in the $n$ th state is proportional to $\exp (- n x)$ for some parameter $x$ . Then the actual probability of being in the $n$ th state is $\exp (- n x) / Z$ , where the normalizing factor $Z$ is

$Z = \sum_{n = 0}^{∞} \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)$ .

If you try to Taylor expand this function

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

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

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

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

$\frac{x}{1 - \exp (- x)} = \sum_{n = 0}^{∞} B_{n} \frac{x^{n}}{n!}$

where the coefficients $B_{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} + \dots + 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 $(4 n - 1)$ -sphere.

More importantly, I don’t really know why the function $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)$ — 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

$MathML-enabled post (click for more details).$

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

2 n \times 2 n

matrix whose entries are equal to

a

on the upper left and bottom right

n \times n

blocks (except on the diagonal, where they are

1

), and equal to

b

on the other two blocks. This is a metric matrix whenever

b^{2} \leq a \leq \sqrt{b} < 1

. But by testing it against the vector which consists of

n

1s followed by

n

-1s, we see that it ceases to be positive definite once

1 + (n - 1) a \leq n b

. The two conditions become compatible for

n \geq 3

, e.g. take

a = 1 / 2

and

b = 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

$MathML-enabled post (click for more details).$

Terence said:

Unfortunately, Exercise 1 is false.

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

(1)

(a - 1)^{2 n - 2} ((n - 1) a + 1 + nb) ((n - 1) a + 1 - n b)

(at least according to maple – I haven’t checked properly). So the matrix is singular when $a = \frac{1}{n - 1}$ and $b = \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)

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

which lies between $1$ and $2 n$ as one would hope!

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

Re: Metric Spaces

$MathML-enabled post (click for more details).$

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 = (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 $(1 - a) + bn + an$ , $(1 - a) - bn + an$ and $1 - a$ , the last with multiplicty 2n-2.

Similarly, it is easy to show that the sum of the entries of Z^{-1} is $2 n / ((n - 1) a + 1 + nb)$ . Let v be the vector (1,1,..,1). Then we want to compute $v Z^{- 1} v^{T}$ . Now, $Z v^{T} = (1 + (n - 1) a + nb) v^{T}$ so $Z^{- 1} v^{T} = (1 + (n - 1) a + nb)^{- 1} v^{T}$ and $v Z^{- 1} v^{T} = (1 + (n - 1) a + nb)^{- 1} v v^{T} = 2 n / (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 / \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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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 $A$ is as the sum of the entries of $Z^{- 1}$ , where $Z$ is the square matrix whose entries are the cardinalities of the hom-sets of $A$ . (This also applies to enriched categories, and in particular to metric spaces.) However, we know a couple of ways to avoid the assumption that $Z$ 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 $A$ be a (possibly enriched) category and $Z$ its associated matrix. A weighting on $A$ is a column vector $w$ such that $Z w = (\begin{matrix} 1 \\ ⋮ \\ 1 \end{matrix}) .$ A coweighting on $A$ is a row vector $\tilde{w}$ such that $\tilde{w} Z = (1, \dots, 1)$ . A category $A$ has cardinality if it admits both a weighting and a coweighting; its cardinality $∣ A ∣$ is the sum $\sum_{i} w_{i} = \sum_{j} {\tilde{w}}_{j}$ for any weighting $w$ and coweighting $\tilde{w}$ . An easy lemma shows that $∣ A ∣$ is independent of the choices involved.

When $Z$ is invertible, there are a unique weighting and coweighting and the cardinality is the sum of the entries of $Z^{- 1}$ . When $Z$ 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, $Z$ 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 $\sum_{i} w_{i}$ for any weighting $w$ . This notion of ‘has cardinality’ is more generous than the one in my post (that $Z$ is invertible). Exercise 1 now becomes:

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

Terry’s answer doesn’t settle Exercise $1^{'}$ . 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 $a$ and $b$ so that $Z$ is not invertible, the cardinality comes out as $1 / b$ .

If Exercise $1^{'}$ 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 $Z$ is invertible is to use a suggestion of Clemens Berger, discussed previously. Write $adj (M)$ for the adjugate, or classical adjoint, of a matrix $M$ . If $Z$ is invertible then the sum of the entries of $Z^{- 1}$ is $\frac{sum of entries of adj (Z)}{\det (Z)} .$ But for every $Z$ there’s a rational function $g (t) = \frac{sum of entries of adj (Z - t)}{\det (Z - t)}$ and this is well-defined at $t = 0$ in many cases where $Z$ is not invertible. You can then take $g (0)$ to be the substitute for ‘sum of the entries of $Z^{- 1}$ ’. That’s essentially what Simon did in his previous comment.

So, we have progress! Exercise 1 is false, but Exercises $1^{'}$ and 2 remain open.

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

Re: Metric Spaces

$MathML-enabled post (click for more details).$

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_{ij} z_{jk} \leq z_{ik}

). On the other hand, the variety of matrices which are non-invertible but have

(1, \dots, 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

n - 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

$MathML-enabled post (click for more details).$

Very interesting.

We now know that there exist ‘singularities’ in the space of metric matrices: points $Z$ 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 $n$ and a non-invertible metric matrix $Z$ . There are plenty of invertible metric matrices near $Z$ , 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 $Z$ behave? There are three possibilities:

their cardinalities converge towards some value at $Z$
their cardinalities don’t converge at $Z$ , but they do stay within some bounded interval
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]$ .

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

Re: Metric Spaces

$MathML-enabled post (click for more details).$

Oh, hang on — I can answer part of that myself. Since the cardinality of a matrix is a rational function in its entries, namely $\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

$MathML-enabled post (click for more details).$

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 $A$ . You write down $A$ 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 $A$ is magically transformed into the identity matrix, at which point the right-hand matrix gives you $A^{- 1}$ .

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

(1)

\frac{dA}{dt} = f (A), \frac{dB}{dt} = f (A)

with the initial conditions $A (0) = A, B (0) = id$ , and having the property that $A (∞) = id, B (∞) = 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

$MathML-enabled post (click for more details).$

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

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

As you approach $(0, 0)$ in any direction, this stays in the interval $[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$ 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

$MathML-enabled post (click for more details).$

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) = \frac{2 u^{2} v^{2}}{u^{4} + v^{4}},$ which is defined for all $(u, v) \in ℝ^{2}$ except $(0, 0)$ . Since $(u^{2} - v^{2})^{2} \geq 0$ , we have $u^{4} + v^{4} \geq 2 u^{2} v^{2}$ , so $f (u, v) \leq 1$ for all $(u, v)$ . Obviously $f (u, v) \geq 0$ , so $f (u, v) \in [0, 1]$ for all $(u, v)$ . However, if we take any nonzero real $λ$ and consider $f (u, λ u)$ as $u \to 0$ , we find $\lim_{u \to 0} f (u, λ u) = \lim_{u \to 0} \frac{2}{λ^{2} + 1 / λ^{2}} = \frac{2}{λ^{2} + 1 / λ^{2}},$ which, of course, depends on $λ$ . So there’s no way to extend $f$ continuously to $(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

$MathML-enabled post (click for more details).$

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 $n$ -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

$MathML-enabled post (click for more details).$

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 $x$ apart:

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

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

$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 $x$ apart should be

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

Here’s a simple question: what coefficients do you get when you Taylor-expand this about $x = 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}$ changes as you rescale it by a factor of $x$ : you hope to get a Taylor series in $x$ 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

$MathML-enabled post (click for more details).$

John asked me to Taylor-expand $2 / (1 + e^{- 2 x})$ about $x = 0$ . Since $\frac{2}{1 + e^{- 2 x}} = 1 + \tanh (x),$ I can cheat and look it up. According to Wikipedia, the answer is $1 + \sum_{n \geq 1} \frac{B_{2 n} 4^{n} (4^{n} - 1)}{(2 n)!} x^{2 n - 1}$ where the $B_{2 n}$ ’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 $ζ$ 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 $A$ consisting of two points distance $d$ apart, the cardinality function $χ_{A}$ is given by $χ_{A} (t) = 2 / (1 + e^{- 2 d t})$ whereas the polynomial on the right-hand side of the conjecture, given by the Hadwiger measures, is just $2$ . (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 $∣ ∣ : {polyconvex sets} \to ℝ,$ 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]$ , converging to $[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

$MathML-enabled post (click for more details).$

Rather more can be said about $1 + \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 + \tan x$ , where the odd Taylor coefficients are all positive integers (whereas for $1 + \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

\tan x + \sec x = \sum_{n \geq 0} E_{n} x^{n} / n!

where the $E_{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_{n}$ is the number of “alternating permutations” of $n$ elements. (A permutation, or rather a listing of the numbers $1$ through $n$ in some order $a_{1}, a_{2}, \dots, a_{n}$ , is said to be alternating if $a_{1}$ > $a_{2}$ < $a_{3}$ > ….)

For a proof, I refer to page 149 of Stanley’s Enumerative Combinatorics. Let me define $E_{n}$ as the number of alternating permutations on $n$ elements. We will count the number of alternating permutations of $n + 1$ elements in two ways. First, the number of such alternating permutations is the same as the number of “reverse alternating” permutations where $a_{1}$ < $a_{2}$ > $a_{3}$ < …; a bijection between them is given by $a_{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 + 1$ elements is $2 E_{n + 1}$ .

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

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

From this, we derive the recurrence relation

2 E_{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_{n}$ , call it $f (x)$ , then this recurrence relation yields

2 f^{'} (x) = 1 + f (x)^{2},

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

f (x) = \tan (\frac{x}{2} + \frac{π}{4}) = \tan x + \sec x

as desired.

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

1

0, 1

1, 1, 0

0, 1, 2, 2

5, 5, 4, 2, 0

0, 5, 10, 14, 16, 16

\dots

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 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

$MathML-enabled post (click for more details).$

John wrote:

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

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

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

Tom essentially wrote:

$1 + \sum_{n \geq 1} \frac{B_{2 n} 4^{n} (4^{n} - 1)}{(2 n)!} x^{2 n - 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}$ consisting of all points with distance $< ϵ$ from the set consisting of two points a distance $x$ 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 $< ϵ$ from a polytope, expand the answer as a power series in $ϵ$ , and see how the coefficient of $ϵ^{k}$ is related to the $k$ -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: $ϵ$ and $x$ .

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

$\int_{0}^{n} i^{2} d i = n^{3} / 3$

but in fact, the volume is precisely

$\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}$ the usual way, and then at the last minute reinterpret $B^{i}$ as the $i$ th 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}$ of distance $\leq ϵ$ 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

$MathML-enabled post (click for more details).$

John wrote:

Ehrhart polynomial

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

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

So, the obvious question: is $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

$MathML-enabled post (click for more details).$

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}$ 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}$ for some $r$ ) 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 \cup ∞$ with $z \in C^{*}$ acting multiplicatively. You get three orbits ${0}$ , ${∞}$ and the dense orbit $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 $z \in C^{*}$ acts by $z^{p}$ then you would get a length $p + 1$ interval with $p$ 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

$MathML-enabled post (click for more details).$

Here’s part of how to think of that.

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

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

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

So somehow $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)$ . So we want to hit $f$ with the summation operator $Σ$ . Now,

$Σ = 1 / Δ$

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

$Σ = 1 / (1 - \exp (d / d x))$

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

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

and then point out that $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)$ ) is here.

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

Re: Metric Spaces

$MathML-enabled post (click for more details).$

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

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

$Σ = 1 / (1 - \exp (d / d x))$

but as John mentioned, this has a pole when $d / 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 $A$ as a multiplication operator

$(A ψ) (k) = f (k) ψ (k)$

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

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

$Σ = 1 / (1 - \exp (d / d x))$

becomes the operator on $L^{2} (ℝ)$ given by multiplication by

$1 / (1 - \exp (i k))$

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

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

We can also study this issue with less analysis using formal power series instead of $L^{2}$ functions, as I did in that Bernoulli number homework. However, then we only see the pole at $k = 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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

Is this what’s expected?

Yes. The $∣ G ∣$ arrows of the group, regarded as a one-object category, are $∣ G ∣$ automorphisms that relate the single object to itself. Hence only the fraction $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 $G$ on something.

So consider the finite group $G$ acting freely on the finite set $S$ with $∣ S ∣$ elements. Since $G$ acts freely, there are precisely $∣ G ∣$ elements in $S$ on each $G$ -orbit, and hence identifying all elements in $S$ which are related by an action of an element in $G$ leads to the quotient set $S / G$ which has $∣ S / G ∣ = ∣ S ∣ / ∣ G ∣$ many elements. Hence the factor of $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

$MathML-enabled post (click for more details).$

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 $G$ , regarded as a 1-object groupoid, should have cardinality $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 $G$ acting on a finite set $S$ , it would be nice if the quotient $S / G$ had cardinality $∣ S ∣ / ∣ G ∣$ , where $∣ G ∣$ is the usual cardinality of $G$ as a set.

This works sometimes, like if the action of $G$ on $S$ is free, but not usually.

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

$∣ 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 $G$ is just $1 / / G$ , and this has cardinality $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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

All the Exercises are now solved!

Thanks to all who have helped. Thanks especially to Terry Tao, whose solutions to Exercises 1 and $1^{'}$ pointed the way towards solving the rest.

So, Simon and I have come up with the following explicit counterexamples. In each of them, $Z$ is a symmetric matrix $(\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})$ for certain values of $a$ , $b$ and $c$ .

(Recall that by definition, $Z_{i j} = e^{- 2 d_{i j}}$ where $d_{i j}$ is the distance from the $i$ th point to the $j$ th point. For $Z$ to be the matrix of a metric space, we need the diagonal entries to be $1$ , the off-diagonal entries to be in $[0, 1)$ , and the triangle inequalities $Z_{i j} Z_{j k} \leq Z_{i k}$ . Here, this says that $b^{2} \leq a$ and $b^{2} \leq c$ .)

Counterexample to Exercise $1^{'}$ Take $(a, b, c) = (4 / 9, 2 / 3, 19 / 34)$ . Then $Z$ has no weighting.
Counterexample to Exercise 2(3), that the cardinality of a nonempty space is always $\geq 1$ Take $(a, b, c) = (4 / 9, 2 / 3, 341 / 612)$ . Then the cardinality is $- 27 / 17$ .
Counterexample to Exercise 2(3), that the cardinality of an $n$ -point space is always $\leq n$ Take $(a, b, c) = (4 / 9, 2 / 3, 647 / 1156)$ . Then the cardinality is $129 / 17 > 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 $A$ and a number $t > 1$ such that when you scale $A$ up by a factor of $t$ , its cardinality goes down!

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

Re: Counterexamples

$MathML-enabled post (click for more details).$

This means that there exists a finite metric space $A$ and a number $t > 1$ such that when you scale $A$ up by a factor of $t$ , 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

$MathML-enabled post (click for more details).$

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 $A$ you can find a sequence $A_{0} \subseteq A_{1} \subseteq \dots$ of finite subsets of $A$ with $\cup_{n} A_{n}$ dense in $A$ , and then $\lim_{n \to ∞} 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 ∣$ of the compact metric space $A$ by $∣ A ∣ = \lim_{n \to ∞} ∣ 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})$ converging to $A$ would have given the same value of $∣ 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 $A$ and sequences $(A_{n})$ , $(B_{n})$ of finite metric spaces converging to $A$ such that the sequences of cardinalities $(∣ A_{n} ∣)$ and $(∣ 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 $ℝ$ ), 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}$ 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 $A$ can be expressed as the limit of a sequence of finite spaces that all have cardinality: take any old sequence $(A_{n})$ as above, then give a slight nudge to any $A_{n}$ ’s that don’t have cardinality.

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

Theorem Let $A$ be a finite metric space with $n$ points. Given $t > 0$ , write $t A$ for $A$ scaled up by a factor of $t$ . Then

$t A$ has cardinality for all but finitely many values of $t$
there exists $T > 0$ such that for $t \geq T$ , the function $t \mapsto ∣ t A ∣$ is well-defined, increasing, and takes values in $[0, n]$ .

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

(Euler characteristic of $A$ ) $\leq$ (Euler characteristic of $B$ ): trivial, as the Euler characteristic of a convex set is $0$ if it’s empty and $1$ otherwise
(perimeter of $A$ ) $\leq$ (perimeter of $B$ ): not so obvious
(area of $A$ ) $\leq$ (area of $B$ ): 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

$MathML-enabled post (click for more details).$

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)$ . 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_{r}$ be a circle of radius $r$ , and let $d (a, b)$ be the length of the anticlockwise arc from $a$ to $b$ . This is a perfectly good non-symmetric metric. Picture $A_{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_{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 $\begin{aligned} ∣ A_{r} ∣ & = \sum_{n \geq 0} \frac{B_{n}}{n!} (- 4 π r)^{n} \\ = 1 + 2 π r + \frac{4}{3} π^{2} r^{2} - \frac{16}{45} π^{4} r^{4} + \dots \end{aligned}$ where the $B_{n}$ are the Bernoulli numbers. Or to put it slightly differently, the cardinality function of the unit circle is $t \mapsto 1 + 2 π t + \frac{4}{3} π^{2} t^{2} - \frac{16}{45} π^{4} t^{4} + \dots .$

Of course, it’s nice to see $2 π 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? $\frac{4}{3} π^{2} r^{2}$ is nearly familiar, but not quite, the constant term $1$ is a puzzle, and I have no clue about $- \frac{16}{45}$ .

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

Re: Cardinality of a circle

$MathML-enabled post (click for more details).$

It’s there implicitly, but I should have said it explicitly: the cardinality of a circle of radius $r$ is $\frac{4 π r}{1 - e^{- 4 π 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

$MathML-enabled post (click for more details).$

Are you thinking that the constant term is what you get when you take $r$ to be $0$ , which should therefore be the cardinality of a circle of radius $0$ , 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 / 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

$MathML-enabled post (click for more details).$

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 $n$ points approaching each other, their $Z$ 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

$MathML-enabled post (click for more details).$

Yes, I know what you mean. From the point of view you describe, the constant term should always be $1$ 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

$MathML-enabled post (click for more details).$

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 π$ and radius (ie distance from the pole) $π / 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 $a$ as

(1)

\frac{2 a}{1 - e^{- 2 a}} .

Hmmm. Now that looks familiar….

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

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

Re: Cardinality of a circle

$MathML-enabled post (click for more details).$

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

(1)

\frac{a e^{a}}{e^{a} - 1} .

There are many observations I could make about these formulas for various values of $a$ , 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

$MathML-enabled post (click for more details).$

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 $a$ .

(1)

\begin{matrix} line & circle \\ symmetric & a + 1 & \frac{a}{1 - e^{- a}} \\ non-symmetric & 2 a + 1 & \frac{2 a}{1 - e^{- 2 a}} \end{matrix}

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_{a}$ the circle of length (i.e. circumference) $a$ with its usual (symmetric) metric. I think an important thing to note is that the cardinality is not a polynomial in $a$ , 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 = 0$ , by which I mean it is giving misleading information for large $a$ .

For small $a$ , the power-series expansion gives $∣ 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 $a$ you have $∣ C_{a} ∣ \sim a$ , by which I mean the precise statement that $∣ C_{a} ∣ - a \to 0$ as $a \to ∞$ . 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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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 $V$ -categories would be to consider (weighted?) colimits of $V$ -objects. In the case $V = [0, ∞]$ , colimits in $V$ 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

$MathML-enabled post (click for more details).$

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}_{X} F$

as a coend

$\int^{X} (Δ I) \cdot F$

(I think), where $Δ 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$ 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

$MathML-enabled post (click for more details).$

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 \mapsto ∣ t A ∣$

in powers of $t$ . 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 $Ω$ in $ℝ^{2}$ is recalled:

the constant coefficient is proportional to the Euler characteristic of $Ω$ ;

the next coefficient is proportional to the length of the boundary of $Ω$ ;

the next coefficients is proportional to the area of $Ω$

(both length and area measured with respect to the standard metric on $ℝ^{2}$ ).

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

Re: Metric Spaces

$MathML-enabled post (click for more details).$

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 $t$ as ‘time’, and we’re trying to understand how the total heat content of our manifold changes with time. In Tom’s setup, $t$ 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 = 1$ . The expansion of the heat content says:

(1)

H (t = 1) \sim Area (Ω) - Length (\partial Ω) + Euler char (Ω) + \dots

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

(2)

H_{λ} (t = 1) \sim λ^{2} Area (Ω) - λ Length (\partial Ω) + Euler char (Ω) + \dots

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

$MathML-enabled post (click for more details).$

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

$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

The n-Category Café

Skip to the Main Content

February 9, 2008

Metric Spaces

Posted by John Baez

Some Related Entries

58 Comments & 8 Trackbacks

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Beautiful Math; Re: Metric Spaces

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

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

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

RH, pi-permian era; Re: Metric Spaces

Re: Metric Spaces

Euler numbers; related sequences; Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Cardinality of a group

Re: Cardinality of a group

Re: Cardinality of a group

Re: Cardinality of a group

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Metric Entropy; Re: Metric Spaces

Counterexamples

Re: Counterexamples

Re: Counterexamples

Cardinality of a circle

Re: Cardinality of a circle

Re: Cardinality of a circle

Re: Cardinality of a circle

Re: Cardinality of a circle

Re: Cardinality of a circle

Re: Cardinality of a circle

Re: Cardinality of a circle

Re: Cardinality of a circle

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Re: Metric Spaces

Access Keys: