2018-10-06

対数関数を多項式で近似したときの零点の話【無限乗積展開!?】

対数関数のテイラー展開と多項式近似

　前回の記事で指数関数を多項式で近似した場合に零点がどのように分布するのかについて調べた。

sky-time-math.hatenablog.jp

　指数関数を調べたついでに対数関数の場合も調べてみようと思ったので、やってみた、というのが今回のお話です。*1
　ついでとは言ったが、対数関数 $\log (1+x)$ が指数関数とでは、 $x=-1$ で負の無限大に発散するという決定的に異なる点がある。そのため、「このことが多項式近似の零点分布にどのような影響を及ぼすのだろうか？」という疑問もモチベーションになっている。

　さて、対数関数は、次の形でのテイラー展開ができる。

$\log (1+x) = - \sum_{n=1}^{\infty} \frac{(-1)^n}{n}x^n$ ……(1)

$x=0$ が零点であることは自明なので、両辺を $x$ で割って、 $\log (1+x)$ を多項式で近似した場合の非自明な零点を調べたい。つまり、次の多項式で近似したときの零点を調べる。

$\frac{\log (1+x)}{x} \simeq \sum_{n=0}^{N} \frac{(-1)^n}{n+1} x^n$ ……(2)

　プログラムは前回の指数関数の多項式近似の零点を調べたときと、同様のものを使用した。つまり、多項式(2)の零点をnumpy.rootsで計算した。また、計算の精度を確認するため、計算した零点を持つ多項式を復元し、元の多項式と比較して、係数の最大値と最小値が十分小さいことをチェックしてある。

零点の分布

まずは、多項式(2)の次数 $N$ が小さいところから見ていこう。 $N=4,6,8,10$ の場合は次のようになる。

f:id:FoxQ:20181006100849p:plain

f:id:FoxQ:20181006100857p:plain

f:id:FoxQ:20181006100906p:plain

f:id:FoxQ:20181006100913p:plain

　なんとなく円形にならんでいるように見える。ここからは、一気に次数を増やしてみてる。 $N=20,50,70,100$ の場合は、次のようになる。*2

f:id:FoxQ:20181006100928p:plain

f:id:FoxQ:20181006100935p:plain

f:id:FoxQ:20181006100947p:plain

f:id:FoxQ:20181006100958p:plain

　次数を増やしていくと、思いっきり円形に並んでいることがわかった。また、次数を増やしていくと円(楕円?)の半径が1に近づいていくことも分かった。

零点の絶対値の最大・最小

　指数関数の場合と同様に、零点の絶対値の最大値と最小値も調べてみた。
　まず、次数 $N=1 \sim 15$ までを見てみる。赤線が零点の絶対値の最大値で、青線が最小値だ。

f:id:FoxQ:20181006101347p:plain

次数が増えるにつれて、円(楕円?)の半径が単調に減少にしていることがわかる。次に、 $N=100$ までを見てみる。

f:id:FoxQ:20181006101613p:plain

　次数が十分大きくなると、零点の分布が半径1の円に漸近していっているように見える。おそらく、 $N \rightarrow \infty$ の極限をとると半径1の円になるのだろう。半径が1になっている理由は、 $\log (1+x)$ が $x=-1$ で $- \infty$ に発散することに関係しているためかと思われる。
　これらの零点が $N \rightarrow \infty$ の極限で元の対数関数と何らかの関係を持ち得るか？という素朴な疑問が上がってくる。率直に考えるなら、

$\log(1+x) = x \prod_{x_0 \in \Gamma} (1-\frac{x}{x_0})$ ……(3)

という無限乗積展開のようなものがあるようにも思えてくる。ここで、 $x_0$ は半径1の円上の点で、 $\Gamma$ は半径1の円のなんらかの部分集合である*3。
　しかしながら、対数関数 $\log (1+x)$ の零点は $x=0$ のみであるはずなので、このような無限乗積展開に意味を与えるのはどうにも難しそうである。
　さて、今回はここまでです。みなさんはどう考えますか？

*1:指数関数だけやって、対数関数を仲間外れにするのもどうかと思ったので。

*2:今回は、 $N=110$ で多項式の復元時の誤差が無視できなくなったので、 $N=100$ までを計算することとなった。

*3:高々加算個であるかどうかすらわからないが……

2018-10-05

exp(x)を多項式で近似したときの零点の話

プチ研究数学プログラミング追記あり、一部未完成 twitter オリジナル

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます！

twitterで見かけた指数関数の話

　twitterでtsujimotterさんが、指数関数について以下のようなツイートをしていた。

ふと思った疑問。指数関数のテイラー展開って、有限項で打ち切った多項式の零点と指数関数の零点ってどういう関係になっているだろう。
— tsujimotter (@tsujimotter) September 30, 2018

　これが少し気になったので、Wolfram alphaを使って10次の多項式まで計算してみたところ零点が放物線っぽく並んでいるのを見つけた。もっと高い次数まで計算してみたかったのだが、Wolfram alpha(無料版)は10次までしか相手してくれなかった。

　そこで、勉強中のPythonを使って計算してみることにした、というのが今回するお話です。

指数関数の多項式近似とスケーリング

　指数関数を $N$ 次の多項式で近似すると、次のようになる。

$exp(x) \simeq \sum_{n=0}^{N} \frac{x^n}{n!}$ ……(1)

　PythonのNumpyには、多項式の零点を計算してくれる便利な関数numpy.rootsがあるので今回はそれを使うことにした。ところが、このまま計算すると、 $N$ 次の項が小さくなり過ぎて桁落ちする恐れがあるので、スターリングの公式(スターリングの近似 - Wikipedia)を参考にして、

$x=\frac{Ny}{e}$ ……(2)

と置き換えて、変数のスケールを事前に変えておく。つまり、

$\sum_{n=0}^{N} \frac{(N/e)^n}{n!} y^n$ ……(3)

という多項式の零点を数値計算する。こうすることで、 $N$ 次の項が極端に小さくなることを回避できる。このスケールした多項式の零点が $y_0$ と求まったら、元の多項式(1)の零点は、

$x_0=\frac{N}{e} y_0$ ……(4)

と求まることになる。

　大量の零点を計算することになるので、ちゃんと計算できているかどうかのチェックが必要になる。そこで、求まった零点からそれらの零点を持つ多項式を逆に再計算して、定数項を1になるように規格化し、元の多項式と比較を行った。今回の記事に載せる計算結果は、すべて、元の多項式と零点から復元した多項式の最大の係数が、有効数字で8桁以上で一致することを確認してある。

零点の分布

　まずは、次数 $N$ が小さい方から多項式(1)の零点の分布をみていく。まずは、Wolfram Alphaでやったやつの再計算結果から。

f:id:FoxQ:20181005111524p:plain

f:id:FoxQ:20181005111547p:plain

f:id:FoxQ:20181005111555p:plain

f:id:FoxQ:20181005111600p:plain

このように、無事再現できた。

　次は、次数を20から60まで一気に増やしていく。 $N=60$ に近づくにつれて、放物線というよりは、馬蹄形のようになっていることがわかった。

f:id:FoxQ:20181005111740p:plain

f:id:FoxQ:20181005111747p:plain

f:id:FoxQ:20181005111752p:plain

