■母関数と整数の分割

 母関数は18世紀にド・モアブル,スターリング,オイラーたちによって考案された偉大なる着想であって,一般的な数学の道具のひとつになっています.たとえば,確率論においても母関数は重要な役割を果たし,そこでは積率母関数や特性関数として知られています.積率母関数・特性関数からはモーメントや複数の確率分布を合成した難しい分布型を得ることができます.
 
 まず,母関数(生成関数)についておさえておきましょう.与えられた数列{an}の性質を知ろうとしたとき,数列{an}を直接調べるのではなく,たとえば,xを変数とする級数関数
  φ(x)=a0+a1x+a2x^2+・・・+anx^n+・・・
をつくり,この関数を観察します.
 
 数列の性質は何らかの形で関数の振る舞いに反映していると考えられます.こうして数列{an}の数論的性質(離散的)を,関数φ(x)の解析的性質(連続的)によって解明していこうとする発想が母関数のアイディアです.
 
 一方,ベキ級数の大切さは,三角関数,指数関数,対数関数など多くのよく知られた関数がベキ級数に展開されることにあります.たとえば,テイラー展開
  exp(x)=1+1/1!x+1/2!x^2+・・・
  log(1+x)=x−1/2x^2+1/3x^3−1/4x^4+・・・
  sinx=x−1/3!x^3+1/5!x^5−・・・
  sinhx=x+1/3!x^3+1/5!x^5+・・・
  cosx=1−1/2!x^2+1/4!x^4−・・・
  coshx=1+1/2!x^2+1/4!x^4+・・・
  arctanx=x−1/3x^3+1/5x^5−1/7x^7+・・・
などがその例です.
 
===================================
 
【1】通常型母関数
 
 数列は補助変数xを用いてベキ級数としてうまく表すことができます.数列{an},すなわち,a0,a1,a2,・・・に対して,
  a0+a1x+a2x^2+・・・=Σanx^n=f(x)
で表される関数f(x)をその通常型母関数といいます.
 
 たとえば,
  exp(x)=1+1/1!x+1/2!x^2+1/3!x^3+・・・
より,exp(x)は数列{1/0!,1/1!,1/2!,・・・}の通常型母関数ですし,
  1/(1−x)=1+x+x^2+x^3+・・・
ですから,1/(1−x)は{1,1,1,・・・}の通常型母関数になっていることがわかります.
 
 また,二項展開より,
  (1+x)^n=ΣnCkx^k
ですから,(1+x)^nは有限数列{nC0,nC1,nC2,・・・,nCn}の通常型母関数で,
  (1+x)^n=(1+x)・・・(1+x)
はn個の異なる対象から順序を気にしないでk個選ぶことができる仕方の数を示す母関数となっています.
 
通常型母関数の例−−−フィボナッチ数列
 隣り合う2項の和が次の項となる数列
  1,1,2,3,5,8,13,・・・
はフィボナッチ数列の名で有名ですが,フィボナッチ数列{Fn}の通常型母関数f(x)は
    f(x)=F0 +F1 x+F2 x^2+F3 x^3+・・・
   xf(x)=   F0 x+F1 x^2+F2 x^3+・・・
  x^2f(x)=       F0 x^2+F1 x^3+・・・
また,Fn =Fn-1 +Fn-2 より
  f(x)=x/(1−x−x^2)=ΣFnx^n
 =1+x+2x^2+3x^3+5x^4+8x^5+13x^6+・・・
と簡単な式になります.
 
 ここで,分母(1−x−x^2)は黄金比と関係しているわけですが,実際,フィボナッチ数列の隣り合う2項の比は黄金比に収束することはよく知られています.
  Fn/Fn-1→φ  (n→∞)
 
 母関数は強力な発見手段であり,整数や数列の性質を調べるのにベキ級数の問題に翻訳することによって答えを見つけることができるよい例となっています.
 
===================================
 
[補]黄金比
 
 黄金比φは,2次方程式x^2−x−1=0の根であり,φ=(√5+1)/2=1.618です.
 
 黄金比φには多くの性質があり,
  1,φ,φ^2,φ^3,φ^4,φ^5,・・・
という等比数列を考えると,1+φ=φ^2ですから
  φ^n=φ^(n-1)+φ^(n-2)
したがって,
  φ=φ
  φ^2=φ+1
  φ^3=φ^2+φ=φ+1+φ=2φ+1
  φ^4=φ^3+φ^2=2φ+1+φ+1=3φ+2
  φ^5=φ^4+φ^3=3φ+2+2φ+1=5φ+3
