注：本节内容为《具体数学》(原书第二版) 第三章 整值函数 3.5节 顶和底的和式的旁注。

背景

在 3.5 节底和顶的和式中，作者介绍了定理：

如果 $\alpha$ 是无理数，那么分数部分 $\{n\alpha\}$ 当 $n \rightarrow \infty$ 时在 $0$ 和 $1$ 之间是非常一致分布的。即对于无理数 $\alpha$ 以及所有处处连续的有界函数 $f$ 有

$$
\lim _ {n \rightarrow \infty} \frac 1 n \sum _ {0 \leq k < n} f(\{k\alpha\}) = \int_0^1 f(x) \mathrm dx
$$

书中为了展示这个定理的意义以及正确性，研究特殊情况：令

$$
f(x) = f_v (x) = [0 \leq x < v], ~0 \leq v \leq 1
$$

来研究当 $n$ 很大且 $\alpha$ 为无理数的情况下，和式

$$
\sum _ {0 \leq k < n} f_v(\{k\alpha\}) = \sum _ {0 \leq k < n} [\{k\alpha\} < v]
$$

与定理所阐明的 $n \rightarrow \infty$ 时的理想值：

$$
n \int_0^1 f_v(x) \mathrm dx = n \int_0^1 [0 \leq x < v] \mathrm dx = nv
$$

有多么接近。

然而书上的过程十分简略，看的时候令我十分头大，故专门撰写此文来完善推导。

推导

首先定义下面的函数 $s(\alpha, n, v)$:

$$
s(\alpha, n, v) = \sum _ {0 \leq k < n} ([\{k\alpha\} < v] - v)
$$

其描述的是代求和式与理想值之间的差。所以我们定义其最大的绝对值 $D(\alpha, n)$ 作为偏差 (Discrepancy)：

$$
D(\alpha, n) = \max _{0 \leq v \leq 1} |s(\alpha, n, v)|
$$

我们的目的是通过证明当 $\alpha$ 为无理数时，$D(\alpha, n)$ 总是 适当地 小，从而证明 $D(\alpha, n)$ 与 $n$ 相比 不太大。不失一般性，我们假设 $0 < \alpha < 1$。

首先我们可以将 $s(\alpha, n, v)$ 改写成简单的形式:

$$
\begin{aligned}
s(\alpha, n, v) &= \sum _ {0 \leq k < n} ([\{k\alpha\} < v] - v) \\
&= \sum _ {0 \leq k < n} (\lfloor k\alpha \rfloor - \lfloor k\alpha - v \rfloor - v)
\end{aligned}
$$

上一步的理由如下：讨论：

(1) $\{k \alpha \} < v$ 时，
$$
\begin{aligned}
& k\alpha - \lfloor k\alpha \rfloor < v \\
\Leftrightarrow & k\alpha - v < \lfloor k\alpha \rfloor \\
\Leftrightarrow & \lfloor k\alpha \rfloor - 1 \leq k\alpha - v < \lfloor k\alpha \rfloor \\
\Leftrightarrow & \lfloor k\alpha - v \rfloor = \lfloor k\alpha \rfloor - 1 \\
\Leftrightarrow & \lfloor k\alpha \rfloor - \lfloor k\alpha - v \rfloor = 1 \\
\end{aligned}
$$

(2) $\{k \alpha \} \geq v$ 时，

$$
\begin{aligned}
& k\alpha - \lfloor k\alpha \rfloor \geq v \\
\Leftrightarrow & k\alpha - v \geq \lfloor k\alpha \rfloor \\
\Leftrightarrow & \lfloor k\alpha \rfloor \leq k\alpha - v < \lfloor k\alpha \rfloor + 1 \\
\Leftrightarrow & \lfloor k\alpha - v \rfloor = \lfloor k\alpha \rfloor \\
\Leftrightarrow & \lfloor k\alpha \rfloor - \lfloor k\alpha - v \rfloor = 0 \\
\end{aligned}
$$

故

