Additive Combinatorics — Sequence Problems

Loading…

Additive Combinatorics — Sequence Problems

最近在看 Yufei Zhao 的 Graph Theory and Additive Combinatorics，感觉最开始介绍的这个单色数列的挺有意思，感觉值得去研究探讨。书上给的相关定理都没有证明，个人感兴趣去查找了一下，然后记录一下自己的学习笔记和一些思考，我觉得这是一个能写出论文且值得尝试的方向。

一些定义

首先是 上密度 的定义。在 Yufei Zhao 的讲义以及加性组合的标准表述中，我们常常关心整数集（或更高维点阵）的子集在“大区间”里所占的比例，为此我们引入上密度；当这个比例的下极限为正时，就称该集合具有 正的上密度。

Definition 1 (上密度).

设

A \subseteq \mathbb{Z}。定义 A 的 \emph{上密度}（upper density）为

\overline{d}(A)

CodeBlock Loading...

若 \overline{d}(A) > 0，则称 A 具有 \emph{正的上密度}（positive upper density）。 更一般地，设 A \subseteq \mathbb{Z}^d。定义

\overline{d}(A)

CodeBlock Loading...

同样地，若 \overline{d}(A) > 0，则称 A 具有正的上密度。 **Definition 2 (星座).** 设 A \subseteq \mathbb{Z}^d。称 A 包含\emph{星座}（constellation）F，其中 F \subseteq \mathbb{Z}^d 为有限集，若存在 a \in \mathbb{Z}^d 与 t \in \mathbb{Z}_{>0}，使得

a + t \cdot F = {a + tx : x \in F} \subseteq A.

若对每个有限集 F \subseteq \mathbb{Z}^d，A 都包含星座 F，则称 A 包含\emph{任意星座}。 **Definition 3 (向日葵).** 设 [N]=\{1,2,\ldots,N\} 已用 r 种颜色着色。一朵\emph{有 m 片花瓣、每片大小为 k-1 的向日葵}是形如

{a}\cup A1\cup\cdots\cup Am

的整数集，其中 Ai={a+di,a+2di,\ldots,a+(k-1)di}（i=1,\ldots,m），且满足：

Ai\cap Aj=\varnothing（i\neq j，花瓣两两不交）；
A_i 中所有元素同色（花瓣单色）；
i\neq j 时，Ai 与 Aj 所用颜色不同（不同花瓣颜色互异）。
此时 A1,\ldots,Am 称为\emphh{花瓣}，a 称为\emphh{中心}。向日葵对每片花瓣的颜色与结构控制很强，但\emphh{不控制}中心 a 的颜色。特别地，若中心颜色等于某片花瓣的颜色，则该向日葵给出一条单色 k-AP。

一些定理

我就按顺序先列一下书中涉及的主要定理（以下均用\emphh{主定理}环境）：

Theorem (van der Waerden).

若用有限多种颜色给整数 $\mathbb{Z}$ 着色，则必有一个颜色类包含任意长的等差数列。

Theorem (Roth).

\mathbb{Z}

的每个具有正上密度的子集都包含一个长度为 $3$ 的等差数列。

Theorem (Szemerédi).

\mathbb{Z}

的每个具有正上密度的子集都包含任意长的等差数列。

Theorem (多维 Szemerédi).

\mathbb{Z}^d

的每个具有正上密度的子集都包含任意星座（见 (def:constellation)）。

Theorem (平方差特例).

具有正上密度的整数集的任一子集，都包含两个差为完全平方数的整数。等价地，对某个 $x \in \mathbb{Z}$ 与 $y \in \mathbb{Z}_{>0}$ ，该集合总包含

\{x,\, x + y^2\}.

Theorem (多项式 Szemerédi).

设 $A \subseteq \mathbb{Z}$ 具有正的上密度。若 $P_1, \ldots, P_k \in \mathbb{Z}[X]$ 满足 $P_1(0) = \cdots = P_k(0) = 0$ ，则存在 $x \in \mathbb{Z}$ 与 $y \in \mathbb{Z}_{>0}$ ，使得

x + P_1(y),\, \ldots,\, x + P_k(y) \in A.

Theorem (Green--Tao).

素数集包含任意长度的等差数列。

van der Waerden 的证明

以下证明严格参照 UPC 离散数学讲义 Proof of Van der Waerden's Theorem（Barcelona, Juan José Rue）复述。证明过程中用到的辅助结果用\emphh{定理}、\emphh{定义}、\emphh{命题}、\emphh{引理}区分。

