¹Financial University under the Government of the Russian Federation, Moscow, Russian Federation

In this paper, we present concave continuations of discrete functions defined on the vertices of an n-dimensional unit cube, an n-dimensional arbitrary cube, and an n-dimensional arbitrary parallelepiped. It is constructively proved that, firstly, for any discrete function f D defined on the vertices of G, where G is one of these three sets, the cardinality of the set of its concave continuations on G is equal to infinity, and, secondly, there is a function f N R that is the minimum among all its concave continuations on G. The uniqueness and continuity of the function f N R on G are also proved.

Barotov D. N. Concave Continuations of Boolean-like Functions and Some of Their Properties. The Bulletin of Irkutsk State University. Series Mathematics, 2025, vol. 51, pp. 82–100. (in Russian)

https://doi.org/10.26516/1997-7670.2025.51.82

1. Barotov D.N. Convex continuation of a Boolean function and its applications. Journal of Applied and Industrial Mathematics, 2024, vol. 18, no. 1, pp. 1–9. https://doi.org/10.1134/S1990478924010010
2. Barotov D.N. On the existence and properties of convex continuations of Boolean functions. Mathematical Notes, 2024, vol. 115, no. 4, pp. 489–505. https://doi.org/10.1134/S0001434624030210
3. Barotov D.N. Concave continuations of Boolean functions and some of their properties and applications. The Bulletin of Irkutsk State University. Series Mathematics, 2024, vol. 49, pp. 105–123. https://doi.org/10.26516/1997- 7670.2024.49.105 (in Russian)
4. Barotov D.N., Barotov R.N. Construction of smooth convex extensions of Boolean functions. Vestnik rossiyskikh universitetov. Matematika = Russian Universities Reports. Mathematics, 2024, vol. 29, no. 145, pp. 20–28. https://doi.org/10.20310/2686-9667-2024-29-145-20-28 (in Russian)
5. Barotov D.N., Barotov R.N. Polylinear Continuations of Some Discrete Functions and an Algorithm for Finding Them. Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie), 2023, vol. 24, pp. 10–23. https://doi.org/10.26089/NumMet.v24r102 (in Russian)
6. Barotov D.N., Muzafarov D.Z., Barotov R.N. On one method for solving systems of Boolean algebraic equations. International Electronic Journal of Mathematics Education, 2021, vol. 8, no. 1, pp. 17–23. (in Russian)
7. Barotov D.N., Muzafarov D.Z., Barotov R.N. Algebraic method for checking bit parity. Intellectual information technologies and intellectual business. Vologda, Vologda State University Publ., 2021, pp. 193–195. (in Russian)
8. Minu M. Mathematical programming. Theory and algorithms. Moscow, Nauka Publ., 1990, 488 p. (in Russian)
9. Faizullin R.T., Dul’keit V.I., Ogorodnikov Yu.Yu. Hybrid method for the approximate solution of the 3-satisfiability problem associated with the factorization problem. Trudy Inst. Mat. i Mekh. UrO RAN., 2013, vol. 19, no. 2. pp. 285–294. (in Russian)
10. Abdel-Gawad A.H., Atiya A.F., Darwish N.M. Solution of systems of Boolean equations via the integer domain.Information Sciences, 2010, vol. 180, no. 2, pp. 288–300. https://doi.org/10.1016/j.ins.2009.09.010
11. Bard G.V. Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis. University of Maryland, College Park, 2007.
12. Barotov D., Osipov A., Korchagin S., Pleshakova E., Muzafarov D., Barotov R., Serdechnyy D. Transformation method for solving system of Boolean algebraic equations. Mathematics, 2021, vol. 9, 3299. https://doi.org/10.3390/math9243299
13. Barotov D.N. Target Function without Local Minimum for Systems of Logical Equations with a Unique Solution. Mathematics, 2022, vol. 10, 2097. https://doi.org/10.3390/math10122097
14. Barotov D.N., Barotov R.N. Polylinear Transformation Method for Solving Systems of Logical Equations. Mathematics, 2022, vol. 10, 918. https://doi.org/10.3390/math10060918
15. Barotov D.N., Barotov R.N., Soloviev V., Feklin V., Muzafarov D., Ergashboev T., Egamov K. The Development of Suitable Inequalities and Their Application to Systems of Logical Equations. Mathematics, 2022, vol. 10, 1851. https://doi.org/10.3390/math10111851
16. Brown F.M. Boolean Reasoning: The logic of Boolean Equations. Kluwer Academic Publishers, Boston, 1990.
17. Burek E., Wronski M., Mank K., Misztal M. Algebraic attacks on block ciphers using quantum annealing. IEEE Transactions on Emerging Topics in Computing, 2022. vol. 10, no. 2. pp. 678–689. https://doi.org/10.1109/TETC.2022.3143152
18. Faugere J.C., Joux A. Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Grobner bases. Annual International Cryptology Conference. Berlin, Heidelberg, Springer Berlin Heidelberg, 2003, pp. 44–60.
19. Faugere J.C. A new efficient algorithm for computing Grobner bases (F4). Journal of pure and applied algebra, 1999, vol. 139, no. 1-3, pp. 61–88. https://doi.org/10.1016/S0022-4049(99)00005-5
20. Gu J. Global optimization for satisfiability (SAT) problem. IEEE Transactions on Knowledge and Data Engineering, 1994, vol. 6, no. 3, pp. 361–381. https://doi.org/10.1109/69.334864
21. Gu J., Gu Q., Du D. On optimizing the satisfiability (SAT) problem. Journal of Computer Science and Technology, 1999, vol. 14, no. 1, pp. 1–17. https://doi.org/10.1007/BF02952482
22. Hammer P.L., Rudeanu S. Boolean Methods in Operations Research and Related Areas. Springer Verlag, Berlin, 1968.
23. Jensen J.L.W.V. Sur les fonctions convexes et les inegalites entre les valeurs moyennes. Acta mathematica, 1906, vol. 30, no. 1, pp. 175–193. https://doi.org/10.1007/BF02418571
24. Meyer R.R. Continuity properties of linear programs. Computer Sciences Department, University of Wisconsin, Madison, Wisconsin 53706, Technical Report, no. 373, 1979.
25. Pakhomchik A.I., Voloshinov V.V., Vinokur V.M., Lesovik G.B. Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis. Algorithms, 2022, vol. 15, 33. https://doi.org/10.3390/a15020033