Выпуклые продолжения некоторых дискретных функций

Выпуклые продолжения некоторых дискретных функций

Баротов Д. Н.
Дискретный анализ и исследование операций, 31, 3, 5–23 (2024)
Скачать статью

УДК  519.8+518.25 
DOI: 10.33048/daio.2024.31.789

Аннотация:

Построены выпуклые продолжения для дискретных функций, заданных на вершинах $n$-мерного единичного куба $[0, 1]^n$, произвольного куба $[a, b]^n$ и параллелепипеда $[c_1, d_1] \times [c_2, d_2] \times \cdots \times [c_n, d_n]$. В каждом случае доказано, что, во-первых, для произвольной дискретной функции $f$, определённой на вершинах множества $\mathbb{G} \in$ {$[0, 1]^n, [a, b]^n, [c_1, d_1] \times [c_2, d_2] \times \cdots \times [c_n, d_n]$}, существует бесконечно много её выпуклых продолжений на $\mathbb{G}$ и, во-вторых, существует единственная функция вида $f_{DM} : \mathbb{G} \to \mathbb{R}$, которая является максимумом среди всех выпуклых продолжений $f$ на $\mathbb{G}$, причём $f_{DM}$ непрерывна на $\mathbb{G}$.  
Библиогр. 24.

Литература:
  1. Armario J. A. Boolean functions and permanents of Sylvester Hadamard matrices // Mathematics. 2021. V. 9, No. 2. Paper ID 177. 8 p. DOI: 10.3390/math9020177.
     
  2. Abdel-Gawad A. H., Atiya A. F., Darwish N. M. Solution of systems of Boolean equations via the integer domain // Inf. Sci. 2010. V. 180, No. 2. P. 288–300. DOI: 10.1016/j.ins.2009.09.010.
     
  3. Brown F. M. Boolean reasoning: The logic of Boolean equations. Boston: Kluwer Acad. Publ., 1990. 304 p.
     
  4. Hammer P. L., Rudeanu S. Boolean methods in operations research and related areas. Heidelberg: Springer, 1968. 330 p.
     
  5. Bard G. V. Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis: PhD Thes. College Park, MD: Univ. Maryland, 2007. 178 p.
     
  6. Faugère J.-C., Joux A. Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases // Advances in cryptology — CRYPTO 2003. Proc. 23rd Annu. Int. Cryptology Conf. (Santa Barbara, USA, Aug. 17–21, 2003). Heidelberg: Springer, 2003. P. 44–60. (Lect. Notes Comput. Sci.; V. 2729). DOI: 10.1007/978-3-540-45146-4_3.
     
  7. Armknecht F. Improving fast algebraic attacks // Fast software encryption. Rev. Pap. 11th Int. Workshop (Delhi, India, Feb. 5–7, 2004). Heidelberg: Springer, 2004. P. 65–82. DOI: 10.1007/978-3-540-25937-4_5.
     
  8. Bardet M., Faugère J.-C., Salvye B., Spaenlehauer P. J. On the complexity of solving quadratic boolean systems // J. Complex. 2013. V. 29. P. 53–75. DOI: 10.1016/j.jco.2012.07.001.
     
  9. Courtois N. T. Fast algebraic attacks on stream ciphers with linear feedback // Advances in cryptology — CRYPTO 2003. Proc. 23rd Annu. Int. Cryptology Conf. (Santa Barbara, USA, Aug. 17–21, 2003). Heidelberg: Springer, 2003. P. 176–194. (Lect. Notes Comput. Sci.; V. 2729). DOI: 10.1007/ 978-3-540-45146-4_11.
     
  10. Faugère J.-C. A new efficient algorithm for computing Gröbner bases (F4) // J. Pure Appl. Algebra. 1999. V. 139. P. 61–88. DOI: 10.1016/S0022-4049(99) 00005-5.
     
  11. Faugère J.-C. A new efficient algorithm for computing Gröbner bases without reduction to zero (F5) // Proc. 2002 Int. Symp. Symbolic and Algebraic Computation (Lille, France, July 7–10, 2002). New York: ACM, 2002. P. 75–83. DOI: 10.1145/780506.780516.
     
  12. Liu M., Lin D., Pei D. Fast algebraic attacks and decomposition of symmetric Boolean functions // IEEE Trans. Inf. Theory. 2011. V. 57. P. 4817–4821. DOI: 10.1109/TIT.2011.2145690.
     
  13. Файзуллин Р. Т., Дулькейт В. И., Огородников Ю. Ю. Гибридный метод поиска приближённого решения задачи 3-выполнимость, ассоциированной с задачей факторизации // Тр. Ин-та математики и механики. 2013. Т. 19, № 2. C. 285–294.
     
  14. Gu J. Global optimization for satisfiability (SAT) problem // IEEE Trans. Knowl. Data Eng. 1994. V. 6, No. 3. P. 361–381. DOI: 10.1109/69.334864.
     
  15. Gu J., Gu Q., Du D. On optimizing the satisfiability (SAT) problem // J. Comput. Sci. Technol. 1999. V. 14, No. 1. P. 1–17. DOI: 10.1007/ BF02952482.
     
  16. 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. V. 15, No. 2. Paper ID 33. 22 p. DOI: 10.3390/a15020033.
     
  17. Barotov D. N., Barotov R. N., Soloviev V., Feklin V., Muzafarov D., Ergashboev T., Egamov Kh. The development of suitable inequalities and their application to systems of logical equations // Mathematics. 2022. V. 10, No. 11. Paper ID 1851. 9 p. DOI: 10.3390/math10111851.
     
  18. Баротов Д. Н., Баротов Р. Н. Полилинейные продолжения некоторых дискретных функций и алгоритм их нахождения // Вычисл. методы и программирование. 2023. Т. 24, вып. 1. С. 10–23. DOI: 10.26089/NumMet. v24r102.
     
  19. Barotov D. N., Osipov A., Korchagin S., Pleshakova E., Muzafarov D., Barotov R. N., Serdechnyi D. Transformation method for solving system of Boolean algebraic equations // Mathematics. 2021. V. 9, No. 24. Paper ID 3299. 12 p. DOI: 10.3390/math9243299.
     
  20. Owen G. Multilinear extensions of games // Manage. Sci. 1972. V. 18, No. 5-2. P. 64–79. DOI: 10.1287/mnsc.18.5.64.
     
  21. Barotov D. N., Barotov R. N. Polylinear transformation method for solving systems of logical equations // Mathematics. 2022. V. 10, No. 6. Paper ID 918. 10 p. DOI: 10.3390/math10060918.
     
  22. Barotov D. N. Target function without local minimum for systems of logical equations with a unique solution // Mathematics. 2022. V. 10, No. 12. Paper ID 2097. 8 p. DOI: 10.3390/math10122097.
     
  23. Баротов Д. Н. Выпуклое продолжение булевой функции и его приложения // Дискрет. анализ и исслед. операций. 2024. Т. 31, № 1. С. 5–18.
     
  24. Jensen J. L. W. V. Sur les fonctions convexes et les inégalités entre les valeurs moyennes // Acta Math. 1906. V. 30. P. 175–193. [French]. DOI: 10.1007/BF02418571.

