Некоторые св-ва последо-стей на огран.интерв.натурально ряда

[tolstopuz]

vicvolf в сообщении #842649 писал(а):

Пусть из последовательности натуральных чисел: $1,2,...N$ наугад выбираются k чисел $k<N$, притом числа могут повторяться.
Определить асимптотическую плотность (9) для k-кортежей взаимнопростых чисел, т.е что выбранные k чисел окажутся взаимнопростыми.

Введем следующие обозначения:
- $C_i$ - событие, что выбранное наугад i-ое натуральное число кратно натуральному числу d;
- $C$ - событие, что наибольший общий делитель (НОД) для выбранных k чисел - $x_1,...x_k$ равен d или $gcd (x_1,...x_k)=d$;
- $D$ - событие, что $gcd (x_1/d,...x_k/d)=1$.
Тогда, учитывая, как было показано выше, что плотность (3) является вероятностью и независимость событий в выборке, получим:
$Pr(C)=Pr(D) \cdot \prod_{i=1}^k Pr(C_i)$, (10) где $Pr(A)$ - вероятность события $A$.

Продемонстрируйте это на численном примере. Возьмите пары чисел от $(1, 1)$ до $(3, 3)$ и $d=2$.

vicvolf в сообщении #843464 писал(а):

Кто-нибудь из Вас встречал это утверждение с доказательством ранее? Если да, то при возможности дайте на него ссылку. Я не нашел.

Cohen, E. "Arithmetical Functions Associated with Arbitrary Sets of Integers." Acta Arith. 5, 407-415, 1959.
http://matwbn.icm.edu.pl/ksiazki/aa/aa5/aa544.pdf (следствие 3.3)

[vicvolf]

tolstopuz в сообщении #843622 писал(а):

vicvolf в сообщении #842649 писал(а):

Пусть из последовательности натуральных чисел: $1,2,...N$ наугад выбираются k чисел $k<N$, притом числа могут повторяться.
Определить асимптотическую плотность (9) для k-кортежей взаимнопростых чисел, т.е что выбранные k чисел окажутся взаимнопростыми.
Введем следующие обозначения:
- $C_i$ - событие, что выбранное наугад i-ое натуральное число кратно натуральному числу d;
- $C$ - событие, что наибольший общий делитель (НОД) для выбранных k чисел - $x_1,...x_k$ равен d или $gcd (x_1,...x_k)=d$;
- $D$ - событие, что $gcd (x_1/d,...x_k/d)=1$.
Тогда, учитывая, как было показано выше, что плотность (3) является вероятностью и независимость событий в выборке, получим:
$Pr(C)=Pr(D) \cdot \prod_{i=1}^k Pr(C_i)$, (10) где $Pr(A)$ - вероятность события $A$.

Продемонстрируйте это на численном примере. Возьмите пары чисел от $(1, 1)$ до $(3, 3)$ и $d=2$.

В Вашем примере $Pr(C_1) \cdot Pr (C_2)=1/d^2+O(1/N)=1/4 +O(1/3)$,т.е возникает очень большая ошибка из-за малого значения N. У меня подразумевается N-большое число, так как потом рассматривается предел при N стремящемся к бесконечности.
Однако, если уже взять N=9, то $Pr(D)=52/81, Pr(C)=16/81, Pr(C_1) \cdot Pr(C_2)=1/4+O(1/9)$ и равенство $Pr(C)=Pr(D) \cdot Pr(C_1) \cdot Pr(C_2)$ получается при $Pr(C_1) \cdot Pr(C_2)=1/4+0,05769$, где 0,05769<1/9.

vicvolf в сообщении #843464 писал(а):

Кто-нибудь из Вас встречал это утверждение с доказательством ранее? Если да, то при возможности дайте на него ссылку. Я не нашел.

Цитата:

Cohen, E. "Arithmetical Functions Associated with Arbitrary Sets of Integers." Acta Arith. 5, 407-415, 1959.
http://matwbn.icm.edu.pl/ksiazki/aa/aa5/aa544.pdf (следствие 3.3)

