Функция распределения (теория чисел) - Partition function (number theory)

Ценности ${\displaystyle p(1),\dots p(8)}$ статистической суммы (1, 2, 3, 5, 7, 11, 15 и 22) можно определить путем подсчета Диаграммы Юнга для разделов чисел от 1 до 8.

В теория чисел, то функция распределения п(п) представляет номер возможных перегородки неотрицательного целого числа п. Например, п(4) = 5 потому что целое число 4 имеет пять разделов 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, и 4.

Нет выражение в закрытой форме для статистической суммы известна, но она имеет как асимптотические разложения которые точно его аппроксимируют и повторяющиеся отношения по которому его можно рассчитать точно. Он растет как экспоненциальная функция из квадратный корень своего аргумента. В мультипликативный обратный своего производящая функция это Функция Эйлера; Эйлера теорема о пятиугольных числах эта функция представляет собой переменную сумму пятиугольное число сила его аргумента.

Шриниваса Рамануджан впервые обнаружил, что статистическая сумма имеет нетривиальные закономерности в модульная арифметика, теперь известный как Сравнение Рамануджана. Например, когда десятичное представление п оканчивается цифрой 4 или 9, количество разделов п будет делиться на 5.

Определение и примеры

Для положительного целого числа п, п(п) это количество различных способов представления п как сумма натуральных чисел. Для целей этого определения порядок членов в сумме не имеет значения: две суммы с одинаковыми элементами в разном порядке не считаются различными.

Условно п(0) = 1, так как есть один способ ( пустая сумма ) представления нуля как суммы положительных целых чисел. По той же причине по определению п(п) = 0 когда п отрицательный.

Первые несколько значений статистической суммы, начиная с п(0) = 1, находятся:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604,… (последовательность A000041 в OEIS ).

Некоторое точное значение п(п) для больших значений п включают:^[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}}}$

По состоянию на сентябрь 2017 г.^{[Обновить]}, самый крупный из известных простое число среди ценностей п(п) является п(221444161), с 16 569 десятичными цифрами.^[2]

Производящая функция

Основная статья: Теорема о пятиугольном числе

В производящая функция за п(п) дан кем-то^[3]

${\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }p(n)x^{n}&=\prod _{k=1}^{\infty }\left({\frac {1}{1-x^{k}}}\right)\\&=(1+x+x^{2}+x^{3}+\cdots )(1+x^{2}+x^{4}+x^{6}+\cdots )(1+x^{3}+x^{6}+x^{9}+\cdots )\cdots \\&={\frac {1}{1-x-x^{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}}$, только конечное число из которых может быть ненулевым. Показатель члена равен ${\displaystyle 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}$. Этот результат обусловлен Леонард Эйлер.^[4] Формулировка производящей функции Эйлера является частным случаем ${\displaystyle q}$-Почхаммер символ и аналогичен рецептуре многих модульные формы, и в частности Функция Дедекинда эта.

Повторяющиеся отношения

Такая же последовательность пятиугольных чисел появляется в отношение повторения для статистической суммы:^[5]

${\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)}$ может быть дано в терминах функция суммы делителей σ:^[6]

${\displaystyle p(n)={\frac {1}{n}}\sum _{k=0}^{n-1}\sigma (n-k)p(k).}$

Если ${\displaystyle q(n)}$ обозначает количество разделов ${\displaystyle n}$ без повторяющихся частей, тогда следует разбить каждое разделение на его четные части и нечетные части и разделить четные части на два, что^[7]

${\displaystyle p(n)=\sum _{k=0}^{\left\lfloor n/2\right\rfloor }q(n-2k)p(k).}$

Сравнения

Основная статья: Сравнение Рамануджана

Шриниваса Рамануджан приписывают открытие, что статистическая сумма имеет нетривиальные закономерности в модульная арифметика Например, количество разделов делится на пять, если десятичное представление ${\displaystyle n}$ оканчивается цифрой 4 или 9, что выражается сравнением^[8]

${\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}}},}$

также Рамануджаном,^[9][10] где обозначение ${\displaystyle (x)_{\infty }}$ обозначает продукт, определенный как

${\displaystyle (x)_{\infty }=\prod _{m=1}^{\infty }(1-x^{m}).}$

Краткое доказательство этого результата может быть получена из производящей функции статистической суммы.

Рамануджан также обнаружил сравнения по модулю 7 и 11:^[8]

${\displaystyle {\begin{aligned}p(7k+5)&\equiv 0{\pmod {7}},\\p(11k+6)&\equiv 0{\pmod {11}}.\end{aligned}}}$

Они исходят от личности Рамануджана^[10]

${\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}}}$ для некоторых а. Однако совпадения формы нет. ${\displaystyle p(bk+a)\equiv 0{\pmod {b}}}$ для любого прайма б кроме 5, 7 или 11.^[11] Вместо этого, чтобы получить сравнение, аргумент ${\displaystyle p}$ должен принять форму ${\displaystyle cbk+a}$ для некоторых ${\displaystyle c>1}$. В 1960-е гг. Аткин А.О. из Иллинойский университет в Чикаго открыл дополнительные сравнения этого вида для малых простых модулей. Например:

${\displaystyle p(11^{3}\cdot 13\cdot k+237)\equiv 0{\pmod {13}}.}$

Кен Оно  (2000 ) доказал, что такие сравнения существуют для любого простого модуля больше 3. Позже Альгрен и Оно (2001) показал, что есть сравнения разбиения по модулю каждого целого числа совмещать к 6.^[12][13]

