AFTD Auto-Formalizing Theoretical Domains

Research Blogs

每个双三尾拉丁杨表的四种扩展

medium tier2026-10-26OP-512审阅: codexEnglish

摘要

arXiv:2610.29291 中的猜想 6.3 询问对于每一个整数 $k \ge 5$,形状为 $\lambda = (k, k-1, \dots, 4, 3, 3)$ 且共轭型为 $\lambda'$ 的拉丁杨表(Latin tableau)的数量是否由 $9 \cdot 4^{k-3}$ 给出。arXiv:2610.29291 中早期的研究在引理 5.4 中建立了将杨表计数与矩阵积和式(permanent)联系起来的基线可用性-积和式恒等式,并在命题 5.5 中展示了顶行单调性,但对单个可用性积和式的求值仍未解决。本文给出了一个形式化证明,表明每一个形状为 $(k, k-1, \dots, 4, 3, 3)$ 的拉丁杨表在添加长度为 $k+1$ 的新顶行时恰好允许四种有效扩展。该证明通过将杨表的列-符号构型分类为典则列剖面(canonical column profile)来展开。结果表明,该族中的每一个杨表都满足典则剖面,并且任何满足该剖面的填法都会产生一个积和式等于 4 的 $(k+1) \times (k+1)$ 二值可用性矩阵。这在整个无限族中确立了均匀的逐点分支因子 4。主要结果及其支持性的结构和组合引理已在 Lean 4 中形式化并经过机械验证。

1. 引言

杨图形状为 $\mu$ 且共轭型为 $\mu'$ 的拉丁杨表是将正整数分配给 $\mu$ 的单元格,使得第 $i$ 行中的每个条目都以上界行长 $\mu.\text{rowLen } i$ 为限,并且同一行或同一列中没有两个单元格包含相同条目。如 arXiv:2610.29291 中所阐述的,拉丁杨表的枚举和结构分类是杨表组合学研究中的核心问题。在 arXiv:2610.29291 考虑的具体形状中,一个突出的未决问题是猜想 6.3,该猜想涉及具有双三尾的阶梯族。对于整数 $k \ge 5$,设 $\lambda = (k, k-1, \dots, 4, 3, 3)$ 为行长从 $k$ 递减 1 直至 3、且末端长度 3 重复两次的分拆。猜想 6.3 询问形状为 $\lambda$ 且类型为 $\lambda'$ 的拉丁杨表总数 $LT(\lambda)$ 是否由闭式解 $9 \cdot 4^{k-3}$ 给出。

arXiv:2610.29291 建立的框架通过连续行的构造来处理杨表枚举。当向现有的形状为 $\mu$ 的拉丁杨表前面添加长度为 $w$ 的新行时,新行中的每个单元格都必须填入有效符号,使得生成的杨表继续满足行相异性和列相异性。在 arXiv:2610.29291 中,该扩展过程通过 0-1 可用性矩阵形式化。arXiv:2610.29291 的引理 5.4 提供了基线可用性-积和式恒等式,证明了在杨表 $T$ 前面添加长度为 $w$ 的行时的有效方式数等于对应的 $w \times w$ 可用性矩阵的积和式。此外,arXiv:2610.29291 的命题 5.5 证明了行扩展下的顶行单调性。

尽管有这些通用的结构工具,猜想 6.3 中的枚举仍然悬而未决,因为文献中仅将 $LT(\lambda)$ 表示为较小形状的拉丁杨表上未知积和式的和。单个可用性积和式的行为尚不为人所知:原则上,扩展数量在相同形状的不同杨表之间可能会有很大差异,平均为 4 的整数倍,或者它可能表现出对特定填法的非平凡依赖。

本文给出了局部扩展行为的一个经验证的解答:对于任何 $k \ge 5$,形状为 $(k, k-1, \dots, 4, 3, 3)$ 的每个拉丁杨表都允许通过长度为 $k+1$ 的额外顶行进行恰好 4 次扩展。也就是说,我们不仅界定总和或证明单调性,而且将每个单独的可用性积和式精确求值为 4。这种逐点的四扩展细化确立了猜想公式 $9 \cdot 4^{k-3}$ 中的因子 4 源自该族中每个杨表处存在的精确 4 比 1 分支比。

