灯夫群上的一元方程

《Journal of Algebra》：One-variable equations over the lamplighter group

　　

## 摘要

我们研究灯夫群 $L_2 = \mathbb{Z}_2 \wr \mathbb{Z}$ 上的单变量方程。尽管 $\mathbb{Z}_2 \wr \mathbb{Z}$ 上任意方程的可判定性问题仍未解决，我们证明了单变量单方程的丢番图问题是可判定的。我们的方法将问题归结为 $\mathbb{Z}_2$ 上参数化 Laurent 多项式族的整除性问题，其中多项式的指数关于一个整数参数呈线性依赖关系。为分析这一整除性问题，我们为相关的二元多项式引入了一种符号除法程序，并从所得商式与余式的结构中推导出参数的显式上界。这给出了一种显式的判定程序，其最坏情况时间复杂度为指数级。另一方面，我们证明对于一般类方程，可解性可在近乎二次时间内判定。这些结果揭示了最坏情况与典型计算行为之间的鲜明对比，并为辫积群上的方程研究提供了新工具。

## 引言

设 $F = F(\mathcal{Z})$ 表示以可数生成元集 $\mathcal{Z} = \{z_i\}_{i=1}^{\infty}$ 的自由群。对于群 $G$，以 $\mathcal{Z}$ 中变量表示的 $G$ 上的方程是形如 $w = 1$ 的方程，其中 $w \in F * G$。若 $w = z_{i_1} g_1 \cdots z_{i_k} g_k$，其中 $z_{i_j} \in \mathcal{Z}$ 且 $g_j \in G$，则称 $\{z_{i_1}, \ldots, z_{i_k}\}$ 为 $w$ 的变量集，称 $\{g_1, \ldots, g_k\}$ 为 $w$ 的常数集（或系数集）。

方程 $w(z_1, \ldots, z_k) = 1$ 在群 $G$ 上的解是同态 $\varphi: F * G \to G$，满足 $\varphi|_G = 1_G$ 且 $w \in \ker \varphi$。若 $\varphi$ 是 $w = 1$ 的一个解且 $g_i = \varphi(z_i)$，则我们通常称 $g_1, \ldots, g_k$ 为 $w = 1$ 的一个解。

我们假设 $G$ 配备了一个固定的生成集 $X$，$G$ 中的元素以 $X$ 中元素及其逆元的乘积给出。这自然地将方程 $w = 1$ 的长度（或规模）定义为其左端词 $w$ 的长度。

群 $G$ 上对某一类方程 $\mathcal{C}$ 的丢番图问题 $\mathrm{DP}_{\mathcal{C}}(G)$ 是一个算法问题，用于判定给定的方程 $w = 1$（属于 $\mathcal{C}$）在 $G$ 中是否有解。它可以被视为可满足性问题在群论中的对应物。更一般地，还可以研究方程组的丢番图问题。本文中，我们关注灯夫群 $\mathbb{Z}_2 \wr \mathbb{Z}$ 上的单变量方程类。

我们称 $w = 1$ 为单变量方程，若 $w$ 只涉及一个变量，为方便起见，假设该变量为 $x$，以 $x$ 或 $x^{-1}$ 的形式出现一次或多次。

近年来，灯夫群中的方程、辫积群中的方程以及更一般地在有限生成元可解群中的方程的计算性质引起了广泛关注。

A. Miasnikov 和 N. Romanovsky [22] 证明了 $\mathbb{Z} \wr \mathbb{Z}$ 上方程组的丢番图问题是不可判定的。R. Dong [7] 用不同的论证证明了相同的结果。然而，$\mathbb{Z} \wr \mathbb{Z}$ 上单方程的问题是否可判定仍然未知。I. Lysenok 和 A. Ushakov 证明了自由元可解群上球面方程的丢番图问题是 NP 完全的 [18]，更一般地，定向方程的丢番图问题也是 NP 完全的 [19]。有限生成阿贝尔群的辫积上定向二次方程的丢番图问题是 NP 完全的 [25]。同样，元可解 Baumslag–Solitar 群上二次方程的丢番图问题是 NP 完全的 [20]，灯夫群上也是如此 [26]。文献 [7] 建立了具有不可判定球面方程的有限生成阿贝尔-循环群的存在性。文献 [12] 声称 $\mathbb{Z}_2 \wr \mathbb{Z}$ 上方程组的丢番图问题是可判定的。然而，后来在其证明中发现了缺陷，$\mathbb{Z}_2 \wr \mathbb{Z}$ 上方程组和单方程的可判定性仍然是一个开放问题。关于群辫积中方程可解性的简要综述见文献 [2]。最近，O. Kharlampovich 和 A. Miasnikov [13] 证明了自由阿贝尔群的迭代辫积中丢番图问题是不可判定的。

