chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2023-24-4-63-77cheb-1595Research ArticleСтатьиArticleКомбинаторные сложностные характеристики слов ШтурмаOn the complexity functions of Sturmian wordsКироваВалерия ОрлановнаKirovaValeria Orlanovnakirova_vo@mail.ruГодуновИгорь ВалентиновичGodunovIgor Valentinovichgodunov.biz@gmail.comМосковский государственный университет им. М. В. ЛомоносоваРоссияLomonosov Moscow State UniversityRussian FederationРоссийский государственный социальный университетРоссияRussian State Social UniversityRussian Federation2023250120242446377Copyright © Кирова В.О., Годунов И.В., 20232023Кирова В.О., Годунов И.В.Kirova V.O., Godunov I.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/1595

В статье рассматриваются комбинаторные сложностные характеристики бесконечных слов, а именно комбинаторная сложность и ее модификации. Прежде всего, представлен обзор имеющихся результатов для класса слов с наименьшей комбинаторной сложностью- слов Штурма. Особое внимание уделено арифметической сложности бесконечных слов,начало изучение которой положила Теорема Ван дер Вардена об одноцветных арифметических прогрессиях. Арифметическая сложность является в некотором смысле модификацией комбинаторной сложности. Представлен обзор текущих результатов и точных значений арифметической сложности для слов Штурма. В статье представлена полиномиальная Теорема Ван дер Вардена, дающая начало изучению более обобщенной модификации функции комбинаторной сложности - полиномиальной сложности бесконечных слов.В завершение, мы представляем ряд открытых проблем для дальнейшего исследования.

The key issue of the paper is combinatorial complexity functions of infinite words, especially factor complexity and its modifications. First of all, we present an overview of the available results for the class of words with the minimal factor complexity - Sturmian words. Specialattention is paid to the arithmetical complexity of infinite words, the study of which was initiatedby Van der Waarden Theorem on one-color arithmetic progressions. Arithmetical complexity is presented in a sense a modification of factor complexity. An overview of current results and exact values of arithmetic complexity for Sturmian words is presented. We present polynomial Van der Waerden Theorem, which gives rise to the study of a more generalized modification ofthe factor complexity function - the polynomial complexity of infinite words. In conclusion, wepresent open problems for further research.

