Binary Quadratic Forms

1. 二元二次型定义
2. 判别式（Discriminant）
3. 相似（Equivalence）
- 3.1. 相似型的判别式相等
- 3.2. 二元二次型相似的实例
4. 类数（Class Number）
5. 合成（Composition）
6. 参考

1. 二元二次型定义

含有二个变量 $x, y$ 的二次齐次函数 $f (x, y) = a x^{2} + b x y + c y^{2}$ 称为二元二次型（Binary Quadratic Form）。如果系数 $a, b, c$ 为复数，则称为“复二次型”。不过，研究最多的是系数 $a, b, c$ 都为整数时的情况，即 $a, b, c \in Z$ ，这时称为“整二元二次型”，也往往简称为“二元二次型”，本文介绍的内容都是系数 $a, b, c$ 为整数时的情况。

二元二次型 $f (x, y) = a x^{2} + b x y + c y^{2}$ 可记为 $(a, b, c)$ 。

2. 判别式（Discriminant）

整数 $d = b^{2} - 4 a c$ 称为二元二次型的判别式（Discriminant）。判别式 $d$ 一定会满足 $d \equiv 0 or 1 (\mod 4)$ 这是为什么呢？因为，对于任意整数 $b$ ，一定有 $b \equiv 0, 1, 2 or 3 (\mod 4)$ ，从而 $b^{2} \equiv 0, 1, 4 or 9 (\mod 4)$ ，而其中的 $4$ 和 $9$ 分别有 $4 \equiv 0 (\mod 4)$ 和 $9 \equiv 1 (\mod 4)$ ，从而 $b^{2} \equiv 0 or 1 (\mod 4)$ ，从而 $b^{2} - 4 a c \equiv 0 or 1 (\mod 4)$ 。

定理： $f (x, y)$ 可以分解为二个二元一次型之积的必要且充分的条件为 $d$ 为一个平方数。 这个定理的证明包含充分性和必要性两个方面。本文不介绍充分性的证明，有兴趣的读者可参考“数论导引（华罗庚著）第十二章”。下面是这个定理必要性的证明：假设 $f (x, y)$ 可分解为二个二元一次型之积，即 $a x^{2} + b x y + c y^{2} = (r x + s y) (t x + u y)$ 那么 $\begin{aligned} d & = b^{2} - 4 a c \\ = (s t + r u)^{2} - 4 r t \cdot s u \\ = (s t - r u)^{2} \end{aligned}$ 从而可知 $d$ 确实为一个平方数。定理的必要性得证。

当 $d$ 是一个平方数时，我们称二元二次型是 Degenerate（退化的），退化的的二元二次型不是我们讨论的重点，我们 往往设 $d$ 不是平方数。

2.1. 不定型（Indefinite）和定型（Definite）

当 $d > 0$ 时，二元二次型称为不定型（Indefinite），这是因为随着 $x, y$ 的变化， $f (x, y)$ 的值可正可负，也可为零。

当 $d < 0$ 时，二元二次型称为定型（Definite），这是因为不论 $x, y$ 取任何实值，只要 $x, y$ 不同时为零， $f (x, y)$ 的值恒正或恒负。具体来说，当 $d < 0, a > 0$ 时，只要 $x, y$ 不同时为零，一定有 $f (x, y) > 0$ ，这时 $f (x, y)$ 称为正定型（Positive Definite）；当 $d < 0, a < 0$ 时，只要 $x, y$ 不同时为零，一定有 $f (x, y) < 0$ ，这时 $f (x, y)$ 称为负定型（Negative Definite）。由于负定型乘以一个负号可以转换为正定型，所以很多时候我们只讨论正定型。

2.2. 基本判别式（Fundamental Discriminant）

如果判别式满足下面条件之一：

$d \equiv 1 (\mod 4)$ 并且 $d$ 是 Square-free 整数；
$d = 4 m$ ，其中 $m \equiv 2 or 3 (\mod 4)$ 并且 $m$ 是 Square-free 整数。

则称它为基本判别式（Fundamental Discriminant）。

上面定义中，提到了 Square-free 整数，一个整数是 Square-free 整数是指它的素因子分解中，素因子的指数都为 1。比如 $10 = 2 \cdot 5$ ，由于它的因子的指数都是 $1$ ，所以 $10$ 是 Square-free 整数，又如 $18 = 2 \cdot 3^{2}$ ，由于因子 $3$ 的指数大于 $1$ ，所以 $18$ 不是 Square-free 整数。

下面是最小的 12 个正 Fundamental Discriminant：

1, 5, 8, 12, 13, 17, 21, 24, 28, 29, 33, 37