该证明基于对该族拉丁杨表的列-符号分布的结构分类。我们表明,每个有效杨表都具有由双三尾所强迫的典则列剖面之一。对于满足这些剖面的任何填法,预期的顶行符号与列之间的二分兼容图恰好具有四个完美匹配。整个过程已在 Lean 4 中通过定理 latin_double_three_tail_four_extensions 完成形式化,并对照 Lean 数学库进行了验证。

2. 预备知识

我们建立整个开发过程中使用的形式化定义和约定,与它们在 Lean 4 中的实现相匹配。

定义 1(latin_double_three_tail_shape)。对于整数 $k \ge 5$,双三尾阶梯形状是具有 $k-1$ 行的杨图 $\lambda$,其行长由 $(k, k-1, \dots, 4, 3, 3)$ 给出。在 Lean 中,图使用基于 0 的坐标进行索引,因此对于 $0 \le i < k-1$,第 $i$ 行的长度由 $\max(3, k-i)$ 定义,并且对于 $i \ge k-1$ 图为空。图的单元格集合是坐标对 $(i, j) \in \mathbb{N} \times \mathbb{N}$ 的集合,满足 $0 \le i < k-1$ 且 $0 \le j < \max(3, k-i)$。

注 1。在此定义中,索引 $i$ 的范围是从 $0$ 到 $k-2$,正好产生 $k-1$ 行。第 $0, 1, \dots, k-4$ 行的长度严格递减为 $k, k-1, \dots, 4$,而第 $k-3$ 行的长度为 $\max(3, 3) = 3$,第 $k-2$ 行的长度为 $\max(3, 2) = 3$。第 $0, 1, 2$ 列各包含 $k-1$ 个单元格,而对于 $3 \le j < k$,第 $j$ 列包含 $k-j$ 个单元格。

定义 2(latin_tableaux)。设 $\mu$ 为杨图。$\mu$ 的填法是一个函数 $T : \mu.\text{cells} \to \mathbb{N}$。形状为 $\mu$ 且类型为 $\mu'$ 的拉丁杨表的有限集(finset),记为 latin_tableaux μ,是满足以下条件的填法 $T$ 的集合:

  1. 对于每个单元格 $c = (i, j) \in \mu.\text{cells}$,条目 $T(c)$ 满足 $1 \le T(c) \le \mu.\text{rowLen } i$;
  2. 条目沿每行严格相异:对于任意两个单元格 $c_1, c_2 \in \mu.\text{cells}$,若 $c_1.1 = c_2.1$ 且 $T(c_1) = T(c_2)$,则 $c_1.2 = c_2.2$;
  3. 条目沿每列严格相异:对于任意两个单元格 $c_1, c_2 \in \mu.\text{cells}$,若 $c_1.2 = c_2.2$ 且 $T(c_1) = T(c_2)$,则 $c_1.1 = c_2.1$。

注 2。在 Lean 中,行长界限是通过从离散区间 $[1, \mu.\text{rowLen } i]$ 中提取每个单元格的值来强制实施的。这确保了出现在第 $i$ 行中的符号受到该行长度的严格限制,这对应于共轭型为 $\mu'$ 的拉丁杨表的标准定义。

定义 3(latin_top_row_availability)。给定一个杨图 $d$、一个填法 $T : d.\text{cells} \to \mathbb{N}$ 和一个预期的行宽 $w \in \mathbb{N}$,顶行可用性矩阵 latin_top_row_availability d T w 是 $\mathbb{N}$ 上的 $w \times w$ 矩阵 $A$,对于行索引 $i \in \{0, \dots, w-1\}$ 和列索引 $j \in \{0, \dots, w-1\}$ 定义为: $$A_{i, j} = \begin{cases} 1 & \text{if } \forall c \in d.\text{cells},\ c.2 = j \implies T(c) \neq i + 1, \\ 0 & \text{otherwise.} \end{cases}$$

