分配関数（数論）

数論において、分割関数p ( n ) は、非負整数nの可能な分割の数を表します。たとえば、整数 4 には1 + 1 + 1 + 1、1 + 1 + 2、1 + 3 、2 + 2、および4 の5 つの分割があるため、 p (4) = 5 となります。

分配関数の閉形式表現は知られていないが、それを正確に近似する漸近展開と、それを厳密に計算できる漸化式の両方が存在する。分配関数は引数の平方根の指数関数として増加する。その生成関数の乗法逆関数はオイラー関数であり、オイラーの五角数定理により、この関数は引数の五角数べき乗の交代和となる。

シュリニヴァーサ・ラマヌジャンは、分割関数がモジュラー算術において非自明なパターンを持つことを最初に発見しました。これは現在、ラマヌジャンの合同式として知られています。例えば、nの十進数表現の末尾が4または9の場合、 nの分割数は5で割り切れます。

正の整数nに対して、p ( n )は、 n を正の整数の和として表す異なる方法の数です。この定義においては、和の項の順序は関係ありません。同じ項でも順序が異なる 2 つの和 (例えば、 1 + 1 + 2と1 + 2 + 1 ) は、異なるとはみなされません。^{[ a ]}

慣例として、p (0) = 1 とします。これは、0 を正の整数の和 (空和) として表す方法が 1 つしかないためです。さらに、nが負の場合、p ( n ) = 0 となります。

分配関数の最初のいくつかの値（ p (0) = 1から始まる）は次のとおりである。

nが大きい場合のp ( n )の正確な値には^{[ 1 ]}が含まれます。$${\displaystyle {\begin{aligned}p(100)&=190,\!569,\!292\\p(1000)&=24,\!061,\!467,\!864,\!032,\!622,\!473,\!692,\!149,\!727,\!991\approx 2.40615\times 10^{31}\\p(10000)&=36,\!167,\!251,\!325,\!\dots ,\!906,\!916,\!435,\!144\approx 3.61673\times 10^{106}\end{aligned}}}$$

p ( n )の生成関数は^{[ 2 ]}で与えられる。$${\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }p(n)x^{n}&=\prod _{k=1}^{\infty }\left({\frac {1}{1-x^{k}}}\right)\\&=\left(1+x+x^{2}+\cdots \right)\left(1+x^{2}+x^{4}+\cdots \right)\left(1+x^{3}+x^{6}+\cdots \right)\cdots \\&={\frac {1}{1-xx^{2​​}+x^{5}+x^{7}-x^{12}-x^{15}+x^{22}+x^{26}-\cdots }}\\&=1{\Big /}\sum _{k=-\infty }^{\infty }(-1)^{k}x^{k(3k-1)/2}.\end{aligned}}}$$この式の1行目と2行目の積の等式は、各因子を展開することによって得られます。${\displaystyle 1/(1-x^{k})}$等比数列に${\displaystyle (1+x^{k}+x^{2k}+x^{3k}+\cdots ).}$展開された積が最初の行の和と等しいことを確認するには、積に分配法則を適用します。これにより、積は次の形式の単項式の和に展開されます。${\displaystyle x^{a_{1}}x^{2a_{2}}x^{3a_{3}}\cdots }$ある係数列に対して${\displaystyle a_{i}}$、そのうち非ゼロとなるのは有限個のみである。この項の指数は${\textstyle n=\sum ia_{i}}$、そしてこの合計は、${\displaystyle n}$パーティションとして${\displaystyle a_{i}}$各番号のコピー${\displaystyle i}$したがって、指数を持つ積の項の数は${\displaystyle n}$まさに${\displaystyle p(n)}$係数と同じ${\displaystyle x^{n}}$左側の和において。したがって、和は積に等しくなります。

式の3行目と4行目の分母に現れる関数はオイラー関数です。1行目の積と3行目と4行目の式との等式はオイラーの五角数定理です。${\displaystyle x}$これらの行には五角数があります${\displaystyle P_{k}=k(3k-1)/2}$のために${\displaystyle k\in \{0,1,-1,2,-2,\dots \}}$（通常の五角数からやや一般化したもの。五角数は、正の値に対して同じ公式から得られる。）${\displaystyle k}$3行目の正負の符号のパターンは、次の用語に由来します。${\displaystyle (-1)^{k}}$4行目には、${\displaystyle k}$肯定的な用語を生み出し、奇妙な選択は否定的な用語を生み出す。

