Skip to the Main Content

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

March 22, 2017

Functional Equations VII: The p-Norms

Posted by Tom Leinster

The pp-norms have a nice multiplicativity property:

(Ax,Ay,Az,Bx,By,Bz) p=(A,B) p(x,y,z) p \|(A x, A y, A z, B x, B y, B z)\|_p = \|(A, B)\|_p \, \|(x, y, z)\|_p

for all A,B,x,y,zA, B, x, y, z \in \mathbb{R} — and similarly, of course, for any numbers of arguments.

Guillaume Aubrun and Ion Nechita showed that this condition completely characterizes the pp-norms. In other words, any system of norms that’s multiplicative in this sense must be equal to p\|\cdot\|_p for some p[1,]p \in [1, \infty]. And the amazing thing is, to prove this, they used some nontrivial probability theory.

All this is explained in this week’s functional equations notes, which start on page 26 here.

Posted at 2:12 AM UTC | Permalink | Post a Comment

March 21, 2017

On the Operads of J. P. May

Posted by Emily Riehl

Guest post by Simon Cho

We continue the Kan Extension Seminar II with Max Kelly’s On the operads of J. P. May. As we will see, the main message of the paper is that (symmetric) operads enriched in a suitably nice category 𝒱\mathcal{V} arise naturally as monoids for a “substitution product” in the monoidal category [P,𝒱][\mathbf{P}, \mathcal{V}] (where P\mathbf{P} is a category that keeps track of the symmetry). Before we begin, I want to thank the organizers and participants of the Kan Extension Seminar (II) for the opportunity to read and discuss these nice papers with them.

Posted at 11:07 AM UTC | Permalink | Followups (3)

March 15, 2017

Functional Equations VI: Using Probability Theory to Solve Functional Equations

Posted by Tom Leinster

A functional equation is an entirely deterministic thing, such as f(x+y)=f(x)+f(y) f(x + y) = f(x) + f(y) or f(f(f(x)))=x f(f(f(x))) = x or f(cos(e f(x)))+2x=sin(f(x+1)). f\Bigl(\cos\bigl(e^{f(x)}\bigr)\Bigr) + 2x = \sin\bigl(f(x+1)\bigr). So it’s a genuine revelation that one can solve some functional equations using probability theory — more specifically, the theory of large deviations.

This week and next week, I’m explaining how. Today (pages 22-25 of these notes) was mainly background:

  • an introduction to the theory of large deviations;

  • an introduction to convex duality, which Simon has written about here before;

  • how the two can be combined to get a nontrivial formula for sums of powers of real numbers.

Next time, I’ll explain how this technique produces a startlingly simple characterization of the pp-norms.

Posted at 12:56 AM UTC | Permalink | Post a Comment

March 10, 2017

The Logic of Space

Posted by Mike Shulman

Mathieu Anel and Gabriel Catren are editing a book called New Spaces for Mathematics and Physics, about all different kinds of notions of “space” and their applications. Among other things, there are chapters about smooth spaces, \infty-groupoids, topos theory, stacks, and various other things of interest to nn-Cafe patrons, all of which I am looking forward to reading. There are chapters by our own John Baez about the continuum and Urs Schreiber about higher prequantum geometry. Here is my own contribution:

Posted at 12:58 PM UTC | Permalink | Followups (16)

Postdocs in Sydney

Posted by Tom Leinster

Richard Garner writes:

The category theory group at Macquarie is currently advertising a two-year Postdoctoral Research Fellowship to work on a project entitled “Enriched categories: new applications in geometry and logic”.

Applications close 31st March. The position is expected to start in the second half of this year.

More information can be found at the following link:

http://jobs.mq.edu.au/cw/en/job/500525/postdoctoral-research-fellow

Feel free to contact me with further queries.

Richard Garner

Posted at 12:19 AM UTC | Permalink | Post a Comment

March 8, 2017

Functional Equations V: Expected Surprise

Posted by Tom Leinster

In today’s class I explained the concept of “expected surprise”, which also made an appearance on this blog back in 2008: Entropy, Diversity and Cardinality (Part 1). Expected surprise is a way of interpreting the qq-deformed entropies that I like to call “surprise entropies”, and that are usually and mistakenly attributed to Tsallis. These form a one-parameter family of deformations of ordinary Shannon entropy.

Also in this week’s session: qq-logarithms, and a sweet, unexpected surprise:

Surprise entropies are much easier to characterize than ordinary entropy!

For instance, all characterization theorems for Shannon entropy involve some regularity condition (continuity or at least measurability), whereas each of its qq-deformed cousins has an easy characterization that makes no regularity assumption at all.