Большое спасибо.

[tolstopuz]

vicvolf в сообщении #844119 писал(а):

tolstopuz в сообщении #843622 писал(а):

vicvolf в сообщении #842649 писал(а):

$Pr(C)=Pr(D) \cdot \prod_{i=1}^k Pr(C_i)$, (10) где $Pr(A)$ - вероятность события $A$.

Продемонстрируйте это на численном примере. Возьмите пары чисел от $(1, 1)$ до $(3, 3)$ и $d=2$.

В Вашем примере $Pr(C_1) \cdot Pr (C_2)=1/d^2+O(1/N)=1/4 +O(1/3)$,т.е возникает очень большая ошибка из-за малого значения N. У меня подразумевается N-большое число, так как потом рассматривается предел при N стремящемся к бесконечности.

То есть равенство (10) неверно. Спасибо за честность.

Кроме того, запись $O(1/N)=O(1/3)$ неверна и в очередной раз показывает ваше непонимание $O$-нотации.

[vicvolf]

tolstopuz в сообщении #844145 писал(а):

То есть равенство (10) неверно.

Нет равенство верно. Просто вероятность $Pr(C_i)=1/d+O(1/N)$ на конечном интервале от 1 до N и нельзя ее считать равной 1/d.

[tolstopuz]

vicvolf в сообщении #844163 писал(а):

tolstopuz в сообщении #844145 писал(а):

То есть равенство (10) неверно.

Нет равенство верно.

Простая проверка опровергает ваше утверждение.

Кстати, в какой вероятностной мере определены присутствующие в равенстве (10) вероятности?

[vicvolf]

tolstopuz в сообщении #844178 писал(а):

vicvolf в сообщении #844163 писал(а):

tolstopuz в сообщении #844145 писал(а):

То есть равенство (10) неверно.

Нет равенство верно.

Простая проверка опровергает ваше утверждение.

Соласен, равенство (10) неверно.
Приведу другой вариант доказательства.

Рассмотрим пример для случая 3.
Пусть из последовательности натуральных чисел: $1,2,...N$ наугад выбираются k чисел $k<N$, притом числа могут повторяться.
Определить асимптотическую плотность (9) для k-кортежей взаимнопростых чисел, т.е что выбранные k чисел окажутся взаимнопростыми.

Ранее было рассмотрено свойство симметричности для k-арных отношений. k-арное отношение между k взаимно простыми числами является симметричным, т.е. кортежи $<x_1,...x_k>$ данного отношения расположены симметрично относительно главной диаганали $<x_1=...=x_k>$.

Сначала рассмотрим случай k=2.
В этом случае кортежи $<x_1,x_2>$ расположены симметрично относительно главной диаганали $<x_1=x_2>$, поэтому можно определить количество пар взаимно простых чисел при $x_1>x_2$, а потом умножив его на 2 получить общее количество пар взаимно простых чисел не превосходящих натуральное число $N$.
При $x_1>x_2$ количество взаимно простых чисел с $x_1$ равно $\varphi(x_1)$, где $\varphi(x)$ - функция Эйлера для натурального числа x.
Просуммировав количество взаимно простых чисел с $x_1$ при всех значениях $x_1$ от 1 до N получим $\sum_{n=1}^{N}{\varphi(n)}$ - количество пар взаимно простых чисел не превосходящих N при условии $x_1>x_2$.
На основании теоремы 321 (Бухштаб) $\sum_{n=1}^{N}{\varphi(n)}=3N^2/(\pi)^2+O(N\ln(N))$.(10) Оценка (10) уточнялась, но для определения асимптотической плотности достаточно этой оценки.
Умножив на 2, для учета симметричных кортежей $<x_1,x_2>$ для случая $x_2>x_1$ получим общее количество пар взаимно простых чисел на интервале от 1 до N:
$\pi(B_N)=6N^2/(\pi)^2+O(N\ln(N))$. (11)
На основании (11) определим вероятность выбранной наугад пары натуральных чисел, не превосдодящих N, быть взаимно простыми по формуле (3):
$Pr(B_N)=\pi(B_N)/N^2=6/(\pi)^2+O(\ln(N)/N)$.(12)
На основании (12) определим искомую асимптотическую плотность пар взаимно простых чисел по формуле (9):
$P'(B)=\lim \limits_{N \to \infty} {\pi(B_N)/N^2}=\lim \limits_{N \to \infty} {6/(\pi)^2}+O(\ln(N)/N)=6/(\pi)^2=1/\zeta(2)$,(13) где $\zeta$ - функция Римана.

