2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 Re: Асимптотическая оценка суммы
Сообщение09.11.2022, 10:35 


23/02/12
3147
RIP
Вы согласны с формулой (2)?

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение09.11.2022, 13:40 
Заслуженный участник
Аватара пользователя


11/01/06
3822
vicvolf в сообщении #1569431 писал(а):
Вы согласны с формулой (2)?
Если её внятно сформулировать, то да: это фактически неравенство Чебышёва.
Кстати, дисперсию для $\ln\varphi(n)$ Вы неправильно посчитали. По-моему, $D(n)=O(1)$ (либо растёт очень медленно, лень аккуратно считать). Но для $\ln\varphi(n)$ это не нужно: хватает матожидания и неравенства Маркова (если оценка вероятности не важна).

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение10.11.2022, 11:11 


23/02/12
3147
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)$$
А это откуда следует?

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение10.11.2022, 12:29 
Заслуженный участник
Аватара пользователя


11/01/06
3822
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$).

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение11.11.2022, 09:49 


23/02/12
3147
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)$ - произвольная медленно растущая функция. В данном случае даже не требуется аддитивность арифметической функции а.

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение13.11.2022, 18:19 


23/02/12
3147
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)$, поэтому если ее дисперсия также ограничена или является медленно растущей функцией, то оценка "почти всюду" не имеет нормального порядка относительно среднего.

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

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение13.11.2022, 20:03 
Заслуженный участник
Аватара пользователя


11/01/06
3822
Согласно списку обозначений, равенство $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 писал(а):
Следовательно, в этом случае оценка "почти всюду" не состоятельна?
Что значит «несостоятельна»? Она содержательна, поскольку даёт нетривиальный результат. Просто в данном случае не удаётся выделить главный член асимптотики, только оценку.

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение14.11.2022, 09:37 


23/02/12
3147
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 писал(а):
Для некоторых функций можно получить асимптотики, что в упомянутых книгах и делается.
Тогда надо говорить об области применения указанных формул.

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение14.11.2022, 18:13 
Заслуженный участник
Аватара пользователя


11/01/06
3822
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 писал(а):
Тогда надо говорить об области применения указанных формул.
Так в книжке это делается.

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение14.11.2022, 20:58 


23/02/12
3147
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})$.

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение14.11.2022, 21:32 
Заслуженный участник
Аватара пользователя


11/01/06
3822
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)$.

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение15.11.2022, 10:35 


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

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение15.11.2022, 16:25 
Заслуженный участник
Аватара пользователя


11/01/06
3822
Лемма 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 не даёт ничего нетривиального.

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение15.11.2022, 18:48 


23/02/12
3147
RIP в сообщении #1570072 писал(а):
То есть для некоторых аддитивных функций теорема 3.1 не даёт ничего нетривиального.
Да, именно это я и хотел сказать. Поэтому даже тривиальные экстремальные оценки, для некоторых аддитивных функций, могут оказаться лучше оценок "почти всюду".
Например, для сильно аддитивной функции выполняется оценка $f^*(n)=\sum_{p|n}\ln(p) \leq \ln(n)$, которая лучше оценки "почти всюду" $f^*(n)=O(\ln^{1+\epsilon}(n)})$.

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение15.11.2022, 21:09 
Заслуженный участник
Аватара пользователя


11/01/06
3822
Если не пользоваться готовыми результатами, а посчитать матожидание и дисперсию непосредственно, то получается $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)$.

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

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



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

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


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

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