log+log(log)+log(log(log))+...

[henselstep]

Hi
Ich hänge seit einiger Zeit an folgendem Problem:
Man betrachte die folgende Summe:
log(x)+log(log(x))+log(log(log(x)))+..., wobei ich nur solange aufsummiere, solange die Terme größer 0 sind.
Ich bin mir ziemlich sicher, dass dieses Biest in O(log) sein muss, aber ich bekomme es ums Verrecken nicht gezeigt. Die beste Einordnung, die ich fand ist bisher O(log^2). Irre ich mich oder wie kann man das zeigen?

[Martin Vaeth]

henselstep <hense...@gmail.com> schrieb:
> log(x)+log(log(x))+log(log(log(x)))+...
> O(log)

Modulo Rechenfehler:

Lemma:
Für $q\in(0,1)$ genügend nahe bei $1$ ist $\log(x) \le x^q$ für
alle $x>0$.

(Beweis: Setze $f_q(x) = \log(x)-x^q$.
Für große $x$ ist die Ableitung $f_q'(x) = 1/x - qx^{q-1}$ negativ,
und die einzige Nullstelle ist bei $q^{-1/q}$. Also liegt das
Maximum von $f_q$ dort: $f(q^{-1/q})=1/q(\log(1/q) - 1)$.
Für $q->1$ geht dieser Ausdruck nach $-1$.)

Der Ausdruck lässt sich nun abschätzen durch:
\log(x) + \log(x^q) + \log((x^q)^q) + ... =
\log(x) + q \log(x) + q^2 \log(x) + ... \le
\log(x)/(1-q)

[Carlo XYZ]

Am 06.01.18 um 09:15 schrieb Martin Vaeth:

Soll hier q von x abhängen oder nicht?

Falls ja, ist die Ableitung tatsächlich wie oben berechenbar?

Falls nein, ist q dann einfach eine konkrete Zahl nahe 1?
Lässt sich so eine direkt angeben?

[Detlef Müller]

Am 08.01.2018 um 16:29 schrieb Carlo XYZ:
> Am 06.01.18 um 09:15 schrieb Martin Vaeth:
>> henselstep <hense...@gmail.com> schrieb:
>>> log(x)+log(log(x))+log(log(log(x)))+...
>>> O(log)

[...]

>> Lemma:
>> Für $q\in(0,1)$ genügend nahe bei $1$ ist $\log(x) \le x^q$ für
>> alle $x>0$.

>> (Beweis: Setze $f_q(x) = \log(x)-x^q$.
>> Für große $x$ ist die Ableitung $f_q'(x) = 1/x - qx^{q-1}$ negativ,
>> und die einzige Nullstelle ist bei $q^{-1/q}$. Also liegt das
>> Maximum von $f_q$ dort: $f(q^{-1/q})=1/q(\log(1/q) - 1)$.
>> Für $q->1$ geht dieser Ausdruck nach $-1$.)

[...]

>> Der Ausdruck lässt sich nun abschätzen durch:
>> \log(x) + \log(x^q) + \log((x^q)^q) + ... =
>> \log(x) + q \log(x) + q^2 \log(x) + ... \le
>> \log(x)/(1-q)

> Soll hier q von x abhängen oder nicht?

Im "Lemma" hat Martin nur q hinreichend groß (z.B. 0.5
reicht, das Maximum f_q ist für q>1/e negativ) angenommen.

> Falls ja, ist die Ableitung tatsächlich wie oben berechenbar?

Die Ableitung kommt ja nur im Lemma vor, insofern wäre
es nicht einmal problematisch, wenn q von x abhinge, solange
es nur hinreichend groß ist.
Wenn die Aussage für allgemeines q>0.5 gezeigt ist, gilt sie
auch für q(x)=(0.5+1/x^2).

> Falls nein, ist q dann einfach eine konkrete Zahl nahe 1?
> Lässt sich so eine direkt angeben?

für den konstanten Faktor in der O-Abschätzung
log(x) <= C * f(x) möchte man ja das C möglichst klein
halten, also q in C = 1/(1-q) möglichst klein, q muß
>= 1/e damit das Minimum noch <=0 ist.
Für q=1/e wird das Minimum 0 von ln(x)-x^q bei x=e^e angenommen,
aus der verwendeten Methode lässt sich also
C<=1/(1-1/e)
abschätzen, etwa 1.582.

Dabei wurde noch nicht verwendet, daß in der O-Notation ja
nur große x interessieren ...

Gruß,
Detlef

--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de

[Carlo XYZ]

Am 09.01.18 um 13:58 schrieb Detlef Müller:

Zumindest wenn x>=2; ich bin zu faul, sie für x=1 nachzuprüfen.