Продолжение следует.

[tolstopuz]

vicvolf в сообщении #845271 писал(а):

На основании теоремы 321 (Бухштаб)

Спасибо, я знаю, что на основании этой теоремы этот факт доказывается тривиально.

[shwedka]

vicvolf в сообщении #845271 писал(а):

На основании (12) определим искомую асимптотическую плотность пар

Только держите себя за фалды, чтобы случайно не заявить, что это-какая-то вероятность.

[vicvolf]

tolstopuz в сообщении #843622 писал(а):

Cohen, E. "Arithmetical Functions Associated with Arbitrary Sets of Integers." Acta Arith. 5, 407-415, 1959.
http://matwbn.icm.edu.pl/ksiazki/aa/aa5/aa544.pdf (следствие 3.3)

Еще раз благодарю за интересную ссылку. С удовольствием ознакомился с текстом статьи. Как Вы ее нашли? Теперь можно ссылаться на эту работу.
В частности из теоремы 3.2 для k>2 на множестве делителей S, состоящего из одного числа 1, получаем оценку количества взаимно простых k-кортежей:
$\pi(B_N)=N^k/\zeta(k)+O(N^{k-1})$. (14)
Из формул (3) и (14) получаем вероятность, что выбранный k-кортеж состоит только из взаимно простых натуральных чисел не превосходящих N:
$Pr(B_N)=\pi(B_N)/N^k=1/\zeta(k)+O(1/N)$.(15)
Асимптотическая плотность k-кортежей, состоящих только из взаимно простых натуральных чисел, на основании формул (9) и (15) равна:
$P'(B)=\lim \limits_{N \to \infty} {\pi(B_N)/N^k}=\lim \limits_{N \to \infty} {1/\zeta(k)+O(1/N)}=1/\zeta(k)$,(16) где $\zeta$ - функция Римана.
Для k=2 оценка количества k-кортежей на множестве делителей s в теореме 3.2 уже устарела, поэтому ранее я привел более современную, хотя и она с тех пор уточнялась, но это не играет роли при определении асимптотической плотности. Не беда, что это тривиально, так как это только пример.

[vicvolf]

shwedka в сообщении #845467 писал(а):

vicvolf в сообщении #845271 писал(а):

На основании (12) определим искомую асимптотическую плотность пар

Только держите себя за фалды, чтобы случайно не заявить, что это-какая-то вероятность.

