В теории чисел , естественная плотность (также называется асимптотической плотностью или арифметической плотностью ) является одним из способов , чтобы определить , как «большое» а подмножество из множества из натуральных чисел есть. Он зависит главным образом от вероятности встречи с членами желаемого подмножества при прочесывании через интервал [1, n ] по мере увеличения n .
Интуитивно считается, что положительных целых чисел больше, чем полных квадратов , поскольку каждый полный квадрат уже положителен, а кроме того существует множество других положительных целых чисел. Однако набор положительных целых чисел на самом деле не больше, чем набор полных квадратов: оба набора бесконечны и счетны, поэтому их можно поставить во взаимно однозначное соответствие . Тем не менее, если рассматривать натуральные числа, квадратов становится все меньше. Понятие естественной плотности делает эту интуицию точной для многих, но не всех, подмножеств натуральных величин (см. Плотность Шнирельмана , которая похожа на естественную плотность, но определена для всех подмножеств).
Если целое число случайно выбрано из интервала [1, n ], то вероятность того, что оно принадлежит A - это отношение количества элементов A в [1, n ] к общему количеству элементов в [1, n] ]. Если эта вероятность стремится к некоторому пределу , как п стремится к бесконечности, то этот предел называется асимптотической плотностью A . Это понятие можно понимать как своего рода вероятность выбора номера из множества A . Действительно, асимптотическая плотность (как и некоторые другие типы плотностей) изучается в вероятностной теории чисел .
Определение
Подмножество A натуральных чисел имеет естественную плотность α, если доля элементов A среди всех натуральных чисел от 1 до n сходится к α, когда n стремится к бесконечности.
Более явно, если для любого натурального числа n определить счетную функцию a ( n ) как количество элементов A, меньшее или равное n , то естественная плотность A, равная α, в точности означает, что [1]
- a ( n ) / n → α при n → ∞.
Из определения следует, что если множество A имеет естественную плотность α, то 0 ≤ α ≤ 1.
Верхняя и нижняя асимптотическая плотность
Позволять быть подмножеством множества натуральных чисел Для любой ставить а также .
Определите верхнюю асимптотическую плотность (также называемую «верхней плотностью»). из от
где lim sup - верхний предел . также известен как верхняя плотность
По аналогии, , нижняя асимптотическая плотность (также называемая "нижней плотностью"), определяется
где lim inf - нижний предел . Можно сказать имеет асимптотическую плотность если , в таком случае равно этому общему значению.
Это определение можно переформулировать следующим образом:
если этот предел существует. [2]
Можно доказать, что из определений следует, что выполняется также следующее. Если бы можно было написать подмножество как возрастающая последовательность, индексированная натуральными числами
тогда
а также если предел существует.
Несколько более слабое понятие плотности - это верхняя банахова плотность ; учитывая набор, определять в виде
Свойства и примеры
- Если d ( A ) существует для некоторого множества A , а A c обозначает его дополнительное множество по отношению ктогда d ( A c ) = 1 - d ( A ).
- Следствие:
- Если а также существовать, тогда
- Для любого конечного множества F натуральных чисел d ( F ) = 0.
- Если - множество всех квадратов, то d ( A ) = 0.
- Если - множество всех четных чисел, то d ( A ) = 0,5. Аналогично для любой арифметической прогрессии мы получили
- Для множества P всех простых чисел из теоремы о простых числах получаем, что d ( P ) = 0.
- Множество всех целых чисел без квадратов имеет плотностьВ более общем смысле, множество всех n- х- степенных чисел для любого натурального n имеет плотность где - дзета-функция Римана .
- Множество обильных чисел имеет ненулевую плотность. [3] Марк Делеглиз показал в 1998 году, что плотность множества обильных и совершенных чисел составляет от 0,2474 до 0,2480. [4]
- Набор
- чисел, двоичное расширение которых содержит нечетное количество цифр, является примером набора, который не имеет асимптотической плотности, так как верхняя плотность этого набора равна
- тогда как его более низкая плотность
- Набор чисел, десятичное расширение которого начинается с цифры 1, также не имеет естественной плотности: нижняя плотность равна 1/9, а верхняя плотность - 5/9. [1] (См . Закон Бенфорда .)
- Рассмотрим равнораспределенную последовательность в и определим монотонную семью комплектов:
- Тогда по определению для всех .
- Если S - множество положительной верхней плотности, то теорема Семереди утверждает, что S содержит сколь угодно большие конечные арифметические прогрессии , а теорема Фюрстенберга – Шаркози утверждает, что некоторые два члена S отличаются на квадратное число.
Другие функции плотности
Другие функции плотности на подмножествах натуральных чисел могут быть определены аналогично. Например, логарифмическая плотность множества A определяется как предел (если он существует)
Аналогично определяются верхняя и нижняя логарифмические плотности.
Для множества кратных целочисленной последовательности теорема Дэвенпорта – Эрдеша утверждает, что естественная плотность и логарифмическая плотность равны. [5]
Заметки
- ^ a b Тененбаум (1995) стр.261
- ^ Натансон (2000) pp.256-257
- ^ Холл, Ричард Р .; Тененбаум, Джеральд (1988). Делители . Кембриджские трактаты по математике. 90 . Кембридж: Издательство Кембриджского университета . п. 95. ISBN 978-0-521-34056-4. Zbl 0653.10001 .
- ^ Делеглиз, Марк (1998). «Границы плотности обильных целых чисел» . Экспериментальная математика . 7 (2): 137–143. CiteSeerX 10.1.1.36.8272 . DOI : 10.1080 / 10586458.1998.10504363 . ISSN 1058-6458 . Руководство по ремонту 1677091 . Zbl 0923.11127 .
- ^ Холл, Ричард Р. (1996), Множества кратных чисел, Кембриджские трактаты по математике, 118 , Cambridge University Press, Кембридж, теорема 0.2, стр. 5, DOI : 10.1017 / CBO9780511566011 , ISBN 978-0-521-40424-2, Руководство по ремонту 1414678
Смотрите также
- Плотность Дирихле
Рекомендации
- Натансон, Мелвин Б. (2000). Элементарные методы теории чисел . Тексты для выпускников по математике. 195 . Springer-Verlag . ISBN 978-0387989129. Zbl 0953.11002 .
- Нивен, Иван (1951). «Асимптотическая плотность последовательностей» . Бюллетень Американского математического общества . 57 (6): 420–434. DOI : 10.1090 / s0002-9904-1951-09543-9 . Руководство по ремонту 0044561 . Zbl 0044.03603 .
- Штойдинг, Йорн (2002). «Вероятностная теория чисел» (PDF) . Архивировано из оригинального (PDF) 22 декабря 2011 года . Проверено 16 ноября 2014 .
- Тененбаум, Джеральд (1995). Введение в аналитическую и вероятностную теорию чисел . Кембриджские исследования в области высшей математики. 46 . Издательство Кембриджского университета . Zbl 0831.11001 .
Эта статья включает материал из Asymptotic density на PlanetMath , который находится под лицензией Creative Commons Attribution / Share-Alike License .