反復アルゴリズムにおいて，各ステップごとに最大化を試みるものを欲張り算法（greedy algorithm）と呼びます．欲張り算法はあるときは最も賢明な方法ですが，ときとして破綻します．今回のコラムでは成功と失敗の２つのケースを紹介します．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】アルゴリズムは破綻しない・・・「エジプト式単位分数」

　分子が１である分数を単位分数と呼びます．古代エジプト人は分数を表すのに，互いに異なる単位分数の和として表しました．たとえば，５／７は

　　５／７＝１／７＋１／７＋１／７＋１／７＋１／７

ではなく，互いに異なる単位分数の和ですから，３つの単位分数を用いて

　　５／７＝１／２＋１／５／１／７０

と書くことができます．

　どんな分数でも相異なる単位分数の和として表現できることは，簡単に証明できます．それでは

　(1)分数ｐ／ｑを越えない最大の単位分数を求め，ｐ／ｑから差し引き，それをｐ1／ｑ1とする

　(2)分数ｐ1／ｑ1を越えない最大の単位分数を求め，ｐ1／ｑ1から差し引き，それをｐ2／ｑ2とする

　(3)分数ｐi／ｑiを越えない最大の単位分数を求め，ｐi／ｑiから差し引き，それをｐi+1／ｑi+1とする

という手順を繰り返せば，つねに単位分数表示が得られるでしょうか？

　答えはyesで，このアルゴリズムは破綻しないことが知られています．もちろん，その表示の仕方はただ１通りです．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

　単位分数の和としての表現は少なくとも１つは存在するのですが，しかし，単位分数表示は１通りとは限らず，たとえば，前述の５／７は

　　５／７＝１／２＋１／７＋１／１４

　　５／７＝１／３＋１／４＋１／８＋１／１６８

のように何通りも表し方があります．

　２／（２ｎ−１）という形の分数の相異なる単位分数の和による表現では，欲張り算法により

　　２／（２ｎ−１）＝１／ｎ＋１／ｎ（２ｎ−１）

のように２個の単位分数を用いて表示できます．

　　２／３＝１／２＋１／６

　　２／５＝１／３＋１／１５

　　２／７＝１／４＋１／２８

　　２／１１＝１／６＋１／６６

　　２／２３＝１／１２＋１／２７６

はこの式に従っていますが，

　　２／９＝１／６＋１／１８

　　２／１３＝１／８＋１／５２＋１／１０４

　　２／１５＝１／１０＋１／３０

　　２／１７＝１／１２＋１／５１＋１／６８

　　２／１９＝１／１２＋１／７６＋１／１１４

　　２／２１＝１／１４＋１／４２

は欲張り算法によるものではありません．

［参］ベンソン著，柳井浩訳「数学へのいざない」朝倉書店

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】アルゴリズムは破綻する・・・「ラグランジュの定理」

　任意の整数ｎは，ｎ個平方和

　　ｎ＝１^2＋１^2＋・・・＋１^2

に書けますから，これをなるべく少ない数の平方和でｎを表そうと思うのは自然な発想です．そこでまず，簡単な数値実験から始めることにしましょう．１から１０までの整数をいくつかの平方数の和の形式で表現するというものです．

　整数の平方

　　０，１，４，９，１６，２５，・・・

は非常にまばらにしか存在しませんが，２つの平方数の和の形で表される整数はより頻繁に現れます．１，２，４，５，８，９，１０，・・・

　　１＝１^2＋０^2

　　２＝１^2＋１^2

　　４＝２^2＋０^2

　　５＝２^2＋１^2

　　８＝２^2＋２^2

　　９＝３^2＋０^2

　１０＝３^2＋１^2

　ここで，３，６，７といった整数は，２つの平方の和では書けないことがわかります．しかし，３つの平方和となると幾分間隙を埋めてくれます．

　　３＝１^2＋１^2＋１^2

　　６＝２^2＋１^2＋１^2

　それでも，なおすべての正の整数を得ることはできません．最後まで残った７に対しては３つの平方数の和で書けず，４つの平方数が必要となります．

　　７＝２^2＋１^2＋１^2＋１^2

　このような数値実験からいくつかのことが予想され，肯定的に証明されています．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

［１］フェルマー・オイラーの定理（２平方和定理）

　特別な素数である２を除外して，素数は４で割ると余りが１になるもの（５，１３，１７，２９，３７，４１，・・・）と３になるもの（３，７，１１，１９，２３，３１，・・・）の２種類に分けられます．

　このうち，４ｎ＋１の形の素数は２つの整数の平方の和として表されます．たとえば，５＝１^2＋２^2，１３＝２^2＋３^2，１７＝１^2＋４^2，２９＝２^2＋５^2

