用户: 数学迷/组合数学中的奇妙构造

组合数学有时会意想不到地用到数论或代数几何中的大定理来构造特定组合结构. 哲学上这可以认为是一种 “组合结构无处不在”. 讲义: 极值图论基础中已有几个例子; 这里记录一些我所看到的.

下面的构造是在 ${\mathbb{R}}^n$ 中放进很多单位向量, 使其两两内积很小, 为 $n^{-1/2}$ 级别.

定理 1. 对素数幂 $q$ 以及自然数 $d$, ${\mathbb{R}}^{2q}$ 中有 $q^d$ 个单位向量, 两两内积不超过 $(d-1)q^{-1/2}$.

证明. 将 ${\mathbb{R}}^{2q}$ 视为 ${\mathbb{C}}^{{\mathbb{F}}_q}$, 即 ${\mathbb{F}}_q$ 上的复值函数. 考虑标准加法特征 $\psi :{\mathbb{F}}_q\to {\mathbb{C}}^{\times }$, 定义为$$\psi (x)={\zeta }_p^{{\mathrm{Tr}}_{{\mathbb{F}}_q/{\mathbb{F}}_p}(x)},$$则一个满足要求的构造是$$x\mapsto q^{-1/2}\psi (a_d{x}^d+\cdots +a_{1}x),a_1,\dots ,a_d\in {\mathbb{F}}_q.$$这自然是 ${\mathbb{C}}^{{\mathbb{F}}_q}$ 中 $q^d$ 个单位向量. 它们两两内积不超过 $(d-1)q^{-1/2}$ 无非相当于说, 对任一不超过 $d$ 次的非常值多项式 $f\in {\mathbb{F}}_q[x]$, $$\left|\sum _{x\in {\mathbb{F}}_q}\psi (f(x))\right|\le (d-1)q^{1/2}.$$这本质上是 Weil 猜想. 回忆 Artin–Schreier 映射 $x\mapsto x-x^q$ 是 ${\mathbb{A}}_{{\mathbb{F}}_q}^1$ 到自身的正规平展覆叠, Galois 群为 ${\mathbb{F}}_q$. 取定素数 $\ell \nmid q$ 以及同构 $\mathbb{C}\cong \overline{{\mathbb{Q}}_{\ell }}$, 则 $\psi$ 复合上 Artin–Schreier 给出的满射 ${\pi }_1({\mathbb{A}}_{{\mathbb{F}}_q}^1,0)\to {\mathbb{F}}_q$ 便得到基本群 ${\pi }_1({\mathbb{A}}_{{\mathbb{F}}_q}^1,0)$ 的 $\overline{{\mathbb{Q}}_{\ell }}$-表示, 对应 ${\mathbb{A}}_{{\mathbb{F}}_q}^1$ 上的 $\overline{{\mathbb{Q}}_{\ell }}$-局部系, 记作 $\mathcal{L}$. 不难发现几何 Frobenius 在 ${\mathcal{L}}_x$, $x\in {\mathbb{F}}_q$ 处的作用是 $\psi (x)$. 现将多项式 $f$ 视为 ${\mathbb{A}}_{{\mathbb{F}}_q}^1$ 到自身的映射, 则由于 $(f^{\ast }\mathcal{L}{)}_x={\mathcal{L}}_{f(x)}$, 几何 Frobenius 在其上的作用是 $\psi (f(x))$. 于是$$\sum _{x\in {\mathbb{F}}_q}\psi (f(x))=\mathrm{Tr}(\mathrm{Frob}|R{\Gamma }_{\text{c}}({\mathbb{A}}_{\overline{{\mathbb{F}}_q}}^1,f^{\ast }\mathcal{L})).$$由于 ${\mathbb{A}}^1$ 不紧, $H_{\text{c}}^0({\mathbb{A}}_{\overline{{\mathbb{F}}_q}}^1,f^{\ast }\mathcal{L})=0$; 由 Poincaré 对偶, $H_{\text{c}}^2({\mathbb{A}}_{\overline{{\mathbb{F}}_q}}^1,f^{\ast }\mathcal{L})=H^0({\mathbb{A}}_{\overline{{\mathbb{F}}_q}}^1,f^{\ast }\mathcal{L}{)}^{\vee }(-1)=0$, 因为 $f^{\ast }\mathcal{L}$ 非平凡, 没有整体截面 (这大抵是因为它在 $\infty$ 比较分歧). 而由 Weil 猜想, $\mathrm{Frob}$ 在 $H_{\text{c}}^1$ 的特征值模长都是 $q^{1/2}$, 故只需证$$\dim H_{\text{c}}^1({\mathbb{A}}_{\overline{{\mathbb{F}}_q}}^1,f^{\ast }\mathcal{L})\le d-1.$$这要等我学会算 Swan 导子之后再写.

$\square$