フィボナッチ・フリーク

数学の小ネタ集。

あるサイズの巡回置換だけで任意の置換を作る

任意の置換は互換の積に表すことができます。では同じように、3元の巡回置換(i~j~k)i,j,kは相異なる)だけを組み合わせて任意の置換を作ることはできるでしょうか?

答えはNoです。(i~j~k)=(i~k)(i~j)(置換は右から合成する)と書けるので、3元の巡回置換は偶置換です。偶置換の積は偶置換なので、この方法では偶置換しか作ることができません。

しかし、実は3元の巡回置換を使えば全ての偶置換を作ることができます。すなわち、S_nn次の対称群、A_n交代群とし、k元の巡回置換で生成されるS_nの部分群をT^{(k)}_nとすると、次が成り立ちます。

命題1. ~T^{(3)}_n=A_n.

証明. 交わる2つの互換の積は3元の巡回置換に他ならず、交わらない2つの互換の積は(i~j)(k~l)=(i~j~k)(j~k~l)なので、2つの互換の積は必ずT^{(3)}_nに入る。A_nはこれらで生成されるからA_n\subset T^{(3)}_nである。逆の包含は3元の巡回置換が偶置換であることから明らか。~~~\square

実はより一般に次が成り立ちます。

命題2. ~kが奇数のときT^{(k)}_n=A_n.

証明. 命題1より、任意のk\geq 5について(3~4~5)\in T^{(k)}_nを示せばよい(すると対称性から任意の3元の巡回置換を含む)。

(k~(k-1)~\cdots~1)^2(1~2~4~3~5~6~~\cdots~k)^2=(1~2)(3~4)

より(1~2)(3~4)\in T^{(k)}_nであり、同様に(1~2)(3~5)\in T^{(k)}_nなので(3~4~5)=(1~2)(3~5)(1~2)(3~4)\in T^{(k)}_nとなる。~~~\square

ではkが偶数のときはどうなるでしょうか。

この場合、なんと任意の置換を作ることができます!以下の証明は箱(@o_ccah)さんから教えていただきました。

命題3. ~kが偶数のときT^{(k)}_n=S_n.

証明. k=2mとする。(1~2)\in T^{(k)}_nを示せばよい。

\sigma = (2~4~6~\cdots~2m~1~3~5~\cdots~(2m-1))\\ \tau=(1~2~\cdots~2m)

と置く。\tau^2\sigma^{-1}=(1~2)なので示された。~~~\square

このように、あるタイプの置換で生成される置換の全体を求めることは、しばしば面白いパズルになります。皆さんも是非オリジナルの置換パズルを考えてみてください。

振り子の幾何学

振り子に勢いよく初速を与えると、跳ね上がって糸がたるむことがありますね。

このとき、「糸がたるみ始める地点」と「球が落下して糸がピンと張る地点」の間には綺麗な関係があります。実は鉛直上方向から角度を測ると、角度の比(図の\theta_1:\theta_2)は必ず1:3になるのです!(図は不正確ですがご容赦ください)

f:id:fibonacci_freak:20170722221034p:plain

この現象には次のような数学的な背景があります。

命題. 軸がy軸に平行な放物線上に4点A,B,C,Dをとる。AC,BDの交点をPとする。A,B,C,D,Pからx軸に下ろした垂線の足をA',B',C',D',P'とすると、
A'P'\cdot P'C'=B'P'\cdot P'D'.

f:id:fibonacci_freak:20170722223938p:plain

この命題は円に対する方べきの定理の放物線における類似なので、俗に「放べきの定理」などと呼ばれています。

証明. 適当に線形変換(行列表示の右上成分が0のもの)と平行移動をすることで、放物線がy=x^2-1AC:y=0BD:y=k(x-a)の場合に帰着できる。B,Dx座標をそれぞれ\alpha,\betaとすると、これらはx^2-1=k(x-a)の解なので

B'P'\cdot P'D'=|a-\alpha|\cdot|a-\beta|\\=|x^2-1-k(a-a)|\\=|x+1|\cdot|x-1|\\=A'P'\cdot P'C'

となり成り立っている。~~~\square

これを使うと、円と放物線の交点の性質が明らかになります。

命題. x軸に平行な軸を持つ放物線と単位円が図のように4点A,B,C,Dで交わっているとする。x軸正方向からA,B,C,Dまで反時計回りに測った角の大きさをそれぞれa,b,c,dとすると
a+b+c+d=0~\mathrm{mod}~2\pi.
f:id:fibonacci_freak:20170722221701p:plain

