2025-11-26T05:13:18.966584

Words with Repeated Letters in a Grid

Halberstam, Schildkraut
Given a word $w$, what is the maximum possible number of appearances of $w$ reading contiguously along any of the directions in $\{-1, 0, 1\}^d \setminus \{\mathbf{0}\}$ in a large $d$-dimensional grid (as in a word search)? Patchell and Spiro first posed a version of this question, which Alon and Kravitz completely answered for a large class of ``well-behaved" words, including those with no repeated letters. We study the general case, which exhibits greater variety and is often more complicated (even for $d=1$). We also discuss some connections to other problems in combinatorics, including the storied $n$-queens problem.
academic

Words with Repeated Letters in a Grid

基本信息

  • 论文ID: 2511.19678
  • 标题: Words with Repeated Letters in a Grid
  • 作者: Zachary Halberstam, Carl Schildkraut
  • 分类: math.CO (Combinatorics)
  • 发表时间: 2025年11月24日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2511.19678

摘要

本文研究在d维网格中，沿着"单词搜索"方向（即方向向量在{-1,0,1}^d{0}中）连续读取时，给定单词w的最大出现次数问题。Patchell和Spiro首次提出该问题，Alon和Kravitz完全解决了无重复字母单词的情况。本文研究包含重复字母的一般情况，展现出更丰富的结构和复杂性（即使在d=1时也是如此），并揭示了与n皇后问题等经典组合问题的深刻联系。

研究背景与动机

1. 核心问题

给定单词w和维度d，在一个n₁×n₂×...×n_d的d维环形网格（每个坐标模n_i）中，如何放置字母以最大化w的出现次数？这里"出现"指沿着3^d-1个搜索方向之一连续读取得到w。

2. 问题重要性

  • 理论意义：该问题连接了加法组合学、傅里叶分析和图论等多个数学分支
  • 组合优化：涉及在约束条件下的极值配置问题
  • 经典问题联系：与周期平铺猜想、n皇后问题等著名问题有深刻联系

3. 现有工作局限

Alon和Kravitz 1完全解决了"良好行为"单词的情况，包括：

  • 无重复字母的单词
  • 满足特定约束的单词（如字母只出现在奇数或偶数位置，且无重复的两字母块）

但对于一般含重复字母的单词，问题仍未解决，且展现出更复杂的结构。

4. 研究动机

  • 探索重复字母单词的极值配置
  • 分类哪些单词是"d-可堆叠"或"d-可倾斜"的
  • 建立与其他组合问题的联系

核心贡献

  1. 完全解决一维情况（定理1.2）：给出任意单词在一维情况下的浓度C₁(w)的闭形式，并分类所有极值网格
  2. 建立维度界（命题1.3）：证明对任意单词w和维度d： 3d−1C1(w)≤Cd(w)≤3d−12C1(w)3^{d-1}C_1(w) \leq C_d(w) \leq \frac{3^d-1}{2}C_1(w)
  3. d-可堆叠性刻画（定理1.4）：
    • 奇偶单词（字母不同时出现在奇偶位置）在所有维度都是d-可堆叠的
    • 字母重复单词保持d-可堆叠性
    • 完全刻画4字母单词的2-可堆叠性
    • 证明AB^(ℓ-1)（ℓ>3）不是2-可堆叠的
  4. d-可倾斜性界（定理1.5）：
    • 长度为ℓ的单词在d≥8log₂ℓ+47时不可能d-可倾斜
    • 当ℓ的所有素因子≥2^d时，AB^(ℓ-1)是d-可倾斜的
  5. 方法论贡献：发展了四种主要技术
    • 加法重构方法
    • 组合归约技术
    • 局部线性规划分析
    • 傅里叶分析方法

方法详解

任务定义

核心概念：

  • 网格Γ：从G=∏ᵢ₌₁ᵈ Z/nᵢZ到字母表Σ的函数
  • 出现：对(p,v)∈G×({-1,0,1}^d{0})，若Γ在位置{p+iv}_^{len(w)-1}处的字母依次为w的字母，则称(p,v)为w的一个出现
  • 浓度：cd(w,Γ) = ct(w,Γ)/|Γ|，即出现次数除以网格大小
  • 极大浓度：Cd(w) = sup_Γ cd(w,Γ)

核心问题：给定单词w和维度d，确定Cd(w)的值。

核心技术框架

1. 加法重构方法（第3节）

