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

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

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

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

Определение

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

определить Более явно, если для любого натурального числа n считающую функцию a ( n ) как количество элементов A , меньших или равных n , тогда естественная плотность A , равная α, в точности означает, что

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

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

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

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

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

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

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

Эти определения могут эквивалентно быть выражено следующим образом. Учитывая подмножество $A$ из $\mathbb {N}$, запишите ее в виде возрастающей последовательности, индексированной натуральными числами: $$A=\{a_{1}<a_{2}<\ldots \}.$$Затем $${\underline {d}}(A)=\liminf _{n\rightarrow \infty }{\frac {n}{a_{n}}},$$$${\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {n}{a_{n}}}$$и $$d(A)=\lim _{n\rightarrow \infty }{\frac {n}{a_{n}}}$$если предел существует.

Несколько более слабое понятие плотности — это верхняя банахова плотность. $d^{*}(A)$ из набора $A\subseteq \mathbb {N} .$ Это определяется как $$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 ^с обозначает его дополнение относительно $\mathbb {N}$, то d ( A ^с ) знак равно 1 - d ( А ).
  • Следствие: если $F\subset \mathbb {N}$ конечно (включая случай $F=\emptyset$), $d(\mathbb {N} \setminus F)=1.$

• Если $d(A),d(B),$ и $d(A\cup B)$ существовать, то $$\max\{d(A),d(B)\}\leq d(A\cup B)\leq \min\{d(A)+d(B),1\}.$$

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

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

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

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

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

• Набор

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

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

${\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}},$

тогда как его меньшая плотность

${\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. (См. закон Бенфорда .)

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

• Натансон, Мелвин Б. (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 .