Тождество с пси-функцией Чебышева [Теория чисел]

[Whitaker]

Здравствуйте, уважаемые друзья!

Пусть $x>0$ и $p\in \mathbb{P}$ (множество простых чисел), то так определяются тэта и пси-функции Чебышева:

$$\theta(x)=\sum \limits_{p\leqslant x}\ln p$$

$$\psi(x)=\sum \limits_{p^m\leqslant x}\ln p$$

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

$$\psi(x)=\sum\limits_{p\leqslant x}\left[\dfrac{\ln x}{\ln p}\right]\ln p=\sum \limits_{m\geqslant 1}\theta(x^{\frac{1}{m}})$$

Доказать, что при $n\geqslant 2$ верно равенство:

$$\ln([n]!)=\sum \limits_{k\geqslant 1}\psi\left(\dfrac{n}{k}\right)$$

Доказательство: Так как

$$[n]!=\prod \limits_{p\leqslant n}p^{\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\dots}$$

Логарифмируя его мы получим:

$$\ln([n]!)=\sum \limits_{p \leqslant n}\left(\left[\dfrac{n}{p}\right]+\left[\dfrac{n}{p^2}\right]+\dots\right)\ln p$$

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

С уважением, Whitaker.

[nnosipov]

Займитесь теперь преобразованием суммы $\sum \limits_{k\geqslant 1}\psi\left(\dfrac{n}{k}\right)$.

[Whitaker]

nnosipov
Вроде получил следующее:

$$\sum \limits_{k\geqslant 1}\psi\left(\dfrac{n}{k}\right)=\sum \limits_{k \geqslant 1}\sum \limits_{s \geqslant 1}\theta\left( \sqrt[s]{n \over k}\right)=\sum \limits_{k \geqslant 1}\sum \limits_{s \geqslant 1}\sum \limits_{p\leqslant \sqrt[s] {n \over k}}\ln p=\sum \limits_{p\leqslant n}\ln p \sum \limits_{s \geqslant 1}\sum \limits_{1 \leqslant k \leqslant \frac{n}{p^s}}1=$$$$=\sum \limits_{p\leqslant n}\ln p \sum \limits_{s \geqslant 1}\left [ \dfrac{n}{p^s}\right]=\sum \limits_{p\leqslant n}\ln p \left(\left[\dfrac{n}{p}\right]+\left[\dfrac{n}{p^2}\right]+\dots\right)$$

Вроде смахивает на правду. Верно?

[nnosipov]

Да, всё хоккей.

[Whitaker]

nnosipov
Спасибо Вам за подсказку!

[Whitaker]

nnosipov
можно спросить у Вас такой вопрос?
Я доказал, что $\psi(n)<2n$ при $n\geqslant 2$ ($n$ может быть и не целым и хотя есть более лучшие оценки для пси-функции Чебышева, но и эта тоже сгодится)
Отсюда нужно вывести, что

$$\theta(\sqrt[s]{n})-\theta\left(\sqrt[s]{n\over 2}\right)+\theta\left(\sqrt[s]{n\over 3}\right)-\theta\left(\sqrt[s]{n\over 4}\right)+\dots<2\sqrt[s]{n}$$

Я вроде так сделал: запишем наше выражение так:

$$\sum \limits_{k\geqslant 1}(-1)^{k-1}\theta\left(\sqrt[s]{n\over k} \right)=\sum \limits_{k\geqslant 1}(-1)^{k-1}\sum \limits_{p\leqslant \sqrt[s]{\frac{n}{k}\right)}}\ln p=\sum \limits_{p\leqslant \sqrt[s]{n}}\ln p\sum \limits_{1\leqslant k \leqslant \frac{n}{p^s}}(-1)^{k-1}\leqslant \sum \limits_{p\leqslant \sqrt[s]{n}}\ln p\cdot 1\leqslant$$

$$\leqslant \sum \limits_{p\leqslant \sqrt[s]{n}}\ln p \left[\frac{\ln \sqrt[s]{n}}{\ln p} \right]=\psi(\sqrt[s]{n})<2\sqrt[s]{n}$$

Верно?

[Whitaker]

Процитирую книгу И.М. Виноградова "Основы ТЧ" (страница 117, решение к задаче 9, a $\gamma$) из главы II)

Цитата:

