9
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wouldn't the probability of f being constant on the orbit be $2^{-k}? $\endgroup$ – Samuel Schlesinger Jan 25 '18 at 9:27
  • 1
    $\begingroup$ Thanks for this by the way, it reminds me a lot of the graph version's proof. $\endgroup$ – Samuel Schlesinger Jan 25 '18 at 9:27
  • 1
    $\begingroup$ Oh, I see why it's $2^{-(k-1)}$ $\endgroup$ – Samuel Schlesinger Jan 25 '18 at 9:29
  • 1
    $\begingroup$ @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}$. $\endgroup$ – Joshua Grochow Jan 25 '18 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.