2014 dxdy logo

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

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


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


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



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


23/02/12
3110
Как оценить сумму $\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
1677
москва
$\sum \limits _{p|n}f(p)\leq d(n)f(n)$, где $d(n)$- число делителей $n$.

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


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

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


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

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


03/01/09
1677
москва
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
3110
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
3110
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
3110
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
3110
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  След.

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



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

Сейчас этот форум просматривают: Gg322


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

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