二次方程（特别是球面方程）在密码学中的应用也得到了探索。特别是，文献 [24] 通过某类有限元可解群上的球面方程，建立了计算群论与基于格的密码学之间的联系。

如上所述，灯夫群上任意单方程的丢番图问题是否可判定仍然是一个开放问题。尽管如此，对于某些受限的方程类，如二次方程 [26]，其可判定性已经得到确立。本文中，我们证明单变量方程构成了另一个这样的类：它是可判定的，其最坏情况时间复杂度由指数函数界定。此外，对于"典型的"单变量方程，解的存在性可在近乎二次时间内判定。

在有限生成阿贝尔群中，单变量方程可以被高效求解。

R. Lyndon [17] 是第一个研究自由群上单变量方程的人，他利用参数化词刻画了其解集。这些参数化词后来由 A. Lorents [15], [16] 和 K. Appel [1] 简化。然而，Lorents 公布了结果但未给出证明，Appel 发表的证明中存在缺陷（见 [5]）。此后 I. Chiswell 和 V. Remeslennikov 提供了完整的证明。自由群上单变量方程的解集还通过上下文无关语言进行了研究 [10]，从而得到了高次多项式时间算法 [4]。最近，R. Ferens 和 A. Je? [9] 描述了同一问题的三次时间算法。

N. Repin [23] 研究了幂零群上的单变量方程。他证明了对于任意 $c \geq 10^{20}$，不存在识别 $c$ 阶自由幂零群中单未知量方程可解性的算法。尽管如此，对于 2 阶有限生成幂零群，这样的算法是存在的（见 [8], [14]）。Repin 还构造了一个 3 阶有限生成幂零群，对于该群不存在识别单未知量方程可解性的算法。

下面我们证明，判定灯夫群上单变量方程的问题可归约为（多个实例的）有限域 $\mathbb{Z}_2$ 上多项式的整除性问题。相应地，我们的复杂度估计反映了 $\mathbb{Z}_2$ 上多项式整除的代价。由于所有算术运算都在大小为二的域中进行，单个域运算的代价是常数。因此，我们在标准 RAM 计算模型下工作，多项式按照第 2.2 节描述的方式表示。

我们使用标准的 Bachmann–Landau 渐近记号（大 $O$ 记号及相关记号）。特别地，对于函数 $f, g: \mathbb{N} \to \mathbb{R}_{\geq 0}$，关系 $f(n)$ 是 $O(g(n))$ 意味着存在常数 $C > 0$ 和 $n_0 \in \mathbb{N}$ 使得对所有 $n \geq n_0$ 有 $f(n) \leq Cg(n)$。

我们还使用软 $O$ 记号 $\tilde{O}$。更精确地，对于函数 $f, g: \mathbb{N} \to \mathbb{R}_{\geq 0}$，我们称 $f(n)$ 是 $\tilde{O}(g(n))$，若存在常数 $k \geq 0$ 使得 $f(n)$ 是 $O(g(n)(\log n)^k)$。等价地，$\tilde{O}$ 抑制了输入规模 $n$ 中的对数多项式因子。

我们简要描述论文的结构及每一节的作用。

在第 2 节中，我们回顾 $\mathbb{Z}_2$ 上 Laurent 多项式的基本概念，特别关注其数据表示和基本算术运算的计算复杂度。本节建立了全文使用的计算模型，并提供了后续反复引用的复杂度上界。

在第 3 节中，我们回顾灯夫群 $L_2 = \mathbb{Z}_2 \wr \mathbb{Z}$ 的定义，并固定其标准表示的记号。我们还引入 $L_2$ 上的单变量方程，并将其重新表述为适合算法分析的形式。