Исследование выполнено за счёт бюджета Финансового университета при Правительстве Российской Федерации.

Баротов Достонжон Нумонжонович
  1. Финансовый университет при Правительстве Российской Федерации, 
    4-й Вешняковский пр-д, 4, 109456 Москва, Россия

E-mail: dnbarotov@fa.ru

Статья поступила 7 декабря 2023 г.
После доработки — 12 февраля 2024 г.
Принята к публикации 22 марта 2024 г.

Abstract:

We construct convex continuations of discrete functions defined on the vertices of the $n$-dimensional unit cube $[0, 1]^n$, an arbitrary cube $[a, b]^n$, and a parallelepiped $[c_1, d_1] \times [c_2, d_2] \times \cdots \times [c_n, d_n]$. In each of these cases, we constructively prove that, for any discrete function $f$ defined on the vertices of $\mathbb{G} \in$ {$[0, 1]^n, [a, b]^n, [c_1, d_1] \times [c_2, d_2] \times \cdots \times [c_n, d_n]$}, first, there exist infinitely many convex continuations to the set $\mathbb{G}$, and second, there exists a unique function$f_{DM} : \mathbb{G} \to \mathbb{R}$ that is the maximum of convex continuations of $f$ to $G$. We also show that the function $f_{DM}$ is continuous on $\mathbb{G}$.  
Bibliogr. 24.

