Asymptotic formula for balanced words (Q2116747): Difference between revisions

A word \(w\) over the alphabet \(\{0, 1\}\) is said to be balanced, if, for every pair of subwords \(u\) and \(v\) of \(w\) with equal length, one has \(||u|_1-|v|_1| \leq 1\), where \(|w'|_1\) denotes the number of \(1\)s in the word \(w'\). It is well known that for any balanced word \(x = x_1 \dotsm x_n\) one can find a slope \(\alpha \in [0,1]\) and intercept \(\rho \in [0,1)\) such that \[ x_j = \lfloor \alpha(j+1)+\rho \rfloor - \lfloor \alpha j+\rho \rfloor \] for every \(j = 1, \dotsc, n\). Naturally the choice of \(\alpha, \rho\) is not unique. Rather a balanced word corresponds to \(\rho, \alpha\) in a convex polygon in \([0, 1) \times [0,1]\). This is nicely demonstrated in Figure 1 of the manuscript. Write \(B(n, t, u)\) for the cardinality of the set of balanced words of length \(n\) with \(\alpha \in [1-t, 1]\) and \(\rho \in [0, u)\). In Theorem 1, the author shows that \[ B(n, t, u) = 1+ \sum_{m \leq n} \sum_{0 \leq i < j \leq m, \, (i, j) = 1 \\ i/j \leq t, \, \langle mi/j \rangle < u} 1, \] where \(\langle x \rangle = x - \lfloor x \rfloor\). Then the author goes on to employ techniques from analytic number theory to provide asymptotic formulae for \(B(n, t, u)\). In particular in Theorem 2 it is shown that \[ B(n, t, u) = \frac{tu}{\pi^2} n^3 + O(n^2(\log n)^{15/2}). \]