Forum:  Komplexitätstheorie
Thema: n^2+1 nicht Produkt von Funktionen aus O(n)?
Themen-Übersicht
sonnenschein96
Senior
Dabei seit: 26.04.2020
Mitteilungen: 213
Aus:
Themenstart: 2020-09-19 17:00

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


Ixx
Aktiv
Dabei seit: 05.04.2020
Mitteilungen: 192
Aus:
Beitrag No.1, eingetragen 2020-09-19 18:37

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.


Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 2410
Aus:
Beitrag No.2, eingetragen 2020-09-19 18:43
\(\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\)

sonnenschein96
Senior
Dabei seit: 26.04.2020
Mitteilungen: 213
Aus:
Beitrag No.3, vom Themenstarter, eingetragen 2020-09-19 19:00

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.


Ixx
Aktiv
Dabei seit: 05.04.2020
Mitteilungen: 192
Aus:
Beitrag No.4, eingetragen 2020-09-19 19:27

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


Kezer
Senior
Dabei seit: 04.10.2013
Mitteilungen: 1029
Aus:
Beitrag No.5, eingetragen 2020-09-19 19:55

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



sonnenschein96
Senior
Dabei seit: 26.04.2020
Mitteilungen: 213
Aus:
Beitrag No.6, vom Themenstarter, eingetragen 2020-09-19 20:42

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.


Kezer
Senior
Dabei seit: 04.10.2013
Mitteilungen: 1029
Aus:
Beitrag No.7, eingetragen 2020-09-19 20:51

Sieht gut aus!




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=249478=510003
Druckdatum: 2020-11-29 11:31