פונקציית החלוקה (תורת המספרים)

חלוקה של מספר טבעי היא הצגה שלו כסכום של מספרים חיוביים, כאשר שינוי בסדר החלקים אינו משנה את החלוקה. למשל 5 = 3+1+1. מספר החלוקות של n מסומן p(n). לדוגמה p(3)=3 ו-p(4)=5. עבור n=1,2,…,10 נקבל את הערכים p(n)=1,2,3,5,7,11,15,22,30,42.

פונקציות החלוקה גדלות מהר. למשל p(100)=190569292 ו-p(1000) בערך 2.4·10^31. ב-1917 הארטדי ורמנוג'אן הוכיחו נוסחה אסימפטוטית שתארת את קצב הגדילה של p(n). הם השתמשו בפונקציות מודולריות, סוג של פונקציות מתמטיות עם סימטריה מיוחדת, ופיתחו את "שיטת המעגל" כדי לאמוד את המקדמים.

רמנוג'אן גילה גם קונגראואנציות מעניינות. קונגראואנציה היא חוק שמסביר חלוקה לפי שארית בחלוקה במספר מסוים. לדוגמה תמיד מתקיים ש-p(5n+4) מתחלק ב-5, ש-p(7n+6) מתחלק ב-7, וש-p(11n+6) מתחלק ב-11. מאוחר יותר נתגלו קונגראואנציות נוספות, ובשנת 2000 הוכיח קן אונו שקיימות זהויות כאלו לכל מספר ראשוני.


לאונרד אוילר חקר את פונקציית החלוקה דרך הפונקציה היוצרת שלה. פונקציה יוצרת היא סדרת חזקות שבה המקדמים הם p(n). אוילר הראה שהפונקציה הזאת ניתנת לכתיבה כמכפלה אינסופית:

g(q)=\sum p(n)q^n=\prod_{m\ge1}(1-q^m)^{-1}.

הפירוק הזה נובע מהאפשרות לבחור כמה פעמים כל מספר k יופיע בחלוקה. הוא גם מאפשר להסיק נוסחאות ושיטות חישוב עבור p(n).

מניפולציות על הפונקציה היוצרת מובילות לנוסחת הנסיגה (recurrence) הידועה, שמבוססת על המספרים המחומשים הכלליים. בצורתה המפורסמת היא נראית כך:

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

כאן האינדקסים 1,2,5,7,12,… הם המספרים המחומשים הכלליים הנתונים על ידי הנוסחה g_k=k(3k-1)/2. הסכום הוא סופי כי p(0)=1 ולכל ערכים שליליים או קטנים מ, 0 המונחים מתאפננים.

חלוקה של מספר פירושה להציג אותו כסכום של מספרים חיוביים. לא מפריע אם משנים את הסדר. למשל 5 = 3+1+1.

מספר החלוקות של מספר מסומן p(n). לדוגמה p(3)=3 ו-p(4)=5. הערכים הראשונים הם 1,2,3,5,7,11,15,22,30,42.

המספרים האלה גדלים מאוד במהירות. לדוגמה p(100) שווה 190,569,292.

אילר גילה דרך חכמה למקם את כל p(n) בסדרה אחת שנקראת פונקציה יוצרת. היא מחברת בין סכומים למכפלה אינסופית. זה עוזר להבין ולחשב חלוקות.

רמנוג'אן מצא תכונות מפתיעות. לפעמים p(n) מתחלק במספרים קטנים לפי חוק פשוט. לדוגמה כל p(5n+4) מתחלק ב-5. חוק כזה נקרא קונגראואנציה. מאוחר יותר הראו שיש עוד חוקי חלוקה כאלו.

יש גם כלל חוזר לחישוב p(n). הוא משתמש ב"מספרים מחומשים", מספרים מיוחדים שמופיעים ברצף 1,2,5,7,12,… . בעזרתם אפשר לחשב p(n) מהערכים הקטנים יותר.

הכללים האלה עוזרים למתמטיקאים להבין איך חלוקות מסודרות ולמצוא תכונות חדשות.