■分割数の漸近挙動(その2)

 「分割数」とは与えられた整数にどれだけ多くの分割があるのか(4=1+1+1+1,4=3+1)という整数の分割理論のことです.整数の分割では,3=2+1と3=1+2のように足し算の順序が違うものは同じと見なすことにします.

 たとえば,4を分割するには非増加数列で構成した5通りの方法,4=3+1=2+2=2+1+1=1+1+1+1がありますから,p(4)=5.同様にして,5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1よりp(5)=7となります.(分割を図形的に表す方法にヤング図形がある.ヤング図形は非増加な非負整数列を表現する印象的な方法である.)

 オイラーの5角数定理を用いると,分割関数に対する再帰関係式

  Σp(n-j(3j±1)/2)(-1)^j=0

  p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+・・・

が得られます.これより

  p(0)=1,p(1)=1,p(2)=2,p(3)=3,p(4)=5,p(5)=7,p(6)=11,

  p(7)=15,p(8)=22,p(9)=30,p(10)=41,p(11)=56,p(12)=77,・・・

を効率的に計算することができます.

 ここで,p(n)はオイラーの分割関数とも呼ばれますが,定義が簡単そうにみえるにも関わらず,分割数を表す簡単な公式はありません.p(n)の正確な公式は,ラーデマッハーの公式(1937年)

  p(n)=1/π√2ΣAk(n)k^(1/2){d/dxsinh(π(2/3(x-1/24))^(1/2)/(x-1/24)^(1/2))

によって与えられます.ここで,Ak(n)は1の24乗根をもちいて明示的に与えることができます.

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

【1】オイラーの分割関数

 たとえば,正の整数nに対して,

  n=k1+2k2+3k3   (k1≧0,k2≧0,k3≧0)

となる解(k1,k2,k3)の個数をanとします.n=5の場合,

  1+1+1+1+1 → (5,0,0)

  1+1+1+2  → (3,1,0)

  1+1+3   → (2,0,1)

  1+2+2   → (1,2,0)

  2+3    → (0,1,1)

ですから,a5=5となります.

  a0=1,a1=1,a2=2,a3=3,a4=4,a5=5,・・・

 このとき,母関数は

  f(x)=Σanx^n=Σx^(k1+2k2+3k3)=Σx^k1Σx^2k2Σx^3k3

 =1/(1−x)・1/(1−x^2)・1/(1−x^3)

となります.

  (1−x)(1−x^2)(1−x^3)Σanx^n=1

ですから,各項の係数を比較すると漸化式

  an=an-1+an-2−an-4−an-5+an-6

を得ることができます.

  a6=7,a7=8,a8=10,a9=12,a10=14,a11=16,・・・

 この問題を一般化して

  n=k1+2k2+3k3+・・・   (k1≧0,k2≧0,k3≧0,・

・・)の個数p(n)を考えます.n=5の場合,a5に

  1+4,5

が加わり,p(5)=7となります.

 このことから,分割数は以下の公式によって代数的に定義することができることがわかります.

  f(x)=Π(1-x^n)^(-1)={(1-x)(1-x^2)・・・(1-x^n)・・・}^(-1)

    =(1+x+x^2+・・・)(1+x^2+x^4+・・・)(1+x^3+x^6+・・・)(1+x^4+x^8+・・・)・・・

    =Σp(n)x^n=1+p(1)x+p(2)x^2+p(3)x^3+・・・

すなわち,f(x)は分割関数p(n)の母関数で,p(n)はx^nの係数になっています.

 x^k1を第1因子(1+x+x^2+・・・)の一般項,x^2k2を第2因子(1+x^2+x^4+・・・)の一般項,x^3k3を第3因子(1+x^3+x^6+・・・)の一般項,・・・とすると,

  n=k1+2k2+3k3+・・・

となって,x^nの項が整数nの分割に対応することになるのですが,オイラーはこのようにしてp(n)の母関数

  f(x)=Π(1-x^n)^(-1)={(1-x)(1-x^2)・・・(1-x^n)・・・}^(-1)

    =Σp(n)x^n=1+p(1)x+p(2)x^2+p(3)x^3+・・・

を得たというわけです.

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

【2】分割数の近似式

 p(n)を評価する問題は数論において研究されていて,ラマヌジャンが予想した注目すべき漸近近似式

  p(n) 〜 1/4n√(3)exp(π√(2n/3))

は,1918年,ハーディーとラマヌジャンによって,円周法を用いて証明が与えられています.

 実は,円周法に基づく漸近公式の結果を正確に証明するだけでも,長くてこみ入った理論が必要になります.そこで漸近公式の概要だけを簡単に述べますが,σ(k)をkの約数の和とすると,p(n)に対する漸化式

  p(n)=1/nΣσ(k)p(n-k)

において,σ(k)の漸近的振る舞い

  1/n^2Σσ(k)〜π^2/12

を用いると,nが大きい場合の分割数の漸近挙動

  p(n)〜exp(π√(2n/3))/4n√3

を得ることができます.このことから,p(n)は準指数関数と考えることができます(p(n)^(1/n)→1).

  q(n)=1/4n√(3)exp(π√(2n/3))

とおいて最も近い整数を求めてみると,

  q(1)=2,q(2)=3,q(3)=4,q(4)=6,q(5)=9,q(6)=13,

  q(7)=18,q(8)=26,q(9)=35,q(10)=48,q(11)=65,q(12)=87,・・・

となってそれほどよい評価式には思えませんが,漸近近似式はnがどんどん大きくなるとき0に近づくような誤差項を含んだ公式なのです.

 その後,分割関数はラーデマッハーによって修正され,完全な明示公式

  p(n)=1/π√(2)Σk^(1/2)Ak(n)d/dn{sinh(πλn√(2/3))/λn}

  λn=√(n-1/24),Ak(n)には1の24乗根が関係する

が与えられました(1937年).

 分割関数の母関数

  f(x)=Π(1-x^n)^(-1)={(1-x)(1-x^2)・・・(1-x^n)・・・}^(-1)

    =Σp(n)x^n=1+p(1)x+p(2)x^2+p(3)x^3+・・・

は,本質的にモジュラー形式を与えるので,ラーデマッハーはその保型性から明示公式にたどりついたのですが,ハーディーとラマヌジャンはその第一近似式を得たことになります.このことに関して,セルバーグは,ハーディーとラマヌジャンが明示公式までたどりつけなかった原因はハーディーがラマヌジャンを十分に理解できなかったことによると興味深いコメントを述べています.

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

【3】分割数の上界と下界

 参考までに記しますが,

  p(n)≦p(n-1)+p(n-2)

が成り立つことより,分割数の増大速度はファイボナッチ数で上から抑えられることが示されます.したがって,黄金比φ=(√5+1)/2とおくと上界は

  p(n)<φ^n.

 ここでは

  [参]マトウシェク・ネシャトリル「離散数学への招待」シュプリンガー・フェアラーク東京

にしたがって,p(n)の粗いがそれなりによい評価式を求めてみたいと思います.

 無限乗積のままでは扱いにくいので,有限乗積

  fn(x)=Π(1-x^n)^(-1)

を使ってp(n)を評価してみましょう.

[1]上界について

 すべての(0,1)なるxに対して

  p(n)≦fn(x)/x^n=1/x^nΠ(1-x^n)^(-1)

が成り立ちます.この右辺の値がなるべく小さくなるようにxを選びたいのですが,まず対数をとると

  lnp(n)≦-nlnx-Σln(1-x^k)≦-nlnx+x/(1-x)Σ1/k^2

 ここで,

  Σ1/k^2=ζ(2)=π^2/6

ですから

  lnp(n)≦-nlnx+π^2/6x/(1-x)

  u=x/(1-x)  u=0~∞

と変数変換すると

  lnp(n)≦-nln(1+1/u)+π^2/6u

また,不等式1+x≦exp(x)よりln(1-1/u)≦1/uですから,

  lnp(n)<-nln(1+1/u)+π^2/6u≦n/u+π^2/6u

  n/u+π^2/6u

が最小となるのはn/u=π^2/6uすなわちu=√(6n)/πのときで,

  lnp(n)<π√(2/3n)

より,

  p(n)<exp(π√(2/3n))

が成り立つことが証明されます.

 この上界は

  p(n) 〜 1/4n√(3)exp(π√(2n/3))

の指数部分と一致し,かなりよい評価であることがわかります.

[2]下界について

 自然数nを順序つきk分割する総数は

  (n-1)C(k-1)=(n-1,k-1)

また,順序のないk分割のそれぞれから高々k!個の順序つきk分割が作れますから,

  p(n)≧(n-1,k-1)/k!≧(n-1)(n-2)・・・(n-k+1)/(k!)^2

が成り立ちます.

 kを1増やせば分母は(k+1)^2倍され,分子は(n-k)倍されるので,最良の下界を与えるためには(k+1)^2≒n-kより

  k≒[√n]

 このとき,

  (n-1)(n-2)・・・(n-k+1)≧(n-k)^(k-1)=n^(k-1)(1-k/n)^(k-1)

k≒[√n]より,k/n≦1/kですから

  (1-k/n)^(k-1)≧(1-1/k)^(k-1)

したがって,

  n^(k-1)(1-k/n)^(k-1)≧n^(k-1)(1-1/k)^(k-1)≧n^k/en

 スターリングの公式の漸近評価

  k!≦ek(k/e)^k

が成り立つので,

  p(n)≧(n/k^2)^kexp(2k-3)/nk^2≧exp(2k-3)/n^2≧exp(2√n)/exp(5)n^2

 以上により,

  exp(2√n)/exp(5)n^2≦p(n)≦exp(π√(2/3n))

小生は事前に

  exp(π√(2/3n))/n^2≦p(n)≦exp(π√(2/3n))

のような形を予想していたのですが,ほぼ一致する結果です.

 したがって,十分大きなnに対しては

  exp(c1√n)≦p(n)≦exp(c2√n)

となる評価が得られたことになります.ラマヌジャンの結果より粗いのですが,関数の増加に対するオーダーがわかればそれでよしとしましょう.

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

【4】おまけ

 ラマヌジャンはp(n)が満たす合同式について

  p(5n+4)=0  mod5

  p(7n+5)=0  mod7

  p(11n+6)=0  mod11

  p(599)=0  mod5^3

  p(721)=0  mod11^2

を予想し,それらを証明しています.

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