Theorem 1 (van der Waerden，有限版本).

CodeBlock Loading...

Proposition 1.

CodeBlock Loading...

$A+d,\ldots,A+(k-1)d$
的着色完全相同；
$A+d$
是一朵有 $m$ 片花瓣、每片大小为 $k-1$ 的向日葵（从而其所有平移 $A+2d,\ldots,A+(k-1)d$ 亦然）。
则 $A\cup(A+d)\cup\cdots\cup(A+(k-1)d)$ 中包含一条单色 $k$ -AP，或一朵有 $m+1$ 片花瓣、每片大小为 $k-1$ 的向日葵。

Proof.

取 $A+d$ ，它已知为一朵有 $m$ 片花瓣、每片大小为 $k-1$ 的向日葵。若其中心颜色与某片花瓣相同，则已得到一条单色 $k$ -AP。

CodeBlock Loading...

A+d=\{a+d\}\cup A_1\cup\cdots\cup A_m,

其中 $A_i=\{a+d+d_i,a+d+2d_i,\ldots,a+d+(k-1)d_i\}$ 。构造

B=\{a\}\cup B_1\cup\cdots\cup B_m\cup B_{m+1},

其中对 $i=1,\ldots,m$ ，

B_i=\{a+(d+d_i),a+2(d+d_i),\ldots,a+(k-1)(d+d_i)\},

而

B_{m+1}=\{a+d,a+2d,\ldots,a+(k-1)d\}

（即 $B_{m+1}$ 由 $A+d,\ldots,A+(k-1)d$ 的中心组成）。显然 $B\subseteq A\cup(A+d)\cup\cdots\cup(A+(k-1)d)$ 。

CodeBlock Loading...

对 $r=1,\ldots,k-1$ 与 $i=1,\ldots,m$ ，元素 $a+r(d+d_i)$ 与 $a+d+rd_i$ 同色（平移 $d$ 不改变颜色），而 $a+d+rd_i$ 与 $a+d+d_i$ 同色（同一花瓣内同色），故 $B_i$ 单色。
若 $i\neq j$ ，则 $B_i$ 所用颜色即为 $a+d_i$ 的颜色，与 $a+d_j$ 的颜色不同，故 $B_i$ 与 $B_j$ 颜色不同。
$B_{m+1}$
也单色，因为 $A+d,\ldots,A+(k-1)d$ 着色相同；且 $B_{m+1}$ 的颜色与 $B_1,\ldots,B_m$ 都不同，因为 $a+d$ （ $A+d$ 的中心）的颜色与每个 $a+d+d_i$ 的颜色不同。
因此 $B$ 即为所求向日葵。

∎

Lemma 1.

CodeBlock Loading...

Proof.

对 $m$ 归纳。 $m=1$ 时，一片大小为 $k-1$ 的花瓣给出一条单色 $(k-1)$ -AP（若中心与花瓣同色则更是 $k$ -AP）。由假设 $W(r,k-1)<\infty$ ，可取 $W(r,1,k-1)\le W(r,k-1)$ 。

CodeBlock Loading...

N_1=W(r,m-1,k-1), N_2=2W(rN_1,k-1).

只需证 $W(r,m,k-1)\le N_1N_2$ 。

CodeBlock Loading...

B+d,\ldots,B+(k-1)d,

使得这些块的着色完全相同。

CodeBlock Loading...

A\cup(A+d)\cup\cdots\cup(A+(k-1)d)

必含一条单色 $k$ -AP，或一朵有 $m$ 片花瓣、每片大小为 $k-1$ 的向日葵。归纳步完成。

∎

(thm:vdw-finite) 的证明.

对 $k$ 归纳。 $W(r,1)=1$ ， $W(r,2)=r+1$ （鸽巢原理）已显然。

CodeBlock Loading...

W(r,k):=W(r,r,k-1).

设 $N\ge W(r,k)$ ， $\chi:[N]\to[r]$ 为任意着色。由 (lem:vdw-sunflower)（取 $m=r$ ）， $\chi$ 要么含单色 $k$ -AP，要么含一朵有 $r$ 片花瓣、每片大小为 $k-1$ 的向日葵。后一种情形中，中心颜色必与某片花瓣颜色相同（共有 $r$ 种颜色、 $r$ 片花瓣颜色互异），于是也得到单色 $k$ -AP。

