经典网文分享: Geometry. I. Finite Field Kakeya Problem

前一阵和本科室友（目前在做调和分析）聊到了Kakeya问题，在这里简单写一下。

Kakeya问题是在问，在 $\mathbb{R}^n$ 上"全方位"转动指针，指针划过的面积最小是多少。换句话说，一个Kakeya set $K\subseteq \mathbb{R}^n$ 满足其包含任意方向的单位向量（比如一个半径为 $1/2$ 的球），那么 $K$ 最小有多大？

Besicovitch很出人意料的证明了 $K$ 的测度可以是0 。目前的主要猜想是 $K$ 的Hausdorff维数是 $n$ 。这个猜想应该是调和分析里面最难的猜想之一了。

回到finite field。我们有如下定义：

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

也就是说，对任意 $a$ ，存在 $b$ 使得 $\{at+b\mid\forall t\in\mathbb{F}_q\}\subseteq K$ 。可以看到全空间是Kakeya的。那么， $K$ 可不可能比全空间显著的小？

Theorem (Dvir).
A Kakeya set $K\subseteq \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$ ，于是这个多项式恒为零，矛盾。

来源：知乎 www.zhihu.com
作者：Yifan

【知乎日报】千万用户的选择，做朋友圈里的新鲜事分享大牛。点击下载

经典网文分享

Geometry. I. Finite Field Kakeya Problem

没有评论:

发表评论