Matroids Matheplanet Forum Index
Forumbereich moderiert von: Bilbo
Theoretische Informatik » Komplexitätstheorie » n^2+1 nicht Produkt von Funktionen aus O(n)?
Druckversion
Druckversion
Universität/Hochschule J n^2+1 nicht Produkt von Funktionen aus O(n)?
sonnenschein96 Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 26.04.2020, Mitteilungen: 218
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Themenstart: 2020-09-19

Hallo Leute,

in einer meiner Informatik-Übungen wurde einmal behauptet, dass es "offensichtlich" keine Funktionen \(f,g\in\mathcal{O}(n)\) gibt, sodass \(n^2+1=f(n)g(n)\) für alle \(n\in\mathbb{N}\). Dies wurde aber natürlich nicht begründet...

Ich finde es ehrlich gesagt nicht so offensichtlich, ob die Aussage überhaupt wahr ist.

Meine Überlegungen dazu: Für festes \(n\in\mathbb{N}\) kann man anhand der Primfaktorzerlegung von \(n^2+1\) erkennen, wie viele Möglichkeiten es gibt \(n^2+1\) in zwei Faktoren aufzuspalten.

Damit sieht man leicht, dass es unendlich viele Möglichkeiten gibt, Funktionen \(f,g\colon\mathbb{N}\to\mathbb{N}\) zu finden, sodass \(n^2+1=f(n)g(n)\) für alle \(n\in\mathbb{N}\).

Die Frage ist nun, ob stets \(f\notin\mathcal{O}(n)\) oder \(g\notin\mathcal{O}(n)\).

Wüssten wir, dass \(n^2+1\) für unendlich viele \(n\in\mathbb{N}\) prim ist, so müsste \(f(n)=n^2+1\) für unendlich viele \(n\in\mathbb{N}\) oder \(g(n)=n^2+1\) für unendlich viele \(n\in\mathbb{N}\) und wir wären fertig.

Ich habe jedoch festgestellt, dass dies anscheinend eines der Landau-Probleme ist, welche bis heute ungelöst sind.

Die Frage ist daher, ob es eine elementarere Begründung für die zu zeigende Aussage gibt?

Ich könnte mir vorstellen, dass \(n^2+1\) für unendlich viele \(n\in\mathbb{N}\) zumindest große Primfaktoren enthält, sodass stets mindestens eine der beiden Funktionen nicht in \(\mathcal{O}(n)\) liegen kann.

Viele Grüße
sonnenschein96



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 05.04.2020, Mitteilungen: 192
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.1, eingetragen 2020-09-19

Wegen $f,g\in\mathcal{O}(n)$ müssen beide linear sein. Seien $x_f, x_g \in \mathbb{Q}$ die Nullstellen von $f,g$. Dann wären es auch Nullstellen von $x^2+1$, Widerspruch.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2411
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.2, eingetragen 2020-09-19
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
@Ixx: $\mathcal O(n)$ enthält auch nichtlineare Funktionen $\IN\to \IN$. Z.B. $n\mapsto n+(-1)^n$.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
sonnenschein96 Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 26.04.2020, Mitteilungen: 218
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.3, vom Themenstarter, eingetragen 2020-09-19

Hallo Ixx,

wir haben \(\mathcal{O}(n)\) definiert als die Menge aller Funktionen \(f\colon\mathbb{N}\to\mathbb{N}\) für dies es \(c,n_0\in\mathbb{N}\) gibt mit \(f(n)\leq cn\) für alle \(n\geq n_0\).

Würde \(\mathcal{O}(n)\) nur lineare Funktionen enthalten, wäre die Frage viel einfacher zu beantworten.

\(\mathcal{O}(n)\) enthält aber viele Funktionen, die sehr kompliziert sein können (wie Nuramon ja schon angedeutet hat), da sie sich von Punkt zu Punkt sehr unterschiedlich verhalten können, solange sie nur nach oben linear beschränkt sind.

Daher meinte ich ja auch, dass man für \(n\in\mathbb{N}\) die Primfaktoren von \(n^2+1\) jeweils auf \(f(n)\) und \(g(n)\) aufteilen kann, was eben zu sehr komplizierten \(f\) und \(g\) führen kann.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 05.04.2020, Mitteilungen: 192
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.4, eingetragen 2020-09-19

Ihr habt natürlich völlig recht, da habe ich zu schnell reagiert...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kezer Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 04.10.2013, Mitteilungen: 1037
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.5, eingetragen 2020-09-19

Dein Vorschlag würde funktionieren, schaue mal hier: MSE/589344. Als offensichtlich würde ich das allerdings nicht bezeichnen :-p




-----------------
The difference between the novice and the master is that the master has failed more times than the novice has tried. ~ Koro-Sensei



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
sonnenschein96 Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 26.04.2020, Mitteilungen: 218
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.6, vom Themenstarter, eingetragen 2020-09-19

Hallo Kezer,

das ist glaube ich genau das was ich gesucht habe, vielen Dank :)

Mein Beweis sähe dann wie folgt aus:

Sei \(A\) die Menge aller \(n\in\mathbb{N}\), sodass \(n^2+1\) einen Primfaktor \(p_n\) größer als \(n\log(n)\) hat. Nach dem Link den Du angegeben hast enthält \(A\) unendlich viele Elemente. (Die Beweise schaue ich mir später an. Ich würde diese auch nicht gerade als offensichtlich bezeichnen :P)

Es seien nun \(f,g\colon\mathbb{N}\to\mathbb{N}\) mit \(n^2+1=f(n)g(n)\) für alle \(n\in\mathbb{N}\). Für jedes \(n\in A\) muss \(p_n\) dann als Primfaktor in \(f(n)\) oder \(g(n)\) vorkommen, d.h. \(f(n)>n\log(n)\) oder \(g(n)>n\log(n)\).

Sei \(A_f\) (\(A_g\)) die Menge aller \(n\in\mathbb{N}\) mit \(f(n)>n\log(n)\) (\(g(n)>n\log(n)\)). Es gilt dann \(A\subseteq A_f\cup A_g\) und da \(A\) unendlich ist, muss mindestens eine der Mengen \(A_f,A_g\) unendlich sein.

Sagen wir \(A_f\) ist unendlich (für \(A_g\) analog). Angenommen \(f\in\mathcal{O}(n)\). Dann gäbe es \(c,n_0\in\mathbb{N}\) mit \(f(n)\leq cn\) für alle \(n\geq n_0\) und es würde \(n\log(n)<f(n)\leq cn\), also \(\log(n)<c\), für alle \(n\in A_f\) mit \(n\geq n_0\) folgen. Dies widerspricht der Unendlichkeit von \(A_f\). Damit ist \(f\notin\mathcal{O}(n)\).

Für den Fall, dass \(A_g\) unendlich ist, folgt \(g\notin\mathcal{O}(n)\). Auf jeden Fall kann nicht \(f\in\mathcal{O}(n)\) und \(g\in\mathcal{O}(n)\) gelten.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kezer Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 04.10.2013, Mitteilungen: 1037
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.7, eingetragen 2020-09-19

Sieht gut aus!


-----------------
The difference between the novice and the master is that the master has failed more times than the novice has tried. ~ Koro-Sensei



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
sonnenschein96 hat die Antworten auf ihre/seine Frage gesehen.
sonnenschein96 hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]