4. 构造没有长度为 3 的等差数列的集合

构造没有三项等差数列 (长度为 3 的等差数列) 的子集 $A\subseteq [N]$ 的一种方法是贪婪构造具有这种性质的自然数的子序列. 产生的序列如下, 我们称之为 Stanley 序列: $$\begin{array}{llllllllllll}0& 1& 3& 4& 9& 10& 12& 13& 27& 28& 30& 31\end{array}$$

笔记 4.1. 给定任何三个不同的数字 $a.b,c$ , 他们的三进制表示中不包含数字 2, 所以我们将任意两个这样的三进制数相加, 不会出现进位的情况. 然后, $2b=b+b$ 的三进制表示中每个数字都是 $0$ 或 $2$, 而 $a+c$ 的三进制表示中数字 $1$ 将出现在 $a$ 和 $c$ 不同的位上 ¹. 因此 $a+c\ne 2b$, 即任意三个这样的数都不构成等差数列.

这个序列全由三进制表示只有数字 0 和 1 的自然数组成. $N=3^k$, 如此构造的子集 $A\subseteq [N]$ 大小为 $|A|=2^k=N^{{\log }_{3}2}$. 很长一段时间, 人们都认为这个例子接近最优. 但在 1940 年代, Salem 和 Spencer 发现了更好的构造 (1942) . 他们的证明后来被 Behrend 简化和改进 (1946) , 我们将在下面介绍他的版本. 令人惊讶的是, 自从上世纪 40 年代以来, 这个下界几乎没有被改进.

定理 4.2.

存在一个常数 $C>0$ 使得对于每个正整数 $N$, 存在一个子集 $A\subseteq [N]$, 该子集的大小 $|A|⩾N{e}^{-C\sqrt{\log N}}$ , 并且该子集不包含长度为 3 的等差数列.

证明.