将问题转化为集合加法问题。对方向v，定义： Sv={p∈G:(p,v)是w的出现}S_v = \{p \in G : (p,v) \text{是w的出现}\}

关键观察： (Su−Sv)∩Iu,v=∅(S_u - S_v) \cap I_{u,v} = \emptyset 其中Iu,v={iv−ju:0≤i,j<len(w),wi≠wj}I_{u,v} = \{iv - ju : 0 \leq i,j < len(w), w_i \neq w_j\}

这将计数问题转化为在加法约束下最大化∑v∣Sv∣/∣G∣\sum_v |S_v|/|G|。

一维情况的完整解：

定义三个参数：

  • c_left：最长回文前缀长度
  • c_right：最长回文后缀长度
  • c_repeat：既是真前缀又是真后缀的最长子串长度

定理3.1：对长度为ℓ的单词w：

  • 若w非回文：C1(w)=max⁡(1ℓ−crepeat,1ℓ−cleft+cright2)C_1(w) = \max\left(\frac{1}{\ell-c_{repeat}}, \frac{1}{\ell-\frac{c_{left}+c_{right}}{2}}\right)
  • 若w是回文：C1(w)=2ℓ−crepeatC_1(w) = \frac{2}{\ell-c_{repeat}}

两种极值构造：

  1. 构造1（重叠相同方向）：当c_repeat较大时，将w=vs（s是长度c_repeat的重复子串）重复v部分
  2. 构造2（交替方向）：当c_left+c_right较大时，交替正反读w，重叠回文部分

2. 组合归约技术（第4节）

投影归约命题4.2：若存在映射π:Σ→Σ'和一维网格Γ₀使得：

  • Γ₀是w-极值的
  • π(Γ₀)是w'-极值的
  • 对任意网格Γ：ct(w,Γ)/ct(w',π(Γ)) ≤ ct(w,Γ₀)/ct(w',π(Γ₀))

则对任意d：Cd(w)/C₁(w) ≤ Cd(w')/C₁(w')

应用实例：

  • 奇偶单词（定理1.4a）：将字母投影到{奇,偶}，归约到AB的情况
  • 字母重复单词（定理1.4b）：通过子采样技术证明w^(k)保持d-可堆叠性
  • 短单词归约：将ABCA、ABBC、ABBA、BABB归约到ABB

3. 局部线性规划分析（第5节）

核心思想：对固定的局部区域S⊂Z^d，通过线性规划优化权重函数F。

命题5.2：若权重函数F满足：

  • (i) 对每个方向类型，平均权重为K
  • (ii) 对任意无穷网格G：∑(p,v)∈A(w,G)F(p,v)≤M\sum_{(p,v)\in A(w,G)} F(p,v) \leq M

则Cd(w) ≤ M/K

线性规划构造：

  1. 选择局部区域S（如3×3或5×5网格）
  2. 选择字母A，定义可行方向集F
  3. 优化： min⁡M s.t. ∑(p,v)∈A(w,G)F(p,v)≤M,∀G∈G\min M \text{ s.t. } \sum_{(p,v)\in A(w,G)} F(p,v) \leq M, \forall G\in\mathcal{G} 其中G是S外全为A的网格集合

关键优化：

  • 利用对称性减少变量数
  • 迭代添加违反约束
  • 对2^|S|个网格进行枚举验证

成功案例：

  • 证明ABB是2-可堆叠的（C₂(ABB)≤2）
  • 证明ABCC是2-可堆叠的（C₂(ABCC)≤6/5）
  • 计算C₂(BABBB)=8/5（既非2-可堆叠也非2-可倾斜）

4. 傅里叶分析方法（第7节）

应用1：形状(Z/3Z)^d网格中的ABB

引理7.1：对f:(Z/3Z)^d→0,1，α=𝔼f： Ex,yf(x)(1−f(x+y))(1−f(x+2y))≤32α(1−α)2\mathbb{E}_{x,y} f(x)(1-f(x+y))(1-f(x+2y)) \leq \frac{3}{2}\alpha(1-\alpha)^2

证明技术：

  • 将期望展开为傅里叶系数
  • 利用ω=e^(2πi/3)的性质
  • 应用引理7.2：若ℜ(z),ℜ(ωz),ℜ(ω²z)≤β，则ℜ(z³)≤β³

应用2：d-可倾斜性的维度界