Формулы аппроксимации

Существуют формулы приближения, которые вычисляются быстрее, чем точная формула, приведенная выше.

An асимптотический выражение для п(п) дан кем-то

${\displaystyle p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right)}$ в качестве ${\displaystyle n\rightarrow \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 m<k,\;(m,k)=1}e^{\pi i\left(s(m,k)-2nm/k\right)}.}$

Здесь обозначение ${\displaystyle (m,k)=1}$ означает, что сумма должна происходить только по значениям ${\displaystyle m}$ которые относительно простой к ${\displaystyle k}$. Функция ${\displaystyle s(m,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]

Рекомендации

1. Слоан, Н. Дж. А. (ред.), «Последовательность A070177», В Он-лайн энциклопедия целочисленных последовательностей, Фонд OEIS
2. Колдуэлл, Крис К. (2017), Двадцать лучших
3. Абрамовиц, Милтон; Стегун, Ирен (1964), Справочник по математическим функциям с формулами, графиками и математическими таблицами, Министерство торговли США, Национальное бюро стандартов, стр.825, ISBN  0-486-61272-4
4. Эйлер, Леонард (1753), "De partitione numerorum", Новые комментарии academiae scientiarum Petropolitanae (на латыни), 3: 125–169
5. Юэлл, Джон А. (2004), "Повторения для статистической суммы и ее родственников", Математический журнал Скалистых гор, 34 (2): 619–627, Дои:10.1216 / rmjm / 1181069871, JSTOR  44238988, МИСТЕР  2072798
6. Уилф, Герберт С. (1982), «Что такое ответ?», Американский математический ежемесячный журнал, 89 (5): 289–292, Дои:10.2307/2321713, МИСТЕР  0653502
7. Ал, Бусра; Алкан, Мустафа (2018), «Заметка об отношениях между разделами», Proc. Средиземноморский Int. Конф. Чистая и прикладная математика. и связанные области (MICOPAM 2018), стр. 35–39
8. Харди, Г. Х.; Райт, Э.М. (2008) [1938], Введение в теорию чисел (6-е изд.), Oxford University Press, п. 380, ISBN  978-0-19-921986-5, МИСТЕР  2445243, Zbl  1159.11001
9. Берндт, Брюс С.; Оно, Кен (1999), «Неопубликованная рукопись Рамануджана о функциях разбиения и тау с доказательствами и комментариями» (PDF), The Andrews Festschrift (Маратея, 1998), Séminaire Lotharingien de Combinatoire, 42, Изобразительное искусство. B42c, 63, МИСТЕР  1701582
10. Оно, Кен (2004), Сеть модульности: арифметика коэффициентов модульных форм и ${\displaystyle q}$-серии, Серия региональных конференций CBMS по математике, 102, Провиденс, Род-Айленд: Американское математическое общество, п. 87, ISBN  0-8218-3368-5, Zbl  1119.11026
11. Альгрен, Скотт; Бойлан, Мэтью (2003), «Арифметические свойства статистической суммы» (PDF), Inventiones Mathematicae, 153 (3): 487–502, Дои:10.1007 / s00222-003-0295-6, МИСТЕР  2000466
12. Оно, Кен (2000), "Распределение статистической суммы по модулю ${\displaystyle m}$", Анналы математики, 151 (1): 293–307, arXiv:математика / 0008140, Дои:10.2307/121118, МИСТЕР  1745012, Zbl  0984.11050
13. Альгрен, Скотт; Оно, Кен (2001), «Свойства сравнения для статистической суммы» (PDF), Труды Национальной академии наук, 98 (23): 12882–12884, Bibcode:2001PNAS ... 9812882A, Дои:10.1073 / pnas.191488598, МИСТЕР  1862931
14. Харди, Г. Х.; Рамануджан, С. (1918), «Асимптотические формулы в комбинаторном анализе», Труды Лондонского математического общества, Вторая серия, 17 (75–115). Перепечатано в Сборник статей Шринивасы Рамануджана, Амер. Математика. Soc. (2000), стр. 276–309.
15. Эндрюс, Джордж Э. (1976), Теория перегородок, Cambridge University Press, стр. 69, ISBN  0-521-63766-X, МИСТЕР  0557013
16. Радемахер, Ганс (1937), «О статистической сумме ${\displaystyle p(n)}$", Труды Лондонского математического общества, Вторая серия, 43 (4): 241–254, Дои:10.1112 / плмс / с2-43.4.241, МИСТЕР  1575213
17. Эрдеш, П. (1942), «Об элементарном доказательстве некоторых асимптотических формул теории разбиений» (PDF), Анналы математики, Вторая серия, 43: 437–450, Дои:10.2307/1968802, МИСТЕР  0006749, Zbl  0061.07905
18. Натансон, М.Б. (2000), Элементарные методы в теории чисел, Тексты для выпускников по математике, 195, Springer-Verlag, п. 456, г. ISBN  0-387-98912-9, Zbl  0953.11002
19. Йоханссон, Фредрик (2012), «Эффективная реализация формулы Харди – Рамануджана – Радемахера», Журнал вычислений и математики LMS, 15: 341–59, arXiv:1205.5991, Дои:10.1112 / S1461157012001088, МИСТЕР  2988821
20. Йоханссон, Фредрик (2 марта 2014 г.), Новая запись функции раздела: p (10²⁰) вычислено

внешняя ссылка

• Первые 4096 значений статистической суммы