Thickness Distribution of Boolean Functions in 4 and 5 Variables

Abstract

This thesis explores the distribution of algebraic thickness of Boolean functions in four and five variables, that is, the minimum number of terms in the ANF of the functions in the orbit of a Boolean function, through all affine transformations. The calculation is completed computationally, and the designed programs are explained thoroughly, and listed as appendices in full. A class of Boolean functions is defined, the rigid functions, that is relevant to algebraic thickness, and -- as will be shown -- is very useful in revealing the algebraic thickness distribution. From rigid functions within the same orbit, the minimum function is chosen as a representative, and the method of this choice is presented. Additionally, a complete analysis of some complexity properties (e.g., nonlinearity) of all relevant orbits of Boolean functions is calculated and listed, with comparisons to a lower number of variables. Some properties of these rigid functions are also presented, and proven.