动机
平方根的连分数常常从某处开始重复。例如,二的平方根中重复出现的数字二是精确的算术事实,而不是从很长的小数展开中推测出来的数值规律。我们希望给出一个证明,既解释为什么会出现重复,也解释为什么一个重复的连分数必然表示二次无理数。
这里有两种不同的机制。一个重复的块是一个整系数分式线性变换,它的不动点满足一个二次方程。反方向上,二次无理数具有整数根式坐标,但这些坐标起初并没有界。我们先证明它的共轭完全商会进入某个区间;只有这样,坐标才落在一个有限集合中。保持这一顺序,可以避免作出“无穷连分数由递推生成,所以必然最终重复”这种缺乏依据的断言。
本文使用渐近分数与完全商公式。这里的数都是实数。连分数是简单连分数:首项是整数,之后每个数字都是正整数。全文所说的取整判定都是精确的,而不是浮点舍入。
定义
定义 11.2.1
(完全商与简约二次无理数)
对于无理数 ,令 ,,。则对 有 。如果连分数的数字从某个下标起开始重复,则称它最终周期;如果从下标零起就重复,则称它纯周期。
实二次无理数是某个二次整系数多项式的无理根。它的另一个根称为共轭,记作 。当 且 时,称该二次无理数是简约的。共轭保持有理数不变,并把其二次域中的正平方根映为负平方根。
定理
定理 11.2.2
(最终周期性刻画实二次无理数)
一个无理实数的简单连分数最终周期,当且仅当它是二次的。重复可以通过某个完全商的重复来精确检测;对于二次无理数,还可以通过某个整数根式状态的重复来检测。
定理 11.2.3
(简约给出有限且可逆的状态系统)
每个二次无理数从某个下标起,其完全商都是简约的。一个二次无理数的简单连分数是纯周期的,当且仅当它是简约的。对于表示
这里 为正的非平方整数。每个简约状态都满足 及 。完全商映射在固定 的简约整数状态这一有限集合上是一个置换。
证明思路
周期块给出二次不动点
证明
(块矩阵的不动点)
运算 的矩阵是 ,行列式为 。始于首项之后的周期只使用正数字。设其乘积为 。它的左下角元素 为正:长度为一的块显然如此,而再乘以一个由正数字构成的矩阵,所需元素的正性得以保持。因此,处于周期起点的完全商 满足
重复尾部的相等性来自无穷简单连分数的唯一性。原来的 是 的分式线性表达式,其系数为整数、行列式为 ,这是在前面接上有限前缀得到的。这样的变换及其逆变换都保持有理性。因此 是无理数,上面所示的多项式次数为二,而 属于同一个二次域,是二次的。如果重复从零开始,则先转到后面的某个完全商;这样就不必对初始数字的符号作任何假设。
把每个二次无理数写成整数根式坐标
证明
(整数根式递推)
设 是整系数方程且 。其判别式 为正且非平方;否则它的根就不会是实无理数。根据所取的根,二次公式把 写成 ,其中 ,或 。两种情形下 都整除 。开始时允许 为负。
对下一个完全商做有理化,得到精确的递推式
整除性假设使 成为整数:模 有 。同一个显式等式也给出新的整除条件。它的分子非零,因为 不是平方数。于是递推在整数坐标中持续进行,但仅凭这一观察还不能说明状态集合是有限的。
共轭最终必须变为负数
证明
(后期的共轭落在 内)
令 ;共轭给出 。没有任何 是有理数。一旦在某个下标 处有 ,则由于 ,下一个 严格位于 与零之间。这个区间随后被保持。
反之,假设对所有 , 都保持为正。下一项为正迫使 ,再下一项为正又迫使 。因此 在每个下标处都与 有相同的简单连分数数字 。于是 与 会有完全相同的无穷多个数字,从而必须相等,这与二次共轭矛盾。
为完整起见,这里用到的唯一性并不依赖小数展开。一个有限的正数字前缀把尾部 映入一个区间,其端点是该前缀的渐近分数与尾部取一时的值。行列式恒等式表明该区间长度至多为 ,其中 是最后一个渐近分数的分母。这些分母无界增长,因为它们的递推是在前一个分母的正整数倍上再加上一项。因此,共享所有前缀的两个数之间的距离为零。这一论证同样适用于被设想具有所有这些正尾部的共轭。
证明透视
有限性在周期性论证中的位置
整数坐标给出一个离散集合,但还不是有界集合。共轭为负使状态成为简约状态。简约状态所满足的不等式再对两个整数坐标加以界定。最后,一个重复的状态给出完全相同的后续状态,因为下一个数字恰好是所表示的数的精确取整。每一步都提供了前一步所没有的条件;仅凭离散性无法确立重复。
简约坐标有界,因而最终重复
证明
(简约坐标有界)
对于简约状态 与 ,差 为正,所以 。不等式 与 给出 以及 。此外 。因此,即使还没有施加整除性或其余不等式 ,可能的整数对 也只有有限多个。
由前面的共轭论证,所有足够靠后的状态都是简约的。因此其中有两个状态具有相同的数对。递推(包括其中的取整判定)是确定性的,所以它们此后的状态与数字永远重复。这就证明了二次无理数蕴含最终周期,并且无需估计简约从何时开始。
为什么简约的起点没有非周期前缀
证明
(简约状态的一个置换)
对固定的 ,考虑所有满足所述整除条件及两个简约不等式的整数状态。我们已经证明这个有限集合被映入自身。它还具有唯一的简约前驱。
事实上,若 是简约的且其共轭为 ,则其前一个完全商必为 ,其共轭为 。要求 ,便确定了
端点不是整数,因为 是无理数。这个 还给出 及 。该前驱属于同一个整数状态集合:取 及 。则 是正整数,直接有理化得 ,且 整除 。它的简约不等式已经内置于 的选取之中。唯一性来自同一个共轭区间。因此该映射是有限集合上的置换,所以每个简约的起始状态从其第一步起就是周期的。
反之,纯周期无理数的首项为正:否则,其重复的首项会在更靠后的下标处违背正性。因此它大于一。它的完全商序列与共轭序列都是周期的,而后者最终落在 中。周期性把这一区间条件带回到初始共轭。这就证明了纯周期性的判别准则。
精确证书,以及有限界没有保证什么
在简约状态中, 为正。因此,要判断 是否大于整数 ,只需比较正平方根 与整数 。若后者为负,比较立即确定;若后者非负,则比较 与它的平方。由于 不是平方数,不会出现相等。这使取整判断完全建立在整数运算上,无需把某个足够精确的小数当作证书的一部分。
因此,验证一个声称的周期,可以列出其中的整数对,逐项核对递推和取整不等式,并展示回到第一个整数对。固定 后,状态的表示唯一:两个 相等,会迫使有理部分和无理系数分别相等,从而两个整数对相同。若返回之前的各对互异,所列状态周期便具有最小长度。若数字存在更短周期,无穷展开的唯一性又会给出相同的完全商,因而迫使状态更早返回。
令 。上述有界矩形最多包含 个整数对,所以它给出每个简约周期长度的上界,尽管许多候选对不满足整除或简约不等式。这个界没有控制任意初始完全商进入简约状态之前需要多少步,也没有证明算法关于 的二进制长度是多项式时间的:与 成比例的界,对于该输入长度可能是指数级的。证明给出了精确终止和可核验的周期,同时保留了与更精细计算估计之间的区别。
例题详解
例题 11.2.4
(二的平方根有前缀,但一加上它则是简约的)
从 及 开始。下一个状态是 ,表示 。它的数字是二,而递推又回到同一个状态。于是 。它的共轭 小于 ,所以最初的平方根不是简约的,其连分数也不是纯周期的。相反, 的共轭 位于 中,并且 等于 。区别在于起始完全商,而不在于某处是否存在周期。
例题 11.2.5
(十三的平方根的精确五步周期)
从 开始。相继的整数状态及其数字为
例如,第一次更新用到 ;最后一次用到 与 。每次取整都来自 ,以及所示的整数分子与分母。回到起点之前的五个状态两两不同。因此 ,且这个完全商循环的长度为五。仅仅观察到小数中出现五个重复的块,并不能提供这些精确的状态相等关系。
例题 11.2.6
(由周期块还原无理数)
对于 ,块矩阵为 。它的不动点方程是 ,所以正根为 。它的值位于一与二之间,而它的共轭 位于 与零之间。简约准则确认所取的根具有纯周期;负根不可能是一个正的完全商。下一个完全商是 ,其数字为二,再下一个完全商又是 。仅有二次方程还不够,还必须配合区间信息来选出所要的根。
常见错误
反例模式
确定性的递推不一定是周期的
整数上的递推 是确定性的,却永不重复。在证明简约不等式之前,整数根式递推同样在一个无限集合上取值。有限状态这一步既需要整数性,也需要有界性。四舍五入后的数值状态又是另一回事:表面上的数值回归并不能证明两个二次无理数相等。
常见错误
(二次无理数不一定是纯周期的)
二次无理数不一定以纯周期开始, 就说明了这一点:它的首项 不重复,因为共轭 小于 ,所以 不是简约的。要到后面的完全商,即 ,周期才开始。
常见错误
(有理数输入不是周期的例子)
有理数在这个算法下会终止;它们另一种以有限的末项表示的写法,并不使它们成为无理周期的例子。
常见错误
(共轭不保持不等式)
证明利用共轭来界定状态,而不是断言共轭保持不等式。共轭可以改变符号与大小顺序:,但它的共轭 是负数。所以每个共轭递推与区间都单独做了检验。
快速检查
快速检查
(对于 ,每个满足 及 的整数对是否都必须出现在平方根的循环中?)
把矩形中整数对的个数,与上面算出的循环长度比较。
解答 · 答案
不必。整除性、简约不等式以及属于该特定轨道,都会施加进一步的限制。矩形包含 、 的 个整数对,但 的循环只用到其中五个。例如 位于矩形内,可是 。这个矩形只是候选状态的一个有限上界,而不是对单个周期的分类。
练习
快速检查
(从 出发,计算 的完全商状态,直到第一次回归。指出哪一个起始完全商是简约的。)
用 代入 及 。
解答 · 答案
由于 ,下一个状态是 ,数字为一。再下一个是 ,数字为二,它回到 。因此 。它的第一个完全商 的共轭 位于 中,所以是简约的。初始共轭 不在该区间内。
快速检查
(利用矩阵方程求出 所表示的正无理数。验证它的两个简约不等式及其两个精确数字。)
计算 ,再解不动点方程。
解答 · 答案
矩阵乘积为 ,给出 。正根为 ,其共轭 位于 中。它的整数部分为二。下一个完全商 的整数部分为一,再下一个完全商回到 。这就验证了精确的周期与根的选取。
快速检查
(设 。求 所满足的二次方程。解释为什么 是最终周期的而不是纯周期的。)
把 代入 。
解答 · 答案
方程 经倒数代换后变为 。正根为 ,位于零与一之间。它的连分数以零开头,此后每个数字都是一。它不可能是纯周期的,因为重复其初始的零会使零出现在后面的数字之中。它也不是简约的,因为它小于一。
快速检查
(解释为什么在一个正的二次尾部前面接上任何有限的容许简单连分数前缀,所得的无理数仍属于同一个二次域。说明为什么对这样的尾部,分式线性变换的分母不会为零。)
把前缀写成分式线性映射,其矩阵的行列式为 。
解答 · 答案
一个前缀给出 ,其系数为整数、行列式为 ,所以它的值位于该尾部所在的二次域中。若该值是有理数 ,则方程 要么使 成为有理数,要么迫使两个系数都为零;后者与行列式非零矛盾。分母在无理数 处不可能为零,因为那将给出一个非平凡的有理线性方程; 同样被行列式排除。因此所接上的值是一个次数为二的域中的无理元素,所以是二次的。
相关笔记
Pell 方程的单元在丢番图(Diophantine)的背景下使用与周期性相关的递推。本定理确立了精确的最终周期性与纯周期性;它没有给出最小周期长度的精确界,没有证明完整的 Hurwitz 逼近定理,也没有分类所有二次范数。