核心策略（定理1.5a证明）：

  1. 构造近极值网格Θ（引理7.3）
  2. 应用稳定性结果（定理3.2）：近极值搜索线有近似相同的字母分布
  3. 傅里叶分析矛盾（引理7.4）：在(Z/nZ)^d（n<2^d）中，不可能所有搜索线都有相同字母分布

引理7.4：在形状(Z/nZ)^d（n<2^d）的网格中，若字母A占比α，则存在两条搜索线的A数量相差至少： min⁡(α,1−α)3d/2n\frac{\sqrt{\min(\alpha,1-\alpha)}}{3^{d/2}}n

证明使用二阶矩方法和傅里叶变换。

技术创新点

  1. 统一框架：首次系统研究含重复字母单词，揭示其比无重复字母情况复杂得多
  2. 加法视角：将网格问题转化为加法组合问题，建立与周期平铺的联系
  3. 多层次归约：发展了灵活的组合归约技术，能处理各种单词类型
  4. 局部-全局原理：通过局部约束的线性规划获得全局上界，并在某些情况达到紧界
  5. 傅里叶-稳定性结合：创新性地结合一维稳定性结果和高维傅里叶分析，获得维度界
  6. n皇后联系：揭示AB^(ℓ-1)的d-可倾斜性与模n皇后问题的深刻联系

实验设置

本文为纯理论数学论文，不涉及传统意义上的实验，但包含大量计算验证：

计算验证

  1. 一维情况：对所有长度≤5的单词完全计算C₁(w)
  2. 二维短单词：
    • 完全确定所有4字母单词的2-可堆叠性（10个同构类）
    • 部分确定5字母单词（31个同构类中的16个）
  3. 线性规划计算：
    • ABB：在3×3区域上验证512个网格配置（引理A.1手工验证）
    • ABCC：在5×5区域上验证（引理A.2手工验证）
    • BABBB：在更大区域上计算机验证
    • ABBB：获得上界C₂(ABBB)≤59526/35459≈1.679

实现细节

线性规划优化策略：

  • 利用对称群(Z/2Z)^d⋊Sd减少变量
  • 将Π-轨道上的网格合并为单一约束
  • 迭代采样约束求解
  • 对称性使计算从2^|S|降至可处理规模

实验结果

主要理论结果

1. 一维完全解（定理3.1, 3.3）

结果展示：

  • SALSA：c_repeat=2, C₁(SALSA)=1/3（构造：...SALSALSALSAL...）
  • ELEPHANT：c_left=1, c_right=1, c_repeat=0, C₁(ELEPHANT)=1/7（构造：...HPELEPHANTNAHPELEPH...）
  • ABABAB：c_repeat=4, C₁(ABABAB)=1（构造：...ABABABABAB...，每个字母用于6次）

结构刻画（命题3.3）：

  • 若c_left+c_right<2c_repeat：仅构造1极值
  • 若c_left+c_right>2c_repeat：仅构造2极值
  • 若c_left+c_right=2c_repeat：两种构造都极值，且所有极值是它们的组合

2. 二维四字母单词完全分类（定理1.4c）

同构类代表2-可堆叠性方法
AB✓ (d-可堆叠)Alon-Kravitz
ABA✓ (d-可堆叠)定理1.4a（奇偶单词）
ABB✓局部线性规划（引理5.4）
ABC✓ (d-可堆叠)Alon-Kravitz
AABB✓ (d-可堆叠)定理1.4b
ABAB✓ (d-可堆叠)定理1.4a
ABBA✓归约到ABB（引理4.3）
BABB✓归约到ABB（引理4.3）
AAAB✗反例网格（图5）
AABC✓局部线性规划（引理5.5）
ABAC✓ (d-可堆叠)定理1.4a
ABBC✓归约到ABB（引理4.3）
ABCA✓归约到ABB（引理4.3）
ABCD✓ (d-可堆叠)Alon-Kravitz

关键发现：ABBB（同构于AAAB）是唯一非2-可堆叠的4字母单词。

3. 五字母单词部分结果

d-可堆叠（8个）： ABABA, ABABC, ABACA, ABACD, ABCBA, ABCBD, ABCDA, ABCDE（定理1.4a） AABBA（归约到AABB）

2-可堆叠（另外5个）： AABCC, AABAA（归约到AAB） ABCAB（归约到ABB） AABCB, ABBAC（归约到ABCC）

非2-可堆叠（2个）：

  • ABBBB：C₂(ABBBB)=8/5>6/5=3C₁(ABBBB)
  • BABBB：C₂(BABBB)=8/5>3/2=3C₁(BABBB)（引理5.6）

