Helly's selection theorem

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 . 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 be any collection of 4 points in the plane. Then we can partition this collection into a disjoint union such that the convex hull of intersects the convex hull of .

(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 be any 4 points in the plane. Then one can find a set of labels , consisting of some of the numbers 1, 2, 3 and 4, such that the following is true: Let be the collection of points whose label is in , and let be the collection of the remaining points. Let be the smallest convex set containing all the points in , and be the smallest convex set containing all the points in . Then the two sets and 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 :




(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 is such a solution. By relabelling the points if necessary, we can assume that there is a certain label such that are all positive while are all less than or equal to 0.

Now from the first defining equation of , we have

.

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

From the second defining equation of , we have

.

Dividing both sides of the equation by , we get

.

But the left hand side of this equation is a convex linear combination of the points , and hence is in the convex hull of ; similarly the right hand side of the equation is in the convex hull of . This completes the proof of the lemma.

Next, we shall prove the theorem by induction on the number of convex sets involved. The theorem is of course trivial if . Suppose now the theorem has been proved for a certain . We shall prove the theorem for convex sets. Suppose we are given convex sets in the plane such that any 3 of them contain a common point. For each label from to , pick a point such that it belongs to all the convex sets except possibly . This is possible by our induction hypothesis. Now consider . By our lemma, relabeling our indices if necessary, we can assume that there exists a label , , such that the convex hulls of and contain a common point. Let's call this common point . Since belongs to the convex hull of , it belongs to for all ; here we make use of the assumptions that the sets are convex. Similarly, since belongs to the convex hull of , it belongs to for all . Hence is contained in all the sets , and this completes the proof.

The theorem actually holds in for any . One just needs to replace 3 by 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 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 ). 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 be a finite field. Suppose we are given a finite number of affine linear subspaces of where any 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.

天秤找假幣（四）

完成這個系列，我說說這個方法在計算機科學（Computer Science）的應用。

曾經有人說過，電腦有超過六成的時間是用來做排序（sorting）的。排序是指有一些不跟次序排列的數字，要根據遞升/遞降（ascending order/descending order）排好。當然實際上要排序的東西可以很多，例如字串（string）、集合（set）等，但在此不作討論。因為電腦用來做排序的時間很多，所以我們很希望想一些算法（algorithm）出來減少其運算時間。歷史上很快就找到一些O(n lg n)的comparison-based sorting方法，如配合binary search的insertion sort、merge sort等。但，有沒有更快的方法呢？

所謂comparison-based sorting，就是每次只可以比較兩個數字a和b，很到的結果是 a<= b是TRUE還是FALSE。 假設現在有n個未排好的數字，則它們的n! permutations都是有可能成為排序後的次序的。若使用樹形圖的概念，這即是說該樹形圖最少要有n!個「黃色格」。而因為每次比較的結果只有兩個可能性，故要達到有n!個「黃色格」，最少要有 log₂(n!) 層，亦即最少要做 log₂(n!) 次comparisons。根據Stirling's Formula， log₂(n!) 約等於 n ln (n) / ln 2 。這證明了 comparison-based sorting需要最少 O(n ln n) 時間。

P.S.: 這裏使用了一個叫"Big-Oh"的notation，未見過的人可在此參考。

天秤找假幣（三）

先看看以下兩張圖（按圖一下以看到清晰的圖像）：





第一張圖是有五個金幣，有一個是假（但不知是輕了還是重了），沒有已給定的真幣時，其中一個需要三次才能確保找出假幣的方法。這也是我在「天秤找假幣（一）」問的問題1(a)。

第二張圖是有五個金幣，有一個是假（但不知是輕了還是重了），有一個給定的真幣時，需要兩次能確保找出假幣的方法。這也是我在「天秤找假幣（一）」問的問題2。

---

在兩張圖，一開始時我們都不能確定哪一枚金幣是假，亦不能知道假幣是輕了還是重了。所以一開始時有10個可能性：1較輕、1較重、2較輕、2較重、3較輕、3較重、4較輕、4較重、5較輕、5較重。而在兩個樹形圖的最低部分，都有10個黃色格，表示這10個可能性。

因為我們是用天秤的，所以每次只有三個可能的結果：左邊較輕、左邊較重或兩邊等重，亦即是說在上面的樹形圖中，每個格最多只有三個在下方與它相連的格。若樹形圖只有一層，則最多只能有3¹=3個黃色格；若樹形圖有兩層，則最多有3²=9個黃色格；若樹形圖有三層，則最多有3³=27個黃色格。

因為兩個情況下我們都會有最少10個黃色格（對應剛說明的10個可能性），所以樹形圖最少有三層，亦代表最少秤三次才能找出假幣，並判斷它比真幣重了還是輕了。

---

但我們的問題並不需要判斷假幣是重了還是輕了。所以當遇到上圖的藍色格時，我們已經知道哪個金幣是假，即使不知道它是重了還是輕了，我們也完成了任務。因此在第二張圖，我們最多只需秤兩次。

在上次的問題1(b)，我們最少會有12個藍色格，因此樹形圖最少有三層，亦代表最少要秤三次才能找出假幣。若我們要求找出假幣是輕了還是重了，則我們要有最少24個黃色格，也是最少三層的樹形圖也能做到這點，而上一次我們已說了用三次秤的方法，大家有興趣不妨根據那個方法畫畫相對的樹形圖。

---

但在問題1(a)，我們可能可以有5個藍色格，那樣兩層的樹形圖是可行的。為甚麼我宣稱秤兩次是不可能呢？這需要用到另一個技巧：backward induction。

在問題1(a)，我們一開始只可能有兩種放法：1 vs 2 或 1,2 vs 3,4（這裏指每邊放一個金幣或每邊放兩個金幣；其他的放法不會給我們帶來任何information）。

若使用 1 vs 2 而兩邊等重時，則我們所遇的問題變成：「有三個幣，其中一個是假（不知輕重），而有兩個確定為真的金幣」。這時我們可以考慮的秤的方法並不多，只有 3 vs 4、1 vs 3、 1,3 vs 4,5 、 1,3 vs 2,4。易証使用四種方法均不能只秤一次就保証判斷到假幣。

若使用 1,2 vs 3,4而兩邊並非等重時，1、2、3、4都有可能是假幣，根據我剛剛介紹的「樹形圖分析」，只少要多秤兩次，即要解決整個問題需要秤三次。

MATH161大發現

MATH161是科大的一個數學通識科（謎之聲：數學都有通識？！）。

D. Hilbert:

It must always be possible to substitute 'table', chair' and 'beer mug' for 'point', line' and 'plane' in a system of geometrical axioms.

看似很玄的一句哩！但其實是很實在、有意思的。甚至我們可以找到例子，來說明「點即是線，線即是點」這一大佛理。:P

說起佛理，最近見到有人用物理的Ohm's Law證明「色即是空，空即是色」。:P

有時間說說希爾伯特這句的意義吧，最近忙著各種瑣碎的事呢。

另外鄭院長用了一個非常有名的舊遊戲去解釋甚麼是projective plane。知道projective plane的人能猜到這個遊戲嗎？

Polynomial FLT and Beyond

The classical Fermat's Last Theorem says if n >= 3, then the equation x^n + y^n = z^n admits no positive integer solutions.

Here is the polynomial version of Fermat's Last Theorem:

Theorem(Polynomial FLT):
Suppose a, b, c are in C[t] (i.e. polynomials with complex coefficients) such that gcd(a, b, c) = 1. (simply means that they do not have a common complex root) For n >= 3, then a^n + b^n = c^n for all t in C implies a, b, and c are constant polynomials.

The proof of this theorem usually uses the following so-called ABC conjecture for function fields, whose proof is totally elementary.

Theorem(Mason)
Suppose a, b, c in C[t] such that (a, b, c) = 1. If a + b = c, then we have:
max{deg(a), deg(b), deg(c)} <= N(abc) - 1, where N(f) denotes the number of distinct complex roots of f.

I will not prove this here as you will probably see the proof during the upcoming talk.

However, I shall give a short proof of the polynomial FLT using Mason's theorem:

Proof of Polynomial FLT: Let n >= 3, we have N(a^n*b^n*c^n) = N(abc). Mason's theorem yields:

n deg(a) = deg(a^n) <= max{deg(a^n), deg(b^n), deg(c^n)} <= N(abc) - 1 <= deg(a) + deg(b) + deg(c) - 1.

Therefore, we have:

n(deg(a) + deg(b) + deg(c)) <= 3(deg(a) + deg(b) + deg(c)) - 3 <= n(deg(a) + deg(b) + deg(c)) - 3, where the last inequality follows from the fact that 3 <= n. This is a contradiction and we are done.

Next, we go a step further. It is now known that if a, b, c are polynomials in t with coefficients in C, then a^n + b^n = c^n has no constants solution if n >= 3. We ask ourselves whether the same holds if a, b, c are allowed to be entire functions. That is a, b, c are power series in t with coefficients in C. The answer is no if n = 3, and yes if n >= 4.

To this end, we change notation a little bit and we write f = a/c, and g = b/c, where f, g are now meromorphic functions in C. We ask whether f^n + g^n = 1 forces f, and g to be constant functions.

For n = 3, we can transform the equation f^3 + g^3 = 1 into an equation of the form: Y^2 = X^3 - 432, via setting f = (36 - Y)/6X, g = (36 + Y)/6X.

E: Y^2 = X^3 - 432 can be realized as an elliptic curve, and it's a well known theorem in elliptic curve that we have an analytic isomorphism:

C/L -> E(C),

where L = {aw_1 + bw_2 | a, b in Z, and w_1, w_2 are linearly independent over R}, and E(C) = complex points in E. As an example, L could be Z[i] the Gaussian integers for example.

This isomorphism is given by the map: z |-> (p(z), p'(z)), where p(z) is the Weierstrass p-function, which is meromorphic in C with double poles precisely at the points in L.

Now, via this isomorphism, we will get non-constant f, g in terms of p(z), and p'(z).

As for n >= 4, the theorem is true and here is a quick proof using theory in compact Riemann surface.

First we know that f = (1 - g^n)^{1/n} defines a compact Riemann surface of genus g >= 2 (since n >= 4) [In fact, it can be shown that f^n + g^n = 1 has genus g = (n - 1)(n - 2)/2.

Let S denotes this Riemann surface. Therefore, we have a meromorphic map f : C to S. Next, we resort to the uniformization theorem which asserts that the universal cover of S is D, the open unit disc since g >= 2. Since D is actually a universal cover, and that C is simply connected, we have a meromorphic lift j: C to D. By Liouville's theorem (or by Picard if one wishes), j must be constant and hence the covering map from D to S is also constant and therefore f is constant. This concludes the proof.

數學講座

日期：2008 年 4 月 18 日（星期五）
時間：下午 6 時 15 分至 8 時
地點：教育局九龍塘教育服務中心西座四樓演講廳
講者：岑嘉評教授
講題：多項式費馬大定理的簡單証明

有關其他詳情及報名方法，可瀏覽 http://gifted.hkedcity.net/Gifted/Enroll/2008MathsCampTalk/index.html#content。

天秤找假幣（二）

最近忙了一點，今次先說說三題的「最佳」答案，下次才說怎樣證明為「最佳」。

說起「最佳」，我的原意是「最少用多少次天秤就能確定能找出假幣？」。網友Pop在上一篇文章留言用了另一個方法看「最佳」，就是「平均用多少次天秤就能確定能找出假幣？」。大家可以到上一篇文章的「意見」看一看。

1) a)

Pop在上一篇文章說了方法，最壞情況需要三次。

1) b)