∎

(thm:vdw) 的证明.

由 (thm:vdw-finite)，对每个 $k,r$ 都存在 $W(r,k)$ 。若 $\chi:\mathbb{Z}\to[r]$ 在 $\mathbb{Z}$ 上不含长度为 $k$ 的单色等差数列，则限制到 $[W(r,k)]$ 也不含，与 (thm:vdw-finite) 矛盾。因此对每个 $k$ 都存在长度为 $k$ 的单色等差数列；由于 $k$ 任意，必有一个颜色类包含任意长的等差数列。

∎

PDF

Download the original write-up here.

一些定义

Definition 1 (上密度).

设

A \subseteq \mathbb{Z}。定义 A 的 \emph{上密度}（upper density）为

\overline{d}(A)

:= \limsup_{N \to \infty} \frac{\bigl|A \cap {-N, -N+1, \ldots, N}\bigr|}{2N+1}
= \limsup_{N \to \infty} \frac{\bigl|A \cap [-N, N]\bigr|}{2N+1}.

CodeBlock Loading...

若 \overline{d}(A) > 0，则称 A 具有 \emph{正的上密度}（positive upper density）。 更一般地，设 A \subseteq \mathbb{Z}^d。定义

\overline{d}(A)

:= \limsup_{N \to \infty} \frac{\bigl|A \cap [-N, N]^d\bigr|}{(2N+1)^d}.

CodeBlock Loading...

同样地，若 \overline{d}(A) > 0，则称 A 具有正的上密度。 **Definition 2 (星座).** 设 A \subseteq \mathbb{Z}^d。称 A 包含\emph{星座}（constellation）F，其中 F \subseteq \mathbb{Z}^d 为有限集，若存在 a \in \mathbb{Z}^d 与 t \in \mathbb{Z}_{>0}，使得

a + t \cdot F = {a + tx : x \in F} \subseteq A.

若对每个有限集 F \subseteq \mathbb{Z}^d，A 都包含星座 F，则称 A 包含\emph{任意星座}。 **Definition 3 (向日葵).** 设 [N]=\{1,2,\ldots,N\} 已用 r 种颜色着色。一朵\emph{有 m 片花瓣、每片大小为 k-1 的向日葵}是形如

{a}\cup A1\cup\cdots\cup Am

的整数集，其中 Ai={a+di,a+2di,\ldots,a+(k-1)di}（i=1,\ldots,m），且满足：

Ai\cap Aj=\varnothing（i\neq j，花瓣两两不交）；
A_i 中所有元素同色（花瓣单色）；
i\neq j 时，Ai 与 Aj 所用颜色不同（不同花瓣颜色互异）。
此时 A1,\ldots,Am 称为\emphh{花瓣}，a 称为\emphh{中心}。向日葵对每片花瓣的颜色与结构控制很强，但\emphh{不控制}中心 a 的颜色。特别地，若中心颜色等于某片花瓣的颜色，则该向日葵给出一条单色 k-AP。

一些定理

我就按顺序先列一下书中涉及的主要定理（以下均用\emphh{主定理}环境）：

Theorem (van der Waerden).

若用有限多种颜色给整数 $\mathbb{Z}$ 着色，则必有一个颜色类包含任意长的等差数列。

Theorem (Roth).

\mathbb{Z}

的每个具有正上密度的子集都包含一个长度为 $3$ 的等差数列。

Theorem (Szemerédi).

\mathbb{Z}

的每个具有正上密度的子集都包含任意长的等差数列。

Theorem (多维 Szemerédi).

\mathbb{Z}^d

的每个具有正上密度的子集都包含任意星座（见 (def:constellation)）。

Theorem (平方差特例).

具有正上密度的整数集的任一子集，都包含两个差为完全平方数的整数。等价地，对某个 $x \in \mathbb{Z}$ 与 $y \in \mathbb{Z}_{>0}$ ，该集合总包含

\{x,\, x + y^2\}.

Theorem (多项式 Szemerédi).

x + P_1(y),\, \ldots,\, x + P_k(y) \in A.

Theorem (Green--Tao).

素数集包含任意长度的等差数列。

van der Waerden 的证明

Theorem 1 (van der Waerden，有限版本).

