インテジャーズ

インテジャーズ

数、特に整数に関する記事。

エジプト分数とグラハムの定理

正の有理数であって、分子が1であるものをエジプト分数、または単位分数といいます。

リンド・パピルスの記録によれば、古代エジプト人はエジプト分数を好み、与えられた正の有理数を

\displaystyle \frac{2}{97}=\frac{1}{56}+\frac{1}{679}+\frac{1}{776}

のようにエジプト分数の和に分解していたようです(エジプト分数分解)。

ただし、

\displaystyle \frac{2}{97}=\frac{1}{97}+\frac{1}{97}

のような分解はいつでもできるため、エジプト分数分解においては各分母は相異なる数であるとします。

なお、

\begin{align} \frac{3}{7} &= \frac{1}{3}+\frac{1}{11}+\frac{1}{231} \\ &= \frac{1}{4}+\frac{1}{7}+\frac{1}{28} \\ &= \frac{1}{6}+\frac{1}{7}+\frac{1}{14}+\frac{1}{21} \end{align}

のようにエジプト分数分解の方法は一般に一通りとは限りません。

エジプト分数分解に関する基本定理は次です:

定理 (Fibonacci-Sylvester) 任意の正の有理数はエジプト分数分解できる。

証明. 正の有理数p/qを考える(p, qは互いに素とする)。q=pa+rと割り算せよ(rが余り)。すると、

\displaystyle \frac{p}{q} = \frac{1}{a+1}+\frac{p-r}{q(a+1)}

が成り立つ。p > p-rであるから、この操作を繰り返すといつかエジプト分数分解に到達することがわかる。 Q.E.D.

ちなみに、この証明法はエジプト分数分解を与えるアルゴリズムを与えています(欲張り計算法)。

今日は6月23日なので、6/23を欲張り計算法でエジプト分数分解してみましょう:

\displaystyle  \frac{6}{23} = \frac{1}{4}+\frac{1}{92}

偶然一回で終わってしまいました笑。皆さんも、いくつか欲張り計算法でエジプト分数分解を与えてみてください。証明中のq(a+1)のパートを見ればわかるように、この手法だとどんどん分母がでかくなってしまうため最善の方法とは言えません。

Grahamの定理

R. Grahamは博士論文でエジプト分数の研究を行いました。例えば、エジプト分数分解における分母を相異なる平方数に限定した縛りプレイを研究しています:

\begin{align} \frac{1}{2} = \ &\frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}+\frac{1}{5^2}+\frac{1}{6^2}+\frac{1}{15^2}+\frac{1}{18^2}+\frac{1}{36^2}+\frac{1}{60^2}+\frac{1}{180^2},\\
\frac{1}{3} = \ &\frac{1}{2^2}+\frac{1}{4^2}+\frac{1}{10^2}+\frac{1}{12^2}+\frac{1}{20^2}+\frac{1}{30^2}+\frac{1}{60^2} \\
= \ &\frac{1}{2^2}+\frac{1}{4^2}+\frac{1}{7^2}+\frac{1}{54^2}+\frac{1}{640^2}+\frac{1}{4302^2}+ \frac{1}{10080^2}+\frac{1}{24192^2}+\\ & \frac{1}{40320^2}+\frac{1}{120960^2}\end{align}

バーゼル問題によって

\displaystyle 1+\frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}+\cdots = \frac{\pi^2}{6}

なので、\pi^2/6より小さい有理数しかこのような表示は持ち得ないことが分かります。バーゼル問題については
integers.hatenablog.com
を参照してください。

Grahamはこの縛りプレイが可能な正の有理数の必要十分条件を与えることに成功しました:

定理 (Graham) 正の有理数が分母が平方数であるような相異なる有限個のエジプト分数の和として表されるための必要十分条件は次の集合に属することである:
\displaystyle \left( 0, \frac{\pi^2}{6}-1 \right) \cup \left[ 1, \frac{\pi^2}{6} \right) .

間に表現できない区間があることが非自明で面白く感じます。

この定理の証明を数回に分けて紹介したいと思います。

連続記事にはなっていないため、カテゴリーの「Grahamの定理」を参照してください。