Geometry. I. Finite Field Kakeya Problem

06-03

來自專欄 Some Interesting Combinatorial Problems

前一陣和本科室友（目前在做調和分析）聊到了Kakeya問題，在這裡簡單寫一下。

Kakeya問題是在問，在 $mathbb{R}^n$ 上「全方位」轉動指針，指針划過的面積最小是多少。換句話說，一個Kakeya set $Ksubseteq mathbb{R}^n$ 滿足其包含任意方向的單位向量（比如一個半徑為 $1/2$ 的球），那麼 $K$ 最小有多大？

Besicovitch很出人意料的證明了 $K$ 的測度可以是0 。目前的主要猜想是 $K$ 的Hausdorff維數是 $n$ 。這個猜想應該是調和分析裡面最難的猜想之一了。

回到finite field。我們有如下定義：

Definition.
A set $Ksubseteq mathbb{F}_q^n$ is called a Kakeya set if it contains a line in every direction.

也就是說，對任意 $a$ ，存在 $b$ 使得 ${at+bmidforall tinmathbb{F}_q}subseteq K$ 。可以看到全空間是Kakeya的。那麼， $K$ 可不可能比全空間顯著的小？

Theorem (Dvir).

A Kakeya set $Ksubseteq mathbb{F}_q^n$ has at least $c_nq^n$ elements, where $c_n=(10 n)^{-n}$ .

證明說起來很容易。在Dvir證明之前，這個問題被認為和 $mathbb{R}^n$ 中的Kakeya問題有同等的難度，所以Dvir的證明可以說震驚了數學界。不過對於這個問題，目前還沒有可以不使用多項式的證明。在不讓用多項式方法的情況下，這個問題還是個絕世難題的..

證明需要兩個facts。第一個是說，對於一個點集 $S$ ，存在一個次數不高的非零多項式，以 $S$ 中的每個點為根；第二個是說，對於一個次數為d的一元多項式，如果有 $d+1$ 個根，那麼這個多項式是0 。

設 $P_d^n$ 是 $mathbb{F}^n$ 上的 $n$ 元次數不超過 $d$ 的多項式組成的空間， $S$ 是 $mathbb{F}^n$ 的一個子集，那麼如果 $dim P_d^n>|S|$ ，則存在 $P_d^n$ 中多項式，以 $S$ 中所有點為根。這大概是一個大一線性代數習題的難度。

值得一提的是上面的Lemma雖然簡單，但是並不顯然。比如考慮 $mathbb{R}^2$ 上的次數最低的二元多項式，使得他的根包含所有的點 $(j,2^j)$ ，對 $j=1,2,dots,10^6$ 。我們可以構造出下面兩個滿足條件的多項式：

$p_1(x_1,x_2)=prod_{i=1}^{10^6}(x_1-i)$

$p_2(x_1,x_2)=prod_{i=1}^{10^6}(x_2-2^i)$

這樣看起來，貌似最小次數多項式的次數大概就是 $10^6$ 上下了，很難構造出再小的多項式了。然而上面的引理告訴我們，存在次數不超過 $2000$ 的多項式滿足條件。

回到finite field Kakeya problem的證明。假設 $K$ 足夠小，小於定理敘述的值。通過上述的多項式零點引理，存在一個次數小於 $q$ 的非零多項式，使得其在 $K$ 上值為 $0$ 。然後我們給這個多項式的每個變數賦值 $at+b$ ，得到了一個同樣次數的一元多項式。根據Kakeya set定義， $mathbb{F_q}$ 上的每個點都是這個多項式的根，又由於次數小於 $q$ ，於是這個多項式恆為零，矛盾。