■長方形の最小分割問題

 前回のコラムでは円の最大分割問題を取り上げたのですが,今回は長方形を最も少ない数の正方形で分割するという問題について考えてみることにします.この問題は私にとって未解決問題となっているもののひとつであって,読者諸賢のお知恵を拝借したいと存じます.

===================================

【1】デーンの定理(1903年)

 「縦がa,横がbの長方形Kを縦横比が有理数であるような有限個の長方形に分割することができるならばa,bの比は有理数であることが必要十分条件である.」

 分割された小長方形は,縦横比が有理数という条件が付いているだけで,それぞれの長さは無理数でもかなわないのですが,分割の際,小長方形の配置は多様にありうるわけですから,この定理はまったく自明な定理とはいえません.

  [参]砂田利一「分割の幾何学」日本評論社

によると,1940年になってからブルックス,スミス,ストーン,テュッテはデーンの定理を電気回路とみなしてキルヒホッフの法則とオームの法則に帰着させて鮮やかに証明したとあり,この問題について詳しく述べてあるので参照してほしいと思います.そこでは,有理数値の重みをもつポアソン方程式Δf=gの解fについて考察していて,グラフ上のラプラシアンに関するスペクトル幾何学の離散近似問題に焼き直してあります.→[補]

 特に,Kを有限個の正方形に分割できればa,bの比は有理数であることが必要十分条件となります.デーンの定理により,縦横比が有理数であるような長方形は正方形分割されるのですが,その方法は1通りではありません.

 縦横比がa/bであるとき,縦をa等分,横をb等分してab個の正方形で分割する方法では正方形領域は最小個数にはならないし,あまりに芸がありません.それに対して,ユークリッドの互除法に基づく連分数の理論は,もっと経済的な分割の方法です.

 ユークリッドの互除法に基づくアルゴリズムは,縦がa,横がbの長方形の分割では左から正方形を最大個数詰め,次に残りの長方形において下から正方形を最大個数詰め,・・・,最後の残った長方形において左から正方形を最大個数詰めると,正方形分割が得られることを示しています.

 a<bとして,このことを数式で表すと,

  b=q0a+r1

  a=q1r1+r2

  r1=q2r2+r3

  r2=q3r3+r4

  ・・・・・・・・

  rl-1=qlrl

上のようにしてrl+1回目に得られるrlはa,bの最大公約数であり,長方形はq0+q1+・・・+ql個の正方形で埋めつくされることになります.

 たとえば,縦が5横が7の長方形において,左から1辺の長さが5の正方形を1つ詰め,下から1辺の長さ2の正方形を2つ詰め,最後に残った長方形において左から対して1辺の長さ2の正方形を2つ詰めると,正方形分割が得られます.これを連分数表示すると

  7/5=[1:2,2]→正方形領域数5

 同様に

  11/7=[1:1,1,3]→正方形領域数6

となりますが,縦横比が無理数の場合はこの連分数展開は無限に続きますから,有限分割することができないことがわかります.

  √2=[1;2,2,2,2,2,・・・]→正方形領域数∞

  √3=[1;1,2,1,2,1,2,・・・]

  √5=[2;4,4,4,・・・]

  √6=[2;2,4,2,4,2,・・・]

  √7=[2;1,1,1,4,1,1,1,4,・・・]

 縦横比が黄金比,すなわち1:(√5+1)/2=1:1.618の長方形を黄金長方形とよびます.黄金長方形から正方形を取り去ると再び小さい黄金長方形が残ります.同様にしてこの手続きは無限に続行できます.したがって,黄金比はユークリッドの互除法によって「1」だけを使って連分数に展開できる無理数であり,すなわち,

  φ=(1+√5)/2=[1;1,1,1,1,1,・・・]

その意味では最もゆっくり収束する無理数であり,最もシンプルなフラクタル生成装置ともいえます.このことから,たとえば,

  55/34=[1:1,1,1,1,1,1,2]→正方形領域数9

は黄金比のよい近似になっていることが理解されます.

 ところが,縦が61,横が69の長方形の正方形分割をユークリッドの互除法に基づいて行うと

  69/61=[1:7,1,1,3]→正方形領域数13

となるのですが,これは最小正方形分割ではなく,1辺の長さが

  25,36,16,9,7,2,5,33,28

の9個の正方形を使って分割できることが知られています.

  25,36,16,9,7,2,5,33,28

