This article is cited in
1 paper
Theoretical Backgrounds of Applied Discrete Mathematics
Linear decomposition of Boolean functions into a sum or a product of components
A. V. Cheremushkin Technology Federal State Unitary Enterprise "Research Institute Kvant", Moscow, Russia
Abstract:
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.
Keywords:
Boolean functions, disjunctive decomposition, disjunctive sum, disjunctive products, linear transformation.
UDC:
519.719.325
DOI:
10.17223/20710410/40/2
Fulltext:
PDF file (669 kB)