張貼日期：Mar 24, 2016 2:46:43 PM
作者：沈俊嚴 副教授（國立台灣大學數學系）
「線～ 真希望有一天我可以變得跟你一樣。」
『你可以的！只要持續不斷地向前奔跑。』
「那.....我們會相遇嗎？」
『點～ 妳今天特別多問題哦 ^^ 嗯.....我想會吧！？從機率的角度來說。』
「相遇之後呢？」
『.....』
「是不是永遠也不再相見了呢...」
『.....永遠有多遠我看不見，如果有那麼一天.....請留在我懷裡，一起成為 Szemerédi 和 Trotter 眼中的一對戀人吧。』
Endre Szemerédi (手持獎盃)是當今最了不起的數學家之一，在離散數學和理論計算機科學領域都有卓越成就，影響深遠，獲頒 2012 年的阿貝爾獎 (Abel Prize)。圖為挪威國王哈拉爾德五世 (Harald V) 親自頒發 2012 年的阿貝爾獎給 Endre Szemerédi 照片。
組合幾何學 (combinatorial geometry)
簡單來說是在研究空間中一些集合的結構性。今天要介紹一個相當有趣且知名的結果，是關於在平面上"點"與"線"的邂逅，從線的角度來看，一條線可以跟許多點邂逅（相交）是天經地義的事，自古皆然阿，當然從公平的角度來看，一個點也可以和許多條線有一腿（相交），像這樣子的一對（點，線）就算做是一對戀人吧。(蝦密?! 也太快就歪掉了XD )
在平面上任意畫 N 條直線，任意給 M 個點，最多有多少對戀人的這個數量就用 I(M,N) 來表示。
首先，一個最簡單的上界是 I(M,N)≦MN ，因為最複雜的關係就是：
所有的點在所有的線上。
但是這當然不常發生，除非全部只有一個點而且所有的線經過此點；或者是只有一條線而所有的點落在這條線上。可是我們這裡當然要談的是，有非常多條線同時也有非常多個點。此時，問題馬上就變得極困難。
在 1983 年兩位數學家 Szemerédi 以及 Trotter [1] 給出了一個非常有意思的結果：
I(M,N)≦C(MN)2/3
這裡 C 是一個常數，跟 M 或 N 都無關。更重要的是，這個上界是"最佳"的上界。
要當數學家，必定都是腦袋充滿創意的人才行。像這樣子神奇又好玩的結果，數學家也不負眾望地給它取了一個非常有創意的名字，流傳於數學史上。那就是..........
Szemerédi-Trotter 相交定理!!!
Szemerédi-Trotter 相交定理!!!
Szemerédi-Trotter 相交定理!!!
是不是很有創意阿~~
William T. Trotter
Szemerédi 和 Trotter 當時提出的證明思路相當複雜，但是提供了許多前瞻性的概念。他們的想法也在後來被許多人推廣或是給了更簡單的證明，其中最簡單的方法當屬 Szekely 用一些基本圖論語言所給出的證明。他們的結果也被用在許多意想不到的地方.....
Erdős-Szemerédi 猜想
在這裡提此結果的一個相當漂亮的運用，這也是目前筆者最喜歡的證明之一。在此之前，我們先來簡單介紹另一個未解的問題，所謂的 Erdős-Szemerédi 猜想 [2]。
布達佩斯羅蘭大學出了非常多了不起的數學家，Erdős 和 Szemerédi 都是校友。
首先，在整數集合中，給定任意一個有限個數的子集合，用 A 來代表 (同時用｜Ａ｜來代表此集合的元素個數)。
例如 A = {8,11, 3, 9, 12, 25}，那麼｜Ａ｜= 6。
集合給定之後，考慮此集合裡面所有元素的相加跟相乘所形成的另外兩個集合，我們稱為加法集合跟乘法集合。用下面符號來代表
A + A = {a + b : a, b in A};
AA = {ab : a, b in A}
也就是說，A+A 這個集合裡面是把 A 集合裡面所有的元素相加；而 AA 這個集合裡面是把 A 集合裡面所有的元素相乘。
Erdős-Szemerédi 想要了解這兩個新的集合的個數跟原本的集合個數的有什麼關聯？不難想像，我們可以分別得到像這樣子的上下界
｜Ａ｜≦｜Ａ＋Ａ｜≦｜Ａ｜２
｜Ａ｜≦｜ＡＡ｜≦｜Ａ｜２
分別來看，這兩個式子的上界都很容易可以造出例子來達到。然而，兩位數學界的大大 Erdős 和 Szemerédi 憑著過人的洞察力，發現事情似乎沒有這麼單純，這兩個集合的元素既然出於同一源頭 A，會不會彼此互相牽引糾纏呢?
他們猜測：
不管 A 怎麼取，那麼加法集合｜Ａ＋Ａ｜或是乘法集合｜ＡＡ｜其中一定有一個集合的個數"幾乎"是｜Ａ｜２。
例如：A 是等差數列 A = {1, 2, 3, ..., 100}。我們可以立刻計算得到｜ＡＡ｜非常大，幾乎到了｜Ａ｜２這麼多。反過來看，如果我們取 A 為等比數列 A = {2, 4, 8, ... , 2100 } ，則變成 ｜Ａ＋Ａ｜非常大，幾乎到了｜Ａ｜２這麼多。
那有沒有其他的例子？當然有！但是相當複雜，在此不易說明，姑且相信我。
Elekes 的神來一筆
雖然 Erdős-Szemerédi 的猜測至今尚未完全解決，不過世界各地的數學家們可沒有因此沮喪，這裏我們要談的是數學家 Elekes 在1997 所證明的一個相關結果[3]。他的證明極具創意，利用了一個看似不相關的結論。
首先給定任意一個集合 A，我們建構下面的"線"集合
L = {y = a(x - b) : a, b in A}
也就是從 A 中給任意兩個元素 a 和 b，則建構一條直線為 y = a(x - b)。那麼此線集合 L 則有｜Ａ｜２這麼多條線。這是因為要嘛斜率不同或者截距不同。
如果要運用上述的 Szemerédi-Trotter 相交定理，我們還需要建構"點"集合，這裡直接定義"點"集合
P = (A + A) ╳ (AA)
意思是，P 集合裡的點 x 座標來自A + A 這個集合，而 y 座標來自 AA 這個集合。
除此之外， P 的元素個數是｜Ａ＋Ａ｜｜ＡＡ｜。
有了很多點和線，這時 Szemerédi-Trotter 相交定理開口說話了:
I(P,L) ≦ I(｜Ａ＋Ａ｜｜ＡＡ｜, ｜Ａ｜２) ≦ C(｜Ａ＋Ａ｜｜ＡＡ｜｜Ａ｜２)２/３
所以如果可以給 I(P, L) 一個下界，那麼結合上界跟下界，就可以得出｜Ａ＋Ａ｜｜ＡＡ｜的一個下界，進而得到｜Ａ＋Ａ｜或是｜ＡＡ｜其中一個的下界。那這裡 I(P, L) 的下界是什麼呢？
別忘了我們目前有｜Ａ｜２這麼多條線，但是每一條線"至少"經過點集合 P 中｜Ａ｜ 個點，因為每一條線的方程式是y = a(x - b)，a 和 b 已經固定。然而在 A 中取出任意一個元素 c，則此線經過 (b + c, ac)這個點，別忘了我們點的集合 P = (A + A) ╳ (AA)。因此，此點 (b + c, ac) 當然在 P 裡面，既然我們有｜Ａ｜這麼多種選擇 c 的方法，所以得到每條線 y = a(x - b) 在 P 裡面至少經過｜Ａ｜個點，而我們有｜Ａ｜２這麼多條直線。
換句話說，至少有｜Ａ｜２｜Ａ｜=｜Ａ｜3 這麼多對的點線戀人。
上面說了那麼多，也就是｜Ａ｜3 ≦ I(P,L)
結合 I(P,L) 的上下界，｜Ａ｜3 ≦ C(｜Ａ＋Ａ｜｜ＡＡ｜｜Ａ｜２)２/３ 。經過一些苦工，我們得出這樣一個結論:
A + A 或是 AA 至少其中一個的個數一定比｜Ａ｜５/４大。
雖然離猜測的 ｜Ａ｜２ 還有一段差距，不過這個可愛的證明還是令人感到相當的滿意阿。
幾何組合學中近期的重大進展
這類結果除了在平面上的點與線，我們還可以考慮其他的集合。例如說考慮更高的維度或者考慮點與圓的邂逅，這些結果往往都會有許許多多非常重要甚至意想不到的運用。除此之外，還可以在有限體的向量空間考慮這類問題，其中一個非常好的優點是，在有限體中的問題可以使用 Fourier analysis (富式分析)。
最後要提到是最近在幾何組合學中最重要的進展，是由兩位數學家 Larry Guth (麻省理工學院) 和 Nets Katz （加州理工學院) 所解決的 Erdős 距離問題：
N 個點之中總共有多少種不同的距離？
他們的論文發表在數學界最頂尖的期刊 Ann of Math 2015. ，受到 Elekes 的啟發，證明裡有許多非常關鍵的地方就是使用 Szemerédi-Trotter 相交定理。
註: Nets Katz 是我指導老師。 延伸閱讀
參考資料
[1] E. Szemerédi and W.T. Trotter (1983). "Extremal problems in discrete geometry". Combinatorica 3 (3–4): 381–392
[2] P. Erdős and E. Szemerédi (1983), "On sums and products of integers" (PDF), Studies in Pure Mathematics [3] G. Elekes (1997), "On the number of sums and products". Acta Arith. 81: 365–367