PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 100(114) (2016), 95–99 DOI: 10.2298/PIM1614095C

ON THE NUMBER OF EQUIVALENCE CLASSES OF INVERTIBLE BOOLEAN FUNCTIONS UNDER ACTION OF PERMUTATION OF VARIABLES ON DOMAIN AND RANGE

Marko Carić and Miodrag Živković

Abstract. Let V_{n} be the number of equivalence classes of invertible maps from {0, 1}^{n} to {0, 1}^{n}, under action of permutation of variables on domain and range. So far, the values V_{n} have been known for n ⩽ 6. This paper describes the procedure by which the values of V_{n} are calculated for n ⩽ 30.

1. Introduction

Let V_{n} be the number of equivalence classes of invertible maps from {0, 1}^{n} to {0, 1}^{n}, under action of permutation of variables on domain and range. Lorens [1] gave a method for calculating the number of equivalence classes of invertible Boolean functions under the following group operations on the input and output variables: complementation, permutation, composition of complementation and permutation, linear transformations and affine transformations. In particular, he calculated the values V_{n} for n ⩽ 5. Irvine [4] in 2011 calculated V_{6} (the sequence A000653). In this paper using a more efficient procedure, the values V_{n} are calculated for n ⩽ 30.

2. Notation

Let S_{r} denote symmetric group on r letters. Consider a set of vectorial invertible Boolean functions (hereinafter referred to as functions), i.e., the set S_{N} of permutations of B_{n} = {0, 1}^{n} where N = 2^{n}. The function F ∈ S_{N} maps the n-tuple X = (x_{1}, …, x_{n}) ∈ B_{n} into Y = (y_{1}, …, y_{n}) = F (X). For some permutation σ ∈ S_{n}, the result of its action on X = (x_{1}, …, x_{n}) ∈ B_{n} is σ′(X) = (x_{σ(1)} , …, x_{σ(n)} ) ∈ B_{n}.

An arbitrary pair (ρ, σ) ∈ S_{n}^{2} determines mapping T_{ρ,σ} : S_{N} → S_{N}, defined by T_{ρ,σ} (F) = ρ′ ∘ F ∘ σ′ where F ∈ S_{N}; in other words, if F′ = T_{ρ,σ} (F) then F′(X) = ρ′(F (σ′(X))) for all X ∈ B_{n}. The set of all mappings T_{ρ,σ} with respect to composition is a subgroup of S_{N!}.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 06E30.

Key words and phrases: invertible Boolean functions, number of equivalence classes, permutation group.

Communicated by Žarko Mijajlović.

The two functions F, H ∈ S_{N} are considered equivalent if there exist permutations ρ, σ ∈ S_{n} such that H = T_{ρ,σ} (F), i.e., if they differ only by a permutation of input or output variables.

Let ι denote the identity permutation. Every permutation σ ∈ S_{n} uniquely determines the permutation σ′ ∈ S_{N}. Let S′_{n} denote the subgroup of S_{N} consisting of all permutations σ′corresponding to permutations σ ∈ S_{n}. The mapping σ ↦ σ′ is a monomorphism from S_{n} to S_{N} (see [2]).

Let σ ∈ S_{r}. Let p_{i}, 1 ⩽ i ⩽ r, denote the number of cycles of length i in a cycle decomposition of σ; here ∑ _{i=1}^{r} ip_{i} = r. The cycle index monomial of σ is the product ∏ _{i=1}^{r} t_{i}^{p_{i}} where t_{i}, 1 ⩽ i ⩽ r, are independent variables. It can be equivalently described by the vector spec(σ) = p = (p_{1}, p_{2}, …, p_{r}). For an arbitrary positive integer n let P_{n} = {(p_{1}, p_{2}, …, p_{n}) | p_{i} ⩾ 0, ∑ _{i=1}^{n} ip_{i} = n} denote the set of partitions of n. For some p ∈ P_{n} let S_{n,p} = {σ ∈ S_{n} | spec(σ) = p}. An arbitrary partition p corresponds to the decomposition n = k_{p,1} +k_{p,2} +⋯ +k_{p,m(p)} into positive summands k_{p,1} ⩾ k_{p,2} ⩾ ⋯⩾ k_{p,m(p)} > 0 where summand i = n, n − 1, …, 1 in this sum appears p_{i} times.

Let ⟨r, s⟩ and (r, s) denote the least common multiple and the greatest common divisor of r and s, respectively.

3. Preliminaries

The calculation of V_{n} is based on the following known facts (see e.g., [1–3]):

(1) The cardinality of S_{n,p} equals to

|S_{n,p} | = \frac{n!}{∏ _{i} i^{p_{i}} p_{i}!}.

(2) Let σ_{1}, σ_{2} ∈ S_{n} be permutations such that spec(σ_{1}) = spec(σ_{2}). Then spec(σ′_{1}) = spec(σ′_{2}). In other words, permutations with the same cycle index in S_{n} induce the permutations with the same cycle index in S′_{n}.

