Связь между асимптотикой ариф. функции и ее вер. харак-ми

[vicvolf]

Уважаемые участники форума!

Я опубликую здесь некоторые утверждения на данную тему, в которых возможны ошибки. Буду благодарен за замечания.



Утверждение 1

Пусть арифметическая функция $f(m)$ при $m=1,2,...,n$ принимает хотя бы два различных значения.

Обозначим среднее значение $f(m)$ -$A_n=\sum_{m=1}^n {f(m)}/n$ и дисперсию $D_n=\sum_{m=1}^n {(f(m)-A_n)^2}/n$.

Пусть $b(n)$ - положительная неограниченно возрастающая функция при $n \to \infty$ и $\sigma_n=(D_n)^{1/2}=O(g(n))$, где $g(n)$ - монотонная функция.

Тогда, почти всюду, для $f(m)$ $m=1,2,...,n$ и $n \to \infty$ выполняется асимптотика: $A_n+O(g(n)n^{\epsilon})$.

Доказательство

Так как $f(m)$ принимает хотя бы два различных значения, то $\sigma_n$ не равно нулю и справедливо неравенство Чебышева:

$P(|f(m)-A_n| \leq k\sigma_n) \geq 1-1/k^2$, где $k \geq 1$.

Поэтому для любой положительной неограниченно возрастающей функции $b(n)$ при $n \to \infty$ выполняется:

$P(|f(m)-A_n| \leq b(n)\sigma_n)=1$.

Учитывая, что $\sigma(n)=O(g(n))$, получим, что, почти всюду, для $f(m)$ $m=1,2,...,n$ и $n \to \infty$:

$f(m)-A_n=O(b(n)g(n))$.

В качестве $b(n)$ можно взять любую медленно растущую функцию $b(n)<n^{\epsilon}$, где $\epsilon$ - малое положительное число.

Поэтому, почти всюду, для $f(m)$ $m=1,2,...,n$ и $n \to \infty$ выполняется асимптотика: $A_n+O(g(n)n^{\epsilon})$. ч.т.д.



Утверждение 2

Пусть арифметическая функция имеет асимптотику:

$f(n)=A(n)+O(g(n)n^{\epsilon})$,

где $A(n)$ - главный член асимптотики, $g(n)$ - монотонная функция и $\epsilon>0$.

Обозначим $A_n$ - среднее значение арифметической функции - $A_n=\sum_{m=1}^n {f(m)}/n$ и дисперсию $D_n=\sum_{m=1}^n {(f(m)-A_n)^2}/n$.

Тогда выполняются асимптотики: $A_n=A(n)+O(g(n)n^{\epsilon})$ и $\sigma_n=(D_n)^{1/2}=O(g(n)n^{\epsilon_1})$, где $\epsilon_1<\epsilon$.

Доказательство

Пусть для арифметической функции выполняется асимптотика: $f(n)=A(n)+O(g(n)n^{\epsilon})$.

Рассмотрим теперь формулу из утверждения 1:

$P(|f(m)-A_n| \leq b(n)\sigma_n)=1$.

Подставим в эту формулу асимптотику арифметической функции $f(m)$:

$P(|A(n)+O(g(n)n^{\epsilon})-A_n| \leq b(n)\sigma_n)=1$.

Подставим в формулу значение асимптотики $A_n$ из условий утверждения:

$P(|A(n)+O(g(n)n^{\epsilon})-A(n)+O(g(n)n^{\epsilon})| \leq b(n)\sigma_n)=1$.

Данная формула будет справедлива, если взять $\sigma_n=O(g(n)n^{\epsilon_1})$ и $b(n)=O(n^{\epsilon_2})$, где $\epsilon=\epsilon_1+\epsilon_2$ ч.т.д.




В качестве примера 1 использования утверждения 2 возьмем арифметическую функцию $\sum_{p \leq n} {\log(p)}$.

В теме ранее была получена асимптотика данной арифметической функции:

$\sum_{p \leq n} {\log(p)}=n+O(n/\log(n))$.

В данном случае $g(n)=O(n^{1-\epsilon}/\log(n))$.

Поэтому $A_n=n+O(n/\log(n))$, $\sigma_n=O(n^{1-\epsilon_1}/\log(n))$, где $\epsilon_1<\epsilon$.

Пример 2. Проблема делителей Дирихле. Вороной доказал асимптотику:

$\sum_{k \leq n} {\tau(k)}=n\log(n)+(2C-1)n+O(n^{1/3+\epsilon})$.

Следовательно, $g(n)=n^{1/3}$. Тогда $A_n=n\log(n)+(2C-1)n+O(n^{1/3+\epsilon})$, $\sigma_n=O(n^{1/3+\epsilon_1})$, где $\epsilon_1<\epsilon$.

Пример 3. Известна асимптотика:

$\sum_{k \leq n} {1/\varphi(k)}=C_1\log(n)+C_2+O(\log^2(n)/n^{2/3})$.

