7. 下界: 代数构造

在本节中, 我们使用代数构造来寻找 $K_{s,t}$-free 图, 对于 $(s,t)$ 的各种取值, 这些构造都达到了 KöváriSós-Turán 定理 (定理 5.2) 中的上界 (仅相差常数因子) . 这种代数构造的最简单例子是下面关于 $K_{2,2}$-free 图的构造.

定理 7.1 (Erdős-Rényi-Sós 1966). $$\mathrm{ex}\left(n,K_{2,2}\right)\ge \left(\frac{1}{2}-o(1)\right)n^{3/2}$$

证明. 假设 $n=p^2-1$ 其中 $p$ 是素数. 考虑下面的图 $G$ (称为 polarity 图) :

•	$V(G)={\mathbb{F}}_p^2\backslash \{(0,0)\}$
•	$E(G)=\{(x,y)\sim (a,b)\mid ax+by=1$ in ${\mathbb{F}}_p\}$

对于任意两个不同的顶点 $(a,b)\ne \left(a^{\prime },b^{\prime }\right)\in V(G)$, 最多有一个解 (公共邻点) $(x,y)\in V(G)$ 满足 $ax+by=1$ 和 $a^{\prime }x+b^{\prime }y=1$. 因此, $G$ 是 $K_{2,2}$-free 的.

此外, 每个顶点都有度数 $p$ 或 $p-1$, 所以边的总数$$e(G)=\left(\frac{1}{2}-o(1)\right)p^3=\left(\frac{1}{2}-o(1)\right)n^{3/2}$$这就完成了证明. 如果对于某个素数 $n$ 不具有 $p^2-1$ 形式, 那么我们让 $p$ 是满足 $p^2-1\le n$ 条件下最大的素数. 我们有 $p=\left(1-o(1)\right)n^{1/2}$ , 构造相同的图 $G_{p^2-1}$ 并添加 $n-p^2+1$ 个孤立顶点.

$\square$

笔记 7.2. 为什么叫作 polarity 图? 您可以从下面二分图的角度考虑: 其中一个顶点集是 ${\mathbb{F}}_p$ 平面上 (投影得到) 的点集, 另一个顶点集是同一平面中的线集. 如果 $p\in \ell$, 点 $p$ 和线 $\ell$ 之间有一条边. 因为不存在两条线在两个不同的点相交的情况, 所以该图是 $C_4$-free 的.

定理 7.1 证明中的构造有一个用线当作点的顶点集. 点和线之间的这种对偶配对在射影几何中被称作极性.

因为方程 $ax+by=1$ 正好有 $p$ 个解 $(x,y)$, 所以大多数顶点的度数为 $p$. 有时我们必须减去 $1$, 因为其中一个解可能是 $(a,b)$ 本身, 这导致了一个自环.

事实上, 对于每个足够大的 $n$, 在区间 $[n-n^{0.525},n]$ 中都存在一个素数 ¹.

一个自然的问题是, 上述构造是否可以推广. 下一个例子为我们提供了 $K_{3,3}$-free 图的构造.

定理 7.3 (Brown 1966). $$\mathrm{ex}\left(n,K_{3,3}\right)\ge \left(\frac{1}{2}-o(1)\right)n^{5/3}$$

笔记 7.4. 定理 7.3 中的常数 1/2 是已知的最佳常数.

概要. 令 $n=p^3$, 其中 $p$ 是素数. 考虑如下图 $G$:

•	$V(G)={\mathbb{F}}_p^3$
•	$E(G)=\left\{(x,y,z)\sim (a,b,c)\mid (ax{)}^2+(by{)}^2+(cz{)}^2=u\text{in}{\mathbb{F}}_p\right\}$, 其中 $u$ 是 ${\mathbb{F}}_p$ 中精心挑选的固定非零元素.

我们需要检查是否可以选出使得上图为 $K_{3,3}$-free 的 $u$ . 我们省略证明, 但会给一些直观上的说明. 如果我们使用 ${\mathbb{R}}^3$ 上的点而不是 ${\mathbb{F}}_p^3$, $K_{3,3}$-free 等价于三个单位球至多有两个公共点. 事实上, 这个关于 ${\mathbb{R}}^3$ 中单位球的陈述可以通过一些代数运算来严格证明. 我们可以对 ${\mathbb{F}}_p$ 进行类似的代数运算, 验证上面的图中没有 $K_{3,3}$.

