Wie groß ist die Wahrscheinlichkeit, dass eine zufällige Boolesche Funktion eine triviale Automorphismusgruppe hat?

9

Bei gegebener Boolescher Funktion haben wir die Automorphismusgruppe .fAut(f)={σSn x,f(σ(x))=f(x)}

Gibt es bekannte Grenzen für ? Ist für Mengen der Form für eine Gruppe ?Prf(Aut(f)1)Prf(GAut(f))G

Samuel Schlesinger
quelle

Antworten:

4

Ja. Bei Ihrer ersten Frage geht die Wahrscheinlichkeit doppelt exponentiell schnell auf Null. Dies kann wie folgt berechnet werden. Für jede Permutation können wir die Wahrscheinlichkeit begrenzen, dass , dh dass für alle . Betrachten Sie die Umlaufbahnen von die auf . Wir haben, dass ein Automorphismus von wenn auf den -orbits konstant ist . Wenn trivial ist, hat es mindestens eine Umlaufbahn auf , die kein Singleton ist, und daher mindestens eine Umlaufbahn aufππAut(f)f(π(x))=f(x)x{0,1}nπ{0,1}nπffππ[n]{0,1}ndas ist kein Singleton. Angenommen, die Umlaufbahn enthält Elemente. Die Wahrscheinlichkeit, dass auf dieser Umlaufbahn konstant ist, beträgt somit genau . Angenommen, , das auf einwirkt, hat Fixpunkte, Zyklen der Länge 2 usw. (insbesondere ). Dann beträgt die durch festgelegte Anzahl von Punkten von genau . Alle verbleibenden Punkte von befinden sich in nichttrivialen Bahnen von . Zur Obergrenze der Wahrscheinlichkeit, dasskf2(k1)π[n]c1c2i=1nici=n{0,1}nπ2ici{0,1}nππAut(f)Beachten Sie, dass die beste Möglichkeit besteht, wenn alle nicht festen Elemente von in Umlaufbahnen der Größe 2 vorliegen. Wir erhalten also wobei . Jetzt wollen wir eine Untergrenze für , was bedeutet, dass wir eine Obergrenze für . Da , kann die größte sein, wenn und , dh und , also und . Wenden Sie nun die Gewerkschaftsbindung an:{0,1}nPr(πAut(f))(1/2)M/2M=2n2iciMiciπ1cic1=n2c2=1ci=n1M=2n2n1=2n1M2n1Pr(πAut(f))(1/2)2n2|Sn|=n!, also , was im Grunde genommen als , ziemlich schnell.Pr((πSn)[π1 and πAut(f)])n!22n22nlgn2n20n

Für jedes gegebene könnten Sie ähnliche Überlegungen verwenden, aber die Wahrscheinlichkeit wird auch sehr schnell auf Null gehen.GSn

Joshua Grochow
quelle
Wäre die Wahrscheinlichkeit, dass f auf der Umlaufbahn konstant ist, nicht $ 2 ^ {- k}?
Samuel Schlesinger
1
Danke übrigens, es erinnert mich sehr an den Beweis der Grafikversion.
Samuel Schlesinger
1
Oh, ich verstehe, warum es2(k1)
Samuel Schlesinger
1
@ SamuelSchlesinger: Ja, ähnlich. Ich denke, es ist in diesem Fall noch einfacher, weil die Anzahl der Booleschen Funktionen doppelt exponentiell ist, während die Anzahl der Graphen nur beträgt . 2n2nlgn
Joshua Grochow