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

 n=243の場合,p(243)=133978259344888に対して

  p(n)〜exp(π√(2n/3))/4n√3〜1.38×10^14

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

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

 分割した数の並べ方も区別するとその総数は,n個の1を横に並べたときに,その間に挿入する「|」の入れ方と一致します.それは明らかに分割数より大きいので

  p(n)<Σ(n−1,k)=2^(nー1)

 また,参考までに記しますが,

  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)

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

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

【2】おまけ

 ラマヌジャンは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

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

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