8. 下界: 随机代数构造

到目前为止, 我们已经看到了使用随机图和代数结构的两种构造方法. 在本节中, 我们将展示由 Bukh 提出的 $K_{s,t}$-free 图的另一种构造 (2015) , 对于某些函数 $t_0$, 在 $t>t_0(s)$ 条件下将有 $\Theta \left(n^{2-\frac{1}{s}}\right)$ 条边. 这是一个添加了一些随机性的代数结构.

首先, 固定 $s\ge 4$ 并取一个素数 $q$. 令 $d=s^2-s+2$, $f\in {\mathbb{F}}_q\left[x_1,x_2,\dots ,x_s,y_1,y_2,\dots ,y_s\right]$ 是一个在 $X=\left(x_1,x_2,\dots ,x_s\right)$ 和 $Y=\left(y_1,y_2,\dots ,y_s\right)$ 上的次数均小于等于 $d$ 的多项式中均匀随机选择的一个多项式. 将 $G$ 的顶点集分为数量相等的两部分: $L=R={\mathbb{F}}_q^s$. 定义边关系为 $(X,Y)\in L\times R$ 当且仅当 $f(X,Y)=0$.

引理 8.1. 对于所有 $u,v\in {\mathbb{F}}_q^s$ 和如上所述随机选择的 $f$,$$\mathbb{P}[f(u,v)=0]=\frac{1}{q}.$$

证明. 注意到如果 $g$ 是 ${\mathbb{F}}_q$ 上一个均匀随机选择的常数, 则 $f(u,v)$ 和 $f(u,v)+g$ 是同分布的. 因此, 每个取值的概率都为 $1/q$.

$\square$

现在边数的期望是我们想要的: $\mathbb{E}[e(G)]=\frac{n^2}{q}$. 我们还需要保证 $K_{s,t}$ 的副本数较小. 为此, 我们必须回答以下问题: 对于 $L$ 中大小为 $s$ 的一组顶点, 它可以有多少个共同的邻点?

引理 8.2. 假设 $r,s\le \min (\sqrt{q},d)$ , $U,V\subset {\mathbb{F}}_q^s$ 且 $|U|=s$ 和 $|V|=r$. 此外, 令 $f\in {\mathbb{F}}_q\left[x_1,x_2,\dots ,x_s,y_1,y_2,\dots ,y_s\right]$ 是一个在 $X=\left(x_1,x_2,\dots ,x_s\right)$ 和 $Y=\left(y_1,y_2,\dots ,y_s\right)$ 上次数均小于等于 $d$ 的多项式中均匀随机选出的一个多项式. 则$$\mathbb{P}[\text{ 对所有 }u\in U,v\in V,f(u,v)=0]=q^{-sr}.$$

证明. 首先让我们考虑 $U$ 中所有点的第一个坐标都不同和 $V$ 中所有点的第一个坐标都不同的特殊情况. 定义$$g\left(X_1,Y_1\right)=\sum _{\genfrac{}{}{0ex}{}{0\le i\le s-1}{0\le j\le r-1}}{a}_{ij}{X}_1^i{Y}_1^j$$$a_{ij}$ 是 ${\mathbb{F}}_q$ 上独立同分布的均匀随机变量. 我们要证明 $f$ 和 $f+g$ 具有相同的分布, 只需证明对于任意的 $b_{uv}\in {\mathbb{F}}_q$ ( $u\in U,v\in V$) , 存在 $a_{ij}$ 使得对于任意的 $u\in U,v\in V$ 有 $g(u,v)=b_{uv}$ . 证明的思路是应用两次拉格朗日插值. 首先, 任取一个 $u\in U$, 我们可以找到一个阶数最多为 $r-1$ 的单变量多项式 $g_u\left(Y_1\right)$ 使得对于所有的 $v\in V$ 有 $g_u(v)=b_{uv}$ . 然后我们可以将 $g\left(X_1,Y_1\right)$ 看作 $Y_1$ 的多项式, 其中系数是 $X_1$ 中的多项式, 即, $$g\left(X_1,Y_1\right)=\sum _{0\le j\le r-1}{a}_j\left(X_1\right)Y_1^j$$再次应用 Lagrange 插值定理, 我们可以找到多项式 $a_0,a_1,\dots ,a_{r-1}$ 使得 $g\left(u,Y_1\right)=g_u\left(Y_1\right)$ 对于所有的 $u\in U$ 成立.

现在假设 $U$ 中所有点的第一个坐标不一定都不同和 $V$ 中所有点的第一个坐标不一定都不同. 我们只需找到线性映射 $T,S$: ${\mathbb{F}}_q^s\to {\mathbb{F}}_q^s$ 满足 $TU$ 和 $SV$ 像中所有点的第一个坐标都不同. 下面让我们证明这样的映射 $T$ 存在. 如果我们找到一个线性映射 $T_1:{\mathbb{F}}_q^s\to {\mathbb{F}}_q$ 将 $U$ 的元素映射到不同的元素, 那么我们可以通过使用 $T_1$ 作为第一个坐标将 $T_1$ 扩展成 $T$. 我们在所有线性映射中均匀随机的选择出 $T_1$, 那么 $U$ 中的每一对冲突的概率是 $\frac{1}{q}$. 所以通过联合边界我们成功的概率至少是 $1-\left(\genfrac{}{}{0ex}{}{|U|}{2}\right)\frac{1}{q}>0$, 所以这样的映射 $T$ 存在. 同理存在映射 $S$.