　しかし，４ｎ＋３の形の素数は１つもこのようには表せないのです．この定理はフェルマーの定理と呼ばれ，フェルマーは無限降下法でこれを証明しましたが，その証明は不十分で，１００年後のオイラーによって完全な証明がなされています．

　それでは，どのような自然数ｍが２つの平方数の和の形に書くことができるのでしょうか？　２つの平方数の和になる数ｍ＝４ｎ＋３はありません．ｍの素因数分解におけるｐ＝４ｎ＋３の形のすべての素因数の指数が偶数であるときに限り，２つの平方数の和の形に表すことができるのです．

（補）自然数ｎが２つの平方数の和であるための必要十分条件は

　　「ｎを素因数分解したとき，４ｋ＋３の形の素数が偶数乗で現れる」ことである．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

［２］ガウス・ルジャンドルの定理（３平方和定理）

　４ｎ＋３の形の数は２個の平方数の和で表せませんが，同様にして，

　　「８ｎ＋７の形の数は３個の平方数の和では表されない．」

　逆にいうと，ｎ≠４^k（８ｎ＋７）はｎが高々３個の平方数で表されるための必要十分条件です．ガウスの定理ともルジャンドルの定理とも呼ばれますが，ルジャンドルは２次形式ａｘ^2＋ｂｙ^2＋ｃｚ^2の研究を通して，より一般的な３元２次形式論として，この結果を得ています．　

（補）自然数ｎが３つの平方数の和であるための必要十分条件は

　　「ｎが４^n（８ｋ＋７）の形でない」ことである．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

［３］ラグランジュの定理（４平方和定理）

　前述の数値実験から「すべての正の整数は，ｇ個の平方数の和として表すことができるだろうか？　さらに，ｇの最小値はいくつであろうか？」というより高度な問題が派生しますが，「すべての正の整数は高々４個の整数の平方和で表される」というのが，ラグランジュの定理です．

　驚くべきことに，７のみならず，任意の自然数がたった４つの平方数の和の形に表せるのです．

　　７＝２^2＋１^2＋１^2＋１^2

　　２＝１^2＋１^2＋０^2＋０^2

このことを，シンボリックに書くと

　　ｎ＝□＋□＋□＋□

となります．□は平方数の意味です．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

［４］アルゴリズムの破綻

　［１］［２］［３］はそれぞれ２元，３元，４元の２次形式の問題なので，ｎ次元空間における格子点の配置の問題として幾何学的に考えることができます．すなわち，ラグランジュの定理は４次元空間内の原点を中心とする半径√ｎの球面には必ず格子点があることを主張しているわけです．半径√ｎの２次元の円，３次元の球には格子点が存在するとは限らないのです．

　上の数値実験では，実際に４個必要なのは７だけで，他はすべて３個以下の平方数の和で書けていました．どの場合に２つで済むのか，３つで済むのか？という問題は，ラグランジュの定理に先行するフェルマー・オイラーの定理，ガウス・ルジャンドルの定理で解決されています．

　また，ｎを越えない最大の平方数は，ガウス記号を用いて［√ｎ］^2と表せるのですが，ｎを越えない最大の平方数をとり，その残りに対して同様に最大の平方数をとる，・・・，そして残りが平方数になるとおしまいというアルゴリズムによって，４個の平方数の和

　　ｎ＝ｎ1^2＋ｎ2^2＋ｎ3^2＋ｎ4^2

に分解できるように思われます．はたして，これは正しいのでしょうか？　数値実験を続けてみることにします．

　　１１＝３^2＋１^2＋１^2

　　１２＝３^2＋１^2＋１^2＋１^2

　　１３＝３^2＋２^2

　　１４＝３^2＋２^2＋１^2

　　１５＝３^2＋２^2＋１^2＋１^2

　　１６＝４^2

　　１７＝４^2＋１^2

　　１８＝４^2＋１^2＋１^2

　　１９＝４^2＋１^2＋１^2＋１^2

　　２０＝４^2＋２^2

　　２１＝４^2＋２^2＋１^2

　　２２＝４^2＋２^2＋１^2＋１^2

　　２３＝４^2＋２^2＋１^2＋１^2＋１^2

　素数２３では５個の平方和となり，このアルゴリズムは２３で破綻してしまいます．もちろん，２３は８ｎ＋７型の素数ですから，３個の平方和では表すことはできませんが，

　　２３＝３^2＋３^2＋２^2＋１^2

のように４個の平方和の形に表すことができます．

　また，

　　１２＝３^2＋１^2＋１^2＋１^2＝２^2＋２^2＋２^2

　　１８＝４^2＋１^2＋１^2＝３^2＋３^2

　　１９＝４^2＋１^2＋１^2＋１^2＝３^2＋３^2＋１^2