証明. 2\piの差は無視されるので、図のような角の取り方のみで示せばよい。AC,BDx軸のなす角を\theta,\phiとする。AC,BDの交点をPとすると、通常の方べきの定理より

AP\cdot PC=BP\cdot PD.

一方上の命題から

AP\cdot PC\cos^2\theta=BP\cdot PD\cos^2\phi.

ゆえに\theta=\phiがわかる。\dfrac{a+c}{2}=\dfrac{\pi}{2}-\theta=\dfrac{\pi}{2}-\phi=~\dfrac{(2\pi-b)+(2\pi-d)}{2}なので命題を得る。~~~\square

 

さて、これがどう振り子と関係するのでしょうか。

振り子が跳ね上がる際、糸がたるみ始めるまでは球は円周上を動きます。糸がたるむと、球は重力によって放物線を描きます。たるむ瞬間に球に撃力が働くことはないので、運動方程式を考えれば、糸がたるむ直前と直後で位置・速度・加速度が一致しています。これはすなわちその点で円と放物線が3重に接していることを表しています。

そこで上の命題で3点A,C,Dが一点に近づく極限を考えれば、それはまさしく冒頭の図で\theta_1:\theta_2=1:3となることを表しています。

実際にこの現象が起きるのか気になった方は、ぜひ実験して確かめてみてください。

広告を非表示にする

根心の存在が自明に思える図

O_1, O_2, O_3を中心とする3円が互いに2点ずつ(A,A',B,B',C,C')で交わっている状況を考えます(下図)。このとき3本の直線AA', BB', CC'は一点で交わります。これを3円の根心と言います。

f:id:fibonacci_freak:20170720195744p:plain

さらっと書いてしまいましたが、本当に一点で交わるの?と疑問に思われる方も多いでしょう(私も初めて聞いたときは驚きました)。このことは方べきの定理を用いて示すことができます。証明は以下に詳しく書かれています。

mathtrain.jp

しかし、実は根心の存在は直感的に明らかな形で理解する方法があります(厳密な証明には向きませんが)。

3つの三角形\triangle{O_1O_2A}, \triangle{O_2O_3B}, \triangle{O_3O_1C}に着目します。

f:id:fibonacci_freak:20170720200752p:plain

ここでこの図を3次元空間内のある平面に置かれたものと考え、それぞれの三角形をO_1O_2, O_2O_3, O_3O_1を軸に回転させると、下図のように三角錐を組み立てることができます。

f:id:fibonacci_freak:20170720201135p:plain

回転させる過程を上から見れば、A,B,Cはそれぞれ直線AA',BB',CC'上を動くので、出来上がる三角錐の頂点(を上から見た点)がちょうど根心になっています。

3次元に生きていて本当によかったですね。

奇跡の楕円曲線と144

私が最も好きな不定方程式の一つに、次のものがあります。

y^2=x^3+20x

いわゆる楕円曲線の一種です。この方程式の整数解は全部でいくつあるでしょうか?

まず方程式の形からx\geq0がわかります。順に試していけばすぐに(x,y)=(0,0),(4,\pm12),(5,\pm15)という解が見つかります。ここから先はなかなか解が現れず、これで全てであるかのように思われます。

しかしこの方程式はそんなつまらないものではありません。実はこんな解もあるのです。

(x,y)=(720,\pm19320)

大きい解ですね。実際計算してみると

19320^2=373262400\\720^3+20\cdot 720=373248000+14400=373262400

となり、確かに解になっています。一般にこのような大きな解がある不定方程式は手計算では解くことが難しいです。しかしこの方程式に限っては、実に鮮やかな方法でこの解を求めることができます。まさに奇跡の楕円曲線というわけです。

以下の方法は私が今年たまたま見つけたものですが(恐らくもっと昔から知られているとは思いますが)、発見した日の晩は興奮して眠れませんでした。

さて、準備としてPell方程式について復習しておきましょう。

補題. ~x^2-5y^2=4の正整数解は
\dfrac{x+y\sqrt5}{2}=\phi^{2n}~(n\geq1)
なる(x,y)で与えられる。ここで\phi=\frac{1+\sqrt5}{2}黄金比)。

証明は以下のサイトなどに丁寧にまとめられています。

IMOmath: Pell's Equations

それでは本題の証明に入りましょう。

命題. ~y^2=x^3+20xの整数解は(x,y)=(0,0),(4,\pm12),(5,\pm15),(720,\pm19320)のみである。

