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

背景

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

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

$$\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\sum _{0\le k<n}f(\{k\alpha \})={\int }_0^{1}f(x)\mathrm{d}x$$

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

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

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

$$\sum _{0\le k<n}{f}_v(\{k\alpha \})=\sum _{0\le k<n}[\{k\alpha \}<v]$$

与定理所阐明的 $n\to \mathrm{\infty }$ 时的理想值：

$$n{\int }_0^1{f}_v(x)\mathrm{d}x=n{\int }_0^1[0\le x<v]\mathrm{d}x=nv$$

有多么接近。

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

推导

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

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

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

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

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

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

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

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

(1) $\{k\alpha \}<v$ 时，
$$\begin{array}{rl}& k\alpha -\lfloor k\alpha \rfloor <v\\ \iff & k\alpha -v<\lfloor k\alpha \rfloor \\ \iff & \lfloor k\alpha \rfloor -1\le k\alpha -v<\lfloor k\alpha \rfloor \\ \iff & \lfloor k\alpha -v\rfloor =\lfloor k\alpha \rfloor -1\\ \iff & \lfloor k\alpha \rfloor -\lfloor k\alpha -v\rfloor =1\end{array}$$

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

$$\begin{array}{rl}& k\alpha -\lfloor k\alpha \rfloor \ge v\\ \iff & k\alpha -v\ge \lfloor k\alpha \rfloor \\ \iff & \lfloor k\alpha \rfloor \le k\alpha -v<\lfloor k\alpha \rfloor +1\\ \iff & \lfloor k\alpha -v\rfloor =\lfloor k\alpha \rfloor \\ \iff & \lfloor k\alpha \rfloor -\lfloor k\alpha -v\rfloor =0\end{array}$$

故

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

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

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

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

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

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

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

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

即

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

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

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

$$\begin{array}{rl}& \sum _k[j{\alpha }^{-1}<k\le (j+v){\alpha }^{-1}]\\ =& \lceil (j+v){\alpha }^{-1}\rceil -\lceil j{\alpha }^{-1}\rceil \\ =& \lceil (j+v)(a+{\alpha }^{\prime })\rceil -\lceil j(a+{\alpha }^{\prime })\rceil \\ =& ja+\lceil j{\alpha }^{\prime }+v(a+{\alpha }^{\prime })\rceil -ja-\lceil j{\alpha }^{\prime }\rceil \\ =& \lceil j{\alpha }^{\prime }+v(a+{\alpha }^{\prime })\rceil -\lceil j{\alpha }^{\prime }\rceil \\ =& \lceil j{\alpha }^{\prime }+v{\alpha }^{-1}\rceil -\lceil j{\alpha }^{\prime }\rceil \\ =& \lceil j{\alpha }^{\prime }+b-v^{\prime }\rceil -\lceil j{\alpha }^{\prime }\rceil \\ =& b+\lceil j{\alpha }^{\prime }-v^{\prime }\rceil -\lceil j{\alpha }^{\prime }\rceil \end{array}$$

带入回原式：

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

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

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

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

对于 (2) 的证明：

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

$$j{\alpha }^{\prime }-v^{\prime }=n\in \mathbb{Z}$$

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

$$j=\frac{v^{\prime }+n}{{\alpha }^{\prime }}$$

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

$$j^{\prime }=\frac{v^{\prime }+n^{\prime }}{{\alpha }^{\prime }}=\frac{v^{\prime }+n+\mathrm{\Delta }n}{{\alpha }^{\prime }}=j+\frac{\mathrm{\Delta }n}{{\alpha }^{\prime }}$$

$$j\in \mathbb{Z},{\alpha }^{\prime }\in \mathbb{R}-\mathbb{Q},\mathrm{\Delta }n\in \mathbb{Z}\Rightarrow j^{\prime }\notin \mathbb{Z}$$

这与 $j^{\prime }\in \mathbb{Z}$ 矛盾。Q.E.D.

所以：

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

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

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

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

$$\begin{array}{rl}s({\alpha }^{\prime },\lceil n\alpha \rceil ,v^{\prime })& =\sum _{0\le j<\lceil n\alpha \rceil }(\lfloor j{\alpha }^{\prime }\rfloor -\lfloor j{\alpha }^{\prime }-v^{\prime }\rfloor -v^{\prime })\\ & =-\lceil n\alpha \rceil v^{\prime }+\sum _{0\le j<\lceil n\alpha \rceil }(\lfloor j{\alpha }^{\prime }\rfloor -\lfloor j{\alpha }^{\prime }-v^{\prime }\rfloor )\end{array}$$

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

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

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

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

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

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

