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

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

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

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

　　ｎ＝１^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

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

　　１１＝３^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)はテータ関数です．Ｒ（ｎ）を求めるのにヤコビはテータ関数を用いたのですが，それ以来，モジュラー形式などの解析的理論が数論へ応用されるようになり，ヤコビは２，４，６，８個の平方の和に分解する仕方の数，エルミートは３，５個の平方の和に分解する仕方の数を得ています．→コラム「もうひとつの五角数定理」，「分割数の漸近挙動」

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