2023/10/02 by Sergey Dovgal, Dovgal, Sergey, Sergey Kirgizov +1 · 1 citation
Computer Science · Mathematics · #semigroups and automata theory #Advanced Combinatorial Mathematics #Coding theory and cryptography
paper · pdf · doi:10.48550/arxiv.2310.01213
A binary word is called q-decreasing, for q>0, if inside this word each of length-maximal (in the local sense) occurrences of a factor of the form 0a1b, a>0, satisfies q ⋅ a > b. We bijectively link q-decreasing words with certain prefixes of the cutting sequence of the line y=qx. We show that for any real positive q the number of q-decreasing words of length n grows as Cq ⋅ Φ(q)n for some constant Cq which depends on q but not on n. From previous works, it is already known that Φ(1) is the golden ratio, Φ(2) is equal to the tribonacci constant, Φ(k) is (k+1)-bonacci constant. We prove that the function Φ(q) is strictly increasing, discontinuous at every positive rational point, and exhibits a fractal structure related to the Stern-Brocot tree and Minkowski's question mark function.