Jakie jest prawdopodobieństwo, że losowa funkcja boolowska ma trywialną grupę automorfizmów?

Biorąc pod uwagę funkcję boolowską , mamy grupę automorfizmów .$f$$Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \}$

Czy są jakieś znane granice dla ? Czy jest coś znanego dla ilości postaci dla jakiejś grupy ?$Pr_f(Aut(f) \neq 1)$$Pr_f(G \leq Aut(f))$$G$

Tak. W pierwszym pytaniu prawdopodobieństwo wynosi zero podwójnie wykładniczo szybkie. Można to obliczyć w następujący sposób. Dla każdej permutacji$\pi$, możemy ograniczyć prawdopodobieństwo, że $\pi \in Aut(f)$, tj. że $f(\pi(x)) = f(x)$ dla wszystkich $x \in \{0,1\}^n$. Rozważ orbity$\pi$ działając na $\{0,1\}^n$. Mamy to$\pi$ jest automorfizmem $f$ iff $f$ jest stały na $\pi$-orbit. Gdyby$\pi$ jest nietrywialny, ma przynajmniej jedną orbitę $[n]$ to nie jest singleton, a zatem przynajmniej na orbicie $\{0,1\}^n$to nie jest singleton. Załóżmy, że ma ją orbita$k$elementy w nim. Prawdopodobieństwo, że$f$ jest stała na tej orbicie, dlatego jest dokładnie $2^{-(k-1)}$. Przypuszczam, że$\pi$ działając na $[n]$ ma $c_1$ punkty stałe, $c_2$ cykle o długości 2 itd. (w szczególności $\sum_{i=1}^n i c_i = n$). Następnie liczba punktów$\{0,1\}^n$ naprawiony przez $\pi$ jest właśnie $2^{\sum_i c_i}$. Wszystkie pozostałe punkty$\{0,1\}^n$ są na nietrywialnych orbitach $\pi$. Do górnej granicy prawdopodobieństwo, że$\pi \in Aut(f)$, należy pamiętać, że najlepszą możliwością jest, jeśli wszystkie nietrwałe elementy $\{0,1\}^n$ przyjdź na orbity wielkości 2. Tak więc otrzymujemy to $Pr(\pi \in Aut(f)) \leq (1/2)^{M/2}$ gdzie $M = 2^n - 2^{\sum_i c_i}$. Teraz chcemy dolnej granicy$M$, co oznacza, że ​​chcemy górnej granicy $\sum_i c_i$. Od$\pi \neq 1$, największy $\sum c_i$ może być kiedy $c_1 = n-2$ i $c_2 = 1$, tj $\sum c_i = n-1$ i $M = 2^n - 2^{n-1} = 2^{n-1}$, więc $M \geq 2^{n-1}$ i $Pr(\pi \in Aut(f)) \leq (1/2)^{2^{n-2}}$. Teraz zastosuj związkową granicę:$|S_n| = n!$, więc $Pr((\exists \pi \in S_n)[\pi \neq 1 \text{ and } \pi \in Aut(f)]) \leq n! 2^{-2^{n-2}}$, co jest w zasadzie $2^{n \lg n - 2^{n-2}} \to 0$ tak jak $n \to \infty$, dość szybko.

Na dowolny $G \leq S_n$ możesz użyć podobnego rozumowania, ale prawdopodobieństwo również bardzo szybko spadnie do zera.