问题
对拉丁方 L,第 i 行确定一个置换 ρi(把列号映到该列的符号),第 j 列确定置换 κj(把行号映到符号)。定义标号奇偶:sign(∏iρi)·sign(∏jκj)(该值在符号重标记下不变:两种符号各乘 sign(σ)n,总变化 sign(σ)2n=+1)。Alon–Tarsi 猜想(1990):偶数阶 n 中,偶标号与奇标号的拉丁方个数不相等(差非零)。奇数阶时差恒为零(命题 1 的配对论证),这正是 «偶数阶» 的由来。猜想的回报巨大:它蕴含列表染色理论的一族推广(Galvin 定理的 «染色–列表» 升级)、组合零点定理的一系推论、以及 Rota 型基猜想的分支。目前只对部分阶(素数 p 的 p±1、某些合数)与少数函数类验证。
主要概念
符号差与多项式系数
现代处理把猜想转成多项式恒等式:设 ⟨L⟩ 记拉丁方的 «符号和»,猜想等价于某个显式多项式(含 ∏(Σaijxiyj) 型乘积)的特定单项式系数非零。组合零点定理(Combinatorial Nullstellensatz)的机器:系数非零 ⟺ «次数配方» 在某顶点上非零——把组合计数问题化成 «一个多项式在一个点上的取值»。
为什么它难
差 Δ(n) 是 «拉丁方按符号差的加权计数»——加权计数的一般工具(不变量理论、表示论)在此面对 «拉丁方」 这个刚性但混乱的对象。已证族的共性:阶 n 与某个素数 p 只差 ±1,此时可用 «素域上的多项式取值» 的整除技巧;一般合数阶没有 «近素数» 的把手。
主要命题与证明
命题 1(奇数阶差恒为零,完整证明) 奇数 n 时,偶标号与奇标号拉丁方个数相等。
证明 采用正文的标号奇偶定义。考察 «交换前两行» 的对合 τ:它把拉丁方映为拉丁方。行侧:诸行置换 ρi 作为集合不变(只是次序互换),sign(∏ρi) 不变;列侧:每列置换 κj 复合同一个行对换 ⟹ sign(∏κj) 乘 (−1)n。故 τ 把每个拉丁方的标号奇偶乘 (−1)n;n 为奇数时奇偶翻转,且 τ 无不动点(交换前两行必改变方表)——偶标号与奇标号拉丁方被 τ 一一配对,个数相等。□
命题 2(Alon–Tarsi 主定理,1992;陈述) 当 n = p−1(p 素数)时猜想成立(Δ(n) ≠ 0);n = p+1 的情形由 Glynn 等后续工作确立。证明走 «有限域多项式»:把差写成 ℤp 上显式多项式的单项式系数,用 «阶乘整除»(n < p 保证零点定理可用)与 Vandermonde 行列式的符号展开把系数算成非零的 «差积»。
梗概 关键配 方:∏i<j(xi−xj) 的 Vandermonde 符号与 «每行每列恰一次» 的置换展开相乘后,目标单项式 xδyδ 的系数在 n=p−1 时恰为 «阶乘比的素域像»,由 Wilson 定理 ((p−1)! ≡ −1) 判非零。□
命题 3(列表染色回报;陈述) 猜想蕴含:完全二部多重图 Kn,n·m 的线图的列表色数恰为 Δ(Galvin 定理的 «组合零点» 证明路线)以及 «染色数 = 列表色数» 的若干推广;反之列表染色的进展也反过来给出 Δ(n) 的部分信息——两条线在 «Alon–Tarsi 多项式» 上汇合。
说明 这一 «猜想 → 应用» 的方向已算闭合:Galvin 定理本身不依赖猜想(有独立证明),但猜想给出的推广(如 «paint number»、对应上界)都以下面这个非零性为引擎。□
进展与文献
Alon–Tarsi《A note on the number of Latin squares》(1990/92);Glynn 的 p+1 情形;Drisko 的拉丁长方横截与符号差工作;Alon《Combinatorial Nullstellensatz》的机器文。开放核心:一般偶数阶(如 n=12,14)的 Δ(n) ≠ 0——每个具体阶都是一次 «多项式系数» 攻坚;猜想与 «拉丁方计数渐近»(40 号)的符号修正版。