It’s all on pages 18–21 of the course notes so far.

Posted at 1:36 AM UTC | Permalink | Followups (12)

March 7, 2017

Algebra Valued Functors in General and Tensor Products in Particular

Posted by Emily Riehl

Guest post by Maru Sarazola

The Kan Extension Seminar II continues, and this time we focus on the article “Algebra valued functors in general and tensor products in particular” by Peter Freyd, published in 1966. Its purpose is to present algebraic theories and some related notions in a way that doesn’t make use of elements, so the concepts can later be applied to any category (satisfying some restrictions).

Concerned that the language of categories was not popular enough at the time, he chooses to target a wider audience by taking an “equational” approach in his exposition (in contrast, for example, to Lawvere’s more elegant approach, purely in terms of functors and natural transformations). I must say that this perspective, which nowadays might seem somewhat cumbersome, greatly helped solidify my understanding of some of these notions and constructions.

Before we start, I would like to thank Brendan Fong, Alexander Campbell and Emily Riehl for giving me the opportunity to take part in this great learning experience, and all the other participants for their enlightening comments and discussions. I would also like to thank my advisor, Inna Zakharevich, for her helpful comments and especially for her encouragement throughout this entire process.

Posted at 10:22 AM UTC | Permalink | Followups (6)

February 28, 2017

Functional Equations IV: A Simple Characterization of Relative Entropy

Posted by Tom Leinster

Relative entropy appears in mathematics, physics, engineering, and statistics under an unhelpful variety of names: relative information, information gain, information divergence, Kullback-Leibler divergence, and so on and on. This hints at how important it is.

In the functional equations course that I’m currently delivering, I stated and proved a theorem today that characterizes relative entropy uniquely:

Theorem   Relative entropy is essentially the only function that satisfies three trivial requirements and the chain rule.

You can find this on pages 15–19 of the course notes so far, including an explanation of the “chain rule” in terms of Swiss and Canadian French.

I don’t know who this theorem is due to. I came up with it myself, I’m not aware of its existence in the literature, and it didn’t appear on this list until I added it. However, it could have been proved any time since the 1950s, and I bet someone’s done it before.

The proof I gave owes a great deal to the categorical characterization of relative entropy by John Baez and Tobias Fritz, which John blogged about here before.

Posted at 7:05 PM UTC | Permalink | Followups (11)

February 26, 2017

Variance in a Metric Space

Posted by Tom Leinster

Here’s a small observation for a Sunday afternoon. When you have a random variable in n\mathbb{R}^n or some other similar space, you can take its expected value. For a random variable XX in an arbitrary metric space, you can’t take the expected value — it simply doesn’t make sense. (Edited to add: maybe that’s misleading. See the comments!) But you can take its variance, and the right definition is

Var(X)=12𝔼(d(X 1,X 2) 2), Var(X) = \tfrac{1}{2} \mathbb{E}(d(X_1, X_2)^2),

where X 1X_1 and X 2X_2 are independent and distributed identically to XX.

Posted at 4:05 PM UTC | Permalink | Followups (7)

February 22, 2017

Functional Equations III: Explaining Relative Entropy

Posted by Tom Leinster

Much of this functional equations course is about entropy and its cousins, such as means, norms, and measures of diversity. So I thought it worth spending one session talking purely about ways of understanding entropy, without actually proving anything about it. I wanted especially to explain how to think about relative entropy — also known as relative information, information gain, and Kullback-Leibler divergence.

My strategy was to do this via coding theory. Information is a slippery concept, and reasoning about it takes some practice. But putting everything in the framework of coding makes everything more concrete. The central point is:

The entropy of a distribution is the mean number of bits per symbols in an optimal encoding.

All this and more is in the course notes. The part we did today starts on page 11.

Next week: relative entropy is the only quantity that satisfies a couple of reasonable properties.

Posted at 12:13 AM UTC | Permalink | Followups (1)

February 18, 2017

Distributive Laws

Posted by Emily Riehl

Guest post by Liang Ze Wong

The Kan Extension Seminar II continues and this week, we discuss Jon Beck’s “Distributive Laws”, which was published in 1969 in the proceedings of the Seminar on Triples and Categorical Homology Theory, LNM vol 80. In the previous Kan seminar post, Evangelia described the relationship between Lawvere theories and finitary monads, along with two ways of combining them (the sum and tensor) that are very natural for Lawvere theories but less so for monads. Distributive laws give us a way of composing monads to get another monad, and are more natural from the monad point of view.