Cлова Штурмакомбинаторная сложностьарифметическая сложностьполиномиальная сложность.Sturmian wordfactor complexityarithmetical complexitypolynomial complexity.ReferencesBanks W. D., Conflitti A., Shparlinski I. E. Character sums over integers with restricted 𝑔-aryBanks, W. D., Conflitti, A. & Shparlinski, I. E. 2002, “Character sums over integers withdigits // Illinois J. Math. 2002. Vol. 46, №3. P. 819-836.restricted 𝑔-ary digits”, Illinois J. Math., vol. 46, no. 3, pp. 819-836.Avgustinovich S., Cassaigne J., Frid A. Sequences of low arithmetical complexity // Theoret.Avgustinovich S., Cassaigne J., Frid A. E. 2006, “Sequences of low arithmetical complexity”Inform. Appl. 40 (2006) P. 569–582Theoret. Inform. Appl. vol.40, pp. 569–582.Allouche J.-P. Baake M. Cassaigne J., Damanik D. Palindrome complexity Selected papersAllouche J.-P. Baake M. Cassaigne J., Damanik D. E. 2003, “Palindrome complexity Selectedin honor of Jean Berstel // Theoret. Comput. Sci. 292 (2003), no. 1, p. 9–31.papers in honor of Jean Berstel” Theoret. Comput. Sci. vol. 292, no. 1, pp. 9–31.Avgustinovich S. V. , Fon-Der-Flaass D. G. , Frid A. E. Arithmetical complexity of infniteAvgustinovich S. V. , Fon-Der-Flaass D. G. , Frid A. E. E.2003 “Arithmetical complexity ofwords // Proc. Words, Languages and Combinatorics III, 2000. Singapore: World Scientifc,infnite words” Proc. Words, Languages and Combinatorics III, Singapore: World Scientifc, pp.P. 51-62.-62.Berstel J., P. Seebold. Sturmian words, in: M. Lothaire, Algebraic Combinatorics on Words //Berstel J., P. Seebold. E.2002 “Sturmian words, in: M. Lothaire, Algebraic Combinatorics onCambridge University Press, 2002. P. 40-97.Words”, Cambridge University Press, pp. 40-97.Berstel J., M. Pocchiola.A geometric proof of the enumeration formula for Sturmian words//Berstel J., M. Pocchiola. E.1993 “A geometric proof of the enumeration formula for SturmianInt. J. Algebra and Comput., 1993, V. 3, 349 -355.words”, Int. J. Algebra and Comput., vol 3, pp. 349 -355.Bell, J. P., Shallit, J. Lie complexity of words// Theoret. Comput. Sci. in press (2022).Bell, J. P., Shallit, J. E. 2022 “Lie complexity of words”, Theoret. Comput. Sci. in press.Brown C.A characterization of the quadratic irrationals// Canad. Math. Bull. (1991), 364Brown C. E.1991 “A characterization of the quadratic irrationals”, Canad. Math. Bull., vol.36.Bresenham J. E. Algorithm for computer control of a digital plotter. IBM Systems J. (1965),Bresenham J. E. E.1965 “Algorithm for computer control of a digital plotter.”, IBM Systems-30.pp. 25-30.Cassaigne J., E.A. Frid. On the arithmetical complexity of Sturmian words// TheoreticalCassaigne J., E.A. Frid. E. 2007 “On the arithmetical complexity of Sturmian words”,Computer Science, 2007, V. 380, P.304-316.Theoretical Computer Science, vol. 380, pp.304-316.Cassaigne J., Fici, G., Sciortino, M., and Zamboni, L. Cyclic complexity of words// J. Combin.Cassaigne J., Fici, G., Sciortino, M., Zamboni, L. E.2017 “Cyclic complexity of words”, J.Theory Ser. A 145 (2017), 36–56.Combin. Theory Ser. , vol. 145 , pp. 36–56.Cassaigne J., Richomme, G., Saari, K., and Zamboni, L. Avoiding. Abelian powers in binaryCassaigne J., Richomme, G., Saari, K., Zamboni, L. Avoiding. E.2011 “Abelian powers in binary words with bounded Abelian complexity”, Internat J. Found. Comput. Sci. vol.22, no. 4, pp.905–920.words with bounded Abelian complexity. Internat// J. Found. Comput. Sci. 22, 4 (2011),Cassaigne J., Kabor´e, I., Tapsoba, T. E.2010 “On a new notion of complexity on infinite–920.words.”, Acta Univ. Sapientiae Math. vol. 2, no. 2 , pp. 127–136.Cassaigne J., Kabor´e, I., Tapsoba, T. On a new notion of complexity on infinite words. ActaEthan M. Coven, Hedlund G. E.1973 “ Sequences with minimal block growth”, MathematicalUniv. Sapientiae Math. 2, 2 (2010), 127–136.systems theory vol. 7, pp. 138–153.Ethan M. Coven, Hedlund G. Sequences with minimal block growth Mathematical systemsDulucq S., D. Gouyou-Beauchamp. E.1987 “ Sur les facteurs des suites de Sturm”, Rapport No. I-8735, Comput. Sci.theory volume 7, 138–153, 1973A. Frid. E.2005 “Sequences of linear arithmetical complexity”, Theoret. Comput. Sci. vol. 339,Dulucq S., D. Gouyou-Beauchamp. Sur les facteurs des suites de Sturm, Rapport No. I-8735, Comput. Sci., 1987.pp. 68–87.A. Frid. Sequences of linear arithmetical complexity// Theoret. Comput. Sci. 339 (2005) 68–87.A. Frid “A lower bound for the arithmetical complexity of Sturmian words”, Siberian Electron.A. FridA lower bound for the arithmetical complexity of Sturmian words// Siberian Electron.Math. Rep. 2, pp. 14–22.Math. Rep. 2, 14–22 (in Russian, English abstract).Fraenkel A.S., M. Mushkin, U. Tassa. E. 1978 “Determination of by [𝑛𝜃] its sequence ofFraenkel A.S., M. Mushkin, U. Tassa. Determination of by [𝑛𝜃] its sequence of differences//differences”, Canad. Math. Bull. , pp. 441-446.Canad. Math. Bull. (1978), 441-446.Kamae, T., and Zamboni, L. E. 2002 “Sequence entropy and the maximal pattern complexityKamae, T., and Zamboni, L. Sequence entropy and the maximal pattern complexity of infiniteof infinite words”, Ergodic Theory and Dynamical Systems vol.22, no.4, pp. 1191–1199.words// Ergodic Theory and Dynamical Systems 22, 4 (2002), 1191–1199.Karhumaki, J., Saarela, A., and Zamboni, L. Q. E. 2013, “On a generalization of abelianKarhumaki, J., Saarela, A., and Zamboni, L. Q. On a generalization of abelian equivalence and complexity of infinite words// J. Combin. Theory, Ser. A 120, 8 (2013), 2189–2206equivalence and complexity of infinite words”, J. Combin. Theory, Ser. A 120, no.8, pp.Hedlund G.A. , M. Morse. Symbolic dynamics// Amer. J. Math, 1938, 815-866.–2206.Hedlund G.A., M. Morse. Sturmian sequences// Amer. J. Math, 1940.Hedlund G.A. , M. Morse. E.1978, “Symbolic dynamics”, Amer. J. Math, pp. 815-866.Hedlund G.A. Sturmian minimal sets// Amer. J. Math, 1944, 605-620.Hedlund G.A., M. Morse. E.1940 “Sturmian sequences”, Amer. J. Math.Ito S., Yasutomi S. On continued fractions, substitutions and characteristic sequences // Japan. J. Math., 1990, 287-306.Hedlund G.A. E.1944 “Sturmian minimal sets”, Amer. J. Math, pp. 605-620.Leibman A., Bergelson V. Polynomial extensions of van der Waerden’s and Szemeredi’sIto S., Yasutomi S. E.1990, “On continued fractions, substitutions and characteristic sequences”, Japan. J. Math., pp. 287-306.theorems // Journal of the American Math Society, Vol. 9, 1996, 725-753.Leibman A., Bergelson V. “ Polynomial extensions of van der Waerden’s and Szemeredi’sMignosi F.On the number of factors of Sturmian words// Theoret. Comput. Sci. 1991, 71-84.theorems ”, Journal of the American Math Society, Vol. 9, 1996, pp. 725-753.Mignosi, F., and Restivo, A.A new complexity function for words based on periodicity // Int.Mignosi F. E.1991, “On the number of factors of Sturmian words”, Theoret. Comput. Sci. pp.J. Algebra Comput. 23, 4 (2013), 963–988.-84.Queffelec M. Substitution Dynamical Systems// Spectral Analysis Lecture Notes Math.,vol.Mignosi, F., and Restivo, A. E.2013, “A new complexity function for words based on, Springer-Verlag, 1987.periodicity”, Int. J. Algebra Comput. vol.23, no.4, pp. 963–988.Rauzy G. Suites a termes dans un alphabet fini, Semin // Theorie des Nombres, 1982-1983,Queffelec M. E.1987, “Substitution Dynamical Systems”, Spectral Analysis Lecture Notes Math., vol. 1294, Springer-Verlag.-01,25-16, Bordeaux.Rauzy G. E.1982-1983, “Suites a termes dans un alphabet fini, Semin”, Theorie des Nombres, 25-01,25-16, Bordeaux.Rauzy G. Mots infinis en arithmetique, in :Automata on infinite words (D. Perrin ed.)// Lect.Rauzy G. E.1985, “Mots infinis en arithmetique, in :Automata on infinite words (D. PerrinNotes Comp. Sci. 1985, 165-171.ed.)”, Lect. Notes Comp. Sci. pp. 165-171.Rauzy G. Sequences defined by iterated morphisms, in :Workshop on Sequences (R. Capocelli ed.)// Lecture Notes Comput. Sci., to appear.Rauzy G. “Sequences defined by iterated morphisms, in :Workshop on Sequences (R. Capocelli ed.)”, Lecture Notes Comput. Sci., to appear.Rigo M. and Salimov, P. Another generalization of abelian equivalence: Binomial complexityRigo M. and Salimov, P. E. 2015, “Another generalization of abelian equivalence: Binomialof infinite words// Theoret. Comput. Sci. 601 (2015), 47–57.complexity of infinite words”, Theoret. Comput. Sci. no.601, pp. 47–57.Seebold P. Fibonacci morphisms and Sturmian words// Theoret. Comput. Sci. 1991, 367-384.Seebold P. E.1991, “Fibonacci morphisms and Sturmian words”, Theoret. Comput. Sci. ,Series C. The geometry of Marhoff numbers// The Mathematical Intelligencer (1985), 20-29.pp.367-384.Stolarsky K. Beatty sequences, continued fractions, and certain shift operators// Cand. Math.Series C. E.1985, “The geometry of Marhoff numbers”, The Mathematical Intelligencer , pp.Bull. (1976), 473-482.-29.Szemeredi E. On sets of integers containing no k elements in arithmetic progression// ActaStolarsky K. E.1976 “Beatty sequences, continued fractions, and certain shift operators”, Cand. Math. Bull. , pp. 473-482.Arithm. 1975. V. 27. P. 199-245.Szemeredi E. E.1975 “On sets of integers containing no k elements in arithmetic progression”, Acta Arithm. . vol. 27, pp. 199-245.E. Szemeredi // Regular partitions of graphs Computer science department, School of Humanities and Sciences, Stanford University, 1975E. Szemeredi “Regular partitions of graphs”, Computer science department, School of Humanities and Sciences, Stanford University, 1975Thue A. Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen// Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania, 1912.Thue A. E.1912 “Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen”, NorskeThue A. Uber unendliche Zeichenreihen // Norske Vid. Skrifter I Mat. Nat. Kl., ChristianiaVid. Skrifter I Mat.-Nat. Kl., Christiania.V. 7 P. 1 22. V. 10. P. 1-67.Thue A. E.1906, “Uber unendliche Zeichenreihen ”, Norske Vid. Skrifter I Mat. Nat. Kl.,Venkov A. Elementary Number Theory// Wolter-Noordho, Groningen, 1970.Christiania. vol. 7 pp. 1-22., vol. 10., pp. 1-67.Van der Waerden B.L, Beweis einer Baudetschen Vermutung // Nieuw Arch. Wisk., 15 (1927),212–216.Venkov A. E.1970, “Elementary Number Theory”, Wolter-Noordho, Groningen.Шкредов И. Д. Теорема Семереди и задачи об арифметических прогрессиях // УМН,Van der Waerden B.L, “Beweis einer Baudetschen Vermutung”, Nieuw Arch. Wisk., 15 (1927),pp. 212–216.:6(372) (2006), 111–178; Russian Math. Surveys, 61:6 (2006), 1101–1166Shkredov I. D. 2006, “Semeredi’s theorem and problems of arithmetic progressions”, Achievements of mathematical sciences, 61:6(372), 111–178; Russian Math. Surveys, 61:6, pp.–1166.–1166.

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