素数域上的单项式有向图何时同构？

素数域上由一个单位乘数决定同构

对素数幂 q 与正整数 m、n，单项式有向图 D(q;m,n) 的顶点集为 F_q × F_q，从 (x1,x2) 到 (y1,y2) 有一条弧，当且仅当 x2 + y2 = x1^m · y1^n。每个这样的有向图都有 q² 个顶点、q³ 条弧，每个顶点的入度和出度均为 q，并在 (0,0) 处有一个自环。

此前的工作证明了其中一个方向：若存在与 q−1 互素的整数 k，使得模 q−1 下 m2 ≡ k·m1 且 n2 ≡ k·n1，则 D(q;m1,n1) 与 D(q;m2,n2) 同构。Kodess 与 Lazebnik 猜想其逆命题也成立。本文证明了当 q 为素数时该逆命题成立，因此在素数域上，乘数条件既是充分条件也是必要条件。

这个乘数并非任意。它必须与 q−1 互素，且两个同余式都在模 q−1 下成立。同一个整数 k 同时缩放 m 与 n，这正是该判据针对参数对 (m,n) 而非单独针对 m 或 n 的原因。

扩域上存在没有此类乘数的同构对

该猜想在一般情况下不成立。论文记录 D(25;3,6) 与 D(25;3,18) 同构，但不存在整数 k 使模 24 下 (3,18) ≡ k·(3,6)。作者也承认其早先工作中曾有一处计算错误，遗漏了这一对。

这并非孤立的偶然。定理 2 构造了一个无限族：对任意满足 R ≡ 1 mod 4 的奇素数幂 R，取 q = R²、m = (R+1)/2，则三个有向图 D(q;m,2m)、D(q;m,2m²) 与 D(q;m²,2m) 两两同构，而不存在整数 k 把 (m,2m) 映到 (m,2m²) 或 (m²,2m)。

其中最小的成员是 q = 25，此时 R = 5，a = (R−1)/2 = 2，m = 3，n = 6，得到 D(25;3,6) ≅ D(25;3,18) ≅ D(25;9,6)。这些有向图各有 625 个顶点和 15625 条弧。因此素数域判据是一条真实的边界，而非关于所有有限域的一般定理。

把同构规范化并迫使其成为线性映射

定理 1 的证明首先归约到 m1 ≠ n1 的情形，因为 m1 = n1 已由此前结果处理。先前工作给出的必要条件给出 m2 = m1 与 n2 = n1，其中 x 表示 gcd(x, q−1)。必要时转向反向有向图，可让作者假设 m1 ≤ n1。

于是同构可写成 φ(x,y) = (f(x,y), g(y))，并具有把 (0,0) 映到 (0,0)、把 (1,0) 映到 (1,0) 的规范化形式。技术核心在于证明 g 是线性的，即对某个 F_p 中的非零 λ 有 g(z) = λz。论证考察 g 在 n1 次幂子群 A 的陪集上的作用，证明 g 是非平凡 Cayley 有向图 Cay(F_p, A) 的自同构，并引用经典结果：此类素数次 Cayley 有向图的自同构群嵌入仿射群 AGL1(F_p)。

由此，证明进一步强化为对 F_p 中所有 x、y、z 有 g(z) = z、f(x,y)^m2 = x^m1 与 f(x,y)^n2 = x^n1。令 F(x) = f(x,0)，得到 F_p 的一个置换，满足 F(x)^m2 = x^m1 与 F(x)^n2 = x^n1，而一个单独的引理恰好把这样的置换转化为所需的、与 q−1 互素的乘数 k。n1 = 1 的情形走另一条路径：两个不同顶点没有公共入邻域，当且仅当它们的第一坐标相同，这迫使 φ 的第一坐标只依赖于 x，随后 g 的可加性给出 g(z) = z。

借助子域上的基变换构造反例

定理 2 是构造性的，而非仅仅存在性的。取 R 为满足 R ≡ 1 mod 4 的奇素数幂，q = R²，m = (R+1)/2，a = (R−1)/2，作者取 F_q 的一个本原元 α 并令 β = α^m。由于 q−1 = 4am，β 的阶为 4a = 2(R−1)，因此 β 落在 F_R 之外，而 β² 生成 F_R^×；于是 {1, β} 是 F_q 在 F_R 上的一组基。

该同构由两个映射拼装而成。一个可逆的 F_R-线性映射 T 把 1 送到 β^{3a}、把 β 送到 β，这是一次基变换；另一个伴随置换 σ 定义在 F_q 上，由 σ(α^j) = α^{j+s(j)} 给出，其中 j 为偶数时 s(j) = a，j 为奇数时 s(j) = 2a。由于 a 为偶数，j ↦ j + s(j) 保持奇偶性，并在 Z_{q−1} 的每个奇偶类上充当平移，因此 σ 是双射。恒等式 T(x^m y^{2m}) = σ(x)^m σ(y)^{2m²} 随后使 φ(x,y) = (σ(x), T(y)) 成为从 D(q;m,2m) 到 D(q;m,2m²) 的同构。

第三个同构 D(q;m,2m) ≅ D(q;m²,2m) 则来自充分性方向：k = m + 4a 与 4a 互素，并满足 k(m,2m²) ≡ (m²,2m)。不存在性那一半是一个简短的同余障碍。每个 (m,2m) 的标量倍数 (u,v) 都满足 v ≡ 2u，但 2m² − 2m = 2m(m−1) = 2ma = (q−1)/2，它在模 q−1 下不为 0，因此没有乘数能产生这两个目标参数对中的任何一个。

非素数域与算法检测仍未解决

论文明确说明它没有解决什么。对非素数的素数幂，定理 2 表明乘数条件不是必要的，但在非素数有限域上哪些参数对给出同构的单项式有向图，这一般性分类仍然悬而未决。

另有两个问题被提出而未解决。第一个问是否存在有向图的有限族 H，使得对充分大的素数幂 q 和所有参数对，若对 H 中每个 H 都有子图计数相等 n(H,D1) = n(H,D2)，就能推出 D1 ≅ D2；作者表示他们未能找到这样的族。第二个问是否存在一个关于 q 的多项式时间算法来判定 D1 与 D2 是否同构。

这些是作为开放问题而非结果提出的，也应当如此理解：论文已证明的贡献是素数域判据加上扩域反例族。

套用乘数检验前先确认是否为素数

本文的实用分界在于 q 是素数还是非素数的素数幂。若 q 为素数，乘数检验在两个方向上都是决定性的：计算 m1 = gcd(m1, q−1)、n1 = gcd(n1, q−1)、m2 = gcd(m2, q−1)、n2 = gcd(n2, q−1)，则两个有向图同构，当且仅当存在单个与 q−1 互素的 k，在模 q−1 下把 (m1,n1) 缩放为 (m2,n2)。

若 q 不是素数，找不到这样的 k 什么也证明不了。定理 2 的族给出具体见证：只要 R 是满足 R ≡ 1 mod 4 的奇素数幂，q = R²，m = (R+1)/2，则参数对 (m,2m)、(m,2m²) 与 (m²,2m) 两两由同构相连，尽管没有可容许的乘数把它们联系起来。最小的实例是 q = 25、m = 3，这正是要牢记的反例，用以否定对该判据的任何不加区分的套用。

因此最具决策意义的要点正是适用范围条件本身：充要的乘数判据是关于素数域的定理，而扩域反例表明，把它推广到该设定之外并非缺少一个证明，而是一个错误的陈述。

本文引用的文献