Beck’s paper starts by defining and characterizing distributive laws. He then describes the category of algebras of the composite monad. Just as monads can be factored into adjunctions, he next shows how distributive laws between monads can be “factored” into a “distributive square” of adjunctions. Finally, he ends off with a series of examples.

Before we dive into the paper, I would like to thank Emily Riehl, Alexander Campbell and Brendan Fong for allowing me to be a part of this seminar, and the other participants for their wonderful virtual company. I would also like to thank my advisor James Zhang and his group for their insightful and encouraging comments as I was preparing for this seminar.

Posted at 7:06 AM UTC | Permalink | Followups (16)

February 14, 2017

Functional Equations II: Shannon Entropy

Posted by Tom Leinster

In the second instalment of the functional equations course that I’m teaching, I introduced Shannon entropy. I also showed that up to a constant factor, it’s uniquely characterized by a functional equation that it satisfies: the chain rule.

Notes for the course so far are here. For a quick summary of today’s session, read on.

Posted at 11:06 PM UTC | Permalink | Followups (12)

February 13, 2017

M-theory from the Superpoint

Posted by David Corfield

You may have been following the ‘Division algebra and supersymmetry’ story, the last instalment of which appeared a while ago under the title M-theory, Octonions and Tricategories. John (Baez) was telling us of some work by his former student John Huerta which relates these entities. The post ends with a declaration which does not suffer from comparison to Prospero’s in The Tempest

But this rough magic

I here abjure. And when I have required

Some heavenly music – which even now I do –

To work mine end upon their senses that

This airy charm is for, I’ll break my staff,

Bury it certain fathoms in the earth,

And deeper than did ever plummet sound

I’ll drown my book.

Posted at 1:21 PM UTC | Permalink | Followups (8)

February 10, 2017

The Heilbronn Institute and the University of Bristol

Posted by Tom Leinster

The Heilbronn Institute is the mathematical brand of the UK intelligence and spying agency GCHQ (Government Communications Headquarters). GCHQ is one of the country’s largest employers of mathematicians. And the Heilbronn Institute is now claiming to be the largest funder of “pure mathematics” in the country, largely through its many research fellowships at Bristol (where it’s based) and London.

In 2013, Edward Snowden leaked a massive archive of documents that shone a light on the hidden activities of GCHQ and its close partner, the US National Security Agency (NSA), including whole-population surveillance and deliberate stifling of peaceful activism. Much of this was carried out without the permission — or even knowledge — of the politicians who supposedly oversee them.

All this should obviously concern any mathematician with a soul, as I’ve argued. These are our major employers and funders. But you might wonder about the close-up picture. How do spy agencies such as GCHQ and the NSA work their way into academic culture? What do they do to ensure a continuing supply of mathematicians to employ, despite the suspicion with which most of us view them?

Alon Aviram of the Bristol Cable has just published an article on this, describing specific connections between GCHQ/Heilbronn and the University of Bristol — and, more broadly, academic mathematicians and computer scientists:

Alon Aviram, Bristol University working with the surveillance state. The Bristol Cable, 7 February 2017.

It includes some quotes from me and from legendary computer-security scientist Ross Anderson, as well as some nuggets from a long leaked Heilbronn “problem book” that’s interesting in its own right.

Posted at 2:42 PM UTC | Permalink | Post a Comment

February 7, 2017

Functional Equations I: Cauchy’s Equation

Posted by Tom Leinster

This semester, I’m teaching a seminar course on functional equations. Why? Among other reasons:

  1. Because I’m interested in measures of biological diversity. Dozens (or even hundreds?) of diversity measures have been proposed, but it would be a big step forward to have theorems of the form: “If you want your measure to have this property, this property, and this property, then it must be that measure. No other will do.”

  2. Because teaching a course on functional equations will force me to learn about functional equations.

  3. Because it touches on lots of mathematically interesting topics, such as entropy of various kinds and the theory of large deviations.

Today was a warm-up, focusing on Cauchy’s functional equation: which functions f:f: \mathbb{R} \to \mathbb{R} satisfy

f(x+y)=f(x)+f(y)x,y? f(x + y) = f(x) + f(y) \,\,\,\, \forall x, y \in \mathbb{R}?

(I wrote about this equation before when I discovered that one of the main references is in Esperanto.) Later classes will look at entropy, means, norms, diversity measures, and a newish probabilistic method for solving functional equations.

Read on for today’s notes and an outline of the whole course.

Posted at 11:25 PM UTC | Permalink | Followups (10)