$$0\leqslant \psi(n)-\psi\left(\dfrac{n}{2}\right)+\psi\left(\dfrac{n}{3}\right)-\psi\left(\dfrac{n}{4}\right)+\dots-\left(\theta\left(n\right)-\theta\left(\dfrac{n}{2}\right)+\theta\left(\dfrac{n}{3}\right)-\theta\left(\dfrac{n}{4}\right)+\dots\right)<$$

$$<2\sqrt{n}+2\sqrt[3]{n}+2\sqrt[4]{n}+\dots+2\sqrt[\tau]{n}<2(\sqrt{n}+\tau\sqrt[3]{n})=O(\sqrt{n})$$

Вот давайте обозначим левую функцию через $f(n)$ и получаем, что $f(n)<O(\sqrt{n})$. Что-то не могу понять смысл этой записи?
Ведь $O(\sqrt{n})$ класс функций. Как некоторая функция $f(n)$ может быть "меньше" класса функций? Или я чего-то не догоняю. Объясните пожалуйста

[Sonic86]

Whitaker в сообщении #648104 писал(а):

$f(n)<O(\sqrt{n})$

Наверное, это означает $f(n)=o(\sqrt{n})$. А может и $f(n)=O(\sqrt{n})$. Если это Ваше обозначение, то правильно тогда писать $f(n)=O(\sqrt{n})$ (т.е. $f(n)<C\sqrt{n}\Rightarrow f(n)=O(\sqrt{n})$).
А $2\sqrt{n}+2\sqrt[3]{n}+2\sqrt[4]{n}+\dots+2\sqrt[\tau]{n}=O(\sqrt{n})$

[Whitaker]

Sonic86
Ну то, что $2\sqrt{n}+2\sqrt[3]{n}+2\sqrt[4]{n}+\dots+2\sqrt[\tau]{n}=O(\sqrt{n})$ это мне понятно.
А что он подразумевает под записью $f(n)<O(\sqrt{n})$ вообще непонятно.
P.S. Если Вам интересно, то можетt посмотреть это задача из второй главы под номером 9a пункт $\gamma$
P.P.S. Вообще он пишет, что $f(n)<O(\sqrt{n})$. Но ведь это запись, как мне кажется, не имеет никакого смысла.

[Sonic86]

Whitaker в сообщении #648120 писал(а):

А что он подразумевает под записью $f(n)<O(\sqrt{n})$ вообще непонятно.

Думаю, что $f(n)<C\sqrt{n}$ для некоторого $C$, т.е. $f(n)=O(\sqrt{n})$.

[Whitaker]

Sonic86
Я вроде тут немного подумал и кажется я понял, что он имел ввиду.
Для краткости изложения введем такие замены:

$$f(n)=\psi(n)-\psi\left(\dfrac{n}{2}\right)+\psi\left(\dfrac{n}{3}\right)-\psi\left(\dfrac{n}{4}\right)+\dots$$

$$g(n)=\theta\left(n\right)-\theta\left(\dfrac{n}{2}\right)+\theta\left(\dfrac{n}{3}\right)-\theta\left(\dfrac{n}{4}\right)+\dots$$

Мы имеем такое неравенство:

$$0\leqslant f(n)-g(n)<2\sqrt{n}+2\sqrt[3]{n}+2\sqrt[4]{n}+\dots+2\sqrt[\tau]{n}<2(\tau-1)\sqrt{n}=K\sqrt{n}$$

Получаем, что: $f(n)-g(n)=O(\sqrt{n})$ и также нетрудно показать, что $f(n)=n\ln 2+O(\ln n)$. Получаем, что $g(n)=n\ln 2+O(\ln n)+O(\sqrt{n})=n\ln 2+O(\sqrt{n})$.
Приходим к тому, что

$$\Theta\left(n, \frac{n}{2}\right)+\Theta\left(\frac{n}{3}, \frac{n}{4}\right)+\Theta\left(\frac{n}{5}, \frac{n}{6}\right)+\dots=n\ln 2+O(\sqrt{n}),$$

где $\Theta(z, z_0)=\sum \limits_{z_0<p\leqslant z}\ln p=\theta(z)-\theta(z_0)$
Ну вот вроде и все

[Sonic86]

Вроде похоже на правду.

[nnosipov]

Whitaker в сообщении #648020 писал(а):

nnosipov
можно спросить у Вас такой вопрос? ... Верно?

Верно.