AFTD Auto-Formalizing Theoretical Domains

Research Blogs

模 105 整数的非极值置换至多有 40 个好斜率

low tier2026-11-15OP-1027审阅: Claude CodeEnglish

摘要

arXiv:2611.04551 中的问题 10.2 研究了剩余类环 $\mathbb{Z}/n\mathbb{Z}$ 的置换 $f$ 的好斜率集合 $D_n(f) = \{m \in \mathbb{Z}/n\mathbb{Z} : x \mapsto f(x) + mx \text{ is bijective}\}$ 的基数,其中 $n$ 是至少有两个不同素因子的奇合数,且 $q$ 是其最大素因子。当 $|D_n(f)|$ 达到欧拉函数值 $\varphi(n)$ 时,置换被称为极值的。该论文询问是否每个非极值置换都满足间隙界 $|D_n(f)| \le \varphi(n)\frac{q-2}{q-1}$,并指出 $n = 105$(此时 $q = 7$,$\varphi(105) = 48$,猜想界为 40)是其结果未能涵盖的最小模数。我们在 Lean 4 中给出了定理 good_slopes_gap_mod_105 的机器验证证明,确立了 $\mathbb{Z}/105\mathbb{Z}$ 的每个非极值置换确实满足 $|D_{105}(f)| \le 40$。该证明结合了一个将好斜率嵌入到单位群 $(\mathbb{Z}/105\mathbb{Z})^\times$ 中的单位平移证书(good_slopes_unit_cover_mod105)与中国剩余定理(CRT)分解 $\mathbb{Z}/105\mathbb{Z} \cong \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$。双行纤维刚性定理(good_slopes_two_row_fiber_rigidity)表明,如果模 35 的两个单位纤维大小之和超过 40,则模 35 的每个单位斜率在两个纤维中都必须是单射的。这迫使平移后的好斜率集合成为阶为 48 的整个单位群,与非极值性矛盾。由于该论文表明对每个奇合数模数该界都是可达的,因此 40 是 $\mathbb{Z}/105\mathbb{Z}$ 的非极值置换的好斜率的最大数量。

1. 引言

论文 arXiv:2611.01465 与 arXiv:2611.04551 研究了剩余类环 $\mathbb{Z}/n\mathbb{Z}$ 的一个置换有多少个仿射扰动仍然是置换;前者的动机源于量子拉丁方(QLS)。

这一研究的核心是好斜率的概念。对于自然数 $n \ge 1$ 和 $\mathbb{Z}/n\mathbb{Z}$ 的置换 $f$,如果仿射扰动 $x \mapsto f(x) + mx$ 仍然是 $\mathbb{Z}/n\mathbb{Z}$ 的置换,则元素 $m \in \mathbb{Z}/n\mathbb{Z}$ 被称为 $f$ 的一个好斜率。$f$ 的所有好斜率构成的集合记为 $D_n(f)$。因为 $f$ 本身是一个置换,所以零始终是一个好斜率,因此 $D_n(f)$ 绝非空集。

$\mathbb{Z}/n\mathbb{Z}$ 的每个置换至多有 $\varphi(n)$ 个好斜率,其中 $\varphi$ 是欧拉函数(arXiv:2611.01465)。达到此界的置换被称为极值的;对于它们,$D_n(f)$ 是单位群的一个平移 $(\mathbb{Z}/n\mathbb{Z})^\times - a$。

一个自然且微妙的问题是理解在极值阈值 $\varphi(n)$ 之下 $|D_n(f)|$ 的分布。对于非极值置换,数量 $|D_n(f)|$ 是否会在 $\varphi(n)$ 之下发生不连续的跌落,还是可以取任意接近 $\varphi(n)?$ arXiv:2611.04551 中的问题 10.2 将此问题表述为一个精确的猜想间隙:

设 $n$ 为至少有两个不同素因子的奇合数,且设 $q$ 为其最大素因子。是否 $\mathbb{Z}/n\mathbb{Z}$ 的每个非极值置换 $f$ 都满足 $$|D_n(f)| \le \varphi(n)\frac{q-2}{q-1}?$$

该论文表明(其命题 9.6)该界无法改进:对于每个奇合数 $n$,都存在某个非极值置换恰好具有 $\varphi(n)\frac{q-2}{q-1}$ 个好斜率。在 Lean 中也验证了两个较小的实例。当 $n = 15 = 3 \times 5$ 时,最大素因子为 $q = 5$,且 $\varphi(15) = 8$。猜想的界为 $8 \times (5-2)/(5-1) = 8 \times (3/4) = 6$。结果 good_slopes_gap_tight_mod_15 证实了该界是可达的:存在 $\mathbb{Z}/15\mathbb{Z}$ 的非极值置换,恰好拥有 6 个好斜率。类似地,对于 $n = 45 = 3^2 \times 5$,最大素因子为 $q = 5$,$\varphi(45) = 24$,猜想的界为 $24 \times (3/4) = 18$。结果 good_slopes_gap_tight_mod_45 表明存在 $\mathbb{Z}/45\mathbb{Z}$ 的非极值置换,恰好具有 18 个好斜率,如该论文的例 9.17 所示。

