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

[vicvolf]

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

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

[mihiv]

$\sum \limits _{p|n}f(p)\leq d(n)f(n)$, где $d(n)$- число делителей $n$.

[waxtep]

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

[mihiv]

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

[mihiv]

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)$

[vicvolf]

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)$. Пример приведен выше.

[RIP]

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$).

[vicvolf]

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$).

А эта оценка не получается. Не докажите?

[RIP]

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$.

[vicvolf]

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$?

[RIP]

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

А какое отношение к этому имеет убывающая функция $f$?

Никакого. Если Вас интересует оценка $\sum_{p|n}f(p)\leqslant\sum_{p\leqslant p_{\omega(n)}}f(p)$, то она тривиальна: в обеих суммах одинаковое кол-во слагаемых, но слагаемые в правой сумме больше.

[vicvolf]

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)$, что можно обобщить по теореме Турана. Ваше мнение?

[RIP]

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 писал(а):

Ваше мнение?

Никакого мнения не имею.

[RIP]

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$ её можно ограничить сколь угодно медленно растущей функцией.

[RIP]

Можно (даже лучше) и без логарифмов:
\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*}