>> Falls nein, ist q dann einfach eine konkrete Zahl nahe 1?
>> Lässt sich so eine direkt angeben?
>
> für den konstanten Faktor in der O-Abschätzung
> log(x) <= C * f(x) möchte man ja das C möglichst klein
> halten, also q in C = 1/(1-q) möglichst klein, q muß
> >= 1/e damit das Minimum noch <=0 ist.
> Für q=1/e wird das Minimum 0 von ln(x)-x^q bei x=e^e angenommen,
> aus der verwendeten Methode lässt sich also
>  C<=1/(1-1/e)
> abschätzen, etwa 1.582.
>
> Dabei wurde noch nicht verwendet, daß in der O-Notation ja
> nur große x interessieren ...

Ja, thanks!
Der Doppelnutzen von x hat mich beim Skimmen irritiert.

Das Ganze ginge viel einfacher nur mit q=1/2 und der
Beobachtung log(x)<=sqrt(x) für x>=1. Dann ist dein C=2.

Der Trick steckt in der Zusammenfassung

>>> \log(x) + q \log(x) + q^2 \log(x) + ... \le
>>> \log(x)/(1-q)

Nett.

[Martin Vaeth]

Carlo XYZ <carl...@invalid.invalid> wrote:
> Das Ganze ginge viel einfacher nur mit q=1/2 und der
> Beobachtung log(x)<=sqrt(x) für x>=1.

Wenn Du das für _alle_ x>=1 (also alle x>0) weißt, ist das gut:
Es reicht ohne Zusatzüberlegungen eben leider nicht,
nur die Abschätzung log(x) <= sqrt(x) für große x zu kennen
weil bei den iterierten Logarithmen die Argumente
irgendwann beliebig klein werden.

Für die Abschätung log(x)<=sqrt(x) auch für kleine x
hatte ich keinen einfachen Beweis gesehen:
Das Lemma (das weniger behauptet), war halt schnell
hingeschrieben gewesen.
Im Nachheinein sehe ich jetzt, dass der Beweis des Lemmas
sogar log(x)<= x^{1/e} zeigt (falls ich mich nicht verrechnet
habe), so dass man sogar die bessere Konstante
1/(1-q)=e/(e-1) erhält.

[Carlo XYZ]

Am 09.01.18 um 21:45 schrieb Martin Vaeth:

> Carlo XYZ <carl...@invalid.invalid> wrote:

>> Das Ganze ginge viel einfacher nur mit q=1/2 und der
>> Beobachtung log(x)<=sqrt(x) für x>=1.
>
> Wenn Du das für _alle_ x>=1 (also alle x>0) weißt, ist das gut:
> Es reicht ohne Zusatzüberlegungen eben leider nicht,
> nur die Abschätzung log(x) <= sqrt(x) für große x zu kennen
> weil bei den iterierten Logarithmen die Argumente
> irgendwann beliebig klein werden.

Aber laut OP dann auch nicht mehr addiert.
Oder mache ich einen Denkfehler?

> Im Nachheinein sehe ich jetzt, dass der Beweis des Lemmas
> sogar log(x)<= x^{1/e} zeigt (falls ich mich nicht verrechnet
> habe), so dass man sogar die bessere Konstante
> 1/(1-q)=e/(e-1) erhält.

Verrechnen unwahrscheinlich. Auch der Mathe-Doc hat
e/(e-1) = 1/(1-1/e) rausbekommen.

[henselstep]

Ich wollte mich noch für diesen Beweis bedanken.

[Carlo XYZ]

Am 10.01.18 um 20:04 schrieb henselstep:

> Ich wollte mich noch für diesen Beweis bedanken.

De nada. Ich geb Martin und Detlef Bescheid:-)

[Martin Vaeth]

Carlo XYZ <carl...@invalid.invalid> wrote:
> Am 09.01.18 um 21:45 schrieb Martin Vaeth:
>
>> Carlo XYZ <carl...@invalid.invalid> wrote:
>
>>> Das Ganze ginge viel einfacher nur mit q=1/2 und der
>>> Beobachtung log(x)<=sqrt(x) für x>=1.
>>
>> Wenn Du das für _alle_ x>=1 (also alle x>0) weißt, ist das gut:
>> Es reicht ohne Zusatzüberlegungen eben leider nicht,
>> nur die Abschätzung log(x) <= sqrt(x) für große x zu kennen
>> weil bei den iterierten Logarithmen die Argumente
>> irgendwann beliebig klein werden.
>
> Aber laut OP dann auch nicht mehr addiert.