は正方形による有限分割をその左辺がより左にあるもの,左辺が同じ位置のものについては上辺がより上にあるものから順に示してあります.

 このように長方形の最小正方形分割に対するユークリッドの互除法のアルゴリズムは破綻するのですが,それでは

  25,36,16,9,7,2,5,33,28

はどのようにして得られたものなのでしょうか? また,最小正方形分割のアルゴリズムは存在するのでしょうか? 次節では分割アルゴリズムの破綻例をもうひとつ掲げておきたいと思います.

===================================

【2】数の平方数分割

 任意の整数nは,n個の平方和

  n=1^2+1^2+・・・+1^2

に書けますから,これをなるべく少ない数の平方和でnを表そうと思うのは自然な成り行きです.そこでまず,簡単な数値実験から始めることにしましょう.1から10までの整数をいくつかの平方数の和の形式で表現するというものです.

 整数の平方

  0,1,4,9,16,25,・・・

は非常にまばらにしか存在しませんが,2つの平方数の和の形で表される整数はより頻繁に現れます.1,2,4,5,8,9,10,・・・

  1=1^2+0^2

  2=1^2+1^2

  4=2^2+0^2

  5=2^2+1^2

  8=2^2+2^2

  9=3^2+0^2

 10=3^2+1^2

 ここで,3,6,7といった整数は,2つの平方の和では書けないことがわかります.しかし,3つの平方和となると幾分間隙を埋めてくれます.

  3=1^2+1^2+1^2

  6=2^2+1^2+1^2

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

  7=2^2+1^2+1^2+1^2

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

===================================

[1]フェルマー・オイラーの定理(2平方和定理)

 特別な素数である2を除外して,素数は4で割ると余りが1になるもの(5,13,17,29,37,41,・・・)と3になるもの(3,7,11,19,23,31,・・・)の2種類に分けられます.

 このうち,4n+1の形の素数は2つの整数の平方の和として表されます.たとえば,5=1^2+2^2,13=2^2+3^2,17=1^2+4^2,29=2^2+5^2

 しかし,4n+3の形の素数は1つもこのようには表せないのです.この定理はフェルマーの定理と呼ばれ,フェルマーは無限降下法でこれを証明しましたが,その証明は不十分で,100年後のオイラーによって完全な証明がなされています.

 それでは,どのような自然数mが2つの平方数の和の形に書くことができるのでしょうか? 2つの平方数の和になる数m=4n+3はありません.mの素因数分解におけるp=4n+3の形のすべての素因数の指数が偶数であるときに限り,2つの平方数の和の形に表すことができるのです.

===================================

[2]ガウス・ルジャンドルの定理(3平方和定理)

 4n+3の形の数は2個の平方数の和で表せませんが,同様にして,

  「8n+7の形の数は3個の平方数の和では表されない.」

 逆にいうと,n≠4^k(8n+7)はnが高々3個の平方数で表されるための必要十分条件です.ガウスの定理ともルジャンドルの定理とも呼ばれますが,ルジャンドルは2次形式ax^2+by^2+cz^2の研究を通して,より一般的な3元2次形式論として,この結果を得ています. 

===================================

[3]ラグランジュの定理(4平方和定理)

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

 驚くべきことに,7のみならず,任意の自然数がたった4つの平方数の和の形に表せるのです.

  7=2^2+1^2+1^2+1^2

  2=1^2+1^2+0^2+0^2

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

  n=□+□+□+□

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

 オイラーはこの定理の直前まで行きながら,最後の段階で成功しませんでした.ラグランジュはオイラーの研究成果からアイデアを得て,1772年,最後の段階を突破したのですが,その証明中で用いられる基本公式が

  x=ap+bq+cr+ds,

  y=aq−bp+cs−dr,

  z=ar−bs−cp+dq,

  w=as+br−cq−dp

とおくと

  (a^2+b^2+c^2+d^2)(p^2+q^2+r^2+s^2)=x^2+y^2+z^2+w^2

が成り立つというもので,1748年にオイラーによって証明されています.

 この基本公式はハミルトンの4元数(1843年)を使ったうまい方法でも証明されますが,それにしても,オイラーはどのようにして発見したのでしょう? なお,四元数は複素数に似ていますが,ただ1つではなく3つの虚数をもつ数体系で,i^2=−1,j^2=−1,k^2=−1,ij=k,jk=i,ki=j,ji=−k,kj=−i,ik=−jなる性質をもち,

(x+yi+zj+wk)(x−yi−zj−wk)=x^2+y^2+z^2+w^2

