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$

f:id:fibonacci_freak:20170713032317p:plain

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

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

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

2017-07-12

Fibonacci数を隠し持つ積分

Fibonacci 積分

次の定積分の値は何になるでしょうか？

$\displaystyle{I=\int_0^1 \log(1 + 4\cos^2 \pi x) dx}$

実はこの積分はFibonacci数と深い関係があります。
被積分関数は $x = 1/2$ を挟んで対称なので

$\displaystyle{I=2\int_0^{1/2}\log(1 + 4\cos^2\pi x) dx\\= \int_0^1\log\left(1+4\cos^2\dfrac{\pi x}{2}\right)dx\\=\lim_{n\to\infty}\dfrac{1}{n}\sum_{k=1}^{n-1}\log\left(1+4\cos^2\frac{k\pi}{2n}\right)\\=\lim_{n\to\infty}\frac{1}{n}\log\left(\prod_{k=1}^{n-1}\left(1+4\cos^2\frac{k\pi}{2n}\right)\right).}$

ここで $\log$ の中身の積の部分に注目します。これは実はFibonacci数になっています（！）Fibonacci数とは

$F_1=F_2=1, F_{n+2}=F_{n+1}+F_n$

で定義される数列でした。 $\zeta_n = \exp\left(\dfrac{2\pi i}{n}\right), \phi=\dfrac{1+\sqrt5}{2},\bar\phi=\dfrac{1-\sqrt5}{2}$ と置きます。 $\phi,\bar\phi$ は $x^2=x+1$ の2解なので

$\phi^2+\bar\phi^2=3\\ \phi^2- \bar\phi^2=\sqrt5\\ \phi\bar\phi=-1$

などがわかります。またFibonacci数の一般項は

$F_n=\dfrac{\phi^n-\bar\phi^n}{\sqrt5}$

と書くことができます。
さて、半角公式を使うと先ほどの積の部分は

$\displaystyle{\prod_{k=1}^{n-1}\left(3+2\cos\frac{k\pi}{n}\right)\\ =\prod_{k=1}^{n-1}\left(\phi^2+\bar\phi^2-2\phi\bar\phi\cos\frac{k\pi}{n}\right)\\ =\frac{\phi^2-\bar\phi^2}{\sqrt5}\prod_{k=1}^{n-1}(\phi-\zeta_{2n}^k\bar\phi)(\phi-\zeta_{2n}^{-k}\bar\phi)\\ =\frac{1}{\sqrt 5}\prod_{k=0}^{2n-1}(\phi-\zeta_{2n}^k\bar\phi)\\ =\frac{\phi^{2n}-\bar\phi^{2n}}{\sqrt 5}=F_{2n}}$

となり、確かにFibonacci数が出てきました！
よって最初の積分の値は

$\displaystyle{I=\lim_{n\to\infty}\frac{\log F_{2n}}{n}\\=\lim_{n\to\infty}\frac{1}{n}\left(\log \phi^{2n}-\log\sqrt5+\log\left(1-\frac{1}{\phi^{4n}}\right)\right)\\ =2\log\phi}$

と求まります。

なお、この方法はより一般に $\log(a+b\cos x)$ 型の積分にも応用できます。ぜひ考えてみてください。

2017-07-10

立方体の"あの角度"

無理数

立方体 $ABCD-EFGH$ において、 $\angle{AGF}$ の大きさが何度になるか知っていますか？

f:id:fibonacci_freak:20170710153900p:plain

$\triangle{AGF}$ に着目して逆三角関数を使えば、この角度は $\arctan \sqrt 2$ と表すことができます。これは果たして有理数度（弧度法で（有理数） $\times \pi$ ）になるのでしょうか？

実は、より一般に次のことが示せます。しかも高校数学のみで！

定理. $\arctan\sqrt n\in\mathbb{Q}\pi$ となる正整数 $n$ は $1,3$ のみである。特に $\arctan\sqrt 2\not\in\mathbb{Q}\pi$ .

証明. 十分性は $\arctan 1=\dfrac{\pi}{4},~\arctan \sqrt{3}=\dfrac{\pi}{3}$ より良い。 $\arctan\sqrt n=\arg(1+\sqrt{-n})\in\mathbb{Q}\pi$ となるとき、正整数 $m$ が存在して $(1+\sqrt{-n})^m\in \mathbb{R}$ となる。さらにこれは