On monochromatic arithmetic progressions in binary words associated with pattern sequences

2022/04/11 by Sobolewski, Bartosz
#Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2204.05287

Abstract

Let e_v(n) denote the number of occurrences of a fixed pattern v in the binary expansion of n ∈ ℕ. In this paper we study monochromatic arithmetic progressions in the class of binary words (e_v(n) \bmod2)_{n ≥ 0}, which includes the famous Thue--Morse word t and Rudin--Shapiro word r. We prove that the length of a monochromatic arithmetic progression of difference d ≥ 3 starting at 0 in r is at most (d+3)/2, with equality for infinitely many d. Moreover, we compute the maximal length of a monochromatic arithmetic progression in r of difference 2^k-1 and 2^k+1. For a general pattern v we provide an upper bound on the length of a monochromatic arithmetic progression of any difference d. We also prove other miscellaneous results and offer a number of related problems and conjectures.

Related

• Monochromatic arithmetic progressions in automatic sequences with group structure
• Monochromatic arithmetic progressions in the Fibonacci, Thue-Morse, and Rudin-Shapiro words
• From discrete to continuous: Monochromatic 3-term arithmetic progressions
• Enumeration of monochromatic three term arithmetic progressions in two-colorings of any finite group
• Enumeration of monochromatic three term arithmetic progressions in two-colorings of cyclic groups