2014 dxdy logo

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

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


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


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



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


23/02/12
3187
Как оценить сумму $\sum_{p|n}f(p)$, где $p$ - простое число?

Оценка суммы $\sum_{p|n}f(p) \leq \sum_{p \leq n} f(p)$ является грубой.

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение05.11.2022, 23:51 
Заслуженный участник


03/01/09
1686
москва
$\sum \limits _{p|n}f(p)\leq d(n)f(n)$, где $d(n)$- число делителей $n$.

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение06.11.2022, 00:05 
Аватара пользователя


07/01/16
1444
Аязьма
Но это же очень зависит от $f()$, нет? Можно подобрать примеры, когда обе представленные в топике оценки не будут верны

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение06.11.2022, 00:23 
Заслуженный участник


03/01/09
1686
москва
waxtep
Да, оценка не универсальная, но в некоторых случаях может быть лучше, чем сумма по всем $p<n$.

 Профиль  
                  
 
 Re: Асимптотическая оценка суммы
Сообщение06.11.2022, 14:59 
Заслуженный участник


03/01/09
1686
москва
mihiv в сообщении #1569063 писал(а):
$\sum \limits _{p|n}f(p)\leq d(n)f(n)$

Должно быть:$\sum \limits _{p|n}f(p)\leq d(n)\cdot \max \limits _{x\in [2,n]}f(x)$

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


23/02/12
3187
mihiv в сообщении #1569110 писал(а):
mihiv в сообщении #1569063 писал(а):
$\sum \limits _{p|n}f(p)\leq d(n)f(n)$
Должно быть:$\sum \limits _{p|n}f(p)\leq d(n)\cdot \max \limits _{x\in [2,n]}f(x)$

Спасибо, наверно точнее $\sum \limits _{p|n}f(p)\leq \omega(n)\cdot \max \limits _{x\in [2,n]}f(x)$

Например, $\sum_{p|n}\Omega(p) \leq (\omega(n))^2 \sim (\ln\ln n)^2$

Хотя можно точнее $\sum_{p|n}\Omega(p) \leq \Omega(n) \sim \ln\ln n$
waxtep в сообщении #1569064 писал(а):
Но это же очень зависит от $f()$, нет?
Конечно. Если наложить дополнительные требования, что $f$ аддитивная арифметическая функция и $f(p^\alpha) \geq f(p)$, то можно доказать, что $\sum_{p|n}f(p) \leq f(n)$. Пример приведен выше.

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


11/01/06
3822
vicvolf в сообщении #1569154 писал(а):
Например, $\sum_{p|n}\Omega(p) \leq (\omega(n))^2 \sim (\ln\ln n)^2$

Хотя можно точнее $\sum_{p|n}\Omega(p) \leq \Omega(n) \sim \ln\ln n$
Можно ещё точнее: $\sum_{p|n}\Omega(p)=\omega(n)$. Только правильные оценки — $\Omega(n)=O(\ln n)$ и $\omega(n)=O\left(\frac{\ln n}{\ln\ln n}\right)$; $\ln\ln n$ — это только для «почти всех» $n$.

Если функция $f$ убывает, бывает полезна оценка $\sum_{p|n}f(p)\leqslant\sum_{p\leqslant p_{\omega(n)}}f(p)$ (где $p_k$ — $k$-е простое число) вместе с оценкой $p_{\omega(n)}\leqslant(1+o(1))\ln n$ (обе оценки достигаются при $n=p_1p_2\dotsm p_m$).

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


