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.

Bibliographie

[1] Cheremushkin A. V., “Methods of affine and linear classification of binary functions”, Tr. Diskr. Mat., 4, 2001, 273–314 (in Russian)

[2] Dixon L. E., Linear Groups with Exposition Galois Field Theory, Leipzig, 1901; 2nd ed., Dover Publications, N.Y., 1958

[3] Cheremushkin A. V., “A condition for uniqueness of linear decomposition of a Boolean function into disjunctive sum of indecomposable functions”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2017, no. 10, 55–56 (in Russian) | DOI

[4] Cheremushkin A. V., “On linear decomposition of Boolean functions”, Prikladnaya Diskretnaya Matematika, 2016, no. 1(31), 46–56 (in Russian) | DOI | MR

[5] Cheremushkin A. V., “The uniqueness of the binary function decomposition in a unrepeated product of non-linear irreducible factors”, Lesnoy vestnik, 2004, no. 4(35), 86–90 (in Russian)