该论文针对保同余置换、两个不同奇素数的乘积以及若干其他族(其中包括 $9q$ 和 $3q^e$)证明了该界;其表 3 列出了 175 以内尚未解决的模数,并指出未被涵盖的最小模数是 $n = 105$。根据其推论 9.5,在最小可能模数处的反例不会保持任何非平凡同余,因此该论文向更小模数的约化方法并不适用。整数 $105 = 3 \times 5 \times 7$ 是三个最小奇素数的乘积。其最大素因子为 $q = 7$,其欧拉函数值为 $$\varphi(105) = \varphi(3)\varphi(5)\varphi(7) = 2 \times 4 \times 6 = 48.$$ 对于 $n = 105$ 的猜想间隙界计算为 $$\varphi(105)\frac{q-2}{q-1} = 48 \times \frac{7-2}{7-1} = 48 \times \frac{5}{6} = 40.$$ 因此,问题 10.2 猜想 $\mathbb{Z}/105\mathbb{Z}$ 的任何置换的好斜率数量都不能严格介于 40 与 48 之间。证明这一点需要分析阶为 105 的环的完整置换空间,这远远超出了暴力枚举的范围,因为 $105! \approx 1.08 \times 10^{168}$。

在这篇博文中,我们报告在 Lean 4 中对此问题经机器验证的解决。我们讨论定理 good_slopes_gap_mod_105 的证明,该定理确立了 $\mathbb{Z}/105\mathbb{Z}$ 的每个非极值置换 $f$ 都满足 $|D_{105}(f)| \le 40$。该论证通过综合单位覆盖平移引理、中国剩余定理分解 $\mathbb{Z}/105\mathbb{Z} \cong \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$ 以及双行纤维刚性定理(good_slopes_two_row_fiber_rigidity),克服了模 105 计算上的不可行性。这一刚性定理迫使任何拥有超过 40 个好斜率的置换在平移后必须将全部 48 个单位都作为好斜率,从而使其成为极值的。结合该论文的命题 9.6,40 因而正是 $\mathbb{Z}/105\mathbb{Z}$ 的非极值置换的好斜率数量的精确最大值。

2. 预备知识

我们在模 $n$ 整数剩余类环的环境下工作,记为 $\mathbb{Z}/n\mathbb{Z}$,在 Lean 4 中由类型 ZMod n 表示。在全文中,$\mathbb{Z}/n\mathbb{Z}$ 的置换均由从 ZMod n 到其自身的双射映射表示。

定义 1(好斜率,good_slopes)。设 $n$ 为满足类型类约束 [NeZero n] 的正自然数。对于 $\mathbb{Z}/n\mathbb{Z}$ 的置换 $f$,$f$ 的好斜率集合记为 $D_n(f)$ 并在 Lean 中定义为 good_slopes n f,是由下式给出的 $\mathbb{Z}/n\mathbb{Z}$ 的有限子集: $$D_n(f) = \{m \in \mathbb{Z}/n\mathbb{Z} : x \mapsto f(x) + mx \text{ is bijective}\}.$$ 在 Lean 中,这形式化为: ``lean def good_slopes (n : ℕ) [NeZero n] (f : Equiv.Perm (ZMod n)) : Finset (ZMod n) := Finset.univ.filter (fun m => Function.Bijective (fun x => f x + m * x)) ` 注。该定义需要 [NeZero n],以便使 $\mathbb{Z}/n\mathbb{Z}$ 良定义。虽然对于有限类型到自身的任何映射,单射性、满射性与双射性在逻辑上都是等价的,但该定义明确指定了 Function.Bijective`。

定义 2(极值置换,is_extremal_perm)。设 $n$ 为带有 [NeZero n] 的自然数。如果 $\mathbb{Z}/n\mathbb{Z}$ 的置换 $f$ 的好斜率集合的基数达到了欧拉函数值 $\varphi(n)$,则称置换 $f$ 是极值的: $$|D_n(f)| = \varphi(n).$$ 在 Lean 中,此谓词定义为: ``lean def is_extremal_perm (n : ℕ) [NeZero n] (f : Equiv.Perm (ZMod n)) : Prop := (good_slopes n f).card = Nat.totient n ` 注。这里 $\varphi(n)$ 由 Nat.totient n 表示。对于 $n = 105$,Nat.totient 105` 计算为 48。

