Balanced rectangles over Sturmian words and minimal discrepancy intervals

这是一份关于论文《Balanced Rectangles over Sturmian Words and Minimal Discrepancy Intervals》（Sturmian 词上的平衡矩形与最小偏差区间）的详细技术总结。

1. 研究背景与问题定义

背景：
Sturmian 词是一类重要的无限二元序列，具有许多优美的组合和数论性质。其中一个基本性质是“平衡性”（balancedness）：对于任意固定长度的因子（连续子串），其中 1 的个数（权重）最多相差 1。
然而，当将 Sturmian 词推广到二维（即由 Sturmian 词生成的无限汉克尔矩阵 $A$ 中的 $m \times n$ 子矩阵）时，情况变得复杂。Berthé 和 Tijdeman 曾证明，在维度大于 1 时，只有周期性的词才是完全平衡的。因此，研究者关注的是：在什么条件下，Sturmian 词生成的特定大小的 $m \times n$ 矩形是“平衡”的？

问题定义：
设 $a$ 是斜率为 $\alpha$（无理数）的 Sturmian 词。定义 $A(i, m, n)$ 为从索引 $i$ 开始的 $m \times n$ 子矩阵。

• 平衡矩形：如果存在整数 $c$，使得对于所有起始位置 $i \ge 1$，矩阵 $A(i, m, n)$ 中所有元素之和 $T(i, m, n)$ 仅取两个值 $\{c, c+1\}$，则称该 $m \times n$ 矩形是平衡的。
• 目标：对于任意无理斜率 $\alpha$（不仅仅是二次无理数），完全刻画使得 $m \times n$ 矩形平衡的整数对 $(m, n)$ 的充要条件。

现有工作局限：
之前的研究（如 Anselmo 等，Shallit 和作者）主要针对斐波那契词或斜率为二次无理数的情况，利用 Zeckendorf 表示或自动机（如 Walnut 软件）进行刻画。这些方法依赖于 $\alpha$ 的连分数展开是最终周期的这一性质，无法推广到所有无理数。

2. 方法论

本文提出了一种基于丢番图逼近（Diophantine approximation）和模 1 分布（distribution modulo 1）的新方法，不依赖于 $\alpha$ 是否为二次无理数。

核心思路：

1. 从矩形到区间：
   利用 Sturmian 词的定义 $a_n = \lfloor (n+1)\alpha + \theta \rfloor - \lfloor n\alpha + \theta \rfloor$，将矩形权重的求和转化为对点集 $\{k\alpha\} \pmod 1$ 在特定区间内计数的求和。
   定理 3.1 建立了关键等价关系：$m \times n$ 矩形平衡 $\iff$ 长度为 $\{n\alpha\}$ 的区间在点集 $\{0, \alpha, \dots, (m-1)\alpha\}$ 上是平衡的（即区间内包含的点数仅取两个连续整数值）。

2. 从区间到双射性：
   为了判断区间是否平衡，作者引入了映射 $f_{left}$ 和 $f_{right}$，分别将索引 $\ell$ 映射到点集 $B=\{\{0\}, \dots, \{(m-1)\alpha\}\}$ 中位于区间右端点 $\{(\ell+n)\alpha\}$ 左侧和右侧最近的点的索引。
   引理 4.3 指出：在一般位置假设下，区间平衡 $\iff$ 映射 $f_{left}$（或 $f_{right}$）是双射。

3. Ostrowski 表示的应用：
   为了分析 $f_{left}$ 和 $f_{right}$ 的双射性，作者利用 Ostrowski 表示（基于 $\alpha$ 的连分数分母 $q_k$ 的表示法）来刻画整数 $m$ 和 $n$ 的结构。

   • 通过分析 $n\alpha \pmod 1$ 的分布性质，特别是 $n$ 在 Ostrowski 表示中的数字（digits）大小和位置，来确定 $x_{left}(\ell)$ 和 $x_{right}(\ell)$ 的行为。
   • 利用连分数收敛项（convergents）和半收敛项（semi-convergents）的最佳逼近性质，推导出 $m$ 和 $n$ 必须满足的特定代数结构。

3. 主要结果

论文给出了 $m \times n$ 矩形平衡的完全刻画（Theorem 2.1）。假设 $2 \le m \le n$，且 $m, n$ 关于 $\alpha$ 的 Ostrowski 表示分别为 $m = \sum b_k q_k$ 和 $n = \sum b'_k q_k$。矩形平衡当且仅当 $(m, n)$ 满足以下四种形态之一（或它们的组合）：