(1) $ϵ$ 的上界：

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

(2) $S$ 的范围：

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

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

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

故

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

有

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

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

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

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

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

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

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

$$\begin{array}{rl}s(\alpha ,n,v)& =-s({\alpha }^{\prime },\boxed{{\displaystyle \lceil n\alpha \rceil }},v^{\prime })-S+ϵ+\{0\text{ or }1\}\\ & \le -s({\alpha }^{\prime },\lfloor n\alpha \rfloor ,v^{\prime })+v^{\prime }\boxed{{\displaystyle -S}}+ϵ+\{0\text{ or }1\}\\ & \le -s({\alpha }^{\prime },\lfloor n\alpha \rfloor ,v^{\prime })+v^{\prime }+\boxed{{\displaystyle ϵ}}+\{0\text{ or }1\}\\ & \le -s({\alpha }^{\prime },\lfloor n\alpha \rfloor ,v^{\prime })+v^{\prime }+\frac{v}{\alpha }+\boxed{{\displaystyle \{0\text{ or }1\}}}\\ & \le -s({\alpha }^{\prime },\lfloor n\alpha \rfloor ,v^{\prime })+\boxed{{\displaystyle v^{\prime }+\frac{v}{\alpha }}}+1\\ & \le -s({\alpha }^{\prime },\lfloor n\alpha \rfloor ,v^{\prime })+\boxed{{\displaystyle \lceil v{\alpha }^{-1}\rceil }}+1\\ & \le -s({\alpha }^{\prime },\lfloor n\alpha \rfloor ,v^{\prime })+\boxed{{\displaystyle \lceil {\alpha }^{-1}\rceil }}+1\\ & \le \boxed{{\displaystyle -s({\alpha }^{\prime },\lfloor n\alpha \rfloor ,v^{\prime })}}+{\alpha }^{-1}+2\\ & \le |s({\alpha }^{\prime },\lfloor n\alpha \rfloor ,v^{\prime })|+{\alpha }^{-1}+2\end{array}$$

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

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

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

$$\begin{array}{rl}D(\alpha ,n)& =\underset{v}{max}|s(\alpha ,n,v)|\\ & \le |s({\alpha }^{\prime },\lfloor n\alpha \rfloor ,v^{\prime })|+{\alpha }^{-1}+2\\ & \le \underset{v^{\prime }}{max}|s({\alpha }^{\prime },\lfloor n\alpha \rfloor ,v^{\prime })|+{\alpha }^{-1}+2\\ & =D({\alpha }^{\prime },\lfloor n\alpha \rfloor )+{\alpha }^{-1}+2\end{array}$$

Q.E.D.

思考

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

补充

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

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

$$\begin{array}{rl}-s(\alpha ,n,v)& =s({\alpha }^{\prime },\lceil n\alpha \rceil ,v^{\prime })+S-ϵ-\{0\text{ or }1\}\\ & \ge s({\alpha }^{\prime },\lceil n\alpha \rceil ,v^{\prime })+0-ϵ-1\\ & \ge s({\alpha }^{\prime },\lfloor n\alpha \rfloor ,v^{\prime })-v^{\prime }-ϵ-1\\ & \ge s({\alpha }^{\prime },\lfloor n\alpha \rfloor ,v^{\prime })-{\alpha }^{-1}-2\end{array}$$

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

故

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

$$\iff s({\alpha }^{\prime },\lfloor n\alpha \rfloor ,v^{\prime })\le |s(\alpha ,n,v)|+{\alpha }^{-1}+2$$

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

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

即

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

最后再进行一下放缩：

$$\begin{array}{rl}D({\alpha }^{\prime },\lfloor n\alpha \rfloor )& =\underset{v^{\prime }}{max}|s({\alpha }^{\prime },\lfloor n\alpha \rfloor ,v^{\prime })|\\ & \le |s(\alpha ,n,v)|+{\alpha }^{-1}+2\\ & \le \underset{v}{max}|s(\alpha ,n,v)|+{\alpha }^{-1}+2\\ & =D(\alpha ,n)+{\alpha }^{-1}+2\end{array}$$

即

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

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

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