下面是最大的 12 个负 Fundamental Discriminant：

−3, −4, −7, −8, −11, −15, −19, −20, −23, −24, −31, -35

如果 $d$ 为基本判别式，则以 $d$ 为判别式的型一定是原型。 原型的定义可参考节 2.3 。

2.3. 原型（Primitive Form）

如果二元二次型系数满足 $gcd (a, b, c) = 1$ ，则称这个二元二次型为原型（Primitive Form）。

很多时候我们仅仅讨论原型，这是因为如果不是原型，即 $gcd (a, b, c) = k \neq 1$ ，这时，我们可以设 $a = k A, b = k B, c = k C$ ，这样， $a, b, c$ 可以都去除公共因子 $k$ 而得到另一个原型。

如果 $d$ 为基本判别式，则以 $d$ 为判别式的型一定是原型。

3. 相似（Equivalence）

关于相似有两套定义，分别是狭义相似和广义相似。

设两个二元二次型 $f (x, y) = a x^{2} + b x y + c y^{2}$ 和 $g (x, y) = a_{1} x^{2} + b_{1} x y + c_{1} y^{2}$ ，如果存在满足条件 $r u - s t = 1$ 的有理整数 $r, s, t, u$ 使得 $g (x, y) = f (r x + s y, t x + u y)$ 成立，则称 $f (x, y)$ 和 $g (x, y)$ 为相似（Equivalence），也称为“狭义相似”（Proper Equivalence）。

设两个二元二次型 $f (x, y) = a x^{2} + b x y + c y^{2}$ 和 $g (x, y) = a_{1} x^{2} + b_{1} x y + c_{1} y^{2}$ ，如果存在满足条件 $r u - s t = \pm 1$ 的有理整数 $r, s, t, u$ 使得 $g (x, y) = f (r x + s y, t x + u y)$ 成立，则称 $f (x, y)$ 和 $g (x, y)$ 为“广义相似”（Wide Equivalence）或 Improper Equivalence。

狭义相似和广义相似和区别仅仅在于 对 $r, s, t, u$ 的限制不一样，一个要求 $r u - s t = 1$ ，另一个则要求 $r u - s t = \pm 1$ 。 为什么要做这样的限制呢？这是因为有了这样限制（ $r u - s t = 1$ 或者 $r u - s t = \pm 1$ ）后，可以推导出“相似型的判别式相等”的结论，参见节 3.1 。

对于两个正定型，如果它们广义相似，则一定狭义相似。但对于不定型而言，就不一定了。

3.1. 相似型的判别式相等

假设 $f (x, y) = a x^{2} + b x y + c y^{2}$ 和 $g (x, y) = a_{1} x^{2} + b_{1} x y + c_{1} y^{2}$ 相似，则它们的判别式相等。

由于它们相似，所以有： $\begin{aligned} g (x, y) & = f (r x + s y, t x + u y) \\ = a (r x + s y)^{2} + b (r x + s y) (t x + u y) + c (t x + u y)^{2} \\ = (a r^{2} + b r t + c t^{2}) x^{2} + (2 a r s + b (r u + s t) + 2 c t u) x y + (a s^{2} + b s u + c u^{2}) y^{2} \end{aligned}$ 从而： $\begin{aligned} a_{1} & = a r^{2} + b r t + c t^{2} \\ b_{1} & = 2 a r s + b (r u + s t) + 2 c t u \\ c_{1} & = a s^{2} + b s u + c u^{2} \end{aligned}$ 由此可得： $\begin{aligned} b_{1}^{2} - 4 a_{1} c_{1} & = (2 a r s + b (r u + s t) + 2 c t u)^{2} - 4 (a r^{2} + b r t + c t^{2}) (a s^{2} + b s u + c u^{2}) \\ = (b^{2} - 4 a c) (r u - s t)^{2} \\ = b^{2} - 4 a c \end{aligned}$ 上一步转换过程中利用了 $(r u - s t)^{2} = 1$ 。由此可见，相似型的判别式相等。

3.2. 二元二次型相似的实例

设有 $f (x, y) = x^{2} + 4 x y + 2 y^{2}$ 和 $g (x, y) = - x^{2} + 4 x y - 2 y^{2}$ ，问 $f (x, y)$ 和 $g (x, y)$ 是否相似。

答案是肯定的，因为存在 $r = - 3, s = 2, t = 1, u = - 1$ ，显然它们满足 $r u - s t = 1$ ，而且 $\begin{aligned} f (r x + s y, t x + u y) & = f (- 3 x + 2 y, x - y) \\ = (- 3 x + 2 y)^{2} + 4 (- 3 x + 2 y) (x - y) + 2 (x - y)^{2} \\ = - x^{2} + 4 x y - 2 y^{2} \\ = g (x, y) \end{aligned}$ 所以二元二次型 $f (x, y)$ 和 $g (x, y)$ 是相似的。

