1
$\begingroup$

The Fibonacci word is a binary sequence defined as follows. We use a substitution rule $0\to 01$, $1\to 0$. Then, starting with the binary string $0$, apply the substitution rules successively. So we get $S_0=0$, $S_1=01$, $S_2=010$, $S_3=01001,\ldots$ and ultimately we get the following aperiodic sequence in $\{0,1\}^{\mathbb Z_+}$, known as the Fibonacci word: $$ 0100101001001\ldots $$ For $S\in \{0,1\}^{\mathbb Z_+}$ and $n\in\mathbb Z_+$, let us define the complexity function $\sigma_n(S)$ as the number of distinct subwords of length $n$ in $S$. It is well-known that if $S$ is the Fibonacci word defined above then $\sigma_n(S)=n+1$. Here is my question:

Given a real number $x>1$. Construct a binary substitution rule $0\to A$, $1\to B$ (here $A$ and $B$ are finite binary strings) where, starting with $0$ and applying the substitution rule successively we get an infinite aperiodic sequence $S$ in $\{0,1\}^{\mathbb Z_+}$ so that $$\lim_{n\to\infty} \frac{\sigma_n(S)}{n}= x$$

Note that $A$ and $B$ must be chosen so that if $S_k$ is the binary string we get starting with $0$ and applying the substitution rule $k$ times, then $S_k$ is a prefix of $S_\ell$ for every $\ell>k$. That way the sequence $S_k$ stabilizes to an infinite binary sequence $S$ as $k$ tends to infinity.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

There are a few things to say here! This is impossible for multiple reasons.

Firstly, there are only countably many substitutions, so there's no hope of achieving every possible $x$ as the "slope" of the complexity function.

More importantly, it's actually not possible for ANY subshift $S$ to satisfy $\sigma_n(S)/n \rightarrow x$ for $x \notin \mathbb{N}$. This is a theorem due to Heinis for the case $x \in (1,2)$ and Cassaigne in the general case.

I should note that this theorem is for two-sided subshifts, and in general I'd need to think about whether it's possible to do more with one-sided subshifts (I suspect not though). But for your question this distinction is moot; substitution sequences are recurrent and so the two-sided subshift generated (the so-called natural extension) has the same language. In other words, for substitutions, the only $x$ that can be achieved in your way are integers.

Another very cool result is due to Pansiot, who showed that for substitutions, the word complexity is "near" (i.e. bounded above and below by constant multiples) either $n$, $n^2$, $n \log n$, or $n \log \log n$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Oh wow, these are some cool results. Thanks for the references! I will look them up. Do you know if an explicit construction exists if we restrict x to be a natural number? $\endgroup$
    – Darren Ong
    Commented Jan 1, 2023 at 8:20
  • 1
    $\begingroup$ Sure, this is quite easy. Among other things, you can generalize the so-called Sturmian shifts (of which your Fibonacci shift is one!) Sturmians are obtained as follows: iterate addition mod 1 of $\alpha \notin \mathbb{Q}$, and code orbits by whether they land in $I_0 = [0, \alpha)$ or $I_1 = [\alpha, 1)$. In other words, generate a $0$-$1$ sequence $s$ by $s(n) = 0$ iff $n\alpha \pmod 1 \in [0, \alpha)$. Then $s$ always has word complexity $n+1$. Simple changes will yield roughly $kn$ for integer $k$; one is to use $\alpha$, $\ldots$, $k\alpha$ as the endpoints for $k+1$ intervals. $\endgroup$
    – Ronnie Pavlov
    Commented Jan 1, 2023 at 16:07
  • $\begingroup$ Thanks @Ronnie Pavlov, that was helpful. To clarify, does your $k+1$ interval shift generate a binary sequence? If I understand correctly what you said, we get $k+1$ intervals, and then we assign a different symbol for each of the $k+1$ intervals, thus generating a sequence with $k+1$ symbols rather than $2$. If I understood that correctly, is there a way to instead generate a binary sequence with complexity kn for positive integer $k$? $\endgroup$
    – Darren Ong
    Commented Jan 3, 2023 at 7:45
  • 1
    $\begingroup$ Ah I forgot you want a 0-1 sequence. Here's something self-contained but a bit clunky; I'm skipping some details. Take the sequence $s$ on $\{0, \ldots, k\}$ above, and make a new sequence $s'$ by replacing each letter $i$ by $0^{i+1} 1^{k+1-i}$, i.e. $i+1$ $0$s followed by $k+1-i$ $1$s. Denote $L = k+2$. Then, any word of length $mL+i$ in $s'$ ($0 \leq i<L$) is determined by a "phase shift" modulo $L$ and a word in $s$ of length between $m$ and $m+2$. In other words, $L \sigma_m(s) \leq \sigma_{mL+i}(s') \leq L \sigma_{m+2}(s)$. It's routine to check that $\sigma_n(s')/n \rightarrow k$. $\endgroup$
    – Ronnie Pavlov
    Commented Jan 3, 2023 at 16:06
  • 1
    $\begingroup$ Also, here are better references: 1. Alex Heinis, "The P(n)/n-function for bi-infinite words," Theoretical Comp. Sci. 2. I don't have the Cassaigne reference. I'm worried it might be "folklore." 3. Jean-Jacques Pansiot, "Complexit´e des facteurs des mots infinis engendr´es par morphismes it´er´es," Lecture Notes in Computer Science. $\endgroup$
    – Ronnie Pavlov
    Commented Jan 3, 2023 at 16:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .