Bracket words: A generalisation of Sturmian words arising from generalised polynomials

Adamczewski, Boris; Konieczny, Jakub

doi:10.1090/tran/8906

Bracket words: A generalisation of Sturmian words arising from generalised polynomials
HTML articles powered by AMS MathViewer

by Boris Adamczewski and Jakub Konieczny;

Trans. Amer. Math. Soc. 376 (2023), 4979-5044

DOI: https://doi.org/10.1090/tran/8906

Published electronically: April 19, 2023

HTML | PDF | Request permission

Abstract:

Generalised polynomials are maps constructed by applying the floor function, addition, and multiplication to polynomials. Despite superficial similarity, generalised polynomials exhibit many phenomena which are impossible for polynomials. In particular, there exist generalised polynomial sequences which take only finitely many values without being periodic; examples of such sequences include the Sturmian words, as well as more complicated sequences like $\left \lfloor 2\left \{ \pi n^2 + \sqrt {2}n\left \lfloor \sqrt {3}n \right \rfloor \right \} \right \rfloor$.

The purpose of this paper is to investigate letter-to-letter codings of finitely-valued generalised polynomial sequences, which we call bracket words, from the point of view of combinatorics on words. We survey existing results on generalised polynomials and their corollaries in terms of bracket words, and also prove several new results. Our main contribution is a polynomial bound on the subword complexity of bracket words.

References

George E. Andrews, Richard A. Askey, Bruce C. Berndt, K. G. Ramanathan, and Robert A. Rankin (eds.), Ramanujan revisited, Academic Press, Inc., Boston, MA, 1988. MR 938955
Boris Adamczewski, Balances for fixed points of primitive substitutions, Theoret. Comput. Sci. 307 (2003), no. 1, 47–75. Words. MR 2014730, DOI 10.1016/S0304-3975(03)00092-6
Boris Adamczewski, Symbolic discrepancy and self-similar dynamics, Ann. Inst. Fourier (Grenoble) 54 (2004), no. 7, 2201–2234 (2005) (English, with English and French summaries). MR 2139693, DOI 10.5802/aif.2079
L. Auslander, L. Green, and F. Hahn, Flows on homogeneous spaces, Annals of Mathematics Studies, No. 53, Princeton University Press, Princeton, NJ, 1963. With the assistance of L. Markus and W. Massey, and an appendix by L. Greenberg. MR 167569, DOI 10.1515/9781400882021
Jean-Paul Allouche, Sur la complexité des suites infinies, Bull. Belg. Math. Soc. Simon Stevin 1 (1994), no. 2, 133–143 (French, with English and French summaries). Journées Montoises (Mons, 1992). MR 1318964
Jean-Paul Allouche and Jeffrey Shallit, The ring of $k$-regular sequences, Theoret. Comput. Sci. 98 (1992), no. 2, 163–197. MR 1166363, DOI 10.1016/0304-3975(92)90001-V
Jean-Paul Allouche and Jeffrey Shallit, Automatic sequences, Cambridge University Press, Cambridge, 2003. Theory, applications, generalizations. MR 1997038, DOI 10.1017/CBO9780511546563
J.-P. Allouche, J. Shallit, and R. Yassawi, How to prove that a sequence is not automatic, Expo. Math. 40 (2022), no. 1, 1–22. MR 4388977, DOI 10.1016/j.exmath.2021.08.001
Jacek Bochnak, Michel Coste, and Marie-Françoise Roy, Real algebraic geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 36, Springer-Verlag, Berlin, 1998. Translated from the 1987 French original; Revised by the authors. MR 1659509, DOI 10.1007/978-3-662-03718-8
Valérie Berthé, Autour du système de numération d’Ostrowski, Bull. Belg. Math. Soc. Simon Stevin 8 (2001), no. 2, 209–239 (French, with French summary). Journées Montoises d’Informatique Théorique (Marne-la-Vallée, 2000). MR 1838931
Vitaly Bergelson, Ultrafilters, IP sets, dynamics, and combinatorial number theory, Ultrafilters across mathematics, Contemp. Math., vol. 530, Amer. Math. Soc., Providence, RI, 2010, pp. 23–47. MR 2757532, DOI 10.1090/conm/530/10439
Vitaly Bergelson and Inger Johanne Håland, Sets of recurrence and generalized polynomials, Convergence in ergodic theory and probability (Columbus, OH, 1993) Ohio State Univ. Math. Res. Inst. Publ., vol. 5, de Gruyter, Berlin, 1996, pp. 91–110. MR 1412598
Vitaly Bergelson, Inger J. Håland Knutson, and Younghwan Son, An extension of Weyl’s equidistribution theorem to generalized polynomials and applications, Int. Math. Res. Not. IMRN 19 (2021), 14965–15018. MR 4324734, DOI 10.1093/imrn/rnaa035
Jakub Byszewski and Jakub Konieczny, Sparse generalised polynomials, Trans. Amer. Math. Soc. 370 (2018), no. 11, 8081–8109. MR 3852458, DOI 10.1090/tran/7257
Jakub Byszewski and Jakub Konieczny, Automatic sequences and generalised polynomials, Canad. J. Math. 72 (2020), no. 2, 392–426. MR 4081697, DOI 10.4153/s0008414x19000038
J. Byszewski and J. Konieczny, Pisot numbers, salem numbers, and generalised polynomials, 2022, In preparation. arXiv:2302.06242
Vitaly Bergelson and Alexander Leibman, Distribution of values of bounded generalized polynomials, Acta Math. 198 (2007), no. 2, 155–230. MR 2318563, DOI 10.1007/s11511-007-0015-y
V. Bergelson and A. Leibman, $\textrm {IP}_r^\ast$-recurrence and nilsystems, Adv. Math. 339 (2018), 642–656. MR 3866908, DOI 10.1016/j.aim.2018.09.032
V. Bergelson, J. Moreira, and F. K. Richter, Multiple ergodic averages along functions from a Hardy field: convergence, recurrence and combinatorial applications, 2020, Preprint, arXiv:2006.03558 [math.DS].
M.-P. Béal, D. Perrin, and A. Restivo, Decidable problems in substitution shifts, 2021, Preprint, arXiv:2112.14499 [math.DS].
J. W. S. Cassels, An introduction to Diophantine approximation, Cambridge Tracts in Mathematics and Mathematical Physics, No. 45, Hafner Publishing Co., New York, 1972. Facsimile reprint of the 1957 edition. MR 349591
Yong-Gao Chen, The best quantitative Kronecker’s theorem, J. London Math. Soc. (2) 61 (2000), no. 3, 691–705. MR 1766098, DOI 10.1112/S0024610700008772
Julien Cassaigne and Juhani Karhumäki, Toeplitz words, generalized periodicity and periodically iterated morphisms, European J. Combin. 18 (1997), no. 5, 497–510. MR 1455183, DOI 10.1006/eujc.1996.0110
Julien Cassaigne and François Nicolas, Factor complexity, Combinatorics, automata and number theory, Encyclopedia Math. Appl., vol. 135, Cambridge Univ. Press, Cambridge, 2010, pp. 163–247. MR 2759107
Émilie Charlier, Narad Rampersad, and Jeffrey Shallit, Enumeration and decidable properties of automatic sequences, Internat. J. Found. Comput. Sci. 23 (2012), no. 5, 1035–1066. MR 2983367, DOI 10.1142/S0129054112400448
S. Chow and N. Technau, Counting multiplicative approximations, Ramanujan J. (2022).
H. Davenport, On some infinite series involving arithmetical functions (II), The Quarterly Journal of Mathematics, os-8(1): 313–320, 01 1937.
Michael Drmota, Clemens Müllner, and Lukas Spiegelhofer, Möbius orthogonality for the Zeckendorf sum-of-digits function, Proc. Amer. Math. Soc. 146 (2018), no. 9, 3679–3691. MR 3825824, DOI 10.1090/proc/14015
Tomasz Downarowicz, Survey of odometers and Toeplitz flows, Algebraic and topological dynamics, Contemp. Math., vol. 385, Amer. Math. Soc., Providence, RI, 2005, pp. 7–37. MR 2180227, DOI 10.1090/conm/385/07188
Fabien Durand, Decidability of the HD0L ultimate periodicity problem, RAIRO Theor. Inform. Appl. 47 (2013), no. 2, 201–214. MR 3072319, DOI 10.1051/ita/2013035
Fabien Durand, Decidability of uniform recurrence of morphic sequences, Internat. J. Found. Comput. Sci. 24 (2013), no. 1, 123–146. MR 3061952, DOI 10.1142/S0129054113500032
Tanja Eisner, Nilsystems and ergodic averages along primes, Ergodic Theory Dynam. Systems 40 (2020), no. 10, 2769–2777. MR 4138910, DOI 10.1017/etds.2019.27
Manfred Einsiedler, Anatole Katok, and Elon Lindenstrauss, Invariant measures and the set of exceptions to Littlewood’s conjecture, Ann. of Math. (2) 164 (2006), no. 2, 513–560. MR 2247967, DOI 10.4007/annals.2006.164.513
Sébastien Ferenczi, Complexity of sequences and dynamical systems, Discrete Math. 206 (1999), no. 1-3, 145–154. Combinatorics and number theory (Tiruchirappalli, 1996). MR 1665394, DOI 10.1016/S0012-365X(98)00400-2
T. Fernique, Multidimensional Sturmian sequences and generalized substitutions, Internat. J. Found. Comput. Sci. 17(3): 575–599, 2006.
Nikos Frantzikinakis and Bernard Host, Higher order Fourier analysis of multiplicative functions and applications, J. Amer. Math. Soc. 30 (2017), no. 1, 67–157. MR 3556289, DOI 10.1090/jams/857
Nikos Frantzikinakis, Equidistribution of sparse sequences on nilmanifolds, J. Anal. Math. 109 (2009), 353–395. MR 2585398, DOI 10.1007/s11854-009-0035-y
Daniel Goč, Dane Henshall, and Jeffrey Shallit, Automatic theorem-proving in combinatorics on words, Internat. J. Found. Comput. Sci. 24 (2013), no. 6, 781–798. MR 3158968, DOI 10.1142/S0129054113400182
Sigrid Grepstad and Nir Lev, Sets of bounded discrepancy for multi-dimensional irrational rotation, Geom. Funct. Anal. 25 (2015), no. 1, 87–133. MR 3320890, DOI 10.1007/s00039-015-0313-z
Ron Graham and Kevin O’Bryant, Can you hear the shape of a Beatty sequence?, Additive number theory, Springer, New York, 2010, pp. 39–52. MR 2744742, DOI 10.1007/978-0-387-68361-4_{3}
W. T. Gowers, A new proof of Szemerédi’s theorem, Geom. Funct. Anal. 11 (2001), no. 3, 465–588. MR 1844079, DOI 10.1007/s00039-001-0332-9
Ben Green and Terence Tao, An arithmetic regularity lemma, an associated counting lemma, and applications, An irregular mind, Bolyai Soc. Math. Stud., vol. 21, János Bolyai Math. Soc., Budapest, 2010, pp. 261–334. MR 2815606, DOI 10.1007/978-3-642-14444-8_{7}
Benjamin Green and Terence Tao, Linear equations in primes, Ann. of Math. (2) 171 (2010), no. 3, 1753–1850. MR 2680398, DOI 10.4007/annals.2010.171.1753
Ben Green and Terence Tao, The Möbius function is strongly orthogonal to nilsequences, Ann. of Math. (2) 175 (2012), no. 2, 541–566. MR 2877066, DOI 10.4007/annals.2012.175.2.3
Ben Green and Terence Tao, The quantitative behaviour of polynomial orbits on nilmanifolds, Ann. of Math. (2) 175 (2012), no. 2, 465–540. MR 2877065, DOI 10.4007/annals.2012.175.2.2
Ben Green, Terence Tao, and Tamar Ziegler, An inverse theorem for the Gowers $U^{s+1}[N]$-norm, Ann. of Math. (2) 176 (2012), no. 2, 1231–1372. MR 2950773, DOI 10.4007/annals.2012.176.2.11
Inger Johanne Håland, Uniform distribution of generalized polynomials, J. Number Theory 45 (1993), no. 3, 327–366. MR 1247389, DOI 10.1006/jnth.1993.1082
Inger Johanne Håland, Uniform distribution of generalized polynomials of the product type, Acta Arith. 67 (1994), no. 1, 13–27. MR 1292518, DOI 10.4064/aa-67-1-13-27
E. F. Harding, The number of partitions of a set of $N$ points in $k$ dimensions induced by hyperplanes, Proc. Edinburgh Math. Soc. (2) 15 (1966/67), 285–289. MR 229128, DOI 10.1017/S0013091500011925
Bernard Host and Bryna Kra, Nonconventional ergodic averages and nilmanifolds, Ann. of Math. (2) 161 (2005), no. 1, 397–488. MR 2150389, DOI 10.4007/annals.2005.161.397
Bernard Host, Bryna Kra, and Alejandro Maass, Complexity of nilsystems and systems lacking nilfactors, J. Anal. Math. 124 (2014), 261–295. MR 3286054, DOI 10.1007/s11854-014-0032-7
Jakub Konieczny, Combinatorial properties of Nil-Bohr sets, Israel J. Math. 220 (2017), no. 1, 333–385. MR 3666828, DOI 10.1007/s11856-017-1520-0
Jakub Konieczny, Generalised polynomials and integer powers, J. Lond. Math. Soc. (2) 105 (2022), no. 1, 154–219. MR 4411322, DOI 10.1112/jlms.12509
Daniel Krenn and Jeffrey Shallit, Decidability and $k$-regular sequences, Theoret. Comput. Sci. 907 (2022), 34–44. MR 4383214, DOI 10.1016/j.tcs.2022.01.018
A. Leibman, Pointwise convergence of ergodic averages for polynomial sequences of translations on a nilmanifold, Ergodic Theory Dynam. Systems 25 (2005), no. 1, 201–213. MR 2122919, DOI 10.1017/S0143385704000215
A. Leibman, A canonical form and the distribution of values of generalized polynomials, Israel J. Math. 188 (2012), 131–176. MR 2897727, DOI 10.1007/s11856-011-0097-2
Robert J. Lemke Oliver and Kannan Soundararajan, Unexpected biases in the distribution of consecutive primes, Proc. Natl. Acad. Sci. USA 113 (2016), no. 31, E4446–E4454. MR 3624386, DOI 10.1073/pnas.1605366113
A. I. Mal′cev, On a class of homogeneous spaces, Izv. Akad. Nauk SSSR Ser. Mat. 13 (1949), 9–32 (Russian). MR 28842
A. I. Malcev, On a class of homogeneous spaces, Amer. Math. Soc. Translation 1951 (1951), no. 39, 33. MR 39734
Yuri V. Matiyasevich, Hilbert’s tenth problem, Foundations of Computing Series, MIT Press, Cambridge, MA, 1993. Translated from the 1993 Russian original by the author; With a foreword by Martin Davis. MR 1244324
Marston Morse and Gustav A. Hedlund, Symbolic Dynamics, Amer. J. Math. 60 (1938), no. 4, 815–866. MR 1507944, DOI 10.2307/2371264
H. Mousavi, Automatic theorem proving in walnut, 2016, Preprint, arXiv:1603.06017 [math.FL].
F. K. Richter, Uniform distribution in nilmanifolds along functions from a Hardy field, JAMA (2022). DOI 10.1007/s11854-022-0253-0.
Michel Rigo, Formal languages, automata and numeration systems. 2, Networks and Telecommunications Series, ISTE, London; John Wiley & Sons, Inc., Hoboken, NJ, 2014. Applications to recognizability and decidability; With a foreword by Valérie Berthé. MR 3526118
Wolfgang M. Schmidt, Norm form equations, Ann. of Math. (2) 96 (1972), 526–551. MR 314761, DOI 10.2307/1970824
Alexander N. Starkov, Dynamical systems on homogeneous spaces, Translations of Mathematical Monographs, vol. 190, American Mathematical Society, Providence, RI, 2000. Translated from the 1999 Russian original by the author. MR 1746847, DOI 10.1090/mmono/190
Terence Tao, Higher order Fourier analysis, Graduate Studies in Mathematics, vol. 142, American Mathematical Society, Providence, RI, 2012. MR 2931680, DOI 10.1090/gsm/142
Terence Tao and Van Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012, DOI 10.1017/CBO9780511755149
R. C. Vaughan, The Hardy-Littlewood method, 2nd ed., Cambridge Tracts in Mathematics, vol. 125, Cambridge University Press, Cambridge, 1997. MR 1435742, DOI 10.1017/CBO9780511470929
Peter Walters, An introduction to ergodic theory, Graduate Texts in Mathematics, vol. 79, Springer-Verlag, New York-Berlin, 1982. MR 648108, DOI 10.1007/978-1-4612-5775-2
Morgan Ward, The arithmetical theory of linear recurring series, Trans. Amer. Math. Soc. 35 (1933), no. 3, 600–628. MR 1501705, DOI 10.1090/S0002-9947-1933-1501705-4
Yuan Wang and Kun Rui Yu, A note on some metrical theorems in Diophantine approximation, Chinese Ann. Math. 2 (1981), no. 1, 1–12 (English, with Chinese summary). MR 619457, DOI 10.1007/bf00646384
Soroosh Yazdani, Multiplicative functions and $k$-automatic sequences, J. Théor. Nombres Bordeaux 13 (2001), no. 2, 651–658 (English, with English and French summaries). MR 1879677, DOI 10.5802/jtnb.342
Tamar Ziegler, Universal characteristic factors and Furstenberg averages, J. Amer. Math. Soc. 20 (2007), no. 1, 53–97. MR 2257397, DOI 10.1090/S0894-0347-06-00532-7