在第 4 节中，我们引入 $\delta$ 参数化多项式的概念，即形如 $\sum_{i=s}^{t} f_i(z) z_i^{\delta}$ 的表达式，其中 $f_s(z), \ldots, f_t(z) \in \mathbb{Z}_2[z^{\pm}]$ 是固定的 Laurent 多项式，$\delta$ 是参数。对于给定的 $L_2$ 上单变量方程 $w = 1$，我们构造两个 $\delta$ 参数化多项式 $F_{\delta}$ 和 $G_{\delta}$，并证明 $w = 1$ 的可判定性归结为判定是否存在某个 $\delta \in \mathbb{Z}$ 使得 $G_{\delta}$ 能被 $F_{\delta}$ 整除。这一归约自然地将问题分为两种情况，取决于 $\sigma_x(w)$ 是否为零，并将整除性确定为主要计算任务。

在第 5 节中，我们研究 $\delta$ 参数化多项式 $F_{\delta}$ 和 $G_{\delta}$ 的结构性质。我们表明这些多项式可以借助 $\mathbb{Z}_2$ 网格的有限子集获得几何解释，并开发了一种词追踪程序以便高效计算它们。我们还建立了其规模和支撑的几个上界，这些上界将在论文余下部分反复使用。

在第 6 节中，我们研究 $\delta$ 参数化多项式的整除性问题并建立其可判定性。主要思想是用辅助变量 $y$ 替换 $F_{\delta}$ 和 $G_{\delta}$ 中的参数单项式 $z^{\delta}$，从而得到二元多项式 $F(z, y)$ 和 $G(z, y)$。然后我们在域 $\mathbb{Z}_2(z)$ 上执行 $G$ 除以 $F$ 的符号除法，并分析所得的商式和余式。这自然地导致两种情况，取决于余式是否为零。在每种情况下，我们推导出参数 $\delta$ 的显式上界，从而得到整除性的判定程序，最终证明该问题属于 NP。

最后，在第 7 节中我们分析所得算法的复杂度并证明，尽管最坏情况运行时间为指数级，但在一般情况下该问题可在近乎二次时间内求解。这建立了灯夫群上单变量方程的可判定性，并展示了最坏情况与典型行为之间的强烈对比。

### 小节摘录

**预备知识：Laurent 多项式**

设 $R$ 是含幺交换环。$R$ 上的 Laurent 多项式是形如 $\sum_{i=-\infty}^{\infty} a_i z^i$（$a_i \in R$）的表达式，其中除了有限多个系数 $a_i$ 外其余均为零。两个多项式的和定义为 $\sum_{i=-\infty}^{\infty} a_i z^i + \sum_{i=-\infty}^{\infty} b_i z^i = \sum_{i=-\infty}^{\infty} (a_i + b_i) z^i$，两个多项式的积定义为 $\left(\sum_{i=-\infty}^{\infty} a_i z^i\right) \cdot \left(\sum_{i=-\infty}^{\infty} b_i z^i\right) = \sum_{i=-\infty}^{\infty} c_i z^i$，其中 $c_i = \sum_{j=-\infty}^{\infty} a_j b_{i-j}$。所有 Laurent 多项式组成的集合，记为 $R[z^{\pm}]$，配备上述 $+$ 和 $\cdot$ 运算构成一个环，见 [6]。本文中，环的……

**预备知识：灯夫群**

定义函数 $f: \mathbb{Z} \to \mathbb{Z}_2$ 的支撑为集合 $\mathrm{supp}(f) = \{i \in \mathbb{Z} \mid f(i) \neq 0\}$。定义集合 $\mathbb{Z}_2^{\mathbb{Z}} = \{f: \mathbb{Z} \to \mathbb{Z}_2 \mid |\mathrm{supp}(f)| < \infty\}$，以及在 $\mathbb{Z}_2^{\mathbb{Z}}$ 上的二元运算 $+$，对 $f, g \in \mathbb{Z}_2^{\mathbb{Z}}$ 产生 $f + g \in \mathbb{Z}_2^{\mathbb{Z}}$，定义为 $(f + g)(z) = f(z) + g(z)$（$z \in \mathbb{Z}$）。对于非平凡的 $f$，方便起见定义 $m(f) = \min_{z \in \mathrm{supp}(f)} z$ 和 $M(f) = \max_{z \in \mathrm{supp}(f)} z$。对于 $f \in \mathbb{Z}_2^{\mathbb{Z}}$ 和 $b \in \mathbb{Z}$，定义 $f_b \in \mathbb{Z}_2^{\mathbb{Z}}$ 为 $f_b(z) = f(z + b)$（$z \in \mathbb{Z}$），这是 $\mathbb{Z}_2^{\mathbb{Z}}$ 上的右 $\mathbb{Z}$-作用，因为 $f_0 = f$ 且 $f_{b_1 + b_2}(z) = f(z + b_1 + b_2) = (f_{b_1})_{b_2}(z)$。因此我们可以考虑半直积 $\mathbb{Z} \ltimes \mathbb{Z}_2^{\mathbb{Z}}$。

