2
$\begingroup$

Let $S_n$ act on the set of boolean functions of size $n$ in the following way:

If $f$ is a boolean function and $\alpha \in S_n$, then $g=\alpha f$ and $g(x)=f(\alpha(x))$ where $x$ is boolean vector of size $n$;

Let $p$ be the number of orbits. Since each orbit can have no more than $n!$ elements it is obvious that $p\ge\frac{2^{2^n}}{n!}$.

I am interested in an upper bound of $p$. Do you know any related results?

Improve this question
$\endgroup$
4
  • $\begingroup$ Why do you have $2^{2^n}$ and not just $2^n$ in the approximation? In any case, it really seems that this is the same as the action of $S_n$ on subsets of $\{1,\ldots, n\}$, and the number of orbits is just $n+1$. $\endgroup$
    – Ehud Meir
    Feb 5, 2017 at 20:09
  • $\begingroup$ $2^{2^n}$ is the number of boolean functions of $n$ arguments. The group acts on that set. $\endgroup$
    – Ashot
    Feb 5, 2017 at 20:24
  • $\begingroup$ So you mean "boolean functions on boolean functions on $n$ elements"? $\endgroup$
    – Ehud Meir
    Feb 5, 2017 at 20:26
  • $\begingroup$ I think Ashot means "Boolean functions in n variables". Such a thing, $f(x_1,\ldots,x_n)$, accepts inputs $x_i\in \{0,1\}$ and produces an output in $\{0,1\}$. That is, it is a function from $\{0,1\}^n$ to $\{0,1\}$. There are $2^{2^n}$ such things. $\endgroup$
    – Keith Kearnes
    Feb 6, 2017 at 3:21

1 Answer 1

Reset to default
5
$\begingroup$

The number of orbits of a two-cycle $\sigma$ acting on subsets of $\{1,\dots,n\}$ is $3\cdot 2^{n-2}$. If follows that the number of orbits of $\sigma$ acting on boolean functions is $2^{2^{n-1}}\cdot 3^{2^{n-2}}$. By the Cauchy-Frobenius lemma (a.k.a. Burnside's lemma), it is then easy to see that $$ p =\frac{1}{n!}\left( 2^{2^n}+\binom n2 2^{2^{n-1}}\cdot 3^{2^{n-2}} + o\left(2^{2^{n-1}}\cdot 3^{2^{n-2}}\right)\right). $$ Thus for instance for all $\varepsilon>0$ and sufficiently large $n$ (depending on $\varepsilon$), we have $$ p<\frac{1}{n!}\left( 2^{2^n}+(1+\varepsilon)\binom n2 2^{2^{n-1}}\cdot 3^{2^{n-2}} \right). $$

Improve this answer
$\endgroup$
1
  • $\begingroup$ One question. $\binom n2 2^{2^{n-1}}\cdot 3^{2^{n-2}}$ is number of orbits when a single two-cycle acts on the set of boolean functions, right? By Cauchy-Frobenius lemma we should add number of functions that a group element leaves unchanged. I am missing something? $\endgroup$
    – Ashot
    Jun 27, 2017 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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