دالة التقسيم (نظرية الأعداد)

في نظرية الأعداد ، تمثل دالة التقسيم p ( n ) عدد التقسيمات الممكنة لعدد صحيح غير سالب n . على سبيل المثال، p (4) = 5 لأن العدد الصحيح 4 له خمسة تقسيمات هي: 1 + 1 + 1 + 1 ، 1 + 1 + 2 ، 1 + 3 ، 2 + 2 ، و 4 .

لا توجد صيغة مغلقة معروفة لدالة التقسيم، ولكن لها متسلسلات تقاربها بدقة، وعلاقات تكرارية يمكن من خلالها حسابها بدقة. تنمو هذه الدالة كدالة أسية للجذر التربيعي لمتغيرها. المعكوس الضربي لدالتها المولدة هو دالة أويلر ؛ وبحسب نظرية أويلر للأعداد الخماسية ، فإن هذه الدالة هي مجموع متناوب لقوى الأعداد الخماسية لمتغيرها.

اكتشف سرينيفاسا رامانوجان لأول مرة أن دالة التقسيم تحتوي على أنماط غير بديهية في الحساب النمطي ، والمعروفة الآن باسم تطابقات رامانوجان . على سبيل المثال، عندما ينتهي التمثيل العشري للعدد n بالرقم 4 أو 9، فإن عدد تقسيمات n سيكون قابلاً للقسمة على 5.

بالنسبة لعدد صحيح موجب n ، فإن p ( n ) هو عدد الطرق المختلفة لتمثيل n كمجموع أعداد صحيحة موجبة. ولأغراض هذا التعريف، فإن ترتيب الحدود في المجموع غير مهم: فمجموعان لهما نفس الحدود بترتيب مختلف (مثل 1 + 1 + 2 و 1 + 2 + 1 ) لا يُعتبران مختلفين. ^{[ أ ]}

بحسب الاصطلاح، فإن p (0) = 1 ، إذ توجد طريقة واحدة لتمثيل الصفر كمجموع أعداد صحيحة موجبة ( المجموع الفارغ ). علاوة على ذلك، فإن p ( n ) = 0 عندما يكون n سالبًا.

القيم القليلة الأولى لدالة التقسيم، بدءًا من p (0) = 1 ، هي

تتضمن بعض القيم الدقيقة لـ p ( n ) للقيم الأكبر من 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 ]}$$\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}}}$$يتم الحصول على المساواة بين نواتج الضرب في السطرين الأول والثاني من هذه الصيغة عن طريق فك كل عامل.${\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}}$في المجموع على اليسار. لذلك، فإن المجموع يساوي حاصل الضرب.

الدالة التي تظهر في المقام في السطرين الثالث والرابع من الصيغة هي دالة أويلر . والمساواة بين حاصل الضرب في السطر الأول والصيغ في السطرين الثالث والرابع هي نظرية أويلر للأعداد الخماسية . أسس${\displaystyle x}$في هذه الأسطر توجد الأعداد الخماسية${\displaystyle P_{k}=k(3k-1)/2}$ل${\displaystyle k\in \{0,1,-1,2,-2,\dots \}}$(مُعمَّمة إلى حد ما من الأعداد الخماسية المعتادة، والتي تأتي من نفس الصيغة للقيم الموجبة لـ${\displaystyle k}$نمط الإشارات الموجبة والسالبة في السطر الثالث يأتي من المصطلح${\displaystyle (-1)^{k}}$في السطر الرابع: خيارات متساوية من${\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}$وبدون أجزاء مكررة، فإنه يتبع ذلك بتقسيم كل قسم إلى أجزائه الزوجية وأجزائه الفردية، وقسمة الأجزاء الزوجية على اثنين، وهو ^{[ 6 ]}$${\displaystyle p(n)=\sum _{k=0}^{\left\lfloor n/2\right\rfloor }q(n-2k)p(k).}$$

يُنسب إلى سرينيفاسا رامانوجان اكتشاف أن دالة التقسيم لها أنماط غير بديهية في الحساب النمطي . على سبيل المثال، يكون عدد التقسيمات قابلاً للقسمة على خمسة كلما كان التمثيل العشري لـ${\displaystyle n}$ينتهي بالرقم 4 أو 9، كما هو موضح في التطابق ^{[ 7 ]}$${\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}).}$$يمكن الحصول على برهان قصير لهذه النتيجة من دالة توليد دالة التقسيم.

اكتشف رامانوجان أيضًا التطابقات modulo 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}}}$لأي عدد أولي b غير 5 أو 7 أو 11. ^{[ 10 ]} بدلاً من ذلك، وللحصول على تطابق، فإن حجة${\displaystyle p}$ينبغي أن يتخذ الشكل${\displaystyle cbk+a}$بالنسبة للبعض${\displaystyle c>1}$في ستينيات القرن العشرين، اكتشف أ. أو. إل. أتكين من جامعة إلينوي في شيكاغو تطابقات إضافية من هذا الشكل للأعداد الأولية الصغيرة. على سبيل المثال: $${\displaystyle p(11^{3}\cdot 13\cdot k+237)\equiv 0{\pmod {13}}.}$$

أثبت كين أونو ( 2000 ) وجود مثل هذه التطابقات لكل عدد أولي بمعامل أكبر من 3. وفي وقت لاحق، أظهر أهلغرين وأونو (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 ، وبشكل مستقل بواسطة جيه في أوسبنسكي في عام 1920. وبالنظر إلى${\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}$الحد النوني من متسلسلة رادماخر هو من الرتبة $${\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})}$، والتي تحتوي على ما يزيد قليلاً عن 11 مليار رقم. ^{[ 20 ]}

بشكلٍ أعم، يمكن النظر في التقسيمات المقتصرة على عناصر مجموعة جزئية A من الأعداد الطبيعية (على سبيل المثال، قيد على القيمة القصوى للأجزاء)، أو قيد على عدد الأجزاء أو على أقصى فرق بينها. كل قيد من هذه القيود يُنتج دالة تقسيم مرتبطة به ذات خصائص محددة. فيما يلي بعض الأمثلة الشائعة.

• أول 4096 قيمة من دالة التقسيم