Формула Харди–Рамануджана — асимптотическая (а в уточнённом виде — точная) формула для вычисления функции разбиений p(n) , предложенная в 1918 году английскими математиками Годфри Харольдом Харди и Сринивасой Рамануджаном. Она стала первым крупным достижением аналитической теории чисел в изучении аддитивных функций и положила начало методу кругов (Hardy–Littlewood circle method).
Определение Формула Харди–Рамануджана предоставляет асимптотическое выражение для количества неупорядоченных разбиений натурального числа n , обозначаемого p(n) . В своей исходной форме она имеет вид:
при: n
Позже Харди и Рамануджан получили уточнённую формулу в виде бесконечного ряда:
которая является точной для всех целых n 1.
Исторический контекст Изучение разбиений восходит к Лейбницу и Эйлеру, который в 1748 году установил производящую функцию:
Долгое время не существовало эффективных методов для вычисления p(n) при больших n . В 1914 году Рамануджан прибыл в Кембридж и начал сотрудничество с Харди. В 1916–1917 годах они разработали метод кругов, позволяющий анализировать производящие функции на границе круга сходимости через локальный анализ в окрестностях корней из единицы.
В 1918 году они опубликовали работу «Asymptotic formulae in combinatory analysis», где впервые появилась асимптотическая формула для p(n) , а затем — её уточнённая версия.
Компоненты формулы Для любого целого n 1:
где все компоненты представлены ниже:
Функция разбиений p(n) Функция p(n) — количество представлений n в виде суммы положительных целых чисел без учёта порядка. По определению p(0)=1 .
Примеры:
p(1)=1 p(2)=2 p(3)=3 p(4)=5 p(5)=7
Арифметическая сумма Ak(n)
: Сумма берется по всем вычетам , взаимно простым с , т.е берется только когда их наибольший общий делитель (НОД) равен 1. Количество слагаемых равно функции Эйлера φ(k) . — алгебраическое число, модуль которого ограничен: .
Сумма Дедекинда s(m,k)
Свойства:
При : , где — обратный по модулю .
Аналитическая часть
Величина — модулярная поправка, связанная с эта-функцией Дедекинда:
Аргумент гиперболического синуса: ; Пусть = , тогда: = Производная по возникает из применения формулы Коши и дифференцирования параметрического интеграла.
Вывод формулы
Производящая функция:
Интеграл Коши:
Метод кругов: Окружность разбивается на мажорные дуги около и минорные дуги между ними. Вклад минорных дуг пренебрежимо мал. Вклад мажорной дуги около выражается через модулярное преобразование .
Асимптотика интеграла даёт слагаемое, зависящее от , , и . Суммирование по всем (взаимно простым с ) даёт . Суммирование по всем даёт полную формулу.
Формула Радемахера
В 1937 году Ханс Радемахер упростил формулу, получив абсолютно сходящийся ряд без производной:
Используя , получаем эквивалентность с формулой Харди–Рамануджана.
Свойства и сходимость
Ряд сходится абсолютно для всех . Для вычисления с погрешностью < 0.5 достаточно взять , где . При : , и слагаемое даёт асимптотическую формулу. Формула точна: при достаточном числе слагаемых результат — целое число.
Уточнение приближения с ростом числа слагаемых
Точность формулы Харди–Рамануджана (или эквивалентной ей формулы Радемахера) резко возрастает с увеличением количества слагаемых в сумме. Это демонстрирует следующая таблица для трёх значений .
(число слагаемых) Приближение Фактическое Погрешность (%) 10 1 48 42 14.533% 2 43 2.519% 3 42 0.050% 50 1 217 590 204 226 6.544% 2 205 239 0.496% 3 204 257 0.015% 100 1 199 280 893 190 569 292 4.571% 2 191 032 426 0.243% 3 190 619 341 0.026%
Как видно из таблицы, даже добавление всего лишь второго и третьего слагаемых () приводит к резкому снижению погрешности, подтверждая, что чем больше , тем точнее приближение.
Применения
Комбинаторика: точный подсчёт разбиений. Теория чисел: пример применения метода кругов. Физика: В теории струн описывает спектр состояний. В термодинамике чёрных дыр (Бекенштейн–Хокинг) энтропия пропорциональна .
Формула Харди-Рамануджана в виде кода Python
В 59 строке кода: 'n' - число для разбиения
В 60 строке кода: 't' количество знаков после запятой при значении n = 1 000 000 и t = 10. Вывод программы будет: "1.471684986e+1107", но если увеличить t до 10 000 то вывод будет точным без степеней.import mpmath import math
mpmath.mp.dps = 80
j = mpmath.j pi = mpmath.pi
def u(n): return n - mpmath.mpf(1)/24
def B(k, n): return (pi / k) * mpmath.sqrt(mpmath.mpf(2)/3 * u(n))
def ProizB(k, n): return (pi / (2 * k)) * mpmath.sqrt(2 / (3 * u(n)))
def Proizddn(k, n): Bval = B(k, n) term1 = mpmath.cosh(Bval) * ProizB(k, n) / mpmath.sqrt(u(n)) term2 = mpmath.sinh(Bval) / (2 * (u(n) ** (3/2))) return term1 - term2
def s(m, k): if k == 1: return mpmath.mpf('0') total = mpmath.mpf('0') for r in range(1, k): term1 = mpmath.mpf(r)/k - mpmath.mpf('0.5') mr_mod_k = (m * r) % k term2 = mpmath.mpf(mr_mod_k)/k - mpmath.mpf('0.5') total += term1 * term2 return total
def A(k, n): total = mpmath.mpc('0') for m in range(0, k): if math.gcd(m, k) == 1: exponent = pi * j * s(m, k) - 2 * pi * j * (mpmath.mpf(n) * m / k) total += mpmath.exp(exponent) return total
def p(n): n = mpmath.mpf(n) itog = mpmath.mpc('0') for k in range(1, 5): akn = A(k, n) sqrt_k = mpmath.sqrt(k) deriv = Proizddn(k, n) itog += akn * sqrt_k * deriv
if abs(akn * sqrt_k * deriv) < abs(itog) * 1e-20 and k > 1: break result = itog / (pi * mpmath.sqrt(2)) if abs(result.imag) < abs(result.real) * 1e-10: return result.real return result
result = p(n) print(mpmath.nstr(result, t))
Примечания
Литература Hardy, G. H.; Ramanujan, S. (1918). «Asymptotic formulae in combinatory analysis». Proceedings of the London Mathematical Society. Rademacher, H. (1937). «A convergent series for the partition function p(n)». Proceedings of the National Academy of Sciences. Apostol, T. M. (1990). Modular Functions and Dirichlet Series in Number Theory. Springer. Andrews, G. E. (1998). The Theory of Partitions. Cambridge University Press.
Категория:Аналитическая теория чисел