A condition for uniqueness of linear decomposition of a Boolean function into disjunctive sum of indecomposable functions

A. V. Cheremushkin

Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 55-56

Résumé

Let $n\geq1$, $V_n=[\operatorname{GF}(2)]^n$, that is, $V_n$ is the $n$-dimensional vector space over the field $\operatorname{GF}(2)$, and $H_n$ be the group of shifts $\sigma_a\colon V_n\to V_n$ of the space $V_n$ defined as $\sigma_a(x)=a\oplus x$. Let $\mathcal F_n$ be the set of all Boolean functions $f\colon V_n \to \operatorname{GF}(2)$ in $n$ variables and, for integer $t\geq0$, let $\mathcal U_t$ be the set of all functions in $\mathcal F_n$ of degree not more than $t$. Let, at last, $(H_n)_f^{(t)}=\{\sigma_a\colon\sigma_a\in H_n, f(a\oplus x)\oplus f(x)\in\mathcal U_t\}$. We say that functions $g$ and $h$ in $\mathcal F_n$ are equivalent modulo $\mathcal U_t$ and write $g\equiv h\pmod{\mathcal U_t}$ if $g\oplus h\in\mathcal U_t$. Also, we say that a function $f\in\mathcal F_n$ is linearly decomposable into disjunctive sum modulo $\mathcal U_t$ if there exist a linear transformation $A$ of the vector space $V_n$, an integer $k\in\{1,2,\dots,n-1\}$, and some Boolean functions $f_1$ and $f_2$ such that, for any $x=x_1x_2\dots x_n\in V_n$, $f(xA)\equiv f_1(x_1,\dots,x_k)\oplus f_2(x_{k+1},\dots,x_n)\pmod{\mathcal U_t}$. In this case, the right part of the last equivalence is called a linear decomposition of the function $f$ into disjunctive sum modulo $\mathcal U_t$ and $f_1$, $f_2$ are the components of the decomposition. By the principle of mathematical induction, these notions are defined for every number $m\geq2$ of components in the sum and, further, just this definition of the linear decomposition of $f$ into disjunctive sum modulo $\mathcal U_t$ is meant. The main result is the following: if $s\geq2$, $(H_n)_f^{(s-1)}$ is trivial (consists only of the identical shift of $V_n$), and $f$ is linearly decomposable into disjunctive sum modulo $\mathcal U_s$, then there exists an unique linear decomposition $D$ of $f$ into disjunctive sum modulo $\mathcal U_s$ of linearly indecomposable (into disjunctive sum modulo $\mathcal U_s$) components. The term “uniqueness” of the decomposition $D$ means that any other similar decomposition of $f$ gives the same decomposition of $V_n$ into the direct sum of subspaces induced by its components that are, in turn, linearly equivalent modulo $\mathcal U_s$ to components in $D$.

Détail

Keywords: Boolean functions, disjunctive sum, linear transformation.

Bibliographie

[1] Cheremushkin A. V., “Odnoznachnost razlozheniya dvoichnoi funktsii v bespovtornoe proizvedenie nelineinykh neprivodimykh somnozhitelei”, Vestnik Moskovskogo gosudarstvennogo universiteta lesa “Lesnoi vestnik”, 2004, no. 4(35), 86–90

[2] Cheremushkin A. V., “Metody affinnoi i lineinoi klassifikatsii dvoichnykh funktsii”, Trudy po diskretnoi matematike, 4, Fizmatlit, M., 2001, 273–314

[3] Cheremushkin A. V., “K voprosu o lineinoi dekompozitsii dvoichnykh funktsii”, Prikladnaya diskretnaya matematika, 2016, no. 1(31), 46–56 | MR