On extremal elements and the cardinality of the set of continuously differentiable convex extensions of a Boolean function
https://doi.org/10.18255/1818-1015-2025-2-100-109
Abstract
In this paper we study the existence of the maximal and minimal elements of the set of continuously differentiable convex extensions to $[0,1]^n$ of an arbitrary Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$ and the cardinality of the set of continuously differentiable convex extensions to $[0,1]^n$ of the Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$. As a result of the study, it was established that the cardinality of the set of continuously differentiable convex extensions to $[0,1]^n$ of an arbitrary Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$ is equal to the continuum. It is argued that for any Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$, there is no minimal element among its continuously differentiable convex extensions to $[0,1]^n$. It is proved that for any Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$, the set of its continuously differentiable convex extensions to $[0,1]^n$ has a maximal element only if the number of essential variables of the given Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$ is less than 2.
About the Authors
Dostonjon N. Barotov
Financial University under the Government of the Russian Federation
Russian Federation
Russian Federation
Ruziboy N. Barotov
Khujand State University named after academician Bobojon Gafurov
Russian Federation
Russian Federation
References
1. A. H. Abdel-Gawad, A. F. Atiya, and N. M. Darwish, “Solution of systems of Boolean equations via the integer domain,” Information Sciences, vol. 180, no. 2, pp. 288–300, 2010, doi: 10.1016/j.ins.2009.09.010.
2. G. V. Bard, Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis. University of Maryland, College Park, 2007.
3. V. K. Leontiev and E. N. Gordeev, “On the number of solutions to a system of Boolean equations,” Automation and Remote Control, vol. 82, pp. 1581–1596, 2021, doi: 10.1134/S000511792109006X.
4. E. Ishchukova, E. Maro, and P. Pristalov, “Algebraic analysis of a simplified encryption algorithm GOST R 34.12-2015,” Computation, vol. 8, no. 2, p. 51, 2020, doi: 10.3390/computation8020051.
5. A. I. Pakhomchik, V. V. Voloshinov, V. M. Vinokur, and G. B. Lesovik, “Converting of Boolean expression to linear equations, inequalities and QUBO penalties for cryptanalysis,” Algorithms, vol. 15, no. 2, p. 33, 2022, doi: 10.3390/a15020033.
6. S. Ramos-Calderer et al., “Solving systems of Boolean multivariate equations with quantum annealing,” Physical Review Research, vol. 4, no. 1, p. 013096, 2022, doi: 10.1103/PhysRevResearch.4.013096.
7. E. Burek, M. Wro'nski, K. Ma'nk, and M. Misztal, “Algebraic attacks on block ciphers using quantum annealing,” IEEE Transactions on Emerging Topics in Computing, vol. 10, no. 2, pp. 678–689, 2022, doi: 10.1109/TETC.2022.3143152.
8. J. Gu, “Global optimization for satisfiability (SAT) problem,” IEEE Transactions on Knowledge and Data Engineering, vol. 6, no. 3, pp. 361–381, 1994, doi: 10.1109/69.334864.
9. D. N. Barotov and R. N. Barotov, “Polylinear continuations of some discrete functions and an algorithm for finding them,” Numerical methods and programming, vol. 24, no. 1, pp. 10–23, 2023, doi: 10.26089/NumMet.v24r102.
10. R. T. Faizullin, V. I. Dulkeyt, and Y. Y. Ogorodnikov, “Hybrid method for the approximate solution of the 3-satisfiability problem associated with the factorization problem,” Trudy Instituta Matematiki i Mekhaniki UrO RAN, vol. 19, no. 2, pp. 285–294, 2013.
11. D. N. Barotov and R. N. Barotov, “Construction of smooth convex extensions of Boolean functions,” Russian Universities Reports. Mathematics, vol. 29, no. 145, pp. 20–28, 2024, doi: 10.20310/2686-9667-2024-29-145-20-28.
12. D. N. Barotov, “Convex continuation of a Boolean function and its applications,” Journal of Applied and Industrial Mathematics, vol. 18, no. 1, pp. 1–9, 2024, doi: 10.1134/S1990478924010010.
13. D. N. Barotov, “On the Existence and Properties of Convex Extensions of Boolean Functions,” Mathematical Notes, vol. 115, no. 3, pp. 489–505, 2024, doi: 10.1134/S0001434624030210.
14. D. N. Barotov, “Concave continuations of Boolean functions and some of their properties and applications,” Bulletin of Irkutsk State University. Series Mathematics, vol. 49, pp. 105–123, 2024, doi: 10.26516/1997-7670.2024.49.105.
15. D. N. Barotov and V. A. Sudakov, “On inequalities between convex, concave, and multilinear continuations of Boolean functions,” Keldysh Institute preprints, no. 30, pp. 1–13, 2024, doi: 10.20948/prepr-2024-30.
16. A. Salomaa, “On essential variables of functions, especially in the algebra of logic,” Annales Fennici Mathematici, no. 339, pp. 1–11, 1964, doi: 10.5186/aasfm.1964.339.
17. Y. Y. Breitbart, “Essential variables of functions of the algebra of logic,” Doklady Akademii Nauk, vol. 172, no. 1, pp. 9–10, 1967.
18. D. N. Barotov, “Convex continuations of some discrete functions,” Journal of Applied and Industrial Mathematics, vol. 18, no. 3, pp. 412–423, 2024, doi: 10.1134/S1990478924030049.
19. D. N. Barotov, “Concave Continuations of Boolean-like Functions and Some of Their Properties,” Bulletin of Irkutsk State University. Series Mathematics, vol. 51, pp. 82–100, 2025, doi: 10.26516/1997-7670.2025.51.82.
Review
For citations:
Barotov D.N., Barotov R.N. On extremal elements and the cardinality of the set of continuously differentiable convex extensions of a Boolean function. Modeling and Analysis of Information Systems. 2025;32(2):100-109. (In Russ.) https://doi.org/10.18255/1818-1015-2025-2-100-109
Views:
37
Email this article 