Unklarheit in Abschätzung

14.09.2021, 18:07

Malcang

Unklarheit in Abschätzung

Hallo zusammen,

ich schaue mir gerade den AKS Test an. Dort findet sich folgende Ungleichung:

[attach]53619[/attach]

Es geht um die erste Abschätzung in der untersten Zeile.
Ich nehme an, dass hier $\begin{eqnarray*} n^i-1 < n \end{eqnarray*}$ abgeschätzt wurde um die Exponenten zusammenzufassen. Aber sollte da bi hat nach der Summenformel ein + stehen?
Aber auch dann wüsste ich leider nicht weiter verwirrt

Was übersehe ich?

14.09.2021, 18:39

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von ichwarneu
Ich nehme an, dass hier $\begin{eqnarray*} n^i-1 < n \end{eqnarray*}$ abgeschätzt wurde um die Exponenten zusammenzufassen.

Richtig, gemäß Kleinem Gauß.

Zitat:

Original von ichwarneu
Aber sollte da bi hat nach der Summenformel ein + stehen?

Wie bitte? Der Satz ist unverständlich.

14.09.2021, 18:44

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von ichwarneu
Aber sollte da bi hat nach der Summenformel ein + stehen?

Wie bitte? Der Satz ist unverständlich.

Grüße dich, HAL,

es sollte Heissen:
"Aber sollte da nicht nach der Summenformel ein Plus stehen?"

Kann es leider nicht mehr editieren.

14.09.2021, 18:55

HAL 9000

Auf diesen Beitrag antworten »

Ich verstehe trotzdem nicht, was du meinst: Von welcher Summenformel redest du, nach der ein Plus stehen soll? verwirrt

14.09.2021, 19:05

Malcang

Auf diesen Beitrag antworten »

Ich hätte folgendes gesagt:

$\begin{eqnarray*} n^{\lfloor log B \rfloor}\cdot \prod\limits_{i=1}^{\lfloor \log^2 n\rfloor}(n^i-1) <n^{\lfloor log B \rfloor}\cdot \prod\limits_{i=1}^{\lfloor \log^2 n\rfloor}n^i = n^{\lfloor log B\rfloor +\sum\limits_{i=1}^{\lfloor \log^2 n \rfloor}i} \end{eqnarray*}$

Und es ist doch $\begin{eqnarray*} \sum\limits_{i=1}^{\lfloor \log^2 n \rfloor}i = \frac{1}{2}\cdot \lfloor \log^2 n \rfloor \cdot (\lfloor \log^2 n \rfloor+1) \leq \frac{1}{2}\cdot \ \log^2 n \ \cdot (\ \log^2 n +1) \end{eqnarray*}$

Im Text steht aber ganz rechts "-1".

14.09.2021, 19:06

HAL 9000

Auf diesen Beitrag antworten »

Ach so, das ist IN der Summenformel, nicht DANACH. Ja stimmt, da muss ein + hin. Beeinträchtigt aber wohl nicht die Gesamtabschätzung, denn die folgende Abschätzung scheint ja ziemlich grob zu sein, zumindest für große $\begin{eqnarray*} n \end{eqnarray*}$ . verwirrt

$\begin{eqnarray*} \log \end{eqnarray*}$ scheint hier $\begin{eqnarray*} \log_2 \end{eqnarray*}$ zu meinen (hast du vergessen zu erwähnen), lässt sich aus einigen andernfalls rätselhaften Abschätzungen in diesem Scan vermuten.

14.09.2021, 19:27

Malcang

Auf diesen Beitrag antworten »

Entschuldige bitte, und danke für die Klärung und die sprachliche Korrektur Augenzwinkern

An der weiteren Abschätzung harkt es Gerade leider noch, aber ich bin auch unterwegs und habe nicht die Ruhe.
Würde mich gerne dazu morgen wieder melden und mich über Rückmeldung freuen!

Danke für die Hilfe!

15.09.2021, 12:38

Malcang

Auf diesen Beitrag antworten »

Guten Tag,

