Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Given a Boolean function $f$, we have the automorphism group $Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \}$.
Are there any known bounds on $Pr_f(Aut(f) \neq 1)$? Is there anything known for quantities of the form $Pr_f(G \leq Aut(f))$ for some group $G$?
Yes. To your first question, the probability goes to zero double-exponentially fast. This can be calculated as follows. For each permutation $\pi$, we can bound the probability that $\pi \in Aut(f)$, i.e. that $f(\pi(x)) = f(x)$ for all $x \in \{0,1\}^n$. Consider the orbits of $\pi$ acting on $\{0,1\}^n$. We have that $\pi$ is an automorphism of $f$ iff $f$ is constant on the $\pi$-orbits. If $\pi$ is nontrivial, it has at least one orbit on $[n]$ that is not a singleton, and therefore at least on orbit on $\{0,1\}^n$ that is not a singleton. Suppose that orbit has $k$ elements in it. The probability that $f$ is constant on that orbit is thus precisely $2^{-(k-1)}$. Suppose that $\pi$ acting on $[n]$ has $c_1$ fixed points, $c_2$ cycles of length 2, etc. (in particular $\sum_{i=1}^n i c_i = n$). Then the number of points of $\{0,1\}^n$ fixed by $\pi$ is precisely $2^{\sum_i c_i}$. All the remaining points of $\{0,1\}^n$ are in nontrivial orbits of $\pi$. To upper bound the probability that $\pi \in Aut(f)$, note that the best possibility is if all the non-fixed elements of $\{0,1\}^n$ come in orbits of size 2. So we get that $Pr(\pi \in Aut(f)) \leq (1/2)^{M/2}$ where $M = 2^n - 2^{\sum_i c_i}$. Now, we want a lower bound on $M$, which means we want an upper bound on $\sum_i c_i$. Since $\pi \neq 1$, the largest $\sum c_i$ can be is when $c_1 = n-2$ and $c_2 = 1$, i.e. $\sum c_i = n-1$ and $M = 2^n - 2^{n-1} = 2^{n-1}$, so $M \geq 2^{n-1}$ and $Pr(\pi \in Aut(f)) \leq (1/2)^{2^{n-2}}$. Now apply the union bound: $|S_n| = n!$, so $Pr((\exists \pi \in S_n)[\pi \neq 1 \text{ and } \pi \in Aut(f)]) \leq n! 2^{-2^{n-2}}$, which is basically $2^{n \lg n - 2^{n-2}} \to 0$ as $n \to \infty$, pretty quickly.
For any given $G \leq S_n$ you could use similar reasoning, but the probability will also go to zero very quickly.