　さらに、次数を増やす。すると妙なことが起こった。
追記(2018/10/07)：後日、これ以降の次数の数値計算に数値誤差があることが判明しました。きちんと計算できているのは、 $N=60$ くらいまでのようです。

f:id:FoxQ:20181005111908p:plain

　謎の分岐が発生した。さらに、次数を増やしていく。

f:id:FoxQ:20181005111952p:plain

f:id:FoxQ:20181005112006p:plain

f:id:FoxQ:20181005112032p:plain

f:id:FoxQ:20181005112040p:plain

f:id:FoxQ:20181005112051p:plain

　 $N=170$ まで計算したところで、多項式の復元時の誤差が有効数字8桁程度になったり、 $N=180$ でプログラムがエラーを吐いたのでここで計算を打ち切った。

　最終的に、零点の分布が描いたのは、二つの弧とその間にぽつぽつとした点があり、それらの弧に二本のツノを引っ付けたような図形となった。
最初の放物線っぽい形から予想できるような、単純な形にはならなかったのである。

零点の絶対値の範囲

　また、twitterでtaketo1024さんが(1)の多項式の零点の絶対値の範囲の見積もりがあることを教えてくれた。

気になって調べたら、このノートに指数関数の n 次近似式の零点は n/e^2 < |z| < n なる範囲にあることの証明が載ってました😆https://t.co/JLUzrBQe2M
— さのたけと (@taketo1024) September 30, 2018

　ノートによると、この不等式は $N$ が十分大きいところで成立するらしい。

　そこで、今回私が計算した零点の絶対値をとり、その最大値と最小値をプロットしてみた。青色の線が零点の絶対値の最小値で、赤色が最大値である。また、ピンクと水色の線は、上記のツイートのノートに書いてあった最大値と最小値である。

$N=100$ までの図をひとまず見ると、不等式の範囲内にあることがわかる。

f:id:FoxQ:20181005113053p:plain

　ところが、 $N=170$ までを見ると、不等式の下限を下回ってしまった。

f:id:FoxQ:20181005113106p:plain

　これが、numpyの限界なのか、 $N$ の大きさが十分でないためなのかは、はっきりとしない。現状、 $N=60 \sim 70$ 付近で、なぜか零点の絶対値の最小値が頭打ちになっているようにも見える。これはちょうど、零点の分布の図で２個目の『弧』が現れ始めたところである。

追記(2018/10/07):この最小値が頭打ちになっているあたりから数値誤差が強く出ているようです。正しい零点の極限分布について、以下のサイトにまとめを見つけたので、そちらを見てください。

数学の散歩道の「３．指数関数が定める多項式のゼロ点集合の極限形」

http://www.eonet.ne.jp/~kotani/sanpo.html

　このような現象がなぜおきるのか？数学的にありうることなのか？単に数値計算による誤差などの限界から来るものなのか？

　いずれもよくわからない、というのが今の感想だ。みなさんは、どう思いますか？

2018-07-28

【解の構成方法】マスターデーモンの一般化

プチ研究数学オリンピック数学オリジナル

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます！

マスターデーモンの一般化

　今回の記事では、マスターデーモンの一般化について考える。
「自然数rが与えられたとき、２以上の $n$ で
$\frac{r^n+1}{n^2}$ ……(1)
が整数となるものを全て求めよ。」

　結論から言うと、(1)式が整数になるような任意の $n$ を構成するアルゴリズムを求めることはできた。ところが、一般の自然数 $r$ に対して、 $n$ を一般的に表す公式を求めるのは極めて困難である。そのため、(1)式を満たす解が無限に存在するかどうかすらも難しい。この難しさは、素因数分解の難しさに関連するものなので、相当な「武器」を持ってこないと太刀打ちできないだろう。
　また、この記事では、自然数は $1$ 以上の整数であるとする。

今回の話のアウトライン

今回の記事のアウトラインは、次の通りである。

①: $n$ が偶数にならないこと
②: $n$ の最小の素因数が、 $r+1$ の奇数の素因数のいずれかに一致すること
③: $n$ の最小の素因数の指数は、 $r+1$ の対応する素因数の指数以下であること
④と⑤:③の証明
⑥:一般化されたマスターデーモンの解を構成するアルゴリズム

①②③を繰り返し用いることで、(1)式が整数になる $n$ を構成するアルゴリズムが得られる。

① $n$ が偶数にならないこと

　 $r$ が偶数のときは、(1)式の分子が奇数になるので、(1)式の分母は偶数ではない。よって、 $n$ も偶数でない。
　 $r$ が奇数の時、 $n$ が偶数と仮定する。すると、(1)式の分母は $4$ の倍数になるので、(1)式が整数になるなら分子 $r^n+1$ も $4$ の倍数である。従って、

$r^n+1\equiv 0 (\bmod 4)$ ……(2)

　ところが、 $r$ は奇数なので、

$r\equiv \pm 1 (\bmod 4)$ ……(3)

であるので、これを(2)式に代入すると、 $n$ を偶数と仮定したことから、

$(\pm 1)^n+1 \equiv 1+1 \equiv 2$
$\therefore 2 \equiv 0 (\bmod 4)$ ……(4)
となるので、矛盾である。背理法により、 $r$ が奇数のときも、 $n$ は偶数ではない。
　よって、(1)式が整数になるならば、 $n$ は偶数ではない。

② $n$ の最小の素因数が、 $r+1$ の奇数の素因数のいずれかに一致すること

　 $n(\ge 2)$ の最小の素因数を $q$ とし、その指数を $k$ とする。すると、 $n$ は、 $p$ と互いに素な自然数 $N$ を用いて、

$n=q^k N$ ……(5)

と表せる。(1)式の分母が $q$ の倍数になるので、

$r^n+1\equiv 0 (\bmod q)$ ……(6)

である必要がある。フェルマーの小定理より、

$r^n+1\equiv r^{q^k N}+1 \equiv r^N +1 \equiv 0 (\bmod q)$ ……(8)
$r^{2N}\equiv 1(\bmod q)$ ……(9)

また、フェルマーの小定理より、

$r^{q-1}\equiv 1 (\bmod q)$ ……(10)

ここで、法を $q$ としたときの $r$ の位数は、 $\gcd(2N,q-1)$ の約数になるが、 $N$ は $q$ より小さい素因数を持たないので、

$\gcd(2N,q-1)=2$ ……(11)

である。よって、

$r\equiv 1 (\bmod q)$ または $r^2\equiv 1(\bmod q)$
$\iff r\equiv \pm 1(\bmod q)$ ……(12)

である。 $r \equiv 1(\bmod q)$ とすると、(8)式より、

$1^N+1\equiv 2 \equiv 0 (\bmod q)$ ……(13)

となるので矛盾である。従って、

$r\equiv -1 (\bmod q)$
$\therefore r+1 \equiv 0(\bmod q)$ ……(14)

である。
　よって、 $n$ の最小の素因数 $q$ は、 $r+1$ の奇数の素因数のいずれかに一致する。

③ $n$ の最小の素因数の指数は、 $r+1$ の対応する素因数の指数以下であること

　 $r+1$ が次のように素因数分解されたとする。

$r+1=2^{e_0} p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$ ……(15)