23/02/12
3187
RIP в сообщении #1569212 писал(а):
Можно ещё точнее: $\sum_{p|n}\Omega(p)=\omega(n)$.
Здесь справа и слева стоит одна и таже сильно аддитивная функция $\omega(n)$, поэтому равенство.
Цитата:
Только правильные оценки — $\Omega(n)=O(\ln n)$ и $\omega(n)=O\left(\frac{\ln n}{\ln\ln n}\right)$
Спасибо, за оценки. Они соответствуют $\omega(n)=\sum_{p|n}\Omega(p) \leq \Omega(n)$
Цитата:
Если функция $f$ убывает, бывает полезна оценка $\sum_{p|n}f(p)\leqslant\sum_{p\leqslant p_{\omega(n)}}f(p)$ (где $p_k$ — $k$-е простое число) вместе с оценкой $p_{\omega(n)}\leqslant(1+o(1))\ln n$ (обе оценки достигаются при $n=p_1p_2\dotsm p_m$).
А эта оценка не получается. Не докажите?

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


11/01/06
3822
vicvolf в сообщении #1569229 писал(а):
RIP в сообщении #1569212 писал(а):
Можно ещё точнее: $\sum_{p|n}\Omega(p)=\omega(n)$.
Здесь справа и слева стоит одна и та же сильно аддитивная функция $\omega(n)$, поэтому равенство.
Да просто по определению $\Omega(n)$ и $\omega(n)$:
$$\sum_{p|n}\Omega(p)=\sum_{p|n}1=\omega(n).$$
vicvolf в сообщении #1569229 писал(а):
Цитата:
Если функция $f$ убывает, бывает полезна оценка $\sum_{p|n}f(p)\leqslant\sum_{p\leqslant p_{\omega(n)}}f(p)$ (где $p_k$ — $k$-е простое число) вместе с оценкой $p_{\omega(n)}\leqslant(1+o(1))\ln n$ (обе оценки достигаются при $n=p_1p_2\dotsm p_m$).
А эта оценка не получается. Не докажете?
Вторая оценка? Она следует из тривиального неравенства
$$\ln n\geqslant\ln\prod_{p\leqslant p_{\omega(n)}}p=\sum_{p\leqslant p_{\omega(n)}}\ln p=\theta\bigl(p_{\omega(n)}\bigr)$$
(где $\theta(x)$ — тета-функция Чебышёва) и асимптотического закона распределения простых чисел в виде $\theta(x)\sim x$ при $x\to+\infty$.

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


23/02/12
3187
RIP в сообщении #1569243 писал(а):
Вторая оценка? Она следует из тривиального неравенства
$$\ln n\geqslant\ln\prod_{p\leqslant p_{\omega(n)}}p=\sum_{p\leqslant p_{\omega(n)}}\ln p=\theta\bigl(p_{\omega(n)}\bigr)$$
(где $\theta(x)$ — тета-функция Чебышёва) и асимптотического закона распределения простых чисел в виде $\theta(x)\sim x$ при $x\to+\infty$.
А какое отношение к этому имеет убывающая функция $f$?

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


11/01/06
3822
vicvolf в сообщении #1569274 писал(а):
А какое отношение к этому имеет убывающая функция $f$?
Никакого. Если Вас интересует оценка $\sum_{p|n}f(p)\leqslant\sum_{p\leqslant p_{\omega(n)}}f(p)$, то она тривиальна: в обеих суммах одинаковое кол-во слагаемых, но слагаемые в правой сумме больше.

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


