离散傅里叶变换一则:中点多边形谜题

把一个多边形的各边中点相邻连接得到更小的多边形,不断重复,得到的结果会越来越“圆”吗?答案是不一定。

大家好,今天的主题和中点多边形有关,显而易见这个词指的就是开头说的那个意思。为了说明起见,不妨再多看一个例子:

蓝色的多边形是一个与自身的边相交的多边形,或者说非简单多边形——在取它的中点多边形(灰色)时,灰色的点是以“沿着蓝色的边走一圈,途中遇到灰色中点”的顺序连接起来的。

这个例子有一个特别之处:蓝色的多边形和自身相交得十分严重,但是取了第一次中点多边形之后,灰色多边形并没有任何相交,而取了两次中点的橙色多边形甚至是一个凸多边形——其每个内角都不超过180度。

这就引出了三个显而易见的问题:
(1) 自身相交的多边形,取其多次中点多边形之后是否一定会自身不相交?
(2) 自身不相交的多边形,取其多次中点多边形之后是否一定变为凸多边形?
(3) 一个凸多边形,取其多次中点多边形之后是否趋于正多边形?

这实际上是个很好玩的想象力谜题,在此笔者鼓励有兴趣的读者先停下来自己想一想。

 

 

(^o^)っ

 

 

按照从简单到难的顺序公布解答:

(3) 是否定的。一个很扁的长方形会变成一个很扁的菱形,然后变回原始的长方形的相似形。

(既然碰巧说到了就顺带一提,任意四边形的中点四边形都是个平行四边形,所以 “中点多边形可以取到任意形状” 的这个命题也并不成立。)

(1) 是否定的。一个正五角星的中点多边形是一个正五角星。

(2) 也是否定的。请看下面的构造:

假设三条竖直大虚线的距离比是黄金分割 \((\sqrt{5}+1):2\),那么之后的每一个中点多边形的相应三条竖直坐标线的距离比也都是黄金分割,由于它们独特的顶点顺序,得到的多边形要么是凹多边形要么自身相交,永远不会得到凸形。

好吧,我们连续得到了四个否定的答案,这很伤心,但这和今天我们真正要聊的主题已经很接近了:

Berlekamp-Gilbert-Sinden 定理 (1965):

对几乎所有的多边形,前面的命题 (1) 和 (2) 无条件成立,中点多边形将无限趋近于一个“椭圆”的正多边形,且有奇数条边的多边形总是某个其他多边形的中点多边形。

要证明这样的结论,我们将引入离散傅里叶变换的概念,看几个3blue1brown最近的视频或许会帮助理解。

简而言之,以任意n边形的所有顶点的重心为原点建系,将二维欧式平面看做复平面,于是其n个顶点可以由相加为0的n个复数 \((x_0,\ldots,x_{n-1})\) 表示。

取n次单位根 \(\omega_n=\exp(2\pi i/n)=\sqrt[n]{1}\),于是重心在原点的逆时针正n边形可以表示为 \((a\omega_n^i)_{i=0}^{n-1}\),a为任意复数。它的几何意义是从某个点a开始,每次相对原点逆时针旋转 \(1/n\) 周,得到下一个顶点,这样总共得到n个顶点。更一般地,对每个从1到 \(n-1\) 的整数c,可以一次性绕原点转过 \(c/n\) 个圆周,得到一个正n角星 \((a\omega_n^{ci})_{i=0}^{n-1}\)(将正n边形看作一种“特殊”的正n角星)。下图是一个 \(c=2\) 的五角星。

我们这样强行使用复数的原因有两个:每个正n角星的中点多边形都是一个小号的正n角星;且如果使用复数加法,那么线段 \((a,b)\) 的中点 \((a+b)/2\),和线段 \((c,d)\) 的中点 \((c+d)/2\) 相加,等于两条线段之和 \((a+c,b+d)\) 的中点,也即“取中点”和“求和”两个操作无关顺序。因此只要我们能将任意n边形 \(x_i\),表达为若干个正n角星的和 \(\sum_ca_c\omega_n^{ci}\),那么想要计算 \(x_i\) 的中点多边形,只需要先计算每个正n角星 \(a_c\omega_n^{ci}\) 的中点多边形,再重新相加就可以了。

这里离散傅里叶变换的作用就是给出一个这样的正n角星和,我们详细了解一下这一步。假设存在一个这样的和

\[x_i=\sum_{c=0}^{n-1}a_c\omega_n^{ci}\tag{$\dagger$}\]

注意这里多出了一项 \(c=0\),它不是一个正n角星,这是因为从 \(a_0\) 开始构造多角星,它一次只能转过0周,也即是平面上的某个定点。我们之后将说明 \(a_0=0\),所以这一项实际上是不存在的。

总之我们给上式两边同时乘以一个正n角星 \(\omega_n^{-si}\),看看会发生什么:等式右侧变成了 \(\sum_ca_c\omega_n^{(c-s)i}\),这是一些一次转过 \(c-s\) 个 \(1/n\) 圆心角的正n角星。每个正n角星只要绕原点转过了非零的度数回到起点,那么重心就在原点,否则就是一个定点。由于求重心和给复数求和的顺序也无关,我们可以给这个新的和求重心,于是除了定点的那一项以外每一项都变成零,而定点保持不变。在定点处原始存在 \(c=s\),且求重心就相当于求平面内n个点的均值,代入之后我们得到了这样的关系式:

