Lynx Roundup, July 24th 2018

Lynx Roundup, July 24th 2018

Databases! Parallelizing Pandas! Massive treasure trove of research on data visualizations!

Matthew Alhonte
Matthew Alhonte

An In-Depth Style Guide for Data Science Projects
Pandas on Ray – Early Lessons from Parallelizing Pandas
Databases 101

John D. Cook, Greg Egan, Dan Piponi and I had a fun mathematical adventure on Twitter. It started when John Cook wrote a program to compute the probability distribution of distances |xy - yx| where x and y were two randomly chosen unit quaternions:

• John D. Cook, How far is xy from yx on average for quaternions?, 5 July 2018.

Three things to note before we move on:

• Click the pictures to see the source and get more information—I made none of them!

• We’ll be ‘randomly choosing’ lots of points on spheres of various dimensions. Whenever we do this, I mean that they’re chosen independently, and uniformly with respect to the unique rotation-invariant Borel measure that’s a probability measure on the sphere. In other words: nothing sneaky, just the most obvious symmetrical thing!

• We’ll be talking about lots of distances between points on the unit sphere in n dimensions. Whenever we do this, I mean the Euclidean distance in \mathbb{R}^n, not the length of the shortest path on the sphere connecting them.

Okay:

If you look at the histogram above, you’ll see the length |xy - yx| is between 0 and 2. That’s good, since xy and yx are on the unit sphere in 4 dimensions. More interestingly, the mean looks bigger than 1. John Cook estimated it at 1.13.

Greg Egan went ahead and found that the mean is exactly

\displaystyle{\frac{32}{9 \pi}} \approx 1.13176848421 \dots

He did this by working out a formula for the probability distribution:

All this is great, but it made me wonder how surprised I should be. What’s the average distance between two points on the unit sphere in 4 dimensions, anyway?

Greg Egan worked this out too:



So, the mean distance |x - y| for two randomly chosen unit quaternions is

\displaystyle{\frac{64}{15 \pi}} \approx 1.35812218105\dots

The mean of |xy - yx| is smaller than this. In retrospect this makes sense, since I know what quaternionic commutators are like: for example the points x = \pm 1 at the ‘north and south poles’ of the unit sphere commute with everybody. However, we can now say the mean of |xy - yx| is exactly

\displaystyle{\frac{32}{9\pi} } \cdot  \frac{15 \pi}{64} = \frac{5}{6}

times the mean of |x - y|, and there’s no way I could have guessed that.

While trying to get a better intuition for this, I realized that as you go to higher and higher dimensions, and you standing at the north pole of the unit sphere, the chance that a randomly chosen other point is quite near the equator gets higher and higher! That’s how high dimensions work. So, the mean value of |x - y| should get closer and closer to \sqrt{2}. And indeed, Greg showed that this is true:

The graphs here show the probability distributions of distances for randomly chosen pairs of points on spheres of various dimensions. As the dimension increases, the probability distribution gets more sharply peaked, and the mean gets closer to \sqrt{2}.

Greg wrote:

Here’s the general formula for the distribution, with plots for n=2,…,10. The mean distance does tend to √2, and the mean of the squared distance is always exactly 2, so the variance tends to zero.

But now comes the surprising part.

Dan Piponi looked at the probability distribution of distances s = |x - y| in the 4-dimensional case:

P(s) = \displaystyle{\frac{s^2\sqrt{4 - s^2}}{\pi} }

and somehow noticed that its moments

\int_0^2 P(s) s^{n} \, dx

when n is even, are the Catalan numbers!

Now if you don’t know about moments of probability distributions you should go read about those, because they’re about a thousand times more important than anything you’ll learn here.

And if you don’t know about Catalan numbers, you should go read about those, because they’re about a thousand times more fun than anything you’ll learn here.

So, I’ll assume you know about those. How did Dan Piponi notice that the Catalan numbers

C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42, \dots

were the even moments of this probability distribution? Maybe it’s because he recently managed to get ahold of Richard Stanley’s book on Amazon for just $11 instead of its normal price of $77.

(I don’t know how that happened. Some people write 7’s that look like 1’s, but….)

Anyway, you’ll notice that this strange phenomenon is all about points on the unit sphere in 4 dimensions. It doesn’t seem to involve quaternions anymore! So I asked if something similar happens in other dimensions, maybe giving us other interesting sequences of integers.

Greg Egan figured it out, and got some striking results:

Here d is the dimension of the Euclidean space containing our unit sphere, and Egan is tabulating the nth moment of the probability distribution of distances between two randomly chosen points on that sphere. The gnarly formula on top is a general expression for this moment in terms of the gamma function.

The obvious interesting feature of this table is that only for d = 2 and d = 4 rows are all the entries integers.

But Dan made another great observation: Greg left out the rather trivial d = 1 row, and that all the entries of this row would be integers too! Even better, d = 1, 2, and 4 are the dimensions of the associative normed division algebras: the real numbers, the complex numbers and the quaternions!

This made me eager to find a proof that all the even moments of the probability distribution of distances between points on the unit sphere in \mathbb{R}^d are integers when \mathbb{R}^d is an associative normed division algebra.

The first step is to notice the significance of even moments.

First, we don’t need to choose both points on the sphere randomly: we can fix one and let the other vary. So, we can think of the distance

D(x) = |(x_1, \dots, x_d) - (1, \dots, 0)| = \sqrt{(x_1 - 1)^2 + x_2^2 + \cdots + x_d^2}

