构造 17、257 和 65537 边形

经典地，能够用尺规作图构造的正多边形仅有 3、4、5 或 15 边形，以及这些边数乘以 2 的幂（因为二等分很容易）。卡尔·弗里德里希·高斯于 1801 年发表了一个证明，表明边数为素数且形如 2^2^m + 1（称为费马素数）的正多边形可以被构造，并声称他证明了只有这些可以被构造（以及由单个费马素数的幂与 2 的幂相乘所得的构造）。Wantzel 后来发表了一个完整的证明。已知的费马素数仅有 N = 3、5、17、257 和 65537。更多历史请参见 Wikipedia。

核心思想是将正多边形在单位圆上的顶点视为复数，即 z^N = 1 的解。因此这些顶点就是"N 次单位根"。高斯证明了某些单位根的和可以用其他和通过二次方程递归求解，最终归结为一对共轭根的和，其一半给出了一个根的实部。由于二次方程可以用尺规作图求解，因此构造是可以实现的。

算法：

找到一个生成 Z_N 乘法群的整数 K。对于 N = 5、17、257、65537，K = 3 恰好适用，因此我们直接使用它。
列出 K 模 N 的幂次，例如对于 N = 17，我们有 1、3、9、10、……。该列表有 N-1 个元素，因为 0 不在乘法群中不会出现。按此顺序列出 N-1 个单位根（省略 1）。
设 S(m,i) 为从列表中第 i 个开始、每隔 m 个取一个的根的和。我们仅使用 m 为 2 的幂的情况。注意 S(1,0) = -1，因为所有 N 个根之和为 0（z^N - 1 = 0 中 z^N-1 的系数），且 1 被省略。
事实证明，S(2*m,i)*S(2*m,i+m) 是 S(m,j) 及更低阶项的整数系数线性组合。同时，S(2*m,j)+S(2*m,j+m) = S(m,j)。从 S(1,0) = -1 开始，我们可以递归地通过二次方程求解所有 S(m,i)。
当 m = (N-1)/2 时，S(m,i) 恰好是两个共轭根的和，因此 S((N-1)/2,i) 就是这两个根（设为 U 和 V）的 x 坐标。
任意两个根之间的弦（例如 1 和 U，或 U 和 V）可以用来在单位圆上标出所有 N 个顶点。

关键的一步是在第 4 步中找到线性组合。出于兴趣，我编写了一个程序来寻找这种组合。所使用的方法是将乘积写成根的符号和，然后用高斯消元法求系数；幸运的是，消元矩阵一开始就很稀疏，并且随着求解的进行越来越稀疏。即使是 65537 边形，使用稀疏矩阵技术，整个消元过程不到 10 分钟，占用不到 60 MB 内存。输出是一个 Mathematica 文件，其中包含一系列二次公式，最终得到所需的值。

17 边形

使用 4 次二次方程求解。 Mathematica file。以下是在单位圆上求第 3 个顶点的 x 坐标的计算序列，从 x 轴上的第 1 个顶点逆时针计数：

a0 = -1

prod = 4*a0
a1 = (a0 + Sqrt[a0^2 - 4*prod])/2

prod = 4*a0
a2 = (a0 - Sqrt[a0^2 - 4*prod])/2

prod = 1*a0
a5 = (a1 - Sqrt[a1^2 - 4*prod])/2

prod = 1*a0
a6 = (a2 - Sqrt[a2^2 - 4*prod])/2

prod = 1*a6
a13 = (a5 + Sqrt[a5^2 - 4*prod])/2

x2 = a13/2

257 边形

使用 24 次二次方程求解。 Mathematica file。以下是在单位圆上求第 33 个顶点的 x 坐标的计算序列，从 x 轴上的第 1 个顶点逆时针计数：

a0 = -1

prod = 64*a0
a1 = (a0 + Sqrt[a0^2 - 4*prod])/2

prod = 64*a0
a2 = (a0 - Sqrt[a0^2 - 4*prod])/2

prod = 16*a0
a3 = (a1 + Sqrt[a1^2 - 4*prod])/2

prod = 16*a0
a4 = (a2 + Sqrt[a2^2 - 4*prod])/2

prod = 16*a0
a5 = (a1 - Sqrt[a1^2 - 4*prod])/2

prod = 16*a0
a6 = (a2 - Sqrt[a2^2 - 4*prod])/2

prod = 5*a0 - 1*a1 - 2*a3
a7 = (a3 + Sqrt[a3^2 - 4*prod])/2

prod = 5*a0 - 1*a2 - 2*a4
a8 = (a4 - Sqrt[a4^2 - 4*prod])/2

prod = 5*a0 - 1*a1 - 2*a5
a9 = (a5 + Sqrt[a5^2 - 4*prod])/2

prod = 5*a0 - 1*a2 - 2*a6
a10 = (a6 - Sqrt[a6^2 - 4*prod])/2

prod = 5*a0 - 1*a1 - 2*a3
a11 = (a3 - Sqrt[a3^2 - 4*prod])/2

prod = 5*a0 - 1*a2 - 2*a4
a12 = (a4 + Sqrt[a4^2 - 4*prod])/2

