Kolmogorov-Komplexitätsanwendungen in der Zahlentheorie

Was sind die Anwendungen der Kolmogorov-Komplexität in der Zahlentheorie und auf beweisbezogenen Gebieten? (Die Monographie von Li & Vitanyi hat nicht viele Anwendungen im Zusammenhang mit der Zahlentheorie.)

Einer der schönen Beweise, auf die ich gestoßen bin, ist der Beweis für die Existenz einer unendlichen Anzahl von Primzahlen unter Verwendung der Definition der Kolmogorov-Komplexität und des Kompressionsfaktors.

Welche Bedeutung hat die Kolmogorov-Komplexität in der Kryptographie?

reference-request big-list it.information-theory kolmogorov-complexity Subhayan
quelle

Könnten Sie mich bitte auf den auf Kolmogoroff-Komplexität basierenden Beweis für die Unendlichkeit der Primzahlen hinweisen?

Martin Berger

@ MartinBerger: siehe Li und Vitanyi Buch oder diese Notiz von Lance Fortnow

Marzio De Biasi

Okay, das ist etwas umständlich, aber ich kann mich anscheinend nicht erinnern, wo ich darauf gestoßen bin. Der Beweis lautet ungefähr so. Nehmen wir an, Sie wählen eine Inf. Satz , so dass positiv ist , und , . Nun zum Zweck des Widerspruchs annimmt , dass es nur eine endliche Anzahl von Primzahlen, .

S. = n_{1}, n_{2}, . . .

$S = {n_1,n_2,...}$

n

$n$

K (n) \geq \frac{l o g_{2} n}{2}

$K(n) \geq \frac{log_2 n}{2}$

\forall n \in S

$\forall n \in S$

p_{1} . . . p_{m}

${p_1...p_m}$

Subhayan

[Fortsetzung] Nun können wir also jedesals. Da wir angenommen haben, dass es nur endlich viele () Primzahlen gibt, haben sie eine feste Darstellung. Sohängt nur von ders .. soes zusammenzufassen,... was höchstens einekann... aber dann haben wirdeklariert. Daher impliziert dies, dass, dies gilt jedoch nur für eine endliche Anzahl von

n_{i}

$n_i$

Σ_{j = 1}^{m} p_{j}^{v_{i, j}}

$\Sigma_{j=1}^{m}p_j^{v_{i,j}}$

m

$m$

K (n_{i})

$K(n_i)$

v_{i, j}

$v_{i,j}$

K (n_{i}) = c o n s t + Σ_{j = 1}^{m} l o g_{2} (v_{i, j} + 1)

$K(n_i) = const + \Sigma_{j=1}^{m}\ log_2(v_{i,j}+1)$

c o n s t + m . l o g_{2} l o g_{2} n_{i}

$const + m.log_2log_2n_{i}$

K (n) \geq \frac{l o g_{2} n}{2}

$K(n) \geq \frac{log_2 n}{2}$

\forall n \in S

$\forall n \in S$

\frac{l o g_{2} n_{i}}{2} \leq m . l o g_{2} l o g_{2} n_{i}

$\frac{log_2 n_i}{2} \leq m.log_2log_2n_{i}$

n_{i}

$n_i$ . Daher kommen wir zu einem Widerspruch

Subhayan

Ich mag das zweite NT-Beispiel aus Lances Notizen: Die te Primzahl ist höchstens . Dies ist eine Abmeldung vom Primzahlsatz, und der Beweis ist ungefähr so einfach wie der Beweis der Unendlichkeit von Primzahlen über K. Komplexität

k

$k$

p_{k}

$p_k$

p_{k} \leq k \log^{2} k

$p_k \leq k\log^2 k$

Sasho Nikolov

Antworten:

Jede ganze Zahl hat eine Kolmogorov-Komplexität; das kürzeste Programm, das diese Ganzzahl druckt.