定义 3(模 105 的 CRT 坐标投影与分解)。由于 $\gcd(3, 35) = 1$ 且 $3 \times 35 = 105$,中国剩余定理诱导了 $\mathbb{Z}/105\mathbb{Z}$ 与 $\mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$ 之间的典范环同构。我们定义:

  • 典范投影 $\pi_3 : \mathbb{Z}/105\mathbb{Z} \to \mathbb{Z}/3\mathbb{Z}$,将 $x \pmod{105}$ 映射到 $x \pmod 3$。
  • 典范投影 $\pi_{35} : \mathbb{Z}/105\mathbb{Z} \to \mathbb{Z}/35\mathbb{Z}$,将 $x \pmod{105}$ 映射到 $x \pmod{35}$。
  • 坐标分解双射 $\sigma : \mathbb{Z}/105\mathbb{Z} \to \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$,定义为 $x \mapsto (\pi_3(x), \pi_{35}(x))$。
  • 中国剩余重构映射 $\sigma^{-1} : \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z} \to \mathbb{Z}/105\mathbb{Z}$。

注。该形式化将素因子 5 和 7 组合为一个复合因子 35,将 $\mathbb{Z}/105\mathbb{Z}$ 视为 $\mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$ 而非三元乘积 $\mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/5\mathbb{Z} \times \mathbb{Z}/7\mathbb{Z}$。这一结构选择至关重要:$\mathbb{Z}/3\mathbb{Z}$ 的单位群仅包含两个元素,即 $1$ 和 $2$,从而允许将乘积环中的单位斜率精确地划分为由 $a \in \{1, 2\}$ 参数化的两个纤维(或行)。

定义 4(模 35 的单位方向纤维)。设 $g : \mathbb{Z}/105\mathbb{Z} \to \mathbb{Z}/105\mathbb{Z}$ 为一个函数。对于每个第一坐标斜率 $a \in \mathbb{Z}/3\mathbb{Z}$,模 35 第二坐标的好单位斜率纤维是集合 $$R(a) = \left\{b \in (\mathbb{Z}/35\mathbb{Z})^\times : x \mapsto (\pi_3(g(x)) + a \pi_3(x), \pi_{35}(g(x)) + b \pi_{35}(x)) \text{ is injective}\right\}.$$

注。由于 $\mathbb{Z}/105\mathbb{Z}$ 是基数为 105 的有限集,该映射到 $\mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$(其基数同样为 $3 \times 35 = 105$)的单射性等价于双射性。单位集 $(\mathbb{Z}/35\mathbb{Z})^\times$ 的基数为 $\varphi(35) = \varphi(5)\varphi(7) = 4 \times 6 = 24$,因此每个纤维 $R(a)$ 都满足 $R(a) \subseteq (\mathbb{Z}/35\mathbb{Z})^\times$ 且 $|R(a)| \le 24$。

3. 主要结果

定理(good_slopes_gap_mod_105)。设 $f$ 为剩余类环 $\mathbb{Z}/105\mathbb{Z}$ 的置换。如果 $f$ 不是极值的,即其好斜率数量满足 $|D_{105}(f)| \neq \varphi(105) = 48$,则 $$|D_{105}(f)| \le 40.$$

该网站在此节下展示了主定理的 Lean 形式化表述: ``lean theorem good_slopes_gap_mod_105 (f : Equiv.Perm (ZMod 105)) (hf : ¬ is_extremal_perm 105 f) : (good_slopes 105 f).card ≤ 40 ` Lean 定理 good_slopes_gap_mod_105 以一个置换 f : Equiv.Perm (ZMod 105) 和一个假设 hf : ¬ is_extremal_perm 105 f 作为前提条件,并得出结论 (good_slopes 105 f).card ≤ 40`,断言 $f$ 的好斜率有限集的基数至多为 40。

每个进一步结果的补充: 这些材料包含了补充 good_slopes_gap_mod_105 的若干支持性与背景性定理:

- 模 15 的紧性(good_slopes_gap_tight_mod_15):证明了间隙界 $\varphi(n)\frac{q-2}{q-1}$ 对 $n = 15$($q = 5$)是紧的,构造出了一个恰好具有 6 个好斜率的 $\mathbb{Z}/15\mathbb{Z}$ 显式非极值置换,与 $\varphi(15) \times (3/4) = 6$ 吻合。