　　２３＝４^2＋２^2＋１^2＋１^2＋１^2＝３^2＋３^2＋２^2＋１^2

のように，より少ない数の平方和として幾通りかに表すことのできる数もあります．

　４＝（±１）^2＋（±１）^2＋（±１）^2＋（±１）^2　　　１６通り

　４＝（±２）^2＋０^2＋０^2＋０^2　　　　　　　　　　　　＋８通り

のように，４個の平方数による分割

　　ｎ＝ｘ1^2＋ｘ2^2＋ｘ3^2＋ｘ4^2

の解の個数をＲ（ｎ）で表せば，１８２９年，ヤコビは

　　Ｒ（ｎ）＝　８Σ（２ｄ＋１）　　　ｎ≡１（mod 2）

　　Ｒ（ｎ）＝２４Σ（２ｄ＋１）　　　ｎ≡０（mod 2）

　　　Σは（２ｄ＋１）｜ｎをわたる

を示しました．

　この出発点となった考え方は，

　　{Σq^(n^2)}^4=ΣR(n)q^n

　　 =1+8nq^n/(1-q^n)

の２つの表現のq^nの係数を比較することであって，Σq^(n^2)はテータ関数です．Ｒ（ｎ）を求めるのにヤコビはテータ関数を用いたのですが，それ以来，モジュラー形式などの解析的理論が数論へ応用されるようになり，ヤコビは２，４，６，８個の平方の和に分解する仕方の数，エルミートは３，５個の平方の和に分解する仕方の数を得ています．→コラム「もうひとつの五角数定理」，「分割数の漸近挙動」

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

［５］ウェアリングの問題とヒルベルトの定理

　１７７０年，ウェアリングは４平方和定理を拡張して，

　　「任意の整数はたかだか９個の３乗数の和として，あるいは１９個の４乗数の和として表される」

ことを証明抜きで主張しました（９三乗数定理，１９四乗数定理）．これが，有名なウェアリングの問題です．

　ｇ（２）＝４はラグランジュにより，ｇ（３）＝９はヴィーフェリッヒによって証明されました（１９０９年）．

　４^k（８ｎ＋７）の形の数は４個の２乗を必要とするのに対して，９個の３乗を必要とする数は，たった２つの場合だけが知られています．

　　２３＝２・２^3＋７・１^3

　２３９＝２・４^3＋４・３^3＋３・１^3

そして，１９３９年，ディクソンは２３，２３９以外の整数はすべて８個の３乗数の和で書けることを示しています．（８個の立方数の和として表せない自然数は，１５，２２，５０，１１４，１６９，１７５，１８６，２１２，２３１，２３８，３０３，３６４，４２０，４２８，４５４の１５個だけである．）

　ウェアリングの問題は，２次形式ではなく高次形式を扱っていて，多くの数学的思考を刺激しました．そして，１９０９年，ヒルベルトによって

　　「どの数もｇ個のｋ乗数の和で表される」

ことが肯定的に証明されています．

　　ｎ＝ｘ1^k＋・・・＋ｘg^k

　ヒルベルトはｇ（ｋ）の値がｋのみによって表されることを証明したのですが，それはｇ（ｋ）の存在のみを証明したのであって具体的な値を決める方法を示したものではありませんでした．

　１８５９年，リューヴィルはｇ（４）≦５３を示しました．ｇ（４）＝１９ですからこの結果は実際とはかなり隔たりがあるのですが，ｇ（４）の限界を与える方法を初めて示したことになります．そのあたりからいろいろな研究がなされることになりました．そして，１９四乗数定理：

　　「すべての正の整数は１９個の４乗数の和で表される」

は１９８６年に証明されています．つまり，ウェアリングの問題（１８世紀）も２００年以上かかって解決されたことになります．

　なお，ｇ乗数は平方数よりもずっとまばらにしか分布しませんから，以下，３７個の５乗数の和，７３個の６乗数の和，・・・と続きます．実は，ガウス記号を用いて

　　ｇ（ｋ）＝２^k＋［（３／２）^k］−２

の式が正しいだろうと予想されています．１≦ｋ≦１０では

　　ｋ　　１　　２　　３　　４　　５　　６　　７　　８　　９　　10

　　下界　１　　４　　９　　19　　37　　73 143 279 548 1079

となり，ここに示した値はすべてこの式を満たし，かなりの範囲のところまで正しいことが確認されます．

　　ｇ（ｋ）≧２^k＋［（３／２）^k］−２

の不等式を証明したのはオイラーの息子，ヨハン・アルブレヒト・オイラーです（１７７２年）．この不等式の証明は

　　［参］水上勉「チャレンジ！整数の問題１９９」日本評論社

のＱ１９１（p272）に掲載されています．簡単でいてしかも面白い証明ですの是非お読みください．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