となり,係数は再びフィボナッチ数列{Fn}となります.
 
 また,ガウス記号[x](xを超えない最大の整数)を用いると,数列{[φ^(n-1)]}の各次数に対応して得られる整数列は
  1,1,2,3,5,8,13,・・・
すなわち,フィボナッチ数列{Fn}となります.
 
 初項1,第2項3のフィボナッチ数列
  1,3,4,7,11,18,・・・
はリュカ数列と呼ばれています.リュカ数列はフィボナッチ数列と同じ漸化式をもち,連続する2つの項の比は黄金比に近づきます.
 
 リュカはフィボナッチ数列,リュカ数列を用いてメルセンヌ数(2^n−1)が素数であるかどうかを判定し,(2^127−1)が素数であることを示しています(1876年).リュカの素数判定法はメルセンヌ数が素数であるか否か判定する非常に能率的なアルゴリズムとなっていて,リュカテストの効率のよさのおかげで最近の素数の世界記録はすべてメルセンヌ素数が独占しています.
 
 さらに,1つの項の和がその前の3つの項の和になっている
  Fn =Fn-1 +Fn-2 +Fn-3
で定義される数列
  1,1,1,3,5,9,17,・・・
は,フィボナッチ数列の拡張とみなせるので,フィボナッチ(Fibonacci)をもじってトリボナッチ(Tribonacci)数列と呼ばれます.
 
===================================
 
【2】指数型母関数
 
 一方,
  a0/0!+a1/1!x+a2/2!x^2+・・・
を数列{an}に対する指数型母関数と呼びます.exp(x)は数列{1,1,1,・・・}の指数型母関数です.
 
 二項展開より,
  (1+x)^n=ΣnCkx^k
ですから,(1+x)^nは有限数列{nC0,nC1,nC2,・・・,nCn}の通常型母関数ですが,さらに,nCk=nPk/k!より,(1+x)^n=ΣnPk/k!x^k,すなわち,(1+x)^nは数列{nP0,nP1,nP2,・・・,nPn}の指数型母関数でもあります.
 
 また,フィボナッチ数列の指数型母関数は,
  f(x)=1/√5[exp(φx)−exp(−x/φ)]
となります.
 
指数型母関数の例−−−ベルヌーイ数列
 有名なベルヌーイ数Bnはベキ和Σk^sやゼータ関数の計算などのほかにも,数多くの魅惑的な整数論的特性をもっていて,正則素数の判定にも顔を出す興味深い数ですが,ベルヌーイ数列{Bn}の指数型母関数は
  x/(exp(x)−1)
で与えられます.すなわち,ベルヌーイ数は
  x/(exp(x)−1)
 =1+B1/1!x+B2/2!x^2+B3/3!x^3+・・・
 =ΣBnx^n/n!
で定義される有理数です.
 
===================================
 
【3】ディリクレ母関数
 
 母関数φ(x)=Σa(n)k(n,x)において,関数k(n,x)をカーネル(核関数)と呼びます.通常型母関数はカーネルとしてk(n,x)=x^nを,指数型母関数ではk(n,x)=x^n/n!を利用しているというわけですが,これらだけが母関数ではありません.
 
 k(n,x)=1/n^xを利用した場合,その母関数をディリクレ母関数と呼びます.{1,1,1,・・・}のディリクレ母関数はゼータ関数ζ(x)=Σ1/n^xです.他ほかにも核関数として二項係数(x,n)などを利用することができますが,k(n,x)=(x,n)の場合がニュートン母関数です.
 
===================================
 
【4】分割数の母関数
 
 「分割数」とは与えられた整数にどれだけ多くの分割があるのか(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となります.(分割を図形的に表す方法にヤング図形がある.ヤング図形は非増加な非負整数列を表現する印象的な方法である.)
 
  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)はオイラーの分割関数とも呼ばれますが,定義が簡単そうにみえるにも関わらず,易しい式で表すことはできません.
 
 ところで,分割数は,以下の公式によって代数的に定義することができます.
  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+・・・
すなわち,f(x)は分割関数p(n)の母関数で,p(n)はx^nの係数になっています.
 
 オイラーは,4平方和定理
  「すべての正の整数は4個の整数の平方和で表される」
を証明するために,級数
  g(x)=1+Σx^(n^2)=1+x+x^4+x^9+x^16+・・・
を考察しています.すると,τ(n)を4つの平方数の和に表す仕方の数として,その母関数は
  g(x)^4=Στ(n)x^n
となります.(しかし,当時これを確認するのは困難で,19世紀に入ってからヤコビが楕円関数を用いて解決しました.)
 
 オイラーのアイディアは,nの分割
  n=n1+n2+・・・+nk