\[\underbrace{\frac1n\sum_{i=0}^{n-1}}_{求重心}\left(x_i\omega_n^{-si}\right)=\underbrace{a_s}_{定点}\tag{$\ddagger$}\]

s可以取任意数,所以这实际上就是我们想要的正n角星 \(a_s\omega_n^{si}\) 的表达了。我们现在只剩下两件事:验证 \(x_i\) 确实是这些正n角星的和,以及之前欠下的 \(a_0=0\)。验证这个和与之前求 \(a_s\) 的方法几乎是一样的:

\[\begin{align*}
\sum_{s=0}^{n-1}a_s\omega_n^{si}&=\sum_{s=0}^{n-1}\left(\frac{1}{n}\sum_{j=0}^{n-1}x_j\omega_n^{-sj}\right)\omega_n^{si}\\
&=\sum_{j=0}^{n-1}\underbrace{\left(\frac{1}{n}\sum_{s=0}^{n-1}x_j\omega_n^{(i-j)s}\right)}_{正n角星的重心}\\
&=\sum_{j=0}^{n-1}
\begin{cases}
0&(j\ne i)\\
x_i&(j=i)
\end{cases}\\
&=x_i
\end{align*}\]

因此这个和式成立,这个把任意n边形 \(x_i\) 联系到正n角星之和的等式组 (†) 和 (‡) 就叫做离散傅里叶变换了。验证 \(a_0=0\) 也不难,由于最早建系时假设的 \(x_i\) 的重心在原点:

\[a_0=\underbrace{\frac{1}{n}\sum_{i=0}^{n-1}x_i}_{x的重心}=0\]

至此为止我们终于将n边形 \(x_i\) 表示为了正n角星之和,下一步就是求每个正n角星的中点多边形了。这其实比上一步容易得多,每个中点正n角星的第一个顶点总是大正n角星的第一条边的中点。我们并不关心这个点相对原点所在的角度,它到原点的距离 \(t_c\) 可以用三角函数求出:

\[t_c=\left|\cos\frac{c\pi}n\right|\]

当c取遍从1到 \(n-1\) 的值时,\(t_c\) 画出了余弦函数绝对值图像的一个先下降再上升的区段,它的最大值在两端,最小值在中心。

然后考虑 \(t_c\) 相对于 \(x_i\) 的几何意义。\(x_i\) 的每一项 \(a_c\omega_n^{ci}\) 都会在取中点后变成一个 \(t_c\) 倍大的小多角星,因为第一个顶点到原点的距离就缩小到了这么多。所以 \(t_c\) 的值越小,这个多角星越容易在取中点之后坍缩;反之亦然,在取很多次中点之后还能幸存的一定是 \(t_c\) 的值最大的那颗正多角星,也即 \(c=1\) 和 \(c=n-1\)。

可以思考一下这意味着什么:这两个正n角星正好是所有多角星里的唯一两个正n边形(因为正n边形的其中一条边只能对应 \(±1/n\) 圆周,而 \(-1/n\) 圆周等于 \((n-1)/n\) 圆周),也就是说 \(x_i\) 在取很多次中点之后一定趋于这两个正多边形的复数和。

我们得知道这两个正多边形的和长什么样子。你可能会想:两个正n边形的和当然仍然是正n边形——但我们的两个正n边形并不完全相同,其中一个逆时针转,另一个顺时针转。这里的一种解决方案是参数化,可以解出这是一个压扁了的正n边形。由于具体过程比较乏味,我随便找了一张维基百科上的动图解释一下背后的几何直观:

没错这就是把万花尺,其中黑色的圆心在逆时针匀速转动,同时绿色的小半径在以同一个角速度顺时针转动,红色点描绘的就是这两个运动的和的轨迹,它是一个椭圆,确切地说由横纵方向两个简谐运动组成。两个正n边形的加和不过是当两个圆每转过 \(1/n\) 圆周就记录一次当下的位置,因此是在椭圆上等时间分布的n个点。椭圆是一个压扁了的圆(或者说拉长了的圆也行),而圆上等时间分布的n个点构成一个正n边形,因此椭圆上等时间分布的n个点就是一个压扁了的正n边形了。——比如说,之前出现过的很扁的长方形和菱形就是被压扁的正方形的例子。

重新回忆一下正n角星加和里的其他项。那些项虽然缩小得比这个椭圆n边形更快,但是当这个椭圆n边形本身扁到只构成一条线段甚至一个点的时候,任何一点来自其它项的微扰都会打乱线段和点的形状,这使得其它的项反而占了主导地位。这也是定理中“几乎所有”这个词的由来:两个正n边形在 \(x_i\) 里的系数本来可以是任意的两个复数,但只有在它们恰好模长相等的时候,中点多边形不会趋于它们的和。

最后值得注意的一点,就是 \(t_c\) 只有在 \(c=n/2\) 的时候才取到零。对每个恒定的c,任一个正n角星和它的中点多角星都有恒定的相似比,因此取中点操作给它们乘上了恒定的常数,准确值是 \((1+\omega_n^c)/2\),但重要的是这个数的模长等于 \(t_c\)。

反过来思考,当n是个奇数的时候 \(t_c\) 不可能为零,也即各个多角星的相似比都不是零,所以可以先把 \(x_i\) 展开成各个多角星的和,再把每个多角星都除以它们的相似比,这样再加起来得到的多边形 \(X_i\),它的中点多边形就恰好等于 \(x_i\) 了。

感谢您的阅读~

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注