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
    Commented 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
    Commented Feb 5, 2017 at 20:24
  • $\begingroup$ So you mean "boolean functions on boolean functions on $n$ elements"? $\endgroup$
    – Ehud Meir
    Commented 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
    Commented 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
    Commented Jun 27, 2017 at 8:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .