2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение31.03.2014, 15:56 
Заслуженный участник


31/12/05
1414
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)

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение01.04.2014, 14:23 


23/02/12
3112
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)

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

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение01.04.2014, 15:37 
Заслуженный участник


31/12/05
1414
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$-нотации.

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение01.04.2014, 16:17 


23/02/12
3112
tolstopuz в сообщении #844145 писал(а):
То есть равенство (10) неверно.

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

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение01.04.2014, 16:57 
Заслуженный участник


31/12/05
1414
vicvolf в сообщении #844163 писал(а):
tolstopuz в сообщении #844145 писал(а):
То есть равенство (10) неверно.
Нет равенство верно.
Простая проверка опровергает ваше утверждение.

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

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение04.04.2014, 12:35 


23/02/12
3112
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$ - функция Римана.

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

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение04.04.2014, 14:51 
Заслуженный участник


31/12/05
1414
vicvolf в сообщении #845271 писал(а):
На основании теоремы 321 (Бухштаб)
Спасибо, я знаю, что на основании этой теоремы этот факт доказывается тривиально.

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение04.04.2014, 20:16 
Заслуженный участник
Аватара пользователя


11/12/05
3542
Швеция
vicvolf в сообщении #845271 писал(а):
На основании (12) определим искомую асимптотическую плотность пар


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

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение05.04.2014, 15:38 


23/02/12
3112
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 уже устарела, поэтому ранее я привел более современную, хотя и она с тех пор уточнялась, но это не играет роли при определении асимптотической плотности. Не беда, что это тривиально, так как это только пример.

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение06.04.2014, 13:46 


23/02/12
3112
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$.

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

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение07.04.2014, 11:30 


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

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

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение28.07.2015, 21:30 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 57 ]  На страницу Пред.  1, 2, 3, 4

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group