Starting with the fundamental work of D.E.Muller in 1954, the polynomial representations of Boolean functions are widely investigated in connection with the theory of coding and for the synthesis of circuits of digital devices. The operator approach to polynomial representations, proposed in the works of S. F. Vinokurov, made it possible, on the one hand, to uniformly describe all known types of polynomial forms of Boolean functions, and, on the other hand, to generalize them to the case of expansions by the operator images of arbitrary odd function, not only conjunction.

In the study of polynomial and, in the general case, operator forms, one of the main questions is obtaining lower and upper bounds of the complexity of the representation of Boolean functions in various classes of forms. The upper bounds of complexity are actually algorithms for minimizing Boolean functions in a particular class of forms.

The lower bounds of complexity can be divided into two types: combinatorial and effective. Combinatorial lower bounds make it possible to prove the existence of Boolean functions, having high complexity, without finding the explicit form of these functions. Effective lower bounds are based on explicit constructing Boolean functions that have high complexity in a particular class of forms.

In this paper, using an algebraic extension of a finite field of order 2, we obtain a lower bound for the complexity of Boolean functions in the class of extended operator forms. This lower bound strengthens the previously known lower bounds for this class of operator forms and is becoming asymptotically optimal if the sequence of Mersenne primes is infinite.

Aleksandr Baliuk, Cand. Sci. (Phys.–Math.), Assoc. Prof., Irkutsk State University, 1, K. Marks St., Irkutsk, 664003, Russian Federation, tel.: (3952)242210, e-mail: sacha@hotmail.ru

Baliuk A.S. Complexity Lower Bound for Boolean Functions in the Class of Extended Operator Forms. The Bulletin of Irkutsk State University. Series Mathematics, 2019, vol. 30, pp. 125-140. https://doi.org/10.26516/1997-7670.2019.30.125

1. A000043 - OEIS. The On-Line Encyclopedia of Integer Sequences. Available at: https://oeis.org/A000043
2. Baliuk A.S., Zinchenko A.S. Lower Bounds of Complexity for Polarized Polynomials over Finite Fields. Siberian Mathematical Journal, 2019, vol. 60, issue 1, pp. 1-9. https://doi.org/10.1134/S0037446619010014
3. Baliuk A.S., Yanushkovskiy G.V. Operatornye polinomial’nye formy funktsiy nad konechnymi polyami [Operator polynomial forms of functions over finite fields]. Proceedings of IX International conference ,,Diskretnye modeli v teorii upravlyayushchikh sistem“. Moscow, MAKS Press Publ., 2015, pp. 28-30. (in Russian)
4. Berndt B.C., Evans R.J., Williams K.S. Gauss and Jacobi sums. John Wiley & Sons Inc., Toronto, 1998, 600 p.
5. Frantseva A.S. Complexity of Boolean functions’ representations in classes of extended pair-generated operator forms. Siberian Electronic Mathematical Reports, 2019, vol. 16, pp. 523-541. (in Russian) https://doi.org/10.33048/semi.2019.16.034
6. Izbrannye voprosy teorii bulevykh funktsiy [Selected questions in the theory of Boolean functions]. Eds. Vinokurov S.F. and Peryazev N A. Moscow, Fizmatlit Publ., 2001, 192 p. (in Russian)
7. Lidl R., Niederreiter H. Finite Fields (Encyclopedia of Mathematics and its Applications). Cambridge University Press, England, 1984, 660 p. https://doi.org/10.1017/CBO9780511525926
8. Markelov N.K. A lower estimate of the complexity of three-valued logic functions in the class of polarized polynomials. Moscow Univ. Comput. Math. Cybern., 2012, vol. 36, issue 3, pp. 150-154. https://doi.org/10.3103/S0278641912030041
9. Muller D.E. Application of Boolean algebra to switching circuit design and to error detection. IRE Trans. Electron. Comput., 1954, vol. EC–3, issue 3, pp. 6-12. https://doi.org/10.1109/IREPGELC.1954.6499441
10. Peryazev N.A. Complexity of Boolean functions in the class of polarized polynomial forms. Algebra and Logic, 1995, vol. 34, no. 3, pp 177-179. https://doi.org/10.1007/BF02341875
11. Selezneva S.N. Upper Bound for the Length of Functions over a Finite Field in the Class of Pseudopolynomials. Computational Mathematics and Mathematical Physics, 2017, vol. 57, no. 5, pp. 898-903. https://doi.org/10.1134/S0965542517050116
12. Vinokurov S.F. Smeshannye operatory v bulevykh funktsiyakh i ikh svoystva [Mixed operators in Boolean functions and their properties]. Irkutsk, Irkutsk University, 2000, 36 p. (Series Discrete mathematics and informatics, Issue 12). (in Russian)