(3) The permutation T_{ρ,σ} has at least one fixed point if and only if spec(σ) = spec(ρ).

(4) Let σ ∈ S_{n,p} and let spec(σ′) = p′ = (p′_{1}, p′_{2}, …, p′_{N}). The number of fixed points of T_{σ,σ} is

N_{p} = ∏_{i} i^{p′_{i}}p′_{i}!.

(5) If σ ∈ S_{n} is a cyclic permutation (a permutation having only one cycle of the length n), then the cycle index monomial of the permutation σ′ is

∏_{d|n} f_{d}^{e(d)} ,

where the numbers e(k), k ⩾ 1 are defined by the recurrent relation

e(k) = \frac{1}{k}( 2^{k} − ∑_{d|k,d<k} d · e(d)) , k > 1.

with the initial value e(1) = 2.

(6) If α is a permutation on a set X with |X| = a and α has a cycle index monomial f_{1}^{j_{1}} ⋯ f_{a}^{j_{a}} , and β is a permutation on Y with |Y | = b and β has a cycle index monomial f_{1}^{k_{1}} ⋯ f_{b}^{k_{b}}, then the permutation (α, β) acting on X × Y by the rule

(α, β)(x, y) = (α(x), β(y))

has cycle index monomial given by

( ∏_{p=1}^{a} f_{p}^{j_{p}} ) ( ∏_{q=1}^{b} f_{q}^{k_{q}} ) = ∏_{p=1}^{a} ∏_{q=1}^{b} (f_{p}^{j_{p}} × f_{q}^{k_{q}}) = ∏_{p=1}^{a} ∏_{q=1}^{b} f_{⟨p,q⟩}^{j_{p} k_{q}(p,q)} .

4. The number of equivalence classes

The value of V_{n} is determined by the following theorem.

Theorem 4.1. For an arbitrary p ∈ P_{n} let σ ∈ S_{n,p}. If spec(σ′) = (p′_{1}, …, p′_{n}), then

(4.1)  V_{n} = ∑_{p∈P_{n}} \frac{∏ _{i} i^{p′_{i}}p′_{i}!}{( ∏ _{i} i^{p_{i}} p_{i}!)^{2}} .

Proof. The permutation F ∈ S_{N} is a fixed point of T_{ρ,σ} if T_{ρ,σ} (F (X)) = F (X) holds for all X ∈ B_{n}. Let I(ρ, σ) be a number of fixed points of T_{ρ,σ} . By the Frobenius lemma (see e.g. [1]) the number of equivalence classes is equal to

V_{n} = \frac{1}{(n!)^{2}} ∑_{σ∈S_{n}} ∑_{ρ∈S_{n}} I(ρ, σ) = \frac{1}{(n!)^{2}} ∑_{p∈P_{n}} ∑_{ρ∈S_{n,p}} ∑_{q∈P_{n}} ∑_{σ∈S_{n,q}} I(ρ, σ).

By the facts (2)–(4) from Preliminaries, the number of fixed points of T_{ρ,σ} corresponding to fixed permutations ρ ∈ S_{n,p}, σ ∈ S_{n,q} is equal to