ここで、 $t$ は１以上のある自然数で、 $e_j(j=0,1,\cdots,t)$ は０以上の整数で、 $e_j$ の内少なくとも１つは $0$ ではない。

　②より、 $n$ の最小の素因数は、ある $j(=1,2,\cdots,t)$ に対して

$q=p_j$ ……(16)
である。 $n=q^k N$ なので、 $r^n$ は次の形に因数分解できる。

$r^{q^k N}+1=(r+1)f_q(r)f_q(r^q)f_q(r^{q^2}) \cdots f_q(r^{q^{k-1}})f_N(r^{q^k})$ ……(17)

ここで、 $f_m(x)$ は、奇数 $m$ に対して、

$f_m(x)=\frac{r^m+1}{r+1}=1-r+r^2-\cdots+ r^{m-1}$ ……(18)

と定義している。このように因数分解したとき、 $j=0,1,\cdots,k-1$ に対して、

$f_q(r^{q^j})\equiv 0 (\bmod q)$ ……(19)
$f_q(r^{q^j})\not\equiv 0 (\bmod q^2)$ ……(20)
$f_N(r^{q^k})\not\equiv 0 (\bmod q)$ ……(21)

であることが示せる(後で、④,⑤で示す)。従って、 $f_q(r^{q^j})$ は、 $q$ でちょうど１回だけ割り切れるので、(15),(17)式より、

$r^n+1$ は $q=p_j$ で $e_j+k$ 回だけ割り切れる……(22)

(1)式の分母は、 $q$ で $2k$ 回割り切れるので、(1)式が整数であるためには、

$e_j+k \ge 2k$
$\iff k \le e_j$
$\therefore k=1,2,\cdots, e_j$ ……(23)

である必要がある。
　特に、
$n=q^k(k=1,2,\cdots,e_j)$

は一般化されたマスターデーモンの１つの解となっている。
　それでは、(19),(20),(21)式を示そう。

④ $f_q(r^{q^j})\equiv 0 (\bmod q)$ 、 $f_N(r^{q^k})\not\equiv 0 (\bmod q)$ であること

　フェルマーの小定理より、 $j=0,1,\cdots,k-1$ に対して、

$f_q(r^{q^j})\equiv f_q(r) (\bmod q)$ ……(24)
$f_N(r^{q^k})\equiv f_N(r) (\bmod q)$ ……(25)

である。(14),(18)式より、 $N$ と $q$ が互いに素であることに注意して、

$f_q(r)\equiv 1-(-1)+(-1)^2-\cdots (-1)^{q-1}\equiv q \equiv 0 (\bmod q)$ ……(26)
$f_N(r)\equiv 1-(-1)+(-1)^2-\cdots (-1)^{N-1}\equiv N \not\equiv 0 (\bmod q)$ ……(27)

よって、(19),(21)式が成立する。

⑤ $f_q(r^{q^j})\not\equiv 0 (\bmod q^2)$ であること

　まず、 $r+1\equiv 0 (\bmod q)$ より、

$(r+1)^2\equiv r^2+2r+1\equiv 0 (\bmod q^2)$
$r^2 \equiv -2r-1 (\bmod q^2)$ ……(28)