証明. x\gt0のみ考えればよい。y^2=x(x^2+20)因数分解する。xが平方数の場合、x^2+20も平方数なのでx=4,y=\pm12となる。平方数でない場合x=s^2mmは平方因子を持たない)とするとmx^2+20を割り切るので、特に20を割り切る。ゆえにm=2,5,10のいずれかである。

m=2の場合、x(x^2+20)=(2s)^2(2s^4+10)で、2s^4+10\equiv 2~\mathrm{mod}~5は平方数とはなりえないので不適(2\mathrm{mod}~5で平方元でない)。

m=10の場合、もとの方程式に代入すれば

\left(\dfrac{y}{10}\right)^2=2s^2(5s^4+1)

となる。右辺の素因数2の数を考えればsは奇数であり、また左辺は偶数なので4Y^2と書ける。このとき

\left(\dfrac{Y}{s}\right)^2=\dfrac{5s^4+1}{2}\equiv3~\mathrm{mod}~5

なので不適(3\mathrm{mod}~5で平方元でない)。

m=5の場合、もとの方程式に代入すれば

\left(\dfrac{y}{5}\right)^2=s^2(5s^4+4).

ゆえに5s^4+4は平方数でありb^2と書くことができる。

b^2-5s^4=4

なので補題(Pell方程式)よりあるnが存在して

\dfrac{b+s^2\sqrt5}{2}=\phi^{2n}

\therefore s^2=\dfrac{\phi^{2n}-\bar\phi^{2n}}{\sqrt5}=F_{2n}

(ただし\bar\phi=\dfrac{1-\sqrt5}{2}F_nはFibonacci数)となり、s^2偶数番目のFibonacci数かつ平方数である。Cohnの定理によれば、このような数は1144しか存在しない。これについては以下の記事に詳しい証明がある。

integers.hatenablog.com

よってx=5s^2=5または720となり、このときそれぞれy=\pm15,\pm19320が解を与える。~~~\square

 

というわけで、720という解はFibonacci平方数である144に由来していたのです。

ところで14412の二乗で、なおかつ12番目のFibonacci数です。12という数字は数学の至る所で重要な役割を果たしています。モジュラー形式\Deltaのウェイトは12ですし、代数曲面論のNoetherの公式には12が含まれます。そしてそれらを繋ぐ組み合わせ論的な定理である12点定理 というものも知られています。私は密かに、Fibonacci平方数144もこれらの12と関係しているのでは、などと妄想しています。

広告を非表示にする

石取りゲームとFibonacci数

2人で次のようなゲームをします。

石がn個積まれている(n\geq2)。交互に1つ以上の石を取り去り、最後の石を取れば勝ちである。ただし次のルールを守らなければいけない。

(1) 先手は最初に全ての石をとってはいけない。

(2) 相手が直前に取った石の数の2倍より多く取ってはいけない。

さて、このゲームに必勝法はあるのでしょうか?

実は次のことが成り立ちます。

命題. 上のゲームはnがFibonacci数のとき後手必勝、それ以外のとき先手必勝である。

ここでFibonacci数とはF_1=F_2=1, F_{n+2}=F_{n+1}+F_nで定義される数列です。これを示すには次の事実を用います。

定理. 任意の正整数nは、隣り合わないいくつかのFibonacci数F_m(m\neq 1)の和に一意的に表される。これをZeckendorf表示という。

たとえば53=34+13+5+1=F_9+F_7+F_5+F_2などです。

証明.  n=1の時は明らか。n\gt 1のときF_m\leq nなる最大のmをとると、帰納法の仮定よりn-F_mは一意的なZeckendorf表示を持つ。最大性よりn-F_mのZeckendorf表示にはF_{m-1}未満のFibonacci数のみ現れるので(そうでなければn\geq F_{m+1}となってしまう)、これとF_mを合わせればnのZeckendorf表示が得られる。

一意性を示すには、F_mを使わなければならないことを示せばよい。F_m未満のFibonacci数のみを用いて表示できる最大の整数はF_{m-1}+F_{m-3}+\cdots+1だが、これは漸化式よりF_{m-2}+F_{m-3}+\cdots+F_1=F_m-1以下であり、これらでnを表すことはできない(最後の式は帰納法で簡単に示せる)。\square

 

さて、Zeckendorf表示を使って上のゲームの必勝法を作ってみましょう。基本的なアイディアは「残りの石の数をZeckendorf表示したとき現れる最小のFibonacci数を取り除く」ことです。

 