注 3。行索引 $i$ 对应于候选符号 $i+1 \in \{1, \dots, w\}$,而列索引 $j$ 对应于候选新顶行中的列坐标。条目 $A_{i, j}$ 为 1 当且仅当符号 $i+1$ 没有出现在现有杨表 $T$ 的第 $j$ 列中的任何位置。如果列 $j$ 超出图 $d$ 的宽度(即 $d$ 中没有单元格具有列索引 $j$),则该条件平凡满足,并且对于所有 $i$ 都有 $A_{i, j} = 1$。

定义 4(矩阵积和式与典则列剖面)。对于条目在 $\mathbb{N}$ 中的 $n \times n$ 矩阵 $M$,其积和式定义为: $$\operatorname{perm}(M) = \sum_{\sigma \in S_n} \prod_{j=0}^{n-1} M_{\sigma(j), j},$$ 其中 $S_n$ 是 $\{0, \dots, n-1\}$ 上的对称群。当应用于 $A = \text{`latin_top_row_availability`} d\ T\ w$ 时,每个满足 $\prod_{j=0}^{w-1} A_{\sigma(j), j} = 1$ 的置换 $\sigma \in S_n$ 都表示一个双射 $j \mapsto \sigma(j)+1$,将符号 $\sigma(j)+1$ 放置在新顶行的单元格 $(0, j)$ 中,而不违反行或列的相异性。

典则列剖面记录了每一列中的符号集。它具有参数 $c\in\{0,1,2\}$ 和 $s\in\{1,2,3\}$:$c$ 标明例外的第一列,而 $s$ 是最后一个被占用的列中的符号。存在九个参数对,或者在允许前三列置换后有三个剖面。确切的列集合出现在下面的证明中。

3. 主要结果

这一主要的研究级结果确立了:属于双三尾阶梯族的每一个拉丁杨表在前面添加长度为 $k+1$ 的额外顶行时,其可用性积和式恰好为 4。

定理(latin_double_three_tail_four_extensions)。对于每一个整数 $k \ge 5$ 和每一个拉丁杨表 $T \in \text{`latin_tableaux`}(\text{`latin_double_three_tail_shape`} k)$,$(k+1) \times (k+1)$ 顶行可用性矩阵的积和式满足: $$\operatorname{perm}\bigl(\text{`latin_top_row_availability`}(\text{`latin_double_three_tail_shape`} k, T, k+1)\bigr) = 4.$$

Lean 语句 theorem latin_double_three_tail_four_extensions (k : ℕ) (hk : 5 ≤ k) : ∀ T ∈ latin_tableaux (latin_double_three_tail_shape k), Matrix.permanent (latin_top_row_availability (latin_double_three_tail_shape k) T (k+1)) = 4 声明了一个满足不等式 $5 \le k$ 的自然数 $k$,对属于有限集 latin_tableaux (latin_double_three_tail_shape k) 的所有单元格填法 $T$ 进行全称量化,并断言 $(k+1) \times (k+1)$ 矩阵 latin_top_row_availability (latin_double_three_tail_shape k) T (k+1) 的积和式等于 4。

该定理将 arXiv:2610.29291 中猜想 6.3 的总体计数问题细化为在每一个杨表处均成立的精确逐点性质。两个模块化引理确立了这一结果,每一个都为该族的结构理解增添了必不可少的组成部分:

第一个支持性结果是 latin_double_three_tail_profile_all,它对整个族的列构型进行了分类。它断言形状为 latin_double_three_tail_shape k 的每个拉丁杨表 $T$ 都满足典则列剖面。该结果消除了对特异杨表填法的任何依赖,表明行长界限和拉丁性的全局约束强迫所有杨表进入一小套典则列剖面中。

第二个支持性结果是 latin_double_three_tail_permanent_of_profile,它证明了满足典则列剖面的任何填法 $T$ 都会产生一个积和式恒等于 4 的可用性矩阵。这将积和式计算从在 $(k+1)!$ 个置换上的棘手组合搜索减少为纯粹由剖面决定的代数求值。

这些结果共同证明了拉丁杨表在阶梯尾部扩展下的增长是由一个不变的局部分支因子决定的。