4. 类数（Class Number）

4.1. 利用相似关系进行分类

二元二次型之间的相似关系是一种等价关系，所以可把所有二元二次型依据是否相似进行分类，凡相似的分在同一类，凡不相似的绝不在同一类。同一分类的判别式相同。不过，判别式相同却不一定都相似。

4.2. 类数有限

对于给定的判别式 $d$ ，有多少个二元二次型，它们的判别式会为 $d$ 呢？由于 $a, b, c$ 可以从 $Z$ 中随意选择，一般可以找到无数对 $a, b, c$ 满足 $b^{2} - 4 a c = d$ 这个要求。

不过，如果把相似的二元二次型算做一类，那么有多少类二元二次型的判别式会为给定的 $d$ 呢？这个类数（Class Number）我们把它记为 $h (d)$ ，Lagrange 证明了当 $d < 0$ 时， $h (d)$ 是有限的。至少到底 $h (d)$ 为多少，可参考节 4.4 。

4.3. 约化型（Reduced Forms）

对于任意正定型（由节 2.1 可知正定型会满足 $d < 0, a > 0$ ），如果下面两个不等式都成立： $\begin{aligned} - a < b \leq a \leq c \\ b \geq 0 i f a = c \end{aligned}$ 则我们称这样的二元二次型为 Reduced 二元二次型。 这种表述见于 Binary Quadratic Forms - An Algorithmic Approach。

关于 Reduced 二元二次型还有另一种表述：对于任意正定型，如果 $- a < b \leq a < c$ 或者 $0 \leq b \leq a = c$ 成立，则称它为 Reduced 二元二次型。这种表述见于“数论导引（华罗庚著）”。

对于任意一类（所有相似的二元二次型称为一类）正定型二元二次型，它们之间“有且仅有一个” Reduced 二元二次型。 这样，Reduced 二元二次型就非常重要了，因为它可以唯一标记正定型二元二次型的类别。

4.3.1. $a \leq \sqrt{| d | / 3}$

引理： 对于某个正定型二元二次型，如果它是 Reduced 二元二次型，则一定有 $a \leq \sqrt{| d | / 3}$ 。 证明如下： $\begin{aligned} | d | & = 4 a c - | b |^{2} & (d < 0) \\ \leq 4 a (a) - a^{2} & (- a < b \leq a, a \leq c) \\ \leq 3 a^{2} \end{aligned}$ 从而 $a \leq \sqrt{| d | / 3}$ 。

4.3.2. Reduction 算法

Reduction 算法是指把一个二元二次型转换为和它相似的 Reduced Form 的方法。

Binary Quadratic Forms - An Algorithmic Approach 中第 5.3 节介绍了 Reduction 算法，这里不详细介绍。

4.4. $d < 0$ 时的类数计算