令 $m$ 和 $d$ 为两个正整数, 他们的取值我们稍后指明. 考虑在 $d$ 维中的格点盒 $X:=[m{]}^d$ , 以及它与半径为 $\sqrt{L}(L\in \mathbb{N})$ 的球体的交点$$X_L:=\left\{\left(x_1,\dots ,x_d\right)\in X:x_1^2+\cdots +x_d^2=L\right\}$$设 $M:=d{m}^2$, 我们有 $X=X_1\bigsqcup \cdots \bigsqcup X_M$. 根据鸽巢原理, 存在 $L_0\in [M]$ 使得 $\left|X_{L_0}\right|⩾m^d/M$. 考虑映射 $\phi :X\to \mathbb{N}$ , 其定义为$$\phi \left(x_1,\dots ,x_d\right):=\sum _{i=1}^d{x}_i(2m{)}^{i-1}$$显然, $\phi$ 是单射的. 此外, 又因为 $\left(x_1,\dots ,x_d\right)$ 中的每个元素都在 $[m]$ 中, 容易发现任何三个不同的 $\vec{x},\vec{y},\vec{z}\in X$ 映射到 $\mathbb{N}$ 中形成等差数列当且仅当 $\vec{x},\vec{y},\vec{z}$ 在 $X$ 中构成等差数列. 作为球的子集, 集合 $X_{L_0}$ 没有长度为 3 的等差数列. 所以 $X_{L_0}$ 的像 $\phi \left(X_{L_0}\right)$ 也没有长度位 3 的等差数列. 因此, 取 $m=\frac{1}{2}[e^{\sqrt{\log N}}\rfloor$ 和 $d=\lfloor \sqrt{\log N}\rfloor$ 我们可以找到 $[N]$ 的一个子集, 即 $A=\phi \left(X_{L_0}\right)$, 不包含长度为 3 的等差数列, 其大小$$|A|=\left|X_{L_0}\right|⩾\frac{m^d}{d{m}^2}⩾N{e}^{-C\sqrt{\log N}}$$其中 $C$ 是某大于 0 的常数.

$\square$

接下来, 让我们研究 Roth 定理的一些变体. 我们将从 Roth 定理的更高维版本开始, 它是第 1 章中提到的多维 Szemerédi 定理的一个特例.

定义 4.3. ${\mathbb{Z}}^2$ 中的角 (corner) 是形如 $\{(x,y),(x+d,y),(x,y+d)\}$ 的三元集, 其中 $d>0$.

定理 4.4. 如果子集 $A\subseteq [N{]}^2$ 中没有角, 则 $|A|=o\left(N^2\right)$.

证明.

考虑和集 ²$A+A\subseteq [2N{]}^2$. 根据鸽巢原理, 存在点 $z\in [2N{]}^2$ 使得至少有 $\frac{\mid A{\mid }^2}{(2N{)}^2}$ 对 $(a,b)\in A\times A$ 满足 $a+b=z$. 令 $A^{\prime }=A\cap (z-A)$ 那么, $A^{\prime }$ 的大小正好是 $z$ 写成 $A$ 的两个元素之和的方案数. 所以, $\left|A^{\prime }\right|⩾\frac{|A{|}^2}{(2N{)}^2}$, 接下来我们只需证明 $\left|A^{\prime }\right|=o\left(N^2\right)$ 即可. 另外, 注意到 $A^{\prime }=z-A^{\prime }$, 所以集合 $A^{\prime }$ 没有 $d\ne 0$ 的角.

现在, 构建一个三部分别为 $X=\left\{x_1,\dots ,x_N\right\},Y=\left\{y_1,\dots ,y_N\right\}$ 和 $Z=\left\{z_1,\dots ,z_{2N}\right\}$ 的三部图. 其中, 每个顶点 $x_i$ 对应一条垂直线 $\{x=i\}\subseteq {\mathbb{Z}}^2$, 每个顶点 $y_j$ 对应一个条水平线 $\{y=j\}$, 每个顶点 $z_k$ 对应一条斜率为 $-1$ 的斜线 $\{y=-x+k\}$. 当且仅当相应的线的交点属于 $A^{\prime }$, $G$ 的两个不同顶点用边相连. 然后, 图 $G$ 中的每个三角形对应于一组三条线, 且每对线的交点在 $A^{\prime }$ 中. 由于 $A^{\prime }$ 没有 $d\ne 0$ 的角, 当且仅当三条对应的线经过 $A^{\prime }$ 中同一个点并且形成一个 $d=0$ 的角, 三个顶点 $x_i,y_j,z_k$ 在 $G$ 中诱导出一个三角形. 由于恰好有一条垂直线、一条水平线和一条斜率为 $-1$ 的线穿过 $A^{\prime }$ 中的每个点, 因此 $G$ 的每条边都恰好属于一个三角形. 因此, 根据推论 2.0.7, $$3\left|A^{\prime }\right|=e(G)=o\left(N^2\right)$$(...) 三条线相交示意图

请注意, 我们可以通过以下方式从角定理推导出 Roth 定理.

推论 4.5. 令 $r_3(N)$ 为不包含长度为 3 的等差数列的 $[N]$ 的最大子集的大小, $r_{└}(N)$ 为不包含角的 $[N{]}^2$ 的最大子集的大小. 则, $r_3(N)N⩽r_{└}(2N)$.

证明. 给定任一集合 $A\subseteq [N]$, 定义集合$$B:=\left\{(x,y)\in [2N{]}^2:x-y\in A\right\}$$因为对于每个 $a\in [N]$ 至少有 $n$ 对 $(x,y)\in [2N{]}^2$ 使得 $x-y=a$, 所以我们有 $|B|⩾N|A|$. 此外, 由于 $B$ 中的每个角 $\{(x,y),(x+d,y),(x,y+d)\}$ 将通过 $(x,y)\stackrel{\pi }{\mapsto }x-y$ 被投影成 $A$ 中长度为 3 的等差数列 $\{x-y-d,x-y,x-y+d\}$ . 所以, 如果 $A$ 没有长度为 3 的等差数列, 则 $B$ 没有角. 因此, $r_3(N)N⩽r_{└}(2N)$.

$\square$

因此, 任何 corner-free 集上界都是 $3-AP-\text{free}$ 集的上界, 而任何的 $3-AP-\text{free}$ 下界都是 corner-free 集的下界. 值得一提的是, Behrend 的 $3-AP-\text{free}$ 集的构造很容易扩展到大型 $3-AP-\text{free}$ 集的构造. 我们目前所知的 $[N{]}^2$ 的 corner-free 子集大小的最佳上界是 $N^2(\log \log N{)}^{-C}$, 其中 $C>0$ 是某常数, Shkredov 使用傅立叶分析的方法证明了这一点 (2006) .