- 模 45 的紧性(good_slopes_gap_tight_mod_45):证明了包含素数平方的合数模数 $n = 45 = 3^2 \times 5$($q = 5$)的紧性,构造出了一个恰好具有 18 个好斜率的 $\mathbb{Z}/45\mathbb{Z}$ 非极值置换,与 $\varphi(45) \times (3/4) = 18$ 吻合。

- 35 点上的单位间隙(good_slopes_fiber35_unit_gap):证明了对于 $\mathbb{Z}/35\mathbb{Z}$ 上的任意 35 个点的构型,如果 24 个单位方向中至少有一个不是单射的,则至多有 20 个单位方向可以是单射的,从而确立了至少 4 个方向的局部跌落。

- 35 点上的着色单位间隙(good_slopes_fiber35_colored_gap):表明如果将 $\mathbb{Z}/35\mathbb{Z}$ 中的 35 个点划分为三个颜色类,使得每个颜色类在所有单位方向形式 $y + ax$ 下都是单射的,则要么每个单位方向都是全局单射的,要么至多有 16 个单位方向是全局单射的。

- 双行纤维刚性(good_slopes_two_row_fiber_rigidity):good_slopes_gap_mod_105 背后的关键驱动,指出在一个包含 $105 = 3 \times 35$ 个点的集合上,如果两行($\mathbb{Z}/3\mathbb{Z}$ 中的两个斜率)中好单位方向的数量相加超过 40,则两行中的每个单位方向都是单射的。

定理 good_slopes_gap_mod_105 (Lean 4 已验证)
theorem good_slopes_gap_mod_105 (f : Equiv.Perm (ZMod 105)) (hf : ¬ is_extremal_perm 105 f) : (good_slopes 105 f).card ≤ 40

4. 证明

证明思路: 证明采用反证法。我们假设 $f$ 是 $\mathbb{Z}/105\mathbb{Z}$ 的非极值置换且 $|D_{105}(f)| > 40$。 首先,利用 good_slopes_unit_cover_mod105,我们找到一个单位 $c \in (\mathbb{Z}/105\mathbb{Z})^\times$,使得将每个好斜率 $m \in D_{105}(f)$ 平移 $c$ 后都产生一个单位 $m + c \in (\mathbb{Z}/105\mathbb{Z})^\times$。 然后我们通过减去线性项 $cx$ 来对 $f$ 进行归一化,令 $f_{\text{norm}}(x) = f(x) - cx$。平移后的斜率集合 $A = \{m + c : m \in D_{105}(f)\}$ 完全由 $\mathbb{Z}/105\mathbb{Z}$ 中的单位构成,大小为 $|A| = |D_{105}(f)| > 40$,并满足性质:$u \in A$ 当且仅当 $x \mapsto f_{\text{norm}}(x) + ux$ 是双射。

接下来,我们通过中国剩余定理同构 $\sigma$ 将 $\mathbb{Z}/105\mathbb{Z}$ 分解为 $\mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$。因为每个 $u \in A$ 都是 $\mathbb{Z}/105\mathbb{Z}$ 中的单位,所以其投影 $a = \pi_3(u)$ 是 $\mathbb{Z}/3\mathbb{Z}$ 中的单位,且其投影 $b = \pi_{35}(u)$ 是 $\mathbb{Z}/35\mathbb{Z}$ 中的单位。环 $\mathbb{Z}/3\mathbb{Z}$ 仅有两个单位:$1$ 和 $2$。这把 $A$ 在 $\sigma$ 下的像划分为两个不相交的纤维 $(\{1\} \times R(1)) \cup (\{2\} \times R(2))$,其中 $R(a)$ 由那些使得映射 $x \mapsto (\pi_3(f_{\text{norm}}(x)) + a \pi_3(x), \pi_{35}(f_{\text{norm}}(x)) + b \pi_{35}(x))$ 为单射的单位斜率 $b \in (\mathbb{Z}/35\mathbb{Z})^\times$ 构成。

基数恒等式 $|A| = |R(1)| + |R(2)|$ 蕴含 $|R(1)| + |R(2)| > 40$。然后我们对 $a = 1$ 和 $a' = 2$ 调用双行纤维刚性定理 good_slopes_two_row_fiber_rigidity。由于跨越两行的好单位对的总数超过 40,刚性定理迫使两个纤维都是完全满的:每个单位 $b \in (\mathbb{Z}/35\mathbb{Z})^\times$ 都同时属于 $R(1)$ 和 $R(2)$。通过 CRT 重新组合表明,每个单位 $u \in (\mathbb{Z}/105\mathbb{Z})^\times$ 都属于 $A$。因此,$A$ 是整个单位群 $(\mathbb{Z}/105\mathbb{Z})^\times$,其基数为 $\varphi(105) = 48$。这给出了 $|D_{105}(f)| = 48 = \varphi(105)$,表明 $f$ 是极值的,并得出了所需的矛盾。

