Статистическая сумма (теория чисел)

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

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

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

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

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

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

По соглашению 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 включают:

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

По состоянию на июнь 2022 г. , самое большое известное простое число среди значений p ( n ) — это p (1289844341) с 40 000 десятичными цифрами. До марта 2022 года это было также самое большое простое число, которое было доказано с помощью доказательства простоты эллиптической кривой .

Генерирующая функция

Использование метода Эйлера для нахождения p (40) : линейка со знаками плюс и минус (серый прямоугольник) сдвигается вниз, соответствующие члены добавляются или вычитаются. Положения знаков задаются разностью чередующихся натуральных (синих) и нечетных (оранжевых) чисел. В файле SVG наведите указатель мыши на изображение, чтобы переместить линейку.

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

для Производящая функция p ( n ) определяется выражением

$${\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}+x^{3}+\cdots \right)\left(1+x^{2}+x^{4}+x^{6}+\cdots \right)\left(1+x^{3}+x^{6}+x^{9}+\cdots \right)\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}}$$

Равенство произведений в первой и второй строках этой формулыполучается путем расширения каждого фактора $1/(1-x^{k})$ в геометрическую серию $(1+x^{k}+x^{2k}+x^{3k}+\cdots ).$Чтобы увидеть, что развернутое произведение равно сумме в первой строке,применить распределительный закон к продукту. Это разлагает произведение в сумму мономов вида $x^{a_{1}}x^{2a_{2}}x^{3a_{3}}\cdots$ для некоторой последовательности коэффициентов $a_{i}$, только конечное число из которых может быть отличным от нуля.Показатель термина ${\textstyle n=\sum ia_{i}}$, и эту сумму можно интерпретировать как представление $n$ как перегородка на $a_{i}$ копии каждого номера $i$. Следовательно, количество членов произведения, имеющих показатель степени $n$ это точно $p(n)$, то же, что и коэффициент $x^{n}$ в сумме слева.Следовательно, сумма равна произведению.

Функция, стоящая в знаменателе в третьей и четвертой строках формулы, — это функция Эйлера . Равенство произведения в первой строке и формул в третьей и четвертой строках — это теорема Эйлера о пятиугольных числах .Экспоненты $x$ в этих строках пятиугольные числа $P_{k}=k(3k-1)/2$ для $k\in \{0,1,-1,2,-2,\dots \}$ (несколько обобщено из обычных пятиугольных чисел, которые происходят из той же формулы для положительных значений $k$). Схема положительных и отрицательных знаков в третьей строке происходит от термина $(-1)^{k}$ в четвертой строке: четные варианты $k$ порождают положительные термины, а нечетный выбор порождает отрицательные термины.

В более общем смысле, производящая функция для разбиений $n$ на числа, выбранные из набора $A$ натуральных чисел можно найти, взяв только те члены первого произведения, для которых $k\in A$. Этот результат принадлежит Леонарду Эйлеру . Формулировка производящей функции Эйлера является частным случаем $q$-Символ Поххаммера и аналогичен формулировке произведения многих модульных форм , в частности эта-функции Дедекинда .

Рекуррентные отношения

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

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

В качестве базовых случаев $p(0)$ принимается равным $1$, и $p(k)$ принимается равным нулю для отрицательных $k$. Хотя сумма в правой части кажется бесконечной, она имеет лишь конечное число ненулевых членов:исходя из ненулевых значений $k$ в диапазоне

$$-{\frac {{\sqrt {24n+1}}-1}{6}}\leq k\leq {\frac {{\sqrt {24n+1}}+1}{6}}.$$

Еще одно рекуррентное соотношение для $p(n)$ может быть задано через функцию суммы делителей σ :

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

Если $q(n)$ обозначает количество разделов $n$ без повторяющихся частей, то, разделив каждую часть на четные и нечетные части и разделив четные части на две, получим

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

Сравнения

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

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

$$p(5k+4)\equiv 0{\pmod {5}}$$

Например, количество разделов для целого числа 4 равно 5.Для целого числа 9 количество разделов равно 30; на 14 имеется 135 разделов. Это соответствие следует из более общего тождества

$$\sum _{k=0}^{\infty }p(5k+4)x^{k}=5~{\frac {(x^{5})_{\infty }^{5}}{(x)_{\infty }^{6}}},$$

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

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

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

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

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

Первый исходит из личности Рамануджана.

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

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

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

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

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

Асимптотическое выражением выражение для p ( n ) определяется

$p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right)$ как $n\to \infty$.

Эта асимптотическая формула была впервые получена Г.Х. Харди и Рамануджаном в 1918 г. и независимо И.В. Успенским в 1920 г. Учитывая $p(1000)$, асимптотическая формула дает примерно $2.4402\times 10^{31}$, что достаточно близко к точному ответу, данному выше (на 1,415 % больше истинного значения).