先在天秤兩邊每邊任意放四個金幣。

若然兩邊重量一樣，則可確定不在天秤上的四個幣其中一個是假的。只需要多用兩次天秤，便能從這四個幣中判出哪個是假（這個不難，自己想一想吧）。

若然兩邊重量不一樣，定義在較輕那邊的四個幣為L1, L2, L3, L4；在較重那邊的四個幣為H1,H2,H3,H4。

把L1,L2,H1放在一邊，L3,L4,H2放在另一邊。若然兩邊重量一樣，則H3是假幣或H4是假幣。那麼只要將H3和H4秤一次，哪個較重就是假的。若然兩邊重量不一樣，不失一般性，設L1,L2,H1那邊較輕。那麼只可能出現以下情況：

i) L1是假幣，比真幣輕
ii) L2是假幣，比真幣輕
iii) H2是假幣，比真幣重

只需將L1和L2秤一次，若兩邊重量一樣，是情況iii)；若L1比L2輕，是情況i)；若L1比L2重，是情況ii)。

故最壞情況也是三次。

2)

設已確定為真的幣為N，而其餘五個幣的編號為1,2,3,4,5。

先將N和1放在一邊，2和3放在另一邊。若兩邊重量一樣，則4為假幣或5為假幣。之後將N和4一起秤，若重量一樣則5為假幣；若重量不同則4為假幣。

若 N和1 比 2和3 輕，則只會出現以下三種情況：
i) 1 是假幣，比真幣輕
ii) 2是假幣，比真幣重
iii) 3是假幣，比真幣重

若 N和1 比 2和3 重，則只會出現以下三種情況：
i) 1是假幣，比真幣重
ii) 2是假幣，比真幣輕
iii) 3是假幣，比真幣輕

兩組的「三種情況」均可以用一次天秤就能判別哪個是假幣，而且方法非常簡單（跟 1) b) 最後一部分類似），故略。


看了解答後，我相信部分人會有一點疑惑：1) a)只有五個幣，1) b)有十二個幣，怎麼「最佳」的解法都是三次？這不敢令人對1) a)的「最佳」解法質疑。所以，數學人必須證明它是「最佳」！

下次我便說說證明「最佳」的方法，並簡介一下這個方法解決了一個Computer Science基本但非常重要的問題。