定理 latin_double_three_tail_four_extensions (Lean 4 已验证)
theorem latin_double_three_tail_four_extensions (k : ℕ) (hk : 5 ≤ k) : ∀ T ∈ latin_tableaux (latin_double_three_tail_shape k), Matrix.permanent (latin_top_row_availability (latin_double_three_tail_shape k) T (k+1)) = 4

4. 证明

证明分为两个部分。首先,行和列条件强迫了对各列中符号集的精确描述。其次,该描述确定了每一个允许的新顶行。第二部分给出了两个独立的二元选择,所有其他条目都被强迫确定。

### 精确列剖面

记 $C_j$ 为现有杨表中第 $j$ 列中出现的符号集。列索引从零开始。定理 latin_double_three_tail_profile_all 提供了一个符号 $s\in\{1,2,3\}$ 和一个例外列 $c\in\{0,1,2\}$,使得:

  1. 对于 $j<3$,例外列具有 $C_c=\{1,\ldots,k-2\}\cup\{k\}$,而其他两列各具有 $C_j=\{1,\ldots,k-1\}$。
  2. 对于 $3\le j<k-2$,有 $C_j=\{1,\ldots,k-j\}$。
  3. 最后两个被占用的列具有 $C_{k-2}=\{1,2,3\}\setminus\{s\}$ 和 $C_{k-1}=\{s\}$。

预期的列 $k$ 是空的。这些是关于符号集的陈述;它们并不规定列内的顺序。特别是,前三列中的两个普通列省略了相同的符号 $k$。例外列省略了 $k-1$。所有三列也都省略了新符号 $k+1$。

该剖面通过对 $k$ 进行归纳来证明。基础情况是形状 $(5,4,3,3)$。底部两行是 $1,2,3$ 的置换,并且它们在每列中的条目互不相同。长度为 4 的行是 $1,2,3,4$ 的置换,而长度为 5 的行是 $1,2,3,4,5$ 的置换。有限的行界和列不等式迫使最后两列将 $\{1,2,3\}$ 划分为一个对和一个单元素集。它们还强迫前三列中的两列包含 $\{1,2,3,4\}$,其余一列包含 $\{1,2,3,5\}$。这是一种结构性计算,而不是对杨表总数的评估。

基础强迫性也可以直接看出。在前三列中的每一列中,底部的两个条目留下一个缺失的低位符号;这三个缺失的符号构成 $1,2,3$ 的一个置换。长度为 4 的行必须将其符号 4 放置在前三列中。否则,它将用缺失的低位符号填满所有三个位置,使得顶行中的三个位置仅有 4 和 5 可用,这是不可能的。在长度为 4 的行使用低位符号的两列中,顶行必须以任意顺序使用 4 和 5。在剩下的一列中,它必须使用缺失的低位符号。然后,长度为 4 的行在第 3 列中使用该相同的低位符号,而长度为 5 的行在其最后两个位置使用其他两个低位符号。因此,第 3 列是一个低位符号对,第 4 列是其补单元素集。前三列的剖面同时也随之得出。

对于归纳步,取形状为 $(k+1,k,\ldots,4,3,3)$ 的杨表并删除其第一行。剩余的填法是前一个形状的拉丁杨表,因此归纳假设给出了其剖面。被删除的行是避开每个旧列符号的 $1,\ldots,k+1$ 的置换。下面的强迫性论证准确地展示了它可以如何放置。添加该行会更新剖面:接收 $k+1$ 的普通列成为新的例外列,中间的初始区间各自获得其下一个符号,而最后三个低位符号位置产生新的末端对和单元素集。因此,相同的描述在参数 $k+1$ 处成立。经检验的归纳步实现了该更新,给出了每个 $k\ge5$ 的剖面。

### 计算允许的行

固定一个具有剖面参数 $c$ 和 $s$ 的杨表。新的顶行必须恰好使用每个符号 $1,\ldots,k+1$ 一次。它在列 $j$ 中的条目必须位于 $C_j$ 之外。

