11. 多项式 Freiman-Ruzsa 猜想

多项式 Freiman-Ruzsa 猜想

在 ${\mathbb{F}}_2^n$ 中, 如果 $A$ 是一个大小为 $n$ 的独立集, 它的倍增常数为 $K=|A+A|/|A|\approx n/2$, 并且任何包含 $A$ 的子群的大小必须至少为 $2^{\Theta (K)}|A|$.

扩展上一个例子, 令 $A$ 是 ${\mathbb{F}}^{m+n}$ 的子集, $A={\mathbb{F}}_2^m\times \left\{e_1,\dots ,e_n\right\}$ (其中 $\left\{e_1,\dots ,e_n\right\}$ 是 ${\mathbb{F}}_2^n$ 的坐标基) . 此结构与前一个结构具有相同的倍增常数, 但 $|A|$ 可以任意大. 这表明 Freiman 定理的 Abel 群版本中的上界不能比指数更好.

注意, 在此示例中, $A$ 必须包含非常大的 (仿射) 子空间 ${\mathbb{F}}_2^m\times \left\{e_1\right\}$, 其大小与 $A$ 相当. 因此我们可能会问, 如果我们只需要覆盖 $A$ 的一个大子集, 我们是否可以在 Freiman 定理中获得更好的界? 这就引出如下猜想:

命题 11.1. [ ${\mathbb{F}}_2^n$ 上的多项式 Freiman-Ruzsa 猜想, Green , 2004] 如果 $A\subset {\mathbb{F}}_2^n$, 并且 $|A+A|\le K|A|$, 则存在一个仿射子空间 $V\subseteq {\mathbb{F}}_2^n$ 且 $|V|\le |A|$ , 满足 $|V\cap A|\ge K^{-O(1)}|A|$.

这个猜想有几种等价形式. 例如, 以下三个猜想等价于猜想 11.1 :

命题 11.2. 如果 $A\subset {\mathbb{F}}_2^n$, 并且 $|A+A|\le K|A|$, 则存在一个子空间 $V\subseteq {\mathbb{F}}_2^n$ 且 $|V|\le |A|$, 使得 $A$ 可以被 $V$ 的 $K^{O(1)}$ 陪集所覆盖.

等价性证明. 显然猜想 11.2 可以推导出猜想 11.1.

现在假设猜想 11.1 为真, 并且假设 $A\subset {\mathbb{F}}_2^n$ 满足 $|A+A|\le K|A|$. 那么通过猜想 11.1, 存在一个最大为 $|A|$ 的仿射子空间 $V$, 使得 $|V\cap A|\ge K^{-O(1)}|A|$. 应用 Ruzsa 覆盖引理 (定理 3.0.1) , $X=A,B=V\cap A$, 我们得到大小为 $K^{O(1)}$ 的集合 $X$, 满足 $A\subseteq V-V+X$. 对 $X$ 的每个元素, 我们平移向量空间 $V-V$ 得到陪集, 所以猜想 11.2 为真.

$\square$

命题 11.3. 如果 $f:{\mathbb{F}}_2^n\to {\mathbb{F}}_2^n$ 满足$$\left|\left\{f(x,y)-f(x)-f(y):x,y\in {\mathbb{F}}_2^n\right\}\right|\le K$$那么存在一个线性函数 $g:{\mathbb{F}}_2^n\to {\mathbb{F}}_2^n$ 使得$$\left|\left\{f(x)-g(x):x\in {\mathbb{F}}_2^n\right\}\right|\le K^{O(1)}$$

命题 11.4. 如果 $f:{\mathbb{F}}_2^n\to \mathbb{C}$ 且 $\Vert f{\Vert }_{\infty }\le 1$ , $\Vert f{\Vert }_{U_3}\ge \delta$ (其中 $\Vert f{\Vert }_{U_3}$ 是 Gowers $U_3$ 范数, 与 4-AP 计数有关) , 则存在 ${\mathbb{F}}_2$ 上的二次多项式 $q\left(x_1,\dots ,x_n\right)$ 满足$$\left|{\mathbb{E}}_{x\in {\mathbb{F}}_2^n}\left[f(x)(-1{)}^{q(x)}\right]\right|\ge {\delta }^{O(1)}$$

事实证明, 这些版本都是等价的 (各个 $O(1)$ 项之间是线性关系) . 迄今为止最好的界限归功于 Sanders, 他实现了 $e^{(\log K{)}^{O(1)}}$ 的拟多项式界限 (2012) . 多项式 Freiman-Ruzsa 猜想将通过下面的加强 Bogolyubov 猜想得到:

命题 11.5 (多项式 Bogolyubov-Ruzsa 猜想, Sanders, 2012). 如果 $A\subset {\mathbb{F}}_2^n$ 且 $|A|=\alpha 2^n$, 则 $2A-2A$ 包含一个余维数为 $O(\log (1/\alpha ))$ 的子空间.

Bogolyubov 引理的标准形式 (定理 6.0.3) 显示了 $O\left({\alpha }^{-2}\right)$ 的界限. 这个猜想的最佳结果也归功于 Sanders, 他获得了 $(\log (1/\alpha ){)}^{O(1)}$ 的拟多项式界限.

类似地, 可以用 $\mathbb{Z}$ 代替 ${\mathbb{F}}_2^n$ 来制作多项式版本的 Freiman-Ruzsa 猜想. 首先, 我们必须定义一个类似于子空间的居中凸级数 (centered convex progression, 下面我们简称为 CCP) .

定义 11.6. CCP 是如下形式的集合$$P=\left\{x_0+{\ell }_1{x}_1+\cdots +{\ell }_d{x}_d:\left({\ell }_1,\dots ,{\ell }_d\right)\in {\mathbb{Z}}^d\cap B\right\}$$其中 $B$ 是 ${\mathbb{R}}^d$ 中的某个凸中心对称体. CCP 的维度是 $d$, 大小是 $\left|{\mathbb{Z}}^d\cap B\right|$.

$\mathbb{Z}$ 上的多项式 Freiman-Ruzsa 猜想陈述如下.

命题 11.7. [ $\mathbb{Z}$ 的多项式 Freiman-Ruzsa 猜想] 如果 $A\subset$ $\mathbb{Z}$ 且 $|A+A|\le K|A|$, 则存在维度为 $O(\log K)$ 且大小最多为 $|A|$ 的 CCP, 其与 $A$ 的交集大小至少为 $K^{-O(1)}|A|$.

更一般地, Abel 群中的多项式 Freiman-Ruzsa 猜想使用 CCCP (centered convex coset progressions) , 其定义为直和 $P+H$, 其中 $P$ 是 ${\mathbb{Z}}^d\cap B$ 到群的同态下的像, $H$ 是子群的某个陪集.

这个猜想的最佳界限 (在 $\mathbb{Z}$ 和 Abel 群的情况下) 还是由 Sanders 提出来的. 他根据多项式 Bogolyubov-Ruzsa 猜想的拟多项式界限推导得出:

命题 11.8. [ $\mathbb{Z}$ 的多项式 Bogolyubov-Ruzsa 猜想, Sanders, 2012] $A\subset \mathbb{Z}/N\mathbb{Z}$ 且 $N$ 是素数, 则 $2A-2A$ 包含维度为 $O(\log (1/\alpha ))$ 且大小至少为 ${\alpha }^{O(1)}N$ 的 CCCP.

同样的, 我们可以通过使用 CCCP 来得到一般 Abel 群的版本.