Es gibt Primzahlen bis zu so dass Primzahlen im Durchschnitt eine geringere Kolmogrov-Komplexität aufweisen als Verbundwerkstoffe; vs . $\approx {x \over ln(x)}$ $x$ $\approx ln({x \over ln(x)})$ $\approx ln(x)$

Als Nebeneffekt müssen einige große Lücken zwischen den Primzahlen bestehen. Andernfalls könnten Sie jede Zahl als vorherige Primzahl plus eine kleine Anzahl von Bits codieren.

Chad Brewbaker
quelle

Aufgrund des Primzahlsatzes gibt es große Lücken zwischen den Primzahlen. Ich glaube nicht, dass Sie die Kolmogorov-Komplexität in die Mischung aufnehmen müssen, um dies zu zeigen.

Sasho Nikolov

Die Zahlentheorie befasst sich im Allgemeinen mit ganzzahligen Gleichungen, obwohl Wikipedia allgemeiner sagt , dass eine Unterzweig der Zahlentheorie die Annäherung von Real durch Rationalen und die Beziehung zwischen ihnen ist: "Man kann auch reelle Zahlen in Bezug auf rationale Zahlen untersuchen, z. wie durch letzteres angenähert ( diophantinische Annäherung ). "

Hier sind im Allgemeinen zwei Artikel in dieser Richtung:

Die Kolmogorov-Komplexität reeller Zahlen Ludwig Staiger
Eine Charakterisierung von ce random reals Cristian S. Calude

vzn
quelle

Welcher Teil der Komolgorov-Komplexität kann nicht auf ganzzahlige Gleichungen angewendet werden? Es stimmt zwar, dass sich das Thema oft mit dem Unendlichen befasst, aber auch die Zahlentheorie (z. B. diophantinische Gleichungen usw.), und natürlich gibt es verschiedene ressourcengebundene Versionen von KC, die relevant sein können usw. Ich bin nur Ich bin mir nicht sicher, wo sich die Zahlentheorie im Allgemeinen mit ganzzahligen Gleichungen befasst. Sie hat etwas damit zu tun, ob es Anwendungen von KC für das Thema gibt.

Steven Stadnicki

Der Punkt ist, dass ich bei einer flüchtigen Online-Suche [noch?] keine Referenzen gefunden habe, die KC direkt mit der Zahlentheorie in Verbindung bringen, aber es gibt einige, die sich auf die Analyse von Realitäten und rationalen Approximationen in einer Weise beziehen, die an die Zahlentheorie grenzt.

vzn

Ja, auch ich habe versucht, über Anwendungen von KC in der Zahlentheorie nachzuschlagen, aber ich konnte nichts finden. Jetzt scheint KC ein guter Weg zu sein, um einige Probleme in der Zahlentheorie anzugehen. Es sollte einige grundlegende Beweise (Anwendungen) geben. hier ..

Subhayan

-2

Versuchen Sie diese Referenz

Von Kolmogorovs Theorem über die empirische Verteilung bis zur Zahlentheorie , Kevin Ford, auch hier .

Wir beschreiben einige neue Schätzungen für die Wahrscheinlichkeit, dass eine empirische Verteilungsfunktion auf einer Seite einer bestimmten Linie bleibt, und geben Anwendungen für die Zahlentheorie.

$K(x)$
$K(x)$ $K(x)$ ist gleichzeitig das strengste Maß für die Entropie und gleichzeitig das unlösbarste, mit anderen Entropiemaßnahmen an anderen "einfacheren" Punkten in diesem scheinbar strengen Kompromisskontinuum.

vzn
quelle

-1: Der Kolmogorov-Satz in der ersten Referenz bezieht sich nicht auf die Kolmogorov-Komplexität. Es ist ein berühmtes Ergebnis über die Konvergenz der empirischen Verteilungsfunktion von IID-Proben mit der CDF.

Sasho Nikolov

stimmte in diesem Punkt überein, oops = (

vzn