Поэтому $g(n)=\log^2(n)/n^{2/3+\epsilon}$. Тогда $A(n)=C_1\log(n)+C_2+O(\log^2(n)/n^{2/3})$, $\sigma_n=\log^2(n)/n^{2/3+\epsilon_1}$, где $\epsilon_1<\epsilon$.

[Brukvalub]

(Оффтоп)

Ну вот как объяснить этому участнику, что теория вероятностей начинается с описания вероятностного пространства? Видимо, уже никак не объяснить...

[alisa-lebovski]

Это не теория вероятностей, а вероятностная теория чисел, специфическая вещь.

[Brukvalub]

alisa-lebovski в сообщении #1474330 писал(а):

Это не теория вероятностей, а вероятностная теория чисел, специфическая вещь.

Если в коневодстве используется теория вероятностей, то и в коневодстве придется начинать с описания вероятностного пространства. Перейдем к деталям: тс с поразительным упорством использует неравенство Чебышева и прочие изюминки аппарата теории вероятностей как дикарь дубину, корректное использование неравенства Чебышева предполагает, что сначала фиксируется вероятностное пространство, и только потом происходят манипуляции со случайными величинами на этом пространстве, а тс "изучает" асимптотики функций на начальном отрезке натурального ряда, наделяя этот отрезок однородной вероятностной мерой. Меняется длина отрезка - меняется и вероятностное пространство, какие тогда могут быть оценки с применением неравенств и т.п., относящихся к ФИКСИРОВАННОМУ вероятностному пространству?
Что само удивительное, так это то, что топикстартеру об этом уже стопицоттыщ на это указывали, но все без толку...

[alisa-lebovski]

А может, тут работает схема серий?

[nnosipov]

ТС сам приводил ссылку на книжку Кубилюса "Вероятностные методы в теории чисел", но вот читает ли он ее и насколько качественно, непонятно.

[vicvolf]

nnosipov в сообщении #1474356 писал(а):

ТС сам приводил ссылку на книжку Кубилюса "Вероятностные методы в теории чисел", но вот читает ли он ее и насколько качественно, непонятно.

Да, именно это я использую. Здесь на стр. 54 это называется аналогом закона больших чисел для арифметических функций - http://bookre.org/reader?file=567701&pg=54 О подходящем названии еще можно поспорить, но формула верна. Я старался сохранить обозначения.

[Brukvalub]

nnosipov в сообщении #1474356 писал(а):

ТС сам приводил ссылку на книжку Кубилюса "Вероятностные методы в теории чисел", но вот читает ли он ее и насколько качественно, непонятно.

Выходит, тс ищет здесь специалиста, изучившего эту книгу и ждет от такого специалиста комментариев?
Обычно все опусы тс претерпевают итерации: "так, никто ошибок не нашел, значит все верно, получите следующую порцию выкладок".
Уверен, что и сейчас будет очередная такая итерация.
Но, на самом деле, никто давно уже и не пытается во всем этом разбираться...

[vicvolf]

Очень благодарен всем за любое мнение и еще более благодарен тем, кто прочитал или прочитает тему.

[vicvolf]

alisa-lebovski в сообщении #1474330 писал(а):

Это не теория вероятностей, а вероятностная теория чисел, специфическая вещь.

Прозорливая мысль. Вот эта формула из утверждения 1, которую Кубилюс называет аналогом закона больших чисел:

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

Поэтому для любой положительной неограниченно возрастающей функции $b(n)$ при $n \to \infty$ выполняется:

$P(|f(m)-A_n| \leq b(n)\sigma_n)=1$.

В утверждении 1 надо теперь заменить сходимость почти наверное на сходимость по распределению, с вероятностью равной 1.

Кстати, вместо неравенства Чебышева надо использовать его аналог и понимать его надо в смысле сходимости по распределению. Это тоже есть у Кубилюса в этом разделе. Конечно, там ни слова не сказано, что аналог надо так понимать, но мы до этого сами дошли.

[Lia]

vicvolf
Лучше бы Вам использовать терминологию Кубилюса, потому что до чего бы Вы ни дошли, это ни на что не повлияло:

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

$P(|f(m)-A_n| \leq b(n)\sigma_n)=1$.

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

За сим тему отправляю в Дискуссионный раздел, вполне достаточно того, что Вы долго обсуждали в ПРР тему, которую Вам запрещалось возобновлять.

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Дискуссионные темы (М)»

-- 10.08.2020, 13:19 --

А поскольку Кубилюса полезет читать далеко не каждый, а всякий ТС, казалось бы, заинтересован в читателе, то основные тезисы лучше разъяснять прямо в теме.

[alisa-lebovski]

Пусть $A(m,n)$ есть некое утверждение о числах $1\le m\le n$, $I(.)$ - индикатор. Полагаю, надо обозначить

$$P_n(A(m,n))=\frac{1}{n}\sum_{m=1}^nI(A(m,n))$$

и писать

$$P_n(A(m,n))\to 1,\quad n\to\infty,$$

так будет корректно. В частности,

