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

Понятие в теории чисел

В теории чисел естественная плотность , также называемая асимптотической плотностью или арифметической плотностью , является одним из методов измерения того, насколько «велико» подмножество множества натуральных чисел . Она в основном опирается на вероятность встречи членов желаемого подмножества при прочесывании интервала [1, n ] по мере того , как n становится больше.

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

Если целое число случайно выбрано из интервала [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 A}$ ${\displaystyle \mathbb {N} =\{1,2,\ldots \}.}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle A(n)}$ ${\displaystyle A(n)=\{1,2,\ldots ,n\}\cap A,}$ ${\displaystyle a(n)=|A(n)|}$ ${\displaystyle A}$ ${\displaystyle n}$

Определим верхнюю асимптотическую плотность ( также называемую «верхней плотностью») как, где lim sup — верхний предел . ${\displaystyle {\overline {d}}(A)}$ ${\displaystyle A}$ $${\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {a(n)}{n}}}$$

Аналогично, определим нижнюю асимптотическую плотность ( также называемую «нижней плотностью») как где lim inf — нижний предел . Можно сказать, что имеет асимптотическую плотность , если , в этом случае равно этому общему значению. ${\displaystyle {\underline {d}}(A)}$ ${\displaystyle A}$ $${\displaystyle {\underline {d}}(A)=\liminf _{n\rightarrow \infty }{\frac {a(n)}{n}}}$$ ${\displaystyle A}$ ${\displaystyle d(A)}$ ${\displaystyle {\underline {d}}(A)={\overline {d}}(A)}$ ${\displaystyle d(A)}$

Это определение можно переформулировать следующим образом: если этот предел существует. ^[2] $${\displaystyle d(A)=\lim _{n\rightarrow \infty }{\frac {a(n)}{n}}}$$

Эти определения могут быть эквивалентно ^{[ требуется ссылка ]} выражены следующим образом. Дано подмножество , запишите его как возрастающую последовательность, индексированную натуральными числами: Тогда и если предел существует. ${\displaystyle A}$ ${\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 d^{*}(A)}$ ${\displaystyle A\subseteq \mathbb {N} .}$ $${\displaystyle d^{*}(A)=\limsup _{N-M\rightarrow \infty }{\frac {|A\cap \{M,M+1,\ldots ,N\}|}{N-M+1}}.}$$

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

• Для любого конечного множества F положительных целых чисел d ( F ) = 0.
• Если d ( A ) существует для некоторого множества A и A ^c обозначает его дополнительное множество относительно , ​​то d ( A ^c ) = 1 − d ( A ). ${\displaystyle \mathbb {N} }$
  • Следствие: Если конечно (включая случай ), ${\displaystyle F\subset \mathbb {N} }$ ${\displaystyle F=\emptyset }$ ${\displaystyle d(\mathbb {N} \setminus F)=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\}.}$$
• Если — множество всех квадратов, то d ( A ) = 0. ${\displaystyle A=\{n^{2}:n\in \mathbb {N} \}}$
• Если — множество всех четных чисел, то d ( A ) = 0,5. Аналогично для любой арифметической прогрессии получаем ${\displaystyle A=\{2n:n\in \mathbb {N} \}}$ ${\displaystyle A=\{an+b:n\in \mathbb {N} \}}$ ${\displaystyle d(A)={\tfrac {1}{a}}.}$
• Для множества P всех простых чисел из теоремы о простых числах следует , что d ( P ) = 0.
• Множество всех целых чисел, свободных от квадратов, имеет плотность. В более общем смысле, множество всех чисел, свободных от n - ^{й степени} , для любого натурального n имеет плотность, где — дзета-функция Римана . ${\displaystyle {\tfrac {6}{\pi ^{2}}}.}$ ${\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 отличаются на квадрат числа.

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

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

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

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

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

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

• Плотность Дирихле
• Гипотеза Эрдёша об арифметических прогрессиях

Примечания

1. Tenenbaum (1995) стр.261
2. Натансон (2000) стр.256–257
3. Холл, Ричард Р.; Тененбаум, Джеральд (1988). Дивизоры . Кембриджские трактаты по математике. Т. 90. Кембридж: Cambridge University Press . С. 95. ISBN 978-0-521-34056-4. Збл  0653.10001.
4. Deléglise, Marc (1998). «Границы плотности обильных целых чисел». Experimental Mathematics . 7 (2): 137–143. CiteSeerX 10.1.1.36.8272 . doi :10.1080/10586458.1998.10504363. ISSN  1058-6458. MR  1677091. Zbl  0923.11127. 
5. Холл, Ричард Р. (1996), Множества кратных, Cambridge Tracts in Mathematics, т. 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. Збл  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 г. . Получено 2014-11-16 .
• Тененбаум, Жеральд (1995). Введение в аналитическую и вероятностную теорию чисел . Cambridge Studies in Advanced Mathematics. Том 46. Cambridge University Press . Zbl  0831.11001.

В данной статье использованы материалы из Asymptotic density на PlanetMath , которые лицензированы в соответствии с лицензией Creative Commons Attribution/Share-Alike License .