现在我们陈述形式化中所使用的关键引理:

引理 1(good_slopes_unit_cover_mod105)。 对于 $\mathbb{Z}/105\mathbb{Z}$ 的每个置换 $f$,存在一个单位 $c \in (\mathbb{Z}/105\mathbb{Z})^\times$,使得对所有 $m \in \text{good\_slopes } 105\ f$,和 $m + c$ 都是 $\mathbb{Z}/105\mathbb{Z}$ 中的单位: $$\exists c \in (\mathbb{Z}/105\mathbb{Z})^\times, \quad \forall m \in D_{105}(f), \quad m + c \in (\mathbb{Z}/105\mathbb{Z})^\times.$$ 证明。对于每个素数 $p \in \{3, 5, 7\}$,模 $p$ 的某个剩余类 $a_p$ 不被任何好斜率达到。由于 $0$ 是好斜率,所以 $a_p \neq 0$。根据中国剩余定理选取 $c$,使得对每个 $p$ 都有 $c \equiv -a_p \pmod p$;则 $c$ 是单位,并且对于每个好斜率 $m$,对所有这三个素数都有 $m + c \not\equiv 0 \pmod p$,因此 $m + c$ 是单位。

引理 2(CRT 双射性与单位分解)。 设 $g : \mathbb{Z}/105\mathbb{Z} \to \mathbb{Z}/105\mathbb{Z}$ 且 $u \in \mathbb{Z}/105\mathbb{Z}$。 1. 映射 $x \mapsto g(x) + ux$ 在 $\mathbb{Z}/105\mathbb{Z}$ 上是双射,当且仅当坐标映射 $$x \mapsto (\pi_3(g(x)) + \pi_3(u)\pi_3(x), \, \pi_{35}(g(x)) + \pi_{35}(u)\pi_{35}(x))$$ 在 $\mathbb{Z}/105\mathbb{Z}$ 上是双射(或等价地,单射)。 2. 坐标分解映射 $\sigma : x \mapsto (\pi_3(x), \pi_{35}(x))$ 是 $\mathbb{Z}/105\mathbb{Z}$ 与 $\mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$ 之间的双射,其逆由中国剩余重构给出。 3. 元素 $a \in \mathbb{Z}/3\mathbb{Z}$ 是单位,当且仅当 $a = 1$ 或 $a = 2$。 4. 元素 $u \in \mathbb{Z}/105\mathbb{Z}$ 是单位,当且仅当 $\pi_3(u)$ 是 $\mathbb{Z}/3\mathbb{Z}$ 中的单位且 $\pi_{35}(u)$ 是 $\mathbb{Z}/35\mathbb{Z}$ 中的单位。 证明。第 1 部分成立是因为 $\pi_3$ 和 $\pi_{35}$ 是环同态且 $\sigma$ 是单射;第 2 部分是中国剩余定理;第 3 和第 4 部分是有限检验。