となります.

 上に掲げた基本公式は,4つの平方数の和となっている数は積の演算で閉じていること,すなわち,n1が4つの平方数の和ならば,n1n2もそうであることを示しています.これにより,ラグランジュの定理を証明するには,すべての素数pが4つの平方数の和であるということの証明に帰着されることになります.また,

  2=1^2+1^2+0^2+0^2

ですから,pは素数と仮定してもよいわけです.

 すべての奇素数pが4つの平方数の和であることの証明も,背理法の1種である無限降下法によって証明できるのですが,これについては

  J.S.Chahal著,織田進訳「数論入門講義」共立出版

にわかりやすい解説がありましたので,それに譲ることにします.

===================================

[4]アルゴリズムの破綻

 [1][2][3]はそれぞれ2元,3元,4元の2次形式の問題なので,n次元空間における格子点の配置の問題として幾何学的に考えることができます.すなわち,ラグランジュの定理は4次元空間内の原点を中心とする半径√nの球面には必ず格子点があることを主張しているわけです.半径√nの2次元の円,3次元の球には格子点が存在するとは限らないのです.

 上の数値実験では,実際に4個必要なのは7だけで,他はすべて3個以下の平方数の和で書けていました.どの場合に2つで済むのか,3つで済むのか?という問題は,ラグランジュの定理に先行するフェルマー・オイラーの定理,オイラー・ルジャンドルの定理で解決されています.

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

  n=n1^2+n2^2+n3^2+n4^2

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

  11=3^2+1^2+1^2

  12=3^2+1^2+1^2+1^2

  13=3^2+2^2

  14=3^2+2^2+1^2

  15=3^2+2^2+1^2+1^2

  16=4^2

  17=4^2+1^2

  18=4^2+1^2+1^2

  19=4^2+1^2+1^2+1^2

  20=4^2+2^2

  21=4^2+2^2+1^2

  22=4^2+2^2+1^2+1^2

  23=4^2+2^2+1^2+1^2+1^2

 素数23では5個の平方和となり,このアルゴリズムは23で破綻してしまいます.もちろん,23は8n+7型の素数ですから,3個の平方和では表すことはできませんが,

  23=3^2+3^2+2^2+1^2

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

 また,

  12=3^2+1^2+1^2+1^2=2^2+2^2+2^2

  18=4^2+1^2+1^2=3^2+3^2

  19=4^2+1^2+1^2+1^2=3^2+3^2+1^2

  23=4^2+2^2+1^2+1^2+1^2=3^2+3^2+2^2+1^2

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

 4=(±1)^2+(±1)^2+(±1)^2+(±1)^2   16通り

 4=(±2)^2+0^2+0^2+0^2            +8通り

のように,4個の平方数による分割

  n=x1^2+x2^2+x3^2+x4^2

の解の個数をR(n)で表せば,1829年,ヤコビは

  R(n)= 8Σ(2d+1)   n≡1(mod 2)

  R(n)=24Σ(2d+1)   n≡0(mod 2)

   Σは(2d+1)|nをわたる

を示しました.

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

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

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

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

===================================

[5]ウェアリングの問題とヒルベルトの定理

 1770年,ウェアリングは4平方和定理を拡張して,

  「任意の整数はたかだか9個の3乗数の和として,あるいは19個の4乗数の和として表される」

ことを証明抜きで主張しました(9三乗数定理,19四乗数定理).これが,有名なウェアリングの問題です.

 g(2)=4はラグランジュにより,g(3)=9はヴィーフェリッヒによって証明されました(1909年).

 4^k(8n+7)の形の数は4個の2乗を必要とするのに対して,9個の3乗を必要とする数は,たった2つの場合だけが知られています.

  23=2・2^3+7・1^3

 239=2・4^3+4・3^3+3・1^3

そして,1939年,ディクソンは23,239以外の整数はすべて8個の3乗数の和で書けることを示しています.

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

  「どの数もg個のk乗数の和で表される」

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

  n=x1^k+・・・+xg^k

 19四乗数定理:

  「すべての正の整数は19個の4乗数の和で表される」

は1986年に証明されています.つまり,ウェアリングの問題(18世紀)も200年以上かかって解決されたことになります.

 なお,g乗数は平方数よりもずっとまばらにしか分布しませんから,以下,37個の5乗数の和,73個の6乗数の和,・・・と続きますが,この最良値を完全に決めることはまだできていません.高次形式の理論はまだ発展途上なのです.

[補]現在,k≧6でのg(k)の値はほぼ決まっている.

  g(6)=73,g(7)=143,g(8)=279,

  g(9)=548,g(10)=1079,・・・

