Convex continuations of some discrete functions

D. N. Barotov

Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 3, pp. 5-23

Résumé

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\dots\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\dots\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}\colon\mathbb{G}\to\mathbb{R}$ that is the maximum of convex continuations of $f$ to $\mathbb{G}$. We also show that the function $f_{DM}$ is continuous on $\mathbb{G}$. Bibliogr. 24.

Détail

Keywords: discrete function, convex continuation of a discrete function, Boolean function, pseudo-Boolean function.

Bibliographie

[1] J. A. Armario, “Boolean functions and permanents of Sylvester Hadamard matrices”, Mathematics, 9:2 (2021), 177, 8 pp. | DOI

[2] A. H. Abdel-Gawad, A. F. Atiya, N. M. Darwish, “Solution of systems of Boolean equations via the integer domain”, Inf. Sci, 180:2 (2010), 288–300 | DOI

[3] F. M. Brown, Boolean reasoning: The logic of Boolean equations, Kluwer Acad. Publ., Boston, 1990, 304 pp.

[4] P. L. Hammer, S. Rudeanu, Boolean methods in operations research and related areas, Springer, Heidelberg, 1968, 330 pp.

[5] G. V. Bard, Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis, PhD Thes, Univ. Maryland, College Park, MD, 2007, 178 pp.

[6] J. C. Faugere, A. Joux, “Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Grobner bases”, Advances in cryptology-CRYPTO 2003, Proc. 23rd Annu. Int. Cryptology Conf. (Santa Barbara, USA, Aug. 17-21, 2003), Lect. Notes Comput. Sci., 2729, Springer, Heidelberg, 2003, 44–60 | DOI

[7] F. Armknecht, “Improving fast algebraic attacks”, Fast software encryption, Rev. Pap. 11th Int. Workshop (Delhi, India, Feb. 5-7, 2004), Springer, Heidelberg, 2004, 65–82 | DOI

[8] M. Bardet, J. C. Faugere, B. Salvye, P. J. Spaenlehauer, “On the complexity of solving quadratic boolean systems”, J. Complex., 29 (2013), 53–75 | DOI

[9] N. T. Courtois, “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), Lect. Notes Comput. Sci., 2729, Springer, Heidelberg, 2003, 176–194 | DOI

[10] J. C. Faugere, “A new efficient algorithm for computing Gröbner bases (F4)”, J. Pure Appl. Algebra, 139 (1999), 61–88 | DOI

[11] J. C. Faugere, “A new efficient algorithm for computing Grobner bases with out reduction to zero (F5)”, Proc. 2002 Int Symp. Symbolic and Algebraic Computation (Lille, France, July 7-10, 2002), ACM, New York, 2002, 75–83 | DOI

[12] M. Liu, D. Lin, D. Pei, “Fast algebraic attacks and decomposition of symmetric Boolean functions”, IEEE Trans. Inf. Theory, 57 (2011), 4817–4821 | DOI

[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 (2013), 285–294 (Russian)

[14] Gu J., “Global optimization for satisfiability (SAT) problem”, IEEE Trans. Knowl. Data Eng., 6:3 (1994), 361–381 | DOI

[15] J. Gu, Q. Gu, D. Du, “On optimizing the satisfiability (SAT) problem”, J. Comput. Sci. Technol., 14:1 (1999), 1–17 | DOI

[16] A. I. Pakhomchik, V. V. Voloshinov, V. M. Vinokur, G. B. Lesovik, “Converting of Boolean expression to linear equations, inequalities and QUBO penalties for cryptanalysis”, Algorithms, 15:2 (2022), 33, 22 pp. | DOI

[17] D. N. Barotov, R. N. Barotov, V. Soloviev, V. Feklin, D. Muzafarov, T. Ergashboev, Kh. Egamov, “The development of suitable inequalities and their application to systems of logical equations”, Mathematics, 10:11 (2022), 1851, 9 pp. | DOI

[18] D. N. Barotov and R. N. Barotov, “Polylinear continuations of some dis crete functions and an algorithm for finding them”, Vychisl. Metody Program., 24:1 (2023), 10–23 (Russian) | DOI

[19] Barotov D. N., Osipov A., Korchagin S., Pleshakova E., Muzafarov D., Barotov R. N., Serdechnyi D., “Transformationmethod for solving system of Boolean algebraic equations”, Mathematics, 9:24 (2021), 3299, 12 pp. | DOI

[20] Owen G., “Multilinear extensions of games”, Manage. Sci., 18:5-2 (1972), 64–79 | DOI

[21] D. N. Barotov, R. N. Barotov, “Polylinear transformation method for solving systems of logical equations”, Mathematics, 10:6 (2022), 918, 10 pp. | DOI

[22] D. N. Barotov, “Target function without local minimum for systems of logical equations with a unique solution”, Mathematics, 10:12 (2022), 2097, 8 pp. | DOI

[23] D. N. Barotov, “Convex continuation of a Boolean function and its applications”, J. Appl. Ind. Math., 18:1 (2024), 1–9 | DOI

[24] J. L. W. V. Jensen, “Sur les fonctions convexes et les inégalités entre les valeurs moyennes”, Acta Math., 30 (1906), 175–193 (French) | DOI