{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:28:55Z","timestamp":1760236135459,"version":"build-2065373602"},"reference-count":69,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Center of Excellence &quot;Center of Photonics&quot; of The Ministry of Science and Higher Education of the Russian Federation","award":["075-15-2020-906"],"award-info":[{"award-number":["075-15-2020-906"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>We present a finite-order system of recurrence relations for the permanent of circulant matrices containing a band of k any-value diagonals on top of a uniform matrix (for k=1,2 and 3) and the method for deriving such recurrence relations, which is based on the permanents of the matrices with defects. The proposed system of linear recurrence equations with variable coefficients provides a powerful tool for the analysis of the circulant permanents, their fast, linear-time computing; and finding their asymptotics in a large-matrix-size limit. The latter problem is an open fundamental problem. Its solution would be tremendously important for a unified analysis of a wide range of the nature\u2019s \u266fP-hard problems, including problems in the physics of many-body systems, critical phenomena, quantum computing, quantum field theory, theory of chaos, fractals, theory of graphs, number theory, combinatorics, cryptography, etc.<\/jats:p>","DOI":"10.3390\/e23111423","type":"journal-article","created":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T23:50:28Z","timestamp":1635465028000},"page":"1423","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Exact Recursive Calculation of Circulant Permanents: A Band of Different Diagonals inside a Uniform Matrix"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6802-3258","authenticated-orcid":false,"given":"Vitaly","family":"Kocharovsky","sequence":"first","affiliation":[{"name":"Department of Physics and Astronomy, Texas A&M University, College Station, TX 77843, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0487-4931","authenticated-orcid":false,"given":"Vladimir","family":"Kocharovsky","sequence":"additional","affiliation":[{"name":"Institute of Applied Physics, Russian Academy of Sciences, 603950 Nizhny Novgorod, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4092-9693","authenticated-orcid":false,"given":"Vladimir","family":"Martyanov","sequence":"additional","affiliation":[{"name":"Intel Corporation, 5000 W Chandler Blvd, Chandler, AZ 85226, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4219-4291","authenticated-orcid":false,"given":"Sergey","family":"Tarasov","sequence":"additional","affiliation":[{"name":"Institute of Applied Physics, Russian Academy of Sciences, 603950 Nizhny Novgorod, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,10,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"322","DOI":"10.3390\/e22030322","article-title":"Unification of the Nature\u2019s Complexities via a Matrix Permanent\u2014Critical Phenomena, Fractals, Quantum Computing, #P-Complexity","volume":"22","author":"Kocharovsky","year":"2020","journal-title":"Entropy"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Caianiello, E.R. (1973). Combinatorics and renormalization in quantum field theory. Frontiers in Physics, W. A. Benjamin Inc.","DOI":"10.1007\/978-1-4615-8909-9"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/S0370-2693(97)00263-3","article-title":"A simple formula for Bose\u2013Einstein corrections","volume":"399","author":"Wosiek","year":"1997","journal-title":"Phys. Lett. B"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Scheel, S. (2004). Permanents in linear optical networks. arXiv.","DOI":"10.1002\/3527606009.ch28"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"3393","DOI":"10.1098\/rspa.2011.0232","article-title":"A linear-optical proof that the permanent is \u266fP-hard","volume":"467","author":"Aaronson","year":"2011","journal-title":"Proc. R. Soc. A"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Kalai, G. (2016). The quantum computer puzzle (expanded version). arXiv.","DOI":"10.1090\/noti1380"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"123601","DOI":"10.1103\/PhysRevLett.116.123601","article-title":"Universality of Generalized Bunching and Efficient Assessment of Boson Sampling","volume":"116","author":"Shchesnovich","year":"2016","journal-title":"Phys. Rev. Lett."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"042304","DOI":"10.1103\/PhysRevA.97.042304","article-title":"Simulating and assessing boson sampling experiments with phase-space representations","volume":"97","author":"Opanchuk","year":"2018","journal-title":"Phys. Rev. A"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Kadanoff, L.P. (2000). Statistical Physics: Statics, Dynamics and Renormalization, World Scientific.","DOI":"10.1142\/4016"},{"key":"ref_10","unstructured":"Kocharovsky, V.V., and Kocharovsky, V.V. (2016). Exact general solution to the three-dimensional Ising model and a self-consistency equation for the nearest-neighbors\u2019 correlations. arXiv."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"108002","DOI":"10.1088\/0031-8949\/90\/10\/108002","article-title":"Microscopic theory of phase transitions in a critical region","volume":"90","author":"Kocharovsky","year":"2015","journal-title":"Phys. Scr."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"2520","DOI":"10.1016\/j.physleta.2015.07.026","article-title":"Towards an exact solution for the three-dimensional Ising model: A method of the recurrence equations for partial contractions","volume":"379","author":"Kocharovsky","year":"2015","journal-title":"Phys. Lett. A"},{"key":"ref_13","unstructured":"Minc, H. (1978). Permanents, Encyclopedia of Mathematics and Its Applications, V. 6, Addison-Wesley."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1080\/03081088708817786","article-title":"Theory of Permanents 1982\u20131985","volume":"21","author":"Minc","year":"1987","journal-title":"Linear Multilinear Algebra"},{"key":"ref_15","first-page":"55","article-title":"Recent developments and open problems in the theory of permanents","volume":"76","author":"Bapat","year":"2007","journal-title":"Math. Stud."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Brualdi, R.A., and Cvetkovic, D. (2008). A Combinatorial Approach to Matrix Theory and Its Applications, CRC Press.","DOI":"10.1201\/9781420082241"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Stanley, R.P. (2012). Enumerative Combinatorics, V. 1, Cambridge University Press.","DOI":"10.1017\/CBO9781139058520"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Barvinok, A. (2016). Combinatorics and Complexity of Partition Functions, Algorithms and Combinatorics 30, Springer International Publishing AG.","DOI":"10.1007\/978-3-319-51829-9"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Ryser, H.J. (1963). Combinatorial Mathematics, The Carus Mathematical Monographs, No. 14, The Mathematical Association of America.","DOI":"10.5948\/UPO9781614440147"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","article-title":"The complexity of computing the permanent","volume":"8","author":"Valiant","year":"1979","journal-title":"Theor. Comput. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1145\/1008731.1008738","article-title":"A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries","volume":"51","author":"Jerrum","year":"2004","journal-title":"J. ACM"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"13161","DOI":"10.1073\/pnas.1505664112","article-title":"A complexity classification of spin systems with an external field","volume":"112","author":"Goldberg","year":"2015","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Daubechies, I. (1992). Ten Lectures on Wavelets, SIAM.","DOI":"10.1137\/1.9781611970104"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1016\/j.jmaa.2010.04.041","article-title":"Wavelet expansions and asymptotic behavior of distributions","volume":"370","author":"Saneva","year":"2010","journal-title":"J. Math. Anal. Appl."},{"key":"ref_25","unstructured":"Silvestrov, S., and Ran\u010di\u0107, M. (2016). Fractional-Wavelet Analysis of Positive definite Distributions and Wavelets on D\u2019(C). Engineering Mathematics II, Springer."},{"key":"ref_26","unstructured":"Diaconis, P., Graham, R., and Holmes, S.P. (2021, October 26). Statistical Problems Involving Permutations with Restricted Positions. Available online: http:\/\/www.math.ucsd.edu\/~fan\/ron\/papers\/01_07_permutations.pdf."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1017\/S1446788700019339","article-title":"On the permanent of Schur\u2019s matrix","volume":"21","author":"Graham","year":"1976","journal-title":"J. Aust. Math. Soc. A"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"B\u00fcrgisser, P., Clausen, M., and Shokrollahi, M.A. (1997). Algebraic Complexity Theory. With the Collaboration of Thomas Lickteig. Grundlehren der MathematischenWissenschaften [Fundamental Principles of Mathematical Sciences] Book Series, GL Volume 315, Springer.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1007\/s00454-001-0083-2","article-title":"A Deterministic Algorithm for Approximating the Mixed Discriminant and Mixed Volume, and a Combinatorial Corollary","volume":"27","author":"Gurvits","year":"2002","journal-title":"Discret. Comput. Geom."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Anari, N., Gurvits, L., Gharan, S.O., and Saberi, A. (2017, January 15\u201317). Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices. Proceedings of the IEEE 58th Annual Symposium, Foundations of Computer Science (FOCS), Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2017.89"},{"key":"ref_31","first-page":"61570","article-title":"On permanental polynomials of certain random matrices","volume":"2006","author":"Fyodorov","year":"2006","journal-title":"Int. Math. Res. Not."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1364","DOI":"10.1016\/j.laa.2008.10.029","article-title":"Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices","volume":"430","author":"Schwartz","year":"2009","journal-title":"Linear Algebra Appl."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"3553","DOI":"10.1016\/j.laa.2011.12.030","article-title":"A note on permanents and generalized complementary basic matrices","volume":"436","author":"Fiedler","year":"2012","journal-title":"Linear Algebra Appl."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/j.laa.2015.10.034","article-title":"The permanent-on-top conjecture is false","volume":"490","author":"Shchesnovich","year":"2016","journal-title":"Linear Algebra Appl."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.laa.2015.12.004","article-title":"An efficient tree decomposition method for permanents and mixed discriminants","volume":"493","author":"Cifuentes","year":"2016","journal-title":"Linear Algebra Appl."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1887","DOI":"10.1016\/j.ejc.2010.01.010","article-title":"The permanent of a square matrix","volume":"31","author":"Glynn","year":"2010","journal-title":"Eur. J. Comb."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"2911","DOI":"10.1016\/j.jpaa.2017.02.008","article-title":"On the complexity of the permanent in various computational models","volume":"221","author":"Ikenmeyera","year":"2017","journal-title":"J. Pure Appl. Algebra"},{"key":"ref_38","unstructured":"Wu, J., Liu, Y., Zhang, B., Jin, X., Wang, Y., Wang, H., and Yang, X. (2016). Computing Permanents for Boson Sampling on Tianhe-2 Supercomputer. arXiv."},{"key":"ref_39","first-page":"539544","article-title":"A Fibonacci matrix and the permanent function","volume":"7","author":"King","year":"1969","journal-title":"Fibonacci Q."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0024-3795(87)90285-0","article-title":"Permanental compounds and permanents of (0,1) circulants","volume":"86","author":"Minc","year":"1987","journal-title":"Linear Algebra Appl."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/S0024-3795(99)00012-9","article-title":"How fast can one compute the permanent of circulant matrices?","volume":"292","author":"Bernasconi","year":"1999","journal-title":"Linear Algebra Appl."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1023\/B:JACO.0000047292.01630.a6","article-title":"The number of terms in the permanent and the determinant of a generic circulant matrix","volume":"20","author":"Thomas","year":"2004","journal-title":"J. Algebr. Comb."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1016\/j.laa.2017.01.024","article-title":"On the permanents of circulant and degenerate Schur matrices","volume":"519","author":"Kocharovsky","year":"2017","journal-title":"Linear Algebra Appl."},{"key":"ref_44","first-page":"106404","article-title":"Circulant matrices and Galois-Togliatti systems","volume":"224","author":"Mezzetti","year":"2019","journal-title":"J. Pure Appl. Algebra"},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Crapo, H., and Senato, D. (2001). On the permanent of certain circulant matrices. Algebraic Combinatorics and Computer Science, Springer.","DOI":"10.1007\/978-88-470-2107-5"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"1258","DOI":"10.1016\/j.laa.2009.10.036","article-title":"The \u03bc-permanent of a tridiagonal matrix, orthogonal polynomials, and chain sequences","volume":"432","year":"2010","journal-title":"Linear Algebra Appl."},{"key":"ref_47","unstructured":"Temme, K., and Wocjan, P. (2012). Efficient Computation of the Permanent of Block Factorizable Matrices. arXiv."},{"key":"ref_48","first-page":"83","article-title":"Sums of permanental minors using Grassmann algebra","volume":"1","author":"Butera","year":"2015","journal-title":"Int. J. Graph Theory Appl."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/j.ipl.2005.06.007","article-title":"Computing sparse permanents faster","volume":"96","author":"Servedio","year":"2005","journal-title":"Inf. Process. Lett."},{"key":"ref_50","unstructured":"Goldenfeld, N. (1992). Lectures on Phase Transitions and Renormalization Group, Addison-Wesley."},{"key":"ref_51","unstructured":"Riordan, J. (1958). Introduction to Combinatorial Analysis, John Wiley."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1017\/S1446788700012337","article-title":"Four-discordant permutations","volume":"28","author":"Whitehead","year":"1979","journal-title":"J. Aust. Math. Soc. (Ser. A)"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0012-365X(87)90002-1","article-title":"M\u00e9nage numbers, bijections and P-recursiveness","volume":"63","author":"Canfield","year":"1987","journal-title":"Discret. Math."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1080\/0020739980290502","article-title":"Lucas numbers and the m\u00e9nage problem","volume":"29","author":"Bong","year":"1998","journal-title":"Int. J. Math. Educ. Sci. Technol."},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"Flajolet, P., and Sedgewick, R. (2009). Analytic Combinatorics, Cambridge University Press.","DOI":"10.1017\/CBO9780511801655"},{"key":"ref_56","unstructured":"(2021, October 26). The Online Encyclopedia of Integer Sequences. Available online: https:\/\/oeis.org\/."},{"key":"ref_57","unstructured":"Zeilberger, D. (2014). Automatic Enumeration of Generalized M\u00e9nage Numbers. arXiv."},{"key":"ref_58","doi-asserted-by":"crossref","unstructured":"Alekseyev, A.A. (2016). Weighted de Bruijn Graphs for the M\u00e9nage Problem and Its Generalizations. arXiv.","DOI":"10.1007\/978-3-319-44543-4_12"},{"key":"ref_59","first-page":"187","article-title":"Additional note on a problem of arrangement","volume":"11","author":"Muir","year":"1882","journal-title":"Proc. R. Soc. Edinb."},{"key":"ref_60","first-page":"113","article-title":"The probleme des menages","volume":"12","author":"Kaplansky","year":"1946","journal-title":"Scr. Math."},{"key":"ref_61","first-page":"109","article-title":"Permutations discordant with two given permutations","volume":"19","author":"Touchard","year":"1953","journal-title":"Scr. Math."},{"key":"ref_62","first-page":"14","article-title":"Discodant permutations","volume":"20","author":"Riordan","year":"1954","journal-title":"Scr. Math."},{"key":"ref_63","first-page":"1","article-title":"Structure polynomial of Latin rectangles and its application to a combinatorial problem","volume":"10","author":"Yamamoto","year":"1956","journal-title":"Mem. Fac. Sci. Kyushu Univ. Ser. A Math."},{"key":"ref_64","doi-asserted-by":"crossref","unstructured":"Dagum, P., Luby, M., Mihail, M., and Vazirani, U. (1988, January 24\u201326). Polytopes, permanents, and graphs with large factors. Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, White Plains, NY, USA.","DOI":"10.1109\/SFCS.1988.21957"},{"key":"ref_65","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1016\/0022-247X(85)90209-4","article-title":"Resurrecting the Asymptotics of Linear Recurrences","volume":"111","author":"Wimp","year":"1985","journal-title":"J. Math. Anal. Appl."},{"key":"ref_66","unstructured":"Zeilberger, D. (2021, October 26). AsyRec, a Maple Package That Computes the Asymptotics for Solutions of Linear Recurrence Equations with Polynomial Coefficients. Available online: http:\/\/www.math.rutgers.edu\/~zeilberg\/tokhniot\/AsyRec."},{"key":"ref_67","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/j.aam.2005.09.003","article-title":"Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory","volume":"37","author":"Apagodu","year":"2006","journal-title":"Adv. Appl. Math."},{"key":"ref_68","unstructured":"Apagodu, M., and Zeilberger, D. (2021, October 26). Multi-Variable Zeilberger and Almkvist-Zeilberger Algorithms and the Sharpening of Wilf-Zeilberger Theory, Software Package. Available online: http:\/\/www.math.rutgers.edu\/~zeilberg\/mamarim\/mamarimhtml\/multiZ.html."},{"key":"ref_69","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1038\/nature23458","article-title":"Quantum computational supremacy","volume":"549","author":"Harrow","year":"2017","journal-title":"Nature"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/11\/1423\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:22:08Z","timestamp":1760167328000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/11\/1423"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,28]]},"references-count":69,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2021,11]]}},"alternative-id":["e23111423"],"URL":"https:\/\/doi.org\/10.3390\/e23111423","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2021,10,28]]}}}