Kolmogorov-Komplexitätsanwendungen in der Zahlentheorie

8

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?

Subhayan
quelle
Könnten Sie mich bitte auf den auf Kolmogoroff-Komplexität basierenden Beweis für die Unendlichkeit der Primzahlen hinweisen?
Martin Berger
2
@ MartinBerger: siehe Li und Vitanyi Buch oder diese Notiz von Lance Fortnow
Marzio De Biasi
1
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, . n K ( n ) l o g 2 n
S.=n1,n2,...
nnS.K.(n)lÖG2n2nS.p1...pm
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Σ m j = 1 P v i , j j m K ( n i ) v i , j K ( n i ) = c o n s t + Σ m j = 1 l o g 2 ( v i , j + 1 ) c o n s t + m . lnichΣj=1mpjvich,jmK.(nich)vich,jK.(nich)=cÖnst+Σj=1m lÖG2(vich,j+1) K ( n ) l o g 2 ncÖnst+m.lÖG2lÖG2nichnSlog2niK.(n)lÖG2n2 nS.nilÖG2nich2m.lÖG2lÖG2nichnich. Daher kommen wir zu einem Widerspruch
Subhayan
2
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ätp k p kk log 2 kkpkpkkLog2k
Sasho Nikolov

Antworten:

3

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 . xln(xxln(x)xln(xln(x))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
0

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:

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

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
-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