另外, 每个顶点的度数大约为 $p^2$, 因为 $(x,y,z)\in {\mathbb{F}}_p^3\mapsto (ax{)}^2+(by{)}^2+(cz{)}^2$ 在 $F_p$ 的取值上几乎是均匀随机的. 因此我们预计大约有 $1/p$ 占比的 $(x,y,z)$ 满足 $(ax{)}^2+(by{)}^2+(cz{)}^2=u$ , 我们再次省略相应细节.

$\square$

尽管 $K_{2,2}$ 和 $K_{3,3}$ 的情况已经完全解决, 但 $K_{4,4}$ 的对应问题是极值图论中的核心开放问题.

问题 7.5. $\mathrm{ex}\left(n,K_{4,4}\right)$ 的增长情况是怎么样的? 是否与定理 5.2 中的上界相同 ($\Theta \left(n^{7/4}\right)$) ?

我们已经得到了 Kóvári-Sós-Turán 定理具体到 $K_{2,2}$ 和 $K_{3,3}$ 的常数因子. 现在我们提出一个与 Kóvári-Sós-Turán 匹配的构造, 但 $K_{s,t}$ 中的 $t$ 要远大于 $s$ .

定理 7.6 (Alon, Kollár, Rónyai, Szabó 1996 1999). 如果 $t\ge (s-1)!+1$ , 则$$ex\left(n,K_{s,t}\right)=\Theta \left(n^{2-\frac{1}{s}}\right)$$

我们首先证明较弱版本: $t\ge s!+1$ . 两者证明的思路是相似的, 稍后我们将对证明细节进行调整从而得到我们之前想要的. 取质数 $p$ 和 $n=p^s$ , 其中 $s\ge 2$. 考虑范数映射 $N:{\mathbb{F}}_{p^s}\to {\mathbb{F}}_p$ $$N(x)=x\cdot x^p\cdot x^{p^2}\cdots x^{p^{s-1}}=x^{\frac{p^s-1}{p-1}}$$定义图 ${\mathrm{NormG}}_{p,s}=(V,E)$$$V={\mathbb{F}}_{p^s},E=\{\{a,b\}\mid a\ne b,N(a+b)=1\}$$

命题 7.7. ${\mathrm{NormG}}_{p,s}$ 的定义同上, 顶点数为 $n=p^s$ , $$|E|\ge \frac{1}{2}{n}^{2-\frac{1}{s}}$$

证明. 由于 ${\mathbb{F}}_{p^s}^{\times }$ 是 $p^s-1$ 阶的循环群, 我们有$$\left|\left\{x\in {\mathbb{F}}_{p^s}\mid N(x)=1\right\}\right|=\frac{p^s-1}{p-1}$$

因此, 对于每个顶点 $x$ (减去一个顶点的自环 $N(x+x)=1)$ $$\mathrm{deg}(x)\ge \frac{p^s-1}{p-1}-1\ge p^{s-1}=n^{1-\frac{1}{s}}$$我们得到了所需的边数的下界.

$\square$

命题 7.8. ${\mathrm{NormG}}_{p,s}$ 是 $K_{s,s!+1}$-free 图.

我们希望给出 $s$ 个顶点的共同邻点数的上界. 我们不加证明地引用下面的结论, 该结论可以通过代数几何来证明.

定理 7.9 (Kollár, Rónyai, and Szabó 1996). 令 $\mathbb{F}$ 是任意域, $a_{ij},b_i\in \mathbb{F}$ 且对于所有 $i\ne i^{\prime }$ 满足 $a_{ij}\ne a_{i^{\prime }j}$ . 则方程组$$\begin{array}{l}\left(x_1-a_{11}\right)\left(x_2-a_{12}\right)\cdots \left(x_s-a_{1s}\right)=b_1\\ \left(x_1-a_{21}\right)\left(x_2-a_{22}\right)\cdots \left(x_s-a_{2s}\right)=b_2\\ ⋮\\ \left(x_1-a_{s1}\right)\left(x_2-a_{s2}\right)\cdots \left(x_s-a_{ss}\right)=b_s\end{array}$$在 ${\mathbb{F}}^s$ 中至多有 $s!$ 个解.

笔记 7.10. 考虑所有 $b_i$ 都是 $0$ 的特殊情况. 在这种情况下, 由于 $a_{ij}$ 对于固定的 $j$ 是不同的, 我们选择满足 $x_j=a_{i_{j}j}$ 的 $i_j$. 因为所有的 $i_j$ 都是不同的, 这相当于在 $[s]$ 上选择一个排列. 因此, 正好有 $s!$ 解决方案.