23/02/12
3187
RIP в сообщении #1569212 писал(а):
Только правильные оценки — $\Omega(n)=O(\ln n)$ и $\omega(n)=O\left(\frac{\ln n}{\ln\ln n}\right)$; $\ln\ln n$ — это только для «почти всех» $n$.
Теперь в отношении асимптотических оценок «почти всюду» для арифметических функций.
Рассмотрим аддитивную арифметическую функцию $\ln \varphi(n)$.
Так как $\varphi(n) \leq n$, то $\ln \varphi(n) \leq \ln(n)$. (1)
Известно, что для любой арифметической функции $f$ выполняется следующая асимптотическая оценка «почти всюду» при $n \to \infty$:
$f(n)=A(n)+O(b(n)\sqrt{D(n)})$, (2)
где $A(n),D(n)$ - соответственно асимптотики среднего значения и дисперсии арифметической функции $f$, а $b(n)$ - медленно растущая функция.
Для арифметической функции $\ln \varphi(n)$ значения: $A(n)=\ln(n)+O(1),D(n)=0,5\ln^2(n)+O(1)$, подставим их в (2) и получим, что «почти всюду» при $n \to \infty$:
$\ln \varphi(n)=\ln(n)+O(\ln^{1+\epsilon}(n))=O(\ln^{1+\epsilon}(n))$, (3) где $b(n)=\ln^{\epsilon}(n)$.
Как можно использовать оценку (3) при наличии (1)?
Делаю вывод, что оценки (2) можно использовать, если $f$ - имеет только нормальный порядок относительно своего среднего значения, например для $\omega(n),\Omega(n)$, что можно обобщить по теореме Турана. Ваше мнение?

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


11/01/06
3822
vicvolf в сообщении #1569368 писал(а):
Как можно использовать оценку (3) при наличии (1)?
Никак: оценка (3) бессодержательна (хуже тривиальной).

Конкретно для функции Эйлера известна оценка снизу вида
$$\varphi(n) > \mathrm{e}^{-\gamma} \frac{n}{\ln p_{\omega(n)}+\textnormal{мелочь}}
= \mathrm{e}^{-\gamma} \frac{n}{\ln\omega(n)+\ln\ln\omega(n)+\textnormal{мелочь}}$$
(где $\gamma$ — постоянная Эйлера–Маскерони). Отсюда при $n\to\infty$ следует
$$n > \varphi(n) > \left(\mathrm{e}^{-\gamma}+o(1)\right)\frac{n}{\ln\ln n} \iff 0 < \ln n-\ln\varphi(n) < \ln\ln\ln n+\gamma+o(1)$$
(причём последняя оценка достигается, например, для $n=p_1p_2\dotsm p_m$). Для «почти всех» $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)$$
но я не знаю, каково «правильное» поведение в этом случае.

vicvolf в сообщении #1569368 писал(а):
Ваше мнение?
Никакого мнения не имею.

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


11/01/06
3822
RIP в сообщении #1569412 писал(а):
Для «почти всех» $n$ можно улучшить
Можно лучше:
$$\sum_{n\leqslant x}\ln\frac{n}{\varphi(n)}=\sum_{n\leqslant x}\sum_{p|n}-\ln\left(1-\frac{1}{p}\right)=\sum_{p\leqslant x}-\ln\left(1-\frac{1}{p}\right)\left\lfloor\frac{x}{p}\right\rfloor\leqslant Ax,$$
где $A=\sum_{p}-\frac{1}{p}\ln\left(1-\frac{1}{p}\right)$, так что
$$\#\left\{n\leqslant x : \ln n-\ln\varphi(n)\geqslant\lambda\right\}\leqslant\frac{Ax}{\lambda},$$
т.е. функция $\ln n-\ln\varphi(n)$ ограничена «в среднем», поэтому для «почти всех» $n$ её можно ограничить сколь угодно медленно растущей функцией.

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


11/01/06
3822
Можно (даже лучше) и без логарифмов:
\begin{gather*}
\sum_{n\leqslant x}\frac{n}{\varphi(n)}=\sum_{n\leqslant x}\sum_{d|n}\frac{\mu^2(d)}{\varphi(d)}=\sum_{d\leqslant x}\frac{\mu^2(d)}{\varphi(d)}\left\lfloor\frac{x}{d}\right\rfloor\leqslant Bx,\qquad B=\sum_{n=1}^{\infty}\frac{\mu^2(n)}{n\varphi(n)}=\frac{\zeta(2)\zeta(3)}{\zeta(6)},\\
\intertext{поэтому}
\#\left\{n\leqslant x : \varphi(n)\leqslant\frac{n}{T}\right\}\leqslant\frac{Bx}{T}.
\end{gather*}

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

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



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

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


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

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