关于正多边形的尺规作图

cancan123456 · 2022-11-04 20:54:55 · 个人记录

由于 Gauss 的工作，所以我们只需要讨论如下几种正多边形：

1. 正三边形
2. 正五边形
3. 正十七边形
4. 正二百五十七边形
5. 正六万五千五百三十七边形

正三边形、正五边形的尺规作图请到课本里找。

正十七边形

我们需要求出单位根 \omega_{17}^1 即可。

设

其中 \omega 为单位根。

显然易得：

什么？你说这不显然？

行，满足你：

然后就可以解出来：

再通过数值计算，我们可以得出：

接下来，我们令

即：

那么显然有：

证明：

然后我们解得：

然后再根据数值计算，我们可以得到上面的结果是对的。

然后再令：

注意我们这里只需要求出 \gamma_0,\gamma_1 的值即可，原因在下面会解释。

那么我们可以得到：

解得：

然后我们观察 \gamma_0=\omega_{17}^0+\omega_{17}^{16}，因为 \omega_{17}^0 和 \omega_{17}^{16} 互为共轭，所以：\gamma_0=2\Re(\omega_{17}^1)，再根据 |\omega_{17}^1|=1 就可以求出 \omega_{17}^1 了。

所以，我们来总结一下 \omega_{17}^1 的构造方法，令：

则：

如果整合在一起就是这个样子（不想化简了）：

结合数值计算我们可以得到中间表达式的大小关系（由于程序原因，需要倒着看）：

Carlyle Circle

考虑两个数 s,p，其可以确定一个二次方程 x^2-sx+p=0，在给定 s,p 的情况下，我们可以尺规作图求出其两个根。

那么有没有很简单的方法？有。

我们作两个点 (0,1) 和 (s,p)，以其为直径作圆，该圆交于 x 轴于两点，则这两点为 x^2-sx+p 的两个根。

注意以 (s,1) 和 (0,p) 做直径也可以。

证明不会。

这个方法就叫 Carlyle Circle。

正二百五十七边形

同正十七边形一样，我们只需要求出 \omega_{257}^1 即可。

我们设：

我们显然有 \Re(\omega_{257}^1)=\dfrac{g_0}2，所以求出 g_0 即可。

我们考虑 g_{64}，通过符号计算我们得到：

问题转化为计算 f_0,f_{56}，同样找两个与其配对的：

问题转化为计算 e_0,e_1,e_{15},e_{23},e_{24},e_{25}，再次配对：

然后 d_0,d_1,d_2,d_3,d_4,d_5,d_6,d_7,d_8,d_9,d_{10},d_{11},d_{12},d_{13},d_{14},d_{15} 都要计算。

还是配对：

问题转化为计算 c_0,c_1,c_2,c_3,c_4,c_5,c_6,c_7，还是配对：

问题转化为计算 b_0,b_1,b_2,b_3，还是配对：

问题转化为计算 a_0,a_1，列出方程：

解出 a_0,a_1 后就可以一路推下去了，最终结果就像这样：

什么？你要看到所有的圆和直线？

可以看这个。

点的坐标范围大概是 [-30,30]\times[-40,40] 之间，所以大概能画在 A4 纸上。

正六万五千五百三十七边形

还是类似的思路：设

仍然从底层倒着推，我们显然有 \Re(\omega_{65537}^1)=\dfrac{s_1}2，所以求出 s_1 即可。

由于过程太长了，所以请运行以下程序产生：

