Bounded-Input-Bijektionen von unendlichen Sequenzen

28

Hier ist ein Rätsel, das ich nicht gelöst habe. Ich würde gerne wissen, ob dieses Problem bereits bekannt ist oder eine einfache Lösung hat.

Es ist möglich, eine Bijektion Verwendung der Eigenschaften von bicartesischen geschlossenen Kategorien zu definieren. Was dies bedeutet, hat Andrej Bauer in seinem Blog unter dem Titel " Konstruktiver Edelstein: Exponentiale jonglieren " erklärt.3N5N

Diese Bijektion hat eine interessante Eigenschaft: Sie ist "gebundene Eingabe", was bedeutet, dass jede Komponente der Ausgabe nur von begrenzt vielen Komponenten der Eingabe abhängt. Für scheint diese Konstruktion jedoch nur zu zeigen, dass und isomorph sind, wenn und beide ungerade oder beide gerade sind. Dies lässt die Frage offen:k N l N k lk,l2kNlNkl

Gibt es eine Bijektion mit beschränkter Eingabe von bis ? 3 N2N3N

Hier ist eine kurze Anmerkung, die das Problem ausführlicher beschreibt: Eine Vermutung über Bijektionen unendlicher Sequenzen mit begrenztem Eingang .

Definitionen:

Eine Funktion wird begrenzt eingegeben, wenn es eine ganze Zahl so dass jede Komponente der Ausgabe von nur von höchstens Komponenten abhängt des Eingangs. Genauer gesagt wird als Eingabe mit wenn für jeden Index die Indizes und eine Funktion so dass für alle die Komponente gleich . k f k f j J i 1 , , i kI f m : X i 1 × × X i kY j x X f ( x ) j f j ( x i 1 ,f:iIXijJYjkfkfjJi1,,ikIfm:Xi1××XikYjxXf(x)jfj(xi1,,xik)

Eine Bijektion ist eine Bijektion mit eingeschränkter Eingabe, wenn es sich um eine Funktion mit eingeschränkter Eingabe handelt.f

Eine Bijektion ist ein Isomorphismus mit beschränkter Eingabe, wenn es sich bei ihr und ihrer Inversen um Funktionen mit beschränkter Eingabe handelt. Das ist auch interessant.f

Colin McQuillan
quelle
Es ist wahrscheinlich besser, die Definition von "Bijection mit beschränkter Eingabe" aus Ihrer Notiz zu kopieren. Ich habe die Definition falsch verstanden, bis ich sie gelesen habe.
Tsuyoshi Ito
1
Getan. Ich möchte darauf hinweisen, dass die Motivation der Frage zwar aus der kategorietheoretischen Semantik stammt, das Puzzle selbst jedoch kombinatorisch ist.
Colin McQuillan
1
Das nervigste an diesem Problem ist, dass es einfach aussieht! Alle Sets begrenzt sind Eingängen isomorph zueinander sind, und so sind alle Sätze ( 2 k + 1 ) N . Ich kann keinen Grund erkennen, warum diese beiden nicht durch die Verwendung einer Variation der Isomorphismen, die in den vorhandenen Beweisen verwendet werden, isomorph gemacht werden können, aber solche Versuche scheinen zu scheitern. Aghh. (Ich habe keine Erfahrung in diesem Bereich, so kann ich von der Marke sein.)(2k)N(2k+1)N
Tsuyoshi Ito
1
Ich mag diese Vermutung wirklich und sie hängt jetzt seit einem Monat rum. Ich werde jedem, der das Problem löst oder wesentliche Fortschritte in beide Richtungen erzielt, eine Prämie gewähren.
Aaron Sterling
3
Schöne Frage :-) Übrigens, was ist der "einfachste" Isomorphismus zwischen und 3 N , den Sie kennen? 2N3N
Andrej Bauer

Antworten:

2

Ich bin kein CS-Theoretiker. In der Ergodentheorie wird diese Art der Abbildung als endliche Isomorphismen bezeichnet. Zum Beispiel wird überlegt, ob zwei Bernoulli-Sequenzen derselben Entropie endlich isomorph sind oder nicht. Zum Beispiel (dies ist eine einseitige Verschiebung, weil Sie sich anscheinend eher mit als mit P Z befassen ):PNPZ

A. Del Junco, "Finitary Codes zwischen einseitigen Bernoulli-Schichten", Ergodic Theory Dynamical Systems, vol. 1, S. 285–301, 1981.

PS Ich habe vor, dies als Kommentar zu hinterlassen, kann es aber aufgrund mangelnder Reputation nicht. Lass es mich wissen, wenn es komplett vom Thema abweicht, dann werde ich es löschen.

Gondoliere
quelle
Ich für meinen Teil begrüße alle verrückten Brainstorming-Ideen an dieser Stelle.
Aaron Sterling
2
Es ist zu beachten, dass es für diese Frage unerheblich ist, ob die Indizes von ℕ oder ℤ genommen werden.
Tsuyoshi Ito
Ich habe dieser Antwort das volle Kopfgeld zugesprochen, denn wenn ich nichts täte, würde die Antwort sowieso die Hälfte des Kopfgeldes erhalten, als die am besten bewertete (und mindestens zwei Stimmen erhalten haben). Wenn jemand zu einem späteren Zeitpunkt einen vollständigen oder teilweisen Proof veröffentlicht und ich sehe, werde ich wahrscheinlich ein weiteres Kopfgeld auslösen, um dem Solver einen Mitarbeiter zuzuweisen.
Aaron Sterling
0

kN2Nkk=3k2k1

2NkN

ii k

kkikki


quelle
2
Diese Eingabe ist in keiner Richtung beschränkt. Gemäß der Definition einer Funktion mit Eingabebegrenzung benötigen Sie eine einheitliche Begrenzung der Anzahl der Eingabevariablen, von denen jede Ausgabevariable abhängt. In der Vorwärtsrichtung Ihres Mappings hängt die i-te Ausgabevariable von den ersten i-Eingabevariablen ab, sodass keine einheitliche Grenze besteht. In Rückwärtsrichtung hängt die i-te Ausgangsvariable von den ersten ki-Eingangsvariablen ab.
Tsuyoshi Ito
1
D'oh. Ich werde die Frage zum 1.5. Mal lesen. :(