2017-08-01

グラフと素数：Erdős-Evansの定理

$0$ から $n-1$ までの整数から相異なる数 $a_1,\cdots,a_r$ を取り、「 $a_i-a_j$ が $n$ と互いに素なら $a_i,a_j$ を結ぶ」という規則で $a_i$ たちを頂点とするグラフを作ってみましょう。例えば $n=8$ として $0,1,2,5,7$ を選ぶと下のようなグラフが得られます（小さい数字は $|a_i-a_j|$ ）。

f:id:fibonacci_freak:20170728000103p:plain

グラフ $G$ をこのような方法で作ることができるとき、 $G$ は $\mathrm{mod}~n$ で表現可能であると言います。

ではどんなグラフが $\mathrm{mod}~n$ で表現可能なのでしょうか。

例えば $n$ を大きな素数として $0,1,\cdots,r-1$ を選べば完全グラフ $K_r$ を作ることができます。また $n=r!$ として $0,1,\cdots,r-1$ を選べば鎖状のグラフが得られます。

サイクルを作るのは少し難しいです。Twitterでこれを出題したところ、＠rudjereverisさんからとてもエレガントな解法を寄せて頂いたのでここで紹介します（私の想定解は間違っていることに後で気づきました…）。

大きな整数 $M$ をとって $n=3\times5\times7\times\cdots\times(2M+1)$ とします。すると考えている範囲で「 $n$ と互いに素 $\Leftrightarrow2$ 冪」としてよいことになります。このとき $0,1,3,7,\cdots,2^i-1, \cdots,2^r-1,2^r$ をとると、これは長さ $r+2$ のサイクルになっています。

さて、本題に入りましょう。実は次の驚くべき事実が成り立ちます！

定理(Erdős-Evans,1989). 任意のグラフはある $n$ に対し $\mathrm{mod}~n$ で表現可能である。

証明のために補題を準備します。

補題. 任意の正整数 $n$ について、 $n$ 個の素数からなる集合 $S$ で次の条件を満たすものが存在する:
【条件】共通部分を持たない任意の部分集合 $A,B\subset S$ について

$\displaystyle{\prod_{p\in A}p-\prod_{q\in B}q}$

は $\prod_{p\in S}p$ と互いに素。

証明. $n$ を固定し、条件を満たす $k$ 個の素数からなる集合で、全ての要素が $3^n$ 以上のもの $S_k$ を帰納的に構成していく。 $k=1$ の時は $3^n$ 以上の素数を任意に取れば良い。 $k\gt1$ の時、新たに加える素数 $p_k$ が満たすべき条件は

$\displaystyle{p_i\nmid p_k\prod_{p\in A}p-\prod_{q\in B}q}$

が任意の $1\leq i\lt k, A,B\subset S_{k-1}(A\cap B=\emptyset)$ に対し成り立つことである。 $p_i\in A$ なら必ず成り立つからそうでない場合のみ考えると、これは

$\displaystyle {p_k\not\equiv\frac{\prod_{q\in B}q}{\prod_{p\in A}p}~\mathrm{mod}~p_i}$

と同値である。右辺の組み合わせは高々 $3^{k-1}(\lt 3^n\leq p_i)$ 通りしかないので、これらをすべて満たす $\mathrm{mod}~p_i$ の剰余類が存在する。中国剰余定理によって $i$ をすべて合わせて考えれば、 $p_k$ はある等差数列中にあればよいことになる。よって算術級数定理より条件をみたす十分大きい $p_k$ を取ることができる。 $~~~\square$

それでは定理を示しましょう。

定理の証明. 表現したいグラフ $G$ に1つの頂点を加え、その補グラフ（辺で結ばれているかどうかを全て反転したグラフ）を $H$ とする。 $H$ の辺の数を $m$ とし、補題の条件を満たす $m$ 個の素数からなる集合 $S$ をとり、各辺に1つずつ素数を割り当てる。 $n=\prod_{p\in S}p$ とし、 $G$ の各頂点に対し「 $H$ で自分に繋がっている辺に割り当てられた素数の積」を選べばよい。 $~~~\square$

