16
$\begingroup$

If we want to compare the repetitiveness of two finite words, it looks reasonable, first of all, to consider more repetitive the word repeating more times one of its factors, and secondarily to consider more repetitive the word repeating larger factors. This motivates the following definitions.

Let $w\in\{0,1\}^*$ be a finite binary word. Let us say that the digit $x\in\{0,1\}$ has repetition pair $(a,b)$ for $w$, in symbols that $R_w(x)=(a,b)$, if $a$ is the largest integer such that $wx$ has a suffix of the form $v^a$, and $b$ is the length of the longest $v$ verifying $wx=uv^a$. Clearly $R_w(0)\ne R_w(1)$.

Consider now the sequence which tries to avoid as much as possible being repetitive. This sequence $b\in\{0,1\}^\omega$ is defined as follows: $b_1=0$ and, for every $n>1$, $b_n=0$ if $R_{b_1,\dots,b_{n-1}}(0)<R_{b_1,\dots,b_{n-1}}(1)$ (where the pairs are ordered lexicographically), $b_n=1$ otherwise. This yields: $$b=0,1,0,0,1,1,0,1,0,0,1,0,1,1,0,0,1,0,0,1,1,0,\dotsc.$$

Fact: the sequence is not eventually periodic. Proof: Suppose by absurd that $w$ is the shortest word such that $b=a\overline{w}$ for some (possibly empty) word $a$. You can take $M$ so large that there is no word $v$ shorter than $w$ such that $b$ has a prefix of type $a'v^M$. Suppose that at step $N=|a|+M|w|$ you chose, say, $b_N=0$ to get the prefix $aw^{M}$. This means that, by picking $b_N=1$, you would have had another suffix $s$ repeating at least $M$ times. Then by hypothesis $|s|<|w|$, but if $M>> |a|$, you have no room to get $M+1$ repetitions of a word longer than $w$.

Some natural questions:

Q1: what is the asymptotic density of 0s in $b$ (if it exists)?

Q2: when does the first triple occur? (Maybe never?) What is the critical exponent of the sequence?

Q3: is the sequence recurrent (that is: every factor appears twice, hence infinitely many times)?

Q4: considered as the binary expansion of a point in $(0,1)$, does it produce a transcendental number?

The sequence is not yet indexed on OEIS (I think I'm going to submit it, it seems fun).

Psychological remark: like most of easily bored personalities, this sequence is a bit of a sad one. Indeed, although trying as much as possible to avoid repetitions at each step, it ends up being more repetitive than its more popular friend the Thue-Morse sequence, which "locally" pursues a completely different goal, but globally achieves less repetitiveness (critical exponent=2).

Some further thoughts

You can generalize the proposed construction a bit. Take $w\in\{0,1\}^*$. You can define an "easily bored" sequence with prefix $w$ as the sequence $\mathcal{B}(w)=s_1s_2\dots$ selecting $x\in\{0,1\}$ at step $n$, so as to minimize the pair $R_{ws_1\dots s_{n-1}}(x)$. Notice that, in this way, $b$ is one of the two elements (the other being simply its complement sequence) of $\mathcal{B}(\epsilon)$, where $\epsilon$ is the empty word, while every nonempty finite word $w$ is associated to a unique sequence $\mathcal{B}(w)$, so that we can define the map: $$\mathcal{B}:w\in\{0,1\}^+\longrightarrow \{0,1\}^\omega$$ whose properties look not trivial.

You can also go a bit further. Indeed, given an infinite binary sequence $w=w_1w_2\dots \in\{0,1\}^\omega$, you can define $\mathcal{B}(w)$ as the limit sequence (if it exists) of: $\mathcal{B}(w^1), \mathcal{B}(w^2),\dots$, where $w^k$ is the finite word $w_kw_{k-1}\dots w_1$. This yields a final question:

Q5: how to characterize the subset $S\subset \{0,1\}^\omega$ such that $$\mathcal{B}:S\to \{0,1\}^\omega$$ is well defined?

Fact: the set $S$ is nonempty. Sketch of the proof: $\overline{0}\in S$. Indeed, you can check directly that the first, say, 10 digits of the sequence $\mathcal{B}(0^m)$ are fixed for every $m$, and they contain some 1s. Therefore, at each step, the process of checking backwords the repetitions to decide whether to insert 0 or 1 has to stabilize at some point, because looking further one is certain to find only zeroes. Therefore the limit sequence exists.

$\endgroup$
11
  • 4
    $\begingroup$ Please use MathJax for italic and bold *italic* and **bold**; it fits better with the other text than the corresponding TeX $\textit{italic}$ and $\textbf{bold}$ $\textit{italic}$ and $\textbf{bold}$. I have edited accordingly. $\endgroup$ – LSpice Nov 22 '20 at 1:44
  • 3
    $\begingroup$ This look like a very interesting and complex sequence! Computations suggest that the density of 0's is $1/2$ and that there are no triples. Moreover the critical exponent for the first 5000 letters is $8/3$. I don't see immediately how to prove these observations however. $\endgroup$ – Antoine Labelle Nov 22 '20 at 4:49
  • $\begingroup$ This is known as the Linus sequence... $\endgroup$ – Anthony Quas Nov 22 '20 at 6:02
  • $\begingroup$ I didn’t know about the Linus sequence, but actually it’s not the same, as there the shorter repeated term is always preferred, while here the smaller number of repetitions is avoided in the first place, and only this being equal they shorter repeated word is selected. You can see that the Linus sequence has triples very soon, by the way, see this paper: memphis.edu/msci/people/pbalistr/linus.pdf $\endgroup$ – Alessandro Della Corte Nov 22 '20 at 6:50
  • 4
    $\begingroup$ @JamesBaxter - since you're adding a single digit to the end, a subword of the form $v^a$ that is not a suffix was already present in $w$, would be my guess. $\endgroup$ – Simon Rose Nov 22 '20 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.