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