设 <span data-mx-katex="r%2Ck"></span> 为正整数，则存在 <span data-mx-katex="W(r%2Ck)"></span>，使得若 <span data-mx-katex="N%5Cge%20W(r%2Ck)"></span>，则 <span data-mx-katex="%5BN%5D%3D%5C%7B1%2C2%2C%5Cldots%2CN%5C%7D"></span> 的任意 <span data-mx-katex="r"></span>-着色都包含一条单色 <span data-mx-katex="k"></span>-AP。

CodeBlock Loading...

Proposition 1.

设 <span data-mx-katex="%5BN%5D"></span> 为 <span data-mx-katex="r"></span>-着色，<span data-mx-katex="A%2CA%2Bd%2C%5Cldots%2CA%2B(k-1)d%5Csubseteq%5BN%5D"></span>（其中 <span data-mx-katex="X%2Bt%3A%3D%5C%7Bx%2Bt%3Ax%5Cin%20X%5C%7D"></span>），且

CodeBlock Loading...

$A+d,\ldots,A+(k-1)d$
的着色完全相同；
$A+d$
是一朵有 $m$ 片花瓣、每片大小为 $k-1$ 的向日葵（从而其所有平移 $A+2d,\ldots,A+(k-1)d$ 亦然）。
则 $A\cup(A+d)\cup\cdots\cup(A+(k-1)d)$ 中包含一条单色 $k$ -AP，或一朵有 $m+1$ 片花瓣、每片大小为 $k-1$ 的向日葵。

Proof.

取 $A+d$ ，它已知为一朵有 $m$ 片花瓣、每片大小为 $k-1$ 的向日葵。若其中心颜色与某片花瓣相同，则已得到一条单色 $k$ -AP。

现设 <span data-mx-katex="A%2Bd"></span> 的中心颜色与它的每片花瓣颜色都不同。记

CodeBlock Loading...

A+d=\{a+d\}\cup A_1\cup\cdots\cup A_m,

其中 $A_i=\{a+d+d_i,a+d+2d_i,\ldots,a+d+(k-1)d_i\}$ 。构造

B=\{a\}\cup B_1\cup\cdots\cup B_m\cup B_{m+1},

其中对 $i=1,\ldots,m$ ，

B_i=\{a+(d+d_i),a+2(d+d_i),\ldots,a+(k-1)(d+d_i)\},

而

B_{m+1}=\{a+d,a+2d,\ldots,a+(k-1)d\}

（即 $B_{m+1}$ 由 $A+d,\ldots,A+(k-1)d$ 的中心组成）。显然 $B\subseteq A\cup(A+d)\cup\cdots\cup(A+(k-1)d)$ 。

下面验证 <span data-mx-katex="B"></span> 是一朵有 <span data-mx-katex="m%2B1"></span> 片花瓣、每片大小为 <span data-mx-katex="k-1"></span> 的向日葵：

CodeBlock Loading...

对 $r=1,\ldots,k-1$ 与 $i=1,\ldots,m$ ，元素 $a+r(d+d_i)$ 与 $a+d+rd_i$ 同色（平移 $d$ 不改变颜色），而 $a+d+rd_i$ 与 $a+d+d_i$ 同色（同一花瓣内同色），故 $B_i$ 单色。
若 $i\neq j$ ，则 $B_i$ 所用颜色即为 $a+d_i$ 的颜色，与 $a+d_j$ 的颜色不同，故 $B_i$ 与 $B_j$ 颜色不同。
$B_{m+1}$
也单色，因为 $A+d,\ldots,A+(k-1)d$ 着色相同；且 $B_{m+1}$ 的颜色与 $B_1,\ldots,B_m$ 都不同，因为 $a+d$ （ $A+d$ 的中心）的颜色与每个 $a+d+d_i$ 的颜色不同。
因此 $B$ 即为所求向日葵。

∎

Lemma 1.

设 <span data-mx-katex="k"></span> 为正整数。若对每个 <span data-mx-katex="r"></span> 都有 <span data-mx-katex="W(r%2Ck-1)%3C%5Cinfty"></span>，则对每个 <span data-mx-katex="r%2Cm"></span> 都存在 <span data-mx-katex="W(r%2Cm%2Ck-1)%3C%5Cinfty"></span>，使得：若 <span data-mx-katex="N%5Cge%20W(r%2Cm%2Ck-1)"></span>，则 <span data-mx-katex="%5BN%5D"></span> 的任意 <span data-mx-katex="r"></span>-着色要么包含一条单色 <span data-mx-katex="k"></span>-AP，要么包含一朵有 <span data-mx-katex="m"></span> 片花瓣、每片大小为 <span data-mx-katex="k-1"></span> 的向日葵。

