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

Bei gegebener Boolescher Funktion haben wir die Automorphismusgruppe .$f$$Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \}$

Gibt es bekannte Grenzen für ? Ist für Mengen der Form für eine Gruppe ?$Pr_f(Aut(f) \neq 1)$$Pr_f(G \leq Aut(f))$$G$

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$\pi$$\pi \in Aut(f)$$f(\pi(x)) = f(x)$$x \in \{0,1\}^n$$\pi$$\{0,1\}^n$$\pi$$f$$f$$\pi$$\pi$$[n]$$\{0,1\}^n$das 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, dass$k$$f$$2^{-(k-1)}$$\pi$$[n]$$c_1$$c_2$$\sum_{i=1}^n i c_i = n$$\{0,1\}^n$$\pi$$2^{\sum_i c_i}$$\{0,1\}^n$$\pi$$\pi \in 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\}^n$$Pr(\pi \in Aut(f)) \leq (1/2)^{M/2}$$M = 2^n - 2^{\sum_i c_i}$$M$$\sum_i c_i$$\pi \neq 1$$\sum c_i$$c_1 = n-2$$c_2 = 1$$\sum c_i = n-1$$M = 2^n - 2^{n-1} = 2^{n-1}$$M \geq 2^{n-1}$$Pr(\pi \in Aut(f)) \leq (1/2)^{2^{n-2}}$$|S_n| = n!$, also , was im Grunde genommen als , ziemlich schnell.$Pr((\exists \pi \in S_n)[\pi \neq 1 \text{ and } \pi \in Aut(f)]) \leq n! 2^{-2^{n-2}}$$2^{n \lg n - 2^{n-2}} \to 0$$n \to \infty$

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