Positivity of Nearly Linearly Recurrent Sequences

这是一份关于论文《Positivity of Nearly Linearly Recurrent Sequences》（近线性递推序列的正性）的详细技术总结。

1. 研究背景与问题定义

背景：
近线性递推（Nearly Linear Recurrences, NLRS）是经典线性递推序列（LRS）的推广，也是控制理论中线性时不变系统（LTI）和程序分析中线性约束循环的特例。

• 定义：一个 $d$ 阶近线性递推序列 $u = (u_n)_{n=0}^\infty$ 满足不等式系统：
  $$\varepsilon_0 \le u_{n+d} - a_{d-1}u_{n+d-1} - \dots - a_0 u_n \le \varepsilon_1$$
  其中 $a_i, \varepsilon_0, \varepsilon_1$ 为有理常数，$a_0 \neq 0$。当 $\varepsilon_0 = \varepsilon_1 = 0$ 时，退化为经典线性递推；当 $\varepsilon_0 = \varepsilon_1$ 时，退化为非齐次线性递推。
• 应用场景：NLRS 可视为受有界扰动（bounded disturbances）的 LRS，或 LTI 系统中带有非确定性控制输入（control inputs）的离散时间系统。

核心问题：正性问题（Positivity Problem）
给定一个近线性递推关系（系数 $a_i, \varepsilon_0, \varepsilon_1$）和初始值 $u_0, \dots, u_{d-1}$，判断所有满足该递推关系和初始条件的序列 $u$ 是否对所有 $n \in \mathbb{N}$ 都满足 $u_n \ge 0$。

• 这是经典 LRS 正性问题的推广（LRS 正性问题本身是计算机科学中著名的未决问题，仅对低阶已知可判定）。
• 在控制理论中，这等价于 LTI 系统的**非可达性（non-reachability）**问题：即系统状态是否永远无法进入半空间 $\{x \in \mathbb{R}^d : e_d^\top x < 0\}$。

2. 主要贡献与结果

核心成果：
论文证明了二阶（Order 2）近线性递推序列的正性问题是可判定的（Decidable）。

• 该判定过程不仅适用于有理数常数，甚至适用于实代数数常数。
• 这是该领域的一个重大突破，因为对于一般的 LRS，正性问题在 5 阶以上仍是开放的，而 NLRS 由于引入了非确定性（扰动），通常被认为比 LRS 更难处理。

关键贡献点：

1. 判定过程构建：针对二阶情况，提出了一套完整的判定算法。
2. 超越性新结果：为了证明算法的终止性，作者证明了一个关于无穷级数的新超越性定理（Theorem 2）。该定理指出，在特定条件下，由 $|a\lambda^n + \bar{a}\bar{\lambda}^n|$ 构成的无穷级数之和是超越数（transcendental），而非代数数。
3. 技术融合：结合了控制理论中的“bang-bang 原理”（极值控制原理）、丢番图逼近（Diophantine approximation）、Schlickewei 的 $p$-进子空间定理（Subspace Theorem）以及 Baker 关于对数线性形式的定理。

3. 方法论与技术细节

3.1 问题转化：矩阵幂形式与 bang-bang 原理

作者首先将 NLRS 转化为向量递推形式：
$$x_{n+1} = A x_n + r_n e_1, \quad r_n \in [\varepsilon_0, \varepsilon_1]$$
其中 $A$ 是伴随矩阵，$r_n$ 是控制变量。

• 目标：判断对于所有可能的控制序列 $r_n$，状态 $x_n$ 是否始终保持在半空间内。
• Bang-Bang 原理：为了判断序列是否可能变为负值，只需考虑最坏情况。作者证明，使序列值最小的控制策略总是取区间的端点（即 $r_n$ 取 $\varepsilon_0$ 或 $\varepsilon_1$）。
• 最小序列构造：定义了一个“最小序列” $u^{(\min)}_n$，其构造依赖于另一个辅助线性递推序列 $u^{(c)}_n$ 的符号。如果 $u^{(c)}_k < 0$，则取 $r = \varepsilon_1$；否则取 $\varepsilon_0$。
• 判定原问题等价于判定序列 $u^{(\min)}_n$ 是否恒非负。

