Distribution of The Boolean Functions of n Variables According to Their Algebraic Degrees

Authors

  • Valentin Bakoev Faculty of Mathematics and Informatics, University of Veliko Tarnovo, Bulgaria

DOI:

https://doi.org/10.55630/sjc.2019.13.17-26

Keywords:

Boolean function, cryptography, algebraic degree, enumeration, distribution

Abstract

Knowledge about the enumeration and distribution of Boolean functions according to their algebraic degrees is important for the theory as well as for its applications. As of now, this knowledge is not complete: for example, it is well-known that half of all Boolean functions have a maximal algebraic degree. In the present paper, a formula for the number of all Boolean functions of n variables and algebraic degree = k is derived. A direct consequence from it is the assertion (formulated already by Claude Carlet) that when n to infty, almost a half of all Boolean functions of n variables have an algebraic degree = n-1. The results obtained by this formula were used in creating the sequence A319511 in the OEIS. The discrete probability a random Boolean function to have a certain algebraic degree is defined and the corresponding distribution is computed, for 3 <= n <= 10. Four applications are considered: at the design and analysis of efficient algorithms for exact or probabilistic computing the algebraic degree of Boolean functions; when checking four test files for representativeness; when creating benchmark files of Boolean functions.

Downloads

Published

2019-10-03

Issue

Section

Articles