1. 分裂表示（Split Representations）：

   • (i) $m$ 仅包含低阶项（索引 $0$到$M$），$n$仅包含高阶项（索引$M+1$及以上）。即$m = \sum_{k=0}^M b_k q_k$, $n = \sum_{k=M+1}^N b_k q_k$。
   • (ii) $m$ 仅包含低阶项，$n$ 的首项是某个 $q_M$，且后续项的索引间隔为偶数（$M+1+2t$）。即 $n = q_M + \sum_{k=M+1+2t} b_k q_k$。
   • 直观理解：这种情况下，区间长度 $\{n\alpha\}$ 极短（或极长），导致区间内包含的点数极少（0 或 1 个），自然平衡。

2. 收敛项/半收敛项情形：

   • (iii) $m$ 是某个收敛项的分母 $q_M$，$n$ 由低阶项和高阶项（索引 $M+2t$）组成。
   • (iv) $m$ 是某个半收敛项（$q_{M-1} + a q_M$），$n$ 由低阶项和高阶项（索引 $M+1+2t$）组成。
   • 直观理解：这种情况下，点集 $\{k\alpha\}$ 分布非常均匀，且区间长度与点间距有特定的匹配关系，使得点数波动被控制在 1 以内。

关键创新点：

• 该结果推广了之前仅针对二次无理数（如斐波那契词）的结论，适用于所有无理斜率 $\alpha$。
• 刻画条件完全基于 $m$ 和 $n$ 的 Ostrowski 表示，这是处理一般无理数连分数性质的自然语言。

4. 技术细节与证明逻辑

• Ostrowski 表示的性质：论文详细回顾了 Ostrowski 表示中数字的约束规则（如 $b_k \le a_{k+1}$ 且若 $b_k = a_{k+1}$ 则 $b_{k-1}=0$），并证明了这些数字如何决定 $\{n\alpha\}$ 在 $[0,1)$ 中的位置及其与最近整数的距离。
• 最小偏差分析：通过引理 5.1-5.17，作者建立了 $n$ 的 Ostrowski 表示与其模 1 距离 $\|n\alpha\|$ 之间的精确不等式关系。特别是，当 $n$ 的表示中“高位”数字较大时，$\{n\alpha\}$ 会非常接近 0 或 1。
• 双射性的判定：
  • 如果 $n$ 的表示使得 $\{n\alpha\}$ 极小（对应情形 i, ii），则 $f_{left}$ 是恒等映射或简单的移位，显然是双射。
  • 如果 $m$ 是收敛项（$q_M$），点集 $\{k\alpha\}$ 在 $[0,1)$ 上几乎均匀分布。此时 $f_{left}$ 的双射性取决于 $n$ 的表示中高位数字的奇偶性（parity restrictions），这对应于情形 (iii) 和 (iv)。
  • 通过反证法，证明了如果 $m, n$ 不满足上述形态，则 $f_{left}$ 或 $f_{right}$ 必然不是双射（即存在两个不同的 $\ell$ 映射到同一个目标，或者存在“空隙”），从而导致矩形不平衡。

5. 意义与贡献

1. 理论突破：彻底解决了 Sturmian 词二维平衡性的分类问题，去除了对斜率 $\alpha$ 为二次无理数的限制。这是该领域的一个重要进展。
2. 方法创新：成功将组合数学中的平衡性问题转化为数论中的最小偏差区间（minimal discrepancy intervals）问题，并利用 Ostrowski 表示这一强有力的工具进行精确刻画。这种方法比之前的自动机方法（Walnut）更具普适性和理论深度。
3. 统一框架：提供了一个统一的框架来理解不同斜率下的平衡现象，揭示了 Ostrowski 表示在描述 Sturmian 词几何性质中的核心作用。
4. 应用潜力：该结果加深了对低偏差序列、准晶格（quasicrystals）以及动力系统（如旋转映射）中点分布规律的理解。

总结：
Ingrid Vukusic 的这篇论文通过巧妙的数论转换，利用 Ostrowski 表示法，给出了 Sturmian 词生成的 $m \times n$ 矩形平衡性的完整且通用的充要条件。这不仅推广了前人的特定结果，还建立了一个连接组合词、丢番图逼近和偏差理论的坚实桥梁。