prod = 5*a0 - 1*a1 - 2*a5
a13 = (a5 - Sqrt[a5^2 - 4*prod])/2

prod = 5*a0 - 1*a2 - 2*a6
a14 = (a6 + Sqrt[a6^2 - 4*prod])/2

prod = 1*a1 + 2*a4 + 1*a7 - 2*a8 + 1*a9
a15 = (a7 + Sqrt[a7^2 - 4*prod])/2

prod = 1*a2 + 2*a5 + 1*a8 - 2*a9 + 1*a10
a16 = (a8 + Sqrt[a8^2 - 4*prod])/2

prod = 1*a1 + 2*a6 + 1*a9 - 2*a10 + 1*a11
a17 = (a9 + Sqrt[a9^2 - 4*prod])/2

prod = 1*a2 + 2*a3 + 1*a10 - 2*a11 + 1*a12
a18 = (a10 + Sqrt[a10^2 - 4*prod])/2

prod = 1*a1 + 2*a4 + 1*a11 - 2*a12 + 1*a13
a19 = (a11 + Sqrt[a11^2 - 4*prod])/2

prod = 1*a2 + 2*a5 + 1*a12 - 2*a13 + 1*a14
a20 = (a12 + Sqrt[a12^2 - 4*prod])/2

prod = 1*a1 + 2*a6 + 1*a13 - 2*a14 + 1*a7
a21 = (a13 - Sqrt[a13^2 - 4*prod])/2

prod = 1*a2 + 2*a3 + 1*a14 - 2*a7 + 1*a8
a22 = (a14 + Sqrt[a14^2 - 4*prod])/2

prod = 1*a1 + 2*a4 + 1*a7 - 2*a8 + 1*a9
a23 = (a7 - Sqrt[a7^2 - 4*prod])/2

prod = 1*a2 + 2*a5 + 1*a8 - 2*a9 + 1*a10
a24 = (a8 - Sqrt[a8^2 - 4*prod])/2

prod = 1*a1 + 2*a6 + 1*a9 - 2*a10 + 1*a11
a25 = (a9 - Sqrt[a9^2 - 4*prod])/2

prod = 1*a2 + 2*a3 + 1*a10 - 2*a11 + 1*a12
a26 = (a10 - Sqrt[a10^2 - 4*prod])/2

prod = 1*a1 + 2*a4 + 1*a11 - 2*a12 + 1*a13
a27 = (a11 - Sqrt[a11^2 - 4*prod])/2

prod = 1*a2 + 2*a5 + 1*a12 - 2*a13 + 1*a14
a28 = (a12 - Sqrt[a12^2 - 4*prod])/2

prod = 1*a1 + 2*a6 + 1*a13 - 2*a14 + 1*a7
a29 = (a13 + Sqrt[a13^2 - 4*prod])/2

prod = 1*a2 + 2*a3 + 1*a14 - 2*a7 + 1*a8
a30 = (a14 - Sqrt[a14^2 - 4*prod])/2

prod = 1*a23 + 1*a24 + 1*a25 + 1*a28
a39 = (a23 - Sqrt[a23^2 - 4*prod])/2

prod = 1*a24 + 1*a25 + 1*a26 + 1*a29
a40 = (a24 - Sqrt[a24^2 - 4*prod])/2

prod = 1*a30 + 1*a15 + 1*a16 + 1*a19
a46 = (a30 + Sqrt[a30^2 - 4*prod])/2

prod = 1*a15 + 1*a16 + 1*a17 + 1*a20
a47 = (a15 - Sqrt[a15^2 - 4*prod])/2

prod = 1*a16 + 1*a17 + 1*a18 + 1*a21
a48 = (a16 - Sqrt[a16^2 - 4*prod])/2

prod = 1*a22 + 1*a23 + 1*a24 + 1*a27
a54 = (a22 + Sqrt[a22^2 - 4*prod])/2

prod = 1*a23 + 1*a24 + 1*a25 + 1*a28
a55 = (a23 + Sqrt[a23^2 - 4*prod])/2

prod = 1*a30 + 1*a40 - 1*a46
a71 = (a39 - Sqrt[a39^2 - 4*prod])/2

prod = 1*a22 + 1*a48 - 1*a54
a111 = (a47 + Sqrt[a47^2 - 4*prod])/2

prod = 1*a7 - 1*a15 - 1*a55 - 1*a71
a239 = (a111 - Sqrt[a111^2 - 4*prod])/2

x32 = a239/2

65537 边形

使用 1141 次二次方程求解。幸运的是，如果你想尝试手工构造，线性组合中的项数最多只有 92 项。 Mathematica file。（这里的二次方程解超过 1141 个，因为我将使用两个根算作一个方程——这可以通过一次几何构造完成，但在这里使用了两个 Mathematica 公式。）公式列表太长，无法放在此处，请参见文件。

参考文献：

Carl Friedrich Gauss, Disquitiones Arithmeticae, 1801, section VII. (English translation by Arthur A. Clarke, 1965 (Yale).)
Christian Gottlieb, "The Simple and Straightforward Construction of the Regular 257-gon," Mathematical Intelligencer, vol. 21, no. 1, 1999, p. 31-37.

返回作图主页。

返回 Ken Brakke 主页。