A problem on sumset sizes of sets of lattice points

技术摘要：关于格点集合和集大小的问题

问题陈述
本研究探讨的核心问题是加法交换半群中有限子集的“和集大小范围”。具体而言，对于半群 $X$ 和正整数 $h$ 与 $k$，本文研究了 $k$ 元子集 $A$ 的 $h$ 次和集（$hA$）以及限制性$h$次和集（$\widehat{hA}$）的可能基数。

作者定义了两个主要关注的集合：

1. $R_X(h, k) = \{ |hA| : A \subseteq X, |A| = k \}$
2. $\widehat{R}_X(h, k) = \{ |\widehat{hA}| : A \subseteq X, |A| = k \}$

本文重点比较了当 $X$ 为整数加法群 ($\mathbb{Z}$) 与当 $X$ 为 $n$ 维格点群 ($\mathbb{Z}^n$) 时这些范围的差异。由于 $\mathbb{Z}$ 同构于 $\mathbb{Z}^n$ 的一个子群，因此 $R_{\mathbb{Z}}(h, k) \subseteq R_{\mathbb{Z}^n}(h, k)$ 是显然成立的。核心问题在于反向包含关系是否成立，从而建立整数与 $n$ 维格点之间和集大小范围的等价性。

此外，本文提出了一个计算效率问题。即使用格点是否可以比使用整数更高效地计算和集的大小集合。这被转化为一个几何问题：在 $n$ 维空间中工作的自由度，是否允许通过检查具有显著更小直径的集合（具体为包含在 $[0, N_n]^n$ 中的集合）来确定这些范围，相比于一维情况下的集合（包含在 $[0, N]$ 中的集合）？

方法论
本文采用的主要方法是通过构造一个特定的线性映射，在格点子集与整数子集之间建立一个保持和集基数的同构关系。

1. 线性映射构造： 作者定义了一个线性函数 $\phi_g: \mathbb{R}^n \to \mathbb{R}$：
   $$\phi_g(x_1, \dots, x_n) = \sum_{i=1}^n x_i g^{i-1}$$
   其中 $g$ 是一个选定的正整数，满足 $g > h\ell$，且 $\ell$ 是集合 $A$ 中坐标的界限。

2. 表示的唯一性： 通过选择 $g > h\ell$，函数 $\phi_g$ 在格点立方体 $[0, h\ell]^n \cap \mathbb{Z}^n$ 上是单射（一一对应）的。这依赖于整数 $g$ 进制表示的唯一性。

3. 保持和集结构： 由于 $\phi_g$ 是线性的且在相关定义域内是单射的，因此对于该定义域内的任何集合 $A$，它满足以下恒等式：

   • $\phi_g(hA) = h\phi_g(A)$
   • $\phi_g(\widehat{hA}) = \widehat{h\phi_g(A)}$
     这些恒等式确保了和集的基数得以保持：$|hA| = |h\phi_g(A)|$。

主要结果
本文确立了以下主要定理：

定理 1： 对于所有正整数 $h$ 和 $k$，
$$R_{\mathbb{Z}}(h, k) = R_{\mathbb{Z}^n}(h, k)$$
且
$$\widehat{R}_{\mathbb{Z}}(h, k) = \widehat{R}_{\mathbb{Z}^n}(h, k)$$

证明大纲：

• 包含关系 $R_{\mathbb{Z}} \subseteq R_{\mathbb{Z}^n}$： 这是显而易见的，因为 $\mathbb{Z}$ 嵌入到 $\mathbb{Z}^n$ 中。
• 包含关系 $R_{\mathbb{Z}^n} \subseteq R_{\mathbb{Z}}$： 令 $t \in R_{\mathbb{Z}^n}(h, k)$。存在一个集合 $A \subset \mathbb{Z}^n$ 使得 $|A|=k$ 且 $|hA|=t$。通过平移不变性，可以假设$A$具有非负坐标，且包含在$[0, \ell]^n$内。选择$g > h\ell$，映射$\phi_g$将$A$转换为一个整数集合$\phi_g(A) \subset \mathbb{N}0$，且$|\phi_g(A)| = k$。由于$\phi_g$的线性和单射性，$|h\phi_g(A)| = |hA| = t$。因此，$t \in R{\mathbb{Z}}(h, k)$。
• 对于限制性和集，使用第二个恒等式进行同样的逻辑推理，证明了 $\widehat{R}_{\mathbb{Z}^n}(h, k) = \widehat{R}_{\mathbb{Z}}(h, k)$。

该函数 $\phi_g$ 被识别为弗赖曼同构（Freiman isomorphism）的一个经典案例。

开放问题与几何问题
虽然本文证明了可能的和集大小的集合是相同的，但并未声称计算这些集合的计算量也是相同的。本文强调了以下开放问题（引用自 Nathanson [4] 和 Gowers [1]）：

1. 问题 1 & 2（限定搜索空间）： 确定最小整数 $N(h, k)$ 和 $\widehat{N}(h, k)$，使得通过仅考虑区间 $[0, N]$（或 $[0, \widehat{N}]$）内的子集即可完整计算范围 $R_{\mathbb{Z}}(h, k)$ 和 $\widehat{R}_{\mathbb{Z}}(h, k)$。
2. 问题 3（维度效率）： 定义 $N_n(h, k)$ 为使得 $R_{\mathbb{Z}}(h, k)$ 可以通过 $n$ 维立方体 $[0, N_n]^n$ 中的子集进行计算的最小整数。本文提出了如下不等式：
   $$N_n(h, k) \leq N(h, k)^{1/n}$$
   本文询问该不等式是否成立，若成立，则意味着在 $n$ 维空间中工作允许使用比一维情况下直径更小的集合（从而减少候选集合数量）来计算和集大小。

意义与主张
本文声称解决了关于“和集大小范围”在整数与格点之间是否存在差异的结构性问题。结果证实，和集范围在格点维度下是保持不变的；即对于 $k$ 个元素，其可能的和集大小集合在选择来自 $\mathbb{Z}$ 或 $\mathbb{Z}^n$ 的元素时是完全相同的。

该结果的意义在于问题的简化：理论上可以通过构造格点集合来计算整数的和集大小范围。然而，本文明确将剩余的挑战界定为一个几何优化问题。它并未声称格点提供了一种更快的计算这些范围的算法，而是提出了这样一个问题：高维空间的几何自由度是否允许通过减小所需集合的“直径”来降低计算这些范围所需的代价。本文最后指出，估计这些界限并验证该维度不等式仍是开放性的问题。