Распределение НОД

[malin]

Как доказать(где прочитать), что если А = {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 формула верна. Кому интересно, могу выложить код.

[ИСН]

Ой, ну это боян. Ключевой факт такой:

$$\prod\limits_1^\infty\left( 1-{1\over p_i^2}\right)={6\over \pi^2}$$

Слева от этого факта идут рассуждения про "...вероятность, что у них нет общего множителя 2, а также 3, 5, и других простых чисел..." Справа от него - сведение произведения (ну, обратного ему) к ряду, который Вы уже знаете.

[malin]

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

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

[ИСН]

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

[malin]

Эта формула - вероятность того, что два числа взаимнопросты, Она мне нужна и с ней как-то понятнее чтоли... Непонятно только, почему вероятность того, что число делится на $p$ = $1/p^2$

[Хорхе]

Логично, что непонятно, поскольку неправильно. Эта вероятность равна $1/p$.

[malin]

Ага. Вот оно что. Здесь надо немного покрутить формулу Эйлера, наверное.

[Хорхе]

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

[ИСН]

Всё так, да. Но я повторяю, это не нужно, потому что потом всё равно доказывать про $k^2$ в знаменателе, а если это доказать, то коэффициент вылезет сам.

[RIP]

Хорхе в сообщении #250795 писал(а):

Вероятность того, что оба числа делятся на $p$ -- $1/p^2$. Но делимости на разные простые числа -- независимые события, откуда и получается написанная ИСН формула.

Вот только это эвристика, а не доказательство.

[malin]

Цитата:

Вот только это эвристика, а не доказательство.

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

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

[RIP]

malin в сообщении #250798 писал(а):

Но хотя интуитивно понятно, что так

Оно, конечно, так, но интуитивно понятное не всегда бывает верным.
Понятно, что зависимость от $k$ есть $c/k^2$, если, конечно, этот предел существует. Но ни существование предела, ни то, что сумма пределов по всем $k$ равна 1, не очевидно. Имхо, проще всего доказать утверждение в лоб, без всякой эвристики.

[Хорхе]

Кстати, не совсем эвристика. В рамках вероятностной теории чисел (где, впрочем, я вовсе не являюсь специалистом) такие рассуждения приобретают вполне строгий смысл.

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

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

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

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

[malin]

Цитата:

Понятно, что зависимость от $k$ есть $c/k^2$, если, конечно, этот предел существует. Но ни существование предела, ни то, что сумма пределов по всем $k$ равна 1, не очевидно

Если $c = 6/{\pi}^2$, то сумма пределов по всем $k$ = 1, т.к.

Цитата:

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

[RIP]

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).$