がnをk個の平方数の和への分割(nが平方和として何通りに書けるか):
  n=□1+□2+・・・+□k
として表した場合の解と1対1に対応することより,
  f(x)=(1+x+x^2+・・・)(1+x^2+x^4+・・・)(1+x^3+x^6+・・・)(1+x^4+x^8+・・・)・・・
    =Π(1-x^n)^(-1)
 
 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+・・・
を得ています.
 
===================================
 
[補]分割数の漸近挙動
 
 σ(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
を得ることができます(ハーディーとラマヌジャン,1918年).
 
 なお,分割を数え上げるとき,並べる順番は問題にしませんが,もし,順番を考慮すると答えは非常に簡単になります.自然数nをk分割する総数は
  n=i1+i2+・・・+ik
において,ij≧1より,n−1カ所にk−1枚の仕切りをつけて分配する問題と等価になります.
  (n-1)C(k-1)=(n-1,k-1)
 
 したがって,
  Σ(n-1,k-1)=2^(n-1)
より2^(n-1)通りあります.このことより,n=3では4つの順序つき分割
  3=1+1+1,3=1+2,3=2+1,3=3
が存在することがわかります.
 
===================================
 
【5】制限のある分割
 
 制限のない分割に対する母関数については,前節で述べましたが,たとえば,最大の整数がmax,最小の整数がminである場合のnの分割に対する母関数は,
  f(x)=1/{(1-x^min)(1-x^(min+1))・・・(1-x^(max-1))(1-x^max)}
と書くことができます.
 
 同様に,6以上の偶数に分割する場合の母関数は
  f(x)=1/{(1-x^6)(1-x^8)(1-x^10)・・・}
となるのですが,次に,nをすべて異なる数に分割する仕方について考えましょう.
 
 この場合の母関数は,各整数を高々1回,繰り返すことなく取ることになるますから,制限のない場合の母関数
  f(x)=(1+x+x^2+・・・)(1+x^2+x^4+・・・)(1+x^3+x^6+・・・)・・・
の因数を1以外に1つの項だけもつようにすればよい,したがって,
  f(x)=(1+x)(1+x^2)(1+x^3)・・・
となることがわかります.
 
 また,この母関数は
  (1+x)(1+x^2)(1+x^3)・・・
  =(1-x^2)/(1-x)・(1-x^4)/(1-x^2)・(1-x^6)/(1-x^3)・・・
  =1/(1-x)(1-x^3)(1-x^5)・・・
と書き換えることができます.
 
 これは奇数の整数への分割に対応する母関数であることがわかります.すなわち,
  q(n):nの奇数のみを用いた分割の総数
  r(n):nの互いに異なる数を用いた分割の総数
とすると
  Σq(n)x^n=1/(1-x)(1-x^3)(1-x^5)・・・
  Σr(n)x^n=(1+x)(1+x^2)(1+x^3)・・・
であり,両者の母関数は一致します.
 
 こうして,異なる数への分割と奇数への分割が同数あるという注目すべき結果を得ることができたのですが,例えば,5を異なる数に分割するのは5,4+1,3+2の3通り,奇数に分割するのは5,3+1+1,1+1+1+1+1の3通りというわけです.
 
 もし,物理状態がn個の基本粒子の分割に関係しているとすると,相異なる分割と奇数の分割は区別できないことがわかったのですが,実際,整数の分割問題は,現在では,統計力学(Maxwell-Boltzmann統計,Bose-Einstein統計,Fermi-Dirac統計)など様々な分野で実際的な問題を解決するのに用いられています.
 
===================================
 
[補]統計力学
 
 n個の箱にr個の玉を入れる問題を考えます.箱を空間の小領域,玉を気体の分子と見立てて,ボルツマンは統計力学(Maxwell-Boltzmann統計)を構成しました.MB統計では1つの玉の入れ方がn通りで,玉がr個ですから全部でn^r通りの入れ方があると考えます.しかし,このように考えると,黒体輻射の実験がどうしてもうまく説明できませんでした.
 
 そこで,玉は区別がつかないと仮定すると,n個の箱に区別できないr個の玉を入れる入れ方は重複組合せnHr通り=n+r-1Cr通りあることになり,新たな統計力学が構成されます.この統計力学はBose-Einstein統計と呼ばれ,光子や中性子がうまく当てはまります.BE統計にしたがう素粒子はボゾン(boson)と呼ばれます.
 
 さらに,1つの箱には玉は1つしか入らないとするパウリの排他則を仮定すると重複のない組合せnCr通りとなり,Fermi-Diracの統計が得られます.FD統計にしたがう素粒子に電子や陽子があり,それらはフェルミオン(fermion)と総称されます.
 
 別の言い方をすると,宇宙を作っている粒子には2種類あり,物質の素になる粒子がフェルミオン(電子やクォークなど),力の素になる粒子がボゾン(光子など)なのですが,宇宙はひもから構成されているというのが「ひも理論」であり,フェルミオンのひもとボゾンのひもの2種類からなるというわけです.
 
 ひも理論の場合,フェルミオンは10次元,ボゾンは26次元というとんでもない値をとるのですが,これについてはコラム「ひもの棲む世界」で説明したとおりです.
 
[補]同じ成分が高々d回しか現れない整数nの分割の個数の母関数
  Σs(n)x^n=Π(1+x^n+x^2+・・・+x^dn)=Π(1-x^(d+1)n)/(1-x^n)
 
===================================
 
【6】オイラーの五角数定理
 
 ある恒等式が分割の立場から何を意味するかという逆問題を考えてみましょう.
 
  1/(1-x)=1+x+x^2+x^3+x^4+・・・
      =(1+x)(1+x^2)(1+x^4)(1+x^8)・・・
において,1+x+x^2+x^3+x^4+・・・の指数は整数そのものの母関数と考えられます.一方,(1+x)(1+x^2)(1+x^4)(1+x^8)・・・は整数を繰り返しなしで2のベキに分解しています.したがって,各整数は2のベキの総和として一意に表せることを意味しているのです.
  n=k1+2k2+2^2k3+・・・
 
 オイラーが発見した定理をもう一つ紹介しておきましょう.分割数p(n)の母関数の逆数
  Π(1-x^n)=(1-x)(1-x^2)(1-x^3)・・・
を考えます.これを展開すると,級数中の係数がすべて0か±1の級数
  Π(1-x^n)=1-x-x^2+x^5+x^7-x^12-x^15+x^22+x^26-x^35-x^40+x^51+・・・
       =Σ(x^(6m^2-m)-x^(6m^2+5m+1))
が得られますが,これが何を意味しているかを発見できるでしょうか?
 
 一見したところ,何を意味しているのかすら明らかではないのですが,この級数は,mが負になる項も含んだ
  Π(1-x^n)=Σ(-1)^mx^(m(3m-1)/2))
