Monochromatic arithmetic progressions in automatic sequences with group structure. (English) Zbl 1533.37037
Summary: We determine asymptotic growth rates for lengths of monochromatic arithmetic progressions in certain automatic sequences. In particular, we look at (one-sided) fixed points of aperiodic, primitive, bijective substitutions and spin substitutions, which are generalisations of the Thue-Morse and Rudin-Shapiro substitutions, respectively. For such infinite words, we show that there exists a subsequence \(\{d_n \}\) of differences along which the maximum length \(A(d_n)\) of a monochromatic arithmetic progression (with fixed difference \(d_n)\) grows at least polynomially in \(d_n\). Explicit upper and lower bounds for the growth exponent can be derived from a finite group associated to the substitution. As an application, we obtain bounds for a van der Waerden-type number for a class of colourings parametrised by the size of the alphabet and the length of the substitution.
MSC:
| 37B10 | Symbolic dynamics |
| 37B15 | Dynamical aspects of cellular automata |
| 05B20 | Combinatorial aspects of matrices (incidence, Hadamard, etc.) |
| 11B25 | Arithmetic progressions |
Keywords:
bijective automata; Rudin-Shapiro substitution; spin substitutions; arithmetic progressions; van der Waerden numbersReferences:
| [1] | Aedo, I., Forward limit sets of semigroups of substitutions and arithmetic progressions in automatic sequences (2023), The Open University: The Open University Milton Keynes, PhD thesis |
| [2] | Aedo, I.; Grimm, U.; Nagai, Y.; Staynova, P., Monochromatic arithmetic progressions in binary Thue-Morse-like words. Theor. Comput. Sci., 65-80 (2022) · Zbl 1537.68156 |
| [3] | Allouche, J.-P.; Liardet, P., Generalized Rudin-Shapiro sequences. Acta Arith., 1-27 (1991) · Zbl 0763.11010 |
| [4] | Allouche, J.-P.; Shallit, J., Automatic Sequences: Theory, Applications, Generalizations (2003), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1086.11015 |
| [5] | Avgustinovich, S. V.; Cassaigne, J.; Frid, A. E., Sequences of low arithmetical complexity. RAIRO Theor. Inform. Appl., 569-582 (2006) · Zbl 1110.68116 |
| [6] | Avgustinovich, S. V.; Fon-Der-Flaass, D. G.; Frid, A. E., Arithmetical complexity of infinite words, 51-62 |
| [7] | Baake, M.; Grimm, U., Aperiodic Order, vol. 1: A Mathematical Invitation (2013), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1295.37001 |
| [8] | Baake, M.; Roberts, J. A.G.; Yassawi, R., Reversing and extended symmetries of shift spaces. Discrete Contin. Dyn. Syst., 835-866 (2018) · Zbl 1377.37027 |
| [9] | Bustos, A.; Luz, D.; Mañibo, N., Admissible reversing and extended symmetries for bijective substitutions. Discrete Comput. Geom., 800-833 (2023) · Zbl 1520.37015 |
| [10] | Chan, L.; Grimm, U.; Short, I., Substitution-based structures with absolutely continuous spectrum. Indag. Math., 1072-1086 (2018) · Zbl 1393.37019 |
| [11] | Coquet, J.; Kamae, T.; Mendès France, M., Sur la mesure spectrale de certaines suites arithmétiques. Bull. Soc. Math. Fr., 369-384 (1977) · Zbl 0383.10035 |
| [12] | Coven, E.; Quas, A.; Yassawi, R., Computing automorphism groups of shifts using atypical equivalence classes. Discrete Anal. (2016) · Zbl 1378.54035 |
| [13] | Dekking, F. M., The spectrum of dynamical systems arising from substitutions of constant length. Z. Wahrscheinlichkeitstheor. Verw. Geb., 221-239 (1978) · Zbl 0348.54034 |
| [14] | Durand, F., A characterization of substitutive sequences using return words. Discrete Math., 89-101 (1998) · Zbl 0895.68087 |
| [15] | Durand, F.; Host, B.; Skau, C., Substitutive dynamical systems, Bratteli diagrams and dimension groups. Ergod. Theory Dyn. Syst., 953-993 (1999) · Zbl 1044.46543 |
| [16] | Durand, F.; Leroy, J., Decidability of isomorphism and factorization between minimal substitution subshifts. Discrete Anal. (2022), (65 pp.) |
| [17] | Fici, G.; Restivo, A.; Silva, M.; Zamboni, L., Anti-powers in infinite words. J. Comb. Theory, Ser. A, 109-119 (2018) · Zbl 1393.68141 |
| [18] | Frank, N. P., Multidimensional constant-length substitution sequences. Topol. Appl., 44-69 (2005) · Zbl 1074.37016 |
| [19] | Frank, N. P., Substitution sequences in \(\mathbb{Z}^d\) with a nonsimple Lebesgue component in the spectrum. Ergod. Theory Dyn. Syst., 519-532 (2003) · Zbl 1031.11009 |
| [20] | Frank, N. P.; Mañibo, N., Spectral theory of spin substitutions. Discrete Contin. Dyn. Syst., 5399-5435 (2022) · Zbl 1505.37025 |
| [21] | Frid, A. E., Sequences of linear arithmetical complexity. Theor. Comput. Sci., 68-87 (2005) · Zbl 1076.68053 |
| [22] | Frid, A. E., Arithmetical complexity of symmetric D0L words. Theor. Comput. Sci., 535-542 (2003) · Zbl 1070.68068 |
| [23] | Goldstein, I., Asymptotic subword complexity of fixed points of group substitutions. Theor. Comput. Sci., 2084-2098 (2009) · Zbl 1168.68025 |
| [24] | Gowers, T., A new proof of Szemerédi’s theorem. Geom. Funct. Anal., 465-588 (2001) · Zbl 1028.11005 |
| [25] | Graham, R. L.; Rothschild, B. L., Ramsey’s theorem for \(n\)-parameter sets. Trans. Am. Math. Soc., 257-292 (1971) · Zbl 0233.05003 |
| [26] | Kellendonk, J.; Yassawi, R., The Ellis semigroup of bijective substitutions. Groups Geom. Dyn., 29-73 (2022) · Zbl 1498.37017 |
| [27] | Klick, A.; Strungaru, N., On higher dimensional arithmetic progressions in Meyer sets. J. Aust. Math. Soc., 312-336 (2023) · Zbl 1529.11015 |
| [28] | Klick, A.; Strungaru, N.; Tcaciuc, A., On arithmetic progressions in model sets. Discrete Comput. Geom., 930-946 (2022) · Zbl 1511.11009 |
| [29] | Landman, B. M.; Robertson, A., Ramsey Theory on the Integers (2004), American Mathematical Society: American Mathematical Society USA · Zbl 1035.05096 |
| [30] | Lee, J.-Y.; Moody, R. V.; Solomyak, B., Consequences of pure point diffraction spectra for multiset substitution systems. Discrete Comput. Geom., 525-560 (2003) · Zbl 1055.37019 |
| [31] | Lemańczyk, M.; Müllner, C., Automatic sequences are orthogonal to aperiodic multiplicative functions. Discrete Contin. Dyn. Syst., 6877-6918 (2020) · Zbl 1454.37020 |
| [32] | de Luca, A.; Pribavkina, E. V.; Zamboni, L. Q., A coloring problem for infinite words. J. Comb. Theory, Ser. A, 306-332 (2014) · Zbl 1295.05256 |
| [33] | Morgenbesser, J. F.; Shallit, J.; Stoll, T., Thue-Morse at multiples of an integer. J. Number Theory, 1498-1512 (2011) · Zbl 1246.11159 |
| [34] | Nagai, Y.; Akiyama, S.; Lee, J.-Y., On arithmetic progressions in non-periodic self-affine tilings. Ergod. Theory Dyn. Syst., 2957-2989 (2022) · Zbl 1503.37036 |
| [35] | Parshina, O. G., Homogeneous arithmetic progressions in the Thue-Morse word · Zbl 1330.68239 |
| [36] | Parshina, O. G., On arithmetic progressions in the generalized Thue-Morse word, 191-196 · Zbl 1330.68239 |
| [37] | Parshina, O. G., On arithmetic index in the generalized Thue-Morse word, 121-131 · Zbl 1405.68269 |
| [38] | Queffélec, M., Substitution Dynamical Systems — Spectral Analysis (2010), Springer: Springer Berlin · Zbl 1225.11001 |
| [39] | Sobolewski, B., On monochromatic arithmetic progressions in binary words associated with pattern sequences (2022), preprint |
| [40] | van der Waerden, B. L., Beweis einer Baudetschen Vermutung. Nieuw Arch. Wiskd., 212-216 (1927) · JFM 53.0073.12 |
| [41] | Wielandt, H., Unzerlegbare nichtnegative Matrizen. Math. Z., 642-645 (1950) · Zbl 0035.29101 |
| [42] | Wojcik, C.; Zamboni, L. Q., Colouring problems for infinite words, 213-231 · Zbl 1405.05005 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