考虑前三列。在两个普通列的每一列中,唯一可用的符号是 $k$ 和 $k+1$。由于这两列必须接收不同的符号,它们以任意顺序接收 $k$ 和 $k+1$。恰好有两种选择。例外列允许 $k-1$ 和 $k+1$,但 $k+1$ 已经在一个普通列中使用。因此它的条目被强迫为 $k-1$。前三列恰好使用 $k-1,k,k+1$。

现在按递增顺序考察列 $j=3,4,\ldots,k-3$。在列 $j$ 处,至多为 $k-j$ 的每个符号都被旧列集禁止。大于 $k+1-j$ 的每个符号已经在前三列或前面的中间列中使用。恰好剩余一个符号可用:$k+1-j$。因此,这些中间条目按降序被强迫为 $k-2,k-3,\ldots,4$。当 $k=5$ 时,中间范围为空,因此在此阶段没有选择或额外条件。

对于最后三列 $k-2,k-1,k$,仅剩余符号 $1,2,3$。在第 $k-2$ 列中,旧符号是 $\{1,2,3\}\setminus\{s\}$,因此新条目必须是 $s$。另外两个低位符号可以按任意顺序放置在第 $k-1$ 和第 $k$ 列中。两种放置方式均可行:第 $k-1$ 列仅禁止 $s$,而第 $k$ 列没有旧条目。这给出了恰好两个最终选择。

反之,通过这些选择构造出的每一行都是有效的。第一组不重复地使用了三个最大的符号。被强迫的中间组一次性使用了从 $4$ 到 $k-2$ 的每个符号。最后一组一次性使用了 $1,2,3$。根据构造,每个条目都避开了其旧列集。因此恰好有 $$2\cdot1\cdot2=4$$ 个有效顶行。第一组和最后一组中的选择是相互独立的,并且没有其他自由度。

### Lean 中的积和式计算

0-1 可用性矩阵精确记录了允许的符号-列对。其积和式计算在每列中选择一个可用符号的置换,因此行计数论证也是一个积和式求值。

latin_double_three_tail_permanent_of_profile 的证明通过独立地对行和列重新编号来实现这一求值。符号从高到低排序,列分为前三列、中间 $k-5$ 列和最后三列。在这些坐标下,矩阵是分块上三角矩阵。三个对角块的大小分别为 $3$、$k-5$ 和 $3$。

第一个块的积和式为 2:普通列交换 $k$ 和 $k+1$,而例外列接收 $k-1$。中间块是上三角的,对角线元素为 1,因此其积和式为 1。更明确地说,有限有序索引集的非恒等置换必须将某个索引向上发送;该选择会遇到三角矩阵的零条目。只有恒等置换有贡献。最后一个块的积和式为 2,对应于不同于 $s$ 的低位符号的两种排序。

重新编号保持积和式不变,并且该分块上三角矩阵的积和式是其对角块积和式的乘积。结果为 $2\cdot1\cdot2=4$。这也涵盖了 $k=5$ 的情况,此时中间块为空且其积和式为 1。该论证对 $k$ 是符号化的;它不会对每个杨表分别枚举 $(k+1)!$ 个置换。

### 六列示例

对于 $k=5$,选择剖面参数 $c=0$ 和 $s=1$。被占用的列集为 $$C_0=\{1,2,3,5\},\quad C_1=C_2=\{1,2,3,4\},\quad C_3=\{2,3\},\quad C_4=\{1\},$$ 且 $C_5$ 为空。四个可能的新行为 $$(4,5,6,1,2,3),\quad(4,5,6,1,3,2),$$ $$(4,6,5,1,2,3),\quad(4,6,5,1,3,2).$$ 第一个坐标被强迫为 4;坐标 1 和 2 交换 5 和 6;坐标 3 被强迫为 1;最终坐标交换 2 和 3。这直接展示了两个独立的二元选择。

最后,主定理应用了已证明的两个引理: ``lean by intro T hT exact latin_double_three_tail_permanent_of_profile k hk T (latin_double_three_tail_profile_all k hk T hT) `` 成员关系假设给出了典则剖面,而积和式引理对它的可用性矩阵进行了求值。结论适用于所述形状的每个拉丁杨表,而剖面引理仍然是从任意杨表到矩阵计算的基本桥梁。

5. 讨论