の形にまとめられ,ここで指数の引数がm(3m−1)/2,すなわち,1,5,12,22,35,51,・・・という数列がピタゴラスの五角数であることから,五角数定理と呼ばれています.
 
 この恒等式は,級数中のx^nの係数がすべて0か±1なのですが,組合せ論の解釈から,偶数個の異なる整数への分割数と奇数個の異なる整数への分割数の差
  peven(n)-podd(n)=(-1)^m    n=m(3m+1)/2
  peven(n)-podd(n)=0      その他の場合
を表すものと考えられます.
 
 たとえば,n=8の場合,偶数個の異なる整数への分割は7+1=6+2=5+3の3通り,奇数個の異なる整数への分割は8=5+2+1=4+3+1の3通りですから,その差は0となります.
 
 個数の差があるのはn=m(3m+1)/2またはn=m(3m−1)/2,すなわち,
  n=1,2,5,7,12,15,22,26,・・・
の場合で,このn=m(3m±1)/2を5角数といいます.nが5角数の場合に限ってpeven(n)とpodd(n)が異なるのですが,五角数は分割問題でも役立つというわけです.
 
 五角数定理はオイラーが分割関数p(n)の研究中に発見した関数等式です(1750年).斉藤正光氏(U.S.A.在住)の談によると「オイラーの五角数定理はヤコビの三重積公式を使うとあっさり証明できる」そうですが,現在,五角数定理にはヤコビの三重積公式による証明やフランクリンによる組合せ的証明があります.
 
 斉藤氏のご指摘のように,五角数定理の完全な証明は,ヤコビのテータ関数や保型形式の理論の中に求められなければなりません.しかし,ヤコビを待つまでもなく,オイラーは五角数定理を証明しました.オイラーはこの定理の証明にほぼ10年を要した(発見は1741年,証明は1750年)のですが,その間,たとえ完全な証明は与えられなくとも正しいことは間違いないことを確信していて,結果の正しさについて,微塵の疑いも抱いていなかったようです.
 
 オイラー自身による証明はヴェイユの「数論」に紹介されています.梅田亨先生の解説によると,今日的な眼からすれば,オイラーの証明には無限次行列に対する跡公式と呼ばれるアイディアが使われているというのですが,跡公式とは,行列Aにおいて対角和=固有値の和,すなわち
  trA=Σλ