ich hänge also leider nach wie vor an dieser Abschätzung.
Es bezeichne $\begin{eqnarray*} ld \end{eqnarray*}$ den Logarithmus zur Basis 2.
Es sei $\begin{eqnarray*} B := \lceil ld^5(n) \rceil \end{eqnarray*}$ .
Zu zeigen ist zuerst die Abschätzung $\begin{eqnarray*} \lfloor ld(B) \rfloor +\frac{1}{2}(ld^4(n) + ld^2(n)) \leq ld^4(n) \end{eqnarray*}$ .
Es ist
$\begin{eqnarray*} \lfloor ld(B) \rfloor +\frac{1}{2}(ld^4(n) + ld^2(n)) \leq ld^4(n) \Leftrightarrow \lfloor ld(B) \rfloor + \frac{1}{2}ld^2(n) \leq \frac{1}{2}ld^4(n) \end{eqnarray*}$ .

Ab hier weiß ich leider nicht weiter. Ich habe es mal versucht die Logarithmen zusammenzufassen aber das war nicht zielführend.

Wie könnte ich vorgehen?

15.09.2021, 13:09

HAL 9000

Auf diesen Beitrag antworten »

Ehrlich gesagt ist diese Ungleichung für $\begin{eqnarray*} n=3 \end{eqnarray*}$ (dort ist $\begin{eqnarray*} B=11 \end{eqnarray*}$ ) tatsächlich falsch. Für $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ sollte man sie aber durch geeignete Abschätzungen hinkriegen:

Um den Schreibaufwand zu mindern, kürze ich mal $\begin{eqnarray*} t:=\log_2(n) \end{eqnarray*}$ ab. Hinreichend für die nachzuweisende Behauptung für $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ ist dann

$\begin{eqnarray*} \log_2(t^5+1) \leq \frac{1}{2} t^2\left(t^2-1\right) \end{eqnarray*}$ für alle reellen $\begin{eqnarray*} t\geq 2 \end{eqnarray*}$

15.09.2021, 13:33

Malcang

Auf diesen Beitrag antworten »

Hallo HAL,

vielen Dank für deine Antwort. Sehr interessant, denn das Originalpaper spricht von $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ . Und das ist ja der Artikel "primes is in P", also gehe ich davon aus, das der entsprechend gegegelgegegelesen wurde. Klar, Fehler passieren, aber bei einem so alten Artikel und so vielen Mathematikern, die ihn gelesen haben?

Aber wie dem sei, danke für den weiteren Ansatz. Sobald ich aus dem Zug raus bin, werde ich mich wieder daran begeben.

15.09.2021, 13:37

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von ichwarneu
Sehr interessant, denn das Originalpaper spricht von $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ .

Das mag auch richtig sein, aber diverse Zwischenabschätzungen wie etwa $\begin{eqnarray*} \lfloor \log_2(n)\rfloor\leq \log_2(n) \end{eqnarray*}$ sind für $\begin{eqnarray*} n=3 \end{eqnarray*}$ zu grob für diesen Beweis. Wenn ich auf deinen Scan oben schaue, so ist

$\begin{eqnarray*} n^{\lfloor \log_2 B\rfloor}\cdot \prod (\ldots) < n^{\log_2^4(n)} \end{eqnarray*}$

trotzdem für n=3 erfüllt - dann eben per Einzelfallprüfung.

n=2 war laut Scan in diesem Beweisteil ausgeschlossen.

15.09.2021, 13:40

Papuga

Auf diesen Beitrag antworten »

Des öfteren tauchen Fehler in Papern auch, trotz Peer-Reviewing. Letztens erst hab Ich ein Paper von 2015 mit 170 Zitationen gelesen, wo eine Ableitung von einem Polynom falsch berechnet war. Am besten immer skeptisch sein

15.09.2021, 14:41

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Hinreichend für die nachzuweisende Behauptung für $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ ist dann

$\begin{eqnarray*} \log_2(t^5+1) \leq \frac{1}{2} t^2\left(t^2-1\right) \end{eqnarray*}$ für alle reellen $\begin{eqnarray*} t\geq 2 \end{eqnarray*}$

