Асимптотическая оценка суммы

[vicvolf]

RIP
Вы согласны с формулой (2)?

[RIP]

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

Вы согласны с формулой (2)?

Если её внятно сформулировать, то да: это фактически неравенство Чебышёва.
Кстати, дисперсию для $\ln\varphi(n)$ Вы неправильно посчитали. По-моему, $D(n)=O(1)$ (либо растёт очень медленно, лень аккуратно считать). Но для $\ln\varphi(n)$ это не нужно: хватает матожидания и неравенства Маркова (если оценка вероятности не важна).

[vicvolf]

RIP
Вы правы, асимптотика дисперсии $\ln \varphi(m), m=1,...,n$ при $n \to \infty$ равна:

$D(n)=E[(\ln(m)-\ln \varphi(m))^2]=E[\ln^2 \frac {m}{\varphi(m)}]=$$E[\sum_{p|m}\ln^2 \frac {p}{p-1}]=E[\sum_{p|m}\ln^2 (1+1/(p-1))]$

$\sum_{p|m}\ln^2 (1+1/(p-1))=$$\sum_{p|m}(1/(p-1)^2+o(1/(p-1)^2) \leq \sum_{p \leq m} {1/(p-1)^2}=O(1)$

$D(n)=E[(\ln(m)-\ln \varphi(m))^2]=O(n)/n=O(1)$.

-- 10.11.2022, 12:03 --

RIP в сообщении #1569454 писал(а):

Но для $\ln\varphi(n)$ это не нужно: хватает матожидания и неравенства Маркова (если оценка вероятности не важна).

А как же оценка "почти всюду"?

-- 10.11.2022, 12:06 --

RIP в сообщении #1569412 писал(а):

Для «почти всех» $n$ можно улучшить до

$$n > \varphi(n) > \left(\mathrm{e}^{-\gamma}+o(1)\right)\frac{n}{\ln\ln\ln n} \iff 0 < \ln n-\ln\varphi(n) < \ln\ln\ln\ln n+\gamma+o(1)$$

А это откуда следует?

[RIP]

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

А как же оценка "почти всюду"?

Если $f(n)\geqslant0$ и $\frac{1}{N}\sum_{n=1}^{N}f(n)\leqslant C$, то количество слагаемых, больших $K>0$, не превосходит $\frac{CN}{K}$. Выбирая $K=K(N)\to+\infty$, получаем, что для «почти всех» $n$ выполнено $f(n)=O(g(n))$, где $g(n)$ — произвольная неограниченно растущая функция. Можно взять $f(n)=\ln n-\ln\varphi(n)$.

-- Чт 2022-11-10 12:34:50 --

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

А это откуда следует?

Я просто подставил $\omega(n)\sim\ln\ln n$ в предыдущее неравенство. Но эта оценка плохая. На самом деле $\varphi(n)\geqslant\dfrac{n}{h(n)}$ для сколь угодно медленно растущей $h(n)$ (при «почти всех» $n$).

[vicvolf]

RIP в сообщении #1569610 писал(а):

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

А как же оценка "почти всюду"?

Если $f(n)\geqslant0$ и $\frac{1}{N}\sum_{n=1}^{N}f(n)\leqslant C$, то количество слагаемых, больших $K>0$, не превосходит $\frac{CN}{K}$. Выбирая $K=K(N)\to+\infty$, получаем, что для «почти всех» $n$ выполнено $f(n)=O(g(n))$, где $g(n)$ — произвольная неограниченно растущая функция. Можно взять $f(n)=\ln n-\ln\varphi(n)$.

Если вспомнить. что $f(n)=|a(n)-E[a,n]|$, где а - арифметическая функция, а $E[a,n]$ - среднее значение а, то при выполнении $\frac{1}{N}\sum_{n=1}^{N}f(n)\leqslant C$ из неравенства Маркова следует, что "почти всюду" при $n \to \infty$ выполняется асимптотика: $a(n)=E[a,n]+O(g(n))$, где $g(n)$ - произвольная медленно растущая функция. В данном случае даже не требуется аддитивность арифметической функции а.

[vicvolf]

RIP

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

Для арифметической функции $\ln \varphi(n)$ значения: $A(n)=\ln(n)+O(1),D(n)=0,5\ln^2(n)+O(1)$

В монографии "Вероятностные методы теории чисел" https://docs.yandex.ru/docs/view?tm=166 ... 26nosw%3D1 на стр 91 приведена формула для дисперсии сильно аддитивной функции $B^2(n)=\sum_{p \leq n} \frac {f^2(p)}{p}$. На основании этой формулы определял эту дисперсию, а формула оказалась ошибочной. Это подтверждается на 93 стр., где ошибочно определяется, что $B(n) \sim \ln(n)/\sqrt{2}$ для аддитивной арифметической функции $f(m)=\ln(m)$.

Я смотрел также монографию Gérald Tenenbaum "Введение в теорию чисел" и там тоже неправильная формула для дисперсии аддитивной арифметической функции на стр 448 (3.10) и (3.11). Наверно дело в том, что формула эвристическая и основана, как сказано, на асимптотической независимости случайных величин для абстрактного вероятностного пространства. Вообщем я так и не нашел общей правильной формулы для определения дисперсии аддитивной арифметической функции. Может подскажите?

Сделал оценку сильно аддитивной функции:

$\sum_{p|n} \ln(\frac {p}{p-1})=\sum_{p|n} \ln (1+1/(p-1))=$$\sum_{p|n} 1/(p-1)+O(1/(p-1)^2)=\sum_{p|n} 1/(p-1)+O(1)$.

Далее, используя Вашу формулу:

$\sum_{p|n} \ln(\frac {p}{p-1})=\sum_{p|n} 1/(p-1)+O(1) \leq \sum_{p \leq \ln(n)}1/(p-1)+O(1)=$$\ln\ln\ln\ln(n)+O(1)$

Однако, оценка среднего значения сильно аддитивной функции $\sum_{p|n} \ln(\frac {p}{p-1})$ дает $O(1)$, поэтому если ее дисперсия также ограничена или является медленно растущей функцией, то оценка "почти всюду" не имеет нормального порядка относительно среднего.

Следовательно, в этом случае оценка "почти всюду" не состоятельна?

[RIP]

Согласно списку обозначений, равенство $B^2(n)=\sum_{p\leqslant n}\frac{\lvert f(p)\rvert^2}{p}$ является определением величины $B(n)$, так что $B(n)$ — это не дисперсия (но для определённого класса функций даёт хорошее приближение для дисперсии; $\ln\varphi(n)$ к этому классу не принадлежит).

Матожидание и дисперсия для произвольной арифметической функции определяются как $E_N(f)=\frac{1}{N}\sum_{n=1}^{N}f(n)$ и $D_N(f)=\frac{1}{N}\sum_{n=1}^{N}\left\lvert f(n)-E_N(f)\right\rvert^2=\frac{1}{N}\sum_{n=1}^{N}\left\lvert f(n)\right\rvert^2-\lvert E_N(f)\rvert^2$. По этим формулам и нужно считать. Для некоторых функций можно получить асимптотики, что в упомянутых книгах и делается.

-- Вс 2022-11-13 20:08:15 --

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

Следовательно, в этом случае оценка "почти всюду" не состоятельна?

Что значит «несостоятельна»? Она содержательна, поскольку даёт нетривиальный результат. Просто в данном случае не удаётся выделить главный член асимптотики, только оценку.

[vicvolf]

RIP в сообщении #1569933 писал(а):

Согласно списку обозначений, равенство $B^2(n)=\sum_{p\leqslant n}\frac{\lvert f(p)\rvert^2}{p}$ является определением величины $B(n)$, так что $B(n)$ — это не дисперсия (но для определённого класса функций даёт хорошее приближение для дисперсии; $\ln\varphi(n)$ к этому классу не принадлежит).

Это не только обозначение. Посмотрите Лемму 3.1а на стр. 59.

RIP в сообщении #1569933 писал(а):

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

Тогда надо говорить об области применения указанных формул.

[RIP]

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

Посмотрите Лемму 3.1а на стр. 59.

Посмотрел. В этой лемме $B(n)$ — это именно $\left(\sum_{p\leqslant n}\frac{\lvert f(p)\rvert^2}{p}\right)^{1/2}$. Лемма сформулирована только для сильно аддитивных функций. Равенство $=BnB^2(n)$ надо читать как $=O\bigl(nB^2(n)\bigr)$.

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

Тогда надо говорить об области применения указанных формул.

Так в книжке это делается.

[vicvolf]

RIP в сообщении #1570012 писал(а):

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

Посмотрите Лемму 3.1а на стр. 59.

Посмотрел. В этой лемме $B(n)$ — это именно $\left(\sum_{p\leqslant n}\frac{\lvert f(p)\rvert^2}{p}\right)^{1/2}$. Лемма сформулирована только для сильно аддитивных функций. Равенство $=BnB^2(n)$ надо читать как $=O\bigl(nB^2(n)\bigr)$.

Надо разделить на $n$ обе части и тогда слева будет стоять дисперсия произвольной комплекснозначной сильно аддитивной арифметической функции $f(m), m=1,...,n$, а справа $O(\sum_{p \leq n} \frac {|f(p)|^2}{p})$.

Аналогично на основании леммы 3.1 для произвольной комплекснозначной аддитивной арифметической функции $f(m), m=1,...,n$ (после деления обеих частей на $n$) дисперсия этой функции равна $O(\sum_{p^a \leq n} \frac {|f(p^a)|^2}{p^a})$.

[RIP]

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

Надо разделить на $n$ обе части и тогда слева будет стоять дисперсия

Не будет, поскольку $A(n)$ — это не настоящее матожидание, а лишь величина, которой в неравенстве типа неравенства Чебышёва можно заменить настоящее матожидание (которое в книге обозначается через $A_n$).
Смысл лемм 3.1 и 3.1а в том, что для аддитивных функций в неравенстве Чебышёва вместо настоящих матожидания $A_n$ и дисперсии $D_n$ можно использовать величины $A(n)$ и $D^2(n)$ ($B^2(n)$ для сильно аддитивных функций). Но из леммы 3.1 можно получить, что $A_n=A(n)+O\bigl(D(n)\bigr)$, $D_n=O\bigl(D^2(n)\bigr)$.

[vicvolf]

RIP в сообщении #1570032 писал(а):

Не будет, поскольку $A(n)$ — это не настоящее матожидание, а лишь величина, которой в неравенстве типа неравенства Чебышёва можно заменить настоящее матожидание (которое в книге обозначается через $A_n$).

Да, $A(n)$ - это асимптотика матожидания.

RIP в сообщении #1570032 писал(а):

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

Смысл лемм 3.1 и 3.1а в том, что для аддитивных функций в неравенстве Чебышёва вместо настоящих матожидания $A_n$ и дисперсии $D_n$ можно использовать величины $A(n)$ и $D^2(n)$ ($B^2(n)$ для сильно аддитивных функций).

Согласен, это утверждается для всякой комплекснозначной аддитивной (сильно аддитивной) арифметической функции в теоремах 3.1 и 3.1а на стр. 59.

Остается вопрос. Для аддитивной арифметической функции $f(m)=\ln(m),m=1,...,n$ получается $A(n) \sim \ln(n),D^2(n) \sim \ln^2(n)/2$ (стр. 93). Как это можно использовать в неравенстве типа Чебышева? Так как в этом случае "почти всюду" при $n \to \infty$ получим $\ln(n)=O(\ln^{1+\epsilon}(n))$.

[RIP]

Лемма 3.1 даёт оценку для дисперсии сверху (если учесть тождество $D_n+\lvert A_n-A(n)\rvert^2=\frac{1}{n}\sum_{m=1}^{n}\lvert f(m)-A(n)\rvert^2$). Конкретно для логарифма эта оценка слишком грубая. Настоящая дисперсия в этом случае $D_n=1+o(1)$, что проверяется непосредственным вычислением. То есть для некоторых аддитивных функций теорема 3.1 не даёт ничего нетривиального.

[vicvolf]

RIP в сообщении #1570072 писал(а):

То есть для некоторых аддитивных функций теорема 3.1 не даёт ничего нетривиального.

Да, именно это я и хотел сказать. Поэтому даже тривиальные экстремальные оценки, для некоторых аддитивных функций, могут оказаться лучше оценок "почти всюду".
Например, для сильно аддитивной функции выполняется оценка $f^*(n)=\sum_{p|n}\ln(p) \leq \ln(n)$, которая лучше оценки "почти всюду" $f^*(n)=O(\ln^{1+\epsilon}(n)})$.

[RIP]

Если не пользоваться готовыми результатами, а посчитать матожидание и дисперсию непосредственно, то получается $A_n=\frac{1}{n}\sum_{m=1}^{n}f^{*}(m)=\ln n+O(1)$, $D_n=\frac{1}{n}\sum_{m=1}^{n}\bigl(f^{*}(m)\bigr)^2-A_n^2=O(\ln n)$, если я не обсчитался (возможно, можно лучше, но тут уже придётся повозиться). Так что имеем оценку «почти всюду» $f(m)=\ln n+O\left((\ln n)^{1/2+\varepsilon}\right)$, $1\leqslant m\leqslant n$, причём оценка снизу нетривиальна. Хотя, как и для $\ln\varphi(n)$, из-за наличия тривиальной оценки $f^{*}(m)\leqslant\ln m\leqslant A_n+O(1)$ без рассмотрения дисперсии получается оценка «почти всюду» $f^{*}(m)=\ln n+O(g(n))$, $1\leqslant m\leqslant n$ (эквивалентно: $f^{*}(n)=\ln n+O(g(n))$) для произвольной неограниченно растущей $g(n)$.