2017-07-24

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

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

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

しかし、実は3元の巡回置換を使えば全ての偶置換を作ることができます。すなわち、 $S_n$ を $n$ 次の対称群、 $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$

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

2017-07-22

振り子の幾何学

初等幾何

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

このとき、「糸がたるみ始める地点」と「球が落下して糸がピンと張る地点」の間には綺麗な関係があります。実は鉛直上方向から角度を測ると、角度の比（図の $\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-1$ 、 $AC:y=0$ 、 $BD:y=k(x-a)$ の場合に帰着できる。 $B,D$ の $x$ 座標をそれぞれ $\alpha,\beta$ とすると、これらは $x^2-1=k(x-a)$ の解なので

となり成り立っている。 $~~~\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,BD$ と $x$ 軸のなす角を $\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$ となることを表しています。

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

2017-07-20

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

初等幾何

$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次元に生きていて本当によかったですね。

2017-07-20

奇跡の楕円曲線と144

Fibonacci

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

$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^2m$ （ $m$ は平方因子を持たない）とすると $m$ は $x^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の定理によれば、このような数は $1$ と $144$ しか存在しない。これについては以下の記事に詳しい証明がある。

integers.hatenablog.com

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

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

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

2017-07-17

石取りゲームとFibonacci数

組み合わせ論 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-b$ が $F_{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$ となり矛盾する（一般に $x$ がFibonacci数の時 $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数が現れるのは面白いですね。

2017-07-14

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

ζ 積分

バーゼル問題とは $\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$

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

2017-07-13

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

$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$