引理 3(good_slopes_two_row_fiber_rigidity)。 设 $X$ 为基数为 $|X| = 3 \times 35 = 105$ 的有限类型。设 $x_3, y_3 : X \to \mathbb{Z}/3\mathbb{Z}$ 与 $x_{35}, y_{35} : X \to \mathbb{Z}/35\mathbb{Z}$ 为函数,使得输入对 $x \mapsto (x_3(x), x_{35}(x))$ 是单射。设 $a, a' \in \mathbb{Z}/3\mathbb{Z}$ 为两个斜率。对任意斜率 $s \in \mathbb{Z}/3\mathbb{Z}$,定义 $\mathbb{Z}/35\mathbb{Z}$ 中的好单位斜率集合: $$R(s) = \{b \in (\mathbb{Z}/35\mathbb{Z})^\times : x \mapsto (y_3(x) + s \cdot x_3(x), y_{35}(x) + b \cdot x_{35}(x)) \text{ is injective}\}.$$ 如果 $|R(a)| + |R(a')| > 40$,则每个单位 $b \in (\mathbb{Z}/35\mathbb{Z})^\times$ 都满足 $b \in R(a)$ 且 $b \in R(a')$。也就是说,两个纤维都是完全满的:$|R(a)| = 24$ 且 $|R(a')| = 24$。 证明。每个纤维至多有 24 个元素,因此两者均非空,并且每个行 $s \in \{a, a'\}$ 都有一个锚斜率 $b_0$ 使得该映射为单射,从而为双射。固定带有锚斜率的行 $s$。对于 $t \in \mathbb{Z}/3\mathbb{Z}$,满足 $y_3(x) + s\,x_3(x) = t$ 的点 $x$ 给出了 $\mathbb{Z}/35\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$ 中恰好 35 个对 $(x_{35}(x), y_{35}(x))$ 构成的集合 $S_t$,且斜率 $b$ 在行 $s$ 中是好的当且仅当 $y + bx$ 在 $S_0, S_1, S_2$ 的每一个上都是单射。假设某个单位 $b$ 在行 $a$ 中是坏的。那么它在集合 $S_t$ 之一上是坏的,由 good_slopes_fiber35_unit_gap 可知该集合至多有 20 个单射单位方向,因此 $|R(a)| \le 20$。若行 $a'$ 有坏单位,同理可得结论,此时 $|R(a)| + |R(a')| \le 40$;所以行 $a'$ 中的每个单位都是好的。现在根据行 $a$ 的坏集合 $S_t$ 中每个点所来自的点的 $x_3$ 值对其进行着色。同一种颜色的两个点具有相同的 $x_3$,且因落在同一条直线 $y_3 + a x_3 = t$ 上,也具有相同的 $y_3$;由于行 $a'$ 中的每个单位都是好的,对于单位 $b$,每个形式 $y + bx$ 在单一颜色内部都是单射的,并且由于 $(x_3, x_{35})$ 是单射,第一坐标在单一颜色内部也是单射的。因此 good_slopes_fiber35_colored_gap 适用,并将 $S_t$ 上的单射单位方向数量(从而 $|R(a)|$)限制在至多 16 个。于是 $|R(a)| + |R(a')| \le 16 + 24 = 40$,矛盾。由对称性,对行 $a'$ 同样成立。这两个 35 点引理承担了组合论证的核心:good_slopes_fiber35_unit_gap 表明 $\mathbb{Z}/35\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$ 中任何具有非单射单位方向的 35 个点至少有四个这样的方向,而 good_slopes_fiber35_colored_gap 在着色假设下将这一数量提高到了八个。

good_slopes_gap_mod_105 的详细证明: 我们现在逐步跟随 good_slopes_gap_mod_105 的 Lean 证明。

1. 反证假设:反设 good_slopes 105 $f$ 的基数严格大于 40。

2. 通过单位覆盖平移:由引理 1(good_slopes_unit_cover_mod105),存在一个单位 $c \in (\mathbb{Z}/105\mathbb{Z})^\times$,使得对所有 $m \in D_{105}(f)$,$m + c$ 都是 $\mathbb{Z}/105\mathbb{Z}$ 中的单位。 我们通过 $x \mapsto f(x) - cx$ 定义归一化映射 $f_{\text{norm}} : \mathbb{Z}/105\mathbb{Z} \to \mathbb{Z}/105\mathbb{Z}$。 我们定义平移后的斜率集合: $$A = \{m + c : m \in D_{105}(f)\} \subseteq \mathbb{Z}/105\mathbb{Z}.$$ 对于任意 $u \in \mathbb{Z}/105\mathbb{Z}$,该证明表明: $$u \in A \iff x \mapsto f_{\text{norm}}(x) + ux \text{ is bijective}.$$ 为了证明正向蕴含,设 $u = m + c$,其中 $m \in D_{105}(f)$。则 $$f_{\text{norm}}(x) + ux = (f(x) - cx) + (m + c)x = f(x) + mx,$$ 由于 $m \in D_{105}(f)$,该式是双射。反向蕴含通过取 $m = u - c$ 对称地得出。 $A$ 的每个元素 $u$ 都是单位,因为对于某个 $m \in D_{105}(f)$ 有 $u = m + c$,且 $c$ 的选取满足单位覆盖性质。 由于加上 $c$ 是单射映射,基数得以保持: $$|A| = |D_{105}(f)| > 40.$$

3. 分解为模 3 和 35 的对:设 $P \subseteq \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$ 为 $A$ 在 CRT 分解映射 $\sigma$ 下的像。因为 $\sigma$ 是单射,所以 $|P| = |A|$。 对于任意 $a \in \mathbb{Z}/3\mathbb{Z}$ 和 $b \in \mathbb{Z}/35\mathbb{Z}$,对 $(a, b)$ 属于 $P$ 当且仅当 $(a, b)$ 的中国剩余重构属于 $A$。 结合 $A$ 的所有元素都是单位这一事实并应用引理 2,我们获得等价性: $(a, b) \in P$ 当且仅当 $a$ 是 $\mathbb{Z}/3\mathbb{Z}$ 中的单位,$b$ 是 $\mathbb{Z}/35\mathbb{Z}$ 中的单位,且映射 $$x \mapsto (\pi_3(f_{\text{norm}}(x)) + a \pi_3(x), \, \pi_{35}(f_{\text{norm}}(x)) + b \pi_{35}(x))$$ 在 $\mathbb{Z}/105\mathbb{Z}$ 上是单射。

4. 分解为两行:定义 $R : \mathbb{Z}/3\mathbb{Z} \to \text{Finset } (\mathbb{Z}/35\mathbb{Z})$ 为 $$R(a) = \{b \in (\mathbb{Z}/35\mathbb{Z})^\times : x \mapsto (\pi_3(f_{\text{norm}}(x)) + a \pi_3(x), \, \pi_{35}(f_{\text{norm}}(x)) + b \pi_{35}(x)) \text{ is injective}\}.$$ 由引理 2,$\mathbb{Z}/3\mathbb{Z}$ 的单位恰好是 $1$ 和 $2$。因此,$P$ 分解为: $$P = (\{1\} \times R(1)) \cup (\{2\} \times R(2)).$$ 因为在 $\mathbb{Z}/3\mathbb{Z}$ 中 $1 \neq 2$,所以集合 $\{1\} \times R(1)$ 与 $\{2\} \times R(2)$ 不相交。 取基数可得: $$|P| = |R(1)| + |R(2)|.$$ 结合 $|P| = |A| = |D_{105}(f)|$,我们有: $$|R(1)| + |R(2)| = |D_{105}(f)| > 40.$$

5. 应用纤维刚性:我们对以下对象应用引理 3(good_slopes_two_row_fiber_rigidity): - 有限类型 $X = \mathbb{Z}/105\mathbb{Z}$,满足 $|X| = 105 = 3 \times 35$。 - 输入坐标函数 $x_3 = \pi_3$ 和 $x_{35} = \pi_{35}$。对 $(x_3, x_{35}) = \sigma$ 是单射。 - 输出坐标函数 $y_3(x) = \pi_3(f_{\text{norm}}(x))$ 和 $y_{35}(x) = \pi_{35}(f_{\text{norm}}(x))$。 - $\mathbb{Z}/3\mathbb{Z}$ 中的行斜率 $a = 1$ 和 $a' = 2$。 - 假设条件 $|R(1)| + |R(2)| > 40$。 该定理输出: $$\forall b \in (\mathbb{Z}/35\mathbb{Z})^\times, \quad b \in R(1) \quad \text{and} \quad b \in R(2).$$

6. 导出极值性与矛盾:设 $u \in \mathbb{Z}/105\mathbb{Z}$ 为任意单位。则 $a = \pi_3(u)$ 是 $\mathbb{Z}/3\mathbb{Z}$ 中的单位,因此 $a \in \{1, 2\}$,且 $b = \pi_{35}(u)$ 是 $\mathbb{Z}/35\mathbb{Z}$ 中的单位。 由刚性结论,$b \in R(a)$。由 $R(a)$ 的定义,映射 $$x \mapsto (\pi_3(f_{\text{norm}}(x)) + a \pi_3(x), \, \pi_{35}(f_{\text{norm}}(x)) + b \pi_{35}(x))$$ 是单射。因为 $\mathbb{Z}/105\mathbb{Z}$ 是有限的,所以该映射也是双射。 应用引理 2,该双射性等价于 $x \mapsto f_{\text{norm}}(x) + ux$ 的双射性。 这蕴含 $u \in A$。 这对每个单位 $u$ 都成立,因此 $A$ 包含 $\mathbb{Z}/105\mathbb{Z}$ 的每个单位。 结合 $A$ 的每个元素都是单位这一事实,我们得到 $A = U$,其中 $U = (\mathbb{Z}/105\mathbb{Z})^\times$。 $\mathbb{Z}/105\mathbb{Z}$ 的单位群基数为: $$|U| = \varphi(105) = 48.$$ 因此 $|D_{105}(f)| = |A| = |U| = 48 = \varphi(105)$。 由定义 2,这意味着 $f$ 满足 is_extremal_perm 105 f。 这直接与 $f$ 不是极值的假设相矛盾。 该矛盾确立了 good_slopes 105 $f$ 的基数至多为 40,从而完成了 good_slopes_gap_mod_105 的证明。

5. 讨论

good_slopes_gap_mod_105 的证明解决了 arXiv:2611.04551 中问题 10.2 针对该论文结果未涵盖的最小模数(即 $n = 105$)的间隙猜想。模 105 代表了与早期所研究情形相比的质的转变:它是三个不同奇素数的乘积($3 \times 5 \times 7$)的最小模数,而不是两个不同素数(例如 $15 = 3 \times 5$ 或 $21 = 3 \times 7$)或素数幂乘以素数($45 = 3^2 \times 5$)。

虽然该结果确立了 $\mathbb{Z}/105\mathbb{Z}$ 的所有非极值置换的上界 $|D_{105}(f)| \le 40$,但仍有若干未决问题:

- 精确值:根据 arXiv:2611.04551 的命题 9.6,$\mathbb{Z}/105\mathbb{Z}$ 的某个非仿射置换恰好具有 40 个好斜率,因此结合 good_slopes_gap_mod_105,$\mathbb{Z}/105\mathbb{Z}$ 的非极值置换的好斜率最大数量恰好是 40,且没有任何置换的好斜率数量介于 41 与 47 之间。Lean 资料中不包含针对 $n = 105$ 的此构造。

- 一般奇合数模数:arXiv:2611.04551 的问题 10.2 询问,界 $|D_n(f)| \le \varphi(n)\frac{q-2}{q-1}$ 是否对每个至少有两个不同素因子的奇合数 $n$ 都成立,其中 $q$ 是 $n$ 的最大素因子。定理 good_slopes_gap_mod_105 仅解决了具体实例 $n = 105$ 的这一问题。该论文表 3 中未解决的其他项仍然悬而未决:$n = 135 = 3^3 \times 5$(界为 54)、$n = 165 = 3 \times 5 \times 11$(界为 72)以及 $n = 175 = 5^2 \times 7$(界为 100)。这里的论证使用了分解 $\mathbb{Z}/105\mathbb{Z} \cong \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$(其中因子 3 仅有两个单位)以及两个有限的 35 点引理;对于 $165 = 3 \times 55$,相同的方案将需要 55 点上的类似引理。

- 推广纤维刚性:这里给出的证明严重依赖于将素因子组合为 $3$ 与 $35 = 5 \times 7$。这种分解产生了由 $\mathbb{Z}/3\mathbb{Z}$ 的单位 $1$ 和 $2$ 索引的恰好两个单位纤维。对于最小素因子更大的模数(例如 $n = 35 = 5 \times 7$,其中因子为 $5$ 和 $7$;或者 $n = 5 \times 7 \times 11 = 385$),分离出最小素数会产生 $\varphi(p) = p - 1 \ge 4$ 个纤维而不是 2 个。为 $\varphi(p) > 2$ 建立多行纤维刚性原理是将这些结果推广到一般奇合数模数的重要途径。

为什么是研究级成果

  • Proves the conjectured gap bound for modulus 105, the smallest case left unsettled by arXiv:2611.04551, using a checked CRT fiber reduction and finite-direction certificates

Lean 声明

  • good_slopes_gap_mod_105Every non-extremal permutation f of ℤ/105ℤ satisfies |D_{105}(f)| ≤ 40: (good_slopes 105 f).card ≤ 40.
  • good_slopes_unit_cover_mod105For every permutation modulo 105, a unit c exists such that adding c to each good slope yields a unit modulo 105.
  • good_slopes_two_row_fiber_rigidityLet X be a finite set of 105 elements with input and output coordinate functions over Z/3 and Z/35, and assume the pair of input…
  • good_slopes_gap_tight_mod_15There exists a non-extremal permutation f of ℤ/15ℤ with exactly 6 good slopes, demonstrating that the gap bound φ(15)(q - 2)/(q - 1) = 6…
  • good_slopes_gap_tight_mod_45There exists a non-extremal permutation f of ℤ/45ℤ with exactly 18 good slopes, demonstrating that the gap bound φ(45)(q - 2)/(q - 1) = 18…
  • good_slopesGiven a natural number n with n ≠ 0 (via [NeZero n]) and a permutation f of ℤ/nℤ, good_slopes n f is the finite set (Finset) of elements m…
  • is_extremal_permGiven n with [NeZero n], a permutation f of ℤ/nℤ is extremal if the number of its good slopes (the cardinality of good_slopes n f) equals…
  • good_slopes_fiber35_unit_gapFor any 35 points over the residues modulo 35, if at least one unit direction fails to be injective, then at most 20 of the 24 unit…
  • good_slopes_fiber35_colored_gapLet S be a set of 35 points over the residues modulo 35, colored with three colors. Suppose that within each color both the first…

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

参考文献

  1. arXiv:2611.04551 — Good slopes, congruence preservation, and gaps over residue rings
  2. arXiv:2611.01465 — Extremal permutations of $\mathbb{Z}_n$ with many good slopes and applications to quantum Latin squares

由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。