Monochromatic arithmetic progressions in automatic sequences with group structure

DOI10.1016/J.JCTA.2023.105831MaRDI QIDQ6187331zbMATH OpenFDO

Authors Ibai Aedo, Uwe Grimm, Neil Mañibo, Yasushi Nagai, Petra Staynova

Publication date 15 January 2024

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2302.12908

zbMATH Keywords

arithmetic progressionsvan der Waerden numbersbijective automataRudin-Shapiro substitutionspin substitutions

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Symbolic dynamics (37B10) Dynamical aspects of cellular automata (37B15) Arithmetic progressions (11B25)

Abstract: 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 $left{d}_{n}ight$ 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.

Recommendations

• Monochromatic arithmetic progressions in binary Thue-Morse-like words
• Reconnaissabilité des substitutions et complexité des suites automatiques
• Publication:3469152
• Generalized van der Waerden numbers
• Automatic sequences

Cites work

• scientific article; zbMATH DE number 2033289 (Why is no real title available?)
• A characterization of substitutive sequences using return words
• A coloring problem for infinite words
• A new proof of Szemerédi's theorem
• Admissible reversing and extended symmetries for bijective substitutions
• Anti-powers in infinite words
• Aperiodic order. Volume 1. A mathematical invitation
• Arithmetical complexity of symmetric D0L words.
• Asymptotic subword complexity of fixed points of group substitutions
• Automatic Sequences
• Coloring problems for infinite words
• Computing automorphism groups of shifts using atypical equivalence classes
• Consequences of pure point diffraction spectra for multiset substitution systems
• Generalized Rudin-Shapiro sequences
• Monochromatic arithmetic progressions in binary Thue-Morse-like words
• Multidimensional constant-length substitution sequences
• ON HIGHER DIMENSIONAL ARITHMETIC PROGRESSIONS IN MEYER SETS
• On arithmetic index in the generalized Thue-Morse word
• On arithmetic progressions in model sets
• On arithmetic progressions in non-periodic self-affine tilings
• On arithmetic progressions in the generalized Thue-Morse word
• Ramsey's Theorem for n-Parameter Sets
• Reversing and extended symmetries of shift spaces
• Sequences of linear arithmetical complexity
• Sequences of low arithmetical complexity
• Spectral theory of spin substitutions
• Substitution dynamical systems. Spectral analysis
• Substitution sequences in \mathbb{Z}^{d} with a non-simple Lebesgue component in the spectrum
• Substitution-based structures with absolutely continuous spectrum
• Substitutional dynamical systems, Bratteli diagrams and dimension groups
• Sur la mesure spectrale de certaines suites arithmétiques
• The Ellis semigroup of bijective substitutions
• The spectrum of dynamical systems arising from substitutions of constant length
• Thue-Morse at multiples of an integer
• Unzerlegbare, nicht negative Matrizen

Cited in

(1)

• On monochromatic arithmetic progressions in binary words associated with pattern sequences

This page was built for publication: Monochromatic arithmetic progressions in automatic sequences with group structure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187331)