3.2 二阶情况的分类讨论

对于二阶系统，矩阵 $A$ 的特征值 $\lambda, \bar{\lambda}$ 决定了序列行为。作者分四种情况讨论：

1. 正实谱：若 $A$ 的某次幂具有正实特征值，则序列属于特定闭包类 $C_{pos}$，正性可判定。
2. 谱半径 > 1：若 $|\lambda| > 1$，序列通常发散至负无穷（除非特定系数为 0），可直接判定。
3. 谱半径 = 1：若 $|\lambda| = 1$，绝对值项的累加和发散，导致序列最终为负。
4. 谱半径 < 1（最困难的情况）：
   • 此时序列收敛。判定正性归结为判断极限 $\lim_{n \to \infty} u^{(\min)}_n$ 的符号。
   • 该极限包含一个无穷级数项：$\sum_{k=0}^\infty |u^{(c)}_k|$。
   • 关键难点：需要确定该级数之和是否为零。如果和为零，则极限可能为 0 或负；如果和不为零，则可以通过数值计算确定符号。

3.3 超越性证明（Theorem 2）

为了证明上述级数之和不为零（即它是超越数），作者采用了反证法：

• 假设：假设该和 $\alpha$ 是代数数。
• 工具：利用Schlickewei 的 $p$-进子空间定理（Subspace Theorem）。
• 构造：
  1. 利用 $\lambda$ 的辐角 $\theta$ 的连分数展开，构造一系列线性递推关系，使得 $|u^{(c)}_m|$ 在“几乎所有”索引处满足这些递推。
  2. 构造一个线性形式 $L$，其系数包含 $\alpha$。利用子空间定理，如果 $\alpha$ 是代数数，则存在另一个线性形式 $F$ 使得 $F(\Lambda_n) = 0$。
  3. 通过减去 $F$ 的倍数，消去 $\alpha$ 相关的项，得到一个新的线性形式 $L'$。
  4. 利用 Baker 定理（关于对数线性形式的下界）证明 $|L'(\Lambda_n)|$ 不能衰减得比某个多项式速度更快。
  5. 然而，根据构造，$L(\Lambda_n)$ 的衰减速度极快（指数级）。这导致了矛盾。
• 结论：假设不成立，$\alpha$ 必须是超越数，因此 $\alpha \neq 0$。这使得极限值的符号可以通过有限精度的数值计算确定。

4. 结果分析

• 可判定性：对于二阶 NLRS，正性问题完全可解。算法流程包括：检查特征值谱半径、处理发散情况、以及在收敛情况下计算极限（利用超越性保证极限非零）。
• 局限性：目前结果仅限于二阶。扩展到三阶及以上涉及更复杂的几何和数论问题，仍是开放课题。
• 变体问题：
  • 存在性变体（是否存在一条正序列）：等价于 LTI 系统的不变性问题，由于 bang-bang 原理不再适用，需要不同的技术。
  • 未初始化变体（是否存在初始值使得序列为正）：等价于线性约束循环的非终止性问题，在二维下已知可判定，但技术路线不同（基于凸分析）。

5. 意义与影响

1. 理论突破：首次解决了近线性递推序列（一类受扰动系统）的正性问题，填补了从确定性 LRS 到非确定性 LTI 系统判定理论之间的空白。
2. 跨学科融合：成功将控制理论（bang-bang 原理）、程序分析（终止性分析）与数论（超越数理论、子空间定理）紧密结合。特别是利用子空间定理解决算法判定问题，展示了数论工具在理论计算机科学中的强大应用。
3. 独立价值：文中证明的关于特定无穷级数的超越性定理（Theorem 2）本身具有独立的数学价值，不依赖于具体的判定问题背景。
4. 未来方向：为更复杂的控制系统的可达性分析提供了新的思路，尽管处理一般多面体控制集和点目标仍面临挑战。

总结：该论文通过巧妙的数学构造，将复杂的非确定性系统正性问题转化为一个关于无穷级数超越性的数论问题，并利用子空间定理解决了这一难题，从而在二阶情形下实现了完全可判定。这是理论计算机科学和动力系统领域的一项重要进展。