Мультипликативное разделение - Multiplicative partition

В теории чисел , в мультипликативной раздела или неупорядоченного разложение целого числа п является способом записи п как произведение чисел больше 1, рассматривая два продукта , как эквивалентные , если они отличаются только в упорядочении факторов. Само число n считается одним из таких продуктов. Мультипликативные разбиения тесно связаны с изучением многораздельных разбиений , обсужденных в Andrews (1976) , которые представляют собой аддитивные разбиения конечных последовательностей натуральных чисел с поточечным сложением . Хотя изучение мультипликативных разбиений продолжается по крайней мере с 1923 года, название «мультипликативное разбиение», по-видимому, было введено Хьюзом и Шаллитом (1983) . Латинское название «factorisatio numerorum» использовалось ранее. MathWorld использует термин неупорядоченная факторизация .

Примеры

• Число 20 имеет четыре мультипликативных раздела: 2 × 2 × 5, 2 × 10, 4 × 5 и 20.
• 3 × 3 × 3 × 3, 3 × 3 × 9, 3 × 27, 9 × 9 и 81 - пять мультипликативных разбиений 81 = 3 ⁴ . Поскольку это четвертая степень простого числа , 81 имеет такое же количество (пять) мультипликативных разбиений, что и 4 аддитивных разбиения .
• Число 30 имеет пять мультипликативных разделов: 2 × 3 × 5 = 2 × 15 = 6 × 5 = 3 × 10 = 30.
• В общем, количество мультипликативных разбиений бесквадратного числа с i простыми множителями является i-м числом Белла , B _i .

Заявление

Хьюз и Шаллит (1983) описывают применение мультипликативных разбиений при классификации целых чисел с заданным числом делителей. Например, целые числа с ровно 12 делителями принимают вид p ¹¹ , p × q ⁵ , p ² × q ³ и p × q × r ² , где p , q и r - различные простые числа ; эти формы соответствуют мультипликативным разбиениям 12, 2 × 6, 3 × 4 и 2 × 2 × 3 соответственно. В более общем смысле, для каждого мультипликативного раздела

${\ displaystyle k = \ prod t_ {i}}$

целого числа k соответствует класс целых чисел, имеющих ровно k делителей, вида

${\ displaystyle \ prod p_ {i} ^ {t_ {i} -1},}$

где каждое p _i - отдельное простое число. Это соответствие следует из мультипликативного свойства функции делителей .

Границы количества разделов

Оппенгейм (1926) приписывает Мак-Магону (1923) задачу подсчета числа мультипликативных разбиений n ; эта проблема с тех пор изучалась другими под латинским названием factorisatio numerorum . Если число мультипликативных разделов п является _п , McMahon и Оппенхайм заметили , что ее ряды Дирихль Производящей функция F ( s ) имеет представление о продукте Ошибка harvtxt: нет цели: CITEREFMcMahon1923 ( справка )

${\ displaystyle f (s) = \ sum _ {n = 1} ^ {\ infty} {\ frac {a_ {n}} {n ^ {s}}} = \ prod _ {k = 2} ^ {\ infty} {\ frac {1} {1-k ^ {- s}}}.}$

Последовательность чисел a _n начинается

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, ... (последовательность A001055 в OEIS ).

Оппенхайм также утверждал , верхняя граница в _п , вида

${\ displaystyle a_ {n} \ leq n \ left (\ exp {\ frac {\ log n \ log \ log \ log n} {\ log \ log n}} \ right) ^ {- 2 + o (1) },}$

но, как показали Canfield, Erdős & Pomerance (1983) , эта оценка ошибочна, а истинная оценка

${\ displaystyle a_ {n} \ leq n \ left (\ exp {\ frac {\ log n \ log \ log \ log n} {\ log \ log n}} \ right) ^ {- 1 + o (1) }.}$

Обе эти оценки не далеки от линейности по n : они имеют вид n ^{1 - o (1)} . Однако типичное значение a _n намного меньше: среднее значение a _n , усредненное по интервалу x  ≤  n  ≤  x + N , равно

${\ displaystyle {\ bar {a}} = \ exp \ left ({\ frac {4 {\ sqrt {\ log N}}} {{\ sqrt {2e}} \ log \ log N}} {\ bigl ( } 1 + o (1) {\ bigr)} \ right),}$

граница, имеющая форму n ^{o (1)} ( Luca, Mukhopadhyay & Srinivas 2008 ).

Дополнительные результаты

Canfield, Erds & Pomerance (1983) наблюдают, а Luca, Mukhopadhyay & Srinivas (2008) доказывают, что большинство чисел не может возникать как число a _n мультипликативных разбиений некоторого n : количество значений меньше N, возникающих таким образом равно НЕТ ^{(журнал журнал журнал  N  / журнал журнал  N )} . Кроме того, Лука, Mukhopadhyay & Шринивас (2008) показывают , что большинство значений п не кратны в _п : число значений п ≤ N такое , что через _п делит п является O ( N  / войти ^{1 + о (1)}  Н ) .

Смотрите также

• раздел (теория чисел)
• делитель

Рекомендации

• Эндрюс, Г. (1976), Теория разделов , Эддисон-Уэсли, глава 12.
• Кэнфилд, ER; Эрдеш, Пол ; Померанс, Карл (1983), «О проблеме Оппенгейма относительно« factorisatio numerorum » », Journal of Number Theory , 17 (1): 1–28, doi : 10.1016 / 0022-314X (83) 90002-1.
• Хьюз, Джон Ф .; Shallit, Джеффри (1983), "О числе мультипликативным разделов", American Mathematical Monthly , 90 (7): 468-471, DOI : 10,2307 / 2975729 , JSTOR  2975729.
• Knopfmacher, A .; Мэйс, М. (2006), «Упорядоченные и неупорядоченные факторизации целых чисел», Mathematica Journal , 10 : 72–89. Цитируется MathWorld .
• Лука, Флориан; Мухопадхьяй, Анирбан; Шринивас, Котяда (2008), О функции «factorisatio numerorum» Оппенгейма , arXiv : 0807.0986 , Bibcode : 2008arXiv0807.0986L.
• MacMahon, PA (1923), "Ряды Дирихле и теория разбиений" , Труды Лондонского математического общества , 22 : 404-411, DOI : 10.1112 / ПНИЛИ / s2-22.1.404.
• Оппенгейм, A. (1926), "Об арифметической функции" , журнал Лондонского математического общества , 1 (4): 205-211, DOI : 10,1112 / jlms / s1-1.4.205 , архивируются с оригинала на 2013- 04-15.

дальнейшее чтение

• Knopfmacher, A .; Mays, ME (2005), "Обзор факторизации функций подсчета" (PDF) , Международный журнал по теории чисел , 1 (4): 563-581, DOI : 10,1142 / S1793042105000315

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

• Вайсштейн, Эрик В. «Неупорядоченная факторизация» . MathWorld .