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

#### Abstract

Knowledge on 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

this 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 →∞, almost 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 of a random Boolean

function having 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 4 test files for

representativeness; when creating benchmark files of Boolean functions.

#### Keywords

### Refbacks

- There are currently no refbacks.

ISSN 1314-7897 - Online

ISSN 1312-6555 - Print