未解决：31个同构类中的15个

4. 维度界结果

定理1.5验证：

  • 上界：对长度ℓ单词，d≥8log₂ℓ+47时不可能d-可倾斜
  • 下界：当ℓ的所有素因子≥2^d时，AB^(ℓ-1)是d-可倾斜的
  • 紧性：由Bertrand公设，上界在常数因子内最优

具体例子：

  • ℓ=5, gcd(5,6)=1：AB⁴是2-可倾斜的（C₂(AB⁴)=8/5=4C₁(AB⁴)）
  • ℓ=7, gcd(7,6)=1：AB⁶是2-可倾斜的（对应7皇后问题）

消融实验

虽非传统消融，但论文展示了各技术组件的必要性：

  1. 加法方法的必要性：一维情况若不用加法重构，难以获得闭形式和结构刻画
  2. 组合归约的威力：
    • 无归约：需分别分析14个4字母单词
    • 有归约：仅需直接分析ABB、ABCC等少数基础情况
  3. 局部方法的不可替代性：
    • ABB的2-可堆叠性：其他方法均无法处理
    • 关键在于能获得紧界（C₂(ABB)=2恰好等于3C₁(ABB)）
  4. 傅里叶分析的局限与优势：
    • 局限：仅能处理特殊结构（如(Z/3Z)^d形状）
    • 优势：获得一般性维度界，这是局部方法无法做到的

案例分析

案例1：CROC的复杂性（注释3.8）

