Timeline for Binary words that are nonconstant on long arithmetic progressions
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 28, 2021 at 18:50 | comment | added | Ronnie Pavlov | As zeb said, for a Sturmian, the max length of a constant run of $0$ or $1$ is just $\lfloor \max \left( \frac{1}{1 - \alpha}, \frac{1}{\alpha} \right) \rfloor$. And for a Sturmian $x$ with rotation number $\alpha$, $x_{a \pmod k}$ is a Sturmian with rotation number $k\alpha$. So, your $m(k)$ function is basically just the reciprocal of the distance $[k\alpha]$ from $k\alpha$ to $\mathbb{Z}$. As zeb said, the growth of $m(k)$ is basically controlled by the continued fraction expansion of $\alpha$. For example, if $\alpha$ is quadratic irrational, then $m(k) = o(k^{2+t})$ for all $t > 0$. | |
| Oct 31, 2020 at 14:20 | comment | added | zeb | I haven't worked out the explicit bound in terms of $k$ - I suspect that without too much effort you may be able to get an explicit quadratic or linear bound in $k$ for the Fibonacci word (since the golden ratio has nice rational approximations). Perhaps you can do better with other words - this seems like a natural followup question to ask! | |
| Oct 30, 2020 at 17:05 | vote | accept | Pace Nielsen | ||
| Oct 30, 2020 at 16:06 | comment | added | Pace Nielsen | Excellent answer. This gives a bound, $m$, in terms of a rather complicated function of $k$. Do you know if a "nicer" bound can be given for $m$ (in terms of a relatively slow growing function of $k$)? | |
| Oct 30, 2020 at 2:15 | comment | added | Narad Rampersad | I think Olga Parshina has looked at Question 1 for the Thue-Morse word here. | |
| Oct 30, 2020 at 0:47 | history | answered | zeb | CC BY-SA 4.0 |