{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,29]],"date-time":"2026-10-29T18:32:39Z","timestamp":1793298759658,"version":"4.5.0"},"reference-count":52,"publisher":"National Academy of Sciences","issue":"44","license":[{"start":{"date-parts":[[2026,10,29]],"date-time":"2026-10-29T00:00:00Z","timestamp":1793232000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006683","name":"Xi'an Jiaotong-Liverpool University","doi-asserted-by":"publisher","award":["RDF-23-01-045"],"award-info":[{"award-number":["RDF-23-01-045"]}],"id":[{"id":"10.13039\/501100006683","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100016022","name":"Data Center of Management Science, National Natural Science Foundation of China - Peking University","doi-asserted-by":"publisher","award":["12350710787"],"award-info":[{"award-number":["12350710787"]}],"id":[{"id":"10.13039\/501100016022","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100014857","name":"\u5e7f\u4e1c\u7701\u4eba\u6c11\u653f\u5e9c | National Natural Science Foundation of China-Guangdong Joint Fund","doi-asserted-by":"publisher","award":["2023JC10X085"],"award-info":[{"award-number":["2023JC10X085"]}],"id":[{"id":"10.13039\/501100014857","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2026,11,3]]},"abstract":"<jats:p>We address the inverse problem for complexity functions of infinite words, which asks which functions can occur as complexity functions of infinite words. We survey our recent advances on this problem and several of its ramifications. We describe an asymptotic solution to the inverse problem, realizing every function satisfying two necessary conditions as the complexity function of an infinite word up to asymptotic equivalence. We then turn to phenomena beyond asymptotic equivalence, presenting constructions of infinite words with seemingly contradictory behavior of the discrete derivatives of their complexity functions. These lead to a solution of a 1995 problem of Cassaigne and to applications in symbolic dynamics, including the question of convergence of Rauzy graphs, as well as to the growth and asymptotic invariants of algebraic structures.<\/jats:p>","DOI":"10.1073\/pnas.2627766123","type":"journal-article","created":{"date-parts":[[2026,10,29]],"date-time":"2026-10-29T17:37:18Z","timestamp":1793295438000},"update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":0,"title":["Complexity functions of infinite sequences"],"prefix":"10.1073","volume":"123","author":[{"given":"Be\u2019eri","family":"Greenfeld","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00453a208","id-type":"ROR","asserted-by":"publisher"}],"name":"Department of Mathematics and Statistics, Hunter College, City University of New York","place":["New York"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul-Henry","family":"Leemann","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03zmrmn05","id-type":"ROR","asserted-by":"publisher"}],"name":"Department of Pure Mathematics, Xi\u2019an Jiaotong\u2013Liverpool University","place":["Suzhou, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carlos Gustavo","family":"Moreira","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/049tv2d57","id-type":"ROR","asserted-by":"publisher"}],"name":"Southern University of Science and Technology International Center for Mathematics","place":["Shenzhen, China"]},{"id":[{"id":"https:\/\/ror.org\/028caqe42","id-type":"ROR","asserted-by":"publisher"}],"name":"Instituto Nacional de Matem\u00e1tica Pura e Aplicada","place":["Rio de Janeiro, Brazil"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Efim","family":"Zelmanov","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/049tv2d57","id-type":"ROR","asserted-by":"publisher"}],"name":"Southern University of Science and Technology International Center for Mathematics","place":["Shenzhen, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"341","published-online":{"date-parts":[[2026,10,29]]},"reference":[{"key":"e_1_3_4_1_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626302"},{"key":"e_1_3_4_2_2","unstructured":"Lothaire Combinatorics on Words Cambridge Mathematical Library (Cambridge University Press Cambridge 1997) pp. xviii+238."},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107326019"},{"key":"e_1_3_4_4_2","unstructured":"Lothaire Applied Combinatorics on Words Encyclopedia of Mathematics and its Applications (Cambridge University Press Cambridge 2005) vol. 105 pp. xvi+610."},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546563"},{"key":"e_1_3_4_6_2","unstructured":"N. Pytheas Fogg V. Berth\u00e9 S. Ferenczi C. Mauduit A. Siegel Eds. Substitutions in Dynamics Arithmetics and Combinatorics Lecture Notes in Mathematics (Springer Berlin 2002) vol. 1794."},{"key":"e_1_3_4_7_2","doi-asserted-by":"crossref","unstructured":"M. P. B\u00e9al J. Berstel S. r. Eilers D. Perrin \u201cSymbolic dynamics\u201d in Handbook of Automata Theory. Vol. II. Automata in Mathematics and Selected Applications J.-\u00c9. Pin Ed. (EMS Press Berlin 2021) pp. 987\u20131030.","DOI":"10.4171\/Automata-1\/27"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.2307\/2371264"},{"key":"e_1_3_4_9_2","first-page":"133","article-title":"Sur la complexit\u00e9 des suites infinies","volume":"1","author":"Allouche J. P.","year":"1994","unstructured":"J. P. Allouche, Sur la complexit\u00e9 des suites infinies. Bull. Belg. Math. Soc. 1, 133\u2013143 (1994).","journal-title":"Bull. Belg. Math. Soc."},{"key":"e_1_3_4_10_2","first-page":"67","article-title":"Complexit\u00e9 et facteurs sp\u00e9ciaux","volume":"4","author":"Cassaigne J.","year":"1997","unstructured":"J. Cassaigne, Complexit\u00e9 et facteurs sp\u00e9ciaux. Bull. Belg. Math. Soc. 4, 67\u201388 (1997).","journal-title":"Bull. Belg. Math. Soc."},{"key":"e_1_3_4_11_2","doi-asserted-by":"crossref","unstructured":"J. Cassaigne \u201cConstructing infinite words of intermediate complexity\u201d in Developments in Language Theory M. Ito M. Toyama Eds. (Springer Berlin Heidelberg 2003) vol. 2450 pp. 173\u2013184.","DOI":"10.1007\/3-540-45005-X_15"},{"key":"e_1_3_4_12_2","unstructured":"J. Cassaigne \u201cSpecial factors of sequences with linear subword complexity\u201d in Developments in Language Theory II (Magdeburg 1995) J. Dassow G. Rozenberg A. Salomaa Eds. (World Scientific Publishing 1996) pp. 25\u201334."},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0143385700009032"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00400-2"},{"key":"e_1_3_4_15_2","doi-asserted-by":"crossref","unstructured":"B. Greenfeld C. G. Moreira E. Zelmanov On the complexity of subshifts and infinite words. J. Eur. Math. Soc. 10.4171\/JEMS\/1753 (2026).","DOI":"10.4171\/jems\/1753"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.4064\/aa142-4-3"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0143385711000137"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/hat005"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00029-023-00862-x"},{"key":"e_1_3_4_20_2","first-page":"29","article-title":"Cubefree words with many squares","volume":"12","author":"Currie J.","year":"2010","unstructured":"J. Currie, N. Rampersad, Cubefree words with many squares. Discret. Math. Theor. Comput. Sci. 12, 29\u201334 (2010).","journal-title":"Discret. Math. Theor. Comput. Sci."},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1090\/proc\/14440"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2011.03.005"},{"key":"e_1_3_4_23_2","unstructured":"P. H. Leemann T. Nagnibeda A. Skripchenko G. Veprev Limits of Rauzy graphs of languages with subexponential complexity. arXiv [Preprint] (2024). https:\/\/doi.org\/10.48550\/arXiv.2402.15877 (Accessed 24 February 2024)."},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/49\/20\/205004"},{"key":"e_1_3_4_25_2","unstructured":"P. H. Leemann \u201cOn subgroups and schreier graphs of finitely generated groups \u201d PhD thesis Universit\u00e9 de Gen\u00e8ve (2016)."},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02698687"},{"key":"e_1_3_4_27_2","doi-asserted-by":"crossref","unstructured":"R. I. Grigorchuk Degrees of growth of finitely generated groups and the theory of invariant means. Izv. Akad. Nauk SSSR Ser. Mat. 48 939\u2013985 (1984) English translation: Math. USSR-Izv. 25 (1985) no. 2 259\u2013300.","DOI":"10.1070\/IM1985v025n02ABEH001281"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2013.177.3.7"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.5802\/aif.2902"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0096-1"},{"key":"e_1_3_4_31_2","unstructured":"R. I. Grigorchuk \u201cOn growth in group theory\u201d in Proceedings of the International Congress of Mathematicians Vol. I II M. Atkinson N. Gilbert J. Howie S. Linton E. Robertson Eds. (Math. Soc. Japan Tokyo 1991) pp. 325\u2013338."},{"key":"e_1_3_4_32_2","first-page":"207","article-title":"On the hilbert-poincar\u00e9 series of graded algebras that are associated with groups","volume":"180","author":"Grigorchuk R. I.","year":"1989","unstructured":"R. I. Grigorchuk, On the hilbert-poincar\u00e9 series of graded algebras that are associated with groups. Mat. Sb. 180, 207\u2013225 (1989).","journal-title":"Mat. Sb."},{"key":"e_1_3_4_33_2","doi-asserted-by":"crossref","unstructured":"L. Bartholdi R. I. Grigorchuk \u201cLie methods in growth of groups and groups of finite width\u201d in Computational and Geometric Aspects of Modern Algebra (London Math. Soc. Lecture Note Ser. Cambridge Univ. Press Cambridge 2000) vol. 275 pp. 1\u201327.","DOI":"10.1017\/CBO9780511600609.002"},{"key":"e_1_3_4_34_2","doi-asserted-by":"crossref","unstructured":"G. R. Krause T. H. Lenagan Growth of Algebras and Gelfand-Kirillov Dimension Graduate Studies in Mathematics (American Mathematical Society Providence RI Revised edition 2000) vol. 22.","DOI":"10.1090\/gsm\/022\/03"},{"key":"e_1_3_4_35_2","unstructured":"J. P. Bell \u201cGrowth functions\u201d in Commutative Algebra and Noncommutative Algebraic Geometry Vol. I: Expository Articles Mathematical Sciences Research Institute Publications D. Eisenbud S. B. Iyengar A. K. Singh J. T. Stafford M. Van den Bergh Eds. (Cambridge University Press Cambridge 2015) vol. 67 pp. 1\u201324."},{"key":"e_1_3_4_36_2","doi-asserted-by":"crossref","unstructured":"G. Bellamy D. Rogalski T. Schedler J. Toby Stafford M. Wemyss Noncommutative Algebraic Geometry (Cambridge University Press Cambridge 2016).","DOI":"10.1017\/9781316416570"},{"key":"e_1_3_4_37_2","first-page":"137","article-title":"Algebras of intermediate growth","volume":"9","author":"Kirillov A. A.","year":"1990","unstructured":"A. A. Kirillov, M. L. Kontsevich, A. I. Molev, Algebras of intermediate growth. Sel. Math. Sov. 9, 137\u2013153 (1990).","journal-title":"Sel. Math. Sov."},{"key":"e_1_3_4_38_2","first-page":"503","article-title":"On fields connected with the enveloping algebras of lie algebras","volume":"167","author":"Gel\u2019fand I.","year":"1966","unstructured":"I. Gel\u2019fand, A. A. Kirillov, On fields connected with the enveloping algebras of lie algebras. Dokl. Akad. Nauk SSSR 167, 503\u2013505 (1966).","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01076413"},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-020-01017-x"},{"key":"e_1_3_4_41_2","volume-title":"A Note on Growth Functions of Algebras and Semigroups","author":"Bergman G. M.","year":"1978","unstructured":"G. M. Bergman, A Note on Growth Functions of Algebras and Semigroups (Berkeley, unpublished notes, University of California, 1978)."},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2003.09.021"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2008.03.028"},{"key":"e_1_3_4_44_2","doi-asserted-by":"crossref","unstructured":"L. Bartholdi. I. I. Reznykov A mealy machine with polynomial growth of irrational degree. Int. J. Algebr. Comput. 18 59\u201382 (2008).","DOI":"10.1142\/S0218196708004287"},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196716500156"},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2018.187.3.2"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.1090\/S1088-4165-09-00352-5"},{"key":"e_1_3_4_48_2","doi-asserted-by":"crossref","unstructured":"V. Bavula \u201cFilter dimension\u201d in Handbook of Algebra M. Hazewinkel Ed. (North-Holland 2006). vol. 4 pp. 77\u2013105.","DOI":"10.1016\/S1570-7954(06)80005-7"},{"key":"e_1_3_4_49_2","doi-asserted-by":"publisher","DOI":"10.1515\/crll.2005.2005.582.61"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.1006\/jabr.1997.7266"},{"key":"e_1_3_4_51_2","doi-asserted-by":"crossref","unstructured":"V. Bavula \u201cKrull Gelfand-Kirillov filter faithful and schur dimensions\u201d in Infinite Length Modules Trends in Mathematics H. Krause C. M. Ringel Eds. (Birkh\u00e4user Basel 2000) pp. 149\u2013166.","DOI":"10.1007\/978-3-0348-8426-6_7"},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10468-008-9091-8"}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.2627766123","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,29]],"date-time":"2026-10-29T17:37:50Z","timestamp":1793295470000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/10.1073\/pnas.2627766123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,10,29]]},"references-count":52,"journal-issue":{"issue":"44","published-print":{"date-parts":[[2026,11,3]]}},"alternative-id":["10.1073\/pnas.2627766123"],"URL":"https:\/\/doi.org\/10.1073\/pnas.2627766123","relation":{},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"value":"0027-8424","type":"print"},{"value":"1091-6490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,10,29]]},"assertion":[{"value":"2026-08-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-08-29","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-10-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"e2627766123"}}