Mit "beliebig" klein meinte ich schon noch positiv, aber eben
kleiner als C (wenn man die Abschätzung log(x) <= sqrt(x)
nur für x > C als bekannt voraussetzt).
Das Problem ist dann eben, dass man eine unbekannte Anzahl
an Summanden hat, bei der die Abschätzung nicht mehr für
alle Iterationen des Logarithmus möglich ist. Man muss diese
Summanden dann mit Zusatzüberlegungen abschätzen, was zwar
vermutlich geht, aber aufwändiger ist, als C=0 nachzuweisen.

[Carlo XYZ]

Am 13.01.18 um 18:36 schrieb Martin Vaeth:

I see the point (I think).
Es ist sicher eine gute Idee, e zu betrachten,
dann hat man das Problem "für genügend große x" nicht.
Ich schreib mal "ln", um Missverständnisse zu vermeiden.

(1) Beh.: ln(x)<sqrt(x) für alle x>0.

Bew.:

Für x>0 hat ln(x)/sqrt(x) ein einziges Maximum
bei 2/e, und 2/e ist <1; also ln(x)/sqrt(x)<1 in (0,\infty).

(2) Beh.: Es gibt eine Konstante C>0, so dass für alle x>0:
ln(x) + ln(ln(x)) + ln(ln(ln(x))) + ... <= max(0,C*ln(x)).

wobei die Summe links nur so lange genommen wird,
wie die Summanden >=0 sind.

Bew.:

Falls 0<x<=1, bleibt von der Summe maximal der erste Summand übrig.
Deswegen ist die Summe =0 und deswegen auch <= max(0,C*ln(x))
(für jedes beliebige positive C).

Sei x>1. Dann

ln(x) + ln(ln(x)) + ln(ln(ln(x))) + ln(ln(ln(ln(x)))) + ...

<= ln(x) + ln(x^{1/2}) + ln(x^{1/4}) + ln(x^{1/8}) + ...

[Dabei wurde Beh.1 0-mal, 1-mal, 2-mal, 3-mal usw. benutzt]

= ln(x) + (1/2)*ln(x) + (1/4)*ln(x) + (1/8)*ln(x) + ...

= (1/(1-1/2))*ln(x)

= 2*ln(x).

In der ersten Zeile können negative Terme vorkommen,
ab der zweiten Zeile nicht mehr. Da die Terme einzeln
abgeschätzt wurden, gilt die Abschätzung auch bis hin
zu der Stelle, ab der nur noch negative Terme in der
ersten Zeile vorkommen, und die Partialsumme in der
zweiten Zeile kann von der Gesamtsumme (also der
letzten Zeile) abgeschätzt werden.

OK so? (Eigentlich ja dein Beweis.)

[Martin Vaeth]

Carlo XYZ <carl...@invalid.invalid> schrieb:

>
> OK so? (Eigentlich ja dein Beweis.)

Ja, und wie erwähnt funktioniert der Beweis
(keinen Rechenfehler bei der Maximumsbestimmung in
Schritt 1 vorausgesetzt) sogar mit x^{1/e}
statt sqrt(x) = x^{1/2}, was wie erwähnt zur
besseren Konstanten e/(e-1)=1.58... statt 2 führt.
Bleibt die Frage nach der bestmöglichen Konstanten.
Die dürfte vermutlich _deutlich_ kleiner sein. aber
dazu ist der primitive Ansatz mit der Abschätzung
durch eine geometrische Reihe natürlich unbrauchbar.

[Carlo XYZ]

Am 15.01.18 um 09:29 schrieb Martin Vaeth:

> Bleibt die Frage nach der bestmöglichen Konstanten.
> Die dürfte vermutlich _deutlich_ kleiner sein. aber
> dazu ist der primitive Ansatz mit der Abschätzung
> durch eine geometrische Reihe natürlich unbrauchbar.

Wieso? Ich vermute, dass mit - wie gehabt -
SUM(x)=ln(x)+ln(ln(x))+... (solange >0) gilt:

\forall C>1\exists y\forall x>y: SUM(x) <= C*ln(x)

D.h., jede Konstante C>1 zeigt,
dass SUM(x)\in O(ln(x)). Nur nicht C=1.

[Martin Vaeth]

Carlo XYZ <carl...@invalid.invalid> schrieb:

Das klingt plausibel. Aber siehst Du einen Beweis dafür?

Angewandt auf den "Rest" würde diese Vermutung
insbesondere die scheinbar allgemeinere Aussage implizieren,
dass für jedes n und jedes e>0 ein M existiert mit

SUM(x) < ln(x) + ln(ln(x)) + ... + ln^n(x) + e ln^n(x)

für alle x>M
(wobei ln^n die n-te Iteration des Logarithmus sei).