References:
  1. J. A. Armario, Boolean functions and permanents of Sylvester Hadamard matrices, Mathematics 9 (2), ID 177 (2021), DOI: 10.3390/math9020177.
     
  2. A. H. Abdel-Gawad, A. F. Atiya, and N. M. Darwish, Solution of systems of Boolean equations via the integer domain, Inf. Sci. 180 (2), 288–300 (2010), DOI: 10.1016/j.ins.2009.09.010.
     
  3. F. M. Brown, Boolean Reasoning: The Logic of Boolean Equations (Kluwer Acad. Publ., Boston, 1990).
     
  4. P. L. Hammer and S. Rudeanu, Boolean Methods in Operations Research and Related Areas (Springer, Heidelberg, 1968).
     
  5. G. V. Bard, Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis, PhD Thesis (Univ. Maryland, College Park, MD, 2007).
     
  6. J.-C. Faugère and A. Joux, Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases, in Advances in Cryptology — CRYPTO 2003 (Proc. 23rd Annu. Int. Cryptology Conf., Santa Barbara, USA, Aug. 17–21, 2003) (Springer, Heidelberg, 2003), pp. 44–60 (Lect. Notes Comput. Sci., Vol. 2729), DOI: 10.1007/978-3-540-45146-4_3.
     
  7. F. Armknecht, Improving fast algebraic attacks, in Fast Software Encryption (Rev. Pap. 11th Int. Workshop, Delhi, India, Feb. 5–7, 2004) (Springer, Heidelberg, 2004), pp. 65–82, DOI: 10.1007/978-3-540-25937-4_5.
     
  8. M. Bardet, J.-C. Faugère, B. Salvye, and P. J. Spaenlehauer, On the complexity of solving quadratic boolean systems, J. Complex. 29, 53–75 (2013), DOI: 10.1016/j.jco.2012.07.001.
     
  9. N. T. Courtois, Fast algebraic attacks on stream ciphers with linear feedback, in Advances in Cryptology — CRYPTO 2003 (Proc. 23rd Annu. Int. Cryptology Conf., Santa Barbara, USA, Aug. 17–21, 2003) (Springer, Heidelberg, 2003), pp. 176–194 (Lect. Notes Comput. Sci., Vol. 2729), DOI: 10.1007/978-3-540-45146-4_11.
     
  10. J.-C. Faugère, A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra 139, 61–88 (1999), DOI: 10.1016/S0022-4049(99) 00005-5.
     
  11. J.-C. Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), in Proc. 2002 Int. Symp. Symbolic and Algebraic Computation, Lille, France, July 7–10, 2002 (ACM, New York, 2002), pp. 75–83, DOI: 10.1145/780506.780516.
     
  12. M. Liu, D. Lin, and D. Pei, Fast algebraic attacks and decomposition of symmetric Boolean functions, IEEE Trans. Inf. Theory 57, 4817–4821 (2011), DOI: 10.1109/TIT.2011.2145690.
     
  13. R. T. Faizullin, V. I. Dul’keit, and Yu. Yu. Ogorodnikov, A hybrid method for the approximate solution of the 3-satisfiability problem associated with the factorization problem, Tr. Inst. Mat. Mekh. 19 (2), 285–294 (2013) [Russian].
     
  14. J. Gu, Global optimization for satisfiability (SAT) problem, IEEE Trans. Knowl. Data Eng. 6 (3), 361–381 (1994), DOI: 10.1109/69.334864.
     
  15. J. Gu, Q. Gu, and D. Du, On optimizing the satisfiability (SAT) problem, J. Comput. Sci. Technol. 14 (1), 1–17 (1999), DOI: 10.1007/BF02952482.
     
  16. 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 15 (2), ID 33 (2022), DOI: 10. 3390/a15020033.
     
  17. D. N. Barotov, R. N. Barotov, V. Soloviev, V. Feklin, D. Muzafarov, T. Ergashboev, and Kh. Egamov, The development of suitable inequalities and their application to systems of logical equations, Mathematics 10 (11), ID 1851 (2022), DOI: 10.3390/math10111851.
     
  18. D. N. Barotov and R. N. Barotov, Polylinear continuations of some discrete functions and an algorithm for finding them, Vychisl. Metody Program. 24 (1), 10–23 (2023) [Russian], DOI: 10.26089/NumMet.v24r102.
     
  19. D. N. Barotov, A. Osipov, S. Korchagin, E. Pleshakova, D. Muzafarov, R. N. Barotov, and D. Serdechnyi, Transformation method for solving system of Boolean algebraic equations, Mathematics 9 (24), ID 3299 (2021), DOI: 10.3390/math9243299.
     
  20. G. Owen, Multilinear extensions of games, Manage. Sci. 18 (5-2), 64–79 (1972), DOI: 10.1287/mnsc.18.5.64.
     
  21. D. N. Barotov and R. N. Barotov, Polylinear transformation method for solving systems of logical equations, Mathematics 10 (6), ID 918 (2022), DOI: 10.3390/math10060918.
     
  22. D. N. Barotov, Target function without local minimum for systems of logical equations with a unique solution, Mathematics 10 (12), ID 2097 (2022), DOI: 10.3390/math10122097.
     
  23. D. N. Barotov, Convex continuation of a Boolean function and its applications, Diskretn. Anal. Issled. Oper. 31 (1), 5–18 (2024) [Russian] [J. Appl. Ind. Math. 18 (1), 1–9 (2024)].
     
  24. J. L. W. V. Jensen, Sur les fonctions convexes et les inégalités entre les valeurs moyennes, Acta Math. 30, P. 175–193 (1906) [French], DOI: 10.1007/ BF02418571.