數學資料庫手記: 4月 2008

最近在科大旁聽functional analysis，偶然會聽到一些數學的歷史故事。

有一個叫Lomonosov的人，在俄羅斯讀大學，上課時遲到，去到課室時教授和學生們都走了，只見到兩塊黑板上，第一塊寫住一條問題，而另一塊則寫著一些topology關於fixed points的定理。Lomonosov也不管三七廿一，把這些東西都抄到筆記裏。他以為那條問題是教授給的功課，於是開始努力想著。最後，他用了那些關於fixed points的定理解決了。

下一堂，他把題解交給教授。但……

其實那條問題是一條幾十年未有人破的open problem，當時教授只是寫在黑板上說這是open problem。而另一塊黑板關於fixed points的定理，其實是再對上一堂另一個教授教書時寫的……

Yesterday a friend of mine showed me a very cute and completely elementary fact about convex sets in the plane, and perhaps I could share it here. It's a classical theorem due to Helly. It actually works in arbitrarily high dimensions, but for clarity of exposition let's restrict ourselves to the Euclidean plane $\mathbb{R}^2$ . The theorem is the following:

If we are given a finite number of convex sets in the plane and any 3 of them contain a common point, then there is a point that is common to all these convex sets.

You may wish to draw a picture to convince yourself of this theorem before proceeding.

The proof is based on the following lemma:

Let $\{x_1, x_2, x_3, x_4\}$ be any collection of 4 points in the plane. Then we can partition this collection into a disjoint union $A_1 \cup A_2$ such that the convex hull of $A_1$ intersects the convex hull of $A_2$ .

(If some of you are not familiar with the notions used in the above statement, here is another (more clumsy) way of saying the same thing: Let $x_1, x_2, x_3, x_4$ be any 4 points in the plane. Then one can find a set of labels $I$ , consisting of some of the numbers 1, 2, 3 and 4, such that the following is true: Let $A_1$ be the collection of points $x_i$ whose label $i$ is in $I$ , and let $A_2$ be the collection of the remaining points. Let $H_1$ be the smallest convex set containing all the points in $A_1$ , and $H_2$ be the smallest convex set containing all the points in $A_2$ . Then the two sets $H_1$ and $H_2$ contain a common point.)

The proof of the lemma is based on the following linear algebra argument:

Consider the system of 3 linear equations in 4 unknown real numbers $a_1, a_2, a_3, a_4$ :

$a_1+a_2+a_3+a_4= 0$
$a_1x_1+a_2x_2+a_3x_3+a_4x_4 = 0$

(The second equation is a vector equation in the plane, so it actually represents two linear equations.)

A well-known linear algebra fact is that if you have 3 linear equations in 4 unknowns, you can always find a non-zero solution to the equation. Suppose by abuse of notation $a_1, a_2, a_3, a_4$ is such a solution. By relabelling the points if necessary, we can assume that there is a certain label $k$ such that $a_1, \dots, a_k$ are all positive while $a_{k+1}, \dots, a_4$ are all less than or equal to 0.

Now from the first defining equation of $a_1, a_2, a_3, a_4$ , we have

$a_1 + \dots + a_k = -a_{k+1} - \dots - a_4\right)$ .

Since we assumed $a_1, a_2, a_3, a_4$ is a non-zero solution, the quantity on the left hand side of the above equation must be positive. Let's call it $s$ .

From the second defining equation of $a_1, \dots, a_4$ , we have

$a_1x_1+\dots+a_kx_k= -a_{k+1}x_{k+1}-\dots-a_4x_4$ .

Dividing both sides of the equation by $s$ , we get

$\frac{a_1x_1+\dots+a_kx_k}{s}= \frac{-a_{k+1}x_{k+1}-\dots-a_4x_4}{s}$ .

But the left hand side of this equation is a convex linear combination of the points $x_1, \dots, x_k$ , and hence is in the convex hull of $x_1, \dots, x_k$ ; similarly the right hand side of the equation is in the convex hull of $x_{k+1}, \dots, x_4$ . This completes the proof of the lemma.

Next, we shall prove the theorem by induction on the number $N$ of convex sets involved. The theorem is of course trivial if $N = 3$ . Suppose now the theorem has been proved for a certain $N \geq 3$ . We shall prove the theorem for $N+1$ convex sets. Suppose we are given $N+1$ convex sets $S_1,\dots,S_{N+1}$ in the plane such that any 3 of them contain a common point. For each label $i$ from $1$ to $N+1$ , pick a point $x_i$ such that it belongs to all the $N+1$ convex sets except possibly $S_i$ . This is possible by our induction hypothesis. Now consider $x_1,x_2,x_3,x_4$ . By our lemma, relabeling our indices if necessary, we can assume that there exists a label $k$ , $1 \leq k < 4$ , such that the convex hulls of $x_1,\dots,x_k$ and $x_{k+1},\dots,x_4$ contain a common point. Let's call this common point $x$ . Since $x$ belongs to the convex hull of $x_1,\dots,x_k$ , it belongs to $S_j$ for all $j>k$ ; here we make use of the assumptions that the sets $S_j$ are convex. Similarly, since $x$ belongs to the convex hull of $x_{k+1},\dots,x_4$ , it belongs to $S_j$ for all $j\leqk$ . Hence $x$ is contained in all the $N+1$ sets $S_1,\dots,S_{N+1}$ , and this completes the proof.

The theorem actually holds in $\mathbb{R}^n$ for any $n$ . One just needs to replace 3 by $n+1$ in the statement of the theorem. The proof and the lemma works equally well in high dimensions; one just needs to replace every 4 by $n+2$ there.

One interesting question came out of my discussion with my friend though. Suppose now we are in a finite dimensional vector space over a finite field (instead of $\mathbb{R}$ ). It of course doesn't make sense to talk about convexity there. However, we may replace "convex sets" by "affine linear subspaces" (translates of vector subspaces) and ask the following question:

Let $F$ be a finite field. Suppose we are given a finite number of affine linear subspaces of $F^n$ where any $n+1$ of them intersect. Must the intersection of all the given affine linear subspaces be non-empty?

I am not sure how interesting or difficult this problem is; perhaps there is a really easy solution to this problem, and we haven't put much effort into thinking about it anyway. But if some of you come up with any idea on how to approach or solve the problem, I'd be interested to know.

數學資料庫手記

2008年4月29日星期二

數學歷史故事（一）

2008年4月24日星期四

數學雜記

2008年4月21日星期一

Helly's selection theorem

著作人

stat

網誌存檔