より一般的には、分割の生成関数は${\displaystyle n}$集合から選択された数値に${\displaystyle A}$正の整数の は、最初の積の項のうち、次の条件を満たすものだけを取ることによって見つけることができます。${\displaystyle k\in A}$この結果はレオンハルト・オイラーによるものである。^{[ 3 ]}オイラー母関数の定式化は、${\displaystyle q}$-ポッホハマー記号であり、多くのモジュラー形式の積の定式化、特にデデキントのイータ関数に似ています。

同じ五角数列が、分配関数の漸化式に現れる。 ^{[ 4 ]}$${\displaystyle {\begin{aligned}p(n)&=\sum _{k\in \mathbb {Z} \setminus \{0\}}(-1)^{k+1}p(n-k(3k-1)/2)\\&=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)-p(n-22)-\cdots \end{aligned}}}$$ 基本ケースとして、${\displaystyle p(0)}$等しいとみなされる${\displaystyle 1}$、 そして${\displaystyle p(k)}$負の場合はゼロとみなされる ${\displaystyle k}$右辺の和は無限に見えますが、非ゼロの項は有限個しかなく、それは次の非ゼロの値から来ています。${\displaystyle k}$範囲内 $${\displaystyle -{\frac {{\sqrt {24n+1}}-1}{6}}\leq k\leq {\frac {{\sqrt {24n+1}}+1}{6}}.}$$ 漸化式は、同等の形式でも記述できる。 $${\displaystyle p(n)=\sum _{k=1}^{\infty }(-1)^{k+1}{\big (}p(n-k(3k-1)/2)+p(n-k(3k+1)/2){\big )}.}$$

もう一つの漸化式は${\displaystyle p(n)}$除数の和関数σで表すことができる: ^{[ 5 ]}$${\displaystyle p(n)={\frac {1}{n}}\sum _{k=0}^{n-1}\sigma (n-k)p(k).}$$ もし${\displaystyle q(n)}$は、${\displaystyle n}$重複する部分がない場合、各パーティションを偶数部分と奇数部分に分割し、偶数部分を 2 で割ると、^{[ 6 ]が成り立つ。}$${\displaystyle p(n)=\sum _{k=0}^{\left\lfloor n/2\right\rfloor }q(n-2k)p(k).}$$

シュリニヴァーサ・ラマヌジャンは、分割関数がモジュラー算術において非自明なパターンを持つことを発見したとされている。例えば、分割の数は、10進数表現が の場合に 5 で割り切れる。${\displaystyle n}$^{合同式[ 7 ]}で表されるように、数字4または9で終わる。$${\displaystyle p(5k+4)\equiv 0{\pmod {5}}}$$ 例えば、整数4の分割数は5です。整数9の分割数は30、14の分割数は135です。この合同性は、より一般的な恒等式によって示唆されます。 $${\displaystyle \sum _{k=0}^{\infty }p(5k+4)x^{k}=5~{\frac {(x^{5})_{\infty }^{5}}{(x)_{\infty }^{6}}},}$$ またラマヌジャンによっても、^{[ 8 ] [ 9 ]}表記法は${\displaystyle (x)_{\infty }}$は、で定義される積を表します。 $${\displaystyle (x)_{\infty }=\prod _{m=1}^{\infty }(1-x^{m}).}$$この結果の簡単な証明は、分割関数生成関数から得ることができる。

ラマヌジャンは法7と法11の合同式も発見した。^{[ 7 ]}$${\displaystyle {\begin{aligned}p(7k+5)&\equiv 0{\pmod {7}},\\p(11k+6)&\equiv 0{\pmod {11}}.\end{aligned}}}$$ 最初のものはラマヌジャンの恒等式^{[ 9 ]から来ています。}$${\displaystyle \sum _{k=0}^{\infty }p(7k+5)x^{k}=7~{\frac {(x^{7})_{\infty }^{3}}{(x)_{\infty }^{4}}}+49x~{\frac {(x^{7})_{\infty }^{7}}{(x)_{\infty }^{8}}}.}$$

5、7、11は連続する素数なので、次の素数13についても同様の合同関係があると考えるかもしれない。${\displaystyle p(13k+a)\equiv 0{\pmod {13}}}$あるaに対して。しかし、次の形式の合同式は存在しない。${\displaystyle p(bk+a)\equiv 0{\pmod {b}}}$5、7、11以外の任意の素数bに対して。 ^{[ 10 ]}代わりに、合同式を得るには、${\displaystyle p}$形式をとるべきである${\displaystyle cbk+a}$一部の人にとって${\displaystyle c>1}$1960年代、イリノイ大学シカゴ校のAOLアトキンは、小さな素数法に対するこの形式の合同式をさらに発見した。例えば、次のようになる 。$${\displaystyle p(11^{3}\cdot 13\cdot k+237)\equiv 0{\pmod {13}}.}$$

