正多角形の対角線の交点の数について(GIFあり)
はじめに
この記事は$2022$年$1$月$22$日に開催された日曜数学会で私が発表した内容についての記事です。
私のTwitterのフォロワー$2500$人記念で正多角形の対角線の交点の数に関連する問題を出題したときに見つけた論文の内容について、なかなか興味深い内容でしたので、私はまだ証明の部分は完全には理解できていないですが、理解できた範囲についてご紹介したいと思います。
論文の紹介
まずは、論文のご紹介から。
この論文は、正$n$角形の対角線の交点の数を完全に解析して、$n$の式で表すことができたというものです。さらにその系として、対角線で分割される領域の数も$n$の式で表しています。
実際にやってみるとわかりますが、任意の正$n$角形の対角線の交点の数を求めることは非常に難しいです。この論文は$1995$年に発表されたもので、$2006$年にv3版にアップデートされています。
つまり、今から $27$ 年前に公式ができた、ということです。割と最近まで公式化されていなかったということで、このことからも、この問題がなかなか難しい問題であることがわかるのではないでしょうか。
きっかけのツイート
この論文を見つけるきっかけとなったのは次の問題を作問したときでした。
==以下引用==
フォロワー2500人突破記念問題
— ａｐｕ (@apu_yokai) July 1, 2021
図のように正17角形のケーキを全ての対角線で切ってバラバラにしたら、何人に分けることができるでしょうか。
なお、大きさが不公平なのは気にしなくてかまいません。 pic.twitter.com/c2kpK01MRS
==引用おわり==
交点の数の上限
正$17$角形を対角線でバラバラにするといくつの領域に分かれるか、という問題です。
正$17$角形の対角線の交点の数がわかれば、それをもとに領域の数を計算できるので、まず対角線の交点の数を計算する必要があります。
そして、正$17$角形の対角線の交点の数は、「$n$が奇数のとき、正$n$角形について$3$本以上の対角線が共点となる($1$点で交わる)ことはない」という性質を使えば手計算できます。
この記事を最後まで読めばこの問題の答えがわかるはずですので、ここではこの問題はいったん棚に上げておいて、一般化した「正(奇数)角形の対角線の交点の数」の計算方法について解説したいと思います。
正多角形の対角線の交点の数の上限は二項係数でわかる
正$n$角形の頂点を$4$つ選ぶと、対角線の交点が$1$つ対応することから、${n \choose 4}$ は交点の数の上限になります。$n$が奇数のときは$3$本以上の対角線が共点となることはないことから、上限はそのまま実際の対角線の数となります。
※ ${n \choose 4}$ は二項係数の表し方の一つです。つまり ${n \choose 4}={}_nC_4$
対角線の交点の数の上限$={n \choose 4}$
nが奇数のときの対角線の交点の数$={n \choose 4}$
$n$が偶数のときは、$3$本以上の対角線が共点となることがありますので、 ${n \choose 4}$ は交点の数の上限にはなりますが、実際の交点の数はこれより少なくなります。
正多角形の対角線の交点の数の公式
$n$ が奇数のときは対角線の交点の数は簡単にわかるのですが、偶数のときはとても難しいです。
偶数のときは $3$ 本以上の対角線が $1$ 点で交差することがあるのですが、そのパターンが非常に多くて調べ上げるのがすごく大変なのです。
しかし、上記の論文ではそのすべてのパターンを調べ上げて公式を作ったのです。
まずは、論文で紹介されている公式をご紹介します!
ここからは、$I(n)$ で正$n$角形の対角線の交点の数を表します。また、 $\delta_m(n)$ は$n$ が $m$ の倍数のとき $1$ 、それ以外のときは $0$ となる関数です。
$ \begin{align} I(n) = &{n \choose 4} + \frac{−5n^3 + 45n^2 − 70n + 24}{24} · δ_2(n)\\ & − \frac{3n}{2} · δ_4(n)+ \frac{−45n^2 + 262n}{6} · δ_6(n) \\ &+ 42n · δ_{12}(n) + 60n · δ_{18}(n)\\ &+ 35n · δ_{24}(n) − 38n · δ_{30}(n) \\ &− 82n · δ_{42}(n) − 330n · δ_{60}(n)\\ &− 144n · δ_{84}(n) − 96n · δ_{90}(n)\\ & − 144n · δ_{120}(n) − 96n · δ_{210}(n) \end{align} $
$\delta_m(n)= \begin{cases} 1 &\qquad \text{if }\, n\equiv 0\,\,(\mod m),\\ 0 &\qquad \text{otherwise.} \end{cases}$
$n$ に具体的な値を代入して計算すると次のようになります。
| $n$ | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | $\cdots$ |
| $I(n)$ | 0 | 1 | 5 | 13 | 35 | 49 | 126 | 161 | $\cdots$ |
公式を分解する
もう少しくわしく、公式をみていきましょう。
実は、先ほどの公式を次のように分解することができます。
ここで、$a_k(n)$ は、正 $n$ 角形のちょうど $k$ 本の対角線が中心以外の場所で交わる点の数を表しています。
$ I(n) = δ_2(n)+a_2(n)+a_3(n)+a_4(n)+a_5(n)+a_6(n)+a_7(n) $
$
\begin{align}
a_2(n)=&n\Biggl(\frac{n^{3}-6n^{2}+11n-6}{24}+\frac{-5n^{2}+46n-72}{16}d_2\left(n\right)-\frac{9}{4}d_4\left(n\right)+\\
&+\frac{-19n+110}{2}d_6\left(n\right)+54d_{12}\left(n\right)+84d_{18}\left(n\right)+50d_{24}\left(n\right)-24d_{30}\left(n\right)-100d_{42}\left(n\right)\\
&-432d_{60}\left(n\right)-204d_{84}\left(n\right)-144d_{90}\left(n\right)-204d_{120}\left(n\right)-144d_{210}\left(n\right)\Biggr)
\end{align}
$
$
\begin{align}
a_3(n)=&n\Biggl(\frac{5n^{2}-48n+76}{48}d_2\left(n\right)+\frac{3}{4}d_4\left(n\right)+\frac{7n-38}{6}d_6\left(n\right)\\
&-8d_{12}\left(n\right)-20d_{18}\left(n\right)-16d_{24}\left(n\right)-19d_{30}\left(n\right)+8d_{42}\left(n\right)\\
&+68d_{60}\left(n\right)+60d_{84}\left(n\right)+48d_{90}\left(n\right)+60d_{120}\left(n\right)+48d_{210}\left(n\right)\Biggr)
\end{align}
$
$
\begin{align}
a_4(n)=&n\Biggl(\frac{7n-42}{12}d_6\left(n\right)-\frac{5}{2}d_{12}\left(n\right)-4d_{18}\left(n\right)+3d_{24}\left(n\right)+6d_{42}\left(n\right)\\
&+34d_{60}\left(n\right)-6d_{84}\left(n\right)-6d_{120}\left(n\right)\Biggr)
\end{align}
$
$
a_5(n)=n\left(\frac{n-6}{4}d_6\left(n\right)-\frac{3}{2}d_{12}\left(n\right)-2d_{24}\left(n\right)+4d_{42}\left(n\right)+6d_{84}\left(n\right)+6d_{120}\left(n\right)\right)
$
$
a_6(n)=n\left(4d_{30}\left(n\right)-4d_{60}\left(n\right)\right)
$
$
a_7(n)=n\left(d_{30}\left(n\right)+4d_{60}\left(n\right)\right)
$
$I(n)$ のそれぞれの項の意味は次のようになります。
$ I(n) = \underbrace{δ_2(n)}_{\text{中心の交点の数}}+\underbrace{a_2(n)+a_3(n)+a_4(n)+a_5(n)+a_6(n)+a_7(n)}_{\text{ちょうど2～7本の対角線の交点(中心除く)の数}} $
この式をよく見ると、いろいろなことがわかります。
・中心を除くと対角線は最大 $7$ 本が共点となる。$8$ 本以上が共点となることはない。
・中心以外で $7$本が共点となるのは $n$ が $30$ の倍数のとき
・中心以外で $6$本が共点となるのは $n$ が $30$ の倍数であって $60$ の倍数でないとき
・$n$ が $6$ の倍数でないときに中心以外で共点となる対角線は最大 $3$ 本
・$n$ が奇数のときに共点となる対角線は最大 $2$ 本
上記の式は複雑そうに見えるかもしれませんが、これらのことは簡単に確認できますので上記の式と見比べてみてください。
正$30$角形は特別
次に、正$30$角形の場合についてみてみましょう。
$n=30$ のとき、初めて$a_7(n)$がゼロでなくなります。(つまり、初めて $7$ 本の対角線が中心以外で共点となる。)
さらにこのとき、$a_2(n)$～$a_7(n)$ がすべてゼロではなくなります。
そのことを実際に確かめてみましょう。
また、$\frac{a_6(n)}{n}$ と $\frac{a_7(n)}{n}$ のとりうる値は次のように$2$種類又は$3$種類しかありません。
$ \frac{a_6(n)}{n}= \begin{cases} 4 &\qquad \text{if }\, n\equiv 0\,\,(\mod 30)\, \land n\not\equiv 0\,\,(\mod 60) ,\\ 0 &\qquad \text{otherwise.} \end{cases} $
$ \frac{a_7(n)}{n}= \begin{cases} 5 &\qquad \text{if }\, n\equiv 0\,\,(\mod 60)\,\\ 1 &\qquad \text{if }\, n\equiv 0\,\,(\mod 30)\, \land n\not\equiv 0\,\,(\mod 60) ,\\ 0 &\qquad \text{otherwise.} \end{cases} $
このことは、対角線$6$本以上が共点となるのは、本質的に正$30$角形のときにあらわれる$5$つのパターンしかないことを意味しています。(左辺について $n$ で割っていることに注意してください。)
具体的には、次の図の $5$ 点のみが本質的に対角線$6$本以上が共点となりうる位置であり、$n$ が $60$ の倍数のときは、対角線$6$本以上共点となりうる位置は全て対角線$7$本共点となるということになります。
対角線で分割される領域数を数える
さて、先ほど対角線の交点の数を、共点となる対角線の本数ごとに分解して計算する式が得られましたので、この式を使うことで、対角線で分割される領域数を数えることができます。
ここからは、正 $n$ 角形が対角線で分割される領域の数を $R(n)$ で表すことにします。
すると、次のように計算することができます。
$ \begin{align} R\left(n\right)=&1+\frac{n\left(n-3\right)}{2}+\left(\frac{n}{2}-1\right)\delta_2\left(n\right)\\ &+a_{2}\left(n\right)+2a_{3}\left(n\right)+3a_{4}\left(n\right)+4a_{5}\left(n\right)+5a_{6}\left(n\right)+6a_{7}\left(n\right) \end{align} $
この式の意味は次のようになります。
$ \begin{align} R\left(n\right)=&\underbrace{1}_{最初の１個}+\underbrace{\frac{n\left(n-3\right)}{2}}_{対角線の端}+\underbrace{\left(\frac{n}{2}-1\right)\delta_2\left(n\right)}_{正偶数角形の中心で交差}\\ &+\underbrace{a_{2}\left(n\right)+2a_{3}\left(n\right)+3a_{4}\left(n\right)+4a_{5}\left(n\right)+5a_{6}\left(n\right)+6a_{7}\left(n\right)}_{中心以外の対角線の交点で交差} \end{align} $
次のように考えると理解できると思います。
まず、正 $n$ 角形の形のケーキを対角線に沿ってゆっくり切るところをイメージすると、他の対角線と交差するとき又は先端がケーキの端に達したときに領域が１つ増えますね。
そのことから、先端が他の対角線と交差する回数とケーキの端に達する回数を数えれば分割される領域の数がわかるというわけです。
具体的な値は次のようになります。
| $n$ | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | $\cdots$ |
| $I(n)$ | 0 | 1 | 5 | 13 | 35 | 49 | 126 | 161 | $\cdots$ |
| $R(n)$ | 1 | 4 | 1 | 24 | 50 | 80 | 154 | 220 | $\cdots$ |
領域の数を数えるもう一つの方法
なお、論文の方ではこのような考え方ではなく、まず対角線の交点を多面体の頂点とみなした場合の「辺」の数を数え、オイラーの多面体定理 $V − E + F = 2$ をあてはめるという方法で $R(n)$ を計算しています。もちろん、どちらの方法で計算しても結果は一致します。
論文での証明のアイデア
初めに書いた通り、私は論文の内容を理解できたわけではないですが、ここからは、私がわかった範囲で論文のアイデアを紹介します。
正多角形の対角線の交点の数についての問題を、チェバの定理の派生版を使って三角関数版ディオファントス方程式の問題に帰着して、まず$3$本の対角線が共点となるパターンを見つけます。そして、$3$本の対角線が共点となる可能性のある配置を注意深く分析すれば、理論的には公式を導き出すのに十分な情報が得られると考えられます。しかし、それは非常に複雑であるため、まず答えの形だけを推測し，次に結果を正確に決定できるほど十分な数の計算を行った、ということのようです。
解析にあたり、円分多項式の性質やガロア群を使って効率的なアルゴリズムを作ったということのようです。
それでも手計算では複雑な場合分けを完璧に行うことは難しかったらしく、最終的にはコンピュータの力も借りてすべてのパターンを調べ上げたそうです。
論文によれば、実は、$1936$年にもGerrit Bolという数学者が同様の方法で同様の公式を作っていたのですが、残念ながら一部の係数が誤っていたそうです。
このことからも、容易には計算できないことが感じられますね。
「ようです」「そうです」と続きましたが、私自身よくわかっていません。間違っていたらゴメンネ。
ここからは、私に理解できた範囲で、論文のアイデアをもう少しかみ砕いていきます。
$3$本の対角線が共点となる条件
論文のアイデアは、まず３本の対角線が共点となる条件についての問題を次の関係で式に表すというものでした。
対角線$AD,BE,CF$ が$1$点で交差するとき
$ \dfrac{AF}{FB} \cdot\dfrac{BD}{DC} \cdot\dfrac{CE}{EA} =1 $
相似を使って証明できます。
$\triangle AFP \text{∽} \triangle CDP ,\,\,\,\,\triangle BDP \text{∽} \triangle AEP ,\,\,\,\,\triangle CEP \text{∽} \triangle BFP$ より
$\dfrac{AF}{CD}=\dfrac{PF}{PD}$
$\dfrac{BD}{AE}=\dfrac{PD}{PE}$
$\dfrac{CE}{BF}=\dfrac{PE}{PF}$
辺々掛け合わせて
$ \dfrac{AF}{FB} \cdot\dfrac{BD}{DC} \cdot\dfrac{CE}{EA} =1 $
三角関数版ディオファントス方程式
図の円の半径を $1$ (つまり単位円)とします。
弧の長さを図のように $u,v,w,x,y,z$ として、さきほどの式を書き直します。
$ \dfrac{AF}{FB} \cdot\dfrac{BD}{DC} \cdot\dfrac{CE}{EA} =1 $
を $u,v,w,x,y,z$ で書き換えると
$ \dfrac{2\sin(x/2)}{2\sin(u/2)} \cdot\dfrac{2\sin(y/2)}{2\sin(v/2)} \cdot\dfrac{2\sin(z/2)}{2\sin(w/2)} =1 $
$ \therefore \sin(u/2)\sin(v/2)\sin(w/2) =\sin(x/2)\sin(y/2)\sin(z/2) $
なお、逆も成り立つので、この式は単位円の$3$本の弦が共点となるための必要十分条件を与えていることになります。
さらに、$U=\dfrac{u}{2\pi}$ のように書き換えると、次のような不定方程式の形になります。
$\sin(\pi U)\sin(\pi V )\sin(\pi W) = \sin(\pi X)\sin(\pi Y)\sin(\pi Z)$
$U +V +W+X+Y +Z = 1$
論文ではこの不定方程式を"trigonometric diophantine equation"と呼んでいます。直訳すれば「三角関数版ディオファントス方程式」といったところでしょうか。
ここからは、この不定方程式の有理数解のパターンを分析することになります。
複素数の不定方程式を作る
先ほどの式に $\sin(\theta)=\frac{e^{i\theta} - e^{-i\theta}}{2i}$ を使い、両辺に $(2i)^3$ を掛けて展開し、$U+V +W = 1 -(X +Y +Z)$ を使って整理すると次の式が得られます。
$−e^{iπ(V+W−U)} +e^{−iπ(V+W−U)} −e^{iπ(W+U−V) }+e^{−iπ(W+U−V)} −e^{iπ(U+V−W)} +e^{−iπ(U+V−W)} = −e^{iπ(Y+Z−X)} +e^{−iπ(Y+Z−X)} −e^{iπ(Z+X−Y)} +e^{−iπ(Z+X−Y)} −e^{iπ(X+Y−Z)} +e^{−iπ(X+Y−Z)}$
すべての項を左辺に移動し、マイナス記号を$e^{-iπ}$に変換し、$i =e^{iπ/2}$を掛けて、
$α_1 = V+W-U-1/2 $
$α_2 = W+U-V-1/2 $
$α_3 = U+V-W-1/2 $
$α_4 = Y+Z-X+1/2 $
$α_5 = Z+X-Y+1/2 $
$α_6 = X+Y-Z+1/2 $
としてみると、このようになります。
$ \sum_{j=1}^{6}e^{i\pi\alpha _j}+\sum_{j=1}^{6}e^{-i\pi\alpha _j}=0 $
このとき
$\sum_{j=1}^{6} α_j = U+V +W+X+Y+Z =1$
です。
逆に、和が $1$ になり上式を満たす有理数 $α_1,α_2,α_3,α_4,α_5,α_6$（必ずしも正ではない）があれば、$U,V,W,X,Y,Z$ が復元できます（例えば、$U＝（α_2＋α_3）/2＋1/2$ のように）。
ただし、この場合、解が正になることを確認する必要があります。
さらに一般化して考える
論文では、さらに一般化して
$\sum_{i=1}^{k}a_i \eta_i=0$
のような関係を考察していきます。
ここで、$a_i$は正の整数で、$η_i$は相異なる１の冪根です。
このような関係を満たすパターンは有限で、円分多項式やガロア群を使って分類できるようです。ここから先の論文の内容は私の理解を超えていますので、どなたか論文を読み解いていただけるとうれしいです。
おまけ(チェバの定理との関係)
ところで、この式の形がいわゆるチェバの定理と同じ形であることにお気づきでしょうか。
$ \dfrac{AF}{FB} \cdot\dfrac{BD}{DC} \cdot\dfrac{CE}{EA} =1 $
実際、チェバの定理と密接な関係があります。
そのことに関して、偶然みつけたこちらのPDFに興味深い記事がありました。なかなか面白いと思いますのでご紹介します。
おわりに
とりあえず、現時点でわかっている範囲の情報をまとめたつもりです。
足りない部分も多々あると思いますが、適宜フォローしていただけるとありがたいと思います。
最後に、記事中の式などを含むDesmosファイルを置いておきますので、いろいろ遊んでみてください。