Ok, also das konnte ich jetzt analytisch hinbekommen, indem ich die Ableitung der Differenz beider Seiten gebildet habe und feststellte, dass diese immer größergleich null ist.
Außerdem gibt es ein $\begin{eqnarray*} t \end{eqnarray*}$ , dass die Ungleichung erfüllt.
Ich denke ich weiß in welche Richtung du mich lenken willst.
Da werde ich gleich nochmal genauer drauf eingehen, frage mich aber gerade, ob es einen weniger analytischen Weg gibt verwirrt

Verstehe mich nicht falsch, ich bin ja um solche Anregungen sehr dankbar. Aber ich habe das Gefühl, man könnte das mit log-Eigenschaften zeigen.
Aber da ich viel(!) weniger Erfahrung habe als du, gehe ich davon aus, da hast du schon dran überlegt Augenzwinkern

15.09.2021, 14:45

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von ichwarneu
Aber ich habe das Gefühl, man könnte das mit log-Eigenschaften zeigen.

Dass ich da meine Zweifel habe, musst du mir zugestehen: Ich bin alt (50+) und daher unflexibel. Wenn du das mit deinem frischen neuen Elan hinkriegst, dann lasse ich mich gern davon überzeugen. smile

15.09.2021, 15:10

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von ichwarneu
Aber ich habe das Gefühl, man könnte das mit log-Eigenschaften zeigen.

Ich würde sagen, es ist genau andersrum: Du hast diese Art der Dinge in deiner mathematischen Laufbahn bereits gesehen und kannst um Längen besser beurteilen ob etwas geht oder nicht.
Auch wenn mich deine Aussage natürlich irgendwie noch mehr beflügelt, es auf eine andere Art zu zeigen Augenzwinkern

06.10.2021, 13:09

Malcang

Auf diesen Beitrag antworten »

Hallo nochmal,

ich hoffe es ist ok, wenn ich diesen Thread nochmal ausgrabe. Mir ist in meiner Abschätzung ein Fehler aufgeallen und daher möchte ich gerne eine neue Abschätzung wagen. Nun hänge ich aber leider an einer Stelle.

Es ist also zu zeigen, dass $\begin{eqnarray*} (2\cdot ld^3(x)-ld(x))\cdot \log(2)\cdot(ld^5(x)+1) - 5\cdot ld^4(x)\geq 0 \forall x\geq 4 \end{eqnarray*}$

Mein Ansatz:
$\begin{eqnarray*} (2\cdot ld^3(x)-ld(x))\cdot \log(2)\cdot(ld^5(x)+1) - 5\cdot ld^4(x) \geq (ld^3(x)-ld(x))\cdot \log(2)\cdot(ld^5(x)+1) - 5\cdot ld^4(x) \geq (ld^3(x)-ld(x))\cdot \log(2)\cdot(ld^4(x)+1) - 5\cdot ld^4(x) = ld^4(x)\cdot ((ld^3(x)-ld(x))\cdot\log(2)-5) \end{eqnarray*}$

Aber nun hänge ich.
Ich hatte schon gedacht, $\begin{eqnarray*} 5\leq ld(x) \end{eqnarray*}$ zu nutzen, aber das geht ja erst ab x=32. verwirrt

06.10.2021, 21:29

IfindU

Auf diesen Beitrag antworten »

Die Abschätzung $\begin{eqnarray*} 2 \geq 1 \end{eqnarray*}$ im ersten Schritt ist schon sehr extrem und bringt dir am Ende nicht viel.

Vorschlag: Definiere $\begin{eqnarray*} y = ld(x) \end{eqnarray*}$ . Dann willst du zeigen, dass $\begin{eqnarray*} f(y) := (2y^3 - y) \log 2 (y^5 + 1) - 5y^4 \end{eqnarray*}$ erfüllt $\begin{eqnarray*} f(y) \geq 0 \end{eqnarray*}$ falls $\begin{eqnarray*} y \geq ld(4) = 2 \end{eqnarray*}$ .

.