であるので、 $q$ を法とするとき、 $f_q(r^{q^j}$ は $r$ の１次式で表せることに着目する。 $j$ を自然数とするとき、

$r^j \equiv a_j r + b_j$ ……(29)

と置くと、(29)式に $r$ をかけて、(28)式を用いることで、 $a_j,b_j$ の漸化式を得る。

$a_{j+1}=b_j-2a_j$ ……(30)
$b_{j+1}=-a_j$ ……(31)

(31)式を(30)式に用いて、

$a_{j+1}=-2a_j -a_{j-1}$ ……(32)

となるので、 $a_j$ の一般解は、

$a_j=(-1)^j(\alpha j +\beta)$ ……(33)

と表せる。 $a_1=1,a_2=-2$ となることから、 $\alpha,\beta$ を求めた後、

$a_j=(-1)^{j+1} j$ ……(34)
$b_j=(-1)^{j-1}(j-1)$ ……(35)

を得る。これより、

$f_q(r)=1+\sum_{j=1}^{q-1} r^j$
$\equiv 1-(\sum_{j=1}^{q-1} (-1)^j j)r +(\sum_{j=1}^{q-1} (-1)^{j-1} (j-1)) (\bmod q^2)$
$\equiv \frac{1-q}{2} r + \frac{3-q}{2}$ ……(36)

ここで、 $f_q(r)\equiv 0 (\bmod q^2)$ と仮定すると、

$\frac{1-q}{2} r + \frac{3-q}{2} \equiv 0 (\bmod q^2)$
$q(1-q)r - q(q-3) \equiv 0(\bmod q^2)$
$q (r+3) \equiv 0 (\bmod q^2)$
$\therefore r\equiv -3 (\bmod q)$ ……(37)

となるが、 $r\equiv -1 (\bmod q)$ であったので矛盾。よって、

$f_q(r)\not\equiv 0 (\bmod q^2)$ ……(38)

　次にオイラーの定理より*1、

$r^{\varphi(q^2)}\equiv r^{q(q-1)} \equiv1(\bmod q^2)$
$\therefore r^{q^2}\equiv r^q (\bmod q^2)$ ……(39)

であるので、

$j=1,\cdots,k-1$ に対して、

$f_q(r^{q^j})\equiv f_q(r^q) (\bmod q^2)$ ……(40)

が言えるので、 $f_q(r^{q^j})\not\equiv 0 (\bmod q^2)$ を示すには、

$f_q(r^q) \not\equiv 0 (\bmod q^2)$ ……(41)

を示せば十分である。 $f_q(r)\not\equiv 0 (\bmod q^2)$ を示したときと同様にして、

$f_q(r^q)\equiv - \frac{q^2-q}{2} r - \frac{q^2-q-2}{2} (\bmod q^2)$ ……(42)

を得る。 $f_q(r^q) \equiv 0 (\bmod q^2)$ となったと仮定すると、(42)式に $2$ をかけて、

$(-q^2+q)r \equiv q^2 -q -2 (\bmod q^2)$
$qr \equiv -q-2 (\bmod q^2)$
$0\equiv q^2 r \equiv -2q$
$\therefore 2q\equiv 0 (\bmod q^2)$ ……(43)

これを満たす奇素数 $q$ は存在しないので、矛盾。よって、

$f_q(r^q)\not\equiv 0 (\bmod q^2)$ ……(44)

　以上をまとめて、 $j=0,1,\cdots,k-1$ に対して、

$f_q(r^{q^j}) \not\equiv 0 (\bmod q^2)$ ……(45)

が示せた。

⑥:一般化されたマスターデーモンの解を構成するアルゴリズム

　①～③を繰り返し用いることにより、一般化されたマスターデーモンの解を構成するアルゴリズムが得られる。

$r_1=r$ とおき、(15)式のように、
$r_1+1=2^{e_0} p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$ ……(46)
と素因数分解できたとき、ある $p_j$ を１つとり、

$q_1=p_j$ ……(47)

とおく。すると、①～③より、次の $e_j$ 個の自然数は一般化されたマスターデーモンの解になる。

$n=n_1=q_1^{k_1} (k_1=1,2,\cdots,e_j)$ ……(48)

ここで、(48)式のそれぞれの解に対して、

$r_2=r_1^{q_1^{k_1}}$ ……(49)

とおく。

　ここまでを最初のステップとして、一般化されたマスターデーモンの全ての一般解は、以下のようなアルゴリズムにより構成できる。

　 $r_m(m \ge 1)$ が与えられ、

$r_m+1=2^{e_0} p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$ ……(50)

と素因数分解できたする。(ここでは、式の見やすさの便宜上、(46)式と同じ記号 $p_j,e_j$ を用いているだけで、(50)(51)式の素因数とその指数は(46)式とは別に定まるものである。そして、以下に現れる $p_j,e_j$ は全て(50)式のものである。)

　このとき、 $p_j \gt q_{n-1}$ となる素因数を1つ選び、

$q_{m+1}=p_j$ ……(51)

とおく。そして、 $k_{m+1}=1,2,\cdots,e_j$ に対して、

$n=n_{m+1}=n_m q_{m+1}^{k_{m+1}}$ ……(52)

とおく。すると、

$r^{n_m q_m^{k_{m+1}}}\equiv -1 \; (\bmod q_m)$

であれば、①～③より、(52)式で構成される全ての $n$ は一般化されたマスターデーモンの解となる。
　最後に、

$r_{m+1}=(r_m)^{q_{m+1}^{k_{m+1}}}$ ……(53)

とおき、同じアルゴリズムを繰り返すことで、一般化されたマスターデーモンの全ての解が得られる。(このことは、rを(53)式で繰り返し与え直して、①～③を繰り返し適用できることからわかる。)
　このアルゴリズムが有限回で終われば、一般化されたマスターデーモンは有限個の解しか持たない。このアルゴリズムが有限回で終わるためには、 $k_1,k_2,\cdots$ のあらゆ取り方によって構成され得る任意の自然数の系列

$r_1+1,r_2+1,\cdots,r_m+1,\cdots$ ……(54)

に現れる素因数の種類が有限であればいい。(これは素因数分解を前提にした話になっているので、これ以上立ち入って一般論を展開するのはかなり困難だと思う。)

　特に、 $r=2$ のときは、

$2+1=3$
$2^3+1=9=3^2$

となるので、上記のアルゴリズムは１回目で終了し、 $r=2$ のときの解が3しか存在しないことがわかる。他にもいくつかの $r$ で試してみる。

　 $r=3$ の場合は、

$r+1=4=2^2$

なので、解は存在しない。

　 $r=4$ の場合は、

$4+1=5$
$4^5+1=1025=5^2\times 41$

より、 $n=5,205(=5\times41)$ などが解になるが、(54)式の系列に現れる素因数の種類が有限であるかは自明でないので、解の個数も自明ではない。

　 $r=5$ の場合は、

$5+1=6=2 \times 3$
$5^3+1=126=2\times 3^2 \times 7$

より、 $n=3,21(=3\times 7)$ などが解になるが、これもまた、(54)式の系列に現れる素因数の種類が有限であるかは自明でないので、解の個数も自明ではない。

　 $r=20$ の場合も考えてみると、

$20+1=21=3\times 7$

より、 $n=3,7$ などが解になることがわかる。この場合も解の個数は非自明である。

　最後に、以上のアルゴリズムから次の系が導かれることを指摘しておく。

(i) $r+1$ が奇数の素因子を持たないとき、一般化されたマスターデーモンは解を待たない。
(ii) $r+1$ が奇数の素因子を持つとき一般化されたマスターデーモンは解を持ち、そのうち最小の解は、 $r+1$ の最小の奇数の素因子 $p$ に一致する。

*1: $r \equiv -1 (\bmod q)$ より、 $r$ と $q$ は互いに素なので、 $r$ と $q^2$ も互いに素。

2018-07-23

マスターデーモンがついに解けました

数学オリンピック数学追記あり、一部未完成

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

整数論の絶版本・品切れ本をコチラから購入できます！

追記(2018/07/25):計算ミスがあり、証明も冗長だったので、少し修正しました。

マスターデーモン

　マスターデーモンとは、1990年IMO中国大会の第3問で出題された次の問題である。

「2以上の自然数 $n$ で
$\frac{2^n+1}{n^2}$ ……(1)
が整数となるものを全て求めよ。」

　この問題、かなり前に挑戦したが、解けなくてしばらく放置していた。

sky-time-math.hatenablog.jp

　ひさびさに問題を見てみるとなんだか解ける感触がしたので、やってみたらついに解けました。そこで、今回は自分がたどり着いた解法を記事にまとめておきます。フェルマーの小定理と合同式さえしっていれば、普通の高校生でも理解できるように書いたつもりです。最近暑くて頭の回転が鈍っているので、うっかりどこかを間違えているかもしれませんが、そのときは優しく指摘してくれると助かります。

追記(2018/07/28):一般化されたマスターデーモンの解を与えるアルゴリズムも作りました。興味がある方は以下の記事を参考にしてください。

sky-time-math.hatenablog.jp

解答のアウトライン

　 $n$ が偶数なら、与式の分母が偶数、分子が奇数となるので題意の式は整数にならない。以後、 $n$ は奇数とする。
　 $n=3$ が求める解の内の一つであることはすぐにわかる。そして、解がこれしかないことを示したい。
　今回、自分が使ったアプローチは「因数分解」による方法だ。
$n$ がある素因数 $p( \ge 3)$ を $k(\ge 1)$ 個もつとき、すなわち $n=p^k N$ ( $N$ は奇数で、 $N$ と $p$ は互いに素。)とあらわせるとき、 $r^n+1$ は次の形に因数分解できる。( $r$ を自然数)

$r^n+1=(r+1) \cdot \frac{r^p+1}{r+1} \cdot \frac{r^{p^2}+1}{r^p+1} \cdots \frac{r^{p^k}+1}{r^{p^{k-1}}+1}\cdot \frac{r^{p^{k} N}+1 }{r^{p^k}+1}$ ……(2)

といっても、このままでは見づらいので、少し記号を用意する。 $m$ を奇数、 $x$ を自然数とするとき、自然数 $f_m(x)$ を

$f_m(x)=\frac{x^m+1}{x+1}=1-x+x^2-\cdots+x^{m-1}$ ……(3)

とおくと、(2)式は次のように書き直せる。

$r^n+1=(r+1) f_p(r) \cdot f_p(r^p) \cdot f_p(r^{p^2}) \cdots f_p(r^{p^{k-1}}) \cdot f_N(r^{p^k})$ ……(4)

このような因数分解が $n$ の各素因子ごとに存在するので、これをうまく使って問題を解いていく。証明は、次の２つのパートに分かれる。

① $n$ に素因数 $3$ がいくつ含まれるか？
$n=3^kN$ と表される場合を考えて、(4)式で $r=2$ , $p=3$ とすると、 $f_p(r^{p^l})$ ( $l=0,1,2,\cdots,k$ )が $3$ でちょうど一回だけ割れることを示す。そのことから、 $2^n+1$ が素因数 $3$ を $k+1$ 個だけ持つことがわかる。分母には素因子 $3$ が $2k$ 個現れるので、 $n=3^kN$ に現れる指数は $k=0,1$ でなければならないことがわかる。

② $n$ が $3$ より大きい素因数を持たないこと。
$n$ が $3$ の次に大きい素因子 $p$ を持つと仮定として、その指数を $m$ とする。つまり、 $n=3^k p^m M$ ( $k=0,1$ )と表せる場合を考える。このとき、 $8\equiv 1 (\bmod 7)$ のため、 $k=1$ の場合、

$2^n+1\equiv 8^{p^m M}+1 \equiv 2 \not\equiv 0 (\bmod 7)$

よって、 $k=1$ の場合、(1)式の分子は7の倍数ではないので、 $n$ は $7$ を素因数に持たない。
　最後に、 $2^n+1\equiv 8^{p^m M}+1$ が素因数 $p$ を持たないことを背理法により示す。

　①②から、題意を満たす $n$ が $3$ のみであることがわかる。

① $n$ に素因数 $3$ がいくつ含まれるか？

$n=3^kN$ と表される場合を考える。(4)式で $r=2$ , $p=3$ 、 $l=0,1,2,\cdots,k$ として、

$f_p(r^{p^l})=f_3(2^{3^l})=1-2^{3^l}+2^{2\cdot 3^l}$ ……(5)

ここで、 $2 \equiv -1 (\bmod 3)$ より、

$f_p(r^{p^l}) \equiv 1-(-1)^{3^l}+(-1)^{2\cdot 3^l} \equiv 1+1+1 \equiv 0 (\bmod 3)$

また、 $9=3^2$ を法として考えると、
$f_p(r)=1-2+4 =3 \not\equiv 0 (\bmod 9)$ ……(6)

であり、 $l=1,2,\cdots,k$ として、
$f_p(r^{p^l})=1-2^{3^l}+2^{2\cdot 3^l}=1-8^{3^{l-1}}+8^{2\cdot3^{l-1}}$ ……(7)

であるが、 $8\equiv -1 (\bmod 9)$ なので、

$f_p(r^{p^l}) \equiv 1-(-1)^{3^{l-1}}+(-1)^{2\cdot3^{l-1}} =1 +1+1 =3 \not\equiv 0 (\bmod 9)$ ……(8)

従って、 $f_p(r^{p^l})$ は素因数 $3$ をちょうど１つだけ持つ。

続いて、 $f_N(r^{p^k})$ が $3$ で割れないことを確認する。

$f_N(r^{p^k})=f_N(2^{3^k})=1-2^{3^k}+2^{2 \cdot 3^k} - \cdots + 2^{(N-1) \cdot 3^k}$ ……(9)

再び、 $2 \equiv -1 (\bmod 3)$ なので、

$f_N(r^{p^k}) \equiv 1 - (-1)^{3^k} + \cdots +(-1)^{(N-1)\cdot 3^k} (\bmod 3)$
$\equiv 1+1+\cdots+1=N (\bmod 3)$ ……(10)

ところで、 $N$ は $3$ と互いに素なので、 $N$ は $3$ の倍数でない。よって、

$f_N(r^{p^k}) \equiv N \not\equiv 0 (\bmod 3)$ ……(11)

以上より、(4)式で $r=2$ , $p=3$ とすることで、 $2^n+1$ は素因数 $3$ を $k+1$ 個持つことがわかった。したがって、分母に現れる素因数 $3$ の個数が $2k$ 個なので、(1)式が整数となるためには、

$k+1 \ge 2k$
$k =0,1$ ……(12)

でなければならないことがわかった。よって、題意を満たす $n$ は $n=3^k N$ ( $k=0,1$ )と表せる。

② $n$ が $3$ より大きい素因数を持たないこと

　 $n$ が $3$ の次に大きい素因子 $p$ を持つと仮定として、その指数を $m$ とする。つまり、

$n=3^k p^m M$ ( $k=0,1$ )……(13)

と表せる場合を考える。ここで、解答のアウトラインで書いたように、 $k=1$ のとき、 $p$ は $7$ ではない。

$p \neq 7$ ……(14)

$2^n+1$ が $p$ を素因数に持たないことを示したい。背理法で示したいので、 $2^n+1$ が $p$ で割り切れたと仮定する。まず

$R=2^{3^k}$ ……(15)

とおくと、 $k=0,1$ なので、

$R=2,8$ ……(16)

である。法を $p$ としてフェルマーの小定理を使うと、 $R^p\equiv R(\bmod p)$ なので、

$2^n+1=R^{p^m M}+1\equiv R^M+1 (\bmod p)$ ……(17)

となる。仮定より、 $2^n+1\equiv 0(\bmod p)$ なので、

$R^M +1 \equiv 0 (\bmod p)$ ……(18)
$R^{2M}\equiv 1 (\bmod p)$ ……(19)

また、フェルマーの小定理より、

$R^{p-1}\equiv 1 (\bmod p)$ ……(20)

であった。ここで、

$R^{\mu}\equiv 1(\bmod p)$ ……(21)

が成り立つ最小の自然数を $\mu$ とすると、(19),(20)式より、ある自然数 $s,t$ が存在して、

$2M=s \mu$ ……(22)
$p-1=t \mu$ ……(23)

と表せる。(22)式の両辺に $t$ をかけると、

$2Mt=s (p-1)$ ……(24)

ここで、(13)式に戻り、 $M$ の定義に立ち戻ると、 $M$ の素因子はすべて $p (\gt p-1)$ より大きいか、または $M=1$ なので、(24)式からある自然数 $u$ が存在して、

$s=Mu$ ……(25)

となる。これを(22)式に代入して整理すると、

$2=u \mu$ ……(26)

従って、

$\mu=1,2$ ……(27)

である。(16)式より $R=2,8$ であったので、

(i) $R=2$ の場合、(21)式から

$2 \equiv 1 (\bmod p)$ または $2^2 \equiv 1(\bmod p)$

$\Rightarrow 1\equiv 0(\bmod p)$ または $3 \equiv 0 (\bmod p)$ ……(28)

となるが、これを満たす素数 $p (\ge 5)$ は存在しないので矛盾。

(ii) $R=8$ の場合も、(21)式から

$8 \equiv 1(\bmod p)$ または $8^2 \equiv 1 (\bmod p)$

$\Rightarrow 7\equiv 0(\bmod p)$ または $63 =3^2\times7 \equiv 0 (\bmod p)$ ……(29)

となる。これを満たす素数 $p (\ge 5)$ は $7$ のみであるが、 $R=8$ のとき $k=1$ であり、この場合、(14)式に書いたように $p\neq 7$ なので矛盾。

　以上より、背理法の仮定が偽であることが言えたので、

$2^n+1$ は $p$ で割れないことが示された。

　以上より、 $n$ が $3$ より大きな素因数を持つとすると、 $2^n+1$ は $p$ で割れきれず、(1)式の分母 $n^2$ が素因数 $p$ を持つので、(1)式は整数にならない。従って、 $n$ は $3$ より大きい素因数を持たない。

よって、(1)式が整数になるような整数 $n (\ge 2)$ は、 $n=3$ に限ることが言えた。

2018-07-18

【素数p,q】5^p+1がqで割り切れ、5^q+1はpで割り切れる

twitter 数学整数問題bot②

数学関連の絶版本・品切れ本をコチラから購入できます！

整数問題bot②で見かけた良問

　昨日(今日)の深夜に整数問題bot②で、ある問題がふと目についた。次のツイートである。

素数の組(p,q)であって, 5^p+1がqで割り切れ, かつ5^q+1がpで割り切れるようなものを全て求めよ.
(出典はヒ・ミ・ツ(^_-)❤)
— 整数問題bot② (@handmade_math) 2018年7月17日

「出典はヒ・ミ・ツ♡」とか書いてあるのがお茶目で、すごく気になったのだ。
この問題、最初はどこから手を付けるかやや悩んだ。(深夜で頭の回転が鈍っていたのかもしれないが……)

　この問題を解き終わったとき、少し前に勉強した群論の知識がうまく使えて、本で勉強した知識を再確認でき、理解が一歩研ぎ澄まされた感じがした。つまり、群論を少し勉強した人にとって、この問題は良問だと思うので紹介してみたい。

　ここでの解説は、群論の知識が無い高校生でも読めるように書いてみるので、整数問題が好きな高校生でも楽しめると思う。

まずは観察と実験から

　まとまった解答は後で書くことにして、まずは問題を見て最初にやってみたことから紹介していこうと思う。このブログでは単に解答を紹介するだけじゃなくて、問題を解くときのライブ感も伝えてみたいからだ。この問題、初見ではどこから手をつけたらいいかすぐにはわからないだろう。そこで、具体的な小さな数で試してみる。解ける兆しが見えていないときでも、自分の手で一歩一歩問題に取り組むのが大切で、もし解けなくても「今の自分がどこまで行けるのか」を知ることが次の挑戦・成長にきっと繋がるからだ。

$p \le q$ として一般性を失わないので、 $p=2,3,5$ の場合をまずは試してみよう。

問題の式は、

$5^p+1 \equiv 0 (\bmod q)$ ……(1)
$5^q+1 \equiv 0 (\bmod p)$ ……(2)

と書ける。

まず、 $p=2$ のとき、 $5 \equiv 1 (\bmod 2)$ より、

$5^q+1 \equiv 1+1 \equiv 0 (\bmod 2)$
$5^2+1 \equiv 26 = 2 \times 13 \equiv 0 (\bmod q)$

よって、 $(p,q)=(2,2),(2,13)$ が解の一つであることがわかる。

次に、 $p=3$ のとき、 $5 \equiv -1 (\bmod 3)$ より、

$5^q+1 \equiv (-1)^q+1 = 0 (\bmod p)$ *1
$5^3+1 \equiv 126 = 2 \times 3^2 \times 7 \equiv 0 (\bmod q)$

よって、 $(p,q)=(3,3),(3,7)$ も解である。

$p=5$ のときは、 $5 \equiv 0 (\bmod 5)$ より、

$5^q+1 \equiv 1 (\bmod 5)$

となるので題意を満たさない。

　ここまでやってみて、見つかった解に規則性らしきものがなさそうに感じられるので、ひょっとしたら、 $p \ge 5$ の解は存在しないんじゃないかという気がしてくる。
実際、 $p=2,3$ 以外に解が無いことは後になってわかるが、前に進むために(1)、(2)式を少し変形してみる。

$5^p \equiv -1 (\bmod q)$ ……(1')
$5^q \equiv -1 (\bmod p)$ ……(2')

この式をしばらく見つめてみる。すると、右辺が $-1$ だから取扱いにくいのかなと思えてくる。そこで、(1')、(2')式の両辺を二乗して右辺を $1$ にしてみることにした。

$5^{2p} \equiv 1 (\bmod q)$ ……(3)
$5^{2q} \equiv 1 (\bmod p)$ ……(4)

　ここで、上の式がフェルマーの小定理(フェルマーの小定理 - Wikipedia)に似ていることに気づく。フェルマーの小定理を書き出してみると、 $p,q \not\equiv 5$ のとき、

$5^{q-1} \equiv 1 (\bmod q)$ ……(5)
$5^{p-1} \equiv 1 (\bmod p)$ ……(6)

が成り立つ。

　ここで、 $5$ を $1$ から順にべき乗していったときに、はじめて $1$ になるのはいつだろうかと考えてみることにした。*2このようなアイデアに自然に行き着いたのは、群論を勉強していたおかげだと思う。ともかく、

$5^\lambda \equiv 1 (\bmod p)$ ……(7)
$5^\mu \equiv 1 (\bmod q)$ ……(8)

を満たす最小の正の整数 $\lambda,\mu$ を考える。*3　このとき、(3)(4)(5)(6)式の指数は、それぞれ対応する $\lambda,\mu$ の倍数であることがわかる。*4 *5

もし、(7),(8)を満たす $\lambda,\mu$ が具体的に求まれば、 $p-1$ 乗や $q-1$ 乗といった考えにくい式は扱わなくてすむだろう。そんなわけで、この問題を解く方針が定まった。それでは、解答に移ろう。

解答

$p \le q$ として一般性を失わない。題意より、

$5^p+1 \equiv 0 (\bmod q)$ ……(1)
$5^q+1 \equiv 0 (\bmod p)$ ……(2)

であるが、これを変形して、

$5^{2p} \equiv 1 (\bmod q)$ ……(3)
$5^{2q} \equiv 1 (\bmod p)$ ……(4)

を得る。 $p,q \equiv 5$ の場合、(3)(4)式は明らかに成立しないので、以下 $p,q \not\equiv 5$ として考える。すると、フェルマーの小定理より、

$5^{q-1} \equiv 1 (\bmod q)$ ……(5)
$5^{p-1} \equiv 1 (\bmod p)$ ……(6)

が成り立つ。次に、

$5^\lambda \equiv 1 (\bmod p)$ ……(7)
$5^\mu \equiv 1 (\bmod q)$ ……(8)

を満たす最小の正の整数を $\lambda,\mu$ とおくと、(4)(6)(7)式より、 $2q$ と $p-1$ は共に $\lambda$ の倍数である。したがって、ある正の整数 $k,l$ により、

$2q=k \lambda$ ……(9)
$p-1=l \lambda$ ……(10)

この２つの式より、(9)式の両辺を $l$ 倍して、

$2 q l = k l \lambda = k(p-1)$ ……(11)

ここで、 $q$ は素数なので、 $k$ または $p-1$ を割り切る。ところが、仮定より $p-1 \lt p \le q$ なので、 $q$ は $p-1$ を割り切らず、 $k$ が $q$ の倍数であることが言える。よって、ある正の整数 $m$ が存在して、

$k=mq$ ……(12)

が得られる。これを(9)式に代入すると、

$2q=mq \lambda$
$2=m \lambda$ ……(13)

となり、 $m,\lambda$ が正の整数であることから、

$\lambda=1,2$ ……(14)

であることがわかった。

① $\lambda=1$ の場合、

(7)式より、

$5^1\equiv 1 (\bmod p)$ ……(15)

これを満たす素数 $p$ は $p=2$ のみである。

② $\lambda=2$ の場合、

(7)式より、

$5^2=25 \equiv 1 (\bmod p)$ ……(16)
$5^1 \not\equiv 1 (\bmod p)$ ……(17)

ここで、(16)式を満たす素数 $p$ は、 $p=2,3,\cdots$ と調べていくことで、 $p=2,3$ のみであることがわかる。 $p=2$ は(15)式を満たすので、(17)式を満たさない。よって、 $\lambda=2$ の場合、 $p=3$ となる。

　以上より、題意を満たす素数 $p(\le q)$ は、 $p=2,3$ しか存在しないことが分かった。よって、求める解は、 $p \le q$ の条件を取り除くと、

$(p,q)=(2,2),(2,13),(13,2),(3,3),(3,7),(7,3)$

だけであることがわかる。

最後に本の紹介

今回の問題が解けたのは、群論を雪江先生の本で勉強していたことが大きかったと思う。そこで、群論に興味がある人のために、以下の本をおススメしておく。

代数学1　群論入門 (代数学シリーズ)

作者: 雪江明彦
出版社/メーカー: 日本評論社
発売日: 2010/11/17
メディア: 単行本（ソフトカバー）
購入: 1人クリック: 21回
この商品を含むブログを見る

自分で読んだときは、数か所証明が分からないところもあったが、主要な部分は独学でも一通り理解できたので親切な良書だといえるだろう。ページ数も150ページ程度なので、頑張れば１～２週間くらいで読めるだろう。定理に対して例も豊富だが、ところどころ証明の要点があっさり書かれすぎている印象をいくらか受けた。数学科の優等生はこれで問題ないのだろうが、ここでつまづく人や独学の人は志賀先生の「群論への30講」を先に読んでみるのもいいと思う。ちなみに、こちらは少し頑張れば5~7日くらいで読めると思う。

群論への30講 (数学30講シリーズ)

作者: 志賀浩二
出版社/メーカー: 朝倉書店
発売日: 1989/08/01
メディア: 単行本
クリック: 22回
この商品を含むブログ (13件) を見る

*1: $q \ge p=3$ は奇数より。

*2: $p-1$ や $q-1$ が、必ずしもそのような最小の正の整数になっているとは限らないことに注意！！

*3: (7)、(8)式を満たす整数が少なくとも１つ存在することは(3)、(4)式よりわかっているので、このような数が存在することがわかる。

*4:このことの証明は、着目する数が倍数でないと仮定して、その数 $\lambda,\mu$ で割ったときの余りに着目するといい。背理法により、矛盾が導ける。

*5:群論では、ラグランジュの定理(ラグランジュの定理 (群論) - Wikipedia)で説明される。

2018-07-16

(a+b^3)/(ab)が整数となる整数a,bを全て求める

twitter 数学整数問題bot

数学関連の絶版本・品切れ本をコチラから購入できます！

2015年ヨーロッパ数学オリンピック日本代表一次選抜試験より

久々に更新してみる。
twitterをのぞいてみたら、整数問題botの問題が目に入った。試しに解いてみたところ、読後感ならぬ解後感(?)が結構よかったので紹介してみたい。
下の問題である。

[171](a＋b³)/(ab)が整数となるような正の整数の組(a,b)をすべて求めよ(2015年ヨーロッパ女子数学オリンピック日本代表一次選抜試験1、3分問題)
— 整数問題bot (@seisu_bot) 2018年7月16日

3分問題ということで、カップラーメンが出来上がるのを待っている間に解けるらしい。お手軽そうなのでやってみた。時間は測らなかったが、だいたい5分くらいで解けたような気がする。ちょっとした頭のストレッチになるので、挑戦したい人は以下の解答を見る前に自分でやってみてほしい。

解答

$a+b^3$ が $b$ で割り切れることから、 $a$ はある正の整数 $a_1$ を用いて、

$a=a_1 b$

と書ける。*1これを問題の式に代入すると、

$\frac{a+b^3}{ab}$ $=\frac{b(a_1+b^2)}{a_1b^2}$
$=\frac{a_1+b^2}{a_1b}$

となる。ここで気づくのが、元の問題の分子に表れていた $b$ の指数 $3$ が $2$ に下がっていることだ。さらに、問題の式の形はこの指数の部分を除いて、変わっていない。 そんなわけだから、この置き換えを繰り返し行えば、指数をどんどん減らしていけそうだ。

$a_1=a_2 b$ と置き換えると、*2
$\frac{a_1+b^2}{a_1b}=\frac{a_2+b}{a_2b}$

$a_2=a_3 b$ と置き換えると、*3
$\frac{a_2+b}{a_2b}=\frac{a_3+1}{a_3b}$ ……(☆)

となり、分子の $b$ は指数が $0$ になってしまい、ついに消えてしまった。

問題の式が整数となるためには、分子の値は分母の値より、大きくないといけない。よって、

$a_3+1 \ge a_3b$
$(b-1)a_3 \le 1$ ……（♪）

$b \ge 1$ なので、この式が成り立つためには、 $b=1$ または $2$ でなければならない。

① $b=2$ のとき、

不等式（♪）より、 $a_3=1$ なので、
$a_2=a_3 b=2$
$a_1=a_2 b=4$
$a=a_1 b=8$

と $a,b$ の値が $2,8$ と求まる。このとき、

$\frac{a+b^3}{ab}=\frac{8+2^3}{8*2}=1$

となり、確かに整数になる。

② $b=1$ のとき、

問題の式の値を、正の整数 $k$ とおくと、(☆)式より、
$\frac{a_3+1}{a_3}=k$

この式を変形して、

$1=(k-1)a_3$

この式を満たす正の整数の組 $(k,a_3)$ は明らかに、 $(2,1)$ のみである。
よって、

$a=a_1=a_2=a_3=1$

となり、 $(a,b)=(1,1)$ である。このとき、問題の式の値は $2$ となる。

以上をまとめて、求める正の整数の組 $(a,b)$ は、

$(a,b)=(1,1),(8,2)$

の２つだけである■

*1: $a+b^3 \equiv a \equiv 0 (\bmod b)$ より、明らか。

*2: $a_2$ はある正の整数で、 $b$ の倍数になることは、 $a$ が $b$ の倍数になることと同様に示せる。

*3: $a_3$ はある正の整数で、 $b$ の倍数になることは、 $a$ が $b$ の倍数になることと同様に示せる。

2017-09-24

【IMO2017】国際数学オリンピックの問題２【解答・解説】

数学数学オリンピック

数学関連の絶版本・品切れ本をコチラから購入できます！

2017年国際数学オリンピック(IMO2017)の問題２

前回に引き続き、問題２に挑戦してみた。問題は、次の通り。(http://www.imojp.org/challenge/から引用。)

$\mathbb{R}$ を実数全体からなる集合とする。関数 $f: \mathbb{R} \rightarrow \mathbb{R}$ であって、任意の実数 $x,y$ に対して
$f(f(x)f(y))+f(x+y)=f(xy)$
が成り立つものをすべて求めよ。

　今回はこの問題に半日くらい粘ってみたが、想像以上に手ごわく、残念ながら完答できなかった。完答できていないのに、なんでこの記事を書いてるんだとツッコミをもらいそうだが、これにはちょっとした事情がある。

日本語の解答・解説を求めて

　なかなか解答の糸口をつかめず、「吸収モード」*1に入っていた私は、ヒントや解説をネットで探していた。ところが、解説が英語のものしか見当たらないのである。英語が得意じゃない私は、解答を理解するまでに必要以上の時間を使ってしまった。そこで今回は、解答・解説を日本語に書き直してまとめておくことにした。これで、英語が苦手なみんなも、気軽に数学オリンピックの問題を楽しめるようになるはずだ。*2

今回の解答・解説は、Youtubeに挙げられている次の２つの動画を参考にした。

www.youtube.com

これらの動画の解説を、私が理解できた範囲で組み合わせ、まとめ直して翻訳してみた。基本的な解答は１つ目の動画、解答の仕上げの部分は２つ目の動画の方法を使わせていただきました。*3もし私の英語力不足で間違い等があったら、やさしく指摘していただけると助かります。それでは、本題へ。

基本的な観察

　まずは、「 $f(x)$ が定数関数であるような解」が存在するか考えてみよう。すべての $x$ に対し、 $f(x)=a \in \mathbb{R}$ とおくと、問題の関数等式より、
$a=f(f(x)f(y))=f(xy)-f(x+y)=a-a=0$
となる。したがって、 $f(x)=0$ は問題の１つの解である。以降、これ以外の解を探すために、 $f(x)$ は恒等的に $0$ でないとする。
　次に、 $x=y=0$ を代入してみる。*4
$f(f(0)f(0))+f(0+0)=f(0 \cdot 0)$
$\Leftrightarrow f(f(0)^2)=0$ ……①
つまり、 $f(0)^2$ という $f(x)$ の零点が存在する。*5
　ここで、 $f(0)=0$ であると仮定すると、面白いことが起きる。問題の関数等式に $y=0$ を代入すると、
$f(f(x)f(0))=f(0)-f(x)$
$\Leftrightarrow f(0)=f(0)-f(x)$
$\Leftrightarrow f(x)=0$
と $f(x)$ が恒等的に $0$ になってしまうのだ。したがって、恒等的に $0$ でない解を探すため、以後 $f(0) \ne 0$ とする。

零点の値を求めて

次に零点の値を調べる。つまり、 $f(r)=0$ となる実数 $r$ の値を求める。関数等式から、
$f(0)=f(f(r)f(x))=f(rx)-f(r+x)$
を得るが、 $f(0)$ は $0$ になってはいけないので、全ての $x$ について
$rx \ne r+x$
$\Leftrightarrow x(r-1) \ne r$
でなければいけない。そして、条件を満たす $r$ は実は $1$ に限る。理由は簡単で、もし $r \ne 1$ なら $x=r/(r-1)$ が上の式の等号を成立させてしまうからだ。
　結局、
$f(r)=0 \Rightarrow r=1$ ……②
であることがわかった。*6ここで、 $f(0)^2$ が零点であったことを思いだして(①式)、
$f(0)^2=1$
$\Leftrightarrow f(0)= \pm 1$
を得る。
　ところで、関数 $f(x)$ が問題の関数等式を満たすなら、 $-f(x)$ も関数等式を満たす。実際、このことは
$f(f(x)f(y))+f(x+y)=f(xy)$
$\Leftrightarrow -f(f(x)f(y))-f(x+y)=-f(xy)$
$\Leftrightarrow -f( [-f(x)][-f(y)])-f(x+y)=-f(xy)$
と確かめられる。そのため、 $f(0)=1$ となる解 $f(x)$ から、 $f(0)=-1$ となる解を構成することができる。そこで、以降は、
$f(0)=1$ ……③
として話を進める。

$f(x)$ の単射性

　 $f(x)$ が単射であることを証明する。ここがこの問題の山場であり、本質をつかなければいけない部分に思える。ここで、紹介する証明は、AoPS forumとかいうところ(?)でdnkywinさんが発表した方法らしい。
　ともかく、 $f(0)=1$ (③式)としたので、関数等式から
$f(f(x)f(1))=f(x)-f(x+1)$
$\Leftrightarrow f(0)=f(x)-f(x+1)$ (①、②式より、 $f(1)=0$ なので)
$\Leftrightarrow 1=f(x)-f(x+1)$
$\Leftrightarrow f(x+1)=f(x)-1$ ……④

という漸化式のような等式を得る。
　 $f(x)$ が単射であるというのは、 $f(a)=f(b)$ ならば $a=b$ であることを指す。
そこで、 $f(a)=f(b)$ とおく。ここで、④式から、 $f(a)=f(b)$ の両辺に $1$ を繰り返し足す（または引く）ことで、 $a \lt 1$ であるようにできるので、以下記号を適当に置き直して $a \lt 1$ とする。
　ここで、(トリッキーだが)２次方程式
$x^2-bx+a-1=0$
を考える！すると、 $a \lt 1$ より、判別式 $D=b^2-4(a-1)$ が正となるので、この２次方程式は２つの実数解 $r,s$ を持つ。*7また、解と係数の関係から、
$r+s=b$
$rs=a-1$ ……⑤
である。これで下準備は終わった。満を持して、問題の関数等式で $x=r,y=s$ を代入する！
$f(f(r)f(s))=f(rs)-f(r+s)$
$=f(a-1)-f(b)$ (⑤式より)
$=f(a)+1-f(b)$ (④式を使った。)
$=1$ (単射性を証明するときの仮定、 $f(a)=f(b)$ より。)
再び、④式を使って、
$f(f(r)f(s)+1)=0$
ここで、②式より、
$f(r)f(s)+1=1$
$\Leftrightarrow f(r)f(s)=0$
を得る。すなわち、
$f(r),f(s)$ の少なくとも一方が $0$
$\Leftrightarrow r,s$ の少なくとも一方が $1$ (②式より)

が言える。ここで、解と係数の関係の式⑤に立ち返ると、
$b=1+s$
$s+1=a$
等から、 $a=b$ を得る*8。よって、 $f(a)=f(b) \Rightarrow a=b$ が言えたので、 $f(x)$ は単射であることが証明された。

最後の仕上げ

最後の仕上げは、冒頭で挙げた２つ目の動画から紹介させていただきます。*9
　問題の関数等式で、 $y=-x$ とおくと、
$f(f(x)f(-x))=f(-x^2)-f(0)$
$\Leftrightarrow f(f(x)f(-x))=f(-x^2)-1$ 　(③式より)
$\Leftrightarrow f(f(x)f(-x))=f(1-x^2)$ 　(④式より)
ここで、関数 $f$ の単射性より、
$f(x)f(-x)=1-x^2$ ……⑥
を得る。
　同様に、問題の関数等式で $y=1-x$ とおくと、
$f(f(x)f(1-x))=f(x(1-x))-f(1)$
$\Leftrightarrow f(f(x)f(1-x))=f(x(1-x))$ 　(①、②式より、 $f(1)=0$ なので)
再び、関数 $f$ の単射性より、
$f(x)f(1-x)=x(1-x)$
$\Leftrightarrow f(x)(f(-x)-1)=x(1-x)$ (④式より)
$\Leftrightarrow f(x)f(-x)-f(x)=x-x^2$
ここで、⑥式を用いると、
$1-x^2-f(x)=x-x^2$
$\Leftrightarrow f(x)=1-x$
を得る。よって、③式の上の方で書いたように、 $f(x)$ が解なら $-f(x)$ も解である。よって、問題の関数等式を満たす解は、
$f(x)=0,1-x,x-1$
の３つである。