命題の証明. xのZeckendorf表示に現れる最小のFibonacci数」をF_{Z(x)}と書くことにする。

nがFibonacci数でなければ、先手はa=F_{Z(n)}個だけ取る。するとZeckendorf表示の性質より残りの数n-a

Z(n-a)\geq Z(n)+2

をみたす。このときFibonacci数の漸化式より F_{Z(n)+2}\gt 2F_{Z(n)}なので後手はF_{Z(n)+2}個以上の石を取ることができず、したがって全ての石を取ることはできない、これを繰り返せば勝てるので、後手が次に取る個数に関わらず繰り返せることを示そう。

後手がb個取ったとし、残りの石の数n-a-bF_{Z(n-a-b)}\gt 2bを満たすと仮定して矛盾を導く。bより真に大きい最小のFibonacci数をF_cとすると、仮定より特に

F_{Z(n-a-b)}\gt 2b\geq 2F_{c-1}\geq F_c

なので

Z(n-a-b)\geq c+1.\tag{1}

一方で後手が操作する前には

F_{Z(n-a)}\geq F_{Z(n)+2}\gt 2F_{Z(n)}\geq b

だったのでcの最小性から

Z(n-a)\geq c.\tag{2}

等号が成立するときは

n-a-b=n-a-F_{Z(n-a)}+(F_{Z(n-a)}-b)

で、括弧内のZeckendorf表示が2b以下のFibonacci数を持つので仮定と矛盾。成立しないときは(1)と(2)を比較すればZ(b)\geq cとなり矛盾する(一般にZ(x-y)\geq\min\{Z(x),Z(y)\}-1であることに注意せよ)。これで先手必勝がわかった。