定理 latin_double_three_tail_four_extensions 为整个双三尾阶梯族在将参数从 $k$ 增加到 $k+1$ 时确立了统一的、逐杨表的扩展数 4。这为 arXiv:2610.29291 中猜想 6.3 的计数提供了所需的归纳步。

猜想 6.3 提出了对于所有 $k \ge 5$,形状为 $\lambda = (k, k-1, \dots, 4, 3, 3)$ 且类型为 $\lambda'$ 的拉丁杨表数量 $LT(\lambda)$ 是否等于 $9 \cdot 4^{k-3}$ 的问题。arXiv:2610.29291 中早期的结果提供了定性和聚合工具:引理 5.4 确立了在顶部添加一行可转化为计算可用性矩阵的积和式,而命题 5.5 确立了顶行单调性。然而,这两个结果都没有给出任何单个积和式的确切值。

此处给出的结果通过直接计算积和式细化了这一图景。因为形状为 $\lambda(k)$ 的每个拉丁杨表都以恰好 4 种方式扩展为顶行长度为 $k+1$ 的有效填法,所以总体计数满足严格的递推关系: $$LT(\lambda(k+1)) = 4 \cdot LT(\lambda(k)),$$ 对所有 $k \ge 5$ 成立。这表明猜想 6.3 中的幂次 $4^{k-3}$ 不是总体平均值或渐近近似,而是在状态空间中每一个杨表处逐点成立的均匀 4 比 1 分支比的精确结果。

虽然 latin_double_three_tail_four_extensions 解决了从 $k$ 到 $k+1$ 的步骤,但它本身并未确立 $k=5$ 时的基准计数。在 $k=5$ 时,形状为 $(5, 4, 3, 3)$,猜想 6.3 预测: $$LT(5, 4, 3, 3) = 9 \cdot 4^{5-3} = 9 \cdot 16 = 144.$$ 我们的定理保证了如果 $LT(5, 4, 3, 3) = 144$,那么: $$LT(\lambda(k)) = 144 \cdot 4^{k-5} = 9 \cdot 4^2 \cdot 4^{k-5} = 9 \cdot 4^{k-3}$$ 对所有 $k \ge 5$ 成立。然而,在形式上评估有限集 latin_tableaux (latin_double_three_tail_shape 5) 的基数为 144 超出了 latin_double_three_tail_four_extensions 的范围,后者纯粹侧重于归纳步的可用性积和式恒等式。

本文材料指出了该结果之后的两个直接方向:

  • 在 Lean 4 内精确验证基准计数 $LT(5, 4, 3, 3) = 144$,与 latin_double_three_tail_four_extensions 结合将完整完成猜想 6.3 的形式化证明。
  • 研究列剖面刚性机制是否能推广到双 3 尾之外,确定还有哪些阶梯尾部构型会产生常数可用性积和式。

为什么是研究级成果

  • a new question answered: Evaluate every individual availability permanent as 4 on the double-3-tail staircase family, rather than merely expressing the total count as a sum of unknown permanents or proving top-row monotonicity.

Lean 声明

  • latin_double_three_tail_four_extensionsConjecture: every Latin tableau of shape (k,k-1,...,4,3,3), k at least 5, extends in exactly four ways after adding the next top row of…
  • latin_double_three_tail_shapeFor k at least 5, the Young diagram with row lengths (k,k-1,...,4,3,3). Its i-th row has length max(3,k-i) for i < k-1 and is empty…
  • latin_tableauxFor a Young diagram μ, the set of Latin tableaux of shape μ and type μ' is the finset of fillings T from the cells of μ to natural numbers…
  • latin_top_row_availabilityThe zero-one matrix whose row index is a prospective symbol minus one and whose column index is a column: an entry is one precisely when…
  • latin_double_three_tail_profile_allEvery Latin tableau in the double-3-tail staircase family has the three canonical column-symbol profiles (nine profiles before permuting…
  • latin_double_three_tail_permanent_of_profileA filling with the canonical column profile has exactly four legal permutations for a new top row of length k+1.

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

参考文献

  1. arXiv:2610.29291 — Counting and constructing Latin tableaux

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