Харди и Рамануджан получили асимптотическое разложение с этим приближением в качестве первого члена:

$$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),$$

где

$$A_{k}(n)=\sum _{0\leq m<k,\;(m,k)=1}e^{\pi i\left(s(m,k)-2nm/k\right)}.$$

Здесь обозначение $(m,k)=1$ означает, что сумма берется только по значениям $m$ которые относительно просты для $k$. Функция $s(m,k)$ является суммой Дедекинда .

Ошибка после $v$ условия имеют порядок следующего члена, и $v$ можно принять порядка ${\sqrt {n}}$. В качестве примера Харди и Рамануджан показали, что $p(200)$ является ближайшим целым числом к ​​сумме первых $v=5$ условия сериала.

В 1937 году Ганс Радемахер смог улучшить результаты Харди и Рамануджана, предоставив выражение сходящегося ряда для $p(n)$. Это

$$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).$$

Доказательство формулы Радемахера включает в себя круги Форда , последовательности Фарея , модульную симметрию и эта-функцию Дедекинда .

Можно показать, что $k$-й член ряда Радемахера имеет порядок

$$\exp \left({\frac {\pi }{k}}{\sqrt {\frac {2n}{3}}}\right),$$

так что первый член дает асимптотическое приближение Харди – Рамануджана. Пол Эрдеш ( 1942 ) опубликовал элементарное доказательство асимптотической формулы для $p(n)$.

Методы эффективной реализации формулы Харди-Рамануджана-Радемахера на компьютере обсуждаются Йоханссоном (2012) , который показывает, что $p(n)$ можно вычислить во времени $O(n^{1/2+\varepsilon })$ для любого $\varepsilon >0$. Это почти оптимально, поскольку оно соответствует количеству цифр результата. Наибольшее значение статистической суммы, вычисленное точно, равно $p(10^{20})$, который имеет чуть более 11 миллиардов цифр.

Строгая функция разделения

Определение и свойства

Раздел, в котором ни одна часть не встречается более одного раза, называется строгим или называется разделом на отдельные части . Функция q ( n ) дает количество этих строгих разбиений данной суммы n . Например, q (3) = 2, поскольку разбиения 3 и 1+2 являются строгими, а третье разбиение 1+1+1 из 3 имеет повторяющиеся части. Число q ( n ) также равно количеству разделов n , в которых разрешены только нечетные слагаемые.

Примеры значений q ( n ) и связанных разделов

н	д ( п )	Строгие перегородки	Разделы только с нечетными частями
0	1	() пустой раздел	() пустой раздел
1	1	1	1
2	1	2	1+1
3	2	1+2, 3	1+1+1, 3
4	2	1+3, 4	1+1+1+1, 1+3
5	3	2+3, 1+4, 5	1+1+1+1+1, 1+1+3, 5
6	4	1+2+3, 2+4, 1+5, 6	1+1+1+1+1+1, 1+1+1+3, 3+3, 1+5
7	5	1+2+4, 3+4, 2+5, 1+6, 7	1+1+1+1+1+1+1, 1+1+1+1+3, 1+3+3, 1+1+5, 7
8	6	1+3+4, 1+2+5, 3+5, 2+6, 1+7, 8	1+1+1+1+1+1+1+1, 1+1+1+1+1+3, 1+1+3+3, 1+1+1+5, 3+5, 1+7
9	8	2+3+4, 1+3+5, 4+5, 1+2+6, 3+6, 2+7, 1+8, 9	1+1+1+1+1+1+1+1+1, 1+1+1+1+1+1+3, 1+1+1+3+3, 3+3+3, 1+1+1+1+5, 1+3+5, 1+1+7, 9

Генерирующая функция

Производящая функция чисел q ( n ) задается простым бесконечным произведением:

$$\sum _{n=0}^{\infty }q(n)x^{n}=\prod _{k=1}^{\infty }(1+x^{k})=(x;x^{2})_{\infty }^{-1},$$

где обозначение $(a;b)_{\infty }$ представляет символ Поххаммера $(a;b)_{\infty }=\prod _{k=0}^{\infty }(1-ab^{k}).$ Из этой формулы можно легко получить первые несколько членов (последовательность A000009 в OEIS ):

$$\sum _{n=0}^{\infty }q(n)x^{n}=1+1x+1x^{2}+2x^{3}+2x^{4}+3x^{5}+4x^{6}+5x^{7}+6x^{8}+8x^{9}+10x^{10}+\ldots .$$

Этот ряд также можно записать в терминах тэта-функций как

