В теории чисел , то функция распределения р ( п ) представляет собой число возможных перегородок из неотрицательного целого числа п . Например, p (4) = 5, потому что целое число 4 имеет пять разделов 1 + 1 + 1 + 1 , 1 + 1 + 2 , 1 + 3 , 2 + 2 и 4 .
Нет замкнутая форма выражения для функции разбиения не известно, но она имеет как асимптотические разложения , которые точно аппроксимировать его и рекуррентные соотношения , с помощью которого он может быть рассчитаны точно. Он растет как экспоненциальная функция от квадратного корня из аргумента. Мультипликативный обратное его порождающей функции является функция Эйлера ; по теореме Эйлера о пятиугольных числах эта функция представляет собой переменную сумму пятиугольных числовых степеней своего аргумента.
Шриниваса Рамануджан первым обнаружил, что статистическая сумма имеет нетривиальные закономерности в модульной арифметике , теперь известные как сравнения Рамануджана . Например, всякий раз, когда десятичное представление n заканчивается цифрой 4 или 9, количество разделов n будет делиться на 5.
Определение и примеры
Для положительного целого числа п , р ( п ) является числом различных способов представления п в виде суммы положительных целых чисел. Для целей этого определения порядок членов в сумме не имеет значения: две суммы с одними и теми же членами в разном порядке не считаются различными.
По соглашению p (0) = 1 , поскольку есть один способ ( пустая сумма ) представить ноль как сумму положительных целых чисел. По той же причине, по определению, p ( n ) = 0, когда n отрицательно.
Первые несколько значений статистической суммы, начиная с p (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 ).
Некоторые точные значения p ( n ) для больших значений n включают: [1]
По состоянию на февраль 2020 г.[Обновить], наибольшее известное простое число среди значений p ( n ) - это p (1289844341) с 40 000 десятичных цифр. [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,для некоторых а . Однако совпадения формы нет.для любого простого числа b, кроме 5, 7 или 11. [11] Вместо этого, чтобы получить сравнение, аргумент должен принять форму для некоторых . В 1960-х годах AOL Atkin из Университета Иллинойса в Чикаго обнаружил дополнительные сравнения этой формы для малых простых модулей. Например:
Кен Оно ( 2000 ) доказал, что такие сравнения существуют для каждого простого модуля больше 3. Позже Альгрен и Оно (2001) показали, что существуют сравнения разбиения по модулю каждого целого числа, взаимно простого с 6. [12] [13]
Формулы аппроксимации
Существуют формулы приближения, которые вычисляются быстрее, чем точная формула, приведенная выше.
Асимптотическое выражение для р ( п ) задается
- в виде .
Эта асимптотическая формула была впервые получена Дж. Харди и Рамануджаном в 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» , Novi Commentarii academiae scientiarum Petropolitanae (на латинском языке), 3 : 125–169
- ^ Юэлл, Джон А. (2004), "Рецидивы для функции распределения и ее родственники", Скалистые горы Журнал математики , 34 (2): 619-627, DOI : 10,1216 / RMJM / 1181069871 , JSTOR 44238988 , MR 2072798
- ^ Уилф, Герберт С. (1982), "Что такое ответ?", American Mathematical Monthly , 89 (5): 289-292, DOI : 10,2307 / 2321713 , MR 0653502
- ^ Ал, Бусра; Алкан, Мустафа (2018), «Заметка об отношениях между разделами», Proc. Средиземноморский Int. Конф. Чистая и прикладная математика. и связанные области (MICOPAM 2018) , стр. 35–39.
- ^ а б Харди, GH ; Райт, EM (2008) [1938], Введение в теорию чисел (6-е изд.), Oxford University Press , стр. 380, ISBN 978-0-19-921986-5, Руководство по ремонту 2445243 , Zbl 1159.11001
- ^ Берндт, Брюс С .; Оно, Кен (1999), «Неопубликованная рукопись Рамануджана о функциях разбиения и тау с доказательствами и комментариями» (PDF) , The Andrews Festschrift (Maratea, 1998) , Séminaire Lotharingien de Combinatoire , 42 , Art. B42c, 63, МР 1701582
- ^ а б Оно, Кен (2004), Сеть модульности: арифметика коэффициентов модульных форм и-series , Серия региональных конференций CBMS по математике, 102 , Провиденс, Род-Айленд: Американское математическое общество , с. 87, ISBN 0-8218-3368-5, Zbl 1119,11026
- ^ Альгрен, Скотт; Бойлан, Мэтью (2003), "Арифметические свойства функции распределения" (PDF) , Inventiones Mathematicae , 153 (3): 487-502, DOI : 10.1007 / s00222-003-0295-6 , МР 2000466
- ^ Оно, Кен (2000), "Распределение статистической суммы по модулю» Анналы математики , 151 (1): 293-307, Arxiv : математика / 0008140 , DOI : 10,2307 / 121118 , МР 1745012 , Zbl +0984,11050
- ^ Альгрен, Скотт; Оно, Кен (2001), «Свойства сравнения для статистической суммы» (PDF) , Proceedings of the National Academy of Sciences , 98 (23): 12882–12884, Bibcode : 2001PNAS ... 9812882A , doi : 10.1073 / pnas. 191488598 , Руководство по ремонту 1862931
- ^ а б Харди, GH ; Рамануджан, С. (1918), "Асимптотические формулы в комбинаторном анализе", Труды Лондонского математического общества , Вторая серия, 17 (75–115). Перепечатано в Сборнике бумаг Шриниваса Рамануджана , амер. Математика. Soc. (2000), стр. 276–309.
- ^ Эндрюс, Джордж Э. (1976), Теория разделов , Издательство Кембриджского университета, стр. 69, ISBN 0-521-63766-X, Руководство по ремонту 0557013
- ^ Радемахер, Ганс (1937), "О статистической сумме» Труды Лондонского математического общества , вторая серия, 43 (4): 241-254, DOI : 10,1112 / ПНИЛ / s2-43.4.241 , MR 1575213
- ^ Erdős, P. (1942), "Об одном элементарного доказательства некоторых асимптотических формул в теории разбиений" (PDF) , Анналы математики , вторая серия, 43 : 437-450, DOI : 10,2307 / 1968802 , MR 0006749 , Zbl 0061.07905
- ^ Натансон, МБ (2000), Элементарные методы в теории чисел , Тексты для выпускников по математике , 195 , Springer-Verlag , p. 456, ISBN 0-387-98912-9, Zbl 0953,11002
- ^ Johansson, Фредрик (2012), "Эффективное осуществление формулы Харди-Рамануджана-Радемахера", LMS Журнал вычислений и математики , 15 : 341-59, Arxiv : 1205,5991 , DOI : 10,1112 / S1461157012001088 , МР 2988821
- ^ Йоханссон, Фредрик (2 марта 2014 г.), Новая запись функции распределения: вычислено p (10 20 )
Внешние ссылки
- Первые 4096 значений статистической суммы