凸幾何與離散幾何

數的幾何(geometry of numbers)

數論問整數及其組合;幾何問形狀與體積。數的幾何是閔可夫斯基的發現:你可以把整數畫成規則格點陣,藉著推理哪些凸形狀被迫含有格點,來回答困難的算術問題。它把「這個方程有整數解」之類的陳述,轉成「這個凸體大到無法錯過格」之類的陳述,用凸幾何的視覺、以體積為本的推理來換掉代數。

舞台是 R^n 中的格 L——某固定基的所有整係數組合,一個完全週期的點陣,其協體積 d(L) 度量每點所占體積。兩根支柱是閔可夫斯基的定理。第一:體積超過 2^n d(L) 的中心對稱凸體必含一個非零格點。第二支配對稱凸體 K 的相繼極小 lambda_1 <= ... <= lambda_n——K 首次捕獲 1, 2, ..., n 個線性獨立格點的最小膨脹——限制其乘積:(2^n/n!) d(L) <= lambda_1 ... lambda_n vol(K) <= 2^n d(L)。約化理論(埃爾米特、閔可夫斯基,以及演算法 LLL)提供「短而近乎正交」的基,使格中隱藏的短向量變得可見且可計算。

回報橫跨純粹與應用數學。古典上它證明拉格朗日四平方定理、狄利克雷逼近定理,以及代數數論中類數與單位群的有限性(閔可夫斯基界、狄利克雷單位定理)。現代的格支撐球填充(8 維與 24 維的最佳填充是 E8 與利奇格)、整數規劃,以及格密碼學,其安全性建立在尋找短格向量被推測為困難之上。一個誠實的提醒:「數的幾何」命名的是一套方法與觀點、而非單一定理;它的威力是真的,但它的界往往不銳利,而在一般高維格中尋找最短向量被認為在計算上難解——這正是密碼學家鍾愛它的緣故。

狄利克雷逼近定理的幾何化:要用分數 p/q 逼近實數 alpha,在 R^2 中考慮對稱凸區域 |q| <= Q 且 |q*alpha - p| <= 1/Q,一個面積為 4 的細平行四邊形。由閔可夫斯基第一定理(面積 4 = 2^2 乘協體積 1)它含一個非零整數點 (p, q),給出 |alpha - p/q| <= 1/(q*Q) <= 1/q^2——一個良好的有理逼近,純由體積計數變出。

一個面積為 4 的細平行四邊形必含格點,給出 |alpha - p/q| <= 1/q^2。

它是一種觀點與工具箱、而非單一定理,其體積界一般並非最優。在高維格中尋找真正最短的向量被推測為困難(在隨機化約化下為 NP 難)——這是後量子格密碼學的基礎,而非待修補的缺陷。

又称
Minkowski's geometry of numbersGeometrie der Zahlen數論幾何方法