Естественная плотность - Natural density

В теория чисел, естественная плотность (также называемый асимптотическая плотность или же арифметическая плотность) - один из методов измерения "большого" размера подмножество из набор из натуральные числа является. Он полагается главным образом на вероятность встречи с членами желаемого подмножества при прочесывании интервал [1, п] в качестве п становится большим.

Интуитивно кажется, что есть еще положительные целые числа чем идеальные квадраты, поскольку каждый полный квадрат уже положителен, а кроме того существует множество других положительных целых чисел. Однако набор положительных целых чисел на самом деле не больше, чем набор полных квадратов: оба набора равны бесконечный и счетный и поэтому может быть вставлен индивидуальная переписка. Тем не менее, если рассматривать натуральные числа, квадратов становится все меньше. Понятие естественной плотности делает эту интуицию точной для многих, но не для всех, подмножеств естественных (см. Плотность Шнирельмана, которая аналогична естественной плотности, но определена для всех подмножеств ${\displaystyle \mathbb {N} }$).

Если целое число случайно выбрано из интервала [1,п], то вероятность того, что он принадлежит А это отношение количества элементов А в 1,п] к общему количеству элементов в [1,п]. Если эта вероятность стремится к некоторой предел в качестве п стремится к бесконечности, то этот предел называется асимптотической плотностью А. Это понятие можно понимать как своего рода вероятность выбора числа из множества А. Действительно, асимптотическая плотность (как и некоторые другие типы плотностей) изучается в вероятностная теория чисел.

Определение

Подмножество А натуральных чисел имеет естественную плотность α если доля элементов А среди всего натуральные числа от 1 до п сходится к α в качестве п стремится к бесконечности.

Более точно, если определить для любого натурального числа п подсчет функция а(п) как количество элементов А меньше или равно п, то естественная плотность A, равная α, в точности означает, что^[1]

а(п) / п → α при п → ∞.

Из определения следует, что если множество А имеет естественную плотность α тогда 0 ≤ α ≤ 1.

Верхняя и нижняя асимптотическая плотность

Позволять ${\displaystyle A}$ быть подмножеством множества натуральных чисел ${\displaystyle \mathbb {N} =\{1,2,\ldots \}.}$ Для любого ${\displaystyle n\in \mathbb {N} }$ положить ${\displaystyle A(n)=\{1,2,\ldots ,n\}\cap A.}$ и ${\displaystyle a(n)=|A(n)|}$.

Определить верхняя асимптотическая плотность (также называется «верхняя плотность») ${\displaystyle {\overline {d}}(A)}$ из ${\displaystyle A}$ к

${\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {a(n)}{n}}}$

где lim sup - это предел высшего. ${\displaystyle {\overline {d}}(A)}$ также известен как верхняя плотность ${\displaystyle A.}$

По аналогии, ${\displaystyle {\underline {d}}(A)}$, то нижняя асимптотическая плотность (также называемая «более низкая плотность») ${\displaystyle A}$, определяется

${\displaystyle {\underline {d}}(A)=\liminf _{n\rightarrow \infty }{\frac {a(n)}{n}}}$

где lim inf - это ограничивать низший. Можно сказать ${\displaystyle A}$ имеет асимптотическую плотность ${\displaystyle d(A)}$ если ${\displaystyle {\underline {d}}(A)={\overline {d}}(A)}$, в таком случае ${\displaystyle d(A)}$ равно этому общему значению.

Это определение можно переформулировать следующим образом:

${\displaystyle d(A)=\lim _{n\rightarrow \infty }{\frac {a(n)}{n}}}$

если этот предел существует.^[2]

Можно доказать, что из определений следует, что выполняется также следующее. Если бы можно было написать подмножество ${\displaystyle \mathbb {N} }$ как возрастающая последовательность, индексированная натуральными числами

${\displaystyle A=\{a_{1}<a_{2}<\ldots \}}$

тогда

${\displaystyle {\underline {d}}(A)=\liminf _{n\rightarrow \infty }{\frac {n}{a_{n}}},}$

${\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {n}{a_{n}}}}$

и${\displaystyle d(A)=\lim _{n\rightarrow \infty }{\frac {n}{a_{n}}}}$если предел существует.

Несколько более слабое понятие плотности - это верхняя банахова плотность; учитывая набор ${\displaystyle A\subseteq \mathbb {N} }$, определять ${\displaystyle d^{*}(A)}$ в качестве

${\displaystyle d^{*}(A)=\limsup _{N-M\rightarrow \infty }{\frac {|A\cap \{M,M+1,\ldots ,N\}|}{N-M+1}}}$

Свойства и примеры

• Если d(А) существует для некоторого множества А, и А^c обозначает его набор дополнений относительно ${\displaystyle \mathbb {N} }$ тогда d(А^c) = 1 − d(А).
  • Следствие: ${\displaystyle d(\mathbb {N} )=1.}$

• Если ${\displaystyle d(A),d(B),}$ и ${\displaystyle d(A\cup B)}$ существовать, тогда

${\displaystyle \max\{d(A),d(B)\}\leq d(A\cup B)\leq \min\{d(A)+d(B),1\}.}$

• Для любого конечный набор F натуральных чисел, d(F) = 0.

