mathnasТруды Института математики НАН БеларусиProceedings of the Institute of Mathematics of the NAS of Belarus1812-5093Институт математики НАН Беларусиmathnas-67Research ArticleАЛГЕБРА И ТЕОРИЯ ЧИСЕЛALGEBRA AND NUMBER THEORYАлгебраическое доказательство эквивалентности двух вариантов cut-нормы для многомерных симметричных матрицAlgebraic proof of the equivalence of two variants of the cut-norm for multidimensional symmetric matricesШведковП. Н.ShvedkovP. N.

Минск

Minsk

shvedkovpavel@gmail.comЛыковК. В.LykovK. V.

Минск

Minsk

alkv@list.ruБелорусский государственный университетBelarusian State UniversityИнститут математики НАН БеларусиInstitute of Mathematics of the National Academy of Sciences of Belarus2025300620253313443Copyright © Шведков П.Н., Лыков К.В., 20252025Шведков П.Н., Лыков К.В.Shvedkov P.N., Lykov K.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://mathnas.ejournal.by/jour/article/view/67

В работе доказана эквивалентность двух специальных матричных норм. Обе нормы возникают в моделях, формулируемых в терминах взаимодействия бинарных переменных. При этом одна норма связана со взаимодействием этих переменных внутри одной группы, а другая – со взаимодействием переменных из разных групп. Утверждение позволяет легко переносить содержательные результаты со второго (более простого) случая на первый.

The paper proves the equivalence of two special matrix norms. Both norms arise in models formulated in terms of interactions between binary variables. One norm is associated with the interaction of these variables within a single group, while the other is related to the interaction of variables from different groups. The statement allows for an easy transfer of meaningful results from the second (simpler) case to the first.

cut-нормаматричная нормаполилинейные формыэквивалентность нормтеория графовкомбинаторная оптимизацияквантовые вычисленияограниченная машина Больцманамногомерный массивтензорcut-normmatrix normmultilinear formsequivalence of normsgraph theorycombinatorial optimizationquantum computingrestricted Boltzmann machinemultidimensional arraytensorРабота К. В. Лыкова поддержана Институтом математики НАН Беларуси в рамках государственной программы «Конвергенция–2025» (задание 1.3.05).ReferencesMcGeoch C. C. Adiabatic Quantum Computation and Quantum Annealing. Springer Nature Switzerland AG, 2014.McGeoch C. C. Adiabatic Quantum Computation and Quantum Annealing. Springer Nature Switzerland AG, 2014.What is Quantum Annealing? [Electronic resourse]. – Mode of access: https://docs.dwavesys.com/docs/latest/c_gs_2.html.What is Quantum Annealing? [Electronic resourse]. – Mode of access: https://docs.dwavesys.com/docs/latest/c_gs_2.html.Lucas A. Ising formulations of many NP problems // Front. in Phys. 2014. Vol. 2. Art. 5. DOI: 10.3389/fphy.2014.00005Lucas A. Ising formulations of many NP problems. Front. in Phys., 2014, vol. 2, art. 5. doi.org/10.3389/fphy.2014.00005Talagrand M. Mean field models for spin glasses. Berlin, Heidelberg: Springer, 2011.Talagrand M. Mean field models for spin glasses. Berlin, Heidelberg, Springer, 2011.Talagrand M. Spin Glasses: A Challenge for Mathematicians. Cavity and Mean Field Models. Berlin, Heidelberg: Springer, 2003.Talagrand M. Spin Glasses: A Challenge for Mathematicians. Cavity and Mean Field Models. Berlin, Heidelberg, Springer, 2003.Hebb D. O. The Organization of Behavior. New York: Wiley & Sons, 1949.Hebb D. O. The Organization of Behavior. New York, Wiley & Sons, 1949.Hopfield J. J. Neural networks and physical systems with emergent collective computational abilities // Proc. Natl. Acad. Sci. USA. 1982. Vol. 79, iss. 8. P. 2554–2558. DOI: 10.1073/pnas.79.8.2554Hopfield J. J. Neural networks and physical systems with emergent collective computational abilities. Proc. Natl. Acad. Sci. USA, 1982, vol. 79, iss. 8, pp. 2554–2558. DOI: 10.1073/pnas.79.8.2554Salakhutdinov R., Hinton G. Deep Boltzmann Machine // Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics. PMLR. 2009. Vol. 5. P. 448–455.Salakhutdinov R., Hinton G. Deep Boltzmann Machine. Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, PMLR, 2009, vol. 5, pp. 448–455.Асташкин С. В., Лыков К. В. О безусловности дробного хаоса Радемахера в симметричных пространствах // Изв. РАН. Сер. матем. 2024. Т. 88, № 1. C. 3–20. doi.org/10.4213/im9406Astashkin S., Lykov K. On the unconditionality of Rademacher’s fractional chaos in symmetric spaces. Izvestiya: Mathematics, 2024, vol. 88, no. 1, pp. 3–20 (in Russian). doi.org/10.4213/im9406Frieze A., Kannan R. Quick Approximation to Matrices and Applications // Combinatorica. 1999. Vol. 19. P. 175–220. DOI: https://doi.org/10.1007/s004930050052Frieze A., Kannan R. Quick Approximation to Matrices and Applications. Combinatorica, vol. 19, pp. 175–220. DOI: https://doi.org/10.1007/s004930050052Håstad J. Some Optimal Inapproximability Results // J. Assoc. Comput. Machinery. 2001. P. 798–859. DOI: 10.1145/502090.502098Håstad J. Some Optimal Inapproximability Results // J. Assoc. Comput. Machinery. 2001. P. 798–859. DOI: 10.1145/502090.502098Alon N., Naor. A Approximating the cut-norm via grothendieck’s inequality // STOC’04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. June 13–16, 2004. New York, USA, 2004. P. 72–80. doi.org/10.1145/1007352.1007371Alon N., Naor. A Approximating the cut-norm via grothendieck’s inequality // STOC’04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. June 13–16, 2004. New York, USA, 2004. P. 72–80. doi.org/10.1145/1007352.1007371Astashkin S., Lykov K. Random unconditional convergence of Rademacher chaos in L∞ and sharp estimates for discrepancy of weighted graphs and hypergraphs, Ver. 1 released 28.12.2024 [Electronic resourse]. – Mode of access: https://arxiv.org/abs/2412.20107.Astashkin S., Lykov K. Random unconditional convergence of Rademacher chaos in L∞ and sharp estimates for discrepancy of weighted graphs and hypergraphs, Ver. 1 released 28.12.2024 [Electronic resourse]. – Mode of access: https://arxiv.org/abs/2412.20107.De la Peña V. H. and Giné E. Decoupling: from dependence to independence. New York, Berlin, Heidelberg: Springer-Verlag, 1999.De la Peña V. H. and Giné E. Decoupling: from dependence to independence. New York, Berlin, Heidelberg: Springer-Verlag, 1999.

The authors declare that there are no conflicts of interest present.