Subsequence Sums in Permutations

技术摘要：排列中的子序列和

问题陈述
本文研究了集合 $\{1, 2, \dots, n\}$ 的排列中是否存在特定的算术子序列。虽然经典的算术拉姆齐理论（例如范德瓦尔登定理）保证了在足够大的着色集合中存在单色算术级数，但恩特林格和杰克逊（1973 年）证明了排列可以避免单调的 3 项算术级数（3-AP）。作者提出，其他算术性质，特别是“加法”子序列，在大型排列中是否不可避免。

正整数序列 $(a_1, a_2, \dots, a_k)$ 被定义为 $\ell$-加法的，如果其项的和满足 $\sum_{i=1}^k a_i = \ell a_1$ 或 $\sum_{i=1}^k a_i = \ell a_k$。本文的主要关注点是 2-加法子序列（即和等于首项或末项的两倍）及其单调变体。本文解决了两个主要问题：

1. 对于固定的长度 $k \ge 3$，是否存在一个 $n$，使得 $\{1, \dots, n\}$ 的每一个排列都包含一个长度为 $k$ 的 2-加法子序列？
2. 此类子序列存在的精确阈值和界限是什么，特别是当限制为单调序列时？

方法论
作者结合了组合论证、案例分析以及算术拉姆齐理论的技术。

• 组合构造与反证法：存在性证明的核心（定理 1.1 和 1.3）依赖于构造排列的特定子集并使用反证法。通过分析元素的相对位置（使用 $L_p(s)$ 和 $R_p(s)$ 分别表示排列 $p$ 中 $s$ 左侧和右侧的元素），作者证明了避免 2-加法子序列会导致排列布局中的结构性矛盾。
• 界限技术：为了确定最小 $n$（记为 $f(k, 2)$）的上界，作者定义了一组由排列前 $2k-1$ 个元素导出的“危险”和。他们利用这些和的最小公倍数（LCM）来确定阈值 $N_k$，超过该阈值后，2-加法子序列将不可避免。
• 下界与反例：下界是通过显式构造大小为 $n-1$ 且缺乏所需子序列的排列来建立的。
• 渐近分析：本文利用素数定理（通过罗瑟的结果）推导了大型排列中此类子序列数量的下界。
• 变换论证：为了将结果扩展到乘积和逆和，作者使用了标准变换，将 $\{1, \dots, n\}$ 中的加法性质映射到 $\{2^1, \dots, 2^n\}$ 中的乘法性质，以及映射到 $\{L_n/1, \dots, L_n/n\}$ 中的逆加法性质（其中 $L_n$ 是 $1$到$n$ 的最小公倍数）。

主要贡献与结果

1. 2-加法子序列的存在性（定理 1.1）：
   对于任意固定的 $k \ge 3$，如果 $n$ 足够大，$\{1, \dots, n\}$ 的每一个排列都包含一个长度为 $k$ 的 2-加法子序列。

   • 界限：本文提供了最小此类 $n$（记为 $f(k, 2)$）的多项式界限。
     • 下界：$f(k, 2) \ge (k-1)(3k-4)/2$。
     • 上界：$f(k, 2) \le 9(k-2)(k^2-k)^2/4$。
   • $k=3$ 的精确值：作者证明了 $f(3, 2) = 5$。$\{1, \dots, 5\}$ 的每一个排列都包含一个长度为 3 的 2-加法子序列，而 $n=4$ 时存在反例。

2. 单调 2-加法子序列（定理 1.3）：
   本文解决了更严格的条件，即子序列必须是单调的。

   • 结果：如果 $n \ge 18$，$\{1, \dots, n\}$ 的每一个排列都包含一个长度为 3 的单调 2-加法子序列。
   • 最优性：数值 18 是最优的；构造了一个 $\{1, \dots, 17\}$ 的特定排列，它避免了此类子序列。
   • 未解决问题：对于长度为 $k \ge 4$ 的单调 2-加法子序列，该结论是否成立仍未知。

3. 一般 $\ell$-加法子序列：

   • 如果 $k = \ell$，恒等排列 $(1, 2, \dots, n)$ 不包含长度为 $k$ 的 $\ell$-加法子序列。
   • 本文解决了两个特定的混合情况：
     • $f(4, 3) = 8$（8 个元素的每一个排列都有一个长度为 4 的 3-加法子序列）。
     • $f(3, 4) = 13$（13 个元素的每一个排列都有一个长度为 3 的 4-加法子序列）。
   • $k \neq \ell$ 且 $k, \ell \ge 4$ 的一般情况被留作未解决问题。

4. 子序列计数：
   作者提供了大小为 $n$ 的任意排列中长度为 $k$ 的 $\ell$-加法子序列最小数量的界限：

   • 上界：$O(n^{k-1})$。
   • 下界：$\Omega(n / \log n)$（假设 $f(k, \ell)$ 存在），这是利用素数分布论证推导得出的。
   • 长度为 3 的单调 2-加法子序列的具体界限给出为 $n/[18(\log n - \log 18 + 2)] - 6 \le G(3, 2, n) \le \frac{1}{18}n^2 + \frac{7}{6}n$。

5. 扩展到乘积和逆和：
   利用算术拉姆齐理论变换，本文将加法结果扩展到：

   • 乘法：足够大的每一个排列都有一个子序列，其乘积是首项或末项的平方（2-乘法）。
   • 逆加法：足够大的每一个排列都有一个子序列，其倒数之和是首项或末项倒数的两倍。
   • 本文指出，对于长度为 3 的单调 2-乘法子序列，阈值至多为 32（且恰好为 32，因为 $n=31$ 时存在反例）。

意义与主张
本文声称建立了专门针对排列的首个舒尔 - 拉多（Schur-Rado）类型结果，证明了虽然排列可以避免单调算术级数（3-AP），但它们无法避免任意长度的 2-加法子序列。这项工作提供了这些结构存在性的首个多项式界限，并确定了小情况（$k=3$）的精确阈值。

作者谦逊地将他们的贡献表述为进一步研究的基础。他们强调，$k \neq \ell$ 的一般情况仍然未解，且长度 $k > 3$ 的单调 2-加法子序列的行为尚不清楚。本文将这些发现定位为理解排列结构与算术性质之间相互作用的步骤，并提出了加权子序列和以及乘法和逆加法变体阈值细化的未来方向。