CodeBlock Loading...

Proof.

设 <span data-mx-katex="W(r%2Cm-1%2Ck-1)%3C%5Cinfty"></span>，证 <span data-mx-katex="W(r%2Cm%2Ck-1)%3C%5Cinfty"></span>。令

CodeBlock Loading...

N_1=W(r,m-1,k-1), N_2=2W(rN_1,k-1).

只需证 $W(r,m,k-1)\le N_1N_2$ 。

取区间 <span data-mx-katex="%5BN_1N_2%5D"></span> 并做 <span data-mx-katex="r"></span>-着色。把它看成：先拼接 <span data-mx-katex="W(rN_1%2Ck-1)"></span> 个长为 <span data-mx-katex="N_1"></span> 的块（第一部分），再拼接 <span data-mx-katex="W(rN_1%2Ck-1)"></span> 个长为 <span data-mx-katex="N_1"></span> 的块（第二部分）；亦即两部分各有 <span data-mx-katex="N_2%2F2"></span> 个长为 <span data-mx-katex="N_1"></span> 的块（这正是 <span data-mx-katex="N_2"></span> 中因子 <span data-mx-katex="2"></span> 的来源）。

先只看第二部分。若其中某个块已含单色 <span data-mx-katex="k"></span>-AP，则证明完成；故可设否则。

第二部分共有 <span data-mx-katex="N_2%2F2%3DW(rN_1%2Ck-1)"></span> 个块，每个块有 <span data-mx-katex="r%5E%7BN_1%7D"></span> 种着色方式。由 <span data-mx-katex="W(rN_1%2Ck-1)"></span> 的定义（将其应用于这些块，而非块内元素），存在下标构成一条 <span data-mx-katex="(k-1)"></span>-AP 的块

CodeBlock Loading...

B+d,\ldots,B+(k-1)d,

使得这些块的着色完全相同。

此时 <span data-mx-katex="%7CB%2Bd%7C%3DN_1%3DW(r%2Cm-1%2Ck-1)"></span>。由归纳假设，<span data-mx-katex="B%2Bd"></span> 中不含单色 <span data-mx-katex="k"></span>-AP，故含一朵有 <span data-mx-katex="m-1"></span> 片花瓣、每片大小为 <span data-mx-katex="k-1"></span> 的向日葵；记 <span data-mx-katex="A%2Bd%5Csubseteq%20B%2Bd"></span> 为其在 <span data-mx-katex="B%2Bd"></span> 中的一份拷贝。

最后令 <span data-mx-katex="B%3D(B%2Bd)-d"></span>，<span data-mx-katex="A%3D(A%2Bd)-d"></span>，则 <span data-mx-katex="A%5Csubseteq%20B"></span>，且 <span data-mx-katex="B"></span> 可能落在第一部分（这同样是 <span data-mx-katex="N_2"></span> 取因子 <span data-mx-katex="2"></span> 的原因）。虽然无法控制 <span data-mx-katex="B"></span> 的着色，但由 (prop:vdw-sunflower-upgrade)，集合

CodeBlock Loading...

A\cup(A+d)\cup\cdots\cup(A+(k-1)d)

必含一条单色 $k$ -AP，或一朵有 $m$ 片花瓣、每片大小为 $k-1$ 的向日葵。归纳步完成。

∎

(thm:vdw-finite) 的证明.

对 $k$ 归纳。 $W(r,1)=1$ ， $W(r,2)=r+1$ （鸽巢原理）已显然。

设 <span data-mx-katex="W(r%2Ck-1)%3C%5Cinfty"></span> 对每个 <span data-mx-katex="r"></span> 成立。由 (lem:vdw-sunflower)，对每个 <span data-mx-katex="r%2Cm"></span> 都有 <span data-mx-katex="W(r%2Cm%2Ck-1)%3C%5Cinfty"></span>；特别地 <span data-mx-katex="W(r%2Cr%2Ck-1)%3C%5Cinfty"></span>。取

CodeBlock Loading...

W(r,k):=W(r,r,k-1).

∎

(thm:vdw) 的证明.

∎

PDF

Download the original write-up here.

Additive Combinatorics — Sequence Problems

Search

Additive Combinatorics — Sequence Problems

一些定义

一些定理

van der Waerden 的证明

PDF

一些定义

一些定理

van der Waerden 的证明

PDF