Концепция теории чисел
В теории чисел естественная плотность , также называемая асимптотической плотностью или арифметической плотностью , является одним из методов измерения того, насколько «большим» является подмножество набора натуральных чисел . Он полагается главным образом на вероятность встретить членов желаемого подмножества при прочесывании интервала [1, n ] по мере увеличения n .
Интуитивно считается, что положительных целых чисел больше , чем идеальных квадратов , поскольку каждый совершенный квадрат уже положителен, а кроме него существует множество других целых положительных чисел. Однако набор натуральных чисел на самом деле не больше, чем набор идеальных квадратов: оба набора бесконечны и счетны и поэтому могут быть поставлены во взаимно однозначное соответствие . Тем не менее, если пройтись по натуральным числам, квадратов становится все меньше. Понятие естественной плотности делает эту интуицию точной для многих, но не для всех, подмножеств натуральных чисел (см. плотность Шнирельмана , которая похожа на естественную плотность, но определена для всех подмножеств ).![{\displaystyle \mathbb {N} }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Если целое число случайно выбрано из интервала [1, n ] , то вероятность того, что оно принадлежит A , равна отношению числа элементов A в [1, n ] к общему количеству элементов в [1, n] ] . Если эта вероятность стремится к некоторому пределу при стремлении n к бесконечности, то этот предел называется асимптотической плотностью A . Это понятие можно понимать как своего рода вероятность выбора числа из множества A. Действительно, асимптотическая плотность (как и некоторые другие виды плотностей) изучается в вероятностной теории чисел .
Определение
Подмножество A натуральных чисел имеет естественную плотность α, если доля элементов A среди всех натуральных чисел от 1 до n сходится к α при стремлении n к бесконечности.
Более подробно, если для любого натурального числа n определить считающую функцию a ( n ) как количество элементов A , меньших или равных n , то естественная плотность A , равная α, в точности означает, что [1]
а ( п )/ п → α как п → ∞ .
Из определения следует, что если множество A имеет естественную плотность α , то 0 ⩽ α ⩽ 1 .
Верхняя и нижняя асимптотическая плотность
Пусть будет подмножеством множества натуральных чисел. Для любого определите пересечение и пусть будет число элементов меньше или равно .![{\displaystyle А}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \mathbb {N} =\{1,2,\ldots \}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle n\in \mathbb {N}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle A (n)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle A (n) = \ {1,2, \ ldots, n \} \ cap A,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle a (n) = | A (n) |}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle А}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle п}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Определите верхнюю асимптотическую плотность ( также называемую «верхней плотностью») по формуле,
где lim sup — верхний предел .![{\displaystyle {\overline {d}}(A)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle А}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\overline {d}}(A)=\limsup _ {n\rightarrow \infty }{\frac {a(n)}{n}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Аналогичным образом определите нижнюю асимптотическую плотность ( также называемую «нижней плотностью») по формуле,
где lim inf — нижний предел . Можно сказать, что имеет асимптотическую плотность, если , и в этом случае оно равно этому общему значению.![{\displaystyle {\underline {d}}(A)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle А}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\underline {d}}(A)=\liminf _{n\rightarrow \infty }{\frac {a(n)}{n}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle А}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle d (A)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\underline {d}}(A)={\overline {d}}(A)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle d (A)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Это определение можно переформулировать следующим образом:
если этот предел существует. [2]![{\displaystyle d(A)=\lim _{n\rightarrow \infty }{\frac {a(n)}{n}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Эти определения эквивалентно могут быть выражены следующим образом. Учитывая подмножество , запишите его как возрастающую последовательность , индексированную натуральными числами:
Тогда
и
если предел существует.![{\displaystyle А}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \mathbb {N} }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A=\{a_{1}<a_{2}<\ldots \}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\underline {d}}(A)=\liminf _{n\rightarrow \infty }{\frac {n}{a_{n}}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {n}{a_{n}}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle d(A)=\lim _{n\rightarrow \infty }{\frac {n}{a_{n}}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Несколько более слабое понятие плотности — это верхняя банахова плотность множества. Она определяется как![{\displaystyle d^{*}(A)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A\subseteq \mathbb {N}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle d^{*}(A)=\limsup _{NM\rightarrow \infty }{\frac {|A\cap \{M,M+1,\ldots,N\}|}{NM +1}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Свойства и примеры
- Если d ( A ) существует для некоторого множества A и Ac обозначает его дополнение относительно , то d ( Ac ) = 1 - d ( A ).
![{\displaystyle \mathbb {N} }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Следствие: Если конечно (включая случай ),
![{\displaystyle F\subset \mathbb {N} }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle F=\emptyset }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle d(\mathbb {N} \setminus F)=1.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Если и существуют, то
![{\ displaystyle d (A), d (B),}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle d (A \ чашка B)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle \ max \ {d (A), d (B) \} \ leq d (A \ чашка B) \ leq \ min \ {d (A) + d (B), 1 \}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Если – множество всех квадратов, то d ( A ) = 0.
![{\displaystyle A=\{n^{2}:n\in \mathbb {N} \}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Если это набор всех четных чисел, то d ( A ) = 0,5. Аналогично для любой арифметической прогрессии получаем
![{\displaystyle A=\{2n:n\in \mathbb {N} \}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A=\{an+b:n\in \mathbb {N} \}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle d(A)={\tfrac {1}{a}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Набор всех целых чисел без квадратов имеет плотность. В более общем смысле, набор всех чисел без квадратов n-й степени для любого натурального n имеет плотность где – дзета-функция Римана .
![{\displaystyle {\tfrac {6}{\pi ^{2}}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\tfrac {1}{\zeta (n)}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \дзета (п)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Множество обильных чисел имеет ненулевую плотность. [3] Марк Делеглиз показал в 1998 году, что плотность множества обильных чисел находится между 0,2474 и 0,2480. [4]
![{\displaystyle A=\bigcup _{n=0}^{\infty }\left\{2^{2n},\ldots,2^{2n+1}-1\right\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- чисел, двоичное представление которых содержит нечетное число цифр, является примером множества, не имеющего асимптотической плотности, поскольку верхняя плотность этого множества равна
![{\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)}}={\ трещина {2}{3}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- тогда как его меньшая плотность
![{\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)}}={\ фракт {1}{3}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Набор чисел, десятичное представление которых начинается с цифры 1, также не имеет естественной плотности: нижняя плотность равна 1/9, а верхняя плотность равна 5/9. [1] (См. закон Бенфорда .)
- Рассмотрим равнораспределенную последовательность и определим монотонное семейство множеств:
![{\displaystyle \{\alpha _{n}\}_{n\in \mathbb {N} }}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle [0,1]}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \{A_{x}\}_{x\in [0,1]}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A_{x}:=\{n\in \mathbb {N}:\alpha _{n}<x\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Тогда по определению для всех .
![{\displaystyle d(A_{x})=x}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle х}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Другие функции плотности
Другие функции плотности на подмножествах натуральных чисел могут быть определены аналогично. Например, логарифмическая плотность множества A определяется как предел (если он существует)
![{\displaystyle \mathbf {\delta } (A)=\lim _{x\rightarrow \infty }{\frac {1}{\log x}}\sum _{n\in A,n\leq x}{ \frac {1}{n}}\ .}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Аналогично определяются верхняя и нижняя логарифмические плотности.
Для множества кратных целочисленной последовательности теорема Давенпорта – Эрдёша утверждает, что естественная плотность, если она существует, равна логарифмической плотности. [5]
Смотрите также
Примечания
- ^ Аб Тененбаум (1995) стр.261
- ^ Натансон (2000), стр. 256–257.
- ^ Холл, Ричард Р.; Тененбаум, Джеральд (1988). Делители . Кембриджские трактаты по математике. Том. 90. Кембридж: Издательство Кембриджского университета . п. 95. ИСБН 978-0-521-34056-4. Збл 0653.10001.
- ^ Делеглиз, Марк (1998). «Границы плотности обильных целых чисел». Экспериментальная математика . 7 (2): 137–143. CiteSeerX 10.1.1.36.8272 . дои : 10.1080/10586458.1998.10504363. ISSN 1058-6458. МР 1677091. Збл 0923.11127.
- ^ Холл, Ричард Р. (1996), Наборы кратных, Cambridge Tracts in Mathematics, vol. 118, Издательство Кембриджского университета, Кембридж, Теорема 0.2, с. 5, номер домена : 10.1017/CBO9780511566011, ISBN 978-0-521-40424-2, МР 1414678
Рекомендации
- Натансон, Мелвин Б. (2000). Элементарные методы теории чисел . Тексты для аспирантов по математике. Том. 195. Шпрингер-Верлаг . ISBN 978-0387989129. Збл 0953.11002.
- Нивен, Иван (1951). «Асимптотическая плотность последовательностей». Бюллетень Американского математического общества . 57 (6): 420–434. дои : 10.1090/s0002-9904-1951-09543-9 . МР 0044561. Збл 0044.03603.
- Стейдинг, Йорн (2002). «Вероятностная теория чисел» (PDF) . Архивировано из оригинала (PDF) 22 декабря 2011 года . Проверено 16 ноября 2014 г.
- Тененбаум, Джеральд (1995). Введение в аналитическую и вероятностную теорию чисел . Кембриджские исследования по высшей математике. Том. 46. Издательство Кембриджского университета . Збл 0831.11001.
Эта статья включает в себя материал из Asymptotic Density на сайте PlanetMath , который доступен под лицензией Creative Commons Attribution/Share-Alike License .