#include <iostream>
#include <complex>
#include <vector>
using namespace std;
const int m = 4;
const int n = (1 << (1 << m)) + 1;
const double pi = 3.14159265358979323846;
struct Number {
    short x[n]; // 这里 short 足够了，最大值 16384.
    Number() {
        for (int i = 0; i < n; i++) {
            x[i] = 0;
        }
    }
};
Number operator + (const Number & a, const Number & b) {
    Number c;
    for (int i = 0; i < n; i++) {
        c.x[i] = a.x[i] + b.x[i];
    }
    return c;
}
Number operator - (const Number & a, const Number & b) {
    Number c;
    for (int i = 0; i < n; i++) {
        c.x[i] = a.x[i] - b.x[i];
    }
    return c;
}
Number operator * (const Number & a, const Number & b) {
    Number c;
    for (int i = 0; i < n; i++) {
        if (a.x[i] > 0) {
            for (int j = 0; j < n; j++) {
                c.x[(i + j) % n] += a.x[i] * b.x[j];
            }
        }
    }
    return c;
}
Number operator * (const Number & a, const int & b) {
    Number c;
    for (int i = 0; i < n; i++) {
        c.x[i] += a.x[i] * b;
    }
    return c;
}
bool operator == (const Number & a, const Number & b) {
    for (int i = 0; i < n; i++) {
        if (a.x[i] != b.x[i]) {
            return false;
        }
    }
    return true;
}
complex < double > omega(int k) {
    return complex < double > (cos(2 * pi * k / n), sin(2 * pi * k / n));
}
complex < double > calc(Number a) {
    complex < double > x = 0;
    for (int i = 0; i < n; i++) {
        x += complex < double > (a.x[i], 0) * omega(i);
    }
    return x;
}
string to_cof(int x) {
    if (x == 1) {
        return "";
    } else {
        return to_string(x);
    }
}
string warpper(int x) {
    if (x <= 9) {
        return to_string(x);
    } else {
        return "{" + to_string(x) + "}";
    }
}
string term(int x, int y) {
    string res;
    if (x > 0) {
        res = "+";
    }
    res += to_cof(x) + "\\omega_{" + to_string(n) + "}^" + warpper(y);
    return res;
}
void print_LaTeX(Number x) {
    string s;
    for (int i = 0; i < n; i++) {
        if (x.x[i] != 0) {
            s += term(x.x[i], i);
        }
    }
    if (s.length() == 0) {
        cout << 0 << endl;
    } else {
        if (s[0] == '+') {
            s = s.substr(1, s.length() - 1);
        }
        cout << s << endl;
    }
}
void print(Number x) {
    for (int i = 0; i < n; i++) {
        printf("%d ", x.x[i]);
    }
    printf("\n");
}
int pow(int a, int b) {
    int ans = 1;
    while (b != 0) {
        if ((b & 1) == 1) {
            ans = 1ll * ans * a % n;
        }
        a = 1ll * a * a % n;
        b = b / 2;
    }
    return ans;
}
int get_first(Number x) {
    for (int i = 0; i < n; i++) {
        if (x.x[i] != 0) {
            return i;
        }
    }
    return -1;
}
vector < int > get(Number x, const vector < Number > & a) {
    vector < int > res(0, a.size());
    for (int i = 0, first; i < (int)a.size(); i++) {
        first = get_first(a[i]);
        if (first != -1) {
            res.push_back(x.x[first]);
            for (int j = 0; j < n; j++) {
                if (a[i].x[j] != 0) {
                    if (x.x[j] != res[i]) {
                        printf("Error.\n");
                        return vector < int > ();
                    }
                }
            }
            x = x - a[i] * res[i];
        }
    }
    if (x == Number()) {
        return res;
    } else {
        return res;
    }
}
void print(vector < int > vec) {
    for (int x : vec) {
        printf("%d ", x);
    }
    printf("\n");
}
bool vis[n];
void print_LaTeX(vector < int > vec, char name) {
    bool first = true;
    for (int i = 0; i < (int)vec.size(); i++) {
        if (vec[i] > 0) {
            vis[i] = true;
            if (!first) {
                printf("+");
            } else {
                first = false;
            }
            if (vec[i] == 1) {
                printf("%c_", name);
                cout << warpper(i);
            } else {
                printf("%d%c_", vec[i], name);
                cout << warpper(i);
            }
        }
    }
    printf("\\\\");
}
vector < vector < int > > vec;
//int which[n];
void get_which(int i) { // 分成 2 ^ i 个组.
    vec.clear();
    for (int j = 0; j < (1 << i); j++) {
        vec.push_back(vector < int > ());
        for (int k = 0; k < (n - 1) / (1 << i); k++) {
            vec[j].push_back(pow(3, (k << i) + j));
//          which[pow(3, (k << i) + j)] = j;
        }
    }
}
vector < int > get(Number x, int i) {
    vector < int > res((1 << i), 0);
    for (int j = 0; j < (1 << i); j++) {
        res[j] = x.x[vec[j][0]];
        for (int k : vec[j]) {
            if (x.x[k] != res[j]) {
                printf("Error.");
            } else {
                x.x[k] = 0;
            }
        }
    }
    for (int j = 0; j < n; j++) {
        if (x.x[j] != 0) {
            printf("Error.");
        }
    }
    return res;
}
Number get_number(int i, int j) { // 2 ^ i 个中的第 j 个.
    Number x;
    for (int k = 0; k < (n - 1) / (1 << i); k++) {
        x.x[pow(3, (k << i) + j)] = 1;
    }
    return x;
}
const char * name = "zabcdefghklopqrs";
bool todo[n];
int main() {
    freopen("output.txt", "w", stdout);
    // now 表示要运算的数的层数.
    printf("$$\\begin{cases}");
    todo[0] = true;
    for (int now = (1 << m) - 1; now > 0; now--) {
        for (int i = 0; i < n; i++) {
            vis[i] = false;
        }
        int delta = 1 << (now - 1);
        get_which(now - 1);
        for (int x = 0, y; x < delta; x++) {
            if (todo[x]) {
                y = (x + delta) % (1 << now);
                Number a = get_number(now, x) + get_number(now, y);
                cout << string() + name[now] + "_" + warpper(x) + "+" + name[now] + "_" + warpper(y) + "=";
                print_LaTeX(get(a, now - 1), name[now - 1]);
                Number b = get_number(now, x) * get_number(now, y);
                cout << string() + name[now] + "_" + warpper(x) + name[now] + "_" + warpper(y) + "=";
                print_LaTeX(get(b, now - 1), name[now - 1]);
            }
        }
//      printf("\n");
        for (int i = 0; i < delta / 2; i++) {
            if (vis[i] || vis[i + delta / 2]) {
//          printf("todo[%d] = true;\n", i);
                todo[i] = true;
            } else {
                todo[i] = false;
            }
        }
//      for (int i = 0; i < n; i++) {
//          if (vis[i]) {
//              printf("%c_", name[now - 1]);
//              cout << warpper(i) << ',';
//          }
//      }
        fprintf(stderr, "Level %d finished.\n", now);
    }
    printf("z_0=-1\\end{cases}$$");
    return 0;
}
/*
abcdefghklopqrs
123456789012345
a - 1 - 2
b - 2 - 4
c - 3 - 8
d - 4 - 16
e - 5 - 32
f - 6 - 64
g - 7 - 128
h - 8 - 256
k - 9 - 512
l - 10 - 1024
o - 11 - 2048
p - 12 - 4096
q - 13 - 8192
r - 14 - 16384
s - 15 - 32768
*/

看的时候要倒过来，在我的计算机上运行了 70s。

你要知道当时 Hermes 搞了 10 年，我们只花了一分钟多。