32
$\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$ with $v$ nonempty, and $b$ is the length of the longest $v$ verifying $wx=uv^a$. Clearly $R_w(0)\ne R_w(1)$ if $w$ is a nonempty word.

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-1}$. 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 a suffix $s$ repeating at least $M$ times. This is only possible if there was already a word of type $s^{M-1}$. Then by hypothesis $|s|>|w|$, but if $M>> |a|$, you have no room to get (at least) $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 now indexed on OEIS here.

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).

I add a plot where blue dots represent the length of the longest repeated suffix at every digit, i.e. of the second element in the pair $R_{b_1\dots b_{n-1}}(b_n)$ defined above, putting zero if no suffix is repeated more than once. It turns out that multiple times the sequence up to some digit is itself a square word.

Blue dots represent the length of the longest repeated suffix at every digit of the sequence up to 5000

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$.

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 the first digit of the sequence $\mathcal{B}(0^m)$ is 1 for every $m$. Therefore, when computing any digit of $\mathcal{B}(\overline{0})$, the process of checking backwords to decide whether to insert 0 or 1 has to stabilize at some point, because looking further back one is certain to find only zeroes, which cannot change our choice. Therefore the limit sequence exists.

In fact, the answer to this question suggests that $S$ may well be of full measure.

$\endgroup$
13
  • 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, 2020 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$ Nov 22, 2020 at 4:49
  • 1
    $\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$ Nov 22, 2020 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, 2020 at 7:52
  • 1
    $\begingroup$ Now on OEIS at: oeis.org/A337546 $\endgroup$ Dec 22, 2020 at 7:14

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.