• Если ${\displaystyle A=\{n^{2}:n\in \mathbb {N} \}}$ - это множество всех квадратов, тогда d(А) = 0.

• Если ${\displaystyle A=\{2n:n\in \mathbb {N} \}}$ множество всех четных чисел, то d(А) = 0,5. Аналогично для любой арифметической прогрессии ${\displaystyle A=\{an+b:n\in \mathbb {N} \}}$ мы получили ${\displaystyle d(A)={\tfrac {1}{a}}.}$

• Для набора п из всех простые числа мы получаем от теорема о простых числах который d(п) = 0.

• Набор всех целые числа без квадратов имеет плотность ${\displaystyle {\tfrac {6}{\pi ^{2}}}.}$ В общем, набор всех п^th-беспроводные номера для любых натуральных п имеет плотность ${\displaystyle {\tfrac {1}{\zeta (n)}},}$ куда ${\displaystyle \zeta (n)}$ это Дзета-функция Римана.

• Набор обильные числа имеет ненулевую плотность.^[3] В 1998 году Марк Делеглиз показал, что плотность множества полных и совершенных чисел находится в пределах от 0,2474 до 0,2480.^[4]

• Набор

${\displaystyle A=\bigcup _{n=0}^{\infty }\left\{2^{2n},\ldots ,2^{2n+1}-1\right\}}$

чисел, двоичное расширение которых содержит нечетное количество цифр, является примером набора, который не имеет асимптотической плотности, так как верхняя плотность этого набора равна

${\displaystyle {\overline {d}}(A)=\lim _{m\to \infty }{\frac {1+2^{2}+\cdots +2^{2m}}{2^{2m+1}-1}}=\lim _{m\to \infty }{\frac {2^{2m+2}-1}{3(2^{2m+1}-1)}}={\frac {2}{3}},}$

тогда как его более низкая плотность

${\displaystyle {\underline {d}}(A)=\lim _{m\to \infty }{\frac {1+2^{2}+\cdots +2^{2m}}{2^{2m+2}-1}}=\lim _{m\to \infty }{\frac {2^{2m+2}-1}{3(2^{2m+2}-1)}}={\frac {1}{3}}.}$

• Набор чисел, чьи десятичное разложение начинается с цифры 1, аналогично не имеет естественной плотности: нижняя плотность составляет 1/9, а верхняя плотность - 5/9.^[1] (Видеть Закон Бенфорда.)

• Рассмотрим равнораспределенная последовательность ${\displaystyle \{\alpha _{n}\}_{n\in \mathbb {N} }}$ в ${\displaystyle [0,1]}$ и определим монотонную семью ${\displaystyle \{A_{x}\}_{x\in [0,1]}}$ комплектов:

${\displaystyle A_{x}:=\{n\in \mathbb {N} :\alpha _{n}<x\}.}$

Тогда по определению ${\displaystyle d(A_{x})=x}$ для всех ${\displaystyle x}$.

• Если S - множество положительной верхней плотности, то Теорема Семереди утверждает, что S содержит сколь угодно большие конечные арифметические прогрессии, а Теорема Фюрстенберга – Шаркози заявляет, что около двух членов S различаются квадратным числом.

Другие функции плотности

Аналогично могут быть определены другие функции плотности на подмножествах натуральных чисел. Например, логарифмическая плотность набора А определяется как предел (если он существует)

${\displaystyle \mathbf {\delta } (A)=\lim _{x\rightarrow \infty }{\frac {1}{\log x}}\sum _{n\in A,n\leq x}{\frac {1}{n}}\ .}$

Аналогично определяются верхняя и нижняя логарифмические плотности.

Для набора кратных целочисленной последовательности Теорема Давенпорта – Эрдеша утверждает, что естественная плотность и логарифмическая плотность равны.^[5]

Примечания

1. Тененбаум (1995) с.261
2. Натансон (2000), стр.256–257
3. Холл, Ричард Р .; Тененбаум, Жеральд (1988). Делители. Кембриджские трактаты по математике. 90. Кембридж: Издательство Кембриджского университета. п. 95. ISBN  978-0-521-34056-4. Zbl  0653.10001.
4. Делеглиз, Марк (1998). «Границы плотности обильных целых чисел». Экспериментальная математика. 7 (2): 137–143. CiteSeerX  10.1.1.36.8272. Дои:10.1080/10586458.1998.10504363. ISSN  1058-6458. МИСТЕР  1677091. Zbl  0923.11127.
5. Холл, Ричард Р. (1996), Наборы кратных, Кембриджские трактаты по математике, 118, Cambridge University Press, Кембридж, теорема 0.2, стр. 5, Дои: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. Дои:10.1090 / s0002-9904-1951-09543-9. МИСТЕР  0044561. Zbl  0044.03603.
• Штойдинг, Йорн (2002). «Вероятностная теория чисел» (PDF). Архивировано из оригинал (PDF) 22 декабря 2011 г.. Получено 2014-11-16.
• Тененбаум, Джеральд (1995). Введение в аналитическую и вероятностную теорию чисел. Кембриджские исследования в области высшей математики. 46. Издательство Кембриджского университета. Zbl  0831.11001.

В этой статье используется материал из раздела Асимптотическая плотность PlanetMath, который находится под лицензией Лицензия Creative Commons Attribution / Share-Alike.