I(ρ, σ) = \{ \begin{matrix}0, & p ≠ q \\ N_{p}, & p = q \end{matrix}

Therefore

V_{n} = \frac{1}{(n!)^{2}} ∑_{p∈P_{n}} ∑_{ρ∈S_{n,p}} ∑_{q∈\{p\}} ∑_{σ∈S_{n,p}} N_{p} = \frac{1}{(n!)^{2}} ∑_{p∈P_{n}} ∑_{ρ∈S_{n,p}} ∑_{σ∈S_{n,p}} N_{p}

= \frac{1}{(n!)^{2}} ∑_{p∈P_{n}} N_{p} ∑_{ρ∈S_{n,p}} ∑_{σ∈S_{n,p}} 1 = \frac{1}{(n!)^{2}} ∑_{p∈P_{n}} N_{p} · |S_{n,p} |^{2}

= ∑_{p∈P_{n}} \frac{∏ _{i} i^{p′_{i}}p′_{i}!}{( ∏ _{i} i^{p_{i}} p_{i}!)^{2}} .  □

By induction the following generalization of the fact (6) can be proved. If α_{i} is permutation on Z_{i}, |Z_{i}| = k_{i}, i = 1, …, n, and if the cycle index monomial of α_{i} is f_{1}^{y_{i,1}} ⋯ f_{k_{i}}^{y_{i,k_{i}}} , then the permutation (α_{1}, …, α_{n}) acting on Z_{1} × Z_{2} × ⋯× Z_{n} by the rule

(α_{1}, …, α_{n})(z_{1}, …, z_{n}) = (α_{1}(z_{1}), …, α_{n}(z_{n}))

has cycle index monomial given by

(4.2)  \begin{aligned}_{i=1}^{n} ( ∏_{z_{i} =1}^{k_{i}} f_{z_{i}}^{y_{i,z_{i}}} ) & = ∏_{z_{1} =1}^{k_{1}} ∏_{z_{2} =1}^{k_{2}} ⋯ ∏_{z_{n} =1}^{k_{n}} _{i=1}^{n} f_{z_{i}}^{y_{i,z_{i}}} \\ & = ∏_{z_{1} =1}^{k_{1}} ∏_{z_{2} =1}^{k_{2}} ⋯ ∏_{z_{n} =1}^{k_{n}} f_{⟨z_{1} ,z_{2} ,...,z_{n} ⟩}^{∏ _{i=1}^{n} (z_{i} y_{i,z_{i}} )/⟨z_{1} ,z_{2} ,...,z_{n} ⟩} \end{aligned}

The proof is based on the fact, also proved by induction, that the cycle index monomial of the direct product of n permutations with cycle index monomials f_{z_{i}}^{y_{i}} , 1 ⩽ i ⩽ n is equal to

_{i=1}^{n} f_{z_{i}}^{y_{i}} = f_{⟨z_{1} ,z_{2} ,...,z_{n} ⟩}^{∏ _{i=1}^{n} (z_{i} y_{i} )/⟨z_{1} ,z_{2} ,...,z_{n} ⟩}

Using this generalization, the following theorem shows how to obtain the cycle index p′ of σ′, used in previous theorem.

Theorem 4.2. Let p ∈ P_{n} be an arbitrary partition and let σ ∈ S_{n,p}. Let σ = α_{1}α_{2} …α_{m} be a decomposition of σ into disjoint cycles. Let the length of α_{i} be k_{i}, 1 ⩽ i ⩽ m. The cycle index monomial ∏ _{i} f_{i}^{p′_{i}} of the corresponding σ′ is given by

_{i=1}^{m} ( ∏_{z_{i} |k_{i}} f_{z_{i}}^{e(z_{i} )} ) = ∏_{z_{1} |k_{1}} ∏_{z_{2} |k_{2}} ⋯ ∏_{z_{m} |k_{m}} f_{⟨z_{1} ,z_{2} ,...,z_{m} ⟩}^{∏ _{i=1}^{m} z_{i} e(z_{i} )/⟨z_{1} ,z_{2} ,...,z_{m} ⟩} ≡ ∏_{i} f_{i}^{p′_{i}}.

Proof. The cycle of length k_{i} in σ induces the product of cycles in σ′ with the cycle index monomial ∏ _{z_{i} |k_{i}} f_{z_{i}}^{e(z_{i} )} . The product of permutations with cycle index monomial ∏ _{i=1}^{n} t_{i}^{p_{i}} = ∏ _{i=1}^{m} t_{k_{i}} in σ induces a permutation with the cycle index monomial _{i=1}^{m} ∏ _{z_{i} |k_{i}} f_{z_{i}}^{e(z_{i} )} in σ′. The cycle index of σ′ is then obtained using (4.2)

∏_{i} f_{i}^{p′_{i}} = ∏_{z_{1} |k_{1}} ∏_{z_{2} |k_{2}} ⋯ ∏_{z_{m} |k_{m}} f_{⟨z_{1} ,z_{2} ,...,z_{m} ⟩}^{∏ _{i=1}^{m} z_{i} e(z_{i} )/⟨z_{1} ,z_{2} ,...,z_{m} ⟩} .  □

The following diagram displays the dependence of the computation time on n. More precisely, the natural logarithms of the two times (in seconds), denoted by T_{n} and T′_{n}, respectively, are displayed—the time needed to compute V_{n}, and the time needed to compute only cycle indexes of σ ∈ S_{n,p} and σ′ for all partitions p ∈ P_{n}. It is seen that the most time-consuming part of the algorithm is the calculation including large numbers.

Figure 1. Computation time.

5. Acknowledgement

We are greatly indebted to the anonymous referee for many useful comments.

References

1. C. S. Lorens, Invertible Boolean functions, IEEE Trans. Electron. Comput. EC-13 (1964), 529–541.

2. M. A. Harrison, The number of transitivity sets of boolean functions, J. Soc. Ind. Appl. Math. 11(3) (1963), 806–828.

3. M. A. Harrison, Counting theorems and their applications to switching theory, Chapter 4 in A. Mukhopadyay (ed.), Recent Developments in Switching Functions, Academic Press, New York, 1971, 85–120.

4. The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org , 2010.

Advanced School of Electrical Engineering Applied Studies (Received 06 01 2016) Belgrade (Revised 03 02 2016 and 23 04 2016) Serbia

caric.marko@gmail.com

Faculty of Mathematics Department of Informatics University of Belgrade Serbia

ezivkovm@matf.bg.ac.rs