數學資料庫手記

2009年3月20日星期五

Cylindrical projection, an Archimedes' result, and Duistermaat-Heckman Theorem

I am always amazed by how accurately some old world map made long time ago depicted the globe. Cartography, or simply map-making, has long been an established form of art and science since navigation to the New World became more and more active. There are several cartography techniques which serve to describe certain geometrical information of the world geography. Cylindrical projection is one of them.

The principle of cylindrical projection is simple indeed. Let us imagine that the globe is a perfect sphere which is inscribed in a cylinder with its height and radius of cross section equal to the radius of the globe. Position this geometric configuration in the three dimensional coordinate system in such a way that the $z$ -axis passes through the center of both the sphere and the cross section of the cylinder. Cylindrical projection is just the horizontal radial projection from the sphere onto the curved surface of the cylinder. Put in a more mathematical way, cylindrical projection maps a point with $z$ -coordinate $z_0$ to the intersection of the cylindrical surface and the horizontal ray(parallel to the $xy$ -plane) emanating from $(0, 0, z_0)$ and passing through that point.

World maps made by cylindrical projection is obtained by flattening out the image of cylindrical projection on the cylindrical surface. For the convenience of archiving, it has been more common to draw world maps on a flat sheet of paper than on a sphere. But paper maps have one major drawback--they greatly distort the actual geography of the world. More precisely, distances on any paper map are not proportional to actual distances. This is a simple consequence of Gauss's Theorema Egregium, which states that the Gaussian curvature of any surface is expressible in terms of its metric. Since a sphere has constant positive curvature, whereas a plane has vanishing curvature, there is no map between them preserving distance. You may observe that the closer to the Poles a place is, the more distortedly it is presented on a map made by cylindrical projection. For instance, the Antarctica appears to be much more elongated on such maps.

But cylindrical projection is not completely without any merit. In fact cylindrical projection is area-preserving. Legend has it that this result was discovered to Archimedes. It is rather mysterious to me how Archimedes derived this fact. Anyway I will show below a proof which amounts to a 'change of variables', but is rephrased in differential-form terminology.

It suffices to show that the cylindrical projection $p:\mathbb{S}^2\to C$ induces a pullback $p^*$ which maps the area form of the cylinder to that of the inscribed sphere. The spherical coordinates are
$x=\sin\varphi\cos\theta, y=\sin\varphi\sin\theta, z=\cos\varphi$
whereas the cylindrical coordinates are
$x=\cos\theta, y=\sin\theta, z=z$
So $p(\varphi, \theta)=(\theta, \cos\varphi)$ . Note that the area form of the sphere is $\sin\varphi d\varphi\wedge d\theta$ , while that of the cylinder is $d\theta\wedge dz$ . Its pullback by $p^*$ is
$p^*(d\theta\wedge dz)=d\theta\wedge d(\cos\varphi)=d\theta\wedge (-\sin\varphi d\varphi)=\sin\varphi d\varphi\wedge d\theta$ So we are done.

For those who enjoy understanding math from a vantage point of view, note that this result of Archimedes' turns out to be a particular case of a theorem in symplectic geometry known as Duistermaat-Heckman Theorem. It says that given a Hamiltonian $T$ -space $(M, \omega)$ where $T$ is a torus and $\omega$ the symplectic form of $M$ , then the Radon-Nikodym derivative of the pushforward of the canonical measure (given by $\frac{\omega^n}{n!}$ , 2n=dimensional of $M$ ) through the moment map $\mu: M\to\mathfrak{t}^*$ with respect to the Lebesgue measure of $\mathfrak{t}^*$ is piecewise polynomial, i.e. for any measurable $U\subset\mathfrak{t}^*$ ,
$\int_{\mu^{-1}(U)}\frac{\omega^n}{n!}=\int_U p(t)dt$ for some piecewise polynomial $p(t)$ in $t\in\mathfrak{t}^*$ . Here the sphere is a Hamiltonian $\mathbb{S}^1$ -space, where its symplectic form is just the area form, $\mathbb{S}^1$ acts on the sphere by rotating about the vertical axis at unit speed and the moment map is the height function. The Radon-Nikodym derivative in this case is the constant $2\pi$ .

2009年3月9日星期一

Convolution Technique in Generating Function (1)

When I was the TA of the course "Combinatorial Analysis" in HKUST, I told students that one of the powerful properties of generating function is "convolution".