したがって,37五乗数定理だけが残されたことになる.

===================================

【3】おまけ

 ここでは,サイズが1×2のブロックを使ってp×qの領域を覆いつくす問題を考えます.もちろんp,qの少なくとも一方は偶数でなければなりませんが,このとき,p×qの領域を1×2のブロックを使って覆いつくせることは明らかです.

 この問題はサイズが1×mのブロックを使う場合に一般化することができます.p×qはmで割り切れるものとします.m=2のときよりも難しくなるのですが,6×6の領域を1×4のブロックでは覆いつくすことはできません.

 また,1×2のブロックを使って覆う場合,覆い方によっては1本の線でp×qの領域を縦断または横断する線分(分断線)ができてしまいますが,分断線ができないように埋めつくしていきます.p,q≧5とすると,(p,q)=(6,6)の場合を除き,分断線ができないように埋めつくすことができることが証明されています.

 これらの6×6の不可能性は,オイラーの士官36人の問題(6次のグレコ・ラテン方陣)に通ずるのかもしれません.「やってみてできなかった」という体験は組織的に完全に実行すれば立派な証明になるのですが,オイラーの士官36人の問題は実際にそういう証明しかない数学の問題となっています.→コラム「群と魔方陣」

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

 デーンの定理では縦横比が有理数となっていましたが,αが無理数のとき,その小数部分には,0,1,・・・,9が1/10の頻度で現れることが見いだされています.このことの応用として「1ではじまる数が多いのはなぜか」という興味深い応用例を紹介します.

 2のベキ乗2^nを順に並べてそれぞれの最大桁の数を取り出すと

  2,4,8,16,32,64,128,256,512,1024,2048,・・・

  →2,4,8,1,3,69,1,2,5,1,2,・・・

となっているのですが,最大桁がk(1≦k≦9)である確率はn→∞のとき,

  log10((k+1)/k)

に収束することが知られています.

 したがって,最大桁の頻度は1が一番高く

  1→log102=0.3010,

以下,

  2→log103/2=0.1761,

  3→log104/3,

  ・・・・・・・・・,

  9→log1010/9

の順になるというわけです.

===================================

【補】太鼓の形を聴きとれるか? (等スペクトル問題)

 太鼓の形を与えて太鼓の音を求める問題を順問題と呼びますが,これに対して,「太鼓の音を聞いて太鼓の形を推定する」問題は,逆問題の一例としてよく取り上げられるものです.実際,1次元(弦)ならば,その音を聞いて弦の形,すなわち,弦の長さを推定することができます.もっとも材質が違えば音色は異なるわけですが,この場合は音色ではなく,音の周波数(スペクトル)だけを問題とすることにします.それならば2次元(外周が固定された膜)ではどうでしょうか?

  Δf=λf

の固有値

  λ1≦λ2≦λ3≦・・・

が固有振動数を与え,対応する固有関数

  φ1,φ2,φ3,・・・

がそれぞれの固有振動数で振動する膜の変位の様子を与えてくれます.

 ワイルの定理とは,いわば「太鼓の音を聴けばその面積がわかる」というものですが,ここでは,歴史背景に思いを馳せてみましょう.1910年代,ワイルは太鼓の音からその面積を推定することが可能であることを証明しました(ワイルの法則).

 また,1930年代には音から周の長さも決定できることが示されました.

  Nd(λ) 〜 cdVdλ^(d/2)−cd-1/4Ad-1/4λ^((d-1)/2)

ここで,Ad-1はd次元多様体Vdの表面積を表します.

 面積や周長だけから正確に定義できる図形は円だけなので,円形の太鼓ならば音からその大きさを決定できることが解ったわけですが,しかし,面積も周長も等しいが形の異なる太鼓が,同じ音をもっているなどということがあり得るだろうか?という一般的な疑問には答えることができませんでした.

 1960年代になると,カッツは「ドラムの形は聴き分けられるか?」

  M. Kac, Can one hear the shape of a drum?, Amer. Math. Monthly, 73(1966),1-23

という論文を発表しました.カッツの問題とは,漸近挙動

  Nd(λ) 〜 cdVdλ^(d/2)

