Совпадение асимптотических оценок сверху

[vicvolf]

Меня интересует вопрос, в каких случаях совпадают асимптотические оценки сверху у функции натурального аргумента $f(n)$ и среднего значения этой функции на интервале $[1,n]$ - $E[f,n]$ ?

Один случай я нашел:

Пусть $f(n) \geq 0$, $f(n)$ - монотонно возрастает, тогда $E[f,n]=O(f(n))$.

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

Предположим, что $E[f,n]=O(g(n))$. Тогда $f(1)+...+f(n)=O(ng(n))$ или $f(1)+...+f(n) \leq Ang(n)$, где $A>0,f(n)\geq 0$.

Если $f(n)$ - монотонно возрастает, то $f(1)+...f(n) \leq nf(n)$. Поэтому взяв в качестве $A=1,g(n)=f(n)$ получим: $f(1)+...+f(n)=O(nf(n))$ или $E[f,n]=O(f(n))$.

Имеются ли другие случаи совпадения указанных асимптотических оценок сверху?

[Brukvalub]

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

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

Предположим, что $E[f,n]=O(g(n))$. Тогда $f(1)+...+f(n)=O(ng(n))$ или $f(1)+...+f(n) \leq Ang(n)$, где $A>0,f(n)\geq 0$.

Если $f(n)$ - монотонно возрастает, то $f(1)+...f(n) \leq nf(n)$. Поэтому взяв в качестве $A=1,g(n)=f(n)$ получим: $f(1)+...+f(n)=O(nf(n))$ или $E[f,n]=O(f(n))$.

Давненько таких перлов не встречал! Здесь все феерично, но особенно хороша вишенка на торте в виде деЦкой логической ошибки "если предположить, что А верно и "доказать", что из А следует В, а потом проверить, что В - верно, то верно и А"
Это не просто ужас, а ужас-ужас, ужас!!!

[Утундрий]

(Оффтоп)

Напомнило "женскую логику по Колмогорову", использующую всего два правила:

1. Если из $A$ следует $B$ и $B$ приятно, то $A$ истинно.
2. Если известно, что $A$ ложно, но из $A$ следует $B$ и $B$ приятно, то $A$ всё-таки истинно.

[vicvolf]

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

Меня интересует вопрос, в каких случаях совпадают асимптотические оценки сверху у функции натурального аргумента $f(n)$ и среднего значения этой функции на интервале $[1,n]$ - $E[f,n]$ ?

Может ли кто-нибудь ответить на этот конкретный вопрос? Или есть только желающие поюморить. Для этих целей есть другой раздел, а не ПРР.

[Brukvalub]

(Оффтоп)

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

Или есть только желающие поюморить.

Какой уж тут юмор, если ТС не понимает тривиальных законов логики.

[Lia]

vicvolf
Изложите текст связно, пожалуйста. И с обоснованными логическими переходами. И с пояснением по обозначениям. Что такое $g(n)$, например, мне не удается найти следов.

[DeBill]

Ну чё вы так сразу....
ТС совершенно верно выписал очевидную оценку (для монотонной функции) $E[f,n]\leqslant f(n), $ что и дает $E[f,n]=O(f(n))$ - а всю прочую шелуху убрать надо, да.
Однако средние (для монотонных) таки могут расти медленней самой функции (пример: $f(n)=2^n$: здесь $\frac{E[f,n]}{f(n)}\sim \frac{2}{n}$).
Можно, видимо, подобрать функции и с любым промежуточным ростом отношения.
Для немонотонных (или убывающих) - наоборот, средние могут быть круче самой функции - и тут тоже можно подобрать все что хочешь (в разумных пределах)

[Brukvalub]

(Оффтоп)

DeBill в сообщении #1464686 писал(а):

ТС совершенно верно выписал очевидную оценку (для монотонной функции) $E[f,n]\leqslant f(n), $ что и дает $E[f,n]=O(f(n))$ - а всю прочую шелуху убрать надо, да.

