Функция распределения (теория чисел)

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

В теории чисел , то функция распределения р ( п ) представляет собой число возможных перегородок из неотрицательного целого числа п . Например, 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]

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

По состоянию на февраль 2020 ^[update]года самым большим известным простым числом среди значений p ( n ) является p (1289844341) с 40000 десятичных цифр. ^[2]

Функция генерации [ править ]

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

Производящая функция для р ( п ) дается формулой ^[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}$

В более общем смысле, производящую функцию для разбиения на числа, выбранные из набора положительных целых чисел, можно найти, взяв только те члены в первом продукте, для которых . Этот результат принадлежит Леонарду Эйлеру . ^[4] Формулировка производящей функции Эйлера является частным случаем символа -Почхаммера и аналогична формулировке произведения многих модульных форм , в частности, эта-функции Дедекинда .${\displaystyle n}$${\displaystyle A}$${\displaystyle k\in A}$ q {\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}}}$.

Другое рекуррентное соотношение для может быть выражено в терминах суммы делителей функции σ : ^[6]${\displaystyle p(n)}$

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

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

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

Конгруэнции [ править ]

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

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

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

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

Формулы аппроксимации [ править ]

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

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

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

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

Харди и Рамануджан получили асимптотическое разложение с этим приближением в качестве первого члена: ^[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)}$

The error after ${\displaystyle v}$ terms is of the order of the next term, and ${\displaystyle v}$ may be taken to be of the order of ${\displaystyle {\sqrt {n}}}$. As an example, Hardy and Ramanujan showed that ${\displaystyle p(200)}$ is the nearest integer to the sum of the first ${\displaystyle v=5}$ terms of the series.^[14]

In 1937, Hans Rademacher was able to improve on Hardy and Ramanujan's results by providing a convergent series expression for ${\displaystyle p(n)}$. It is^[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).}$

The proof of Rademacher's formula involves Ford circles, Farey sequences, modular symmetry and the Dedekind eta function.

It may be shown that the ${\displaystyle k}$th term of Rademacher's series is of the order

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

so that the first term gives the Hardy–Ramanujan asymptotic approximation. Paul Erdős (1942) published an elementary proof of the asymptotic formula for ${\displaystyle p(n)}$.^[17][18]

Techniques for implementing the Hardy–Ramanujan–Rademacher formula efficiently on a computer are discussed by Johansson (2012), who shows that ${\displaystyle p(n)}$ can be computed in time ${\displaystyle O(n^{1/2+\varepsilon })}$ for any ${\displaystyle \varepsilon >0}$. This is near-optimal in that it matches the number of digits of the result.^[19] The largest value of the partition function computed exactly is ${\displaystyle p(10^{20})}$, which has slightly more than 11 billion digits.^[20]

References[edit]

External links[edit]

• First 4096 values of the partition function