我们现在可以证明命题 7.8.

命题 7.8. 考虑互不相同的 $y_1,y_2,\dots ,y_s\in {\mathbb{F}}_{p^s}$. 我们希望限制他们共同邻点 $x$ 的数量. 我们可以利用这样一个事实: 在具有特征 $p$ 的域中, 我们有 $(x+y{)}^p=x^p+y^p$ , 从而对于所有 $1\le i\le s$ $$\begin{array}{rl}1=N\left(x+y_i\right)& =\left(x+y_i\right){\left(x+y_i\right)}^p\dots {\left(x+y_i\right)}^{p^{s-1}}\\ & =\left(x+y_i\right)\left(x^p+y_i^p\right)\dots \left(x^{p^{s-1}}+y_i^{p^{s-1}}\right)\end{array}$$根据定理 7.9, 这 $s$ 个方程在 $x$ 中最多有 $s!$ 个解. 之所以满足定理 7.9 的形式是因为在我们的域中 $y_i^p=y_j^p$ 当且仅当 $y_i=y_j$ .

$\square$

现在我们进行调整来实现定理 7.6 中的 $t\ge (s-1)!+1$ . 我们定义图 ${\mathrm{NormG}}_{p,s}=(V,E)$ , 其中 $V={\mathbb{F}}_{p^{s-1}}\times {\mathbb{F}}_p$ ($s\ge 3$) . 易知 $n=(p-1)p^{s-1}$. 定义两点之间边存在 $(X,x)\sim (Y,y)$ 当且仅当$$N(X+Y)=xy$$

命题 7.11. ${\mathrm{NormG}}_{p,s}$ 的定义同上, 顶点数为 $n$, 显然 $n=(p-1)p^{s-1}$ , 则$$|E|=\left(\frac{1}{2}-o(1)\right)n^{2-\frac{1}{s}}$$

证明. 每个顶点 $(X,x)$ 的邻点 $(Y,N(X+Y)/x)$ 覆盖了 ${\mathbb{F}}_{p^{s-1}}$. 减去自环后, 每个顶点的度数都为 $p^{s-1}-1=(1-o(1))n^{1-1/s}$ .

$\square$

现在我们确定了边的数量, 我们只需要证明我们的图是 $K_{s,(s-1)!+1}$-free 的.

命题 7.12. ${\mathrm{NormG}}_{p,s}$ 是 $K_{s,(s-1)!+1}$-free 图.

证明. 固定不同的 $\left(Y_i,y_i\right)\in V$ , $1\le i\le s$. 我们希望找到所有的共同邻点 $(X,x)$. 考虑$$N\left(X+Y_i\right)=x{y}_i$$假设这个系统至少有一个解. 如果 $Y_i=Y_j$ 且 $i\ne$ $j$ , 则必须有 $y_i=y_j$. 因此, 所有 $Y_i$ 都是不同的. 对于每个 $i<s$ 我们可以取 $N\left(X+Y_i\right)=x{y}_i$ 并除以 $N\left(X+Y_s\right)=x{y}_s$ 从而得到$$N\left(\frac{X+Y_i}{X+Y_s}\right)=\frac{y_i}{y_s}$$两边再除以 $N\left(Y_i-Y_s\right)$ ($1\le i\le s-1$) 得到$$N\left(\frac{1}{X+Y_s}+\frac{1}{Y_i-Y_s}\right)=\frac{y_i}{N\left(Y_i-Y_s\right)y_s}$$现在应用定理 7.9, $X$ 最多有 $(s-1)!$ 个解, 这也意味着 $x=N\left(X+Y_1\right)/y_1$. 因此, 至多有 $(s-1)!$ 个共同的邻点.

$\square$

最后, 我们来证明定理 7.6.

定理 7.6. 根据命题 7.11 和命题 7.12, 我们知道 ${\mathrm{NormG}}_{p,s}$ 是 $K_{s,(s-1)!+1}$-free 并且有 $\left(\frac{1}{2}-o(1)\right)n^{2-\frac{1}{s}}$ 条边.

$\square$

1.	^ 译者注: 您可以参考该著名结果的原文 Baker,Harman and Pintz: The difference between consecutive primes Terry Tao 博客有一篇讲述了相邻素数差的下界的研究进展: https://terrytao.wordpress.com/2014/08/21/large-gaps-between-consecutive-prime-numbers/