Du kannst z.B. zeigen, dass $\begin{eqnarray*} f(2) > 0 \end{eqnarray*}$ ist und $\begin{eqnarray*} f'(y) > 0 \end{eqnarray*}$ für alle $\begin{eqnarray*} y > 2 \end{eqnarray*}$ . Vermutlich gilt $\begin{eqnarray*} f^{(n)}(2) > 0 \end{eqnarray*}$ für alle $\begin{eqnarray*} n \in \{0, 1, .., 7\} \end{eqnarray*}$ und $\begin{eqnarray*} f^{(8)} (y) = 8! \cdot log 2 > 0 \end{eqnarray*}$ . Und damit wäre es auch gezeigt.

Es ist nur etwas nervig, weil es ein Polynom 8. Grades.

Alternativ direkter: Ausmultiplizieren $\begin{eqnarray*} f(y) = \log 2 ( 2y^8 - y^6 + 2y^3 - y) - 5 y^4 \end{eqnarray*}$ .
Also $\begin{eqnarray*} f(y) \geq \frac 12 ( 2y^8 - y^6 + 2y^3 - y) - 5 y^4 \end{eqnarray*}$ . Jetzt gilt es auszunutzen wie viel größer die Potenzen sind:
$\begin{eqnarray*} y^8 = y^2 \cdot y^6 \geq 4 y^6 \end{eqnarray*}$ da $\begin{eqnarray*} y \geq 2 \end{eqnarray*}$ .
Also $\begin{eqnarray*} 2y^8 = \left ( \frac 7 4 + \frac 1 4 \right) y^8 \geq \frac 7 4 y^8 + y^6 \end{eqnarray*}$ . Insb. $\begin{eqnarray*} 2y^8 - y^6 \geq \frac 7 4 y^8 \end{eqnarray*}$ . Analog kannst du alle anderen negativen Summanden gegen höhere $\begin{eqnarray*} y \end{eqnarray*}$ -Potenzen wegschätzen. Am Ende bleibt eine Summe von strikt positiven Summanden übrig.

07.10.2021, 10:23

Malcang

Auf diesen Beitrag antworten »

Hallo IfindU,

danke für deine Mühen.
Ich hatte auch schon gedacht dass ich über die Ableitung gehen kann. Aber das erschien mir zu viel für mein Vorhaben. Deshalb habe ich nochmal einen anderen Ansatz probiert.

Was hälst du davon?
[attach]53767[/attach]

07.10.2021, 10:35

HAL 9000

Auf diesen Beitrag antworten »

Hmm, $\begin{eqnarray*} \log \end{eqnarray*}$ war bei dir der natürliche Logarithmus, oder? (Ich verwende nur $\begin{eqnarray*} \log \end{eqnarray*}$ , wenn die Basis egal ist, ansonsten nur $\begin{eqnarray*} \ln,\lg,\operatorname{ld},\log_b \end{eqnarray*}$ , um solchen Missverständnissen aus dem Weg zu gehen.)

Dann ist das richtig - für den dekadischen Logarithmus wäre nämlich die letzte benötigte Abschätzung $\begin{eqnarray*} 16\log(2)-5 > 0 \end{eqnarray*}$ falsch.

07.10.2021, 10:44

Malcang

Auf diesen Beitrag antworten »

Hallo HAL,

danke für den Hinweis. In der Tat ist $\begin{eqnarray*} \log \end{eqnarray*}$ der natürliche Logarithmus.
In meinem Dokument hab ich das auch weiter oben genannt aber natürlich verpeilt, dass hier ebenfalls zu nennen Hammer

Zumindest sollte ich das aber nochmal umformulieren, denn die Monotonie habe ich ja weiter oben schon benutzt.
Dafür bringe ich dann nochmal an, dass sich die Abschätzung $\begin{eqnarray*} \log(x) < 1-\frac{1}{x} \end{eqnarray*}$ auf den natürlichen Logarithmus bezieht.

Danke sehr!

Neue Frage »

Antworten »

Unklarheit in Abschätzung

Verwandte Themen