A polynomial decomposition of Boolean functions
Some results on polynomial decompositions of Boolean functions with respect to various systems of Boolean functions are deduced. For example, if \(\{g_ \tau (x,y)\}\) is a system of Boolean functions such that the matrix \((\alpha_{\sigma\tau})\) is nondegenerate, where \(\alpha_{\sigma\tau}=(g_ \tau (\sigma,y))'_ y\) (the derivative of a Boolean function \(f(x,y)\) with respect to the variable \(y\) is, by definition, \(f'_ y (x,y)= f(x,0) \oplus f(x,1))\), then any Boolean function \(f(x,z)\) can be represented in the form \[ f(x,z)= \sum_ \sigma \sum_ \tau \beta_{\sigma\tau} (g_ \tau (x,f(\sigma, z))\oplus g_ \tau(x,0)), \] where \((\beta_{\sigma\tau})^ t= (\alpha_{\sigma\tau})^{-1}\), the vectors \(x\), \(\tau\), \(\sigma\), 0 are one-dimensional, and \(z\) has an arbitrary dimension. Other simplified decompositions are obtained whenever the functions \(g_ \tau (x,y)\) are nondegenerate (this notion implies a differential Boolean operator defined inductively in the paper).
scientific article; zbMATH DE number 567869