<p>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.</p>

<p>For any given $G \leq S_n$ you could use similar reasoning, but the probability will also go to zero very quickly.</p>

CC BY-SA 3.0
2018-01-25T09:27:12.730Z
Wouldn't the probability of f being constant on the orbit be $2^{-k}?
Samuel Schlesinger
CC BY-SA 3.0
2018-01-25T09:27:52.813Z
Thanks for this by the way, it reminds me a lot of the graph version's proof.
Samuel Schlesinger
CC BY-SA 3.0
2018-01-25T09:29:05.953Z
Oh, I see why it's $2^{-(k-1)}$
Samuel Schlesinger
CC BY-SA 3.0
2018-01-25T18:11:33.633Z
@SamuelSchlesinger: Yes, similar. I think it's even easier in this case because the number of boolean functions is double-exponential whereas the number of graphs is only $\sim 2^{n^2 - n \lg n}$.
Joshua Grochow
CC BY-SA 3.0
2018-01-25T09:08:04.487Z
2018-01-25T09:08:04.487Z
Joshua Grochow
<p>Given a Boolean function $f$, we have the automorphism group $Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \}$.</p>

<p>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$?</p>

<boolean-functions><randomness><gr.group-theory><symmetry>
What is the probability that a random Boolean function has a trivial automorphism group?
Samuel Schlesinger
# What is the probability that a random Boolean function has a trivial automorphism group?

(Asked by: username_0 on 2018-01-24)

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$?

**Tags:** boolean-functions, randomness, gr.group-theory, symmetry


---

## 1 answers

### Answer by username_1 on 2018-01-25. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: Wouldn't the probability of f being constant on the orbit be $2^{-k}?  
> **username_0**: Thanks for this by the way, it reminds me a lot of the graph version's proof.  
> **username_0**: Oh, I see why it's $2^{-(k-1)}$  
> **username_1**: @SamuelSchlesinger: Yes, similar. I think it's even easier in this case because the number of boolean functions is double-exponential whereas the number of graphs is only $\sim 2^{n^2 - n \lg n}$.  

---