as a function on the sphere, or more generally a function of x \in \mathbb{R}^d. And when we do this we instantly notice that the square root is rather obnoxious, but all the even powers of the function D are polynomials on \mathbb{R}^d.

Then, we notice that restricting polynomials from Euclidean space to the sphere is how we get spherical harmonics, so this problem is connected to spherical harmonics and ‘harmonic analysis’. The nth moment of the probability distribution of distances between points on the unit sphere in \mathbb{R}^d is

\int_{S^{d-1}} D^n

where we are integrating with respect to the rotation-invariant probability measure on the sphere. We can rewrite this as an inner product in L^2(S^{d-1}), namely

\langle D^n , 1 \rangle

where 1 is the constant function equal to 1 on the whole sphere.

We’re looking at the even moments, so let n = 2m. Now, why should

\langle D^{2m} , 1 \rangle

be an integer when d = 1, 2 and 4? Well, these are the cases where the sphere S^{d-1} is a group! For d = 1,

S^0 \cong \mathbb{Z}/2

is the multiplicative group of unit real numbers, \{\pm 1\}. For d = 2,

S^1 \cong \mathrm{U}(1)

is the multiplicative group of unit complex numbers. And for d = 4,

S^3 \cong \mathrm{SU}(2)

is the multiplicative group of unit quaternions.

These are compact Lie groups, and L^2 of a compact Lie group is very nice. Any finite-dimensional representation \rho of a compact Lie group G gives a function \chi_\rho \in L^2(G) called its character, given by

\chi_\rho(g) = \mathrm{tr}(\rho(g))

And it’s well-known that for two representations \rho and \sigma, the inner product

\langle \chi_\rho, \chi_\sigma \rangle

is an integer! In fact it’s a natural number: just the dimension of the space of intertwining operators from \rho to \sigma. So, we should try to prove that

\langle D^{2m} , 1 \rangle

is an integer this way. The function 1 is the character of the trivial 1-dimensional representation, so we’re okay there. What about D^{2m}?

Well, there’s a way to take the mth tensor power \rho^{\otimes m} of a representation \rho: you just tensor the representation with itself m times. And then you can easily show

\chi_{\rho^{\otimes m}} = (\chi_\rho)^m

So, if we can show D^2 is the character of a representation, we’re done: D^{2m} will be one as well, and the inner product

\langle D^{2m}, 1 \rangle

will be an integer! Great plan!

Unfortunately, D^2 is not the character of a representation.

Unless \rho is the completely silly 0-dimensional representation we have

\chi_\rho(1) = \mathrm{tr}(\rho(1)) = \dim(\rho) > 0

where 1 is the identity element of G. But suppose we let D(g) be the distance of g from the identity element—the natural choice of ‘north pole’ when we make our sphere into a group. Then we have

D(1)^2 = 0

So D^2 can’t be a character. (It’s definitely not the character of the completely silly 0-dimensional representation: that’s zero.)

But there’s a well-known workaround. We can work with virtual representations, which are formal differences of representations, like this:

\delta = \rho - \sigma

The character of a virtual representation is defined in the obvious way

\chi_\delta = \chi_\rho - \chi_\sigma

Since the inner product of characters of two representations is a natural number, the inner product of characters of two virtual representations will be an integer. And we’ll be completely satisfied if we prove that

\langle D^{2m}, 1 \rangle

is an integer, since it’s obviously ≥ 0.

So, we just need to show that D^{2m} is the character of a virtual representation. This will easily follow if we can show D^2 itself is the character of a virtual representation: you can tensor virtual representations, and then their characters multiply.

So, let’s do it! I’ll just do the quaternionic case. I’m doing it right now, thinking out loud here. I figure I should start with a really easy representation, take its character, compare that to our function D^2, and then fix it by subtracting something.

Let \rho be the spin-1/2 representation of \mathrm{SU}(2), which just sends every matrix in \mathrm{SU}(2) to itself. Every matrix in \mathrm{SU}(2) is conjugate to one of the form

g = \left(\begin{array}{cc} \exp(i\theta) & 0 \\ 0 & \exp(-i\theta) \end{array}\right)

so we can just look at those, and we have

\chi_\rho(g) = \mathrm{tr}(\rho(g)) = \mathrm{tr}(g) = 2 \cos \theta

On the other hand, we can think of g as a unit quaternion, and then

g = \cos \theta + i \sin \theta

where now i stands for the quaternion of that name! So, its distance from 1 is

D(g) = |\cos \theta + i \sin \theta - 1|

and if we square this we get

D(g)^2 = (1 - \cos \theta)^2 + \sin^2 \theta = 2 - 2 \cos \theta

So, we’re pretty close:

D(g)^2 = 2 - \chi_{\rho}

In particular, this means D^2 is the character of the virtual representation

(1 \oplus 1) - \rho

where 1 is the 1d trivial rep and \rho is the spin-1/2 rep.

So we’re done!

At least we’re done showing the even moments of the distance between two randomly chosen points on the 3-sphere is an integer. The 1-sphere and 0-sphere cases are similar.

But course there’s another approach! We can just calculate the darn moments and see what we get. This leads to deeper puzzles, which we have not completely solved. But I’ll talk about these next time, in Part 2.

Roundup

Matthew Alhonte

Supervillain in somebody's action hero movie. Experienced a radioactive freak accident at a young age which rendered him part-snake and strangely adept at Python.