Как я уже писал асимптотическая плотность, определенная по формуле (9), имеет с вероятностью, определенной по формуле (3) общие свойства.
Пусть $\Omega$ множество k-кортежей $N^k$ (k-ое прямое произведение натурального ряда), а $F$ - алгебра подмножеств $\Omega$.
Тогда для асимптотической плотности k-кортежей- P'(B). определенной по формуле (9) выполняются следующие свойства:
1. Для любого подмножества $D \in F$ выполняется $P'(D)\geq 0$.
2. Для любых двух подмножеств $D_1 \in F$ и $D_2 \in F$ выполняется $P'(D_1 \cup D_2)=P'(D_1)+P(D_2)$.
3. $P'(\Omega)=1$.
Но этого конечно не достаточно, чтобы асимптотическая плотность, определенная на бесконечном пространстве $N^k$, была вероятностью. Выполняется только свойство 2 - конечная аддитивность и не выполняется свойство - счетная аддитивность.
Вот кстати пример, подтверждающий это.
Рассмотрим асимптотическую плотность натуральных чисел кратных натуральному d. Она равна - 1/d. Если просуммировать данную асимптотическую плотность для всех значений d от 1 до бесконечности, то получим сумму гармонического ряда равную бесконечности. Если бы асимптотическая плотность, определенная в (9) была бы вероятностью, то выполнялась бы счетная аддитивность и на основании свойства 3 эта сумма была бы равна 1.
С другой стороны, если рассмотреть асимптотическую плотность натуральных чисел, имеющих остаток от деления на d от 0 до d-1, т.е. последовательности вида - $dn+l$, где l=0,...d-1, то асимптотическая плотность каждой из них также равна 1/d. Если просуммировать асимптотическую плотность этих последовательностей для всех остатков от $l=0$ до $l=d-1$, то получим 1, так как для асимптотической плотности выполняется конечная аддитивность - свойство 2 и свойство 3.
Есть еще одно свойство асимптотической плотности, вытекающее из определений (3) и (9):
$P'(B)=\lim \limits_{N \to \infty} {Pr(B_N)}$.(17)
Данное свойство я использовал во всех примерах для нахождения асимптотической плотности.
Рассмотрим подробнее последний пример определения асимптотической плотности для k-кортежей взаимно простых чисел, т.е что выбранные k чисел окажутся взаимно простыми.
На основании (17) формулу (16) можно записать в виде:
$P'(B)=\lim \limits_{N \to \infty} {Pr(B_N)}=\lim \limits_{N \to \infty} {1/\zeta(k)+O(1/N)}=1/\zeta(k)$,(18) где $\zeta$ - функция Римана.
На основании определения (3) последовательность вероятностей $Pr(B_N)$ является последовательностью рациональных чисел, а ее предел - асимптотическая плотность, к которой стремится данная последовательность, в общем случае, не является рациональным числом. Так при $k=2$ асимптотическая плотность пар взаимно простых чисел, на основании (13), равна $6/(\pi)^2$, т.е. является иррациональным числом, поэтому она ни как не может быть вероятностью, определенной по формуле (3).
Возможно, что асимптотическая плотность k-кортежей взаимно простых чисел, определенная по формуле (16) - $1/\zeta(k)$, является иррациональным числом при всех натуральных значениях k>1.
Отсюда напрашиваются гипотезы.

Гипотеза 1. Функция Римана $\zeta(k)$ принимает иррациональные значения при всех натуральных значениях k>1.

В пользу этой гипотезы говорит следующее. Известно, что функция Римана при четных значениях является иррациональным числом. Также известно, что функция Римана иррациональна при $k=3$. http://ru.wikipedia.org/wiki/%D0%9F%D0% ... 1%80%D0%B8
Также известна бесконечность иррациональных значений функции Римана в нечетных числах, а наличие иррациональных значений функции Римана в некоторых наборах нечетных чисел. http://www.mathnet.ru/links/d882d142397 ... /rm389.pdf


Гипотеза 2. Функция Римана $\zeta(k)=(\pi)^k/C(k)$, где $C(k)$ - постоянная зависящая от натурального k>1.
Из гипотезы 2 следует гипотеза 1, поэтому гипотеза 2 носит более общий характер.

В пользу гипотезы 2 говорит следующее. Известно, что гипотеза 2 выполняется при четных значениях k:
$\zeta(2m)=(-1)^{m+1}(2\pi)^{2m}B_{2m}/2(2m)!$, (19) где $B_{2m}$ - число Бернулли.
Например, на основании (19): $\zeta(4)=(\pi)^4/90, \zeta(6)=(\pi)^6/1890$.

Буду благодарен за замечания и предложения.

[vicvolf]

vicvolf в сообщении #846163 писал(а):

Гипотеза 2. Функция Римана $\zeta(k)=(\pi)^k/C(k)$, где $C(k)$ - постоянная зависящая от натурального k>1.

Уточню - $C(k)$ - рациональное число и $C(k)<(\pi)^k$.

[Deggial]

Ветка Асимпт. плотность решений диофантовых уравнений выделена в Пургаторий по причине тривиальности результата, несоразмерного количества букв и бесперспективности дальнейшего обсуждения