2014 dxdy logo

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

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




 
 Распределение НОД
Сообщение10.10.2009, 23:06 
Как доказать(где прочитать), что если А = {1,2,...,N} и случайный вектор (x1,x2) ~ R(AxA), то

$\mathop {\lim }\limits_{N \to + \infty } P(НОД(x1,x2) = k) = 6/({\pi}^2k^2)$

У меня есть совсем немного мыслей на этот счёт. Одна из них - это если рассмотреть ряд из квадратов натуральных чисел в -1 степени, то сумма этого ряда будет равна ${\pi}^2/6$ - имеем распределение вероятностей на множестве натуральных чисел. Вот только толку от этого немного. Здесь, скорее всего, надо разбираться в теории чисел.

Я, даже, будучи не в силах доказать этот факт, решил проверить на компьютере. Действительно, уже при N = 1000 формула верна. Кому интересно, могу выложить код.

 
 
 
 Re: Распределение НОД
Сообщение10.10.2009, 23:17 
Аватара пользователя
Ой, ну это боян. Ключевой факт такой: $$\prod\limits_1^\infty\left( 1-{1\over p_i^2}\right)={6\over \pi^2}$$
Слева от этого факта идут рассуждения про "...вероятность, что у них нет общего множителя 2, а также 3, 5, и других простых чисел..." Справа от него - сведение произведения (ну, обратного ему) к ряду, который Вы уже знаете.

 
 
 
 Re: Распределение НОД
Сообщение10.10.2009, 23:31 
Спасибо большое! Да, самое главное вы мне подсказали. Большего и не надо, а ваша формула, кажется следует из похожей формулы для гамма-функции. Ну или откуда-то из этой области. Это я уже сам докажу, почитаю в фихтенгольце.

Какие же тут, всё-таки, все умные. И главное, во всех областях математики шарят :)

 
 
 
 Re: Распределение НОД
Сообщение10.10.2009, 23:33 
Аватара пользователя
Она не моя, не следует, не похожа, и не для гамма-функции. И - да - она не нужна. Можно короче. Достаточно понять, почему $\sim {1\over k^2}$, а нормировочный коэффициент сам вылезет.

 
 
 
 Re: Распределение НОД
Сообщение10.10.2009, 23:46 
Эта формула - вероятность того, что два числа взаимнопросты, Она мне нужна и с ней как-то понятнее чтоли... Непонятно только, почему вероятность того, что число делится на $p$ = $1/p^2$

 
 
 
 Re: Распределение НОД
Сообщение10.10.2009, 23:50 
Аватара пользователя
Логично, что непонятно, поскольку неправильно. Эта вероятность равна $1/p$.

 
 
 
 Re: Распределение НОД
Сообщение10.10.2009, 23:58 
Ага. Вот оно что. Здесь надо немного покрутить формулу Эйлера, наверное.

 
 
 
 Re: Распределение НОД
Сообщение11.10.2009, 00:01 
Аватара пользователя
Да не надо тут формулу Эйлера крутить. Вероятность того, что оба числа делятся на $p$ -- $1/p^2$. Но делимости на разные простые числа -- независимые события, откуда и получается написанная ИСН формула.

 
 
 
 Re: Распределение НОД
Сообщение11.10.2009, 00:09 
Аватара пользователя
Всё так, да. Но я повторяю, это не нужно, потому что потом всё равно доказывать про $k^2$ в знаменателе, а если это доказать, то коэффициент вылезет сам.

 
 
 
 Re: Распределение НОД
Сообщение11.10.2009, 00:12 
Аватара пользователя
Хорхе в сообщении #250795 писал(а):
Вероятность того, что оба числа делятся на $p$ -- $1/p^2$. Но делимости на разные простые числа -- независимые события, откуда и получается написанная ИСН формула.
Вот только это эвристика, а не доказательство.

 
 
 
 Re: Распределение НОД
Сообщение11.10.2009, 00:13 
Цитата:
Вот только это эвристика, а не доказательство.

да, тут те же самые слова написаны. просто определение независимости.

Но хотя интуитивно понятно, что так. (Теперь понятно, спасибо Хорхе)

 
 
 
 Re: Распределение НОД
Сообщение11.10.2009, 00:37 
Аватара пользователя
malin в сообщении #250798 писал(а):
Но хотя интуитивно понятно, что так
Оно, конечно, так, но интуитивно понятное не всегда бывает верным.
Понятно, что зависимость от $k$ есть $c/k^2$, если, конечно, этот предел существует. Но ни существование предела, ни то, что сумма пределов по всем $k$ равна 1, не очевидно. Имхо, проще всего доказать утверждение в лоб, без всякой эвристики.

 
 
 
 Re: Распределение НОД
Сообщение11.10.2009, 00:39 
Аватара пользователя
Кстати, не совсем эвристика. В рамках вероятностной теории чисел (где, впрочем, я вовсе не являюсь специалистом) такие рассуждения приобретают вполне строгий смысл.

-- Вс окт 11, 2009 01:41:12 --

Ага, мы, наверное, о разных вещах говорим :)

-- Вс окт 11, 2009 01:42:52 --

Да нет, об одном и том же. $(x,y)=k\Leftrightarrow (x/k,y/k)=1$.

 
 
 
 Re: Распределение НОД
Сообщение11.10.2009, 16:42 
Цитата:
Понятно, что зависимость от $k$ есть $c/k^2$, если, конечно, этот предел существует. Но ни существование предела, ни то, что сумма пределов по всем $k$ равна 1, не очевидно


Если $c = 6/{\pi}^2$, то сумма пределов по всем $k$ = 1, т.к.
Цитата:
если рассмотреть ряд из квадратов натуральных чисел в -1 степени, то сумма этого ряда будет равна ${\pi}^2/6$

 
 
 
 Re: Распределение НОД
Сообщение11.10.2009, 17:06 
Аватара пользователя
malin в сообщении #250930 писал(а):
Цитата:
Понятно, что зависимость от $k$ есть $c/k^2$, если, конечно, этот предел существует. Но ни существование предела, ни то, что сумма пределов по всем $k$ равна 1, не очевидно


Если $c = 6/{\pi}^2$, то сумма пределов по всем $k$ = 1, т.к.
Цитата:
если рассмотреть ряд из квадратов натуральных чисел в -1 степени, то сумма этого ряда будет равна ${\pi}^2/6$
Я хотел сказать, что "доказательство", которое предлагал ИСН (если $c$ --- значение предела при $k=1$, то при произвольном $k$ предел равен $c/k^2$; значение постоянной $c$ находится из условия $\sum_{k=1}^\infty c/k^2=1$), на самом деле не является доказательством по двум причинам. Во-первых, существование $c$ не очевидно (и приведённые выше эвристические рассуждения не доказывают его существования; и даже не доказывают, что $c=6/\pi^2$, если предположить, что предел существует); во-вторых, равенство $\sum_{k=1}^\infty c/k^2=1$ тоже не очевидно. То, что оба эти факта верны, --- это нам просто повезло.
Настоящее док-во выглядит так (при $k=1$)
$P((x_1,x_2)=1)=N^{-2}\sum_{1\le x,y\le N}\sum_{d|(x,y)}\mu(d)=N^{-2}\sum_{d\le N}\mu(d)\lfloor N/d\rfloor^2=$
$=\sum_{d=1}^N\bigl(\mu(d)/d^2+O(1/(Nd))\bigr)=6/\pi^2+o(1).$

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group