をもっと詳しく調べれば,太鼓の形についての幾何学的情報がすべて得られないだろうか?という問いかけです.カッツが提出した等スペクトル問題は,数学論文としてはめずらしく魅力的なタイトルがものをいって,大きな注目を集めこの問題を解こうという研究を大きく促すきっかけとなりました.等スペクトル問題は逆問題の特殊な例になっていて,この論文のタイトルが逆問題の有名な標語(スローガン)になったというわけです.

 カッツの論文により「太鼓の音から,その面積,周の長さ,穴の数が聴きとれる」ことが示されたのですが,これらの成果にもかかわらず,境界の形が円であるのか楕円であるのか,四角形か多角形かなのか,面の正確な形が推測できるかというさらに一般的な疑問には答えられませんでした.これが,マッキーンやシンガーなどの人々を触発し,その後の研究が展開する契機となりました.

===================================

 数学者は1次元・2次元・3次元という一般的な空間だけにとらわれません.無限次元さえ考えるのですが,1964年,ミルナーは幾何学的には異なるけれども同じ音を出す16次元のドラムのペアを発見しました.また,別の数学者は異なる次元で等スペクトル多様体(等しい固有値をもち,リーマン多様体として異なる多様体)の例を発見しました.

 多様体がコンパクトのとき,ラプラシアン(楕円型偏微分作用素)

  Δ=d^2/dx1^2+・・・+d^2/dxn^2

のスペクトルは固有値のみからなり,多様体の幾何学的性質(曲率,体積,直径,閉測地線など)と固有値の分布状態は密接に関係することが明らかにされてきたのですが,カッツの提出した「音で太鼓の形が聞き分けられるか?」という有名な問題については,ミルナーなどによる否定的な研究がありました.それらの研究では空間型の特殊性を利用し,後述するヤコビの恒等式やセルバーグの跡公式のような精密な恒等式が重要な役割を果たしています.

 それを受けて,1984年,砂田利一は等スペクトル多様体をほとんど思うがままに作り出す画期的な方法を発見し,これによって低次元の実例を作り出すことが可能になりました.そして,カッツの反例となる等スペクトル多様体が構成できることを示したのです.

  T.Sunada, Riemannian coverings and isospectral manifolds, Ann. Math., 121(1985), 248-277

 砂田の方法では,跡公式と呼ばれるアイディアが使われているのですが,跡公式とは,有限次行列Aにおいて対角和=固有値の和,すなわち

  trA=Σλ

の左辺が解析的,右辺が幾何学的に得られたものであるように,ある作用素の跡を2通りの方法で計算することにより得られる等式であって,作用素とはいわば無限次行列のことと考えておくとよいと思われます.参考図書としては

  砂田利一「基本群とラプラシアン」紀伊国屋書店

を掲げておきます.

 跡公式のひとつの原型が非コンパクト型対称空間(特に上半平面)とそれに作用する離散群に対して,1956年,セルバーグにより定式化されたものです.跡公式がその美しさを最も発揮するのが負の定曲率曲面の場合で,セルバーグが重点的に扱ったのもリーマン面上の調和解析としての跡公式でした.

    R^2               H

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

  Δ=d^2/dx^2+d^2/dy^2   Δ=-1/y^2(d^2/dx^2+d^2/dy^2)

  長方形とその面積        基本領域とその面積

  ポアソンの和公式        セルバーグ跡公式

  リーマンゼータ関数       セルバーグゼータ関数

 すなわち,上半平面Hでユークリッドラプラシアンに対応するものが双曲的ラプラシアンと呼ばれる作用素であり,R^2におけるリーマンゼータ関数に対応するものがセルバーグゼータ関数,ポアソンの和公式に対応するものがセルバーグの跡公式という対応になっていると考えられます.

 長い間,2次元の世界で等スペクトル多様体のペアを探しだすことはできませんでしたが,1991年には大きな進展がありました.ゴードンとその夫ウェッブは,ウォルポートからヒントを得て,面積と周長は等しいけれども形の違う,けれども同じ音をもつ2次元・3次元のペアを探し出すことに成功したのです.

  C.Gordon,D.Webb and S.Wolport, Isospectral plane domains.and surfaces via Riemannian orbits, Invent. Math., 110(1192), 1-22

 また,現在知られている最も単純な2次元図形はチャップマンによる8つの角をもつ図形です.

  S.J.Chapman, Drums that sound the same, Amer. Math. Monthly, 102(1995), 124-138

  [参]浦川肇「ラプラス作用素とネットワーク」,裳華房

には,これらの図形が図入りで詳しく書かれています.とはいえ,新たな問題も浮かび上がっています.たとえば,もっと単純な構造をもつもの,あるいは,滑らかな境界をもつドラムのペアは存在するであろうか? 等々.スペクトル幾何学の研究はやっと始まったばかりで,まだ多くの問題が残されているのです.

===================================