の左辺が解析的,右辺が幾何学的に得られたものであるように,ある作用素の跡を2通りの方法で計算することにより得られる等式であって,作用素とはいわば無限次行列のことと考えておくとよいと思われます.
 
 2通りに計算するということを喩えていうならば,家計簿つけのシーンにおいて,まず行ごとの合計を求めそれを総計する,次に列ごとの合計を求めそれを総計する,そして計算が正しければその2つの計算結果は一致するはずというわけです.
 
 なお,オイラーの五角数定理
  Π(1-x^n)=Σ(-1)^mx^(m(3m-1)/2))
により
  x^(1/24)/f(x)=Σ(-1)^nx^((6n-1)^2/24)
したがって,左辺はデデキントのイータ関数の定義そのもの,また,右辺は確かにテータ級数(ベキが平方数であるような交代級数:例えば,1-x+x^4-x^9+x16-・・・)であることがわかります.
 
 オイラーの五角数定理は,左辺がイータ関数,右辺がテータ関数と呼ばれる保型形式の原型を与えていたので,19世紀には,
  デデキントのイータ関数=ヤコビのテータ関数
すなわち,保型形式の間の等式と捉えられるようになりました.
 
 分割関数の母関数は本質的にモジュラー形式を与えるというわけで,さらに,1987年,ウィッテンにより,素粒子の超弦理論はアデール理論として捉えられたことにより,最近では素粒子の超弦理論との関連も研究されています.
 
===================================
 
[補]ヤコビの三角数定理
 
 1750年のオイラーによる五角数定理
  Π(1-x^n)=Σ(-1)^mx^(m(3m-1)/2))   m(3m-1)/2は五角数
に対して,ヤコビの三角数定理(1829年)とは
  Π(1-x^n)^3=Σ(-1)^m(2m+1)x^((m^2+m)/2)   (m^2+m)/2は三角数
で与えられる関数等式です.
 
 なお,三角数の母関数は
  (1-x^2)(1-x^4)(1-x^6)・・・/(1-x)(1-x^3)(1-x^5)・・・
  =1+x+x^3+x^6+x^10+・・・
となります.
 
===================================
 
[補]m角数定理
 
 多角数という名前はそれぞれの図形の点の配置に由来するもので,ピタゴラスらが興味をもった図形数ですから,代数的にではなく図形的に考えてみることにしましょう.
 
 そうすると,n−1番目の三角数をΔn-1=(n−1)n/2とすると,多角形にΔn-1個の点からなる三角形を追加して作ることができるわけですから
  n+(m−2)Δn-1=1/2・n・{2+(m−2)(n−1)}
とも考えることができます.
 
 一般に,m角数の第n項は,多角形の辺数mは公差よりも2だけ大きいことから,初項1,公差m−2の等差数列の和:
  1/2・n・{2+(m−2)(n−1)}
で与えられることがわかります.
 
 1/2・n・{2+(m−2)(n−1)}の形の自然数をm角数といいます.すなわち,三角数△nとはn(n+1)/2,四角数□nとはn^2の形の自然数,すなわち平方数です.五角数☆nはn(3n−1)/2で表されます.
 
 ガウスは1796年の日記に「わかった! n=△+△+△」と書いていますが,それはすべての整数は3つの3角数の和によって表しうるという意味で,m=3の場合についての証明に相当します.ガウスの発見は8n+3の形をしたすべての整数を3つの奇数の平方の和として表せることを意味していて,3平方和定理「8n+7の形の自然数は3つの平方数の和では表せない」を用いると「n=△+△+△」を簡単に示すことができます.
 
(証明)4^k(8n+7)でない奇数は3平方和で表せますから,任意の自然数nに対して8n+3=x^2+y^2+z^2と書けます.このとき,x=2p+1,y=2q+1,z=2r+1とおくと
  n=p(p+1)/2+q(q+1)/2+r(r+1)/2
 
 「m角数定理」とは「すべての自然数はたかだかm個のm角数で表せる」というものです.この定理で,m=3の場合がガウスの定理「n=△+△+△」,m=4の場合がラグランジュの定理「n=□+□+□+□」に相当します.m=5の場合が五角数定理「n=☆+☆+☆+☆+☆」の相当するわけですが,フェルマーが遺して後世を悩ましていたこの命題は,オイラー,ラグランジュ,ルジャンドルなどの研究を経て,1813年,コーシーが証明しセンセーションを巻き起こしました.
 
===================================
 
[参]シュレーダー「科学と通信における数論」コロナ社
 
===================================