В теории чисел, естественная плотность (также называемая асимптотической плотность или арифметическая плотность ) - это один из методов измерения того, насколько «большим» является подмножество из набора из натуральных чисел. Он в основном полагается на вероятность встретить элементы желаемого подмножества при прочесывании через интервал [1, n] по мере того, как n становится большим.
Интуитивно кажется, что существует больше натуральных чисел, чем полных квадратов, поскольку каждый полный квадрат уже положителен, а кроме того существует множество других положительных целых чисел. Однако набор положительных целых чисел на самом деле не больше, чем набор полных квадратов: оба набора являются бесконечными и счетными и поэтому могут быть помещены в однозначно. одна корреспонденция. Тем не менее, если рассматривать натуральные числа, квадратов становится все меньше. Понятие естественной плотности делает эту интуицию точной для многих, но не всех, подмножеств натуральных значений (см. плотность Шнирельмана, которая аналогична естественной плотности, но определена для всех подмножеств ).
Если целое число случайно выбрано из интервала [1, n], то вероятность того, что оно принадлежит A, является отношением количества элементов A в [1, n] к общему количеству элементы в [1, n]. Если эта вероятность стремится к некоторому пределу, когда n стремится к бесконечности, то этот предел называется асимптотической плотностью A. Это понятие можно понимать как своего рода вероятность выбора числа из множества A. Действительно, асимптотическая плотность (как и некоторые другие типы плотностей) изучается в вероятностной теории чисел.
Содержание
- 1 Определение
- 1.1 Верхняя и нижняя асимптотическая плотность
- 2 Свойства и примеры
- 3 Другие функции плотности
- 4 Примечания
- 5 См. Также
- 6 Ссылки
Определение
Подмножество A положительных целых чисел имеет естественную плотность α, если пропорция элементов A среди всех натуральных чисел от 1 до n сходится к α, когда n стремится к бесконечности.
Более точно, если определить для любого натурального числа n счетную функцию a (n) как количество элементов A, меньшее или равное n, тогда естественная плотность A равенство α в точности означает, что
- a (n) / n → α при n → ∞.
Из определения следует, что если множество A имеет естественную плотность α, то 0 ≤ α ≤ 1.
Верхняя и нижняя асимптотическая плотность
Пусть будет подмножеством множества натуральных чисел Для любого положим и .
Определите верхнюю асимптотическую плотность (также называемую «верхней плотностью») из по
где lim sup - верхний предел. также известен как верхняя плотность
Аналогично, , нижняя асимптотическая плотность (также называемая "нижней плотность ") из , определяется как
где lim inf - нижний предел. Можно сказать, что имеет асимптотическую плотность , если , в этом случае равно этому общему значению.
Это определение можно переформулировать следующим образом:
, если этот предел существует.
Можно доказать, что определения подразумевают, что также выполняется следующее. Если бы можно было записать подмножество как возрастающую последовательность, проиндексированную натуральными числами
, то
и , если ограничение существует.
Несколько более слабым понятием плотности является верхняя банахова плотность; для данного набора , определить при
Свойства и примеры
- Если и существуют, тогда
- Для любого конечного множества F натуральных чисел d (F) = 0.
- Если - это множество всех квадратов, тогда d (A) = 0.
- Если - это набор всех четных чисел, тогда d (A) = 0,5. Точно так же для любой арифметической прогрессии мы получаем
- Для множества P всех простых чисел мы получаем из теоремы о простых числах, что d (P) = 0.
- Набор всех целых чисел без квадратов имеет плотность В общем, множество всех n-степенных чисел для любого натурального n имеет плотность где - это дзета-функция Римана..
- Набор избыточных чисел имеет ненулевую плотность. В 1998 году Марк Делеглиз показал, что плотность множества обильных и совершенных чисел составляет от 0,2474 до 0,2480.
- чисел, двоичное расширение которых содержит нечетное количество цифр, является примером набора, не имеющего асимптотической плотности, поскольку верхняя плотность этого набора равна
- , тогда как его более низкая плотность равна
- Набор чисел, десятичное разложение которого начинается с цифры 1, также не имеет естественной плотности: нижняя плотность равна 1/9, а верхняя плотность равна 5 / 9. (См. закон Бенфорда.)
- . Рассмотрим равнораспределенную последовательность в и определите монотонное семейство наборов:
- Тогда по определению для всех .
- Если S - множество положительной верхней плотности, то теорема Семереди утверждает, что S содержит сколь угодно большие конечные арифметические прогрессии, а теорема Фюрстенберга – Шаркози утверждает, что некоторые два члена S различаются на квадратное число.
Другие функции плотности
Другие функции плотности на подмножествах натуральных чисел могут быть определены аналогично. Например, логарифмическая плотность набора A определяется как предел (если он существует)
Аналогично определяются верхняя и нижняя логарифмические плотности.
Для множества кратных целочисленной последовательности теорема Дэвенпорта – Эрдеша утверждает, что естественная плотность и логарифмическая плотность равны.
Примечания
См. Также
Ссылки
- Натансон, Мелвин Б. (2000). Элементарные методы в теории чисел. Тексты для выпускников по математике. 195 . Спрингер-Верлаг. ISBN 978-0387989129. Zbl 0953.11002.
- Нивен, Иван (1951). «Асимптотическая плотность последовательностей». Бюллетень Американского математического общества. 57(6): 420–434. doi : 10,1090 / s0002-9904-1951-09543-9. MR 0044561. Zbl 0044.03603.
- Steuding, Jörn (2002). «Вероятностная теория чисел» (PDF). Архивировано из оригинального (PDF) 22 декабря 2011 г. Дата обращения 16 ноября 2014 г.
- Тененбаум, Джеральд (1995). Введение в аналитическую и вероятностную теорию чисел. Кембриджские исследования в области высшей математики. 46. Издательство Кембриджского университета. Zbl 0831.11001.
Эта статья включает материал из Asymptotic density на PlanetMath, который находится под лицензией Creative Commons Attribution / Share-Alike License.