nがFibonacci数F_mだったとする。先手の操作後にまたFibonacci数F_{m'}が残ると後手が勝つ。なぜなら先手が取る石の数はF_m-F_{m'}\geq F_{m-2}であり、後手はF_{m'}(\leq F_{m-1}\leq 2F_{m-2})個の石をすべて取れるからである。そうでない場合、先ほどの議論を後手に適用することでやはり後手が勝てることがわかる. \square

こんな単純なゲームにFibonacci数が現れるのは面白いですね。

バーゼル問題の二重対数による解法

バーゼル問題とは\displaystyle\sum_{n=1}^\infty \frac{1}{n^2}の値(=\pi^2/6)を求める問題で、当ブログでは以前Calabiによる短い証明を紹介しました。

fibonacci-freak.hatenablog.com

今回はこのバーゼル問題の、二重対数関数(Dilogarithm)という不思議な関数を使った解法を紹介します。

二重対数関数とは|x|\lt 1で収束する級数

\displaystyle\mathrm{Li}_2(x)=\sum_{n=1}^\infty\frac{x^n}{n^2}

で定義される関数です。今回求めたい級数\displaystyle\sum_{n=1}^\infty \frac{1}{n^2}\mathrm{Li}_2(1)と書くことができます(厳密にはx\to 1の極限)。よく知られた\log級数展開

\displaystyle -\log(1-x)=\sum_{n=1}^\infty \frac{x^n}{n}

xで割り1回積分することで、積分表示

\displaystyle \mathrm{Li}_2(x)=-\int_0^x\frac{\log(1-t)}{t}dt

が得られます。被積分関数[1,\infty)を除いて一価正則に定義できるので、その領域内での線積分によって逆に\mathrm{Li}_2(x)を定めれば定義域を\mathbb{C}\setminus[1,\infty)に延長(解析接続)して考えることができます。以下この延長を考えます。

さて、この関数の性質を見ていきましょう。

命題1. \displaystyle\mathrm{Li}_2(-1)=-\frac{\mathrm{Li}_2(1)}{2}.

証明. 級数表示より~\displaystyle{\mathrm{Li}_2(1)-\mathrm{Li}_2(-1)=\sum_{n=1}^\infty\frac{2}{(2n)^2}=\frac{\mathrm{Li}_2(1)}{2}}. これを移項すればよい。\square

命題2. \mathrm{Im}~x\gt0に対し、\displaystyle\mathrm{Li}_2(x)+\mathrm{Li}_2\left(\frac{1}{x}\right)=\pi i\log x-\frac{\log^2 x}{2}+2\mathrm{Li}_2(1).

証明. 左辺を微分すると

\displaystyle{\frac{d}{dx}\left(\mathrm{Li}_2(x)+\mathrm{Li}_2\left(\frac{1}{x}\right)\right)\\=\frac{-\log(1-x)+\log(1-1/x)}{x}\\=\frac{1}{x}\left(\log\left|\frac{1-1/x}{1-x}\right|+i\arg\left(\frac{1-1/x}{1-x}\right)\right)\\=\frac{1}{x}\left(-\log|x|+i\arg \left(-\frac{1}{x}\right)\right)\\=\frac{1}{x}(-\log|x|+i(\pi-\arg x))\\=\frac{\pi i-\log x}{x}}.

これは右辺の微分に等しいから両辺の差は定数である。x\to 1の極限を考えると両辺ともに2\mathrm{Li}_2(1) となるので一致することがわかる。\square

いよいよ本題のバーゼル問題です。

定理. \displaystyle\mathrm{Li}_2(1)=\sum_{n=1}^\infty \frac{1}{n^2}=\frac{\pi^2}{6}.

証明. 命題2において\mathrm{Im}~x\gt 0から近づくようにx\to-1の極限をとると

\displaystyle 2\mathrm{Li}_2(-1)=-\frac{\pi^2}{2}+2\mathrm{Li}_2(1)

これと命題1を合わせれば

\displaystyle{-\mathrm{Li}_2(1)=-\frac{\pi^2}{2}+2\mathrm{Li}_2(1)\\\therefore \mathrm{Li}_2(1)=\frac{\pi^2}{6}.}~~~~~\square

 

解析接続して函数等式を利用するという手法の強力さがわかる見事な証明ですね

完全有向グラフはハミルトンパスを持つ

n頂点の完全グラフ(n\geq 2)の各辺に向きが与えられたものをn頂点の完全有向グラフといいます。例えば下の図のようなものです。

f:id:fibonacci_freak:20170713030148p:plain

実は完全有向グラフには必ずハミルトンパスが存在します。ハミルトンパスとは全ての頂点を1回ずつ通る道のことです(閉路でなくても構いません)。

頂点AからBへの有向辺が存在することをA\to Bと表すことにします。

定理. 任意の完全有向グラフGにはハミルトンパスが存在する。

証明. 頂点数nについての帰納法で示す。n=2のときは明らか。n\gt 2の場合、頂点を任意に1つとりVとする。G-V(Vを除いた部分グラフ)には帰納法の仮定によりハミルトンパスA_1\to A_2\to\cdots\to A_{n-1}が存在する。V\to A_1またはA_{n-1}\to Vならばそれを道の端に追加することでハミルトンパスを得る。そうでない場合A_1\to VかつV\to A_{n-1}なので、A_i\to VかつV\to A_{i+1}なるi\lt nが存在する(下図)。この時A_1\to\cdots\to A_i\to V\to A_{i+1}\to \cdots\to A_{n-1}なるハミルトンパスが取れる。\square

f:id:fibonacci_freak:20170713030438p:plain

ところで、完全有向グラフの頂点があるハミルトンパスの始点になるための条件は簡単にわかるのでしょうか?これと似た条件として次のような概念を考えてみましょう。

定義. 完全有向グラフの頂点V基点であるとは、Vから任意の他の頂点への道が存在することを指す。先ほどの定理より、基点は必ず存在する。

例えば下の図で左下の頂点は基点です。

f:id:fibonacci_freak:20170713030337p:plain

基点であることは見かけ上「ハミルトンパスの始点」より弱い条件ですが、実は次が成り立ちます。

定理. 完全有向グラフGの頂点Vがあるハミルトンパスの始点になることと基点であることは同値である。

証明. ハミルトンパスの始点ならば基点であることは明らかなので逆を示す。頂点数nについての帰納法による。n=2の場合は明らか。n\gt 2の場合、V\to Aなる頂点A全体のなす部分グラフをSとし、Sの基点V'を取る。これはG-Vの基点でもある。実際W\in G-Vに対しVからの最短のハミルトンパスV\to A\to\cdots\to Wを取れば、V'からAへの(S内の)道とAからWへの道を連結することでV'からWへの道が得られる(下図)。よって帰納法の仮定よりV'を始点とするG-Vのハミルトンパスが存在するので、この先頭にV\to V'を連結すればよい。\square

f:id:fibonacci_freak:20170713032317p:plain

パズルのようで面白いですね。

最後に一つ問題を出したいと思います。解答はここには書きませんので、ぜひ自分で考えてみてください。

問題. 完全有向グラフに含まれる基点の総数は、ちょうど2にはならないことを示せ。