Abstract:
Let f:GF(2)n→GF(2) be a Boolean function, n⩾2, and Us be a set of Boolean functions f of degree degf⩽s. Here is a consideration of the disjunctive decomposition of f into sum and products modulo Us 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 GF(2)n are essential modulo Us 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.
Citation:
A. V. Cheremushkin, “Linear decomposition of Boolean functions into a sum or a product of components”, Prikl. Diskr. Mat., 2018, no. 40, 10–22