如何でしたでしょうか。この証明は美しいですが、算術級数定理を使っているところが少し残念かもしれません。もっと初等的に示せた方がいましたら、ぜひ教えてください。

2017-07-29

2^n+1を割り切る素数の密度は17/24

素数

$2^n+1(n\geq1)$ という数列を考えましょう。

$3,5,9,17,33,65,129,257,\cdots$

これは全て奇数ですから $2$ の倍数は登場しません。 $3,5,11,13,17$ の倍数は上の列に出てきていますね。しかし $7$ の倍数は見当たりません。実はこの列には $7$ の倍数は現れないのです。これは $2^n~\mathrm{mod}~7$ が

$2,4,1,2,4,1,\cdots$

と循環し、 $6$ が現れないことからわかります。

では、 $2^n+1$ の素因数に現れる素数は、素数全体のうちどのくらいあるのでしょうか？

実はHasseによる次の定理(1966)があります。

定理. ある $n\geq1$ について $2^n+1$ を割り切る素数の密度は $\dfrac{17}{24}$ である。

ここで密度とは、 $x$ 以下の素数の個数をを $\pi(x)$ 、その中で条件を満たす素数の個数を $\pi'(x)$ とするとき

$\displaystyle{\lim_{x\to \infty}\frac{\pi'(x)}{\pi(x)}}$

のこと（いわゆる自然密度）とします。

17という数が出てくるところが面白いですね。

今回はこの定理の証明をしたいと思いますが、初等的な証明ではないので、代数的整数論の基本的な知識（円分体における素イデアルの分解など）を仮定します。これについては以下のtsujimotterさんのブログにわかりやすい解説があるので、あまり詳しくない方はそちらも参照してみてください。

tsujimotter.hatenablog.com

さて、ある条件を満たす素数の密度を計算する方法はどんなものがあるでしょうか？

整数論に詳しい人なら、その一つとして真っ先にChebotarevの密度定理を挙げるでしょう。あるいはその特別な場合である次の定理が有名です。

命題1. Galois拡大 $K/\mathbb{Q}$ で完全分解する素数の密度は $\dfrac{1}{[K:\mathbb{Q}]}$ である。

証明は省略しますが、比較的簡単なので今後このブログで紹介するかもしれません。

Hasseによる証明では、素数が $2^n+1$ を割り切るという条件をある代数体における完全分解という条件に書き直すことで、命題1に帰着させるのです。まずはこの書き換えをしていきましょう。議論を簡単にするため、素数は奇素数のみ考えます（こうしても密度には影響しません）。

素数 $p$ が条件を満たさない、つまり $2^n\equiv-1~\mathrm{mod}~p$ が解を持たないためには、 $\mathbb{F}_p^\times\cong \mathbb{Z}/(p-1)\mathbb{Z}$ における $2$ の位数が奇数であることが必要十分です。ここで次の補題を使います。

補題. $\mathrm{ord}_2(p-1)=j$ とする。 $\mathbb{F}_p^\times$ における $a$ の位数が奇数である必要十分条件は

$x^{2^j}\equiv a~\mathrm{mod}~p\tag{1}$

が解を持つことである。

証明. (1)が解を持つならば $a^{(p-1)/2^j}\equiv x^{p-1}\equiv 1~\mathrm{mod}~p$ だから、 $a$ の位数は $(p-1)/2^j$ を割り切り、奇数である。逆に $a$ の位数が奇数 $2m+1$ ならば、原始根 $r$ をとって $a=r^k$ とすると $a^{2m+1}\equiv r^{k(2m+1)}\equiv1~\mathrm{mod}~p$ なので $2^j\mid k$ となり解 $r^{k/2^j}$ が得られる。 $~~~\square$

$2^j\mid p-1$ より $\mathbb{F}_p$ には $1$ の $2^j$ 乗根が全てあるので、上の方程式が解を持つことは

$x^{2^j}-2=(x-a_1)\cdots(x-a_{2^j})~\mathrm{mod}~p$

と一次式の積に分解することと同値です。以上で次が得られました。

命題2. $^\forall n,~p\nmid 2^n+1$ かつ $\mathrm{ord}_2(p-1)=j ~\Leftrightarrow~ p$ が $\mathbb{Q}(\sqrt[2^j]{2})$ で完全分解かつ $\mathrm{ord}_2(p-1)=j.$

次に $\mathrm{ord}_2(p-1)=j$ の部分を書き換えましょう。これは

$p\equiv 1~\mathrm{mod}~2^j$ かつ $p\not\equiv 1~\mathrm{mod}~2^{j+1}$

と同値です。円分体における素イデアルの分解法則より、上の条件は

$p$ は $\mathbb{Q}(\zeta_{2^j})$ で完全分解するが $\mathbb{Q}(\zeta_{2^{j+1}})$ では完全分解しない

と言い換えられます（ $\zeta_n$ は $1$ の原始 $n$ 乗根）。ここで2つの $\mathbb{Q}$ 上Galois拡大体の系列 $K_j.L_j(j\geq 1)$ を

$K_j=\mathbb{Q}(\zeta_{2^j},\sqrt[2^j]{2})\\L_j=\mathbb{Q}(\zeta_{2^{j+1}},\sqrt[2^j]{2})$

と定めます。一般に「合成体 $LK$ で完全分解 $\Leftrightarrow L,K$ で完全分解」であることに注意すれば、結局次が得られたことになります。

命題3. $^\forall n,~p\nmid 2^n+1$ かつ $\mathrm{ord}_2(p-1)=j ~\Leftrightarrow~ p$ は $K_j$ で完全分解するが $L_j$ で完全分解しない。

命題1と組み合わせることで次が得られます。

命題4. ある $n\geq1$ について $2^n+1$ を割り切る素数の密度は

$\displaystyle{1-\sum_{j=1}^\infty\left(\frac{1}{[K_j:\mathbb{Q}]}-\frac{1}{[L_j:\mathbb{Q}]}\right).}$

これで問題は拡大次数 $[K_j:\mathbb{Q}],[L_j:\mathbb{Q}]$ を求めることに帰着されました！

$K_j$ から求めていきましょう。 $j=1$ のとき $2$ 次、 $j=2$ のとき $8$ 次拡大であることは簡単にわかります。 $j\geq3$ の場合、 $[\mathbb{Q}(\zeta_{2^j}):\mathbb{Q}]=\phi(2^j)=2^{j-1}$ なので、 $[\mathbb{Q}(\sqrt[2^j]{2}):\mathbb{Q}(\zeta_{2^j})]$ を求めます。

$C_j=\mathbb{Q}(\zeta_{2^j}),\alpha:=\sqrt2$ と置きます。 $\alpha=\zeta_8+\zeta_8^{-1}\in C_j$ なので上の拡大はKummer拡大 $C_j(\sqrt[2^{j-1}]{\alpha})/C_j$ であり、Kummer理論より拡大次数は $\langle\alpha\rangle\subset C^\times/(C^\times)^{2^{j-1}}$ の位数に等しくなります。ここで $\sqrt[4]{2}\not\in C_j$ *1より $k\lt j-1$ のとき $\alpha^{2^k}\not\in (C^\times)^{2^{j-1}}$ なので、拡大次数は $2^{j-1}$ とわかりました。よって

$[K_j:\mathbb{Q}]=2^{j-1}\cdot2^{j-1}=2^{2j-2}.$

同様に $L_j$ についても $j=1$ のとき $4$ 次拡大であり、 $j\geq2$ の時はKummer拡大 $C_{j+1}(\sqrt[2^{j-1}]{2})/C_{j+1}$ の次数が $2^{j-1}$ なので

$[L_j:\mathbb{Q}]=2^j\cdot2^{j-1}=2^{2j-1}.$

以上をまとめると次のようになります。

$j$	$1$	$2$	$\geq3$
$[K_j:\mathbb{Q}]$	$2$	$8$	$2^{2j-2}$
$[L_j:\mathbb{Q}]$	$4$	$8$	$2^{2j-1}$

それでは密度を求めてみましょう。

$\displaystyle{1-\sum_{j=1}^\infty\left(\frac{1}{[K_j:\mathbb{Q}]}-\frac{1}{[L_j:\mathbb{Q}]}\right)\\=1-\left(\frac{1}{2}-\frac{1}{4}\right)-\left(\frac{1}{8}-\frac{1}{8}\right)-\sum_{j=3}^\infty \left(\frac{1}{2^{2j-2}}-\frac{1}{2^{2j-1}}\right)\\=\frac{3}{4}-\sum_{j=3}^\infty \frac{2}{4^j}\\=\frac{3}{4}-\frac{2\cdot\frac{1}{64}}{1-\frac{1}{4}}\\=\frac{17}{24}.}$

ちゃんと $\dfrac{17}{24}$ が出てきましたね！これでHasseの定理の証明が完了しました。

実は私が最近読んだ論文の中に「Lucas数を割り切る素数の密度は $\dfrac{2}{3}$ である」という定理があって、その中に上の結果と証明が紹介されていたというのが今回の記事の経緯です。Lucas数の方の結果も同じように素イデアル分解の条件に書き直して密度定理を使うことで証明できるようです。

*1: $C_j(\sqrt[4]{2})$ が $\mathbb{Q}$ の非Abel拡大 $K_2=\mathbb{Q}(i,\sqrt[4]{2})$ を含むことからわかります。

2017-07-28

とある整数論の問題と、その鮮やかな解法

次の問題は1984年にハンガリーのとある数学コンテストで出題されたものです。

問題. $a,b$ を正整数とする。どんな素数 $p$ についても $a$ を $p$ で割った余りが $b$ を $p$ で割った余り以下であるとき、 $a=b$ を示せ。

これはもともとPálfyという数学者が予想し、ErdősがSylvester-Shurの定理から従うことを指摘したという経緯があります。しかしこれを数学コンテストに出題したところ、Szegedyという学生が簡潔でself-containdな解法を発見しました。その後、彼ら3人はその解法を共著論文にまとめています。今回はそのエレガントな解法を紹介したいと思います。

以下 $a,b$ を $p$ で割った余りを $a_p,b_p$ と書きます。

問題の解答. $a\neq b$ と仮定する。まず $p$ を十分大きくとることで $a\lt b$ がわかる。さらに $a$ を $b-a$ に変えても仮定は保たれるから、最初から $1\leq a\leq b/2$ としてよい。

$A=1\cdot2\cdots (a-1)a\\B=(b-a+1)\cdots (b-1)b$

と置く。また $\alpha(p^k),\beta(p^k)$ を $A,B$ それぞれの因子（掛けられている $a$ 個の数）のうち $p^k$ で割れるものの個数とする。すると

$\displaystyle{A=\prod_p p^{\sum_{k=1}^\infty\alpha(p^k)},~B=\prod_p p^{\sum_{k=1}^\infty\beta(p^k)}.}$

ここで $A,B$ の因子はどちらも $a$ 個の連続した自然数だから $|\alpha(p^k)-\beta(p^k)|\leq1$ がわかる。さらに $A,B$ の因子を大きい方から順に見ていくと、問題の仮定 $a_p\leq b_p$ より $A$ の因子の方が先に $p$ で割れるから $\alpha(p)\geq \beta(p)$ である。とくに $p\gt a$ ならば $\alpha(p)=\beta(p)=0$ である。ゆえに上の式は

$\displaystyle{\frac{B}{A}=\prod_{p\leq a} p^{\sum_{k=1}^\infty(\beta(p^k)-\alpha(p^k))}}$

となる。 $\beta(p^k)\gt 0$ となる最大の $k$ を $\kappa(p)$ と置くと上の指数部分は

$\displaystyle{\sum_{k=1}^\infty(\beta(p^k)-\alpha(p^k))=(\beta(p)-\alpha(p))+\sum_{k=2}^{\kappa(p)}(\beta(p^k)-\alpha(p^k))-\sum_{k=\kappa(p)+1}^\infty \alpha(p^k)\\ \leq 0+\sum_{k=2}^{\kappa(p)}1=\kappa(p)-1}$

と評価できるから

$\displaystyle{\frac{B}{A}\biggm\vert \prod_{p\leq a}p^{\kappa(p)-1}}.$

変形すると

$\displaystyle{\frac{(b-a+1)\cdots (b-1)b}{\prod_{p\leq a}p^{\kappa(p)}}\biggm\vert\frac{1\cdot2\cdots(a-1)a}{\prod_{p\leq a}p}}$

となる（両辺は整数になっている）。左辺分子の因子のうち約分されるものは高々 $\pi(a)$ 個（ $\pi(n)$ は $n$ 以下の素数の個数）なので

$(左辺)\geq(b-a+1)^{a-\pi(a)}.$

一方右辺分子の因子はちょうど $\pi(a)$ 個約分されるので

$(右辺)\leq a^{a-\pi(a)}.$

よって $b-a+1\leq a$ .これは最初に課した仮定 $b\geq2a$ に矛盾している。よって $a=b$ が示された。 $~~~\square$

まさに見事な証明と言うほかありません。この証明を部屋に飾って眺めていたいくらいです。いつかこんな証明がしてみたいですね。

2017-07-26

Fibonacci素数とF-完全数

Fibonacci 素数

完全数とは「自分自身以外の約数の総和が自分自身になる」ような正整数のことで、 $6,28,496,8128,\cdots$ と続きます。

これの仲間として「自分自身以外の約数の2乗和が自分自身の3倍になる」ような正整数を「F-完全数」と呼ぶことにしましょう。最初の3つのF-完全数は

$10\to 1^2+2^2+5^2=30=10\times 3\\65\to 1^2+5^2+13^2=195=65\times 3\\20737\to 1^2+89^2+233^2=62211=20737\times 3$

となります。

ところでこれらの数の約数を眺めていると不思議なことに気がつきます。そう、 $2,5,13,89,233$ は全てFibonacci数になっているのです。

種明かしをすると、実は次の定理が成り立つのです（Cai-Chen-Zhang,2015）。

定理. $n$ がF-完全数である必要十分条件は、共に素数である2つのFibonacci数 $F_{2m-1}, F_{2m+1}$ を用いて $n=F_{2m-1}F_{2m+1}$ と表されることである。

これを証明するためにLucas数について簡単な性質を確認しておきましょう。Lucas数とはFibonacci数の仲間で、 $L_1=1,L_2=3,L_{n+2}=L_{n+1}+L_n$ で定義されます。一般項を求めると次のようにまとめられます（証明略）。

補題. $\dfrac{L_n+F_n\sqrt5}{2}=\left(\dfrac{1+\sqrt5}{2}\right)^n.$

またFibonacci数との間には以下の関係があります。

補題. $L_n=F_{n+1}+F_{n-1}.$

これは帰納法により簡単に示すことができます。

それでは定理を示しましょう！

定理の証明. $n$ の約数が5個以上あったとし、小さい方から2つめ,3つめのものを $d_1, d_2$ とすると、相加相乗平均の不等式より

$1^2+d_1^2+(n/d_1)^2+d_2^2+(n/d_2)^2\geq1+2n+2n=1+4n$

となり不適。逆に約数が3個以下でも明らかに不適。ゆえに約数はちょうど4個なので、 $n=pq$ または $n=p^3$ （ $p,q$ は素数）と書ける。後者の場合約数の2乗和は $1+p^2+p^4\gt p\cdot p^3$ となるから $p\geq3$ では不適で、 $p=2$ でも成り立たない。よって $n=pq$ となる。

このとき満たすべき方程式は $1+p^2+q^2=3pq\Leftrightarrow (3p-2q)^2-5p^2=-4$ と変形できる。これはPell方程式だから解は

$(3p-2q,p)=(L_{2m+1},F_{2m+1})$

と書くことができる（Pell方程式については過去記事「奇跡の楕円曲線と144」内のリンクを参照）。補題と漸化式より

$q=\dfrac{3F_{2m+1}-L_{2m+1}}{2}=\dfrac{2F_{2m+1}+F_{2m+1}-F_{2m+2}-F_{2m}}{2}\\=\dfrac{2F_{2m+1}-2F_{2m}}{2}=F_{2m-1}$

となるから $n=pq=F_{2m-1}F_{2m+1}$ と書ける。逆にこの形ならばF-完全数であることも上の式変形を逆にたどれば示される。 $~~~\square$

ちなみにF-完全数が無限に存在するかどうかは未解決問題です。というのも、そもそもFibonacci数に素数が無限個存在するかが未解決だからです。なんとか私が生きている間に解決されてほしいものです。

2017-07-25

Fibonacci数の逆数和は無理数である

無理数 Fibonacci

【注意】この記事には横に長い数式が多く含まれます。小さい端末では画面を横向きにすることを推奨します。

皆さん、Fibonacci数は好きですか？好きですよね。私も大好きです。

今回は21世紀に生きるフィボナッチ・フリークなら必ず一度は証明を読んでおきたい"あの"定理を示しましょう。

Fibonacci数の逆数の和

$\displaystyle{\psi = \sum_{n=1}^\infty \dfrac{1}{F_n}=\dfrac{1}{1}+\dfrac{1}{1}+\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{5}+\dfrac{1}{8}+\cdots}$

はReciprocal Fibonacci Constantと呼ばれ、その値はおよそ

$\psi=3.35988566…$

となります。この数は無理数であることがAndré-Jeanninにより1989年に示されました。ここではDuverney(1997)（私が生まれた年！）により簡略化されたその証明を紹介したいと思います。

まず証明に必要な $q$ -指数・対数関数というものを定義します。

定義. $|q|\gt 1,|x|\lt |q|$ に対し

$\displaystyle{E_q(x)=1+\sum_{n=1}^{\infty}\dfrac{x^n}{(q^n-1)(q^{n-1}-1)\cdots(q-1)}}$

と定め、 $q$ -指数関数と呼ぶ。また

$\displaystyle{L_q(x)=\sum_{n=1}^\infty \dfrac{x^n}{q^n-1}}$

と定め、 $q$ -対数関数と呼ぶ。

これらは通常の指数・対数を定義する級数

$\displaystyle{e^x=1+\sum_{n=1}^\infty \dfrac{x^n}{n!},~~-\log(1-x)=\sum_{n=1}^\infty \dfrac{x^n}{n}}$

の自然数 $n$ の部分を $q^n-1$ というパラメータに置き換えたものになっています。このような置き換えは $q$ -類似と呼ばれています。

今回の証明の鍵となるのは次の性質です。

命題. $L_q(x)=x\dfrac{E'_q(-x)}{E_q(-x)}.$

証明. まず

$\displaystyle{E_q(x)-E_q\left(\frac{x}{q}\right)=\sum_{n=1}^\infty \dfrac{(x/q)^n(q^n-1)}{(q^n-1)\cdots(q-1)}=\frac{x}{q}E_q\left(\frac{x}{q}\right)}$

より

$E_q(x)=\left(1+\dfrac{x}{q}\right)E_q\left(\dfrac{x}{q}\right).$

これを繰り返し用いて

$\displaystyle{E_q(x)=\prod_{n=1}^\infty \left(1+\frac{x}{q^n}\right)}$

を得る。対数を取り微分すると

$\displaystyle{\dfrac{E'_q(x)}{E_q(x)}=\sum_{n=1}^\infty \frac{1}{q^n+x}.}\tag{1}$

一方で

$\displaystyle{L_q(x)-L_q\left(\frac{x}{q}\right)=\sum_{n=1}^\infty\left(\frac{x}{q}\right)^n=\frac{x}{q-x}}$

を繰り返し用いると

$\displaystyle{L_q(x)=\sum_{n=1}^\infty\frac{x}{q^n-x}.}\tag{2}$

$(1),(2)$ を比較すれば命題の式を得る。 $~~~\square$

それでは主定理を証明しましょう。

定理. $\displaystyle{\psi=\sum_{n=0}^\infty \frac{1}{F_n}}$ は無理数である。

証明. $\phi=\dfrac{1+\sqrt5}{2}, \bar\phi=\dfrac{1-\sqrt5}{2}$ と置く。 $\psi$ は $q$ -対数関数を使って

$\displaystyle{\psi=\sum_{n=1}^\infty \frac{\sqrt5}{\phi^n-\bar\phi^n}=\sum_{n=1}^\infty \frac{\sqrt5(-\phi)^n}{(-\phi^2)^n-1}=\sqrt5L_{-\phi^2}(-\phi)}$

と書ける。これが有理数 $\dfrac{-A}{B}$ （ $A,B$ は互いに素な整数）だったと仮定する。すると上の命題より

$AE_{-\phi^2}(\phi)-B\phi\sqrt5E'_{-\phi^2}(\phi)=0$

となる。 $E_q(x)$ の定義式に代入すると

$\displaystyle{A+\sum_{n=1}^\infty\frac{(A-Bn\sqrt5)(-\phi)^n}{\prod_{m=1}^n(1-(-\phi^2)^m)}=0.}$

ここで上の式の無限和を $n\leq N$ と $n\geq N+1$ に分割すると

$\displaystyle{A+\sum_{n=1}^N\frac{(A-Bn\sqrt5)(-\phi)^n}{\prod_{m=1}^n(1-(-\phi^2)^m)}=-\sum_{n=N+1}^\infty\frac{(A-Bn\sqrt5)(-\phi)^n}{\prod_{m=1}^n(1-(-\phi^2)^m)}.\tag{3}}$

分母を払えば

$\displaystyle{A\prod_{m=1}^N(1-(-\phi^2)^m)+\sum_{n=1}^N(A-Bn\sqrt5)(-\phi)^n\prod_{m=n+1}^N(1-(-\phi^2)^m)\\=-\sum_{n=N+1}^\infty\frac{(A-Bn\sqrt5)(-\phi)^n}{\prod_{m=N+1}^n(1-(-\phi^2)^m)}.}$

左辺の値を $X_N$ とし、右辺の無限和の中身を $R_n$ と置くと

$\displaystyle{|R_n|\leq\frac{(|A|+|B|\sqrt5)\cdot n\phi^n}{\prod_{m=N+1}^n\phi^{2m-1}}=\frac{(|A|+|B|\sqrt5)\cdot n}{\phi^{n^2-n-N^2}}\lt \frac{C_1n}{\phi^n}}$

と評価できる（ $C_1$ はある正の定数）。ゆえにある正の定数 $C'_1$ があって

$\displaystyle{|X_N|\lt\sum_{n=N+1}^\infty\frac{C_1n}{\phi^n}\lt \frac{C'_1N}{\phi^N}.}$

一方で $X_N$ の共役無理数( $\sqrt5$ を $-\sqrt5$ に置き換えたもの)を $\overline{X_N}$ と置くと、 $|\bar\phi|\lt 1$ なので、 $(1+|\bar\phi|^2)(1+|\bar\phi|^4)\cdots$ が $E_{\phi^2}(1)$ に収束することに注意すれば

$|\overline{X_N}|\lt C_2N^2$

（ $C_2$ はある正の定数）と評価できる。これらを合わせれば

$|X_N\overline{X_N}|\lt \dfrac{C_1'C_2N^3}{\phi^N}\to 0~~(N\to \infty).$

ここで $X_N$ は定義より代数的整数なので上式左辺は整数であり、ある $N_0$ が存在して $N\geq N_0-1\Rightarrow X_N=0$ でなければならない。このとき(3)式の左辺も $0$ になる。 $N=N_0-1,N_0$ として差分をとれば

$\dfrac{(A-BN_0\sqrt5)(-\phi)^{N_0}}{\prod_{m=1}^{N_0}(1-(-\phi^2)^m)}=0\\ \therefore\sqrt5=\dfrac{A}{BN_0}$

となり、 $\sqrt5$ の無理性に反する。ゆえに $\psi$ は無理数である。 $~~~\square$

ちなみに $\psi$ が超越数かどうかは未解決問題です（ぜひチャレンジしてみてください！）。一方でFibonacci数の逆数の2n乗和は超越数であることがわかっています。奇数乗和に関してわかっていることは少なく、ちょうどRiemannゼータ関数の特殊値のような状況になっています。これからどんな結果が出てくるか楽しみですね。

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$ となることを表しています。

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