$$
[\{k\alpha\} < v] = \lfloor k\alpha \rfloor - \lfloor k\alpha - v \rfloor
$$

然后引入一个新的指标变量 $j$：

$$
\begin{aligned}
& \sum _ {0 \leq k < n} (\lfloor k\alpha \rfloor - \lfloor k\alpha - v \rfloor - v) \\
=& -nv + \sum _ {0 \leq k < n} \sum _ {j {\color{pink}{\in \mathbb Z}}} [k\alpha - v < j \leq k \alpha]
\end{aligned}
$$

接下来交换求和顺序。注意：因为 $\alpha \in \mathbb R - \mathbb Q, n \in \mathbb Z$，所以 $n\alpha$ 同样为无理数，由此来确定求和上下界。

$$
\begin{aligned}
=& -nv + \sum _ {0 \leq k < n} \sum _ {j {\color{pink}{\in \mathbb Z}}} [k\alpha - v < j \leq k \alpha] \\
=& -nv + \sum _ {0 \leq j < \lceil n\alpha \rceil} \sum _ {k < n} [k\alpha - v < j \leq k \alpha] \\
=& -nv + \sum _ {0 \leq j < \lceil n\alpha \rceil} \sum _ {k < n} [j\alpha ^ {-1} < k \leq (j + v) \alpha ^ {-1}] \\
\end{aligned}
$$

为了让式子不至于太过凌乱，引入新记号：

$$
a = \lfloor \alpha ^ {-1} \rfloor, \alpha' = \alpha ^ {-1} - a
$$

$$
b = \lceil v \alpha ^ {-1} \rceil, v' = b - v \alpha ^ {-1}
$$

即

$$
\alpha' = \{ \alpha ^ {-1} \}
$$

$$
v' = v \alpha ^ {-1} ~~\text{mumble} ~~ 1
$$

边界条件就是灾难之源，所以我们不妨先忽略 $k < n$，先专注于求解

$$
\begin{aligned}
&\sum _ k [j\alpha ^ {-1} < k \leq (j + v) \alpha ^ {-1}] \\
=& \lceil (j+v)\alpha ^ {-1} \rceil - \lceil j\alpha ^ {-1} \rceil \\
=& \lceil (j+v)(a + \alpha') \rceil - \lceil j(a + \alpha') \rceil \\
=& ja + \lceil j\alpha'+v(a + \alpha') \rceil - ja - \lceil j\alpha' \rceil \\
=& \lceil j\alpha'+v(a + \alpha') \rceil - \lceil j\alpha' \rceil \\
=& \lceil j\alpha'+v\alpha ^ {-1} \rceil - \lceil j\alpha' \rceil \\
=& \lceil j\alpha'+b - v' \rceil - \lceil j\alpha' \rceil \\
=& b + \lceil j\alpha' - v' \rceil - \lceil j\alpha' \rceil \\
\end{aligned}
$$

带入回原式：

$$
s(\alpha, n, v) = -nv + \lceil n\alpha \rceil b + \sum _ {0 \leq j < \lceil n\alpha \rceil} (\lceil j\alpha' - v' \rceil - \lceil j\alpha' \rceil) - S
$$

其中，$S$ 是对我们未能排除掉的 $k \geq n$ 的情况所做的修正。接下来，我们想将向上取整转换为向下取整，我们来考察这两个取整式：

(1) 对于 $\lceil j\alpha' \rceil$: 由于 $\alpha$ 为无理数，显然 $\alpha '$ 也为无理数，所以当且仅当 $j = 0$ 有 $j\alpha' = \lceil j\alpha' \rceil$

(2) 对于 $\lceil j\alpha' - v' \rceil$: 给定 $\alpha', v'$ 的情况下，我们至多找得到 一个$j \in \mathbb Z$ 使得 $j\alpha' - v'$ 为整数，即 $j\alpha' - v' = \lceil j\alpha' - v' \rceil$.

对于 (2) 的证明：

假设我们已经找到一个 $j \in \mathbb Z$，使得

$$
j\alpha' - v' = n \in \mathbb Z
$$

进行一下简单的代数变换：

$$
j = \frac {v' + n} {\alpha'}
$$

如果这样的 $j$ 不止一个，那么我们一定会产生一个新的 $n' \in \mathbb Z$ (因为 $\alpha' \neq 0$)，所以有：