(*)To combinatorially construct an object of size n, it is a common way to first construct two smaller objects of size k and M-k (where M is a function of n, say, n or (n-1)), and then join the two smaller objects together.

The most famous example must be finding the Catalan Number. Catalan Number $C_n$ is counting the number of ways to write n "+1" and n "-1" in a row such that the for $1\leq k\leq 2n$ , the sum of the first k terms (we denote it by $P_k$ ) is NOT negative. For example, when $n=3$ , "+1 +1 -1 -1 +1 -1" and "+1 +1 +1 -1 -1 -1" satisfy the requirement while "+1 +1 -1 -1 -1 +1" does not (the first five terms sum to -1, which is negative).

Now we find out a recurrence of $C_n$ using the technique mentioned in (*). We denote the i^th term be $x_i$ .

You know, $x_1=1$ and $P_{2n}=0$ . So there exists a smallest $k\geq 0$ such that $P_{2(k+1)}=0$ . ( $P_a=0$ is impossible if a is odd.)

The terms between $x_2$ and $x_{2k}$ (inclusive) must itself form a Catalan sequence of size 2k. The reason is, if it is not a Catalan sequence, then $x_2+x_3+\cdots+x_{2a}=-1$ for some $1\leq a\leq k$ , and then , $P_{2a}=0$ , i.e. contradicting to the assumption that k is the smallest integer such that $P_{2k}=0$ . Hence, there are $C_k$ ways to fill in $x_2$ to $x_{2k}$ .

Similarly, the terms between $x_{2k+3}$ and $x_{2n}$ (inclusive) must itself form a Catalan sequence of size 2n-2k-2. Hence, there are $C_{n-1-k}$ ways to fill in $x_{2k+3}$ to $x_{2n}$ .

Hence, if k is the smallest integer such that $P_{2k}=0$ , there are $C_k C_{n-1-k}$ ways to construct a Catalan sequence of size 2n. The value of k can be varied from 0 to n-1. So we have the "convolution recurrence":

$C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$

Now define the generating function $C(z) = C_0 + C_1 z + C_2 z^2 + C_3 z^3 + \cdots$ . Reader can check that (by comparing coefficients)

$C(z) = z C(z)^2 + 1$

This is what we called "convolution" in the first paragraph. When someone multiplies two polynomials, to find the coefficient of $z^i$ , he has to multiply the term $x_j$ in the first polynomial to the term $x_{i-j}$ in the second polynomial. This "one increase, one decrease" property for polynomial multiplication gives the great convenience for the generating function to handle the convolution recurrence for Catalan numbers.

Now, the remaining task is purely algebraic. For $C(z) = z C(z)^2 + 1$ , treat $C(z)$ as a variable, then it becomes a quadratic equation. By quadratic formula, we have

$C(z) = \frac{1\pm\sqrt{1-4z}}{2z}$

Requiring $C(z)$ has no pole at $z=0$ , we reject $C(z)=\frac{1+\sqrt{1-4z}}{2z}$ and hence

$C(z)=\frac{1-\sqrt{1-4z}}{2z}$
Lastly, apply Newton's binomial theorem to $\sqrt{1-4z}$ , we arrive at the fact that

$C_n = [z^n] C(z) = -\frac{[z^{n+1}]\sqrt{1-4z}}{2} = -\frac{1}{2}\binom{\frac{1}{2}}{n+1} (-4)^{n+1}= -\frac{1}{2}\frac{\frac{1}{2}\times\frac{-1}{2}\times\frac{-3}{2}\times\cdots\times\frac{-(2n-1)}{2}}{(n+1)!}(-4)^{n+1}=(-1)^{2n+2}4^{n+1}\left(\frac{1}{2}\right)^{n+2}\frac{(1)(3)(5)\cdots(2n-1)}{(n+1)!}=2^n\frac{(2n)!}{2^n n! (n+1)!}=\frac{1}{n+1}\binom{2n}{n}$

數學資料庫手記

2009年3月20日星期五

Cylindrical projection, an Archimedes' result, and Duistermaat-Heckman Theorem

2009年3月9日星期一

Convolution Technique in Generating Function (1)

著作人

stat

網誌存檔

數學資料庫手記

2009年3月20日 星期五

Cylindrical projection, an Archimedes' result, and Duistermaat-Heckman Theorem

2009年3月9日 星期一

Convolution Technique in Generating Function (1)

著作人

stat

網誌存檔

2009年3月20日星期五

2009年3月9日星期一