Monochromatic arithmetic progressions in automatic sequences with group structure

DOI10.1016/J.JCTA.2023.105831arXiv2302.12908MaRDI QIDQ6187331FDOQ6187331

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

Publication date: 15 January 2024

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

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.

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)

Cites Work

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

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)