$$
j' = \frac {v' + n'} {\alpha'} = \frac {v' + n + \Delta n} {\alpha'} = j + \frac {\Delta n} {\alpha'}
$$

$$
j \in \mathbb Z, \alpha' \in \mathbb R - \mathbb Q, \Delta n \in \mathbb Z \Rightarrow j' \notin \mathbb Z
$$

这与 $j' \in \mathbb Z$ 矛盾。Q.E.D.

所以：

$$
\begin{aligned}
s(\alpha, n, v) &= -nv + \lceil n\alpha \rceil b + \sum _ {0 \leq j < \lceil n\alpha \rceil} (\lceil j\alpha' - v' \rceil - \lceil j\alpha' \rceil) - S \\
&= -nv + \lceil n\alpha \rceil b + \sum _ {0 \leq j < \lceil n\alpha \rceil} (\lfloor j\alpha' - v' \rfloor + 1 - \lfloor j\alpha' \rfloor - 1) - S + \{0 \text{ or } 1\} \\
&= -nv + \lceil n\alpha \rceil b - \sum _ {0 \leq j < \lceil n\alpha \rceil} (\lfloor j\alpha' \rfloor - \lfloor j\alpha' - v' \rfloor) - S + \{0 \text{ or } 1\}
\end{aligned}
$$

看起来我们得到了很有意思的东西，并不是封闭形式，而像是递归式。回忆一下，我们有：

$$
s(\alpha, n, v) = \sum _ {0 \leq k < n} (\lfloor k\alpha \rfloor - \lfloor k\alpha - v \rfloor - v)
$$

这里我们更换一下参数，就会发现其与我们得到的式子中的和式非常相似！

$$
\begin{aligned}
s(\alpha', \lceil n\alpha \rceil, v') &= \sum _ {0 \leq j < \lceil n\alpha \rceil} (\lfloor j\alpha' \rfloor - \lfloor j\alpha' - v' \rfloor - v') \\
&= - \lceil n\alpha \rceil v' + \sum _ {0 \leq j < \lceil n\alpha \rceil} (\lfloor j\alpha' \rfloor - \lfloor j\alpha' - v' \rfloor)
\end{aligned}
$$

带入回 $s(\alpha, n, v)$，我们可以得到：

$$
\begin{aligned}
s(\alpha, n, v) &= -nv + \lceil n\alpha \rceil b - \lceil n\alpha \rceil v' - s(\alpha', \lceil n\alpha \rceil, v') - S + \{0 \text{ or } 1\} \\
&= -nv + \lceil n\alpha \rceil (b - v') - s(\alpha', \lceil n\alpha \rceil, v') - S + \{0 \text{ or } 1\} \\
&= -nv + \boxed{\lceil n\alpha \rceil v\alpha ^ {-1}} - s(\alpha', \lceil n\alpha \rceil, v') - S + \{0 \text{ or } 1\}
\end{aligned}
$$

观察框出来的地方：假如我们能将 $\lceil n\alpha \rceil$ 替换为 $n\alpha$，一切都可以变得简洁，前面的项会全部被抵消:

$$
s(\alpha, n, v) = -s(\alpha', \lceil n\alpha \rceil, v') - S + \epsilon + \{0 \text{ or } 1\}
$$

其中，$\epsilon$ 为这样做的正误差。

接下来，我要在这里求出并证明 $\epsilon$ 和 $S$ 的上界。此处包含了习题 18 的内容。

(1) $\epsilon$ 的上界：

$$
0 < \epsilon = (\lceil n\alpha \rceil - n\alpha) v\alpha ^ {-1} < v\alpha ^ {-1}
$$

(2) $S$ 的范围：

$$
S = \sum _{0 \leq j < \lceil n\alpha \rceil} \sum _ k [n \leq k < (j + v) \alpha ^ {-1}]
$$

当 $j \leq \lceil n\alpha \rceil - 2$ 时

$$
\frac {j + v} {\alpha} \leq \frac {\lceil n\alpha \rceil - 2 + v} {\alpha} \leq \frac {\lceil n\alpha \rceil - 1} {\alpha} < \frac {(n\alpha + 1) - 1} {\alpha} = n
$$

故

$$
\sum _{0 \leq j < \lceil n\alpha \rceil - 1} \sum _ k [n \leq k < (j + v) \alpha ^ {-1}] = 0
$$

有

$$
\begin{aligned}
0 \leq S &= \sum _{j = \lceil n\alpha \rceil - 1} \sum _ k [n \leq k < (j + v) \alpha ^ {-1}] \\
&= \sum _ k [n \leq k < \frac {\lceil n\alpha \rceil - 1 + v} {\alpha}] \\
&= \Big \lceil \frac {\lceil n\alpha \rceil - 1 + v} {\alpha} \Big \rceil - n \\
&= \Big \lceil \frac {\lceil n\alpha \rceil - n\alpha - 1 + v} {\alpha} \Big \rceil \\
&< \Big \lceil \frac {1 - 1 + v} {\alpha} \Big \rceil = \Big \lceil \frac {v} {\alpha} \Big \rceil
\end{aligned}
$$

结束了 $\epsilon$ 和 $S$ 上界的讨论，我们继续看我们得到的递归式：

$$
s(\alpha, n, v) = -s(\alpha', \lceil n\alpha \rceil, v') - S + \epsilon + \{0 \text{ or } 1\}
$$

注意到：$s(\alpha', \lceil n\alpha \rceil, v')$ 的最后一项 $j = \lceil n\alpha \rceil - 1 = \lfloor n\alpha \rfloor$，这一项对答案的贡献为 $v'$ 或 $v' - 1$，因为我们可以看回没有经过任何变形的原式（用 $j$ 替换了原来的 $k$）：

$$
s(\alpha, n, v) = \sum _ {0 \leq j < n} ([\{j\alpha\} < v] - v)
$$

对于每一项，答案只可能为 $0-v$ 或者 $1-v$，由于这里的 $s(\alpha', \lceil n\alpha \rceil, v')$ 前有符号，所以这一项对答案的贡献只可能为 $-(-v') = v'$ 或 $-(1-v') = v'-1$。

接下来，我们便可以开始进行放缩了：

$$
\begin{aligned}
s(\alpha, n, v) &= -s(\alpha', \boxed{\lceil n\alpha \rceil}, v') - S + \epsilon + \{0 \text{ or } 1\} \\
&\leq -s(\alpha', \lfloor n\alpha \rfloor, v') + v' \boxed{- S} + \epsilon + \{0 \text{ or } 1\} \\
&\leq -s(\alpha', \lfloor n\alpha \rfloor, v') + v' + \boxed{\epsilon} + \{0 \text{ or } 1\} \\
&\leq -s(\alpha', \lfloor n\alpha \rfloor, v') + v' + \frac {v} {\alpha} + \boxed{\{0 \text{ or } 1\}} \\
&\leq -s(\alpha', \lfloor n\alpha \rfloor, v') + \boxed{v' + \frac {v} {\alpha}} + 1 \\
&\leq -s(\alpha', \lfloor n\alpha \rfloor, v') + \boxed{\lceil v\alpha ^ {-1} \rceil} + 1 \\
&\leq -s(\alpha', \lfloor n\alpha \rfloor, v') + \boxed{\lceil \alpha ^ {-1} \rceil} + 1 \\
&\leq \boxed{-s(\alpha', \lfloor n\alpha \rfloor, v')} + \alpha ^ {-1} + 2 \\
&\leq |s(\alpha', \lfloor n\alpha \rfloor, v')| + \alpha ^ {-1} + 2
\end{aligned}
$$

由于 $|s(\alpha', \lfloor n\alpha \rfloor, v')| + \alpha ^ {-1} + 2 > 0$ ，所以我们可以将不等式左边也写成绝对值的形式：

$$
|s(\alpha, n, v)| \leq |s(\alpha', \lfloor n\alpha \rfloor, v')| + \alpha ^ {-1} + 2
$$

我们已经离目标很近了！我们可以再进行一次缩放：

$$
\begin{aligned}
D(\alpha, n) &= \max _ v |s(\alpha, n, v)| \\
&\leq |s(\alpha', \lfloor n\alpha \rfloor, v')| + \alpha ^ {-1} + 2 \\
&\leq \max _ {v'} |s(\alpha', \lfloor n\alpha \rfloor, v')| + \alpha ^ {-1} + 2 \\
&=D(\alpha', \lfloor n\alpha \rfloor) + \alpha ^ {-1} + 2
\end{aligned}
$$

Q.E.D.

思考

这个过程中，我们用到了大量的放缩技巧。最后得到了一个关于 $D$ 的递推不等式链。思考一下这个式子到底说明了什么：由于 $\lfloor n\alpha \rfloor$ 总是小于 $n$，所以当 $n$ 充分大的时候，$D(\alpha, n)$ 总是比 $n$ 要小得多。从而说明了定理在这种特殊情况下，即 $f_v$ 阶梯函数作为映射关系时的正确性。

补充

接下来，我们还证明一下 习题 29，也就是这个推导中的补充结论。

首先变换递推式，然后进行放缩：

$$
\begin{aligned}
-s(\alpha, n, v) &= s(\alpha', \lceil n\alpha \rceil, v') + S - \epsilon - \{0 \text{ or } 1\} \\
&\geq s(\alpha', \lceil n\alpha \rceil, v') + 0 - \epsilon - 1 \\
&\geq s(\alpha', \lfloor n\alpha \rfloor, v') - v' - \epsilon - 1 \\
&\geq s(\alpha', \lfloor n\alpha \rfloor, v') - \alpha ^ {-1} - 2
\end{aligned}
$$

注：由于和上面的相似，所以包含了大量的跳步。

故

$$
|s(\alpha, n, v)| \geq -s(\alpha, n, v) \geq s(\alpha', \lfloor n\alpha \rfloor, v') - \alpha ^ {-1} - 2
$$

$$
\Leftrightarrow s(\alpha', \lfloor n\alpha \rfloor, v') \leq |s(\alpha, n, v)| + \alpha ^ {-1} + 2
$$

又 $|s(\alpha, n, v)| + \alpha ^ {-1} + 2 > 0$，故

$$
|s(\alpha', \lfloor n\alpha \rfloor, v')| \leq |s(\alpha, n, v)| + \alpha ^ {-1} + 2
$$

即

$$
|s(\alpha, n, v)| \geq |s(\alpha', \lfloor n\alpha \rfloor, v')| - \alpha ^ {-1} - 2
$$

最后再进行一下放缩：

$$
\begin{aligned}
D(\alpha',\lfloor n\alpha \rfloor) &= \max_{v'} |s(\alpha', \lfloor n\alpha \rfloor, v')| \\
&\leq |s(\alpha, n, v)| + \alpha ^ {-1} + 2 \\
&\leq \max_v |s(\alpha, n, v)| + \alpha ^ {-1} + 2 \\
&= D(\alpha, n) + \alpha ^ {-1} + 2
\end{aligned}
$$

即

$$
D(\alpha, n) \geq D(\alpha',\lfloor n\alpha \rfloor) - \alpha ^ {-1} - 2
$$

结合上面的结论，我们得到了：

$$
D(\alpha',\lfloor n\alpha \rfloor) - \alpha ^ {-1} - 2 \leq D(\alpha, n) \leq D(\alpha', \lfloor n\alpha \rfloor) + \alpha ^ {-1} + 2
$$