**单变量方程：转化为参数化多项式**

在本节中，我们引入 $\delta$ 参数化多项式，并证明 $L_2$ 上单变量方程的丢番图问题 $\mathrm{DP}_1(L_2)$ 可以在多项式时间内归约为 $\delta$ 参数化多项式的整除性问题。

**引理 4.1** 将一个词 $w(a, t, x)$ 转化为形式 $c_0 x^{\varepsilon_1} c_1 \cdots c_{k-1} x^{\varepsilon_k} c_k = 1$ 需要线性时间，其中 $c_i = (\delta_i, f_i) \in \mathbb{Z} \ltimes \mathbb{Z}_2^{\mathbb{Z}}$ 是常数且 $\varepsilon_i = \pm 1$。

**证明** 将 $w(a, t, x)$ 改写为交替乘积 $w_0(a, t) x^{\varepsilon_1} w_1(a, t) \cdots w_{k-1}(a, t) x^{\varepsilon_k} w_k(a, t)$ 是直接的，然后对每个部分应用引理 3.1……

**$F_{\delta}$ 和 $G_{\delta}$ 的递推公式**

考虑方程 $w(a, t, x) = 1$ 以及词 $w$ 的表达式 (7) 的紧凑形式。多项式 $F_{\delta}$ 和 $G_{\delta}$ 可以通过从右向左读取词 $w$ 来高效构造，如下面引理所描述。

**引理 5.1** 对于空词 $\varepsilon$，有 $x_{\varepsilon} = t_{\varepsilon} = 0$ 且 $F_{\delta,\varepsilon} = G_{\delta,\varepsilon} = 0$。

**引理 5.2** 若 $w' = x \circ w$，则 $t_{w'} = t_w$，$x_{w'} = x_w + 1$，$F_{\delta, w'} = F_{\delta, w} + z^{\delta}$，$G_{\delta, w'} = G_{\delta, w}$。

**证明** 将公式 (12) 左边乘以 $x = (\delta, f)$ 得到……即得所要求的公式。

**引理 5.3** 若 $w' = x^{-1} \circ w$，则 $t_{w'} = t_w$，$x_{w'} = x_w - 1$，$F_{\delta, w'} = F_{\delta, w} + z^{\delta - 1}$，$G_{\delta, w'} = G_{\delta, w}$。

**参数化多项式的整除性问题**

设 $F_{\delta}$ 和 $G_{\delta}$ 为 $\delta$ 参数化多项式，其中 $F_{\delta}$ 非平凡。在本节中我们证明 $F_{\delta} \mid G_{\delta}$ 是可判定的。

**$\mathbb{Z}_2 \wr \mathbb{Z}$ 上单变量方程丢番图问题的一般情况复杂度**

在本节中，我们论证一个一般（典型）的方程 $w(a, t, x) = 1$ 满足 $\sigma_x(w) \neq 0$，从而可以在近乎二次时间内求解。

让我们回顾几个与一般情况复杂度相关的定义 [21, 第 10 章]。对 $m \in \mathbb{N}$ 定义（有限）集合 $S_m = \{w \in F(a, t, x) \mid |w| = m\}$，称为 $F(a, t, x)$ 的 Cayley 图中半径为 $m$ 的球面。设 $P_m$ 为 $S_m$ 上的均匀概率分布。我们称集合 $S \subseteq F(a, t, x)$ 在 $F(a, t, x)$ 中是一般的，若 $P_m(S \cap S_m) = |S \cap S_m| / |S_m| \to 1$（当 $m \to \infty$ 时），即……

Alexander Ushakov | Yankun Wang