$$P(|f(m)-A_n| \leq b(n)\sigma_n)=1$$

переписать как

$$P_n(|f(m)-A_n| \leq b(n)\sigma_n)\to 1.\quad n\to\infty.$$

-- Пн авг 10, 2020 12:34:29 --

И кстати, утверждения вида

$$P_n(|f(m)-A_n|\le CB_n)\to 1,\quad n\to\infty$$

для любого $C>0$ и

$$f(n)-A_n=O(B_n),\quad n\to\infty$$

совсем не эквивалентны. Если взять теорему Харди — Рамануджана, там можно получить утверждение первого типа, а второго типа - просто неверно, хотя бы потому что время от времени, на простых числах, $\omega(n)=1$.

[vicvolf]

alisa-lebovski в сообщении #1478200 писал(а):

Пусть $A(m,n)$ есть некое утверждение о числах $1\le m\le n$, $I(.)$ - индикатор. Полагаю, надо обозначить

$$P_n(A(m,n))=\frac{1}{n}\sum_{m=1}^nI(A(m,n))$$

и писать

$$P_n(A(m,n))\to 1,\quad n\to\infty,$$

так будет корректно. В частности,

$$P(|f(m)-A_n| \leq b(n)\sigma_n)=1$$

переписать как

$$P_n(|f(m)-A_n| \leq b(n)\sigma_n)\to 1.\quad n\to\infty.$$

Спасибо, за предложение по обозначениям. Вижу Вы взяли за основу идеи обозначений у Кубилюса.

Начать нужно с вероятностного пространства для арифметических функций:

Любой начальный отрезок натурального ряда $\{1,2,\dotsc,n\}$ можно естественным образом превратить в вероятностное пространство $\left(\Omega_{n},\mathcal{A}_{n},\mathbb{P}_{n}\right)$, взяв $\Omega_{n}=\{1,2,\dotsc,n\}$, $\mathcal{A}_{n}$ — все подмножества $\Omega_{n}$, $\mathbb{P}_{n}(A)=\frac{|A|}{n}$. Тогда произвольную (вещественно- или даже комплекснозначную) функцию $f(k)$ натурального аргумента (а точнее, её ограничение на $\Omega_{n}$) можно рассматривать как случайную величину $\xi_{n}$ на этом вероятностном пространстве: $\xi_{n}(k)=f(k)$, $1\leqslant k\leqslant n$.

После описания вероятностного пространства надо обосновать использование в данном случае сходимости по распределению, с вероятностью равной 1, так как в этой теме этого не было.

Кстати $\sum_{m=1}^nI(A(m,n))$ - это арифметическая функция количества натуральных чисел $m \leq n$, удолетворяющих утверждению $A(m,n)$. Может быть лучше взять другую букву, так у Кубилюса $A_n$ - среднее значение арифметической функции, а у меня $A(n)$ - главный член асимптотики.

alisa-lebovski в сообщении #1478200 писал(а):

И кстати, утверждения вида

$$P_n(|f(m)-A_n|\le CB_n)\to 1,\quad n\to\infty$$

для любого $C>0$ и

$$f(n)-A_n=O(B_n),\quad n\to\infty$$

совсем не эквивалентны. Если взять теорему Харди — Рамануджана, там можно получить утверждение первого типа, а второго типа - просто неверно, хотя бы потому что время от времени, на простых числах, $\omega(n)=1$.

Я так не писал. Писал, что это выполняется "почти всюду". Это учитывает указанный случай $\omega(n)=1$.

Но как мы решили, что сходимость "почти наверное" надо заменить на сходимость "по распределению, с вероятностью равной 1".

Это можно записать не только через неравенство, но и через утверждение об асимптотике:

$$P_n(f(n)=A_n+O(b(n)\sigma(n)))\to 1,\quad n\to\infty$$

Сейчас все согласуем, а потом я переделаю первое сообщение.

[alisa-lebovski]

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

Но как мы решили, что сходимость "почти наверное" надо заменить на сходимость сходимость "по распределению, с вероятностью равной 1".

Я лично такого не решала. Лучше вообще не называйте это словами, чем все время неправильно.

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

Это можно записать не только через неравенство, но и через утверждение об асимптотике:

$$P_n(f(n)=A_n+O(b(n)\sigma(n)))\to 1,\quad n\to\infty$$

Нет, нельзя так записать! Это бессмыслица. Можно записать либо

$$P_n(|f(m)-A_n|\le Cb(n)\sigma(n))\to 1,\quad n\to\infty,\quad\forall C>0,$$

либо

$$f(n)=A_n+O(b(n)\sigma(n)),\quad n\to\infty,$$

и это будет иметь разный смысл.

-- Пн авг 10, 2020 19:02:41 --

Вот Вам простой пример: пусть

$$f(n)=n,$$

тогда

$$P_n\left(\left|f(m)-\frac{n+1}{2}\right|\le\frac{n-1}{2}\right)=1.$$

Понимаете разницу? Тут нет даже общего $A_n$.