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

Концепция теории чисел

В теории чисел естественная плотность , также называемая асимптотической плотностью или арифметической плотностью , является одним из методов измерения того, насколько «велико» подмножество набора натуральных чисел . Он полагается главным образом на вероятность встретить членов желаемого подмножества при прочесывании интервала [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}$

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

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

верхний предел

Аналогичным образом определите нижнюю асимптотическую плотность ( также называемую «нижней плотностью») по формуле ${\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)}$

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

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

^[2]

Эти определения могут быть эквивалентно выражены следующим образом. Учитывая подмножество , запишите его как возрастающую последовательность, индексированную натуральными числами: ${\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 и Ac обозначает его дополнение относительно , ​​то d ⁽ Ac ) = 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. Тененбаум (1995) стр.261
2. Натансон (2000), стр. 256–257.
3. Холл, Ричард Р.; Тененбаум, Джеральд (1988). Делители . Кембриджские трактаты по математике. Том. 90. Кембридж: Издательство Кембриджского университета . п. 95. ИСБН 978-0-521-34056-4. Збл  0653.10001.
4. Делеглиз, Марк (1998). «Границы плотности обильных целых чисел». Экспериментальная математика . 7 (2): 137–143. CiteSeerX 10.1.1.36.8272 . дои : 10.1080/10586458.1998.10504363. ISSN  1058-6458. МР  1677091. Збл  0923.11127. 
5. Холл, Ричард Р. (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 .