Как раз это - самое прикольное! Тривиальный, самоочевидный факт "доказан" с вопиющими логическими ошибками! И так каждый раз: очевидные вещи ТС выдает за "открытия" и, безбожно путаясь, "доказывает" их, генерируя многостраничные опусы, которые давно уже никто и не читает.

[vicvolf]

DeBill в сообщении #1464686 писал(а):

ТС совершенно верно выписал очевидную оценку (для монотонной функции) $E[f,n]\leqslant f(n), $ что и дает $E[f,n]=O(f(n))$

Большое спасибо за конкретный ответ.

Цитата:

Однако средние (для монотонных) таки могут расти медленней самой функции

Следовательно, в этом случае $E[f,n]=O(f(n))$.

Цитата:

Для немонотонных (или убывающих) - наоборот, средние могут быть круче самой функции

Поэтому в этом случае, если $E[f,n]=O(g(n))$, то $f(n)=O(g(n))$. Этот случай обобщается и на первый.

Brukvalub в сообщении #1464688 писал(а):

каждый раз: очевидные вещи ТС выдает за "открытия" и, безбожно путаясь, "доказывает" их, генерируя многостраничные опусы, которые давно уже никто и не читает.

Я любитель и имею право на ошибку в отличие от профессионалов.

[mihaild]

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

Поэтому в этом случае, если $E[f,n]=O(g(n))$, то $f(n)=O(g(n))$. Этот случай обобщается и на первый.

По-русски это пишется так: $f(n) = O(E[f, n])$. И выше есть контрпример: $f(n) = 2^n$, $g(n) = \frac{2^n}{n}$.
Для немонотонных $\frac{f(n)}{E[f, n]}$ может гулять почти как угодно. Для монотонных эта дробь очевидно где-то в отрезке $[1, n]$.

[vicvolf]

mihaild Большое спасибо. Помогите разобраться c частным случаем.

Пусть $f(p)$ некоторая функция простого аргумента $p$. Ранее мною выдвигалась гипотеза, что:

$\sum_{p \leq n} {f(p)}=\sum_{k=2}^n {f(k)/log(k)(1+o(1))$. (1)

Какие требования должны предъявляться к функции $f$, чтобы выполнялась асимптотика (1)?

Немного поясню. Понятно, что $f(p)=f(n)$, если $n=p$ и $f(p)=0$ в противном случае.

Ранее в другом теме я показал, что вероятность натурального числа из интервала $[2,n)$ быть простым равна $1/\log(n)(1+o(1))$, поэтому среднее значение функции $f(p)$ на интервале $[2.n)$ - $E[f(p),n]=f(n)/\log(n)(1+o(1))$.

Следовательно вопрос сводится к тому, при какой $f$ совпадают асимптотики $f(p)$ и $E[f(p),n]$?

Мой ответ: функция $f$ должна быть монотонна и иметь следующую оценку сверху $f(n)=O(n^l \log(n))$.

Это подтверждают следующие примеры:


$\sum_{p \leq n} {1/p} = \sum_{k=2}^n {\frac {1} {k \log(k)} (1+o(1))}}=\log\log(n)(1+o(1))$. (2)

$\sum_{p \leq n} {\log(p)} = \sum_{k=2}^n \frac {\log(k)} {\log(k)}(1+o(1))}=n(1+o(1))$. (3)

$\sum_{p \leq n}{\frac {log(p)} {p}}=\sum_{k=2}^n {\frac {\log(k)} {k\log(k)}(1+o(1))}=\log(n)(1+o(1))$. (4)

Результаты (2), (3) и (4) соответствуют формулам монографий Прахара и Бухштаба.

На основании (1) можно также получить другие асимптотические оценки:

$\sum_{p \leq n} {p^l \log(p)} =\sum_{k=2}^n {\frac {k^llog(k)} {\log(k)}}= \frac {n^{l+1}} {l+1}(1+o(1))$, (5)

где $l \geq 0$. Формула (5) обобщает (3).

[Lia]

vicvolf
Предупреждение за дублирование сообщения почти полностью.

Продолжайте там.

[Modest]

Тема временно открыта на случай, если участники заходят ответить.

vicvolf, при дальнейшем дублировании сообщений будут закрыты обе темы.