On the order of smoothness of the maximal convex continuation of a Boolean function
https://doi.org/10.22405/2226-8383-2025-26-3-58-70
Abstract
This paper is devoted to establishing the order of smoothness of 𝑓𝑁𝑅(𝑥1, 𝑥2, ..., 𝑥𝑛) — the largest convex continuation to [0, 1]𝑛 of any Boolean function 𝑓𝐵(𝑥1, 𝑥2, ..., 𝑥𝑛). As a result of the study, for each Boolean function 𝑓𝐵(𝑥1, 𝑥2, ..., 𝑥𝑛), the order of differentiability of 𝑓𝑁𝑅(𝑥1, 𝑥2, ..., 𝑥𝑛) — the corresponding greatest convex continuation to [0, 1]𝑛 — was established, namely, firstly, the greatest convex continuation 𝑓𝑁𝑅(𝑥1, 𝑥2, ..., 𝑥𝑛) was estimated from both sides so that, which implies the continuity of 𝑓𝑁𝑅(𝑥1, 𝑥2, ..., 𝑥𝑛) on [0, 1]𝑛 for any
natural 𝑛, and secondly, it was proved that if the number of essential variables of the Boolean function 𝑓𝐵(𝑥1, 𝑥2, ..., 𝑥𝑛) is less than two, then on [0, 1]𝑛 the greatest convex continuation 𝑓𝑁𝑅(𝑥1, 𝑥2, ..., 𝑥𝑛) is infinite differentiable, and if there are at least two, then on [0, 1]𝑛 the largest convex continuation 𝑓𝑁𝑅(𝑥1, 𝑥2, ..., 𝑥𝑛) is not differentiable, i.e. it is only continuous.
About the Authors
Dostonjon Numonjonovich Barotov
Financial University under the Government of the Russian Federation
Russian Federation
Russian Federation
Ruziboy Numonjonovich Barotov
Khujand state university named after academician Bobojon Gafurov
Tajikistan
Tajikistan
References
1. Brown, F.M. 1990, Boolean Reasoning: The logic of Boolean Equations, Boston: Kluwer Academic Publishers.
2. Barotov, D.N. & Barotov, R.N. 2024, “On a reduction of the system of Boolean equations to an equivalent system of polynomial equations”, Mathematical Structures and Modeling, no. 1(69), pp. 5–17. doi: 10.24147/2222-8772.2024.1.5-17.
3. Hammer, P.L. & Rudeanu, S. 1968, Boolean Methods in Operations Research and Related Areas, Berlin: Springer Verlag.
4. Barotov, D.N. & Barotov, R.N. 2024, “Construction of smooth convex extensions of Boolean functions”, Russian Universities Reports. Mathematics, vol. 29, no. 145, pp. 20–28. doi:10.20310/2686-9667-2024-29-145-20-28.
5. Bard, G.V. 2007, Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis, College Park: University of Maryland.
6. Faugere, J.C. & Joux, A. 2003, “Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Grobner bases”, in Annual International Cryptology Conference, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 44–60.
7. Armknecht, F. 2004, “Improving fast algebraic attacks”, in Fast Software Encryption: 11-th International Workshop, FSE 2004, Delhi, India, February 5-7, 2004. Revised Papers 11, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 65–82.
8. Bardet, M., Faugere, J.C., Salvye, B. & Spaenlehauer, P.J. 2013, “On the complexity of solving quadratic Boolean systems”, Journal of Complexity, vol. 29, no. 1, pp. 53–75. doi:10.1016/j.jco.2012.07.001.
9. Courtois, N.T. 2003, “Fast algebraic attacks on stream ciphers with linear feedback”, in Advances in Cryptology-CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003. Proceedings 23, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 176–194.
10. Liu, M., Lin, D. & Pei, D. 2011, “Fast algebraic attacks and decomposition of symmetric Boolean functions”, IEEE Transactions on Information Theory, vol. 57, no. 7, pp. 4817–4821. doi:10.1109/TIT.2011.2145690.
11. Gu, J. 1990, “How to Solve Very Large-Scale Satisfiability (VLSS) Problems”, Technical Report UCECETR-90-002, University of Calgary, Calgary.
12. Gu, J. 1992, “On optimizing a search problem”, Artificial Intelligence Methods and Applications, pp. 63–105. doi:10.1142/9789814354707_0002.
13. Barotov, D.N., Muzafarov, D.Z. & Barotov, R.N. 2021, “On one method for solving systems of Boolean algebraic equations”, Mod. Math. Concept Innov. Math. Educ., vol. 8, pp. 17–23.
14. Gu, J. 1994, “Global optimization for satisfiability (SAT) problem”, IEEE Transactions on Knowledge and Data Engineering, vol. 6, no. 3, pp. 361–381. doi:10.1109/69.334864.
15. Gu, J., Gu, Q. & Du, D. 1999, “On optimizing the satisfiability (SAT) problem”, Journal of Computer Science and Technology, vol. 14, no. 1, pp. 1–17. doi:10.1007/BF02952482.
16. Barotov, D., Osipov, A., Korchagin, S., Pleshakova, E., Muzafarov, D., Barotov, R. & Serdechnyy, D. 2021, “Transformation method for solving system of Boolean algebraic equations”, Mathematics, vol. 9, p. 3299. doi:10.3390/math9243299.
17. Pakhomchik, A.I., Voloshinov, V.V., Vinokur, V.M. & Lesovik, G.B. 2022, “Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis”, Algorithms, vol. 15, p. 33. doi:10.3390/a15020033.
18. Burek, E., Wronski, M., Mank, K. & Misztal, M. 2022, “Algebraic attacks on block ciphers using quantum annealing”, IEEE Transactions on Emerging Topics in Computing, vol. 10, no. 2, pp. 678–689. doi:10.1109/TETC.2022.3143152.
19. Abdel-Gawad, A.H., Atiya, A.F. & Darwish, N.M. 2010, “Solution of systems of Boolean equations via the integer domain”, Information Sciences, vol. 180, no. 2, pp. 288–300. doi:10.1016/j.ins.2009.09.010.
20. Barotov, D.N., Barotov, R.N., Soloviev, V., Feklin, V., Muzafarov, D., Ergashboev, T. & Egamov, K. 2022, “The Development of Suitable Inequalities and Their Application to Systems of Logical Equations”, Mathematics, vol. 10, p. 1851. doi:10.3390/math10111851.
21. Faugere, J.C. 1999, “A new efficient algorithm for computing Grobner bases (F4)”, Journal of Pure and Applied Algebra, vol. 139, no. 1-3, pp. 61–88. doi:10.1016/S0022-4049(99)00005-5.
22. Faugere, J.C. 2002, “A new efficient algorithm for computing Grobner bases without reduction to zero (F5)”, Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, pp. 75–83.
23. Faizullin, R.T., Dul’keit, V.I. & Ogorodnikov, Yu.Yu. 2013, “A hybrid search method for the approximate solution of the 3-satisfiability problem associated with the factorization problem”, Trudy Instituta Matematiki i Mekhaniki, vol. 19, no. 2, pp. 285–294.
24. Barotov, D.N. & Barotov, R.N. 2023, “Polylinear continuations of some discrete functions and an algorithm for finding them”, Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie), vol. 24, pp. 10–23. doi:10.26089/NumMet.v24r102.
25. Barotov, D.N. 2022, “Target Function without Local Minimum for Systems of Logical Equations with a Unique Solution”, Mathematics, vol. 10, p. 2097. doi:10.3390/math10122097.
26. Barotov, D.N. & Barotov, R.N. 2022, “Polylinear Transformation Method for Solving Systems of Logical Equations”, Mathematics, vol. 10, p. 918. doi:10.3390/math10060918.
27. Barotov, D.N. 2024, “Convex Continuation of a Boolean Function and Its Applications”, Journal of Applied and Industrial Mathematics, vol. 18, pp. 1–9. doi:10.1134/S1990478924010010.
28. Barotov, D.N. 2024, “On the Existence and Properties of Convex Extensions of Boolean Functions”, Mathematical Notes, vol. 115, no. 4, pp. 489–505. doi:10.1134/S0001434624030210.
29. Barotov, D.N. & Sudakov, V.A. 2024, “On inequalities between convex, concave, and polylinear continuations of Boolean functions”, Preprints of the M.V. Keldysh Institute of Applied Mathematics, no. 30, pp. 1–13. doi:10.20948/prepr-2024-30.
30. Barotov, D.N. 2024, “Concave Continuations of Boolean Functions and Some of Their Properties and Applications”, The Bulletin of Irkutsk State University. Series Mathematics, vol. 49, pp. 105–123. (in Russian). doi:10.26516/1997-7670.2024.49.105.
31. Barotov, D.N. 2024, “Convex Continuations of Some Discrete Functions”, Journal of Applied and Industrial Mathematics, vol. 18, no. 3, pp. 412–423. doi:10.1134/S1990478924030049.
32. Jensen, J.L.W.V. 1906, “Sur les fonctions convexes et les in´egalit´es entre les valeurs moyennes”, Acta Mathematica, vol. 30, no. 1, pp. 175–193. doi:10.1007/BF02418571.
Review
For citations:
Barotov D.N., Barotov R.N. On the order of smoothness of the maximal convex continuation of a Boolean function. Chebyshevskii Sbornik. 2025;26(3):58-70. (In Russ.) https://doi.org/10.22405/2226-8383-2025-26-3-58-70
Views:
39
Email this article 