$$\sum _{n=0}^{\infty }q(n)x^{n}=\vartheta _{00}(x)^{1/6}\vartheta _{01}(x)^{-1/3}{\biggl \{}{\frac {1}{16\,x}}{\bigl [}\vartheta _{00}(x)^{4}-\vartheta _{01}(x)^{4}{\bigr ]}{\biggr \}}^{1/24},$$

где

$$\vartheta _{00}(x)=1+2\sum _{n=1}^{\infty }x^{n^{2}}$$

и

$$\vartheta _{01}(x)=1+2\sum _{n=1}^{\infty }(-1)^{n}x^{n^{2}}.$$

Для сравнения, производящая функция обычных номеров разделов p ( n ) имеет это тождество по отношению к тэта-функции:

$$\sum _{n=0}^{\infty }p(n)x^{n}=(x;x)_{\infty }^{-1}=\vartheta _{00}(x)^{-1/6}\vartheta _{01}(x)^{-2/3}{\biggl \{}{\frac {1}{16\,x}}{\bigl [}\vartheta _{00}(x)^{4}-\vartheta _{01}(x)^{4}{\bigr ]}{\biggr \}}^{-1/24}.$$

Идентификаторы строгих номеров разделов

Следующие идентификаторы действительны для продуктов Pochhammer:

$(x;x)_{\infty }^{-1}=(x^{2};x^{2})_{\infty }^{-1}(x;x^{2})_{\infty }^{-1}$

Из этого тождества следует формула:

${\biggl [}\sum _{n=0}^{\infty }p(n)x^{n}{\biggr ]}={\biggl [}\sum _{n=0}^{\infty }p(n)x^{2n}{\biggr ]}{\biggl [}\sum _{n=0}^{\infty }q(n)x^{n}{\biggr ]}$

Следовательно, эти две формулы справедливы для синтеза числовой последовательности p(n):

$p(2n)=\sum _{k=0}^{n}p(n-k)q(2k)$

$p(2n+1)=\sum _{k=0}^{n}p(n-k)q(2k+1)$

Ниже точно выполнены два примера:

$p(8)=\sum _{k=0}^{4}p(4-k)q(2k)=$

$=p(4)q(0)+p(3)q(2)+p(2)q(4)+p(1)q(6)+p(0)q(8)=$

$=5\times 1+3\times 1+2\times 2+1\times 4+1\times 6=22$

$p(9)=\sum _{k=0}^{4}p(4-k)q(2k+1)=$

$=p(4)q(1)+p(3)q(3)+p(2)q(5)+p(1)q(7)+p(0)q(9)=$

$=5\times 1+3\times 2+2\times 3+1\times 5+1\times 8=30$

Ограниченная функция разделов

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

Глейшера

Двумя важными примерами являются разделения, ограниченные только нечетными целыми частями или только четными целыми частями, при этом соответствующие функции разделения часто обозначаются $p_{o}(n)$ и $p_{e}(n)$.

Теорема Эйлера показывает, что количество строгих разбиений равно количеству разбиений только с нечетными частями: для n всех $q(n)=p_{o}(n)$. Это обобщено как теорема Глейшера , которая утверждает, что количество разделов, в которых не более чем d-1 повторений любой части, равно количеству разделов, в которых ни одна часть не делится на d .

Гаусса

Если мы обозначим $p(N,M,n)$ количество разбиений n не более чем на M частей, каждая из которых меньше или равна N , тогда производящая функция $p(N,M,n)$ представляет собой следующий биномиальный коэффициент Гаусса :

$\sum _{n=0}^{\infty }p(N,M,n)q^{n}={N+M \choose M}_{q}={\frac {(1-q^{N+M})(1-q^{N+M-1})\cdots (1-q^{N+1})}{(1-q)(1-q^{2})\cdots (1-q^{M})}}$

Асимптотика

Известны некоторые общие результаты об асимптотических свойствах ограниченных статистических сумм. Если p _A ( n ) — статистическая сумма разбиений, ограниченных только элементами подмножества A натуральных чисел, то:

Если A обладает положительной естественной плотностью α, то $\log p_{A}(n)\sim C{\sqrt {\alpha n}}$, с $C=\pi {\sqrt {\frac {2}{3}}}$

и наоборот, если это асимптотическое свойство справедливо для p _A ( n ), то A имеет естественную плотность α. Этот результат был сформулирован вместе с наброском доказательства Эрдёшем в 1942 году.

Если A — конечное множество, этот анализ неприменим (плотность конечного множества равна нулю). Если A имеет k элементов, наибольший общий делитель которых равен 1, то

$p_{A}(n)=\left(\prod _{a\in A}a^{-1}\right)\cdot {\frac {n^{k-1}}{(k-1)!}}+O(n^{k-2}).$

Внешние ссылки

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