Grahamの第二論文を読む ー①
過去の記事を読むには上のカテゴリーをクリックしてください。前の記事で導入した記号・用語については説明を省略しています。
前回までにGrahamの第一論文を読み終えました。
一連のプロジェクトの目標は
integers.hatenablog.com
で紹介したGrahamの定理を証明することです。
それは分母が平方数であるようなエジプト分数の有限和として表すことができる有理数の特徴付けを与えるものですが、第二論文では平方数に限定せず、一般の乗数の場合にも適用できる形で定理を証明します。
を正の整数とし、
乗数を小さい順に
と並べてできる数列を
と表すことにします。すると、
は
乗数を分母に持つようなエジプト分数を大きいものから順に
と並べてできる数列になります。
このとき、目標は「集合を決定すること」と表現することができます。正の実数からなる数列
に対して、集合
を
と定めます。すると、第一論文の主定理から次の定理が得られます:
証明. 定義上、は両辺ともに入る。よって、正の有理数
(
は互いに素な正の整数)に対して、
を示せばよい。
まず、であることに注意する。Spragueの定理より、
は半完全である。
とすると、
なので、は有界である。
が
のある項を割り切ることは自明(
である)。
従って、Grahamの第一論文の主定理Grahamの第一論文を読む -② - INTEGERSより①が従う。 Q.E.D.
定理1によって、を知るには
を知ればよいことがわかりました。なので、第二論文は正の実数からなる数列
に対して、
をより明示的に与える一般論を展開することから始まります。
この記事では定義一つと補題三つを片付けておくことにしましょう。
証明. なら主張は自明となるため、
と仮定する。このとき、
が成り立つ。最後の条件はが
において滑らかに置換可能であることと同値である。 Q.E.D.
これは、128より大きい任意の整数は相異なる平方数の和として表すことができる。 - INTEGERSにおいて紹介したSierpinskiの補題とBrownの命題における条件の関係と似ています。
証明. 条件は
であり、仮定より
が成り立つので、
を得る。これは
と書き換えられ、が
において滑らかに置換可能であることが示された。 Q.E.D.
証明. 正整数が
を満たすならば、補題2の証明と同様の変形によって
が成り立つ。よって、補題1よりなる
に対して、
は
において滑らかに置換可能であることがわかる。特に、
としてもそうである。 Q.E.D.