定理：判别式为 $d$ 的正定型二元二次型的类数等于适合 $b^{2} - 4 a c = d, {\begin{cases} - a < b \leq a < c \\ o r 0 \leq b \leq a = c \end{cases}$ 的整数组 $a, b, c$ 的组数。证明过程可参考“数论导引（华罗庚著）”。

这个定理也可换一种表述：当 $d < 0$ 时，类数 $h (d) = | {(a, b, c) \in Z^{3} | \begin{aligned} b^{2} - 4 a c = d \\ - a < b \leq a < c o r 0 \leq b \leq a = c \end{aligned}} |$

注 1：这个定理中对 $a, b, c$ 的约束条件 $- a < b \leq a < c o r 0 \leq b \leq a = c$ 就是 Reduced 二元二次型的定义要求。换句话说， $d < 0$ 时，二元二次型的类数就是判别式为 $d$ 的 Reduced 二元二次型的个数。

注 2：由这个定理容易推导出类数有限的结论。因为由节 4.3 知 $a \leq \sqrt{| d | / 3}$ ，从而 $a$ 是有限的；又由于 $| b | \leq a$ ，从而 $b$ 也是有限的；又由于 $c = (b^{2} - d) / 4 a$ ，从而 $c$ 也是有限的。从而 $a, b, c$ 的组合也是有限的，从而类数有限。

4.4.1. 类数计算的实例

实例：设正定型二元二次型的判别式 $d = - 35$ ，求解 $h (d)$ 。

当 $d < 0$ 时，求类数 $h (d)$ 的基本思路是：找出所有判别式为 $d$ 的 Reduced 二元二次型，然后统计其个数，得到的结果就是类数 $h (d)$ 。

由节 4.3.1 知， $a \leq \sqrt{| d | / 3} = 3.415$ ，从而可知 $1 \leq a \leq 3, - 3 \leq b \leq 3$ 。又由于 $d$ 是奇数，从而 $b$ 也一定是奇数，所以有 $b \in {- 3, - 1, 1, 3}$ 。 $b$ 的这 $4$ 种取值，下面分 $b = \pm 1, b = \pm 3$ 两种情况来讨论。

当 $b = \pm 1$ 时， $c = (b^{2} - d) / 4 a = 9 / a$ ，由于 $c$ 是整数，所以 $a = 1 o r 3$ ，组合起来可得到了 $(1, 1, 9), (1, - 1, 9), (3, 1, 3), (3, - 1, 3)$ ，但其中 $(1, - 1, 9), (3, - 1, 3)$ 不是 Reduced Form，所以当 $b = \pm 1$ 时，得到了两个 Reduced Form $(1, 1, 9), (3, 1, 3)$ 。

当 $b = \pm 3$ 时，由于 $a \geq | b |$ 所以 $a = 3$ ，但是 $c = (b^{2} - d) / 4 a = 44 / 12$ 不是整数，所以当 $b = \pm 3$ 时没有 Reduced Form。

所以 $h (- 35) = 2$ 。

4.4.2. 类数计算的程序实现（当 $| d |$ 很大时计算很慢）

Binary Quadratic Forms - An Algorithmic Approach 中给出了当 $d < 0$ 时类数计算的伪代码，如图 1 所示（算法中的 $Δ$ 就是判别式 $d$ ），它的时间复杂度为 $O (| d | (s i z e d)^{2})$ 。这并不是一个高效的类数计算算法（本质上是一种穷举法），当 $| d |$ 很大时，计算类数将非常慢，这是一个计算困难问题（Computationally Difficult Problem）。

Figure 1: Class Number

4.4.3. 类数比较小时的基本判别式列表

表 1 是类数 $h (d)$ 为 1 到 10 时，判别式 $d < 0$ 且 $d$ 为基本判别式（参考节 2.2）时的列表（摘自：https://mathworld.wolfram.com/ClassNumber.html ）。这个表，最后一列是省略负号的写法，比如，表中第一行表示当 $d = - 3, - 4, - 7, - 8, - 11, - 19, - 43, - 67, - 163$ 时 $h (d) = 1$ 。

Table 1: Class Numbers
$h (- d)$	$N$	Sloane	$d$
1	9	A014602	3, 4, 7, 8, 11, 19, 43, 67, 163
2	18	A014603	15, 20, 24, 35, 40, 51, 52, 88, 91, 115, 123, 148, 187, 232, 235, 267, 403, 427
3	16	A006203	23, 31, 59, 83, 107, 139, 211, 283, 307, 331, 379, 499, 547, 643, 883, 907
4	54	A013658	39, 55, 56, 68, 84, 120, 132, 136, 155, 168, 184, 195, 203, 219, 228, 259, 280, 291, 292, 312, 323, 328, 340, 355, 372, 388, 408, 435, 483, 520, 532, 555, 568, 595, 627, 667, 708, 715, 723, 760, 763, 772, 795, 955, 1003, 1012, 1027, 1227, 1243, 1387, 1411, 1435, 1507, 1555
5	25	A046002	47, 79, 103, 127, 131, 179, 227, 347, 443, 523, 571, 619, 683, 691, 739, 787, 947, 1051, 1123, 1723, 1747, 1867, 2203, 2347, 2683
6	51	A046003	87, 104, 116, 152, 212, 244, 247, 339, 411, 424, 436, 451, 472, 515, 628, 707, 771, 808, 835, 843, 856, 1048, 1059, 1099, 1108, 1147, 1192, 1203, 1219, 1267, 1315, 1347, 1363, 1432, 1563, 1588, 1603, 1843, 1915, 1963, 2227, 2283, 2443, 2515, 2563, 2787, 2923, 3235, 3427, 3523, 3763
7	31	A046004	71, 151, 223, 251, 463, 467, 487, 587, 811, 827, 859, 1163, 1171, 1483, 1523, 1627, 1787, 1987, 2011, 2083, 2179, 2251, 2467, 2707, 3019, 3067, 3187, 3907, 4603, 5107, 5923
8	131	A046005	95, 111, 164, 183, 248, 260, 264, 276, 295, 299, 308, 371, 376, 395, 420, 452, 456, 548, 552, 564, 579, 580, 583, 616, 632, 651, 660, 712, 820, 840, 852, 868, 904, 915, 939, 952, 979, 987, 995, 1032, 1043, 1060, 1092, 1128, 1131, 1155, 1195, 1204, 1240, 1252, 1288, 1299, 1320, 1339, 1348, 1380, 1428, 1443, 1528, 1540, 1635, 1651, 1659, 1672, 1731, 1752, 1768, 1771, 1780, 1795, 1803, 1828, 1848, 1864, 1912, 1939, 1947, 1992, 1995, 2020, 2035, 2059, 2067, 2139, 2163, 2212, 2248, 2307, 2308, 2323, 2392, 2395, 2419, 2451, 2587, 2611, 2632, 2667, 2715, 2755, 2788, 2827, 2947, 2968, 2995, 3003, 3172, 3243, 3315, 3355, 3403, 3448, 3507, 3595, 3787, 3883, 3963, 4123, 4195, 4267, 4323, 4387, 4747, 4843, 4867, 5083, 5467, 5587, 5707, 5947, 6307
9	34	A046006	199, 367, 419, 491, 563, 823, 1087, 1187, 1291, 1423, 1579, 2003, 2803, 3163, 3259, 3307, 3547, 3643, 4027, 4243, 4363, 4483, 4723, 4987, 5443, 6043, 6427, 6763, 6883, 7723, 8563, 8803, 9067, 10627
10	87	A046007	119, 143, 159, 296, 303, 319, 344, 415, 488, 611, 635, 664, 699, 724, 779, 788, 803, 851, 872, 916, 923, 1115, 1268, 1384, 1492, 1576, 1643, 1684, 1688, 1707, 1779, 1819, 1835, 1891, 1923, 2152, 2164, 2363, 2452, 2643, 2776, 2836, 2899, 3028, 3091, 3139, 3147, 3291, 3412, 3508, 3635, 3667, 3683, 3811, 3859, 3928, 4083, 4227, 4372, 4435, 4579, 4627, 4852, 4915, 5131, 5163, 5272, 5515, 5611, 5667, 5803, 6115, 6259, 6403, 6667, 7123, 7363, 7387, 7435, 7483, 7627, 8227, 8947, 9307, 10147, 10483, 13843

4.5. 类数的解析公式（Dirichlet 类数公式）

德国数学家 Dirichlet 给出了计算类数的解析公式，称为 Dirichlet Class Number Formula ，表述如下。

设 $d$ 为基本判别式，则类数 $h (d)$ 满足下面公式 $h (d) = {\begin{cases} \frac{w \sqrt{| d |}}{2 π} L (1, χ), & d < 0; \\ \frac{\sqrt{d}}{\ln ε} L (1, χ), & d > 0. \end{cases}$ 式中 $w = {\begin{cases} 2, & d < - 4; \\ 4, & d = - 4; \\ 6, & d = - 3. \end{cases}$ 式中 $L (1, χ)$ 为 Dirichlet L-function $L (1, χ) = \sum_{n = 1}^{\infty} \frac{χ (n)}{n}$ 式中 $χ (n) = (\frac{d}{n})$ 为 Kronecker symbol ，式中 $ε = \frac{1}{2} (t + u \sqrt{d})$ ，其中 $t, u$ 是 Pell 方程 $x^{2} - d y^{2} = 4$ 的解（需要满足 $t > 0, u > 0$ ，且 $u$ 为最小可能值）。

4.6. 高斯类数问题

高斯类数问题（Class Number Problem）是指下面 3 个高斯猜想：

正好存在 9 个负的基本判别式，使得类数 $h (d) = 1$ 。
当负的基本判别式 $d \to - \infty$ 时，类数 $h (d) \to + \infty$ 。
存在无穷多个正的基本判别式，使得类数 $h (d) \to + \infty$ 。

目前为止，剩下第 3 个猜想未解决。

5. 合成（Composition）

记所有判别式为 $d$ 的二元二次原型类的全体为 $C (d)$ ， $C (d)$ 是一个有限 Abel 群。

既然是一个群，就需要为这个群定义一个运算，这个运算就是二次型的 Composition 运算，数学家 Gauss, Arndt, Dirichlet, Bhargava 都对 Composition 运算进行了研究，所以 Composition 运算有不同的变种，具体可参考：Composing Quadratic Forms: Gauss, Dirichlet and Bhargava。

6. 参考

本文主要参考下面资料：

数论导引（华罗庚著）
从高斯到盖尔方特：二次数域的高斯猜想
Binary Quadratic Forms - An Algorithmic Approach
Binary quadratic forms, Lipa Long
Class Groups for Cryptographic Accumulators