CROC满足c_left+c_right=2c_repeat，属于定理3.3的情况(c)。

  • v=CROC, v'=CORO
  • 极值网格可以是Grid(v₁...vₘ)，其中vᵢ∈{v,v'}
  • 大小3n的极值网格数量关于n指数增长
  • 例：Grid(CROCROCOR)是极值的但不等价于构造1或2

案例2：BABBB的非单调性（引理5.6）

网格Γ (5×5):
A B B B B
B B B A B
B A B B B
B B B B A
B B A B B
  • c₂(BABBB,Γ)=8/5
  • 3C₁(BABBB)=3×(1/2)=3/2<8/5
  • 4C₁(BABBB)=2>8/5
  • 结论：既非2-可堆叠也非2-可倾斜，展示了中间行为

案例3：AB⁶与7皇后问题（图6-7）

7个非攻击皇后配置对应C₂(AB⁶)=4C₁(AB⁶)的极值网格：

A B B B B B B
B B A B B B B
B B B B A B B
B B B B B B A
B A B B B B B
B B B A B B B
B B B B B A B

每个A周围8个方向都有6个连续B，共56次出现。

实验发现

  1. 复杂性跃升：从无重复字母到有重复字母，问题复杂度显著增加
    • 无重复：所有单词d-可堆叠
    • 有重复：出现非d-可堆叠、d-可倾斜、中间情况三种类型
  2. 维度效应：
    • 低维(d=1,2)：需要精细分析每个单词
    • 高维(d≥8log₂ℓ)：一般性结果显示无单词d-可倾斜
  3. 方法互补性：
    • 组合方法：处理结构化单词
    • 线性规划：处理少数关键硬例
    • 傅里叶分析：提供渐近界
  4. 开放问题丰富性：
    • 31个5字母单词中15个未解决
    • ABB在d≥3时的行为未知
    • ABBB的精确C₂值未知

相关工作

1. 网格中的单词搜索

Patchell-Spiro 14 (2022)：

  • 首次系统提出问题
  • 给出部分结果和猜想

Alon-Kravitz 1 (2024)：

  • 完全解决无重复字母单词
  • 主要结果：对"良好行为"单词w，Cd(w)=3^(d-1)/(len(w)-1)
  • 极值构造：交替正反读，如...w₂w₁w₂...wℓwℓ...w₂w₁...
  • 方法：傅里叶分析+组合论证

本文扩展：

  • 处理一般重复字母单词
  • 揭示更丰富的结构（三种类型：d-可堆叠、d-可倾斜、中间）
  • 发展新方法（局部线性规划）

2. 加法组合学

周期平铺猜想：

  • Greenfeld-Tao 8 (2024)反例：存在非周期平铺
  • 本文问题2.5：是否存在极值网格？与平铺猜想相似
  • 联系：平铺要求S+T=Z^d，本文要求(S-S)∩I=∅

Kravitz集密度 11：

  • 研究避免特定差集的集合密度
  • 与本文的加法约束相关

3. 极值组合学

Flag代数 16：

  • Razborov的半定规划方法
  • 用于子图密度等问题
  • 本文的线性规划是类似思想的简化版本

几何极值问题：

  • 无单位距离集 2,17
  • 无正交向量的球面集 3,7
  • 共同点：局部约束下的全局极值

4. n皇后问题

经典n皇后 4：

  • 1848年起的经典问题
  • Bell-Stevens综述

模n皇后：

  • Pólya 15 (1921)：gcd(n,6)=1时存在n个非攻击皇后
  • Klarner 9, Kunt 10：高维推广
  • Nudelman 13：不同攻击约定

本文贡献：

  • 推论8.2：对gcd(n,(2d)!)=1，存在n^(d-1)个非攻击皇后
  • 这证明了Bell-Stevens猜想25的一个方向
  • 定理1.4d和1.5b建立了AB^(ℓ-1)与ℓ皇后问题的等价性

5. 傅里叶分析在组合学中的应用

算术级数：

  • Roth定理(3-AP)、Szemerédi定理(k-AP)
  • 高阶傅里叶分析 18
  • 本文问题类似于限制差的AP问题，但更困难

最新进展 5：

  • 限制3-AP的有效界
  • 本文问题对ℓ>3可能需要高阶傅里叶分析

结论与讨论

主要结论

  1. 一维完全解：给出任意单词的C₁(w)闭形式和极值网格完全分类
  2. 二维短单词：完全解决4字母单词，部分解决5字母单词
  3. 维度界：
    • 一般界：3^(d-1)C₁(w) ≤ Cd(w) ≤ (3^d-1)/2·C₁(w)
    • d-可倾斜性：长度ℓ单词在d≥8log₂ℓ+47时不可能d-可倾斜
  4. 结构定理：
    • 奇偶单词总是d-可堆叠
    • 字母重复保持d-可堆叠性
    • AB^(ℓ-1) (ℓ>3)不是2-可堆叠
  5. 方法论：建立了四种互补技术的工具箱

局限性

  1. 计算复杂性：
    • 线性规划方法对|S|>25的区域不可行
    • 手工验证（如ABB、ABCC）极其繁琐
    • 限制了能处理的单词长度
  2. 覆盖范围：
    • 5字母单词仍有48%未解决
    • 6字母及以上几乎完全未触及
    • ABB在d≥3时的行为未知
  3. 方法局限：
    • 傅里叶分析需要特殊结构（如形状(Z/3Z)^d）
    • 组合归约需要找到合适的"基础单词"
    • 局部方法难以证明非紧界
  4. 理论空白：
    • 问题2.5（极值网格存在性）仅在d=1时解决
    • 高维稳定性结果（问题9.6）完全未知
    • 一般单词的"典型行为"不清楚

未来方向

论文明确提出的问题：

  1. 极值网格存在性（问题2.5）：
    • 对每个(w,d)，是否存在w-极值网格？
    • 类比：周期平铺猜想已被否定，本问题在高维可能也是否定的
  2. 短单词完全分类：
    • 问题9.1：哪些5字母单词是2-可堆叠的？
    • 问题9.2：ABB是否对所有d都d-可堆叠？
    • 问题9.3：C₂(ABBB)=8/5吗？
  3. 高维结构（问题9.5-9.6）：
    • 所有w-极值网格是否有相同字母分布？
    • 是否存在类似定理3.2的稳定性结果？
  4. 渐近行为（问题9.4）：
    • 长单词中d-可堆叠/d-可倾斜的比例？
    • "典型"单词的行为？

潜在研究方向：

  1. 高阶傅里叶分析应用：
    • 能否用Gowers范数处理长单词？
    • 与限制差的AP问题的精确联系？
  2. 计算方法改进：
    • 更高效的线性规划求解
    • 机器学习辅助寻找极值配置
    • 符号计算验证
  3. 其他组合问题联系：
    • 与Ramsey理论的联系
    • 与编码理论的联系
    • 推广到非网格结构（如图、流形）
  4. 算法问题：
    • 给定(w,d)，近似Cd(w)的算法复杂度？
    • 构造近极值网格的高效算法？

深度评价

优点

  1. 问题选择优秀：
    • 自然且具有挑战性
    • 连接多个数学分支
    • 既有理论深度又有具体可计算性
  2. 方法论创新：
    • 多样性：四种互补技术各有所长
    • 统一性：通过加法重构提供统一视角
    • 实用性：线性规划方法在某些情况获得紧界
  3. 结果深度：
    • 一维完全解包含精细的结构刻画（定理3.3）
    • 稳定性结果（定理3.2）为高维分析奠定基础
    • 与n皇后问题的联系具有独立价值（推论8.2）
  4. 技术严谨性：
    • 所有主要定理都有完整证明
    • 计算验证透明（附录A提供手工验证）
    • 对局限性和开放问题诚实
  5. 写作质量：
    • 结构清晰，按技术方法组织
    • 大量例子和图示（如图5-9）
    • 详细的动机说明和直观解释

不足

  1. 计算瓶颈：
    • 线性规划方法的可扩展性有限
    • ABB的手工验证（引理A.1）极其繁琐，难以推广
    • 对BABBB等情况依赖计算机，无简洁证明
  2. 覆盖不完整：
    • 5字母单词仍有15/31未解决
    • 对长单词几乎没有结果
    • 高维情况（d≥3）结果稀少
  3. 理论空白：
    • 问题2.5（极值存在性）在d≥2时完全开放
    • 缺乏一般单词的渐近结果
    • 高维稳定性理论缺失
  4. 方法局限性：
    • 傅里叶分析仅适用于特殊形状网格
    • 组合归约需要识别"基础单词"，缺乏系统方法
    • 局部方法难以处理非紧界情况
  5. 某些证明复杂度：
    • 定理3.3(c)的证明极其技术化
    • 定理7.4的证明依赖多个精细估计
    • 可读性有时受影响

影响力

理论贡献：

  • 为含重复字母单词开辟了系统研究
  • 发展的技术（特别是局部线性规划）可能适用于其他极值问题
  • 与n皇后问题的联系可能激发新研究

方法论价值：

  • 展示了多种技术的互补性
  • 加法重构视角可能启发相关问题
  • 局部-全局原理的成功应用

开放问题：

  • 提出了大量具体、可攻击的问题
  • 不同难度层次，适合不同背景研究者
  • 计算辅助证明的空间大

局限性：

  • 短期内难以完全解决（如一般单词的Cd(w)）
  • 需要新思想突破计算瓶颈
  • 实际应用场景不明显（纯理论问题）

适用场景

直接应用：

  • 组合优化：在约束下最大化配置数量
  • 编码理论：可能与码字分布有关
  • 游戏设计：单词搜索游戏的极限配置

理论工具：

  • 加法组合学研究者：新的极值问题类型
  • 傅里叶分析：具体的应用案例
  • 线性规划：局部方法的示范

教学价值：

  • 展示了多种技术的综合运用
  • 从简单到复杂的清晰进展
  • 大量具体例子适合讲解

未来研究：

  • 作为跳板研究相关极值问题
  • 测试新计算方法的平台
  • 与其他领域（如高阶傅里叶分析）的接口

参考文献

核心参考文献：

1 N. Alon and N. Kravitz. Cats in cubes. Electron. J. Combin., 31(3):Paper No. 3.29, 2024.

  • 本文的直接前驱，解决无重复字母情况

14 G. Patchell and S. Spiro. The maximum number of appearances of a word in a grid. Amer. Math. Monthly, 129(5):415–434, 2022.

  • 问题的原始提出

8 R. Greenfeld and T. Tao. A counterexample to the periodic tiling conjecture. Ann. of Math., 200(1):301–363, 2024.

  • 与问题2.5相关的重要反例

4 J. Bell and B. Stevens. A survey of known results and research areas for n-queens. Discrete Math., 309(1):1–31, 2009.

  • n皇后问题的全面综述

16 A. A. Razborov. Flag algebras. J. Symbolic Logic, 72(4):1239–1282, 2007.

  • 极值组合学的强大工具，与本文的线性规划方法相关

18 T. Tao. Higher order Fourier analysis. Graduate Studies in Mathematics, vol. 142, AMS, 2012.

  • 高阶傅里叶分析的标准参考，论文讨论了其潜在应用

总体评价：这是一篇优秀的组合数学论文，系统研究了一个自然且深刻的问题。通过发展多种互补技术，作者取得了实质性进展，特别是完全解决了一维情况并部分解决了二维短单词情况。论文揭示了与n皇后问题等经典问题的意外联系，提出了丰富的开放问题。主要局限在于计算复杂性限制了方法的可扩展性，以及对长单词和高维情况的理解仍然有限。尽管如此，本文为该领域奠定了坚实基础，其方法和结果将启发未来研究。