$\square$

固定 $|U|=s$ , 其中 $U\subset {\mathbb{F}}_q^s$. 我们希望给出 $U$ 的共同邻点的数量的上界. 我们将使用矩方法实现这一点. 令 $I(v)$ 为指示变量, 当 $v$ 是 $U$ 的公共邻点时恰好为 $1$. 令 $X$ 为 $U$ 的公共邻点的数量. 借助引理 8.2, $$\begin{array}{rl}\mathbb{E}\left[X^d\right]=\mathbb{E}\left[{\left(\sum _{v\in {\mathbb{F}}_q^s}I(v)\right)}^d\right]& =\sum _{v_1,\dots ,v_d\in {\mathbb{F}}_q^s}\mathbb{E}\left[I\left(v_1\right)\cdots I\left(v_d\right)\right]\\ & =\sum _{r\le d}\left(\genfrac{}{}{0ex}{}{q^s}{r}\right)q^{-rs}{M}_r\le \sum _{r\le d}{M}_r=M\end{array}$$其中 $M_r$ 定义为从 $[d]$ 到 $[r]$ 的投影数 ¹, $M={\sum }_{r\le d}{M}_r$ . 使用 Markov 不等式我们得到$$\mathbb{P}(X\ge \lambda )\le \frac{\mathbb{E}\left[X^d\right]}{{\lambda }^d}\le \frac{M}{{\lambda }^d}$$

现在, 即使 $X$ 的期望值很小, 我们也不能确定 $X$ 很大的概率很小. 例如, 如果我们采用带有 $p=n^{-\frac{1}{s}}$ 的随机图, 那么 $X$ 的期望值会很低, 但是会有一条长而平滑的衰减尾部.

事实证明, 代数几何理论帮助我们阻止了公共邻点 $X$ 的数量可以取任意值. 公共邻点由一组多项式方程的零点确定, 因此变成了一个代数问题. 直觉告诉我们, 我们要么处于 $X$ 非常小的 “零维” 情况, 要么处于 $X$ 至少在 $q$ 数量级的 “正维” 情况.

引理 8.3 (Bukh 2015). 对于所有 $s,d$ , 存在一个常数 $C$ 使得如果 $f_1(Y),\dots ,f_s(Y)$ 是 ${\mathbb{F}}_q^s$ 上阶数最大为 $d$ 的多项式, 则$$\left\{y\in {\mathbb{F}}_q^s\mid f_1(y)=\dots f_s(y)=0\right\}$$集合的大小满足以下两者之一: 最大为 $C$ 或者最少为 $q-C\sqrt{q}$.

引理 8.3 可以由代数几何重要结论 Lang-Weil 界 ²推导出来, 它说 ${\mathbb{F}}_q^s$ 中 $r$ 维代数簇 ³的点数大致为 $q^r$, 只要满足某些不可约性假设即可.

定理 8.4 (Lang-Weil bound 1954). 如果 $V=\{y\in {\overline{\mathbb{F}}}_q^s\mid g_1(y)=g_2(y)=$ $\dots =g_m(y)\}$ 是不可约且 $g_i$ 的阶数至多为 $d$, 则$$\left|V\cap {\mathbb{F}}_q^s\right|=q^{\dim V}\left(1+O_{s,m,d}\left(q^{-\frac{1}{2}}\right)\right)$$

现在我们可以使用 Markov 不等式的界和引理 8.3. 令引理 $2.41$ 中的 $s$ 个多项式 $f_1(Y),\dots ,f_s(Y)$ 为 $s$ 个覆盖 $U$ 中 $s$ 个元素的关于 $u$ 的多项式 $f(u,Y)$ . 对于足够大的 $q$, 存在一个来自引理 8.3 的常数 $C$, 使得 $X>C$ , 这告诉我们 $X\ge q-C\sqrt{q}>q/2$, 所以$$\mathbb{P}(X>C)=\mathbb{P}\left(X>\frac{q}{2}\right)\le \frac{M}{(q/2{)}^d}$$因此, $L$ 或 $R$ 的大小为 $s$ 且大于 $C$ 个共同邻点的子集的数量至多为$$2\left(\genfrac{}{}{0ex}{}{n}{s}\right)\frac{M}{(q/2{)}^d}=O\left(q^{s-2}\right)$$我们从 $G$ 中每个这样的子集中删除一个顶点来得到 $G^{\prime }$. 首先我们知道 $G^{\prime }$ 是 $K_{s,C+1}$-free 的, 然后$$\mathbb{E}\left[e\left(G^{\prime }\right)\right]\ge \frac{n^2}{q}-O\left(n{q}^{s-2}\right)=(1-o(1))\frac{n^2}{q}=(1-o(1))n^{2-\frac{1}{s}}$$且 $v\left(G^{\prime }\right)\le 2n$. 所以确实存在一个的实例 $G^{\prime }$, 它达到了所需的上界.

1.	^ 包含 $m$ 元素的集合到包含 $n$ 元素的集合 ($m>n$) 的投影数是 ${\sum }_{i=0}^n(-1{)}^i(\genfrac{}{}{0ex}{}{n}{i})(n-i{)}^m$
2.	^ Terry Tao 的博客中有一篇详细介绍了 Lang-Weil Bound: https://terrytao.wordpress.com/2012/08/31/the-lang-weil-bound/
3.	^ 代数簇, 亦作代数多样体, 是代数几何学上多项式集合的公共零点解的集合.