Linear decomposition of Boolean functions into a~sum or a~product of components

A. V. Cheremushkin

Prikladnaâ diskretnaâ matematika, no. 2 (2018), pp. 10-22

Résumé

Let $f\colon\operatorname{GF}(2)^n\to\operatorname{GF}(2)$ be a Boolean function, $n\ge2$, and $\mathcal U_s$ be a set of Boolean functions $f$ of degree $\operatorname{deg}f\le s$. Here is a consideration of the disjunctive decomposition of $f$ into sum and products modulo $\mathcal U_s$ of Boolean functions after a linear substitution on arguments. The main result is the following: if all arguments of the functions $f(xA)$ under linear substitutions $A$ of the vector space $\operatorname{GF}(2)^n$ are essential modulo $\mathcal U_s$ and $f$ may be represented as disjunctive sum $f\equiv f_1\oplus\dots\oplus f_m\pmod{\mathcal U_s}$, where $m$ is maximal, then subsequent direct sum of subspaces $\operatorname{GF}(2)^n=V^{(1)}+\dots+V^{(m)}$ is unique and invariant under stabilizer group of the function $f$ in general linear group. The article contains analogous result describing sufficient uniqueness condition for disjunctive products $f\equiv f_1\dots f_m\pmod{\mathcal U_s}$, namely, every function $f_i$ has no affine multipliers and the set $\{a\in V_i\colon f_i(x\oplus a)\oplus f_i(x)\ \text{has affine multipliers}\}$ generates the whole subspace $V_i$, $i=1,\dots,m$. For instance, this class of functions contains a nondegenerated quadratic forms.

Détail

Keywords: Boolean functions, disjunctive decomposition, disjunctive sum, disjunctive products, linear transformation.