Letzteres war meine anfängliche Vermutung gewesen, aber
nachdem der Beweis mit der geometrischen Reihe wegen des
beschriebenen Problems nicht glatt dafür durchgelaufen ist,
bin ich inzwischen nicht mehr so sicher, ob die Vermutung
tatsächlich richtig ist.

[Martin Vaeth]

Martin Vaeth <mar...@mvath.de> wrote:
> dass für jedes n und jedes e>0 ein M existiert mit
>
> SUM(x) < ln(x) + ln(ln(x)) + ... + ln^n(x) + e ln^n(x)
>
> für alle x>M

Der Variablenname "e" ist in diesem Zusammenhang ungünstig:
Natürlich meinte ich "epsilon" damit, nicht die Eulersche Zahl...

[Carlo XYZ]

Am 17.01.18 um 10:36 schrieb Martin Vaeth:

> Das klingt plausibel. Aber siehst Du einen Beweis dafür?

Geht das nicht so, dass ln(x) für r>0 immer unter x^r bleibt,
zumindest wenn x groß genug ist? Und dann ungefähr wie vorher.

<https://math.stackexchange.com/questions/2501420/proving-lim-x-to-infty-frac-ln-xxr-0-and-lim-x-to-0xr-ln-x-0/2503146>

[Martin Vaeth]

Carlo XYZ <carl...@invalid.invalid> wrote:
>
> Geht das nicht so, dass ln(x) für r>0 immer unter x^r bleibt,
> zumindest wenn x groß genug ist?

Eben nur wenn x groß genug ist. Für die "meisten" der Summanden
wird das aber in vielen Logarithmen nicht der Fall sein.
Für einen korrekten Beweis müsste man zeigen, dass die Summe der
Summanden, für die die Abschätzung nicht greift (weil eines der
Argumente zu klein ist), durch eine endliche Konstante beschränkt
ist...
In einem formal korrekten Beweis könnte man beispielsweise jeweils
entweder die stärkere Abschätzung ln(x)\le x^q _oder_ die schwächere
ln(x)\le x^{1/2} machen (je nachdem, wie groß das jeweilige x ist) und
dann vorsichtig genug abschätzen, für welche Summandne man die schwächere
Abschätzung maximal anwenden musste, so dass man für deren Summe
mit irgendwelchen geometrischen Reihen einen _absoluten_ Fehlerterm
für alle Summanden erhält, die mindestens einmal die Potenz 1/2
enthalten (das wäre dann eine Abschätzung für die oben erwähnte
endliche Konstante).
Ob das Argument aber wirklich durchgeht, bin ich nicht sicher.
Es ist in jedem Fall so technisch, dass ich es nicht im Kopf kann,
und zum Aufschreiben habe ich im Moment weder Zeit noch Lust...

[Carlo XYZ]

Am 17.01.18 um 13:40 schrieb Martin Vaeth:

> Carlo XYZ <carl...@invalid.invalid> wrote:
>>
>> Geht das nicht so, dass ln(x) für r>0 immer unter x^r bleibt,
>> zumindest wenn x groß genug ist?
>

> Eben nur wenn x groß genug ist. [...]

Genügt das nicht für eine groß-O-Abschätzung,
mit einem ähnlichen Beweis wie vorher?

Na wie auch immer, ich klinke mich auch aus.

[Martin Vaeth]

Carlo XYZ <carl...@invalid.invalid> wrote:
> Am 17.01.18 um 13:40 schrieb Martin Vaeth:
>
>> Carlo XYZ <carl...@invalid.invalid> wrote:
>>>
>>> Geht das nicht so, dass ln(x) für r>0 immer unter x^r bleibt,
>>> zumindest wenn x groß genug ist?
>>
>> Eben nur wenn x groß genug ist. [...]
>
> Genügt das nicht für eine groß-O-Abschätzung,
> mit einem ähnlichen Beweis wie vorher?

Nein: Wenn \log x < x^r für x > C_1 gilt, folgt
\log^n x < x^{nr} nur für x > C_n
wobei C_{n+1} = exp(C_n). Wegen C_n \to \infty
genügt das nicht für den Beweis.

[Carlo XYZ]

Am 17.01.18 um 18:44 schrieb Martin Vaeth:

> Carlo XYZ <carl...@invalid.invalid> wrote:
>>
>> Genügt das nicht für eine groß-O-Abschätzung,
>> mit einem ähnlichen Beweis wie vorher?
>
> Nein: Wenn \log x < x^r für x > C_1 gilt, folgt
> \log^n x < x^{nr} nur für x > C_n
> wobei C_{n+1} = exp(C_n). Wegen C_n \to \infty
> genügt das nicht für den Beweis.

Einverstanden. Die Frage bleibt offen.