Ken Ono ( 2000 )は、3 より大きいすべての素数の法に対してそのような合同式が存在することを証明しました。その後、AhlgrenとOno (2001)は、6 と互いに素なすべての整数を法とする分割合同式が存在することを示しました。 ^{[ 11 ] [ 12 ]} 

ニューマン予想は、1960年に数学者モリス・ニューマンによって定式化された、分割関数の合同に関する未解決問題である。^{[ 13 ]}この予想は、任意の整数r、mが与えられたとき、${\displaystyle 0\leq r\leq m-1}$、非負整数nは無限に存在し、${\displaystyle p(n)\equiv r{\pmod {m}}}$。

上記の厳密な式よりも計算が速い近似式が存在する。

p ( n )の漸近表現は次のように与えられる。

${\displaystyle p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right)}$として${\displaystyle n\to \infty }$。

この漸近公式は、1918年にGHハーディとラマヌジャンによって初めて得られ、 1920年にはJVウスペンスキーによって独立に得られた。${\displaystyle p(1000)}$漸近式では約${\displaystyle 2.4402\times 10^{31}}$、上記の正確な答えにかなり近い値です（真の値より1.415%大きい）。

ハーディとラマヌジャンは、この近似を第一項とする漸近展開を得た。 ^{[ 14 ]}$${\displaystyle p(n)\sim {\frac {1}{2\pi {\sqrt {2}}}}\sum _{k=1}^{v}A_{k}(n){\sqrt {k}}\cdot {\frac {d}{dn}}\left({{\frac {1}{\sqrt {n-{\frac {1}{24}}}}}\exp \left[{{\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}}\,\,\,\right]}\right),}$$ どこ $${\displaystyle A_{k}(n)=\sum _{0\leq h<k,\;(h,k)=1}e^{\pi i\left(s(h,k)-2nh/k\right)}.}$$ ここでは、表記法${\displaystyle (h,k)=1}$合計は、${\displaystyle h}$比較的優良な${\displaystyle k}$. 機能${\displaystyle s(h,k)}$これはデデキント和です。

エラーの後${\displaystyle v}$項は次の項のオーダーであり、${\displaystyle v}$オーダーとしては${\displaystyle {\sqrt {n}}}$例えば、ハーディとラマヌジャンは、${\displaystyle p(200)}$最初の合計に最も近い整数${\displaystyle v=5}$シリーズの用語。^{[ 14 ]}

1937年、ハンス・ラデマッハーは、収束級数表現を提供することで、ハーディとラマヌジャンの結果を改善することができた。${\displaystyle p(n)}$. それは^{[ 15 ] [ 16 ]}$${\displaystyle p(n)={\frac {1}{\pi {\sqrt {2}}}}\sum _{k=1}^{\infty }A_{k}(n){\sqrt {k}}\cdot {\frac {d}{dn}}\left({{\frac {1}{\sqrt {n-{\frac {1}{24}}}}}\sinh \left[{{\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}}\,\,\,\right]}\right).}$$

ラデマッハーの公式の証明には、フォード円、ファレイ数列、モジュラー対称性、およびデデキントのイータ関数が関係する。

次のように示されるかもしれない。${\displaystyle k}$ラデマッハー級数の第 1 項は、次のオーダーである。 $${\displaystyle \exp \left({\frac {\pi }{k}}{\sqrt {\frac {2n}{3}}}\right),}$$ そのため、最初の項はハーディ・ラマヌジャン漸近近似を与える。 ポール・エルデシュ（1942 ）は、漸近公式の初等的な証明を発表した。 ${\displaystyle p(n)}$[ ^{17 ] [ 18 ]​}

ハーディ・ラマヌジャン・ラデマッハーの公式をコンピュータ上で効率的に実装するための手法については、ヨハンソン（2012）が論じており、彼は、${\displaystyle p(n)}$時間で計算できます${\displaystyle O(n^{1/2+\varepsilon })}$いかなる場合でも${\displaystyle \varepsilon >0}$これは、結果の桁数と一致するため、ほぼ最適である。^{[ 19 ]}正確に計算された分割関数の最大値は${\displaystyle p(10^{20})}$110億桁強の数字を持つ。^{[ 20 ]}

より一般的には、自然数の部分集合Aの要素のみに限定した分割（例えば、各部分の最大値に制限を設ける場合）や、部分の数、あるいは部分間の最大差に制限を設ける分割を考えることができる。それぞれの制限によって、固有の性質を持つ分割関数が対応する。以下にいくつかの一般的な例を示す。

• 分割関数の最初の4096個の値